Minimizing Fuel in Multi-Agent Pathfinding

Abstract

The multi-agent pathfinding problem (MAPF) of finding conflict-free paths for multiple agents has attracted a large number of researchers in the past. The cost of the solution is commonly measured by the sum-of-costs (SOC) cost function or, less commonly, by Makespan. In this paper, we focus on the Fuel cost function, which is the number of physical steps the agents traverse. While Fuel was mentioned in many previous papers, our paper is the first to deepen into it. We introduce an A*-based algorithm and a CBS-based algorithm for Fuel. We study Fuel theoretically, showing that it can be (perhaps non-intuitively) more complex than SOC. Finally, we experimentally compare both algorithms against each other and against their SOC counter parts, studying their advantages and disadvantages.