Rapidly Exploring Random Trees (RRTs) have gained significant attention due to provable properties such as completeness and asymptotic optimality. However, offline methods are only useful when the entire problem landscape is known a priori. Furthermore, many real world applications have problem scopes that are orders of magnitude larger than typical mazes and bug traps that require large numbers of samples to match typical sample densities, resulting in high computational effort for reasonably low-cost trajectories. In this paper we propose an online trajectory optimization algorithm for uncertain large environments using RRTs, which we call Locally Adaptive Rapidly Exploring Random Tree (LARRT). This is achieved through two main contributions. We use an adaptive local sampling region and adaptive sampling scheme which depend on states of the dynamic system and observations of obstacles. We also propose a localized approach to planning and re-planning through fixing the root node to the current vehicle state and adding tree update functions. LARRT is designed to leverage local problem scope to reduce computational complexity and obtain a total lower-cost solution compared to a classical RRT of a similar number of nodes. Using this technique we can ensure that popular variants of RRT will remain online even for prohibitively large planning problems by transforming a large trajectory optimization approach to one that resembles receding horizon optimization. Finally, we demonstrate our approach in simulation and discuss various algorithmic trade-offs of the proposed approach.
Skip Nav Destination
ASME 2018 Dynamic Systems and Control Conference
September 30–October 3, 2018
Atlanta, Georgia, USA
Conference Sponsors:
- Dynamic Systems and Control Division
ISBN:
978-0-7918-5191-3
PROCEEDINGS PAPER
Locally Adaptive Online Trajectory Optimization in Unknown Environments With RRTs
Ethan N. Evans,
Ethan N. Evans
Georgia Institute of Technology, Atlanta, GA
Search for other works by this author on:
Patrick Meyer,
Patrick Meyer
Georgia Institute of Technology, Atlanta, GA
Search for other works by this author on:
Samuel Seifert,
Samuel Seifert
Georgia Institute of Technology, Atlanta, GA
Search for other works by this author on:
Dimitri N. Mavris,
Dimitri N. Mavris
Georgia Institute of Technology, Atlanta, GA
Search for other works by this author on:
Evangelos A. Theodorou
Evangelos A. Theodorou
Georgia Institute of Technology, Atlanta, GA
Search for other works by this author on:
Ethan N. Evans
Georgia Institute of Technology, Atlanta, GA
Patrick Meyer
Georgia Institute of Technology, Atlanta, GA
Samuel Seifert
Georgia Institute of Technology, Atlanta, GA
Dimitri N. Mavris
Georgia Institute of Technology, Atlanta, GA
Evangelos A. Theodorou
Georgia Institute of Technology, Atlanta, GA
Paper No:
DSCC2018-8997, V003T32A002; 10 pages
Published Online:
November 12, 2018
Citation
Evans, EN, Meyer, P, Seifert, S, Mavris, DN, & Theodorou, EA. "Locally Adaptive Online Trajectory Optimization in Unknown Environments With RRTs." Proceedings of the ASME 2018 Dynamic Systems and Control Conference. Volume 3: Modeling and Validation; Multi-Agent and Networked Systems; Path Planning and Motion Control; Tracking Control Systems; Unmanned Aerial Vehicles (UAVs) and Application; Unmanned Ground and Aerial Vehicles; Vibration in Mechanical Systems; Vibrations and Control of Systems; Vibrations: Modeling, Analysis, and Control. Atlanta, Georgia, USA. September 30–October 3, 2018. V003T32A002. ASME. https://doi.org/10.1115/DSCC2018-8997
Download citation file:
43
Views
Related Proceedings Papers
Related Articles
Hierarchical Nonlinear Moving Horizon Estimation of Vehicle Lateral Speed and Road Friction Coefficient
Letters Dyn. Sys. Control (January,2021)
Learning an Optimization Algorithm Through Human Design Iterations
J. Mech. Des (October,2017)
Improved Neural Network Control Approach for a Humanoid Arm
J. Dyn. Sys., Meas., Control (October,2019)
Related Chapters
Trajectory Optimization of Hypersonic Vehicle Using Gauss and Legendre Pseudospectral Method
International Conference on Mechanical and Electrical Technology, 3rd, (ICMET-China 2011), Volumes 1–3
Multidimension Application Introduction and the Gradient
Engineering Optimization: Applications, Methods, and Analysis
Optimization Algorithms
Nonlinear Regression Modeling for Engineering Applications: Modeling, Model Validation, and Enabling Design of Experiments