一种基于改进冲突搜索的多机器人路径规划算法

A multi-robot path finding algorithm based on improved conflict search

针对智能仓储环境下多载位自主移动机器人集群拣选-配送路径规划问题,提出一种改进型基于冲突搜索的多智能体路径规划算法.在模型方面,采用多载位机器人替代KIVA机器人,建立以最小化拣选-配送时间以及无效路径比为目标的数学规划模型.在算法方面,首先,提出一种基于优先级规则的多智能体冲突消解加速策略;然后,设计基于动态规划的单机器人拣选序列优化算法;最后,设计考虑转向惩罚的增强A^(*)算法搜索机器人最优路径.实验结果表明:所提出模型与KIVA系统相比有较大优越性;所提出算法能够有效缩短拣选-配送时间、减少无效路径时间.

An improved multi-agent path finding algorithm based on the conflict search algorithm is proposed for the path planning problem of picking-delivery with mobile robot clusters in the smart storage environment.In terms of the model,a mathematical planning model with the objective of minimizing the picking-delivery time and the invalid path ratio is established by using multi-carrier robots instead of KIVA robots.In terms of the algorithm,firstly a priority rule-based multi-intelligent conflict resolution acceleration strategy is proposed.Then a single-robot picking sequence optimization algorithm based on dynamic planning is designed.Finally,an enhanced A^(*)algorithm with the consideration of turning penalty is proposed to search for the optimal robot path.The experimental results show that the proposed model is superior to the KIVA system.The proposed algorithm can effectively shorten the picking-delivery time and reduce the invalid path time.