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

Ryuichi Ueda; Leon Tonouchi; Tatsuhiro Ikebe; Yasuo Hayashibara

doi:10.20965/jrm.2023.p1489

single-rb.php

« previous

JRM Vol.35 No.6 pp. 1489-1502

doi: 10.20965/jrm.2023.p1489

(2023)

Paper:

Views over last 60 days: 5,093

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

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

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

Received:

May 21, 2023

Accepted:

September 20, 2023

Published:

December 20, 2023

Keywords:

mobile robot navigation, obstacle avoidance, dynamic programming, value iteration

Abstract

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 m² free space. We also verified that our implementation calculates long detour paths toward closures composed of obstacles.

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:

References

[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. https://doi.org/10.1109/TSSC.1968.300136
[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. https://doi.org/10.1109/100.580977
[3] Y. Li and Y. Liu, “Vision-based Obstacle Avoidance Algorithm for Mobile Robot,” Proc. of Chinese Automation Congress, pp. 1273-1278, 2020. https://doi.org/10.1109/CAC51589.2020.9326906
[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. https://doi.org/10.20965/jrm.2011.p0999
[5] R. Bellman, “Dynamic Programming,” Princeton University Press, Princeton, NJ, 1957.
[6] R. S. Sutton and A. G. Barto, “Reinforcement Learning: An Introduction second edition,” The MIT Press, Cambridge, MA, 2018.
[7] R. Ueda, T. Fukase, Y. Kobayashi, and T. Arai, “Vector Quantization for State-Action Map Compression,” Proc. of ICRA, pp. 2356-2361, 2003. https://doi.org/10.1109/ROBOT.2003.1241945
[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. https://doi.org/10.1109/IROS.2003.1250674
[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. https://doi.org/10.1109/ROBOT.2007.363756
[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] 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] 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] 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] S. Thrun, W. Burgard, and D. Fox, “Probabilistic Robotics,” MIT Press, 2005.
[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. https://doi.org/10.1109/ICRA.2016.7487258
[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. https://doi.org/10.1109/ICARA.2000.4803910
[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. https://doi.org/10.3390/agriculture11100954
[18] J.-C. Latombe, “Robot Motion Planning,” Kluwer Academic Publishers, Boston, MA, 1991.
[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. https://doi.org/10.1080/01691864.2015.1033461
[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. https://doi.org/10.20965/jrm.2016.p0500
[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. https://doi.org/10.20965/jrm.2023.p0262

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[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. https://doi.org/10.1109/TSSC.1968.300136

[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. https://doi.org/10.1109/100.580977

[3] [3] Y. Li and Y. Liu, “Vision-based Obstacle Avoidance Algorithm for Mobile Robot,” Proc. of Chinese Automation Congress, pp. 1273-1278, 2020. https://doi.org/10.1109/CAC51589.2020.9326906

[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. https://doi.org/10.20965/jrm.2011.p0999

[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. https://doi.org/10.1109/ROBOT.2003.1241945

[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. https://doi.org/10.1109/IROS.2003.1250674

[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. https://doi.org/10.1109/ROBOT.2007.363756

[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. https://doi.org/10.1109/ICRA.2016.7487258

[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. https://doi.org/10.1109/ICARA.2000.4803910

[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. https://doi.org/10.3390/agriculture11100954

[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. https://doi.org/10.1080/01691864.2015.1033461

[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. https://doi.org/10.20965/jrm.2016.p0500

[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. https://doi.org/10.20965/jrm.2023.p0262