>> 韩李涛，2006，大范围虚拟城市环境中智能虚拟主体的自主导航方法
摘 要
随着人工智能在虚拟环境、计算机动画、系统仿真等领域的快速发展，智能虚拟环境（IVE）、行为动画、智能仿真系统等以交叉学科为基础的新研究领域逐渐成为计算机图形学界和人工智能界共同关注的焦点。作为智能虚拟环境主要特征的智能虚拟主体（IVA）是研究的核心问题之一，已经成为计算机图形学、虚拟环境、移动机器人、人工智能以及人工生命等多个学科领域的学术前沿和研究热点。在IVA研究中，自主导航行为一直是该领域研究的难点问题。传统的虚拟角色导航方法利用鼠标或键盘实时控制虚拟角色的运动方向和速度，或者让角色沿预先设定的路线运动。这些导航方法简单、有效，但缺乏自主性和灵活性，不适于具有自治特性的智能虚拟主体。IVA的自治特性要求IVA能够主动感知虚拟环境，自主地实现路径规划并能够应对动态未知环境的实时变化。目前，IVA自主导航研究主要集中在空间范围较小、环境内容较为简单的虚拟环境中；且多采用碰撞检测法、人工势场法等缺乏行为真实感的局部导航方式。随着基于遥感影像和三维激光扫描数据进行大范围自然场景的快速三维重建技术的发展，构建虚拟城市环境的代价迅速降低，虚拟城市环境建设得到快速发展。因此，大范围复杂虚拟城市环境中IVA自主导航问题日益凸现出来。针对上述问题，本文借鉴移动机器人和人工智能领域中的相关思路和算法，提出采用全局导航和虚拟视觉辅助下的实时局部导航有机结合的集成导航策略，并深入研究和实现了该导航策略中的关键模型和算法，具体内容包括：
- 顾及地形起伏信息的三维层次道路图模型及其构建方法。依据虚拟城市环境的特点，提出采用层次道路图模型对大范围虚拟城市空间建立环境地图。核心思想是把庞大复杂的三维环境空间利用自适应双剪切平面转化到二维平面空间，采用CDT剖分自由空间并在约束三角网中提取原始道路图；然后，把地形起伏因子融入道路图路径代价中以顾及地形表面形态，并深入分析原始道路图的拓扑邻接性质构建了道路网的层次结构。实验表明层次道路图在节点数、数据量等方面明显优于现有的规则网格地图，增强了环境地图的导航效率。
- 把能够反映人类视觉特点的视域、分辨率、注意力聚焦等重要视觉特性融入IVA虚拟视觉感知模型，提出了HVM视觉感知模型。在模型实现时首先采用合成视觉生成假彩色视觉图像，然后基于视觉图像快速获取目标类型、距离、方位、速度等多种目标信息。为加快视觉图像处理速度，利用多分辨率重采样方法优化图像处理过程。实验表明，通过减小视觉图像大小和优化视觉图像处理过程，该视觉模型能够满足自主导航的实时性、真实感要求并获取丰富的环境信息。
- 适于层次道路图的HA*路径搜索算法。基本思想是把路径搜索过程分为抽象道路层的主路径搜索和分支路径搜索两个层次，并最后把两个层次获取的路径有效连接作为最终路径。该算法能很好地适于层次道路图路径搜索，并利用减少搜索空间获取比传统A*算法更高的搜索效率，且搜索算法在算法完备性、可纳性等方面接近A*算法。整体路径优化采用二次抛物拟合对折线路径作自适应光滑处理，在路径跟踪过程中利用虚拟视觉对实时调整移动路径，经两次优化实际移动路线更加自然和具有现实感。
- 虚拟视觉辅助下的实时避障。针对路径跟踪过程中的实时避障和路径调整问题，提出视觉辅助下的IVA局部自主导航策略。利用虚拟视觉实时获取IVA周围各种障碍物的相关信息，并基于预定义导航规则和IVA与障碍物之间的空间几何关系及运动状态设计合理的避障算法。本文给出了不可预知的静止障碍物和移动障碍物的详细避障算法。实验结果表明该策略能够有效完成IVA局部避障任务。
- 原型系统开发和综合实验。扩展VGEGIS软件平台，设计开发了实验原型系统以综合验证本文探讨和提出的有关理论、方法和算法。实验表明，全局导航和视觉辅助下实时导航的有机结合能够较好地满足虚拟城市环境中IVA自主导航。
本文对大范围虚拟场景中IVA自主导航的研究，本质上是对现实环境中智能生物或移动对象进行导航行为建模与仿真。本文研究的结论和成果可应用于军事或航天工业领域的模拟与训练、智能动画角色建模与控制、城市交通仿真、人类应急反应行为等许多研究和应用领域。
关键词：
虚拟城市环境，智能虚拟主体，自主导航，层次道路图，层次A*算法，虚拟视觉，实时避障，路径优化
Abstract
With the rapid development of artificial intelligence in such fields as virtual environment, computer animation and system simulation, some new researching domains such as intelligent virtual environment (IVE), behavioral animation and intelligent simulation system are gradually becoming focus concerned by many scholars from computer graphics field and artificial intelligence. Intelligent virtual agent (IVA) that is the most important feature of IVE has become the academic front and hotspot of many subjects such as computer graphics, virtual environment, moving robotics, artificial intelligence and artificial life. Autonomous navigation is always one of nodi of IVA research. Traditional navigation methods for virtual character are to control the direction and velocity of movement by the mouse and keyboard or to let it move along the initialized path. Those ways are simple and efficient but empty of autonomy and flexibility, which are unfit for intelligent virtual agent. The autonomy of IVA requires that it can sense virtual environment on its own initiative, plan path and response autonomously to dynamic and unknown environment. Most existing researches on autonomous navigation for IVA focus on relatively small and simple environments and are limited to local navigation modes. Many algorithms based on collision detection and artificial potential fields have been widely used for local navigation but lack of reality; the great progress of 3D reconstruction technology for large-scale scene based on RS images and 3D laser scanned data decreases the cost of constructing the virtual urban environment (VUE), which makes VUE develop rapidly. Thereupon, autonomous navigation for IVA arises in the large-scale and complex virtual urban environment. For above problems, an integrated strategy is proposed which combines global navigation and real-time local navigation supported by virtual vision referring to related ideas and algorithms from moving robotics and AI. Pivotal models and algorithms concerned about this strategy are deeply studied and realized which mainly include several aspects as followed:
(1) Hierarchical road map considering the uneven feature of terrain and its establishment. According to the features of VUE, hierarchical road map model is presented to represent the large-scale urban space. The main steps are as followed: an adaptive plane is used to cut geometric models of objects to translate the 3D space to 2D space; the Constrained Delaunay Triangulation algorithm is used to partition the free space and a preliminary plane road map is extracted from TIN; then, the slope factor of terrain is added to path cost and hierarchical structure of road map is constructed based on the topological adjacency. Experimental results show that the hierarchical road map has obvious superiority to the regular grid map in quantity of nodes and size of map and enhances the navigating efficiency of environmental map.
(2) HVM virtual vision model is presented which integrates several human optic characteristics such as field of vision, resolution and attention. To realize the model, false-color image is rendered firstly by synthetic vision, then many kinds of information about objects (type, distance, orientation, speed, etc) are extracted from the image. To speed the image processing, multi-resolution resample is used to optimize the processing procedure. The experimental results show that the model can have satisfying efficiency, sensory reality by reducing the size of image and optimizing the processing procedure.
(3) HA* algorithm applicable to hierarchical road map is presented. Its main idea is that path planning is divided into two parts: the main path searching based on abstract road layer and the branched path searching on lower layer, which are connected as the complete path. The algorithm is suitable for hierarchical road map and more efficient than traditional A* algorithm by reducing the searched space with almost equal soundness and optimality to A* algorithm. Path optimization consists of two stages: quadratic parabolic fitting is used to smooth adaptively the polygonal path, and virtual vision is used for real-time adjustment of path during the path following. The optimized path is more natural and real.
(4) Real-time avoiding obstacle supported by virtual vision. For real-time obstacle-avoidance and path adjustment during the path following, autonomous local navigational strategy supported by virtual vision is proposed. Virtual vision is used for real-time acquisition of environmental information. The algorithms to avoid unpredictable stationary objects and moving ones are designed based on predefined navigational rules, spatio-temporal relations among obstacles and IVA and moving state of them. The efficiency of the strategy is proved by experimental results.
(5) Prototype system and integrated experiments. A prototype system is developed by expanding the software platform VGEGIS to test the theories, methods and algorithms discussed in this paper. Results show that the combination of global navigation and real-time local navigation supported by virtual vision is an efficient strategy for IVA autonomous navigation in VUE.
In fact, Autonomous navigation of IVA in the large-scale virtual scene in this paper is to model and simulate navigational behavior of intelligent creatures or moving object in the real world. Experimental results and conclusions can be applicable to many aspects such as emulating and training in military or space fields, modeling and control of intelligent animate character, urban traffic simulation, human emergent reaction behavior research, etc.
Key words:virtual urban environment, intelligent virtual agent, autonomous navigation, hierarchical road map, HA* algorithm, virtual vision model, real-time obstacle-avoidance, path optimization.
