Path planning in uncertain environment by using firefly algorithm

B.K.Patle,Anish Paney,A.Jagaeesh,D.R.Parhi

aDepartment of Mechanical Engineering,CVR College of Engineering,Hyderabad,India

bSchool of Mechanical Engineering,KIIT University Bhubaneshwar,Odisha,India

cDepartment of Mechanical Engineering,Audisankara Group of Institutions,Gudur,India dDepartment of Mechanical Engineering,NIT Rourkela,Odisha,India

Keywords:Mobile robot navigation Firefly algorithm Path planning Obstacle avoidance

A B S T R A C T Autonomous mobile robot navigation is one of the most emerging areas of research by using swarm intelligence.Path planning and obstacle avoidance are most researched current topics like navigational challenges for mobile robot.The paper presents application and implementation of Firefly Algorithm(FA)for Mobile Robot Navigation(MRN)in uncertain environment.The uncertainty is defined over the changing environmental condition from static to dynamic.The attraction of one firefly towards the otherfirefly due to variation of their brightness is the key concept of the proposed study.The proposed controller efficiently explores the environment and improves the global search in less number of iterations and hence it can be easily implemented for real time obstacle avoidance especially for dynamic environment.It solves the challenges of navigation,minimizes the computational calculations,and avoids random moving of fireflies.The performance of proposed controller is better in terms of path optimality when compared to other intelligent navigational approaches.

1.Introduction

Mobile robot navigation is a research area concerns with the effective path planning and obstacle avoidance in physical environment.Today,it is the most leading areas of Science and Technology not only limited to industry but also household areas.Its relevance with the development of Artificial Intelligent Navigational Approaches mentioned in partially known and fully unknown environment in presence of variety of stationary and moving obstacles.The global path planning approaches such as cell decomposition,road map,sub-goal network,Voronoi diagram and potential field method are usually applied for known environment where the information about the environment,goal and obstacle requires to robot.The main advantage of the global path planning is to produce optimal path and to avoid the local minima.However,inability to handle the uncertainty is the major drawback of this technique.In local path planning approach,the robot does not require early information of the environment.Hence it is widely accepted.The several researchers proposed Fuzzy Logic[1],Neural Network[2]and Metaheuristic based Approaches for navigation to handle the uncertainty present in the environment.But,the performance of Fuzzy Logic depends on the selection of the membership function and efficient rule making while neural network depends on the construction of connecting nodes and optimal selection of nodes.In addition to this,many researchers proposed the nature based Metaheuristic Algorithm such as Genetic Algorithm[3],Particle Swarm Optimization[4],Ant Colony Algorithm[5],Bacteria Forging Algorithm[6],Cuckoo Search Algorithm[7]Bee Algorithm[8],Simulated Annealing[9]and many more Hybrid Approaches[10]for solving the problem of MRN due to their capability to search for optimal solution over defined problem space.

The paper presents the application of FA[11]for local path planning in uncertain environment surrounded by variety of static and dynamic obstacles.Here,effective controller has been designed for optimal path generation in presence of moving obstacle and goal.Many researchers have developed numerous approaches to solve moving obstacle problem[12,13]for MRN from last few decades.But,newly FA based approach has been successfully implemented here for MRN over moving obstacle and goal in uncertain environment.Initially,FA is used by Hidalgo et al.[14]to fulfill the multi task of navigation such as path safety,path length and path smoothness in presence of only static obstacle.The mobile robot navigation approach for both single and multiple robot system in concave,zigzag and convex obstacle conditions are demonstrated by Kim et al.[15].Mitic et al.[16]presented the application of FA with vision based mechanism to guide the robot from demonstration but the application is limited to only indoor environment.The approach for robot arm path planning by using Q-learning based FA is presented by Sadhu et al.[17].They implemented Q-learning with FA for balancing the exploration and exploitation while searching for the global optima in the search space.This is done by controlling the randomization parameter and light absorption coefficient.Tighzertet al.[18]have developed the compact FA with minimum cost of computation to control the various operations of the humanoid robot.The developed approach consists the propositions such as elitism strategies,levy movements and opposition-based learningwhich reducesthecomplexityof attraction model and achieves the optimization with minimum of attractions.The application of FA for underwater robot navigation is provided by Liu et al.[19]in presence of static obstacle.They introduced an autonomous flight model to avoid instances of invalid flight although it is unable to deal with marine situation which is mostly dynamic.To solve the problem of aerial navigation Wang et al.[20]presented the new form of Firefly Algorithm for path planning of Uninhabited Combat Air Vehicle(UCAV).They have provided “Modified Firefly Algorithm”to avoid the threat areas and to minimize the fuel cost during navigation of UCAV in complicated battle field environment.The modified form of FA is also presented by Patle et al.[21]for robot navigation in complex environment using probability model.The FA with artificial bee colony algorithm as a hybrid approach is presented by Abbas et al.[22]for trajectory tracking of a nonholonomic differential two wheeled mobile robot.Brand et al.[23]have compared the performance of FA with Ant Colony optimization for solving the path planning problem of robot and they observed that the path obtained by the FA is optimal in terms of path length and computational cost.The ability to self-plan,self-adaptation and selforganize of FA is used by various researcher for various optimization problem such as fault detection in robot,economic emission dispatched problem,reliability-redundancy optimization,mixed variable structural optimization problem,cooperative networking problem,combinatorialoptimizationproblem,learningfrom demonstration problem and many more.

