Skip to main content
SpringerLink
Log in

Motion planning among time dependent obstacles

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

In this paper we study the problem of motion planning in the presence of time dependent, i.e. moving, obstacles. More specifically, we will consider the problem: given a bodyB and a collection of moving obstacles inD-dimensional space decide whether there is a continuous, collision-free movement ofB from a given initial position to a target position subject to the condition thatB cannot move any faster than some fixed top-speedc. As a discrete, combinatorial model for the continuous, geometric motion planning problem we introduce time-dependent graphs. It is shown that a path existence problem in time-dependent graphs is PSPACE-complete. Using this result we will demonstrate that a version of the motion planning problem (where the obstacles are allowed to move periodically) is PSPACE-hard, even ifD=2, B is a square and the obstacles have only translational movement. ForD=1 it is shown that motion planning is NP-hard. Furthermore we introduce the notion of thec-hull of an obstacle: thec-hull is the collection of all positions in space-time at which a future collision with an obstacle cannot be avoided. In the low-dimensional situationD=1 andD=2 we develop polynomial-time algorithms for the computation of thec-hull as well as for the motion planning problem in the special case where the obstacles are polyhedral. In particular forD=1 there is aO(n lgn) time algorithm for the motion planning problem wheren is the number of edges of the obstacle.

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

  • [DS] Dunford, N., Schwartz, J.: Linear operators, Part I: General theory. New York: J. Wiley & Sons, 1964.

    Google Scholar 

  • [GH] Guibas, L., Hershberger, J.: Computing the visibility graph ofn line segments inO(n2) time. Bull. EATCS26, 13–19 (1985).

    Google Scholar 

  • [HJW] Hopcroft, J., Joseph, D., Whitesides, S.: On the movement of robot arms in 2-dimensional bounded regions. SIAM J. Comput..14, 315–333 (1985).

    Article  MATH  MathSciNet  Google Scholar 

  • [HSS] Hopcroft, J.E., Schwartz, J.T., Sharir, M.: On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the “warehouseman’s problem”. Int. J. Robot. Res..3(4), 76–88 (1984).

    Article  Google Scholar 

  • [K] Kirkpatrick, D.G.: Efficient computations of continuous skeletons. Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, 1979, pp. 18–27. IEEE Press, New York

    Google Scholar 

  • [LPW] Lozano-Perez, T., Wesley, M.: An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM, 560–570 (1979)

  • [PS] Preparata, F.P., Shamos, M.I.: Computational geometry. Berlin Heidelberg New York: Springer 1985.

    Google Scholar 

  • [R] Reif, J.: Complexity of the mover’s problem and generalizations. Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, 1979, pp. 421–427. IEEE Press, New York.

    Google Scholar 

  • [RS] Reif, J., Sharir, M.: Motion planning in the presence of moving obstacles. Harvard University, TR-06-85

  • [SS1] Schwartz, J.T., Sharir, M.: On the piano mover’s problem. I. The special case of a rigid polygonal body moving amidst polygonal barriers. Commun. Pure Appl. Math..36, 345–398 (1983).

    Article  MATH  MathSciNet  Google Scholar 

  • [SS2] Schwartz, J.T., Sharir, M.: On the piano mover’s problem. II. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math..4, 298–351 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  • [SS3] Schwartz, J.T., Sharir, M.: On the piano mover’s problem. III. Coordinating the motion of the several independent bodies: the special case of circular bodies moving among polygonal barriers. Int. J. Robot. Res..2(3), 46–75 (1983)

    Article  MathSciNet  Google Scholar 

  • [SY] Spirakis, P., Yap, C.: Strong NP-hardness of moving many disks Inform. Process. Lett.19, 55–59 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  • [Y] Yap, C.: Coordinating the motion of several disks. TR-105-84, Courant Institute of Math. Sciences, New York University, February 1985.

Download references

Author information

Authors and Affiliations

  1. Stevens Institute of Technology, 07030, Hoboken, NJ, USA

    K. Sutner

  2. University of Illinois at Chicago, 60638, Chicago, IL, USA

    W. Maass

Authors
  1. K. Sutner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. W. Maass
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

During the preparation of this paper the second author has been supported in part by NSF grant DCR-85-04247

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sutner, K., Maass, W. Motion planning among time dependent obstacles. Acta Informatica 26, 93–122 (1988). https://doi.org/10.1007/BF02915447

Download citation

  • Received:

  • Issue Date:

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

Keywords

Search

Navigation