Path planning for the autonomous robots using modified grey wolf optimization approach

Abstract

Path planning for robots plays a vital role to seek the most feasible path due to power requirement, environmental factors and other limitations. The path planning for the autonomous robots is tedious task as the robot needs to locate a suitable path to move between the source and destination points with multifaceted nature. In this paper, we introduced a new technique named modified grey wolf optimization (MGWO) algorithm to solve the path planning problem for multi-robots. MGWO is modified version of conventional grey wolf optimization (GWO) that belongs to the category of metaheuristic algorithms. This has gained wide popularity for an optimization of different parameters in the discrete search space to solve various problems. The prime goal of the proposed methodology is to determine the optimal path while maintaining a sufficient distance from other objects and moving robots. In MGWO method, omega wolves are treated equally as those of delta wolves in exploration process that helps in escalating the convergence speed and minimizing the execution time. The simulation results show that MGWO gives satisfactory performance than other state of art methods for path planning of multiple mobile robots. The performance of the proposed method is compared with the standard evolutionary algorithms viz., Particle Swarm Optimization (PSO), Intelligent BAT Algorithm (IBA), Grey Wolf Optimization (GWO), and Variable Weight Grey Wolf Optimization (VW-GWO) and yielded better results than all of these.

Keywords

Meta-heuristic particle swarm optimization intelligent BAT algorithm grey wolf optimization (GWO)modified grey wolf optimization (MGWO)variable weight grey wolf optimization (VW-GWO)

1 Introduction

In modern era, an intelligent machine plays a pivotal role in human life to perform various activities in dynamic environments. Among them, usages of autonomous mobile robots have been considered critical. These robots are used in various applications and thereby assist human life for accomplishing various tasks such as automated transportation, computer aided diagnosis, home maintenance, and surveillance in defense etc. [1, 2]. The initial job of mobile robots is to directly fetch information from their surroundings without any human involvement.

Path planning for autonomous mobile robots deals with construction of a feasible trajectory in such a way that all the robots can have the collision free path to reach the destination point. There are two categories of path planning algorithms; one is known as centralized and other as decentralized. In centralized planning techniques, all the individual robots construct the complex environment to find the optimal path [3]. In this, path planning algorithm is used to compute robot’s constraints and their objective functions while in case of decentralized approach, personal configuration space is assigned to each and every robot for path planning [4 –6].

Robots have the potential to deal with the complex situations and harsh environment, where it’s hard for humans to work. To move on to the path from starting point to target point, it needs either 2D or 3D workspace [3]. In general, path is defined as a collection of organized points located in contiguous framework [5]. The essential steps which are required for the proper path or route planning are given as follows [7]:

First step: In the first step, we need to define the workspace and carry out categorization among its vacant area and occupied area. Here, workspace includes different points linked to each other in the grid map.

Second step: In second step, we need to organize correlated points from the source to the destination beyond any dissension points in the specified route. Any suitable deterministic or non-deterministic algorithm could be employed for this purpose.

Final step: In the final step, an efficient and feasible track is created from the defined route that deemed fit for real time execution of the robots.

Over the past twenty years, numbers of conventional and evolutionary methods have been introduced by different eminent researchers for developing path planning models for autonomous mobile robots. In this context, several deterministic, heuristic, and meta-heuristic algorithms have been developed by researchers over the years [8]. For instance, Gigras et al. [9] proposed the artificial bee colony (ABC) optimization technique for the route planning problem and compared their results against PSO algorithm in terms of convergence rate, demonstrating the superiority of ABC algorithm over PSO. On applying the ABC optimization technique, the significant improvement was observed in convergence rate with increase in population size. Another advantage of ABC algorithm is that it uses the less number of control parameters as compared to PSO. However, the developed method has poor accuracy and convergence speed, while applying for high dimensional and complex problems such as clustering, job scheduling, mining etc., which requires highly, optimized solutions.

Dewangan et al. [10] utilized GWO algorithm to solve the three dimensional path planning problem of unmanned aerial vehicles (UAVs) and obtained the feasible trajectory between source and target points. The GWO algorithm outperformed over the other deterministic algorithms such as Dijkstra, A*, D*, and metaheuristic algorithms such as biogeography based optimization (BBO), particle swarm optimization (PSO), glowworm swarm optimization (GSO), and sine cosine algorithm (SCA) in terms of path calculation and convergence rate. However, the major limitation of GWO algorithm for three dimensional path planning problem is that it can have the sharp turn in the retrieved path that might create a problem for UAV’s during navigation.

Khandelwal et al. [11] proposed modified grey wolf optimization (MGWO) technique to solve the transmission network expansion planning (TNEP) problem for six bus Graver’s system as well as for Brazilian 46-bus system. The TNEP problem is considered complex, large scale, and non-linear mixed integer problem. The performance of the proposed algorithms was evaluated using twenty standard benchmark functions and achieved excellent results in terms of success rate (SR), average number of function evaluations (AFE), mean error (ME), and standard deviation (SD) over other meta-heuristic algorithms. The authors also illustrated the utilization of MGWO to solve the multimodal and non separable complex optimization problems. The developed algorithm achieved the satisfactory results in comparison to the other nature inspired algorithms such as GWO, PSO, ABC, and differential evolution (DE).

Similarly, Gupta et al. [12] presented an improved version of GWO algorithm (I-GWO) with opposition based learning and chaotic local search for integer and mixed integer optimization problems. They adopted opposition based learning to accelerate the convergence rate, while maintaining the balance between exploration and exploitation using the chaotic local search. They achieved satisfactory results for optimization problems for mixed integers with the proposed algorithm.

One more powerful algorithm named variable weight grey wolf optimization (VW-GWO) was recently proposed by Kumar et al. [13] in order to obtain an optimal solution for path planning problem of mobile robots. In this study, variable weights were assigned to α, β, and δ wolves according to their respective positions from the prey. The authors argue that α wolves being nearest to the prey should be given higher weights compared to β, and δ wolves initially. This method was initially proposed by Gao et al. [14] in year 2019 claiming its superiority over original GWO method based on twenty standard benchmark functions.

Another improved variant of GWO was suggested by Ge et al. [15] that dealt with the unmanned aerial vehicles (UAV) path planning issues for oilfield inspection. In this paper, authors developed grey wolf fruit fly optimization (GWFOA) algorithm by integrating fruitfly optimization (FOA) and GWO. Basic GWO algorithm provides weak optimal solutions for oilfield path planning problems due to random generations of new solutions. To resolve this problem, authors integrated fruit fly optimization algorithm with GWO that enhanced the capability of GWO algorithm and enabled it to get the satisfactory solutions in the complex environment [15].

Apart from GWO based algorithms [16 –25], the researchers have also used other nature inspired algorithms such as particle swarm optimization (PSO) [26 –30], and Intelligent BAT algorithm (IBA) [31 –33] for yielding an effective optimized solution for path planning, unit commitment, and optimal reactive power dispatch problems. However, GWO and its variants [34 –43] have been proven more useful for solving such problems.

Patle et al. [44] presented the exhaustive study of large number of mobile robots navigation methods used so far. They reviewed traditional and reactive approaches in their paper to present the development of route planning techniques and identified various research gaps therein. In their study, they found reactive approaches more promising than traditional methods for topographical surfaces. According to their study, the reactive approaches can also be used to improve the performance of the conventional algorithms while used as hybrid algorithms.

Some traditional methods such as Grid method [45], neural network [46], fuzzy method [7, 47], evolutionary algorithms [48], probabilistic road maps [16], randomly exploring algorithms [6], visibility graphs, and Dijkstra deterministic search [8] have also been successfully applied for solving real world optimization problems. However, these conventional approaches offer some limitations in terms of slow convergence speed and low accuracy [18]. Traditional approaches based system need more computational time to obtain optimal solutions due to incomplete information about the environment [39]. To address this issue, classical approaches can be combined with the evolutionary algorithms such as PSO, IBA, and GWO. Most of the evolutionary algorithms have the capability not to trap into local optima, and also enlarge the range of random search. Though, this additional feature of evolutionary algorithms is obtained at an extra computational cost, especially when the search space is very irregular. As we know that the search space for robot path planning problem is very irregular. Hence, it is difficult to get global optimal solution for path planning task. In this study, we adopted a new method known as MGWO to address the aforementioned problem. The adopted MGWO algorithm is based on Grey wolf optimizer and includes omega wolves in searching and hunting process along with the alpha, beta and delta wolves. Due to the involvement of omega wolves along with alpha, beta and delta wolves, the MGWO algorithm converge much faster and take less processing time to find the suitable path trajectory for mobile robots. Sometimes the non-involvement of omega wolves in GWO algorithm poses a limitation on the exploration phase and puts a constraint on convergence speed resulting into stagnation of initial population into local minima during search process while MGWO has minimal chances of getting stuck into local optima.

