時間：2023-05-28 09:24:44
開篇：寫作不僅是一種記錄，更是一種創造，它讓我們能夠捕捉那些稍縱即逝的靈感，將它們永久地定格在紙上。下面是小編精心整理的12篇路徑規劃典型算法，希望這些內容能成為您創作過程中的良師益友，陪伴您不斷探索和進步。
【關鍵詞】智能交通系統 蟻群算法 信息素 最優路徑 組合優化
交通運輸的現代化使人們享受便利的同時，也面臨道路擁堵、事故頻發等問}。近年來，智能交通系統越來越受到人們的重視，它涉及到交通領域諸多方面，如最優路徑選擇、車輛路徑規劃、動態車輛調度、交通流量控制等。其中一個重要的應用是一類典型的以數學理論為基礎的組合優化問題，而蟻群算法具有內在的搜索機制及正反饋性，適合求解一系列的組合優化問題。
1 蟻群算法描述
蟻群算法源于20世紀90年代初意大利學者M.Dorigo首次提出的螞蟻系統。它是基于種群的啟發式放生進化系統，是通過對蟻群覓食過程中其行為的研究而得出的一種算法。主要思路是螞蟻借助自己路徑尋優的能力可以找到巢穴與食物之間最短的途徑。在尋找過程中主要依靠的是每個螞蟻在行進過程中留下的揮發性分泌物――信息素，依靠信息素，蟻群的螞蟻之間可以相互合作，相互配合，因此形成的正反饋可以使每只螞蟻找到所有路徑中最短的路徑。
螞蟻a從節點j移動至k的轉移概率可以從式（1）中獲取：
（1）
（2）
（3）
2 蟻群算法的應用優勢
蟻群算法，又名螞蟻算法，螞蟻可以利用信息素的濃度大小從而尋找到覓食的最優路徑。該算法的優點可以總結為：
2.1 并行分布式計算
每個螞蟻都是獨立的個體，在覓食過程中屬于多起點同時啟動，互不影響，從根本上分析該過程屬于分布式的多Agent系統，整體蟻群最終任務的順利完成不會由于某些個體的缺陷而受到影響。該算法具有真實可用性，并且可用于解決對單目標的優化或者對多目標的優化等重要問題。此外，螞蟻算法還可進行并行計算。
2.2 魯棒性
蟻群算法的最終結果與螞蟻最初選擇的路徑無太大關系，在利用人工仿真螞蟻進行問題求解過程中，不需要對其進行人工的修整。把問題簡單化，可以和其他算法相互結合求解最優問題。
2.3 自組織性
蟻群算法組織指令的來源為系統內部，它不受外界環境的干擾，因此該算法具有自組織性。
2.4 正反饋性
螞蟻對于最優路徑的選擇主要依靠路徑上信息素濃度的多少，信息素的堆積是正反饋的過程，路徑上信息素的含量越多則該路徑被選擇的幾率就會越大，正反饋的作用是使整體能夠更快的尋找到最優途徑，正反饋在蟻群算法中處于重要地位。
2.5 易于實現
它是一種啟發示算法，其計算復雜性為，整個算法的空間復雜度是：。
3 蟻群算法在智能交通領域的應用空間
蟻群算法在解決組合優化問題方面有著明顯的優勢，從而在智能交通領域也有著廣泛的應用空間。
3.1 車輛路徑導航
根據行車人員的需要，根據對實時路況信息的統計，系統可以智能的為其推薦最優路徑，節省時間，節省資源。
3.2 動態車輛調度
當客戶需要調度中心為其進行車輛服務時，調度中心要考慮到客戶的情況，要考慮到效率的問題，要考慮到行車路線、行駛時間等問題。蟻群算法便可迅速得到合理的解決方案，使客戶和調度中心均可受益。
3.3 車輛路徑規劃
面對多個客戶不同的要求時，配送中心要根據實際情況進行車輛的配送，通過蟻群算法系統獲取整體的最優路線，根據路線規劃，及時進行車輛出發以滿足客戶要求，同時充分利用了道路資源和車輛資源。
3.4 公共交通智能化調度
利用先進的技術手段、大型數據庫技術等動態地獲取實時交通信息，實現對車輛的實時監控和調度，最終建立集運營指揮調度、綜合業務通信及信息服務等為一體的智能化管理系統。
3.5 交通流量控制
通過蟻群算法簡化復雜的道路交通網絡，盡量使交通流量在各個道路上分布均勻，避免因流量過大而造成車輛的阻塞。及時了解交通流量情況，緩解了交通擁擠，降低了交通事故的發生率。
參考文獻
[1]M.Dorigo，V.Maniezzo，A.Colom.Ant System：Optimization by a colony of cooperating agents.IEEE trans on SMC，1996，26（01）：28-41
[2]Eric BONABEAUB， Marco DORIGO，Guy THERAULAZ.AWARM intelligence： from natural to artificial systems[M].New York：Oxford University Press，1999
[3]楊海.蟻群算法及其在智能交通中的應用[D].濟南：山東師范大學，2008：14-18
作者簡介
白曉（1979-），女。工學碩士學位。現供職于廈門軟件職業技術學院軟件工程系。主要研究方向為軟件工程、智能算法。
王婭（1983-），女。工學碩士學位。現供職于廈門軟件職業技術學院軟件工程系。主要研究方向為網絡工程，軟件設計。
摘 要：在查閱大量文獻的基礎上對多機器人路徑規劃的主要研究內容和研究現狀進行了分析和總結，討論了多機器人路徑規劃方法的評判標準，并闡述了研究遇到的瓶頸問題，展望了多機器人路徑規劃方法的發展趨勢。
關鍵詞：多機器人；路徑規劃；強化學習；評判準則
Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multirobot.Then discussed the criterion of path planning research for multirobot based large of literature.Meanwhile，it expounded the bottleneck of the path planning research for multirobot，forecasted the future development of multirobot path planning.
Key words:multirobot；path planning;reinforcement learning;evaluating criteria
近年來，分布式人工智能(DAI)成為人工智能研究的一個重要分支。DAI研究大致可以分為DPS（distributed problem solving）和MAS（multiagent system）兩個方面。一些從事機器人學的研究人員受多智能體系統研究的啟發，將智能體概念應用于多機器人系統的研究中，將單個機器人視做一個能獨立執行特定任務的智能體，并把這種多機器人系統稱為多智能體機器人系統（MARS）。因此，本文中多機器人系統等同于多智能體機器人系統。目前，多機器人系統已經成為學術界研究的熱點，而路徑規劃研究又是其核心部分。
機器人路徑規劃問題可以建模為一個帶約束的優化問題，其包括地理環境信息建模、路徑規劃、定位和避障等任務，它是移動機器人導航與控制的基礎。單個移動機器人路徑規劃研究一直是機器人研究的重點，且已經有許多成果[1~3]，例如在靜態環境中常見的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓撲法、鏈接圖法、DempsterShafer證據理論建圖等；動態環境中常見的有粒子群算法、免疫算法、遺傳算法、神經網絡、蟻群算法、模擬退火算法、人工勢場法等。然而，多機器人路徑規劃研究比單個機器人路徑規劃要復雜得多，必須考慮多機器人系統中機器人之間的避碰機制、機器人之間的相互協作機制、通信機制等問題。
1 多機器人路徑規劃方法
單個機器人的路徑規劃是找出從起始點至終點的一條最短無碰路徑。多個機器人的路徑規劃側重考慮整個系統的最優路徑，如系統的總耗時間最少路徑或是系統總路徑最短等。從目前國內外的研究來看，在規劃多機器人路徑時，更多考慮的是多機器人之間的協調和合作式的路徑規劃。
目前國內外多機器人路徑規劃研究方法分為傳統方法、智能優化方法和其他方法三大類。其中傳統方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優化方法主要有遺傳算法、蟻群算法、免疫算法、神經網絡、強化學習等；其他方法主要有動態規劃、最優控制算法、模糊控制等。它們中的大部分都是從單個機器人路徑規劃方法擴展而來的。
1）傳統方法 多機器人路徑規劃傳統方法的特點主要體現在基于圖論的基礎上。方法一般都是先將環境構建成一個圖，然后再從圖中尋找最優的路徑。其優點是比較簡單，比較容易實現；缺點是得到的路徑有可能不是最優路徑，而是次優路徑。薄喜柱等人[4]提出的一種新路徑規劃方法的基本思想就是基于柵格類的環境表示和障礙地圖的。而人工勢場方法的基本思想是將移動機器人在環境中的運動視為一種虛擬人工受力場中的運動。障礙物對移動機器人產生斥力，目標點產生引力，引力和斥力周圍由一定的算法產生相應的勢，機器人在勢場中受到抽象力作用，抽象力使得機器人繞過障礙物。其優點是適合未知環境下的規劃，不會出現維數爆炸問題；但是人工勢場法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國昌等人[5]提出了引用總體勢減小的動態調度技術的多機器人路徑規劃，較好地解決了這個問題。
2）智能優化方法 多機器人路徑規劃的智能優化方（算）法是隨著近年來智能計算發展而產生的一些新方法。其相對于傳統方法更加智能化，且日益成為國內外研究的重點。
遺傳算法是近年來計算智能研究的熱點，作為一種基于群體進化的概率優化方法，適用于處理傳統搜索算法難以解決的復雜和非線性問題，如多機器的路徑規劃問題。在路徑規劃中，其基本思想是先用鏈接圖法把環境地圖構建成一個路徑節點鏈接網，將路徑個體表達為路徑中一系列中途節點，并轉換為二進制串；然后進行遺傳操作（如選擇、交叉、復制、變異），經過N次進化，輸出當前的最優個體即機器人的最優路徑。遺傳算法的缺點是運算速度不快，進化眾多的規劃要占據很大的存儲空間和運算時間；優點是有效避免了局部極小值問題，且計算量較小。
孫樹棟等人[6，7]在這方面較早地展開了研究，提出的基于集中協調思想的一種混合遺傳算法來規劃多機器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環境地圖，在環境未知情況下的規劃沒有得到很好的解決；且規劃只能保證找到一個比較滿意的解，在求解全局最優解時仍有局限。
文獻[8]中提出的一種基于定長十進編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長編碼機制及定長二進制編碼機制需特殊遺傳操作算子和特殊解碼的缺陷， 使得算法更加簡單有效。
智能計算的另一種常見的方法——蟻群算法屬于隨機搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運動過程來實現尋優，通過螞蟻群體中各個體之間的相互作用，分布、并行地解決組合優化問題。該算法同樣比較適合解決多機器人的路徑規劃問題。
朱慶保[9]提出了在全局未知環境下多機器人運動螞蟻導航算法。該方法將全局目標點映射到機器人視野域邊界附近作為局部導航子目標，再由兩組螞蟻相互協作完成機器人視野域內局部最優路徑的搜索，然后在此基礎上進行與其他機器人的碰撞預測與避碰規劃。因此，機器人的前進路徑不斷被動態修改，從而在每條局部優化路徑引導下，使機器人沿一條全局優化的路徑到達目標點。但其不足是在動態不確定的環境中路徑規劃時間開銷劇增，而且機器人缺乏必要的學習，以至于整個機器人系統路徑難以是最優路徑。
強化學習[10，11] (又稱再激勵學習)是一種重要的機器學習方法。它是一種智能體從環境狀態到行為映射的學習，使得行為從環境中獲得積累獎賞值最大。其原理如圖1所示。
強化學習算法一般包含了兩個步驟：a）從當前學習循環的值函數確定新的行為策略；b）在新的行為策略指導下，通過所獲得的瞬時獎懲值對該策略進行評估。學習循環過程如下所示，直到值函數和策略收斂:
v0π1v1π2…v*π*v*
目前比較常見的強化學習方法有：Monte Carlo方法、動態規劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學習算法以及Dyna-Q算法等。其Q值函數迭代公式分別為
TD（0）策略： V(si)V(si)+α[γi+1+γV(si+1)-V(si)]
Sarsa算法： Q(st，at)Q(st，at)+α[γt+1+γQ(st+1，at.+1)-Q(st，at)]Qs′學習算法： Qπ(s，a)=∑Pαss′[Rass′+γVπ(s′)]
近年來，基于強化學習的路徑規劃日益成為國內外學者研究的熱點。M. J. Mataric[12]首次把強化學習引入到多機器人環境中。而基于強化學習的多機器人路徑規劃的優點主要體現在：無須建立精確的環境模型，簡化了智能體的編程；無須構建環境地圖；強化學習可以把路徑規劃、避碰、避障、協作等問題統一解決。
張芳等人[13]提出了基于再激勵協調避障路徑規劃方法，把再勵函數設計為基于行為分解的無模型非均勻結構，新的再勵函數結構使得學習速度得以提高且有較好的魯棒性。同時，證明了在路徑規劃中，機器人的趨向目標和避障行為密切相關，對反映各基本行為的再勵函數取加權和來表示總的再勵函數要優于取直接和的表示方式，也反映了再勵函數設計得合理與否及其確切程度將影響再勵學習的收斂速度。王醒策等人[14]在動態編隊的強化學習算法方面展開了研究。宋一然[15]則提出了分段再勵函數的強化學習方法進行路徑規劃。其缺點是學習次數較多、效率不高，當機器人數目增加時，它有可能面臨維數災難的困難。所以，基于強化學習的路徑規劃在多機器人環境下的學習將變得比較困難，需要對傳統的強化學習加以優化，如基于人工神經網絡的強化學習[16]等。
3)其他方法 除了以上國內外幾種比較常見且研究較多的方法外，還有唐振民等人[17]提出的基于動態規劃思想的多機器人路徑規劃，把運籌學中的動態規劃思想與Dijkstra算法引入到多機器人的路徑規劃中，用動態規劃的基本思想來解決圖論中的費用流問題和路徑規劃中的層級動態聯盟問題。其選擇距離鄰近法作為聯盟參考依據。一個機器人的鄰居是指在地理位置上分布在這個機器人周圍的其他機器人；與該機器人最近鄰的機器人為第一層鄰居，第一層鄰居的鄰居為該機器人的第二層鄰居， 依此類推。那么層級越高（即越近)的鄰居，它滿足協作要求的可能性越大。動態規劃算法實質上是一種以空間換時間的技術，它在實現的過程中，必須存儲產生過程中的各種狀態，其空間復雜度要大于其他算法，故動態規劃方法比較適合多機器人的全局路徑規劃。
孫茂相等人[18]提出了最優控制與智能決策相結合的多移動機器人路徑規劃方法。其首先構造一個以各機器人最優運動狀態數據庫為核心的實時專家系統， 在離線狀態下完成; 然后各機器人在此專家系統的支持下， 以最優規劃策略為基礎， 采用速度遷移算法， 自主決定其控制。該方法擁有較好的穩定性與復雜度。焦立男等人[19]提出的基于局部傳感和通信的多機器人運動規劃框架較好地解決了多機器人路徑規劃在局部在線規劃的系統框架問題。沈捷等人[20]提出了保持隊形的多移動機器人路徑規劃。以基于行為的導航算法為基礎，把機器人隊列的運動過程劃分為正常運動、避障和恢復隊形三個階段。在避障階段，引入虛擬機器人使隊形保持部分完整;當隊形被嚴重打亂時，規劃機器人的局部目標位姿使隊列快速恢復隊形。其算法重點為避障機器人進入避障狀態，暫時脫離隊列，并以虛擬機器人代替避障機器人。
2 多機器人避碰和避障
避障和避碰是多機器人路徑規劃研究中需要考慮的重點問題之一。避障和避碰主要討論的內容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規劃中常見的多機器人避障方法[21]有主從控制法、動態優先法（建立在機器人之間的通信協商上）、交通規則法、速率調整法，以及障礙物膨脹法、基于人工勢場的方法等。
目前國內外對于多機器人避障展開的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎，擴充并完善了路徑/速度分解方案來協調多機器人，設立集中管理agent進行整體規劃，為每個機器人規劃路徑；并根據優先級規則對運動特征進行分布式規劃以避免機器人間的沖突。周明等人[23]提出分布式智能避撞規劃系統，將原來比較復雜的大系統轉換為相對簡單的子系統問題，由各智能機器人依據任務要求和環境變化， 獨立調整自身運動狀態，完成任務的分布式智能決策體系結構。任炏等人[24]提出了基于過程獎賞和優先掃除的強化學習多機器人系統的沖突消解方法。該算法能夠顯著減少沖突，避免死鎖，提高了系統整體性能。歐錦軍等人[25]提出了通過調整機器人的運動速度實現多機器人避碰，將避碰問題轉換為高維線性空間的優化問題， 并進一步將其轉換為線性方程的求解。該方法的缺點是系統的復雜度較高、計算量太大。
人工勢場方法的特點是計算簡潔、實時性強、便于數學描述，且適合于多自由度機器人環境，但容易產生抖動和陷入局部極小。為了克服其缺點，景興建等人[26]提出了人工協調場的方法，在傳統排斥力場中增加一個協調力，并將吸引力、排斥力和協調力與局部環境下機器人的運動狀態和運動要求結合起來，有效地保證機器人的安全性，提高機器人在復雜動態環境下行為決策的準確性和魯棒性。
3 多機器人協作和協調機制
多機器人間的運動協調[27~31]是多機器人路徑規劃的關鍵，也是多機器人與單機器人路徑規劃相區別的根本所在。多機器人系統在復雜動態實時環境下，由于受到時間、資源及任務要求的約束，需要在有限時間、資源的情況下進行資源分配、任務調配、沖突解決等協調合作問題，而機器人間的協調與協作，能夠大大地提高整個系統的效率和魯棒性，成為系統完成控制或解決任務的關鍵。
目前已有的協調方式分為集中式、分布式和混合式三種。在集中式協調中，集中規劃器詳細地規劃出每個機器人的動作，通常的做法是將多個機器人看做一個多自由度的機器人進行規劃；而分布式協調規劃中，機器人之間進行合作，將一個任務分成多個子任務，根據各自的特點完成不同的子任務，從而共同完成總任務；混合式協調是集中式和分布式混合在一起的形式。
多機器人間典型的協調方法[32]有合同網協議[33]、黑板模型、結果共享的協同方法、市場機制。近年來強化學習在多機器人協作方面也得到很好的應用，陳雪江[32]在基于強化學習的多機器人協作方面展開了研究，提出了多智能體協作的兩層強化學習方法來求解在多智能體完全協作、有通信情況下的協作問題。其主要通過在單個智能體中構筑兩層強化學習單元來實現：第一層強化學習單元負責學習智能體的聯合任務協作策略；第二層強化學習單元負責學習在本智能體看來是最有效的行動策略。陳偉等人[34]提出基于多目標決策理論的多機器人協調方法；通過對環境的拓撲建模，從基于行為的機器人學角度出發，對任務進行分解并設計目標行為，以多目標行為決策理論作為決策支持，從而達到多機器人運動協調的目的。
4 多機器人路徑規劃方(算)法的判優準則
通常評價機器人路徑規劃方(算)法的標準文獻[35]有正確性、時間/空間復雜度、并行性、可靠性、擴展性、魯棒性和學習。而多機器人的路徑規劃除了以上一些衡量標準之外，還需要考慮整個系統的最優化以及機器人間的協調性。
1)正確性 是分析算法的最基本的原則之一。一般來說算法的正確性是指:在給定有效的輸入數據后，算法經過有窮時間的計算能給出正確的答案。但在多機器人路徑規劃算法中，正確性主要指:路徑規劃算法要生成多個機器人協調運動的無碰安全路徑;這條路徑是優化的。
2)安全性 一般指多機器人所生成的各路徑中節點與障礙物有一定的距離。但在實際的應用背景下，有人認為安全性可以從兩個方面來理解：a）狹義地講，它就是機器人在行走過程中所做的功。在一定的條件下，它與路徑長度準則是一致的。b）廣義地講，它是各種優化條件加權綜合而得到的結果。
3)復雜度 一個算法的復雜性高低體現在該算法所需要的計算機資源的多少上面。所需要的資源越多，該算法的復雜性越高；反之，所需要的資源越少，該算法的復雜性就越低。算法的復雜性包括時間復雜度和空間復雜度。
在多機器人的路徑規劃算法中，算法的復雜度分析顯得尤為重要。一般地，單機器人路徑規劃算法的時空復雜度已經頗高，它們的數量級至少是O(n2)；多機器人的路徑規劃算法不僅是m-O(n2)(即m個機器人路徑規劃簡單地疊加)，它們之間還存在著對運動空間競爭的沖突，面對不斷變化的沖突的協調需要花費大量的時間和空間。通常多機器人的路徑規劃算法與機器人的個數呈指數關系O(km×n2)（k為常數）。這對多機器人路徑規劃算法的時間/空間復雜度控制是一個很嚴峻的考驗。
4)并行性 算法的并行性從算法設計、編寫程序、編譯和運行等多個不同的層次來體現。路徑規劃過程需要大量的計算，當處理的環境比較復雜，機器人工作的環境過于緊湊，尤其是機器人數量很多時，算法的時間/空間復雜度勢必會成為算法效率的關鍵。因此，在算法設計和運行上的并行性是通常考慮的方法。對多個機器人的路徑規劃盡量采用分布式多進程的規劃機制，以實現每個機器人路徑規劃的并行性。
5)可靠性 把多個機器人及其工作環境看成是一個系統，多機器人處于它們各自的起始點時，稱該系統處于初始狀態；當它們處于各自的目標點時，稱該系統處于目標狀態。多機器人的路徑規劃就是在該系統的這兩個狀態間建立一串合理的狀態變遷。這一狀態變遷過程可能會歷經許多狀態，如果在狀態變遷過程中，路徑規劃算法控制不好各狀態間的轉移關系，就會導致系統紊亂，出現機器人間的碰撞、找不到路徑等惡性后果，使任務失敗。所以這就對算法的可靠性和完備性提出了挑戰。為了很好地克服這一困難，需要對系統的各種可能狀態建模，分析它們相互間的關系，建立有限狀態自動機模型或Petri網模型，并以此為指導，按照軟件工程的思想，構造恰當的算法輸入來對算法的可靠性進行檢驗。
6)可擴展性 在多機器人的路徑規劃算法中，可擴展性主要是指一種路徑規劃算法在邏輯上，或者說在實現上能否容易地從2D空間擴展到3D空間，從低自由度擴展到高自由度，從較少的機器人數到更多的機器人數。可擴展性在各種路徑規劃算法之間沒有一種量的比較標準，只能從實際的具體情況出發、從對環境描述的適宜程度出發、從算法解決這一問題的復雜度出發、從算法本身的自適應出發等來考慮。
7)魯棒性和學習 魯棒性對于多機器人系統非常重要。因為許多應用，如路徑規劃要求連續的作業、系統中的單個機器人出現故障或被破壞，要求機器人利用剩余的資源仍然能夠完成任務。學習是在線適應特定的任務。雖然通用的系統非常有用，但將它用于特定應用上時，通常需要調整一些參數。具有在線調整相關參數的能力是非常吸引人的，這在將體系結構轉移到其他應用時可以節省許多工作。尤其是多機器人系統中機器人的自身學習和相互間的學習能夠大大提高整個系統的效率和系統的穩定性。
8）最優化 對動態環境有優化反應。由于有些應用領域涉及的是動態的環境條件，具有根據條件優化系統的反應能力成為能否成功的關鍵。
5 結束語
綜上所述，國內外研究者在多機器人路徑規劃取得了一些成果，但是在協作、學習、通信機制等方面仍面臨很大的困難和不足。如何進一步提高機器人間的協調性，增強機器人自身以及相互間的學習以提高多機器人系統的效率和魯棒性都有待深入研究。近年來無線通信技術得到長足發展，但在目前的技術條件下，在多機器人系統中實現所有機器人之間的點對點實時通信還有較大困難，這也是大多數多機器人系統仍然采用集中通信方式的主要原因。因此，如何降低多機器人系統對通信速度的依賴程度也是一個非常重要的問題。
總之，多機器人路徑規劃設計和實現是一項極其復雜的系統工程，展望其能在結合計算智能方法，如差分進化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網絡、人工勢場的改進、模擬退火和環境建模方法等方面取得新的突破。
參考文獻：
［1］WEISS G.Multiagent systems:a modern approach to distributed modern approach to artificial intelligence[M].Cambridge， Massachusetts：MIT Press，1999：121-161.
[2]蔡自興，徐光祐.人工智能及其應用:研究生用書[M].3版.北京：清華大學出版社，2004：124-198.
[3]譚民，王碩，曹志強.多機器人系統[M].北京：清華大學出版社，2005：6-81.
[4]薄喜柱，洪炳熔.動態環境下多移動機器人路徑規劃的一種新方法[J].機器人，2001，23（5）：407-410.
[5]顧國昌，李亞波.基于總體勢減小的動態調度技術解決多機器人的路徑規劃[J].機器人，2001，23（2）：171-174.
[6]孫樹棟，林茂.基于遺傳算法的多移動機器人協調路徑規劃[J].自動化學報，2000，26（5）：672-676.
[7]周明，孫樹棟，彭炎午.基于遺傳算法的多機器人系統集中協調式路徑規劃[J].航空學報，2000，21（2）：146-149.
[8]CAI Zixing，PENG Zhihong.Cooperative coevolutionary adaptive genetic algorithm in path planning of cooperative multimobile robot systems[J].Journal of Intelligent and Robotic Systems:Theory and Applications，2002，33(1):61-71.
[9]朱慶保.全局未知環境下多機器人運動螞蟻導航算法[J].軟件學報，2006，17（9）：1890-1898.
[10]SANDHOLM T W，CRITES R H.Multiagent reinforcement learning in the iterated prisoner’s dilemma[J].BioSystems，1996，37(1):147-166.
[11]高陽，陳世福，陸鑫.強化學習研究綜述[J].自動化學報，2004，30（1）：
86-100.
[12]MATARIC M J.Interaction and intelligent behavior[D].Massachusetls:Department of Electrical Engineering and Computer Science，MIT，1994.
[13]張芳，顏國正，林良明.基于再勵學習的多移動機器人協調避障路徑規劃方法[J].計算機工程與應用，2003，39（3）：80-83.
[14]王醒策，張汝波，顧國昌.多機器人動態編隊的強化學習算法研究[J].計算機研究與發展，2003，40（10）：1444-1450.
[15]宋一然.基于強化學習的多機器人路徑規劃方法[J].莆田學院學報，2006，13（2）：38-41.
[16]韓學東，洪炳熔.基于人工神經網絡的多機器人協作學習研究[J].計算機工程與設計，2002，23（6）：1-3.
[17]唐振民，趙春霞，楊靜宇，等.基于動態規劃思想的多機器人路徑規劃[J].南京理工大學學報，2003，27（5）：610-615.
[18]孫茂相，周明，王艷紅，等.多移動機器人實時最優運動規劃[J].控制與決策，1998，
13（2）：125-130.
[19]焦立男，唐振民.基于局部傳感和通訊的多機器人運動規劃框架[J].計算機工程與應用，2007，43(17)：89-93.
[20]沈捷，費樹岷，鄭波.多移動機器人保持隊形路徑規劃[J].東南大學學報，2005，35(3):391-395.
[21]MANSOR M A，MORRIS A S.Path planning in unknown environment with obstacles using virtual window[J].Journal of Intelligent and Robotic Systems，1999，24(3):235-251.
[22]徐潼，唐振民.多機器人系統中的動態避碰規劃[J].計算機工程，2003，29(17):
79-81，104.
[23]周明，孫茂相，尹朝萬，等.多移動機器人分布式智能避撞規劃系統[J].機器人，1999，21（2）：139-143.
[24]任炏，陳宗海.基于強化學習算法的多機器人系統的沖突消解的方法[J].控制與決策，2006，21(4):430-434，439.
[25]歐錦軍，朱楓.一種多移動機器人避碰規劃方法[J].機器人，2000，22(6):474-481.
[26]景興建，王越超，談大龍.基于人工協調場的多移動機器人實時協調避碰規劃[J].控制理論與應用，2004，21(5):757-764.
[27]PANAIT L，LUKE S.Cooperative multiagent learning:the state of the art[J].Autonomous Agents and MultiAgent Systems，2005，11(3):387-434.
[28]TZAFESTAS C S，PROKOPIOU P A，TZAFESTAS S G.Path planning and control of a cooperative three robot system manipulating large objects[J].Journal of Intelligent and Robotic Systems，1998，22(2):99-116.
[29]薛宏濤，葉媛媛，沈林成，等.多智能體系統體系結構及協調機制研究綜述[J].機器人，2001，23（1）：85-90.
[30]周風余，李貽斌，宋銳，等.基于混合式多智能體系統的協作多機器人系統研究[J].山東大學學報:工學版，2005，35(1):82-87.
[31]夏冰，張佐，張毅，等.基于多智能體系統的動態路徑選擇算法研究[J].公路交通科技，2003，20（1）：93-96.
[32]陳雪江.基于強化學習的多機器人協作機制研究[D].杭州：浙江工業大學，2004.
[33]SMITH R.The contract net protocol:highlevel communication and control in a distributed problem solver[J].IEEE Trans on Computer，1980，C-29(12):1104-1113.
關鍵詞：物流系統；智能化；車輛路徑；規劃
中圖分類號：P208 文獻標識碼：A 文章編號：1007-9599 （2013） 02-0000-02
1 概述
物流產業隨著基礎工業的不斷壯大及消費市場的蓬勃發展而快速興起。而中國的物流企業不論從技術裝備還是管理水平與國外仍存在較大差距，概括起來有一下幾個方面：對現代物流理念上的差距，企業規模方面的差距，社會需求方面的差距，管理體制方面的差距，專業手段方面的差距，專門人才方面的差距。據對美國物流業的統計與分析，以運輸為主的物流企業年平均資產回報率為8.3%（irr），倉儲為7.1%，綜合服務為14.8%。在中國大部分物流企業的年平均資產回報率僅為1%。這一數據，不僅說明了中國物流效率低下，同時企業仍有很大的空間通過物流來降低成本。
如何應用先進的技術手段來提高物流業的經營效率，及時高效、經濟地將商品配送到客戶手中，成了大家探討的話題，這也就是現代物流領域中備受關注的車輛路徑問題（vehicle routing problem，VRP）。物流配送路徑規劃的優化與否，對物流配送效率、費用和服務水平影響較大。而此類問題都涉及如何處理大量的空間數據與屬性數據而縮短物流時間、降低成本的問題。
地理信息系統作為不僅具有對空間和屬性數據采集、處理和顯示功能，而且可為系統用戶進行預測，監測、規劃管理和決策提供科學依據。它可以有效的結合最優路徑、各種VRP模型、車輛行駛成本等要素，在可視化分析以及物流規劃路徑分析等方面具有不可替代的作用。GIS技術與現代物流工程技術相結合，給現代物流行業提供了巨大的發展空間，為物流企業完善管理手段、減低管理成本、提高經濟效益、最終提升核心競爭力提供了機遇。
2 技術實現途徑研究
物流配送車輛路線優化問題由Dautzig和Ramser于1959年首次提出，該問題一般定義為：對一系列給定的顧客（取貨點或送貨點），確定適當的配送車輛行駛路線，使其從配送中心出發，有序地通過它們，最后返回配送中心。并在滿足一定的約束條件下（如車輛容量限制、顧客需求量、交發貨時間等），達到一定的目標（如路程最短、費用最少等）。配送中心的每次配送活動通常面對多個非固定用戶，并且這些用戶分布在不同的地點，同時他們的配送時間和配送數量也都不盡相同。如果配送中心不合理規劃車輛、貨物的運輸路線，常會影響了配送服務水平，還會造成運輸成本的上升，因此對車輛及貨物的配送路線進行規劃是配送中心的一項重要工作。
車輛路線優化問題一般可根據空間特性和時間特性分為車輛路線規劃問題和車輛調度問題。當不考慮時間要求，僅根據空間位置安排車輛的線路時稱為車輛線路或車輛路徑規劃問題（VRP）。當考慮時間要求安排運輸線路時稱為車輛調度問題（VSP）。本文不考慮時間要求，主要針對第一類VRP問題，提出相應的技術實現方案研究。
典型的VRP具有以下特征：（1）所有車輛從倉庫出發，并最終回到倉庫；（2）所有車輛必須滿足一定的約束；（3）多輛車負責多個客戶；（4）每個客戶由一輛車訪問一次；（5）車輛的路線上可以取送貨。目前研究的車輛路線規劃的模型主要有兩類，一類為網絡圖模型，另一類為數學模型。由于VRP難以用精確算發求解，啟發式算法是求解車輛運輸問題的主要方法，多年來許多學者對車輛運輸問題進行了研究，提出了各種各樣的啟發式方法。
物流公司的業務一般具有配送范圍廣的特點，本文主要針對大范圍跨省配送的案例進行智能路徑規劃，因此影響因素較多，主要包括：（1）大范圍、跨省的配送交通網絡圖；（2）復雜的車輛運作規則，包括運行時間、運載能力、運行成本計算、駕駛員工作時間限制等；（3）復雜的道路選擇優先級；（4）復雜的運輸車輛優先級；（5）客戶訂單及運輸車輛數據；（6）取貨及分發過程；（7）繁雜的配送規則，如倉庫、貨物、客戶的時間等；（8）運輸車輛的重復利用，要求同一輛車在符合多個約束條件下盡可能多的參與到不同路線的配送中。
本文主要基于ArcObjects的網絡分析和地圖展示等組件進行二次開發，同時對其提供的車輛路徑規劃算法進行了拓展性研究。
3 功能模塊設計方案
3.1 軟件架構設計
系統建設遵循SOA架構，由數據資源層、組件層、服務層和表現層組成。數據資源層包括各種數據庫、關系型數據庫和空間數據庫引擎ArcSDE，實現對物流業務數據的存儲和管理；組件層包括接口協議、GIS組件、其他中間件；服務層實現計算功能，接受表現層的請求進行計算；表現層采用多種形式展現分析結果。
3.2 軟件功能設計
本系統是物流業務管理系統的一部分，主要提供歷史數據管理模塊、線路優化分析模塊、地圖操作模塊，同時提供與其他相關業務系統的擴展功能。
（1）線路優化分析模塊
線路優化分析模塊是系統的關鍵，提供兩種分析結果：一種是基于AO自帶的網絡分析模塊設計，計算分析結果；另一種是歷次根據具體路況等信息的實際調度結果。
實際調度結果來自車輛GPS監控數據，并將實際調度結果作為輸入，用來校正線路優化分析方法，最后生成最優路徑規劃。
（2）地圖展示模塊
地圖展示模塊，在配送交通網絡圖上展示道路基本信息、周邊環境、倉庫及客戶地點、車輛位置信息等。同時將各種車輛路徑規劃分析結果以地圖形式展示。基于ArcGIS提供的基礎地圖操作功能，實現地圖縮放、瀏覽、鷹眼、圖層控制、測量、選擇、標注、信息查詢等功能。
（3）歷史數據管理模塊
歷史數據管理主要存儲歷史客戶訂單數據、實時路況信息、歷史路徑規劃分析結果、實際運輸路徑等，可支持對歷史數據的查詢和修改。
（4）擴展功能模塊
提供與其他相關業務系統、車載GPS設備、車輛監控設備等的接口，便于系統的擴展。
3.4 數據庫設計
本系統中涉及的數據庫主要包括元數據庫、基礎地理空間數據庫、業務數據庫、分析模型數據庫、歷史數據庫等。
4 結束語
本文將物流車輛路徑規劃理論算法的研究與地理信息系統的網絡分析模塊相結合，經過二次開發，形成了用于實際的物流車輛路徑規劃信息系統。另外車輛路徑規劃設計約束較多，本文中不考慮時間要求，僅根據空間位置安排車輛的線路，同時不考慮裝箱問題。
車輛路徑規劃問題是現代物流業的熱點問題，但是基本停留在理論算法層面，隨著技術的不斷進步，必然出現考慮更多約束的先進算法，希望將這些算法真正與現代物流業結合，那將會是一個跨越式的進步。
參考文獻：
關鍵詞：無線傳感器網絡；移動信標；節點定位
中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2011)21-5080-03
Research on Technology of Nodes Localization Based on Mobile Beacon for Wireless Sensor Network (WSN)
DING Hui, LI Bo-yong, AI Shu-liang
(Chenzhou Vocational and Technical College, Chenzhou 423000, China)
Abstract：Wireless sensor network has been used in many field. Nodes location of WSN has provided the basic information for many applications. Nodes location based on mobile beacon is one of the important research fields. Some basic principles and performance evaluating criterions of nodes localization based on mobile beacon for WSN are introduced. Some issues which need to be resolved in future are discussed.
Key words: wireless sensor network (WSN); mobile beacon; nodes localization
隨著傳感器技術、無線通信、微電子技術以及嵌入式計算等技術的發展，無線傳感器網絡(Wireless Sensor Network 簡稱WSN)得到了廣泛應用，成為當今活躍的研究領域。無線傳感器網絡是新型的傳感器網絡，同時也是一個多學科交叉的領域，與當今主流無線網絡技術一樣，均使用802.15.4的標準，由具有感知能力、通信能力和計算能力的大量微型傳感器節點組成，具有低成本、低功耗的優點和強大的數據獲取和處理能力。
在無線傳感器網絡的眾多應用中,如：國防軍事、環境監測、交通管理、醫療衛生、目標跟蹤、物流管理、入侵檢測、交通流量監控和勘測應用等領域, 監測到事件之后需要確定事件發生的位置，信息融合后得到的相關數據信息如果不包含事件位置信息將毫無意義，只有帶有標識位置信息的傳感數據才有實際的意義。傳感器節點自身的正確定位是提供事件位置信息的前提, 因此節點的精確定位基礎而關鍵[1] 。
1 無線傳感器網絡節點定位的分類及基本方法
節點定位是指確定傳感器節點的相對位置或絕對位置，節點所采集到的數據必須結合其在測量坐標系內的位置信息才有意義。人工部署傳感節點和為所有節點安裝GPS接收器都會受到成本、功耗、節點體積、擴展性等方面的限制，甚至在某些應用中是根本無法實現的。通常是為部分節點配置定位裝置（如GPS接收器）或事先標定其準確位置，這些節點稱為信標節點（也稱錨節點），再利用信標節點的相關信息采用一定的機制與算法實現無線傳感器網絡節點的自身定位。目前人們提出了兩類節點定位算法[2]：基于測量距離的定位算法與測量距離無關的定位算法。基于距離的定位方法首先使用測距技術測量相鄰節點間的實際距離或方位，然后使用三邊測量法、三角測量法、最小二乘估計法等方法進行定位。與測量距離無關的定位算法主要包括：APIT、質心算法、DV-Hop、Amorphous等。
1.1 基于無線傳感器網絡自身定位系統的分類[1,3-5]
1) 絕對定位與相對定位。絕對定位與物理定位類似，定位結果是一個坐標位置，如經緯度。而相對定位通常是以傳感區域某點為參考，建立整個網絡的相對坐標系統。
2) 物理定位與符號定位。經緯度就是物理位置；而某個節點在某街道的某門牌的建筑物內就是符號位置。一定條件下，物理定位和符號定位可以相互轉換。與物理定位相比，符號定位在一些特定的應用場合更加便于使用。
3) 集中式計算與分布式計算定位。集中式計算是指把所需信息傳送到某個中心節點，并在那里進行節點定位計算的方式；分布式計算是指依賴節點間的信息交換和協調，由節點自行計算的定位方式。
4) 移動信標與固定信標定位。移動信標節點是一類裝備了GPS或其它定位裝置的可移動節點，它在移動的過程中周期性自己的位置信息。基于移動信標的未知節點定位有很多優點，如定位成本低，容易達到很高的定位精度、可實現分布式定位計算、易于實現三維定位等。而固定信標節點是一類裝備了GPS或其它定位裝置的不可移動節點。
1.2 基于距離的節點坐標計算基本方法
待定位節點在獲得與鄰近信標節點的距離信息后，通常采用下列方法計算自身的位置[3]。
1) 三邊測量法：利用網絡中三個信標節點的位置坐標以及未知節點到這三個信標節點的距離，運用幾何方法求出未知節點的坐標。
2) 三角測量法：利用網絡中三個信標節點的位置坐標以及未知節點為角頂點角邊分別為三個信標節點的角度，運用幾何方法求出未知節點的坐標。
3) 最小二乘估計法：利用未知節點的相鄰節點中的多個信標節點的位置坐標以及它們與未知節點的距離或角度，運用最小均方差估計方法求出未知節點的坐標。
1.3 常用的測距方法
1) 信號接收強度（RSSI）測距法
已知發射功率和天線接收增益，在接收節點測量信號接收功率，計算傳播損耗，使用理論或經驗的無線電傳播模型由傳播損耗計算出信源與接收者間的距離。通常使用下列對數-常態分布模型來計算節點間的距離[1]。
PL(d)=PL(d0)+10λ?log(d/d0)+X （1）
PL(d0)=32.44+10λ?log(d0)+ 10λ?log(f) （2）
RSSI=發射功率+天線增益-路徑損耗(PL(d)) （3）
其中PL(d)[dB]是經過距離d后的路徑損耗，X是平均值為0的高斯分布隨機變數，其標準差取為4至10，λ為取衰減因子通常為2至3.5，f是頻率，取d0=1(m)，這樣根據上述3式可得節點間的距離。
2) 到達時間測距法
到達時間(TOA)技術通過測量信號傳播時間來測量距離，若電波從信標節點到未知節點的傳播時間為t，電波傳播速度為c，則信標節點到未知節點的距離為t×c。
3) 時間差測距法
TDOA測距是通過測量兩種不同信號到達未知節點的時間差，再根據兩種信號傳播速度來計算未知節點與信標節點之間的距離，通常采用電波和超聲波組合。
4) 到達角定位法
到達角(AOA)定位法采用陣列天線或多個接收器組合來獲取相鄰節點所處位置的方向，從而構成從接收機到發射機的方位線。兩條方位線的交點就是未知節點的位置。
1.4 典型非測距算法
基于距離測量和角度測量的定位算法的缺點是對專用硬件有一定的要求，從而使傳感器節點成本和體積加大，限制了它的實用性。非測距的算法不需要測量未知節點到信標節點的距離，在成本和功耗方面比基于測距的定位方法具有一定的優勢，但是精度相對不足。
1) DV－hop算法
為了避免對節點間距離的直接測量， Niculescu等人提出了DV－hop算法[3]。該算法基本思想是：用網絡中節點的平均每跳距離和信標到待定位節點之間的跳數乘積來表示待定位節點到信標節點之間的距離，再用三角定位來獲得待定位節點的位置坐標。
2) 質心法
質心法由南加州大學Nirupama Bulusu等學者提出[3]，該算法是未知節點以所有可收到信號的信標節點的幾何質心作為自己的估計位置，它是一種基于網絡連通性的室外節點定位算法。
3) APIT 算法
一個未知節點任選3個能夠與之通信的信標節點構成一個三角形，并測試自身位置是在這個三角形內部還是在其外部；然后再選擇另外3個信標節點進行同樣的測試，直到窮盡所有的組合或者達到所需的精度。
4) Amorphous 算法
Amorphous 定位算法[3]采用與 DV-Hop 算法類似的方法獲得距信標節點的跳數，稱為梯度值。未知節點收集鄰居節點的梯度值，計算關于某個信標節點的局部梯度平均值。Amorphous 算法假定預先知道網絡的密度，然后離線計算網絡的平均每跳距離，最后當獲得3個或更多錨節點的梯度值后，未知節點計算與每個錨節點的距離，并使用三邊測量法和最大似然估計法估算自身位置。
2 基于移動信標的無線傳感器網絡節點定位技術
無論是距離相關還是距離無關定位算法，常采用固定信標節點方式測量距離、相對角度、傳播時間差及傳播時間等進行節點定位[1]。通常參與定位的固定信標節點越多, 定位精度將越高。但是信標節點的成本遠遠高于普通節點，當定位工作完成后，信標節點將轉成普通的傳感器節點使用。因此信標點越多，布設整個網絡的成本將會增大, 定位算法的計算負荷以及通訊負荷將會增大[1] ，過多的信標節點將會造成較大的浪費。所以利用移動節點發出的虛擬坐標點進行輔助定位的思想將成為節點定位研究的一個重要研究方向。
假定整個WSN由靜止節點以及移動節點(如撒播節點完畢的飛機、運動的車輛、移動的小型機器人或普通的能移動的傳感器節點等) 兩種類型節點構成。根據傳感器網絡的規模大小, 可以配置一個或者多個移動節點。各移動節點均配置一個GPS接收器用于定位移動信標節點本身, 并有足夠的能量自我移動或捆綁移動機器人、移動車輛或三維空間中的飛機等工具。移動節點在傳感器區域內按照一定的運動路徑移動, 并周期性地發送坐標位置信息, 待定位節點根據接收到的坐標信息與采用適當的定位算法完成定位[6] 。
近幾年有一些研究者對移動錨節點路徑規劃展開研究，提出了一些比較好的路徑規劃方案。移動錨節點路徑規劃主要有兩個目標：
1) 移動軌跡能夠覆蓋網絡中的所有未知節點；
2) 為未知節點定位提供質量好的信標點。
如果滿足網絡節點均勻分布的條件，規劃路徑通常采用靜態規劃路徑，移動錨節點都按照預先規劃的路徑移動，不具有根據節點分布狀況靈活變化的性能。文獻[7]針對移動錨節點的路徑規劃問題利用空間填充線理論提出了SCAN、DOUBLESCAN以及HILBERT路徑規劃方法，分別如圖1、圖2和圖3所示。在節點通信距離小和空間填充線密度大的條件下， SCAN路徑比HILBERT路徑的定位結果準確。但是在節點通信距離大、空間填充線密度較小時，HILBERT路徑明顯優于SCAN路徑。
SCAN路徑存在明顯的缺點就是提供了大量共線的信標點，HILBERT路徑通過增加移動路徑長度解決了信標點共線性的問題，只要達到一定的密度就可以為定位提供優質的不共線信標點。為了解決信標點存在共線性的問題，文獻[8]提出了圓形規劃路徑和S形規劃路徑方法，如圖4和圖5所示。圓形規劃路徑完全覆蓋方形網絡區域時必須增加大圓路徑，這很大程度增加了路徑的長度。而圓形的直徑非常大時，在局部帶來了信標點的共線性問題。S形路徑通過引入S形曲線代替直線，解決了信標點共線性問題。
而對于實際環境中節點非均勻分布的情況，文獻[9]提出了提出了寬度優先和回溯式貪婪算法。這種方法能夠根據網絡信息自適應進行路徑規劃，規劃路徑不再是規則的圖形，能夠充分利用節點分布信息覆蓋所有節點，保證路徑最短，克服了靜態路徑規劃的缺點。文獻[10]提出讓一個攜帶GPS的移動信標采用隨機移動模型的方式盡量遍歷傳感區域，然后采用分布式算法為未知節點定位，該方法結合了基于測距方法的優點，并且無需布置固定的信標節點，節省了成本開銷，但是由于移動信標的移動模型采用隨機的方式，難以讓其移動范圍覆蓋整個傳感區域，從而有些未知節點無法定位。
3 定位算法的評價標準
定位算法設計的優劣通常以下列幾個評價標準[11]來評價：
1）定位精度：一般用誤差值與節點無線射程的比例表示，是定位技術首要的評價指標。
2）定位覆蓋率：指利用定位算法能夠進行定位的節點數與總的未知節點個數之比，它是評價定位算法的另外一個重要的指標。
3）信標節點密度：信標節點占所有節點的比例或者是單位區域內信標節點的數目。
4）節點密度：節點密度通常以網絡的平均連通度來表示。
5）功耗：功耗是指傳感器節點在單位時間內所消耗的能源的數量。由于傳感器節點不會始終在工作的，有時候會處于休眠狀態，但這同樣也會消耗少量的能量，因此，傳感器節點的功耗一般會有兩個，一個是工作時的功耗，另一個是待機時的功耗。
6）成本：包括時間、空間和費用。時間指一個系統的安裝、配置和定位所需的時間。空間包括一個定位系統或算法所需的基礎設施和網絡節點的數量、安裝尺寸等。費用則包括實現某種定位系統或算法的基礎設施、節點設備的總費用。
7）魯棒性：定位系統和算法必須具有很強的容錯性和自適應性，能夠通過自身調整或重構糾正錯誤、適應環境、減小各種誤差的影響，以提高定位精度。
上述的這些評價指標不僅是評價WSN自身定位系統和算法的標準，也是其設計和實現的優化目標。
4 結束語
使用移動信標節點來完成WSN所有節點的定位，就必須要足夠的時間讓移動信標節點遍歷完整個網絡, 為了減小所有節點定位所需的時間以及提高定位效率，如何進一步優化移動信標節點的運動路徑將成為基于移動信標的WSN節點定位技術更研究的重要方向。
參考文獻：
[1] 孫利民.無線傳感器網絡[M].北京:清華大學出版社,2005.
[2] A l-Karaki.JN, Kamal.AE. Routing Techniques in Wireless Sensor Networks: A Survey[J].In Wireless Communications,IEEE,Volume:11,Issue:6, Dec,2004:6-28.
[3] 王福豹,史龍,任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報,2005,16(5):857-869.
[4] Kushwaha,M. Molnar,K. Sallai,J. Volgyesi, P. Maroti, M. Ledeczi, A. Sensor Node Localization Using Mobile Acoustic Beacons[C], In proc. 2005. IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Nov,2005.
[5] 倪巍,王宗欣.基于接收信號強度測量的室內定位算法[J].復旦學報(自然科學版),2004.43(1):72-76.
[6] Mihail L. Sichitiu ,Vaidyanathan Ramadurai. Localization of Wireless Sensor Networks with a Mobile Beacon[C].//IEEE 2004:174-182.
[7] Koutsonilas D, Das S M, Hu Y Charlie. Path Planning of mobile landmarks for localization in wireless sensor networks[J].Computer Communication.2007,30(13): 2577-259.
[8] Rui Huang,Zaruba Gergely V. Static Pathplanning for mobile beaeons to localize sensor networks[C] / /Proc of IEEE PerComW. Piscataway,NJ:IEEE，2007:323-330.
[9] Hongjun Li,Jianwen Wang,Xun Li and Hongxu Ma. Real-time Path Planning of Mobile Anchor Node in Localization for Wireless Sensor Networks[C].//Proeeedings of the 2008 IEEE International Conference on Information and Automation,Zhangjiajie,China,June,20-23,2008.
[10] Srinath T V. Localization in Resource Constrained Sensor Networks Using a Mobile Beacon with In-Ranging[C]/ / IFIP International Conference on Wireless and Optical Communications Networks,India, 2006:301-305.
關鍵詞： 人工智能 足球機器人 人工神經網絡 智能控制
引言
足球機器人系統是一個典型的多智能體系統和分布式人工智能系統，涉及機器人學、計算機視覺[1]、模式識別、多智能體系統[2]、人工神經網絡[3]等領域，而且它為人工智能理論研究及多種技術的集成應用提供了良好的實驗平臺。機器人球隊與人類足球一樣，它的勝負不但取決于機器人本身的性能，而且取決于比賽策略，只有將可靠的硬件與先進的策略結合才能取勝。人工智能技術在足球機器人的平臺上有著重要的作用。從機器人的外觀到機器人最重要的核心部分——控制、決策，都無不起著重要的作用。專家系統[4]、人工神經網絡在機器人的路徑規劃[5]上得到充分的應用。
1.人工智能研究現狀
人工智能[6-8]是一門研究人類智能機理，以及如何用計算機模擬人類智能活動的學科，該領域的研究包括機器人、語言識別[9]、圖像識別、自然語言處理和專家系統等，涉及數理邏輯、語言學、醫學和哲學等多門學科。人工智能學科研究的主要內容包括：知識表示[10][11]、自動推理和搜索方法、機器學習和知識獲取、知識處理系統、自然語言理解、計算機視覺、智能機器人、自動程序設計等方面。
幾乎所有的編程語言均可用于解決人工智能算法，但從編程的便捷性和運行效率考慮，最好選用“人工智能語言”[12]。常用的人工智能語言有傳統的函數型語言Lisp、邏輯型語言Prolog及面向對象語言Smalltalk、VC++及VB等，Math-Works公司推出的高性能數值計算可視化軟件Matlab中包含神經網絡工具箱，提供了許多Matlab函數。另外，還有多種系統工具用于開發特定領域的專家系統，如INSIGHT、GURU、CLIPS、ART等。這些實用工具為開發人工智能應用程序提供了便利條件，使人工智能越來越方便地運用于各種領域。
智能機器人是信息技術和人工智能等學科的綜合試驗場，可以全面檢驗信息技術和人工智能等各領域的成果，以及它們之間的相互關系。人工智能技術中的視覺、傳感融合、行為決策、知識處理等技術，需要使無線通訊、智能控制、機電儀一體化、計算機仿真等許多關鍵技術有機、高效地集成統一。人們在很多領域都成功地實現了人工智能：自主規劃和調度、博弈、自主控制、診斷、后勤規劃、機器人技術、語言理解和問題求解等。
2.人工智能主要研究領域
人工智能的研究領域非常廣泛，而且涉及的學科非常多。目前，人工智能的主要研究領域包括：專家系統、機器學習、模式識別、自然語言理解、自動定理證明、自動程序設計、機器人學、智能決策支持系統及人工神經網絡等。下面主要介紹在足球機器人設計、制造、控制等過程中常用的人工智能技術[13]。
2.1專家系統
專家系統是一個智能計算機程序系統，是一個具有大量專門知識與經驗的程序系統，它應用人工智能技術和計算機技術，根據某領域一個或多個專家提供的知識和經驗，進行推理和判斷，模擬人類專家的決策過程，以便解決那些需要人類專家處理的復雜問題。專家系統一般具有如下基本特征：具有專家水平的專門知識；能進行有效的推理；具有獲取知識的能力；具有靈活性；具有透明性；具有交互性；具有實用性；具有一定的復雜性及難度。
2.2人工神經網絡
人工神經網絡是由大量處理單元互聯組成的非線性、自適應信息處理系統，采用了與傳統人工智能和信息處理技術完全不同的機理，克服了傳統的基于邏輯符號的人工智能在處理直覺、非結構化信息方面的缺陷，具有自適應、自組織和實時學習的特點。神經網絡在很多領域已得到了很好的應用，但其需要研究的方面還很多。其中，具有分布存儲、并行處理、自學習、自組織和非線性映射等優點的神經網絡與其他技術的結合，以及由此而來的混合方法和混合系統，已經成為一大研究熱點。由于其他方法也有優點，因此將神經網絡與其他方法相結合，取長補短，可以達到更好的應用效果。目前這方面工作有神經網絡與模糊邏輯、專家系統、遺傳算法、小波分析、混沌、粗集理論、分形理論、證據理論和灰色系統等的融合。
2.3圖像處理
圖像處理是用計算機對圖像進行分析，達到所需結果，又稱影像處理。圖像處理技術主要包括圖像壓縮，增強和復原，匹配、描述和識別三個部分。常見的處理有圖像數字化、圖像編碼、圖像增強、圖像復原、圖像分割和圖像分析等。數字圖像處理中的模式識別技術，可以對人眼無法識別的圖像進行分類處理，可以快速準確地檢索、匹配和識別出各種東西，在日常生活各方面和軍事上用途較大。
3.人工智能在足球機器人中的應用
3.1基于專家系統的足球機器人規劃
路徑規劃或避碰問題是足球機器人比賽中的一個重要環節。根據工作環境，路徑規劃模型可分為基于模型的全局路徑規劃和基于傳感器的局部路徑規劃。全局路徑規劃的主要方法有：可視圖法、自由空間法、最優控制法、柵格法、拓撲法、切線圖法、神經網絡法等。局部路徑規劃的主要方法有：人工勢場法、模糊邏輯算法、神經網絡法、遺傳算法[14]等。機器人規劃專家系統是用專家系統的結構和技術建立起來的機器人規劃系統。大多數成功的專家系統都是以基于規則系統的結構來模仿人類的綜合機理的。它由五部分組成：知識庫、控制策略、推理機、知識獲取、解釋與說明。隨著人工智能計算智能與進化算法研究的逐步發展，遺傳算法、蟻群算法等的提出，機器人路徑規劃問題得到了相應發展。尤其是通過遺傳算法在路徑規劃中的應用，機器人更加智能化，其運行路徑更加逼近理想的優化要求。以動態、未知環境下的機器人路徑規劃為研究背景，利用遺傳算法采用了基于路點坐標值的可變長染色體編碼方式，構造了包含障礙物排斥子函數項的代價函數，使得路徑規劃中的地圖信息被成功引入到了遺傳操作的實現過程中。同時針對路徑規劃問題的具體應用，改進了交叉和變異兩種遺傳算子，獲得了較為理想的路徑搜索效率，達到了較好的移動機器人路徑規劃效果。
3.2人工神經網絡在機器人定導航中的應用
人工神經網絡是一種仿效生物神經系統的信息處理方法，其優點主要體現在它可以處理難以用模型或規則描述的過程和系統；對非線性系統具有統一的描述；有較強的信息融合能力。因此在移動機器人定位與導航方面，基于神經網絡的多傳感器信息融合正是利用了神經網絡的這些特性，將機器人外部傳感器的傳感數據信息作為神經網絡的輸入處理對象，從而獲得移動機器人自身位置與對障礙物比較精確的估計，實現移動機器人的避障與自定位。
結語
隨著人工智能技術的進一步研究，足球機器人競賽水平將不斷提高。但就目前情況來看，在現有的基礎上擴大應用的范圍，增強應用的效果，還應主要在人工智能技術上做進一步的研究。專家系統在專家知識的總結、表述及不確定的情況下推理是目前專家系統的瓶頸所在。制造生產的多變復雜性及操作的人工經驗性，使人工智能的應用受到限制。此外，一些工藝參數的定量化實現也不易。隨著技術的飛速發展，人工智能技術也在進一步完善，如多種方法混合技術、多專家系統技術、機器學習方法、并行分布處理技術等。隨著新型人工智能技術的出現，制造業將會更加光明，性能更加優越的足球機器人也不再遙遠。
參考文獻：
[1]鄭南寧.計算機視覺與模式識別[M].北京-國防工業出版社，1998.3.
[2]Wang Hongbing Fan Zhihua She Chundong Formal Specification of Role Assignment for Open Multi Agent System Chinese of Journal Electronics[J].2007，16（2）：212-216.
[3]LIMING ZHANG AND FANJI GU NEURAL INFORMATION PROCESSING VOLUME 1[M]Fudan University Press， 2001.
[4]Cai Zixing，King-Sun Fu. Expert-System-Based Robot Planning ？Control Theory & Applications[J] .1988（2）： 35-42.
[5]張銳，吳成東.機器人智能控制研究進展[J].沈陽建筑工程學院學報（自然科學版），2003，19（1）：61-64.
[6]蔡自興，徐光祐.人工智能機器應用（第三版）清華大學出版社，2004.
[7]艾輝.謝康寧，謝百治.談人工智能技術[J]中國醫學教育技術，2004，18（2）：78-80.
[8]Nilsson NJ.Artificial Intelligence：A New Synthesis[M].Beijing：China Machine Press，2006：72-95.
[9]Han Jiqing Gao Wen Robust Speech Recognition Method Based on Discriminative Environment Feature Extraction Journal of Computer Science and Technology[J]. 2001；16（5）：458-464.
[10]Tang Zhijie Yang Baoan Zhang Kejing Design of Multi-attribute Knowledge Base Based on Hybrid Knowledge Representation Journal of Donghua University 2006，23（6）：62-66.
[11]Hu Xiangpei Wang Xuyin Knowledge representation and rule——based solution system for dynamic programming model Journal of Harbin Institute of Technology 2003，10（2）：190-194.
[12]姚根.人工智能的概況及實現方法[J] .2009，28（3）：108.
關鍵詞：IPv6；OSPFv3；RIPng；協議
中圖分類號：TP393.05 文獻標識碼：A 文章編號：1007-9599 (2011) 18-0000-02
IPV6 Routing Protocols and Algorithms Exploration
Zhao Yikui
(Wuxi Technician College,Wuxi 214044,China)
Abstract:Ipv6 is the core of coming Internet technology.In contemporary network technology the Routing Protocol is important concept.In this article we introduce IPv6's RIPng Routing Protocol and OSPFv3 Routing Protocol based upon the next generation,at the same time introduce the fundamental algorithm of above two protocols.
Keywords:IPv6;OSPFv3;RIPng;Agreement
隨著Internet的發展，使得網絡規模急劇膨脹，目前使用的IPv4協議由于其缺陷，己經不能從根本上適應網絡發展的需要。在這樣的背景下，下一代網絡標準――IPv6（Internet Protocol Version 6）協議應運而生。IETF設計了新一代的網絡協議，也被稱IPV6[3]。與IPV4（Internet Protocol Version 4）相比，在地址格式上發生了巨大的改變，地址長度由原來的32位變為128位。相應地在整個地址分配上也進行了一定的改進。IPV6協議仍然整個地址空間仍然是層次結構的，仍然支持類似于IPV4無類域間路由（classless inter-domain routing，簡稱CIDR）地址結構下的路由合并，因此IPV6協議采用不會改變路由查找的特點。但是地址空間的增大，大大增加了路由查找的復雜度。
目前IPv6網絡的路由協議基本沿襲了IPV4相關路由協議，IPV6地址相對IPV4更加結構化和層次化，使得IPV6網絡的路由架構的層次化和可擴展性更優，這不僅對路由協議本身提出了新的要求，也對在不同網絡結構下如何利用不同路由協議特點建立路由體系提出了新的挑戰。近年對IPV6標準的不斷充實和完善，IPv6協議及相關協議發展已相當成熟。下面給各位探討流行的2種路由協議：RIPng和OSPF。
一、RIPng協議（RIP next generation）和RIPng路由選擇算法
在網絡中最復雜，最重要的一個方面就是路由。路由選擇算法是網絡層軟件的一部分。按照其能否隨著網絡的通信量或拓撲結構來適應和調整變化來劃分，可以分為自適應路由選擇算法和非自適應路由選擇算法。自適應路由選擇算法主要使用距離――向量路由和鏈路一狀態路由兩種自適應路由選擇算法來收集和處理路由信息。
RIP作為一種成熟的路由標準，在因特網中有著廣泛的應用，特別是在一些中小型網絡中。正是基于這種現狀，同時考慮到RIP與IPv6的兼容性問題，IETF對現有技術進行改造，制定了IPv6下的RIP標準，即RIPng（RIP next generation）。RIPng協議使用是距離――向量路由算法。以下介紹一下常用RIPng路由選擇算法。
二、Floyd算法[4]
Floyd算法又稱為弗洛伊德算法，是求解網絡中所有兩節點間最短路的比較有效的算法之一。是一種動態規劃算法，它的核心思路通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。
把圖用鄰接距陣G表示出來；如果從Vi到Vj有路可達，則G（i，j）=d，d表示該路長度，否則G（i，j）=inf，為了搜出最短路徑我們還需要一個距陣用來記錄所插入點的信息。這個距陣是D，D（i，j）表示從V（i）到V（j）需要經過的點，初始化D（i，j）=j，接著按順序依次將端集中的端點作為中間的轉接點，計算此點距其他各點的徑長，每次計算后都以求得的與上次相比較小的徑長去更新前一次較大的徑長，若后求得的徑長比前次徑長大或者相等則不變。以此不斷更新G和D。直至形中的數值收斂。
Floyd算法優點是比較容易理解，可以算出任意兩個節點之間的最短距離，可以以較簡單的代碼來表示該算法。該算法的缺點是復雜性比較高，數據量大是效率較低。
三、OSPF（Open Shortest Path First）協議和OSPFv3路由選擇算法[6]
OSPF即Open Shortest Path First（開放最短路徑優先），與RIP協議是距離――向量路由不同，OSPF是典型的鏈路――狀態協議，OSPFV2協議基于IPV4，用于支持IPV4服務；為了更好的支持IPV6，IETF推出OSPFv3。OSPF是一種基于區域實現的、建立在鏈路狀態（Link State）算法和Dijkstra算法基礎之上的內部網關動態路由協議。OSPFv3是該協議的第3版本，是IPV6網絡中路由技術的主流協議。
OSPFv2是基于網絡運行的，兩個路由器要形成鄰居關系必須在同一個網段。OSPFv3的實現是基于鏈路，一個鏈路可以劃分為多個子網，節點即使不在同一個子網內，只要在同一鏈路上就可以直接通話。
四、Dijkstra算法[5]
OSPF中用到的Dijkstra算法和RIP中用到的距離向量算法一樣，都是相當經典的最短路徑算法。Dijkstra算法是由荷蘭計算機科學家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。
Dijkstra算法基本原理是：每次擴展一個距離最短的點，更新與其相鄰點的距離。當所有邊權都為正時，由于不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了算法的正確性。不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質[6]。
假設每個點都有一對標號（mj，nj），其中mj是從起源點s到點j的最短路徑的長度（從頂點到其本身的最短路徑是零路（沒有弧的路），其長度等于零）；nj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下：（1）初始化。起源點設置為：①ms=0，ns為空；②所有其他點：mi=∞，ni=?；③標記起源點s，記k=s，其他所有點設為未標記的。（2）檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，并設置：mj=min［mj，mk+lkj］式中，lkj是從點k到j的直接連接距離。（3）選取下一個點。從所有未標記的結點中，選取mj中最小的一個i：mi=min［mj，所有未標記的點j］，點i就被選為最短路徑中的一點，并設為已標記的。（4）找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點，設置：i=j*（5）標記點i。如果所有點已標記，則算法完全推出，否則，記k=i，轉到2）再繼續。
RIPng協議和OSPFv3協議作為IPv6網絡使用較多的內部網關路由協議，具有出色的路由能力。這兩種協議都是IPV4網絡協議基礎發展而來，但是網絡協議還需考慮傳輸容量和服務質量，還要分析全網負荷，平衡各條通道的數據流量等諸多因素的，因此RIPng協議和OSPFv3協議還需進一步的研究和優化。
參考文獻：
[1]Y.Rekhter,T.Li,An architecture for IP address allocation with CIDR,RFC 1518,1993,9
[2]M.Degermark,A.Brodnik,S.Carlsson,and S.Pink,Small forwarding tables for fast routing lookups,In:Proc.of the ACM SIGCOMM’97,Cannes France:ACM Press,1997,9:3-14
[3]伍海桑,陳茂科.IPv6原理與實踐[M].北京:人民郵電出版社,2000
[4]來強,基于V-D算法的RIP協議及其設計[J].現代電子技術,2002,l:51-53
[5]李琨.RIP協議分析與仿真研究[J].計算機工程,2002,28(3):85-87
關鍵詞:改進蟻群算法;網頁分類;支持向量機;貢獻函數
中圖分類號:TP391文獻標識碼:A文章編號:1009-3044(2009)35-10069-03
Study of Categorization of Web-Page Based on Improved Ant Colony Algorithm and Support Vector Machine
SONG Jun-tao, DU Qing-ling
(Dept. of Information Science and Engineering, Henan University of Technology, Zhengzhou 450001, China)
Abstract: Web page categorization is an of web data mining, it is a typical application based on technology of natural language processing and machine learning. It is imperative to find a effective and efficient method for web page categorization. In this paper, a new method is proposed for web page categorization based on improved ant colony optimization algorithm (IACOA) and support vector machines (SVMs).The experimental results show that the method is effective and robust, only to make up for the use of support vector machines for large sample training set less than the slow convergence with better precision and recall.
Key words: improved ant colony algorithm (IACA); web page categorization; support vector machine (SVM); contribution function
隨著計算機網絡技術的快速發展和Web 2.0廣泛深入的應用,同時互聯網上的信息呈指數級增長,人們可利用的網絡信息也越來越多,如何從這些海量的信息中高效的獲得所需信息已成為當前必須解決的問題。bayes分類、關聯規則、決策樹分類、單純的支持向量機算法[7]等在文本分類中得到廣泛的應用并取得了很大的進步,與文本分類最大的不同在于網頁屬于半結構化數據且數量極大,先前的文本分類算法直接引用到網頁分類中,其分類精度和效率受到一定的影響,特別是大規模樣本適應性不強,收斂速度慢。支持向量機分類最大的優點在于構造一個最優超平面,且有強大的統計理論基礎,分類精度高,因此在分類中得到廣泛的應用,但對于大規模樣本訓練過程中,表現出適應性不強,收斂速度比較慢的不足,為此本文提出了基于蟻群算法和支持向量機的網頁分類方法。
1 SVM基本原理和蟻群算法
1.1 SVM基本原理
支持矢量機(Support Vector Machine,SVM)[1]是Vapnik等人于20世紀90年代中期提出的一類新型機器學習方法, 其理論基礎是統計學習理論。與基于經驗風險最小化原理的傳統的統計學習方法不同,SVM基于的是結構風險最小化原理。SVM不僅結構簡單,而且各種技術性能尤其是推廣能力比神經網絡等方法有明顯提高。標準的SVM的實現涉及求解線性約束的二次規劃問題,該問題可以收斂到全局最優解。但當訓練數據很多時――這是很多實際問題所碰到的情況,二次規劃問題的求解受到存儲器容量的限制,而且分類速度也得不到保證,從而限制了SVM在很多問題上的應用。常用的做法是將問題分解為若干個子問題,然后再對這些子問題進行逐一優化。這樣做的缺陷是:結果可能只是一個次優解,并且分解的時候可能需要多次分解才能將問題的規模轉化為能解決的程度。
1.2 蟻群算法簡介
蟻群算法[2](Ant Algorithm)由意大利人M.Dorigo等人首先提出的,蟻群算法是一個新的啟發算法,蟻群算法固有的并發性和可擴充性,使它非常適合用于帶約束的二次優化求解問題。在同一時間內,所有影響資源狀態的因素都能由一個事情,即信息素描述。進而能夠非常簡單、快速地獲得預測結果。
該算法按照啟發式思想,通過信息傳媒Pheromone的誘導作用,逐步收斂到問題的全局最優解,是求解適應性計算問題的一種有效方法。由于帶約束的二次規劃求解問題是眾所周知的NP問題,而大量的實驗表明,蟻群算法是一種有效的求解NP類問題的新型算法,具有較強的魯棒性和內在的分布并行性,且易于和其他方法相結合。蟻群算法還有一個很大的優點就是具有可擴展性。所謂可擴展性指的是在原有一個規模n的問題上求出最優解后,再增加m個節點,可在原有解的基礎上快速找到該問題的n+m規模的最優解,本文將蟻群算法與支持向量機結合充分保證支持向量機分類精度同時彌補其針對大規模訓練樣本收斂慢的不足。
2 ACA及SVM在網頁分類中的應用
2.1 網頁文檔預處理
網頁中數據最大的特點是半結構化,數據呈現形式多樣化,首先用向量空間模型(SVM)[4-5]表示Web頁面數據信息,本文采用TFIDF[6]向量表示方法,并非所有特征對分類都有用,況且不同的特征所起的作用也不一樣,預處理階段最重要的是關鍵特征提取及降維,直接影響到后續分類的精度。
2.2 SVM訓練及ACA優化求解流程
首先將樣本集分為訓練集(80%)和測試集(20%)兩部分,訓練集專門用于SVM訓練,而測試集專門用于評價測試SVM分類性能,其中影響SVM分類性能的兩個重要參數是折衷參數C和高斯核函數K(xi,xj)=Ф(xi)Ф(xj),訓練過程中,不斷地調整參數C,同時利用上述蟻群算法對高斯核函數進行優化,最終選取合適的參數值,整個過程利用上述蟻群算法對SVM分類器函數優化求解,輸出分類結果,整個分類過程如圖1。
2.3 SVM[8-10]訓練算法描述
1) 假設待訓練樣本集為T={(x1,y1),(x2,y2),…,(xi,yi)} 其中xi∈Rn,yi∈{1,2,…M} i=1,2, …,n
2) SVM算法的出發點是利用核技巧在高維空間里進行有效的計算,找出支持向量及其系數構造最優分類面。而此最優分類面的構造問題實質上是在約束條件下求解一個二次優化問題,以得到一個最優的決策函數,最優分類超平面為:
決策分類目標函數為:
3) 最優分類超平面問題描述為:
b是一個閾值。
4) 其對偶最優化問題為:
αi為二次優化問題的最優解,其中,K(xi,xj)=Ф(xi)Ф(xj)稱為高斯核函數,n為訓練樣本個數,C為懲罰因子,它控制的是訓練錯誤率與模型復雜度間的折衷。容易證明,該優化問題的解中只有一部分(通常是很少的部分)αi不為零,這些不為零αi的對應的樣本就是支持向量,只有支持向量影響最終的劃分結果。
2.4 蟻群算法[3-9]求解步驟:
算法優化求解開始時,訓練集中的每一個樣本點對應一個螞蟻智能體,從t=0時刻開始第一輪搜索,當t=l時所有螞蟻遍歷所有樣本點,完成了第一輪搜索。此時更新路徑上的信息素,并將禁忌表清空。然后開始下一輪搜索,在達到用戶設定的最大搜索輪數NC時,算法終止,此時找到的最優解作為問題的最優解。
1) 初始化:設定t=0,循環輪次數NC=0,對每條路徑設置ζi(0)=C和Δζij=0,將m只螞蟻均勻放置n個訓練集中。
2) 設置s=l(s是禁忌表的索引),對k=l,…,m,將第k只螞蟻所在的樣本點的編號放入禁忌表中。
3) 在禁忌表索引s≤n時,重復如下操作:
① s=s+i;
② 對k=1,…,m,做如下工作:依照公式
計算螞蟻在樣本點i選擇第j個樣本點作為下一站的概率,并按概率選擇樣本點,將螞蟻移至該樣本點,將其編號放入禁忌表中。
4) 對k=l,…,m,做如下工作:計算第k只螞蟻走過的路
徑長度,記錄當前找到的最優解,按公式
計算每只螞蟻的信息素增量。
5) 對所有的點(i,j)根據公式
更新路徑上的信息素。
設置t=t+n;NC=NC+1;設置所有的Δζij=0,
6) 如果NC≤NCmax或者沒有出現收斂現象,設置它們的禁忌表為空;轉到第2)步;否則,輸出最優解,算法結束。
2.5 改進蟻群算法
2.5.1 貢獻函數的引入及優化信息素平滑機制
蟻群算法在螞蟻對路徑進行探索之前,會對每條路徑上的信息素含量進行初始化,即每條邊的信息素含量具有相同的賦值。螞蟻在進行路徑選擇的時候,主要是憑借路徑的長度和信息素的含量來計算選擇該條路徑的概率,而在算法的起始階段,各條邊上的信息素含量是沒有差異或者差異很小。這樣就導致了螞蟻在最初階段僅僅憑借路徑的長短來對路徑進行選擇,然后再在選擇的路徑上留下信息素,從而吸引后續的螞蟻繼續對這些路徑進行探索。這種機制會使螞蟻盡可能的選擇長度較短的邊來構造整個路徑,它使得螞蟻在路徑選擇時只對局部的優化進行考慮,而忽略了全局,形成“近視”現象,在開始階段,每條邊上的信息素含量是相同的,螞蟻僅根據路徑的長度來進行概率性選擇。一種被稱作信息素平滑的機制首次被提出,它使得算法在接近收斂時能夠減小各條邊之間的信息素含量的差異,從而保證螞蟻對解空間的探索行為不會集中在一個相對較窄的范圍之內。為了更好的分析、改進這種機制,首先簡單介紹一下蟻群算法的收斂條件。
從前面的分析可以看出,隨著蟻群對路徑探索的深入,也就是循環次數的增加,信息素的更新和揮發使得邊之間的信息素含量的差異將會變得越來越大,最終導致以每個城市為起點的邊集合中只有一條邊上的信息素含量值保持在一個較高的水平上。由于信息素的揮發機制,其它的邊幾乎不對螞蟻的選擇過程產生影響。這種情況被稱作算法收斂[11],具體的定義如下:
定義2.1 τ(i,j)以i為起點的所有邊的集合上的信息素含量值,τmax(i,j)=argmax{τ(i,j)},τmin(i,j)=argmin{τ(i,j)},使信息素含量最大、最小值之間的差ζr=τmax(i,j)- τmin(i,j)。令τ=λζr+τmin(i,j),其中λ∈(0,1),那么點i的λ-branching就定義為集合{τ(i,j)τ(i,j)>τ
由定義2.1可以看出當信息素含量差異越大時,λ-branching的值越小。所有點的λ-branching的均值就表明了算法的收斂程度,均值越接近1,算法越接近收斂狀態,即當meanλ-branching =l時,算法收斂,也就是說螞蟻不再對新的解空間進行探索,最終結果將被獲得。當算法非常接近收斂的時候,信息素平滑機制允許每條邊上的信息素含量根據一定的比例進行增加,從而減小差異,保持螞蟻對新的解空間的搜索行為。平滑公式如下:
其中,τij和τ*ij分別為平滑前后邊(i,j)上的信息素含量,δ∈[0,1],τmax為最大的信息素含量。當δ∈(0,1)時,螞蟻對路徑的認識信息,即信息素含量,并沒有完全丟失,而只是被弱化了:當δ=0時,平滑機制對于信息素含量沒有任何影響;當δ=1時,每條邊上的信息素含量都被設定為一個固定的值τmax。
但是,信息素平滑機制并沒有考慮到邊是否對于構造更好路徑有幫助。這樣那些有幫助的邊沒有得到足夠的信息素增強,同時那些沒有幫助,甚至可能對后續螞蟻的選擇過程產生負面影響的邊上的信息素含量則得到了增強,從而使它們被選擇的機會大大增加。這兩個方面的影響都會在一定程度上降低算法的性能。因此,有必要引入貢獻函數來對平滑機制進行改進,使得貢獻函數大的邊能夠獲得更多的信息素增量,而使那些沒有貢獻,甚至對構造更好的解產生負面作用的邊獲得較少的更新,以便螞蟻在后續的探索過程中更多的探索貢獻函數值比較大的邊,從而構造出更好的路徑。改進后的信息素平滑公式如下:
其中,(i,j)是邊(i,j))的貢獻函數。
2.5.2改進蟻群算法描述
網頁分類的目的是從訓練數據集中提取出IF-THEN規則,蟻群算法通過對每個屬性域中的屬性值集合的選取完成分類規則的構建,算法描述具體步驟如下:
1) 清空規則列表,構造訓練集;
2) 初始化信息素和啟發式函數;
3) 放置螞蟻,開始對屬性值集合進行選取,構造分類規則;
4) 對構造的規則進行處理,刪除不相關的屬性;
5) 根據構造的分類規則的好壞進行信息素更新,若滿足終止條件,進行第6步,
否則進行第3步;
6) 將提取出的分類規則加入到規則列表中,若提取的分類規則可以涵蓋足夠的訓練數據集中的數據,算法終止,否則,進行第2步。
3 實驗結果與分析
3.1 試驗結果
本文試驗在MATLAB7.0 環境進行仿真,數據采用10000篇網頁文檔(根據網頁主題內容共分10個大類別),通過預處理后從中隨機抽取20%用于測試評價分類器的性能,剩余80%用于訓練,如圖2是在本文方法在訓練過程中分別對不同的核函數(多層感知器核函數a、多項式核函數圖b,高斯核函數圖c)進行優化的分類效果圖,結果表明本方法選用高斯核函數在網頁分類(特別是高維空間訓練集)中效率比較高,明顯由于其它兩種核函數。
本文提出的方法與其它SVM分類方法相比,在訓練樣本規模較小時分類精度沒有明顯的區別,但隨著樣本規模的增大,本文的方法在保證分類精度的同時適應性有明顯提高,彌補了SVM本身針對大樣本適應性方面的不足。
3.2 分析評價比較
表1是本文提出方法與其它兩種方法在準確率、召喚率、宏平均和微平均方面的比較。
本文采用傳統的評價方法:正確率(P),召喚率(R)和F1值來衡量分類的效果,其中
li,mi,ni分別表示第i(i=1,…,10)類分類結果中正確的網頁數目,實際包含的網頁數目和結果中出現的數目。微平均計算方法如下公式:
4 結束語
本文利用改進蟻群算法和支持向量機理論相結合,提出了基于改進蟻群算法和支持向量機的分類方法,對尋求構建高效的網頁分類器進行了研究,并與傳統的分類算法如bayes算法、蟻群算法和支持向量機算法等進行分析比較,結果表明該方法應用在網頁分類中在有效性、準確性有明顯的改善,尤其在大規模訓練集中適應性更強。該方法在提高搜索引擎的速度和質量方面有很大的應用空間,是進一步學習研究的重點。
參考文獻:
[1] VAPNIK V.Universal Learning Technology: Support Vector Machines[J].NEC Journal of Advanced Technology,2005(2):137-144.
[2] 段海濱.蟻群算法原理及應用[M].北京:科學出版社,2005.
[3] 朱剛,馬良.TSP問題的蟻群算法求解[J].計算機工程與應用,2007,43(10):79-80.
[4] CHEN P H,LIN C J,SCHLKOPF B.A tutorial on v-support vector machines[J].Applied Stochastic Models in Business and Industry,2005,21(2):111-136.
[5] Chang Chin-chang.Lin Chi-hjen.LIBSVM: a Library for support vector machines[J/OL].csie.ntu.tw/~cjlin/libsvm.2005.
[6] Mlademic D, Grobelink M. Feature Selection on Hierarchy of Web Documents[J].Decision Support System,2006(35).
[7] 賈s,梁久禎.基于支持向量機的中文網頁自動分類[J].計算機工程,2005(5):18-22.
[8] 彭濤.基于粒子群優化算法的網頁分類技術[J].計算機研究與發展,2006(6)33-38.
[9] 許建潮,胡明.中文web文本的特征獲取與分類[J].計算機工程,2005(4):24-26.
關鍵詞：配送；路徑優化；節約里程法
中圖分類號：F252.24 文獻識別碼：A 文章編號：1001-828X（2017）012-0-02
一、順豐速運現狀分析
順豐速運于1993年成立于廣州順德，目前已發展成為業務覆蓋全國的包括港澳臺地區的大型物流配送公司。為保障物流的時效性，順豐一半實行通宵作業，所有晚上攬收的快件，將在當晚至凌晨完成全部的分揀，裝運等工作，凌晨已準備或已經通過空運或陸運開始運輸。在配送方面，順豐搭建了自建的物流體系，在全國建立了華北、華南、華東三個分撥中心，保障全國不同區域的的快件能夠在打到中心區之后快速送達輻射區域內：主要的一線城市之間每天均有兩趟的包機專線運送，保障了空運的快件能夠及時周轉至下一環節；在城市內部，順豐也建立了多個分撥中心，每天多個批次運送快件至各個快遞網點，保障物流配送的“最后一公里”時效不受影響。
1.順豐公司發展現狀
從順豐的配送來看，主要分為城市間運輸、城市內配送、終端配送等多個環節。城市間運輸依靠極為高效不間斷的分揀裝運流水線完成作業，快速將快件通過空運或陸運送出。城市內配送主要依靠往返于市內各分撥中心與營業網點之間的車輛保障運送，由于快件量多，每天需要運送的快件變動量大，實時的交通運輸條件有較大差異，因此這一環節受到各類影響因素的作用最大。終端配送工作由快遞員負責，主要通過高標準的員工培訓及績效獎勵保證工作質量，因此有著極高的時效性保障。
2.順豐配送的特點與需求
目前順豐的配送特點有：
（1）有完善的貨物追蹤系統，高效便利的呼叫中心，使客戶可以快捷方便的進行網上自助服務。
（2）有安全的運輸服務保障，擁有自營的運輸網絡，為客戶提供高效、高質、快速、安全的服務。
（3）有很大一部分責任心強，積極上進的員工。
（4）有良好的物流配送網絡，配送覆蓋面積大。
（5）有專業的o2o與DDP服務，網上、電話訂單，迅速傳達，快速靈活的門到門服務。
（6）有良好的客戶資源和品牌口碑。
在配送方案的規劃目標方面，保障速度最快、時間最低的條件下成本最優是其基本原則。順豐相較于國內其他同行企業收費較高，費用的溢價主要用于保障整個配送過程以及設施的投入方面，保障快件的效率才是順豐的第一服務原則。基于此，可以了解到順分在配送方面的優化需求在配送環節中的成本降低，有效的規劃其配送路線為基礎，本文對這一條件下的配送路線優化進行了研究分析
3.順豐配送路徑中的問題分析
從順豐配送的主要流程來看，城市內部的車輛配送受到的影響因素較多，由于受到道路擁堵等問題的影響，終端的配送由營業點快遞員完成，其配送路線較為自由隨機，以快遞員對工作便利及效率的判斷為主要標準。需要進行動態的方案規劃。
以北京市為例，在北京市內的配送過程中，避免不了的是車輛擁堵問題，現代化的交通設施和出行方式使得交通運輸壓力很大。在配送專業人才欠缺的情況下，無法高效的利用配送優化方法來解決物流配送路線的壓力是現在順豐配送的問題所在。在既要滿足配送時間合理的情況下，同時需要降低配送的成本是重中之重。
在配送方案的規劃目標方面，保障速度最快條件下的成本最優是其基本原則。順豐速運在國內收費較高，費用的溢價主要用于保障順豐對基礎服務設施的投入以及對員工的績效保障上，保障快件運送效率是順豐運作的第一原則，在此基礎上才考慮成本經濟。基于以上分析，可以了解到順豐速運在配送方面存在優化需求的主要環節是城市內的車輛配送，其規劃目標是速度最優條件下的成本最優，以此為基礎，本文對這一條件下的順豐配送路線優化方案進行了分析。
二、配送路線優化方法
1.路徑規劃的主要優化方案
路徑規劃問題（Vehicle Routing Problem，VRP）是在1959年有Dantzig以及Ramser提出的，VRP問題是一類典型的NP-C問題，該問題需要滿足一定數量客戶同一時間內的不同配送需求，配送的需求同時要滿足時間最快、成本最低、客戶滿意度最高等多種約束條件。由于問題復雜，約束條件多，該問題一直以來吸引了較多理論研究的關注，并不斷的改良算法，尋求最優的解決方案
在針對順豐速運的物流配送優化方面，本文主要針對順豐的配送中心與各營業網點之間的配送路線進行優化，在實際的問題中，需要針對動態因素的改變來調整算法
2.基于條件控制下的節約里程模型
運用最短路徑算法確定貨物始發點，并確定幾個收貨點，確保一下幾種事項：（1）配送總里程最短；（2）單車貨物不超載；（3）滿足用戶的需求；（4）每天每車的運輸里程不超過最大規定里程。
圖2-1 圖2-2
如圖2-1與圖2-2所知，圖2-1的行駛總里程為2a+2b+2c，圖2-2的行駛總里程為a+d+e+c。計算圖2-1總里程減去圖2-2總里程即可得出最優方案：2a+2b+2c-（a+d+e+c）=a+2b+c-d-e。由三角形兩邊之和大于第三邊得出：a+b>d；b+c>e，所以a+2b+c-d-e>0，即圖2-1總里程大于圖2-2總里程，圖2-2為最優方案。
通過節約里程模型分析可知，利用節約里程法可以降低配送時間、配送成本，使原本多條配送路線閉合成回路縮短行駛路線。在企業將來的發展中可以獲得更大的經濟效益。在減少配送時間與配送距離的同時，也是為環保做出一份貢獻，不僅僅推動了企業的發展，更是進一步的使國民生活質量得到了改善。
三、結語
由于順豐速運將快件配送的速度保障作為工作的第一要素，因此在所有的配送過程中，城市內配送中心想各營業網點的配送速度成為了快件配送r效性的決定因素。本文以順豐城市內配送方案為研究對象，結合節約里程法總結出該方案的可行性，配合方案能夠對順豐速運的配送路線進行合理優化，對于提升配送速度，節約配送成本有著較為顯著的效果，同時有著較好的時間解決意義。
參考文獻：
[1]張紅霞，黃曉霞.物流企業配送車輛調度問題研究綜述[J].電腦知識與技術，2009（13）.
[2]柳伍生，劉軍.一種改進節約發在車輛配送路徑優化中的應用[J].現代交通技術，2007（6）.
[3]魏寶紅淺析我國電子商務中物流配送存在的問題及對策[J].現代交通技術，2007（6）.
[4]袁清平.物流企業配送系統系統優化研究[D].西華大學管理學院，2008.
關鍵詞:群體動畫;真實感行為;認知建模;行為建模;群體動畫
中圖分類號: TP391.41; TP391.9
文獻標志碼:A
Survey on realistic behavior in crowd animation
RAO Yun-bo, CHEN Lei-ting, ZHOU Jun, LI Yan-mei
英文地址(
School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China
Abstract:In recent years, computer crowd animation has been widely used in various applications such as virtual reality, computer game, education, amusement, and simulation training. The critical two areas of crowd simulations include: the first one is focusing on the simulation model of large crowd motion that is how to simulate realism behavior in crowd animation; the second one is high-quality visualization that is how to regularly use virtual scene in large crowd motion by 3D model. Some wonderful results have been achieved in the two areas. The authors presented the definition of crowd animation and structure of crowd animation, gave a survey on realism behavior in crowd animation from crowd simulation timeline, crowd modeling and crowd simulation algorithms. At last, the authors also presented the conclusions and discussed the prospect
Key words:crowd animation; realism behavioral; cognize modeling; behavioral modeling; crowd motion
0 引言
近年來,計算機圖形學得到了極大的發展,同時隨著數字媒體處理技術的迅速發展及計算機硬件成本的進一步降低,計算機動畫技術及其相關應用得到有力推動與普及,特別是計算機群體動畫被廣泛地應用于虛擬現實、計算機游戲、在線教育、娛樂、模擬訓練等多個領域。第一個群體概念是Amkraut等人[1]提出的。所謂群體是指兩人或兩人以上的集合體,他們遵守共同行為規范、情感上互相依賴、思想上互相影響、有共同奮斗目標。而所謂群體運動[2]是指在場景中有大量的群體,這些群體做著大致相同的行為,即他們擁有同一個目標,但是仔細觀察每個個體的動作和造型,又會發現他們存在細微差異。第一個可編程群體動畫模擬(虛擬鳥群)是由Amkraut S等人在一部名為Eurhythmy的電影中實現的。
在真實世界中,組群是普遍存在的。在查閱文獻[3-4]等后,把群體動畫研究的應用及每個領域的研究者歸納如圖1所示。根據圖1可見群體動畫的研究不只是在計算機圖形學領域,而在其他學科諸如:社會學、心理學、工程學和計算機視覺等領域都有相應研究。從圖1中可以看到群體動畫應用到了群體管理(檢閱系統、暴亂處理系統)、公共空間設計(建筑物和城市規劃)、虛擬環境群(動畫動漫、計算機游戲和電影等)、智能環境(組群行為學)和視覺監視等領域。
圖片
圖1 群體動畫的應用領域和研究者
目前國內關于群體動畫的研究工作較少。主要有:電子科技大學研究虛擬環境下群體動畫實時模型與繪制技術,研究內容是構建一個群體動畫通用引擎模塊,包括群體行為模擬及群體渲染兩個部分,并在此基礎上實現群體行為驗證演示系統;中國科學院虛擬實現技術實驗室研究支持大型公共設施安全問題研究的虛擬現實系統,研究內容是場景快速建模、人群行為模擬、大規模虛擬群體繪制、火(煙霧)運動模擬與繪制等;浙江大學數字媒體計算與設計實驗室研究虛擬人運動與表情建模,研究內容是運動捕獲數據的分析、檢索、合成,人臉表情跟蹤、分析與再生、超分辨率生成、人臉重建人臉幻想;另外還有微軟亞洲研究院的群體動畫研究。國外關于群體動畫研究相對較多。主要有:斯坦福大學基于群體行為在危急環境中的緊急撤離和個體的角色表現的研究;GEOIDE和加拿大圖形網絡中心基于警察和軍隊的組行為,開發模擬群體行為的研究;利物浦大學心理學院和荷蘭警察研究院基于群體與群體之間的沖突及交互模擬的研究;英國EPSRC基于人群運動和密度對潛在的危險位置,以及正常人和犯罪人行為的研究;歐盟PRISMATICA和ADVISOR基于人群在公共場所的運輸流動研究;歐洲ICT財團ISCAPS基于區域類人群的自動安全監視系統的研究;以及歐盟支持的SERKET基于模擬群體恐怖防護的應急系統的研究。
雖然關于群體動畫的研究者多且存在于不同的領域,而且在計算機方面群體動畫國內外的研究工作也很多,但是關于計算機群體動畫真實感行為綜述的文章在國內外發表較少,部分綜述存在于文獻[5-11]中,但是不夠完善。本文的貢獻在于:1)明確了群體運動的概念;2)提出了群體動畫的引擎框架,并對計算機群體動畫研究進行分類;3)根據群體動畫的發展歷程對群體動畫的研究工作進行歸納;4)對群體動畫的典型建模進行分析與總結;5)歸納了群體動畫在真實感行為方面的主要研究算法;6)利用給出的群體動畫框架在理論上探索新的計算機群體動畫真實感行為研究方向。
1 群體動畫的引擎框架
在綜合研究文獻[3-4,12]后,歸納了如下的群體動畫研究方向。
1.1 群體動畫研究領域(方向)
目前群體運動技術中三個關鍵的研究方向是:1)研究并建立大規模群體運動的仿真模型,即如何實現對群體運動的真實感行為模擬;2)研究群體動畫中高質量的可視化效果,即如何將大規模群體運動以三維的方式逼真地展現到虛擬場景中,這些都要依靠計算機的硬件繪制能力;3)真實感行為與可視化效果的混合研究。真實感行為模擬研究通常可以通過簡單的2D可視化來對群體運動進行模擬,比如撤退模擬、社會群體模擬。在該領域中模擬的行為通常從一個有限的、可控制的效果到特定情況下的真實世界群體運動。在理想情況下,模擬的結果和真實人群運動相一致。研究質量的可視化效果的目的是使得群組中個體的行為和外貌產生多樣性,同時提高場景的渲染速度。比如在電影作品創作和計算機游戲中的群體運動模擬,在這種情況下,真實感行為模型的真實性就不是太重要,而令人信服的視覺效果才是所關心的重點。真實感行為與可視化效果的混合研究領域中,面向可視化效果的群體系統嘗試融合更好的行為模型,從而簡化令人信服的動畫創作,而面向行為的群體模型則嘗試達到更好的可視化效果,尤其是在撤退模擬領域的研究。總之,群體運動要求群體真實感行為的有效性和高質量的可視化效果。
1.2 群體動畫引擎框架
通過對群體動畫研究文獻分析。圖2給出了一種群體動畫的引擎框架,用于描述群體動畫的研究方向、技術和綜述的模塊。該引擎主要考慮了群體動畫的真實感行為模擬與高效的可視化效果兩個方面。框架包含三個模塊:群體動畫管理器模塊、真實感行為模擬模塊和群體動畫高效的可視化效果模塊。群體動畫管理器用于對群體的真實感行為模擬模塊和群體動畫高效的可視化效果模塊進行管理,需要考慮群體所在的虛擬環境的復雜性、群體角色可視化方法和真實感行為模型等方面。真實感行為模擬模塊包括5個基本建模:基于行為的建模、基于認知的建模、基于虛擬環境的建模、基于人群建模、基于角色的群體建模(將在第3章介紹)和兩種算法:基于路徑規劃算法、基于碰撞避免算法(將在第4章介紹)。群體動畫的高效的可視化效果模塊,主要用于加速復雜虛擬場景繪制速率,提高計算機實時渲染能力的主要技術有[5,9]:可見性剔除技術、基于幾何的圖形繪制和加速技術、基于圖像的繪制加速技術和基于可編程圖像硬件(GPU)的加速渲染技術。
2 基于發展歷程的群體動畫真實感行為模擬分析
群體動畫真實感行為的研究開始于19世紀,但是嘗試用計算機建模來模擬群體行為則是最近才開始的。近幾年來,群體真實感行為方面的研究者涉及的領域非常廣泛,比如建筑學領域、計算機圖形學領域、物理學領域以及社會學領域都一直在進行關于群體真實感行為的研究。
引言從社會學的角度給出了群體和群體運動的概念。在參考文獻[13-14]后,從計算機圖形學的角度對這個兩個概念進行定義。
Фㄒ1 設F是群體函數,I為群體的集合。pi為個體,則群體集合P′可以表示為:
F(p1,p2,…,pn)=p′; p′∈I(1)
其中P′為值域,表示一個群體。要求P′燎sum(P′)=p1+p2+…+pi≥2,pi={r,e,j,g},r表示群體遵循的規則,e表示群體感情和精神上依托,j表示群體交互,g表示群體共同的奮斗目標。
通過對群體的定義和理解,給出群體運動的定義。
定義2 設F是群體運動評估函數,pi為個體,G(pi)為第i個個體運動評估函數,則群體運動可以定義為:
F(p1+p2+…+pn)=G(p1)+G(p2)+…+G(pn)(2)
其中F(p1+p2+…+pn)表示群體運動的評估值總值。現在根據個體運動情況和約束來對G(pi)進行分解。假設每個個體從原點到目標地點的時間為t∈[0,T],距離為s,則:
G(pi)=∏t∈[0,T]f(α∫so1ds+β∫To1dt+γ∫ToGdt)(3)
其中:α∫so1ds為個體從原點到目標地點的距離;β∫To1dt為個體從原點到目標地點的時間;γ∫ToGdt為個體從原點到目標地點時產生的運動舒適度(主要指運動個體的約束,如:碰撞、外形、個體質量、個體速度和運動方向等);α,β,γ為權重系數。
通過對群體及群體運動的定義,圖3給出了一個群體動畫發展歷程的主要研究成果及群體動畫的主要研究者。
Amkraut等人[1]在1985年SIGGRAPH的The Electronic Theater中提出群體動畫概念。他們的工作是采用鳥群運動的全局向量力場來完成,并且使用這個技術在Eurhythmy的電影中第一次實現了可編程虛擬鳥群的群體動畫模擬。人類群體的真實感行為模擬或者說具有人特點的群體模擬都是以那些更為簡單的實體群體模擬為基礎的,特別是鳥群的模擬[15]和魚群的模擬[16]。
在1987年SIGGRAPH的The Electronic Theater中Reynolds[15]提出boids系統,首次完整給出了一個群體行為控制的模型,其目的是為自治主體群給出一種類似鳥群、魚群或蜂群等群體行為的逼真形式。Reynolds提出了基于規則(中心吸引力、速度跟隨、相互排斥力)來模擬簡單個體組成的群落與環境以及個體之間的互動行為,其所實現的群體行為動畫可以獲得突現行為效果。后來,Reynolds擴展了他的工作,引入了指導行為的目標尋找、躲避障礙、路徑跟進和分散等策略對群體動畫進行處理。
Tu等人[16]提出基于自然生命模型的動畫生成方法,把魚作為自主智能體,創作了包括生物力學模型、幾何顯示模型、感知模型、動機模型和行為選擇機制在內的人工魚模擬動畫系統。通過固定的、具有優先級的規則在一系列基本行為中進行選擇。這些規則包括:避開障礙物、進食、求偶、逃跑、游戈和離開等。實現了魚的捕食、求偶、集群和逃逸等生物活動,是基于Agent的群體動畫的典型代表之一。Funge等人[17]對Tu的工作進行了擴展。對行為動力學中的諸如“刺激―響應”等進行模擬,同時也模擬了感知系統中的知識和學習過程。對于感知系統,Shao等人[18]又進一步擴展到了步行者的視覺范圍和尋道方面。
Brogan等人[19-20]基于規則組合的模型通過對各種場的構建以及個體間、個體與環境間各種力的按規則生成和組合來實現個體的避障。算法分為兩個步驟:第1步,感知模型決定個體和障礙物是否都可視;第2步,安置算法決定為每個運動個體獲取位置和個體與障礙物的速度。由于連續的設定、計算復雜性、系統平衡性的制約以及穿透矯正行為的缺失,它們都沒有徹底解決個體間可能出現的穿透問題。其中Lakoba等人[21]和Treuille等人[13]分別提出了一種用來矯正穿透的方法,但存在算法上的局限,依然無法徹底避免穿透。
Bouvier等人[22-23]使用了一種與鳥群模擬相似的方法來模擬人群。他們將粒子系統與轉換網格相結合,用來模擬虛擬城市中的人群。在低層行為,類似于物理電子學中的吸引力和排斥力使得人群在所處的環境中移動。群體目標的一致性產生群體個體之間的相互吸引力,而障礙物則產生群體個體之間的排斥力場。高層行為則通過轉換網格進行模擬,在該轉換網格中轉換依賴于時間、對某些點的訪問、局部人群密度的改變以及全局事件等。
Musse等人[24-25]針對虛擬人群的實時模擬提出了一種層次模型。該模型是基于組的,而不是基于個體的。組是一種更加智能的結構,每一個組都由不同的自治水平來控制:可指導的群體可在運行時遵循由用戶指定的順序;可編程的群體則遵循預定制好的行為;而自治性的群體則使用事件和反作用力來產生更加復雜的行為。群體所處的環境則是由一些標識目標與路徑的信息點集合一些動作點集組成,如在到達目標以后需要做的動作點集合。
Ulicny和Thalmann等人[26-27]提出了一種基于層次的群體動畫規則。在他們的系統中,行為捕獲通過層次來決定其行為規則,而行為的執行通過層次的有限狀態機處理。
Niederberger等人[28]對群體模擬的應用提出了一種分層次的體系結構。在該體系結構中,群體行為是通過對現有行為類型的特殊化和對新類型的繼承來定義的。每一組的結構是通過遞歸和基于模式,而行為引擎為了保證最小的幀率,則需要考慮每次運行時所需要的最大時間量。
Treuille等人[13]使用一個全局的動態勢能場處理變化的環境,同時考慮了人群的密度、人群的速度、地勢高低以及舒適度的問題,將局部的碰撞避免和全局的路徑控制結合在一起,但要求以組為單位進行模擬,組內的個體擁有相同的運動特性,有效地解決了在沒有明確碰撞規避機制的情況下,大量虛擬人群的運動,但只能是在二維的環境中進行,如圖4所示。
圖片
圖4 城市各種模擬方案[13]da Silva等人[29]提出了運動風格克隆。在動態環境中創作自然人體運動因為其復雜的幾何和物理作用而變得困難,提出了在交互狀態下通過規則的控制計算來克隆運動風格。只要給出運動的參數和期望的目標,控制系統就能模擬和克隆出新環境,且產生的高質量運動可以與幾何和物理的環境模擬保持一致。關于運動克隆的文章,在2008年McDonnell等人[30]也提出了外形的克隆,在大規模人群中通過模板風格進行克隆。
Kwon等人[31]提出了一個依靠個體運動的軌跡及維持相鄰個體整體的組運動編輯。用戶可以通過拖拉個體來改變組的運動軌跡。多個組的運動能夠被整合成一個長的或者大的運動,采用了一種地圖的結構,頂點表示指定針的個置,邊表示鄰接個體的排列和移動的軌跡。Kim等人[32]擴展了Kwon的工作,提出了同步的多個體運動編輯方式,針對多個體交互時候存在的線形約束,采用了拉普拉斯方法。
3 群體動畫建模
動畫的建模在計算機圖形學上按照層次等級方式進行歸納。最早的動畫模型是幾何模型,然后是前向和逆向的運動學建模,接著是基于物理的模型,最近在創作動畫方面提出行為建模,即個體對環境刺激和感知產生反映。最高層次的建模:認知模型,即獨立的個體能對給定的目標和自由的動作產生反映。具體結構如圖5所示。
圖片
圖5 動畫建模層次歸類[41]
對于群體運動的建模也遵循圖5所示的動畫建模分類,但是在群體運動中考慮如下因素:1)基于人群的群體運動模擬較多,且人是自然界最復雜的智能體,日常生活中的每一件小動作,如飲水、購物,其背后都隱含著復雜的感知和決策過程,在這些方面人類對于自身認識還相當不夠;2)環境對群體運動模擬的影響比較大;3)不同的角色在不同虛擬環境中對群體運動個體的影響比較大。
基于以上分析和群體動畫引擎框架,在這里把群體動畫的建模分為五類:基于行為的建模、基于認知的建模、基于虛擬環境的建模、基于人群建模和基于角色的群體建模。下面將介紹每類中比較成熟且有代表意義工作的文獻。
3.1 基于行為的建模
行為建模技術主要考慮模擬個體的數目、個體的智商水平、控制機制和碰撞處理等。解決這些問題的方法可以是粒子系統、群體系統、行為系統和等級層次系統等[25]。
粒子系統最早由Reeves于1983年引進到計算機圖形學領域,用來進行一些自然模糊現象的建模和可視化,比如云、水、氣體以及火焰等。法國的Bouvier等人[23]以粒子系統為原型建立了人群運動模型。在Bouvier建立的模型中,每個人都是一個模擬對象――“粒子”,整個人群則看作是一個粒子系統,系統內的粒子間可以進行互動。一個粒子集合對應于一群具有相同行為模式的人,通過在粒子系統內設置各種力場,采用牛頓力學機制并輔以被賦予概率的事件,通過仿真計算求得每個粒子的位置、速度、加速度等屬性,以實現人群運動的模擬。對于一些復雜的、需要較多決策知識的人群行為,還需要提供人群行為模式的學習方法、建立決策知識庫等。Tu等人[16]的研究工作是這一模型的代表。
3.2 基于認知的建模
認知建模的研究主要在行為控制,目前在計算機圖形學中認知建模的研究有文獻[17,33-39]。其中Funge等人[17]提出了認知建模在行為建模方面的作用,并通過對角色動作、角色先前條件和影響、角色行為的設置等定義了認知建模語言(Cognitive Modelling Language, CML)。認知建模分為兩個子模塊:知識域描述和角色范圍。知識域描述是描述角色在環境中的基本信息,而角色范圍是角色行為按照一定規則獲得指定目標。CML為獲取的目標提供了高維接口:一方面CML是傳統語言,可以描述指定的動畫角色;另一個方面,CML提供了簡單而有力的認知建模語言,通過CML語法描述關鍵的精確映射及計算。
Pelechano等人[34-36]提出了HiDAC(高密度的自治群體)模型,集中模擬個體在動態變化環境中的局部運動行為。結合心理學和幾何學的規則,采用了個體認知和基于物理的力模型。系統模擬了個體在不同環境下的不同運動行為(如:抖動行為、雙向行走行為、推行為和恐慌的蔓延行為)。并概括了基于個體模擬研究群體的基本方法:社會力模型、基于規則模型和基于CA(Cellular Automata)模型。
Shao等人[18]提出的人工生命方法整合了運動、感知、行為和認知等。方法支持自由行走的個體感知虛擬環境和反映個體行為,解決了行走者在復雜的城市環境下模擬不真實的一些行為(如:群體運動的碰撞避免、群體的運動軌跡等)。
以班曉娟等人[37]提出的“曉媛魚”為基礎的相關研究有:人工魚的自繁衍、自學習和“情+智”協調研究等,這些研究大多集中在人工魚的個體上,旨在提高人工魚個體的智能水平和認知能力。
趙光俊等人[38]針對群體動畫中角色的行為選擇(策略、目標和計劃)過程和認知建模方法,提出了一種建立自主角色認知模型的新方法。通過在行為動畫中引入“動物行為邏輯”的概念,給出了高層非確定性目標導向行為與低層確定性預定義行為相結合的協調控制方案,并以魚群動畫為例進行了仿真實驗。此方法不僅使行為動畫中的角色具備行為選擇智能,且能較好地反映群體行為的真實性。
Silverman等人[39]利用影響人群行為的心理元素提出了PMFServ系統。PMFServ系統是具有高融合的軟件系統,能模擬不同的群體領域,而且提供了認知結構的接口,能模擬基于情感的人群。
3.3 基于群體環境的建模
環境建模與行為建模非常相關,模擬環境的目的是為了讓群體的模擬與它們所處的環境相符。如果虛擬群體的行為與它們所處的環境相符,則虛擬群體模擬的可信性則會大大地增加。相反,如果虛擬群體的行為與現實世界不一致或者不被允許,比如穿墻或者人在水上行走,則會破壞掉虛擬群體模擬的可信性。
Thomas等人[40]提出了一種針對人群行為的虛擬城市模型。在該模型中,環境數據庫被劃分為兩部分:一部分是一種包含區域樹的層次結構,這點與信息化環境數據庫相似;一部分是一種具有公路交通網絡的拓撲結構,每一塊區域包含了關于流通方向的信息,包括在交叉路口的通道變化。每一個個體使用該數據庫作為整個城市的導航。
Sung等人[41]提出了一種控制群體行為的新方法,該方法通過使用一種名為“Situation”的結構來將行為信息存放到所處的環境中。同先前的方法相比,環境結構Situation中的信息是可以交叉的,而與這些交叉的環境結構Situation相對應的行為則是通過概率分布計算得到。根據當前所處環境狀態或的過去狀態,行為函數決定了行為狀態轉換的可能性,即觸發行為的變化。
王潔等人[42]針對模擬低密度下個人安全距離的保持和高密度下人群擁擠的情況,采用基于原位置的穿透矯正法克服現有模擬中由于避免穿透而引入的限制和失真,有效地杜絕穿透現象的出現。
3.4 基于人群的建模
目前通用的人群運動建模方法均處于初步研究階段,實際應用有一定難度。而針對特定應用系統,在限定模擬場景或情節并給定人群目標的情況下,研究人群的行為特征、建立人群運動模型則較為容易。目前已經有不少針對特定應用的人群運動仿真系統,如:模擬在輪船失事情況下乘客逃生過程的maritime EXODUS系統;模擬在地鐵、港口等典型建筑物危急情況下人群逃生的Vegas系統等。下面介紹一些有代表工作的文獻。
3.4.1 恐慌狀態下人群撤離運動建模
Helbing等人[43]系統地研究了恐慌狀態下的人群撤離行為,建立了恐慌狀態下人群撤離的運動仿真模型。該模型僅針對恐慌狀態下的人群撤離行為,以粒子系統為基礎,著重研究和分析個體的受力情況,根據個體的受力情況計算個體的移動速度,模擬恐慌狀態下人群撤離的典型行為特征,計算人群通過狹隘通道和出口撤離的速度,并計算可能的受傷人數。個體受力情況和運動速度的關系可用式(4)表示:
midvidt=miv0i(t)e0i(t)-vi(t)τi+∑j≠ifij+∑wfiw (4)
其中:mi是個體質量;v0i(t)是個體速率i的初始速度;e0i(t)是個體初始運動方向;vi(t)是個體期望的經過ti時刻后的運動速度;∑j≠ifij是周圍人群施加給個體i的力。∑wfiw是周圍建筑如墻壁、障礙物等施加給個體i的力。圖6顯示了恐慌狀態下人群撤離的模擬。
3.4.2 Vi Crowd 人群運動建模
ViCrowd模型由瑞士聯邦技術研究所計算機圖形實驗室的Soraia等人[25]提出。ViCrowd模型定義了虛擬人三個不同層次的集合:人群、團隊和個體。而后定義了人群的三個大方面的屬性:知識、信念和意圖。知識主要涉及虛擬環境中的各種信息,包括:障礙物、基于環境的人群動作和行為、人群知識等。信念主要包括人群即將執行的動作和行為,它可以分為三個方面:1)人群和群的行為,比如聚集、跟隨、更換目標、吸引、排斥、分裂、空間占用和安全檢測等;2)情感狀態,比如喜怒哀樂等;3)個人信念,比如個體是否要脫離或加入一個群、個體在人群中的地位等。意圖則表示人群目標。
圖片
圖6 人群通過一個狹隘出口撤離的模擬結果[43]
ViCrowd模型同時還定義了虛擬人行為的三個自由度層次,即被引導的(又稱外部控制)、規劃的(也稱腳本控制)和自治的(內在行為)。在人群運動模擬中,外部控制行為的優先級最高,其次是腳本控制行為,最后是自治行為。圖7是采用ViCrowd模型進行仿真的結果。
圖片
圖7 基于ViCrowd 模型的人群運動仿真結果[25]
3.4.3 Brogan and Hodgins建模
Brogan and Hodgins模型,主要針對具有顯著物理特征的人群[20],在建模過程中更多地使用動力學原理,對人群的速度、位置、加速度變化進行了更多的考慮和限制,同時也從物理角度應用動力學原理建立個體運動仿真模型。它是粒子系統針對具有顯著物理特征的人群行為的一種擴展,適用于馬拉松、自行車賽、游泳等體育項目的模擬仿真。模擬結果如圖8所示。
圖片
圖8 Brogan and Hodgins人群運動仿真[20]
3.5 基于角色的群體建模
通常在特定的生存環境中,不同的智能角色有不同的感覺能力。為了生動逼真地刻畫出智能角色的感知能力,必須對智能角色的感知系統進行合理、正確的建模。為智能角色建立感知模型涉及兩個內容:1)模仿智能角色的感知能力以及感知局限性;2)通過模仿角色大腦對感知信息的處理結果來解釋感知的信息。
Reynolds等人[15]提出了一個集群行為計算模型,其中每個角色是在各自的環境中獨立的行為者,通過感知局部環境來決定在給定的時間采取何種行為;Tu[7]的工作中提出了基于自然生命模型的動畫自動生成方法,把魚作為自激勵的自主智能體,創作了生動逼真的人工魚群,其工作是智能角色動畫的典型代表;Isla等人[44]提出了智能角色建模領域中的最新挑戰。這些基于角色的建模較復雜,產生的運動有限,需要進一步對真實感行為進行研究。
3.6 小結
如表1所示,我們對近年來有關計算機群體動畫研究的文獻按照群體動畫的建模方式進行分類。從表1中可以看出,在收集到的50篇論文中,對于群體動畫的研究大多從個體行為研究開始,主要方法是采用基于社會力模型、基于規則模型、CA模型和人工生命方法等。通過對群體動畫建模分類,能更好地理解群體動畫研究的方法和方向。
表格(有表名)
表1 計算機群體動畫的建模分類
群體動畫的建模類型主要研究內容研究方法研究文獻
基于行為的建模考慮模擬個體的數目、個體的智商水平、控制機制和碰撞處理等粒子系統、群體系統、行為系統、等級層次系統等[1,15-16,23,25]基于認識的建模行為控制社會力模型、基于規則模型、基于CA模型[17-20,23,[34-39]基于群體環境的建模復雜環境對模擬、對群體運動的影響,阻止穿透現象的產生環境數據庫、環境結構[41-43]基于人群的建模人群的行為特征、建立人群運動模型ViCrowd模型、社會力模型、基于規則模型、物理學模型[20,25,43]基于角色的建模智能角色的研究人工生命方法、基于規則的模型[7,15,29-30,44]
4 群體運動算法
群體真實感行為的控制方式主要分為兩類:自底向上的方式,即基于局部控制的方式;自頂向下的方式,即基于全局控制的方式。對于運動的群體,無論是局部控制方式還是全局控制方式都要設計解決兩個問題:路徑規劃和碰撞避免。對于這兩個問題,先前的研究者提出一些算法和方法,下面進行歸納分析。
4.1 碰撞避免算法
碰撞檢測按照是否考慮時間參數,可分為連續碰撞檢測和離散碰撞檢測。其碰撞檢測的典型算法包括:空間分解法和包圍盒層次法。常見的空間分解法有八叉樹法和二叉空間剖分法。常見的包圍盒有包圍球、沿坐標軸的軸向包圍盒(AABB)、方向包圍盒(OBB)和離散方向多面體(k-DOP)等。
Kim等人[45]采用了分割區域的方法,并為每個人設置一個觸角圓柱體用于探測其所在方形內其他個體。缺點:觸角圓實際上是個體的感知范圍,范圍太大計算量會增加,太小就不能模擬人的視覺。Chenney等人[46]采用流片元方式使用可自由分支的流模擬人群體的方法,有效地模擬擁塞避免的人群特性。
在1983年Reeves提出粒子系統后,Bouvier等人[22-23]使用粒子系統和有限自動機模擬了城市環境中的虛擬人群,使用類似電子力的吸引力和排斥力作為底層力來實現碰撞避免。
劉莉等人[47]提出一種新的穿透深度計算方法,無須對凹多面體進行凸分解,就能精確地計算任意多面體間的方向穿透深度。在此基礎上,提出一種基于個體分解的包圍體層次,極大地提高了算法的效率。
其他碰撞的算法有:基于網格的規則、基于密度的技術、行為系統和粒子交互力。
4.2 路徑規劃算法
所謂路徑規劃就是依據某個或某些優化準則(如工作代價最小、行走路線最短和行走時間最短等),在其工作空間中找到一條從起始狀態到目標狀態的能避開障礙物的路徑。主要的方法有:基于網格的算法、基于人工勢能場算法、CMM算法、IRM算法和DB算法等。
基于網格的方法是把虛擬環境劃分成單元格,然后使用A*搜索算法。A*搜索算法缺乏適應性,同一條路徑只有固定的路徑查詢格式,計算代價比較大。D*算法[48]也使用網格方法,采用全局搜索算法且克服A*算法的缺點。優點是:當重新計算新優化路徑時,不需要計算整個路徑。Tang等人[49]使用了一種改進的A*算法在由高度圖生成的地形網格上進行路徑規劃。Willns等人[50]提出了改進的DB算法,該算法是基于網格的動態距離繁衍系統。Reynolds[15]提出了領隊跟隨和路徑跟隨模式。對于被指定的組,領隊跟隨運動模式的組內成員分為領隊者和跟隨者,當指定領隊的運動速度、方向和目標位置以后,跟隨者的運動就完全由領隊者控制,初始狀態時的領隊者和跟隨者的相對位置關系和目標狀態時的領隊者和跟隨者的相對位置關系相同。
Pettre等人[51]使用靜態場景的導航圖實時地規劃個體的路線,但是沒有考慮碰撞和擁塞的避免。通常來說,靜態勢能場不能處理變化的環境。Treuille等人[13]使用一個全局的動態勢能場解決了這個問題,算法同時考慮了人群的密度、人群的速度、地勢高低以及舒適度的問題,但只能是在二維的環境中進行。
Geraerts等人[52]提出CMM(走廊地圖方法)。CMM克服了傳統路徑尋徑的缺點,在復雜環境中容易計算出光滑路徑。但是對同一路徑搜索方式固定,無靈活性。Karamouzas等人[53]使用運動個體在走廊中的路徑選擇擴展了CMM方法。Geraerts等人[54]采用提取離散的路徑信息來改進CMM。
Karamouzas等人[55]提出了IRM算法,該方法被廣泛地應用于計算機游戲和虛擬環境。IRM算法被分為三個階段:1)計算個體指示的路線;2)對路線創建一個走廊,使得個體在虛擬環境中無碰撞;3)使用勢能場方法從創建的走廊中提取個體運動信息。該算法能準確地規劃路徑并且防止個體碰撞。
Lamarche等人[56]為快速層次路徑規劃提出了一種幾何環境的拓撲結構,為虛擬群體提出了一種可反應的導航算法。但是采用了一個獨立的碰撞避免過程,在擁塞的處理上容易產生堵塞現象。
4.3 小結
表2對碰撞避免算法和路徑規劃算法的16篇文獻進行分類。并對每一類算法進行歸類,其實在很多文獻中,碰撞避免算法和路徑規劃算法往往是放在一起研究,如文獻[52,55]等。
表格(有表名)
5 結語
群體動畫屬于計算機圖形學的研究范疇,但是群體動畫的真實感行為研究涉及到計算機圖形學、人工智能、機器學習和認知科學等領域,已經成為一個多學科技術交叉的研究領域。
本文首先給出了群體動畫引擎框架,對群體動畫進行分類和歸納;根據群體動畫近年來的發展情況進行了分析,給出了群體和群體運動的概念;根據群體動畫引擎框架對現有的計算機群體動畫真實感行為的建模研究進行了綜述(主要包括:基于認知的建模、基于行為的建模、基于群體環境的建模、基于人群的建模和基于角色的群體建模);同時對群體運動的個體從碰撞避免算法和路徑規劃算法等兩個方面對群體動畫的算法進行分析。
通過查閱相關文獻[2-4,13,16,18],群體動畫未來幾年可能取得突破的研究方向有:1)基于心理學和認知科學的研究,發掘出更具一般性的群體行為、表情甚至感情等機制的真實感行為;2)全局控制與局部控制的人工智能問題在大規模場景中的研究;3)多種群體分組策略研究,并通過按照地理及目標點進行分組控制,優化計算性能;4)個體的高層決策模型研究,采用有限狀態機及模糊狀態機來描述個體的意圖轉換,從而做出意圖決策;5)群體模型中個體避免碰撞和智能路徑規劃技術的算法研究,可以考慮基于“局部側滑力避障路徑算法”、“基于自學習的避障路徑算法”及“基于特定目標點的最優化路徑算法”等算法的改進。
致謝 本文的工作得到了國家863計劃項目(2007AA01Z322)和總裝基金項目(9140A06060208DZ0207) 資助。同時感謝本文所參考文獻的作者和研究團體,感謝他們卓絕的工作;感謝電子科技大學計算機學院數字媒體研究所的各位成員,感謝他們的建議和良好的協作精神。
參考文獻:
[1]AMKRAUT S, GIRARD M, KARL G. Motion studies for a work in progress entitled "Eurnythmy" [EB/OL]. [2009-04-20]. /Paper/1280362.aspx
[2]PELECHANO N, OBRIEN K, SILVERMAN B, et al. Crowd simulation incorporating Agent psychological models, roles and communication [C]// Proceedings of the 1st International Workshop on Crowd Simulation. St. Philadelphia, PA: [s.n.], 2008: 21-30
[3]ADI BIN MOHAMED AZAHAR M, SUNAR M S, DAMAN D, et al. A survey on real-time crowds simulation [C]// Proceedings of the 3rd International Conference on Technologies for E-learning and Digital Entertainment, LNCS 5093. Berlin: Springer-Verlag, 2008: 573-580
[4]ZHAN BEI-BEI, MONEKOSSO D N, REMAGNINO P, et al. Crowd analysis: A survey [J]. Machine Vision and Applications, 2008, 19(5/6): 345-357
[5]陳雷霆.三維復雜場景實時繪制技術[D].成都:電子科技大學,2007
[6]肖俊.智能人體動畫若干關鍵技術研究[D].杭州:浙江大學,2007
[7]TU XIAO-YUAN. Artificial animals for computer animation: Biomechanics, locomotion, perception, and behavior [D]. Toronto: University of Toronto, 1996
[8]MCDONNELL R. Realistic crowd animation: A perceptual approach [D]. Dublin: University of Dublin, Trinity College, 2006
[9]陳健.群體動畫實時渲染技術的研究[D].成都:電子科技大學,2007
[10]徐文彬.大規模虛擬人實時繪制技術研究及其實現[D].北京:中國科學院計算技術研究所,2006
[11]PALMQVIST B, DIMBERG N. Boids for real-time management of armies [D]. Umea: Umea University, 2006
[12]THALMANN D, MUSSE S R. Crowd simulation [M]. London: Springer-Verlag, 2007
[13]TREUILLE A, COOPER S, POPOVIC Z. Continuum crowds [C]// SIGGRAPH06: Proceedings of the 33rd International Conference and Exhibition. Boston, Massachusetts: ACM Press, 2006: 1160-1168
[14]HUANG LING, WONG S C, ZHANG MENG-PING, et al. Revisiting Hughes dynamic continuum model for pedestrian flow and the development of an efficient solution algorithm [J]. IEEE Transportation Research, 2009, 43(1): 127-141
[15]REYNOLDS C W. Flocks, herds, and schools: A distributed behavioral model [C]// SIGGRAPH87: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1987: 25-34
[16]TU X, TERZOPOULOS D. Artificial fishes: Physics, locomotion, perception, behavior [C]// SIGGRAPH94: Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1994: 43-50
[17]FUNGE J, TU X, TERZOPOULOS D. Cognitive modeling: Knowledge, reasoning and planning for intelligent characters [C]// SIGGRAPH99: Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1999, 29-38
[18]SHAO W, TERZOPOULOS D. Autonomous pedestrians [C]// SCA05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York: ACM Press, 2005: 19-28
[19]HODGINS J, BROGAN D. Robot herds: Group behaviors for systems with significant dynamics [C]// Proceedings of the 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems. Washington, DC: IEEE Computer Society, 1995: 528-534
[20]BROGAN D, HODGINS J. Group behaviors for systems with significant dynamics [J]. Autonomous Robots, 1997, 4(1): 137-153
[21]LAKOBA T I, KAUP D J, FINKELSTEIN N M. Modifications of the Helbing-Molnár-Farkas-Vicsek social force model for pedestrian evolution [J]. Simulation, 2005, 8l(5): 339-352
[22]BOUVIER E, GUILLOTEAU P. Crowd simulation in immersive space management [C]// Proceedings of the 1996 Eurographics Workshop on Virtual Environments and Scientific Visualization. Berlin: Springer-Verlag, 1996: 104-110
[23]BOUVIER E, COHEN E, BAJMAN L. From crow simulation to airbag deployment: Particle systems, a new paradigm of simulation [J]. Journal of Electrical Imaging, 1997, 6(1): 94-107
[24]MUSSE S R. Human crowd modeling with various levels of behavior control [D]. Lausanne: EPFL, 2000
[25]MUSSE S R, THALMANN D. A hierarchical model for real time simulation of virtual human crowds [J]. IEEE Transactions on Visualization and Computer Graphics, 2001, 7(2): 152-164
[26]ULICNY B, THALMANN D. Towards interactive real-time crowd behavior simulation [J]. Computer Graphics Forum, 2002, 21(4): 767-775
[27]ULICNY B, THALMANN D. Crowd brush: Interactive authoring of real-time crowd scenes [C]// Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York: ACM Press, 2004: 243-252
[28]NIEDERBERGER C, GROSS M. Hierarchical and heterogeneous reactive Agents for real-time applications [J]. Computer Graphics Forum, 2003, 22(3): 323-331
[29]da Silva M, ABE Y, POPOVIC J. Interactive simulation of stylized human locomotion [J]. ACM Transactions on Graphics, 2008, 27(3): 63:1-63:12
[30]McDONNELL R, LARKIN M, DOBBYN S, et al. Clone attack! perception of crowd variety [J]. ACM Computer Graphics, 2008, 27(3): 1-8
[31]KWON T, LEE K H, LEE J, et al. Group motion editing [J]. ACM Computer Graphics, 2008, 27(3): 80:1-80:8
[32]KIM M, HYUN K, KIM J, et al. Synchronized multi-character motion editing [C]// SIGGRAPH 2009: Proceedings of the 2009 International Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 2009: 79-79
[33]CONDE T, THALMANN D. Learnable behavioral model for autonomous virtual Agents: Low-level learning [C]// Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems. New York: ACM Press, 2006: 89-96
[34]PELECHANO N, ALLBECK J M, BADLER N I. Controlling individual Agents in high-density crowd simulation [C]// Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York: ACM Press, 2007: 99-108
[35]PELECHANO N, STOCKER C, ALLBECK J, et al. Being a part of the crowd: Towards validating VR crowds using presence [C]// AAMAS08: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2008: 136-142
[36]DURUPINAR F, ALLBECK J, PELECHANO N, et al. Creating crowd variation with the OCEAN personality model [C]// AAMAS 2008: Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2008: 12-16
[37]寧淑榮,班曉娟,涂序彥.人工魚“情+智”協調的“意圖產生”和“行為控制”[J].自動化學報,2007,33(8):835-839
[38]趙光俊,張文俊,陳偉平.群體行為動畫中認知角色的建模方法[J].系統仿真學報,2007,19(14):3253-3257
[39]SILVERMAN B G, BHARATHY G, OBRIEN K, et al. Human behavior models for Agents in simulators and games: Part I-Enabling science with PMFserv [J]. Presence: Teleoperators, and Virtual Environments, 2006, 15(2): 139-162
[40]THOMAS G, DONIKIAN S. Modeling virtual cities dedicated to behavioral animation [J]. Computer Graphics Forum, 2000, 19(3): C71-C80
[41]SUNG M, GLEICHER M, CHENNEY S. Scalable behaviors for crowd simulation [J]. Computer Graphics Forum, 2004, 23(3): 519-528
[42]王潔,王兆其,李淳芄,等.一種用于群體模擬的分層次避障法[J].計算機研究與發展,2007,44(12):2058-2065
[43]HELBING D, FARKAS I, VICSEK T. Simulating dynamical features of escape panic [J]. Nature, 2000, 407(6803): 487-490
[44]ISLA D, BLUMBERG B. New challenges for character-based AI for games [C]// Proceedings of AAAI Spring Symposium on AI and Interactive Entertainment. Cambridge, MA: AAA Press, 2002: 141-146
[45]KIM H K, OH J K, CHOI M G. An event-driven approach for crowd simulation with example motions, CS-TR-2001-170[R]. Taejon, Korea: Korea Advanced Institute of Science and Technology, 2002
[46]CHENNEY S. Flow tiles [C]// Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Aire-la-Ville, Switzerland: Eurographics Association, 2004: 233-242
[47]劉莉, 王兆其, 夏時洪, 等.碰撞響應中方向穿透深度算法的研究[J].計算機研究與發展,2008,45(3):519-526
[48]KOENIG S, LIKHACHEV M. Fast replanning for navigation in unknown terrain [J]. IEEE Transactions on Robot, 2005, 21(3): 354-363
[49]TANG W, WAN T R, PATEL S. Real-time crowd movement on large scale terrains [C]// Proceedings of the 2003 Theory and Practice of Computer Graphics. Washington, DC: IEEE Computer Society, 2003: 146-146
[50]WILLNS A R, YANG S X. Real-time robot path planning via a distance propagating dynamic system with obstacle clearance [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 2008, 38(3): 884-893
[51]PETTRE J, LAUMOUND J P, THALMANN D. A navigation graph for real-time crowd animation on multilayered and uneven terrain [C]// V-CROWDS05: Proceedings of the 1st International Workshop on Crowd Simulation. Lausanne, Switzerland: [s.n.], 2005: 81-89
[52]GERAERTS R, OVERMARS M H. The corridor map method: A gen-eral framework for real-time high-quality path planning [J]. Computer Animation and Virtual Worlds, 2007, 18(2):107-119
[53]KARAMOUZAS I, OVERMARS M H. Adding variation to path planning [J]. Computer Animation and Virtual Worlds, 2008, 19(3/4): 283-293
[54]GERAERTS R, OVERMARS M H. Enhancing corridor maps for real-time path planning in virtual environments [C]// CASA 2008: Proceedings of the 2008 International Conference on Computer Animation and Social Agents. Seoul, Korea: [s.n.], 2008: 64-71
關鍵詞：unity 3D 探險游戲 C# 藏族特色
中圖分類號：TP311 文獻標識碼：A 文章編號：1003-9082（2015）06-0019-01
引言
在人類的社會生活當中，游戲占有很大的比重，并且隨著社會的發展而不斷發展。在現有的游戲市場中，具有藏族特色游戲更是寥寥無幾，恢弘傳統民族文化，游戲也是一種途徑。在本游戲設計之初，對一些具有藏族特色的游戲，進行了試玩和調查，比如藏式麻將[1]對本游戲具有很大的引導作用。藏式探險小游戲的設計與開發，在一定的程度上，開創了藏式探險游戲的先河。藏式探險小游戲的設計與開發，旨在訓練玩家的思維應變能力，以及在玩的過程中了解的文化元素，游戲場景設計中具有大量的藏族元素，如場景中的雪山冰川，給人以身臨其境的感受。
一、運用unity3D游戲引擎中遇到的問題
1.unity3D游戲引擎中圖形用戶界面藏文字符實現
Unity3D游戲引擎在目前的游戲市場占據著半壁江山，因此在游戲設計之初，就決定使用該款游戲引擎作為設計開發平臺。但是，unity3D本身仍然存在著一些弊端，現在市場上的unity3D軟件還不支持中文輸入，因此藏文的輸入也是無法完成，用戶圖形界面如果需要做得具有藏族特色，即插入藏文字符菜單欄，實現起來有困難。unity3D中可以將任意字體作為材質文件賦予“GUI Text”，其中就包括藏文字體。具體做法如下：
第一步：將需要的藏文字體拷入到項目文件中“Assets”（資源）文件夾內。
第二步：在菜單欄選中Game Object創建一個G.U.I文件，將字體導入，在屬性面板中找到“Text”后面的輸入框輸入需要的文字即可；
2.游戲引擎后臺程序設計語言的選擇
在網絡日益盛行的當今社會，各種程序設計語言如雨后春筍，Unity3D游戲引擎作為一款主流的游戲制作軟件，對程序設計語言也有較高的要求。Unity3D后臺支持的主要程序設計語言有C#、java script和bootstrap等程序語言[1]。本次游戲設計選擇了C#語言作為游戲設計開發語言，由于使用C#可以減少許多語言上的麻煩，而且C#作為一種簡單、通用、現代的語言，對于新手是比較合適的程序設計語言。同時，C#語言也是unity3D后臺程序開發運用最廣泛的語言，而且C#的算法在unity3D游戲引擎中容易實現[2]。相比其他幾種程序語言，如果使用java script程序設計語言，程序代碼將會很繁瑣，而且java script的運算速度相對較慢。Bootstrap是目前最受歡迎前端框架，更多用于做網站，不適合做游戲開發。
二、游戲設計中算法的實現
1.探險人物路徑的設計
人物在探險的過程中會有柵欄的阻礙和怪獸的追擊，人物路徑的設計具有一定的難度，解決人物移動的算法運用了C#程序設計語言中常用的遍歷算法。以下代碼完成了人物路徑的設計：
//人物所在的行列數編號=格子的行列數編號+1
for （int i = 0； i < 8； i++）//遍歷編號為0-7總共8行的格子
{for （int j = 0； j < 6； j++）//遍歷每一行編號為0-5總共有6列的格子
if （row == j + 1）{ //當前遍歷的格子與人物所在的行數相同
if （col == i）{//當前遍歷的格子列數=人物所在的列數+1
if （！row barrier.Contains（new Vector2（row - 1， col - 1）））//若此格子右邊沒有豎柵欄阻擋 }
//則當前遍歷的格子列數=人物所在的列數-1
if （col == i + 2）{
if （！Row barrier.Contains（new Vector2（row - 1， col - 2））） //若此格子左邊沒有豎柵欄阻擋；人物向左移動，并記錄移動前的行列數
dir = 3； old Row = row； old Col = col； move = true； }} }
//當前遍歷的格子與人物所在的列數相同
if （col == i + 1）
//當前遍歷的格子行數=人物所在的列數+1
2.游戲中怪獸移動算法
算法在程序設計中具有核心作用，因此算法的設計對程序的設計具有決定性的作用，常見算法設計方法主要有：遞推法、遞歸法、回溯法、迭代法、動態規劃法等[3]。而此次探險游戲設計使用了類深度優先遍歷的計算方法，用程序實現搜尋答案的計算方法，即根據探險人物路徑遍歷搜尋怪獸的移動算法。由以下代碼實現了怪獸的移動：
void AI（）
{
if （！move && m Move==0）
{ //怪獸移動前，人物不移動時進行AI
//生成可行走路徑數組
Now Path.Add（new Vector2（m Row， m Col））；//將當前搜尋的格 子位置打入到當前要遍歷的路徑鏈表
m Path.Add（new List（now Path））；//將當前要遍歷的 路徑鏈表插入到可移動路徑數組
//開始遍歷
for （int i = 0； i < m Path.Count； i++）
{//若速度（2+1，因包括自身所在格）范圍內的所有格子都已遍歷， 則退出遍歷}
三、結語
在信息化高速發展的今天，游戲市場還處在不斷發展的階段，而開發具有藏族特色的游戲，前景更是廣闊。基于unity3D藏式探險游戲設計完成了具有特色的傳統游戲開發，實現了在unity3D游戲引擎上對具有藏式特色游戲的設計開發。不可避免該設計還存在一些缺點，在以后的時間里，不斷完善使其做到極致。同時了解更多關于的傳奇故事，將其演繹成游戲的形式奉獻給大家，將元素及文化傳向中國、傳向世界。
參考文獻
[1]曲珍.朱世清.藏式麻將游戲設計與實現[M]：大學出版社，2013.
[2]吳亞峰.Unity 3D游戲開發技術詳解與典型案例[M]：人民郵電出版社，2012.
[4]雷軍環、劉震.數據結構C#版教程[M]：清華大學出版社，2009.
關鍵詞：遺傳算法；時間窗；車輛路徑問題；基因庫
中圖分類號：TP202+.7文獻標識碼：A文章編號：1009-3044(2011)10-2411-03
Research on VRPTW Problem Based on Improved Genetic Algorithm
FAN Yue-lin, ZHOU Su-ping
(Economy Management College, Nanjing University of Information Science & Technology, Nanjing 210044, China)
Abstract: The Vehicle Routing Problem with Time Windows (VRPTW) is NP-hard, this paper explored the optimal solution by improved Genetic Algorithm, and firstly analyzed the general mathematical model of the Vehicle Routing Problem with Time Window, and dealt with Time Window through penalty function. Then designed a fitness function with weight in-built, then adopted the elite selection operator based on gene pool ,PMX crossover operator and local_climbing mutation operator. Finally compared the algorithm with simple genetic algorithm and adaptive genetic algorithm by simulation. The results indicate that the improved genetic algorithm has higher convergent speed and global searching capability.
Key words: genetic algorithm; time window; VRP; gene pool
車輛路徑問題（Vehicle Routing Problem-VRP）是物流配送中的關鍵問題之一，最早由Dantzing和Ramser于1959年提出[1]，是典型的NP-hard問題。而有時間窗約束的車輛路徑問題（Vehicle Routing Problem with Time Window-VRPTW ）則是VRP的一個特例，它考慮了需求在時間上的約束，即要求車輛盡可能在時間窗以內到達客戶點，現實意義更強。眾所周知，對于NP-hard問題，采用精確式算法得出確定的最優解往往是不可行或不經濟的，而更為有效的方法則是通過某種啟發式算法找到問題的近優解。其中遺傳算法以其獨特的算法形式和運行機理在復雜問題的求解中有著比較明顯的優勢。為此，本文采用改進的遺傳算法對有時間窗約束的車輛路徑問題進行了探討研究，以尋找最優解為目標，在構造出VRPTW的一般模型后，著重闡述了改進遺傳算法的設計，最后通過仿真計算取得了良好的效果。
1 VRPTW模型
給定一個配送中心，擁有若干載重相同的配送車輛。在配送中心周圍分布有若干客戶，每個客戶有不同的貨物需求。配送車輛裝載一定數量的貨物，按照預先分配好的線路行駛，在各個客戶要求的服務時間窗內將貨物送達。通過合理安排配送線路和次序，使得配送過程的總成本最小（見圖1）。
為方便表示，建立如下符號體系：Z表示配送總成本；m為所需的配送車輛數；n代表需要服務的客戶數量；Di,j表示從客戶i到客戶j的距離（i,j的取值從0到n）；c表示單位距離運輸成本；gi表示客戶i的需求量；q表示配送車輛的最大載重；[eti,lti]是客戶i要求的服務時間窗；ti是配送車輛到達客戶i的時間（t0是車輛從配送中心的出發時間），time是對每個客戶的服務停留時間，speed是配送車輛的平均行駛速度。另外定義變量如：
本文采用罰函數的方法來處理時間窗約束，并設a、b分別為配送車輛提前和滯后到達客戶的時間窗懲罰因子，則客戶i處的時間窗成本為：
有了以上的符號體系，可以得到如下成本表示[3]：
距離運輸成本：
(1)
超重成本：
(2)
時間窗成本：
(3)
其中DistanceCost計算的是各條線路的距離成本；CapacityCost計算的是各配送車輛由于超載所產生的成本，在現實生活中如果嚴防超載，可以將M系數設置成非常大（一般為1000000）即可；TWCost反應了配送車輛違背時間窗的懲罰成本。三種成本按照用戶設定的權重值(W1,W2,W3)加權計算，就得到了配送總成本的表達形式：
(4)
2 改進的遺傳算法
2.1 算法原理
遺傳算法最初是由J.H.Holland等在70年代提出[2]，以自然選擇和遺傳理論為基礎，模仿自然界優勝劣汰的進化機制，通過不斷迭代最終得出最優解。本文對傳統遺傳算法的選擇和變異操作進行改進，算法流程圖見圖2。
2.2 算法設計
2.2.1 編碼
本文將按照配送車輛到達客戶的先后順序進行編碼。假設有九個客戶需要配送貨物，分別命名為1,2，…9，配送中心為0，隨機產生一個序列作為一條染色體如3 5 6 9 2 1 4 8 7 ，表示配送車輛到達的次序是客戶3,客戶5，…，最后到達客戶7。現實應用中往往需同時派出多輛配送車運送貨物，每輛配送車負責一條線路，對以上的染色體進行可行化處理――線路劃分，這樣每輛配送車能在不超載的情況下完成各自的配送任務，這樣就很好的解決了車輛載重約束。線路劃分算法如圖3。
假設經過線路劃分的染色體編碼形式變為：
解碼后：
2.2.2 適應度函數
適應度函數是衡量染色體接近最優解的程度，能有效地反映每一條染色體與問題最優解染色體的差距。由于我們在編碼階段已經通過線路劃分完全消除了車輛超載的可能，因此我們在適應度的計算中只需考慮距離運輸成本和時間窗成本。我們采用如下設計：
第w條染色體的適應度函數為fw
(5)
其中w1,w3分別為距離運輸成本和時間窗成本的權重值，且0≤w1,w3≤1 , w1+w3=1.
2.2.3 遺傳操作的改進
遺傳操作包括選擇、交叉和變異三個過程。在選擇算子中本文在roulette wheel選擇法的基礎上進行改進，建立了世代基因庫，用于存儲進化過程中適應度很高的精英染色體。基因庫中染色體按適應度大小排序且庫大小設置為20，每次更新基因庫時將新染色體按適應度大小插入，將適應度最小者剔除以保證基因庫中的平均適應度不斷提高（見圖4） 。在選擇染色體時將基因庫中的染色體混入一般染色體中用于進一步進化。
交叉算子模擬的是自然界中的基因重組過程，本文采用部分匹配交叉（partially matched crossover , PMX）,在交叉過程中將隔離基因預先剔除，交叉完成后重新進行線路劃分，以杜絕不可行解的出現。
變異過程是對染色體上一個或幾個基因位進行隨機替換。本文將傳統多點變異改進成局部爬山變異，即變異有若干個候選變異方向，算子將按照其中最好的方向實施變異，以達到局部最優。設計如下：在染色體編碼序列中隨機產生三個位置（非隔離基因0）pos1, pos2, pos3作為變異點如：
pos1, pos2, pos3三個位置的編碼值任意交換位置產生A33=6種組合，分別計算這六種組合所對應的編碼序列的適應度函數，將適應度最高的染色體保留下來作為變異的結果。如此使得變異算子具有局部爬山能力，可使染色體只向有利的方向變異，提高收斂速度。
3 仿真實驗及分析
3.1 仿真條件及參數設置
本文在Java Eclipse Galileo環境下進行了仿真，主機配置為Intel 雙核處理器，CPU主頻1.8GHZ，內存2.0GB，采用Java和SQL Sever2000編程實現。仿真數據如下：O是配送中心，坐標為[200,200]，配送車輛出發時間是8:00，A～J分別代表十個有配送需求的客戶，客戶信息見表1。算法參數為：種群大小=50，交叉概率=0.80，變異概率=0.01，終止代數=500，車輛最大載重=8.0，早于時間窗懲罰因子=10.0，晚于時間窗懲罰因子=10.0。
表1 客戶信息表
3.2 仿真結果及分析
采用以上參數設置時經過687ms的計算取得了較為滿意的計算結果見圖6。結果顯示，當種群進化到113代以后，配送車輛的規劃路徑已經不在發生變化（---OGFO---OAJHIO----OEDCBO----），并且總成本也趨于穩定直至254代以后完全固定在2244.098為止。圖5則給出了最佳配送方案的直觀展示，十個客戶按照配送順序被劃分到①②③三個區域，分別由三輛配送車進行配送。
為驗證本文改進遺傳算法的可行性和有效性，分別采用傳統遺傳算法（SGA）、自適應遺傳算法（ASA）和本文改進的遺傳算法（IGA）對帶時間窗VRP問題在相同實驗環境和仿真數據下進行了100次對比仿真實驗，結果如表2。
表2表明：對于本文的帶時間窗VRP問題，改進遺傳算法的選擇和變異操作中要比另外兩種算法復雜，但局部的復雜卻提高了算法全局的進化效率，收斂時間大為縮短。而且當問題規模較小時，三種方法雖都能得出最優解，但改進算法的最優解收斂次數卻提高了13.64%以上。可見改進的遺傳算法運算效率得到了提升而且全局搜索能力大大增強。
4 結束語
采用遺傳算法處理帶時間窗約束的車輛路徑問題，其實質就是將約束條件轉化到遺傳算子的設計中，在成功處理了約束條件后，問題就簡化為簡單的TSP問題[6]，目前，具有較強實際意義的約束條件有載重約束、時間窗約束、路徑長度約束、取貨送貨約束、回程約束和司機工作時間約束等等。隨著約束條件的增加，遺傳算法的設計難度也越大。因此，如何恰當的將各種約束條件進行轉化成為解決車輛路徑問題的關鍵，也是當前的研究熱點。筆者希望通過本文的探討研究能為VRP問題的研究者提供參考。
參考文獻：
[1] CORDEAU J F,LAPORTE G.A unified tabu search heuristic for vehicle routing problems with time window[J].Journal of the Operational Research Society,2001,52(8):928-936.
[2] Holland J H.Adaptation in Natural and Artificial System[M].Mit Press,Cambridge,Mass,1975.
[3] 陳湘州,楊勇,王俊年.一種改進的自然數編碼遺傳算法在非滿載時間窗車輛優化調度問題中的應用[J].長沙電力學院學報:自然科學版,2004,19(2):56-59.
[4] 孫曦,蔡臨寧.帶時間窗的車輛路由問題的改進遺傳算法[J].工業工程與管理,2007(3):16-20.
[5] 孫輝.遺傳算法在物流企業配送業務中的應用[D].吉林大學數學所,2005.
[6] 李大衛,王莉,王夢光.遺傳算法在有時間窗車輛路徑問題上的應用[J].系統工程理論與實踐,1999,19(8):65-69.
關鍵詞：無人機；航路規劃；動態規劃算法；啟發式算法；遺傳算法
1 無人機航路規劃問題的描述
無人機航路規劃是依據地形信息和執行任務環境條件信息，綜合考慮無人機的性能、到達時間、耗能、威脅以及飛行區域等約束條件，為無人機規劃出一條或多條自出發點到目標點的最優或可行的飛行航路，保證無人機高效、圓滿地完成飛行任務，并安全返回基地[1]。其本質是多約束條件下最優或可行解的求解問題。無人機航路規劃一般分兩步：首先是飛行前預規劃，即根據既定任務，結合環境限制與飛行約束條件，從整體上制定最優參考路徑并裝訂特殊任務；其次是飛行過程中的重規劃，即根據飛行過程中遇到的突發狀況，如地形、氣象變化、未知限飛禁飛因素等，局部動態的調整飛行路徑或改變動作任務（如圖1所示）。
從框圖中可知，按照任務環境模型是否實時變化，即無人機飛行環境是否確定，航路規劃可分為已知威脅信息環境下航路規劃和未知威脅信息環境下航路規劃。已知威脅信息環境下航路規劃根據無人機飛行環境的確定信息，在無人機執行任務之前就可以進行規劃設計，這一過程一般在無人機起飛前完成，實時性要求不高；未知威脅信息環境下航路規劃通過無人機對環境變化更新后，在飛行中對航路進行重規劃，實時性要求較高。
2 無人機航路規劃約束條件
2.1 飛行環境限制
無人機在執行任務時，會受到如禁飛區、障礙物、險惡地形等復雜地理環境的限制，因此在航路規劃時，應盡量避開這些區域，可將這些區域在地圖上標識為禁飛區域，以提升無人機工作效率。此外，飛行區域內的氣象因素也將影響任務效率，應充分考慮大風、雨雪等復雜氣象下的氣象預測與應對機制。
2.2 無人機物理限制
⑴最小轉彎半徑：由于無人機飛行轉彎形成的弧度將受到自身飛行性能限制，它限制無人機只能在特定的轉彎半徑范圍內轉彎。⑵最大俯仰角：限制了航跡在垂直平面內上升和下滑的最大角度。⑶最小航路段長度：無人機飛行航路由若干個航點與相鄰航點之間的航路段組成，在航路段飛行途中沿直線飛行，而到達某些航點時有可能根據任務的要求而改變飛行姿態，最小航路段長度是指限制無人機在開始改變飛行姿態前必須直飛的最短距離。⑷最低安全飛行高度：限制通過任務區域最低飛行高度，防止飛行高度過低而撞擊地面而墜毀。
2.3 飛行任務要求
無人機具體執行的飛行任務主要包括到達時間和進入目標方向等，需滿足如下要求：⑴航路距離約束：限制航路長度不大于一個預先設定的最大距離。⑵固定的目標進入方向：確保無人機從特定角度接近目標。
2.4 實時性要求
當預先具備完整精確的環境信息時，可一次性規劃自起點到終點的最優航路。而實際情況是難以保證獲得的環境信息不發生變換；另一方面，由于任務的不確定性，無人機常常需要臨時改變飛行任務。在環境信息變化區域不大的情況下，可通過局部更新的方法進行航路的在線重規劃；而當環境變化區域較大時，無人機航路規劃系統則必須具備在線重規劃功能。
3 無人機航路規劃算法
由于無人機所處的戰場環境異常復雜遼闊，規劃約束條件眾多，各因素之間又存在強耦合，再加上無人機自身獨特的控制方式，航路規劃在處理這些因素時面臨極大挑戰。Canny在1988年就已經證明航路規劃是一個NP問題，對其直接求解往往導致組合爆炸。為了加速規劃進程，近年來國內外學者已提出了許多不同的規劃方法。下面對已有的規劃方法加以概述。
3.1 動態規劃算法
動態規劃是分階段決策過程的最優化方法。動態規劃法是對于存在多個空中封鎖和地面障礙等多約束的情況下，采用航路圖分類法進行航路規劃。無人機根據約束，在有限的探測和處理范圍內，根據不同的滾轉角度，得到下一時刻無人機可能到達的位置，并在新的飛行點上，計算再下一時刻的位置。以此類推，得到一棵航路樹，比較樹枝終點的性能指標并找到代價最小的節點，反向搜索其父節點，得到最優航路。
動態規劃法模型簡單，對地形要求不高，算法不依賴于威脅場的連續性，容易實現。但由于動態規劃算法具有維數爆炸特性，如果在大范圍內進行動態搜索，計算機無法處理大量信息，因此動態規劃算法適于小范圍內航路規劃，對于范圍較大的區域會出現組合爆炸。
3.2 啟發式算法
啟發式算法是指通過尋求一種能產生可行解的啟發式規劃，找到問題的一個最優解或近似最優解。啟發式算法比較典型的是啟發式A*搜索法，是利用問題擁有的啟發信息來引導搜索，以達到減少搜索范圍，降低問題復雜度的目的。啟發式搜索首先定義以下代價函數：f（M）=g（M）+h（M）
式中：g（M）為啟發式因子，表示從初始節點到當前節點M的真實代價；h（M）表示從當前節點M到目標節點的最小代價估計值；f（M）則表示從初始節點經M到目標節點的最小代價路徑的估計值。搜索的原則是優先擴展f（M）小的節點，最終搜索得到最優航路（如圖2所示）。
啟發式算法由于提供了智能搜索，因此大幅度提高了搜索效率。用啟發式A*搜索法進行航路搜索時，由于需要綜合考慮各種因素，獲得一條最優航路需要很長的收斂時間和極大的內存空間，因此不適于實時求解。為此，Robert J.Szczerba等人提出了一種用于二維規劃的稀疏A*搜索算法。該算法結合航路約束有效地消減搜索空間，大大縮短了搜索時間，節省了內存空間，較好地滿足了實時性要求。
3.3 遺傳算法
遺傳算法提供了一種求解復雜問題的通用框架，它仿效生物的遺傳和進化機制，借助復制、雜交、變異等操作，使所要解決的問題從初始解一步步逼近最優解。其5個要素包括染色體編碼、初始群體、適應度函數、遺傳操作和控制參數。很多學者都將遺傳算法用行器的航路規劃求解。
在角頻率組固定的情況下，使用幅值組構造一條染色體，其基因位置表示對應的角頻率，數值代表相應的幅值。應用該型染色體構造方法進行遺傳搜索得到的優化航路（如圖3所示）。
遺傳算法計算速度快，得到的航路滿足無人機機動性能，無須再進行平滑處理，所得航路能夠嚴格經過起始點和目標點，但是容易產生早熟現象，不能得到最優解。Juris Vagners等人通過采用多種群并發計算，通過競爭機制優選的思想來解決遺傳算法的早熟現象。Ioannis K.Nikolos等人采用更能符合實際的B樣條曲線來表示航路，對無人機全局和局部航路進行規劃，得到了較好的結果。
綜上，無人機航路規劃有多種算法，既有適于小范圍的規劃算法，可在無人機上進行動態修改；又有適于大范圍的規劃算法，可在已知信息下求得全局最優解；既能進行人為的智能規劃，又能在一定范圍內進行模型的自動求解。應在具體問題具體分析基礎上，發展高效的無人機航路規劃方法。
隨著無人機所要執行的任務越來越復雜，加上環境的不確定性，對航路規劃的要求也將越來越高。未知威脅信息環境下的實時航路規劃將是未來研究的重點，高效的全局搜索方法和局部搜索方法，二者混合使用將是無人機航路規劃的一種趨勢。
[參考文獻]
[1]J.F.Gilmore.Autonomous vehicle planning analysis methodology[J].In：The Proceeding of American Control Conference，Kluwer.Boston，MA，1991.
