Optimal Multi-robot Path Finding Algorithm Based on A*

This paper presents an optimal path finding algorithm for a group of robots. Presented approach is based on A* graph traversal algorithm and contains modifications that make it possible to apply strengths of an original algorithm to solve multi-robot path planning problem. Proposed modification is to dynamically change costs of nodes used in path of one robot while planning route for another. In another words to give the cost meaning of a time which robots need to wait to be able to take the node. Although presented approach was used to solve multi-robot path finding problem on unknown map it can be successfully applied to solve navigating problems of group of mobile agents on known maps. Computer simulation showed reliable results for maps of different configuration.