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

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.

• Dong-Hyung Kim
• Ji Yeong Lee
• Chang-Soo Han

• Motion planning
• car-like robot
• bug algorithm
• autonomous motion planning
• nonholonomic constraint.

[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.