In this paper, we present CHOMP (covariant Hamiltonian optimization for motion planning), a method for trajectory optimization invariant to reparametrization. CHOMP uses functional gradient techniques to iteratively improve the quality of an initial trajectory, optimizing a functional that trades off between a smoothness and an obstacle avoidance component. CHOMP can be used to locally optimize feasible trajectories, as well as to solve motion planning queries, converging to low-cost trajectories even when initialized with infeasible ones. It uses Hamiltonian Monte Carlo to alleviate the problem of convergence to high-cost local minima (and for probabilistic completeness), and is capable of respecting hard constraints along the trajectory. We present extensive experiments with CHOMP on manipulation and locomotion tasks, using seven-degree-of-freedom manipulators and a rough-terrain quadruped robot.
AmariSINagaokaH (2000) Methods of Information Geometry. Oxford: Oxford University Press.
2.
BagnellJA (2004) Learning Decisions: Robustness, Uncertainty, and Approximation. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
3.
BarraquandJLatombeJC (1990) A Monte-Carlo algorithm for path planning with many degrees of freedom. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1712–1717.
4.
BentleyJL (1975) Multidimensional binary search trees used for associative searching. Communications of the ACM18(9): 509–517.
5.
BerensonDSrinivasaSFergusonDCollet RomeaAKuffnerJ (2009) Manipulation planning with workspace goal regions. In: Proceedings of the IEEE International Conference on Robotics and Automation.
6.
BobrowJE (1989) A direct minimization approach for obtaining the distance between convex polyhedra. The International Journal of Robotics Research8(3): 65–76.
7.
BranickyMSLaValleSMOlsonKYangL (2001) Quasi-randomized path planning. In: Proceedings of the International Conference on Robotics and Automation.
8.
BrockOKhatibO (2002) Elastic Strips: A framework for motion generation in human environments. The International Journal of Robotics Research21(12): 1031–1052.
9.
CasalA (2001) Reconfiguration Planning for Modular Self-reconfigurable Robots. PhD thesis, Aeronautics and Astronautics Department, Stanford University.
10.
ChaichianMDemichevA (2001) Path Integrals in Physics Volume 2: Quantum Field Theory, Statistical Physics & Other Modern Applications. Taylor & Francis.
11.
ChenPCHwangYK (1998) SANDROS: A dynamic graph search algorithm for motion planning. IEEE Transactions on Robotics and Automation14(3): 390–403.
12.
ChestnuttJ (2007) Navigation Planning for Legged Robots. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
13.
CohenBChittaSLikhachevM (2010) Search-based planning for manipulation with motion primitives. In: IEEE International Conference on Robotics and Automation. IEEE, pp. 2902–2908.
14.
ConteSde BoorC (1972) Elementary Numerical Analysis. New York: McGraw-Hill.
15.
DalibardSLaumondJ (2009) Control of probabilistic diffusion in motion planning. In: Proceedings of the International Workshop on Algorithmic Foundations of Robotics, pp. 467–481.
16.
DeyDLiuTYHebertMBagnellJA (2012) Contextual sequence prediction with application to control library optimization. In: Proceedings of RSS.
17.
DiankovR (2010) Automated Construction of Robotics Manipulation Programs. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
18.
DiebelJ (2006) Representing Attitude: Euler Angles, Unit Quaternions, and Rotation Vectors. Technical Report, Stanford University.
19.
DogarMSrinivasaS (2011) A framework for push-grasping in clutter. In: Proceedings of Robotics: Science and Systems, Los Angeles, CA.
20.
DraganAGordonGSrinivasaS (2011a) Learning from experience in manipulation planning: Setting the right goals. In: Proceedings of ISRR.
21.
DraganALeeKSrinivasaS (2013) Legibility and predictability of robot motion. In: Proceedings of Human–Robot Interaction.
22.
DraganARatliffNSrinivasaS (2011b) Manipulation planning with goal sets using constrained trajectory optimization. In: Proceedings of the 2011 IEEE International Conference on Robotics and Automation.
23.
EisemannEDecoretX (2008) Single-pass GPU solid voxelization for real-time applications. In: Proceedings of the Graphics Interface Conference.
24.
FaverjonB (1989) Hierarchical object models for efficient anti-collision algorithms. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 333–340. DOI: 10.1109/ROBOT.1989.100010.
GelenbeELentRXuZ (2001) Design and performance of cognitive packet networks. Performance Evaluation46(2-3): 155–176.
27.
GelfandIMFominSV (1963) Calculus of Variations. Englewood Cliffs, NJ: Prentice-Hall, Inc.
28.
GeraertsROvermarsMH (2006) Creating high-quality roadmaps for motion planning in virtual environments. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4355–4361.
29.
GilbertEGJohnsonDWKeerthiSS (1988) A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Journal of Robotics and Automation4(2): 193–203. DOI: 10.1109/56.2083.
30.
HassaniS (1999) Mathematical Physics: A Modern Introduction to Its Foundations. New York: Springer-Verlag.
31.
HazanEAgarwalAKaleS (2006) Logarithmic regret algorithms for online convex optimization. In: Proceedings of COLT, pp. 499–513.
HsuDLatombeJCMotwaniR (1997) Path planning in expansive configuration spaces. In: Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3, pp. 2719–2726. DOI: 10.1109/ROBOT.1997.619371.
34.
IgelCToussaintMWeishuiW (2005) Rprop using the natural gradient. In: Trends and Applications in Constructive Approximation (ISNM International Series of Numerical Mathematics, vol. 151). Basel: Birkhäuser, pp. 259–272.
35.
JetchevNToussaintM (2010) Trajectory prediction in cluttered voxel environments. In: IEEE International Conference on Robotics and Automation, pp. 2523–2528.
36.
KajitaSKanehiroFKanekoK. (2003) Biped walking pattern generation by using preview control of zero-moment point. In: IEEE International Conference on Robotics and Automation.
37.
KalakrishnanMBuchliJPastorPMistryMSchaalS (2011a) Learning, planning, and control for quadruped locomotion over challenging terrain. The International Journal of Robotics Research30(2): 236–258.
38.
KalakrishnanMChittaSTheodorouEPastorPSchaalS (2011b) STOMP: Stochastic trajectory optimization for motion planning. In: Proceedings IEEE International Conference on Robotics and Automation (ICRA), pp. 4569–4574. DOI: 10.1109/ICRA.2011.5980280.
39.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research30(7): 846–894.
40.
KavrakiLELatombeJC (1998) Probabilistic roadmaps for robot path planning. In: Practical Motion Planning in Robotics: Current Approaches and Future Directions. New York: John Wiley & Sons, Inc.
41.
KavrakiLEŠvestkaPLatombeJCOvermarsMH (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation12(4): 566–580. DOI: 10.1109/70.508439.
KhatibO (1986) Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research5(1): 90–98.
44.
KindelR (2001) Motion Planning for Free-flying Robots in Dynamic and Uncertain Environments. PhD thesis, Aeronautics and Astronautics Department, Stanford University.
45.
KleinertH (2009) Path Integrals in Quantum Mechanics, Statistics, Polymer Physics, and Financial Markets (5th edn). Singapore: World Scientific Publishing Company.
KuffnerJJLaValleSM (2000) RRT-connect: An efficient approach to single-query path planning. In: Proceedings IEEE International Conference on Robotics and Automation (ICRA ’00), vol. 2, pp. 995–1001. DOI: 10.1109/ROBOT.2000.844730.
48.
LauterbachCMoQManochaD (2010) gProximity: hierarchical GPU-based operations for collision and distance queries. Computer Graphics Forum29(2): 419–428.
49.
LaValleSM (2006) Planning Algorithms. Cambridge: Cambridge University Press.
50.
LaValleSMBranickyMSLindemannSR (2004) On the relationship between classical grid search and probabilistic roadmaps. The International Journal of Robotics Research23(7/8): 673–692.
51.
LaValleSMKuffnerJJ (2001) Rapidly-exploring random trees: Progress and prospects. In: Algorithmic and Computational Robotics: New Directions, pp. 293–308.
52.
LikhachevMGordonGThrunS (2004) ARA*: Anytime A* with provable bounds on sub-optimality. In: Workshop on Neural Information Processing Systems.
53.
LikhachevMStentzA (2008) R* search. In: Proceedings of AAAI.
54.
LinMCCannyJF (1991) A fast algorithm for incremental distance calculation. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1008–1014. DOI: 10.1109/ROBOT.1991.131723.
55.
MayneDHJacobsonDQ (1970) Differential Dynamic Programming. New York: American Elsevier Pub. Co.
56.
-1Neal RM (1993) Probabilistic Inference using Markov Chain Monte Carlo Methods. Technical Report, University of Toronto.
57.
NealRM (2010) MCMC using Hamiltonian dynamics. In: Handbook of Markov Chain Monte Carlo. Boca Raton, FL: Chapman & Hall/CRC, pp. 113–162.
58.
PanJChittaSManochaD (2012) FCL: A general purpose library for proximity and collision queries. In: Proceedings of the IEEE International Conference on Robotics and Automation.
59.
PhillipsMCohenBChittaSLikhachevM (2012) E-graphs: Bootstrapping planning with experience graphs. In: Proceedings of Robotics: Science and Systems.
QuinlanSKhatibO (1993) Elastic Bands: connecting path planning and control. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 802–807. DOI: 10.1109/ROBOT.1993.291936.
62.
RatliffNBagnellJAZinkevichM (2006a) Maximum margin planning. In: Proceedings of the International Conference on Machine Learning.
63.
RatliffNBagnellJAZinkevichM (2007) (Online) Subgradient methods for structured prediction. In: Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics (AIStats).
64.
RatliffNBradleyDBagnellJAChestnuttJ (2006b) Boosting structured prediction for imitation learning. In: Workshop on Neural Information Processing Systems.
65.
RatliffNZuckerMBagnellJASrinivasaS (2009) CHOMP: Gradient optimization techniques for efficient motion planning. In: Proceedings of the IEEE International Conference on Robotics and Automation.
66.
ReggianiMMazzoliMCaselliS (2002) An experimental evaluation of collision detection packages for robot motion planning. In: 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 3, pp. 2329–2334.
67.
RimonEKoditschekDE (1988) Exact robot navigation using cost functions: the case of distinct spherical boundaries in En. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1791–1796. DOI: 10.1109/ROBOT.1988.12325.
68.
SchlkopfBSmolaAJ (2001) Learning with Kernels. Cambridge, MA: Massachusetts Institute of Technology.
69.
SchouwenaarsTMoorBDFeronEHowJ (2001) Mixed integer programming for multi-vehicle path planning. In: Proceedings of the European Control Conference.
70.
ShillerZDubowskyS (1991) On computing the global time-optimal motions of robotic manipulators in the presence of obstacles. IEEE Transactions on Robotics and Automation6(7): 785–797.
71.
SiggCPeikertRGrossM (2003) Signed distance transform using graphics hardware. In: Proceedings of the IEEE Visualization Conference.
72.
SrinivasaSFergusonDHelfrichC. (2010) HERB: a home exploring robotic butler. Autonomous Robots28(1): 5–20.
73.
SudAGovindarajuNGayleRManochaD (2006) Interactive 3D distance field computation using linear factorization. In: Proceedings of the Symposium on Interactive 3D Graphics and Games.
74.
TheodorouEBuchliJSchaalS (2010) Generalized path integral control approach to reinforcement learning. Journal of Machine Learning Research11: 3137–3181.
75.
TodorovE (2006) Linearly-solvable Markov decision problems. In: Proceedings of Neural Information Processing Systems. Cambridge, MA: MIT Press, pp. 1369–1376.
76.
TodorovELiW (2005) A generalized iterative LQG method for locally-optimal feedback control of constrained nonlinear stochastic systems. In: Proceedings of the American Control Conference.
77.
ToussaintM (2009) Robot trajectory optimization using approximate inference. In: Proceedings of the 26th Annual International Conference on Machine Learning. New York: ACM Press, pp. 1049–1056.
78.
VernazaPLeeD (2011) Learning dimensional descent for optimal motion planning in high-dimensional spaces. In: Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI) Conference.
79.
ŽefranMDesaiJPKumarV (1996) Continuous motion plans for robotic systems with changing dynamic behavior. In: Proceedings of the International Workshop on Algorithmic Foundations of Robotics.
80.
ZiebartBD (2010) Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy. PhD thesis, Machine Learning Department, Carnegie Mellon University.
81.
ZiebartBDBagnellJADeyA (2010) Modeling interaction via the principle of maximum causal entropy. In: Proceedings of the International Conference on Machine Learning.
82.
ZiebartBDRatliffNGallagherG. (2009) Planning-based prediction for pedestrians. In: Proceedings IROS 2009.
83.
ZinkevichM (2003) Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the Twentieth International Conference on Machine Learning, pp. 928–936.
84.
ZuckerMRatliffNStolleM. (2011) Optimization and learning for rough terrain legged locomotion. The International Journal of Robotics Research30(2): 175–191.
