Original title:
Multi-agentní hledání cest v orientovaných prostředích
Translated title:
Multi-agent Path Planning in Unidirectional Environments
Authors:
Švancara, Jiří ; Surynek, Pavel (advisor) ; Barták, Roman (referee) Document type: Master’s theses
Year:
2016
Language:
cze Abstract:
[cze][eng] V této práci se zaměříme na optimální multi-agentní plánování cest, které je NP-úplným problémem. K řešení této úlohy budeme využívat centralizovaný prohledávací algoritmus A*, pro který navrhneme novou heuristiku. Ke konstrukci námi navržené heuristiky zkoumáme řešení multi-agentního plánování pomocí převodu na multi-komoditní tok, který je také NP-úplným problémem. Naše heuristika spočívá v relaxaci multi-komoditního toku na jedno-komoditní tok, který lze řešit v polynomiálním čase. Ukážeme, že takto vybudovaná heuristika je přípustná a konzistentní. Dále také ukážeme typy zadání, pro které je naše heuristika úspěšnější než jiné heuristiky. Powered by TCPDF (www.tcpdf.org)In this paper we focus on the optimal multi-agent path planning, which is an NP-complete problem. To solve this task, we will use centralized A* search algorithm for which we propose a new heuristic. To construct our proposed heuristic, we examine the solution of multi-agent path planning via its reduction to multi-commodity flow, which is also an NP-complete problem. Our heuristic is based on relaxation of multi-commodity flow to single-commodity flow that can be solved in polynomial time. We show that this new heuristics is admissible and consistent. We also show types of problems for which our heuristic is more successful than other heuristics. Powered by TCPDF (www.tcpdf.org)
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/83051