International Journal of Automation and Computing DOI: 10.1007/s11633-016-1019-x

An Intelligent Multi-robot Path Planning in a Dynamic Environment Using Improved Gravitational Search Algorithm P. K. Das1 1

H. S. Behera1

P. K. Jena2

B. K. Panigrahi3

Department of Computer, Sceime and Engineering and Information Technology, Veer Surendra Sai University of Technology, Burla, Odisha, India 2

Departmet of Mechanical Engineering, Veer Surendra Sai University of Technology, Burla, Odisha, India 3

Departmet of Electrical Engineering, Indian Institute of Technology, Delhi, India

Abstract: This paper proposes a new methodology to optimize trajectory of the path for multi-robots using improved gravitational search algorithm (IGSA) in clutter environment. Classical GSA has been improved in this paper based on the communication and memory characteristics of particle swarm optimization (PSO). IGSA technique is incorporated into the multi-robot system in a dynamic framework, which will provide robust performance, self-deterministic cooperation, and coping with an inhospitable environment. The robots in the team make independent decisions, coordinate, and cooperate with each other to accomplish a common goal using the developed IGSA. A path planning scheme has been developed using IGSA to optimally obtain the succeeding positions of the robots from the existing position in the proposed environment. Finally, the analytical and experimental results of the multi-robot path planning were compared with those obtained by IGSA, GSA and differential evolution (DE) in a similar environment. The simulation and the Khepera environment result show outperforms of IGSA as compared to GSA and DE with respect to the average total trajectory path deviation, average uncovered trajectory target distance and energy optimization in terms of rotation. Keywords: Gravitational search algorithm, multi-robot path planning, average total trajectory path deviation, average uncovered trajectory target distance, average path length.

1

Introduction

Gravitational search algorithm (GSA) is an effective and efficient alternative approach to the multi robot path planning. Although many algorithms[1, 2] have been proposed and proven to be feasible and efficient for robot motion planning and collision avoidance, classic techniques for path planning problem[3, 4] are general methods like roadmap, cell decomposition, potential fields, optical tweezers and mathematical programming. Many authors have proposed a multi-robot and the single robot path planning problems using different classical techniques[5, 6] , neural network[7] , artificial immune system[8, 9] and heuristic optimization algorithms[10−14] . High time complexity in large problem spaces and trapping in local optima are drawbacks of classic techniques and in many meta-heuristic algorithms. These drawbacks cause the classical techniques inefficient in the various problem spaces. To improve the efficiency of classical methods, probabilistic algorithms like probabilistic roadmap (PRM) and the rapidly-exploring random tree (RRT) are proposed for improving the local optimization problem. Many evolutionary algorithms Research Article Manuscript received date September 3, 2015; accepted December 10, 2015 Recommended by Associate Editor Min Tan c Institute of Automation, Chinese Academy of Sciences and  Springer-Verlag Berlin Heidelberg 2016

like genetic algorithms[1, 15] , particle swarm optimization (PSO)[16, 17] , bee colony optimization[18] and differential evolution algorithm[19] are used in multi-robot path planning problem. Gravitational search algorithm[20−22] is a recent algorithm that has been inspired by the Newton laws of gravity and motion. GSA has undergone a lot of changes to the algorithm itself and has been applied in various applications. At present, there are many variants of GSA[23−26] which have been developed to enhance and improve the original version. The algorithm has also been explored in many areas[21, 27] . For realization of multi robot path planning problem with different goals of the respective robots with GSA[1, 23] by the centralized approach, a fitness function is constructed to determine the next position of the robots that lie on optimal trajectories leading towards the respective goals. The fitness function of the GSA[28] has two main components: first one is the objective function describing the selection of next position on an optimal trajectory based on velocity, and the second one is the constraint on acceleration representing avoidance of collision with other robots and with static obstacles. Path-planning problem considered here is formulated by a centralized approach, where an iterative algorithm is invoked to determine the next position of all the robots satisfying all the constraints imposed on the multiobjective function. The algorithm is iterated until all the

2 robots reach their destination (goal position). The advantages of GSA are: 1) Easy to implement with higher computational efficiency. 2) Few parameters to adjust, but the disadvantages of this algorithm are as follows a) if premature convergence occurs, there will not be any recovery for this algorithm, b) the algorithm loses its ability to explore and then becomes inactive only after becoming convergent. Due to the above difficulties in GSA, further improvements are required for the optimal solution to the complex problem. Here, we consider the improvement of GSA based on the communication and memory characteristics of PSO. Therefore, we called it an improved gravitational search algorithm. The main objective of this paper may be summarized as follows: 1) We study the problem of multi-robot path planning in a clutter environment and formulate the above problem as an optimization problem with constraints. 2) IGSA, a novel approach has been developed to obtained the solution of optimal trajectory path generation for multi robot path planning problem in this article. 3) The proposed algorithm has been applied for multi robot path planning in a clutter and dynamic environment and obtained results are compared with other competitive optimization algorithms like GSA, DE. 4) The performance of the proposed IGSA, has been verified for both simulation of multi-robot path planning as well as Khepera-II environment and results are presented. 5) The performance matrix of the proposed approach is successfully validated with other competitive algorithms in simulation and Khepera-II. In this paper, the modified gravitational search technique has been implemented to determine the trajectory path for multiple robots from predefined initial positions to predefined target positions in the environment with an objective to minimize the path length of all the robots. The result shows that the algorithm can improve the solution quality in a reasonable amount of time and also improves the convergence rate. This paper improves the GSA for improving the global path planning problem of the multi-robots by improving the convergence rate. Finally, the efficiency of the IGSA has been proved through the simulation as well as Khepera environment and the result obtained is compared with other evolutionary computing algorithms such as GSA and DE. The rest of the paper is outlined as follows. Section 2 briefly describes the gravitational search algorithm and its improvement. Formulation of the problem for multirobot path planning has been elaborated in Section 3. Multi-objective optimization problem solving using improved GSA is described in detail in Section 4. Section 5 demonstrates the computer simulation for path planning of multi-robot. In Section 6, the experiment has been conducted in Khepera II environment and finally, conclusions and future work are presented in Section 7.

