Empirical Analysis of Hierarchical Pathfinding in Lifelong Multi-Agent Pathfinding with Turns

Abstract

Lifelong multi-agent pathfinding has two interrelated aspects: one is to find conflict-free paths for the agents, and the other is to resolve the conflicts among the agents in the best possible way. We focus on the first aspect by investigating three hierarchical pathfinding approaches, while we apply the same conflict resolution method. We formally present the three pathfinding options: map reduction using fixed waypoints, map reduction using dynamic waypoints, and the classic grid region-based approach. We point out the problem of emerging conflicts in lifelong multi-agent pathfinding with turns. We describe how we evaluate the proposed solutions to example scenarios from the League of Robot Runners competition, and we formulate the goals of the empirical analysis. Based on the experimental results, we point out the need to find the sweet spot between response time and throughput.