Inteligentní agenti

Ve výzkumné skupině Inteligentní agenti zkoumáme různé oblasti umělé inteligence týkající se inteligentního rozhodování a řešení úloh v kontextu jednoagentních a multiagentních prostředí. Naší základní filozofií je u zkoumaných konceptů poskytovat důležité teoretické garance, jako jsou úplnost algoritmů, časová a paměťová složitost či vysvětlení učiněných rozhodnutí.

Více o nás

Aplikace
Čemu se skupina věnuje

Témata spadající do našich zájmů zahrnují algoritmy pro plánování a řešení úloh v robotice, hledání cest, multi-agentní hledání cest (MAPF) a jeho generalizace směrem k obecnému plánování pohybu a koordinaci. K řešení zkoumaných problémů se snažíme používat a rozvíjet techniky z výrokové logiky (SAT), z logiky prvního řádu, ze SAT-modulovaných teorií (SMT) a splňování omezení (CSP).

Vybavení

Ozobot evo

Pro testování algoritmů hledání cest máme skupinu malých mobilních robotů Ozobot evo.

Projekty

Inteligentní algoritmy pro zobecněné varianty multi-agetního hledání cest

Program
Standardní projekty
Kód
GA19-17966S
Období
2019 - 2021
Popis
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.

Publikace

Unifying Search-Based and Compilation-Based Approaches to Multi-Agent Path Finding through Satisfiability Modulo Theories

Autoři
Rok
2019
Publikováno
Proceedings of the Twelfth International Symposium on Combinatorial Search. Palo Alto, California: Association for the Advancement of Artificial Intelligence (AAAI), 2019. p. 202-203. 1. vol. 1. ISBN 978-1-57735-808-4.
Typ
Stať ve sborníku
Anotace
We unify search-based and compilation-based approaches to multi-agent path finding (MAPF) through satisfiability modulo theories(SMT). The task in MAPF is to navigate agents in an undirected graph to given goal vertices so that they do not collide. We rephrase Conflict-Based Search (CBS) in the terms of SMT. This idea combines MDD-SAT, a SAT-based optimal MAPF solver, at the low level with conflict elimination of CBS at the high level.

Multi-Agent Path Finding for Large Agents

Autoři
Surynek, P.; Felner, A.; Li, J.; Ma, H.; Koenig, S.; Kumar, S.
Rok
2019
Publikováno
Proceedings of the Twelfth International Symposium on Combinatorial Search. Palo Alto, California: Association for the Advancement of Artificial Intelligence (AAAI), 2019. p. 186-187. 1. vol. 1. ISBN 978-1-57735-808-4.
Typ
Stať ve sborníku
Anotace
Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conflict-Based Search(CBS) is a state-of-the-art MAPF algorithm based on a two-level tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e.g., a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. In this paper, we formalize and study MAPF for large agents that considers the shapesof agents. We present a generalized version of CBS, called Multi-Constraint CBS (MC-CBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. Experimental results show thatall MC-CBS variants significantly outperform CBS. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases.

Všechny publikace

Solving Multi-agent Path Finding on Strongly Biconnected Digraphs

Autoři
Surynek, P.; Bonusi, D.; Botea, A.
Rok
2018
Publikováno
Journal of Artificial Intelligence Research. 2018, 62(1), 273-314. ISSN 1076-9757.
Typ
Článek
Anotace
Much of the literature on suboptimal, polynomial-time algorithms for multi-agent path finding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, traveling on directed graphs is relevant in navigation domains, such as path finding in games, and asymmetric communication networks.

Kde nás najdete?

Výzkumná skupina inteligentních agentů
Katedra aplikované matematiky
Fakulta informačních technologií
České vysoké učení technické v Praze

Místnost TH:A-1433 (Budova A, 14. patro)
Thákurova 9
Praha 6 – Dejvice
160 00

Kontaktní osoba

doc. RNDr. Pavel Surynek, Ph.D.

Za obsah stránky zodpovídá: doc. Ing. Štěpán Starosta, Ph.D.