International Journal of Automation and Computing

2 2.1

Gravitational search algorithm (GSA) Classical GSA

Recently the scientific community has gained interest on GSA. It is a meta-heuristic optimization algorithm inspired by nature which is based on the Newton laws of gravity and the law of motion[27, 30] . The algorithm is intended to improve the performance in the exploration and manipulation capabilities of a population based algorithm by the law of gravity. GSA is based on the two important formulas about Newton gravity laws given by (1) and (2). Equation 1 is the gravitational force equation between the two particles, which is directly proportional to their masses and inversely proportional to the square of the distance between them. But in GSA instead of the square of the distance, only the distance is used. Equation (2) is the equation of acceleration of a particle when a force is applied to it[27, 30] . M1 M2 R2 F a= M

F =G

(1) (2)

where G is gravitational constant, M1 and M2 are masses and R is the distance between two masses, F is gravitational force, a is acceleration. Based on these formulas, the heavier object with more gravity force attracts other objects as it is seen in Fig. 1.

Fig. 1

Newton gravitational force representation

In GSA, each mass (agent) has four characteristics, namely position, inertial mass, active gravitational mass, passive gravitational mass and their performance are measured by their masses. The position of the mass corresponds to a solution of the problem, and the fitness function is used to determine the gravitational and inertial masses[20, 27] . The current velocity of any mass is equal to the sum of the fraction of its previous velocity and the variation in the velocity. Variation in the velocity or acceleration of any mass is equal to the force acting on the system divided by mass of inertia. Agents initialization: Consider a system with N masses in which position of the i-th mass is defined as follows: Xi = (x1i ,· · ·, xdi · · ·, xni ) for i = 1, 2, · · · , N

(3)

P. K. Das et al. / An Intelligent Multi-robot Path Planning in a Dynamic Environment Using · · ·

where xdi is the position of i-th mass in d-th dimension and n is the dimension of the search space. Fitness and best fitness computation: worst(t) and best(t) are defined as follows for minimization case: worst(t) = max f iti (t), p = 1, 2, · · · , N

(4)

best(t) = max f iti (t), p = 1, 2, · · · , N.

(5)

i∈p

i∈p

Gravitational constant (G) computation: The gravitational constant G [27] is computed as follow: G(t) = G0 e

−αt T

.

(6)

Here, T is the maximum iteration, t is the current iteration and α is the weight factor, computed as α = αmax −

αmax − αmin × t. T

f iti (t) − worst(t) best(t) − worst(t) mi (t) Mi (t) = N  mj (t) mi (t) =

(8) (9)

j=1

where Mi (t) and f iti (t) represent the mass and the fitness value of the agent i at iteration t, respectively. Velocity and positions of agents: The velocity and position of the agents are updated as Vid (t + 1) = βVid (t) + adi (t)

(10)

xdi (t + 1) = xdi (t) + Vid (t + 1).

(11)

Here, β is a random number, 0 ≤ β ≤ 1 and an acceleration of the i-th agent at iteration t is computed as adi (t) =

Fid (t) P Mi (t)

k0 is set to N (total number of agents) and is decreased linearly to 1. Fijd (t) is computed using the following equation: Fijd (t) = G(t)(Mpi (t) ×

(12)

Fid (t) is the total force acting on i-th agent calculated as  βFijd (t) (13) Fid (t) = j∈kbest ,j=i

where Kbest is the set of first K agents with the best fitness value and biggest mass, which is a function of time, initialized to k0 at the beginning and decreasing with time. Here

Maj (t) )(Xjd (t) − Xid (t)). disij (t) + ε (14)

Here Xi and Xj are the position vectors of the i-th and j-th agent in d-th dimension, Fijd (t) is the force acting on agent i from agent j at d-th dimension and i-th iteration. disij (t) is the Euclidian distance between two agents i and j at iteration t. G(t) is the computed gravitational constant at the same iteration. While ε is a small constant. Mpi (t) is the passive gravitational mass of the agent i at the instant t. Maj is the active gravitational mass of the agent j at time t, these masses being calculated according to [23–26].

2.2

(7)

Calculation of masses of the agents: Each agent mass is calculated after computing current population fitness as Mpi = Mai = Mii = Mi , i = 1, 2, · · · , N . Here, Mpi and Mai are the active and passive gravitational masses respectively, while Mii is the inertia of mass for t-th agent.

3

Improved gravitational search algorithm based on simplified PSO

Most of the meta-heuristic searching algorithms find their best solutions due to a good balance of exploration and exploitation[28−29] . The exploration capability of the algorithm provides the connectivity relationship of the search space, which helps to find a global optimal solution. The exploitation helps to find the best optimal solutions in the visited domain, which reinforce the convergence capability of local search. So, good meta-heuristic algorithm should improve the exploration ability in the first step and then, in the second step, exploitation ability with increasing of iteration. Therefore, the gravitational search algorithm has been improved to maintain better balance between exploration and exploitation. In GSA, the moment direction of each agent is based on the total force exerted by other agents on it without any communication between the agents. Therefore, improving the searching ability of GSA is based on the communication and memory characteristics of PSO. The PSO updates the velocity using the congnite and social factor. If the social factor is zero, then it acts as local search. The velocity and position update equation of PSO is as follows: Vid (t + 1)P SO = ω × Vid (t) + C1 × φ1 × (xdpbesti − xdi (t)) + C2 × φ2 × (xdgbest − xdi (t)) xdi (t

+ 1)P SO =

