Řešící algoritmy pro multi-agentní hledání cest s dynamickými překážkami

Majerech, Ondřej

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. 1

host :: přihlásit Digitální repozitář
		Hledej		Nový záznam		Nápověda		O repozitáři