COMP316A: Artificial Intelligence Techniques and Applications

- Assignment 1: Uninformed Search -

1. Implement a solver for the blocks world using breadth-first search. The 2D blocks world consists of of a set of blocks named A, B, C, etc., that are arranged in stacks and a robot arm that can move a block from the top of one stack to the top of another stack (and this is the only action the robot can perform). The states in this problem are arbitrary configurations of blocks in a fixed number of (possibly empty) stacks. Your program must be able to read a start state from a file and a goal state from a file and output a sequence of actions for getting from the start state to the goal state. The output must be to standard out.

   More specifically, your program must be able to read files where each line has a comma-separated list of uppercase letters representing the blocks in a stack, starting with the bottom-most block as the first element in the list, and containing the other blocks in the stack in ascending order. An empty line corresponds to an empty stack. You can assume that the file for the start state and the file for the goal state have the same number of lines (i.e. stacks) and the same set of letters (i.e. blocks).

   Once your program has found a solution, it must output it to standard output, with one action on each line. The actions must be represented by comma-separated pairs of indexes, where an index represents the position of a stack in the world (the indexes must start from 1). The first index in a pair must be the index of the stack from which the block is taken, and the second index must be the index of the stack to which the block is added.

   Here is an example start state for a world with three blocks arranged in three stacks:

   ---

   B,A

C


   ---

   Here is an example goal state for the same world:

   ---

   A

B,C


   ---

   And here is a sequence of actions to get from the start state to the goal state:

   ---

   1,2
3,2
1,3
2,3
2,1


   ---

   Please make sure that your program complies with these specifications so that it will work with our test cases.

2. Implement bidirectional search for the solver.

Other Information

Value: 11% of the final grade
Due date: Wednesday, 12 March, midday

Please submit the assignment as a compressed archive (.zip or .tar.gz).

No extensions will be granted except for sound, documented, medical reasons.