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

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.56 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:

390

Actions tried:

7

Outcome:

Success

Time:

4882 milliseconds

 

Test 12:



   Steps to goal: 9
   Spaces: 11

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.02 seconds

Nodes created:

1022

Actions tried:

9

Outcome:

Success

Time:

11,160 milliseconds

 

Test 21:




   Steps to goal: 2
   Spaces: 10

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.44 seconds

Outcome:

Success

Time:

.01 second

Plans created:

116

Plans explored:

35

Outcome:

Success

Time:

0 seconds

Nodes created:

211

Actions tried:

2

Outcome:

Success

Time:

500 milliseconds

 

Test 22:




   Steps to goal: 4
   Spaces: 10

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.48 seconds

Outcome:

Success

Time:

7.8 seconds

Plans created:

21411

Plans explored:

7150

Outcome:

Success

Time:

.02 seconds

Nodes created:

727

Actions tried:

4

Outcome:

Success

Time:

14,900 milliseconds

 

Test 23:






   Steps to goal: 4
   Spaces: 15

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.5 seconds

Outcome:

Success

Time:

7 seconds

Plans created:

16,318

Plans explored:

5102

Outcome:

Success

Time:

0 seconds

Nodes created:

458

Actions tried:

4

Outcome:

Success

Time:

2,610 milliseconds

 

Test 24:






   Steps to goal: 8
   Spaces: 15

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.58 seconds

Outcome:

Failure

Time:

n/a

Plans created:

n/a

Plans explored:

n/a

Outcome:

Success

Time:

.05 seconds

Nodes created:

1626

Actions tried:

19

Outcome:

Success

Time:

48,820

 

Test 25:






   Steps to goal: 10
   Spaces: 15

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

.73 seconds

Outcome:

Failure

Time:

n/a

Plans created:

n/a

Plans explored:

n/a

Outcome:

Success

Time:

.1 seconds

Nodes created:

2088

Actions tried:

154

Outcome:

Success

Time:

64,960

 

Test 26:






   Steps to goal: 14
   Spaces: 15

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

1.1 seconds

Outcome:

Failure

Time:

n/a

Plans created:

n/a

Plans explored:

n/a

Outcome:

Success

Time:

.8 seconds

Nodes created:

2967

Actions tried:

12715

Outcome:

No solution found

Time:

n/a

 

Test 27:









   Steps to goal: 21
   Spaces: 22

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Success

Time:

38.22 seconds

Outcome:

Failure

Time:

n/a

Plans created:

n/a

Plans explored:

n/a

Outcome:

Failure

Time:

n/a

Nodes created:

n/a

Actions tried:

n/a

Outcome:

Failure

Time:

n/a

 

Test 28:









   Steps to goal: 21
   Spaces: 36

Our Problem Solver

UCPOP

Graphplan

Sensory Graphplan

Outcome:

Failure

Time:

n/a

Outcome:

Failure

Time:

n/a

Plans created:

n/a

Plans explored:

n/a

Outcome:

Failure

Time:

n/a

Nodes created:

n/a

Actions tried:

n/a

Outcome:

Failure

Time:

n/a


Conclusion: All programs were relatively close in speed at solving simple Boxxle problems. However, UCPOP began to take significantly longer than the others with map test7 when it took over 18 seconds to solve the problem while the others took less than one second. It should be noted that SGP, which very similar Lisp code to UCPOP, was able to solve the problem.

Sensory Graphplanner proved itself to be much faster and able to solve Boxxle problems than UCPOP. It is our recommendation that you look into changing the project from using UCPOP to Sensory Graphplanner next year. They take nearly identical input, while Sensory Graphplanner can solve problems that UCPOP cannot and may prevent the same frustration that Rich and I faced during the UCPOP project. We were relieved to know that our code was all right, but UCPOP just couldn't handle certain kinds of problems.

   We would also like to point out how simple graphplan was to use. While learning UCPOP, it seemed as though learning how to load it in Lisp was half the battle. Graphplan simply reads two text files at runtime (the domain definition and the problem definition) and then proceeds to solve the problem. It was faster than both the Lisp planners and much easier to use. If working with a Lisp planner isn't a requirement for the class than I would suggest looking into changing the project from UCPOP to Graphplan. Graphplan not only outperformed both UCPOP and SGP but it's low learning curve would allow students to concentrate more on creating intricate domains and detailed documentation than fighting with Lisp to get results that they want.

   As expected, our problem solver which was designed to specifically solve Boxxle problems had the best performance. However, it took many hours of man work to produce this fine tuned program. The only problem we tested that Graphplan did not keep up with our planner was test27, which graphplan could not solve but our problem solver figured out in 38 seconds. Our problem solver used techniques such as never searching a state we had visited before and not searching down certain paths that it knew a goal could not be reached on.

   In conclusion, every option we tried (besides our Boxxle planner which was not completed) outperformed UCPOP in solving Boxxle problems. Our problem solver took the most time to produce, which is understandable seeing as it is an entire program instead of a problem definition in another program. Graphplan outperformed SGP, although in most cases the difference was only by a few seconds. Test26 was the only case that Graphplan could solve but SGP could not.