Efficient path planning for automated guided vehicles using A* (Astar) algorithm incorporating turning costs in search heuristic

References

• Anavatti, S. G., S. L. Francis, and M. Garratt. 2016. “Path-Planning Modules for Autonomous Vehicles: Current Status and Challenges.” 2015 International Conference on Advanced Mechatronics, Intelligent Manufacture, and Industrial Automation (ICAMIMIA), Surabaya, Indonesia, October 15-17, 205–214.
   Google Scholar
• Bae, J., and W. Chung. 2018. “A Heuristic for Path Planning of Multiple Heterogeneous Automated Guided Vehicles.” International Journal of Precision Engineering and Manufacturing 19 (12): 1765–1771.
   Web of Science ®Google Scholar
• Bae, J., and W. Chung. 2019. “Efficient Path Planning for Multiple Transportation Robots Under Various Loading Conditions.” International Journal of Advanced Robotic Systems 16 (2): 1–9.
   Web of Science ®Google Scholar
• Ballamajalu, R., M. Li, F. Sahin, C. Hochgraf, R. Ptucha, and M. E. Kuhl. 2020, August 20-21. “Turn and Orientation Sensitive A ∗ for Autonomous Vehicles in Intelligent Material Handling Systems.” IEEE International Conference on Automation Science and Engineering, 606–611.
   Google Scholar
• Bartlett, K., J. Lee, S. Ahmed, G. Nemhauser, J. Sokol, and B. Na. 2014. “Congestion-Aware Dynamic Routing in Automated Material Handling Systems.” Computers and Industrial Engineering 70 (1): 176–182.
   Web of Science ®Google Scholar
• Campbell, S., N. O'Mahony, A. Carvalho, L. Krpalkova, D. Riordan, and J. Walsh. 2020. “Path Planning Techniques for Mobile Robots A Review.” 2020 6th International Conference on Mechatronics and Robotics Engineering (ICMRE), Barcelona, Spain, February 12-15, 12–16.
   Google Scholar
• Chaudhari, A. M., M. R. Apsangi, and A. B. Kudale. 2017, March 24-25. “Improved A-Star Algorithm with Least Turn for Robotic Rescue Operations.” Communications in Computer and Information Science 776: 614–627.
   Google Scholar
• Cui, Y., D. P. Ma, Y. Fang, and Z. Lei. 2018. “Conflict-Free Path Planning of AGV Based on Improved A-star Algorithm.” 2nd International Conference on Information, Communication and Engineering (ICICE 2018), Hangzhou, Zhejiang Province, P.R. China, November 9-13, 31–34.
   Google Scholar
• De Ryck, M., M. Versteyhe, and F. Debrouwere. 2019. “Automated Guided Vehicle Systems, State-of-the-Art Control Algorithms and Techniques.” Journal of Manufacturing Systems 54: 152–173.
   Web of Science ®Google Scholar
• Dijkstra, E. W. 1959. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1 (1): 269–271.
   Google Scholar
• Floyd, R. W. 1962. “Algorithm 97: Shortest Path.” Communications of the ACM 5 (6): 345.
   Web of Science ®Google Scholar
• Fragapane, G., R. de Koster, F. Sgarbossa, and J. O. Strandhagen. 2021. “Planning and Control of Autonomous Mobile Robots for Intralogistics: Literature Review and Research Agenda.” European Journal of Operational Research 294 (2): 405–426.
   Web of Science ®Google Scholar
• Fransen, K. J. C. 2019. “A Path Planning Approach for AGVs in the Dense Grid-Based AgvSorter.” Master's thesis, Eindhoven University of Technology. https://research.tue.nl/en/studentTheses/a-path-planning-approach-for-agvs-in-the-dense-grid-based-agvsort
   Google Scholar
• Fransen, K. J. C., J. A. W. M. Van Eekelen, A. Pogromsky, M. A. A. Boon, and I. J. B. F. Adan. 2020. “A Dynamic Path Planning Approach for Dense, Large, Grid-Based Automated Guided Vehicle Systems.” Computers and Operations Research 123: 1–10.
   Web of Science ®Google Scholar
• Ganeshmurthy, M. S., and G. R. Suresh. 2015. “Path Planning Algorithm for Autonomous Mobile Robot in Dynamic Environment.” 2015 3rd International Conference on Signal Processing, Communication and Networking (ICSCN), Chennai, India, March 26-28.
   Google Scholar
• 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.
   Web of Science ®Google Scholar
• Injarapu, A. S. H. H. V., and S. K. Gawre. 2018. “A Survey of Autonomous Mobile Robot Path Planning Approaches.” International Conference on Recent Innovations in Signal Processing and Embedded Systems, RISE 2017, Bhubaneswar, India, July 27, 624–628.
   Google Scholar
• Jia, F., C. Ren, Y. Chen, and Z. Xu. 2017. “A System Control Strategy of a Conflict-Free Multi-AGV Routing on Improved A ∗ Algorithm.” 2017 24th International Conference on Mechatronics and Machine Vision in Practice (M2VIP), Auckland, New Zealand, November 21–23, 1–6.
   Google Scholar
• Krukhmalev, V., and V. Pshikhopov. 2017. “Chapter Four - Genetic Algorithms Path Planning.” In Path Planning for Vehicles Operating in Uncertain 2D Environments, edited by V. Pshikhopov, 137–184. Oxford: Butterworth-Heinemann.
   Google Scholar
• Kusuma, M., Riyanto, and C. Machbub. 2019. “Humanoid Robot Path Planning and Rerouting Using A-Star Search Algorithm.” 2019 IEEE International Conference on Signals and Systems (ICSigSys), Bandung, Indonesia, July 16-18, 110–115.
   Google Scholar
