Set Wednesday 24th April, due Thursday 2nd May.

1. Reading.

In the next two weeks, please read chapters 3 and 4 of Ferber's book.

2. Distributed exploration.

In the first European conference of Decentralized AI in 1989, Luc Steels described a reactive agent approach to the following problem:
``The objective is to explore a distant planet, to collect samples of a particular type of scientifically interesting rock. The location of the rock samples is not known in advance but they are expected to be clustered in certain localized areas. A number of autonomous vehicles are available that can drive around the planet collecting samples and later reenter the mothership spacecraft to go back to earth. There is no detailed map of the planet available although it is known that the terrain is full of obstacles. - hills, valleys, etc.''

He assumed that direct communication between robots was infeasible and he also argued that a logical approach would not work. He proposed a method of signalling where robots could drop ``radioactive crumbs'' which other robots could detect and pick up. The general idea was that if a robot found some rocks then it would drop crumbs, causing other robots to go to the same locale. As the supply of rocks was depleted the crumbs would get picked up and so robots would not go there anymore.
For navigation, he assumed the mothership would generate a ``gradient field'' which robots could detect and which reduced uniformly in intensity as the distance to the ship increased.
He proposed the following design, where the robots would obey a set of reactive rules, which were in an order or priority.
1. if detect an obstacle then change direction.
2. if detect a sample then pick sample up.
3. if true then move randomly.
4. if carrying samples and not at base then drop two crumbs and travel up gradient.
5. if carrying samples and at the base then drop samples.
6. if sense crumbs then pick up one crumb and travel down gradient.

The priority order is 1 > 5 > 4 > 2 > 6 > 3.

(i) Comment on this design, pointing out its strengths and weaknesses.
(ii) Assuming that direct wireless communication between robots is possible, and that robots have some in inferencing ability give a new design which will be superior in certain cases. Describe these cases and explain how your design would work better. You also may assume some deadreckoning and gyroscope/orientation or other such abilities which will allow robots to determine their spatial positions and orientations relative to the spaceship. Make assumptions about the problem as needed, but state your assumptions. There should if possible be graceful degradation if some robots break down.

3. Programming agents for distributed exploration.

Program a simple version of your proposed exploration robots in Prolog. Put each robot on a separate machine, and use a simple world server that will be provided as a Prolog program to run on its own machine.
The world server is described here:
http://www.cs.caltech.edu/~bond/courses/cs101c/programs/doc/doc.html

You should send an email to me with a URL of a web page where your answer is. Your answer should have the code, a brief explanation, and some data cases showing your code works correctly.