A complete and scalable strategy for coordinating multiple robots within roadmaps
A complete and scalable strategy for coordinating multiple robots within roadmaps
复制标题
DOI：
10.1109/tro.2008.918056
复制
发表时间：
2008-04-01
影响因子：
7.8
通讯作者：
McPhee, John
中科院分区：
文献类型：
--
作者：
Peasgood, Mike;Clark, Christopher Michael;McPhee, John
本文解决了为许多机器人寻找无冲突的轨迹的挑战性问题。多机器人计划的最流行算法通过单独规划机器人计划轨迹来管理问题的复杂性；如果存在这样的解耦方法，则不能保证找到解决方案。相比之下，本文描述了针对计划问题的多相方法，该方法使用图形并跨越树表示，以创建和维护环境环境中的无障碍路径，以使每个机器人达到目标。所得算法保证了在公共环境中定义明确数量的机器人的解决方案。在机器人数量中，计算成本可扩展具有线性的可扩展性，并通过解决100个机器人的计划问题，在地下矿山环境中模拟的100个机器人的规划问题，并在不到1.5 GHz处理器的情况下在不到1.5 s的情况下进行了模拟。在现实的应用中，该算法的实用性已在需要多个物理机器人的协调运动计划中证明。
This paper addresses the challenging problem of finding collision-free trajectories for many robots moving toward individual goals within a common environment. Most popular algorithms for multirobot planning manage the complexity of the problem by planning trajectories for robots individually; such decoupled methods are not guaranteed to find a solution if one exists. In contrast, this paper describes a multiphase approach to the planning problem that uses a graph and spanning tree representation to create and maintain obstacle-free paths through the environment for each robot to reach its goal. The resulting algorithm guarantees a solution for a well-defined number of robots in a common environment. The computational cost is shown to be scalable with complexity linear in the number of the robots, and demonstrated by solving the planning problem for 100 robots, simulated in an underground mine environment, in less than 1.5 s with a 1.5 GHz processor. The practicality of the algorithm is demonstrated in a real-world application requiring coordinated motion planning of multiple physical robots.