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)?
- (a) you stay put while your
friend searches for you,
- (b) you and your friend both
search for each other,
- (c) you both stay put and hope for a
disruption of the space-time continuum, or
- (d) all of the
above.
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:
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