Multi-Robot-Path-Planning-on-Graphs

Multi-Robot Path Planning on Graphs Solution by A* algorithm

We study the problem of optimal multi-robot path planning on graphs (MPP) over the makespan (last arrival time) criteria. We implemented A* search algorithm to find solution. In an MPP instance, the robots are uniquely labeled (i.e., distinguishable) and are confined to an nxn squared connected graph. The robots may move from a vertex to an adjacent one in one time step in the absence of collision, which may occur when two robots simultaneously move to the same vertex or along the same edge in different directions. A distinguishing feature of our MPP formulation is that we allow robots on fully occupied cycles to rotate synchronously.

To solve above problem, we implemented A* algorithm to find optimum route from given initial 3x3 robot positions and desired 3x3 robot positions. First algorithm starts to construct graph whose connections shows us possible movement. Then we extented it as time based graph. According to time extented graph, all nodes are dublicated for every single of time step. that means if we have 3x3 node for given example, we will have 3x3xts number of node in our time expanded graph for ts time span analysis as we set it ts=7 for our demo. every node in t layer has its own node in (t+1) layer but it has connection to one step far nodes in (t+1) layer as well.