Congestion Avoidance for Multiple Micro-Robots Using the Behaviour of Fish Schools

Abstract

This article summarizes a research topic which discusses one of the most common problems in multiple micro-robots' navigation, namely congestion avoidance. This situation occurs when troops of micro-robots moving in different directions meet each other at a common area causing congestion situations. To avoid this risky state - which can create an inextricable scenario - firstly, we established a local and a global communication network that manages the robots' displacement through formation control. This warns each of them of the existence of a risk of congestion and manages the choice of the priority group, which is a new concept that we introduce in order to deal with this kind of congestion conflict. Secondly, we consider a new algorithm based on chaotic equations and inspired by the behaviour of schools of fish, which solves the congestion problem by creating a bifurcation of the troop's configuration and enables the proper avoidance of the conflict exhibited by congestion.

Keywords

Congestion Avoidance Multiple Robot Displacement Formation Control Collision Avoidance

1. Introduction

In recent years, the global study of the navigation of multiple micro-robots has been very productive. Indeed, most of developed control laws, cooperative coordination algorithms and task solving methods have proven to be efficient for fulfilling specific tasks. Usually, these approaches always suffer from restrictive assumptions and constraints which do not allow a relatively wide panel of application and flexibility in the usage of these algorithms.

Many works dealing with multi-agent navigation exist. Some of them directly consider the congestion avoidance problem [1–2] but most other studies deal with traffic control and collision avoidance [3 –10]. Generally, a collision avoidance algorithm is used on a single robot or a small number of mobile robots where suitable constraints are already fixed by the configuration. However, if we initially consider a dynamic, unstructured and uncertain environment with priorities which deal with the entity and the group priority, any attempts at traffic control may encounter unmanageable tasks that do not match with the role of this approach. Also, the management of the safe displacement of a large number of robots with only a local collision avoidance method may disturb the arrival of all the elements [11] or else create inextricable scenarios and conflict.

Due to the problems and limitations mentioned above, a congestion avoidance algorithm will be very useful when a large number of micro-robots are used. Indeed, there exist some works dealing directly with the congestion problem, for example in [1] the proposed algorithm avoids congestion for groups that move in opposite directions before encountering and changing their behaviours. However, the application of this approach requires a constant velocity for all the troops and also considers only the case when groups face with each other. One interesting study developed in [12] addresses a decentralized flocking problem for micro-robot swarms that controls how they autonomously navigate in an unknown environment in three-dimensional space. In [12], only fixed obstacles were tested and no specifications about individual robot kinematics were given. In the same vein, in [13], a theoretical framework for the design and analysis of distributed flocking algorithms was developed. Two cases of flocking in free-space in the presence of multiple obstacles were considered. This technique can be used in some simple congestion situation cases, but it requires huge computational effort in a real time process and does not consider the case of a moving obstacle.

As mentioned above, there are many methods that can be applied to solve the problem of congestion. Among these methods, some of them solved the problem of congestion without avoiding conflict; in other words, the catalyst of the algorithm is the occurrence of the problem itself. Other approaches can solve the congestion problem only for some already structured systems, such as with a car traffic problem. On the other hand, some methods circumvent the problem by using approaches that avoid congestion but which still suffer because of some strict limitations that do not offer the free use of these techniques. Therefore, we propose our own method, which solves the problem of congestion for an unstructured environment by avoiding the tough problem of a congested area while dealing with a minimum of assumptions in order to get a wider panel of application.

Moreover, the proposed algorithm can be perceived as a collision avoidance algorithm for a large robot population. However, it is more appropriate to view this method as an anticipative congestion avoidance approach because it still provides a kind of freedom to use collision avoidance algorithms locally.

2. Methodology

The concept of our research is based on an anticipative approach in order to develop an algorithm that avoids micro-robot troop congestion situations. If two troops of robots meet with each other, this may result in congestion; in this, a group of micro-robots will be divided into two subgroups depending on the distribution of the multi-agents in the space. In other words, by considering certain priorities, one group will receive the right to go ahead in order to reach their target while the other group of micro-robots will divide its spatial configurations to make a path that allows the priority group to reach the target without altering its behaviour.

To develop this technique, we built a local system of communication between two groups of micro-robots in order to warn their teammates of the existence of a risk of congestion and also to alert them to change their behaviours so as to avoid this situation. However, before alerting the groups, the priority troop needs to be chosen based on certain criterion, such as: the average group speed, energy consumption and the distance of each group to the target. We define the priority troop based on these criteria. The fastest group, which has already consumed more energy than the other group or else is located a shorter distance from the target, has the highest priority. Thus, an intelligent choice needs to be made to select the priority troop.

As such, the basic idea of the division is developed in considering the means that schools of fish use to avoid attacks by changing their motion behaviours. Figure 1 shows one common form of behaviour of schools of fish, where a predator approaches them. As can be seen, the behaviour of the fish population reacts by surrounding the predator as if a repulsive force is acting between the predator and its entourage. From this, some basic motions of swarms that resemble the motion of a school of fish can be obtained. When these populations are subject to attack by predator, the behaviour of the school changes totally, since a few individual fish will react by avoiding the “collision” with the predator while others have to decide for themselves which flock to consider in order to survive the attack.

By ignoring the consequences of such attacks and considering its spatial configurations, an analogy with congestion avoidance behaviour can be seen and, moreover, such behaviour as inspired from the motion of schools of fish can be applied to micro-robot populations. Thus, by translating the escaping and the flocking behaviours to a robot population, we propose a new algorithm that allows micro-robots to avoid congestion with other troops when they meet each other in a common area.

