Abstract- In this paper, the ant colony optimization (ACO) metaheuristic is propod to solve the mobile robot path planning (MRPP) problem. In order to demonstrate the effectiveness of ACO in solving the MRPP problem, veral maps of varying complexity ud by an earlier rearcher is ud for evaluation. Each map consists of static obstacles and walls in different arrangements. Besides that, each map has a grid reprentation with an equal number of rows and columns. The maps have a starting point and a destination as well. At the beginning of the problem, the ants (reprenting the mobile robot) are placed at the starting point. The ants would then have to find their way towards the destination whilst avoiding all the obstacles and walls along the way. The ants should also do so with the shortest distance possible. The performance of the propod ACO metaheuristic is tested on a given t of maps and the results are compared with tho reported in the literature. The performance of the propod ACO metaheuristic is found to be better than the result reported in the literature.
I. INTRODUCTION
The automation phenomenon has grown rapidly since the last century, influencing our daily lives at the same time. As of late, autonomous mobile robots have become a major part of this trend. The mobile robots can be ud in a wide variety of applications. For example, in the manufacturing industry, mobile robots can be ud to transport items and tools from one station to another. In the aerospace industry,
mobile robots can be ud for the purpo of planetary exploration, where they can be ud to collect environmental data, rock or soil samples and many more. For home application, a mobile robot can be ud as a mobile vacuum cleaner. This function is achieved with the mobile robot navigating itlf effectively and efficiently around an area in the hou and removing dirt at the same time.
One of the most important tasks in the control of a mobile robot is path planning. Path planning is defined as follows [1]: “Give a description of the environment to a robot, plan a path between two specific locations. The path must be collision-free (feasible) and satisfied the certain optimization criteria”. In other words, for a given environment with obstacles, a collision-free path is to be generated. According to Castillo and Trujillo [2], the
Manuscript received January 31, 2009.
Yee Zi Cong was with Monash University, Sunway Campus, 46150 Bandar Sunway, Malaysia. (e-mail: ).
S. G. Ponnambalam is with the Monash University, Sunway Campus, 46150 Bandar Sunway, Malaysia (phone: +60-3-55146203; fax: +60-3-55146207; e-mail: ash.ed
< ).
mobile robot should also show a level of intelligence. Hence, the possible paths should be optimized with respect to some criteria which are important to the robot, the terrain and the problem in question, e.g. minimum distance possible or minimum number of turns possible. This is to ensure that the minimum amount of energy and time are ud by the robot in travelling from the starting point to the destination.
The path planning problem is further divided into two categories [3] – global path planning and local path planning. In global path planning, it is required that environment should be completely known and the obstacles should be static. The mobile robot generates a complete path from the starting point to the destination before it starts moving. On the other hand, local path planning enables a mobile robot to plan its path as it is moving in the environment. In other words, this means that the mobile robot will be able to produce new paths in respon to any changes in the environment.
In this project, an ACO metaheuristic is propod to solve the mobile robot path planning problem bad on the global path planning approach. The ACO metaheuristic is to determine the shortest distance possible for a mobile robot in travelling from the starting point to the destination. The perfor
mance of the propod metaheuristic is evaluated with a t of maps that has been obtained from the rearch performed by Sedighi et. al. [3].
The robot path planning problem is a subt of a larger t of problems related to scheduling and routing and is known to be NP-hard (NP-complete) [3]. Many rearchers have propod evolutionary approaches to solve the path planning problem. Since the focus of this rearch is to propo an ACO metaheuristic for MRPPs, only the relevant literatures are included in this ction.
A. Literature Review
Sedighi et. al. [3] utilized the genetic algorithm (GA) in solving the path planning problem. A genetic algorithm is an evolutionary optimization method bad on the idea of simulated evolution. They conducted their rearch on 8 maps, each having a grid reprentation and an equal number of rows and columns. Besides that, each map has static obstacles and walls in different arrangements. As their program works bad on the concept of local path planning, they suggested that a method to address global path planning could be developed as part of the future work to be done. The performance of the global path planning algorithm should then be compared with that of the local path planning algorithm.
Mobile Robot Path Planning using Ant Colony Optimization
Yee Zi Cong and S. G. Ponnambalam
2009 IEEE/ASME International Conference on Advanced Intelligent Mechatronics Suntec Convention and Exhibition Center
Singapore, July 14-17, 2009
The MRPP problem has also been tackled using the particle swarm optimization (PSO) metaheuristic by Lei et. al. [4]. In their rearch, the model of the vertexes of the obstacles prent in the environment is constructed in the arch space, leading to the existence of constrained path functions between the starting and the finishing points. The modified PSO algorithm needs to optimize the constrained path functions above to obtain a satisfactory collision-free path between the start and the finish points.
根雕佛国Castillo and Trujillo [2] designed a multiple-objective GA-bad (MOGA) offline point-to-point path planning optimization method for mobile robots. Its objective is to generate feasible paths for a holonomic robot to enable it to move from one point to another from the start to the finish with minim
um path length and difficulty. This is to be performed across an environment that is reprented by a 2-dimensional grid. The terrain consists of obstacles that are to be avoided through the utilization of the path planning algorithm. Castillo’s MOGA is bad on the concept of Pareto optimality. They compared the performance of the conventional GA (one criterion; minimum path length) with that of the MOGA (two criteria; minimum path length and difficulty).
Garro et. al. [5,6] tackled the mobile robot path planning problem by using an evolving ACO method. His rearch focud on designing a variant of the ACO by evolving some parameters of the ACO using GAs, making it an ACO-GA optimized path planning algorithm. Performance comparisons were performed between the conventional ACO method and the ACO-GA method.
Pratihar’s [7] rearch focud on combining the concepts of a fuzzy logic controller and GAs for the purpo of a time optimal, obstacle-free path generation for mobile robots. In his rearch, the fuzzy logic controller is ud to find obstacle-free paths from the start to finish, locally. GA is then ud for the purpo of optimizing the paths by finding optimal/near optimal locations along the obstacle-free paths.
Li et. al. [8] propod a hybrid GA to optimize the paths that have been planned by a mobile robot. T
he crossover and mutation operations in his GA are performed bad on the lf-adapting algorithm instead of the adjustment algorithm. They suggested that including noi in path planning simulations is to replicate real-life situations. Afsar et. al. [9] conducted a rearch on the path planning optimization of a mobile robot bad on GAs and morphological image pre-processing of the terrain (arch space). According to them, GAs have the tendency of arching for optimal paths without considering the location and distribution of obstacles in the given arch space, therefore a long time may be spent before a feasible path could be found. Their method of overcoming this disadvantage is by the implementation of morphological image pre-processing of the arch space.
The objective of this rearch is to propo an ACO metaheuristic for the MRPP problem and to evaluate its performance over the genetic algorithm propod by Sedighi et. al. [3] using their maps.
II.THE ACO METAHEURISTIC
ACO is influenced by the behaviour of ants in finding paths from their colonies to the food source. It is also bad on the concept of stigmergic communication, whereby stigmergy means “interaction through the environment”. For example, there is an indirect interaction between two individuals when one of them modifies the state of the environment and the other responds to this change at a later time.财务简历工作经验模板
A.Pheromone Trails and Heuristic Information
As ants are almost blind, they move in random directions in the initial stages. Pheromones are deposited on the ground as they move around. A pheromone is a type of chemical that stimulates a natural behavioural respon to another member of the same species. The subquent ants would choo a path bad on the amount of pheromones prent on all the possible paths from the starting point to the destination. The shorter a path is, the greater the intensity of its pheromone trail and vice-versa. Subquent ants are more likely to choo a path with greater pheromone trail intensity. The ants would continue reinforcing the ideal path by depositing more pheromones.
Besides pheromone trails, ants rely on heuristic information as well. The heuristic information is defined as the inver of the distance between two locations as shown
in equation (1):
1
. . . . . . . (1)
ij
ij
n
d
=
Where n ij is the heuristic information linking nodes i to j while d ij is the distance between nodes i and j. Therefore, the shorter the distance between two given locations, the better their heuristic information and vice-versa. The heuristic information is an indirect method of communication between the predecessor and successor ants. The predecessors would provide information to the successors bad on what they have experienced.
All ants would take into consideration the intensity of pheromones for a given path and also the heuristic information associated with it before deciding on a path to take. This leads us to the concept of transition probabilities.
B.Transition Probabilities
Armed with knowledge regarding the intensity of the pheromone trails and heuristic information, the probability with which a path is to be chon by an ant can be determined. This probability is known as the transition probability. Over the past few years, many variants of the ACO metaheuristic have been propod, each with its own method of calculating transition probabilities and performing updates of pheromone intensities and heuristic
information. Some of the include [10]:
• Ant System
• Elitist Ant System
• MAX-MIN Ant System • Ant Colony System
• Approximate Nondeterministic Tree Search
(ANTS)
• Hyper-Cube Framework for ACO • Rank-Bad Ant System
To propo ACO metaheuristic, the Ant System (AS) algorithm has been chon. This algorithm was developed by Marco Dorigo and his colleagues in the early 1990s. The formula (equation 2) for calculating the transition probability in the AS algorithm is as follows:
[][] . . . . .(2)[][]
ij ij k ij
blogk
i
il il n p l n αβαβ
ττ=∑∈`
The left hand side of the equation reprents the probability in which ant k will traver from node i to node j. The numerator on the right hand side of the equation consists of a product of two terms, []ij α
τand []ij n β. []ij α
τ reprents the intensity of the pheromone trail between nodes i and j with a corresponding weight of α. On the other hand,
[]ij n β reprents the heuristic information between nodes i
and j with a corresponding weight of β. The denominator on the right hand side of the equation is a sum of the products of the pheromone intensity and heuristic information for all possible moves. As can be en from the equation also, the greater the pheromone intensity and heuristic information associated with a path, the more likely it is to be chon by an ant.
III. IMPLEMENTATION OF THE ACO
METAHEURISTIC
A. Problem Definition
The MRPP problem is to be implemented on ven maps, each having a grid reprentation and an equal number of rows and columns. The maps have been taken from Sedighi et. al [3]. Each map has a varying degree of complexity. The static obstacles and walls are prent in different arrangements and locations for each map. Each artificial ant (hereafter referred to as ants) reprent
s the mobile robot and is placed at the starting point in one corner of the map which is being considered. The objective of each ant is to find its way towards the destination in the opposite corner of the map. It has to do so whilst avoiding all obstacles and walls along the way. In order to utilize the concepts behind the ACO metaheuristic, each ant should attempt to arch for the shortest distance as possible as it can from the starting point to the destination.
B. Assumptions Made
In applying the propod ACO metaheuristic for the MRPP problem, veral assumptions have been made.
Firstly, only one ant is nt out at a time to explore the map. Also, the ants are allowed to move only one node at a time, i.e. upwards, downwards, leftwards or rightwards. Diagonal movements cannot be made. Besides that, each ant can only travel to a node once. This means that if an ant encounters a dead-end (no more possible moves), it is killed off and another ant is deployed into the map.
Another assumption made is related to the implementation of the heuristic information in the propod ACO metaheuristic. As described earlier, the heuristic information is defined as the inver
of the distance between two locations. However, a slight modification to this concept was required before it could be implemented into propod ACO metaheuristic. This is becau the propod ACO metaheuristic only allows each ant to move to one node at a time. This means that no matter which node an ant moves to, it results in a distance of 1. Hence, the usage of heuristic information would be redundant in this ca.
Instead of eliminating the usage of heuristic information in the propod ACO metaheuristic, a slight modification was made to the concept. We have decided to give each node an initial value for the heuristic information, similar to the pheromones. However, unlike the pheromones, the heuristic information does not evaporate or decay. The heuristic information is to be updated in a method similar to that of the pheromones. This would be explained in the next ction of this chapter.
As each map has a grid-like reprentation, each node has been assigned its own pheromone intensity and heuristic information. The pheromone intensities for each node are initialized to a value of 3.0 in the beginning while the heuristic information for each node is initialized to a value of 1.0. The values have been chon after extensive testing. Other than that, a large number of ants are required for the propod ACO metaheuristic to work effectively with the MRPP problem as only one ant is nt out to a map at a time, as mentioned earlier. As the pioneer ants are not guided by ph
eromone trails and heuristic information in the beginning, they are forced to move in random. As a result of this, most of the ants would produce bad tours and encounter dead-ends, resulting in a large number of ants being killed off in the beginning.
C. Update of Pheromone Trails and Heuristic Information In order for the ants to produce good tours, they have to be guided towards the destination. Therefore, the update of the pheromone trails and heuristic information associated with a map should be performed.
Regardless of successful tour or not, the evaporation of pheromones takes place. The evaporation factor was t to a factor of 0.2. It is necessary to perform the evaporation of pheromones on all nodes to prevent the unlimited电影当幸福来敲门
accumulation of pheromones in each node. Pheromone evaporation also allows the ACO metaheuristic to “eliminate” bad solutions that have been previously found by the other ants [10].
For successful tours, the pheromone intensity of each node travelled in that tour is incread by the following amount (equation 3):
()number of rows in a map 1.21 . . . (3)
tour distance ij new ij ττ⎛⎞=××+⎜⎟⎝⎠
For example, consider the ca of a 5 x 5 map, whereby the successful tour produced a distance of 8. The change in pheromone intensity for each node in the map is illustrated
below:
鸟画眉
Fig. 1. Initial pheromone intensities in each node
魔兽世界装备升级
Fig. 2. Pheromone intensities in each node are updated. The shaded nodes
are the nodes that have been taken by a successful ant As can be en in figure 1, the pheromone intensities in each node are initialized equally at the beginning. When a successful path has been found, the pheromone intensities for all the nodes in the map are updated accordingly as can be en in figure 2. The pheromone intensities of the nodes in the successful tour are incread, thereby increasing the attractiveness of this path for the subquent ants. The heuristic information in the nodes of the successful tour is also updated. They are incread by the following amount (equation 4): ()number of rows in a map . . . (4)tour distance ij new ij n n ⎛⎞=+⎜⎟⎝⎠
To illustrate the formula mentioned, consider again the ca
of the 5 x 5 map mentioned above, whereby the successful
tour produced a distance of 8. The change in heuristic
information for each node in the map is illustrated below:
Fig. 3. Initial heuristic information in each node
Fig. 4. The heuristic information in each node is updated. The shaded
nodes are the nodes that have been taken by a successful ant
As can be en in figure 3, the heuristic information in each node is initialized equally in the beginning. When a successful path has been found, the heuristic information for all the nodes in the successful tour are incread accordingly as can be en in figure 4. Hence, subquent ants would be more attracted to this path. Take note that there is no decay in heuristic information.
For the ca of failed tours, the penalization of the pheromone intensities and heuristic information for the nodes in the cond half of the bad tour is performed. In the said nodes, both values are reduced by half. This is to discourage the successor ants from producing poor solutions again.
D. Description of the Steps Involved in the ACO
Metaheuristic
The following are the steps involved:
Step 1: Execution of the ACO program. Ur lects map to perform ACO. Step 2: (Re-) Initialization of variables. The variables are
required for the proper execution of the coded ACO program.
Step 3: Check if there are any ants left to be deployed. If not, proceed to step 13. El, proceed to the next step. Step 4: Deploy an ant into the map.
Step 5: The said ant arches for all possible moves from its current position. A possible move exists if a node is free of obstacles or if it has not been pasd yet. If there are moves available, proceed to the next step. El, kill the current ant and perform penalization of pheromone trails and heuristic information for the cond half of the bad tour
and return to step 2. Evaporation of pheromones for all nodes is performed as well. Step 6: Calculate the transition probabilities for each
possible move (refer to equation 2).
Step 7: Select a node to move to. The nodes with higher
transition probabilities would have higher chances of being
lected by an ant and vice-versa. Then, the relevant
variables are reinitialized to ensure proper execution of the coded ACO program.
Step 8: Check if the destination has been reached. If not, return to step 5. El, proceed to the next step.
Step 9: Evaporate pheromones for all nodes. Then, perform the necessary updates of pheromone trail intensities and
heuristic information for all the nodes involved in the successful tour (refer to equations 3 and 4). Step 10: Produce a plot of the path that has been taken by the current ant.
Step 11: Produce a plot of the distances travelled by the successful ants.
Step 12: Check if there are any ants left to deploy into the map. If yes, return to step 4. El, proceed to the next step. Step 13: Stop the ACO process.
IV. RESULTS AND PERFORMANCE ANALYSIS A.
The Maps Ud for Evaluation
Fig. 5. A list of maps that have been chon to evaluate the
performance of the coded ACO program
Figure 5 shows a list of maps that are taken from [3]. SPSet03 is not available for analysis as it is not provided in their rearch paper. The thick boxes in the sub-figures above reprent the static obsta
cles and walls. The cross (X) reprent the paths that are produced by the genetic algorithm developed by Sedighi et. al. [3].
B. Sample Outputs from the ACO Program
The program for solving the MRPP problem using the propod ACO metaheuristic was coded in MATLAB R2007B. Sample outputs from the program are given in figures 6, 7, and 8. In figures 6 and 7, the squares and diamonds on the bottom left and top right corners, respectively, reprent the starting point and the destination. The circles reprent the static obstacles and walls. The lines with cross reprent the path that has been taken by the current ant.
乘传Fig. 6. A plot of the path taken by an ant for the ca when an ant
encounters a dead end
Fig. 7. A plot of the path taken by an ant when it has managed to
reach the destination
Fig. 8. A plot of the distances obtained by the ants which have
managed to complete a successful tour
In figure 6, it can be en that the ant has reached a dead-end as highlighted in the figure. In figure 7, the ant has managed to reach its destination. A successful tour is produced. In figure 8, a plot of the distances obtained by the ants which have managed to complete a successful tour is produced. In the early stages, the solutions obtained by the ants were found to be below par as their distances were not clo to the optimal value. However, as time pass by, the pheromone intensities and heuristic information associated with each node will begin to get updated. The ants would then begin to get guided towards the better solutions, eventually converge towards the optimal solution as highlighted in figure 8.
C. Results
The ACO program that was coded was executed for the maps SPSet01 to SPSet08 (except SPSet03). As the ACO process produces random results, the ACO program was executed 10 times to determine the minimum possible distance obtained. The ACO program was executed using an Intel Core2Duo 1.83GHz computer. The results obtained are tabulated and shown below:
(For values, 1.8, 1.5 and 0.2αβρ===whereby
α
爱情誓言is the weight of the pheromone intensities, and β is the weight of the heuristic information and ρis the evaporation factor of the pheromones).
