面向大型仓储环境的基于冲突搜索算法  

Conflict-based search algorithm for large-scale warehousing environment

作　　者：邓辅秦 谭朝恩 黎俊炜 钟家铭 付兰慧 张建民 王宏民 李楠楠 姜炳春[3] 林天麟 DENG Fuqin;TAN Chaoen;LI Junwei;ZHONG Jiaming;FU Lanhui;ZHANG Jianmin;WANG Hongmin;LI Nannan;JIANG Bingchun;LAM Tin Lun(School of Intelligent Manufacturing,Wuyi University,Jiangmen Guangdong 529020,China;The Shenzhen Institute of Artificial Intelligence and Robotics for Society,The Chinese University of Hong Kong,Shenzhen,Shenzhen Guangdong 518116,China;School of Mechanical and Electrical Engineering,Guangdong University of Science and Technology,Dongguan Guangdong 523083,China;Faculty of Innovation Engineering,Macao University of Science and Technology,Macao 999078,China)

机构地区：[1]五邑大学智能制造学部,广东江门529020 [2]香港中文大学(深圳)深圳市人工智能与机器人研究院,广东深圳518116 [3]广东科技学院机电工程学院,广东东莞523083 [4]澳门科技大学创新工程学院,中国澳门999078

出　　处：《计算机应用》2024年第12期3854-3860,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(62073274);深圳市人工智能与机器人研究院探索性研究项目(AC01202101103);五邑大学港澳联合基金资助项目(2022WGALH17,2021WGALH18)。

摘　　要：针对多智能体在大型仓储环境中进行路径规划时,现有算法有智能体易陷入拥堵区域和耗时长的问题,提出一种改良的基于冲突搜索(CBS)算法。首先,优化现有单一的仓储环境建模方式,在易解决路径冲突的传统的栅格化建模的基础上,提出栅格-热力图的混合建模方式,并通过热力图定位仓储中的拥堵区域,从而解决多智能体易陷入拥堵区域的问题;其次,通过改良的CBS算法,快速求解大型仓储环境下的多智能体路径规划(MAPF)问题;最后,提出基于热力图的显示估计冲突搜索(HM-EECBS)算法。实验结果表明,在warehouse-20-40-10-2-2大型地图集上,当智能体数为500时,相较于显示估计冲突搜索(EECBS)算法和懒惰添加约束的MAPF算法(LaCAM)算法:HM-EECBS算法的求解时间分别减少了约88%和73%;当仓储中存在5%、10%的区域拥堵时,HM-EECBS算法的成功率分别提高了约49%、20%,这表明所提算法适用于解决大规模且拥堵的仓储物流环境下的MAPF问题。When multiple agents performing path finding in large-scale warehousing environment,the existing algorithms have problems that agents are prone to fall into congestion areas and it take a long time.In response to the above problem,an improved Conflict-Based Search(CBS)algorithm was proposed.Firstly,the existing single warehousing environment modeling method was optimized.Based on the traditional grid based modeling,which is easy to solve path conflicts,a hybrid modeling method of grid-heat map was proposed,and congestion areas in the warehouse were located through a heat map,thereby addressing the issue of multiple agents prone to falling into congestion areas.Then,an improved CBS algorithm was employed to solve the Multi-Agent Path Finding(MAPF)problems in large-scale warehousing environment.Finally,a Heat Map for Explicit Estimation Conflict-Based Search(HM-EECBS)algorithm was proposed.Experimental results show that on warehouse-20-40-10-2-2 large map set,when the number of agents is 500,compared with Explicit Estimation Conflict-Based Search(EECBS)algorithm and Lazy Constraints Addition for MAPF(LaCAM)algorithm,HM-EECBS algorithm has the solution time reduced by about 88%and 73%respectively;when there is 5%,10%area congestion in warehouse,the success rate of HM-EECBS algorithm is increased by about 49%and 20%respectively,which illustrates that the proposed algorithm is suitable for solving MAPF problems in large-scale and congested warehousing and logistics environments.

关 键 词：仓储 拥堵 热力图 多智能体路径规划 显式估计冲突搜索算法 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]