Cooperative multi-agent multi-target catching

Master thesis (2022)

Authors

S. Waij Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (mentor)
F.A. Oliehoek Interactive Intelligence - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Sander Waij
More Info
expand_more

Published Date

31-01-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Multi-agent multi-target catching is the act of multiple agents trying to catch multiple moving targets. The exact algorithms created for such chases are generally targets that are actively trying to get as far as possible, while the agents try to prevent that. However, these algorithms can get much more efficient whenever targets also want to get caught.
In this thesis, we introduce cooperative multi-agent multi-target catching, where the targets give as much information to the agents as they can to ensure that they get caught as quickly as possible. When targets share their path, agents can calculate where each of the targets can be intercepted and with that, increase the efficiency of the assignments. This leads to about half the number of iterations needed or about two-thirds of the distance that the agents need to travel.
We also introduce two variations: allowing agents to catch multiple targets and using only specific stopping locations. Allowing agents to catch multiple targets slightly lowers both the number of iterations and the agent distance needed. Using only specific stopping locations increases the number of iterations needed, but has next to no effect on the agent distance when using the targets' paths.