some text

Multi-Agent Rendezvous, or, How to (re)build a Terminator

Most people in Western countries of a certain age have probably seen the movie Terminator 2. In a famous scene towards the end of the film, the evil Terminator becomes liquified after an explosion. Blobs of liquid metal are scattered on the ground and he appears to have been "terminated". However, as if guided by some mysterious superior intelligence, the blobs suddenly start moving towards one another, eventually merging and reforming the intact Terminator, who then sets off on the rampage again. The question, "How did they do it ?", provided the motivation for the subject of this talk, which is not as far from science fact as the previous description may suggest. People working in robotics have long been interested in, and formalised, problems of this type, in which the basic assumption is that no agent possesses global knowledge of the system, yet they must all coordinate their activities somehow (in the case at hand, they must "rendezvous"). I will describe this background and the (apparently) novel angle from which we approached the problem, which can be (very loosely) summarised by saying that we sought randomised rendezvous algorithms which would asymptotically almost surely be optimal for random initial configurations. (Joint work with Anders Martinsson and Dmitry Zhelezov).