The paper is organized by the Firefly Algorithmwith its basics in Section 2 and objective function formulation for mobile robot in Section 3.The Section 4 and Section 5 describe the simulation results and experimental results respectively.The comparisons between the simulational result and experimental result has been shown in Section 6 and finally conclusion with future scope explained in Section 7.

2.Firefly algorithm

In 2008,Yang[11-24]presented the nature based metaheuristic algorithm inspired by flashing behavior of fireflies.It is new artifi cial intelligence approach is popularly used in every field of optimization and autonomous system.It evolved from the flashing behavior of the fireflies present in the atmosphere.Bioluminescence[25]is the process by which firefly emits the light and the light is used as signal system to attract other fireflies.The attraction of both male and female firefly depends on the rhythm of flash light,rate of flashing of light and amount of time for which the flash of light is observed.The flashing light of fireflies is used as the objective function which is to be optimized and used to formulate new optimization algorithm.The attraction of one firefly towards the other is possible when the other possessing the higher light intensity[26]and this is the basic concept of working of FA.The three basic rules of firefly algorithm are mentioned below.

1.All fireflies are unisex and are attracted to each other regardless of their sex.

2.The degree of attractiveness of a firefly is proportional to its brightness and thus for any two flashing fireflies,the one that is less bright will move towards to the brighter one.The distance between two fireflies will be less for the more brightness.The random movement equals the brightness of the flashing if reflies.

3.The objective function is generated for evaluating the brightness of fireflies.

Let,β（r）=Attractiveness of firefly,β0=Attractiveness of firefly at r=0,Coefficient of light absorption,xi=Position of first firefly,xj=Position of second firefly,i=first firefly,j=second firefly,=current value of ithfirefly at kthdimension,rij=distance between xiand xj,d=dimension,t=iteration,r=random number,α=randomization parameter.

Then,

Attractiveness of the fireflies is given by,

Distance between two fireflies is,

Movement of one firefly towards the brighter is,

The pseudo code for FA is given in Fig.1 to understand the execution.(See Fig.2),(See Fig.3).

3.Objective function formulation using FA

In MRN problem,flashing behavior of firefly is used to find out the optimal path planning when the robot is surrounded by static and dynamic obstacles.The effort has been made here to develop effective path planning for mobile robot using FA in appropriate time.Path planning for mobile robot is the design of optimal parameters to meet certain performance requirement according to the objective which includes challenges such as obstacle detection,obstacle avoidance,to face trap like situation,to avoid random walk,optimal path generation,etc.While moving in the environment,the information about the surrounding is provided by the sensors which are mounted on robot,helps the robot to localize its position in unknown environment.This sensor provides the information about the shape,size,and position of the obstacle and by using this sensory information,robots move towards goal without collision to obstacle.To obtain the optimal and safe path planning for mobile robot is the primary aim of the present study.Initially,navigational path optimization problem is converted into the minimization problem and later expressed as objective function based on the goal and obstacle position as desired parameter with the implementation of FA.The localization of globally brighterfirefly that is chosen in each iteration and the robot moves to these location in series during the process of execution.If there is no obstacle found in the path of mobile robot during the execution,then the robot directly finds the goal position without using the artificial intelligent mechanism.The following are the key objectives of the FA controller:

Table 1 Parameters for FA.

i.To design and develop the effective path planning algorithm to avoid obstacle present in the path.

ii.To avoid random moving of the robot in its environment as per the time optimality.

iii.To produce the uniqueness in simulation and experimental result.

iv.To give better performance when compared with the other navigational controller.

The advantages of the FA for optimization problem is gives as follows

i.It can handle both linear and nonlinear problems,and multimodel problem.

ii.The convergence speed is very high.

iii.The cost of computation is low.

iv.It is easy to adopt with other technique to form hybrid approach.

