Sokoban Planner

State Representation

Sokoban world could easily be described by a static part and a dynamic part. The static part consists of the position of the walls (including obstacles) and the position of goals. The dynamic part consists of the position of the robot and the position of the boxes. In a state, it is su cient to describe only the changing parameters. In light of these observations, we created our state to only include the position of the robot and the positions of the boxes. We think this is a light-weight and e fficient representation. It is important to note here that we do not tag the boxes and goals by hand.

Method of Planning

Our planner works in 2 phases in which a graph is formed and a search is performed. In the initial phase, given an initial world con figuration (static part + initial state), our planner generates a sparse graph, where the states are the nodes and the actions are the edges. The graph is generated as follows; given a state (i.e., node), available actions are evaluated and then applied (thus actions become edges) to generate new states. This goes on until there are no more possible nodes to generate. A newly created node is checked whether is was generated before to eliminate redundant nodes. During the generation of the graph, nodes are given heuristic values excluding their path costs. After this graph is constructed, A* search is applied to find a path from the initial state to a goal state.

Heuristics

We calculate the heuristic as the sum of Manhattan distances between boxes and the corresponding goals. We determine the corresponding goals of boxes as their position in a goal state. Recall that we expand all the nodes. An important property to note here is that we do not explicitly match the boxes with the goals. Mathematically, the heuristic of a state is calculated.

Execution File