Swarm robotics has several challenge options to provide control management of social behavior to achieve specific goals. Bio-inspired approaches are on the top of the solutions that do not use artificial intelligence, - specially versions based on ant colony algorithms - where local information spread in the application environment is used instead of local centralized database. Such approach is specially suited to applications in digital manufacturing because of the high flexibility of this production environment. In this work is presented an alternative proposal that emulates pheromone trough RFID tags spread in the manufacturing environment with enhanced memory capacity. Advances in cost and complexity of this implementation would come out from an integrated system were robots emulate an ant colony which use pheromone represented by Petri net inserted inversely in an RFID distributed database called iPNRD. In the iPNRD approach, the environment receives only RFID tags, which stores a PN trigger vector, while the robots have a RFID reader, which provides their own PN incidence matrix and marking. During tag data capture the robot updates its marking vector. This article will show how iPNRD emulates the pheromone of ants, assuming the environment possesses embedded readers. To avoid robots' collision, the iPNRD solution assist two red/green semaphores: one in the feed source and another in pheromone area. That solution has lower complexity and the implementation has a relative low cost. The interaction between robots and environment and the resulting behavior are also modeled using Unified Extended Petri Nets where pseudo-boxes are used to represent the flow of communication concerning robots and environment.
RFID
Petri
nizing robot’s actions and exchanging information among them. A bio-inspired
approach is suitable to model this information exchange either based on
centralized or distributed architectures. Petri Nets (PN) have been applied in this
context [
The behavior of an ant colony and the interactions of robots in a swarm are
both based on behavioral rules that only exploits local information [
There are different ways to represent the pheromone, each one with its
peculiarities. [
Since the initial RFID application with the Walmart, in early 2000’s, much
attention has been pointed out to this technology. Current RFID market still
shows a lot of optimism and maybe overestimation in the success of this
technology. However, RFID implementation is below its potential because of the lack
of process information embedded together with automatic data gathering and
process [
Another application of RFID systems is in manufacturing and logistic
process where a Petri Net can model the product behavior. Elementary Petri Net
stored in RFID database (PNRD) [
Since each tag refers to a single object, the PNRD must be a safe Petri net,
and the calculation of the next state must be a unimodular vector. There are also
some variants of PNRD: i) he PNRD extended to distance integrates PNRD with
RFID IPS to control mobile robots [
Figure 1 presents Petri net and RFID integration through PNRD or iPNRD.
On one hand Petri net can model, control, deals with concurrency, process and
it has several formal properties as model checking and invariant analysis. RFID,
on the other hand is an automatic data capture tools with a unique
identification, and it can become a position sensor. It is possible to read up to 1000 tags
per second, depending on RFID frequency. Whereas RFID can be a dynamic
database it is pointed out as a smart product cornerstone [
This paper aims to bring up how Petri net (PN) and RFID can be integrated to emulate ant pheromone applied to robot swarms. To achieve this goal, it is necessary to reach the requirements related to the ant pheromone in swarm mobile robots, so the need of smarter environment is mandatory.
In the next section additional related works on swarm robotics are presented and the iPNRD is presented in section 3. The fourth section shows the system proposal. Lastly, section 5 presents conclusions, followed by the acknowledgement and the references. 2
Related works in swarm robots and ant pheromone One of the great challenges related to the swarm of robots lies in the control algorithm and in the strategies of cooperation between them, without any collision. There is a search for new models of behavior and innovations/enlargements to those already studied.
According to [
[
In relation to the ant pheromone, RFID tags arranged in the environment
can works as pheromone carriers [
iPNRD
According to [
In this approach each tag stores its own incidence matrix and state vector of a Petri net referring to the process part to which the tagged object in question participates; and each reader stores the corresponding control vector list and the triggering conditions. The PNRD operation is based on the capture of the tagId followed by the AT or incidence matrix, and the tag state vector MK . The software responsible for calculating the next state finds the corresponding uK (control vector) related to the conditioning set composed by tagId, tag state, antennaId, readerId, and other optional additional data, such as time interval, the distance among other. The calculation of the next tag state MK+1 follows Eq. 1.
MK+1 = MK + AT :uK ; k = 1::n (1)
The next tag state result must be evaluated. If the result is a unitary vector,
this means that the Petri net remains elementary and safe, which is consistent
with the fact that each tag has a 1: 1 relation with Petri Nets. This result is
supposed in agreement with the expected process flow, allowing the record of the
MK+1 in the tag memory as new tag state. Otherwise, the Petri net is no longer
safe, indicating an abnormality in the expected follow-up of the process, which
can generate a real-time warning signal. It can monitor the process of each tag
individually. Even flexible processes can be stored, giving to the tagged object
the ability to follow different paths if properly planned and modeled previously.
One of the possible problems during the execution is the appearance of conflicts.
Conflicts occur when the same antenna/reader is associated with more than one
transition relative to the same tagId, tag state, and additional data. A decision
algorithm can be applied to choose what transition should be triggered to solve
the conflict. Hence, PNRD is based on a previously modeled system, and it
can check whether the desirable model is followed or not. [
[
It is possible to point out that in both approaches there are a strong connection between RFID and Petri Net, which reduces the need for queries in external databases although there is a need to predefine the PN process in advance. After this process modeling, an operational management system must attribute a specific PN process and part (incident matrix, state vector or trigger vector) to each tagged object and RFID reader.
To summarize theses definitions, Tab. 1 presents the original PNRD and iPNRD approaches with its variants. There are three different ways to distribute Petri net elements between RFID reader and tag. This paper uses the original iPNRD where the robot carries the RFID reader and the environment has the passive tag.
The approach of this work is the environment (world) with passive RFID tags strategically spread in it and mobile robots have a RFID reader that reads tag data when it passes through the tag, the tag information can change mobile robots’ behavior, and the mobile robots can write new information inside the tag. In this paper, tags represent the pheromone of ants, the energy source, and semaphores to avoid collision during pheromone data capture. The iPNRD is applied in this scenario, so the robots carry the incidence matrix and its own marking while the tag carries the trigger vector. Since the ants (robots) are homogeneous, the robots modeling and characteristics are the same for every robot. 4
The system’s bench (see Fig. 2) is based on [
The robot moves in the bench following the Petri net presented in Fig. 3. It can be noticed that each tag, spread in the environment, is considered as a mobile robot transition and each place defines a set of actions that the mobile robot must execute, such as place p2 (Robot waits green light ). In this specific place the robot must stop on the tag, write its presence inside the tag, wait for the environment reader to change the semaphore color from red to green, then continuous to move to the next tag. As well as for the place p2 all places in the mobile robots’ PN are considered as macro places where each place has a set of specific actions.
The transition pheromone tag, on the other hand, stores the more attractive trail, following the ant pheromone algorithm which are going to be presented in 4.1 subsection, defining the trail to be followed.
This mobile robots’ PN could be defined as finite automata, or as finite state machine, or as sequential function chart (Grafcet), but since environmental and pheromone modeling uses Petri Net the authors decided to standardize the modeling. Also, as shown, the places modeled for the mobile robots indicate that the actions of the robots, while the transitions are represented by the capture of the tags. Thus, iPNRD can be applied to this case. from pheromone area to source area following trail A. The tag S1 (transition t4) indicates that the robot achieved the source area. Looking for trail B the respective place and transition for the same situation are p10 and t11 (tag S2).
It is possible to verify that if the mobile robot reads the tag N5, it means that the pheromone calculus chose trail A. Otherwise, the mobile robot is going to read the tag N6. During the source capture, another semaphore related with S1 and S2 tags works similarly to the nest one. After the source capture, the mobile robot returns to the nest semaphore (N2 and N3 tags), it stores information to next pheromone calculus and it enters in the nest when read N4 tag.
Three important points must to be considered: – How to avoid collision between the robots; – How to synchronize the robot and the environment readers to read and write the same tag and; – How to define the direction to be taken from the robot to the source.
To avoid collision the robots are going to follow a line tracking with sensors and it must sense walls around itself. In each path there are two lines, so the robot moves to the source in one line and returns to the nest in another one. When the robot moves along trail A, it follows from the nest to a source close to the outer wall and returns close to the inner wall, while at trail B is the opposite. In the nest there is no collision between the robots as it follows a unique path in the counterclockwise direction forming a FIFO (First In, First Out) queue.
Even so, there are two points of concurrency that is necessary to be aware, it means, during the reading of the source tag and the pheromone one. The source tag can be reached from trail A and trail B, and the pheromone tag can be reached when the robot wants to leave the nest and when it wants to return from both trails. To avoid collision in these cases, there are two red/green semaphores, which is detailed in section 4.2. 4.1
Pheromone function as chemical messengers among individuals [
As mobile robot and the environment can change the tag’s information, there is a concurrency in communication if the robot RFID reader and the environment RFID reader try to write or read the tag at the same time. Figure 4 presents an example of RFID reading collision between the mobile robot and the environment in the pheromone tag. There is a need of synchronization between the robot RFID reader and the world RFID reader. This synchronization can be implemented applying a time lag between the mobile robot clock the environment clock. These clocks are activated on the rising edge and deactivated on the falling edge. For this synchronization, the robot clock and the environment’s clock are 180 degrees out of phase.
Since the pheromone is a volatile substance and its concentration decreases in time, the world can decrease pheromone value according to Eq. 2, where c_value is the concentration value stored on the tag. This equation is proposed because the pheromone value decreases inversely proportional to the concentration. Low concentration takes lesser time to evaporate than high concentration. (2)
Figure 5 shows how the pheromone tag is going to work over time. Every time a robot comes back from source tag, it increases the pheromone concentration stored at pheromone tag with the power removed from the source. The world’s reader decreases the pheromone concentration according to the Eq. 2, and every time the pheromone tag is updated by the robot, the world’s reader starts the equation from t = 0. This function is applied to both trails, and the environmental reader stores the comparison of them to assist the mobile robot trail definition.
According to the amount of pheromone in each track a specific value will be saved in the pheromone tag (00, 01 or 10). It is observed that until the time T1 the amount of pheromone in the two trails are identical since no robot has returned to the nest with food. In this case the value saved in the tag is 00 and when a robot reads this information it decides at random which path to follow. In the present case, a mobile robot has returned to trail A with which the value of the pheromone concentration has increased and until the instant T2 this value is higher than the pheromone concentration in the trail B, so the value saved in the tag is 10 indicates that the robot must take this path when leaving the nest. From T2 to T3 the saved value is 01 and indicates that the mobile robot must follow the path B. From T3 to T4 the concentration of pheromone in track A is higher than the concentration of pheromone in track B, then the value saved in the tag is again 10. It is observed that at instants T2, T3 and T4 the amount of pheromone in the two tracks is the same. With this the value saved in the tag is 00 which indicates that the robot can follow any of the paths. In this work when this situation happens the robot chooses to follow at random.
Figure 5 presents 7 robots in the bench over timer. Robot 1 to 4 are arriving the nest and robots 5 to 7 are leaving the nest. When the robot 1 reaches the pheromone tag it stores the information that it came from trail A, so the pheromone concentration in trail A increases, and when robot 6 reads the pheromone tag, it reads the value 01 and moves to source area following trail A. Robots 2 and 3 reaches the pheromone tag and now the trail B has more pheromone concentration. So, when robot 7 leaves the nest, it reads 10 and moves to source area following trail B.
As presented in [
Similarly, the robot RFID reader at the pheromone tag (see Fig. 7) can perform three different readings (trail A; trail B; and without pheromone or same amount on both trails) or store two distinct information (returned by trail A or returned by trail B). Clearly the pheromone RFID tag stores the trigger vector of both RFID readers.
As can be seen, both PN have inhibitor arcs. These arcs mean that storage
has priority over reading. [
To avoid collision over source and pheromone tags there are two semaphores in this scenario, one in source area and the other one in pheromone area. The robot can reach the source tag from two paths, so the source semaphore avoids robot collisions using four tags. Two of these tags are the red/green semaphores and makes the robot wait (if the source semaphore RFID tag store red as information) or move (if the source semaphore RFID tag holds green as information), and the other two tags just indicates when the robot has left the source area enabling another robot to pass through the sourcing area.
For the pheromone semaphore (semaphore 2) there are three paths (one to leave the nest and two to reach the nest from each trail), so there is a need of six tags. Three of these tags indicates when the robot has left the pheromone area (N4 to N6) and the other three are the red/green semaphores (N1 to N3). Fig. 8 presents how semaphore 2 is implemented physically.
Table 3 presents the action sequence in the pheromone area during leaving and arriving nest. Both are similar, except during stage 5 when the pheromone is read (for the mobile robot leaving the nest) or the pheromone is stored (for the mobile robot returning from a trail). The mobile robot and environment change information through tag data capture and storage and tags are the media to exchange this information.
When the mobile robot is leaving the nest, it reaches the semaphore tag N1 (Fig. 9), it stops, and stores it presence in the tag. Next, the environment RFID reader at the N1 RFID tag perceives the robot presence, and it informs other semaphore entrance readers (through Robot Leaving Nest pseudo-box) and if the semaphore is free, it changes the semaphore color to green. After that, the robot reads the green signal and moves to the pheromone tag. The environment sends messages to other semaphore entrance readers indicating that the semaphore is busy and changes the semaphore color to red.
When the robot reaches the pheromone tag, it reads the trigger vector stored at the tag (psPhe3 to psPhe5 ) which defines what trail must be followed. If psPhe3 is read, it means that the pheromone in trail A has the same weight of the pheromone in trail B, and then the mobile robot controller chooses randomly what trail to follow. The psPhe4 and psPhe5 defines the trail. The robot moves through the tag N5 if the pheromone indicated the trail A or through the tag N6 if the pheromone indicates the trail B. At this point, the robot stores its presence, so the environment reader at the tag N5 or N6 can read this information and inform other pheromone entrance RFID readers that the semaphore is free.
The higher priority is at tag N2, since that tag indicates a robot returning to nest from the shorter trail. The robot leaves the nest (tag N1) has the lowest priority. Note that a token changes between SemaphoreFree and SemaphoreBusy, so the mobile robot returning from source disable the semaphore and it’s kept as red. The semaphore only turns free if a robot pass tags N4, N5 or N6, which means, it has left the pheromone area, and other robot can pass through. The places GreenN1, RedN1 and RobotLeavingNest are also pseudo-boxes since this information must be exchanged with other pheromone RFID readers entrance.
Fig. 9. Petri net for tag N1 in semaphore 2.
The inhibitor arcs at WriteGreenN1 indicates that if there is a robot returning to the nest, the robot leaving the nest must wait until that robot pass through tag N4. Theses inhibitor arcs are defined at microcontroller code.
The Petri net for tag N6 in semaphore 2 (see Fig. 10) has connection to the Petri net for tag N1 through the pseudo-box RobotInTrailB. Since tag N6 is only a tag that indicates the mobile robot has left the pheromone are, its net just reads the tag and send a pseudo-box every time it senses the robot at this position. The paper presented how to integrate PN and RFID to emulate pheromone of ants. The iPNRD approach was used to reach the ant pheromone in swarm mobile robots requirements, it means, the iPNRD approach meets collision avoidance, it doesn’t demand high battery power consumption, it has practical implementation and, introducing smart environment with embedded RFID readers, this approach generates independence between the environment pheromone and mobile robots. This solution requires clock synchronization between smart environment RFID readers and mobile robot readers.
RFID Tag data capture and RFID tag storing as viewed as pseudo-box means that they are message exchanging between both readers from environment and mobile robots.
The semaphore is a low-cost implementation due the cost of each reader being under U$ 2.25 (price quoted on ebay). The system can use only one controller for the entire semaphore, or each reader can have one controller attached. For this to be possible, the controller must have a master-slave communication protocol.
This approach shows that the pheromone is independent of the mobile robot, since its concentration only depends on the value stored in the tag. But the robot only can choose a path to follow if there is an information (trigger vector) stored on pheromone’s tag.
For further works an analysis of the hardware must be considered just like the system implementation.
Changes can be proposed on pheromone algorithm and source algorithm to evaluate the robots’ behavior when there is a lack of energy stored in the source, when the energy carried by the robot is variable, and when the pheromone concentration decreases according to different equations.
Also, it is possible to analyze the swarm behavior collectively or individually. When the nest is a FIFO queue if one robot stops, all the system is going to fail, but if the nest has an area to park each robot, when this robot stops the system continuous to work with any problem.
Lastly, a Petri net analyses must be considered regarding deadlocks, model checking and invariants. 6
CAPES, UNA and UFU supported this research.