Rudolf Reiter

Systems Control and Optimization Laboratory, Uni. Freiburg

Tuesday, November 12, 2024, 14:00 - 16:00

SR 02-016/18 Geb. 101

Planning feasible trajectories and considering the nonconvex problem of obstacle avoidance pose significant challenges in autonomous driving. The complexity is, among other sources, due to the high-dimensional planning space, combinatorial choices that scale the problem difficulty exponentially, hard realtime requirements, major nonconvexities, and the difficult motion prediction of other vehicles.

This thesis reports on motion planning and obstacle avoidance for autonomous driving. The proposed algorithms address the abovementioned difficulties by utilizing optimization-based methods. Particularly, this thesis proposes to use nonlinear and combinatorial optimization techniques, possibly improved algorithmically by machine learning techniques. The thesis pivots around three main fields within this context: (i) the vehicle model for on-road driving as part of an optimization solver, (ii) strategic decision-making and planning in a highly nonconvex space, and (iii) interactive planning in competitive scenarios. Optimization-based techniques provide the advantages of utilizing model knowledge, providing safety guarantees (or at least safety certifications), and separating the model identification, problem formulation, and solution algorithms. 

The vehicle models for on-road driving are based on road-aligned coordinates. An a priori computation of the road-aligned coordinate transformation curve is proposed to allow numerical optimization algorithms, particularly sequential quadratic programming, to solve the problem efficiently. Due to the numerically favorable properties of collision avoidance in the Cartesian coordinate frame, a novel lifted formulation in both the transformed and the Cartesian configuration states expands the state space. By barely increasing the computation time, the obstacles can be tightly and safely over-approximated within the lifted formulation, as shown in simulations.

A major challenge of obstacle avoidance is the inherent nonconvexity, which, for example, involves the decision of overtaking left or right. Relying purely on discrete planning is burdened by the high-dimensional planning space and suffers from the curse of dimensionality. Mixed-integer optimization utilizes gradients of continuous variables and discrete optimization to find integer assignments in a combined framework. However, the computation time scales exponentially with the number of integer variables. Three motion planning algorithms based on mixed-integer optimization for specific obstacle characteristics are proposed to reduce the online computational burden. For a static environment, a spatial reformulation allows the consideration of a large number of obstacles. The performance of this algorithm was evaluated on a real-world race track on embedded hardware. For structured highway driving, a novel spatio-temporal reformulation significantly reduces the number of integer variables and allows for long-term planning. A final contribution proposes a generic way of learning to predict integer variable assignments by machine learning, enabling real-time planning with high closed-loop performance in the simulated scenarios. 

Besides the challenge of nonconvexity, planning problems stemming from autonomous racing competitions may also comprise the task of obtaining interactive competitive behavior. For this third major field, this thesis contributes with real-time feasible algorithms for planning and predicting other vehicles. A hierarchical approach using reinforcement learning and model predictive control can learn interactive behavior, such as blocking other vehicles from overtaking in simulations. The optimization layer provides safety in this context.