Abstract | ||
---|---|---|
Discovering high-quality paths for multirobot problems can be achieved, in principle, by exploring the composite space of all robots. For instance, sampling-based algorithms that build either roadmaps or tree data structures achieve asymptotic optimality. The hardness of motion planning, however, which implies an exponential dependence on problem dimensionality, renders the explicit construction of such structures in the composite space of all robots impractical. This work proposes a scalable, sampling-based planner for coupled multi-robot problems that provides desirable path-quality guarantees. The proposed dRRT* is an informed, asymptotically-optimal extension of a prior method dRRT, which introduced the idea of building roadmaps for each robot and implicitly searching the tensor product of these structures in the composite space. The paper describes the conditions for convergence to optimal paths in multi-robot problems, which is not feasible for the prior method. Moreover, simulations indicate dRRT* converges to high-quality paths and scales to higher numbers of robots where various alternatives fail. It can also be used on high-dimensional challenges, such as planning for robot manipulators. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1109/MRS.2017.8250940 | 2017 International Symposium on Multi-Robot and Multi-Agent Systems (MRS) |
Keywords | DocType | Volume |
scalable sampling,coupled multirobot problems,desirable path-quality guarantees,asymptotically-optimal extension,prior method dRRT,roadmaps,composite space,optimal paths,high-quality paths,high-dimensional challenges,robot manipulators,sampling-based algorithms,tree data structures,exponential dependence,problem dimensionality,scalable asymptotically-optimal multirobot motion planning | Conference | abs/1706.09932 |
ISBN | Citations | PageRank |
978-1-5090-6310-9 | 1 | 0.35 |
References | Authors | |
14 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrew Dobson | 1 | 50 | 3.90 |
Kiril Solovey | 2 | 71 | 10.30 |
Rahul Shome | 3 | 34 | 6.07 |
Dan Halperin | 4 | 1291 | 105.20 |
Kostas E. Bekris | 5 | 938 | 99.49 |