Figure 1.

Behaviour of a school of fish during a shark attack

Different groups of non-holonomic mobile micro-robots move along desired trajectories and meet with each other on a common trajectory zone, which we call the potential congestion area. The potential congestion area can be defined not only by that situation where micro-robots face each other, but also where they meet each other at different angles by creating overcrowding situations.

Figure 2.

Illustration of congestion risk while robots meet each other with an encountered angle α

First of all, using the control law developed in [14], we choose our leaders for the purpose of steering their own troops to their target. Figure 2 illustrates an example where two groups of six micro-robots move along a desired trajectory as a whole. In this case, the micro-robots encounter each other at an angle α, as defined in the figure.

We also consider the case where the position and orientation of each micro-robot is known using the algorithm proposed in [17]. This method is followed by odometry in order to rapidly position and orientate each micro-robot.

Assume that the micro-robots are differential mobile robots with non-holonomic constraints. Each i^th group of the micro-robot leader's posture, denoted by $p_{i} = {[\begin{matrix} x_{i} & y_{i} & θ_{i} \end{matrix}]}^{T}$ , is described by a unicycle model, as follows:

{\dot{p}}_{i} = [\begin{matrix} {\dot{x}}_{i} \\ {\dot{y}}_{i} \\ {\dot{θ}}_{i} \end{matrix}] = [\begin{matrix} \cos θ_{i} \\ \sin θ_{i} \\ 0 \end{matrix}] v_{i} + [\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}] ω_{i}

(1)

where (x_i, y_i) denotes the i^th micro-robot coordinates in the X-Y plane, θ_i denotes the orientation of the i^th micro-robot with respect to an inertial coordination frame, and v_i and ω_i stand for the linear and angular velocities respectively.

Concerning the followers of the lead robot, we denote by $p_{i j} = {[x_{i j}, y_{i j}, θ_{i j}]}^{T}$ the posture of the j^th follower in the i^th group, which is also described by a unicycle model, thus:

{\dot{p}}_{i j} = [\begin{matrix} {\dot{x}}_{i j} \\ {\dot{y}}_{i j} \\ {\dot{θ}}_{i j} \end{matrix}] = [\begin{matrix} \cos θ_{i j} \\ \sin θ_{i j} \\ 0 \end{matrix}] v_{i j} + [\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}] ω_{i j}

(2)

where (x_ij, y_ij) denotes the j^th follower coordinates of the i^th group in the X-Y plane, θ_ij denotes the orientation of the j^th micro-robot of the i^th group with respect to an inertial coordination frame, and v_ij and ω_ij stand for the linear and angular velocities respectively.

The formation control, which defines the initial states (or Maintenance State) of the troops, is managed by the Separation Bearing Controller, presented in [14], where each micro-robot i is considered to be a leader who leads a group of micro-robots with a reference separation distance and a desired relative bearing angle.

As it can be seen, our paper is divided into four sections, described as follows: a section on communication, which regroups a local and a global communication network in order to minimize the exchange of data between different groups and different teammates on the potential risk of congestion. Secondly, section on decision-making, which provides the troops with the ability to make choices based on different criteria developed below. Thirdly, a section on bifurcation, which is inspired by the behaviour of schools of fish, which regroup when escaping and flocking. Finally, a section on unification and the reaching of the target, which ensures the arrival of all the troops.

3. Communication

In order to develop our algorithm, our micro-robots need to communicate with the purpose of reporting their postures and velocities and also warning their teammates of the existence of a potential congestion area. This section is concerned with minimizing the exchange of data among micro-robots as much as possible.

To achieve this, a local and a global communication system was created in order to ensure a proper data sharing that can reduce the quantity of exchanged data, while introducing the concept of confidentiality by keeping some of the data unshared. As such, the local communication system ensures formation through a bifurcation alert and the unification of each group through information shared locally between robots that belong to the same group. In addition, the global communication system ensures the synchronization of congestion avoidance through the information shared between the leaders.

Suppose that there are two groups of micro-robots with a potential risk of congestion. Using the previous control law, only the posture of the leader and its velocities is enough to compute the command of each micro-robot relative to its leader. In order to alert the troop to a congestion risk, the leader will inform them about the danger only if the troop has been chosen, based on the criteria that we develop in the next part, as a non-priority troop. According to this, a set of information Li is defined as $L_{i} = {\begin{matrix} {\dot{p}}_{i} & p_{i} & P t_{i} \end{matrix}}$ , where p_i represents the i^th group leader posture and Pt_i represents a binary element defined as:

