Multi-AGV Path Planning for Indoor Factory by Using Prioritized Planning and Improved Ant Algorithm
DOI:
https://doi.org/10.5614/j.eng.technol.sci.2018.50.4.6Keywords:
ant algorithm, collision avoidance, decentralized algorithm, path planning.Abstract
Multiple automated guided vehicle (multi-AGV) path planning in manufacturing workshops has always been technically difficult for industrial applications. This paper presents a multi-AGV path planning method based on prioritized planning and improved ant colony algorithms. Firstly, in dealing with the problem of path coordination between AGVs, an improved priority algorithm is introduced, where priority is assigned based on the remaining battery charge of the AGVs, which improves the power usage efficiency of the AGVs. Secondly, an improved ant colony algorithm (IAC) is proposed to calculate the optimal path for the AGVs. In the algorithm, a random amount of pheromone is distributed in the map and the amount of pheromone is updated according to a fitness value. As a result, the computational efficiency of the ant colony algorithm is improved. Moreover, a mutation operation is introduced to mutate the amount of pheromone in randomly selected locations of the map, by which the problem of local optimum is well overcome. Simulation results and a comparative analysis showed the validity of the proposed method.Downloads
References
Draganjac, I., MikliA, D., KovaA iA, Z., VasiljeviA, G. & Bogdan, S., Decentralized Control of Multi-AGV Systems in Autonomous Warehousing Applications, IEEE Transactions on Automation Science & Engineering, 13(4), pp. 1433-1447, 2016.
Pan, X.Y., Wu, J., Zhang, Q.W., Lai, D., Xie, H.L. & Zhang C, A Case Study of AGV Scheduling for Production Material Handling, Applied Mechanics and Materials, 411, pp. 2351-2354, 2013.
Wang, F. & Zhu, Z., Global Path Planning of Wheeled Robots Using a Multi-Objective Memetic Algorithm, Integrated Computer Aided Engineering, 22(4), pp. 387-404, 2015.
Li, B., Liu, H., Xiao, D. & Zhang, Y., Centralized and Optimal Motion Planning for Large-scale AGV Systems: A Generic Approach, Advances in Engineering Software, 106(C), pp. 33-46, 2017.
Peasgood, M., Clark, C. & McPhee, J., A Complete and Scalable Strategy for Coordinating Multiple Robots within Roadmaps, IEEE Transactions on Robotics, 24(2), pp. 282-292, 2008.
Clark, C., Probabilistic Road Map Sampling Strategies for Multi-robot Motion Planning, Robotics and Autonomous Systems, 53(3), pp. 244-264, 2005.
Wang, K.H.C. & Botea, A., Tractable Multi-Agent Path Planning on Grid Maps, International Joint Conference on Artificial Intelligence IJCAI-09, Pasadena, CA, USA, 2009, pp. 1870-1875.
Ma, X., Jiao, Z., Wang, Z. & Panagou, D., Decentralized Prioritized Motion Planning for Multiple Autonomous UAVs in 3D Polygonal Obstacle Environments, International Conference on Unmanned Aircraft Systems (ICUAS), Arlington, VA USA, 2016, pp. 292-300.
Erdmann, M. & Lozano-Prez, T., On Multiple Moving Objects, Algorithmica, 2, pp. 1419-1424, 1987.
Dewangan, R.K., Shukla, A. & Godfrey, W.W., Survey on Prioritized Multi Robot Path Planning, 2017 IEEE International Conference on Smart Technologies and Management for Computing, Communication, Controls, Energy and Materials (ICSTM), Chennai, pp. 423-428, 2017.
A?ap, M., Novak, P., Kleiner, A. & Seleck1/2, M., Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots, IEEE Transactions on Automation Science & Engineering, 12(3), pp. 835-849, 2015.
Oliveira, M.M., Galdames, J.P.M., Vivaldini, K.T., Magalhes, D.V. & Becker, M., Battery State Estimation for Applications in Intelligent warehouses, IEEE Conference on Robotics and Automation, pp. 5511-5516, 2011.
Anton, S.R. & Inman, D.J., Vibration Energy Harvesting for Unmanned Aerial Vehicles, Proc Spie, p. 6982, 2008.
Aminzahed, I., Zhang, Y. & Jabbari, M., Energy Harvesting from a Five-story Building and Investigation of Frequency Effect on Output Power, International Journal on Interactive Design & Manufacturing, 10(3), pp. 1-8, 2016.
Mousavi, M. Yap, H.J Musa, S.N., Tahriri, F. & Md Dawal, S.Z., Multi-Objective AGV Scheduling in an FMS Using a Hybrid of Genetic Algorithm and Particle Swarm Optimization, Plos One, 12(3), e0169817, 2017.
Pandey, A., Mobile Robot Navigation and Obstacle Avoidance Techniques: A Review, International Journal of Robotics & Automation, 2(3), pp. 1-12, 2017.
Faraji, H., Hajimirzaalian, H., Farzadpour, F. & Legha, M.M., A New Hybrid Particle Swarm Optimization Approach for Sizing and Placement Enhancement of Distributed Generation. Energy and Electrical Drives (POWERENG), 2013 Fourth International Conference on (pp. 1277-1281). IEEE.
Dorigo, M., Di, C.G. & Gambardella, L.M., Ant Algorithms for Discrete Optimization, Artificial Life, 5(2), pp. 137, 1999.
A?ap, M., Algorithms for Multi-Robot Trajectory Planning in Well-formed Infrastructures, Association for the Advancement of Artificial Intelligence, pp. 1-5, 2015.
Van Den Berg, J.P. & Overmars, M.H., Prioritized Motion Planning for Multiple Robots, IEEE/RSJ International Conference on Intelligent Robots and Systems IEEE, pp. 374-382, 2005.
Cap, M., Novak, P., Seleck1/2, M., Faigl, J. & Vokffnek, J., Asynchronous Decentralized Prioritized Planning for Coordination in Multi-robot System, IEEE/RSJ International Conference on Intelligent Robots and Systems IEEE, pp. 3822-3829, 2013.
Liu, G., Li, T., Peng, Y. & Hou, X., The Ant Algorithm for Solving Robot Path Planning Problem, International Conference on Information Technology and Applications, IEEE Computer Society, pp. 25-27, 2005.
Rashid, R., Perumal, N., Elamvazuthi, I., Tageldeen, M.K., Ahamed Khan, M.K.A. & Parasuraman, S., Mobile Robot Path Planning Using Ant Colony Optimization, IEEE International Symposium on Robotics and Manufacturing Automation, IEEE, pp. 1-6, 2017.
Dorigo, M. & Gambardella, L.M., Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, 1(1), pp. 53-66, 1997.
Stutzle, T. & Hoos, H.H., MAX-MIN Ant System, Future Generation Computer Systems, The International Journal of Escience, 16(8), pp. 889-914, 2000.
Elfes, A., Using Occupancy Grids for Mobile Robot Perception and Navigation, Computer, 22(6), pp. 46-57, 2002.
Huang, C., Fei, J., Liu, Y. & Liu, X., Smooth Path Planning Method Based on Dynamic Feedback A Ant Colony Algorithm, Transactions of the Chinese Society for Agricultural Machinery, 48(4), pp. 34-40, 2017.
