An Effective Initialization Method for Genetic Algorithm-based Robot Path Planning using a Directed Acyclic Graph

Abstract [Title Page]

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.

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.


Missing Figures

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

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.


Illustration (Map 01) Execution (SGMP)
(a) Artificial Map 01 [Link]
 
(b) Exploring map (DAG construction)
 
Obtained 50 paths GA optimization
(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}
}


Download

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.


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.