基于ＶＲＭＬ的虛擬城市導航系統的研究

摘 要：雖然虛擬現實技術最先是用于美國軍方的，但是現在它已經應用于社會生活的各個方面。如CAD，醫學，教育，城市規劃，遠程控制，游戲，娛樂等等。虛擬城市就是研究熱點之一。虛擬城市可以幫助人們通過網絡等媒介就可以了解一個城市。但是對于在虛擬城市中導航的研究并不多。所以本文提出了一個在基于VRML的虛擬城市中使用帶有路徑規劃器導航的思想。

關鍵詞：虛擬現實；虛擬城市；路徑規劃；導航

中圖分類號：U675.73；TP391.9 文獻標志碼：A

Research of Navigation System for Virtual City base on VRML

WANG Wei， TONG Jia-ying， WANG Li-fen， CHEN Xiao-dan

(College of Computer and Information Management，Hei Longjiang Institute of

Science and Technology， Harbin 50027， China)

Abstract:Virtual Reality technology has been used in various fields of social life， such as medicine， education， city planning， long-distance control， games and amusement and so on. Virtual city is one of the pop studies. Virtual city can help people to know the city via network etc. But the study of navigation in the virtual city is less. So this paper proposes a model that the navigation uses the random roadmap path planning in virtual city base on VRML.

Key words:virtual reality; virtual city; path planning; navigation

虛擬現實技術(Virtual Reality簡稱ＶＲ)是20世紀80年代末興起的一門嶄新的綜合性信息技術，它融合了數字圖像處理、計算機圖形學、多媒體技術、傳感器技術等多個信息技術分支，大大推進了計算機技術的發展。它以模擬方式為使用者創造了一個實時反映實體對象變化與相互作用的三維圖像世界，在視、聽、觸、嗅等感知行為的逼真體驗中，使參與者可直接參與和探索虛擬對象所處環境的作用和變化，仿佛置身于現實世界中，產生多感知(multi-sensory)、沉浸感(immersive)、實時感(real-time)和交互感(interactive)。這正是虛擬現實的最突出的特征［1］。例如，當你進入了一個虛擬城市中，你就會像真的進入了這座城市一樣，看到高樓林立，車輛穿行等等，如同身入其中。

在如今的信息化時代，人們通過網絡已經可以足不出戶就了解全世界。虛擬城市就可以讓人們不必親臨城市就可以了解這座城市的格局建筑等，因為它是真實城市的映射。很多人已經開始了虛擬城市的工作［2-4］。 但是如果你想了解一個陌生的城市，想找到這個城市中的某個位置，你在這個城市中漫無目的地去尋找，可能會費很大的勁才能找到，可能沒等找到就已經沒有了耐心，這時如果有個導航系統幫助的話就不會有這樣的煩惱了。所以本文提出了運用路徑規劃在虛擬城市中導航的思想。

1 VRML概述

1.1 VRML簡介

虛擬現實建模語言VRML (Virtual Reality Modeling Language)是一種描述三維境界的語言，可以直接構造虛擬環境。通過VRML語言直接構造的三維物體具有代碼簡單、執行速度快等優點。可以直接用寫字板編輯VRML文件，也可用一些支持VRML的編輯器編輯(如VrmlPad)編寫VRML文件。它的應用平臺是因特網、內部網和本地客戶系統，與具體的設備(如:數據手套、數據衣)無關。VRML是一種ASCII碼格式的文本文件，其文件長度有限，同樣一個場景文件的長度遠小于其它格式的文件，所以在網絡帶寬有限的條件下，它更加適合于在計算機網絡上進行傳播［5］。

1.2 利用支持VRML的開發工具構造虛擬環境

使用VRML編寫復雜場景時較為繁瑣，可以利用目前國際上較為流行的、能較好的為VRML提供可視化的工具來對復雜三維物體建模，從而可以大大提高了開發效率。目前支持VRML的工具有很多，而且它們大多提供可視化的操作，如3DS MAX、Maya、LightScape等。這些軟件都可以導出*. wrl文件，與VRML之間都提供了格式轉換接口，從而為幾種工具結合起來使用提供了可能［6］。

1.3 VRML的交互功能

VRML提供用戶與虛擬環境的交互功能，用戶可以根據需要感知VRML場景、改變場景中的造型狀態、觸發一個事件或開始一段VRML動畫。VRML提供了接觸傳感器、環境傳感器、感知傳感器及碰撞編組四類交互傳感器來完成VRML中的交互工作。

由于某些復雜的虛擬環境及交互VRML本身不能實現，但VRML提供了Script節點用以實現腳本語句的編程以方便對事件的高層處理和動畫的擴展控制。通過VRML提供的Script節點與JAVASCRIPT、JAVA進行數據通信，借助JAVASCRIPT、JAVA語言來實現對復雜動畫和交互的設計與實現。其方法有以下幾種：

