Scribd
Upload
16 views4 pages

Astar For Sokoban Report

Uploaded by

phanhuyhoang0425
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views4 pages

Astar For Sokoban Report

Uploaded by

phanhuyhoang0425
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

A* search for Sokoban - Report

Fullname: Ngo Duc Hoang Hiep


Student ID: 21520846

I. Provided heuristic for sokoban


Regarding all added states in the frontier, we choose the state
that has the smallest total Manhattan distance(L1 distance)
between boxes to arbitrary empty goals. Make sure we just pair
one box and one empty goal at a time, in the other words, there
are not two boxes paired to the same goal and otherwise.

In the provided heuristic, we just ignore all boxes on goals when


computing total manhattan distance(equal 0), that means we
encourage the search explorer to expand the branch having
lower L1 distance and more boxes on the goals, although those
positions may not be the optimal locations of those boxes(we
can move a box on a goal to another goal to find better
solutions)

Estimation cost = L1 distance of boxes to goals

II. Heuristic on player’s position(Astar+)


The given heuristic only considers the L1 distance between
boxes and goals in arbitrary pairs. However, regarding the actual
cost of a solution, the number of moves to place all boxes on
their goals, the position of the player should be taken into
account in the estimated cost. Particularly, at a specific state, we
need to spend some steps to move the player to a box before
pushing the one of them to its goal, unless it is the goal state.

Based on that information, I establish a new heuristic that is the


sum of the total L1 distance of boxes from their goals(as the
previous strategy) and the L1 distance of the player to the
closest box.

1
In the second term of heuristic, I consider all boxes on the map
without examining the status of the box(on goal or not), “the
closest box” may or may not be the box that is pushed on a goal.
The intuition behind it is that I want to encourage the search to
expand the state that the player can reach the first box with
fewer steps and some goal boxes can be moved to the other
goals(it may produce a better solution).

If we ignore the closest goal boxes(produce bigger distance to


non-goal boxes) then the search overestimates the cost of
branches that lead to the state that has a higher number of goal
boxes, and turns out the algorithm is less likely to expand those
states.

Estimation cost = L1 distance of boxes to goals + L1 distance of


player to closest goal

III. Heuristic with placement boxes on


goals(Astar++)
This strategy combines two previous approaches and a
“discount” of cost based on the number of boxes that are
placed on goals. In the other words, the cost to a state that has
a higher number of goal boxes would be lower than the other
ones.

This heuristic strengthens an implication: “the higher number


goal boxes in the state, the closer that state to the goal state”

The intuition is still the same as the previous heuristic but


promotes the impact of goal boxes by producing reduction in
the estimation cost.

Estimation cost = L1 distance of boxes to goals + L1 distance of


player to closest goal - number of goal boxes.

*Note: “goal box” means a box is placed in a goal.

2
IV. Experiment results

3
Conclusion
The solutions found by 3 heuristic are relatively similar in number of
moves and number moves without box pushing. At level 13 and 16,
the solution is not the optimal one, because it is not as good as the
solution found by UCS, if we choose the cost is the number of steps
without moving a box.

Astar+ and Astar++ do better than both default Astar and UCS in
most cases.

In terms of the number of explored nodes, Astar++ achieves the best


result of 13/16 levels.

You might also like