>>2006,HAN Litao, Research on Autonomous Navigation for IVA in Large-scale Virtual Urban Environments

---

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.