Robot trajectory optimization using approximate inference

ABSTRACT

The general stochastic optimal control (SOC) problem in robotics scenarios is often too complex to be solved exactly and in near real time. A classical approximate solution is to first compute an optimal (deterministic) trajectory and then solve a local linear-quadratic-gaussian (LQG) perturbation model to handle the system stochasticity. We present a new algorithm for this approach which improves upon previous algorithms like iLQG. We consider a probabilistic model for which the maximum likelihood (ML) trajectory coincides with the optimal trajectory and which, in the LQG case, reproduces the classical SOC solution. The algorithm then utilizes approximate inference methods (similar to expectation propagation) that efficiently generalize to non-LQG systems. We demonstrate the algorithm on a simulated 39-DoF humanoid robot.

REFERENCES

• 1: Attias, H. (2003). Planning by probabilistic inference. Proc. of the 9th Int. Workshop on Artificial Intelligence and Statistics.
• 2: Bryson, A. E., & Ho, Y.-C. (1969). Applied optimal control. Blaisdell Publishing Company.
• 3: Chen, Y.-C. (1991). Solving robot trajectory planning problems with uniform cubic b-splines. Optimal Control Applications and Methods, 12, 247--262.
• 4: Cooper, G. (1988). A method for using belief networks as influence diagrams. Proc. of the Fourth Workshop on Uncertainty in Artificial Intelligence (pp. 55--63).
• 5: Peter Dayan , Geoffrey E. Hinton, Using expectation-maximization for reinforcement learning, Neural Computation, v.9 n.2, p.271-278, Feb. 15, 1997 [doi>10.1162/neco.1997.9.2.271]
• 6: Kappen, B., Gomez, V., & Opper, M. (2009). Optimal control as a graphical model inference problem.
• 7: Thomas P. Minka , Rosalind Picard, A family of algorithms for approximate bayesian inference, Massachusetts Institute of Technology, 2001
• 8: Thomas P. Minka, Expectation Propagation for approximate Bayesian inference, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.362-369, August 02-05, 2001
• 9: Kevin Patrick Murphy , Stuart Russell, Dynamic bayesian networks: representation, inference and learning, University of California, Berkeley, 2002
• 10: Schlemmer, M., & Gruebel, G. (1998). Real-time collision- free trajectory optimization of robot manipulators via semi-infinite parameter optimization. Int. Journal of Robotics Research, 17, 1013--1021.
• 11: Ross D. Shachter , Mark A. Peot, Decision making using probabilistic inference methods, Proceedings of the eighth conference on Uncertainty in Artificial Intelligence, p.276-283, June 1992, Stanford, California, United States
• 12: Ross D. Shachter, Probabilistic inference and influence diagrams, Operations Research, v.36 n.4, p.589-604, July-August 1988 [doi>10.1287/opre.36.4.589]
• 13: Stengel, R. F. (1986). Stochastic optimal control. Wiley.
• 14: Todorov, E. (2008). General duality between optimal control and estimation. In proceedings of the 47th ieee conf. on decision and control.
• 15: Todorov, E., & Li, W. (2005). A generalized iterative lqg method for locally-optimal feedback control of constrained nonlinear stochastic systems. In Proc. of the american control conference, 300--306.
• 16: Toussaint, M., & Goerick, C. (2007). Probabilistic inference for structured planning in robotics. Int Conf on Intelligent Robots and Systems (IROS 2007) (pp. 3068--3073).
• 17: Toussaint, M., Harmeling, S., & Storkey, A. (2006). Probabilistic inference for solving (PO)MDPs (Technical Report EDI-INF-RR-0934). University of Edinburgh, School of Informatics.
• 18: Yedidia, J., Freeman, W., & Weiss, Y. (2001). Understanding belief propagation and its generalizations.
• 19: Zhang, J., & Knoll, A. (1995). An enhanced optimization approach for generating smooth robot trajectories in the presence of obstacles. Proc. of the 1995 European Chinese Automation Conference (pp. 263--268). London.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Workcell organization and planning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning; Inference engines
      I.2.6 Learning
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance, Theory