  We study the problem of motion planning for a collection of $n$ labeled unit
disc robots in a polygonal environment. We assume that the robots have
revolving areas around their start and final positions: that each start and
each final is contained in a radius $2$ disc lying in the free space, not
necessarily concentric with the start or final position, which is free from
other start or final positions. This assumption allows a weakly-monotone motion
plan, in which robots move according to an ordering as follows: during the turn
of a robot $R$ in the ordering, it moves fully from its start to final
position, while other robots do not leave their revolving areas. As $R$ passes
through a revolving area, a robot $R'$ that is inside this area may move within
the revolving area to avoid a collision. Notwithstanding the existence of a
motion plan, we show that minimizing the total traveled distance in this
setting, specifically even when the motion plan is restricted to be
weakly-monotone, is APX-hard, ruling out any polynomial-time
$(1+\epsilon)$-approximation algorithm.
  On the positive side, we present the first constant-factor approximation
algorithm for computing a feasible weakly-monotone motion plan. The total
distance traveled by the robots is within an $O(1)$ factor of that of the
optimal motion plan, which need not be weakly monotone. Our algorithm extends
to an online setting in which the polygonal environment is fixed but the
initial and final positions of robots are specified in an online manner.
Finally, we observe that the overhead in the overall cost that we add while
editing the paths to avoid robot-robot collision can vary significantly
depending on the ordering we chose. Finding the best ordering in this respect
is known to be NP-hard, and we provide a polynomial time $O(\log n \log \log
n)$-approximation algorithm for this problem.
