The better analogy when the markers are distinct is not Sokoban, but the well-known [15-puzzle][1]. It is even on an *undirected graph*.

All my remarks below are about the undirected version. (My brief literature search turn up only one paper with directed graphs, for a *single* pebble (robot) with obstacles whose final position is irrelevant.) The upshot is:
> On undirected graphs, the decision version ("Does a solution exist?") is solvable in polynomial time, but minimizing the number of moves is NP-hard.

 There is a short paper by Oded Goldreich, dating back to 1984 but [published][2] only in 2011, "[Finding the shortest move-sequence in the
graph-generalized 15-puzzle is NP-hard][3]". Ratner and Warmuth showed ([Journal of Symbolic Computation, 1990][4]) that this is true even for the extension of the 15-puzzle to larger squares.


Richard Wilson has [characterized][5] in 1974 the cases when a solution is possible, in the case when there are $n-1$ tokens on a general $n$-vertex graph, like in the 15-puzzle.
According to a [recent paper by Gabriele Röger and Malte Helmert][6],
Kornhauser, Miller, and Spirakis (["Coordinating pebble motion on graphs, the diameter of permutation groups, and applications", 1984][7]) have extended these results to the case when fewer vertices are occupied, and showed that there is a solution with $O(n^3)$ moves if there is a solution at all. (I haven't looked at this paper.)

  [1]: http://en.wikipedia.org/wiki/15_puzzle
  [2]: http://dx.doi.org/10.1007/978-3-642-22670-0_1
  [3]: http://www.wisdom.weizmann.ac.il/~oded/COL/puzzle.pdf
  [4]: http://dx.doi.org/10.1016/S0747-7171(08)80001-6
  [5]: http://dx.doi.org/10.1016/0095-8956(74)90098-7
  [6]: http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/viewFile/5407/5197
  [7]: http://dx.doi.org/10.1109/SFCS.1984.715921%20