The joint movement of pebbles in solving the (\(N^2-1\))-puzzle suboptimally and its applications in rule-based cooperative path-finding

摘要

The present paper deals with the problem of solving the (\(n^2 - 1\))-puzzle and cooperative path-finding (CPF) problems sub-optimally by rule-based algorithms. To solve the puzzle, we need to rearrange \(n^2 - 1\) pebbles in the \(n \times n\)-sized square grid using one vacant position to achieve the goal configuration. An improvement to the existing polynomial-time algorithm is proposed and experimentally analyzed. The improved algorithm represents an attempt to move pebbles in a more efficient way compared to the original algorithm by grouping them into so-called snakes and moving them together as part of a snake formation. An experimental evaluation has shown that the snakeenhanced algorithm produces solutions which are 8–9 % shorter than the solutions generated by the original algorithm. Snake-like movement has also been integrated into the rule-based algorithms used in solving CPF problems sub-optimally, which is a closely related task. The task in CPF consists in moving a group of abstract robots on an undirected graph to specific vertices. The robots can move to unoccupied neighboring vertices; no more than one robot can be placed in each vertex. The (\(n^2 - 1\))-puzzle is a special case of CPF where the underlying graph is a 4-connected grid and only one vertex is vacant. Two major rule-based algorithms for solving CPF problems were included in our study—BIBOX and PUSH-and-SWAP (PUSH-and-ROTATE). The use of snakes in the BIBOX algorithm led to consistent efficiency gains of around 30 % for the (\(n^2 - 1\))-puzzle and up to 50 % in for CPF problems on biconnected graphs with various ear decompositions and multiple vacant vertices. For the PUSH-and-SWAP algorithm, the efficiency gain achieved from the use of snakes was around 5–8 %. However, the efficiency gain was unstable and hardly predictable for PUSH-and-SWAP.