The thesis is devoted to finding robust non-conflict paths in multi-agent path finding (MAPF). We propose several new techniques for the construction of these types of paths and describe their properties. We deal with the use of contingency planning and we create a tree plan for the agents where the specific path is chosen by the agents during the execution based on the current delay. Next we present an algorithm that increases robustness while maintaining the original length of the solution and we combine it with the previous approach. Then we will focus on the method of increasing robustness by changing the speed of agents. Finally we experimentally verify the applicability of these techniques on different types of graphs. We will show that all the proposed methods are significantly more robust than the classic solution and they also have certain advantages over previously known constructions of robust plans.

Throughout today’s society, increasingly more areas are being automated. Grocery stores however have been the same for years. Only recently, self-checkout counters and online shopping have been utilised in this business area. This thesis aims to take it to the next step by introducing automated grocery stores using a multi-agent system. Orders will be given to the system, and on a small area, multiple agents will pick the products in a time-efficient way and deliver them to the customer. This can both increase the throughput but also decrease the food waste and energy consumption of grocery stores. This thesis investigates already existing solutions for the multi-agent pickup and delivery problem. It extends these to the important case of batched tasks in order to improve the customer experience. Batches of tasks represent shopping carts, where fast completion of whole batches gives greater customer satisfaction. This notion is not mentioned in related work, where completion of single tasks is the main goal. Because of this, the existing solution does not accommodate the need of batches or the importance of completing whole batches fast and in somewhat linear order. For this purpose, a new metric called batch ordering weighted error (BOWE) was created that takes these factors into consideration. Using BOWE, one existing algorithm has been extended into prioritizing completing whole batches and is now called B-PIBT. This new algorithm has significantly improved BOWE and even batch service time for the algorithm in key cases and is now superior in comparison to the other state-of-the-art algorithms.

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.

The rising interest in autonomous systems has emphasized the significance of effective path and motion planning, particularly in coordinating multiple Unmanned Areal Vehicles (UAVs) in missions. An important research field is the problem of Multi-Agent Path Finding (MAPF), in which the objective is to find collision-free paths for multiple agents simultaneously. Various algorithms, categorized into optimal, bounded sub-optimal, and unbounded sub-optimal solvers, have been investigated in order to address MAPF problems. However, recent attention has shifted towards MAPF with kinematic constraints, particularly focusing on nonholonomic agents like cars and fixed-wing UAVs. These nonholonomic agents, distinguished by their motion constraints, require specialized methods for trajectory planning.  To investigate the potential of MAPF with nonholonomic agents, two MAPF algorithms have been implemented, incorporating the kinematic constraints of a fixed-wing UAV. The first algorithm is a UAV-like Conflict-Based Search (CBS) algorithm, belonging to the optimal MAPF solver class, and is based on a Car-like CBS algorithm. The second algorithm is a Prioritized Planner, belonging to the search-based MAPF solver class. Both algorithms utilize a common single-agent search algorithm, the Spatiotemporal Hybrid A* (SHA*), which has been enhanced to incorporate a kinematic bicycle model. This enhancement allows for a greater variety of motions, creates feasible paths for fixed-wing UAVs, and enables control over acceleration and steering rates. A comparison of the two MAPF algorithms was conducted for three different map instances. Furthermore, the use of weighted heuristics, resampling and distance-based priority have been implemented and simulated with the Prioritized Planner. Additionally, two methods of simultaneous arrival have been implemented using the UAV-like CBS, where agents have a fixed time of arrival and a variable time of arrival. The results from the simulations confirm the trade-offs between both MAPF algorithms concerning solution quality, success rate and runtime. The UAV-like CBS is capable of finding solutions of higher quality, while the Prioritized Planner is faster at finding solutions and more efficient for an increasing number of agents. However, the performance of the two algorithms varied significantly, depending on the scenario. The thesis concludes that both algorithms can be utilized for MAPF with nonholonomic fixed-wing UAVs, and that the UAV-like CBS is the best choice for a lower amount of agents, while the Prioritized Planner is preferable for a higher amount of agents. The priority of the agents has been shown to be important, and by allowing resampling, the success rate of the Prioritized Planner can be increased significantly. Additionally, simultaneous arrival at the goal position can be achieved optimally for the UAV-like CBS by solving the problem backwards.