.png){kind=icon}
.png){kind=icon}
Return
An auto-adaptive convex map generating path-finding algorithm: Genetic Convex A*
.png){kind=icon}
PRE
AI
DOI：10.1007/s13042-012-0120-x.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 online 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.
Keywords:
Path-finding
Convex map
Abstract graph
Genetic algorithm
G-CA*
Journal
IF:
2.7
Papers:
3.1K
Citations:
5.6K