International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 22

ISSN 2229-5518

The State of Art on Navigational Algorithm for Path

Optimization of a Mobile Robot

Hasan Mujtaba*, Gopal P Sinha*

Abstract— Mobile robots are vital for automation industries, surveillance and mapping, hazardous operation like nuclear plants, landmine detection etc. The path of such robots is controlled by a navigational algorithm. Several algorithm have been proposed and tried out for navigation of an autonomous mobile robot (AMR) around the globe .Some of these determine the path which is feasible to reach the destination without collision, while other also tries to optimize .Key parameters of the navigation are distance and time (either or both) to reach the destination or cost of reaching the destination. The prevalent algorithm have used various technique like fuzzy logic, genetic algorithm, artificial neural network, dynamic programming, potential field method, bug algorithm, ant colony optimization etc. Many others have developed the specific algorithms in evolutionary manner stage by stage through various trials. This also includes a number of heuristic based algorithms. This article describes the important features of the current navigational algorithm for optimizing the path of an autonomous mobile robot (AMR).The relative merits and demerits and challenges of each of these have been identified with a view to obtaining a methodology of overcoming the challenges.

Keywords— Autonomous mobile robot, Fuzzy logic, Genetic Algorithm, Artificial neural network, Robot motion Planning

——————————  —————————

1 INTRODUCTION

AVIGATION algorithm deals with path planning and motion control of an autonomous object at various points of the time. Depending on the environment in which a mobile robot is expected to operate, the navigational algorithm has to perceive the terrain and the obstacles around which it has to operate. Therefore various algorithms have evolved for different situation expected to be encountered. Broadly indoor and outdoor situation are fundamentally different. Some situations, mostly indoor face only stationary obstacle. Outdoor robots, however, have to encounter moving objects like vehicles on road, animals etc quite frequently. For navigation of a mobile robot we require (1) perception or sensing of environment, (2) localization and map building, (3) cognition and path planning (4) controlled movement. When an autonomous robot moves in any environment these factors influence the as a sequential navigation process [1] (as given in fig 1) each of them are subject of in-depth study and development. Perception used for sensing the environment where robot has to move and for general visualization of terrain .Collection of data leads to a rough terrain map. Localization and map building is next step in path determination. This process initiates with an input of digital terrain map. This map is used for setting the
orientation of the mobile robot towards destination.

Cognition and path planning refers to the self learning capabilities built in the algorithm. Such algorithms use statistical and expert system modules to utilize the past

experience for drawing the judgment about optimal path amidst several obstacles. The objective and goal of the mission need to be provided to this module to generate the desired path for the AMR. After generating the desired path it is important that robot has a controlled motion to execute the path in stable manner. We generally classify path planning algorithms in two ways (1) Off –line path planning and (2) On line path planning. In the former one information about environments or path are fixed in advance. The off line mobile robots perform only the guided task in a definite or fixed area. In on-line path planning mobile robots move in an unknown environment. Robot gets information through sensor and plan its movement according to data it gets form environment. Using online path planning it can avoid both static and dynamic obstacle coming in its path .For solving path planning several research work have been done like Classical, Evolutionary, and Heuristics approaches. This paper gives a review on techniques like Fuzzy Logic, Genetic Algorithm, Artificial Neural Network, Dynamic Programming, Ant Colony Optimization or Swarm Navigation etc for robotic navigation.

————————————————

• Hasan Mujtaba pursuing Phd degree program in Electronics & communication engineering from Sharda University, India PH-91-9971195795. E-mail: hasan_mujtaba2002@yahoo.com

• Gopal PSinha Prof Mechanical Engineering Deptt in Sharda University, India. E-mail: gopal.sinha@sharda.ac.in

International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 23

ISSN 2229-5518

Motion control

Environment

Perception

2.2 The Application

Peri and Simon in 2005 [2] designed microcontroller based robot using matlab and fuzzy logic rule to optimize best robot results .The advantage of such kind of mobile robot to reach any end position in effective manner whatever its x-y Cartesian plane. Lei & Li in 2007 [3] have incorporate fuzzy logic control with behavior based control of mobile robot path planning. it is a fusion control of two behavior such as navigation towards the target and avoiding obstacle. It is simulation based stage wise work using pioneer model (pioneer 2dx mobile robot) with sonar sensor. This paper is focused on behavior weighting and fusion. The flow chart shows (Fig3) the architecture of behavior.

Path

"Cognition" and path planning

Localization & Map Building

Task/Mission

Mobile Robot

OAB

