{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T00:14:13Z","timestamp":1768004053900,"version":"3.49.0"},"reference-count":47,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T00:00:00Z","timestamp":1621382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotics"],"abstract":"<jats:p>A multi-AGV based logistic system is typically associated with two fundamental problems, critical for its overall performance: the AGV\u2019s route planning for collision and deadlock avoidance; and the task scheduling to determine which vehicle should transport which load. Several heuristic functions can be used according to the application. This paper proposes a time-based algorithm to dynamically control a fleet of Autonomous Guided Vehicles (AGVs) in an automatic warehouse scenario. Our approach includes a routing algorithm based on the A* heuristic search (TEA*\u2014Time Enhanced A*) to generate free-collisions paths and a scheduling module to improve the results of the routing algorithm. These modules work cooperatively to provide an efficient task execution time considering as basis the routing algorithm information. Simulation experiments are presented using a typical industrial layout for 10 and 20 AGVs. Moreover, a comparison with an alternative approach from the state-of-the-art is also presented.<\/jats:p>","DOI":"10.3390\/robotics10020072","type":"journal-article","created":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T21:49:21Z","timestamp":1621460961000},"page":"72","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["A* Based Routing and Scheduling Modules for Multiple AGVs in an Industrial Scenario"],"prefix":"10.3390","volume":"10","author":[{"given":"Joana","family":"Santos","sequence":"first","affiliation":[{"name":"Faculty of Engineering, University of Porto (FEUP), 4200-465 Porto, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4133-3210","authenticated-orcid":false,"given":"Paulo M.","family":"Rebelo","sequence":"additional","affiliation":[{"name":"Institute for Systems and Computer Engineering, Technology and Science (INESC TEC), 4200-465 Porto, Portugal"}]},{"given":"Luis F.","family":"Rocha","sequence":"additional","affiliation":[{"name":"Institute for Systems and Computer Engineering, Technology and Science (INESC TEC), 4200-465 Porto, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0435-8419","authenticated-orcid":false,"given":"Pedro","family":"Costa","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, University of Porto (FEUP), 4200-465 Porto, Portugal"},{"name":"Institute for Systems and Computer Engineering, Technology and Science (INESC TEC), 4200-465 Porto, Portugal"}]},{"given":"Germano","family":"Veiga","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, University of Porto (FEUP), 4200-465 Porto, Portugal"},{"name":"Institute for Systems and Computer Engineering, Technology and Science (INESC TEC), 4200-465 Porto, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Kalinovcic, L., Petrovic, T., Bogdan, S., and Bobanac, V. (2011, January 20\u201321). Modified Banker\u2019s algorithm for scheduling in multi-AGV systems. Proceedings of the IEEE International Conference on Automation Science and Engineering, Hong Kong, China.","DOI":"10.1109\/CASE.2011.6042433"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Cirillo, M., Pecora, F., Andreasson, H., Uras, T., and Koenig, S. (2014, January 21\u201326). Integrated motion planning and coordination for industrial vehicles. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), Portsmouth, NH, USA.","DOI":"10.1609\/icaps.v24i1.13668"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1720","DOI":"10.1016\/j.asoc.2012.02.001","article-title":"A multi-agent based approach to dynamic scheduling of machines and automated guided vehicles in manufacturing systems","volume":"12","author":"Erol","year":"2012","journal-title":"Appl. Soft Comput. J."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1287\/trsc.1030.0056","article-title":"Vehicle routing problem with time windows, Part I: Route construction and local search algorithms","volume":"39","author":"Gendreau","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"M\u00f6hring, R.H., K\u00f6hler, E., Gawrilow, E., and Stenzel, B. (2005). Conflict-Free Real-Time AGV Routing, Springer.","DOI":"10.1007\/3-540-27679-3_3"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1109\/TASE.2009.2016350","article-title":"Time windows based dynamic routing in multi-AGV systems","volume":"7","author":"Bogdan","year":"2010","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Ballal, P., Giordano, V., and Lewis, F. (2006, January 28\u201330). Deadlock free dynamic resource assignment in multi-robot systems with multiple missions: A matrix-based approach. Proceedings of the 14th Mediterranean Conference on Control and Automation (MED\u201906), Ancona, Italy.","DOI":"10.1109\/MED.2006.328691"},{"key":"ref_8","first-page":"426","article-title":"A literature review of deadlock prevention policy based on petri nets for automated manufacturing systems","volume":"6","author":"Guan","year":"2012","journal-title":"Int. J. Digit. Content Technol. Its Appl."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Santos, J., Costa, P., Rocha, L.F., Moreira, A.P., and Veiga, G. (2015, January 17\u201319). Time enhanced A: Towards the development of a new approach for Multi-Robot Coordination. Proceedings of the IEEE International Conference on Industrial Technology, Seville, Spain.","DOI":"10.1109\/ICIT.2015.7125589"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Santos, J., Costa, P., Rocha, L., Vivaldini, K., Moreira, A.P., and Veiga, G. (2016, January 6\u201310). Validation of a time based routing algorithm using a realistic automatic warehouse scenario. Proceedings of the Advances in Intelligent Systems and Computing, Lviv, Ukraine.","DOI":"10.1007\/978-3-319-27149-1_7"},{"key":"ref_11","unstructured":"Olmi, R., Secchi, C., and Fantuzzi, C. (2010, January 8). Coordinating the motion of multiple AGVs in automatic warehouses. Proceedings of the Workshop on Robotics and Intelligent Transportation Systems, Anchorage, Alaska."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Liu, C., and Kroll, A. (2012). A centralized multi-robot task allocation for industrial plant inspection by using A* and genetic algorithms. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer.","DOI":"10.1007\/978-3-642-29350-4_56"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1564","DOI":"10.1016\/j.compeleceng.2012.06.016","article-title":"Dynamic path planning of mobile robots with improved genetic algorithm","volume":"38","author":"Tuncer","year":"2012","journal-title":"Comput. Electr. Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1007\/s10845-010-0404-5","article-title":"A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time","volume":"23","author":"Kapanoglu","year":"2012","journal-title":"J. Intell. Manuf."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.procs.2018.07.018","article-title":"Methodology for Path Planning and Optimization of Mobile Robots: A Review","volume":"133","author":"Zafar","year":"2018","journal-title":"Procedia Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"3817","DOI":"10.1016\/j.eswa.2011.09.090","article-title":"Multi-robot path planning using co-evolutionary genetic programming","volume":"39","author":"Kala","year":"2012","journal-title":"Expert Syst. Appl."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s10514-010-9202-3","article-title":"Time-extended multi-robot coordination for domains with intra-path constraints","volume":"30","author":"Jones","year":"2011","journal-title":"Auton. Robot."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1002\/tee.21868","article-title":"Intelligent combinatorial auctions of decentralized task assignment for AGV with multiple loading capacity","volume":"8","author":"Fauadi","year":"2013","journal-title":"IEEJ Trans. Electr. Electron. Eng."},{"key":"ref_19","unstructured":"Sun, D., Kleiner, A., and Nebel, B. (June, January 31). Behavior-based multi-robot collision avoidance. Proceedings of the IEEE International Conference on Robotics and Automation, Hong Kong, China."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.neucom.2012.09.019","article-title":"Robot path planning in uncertain environment using multi-objective particle swarm optimization","volume":"103","author":"Zhang","year":"2013","journal-title":"Neurocomputing"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.swevo.2015.09.004","article-title":"Unknown environment exploration of multi-robot system with the FORDPSO","volume":"26","author":"Wang","year":"2016","journal-title":"Swarm Evol. Comput."},{"key":"ref_22","unstructured":"Simmons, R., Apfelbaum, D., Burgard, W., and Fox, D. (2000, January 1\u20133). Coordination for multi-robot exploration and mapping. Proceedings of the Aaai\/Iaai, Austin, TX, USA."},{"key":"ref_23","unstructured":"Berhault, M., Huang, H., Keskinocak, P., Koenig, S., Elmaghraby, W., Griffin, P., and Kleywegt, A. (November, January 27). Robot Exploration with Combinatorial Auctions. Proceedings of the IEEE International Conference on Intelligent Robots and Systems, Las Vegas, NV, USA."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1177\/0278364913487931","article-title":"Optimality and robustness in multi-robot path planning with temporal logic constraints","volume":"32","author":"Ulusoy","year":"2013","journal-title":"Int. J. Robot. Res."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Yu, J., and Lavalle, S.M. (2013, January 6\u201310). Planning optimal paths for multiple robots on graphs. Proceedings of the IEEE International Conference on Robotics and Automation, Karlsruhe, Germany.","DOI":"10.1109\/ICRA.2013.6631084"},{"key":"ref_26","unstructured":"Chaimowicz, L., Sugar, T., Kumar, V., and Campos, M.F. (2001, January 21\u201326). An architecture for tightly coupled multi-robot cooperation. Proceedings of the IEEE International Conference on Robotics and Automation, Seoul, Korea."},{"key":"ref_27","unstructured":"Guo, Y., and Parker, L.E. (2002, January 11\u201315). A distributed and optimal motion planning approach for multiple mobile robots. Proceedings of the IEEE International Conference on Robotics and Automation, Washington, DC, USA."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.robot.2016.02.003","article-title":"Task allocation and collision-free path planning of centralized multi-robots system for industrial plant inspection using heuristic methods","volume":"80","author":"Jose","year":"2016","journal-title":"Robot. Auton. Syst."},{"key":"ref_29","unstructured":"Zhang, X., Yan, M., and Ju, Y. (2012, January 12\u201314). A tabu search based flocking algorithm of motion control for multiple mobile robots. Proceedings of the 2012 5th International Conference on Intelligent Computation Technology and Automation (ICICTA 2012), Zhangjiajie, China."},{"key":"ref_30","unstructured":"Fierro, R., Das, A.K., Kumar, V., and Ostrowski, J.P. (2001, January 21\u201326). Hybrid control of formations of robots. Proceedings of the IEEE International Conference on Robotics and Automation, Seoul, Korea."},{"key":"ref_31","unstructured":"Stentz, A. (1994, January 8\u201313). Optimal and efficient path planning for partially-known environments. Proceedings of the IEEE International Conference on Robotics and Automation, San Diego, CA, USA."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1007\/s00170-015-7343-4","article-title":"Integrated tasks assignment and routing for the estimation of the optimal number of AGVS","volume":"82","author":"Vivaldini","year":"2016","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_33","unstructured":"Nilsson, N.J. (2014). Principles of Artificial Intelligence, Morgan Kaufmann."},{"key":"ref_34","unstructured":"Mitchell, R., Michalski, J., and Carbonell, T. (2013). An Artificial Intelligence Approach, Springer."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Atzmon, D., Stern, R., Felner, A., Wagner, G., Bart\u00e1k, R., and Zhou, N.F. (2020). Robust multi-agent path finding and executing. J. Artif. Intell. Res.","DOI":"10.1613\/jair.1.11734"},{"key":"ref_36","unstructured":"Li, J., Sun, K., Ma, H., Felner, A., Satish Kumar, T.K., and Koenig, S. (2020, January 9\u201313). Moving agents in formation in congested environments. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), Auckland, New Zealand."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Atzmon, D., Stern, R., Felner, A., Sturtevant, N.R., and Koenig, S. (2020, January 14\u201319). Probabilistic robust multi-agent path finding. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), Nancy, France.","DOI":"10.1609\/icaps.v30i1.6642"},{"key":"ref_38","unstructured":"Liu, M., Ma, H., Li, J., and Koenig, S. (2019, January 13\u201317). Task and path planning for multi-agent pickup and delivery. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), Montreal, QC, Canada."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Surynek, P. (2009, January 12\u201317). A novel approach to path planning for multiple robots in bi-connected graphs. Proceedings of the IEEE International Conference on Robotics and Automation, Kobe, Japan.","DOI":"10.1109\/ROBOT.2009.5152326"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Wagner, G., Kang, M., and Choset, H. (2012, January 14\u201318). Probabilistic path planning for multiple robots with subdimensional expansion. Proceedings of the IEEE International Conference on Robotics and Automation, Saint Paul, MN, USA.","DOI":"10.1109\/ICRA.2012.6225297"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Bart\u00e1k, R., \u0160vancara, J., \u0160kopkov\u00e1, V., and Nohejl, D. (2018). Multi-agent path finding on real robots: First experience with ozobots. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer.","DOI":"10.1007\/978-3-030-03928-8_24"},{"key":"ref_42","unstructured":"Li, D., Ouyang, B., Wu, D., and Wang, Y. (2019). Artificial intelligence empowered multi-AGVs in manufacturing systems. arXiv."},{"key":"ref_43","unstructured":"Sasi Kumar, G., Shravan, B., Gole, H., Barve, P., and Ravikumar, L. (2011). Path Planning Algorithms: A Comparative Study."},{"key":"ref_44","unstructured":"Moreira, A.P., Costa, P.J., and Costa, P. (2009, January 7). Real-time path planning using a modified A* algorithm. Proceedings of the 9th Conference on Mobile Robots and Competitions, Castelo Branco, Portugal."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Petrinec, K., and Kova\u010di\u0107, Z. (2005, January 20\u201323). The application of spline functions and b\u00e9zier curves to AGV path planning. Proceedings of the IEEE International Symposium on Industrial Electronics, Dubrovnik, Croatia.","DOI":"10.1109\/ISIE.2005.1529146"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Secchi, C., Olmi, R., Fantuzzi, C., and Casarini, M. (2014). TRAFCON\u2014Traffic control of AGVs in automatic warehouses. Springer Tracts in Advanced Robotics, Springer.","DOI":"10.1007\/978-3-319-03838-4_5"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","article-title":"Future paths for integer programming and links to artificial intelligence","volume":"13","author":"Glover","year":"1986","journal-title":"Comput. Oper. Res."}],"container-title":["Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2218-6581\/10\/2\/72\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:03:48Z","timestamp":1760162628000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2218-6581\/10\/2\/72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,19]]},"references-count":47,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["robotics10020072"],"URL":"https:\/\/doi.org\/10.3390\/robotics10020072","relation":{},"ISSN":["2218-6581"],"issn-type":[{"value":"2218-6581","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,19]]}}}