Sokoban is a classic problem which appeared so far in all the ASP Competitions. This year the problem specifications were adapted in order to adhere to the specifications of the homologous problem used at IPC 2011 and 2008, in order to achieve a clearer comparative picture between planners and ASP solvers.
Sokoban is a game puzzle developed by the Japanese company Thinking Rabbit, Inc. in 1982. 'Sokoban' means 'warehouse-keeper' in Japanese. Each puzzle consists of a room layout (a number of square fields representing walls or parts of the floor, some of which are marked as storage space) and a starting situation (one sokoban and a number of boxes, all of which must reside on some floor location, where one box occupies precisely one location and each location can hold at most one box). The goal is to move all boxes onto storage locations. To this end, the sokoban can walk on floor locations (unless occupied by some box), and push single boxes onto unoccupied floor locations.
The former ASP Comp 2011 Sokoban specification was such that "the sokoban walking to a box and pushing it a certain number of locations in one direction" was an atomic action. This has been lifted in this years' edition, thus there are no combined actions.
In the decision version of this problem, the question to answer is whether a solution involving at most N actions exists, for N given as input. If so, a witness containing the sequence of actions should be produced; otherwise no solution should be output.
Input: at/2, clear/1, goal/1, isgoal/1, isnongoal/1, movedir/3, player/1, step/1, stone/1
Output: pushtogoal/7, pushtonongoal/7, move/5
In our setting, an instance contains the warehouse layout, representing the floor locations, and in particular their horizontal and vertical relationships; storage locations, where the boxes should eventually go to; and, initial positions of stones and the sokoban. This information is encoded as facts using predicates movedir/3, goal/1, stone/1, isgoal/2, player/1, at/2, clear/2 as follows:
movedir(x,y,dir): y is a location reachable by location x by moving towards direction dir, where dir can be one of 'dir_up','dir_down','dir_left','dir_right'.
goal(s): the stone s must be put in a goal location stone(s): s is a stone isgoal(l): l is a goal location isnongoal(l): l is not a goal location. This information can be obtained by complehementing information given by isgoal, but it has been retained for compatibility with the IPC 2011 domain description. player(p): p is the sokoban. at(o,p): the object o (either the sokoban or a stone) is initially at position p. clear(p): the floor location p is clear of objects.
Each instance has exactly one fact for player/1. There can be in principle non-goal stones (i.e. there can be s such that stone(s) holds, but not goal(s)).
An instance also contains a sequence of time-steps for warehouse configurations, between which the actions occur:
step(s): s is an allowed step. It can be assumed steps are consecutive integers ranging from 1 towards a limit value N. Steps are associated to actions. It's up to problem modeller's how to treat properly the presence of N+1 intermediate states.
According to the IPC 2011 domain specification, there are 3 possible action types:
pushtonongoal(p,s,ppos,from,to,dir,t): at step t, the sokoban p pushes the stone s in direction 'dir', from location 'from' to location 'to'. The sokoban itself moves from 'ppos' to 'from'. This actions is allowed if: ppos, from and to are either vertically of horizontally consecutive locations; 'to' is not a goal location and is clear; s was previously at 'from' and p was previously at 'ppos'.
pushtogoal(p,s,ppos,from,to,dir,t): same as above, but 'to' must be a goal location as a prerequisite.
move(p,from,to,dir,t): at step t, the sokoban p is moved from 'from' to 'to' in direction 'dir'. This action is allowed if 'to' is clear, the sokoban was previously at 'from' and 'from' and 'to' are properly connected.
Sample instances: download
Type: Search Competition: Both
Notes and Updates
- Authors: Giovambattista Ianni, Carlos Linares López
- Affiliation: University of Calabria, Italy and Universidad Carlos III de Madrid, Spain
- Original Author: Wolfgang Faber
- Affiliation: University of Calabria, Italy