芻議基于優(yōu)化Dijkstra算法的仿真實體路徑規(guī)劃

張賀勇 甄磊 孫娟 麻麗俊

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

1 仿真實體路徑問題

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

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

2 DlS算法

2.1 算法思路

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

2.2 算法比較

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

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

Dijkstra算法采用了數(shù)組的思想，隨著計算層數(shù)的增加，能夠較快地適應(yīng)條件變量的更新，達(dá)到快速求解的目的。在相同條件下，Dijkstra算法與基礎(chǔ)神經(jīng)網(wǎng)絡(luò)算法相比，其計算耗時低且準(zhǔn)確率高。

3 優(yōu)化算法應(yīng)用實體路徑規(guī)劃

3.1 算法優(yōu)化

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

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

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

3.2 優(yōu)化算法規(guī)劃實體路徑實現(xiàn)

針對約束條件下和移動實體目標(biāo)路徑基于Dijkstra算法的遍歷，在XSIM平臺中仿真模型以紅方雷達(dá)探測范圍作為限制條件下的Dijkstra算法遍歷閾值范圍，藍(lán)色方的殲擊機(jī)作為移動的目標(biāo)實體，藍(lán)色虛線混傷區(qū)域代表射程范圍，紅色方的源點戰(zhàn)斗機(jī)?？吭跈C(jī)場且射程范圍與藍(lán)色方殲擊機(jī)相同。指揮所在藍(lán)方殲擊機(jī)進(jìn)入雷達(dá)探測區(qū)域時，對紅方戰(zhàn)斗機(jī)下發(fā)交火任務(wù)指令摧毀藍(lán)方殲擊機(jī)。

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

4 結(jié)束語

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