You may work on this on your own or in teams or with one partner of your own choosing. If you work with a partner, you must complete the extra problem at the end of this assignment.
Note: please do not search for or plagerize solutions you find on the web. I am aware of these and you will be caught.
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. You can only push one crate at a time, you cannot push a row of crates. If you are not careful, some of the crates can get stuck in wrong places or block your way.
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. Walls are marked X, Sokobans marked S, crates marked C, and crate goal squares are highlighted gray.
In this example, in order for the sokoban to accomplish his goal, the Sokoban must move to the north side of the crate and push it down one space (2 moves and one push). Then it must move to the east side of the crate and push it west two squares (2 more moves and two pushes). Then it must move to the south side of the crate and push it up one square to completion (2 more moves and a push).
Your assignment is to formulate the sokoban problem in STRIPS representation. Utilize the planning as satisfiability system Blackbox to solve the following problems.
Problem 1:
Problem 2:
Problem 3:
Problem 4:
Click here for instructions for downloading and using the Blackbox planning system, including the input language specification. Be sure to note the instructions to use the option "-solver chaff" in order to obtain best performance.
Use Blackboard to turn in a zipped folder named sokoban-FIRSTNAME-LASTNAME.zip (or for partners, sokoban-FIRSTNAME-LASTNAME-FIRSTNAME-LASTNAME.zip) containing:
The state of the art of both SAT based planners and heuristic state-space search planners has advanced since the creation of Blackbox. Download the two following state-of-the-art planning systems, and compare their performance on the Sokoban problems to Blackbox and each other. Write up a summary of your observations (1 to 2 pages long) and include it as a pdf file in the zipped folder you turn in. Note that you may need to modify your operator files to account for the fact that these planners stick more closely to the official PDDL language. If you are the first students to get these systems running on our Linux cycle machines, please let the TA's know where you put the binaries so that they can put a copy in the public class directory.
I strongly advise you to build up to the full Sokoban representation. Start by defining the grid itself. How will you represent each square? For example, each square could be represented by a single object, or by a pair of objects (its coordinates). How will you represent the ways that one square can be adjacent to another square (above, below, to the left, to the right)? Once this is decided, create operators for moving a Sokoban in each direction (up, down, left, right) without worrying about crates, walls, or other Sokobans. Run you operators on several small problems instances you create in order to be sure everything is working problems. Next, add in walls and more than one Sukoban and test again. Finally, add push crate operators for each direction.