831
Views
4
CrossRef citations to date
0
Altmetric
Research Article

Scheduling of autonomous mobile robots with conflict-free routes utilising contextual-bandit-based local search

ORCID Icon, &
Pages 4090-4116 | Received 09 Feb 2021, Accepted 31 Mar 2022, Published online: 30 Apr 2022

References

  • Abar, S., G. K. Theodoropoulos, P. Lemarinier, and G. M. O’Hare. 2017. “Agent Based Modelling and Simulation Tools: A Review of the State-of-art Software.” Computer Science Review 24: 13–33.
  • Akhshabi, M., R. Tavakkoli-Moghaddam, and F. Rahnamay-Roodposhti. 2014. “A Hybrid Particle Swarm Optimization Algorithm for a no-Wait Flow Shop Scheduling Problem with the Total Flow Time.” The International Journal of Advanced Manufacturing Technology 70 (5-8): 1181–1188.
  • Asama, H., K. Ozaki, H. Itakura, A. Matsumoto, Y. Ishida, and I. Endo. 1991. Collision Avoidance Among Multiple Mobile Robots Based on Rules and Communication. In Proceedings IROS'91: IEEE/RSJ International Workshop on Intelligent Robots and Systems’ 91 (pp. 1215-1220). IEEE.
  • Baldacci, R., E. Bartolini, and A. Mingozzi. 2011. “An Exact Algorithm for the Pickup and Delivery Problem with Time Windows.” Operations Research 59 (2): 414–426.
  • Baldi, S., N. Maric, R. Dornberger, and T. Hanne. 2018. Pathfinding Optimization When Solving the Paparazzi Problem Comparing A* and Dijkstra's Algorithm. In 2018 6th International Symposium on Computational and Business Intelligence (ISCBI) (pp. 16-22). IEEE.
  • Belhaous, S., S. Baroud, S. Chokri, Z. Hidila, A. Naji, and M. Mestari. 2019. Parallel Implementation of A* Search Algorithm For Road Network. In 2019 Third International Conference on Intelligent Computing in Data Sciences (ICDS) (pp. 1-7). IEEE.
  • Bonabeau, E. 2002. “Agent-based Modeling: Methods and Techniques for Simulating Human Systems.” Proceedings of the National Academy of Sciences 99 (suppl 3): 7280–7287.
  • Botea, A., M. Müller, and J. Schaeffer. 2004. “Near Optimal Hierarchical Path-Finding.” Journal of Game Development 1 (1): 7–28.
  • Chen, Y., M. Cutler, and J. P. How. 2015. Decoupled Multiagent Path Planning Via Incremental Sequential Convex Programming. In 2015 IEEE International Conference on Robotics and Automation (ICRA) (pp. 5954-5961). IEEE.
  • Chen, Y. F., M. Everett, M. Liu, and J. P. How. 2017. Socially Aware Motion Planning With Deep Reinforcement Learning. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 1343-1350). IEEE.
  • Cherkesly, M., G. Desaulniers, and G. Laporte. 2015. “A Population-Based Metaheuristic for the Pickup and Delivery Problem with Time Windows and LIFO Loading.” Computers & Operations Research 62: 23–35.
  • Cirillo, M., T. Uras, and S. Koenig. 2014. A Lattice-Based Approach to Multi-Robot Motion Planning for Non-Holonomic Vehicles. In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 232-239). IEEE.
  • Cohen, L., T. Uras, S. Jahangiri, A. Arunasalam, S. Koenig, and T. K. Kumar. 2018. The FastMap Algorithm for Shortest Path Computations. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (pp. 1427-1433). AAAI Press.
  • Curtois, T., D. Landa-Silva, Y. Qu, and W. Laesanklang. 2018. “Large Neighbourhood Search with Adaptive Guided Ejection Search for the Pickup and Delivery Problem with Time Windows.” EURO Journal on Transportation and Logistics 7 (2): 151–192.
  • Dijkstra, E. W. 1959. “A Note on two Problems in Connexion with Graphs.” Numerische Mathematik 1 (1): 269–271.
  • Draganjac, I., D. Miklić, Z. Kovačić, G. Vasiljević, and S. Bogdan. 2016. “Decentralized Control of Multi-AGV Systems in Autonomous Warehousing Applications.” IEEE Transactions on Automation Science and Engineering 13 (4): 1433–1447.
  • Duchoň, F., A. Babinec, M. Kajan, P. Beňo, M. Florek, T. Fico, and L. Jurišica. 2014. “Path Planning with Modified a Star Algorithm for a Mobile Robot.” Procedia Engineering 96: 59–69.
  • Elish, M. O., and K. O. Elish. 2009. Application of Treenet in Predicting Object-Oriented Software Maintainability: A comparative study. In 2009 13th European Conference on Software Maintenance and Reengineering (pp. 69-78). IEEE.
  • Elmachtoub, A. N., R. McNellis, S. Oh, and M. Petrik. 2017. A Practical Method for Solving Contextual Bandit Problems Using Decision Trees. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, UAI (pp. 11-15).
  • Ferguson, D., M. Likhachev, and A. Stentz. 2005. A Guide to Heuristic-Based Path Planning. In Proceedings of the international workshop on planning under uncertainty for autonomous systems, international conference on automated planning and scheduling (ICAPS) (pp. 9-18).
  • Fragapane, G., H. H. Hvolby, F. Sgarbossa, and J. O. Strandhagen. 2021. “Autonomous Mobile Robots in Sterile Instrument Logistics: An Evaluation of the Material Handling System for a Strategic fit Framework.” Production Planning & Control, 1–15. doi:https://doi.org/10.1080/09537287.2021.1884914.
  • Frank, A. G., L. S. Dalenogare, and N. F. Ayala. 2019. “Industry 4.0 Technologies: Implementation Patterns in Manufacturing Companies.” International Journal of Production Economics 210: 15–26.
  • Friedman, J. H., and J. J. Meulman. 2003. “Multiple Additive Regression Trees with Application in Epidemiology.” Statistics in Medicine 22 (9): 1365–1381.
  • Godoy, J. E., I. Karamouzas, S. J. Guy, and M. Gini. 2015. Adaptive Learning For Multi-Agent Navigation. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (pp. 1577-1585). International Foundation for Autonomous Agents and Multiagent Systems.
  • Goëffon, A., F. Lardeux, and F. Saubion. 2016. “Simulating non-Stationary Operators in Search Algorithms.” Applied Soft Computing 38: 257–268.
  • Guney, M. A., and I. A. Raptis. 2021. “Dynamic Prioritized Motion Coordination of Multi-AGV Systems.” Robotics and Autonomous Systems 139: 1–9.
  • Guy, S. J., J. Chhugani, C. Kim, N. Satish, M. Lin, D. Manocha, and P. Dubey. 2009. Clearpath: Highly Parallel Collision Avoidance for Multi-agent Simulation. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (pp. 177-187). ACM.
  • Harabor, D. D., and A. Grastien. 2011. Online Graph Pruning for Pathfinding on Grid Maps. In Twenty-Fifth AAAI Conference on Artificial Intelligence.
  • Hart, P. E., N. J. Nilsson, and B. Raphael. 1968. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Transactions on Systems Science and Cybernetics 4 (2): 100–107.
  • Ho, Y. C., and S. H. Chien. 2006. “A Simulation Study on the Performance of Task-Determination Rules and Delivery-Dispatching Rules for Multiple-Load AGVs.” International Journal of Production Research 44 (20): 4193–4222.
  • Ho, Y. C., and H. C. Liu. 2009. “The Performance of Load-Selection Rules and Pickup-Dispatching Rules for Multiple-Load AGVs.” Journal of Manufacturing Systems 28 (1): 1–10.
  • Hosny, M. I., and C. L. Mumford. 2009. Investigating Genetic Algorithms for Solving the Multiple Vehicle Pickup and Delivery Problem with Time Windows. In MIC2009, Metaheuristic International Conference.
  • Hu, H., X. Yang, S. Xiao, and F. Wang. 2021. “Anti-conflict AGV Path Planning in Automated Container Terminals Based on Multi-Agent Reinforcement Learning.” International Journal of Production Research, 1–16. doi:https://doi.org/10.1080/00207543.2021.1998695.
  • Huang, B., M. Zhou, A. Abusorrah, and K. Sedraoui. 2020. “Scheduling Robotic Cellular Manufacturing Systems With Timed Petri Net, A* Search, and Admissible Heuristic Function.” IEEE Transactions on Automation Science and Engineering 243–250.
  • Jager, M., and B. Nebel. 2001. Decentralized Collision Avoidance, Deadlock Detection, and Deadlock Resolution for Multiple Mobile Robots. In Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No. 01CH37180) (Vol. 3, pp. 1213-1219). IEEE.
  • Jun, S., S. Lee, and Y. Yih. 2021. “Pickup and Delivery Problem with Recharging for Material Handling Systems Utilising Autonomous Mobile Robots.” European Journal of Operational Research 289 (3): 1153–1168.
  • Khantanapoka, K., and K. Chinnasarn. 2009. Pathfinding of 2D & 3D Game Real-time Strategy with Depth Direction A∗ Algorithm for Multi-Layer. In 2009 Eighth international symposium on natural language processing (pp. 184-188). IEEE.
  • Knopp, S., P. Sanders, D. Schultes, F. Schulz, and D. Wagner. 2007. Computing Many-to-Many Shortest Paths Using Highway Hierarchies. In 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 36-45). Society for Industrial and Applied Mathematics.
  • Koenig, S., and M. Likhachev. 2002. D* Lite. In Proceedings of the AAAI Conference of Artificial Intelligence (AAAI), pp. 476-483.
  • Lee, H. Y., and C. C. Murray. 2019. “Robotics in Order Picking: Evaluating Warehouse Layouts for Pick, Place, and Transport Vehicle Routing Systems.” International Journal of Production Research 57 (18): 5821–5841.
  • Li, Y., H. Chen, and C. Prins. 2016. “Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Time Windows, Profits, and Reserved Requests.” European Journal of Operational Research 252 (1): 27–38.
  • Li, H., and A. Lim. 2003. “A Metaheuristic for the Pickup and Delivery Problem with Time Windows.” International Journal on Artificial Intelligence Tools 12 (02): 173–186.
  • Li, J., X. Meng, M. Zhou, and X. Dai. 2016. “A two-Stage Approach to Path Planning and Collision Avoidance of Multibridge Machining Systems.” IEEE Transactions on Systems, Man, and Cybernetics: Systems 47 (7): 1039–1049.
  • Lim, A., Z. Zhang, and H. Qin. 2017. “Pickup and Delivery Service with Manpower Planning in Hong Kong Public Hospitals.” Transportation Science 51 (2): 688–705.
  • Liu, M., H. Ma, J. Li, and S. Koenig. 2019. Task and Path Planning for Multi-Agent Pickup and Delivery. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (pp. 1152-1160). International Foundation for Autonomous Agents and Multiagent Systems.
  • Long, P., T. Fan, X. Liao, W. Liu, H. Zhang, and J. Pan. 2018. Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning. In 2018 IEEE International Conference on Robotics and Automation (ICRA) (pp. 6252-6259). IEEE.
  • Luo, J., K. Xing, M. Zhou, X. Li, and X. Wang. 2014. “Deadlock-free Scheduling of Automated Manufacturing Systems Using Petri Nets and Hybrid Heuristic Search.” IEEE Transactions on Systems, Man, and Cybernetics: Systems 45 (3): 530–541.
  • Ma, H., D. Harabor, P. J. Stuckey, J. Li, and S. Koenig. 2019. Searching with Consistent Prioritization for Multi-Agent Path Finding. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, pp. 7643-7650).
  • Mahmoudi, M., and X. Zhou. 2016. “Finding Optimal Solutions for Vehicle Routing Problem with Pickup and Delivery Services with Time Windows: A Dynamic Programming Approach Based on State–Space–Time Network Representations.” Transportation Research Part B: Methodological 89: 19–42.
  • Małopolski, W. 2018. “A Sustainable and Conflict-Free Operation of AGVs in a Square Topology.” Computers & Industrial Engineering 126: 472–481.
  • Masmoudi, M. A., M. Hosny, E. Demir, K. N. Genikomsakis, and N. Cheikhrouhou. 2018. “The Dial-a-Ride Problem with Electric Vehicles and Battery Swapping Stations.” Transportation Research Part E: Logistics and Transportation Review 118: 392–420.
  • Material Handling Institute. 2018. The 2018 MHI Annual Industry Report - Overcoming Barriers to NextGen Supply Chain Innovation. https://www.mhi.org/publications/report.
  • Mitrović-Minić, S., R. Krishnamurti, and G. Laporte. 2004. “Double-horizon Based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows.” Transportation Research Part B: Methodological 38 (8): 669–685.
  • Miyamoto, T., and K. Inoue. 2016. “Local and Random Searches for Dispatch and Conflict-Free Routing Problem of Capacitated AGV Systems.” Computers & Industrial Engineering 91: 1–9.
  • Moore, E. F. 1959. The Shortest Path Through a Maze. In Proc. Int. Symp. Switching Theory, (pp. 285-292).
  • Moorthy, R. L., W. Hock-Guan, N. Wing-Cheong, and T. Chung-Piaw. 2003. “Cyclic Deadlock Prediction and Avoidance for Zone-Controlled AGV System.” International Journal of Production Economics 83 (3): 309–324.
  • Mousavinejad, E., X. Ge, Q. L. Han, T. J. Lim, and L. Vlacic. 2021. “An Ellipsoidal Set-Membership Approach to Distributed Joint State and Sensor Fault Estimation of Autonomous Ground Vehicles.” IEEE/CAA Journal of Automatica Sinica 8 (6): 1107–1118.
  • Muñoz-Carpintero, D., D. Sáez, C. E. Cortés, and A. Núñez. 2015. “A Methodology Based on Evolutionary Algorithms to Solve a Dynamic Pickup and Delivery Problem Under a Hybrid Predictive Control Approach.” Transportation Science 49 (2): 239–253.
  • Murugappan, E., N. Subramanian, S. Rahman, M. Goh, and H. K. Chan. 2021. “Performance Analysis of Clustering Methods for Balanced Multi-Robot Task Allocations.” International Journal of Production Research, 1–16. doi:https://doi.org/10.1080/00207543.2021.1955994.
  • Nareyek, A. 2003. “Choosing Search Heuristics by non-Stationary Reinforcement Learning.” In Metaheuristics: Computer Decision-Making, edited by Mauricio G. C. Resende and Jorge Pinho de Sousa, 523–544. Boston: Springer.
  • Pankratz, G. 2005. “A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows.” Or Spectrum 27 (1): 21–41.
  • Phan, D. H., and J. Suzuki. 2016. “Evolutionary Multiobjective Optimization for the Pickup and Delivery Problem with Time Windows and Demands.” Mobile Networks and Applications 21 (1): 175–190.
  • Reveliotis, S. A. 2000. “Conflict Resolution in AGV Systems.” IIE Transactions 32 (7): 647–659.
  • Ropke, S., and J. F. Cordeau. 2009. “Branch and cut and Price for the Pickup and Delivery Problem with Time Windows.” Transportation Science 43 (3): 267–286.
  • Savelsbergh, M. W. P., and M. Sol. 1994. A Branch-and-Price Algorithm For the Pickup and Delivery Problem with Time Windows. Technical Report COC-94-06, Georgia Institute of Technology, Atlanta.
  • Schniederjans, D. G., C. Curado, and M. Khalajhedayati. 2020. “Supply Chain Digitisation Trends: An Integration of Knowledge Management.” International Journal of Production Economics 220: 1–11.
  • Schouwenaars, T., B. De Moor, E. Feron, and J. How. 2001. Mixed Integer Programming for Multi-Vehicle Path Planning. In 2001 European control conference (ECC) (pp. 2603-2608). IEEE.
  • Sharon, G., R. Stern, A. Felner, and N. R. Sturtevant. 2015. “Conflict-based Search for Optimal Multi-Agent Pathfinding.” Artificial Intelligence 219: 40–66.
  • Shouwen, J., L. Di, C. Zhengrong, and G. Dong. 2020. “Integrated Scheduling in Automated Container Terminals Considering AGV Conflict-Free Routing.” Transportation Letters 13 (7): 501–513.
  • Siegwart, R., I. R. Nourbakhsh, and D. Scaramuzza. 2011. Introduction to Autonomous Mobile Robots. London, England: MIT press.
  • Sigurdson, D., V. Bulitko, W. Yeoh, C. Hernández, and S. Koenig. 2018. Multi-Agent Pathfinding with Real-Time Heuristic Search. In 2018 IEEE Conference on Computational Intelligence and Games (CIG) (pp. 1-8). IEEE.
  • Srivastava, S. C., A. K. Choudhary, S. Kumar, and M. K. Tiwari. 2008. “Development of an Intelligent Agent-Based AGV Controller for a Flexible Manufacturing System.” International Journal of Advanced Manufacturing Technology 36 (7-8): 780–797.
  • Sun, D., A. Kleiner, and B. Nebel. 2014. Behavior-based Multi-robot Collision Avoidance. In 2014 IEEE international conference on robotics and automation (ICRA) (pp. 1668-1673). IEEE.
  • Sun, P., L. P. Veelenturf, M. Hewitt, and T. Van Woensel. 2018. “The Time-Dependent Pickup and Delivery Problem with Time Windows.” Transportation Research Part B: Methodological 116: 1–24.
  • Sun, P., L. P. Veelenturf, M. Hewitt, and T. Van Woensel. 2020. “Adaptive Large Neighborhood Search for the Time-Dependent Profitable Pickup and Delivery Problem with Time Windows.” Transportation Research Part E: Logistics and Transportation Review 138: 1–33.
  • Tsolakis, N., D. Zissis, S. Papaefthimiou, and N. Korfiatis. 2021. “Towards AI Driven Environmental Sustainability: An Application of Automated Logistics in Container Port Terminals.” International Journal of Production Research, 1–21. doi:https://doi.org/10.1080/00207543.2021.1914355.
  • Tzafestas, S. G. 2018. “Mobile Robot Control and Navigation: A Global Overview.” Journal of Intelligent & Robotic Systems 91 (1): 35–58.
  • Utamima, A., K. R. Pradina, N. S. Dini, and H. Studiawan. 2015. “Distribution Route Optimization of Gallon Water Using Genetic Algorithm and Tabu Search.” Procedia Computer Science 72: 503–510.
  • Vinayak, R. K., and R. Gilad-Bachrach. 2015. DART: Dropouts Meet Multiple Additive Regression Trees. In Artificial Intelligence and Statistics (pp. 489-497).
  • Wagner, G., and H. Choset. 2011. M*: A Complete Multirobot Path Planning Algorithm with Performance Bounds. In 2011 IEEE/RSJ international conference on intelligent robots and systems (pp. 3260-3267). IEEE.
  • Wang, T., R. M. Lima, L. Giraldi, and O. M. Knio. 2019. “Trajectory Planning for Autonomous Underwater Vehicles in the Presence of Obstacles and a Nonlinear Flow Field Using Mixed Integer Nonlinear Programming.” Computers & Operations Research 101: 55–75.
  • Wang, L., and J. Lu. 2019. “A Memetic Algorithm with Competition for the Capacitated Green Vehicle Routing Problem.” IEEE/CAA Journal of Automatica Sinica 6 (2): 516–526.
  • Wang, J., Y. Sun, Z. Zhang, and S. Gao. 2020. “Solving Multitrip Pickup and Delivery Problem with Time Windows and Manpower Planning Using Multiobjective Algorithms.” IEEE/CAA Journal of Automatica Sinica 7 (4): 1134–1153.
  • Wu, N., and M. Zhou. 2005. “Modeling and Deadlock Avoidance of Automated Manufacturing Systems with Multiple Automated Guided Vehicles.” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 35 (6): 1193–1202.
  • Wu, N., and M. Zhou. 2007. “Shortest Routing of Bidirectional Automated Guided Vehicles Avoiding Deadlock and Blocking.” IEEE/ASME Transactions on Mechatronics 12 (1): 63–72.
  • Xue, L., Z. Luo, and A. Lim. 2016. “Exact Approaches for the Pickup and Delivery Problem with Loading Cost.” Omega 59: 131–145.
  • Yu, J., and S. M. LaValle. 2016. “Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics.” IEEE Transactions on Robotics 32 (5): 1163–1177.
  • Yuan, R., T. Dong, and J. Li. 2016. “Research on the Collision-Free Path Planning of Multi-AGVs System Based on Improved A* Algorithm.” American Journal of Operations Research 6 (06): 442–449.
  • Zhang, Z., M. Liu, and A. Lim. 2015. “A Memetic Algorithm for the Patient Transportation Problem.” Omega 54: 60–71.
  • Zhao, Y., K. L. Man, H. N. Liang, W. Wang, Y. Yue, and T. Jeong. 2015. Design of Intelligent Algorithms For Multi-Mobile Robot Systems. In 2015 International SoC Design Conference (ISOCC) (pp. 177-178). IEEE.
  • Zheng, K., D. Tang, W. Gu, and M. Dai. 2013. “Distributed Control of Multi-AGV System Based on Regional Control Model.” Production Engineering 7 (4): 433–441.
  • Zhong, M., Y. Yang, Y. Dessouky, and O. Postolache. 2020. “Multi-AGV Scheduling for Conflict-Free Path Planning in Automated Container Terminals.” Computers & Industrial Engineering 142: 1–11.
  • Zhou, B., and Z. He. 2021. “A Novel Hybrid-Load AGV for JIT-Based Sustainable Material Handling Scheduling with Time Window in Mixed-Model Assembly Line.” International Journal of Production Research, 1–22. doi:https://doi.org/10.1080/00207543.2021.2017056.
  • Zhou, L., Z. Jiang, N. Geng, Y. Niu, F. Cui, K. Liu, and N. Qi. 2021. “Production and Operations Management for Intelligent Manufacturing: A Systematic Literature Review.” International Journal of Production Research, 1–39. doi:https://doi.org/10.1080/00207543.2021.2017055.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.