Multi-agent path finding (MAPF) is the task of finding non-conflicting paths for multiple agents that operate in a environment with shared resources.
Finding an optimal solution quickly becomes intractable for many applications and consequently suboptimal methods are also explored extensively in literature.
This work presents the Decentralized Optimization (DECOP) algorithm: a novel receding horizon control algorithm that exploits insights from MAPF research as well as decentralized control. In the proposed framework, each travelling agent communicates with agents in its proximity to solve a local MAPF problem that considers only a selected tractable number of agents. Inter-agent cooperation and conflict free operation are induced through applying a common local optimization policy during parallel local optimization and through a subsequent path reservation scheme based on random priorities. Inter-agent communication consists of sharing respective route alternatives from which additional information with regard to an agents' entanglement can be inferred which can also be included in the local optimization cost function.
Comparative results with other decentralized algorithms show that the DECOP algorithm yields competitive results while guaranteeing conflict free operations, with limited required communication and without the need of any training time. Among many degrees of freedom to be explored further, including information about the entanglements of an agent's route alternatives in the common policy for local optimization yields an increase in performance and suggests an increased extent of induced cooperation.