Path Planning in Multi-AGVs Using a Modified A-star Algorithm

Xing  Xu; Munashe Zhoya

doi:10.31686/ijier.vol8.iss5.2342

Authors

Xing Xu

Zhejiang University of Science and Technology, Hangzhou 310023，Zhejiang，China
Munashe Zhoya

Zhejiang Provincial Key Lab for Chem. & Bio. Processing Technology of Farm Product, Hangzhou 310023

DOI:

https://doi.org/10.31686/ijier.vol8.iss5.2342

Keywords:

AGV, A-star algorithm, collision free, path planning, efficiency, throughput

Abstract

The problem of path planning is a hot and exclusive research topic on multiple Automatic Guided Vehicles (multi-AGVs) systems. Many research results have been reported, but outrightly solving path planning problem from the perspective of reducing traffic congestion have faced obstacles. A collision-free path planning procedure based on a modified A-star Algorithm for multi-AGVs logistics sorting system is proposed in this paper. AGVs are now a poplar way to handle materials in latest smart warehouses. Many researches have been conducted and new technologies are still being developed. There is wide scale research on algorithms to help in scheduling, routing and path planning. Multi-AGVs are used to load goods automatically in a packaging factory. To ensure an effective and safe collision free path planning, this work investigates movement, scheduling and routing, speed manipulation and efficiency of machinery to target positions. The A-star algorithm with grid method to map out a typical warehouse scenario into multiple nodes was used. To have the shortest possible path, for obstacle avoidance, we employed the Braitenberg model. The waiting strategy is used for conflict resolution at intersections.

Author Biography

Xing Xu, Zhejiang University of Science and Technology, Hangzhou 310023，Zhejiang，China

School of Mechanical and Energy Engineering

References

Atere, A. and Lehtinen, J. (2013) A Multiresolution A* Method for Robot Path Planning.

Applications of Artificial Intelligence in Engineering XII, 19, 132-137.

Braitenberg, V. (1984). Vehicles: Experiments in synthetic psychology. Cambridge, MA: MIT Press.

Ebben, M.J.R. (2001). Logistic Control in Automated Transportation Networks. Doctoral Thesis. Published by University of Twente, Enschede Gademan, A.J.R.M. van de Velde, S.L. (2000). Positioning automated guided vehicles in a loop layout. European Journal of Operational Research, 127, pp. 565-573. 7. DOI: https://doi.org/10.1016/S0377-2217(99)00341-0

Egbelu, P. J, & Tanchoco, J. M. A. (1984). Characterization of Automatic Guided Vehicle; Dispatching Rules in facilities with Existing Layouts, International Journal of Production Research, 22, 3, pp. 359-374. DOI: https://doi.org/10.1080/00207548408942459

Egemin. Automation. (2013). Automated Guided Vehicle Safety. Retrieved from http://www.egeminusa.com/pages/agv_education/education_safety.html, visited 04-12-2019.

Gawrilow, E., Köhler, E., Möhring, R. H., & Stenzel, B. (2008). Dynamic routing of automated guided vehicles in real-time. In Mathematics– Key Technology for the Future, pp. 165-177, Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-540-77203-3_12

Gochev, I., Nadzinski, G., Prof. DSc Mile Stankovski, (2017) Path Planning and Collision Avoidance Regime for a Multi-Agent System in Industrial Robotics. Faculty of Electrical Engineering and Information Technology – University of Ss Cyril and Methodius, Republic of Macedonia, Skopje.

Guruji, A.K., Agarwal, H. and Parsediya, D.K. (2016) Time-Efficient A* Algorithm for Robot Path Planning. Procedia Technology, 23, 144-149. DOI: https://doi.org/10.1016/j.protcy.2016.03.010

Han, Z., Wang, D., Liu, F., Zhao, Z. (2017). Multi-AGV path planning with double-path constraints by using an improved genetic algorithm, Plos One, 12(7), e0181747. DOI: https://doi.org/10.1371/journal.pone.0181747

Henesey, L., Davidsson, P., & Persson, J. A. (2009). Evaluation of automated guided vehicle systems for container terminals using multi agent based simulation. In Multi-Agent-Based Simulation IX, pp. 85-96, Springer Berlin Heidelberg DOI: https://doi.org/10.1007/978-3-642-01991-3_7