P t_{i} = {\begin{matrix} 1 & i f t h e g r o u p i s a p r i o r i t y t r o o p \\ 0 & i f t h e g r o u p i s a n o n - p r i o r i t y t r o o p \end{matrix}

(3)

Each micro-robot j from the i^th group is able to get the data shared through L_i. Therefore, by using L_i the troop is able to communicate locally but needs also to communicate with other groups.

Thus, the group's communication or global communication is defined in order to exchange data about the micro-robots' spatial configuration, velocities, target position and consumed energy. According to this, a set of data Lg_i is defined as:

L g_{i} = {\begin{matrix} {\dot{p}}_{i} & X_{i T \arg e t} & P_{e i} \end{matrix}} \cup V_{C o n v e x} (P_{i})

(4)

where:

Lg_i: Set of data of the ith group intended for other groups.

Xf_iTarget: Target coordinates of the ith group.

P_ei: Approximation of the consumed energy.

ṗ: Set of the ith group's element's postures.

V_Convex(P_i): Convex hull of a given finite nonempty set of points P_i.

The information about the convex hull of the i^th group will decrease the amount of exchanged data since only the micro-robots postures defined on the envelope of the group will be included in Lg_i.

4. Priority group selection criteria

The priority group is defined as the troop which does not change its behaviour when a risk of congestion is detected. In other words, the priority group will follow its path indifferent to the potential risk of congestion that may occur. The main idea behind choosing this group is to respect a kind of equitability in order to be fair while conserving different criteria so as to make this choice. The criteria chosen to make our choice use the exchanged data given by Lg_i. Through the exchanged data Lg_i that regroups the target coordinates, the leader posture information and the consumed energy, we choose our priority group by computing Pt_i.

As defined, Pt_i represents a binary element shared in the local communication network and depending on the returned value of this element the troop will maintain its initial behaviour or else will switch its behaviour so as to avoid congestion. Thus, rather than including Pt_i as an element shared in the global communication network, we prefer to allow each group to generate the Pt_i, whether or not it defines a priority group.

In order to do this, each troop will generate:

f_{\Pr i o r i t y - i} (t) = \frac{\sqrt{{\dot{p}}_{i} {(1)}^{2} + {\dot{p}}_{i} {(2)}^{2}}}{V_{m}} + \frac{‖ X_{i T \arg e t} - X_{i C o n v e x H u l l} ‖}{d_{m i}} + \frac{P_{e i}}{e_{0}}

(5)

where:

V_m: Maximum speed.

X_iConvexHull: Coordinates of the centre of the hull of the i^th given by V_Convex(P_i).

d_mi: Initial distance from the starting point to the goal.

e₀: Initial energy stored in the batteries.

f_Priority-i: Priority function.

The definition of f_Priority-i takes into consideration the speed of the group's leader, the remaining distance to the target and the consumed energy. Therefore, if the group is relatively fast compared to other troops, it may be chosen as a priority group. Indeed, the distance plays a role in the strategy choice where the closest group to the goal will get a lower priority compared with groups which are much further from their respective targets. After computing this function for each troop, the priority element Pt_i is defined as follows:

P t_{i} = {\begin{array}{l} 1 i f \max ({f_{p r i o r i t y k} (t) |}_{t = t_{r i s k}}) = {f_{p r i o r i t y i} (t) |}_{t = t_{r i s k}} w i t h k = 1 : n \\ 0 i f {f_{p r i o r i t y k} (t) |}_{t = t_{r i s k}} is not the maximum \end{array}

(6)

By assigning priority to one troop, it can pursue its displacement task without discontinuous motion. Figure 3 illustrates the three criteria that are used in order to make the priority choice. In this figure, we show a basic illustration of the criteria as translated through the global communication network.

Figure 3.

Illustration of the criteria used to choose the priority group (speed, distance to the target and consumed energy)

Now suppose that two groups are face to face with each other: after computing the priority element, one group goes ahead to its target and the other changes its behaviour - using the method that we will develop below - in order to avoid the groups' collision.

Thus, considering only two groups seems a manageable task, since only one non-priority group is defined. However, what will happen if we consider a more complex scene involving the management of more than two groups?

Figure 4 illustrates four groups of mobile micro-robots in a potential congestion situation. Enabling one priority group solves the problem only for that group while it increases the complexity of our task for other troops, which may still face a high risk of congestion. In order to simplify our problem, as assumed before, first we consider that only two groups of micro-robots can encounter each other at a certain interval of time T. In other words, for a given moment we do not consider more than two groups of micro-robots encountering each other at the same time. However, this does not mean that we are not managing a congestion problem for more than two groups of micro-robots.

Figure 4.

Four groups of mobile micro-robots in a potential congestion situation

Suppose that multiple groups of micro-robots (N_g > 2) are in a congestion risk situation. After adopting the criteria and choosing a priority group by computing the priority function, only the priority group and the group with the highest priority function (except the priority group) will be able to continue their displacements. In other words, the priority group continues its motion towards the target, the second group will change its behaviour in order to avoid a collision, and the remaining groups will stay in standby mode, waiting until the first risk of congestion is solved. We will call the group that changes its behaviour ‘the active group', which has the right to continue its displacement. The active group will be chosen as follows:

\begin{array}{l} i f P t_{i} = 1 & {f_{p r i o r i t y J} (t) |}_{t = t_{r i s k}} = \max ({f_{p r i o r i t y k} (t) |}_{t = t_{r i s k}}) \\ w i t h k = 1 : n & k \neq i \to t h e j^{t h} g r o u p i s c h o s e n a s a c t i v e g r o u p \end{array}

(7)

This approach resembles traffic control strategies by applying some rules to the whole population of micro-robots and making safe decisions by keeping some members of the population waiting while the risk goes on. In fact, we use this approach as a first trial approach without any special contribution in order to get on with developing our main subject, which deals with the congestion avoidance problem.

5. Bifurcation Generation

In this section, we consider splitting, which we will rename ‘Bifurcation Generation'. When a group of micro-robots detects a risk of congestion, this will generate different trajectories, based on chaos equations, to avoid conflict. Let us look closer at a chaos equation, such as the Lorenz equation.

The Lorenz equation is an example of a non-linear dynamic system corresponding with the long-term behaviour of the Lorenz oscillator, commonly defined as three coupled ordinary differential equations, modelled as:

\begin{array}{l} \frac{d x}{d t} = σ (y - x) \\ \frac{d y}{d t} = x (r - z) - y \\ \frac{d z}{d t} = x y - b z \end{array}

(8)

where the three parameters σ, r and b are positive and are called the Prandtl number, the Rayleigh number and the physical proportion, respectively.

Figure 5 shows a computation result of Lorenz equations with the parameters r = 28, σ = 10 and b = 8/3. The development of the system is plotted in the phase space in the graph. From Figure 5, it is then clear that the system is confined to a certain region, namely the two shells.

In our work, as mentioned before, we consider only the two-dimensional space X-Y. Thus, the coordinates in the Z axis will just be ignored. One of the most important properties of the Lorenz equation is that it has a natural symmetry, defined by (x, y, z) → (-x, -y, z). Since the Lorenz equation is defined as a chaotic equation, where the system evolves differently with a very slight variation of the initial conditions, as a path generator it can lead to inextricable and unpredictable cases and can create more problems rather than solving them. Thus, in order to avoid this in our research, we consider only those shapes that can be generated through the Lorenz equation.

By changing the parameters r, σ and b we can generate new trajectories that can be used in order to avoid congested situations, not only in those configurations where groups face each other, but also in other configurations where troops meet each other with a known angle. After testing and generating many trajectories by changing the coefficients r, σ and b, we discovered that by keeping b and r constant and analysing the variation of σ in the generated trajectory, we observe that if the value of σ is big enough then we get a long path on the x axis, and vice versa. Thus, by changing the parameter σ, depending on the meeting angle, we can allow some elements of the group to bypass the coming priority group in order to avoid it. Moreover, and concerning the remaining elements, some other rules need to be established, depending on the group's relative positions compared with the coming priority group.

Figure 5.

A Lorenz attractor for the values r = 28, σ = 10 and b = 8/3. These values are usually used to describe the Earth's atmosphere.

Figure 6 shows the variation of the generated trajectories by keeping both r and b constant while changing σ. When the troops face each other, the generated trajectories with a high value for σ for one subgroup and its symmetric pair are compared with the symmetrical line defined by the initial path for the other subgroup, which will be sufficient to bypass the priority group.

However, if troops meet with an encountering α, other cases need to be considered:

$• π - Δ α < α < π + Δ α$

The elements of the troop will react like where α = π. In other words, a high value for σ will be chosen and then one subgroup will follow the initial generated path and the other will follow the symmetric path from the initial path, which is compared with the symmetrical line defined by the initial path.

$• \frac{π}{2} + Δ α < α < π - Δ α or π + Δ α < α < \frac{3 π}{2} - Δ α$

The choice of σ will be oriented to a smaller value so as to generate the trajectory of the subgroup, which is on the side of the coming priority group. The value of σ will be smaller if it approaches π/2+Δα or 3π/2-Δα. In addition, the other subgroup will keep using the generated trajectory, like where the troops were facing each other.

$• \frac{π}{2} - Δ α < α < \frac{π}{2} + Δ α or \frac{3 π}{2} - Δ α < α < \frac{3 π}{2} + Δ α$

In this case, the troops will not bifurcate but will together avoid the group's collision. Depending on the priority group's speed, the non-priority group will surpass the other troop if the global speed of the other troop is relatively slow compared with the generated trajectory as with when the troops were facing each other. If the priority group's speed is relatively high, then the non-priority troop will bypass the conflict in a criss-cross way through the path generated with low value of σ.

Figure 6.

Paths generated by varying σ

$• Δ α < α < \frac{π}{2} - Δ α or \frac{3 π}{2} + Δ α < α < 2 π - Δ α$

The choice of σ will be oriented to a smaller value in order to generate the trajectory of the subgroup, which is on the side of the coming priority group. The value of σ will be smaller if α approaches Δα or 3π/2+Δα. Moreover, the other subgroup will keep using the generated trajectory, as with the troops in the first case.

$• - Δ α < α < Δ α$

The elements of the troop will react as though α = 0. In other words, σ will take the smallest value where one subgroup will follow the initial generated path while the other will follow the symmetric path from the initial path.

Using the parameter $Δ α$ , the bifurcation of the robots is simplified into two main approaches. The first approach allows the robots to undertake two symmetrical escape routes - not only for a given meeting angle but also for a given range - which will simplify the trajectory generation by computing only one trajectory and calculating its symmetric trajectory. The second approach is defined by two different generated trajectories which require more computations. Therefore, the computation time is reduced by defining an appropriate $Δ α$ through these two approaches.

Now, in order to adapt the trajectory for each sub-leader element of the non-priority group, some spatial transformation for this trajectory will be applied, considering the arriving priority group data obtained from V_Convex(P_k):

ς_{i j} = Γ (V_{c o n v e x} (P_{k})) \cdot F (σ)

(9)

where:

$ς_{i j}$ : New generated trajectory for the j^th leader of the non-priority group i.

$Γ (V_{C o n v e x} (P_{k}))$ : Spatial transformation to match a priority micro-robot width.

$F (σ)$ : Generated trajectory using the Lorenz equation.

These paths are concerned with only two pioneer sub-leaders that compose the head of the flocking part. These two are chosen based on the following: the micro-robots closest to the congestion area and those forming the front of the robot are the sub-leaders.

With regard to the flocking part, we consider each agent as a simple follower using the same control law developed before, but with different sub-leaders. The introduction of the term ‘flocking' implies respect for the three rules discussed before. First, the agents have to move in the same direction as their neighbours.

To accomplish this, we replace the bearing angle between the leader and their followers by a reference angle. The second rule implies that they remain close to their neighbours. We keep the desired distance equal to the initial distance between each follower and its respective sub-leader. Finally, the agents must avoid collisions with their neighbours, by equipping each agent with a local collision avoidance ability.

The modified control law is given by:

v_{i j} (k) = S_{i j} \cos (γ_{i j}) - l_{i j} \sin (γ_{i j}) (b_{i j} + ω_{i k}) + v_{i k} \cos (θ_{i k} - θ_{i j})

(10)

ω_{i j} (k) = \frac{S_{i j} \cos (γ_{i j}) - l_{i j} \sin (γ_{i j}) (b_{i j} + ω_{i k}) + v_{i k} \cos (θ_{i k} - θ_{i j})}{d}

(11)

where:

\begin{array}{l} γ_{i j} = θ_{i k} + ψ_{i j} - θ_{i j} and S_{i j} = k_{1k} (l_{i j}^{d} - l_{i j}) \\ b_{i j} = k_{2 k} (ψ_{i j}^{d} - ψ_{i j}), l_{i j} = \sqrt{{(x_{i k} - x_{i j})}^{2} + {(y_{i k} - y_{i j})}^{2}} \\ ψ_{i j} = π - θ_{i k} + \tan^{- 1} \frac{(y_{i k} - y_{i j})}{(x_{i k} - x_{i j})} \end{array}

where:

v_ik(k): Linear velocity of the j^th follower with respect to the k^th sub-leader.

ω_ik(k): Angular velocity of the j^th follower with respect to the k^th sub-leader.

v_ik: Linear velocity of the k^th sub-leader.

ω_ik: Angular velocity of the k^th sub-leader.

θ_ik: Orientation of the k^th sub-leader.

k_1k, k_2k: Positive gains relative to the k^th sub-leader

The desired distances between the k^th sub-leader and the follower i, j and k are equal to the real distance between these two micro-robots when the congestion avoidance process starts. We will not consider a desired angle between the sub-leader k and the followers i, j and k, but we will use the desired angle between the followers i, j and k and the reference, which is equal to the orientation of the follower at each time t.

The following algorithm in Table 1 shows the proper sequence for avoiding a congestion conflict. Using the algorithm introduced in this table, all the robots are able to reach their respective objective by avoiding the creation of a congested area.

However, in order to ensure the troop's success in reaching its target without the appearance of conflicts, a temporal synchronization needs to be developed for the non-priority troop while the other troop crosses the potential congestion area. To achieve this, we impose on the non-priority group the requirement that it reach the safest zone, which we define as the apogee (peak) of the curve generated with the Lorenz equations, when the priority group passes by the other group. In addition, we allow the non-priority group to exceed its initial velocity to a value that can reach the maximum velocity of the troop while splitting. This maximum velocity is defined in what follows and concerns the path following the control law.

In some cases, only the sub-leader composes a subgroup while other agents safely follow the second sub-leader. This shows clearly that the partitioning does not separate the non-priority troop into equal subgroups but that it still depends upon the posture of each follower before the flocking compared with its relative leader. The followers will only choose the closest sub-leader to flock to in order to get to the safest relative subgroup. However, this still also depends on the initial maintenance approach that we impose.

Table 1.

Congestion avoidance algorithm applied in all troops

ALGORITHM - CONGESTION AVOIDANCE
Start i^th group formation control Start reach target Check If congestion risk {Compute Pt_i If Pt_i = 1 Estimate the encountering angle α Compute F(σ) % (path from Lorenz equation) Compute ς_ij = Γ(V_Convex(P_k))·F(σ) Apply ς_ij to the closest r_ij micro-robots to the priority group Force remaining agents to choose a sub-leader and start flocking If risk of congestion disappear {Reach target and form the unification} Else ignore congestion risk } End

ALGORITHM - CONGESTION AVOIDANCE

Start i^th group formation control Start reach target Check If congestion risk {Compute Pt_i If Pt_i = 1 Estimate the encountering angle α Compute F(σ) % (path from Lorenz equation) Compute ς_ij = Γ(V_Convex(P_k))·F(σ) Apply ς_ij to the closest r_ij micro-robots to the priority group Force remaining agents to choose a sub-leader and start flocking If risk of congestion disappear {Reach target and form the unification} Else ignore congestion risk } End

Accordingly, let us introduce the sub-leaders' control law in order to follow the generated trajectories. Constraints exist at different levels of a control system for a mobile micro-robot. At the motor level, the magnitude of voltages and currents are limited, and at a trajectory level the same goes for velocities and accelerations [15]. Since the path following algorithm is a velocity trajectory generator that generates references to the underlying motor controllers, only constraints on the velocities of the micro-robot are considered.

The kinematic model linking the velocities v_ik and ω_ik with the differentially actuated left and right wheels v_Lik and v_Rik respectively is denoted as:

\begin{matrix} v_{i k} = \frac{1}{2} (v_{R i k} + v_{L i k}) \\ ω_{i k} = \frac{1}{2 b} (v_{R i k} + v_{L i k}) \end{matrix}

(12)

where 2b is the given distance between the common axis of the left wheel and the right wheel.

Let $v_{\max}^{ω}$ and - $v_{\max}^{ω}$ be the maximum and the minimum velocities for the left and the right wheel, such that:

- v_{\max}^{ω} < v_{R i k} < v_{\max}^{ω} & - v_{\max}^{ω} < v_{L i k} < v_{\max}^{ω}

(13)

As is known, the micro-robot can move on paths of an arbitrary curvature given by:

K_{k} = \frac{1}{b} \frac{v_{R i k} - v_{L i k}}{v_{R i k} + v_{L i k}}

(14)

Because, in our work, we consider non-holonomic micro-robots, we impose a positive value constraint for both the speeds v_Lik and v_Rik, which implies that the curvature becomes bounded if:

v_{\max}^{ω} = V_{m} & v_{R i k}, v_{L i k} \in [0, V_{m}] \Rightarrow K_{k} \in [- \frac{1}{b}, \frac{1}{b}]

(15)

In order to develop the path following control law, we will apply a suitable change of variables, as developed in [15] using the Frenet frame. The sub-leaders' model becomes:

\begin{array}{l} {\dot{x}}_{1 i k} = - {\dot{μ}}_{k} (1 - K_{r} y_{1 i k}) + v_{i k} \cos θ_{1 i k} \\ {\dot{y}}_{1 i k} = - K_{r} {\dot{μ}}_{k} x_{1 i k} + v_{i k} \sin θ_{1 i k} \\ {\dot{θ}}_{1 i k} = ω_{i k} - K_{r} {\dot{μ}}_{k} \end{array}

(16)

where:

K_r: The curvature of the reference path.

μ_k: The scalar that parameterizes the path $ς_{i j}$ .

By considering this change of variables, we adapt the control law developed in [20] in order to follow the generated path, such that the control law becomes:

\begin{matrix} v_{R i k} = v_{i k} + b (K_{r} {\dot{μ}}_{k} + {\dot{θ}}_{1 i k}) \\ v_{L i k} = v_{i k} - b (K_{r} {\dot{μ}}_{k} + {\dot{θ}}_{1 i k}) \end{matrix}

(17)

As indicated, we also allow the non-priority group to exceed its initially-used velocity to a value that can reach the maximum velocity of the troop while splitting. In order to command wheel velocities to the highest possible (positive) linear velocity v_ik, the following should be satisfied:

\max {v_{R i k}, v_{L i k}} = | v_{i k} | (1 + b | K_{i C l o s e d L o o p} |) = V_{m} \Rightarrow v_{i k} = \frac{V_{m}}{(1 + b | K_{i C l o s e d L o o p} |)}

(18)

with:

K_{i C l o s e d L o o p} = K_{r} \cos θ_{1 i k} + ε & ε \leq \frac{1}{b} - K_{r M a x}

This approach is followed only if the splitting requires a fast time of accomplishment due to time constraints. Otherwise the use of such an approach is not completely necessary.

6. Reaching the Target & Unification

The goal that we impose on micro-robots is that they should reach their respective target by choosing a leader in each subgroup that steers them to the goal. However, if one subgroup stands to meet the other subgroup, both subgroups must have the ability to unify themselves in order to form the initial troop. The unification that we will use was developed in [16] and the goal that we want to reach is to develop an algorithm that divides a group of micro-robots into sets; in each set, a choice for the election of the leader that will steer the other agents to accomplish the displacement task will be performed. Based on this, each micro-robot is outfitted with a virtual proximity area, which can be illustrated as a circle with a fixed radius, as shown in Figure 7.

Accordingly, if the proximity area of one micro-robot overlaps with another proximity area of another micro-robot, these two will be listed in the same set. Applying this process to the entire elements of the group, we can define the number of sets and get the micro-robot membership list. Moreover, in order to illustrate each set as an independent robot, a convex hull defined as a non-ambiguous and efficient representation of the required convex shape algorithm is applied in each sub-group to define the envelope of each set. The second step, after defining each sub-group, consists in constructing a list of criteria that allows the sub-groups to choose a leader and reach the unification of the entirety of the divided robots. The number of criteria depends upon the assumptions that we have already made. The distance of the micro-robot and its orientation compared with the target are chosen as criteria. Let:

\begin{array}{l} d_{i j k} = \sqrt{{(x_{i j k} - X_{i Target} (1))}^{2} + {(y_{i j k} - X_{i Target} (2))}^{2}} \\ θ_{i j k} = \arctan (\frac{y_{i j k} - X_{i Target} (2)}{x_{i j k} - X_{i Target} (1)}) \end{array}

(19)

where:

d_ijk: Distance between the j^th agent in the k^th subgroup

and the target.

Figure 7.

Illustration of the sets' definitions using overlapping, where the virtual circular boundaries of a robot overlap with those of another robot, these two robots will be included in the same subgroup

In order to choose the leader, we define a selection factor which depends upon the listed criteria:

f_{i j k} = \frac{d_{i j k}}{(\sum_{1}^{n_{k}} d_{i j k}) / n_{k}} + \frac{θ_{i j k}}{(\sum_{1}^{n_{k}} θ_{i j k}) / n_{k}}

(20)

where:

f_ij: Selection factor of the j^th micro-robot in the i^th group.

n_k: Number of micro-robots in the k^th subgroup.

The leader in each sub-group will be that element which has a minimum selection factor compared with the other element's selection factor of the same sub-group. In most cases, the leader in each subgroup will be the leader that has been already been chosen as a sub-leader while bifurcating. Thus, we proposed this method to ensure an efficient leader in the configuration space and also to give the ability to subgroups to reach their target even if the unification is not performed. Sometimes, and depending upon the configuration of the micro-robots, the number of elements in one sub-group can only be one. In this case, we directly set a desired position for this micro-robot to join the initial formation used in the first maintenance part.

7. Experiments

For the purpose of presenting our experiment, some specifications need to be known:

The priority group has been chosen offline.

Due to the delay of the tracking data, the velocity of the troops does not exceed 100mm/s.

Due to Bluetooth connection restrictions, only seven micro-robots are used.

The initial conditions of the Lorenz equations are: x = 0.2, y = 0.2, z = 0.

The range of σ is, in other words, if α = 0 → σ will tend to 0 and if α = π → σ = 30.

The radius R_g used to detect the risk of congestion using a virtual circle overlapping technique is equal to 300mm.

To establish our experiment, we developed some algorithms that allow the e-puck [26] to calculate its position through odometry, to have a local collision avoidance ability using data from proximity sensors, and also to reach a defined target using the proportional control law. A formation control algorithm has also been developed to challenge both maintenance and reaching the target in order to keep a structured troop formation. The basic assumptions used to establish the experiment are:

All of the micro-robots are considered to be non-holonomic robots.

The position and the orientation of each micro-robot is known at any time t.

We assume that only two troops can meet with each other at a certain time, and any case when more than two troops meet each other will not be considered.

Each micro-robot is already equipped with a local collision avoidance algorithm.

7.1. First scenario: Micro-Robots are facing each other.

In this case, both the proposed method and that presented in [1] are exposed. As has already been proven in [1], the congestion problem is totally solved by the coordinated method, except that the micro-robot troops must have an equal velocity in order to ensure coordination.

Figure 8.

From left to right, the sequence of congestion avoidance using the coordinated method. From t₁ to t₃, the maintenance step, from t₄ to t₆, the coordination step, and finally the step for reaching the target at t₇ and t₈.

Figure 8 shows the sequence of congestion avoidance using the coordination method. The same scenario is solved using our proposed method and the results are presented in Figure 9. Since the troops are facing each other, we considered a meeting angle α close to π which implies a trajectory generated using a σ = 30.

Figure 9.

From left to right, the congestion avoidance sequence when the encountered angle α is close to 0. All of the maintenance, bifurcation, target reaching and unification steps are fully accomplished. From t₁ to t₄→ Maintenance, from t₅ to t₈ Bifurcation, from t₉ to t₁₂→ Unification and reaching the target. The choice of the sub-leaders follows the rules whereby the two elements closest to the potential congested area are chosen directly as sub-leaders while the remaining elements flock relatively to one of these sub-leaders.

7.2. Second scenario: Null encountering angle α.

In this case, a low value of σ is used to generate the path. As indicated before, depending upon the prompt appearance of the congestion risk, the V_m developed in the path following path can be used to ensure a fast bottlenecking. This method has been used in this case where micro-robots were splitting in order to reach their maximum speed and to leave the way free for the priority group. Figure 10 shows the sequence of experimental results.

Figure 10.

From left to right, the congestion avoidance sequence when the encountered angle α is close to 0. All of the maintenance, bifurcation, reaching the target and unification steps are fully accomplished. From t₁ to t₂, the maintenance step, from t₃ to t₆, the coordination step and, finally, the unification and target reaching step, in t₇ and t₈.

7.3. Third scenario: Encountering angle α = 5π/4.

The meeting angle is estimated using the data of the convex hull of both troops after detecting the risk of congestion. In this situation, the generated trajectories lose their symmetry but adapt the path for a suitable avoidance of the incoming priority group. Figure 11 shows the congestion avoidance sequence relative to this case.

Figure 11.

From left to right, the congestion avoidance sequence when the encountered angle α = 5π/4. All of the maintenance, bifurcation, reaching the target and unification steps are fully accomplished. From t₁ to t₂, the maintenance step, from t₃ to t₆, the coordination step and, finally, the unification and target reaching step, in t₇ and t₈. The value of σ was computed offline so as to rapidly get the trajectories parameterization data.

8. Conclusion

In this paper, we presented a new approach to avoid the problem of congestion when the troops of micro-robots meeting in a common area cause complex situations. The proposed algorithm was inspired from the behaviour of schools of fish in both natural and risky situations. As such, the problem of avoiding such conflict was solved by noticing that, in a risky situation, the members of some schools of fish undertake various paths while the remaining members simply flock by following other entities. Using this concept, the problem was simplified by selecting a priority group using certain criteria that maintains its initial displacement while providing the ability to the other troop to follow that behaviour which can be recognized in some schooling populations.

To reach our goal, we had to prepare a global and a local communication network that would reduce the data exchanged between the micro-robots and which would also anticipate the congestion by detecting its occurrence through a simple method. The bifurcation part, which uses the Lorenz equation, provides the micro-robots with the ability to deviate their displacement and divide their configuration into two subgroups, depending upon the troops' estimated meeting angle. By generating two paths, two sub-leaders from the non-priority troop come along the paths using a path following control law, while the remaining micro-robots of the same troop flock relatively to a chosen sub-leader. Finally, when the risk of congestion disappears, this same troop reconsiders its initial goal to reach its target while giving to the micro-robots the ability to reunify in their initial configuration. A series of experiments confirms the validity of our proposed method and some comparisons with other, existing methods were also performed.

Footnotes

9. Acknowledgments

This work was supported, in part by a Korea Science and Engineering Foundation (KOSEF) NRL Program grant funded by a Korean government (MEST) (No.R0A-2008-000-20004-0), in part by the Brain Korea 21 Project, and in part by the Industrial Foundation Technology Development Program of MKE/KEIT [Development of CIRT (Collective Intelligence Robot Technologies)].

References

Leandro Soriano Marcolino, Luiz CHAIMOWICZ (2009) Traffic Control for a Swarm of Robots: Avoiding Group Conflicts, IEEE International Conference on Intelligent Systems.

Maniccam

(2008) Adaptive decentralized congestion avoidance in two-dimensional traffic, Physica A: Statistical Mechanics and its Applications, Vol. 387, No. 12, p. 3072.

Khatib

Oussama

(1986) Real-Time Obstacle Avoidance for Manipulators and Mobile Robots, The International Journal of Robotics Research.

Fox

Dieter

Burgard

Wolfram

Thrun

Sebastian

(1998) A Hybrid Collision Avoidance Method for Mobile Robots, IEEE International Conference on Robotics and Automation.

Mastellone

Silvia

Stipanovi'c

Dušan M.

Graunke

Christopher R.

Intlekofer

Koji A.

Spong

Mark W.

(2008) Formation Control and collision Avoidance for Multi-agent Non-holonomic Systems: Theory and experiments, the International Journal of Robotics Research.

Borenstein

Koren

(1991) The vector field histogram - fast obstacle avoidance for mobile robots, IEEE Transactions on Robotics and Automation.

Fox

Burgard

Thrun

, (1996) Controlling synchrodrive robots with the dynamic window approach to collision avoidance, Proc. of the IEEE/RSJ.

Choi

Jeong S.

Eoh

Gyuho

Kim

Jimin

Yoon

Younghwan

Park

Junghee

Lee

Beom H.

(2010) Analytic Collision Anticipation Technology Considering Agents' Future Behavior, IEEE/RSJ International Conference on Intelligent Robots and Systems, Taipei, Taiwan.

Hwan

Park Seung

Hee

Lee Beom

(2006) Analysis of Robot Collision Characteristics Using the Concept of the Collision Map, Robotica, Vol.24, pp. 295–303.

10.

Lee

Tae S.

Eoh

Gyu H.

Lee

Heon C.

Lee

Seung H.

Lee

Jeong H.

Choi

Hyun T.

Lee

Beom H.

(2010) Reactive Collision Avoidance of a Mobile Robot in Route Environments, International Symposium on Intelligent Systems, Hachioji, Japan.

11.

Marcolino

L. S.

Chaimowicz

(2008) No Robot Left Behind: Coordination to Overcome local Minima in Swarm Navigation, in Proceedings of the 2008 IEEE International Conference on Robotics and Automation.

12.

Nishimura

Yasuhiro

Lee

Geunho

Chong

Nak Young

(2010) Decentralized Adaptive Flocking in Three Dimensional Space, URAI.

13.

Olfati-Saber

Reza

(2004) Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory, IEEE Transactions on Automatic Control.

14.

Fierro

Das

Kumar

Ostrowski

J. P.

(2001) Hybrid Control of Formations of Robots, International Conference on Robotics and Automation.

15.

Indiveri

Giovanni

Nüchter

Andreas

Lingemann

Kai

(2007) High Speed Differential Drive Mobile Robot Path Following Control With Bounded Wheel Speed Commands, IEEE International Conference on Robotics and Automation.

16.

Yaniss

Touahmi

lee

Beom Hee

(2010) Control of Multi-agent using adaptive leader selection, KROS.

17.

Shams

Soheil

(2006) Simultaneous recognition of multiple objects using the MEM model, Lecture Notes in Computer Science.

18.

Bak

Martin

Poulsen

Niels Kjolstad

Ravn

Ole

(2001) Path Following Mobile Robot in the Presence of Velocity Constraints, Informatics and Mathematical Modeling, Technical University of Denmark.

19.

Breder

C. M.

Jr. (1954) Equation Descriptive of Fish Schools and Other Animal Aggregations, Ecology, Vol. 35, No. 3.

20.

Lee

S.-H.

Park

J. H.

Chon

T.-S.

Pak

H. K.

(2006) Prey-Flock Deformation under a Predator's Attack, Journal of the Korean Physical Society, Vol. 48, pp. S236–S240.

21.

de Ipiña

Diego López

Mendonça

Paulo R. S.

Hopper

Andy

(2002) TRIP: A Low-Cost Vision-Based Location System for Ubiquitous Computing, Personal and Ubiquitous Computing.

22.

Postel

(1980) User Datagram Protocol, ISI.

23.

Fraichard

Th.

(1993) Dynamic trajectory planning with dynamic constraints a ‘State-Time Space’ approach, Conference on Intelligent Robots and Systems.

24.

Samson

Ait-Abderrahim

“Feedback control of a non-holonomic wheeled cart in Cartesian space”, Proceedings of IEEE International Conference on Robotics and Automation, 1991.

25.

David

D. Grossman

, “Traffic Control of Multiple Robot vehicles” IEEE Journal of Robotics and Automation, October 1988.

26.

Mondada

Bonani

Raemy

Pugh

Cianci

Klaptocz

Magnenat

Zufferey

J.-C.

Floreano

Martinoli

, “The e-puck, a Robot Designed for Education in Engineering” Proceedings of the 9th Conference on Autonomous Robot Systems and Competitions, 1(1) pp. 59–65, 2009.