• Lawler, E. L., and D. E. Wood. 1966. “Branch-and-Bound Methods: A Survey.” Operations Research 14 (4): 699–719.
   Web of Science ®Google Scholar
• Lian, Y., and W. Xie. 2019. “Improved A ∗ Multi-AGV Path Planning Algorithm Based on Grid-Shaped Network.” 2019 Chinese Control Conference (CCC), Guangzhou, China, July 27–30, 2088–2092.
   Google Scholar
• Lian, Y., W. Xie, and L. Zhang. 2020, July 11-17. “A Probabilistic Time-Constrained Based Heuristic Path Planning Algorithm in Warehouse Multi-AGV Systems.” IFAC-PapersOnLine, Vol. 53, 2538–2543.
   Google Scholar
• Lin, M., K. Yuan, C. Shi, and Y. Wang. 2017. “Path Planning of Mobile Robot Based on Improved A ∗ Algorithm.” 2017 29th Chinese Control and Decision Conference (CCDC), Chongqing, China, May 28–30, 3570–3576.
   Google Scholar
• Liu, Y., M. Chen, and H. Huang. 2019. “Multi-Agent Pathfinding Based on Improved Cooperative A ∗ in Kiva System.” 2019 5th International Conference on Control, Automation and Robotics (ICCAR), Beijing, China, April 19–22 633–638.
   Google Scholar
• Liu, X., and D. Gong. 2011. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, Wuhan, China, March 25-27, 24–27.
   Google Scholar
• Mac, T. T., C. Copot, D. T. Tran, and R. De Keyser. 2016. “Heuristic Approaches in Robot Path Planning: A Survey.” Robotics and Autonomous Systems 86: 13–28.
   Web of Science ®Google Scholar
• MacGregor, J., and S. Leung. 2009. “Pathfinding Strategy for Multiple Non-Playing Characters in 2.5 D Game Worlds.” In Learning by Playing. Game-based Education System Design and Development. Edutainment 2009. Lecture Notes in Computer Science. Vol. 5670, edited by M. Chang, R. Kuo, Kinshuk, G.-D. Cheng, and M. Hirose, 351–362. Berlin: Springer.
   Google Scholar
• Mathew, G. E. 2015. “Direction Based Heuristic for Pathfinding in Video Games.” Procedia Computer Science 47C: 262–271.
   Google Scholar
• Mu, T., J. Zhu, X. Li, and J. Li. 2020, November 22-25. “Research on Two-Stage Path Planning Algorithms for Storage Multi-AGV.” Communications in Computer and Information Science 1160: 418–430.
   Google Scholar
• Róka, R., ed. 2018. Advanced Path Planning for Mobile Entities. London: IntechOpen.
   Google Scholar
• Sedgewick, R., and J. S. Vitter. 1986. “Shortest Paths in Euclidean Graphs.” Algorithmica1 (1): 31–48.
   Web of Science ®Google Scholar
• Shabalina, K., A. Sagitov, and E. Magid. 2018. “Comparative Analysis of Mobile Robot Wheels Design.” Proceedings -- International Conference on Developments in eSystems Engineering, DeSE, Cambridge, September 2-5, 175–179.
   Google Scholar
• Shi, J., Y. Su, C. Bu, and X. Fan. 2020. “A Mobile Robot Path Planning Algorithm Based on Improved A*.” Journal of Physics: Conference Series 1486: 032018.
   Google Scholar
• Song, Z., and L. Yuan. 2019. “Application of Improved A ∗ Algorithm in Mobile Robot Path Planning.” 2019 3rd International Symposium on Autonomous Systems (ISAS), Shanghai, China, May 29–31, 534–537.
   Google Scholar
• Tóth, G. 2000. “Note on Geometric Graphs.” Journal of Combinatorial Theory. Series A 89 (1): 126–132.
   Web of Science ®Google Scholar
• Vis, I. F. A. 2006. “Survey of Research in the Design and Control of Automated Guided Vehicle Systems.” European Journal of Operational Research 170 (3): 677–709.
   Web of Science ®Google Scholar
• Wang, C., L. Wang, J. Qin, Z. Wu, L. Duan, Z. Li, M. Cao, et al. 2015. “Path Planning of Automated Guided Vehicles Based on Improved A-Star Algorithm.” 2015 IEEE International Conference on Information and Automation, Lijiang, Yunnan, China, August 8-10, 2071–2076.
   Google Scholar
• Wang, Z., and X. Xiang. 2018. “Improved Astar Algorithm for Path Planning of Marine Robot.” 2018 37th Chinese Control Conference (CCC), Wuhan, China, July 25-27, 5410–5414.
   Google Scholar
• Whangbo, T. K. 2007. “Efficient Modified Bidirectional A ∗ Algorithm for Optimal Route-Finding.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), edited by H. G. Okuno and M. Ali, 344–353. Berlin: Springer.
   Google Scholar
• Yao, J., C. Lin, X. Xie, A. J. Wang, and C. C. Hung. 2010. “Path Planning for Virtual Human Motion Using Improved A ∗ Algorithm.” 2010 Seventh International Conference on Information Technology: New Generations, Las Vegas, Nevada, USA, April 12–14, 1154–1158.
   Google Scholar
• Yap, P. 2002. “Grid-Based Path-Finding.” In Advances in Artificial Intelligence. Canadian AI 2002. Lecture Notes in Computer Science. Vol. 2338, edited by R. Cohen and B. Spencer, 44–55. Berlin: Springer.
   Google Scholar
• Zheng, T., Y. Xu, and D. Zheng. 2019. “AGV Path Planning Based on Improved A-Star Algorithm.” 2019 IEEE 3rd Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC), Chongqing, China, October 11-13, 1534–1538.
   Google Scholar