The key points of swarm based algorithms are to generate most favorable paths in a typical workspace in comparison to that of conventional deterministic methods [18]. These techniques are robust as well as efficient and also offer good solutions for different applications [19]. High computational cost is still of prime concern that could be reduced further using either hybrid meta-heuristic algorithms or their modified versions [20]. Therefore, in this study, the enhanced version of GWO called MGWO is introduced to make a 2D path planning strategy for multiple robots that tend to give more satisfactory performance in comparison to other recent studies based on meta-heuristic algorithms for this specific application. The proposed algorithm shows the faster convergence towards the global solution while avoiding the problem of local optima.

Table 1 presents scope, advantages and limitations of various current states of art methods available in the literature. This also presents the key points of the algorithms, depicting the similarities and differences among GWO variants and other considered algorithms.

Table 1
Summary of scope, advantages and limitations of current state of art methods including GWO and its variants over last three years

Algorithm Scope and advantages Limitations Key points of algorithms^** (Similarities &differences)

TLBO-ANFIS [49] # Used for finding optimal trajectory for mobile robot navigation system. # Achieved optimal path trajectory. # Minimize the travelling time of mobile robot. # Difficult to design membership functions for complex map structures containing closer objects. # It works based on TLBO and ANFIS approach.

# TLBO does not demand the parameter adjustment.

# Avoid stagnation of ANFIS into local minima.

FF-CPSO [50] # Employed for path planning of mobile robots. # Does not perform well in case of sharp turn of robots. # This method work based on the fusion of firefly optimization (FF) algorithm &Chaotic particle swarm optimization (CPSO).

# Able to find shortest path in comparison to FF &CPSO algorithms. # Need additional power for coverage of tilted path.

GWO [10] # Applied to solve three dimensional path planning problem of Unmanned aerial vehicles (UAVs). # May go out of the boundaries easily due to generation of new random solutions. # The alpha, and beta wolves participate actively in exploration and exploitation process. # Optimization process begins with random solutions in the form of initial populations.

# Capable to maintain the right balance between exploration and exploitation process. # Exhibit probability of getting trapped into local optima.

# Uses fewer number of control parameters. # Can have the sharp turn in the retrieved path, causing a problem for UAVs

VW-GWO [13] # Useful for high dimensional optimization problems. # Not optimized on all standard benchmark functions. # Variable weights are assigned to each category of wolves.

# Gives the low residual errors. # GWO is used as a baseline model.

I-GWO [12] # Used for Integer and mixed integer optimization problems. # Achieve faster convergence rate due to usage of opposition based learning. # Possess better search efficiency. # Not suitable for solving complex problems. # Convergence rate depends upon the degree of complexity of a particular problem. # Integrate opposition based learning (IOL) and chaotic local search (CLS) with GWO to solve integer and mixed integer optimization problems.

# IOL escalates the convergence speed while CLS balance the searching and hunting processes.

GW-FOA [15] # Suitable for local search problems. # Not able to attain global optima therefore may not be well suited for wheeled or legged robots. # Used fruit fly optimization algorithm (FOA).

# Provides faster convergence rate and strong local search ability. # Used GWO as a base line model in integration with FOA.

MGWO [11] # Applied to solve TNEP problem. # Convergence faster due to involvement of omega wolves in exploration &exploitation processes. # Needs further escalation of the exploitation and hunting process to obtain better optimization solutions # Promotes the involvement of omega wolves in position updation during exploration phase.

# Enhances the exploration speed thereby.

# Minimize the computational cost.

Algorithm	Scope and advantages	Limitations	Key points of algorithms^** (Similarities &differences)
TLBO-ANFIS [49]	# Used for finding optimal trajectory for mobile robot navigation system. # Achieved optimal path trajectory. # Minimize the travelling time of mobile robot.	# Difficult to design membership functions for complex map structures containing closer objects.	# It works based on TLBO and ANFIS approach.
			# TLBO does not demand the parameter adjustment.
			# Avoid stagnation of ANFIS into local minima.
FF-CPSO [50]	# Employed for path planning of mobile robots.	# Does not perform well in case of sharp turn of robots.	# This method work based on the fusion of firefly optimization (FF) algorithm &Chaotic particle swarm optimization (CPSO).
	# Able to find shortest path in comparison to FF &CPSO algorithms.	# Need additional power for coverage of tilted path.
GWO [10]	# Applied to solve three dimensional path planning problem of Unmanned aerial vehicles (UAVs).	# May go out of the boundaries easily due to generation of new random solutions.	# The alpha, and beta wolves participate actively in exploration and exploitation process. # Optimization process begins with random solutions in the form of initial populations.
	# Capable to maintain the right balance between exploration and exploitation process.	# Exhibit probability of getting trapped into local optima.
	# Uses fewer number of control parameters.	# Can have the sharp turn in the retrieved path, causing a problem for UAVs
VW-GWO [13]	# Useful for high dimensional optimization problems.	# Not optimized on all standard benchmark functions.	# Variable weights are assigned to each category of wolves.
	# Gives the low residual errors.	# GWO is used as a baseline model.
I-GWO [12]	# Used for Integer and mixed integer optimization problems. # Achieve faster convergence rate due to usage of opposition based learning. # Possess better search efficiency.	# Not suitable for solving complex problems. # Convergence rate depends upon the degree of complexity of a particular problem.	# Integrate opposition based learning (IOL) and chaotic local search (CLS) with GWO to solve integer and mixed integer optimization problems.
			# IOL escalates the convergence speed while CLS balance the searching and hunting processes.
GW-FOA [15]	# Suitable for local search problems.	# Not able to attain global optima therefore may not be well suited for wheeled or legged robots.	# Used fruit fly optimization algorithm (FOA).
	# Provides faster convergence rate and strong local search ability.		# Used GWO as a base line model in integration with FOA.
MGWO [11]	# Applied to solve TNEP problem. # Convergence faster due to involvement of omega wolves in exploration &exploitation processes.	# Needs further escalation of the exploitation and hunting process to obtain better optimization solutions	# Promotes the involvement of omega wolves in position updation during exploration phase.
			# Enhances the exploration speed thereby.
	# Minimize the computational cost.

^**The last column summarizes the key points of various algorithms depicting the similarities and differences among them.

The limitations of the above studies [10–15 , 51] and successful attempt of MGWO algorithm for transmission network expansion planning (TNEP) problem motivated authors to explore its use for developing path planning model for autonomous mobile robots. Therefore, in this study, we made an attempt to implement MGWO algorithm for mobile robot path planning problem and analyzed its performance with respect to extremely prevalent nature inspired algorithms. This approach was first introduced by Khandelwal et al. [11] for solving TNEP problem and is a recent contribution to the field of swarm intelligence. In author’s viewpoint, the modified variants of GWO could yield competent results due to having high resemblance between TNEP and robot path planning problems, both being complex, large scale and non-linear.

The contributions of the present study are:

To introduce a modified version of GWO known as MGWO for route planning of autonomous robots that is comparatively faster than those of original GWO and traditional algorithms in terms of speed.

To analyze the performance of the proposed method using different maps and is compared with other state of art methods such as PSO, GWO, VW-GWO, and IBA in terms of speed and convergence.

To analyze the performance of proposed method in terms of distance covered and execution time and the results are compared with other state of art methods (non-deterministic algorithms) for different number of iterations and population size.

This paper is organized as follows: section 2 describes problem formulation for multiple robots route planning and formation of surrounding. Section 3 explains GWO, MGWO, and VW-GWO path planning algorithms and aligning of MGWO technique to the multiple robot route planning problem. Implementation procedure and performance comparison of various algorithms are discussed in section 4. Section 5 presents results and discussion including convergence analysis of MGWO algorithm and its performance evaluation. Section 6 includes the conclusion.

2 Problem formulation

