Publication

P. Surynek and P. Michalik. The Joint Movement of Pebbles in Solving the (N^2-1)-Puzzle Suboptimally and its Applications in Rule-Based Cooperative Path-Finding. Autonomous Agents and Multi-Agent Systems, 31, (3), 715-763, 2016.

Abstract: 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 NxN 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 percent shorter than solutions generated by the original algorithm.

Download the paper in pdf.