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

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