2.1 Problem statement

The multiple robot 2D route planning can be represented as a function of initial and final points that would follow up the desired trajectories as: $F_{n} ({input}_{i}, {output}_{i}) \to {Trajectory}_{i}$ (1)

Where input_i represents the origin indicated by (x_a, y_a) for i^th robot which is indicated as robot_i, output_i represents the destination point (x_d, y_d) for robot_i while trajectory_i points out the appropriate track for robot_i.

The primary aim of route planning is to determine a non-interacting optimal path with minimal path length cost ($_i). The initial position matrix for n robot is expressed as: $Pos = [\begin{matrix} {psn}_{1}^{1} & \dots & {psn}_{1}^{m} \\ {psn}_{2}^{1} & ⋱ & {psn}_{2}^{m} \\ {psn}_{n}^{1} & \dots & {psn}_{n}^{m} \end{matrix}]$ (2)

Where pos_i provides the information about the situation of i^th robot in a space of m dimension. As we are considering 2D space, therefore, the value of m is set as 2. The path length (Lp_i) of each given robot is shortened by using objective function as follows: $($_{1}^{*}, $_{2}^{*}, \dots $_{n}^{*}) = min ($_{1}, $_{2,} \dots $_{n}) \sum_{j = 1}^{n} c_{j} $_{j}$ (3)

The objective function is subject to constraint $p_{ij} ($_{i}, $_{j}) = 0 for every i, j = 1, 2, 3 \dots n$ (4)

Where i and j express distinct robots.

$_i represent route of i^th robot and is expressed as: $$_{i} = \sqrt{{(x_{a} - x_{d})}^{2} + {(y_{a} - y_{d})}^{2}}$ (5)

Where c_j express the route cost related with the route $ _j , whereas, the non-interacting track of robot i and j is denoted by p_ij. Therefore i and j have been considered from non-crossing routes lying between initial and final points.

2.2 Construction of maps

We have generated 3D-model graphs to present the multiple paths planning for the robots. The map permits the robots to move towards the goal point without having impact with static objects as well as other moving robots. In this research experiment, we have used four maps for the simulation process, which, along with their map boundaries, are presented in Table 3. There are initial boundary position and end boundary position for all the robots including obstacles. The initial and final positions of the robots are listed in Table 2. Table 3 presents the 3D coordinates of the obstacles, assuming the third dimension to be almost negligible. Here, the obstacle height (z-coordinate) is set to 0.25. In this experiment, we have considered 3D maps for the clear representation of 3D objects. However, the experiments were conducted for robots moving along the two axes x, y in the 3D map. Owning to this, we assumed the movement of robot in Z direction negligible (i.e. zero) for all the simulations carried out in this work. Obstacle representations for different maps are given in Table 3, where, absence of obstacles is indicated by dashes.

Table 2
3D map source and destination representation of six robots

Map Start position End position

1: (1,1,0)(5,2,0)(1,5,0)(2,1,0)(3.5,5,0)(7.5,2,0) → (15,8,0)(18,8,0)(17,8,0)(16,7,0)(19,9,0)(20,10,0)

2: (–4,0,0)(–2,1,0)(0,0,0)(1,2,0)(2,3,0)(4,0,0) → (10,10,0)(8,18,0)(10,15,0)(9,16,0)(8,9,0)(9,9,0)

3: (0,–4,0)(2,–2,0)(1,0,0)(1,4,0)(1,2,0)(5,5,0) → (20,20,0)(15,15,0)(17,18,0)(15,16,0)(19,17,0)(18,15,0)

4: (–4,–3,0)(–3,–4,0)(–2,–2,0)(1,1,0)(2,1,0)(1,2,0) → (10,15,0)(8,12,0)(8,15,0)(9,12,0)(10,12,0)(7,10,0)

Map	Start position	End position
1:	(1,1,0)(5,2,0)(1,5,0)(2,1,0)(3.5,5,0)(7.5,2,0) →	(15,8,0)(18,8,0)(17,8,0)(16,7,0)(19,9,0)(20,10,0)
2:	(–4,0,0)(–2,1,0)(0,0,0)(1,2,0)(2,3,0)(4,0,0) →	(10,10,0)(8,18,0)(10,15,0)(9,16,0)(8,9,0)(9,9,0)
3:	(0,–4,0)(2,–2,0)(1,0,0)(1,4,0)(1,2,0)(5,5,0) →	(20,20,0)(15,15,0)(17,18,0)(15,16,0)(19,17,0)(18,15,0)
4:	(–4,–3,0)(–3,–4,0)(–2,–2,0)(1,1,0)(2,1,0)(1,2,0) →	(10,15,0)(8,12,0)(8,15,0)(9,12,0)(10,12,0)(7,10,0)

Table 3

Obstacle dimensions for 3D maps

Obstacle Number	Map 1	Map 2	Map 3	Map 4
	(0,0,0) –(20,10,10)	(–5,0,0) –(10,20,15)	(0,–5,0) –(20,20,10)	(–5,–5,0) –(15,15,15)
1	(1,2,0) –(2,4,0)	(–4,1,0) –(–3,6,0)	(2,–5,0) –(3,5,0)	(–3, –5,0) –(–2.5,13,0)
2	(5,6,0) –(7,6,0)	(–2,7,0) –(–1,12,0)	(2,10,0) –(3,20,0)	(0,–3,0) –(0.5,15,0)
3	(5,1,0) –(6,3,0)	(–4,13,0) –(–3,18,0)	(5,5,0) –(6,15,0)	(3,–5,0) –(3.5,13,0)
4	(9,2,0) –(10,3,0)	(1,1,0) –(2,19,0)	(8,–5,0) –(9,5,0)	(6,–3,0) –(6.5,15,0)
5	(9,6,0) –(10,8,0)	(4,2,0) –(6,6,0)	(8,10,0) –(9,20,0)	(9,–5,0) (9.5,13,0)
6	(3,7,0) –(5,9,0)	(4,8,0) –(6,12,0)	(12,5,0) –(13,15,0)	(12,15,0)–(12.5,–3,0)
7	(14,2,0) –(15,8,0)	(4,14,0) –(6,18,0)	(16,–5,0) –(17,5,0)	—
8	—-	(8,5,0) –(8.5,19,0)	(16,10,0) –(17,20,0)	—

3 Methodology for robot path planning

In this section, firstly, we discuss the theoretical background of GWO and MGWO algorithms along with building the robot routes for grey wolves. Thereafter, the competency of implemented technique is compared with most recent state of art methods given in the literature.

3.1 Building the robot routes for grey wolves

In this algorithm, firstly the path with matrix ‘Pm’ is initialized, and then the source point ‘Sp’ is chosen, considering the later as current point. Here, N represents the highest counts in the matrix. If the route matrix contains the points greater than ‘N’, then the new developed route is assumed as a current solution. The modified GWO algorithm yields grey wolf as a connecting route between two points within the workspace [38]. Acquired outcomes include a price feature as discussed in the previous section. This value determines the work functionality. Better results are expected to achieve in terms of speed due to the involvement of omega wolves in exploration and exploitation process. To avoid the likelihood of robot entering into a countless loop or resettling again to the initial position, neighbor randomness was taken into consideration during its development phase to achieve the desired solution.

Algorithm 1: Generation of initial solutions based on random neighbor selection
1: Initialize path matrix ‘Pm’ and starting point ‘Sp’
2: Current point (Cp) = ‘Sp’
3: Neighbors n = get-Neighbors (Sp)
4: for all I = 1 to m do
5: Select n such that n (i)∪ n (i + 1) = ∅
6: Select random (n (i))
7: Pm = Pm ∪ n (i)
8: Cp = n (i)
9: if (Cp! = destination \|\| Num-points <N) then
10: go to step 3. Else go to step 5
11: end if
12: end for
13: set visited-points = unique (visited-points)
14: Return the path set ‘Pm’

Pseudo code for the random neighbor selection algorithm [39].

In this experiment, the workspace was symbolized as a discrete map. The discrete map was divided into identical sized cells referred to as grid. The main reason behind choosing the discrete map is that it seems to be more suitable than continuous map for graph representation. Robot path can be regarded as set of continuous points that initially begins from source point ultimately reaching to the target point. However, setting up the route from a specific point in the given maps generates eight possibilities for a robot to move in different directions on the surface. For example for an object O (x, y), the eight adjacent cells in the grid are denoted by:

