Multiagent Path Finding using Dijkstra Algorithm

The problem of cooperative behavior of a set of agents in an environment given by a directed state graph is considered. The task is to achieve the required balance between the length of the paths of agents and the number of conflicts between agents in the process of passing paths. In the basic formulation of the problem, the conflict between agents is the sharing of identical arcs in the paths of agents. To solve the problem, the classical Dijkstra algorithm is used, which is executed sequentially by each agent. In the course of finding the shortest path, each agent modifies the graph space in such a way as to reduce the likelihood of conflicts with subsequent agents. This approach is original, and a number of computational experiments were performed to verify it using the software developed for this purpose. The conducted experiments demonstrate the adequate behavior of the main algorithm. The paper analyzes the limitations inherent to the proposed approach in the framework of an abstract formulation of the problem. Directions for further development of the basic approach are determined. In particular, an important modification was designed that allows taking into account the conflicts of finding several agents at the same nodes of the graph, as well as a hybrid version.