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

doi:10.11772/j.issn.1001-9081.2023121858

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (12): 3854-3860.DOI: 10.11772/j.issn.1001-9081.2023121858

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

邓辅秦¹^,²^,³, 谭朝恩¹, 黎俊炜¹, 钟家铭¹^,³, 付兰慧¹, 张建民¹, 王宏民¹, 李楠楠⁴, 姜炳春³, 林天麟²()

^1.五邑大学智能制造学部，广东江门 529020
^2.香港中文大学（深圳）深圳市人工智能与机器人研究院，广东深圳 518116
^3.广东科技学院机电工程学院，广东东莞 523083
^4.澳门科技大学创新工程学院，澳门 999078

收稿日期:2024-01-16 修回日期:2024-05-28 接受日期:2024-06-03 发布日期:2024-07-04 出版日期:2024-12-10
通讯作者: 林天麟
作者简介:邓辅秦（1982—），男，湖南郴州人，高级工程师，博士，主要研究方向：机器学习、多机器人系统
谭朝恩（1999—），男，广东佛山人，硕士研究生，主要研究方向：多机器人路径规划
黎俊炜（1999—），男，广东江门人，硕士研究生，主要研究方向：机器视觉
钟家铭（1998—），男，广东韶关人，硕士研究生，主要研究方向：机器视觉
付兰慧（1987—），女，河南新乡人，讲师，博士，主要研究方向：机器学习、图像信息处理
张建民（1981—），男，河北沧州人，副教授，硕士，主要研究方向：机器学习、多机器人系统
王宏民（1978—），男，河北承德人，教授，博士，主要研究方向：仿生机器人、机器人运动控制
李楠楠（1982—），男，安徽阜阳人，助理教授，博士，主要研究方向：机器视觉
姜炳春（1987—），男，福建三明人，副教授，硕士，主要研究方向：塑性成形工艺及材料表面改性；
基金资助:
国家自然科学基金资助项目(62073274);深圳市人工智能与机器人研究院探索性研究项目(AC01202101103);五邑大学港澳联合基金资助项目(2022WGALH17)

Conflict-based search algorithm for large-scale warehousing environment

Fuqin DENG¹^,²^,³, Chaoen TAN¹, Junwei LI¹, Jiaming ZHONG¹^,³, Lanhui FU¹, Jianmin ZHANG¹, Hongmin WANG¹, Nannan LI⁴, Bingchun JIANG³, Tin Lun LAM²()

^1.School of Intelligent Manufacturing，Wuyi University，Jiangmen Guangdong 529020，China
^2.The Shenzhen Institute of Artificial Intelligence and Robotics for Society，The Chinese University of Hong Kong，Shenzhen，Shenzhen Guangdong 518116，China
^3.School of Mechanical and Electrical Engineering，Guangdong University of Science and Technology，Dongguan Guangdong 523083，China
^4.Faculty of Innovation Engineering，Macao University of Science and Technology，Macao 999078，China

Received:2024-01-16 Revised:2024-05-28 Accepted:2024-06-03 Online:2024-07-04 Published:2024-12-10
Contact: Tin Lun LAM
About author:DENG Fuqin， born in 1982， Ph. D.， senior engineer. His research interests include machine learning， multi-robot systems.
TAN Chaoen， born in 1999， M. S. candidate. His research interests include multi-robot path planning.
LI Junwei， born in 1999， M. S. candidate. His research interests include computer vision.
ZHONG Jiaming， born in 1998， M. S. candidate. His research interests include computer vision.
FU Lanhui， born in 1987， Ph. D.， lecturer. Her research interests include machine learning， image information processing.
ZHANG Jianmin， born in 1981， M. S.， associate professor. His research interests include machine learning， multi-robot systems.
WANG Hongmin， born in 1978， Ph. D.， professor. His research interests include bionic robots， robot motion control.
LI Nannan， born in 1982， Ph. D.， assistant professor. His research interests include computer vision.
JIANG Bingchun， born in 1987， M. S.， associate professor. His research interests include plastic forming process and material surface modification.
Supported by:
National Natural Science Foundation of China(62073274);Exploratory Research Project of Shenzhen Institute of Artificial Intelligence and Robotics for Society(AC01202101103);Wuyi University-Hong Kong-Macau Joint Fund(2022WGALH17)

