The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
New lower bound techniques for robot motion planning problems
Abstract
We present new techniques for establishing lower bounds in robot motion planning problems. Our scheme is based on path encoding and uses homotopy equivalence classes of paths to encode state. We first apply the method to the shortest path problem in 3 dimensions. The problem is to find the shortest path under an Lp metric (e.g. a euclidean metric) between two points amid polyhedral obstacles. Although this problem has been extensively studied, there were no previously known lower bounds. We show that there may be exponentially many shortest path classes in single-source multiple-destination problems, and that the single-source single-destination problem is NP-hard. We use a similar proof technique to show that two dimensional dynamic motion planning with bounded velocity is NP-hard. Finally we extend the technique to compliant motion planning with uncertainty in control. Specifically, we consider a point in 3 dimensions which is commanded to move in a straight line, but whose actual motion may differ from the commanded motion, possibly involving sliding against obstacles. Given that the point initially lies in some start region, the problem of finding a sequence of commanded velocities which is guaranteed to move the point to the goal is shown to be non-deterministic exponential time hard, making it the first provably intractable problem in robotics.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
An algorithm for planning collision-free paths among polyhedral obstacles
Lozano-Pérez, T., & Wesley, M. A. (1979) · Communications of the ACM · doi:10.1145/359156.359164 · Cited by 2,304
Spatial Planning: A Configuration Space Approach
Lozano-Perez (1983) · IEEE Transactions on Computers · doi:10.1109/tc.1983.1676196 · Cited by 2,113
Compliance and Force Control for Computer Controlled Manipulators
Mason, M. T. (1981) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1981.4308708 · Cited by 1,542
Automatic Synthesis of Fine-Motion Strategies for Robots
Lozano-Pérez, T., Mason, M. T., & Taylor, R. H. (1984) · The International Journal of Robotics Research · doi:10.1177/027836498400300101 · Cited by 898
Schwartz, J. T., & Sharir, M. (1983) · Advances in Applied Mathematics · doi:10.1016/0196-8858(83)90014-3 · Cited by 801
Complexity of the mover's problem and generalizations
Reif, J. H. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.10 · Cited by 765
Self-citationHopcroft, J. E., Schwartz, J. T., & Sharir, M. (1984) · The International Journal of Robotics Research · doi:10.1177/027836498400300405 · Cited by 528
The complexity of elementary algebra and geometry
Ben-Or, M., Kozen, D. C., & Reif, J. H. (1986) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(86)90029-2 · Cited by 222
Self-citationPlanning, geometry, and complexity of robot motion
Schwartz, J. T., Sharir, M., & Hopcroft, J. E. (1986) · Cited by 217
Cited by
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Sampling-based algorithms for optimal motion planning
Karaman, S., & Frazzoli, E. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364911406761 · Cited by 5,275
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
Paden, B., Cap, M., Yong, S. Z., Yershov, D., & Frazzoli, E. (2016) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2016.2578706 · Cited by 2,585
Motion Planning in Dynamic Environments Using Velocity Obstacles
Fiorini, P., & Shiller, Z. (1998) · The International Journal of Robotics Research · doi:10.1177/027836499801700706 · Cited by 2,008
Gross motion planning—a survey
Hwang, Y. K., & Ahuja, N. (1992) · ACM Computing Surveys · doi:10.1145/136035.136037 · Cited by 826
Donald, B., Xavier, P., Canny, J., & Reif, J. (1993) · Journal of the ACM · doi:10.1145/174147.174150 · Cited by 458
Self-citationCooperative UAV Formation Flying With Obstacle/Collision Avoidance
Wang, X., Yadav, V., & Balakrishnan, S. N. (2007) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2007.899191 · Cited by 452
Orienting polygonal parts without sensors
Goldberg, K. Y. (1993) · Algorithmica · doi:10.1007/bf01891840 · Cited by 437
Geometric Shortest Paths and Network Optimization
Mitchell, J. S. B. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50016-4 · Cited by 427
Optimal path planning of mobile robots: A review
Raja, P. (2012) · International Journal of the Physical Sciences · doi:10.5897/ijps11.1745 · Cited by 404
Efficient algorithms for geometric optimization
Agarwal, P. K., & Sharir, M. (1998) · ACM Computing Surveys · doi:10.1145/299917.299918 · Cited by 257
Morales, E. F., Murrieta-Cid, R., Becerra, I., & Esquivel-Basaldua, M. A. (2021) · Intelligent Service Robotics · doi:10.1007/s11370-021-00398-z · Cited by 101
COMPUTATIONAL GEOMETRY COLUMN 35
O'ROURKE, J. (1999) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195999000297 · Cited by 9
Metadata
- Authors
- Canny, J., & Reif, J.
- Venue
- 28th Annual Symposium on Foundations of Computer Science (sfcs 1987)
- Publisher
- IEEE
- Published
- 1987-10
- Pages
- 49-60
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2170220350
- Cited by
- 538
- References
- 14
- FWCI
- 35.21
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.