xdi (t)

+

vid (t

+ 1)P SO

(15) (16)

where, xi =(xi1 , xi2 , · · · , xiD ) represent the current position vector of the particle i (1 ≤ N ) in a D dimensional search space, Vi = (Vi1 , Vi2 , · · · , ViD ) represents the velocity of the i particle, C1 (C1 = 0) and C2 (C2 = 0) are the acceleration constants, φ1 and φ2 are two random numbers in the range [0, 1]. xpbest is the previous best position of the particle in generation k, xgbest is the previous global best position among all the particles in generation k and ω is inertia weight. When the social factor of PSO is zero, it acts as a local search. So, the velocity update equation of PSO can

4

International Journal of Automation and Computing

be modified as

yi (t + δt)) can be derived from Fig. 2 as follow:

Vid (t + 1)P SO = ω × Vid (t) + C1 × φ1 × (xdpbesti − xdi (t)) Vid (t

+ 1)IGSA = β ×

Vid (t)GSA

+

xi (t + δt) = xi (t) + vi (t)cosθi δt

(20)

yi (t + δt) = yi (t) + vi (t)sinθi δt.

(21)

(17) adi (t)

When δt = 1, the (20) and (21) is reduced to

+ rand×

Vid (t + 1)P SO xdi (t + 1)IGSA = xdi (t) + Vid (t + 1)IGSA .

(18)

xi (t + 1) = xi (t) + vi (t)cosθi

(22)

(19)

yi (t + 1) = yi (t) + vi (t)sinθi .

(23)

The IGSA velocity is formulated using (18), which is formulated and updated using PSO velocity by considering the social factor as zero and GSA acceleration.

3

Problem formulation for multi-robot path planning

The problem formulation for multi-robot path planning is to determine the next position of robots from their existing position in the workspace by avoiding the collision with other robots and obstacles (which are static in nature) in their path to reach at the goal. Multi-robot path planning problem is formulated by considering the set of principles using the following assumptions. Assumptions 1. 1) For each robot the current position (recent position) and goal position (target position) is known in a given reference coordinate system. 2) The robot can select any action in a given time from a fixed set of actions for its motion. 3) Each robot is performing its action in steps until all robots reached in their respective target positions. The following principles have been taken care of for satisfying the given assumptions. 1) For determining the next position from its current position, the robot tries to align its heading direction towards the goal. 2) The alignment may cause a collision with the robots/obstacles (which are static in nature) in the environment, hence, the robot has to turn its heading direction left or right by a prescribed angle to determine its next position. 3) If a robot can align itself with a goal without collision, then, it will move to that determine position. 4) If the heading direction is rotated to the left or right then it is required for the robot to rotate the same angle about its z-axis, if it is same for more than one, and then decide randomly. Consider the initial position of the i-th robot at a time t is (xi (t), yi (t)), the next position of the same robot at a time (t + δt) is (xi (t + δt), yi (t + δt)), vi (t) is the velocity of the robot Ri and (xgoal , yigoal ) is the target or goal position i of the robot Ri . So, the expression for the next position (xi (t + δt),

Fig. 2 Representation of next position from current position of the i-th robot

Consider initially, the robot Ri is placed at the location (xi (t), yi (t)). We want to find the next position of the robot (xi (t + 1), yi (t + 1)), such that the line joining between {(xi (t), yi (t)), (xi (t + 1), yi (t + 1))} and {(xi (t + , yigoal )} should not touch the obstacle in 1), yi (t + 1)), (xgoal i the world map as represented in Fig. 3 and minimizes the total path length from current position to the goal position without touching the obstacles by forming constraint. Then objective function f it1 that determines the length of the trajectory for “n” number of robots is f it1 =

n   { (xi (t) − xi (t + 1))2 + (yi (t) − yi (t + 1))2 + i=1



(xi (t + 1) − xgoal )2 + (yi (t + 1) − yigoal )2 }. i (24)

Fig. 3 Selection of next position (xi (t + δt),yi (t + δt)) from the current position (xi (t), yi (t)) to avoid collision with obstacles

By putting the value xi (t + 1) and yi (t + 1) from (22) and (23) into (24), we obtain

P. K. Das et al. / An Intelligent Multi-robot Path Planning in a Dynamic Environment Using · · ·

f it1 =

n  

 vi (t) +

 (xi (t) + vi (t) cos θi − xgoal )2 + (yi (t) + vi (t) sin θi − yigoal )2 . i

5

(25)

i=1

The multi-robot path-planning is now represented as an optimization problem by minimizing the objective function in (25) with considering the penalty function as the constraints in the objective function. Minimizing the objective function in (25) shows that the robot will follow the shortest distance from the initial point to target point. The constraints here are two types of penalty. The first penalty is to avoid collision between teammates (any two mobile robots), whereas the second penalty is to avoid collision of a robot with a static obstacle. By combining these two penalties a linear fuzzy function is developed for evaluating the obstacle presence in the path. So, the objective function formed based on the fuzzy function is denoted as f itj . ⎧ 1 : d(Oj ) ≤ d(Oj )min ⎪ ⎪ ⎪ d(Oj )−d(Oj )min ⎪ ⎨ −α d(O j )max −d(Oj )min e : d(Oj )min < d(Oj ) < f itj = ⎪ ⎪ d(Oj )max ⎪ ⎪ ⎩ 0 : d(Oj ) ≥ d(Oj )max (26) where α is positive constant, d(Oj ) is the distance between mobile robot and obstacles, d(Oj )max is maximum distance and d(Oj )min is the minimum distance with respect to the obstacle Oj . The path is safe and collision free, when d(Oj ) ≥ d(Oj )max and path is unsafe if, d(Oj ) ≥ d(Oj )min . Thus, mathematically, the optimization problem for obstacles can be formulated as follows. f it2 = maxj=1,2, ··· , N (f itj ).

(27)

Thus, the optimization problem can be represented as follows: f it = f it1 +

λ . f it2

(28)

Here, λ is positive constant. The above optimization problem is to minimize the Euclidean distance between the current position and their goal position is presented by the objective function f it1 and second objective function is a constraint to find the safe path.

4

Multi-objective optimization problem solving using IGSA

In this section, multi-robot path planning algorithm has been proposed using IGSA. The proposed IGSA algorithm is used to evaluate the next positions of every robot by presuming the current positions of robots and speeds as the parameter for optimizing the given multi-objective function. It determines the optimized path from each state to the goal state in a dynamic as well as static environment and robot measures its distance to obstacles with the help

of equipped sensors. The detail of the algorithm for multi robot path planning using proposed IGSA is described below. 1) Initialize: Number of robots (n), gravitational constant (G0 ), cognitive constant (C1 ), inertial weight (w), weight factor of GSA (αmax , αmin ), Maxiter and no of agents (N ). 2) for each robot n 3) while stopping criteria is not met do 4) while iter is not equal to Maxiter 5) Generate agents for each robot and evaluate the fitness value of each agent. 6) Calculate Fijd (t) as the force acting on agent i from agent j at d-th dimension using (14) 7) Calculate total force Fid (t) on i-th agent using (13) 8) Evaluate worst(t) and best(t) using (4) and (5) 9) Compute Mi (t), G(t) of agent by (9) and (6) and update α by (7) 10) Compute the acceleration of each agent using (12) and compute the velocity of each agent using (18) 11) Update the position of agent by (19) 12) iter= iter+1 13) end while 14) Move to updated position. 15) end while 16) end for The agents movement in the search space with the help of the gravity is considered in the proposed IGSA based path planning. The outline of the proposed algorithm pseudo code has been described in Algorithms 1 and 2. Algorithm 1. Path planning using proposed IGSA 1) Procedure IGSA−AGORITHM(xcurri , ycurri , Posvector) 2) Initialize positions of N agents randomly in the population and gravitational constant G0 , C1 , w, αmax , αmin and set Kbest = N 3) for d = 1 to no of do 4) for iter = 1 to do 5) repeat 6) for each agent do 7) Evaluate the fitness of each agent using (28) 8) The total force on an agent i by other agents is Fid (t) which is calculated as:  d d Fid (t) = n i=1,j=i βFij (t) and Fij (t) using (14) 9) Calculate worst(t) and best(t) using (4) and (5) 10) Compute Mi (t), G(t) of agent by (9) and (6)

