基于戰術背景的路徑規劃的研究

摘要： 該文通過總結分隊級仿真系統中agent的戰術需求，研究了agent借助掩體的戰術式路徑規劃。

關鍵詞： 戰術；路徑規劃；agent

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2008)25-1512-03

Research of Path-planning Based on Tactics

HE Yi-hui， ZHAO Zhou

(Institute of Command Automation， PLA University of Science and Technology， Nanjing 210007， China)

Abstract: This paper summarize the tactical demand of an agent in unit-level simulation system， and research the tactical path-planning of the agent in aid of blindage.

Key words: tactics; path-planning; agent

1 引言

所謂戰術，在軍事學上是指戰時運用軍隊達到戰略目標的手段、作戰具體部署和克敵制勝的謀略。在分隊級防真系統中，我們可以定義它為達到一定目標的操作序列。因此，戰術包括3個要素：初始狀態、目標狀態和從一個狀態移動到另一個狀態的規劃。

動態戰場環境中，agent的戰術式路徑規劃（tactical path planning）是指agent在演練過程中根據自身任務及虛擬戰場環境和其它實體的狀態，按照一定的策略使單兵從初始位置無碰撞地到達目標位置，并且滿足一些附加的約束條件的最優路徑選擇的技術，它是agent自治性的重要體現。專家們為此已經提出了一些解決方案，其中效果較好的是基于路標的方法。

1.1 戰術問題

在分隊模擬系統中，為了使計算機控制的agent在路徑規劃方面具有較為真實的表現，需要先解決戰術層面的幾種能力：

1）判斷能力：主要是對自動生成兵力而言。電腦應具備一定程度的形勢判斷能力，能夠對雙方的實力對比，敵方兵力分布，防御體系的強弱作出一定程度的判斷，并據此采取相應的戰術移動。

2）戰術配合、協作能力：模擬系統中的分隊往往因為缺乏整體協作，在移動的過程中集聚在一處有利地形上，而不能實現分隊配合作戰的思路方式，使得一些分隊的進徑看起來非常愚蠢。

3）靈活性：這是指戰術上的變化而言。如果單兵分隊模擬系統在電腦agent上都只有有限的幾種固定攻擊線路，這無疑會使模擬系統顯得單調且不真實。

1.2 戰術式路徑規劃的劃分

戰術式路徑規劃根據路徑長短有不同的劃分：

長距離路徑規劃——agent執行的任務需要行進好幾公里以上時，我們一般考慮是通過車載工具輸送。

中等距離路徑規劃——agent只需移動幾百到一兩公里的距離時，我們通?？紤]是通過步行抵達目的地，沿途需綜合考慮地形、體力、敵軍威脅和避免諸如河流等較大的障礙物并且尋找道路和橋梁。

短距離路徑規劃——agent移動距離只有幾十米到百米時，agent移動的戰術問題體現的尤其重要：考慮路徑中變化多樣的斜坡和障礙物，并且避免暴露于敵人的威脅之下。

當然戰術移動還包括：agent隱藏于掩體后面，并且變化姿勢直到移動；通過調整姿勢和方向穿過縫隙和窄道，躲避障礙；奔跑通過敵監視區；攀爬通過窗子，上梯子；跳過障礙和從障礙上跳下；踢開門等等。但是在本文中，我們僅涉及包括行走和奔跑兩種行為，從agent借助掩體實現戰術路徑規劃的角度，對步兵分隊中作戰個體的中短距離戰術路徑規劃作研究。

2 單兵agent借助掩體實現戰術路徑規劃

如果分隊模擬系統中僅僅要求agent從點A到達點B的話，那么只需要提供一條最短的無碰路徑就可以了。然而，除了到達點B，通常還要求agent在途中避免被偵查或是被射擊。這便帶來了戰術式路徑規劃的問題。要實現戰術式，兩個重要策略便是隱蔽和掩護。隱蔽是指agent借助于光線、噪音，以及自身的移動紀律和偽裝實現；掩護是指agent行動中相互依賴或是依靠地形特征。因此agent在考慮敵方的位置和他們的火力線后，通常都采取了緊貼障礙物和避開敵威脅地域繞道行進的方式。

