The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Complexity of the mover's problem and generalizations
Open accessAbstract
This paper concerns the problem of moving a polyhedron through Euclidean space while avoiding polyhedral obstacles.
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
Relationships between nondeterministic and deterministic tape complexities
Savitch, W. J. (1970) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(70)80006-x · Cited by 1,366
A Mobile Automaton: An Application of Artificial Intelligence Techniques
Nilsson, N. J. (1969) · doi:10.21236/ada459660 · Cited by 552
Modelling, Trajectory Calculation and Servoing of a Computer Controlled Arm
Paul, R. (1972) · Defense Technical Information Center (DTIC) · doi:10.21236/ad0785071 · Cited by 362
Topics in Computational Geometry
Zolnowsky, J. (2018) · doi:10.2172/1453953 · Cited by 14
Cited by
RRT-connect: An efficient approach to single-query path planning
Kuffner, J. J., & LaValle, S. M. (2000) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844730 · Cited by 3,555
Randomized Kinodynamic Planning
LaValle, S. M., & Kuffner, J. J. (2001) · The International Journal of Robotics Research · doi:10.1177/02783640122067453 · Cited by 3,254
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
The thermodynamics of computation—a review
Bennett, C. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02084158 · Cited by 2,006
Learning metric-topological maps for indoor mobile robot navigation
Thrun, S. (1998) · Artificial Intelligence · doi:10.1016/s0004-3702(97)00078-7 · Cited by 1,042
Robot Motion Planning: A Distributed Representation Approach
Barraquand, J., & Latombe, J.-C. (1991) · The International Journal of Robotics Research · doi:10.1177/027836499101000604 · Cited by 995
Anytime Motion Planning using the RRT*
Karaman, S., Walter, M. R., Perez, A., Frazzoli, E., & Teller, S. (2011) · 2011 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2011.5980479 · Cited by 881
Experiences with an interactive museum tour-guide robot
Burgard, W., Cremers, A. B., Fox, D., Hähnel, D., Lakemeyer, G., Schulz, D., Steiner, W., & Thrun, S. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00070-3 · Cited by 818
Schwartz, J. T., & Sharir, M. (1983) · Advances in Applied Mathematics · doi:10.1016/0196-8858(83)90014-3 · Cited by 801
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
Sampling-Based Robot Motion Planning: A Review
Elbanhawi, M., & Simic, M. (2014) · IEEE Access · doi:10.1109/access.2014.2302442 · Cited by 786
Randomized Kinodynamic Motion Planning with Moving Obstacles
Hsu, D., Kindel, R., Latombe, J.-C., & Rock, S. (2002) · The International Journal of Robotics Research · doi:10.1177/027836402320556421 · Cited by 771
Toward Efficient Trajectory Planning: The Path-Velocity Decomposition
Kant, K., & Zucker, S. W. (1986) · The International Journal of Robotics Research · doi:10.1177/027836498600500304 · Cited by 753
Lumelsky, V. J., & Stepanov, A. A. (1987) · Algorithmica · doi:10.1007/bf01840369 · Cited by 699
Incremental Sampling-based Algorithms for Optimal Motion Planning
Karaman, S., & Frazzoli, E. (2010) · Robotics: Science and Systems VI · doi:10.15607/rss.2010.vi.034 · Cited by 680
Randomized kinodynamic planning
LaValle, S. M., & Kuffner, J. J. (2003) · Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C) · doi:10.1109/robot.1999.770022 · Cited by 673
Perception, Planning, Control, and Coordination for Autonomous Vehicles
Pendleton, S., Andersen, H., Du, X., Shen, X., Meghjani, M., Eng, Y., Rus, D., & Ang, M. (2017) · Machines · doi:10.3390/machines5010006 · Cited by 657
Survey of Deep Reinforcement Learning for Motion Planning of Autonomous Vehicles
Aradi, S. (2022) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2020.3024655 · Cited by 639
A Catalog of Complexity Classes
JOHNSON, D. S. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50007-2 · Cited by 556
Path planning in expansive configuration spaces
Hsu, D., Latombe, J.-C., & Motwani, R. (2002) · Proceedings of International Conference on Robotics and Automation · doi:10.1109/robot.1997.619371 · Cited by 552
New lower bound techniques for robot motion planning problems
Canny, J., & Reif, J. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.42 · Cited by 538
Self-citationProbabilistic Algorithms and the Interactive Museum Tour-Guide Robot Minerva
Thrun, S., Beetz, M., Bennewitz, M., Burgard, W., Cremers, A. B., Dellaert, F., Fox, D., Hähnel, D., Rosenberg, C., Roy, N., et al. (2000) · The International Journal of Robotics Research · doi:10.1177/02783640022067922 · Cited by 516
Schwartz, J. T., & Sharir, M. (1983) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.3160360305 · Cited by 454
Orienting polygonal parts without sensors
Goldberg, K. Y. (1993) · Algorithmica · doi:10.1007/bf01891840 · Cited by 437
Optimal kinodynamic motion planning using incremental sampling-based methods
Karaman, S., & Frazzoli, E. (2010) · 49th IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2010.5717430 · Cited by 416
Polack, P., Altche, F., d'Andrea-Novel, B., & de La Fortelle, A. (2017) · 2017 IEEE Intelligent Vehicles Symposium (IV) · doi:10.1109/ivs.2017.7995816 · Cited by 408
A “retraction” method for planning the motion of a disc
Ó'Dúnlaing, C., & Yap, C. K. (1985) · Journal of Algorithms · doi:10.1016/0196-6774(85)90021-5 · Cited by 404
Differentially constrained mobile robot motion planning in state lattices
Pivtoraiko, M., Knepper, R. A., & Kelly, A. (2009) · Journal of Field Robotics · doi:10.1002/rob.20285 · Cited by 393
Dynamic path planning for a mobile automaton with limited information on the environment
Lumelsky, V., & Stepanov, A. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104175 · Cited by 388
Euclidean shortest paths in the presence of rectilinear barriers
Lee, D. T., & Preparata, F. P. (1984) · Networks · doi:10.1002/net.3230140304 · Cited by 387
The bridge test for sampling narrow passages with probabilistic roadmap planners
Hsu, D., Jiang, T., Reif, J., & Sun, Z. (2004) · 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422) · doi:10.1109/robot.2003.1242285 · Cited by 355
Self-citationMoore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Exact robot navigation by means of potential functions: Some topological considerations
Koditschek, D. (2005) · Proceedings. 1987 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1987.1088038 · Cited by 345
Sampling-based robotic information gathering algorithms
Hollinger, G. A., & Sukhatme, G. S. (2014) · The International Journal of Robotics Research · doi:10.1177/0278364914533443 · Cited by 334
Robust hybrid control for autonomous vehicle motion planning
Frazzoli, E., Dahleh, M. A., & Feron, E. (2002) · Proceedings of the 39th IEEE Conference on Decision and Control (Cat. No.00CH37187) · doi:10.1109/cdc.2000.912871 · Cited by 297
A Random Sampling Scheme for Path Planning
Barraquand, J., Kavraki, L., Latombe, J.-C., Motwani, R., Li, T.-Y., & Raghavan, P. (1997) · The International Journal of Robotics Research · doi:10.1177/027836499701600604 · Cited by 277
Dynamically-Stable Motion Planning for Humanoid Robots
Kuffner, J. J., Kagami, S., Nishiwaki, K., Inaba, M., & Inoue, H. (2002) · Autonomous Robots · doi:10.1023/a:1013219111657 · Cited by 265
Motion Planning: A Journey of Robots, Molecules, Digital Actors, and Other Artifacts
Latombe, J.-C. (1999) · The International Journal of Robotics Research · doi:10.1177/02783649922067753 · Cited by 264
Motions in Microseconds via Vectorized Sampling-Based Planning
Thomason, W., Kingston, Z., & Kavraki, L. E. (2024) · 2024 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra57147.2024.10611190 · Cited by 28
Metadata
- Authors
- Reif, J. H.
- Venue
- 20th Annual Symposium on Foundations of Computer Science (sfcs 1979)
- Publisher
- IEEE
- Published
- 1979-10
- Pages
- 421-427
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2042106485
- Cited by
- 765
- References
- 4
- FWCI
- 1.38
- Type
- conference paper
- Language
- en
- Open access
- green
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.