English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The problem of solving $(n^2-1)$-puzzle and cooperative path-finding (CPF)sub-optimally by rule based algorithms is addressed in this manuscript. Thetask in the puzzle is to rearrange $n^2-1$ pebbles on the square grid of thesize of n x n using one vacant position to a desired goal configuration. Animprovement to the existent polynomial-time algorithm is proposed andexperimentally analyzed. The improved algorithm is trying to move pebbles in amore efficient way than the original algorithm by grouping them into so-calledsnakes and moving them jointly within the snake. An experimental evaluationshowed 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-basedalgorithms for solving the CPF problem sub-optimally, which is a closelyrelated task. The task in CPF is to relocate a group of abstract robots thatmove over an undirected graph to given goal vertices. Robots can move tounoccupied neighboring vertices and at most one robot can be placed in eachvertex. The $(n^2-1)$-puzzle is a special case of CPF where the underlyinggraph 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 andPUSH-and-SWAP (PUSH-and-ROTATE). Improvements gained by using snakes in theBIBOX algorithm were stable around 30% in $(n^2-1)$-puzzle solving and up to50% in CPFs over bi-connected graphs with various ear decompositions andmultiple vacant vertices. In the case of the PUSH-and-SWAP algorithm theimprovement achieved by snakes was around 5% to 8%. However, the improvementwas unstable and hardly predictable in the case of PUSH-and-SWAP.

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