JRM Vol.34 No.1 pp. 86-100
doi: 10.20965/jrm.2022.p0086


Local and Global Path Planning for Autonomous Mobile Robots Using Hierarchized Maps

Nobuyuki Matsui*, Isuru Jayarathne**, Hiroaki Kageyama***, Keitaro Naruse**, Kazuki Urabe*, Ryota Sakamoto*, Tomoaki Mashiko***, Seiya Kumada***, Yuichi Yaguchi**, Makoto Yashiro**, Yasutsugu Ishibashi*, and Miki Yutani*

*TIS Inc.
17-1 Nishishinjuku 8-chome, Shinjuku-ku, Tokyo 160-0023, Japan

**University of Aizu
Tsuruga, Ikki-machi, Aizu Wakamatsu City, Fukushima 965-8580, Japan

***Japan Advanced System, Ltd.
128-27 Kitsuneishi, Morijuku, Sukagawa City, Fukushima 962-0001, Japan

February 19, 2021
September 24, 2021
February 20, 2022
autonomous robot, map, path planning
Local and Global Path Planning for Autonomous Mobile Robots Using Hierarchized Maps

The proposed hierarchized map structure

We are currently facing a “labor crisis,” particularly in the field of logistics, because of reductions in the labor force. Therefore, industries must make their logistics more efficient by utilizing autonomous mobile robotics technologies. This paper proposes a hierarchized map concept that makes unmanned delivery tasks which use multiple autonomous robots more efficiently. Using our proposed concept, an autonomous mobile robot can move automatically on a more efficient path than using current methods. In addition, the management platform for autonomous robots can be used to prevent accidents such as collisions or deadlocks between autonomous robots.