6

International Journal of Automation and Computing

11) Update the α by (7) 12) Compute the acceleration of each 13) agent using (12) 14) Compute the velocity of each agent 15) using (18) 16) Update the position of agent by (19) 17) end for 18) until Kbest = 1 19) end for 20) end for 21) Update : 22) xcurr−i=xcurr−i+Vid cos θi 23) ycurr−i =ycurr−i+Vid sin θi 24) end procedure Algorithm 2. Pseudo code for path planning Input: (xi (t), yi (t), (xgoal , yigoal ) and vi (t) are the inii tial position, goal position and velocity for robots, 1 ≤ i ≤ n respectively and ∈ is the threshold value. Output: Trajectory of path T Pi for each robot Ri from (xi (t), yi (t) to goal (xgoal , yigoal ). i 1) for i=1 to n do 2) xcurr i ← xi (t) ; ycurr i ← yi (t) 3) end for 4) repeat 5) for robot i = to n do 6) Call IGSA (xcurri , ycurri , posvector); // posvector is the position vector which denotes updated current position of the i-th robot // 7) end for 8) for i=1 to n do 9) Move-to(xcurr i ,ycurr i ) 10) end for until curr i − G ≤∈//curr i= (xcurr i , ycurr i ), Gi = (xgoal , yigoal )// i

5

and DE for same environment and same number of robots like IGSA. The optimal trajectory of the path has been presented in Figs. 8 and 9 for GSA and DE, respectively. The experiment has been conducted using a central version of the algorithm using the fitness function (28) for deciding the next position of the robot. In our experiment, parameters have been described in the Table 1 for simulation and Khepera II environment. Table 1

5.1

Parameters

Values

G0

100

αmin

0.2

αmax

0.4

λ

100

C1

2

C2

0

T

100

ω

0.72

β

0.5

Average total trajectory path distance (ATTPD)

Consider a trajectory path from predefined starting point Sk to the goal point Gk generated by the program for robot Rk in the j-th run as T Pkj . If T Pk1 , T Pk2 , · · · , T Pkj are the trajectory paths generated over J-th runs, then the average total trajectory path traversed (ATTPT) by a robot  Rk is given by jr=1 T Pj ir and the average trajectory path distance for this robot is evaluated by measuring the difference between ATTPT and the ideal shortest path between Sk to Gk . If the ideal trajectory path for robot Rk obtained geometrically is T Pk−real , then the average path distance is given by

