Improvements in Sub-optimal Solving of the $(N^2-1)$-Puzzle via Joint
  Relocation of Pebbles and its Applications to Rule-based Cooperative
  Path-Finding
  The problem of solving $(n^2-1)$-puzzle and cooperative path-finding (CPF)
sub-optimally by rule based algorithms is addressed in this manuscript. The
task in the puzzle is to rearrange $n^2-1$ pebbles on the square grid of the
size of n x n using one vacant position to a desired goal configuration. An
improvement to the existent polynomial-time algorithm is proposed and
experimentally analyzed. The improved algorithm is trying to move pebbles in a
more efficient way than the original algorithm by grouping them into so-called
snakes and moving them jointly within the snake. An experimental evaluation
showed that the algorithm using snakes produces solutions that are 8% to 9%
shorter than solutions generated by the original algorithm.
  The snake-based relocation has been also integrated into rule-based
algorithms for solving the CPF problem sub-optimally, which is a closely
related task. The task in CPF is to relocate a group of abstract robots that
move over an undirected graph to given goal vertices. Robots can move to
unoccupied neighboring vertices and at most one robot can be placed in each
vertex. The $(n^2-1)$-puzzle is a special case of CPF where the underlying
graph is represented by a 4-connected grid and there is only one vacant vertex.
Two major rule-based algorithms for CPF were included in our study - BIBOX and
PUSH-and-SWAP (PUSH-and-ROTATE). Improvements gained by using snakes in the
BIBOX algorithm were stable around 30% in $(n^2-1)$-puzzle solving and up to
50% in CPFs over bi-connected graphs with various ear decompositions and
multiple vacant vertices. In the case of the PUSH-and-SWAP algorithm the
improvement achieved by snakes was around 5% to 8%. However, the improvement
was unstable and hardly predictable in the case of PUSH-and-SWAP.
