Název:
Řešící algoritmy pro multi-agentní hledání cest s dynamickými překážkami
Překlad názvu:
Solving Algorithms for Multi-agent Path Planning with Dynamic Obstacles
Autoři:
Majerech, Ondřej ; Surynek, Pavel (vedoucí práce) ; Vlk, Marek (oponent) Typ dokumentu: Diplomové práce
Rok:
2017
Jazyk:
eng
Abstrakt: [eng][cze] In this work we present the problem of multi-agent path-finding with dynamic obstacles, a generalisation of multi-agent path-finding (MAPF) in which the environment contains randomly-moving dynamic obstacles. This generalisation can be though of as an abstraction of incomplete knowledge of the environment or as a simplification of the multi-agent path-finding where we do not include all agents in the cooperative planner. We adapt three planning algorithms for MAPF to work in an environment with dy- namic obstacles: Local-Repair A* (LRA*), Windowed Hierarchical Cooper- ative A* (WHCA*) and Operator Decomposition with Independence Detec- tion (OD/ID). In addition, we propose two heuristics for these algorithms in dynamic environments: Path Rejoining and Obstacle Predictor. In our experiments, we find that LRA* and WHCA* are best suited for the dy- namic environment. The Path Rejoining heuristic is successful in improving run-times at a small cost in makespan. Obstacle Prediction is capable of lowering the number of times a plan has to be found, but the overhead of our implementation outweighs any performance benefits in most cases. 1V předložené práci představujeme problém multiagentního hledání cest s dynamickými překážkami, tedy zobecnění multiagentního hledání cest, ve kterém jsou v prostředí náhodně se pohybující překážky. Takové zobecnění lze vnímat jako abstrakce neúplné znalosti o prostředí nebo jako zjednodušení multiagentního hledání cest, kde ne všichni agenti jsou zahrnuti v kooper- ativním algoritmu. Představujeme úpravu tří algoritmů pro multiagentní hledání cest pro prostředí s dynamickými překážkami: Local-Repair A* (LRA*), Windowed Hierarchical Cooperative A* (WHCA*) a Operator De- composition s Independence Detection (OD/ID). Dále představujeme dvě heuristiky pro uvedené algoritmy v dynamickém prostředí: Navracení na cestu a odhad pohybu překážek. V experimentech zjišťujeme, že LRA* a WHCA* se pro dynamické prostředí hodí nejlépe. Navracení na cestu úspěšně zlepšuje čas běhu plánovače za cenu malého prodloužení nalezených cest. Odhad pohybu překážek úspěšně zvládá snížit potřebu hledat nový plán, ale ve většině případů časová náročnost naší implementace převyšuje výkonnostní výhody plynoucí z menšího počtu hledání nových plánů. 1
Klíčová slova:
artificial intelligence; dynamic obstacles; Multi-Agent Path-Finding; artificial intelligence; dynamic obstacles; Multi-Agent Path-Finding