摘要
轻载环境中,复杂障碍物区域将引起机器人之间局部冲突加剧,进而导致路径求解效率下降,针对该问题,提出轻载环境下带障碍物惩罚因子的多机器人路径规划方法。在基于冲突搜索(conflict-based search,CBS)算法框架的下层单机规划过程中,通过对即将拓展机器人位置的周围障碍物分布类型进行判断,赋予与之对应的障碍物惩罚因子;对路径规划过程中的惩罚因子进行累加,作为单机规划的启发值对路径进行选取;结合CBS算法框架的上层冲突消解策略进行多机器人的路径规划与冲突协调。测试结果表明,在10%障碍物分布的轻载环境中,所提算法的求解时间约为CBS算法的81.38%~83.67%,二叉约束树(constraint tree,CT)拓展量为CBS算法的60.14%~71.66%。在Gazebo中仿真表明,所提方法可减小通过复杂障碍物区域的次数。
In light load environments,complex obstacle areas will exacerbate local conflicts between agents,leading to a decrease in path solving efficiency.This paper proposes a multi-agent path planning(MAPF)method with obstacle penalty factors in light load environments.First,in the low-level single machine planning process based on the conflict-based search(CBS)algorithm framework,by judging the distribution type of surrounding obstacles that are about to expand the agent's position,corresponding obstacle penalty factors are assigned to them;then,the penalty factors in the path planning process are accumulated and used as the heuristic value of single machine planning to select the path;finally,combined with the upper-level conflict resolution strategy of the CBS algorithm framework,MAPF and conflict coordination are performed.The results show that in a light load environment with a 10%obstacle distribution,the proposed algorithm has a solving time of about 81.38%~83.67%of that of the CBS algorithm,and the expansion amount of the constraint tree(CT)is 60.14%~71.66%of that of the CBS algorithm.Simulation in Gazebo has shown that this method can reduce the number of passes through complex obstacle areas.
作者
闫星宇
李大焱
王妮娅
张凯翔
毛剑琳
Yan Xingyu;Li Dayan;Wang Niya;Zhang Kaixiang;Mao Jianlin(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;Faculty of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming 650500,China)
出处
《系统仿真学报》
CAS
CSCD
北大核心
2024年第3期673-685,共13页
Journal of System Simulation
基金
国家自然科学基金(62263017)
云南省重大科技专项计划(202002AC080001)。
关键词
轻载环境
多机器人路径规划
惩罚因子
基于冲突搜索算法
约束树
light load environment
multi-agent path finding(MAPF)
penalty factor
conflict-based search(CBS)
constraint tree(CT)
