Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Exponential Convergence of Infeasibility Proofs for Kinematic Motion Planning

  • Conference paper
  • First Online:
Algorithmic Foundations of Robotics XV (WAFR 2022)

Part of the book series: Springer Proceedings in Advanced Robotics ((SPAR,volume 25))

Included in the following conference series:

Abstract

Proving motion planning infeasibility is an important part of a complete motion planner. Common approaches for high-dimensional motion planning are only probabilistically complete. Previously, we presented an algorithm to construct infeasibility proofs by applying machine learning to sampled configurations from a bidirectional sampling-based planner. In this work, we prove that the learned manifold converges to an infeasibility proof exponentially. Combining prior approaches for sampling-based planning and our converging infeasibility proofs, we propose the term asymptotic completeness to describe the property of returning a plan or infeasibility proof in the limit. We compare the empirical convergence of different sampling strategies to validate our analysis.

This work is supported in part by the National Science Foundation under Grant No. IIS-1849348.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 229.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 299.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 299.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Amato, N.M., Wu, Y.: A randomized roadmap method for path and manipulation planning. In: ICRA. vol. 1, pp. 113–120. IEEE (1996)

    Google Scholar 

  2. Basch, J., Guibas, L.J., Hsu, D., Nguyen, A.T.: Disconnection proofs for motion planning. In: ICRA. vol. 2, pp. 1765–1772. IEEE (2001)

    Google Scholar 

  3. Ben-Shahar, O., Rivlin, E.: Practical pushing planning for rearrangement tasks. T-RO 14(4), 549–565 (1998)

    Google Scholar 

  4. Berenson, D., Srinivasa, S.S., Ferguson, D., Kuffner, J.J.: Manipulation planning on constraint manifolds. In: ICRA

    Google Scholar 

  5. Boissonnat, J.D., Chazal, F., Yvinec, M.: Geometric and Topological Inference. Cambridge Texts in Applied Mathematics. Cambridge University Press (2018). https://hal.inria.fr/hal-01615863

  6. Boissonnat, J.D., Ghosh, A.: Manifold reconstruction using tangential Delaunay complexes. Discret. Comput. Geom. 51(1), 221–267 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  7. Boor, V., Overmars, M.H., Van Der Stappen, A.F.: The Gaussian sampling strategy for probabilistic roadmap planners. In: RSS. vol. 2, pp. 1018–1023. IEEE (1999)

    Google Scholar 

  8. Branicky, M.S., LaValle, S.M., Olson, K., Yang, L.: Quasi-randomized path planning. In: ICRA, vol. 2, pp. 1481–1487. IEEE (2001)

    Google Scholar 

  9. Cambon, S., Alami, R., Gravot, F.: A hybrid approach to intricate motion, manipulation and task planning. IJRR 28(1), 104–126 (2009)

    Google Scholar 

  10. Canny, J.: Computing roadmaps of general semi-algebraic sets. Comput. J. 36(5), 504–514 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chazelle, B.: Approximation and decomposition of shapes. Algorithm. Geom. Aspects of Robot. 1, 145–185 (1985)

    Google Scholar 

  12. Şucan, I.A., Moll, M., Kavraki, L.E.: The open motion planning library. RAM 19(4), 72–82 (2012)

    Google Scholar 

  13. Şucan, I.A., Kavraki, L.E.: A sampling-based tree planner for systems with complex dynamics. T-RO 28(1), 116–131 (2012). http://dx.doi.org/10.1109/tro.2011.2160466

  14. Dantam, N.T.: Task and Motion Planning. Springer, Berlin, Heidelberg (2020)

    Google Scholar 

  15. Dantam, N.T., Kingston, Z.K., Chaudhuri, S., Kavraki, L.E.: An incremental constraint-based framework for task and motion planning. IJRR 37(10), 1134–1151 (2018)

    Google Scholar 

  16. Dobson, A., Bekris, K.E.: Sparse roadmap spanners for asymptotically near-optimal motion planning. IJRR 33(1), 18–47 (2014)

    Google Scholar 

  17. Donald, B., Xavier, P., Canny, J., Reif, J.: Kinodynamic motion planning. JACM 40(5), 1048–1066 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  18. Garrett, C.R., Chitnis, R., Holladay, R., Kim, B., Silver, T., Kaelbling, L.P., Lozano-Pérez, T.: Integrated task and motion planning. Ann. Rev. control, Robot. Autonom. Syst. 4, 265–293 (2021)

    Article  Google Scholar 

  19. Hsu, D., Kindel, R., Latombe, J.C., Rock, S.: Randomized kinodynamic motion planning with moving obstacles. IJRR 21(3), 233–255 (2002)

    MATH  Google Scholar 

  20. Janson, L., Ichter, B., Pavone, M.: Deterministic sampling-based motion planning: optimality, complexity, and performance. IJRR 37(1), 46–61 (2018)

    Google Scholar 

  21. Janson, L., Schmerling, E., Clark, A., Pavone, M.: Fast marching tree: a fast marching sampling-based method for optimal motion planning in many dimensions. IJRR 34(7), 883–921 (2015)

    Google Scholar 

  22. Kalakrishnan, M., Chitta, S., Theodorou, E., Pastor, P., Schaal, S.: STOMP: stochastic trajectory optimization for motion planning. In: ICRA, pp. 4569–4574. IEEE (2011)

    Google Scholar 

  23. Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. IJRR 30(7), 846–894 (2011)

    MATH  Google Scholar 

  24. Kavraki, L.E., Kolountzakis, M.N., Latombe, J.C.: Analysis of probabilistic roadmaps for path planning. T-RO 14(1), 166–171 (1998)

    Google Scholar 

  25. Kavraki, L.E., Latombe, J.C., Motwani, R., Raghavan, P.: Randomized query processing in robot path planning. JCSS 57(1), 50–60 (1998)

    MathSciNet  MATH  Google Scholar 

  26. Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. T-RO 12(4), 566–580 (1996)

    Google Scholar 

  27. Kingston, Z., Moll, M., Kavraki, L.E.: Exploring implicit spaces for constrained sampling-based planning. IJRR 38(10–11), 1151–1178 (2019)

    Google Scholar 

  28. Kuffner, J.J., LaValle, S.M.: RRT-connect: an efficient approach to single-query path planning. In: ICRA, vol. 2, pp. 995–1001. IEEE (2000)

    Google Scholar 

  29. Ladd, A.M., Kavraki, L.E.: Fast tree-based exploration of state space for robots with dynamics. In: Algorithmic Foundations of Robotics VI, pp. 297–312. Springer (2004)

    Google Scholar 

  30. Lafferriere, G., Sussmann, H.: Motion planning for controllable systems without drift. In: ICRA, pp. 1148–1149. IEEE Computer Society (1991)

    Google Scholar 

  31. LaValle, S.M.: Rapidly-exploring random trees: a new tool for path planning. Technical Report TR-98-11, Computer Science Department, Iowa State University (1998)

    Google Scholar 

  32. LaValle, S.M.: Planning Algorithms. Cambridge University Press (2006)

    Google Scholar 

  33. LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. IJRR 20(5), 378–400 (2001)

    Google Scholar 

  34. Li, S., Dantam, N.T.: Learning proofs of motion planning infeasibility. In: RSS (2021)

    Google Scholar 

  35. Li, Y., Littlefield, Z., Bekris, K.E.: Asymptotically optimal sampling-based kinodynamic planning. IJRR 35(5), 528–564 (2016)

    Google Scholar 

  36. Makino, H.: Assembly robot (1982), US Patent 4,341,502

    Google Scholar 

  37. McCarthy, Z., Bretl, T., Hutchinson, S.: Proving path non-existence using sampling and alpha shapes. In: ICRA, pp. 2563–2569. IEEE (2012)

    Google Scholar 

  38. Mukadam, M., Dong, J., Yan, X., Dellaert, F., Boots, B.: Continuous-time Gaussian process motion planning via probabilistic inference. IJRR 37(11), 1319–1340 (2018)

    Google Scholar 

  39. Murray, S., Floyd-Jones, W., Qi, Y., Sorin, D.J., Konidaris, G.D.: Robot motion planning on a chip. In: RSS (2016)

    Google Scholar 

  40. Orthey, A., Toussaint, M.: Sparse multilevel roadmaps for high-dimensional robotic motion planning. In: ICRA, pp. 7851–7857 (2021)

    Google Scholar 

  41. Ota, J.: Rearrangement of multiple movable objects-integration of global and local planning methodology. In: ICRA, vol. 2, pp. 1962–1967. IEEE (2004)

    Google Scholar 

  42. Otte, M., Frazzoli, E.: RRTX: asymptotically optimal single-query sampling-based motion planning with quick replanning. IJRR 35(7), 797–822 (2016)

    Google Scholar 

  43. Plaku, E., Bekris, K.E., Chen, B.Y., Ladd, A.M., Kavraki, L.E.: Sampling-based roadmap of trees for parallel motion planning. T-RO 21(4), 597–608 (2005)

    Google Scholar 

  44. Schulman, J., Duan, Y., Ho, J., Lee, A., Awwal, I., Bradlow, H., Pan, J., Patil, S., Goldberg, K., Abbeel, P.: Motion planning with sequential convex optimization and convex collision checking. IJRR 33(9), 1251–1270 (2014)

    Google Scholar 

  45. Siméon, T., Laumond, J.P., Nissoux, C.: Visibility-based probabilistic roadmaps for motion planning. Adv. Robot. 14(6), 477–493 (2000)

    Article  Google Scholar 

  46. Varava, A., Carvalho, J.F., Pokorny, F.T., Kragic, D.: Caging and path non-existence: a deterministic sampling-based verification algorithm. In: Robotics Research, pp. 589–604. Springer (2020)

    Google Scholar 

  47. Zhang, L., Kim, Y.J., Manocha, D.: A hybrid approach for complete motion planning. In: IROS, pp. 7–14. IEEE/RSJ (2007)

    Google Scholar 

  48. Zhang, L., Kim, Y.J., Manocha, D.: A simple path non-existence algorithm using c-obstacle query. In: Algorithmic Foundation of Robotics VII, pp. 269–284. Springer (2008)

    Google Scholar 

  49. Zucker, M., Ratliff, N., Dragan, A.D., Pivtoraiko, M., Klingensmith, M., Dellin, C.M., Bagnell, J.A., Srinivasa, S.S.: CHOMP: covariant Hamiltonian optimization for motion planning. IJRR 32(9–10), 1164–1193 (2013)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Colorado School of Mines, Golden, CO, USA

    Sihui Li & Neil T. Dantam