$\begin{matrix} E (x + 1, y), F (x - 1, y), G (x, y + 1), H (x, y - 1), \\ I (x + 1, y + 1), J (x + 1, y - 1), K (x - 1, y + 1), \\ L (x - 1, y - 1) \end{matrix}$ (6)

1 can be added or subtracted for reaching the next point in the two dimensional workspace.

3.2 Grey wolf optimization (GWO) technique

Mirjalili et al. [20] developed an algorithm based on the social conduct, social hierarchy and trapping process of grey wolves. The developed algorithm is popularly known as GWO. The main steps associated with this algorithm are: (i) search for the prey, (ii) enclose the prey followed by hunting and pouncing.

In general, a metaheuristic algorithm includes two phases: an exploration followed by exploitation. Initially, in the first phase, the search points are decided by the grey wolves for different target nodes in the workspace. Thereafter, adjacent points join together to acquire optimized path length [39].

3.2.1 Social hierarchy

Alpha (α), beta (β), delta (δ) and omega (ω) wolves constitute the social hierarchy of grey wolves. We get the first best solution by α, followed by second and third best solution by β and δ, respectively. Whereas, response time of ω is slow. Alpha is usually considered as leader, who is responsible to frame rules and regulations for other wolves, while, the β wolves implements the instructions received from α., and δ wolves are treated as supervisors followed by other wolves known as ω. Omega wolves are treated as soldiers [20, 39].

3.2.2 Encircling prey

This section presents the mathematical model of grey wolf optimization algorithm. Wherein, the prey gets enclosed by grey wolf before getting trapped as illustrated by following equations: $S = | R * {psn}_{p} (i) - psn (i) |$ (7) $psn (i + 1) = {psn}_{p} (i) - P * S$ (8) the Equations (7) and (8) reflects the social hierarchy of the grey wolves pertaining to encircling behavior of grey wolves. Here, i express the current epoch, whereas psn_p represents the destination vector points. P, R represents the coefficient vectors; while, psn indicates the robot’s vector positions. The coefficient vectors P and R are estimated as follows: $P = 2 * a * r_{1} - a$ (9) $R = 2 * r_{2}$ (10)

Where r₁ and r₂ are assumed as random vectors lying in the range of [0 1], the coefficient a varies from 2 (maximum) to 0 (minimum)with increase in number of iterations and is expressed as: $a = 2 * (1 - \frac{{Crnt}_{iter}}{{Max}_{iter}})$ (11)

Crnt_iter and Max_iter refers to the current and maximum number of iterations respectively.

3.2.3 Hunting the prey

The grey wolves used to search the location of prey with the motive of enclosing them. α wolves take the lead and supervise the hunt, while, the β and δ wolves ‘barely take part in chasing [10]. Places of other search agents get refreshed with respect to the α position for updating the each robot’s location during optimization: $S_{alpha} = | R_{1} * {psn}_{alpha} - psn |$ (12) ${psn}_{1} = {psn}_{alpha} - P_{1} * S_{alpha}$ (13) $S_{beta} = | R_{2} * {psn}_{beta} - psn |$ (14) ${psn}_{2} = {psn}_{beta} - P_{2} * S_{beta}$ (15) $S_{delta} = | R_{3} * {psn}_{delta} - psn |$ (16) ${psn}_{3} = {psn}_{delta} - P_{3} * S_{delta}$ (17) $psn (i + 1) = \frac{{psn}_{1} + {psn}_{2} + {psn}_{3}}{3}$ (18)

Where S_alpha, S_beta and S_delta denote best search agents, while psn_alpha, psn_beta and psn_delta represents the corresponding position vectors. Here, we generates random population of grey wolves in order to initializes the underlying process. With the updated iterations, α, β and δ wolves evaluate the approximate location of the prey, thereby updating its distance from the prey with each iteration. Individual updated positions of α, β and δ wolves are represented by Equations 13, 15 and 17, respectively. However, the mean location of prey is obtained from the refreshed locations of α, β and δ wolves as represented by Equation (18).

3.2.4 Search for prey and attacking (exploration & exploitation)

The divergence phase for P occurs when P > 1. In case, the value of P lies in the range of [–1 1], the next position of the search agent will fall between the initial and final points. It can be adjusted such that the target position may result in convergence. The convergence or divergence of exploration depends upon the magnitude of P. Exploration converges from the target, if the value of P is smaller than 1, and diverges, if it is greater than 1. As per the analysis, exploration mechanism is driven by separate coefficient vector R, which yields the random values ranging between 0 and 2. If the value of R is considered to be greater than 1, then target gives more emphasis on the random weights, otherwise, target impact gets affected. It helps to avoid the local optima. The optimization process in grey wolf optimization process starts off with a set of initial populations generating the random solutions. The three best solutions are obtained corresponding to α, β and δ respectively. Corresponding to each ω wolf, their current position gets updated using Equations (12) to (18).

Explanation of pseudo code for GWO path planning approach is given as follows:

Algorithm 2: Algorithm for multi-Robot path planning using GWO
1. Initialize parameters: Population size: n, Initial position,
maximum iterations: max_iter, a, P, R.
2. Compute the fitness value of each robot.
a. psn_alpha = the principal search agent.
b. psn_beta = best search agent of second order.
c. psn_delta = best search agent of third order.
3. produce the initial grey wolf optimizer results using the Equations (2) and (3).
4. while iter ! = max_iter do.
5. for all (i = 1 to n) do.
6. update the current robots positions according to Equation (14).
7. end for.
8. Update a, P, and R using Equations (11), (9) and (10) respectively.
9. Calculate the fitness of all the Robots.
10. Update psn_alpha, psn_beta,psn_delta using Equations (13), (15) and (17).
11. iter = iter +1.
12. end while.
13. output the most optimized path = best grey wolf (psn_alpha).

3.3 Modified grey wolf optimization (MGWO)

In modified GWO algorithm, all ω wolves are also included in the hunting process along with δ wolves. Thus, δ wolves form a new family along with ω wolves which is represented by the following equation: ${psn}_{3} (new) = \frac{{psn}_{3} + {psn}_{4}}{2}$ (19)

Where, psn₄ represents the location of ω wolves, while psn₃ (new) represents the location of a new family, which is comprised of δ and ω wolves. In this algorithm, ω wolves ‘position also gets updated similar to that of α, β and δ wolves pertaining to GWO algorithm.

The positions of ω wolves are updated as follows: $S_{omega} = | R_{4} * {psn}_{omega} - psn |$ (20) ${psn}_{4} = {psn}_{omega} - P_{4} * S_{omega}$ (21)

The best solution after updation of position is given by: $psn (i + 1) = \frac{{psn}_{1} + {psn}_{2} + {psn}_{3} (new)}{3}$ (22)

The pseudo code for MGWO is described as follows:

Algorithm 3: Modified Grey wolf Optimization (MGWO) [9].
1. Initialize the Grey wolf population.
2. Initialize a,μ, P and R variables.
3. Define MNI = maximum number of iterations.
4. Compute fitness of each search agent (SA).
i. psn_alpha = principal SA.
ii. psn_beta = best SA of second order.
iii. psn_delta = best SA of third order.
iv. psn_omega = rest of the SA.
5. While μ < MNI do
6. For each search agent do
7. Refresh the location of the existing SA by Equation (22)
8. End for
9. Update a, P and R
10. Evaluate the fitness for all SA candidates
11. Update psn_alpha, psn_beta, psn_delta and psn_omega
12. μ =μt + 1
13. end while
14. return psn_alpha

SA - search agent

3.4 Variable weight grey wolf optimization algorithm (VW-GWO)

In the standard GWO algorithm, Gao et al. [14] proposed the idea of equal contribution of dominant wolves in the searching process as can be seen from Equation (18). However, initially, αis considered to be closer to the prey. Therefore, the can be given higher weights compared to that of β and δ wolves. Authors considered the average weight given in Equation (18) against the social hierarchy of the grey wolves [14]. Based upon this logic, they hypothesized the new strategy as follows:

Initially, α is closest to the prey in comparison to other wolves, therefore has been given maximum weight close to 1 initially, while weights of β and δ is set to zero.

