| Résumé | Efficient exploration of unknown or unmapped environments has become one
of the fundamental problem domains in algorithm design. Its applications
range from robot navigation in hazardous environments to rigorous
searching, indexing and analysing digital data available on the
Internet. A large number of exploration algorithms has been proposed
under various assumptions about the capability of mobile (exploring)
entities and various characteristics of the environment which are to be
explored. Here we consider the "graph model", where the environment is
represented by a graph of connections in which discrete moves are
permitted only along its edges. Designing efficient exploration
algorithms in this model has been extensively studied under a diverse
set of assumptions, e.g., directed vs undirected graphs, anonymous nodes
vs nodes with distinct identities, deterministic vs probabilistic
solutions, single vs multiple agent exploration, as well as in the
context of different complexity measures including the time complexity,
the memory consumption, and the use of other computational resources
such as tokens and messages. In this talk the emphasis is on memory
efficient exploration of anonymous graphs. We discuss in greater detail
three approaches: "random walk", "Propp machine" and "basic walk",
reviewing major relevant results, presenting recent developments, and
commenting on directions for further research.
|