Authors
  1. Sihui Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Neil T. Dantam
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sihui Li .

Editor information

Editors and Affiliations

  1. Center for Ubiquitous Computing, University of Oulu, Oulu, Finland

    Steven M. LaValle

  2. Department of Computer Science and Engineering, Texas A&M University, College Station, TX, USA

    Jason M. O’Kane

  3. Department of Aerospace Engineering, University of Maryland, College Park, MD, USA

    Michael Otte

  4. Gates Computer Science, Stanford University, Stanford, CA, USA

    Dorsa Sadigh

  5. Department of Computer Science, University of Maryland, College Park, MD, USA

    Pratap Tokekar

A Appendix: Comparing PRM and RRT-Connect

A Appendix: Comparing PRM and RRT-Connect

Below is an example comparing PRM and RRT-connect in a 2D configuration space with disconnected \(\mathcal {C}_{\textrm{rest}}\) regions. PRM’s samples form two classes, the samples connectable to the goal configuration, and the samples not connectable to the goal configuration. RRT-connect’s samples also form two classes, the start tree samples and the goal tree samples. The example configuration space’s \(\mathcal {C}_{\textrm{rest}}\) in Fig. 6 has two disconnected components, the region outside of obstacle region 1, and the region in between obstacle region 1 and 2. PRM samples all \(\mathcal {C}_{\textrm{free}}\), so with disconnected \(\mathcal {C}_{\textrm{rest}}\), the trained manifold is in \(\mathcal {C}_{\textrm{obs}}\) (Fig. 6a). RRT-connect samples are connected to either the start configuration or the goal configuration, which is nor guaranteed to cover the entire \(\mathcal {C}_{\textrm{free}}\) if there are disconnected regions, thus the learned manifold may not converge into \(\mathcal {C}_{\textrm{obs}}\) (Fig. 6b). In our proof, if \(\mathcal {C}_{\textrm{rest}}\) has disconnected regions, then we need to use PRM planner. If \(\mathcal {C}_{\textrm{rest}}\) is connected, then PRM and RRT-connect are the same.

Fig. 6.
figure 6

Comparing PRM and RRT-connect in disconnected \(\mathcal {C}_{\textrm{rest}}\) configuration space. Manifold trained from PRM samples are guaranteed to converge, while manifold trained from RRT-connect samples may not converge. For this reason, we switch to use PRM for the proofs in this paper to cover the general case.

Full size image

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Li, S., Dantam, N.T. (2023). Exponential Convergence of Infeasibility Proofs for Kinematic Motion Planning. In: LaValle, S.M., O’Kane, J.M., Otte, M., Sadigh, D., Tokekar, P. (eds) Algorithmic Foundations of Robotics XV. WAFR 2022. Springer Proceedings in Advanced Robotics, vol 25. Springer, Cham. https://doi.org/10.1007/978-3-031-21090-7_18

Download citation

Publish with us

Policies and ethics

Search

Navigation