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

關(guān)鍵詞：虛擬現(xiàn)實；虛擬城市；路徑規(guī)劃；導(dǎo)航

中圖分類號：U675.73；TP391.9 文獻(xiàn)標(biāo)志碼：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

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

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

1 VRML概述

1.1 VRML簡介

虛擬現(xiàn)實建模語言VRML (Virtual Reality Modeling Language)是一種描述三維境界的語言，可以直接構(gòu)造虛擬環(huán)境。通過VRML語言直接構(gòu)造的三維物體具有代碼簡單、執(zhí)行速度快等優(yōu)點?？梢灾苯佑脤懽职寰庉媀RML文件，也可用一些支持VRML的編輯器編輯(如VrmlPad)編寫VRML文件。它的應(yīng)用平臺是因特網(wǎng)、內(nèi)部網(wǎng)和本地客戶系統(tǒng)，與具體的設(shè)備(如:數(shù)據(jù)手套、數(shù)據(jù)衣)無關(guān)。VRML是一種ASCII碼格式的文本文件，其文件長度有限，同樣一個場景文件的長度遠(yuǎn)小于其它格式的文件，所以在網(wǎng)絡(luò)帶寬有限的條件下，它更加適合于在計算機(jī)網(wǎng)絡(luò)上進(jìn)行傳播［5］。

1.2 利用支持VRML的開發(fā)工具構(gòu)造虛擬環(huán)境

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

1.3 VRML的交互功能

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

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

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

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

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

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

2 路徑規(guī)劃問題

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

2.1 全局路徑規(guī)劃

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

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

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

2.2 局部路徑規(guī)劃

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

2.3 隨機(jī)路標(biāo)規(guī)劃器

一些為全局路徑規(guī)劃的實際算法都是基于在機(jī)器人構(gòu)型空間的隨機(jī)采樣方法。

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

帶有隨機(jī)路標(biāo)方法的路徑規(guī)劃器屬于多次查詢規(guī)劃器方法。它包括兩個階段：預(yù)處理階段和查詢階段。

在預(yù)處理階段，規(guī)劃器從虛擬環(huán)境中抽取集合信息，采樣C-空間并為自由空間（無碰撞構(gòu)型集合）建立一個連通圖。規(guī)劃器會在自由空間中的各個方向采集構(gòu)型，采集足夠的構(gòu)型后，規(guī)劃器會通過局部規(guī)劃器用一個簡單的路徑計算連接附近的構(gòu)型，從而形成一個自由空間的拓?fù)浣Y(jié)構(gòu)的連通圖。

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

2.4 帶有隨機(jī)路標(biāo)規(guī)劃器的虛擬城市中導(dǎo)航

虛擬城市的特點：道路固定，也就是環(huán)境靜態(tài)。這樣對于城市中的自由空間就很好確定，并且由于導(dǎo)航是在與路面這樣一個二維平面上，不像機(jī)器人的空間是三維的，所以對于虛擬城市中自由空間的信息量相對會少些。基于這些特點選擇基于自由空間的隨即路標(biāo)規(guī)劃方法?？梢远啻尾樵?nèi)我鈨牲c之間的路徑，而不必對空間進(jìn)行重構(gòu)。

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

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

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

3 結(jié)論

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

參考文獻(xiàn)

［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］萬 剛，陳 剛，游 雄.虛擬城市中地物幾何建模技術(shù)的研究［J］.測繪學(xué)報，2002，(1):60-65.

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

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

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

［6］朱 鳳，王汝傳，王海艷，劉 麗.基于VRML室內(nèi)虛擬環(huán)境構(gòu)建的研究與實現(xiàn)［J］.南京郵電學(xué)院學(xué)報.2004(4):80-85.

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

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