Original title: Multi-agentní hledání cest
Translated title: Multi-agent Path Finding
Authors: Švancara, Jiří ; Barták, Roman (advisor) ; Koenig, Sven (referee) ; Vokřínek, Jiří (referee)
Document type: Doctoral theses
Year: 2020
Language: eng
Abstract: [eng] [cze]
Multi-Agent Path Finding (MAPF) is the task to find efficient collision-free paths for a fixed set of agents. Each agent moves from its initial location to its desired destination in a shared environment represented by a graph. The classical definition of MAPF is very simple and usually does not reflect the real world accurately. In this thesis, we try to add several attributes to the MAPF definition so that we overcome this shortcoming. This is done in several steps. First, we present an approach on how to model and solve MAPF via reduction to Boolean satisfiability using Picat programming language. This provides us with a useful model that can be easily modified to accommodate additional constraints. Secondly, we modify MAPF to portray a more realistic world. Specifically, we allow new agents to enter the shared environment during the execution of the found plan, and we relax the requirement on the homogeneousness of the shared environment. Lastly, we experimentally verify the applicability of the novel models on real robots in comparison with the classical MAPF setting. Zadáním multi-agentního hledání cest (MAPF z anglického multi-agent path finding) je nalézt nekonfliktní cesty pro neměnnou skupinu agentů, kteří se pohybují ve sdíleném prostředí. Každý z agentů je definován svojí výchozí a cílovou polohou. Tato běžná definice MAPF je velice jednoduchá a často nezohledňuje všechny parametry reálného světa, které je potřeba vyřešit, aby byl problém prakticky aplikovatelný. V této práci se snažíme tento nedostatek odstranit tím, že definici rozšíříme o několik parametrů. Toho dosáhneme v několika krocích. Nejprve představíme přístup k řešení MAPF pomocí převodu na splnitelnost Booleovských formulí. Tento přístup modelujeme v programovacím jazyce Picat, který nám poskytuje snadno upravitelný model, do kterého lze přidávat nové podmínky a omezení. Toho využijeme v dalším kroku, kdy upravíme původní zadání MAPF. Zaprvé povolíme, aby do sdíleného prostředí vstupovali noví agenti během exekuce již nalezeného plánu. Zadruhé relaxujeme požadavek na homogenitu sdíleného prostředí, které je běžně reprezentováno neohodnoceným grafem. V poslední části práce provedeme experimentální studii na skutečných robotech, abychom ověřili, že přidané atributy skutečně modelují situaci lépe než klasická definice.
Keywords: Multi-agent Path Finding; Real Robots; Satisfiability; State Search; Multi-agentní hledání cest; Prohledávání stavového prostoru; Reální roboti; Splnitelnost

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/123554

Permalink: http://www.nusl.cz/ntk/nusl-437013


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses