intALG-MAPFg: Intelligent Algorithms for Generalized Variants of Multi-Agent Path Finding
Project goals
Multi-agent path finding (MAPF) is a task of finding non-colliding paths for multiple distinguishable agents in a graph. The MAPF problem represents an important theoretical challenge but also has many practical applications. Solving techniques for the standard MAPF experienced significant progress recently for both the optimal and the sub-optimal case. This project reflects the growing interest of research community in generalizations of MAPF. Our research aims on study of intelligent solving algorithms in several diverse conceptual directions of MAPF generalizations that are unique to this project. Generalizations in logic formulations of MAPF with focus on expressing MAPF in the SAT modulo theory framework (SMT) and complex local and global constraints are studied. In adversarial variants of MAPF (AMAPF), where multiple teams of agents compete in reaching their goals, the project aims on combination of game-theoretic approach with machine learning. Worthwhile generalizations concern polynomial-time algorithms for MAPF where extensions from undirected to directed case are studied.
Keywords
Multiple agentspath-findingMAPFlogic formulationsSAT-modulo theorySMTproblem generalizationslocal constraintsglobal constraintsMAPF with adversariesAMAPFgame strategiesgame tree samplingmachine learningpolynomial algorithms
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
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
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
Basic information
Recognised costs
2 693 CZK thou.
Public support
2 693 CZK thou.
100%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2019 - 31. 12. 2021