Skip to main content
SpringerLink
Log in

A new potential field-based algorithm for path planning

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

Abstract

In this paper, the path-planning problem is considered. We introduce a new potential function for path planning that has the remarkable feature that it is free from any local minima in the free space irrespective of the number of obstacles in the configuration space. The only global minimum is the goal configuration whose region of attraction extends over the whole free space. We also propose a new method for path optimization using an expanding sphere that can be used with any potential or penalty function. Simulations using a point mobile robot and smooth obstacles are presented to demonstrate the qualities of the new potential function. Finally, practical considerations are also discussed for nonpoint robots

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. Bazaraa, M. S., Sherali, H. D. and Shetty, C. M., Nonlinear Programming: Theory and Algorithms, 2nd edn, Wiley, Singapore, 1993.

    Google Scholar 

  2. Bobrow, J. E., Optimal robot path planning using the minimum-time criterion, IEEE Trans. Robotics and Automation 4(4) (1988), 443–450.

    Google Scholar 

  3. Borenstein, J. and Koren, Y., High-speed obstacle avoidance for mobile robots, in IEEE Int. Symp. Intell. Control, 1989, pp. 382–384.

  4. Canny, J. F., The Complexity of Robot Motion Planning, ACM Doctoral Dissertation Award, MIT Press, 1987.

  5. Elnagar, A. and Basu, A., Heuristics for local path planning, IEEE Trans. Syst. Man and Cybernet. 23(2) (1993), 642–634.

    Google Scholar 

  6. Fujimaru, K. and Samet, H., A hierachical strategy for path planning among moving obstacles, IEEE Trans. Robotics and Automation 5(1) (1989), 61–69.

    Google Scholar 

  7. Gilbert, E. G. and Johnson, D. W., Distance functions and their application to robot path planning in the presence of obstacles, IEEE Trans. Robotics and Automation RA-1 (1985), 21–30.

    Google Scholar 

  8. Hirsch, M. W. and Smale, S., Differential Equations, Dynamical Systems, and Linear Algebra, Academic Press, London, 1974.

    Google Scholar 

  9. Hwang, Y. K. and Ahuja, N., A potential field approach to path planning, IEEE Trans. Robotics and Automation 8(1) (1992), 23–32.

    Google Scholar 

  10. Johnson, D. W. and Gilbert, E. G., Minimum time robot path planning in the presence of obstacles, in Proc. IEEE Conf. Decision and Control, December 1985, pp. 1748–1753.

  11. Johnson, D. W., The optimization of robot motion in the presence of obstacles, PhD Dissertation, University of Michigan, 1987.

  12. Khatib, O., Real-time obstacle avoidance for manipulators and mobile robots, Int. J. Robotics Res. 5(1) (1986), 90–98.

    Google Scholar 

  13. Khosla, P. and Volpe, R., Superquadric artificial potentials for obstacle avoidance and approach, Proc. IEEE Int. Conf. Robotics and Automation 3 (1988), 1778–1784.

    Google Scholar 

  14. Kim, B. K. and Shin, K. G., Minimum-time path planning for robot arms and their dynamics, IEEE Trans. Syst. Man and Cybernet. SMC-15(2) (1985), 213–223.

    Google Scholar 

  15. Kim, J. O. and Khosla, P. K., Real-time obstacle avoidance using harmonic potential functions, IEEE Trans. Robotics and Automation 8(3) (1992), 338–349.

    Google Scholar 

  16. Kyriakopoulos, K. J. and Saridas, G. N., An integrated collision prediction and avoidance scheme for mobile robots in non-stationary environment, Automatica 29 (1993), 309–322.

    Google Scholar 

  17. Latombe, J. C., Robot Motion Planning, Kluwer, Boston, 1991.

    Google Scholar 

  18. Lozano-Perez, T. and Wesley, M. A., An algorithm for planning collision-free paths among polyhedral obstacles, Commun. ACM 22(10) (1979), 560–570.

    Google Scholar 

  19. Lozano-Perez, T., A simple motion-planning algorithm for general robot manipulators, IEEE Trans. Robotics and Automation RA- 3(3) (1987), 224–237.

    Google Scholar 

  20. Luh, J. Y. S. and Campbell, C. E.Jr., Minimum distance collision-free path planing for industrial robots with a prismatic joint, IEEE Trans. Automatic Control AC- 29(8) (1984), 675–680.

    Google Scholar 

  21. Pavlov, V. V. and Voronin, A. N., The method of potential functions for coding constraints of the external space in an intelligent mobile robot, Sov. Automatic Control 17 (1984), 45–51.

    Google Scholar 

  22. Rimon, E. and Koditschek, D. E., Exact robot navigation using cost functions: The case of distinct spherical boundaries in E n, IEEE Int. Conf. Robotics and Automation 3 (1988), 1791–1796.

    Google Scholar 

  23. Rimon, E. and Koditschek, D. E., Exact robot navigation using artificial potential functions, IEEE Trans. Robotics and Automation 8(5) (1992), 501–518.

    Google Scholar 

  24. Schwartz, J. T. and Sharir, M., On piano movers problem 1: The case of a two-dimensional rigid polygonal body amidst polygonal barriers, Commun. Pure and Applied Math. 36 (1983), 345–398.

    Google Scholar 

  25. Shiller, Z. and Dubowsky, S., Robot path planning with obstacle, actuator, gripper and pay-load constraints, Int. J. Robotics Res. 8(6) (1989).

  26. Shiller, Z. and Gwo, Y., Dynamic motion planning of autonomous vehicles, IEEE Trans. Robotics and Automation 7(2) (1991).

  27. Shin, K. G. and McKay, N. D., Selection of near-minimum time geometric path for robotic manipulators, IEEE Trans. Automatic Control AC-31(6) (1986), 501–511.

    Google Scholar 

  28. Tilove, R. B., Local obstacle avoidance for mobile robots based on the method of artificial potential functions, in IEEE Int. Conf. Robotics and Automation, May 1990, pp. 566–571.

  29. Tournassound, P., Motion planning for a mobile robot with kinematic constraint, in IEEE Int. Conf. Robotics and Automation, 1988, pp. 1785–1790.

  30. Udupa, S. M., Collision detection and avoidance in computer controlled manipulators, Proc. 5th Int. Joint Conf. on Artificial Intell., Boston, 2 (1977), 737–748.

    Google Scholar 

  31. Volpe, R. and Khosla, P., Artificial potentials with elliptical isopotential contours for obstacle avoidance, in Proc. 26th IEEE Conf. Dec. and Control, December 1987, pp. 180–185.

  32. Wong, E. K. and Fu, K. S., A hierarchical orthogonal space approach to three-dimensional path planning, IEEE Trans. Robotics and Automation 2(1) (1986).

  33. MATLAB Optimization Toolbox Manual, MATHWORKS Inc., MA, USA, 1992.

Download references

Author information

Authors and Affiliations

  1. Department of Systems Engineering, King Fahd University of Petroleum and Minerals, 31261, Dhahran, Saudi Arabia

    K. S. Al-Sultan & M. D. S. Aliyu

Authors
  1. K. S. Al-Sultan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. D. S. Aliyu
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Al-Sultan, K.S., Aliyu, M.D.S. A new potential field-based algorithm for path planning. Journal of Intelligent and Robotic Systems 17, 265–282 (1996). https://doi.org/10.1007/BF00339664

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00339664

Key words

Search

Navigation