Self-organized Multi-agent System for Robot Deployment in Unknown Environments - Foundations on Natural and Artificial Computation - page 170

This information will be received and stored by all cameras (Network Thread,
Fig. 4). The Neighbouring Thread running in every camera will periodically
check if the detections of the robots are taking place simultaneously from other
cameras (Fig. 2), updating the neighbourhood information accordingly.
A very important aspect to notice is that even though this neighbourhood
information can change dynamically (e.g. if some camera is moved or stops work-
ing), our system will be able to cope with this since this information is updated
continuously.
3.2 Distributed Route Planning
A route is an ordered set of cameras through which the robot can navigate:
basically, the robot will go from the FOV of one the cameras to the FOV of the
next camera on the route. These routes will allow our robots to navigate without
metric maps of the environment. Following with our system's philosophy, these
routes will be generated on demand as a result of local interactions amongst the
cameras, without the intervention of any central entity.
The route formation starts with the detection of a call event that requires
the presence of a robot. When this happens, the Vision Thread of the cam-
era detecting it (Fig. 3, CallMarkerDetection) informs the corresponding Call
Thread, which in turn will broadcast a request to all the robots (C2R CALL
broadcast, Fig. 5). Upon reception of this message (Fig. 6), every free robot
(IDLE state) accepts the call, and broadcasts this acceptance to every cam-
era (C2R ACCEPTCALL). Then, those cameras which receive the acceptance
message and which are seeing the robot which issued that message, will start a
back-propagation process (Fig. 4) to create a route; through this process there
will be a passing message that will contain a route to go from the FOV where
the robot is seen, until the FOV where the event that started the call is. Each
camera passing the message will include itself in the route, and forward it to its
neighbours (except those that are already included in the route). This process
ends when the message is received by the camera which triggered the call. There-
fore, this camera should receive information about which robots accept the call
and the routes they would have to follow in order to reach its FOV.
The Call Thread of the calling camera (Fig. 5) will select the shortest route
received, inform the corresponding robot accordingly (C2R INFORMROUTE),
and wait until the robot arrives to the call event area, provided that the robot
has previously accepted the route.
As an example of route formation, consider the hypothetical topology in Fig. 1.
Consider that the robot A is free (willing to accept any call), while the robot B
is not. In this scenario, when the camera 1 detects the call event (CE) and asks
for robots to attend, RA is the only one accepting the call. Then, the camera
5 receives the acceptance, and forwards it to cameras 3 and 4 (its neighbours),
which will forward it as well to their own neighbours, and so on. Finally, camera
1 will receive two acceptances with the routes 5-3-1 and 5-4-2-1 coming along,
from which the first one will be chosen. It is clear, after this description, that