Computer simulation

The multi-robot path-planning algorithm is implemented in a simulated environment. The simulation is conducted through programming in C language on a Pentium microprocessor and robot is represented with similar soft-bots of circular shape with different color code. Each robot radius is 6 pixels. Prior to start of the experiment, predefined initial location and goal location for all the robots is assigned. The experiments were conducted with seven differently shaped obstacles and assigned same velocities for each robot at the time of the program run; however, the velocities of each robot are adjusted in different runs of the same program. The initial configuration of the world map in our experimental result is presented in Fig. 4 with ten obstacles and 10 soft-bots, out of 10 soft-bots, five circular shaped with different color represent the initial position of each robot and rest five in rectangular shape represent the goal position of each robot within the same color code. The intermediate steps of movement of the robots are shown in Figs. 5 and 6. The final stage of world maps, where all the robots reached in their predefined goal respectively is shown in Fig. 7. The simulation is also conducted for GSA

Parameter used in the simulation and Khepera

T Pk−real =

j  T Pir . j r=1

Therefore, for robots in the workspace the average total trajectory path deviation (ATTPD) is n  i=1

Fig. 4

(T Pk−real −

j  T Pir ). j r=1

Initial environment for 10 obstacles and 5 robots

P. K. Das et al. / An Intelligent Multi-robot Path Planning in a Dynamic Environment Using · · ·

7

we evaluate the average of UTTDs, and call it the average uncovered trajectory target distance (AUTTD). Fig. 10 shows that by decreasing the velocity, AUTTD takes longer time to converge and gradually terminated with iteration. Again, it is noted that larger the velocity of the robot, the faster falloff in the AUTTD. Fig. 11 shows that, the larger the number of robots, slower the convergence rate. A slower convergence causes the delay in falloff in AUTTD.

Fig. 5 Intermediate state of the world map during execution of IGSA for 5 robots and 10 obstacles after 9 steps

Fig. 8 All robots reached at their respective pre-defined goal in 29 steps by GSA

Fig. 6 Intermediate stage of the world map during execution of IGSA for 5 robots and 10 obstacles after 17 steps

Fig. 9 All robots reached at their respective pre-defined goal in 30 steps by DE

Fig. 7

Five robots reached at their respective pre-defined goal

5.2

Average uncovered trajectory target distance (AUTTD)

Given a goal position Gk and the current position Ck of a robot on a 2-dimensional workspace, where Gk or Ck are 2-dimensional vectors, the uncovered trajectory distance for the robot k is Gk −Ck , where· denotes Euclidean norm. For robots, uncovered trajectory target distance (UTTD)  is UTTD = n i=1 Gk − Ck . For k runs of the program,

Fig. 10 Average uncovered trajectory distance vs. number of stages with variable velocity for fixed number of obstacles=10

8

International Journal of Automation and Computing

The performance analysis was undertaken in the simulation environment and the ATTPT was plotted for n robots, called average total trajectory path traveled (ATTPT) by varying number of robots from 1 to 5 presented in Fig. 12 and generate paths using three algorithms, including realcoded DE, GSA and IGSA. It is noteworthy from Fig. 12 that IGSA possesses least ATTPT in comparison to the algorithms irrespective of the number of robots.

number of robots. Now, the performance analysis was undertaken by comparing the running time over the maximum number of iterations using three algorithms. Fig. 15 provides the time required for robots to reach in their respective goal position by three different algorithms and it shows that IGSA takes less time for robots to reach the destination.

Fig. 11 Average uncovered trajectory distance vs. number of stages with variable number of robots for fixed number of obstacles=10 (constant)

Fig. 13 Average uncovered trajectory vs. number of steps in different algorithms

Fig. 12 Average total trajectory path traversed vs. number of robots with variable number of obstacles for fixed velocity

The performance analysis has been carried out in terms of AUTTD over the number of steps in Fig. 13. It provides the graph between the AUTTD verses number of stages required during the planning of path using three algorithms with number of obstacles = 7 and number of robots = 5. It is apparent from Fig. 13 that AUTTD returns the smallest value for IGSA irrespective of the number of planning steps. The performance of the result has been analyzed by plotting the average total trajectory path distance (ATTPD) with the number of robots as variable in Fig 14. This path is generated by three different evolutionary algorithms such as GSA, DE, IGSA. Fig. 14 shows the result of ATTPD computation, when the number of robots varies between 1 to 5. Here, we observed that IGSA performs better than the other two algorithms as ATTPD is smallest for IGSA in comparison to other two algorithms irrespective of the

target

distance

Fig. 14 Average total trajectory path deviation vs. number of robots in different algorithms with fixed number of obstacles=10

Fig. 15 rithms

Run time vs. maximum iteration for different algo-

P. K. Das et al. / An Intelligent Multi-robot Path Planning in a Dynamic Environment Using · · ·

Finally, the performance of the simulation result is analyzed in terms of number of turns (rotation), by which we can be able to minimize the energy consumption. The number of turns required for three different algorithms for number of robots = 6 is demonstrating in Fig. 16. It shows that IGSA takes a less number of turn than the other two algorithms and energy consumption to reach the destination is less than the other two algorithms. The simulation is only presented for five number of robots, but number of turns are less irrespective of number of robots in the planning scheme of the algorithm.

9

robots of the simulation results for different algorithms are presented in Table 3. Table 3 shows that the number of optimal steps required for IGSA is less than the other algorithm such as GSA and DE. The total number of optimal steps required for IGSA, GSA and DE is 26, 29 and 30, respectively.

