The aim of this project is to solve some instances of the sliding tile puzzle with the aid of AI Planning techniques. In particular, the work focuses on developing a domain and some instances of the problem in PDDL. The presentation is organized as follows. Firstly, it presents the approach used during the development phases. Secondly, it provides an overview about the domain and the problem instances, with documentation of the PDDL domain file and description of the domains utilized as reference. Thirdly, the planners selected for the assignment are briefly described, along with some quick information about the compilation / build phases and the CLI launch commands for solving the problems. Lastly, the results of the planning tasks are proposed along with a critical analysis of what is obtained.
The problem was developed with a classical planning approach, so predicates depicting states in the state-space are boolean variables. A ‘closed-world assumption’ was used, as only the predicates regarding true facts were coded for both domain and problem instances. About the development methodology, it followed an iterative approach. For each action, an initial understanding of the action requirements was done by trying applications on easy problems with paper and pen. The code implementation was done via the editor tool of planning.domains, tested on some elementary instances and eventually debugged. Subsequently, an analysis of what was implemented was carried out, with the idea of evaluating the outcome, finding potential flaws and correcting them. Also, some PDDL models were studied before the implementation and used as references. The most influential are:
- The implementations of the sliding tile problem found at:
- https://github.com/SoarGroup/Domains-Planning-Domain-Definition-Language/blob/master/pddl/slidetile.pddl
- https://github.com/SoarGroup/Domains-Planning-Domain-Definition-Language/blob/master/pddl/eight01x.pddl
- Some domains available from the ‘All-IPC (STRIPS)’ folder in planning.domains. In particular:
- Blocks-reduced
- Gripper
- Logistics00-reduced
- Peg-solitaire
There is a board that contains tiles of different kinds, represented by letters. One of those is the empty tile, represented by the X letter. The problem consists of finding a plan to reach a goal state from an initial state by swapping horizontally or vertically two adjacent tiles at a time. To solve the problem, there are some rules that must be followed. Only two tiles that are adjacent horizontally or vertically can be swapped. When they are swapped, the two tiles switch their coordinates. Not all kinds of tiles are movable; if one tile is not movable it cannot be swapped in any direction. Every time three tiles of the same type are aligned horizontally or vertically, all of them can be transformed into the empty tile. Lastly, there are some particular tile pairs - named special pairs for simplicity. When the tiles that compose a special pair is swapped, one tile of the two is transformed into the empty tile.
In the current implementation, four PDDL files were created, one for the domain and three for the problem instances. The domain is composed of six actions, which make use of three types and six predicates.
The types are:
- tile - the tile type. In the current implementation, it can take one value among the set (G, S, R, H, X), with X representing the ‘empty’ tile
- row - the row coordinate of the position of the tile on the board
- column - the column coordinate of the position of the tile on the board
The predicates are:
- tile_at ?row ?col ?tile - links the tile type ?tile to its row and column coordinates ?row ?col
- adjacent-rows ?row1 ?row2 - whether the two rows ?row1 and ?row2 are adjacent
- adjacent-columns ?col1 ?col2 - whether the two columns ?col1 and ?col2 are adjacent
- movable ?tile - whether a tile type can be moved or not. This predicate was introduced as it is asked that the types S, G, R, H should move while the empty tile X should not
- empty ?tile - true if ?tile is the empty tile
- magically-disappears ?tile1 ?tile2 - This predicate links the two tiles ?tile1 and ?tile2. It is used to encode the required condition of S becoming ‘empty’ once switched with G for magical reasons and it is used within the swap-up-down-special and swap-left-right-special actions.
The actions of the domain are the following:
-
swap-up-down
parameters (?col - col ?tile1 ?tile2 - tile ?row1 ?row2 - row)
If two tiles ?tile1 ?tile2 are movable and are not the same tile type, have the same column coordinate ?col, have adjacent row coordinates ?row1 ?row2 and their types do not make true a (magically-disappear ?tile1 ?tile2) predicate, their row coordinates are swapped -
swap-left-right
parameters (?row1 - row ?tile1 ?tile2 - tile ?col1 ?col2 - col)
If two tiles ?tile1 ?tile2 are movable and are not the same tile type, have the same row coordinate ?row1, have adjacent column coordinates ?col1 ?col2 and their types do not make true a (magically-disappear ?tile1 ?tile2) predicate, their column coordinates are swapped -
swap-up-down-special
parameters (?col1 - col ?tile1 ?tile2 - tile ?row1 ?row2 - row ?empty - tile)
If two tiles ?tile1 ?tile2 are movable and are not the same tile type, have the same column coordinate ?col1, have adjacent row coordinates ?row1 ?row2 and make true a (magically-disappear ?tile1 ?tile2) predicate, then swap their row coordinates and and transform ?tile2 into the ‘empty’ tile X -
swap-left-right-special
parameters (?row1 - row ?t1 ?t2 - tile ?col1 ?col2 - col ?empty - tile)
If two tiles ?tile1 ?tile2 are movable and are not the same tile type, have the same row coordinate ?row1, have adjacent column coordinates ?col1 ?col2 and make true a (magically-disappear ?tile1 ?tile2) predicate, then swap the column coordinates and transform ?tile2 into the ‘empty’ tile X -
match-three-row
parameters (?tile1 - tile ?r1 - row ?c1 ?c2 ?c3 - col ?empty - tile)
If three tiles of the same type ?t1 are not ‘empty’, have the same row coordinate ?row1, and their column coordinates ?col1 ?col2 ?col3 are adjacent two by two, then all three tiles are transformed into ‘empty’ tiles X -
match-three-column
parameters (?t1 - tile ?col1 - col ?row1 ?row2 ?row3 - row ?empty - tile)
If three tiles of the same type ?t1 are not ‘empty’, have the same column coordinate ?col1 two by two have adjacent row coordinates and are not the ‘empty’ tile, then all three tiles are transformed into ‘empty’ tiles X
In the current implementation, in each instance the goal state is to have the board composed only by empty tiles. The instances are three:
- 3x3 board
|G H G|
|H H R|
|R R G|
- 4x3 board
|G H G|
|H H S|
|S S G|
|R R R|
- 4x4 board
|X S G H|
|S H G R|
|S H R G|
|H H H R|
ENHSP was cloned from the official Gitlab page (https://gitlab.com/enricos83/ENHSP-Public), it was compiled and installed by executing the ‘compile’ and ‘install’ files provided in the repository (./compile and ./install commands run in the root folder). The build generated the ‘enhsp’ executable, which was then called to launch the planner. The PDDL files were pasted in a folder called ‘assignment’ inside the root folder. ENHSP was then launched in its optimal version, which makes use of A* with hmax heuristics and redundant constraints. To do so, the planner was run with the following commands in the root folder:
./enhsp -o pdd_files/domain.pddl -f pdd_files/prob1.pddl -planner opt
./enhsp -o pdd_files/domain.pddl -f pdd_files/prob2.pddl -planner opt
./enhsp -o pdd_files/domain.pddl -f pdd_files/prob3.pddl -planner opt
FD was downloaded from the public Git repo (available at https://github.com/aibasel/downward) and it was built using the Cmake 3.19 GUI tool. As for ENHSP, the PDDL files were pasted inside the root folder in a folder called ‘assignment’. The planner was used with A* search along with landmark-cut heuristic. The launch commands are:
./fast-downward.py pdd_files/domain.pddl pdd_files/prob1.pddl --search “astar(lmcut())”
./fast-downward.py pdd_files/domain.pddl pdd_files/prob2.pddl --search “astar(lmcut())”
./fast-downward.py pdd_files/domain.pddl pdd_files/prob3.pddl --search “astar(lmcut())”
The solution plans are analyzed in the summary tables here below. To better understand the behaviour of the planners, some metrics were used. In particular, the metrics of interest are:
- solved: if the problem was solved or not
- T(s): total planning time in seconds
- Q - quality of the solution plan. It is measured as the number of actions required to solve the problem
- Q ratio - the quantity Q/Q*, where Q is the quality of the solution plan found by the considered planner and Q* is the best plan found among all planners
- Nodes expanded
- Nodes evaluated
| Solved | T(s) | Q | Q ratio | Nodes expanded | Nodes evaluated | |
|---|---|---|---|---|---|---|
| ENHSP | yes | 1.205 | 6 | 1.0 | 223 | 619 |
| FD | yes | 0.006 | 6 | 1.0 | 9 | 52 |
| Solved | T(s) | Q | Q ratio | Nodes expanded | Nodes evaluated | |
|---|---|---|---|---|---|---|
| ENHSP | yes | 19.934 | 10 | 1.0 | 54189 | 146181 |
| FD | yes | 0.214 | 10 | 1.0 | 1003 | 5367 |
| Solved | T(s) | Q | Q ratio | Nodes expanded | Nodes evaluated | |
|---|---|---|---|---|---|---|
| ENHSP | yes | 167.845 | 11 | 1.0 | 378261 | 985296 |
| FD | yes | 0.601 | 11 | 1.0 | 1454 | 10552 |
It is possible to notice that both planners solved all instances, with the same plan quality. However, FD expands and evaluates far fewer nodes and takes way less time than ENHSP.
The project aims at developing a planning-based solution to the sliding-tile problem. For such purpose, the domain file along with the problem instances were implemented in PDDL.
The domain and problem instances were fed into two popular planners available in literature, namely ENHSP and Fast Downward. Results show that both planners were able to find solution plans of the same quality. However, there is a remarkable gap in performance between the two. In particular, Fast Downward outperformed ENHSP in planning time, nodex expanded and nodes evaluated.
Some areas of this project could be explored more in depth. Future developments could concern:
- solving instances with larger grids
- evaluating correlation between the grid size and the quality metrics
- comparing the performance of more planners
- changing the existing domain rules
- adding other domain rules
planning.domains
https://gitlab.com/enricos83/ENHSP-Public
https://github.com/aibasel/downward
... work in progress ...
This project was developed during the AI Planning module of the MSc course in Artificial Intelligence offered by University of Huddersfield. This project was not created for deployment into a production environment. Also, the software could contain bugs.