Robust multi-agent path finding

Práce se věnuje hledání robustních nekonfliktních cest v multi-agent path finding (MAPF). Představíme zde několik nových technik pro konstrukci těchto cest a popíšeme jejich vlastnosti. Budeme se zabývat použitím techniky plánování s alternativami, na základě níž vytvoříme pro agenty stromový plán, přičemž konkrétní průchod si agenti zvolí na základě aktuálního zpoždění během cesty. Dále představíme algoritmus zvyšující robustnost při zachování původní délky řešení a zkombinujeme ho s předchozím přístupem. Věnovat se budeme také metodě zvyšující robustnost pomocí změn rychlosti agentů. Následně experimentálně ověříme použitelnost všech technik na různých typech grafů. Ukážeme, že navržené metody jsou výrazně robustnější než klasické řešení a jisté výhody mají i oproti doposud známým konstrukcím robustních plánů.The thesis is devoted to finding robust non-conflict paths in multi-agent path finding (MAPF). We propose several new techniques for the construction of these types of paths and describe their properties. We deal with the use of contingency planning and we create a tree plan for the agents where the specific path is chosen by the agents during the execution based on the current delay. Next we present an algorithm that increases robustness while maintaining the original length of the solution and we combine it with the previous approach. Then we will focus on the method of increasing robustness by changing the speed of agents. Finally we experimentally verify the applicability of these techniques on different types of graphs. We will show that all the proposed methods are significantly more robust than the classic solution and they also have certain advantages over previously known constructions of robust plans.Katedra teoretické informatiky a matematické logikyDepartment of Theoretical Computer Science and Mathematical LogicFaculty of Mathematics and PhysicsMatematicko-fyzikální fakult