Multi-Agent Systems: New Results for Path Planning and Pattern Formation

Coordinating the behavior of multiple autonomous agents with shared environments is a significant challenge for modern distributed and robotic systems. Applications like automated warehouses, intelligent transportation systems, autonomous vehicles, and robotic swarms require the agents to navigate eciently without colliding with each other and within the environment. This requires algorithmic frameworks such as Multi-Agent Path Finding (MAPF) to coordinate the agents. In this dissertation, we study centralized Multi-Agent Path Finding problem, with a focus on the Anonymous Multi-Agent Path Finding and its extensions to include deadline constraints, capacity constraints, and unbalanced agent and target configurations. We also consider Pattern Formation algorithms for distributed multi- agents. Multi-Agent Path Finding (MAPF) and the Anonymous Multi-Agent Path Find- ing problem, where the agents are indistinguishable with respect to the targets, are the focus of the first part (I) of the dissertation. Although the MAPF prob- lem is computationally intractable, real-world applications introduce practical con- straints, such as deadlines and capacity limits on agents. Part I introduces the Unbalanced Anonymous Multi-Agent Path Finding with Deadlines and Capacities problem (UAMAPFwDC), where the environment involves capacity constraints on the vertices and edges, as well as an unbalanced ratio of agents and targets. This part analyzes the computational complexity of the problem and identifies tractable versions with polynomial- and pseudo-polynomial time algorithms. The experiments validate the results for the problem, showing the potential for real-world applica- tions. Considering the limitations of the above approaches in terms of scalability, the part also proposes a fast heuristic algorithm for the Anonymous MAPF with Indi- vidual Deadlines problem. The algorithm extends the applicability of the swapping approach to the case with individual agent deadlines and is shown to be e↵ective in achieving near-optimal travel costs while also reducing the makespan compared to the optimal solution. This is particularly important in the case of hundreds of agents. The second part II of the dissertation addresses the problem of multi-agent co- ordination from a distributed perspective and proposes a solution to the problem of Pattern Formation in the absence of any central control. The focus is on the prob- lem of Geodesic Mutual Visibility (GMV), in which the agents move on graphs and aim to form configurations such that any two agents are mutually visible and are connected by the shortest paths without any other agent in between. Within this framework, the problem of coordinating oblivious agents using the look-compute- move model is addressed on honeycomb networks. The structural properties of the graphs are analyzed, and an optimal distributed algorithm is proposed to solve the GMV problem for synchronous agents while avoiding collisions between the agents. The solution provides important algorithmic and combinatorial tools to the problem of distributed coordination of multi-agent systems and highlights the directions in which the problem can be solved in the case of other types of graphs and agent movements. Summarizing, the dissertation provides contributions to the problem of multi- agent coordination and brings together the advances bringing together progress in Path Planning and Pattern Formation problems.