A hierarchical decoupled approach for multi robot motion planning on trees

In this paper, the multi robot motion planning problem is solved through a decoupled approach, where a new algorithm for prioritizing the robots moves is developed. Assuming that the workspace is mapped into a tree graph and the initial and final configurations of robots are known, the robots´ shortest start-to-goal paths on the tree are calculated independently. Then, a new rule-based prioritization scheme is applied in two phases: (a) Path Prioritization, which determines which robot can directly move along its shortest path and which robot should deviate from it, and (b) Motion Prioritization, which decides the order of robots´ sequential moves. Furthermore, an algorithm is presented for minimizing the number of moves by adding extra vertices to the tree.