According to Gao et al. [14] initially all the weights assigned to α, β, and δ wolves must vary between 0 and 1 and attains the value of 1 after summation. The proposed rule was incorporated as follows: $psn (i + 1) = w_{1} * {psn}_{1} + w_{2} * {psn}_{2} + w_{3} * {psn}_{3}$ (23) $w_{1} + w_{2} + w_{3} = 1$ (24)

Secondly, the weight of α, β, and δ must also satisfy $w_{1} ⩾ w_{2} ⩾ w_{3 .}$ (25)

Where w_1, w₂_, and w₃ indicate the weight of α, β, and δ respectively.

Equation (25) demonstrates the highest weight of alpha wolves in the beginning of hunting process due to their closeness to the prey. As time lapse weight of α decreases from 1 to 1/3 due to the involvement of beta wolves. However, the weights of the β and δ increases from 0.0 to 1/3 due to their active participation in the hunting process [13]. The above range has been computed using a cosine function that describes w₁ with the angle θ to vary between 0 and arcos (1/3).

The weights should vary with the cumulative iteration number. We know that $w_{2} . w_{3} \to 0 when iter = 0$ (26) $w_{1}, w_{2}, w_{3} \to \frac{1}{3} when iter \to \infty .$ (27)

Based on above assumptions, a new method of the locations with variable weights is presented as follows:

$\begin{matrix} w_{1} = \cos θ, w_{2} = \frac{1}{2} \sin θ . cos (90 - θ), \\ w_{3} = 1 - w_{1} - w_{2} \end{matrix}$ (28)

The Fig. 1 represents the variable weights versus number of iteration.

Fig. 1

The variable weights vs. iterations.

3.5 Trajectory formation for multiple robots

MGWO algorithms can cause an abrupt change in the retrieved route that might not be followed by robots during navigation. Therefore, it is essential to refine the path of trajectory. The vehicular mobility that is expressed as a speed and displacement of robot is defined as a function of the time using polynomial Equation (29). The fifth order equation with the initial and final values would generate an adjacent route assuming the initial derivatives to be consistent. Thereafter, the derivative of polynomials is computed yielding the successful outcome of the drive. A normal fifth degree polynomial is described as: $S (t) = b_{0} + b_{1} t + b_{2} t^{2} + b_{3} t^{3} + b_{4} t^{4} + b_{5} t^{5}$ (29)

The sub-points initiated in the preliminary phase, are considered to be crucial points in the enclosed path during trajectory formation assist the robot to avert any obstacle or hindrance. The speed and movement of the robot traversing with all the points are chosen based on trajectory fitting strategy [37] to generate an appropriate path. The ultimate aim of path planning using MGWO is to acquire an optimal path between initial and target points while avoiding collision between obstacles and robots.

4 Implementation approach

To evaluate the performance of MGWO algorithm, several experiments on six similar robots were conducted in MATLAB 2018a using personal computer with i7 processor and 8 GB RAM. In this work, the algorithms were executed on four different maps as listed in Table 2.

4.1 Setting of parameters for 2D path planning

In this section, we have demonstrated the path planning of all robots in 2D workspace using various metaheuristic algorithms. All the algorithms are tested using four different maps and the coordinates values corresponding to these maps are given in Table 2.

We conducted the number of trials to make the exact choice of model parameter values before the actual implementation of the considered algorithms and their parameter values are listed in Table 4.

Table 4
Parameter values for different algorithms under consideration.

Algorithm Parameters Values

PSO Population size 25–30

Maximum iterations 30–45

Personal learning coefficient (c₁) 1.6

Global learning coefficient (c₂) 1.4

Inertia weight (w) 1

Inertia weight damping ratio 0.96

IBA Population size 25–30

Maximum Iterations 30–45

Loudness (A) 0.5

Frequency(Q) 0.5

Pulse emission rate(r) 0.5

GWO Maximum iterations 30–45

Population size 25–30

Parameter (a) [2,0]

MGWO Maximum iterations 30–45

Population size 25–30

Parameter (a) [2,0]

VW-GWO w1 1–0.3,

w2 0–0.3,

w3 0–0.3

Population size 25–30

Maximum iterations 30–45

Parameter (a) [2,0]

Algorithm	Parameters	Values
PSO	Population size	25–30
	Maximum iterations	30–45
	Personal learning coefficient (c₁)	1.6
	Global learning coefficient (c₂)	1.4
	Inertia weight (w)	1
	Inertia weight damping ratio	0.96
IBA	Population size	25–30
	Maximum Iterations	30–45
	Loudness (A)	0.5
	Frequency(Q)	0.5
	Pulse emission rate(r)	0.5
GWO	Maximum iterations	30–45
	Population size	25–30
	Parameter (a)	[2,0]
MGWO	Maximum iterations	30–45
	Population size	25–30
	Parameter (a)	[2,0]
VW-GWO	w1	1–0.3,
	w2	0–0.3,
	w3	0–0.3
	Population size	25–30
	Maximum iterations	30–45
	Parameter (a)	[2,0]

The social capability, cognitive capability, and naïve capability are used to characterize the metaheuristic algorithms depends on their attitude to mingle with other candidates. The social strength can be understood as the individual’s capability to grasp from others in the swarm. To possess this quality, one should have to establish an honest communication among people within the cluster. The cognitive strength represents the individual’s strength to learn from its historical experience.

It is very difficult to do the theoretical comparison among different meta-heuristic algorithms merely on the basis of their physical properties, since each metaheuristic algorithm possess its own property to deal with a particular problem. Table 3 provides the description of parameters which are used for different metaheuristic algorithms under study.

5 Simulation results

In this section, we present the simulation results of different variants of GWO including PSO and IBA for four maps with six robots; wherein each map contains 6 to 8 obstacles.

The MGWO method was run on all the four maps and the obtained results were compared with four different metaheuristic approaches viz., PSO [26], IBA [31], GWO [10], and VW-GWO [13]. The execution time corresponding to Map 1, 2, 3, and 4 is listed in Table 5, 6, 7 and 8 respectively. For these maps, number of iterations and population size were set to 25, 30 and 40, 45, respectively.

Table 5
Average time taken (in sec.) and distance covered (in cm.) of different techniques of Map 1 for varying number of iterations and population size

Algorithm P. Size Iterations BC (R1) BC (R2) BC (R3) BC (R4) BC (R5) BC (R6) Overall Time(avg.)

PSO 25 40 168 205 199 139 227 310 48.00

IBA 25 40 169 203 199 141 227 309 72.12

GWO 25 40 168 204 198 141 227 310 21.99

MGWO 25 40 168 203 198 140 226 308 15.27

VW-GWO 25 40 169 204 199 140 227 310 22.91

PSO 30 45 168 205 199 141 228 311 64.44

IBA 30 45 169 204 200 140 226 307 98.46

GWO 30 45 168 212 199 141 227 308 24.15

MGWO 30 45 168 204 198 140 226 307 17.91

VW-GWO 30 45 169 207 198 140 226 310 23.03

Algorithm	P. Size	Iterations	BC (R1)	BC (R2)	BC (R3)	BC (R4)	BC (R5)	BC (R6)	Overall Time(avg.)
PSO	25	40	168	205	199	139	227	310	48.00
IBA	25	40	169	203	199	141	227	309	72.12
GWO	25	40	168	204	198	141	227	310	21.99
MGWO	25	40	168	203	198	140	226	308	15.27
VW-GWO	25	40	169	204	199	140	227	310	22.91
PSO	30	45	168	205	199	141	228	311	64.44
IBA	30	45	169	204	200	140	226	307	98.46
GWO	30	45	168	212	199	141	227	308	24.15
MGWO	30	45	168	204	198	140	226	307	17.91
VW-GWO	30	45	169	207	198	140	226	310	23.03

BC-Best cost, R - Robot.

Table 6

Average time taken (in sec.) and distance covered (in cm.) of different techniques of Map 2 for varying number of iterations and population size

Algorithm	P. Size	Iterations	BC (R1)	BC (R2)	BC (R3)	BC (R4)	BC (R5)	BC (R6)	Overall Time(avg.)
PSO	25	40	262	306	271	250	131	150	133
IBA	25	40	258	302	269	254	129	149	157
GWO	25	40	267	312	269	261	130	149	25.85
MGWO	25	40	257	301	269	261	128	149	21.80
VW-GWO	25	40	269	312	270	260	130	150	26.36
PSO	30	45	262	301	268	252	131	149	115
IBA	30	45	266	303	270	252	129	147	199
GWO	30	45	268	312	269	259	130	148	31.38
MGWO	30	45	261	316	268	252	128	147	24.75
VW-GWO	30	45	270	315	272	263	131	149	29.66

