SpringerLink
Log in

Survey of Motion Planning Literature in the Presence of Uncertainty: Considerations for UAV Guidance

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

Abstract

This paper provides a survey of motion planning techniques under uncertainty with a focus on their application to autonomous guidance of unmanned aerial vehicles (UAVs). The paper first describes the primary sources of uncertainty arising in UAV guidance and then describes relevant practical techniques that have been reported in the literature. The paper makes a point of distinguishing between contributions from the field of robotics and artificial intelligence, and the field of dynamical systems and controls. Mutual and individual contributions for these fields are highlighted providing a roadmap for tackling the UAV guidance problem.

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
EUR 32.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 includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Boutilier, C., Dean, T., Hanks, S.: Decision-theoretic planning: structural assumptions and computational leverage. J. Artif. Intell. Res. 11, 1–64 (1999)

    MATH  MathSciNet  Google Scholar 

  2. Blythe, J.: Decision-theoretic planning. AI Mag. 20(2), 37–54 (1999)

    Google Scholar 

  3. LaValle, S., Sharma, R.: A framework for motion planning in stochastic environments: modeling and analysis. In: IEEE International Conference on Robotics and Automation (1995)

  4. LaValle, S., Sharma, R.: A framework for motion planning in stochastic environments: application and computational issues. In: IEEE International Conference on Robotics and Automation (1995)

  5. Goerzen, C., Kong, Z., Mettler, B.: A survey of motion planning algorithms from the perspective of autonomous UAV guidance. J. Intell. Robot. Syst. 57(1), 65–100 (2010)

    Article  MATH  Google Scholar 

  6. Thrun, S., Burgard, W., Fox, D.: Probabilistic Robotics. The MIT Press (2005)

  7. Spaan, M.T.J.: Approximate planning under uncertainty in partially observable environments. Ph.D. dissertation, Universiteit van Amsterdam, Netherlands (2006)

  8. Bellman, R.: Dynamic Programming. Princeton University Press (1957)

  9. Bertsekas, D.: Dynamic programming and optimal control: vols. 1 & 2. Athena Scientific, Belmont, MA (2005)

    Google Scholar 

  10. Cassandra, A.R.: Exact and approximate algorithms for partially observable markov decision process. Ph.D. dissertation, Brown University, USA (1994)

  11. Cassandra, A., Kaelbling, L., Kurien, J.: Acting under uncertainty: discrete bayesian models for mobile-robot navigation. In: IEEE Conference on Intelligent Robots and Systems (IROS) (1996)

  12. Kaelbling, L., Littman, M., Cassandra, A.: Planning and acting in partially observable stochastic domains. Artif. Intell. 101(1–2), 99–134 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  13. Papadimitriou, C., Tsisiklis, J.: The complexity of markov decision processes. Math. Oper. Res. 12(3), 441450 (1987)

    Article  Google Scholar 

  14. Chang, H., Fu, M., Hu, J., Marcus, S.: Simulation-based Algorithms for Markov Decision Processes. Springer Berlin (2007)

    MATH  Google Scholar 

  15. Bryson, A.E., Ho, Y.C.: Applied Optimal Control. Taylor and Francis, Bristol, PA (1975)

    Google Scholar 

  16. Bryson, A.E.: Dynamic Optimization. Addison Wesley Longman (1999)

  17. Hull, D.: Conversion of optimal control problems into parameter optimization problems. J. Guid. Control Dyn. 20(1), 57–60 (1997)

    Article  MATH  Google Scholar 

  18. Borrelli, F., Subramanian, D., Raghunathan, A., Biegler, L.: MILP and NLP techniques for centralized trajectory planning of multiple unmanned air vehicles. In: American Control Conference, pp. 5763–5768 (2006)

  19. Schouwenaars, T., Mettler, B., Feron, E., How, J.: Hybrid model for trajectory planning of agile autonomous vehicles. Journal of Aerospace Computing, Information, and Communication, vol. 1 (2004)

  20. Mayne, D.: Nonlinear model predictive control: an assessment. In: American Institute of Chemical Engineers (AIChE) Symposium Series, pp. 217–231 (1997)

  21. Mayne, D., Rawling, J., Rao, C., Scokaert, P.: Constrained model predictive control: stability and optimality. Automatica 36(6), 789–814 (1987)

    Article  Google Scholar 

  22. Primbs, J.A., Nevistic, V., Doyle, J.C.: A receding horizon generalization of pointwise min-norm controllers. IEEE Trans. Automat. Contr. 45(5), 898–909 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  23. Jadbabaie, A., Yu, J., Hauser, J.: Unconstrained receding-horizon control of nonlinear systems. IEEE Trans. Automat. Contr. 776–783 (2001)

  24. Bemporad, A., Morari, M.: Robust model predictive control: a survey. Lect. Notes Control Inf. Sci. 207–226 (1999)

  25. Lee, Y.I., Kouvaritakis, B.: A linear programming approach to constrained robust predictive control. IEEE Trans. Automat. Contr. 45(9), 1765–1770 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  26. Cuzzola, F.A., Geromel, J.C., Morari, M.: An improved approach for constrained robust model predictive control. Automatica 38, 1138 (2002)

    MathSciNet  Google Scholar 

  27. Lee, J.H., Yu, Z.: Worst-case formulations of model predictive control for systems with bounded parameters. Automatica 33(5), 763–781 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  28. Kerrigan, E.C., Mayne, D.Q.: Optimal control of constrained, piecewise affine systems with bounded disturbances. In: IEEE Conference on Decision and Control (2002)

  29. Lee, Y.I., Kouvaritakis, B.: Constrained receding horizon predictive control for systems with disturbances. Int. J. Control 72(11), 1027–1032 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  30. Frazzoli, E., Dahleh, M.A., Feron, E.: A hybrid control architecture for aggressive maneuvering of autonomous helicopter. In: IEEE Conference on Decision and Control, Phoenix, AZ (1999)

  31. Mettler, B., Valenti, M., Schouwenaars, T., Frazzoli, E., Feron, E.: Rotorcraft motion planing for agile maneuvering. In: Proceedings of the 58th Forum of the American Helicopter Society, Montreal, Canada (2002)

  32. Schouwenaars, T., Mettler, B., How, J., Feron, E.: Robust Motion Planning Using a Maneuver Automaton with Built-in Uncertainties. American Control Conference, Denver, CO (2003)

    Google Scholar 

  33. Calafiore, G.C., Ghaoui, L.E.: Linear Programming with Probability Constraints Part 1. American Control Conference, New York City, NY (2007)

    Google Scholar 

  34. Calafiore, G.C., Ghaoui, L.E.: Linear Programming with Probability Constraints Part 2. American Control Conference, New York City, NY (2007)

    Google Scholar 

  35. Blackmore, A.B.L., Ono, M., Williams, B.C.: A probabilistic particle control approximation of chance constrained stochastic predictive control. IEEE Trans. Robot. 26(3), 502–517 (2010)

    Article  Google Scholar 

  36. Doucet, A., De Freitas, N., Gordon, N.: Sequential Monte Carlo methods in Practice. Springer Verlag (2001)

  37. Shapiro, A.: Stochastic programming approach to optimization under uncertainty. Math. Program. 112(1), 183–220 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  38. Blackmore, L., Li, H., Williams, B.: A Probabilistic Approach to Optimal Robust Path Planning with Obstacles. American Control Conference, Minneapolis, MN (2006)

    Google Scholar 

  39. Richards, A.: Robust Constrained Model Predictive Control. Ph.D. dissertation, Massachusetts Institute of Technology, USA (2005)

  40. Goerzen, C., Whalley, M.: Minimal risk motion planning: a new planner for autonomous uavs in uncertain environment. In: AHS International Specialists’ Meeting on Unmmaned Rotorcraft, Tempe, Arizona (2011)

  41. Weiß, B., Naderhirn, M., del Re, L.: Global real-time path planning for uavs in uncertain environment. In: IEEE International Symposium on Intelligent Control and International Conference on Control Applications, pp. 2725–2730. Munich, Germany (2006)

  42. Frazzoli, E.: Robust Hybrid Control for Autonomous Vehicle Motion Planning. PhD Thesis, MIT, Cambridge, MA (2001)

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

    Article  Google Scholar 

  44. LaValle, S., Kuffner, J. Jr.: Randomized kinodynamic planning. Int. J. Rob. Res. 20(5), 378 (2001)

    Article  Google Scholar 

  45. Pettersson, P., Doherty, P.: Probabilistic roadmap based path planning for an autonomous unmanned aerial vehicle. J. Intell. Fuzzy Syst. 17, 395–405 (2006)

    Google Scholar 

  46. Missiuro, P., Roy, N.: Adapting probabilistic roadmaps to handle uncertain maps. In: IEEE Conference on Robotics and Automation (ICRA), pp. 1261–1267. Orlando, FL (2006)

  47. Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithms 34(2), 251–281 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  48. Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms 21(2), 267–305 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  49. Stentz, A.: Optimal and efficient path planning for partially-known environments. In: IEEE International Conference on Robotics and Automation, vol. 4, pp. 3310–3317 (1994)

  50. Stentz, A.: The focussed D ∗  algorithm for real-time replanning. In: International Joint Conference on Artificial Intelligence (1995)

  51. Koenig, S., Likhachev, M.: D ∗  lite. In: Proceedings of the 18th National Conference on Artificial Intelligence (AAAI), pp. 476–483 (2002)

  52. Zilberstein, S., Russell, S.: Approximate reasoning using anytime algorithms. In: Imprecise and Approximate Computation. The Kluwer International Series in Engineering and Computer Science, vol. 318, pp. 43–62. Springer US (1995)

  53. Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., Thrun, S.: Anytime search in dynamic graphs. Artif. Intell. 172(14), 1613–1643 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  54. Thrun, S.: Robotic map**: a survey. In: Exploring artificial intelligence in the new millennium, pp. 1–35 (2002)

  55. Csorba, M.: Simultaneous Localization and Map Building. Ph.D. dissertation, University of Oxford (1997)

  56. Castellanos, J., Tardos, J.: Mobile robot localization and map building: a multisensor fusion approach. Kluwer Academic Pub (1999)

  57. McLachlan, G., Krishnan, T.: The EM algorithm and extensions. Wiley New York (1997)

    MATH  Google Scholar 

  58. Moravec, H., Elfes, A.: High resolution maps from wide angle sonar. In: IEEE Conference on Robotics and Automation (ICRA), vol. 2 (1985)

  59. Elfes, A.: Using occupancy grids for mobile robot perception and navigation. Comput. 22(6), 46–57 (1989)

    Article  Google Scholar 

  60. Konolige, K.: Improved occupancy grids for map building. Auton. Robots 4(4), 351–367 (1997)

    Article  Google Scholar 

  61. Pathak, K., Birk, A., Pop**a, J., Schwertfeger, S.: 3D Forward sensor modeling and application to occupancy grid based sensor fusion. In: IEEE Conference on Intelligent Robots and Systems (IROS), San Diego, CA (2007)

  62. Shim, D., Chung, H., Sastry, S.: Conflict-free navigation in unknown urban environments. IEEE Robot. Autom. Mag. 13(3), 27–33 (2006)

    Article  Google Scholar 

  63. Sinopoli, B., Micheli, M., Donato, G., Koo, T.: Vision based navigation for an unmanned aerial vehicle. In: IEEE Conference on Robotics and Automation (ICRA), vol. 2, pp. 1757–1764. Seoul, Korea (2001)

  64. Hrabar, S.: 3D path planning and stereo-based obstacle avoidance for rotorcraft UAVs. In: IEEE Conference on Intelligent Robots and Systems (IROS), pp. 807–814. Nice, France (2008)

  65. Scherer, S., Singh, S., Chamberlain, L., Saripalli, S.: Flying fast and low among obstacles. In: IEEE Conference on Robotics and Automation (ICRA), pp. 2023–2029. Roma, Italy (2007)

  66. Li, Z., Bui, T.: Robot path planning using fluid model. J. Intell. Robot. Syst. 21(1), 29–50 (1998)

    Article  MathSciNet  Google Scholar 

  67. Andert, F., Adolf, F.: Online world modeling and path planning for an unmanned helicopter. Auton. Robots, 27(3), 147–164 (2009)

    Article  Google Scholar 

  68. Davis, J., Chakravorty, S.: Motion planning under uncertainty: application to an unmanned helicopter. J. Guid. Control Dyn. 30(5), 1268–1276 (2007)

    Article  Google Scholar 

  69. Kumar, P.R., Varaiya, P.: Stochastic Systems: Estimation, Identification and Adaptive Control. Prentice-Hall, New Jersey, USA (1986)

    MATH  Google Scholar 

  70. Jennings, A., Ordonez, R., Ceccarelli, N.: Dynamic programming applied to UAV way point path planning in wind. In: IEEE International Conference on Computer-Aided Control Systems, CACSD, pp. 215–220 (2008)

  71. McGee, T., Spry, S., Hedrick, J.: Optimal path planning in a constant wind with a bounded turning rate. In: AIAA Guidance, Navigation, and Control Conference (2005)

  72. Dubins, L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math. 79(3), 497–516 (1957)

    Article  MATH  MathSciNet  Google Scholar 

  73. Boissonnat, J.D., Cerezo, A., Leblond, J.: Shortest paths of bounded curvature in the plane. In: IEEE Conference on Robotics and Automation (ICRA), vol. 3, pp. 2315–2320 (1992)

  74. McGee, T., Hedrick, J.: Path planning and control for multiple point surveillance by an unmanned aircraft in wind. In: American Control Conference, Minneapolis, Minnesota, USA (2006)

  75. Ceccarelli, N., Enright, J., Frazzoli, E., Rasmussen, S., Schumacher, C.: Micro UAV path planning for reconnaissance in wind. In: American Control Conference, pp. 5310–5315. New York City, USA (2007)

  76. Ketema, Y., Zhao, Y.: Micro Air Vehicle Trajectory Planning in Winds. J. Aircr. 47(4), 1460–1463 (2010)

    Article  Google Scholar 

  77. Nelson, D.R., Barber, D.B., McLain, T.W., Beard, R.W.: Vector field path following for small unmanned air vehicles. In: American Control Conference, Minneapolis, Minnesota, USA (2006)

  78. Kuwata, Y., Schouwenaars, T., Richards, A., How, J.: Robust constrained receding horizon control for trajectory planning. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit (2005)

  79. Kendoul, F., Fantoni, I., Nonami, K.: Optic flow-based vision system for autonomous 3D localization and control of small aerial vehicles. Robot. Auton. Syst. 57(6–7), 591–602 (2009)

    Article  Google Scholar 

  80. Celik, K., Chung, S.-J., Clausman, M., Somani, A.K.: Monocular vision SLAM for indoor aerial vehicles. IEEE Conference on Intelligent Robots and Systems (IROS), St. Louis, MO (2009)

  81. Achtelik, M., Bachrach, A., He, R., Prentice, S., Roy, N.: Stereo vision and laser odometry for autonomous helicopters in GPS-denied indoor environments. Proceedings of the SPIE, Unmanned Systems Technology XI. Orlando, Florida (2009)

  82. Roy, N., Gordon, G., Thrun, S.: Finding approximate POMDP solutions through belief compression. J. Artif. Intell. Res. 23, 1–40 (2005)

    Article  MATH  Google Scholar 

  83. Aberdeen, D.: A (revised) Survey of Approximate Methods for Solving Partially Observable Markov Decision Processes. National ICT Australia, Tech. Rep., Canberra, Australia (2003)

  84. Roy, N., Thrun, S.: Coastal navigation with mobile robots. Advances in Neural Processing Systems 12(12), 1043–1049 (1999)

    Google Scholar 

  85. Prentice, S., Roy, N.: The belief roadmap: efficient planning in linear pomdps by factoring the covariance. In: Proceedings of the 13th International Symposium of Robotics Research (ISRR), Hiroshima, Japan (2007)

  86. Olson, C.F.: Probabilistic self-localization for mobile robots. IEEE Trans. Robot. Autom. 16(1), 55–66 (2000)

    Article  Google Scholar 

  87. Thrun, S., Fox, D., Burgard, W.: Robust Monte Carlo localization for mobile robots. Artif. Intell, 128(1–2), 91–141 (2000)

    Google Scholar 

  88. Takeda, H., Latombe, J.: Sensory uncertainty field for mobile robot navigation. In: IEEE Conference on Robotics and Automation, pp. 2465–2472 (1992)

  89. Djekoune, A.O., Achour, K., Toumi, R.: A sensor based navigation algorithm for a mobile robot using the DVFF approach. Int. J. Adv. Robot. Syst. 6(2), 97–108 (2009)

    Google Scholar 

  90. Ma, Y., Soatto, S., Kosecka, J., Sastry, S.: An invitation to 3-D Vision. Springer-Verlag, LCC (2003)

    Google Scholar 

  91. Qian, G., Chellappa, R., Zheng, Q.: Robust structure from motion estimation using inertial data. J. Opt. Soc. Am. A, 18(12), 2982–2997 (2001)

    Article  Google Scholar 

  92. Prazenica, R.J., Kurdila, A.J., Sharpley, R.C.: Receding horizon control for mav with vision-based state and obstacle estimation. AIAA Guidance, Navigation, and Control Conference, South Carolina (2007)

  93. Yu, H., Beard, R.W., Byrne, J.: Vision-based local multi-resolution map** and path planning for miniature air vehicles. In: American Control Conference, St. Louis, Missouri, USA (2009)

  94. Watanabe, Y., Calise, A., Johnson, E.: Vision-based obstacle avoidance for UAVs. In: AIAA Guidance, Navigation and Control Conference, South Carolina (2007)

  95. Barrows, G., Chahl, J., Srinivasan, M.: Biomimetic visual sensing and flight control. The Aeronautical Journal, London: The Royal Aeronautical Society, 107(1069), 159–168 (2003)

    Google Scholar 

  96. Ruffier, F., Franceschini, N.: Optic flow regulation: the key to aircraft automatic guidance. Robot. Auton. Syst. 50(4), 177–194 (2005)

    Article  Google Scholar 

  97. Green, W., Oh, P., Sevcik, K., Barrows, G.: Autonomous landing for indoor flying robots using optic flow. In: ASME international mechanical engineering congress and exposition, vol. 2, pp. 1347–1352. (2003)

  98. Green, W., Oh, P., Barrows, G.: Flying insect inspired vision for autonomous aerial robot maneuvers in near-earth environments. In: IEEE Conference on Robotics and Automation, ICRA (2004)

  99. Beyeler, A., Zufferey, J., Floreano, D.: Vision-based control of near-obstacle flight. Auton. robots, 27(3), 201–219 (2009)

    Article  Google Scholar 

  100. Zufferey, J.C., Floreano, D.: Fly-inspired visual steering of an ultralight indoor aircraft. IEEE Trans. Robot. 22(1), 137–146 (2006)

    Article  Google Scholar 

  101. Hrabar, S., Sukhatme, G., Corke, P., Usher, K., Roberts, J.: Combined optic-flow and stereo-based navigation of urban canyons for a UAV. In: IEEE Conference on Intelligent Robots and Systems, IROS, pp. 3309–3316 (2005)

  102. Borenstein, J., Koren, Y.: Real-time obstacle avoidance for fast mobile robots. IEEE Trans. Syst. Sci. Cybern. 19(5), 1179–1187 (1989)

    Article  Google Scholar 

  103. Borenstein, J., Koren, Y.: The vector field histogram - fast obstacle avoidance for mobile robots. IEEE Trans. Robot. Autom. 7(3), 278–288 (1991)

    Article  Google Scholar 

  104. Minguez, J., Montano, L.: Nearness diagram (ND) navigation: collision avoidance in troublesome scenarios. IEEE Trans. Robot. Autom. 20(1), 45–59 (2004)

    Article  Google Scholar 

  105. Simmons, R.: The curvature-velocity method for local obstacle avoidance. In: IEEE International Conference on Robotics and Automation, pp. 3375–3382. Minneapolis, Minnesota (1996)

  106. Ko, N., Simmons, R.: The lane-curvature method for local obstacle avoidance. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1615–1621. B.C, Canada (1998)

Download references

Author information

Authors and Affiliations

  1. Interactive Guidance and Control Lab, Department of Aerospace Engineering and Mechanics, University of Minnesota, Minneapolis, MN, 55455, USA

    Navid Dadkhah & Bérénice Mettler

Authors
  1. Navid Dadkhah
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bérénice Mettler
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bérénice Mettler.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dadkhah, N., Mettler, B. Survey of Motion Planning Literature in the Presence of Uncertainty: Considerations for UAV Guidance. J Intell Robot Syst 65, 233–246 (2012). https://doi.org/10.1007/s10846-011-9642-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10846-011-9642-9

Keywords

Search

Navigation