A Swarm Robotics Approach to Decontamination

A Swarm Robotics Approach to Decontamination

Daniel S. F. Alves (Instituto de Matemática, UFRJ, Brazil), E. Elael M. Soares (Escola Politécnica, UFRJ, Brazil), Guilherme C. Strachan (Escola Politécnica, UFRJ, Brazil), Guilherme P. S. Carvalho (Escola Politécnica, UFRJ, Brazil), Marco F. S. Xaud (Escola Politécnica, UFRJ, Brazil), Marcos V. B. Couto (Escola Politécnica, UFRJ, Brazil), Rafael M. Mendonça (UERJ, Brazil), Renan S. Freitas (Escola Politécnica, UFRJ, Brazil), Thiago M. Santos (Escola Politécnica, UFRJ, Brazil), Vanessa C. F. Gonçalves (UFRJ, Brazil), Luiza M. Mourelle (UERJ, Brazil), Nadia Nedjah (UERJ, Brazil), Nelson Maculan (UFRJ, Brazil), Priscila M. V. Lima (Instituto de Ciências Exactas, UFRRJ, Brazil) and Felipe M. G. França (UFRJ, Brazil)
Copyright: © 2014 |Pages: 15
DOI: 10.4018/978-1-4666-4607-0.ch046

Abstract

Many interesting and difficult practical problems need to be tackled in the areas of firefighting, biological and/or chemical decontamination, tactical and/or rescue searches, and Web spamming, among others. These problems, however, can be mapped onto the graph decontamination problem, also called the graph search problem. Once the target space is mapped onto a graph G(N,E), where N is the set of G nodes and E the set of G edges, one initially considers all nodes in N to be contaminated. When a guard, i.e., a decontaminating agent, is placed in a node i ? N, i becomes (clean and) guarded. In case such a guard leaves node i, it can only be guaranteed that i will remain clean if all its neighboring nodes are either clean or clean and guarded. The graph decontamination/search problem consists of determining a sequence of guard movements, requiring the minimum number of guards needed for the decontamination of G. This chapter presents a novel swarm robotics approach to firefighting, a conflagration in a hypothetical apartment ground floor. The mechanism has been successfully simulated on the Webots platform, depicting a firefighting swarm of e-puck robots.
Chapter Preview
Top

Definitions

In order to present the problem and its respective solution in a coherent fashion, some concepts that will be use used in this chapter need to be presented. Given a connected graph G and two nodes v and u, which belong to G, if an edge e connects v and u, then v and u are neighbors. This implies that they have a relation of adjacency. If two nodes are neighbors in G and D results from an orientation of G, then those two nodes are also neighbors in D, regardless of the orientation of the edges. The reverse of an orientated edge e from v to u is an orientated edge f from u to v.

For the graph contamination problem, nodes of a graph C are in one of three states: contaminated, clean, and guarded or clean. Contaminated is the initial state of all nodes. A (clean and) guarded node is a node that has received a decontamination agent, which is a tool of the decontamination algorithm and can have different properties regarding creation of new agents and mobility. After leaving a node, the decontamination agent becomes clean. If a clean node has a contaminated neighbor, it becomes contaminated again. This event is called recontamination.

A sink decomposition is a distribution of the nodes of an acyclic connected digraph D in numbered layers. The layer of a node is the length of the longest simple path to any sink, or zero if the node is itself a sink. This also results in the property that a node in layer k, for 1 ≤ k ≤ l, where l is the highest layer, has always at least one neighbor in layer k – 1.

Complete Chapter List

Search this Book:
Reset