Cite this article as:
Nobuyuki Matsui, Isuru Jayarathne, Hiroaki Kageyama, Keitaro Naruse, Kazuki Urabe, Ryota Sakamoto, Tomoaki Mashiko, Seiya Kumada, Yuichi Yaguchi, Makoto Yashiro, Yasutsugu Ishibashi, and Miki Yutani, “Local and Global Path Planning for Autonomous Mobile Robots Using Hierarchized Maps,” J. Robot. Mechatron., Vol.34, No.1, pp. 86-100, 2022.
Data files:
  1. [1] R. Smith and P. Cheeseman, “On the Representation and Estimation of Spatial Uncertainty,” Int. J. on Robotics Research, Vol.5, No.4, pp. 56-68, 1986.
  2. [2] F. Lu and E. Millos, “Globally consistent range scan alignment for environment mapping,” Autonomous Robots, Vol.4, Issue 4, pp. 333-349, 1997.
  3. [3] S. Thrun, W. Burgard, and D. Fox, “Probabilistic Robotics,” The MIT Press, 2005.
  4. [4] E. Olson, J. Leonard, and S. Teller, “Fast iterative alignment of pose graphs with poor initial estimates,” Proc. of ICRA, pp. 2262-2269, 2006.
  5. [5] O. Brock and O. Khatib, “High-Speed Navigation Using the Global Dynamic Window Approach,” Proc. of IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 341-346, 1999.
  6. [6] H. Darweesh, E. Takeuchi, K. Takeda, Y. Ninomiya, A, Sujiwo, L. Y. Morales, N. Akai, T. Tomizawa, and S. Kato, “Open Source Integrated Planner for Autonomous Navigation in Highly Dynamic Environments,” J. Robot. Mechatron., Vol.29, No.4, pp. 668-684, 2017.
  7. [7] P. Marin-Plaza, A. Hussein, D. Martin, and A. Escalera, “Global and local path planning study in a ROS-based research platform for autonomous vehicles,” J. of Advanced Transportation, Vol.2018, 6392697, 2018.
  8. [8] J. Snape, J. van den Berg, S. J. Guy, and D. Manocha, “Smooth and collision-free navigation for multiple robots under differential-drive constraints,” Proc. of the 2010 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 18-22, 2010.
  9. [9] C. Roesmann, W. Feiten, T. Woesch, F. Hoffmann, and T. Bertram, “Trajectory modification considering dynamic constraints of autonomous robots,” Proc. of the 7th German Conf. on Robotics, pp. 74-79, 2012.
  10. [10] R. A. Knepper and D. Rus, “Pedestrian-inspired sampling-based multi-robot collision avoidance,” Proc. of the 21st IEEE Int. Symp. on Robot and Human Interactive Communication, pp. 94-100, 2012.
  11. [11] M. Samadi and M. F. Othman, “Global Path Planning for Autonomous Mobile Robot Using Genetic Algorithm,” Proc. of the 2013 Int. Conf. on Signal-Image Technology & Internet-Based Systems, pp. 726-730, 2013.
  12. [12] A. Mowshowitz, A. Tominaga, and E. Hayashi, “Robot Navigation in Forest Management,” J. Robot. Mechatron., Vol.30, No.2, pp. 223-230, 2018.
  13. [13] K. Karur, N. Sharma, C. Dharmatti, and J. E. Siegel, “A Survey of Path Planning Algorithms for Mobile Robots,” Vehicles, Vol.3, No.3, pp. 448-468, 2021.
  14. [14] K. Kurashiki, M. Aguilar, and S. Soontornvanichkit, “Visual Navigation of a Wheeled Mobile Robot Using Front Image in Semi-Structured Environment,” J. Robot. Mechatron., Vol.27, No.4, pp. 392-400, 2015.
  15. [15] S. Thrun and A. Bucken, “Integrating grid-based and topological maps for mobile robot navigation,” Proc. of National Conf. on Artificial Intelligence, Vol.2, pp. 944-951, 1996.
  16. [16] M. Bosse, P. Newman, J. Leonard, M. Soika, W. Feiten, and S. Teller, “An Atlas framework for scalable mapping,” Proc. of IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 1899-1906, 2003.
  17. [17] H. J. Chang, C. S. G. Lee, Y. C. Hu, and Y. H. Lu, “Multi-robot SLAM with topological/metric maps,” Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 1467-1472, 2007.
  18. [18] S. Thrun, “Learning metric-topological maps for indoor mobile robot navigation,” Artificial Intelligence, Vol.99, Issue 1, 1998.
  19. [19] H. Tibebu, J. Roche, V. D. Silva, and A. Kondoz, “LiDAR-Based Glass Detection for Improved Occupancy Grid Mapping,” Sensors, Vol.21, No.7, 2263, 2021.
  20. [20] J. Zhang and S. Singh, “LOAM: Lidar Odometry and Mapping in Real-time,” Robotics: Science and Systems Conf., 2014.
  21. [21] H. Moravec and A. Elfes, “High resolution maps from wide angle sonar,” Proc. of IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 116-121, 1985.
  22. [22] F. Dellaerty, D. Foxy, W. Burgardz, and S. Thruny, “Monte Carlo Localization for Mobile Robots,” Proc. of IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 1322-1328, 1999.
  23. [23] D. Fox, W. Burgardz, F. Dellaerty, and S. Thruny, “Monte Carlo Localization: Efficient Position Estimation for Mobile Robots,” Proc. of AAAI Conf. on Artificial Intelligence, pp. 343-349, 1999.
  24. [24] D. Fox, “Adapting the Sample Size in Particle Filters Through KLD-Sampling,” Int. J. of Robotics Research, Vol.22, No.12, pp. 985-1003, 2003.
  25. [25] B. P. Gerkey and K. Konolige, “Planning and control in unstructured terrain,” Proc. of IEEE Int. Conf. on Robotics and Automation (ICRA), Workshop on Path Planning on Costmap, 2008.
  26. [26] Y. K. Hwang and N. Ahuja, “A potential field approach to path planning,” IEEE Trans. on Robotics and Automation, Vol.8, Issue 1, 1992.
  27. [27] J. Barraquand, B. Langlois, and J. C. Latombe, “Numerical potential field techniques for robot path planning,” IEEE Trans. on Systems, Man, and Cybernetics, Vol.22, Issue 2, 1992.
  28. [28] E. Tsardoulias, K. Iliakopoulou, A. Kargakos, and L. Petrou, “A Review of Global Path Planning Methods for Occupancy Grid Maps Regardless of Obstacle Density,” J. of Intelligent & Robotic Systems, Vol.84, pp. 829-858, 2016.
  29. [29] P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimal Cost Paths,” IEEE Trans. on Systems Science and Cybernetics, Vol.4, No.2, 1968.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on May. 20, 2022