Real-Time Motion Planning With Applications to Autonomous Urban Driving

Kuwata, Yoshiaki; Karaman, Sertaç; Teo, J.; Frazzoli, Emilio; How, Jonathan P.; Fiore, Gaston · 2009 · OpenAlex-citations

DOI: 10.1109/tcst.2008.2012116

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper presents a real-time motion planning algorithm designed for autonomous vehicles operating in complex, uncertain urban environments. The research was motivated by the challenges faced during the 2007 DARPA Urban Challenge, where vehicles had to navigate paved roads with intersections, traffic, and strict safety rules. Standard motion planning methods often fail to handle the unstable dynamics and significant drift of full-size vehicles in real-time. The authors address this by extending the Rapidly-exploring Random Tree (RRT) algorithm to incorporate closed-loop prediction, ensuring dynamically feasible and safe trajectories. The proposed method, termed Closed-Loop RRT (CL-RRT), integrates a low-level stabilizing controller into the planning process. Instead of sampling raw control inputs, the algorithm samples reference commands (position and speed) for the controller. It then performs forward simulations of the closed-loop system to generate predicted trajectories. This approach reduces prediction errors caused by modeling inaccuracies and allows the planner to handle nonlinear vehicle dynamics. To improve efficiency in structured environments, the algorithm employs biased sampling strategies tailored to specific scenarios, such as lane following, intersection crossing, and U-turns. Node connections are evaluated using Dubins path lengths to account for nonholonomic constraints, and a hybrid heuristic balances exploration of new space with optimization of existing paths. Feasibility is checked against a high-resolution drivability map that encodes obstacles, lane boundaries, and safety penalties. The algorithm was implemented in the planning software for Team MIT’s vehicle, Talos, during the DARPA Urban Challenge. The system successfully completed a 60-mile simulated military supply mission, navigating through high-density traffic with up to 70 simultaneous vehicles. The CL-RRT planner demonstrated the ability to generate feasible trajectories in real-time, allowing the vehicle to obey traffic laws, yield to other vehicles, execute U-turns around blockages, and park in assigned spaces. The use of closed-loop prediction enabled the vehicle to maintain stability and safety despite complex dynamics and limited sensing capabilities. The significance of this work lies in its demonstration that sampling-based motion planning can be effectively applied to dynamic, unstable robotic vehicles in real-world settings. By leveraging closed-loop dynamics and environment-biased sampling, the algorithm achieves a balance between computational efficiency and safety. This approach provides a robust framework for autonomous driving systems that must operate safely alongside human-driven traffic, addressing critical challenges in dynamic obstacle avoidance and rule compliance. The success in the DARPA Urban Challenge validates the practical applicability of CL-RRT for advanced autonomous vehicle control.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• passenger motion sickness comfort