Intelligent navigation of multiple coordinated robots

Abstract

Navigation of multiple robots is a challenging task, particularly for many robots, since individual gains may more often than not adversely affect global gain. This paper investigates the problem of multiple robots moving towards individual goals within a common workspace without colliding amongst themselves. Two solutions for coordination namely Fuzzy Logic Controller (FLC) and Genetic Algorithm based FLC (GA-FLC) have been employed and the efficacy of cooperation strategies have been compared with their non-cooperative counterparts as well as with the fundamental potential field method (PFM). Proposed coordination schemes are verified through simulations. A total of 100 scenarios are considered varying the number of robots (8, 12, 16 and 20). The obtained results show the efficacy of the proposed schemes.

Keywords

Multi-agent systems motion planning coordination

1 Introduction

Motion coordination among multiple mobile robots is a challenging proposition, particularly when negotiating on a common workplace. Higher the number of robots more tedious is their motion planning. A wide variety of taxonomies exist in robot motion planning parlance that accounts for diverse environmental conditions, the existence of other robotic entities in the workspace, nature of any obstacles in the workspace, local and global criteria for path planning and so on. A brief account can be obtained from [1]. A particular mobile robot navigates through static or dynamic obstacles in steps with determining its next position towards the goal by satisfying a variety of conditions such as path, time, energy-optimality etc. This utilizes the local path planning mechanism. The primary objective is to find collision-free path.

In this paper, a dynamic path planning is addressed with multiple mobile robots sharing a common workspace. These robots are characterized by their respective source and destination points within the workspace and respective velocities. Each robot is capable of accelerating/decelerating to avoid collision with other robots and a fixed time interval for periodic updations in position, velocity, and strategy. In that sense, the problem addressed in this paper falls under dynamic motion planning (DMP) category and a wide variety of fuzzy approaches have been employed, particularly to emphasize on user-defined rules setting for collision-free paths [2 –4]. Generally, such approaches alleviate computational burden as well. Besides, a number of sophisticated genetic algorithm based schemes have also been studied that not only ensures collision-free paths but also improves travel time for recommended paths [5 , 16]. Genetic algorithms [8, 9] have also been employed for deducing optimal/near-optimal by means of user-defined scenarios. Some such GA-Fuzzy schemes [11] demonstrated inconclusive results. Previously researchers have used traditional methods like a potential field, reinforcement learning etc. But soft computing and evolutionary algorithm [12, 17] based approaches have been more popular among the researchers due to their optimality in nature.

Considering motion planning problem, robots may encounter coordination problems caused by moving robots that may pose as obstacles for some others. While smooth coordination between human beings is still a challenging issue till date, development of fruitful coordination between two non-living things is surely a herculean task. A number of researchers attempted to solve the coordination problem [4 , 16]. At the time of navigation process, lots of events may occur. Figure 1 depicts a sequence diagram for a multi-robot motion planning, each robot marked as an agent that all the agents want to achieve the same objective. A particular agent senses and receives signal to get the other agents’ information depending upon the environment. As multiple agents perform a common objective with the same velocity, so they may collide with each other. These activities have also been depicted in Fig. 1. To avoid collisions, different strategies need to be followed by the agents. Different rule sets had been compiled for varying the number of movable obstacles, generally as offline schemes. However, schemes that could be used by online robots, irrespective of the number of robots had been tried by some data-driven learning algorithms [7 , 15] by means of FLCs.

Fig. 1

Sequence diagram depicting common navigation steps for different robots (agents).

In this paper coordination based navigation of three different motion planning approaches have been developed. In the first developed approach PFM based navigation has been applied. On the second approach, a Mamdani-type FLC with manually designed rules is made. Whereas in Approach 3, a GA evolved FLC is considered. Since competition between agents is not good, so a strategic approach has developed to solve the coordination problem among agents. A hundred numbers of scenarios have been taken to compare the performance between coordination and non-coordination schemes. It has experimented that coordination technique is more acceptable than non-coordination approaches concerning coordinated multi-robot navigation.

2 An overview of the Multi-Robot navigation

This problem is worked out to obtain the next step for a particular robot from its present location in the environment avoiding collisions with other robots [8, 9]. The contemplated ideology and hypothesis are discussed below.

2.1 Postulations

Starting and Goal location of all the robots are known in the environment.

For a time-step, a particular robot can perform any action within its motion plan.

All navigating robots perform their individual action until they reach in their individual target positions by taking some time-steps.

The ensuing principles implemented takes care of the aforesaid viewpoints.

Robots are heading towards the goal.

