Bachelor's Thesis

Game Theory Applications to UAV Collision Avoidance

Final Thesis 486.01 kB Appendix 2.25 MB

Author of thesis: Marek Přibyl

Acad. year: 2025/2026

Supervisor: Ing. Ivan Eryganov, Ph.D.

Reviewer: Ing. Roman Byrtus

Abstract:

This bachelor thesis deals with the issue of autonomous collision avoidance of unmanned aerial vehicles (UAVs) in a decentralized environment without a superior coordinating authority. With regard to the growing traffic density and current legislative requirements for determinism and safety (e.g., EASA EPAS 2025), a new part of an algorithm based on the principles of non-cooperative game theory and myopic decision-making is proposed. The main contribution of the thesis is the design, derivation, and mathematical analysis of a payoff function, which in real time balances the effort of the autonomous agent to reach the target with the necessity to maintain safe separation from other traffic participants. The presented non-linear model effectively eliminates the shortcomings of existing approaches, such as numerical instability or undesirable distancing from the target destination (the so-called runaway effect). Mathematical analysis proves the existence of an optimum and the boundedness of the gradient of the proposed function, which improves the properties of the numerical solution. The functionality, robustness, and ability of the algorithm to solve multiple conflicts are subsequently verified through a custom simulation environment in the Python language.

Keywords:

unmanned aerial vehicles, UAV, game theory, collision avoidance, myopic decision-making, non-cooperative games, Nash equilibrium, decentralized control, autonomous systems

Date of defence

09.06.2026

Result of the defence

Defended (thesis was successfully defended)

znamkaAznamka

Grading

A

Process of defence

Student prezentoval svou práci, byly přečteny posudky vedoucího a oponenta. Otázky oponenta: 1. V krátkosti zodpovězeno. 2. Zodpovězeno. doc. Hrdina: Délka kroku, vektor aktuálních hodnot, předešlé hodnoty. Vše osvětleno. dr. Trnka: priority hráče a ostatních hráčů - proběhla konstruktivní diskuze

Language of thesis

Czech

Faculty

Fakulta strojního inženýrství

Department

Institute of Mathematics

Study programme

Mathematical Engineering (B-MAI-P)

Composition of Committee

prof. RNDr. Miroslav Doupovec, CSc., dr. h. c. (předseda)
doc. Mgr. Jaroslav Hrdina, Ph.D. (místopředseda)
Mgr. Dominik Trnka, Ph.D. (člen)
doc. Ing. Petr Tomášek, Ph.D. (člen)
doc. RNDr. Libor Žák, Ph.D. (člen)

Supervisor’s report
Ing. Ivan Eryganov, Ph.D.

Student se ve své bakalářské práci zabývá aplikací teorie her na problém vyhýbání se kolizím bezpilotních letounů. Téma je aktuální, interdisciplinární a vyžaduje propojení matematického modelování, teorie her, optimalizace a numerických simulací. Student se s tématem vypořádal velmi dobře a prokázal schopnost samostatně formulovat problém, navrhnout vlastní model, analyzovat jeho matematické vlastnosti a následně jej implementovat v simulačním prostředí.

Práce obsahuje přehled vybraných existujících přístupů, zavedení potřebných pojmů z teorie her, návrh vlastní výplatní funkce a její matematickou analýzu. Za podstatný přínos považuji zejména konstrukci nelineární výplatní funkce, která kombinuje snahu agenta dosáhnout cíle s penalizací nebezpečného přiblížení k ostatním dronům. Student se neomezil pouze na numerickou implementaci, ale zabýval se také existencí optima, spojitostí funkce a ohraničeností gradientu na vhodně definovaném přípustném oboru.

Významnou součástí práce je vlastní simulační prostředí v jazyce Python, ve kterém student porovnává sekvenční, simultánní a centralizovaný přístup. Výsledky jsou vyhodnoceny statisticky pro různé hodnoty parametru gamma, přičemž student diskutuje vliv tohoto parametru na stabilitu optimalizačního procesu, rychlost dosažení cíle i četnost selhání. Oceňuji, že práce nezůstává pouze u teoretického návrhu, ale obsahuje i praktické ověření chování modelu.

