Název: Multi-agentní hledání cest v orientovaných prostředích
Překlad názvu: Multi-agent Path Planning in Unidirectional Environments
Autoři: Švancara, Jiří ; Surynek, Pavel (vedoucí práce) ; Barták, Roman (oponent)
Typ dokumentu: Diplomové práce
Rok: 2016
Jazyk: cze
Abstrakt: [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)

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/83051

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-352700


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce