【作者】 郑辉；

【导师】 刘新国；

【作者基本信息】 浙江大学 ， 计算机应用技术， 2016， 硕士

【摘要】 寻径技术一直是人工智能中比较重要的研究内容,广泛应用于游戏、虚拟现实、导航、机器人等领域。随着计算机图形学技术的发展,场景的立体化、复杂化,三维场景的寻径得到了越来越多的关注。A~*算法是寻径算法里的最为经典的算法。A~*算法是一种启发式搜索算法,其核心是到目标点的路径代价估计函数。该函数包含两项,一项表示起始节点到当前节点实际距离,另一项启发式函数表示当前节点到目标节点的距离估计。启发式函数越准确,A~*寻径的效率越高。在三维场景中,路径生成效率往往受限于复杂的三维表面,例如孔洞、表面扭曲等。在这种复杂的场景下,传统的启发式函数很难准确地估计节点间的距离。本文提出一种基于谱分析的启发式函数,以得到尽量准确的路径代价估计值用于A~*寻径。该方法通过寻找合适的谱分解方法将复杂三维场景的距离信息尽可能等距地嵌入到一个合适的谱空间,在后续寻径中,通过计算该谱空间上点对的欧式距离可以较好求得启发式函数的值。以往基于预计算的改进方法往往受限于点对距离的空间存储,时间效率等,本文的算法很好的解决了空间存储问题,在时间上也有很好的提升。本文分析比较了几种谱分解的方法,基于这些方法选取合适的嵌入谱空间,并分析其应用于三维场景寻径启发式函数的可行性。基于局部特性保持的谱方法主要是通过保持局部的几何关系进行谱分解映射到谱空间,而其全局的几何特性相对保持较差。而全局特性保持的谱方法,特别是距离保持的谱方法,比较契合本文的应用需求。本文经过分析比对采用了保距的多维尺度分析(MDS)谱分解方法来嵌入到合适的谱空间,求解启发式函数。我们还进行了场景测试实验,根据场景对应谱空间上的点对欧式距离进行启发式三维场景寻径,进而验证算法的可行性及性能。实验表明,本文的方法在三维场景寻径方面具有较好的表现。更多还原

【Abstract】 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.更多还原