在傳統的系統軟件中，戰場環境一般都是基于柵格的。然而 Borut Pfeifer在他的文章《利用導航網格實現自動掩體尋找》中，提出將導航網格與碰撞信息結合起來的環境，并且計算機控制的agent可以據此自動地找到掩體位置。具體方法是將導航網格進行擴展，對每個三角形的3個邊，分別增加用于描述鄰居網格導航性的附加信息，這些信息記錄了每個邊上可用的掩體，或者沒有可用掩體。然后使用標準的、運行時搜索算法，為計算機控制的agent自動偵測合法的掩體位置。我們可以在掩體附近設置隱蔽點作為路點，通過在兩個隱蔽點之間生成行進路徑，保證agent盡可能地躲在掩體后面隱蔽移動。

2.1 搜索掩體位置

在動態的戰場環境下，掩體附近對攻擊和防守都至關重要，即使是部分地隱蔽都將是重要的優勢。有時agent行動之前根本沒有預定的行動目標。如某個情景需要AI躲避起來，然而躲到哪里并沒有確定的目標點，需要agent自己選擇躲避點。這是一個決策的過程，需要考慮戰場態勢，環境及自身的狀態以尋找安全點。其實質就是尋找障礙物作為掩體。

但是定義掩體的概念是相對的，而且也經常變化，因此要想檢測一個掩體，不得不提供幾個輸入參數：

agent主體的位置，即搜索的起始點（x1，y1）。

攻擊目標位置（x2，y2）。相對于這個點的位置，才能確保確實身處掩體之中。

agent主體面向攻擊目標移動的方向的一個允許的偏離角度。

最大的“偏離距離”L。

根據6個輸入框定一個扇形區域，把搜索結果限定在幾個合理的掩體位置上。通過伸縮調整最大的偏離距離值可以戰術改變agent的路徑規劃，比如agent因為更多的掩體選擇，可以繞道至敵人身后發起攻擊。

2.2 考慮掩體的戰術價值

借助于限定搜索掩體的結果，agent可以實現戰術路徑規劃，但并非所有合理掩體在當次的路徑規劃中都有其戰術價值，因為簡單地借助隱蔽點行徑，會產生戰術上有缺陷的路徑，打破我們最初的智能幻想，高效的戰術行徑需要進一步的優化隱蔽點列表。

2.2.1選擇戰術價值高的隱蔽點作為路點

在戰場環境下，agent作戰時必須做到：“迅速”、“隱蔽”和“兇悍”。迅速，就是說agent的動作要快，在權衡戰場威脅的前提下，盡量縮短行進路徑的長度；隱蔽，對于危險的狀況而言，能借助掩體行進是agent最好的防御措施，agent在偵察時所選取的隱蔽點需滿足以下四點要求：1）能觀察遠近的情況；2）遠處的敵人很難偵察到agent；3）敵人很難有條安全路線靠近agent；4）此點允許agent比較自由的移動（進退）。

2.2.2 權衡暴露時間和次數

假設agent可以通過同樣長度的兩條路徑到達目的地。一條路徑將使agent僅僅暴露一次，不過時間將長達10秒。另一條路徑將同樣使單兵暴露10秒，但是路徑中間有一處掩體，將10秒的路徑間隔成3秒和7秒。

對于敵方來說，agent暴露的時間長度是非常關鍵的。對于單獨的一段10秒的暴露時間來說，可能已經足夠瞄準并擊斃agent了。然而，如果agent選擇后一條路徑，這種情況就不那么容易發生了?？紤]到敵方永遠是希望目標能有更長的暴露時間，而不是有更多的暴露次數。所以我們希望規劃出的路徑附近能有更多的障礙物，即有更多隱蔽點的路徑。

