The better analogy when the markers are distinct is not Sokoban, but the well-known 15-puzzle. 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.) There is a short paper by Oded Goldreich, dating back to 1984 but published only in 2011, "Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard". Ratner and Warmuth showed (Journal of Symbolic Computation, 1990) that this is true even for the extension of the 15-puzzle to larger squares.
Richard Wilson has characterized in 1974 the cases when a solution is possible, in the case when there are $n-1$ tokens on an $n$-vertex graph, like in the 15-puzzle. According to a recent paper by Gabriele Röger and Malte Helmert, Kornhauser, Miller, and Spirakis ("Coordinating pebble motion on graphs, the diameter of permutation groups, and applications", 1984) 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.)