Real-Time Motion Planning With Applications to Autonomous Urban Driving

By Yoshiaki Kuwata, Sertac Karaman, Justin Teo, Emilio Frazzoli, Jonathan P. How, Gaston A. Fiore. 2009

903 citations recorded by the source corpus.

This paper describes a real-time motion planning algorithm, based on the rapidly-exploring random tree (RRT) approach, applicable to autonomous vehicles operating in an urban environment. Extensions to the standard RRT are predominantly motivated by: 1) the need to generate dynamically feasible plans in real-time; 2) safety requirements; 3) the constraints dictated by the uncertain operating (urban) environment. The primary novelty is in the use of closed-loop prediction in the framework of RRT. The proposed algorithm was at the core of the planning and control software for Team MIT's entry for the 2007 DARPA Urban Challenge, where the vehicle demonstrated the ability to complete a 60 mile simulated military supply mission, while safely interacting with other autonomous and human driven vehicles.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Control and Systems Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

Citations in the corpus

Deep Reinforcement Learning for Autonomous Driving: A Survey (2020, background): “The control input is usually deﬁned over a ﬁnite time horizon and restricted on a feasible state space x ∈ X free [13].”
A Fast Integrated Planning and Control Framework for Autonomous Driving via Imitation Learning (2017, neutral): “Emails: { litingsun, chengpeng2014, wzhan, tomizuka} @berkeley.edu. i) graph-search-based, such as A ∗ (see [4]), ii) sampling-based (e.g., RRT, RRT*, see [5], [6]), iii) interpolating-curve-based [7], [8], and iv) optimization-based [9], [10].”
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles (2016, neutral): “A control system then reactively corrects errors in the execution of the planned motion.”
Research Advances and Challenges of Autonomous and Connected Ground Vehicles (2019, background): “Improving the computational efﬁciency of RRT is also widely studied [399]– [402].”
Stereo vision-based obstacle avoidance for micro air vehicles using disparity space (2014, methodology): “Collision checking of trajectories generated by a CL-RRT planner is done very ef(cid:2)ciently by performing a C-space-like expansion of the disparity map, projecting candidate trajectories into image space, and performing a z-buffer-like visibility test.”
Information-Theoretic Model Predictive Control: Theory and Applications to Autonomous Driving (2017, background): “In particular, the path planner typically has very coarse knowledge of the underlying system dynamics, usually only utilizing kinematic constraints [8]–[11].”
Online Verification of Automated Road Vehicles Using Reachability Analysis (2014, neutral): “[40]).”
Intention-aware online POMDP planning for autonomous driving in a crowd (2015, methodology): “A more sophisticated approach is to compute an open-loop plan, i.e., a path, using a predictive model and then execute the plan with a feedback controller (see, e.g., [9], [21], [22]).”
A unified approach to local trajectory planning and control for autonomous driving along a reference path (2014, background): “The high-level planner is mainly responsible for finding a long-term, collision-free geometric path to reach the goal state by employing graph-based heuristic search (such as Hybrid A* [1], AD* [2]) or random sampling-based motion planning algorithms (such as RRTs [3]), etc.”
Human motion trajectory prediction: a survey (2019, methodology): “Aoude et al. (2010) grow a tree of future trajectories for each target agent using a closed-loop RRT algorithm that samples the controls of a bicycle motion model (Kuwata et al. 2009) avoiding obstacles in the map.”
Sampling-based algorithms for optimal motion planning (2011, methodology): “For example, in many field implementations of sampling-based planning algorithms (see, e.g., Kuwata et al. 2009), it is often the case that since a feasible path is found quickly, additional available computation time is devoted to improving the solution with heuristics until the solution is…”
Local Path Planning for Off-Road Autonomous Driving With Avoidance of Static Obstacles (2012, background): “RRT-based planning algorithms for real-time implementations require efficient guiding heuristics for the sampling configuration [9], [13]–[16].”
Planning and Decision-Making for Autonomous Vehicles (2018, methodology): “(38) computed a cost map of the drivable space of the car and employed the RRT approach to find the path with the lowest cost.”
Sampling-Based Robot Motion Planning: A Review (2014, background): “A high level planner modifies the sampling domain to influence the behavior of a self-driving car by manipulating the Closed Loop RRT (CL-RRT) growth [77].”
Motion Planning for Autonomous Driving: The State of the Art and Future Perspectives (2023, background): “[36] integrate both operations in an iterative loop; HU et al.”