Skip to main content
SpringerLink
Log in

Fast Path Re-planning Based on Fast Marching and Level Sets

  • Published:
Journal of Intelligent & Robotic Systems Aims and scope Submit manuscript

Abstract

We investigate path planning algorithms that are based on level set methods for applications in which the environment is static, but where an a priori map is inaccurate and the environment is sensed in real-time. Our principal contribution is not a new path planning algorithm, but rather a formal analysis of path planning algorithms based on level set methods. Computational costs when planning paths with level set methods are due to the creation of the level set function. Once the level set function has been computed, the optimal path is simply gradient descent down the level set function. Our approach rests on the formal analysis of how value of the level set function changes when the changes in the environment are detected. We show that in many practical cases, only a small domain of the level set function needs to be re-computed when the environment changes. Simulation examples are presented to validate the effectiveness of the proposed method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alton, K., Mitchell, I.M.: Optimal path planning under different norms continuous state spaces. In: Proc. of IEEE International Conf. on Robotics and Automation, pp. 866–872 (2006)

  2. Choi, W., Zhu, D., Latombe, J.C.: Contingency-tolerant robot motion planning and control. In: Proc. of IEEE/RSJ International Workshop on Intelligent Robots and Systems, pp. 78–86 (1989)

  3. Cohen, L.D., Kimmel, R.: Global minimum for active contours models: a minimal path approach. Int. J. Comput. Vis. 24(1), 57–78 (1997)

    Article  Google Scholar 

  4. Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (1989)

    Google Scholar 

  5. Elfes, A.: Using occupancy grids for mobile robot perception and navigation. Computer 22(6), 46–57 (1989)

    Article  Google Scholar 

  6. Ferguson, D., Likhachev, M., Stentz, A.: A guide to heuristic path planning. In: Proc. of the International Workshop on Planning under Uncertainty for Autonomous Systems, International Conference on Automated Planning and Scheduling (2005)

  7. Hassouna, M.S., Abdel-Hakim, A.E., Farag, A.A.: Robust robotic path planning using level sets. In: Proc. of IEEE International Conf. on Image Processing, vol. 3, pp. 473–476 (2005)

  8. Khatib, M., Jaouni, H., Chatila, R., Laumond, J.P.: Dynamic path modification for car-like nonholonomic mobile robots. In: Proc. of IEEE International Conf. on Robotics and Automation, pp. 2920–2925 (1997)

  9. Kimmel, R., Sethian, J.A.: Optimal algorithm for shape from shading and path planning. J. Math. Imaging Vis. 14, 237–244 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  10. Kimmel, R., Amir, A., Bruckstein, A.M.: Finding shortest paths on surfaces using level set methods. IEEE Trans. Pattern Anal. Mach. Intell. 17(6), 635–640 (1995)

    Article  Google Scholar 

  11. Koenig, S., Likhachev, M.: Improved fast replanning for robot navigation in unknown terrain. Technical Report GIT-COGSCI-2002/3, College of Computing, Georgia Institute of Technology, Atlanta, GA (2002)

  12. Krogh, B.H., Thrope, C.E.: Integrated path planning and dynamic steering control for autonomous vehicles. In: Proc. of IEEE International Conf. on Robotics and Automation, pp. 1664–1669 (1986)

  13. Lamiraux, F., Bonnafous, D., Lefebvre, O.: Reactive path deformation for nonholonomic mobile robots. IEEE Trans. Robot. 2(6), 967–977 (2004)

    Article  Google Scholar 

  14. Latombe, J.C.: Robot Motion Planning. Kluwer Academic, Norwell (1991)

    Book  Google Scholar 

  15. LaValle, S.: Planning Algorithms. Cambridge University Press, Cambridge (2006)

    Book  MATH  Google Scholar 

  16. Lions, P.L.: Generalized Solutions of Hamilton–Jacobi Solutions. Pitman, New York (1982)

    MATH  Google Scholar 

  17. Mitchell, I.M., Sastry, S.: Continuous path planning with multiple constraints. In: Proc. of the 42nd IEEE Conf. on Decision and Control, pp. 5502–5507 (2003)

  18. Osher, S.J., Sethian, J.A.: Fronts propagating with curvature dependent speed: algorithms based on Hamilton–Jacobi formulations. J. Comput. Phys. 79, 12–49 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  19. Petres, C., Pailhas, Y., Patron, P., Petillot, Y., Evans, J., Lane, D.: Path planning for autonomous underwater vehicles. IEEE Trans. Robot. 23(2), 331–341 (2007)

    Article  Google Scholar 

  20. Phillippsen, R.: A light formulation of the E* interpolated path replanner. Technical Report, Autonomous Systems Lab, Ecole Polytechnique Federale de Lausanne, Switzerland (2006)

  21. Quinlan, S., Khatib, O.: Elastic bands: connecting path planning and control. In: Proc. of IEEE International Conf. on Robotics and Automation, pp. 802–807 (1993)

  22. Rouy, E., Tourin, A.: A viscosity solutions approach to shape-from-shading. SIAM J. Numer. Anal. 29(3), 867–884 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Sethian, J.A.: Fast marching method. SIAM Rev. 41(2), 199–235 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  24. Sun, X., Yeoh, W., Koenig, S.: Dynamic fringe-saving A*. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 891–898 (2009)

  25. Tsitsiklis, J.N.: Efficient algorithm for globally optimal trajectories. IEEE Trans. Automat. Contr. 40(9), 1528–1538 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  26. Xu, B., Stilwell, D.J., Kurdila, A.J.: Efficient computation of level sets for path planning. In: IEEE/RSJ International Conf. on Intelligent Robots and Systems (2009)

Download references

Author information

Authors and Affiliations

  1. The Bradley Department of Electrical and Computer Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA, 24061, USA

    Bin Xu & Daniel J. Stilwell

  2. The Department of Mechanical Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA, 24061, USA

    Andrew J. Kurdila

Authors
  1. Bin Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel J. Stilwell
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andrew J. Kurdila
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel J. Stilwell.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xu, B., Stilwell, D.J. & Kurdila, A.J. Fast Path Re-planning Based on Fast Marching and Level Sets. J Intell Robot Syst 71, 303–317 (2013). https://doi.org/10.1007/s10846-012-9794-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10846-012-9794-2

Keywords

Search

Navigation