  In multi-robot motion planning (MRMP) the aim is to plan the motion of
several robots operating in a common workspace, while avoiding collisions with
obstacles or with fellow robots. The main contribution of this paper is a
simple construction that serves as a lower bound for the computational cost of
a variety of prevalent MRMP problems. In particular we show that optimal
decoupling of multi-robot motion -- decoupling being a standard approach to
practically addressing MRMP -- is NP-hard. The basic problem for which we
present our construction is monotone MRMP, a restricted and natural MRMP
variant, where robots move one by one to their targets with no intermediate
stops. Observing the hardness of these restricted versions of MRMP is
significant as it guides the search for efficient solutions towards techniques
that can cope with intractable problems. Furthermore, our construction
highlights structural properties of difficult instances, such as the need of
robots to pass through many start and target positions of other robots. These
insights can lead to useful problem relaxations resulting in efficient
solutions and to suitable engineering of workspaces.
