Sensor-Based Motion Planning for a Car-like Robot Based On Bug Family Algorithms

Authors: Dong-Hyung Kim, Ji Yeong Lee, Chang-Soo Han

Abstract:

This paper presents a sensor-based motion planning algorithm for 3-DOF car-like robots with a nonholonomic constraint. Similar to the classic Bug family algorithms, the proposed algorithm enables the car-like robot to navigate in a completely unknown environment using only the range sensor information. The car-like robot uses the local range sensor view to determine the local path so that it moves towards the goal. To guarantee that the robot can approach the goal, the two modes of motion are repeated, termed motion-to-goal and wall-following. The motion-to-goal behavior lets the robot directly move toward the goal, and the wall-following behavior makes the robot circumnavigate the obstacle boundary until it meets the leaving condition. For each behavior, the nonholonomic motion for the car-like robot is planned in terms of the instantaneous turning radius. The proposed algorithm is implemented to the real robot and the experimental results show the performance of proposed algorithm.

Keywords: Motion planning, car-like robot, bug algorithm, autonomous motion planning, nonholonomic constraint.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084950

References:

[1] V. J. Lumelsky and A. Stepanov, "Path planning strategies for point automaton moving amidst unknown obstacles of arbitrary shape,"Algorithmica,vol. 2, pp.403-430, 1987.
[2] I. Kamon, E. Rimon and E. Rivlin, "Tangentbug: A range-sensor based navigation algorithm," Int. J. Robot. Res., vol. 17, p.934-953, 1998.
[3] S. Laubach and J. Burdick, "An autonomous sensor-based path planner for planetary microrovers," in Proc. IEEE ICRA, Detroit, MI, 1999, pp. 347-354.
[4] E. Magid and E. Rivlin, "CAUTIOUSBUG: A competitive algorithm for sensory-based robot navigation," in Proc. IEEE/RSJ Int. Conf. IROS, Sendai, Japan, Oct. 2004, pp. 2757-2762.
[5] Y. Gabriely and E. Rimon, "CBUG: A Quadratically Competitive Mobile Robot Navigation Algorithm," IEEE Trans. Robot., vol. 24, no. 6, pp. 1451-1457, Dec. 2008.
[6] F. Mastrogiovanni, A. Sgorbissa, and R. Zaccaria, "Robust Navigation in an Unknown Environment with Minimal Sensing and Representation," IEEE Trans.on Systems, Man, and CyberneticsÔÇöPart B: Cybernetics, vol. 39, no. 1, Feb. 2009.
[7] J. Minguez and L. Montano, "Extending Collision Avoidance Methods to Consider the Vehicle Shape, Kinematics, and Dynamics of a Mobile Robot," IEEE Trans. Robot., vol. 25, no. 2, pp. 367-381, Apr. 2009.
[8] F. Lamiraux, D. Bonnafous, and O. Lefebvre, "Reactive Path Deformation for Nonholonomic Mobile Robots," IEEE Trans. Robot., vol. 20, no. 6, pp. 967-977, Dec. 2004.
[9] K.Nagatani, Y. Iwai, and Y. Tanaka, "Sensor-based navigation for car-like mobile robots based on a generalized Voronoi graph," Advanced Robotics, vol. 17, no. 5, pp. 385-401, 2003.
[10] C. Lanzoni and A. Sanchez, "Sensor-based motion planning for car-like mobile robots in unknown environments," in Proc. IEEE ICRA, Taipei, Taiwan, Sep.2003,pp. 4258-4263.
[11] A. Ollero and G. Heredia, "Stability Analysis of Mobile Robot Path Tracking," in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., Pittsburgh, PA, 1995, vol. 3, pp. 461-466.
[12] Thomas Hellström, Ola Ringdahl, "Follow the past - a path tracking algorithm for autonomous vehicles", in Int. J. Vehicle Autonomous Systems, vol. 4, pp. 216-224, 2006.