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.

I. Introduction

THE Multi Robot Motion Planning (MRMP) problem is gaining increased attention as many real-world complex applications require collective intelligent behaviors exhibited by multiple robots. The basic MRMP problem is to find start-to-goal paths for a number of robots moving in a space with obstacles, such that they do not collide with obstacles or each other. Space is the most limiting constraint in a typical MRMP problem: often, because of lack of sufficient space around robots, they cannot reach their goals without obstructing each other's way, causing deadlocks. Deadlocks are situations where two or more robots intercept each other's motions and are prevented from reaching their goals. This happens generally in narrow passageways where robots cannot pass by each other.