BC-Best cost, R - Robot.

Table 7

Average time taken (in sec.) and distance covered (in cm.) of different techniques of Map 3 for varying number of iterations and population size

Algorithm	P. Size	Iterations	BC (R1)	BC (R2)	BC (R3)	BC (R4)	BC (R5)	BC (R6)	Overall Time(avg.)
PSO	25	40	472	336	377	336	299	260	199
IBA	25	40	475	340	381	282	296	260	208
GWO	25	40	483	348	386	287	298	262	28.45
MGWO	25	40	482	348	386	287	295	260	28.11
VW-GWO	25	40	483	346	386	288	299	264	31.38
PSO	30	45	469	338	375	337	299	262	256
IBA	30	45	473	344	385	377	298	258	295
GWO	30	45	484	352	386	286	299	260	32.83
MGWO	30	45	481	348	387	287	298	261	32.64
VW-GWO	30	45	482	349	386	287	299	263	37.28

BC-Best cost, R –Robot.

Table 8

Average time taken (in sec.) and distance covered (in cm.) of different techniques of Map 4 for varying number of iterations and population size

Algorithm	P. Size	Iterations	BC (R1)	BC (R2)	BC (R3)	BC (R4)	BC (R5)	BC (R6)	Overall Time(avg.)
PSO	25	40	351	172	296	229	228	160	186
IBA	25	40	351	163	298	227	229	160	226
GWO	25	40	358	174	304	239	229	160	18.18
MGWO	25	40	350	171	305	225	231	159	17.49
VW-GWO	25	40	358	171	305	239	229	160	22.52
PSO	30	45	358	167	304	238	226	158	102
IBA	30	45	354	169	301	238	228	159	182
GWO	30	45	359	172	305	242	232	159	26.27
MGWO	30	45	359	173	305	238	229	161	25.34
VW-GWO	30	45	360	171	304	238	228	162	33.45

BC-Best cost, R - Robot.

Figures 6 and 7 shows the average best fitness cost and execution time for varying number of iterations and population size for all the four maps. It can be observed that the MGWO approach yielded the better results compared to the most of the other metaheuristic approaches. The Figs. 2, 3, 4, and 5 illustrates the robot movement and paths generated by the algorithms. The trajectory relies on the path smoothness and MGWO optimization strategy.

Fig. 2

Map 1 Path planning for Robot 6: (0.5, 0.5, 0) –(20, 10, 0).

Fig. 3

Map 2 Path planning for Robot 3: (0, 0, 0) –(10, 15, 0).

Fig. 4

Map 3 Path planning example for Robot 1: (0,-5, 0) –(20, 20, 0).

Fig. 5

Map 4 Path planning for Robot 1: (–4, –3, 0) –(10, 15, 0).

Fig. 6

Average best cost and execution time analysis for Map 1, Map 2, Map 3, and Map 4 (Ps = 25, It = 40).

Fig. 7

Average best cost and execution time analysis for Map 1, Map 2, Map 3, and Map 4 (Ps = 30, It = 45).

The execution time of the proposed algorithm is compared with PSO, IBA, GWO, and VW-GWO algorithms for generating a feasible route from the initial point to target point. The algorithm works in such a way that they are able to generate the routes between desired ends for all the grid maps.

From Tables 5, 6, 7 and 8 it was noticed that the MGWO algorithm took the less time and performed well, compared to other metaheuristic algorithms under consideration in almost all the cases. MGWO outperformed over GWO, while, VW-GWO yielded relatively better results with respect to execution time and average best cost over other techniques.

5.1 Analysis of convergence for MGWO algorithm

From the results given in Tables 9, 10, 11, and 12 it can be noticed that the MGWO algorithm yielded an optimal result with less number of iterations without any obstruction in the workspace. However, more number of iterations are required for convergence with increase in number of obstructions in workspace. Figure 8 reflects the drastic reduction in the average best cost of various algorithms for different number of iteration (1 to 10). From convergence analysis shown in Fig. 8, it can be observed that some points of MGWO algorithm overlaps with other metaheuristic algorithms for Map 1 and Map 2, respectively. However, for Map 3, overlapping occurs for higher iterations (30 iterations) and it is almost negligible for Map 4. Some robots may fail to reach to the destination point in case of iterations smaller than 10. The initial best cost is higher for IBA algorithm with Map 1, Map 2, and Map 3, while it is higher for VW-GWO algorithm for Map 4. A little difference is observed in the execution times of different meta-heuristic algorithms for Map 1 and Map 4, as presented in Table 9, 10, 11 and 12, respectively. However, this gap enlarges for Map 2 and Map 3 due to presence of more number of obstacles in these maps. All the considered algorithms were run 100 times to get the average time and average best cost. The above results demonstrate that MGWO algorithm gives better performance than other state of art methods. Hence the proposed approach seems to be more competent than other approaches taken under consideration for multi robot route planning applications.

Table 9
Average best cost (in cm) per iteration count for Map 1

Iterations Mean±SD Mean±SD Mean±SD Mean±SD Mean±SD

PSO IBA GWO MGWO VW-GWO

1 226.30±1.36 292.80±2.23 226.35±1.18 224.20±1.15 225.40±1.17

10 217.20±1.31 221.30±2.11 217.20±1.10 215.90±1.01 216.60±1.07

20 210.80±1.28 215.60±1.87 210.85±0.88 209.50±0.82 210.50±0.92

30 208.70±1.24 211.20±1.75 208.70±0.73 208.40±0.68 208.80±0.70

40 208.00±1.23 208.00±1.73 208.00±0.70 207.16±0.62 208.26±0.66

Iterations	Mean±SD	Mean±SD	Mean±SD	Mean±SD	Mean±SD
1	226.30±1.36	292.80±2.23	226.35±1.18	224.20±1.15	225.40±1.17
10	217.20±1.31	221.30±2.11	217.20±1.10	215.90±1.01	216.60±1.07
20	210.80±1.28	215.60±1.87	210.85±0.88	209.50±0.82	210.50±0.92
30	208.70±1.24	211.20±1.75	208.70±0.73	208.40±0.68	208.80±0.70
40	208.00±1.23	208.00±1.73	208.00±0.70	207.16±0.62	208.26±0.66

Table 10

Average best cost (in cm) per iteration count for Map 2

Iterations	Mean±SD	Mean±SD	Mean±SD	Mean±SD	Mean±SD
	PSO	IBA	GWO	MGWO	VW-GWO
1	492.20±2.54	972.97±4.71	523.04±2.68	503.60±2.54	538.34±2.86
10	282.70±2.33	312.41±3.21	286.93±2.00	272.38±2.01	286.85±2.11
20	266.10±2.24	267.04±2.45	255.74±1.54	246.32±1.43	256.44±1.45
30	241.30±2.01	248.72±2.32	246.52±1.89	238.84±1.17	245.62±1.22
40	228.00±1.78	231.60±2.09	231.43±1.21	227.00±1.02	232.00±1.20
50	217.40±1.75	221.20±1.98	228.65±0.98	223.74±0.78	229.53±0.88

Table 11

Average best cost (in cm) per iteration count for Map 3

Iterations	Mean±SD	Mean±SD	Mean±SD	Mean±SD	Mean±SD
	PSO	IBA	GWO	MGWO	VW-GWO
1	512.82±2.45	748.20±3.87	402.33±2.77	386.22±2.43	392.11±2.76
10	442.64±2.33	442.88±2.78	362.63±2.34	358.50±2.23	359.66±2.22
20	402.00±2.03	396.52±2.44	353.34±2.21	349.20±2.06	351.52±2.12
30	359.32±2.00	347.64±2.12	346.62±2.00	344.44±1.89	345.00±1.97
40	347.00±1.65	339.00±2.01	344.00±1.64	343.00±1.66	344.33±1.64
50	345.25±1.56	336.04±1.77	342.22±1.07	341.80±1.07	342.72±1.06

Table 12

Average best cost (in cm) per iteration count for Map 4

Iterations	Mean±SD	Mean±SD	Mean±SD	Mean±SD	Mean±SD
	PSO	IBA	GWO	MGWO	VW-GWO