Fig. 17 Fitness value of IGSA,GSA and DE for fitness function in (28)

Fig. 16 Number of turn vs number of robots in three different algorithms

The experiment is conducted in the environment shown in Fig.4 by three algorithms for the same fitness function in (28) and same parameters for 30 iterations; the best fitness value for three algorithms is presented in Fig. 17. The fitness value of the robots presented in Fig. 17 indicates that there is no conflict in the next position calculation by the robots, it shows that the best fitness value obtained for IGSA after 26 iterations is 3.638, but that achieved by GSA and DE after 29 and 30 iterations is 4.105 and 4.711 respectively. This presents that IGSA is better than GSA and DE in the terms of avoiding problems at local optima and faster convergence rate. The comparison of fitness function between global and local path planning has been presented in Fig. 18. It shows that the fitness value for local path planning is more irrespective of number of robots than global path planning. So, the global path planning is better than local path planning. The influence of parameters on the performance of multi robot path planning has been elaborated in Table 2. The performance of the multi robot path planning has been analyzed in terms of number of steps, number of turns, ATTPD, AUTTD and execution time. It is observed from the results shown in Table 2 that best settings for constant β, gravitational constant G0 congnite factor C1 and inertia weight ω is β = 0.5, G0 = 100, C1 = 2, and ω = 0.72 respectively. Note that the best setting of the parameters provides better results in terms of number of steps, number of turns, ATTPD, AUTTD and execution time. Number of optimal steps required for different

Fig. 18 Comparison of fitness function between global and local path planning

The result of the experiments performed are summarized in Table 4 in the terms of three performance metrics, namely. 1) total no of steps required to reach in the goal; 2) ATTPT, and 3) ATTPD, have been used here to determine the relative merits of IGSA over the other algorithms for different robots. Table 1 confirms that it outperforms the remaining two algorithms with respect to all three metrics for different robots.

6

Experiment on Khepera II robot

Khepera II (Fig. 19) is a miniature robot (with a diameter of 8 cm) equipped with 8 built-in infrared range and light sensors, and 2 relatively accurate encoders for the two motors. The range sensors are positioned at fixed angles

10

International Journal of Automation and Computing

and have limited range detection capabilities. The sensors are numbered clockwise from the leftmost sensor 0 to sensor 7 and its internal structure (Fig. 20). Sensor values are numerical ranging from 0 (for distance> 5 cm) to 1 023 (approximately 2 cm). The on board microprocessor has a flash memory size of 256 KB, and the CPU of 8 MHz. Khepera can be used on a desk, connected to a workstation through a wired serial link. This configuration allows an optional experimental configuration with everything at hand: the robot, the environment and the host computer. The Khepera II network and its accessories are presented in Fig. 21 for the conduct of experiments.

Fig. 21

Fig. 22 ning

Fig. 19

Khepera network and its accessories

Khepera environment setup for multi-robot path plan-

The Khepera II robot

Fig. 23 Snapshot of intermediate stage of the multi-robot path planning using IGSA in Khepera environment Fig. 20

Position of sensors and internal structure of Khepera II

The initial world map for conducting the experiment in the Khepera II is presented in Fig. 22 with 8 obstacles of different shape and predefined initial state and goal is marked on the map, where different meta heuristic algorithm is applied. Fig. 23 shows the intermediate moment of the robot in the trajectory path towards the goal by respective robot using IGSA. IGSA is implemented in the Khepera-II robot by considering two robots and compared with a different evolutionary computing algorithm as demonstrated in the Fig. 24. It shows better convergence in comparison to the other meta-heuristic algorithm presented in the Fig. 24. Finally, different meta-heuristic algorithm is applied in Khepera environment and result of the trajectory path is presented in Fig. 24.

Fig. 24 Optimal path representation of different algorithm for multi-robot path planning in Khepera environment represented by different color code

P. K. Das et al. / An Intelligent Multi-robot Path Planning in a Dynamic Environment Using · · · Table 2

11

Influence of parameters on performance of multi-robot path planning

Parameters

Number of steps

Number of turns

ATTPD (pixel)

AUTTD

Execution time (s)

Other parameters

G0 =30

26

19

168.45

191.78

65.23

ω =0.72, C1 =2, β=0.5

G0 =70

23

17

148.75

162.45

58.65

G0 =100

21

14

138.67

153.34

52.45 57.89

G0 =130

25

20

152.34

178.56

G0 =150

27

22

175.68

189.67

67.74

ω=0.5

27

21

172.58

167.45

64.69

ω=0.6

25

19

162.93

165.89

60.28

ω=0.68

23

17

145.42

157.63

55.25

ω=0.72

21

14

138.67

153.34

52.45

ω=0.8

29

22

169.83

159.23

65.98

C1 =0.5

31

22

164.68

169.67

66.45

C1 =1

29

19

152.38

162.47

61.89

C1 =1.5

25

17

145.32

156.98

56.76

C1 =2

21

14

138.67

153.34

52.45

C1 =2.5

27

21

157.89

159.76

67.34

β=0.3

29

20

168.56

161.28

66.56

β=0.4

25

19

146.45

156.21

60.45

β=0.5

21

14

138.67

153.34

52.45

β=0.6

27

21

155.69

158.73

59.48

β=0.7

31

23

173.84

162.56

69.29

Table 3 Robot number

G0 =100, ω =0.72,β =0.5

G0 =100, ω=0.72, C1 =2

Description of obstacles presented in Fig. 4

Number of steps