1）Script→EventOut模式(間接的節點訪問方式)。傳感器通過路由到達Script節點，瀏覽器自動將到達的EventIn事件傳送到Url字段所致的腳本程序中，同時，瀏覽器用一種方法將程序運行所返回的結果寫入Script節點的EventOut字段，由EventOut發送事件通過路由將返回結果更新所控制的目標節點。

2）非Script→EventOut模式(直接的節點訪問方式)。不需要在Script節點中設置EventOut，由路徑顯示的將Java程序數據傳送到它想要產生影響的地方。首先要給出指向景中的目標的任意一個節點的指針，并且該指針類型SFNode類型還要被Script節點接受。這樣，當場景中的事件傳送到事件入口點時，由時間操縱類自動引導，Java程序便獲得了讀寫SFNode指針所指節點類型的字段。

3）VRML類包。是與相應的瀏覽器插件捆綁在一起，其作用是提供用于VRML編程的Java類，主要包含VRMLVrml.node和Vrml.field，還有一個可以操縱瀏覽器狀態的browser類。主要提供了EvenIn，Node接口和為每個VRML數據類型提供一個類擴展。Java程序之所以能夠通過Script節點訪問VRML場景是因為在Java的Vrml.node包中定義了一個Script類Script類是一個公共類，只要其他的對象可以看到這個類，就可以使用其中的變量、調用其中的方法；同時，它又是一個抽象類，只能供別的類繼承，而自己不能直接產生對象。常常用到的是Initialize和ProcessEvent方法，Initialize方法用于腳本程序在第一次運行時初始化內部數據；ProcessEvent方法是腳本接收到一個事件時被調用，處理腳本程序獲取的VRML場景數據并反饋給VRML場景。

4）利用VRML與Java編程技術擴展VRML節點(擴展VRML語言參數)。構成現實世界的宏觀對象是復雜多變的。在計算機中構成的虛擬場景在精度要求不高的情況下VRML的原始節點就可以滿足要求，可是在虛擬場景的精度較高時，VRML的原始節點就不能夠體現現實世界的精度要求。為了達到不同的精度要求，需要利用VRML的原型節點PROTO與Java(JavaScript)編程技術，構造符合要求的復雜的體現現實世界中對象的新節點(擴展VRML節點接口)。

2 路徑規劃問題

路徑規劃問題是機器人學中很重要的一個方面，是機器人導航中最重要的任務之一。根據對環境信息掌握的程度不同將移動機器人路徑規劃分為2種類型，1個是基于環境先驗完全信息的全局路徑規劃，另1個是基于傳感器信息的局部路徑規劃［7-8］。

2.1 全局路徑規劃

全局路徑規劃是指根據先驗環境模型找出從起始點到目標點的符合一定性能的可行或最優路徑，包括環境建模和路徑搜索策略2個子問題，其中局域路徑規劃按世界模型表達方法的不同存在3種比較典型的環境建模方法：構型空間法、自由空間法（free space approach）和柵格法（grids）等。

自由空間法應用于機器人路徑規劃，采用預先定義的如廣義錐形和凸多邊形等基本形構造自由空間，并將自由空間表示為連通圖，然后通過搜索連通圖來進行路徑規劃。

基于C空間的自由空間法的一般步驟是:1)建立C空間，構造自由空間； 2)確定單元的連通性，將自由空間表示為連通圖；3)建立搜索樹，確定搜索策略；4)進行路徑優化。自由空間法的優勢在于，構形空間能夠用清晰了然，然后通過這些幾何描述定義一些搜索方法。如果在已知的自由空間中存在避碰路徑，那么這些搜索方法可以保證找到這樣的路徑，而且是最短路徑，所以可以按其性能指標來搜索和優化路徑，且具有完備解。另外，該法比較靈活，初始點和目標點的改變不會造成連通圖的重構。

2.2 局部路徑規劃

局部路徑規劃的環境是未知或部分未知的，即障礙物的尺寸、形狀和位置等信息必須通過傳感器獲取。其主要方法有：人工勢場法（artificial potential field)、遺傳算法（genetic algorithm）和模糊邏輯算法（fuzzy logic algorithm）等。人工勢場法是由Khatib提出的一種虛擬力法，其基本思想是將機器人在環境中的運動視為一種虛擬的人工受力場中的運動，其中障礙物對機器人產生斥力，而目標點對機器人產生引力，引力和斥力的合力作為機器人的加速力來控制機器人的運動方向和計算機器人的位置。該法結構簡單，便于低層的實時控制，在實時避障和平滑軌跡控制，得到了廣泛應用。

2.3 隨機路標規劃器

