## Project 2: Sokoban

### Due Tuesday 8 April by 11:59pm

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.

### 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. 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).

### Assignment

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:

### Blackbox Planner

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.

### Turn In

Use Blackboard to turn in a zipped folder named sokoban-FIRSTNAME-LASTNAME.zip (or for partners, sokoban-FIRSTNAME-LASTNAME-FIRSTNAME-LASTNAME.zip) containing:

• a domain operator file named sokoban.pddl
• four problem instance files named s1.pddl, s2.pddl, s3.pddl, s4.pddl
• four solution files (created using the -g FILE option) named s1.sol, s2.sol, s3.sol, s4.sol

### Extra Problem for 2-Person Teams

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.

• The Madagascar planner (M, Mp, MpC) is a very efficient implementation of the SAT based techniques for planning by Jussi Rintanen.
• Fast Forward (FF) is a powerful state-space planning system by Joerg Hoffmann.