Number of steps

Number of steps

required to goal in IGSA

required to goal in GSA

required to goal in DE

1

17

19

23

2

21

25

29

3

15

23

27

4

26

29

30

5

12

14

17

Table 4

Comparison of number of steps taken, ATTPT and ATTPD of different algorithms for different number of robots Algorithms (steps taken)

7

G0 =100, C1 =2, β =0.5

ATTPT (pixel)

ATTPD (pixel)

Robot number

IGSA

DE

GSA

IGSA

DE

GSA

IGSA

DE

GSA

2

12

16

18

481.3

558.3

624.8

59.9

77.3

105.7

3

15

18

20

930.2

1189.2

1360.7

98.8

132.9

211.6

4

29

21

24

1207.6

1365.1

1428.1

127.5

192.9

216.8

5

21

24

26

1499.2

1523.5

1667.7

202.6

230.4

339.3

Conclusions and future work

An improved gravitational search algorithm was proposed for trajectory path planning of multi-robot in order to find collision free smooth optimal path from predefined start position to end position for each robot in the environment. The result obtained from the experimental work performs is better compared to other algorithms. Comparisons of the performances among different techniques have been carried out. From the simulation and Khepera-II environment, it is observed that the IGSA technique is best over other techniques for navigation of multiple mobile robots. However, in this paper, both the environment and obstacles are static relative to the robots; where as other robots

are dynamic for priority robots. In the future, work will be carried out using dynamic obstacles other than robots such as running vehicle, animals and onboard camera during the multi-robot path planning.

References [1] A. Tuncer, M. Yildirim. Dynamic path planning of mobile robots with improved genetic algorithm. Computers and Electrical Engineering, vol. 38, no. 6, pp. 1564–1572, 2012. [2] Y. Guo, L. E. Parker. A distributed and optimal motion planning approach for multiple mobile robots. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Washington, USA, vol. 3, pp. 2612-2619, 2002.

12

International Journal of Automation and Computing

[3] A. Konar. Artificial Intelligence and Soft Computing: Behavioral and Cognitive Modeling of the Human Brain, Boca Raton, USA: CRC Press, 1999.

[15] G. Chen, L. C. Shen. Genetic path planning algorithm under complex environment. Robot, vol. 23, no. 1, pp. 40–43, 2001.

[4] A. G. Banerjee, S. Chowdhury, W. Losert, S. K. Gupta. Real-time path planning for coordinated transport of multiple particles using optical tweezers. IEEE Transaction on Automation Science and Engineering, vol. 9, no. 4, pp. 669678, 2012.

[16] Y. Zhang, D. W. Gong, J. H. Zhang. Robot path planning in uncertain environment using multi-objective particle swarm optimization. Neurocomputing, vol. 103, pp. 172–185, 2013.

[5] D. Kcymeulcn, J. Decuyper. The fluid dynamics applied to mobile robot motion: The stream field method. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, San Diego, USA, vol. 1, pp. 378–385, 1994. [6] C. Li, B. Bodkin, J. Lancaster. Programming Khepera II robot for autonomous navigation and exploration using the hybrid architecture. In Proceedings of the 47th Annual Southeast Regional Conference, ACM, Clemson, USA, pp. 1–31, 2009. [7] J. Yu, V. Kromov. A rapid path planning algorithm of neural network. Robot, vol. 23, no. 3, pp. 201–205, 2001. [8] P. K. Das, S. K. Pradhan, S. N. Patro, B. K. Balabantaray. Artificial immune system based path planning of mobile robot. Soft Computing Techniques in Vision Science, S. Patnaik, Y. M. Yang, Eds., Berlin Heidelberg, Germany: Springer-Verlag, vol. 395, pp. 195–207, 2012. [9] G. C. Luh, W. C. Cheng. Behavior-based intelligent mobile robot using an immunized reinforcement adaptive learning mechanism. Advanced Engineering Informatics, vol. 16, no. 2, pp. 85–98, 2002. [10] P. K. Das, A. Konar, R. Laishram. Path planning of mobile robot in unknown environment. International Journal of Computer and Communication Technology, vol. 1, pp. 26– 31, 2010. [11] S. Das, A. Mukhopadhyay, A. Roy, A. Abraham, B. K. Panigrahi. Exploratory power of the harmony search algorithm analysis and improvements for global numerical optimization. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, vol. 41, no. 1, pp. 89–106, 2011. [12] Z. W. Geem, J. H. Kim, G. V. Loganathan. A new heuristic optimization algorithm: Harmony search. International Journal of Simulation, vol. 76, no. 2, pp. 60–68, 2001. [13] X. S. Yang. Harmony search as a metaheuristic algorithm. Music-inspired Harmony Search Algorithm: Theory and Applications, Z. W. Geem, Ed., Berlin Heidelberg, Germany: Springer-Verlag, vol. 191, pp. 1–14, 2009. [14] R. Regele, P. Levi. Cooperative multi-robot path planning by heuristic priority adjustment: The stream field method. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, Beijing, China, pp. 5954–5959, 2006.

