View article

The computational problem of planning motion for a single robot system had been investigated for some time [5, 6], most recently from an algorithmic view-point [2, 4, 7, 8, 9, 10, 11]. The extension to coordinating motion for several independently moving bodies has only recently been raised. In spite of the importance of coordination problems (eg to get two robot arms to cooperate on a task), very little is understood. We call this the Many (Moo-ing) Bodies Problem. So far, the only type of bodies for which algorithms have been designed are discs [12, 13]. The purpose of this article is to show that this Many Discs Problem is NP-hard in the strong sense (see [l]). Our result should be contrasted with the fact that moving many nonconvex bodies is PSPACE-hard[3].(Apparently, their result can be strengthened so that the bodies are rectangles.)

We remark that discs are the simplest non-trivial objects to study. Thus, discs are …