Lattice-Hopping: A Novel Map-Representation-Based Path Planning Algorithm for a High-Density Storage System
Source abstract
Abstract
Optimal path planning algorithms offer substantial benefits in high-density storage (HDS) systems in modern smart manufacturing. However, traditional algorithms may encounter significant optimization challenges due to intricate architectural configurations and traffic constraints of the HDS system. This paper addresses these issues by introducing a two-step novel path planning method: (1) the mesh-tree grid map topological representation and the (2) Lattice-Hopping (LH) algorithm. The proposed method first converts the layout of an HDS system into a mesh-tree grid hierarchical structure by capturing and simplifying the spatial and geometrical information as well as the traffic constraints of the HDS system. Then, the LH algorithm is proposed to find optimal shipping path by leveraging the global connectivity of main tracks (main track priority) and the ‘jumping’ mechanism of sub-tracks. The main track priority and the ‘jumping’ mechanism work together to save computational complexity and enhance the feasibility and optimality of the proposed method. Numerical and case studies are performed to demonstrate the superiorities of our method to properly modified benchmark algorithms. Algorithm scalability, robustness, and operational feasibility for industrial production in modern smart manufacturing are also displayed and emphasized.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · Power Line Inspection Robots · Smart Parking Systems Research
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
The College of Information, Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai 201418, China
Department of Mechanical Engineering, The University of Hong Kong, Hong Kong 999077, China
Nanjing Huade Storage Equipment Manufacturing Co., Ltd., Nanjing 211122, China
Funding
Shanghai Normal University
References (41)
Show source-provided references
1. Artificial intelligence application in smart warehousing environment for automated logistics
2. Yuan, Y., Song, D., and Huang, Y. (2021, January 27–29). The Limitations of Traditional Retail Enterprises’ Self-built Logistics System—A Case Study of Walmart. Proceedings of the 2021 International Conference on Financial Management and Economic Transition (FMET 2021), Online.10.2991/aebmr.k.210917.074 ↗
3. Carli, R., Dotoli, M., Digiesi, S., Facchini, F., and Mossa, G. (2020). Sustainable scheduling of material handling activities in labor-intensive warehouses: A decision and control model. Sustainability, 12.10.3390/su12083111 ↗
4. Tutam, M. (2022). Warehousing 4.0 in Logistics 4.0. Logistics 4.0 and Future of Supply Chains, Springer.10.1007/978-981-16-5644-6_7 ↗
5. Mao, J., Cheng, J., Li, X., and Cao, B. (2023). Research on scheduling optimization of four-way shuttle-based storage and retrieval systems. Sci. Rep., 13.10.1038/s41598-023-31050-8 ↗
6. Zheng, Z., Ma, Y., Liu, Y., Yang, F., Li, Z., Zhang, Y., Zhang, J., Shi, W., Chen, W., and Li, D. (2021, January 23–27). Xlink: Qoe-driven multi-path quic transport in large-scale video services. Proceedings of the 2021 ACM SIGCOMM 2021 Conference, Virtual.10.1145/3452296.3472893 ↗
7. Li, Z., Wegner, J.D., and Lucchi, A. (November, January 27). Topological map extraction from overhead images. Proceedings of the IEEE/CVF International Conference on Computer Vision, Seoul, Republic of Korea.
8. Distributed consensus on robot networks for dynamically merging feature-based maps10.1109/TRO.2012.2192012 ↗
9. Map symbols for crisis mapping: Challenges and prospects10.1080/00087041.2017.1413810 ↗
10. Thakur, A., Anand, B., Verma, H., and Rajalakshmi, P. (2022, January 18–20). Real time lidar odometry and mapping and creation of vector map. Proceedings of the 2022 8th International Conference on Automation, Robotics and Applications (ICARA), Prague, Czech Republic.10.1109/ICARA55094.2022.9738576 ↗
11. On scatteredly continuous maps between topological spaces10.1016/j.topol.2009.04.043 ↗
12. WHU-helmet: A helmet-based multisensor SLAM dataset for the evaluation of real-time 3-D mapping in large-scale GNSS-denied environments
13. Sharifzadeh, S., Baharlou, S.M., Berrendorf, M., Koner, R., and Tresp, V. (2021, January 10–15). Improving visual relation detection using depth maps. Proceedings of the 2020 25th International Conference on Pattern Recognition (ICPR), Milan, Italy.10.1109/ICPR48806.2021.9412945 ↗
14. A survey on active simultaneous localization and mapping: State of the art and new frontiers10.1109/TRO.2023.3248510 ↗
15. Deadlock prevention and multi agent path finding algorithm considering physical constraint for a massive fleet AGV system10.1016/j.asoc.2024.111725 ↗
16. Li, Q., Xie, F., Zhao, J., Xu, B., Yang, J., Liu, X., and Suo, H. (2022). FPS: Fast path planner algorithm based on sparse visibility graph and bidirectional breadth-first search. Remote Sens., 14.10.3390/rs14153720 ↗
17. Dijkstra graphs10.1016/j.dam.2017.07.033 ↗
18. Pándy, M., Qiu, W., Corso, G., Veličković, P., Ying, Z., Leskovec, J., and Lio, P. (2022, January 9–12). Learning graph search heuristics. Proceedings of the Learning on Graphs Conference, PMLR, Virtual.
19. Geometric A-star algorithm: An improved A-star algorithm for AGV path planning in a port environment10.1109/ACCESS.2021.3070054 ↗
20. Development of pathfinding using a-star and d-star lite algorithms in video game
21. Recent advances in Rapidly-exploring random tree: A review10.1016/j.heliyon.2024.e32451 ↗
22. Comparison of optimization techniques based on gradient descent algorithm: A review
23. Optimization of energy consumption in industrial robots, a review10.1016/j.cogr.2023.05.003 ↗
24. Lei, T., Chintam, P., Luo, C., Liu, L., and Jan, G.E. (2023). A convex optimization approach to multi-robot task allocation and path planning. Sensors, 23.10.3390/s23115103 ↗
25. A review on genetic algorithm: Past, present, and future10.1007/s11042-020-10139-6 ↗
26. Particle swarm optimization algorithm and its applications: A systematic review10.1007/s11831-021-09694-4 ↗
27. Ant Colony Optimization: Overview and Recent Advances
28. Bae, H., Kim, G., Kim, J., Qian, D., and Lee, S. (2019). Multi-robot path planning method using reinforcement learning. Appl. Sci., 9.10.3390/app9153057 ↗
29. Xin, J., Zhao, H., Liu, D., and Li, M. (2017, January 20–22). Application of deep reinforcement learning in mobile robot path planning. Proceedings of the 2017 Chinese Automation Congress (CAC), Jinan, China.10.1109/CAC.2017.8244061 ↗
30. Moctezuma, L.E.G. (2023). Dynamic Multivariable Optimization for Routing in High-Density Manufacturing Transportation Systems. [Master’s Thesis, Tampere University].
31. Fu, X., Zhang, B., and Yu, H. (2015, January 27–29). Vehicles routing and scheduling algorithm for an automated storage and retrieval system of a warehouse. Proceedings of the 2015 International Conference on Logistics, Informatics and Service Sciences (LISS), Barcelona, Spain.
32. Chen, S., Wang, M., and Song, W. (2024). Hierarchical learning with heuristic guidance for multi-task assignment and distributed planning in interactive scenarios. IEEE Trans. Intell. Veh.10.1109/TIV.2024.3369730 ↗
33. Design and control of warehouse order picking: A literature review10.1016/j.ejor.2006.07.009 ↗
34. Warehousing in the e-commerce era: A survey10.1016/j.ejor.2018.08.023 ↗
35. Robotized and automated warehouse systems: Review and recent developments10.1287/trsc.2018.0873 ↗
36. Efficient safe control via deep reinforcement learning and supervisory control–case study on multi-robot warehouse automation10.1016/j.ifacol.2022.10.318 ↗
37. Jiang, Z., Zhang, X., and Wang, P. (2023). Grid-map-based path planning and task assignment for multi-type AGVs in a distribution warehouse. Mathematics, 11.10.3390/math11132802 ↗
38. Xu, X., Wang, C., Wang, Y., and Xiong, R. (2021). Hitmap: A hierarchical topological map representation for navigation in unknown environments. arXiv.
39. Hou, J., Yuan, Y., and Schwertfeger, S. (2019, January 2–6). Area graph: Generation of topological maps using the voronoi diagram. Proceedings of the 2019 19th International Conference on Advanced Robotics (ICAR), Belo Horizonte, Brazil.10.1109/ICAR46387.2019.8981588 ↗
40. Safety of mobile robot systems in industrial applications
41. Xiang, D., Lin, H., Ouyang, J., and Huang, D. (2022). Combined improved A* and greedy algorithm for path planning of multi-objective mobile robot. Sci. Rep., 12.10.1038/s41598-022-17684-0 ↗