v.It does not require a good initial solution to start its iteration process.

3.1.Obstacle avoidance behavior

Navigation is difficult task for any mobile robot when the environment is uncertain.The uncertainty may be about changing condition of obstacle or goal.The obstacle present in the environment may be varying in shape and size.For effective navigation in uncertain environment,robot requires obstacle avoidance mechanism to avoid collision with obstacles.The FA produces the number of random fireflies near the obstacle and the brighter firefly is selected among the group based on brightness.The brighter firefly is selected in such a way that,it must be at the maximum safe distance from the nearest obstacle.The robot occupies the position of the newly selected fireflies and the procedure for searching for the next brighter firefly starts till the safe and optimum path generates.The best firefly is selected by using Euclidean distance between the firefly and the closest obstacle which is shown by the equation(4).

Let,Dfois the Euclidean distance between position of firefly with the nearby obstacle,xfiand yfiare the x and y coordinates of the firefly position respectively,xOand yOare x and y coordinate ofobstacle position respectively.

Table 2 Variation in path length and obstacle avoidance behavior when change in control parameters.

Then,Euclidean distance is

For the complex crowded environment,the selection of the nearbyobstacle ismust for the optimum path generation and hence the distance between the neighboring obstacles is calculated by the equation(5).

Let,DROis the distance between the robot to nearby obstacle,xOnand yOnare the x and y coordinates of the nearby obstacle respectively,xRand yRare the x and y coordinates of the robot position respectively.

Then the distance between the robot and nearby obstacle is presented as

3.2.Goal searching behavior

Here,the brighter firefly is selected from the group of randomfireflies in such a way that it has the maximum distance from the obstacle(mentioned in the obstacle avoidance behavior)and minimum distance of same firefly from the goal.This is the continuous searching process for brighter firefly over the time till it completely finds the goal.The position of the current brighterfirefly must be always at minimum distance from the goal position.The Euclidean distance between the goal and firefly is shown by equation(6).

Table 3 Simulational path length comparisons between other AI technique and FA.

Let,Dfgis the minimum Euclidean distance between firefly and goal position,xgand ygare the x and y coordinates of the goal position.

Then,the distance between fireflies with goal is

From the study,the obstacle avoidance behavior and the goal searching behavior comprises to formulation of objective function of fireflies for path planningoptimizationproblem is represented as follow

As per the objective function formulation,the environment is considered with ‘n’obstacle,and represented as O1,O2,O3,O4… Onand their coordinate positions are(xo1,yo1),(xo2,yo2),(xo3,yo3),(xo4,yo4),……(xon,yon).The number of obstacle is detected by the robot when it comes in threshold range of sensor during navigation in environment is os.When the number of fireflies(fi)lies away from the obstacle,then the value of minon∈will be huge in objective function and when the filies closer to goal,then the value ofwill be reduced.Therefore,the study of objective function by using FA comes under the minimization optimization problem which helps to find optimal path planning for mobile robots in uncertain environment.Here,K1is the fitting parameter which decides the path safety;K2decides the maximum and minimum path length of the navigation.When,the value of K1is maximum then the robot can safely avoid the obstacle without hitting the boundary however,the chances of collision to obstacle increases with decrease in value of K1.Similarly,maximum value of the K2minimizes the path length and minimumvalue of K2maximizes the path length.Hence,the proper selection of control parameter over the local minima problem decides the success of objective function for robot path planning.Trial and error method has been used for controlling the parameters of objective function.

3.3.Steps involved in the FA for MRN

1.Initialize the robot,goal and obstacle position.

2.Movement of robot towards the goal till it detects the obstacle.

3.If the obstacle exists in the path,then activate FA.

4.Generate the population of fireflies randomly.

5.Select the brightest firefly among the population to fit equation(7).

6.Move robot towards the current brightest firefly position.

7.Repeat the step 2 to 6 till robot avoids the obstacle.

Fig.4 shows the complete architecture of the proposed FA based controller for MRN.

4.Simulation result

To check the optimality of present FA based controller in terms of path length and time required for navigation,the variety of environment has been tested on simulation software MATLAB(R2008).The simulation experiment performed on the PC with I3processor(3 GHz),4 GB RAM,500GB hard disk,windows 7(64 bit)OS,NVDIA(1 GB)graphics card.

Table 4 Specification of Khepera-II robot.

