M.Sc Thesis

M.Sc StudentVinogradova Galina
SubjectAspects of Conflict Resolution and Accommodation in Multi-
Agent Systems
DepartmentDepartment of Applied Mathematics
Supervisor PROF. Michael Heymann


A key part of Air Traffic Management (ATM) research involves the study of conflict resolution among airplanes competing for airspace. In this thesis we view airplanes as autonomous entities that are allowed to choose the optimal routes to their designated destinations (Free Flight). The type of conflict  resolution we discuss here is characterized by efficiency of airspace utilization, where being efficient means having the greatest number of airplanes safely in the air. In this thesis we use a multi-agent system approach to the problem of conflict resolution through efficient airspace utilization. In the system airplanes are represented by autonomous selfish agents that have individual tasks to move from source points to destination points using routes they have chosen. The agents share common resources  representing airspace areas at given points in time. In our system only one agent is allowed to occupy a resource, and an agent, while executing its task, cannot be suspended or stopped.


It turns out that the question of whether there is a way to resolve conflicts such that all agents can  execute their tasks simultaneously is NP-hard. Moreover, the problem of resolving conflicts such that  maximally efficient space utilization is achieved is equivalent to a maximum clique problem. These findings suggest that the studied problem and its approximation are NP-hard. The reduction we present  here allows us to apply to this problem any existing solution of the well-studied maximum clique problem, ranging from exact solutions to fast heuristics. We show, however, that for some of our multi-agent systems the problems can be solved in terms of bipartite matching in polynomial time.


We also address an accommodation problem whose objective is to accommodate idle agents in the system of agents whose conflicts have been resolved, and whose tasks are currently being executed.

The literature offers an algorithm for solving the problem for a single idle agent. We give an optimal  algorithm for accommodation of idle whose performance, in the case of a single agent, is better than that of the above mentioned algorithm by an exponential factor. The algorithm yields a maximal solution, wherein maximal means that the number of agents accommodated in the solution cannot  be increased without removing other agents from the solution. We also show how the accommodation algorithm can be used to solve an accommodation problem in systems with prioritization of agents over common resources.