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

摘要： 针对关隘地形下多机器人路径规划存在的高度耦合性,引入调度次序优化思想构造了分层的多机器人路径求解与优化算法。首先,在优化层采用遗传算法生成所有机器人的调度次序,并根据适应度对调度次序进行迭代和进化。其次,根据优化层制定的调度次序,在规划层采用改进的层级协作A*(IHCA*)算法进行路径求解,并将求解结果返回上层以对该次序的适应度进行更新。最后,通过上下层相互配合,逐步提升问题求解成功率并降低路径耗时。此外,提出搜索熔断机制,避免原始HCA*算法在关隘地形中陷于反复无效搜索的状态,可进一步提升求解效率。研究结果表明,所提算法在高耦合关隘环境下具有较高的求解成功率,且路径总耗时更少。

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