An Effective Initialization Method for Genetic Algorithm-based Robot Path Planning using a Directed Acyclic Graph
The goal of robot path planning is to find a feasible path that proceeds from a starting point to a destination point without intersecting any obstacles in the given environment. Recently, genetic algorithm-based robot path planning methods have been widely considered in the intelligent robotics community. Because the initialization process significantly influences the performance of the genetic algorithm, an effective initialization method is required. However, investigation on this subject is still lacking. In this paper, we propose an effective initialization method for genetic algorithm-based robot path planning. Experimental results comparing genetic algorithms with conventional initialization methods and the proposed initialization method showed that the proposed method leads to high quality paths in a significantly shorter execution time.
Information Title Page
This program is designed to generate initial path set for genetic algorithm-based robot path planning.
The main technical ideas behind how this program works appear in this paper:
Jaesung Lee and Dae-Won Kim, "An Effective Initialization Method for Genetic Algorithm-based Robot Path Planning using a Directed Acyclic Graph," Information Sciences, 332(1):1-18, 2016.
This software is a Matlab implementation of proposed method. The original version of this program was written by Jaesung Lee and Min-Gwan Seo.
The main technical ideas behind how this program works appear in this paper:
Jaesung Lee and Dae-Won Kim, "An Effective Initialization Method for Genetic Algorithm-based Robot Path Planning using a Directed Acyclic Graph," Information Sciences, 332(1):1-18, 2016.
This software is a Matlab implementation of proposed method. The original version of this program was written by Jaesung Lee and Min-Gwan Seo.
Missing figures and corresponding captions
In the original papers, there are missing figures; Figure 2(i), 2(j), 2(k), and 2(l). You can find the missing figure and corresponding explanation from this web page, or download the figures with PDF or JPG format. To see the missing figure here, please click below link.
Missing figures and corresponding captions
Figure 2 shows an example of the graph creation process. At the top of each figure, a table shows the status of V and E in the corresponding figure. In each figure, yellow boxes provide an explanation according to each procedure, and the number in the top-right white circle indicates the sequence of execution.
Detailed explanation about each figure is given in the original article Link
Missing figures and corresponding captions
Figure 2 shows an example of the graph creation process. At the top of each figure, a table shows the status of V and E in the corresponding figure. In each figure, yellow boxes provide an explanation according to each procedure, and the number in the top-right white circle indicates the sequence of execution.
 |
 |
 |
| (a) createGraph: initialise V, E, vl and test <vl, D> | (b) newFeasibleEdge: find < vy, vx > | (c) createGraph: set U and update V, E, vl |
 |
 |
 |
| (d) test < vl, D >, find < vy, vx >, and set U | (e) add < v1, vx > and update V, E, vl | (f) test < vl, D >, find < vy, vx >, and set U |
 |
 |
 |
| (g) add < u1, vx > and update V, E, vl | (h) test < vl, D >, find < vy, vx >, set U, and update V, E, vl | (i) test < vl, D >, find < vy, vx >, add < u1, vx >, update V, E, vl |
 |
 |
 |
| (j) test < vl, D >, find < vy, vx >, add < u1, vx >, update V, E, vl | (k) test < vl, D >, update V, E, vl, and terminate | (l) After termination |
Detailed explanation about each figure is given in the original article Link
Graphical Examples
Below examples show the graphical illustration of proposed method; (a) Artificial map 01, (b) a process of DAG construction, (c) 50 feasible paths created from obtained DAG, and (d) the change of paths according to GA optimization process.
Figure (a) shows the artificially created map, namely Map 01. In the figure, red circle and star indicate the position of starting node and destination node, respectively. Figure (b) demonstrates an example of directed acyclic graph (DAG) construction. In this step, the proposed method explores given map, resulting in a DAG connecting starting node and destination node. Figure (c) shows 50 feasible paths created from DAG, that form a initial path set for GARPP method. Finally, Figure (d) displays how GA optimizes given initial path set according to each generation. In the figure, a path with clearer red color indicates better path in terms of path length.
 |
 |
| (a) Artificial Map 01 [Link] |
(b) Exploring map (DAG construction) |
 |
 |
| (c) 50 feasible paths created from DAG | (d) GA optimization |
Figure (a) shows the artificially created map, namely Map 01. In the figure, red circle and star indicate the position of starting node and destination node, respectively. Figure (b) demonstrates an example of directed acyclic graph (DAG) construction. In this step, the proposed method explores given map, resulting in a DAG connecting starting node and destination node. Figure (c) shows 50 feasible paths created from DAG, that form a initial path set for GARPP method. Finally, Figure (d) displays how GA optimizes given initial path set according to each generation. In the figure, a path with clearer red color indicates better path in terms of path length.
Bibtex Code
@article{lee2016effective,
title={An Effective Initialization Method for Genetic Algorithm-based Robot Path Planning using a Directed Acyclic Graph},
author={Lee, Jaesung and Kim, Dae-Won},
journal={Information Sciences},
volume={332},
number={1},
pages={1-18},
year={2016},
publisher={Elsevier}
}
Terms and Usage
This program is available for download for non-commercial use, licensed under the GNU General Public License, which is allows its use for research purposes or other free software projects but does not allow its incorporation into any type of commerical software.
Download SGMP (Single Graph Multiple Path) Program (3 MATLAB .m files)
Download Experimental Maps (20 Artificial Maps, 4 Real-world Maps)
The zipped packages include componenets for source files and a sample input file, respectively.
Download SGMP (Single Graph Multiple Path) Program (3 MATLAB .m files)
Download Experimental Maps (20 Artificial Maps, 4 Real-world Maps)
The zipped packages include componenets for source files and a sample input file, respectively.
Sample Input and Output
SGMP function will return the path set according to given map. This code can be executed from MATLAB command window. Detailed information is given below.
[Usage]:
>> [pathSet, execTime, dag] = sgmp( map, sp, dp, setSize, numPt );
[Description]
pathSet - A set of path that contains "setSize" paths
execTime - A history of execution time for creating each path
dag - A Directed Acyclic Graph created by SGMP
map - A map specified in the binary square matrix [Download]
sp - The index of starting node
dp - The index of destination node
setSize - The number of paths to be created from DAG
numPt - The maximum number of allowable parents node
For more detailed information, please type "help sgmp" from MATLAB command window.
Other miscellaneous functions are also included in the ZIP package.
[Usage]:
>> draw_path( map, path ); - it will draw the obtained path.
>> draw_dag( map, dag ); - it will draw the obtaind DAG.
[Usage]:
>> [pathSet, execTime, dag] = sgmp( map, sp, dp, setSize, numPt );
[Description]
pathSet - A set of path that contains "setSize" paths
execTime - A history of execution time for creating each path
dag - A Directed Acyclic Graph created by SGMP
map - A map specified in the binary square matrix [Download]
sp - The index of starting node
dp - The index of destination node
setSize - The number of paths to be created from DAG
numPt - The maximum number of allowable parents node
For more detailed information, please type "help sgmp" from MATLAB command window.
Other miscellaneous functions are also included in the ZIP package.
[Usage]:
>> draw_path( map, path ); - it will draw the obtained path.
>> draw_dag( map, dag ); - it will draw the obtaind DAG.