Motion Planning Under Uncertainty Using Differential Dynamic Programming in Belief Space

详细信息    查看全文

• 刊名：Springer Tracts in Advanced Robotics
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：100
• 期：1
• 页码：473-490
• 全文大小：288 KB
• 参考文献：1.H. Bai, D. Hsu, W. Lee, V. Ngo, Monte Carlo value iteration for continuous state POMDPs, in Workshop on the Algorithmic Foundations of Robotics (2010)
  2.D. Bertsekas, Dynamic Programming and Optimal Control (Athena Scientific, 2001)
  3.A. Brooks, A. Makarendo, S. Williams, H. Durrant-Whyte, Parametric POMDPs for planning in continuous state spaces. Robot. Auton. Syst. 54(11), 887–897 (2006)CrossRef
  4.A. Bry, N. Roy, Rapidly-exploring random belief trees for motion planning under uncertainty, in IEEE International Conference on Robotics and Automation (2011)
  5.S. Candido, S. Hutchinson, Minimum uncertainty robot navigation using information- guided POMDP planning, in IEEE International Conference on Robotics and Automation (2011)
  6.N. Du Toit, J. Burdick, Robotic motion planning in dynamic, cluttered, uncertain environments, in IEEE International Conference on Robotics and Automation (2010)
  7.T. Erez, W.D. Smart, A scalable method for solving high-dimensional continuous POMDPs using local approximation, in Conference on Uncertainty in Artificial Intelligence (2010)
  8.K. Hauser, Randomized belief-space replanning in partially-observable continuous spaces, in Workshop on the Algorithmic Foundations of Robotics (2010)
  9.V. Huynh, N. Roy, icLQG: combining local and global optimization for control in information space, in IEEE International Conference on Robotics and Automation (2009)
  10.D. Jacobson, D. Mayne, Differential Dynamic Programming (American Elsevier Publishing Company Inc., New York, 1970)MATH
  11.S. LaValle, J. Kuffner, Randomized kinodynamic planning. Int. J. Robot. Res. 20(5), 378–400 (2001)CrossRef
  12.L.-Z. Liao, C. Shoemaker, Convergence in unconstrained discrete-time differential dynamic programming. IEEE Trans. Autom. Control 36(6), 692–706 (1991)MathSciNet CrossRef MATH
  13.W. Li, E. Todorov, Iterative linearization methods for approximately optimal control and estimation of non-linear stochastic system. Int. J. Control 80(9), 1439–1453 (2007)MathSciNet CrossRef MATH
  14.L. Kaelbling, M. Littman, A. Cassandra, Planning and acting in partially observable stochastic domains. Artif. Intell. 101(1–2), 99–134 (1998)MathSciNet CrossRef MATH
  15.H. Kurniawati, D. Hsu, W. Lee, SARSOP: efficient point-based POMDP planning by approximating optimally reachable belief spaces. Robotics: Science and Systems, 2008. configuration spaces. IEEE Trans. Robot. Autom. 12( 4), 566–580 (1996)
  16.S. Ong, S. Png, D. Hsu, W. Lee, Planning under uncertainty for robotic tasks with mixed observability. Int. J. Robot. Res. 29(8), 1053–1068 (2010)CrossRef
  17.C. Papadimitriou, J. Tsisiklis, The complexity of Markov decision processes. Math. Oper. Res. 12(3), 441–450 (1987)MathSciNet CrossRef
  18.J. Porta, N. Vlassis, M. Spaan, P. Poupart, Point-based value iteration for continuous POMDPs. J. Mach. Learn. Res. 7, 2329–2367 (2006)MathSciNet MATH
  19.R. Platt, R. Tedrake, L. Kaelbling, T. Lozano-Perez, Belief space planning assuming maximum likelihood observations, in Robotics: Science and Systems (2010)
  20.S. Prentice, N. Roy, The belief roadmap: efficient planning in belief space by factoring the covariance. Int. J. Robot. Res. 28(1112), 1448–1465 (2009)CrossRef
  21.S. Thrun, Monte Carlo POMDPs. Advances in Neural Information Processing Systems (The MIT Press, 2000)
  22.S. Thrun, W. Burgard, D. Fox, Probabilistic Robotics (MIT Press, 2005)
  23.E. Todorov, W. Li, A generalized iterative LQG method for locally-optimal feedback control of constrained nonlinear stochastic systems, in American Control Conference (2005)
  24.J. van den Berg, P. Abbeel, K. Goldberg, LQG-MP: optimized path planning for robots with motion uncertainty and imperfect state information, in Robotics: Science and Systems (2010)
  25.M.P. Vitus, C.J. Tomlin, Closed-loop belief space planning for linear, Gaussian systems, in IEEE International Conference on Robotics and Automation (2011)
  26.G. Welch, G. Bishop, An introduction to the Kalman filter. Tech. Report TR 95-041, University of North Carolina at Chapel Hill (2006)
  27.S. Yakowitz, Algorithms and computational techniques in differential dynamic programming. Control Dyn. Syst. 31, 75–91 (1989)CrossRef
  
• 作者单位：Jur van den Berg (5)
  Sachin Patil (5)
  Ron Alterovitz (5)
  
  5. Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, USA
  
• 丛书名：Robotics Research
• ISBN：978-3-319-29363-9
• 刊物类别：Engineering
• 刊物主题：Automation and Robotics
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1610-742X
• 卷排序：100

文摘

We present an approach to motion planning under motion and sensing un-certainty, formally described as a continuous partially-observable Markov decision process (POMDP). Our approach is designed for non-linear dynamics and observation models, and follows the general POMDP solution framework in which we represent beliefs by Gaussian distributions, approximate the belief dynamics using an extended Kalman filter (EKF), and represent the value function by a quadratic function that is valid in the vicinity of a nominal trajectory through belief space. Using a variant of differential dynamic programming, our approach iterates with second-order convergence towards a linear control policy over the belief space that is locally-optimal with respect to a user-defined cost function. Unlike previous work, our approach does not assume maximum-likelihood observations, does not assume fixed estimator or control gains, takes into account obstacles in the environment, and does not require discretization of the belief space. The running time of the algorithm is polynomial in the dimension of the state space. We demonstrate the potential of our approach in several continuous partially-observable planning domains with obstacles for robots with non-linear dynamics and observation models.