CSE 573 Artificial Intelligence Autumn 2001
Homework #3B
Due 11/23/01 (No class on that day)

1.Problem
There is a game called "Sokoban" which roughly translated from Japanese means "warehouse keeper." The first sokoban game was created in 1982 by Hiroyuki Imabayashi at the Japanese company Thinking Rabbit, Inc. The idea is that you are a warehouse keeper trying to push crates to their proper locations in a warehouse.

The problem is that you cannot pull the crates or step over them. If you are not careful, some of the crates can get stuck in wrong places and/or block your way.1

This problem naturally lends itself to a grid world representation. Take the following problem in a 4x4 world where the goal is to move the crate to the other side of the "wall":
"W" is a wall, "O" is a clear space, "S" is Sokoban, "c" is a crate destinations for the crates are underlined
OOOO
OWcS
OOOO
OOOO
In this example, in order for the sokoban to accomplish his goal, he must move to the north side of the crate and push it down one space (2 moves and one push). Then he must move to the east side of the crate and push it west two squares (2 more moves and two pushes). Then he must move to the south side of the crate and push it up one square to completion (2 more moves and a push).

By adding additional crates, the problem quickly can become non-trivial. As in the following example:
WWOOWWW   
OOOOOcO
OWOOWcO
OOOOWSO











2. Assignment
Your assignment is to formulate the sokoban problem in strips representation. Utilize the program "Blackbox" to solve the following problems. How many steps does it take to solve each problem? 
1.
OOWW
OOWW
cSOO
OOcO
OOWW

2.(Same as 1. but with two sokobans (sokobani?))
OOWW
OOWW
cSOO
OOcS
OOWW

3.
OOOO
OWSO
OccO
OOcO
3.Resources:
1.There is an interactive version of Sokoban that ships with KDE.
2.Http://javaboutique.internet.com/Sokoban is a java applet that you can play to get a feel for the game.
3.Blackbox binaries and descriptions of the strips language format are located at http://www.cs.washington.edu/homes/kautz/blackbox/index.html
4.I strongly advise you to build up to the full sokoban representation. For example first try and represent the problem of moving the sokoban in one dimension in one direction to a goal square.  Then try extending the representation to include moving in two directions in one dimension. Then try moving in two dimensions, then add moving crates in one dimension, etc. etc.  If you try and implement the whole thing all at once you will get very frustrated at the representation language, and won't be able to figure out several things which are bound to be going wrong all at once.
5.Remember that there should be no negative preconditions. Make ~Wall() into Clear() for example. Also remember the hack that two parameters may not be the same object. Consider this in your problem formulation.
4.Turn-in
1.Print out the domain.pddl file that you used to solve the three problems above. Print out the problem.pddl file that corresponds to problem 3 above. Print out the sequence of moves that your representation produced.  Please translate the raw output, if necessary, so that I can easily figure out what each action in your plan is.
2.Turn these three things into my mailbox on the first floor of Sieg or hand them to me directly.  You may also set-up a web page with your solutions on it and email me the address if you're paper averse.
3.I'd rather you didn't email me the documents directly, but you can if you're willing to risk the "wrath of the TA". (see http://www.cs.washington.edu/homes/djp3/wrath.jpg )