Anytime Tree-Based Trajectory Planning for Urban Driving
Christoph Ziegler, Jürgen Adamy
Abstract
The personal mobility of the future will be changed significantly by autonomous driving. To realize this vision, the complex task of trajectory planning needs to be solved. In this article, a novel planning concept, CarPre trajectory planning, based on Monte-Carlo tree search, is presented. Using a speed-dependent steering angle transformation, the state space of a kinematic single track model is discretized. The planner can then choose between different actions, each consisting of a discrete-value pair of an acceleration and a steering rate. With this, an equitemporal search tree is created to compute the future trajectory. Using Monte-Carlo simulations, the influence of short-term actions of the vehicle can be evaluated over a longer planning horizon. Thus, the current best solution can be accessed at any point during computation, enabling real-time applications. Furthermore, the discretized search tree enables easy checking of complex constraints dependent on binary or continuous variables. The concept is verified on a real test vehicle in a lane keeping maneuver. Through initial testing, a pleasant driving experience is perceived, which indicates future acceptance of the real-time capable algorithm.