To develop the efficient FA controller,proper selection of the parameter is must according to problem domain.Randomization parameter(α),Light absorption coefficient（γ）and attractiveness(β)are the controlled parameters which decide the functioning of FA as shown in Table 1.These parameters are considered for problem analysis between the ranges of 0-1.To minimize the computational efforts,the number of fireflies and maximum generation are considered for MRN problem.The series of experiments have been conducted by varying control parameters(γ，α，β )with step of 0.05,whereas number of fireflies with step of 5.The optimal control parameters are finalized after performing optimization for 50 times and it is observed when γ=0.5，α=0.5 andβ=0.2.The obtained control parameters are considered as initial position of the robot during obstacle avoidance.The simulation results have been tested in 2D space of 100 cm by 100 cm square background in presence of variety of static and dynamic obstacles.The navigation of mobile robot in static environment is shown in Fig.5 and Fig.6.The path obtained by robot is optimal and smooth in sense of making safe distance with obstacle in complex environment.By using FA based navigational strategy mobile robot can easily avoid the two moving obstacles in dynamic environment in Fig.7.The environment with moving goal has been tested successfully in dynamic environment as shown in Fig.8 where robot follows the goal till it reaches.

The navigational results due to variation in control parameters on path planning and obstacle avoidance are checked by trial and error method.The Fig.9 shows the variation in path length due to change in parameter such as N andβ.During the test,the values of parameters like r=0.5 andα=0.5 are considered.

From the Table 2,when the parameters N andβare 50 and 0.2 respectively then the path is optimal and robot avoids obstacle safely.The variation inparameter N in range of 40-60 and variation in parameter ofβ.from 0.2 to 0.3 gives the nearby optimal solution and avoids the obstacle.The comparison of the proposed FA with other intelligent controller is shown in Figs.10-15 over same environmental setup.While comparing with other intelligent approaches,the path length saved by using FA is mentioned inTable 3.The graphical comparison between the proposed approach and other intelligent approach based on path length is shown in Fig.16.

5.Experimental analysis

The feasibility of the FA based decision controller is demonstrated in real time environment in presence of variety of obstacles.For navigational purpose,the Khepera-II robot as shown in Fig.17 is used.Khepera-II robot has eight infrared sensors which are capable to emit and receive the signals.These sensors must be kept in a circular fashion around its body and sensors can measure distance in a short range of 1cm-5 cm.The technical specification of Khepera-II robot given in Table 4.The C++programming language is used for coding the program of MRN during the experiment.The GPS based localization technique is used for path planning.The Petri-Net model is applied to avoid collision between the robots.During the experiment,following assumptions are considered for navigation as

1.The work space is used as plane ground for robot.

2.Inertial effects are neglected.

3.Navigation of mobile robot is without sleeping.

4.Obstacle and goal position is fixed and can modify for different environmental condition.

During the experiment,as shown in Fig.2,the robot directly reaches to goal when there is no obstacle present in the path of the robot and there is no need of FA based decision mechanism.However,the FA based decision mechanism activates when the obstacle comes in the path of robot as shownin Fig.3.The proposed controller performs well in terms of obstacle avoidance and optimal path planning in single mobile robot system as shown in Fig.18(a),(c)and multiple mobile robot system in Fig.18(e).

6.Experimental VS simulational analysis over similar environmental setup

In order to investigate the functioning of the proposed FA based controller on the basis of path length and time,the uniform environmental setup is considered for experimental and simulational analysis.Foranalysis of single and multiplemobile robot systems 20 and 10 trials are taken respectively which is shown in Figs.19 and 20.From the Fig.18 and Tables 5-8,it is clear that the simulation path is optimal and time requires for navigation is lesser as compared to experimental path.The obtained results are almost same for simulational and experimental set up and the percentage of deviation is less than 5.7%.

Table 5 Experimental path length versus simulational path length for single robot system.

Table 6 Experimental time versus simulational time for single robot system.

Table 7 Experimental path length versus simulational path length for multiple robot system.

Table 8 Experimental time versus simulational time for multiple robot system.

7.Conclusion

The approach of efficient navigation has been developed using FA in uncertain environment in presence of variety of static and dynamic obstacle.The proposed FA based controller gives the optimal path with effective obstacle avoidance mechanism for single and multiple mobile robot system in minimum time at low computational cost.It also shows the greatest commitment when environment consist of moving obstacles and goal.The simulational and experimental results are nearby same and the percentage of deviation is less than 5.7%.On comparison with the other intelligent approaches such as Neuro-Fuzzy,Genetic Algorithm and Fuzzy-Neural,it has been observed that the path obtained by the FA controller is short and more than 6%path length can be saved.

Future scope

The proposed work can be applied for the navigation of the underwater and the aerial robot.It can also be used for path planning of autonomous car in complex environment.

Acknowledgement

This work is not funded and supported by any organization.