Name
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. © 2012 Springer-Verlag. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s13042-012-0120-x | Int. J. Machine Learning & Cybernetics |
Keywords | Field | DocType |
path-finding,abstract graph,g-ca*,genetic algorithm,convex map | Mathematical optimization,Convex combination,Convex hull,Algorithm,Convex set,Subderivative,Convex polytope,Proper convex function,Convex optimization,Mathematics,Convex analysis | Journal |
Volume | Issue | ISSN |
4 | 5 | 1868808X |
Citations | PageRank | References |
8 | 0.54 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pan Su | 1 | 82 | 11.72 |
| Yan Li | 2 | 101 | 11.46 |
| Yingjie Li | 3 | 8 | 0.54 |
| Simon Shiu | 4 | 8 | 0.54 |