EECE 822: PS 6

Due: Wednesday 15 March 2000

Problem 1 (50%): For this problem you will show how the asynchronous weak commitment search algorithm (Algorithm 4.2) works to solve the 4-queens problem. You will draw each succesive state of the board, along with the priorities of all the variables (as done in Figure 4.8). You will also show the messages that are sent between the agents. In cases were more than one agent could take an action (after all, it is an asynchronous algorithm), just pick one, but specify which one.

The start state you will use depends on the last four digits of your ssn, as used in the grades page. If your last four digits are x1 x2 x3 x4, then queen 1 will start out in position (x1 modulo 4), queen 2 in (x2 modulo 4), and so on. If, lucky you, your start state is also a solution, then close your eyes, roll a four-sided dice four times, and pick a new start state.

Problem 2 (10%): If you are in the mall with a friend and you get separated, which is the best strategy stragety for you to find each other the fastest (assume that no yelling, intercom, hired help, etc. are allowed)?

Would your answer change if it was a strip-mall (i.e. mostly one-dimensional) versus a regular mall (i.e. a 3-dimensional maze).

Problem 3 (40%): Show the first 8 steps of the LRTA* algorithm as it is applied to an 8-puzzle where k(i,j)= 1 for all states i,j of the board, and the initial h(j) is the sum of the Manhattan distances between all tiles and their final destination

The initial state will be formed using the last four digits of your ssn: x1 x2 x3 x4. The board will look like:

x1 x2 x3
x4 4 3
2 1  
The final board will have the tiles in numerical order from left-to-right and top-to-bottom. If you have repeat numbers, don't worry about it, they go one after the other. Since you are only doing the first 8 steps, you also don't need to worry about whether it will ever find a solution or not (but, you should wonder about that!)

Jose M. Vidal
Last modified: Sun Feb 27 22:44:35 EST 2000