The problems that we will consider here relate to multi-agent rendezvous. As a basis we are attempting to extend the work that has been done analyzing optimal searching methods for single agents under various restrictions (see [4]) in concert with rendezvous strategies to effectively co-ordinate exploration. These considerations hopefully show the motivation for the strict assumptions that this beginning work makes. Future work will be proposed in the paper that will relax these restrictions to deal with more realistic circumstances.
Two friends have lost their car keys. They remember putting them down somewhere in the plane, but neither has any idea where. So we have uniformly distributed knowledge of the solution space, i.e. none. How should they go about finding them? Bear in mind that the friends are lazy, and the plane is a big place. What should they do? If they heed the advice of [4] they would understand that spiral search will be at least as good as any method for getting around. Since they feel they should split up to find their keys faster, then they probably want to perform bow-tie search on their respective search regions since this, too, is at least as good as anything else they could think of.
Our friends are concerned though that when one of them find the keys, how will they tell the other that it is time to go? This seems like a problem since they both walk the same speed, and it might take too long to catch up to the other person after finding the keys. In addition, our friends can't bear to yell out, they have head-aches [perhaps this is why they have lost their keys!]. By whispering to one another they restrict their range of communication to almost zero. So they agree to [try to] meet every so often at the origin of there search. But how often is good enough for these lazy friends? This is what we will try to answer for them.
Another problem that Fakete [3] tries to help our friends with is how to meet up with each other when they are lost in the bush. With their head-aches all cleared up, and being outside, our friends are free to call out to one another and by doing so can judge how far away they are from each other. Though the bush is thick and they can't tell which direction to walk in to find each other. Fortunately they both have compasses, but one friend has hurt his leg and can't walk as fast as usual, but this shouldn't matter. A problem has arisen though. During the fall, when she injured her leg she also damaged the compass. So although it still works, albeit inaccurately, can they still find each other? Perhaps not using the same method they first thought, but by using a very similar one they can maximize there chances of reuniting.