Efficiently searching a graph by a smell-oriented vertex process

Efficient graph search is a central issue in many aspects of AI. In most of existing work there is a distinction between the active "searcher", which both executes the algorithm and holds the memory, and the passive "searched graph", over which the searcher has no control at all. Large dynamic netwo rks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavily-loaded, call for a different paradig m, in which most of the burden of computing and memorizing is moved from th e searching agent to the nodes of the network. In this paper we suggest a m ethod for searching an undirected, connected graph using the Vertex-Ant-Wal k method, where an a(ge)nt walks along the edges of a graph G, occasionally leaving "pheromone" traces at nodes, and using those traces to guide its e xploration. We show that the ant can cover the graph within time O(nd), whe re n is the number of vertices and d the diameter of G. The use of traces a chieves a trade-off between random and self-avoiding walks, as it dictates a lower priority for already-visited neighbors. Further properties of the s uggested method are: (a) modularity: a group of searching agents, each appl ying the same protocol, can cooperate on a mission of covering a graph with minimal explicit communication between them; (b) possible convergence to a limit cycle: a Hamiltonian path in G (if one exists) is a possible limit c ycle of the process.