Efficient Spatiotemporal Graph Search for Local Trajectory Planning on Oval Race Tracks

Autonomous racing has increasingly become a research subject as it provides insights into dynamic, high-speed situations. One crucial aspect of handling these situations, especially in the presence of dynamic obstacles, is the generation of a collision-free trajectory that represents a safe behavior and is also competitive in the case of racing. We propose a local planning approach that generates such trajectories for a racing car on an oval race track by searching a spatiotemporal graph. A considerable challenge of search-based methods in a spatiotemporal domain is the curse of dimensionality. Therefore, we propose how a previously presented graph structure that is based on intervals instead of discrete values can be searched more efficiently without losing optimality by using a uniform-cost search strategy. We extend the search method to make it anytime-capable so that it can provide a suboptimal trajectory even if the search has to be terminated early. The graph-based planning approach allows us to apply a flexible cost function so that our approach can operate fully autonomously on an oval race track, including the pit lane. We present a cost function for oval racing and explain how the terms contribute to the desired behaviors. This is supported by results with a full-scale prototype.