An auto-adaptive convex map generating path-finding algorithm: Genetic Convex A*

Pan Su, Yan Li, Yingjie Li, Chi Keung Simon Shiu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

Path-finding is a fundamental problem in many applications, such as robot control, global positioning system and computer games. Since A*is time-consuming when applied to large maps, some abstraction methods have been proposed. Abstractions can greatly speedup on-line path-finding by combing the abstract and the original maps. However, most of these methods do not consider obstacle distributions, which may result in unnecessary storage and non-optimal paths in certain open areas. In this paper, a new abstract graph-based path-finding method named Genetic Convex A*is proposed. An important convex map concept which guides the partition of the original map is defined. It is proven that the path length between any two nodes within a convex map is equal to their Manhattan distance. Based on the convex map, a fitness function is defined to improve the extraction of key nodes; and genetic algorithm is employed to optimize the abstraction. Finally, the on-line refinement is accelerated by Convex A*, which is a fast alternative to A*on convex maps. Experimental results demonstrated that the proposed abstraction generated by Genetic Convex A*guarantees the optimality of the path whilst searches less nodes during the on-line processing.
Original languageEnglish
Pages (from-to)551-563
Number of pages13
JournalInternational Journal of Machine Learning and Cybernetics
Volume4
Issue number5
DOIs
Publication statusPublished - 1 Oct 2013

Keywords

  • Abstract graph
  • Convex map
  • G-CA *
  • Genetic algorithm
  • Path-finding

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Cite this