Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
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
Journal of Computer Applications    2024, 44 (12): 3854-3860.   DOI: 10.11772/j.issn.1001-9081.2023121858
Abstract114)   HTML2)    PDF (2950KB)(40)       Save

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.

Table and Figures | Reference | Related Articles | Metrics