intALG-MAPFg: Intelligent Algorithms for Generalized Variants of Multi-Agent Path Finding
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 23 (SGA0201900001)
Main participants
České vysoké učení technické v Praze / Fakulta informačních technologií
Contest type
VS - Public tender
Contract ID
19-17966S
Alternative language
Project name in Czech
intALG-MAPFg: Inteligentní algoritmy pro zobecněné varianty multi-agetního hledání cest
Annotation in Czech
V multi-agentním hledání cest (MAPF) je úkolem najít vzájemně nekolidující cesty v grafu pro skupinu rozlišitelných agentů. Problém MAPF představuje důležitou teoretickou výzvu a zároveň má mnoho praktických aplikací. Významného pokroku bylo v poslední době dosaženo v řešících technikách jak pro optimální, tak pro neoptimální případ problému. Tento projekt odráží vzrůstající zájem výzkumné komunity o zobecnění problému MAPF. Náš výzkum je zaměřen na studium inteligentních řešících algoritmů v několika různorodých směrech zobecňování problému MAPF, které jsou unikátní pro tento projekt. Jsou studována zobecnění v logickém vyjádření úlohy MAPF se zaměřením na složité lokální a globální podmínky založené na SAT-modulovaných teoriích (SMT). V rámci úlohy MAPF s protivníkem, kdy více týmů agentů soupeří v dosažení svých cílů, se projekt zabývá kombinací teorie her se strojovým učením. Užitečná zobecnění souvisejí také s algoritmy pro MAPF s polynomiálním časem, kde studujeme rozšíření z neorientovaných na orientované grafy.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
CEP - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
AF - Documentation, librarianship, work with information<br>BC - Theory and management systems<br>BD - Information theory<br>IN - Informatics
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project produced significant results in the area of multi-agent path finding (MAPF), especially when using logical reasoning based on applying SAT/SMT-solving in the given area and further in solving a generalisation of MAPF with continuous time by using newly proposed sparse decision diagrams. The results were published at high-quality conferences, including venues of top quality worldwide.
Solution timeline
Realization period - beginning
Jan 1, 2019
Realization period - end
Dec 31, 2021
Project status
U - Finished project
Latest support payment
Mar 31, 2021
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP22-GA0-GA-U
Data delivery date
Jun 29, 2022
Finance
Total approved costs
2,693 thou. CZK
Public financial support
2,693 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK