基于讨价还价博弈机制的B-IHCA^(*)多机器人路径规划算法  

B-IHCA^(*),a Bargaining Game Based Multi-agent Path Finding Algorithm

作　　者：张凯翔 毛剑琳[2] 向凤红[2] 宣志玮 ZHANG Kai-Xiang;MAO Jian-Lin;XIANG Feng-Hong;XUAN Zhi-Wei(Faculty of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming 650500;Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500)

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

出　　处：《自动化学报》2023年第7期1483-1497,共15页Acta Automatica Sinica

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

摘　　要：针对密集场景中大规模冲突导致多机器人路径规划(Multi-agent path finding,MAPF)成功率低的问题,引入讨价还价博弈机制并以层级协作A^(*)(Hierarchical cooperative A^(*),HCA^(*))算法为内核,提出一种基于讨价还价博弈机制的改进层级协作A^(*)(Bargaining game based improving HCA^(*),B-IHCA^(*))算法.首先,在HCA^(*)算法基础上,对导致路径无解的冲突双方或多方进行讨价还价博弈.由高优先级机器人先出价,当低优先级机器人在该条件下无法求解时,则其将不接受该出价,并通过降约束求解方式进行还价.再由其他冲突方对此做进一步还价,直至各冲突方都能协调得到可接受的路径方案.其次,为避免原始HCA^(*)算法由于高优先级的阻碍陷于过长或反复无效搜索状态,在底层A^(*)搜索环节加入了熔断机制.通过熔断机制与讨价还价博弈相配合可在提升路径求解成功率的同时兼顾路径代价.研究结果表明,所提算法在密集场景大规模机器人路径规划问题上较现有算法求解成功率更高、求解时间更短,路径代价得到改善,验证了算法的有效性.Large-scale conflict of paths is a reason which can hugely reduce the success rate for multi-agent path finding(MAPF)in dense scenarios.For this problem,a bargaining game based improving hierarchical cooperation A^(*)(B-IHCA^(*))algorithm is proposed by introducing bargaining game mechanism and taking hierarchical cooperation A^(*)(HCA^(*))algorithm as the core.Firstly,based on the HCA^(*)algorithm,the bargaining game is performed between the two or more parties that leads to conflicts and the unsolved state.The high-priority agent finds a path and bids first.If the low-priority agent cannot get a path with constraint of the bid,it will does not accept the bid and counter-offer another path by reducing the constraint.And then the other conflicting parties will make further counter-offers until all conflicting parties can coordinate to obtain an acceptable path scheme.Secondly,in order to avoid the state of too long or repeated invalid search of HCA^(*)algorithm due to the obstruction of high-priority agent,a fusing mechanism is added to its bottom A^(*)algorithm.Accordingly,by the cooperation of bargaining game and fusing mechanism,the success rate of the paths finding can be improved while taking into account the path costs.The results show that,compared with the existing algorithms,the proposed algorithm has higher success rate,shorter time consumption and ameliorative path costs for large-scale MAPF problem in dense scenarios,which verifies the effectiveness of the algorithm.

关 键 词：多机器人 路径规划 讨价还价博弈 解耦 协作 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置] TP18[自动化与计算机技术—控制科学与工程]