Selective Method Based on Auctions for Map Inspection by Robotic Teams - Foundations on Natural and Artificial Computation - page 176

2.3 Elements and Structures

In the sequel we enumerate the structures and elements used in our method:

- Graph: The graph is the representation of the real environment where nodes

represent intersections and edges represent corridors or tunnels. Isolated
nodes are not present in the graph neither small groups of disassociates
nodes or islands. Thus, we are working with connected graphs.

- Route: It is a “a sequence of arcs where all

the arcs are directed in the same way, i.e. the end of an arc coincides with
the origin of the following one“

path of the graph, where a path is

[12]. The first node of a path always is the
agent's current node. The routes represent a set of nodes (and therefore a
set of edges) that the agent decides to visit.
- Agent: An agent is the representation for a robot, it will select the routes
to be visited. The agent will negotiate the routes with other agents in an
auction through a central server.

- Central Server: The aim of this element is to be a shared memory. When

agents can communicate with the central server, they will be able to know
which edges have been visited for other agents. Likewise, this will be the
place where agents bid for routes during the negotiation.

2.4 How It Works

As each member of the team as the central server work independently. An indi-
vidual member of the team negotiates with other teammates through the central
server to accomplish the main task: inspect all edges of the graph. The central
server works as a shared memory that allow the team to share knowledge about
the graph state and make auctions to make the appropriate decisions.
The following sections describe in more detail the role played by each element.

Central Server. This component has two main tasks: it develops the role of

shared memory for all agents and it is also a place where the agents perform the
auctions. As shared memory provides to the agents the necessary information to
keep their own maps updated with the progress on the global task.
When an agent wants to start an auction, it sends a message to the central
server for starting the auction process. Others agents can submit theirs own
routes and when finish the time for the auction, the central server proceed to
make an election and communicate to each agent if its route is the winner. An
agent with a winner route could do the trip through the nodes of the route.
The routes are compared in function of the shared stretchs (edges between two
nodes). In terms of set theory, if each route is a set of stretchs to be cover, the
central server compares all routes that intersect. The routes that not intersect
with any other are selected as winners (see eq. 1). For the routes that intersect
with others, the central server will choose as the winner to the route with more
exclusive stretchs (see eq. 2), or a random of them in case of equality.