A survey on coverage path planning for robotics <s> Bio-inspired Multi-robot Coverage <s> We investigate the ability of a group of robots, that communicate by leaving traces, to perform the task of cleaning the floor of an un-mapped building, or any task that requires the traversal of an unknown region. More specifically, we consider robots which leave chemical odour traces that evaporate with time, and are able to evaluate the strength of smell at every point they reach, with some measurement error. Our abstract model is a decentralized multi-agent adaptive system with a shared memory, moving on a graph whose vertices are the floor-tiles. We describe three methods of covering a graph in a distributed fashion, using smell traces that gradually vanish with time, and show that they all result in eventual task completion, two of them in a time polynomial in the number of tiles. Our algorithms can complete the traversal of the graph even if some of the agents die or the graph changes during the execution, as long as the graph stays connected. Another advantage of our agent interaction processes is the ability of agents to use noisy information at the cost of longer cover time. <s> BIB001 </s> A survey on coverage path planning for robotics <s> Bio-inspired Multi-robot Coverage <s> When looking at science and technology today, we find a recurrent problem to many fields: how to cover a search space consistently and uniformly. This problem is encountered in robotics (searching for targets), optimization (searching for solutions), mathematics and computer science (graph traversals), and even in software engineering (the main motivation for this research). In insect societies, and in particular ant colonies, one can find the concept of alarm pheromones used to indicate an important event to the society (e.g. a threat). Alarm pheromones enable the society to have a uniform spread of its individuals, probably as a survival mechanism --- the more uniform the spread the better the changes of survival at the colony level. This paper proposes a model of this ant behavior which can be used to solve the aforementioned problem. The model, called ALARM is inspired primarily by ACO and from observations of ants alarm behavior. We compare the model with a random walk, to demonstrate a significant improvement over this approach. <s> BIB002 </s> A survey on coverage path planning for robotics <s> Bio-inspired Multi-robot Coverage <s> In the world of living creatures, simple-minded animals often cooperate to achieve common goals with amazing performance. One can consider this idea in the context of robotics, and suggest models for programming goal-oriented behavior into the members of a group of simple robots lacking global supervision. This can be done by controlling the local interactions between the robot agents, to have them jointly carry out a given mission. As a test case we analyze the problem of many simple robots cooperating to clean the dirty floor of a non-convex region in Z2, using the dirt on the floor as the main means of inter-robot communication. <s> BIB003
Several muli-robot coverage path planning proposals have been presented which are inspired by behaviors found in nature. Many of them are inspired by ant behavior, using evaporating traces to achieve an emergent coverage behavior BIB001 BIB003 BIB002 . In  two algorithms are presented which are based on the premise that to achieve coverage the team of robots must "spread out" over the environment. The authors note that "this premise is loosely inspired by the diffusive motion of fluid particles". Using these algorithms robots perform obstacle avoidance and at the same time are mutually repelled by each other within their sensor range. These bio-inspired works are validated in simulation, but their practical application has been very limited up to date.