1	266.20±1.54	263.74±2.11	274.84±1.78	271.80±1.88	275.10±1.79
10	252.33±1.32	248.00±1.65	253.65±1.21	249.33±1.15	254.55±1.11
20	245.18±1.12	243.33±1.56	246.80±1.08	242.44±1.03	246.00±1.00
30	240.04±0.99	238.80±1.43	244.33±0.88	240.20±0.75	244.04±0.86
40	239.33±0.89	238.00±1.10	244.00±0.76	238.00±0.68	243.66±0.73

Fig. 8

Convergence analysis graph for Map 1, Map 2, Map 3, and Map 4 using MGWO algorithm.

5.2 Performance evaluation

MGWO algorithm possesses the following advantages over other algorithms: (i) flexibility, (ii) simplicity, (iii) induction free technique, and (iv) avoidance of local optimum. Simplicity means it requires comparatively less variables to manage the algorithm. Flexibility denotes the applicability and suitability of MGWO algorithm to various kinds of problems without any modification in the algorithm. In contrast with gradient based optimization methods, Grey Wolf Optimizer and its variants possess good capability to optimize the problems stochastically. In former case, there is need to compute the derivative of search spaces during the optimization process. Whereas, in later case, no derivative is needed to compute. MGWO technique can be efficaciously used for real problems with unknown by-product information.

Stochastic nature of MGWO algorithm makes it more compatible for local optima avoidance compared to the traditional optimization methods. Owning to this, MGWO algorithm becomes highly competent for solving nonlinear, multivalued, and interdisciplinary function optimization problems. The recent study [11] has also proven the efficacy of the MGWO algorithm for solving the transmission network expansion planning (TNEP) problem. This problem is a non-linear programming problem for mixed integers. The chances of MGWO algorithm for getting trapped into local minima reduces significantly due to less number of parameters in comparison to other meta-heuristic algorithms.

Wolpert et al. [38] presented No Free Lunch (NFL) hypothesis. According to NFL hypothesis, there is no meta-heuristic technique that may best deal with all sorts of optimization problems. Especially, a particular algorithm may produce excellent results for a specific type of problem; however, the same algorithm may not yield good results for different kind of problem.

As we do not have prior knowledge about the algorithms, which algorithm would be most suitable for solving any specific optimization problem. Here, in this work, various biologically inspired techniques are tested to resolve the actual multi robot route planning assignment. We undertook many algorithms such as PSO, IBA, GWO, and VW-GWO to resolve the robot’s route planning problem and found MGWO technique to be most suitable for this particular application. Hence, in this paper, MGWO algorithm is recommended as a most competent and preferred algorithm for solving multi robot route planning issues.

To solve the multi robot route planning issue, some theoretical points are needed to be taken into consideration about MGWO [11 , 44]:

The uncompromising social structure facilitates MGWO algorithm to obtain the faster optimal answer with the growing range of iterations.

Parameter of MGWO allows robots for the smooth transformation between exploitation and exploration.

As we increase gain of P, initially, about 50 percent of the iterations are committed to the search space exploration and rests of the 50 percent iterations are committed to converging into respective target location.

There is only one variable in MGWO algorithm that needs to be regulated in the robot route planning task.

The proposed method is compared with the work of various researchers who have contributed to the field of robot path planning. The results are provided in Table 13. However, the proposed method is not directly comparable with those of TLBO-ANFIS and FF-CPSO methods due to consideration of different map structures, simulation environment, number and size of obstacles, and hardware configuration used by different researchers. The results provided in Table 13 presents that our method gives better performance in comparison to other methods such as VW-GWO, GWO, and BAT when implemented on same hardware.

Table 13
Performance comparison of the proposed method with current state of art methods in terms of average execution time, and average speed

Methods Number of Runs Avg. execution time (sec.) Avg. Speed (cm/sec.) Hardware used (Processor/RAM)

GWO [10] 100 28.32 9.14 Processor: i7; Speed: 1.5 GHZ; RAM: 8 GB

VW-GWO [13] 100 23.62 9.96 Processor: i7; Speed: 1.5 GHZ; RAM: 8 GB

FF-CPSO [50] 10 74.29 14.89 Processor: i7; Speed: 2.70 GHZ; RAM: 8 GB

TLBO-ANFIS [49] — 18.30 20.00 Khepera III robot with speed: 25 MHZ; RAM: 512 KB

IBA [31] 100 179.70 1.60 Processor: i7; Speed: 1.5 GHZ; RAM: 8 GB

MGWO (Proposed Method) 100 20.67 11.36 Processor: i7; Speed: 1.5 GHZ; RAM: 8 GB

Methods	Number of Runs	Avg. execution time (sec.)	Avg. Speed (cm/sec.)	Hardware used (Processor/RAM)
GWO [10]	100	28.32	9.14	Processor: i7; Speed: 1.5 GHZ; RAM: 8 GB
VW-GWO [13]	100	23.62	9.96	Processor: i7; Speed: 1.5 GHZ; RAM: 8 GB
FF-CPSO [50]	10	74.29	14.89	Processor: i7; Speed: 2.70 GHZ; RAM: 8 GB
TLBO-ANFIS [49]	—	18.30	20.00	Khepera III robot with speed: 25 MHZ; RAM: 512 KB
IBA [31]	100	179.70	1.60	Processor: i7; Speed: 1.5 GHZ; RAM: 8 GB
MGWO (Proposed Method)	100	20.67	11.36	Processor: i7; Speed: 1.5 GHZ; RAM: 8 GB

6 Conclusion

This study presents a better solution for a route planning strategy of multiple robots based on modified grey wolf optimization (MGWO) algorithm. The proposed algorithm was able to identify an optimized track between the initial point and destination points while keeping optimal terrain constraints with static barriers. In this algorithm, we carried out simulation for different route tracks using four maps and six robots in order to seek the most feasible solution for multi robot path planning based on the social and optimized behavior of grey wolves. The proposed approach leads to the faster convergence and local optima avoidance, resulting in less computational cost and higher efficacy in comparison to other state of art methods. The presented approach utilizes minimum parameters, thereby improving the speed of convergence.

From the experimental results provided in the paper, we infer that the MGWO algorithm is more competent and suitable for muti-robot route planning problems compared to other state of art methods. Hence, authors recommend it for this particular robotic application. However, the speed performance of the algorithm might get affected on increasing the complexity of simulation environment (i.e. with more than eight obstacles) subject to confirmation through conduction of more number of experimental trials with varying size, shape and number of obstacles. The efficacy of the algorithm could be further enhanced by using reinforcement learning during exploration and exploitation process and may be adopted as a possible solution to the problem. As a future work, it could be interesting to extend its application to develop an efficient path planning model for UAVs in dynamic environment.

References

Xia

, Zhang

, Weng

, Liu

and Wang

, Robot path planning based on multi-objective optimization with local search, Journal of Intelligent & Fuzzy Systems 35(2) (2018), 1755–1764.

Jaffery Zaheeruddin

Z.A.

and Singh

, Computerized segmentation of suspicious lesion in digital mammograms, Computer Methods in Biomechanics and Biomedical Engineering: Imaging & Visualization 5(2) (2017), 77–86.

Hosseininejad

and Dadkhah

, Mobile robot path planning in dynamic environment based on cuckoo optimization algorithm, International Journal of Advanced Robotic Systems 16(2) (2019), 1–13.

Smierzchalski

and Michalewicz

, Path planning in dynamic environments, Innovations in Robot Mobility and Control 8 (2005), 135–153.

Barraquand

and Latombe

J.C.

, Robot motion planning: A distributed representation approach, The International Journal of Robotics Research 10(6) (1991), 628–649.

Lavalle

S.M.

, Rapidly exploring random trees: A new tool for path planning, Technical Report 3 (1998).

Kala

, Shukla

and Tiwari

, Fusion of probabilistic A* algorithm and fuzzy inference system for robotic path planning, Artificial Intelligence Review 33 (2010), 307–327.

Asadi

, Azimirad

, Eslami

and Ghanbari

, A novel global optimal path planning and trajectory method based on adaptive Dijkstra-immune approach for mobile robot, Proceedings of the IEEE International Conference on Advanced Intelligent Mechatronics (2011), 1093–1098.

Gigras

