Rendezvous Problem - Search Theory: A Game Theoretic Perspective - page 163

entities cannot leave any marks at visited nodes, nor send messages to other robots.
The movement of entities depends solely on snapshots of the network configuration
(position of all entities) taken independently by each entity. This chapter surveys re-
cent results obtained in important network topologies such as rings, grids, and trees.
This work include impossibility results on rings including the case where global-
strong multiplicity detection (ability to detect whether to entities occupy the same
node) is assumed. Further, the global-weak multiplicity detection model is consid-
ered in which all possible gatherable configurations have been determined. Finally,
this survey provides also partial results for the case of local-weak multiplicity de-
tection.
Finally, in Chap. 14 one can find a list of open rendezvous problems asked from
Operations Research perspective, where optimization of the search process is inter-
preted as minimising the expected time to meet, or possibly maximising the proba-
bility of meeting within a given time.

11.5 Further Comments

The readers are strongly encouraged to advance their knowledge in the field. The
topic by Alpern and Gal [ 4 ] is a jewel on the shelf of any researcher thinking seri-
ously about working on searching games and rendezvous problems. Other recom-
mended survey type sources include a monograph on rendezvous in the ring co-
authored by Kranakis et al. [ 21 ] and a more recent survey by Pelc [ 24 ] that focuses
on deterministic mechanisms used in efficient rendezvous. The rendezvous problem
has been also discussed in the context of consensus problems in networked dynamic
systems, flocking, fast consensus in small-world networks, Markov processes and
gossip-based algorithms, load balancing in networks, distributed sensor fusion in
sensor networks, and belief propagation [ 23 ].

References

1. S. Alpern, The rendezvous search problem, SIAMJ.ControlOptimisation, 33, 673-678, 1995.

2. S. Alpern, Bilateral street searching in Manhattan (line-of-sight rendezvous on a planar

lattice), CDAM Research Report Series, LSE-CDAM-2004-09.

3. S. Alpern and S. Gal, Rendezvous Search on the Line with Distinguishable Players, SIAM J.

Control and Optimisation 33, 1270-1276, 1995.

4. S. Alpern and S. Gal, Theory of Search Games and Rendezvous, KluwerAcademicPublishers,

2003.

5. J. Anaya, J. Chalopin, J. Czyzowicz, A. Labourel, A. Pelc, and Y. Vaxes, Collecting Informa-

tion by Power-Aware Mobile Agents, DISC 2012, 46-60.

6. E.J. Anderson and S. Essegaier, Rendezvous search on the line with indistinguishable players,

SIAM J. Control Optimisation33, 1637-1642, 1995.

7. E.J. Anderson and R.R. Weber, The rendezvous problem on discrete locations, J. Applied

Probability 27, 839-851, 1990.