Fuzzy

Controller

BWFM

Fuzzifier

TSB

Fuzzy

Controller

Position/Map

Rule Base

Fig 1

Basic block of mobile robot path navigation

2 FUZZY LOGIC IN ROBOTICS

2.1 Basic Theory

L.A.Zadeh has given the concept of fuzzy logic in year 1965. Fuzzy logic is based on the concept of fuzzy set or rules. For a mobile robot path planning fuzzy logic is used to design the controller to more crisp or optimal solution .The fuzzy controller has four main components The “rule-base” holds the knowledge, in the form of a set of rules, of how best to control the system. The inference mechanism evaluates which

υo, ωo

Fuzzy

Defuzzifier

Behavior Fusion

υ, ω

Fig 3

υt, ωt

control rules are relevant at the current time and then decides
what should be the input to the robot. The fuzzification
interface simply modifies the inputs so that they can be
interpreted and compared to the rules in the rule-base. The
defuzzification interface converts the conclusions reached by
the inference mechanism into the inputs to the robot as shown in (Fig 2).

Fuzzy Controller

3 GENETIC ALGORITHM IN ROBOTICS

3.1 Basic Theory

Prof John Holland & students of Michigan university has develop genetic algorithm in 1975. It is a nontraditional optimizing technique. GA work with the coding of the parameter set not the parameter themselves. GA search for population of points not a single point. GA always uses probalitic transition rule not deterministic rule.

Reference input

r(t)

Interface

Mechanism

Rule-base

Fig 2

Inputs u(t)

Process

Outputs y(t)

3.2 The Application

Castillo et al in 2006 [6] has described the application of genetic algorithm for offline point to point autonomous mobile robot path planning. Proposed work used to generate the possibility of path and trajectory for a robot in a two dimension grid map. The objective of the robot is to optimize its path on length and difficulty found in navigation. Kala et al in 2009 [7] has proposed mobile robot navigation control in

International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 24

ISSN 2229-5518

moving obstacle environment with genetic and others algorithm for collision free navigation of each robot for survey and data acquisition etc. The algorithm used Genetic algorithm to find out the goal starting from the initial position. By using genetic algorithm they have considered graphical node as a chromosome, in place of taking a predetermined length of bit sequence. In this method they found a random solution out of the given solutions. By considering any two arbitrary points on the path. The path between these two points has been replaced by this new path. If more than one solution is found, the old path is being replaced by the one with the least count of fitness function. S. Parasuraman & Ganapathy [8] has done a simulation based work using genetic algorithm on mobile robot navigation which is implemented on AmigoBot robot. Research has been focused on exploring the algorithm that avoids acute obstacles in the environment. A controller has been designed which is capable of re-planning the new optimum collision free path. This paper is focused on path planning and obstacle avoidance for navigation of mobile robot.

Start

Initialization

Goal heading algorithm

Fig 4
The flow chart shows (Fig 4) the Genetic Algorithm based Dynamic Path Planning Algorithm. In this research, the optimal path for the autonomous mobile robot to move is found from the starting point to goal position without hitting any obstacles in a recognized environment. Mobile robots are capable of escaping from complicated obstacles such as acute

‘U’ shaped obstacles, or obstacles that trap the mobile robot from further movement in complex environment. Zhou Yongnian et al in 2012 [9] has proposed an improved genetic algorithm based on rough sets reduction theory. They optimized the genetic operators which overcome the weakness of the traditional genetic algorithm like huge number of initial population and slow velocity of optimization and convergence. They performed experiments in simple and complex environment. From the simulation result indicated that this method is able to reduce the scale of the population, minimize the searching scope, and improve the velocity of the convergence and optimization for the mobile robot path planning. The entire operation which reduces the above written parameter is shown in flow chart (Fig 5)

Remove redundant point algorithm

Store feasible path algorithm

Establish the initial decision table

Reduce the condition attribute

Reduce the value of attribute

All unexplored path

Yes

Minimum decision rule

Retrieve unexplored path

The set of initial path

Yes

starting point

Selection operator Genetic operation Crossover operator Mutation operator

Compute shortest path algorithm

Path optimization algorithm

Calculation of fitness function

Yes

Any additional algorithm

No Satisfy the ending

condition or not?

Travel to the goal according to the planned optimal path

Yes

Stop

Export optimal path

International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 25

ISSN 2229-5518

Fig 5
The combination of rough sets and genetic algorithm his paper has overcome the faultiness of the large number of initial population and redundant individuals. The algorithm has able to excel the performance in convergence rate and optimization efficiency. Which are the part of further research to improve the path planning for mobile robot in dynamic environments and multi-robot model?

