A quadratic regulator-based heuristic for rapidly exploring state space
- 1 May 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (10504729), 5021-5028
- https://doi.org/10.1109/robot.2010.5509718
Abstract
Kinodynamic planning algorithms like Rapidly-Exploring Randomized Trees (RRTs) hold the promise of finding feasible trajectories for rich dynamical systems with complex, nonconvex constraints. In practice, these algorithms perform very well on configuration space planning, but struggle to grow efficiently in systems with dynamics or differential constraints. This is due in part to the fact that the conventional distance metric, Euclidean distance, does not take into account system dynamics and constraints when identifying which node in the existing tree is capable of producing children closest to a given point in state space. We show that an affine quadratic regulator (AQR) design can be used to approximate the exact minimum-time distance pseudometric at a reasonable computational cost. We demonstrate improved exploration of the state spaces of the double integrator and simple pendulum when using this pseudometric within the RRT framework, but this improvement drops off as systems' nonlinearity and complexity increase. Future work includes exploring methods for approximating the exact minimum-time distance pseudometric that can reason about dynamics with higher-order terms.Keywords
This publication has 14 references indexed in Scilit:
- Planning AlgorithmsPublished by Cambridge University Press (CUP) ,2006
- Guidelines in nonholonomic motion planning for mobile robotsPublished by Springer Nature ,2006
- Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling DomainPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- An RRT-Based Algorithm for Testing and Validating Multi-Robot ControllersPublished by Robotics: Science and Systems Foundation ,2005
- Design and verification of controllers for airshipsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Randomized kinodynamic planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A randomized roadmap method for path and manipulation planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Randomized Kinodynamic PlanningThe International Journal of Robotics Research, 2001
- Optimal obstacle avoidance based on the Hamilton-Jacobi-Bellman equationIEEE Transactions on Robotics and Automation, 1997
- An exact algorithm for kinodynamic planning in the planePublished by Association for Computing Machinery (ACM) ,1990