Alex Golden
Richard Golden
CSC 242 Term Project

Planning with UCPOP, Graphplan and Sensory Graphplan


Background:
 Both Richard and Alexander greatly enjoyed working with UCPOP during the planning assignment. They each came up with different, interesting domains to solve, Rich's being "Dungeon Master" where a man must find a way out of a dungeon. Alex chose to represent the world of Boxxle in UCPOP to see if it could solve the puzzles.

   They were both disappointed to find that UCPOP failed to find solutions to many of their problems, even though they were relatively simple (had few operators, only took a few steps to get to a solution).

   Both Rich and Alex are very interested in finding out why UCPOP didn't work on those certain problems and domains. Our goal for the Term Project was to determine what went wrong during the UCPOP assignment. Were our domains and problems too complicated for UCPOP to solve, or could we simplify them to the point of being solvable in UCPOP? Would other planners be able to solve the problems that UCPOP can't? Would a problem solver have better luck than the planners? We set out to answer all of these questions and more in this project.

 

   Note:  When using graphplan to solve “Dungeon Master” problems it solved all of Rich’s test cases from the UCPOP project.  It fared so well on them that Rich believed that with “Dungeon Master” domain it would be difficult to produce a problem hard for graphplan to solve, except for a stress test.  As such, our group project tends to focus mainly on the Boxxle domain, a far more interesting domain than “Dungeon Master.”  For all inquiries into the “Dungeon Master” domain, please see Rich’s UCPOP project. 



About the planners / problem solvers:

Name

Type

Web page

Info

BoxxleSolver

Problem solver

n/a

Written by us in Java.
It has a few optimizations that make it better than the other planners at solving medium sized Boxxle levels.

UCPOP

Planner (Lisp)

http://www.cs.washington.edu/ai/ucpop.html

A planner written in Lisp.
According to its web page it is an aging system. They recommend using Sensory Graphplanner instead, and we agree with them on that.
Very poor performance in solving all but the simplest Boxxle levels.

Sensory Graphplanner (SGP)

Planner (Lisp)

http://www.cs.washington.edu/ai/sgp.html

A Lisp planner based on Graphplanner.
Performs much faster than UCPOP in solving Boxxle problems, and can also solve more complicated problems that UCPOP chokes on.

Graphplan

Planner (Written in C)

http://www-2.cs.cmu.edu/~avrim/graphplan.html

A compiled planner written in C.
It reads domains and problems from text files at runtime.
Easier to use and faster than both Lisp planners.


Directory Structure:

docs/

Contains document files.

graphplan/

Contains the Graphplan executable and more.

our-planner/

Contains Java source code to our incomplete planner to solve Boxxle problems.

problem-solver/

Contains Java source code to our Boxxle problem solver.

sgp/

Sensory Graphplanner (SGP).

test-cases/

Contains ASCII files of Boxxle maps and Java programs to convert those to useable files.

UCPOP/

Contains UCPOP and Boxxle domain definitions. This is a slightly more efficient version of Alex's UCPOP project.

About the test-cases:
   Creating the input for four different programs would prove be a time consuming task. In order to simplify the process Rich and I wrote four different programs:

AsciiToProdigy

Java application to convert an ASCII Boxxle map to a facts file readable by graphplan.
(graphplan uses the same format as the Prodigy planner)

AsciiToSgp

Java application to convert an ASCII Boxxle map to Lisp code usable by Sensory Graphplanner.
This is a modified version of LevelToProblem, which converted ASCII Boxxle maps to Lisp code usable by UCPOP.

MapToJava

Java application to convert an ASCII Boxxle to a character array definition useable by Java.

MapToHtml

Java application to convert an ASCII Boxxle to a HTML code to display a graphical representation of the map.
The pictures of Boxxle levels in this readme were generated by this program.


   Each of these programs is capable of converting one ASCII map at a time. Perl scripts were written to convert all of the current test cases at once, put them into their appropriate files (i.e. BoxxleSolver.java for the problem solver, or domains.lisp for UCPOP or SGP).

About our planner:
 Our original task was to write a planner to solve Boxxle levels. However, after many hours of work the planner was not close to being able to solve Boxxle levels. After that we searched the web and found additional planners we could use instead of UCPOP. These are without a doubt more efficient than our planner would have been, and are more than capable of showing UCPOP's weaknesses.


What is Boxxle?


Boxxle is a puzzle game for the Nintendo Game Boy released in 1989. The idea of the game is simple: You are a guy, and you meet a girl who you would love to show a night on the town. Unfortunately you don't have any cash, and you need to get a job. You weren't smart enough to be a computer science major so you take a job moving boxes around in a warehouse. For what the game lacks in an interesting story it more than makes up for with challenging puzzles.  The game puts on you different levels, and on each level your job is to push all of the boxes to goal squares on the map. Once you've done this, you go on to the next level, until you beat the game, get to go out on your date.

