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

All my remarks below are about the undirected version. **ADDITION:** *At the end there is a remark about the application to the directed case*. (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 biconnected $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]) extended these results to the case when fewer vertices are occupied and to more general graphs, 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. Anyway, Röger and Helmert recommend to find more details in the [tech-report][8], which contains Daniel Kornhauser's Master's theses. Let me mention that I don't believe the $\Omega(n^3)$ lower bound proof given there, Theorem 5 on p.42. This is just too close to bubblesort.)

For **directed graphs** which are *biconnected and strongly connected*, one can apply the characterizations of the undirected graph case, because a "backward move" can always be simulated: Let $ab$ be an arc and suppose we would like to move a pebble $X$ from $b$ to $a$.
Find a directed cycle through $ab$ and push the vertices on this cycle through, but don't make the last move of pebble $X$ from $a$ to $b$. This realizes a backward move by $O(n^2)$ forward moves.
This yields a linear-time decision algorithm and an $O(n^5)$ upper bound on the number of moves (when a solution exists) for this digraph class.


  [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
  [8]: http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-320.pdf