Huls, C., Piggott, J., Windhouwer, D., Aksit, Prof. Dr. Ir. M. (2014), An Architecture for a Factory Automation System Master course: Design of Software Architecture, University of Twente, pp. 1-63.

Koo, P.H., and Jang, J.J. (2002). Vehicle Travelling Models for AGV Systems under Various Dispatching Rules. The International Journal of Flexible Manufacturing Systems, 14, pp. 249-261. DOI: https://doi.org/10.1023/A:1015831711304

Luo, L., Wen, H., Lu, Q., Huang, H., Chen, H., Zou, X., and Wang, C. (2018) Research on the Collision-Free Path-Planning for Six-DOF Serial Harvesting Robot Based on Energy Optimal and Artificial Potential Field. DOI: https://doi.org/10.1155/2018/3563846

Nishi, T., Ando, M. and Konishi, M. (2006). Experimental Studies on a Local Rescheduling

Procedure for Dynamic Routing Autonomous Decentralized AGV Systems. Robotics and

Computer Integrate Manufacturing, 22, 154-65.

Olmi, R. (2011). Traffic Management of Automated Guided Vehicles in Flexible Manufacturing Systems. Doctoral Thesis, Università degli Studi di Ferrara.

Santos, J., Costa, P., Rocha, L., Vivaldini, K., Moreira, A. P., & Veiga, G. (2016). Validation of a Time Based Routing Algorithm Using a Realistic Automatic Warehouse Scenario. Robot 2015: Second Iberian Robotics Conference. DOI: https://doi.org/10.1007/978-3-319-27149-1_7

Smolic-Rocak, N., Bogdan, S., Kovacic, Z., Petrovic, T. (2010). Time windows based dynamic routing in Multi-AGVsystems. IEEE Transactions on Automation Science and Engineering. 7(1): pp. 151–155. DOI: https://doi.org/10.1109/TASE.2009.2016350

Suárez, J.I., B. M. Vinagre, F. Gutierrez, J. E. Naranjo, & Y. Q. Chen. (2004). Dynamic models of an AGV based on experimental results. IFAC Proceedings Volumes, 37(8). DOI: https://doi.org/10.1016/S1474-6670(17)31987-0

Vivaldini, K., Rocha, L.F., Martarelli, N.J., Becker, M., Moreira A.P. (2016) Integrated tasks assignment and routing for the estimation of the optimal number of AGVs. The International Journal of Advanced Manufacturing Technology. 82(1): pp. 719–736. DOI: https://doi.org/10.1007/s00170-015-7343-4

Weyns, D., Shelfhout, K., & Holvoet, T. (2005). Architecture-centric development of an AGV transportation system, Lecture notes in Computer Science, volume 3690, pp. 640-644. DOI: https://doi.org/10.1007/11559221_80

Weyns, D., Shelfhout, K., Holvoet, T., & Lefever, T. (2005). Decentralized control of EGV transportation system, Proceedings of the forth international joint conference on autonomous agents and multiagents system. DOI: https://doi.org/10.1145/1082473.1082806

Weyns D., & Holvoet T. (2008). Architectural design of a situated multiagent system for controlling automatic guided vehicles, Int. J. Agent-Oriented Software Engineering, Vol.2, No. 1. DOI: https://doi.org/10.1504/IJAOSE.2008.016801

Xia, G.M., Zeng, J.C. (2007). A stochastic particle swarm optimization algorithm based on the genetic algorithm of roulette wheel selection, Computer Engineering and Science. 29(6), pp. 6–11.

Yang, X., and Wushan, C. (2016). AGV Path Planning Based On Smoothing A* Algorithm, College Of Mechanical Engineering, Shnghai University Of Enineering Science, China

Yuan, R.P., Dong, T.T and Li, J.T. (2016) Research on the Collision-Free Path Planning of Multi-AGVs System Based on A* Algorithm. American Journal of Operations Research, 6, 442-449. DOI: https://doi.org/10.4236/ajor.2016.66041