×

On the general motion-planning problem with two degrees of freedom. (English) Zbl 0685.68049

The problem of motion planning for two-degree-of-freedom systems is considered when obstacles to be avoided are bounded in configuration space by an arrangement of simple Jordan arcs. The existence of the continuous motion path connecting given initial and final configuration in a cluttered workspace is the issue, then the motion planning problem is considered. As a collision-free motion exists iff the initial and final configuration belongs to the same connected component of the so called free configuration space the attention is focussed on topological, combinatorial and algorithmic issues involving single face problem for an arrangement of Jordan curves. An upper bound for the time- and space- complexity of the algorithm is given in terms of the number of collision constraints and the maximum algebraic degree of these constraints (the algorithm is supposed to solve the problem of finding a collison-free path). Davenport-Schinzel sequences are used to establish the complexity measure. Although the upper bounds for the computations cost are not very restrictive given a 2 d.o.f. system and quite reallistically modelled obstacles boundaries, it is claimed that the extension of the approach to the 3 d.o.f. case is not straightforward nor simple. Included proofs are of constructive nature. The whole work can be viewed as the generalisation of the earlier studies single face problem for an arrangement of line segments.
Reviewer: A.Kasinski

MSC:

68Q25 Analysis of algorithms and problem complexity
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
52A37 Other problems of combinatorial convexity
05B30 Other designs, configurations
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] P. Agarwal, M. Sharir, and P. Shor, Sharp upper and lower bounds for the length of general Davenport-Schinzel sequences, Tech. Rept. 332, Comput. Science Dept., Courant Institute, New York, 1987. (To appear inJ. Combin. Theory Ser. A.) · Zbl 0697.05003
[2] P. Agarwal and M. Sharir, Red-blue intersection detection algorithms, with applications to motion planning and collision detection,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 70-80.
[3] B. Aronov and M. Sharir, Triangles in space, or: Building (and analyzing) castles in the air,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 381-391. (Also to appear inCombinatorica.) · Zbl 0717.68099
[4] M. Atallah, Dynamic computational geometry,Proc. 24th IEEE Symp. on Foundations of Computer Science, 1983, pp. 92-99. Also inComput. Math. Appl.11 (1985), pp. 1171-1181. · Zbl 0586.68085
[5] J. L. Bentley and T. Ottmann, Algorithm for reporting and counting geometric intersections,IEEE Trans. Comput.28 (1979), pp. 643-647. · Zbl 0414.68074 · doi:10.1109/TC.1979.1675432
[6] B. Bhattacharya and J. Zorbas, Solving the two-dimensional findpath problem using a line-triangle representation of the robot,J. Algorithms9 (1988), pp. 449-469. · Zbl 0662.68119 · doi:10.1016/0196-6774(88)90012-0
[7] B. Chazelle and H. Edelsbrunner, An optimal algorithm for intersecting line segments in the plane,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 590-600. · Zbl 0799.68191
[8] B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Proc. 1st ACM Symp. on Computational Geometry, 1985, pp. 135-146. · Zbl 0695.68033
[9] K. Clarkson, Applications of random sampling in computational geometry, II,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 1-11.
[10] K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 568-579. · Zbl 0704.51003
[11] H. Edelsbrunner and L. Guibas, Topologically sweeping an arrangement,Proc. 18th ACM Symposium on Theory of Computing, 1986, pp. 389-403. · Zbl 0676.68013
[12] H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl, Implicitly representing arrangements of lines or segments,Discrete Comput. Geom. (1989), this issue, pp. 433-436. · Zbl 0688.68031
[13] H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink, On arrangements of Jordan arcs with three intersections per pair,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 258-265. · Zbl 0687.05004
[14] H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, Arrangements of arcs in the plane: Topology, combinatorics, and algorithms,Proc. 15th Int. Colloq. on Automata, Languages and Programming, 1988, pp. 214-229. · Zbl 0649.68040
[15] H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity of many faces in arrangements of lines or of segments,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 44-55. · Zbl 0691.68035
[16] H. Edelsbrunner and M. Sharir, The maximum number of ways to stabn disjoint convex sets in the plane is 2n−2, Tech. Rept. 281, Comput. Sci. Dept., Courant Institute, New York, 1987 (to appear inDiscrete Comput. Geom.).
[17] S. Fortune, G. Wilfong, and C. Yap, Coordinated motion of two robot arms,Proc. IEEE Conf. on Robotics and Automation, 1986, pp. 1216-1223.
[18] S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica6 (1986), pp. 151-177. · Zbl 0636.05003 · doi:10.1007/BF02579170
[19] R. Hartshorne,Algebraic Geometry, Springer-Verlag, New York, 1977. · Zbl 0367.14001 · doi:10.1007/978-1-4757-3849-0
[20] 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,Proc. 1st ACM Symp. on Computational Geometry, 1985, pp. 75-80.
[21] K. Kedem and M. Sharir, An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space, to appear inDiscrete Comput. Geom. · Zbl 0688.68039
[22] K. Kedem, R. Livne, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles,Discrete Comput. Geom.1 (1986), pp. 59-71. · Zbl 0594.52004 · doi:10.1007/BF02187683
[23] D. Leven and M. Sharir, An efficient and simple motion-planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers,J. Algorithms8 (1987), pp. 192-215. · Zbl 0643.68050 · doi:10.1016/0196-6774(87)90038-1
[24] D. Leven and M. Sharir, Planning a purely translational motion of a convex object in two-dimensional space using generalized Voronoi diagrams,Discrete Comput. Geom.2 (1987), pp. 9-31. · Zbl 0606.52002 · doi:10.1007/BF02187867
[25] K. Mulmuley, A fast planar partition algorithm, I,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 590-600.
[26] K. Mulmuley, A fast planar partition algorithm, II,Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 33-43.
[27] C. Ó’Dúnlaing, M. Sharir, and C. Yap, Generalized Voronoi diagrams for a ladder: I. Topological considerations,Comm. Pure Appl. Math.39 (1986), pp. 423-483. · Zbl 0601.51025 · doi:10.1002/cpa.3160390402
[28] C. Ó’Dúnlaing, M. Sharir, and C. Yap, Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram,Algorithmica2 (1987), pp. 29-57.
[29] C. Ó’Dúnlaing and C. Yap, A “retraction” method for planning the motion of a disc,J. Algorithms6 (1985), pp. 104-111. · Zbl 0556.68051 · doi:10.1016/0196-6774(85)90021-5
[30] J. Pach and M. Sharir, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: combinatorial analysis,Discrete Comput. Geom.4 (1989), pp. 291-309. · Zbl 0734.05054 · doi:10.1007/BF02187732
[31] R. Pollack, M. Sharir, and S. Sifrony, Separating two simple polygons by a sequence of translations,Discrete Comput. Geom.3 (1988), pp. 123-136. · Zbl 0646.68052 · doi:10.1007/BF02187902
[32] J. T. Schwartz and M. Sharir, On the piano movers’ problem: I. The case of a rigid polygonal body moving amidst polygonal barriers,Comm. Pure Appl. Math.36 (1983), pp. 345-398. · Zbl 0554.51007 · doi:10.1002/cpa.3160360305
[33] J. T. Schwartz and M. Sharir, On the piano movers’ problem: II. General techniques for calculating topological properties of real algebraic manifolds,Adv. in Appl. Math.4 (1983), pp. 298-351. · Zbl 0554.51008 · doi:10.1016/0196-8858(83)90014-3
[34] J. T. 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 barriers,Internat. J. Robotics Res.2 (1983) (3), pp. 46-75. · Zbl 0592.51011 · doi:10.1177/027836498300200304
[35] J. T. Schwartz and M. Sharir, On the piano movers’ problem: V. The case of a rod moving in 3-D space amidst polyhedral obstacles,Comm. Pure Appl. Math.37 (1984), pp. 815-848. · Zbl 0554.51009 · doi:10.1002/cpa.3160370605
[36] J. T. Schwartz and M. Sharir, On the two-dimensional Davenport-Schinzel problem, Tech. Rept. 193 (revised), Comput. Sci. Dept., Courant Institute, New York, 1987. (To appear inJ. Symbolic Computation.)
[37] M. Sharir and E. Ariel-Sheffi, On the piano movers’ problem: IV. Various decomposable two-dimensional motion-planning problems,Comm. Pure Appl. Math.37 (1984), pp. 479-493. · Zbl 0592.51012 · doi:10.1002/cpa.3160370406
[38] M. Sharir and S. Sifrony, Coordinated motion planning for two independent robots,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 319-328. · Zbl 0875.68438
[39] P. Shor, Geometric realizations of superlinear Davenport-Schinzel sequences, in preparation.
[40] S. Sifrony, Efficient algorithms for motion-planning problems in robotics, Ph.D. Dissertation, Tel Aviv University, 1989.
[41] S. Sifrony, Efficient algorithms for motion planning of certain spatial 3-DOF manipulator arms, manuscript, 1989.
[42] S. Sifrony and M. Sharir, A new efficient motion-planning algorithm for a rod in 2-D polygonal space,Algorithmica2 (1987), pp. 367-402. · Zbl 0643.68049 · doi:10.1007/BF01840368
[43] A. Wiernik and M. Sharir, Planar realization of nonlinear Davenport-Schinzel sequences by segments,Discrete Comput. Geom.3 (1988), pp. 15-47. · Zbl 0636.68043 · doi:10.1007/BF02187894
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.