摘要/Abstract

摘要：

针对多智能体在大型仓储环境中进行路径规划时，现有算法有智能体易陷入拥堵区域和耗时长的问题，提出一种改良的基于冲突搜索（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问题。

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

Abstract:

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.

Key words: warehousing, congestion, heat map, Multi-Agent Path Finding (MAPF), Explicit Estimation Conflict-Based Search (EECBS) algorithm

中图分类号:

TP242

邓辅秦, 谭朝恩, 黎俊炜, 钟家铭, 付兰慧, 张建民, 王宏民, 李楠楠, 姜炳春, 林天麟. 面向大型仓储环境的基于冲突搜索算法[J]. 计算机应用, 2024, 44(12): 3854-3860.

Fuqin DENG, Chaoen TAN, Junwei LI, Jiaming ZHONG, Lanhui FU, Jianmin ZHANG, Hongmin WANG, Nannan LI, Bingchun JIANG, Tin Lun LAM. Conflict-based search algorithm for large-scale warehousing environment[J]. Journal of Computer Applications, 2024, 44(12): 3854-3860.

图/表 11

图1 2种常见的冲突

Fig. 1 Two common conflicts

图2 HM-EECBS算法流程

Fig. 2 Flowchart of HM-EECBS algorithm

图3 栅格-热力图建模

Fig. 3 Grid-heat map modeling

图4 仓储环境示意图

Fig.4 Schematic diagram of warehousing environment

图5 HM-EECBS与EECBS算法的核心内容

Fig. 5 Core contents of HM-EECBS and EECBS algorithms

图6 HM-EECBS与EECBS算法规划路径差异示意图

Fig. 6 Schematic diagram of planned path difference between HM-EECBS and EECBS algorithms

表1 不同规模的地图集下不同算法的求解时间 (ms)

Tab.1 Solution time of different algorithms in different sized maps

地图集	算法	不同智能体数的求解时间
地图集	算法	50	250	500	750	1 000
地图集1	CBS	21 742	－	－	－	－
	D^* Lite	9 503	－	－	－	－
	EECBS	39	1 275	15 336	24 561	－
	LaCAM	32	1 147	4 853	11 495	16 017
	HM-EECBS	28	483	1 754	6 047	10 468
地图集2	CBS	27 700	－	－	－	－
	D^* Lite	17 451	－	－	－	－
	EECBS	70	1 682	18 854	－	－
	LaCAM	43	1 451	7 981	17 274	19 690
	HM-EECBS	37	790	2 191	9 227	15 639

表2 地图集1中不同算法的路径成本

Tab. 2 Path costs of different algorithms in map 1

算法名称	地图集1中不同智能体数的路径成本
算法名称	50	250	500	750	1 000
EECBS	8 118	43 957	100 947	175 942	－
LaCAM	13 481	68 171	165 841	241 495	396 786
HM-EECBS	8 752	46 412	113 082	190 114	271 741

图7 中等规模场景下不同算法的成功率对比

Fig.7 Success rates of different algorithms in medium-scale scenarios

表3 地图集2中各算法的路径成本

Tab. 3 Path costs of each algorithm in map 2

算法名称	地图集2中不同智能体数的路径成本
算法名称	50	250	500	750	1 000
EECBS	10 554	51 736	121 446	－	－
LaCAM	19 347	77 124	197 275	261 429	421 721
HM-EECBS	11 864	55 694	145 747	220 413	305 976

图8 大规模场景下不同算法的成功率对比

Fig.8 Success rates of different algorithms in large-scale scenarios

参考文献 20

1	刘思嘉，童向荣. 基于强化学习的城市交通路径规划［J］. 计算机应用，2021， 41（1）：185-190.
	LIU S J， TONG X R. Urban transportation path planning based on reinforcement learning ［J］. Journal of Computer Applications， 2021， 41（1）：185-190.
2	陈昇，周隽，胡小兵，等. 基于混合模拟退火算法的机场进场程序优化［J］. 计算机应用， 2022， 42（2）：606-615.
	CHEN S， ZHOU J， HU X B， et al. Optimization of airport arrival procedures based on hybrid simulated annealing algorithm［J］. Journal of Computer Applications， 2022， 42（2）： 606-615.
