M.Sc Student | Vinogradova Galina |
---|---|

Subject | Aspects of Conflict Resolution and Accommodation in Multi- Agent Systems |

Department | Department of Applied Mathematics |

Supervisor | Professor 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.}