Joint Movement of Pebbles in Solving the (N2-1)-Puzzle and its Applications in Cooperative Path-Finding: (JAAMAS Extended Abstract)

Moving pebbles jointly in formations called snakes has been integrated into the Parberry's algorithm for solving the (N 2-1)-puzzle sub-optimally in the on-line mode. Using snakes consisting of 2 pebbles that are relocated jointly towards their goal positions after their opportunistic formation yields a measurable reduction of the total number of pebble movements at low extra computational cost. As the N×N-puzzle represents a special case of the cooperative path finding problem (CPF) we also transferred the concept of snake-like movements into the context of two rule-based sub-optimal algorithms for CPF-BIBOX and PUSH-and-SWAP (PUSH-and-ROTATE). The evaluation indicates significant benefit from employing snakes within the BIBOX algorithm and also increasing benefit in PUSH-and-SWAP being applied on biconnected graphs with growing size of ears.