芻議基于優化Dijkstra算法的仿真實體路徑規劃

張賀勇 甄磊 孫娟 麻麗俊

北方自動控制技術研究所 山西 太原 030006

1 仿真實體路徑問題

在仿真過程中，無論是目標打擊任務，還是實體機動巡邏任務，模型實體機動的路徑是否符合我們預想的目標一直都是我們關心的問題。尤其是在軍事推演方面，實體機動的路徑也算是推演過程中的一部分。手動添加設置機動點不需要我們考慮實體機動路徑是否合理，實體模型只需按照預設的機動點逐點機動即可。但是在仿真平臺自行推演實體機動的過程中，就需要我們通過算法來實現合理的實體機動路徑。

以偵察打擊目標來說，在偵察實體發現多個固定目標如空軍基地、雷達站、指揮所等時，混傷爆破實體接收打擊目標位置坐標，并向目標位置機動，在打擊范圍內摧毀目標實體。在上面的偵察打擊目標任務中，混傷爆破實體出發位置就可以理解為推演實體路徑原點，固定目標實體位置對應于軌跡路徑所要經過的點。與傳統的多個點所構成的圖的遍歷所形成的一條路徑不同，這里我們還要考慮限制條件混傷爆破實體的打擊范圍，即加了限制條件一定范圍內無向圖中各點的遍歷路徑問題[1]。

2 DlS算法

2.1 算法思路

針對上面仿真推演過程中實體軌跡路徑所轉化成的無向圖中各點之間的遍歷問題，無論是哪種遍歷方法，最終遍歷結束之后都會形成一條軌跡，這條軌跡就是實體在推演過程中的機動路徑。對于少量節點的實體模型來說，逐點遍歷形成一個路徑軌跡即可，對于多個節點的實體路徑來講，就要依靠算法來實現一條高效的軌跡路徑，這里我們給出利用Dijkstra算法（簡稱為DIS算法）來實現實體路徑的規劃。

2.2 算法比較

對于最短路徑算法，目前被應用最廣的有：Dijkstra、Floyd、Bellman-ford三種算法。三種算法各有優缺點，Dijkstra算法復雜度低且比較容易實現，但不適用于多源點存在負權值圖的路徑遍歷。Floyd算法可用于遍歷多源點帶負權邊的圖，缺點是算法復雜度高且雙鄰接矩陣的算法實現繁雜難懂。Bellman-ford算法適用于權值有負值的圖且能夠檢測負圈，但對于稠密圖的路徑遍歷來說算法復雜度過高，關系密切的頂點來說亦是如此。

雖然Dijkstra算法比較于Floyd和Bellman-ford算法來說不能遍歷帶負權的圖，但Floyd算法復雜度高對于稠密圖的最短路徑遍歷來說耗費的內存和時間過大。Bellman-ford算法雖然復雜度低，但其只適用于稀疏圖，在現實問題中我們往往面對的都是稠密圖最短路徑的遍歷。所以以算法的復雜度和適用范圍來說，這里我們以Dijkstra算法為基礎來進行實體路徑規劃。

Dijkstra算法采用了數組的思想，隨著計算層數的增加，能夠較快地適應條件變量的更新，達到快速求解的目的。在相同條件下，Dijkstra算法與基礎神經網絡算法相比，其計算耗時低且準確率高。

3 優化算法應用實體路徑規劃

3.1 算法優化

（1）源點確定。與Dijkstra算法中自行確定源點位置的情況不同，算法在仿真平臺應用時，在對想定中實體進行推演仿真的過程中，我們所要確定的源點對象是具有機動能力的實體。像戰斗機、裝甲車、突擊班等這些具有機動打擊行為的實體都可以作為我們在初始化算法時的源點位置。

（2）節點與邊的確定。同樣的對于Dijkstra算法中遍歷節點與邊的確定，將仿真平臺想定編輯中的固定目標實體作為確定的節點位置，像軍事基地、指揮所、雷達、機場等。Dijkstra算法圖中節點之間的邊都是給出的，對于在仿真場景中源點和遍歷節點存在確定邊的情況，我們默認為源點到每個節點都存在一條可直接到達的邊。當然對于超出一定距離閾值的情況我們就認為其需要借助其他點來到達。

（3）針對移動目標的實現方案。Dijkstra算法不能實現對移動實體目標在仿真過程的路徑遍歷，針對移動的實體目標，這里我們給出一種在我們的約束條件下的優先路徑遍歷方案。在移動目標進入閾值范圍且進入源點實體限制因素射程范圍內時，優先在仿真周期對移動實體目標進行路徑遍歷。

3.2 優化算法規劃實體路徑實現

針對約束條件下和移動實體目標路徑基于Dijkstra算法的遍歷，在XSIM平臺中仿真模型以紅方雷達探測范圍作為限制條件下的Dijkstra算法遍歷閾值范圍，藍色方的殲擊機作為移動的目標實體，藍色虛線混傷區域代表射程范圍，紅色方的源點戰斗機停靠在機場且射程范圍與藍色方殲擊機相同。指揮所在藍方殲擊機進入雷達探測區域時，對紅方戰斗機下發交火任務指令摧毀藍方殲擊機。

利用上方建立的實體模型，相同條件下利用Dijkstra算法與原有算法比較得到仿真結果。根據仿真結果可知，在相同的條件下，都實現了在藍色方殲擊機進入偵察區域紅方戰斗機開始對目標進行打擊，并在射程范圍內摧毀藍方殲擊機，黑色標記為藍方殲擊機被擊落點。但平臺本身算法仿真結果顯示戰斗機往返路徑基本相同，運用Dijkstra算法仿真推演得到的實體路徑軌跡更加符合我們所要求的標準。

4 結束語

在互聯網技術高速發展的今天，對于軍事仿真的效果越來越高。對于優化的Dijkstra算法來說，其不僅僅是應用在仿真推演過程中的實體路徑軌跡規劃的問題上。在XSIM平臺中應用Dijkstra算法解決的路徑軌跡推演的問題，在技術互通的今天，其他平臺的仿真實體路徑問題亦可運用上面的思想來解決同一類的路徑問題。像三維場景中的藍軍智能行為牽扯到的巡邏、機動、上下車等問題，都可以利用Dijkstra算法思想來解決。