A Spectral Based Heuristic Function For 3D Path Finding

Path-finding is an important research area in artificial intelligence,and path-finding techniques are widely used in many applications,such as 2D/3D video games,virtual reality,navigation,robots,and etc.With the development of the computer graphics technology,there have been more and more scenarios with complex environment and geometry,which requires highly efficient and intelligent path-finding algorithms.A~*algorithm,known as a heuristic algorithm,is a very classic path-finding algorithm.The key idea of A~*is a cost function for estimating the cost to the goal point.The cost function contains two parts:one is the exact distance from start position to the current position;and the other is a heuristic function to estimate the distance from current position to the goal position.The previous research work showed that the efficiency of A~*algorithm largely depends on the heuristic function.More accurate the heuristic function is,more efficient the path-finding algorithm is.In 3D scenario,path-finding is usually restricted by 3D surfaces,with holes and bend for instance,for which many previous existing path-finding algorithm do not work well.We introduce a new class of spectral-based heuristic function for A~*path-finding algorithms in this paper.The goal of our work is to calculate as accurately as possible the heuristic distance.We estimate the distance in a distance-preserving spectral space,which is obtained by a spectral decomposition algorithm so that the heuristic distance in the spectral space well approximates the Euclidean distance.The spectral representation in our method consumes much less space that the precomputed distance values in many previous accelerated A~*algorithms.As our heuristic function is more accurate,less time is spent before finding the path to the goal point.We tested and compared several traditional spectral analysis algorithms for the heuristic function of A~*algorithm.Local spectral methods aim at preserving the local spatial relationship,but usually fail to preserve a good global geometry well.On the contrary,global spectral methods,especially distance preserving methods,preserve the global geometry well enough for the requirement of our heuristic method.Through analysis and comparisons,we adopt the multi dimension scaling(MDS)method for spectral embedding.MDS is a distance preserving method,which is consistent with the goal of the heuristic function.We also tested the path-finding algorithm on several 3D scenarios,aiming at verifying our method’s feasibility and efficiency.The experiments showed that our algorithm achieves better performance in 3D path-finding.