We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire region. An environment is composed of pixels that form a connected subset of the integer grid. There is at most one robot per pixel and robots move horizontally or vertically at unit speed. Robots enter R by means of k>=1 door pixels Robots are primitive finite automata, only having local communication, local sensors, and a constant-sized memory. We first give algorithms for the single-door case (i.e., k=1), analyzing the algorithms both theoretically and experimentally. We prove that our algorithms have optimal makespan 2A-1, where A is the area of R. We next give an algorithm for the multi-door case (k>1), based on a wall-following version of the leader-follower strategy. We prove that our strategy is O(log(k+1))-competitive, and that this bound is tight for our strategy and other related strategies.
@cite_14: We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. We introduce a new type of homing sequence for two robots which helps the robots recognize certain previously-seen nodes. We then present an algorithm in which the robots learn the graph and the homing sequence simultaneously by wandering actively through the graph. Unlike most previous learning results using homing sequences, our algorithm does not require a teacher to provide counterexamples. Furthermore, the algorithm can use efficiently any additional information available that distinguishes nodes. We also present an algorithm in which the robots learn by taking random walks. The rate at which a random walk converges to the stationary distribution is characterized by the conductance of the graph. Our random-walk algorithm learns in expected time polynomial in n and in the inverse of the conductance and is more efficient than the homing-sequence algorithm for high-conductance graphs. >
@cite_4: 
@cite_9: We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every so often to its starting position (for refueling, say). The environment is modeled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that it has already explored. We present a surprisingly efficient algorithm for piecemeal learning an unknown undirected graph G=(V, E) in which the robot explores every vertex and edge in the graph by traversing at most O(E+V1+o(1)) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E+V2) edges. We also give an application of piecemeal learning to the problem of searching a graph for a “treasure.”
@cite_19: Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many results have focused on finding efficient solutions to restricted versions of the problem. In this paper, we consider a model that makes very limited assumptions about the environment and solve the mapping problem in this general setting. We model the environment by an unknown directed graph G, and consider the problem of a robot exploring and mapping G. The edges emanating from each vertex are numbered from ‘1’ to ‘d’, but we do not assume that the vertices of G are labeled. Since the robot has no way of distinguishing between vertices, it has no hope of succeeding unless it is given some means of distinguishing between vertices. For this reason we provide the robot with a “pebble”—a device that it can place on a vertex and use to identify the vertex later. In this paper we show: (1) If the robot knows an upper bound on the number of vertices then it can learn the graph efficiently with only one pebble. (2) If the robot does not know an upper bound on the number of vertices n, then (log log n) pebbles are both necessary and sufficient. In both cases our algorithms are deterministic. C © 2002 Elsevier Science (USA)
@cite_27: 
@cite_10: It is desired to explore all edges of an unknown directed, strongly connected graph. At each point one has a map of all nodes and edges visited, one can recognize these nodes and edges upon seeing them again, and it is known how many unexplored edges emanate from each node visited. The goal is to minimize the ratio of the total number of edges traversed to the optimum number of traversals had the graph been known. For Eulerian graphs this ratio cannot be better than 2, and 2 is achievable by a simple algorithm. In contrast, the ratio is unbounded when the deficiency of the graph (the number of edges that have to be added to make it Eulerian) is unbounded. The main result is an algorithm that achieves a bounded ratio when the deficiency is bounded; unfortunately the ratio is exponential in the deficiency. It is also shown that, when partial information about the graph is available, minimizing the worst-case ratio is PSPACE-complete. >
There is a vast literature on algorithms for one or several robots to explore unknown environments. The environments can be modeled as graphs (directed or undirected), mazes, or geometric domains, and the robots can have a range of computing powers; see, e.g., @cite_9 @cite_19 @cite_14 @cite_10 @cite_4 . Mitchell @cite_27 includes a survey of many results on exploring and navigating in geometric environments.