[17] E. Masehian, D. Sedighizadeh. Multi-objective PSO-and NPSO-based algorithms for robot path planning. International Journal of Advances in Electrical and Computer Engineering, vol. 10, pp. 69–76, 2010. [18] P. Bhattacharjee, P. Rakshit, I. Goswami, A. Konar, A. K. Nagar. Multi-robot path-planning using artificial bee colony optimization algorithm. In Proceedings of the 3rd World Congress on Nature and Biologically Inspired Computing, IEEE, Salamanca, Spain, pp. 219–224, 2011. [19] J. Chakraborty, A. Konar, L. C. Jain, U. K. Chakraborty. Cooperative multi-robot path planning using differential evolution. Journal of Intelligent and Fuzzy Systems, vol. 20, no. 1–2, pp. 13–27, 2009. [20] O. P. Verma, R. Sharma, M. Kumar, N. Agrawal. An optimal edge detection using gravitational search algorithm. Software Engineering, vol. 1, no. 2, pp. 148–152, 2013. [21] T. Eldos, R. Al Qasim. On the performance of the gravitational search algorithm. International Journal of Advanced Computer Science and Applications, vol. 4, no. 8, pp. 74–78, 2013. [22] A. Chatterjee, G. K. Mahanti, P. R. S. Mahapatra. Generation of phase-only pencil-beam pair from concentric ring array antenna using gravitational search algorithm. In Proceedings of International Conference on Communications and Signal Processing, IEEE, Calicut, India, pp. 384–388, 2011. [23] R. E. Precup, R. C. David, E. M. Petriu, S. Preitl, M. B. Radac. Novel adaptive gravitational search algorithm for fuzzy controlled servo systems. IEEE Transactions on Industrial Informatics, vol. 8, no. 4, pp. 791–800, 2012. [24] E. Rashedi, H. Nezamabadi-pour, S. Saryazdi. BGSA: Binary gravitational search algorithm. Natural Computing, vol. 9, no. 3, pp. 727–745, 2010. [25] E. Rashedi, H. Nezamabadi-pour, S. Saryazdi. GSA: A gravitational search algorithm. Information Sciences, vol. 179, no. 13, pp. 2232–2248, 2009. [26] C. Purcaru, R. E. Precup, D. Iercan, L. O. Fedorovici, R. C. David, F. Dragan. Optimal robot path planning using gravitational search algorithm. International Journal of Artificial Intelligence, vol. 10, no. S13, pp. 1–20, 2013. [27] N. M. Sabri, M. Puteh, M. R. Mahmood. A review of gravitational search algorithm. International Journal of Advances in Soft Computing and Its Applications, vol. 5, no. 3, pp. 1–39, 2013.

P. K. Das et al. / An Intelligent Multi-robot Path Planning in a Dynamic Environment Using · · · [28] E. Alba, B. Dorronsoro. The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Transactions on Evolutionary Computation, vol. 9, no. 2, pp. 126–142, 2005. ˇ [29] S. H. Liu, M. Mernik, D. Hrnˇciˇ c, M. Crepinˇ sek. A parameter control method of evolutionary algorithms using exploration and exploitation measures with a practical application for fitting Sovova s mass transfer model. Applied Soft Computing, vol. 13, no. 9, pp. 3792–3805, 2013. [30] E. Rashedi, H. Nezamabadi-Pour, S. Saryazdi. GSA: A gravitational search algorithm. Information Sciences, vol. 179, no. 13, pp. 2232–2248, 2009.

P. K. Das received the M. Eng. degree from Jadavpur University, Calcutta, India in 2010 and has been continuing his Ph. D. degree in Veer Surendra Sai University of Technology (VSSUT), India since 2014. The author has 14 years of teaching experience. Currently, he is an assistant professor in Department of Computer Science, Engineering and Information Technology, Veer Surendra Sai University of Technology (A Unitary Technical University, Established by Government of Odisha), Burla, India. He has published 18 papers in top international journals and conference proceedings. He was the recipient of the IT-Professional-2014 award from CSI for his significant contribution in the area of robotics. His research includes intelligent robotics and vision systems, image processing and pattern reorganisation and machine intelligence. E-mail: [email protected] (Corresponding author) ORCID iD: 0000-0003-4771-197X H. S. Behera received the M. Tech. degree in computer science and engineering from NIT, India (formerly R. E. C., Rourkela) and doctor of philosophy in engineering (Ph. D. degree) from Biju Pattnaik University of Technology, India. Currently, he is an associate professor in the Department of Computer Science, Engineering and Information Technology, Veer Surendra Sai University of Technology (VSSUT) (A Unitary

13

Technical University, Established by Government of Odisha), Burla, India. He has published more than 80 research papers in various international journals and conferences, edited 11 books and is acting as a member of the editorial/reviewer Board of various international journals. He is a proficient in the field of computer science engineering and served the capacity of program chair, tutorial chair and act as advisory member of committees of many national and international conferences. He is associated with various educational and research societies like OITS, ISTE, IE, ISTD, CSI, OMS, AIAER, SMIAENG, SMCSTA etc. His research interests includes data mining and intelligent computing. E-mail: hsbehera [email protected]

P. K. Jena received the M. Tech. degree in mechanical engineering from NIT, India in thermal engineering and pursuing his Ph. D. degree at NIT, India in field of vibration analysis of cracked structures. Currently, he is an assistant professor in the Department of Mechanical Engineering, Veer Surendra Sai University of Technology (VSSUT) (A Unitary Technical University, Established by Govement of Odisha), Burla, India. He has total of fourteen and a half years of academic experience. So far he has published many research papers in international and national journals and conferences. His research interests include navigation of mobile robots and vibration analysis of complex structures. E-mail: [email protected]

B. K. Panigrahi received the Ph. D. degree from Sambalpur University, India. Currently, he is an associate professor of Electrical and Electronics Engineering Department in Indian Institute of Technology, Delhi, India. He is serving as the chief editor of the International Journal of Power and Energy Conversion. His interests include power quality, FACTS devices, power system protection, and AI application to power system and robotics. E-mail: [email protected]