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

摘要：

针对密集场景中大规模冲突导致多机器人路径规划(Multi-agent path finding,MAPF)成功率低的问题,引入讨价还价博弈机制并以层级协作A*(Hierarchical cooperative A*,HCA*)算法为内核,提出一种基于讨价还价博弈机制的改进层级协作A*(Bargaining game based improving HCA*,B-IHCA*)算法.首先,在HCA*算法基础上,对导致路径无解的冲突双方或多方进行讨价还价博弈.由高优先级机器人先出价,当低优先级机器人在该条件下无法求解时,则其将不接受该出价,并通过降约束求解方式进行还价.再由其他冲突方对此做进一步还价,直至各冲突方都能协调得到可接受的路径方案.其次,为避免原始HCA*算法由于高优先级的阻碍陷于过长或反复无效搜索状态,在底层A*搜索环节加入了熔断机制.通过熔断机制与讨价还价博弈相配合可在提升路径求解成功率的同时兼顾路径代价.研究结果表明,所提算法在密集场景大规模机器人路径规划问题上较现有算法求解成功率更高、求解时间更短,路径代价得到改善,验证了算法的有效性.

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

所属期刊栏目：49

分类号：TP301.6;TP242.6;U491.12

在线出版日期：2023-08-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：1483-1497