关键词: 多机器人, 路径规划, 关隘地形, 调度次序, 遗传算法

Abstract: Aiming at the high coupling of multi-robot paths in pass terrain,a hierarchical multi-robot path planning and optimization algorithm was constructed by introducing the idea of scheduling order optimization.In the optimization layer,the genetic algorithm was responsible for generating the scheduling order of each robot,and evolving the scheduling order according to the fitness.Then,in the planning layer,the Improved Hierarchical Cooperative A* (IHCA*) algorithm was used to find paths according to the scheduling order from the optimization layer,and the solutions was returned to the optimization layer to update the fitness of the scheduling order.Accordingly,by the cooperation between the upper and lower layers,the success rate of problem solving was improved and the path costs were reduced.In addition,a search fuse mechanism was proposed to avoid the repeated invalid search of original HCA* algorithm in the pass terrain,which could further improve the solving efficiency.The results showed that the proposed algorithm had performance of higher success rate and less solution costs in high coupling pass terrain.

Key words: multi-robot, path planning, pass terrain, scheduling order, genetic algorithms