Efficient coordinated motion

The problem of efficiently coordinating the motion of multiple objects is examined. It is assumed that there is sufficient space without objects to guarantee a solution. For simplifying the analysis, we also consider all objects to have the same size. A new divide-and-solve technique is proposed for addressing coordinated motion problems. The algorithm suggested divides a problem into subproblems, solves the smaller problems locally, exchanges objects across the local boundaries, and repeats the process until the desired configuration is achieved. It is shown that the average complexity of such an algorithm is much better compared to naive methods for solving this problem.