Za silnou stránku práce považuji především vlastní invenci studenta při návrhu modelu a schopnost postupně reflektovat nedostatky původních přístupů. Student v průběhu řešení aktivně konzultoval, reagoval na připomínky a prokázal velmi dobrou míru samostatnosti. Téma bylo zpracováno nad rámec běžné bakalářské práce, zejména rozsahem matematického modelování a implementační části.

Práce má i drobné nedostatky. Místy se vyskytují formulačně méně obratné nebo neformální pasáže a některá tvrzení mohla být formulována opatrněji. Rešeršní část je vzhledem k šíři tématu spíše stručnější. Tyto nedostatky však nesnižují celkovou kvalitu práce zásadním způsobem a jsou vyváženy vlastním přínosem, rozsahem řešení a schopností studenta vytvořit funkční model i numerickou simulaci.

Cíle zadání považuji za splněné. Práci doporučuji k obhajobě a hodnotím ji známkou A.
Evaluation criteria Grade
Splnění požadavků a cílů zadání A
Postup a rozsah řešení, adekvátnost použitých metod A
Vlastní přínos a originalita A
Schopnost interpretovat dosažené výsledky a vyvozovat z nich závěry A
Využitelnost výsledků v praxi nebo teorii A
Logické uspořádání práce a formální náležitosti B
Grafická, stylistická úprava a pravopis B
Práce s literaturou včetně citací B
Samostatnost studenta při zpracování tématu A

Grade proposed by supervisor: A

Reviewer’s report
Ing. Roman Byrtus

Práce se zabývá využitím teorie her pro řešení problematiky vyhýbání se kolizím bezpilotních vzdušných prostředků (UAV) v rámci rojů. Jedná se o aktuální téma s vysokou praktickou relevancí vzhledem k rostoucímu počtu autonomních systémů působících ve sdíleném vzdušném prostoru.

Autor v úvodních kapitolách přehledně analyzuje existující přístupy k řešení kolizních situací UAV a následně představuje teoretické základy teorie her potřebné pro další část práce. Teoretický rozbor je zpracován na odpovídající odborné úrovni a vytváří kvalitní základ pro navržené řešení.

Velmi pozitivně hodnotím zejména realizační část práce a provedené simulace. Simulační scénáře jsou navrženy promyšleně, pokrývají různé typy konfliktních situací a umožňují posoudit chování navrženého modelu v reprezentativních podmínkách. Výsledky jsou prezentovány přehledně a jejich interpretace svědčí o dobrém porozumění řešené problematice. Autor rovněž vhodně diskutuje omezení navrženého přístupu a možnosti jeho dalšího rozvoje.

Po formální stránce je práce zpracována velmi dobře. Text je přehledný, logicky strukturovaný a jednotlivé kapitoly na sebe přirozeně navazují. Práce s literaturou odpovídá požadavkům kladeným na bakalářskou práci.

Jedinou významnější připomínku mám k organizaci implementace. Zdrojový kód je soustředěn do jediného souboru, což snižuje jeho přehlednost a zhoršuje možnosti budoucího rozšiřování či údržby. Vzhledem k rozsahu implementace by bylo vhodnější rozdělit jednotlivé funkcionality do více modulů. Tato připomínka však nemá zásadní vliv na dosažené výsledky ani na celkovou kvalitu práce.

Jelikož byly všechny cíle práce splněny na výbornou, doporučuji práci k obhajobě s celkovým hodnocením A.
Evaluation criteria Grade
Splnění požadavků a cílů zadání A
Postup a rozsah řešení, adekvátnost použitých metod A
Vlastní přínos a originalita A
Schopnost interpretovat dosaž. výsledky a vyvozovat z nich závěry A
Využitelnost výsledků v praxi nebo teorii A
Logické uspořádání práce a formální náležitosti A
Grafická, stylistická úprava a pravopis A
Práce s literaturou včetně citací A
Topics for thesis defence:
  1. Jen pro představu, jaká je zhruba výpočetní náročnost implementovaných algoritmů (třeba skrze výpočetní čas)?
  2. Existují open source řešení problematiky, se kterým by se Vaše implementace dala porovnat?

Grade proposed by reviewer: A

Responsibility: Mgr. et Mgr. Hana Odstrčilová