.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Path-finding
Convex map
Abstract graph
Genetic algorithm
G-CA*
期刊
IF:
2.7
论文数:
3.2K
被引数:
5.6K
机构
引用论文
Characterization of the aluminium coating layer in the hot press forming of boron steel.png)
Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture
Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering ManufactureIF0
PREAI
分享收藏分享收藏
A genetic algorithm for solving the inverse problem of support vector machines一种求解支持向量机反问题的遗传算法NEUROCOMPUTING
NEUROCOMPUTINGIF6.5
PREAI
分享收藏
查看更多内容