It is hard to find the global optimum of general nonlinear and nonconvex optimization problems in a reasonable time. This article presents a method to transfer the receding horizon control approach, where nonlinear, nonconvex optimization problems are considered, into graph-search problems. Specifically, systems with symmetries are considered to transfer system dynamics into a finite-state automaton. In contrast to traditional graph-search approaches where the search continues until the goal vertex is found, the transfer of a receding horizon control approach to graph-search problems presented in this article allows to solve them in real time. We prove that the solutions are recursively feasible by restricting the graph search to end in accepting states of the underlying finite-state automaton. The approach is applied to trajectory planning for multiple networked and autonomous vehicles. We evaluate its effectiveness in simulation and experiments in the Cyber-Physical Mobility Lab, an open-source platform for networked and autonomous vehicles. We show real-time capable trajectory planning with collision avoidance in experiments on off-the-shelf hardware and code in MATLAB for two vehicles.

Motion planning methods often rely on libraries of primitives. The selection of primitives is then crucial for assuring feasible solutions and good performance within the motion planner. In the literature, the library is usually designed by either learning from demonstration, relying entirely on data, or by model-based approaches, with the advantage of exploiting the dynamical system’s property, e.g., symmetries. In this work, we propose a method combining data with a dynamical model to optimally select primitives. The library is designed based on primitives with highest occurrences within the data set, while Lie group symmetries from a model are analysed in the available data to allow for structure-exploiting primitives. We illustrate our technique in an autonomous driving application. Primitives are identified based on data from human driving, with the freedom to build libraries of different sizes as a parameter of choice. We also compare the extracted library with a custom selection of primitives regarding the performance of obtained solutions for a street layout based on a real-world scenario.

Motion planning for autonomous vehicles is commonly implemented via graph-search methods, which pose limitations to the model accuracy and environmental complexity that can be handled under real-time constraints. In contrast, reinforcement learning, specifically the deep Q-learning (DQL) algorithm, provides an interesting alternative for real-time solutions. Some approaches, such as the (), model the RL-action space by quantizing the continuous control inputs. Here, we propose to use motion primitives, which encode continuous-time nonlinear system behavior as the action space. The novel methodology of motion primitives-DQL planning is evaluated in a numerical example using a single-track vehicle model and different planning scenarios. We show that our approach outperforms a state-of-the-art graph-search method in computation time and probability of reaching the goal.

Trajectory planning for autonomous cars can be addressed by primitive-based methods, which encode nonlinear dynamical system behavior into automata. In this paper, we focus on optimal trajectory planning. Since, typically, multiple criteria have to be taken into account, multiobjective optimization problems have to be solved. For the resulting Pareto-optimal motion primitives, we introduce a universal automaton, which can be reduced or reconfigured according to prioritized criteria during planning. We evaluate a corresponding multi-vehicle planning scenario with both simulations and laboratory experiments.

The computation time required to solve nonconvex, nonlinear optimization problems increases rapidly with their size. This poses a challenge in trajectory planning for multiple networked vehicles with collision avoidance. In the centralized formulation, the optimization problem size increases with the number of vehicles in the networked control system (NCS), rendering the formulation unusable for experiments. We investigate two methods to decrease the complexity of networked trajectory planning. First, we approximate the optimization problem by discretizing the vehicle dynamics with an automaton, which turns it into a graph-search problem. Our search-based trajectory planning algorithm has a limited horizon to further decrease computation complexity. We achieve recursive feasibility by design of the automaton which models the vehicle dynamics. Second, we distribute the optimization problem to the vehicles with prioritized distributed model predictive control (P-DMPC), which reduces the problem size. To counter the incompleteness of P-DMPC, we propose a framework for time-variant priority assignment. The framework expands recursive feasibility to every vehicle in the NCS. We present two time-variant priority assignment algorithms for road vehicles, one to improve vehicle progress and one to improve computation time of the NCS. We evaluate our approach for online trajectory planning of multiple networked vehicles in simulations and experiments.

Trajectory planning techniques form a central step to enable autonomous driving. The motion primitives method generates an automaton of precomputed maneuvers with structure-exploiting properties. Thereby, the trajectory planning problem can be reduced to finding an admissible/optimal sequence of motion primitives. In this chapter, we present ways to designing maneuver automata based on different system models and on either analytical or data-based approaches for automaton generation. Moreover, numerical methods for computing optimal maneuvers are listed and we discuss graph-based planning techniques. A subsequent chapter shows the evaluation of motion primitives automata in the Cyber-Physical Mobility Lab.