, Jora

and Dhull

, Comparison between different metaheuristic algorithms for path planning in Robotics, International Journal of Computer Applications 142(3) (2016), 6–10.

10.

Dewangan

R.K.

, Shukla

and Godfrey

W.W.

, Three dimensional path planning using grey wolf optimizer for UAVs, Applied Intelligence 49(7) (2019), 2201–2217.

11.

Khandelwal

, Bhargava

, Sharma

and Sharma

, Modified Grey Wolf Optimization Algorithm for Transmission network Expansion planning Problem, Arabian Journal for Science and Engineering 43 (2018), 2899–2908.

12.

Gupta

and Deep

, An efficient Grey Wolf optimizer with Opposition based learning and Chaotic Local search for Integer and Mixed-Integer Optimization Problems, Arabian Journal for Science and Engineering 44 (2019), 7277–7296.

13.

Kumar

, Singh

and Tiwari

, Comparison of two Meta- Heuristic Algorithms for path planning in Robotics, International Conference on Contemporary Computing and Applications (2020), 159–162.

14.

Gao

Z. M.

and Zhao

, An improved Grey Wolf optimization algorithm with variable weights, Computational Intelligence and Neuroscience 2019 (2019), 1–13.

15.

, Kun

, Xu

and Wang

, Path Planning of UAV for oilfield inspection based on improved GreyWolf Optimization Algorithm, The 31th Chinese Control and Decision Conference IEEE (2019), 3666–3671.

16.

Shanmugavel

, Tsourdos

, Bikowski

R. Z.

and White

, Path planning of multiple UAVs with clothoid curves in two dimensions, 17th IFAC Symposium on Automatic Control in Aerospace 40(7) (2007), 461–466.

17.

Bellingham

J.S.

, Tillerson

and Alighanbari

, Cooperative path planning for multiple UAVs in dynamic and uncertain environments, Proceedings of IEEE Conference on Decision and Control 41 (2002), 2816–2822.

18.

Ding

X.C.

, Rahmani

A.R.

and Egerstedt

, Multi UAV convoy protection: an optimal approach to path planning and coordination, IEEE Trans Robot 26(2) (2010), 256–268.

19.

Zhang

, Zhang

and Hapeshi

, A review of nature inspired algorithms, Journal of Bionic Engineering 7(4) (2010), 232–237.

20.

Mirjalili

, Mirjalili

S.M.

and Lewis

, Grey wolf optimizer, Advances in Engineering Software 69 (2014), 46–61.

21.

Komaki

G.M.

and Kayvanfar

, Grey wolf optimizer algorithm for the two-stage assembly flow shop scheduling problem with release time, Journal of Computational Science 8 (2015), 109–120.

22.

Sharma

and Saikia

L.C.

, Automatic generation control of a multi-area ST-thermal power system using grey wolf optimizer algorithm based classical controllers, International Journal of Electrical Power & Energy Systems 73 (2015), 853–862.

23.

Jayakmar

, Subramanian

, Ganesan

and Elanchezhian

E.B.

, Grey wolf optimization for combined heat and power dispatch with cogeneration systems, International Journal of Electrical Power & Energy Systems 74 (2016), 252–264.

24.

Emary

, Zawbaa

H.M.

and Hassanien

A.E.

, Binary grey wolf optimization approaches for feature selection, Neuro Computing 172 (2016), 371–381.

25.

Sulaiman

M.H.

, Mustaffa

, Mohamed

M.R.

and Aliman

, Using the grey wolf optimizer for solving optimal reactive power dispatch problem, Applied Soft Computing 32 (2015), 286–292.

26.

Wang

and Cai

, Dynamic path planning for mobile robot based on particle swarm optimization, AIP Conf Proc 1864 (2017), 20–24.

27.

Mirjalili

, Saremi

, Mirjalili

S.M.

and Coelho

L.D.S.

, Multi-objective grey wolf optimizer: A novel algorithm for multi-criteria optimization, Expert Systems with Applications 47 (2016), 106–119.

28.

Emary

, Yamany

, Hassanien

A.E.

and Snase

, Multi-objective grey wolf optimization for attribute reduction, Procedia Computer Science 65 (2015), 623–632.

29.

Kamboj

V.K.

, A novel hybrid PSO-GWO approach for unit commitment problem, Neural Computing Applications 27 (2016), 1643–1655.

30.

and Xu

, Research of biogeography particle swarm optimization for robot path planning, Neurocomputing 148 (2015), 91–99.

31.

Guo

, Gao

and Cui

, The path planning for mobile robot based on bat algorithm, Int Journal of Automation and Control 9(1) (2015), 50–60.

32.

Wang

, Chu

and Mirjalili

, Three dimensional path planning of UCAV using an improved BAT algorithm, Aero Sci Technology 49 (2016), 231–238.

33.

Wang

, Guo

, Duan

, Liu

and Wang

H.A.

, A BAT algorithm with mutation for UCAV path planning, The Scientific World Journal 2012 (2012), 1–15.

34.

Bohat

and Arya

K.V.

, An effective gbest-guided gravitational search algorithm for real parameter optimization and its application in training of feedforward neural networks, Knowledge Based System 143 (2018), 192–207.

35.

Khairuzzaman

A.K.M.

and Chaudhary

, Multilevel thresholding using grey wolf optimizer for image segmentation, Expert Systems with Applications 86 (2017), 64–76.

36.

Bohat

and Arya

K.V.

, Artificial Prey-Predator (APP): An efficient approach for numerical function optimization, Conference on Information and Communication Technology (2017), 1–6.

37.

Duan

H.B.

, Ma

G. J.

and Luo

D.L.

, Optimal formation reconfiguration control of multiple UCAVs using improved particle swarm optimization, Journal of Biotic Engineering 5 (2008), 340–347.

38.

Wolpert

D.H.

and Macready

W.G.

, No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation 1(1) (1997), 67–82.

39.

Song

, Grey wolf optimizer for parameter estimation in surface waves, Soil Dynamics and Earthquake Engineering 75 (2015), 147–157.

40.

Guha

, Roy

P.K.

and Banerjee

, Load frequency control of large scale power system using quasi-oppositional grey wolf optimization algorithm, Engineering Science and Technology (2016).

41.

Sharma

, Sundaram

, Sharma

and Gupta

, Diagnosis of Parkinson’s disease using modified grey wolf optimization, Cognitive Systems Research 54 (2019), 100–115.

42.

Gupta

and Deep

, A Novel Random Walk Grey Wolf Optimizer, Swarm and Evolutionary Computation 44 (2018), 101–112.

43.

Xing

, Yue

, Chen

and Xiang

Y.A.

, Deep Belief network combined with modified grey wolf optimization algorithm for PM 2.5 concentration prediction, Applied Sciences 9(18) (2019), 3765.

44.

Patle

B.K.

, Babu

L.G.

, Pandey

, Parhi

D.R.K.

and Jagadeesh

, A Review: On path planning strategies for navigation of mobile robots, Defence Technology 15(4) (2019), 582–606.

45.

Yan

A.J.

, Improving mobile robot localization: Grid based approach, Optical Engineering 51(2) (2012), 4401.

46.

Qu.

, Yang

S.X.

, Willms

A.R.

and Yi

, Real time robot path planning based on a modified pulse coupled neural network model, IEEE Transactions on Neural Networks 20(11) (2009), 1724–1739.

47.

, Li

, Jiang

and Wang

, Double layers fuzzy logic based mobile robot path planning in unknown environment, Intelligent Automation and Soft Computing 15(2) (2009), 275–288.

48.

Giagkiozis

, purshouse

R.C.

and Fleming

P.J.

, An overview of population based algorithms for multi-objective optimization, International Journal of Systems Science 46(9) (2015), 1572–1599.

49.

Aouf

, Boussaid

and Sakly

, TLBO based Adaptive Neurofuzzy Controller for mobile robot navigation in a strange environment, Computational Intelligence and Neuroscience 2018 (2018), 1–8.

50.

Jawad

M.M.

and Hadi

E.A.

, A Comparative study of various intelligent algorithms based path planning for Mobile Robots, Journal of Engineering 25(6) (2019), 83–101.

51.

Feng

and Wu

, Robot path planning algorithm based on partially observable Markov, Journal of Intelligent and Fuzzy Systems 24(10) (2017), 1–6.