3	ZHEN L， LI H. A literature review of smart warehouse operations management［J］. Frontiers of Engineering Management， 2022， 9（1）： 31-55.
4	OU Y， FAN Y， ZHANG X， et al. Improved A^* path planning method based on the grid map［J］. Sensors， 2022， 22（16）： No.6198.
5	SHANG Z， SHEN Z. Topology-based UAV path planning for multi-view stereo 3D reconstruction of complex structures ［J］. Complex and Intelligent Systems， 2023， 9（1）： 909-926.
6	KLOETZER M， BELTA C. Automatic deployment of distributed teams of robots from temporal logic motion specifications ［J］. IEEE Transactions on Robotics， 2010， 26（1）： 48-61.
7	YU J， LaVALLE S M. Structure and intractability of optimal multi-robot path planning on graphs ［C］// Proceedings of the 27th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2013： 1443-1449.
8	SHARON G， STERN R， FELNER A， et al. Conflict-based search for optimal multi-agent pathfinding［J］. Artificial Intelligence， 2015， 219： 40-66.
9	HART P E， NILSSON N J， RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths［J］. IEEE Transactions on Systems Science and Cybernetics， 1968， 4（2）： 100-107.
10	LI J， RUML W， KOENIG S. EECBS： a bounded-suboptimal search for multi-agent path finding ［C］// Proceedings of the 35th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2021： 12353-12362.
11	THAYER J T， RUML W. Bounded suboptimal search： a direct approach using inadmissible estimates［C］// Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2011： 674-679.
12	OKUMURA K. LaCAM： search-based algorithm for quick multi-agent pathfinding ［C］// Proceedings of the 37th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2023： 11655-11662.
13	GU Z. Complex heatmap visualization ［J］. iMeta， 2022， 1（3）： No.e43.
14	STERN R， STURTEVANT N R， FELNER A， et al. Multi-agent pathfinding： definitions， variants， and benchmarks［C］// Proceedings of the 12th International Symposium on Combinatorial Search. Palo Alto： AAAI Press， 2019： 151-158.
15	WANG X， SAHIN A， BHATTACHARYA S. Coordination-free multi-robot path planning for congestion reduction using topological reasoning［J］. Journal of Intelligent and Robotic Systems， 2023， 108： No.50.
16	BARER M， SHARON G， STERN R， et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem［C］// Proceedings of the 7th Annual Symposium on Combinatorial Search. Palo Alto： AAAI Press， 2014： 19-27.
17	KOENIG S， LIKHACHEV M. D^* Lite ［C］// Proceedings of the 8th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2002： 476-483.
18	LIU Z， ZHOU S， WANG H， et al. A hierarchical framework for coordinating large-scale robot networks［C］// Proceedings of the 2019 International Conference on Robotics and Automation. Piscataway： IEEE， 2019： 6672-6677.
19	FU S， LI J， FU Z H. Cooperatively scheduling hundreds of fetch and freight robots in an autonomous warehouse ［C］// Proceedings of the 2022 IEEE International Conference on Real-time Computing and Robotics. Piscataway： IEEE， 2022： 469-474.
20	BATES P D， DE ROO A P J. A simple raster-based model for flood inundation simulation［J］. Journal of Hydrology， 2000， 236（1/2）： 54-77.

[1]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.
[2]	赵志学, 李夏苗, 周鲜成. 考虑拥堵区域的多车型绿色车辆路径问题优化[J]. 计算机应用, 2020, 40(3): 883-890.
[3]	范家佳, 刘洪星, 李勇华, 杨丽金. 基于博弈论的内河港口作业车辆协同选路方法[J]. 计算机应用, 2020, 40(1): 50-55.
[4]	张家晨, 陈庆奎. 基于YOLO的道路车辆拥堵分析模型[J]. 计算机应用, 2019, 39(1): 93-97.
[5]	薛鹏任鹏飞王划. 环状交通流Washout控制及其稳定性分析[J]. 计算机应用, 2014, 34(2): 597-600.

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

Conflict-based search algorithm for large-scale warehousing environment

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 20

相关文章 5

编辑推荐

Metrics