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

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

针对密集场景中大规模冲突导致多机器人路径规划(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.