Abstract: In view of the shortcomings of the current path planning strategies for multiple robots, such as high path coupling, long total path, long waiting time for collision avoidance, and the resulting problems of low system robustness and low robot utilization, a multi-robot path planning algorithm based on 3D spatiotemporal maps and motion decomposition was proposed. Firstly, the dynamic temporary obstacles in time dimension were generated according to the existing path set and the current robots' positions, and were expanded into 3D search space together with the static obstacles. Secondly, in the 3D search space, the total time of path motion was divided into three parameters:motion time, turning time, and in-situ dwell time, and the conditional depth first search strategy was used to calculate the set of all paths from the starting node to the target node that met the parameter requirements. Finally, all paths in the path set were traversed. For each path, the actual total time consumption was calculated. If the difference between the actual total time consumption and the theoretical total time consumption of a path was less than the specified maximum error, the path was considered as the shortest path. Otherwise, the remaining paths were continued to traverse. And if the differences between the actual total time and the theoretical total time of all paths in the set were greater than the maximum error, the parameters needed to be adjusted dynamically, and then the initial steps of algorithm were continued to execute. Experimental results show that, the path planned by the proposed algorithm has the advantages of short total length, less running time, no collision and high robustness, and the proposed algorithm can solve the problem of completing continuous random tasks by multi-robot system.

Key words: multi-robot path planning, distributed, 3D spatiotemporal, depth first search, A^* algorithm, ant colony algorithm

摘要： 针对当前多机器人路径规划策略中存在的路径耦合性高、总路径长、避碰等待时间长等缺点，以及由此导致的系统鲁棒性低、机器人利用率低等问题，提出了基于三维时空地图和运动分解的多机器人路径规划算法。首先，根据已有路径集和当前机器人的位置生成时间维度上的动态临时障碍物，将其与静态障碍物一并拓展为三维搜索空间；其次，在三维搜索空间内，将路径运动总时间拆分为运动时间、转向时间和原地停留时间这三个参数，并使用条件深度优先搜索策略计算出从起始节点到达目标节点的所有符合参数要求的路径集合；最后，遍历路径集合中的所有路径，对于每条路径，计算其实际总耗时。如果某一路径的实际总耗时和理论总耗时之间的差距小于规定的最大误差，则可认为该路径为最短路径，否则，继续遍历剩下的其余路径；而如果路径集合中所有路径的实际总耗时和理论总耗时之差全都大于最大误差，则需要动态调整参数，然后继续执行算法的初始步骤。实验结果表明，所提算法规划的路径具有总长短、运行时间少、系统无碰撞、鲁棒性高等优点，解决了多机器人系统完成持续随机任务的问题。

关键词: 多机器人路径规划, 分布式, 三维时空, 深度优先搜索, A^*算法, 蚁群算法