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

Robots are increasingly utilized in industry for their capability to perform repetitive,complex tasks in environments unsuitable for humans. This surge in robotic applicationshas spurred research into Multi-Robot Systems (MRS), which aim to tackle complex tasksrequiring collaboration among multiple robots, thereby boosting overall efficiency. However,MRS introduces multifaceted challenges that span various domains, including robot perception,localization, task assignment, communication, and control. This dissertation delves into theintricate aspects of task assignment and path planning within MRS.The first area of focus is on multi-robot navigation, specifically addressing the limitationsinherent in current Multi-Agent Path Finding (MAPF) models. Traditional MAPF solutionstend to oversimplify, treating robots as holonomic units on grid maps. While this approachis impractical in real-world settings where robots have distinct geometries and kinematicrestrictions, it is important to note that even in its simplified form, MAPF is categorized as anNP-hard problem. The complexity inherent in MAPF becomes even more pronounced whenextending these models to non-holonomic robots, underscoring the significant computationalchallenges involved. To address these challenges, this thesis introduces a novel MAPF solverdesigned for non-holonomic, heterogeneous robots. This solver integrates the hybrid A*algorithm, accommodating kinematic constraints, with a conflict-based search (CBS) for efficientconflict resolution. A depth-first search approach in the conflict tree is utilized to accelerate theidentification of viable solutions.The second research direction explores synergizing task assignment with path-finding inMRS. While there is substantial research in both decentralized and centralized task assignmentstrategies, integrating these with path-finding remains underexplored. This dissertation evaluatesdecoupled methods for sequentially resolving task assignment and MAPF challenges. Oneproposed method combines the Hungarian algorithm and a Traveling Salesman Problem (TSP)solver for swift, albeit suboptimal, task allocation. Subsequently, robot paths are generatedindependently, under the assumption of collision-free navigation. During actual navigation, aNonlinear Model Predictive Controller (NMPC) is deployed for dynamic collision avoidance. Analternative approach seeks optimal solutions by conceptualizing task assignment as a MultipleTraveling Salesman Problem (MTSP), solved using a simulated annealing algorithm. In tandem,CBS is iteratively applied to minimize the cumulative path costs of the robots.

Multi-Agent Path Finding (MAPF) is the task to find efficient collision-free paths for a fixed set of agents. Each agent moves from its initial location to its desired destination in a shared environment represented by a graph. The classical definition of MAPF is very simple and usually does not reflect the real world accurately. In this thesis, we try to add several attributes to the MAPF definition so that we overcome this shortcoming. This is done in several steps. First, we present an approach on how to model and solve MAPF via reduction to Boolean satisfiability using Picat programming language. This provides us with a useful model that can be easily modified to accommodate additional constraints. Secondly, we modify MAPF to portray a more realistic world. Specifically, we allow new agents to enter the shared environment during the execution of the found plan, and we relax the requirement on the homogeneousness of the shared environment. Lastly, we experimentally verify the applicability of the novel models on real robots in comparison with the classical MAPF setting.

Society today brings a high pace development and demand of Artificial intelligence systems as well as robotics. To further expand and to take one step closer to have Unmanned Aerial Vehicles (UAVs) working in the cities, the European Union Aviation Safety Agency launched a project that introduces U-space airspace, an airspace where UAVs, for instance, are allowed to operate for commercial services.The problems defined for U-space airspace resemble problems defined in the area of multi-agent path finding, such as scaling and traffic etc., resulting an interest to research whether MAPF-solutions can be applied to U-space scenarios. The following thesis extends the state-of-the-art MAPF-algorithm Continuous-time Conflict based search (CCBS) to handle simplified U-space scenarios, as well as extend other A*-based algorithms, such as a version of the Receding Horizon Lattice-based Motion Planning named Extended Multi-agent A* algorithm with Wait-Time (EMAWT) and an extended A* named Extended Multi-agent A* algorithm (EMA) to handle them. Comparisons of the three algorithms resulted in the EMAWT being the most reliable and stable solution throughout all tests, whilst for fewer agents, the CCBS being the clear best solution.

Scheduling allocates scarce resources to activities such that certain constraints are satisfied and specific objectives are optimized. The activities to be executed are com- monly known or determined a priori in the planning stage. To improve the flexibility of scheduling systems, the concept of optional activities was invented. Optional activities are those activities whose presence in the resulting schedule is to be decided. Rather than determining which activities need to be executed and scheduling them in two consecu- tive phases, flexibility and efficiency can be improved significantly when both activity selection and time allocation are integrated within the same solver. Such an approach was implemented in a few Constraint Programming solvers and manifested great perfor- mance on multiple scheduling problems. In this thesis, we apply the concept of optional activities to scheduling problems that do not seem to involve optional activities, such as the production scheduling problem with sequence-dependent non-overlapping setups, but also on problems beyond the scheduling domain, such as the multi-agent path finding problem and its extension with weighted and capacitated arcs. 1