4 ARTIFICIAL NATURAL NETWORK IN ROBOTICS

4.1 Basic Theory

An artificial neural network is a mathematical model based on connection computation. In most cases a neural network is an adaptive system that changes its structure of analysis during a learning phase. Neural networks are used for modeling complex relationships between inputs and outputs.

4.2 The Application

Engedy & Horvarth in 2009 [10] in IEEE International Symposium on Intelligent Signal Processing has describe path planning method to navigate a mobile robot using dynamic behavior of ANN . Back propagation through time algorithm (BPTT) is used for control the motion robot which is able to predict the obstacles in path. In BPTT algorithm there is a feedback process with ANN control done by iteration steps to find out the error between start and end path .The operation of navigation system shown given (Fig 6)

Robot

Observing the

work area Radio

Camera

Robot Sale, Target,

Speed of the wheels

are small taken as a constraint for higher speeds as mobile robot .Velappa Ganapathy in 2009 [11] has given Q – learning algorithm in robotics the research is focused on developing integration of multi-layer neural network and Q-Learning as an online learning robotic controller. The learning process is divided into two stages. The initial stage the agent it will map the environment through collecting state-action information according to the Q-Learning procedure Second stage is the training process involves neural network training which is used to utilize further action on the information gathered in initial phase. Finally Q-learning and trained neural network is used for navigation purpose of mobile robot. The developed algorithm is simulated on MATLAB and implemented on AmigoBot robot. Daniel Oliva Sales et al in 2012 [12] has given an autonomous patrolling system with four intelligent robots that can freely move in an indoor environment to detect intruder. Robots have used navigation system made of an artificial neural network to detect the key features of environment. These features are considered as input for other finite state machine. When an intruder is detected, a broadcast message is sent to all other robots. Using A* algorithm all robos can coordinate with each other to determine the best path to reach the goal position. Then the robots autonomously navigate through this new path to reach the destination.

5 ANT COLONY OPTIMIZATION IN ROBOTICS

5.1 Basic Theory

ACO is proposed by Colorni and Dorigo at ealrly of 1990 which based on swarm optimization in which complex behavior generated from behavior of ants used for determine the shortest path between sources to destination. Its main characteristic have positive feedback search mechanism, distributed computation and the use of constructive heuristic approach. Ants lays chemical trail called the pheromone when they walk the exchange information by this trial Ants go back and forth between the nest and food .During the same period the pheromone led on the shortest path is more than on longer path[13] .The pheromone attract other ant to take the shortest route.

5.2 The Application

Yuwan Cen et al. in 2008 [14] has proposed a path planning approach using ant colony optimization of mobile robots in structured environment. The environment and the path length

Image processing

Application logic

Obstacles

Controller Gateway

Training procedure

are considered in fitness function and computed by neural
network the path nodes were considered as an ant so by using
ant colony optimization algorithm, the best path was found. It
is a simulation based approach through which for path
planning exploration has been done. The method is easy to transform the path planning into penalty function optimization. The function further constructed by neural network which include obstacles and length of path. Finally it is used to find the optimized and safe path. Xin Tan in 2009
Fig 6
This kind of algorithm are useful when the speed of obstacle
[15] artificial potential field (APF) and ant colony optimization
(ACO) algorithm for path planning of mobile robots. Two

International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 26

ISSN 2229-5518

steps have used in this approach (1) free space model of mobile robot is established by using visible graph method and ACO algorithm to find a collision-free path which is the shortest routine through known static obstacles. (2) When unknown obstacles are found in the path APF algorithm is used to generate a real-time local path for avoiding collision. Velappa Ganapathy in 2010 [16] has proposed an improved Ant Colony Optimization algorithm for the purpose of robot navigation. This algorithm is capable of calculating optimum path for different operations like goal-seeking, wall- following and obstacle in the path. Their work shows the usefulness of the ACO algorithm by designing and creating a ACO graphical user interface. This research work is an improve version of earlier works done by Mehtap Kose. It improves the algorithm equations, expand the size of the simulation environment also increase the task capabilities of the robot and testing of algorithm in real world. Qi Zhang and Jiachen Ma et al in 2012 [17] has proposed hybrid-simulated annealing (SA) and ant colony optimization (ACO) algorithm combinedly known as SAACO for path planning of robot. Simulated annealing is a local search algorithm. The robot in unknown environment move as particles like Brownian motion. Using simulated annealing method the robot o moves in the direction of the minimum potential energy using the randomness of disturbance in the environment. ACO is a new combinatorial optimization method which operates to establish environmental model. It finds the effective path and keeps the optimal path. Change with effective information. The Combination of SA and ACO is new approach mobile robot navigation. SA is not effective because the technique is too exploratory and gives a minimum inherent to the discreteness of the cost function. In mobile robot navigation SAACO gives better simulation results. SAACO algorithms select the paths to move towards the destination by avoiding obstacles and increase the speed of the navigation. Fig 7 shows the process of mobile robot navigation. It collects the information from environment by using sensors. After building the map SAACO is used to decide the optimal for navigation by avoiding obstacles.