To avoid collision with the other robots, they might not move along the goal directions. They might need to take a turn either left or right. This angular deviation is calculated using Eqn No. (8).

Let us consider that the starting position of the n^throbot at time “t” is $(x_{n}^{init}$ , $(y_{n}^{init}$ ) and the future location of that robot at time t + Δt is ( $(x_{n}^{next}$ , $(y_{n}^{next}$ ). If $(v_{n}^{init}$ is the initial velocity of the n-th robot and ( $(x_{n}^{goal}$ , $(y_{n}^{goal}$ ) is the goal location, next position ( $(x_{n}^{next}$ , $(y_{n}^{next}$ ) of the robot can be obtained following Fig. 2 as: $x_{n}^{next} = x_{n}^{init} + (v_{n}^{init} \times Δ t) \cos θ_{n}$ (1) $y_{n}^{next} = y_{n}^{init} + (v_{n}^{init} \times Δ t) sin θ_{n}$ (2)

Fig. 2

Future and present position of the nth robot.

Initially, the robot (Robot 1) starts its journey from the location ( $x_{n}^{init}$ , $y_{n}^{init}$ ) and updates its position to ( $x_{n}^{next}$ , $y_{n}^{next}$ ), then from ( $x_{n}^{next}$ , $y_{n}^{next}$ ) to ( $x_{n}^{goal}$ , $y_{n}^{goal}$ ) without collision with other robots in number of steps as depicted in Fig. 3 such that distance from its present location to destination by forming constraint is minimized. Thereafter, trajectory distance for rth robot is derived. $\begin{matrix} F 1 = \sum_{n = 1}^{r} {\sqrt{((x_{n}^{init} - x_{n}^{next})^{2} + (y_{n}^{init} - y_{n}^{next})^{2}}) \\ + \sqrt{((x_{n}^{next} - x_{n}^{goal})^{2} + (y_{n}^{next} - y_{n}^{goal})^{2}})} \end{matrix}$ (3)

Fig. 3

Navigation of three robots to identify the critical robot.

By putting the value of $x_{n}^{next}$ and $y_{n}^{next}$ from equations 1 and 2 into equation number 3, F₁ will be $F 1 = \sum_{n = 1}^{r} {v_{n}^{init} + \sqrt{\begin{matrix} (x_{n}^{init} + v_{n}^{init} \cos θ_{n} - x_{n}^{goal})^{2} \\ + (y_{n}^{init} + v_{n}^{init} sin θ_{n} - y_{n}^{goal})^{2} \end{matrix}}}$ (4)

Potential field method (PFM) is one of the computationally efficient methods for solving motion planning problems. Functions of attractive and repulsive potentials are considered as follows. $Fatt (X) = ξ att \times dgoal (X)$ (5) $Frep (X) = ξ rep \times \frac{[1 / dobs (X) - 1 / dobs (0)]}{dobs (X) \times dobs (X)}$ (6)

Here, all the notations are seldom defined following [8, 10]. The resultant force is then obtained as follows: $Fres (X) = \sqrt{\begin{matrix} {Fatt}^{2} (X) \\ + {Frep}^{2} (X) - 2 \times Fatt (X) \\ \times Frep (X) \times cos (φ (r)) \end{matrix}}$ (7)

In order to avoid collisions, a planning robot should deviate by an angle, which is determined using the Equation 8. $α {(r) = \tan}^{- 1} {\frac{(- Frep \times \sin (φ (r)))}{Fatt + Frep \times \cos (φ (r))}}$ (8) where, α= Deviation due to avoiding obstacles; φ= Critical angle due to the critical robot and r = number of robots.

Finally, the objective function, the traveling time (T) has been computed. $T = \sum_{n = 1}^{r} \begin{matrix} (t + Δ t) \\ + (\sqrt{\begin{matrix} {(x_{n}^{final} - x_{n}^{goal}) \\ + (y_{n}^{final} - y_{n}^{goal})} \end{matrix}} / v_{init}) \end{matrix}$ (9)

Where ( $x_{n}^{final}$ , $y_{n}^{final}$ ) is the final position of the robot.

3 Intelligent navigation strategies for coordinated Robots

Myriad strategies for navigation of multi-robots have been developed over the last few decades. However, this paper envisions a novel way for incorporating coordination by defining instants for coordination and unique ways for including the same. Collision avoidance amongst each other forms a core part of all such strategies.

To implement this, Euclidean Distance (ED) is calculated amongst a path tracing robot and its nearby counterpart. Assuming a multi-robot system with 4 robots navigating with robot 1 posing as the most critical to robot 2 and vice versa at any instant, under such circumstances, movements of both robots shall be planned individually [4 , 8]. Therefore, there may be two incidents. In the first incident, they might avoid the collisions between them by taking the deviation. In another incident, none of them decides who will take the deviation to avoid the collision. This can be addressed with the general notion of cooperation having the following three variations.

Variation 1: No robot will alter its planned path and that robot shall treat the path as per the planner (V1).

Variation 2: For Both the robots will change their planned motion, with decelerations and new path planning decisions (V2).

Variation 3: One will sacrifice its motion but the other will not. Regarding cooperation case, the deviation has been considered as a parameter. The robot with larger amount of deviation angle will be called as cooperative and the other will be non-cooperative (V3).

To solve the coordination problem [8 , 16] different strategies have been developed by using the above mentioned three possible concepts. If a particular robot treats another robot as most critical one then nine different strategies may be built based on three different strategies. Proposed strategy matrix has been shown in Table 1.

Table 1
Strategic matrix between planning Robot and critical Robot

Planning Critical robot

Robot V1 V2 V3

V1 (V1, V1) (V1, V2) (V1, V3)

V2 (V2, V1) (V2, V2) (V2, V3)

V3 (V3, V1) (V3, V2) (V3, V3)

Planning	Critical robot
V1	(V1, V1)	(V1, V2)	(V1, V3)
V2	(V2, V1)	(V2, V2)	(V2, V3)
V3	(V3, V1)	(V3, V2)	(V3, V3)

The agents may avoid a collision and can reach the destination by optimal time using heuristic coordination where deviation has been taken a key constraint to perform coordination. Following pseudo code is presented to show the coordination process between two particular robots.

Algorithm 1 clearly indicates that the robot that takes more deviation is considered to be more cooperative. However, the challenge to identify the coordinated robot is solved and it is depicted by using a use case diagram as shown in Fig. 4. As discussed, traditional as well as nontraditional approaches have already existed for solving the navigation and coordination problem. Figure 4 depicts the use case diagram presenting to motion planning of multiple robots.

Fig. 4

Case diagram depicting motion planning of multiple robots.

Algorithm 1: Pseudo code for coordination process
between two robots
Start
1. Initialize Source and Goal
2. Robot started navigation
3. If critrobo (i)==j & &critrobo(j)==i
4. Cooperationcount = 1; //Initialize the variable
5. If deviation (i)<deviation (j)
6. Cooperative robot = i; // Find the cooperative robot
7. Else
8. Cooperative robot = j;
End

A particular agent starts its motion planning by FLC based motion planner. After that, different activities will be performed by agents those are presented in Fig. 4. The same concept is applicable to other agents too. Thereafter, a combined GA-FLC is applied to the system of robots to optimize travel time.

3.1 Fuzzy logic controller based intelligent navigation

The fuzzy theory has the capability to deal with incomplete uncertain and approximate information [9]. This technique generated additional significance amongst the robotics researchers. In this paper, the inputs, viz. distance and angle and two outputs named deviation and acceleration have been considered. Both the inputs (distance and angle) and outputs (acceleration and deviation) are represented with different linguistic terms as per [11]. The rule base consists of 20 different rules and they are presented in Table 2. The database is considered to be linear in nature.

Table 2
Manually constructed rule base of FLC

Rule No Distance Angle Deviation Acceleration

1 VNR LT AH H

2 VNR AHL AHR H

3 VNR A AHL VH

4 VNR AHR AH H

5 VNR RT AH H

6 NR LT AH L

7 NR AHL AH H

8 NR A RT VH

9 NR AHR AH H

10 NR RT AH L

11 FR LT AH VL

12 FR AHL AH L

13 FR A AHR H

14 FR AHR AH L

15 FR RT AH VL

16 VFR LT AH VH

17 VFR AL AH VH

18 VFR A AH VH

19 VFR AHR AH VH

20 VFR RT AH VH

Rule No	Distance	Angle	Deviation	Acceleration
1	VNR	LT	AH	H
2	VNR	AHL	AHR	H
3	VNR	A	AHL	VH
4	VNR	AHR	AH	H
5	VNR	RT	AH	H
6	NR	LT	AH	L
7	NR	AHL	AH	H
8	NR	A	RT	VH
9	NR	AHR	AH	H
10	NR	RT	AH	L
11	FR	LT	AH	VL
12	FR	AHL	AH	L
13	FR	A	AHR	H
14	FR	AHR	AH	L
15	FR	RT	AH	VL
16	VFR	LT	AH	VH
17	VFR	AL	AH	VH
18	VFR	A	AH	VH
19	VFR	AHR	AH	VH
20	VFR	RT	AH	VH

Deviation and Acceleration are calculated in a step-wise manner as shown below.

Step 1 (Fuzzification): Measured variables are changed to suitable fuzzy set to express uncertainty measurement.

Step 2 (Rule-base Mapping): Using fuzzified inputs, control rules are evaluated through the rule-base and fuzzified output is obtained.

Step 3 (Defuzzification): The crisp value of the output has been generated converting the fuzzified output.

Different defuzzification methods are there. Center of Sum method is used in the present study.

3.2 Automatically tuned GA-fuzzy based intelligent navigation

A GA-based FLC approach has been employed for the better performance of the FLC based technique discussed in Section 3.1. It has experimented that FLC’s performance is mainly dependent on its rule-base. Therefore, the FLC rule base can be, only by using GA and the membership function distribution will remain unchanged. Due to the discrete nature of variables (existence or non-existence of a rule), a binary-coded GA [11] is used at the time of optimization For its long iteration, the computational complexity of GA is more. The offline process is used for FLC optimization.

FLC has been constructed depending on the author’s knowledge base. Occasionally, it is difficult to collect knowledge from the earlier process which is controlled using FLC. To minimize this difficulty, a GA-based approach has been proposed for the manual design of FLC. A binary-coded GA will choose some good fuzzy rules through search from a large rule base which consists of the maximum number of possible rules generated from the Table 2. A 140-bits long GA-string is used to express the knowledge base of the FLC:

$\underset{Data Base}{\underset{︸}{10 . . 1100 . . 0111 . . 11}} \underset{Input Combinations}{\underset{︸}{10 . . 101 . . 011}} \underset{Consequent of rules}{\underset{︸}{10 . . 01 . . 011 . . 0011}}$

Already mentioned above that, Approach 1 has been treated as a data-driven optimization problem [15]. Now the evolution of approaches has been made. Now the problem can be redefined as soft computing based data-driven optimization problem [7 , 15]. All the data pertaining to compute the objective function value mentioned on equation no 11; getting optimizes value. A combined coordination and GA-fuzzy-based motion planning scheme is presented in Fig. 5.

Fig. 5

Activity diagram showing coordination based motion planning scheme.

4 Results and discussions

The efficacy of the designed approach has been experimented through computer simulations to solve different cases of multiple mobile robots. Two different cases with eight and twelve robots navigating in a grid of 40 × 40 m² (400 × 400 dm²) is considered. Some of the important parameters of the robots are mentioned below.

Dimension: Measured Two-wheeled differential drive robot

Maximum Velocity: 4 m/s

Acceleration: 0.005 m/s² to 0.05 m/s²

Time interval (dt): 2 seconds.

d_obs (0) =8m

4.1 GA-parametric study with best rule base identification of FLC

Performances of Approaches 1 and 2 can be compared straight-way. However, Approach 3 should be trained before comparing its performances with the other approaches. For this purpose, an optimal knowledge base of the FLC for Approach 3 is noted. However, some of the parameters of GA are also to be set for better performance of it. Those parameters are to be decided before the task of evolution is given to GA. So, GA parametric study has been carried out systematically. The crossover probability is kept fixed at 0.5. The mutation probability, population size and the maximum number of generations are then systematically varied in the ranges of (0.001 to 0.011), (50 to 150) and (0 to 150), respectively, and optimal values are noted against the best fitness value of GA. The optimal GA-parameters are presented in Table 3 for three different cases. Once, the decision on GA parameters is made, it is used to evolve the knowledge base (database and rule base) of the FLC.

Table 3
Optimal parameters of GA for the three different cases for approach 3

Cases Crossover probability Mutation probability Population size Maximum number of generations

Case 1 (Involves 8 robots) 0.5 0.009 90 90

Case 2 (Involves 12 robots) 0.011 70 100

Case 3 (Involves 16 robots) 0.011 70 130

Case 3 (Involves 20 robots) 0.010 70 120

Cases	Crossover probability	Mutation probability	Population size	Maximum number of generations
Case 1 (Involves 8 robots)	0.5	0.009	90	90
Case 2 (Involves 12 robots)		0.011	70	100
Case 3 (Involves 16 robots)		0.011	70	130
Case 3 (Involves 20 robots)		0.010	70	120

4.2 Motion planning of the different number of robots

One hundred different scenarios have been considered and traveling time of each robot is calculated. Average traveling time for all the scenarios is presented in Table 4. R1 to R20 are representing Robots 1 to 20.

Conventional PFM when executed, where the attractive potential is increasing which is made by the goal of the same robot as well as repulsive potential also rising by all the other navigating robots and is not suitable for large number of robots. It is to be replaced by other techniques such as FLC based motion planner.

Cooperation scheme has also been deployed and deviation constraint has been taken as an archetype to implement cooperation scheme. With the incorporation of this, one robot may take more time to reach goal having better cooperation score. To get the optimal result from FLC, the FLC has been tuned by Genetic Algorithm. After successful tuning, the average traveling time has been recorded higher for non-cooperation than cooperation technique. So the overall scenario is like that all approaches have given optimal average traveling time for cooperation issue. It highly demands the cooperation between multiple mobile robots. It may be interesting that in the case of non-optimal FLC, cooperation technique performs well. Standard deviation as presented in Table 4 also shows the efficacy of the simulation results. Previously it has been shown that authors have made the rule base manually for FLC.

Table 4
Average travel time in seconds of the robots for different approaches and cooperation

8-Robots Case 12-Robots Case 8-Robots Case 12-Robots Case

App1 App2 App3 App1 App2 App3 App1 App2 App3 App1 App2 App3

Robots NC FC NC FC NC FC NC FC NC FC NC FC CC CC CC CC CC CC

R1 59.77 59.38 62.05 61.68 61.59 61.32 58.27 56.58 67.79 64.62 63.63 61.57 12 13 12 13 13 14

R2 68.48 68.45 71.68 71.68 70.00 69.69 68.49 68.46 76.74 75.34 71.14 70.17 6 5 12 9 10 24

R3 62.54 61.72 64.96 64.18 64.14 63.83 60.47 58.07 70.33 67.65 65.53 64.08 6 2 13 11 7 14

R4 54.36 53.94 55.76 55.34 55.88 55.77 53.91 52.52 64.25 61.16 57.94 56.06 7 7 11 10 10 18

R5 103.30 102.86 104.87 104.43 105.31 104.86 101.97 101.92 106.92 106.10 106.61 105.21 11 14 23 16 18 29

R6 82.55 82.44 84.69 84.60 84.16 83.98 82.66 82.14 89.42 87.76 85.99 84.29 7 5 20 9 8 17

R7 115.02 114.91 115.99 115.89 116.34 116.12 114.68 114.23 116.11 115.54 117.96 116.39 7 7 17 12 10 19

R8 82.34 82.21 84.99 84.86 84.06 83.54 82.36 82.15 90.20 88.67 85.57 83.83 18 17 29 18 19 37

R9 53.86 54.29 61.37 60.56 56.10 54.37 8 5 11

R10 43.05 43.55 52.18 51.22 44.74 43.17 8 4 15

R11 57.22 54.62 65.42 62.45 63.34 61.29 8 8 25

R12 51.72 51.72 63.64 60.96 54.73 52.90 10 9 12

Avg. 78.55 78.24 80.62 80.33 80.18 79.89 69.06 68.35 77.03 75.17 72.77 71.11

S.D. 21.61 21.70 21.26 21.35 21.60 21.56 21.93 22.12 19.58 20.09 22.07 22.16

16-Robots Case 20-Robots Case 16-Robots Case 20-Robots Case

App1 App2 App3 App1 App2 App3 App1 App2 App3 App1 App2 App3

Robots NC FC NC FC NC FC NC FC NC FC NC FC CC CC CC CC CC CC

R1 64.83 64.46 62.79 62.22 61.77 61.16 63.62 63.44 66.24 61.65 66.97 62.95 10 14 15 10 22 15

R2 75.13 74.33 73.88 73.28 72.41 72.15 73.87 72.87 78.55 74.84 76.67 72.13 13 27 23 15 42 13

R3 65.54 63.87 64.51 63.91 63.39 63.21 65.17 64.86 70.23 68.90 69.94 66.06 11 23 16 12 31 11

R4 58.87 58.59 57.69 57.05 56.40 56.82 60.02 59.80 64.86 59.24 63.05 57.48 12 22 18 15 28 17

R5 106.19 106.11 105.64 105.90 105.57 105.50 105.96 105.22 112.89 108.50 110.56 106.93 14 42 14 18 56 21

R6 86.52 85.38 84.63 85.17 84.44 84.08 86.26 85.50 90.93 88.65 88.86 85.54 14 37 38 18 47 24

R7 115.34 114.36 116.86 117.37 116.65 115.29 115.90 115.23 123.51 120.83 121.96 118.01 13 28 32 16 38 22

R8 86.22 85.82 85.24 84.80 83.94 82.72 86.39 85.21 90.34 87.99 89.26 85.26 18 32 24 22 42 26

R9 59.70 60.34 58.37 57.94 56.94 55.29 60.09 59.71 61.16 58.24 59.79 56.05 13 30 28 16 39 27

R10 48.62 48.67 47.39 46.68 45.26 45.47 49.41 48.43 51.02 47.25 47.53 44.49 4 14 16 6 14 15

R11 62.57 62.55 62.08 62.15 61.88 61.06 62.79 62.17 72.31 67.13 69.22 63.37 10 23 24 14 29 19

R12 57.47 57.17 55.77 55.12 54.44 54.24 58.45 58.25 63.05 58.59 59.02 54.43 12 23 25 14 27 24

R13 62.66 62.47 61.35 60.85 59.25 59.05 63.19 62.51 69.98 63.89 66.13 61.03 18 32 22 21 36 27

R14 62.66 62.70 61.87 61.17 60.76 60.26 61.75 61.32 63.74 59.46 60.65 57.68 5 16 12 7 21 18

R15 85.38 85.48 84.57 84.82 84.19 84.13 86.97 86.15 92.87 87.00 88.33 84.93 6 31 25 8 35 26

R16 63.88 63.77 63.61 63.55 63.47 63.12 64.89 64.42 72.72 68.98 68.21 64.70 12 21 18 16 25 17

R17 86.86 86.07 90.66 87.38 87.67 84.93 6 29 14

R18 60.97 60.51 65.58 61.87 63.20 58.24 15 24 13

R19 93.04 91.79 96.69 92.39 93.87 90.87 16 34 20

R20 65.81 64.33 66.11 62.77 63.37 60.19 13 23 28

Avg. 72.59 72.25 71.64 71.37 70.67 70.22 73.57 72.89 78.17 74.28 75.71 71.76

S.D. 17.93 17.76 18.41 18.74 18.83 18.67 17.63 17.50 18.59 18.82 18.72 18.93

	8-Robots Case	12-Robots Case	8-Robots Case	12-Robots Case
R1	59.77	59.38	62.05	61.68	61.59	61.32	58.27	56.58	67.79	64.62	63.63	61.57	12	13	12	13	13	14
R2	68.48	68.45	71.68	71.68	70.00	69.69	68.49	68.46	76.74	75.34	71.14	70.17	6	5	12	9	10	24
R3	62.54	61.72	64.96	64.18	64.14	63.83	60.47	58.07	70.33	67.65	65.53	64.08	6	2	13	11	7	14
R4	54.36	53.94	55.76	55.34	55.88	55.77	53.91	52.52	64.25	61.16	57.94	56.06	7	7	11	10	10	18
R5	103.30	102.86	104.87	104.43	105.31	104.86	101.97	101.92	106.92	106.10	106.61	105.21	11	14	23	16	18	29
R6	82.55	82.44	84.69	84.60	84.16	83.98	82.66	82.14	89.42	87.76	85.99	84.29	7	5	20	9	8	17
R7	115.02	114.91	115.99	115.89	116.34	116.12	114.68	114.23	116.11	115.54	117.96	116.39	7	7	17	12	10	19
R8	82.34	82.21	84.99	84.86	84.06	83.54	82.36	82.15	90.20	88.67	85.57	83.83	18	17	29	18	19	37
R9							53.86	54.29	61.37	60.56	56.10	54.37				8	5	11
R10							43.05	43.55	52.18	51.22	44.74	43.17				8	4	15
R11							57.22	54.62	65.42	62.45	63.34	61.29				8	8	25
R12							51.72	51.72	63.64	60.96	54.73	52.90				10	9	12
Avg.	78.55	78.24	80.62	80.33	80.18	79.89	69.06	68.35	77.03	75.17	72.77	71.11
S.D.	21.61	21.70	21.26	21.35	21.60	21.56	21.93	22.12	19.58	20.09	22.07	22.16
	16-Robots Case	20-Robots Case	16-Robots Case	20-Robots Case
	App1	App2	App3	App1	App2	App3	App1	App2	App3	App1	App2	App3
Robots	NC	FC	NC	FC	NC	FC	NC	FC	NC	FC	NC	FC	CC	CC	CC	CC	CC	CC
R1	64.83	64.46	62.79	62.22	61.77	61.16	63.62	63.44	66.24	61.65	66.97	62.95	10	14	15	10	22	15
R2	75.13	74.33	73.88	73.28	72.41	72.15	73.87	72.87	78.55	74.84	76.67	72.13	13	27	23	15	42	13
R3	65.54	63.87	64.51	63.91	63.39	63.21	65.17	64.86	70.23	68.90	69.94	66.06	11	23	16	12	31	11
R4	58.87	58.59	57.69	57.05	56.40	56.82	60.02	59.80	64.86	59.24	63.05	57.48	12	22	18	15	28	17
R5	106.19	106.11	105.64	105.90	105.57	105.50	105.96	105.22	112.89	108.50	110.56	106.93	14	42	14	18	56	21
R6	86.52	85.38	84.63	85.17	84.44	84.08	86.26	85.50	90.93	88.65	88.86	85.54	14	37	38	18	47	24
R7	115.34	114.36	116.86	117.37	116.65	115.29	115.90	115.23	123.51	120.83	121.96	118.01	13	28	32	16	38	22
R8	86.22	85.82	85.24	84.80	83.94	82.72	86.39	85.21	90.34	87.99	89.26	85.26	18	32	24	22	42	26
R9	59.70	60.34	58.37	57.94	56.94	55.29	60.09	59.71	61.16	58.24	59.79	56.05	13	30	28	16	39	27
R10	48.62	48.67	47.39	46.68	45.26	45.47	49.41	48.43	51.02	47.25	47.53	44.49	4	14	16	6	14	15
R11	62.57	62.55	62.08	62.15	61.88	61.06	62.79	62.17	72.31	67.13	69.22	63.37	10	23	24	14	29	19
R12	57.47	57.17	55.77	55.12	54.44	54.24	58.45	58.25	63.05	58.59	59.02	54.43	12	23	25	14	27	24
R13	62.66	62.47	61.35	60.85	59.25	59.05	63.19	62.51	69.98	63.89	66.13	61.03	18	32	22	21	36	27
R14	62.66	62.70	61.87	61.17	60.76	60.26	61.75	61.32	63.74	59.46	60.65	57.68	5	16	12	7	21	18
R15	85.38	85.48	84.57	84.82	84.19	84.13	86.97	86.15	92.87	87.00	88.33	84.93	6	31	25	8	35	26
R16	63.88	63.77	63.61	63.55	63.47	63.12	64.89	64.42	72.72	68.98	68.21	64.70	12	21	18	16	25	17
R17							86.86	86.07	90.66	87.38	87.67	84.93				6	29	14
R18							60.97	60.51	65.58	61.87	63.20	58.24				15	24	13
R19							93.04	91.79	96.69	92.39	93.87	90.87				16	34	20
R20							65.81	64.33	66.11	62.77	63.37	60.19				13	23	28
Avg.	72.59	72.25	71.64	71.37	70.67	70.22	73.57	72.89	78.17	74.28	75.71	71.76
S.D.	17.93	17.76	18.41	18.74	18.83	18.67	17.63	17.50	18.59	18.82	18.72	18.93

Abbreviations: NC: No Cooperation; FC: Full Cooperation; CC: Cooperation Count; App1: Approach 1, App2: Approach 2, App3: Approach 3.

It has been observed that cooperation scheme has been fired many a times and we also have counted this. For example, it has been recorded that Robot 1 to Robot 8 has been cooperated in 16, 6, 7,8,11,14,7 and 19 scenarios, respectively out of hundred number of different scenarios (refer to Table 4). High number of cooperation count indicates the requirement of this strategy. Finally, the movement of all the robots for a particular scenario of different approaches has been presented in Fig. 6. All the scenarios are not cooperation oriented but maximum scenarios tend to cooperation. Out of all hundred scenarios, one best scenario has been taken as a best cooperative scenario where robots show their maximum cooperation. Step-by-step movements of robots for that best scenario have been presented.

Fig. 6

Navigation of eight, twelve, sixteen and twenty robots using different approaches.

5 Conclusion

Coordinated navigation of multiple mobile robots is demonstrated using three techniques. Coordination schemes have been implemented with acceleration/ deceleration and deviations of robots upon tracing impending collisions with other robots. From the results of simulations conducted, it can be observed that the performance of FLC based approach deteriorates with increasing number of robots, but without significant changes in average traveling time. Here, we could successfully implement the cooperation scheme in compared to the existing methods in the literature. The fuzzy logic rule base has been tuned by GA and average traveling time has been improved. GA parametric study has been carried out for four robots and the optimal values have been used for eight, twelve, sixteen and twenty number of robots cases. In the case of all developed approaches, hundred scenarios have been considered to show the performance of the developed algorithm, though only one scenario has been presented for all cases. Computational complexity has also been measured for all types of robots here. Development of game theory-based coordination strategy is also there in the authors’ mind.

References

Bayindir

, A review of swarm robotics tasks, Neurocomputing172 (2106), 292–321.

, Ramezan Shirazi

Sun

and Jin

Y.,

Bio-inspired self-organizing multi-robot pattern formation: A review, Robot. Auton. Syst.91 (2017), 83–100.

Brambilla

, Ferrante

, Birattari

and Dorigo

, Swarm robotics: A review from the swarm engineering perspective, Swarm Intell.7(1) (2013), 1–41.

Hui

N.B.

Coordinated motion planning of multiple mobile robots using potential field method, International Conference on Industrial Electronics, Control and Robotics (IECR 2010), NIT Rourkela, India, Dec. 27–29, 2010.

Khatib

M.A.

and Saade

J.J.

, An efficient data-driven fuzzy approach to the motion planning problem of a mobile robot, Fuzzy Sets and Systems134(1) (2003), 65–82.

Shirazi

A.R.

and Jin

, A Strategy for Self-Organized Coordinated Motion of a Swarm of Minimalist Robots, in, IEEE Transactions on Emerging Topics in Computational Intelligence1(5) (2017), 326–338.

Watabe

and Kawaoka

, Automatic learning of Action Knowledge-Base for a mobile robot using genetic algorithms, Journal of Intelligent and Fuzzy Systems15(3,4) (2004), 219–223.

Elhoseny

, Shehab

and Yuan

, Optimizing robot path in dynamic environments using genetic algorithm and bezier curve, Journal of Intelligent and Fuzzy Systems33(4) (2017), 2305–2316.

Pradhan,

Sinha

Roy D

and Hui,

N.B

Motion planning and coordination of multi-agent systems, International Journal of Computational Vision and Robotics8(5) (2018), 492–508.

10.

Das

P.K.

, Behera

H.S.

and Panigrahi

B.K.

, A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning, In Swarm and Evolutionary Computation28 (2016), 14–28.

11.

Hui

N.B.

, Mahendar

and Pratihar

D.K.

, Time-optimal collision-free navigation of a car-like robot using a neuro-fuzzy approach, Fuzzy Sets and Systems157(16) (2006), 2171–2204.

12.

Jin

, Surrogate-assisted evolutionary computation: recent advances and future challenges, Swarm and Evolutionary Computation1(2) (2011), 61–70.

13.

Philip

, Givigi

S.N.

Jr. and Schwartz

H.M.

, Cooperative ngation of unknown environments using potential games, International Journal of Mechatronics and Automation (IJMA), Inderscience4(3) (2014), 173–187.

14.

Xu,

X.Z.

Gao,

Gao-liang

Peng,

Kai

Xue

and Yulin

Ma,

Prototype optimization of reconfigurable mobile robots based on a modified Harmony Search method, Transactions of the Institute of Measurement and Control34(2–3) (2010), 334–360.

15.

Cheng

, Jin

, Narukawa

and Sendhoff

, A multi-objective evolutionary algorithm using Gaussian process based inverse modeling, IEEE Transactions on Evolutionary Computation19(6) (2015), 838–856.

16.

Wang

, Jin

and Jansen

J.O.

, Data-driven surrogate-assisted multi objective evolutionary optimization of a trauma system, In IEEE Transactions on Evolutionary Computation20(6) (2016), 939–952.

17.

Pradhan

, Sinha Roy

Hui

N.B.

Multi-Agent Navigation and Coordination using GA-Fuzzy Approach, Soft Computing for Problem Solving, Advances in Intelligent Systems and Computing, 2019, pp. 793–805.

Planning	Critical robot
Robot	V1	V2	V3
V1	(V1, V1)	(V1, V2)	(V1, V3)
V2	(V2, V1)	(V2, V2)	(V2, V3)
V3	(V3, V1)	(V3, V2)	(V3, V3)

Intelligent navigation of multiple coordinated robots

Abstract

Keywords

1 Introduction

2.1 Postulations

Table 1 Strategic matrix between planning Robot and critical Robot Planning Critical robot Robot V1 V2 V3 V1 (V1, V1) (V1, V2) (V1, V3) V2 (V2, V1) (V2, V2) (V2, V3) V3 (V3, V1) (V3, V2) (V3, V3)

4.1 GA-parametric study with best rule base identification of FLC

References

Table 1
Strategic matrix between planning Robot and critical Robot

Planning Critical robot

Robot V1 V2 V3

V1 (V1, V1) (V1, V2) (V1, V3)

V2 (V2, V1) (V2, V2) (V2, V3)

V3 (V3, V1) (V3, V2) (V3, V3)