This paper defines the research area of Diversity-enhanced Autonomy in Robot Teams (DART), a novel paradigm for the creation and design of policies for multi-robot coordination. Although current approaches to multi-robot coordination have been successful in structured, well-understood environments, they have not been successful in unstructured, uncertain environments, such as disaster response. Although robot hardware has advanced significantly in the past decade, the way we solve multi-robot problems has not. Even with significant advances in the field of multi-robot systems, the same problem-solving paradigm has remained: assumptions are made to simplify the problem, and a solution is optimized for those assumptions and deployed to the entire team. This results in brittle solutions that prove incapable if the original assumptions are invalidated. This paper introduces a new multi-robot problem-solving paradigm which uses a diverse set of control policies that work together synergistically within the same team of robots. Such an approach will make multi-robot systems more robust in unstructured and uncertain environments, such as in disaster response, environmental monitoring, and military applications, and allow multi-robot systems to extend beyond the highly structured and highly controlled environments where they are successful today.
more »
« less
DART: Diversity-enhanced Autonomy in Robot Teams
This paper defines the research area of Diversity-enhanced Autonomy in Robot Teams (DART), a novel paradigm for the creation and design of policies for multi-robot coordination. While current approaches to multi-robot coordination have been successful in structured, well understood environments, they have not been successful in unstructured, uncertain environments, such as disaster response. The reason for this is not due to limitations in robot hardware, which has advanced significantly in the past decade, but in how multi-robot problems are solved. Even with significant advances in the field of multi-robot systems, the same problem-solving paradigm has remained: assumptions are made to simplify the problem, and a solution is optimized for those assumptions and deployed on the entire team. This results in brittle solutions that prove incapable if the original assumptions are invalidated. This paper introduces a new multi-robot problem-solving paradigm which relies on diverse control policies to make multi-robot systems more resilient to uncertain environments.
more »
« less
- Award ID(s):
- 1553726
- PAR ID:
- 10081426
- Date Published:
- Journal Name:
- International Symposium on Robotics Research
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider multi-robot service scenarios, where tasks appear at any time and in any location of the working area. A solution to such a service task problem requires finding a suitable task assignment and a collision-free trajectory for each robot of a multi-robot team. In cluttered environments, such as indoor spaces with hallways, those two problems are tightly coupled. We propose a decentralized algorithm for simultaneously solving both problems, called Hierarchical Task Assignment and Path Finding (HTAPF). HTAPF extends a previous bio-inspired Multi-Robot Task Allocation (MRTA) framework [1]. In this work, task allocation is performed on an arbitrarily deep hierarchy of work areas and is tightly coupled with a fully distributed version of the priority-based planning paradigm [12], using only broadcast communication. Specifically, priorities are assigned implicitly by the order in which data is received from nearby robots. No token passing procedure or specific schedule is in place ensuring robust execution also in the presence of limited probabilistic communication and robot failures.more » « less
-
Multi-stage stochastic linear programs (MSLPs) are notoriously hard to solve in general. Linear decision rules (LDRs) yield an approximation of an MSLP by restricting the decisions at each stage to be an affine function of the observed uncertain parameters. Finding an optimal LDR is a static optimization problem that provides an upper bound on the optimal value of the MSLP, and, under certain assumptions, can be formulated as an explicit linear program. Similarly, as proposed by Kuhn et al. (Math Program 130(1):177–209, 2011) a lower bound for an MSLP can be obtained by restricting decisions in the dual of the MSLP to follow an LDR. We propose a new approximation approach for MSLPs, two-stage LDRs. The idea is to require only the state variables in an MSLP to follow an LDR, which is sufficient to obtain an approximation of an MSLP that is a two-stage stochastic linear program (2SLP). We similarly propose to apply LDR only to a subset of the variables in the dual of the MSLP, which yields a 2SLP approximation of the dual that provides a lower bound on the optimal value of the MSLP. Although solving the corresponding 2SLP approximations exactly is intractable in general, we investigate how approximate solution approaches that have been developed for solving 2SLP can be applied to solve these approximation problems, and derive statistical upper and lower bounds on the optimal value of the MSLP. In addition to potentially yielding better policies and bounds, this approach requires many fewer assumptions than are required to obtain an explicit reformulation when using the standard static LDR approach. A computational study on two example problems demonstrates that using a two-stage LDR can yield significantly better primal policies and modestly better dual policies than using policies based on a static LDR.more » « less
-
One potential application of multirobot systems is collective transport, a task in which multiple robots collaboratively move a payload that is too large or heavy for a single robot. In this review, we highlight a variety of control strategies for collective transport that have been developed over the past three decades. We characterize the problem scenarios that have been addressed in terms of the control objective, the robot platform and its interaction with the payload, and the robots’ capabilities and information about the payload and environment. We categorize the control strategies according to whether their sensing, computation, and communication functions are performed by a centralized supervisor or specialized robot or autonomously by the robots. We provide an overview of progress toward control strategies that can be implemented on robots with expanded autonomous functionality in uncertain environments using limited information, and we suggest directions for future work on developing such controllers.more » « less
-
In large scale coverage operations, such as marine exploration or aerial monitoring, single robot approaches are not ideal, as they may take too long to cover a large area. In such scenarios, multi-robot approaches are preferable. Furthermore, several real world vehicles are non-holonomic, but can be modeled using Dubins vehicle kinematics. This paper focuses on environmental monitoring of aquatic environments using Autonomous Surface Vehicles (ASVs). In particular, we propose a novel approach for solving the problem of complete coverage of a known environment by a multi-robot team consisting of Dubins vehicles. It is worth noting that both multi-robot coverage and Dubins vehicle coverage are NP-complete problems. As such, we present two heuristics methods based on a variant of the traveling salesman problem-k-TSP-formulation and clustering algorithms that efficiently solve the problem. The proposed methods are tested both in simulations to assess their scalability and with a team of ASVs operating on a 200 km 2 lake to ensure their applicability in real world.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