一些為全局路徑規劃的實際算法都是基于在機器人構型空間的隨機采樣方法。

許多有效的規劃器可以在一個合理的環境中用很短的時間計算出一條無碰撞的路徑。他們可以分成兩個主要的類別：單次查詢方法和多次查詢方法。單次查詢方法不需要預測環境，只在運行階段對環境進行簡單的描述。多次查詢方法在對構型空間進行預處理的時候可能要花費一些時間以便為以后的路徑規劃查詢。多次查詢規劃器通常假設環境是不經常變化的，否則，每當環境改變，規劃器都會重新進行一次預處理。

帶有隨機路標方法的路徑規劃器屬于多次查詢規劃器方法。它包括兩個階段：預處理階段和查詢階段。

在預處理階段，規劃器從虛擬環境中抽取集合信息，采樣C-空間并為自由空間（無碰撞構型集合）建立一個連通圖。規劃器會在自由空間中的各個方向采集構型，采集足夠的構型后，規劃器會通過局部規劃器用一個簡單的路徑計算連接附近的構型，從而形成一個自由空間的拓撲結構的連通圖。

在查詢階段，給規劃器一對構型（初始構型和目標構型，分別q_i和q_g來表示），規劃器會找到一條連接它們的無碰撞路徑。路標規劃器會先試著將q_i和q_g分別與連通圖中的其它節點連接，分別用q_i’和q_g’表示，并在圖中找到一條連接q_i’和q_g’的路徑。連接q_i和q_g的路徑可以通過局部規劃器建立。

2.4 帶有隨機路標規劃器的虛擬城市中導航

虛擬城市的特點：道路固定，也就是環境靜態。這樣對于城市中的自由空間就很好確定，并且由于導航是在與路面這樣一個二維平面上，不像機器人的空間是三維的，所以對于虛擬城市中自由空間的信息量相對會少些。基于這些特點選擇基于自由空間的隨即路標規劃方法。可以多次查詢任意兩點之間的路徑，而不必對空間進行重構。

在預處理階段，規劃器在自由空間（所有的道路）中采樣路標。如果是有公交站臺的道路，那么公交站點就作為路標，如果是沒有公交站臺的道路，規劃器可以沿著道路每隔一段距離采樣一個路標。連接兩個相鄰的路標。直到所有的道路都采集了路標，采樣結束，并為查詢階段建立一個連通圖。因為不是像機器人學中任意方向都進行采樣，所以路標數量并不會很大。

在查詢階段，向規劃器輸入一個初始地址q_i和一個目標地址q_g，這些地址可以是建筑名也可以是道路名。然后規劃器回在連通圖中找到一條連接q_i和q_g的路徑。

在本文中，我們提出一個將隨機路標規劃器用于虛擬城市導航系統中的思想。目的是讓用戶在虛擬城市中很容易找到一個指定位置。當然，用戶也可以不沿著導航行走，自己自由行走，畢竟導航只是一個輔助工具。

3 結論

隨著虛擬現實技術的發展，對虛擬城市的研究也越來越多，這就出現了在虛擬城市中的導航問題，本文介紹了機器人學中的導航方法，并提出將機器人中的基于自由空間的隨機路標規劃方法引用到虛擬城市導航系統的思想，由于VRML具有與JAVA語言通信的能力，所以可以將用JAVA語言編寫的導航系統應用于基于VRML的虛擬城市中。但由于現在還處于研究階段，以后在付諸實踐的過程中可能會出現實際問題，有待進一步解決。

參考文獻

［1］Maurizio Piaggio，Renato Zaccaria. Using roadmaps to classify regions of space for autonomous robot navigation［J］.Robotics andAutonomous Systems 1998，25:209-217.

［2］萬 剛，陳 剛，游 雄.虛擬城市中地物幾何建模技術的研究［J］.測繪學報，2002，(1):60-65.

［3］萬劍華，潘正風，李清泉.基于VRML的虛擬城市的建立［J］.測繪通報.2002(5):17-19.

［4］段學軍.虛擬城市:技術方案與應用［J］.測繪通報.2001(12):1-3.

［5］王汝傳，姚旭敏，王海艷，劉 麗.基于Java和VRML虛擬場景通信方式的研究［J］.系統仿真學報，2003，15 (7):986-990.

［6］朱 鳳，王汝傳，王海艷，劉 麗.基于VRML室內虛擬環境構建的研究與實現［J］.南京郵電學院學報.2004(4):80-85.

［7］柏藝琴，賀懷清.移動機器人路徑規劃方法簡介［J］.中國民航學院學報.2003，增刊:206-209.

［8］祝奎臣.基于幾何和圖像的機艙漫游場景建模技術［J］.船海工程，2006(3):62-65.