  We study the parameterized complexity of a generalization of the coordinated
motion planning problem on graphs, where the goal is to route a specified
subset of a given set of $k$ robots to their destinations with the aim of
minimizing the total energy (i.e., the total length traveled). We develop novel
techniques to push beyond previously-established results that were restricted
to solid grids.
  We design a fixed-parameter additive approximation algorithm for this problem
parameterized by $k$ alone. This result, which is of independent interest,
allows us to prove the following two results pertaining to well-studied
coordinated motion planning problems: (1) A fixed-parameter algorithm,
parameterized by $k$, for routing a single robot to its destination while
avoiding the other robots, which is related to the famous Rush-Hour Puzzle; and
(2) a fixed-parameter algorithm, parameterized by $k$ plus the treewidth of the
input graph, for the standard \textsc{Coordinated Motion Planning} (CMP)
problem in which we need to route all the $k$ robots to their destinations. The
latter of these results implies, among others, the fixed-parameter tractability
of CMP parameterized by $k$ on graphs of bounded outerplanarity, which include
bounded-height subgrids.
  We complement the above results with a lower bound which rules out the
fixed-parameter tractability for CMP when parameterized by the total energy.
This contrasts the recently-obtained tractability of the problem on solid grids
under the same parameterization. As our final result, we strengthen the
aforementioned fixed-parameter tractability to hold not only on solid grids but
all graphs of bounded local treewidth -- a class including, among others, all
graphs of bounded genus.
