JRM Vol.35 No.6 pp. 1489-1502
doi: 10.20965/jrm.2023.p1489


Implementation of Brute-Force Value Iteration for Mobile Robot Path Planning and Obstacle Bypassing

Ryuichi Ueda ORCID Icon, Leon Tonouchi, Tatsuhiro Ikebe, and Yasuo Hayashibara ORCID Icon

Department of Advanced Robotics, Faculty of Advanced Engineering, Chiba Institute of Technology
2-17-1 Tsudanuma, Narashino, Chiba 275-0016, Japan

May 21, 2023
September 20, 2023
December 20, 2023
mobile robot navigation, obstacle avoidance, dynamic programming, value iteration

We applied a brute-force value iteration algorithm to mobile robot navigation. Value iteration is computationally more expensive than search methods used for navigation. However, it can perfectly calculate the expected cost-to-go from any point in a state space. From this cost data, a robot can know not only the optimal behavior at any position and orientation but also the appropriate detour path against suddenly appearing obstacles. This study implemented value iteration and investigated its properties through experiments with simulated and actual robots. Although its computational cost remained high, our implementation could operate a robot in an actual outdoor environment with 3,700 m2 free space. We also verified that our implementation calculates long detour paths toward closures composed of obstacles.

Avoidance of safety cones and persons

Avoidance of safety cones and persons

Cite this article as:
R. Ueda, L. Tonouchi, T. Ikebe, and Y. Hayashibara, “Implementation of Brute-Force Value Iteration for Mobile Robot Path Planning and Obstacle Bypassing,” J. Robot. Mechatron., Vol.35 No.6, pp. 1489-1502, 2023.
Data files:
  1. [1] 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, pp. 100-107, 1968.
  2. [2] D. Fox, W. Burgard, and S. Thrun, “The Dynamic Window Approach to Collision Avoidance,” IEEE Robotics & Automation Magazine, Vol.4, No.1, pp. 23-33, 1997.
  3. [3] Y. Li and Y. Liu, “Vision-based Obstacle Avoidance Algorithm for Mobile Robot,” Proc. of Chinese Automation Congress, pp. 1273-1278, 2020.
  4. [4] T. Sonoura, S. Tokura, T. Tasaki, F. Ozaki, and N. Matsuhira, “Reflective collision avoidance for mobile service robot in person coexistence environment,” J. Robot. Mechatron., Vol.23, No.6, pp. 999-1011, 2011.
  5. [5] R. Bellman, “Dynamic Programming,” Princeton University Press, Princeton, NJ, 1957.
  6. [6] R. S. Sutton and A. G. Barto, “Reinforcement Learning: An Introduction second edition,” The MIT Press, Cambridge, MA, 2018.
  7. [7] R. Ueda, T. Fukase, Y. Kobayashi, and T. Arai, “Vector Quantization for State-Action Map Compression,” Proc. of ICRA, pp. 2356-2361, 2003.
  8. [8] R. Ueda, T. Arai, K. Asanuma, S. Kamiya, and K. Umeda, “Mobile Robot Navigation based on Expected State Value under Uncertainty of Self-localization,” Proc. of IROS, pp. 473-478, 2003.
  9. [9] R. Ueda, K. Sakamoto, K. Takeshita, and T. Arai, “Dynamic Programming for Creating Cooperative Behavior of Two Soccer Robots —Part1: Creation of State-Action Map,” Proc. of ICRA, 2007.
  10. [10] R. Ueda, T. Ikebe, and Y. Hayashibara, “Real-time path planning ros package using brute-force value iteration,” The 39th Annual Conf. of the Robotics Society of Japan, Article No.RSJ2021AC2I1-04, 2021 (in Japanese).
  11. [11] R. Ueda, T. Ikebe, and Y. Hayashibara, “Real-time path planning considering quasi-static obstacles with value iteration,” The 40th Annual Conf. of the Robotics Society of Japan, Article No.RSJ2022AC12I2-01, 2022 (in Japanese).
  12. [12] R. Ueda, T. Ikebe, and Y. Hayashibara, “Real-time global planning and obstacle avoidance for mobile robot navigation by brute-force value iteration,” Proc. of 27th Robotics Symposia, pp. 109-112, 2022 (in Japanese).
  13. [13] L. Tonouchi, Y. Hayashibara, and R. Ueda, “Outdoor navigation with a mobile robot using value iteration,” Proc. of JSME Conf. on Robotics and Mechatronics (ROBOMECH), Article No.2P1-G06, 2023 (in Japanese).
  14. [14] S. Thrun, W. Burgard, and D. Fox, “Probabilistic Robotics,” MIT Press, 2005.
  15. [15] W. Hess, D. Kohler, H. Rapp, and D. Andor, “Real-Time Loop Colsure in 2D LIDAR SLAM,” Proc. of IEEE ICRA, pp. 1271-1278, 2016.
  16. [16] Y. Suzuki, S. Thompson, and S. Kagami, “Smooth path planning with pedestrian avoidance for wheeled robots,” J. Robot. Mechatron., Vol.22, No.1, pp. 21-27, 2010.
  17. [17] A. Ravankar, A. A. Ravankar, A. Rawankar, and Y. Hoshino, “Autonomous and Safe Navigation of Mobile Robots in Vineyard with Smooth Collision Avoidance,” Agriculture, Vol.11, No.10, Article No.954, 2021.
  18. [18] J.-C. Latombe, “Robot Motion Planning,” Kluwer Academic Publishers, Boston, MA, 1991.
  19. [19] S. Hoshino and K. Maki, “Safe and efficient motion planning of multiple mobile robots based on artificial potential for human behavior and robot congestion,” Advanced Robotics, Vol.29, No.17, pp. 1095-1109, 2015.
  20. [20] T. Tomizawa and Y. Shibata, “Oncoming human avoidance for autonomous mobile robot based on gait characteristics,” J. Robot. Mechatron., Vol.28, No.4, pp. 500-507, 2016.
  21. [21] Y. Arai, T. Sago, Y. Ueyama, and M. Harada, “MGV obstacle avoidance trajectory generation considering vehicle shape,” J. Robot. Mechatron., Vol.35, No.2, pp. 262-270, 2023.

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

Last updated on Feb. 19, 2024