Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Motion planning in the presence of movable obstacles

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

Most motion planning algorithms have dealt with motion in a static workspace, or more recently, with motion in a workspace that changes in a known manner. We consider the problem of finding collision-free motions in a changeable workspace. That is, we wish to find a motion for an object where the object is permitted to move some of the obstacles. In such a workspace, the final positions of the movable obstacles may or may not be part of the goal. In the case where the final positions of the obstacles are specified, the general problem is shown to be PSPACE-hard. In the case where the final positions of the obstacles are unspecified, the motion planning problem is shown to be NP-hard. Algorithms that run inO(n 3) time are presented for the case where there is only one movable obstacle in a polygonal environment withn corners and the object to be moved and the obstacle are convex polygons of constant complexity.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. B. Aronov, S. Fortune and G. Wilfong, Minimum speed motions, Robotics Research Technical Report 163, NYU-Courant Institute (July 1988).

  2. R. Benson,Euclidean Geometry and Convexity (McGraw-Hill, 1966).

  3. J. Canny, A new algebraic method for robot motion planning and real geometry, in:Proc. 28th FOCS (1987) pp. 39–48.

  4. J. Canny, B. Donald, J. Reif and P. Xavier, On the complexity of kinodynamic planning, in:Proc. 29th FOCS (1988).

  5. J. Canny and J. Reif, New lower bound techniques for robot motion planning problems, in:Proc. 28th FOCS (1987) pp. 49–60.

  6. S. Fortune and G. Wilfong, Planning constrained motion, in:Proc. 20th Annual ACM STOC (1988) pp. 445–457.

  7. M. Garey and D. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, 1979).

    Google Scholar 

  8. J. Hopcroft, J. Schwartz and M. Sharir, On the complexity of motion planning for multiple independent objects; PSPACE hardness of the “warehouseman's problem”, Int. J. Robotics Res. 3 (4) (1984) 76–88.

    Google Scholar 

  9. K. Kant and S. Zucker, Toward efficient trajectory planning: The path-velocity decomposition, Int. J. Robotics Res. 5 (3) (1986) 72–89.

    Google Scholar 

  10. K. Kedem, R. Livne, J. Pach and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discr. Comput. Geom. 1 (1) (1986) 59–72.

    Google Scholar 

  11. T. Lozano-Pérez and M. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, CACM 22 (10) (1979) 560–570.

    Google Scholar 

  12. C. Ó'Dúnlaing, Motion planning with inertial constraints, Algorithmica 2 (4) (1987) 431–475.

    Google Scholar 

  13. J. Reif and M. Sharir, Motion planning in the presence of moving obstacles, in:Proc. 26th FOCS (1985) pp. 144–154.

  14. N. Sarnak and R. Tarjan, Planar point location using persistent search trees, CACM 29 (7) (1986) 669–679.

    Google Scholar 

  15. J. Schwartz and M. Sharir, On the piano movers' problem: II. General techniques for computing topological properties of real algebraic manifolds, Adv. Appl. Math. 4 (1983) 298–351.

    Google Scholar 

  16. J. Schwartz and M. Sharir, On the piano movers' problem: III. Coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal boundaries, Int. J. Robotics Res. 2 (3) (1983) 46–75.

    Google Scholar 

  17. R. Sedgewick,Algorithms (Addison-Wesley, Reading, MA, 1983).

    Google Scholar 

  18. M. Sharir and S. Sifrony, Coordinated motion planning for two independent robots, in:Proc. Symp. on Computational Geometry (1988).

  19. R. Tarjan and C. Van Wyck, AnO(n log logn)-time algorithm for triangulating a simple polygon, SIAM J. Comput. 17 (1988) 143–178.

    Google Scholar 

  20. C. Yap, Algorithmic motion planning, in:Advance in Robotics, Vol. 1: Algorithmic and Geometric Aspects, J. Schwartz and C. Yap (eds.) (Lawrence Erlbaum Assoc, Hillsdale, NJ, 1986).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. AT&T Bell Laboratories, 07974, Murray Hill, New Jersey, USA

    Gordon Wilfong

Authors
  1. Gordon Wilfong
    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

Wilfong, G. Motion planning in the presence of movable obstacles. Ann Math Artif Intell 3, 131–150 (1991). https://doi.org/10.1007/BF01530890

Download citation

  • Issue Date:

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

Keywords

Search

Navigation