A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space. (English) Zbl 0643.68049

Sifrony, S.; Sharir, M.

Algorithmica 2, 367-402 (1987).

We present here a new and efficient algorithm for planning collision-free motion of a line segment (a rod or a “ladder”) in two-dimensional space amidst polygonal obstacles. The algorithm uses a different approach than those used in previous motion-planning techniques, namely, it calculates the boundary of the (three-dimensional) space of free positions of the ladder, and then uses this boundary for determining the existence of required motions, and plans such motions whenever possible. The algorithm runs in time O(K log n)\(=O(n^ 2 \log n)\) where n is the number of obstacle corners and where K is the total number of pairs of obstacle walls or corners of distance less than or equal to the length of the ladder. The algorithm has thus the same complexity as the best previously known algorithm of D. Leven and the second author [J. Algorithms 8, 192-215 (1987; see the following review)], but if the obstacles are not too cluttered together it will run much more efficiently. The algorithm also serves as an initial demonstration of the viability of the technique it uses, which we expect to be useful in obtaining efficient motion- planning algorithms for other more complex robot systems.

MSC:

68Q25	Analysis of algorithms and problem complexity
52-04	Software, source code, etc. for problems pertaining to convex and discrete geometry

Keywords:

robotics; computational geometry; configuration space; ladder; polygonal obstacles; motion-planning

Citations:

Zbl 0643.68050

References:

[1]	Bentley, J. L.; Ottman, A., Algorithm for reporting and counting geometric intersections, IEEE Trans. Comput., 28, 643-647 (1979) · Zbl 0414.68074 · doi:10.1109/TC.1979.1675432
[2]	J. E. Hopcroft and G. Wilfong, On the motion of objects in contact, Technical Report 84-602, Computer Science Department, Cornell University, 1984.
[3]	K. Kedem and M. Sharir, Efficient algorithm for planning translational collision-free motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles,Proceedings of the ACM Symposium on Computational Geometry, 1985, pp. 75-80.
[4]	Kedem, K.; Livne, R.; Pach, J.; Sharir, M., On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete Comput. Geom., 1, 59-71 (1986) · Zbl 0594.52004 · doi:10.1007/BF02187683
[5]	D. Leven and M. Sharir, An efficient and simple motion-planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers,Proceedings of the ACM Symposium on Computational Geometry, 1985, pp. 221-227 (also to appear inJ. Algorithms.)
[6]	Leven, D.; Sharir, M., Planning a purely translational motion of a convex object in two-dimensional space using generalized Voronoi diagrams, Discrete Comput. Geom., 2, 9-31 (1987) · Zbl 0606.52002 · doi:10.1007/BF02187867
[7]	Moise, E. E., Geometric Topology in Dimension 2and 3 (1977), New York: Springer-Verlag, New York · Zbl 0349.57001
[8]	O’Dunlaing, C.; Sharir, M.; Yap, C., Generalized Voronoi diagrams for a ladder: I. Topological considerations, Comm. Pure Appl. Math., 39, 423-483 (1986) · Zbl 0601.51025 · doi:10.1002/cpa.3160390402
[9]	O’Dunlaing, C.; Yap, C., A retraction method for planning the motion of a disc, J. Algorithms, 6, 104-11 (1985) · Zbl 0556.68051 · doi:10.1016/0196-6774(85)90021-5
[10]	O’Dunlaing, C.; Sharir, M.; Yap, C., Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram, Algorithmica, 2, 27-59 (1987) · Zbl 0631.68042 · doi:10.1007/BF01840348
[11]	J. O’Rourke, Lower bounds on moving a ladder, Technical Report, Department of EECS, Johns Hopkins University, 1985.
[12]	Schwartz, J. T.; Sharir, M., On the piano movers’ problem: I. The case of a rigid polygonal body moving amidst polygonal barriers, Comm. Pure Appl. Math., 36, 345-398 (1983) · Zbl 0554.51007 · doi:10.1002/cpa.3160360305
[13]	Schwartz, J. T.; Sharir, M., On the piano movers’ problem: II. General techniques for computing topological properties of real algebraic manifolds, Adv. in Appl. Math., 4, 298-351 (1983) · Zbl 0554.51008 · doi:10.1016/0196-8858(83)90014-3
[14]	Schwartz, J. T.; Sharir, M., On the piano movers’ problem: III. Coordinating the motion of several independent bodies: the special case of circular bodies moving amidst polygonal barriers, Robotics Res., 2, 46-75 (1983) · Zbl 0592.51011 · doi:10.1177/027836498300200304
[15]	Schwartz, J. T.; Sharir, M., On the piano movers’ problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles, Comm. Pure Appl. Math., 37, 815-848 (1984) · Zbl 0554.51009 · doi:10.1002/cpa.3160370605
[16]	J. T. Schwartz and M. Sharir, Efficient motion planning algorithms in environments of bounded local complexity, Technical Report, Computer Science Department, Courant Institute, 1985.
[17]	Sharir, M.; Ariel-Sheffi, E., On the piano movers’ problem: IV. Various decomposable two-dimensional motion-planning problems, Comm. Pure Appl. Math., 37, 479-493 (1984) · Zbl 0592.51012 · doi:10.1002/cpa.3160370406
[18]	C. K. Yap, Coordinating the motion of several discs, Technical Report 105, Computer Science Department, Courant Institute, 1984.