_{1}

^{*}

Technically, a group of more than two wheeled mobile robots working collectively towards a common goal are known as a multi-robot system. An increasing number of industries have implemented multi-robot systems to eliminate the risk of human injuries while working on hazardous tasks, and to improve productivity. Globally, engineers are continuously researching better, simple, and faster cooperative Control algorithms to provide a Control strategy where each agent in the robot formation can communicate effectively and achieve a consensus in their position, orientation and speed.
This paper explores a novel Formation Building Algorithm and its global stability around a configuration vector. A simulation in MATLAB
^{?}
was carried out to examine the performance of the Algorithm for two geometric formations and a fixed number of robots. In addition, an obstacle avoidance technique was presented assuming that all robots are equipped with range sensors. In particular, a uniform rounded obstacle is used to analyze
the performance of the technique with the use of detailed geometric calculations.

Multiple studies show that novel and better multi-agent formation algorithms have been proposed in recent years. The idea behind developing control laws for large-scale systems is to provide an alternative for the control of a group of autonomous vehicles dynamically decoupled [

The use of studies on basic motion dynamics in biology let us generate powerful algorithms to recreate geometric formations for groups of wheeled mobile vehicles [

The goal of the research behind Formation Building Algorithms is to reduce the risk of hazardous tasks currently done by humans [

Different algorithms have been formulated for multi-agent systems exploring a vast number of control laws for a first and a second order approach. The first visible example of some of the control algorithms can be found in [

The aim is to model a Formation Building Algorithm presented in the journal article [

To begin with, we take the spatial coordinates ( x , y ) in a global reference frame, and the orientation θ about the x-axis (

Let us take the linear speed v i ( t ) and the angular velocity w i ( t ) as the control inputs of the system, computed later with a novel distributed control technique based on the consensus between vehicles, and their adjacency in the reference frame. Such adjacency is calculated with the help of the Euclidean distance formula (

If the distance is less or equal to a reference range, they are said to be connected through an edge under the graph analysis [

( x ˙ i ( t ) y ˙ i ( t ) θ ˙ i ( t ) ) = ( v i ( t ) cos ( θ i ( t ) ) v i ( t ) sin ( θ i ( t ) ) w i ( t ) ) (1)

Let i = 1 , 2 , ⋯ , n be the number of robots found in the multi-robot system, each with Cartesian coordinates ( x i ( t ) , y i ( t ) ) with its heading measured counterclockwise from the x-axis. As explained before the linear and angular speed control inputs are applied distributed to each of the agents of the group of wheeled mobile vehicles. The standard kinematics are not only used to describe the dynamical behavior of wheeled vehicles, but for many other artifacts, such as UAVs, smart missiles, etc. [

− w max ≤ w i ( t ) ≤ w max V m ≤ v i ( t ) ≤ V M w max > 0 and 0 < V m < V M (2)

Each robot communicates at a discrete time k = 1 , 2 , ⋯ , n . Based on the graph analysis we assume that each of the nodes that belongs to the group of robots is connected through a set of lines that forms an undirected graph. In [_{c}. Back in [

Some of the assumptions found in [

θ i ˜ ( k + 1 ) = θ i ˜ ( k ) + ∑ j ∈ N i ( k ) θ j ˜ ( k ) | 1 + N i ( k ) | x i ˜ ( k + 1 ) = ( x i ˜ ( k ) + x i ( k ) ) + ∑ j ∈ N i ( k ) ( x j ˜ ( k ) + x j ( k ) ) | 1 + N i ( k ) | − x i ( k + 1 ) y i ˜ ( k + 1 ) = ( y i ˜ ( k ) + y i ( k ) ) + ∑ j ∈ N i ( k ) ( y j ˜ ( k ) + y j ( k ) ) | 1 + N i ( k ) | − y i ( k + 1 ) θ i ˜ ( k + 1 ) = θ i ˜ ( k ) + ∑ j ∈ N i ( k ) θ j ˜ ( k ) | 1 + N i ( k ) | (3)

If we analyze further the behavior of the equations when k tends to infinite, we may find that each of the values converges to a constant value θ o ˜ , v o ˜ , x o ˜ , y o ˜ , such that:

lim k → ∞ θ i ˜ ( k ) = θ o ˜ lim k → ∞ v i ˜ ( k ) = v o ˜ lim k → ∞ ( x i ˜ ( k ) + x i ( k ) ) = X o ˜ lim k → ∞ ( y i ˜ ( k ) + y i ( k ) ) = Y o ˜ (4)

This is shown in [_{ }

lim t → ∞ θ i ( t ) = 0 lim t → ∞ v i ( t ) = v o ˜ lim t → ∞ ( x i ( t ) − x j ( t ) ) = X i − X j lim t → ∞ ( y i ( t ) − y j ( t ) ) = Y i − Y j (5)

From the above definition one can say that all vehicles will have the same speed and orientation along the x-axis maintaining the formation configuration C . The journal article [

maximum linear and angular speed as 2 V M w max , known to all the robots.

Let us introduce a two-dimensional vector h i , which defines the behavior and location of the fictitious target T :

h i ( t ) = ( x i ( t ) + x i ˜ ( t ) ) + X i + t v i ˜ ( t ) (6)

The fictitious target coordinates x and y are calculated as:

g i x ( t ) = { h i ( t ) + c , if x i ( t ) ≤ h i ( t ) x i ( t ) + c , if x i ( t ) > h i ( t ) g i y ( t ) = ( y i ( t ) + y i ( t ) ˜ ) + Y i (7)

We form a vector that includes both x and y coordinates:

g i = ( g i x g i y ) (8)

In

vector of each robot coordinates z i ( t ) = ( x i ( t ) y i ( t ) ) and the vector of the fictitious

target g i , is what we know as the distance ahead of the robot to the target at each instant of time: d i ( t ) = g i ( t ) − z i ( t ) .

The Decentralized Control Law defined in [

v i ( t ) = { V M , if x i ( t ) ≤ h i ( t ) V m , if x i ( t ) > h i ( t ) w i ( t ) = w max F ( V i ( t ) , d i ( t ) ) (9)

Here: V i ( t ) = ( x ˙ i ( t ) y ˙ i ( t ) ) , and the Function F ( V i ( t ) , d i ( t ) ) is defined by the sign of the angle between V i ( t ) and d i ( t ) .

Another of the challenges presented is the presence of obstacles in addition to the distributed control law described in the previous chapter. At this point, a fix circular obstacle is placed with coordinates ( X o , Y o ) and according to [

The sensor detects an obstacle at certain distance r_{s}, and with a calculation the robot determines the range and angle to the landmark.

The robot collects all the information from the sensors and proceeds to evaluate the actions required to avoid the obstacle, in other words, it finds the route away from the collision path. The algorithm applied comes from an extensive analysis performed in documents such as [

the robot detects an obstacle once inside the range of the sensor. The robot adjusts its heading and speed to maintain a distance from the surface of the obstacle. Taking R_{t} as the turning radius and d the distance from the obstacle when the robot is moving parallel to the obstacle, one can calculate maximum rotation and minimum distance boundaries, respectively.

R t max = V M w max

d min = r s − R t max

Assumptions are considered for this problem. Firstly, we can assume that the robot displacement is parallel and along the circumference perimeter. Secondly, we assume that the obstacle is considerably big to represent the surface of the obstacle as a flat long rectangle. At this point, the sensor detects at a distance r_{s} the obstacle and taking as reference the center of the robot there will be an angle between the heading of the vehicle and the ray that the sensor emits. This difference is considered the desired avoidance angle and can be calculated as:

φ o = sin − 1 ( d o r s ) (10)

Where, d_{o} is the farthest point that the sensor can detect from the central point of reference of the robot coordinates. If there is a curved obstacle the robot should keep a constant distance from the surface of the landmark as explained before; however, in this case, the sensor detects that the angle of avoidance φ is greater than the desired angle φ o , with a difference:

Δ ϕ = | φ − φ o | (11)

The angular rate of change is what the robot needs to correct to preserve the desire distance from the obstacle. In _{o}. The angle between the heading of the robot and the virtual representation of the sensor ray for a flat surface is φ o defined as the desired avoidance angle. At this point as the surface is not flat but convex the robot needs to rotate Δ ϕ towards the obstacle to preserve a distance d_{o} from it.

Again, we can consider the existence of a fictitious target T , located at a distance to the robot denoted by r_{s} and an angle Δ ϕ which becomes the rate of change necessary to keep a distance d_{o} from the obstacle while avoiding it. Given some equalities and according to

are equal since the angles projected θ ′ and θ ″ are equal in value as well. Furthermore, the segment A B ¯ as a result of the union of the respective points is equal to the segment C D ¯ . The angle formed by the points ∡ O D B = ∡ O C D = γ that in turn shows the equality of the triangles formed by the points BED and AFC. Therefore, the distances represented by the segment AF, which is the distance from the vehicle to the obstacle is equal to the segment B E = d o [

If C is the point where the fictitious target is located, one can determine that the robot will maintain a constant distance from the obstacle. If the obstacle has a sudden change in the shape, we can see that the fictitious target will change its location to maintain a fixed distance from the obstacle and readjust robot heading (

In that order, the robot needs to rotate Δ ϕ degrees to maintain the distance d_{o}, for both scenarios: the flat and convex surfaces. The proposed control rule, like the one described in the previous chapter, is designed to calculate the linear and angular speed necessary to move the robot away from the collision course around the obstacle [

v i ( t ) = V M w i ( t ) = w max sign ( ψ i ( t ) ) ψ i ( t ) = { 1 if θ < θ o 0 if θ = θ o − 1 if θ > θ o (12)

The sign of the angle and the constant maximum angular velocity are provided by the control rule described in the previous chapter.

Numerical simulation results are presented for the control law and consensus

variables algorithm under analysis (3) and (9). MATLAB^{®} a well-known programming environment and numerical analysis tool was used to simulate and interpret the Formation Building Algorithm presented in [_{c} (

Thus,

− 2 ≤ w i ( t ) ≤ 2 0.2 m / s ≤ v i ( t ) ≤ 1.5 m / s w max > 0 and 0 < V m < V M

The formation configuration vector C was defined for both shapes as: (

Simulations for the Line and Delta formation are shown in

Parameter | Configuration settings | ||||
---|---|---|---|---|---|

t | V M | V m | c = 2 V M w max | r c | |

value | 50 s | 1.5 m/s | 0.2 m/s | 1.5 | 2 m |

Parameter | Line shape | Delta shape |
---|---|---|

value | C = [ 0 − 2 ; 0 − 1.5 ; 0 − 1 ; 0 − 0.5 ; 0 0 ] | C = [ 0 − 1.5 ; 1 − 1 ; 2 − 0.5 ; 1 0 ; 0 0.5 ] |

According to [

In Lemma 3.1 [_{o} and Y_{o} for the X and Y coordinates, respectively, as shown in

The same is seen in the consensus heading and speed of the robot that converges to a constant value when the discrete time k tends to infinite as seen in

Now, for obstacle avoidance, we assume that the robot is equipped with a set of range sensors. Those sensors help the robot to determine the distance from a fixed round obstacle placed at ( X o , Y o ) with a radius r_{o}. According to the obstacle avoidance algorithm the robot maintains a desired angle, which comes from the relation between the heading of the vehicle and the projected line of the sensor range, given that the robot should maintain a desired distance from the obstacle. We implemented a set of equations for the intersection points between the obstacle surface and the radial detection range of the sensor (

Parameter | lim k → ∞ ( x i ˜ ( k ) + x i ( k ) ) = X o ˜ | lim k → ∞ ( y i ˜ ( k ) + y i ( k ) ) = Y o ˜ |
---|---|---|

value | 1.95881 | 2.06918 |

Parameter | lim k → ∞ θ i ( k ) ˜ = θ o ˜ | lim k → ∞ v i ( k ) ˜ = V o ˜ |
---|---|---|

value | 1.52412 rads | 0.388873 m/s |

The first of the equations finds the range of the radial sensor about the robots’ instant position ( x r , y r ) :

r s 2 = ( X − x r ) 2 + ( Y − y r ) 2 (13)

The surface of the obstacle is defined by:

r o 2 = ( X − x o ) 2 + ( Y − y o ) 2 (14)

By solving these two Equations (13) and (14), we find the intersection points, where ( x r , y r ) , and ( x o , y o ) are the robot and obstacle coordinates, respectively. Moreover, by expanding and subtracting them we get:

− 2 X ( x r − x o ) − 2 Y ( y r − y o ) = ( r s 2 − r o 2 ) − ( x r 2 − x o 2 ) − ( y r 2 − y o 2 ) (15)

Solving 15 for Y we get:

Y = − X x r − x o y r − y o + − ( r s 2 − r o 2 ) + ( x r 2 − x o 2 ) + ( y r 2 − y o 2 ) 2 ( y r − y o ) (16)

Substituting Equation (16) in Equation (15), we get the equation for the intersection point in X only:

[ 1 + ( x r − x o ) 2 ( y r − y o ) 2 ] + [ ( − 2 x o + 2 y o ( x r − x o ) ( y r − y o ) ) + ( ( x r − x o ) ( ( r s 2 − r o 2 ) + ( x r 2 − x o 2 ) + ( y r 2 − y o 2 ) ( y r − y o ) 2 ) ) ] X + x o 2 + y o 2 − r o 2 + ( − ( r s 2 − r o 2 ) + ( x r 2 − x o 2 ) + ( y r 2 − y o 2 ) 2 ( y r − y o ) ) 2 + y o ( r s 2 − r o 2 ) − ( x r 2 − x o 2 ) − ( y r 2 − y o 2 ) ( y r − y o ) = 0 (17)

with the use of the function “roots” implemented in MATLAB^{®} the polynomial Equation (17) can be solved. The solution indicates whether the sensor detects an obstacle or not. If the solution is real it means there is a detection, while it does not if it is conjugated. The value obtained should be always positive ahead in front of the robot to tell them that a control input needs to be applied to avoid the obstacle maintaining a fixed distance d_{o} from it. The robot rotates counterclockwise if its position is below the obstacle, and clockwise if the robot is located above the obstacle (

We can see that for both the response of the Distributed Control Law together with Formation Building Algorithm and the obstacle avoidance technique is considerably rapid and adjusts the parameters in a few seconds. The results let us claim that the system is globally stable with random initial conditions around the configuration vector C. In addition, it is said that the limit of the difference in the position between robots, when the time tends to infinite is equal to the difference in the values contained in the formation configuration vector C. For illustrative purposes we present the plot for robot 1 and 2 (

lim t → ∞ ( x i ( t ) − x j ( t ) ) = X i − X j lim t → ∞ ( y i ( t ) − y j ( t ) ) = Y i − Y j

Theorem | lim t → ∞ ( x i ( t ) − x j ( t ) ) = X i − X j | lim t → ∞ ( y i ( t ) − y j ( t ) ) = Y i − Y j |
---|---|---|

value | ~0 | ~−0.5 |

To conclude, we proved through simulation that the Formation Building Algorithm (3), and Control Law (9) is Globally stable for any initial conditions around a configuration vector C.

The document presents the simulation for two different configurations a line and arrow-head formation. The Formation Building Algorithm applies a Distributed Control Law, where there exists a fictitious target, always located ahead far from the robot position.

The fictitious target position depends on the value of the constant variable c. If c has a small value, the system reaches faster the target position resembling a pure pursuit control technique. The Distributed Control Law applies constraints to both the angular and linear velocity, and unlike other algorithms, the one under review does not have any visible leaders in the formation.

We found and aligned with the journal paper, that all the robots reach an agreement in their position, heading and speed based on local information from other robots under the graph analysis. Also, that the control rule satisfies all theorems and assumptions.

On the other hand, the simulation of the obstacle avoidance algorithm, showed us that the robot maintains a desired distance to the obstacle while applying the required control inputs in order to change its orientation with the use of advance geometric analysis.

The group of robots start at a random initial position, apply the Consensus Algorithm to build the spatial formation, those that detect the obstacle change their path to avoid collision and once they have passed the obstacle, all robots form again the shape, always parallel to the x-axis. The robots are assumed to be equipped with linear range sensors that detect an obstacle at certain distance r_{s}. Further mathematical proof of the algorithms can be found in the core paper under analysis.

The author declares no conflicts of interest regarding the publication of this paper.

Levkovsky, M. (2021) Review and Simulation of a Novel Formation Building Algorithm While Enabling Obstacle Avoidance. World Journal of Engineering and Technology, 9, 155-172. https://doi.org/10.4236/wjet.2021.91012