CSC 324 Assignment 4

For this assignment, you will construct and manipulate a simple blocks world. The blocks world is a simple dynamic example that is commonly used to study planning problems.

Part I

Defining the world

First we define the properties of the world.

There is a table.
There are four blocks in the world named a, b, c and d.
Blocks can be placed directly on the table, but the table is only large enough for three blocks to sit directly on it at a time.
Blocks can be placed directly on top of exactly one other block.
At most one block can be placed directly on top of a block (though blocks can be stacked in piles).
Every block is either on the table or on top of another block.

The initial state of the world should be as illustrated below. The table is represented by the horizontal lines, and the blocks by their names. There are two piles of blocks: block a itself, and a pile of blocks b, c and d. Note that one location on the table is clear.

		d
		c
	a	b	
	=================

There are two types of actions that can be taken. The state of the world is modified by taking the action.

A single block can be moved to be on the table (if there is space).
A single block can be moved to be on top of another block (if there is no other block already on top of this block).

Only a single block can be moved at any time. If there are blocks on top of the the block we want to move, those blocks must be moved off the block before the block can be moved.

We will represent the state of the world with several relations.

on(A,B) - block A is directly on top of B, where B is either the name of a block or table
clear(A) - there is nothing on top of block A

We will represent an action (which may change the state of the world) with the following relation.

place(A,B) - place block A directly on top of B, where B is either the name of a block or table

Define these relations (possibly by defining helper relations or additional objects) subject to the world restrictions mentioned above. Since the place predicate can change the state of the world, we will need to assert and retract facts about the world. For example, if we move block a from the table to be on top of block b, we might have to retract(on(a,table)) and assert(on(a,b)), among other facts.

It might be useful to declare some of your relations as being dynamic, using something similar to the following clause:

    :- dynamic on/2.

Handling errors

The actions that can be taken at any time are resticted. For example, if block d is on top of block c, it would be incorrect to ask place(c,d) or place(c,table). Prolog should detect that your command cannot be satisfied and report "No", but that doesn't tell the user why it is wrong.

Write additional rules to detect errors and print a suitable error message. These rules should use a cut (!) to abandon any useless alternatives that may have been constructed, and always fail.

You may wish to use the built-ins write to print a string (always succeeds, no branching), nl to print a newline, and fail which always fails (which, if all alternatives are cut, will guarantee the computation fails). For example, the following might be the end of an error rule:

    write('No space available on the table!'), nl, !, fail.

Hint: Simplicity is key for this part. You will be extending your Part I code in A5, so make sure you test it thoroughly.

Part II

Initial state of the world

In this part we extend the basic world to allow some user customization. To allow the user to set up an initial state of the world, provide an initialize_world relation that takes a list of piles of blocks, each pile being a list of blocks from bottom to top, and initializes the world to that state.

For example, initialize_world([[a],[b,c,d],[]]). results in a world where block a is on the table with nothing on top of it, a pile of blocks with d at the top, c in the middle, and b at the bottom on the table, and one free spot on the table.

Notice that initialize_world gives us a great amount of flexibility: we can give our own names to the blocks, have various numbers of blocks, and specify the size of the table (how many different blocks can be directly on the table at once). This flexibility may require generalization of some of your rules.

Displaying the world

Write a relation print_world that uses write to print a representation of the world.

For example, print_world on the initial state mentioned above could look like this:


	d
	c
a	b	
=================

Hint: For this part, it might be useful to store the current state of the world as a list, in the format used by initialize_world, and derive on and print_world (and any other relations) from this state.