Environment

Sensor Information

Robot

Fig 7

6 DYNAMIC PROGRAMMING IN ROBOTICS

6.1 Basic Theory

Dynamic programming has been used for deciding the optimal navigation route of an autonomous robot, Enunciated by Bellman, the technique decompose complex problem in to multiple simple problems to be solved in a number of stages
.The stages are linked through recursive equation such the stage wise solution obtained leads to an overall optimal one for the given initial state. The principal of optimality propounded by Bellman states that an optimal policy has the property that whatever the initial state and decision are the remaining decision must constitute an optimal policy with regard to the robot to the state resulting from the first decision. The algorithm leads to the robot to the shortest distance route or lowest cost route to the pre specified destination from the initial location.

6.2 The Application

Sadegh and Woodruff in 2008 [18] has proposed a discrete time algorithm using dynamic programming for multi degree of freedom in a mobile robot to reach the destination through an obstacle with minimum no time steps .The final optimal path guaranteed degree of smoothness and motion constraint like velocity ,acceleration and jerk limit. The algorithm is used a finite number of step avoiding the computation complexity in algorithm. The algorithm is tested on a mobile robot in two dimensional space to show the velocity and acceleration limit of mobile robot. Yuan et al in 2010 [19] has developed a neuro-dynamic programming method for path planning of mobile robot, which is able to record the environment information through neural network and compute the optimal cost between two points . it is a simulation result based work collectively used for optimizing the global planning and real time of local planning in mobile robot .Ku lan su et al in
2010[20] has proposed a path planning experimental method
using dynamic programming to find the minimum distance
between source to target .A mobile robot has been designed of
diameter = 8cm, height=15cm and weight= 1.5 Kg . Using a microcontroller MCS-51 a controller is being designed which

Building Map

Module

Chosen Path

Path choice module (SA+ACO)

contain an obstacle detection module, voice module, wireless RF module an encoder module for calculating distance and a compass module for orientation of robot toward the target.
Mobile robot is controlled by supervisory computer which give the pulses by RF interface and direct the robot towards the target . Using dynamic programming method computer is able to compute the minimum distance between source and

The next state of MR

Move to Goal

Goal

target and compare it with previous trajectory.

7 CONCLUSION

This review paper describes a host of algorithms used for

International Journal of Scientific & Engineering Research, Volume 4, Issue 9, September-2013 27

ISSN 2229-5518

navigation of an autonomous mobile robot from a specified source to a defined destination. A number of techniques have been used in the past for achieving this objective. The approaches ranges from heuristics like fuzzy logic , Neural network ,Neuro-fuzzy , Genetic algorithm , Particle swarm optimization, Ant colony optimization, Potential field method or hard core optimization like dynamic programming. The algorithm have been implemented through software codes using well established tool like Matlab , Simulink ,ANFIS etc.The criteria for achieving optimization has been minimum distance , minimum-time or minimum-cost to reach the destination safely among the obstacles without hitting them. The algorithm is normally driven by local minima’s. In different situation the optimal path can be found in different
manner ranging from wall following, fuzzy system or

[10] István EngedyGábor Horváth,“.Artificial Neural Network based Mobile Robot Navigation” IEEE International Symposium on Intelligent Signal Processing Budapest, Hungary2009

[11] Velappa Ganapathy, Soh Chin Yun, Halim Kusama Joe,“Neural Q-Learning

Controller for Mobile Robot” IEEE/ASME International Conference on

Advanced Intelligent Mechatronics2009.

[12] Daniel Oliva Sales, Daniel Feitosa, Fernando Santos Osório, Denis

Fernando Multi-Agent Autonomous Patrolling System using ANN and

FSM Control” Second Brazilian Conference on Critical Embedded

Systems2012

