Scalable asymptotically-optimal multi-robot motion planning
Scalable asymptotically-optimal multi-robot motion planning
复制标题
可扩展渐近最优多机器人运动规划
DOI：
10.1109/mrs.2017.8250940
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Kostas E. Bekris
中科院分区：
文献类型：
--
作者：
Andrew Dobson;Kiril Solovey;Rahul Shome;D. Halperin;Kostas E. Bekris
可以通过探索所有机器人的复合空间来发现多机器人问题的高质量路径。暗示对问题维度的指数依赖性，使所有机器人的复合空间中的此类结构的明确结构不切实际可扩展的，基于抽样的计划者，用于提供理想的路径质量保证的多机器人问题。机器人和隐式搜索这些结构在复合空间中的张量。此外，模拟表明DRRT ∗将各种替代方案的机器人收敛到更高的机器人。
Discovering high-quality paths for multirobot problems can be achieved, in principle, by exploring the composite space of all robots. For instance, samplingbased 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.