Minimum-Speed Motions

Abstract

We consider the problem of determining how fast an object must be capable of moving for it to be able to reach a given position at a given time while avoiding moving obstacles. The problem is to plan velocity profile along a given path so that collisions with moving obstacles crossing the path are avoided and the maximum velocity along the path is mini mized. Suppose the time-varying environment is fully speci fied, both in space and in time, by n linear constraints. An algorithm is presented that, given a full description of the environment and the initial configuration of the system (that is, initial position and starting time of the object), answers in O(log n) time queries of the form : "What is the lowest speed limit that the object can obey while still being able to reach the query configuration from the initial configuration without colliding with the obstacles?" The algorithm can also be used to compute a motion from the initial configuration to the query configuration that obeys the speed limit in O (n) time. The algorithm requires O(n log n) preprocessing time and O (n) space.

Get full access to this article

View all access options for this article.

References

Asano, T. , Guibas, L.J. , Hershberger, J. , and Imai, H. 1986. Visibility of disjoint polygons. Algorithmica 1(1):49-63.

Canny, J.F. 1987. The Complexity of Robot Motion Planning. Cambridge, Mass.: MIT Press.

Canny, J.F. , Donald, B.R. , Reif, J.H. , Xavier, P. 1988. On the complexity of kinodynamic planning, 29th Annual Symp. on Foundations of Computer Science, pp. 306-316. Los Alamitos, CA: IEEE Computer Society Press.

Canny, J.F. , and Reif, J.H. 1987. New lower bound techniques for robot motion planning problems . 28th Annual Symp. on Foundations of Computer Science, pp. 49-60. Los Alamitos, CA: IEEE Computer Society Press.

Edelsbrunner, H. 1987. Algorithms in Combinatorial Geometry, Heidelberg: Springer-Verlag.

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

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

Kapoor, S. , and Maheshwani, S.N. 1988. Efficient algorithms for euclidean shortest path and visibility problems with polygonal obstacles. Proc. 4th ACM Syp. on Computational Geometry, pp. 172-182. New York, NY:ACM Press.

Ó'Dúnlaing, C. 1987. Motion planning with inertial constraints. Algorithmica 2(4):431-476.

10.

Reif, J.H. , and Sharir, M. 1985. Motion planning in the presence of moving obstacles . Proc. 26th Annual Symp. on Foundations of Computer Science, pp. 144-154. Los Alamitos, CA: IEEE Computer Society Press.

11.

Sarnak, N. , and Tarjan, R.E. 1986. Planar point location using persistent search trees . Comm. Assoc. Comp. Mach. 29(7):669-679.

12.

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

13.

Yap, C.K. 1987. Algorithmic motion planning. In Schwartz, J. T. , and Yap, C. K. (eds.): Advances in Robotics, Volume 1: Algorithmic and Geometric Aspects of Robotic. Hills-dale, N.J.: Lawrence Erlbaum Assoc., pp. 95-144.