An official website of the United States government
We study the labeled multi-robot path planning problem in continuous 2D and 3D domains in the absence of obstacles where robots must not collide with each other. For an arbitrary number of robots in arbitrary initial and goal arrangements, we derive a polynomial time, complete algorithm that produces solutions with constant-factor optimality guarantees on both makespan and distance optimality, in expectation, under the assumption that the robot labels are uniformly randomly distributed. Our algorithm only requires a small constant-factor expansion of the initial and goal configuration footprints for solving the problem, i.e., the problem can be solved in a fairly small bounded region. Beside theoretical guarantees, we present a thorough computational evaluation of the proposed solution. In addition to the baseline implementation, adapting an effective (but non-polynomial time) routing subroutine, we also provide a highly efficient implementation that quickly computes near-optimal solutions. Hardware experiments on the microMVP platform composed of non-holonomic robots confirms the practical applicability of our algorithmic pipeline.
more »
« less
Assignment Algorithms for Variable Robot Formations
This paper describes algorithms to perform optimal assignment of teams of robots translating in the plane from an initial formation to a variable goal formation. We consider the case when each robot is to be assigned a goal position, the individual robots are interchangeable, and the goal formation can be scaled or translated.We compute the costs for all candidate pairs of initial, goal robot assignments as functions of the parameters of the goal formation, and partition the parameter space into equivalence classes invariant to the cost order using computational geometry techniques. We compute a minimum completion time assignment for an equivalence class by formulating it as a linear bottleneck assignment problem (LBAP). To improve efficiency, we solve the LBAP problem for each equivalence class by incrementally updating the solution as the formation parameters are varied. This work is motivated by applications that include the motion of droplet formations in digital microuidic lab-on-a-chip devices, and of robot and drone formations in the plane.
more »
« less
- Award ID(s):
- 1547175
- PAR ID:
- 10039660
- Editor(s):
- Goldberg, Ken; Abbeel, Pieter; Bekris, Kostas; Miller, Lauren
- Date Published:
- Journal Name:
- Algorithmic Foundations of Robotics XII
- Page Range / eLocation ID:
- 912-927
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the problem of deploying robots to observe the evolution of a stochastic process in order to output a sequence of observations that fit some given specification. This problem often arises in contexts such as event reporting, situation depiction, and automated narrative generation. The paper extends our prior work by formulating and examining the multi-robot case: a team of robots move about, each recording what they observe, and, if they manage to capture some event, communicating that fact with the group. In the end, all events from all the robots are collated to provide a cumulative output. A plan is used to decide what each robot will attempt to capture next, based on the state of the world and the events that have been captured (collectively) so far. This paper focuses on the question of how to compute effective multi-robot plans. A monolithic treatment, involving the optimal selection of joint choices, i.e., choosing the next elements to attempt to capture by all robots, is formulated where costs are minimized in an expected sense. Since such plans are prohibitive to compute, variants based on an approximation scheme based on solving a sequence of individual planning problems are then introduced. This scheme sacrifices some solution quality but requires far less computational expense; we show this permits one to scale to greater numbers of robots.more » « less
-
Goal-conditioned policies, such as those learned via imitation learning, provide an easy way for humans to influence what tasks robots accomplish. However, these robot policies are not guaranteed to execute safely or to succeed when faced with out-of-distribution goal requests. In this work, we enable robots to know when they can confidently execute a user’s desired goal, and automatically suggest safe alternatives when they cannot. Our approach is inspired by control-theoretic safety filtering, wherein a safety filter minimally adjusts a robot’s candidate action to be safe. Our key idea is to pose alternative suggestion as a safe control problem in goal space, rather than in action space. Offline, we use reachability analysis to compute a goal-parameterized reach-avoid value network which quantifies the safety and liveness of the robot’s pre- trained policy. Online, our robot uses the reach-avoid value network as a safety filter, monitoring the human’s given goal and actively suggesting alternatives that are similar but meet the safety specification. We demonstrate our Safe ALTernatives (SALT) framework in simulation experiments with indoor navigation and Franka Panda tabletop manipulation, and with both discrete and continuous goal representations. We find that SALT is able to learn to predict successful and failed closed-loop executions, is a less pessimistic monitor than open- loop uncertainty quantification, and proposes alternatives that consistently align with those that people find acceptable.more » « less
-
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-robot cooperative control has been extensively studied using model-based distributed control methods. However, such control methods rely on sensing and perception modules in a sequential pipeline design, and the separation of perception and controls may cause processing latencies and compounding errors that affect control performance. End-to-end learning overcomes this limitation by implementing direct learning from onboard sensing data, with control commands output to the robots. Challenges exist in end-to-end learning for multi-robot cooperative control, and previous results are not scalable. We propose in this article a novel decentralized cooperative control method for multi-robot formations using deep neural networks, in which inter-robot communication is modeled by a graph neural network (GNN). Our method takes LiDAR sensor data as input, and the control policy is learned from demonstrations that are provided by an expert controller for decentralized formation control. Although it is trained with a fixed number of robots, the learned control policy is scalable. Evaluation in a robot simulator demonstrates the triangular formation behavior of multi-robot teams of different sizes under the learned control policy.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-030-43089-4_58
