Journal Title
Title of Journal: Int J Mach Learn Cyber
|
Abbravation: International Journal of Machine Learning and Cybernetics
|
Publisher
Springer Berlin Heidelberg
|
|
|
|
|
|
Authors: Pan Su Yan Li Yingjie Li Simon ChiKeung Shiu
Publish Date: 2012/07/20
Volume: 4, Issue: 5, Pages: 551-563
Abstract
Pathfinding is a fundamental problem in many applications such as robot control global positioning system and computer games Since A is timeconsuming when applied to large maps some abstraction methods have been proposed Abstractions can greatly speedup online pathfinding 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 nonoptimal paths in certain open areas In this paper a new abstract graphbased pathfinding 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 online 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 Aguarantees the optimality of the path whilst searches less nodes during the online processingThis research is supported by National Natural Science Foundation of China No 60903088 Natural Science Foundation of Hebei Province No F2009000227 Hong Kong PolyU grant No APJ18 and 100Tanlent Programme of Hebei Province No CPRC002 I would like to take the opportunity to thank Ren Diao and Peter Scully for proof reading the paper and the reviewers who have provided their critical comments and useful suggestions help in improving the contents
Keywords:
.
|
Other Papers In This Journal:
|