Conflict-based search algorithm for large-scale warehousing environment

doi:10.11772/j.issn.1001-9081.2023121858

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (12): 3854-3860.DOI: 10.11772/j.issn.1001-9081.2023121858

• Advanced computing • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP242

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.

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

Figures/Tables 11

References 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.

地图集	算法	不同智能体数的求解时间
地图集	算法	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

地图集	算法	不同智能体数的求解时间
地图集	算法	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

算法名称	地图集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

算法名称	地图集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

算法名称	地图集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

Conflict-based search algorithm for large-scale warehousing environment

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 20

Related Articles 15

Recommended Articles

Metrics

[1]	Houming FAN, Shuang MU, Lijun YUE. Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion [J]. Journal of Computer Applications, 2022, 42(7): 2281-2291.
[2]	Hanguang LAI, Qing LI, Yong JIANG. Transmission control protocol congestion control switching scheme based on scenario change [J]. Journal of Computer Applications, 2022, 42(4): 1225-1234.
[3]	ZHAO Zhixue, LI Xiamiao, ZHOU Xiancheng. Green vehicle routing problem optimization for multi-type vehicles considering traffic congestion areas [J]. Journal of Computer Applications, 2020, 40(3): 883-890.
[4]	FAN Jiajia, LIU Hongxing, LI Yonghua, YANG Lijin. Collaborative routing method for operation vehicle in inland port based on game theory [J]. Journal of Computer Applications, 2020, 40(1): 50-55.
[5]	TAN Jing, DONG Chengfeng, WANG Huiqiang, WANG Hezhe, FENG Guangsheng, LYU Hongwu, YUAN Quan, CHEN Shijun. ERC²: DTN Epidemic Routing method with Congestion Control strategy [J]. Journal of Computer Applications, 2019, 39(1): 26-32.
[6]	ZHANG Jiachen, CHEN Qingkui. Road vehicle congestion analysis model based on YOLO [J]. Journal of Computer Applications, 2019, 39(1): 93-97.
[7]	ZUO Yuxing, GUO Aihuang, HUANG Bo, WANG Lu. Power control algorithm based on network utility maximization in Internet of vehicles [J]. Journal of Computer Applications, 2017, 37(12): 3345-3350.
[8]	WANG Renqun, PENG Li. Topology-aware congestion control algorithm in data center network [J]. Journal of Computer Applications, 2016, 36(9): 2357-2361.
[9]	YANG Huihua, WANG Ke, LI Lingqiao, WEI Wen, HE Shengtao. K-means clustering algorithm based on adaptive cuckoo search and its application [J]. Journal of Computer Applications, 2016, 36(8): 2066-2070.
[10]	SUN Sanshan, WANG Shuai, FAN Zifu. Flow scheduling cost based congestion control routing algorithm for data center network on software defined network architecture [J]. Journal of Computer Applications, 2016, 36(7): 1784-1788.
[11]	GAN Fenghao, NIU Yugang, JIA Tinggang. Congestion control algorithm in wireless sensor network based on fuzzy compress sensing [J]. Journal of Computer Applications, 2015, 35(9): 2430-2435.
[12]	LUO Long, YU Hongfang, LUO Shouxi. Congestion avoidance and fast traffic migration based on multi-topology routing [J]. Journal of Computer Applications, 2015, 35(7): 1809-1814.
[13]	DANG Xiaochao, YANG Dongdong, HAO Zhanjun. Three-dimensional coverage algorithm based on virtual force in sensor network [J]. Journal of Computer Applications, 2015, 35(11): 3021-3025.
[14]	SHEN Jian XIA Jingbo FU Kai SUN Yu. Active congestion control strategy based on historical probability in delay tolerant networks [J]. Journal of Computer Applications, 2014, 34(3): 644-648.
[15]	ZHAO Pan WEI Zhengxi ZHANG Hong. Calculation method and performance evaluation for network survivability [J]. Journal of Computer Applications, 2013, 33(10): 2742-2745.