2.2.3 優化隱蔽點列表

路徑中設置更多的隱蔽點，不能保證一定得到更戰術化的尋徑結果，隱蔽點序列需要進一步簡化。根據agent在兩隱蔽點間運動時的敵有效射角θ、兩隱蔽點間agent暴露于敵人威脅下的行進路長l以及此次行進線相距敵人的垂直距離r三個評估因素，我們為每兩個隱蔽點間的行進路徑定義一個危險系數λ，函數表達式為：

λ=1/η（其中η= m·l/L + n·r/L + q·θ/180）

其中λ和θ、l、r三因素成反比例關系，m、n和q分別是三個評估函數的權重，它們比較難調整和確定， 隨著路徑和障礙物的情況變化而變化的。根據路徑的危險系數可以優化隱蔽點列表。

下面我們通過一個例子，可以更為容易地解釋agent是如何迅速并且安全地逼近目標點的：agent首先確定目標點位置，其后偵察可視范圍內的威脅情況并做出形勢分析。經過以上預處理后系統進行路徑規劃，首先生成隱蔽點列表，然后借助各隱蔽點的連接形成路徑。

■

圖1 agent借助掩體躍進（左圖），對掩體戰術價值考察后的修改路徑（右圖）

我們的初衷是能充分利用符合掩體要求的每個隱蔽點，將它們由遠及近都設置為此次路徑規劃的路點（圖1左）。然而刪改其中的路點，選擇所在隱蔽點對應掩體的包圍盒的其中一個頂點作為新路點，轉道行進至下一路點（圖1右）的做法，不但縮短了進攻路線，甚至還能降低行徑過程的暴露次數和時間，起到奇襲的效果。為此我們對隱蔽點列表進行優化，具體方法是針對agent所在點，考慮下兩個隱蔽點的危險系數λ，據此決定是否刪除中間的隱蔽點，依照這一方法循環計算比較，直到列表無需再作刪改，得到最優化的隱蔽點列表，及時路點列表。

移動期間，我們還要盡量避開敵人的偵察視角。如果當agent移動到障礙物4后面時，敵人視線是沿虛線方向的。如果接到攻擊指令，agent應緊貼障礙物繞行至攻擊目標的右側（受敵人威脅虛弱的點），伏擊敵人，消除路障（敵人）后行進至目標點；如果沒有能力制敵，agent將會智能地選擇4號掩體后的隱蔽點作為新的目標點。涉及到掩體附近的隱蔽點的選擇問題，這一工作也通過比較得出，具體思想是將兩掩體外包圍盒的各角相連產生路徑，比較無阻礙路徑的危險系數λ，保留λ值最小的，即保留最安全的路徑。

2.3 更戰術化的改進

由于導航地圖是經過預處理的，所以算法只能找到靜態掩體，針對這一局限性，我們設置了一個包含足夠多動態對象的列表，方便添加新的隱蔽點。

另外因為敵人的威脅并不是靜態的，他會在一個區域內巡邏，并且經常變化偵察視角，為了能得到更好的戰術式路徑，我們采取的措施是每隔大約3s重新進行agent的戰術式路徑規劃。

3 總結

路徑規劃早已不是一道新的課題，該文借助戰術變化的靈活性，豐富了模擬系統以往固定的攻擊線路選擇，使得模擬系統顯得更為真實和智能化。

參考文獻：

[1] Treglia D. 游戲編程精粹3[M]. 張磊， 譯. 北京:人民郵電出版社，2003.

[2] Kamphuis A， Rook M， Mark H. Tactical Path Finding in Urban Environments[EB\\OL]. http://www.cs.uu.nl/groups/AA/movie/publications/PDF/KRO05.pdf.

[3] Verth J V， Brueggemann V， Owen J， et al. Formation-Based Pathfinding With Real-World Vehicles[EB\\OL]. http://citeseer.ist.psu.edu/vanverth00formationbased.html.