Optimized multi-agent resource extraction

Abstract

Multi-Agent Resource Extraction combines collecting resources with Multi-Agent Pathfinding. For this, multiple agents are coordinated in a graph to remove resources and deposit them into a warehouse. Agents can collide with each other and as long as a resource is not removed, it is an obstacle for the agents. This problem is inspired by real-time strategy computer games, but could also apply to automated warehouses or pickup and delivery problems. In this work, we have studied the complexity of Multi-Agent Resource Extraction for finding a feasible solution as well as finding the fastest possible solution. In this context, we introduced two restrictions to our problem: One where the starting positions are constrained, and another where the capacity of each agent and the size of each resource deposit is limited to one. We showed that finding the fastest possible solution is NP-hard, even if we impose both restrictions. Unlike other related problems, we concluded that deciding if a solution exists is NP-complete. This is still the case when the two restrictions are applied individually. Only by applying both, we were able to find a subset of problems that is not NP-hard. For that subset of problems, we developed an 𝑂(𝑛5) algorithm that finds a feasible solution. As part of this algorithm, we also developed another algorithm that decides whether an agent can reach a specific vertex.