面向关隘地形的分层调度多机器人路径规划  

Hierarchical scheduling based multi-robot path planning for pass terrain

作　　者：张凯翔 毛剑琳[2] 宣志玮 向凤红[2] 付丽霞[2] ZHANG Kaixiang;MAO Jianlin;XUAN Zhiwei;XIANG Fenghong;FU Lixia(Faculty of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming 650500,China;Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

机构地区：[1]昆明理工大学机电工程学院,云南昆明650500 [2]昆明理工大学信息工程与自动化学院,云南昆明650500

出　　处：《计算机集成制造系统》2024年第1期172-183,共12页Computer Integrated Manufacturing Systems

基　　金：云南省重点研发计划资助项目(202002AC080001);国家自然科学基金资助项目(62263017)。

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]