» Download Article

Authors
Kristijan Macek; Roland Siegwart

Identifier
10.3182/20060906-3-IT-2910.00108

Index Terms
No keywords available

Abstract
This paper addresses the problem of path planning of mobile robots in dynamic environments. A collision-free trajectory of the robot is generated in the presence of moving obstacles that is three times differentiable and enables direct derivation of kinematic level controls for the robot. A chained form decomposition and state transformation for a geometric and time criterion of collision avoidance is based on an approach where closed-form solution is found for a polynomial family of curves based on only one adjustable parameter for collision avoidance. However, the sensitivity of the parameter is considerable and can induce trajectories with large detours from the goal direction. Therefore, a family of curves based on B-splines is introduced here that enables better local curve shape control. Relative obstacles to robot movement determines the prohibited regions in the transformed space. Thereafter, a collision-free path is found by a line-segment expansion from the transformed start and goal configuration based on Rapidly-exploring Random Trees. Thus obtained path is further approximated by a B-spline curve resulting in the final smooth trajectory.

References

[1] de Boor, C. (2001). A practical guide to splines.
    Applied mathematical sciences 27. Springer.
[2] Erdmann, M. and T. Lozano-Perez (1986). On
    multiple moving objects. In: Proc. IEEE Int.
    Conf. Robotics and Automation. San Francisco,
     CA. pp. 1419-1424.
[3] Fiorini, P. and Z. Shiller (1998). Motion planning
    in dynamic environments using velocity obstacles.
     Int. J. Robot. Res. 17, 760-772.
[4] Fraichard, T. (1993). Dynamic trajectory planning
     with dynamic constraints: a state-time
    approach. In: IEEE/RSJ Int. Conf. on Intell.
    Robots and Sys.. pp. 1393-1400.
[5] Hsu, D., R. Kindel, J.-C. Latombe and S. Rock
    (2002). Randomized kinodynamic motion
    planning with moving obstacles. Int. J.
    Robot. Res. 21, 233-255.
[6] Jing, Xing-Jian (2005). Behavior dynamics based
    motion planning of mobile robots in uncertain
     dynamic environments. Robotics and autonomous
     systems 53, 99-123.
[7] Kant, K. and S. W. Zucker (1988). Planning collision
     free trajectories in time-varying environment:
     A two level hierarchy. In: Proc. IEEE
    Int. Conf. Robotics and Automation. Raleigh,
    NC. pp. 1644-1649.
[8] Laumond, J. P. (1998). Robot motion planning
    and control. Lecture notes in control and
    information sciences 229. Springer.
[9] LaValle, S. M. and J. J. Kuffner (2001). Algorithmic
     and Computational Robotics: New Directions
    . Chap. Rapidly-exploring random trees:
    Progress and prospects, pp. 293-308. Wellesley,
     MA.
[10] Qu, Z., J. Wang and C. E. Plaisted (2004). A new
     analytical solution to mobile robot trajectory
     generation in the presence of moving obstacles.
      IEEE Transactions on Robotics 20, 978-
     993.
[11] Shiller, Z., F. Large and S. Sekhavat (2001). Motion
      planning in dynamic environments: Obstacles
      moving along arbitrary trajectories.
     In: Proc. IEEE Int. Conf. Robotics and Automation
     . Seoul, Korea. pp. 3716-3721.