Adrian German presented some ideas toward a solution to the so-called "Easter Egg problem" where one has a field with randomly placed Easter Eggs. One wants to unleash a collection of near-sighted agents to path around the field and collect the easter eggs in the shortest amount of time. The question is, "Is there any algorithm that beats random searching. German was convinced that there was and presented the first part of his algorithm. It involved creating rule patterns that the agents would attempt to match to their surroundings with a default case of action if no patterns matched. German only got as far as showing the templates that cause the agent to spiral outward in a path that fills all space before his time ran out.
I am especially eager for German to find an algorithm more efficient than random search, since this is apparently what my Roomba employs to clean the living room and its algorithm is incredibly inefficient. The Roomba crosses its own path many times in its attempt to collect all the "easter eggs" on the living room floor. Here's hoping that German finds results that are employed by the iRobot corporation in their wonderful products.
I was asked by one member of the audience during the presentation if the set of rules that I have chosen would work better than a random search. While I asked for a definition of "random search" another member of the audience said "randomly searching reveals eggs with a probability that is proportional with the area looked at". Both comments are quite meaningful but I would like to point out that there is danger in making assumptions without explicitly stating them, since we might end up speaking about different, distinct problems.
As an example, it should be clear that you're not allowed to sample the space without replacement: sampling the floor, the ground, is not like randomly drawing balls from a urn. If you remove part of the ground you won't have what to walk on. My solution does not suffer of this predicament: what the head of my Turing tape has visited can be safely eliminated, since the border is simply connected and allows you to reach any of the points not visited yet.
You also don't want to revisit places that you've searched before (in my case I can throw away the pieces of inside, once they no longer belong to the border). A random walk where steps in all directions are equally likely would not get very far very quickly and would be very redundant. My model extends like water on the table, in all directions, except I didn't get to show that.
Otherwise I just want to point out that my model paints (or marks) the space to avoid going back into territory that has been already searched. The only redundant movement is on the border, in search of replacement patterns. The space that is marked, or painted, can be removed since it is not needed after it becomes part of the inside. Only the border needs to be kept, that is. I think I may have said this already.
During my presentation I only showed the basic animation loop in the rewritten program; I have enumerated the rules and the basic topological restrictions. I have also, I hope, communicated clearly the basic idea, also the steps one would take if one were to apply NKS to this problem from here on, and that that was exactly what I did do back in 1993 when I produced these rules. Except then I searched through a space of rules "by hand" whereas much more could be done with an NKS approach. I am going to finish the implementation that I mentioned tonight and I will upload it tomorrow to the forum, and then I will post the link to it here. Thanks for your patience and interest.
Many thanks for allowing me to add this comment here after the talk and thanks for the summary as well.
Posted by: Adrian German | Saturday, July 14, 2007 at 10:17 PM
With considerable delay (about 15 days, I guess) I have posted a notebook on the NKS forum (click on the link to be taken to my post which includes a link to the Mathematica notebook) with details of the implementation discussed during my presentation.
The direct link to the notebook:
http://www.cs.indiana.edu/~dgerman/nks2007/dgerman-eep.nb
Obviously, I'd be more than eager to answer any questions with respect to the approach I presented. Also I would be quite interested in any joint development of subsequent rule spaces and/or experiments with anyone interested.
Posted by: Adrian German | Monday, July 30, 2007 at 12:33 PM
A plain HTML version of my notebook:
http://www.cs.indiana.edu/~dgerman/nks2007/dgerman-eep.htm
This, for those who might not have Mathematica 6 just yet.
Posted by: Adrian German | Tuesday, July 31, 2007 at 01:53 AM