Printer Friendly

Intelligent path planning with A* search algorithm.


In order to achieve a high degree of autonomy and robustness in industry, an intelligent mobile robot should be able to navigate its environment, build or update map, plan and execute actions, and adapt its behavior to environmental changes. It should also be able to cooperate with others and human operators to achieve intelligence system performance. For a number of differences navigational control strategies have been adopted by various parties. Consider a highly automated factory where mobile robots pick up parts and deliver them to assembly robots. The robots must find their way to parts, pick them up, and move to the assembly stations. All these motions have to be executed without colliding with Objects and other robots. Without a motion planner for the robots and arms, human operators have to constantly specify the motions. An automatic motion planner will relieve the operators from this tedious job and enable them to control at a supervisory level. In turn, this increases efficiency by eliminating human errors. The need for collision avoidance and efficient motions leads to the problem of motion planning. There are 2 approaches for the Path planning, global Path Planning and local Path Planning. In real world applications of mobile robots both global and local maps are used. Global maps should decompose hierarchically into local maps to allow easy movement between the two. One obvious advantage of this structure is a reduction in the use of local memory without loss of detail because the computer in the robot has to store only the global map and a detail local map for the area it is in not a detailed map of its whole universe. This assumes that local maps can be retrieved from secondary storage, or a host computer, at any time.

Path Planning

Global Path Planning

Road map

Thy roadmap method consists of capturing the connectivity of the robot s free space. In a network of one dimensional curve, called the roadmap, a subpath combined in the roadmap and a subpath connector the roadmap to the goal configuration. Various methods based on this general idea have been proposed. They compute different types of roadmaps called visibility graph, Voronoi diagram. A visibility roadmap is obtained by generating all line segments between pairs of obstacle region vertices. Any line segment that lies entirely in the free space is added to the roadmap. When a path planning is given the initial position and goal position are also treated as vertices (in other words, they are connected to other vertices, if possible). This generates a connectivity graph that can be searched for a solution. The naive approach to constructing this graph takes time. The sweep-line principle can be applied to yield a more efficient algorithm.

Voranoi diagram

Another roadmap method calls retraction or Voronoi. This diagram is the set of ah the free configurations whose minimal distance to the obstacle region. The advantage of this diagram is that it yields free paths which tend to maximize the clearance between the robot and the obstacles. When the obstacles are polygons, the Voronoi diagram consists of straight and parabolic segments.

Cell decomposition

Cell Decomposition methods are perhaps the motion planning methods which have been the most extensively studied so far. They consist of decomposing the robot's free space into simple region called cell, such that a path between any two configurations in a cell can be easily generated. A non directed graph representing the adjacency between the cells in then constructed and searched. This graph is called the connectivity graph. Its node is the cell extracted from the free space and two nodes are connected by a link if and only if the two corresponding cells are adjacent. The outcome of the search is a sequence of cells caned a channel.

Local Path Planning

The reduction of the calculation time for planning is decisive for the controlling concept. Between the planning steps a discrepancy occurs between the present obstacle knowledge and last calculated global plan. These discrepancies have to be bridged by the local planner until the new global plan is calculated. This leads to a different consideration of the online in comparison to the off-line concept. Demand can be made for the local planner depending on the discrepancy. This study assumes that the discrepancy is relatively small. This leads to the demand that the local planner should not have a complex navigation strategy when having a fast execution in mind.

A* Search algorithm

The environment has to be represented in a grid, the size and resolution of which are usually determined by speed and memory limitations. Each goal square is given a distance transform value of 0. The minimum cost of moving to each square from the minimum of its neighbors is calculated in a series of forward and reverse raster operations. This section of the algorithm terminates when the values in each square no longer change after a raster operation in each direction. The required path is then a simple gradient descent from the robot's current square to the nearest goal. First the program sets ah the cells in the grid to initial values. Goal and obstacle cells have constant values throughout the computation. Since the cost of traveling from the goal to the goal is zero, the goal cell is always set to 0.0. Since traveling through obstacles is not normally desire. We discourage this by setting the cost at obstacle cells to an arbitrarily large value called Big-cost. After setting the cells to initial values, the program repeatedly scans through the grid looking for cells it can reset to lower values. The lower cost is computed by looking at neighboring cells and using an estimate of travel cost from the adjacent cells to the current cell. For orthogonal adjacent cells the estimate is 1.0, and for diagonally ad sent cells it's This is just the distance from the center of one cell to the center of the next, assuming each cell measures one unit on a side Note that if the cost estimates were multiplied by the resolution of the grid the values at each cell would reflect the true distance to the goal.

The paths used in this system are called virtual paths. Most path planner abstracts the search space to a graph of possible paths. This graph is then search to find the shortest path. This approach arises naturally in a learning environment, where a robot may have traversed several paths to map the world.


From figure the solution X to Y has cost:

Path 1: from X [right arrow] A = 5 m.

from A [right arrow] S = 2 m.

from S [right arrow] Y = 3 m.

Path 2: from X [right arrow] A = 5 m.

from A [right arrow] B = 4 m.

from B [right arrow] Y = 6 m.

Path 3: from X [right arrow] B = 3 m.

from H [right arrow] A = 4 m.

from A [right arrow] S = 2 m.

from S [right arrow] Y = 3 m.

Path 4: from X [right arrow] B = 3 m. from B [right arrow] Y = 6 m.

so the shortest cost from X to Y is path number 4, which is 3+6 (X[right arrow]B[right arrow]Y) equal 9m.


The geometric map building, the resulting map is intelligence to human operator. This allows for easy supervision of the robot operation by the operator. Occupancy grid is usually read from a file at startup time. Occupancy grids are easy to update if the robot discovers a discrepancy. Suppose, for instance, that the robot discovers a new obstacle just to the north of itself. This paper introduces intelligent path planning with A* search algorithm, which use to generate the most efficient path to goal.


This research from Measurement and Mobile Robot Laboratory (M&M-LAB) was supported by Faculty of Engineering, Srinakharinwirot University.


[1] Andrew C.Staugaard,Jr, 1987, Robotics and AI, An introduction to Applied machine Intelligence, Prentice Hall, Inc., Englewood Cliffs, N.J. pp 19-67.

[2] H.R.Everett, 1995. Sensors fur mobile Robot Theory and Application, A K Peters. Ltd, Wellesley, Massachusetts pp 279-304.

[3] M.Vidyasagar, Mohan Trivedi 1991, Intelligence Robotics Proceeding of The International Symposium on Intelligent Robotics January 2-5, 1991, Bangalore, INDIA.

[4] C.A. Czarnecki and T. W. Rotten, "Evolutionary Motion Planning for Mobile Robots," ECML Workshop on Intelligent Robotics, Greece, 25-29 April 1995.

[5] C. A. Czarnecki and T. W. Routen "Evolutionary Motion Planning," Journal of Microcomputer Applications, 1995.

Surachai Panich

Srinakharinwirot University, Thailand

COPYRIGHT 2010 Research India Publications
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2010 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Panich, Surachai
Publication:International Journal of Computational Intelligence Research
Date:Oct 1, 2010
Previous Article:Prediction of performance and emission characteristics of diesel engine fuelled with biodiesel using ANN.
Next Article:Binary sequences design using MGA.

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |