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

A Probabilistically Robust Path Planning Algorithm for UAVs Using Rapidly-Exploring Random Trees

  • Published:
Journal of Intelligent & Robotic Systems Aims and scope Submit manuscript

Abstract

The computationally efficient search for robust feasible paths for unmanned aerial vehicles (UAVs) in the presence of uncertainty is a challenging and interesting area of research. In uncertain environments, a “conservative” planner may be required but then there may be no feasible solution. In this paper, we use a chance constraint to limit the probability of constraint violation and extend this framework to handle uncertain dynamic obstacles. The approach requires the satisfaction of probabilistic constraints at each time step in order to guarantee probabilistic feasibility. The rapidly-exploring random tree (RRT) algorithm, which enjoys the computational benefits of a sampling-based algorithm, is used to develop a real-time probabilistically robust path planner. It incorporates the chance constraint framework to account for uncertainty within the formulation and includes a number of heuristics to improve the algorithm’s performance. Simulation results demonstrate that the proposed algorithm can be used for efficient identification and execution of probabilistically safe paths in real-time.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Atkinson, K.E.: An Introduction to Numerical Analysis. John (2001)

  2. Barr, N.M., Gangsaas, D., Schaeffer, D.R.: Wind models for flight simulator certification of landing and approach guidance and control system. Paper FAA-RD-74-206 (1974)

  3. Blackmore, L.: A probabilistic particle control approach to optimal, robust predictive control. In: Proceedings of the AIAA Guidance, Navigation and Control Conference (2006)

  4. Blackmore, L.: Convex chance constrained predictive control without sampling. Technical Report, NASA Jet Propulsion Laboratory (2008)

  5. Blackmore, L., Li, H., Williams, B.: A probabilistic approach to optimal robust path planning with obstacles. In: Proceedings of the IEEE American Control Conference (2006)

  6. Blackmore, L., Ono, M.: Convex chance constrained predictive control without sampling. In: Proceedings of the AIAA Guidance, Navigation and Control Conference (2009)

  7. Blackmore, L., Ono, M., Bektassov, A., Williams, B.: A probabilistic particle-control approximation of chance-constrained stochastic predictive control. IEEE Trans. Robot. 26(3) (2010)

  8. Blackmore, L., Ono, M., Williams, B.: Chance-constrained optimal path planning with obstalces. IEEE Trans. Robot. 27(6) (2011)

  9. Burns, B., Brock, O.: Sampling-based motion planning with sensing uncertainty. In: Proc. IEEE Int Robotics and Automation Conf., pp. 3313–3318 (2007)

  10. Foka, A., Trahanias, P.: Real-time hierararchical POMDPs for autonomous robot navigation. Robot. Auton. Syst. 55, 561–571 (2007)

    Article  Google Scholar 

  11. Frazzoli, E., Dahleh, M.A., Feron, E.: Real-time motion planning for agile autonomous vehicles. AIAA J. Guid. Control Dyn. 25(1), 116–129 (2002)

    Article  Google Scholar 

  12. Fulgenzi, C., Tay, C., Spalanzani, A., Laugier, C.: Probabilistic navigation in dynamic environment using rapidly-exploring random trees and gaussian processes. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (2008)

  13. Fulgenzi, C., Tay, C., Spalanzani, A., Laugier, C.: Probabilistic navigation in dynamic environment using rapidly-exploring random trees and Gaussian processes. In: Proceedings of the IEEE International Conference on Intelligent Robots and Systems, pp. 1056–1062. Nice, France (2008)

    Google Scholar 

  14. Gossner, J.R., Kouvaritakis, B., Rossiter, J.A.: Stable generalized predictive control with constraints and bounded disturbances. Automatica 33(4), 551–568 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  15. Greytak, M., Hover, F.: Motion planning with an analytic risk cost for holonomic vehicles. In: Proc. 48th IEEE Conf. Held Jointly with the 2009 28th Chinese Control Conf Decision and Control CDC/CCC 2009, pp. 5655–5660 (2009)

  16. Guibas, L.J., Hsu, D., Kurniawati, H., Rehman, E.: Bounded uncertainty roadmaps for path planning. In: Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (2008)

  17. Kewlani, G., Ishigami, G., Iagnemma, K.: Stochastic mobility-based path planning in uncertain environments. In: Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems IROS 2009, pp. 1183–1189 (2009)

  18. Kothari, M., Postlethwaite, I., Gu, D.-W.: Multi-UAV path planning in obstalce rich environments using rapidly-exploring random trees. In: Proceeding of the 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference (2009)

  19. Kuwata, Y., Richards, A., How, J.: Robust receding horizon control using generalized constraint tightening. In: Proceedings of the IEEE American Control Conference, pp. 4482–4487. New York (2007)

  20. Kuwata, Y., Teo, J., Fiore, G., Karaman, S., Frazzoli, E., How, J.P.: Real-time motion planning with applications to autonomous urban driving. IEEE Trans. Control Syst. Technol. 17(5), 1105–1118 (2009)

    Article  Google Scholar 

  21. Latombe, J.-C.: Robot Motion Planning. Kluwer, Boston (1991)

    Book  Google Scholar 

  22. LaValle, S.M.: Rapidly-exploring random trees: a new tool for path planning. Technical Report 98–11, Iowa State University (1998)

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

    Book  MATH  Google Scholar 

  24. LaValle, S.M., Sharma, R.: On motion planning in changing, partially-predictable environments. Int. J. Rob. Res. 16(6), 775–824 (1995)

    Article  Google Scholar 

  25. Leonard, J., How, J., Teller, S., Berger, M., Campbell, S., Fiore, G., Fletcher, L., Frazzoli, E., Huang, A., Karaman, S., Koch, O., Kuwata, Y., Moore, D., Olson, E., Peters, S., Teo, J., Truax, R., Walter, M., Barrett, D., Epstein, A., Maheloni, K., Moyer, K., Jones, T., Buckley, R., Antone, M., Galejs, R., Krishnamurthy, S., Williams, J.: A perception-driven autonomous urban vehicle. JFR 25(10), 727–774 (2008)

    Google Scholar 

  26. Li, P., Wendt, M., Wozny, G.: A probabilistically constrained model predictive next term controller. Automatica 38(7), 1171–1176 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  27. Luders, B., Kothari, M., How, J.P.: Chance constrained RRT for probabilistic robustness to environmental uncertainty. In: Proceeding of the AIAA Guidance, Navigation, and Control Conference and Exhibit (2010)

  28. Melchior, N.A., Simmons, R.: Particle RRT for path planning with uncertainty. In: Proceedings of the IEEE International Conference on Robotics and Automation (2007)

  29. Miralles, A.S., Bobi, M.A.S.: Global path planning in Gaussian probabilistic maps. J. Intell. Robot. Syst. 40, 89–102 (2004)

    Article  Google Scholar 

  30. Missiuro, P.E., Roy, N.: Adapting probabilistic roadmaps to handle uncertain maps. In: Proc. IEEE Int. Conf. Robotics and Automation ICRA 2006, pp. 1261–1267 (2006)

  31. Ono, M., Williams, B.C.: An efficent motion planning algorithm for stochastic dynamic system with constraints on probability of failure. In: Proceeding of the 23th AAAI Conference on Artifical Intelligence (2008)

  32. Pepy, R., Lambert, A.: Safe path planning in an uncertain-configuration space using RRT. In: Proc. IEEE/RSJ Int Intelligent Robots and Systems Conf, pp. 5376–5381 (2006)

  33. Roy, N., Gordon, G., Thrun, S.: Planning under uncertainty for reliable health care robotics. In: Yuta, S., Asama, H., Prassler, E., Tsubouchi, T., Thrun, S. (eds.) Field and Service Robotics, vol. 24, pp. 417–426. Springer Berlin, Heidelberg (2006)

    Chapter  Google Scholar 

  34. Simon, D.: Optimal Estimation: Kalman, H  ∞ , and Nonlinear Approaches. Wiley (2006)

  35. Toit, N.E.D., Burdick, J.W.: Robot motion planning in dynamic, uncertain environments. IEEE Trans. Robot. 28(1), 101–115 (2012)

    Article  Google Scholar 

  36. Urmson, C., Simmons, R.: Approaches for heuristically biasing RRT growth. In: Proceedings of the IEEE International Conference on Intelligent Robots and Systems, pp. 1178–1183. Las Vegas, NV (2003)

  37. van Hessem, D.H.: Stochastic inequality constrained closed-loop model predictive control with application to chemcial process operation. PhD thesis, Technische Universiteit Delft (2004)

  38. Visintini, A.L., Glover, W., Lygeros, J., Maciejowski, J.: Monte Carlo optimization for conflict resolution in air traffic control. IEEE Trans. Intel. Transp. Syst. 7(4), 470–482 (2006)

    Article  Google Scholar 

  39. Yan, Y., Bitmead, R.R.: Incorporating state estimation into model predictive control and its application to network traffic control. Automatica 41, 595–604 (2005)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computing, Engineering and Information Sciences, Northumbria University, NE1 8ST, Newcastle Upon Tyne, United Kingdom

    Mangal Kothari

  2. Northumbria University, NE1 8ST, Newcastle Upon Tyne, United Kingdom

    Ian Postlethwaite

Authors
  1. Mangal Kothari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ian Postlethwaite
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mangal Kothari.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kothari, M., Postlethwaite, I. A Probabilistically Robust Path Planning Algorithm for UAVs Using Rapidly-Exploring Random Trees. J Intell Robot Syst 71, 231–253 (2013). https://doi.org/10.1007/s10846-012-9776-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10846-012-9776-4

Keywords

Search

Navigation