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

with not winner routes should calculate its best next route and start a new
auction process.
On the other hand, if the route is not confirmed and the communication is
not possible, the agent will execute the first step of its personal trip, trying to
contact with the central server in the next node to negotiate this route.
The route selection process is as follow. The agent selects all possible paths
starting from its current position on the map. The agent only considers paths
with a length of three nodes. This arbitrary number is empirically determined
and can be tunned according to size and topology of the map. The criterium
followed to establish the length of the paths is to avoid combinatorial explosion
in the route search process. Then, preselected routes are evaluated according
to the edges: a visited edge is more interesting that a not visited edge. Finally,
the selected route for auction process is the most valued route between all the
preselected. In case of equality, the agent selects a random path.

route := []
route_confirmed := False
while not is_all_map_inspected ():
if route != []:
if route_confirmed :
go_to_next_node( route )
else :
if is_communication_possible ():
auction_result := start_auction(route)
route_confirmed := auction_result
else :
go_to_next_node( route )

else :
route := select_best_route_from_current_position ()

Fig. 2. Pseudo-code for robot-agent

3 Experimental Results

We have conducted several experiments to check the worth of the proposed
method. The results are compared to the obtained by teams of robots with a
random behavior. The criterium followed by these teams is completely random,
i.e. each agent randomly selects a not visited edge from its current position and
when if all the edges are been visited, a random edge is selected.
The objective to achieve is that all edges of the graph will be visited with the
least number of steps. We assume a

step as the action of “go from a node A to a

node B” . We will show the results of the experiments for two kind of teams formed

by agents, each with a different behavior (one for random behavior and the
other with our method). Each behavior is executed by an incremental group of
agents, starting with one agent and finishing with teams of thirty agents working