Article

Free access

On the complexity of reachability and motion planning questions (extended abstract)

Authors:

Deborah A. Joseph,

W. Harry PlantingsAuthors Info & Claims

SCG '85: Proceedings of the first annual symposium on Computational geometry

Pages 62 - 66

https://doi.org/10.1145/323233.323242

Published: 01 June 1985 Publication History

PDF eReader

Abstract

In this paper we consider from a theoretical viewpoint the complexity of some reachability and motion planning questions. Specifically, we are interested in determining which generalizations of the basic mover's problem result in computationally intractable problems. It has been shown that for any set of motion-planning problems with bounded degree of freedom, there is a polynomial-time algorithm to solve the motion-planning problem (although the degree of the polynomial may be large), but the two most basic generalizations to the problem, multiple movable obstacles and conformable objects, result in much harder problems. It has been shown that the warehouseman's problem is P-space hard: in this paper we show that the reachability problem for one of the simplest types of conformable objects, a two-dimensional linear (“robot arm”) linkage, is P-space complete. In addition, we demonstrate some motion-planning problems that take exponential time.

References

[1]

1. Howden, W. E., "The Sofa Problem," Comput J. 11 pp. 299- 301 (1968).

Crossref

Google Scholar

[2]

2. Lozano-Perez, T. and M. A. Wesley, "An algorithm for planning collision-free paths among polyhedral obstacles," Comm. ACM 22 pp. 560-570 (October 1979).

Digital Library

Google Scholar

[3]

3. Reif, J. H., "Complexity of the Mover's Problem and Generalizations (Extended Abstract)." Proc. 20th IEEE FOCS. pp. 421- 427 (1979).

Google Scholar

[4]

4. Brooks, R. A., "Planning collision-free motion for pick-and place operations." The International Journal of Research 2(4) (1983).

Google Scholar

[5]

5. Schwartz, J. T. and M. Sharir. "On the 'Piano Movers' Problem - II. General Techniques for Computing Topological Properties of Real Algebraic Manifolds," Advances in Applied Math. 4 pp. 298-351 (1983).

Digital Library

Google Scholar

[6]

6. Hopcroft, J. E., J. T. Schwartz. and M. Sharir. "On the complexity of motion planning for multiple independent objects: Pspace hardness of the "Warehouseman's problem"," Preprint (1983).

Google Scholar

[7]

7. Hopcroft, J. E., D. A. Joseph. and S. H. Whitesides. "On the movement of robot arms in 2-dimensional bounded regions." Siam J. Comput. 14(2)(May, 1985).

Crossref

Google Scholar

[8]

8. Hopcroft, J. E., D. A. Joseph, and S. H. Whitesides. "Movement problems for 2-dimensional linkages." SIAM J. Comput. 13(3)(1984).

Digital Library

Google Scholar

[9]

9. Karp. R. M., "Reducibility among combinatorial problems." pp. 85-103 in Complexity of Computer Computations. ed. R. Miller, J. Thatcher. Plenum Press. New York (1972).

Google Scholar

Cited By

View all

Ho MFarid AMajumdar A(2022)Towards a Framework for Comparing the Complexity of Robotic TasksAlgorithmic Foundations of Robotics XV10.1007/978-3-031-21090-7_17(273-293)Online publication date: 15-Dec-2022
https://doi.org/10.1007/978-3-031-21090-7_17
Van Rooij I(2010)The Tractable Cognition ThesisCognitive Science10.1080/0364021080189785632:6(939-984)Online publication date: 10-Feb-2010
https://doi.org/10.1080/03640210801897856
Whitesides SPei N(2005)On the reconfiguration of chainsComputing and Combinatorics10.1007/3-540-61332-3_172(381-390)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-61332-3_172
Show More Cited By

Index Terms

On the complexity of reachability and motion planning questions (extended abstract)
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        Motion capture
    2. Planning and scheduling
  2. Computer graphics
    1. Animation
      1. Motion capture
      2. Motion processing
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

The Complexity of Fine Motion Planning
Arithmetic Circuit Complexity \& Motion Planning
On the hardness of unlabeled multi-robot motion planning

In unlabeled multi-robot motion planning, several interchangeable robots operate in a common workspace. The goal is to move the robots to a set of target positions such that each position will be occupied by some robot. In this paper, we study this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '85: Proceedings of the first annual symposium on Computational geometry

June 1985

322 pages

ISBN:0897911636

DOI:10.1145/323233

Chairman:
Joseph O'Rourke
Johns Hopkins Univ., Baltimore, MD

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCG85

Sponsor:

SCG85: The 1st Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry 1985

June 5 - 7, 1985

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
371
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)10

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ho MFarid AMajumdar A(2022)Towards a Framework for Comparing the Complexity of Robotic TasksAlgorithmic Foundations of Robotics XV10.1007/978-3-031-21090-7_17(273-293)Online publication date: 15-Dec-2022
https://doi.org/10.1007/978-3-031-21090-7_17
Van Rooij I(2010)The Tractable Cognition ThesisCognitive Science10.1080/0364021080189785632:6(939-984)Online publication date: 10-Feb-2010
https://doi.org/10.1080/03640210801897856
Whitesides SPei N(2005)On the reconfiguration of chainsComputing and Combinatorics10.1007/3-540-61332-3_172(381-390)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-61332-3_172
Abramowski SMüller H(2005)Searching connected components in very large grid graphsGraph-Theoretic Concepts in Computer Science10.1007/3-540-17218-1_54(118-130)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-17218-1_54
Alt HKnauer CRote GWhitesides SFortune S(2003)The complexity of (un)foldingProceedings of the nineteenth annual symposium on Computational geometry10.1145/777792.777818(164-170)Online publication date: 8-Jun-2003
https://dl.acm.org/doi/10.1145/777792.777818
Pujol FGarcía Chamizo JFuster APujol MRizo R(2002)Use of mathematical morphology in real‐time path planningKybernetes10.1108/0368492021041379131:1(115-123)Online publication date: 1-Feb-2002
https://doi.org/10.1108/03684920210413791
Mohades ARazzazi M(2001)Reachability on a region bounded by two attached squaresComputational Science — ICCS 200110.1007/3-540-45545-0_88(763-771)Online publication date: 17-Jul-2001
https://doi.org/10.1007/3-540-45545-0_88
Streinu I(2000)A combinatorial approach to planar non-colliding robot arm motion planningProceedings 41st Annual Symposium on Foundations of Computer Science10.1109/SFCS.2000.892132(443-453)Online publication date: 2000
https://doi.org/10.1109/SFCS.2000.892132
Valero FMata VCeccarelli M(2000)Path Planning in Complex Environments for Industrial Robots with Additional Degrees of FreedomRomansy 1310.1007/978-3-7091-2498-7_46(431-438)Online publication date: 2000
https://doi.org/10.1007/978-3-7091-2498-7_46
Hsu DLatombe JMotwani RKavraki L(1999)Capturing the Connectivity of High-Dimensional Geometric Spaces by Parallelizable Random Sampling TechniquesAdvances in Randomized Parallel Computing10.1007/978-1-4613-3282-4_8(159-182)Online publication date: 1999
https://doi.org/10.1007/978-1-4613-3282-4_8
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

The Complexity of Fine Motion Planning

Arithmetic Circuit Complexity \& Motion Planning

On the hardness of unlabeled multi-robot motion planning