2016/10/17 by Pavel Surynek, Surynek, Pavel, Petr Michalík +1
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Data Management and Algorithms #FOS: Computer and information sciences #Robotic Path Planning Algorithms #cs.AI
paper · pdf · doi:10.48550/arxiv.1610.04964
arxiv created 2016/10/17 · openalex publication_date 2016/10/17 · arxiv updated 2016/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of solving (n2-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 n2-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 (n2-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 (n2-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.