Od abstraktních k proveditelným plánům

Abstract

Tato práce se zabývá postprocesingem na plánech řešících problém hledání cesty pro více agentů. Účelem postprocesingu je převod plánů na takové, které mohou být snáze prováděny reálnými agenty. Jedná se o snižování plýtvání časem a zavádění robustnosti. Je v ní navrženo pět základních metod, později rozšířených na 10, jejichž prostřednictvím jsou MAPF plány převáděny na významně nižší úroveň abstrakce. Výsledky byly ověřeny na šedesáti plánech na šesti mapách generovaných programem MAPF Scenario. Některé výsledky byly ověřeny na robotech Ozobot Evo. Ukázalo se, že vhodným postprocesingem lze za relativně malou výpočetní cenu výrazně vylepšit kvalitu původních plánů z pohledu rychlosti i bezpečnosti. Zároveň se ukázalo, že jednotlivé navrhované algoritmy jsou užitečné pro různé účely a typy plánů.

This thesis delves into postprocesing on plans for Multi Agent Path Finding. The intent behind postprocesing is to chang the plans so they can be performed by real robots. Changes include reduction in wasted time and introduction of robustness. This thesis proposes five algorithms (later extended to ten), through which MAPF plans are being transfered to a significantly lower level of abstraction. Results were tested on sixty plans created by MAPF solver MAPF Scenatio over five maps. Some resulting plans were tested in real life on robots Ozobot Evo. Results indicate that significantly lower makespan and greater robustness can be achieved through postprocessing. This study also indicates that various algorithms are more effective for certain types of plans.