[13] Jie Dong, Bing Liu, Kaixiang Peng and Yixin Yin, ” Robot Obstacle

Avoidance based on an Improved Ant Colony Algorithm” IEEE DOI

10.11.2009/GCIS.

[14] Yuwan Cen; Choingzhi Song; Nenggang Xie;Lu Wang “ Path Planning

Method for Mobile Robot Based on Ant Colony Optimization Algorithm” IEEE conference2008

[15] Velappa Ganapathy, TitusTang Jia Jie, S.Parasuraman “ A Hybrid Approach

of Path Planning for Mobile Robots based on the Combination of ACO and

APF algorithms by Improved ant colony optimization for robot navigation”

dynamic programming etc. The input are normally from

in Proceeding of the 7

International Symposium on Mechatronics and its

sensor like optical, Infra red sensors, ultrasonic, GPS etc. The algorithm is basically target seeking and obstacle avoiding the robot is driven along the path as decided by navigational routine. To achieve this purpose standard robot like Pioneer2, Amigobot and some lab fabricated robot have been used. Many of these works are grossly macroscopic in term of precision of maps drawn. Future work is required for attaining the accuracy of path followed by the robot. This can be achieve by blending information obtained from differential GPS with the calculated co-ordinate and correcting them stage wise.

ACKNOWLEDGMENT

I wish to thanks Prof Noor E Zahra of ECE Deptt at Sharda University , greater noida for encouraging me to work in the area of robotics.

REFERENCES

[1] P.Raja , S.Pugazhenthi “Optimal path planning of mobile robots A

review”. International Journal of Physical Sciences Vol. 7(9), 1314 - 1320,

23 ,2012

[2] Vamis Mohan Peri ,Dan Simon “Fuzzy logic control for an autonomous

robot” IEEE conference Fuzzy Information processing society, page337-

342,2005

[3] Bin Lei ,Wenfeng Li , “A Fuzzy Behaviors Fusion Algorithm for Mobile

Robot Real-time Path Planning in Unknown Environmen”page173 –

178,2007

[4] Mbaitiga Zacharie, “ Adaptive Fuzzy knowledge based controller for autonomous robot motion control” Journal of computer science 6(10)-

1048-1055, 2010

[5] Bojeiben ,Maissa “ Hierarchical fuzzy controller for a non-holonomic mobile robot” MED page 341-347,2012,

[6] Oscar Castillo , Leorando Trujillo ,Patricia Melin , “.Multi objective genetic algorithm for path planning optimization in autonomous mobile robot” in Springer 2006

[7] Rahul Kala, Dr. Anupam Shukla , Dr. Ritu Tiwari “.Mobile Robot

Navigation Control in Moving Obstacle Environment usingGenetic Algorithm, Artificial Neural Networks and A* Algorithm” World Congress on Computer Science and Information Engineerinin year.

[8] Soh Chin, Yun, S. Parasuraman , Velappa Ganapathy “Dynamic Path Planning Algorithm in MobileRobot Navigation” IEEE symposium on industrial electronics and application2011 .

[9] Zhou Yongnian, Zheng Lifang , Li Yongping “An Improved Genetic

Algorithm for Mobile Robotic Path Planning” 24th Chinese Control and

Decision Conference2012 .

Applications(ISMA10), Sharjah, UAE April 20-22, 2010

[16] Qi Zhang and Jiachen Ma Qiang Liu , “ Path Planning based Quadtree

Representation for Mobile Robot Using Hybrid-Simulated Annealing and

Ant Colony Optimization Algorithm” in proceeding of world congress on intelligent control and automation2012 at china.

[17] Sadegh, NGeorge W. Woodruff “ Time-optimal motion planning of autonomous vehicles in the presence of obstacles” This paper appears in American Control Conference, Sch. of Mech. Eng., Georgia Inst. of Technol., Atlanta,GA Page(s):1830-1835,2008

[18] Yuan Yuan Zhiqiang Cao; Zengguang Hou; Min Tan“Dynamic

programming field based environment learning and path planning for mobile robots this paper appears in Intelligent Control and Automation ” (WCICA),8th World Congressy Page(s): 883 – 887,2010

[19] Kuo-Lan Su Dept. of Electr. Eng., Yunlin Univ. of Sci. & Technol., Yunlin, Taiwan Sheng-Ven Shiau; Jr-Hung Guo; Yi-Lin Liao,“Implement a Path Planning Method for Mobile Robots on the Unknown Environment appears in Genetic and Evolutionary Computing (ICGEC)”Fourth International conference 2010 .