In this paper we present LQG-MP (linear-quadratic Gaussian motion planning), a new approach to robot motion planning that takes into account the sensors and the controller that will be used during the execution of the robot’s path. LQG-MP is based on the linear-quadratic controller with Gaussian models of uncertainty, and explicitly characterizes in advance (i.e. before execution) the a priori probability distributions of the state of the robot along its path. These distributions can be used to assess the quality of the path, for instance by computing the probability of avoiding collisions. Many methods can be used to generate the required ensemble of candidate paths from which the best path is selected; in this paper we report results using rapidly exploring random trees (RRT). We study the performance of LQG-MP with simulation experiments in three scenarios: (A) a kinodynamic car-like robot, (B) multi-robot planning with differential-drive robots, and (C) a 6-DOF serial manipulator. We also present a method that applies Kalman smoothing to make paths Ck-continuous and apply LQG-MP to precomputed roadmaps using a variant of Dijkstra’s algorithm to efficiently find high-quality paths.
Alterovitz R., Siméon T. and Goldberg K. ( 2007) The stochastic motion road-map: a sampling framework for planning with Markov motion uncertainty. In: Proceedings of Robotics: Science and Systems, 2007.
2.
Bertsekas D. ( 2001) Dynamic Programming and Optimal Control. Nashua, NH: Athena Scientific.
3.
Bouilly B., Simeon T. and Alami R. ( 1995) A numerical technique for planning motion strategies of a mobile robot in presence of uncertainty. Proceedings of the IEEE International Conference on Robotics and Automation, 1995.
4.
Burns B. and Brock O. ( 2007) Sampling-based motion planning with sensing uncertainty . In: Proceedings of the IEEE International Conference on Robotics and Automation, 2007.
5.
Fraichard T. and Mermond R. ( 1998) Path planning with uncertainty for car-like robots. In: Proceedings of the IEEE International Conference on Robotics and Automation, 1998.
6.
Geraerts R. and Overmars M. ( 2007) Creating high-quality paths for motion planning. The International Journal of Robotics Research26: 845-863.
7.
Gonzalez J. and Stentz A. ( 2009) Using linear landmarks for path planning with uncertainty in outdoor environments. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009.
8.
Guibas L., Hsu D., Kurniawati H. and Rehman E. ( 2008) Bounded uncertainty roadmaps for path planning. In: Proceedings of the Workshop on Algorithmic Foundations of Robotics, 2008.
9.
Huang Y. and Gupta K. ( 2009) Collision-probability constrained PRM for a manipulator with base pose uncertainty. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009.
10.
Huynh V. and Roy N. ( 2009) icLQG: combining local and global optimization for control in information space. In: Proceedings of the IEEE International Conference on Robotics and Automation, 2009.
11.
Kaelbling L., Littman M. and Cassandra A. ( 1998) Planning and acting in partially observable stochastic domains. Artificial Intelligence101: 99-134.
12.
Kavraki L., Svestka P., Latombe J-C and Overmars M. ( 1996) Probabilistic roadmaps for path planning in high dimensional configuration spaces. IEEE Transactions on Robotics and Automation12: 566-580.
13.
Kewlani G., Ishigami G. and Iagnemma K. ( 2009) Stochastic mobility-based path planning in uncertain environments . In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009.
14.
Kuwata Y., Teo J., Karaman S., Fiore G., Frazzoli E. and How J. ( 2008) Motion planning in complex environments using closed-loop prediction. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit, 2008.
15.
Kurniawati H., Hsu D. and Lee W. ( 2008) SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. Proceedings of the Robotics: Science and Systems, 2008.
16.
LaValle S. ( 2006) Planning Algorithms. Cambridge: Cambridge University Press.
17.
LaValle S. and Hutchinson S. ( 1998) An objective-based framework for motion planning under sensing and control uncertainties. The International Journal of Robotics Research17: 19-42.
18.
LaValle S. and Kuffner J. ( 2001) Randomized kinodynamic planning. The International Journal of Robotics Research20: 378-400.
19.
Lazanas A. and Latombe J. ( 1995) Motion planning with uncertainty: a landmark approach . Artificial Intelligence76: 285-317.
20.
Melchior N. and Simmons R. ( 2007) Particle RRT for path planning with uncertainty. In: Proceedings of the IEEE International Conference on Robotics and Automation, 2007.
21.
Missiuro P. and Roy N. ( 2006) Adapting probabilistic roadmaps to handle uncertain maps . In: Proceedings of the IEEE International Conference on Robotics and Automation, 2006.
22.
Nakhaei A. and Lamiraux F. ( 2008) A framework for planning motions in stochastic maps. In: Proceedings of the International Conference on Control, Automation, Robotics and Vision, 2008.
23.
Papadimitriou C. and Tsisiklis J. ( 1987) The complexity of Markov decision processes. Mathematics of Operations Research12: 441-450.
24.
Pepy R. and Lambert A. ( 2006) Safe path planning in an uncertain-configuration space using RRT. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006.
25.
Platt R., Tedrake R., Kaelbling L. and Lozano-Perez T. ( 2010) Belief space planning assuming maximum likelihood observations . In: Proceedings of the Robotics: Science and Systems, 2010.
26.
Porta J., Vlassis N., Spaan M. and Poupart P. ( 2006) Point-based value iteration for continuous POMDPs. Journal of Machine Learning Research7: 2329-2367.
27.
Prentice S. and Roy N.(2009) The belief roadmap: efficient planning in belief space by factoring the covariance. The International Journal of Robotics Research28: 1448-1465.
28.
Rauch H., Tung F. and Striebel C. ( 1965) Maximum likelihood estimates of linear dynamic systems . AIAA Journal3: 1445-1450.
29.
Roy N., Burgard W., Fox D. and Thrun S. ( 1999) Coastal navigation-mobile robot navigation with uncertainty in dynamic environments. In: Proceedings of the IEEE International Conference on Robotics and Automation, 1999 .
30.
Tedrake R. ( 2009) LQR-trees: Feedback motion planning on sparse randomized trees. In: Proceedings of the Robotics: Science and Systems , 2009.
31.
Thrun S., Burgard W. and Fox D. ( 2005) Probabilistic Robotics. Cambridge, MA: The MIT Press.
32.
van den Berg J. and Overmars M. ( 2005) Prioritized motion planning for multiple robots. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005.
33.
van den Bergen G. ( 2004) Collision Detection in Interactive 3D Environments. San Mateo, CA: Morgan Kaufmann.
34.
Welch G. and Bishop G. ( 2006) An Introduction to the Kalman Filter. Techical Report TR 95-041, University of North Carolina at Chapel Hill , 2006.
