There are two main approaches to multi-robot motion planning: centralized and decoupled [Lat91]. In the centralized approach, all the robots are grouped together as a single composite robot. Thereafter, the problem reduces to a single robot motion planning problem. The problem with this approach is that usually the resulting composite robot has many degrees of freedom (DOFs), which is quite undesirable given the fact that time complexity of path planning methods grows exponentially with number of DOFs. This issue led to the emergence of the decoupled approach to multi-robot motion planning ([KZ86,EP86, DP89]), where completeness is sacrificed in the favor of time complexity. In the basic decoupled approach, planning is done in two essentially decoupled phases. In the first phase, for each robot, a path is computed which is collision-free with respect to the obstacles in the environment excluding the other robots. Collisions between the robots are resolved in the second phase by velocity tuning, i.e. the velocities of each the robot along their paths, computed in the first phase, are selected in such a way that they avoid any collision with each other along their respective paths. This two phase startegy is inherently an incomplete strategy, because a path may not exist in the velocity space for the motions computed in the first phase, even though there may exist a path in the composite configuration space of all the robots. Even though decoupled planners are inherently incomplete, they have been a prefered approach for the multi-robot motion planning problems because they operate in configuration spaces of much smaller dimensionality, compared to centralized planners.

In a recent study [SL01], it was shown that high failure rates in decoupled multi-robot motion planning make the decoupled planning approach an unsuitable choice, in comparison to the centralized approach, in many practical instances. Motivated by this study, we devised a new multi-robot planning strategy MRP-IC [SI06] in which we partially merge the two stages of the basic decoupled planning approach. Our experimental results show that this new strategy significantly improves upon the reliability of the decoupled planning approach. Overall in our tests, the new strategy outperforms both the centralized and decoupled planning approach, indicating that in practice it can be a better choice, than both the centralized and decoupled approach, for solving multi-robot planning problems.