In this work we present the problem of multi-agent path-finding with dynamic obstacles, a generalisation of multi-agent path-finding (MAPF) in which the environment contains randomly-moving dynamic obstacles. This generalisation can be though of as an abstraction of incomplete knowledge of the environment or as a simplification of the multi-agent path-finding where we do not include all agents in the cooperative planner. We adapt three planning algorithms for MAPF to work in an environment with dy- namic obstacles: Local-Repair A* (LRA*), Windowed Hierarchical Cooper- ative A* (WHCA*) and Operator Decomposition with Independence Detec- tion (OD/ID). In addition, we propose two heuristics for these algorithms in dynamic environments: Path Rejoining and Obstacle Predictor. In our experiments, we find that LRA* and WHCA* are best suited for the dy- namic environment. The Path Rejoining heuristic is successful in improving run-times at a small cost in makespan. Obstacle Prediction is capable of lowering the number of times a plan has to be found, but the overhead of our implementation outweighs any performance benefits in most cases. 1

No description available.

This compilation thesis presents an overarching framework on the utilization of nonlinear model predictive control(NMPC) for various applications in the context of Unmanned Aerial Vehicle (UAV) path planning and collision avoidance. Fast and novel optimization algorithms allow for NMPC formulations with high runtime requirement, as those posed by controlling UAVs, to also have sufficiently large prediction horizons as to in an efficient manner integrate collision avoidance in the form of set-exclusion constraints that constrain the available position-space of the robot. This allows for an elegant merging of set-point reference tracking with the collision avoidance problem, all integrated in the control layer of the UAV. The works included in this thesis presents the UAV modeling, cost functions, constraint definitions, as well as the utilized optimization framework. Additional contributions include the use case on multi-agent systems, how to classify and predict trajectories of moving (dynamic) obstacles, as well as obstacle prioritization when an aerial agent is in the precense of more obstacles, or other aerial agents, than can reasonably be defined in the NMPC formulation. For the cases of dynamic obstacles and for multi-agent distributed collision avoidance this thesis offers extensive experimental validation of the overall NMPC framework. These works push the limits of the State-of-the-Art regarding real-time real-life implementations of NMPC-based collision avoidance. The works also include a novel RRT-based exploration framework that combines path planning with exploration behavior. Here, a multi-path RRT * planner plans paths to multiple pseudo-random goals based on a sensor model and evaluates them based on the potential information gain, distance travelled, and the optimimal actuation along the paths.The actuation is solved for as as the solutions to a NMPC problem, implying that the nonlinear actuator-based and dynamically constrained UAV model is considered as part of the combined exploration plus path planning problem. To the authors best knowledge, this is the first time the optimal actuation has been considered in such a planning problem. For all of these applications, the utilized optimization framework is the Optimization Engine: a code-generation framework that generates a custom Rust-based solver from a specified model, cost function, and constraints. The Optimization Engine solves general nonlinear and nonconvex optimization problems, and in this thesis we offer extensive experimental validation of the utilized Proximal-Averaged Newton-type method for Optimal Control (PANOC) algorithm as well as both the integrated Penalty Method and Augmented Lagrangian Method for handling the nonlinear nonconvex constraints that result from collision avoidance problems.