Skip to main content
SpringerLink
Log in

PiP-X: Funnel-Based Online Feedback Motion Planning/Replanning in Dynamic Environments

  • 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

We propose an online single-query sampling-based feedback motion re-planning algorithm using finite-time invariant sets, “funnels". We combine concepts from nonlinear systems analysis, sampling-based motion planning, and graph-search methods to create a single framework that enables feedback motion planning/replanning for general nonlinear dynamical systems in a dynamic workspace. We introduce a novel graph data structure to represent a network of volumetric funnels, enabling the use of quick graph-replanning techniques. The use of incremental search techniques and a pre-computed library of motion-primitives ensure that our method can be used for quick on-the-fly rewiring of controllable motion plans in response to changes in the environment. We validate our approach on a simulated 6DOF quadrotor platform operating in a maze, and random forest environment.

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. Jaffar, M.K.M., Otte, M.: PiP-X: Online feedback motion planning/replanning in dynamic environments using invariant funnels (2022). arXiv:2202.00772

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

    Article  MATH  Google Scholar 

  3. Karaman, S., Frazzoli, E.: Optimal kinodynamic motion planning using incremental sampling-based methods. In: 49th IEEE Conference on Decision and Control (CDC), pp. 7681–7687. IEEE (2010)

    Google Scholar 

  4. Kuffner, J.J., LaValle, S.M.: RRT-connect: An efficient approach to single-query path planning. In: Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), vol. 2, pp. 995–1001. IEEE (2000)

    Google Scholar 

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

    Article  Google Scholar 

  6. LaValle, S.M., Kuffner, J.J., Jr.: Randomized kinodynamic planning. Int. J. Robot. Res. 20(5), 378–400 (2001)

    Article  Google Scholar 

  7. hwan Jeon, J., Karaman, S., Frazzoli, E.: Anytime computation of time-optimal off-road vehicle maneuvers using the RRT. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference, pp. 3276–3282. IEEE (2011)

    Google Scholar 

  8. Webb, D.J., Van Den Berg, J.: Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics. In: 2013 IEEE International Conference on Robotics and Automation, pp. 5054–5061. IEEE (2013)

    Google Scholar 

  9. Ravankar, A., Ravankar, A.A., Kobayashi, Y., Hoshino, Y., Peng, C.C.: Path smoothing techniques in robot navigation: State-of-the-art, current and future challenges. Sensors 18(9), 3170 (2018)

    Article  Google Scholar 

  10. Basescu, M., Moore, J.: Direct NMPC for post-stall motion planning with fixed-wing UAVs. In: 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 9592–9598. IEEE (2020)

    Google Scholar 

  11. Tedrake, R., Manchester, I.R., Tobenkin, M., Roberts, J.W.: LQR-trees: Feedback motion planning via sums-of-squares verification. Int. J. Robot. Res. 29(8), 1038–1052 (2010)

    Article  Google Scholar 

  12. Majumdar, A., Tedrake, R.: Funnel libraries for real-time robust feedback motion planning. Int. J. Robot. Res. 36(8), 947–982 (2017)

    Article  Google Scholar 

  13. Verginis, C.K., Dimarogonas, D.V., Kavraki, L.E.: KDF: Kinodynamic motion planning via geometric sampling-based algorithms and funnel control (2021). arXiv:2104.11917

  14. Bajcsy, A., Bansal, S., Bronstein, E., Tolani, V., Tomlin, C.J.: An efficient reachability-based framework for provably safe autonomous navigation in unknown environments. In: 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 1758–1765. IEEE (2019)

    Google Scholar 

  15. Kousik, S., Vaskov, S., Bu, F., Johnson-Roberson, M., Vasudevan, R.: Bridging the gap between safety and real-time performance in receding-horizon trajectory design for mobile robots. Int. J. Robot. Res. 39(12), 1419–1469 (2020)

    Article  Google Scholar 

  16. Herbert, S.L., Chen, M., Han, S., Bansal, S., Fisac, J.F., Tomlin, C.J.: FaSTrack: A modular framework for fast and guaranteed safe motion planning. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 1517–1522. IEEE (2017)

    Google Scholar 

  17. Singh, S., Landry, B., Majumdar, A., Slotine, J.J., Pavone, M.: Robust feedback motion planning via contraction theory. Int. J. Robot. Res. (2019)

    Google Scholar 

  18. Stentz, A., et al.: The focussed D\(^{*}\) algorithm for real-time replanning. In: IJCAI, vol. 95, pp. 1652–1659 (1995)

    Google Scholar 

  19. Koenig, S., Likhachev, M.: D\(^{*}\)Lite. Aaai/iaai 15, 476–483 (2002)

    Google Scholar 

  20. Otte, M., Frazzoli, E.: RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning. Int. J. Robot. Res. 35(7), 797–822 (2016)

    Article  Google Scholar 

  21. Tobenkin, M.M., Manchester, I.R., Tedrake, R.: Invariant funnels around trajectories using sum-of-squares programming. IFAC Proc. Vol. 44(1), 9218–9223 (2011)

    Article  Google Scholar 

  22. Frazzoli, E., Dahleh, M.A., Feron, E.: Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Trans. Robot. 21(6), 1077–1091 (2005)

    Article  Google Scholar 

  23. Majumdar, A., Tedrake, R.: Robust online motion planning with regions of finite time invariance. In: Algorithmic Foundations of Robotics X, pp. 543–558. Springer (2013)

    Google Scholar 

  24. Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30(7), 846–894 (2011)

    Article  MATH  Google Scholar 

  25. Jaffar, M.K.M., Velmurugan, M., Mohan, R.: A novel guidance algorithm and comparison of nonlinear control strategies applied to an indoor quadrotor. In: 2019 Fifth Indian Control Conference (ICC), pp. 466–471. IEEE (2019)

    Google Scholar 

  26. Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11(1–4), 625–653 (1999)

    Google Scholar 

Download references

Acknowledgements

The authors wish to thank the Robot Locomotion Group at MIT for providing an open-source software distribution for computing funnels. This work is supported by the grant N00421-21-1-0001 from Naval Air Systems Command (NAVAIR).

Author information

Authors and Affiliations

  1. University of Maryland, College Park, MD, 20742, USA

    Mohamed Khalid M Jaffar & Michael Otte

Authors
  1. Mohamed Khalid M Jaffar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Otte
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohamed Khalid M Jaffar .

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

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

Jaffar, M.K.M., Otte, M. (2023). PiP-X: Funnel-Based Online Feedback Motion Planning/Replanning in Dynamic Environments. 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_9

Download citation

Publish with us

Policies and ethics

Search

Navigation