Rules Of The Domain:
   1: There is a map that consists of the player, boxes, goal squares, empty squares, and walls.
   2: The goal for each map is to push all of the boxes onto goal squares.
   3: There are an equal number of goal squares and boxes for each map.
   4: The player may move up, down, left, and right so long as there is an adjacent, empty square in that direction.
   5: The player may only move boxes by pushing them. The player may only push a box into an empty square.

Key:
    The Player = Where the player starts
    A Box = A Box
    Goal State = Where you want the boxes to be
    Box On Goal = A box on a goal
    Wall = A wall
    Space = An empty space on the map

A Simple Map & Solution:





Our Test Maps: Here are our tests maps for Boxxle. Each map is also accompanied by a table that shows how our problem solver, UCPOP, Graphplan, and Sensory Graphplan fared on them.  Enjoy!


test1:



   Steps to goal: 1
   Spaces: 3

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.4 seconds

Outcome:

Success

Time:

.04 seconds

Plans created:

27

Plans explored:

7

Outcome:

Success

Time:

0.00 seconds

Nodes created:

25

Actions tried:

1

Outcome:

Success

Time:

0 seconds

 


test2:




   Steps to goal: 2
   Spaces: 4

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.44 seconds

Outcome:

Success

Time:

.01 seconds

Plans created:

80

Plans explored:

21

Outcome:

Success

Time:

0.00 seconds

Nodes created:

62

Actions tried:

2

Outcome:

Success

Time:

20 milliseconds

 


Test3:



   Steps to goal: 1
   Spaces: 4

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.42 seconds

Outcome:

Success

Time:

.00 seconds

Plans created:

27

Plans explored:

7

Outcome:

Success

Time:

0.00 seconds

Nodes created:

36

Actions tried:

1

Outcome:

Success

Time:

10 milliseconds

 


Test4:



   Steps to goal: 3
   Spaces: 6

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.53 seconds

Outcome:

Success

Time:

.72 seconds

Plans created:

2416

Plans explored:

641

Outcome:

Success

Time:

0.00 seconds

Nodes created:

151

Actions tried:

3

Outcome:

Success

Time:

140 milliseconds

 


Test 5:



   Steps to goal: 3
   Spaces: 7

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.44 seconds

Outcome:

Success

Time:

.31 seconds

Plans created:

2416

Plans explored:

641

Outcome:

Success

Time:

0.00 seconds

Nodes created:

172

Actions tried:

3

Outcome:

Success

Time:

260 milliseconds

 


Test 6:



   Steps to goal: 3
   Spaces: 5

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.44 seconds

Outcome:

Success

Time:

.23 seconds

Plans created:

1911

Plans explored:

452

Outcome:

Success

Time:

0.00 seconds

Nodes created:

138

Actions tried:

3

Outcome:

Success

Time:

90 milliseconds

 


Test 7:



   Steps to goal: 4
   Spaces: 6

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.47 seconds

Outcome:

Success

Time:

18.35 seconds

Plans created:

32861

Plans explored:

8759

Outcome:

Success

Time:

0.00 seconds

Nodes created:

217

Actions tried:

4

Outcome:

Success

Time:

260 milliseconds

 


Test 8:




   Steps to goal: 6    Spaces: 7

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.52 seconds

Outcome:

Failure (ran out of memory)

Time:

n/a

Plans created:

n/a

Plans explored:

n/a

Outcome:

Success

Time:

0.01 seconds

Nodes created:

384

Actions tried:

6

Outcome:

Success

Time:

860 milliseconds

 


Test 9:




   Steps to goal: 6
   Spaces: 8

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.47 seconds

Outcome:

Failure (ran out of memory)

Time:

n/a

Plans created:

n/a

Plans explored:

n/a

Outcome:

Success

Time:

0.01 seconds

Nodes created:

451

Actions tried:

6

Outcome:

Success

Time:

1476 milliseconds

 


Test 10:




   Steps to goal: 6
   Spaces: 9

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.52 seconds

Outcome:

Failure (ran out of memory)

Time:

n/a

Plans created:

n/a

Plans explored:

n/a

Outcome:

Success

Time:

0.01 seconds

Nodes created:

518

Actions tried:

6

Outcome:

Success

Time:

2440 milliseconds

 


Test 11:



   Steps to goal: 7
   Spaces: 10

Our Problem Solver

UCPOP