人機協(xié)同搜救優(yōu)化問題的計算求解研究

鄭宇軍，楊 瀟，杜怡辰，江勛林

(1.杭州師范大學(xué) 信息科學(xué)與技術(shù)學(xué)院，浙江 杭州 311121；2.中國人民解放軍陸軍步兵學(xué)院 工程技術(shù)與應(yīng)用系，江西 南昌 330100)

同各種自然和人為災(zāi)難抗爭是人類社會的一個永恒課題。在發(fā)生嚴重傷亡的災(zāi)害中，生命搜救是第一要務(wù)。應(yīng)急搜救能力是災(zāi)害應(yīng)急管理中的一項核心能力，是處置應(yīng)急突發(fā)事件、維護社會安全穩(wěn)定的重要基石[1-2]。在剛剛過去的2021年，就有甘肅白銀馬拉松事故、云南哀牢山地質(zhì)人員失聯(lián)、山東煙臺海域“天豐369”貨船沉沒等事件中的搜救行動牽動了億萬國人的心。從技術(shù)發(fā)展的角度來看，人類社會的搜救能力的進步主要經(jīng)歷了4個階段：

(1)人類社會中早期，應(yīng)急搜救主要依賴人力(包括人類馴養(yǎng)的一些動物)進行。搜救能力主要取決于社會所能組織的人力資源，以及管理者和搜救人員自身的經(jīng)驗和水平[3]。在面臨地震、洪水等重大災(zāi)害時，早期社會往往難以組織起大規(guī)模有效的應(yīng)急搜救行動，這是歷史上很多災(zāi)害造成巨大傷亡的重要原因。

(2)進入工業(yè)革命以來，使用蒸汽和電力等能源的運輸、探測、挖掘等裝備在應(yīng)急搜救中得到廣泛應(yīng)用。這些機械化裝備極大提高了搜救的能力和效率，同時也給管理決策者帶來了新的挑戰(zhàn)，即要對人力和各類裝備進行科學(xué)的規(guī)劃調(diào)度；此外，救援人員使用裝備的技術(shù)水平也在很大程度上影響了搜救能力[4]。

(3)進入信息技術(shù)革命以來，人們對災(zāi)情、環(huán)境、任務(wù)、資源等數(shù)據(jù)和信息進行采集、處理、利用的手段大大豐富。例如可通過衛(wèi)星快速獲取災(zāi)害現(xiàn)場遙感影像，通過手機實時獲取被困人員定位并與被困人員進行通信，通過信息管理系統(tǒng)全方位掌握救援人力和資源數(shù)據(jù)等，這些都能為管理決策者提供重要支持，從而極大提高任務(wù)決策的效率和可信性。但這同時也對災(zāi)害數(shù)據(jù)分析處理能力和任務(wù)規(guī)劃調(diào)度能力提出了更高的要求。特別是在發(fā)生大規(guī)模災(zāi)害時，往往需要對多地區(qū)、多部門救援力量和資源進行統(tǒng)籌調(diào)度，并在救援過程中進行充分的數(shù)據(jù)共享和信息交換。該問題引起了國內(nèi)外管理者和研究人員的廣泛重視[5-7]。

(4)伴隨著新一代技術(shù)革命，大數(shù)據(jù)支持下的無人智能技術(shù)得到飛速發(fā)展，無人機、無人艇、地面搜救機器人、水下搜救機器人等自主智能裝備為應(yīng)急搜救提供了全新的手段，并在大量實際應(yīng)急搜救行動中取得了很好的效果[8]?；仡?008年汶川地震，由于災(zāi)區(qū)通信中斷、大量臺站被破壞，一線災(zāi)情無法及時被送出，最終是數(shù)百名空降兵“舍命一搏”高空跳傘進入災(zāi)區(qū)，才打通與外界的聯(lián)系通道；而到了六年后的魯?shù)榈卣穑?個無人機組在第一時間進入災(zāi)區(qū)并傳回高分辨率影像圖，被認為是我國無人機救災(zāi)應(yīng)用的歷史性時刻。當然，智能機器人同樣需要對其行動路線和任務(wù)進行合理的規(guī)劃和調(diào)度，特別是多機器人的協(xié)同調(diào)度具有很高的難度[9]。

近年來，機器人搜索方法研究引起了廣泛的興趣。這些方法可以分為局部搜索和全局搜索兩大類。局部搜索方法主要規(guī)劃機器人當前或未來有限時間段內(nèi)的動作，常用的算法有梯度下降算法[10]、貪婪算法[11]、特定邊界搜索算法[12-13]，以及這些算法的混合形式[14-15]。全局搜索方法則針對某個全局目標函數(shù)(如最終搜索成功概率或預(yù)期搜索完成時間)來預(yù)先規(guī)劃完整的搜索路徑，常用的算法有優(yōu)度比搜索[16]、Monte Carlo樹搜索[17]、擴展鄰域搜索[18]等問題特定的啟發(fā)式搜索算法，以及遺傳算法[19]、細菌覓食算法[20]、差分進化[21]、蟻群優(yōu)化[22，23]、粒子群優(yōu)化[24]等元啟發(fā)式搜索算法。陳佳[25]等人研究了無人駕駛救助船路徑規(guī)劃算法，在Dijkstra最短路徑算法的基礎(chǔ)上使用蟻群優(yōu)化算法進行路徑規(guī)劃。Mendonca[26]等研究了海難幸存者搜救中的無人艇與無人機協(xié)作調(diào)度方法。Wang[27]等研究了海上搜救無人機通過深度學(xué)習(xí)進行目標定位和搜索的方法，通過假設(shè)生成和驗證來提高對幸存者的識別精度。Wang[28]等提出了一種無人機搜索未知目標的超啟發(fā)式算法，其中即考慮了每個待搜索區(qū)域中的目標存在概率，也考慮了無人機在不同搜索模式下的搜索成功概率。Hong[29]等將該問題擴展到多無人機場景，并提出一種融合自適應(yīng)局部搜索的文化基因算法來求解該問題。Du[30]等研究了一個景區(qū)失蹤游客的無人機搜索問題，提出了基于地理位置及時空關(guān)系的目標概率估計方法，并設(shè)計了無人機路徑規(guī)劃的進化算法。

但在很多復(fù)雜任務(wù)場景中，智能機器仍無法完全取代人的作用。例如在地震被困人員搜救中，無人機可用于快速尋找被困者，隨后還需要救援人員幫助其脫困并進行急救治療。人機之間的高效智能協(xié)同是提高此類任務(wù)能力的關(guān)鍵。但目前對人機協(xié)同搜救方法的研究還很有限。Liu[31]研究了一種基于貝葉斯推理的分配算法，用于將待搜索區(qū)域合理劃分并分配給人和無人機進行搜索。Hong[32]等研究了一種基于強化學(xué)習(xí)的控制方法，用于簡化搜救過程中人對機器的控制操作。還有一些研究[33]關(guān)注如何提高人機交互體驗。但這些研究都并未體現(xiàn)真正意義上人機協(xié)同的內(nèi)在需求[34]。未來復(fù)雜的搜救任務(wù)不僅需要先進的智能機器人，更需要人機之間的高效智能協(xié)同來提高搜救能力。近年來，本團隊在長期研究應(yīng)急搜救調(diào)度方法及其實踐應(yīng)用的基礎(chǔ)上，開展了人機協(xié)同搜救調(diào)度方法的探索性研究[35-36]，一方面體現(xiàn)機器人對提升任務(wù)能力的巨大作用，另一方面關(guān)注人在任務(wù)中不可替代的環(huán)節(jié)，從搜救任務(wù)的內(nèi)在需求出發(fā)，通過人機協(xié)同優(yōu)化調(diào)度，突破任務(wù)性能瓶頸，從根本上提升任務(wù)能力。

本文考慮的場景是：在指定區(qū)域內(nèi)，多個人工搜索隊與機器人協(xié)同搜救某個目標，如果人工搜索隊發(fā)現(xiàn)目標，則任務(wù)完成；如果機器人首先發(fā)現(xiàn)目標，則還需要人工搜索隊到達目標位置方能完成任務(wù)。若是機器人首先發(fā)現(xiàn)目標，接下來的目標行為可分為3種模式：(1)目標靜止等待救援；(2)目標主動向人工搜索隊靠攏；(3)目標逃避搜索。針對每種模式，分別構(gòu)建問題的優(yōu)化模型，以任務(wù)完成的期望時間最小化作為目標函數(shù)。為了優(yōu)化目標函數(shù)，人工搜索隊的動作路徑和機器人的動作路徑之間需要進行有效協(xié)同：如果人和機器人過于分散，發(fā)現(xiàn)目標的時間可能較早，但機器人發(fā)現(xiàn)目標后，人工搜索隊可能需要很長的時間才能到達目標位置；反之，如果人和機器人過于靠近，機器人發(fā)現(xiàn)目標后人工搜索隊可以很快到達目標位置，但發(fā)現(xiàn)目標的時間可能較長。因此問題的決策需要在上述兩種情況之間取得一個較好的平衡。本文設(shè)計了進化算法與局部搜索相結(jié)合的混合優(yōu)化算法，對3種模式下的人機搜救行動進行協(xié)同優(yōu)化調(diào)度。最后，基于我國南方山區(qū)及丘陵等典型地貌構(gòu)建搜救問題測試實例，計算實驗的結(jié)果驗證了本文所提模型及算法的有效性。

1 人機協(xié)同搜救優(yōu)化問題的典型數(shù)學(xué)模型

1.1 目標被發(fā)現(xiàn)后保持靜止的模型

圖1 不同搜索模式示意圖

搜救任務(wù)有兩個關(guān)鍵時間點，一是目標被發(fā)現(xiàn)的時間，這里記為T；二是人工搜索隊接觸到目標的時間，這里記為T*。如果是人工搜索隊首先發(fā)現(xiàn)目標，此時有T=T*，任務(wù)完成；當機器人首先發(fā)現(xiàn)目標時，距離目標最近的人工搜索隊將從T時刻開始趕往目標所在地，此時有T

先考慮目標被發(fā)現(xiàn)的時間。如果目標被人工搜索隊發(fā)現(xiàn)，時間記為Th；如果目標被機器人發(fā)現(xiàn)，時間記為Tu。初始時發(fā)現(xiàn)目標的概率為0，則有：

P(Th=0)=0，

(1)

P(Tu=0)=0.

(2)

在搜索行動中，一般同一時刻同一區(qū)域最多只有一個搜索單位(人工搜索隊或機器人)對其執(zhí)行搜索操作，故不同搜索單位發(fā)現(xiàn)目標的事件是相互獨立的。人工搜索隊在任一時刻t>0發(fā)現(xiàn)目標的概率公式可展開為

(3)

其中

(4)

對應(yīng)的，機器人在任一時刻t>0發(fā)現(xiàn)目標的概率公式可展開為

(5)

其中

(6)

(7)

(8)

其中

(9)

式(9)等號右側(cè)if分支條件表示機器人在t′時刻發(fā)現(xiàn)目標，而后最近的人工搜索隊使用(t-t′)的時間段趕到目標位置。

(10)

即使只考慮人工搜索隊或只考慮無人機，其搜索路徑規(guī)劃可視為經(jīng)典的車輛路徑規(guī)劃問題，該問題已知為NP難題[37]。本問題在人機各自路徑規(guī)劃的基礎(chǔ)上還考慮人機之間的協(xié)同，其復(fù)雜度高于車輛路徑規(guī)劃問題。

1.2 目標被發(fā)現(xiàn)后向人工搜索隊靠攏的模型

圖2 目標被發(fā)現(xiàn)后向人工搜索隊靠攏示意圖

(11)

若是目標所在區(qū)域不能完全自由行動，則要找出其可以行動的路徑，并計算人工搜索隊到目標最短路徑距離來替換式(11)中的右側(cè)的分子項。

(12)

該條件的判斷比1.1節(jié)模型中的條件判斷更為復(fù)雜，因此問題復(fù)雜度也更高，同樣屬于NP難題。

1.3 目標被發(fā)現(xiàn)后逃避搜救的模型

(13)

再根據(jù)一元二次方程求根公式可得Δt(j*)。實際計算中，選取三個可能的目標移動方向，即與機器人方向一致，以及與機器人方向垂直(夾角為90°或270°)，對三個θ角度分別計算Δt(j*)值，并以三者的平均值作為Δt(j*)的最終估值。

圖3 目標被發(fā)現(xiàn)后逃避搜索示意圖

若是目標所在區(qū)域不能完全自由行動，則可以對其可能選擇的各條移動路徑分別計算Δt(j*)，在以這些結(jié)果的作為Δt(j*)的最終估值。

最后將Δt(j*)的最終估值代入式(12)，計算任務(wù)完成時間的概率分布。該問題同樣也屬于NP難題。

2 人機協(xié)同搜救優(yōu)化問題的混合進化算法

上述問題屬于復(fù)雜的路徑規(guī)劃問題，問題解空間隨著搜索區(qū)域數(shù)量和搜索單位數(shù)量的增加而呈爆炸性增長，傳統(tǒng)精確優(yōu)化算法難以有效應(yīng)對[37]。特別的，上述問題的目標函數(shù)需要基于時間變化不斷推演，計算量很大；而問題的優(yōu)化目標是基于概率估計的期望值，沒有必要追求絕對最優(yōu)解。因此，這里提出一種混合進化算法來求解上述問題。算法首先生成一個種群的初始解，而后對種群進行迭代進化。在每次迭代時，對每個解首先進行變異操作；如果變異解優(yōu)于原始解，則替換原始解；否則再對該解進行遷移操作。算法還對找到的較優(yōu)解進行局部搜索，以提高解的精度。算法的基本流程如圖4所示。下面分別介紹算法各部分操作的實現(xiàn)過程。

圖4 求解人機協(xié)同搜救優(yōu)化問題的啟發(fā)式算法流程

2.1 初始解生成

問題的每個解z的編碼由n1個人工搜索隊的動作路徑{x1，x2，…，xn1}和n2個機器人的動作路徑{y1，y2，…，yn2}組成。設(shè)算法種群大小為N，初始種群中包含N-2個隨機生成的解，以及2個采用不同貪心策略得到的解。注意無論采用哪種方式，人工搜索隊的路徑必須由相鄰的子區(qū)域構(gòu)成，機器人則視行動方式?jīng)Q定其路徑是否要由相鄰的子區(qū)域構(gòu)成(如地面機器人需要；無人機不需要，它可以快速飛往一個遠處的子區(qū)域進行搜索)。隨機生成解時，通過隨機選擇尚未分配的可行子區(qū)域并隨機設(shè)置搜索模式來逐步構(gòu)造每條路徑。采用第一種貪心策略構(gòu)造路徑時，每次在尚未分配的可行子區(qū)域集合中選取目標發(fā)現(xiàn)概率p(i，t)ph(i，k1，t)或p(i，t)pu(i，k2，t)與預(yù)期搜索時間th(i，k1)或tu(i，k2)的比值最大的一個子區(qū)域并設(shè)置相應(yīng)的搜索模式。采用第二種貪心策略構(gòu)造路徑時，先對機器人采用第一種貪心策略構(gòu)造路徑，而后再對人工搜索隊構(gòu)造路徑，每次在尚未分配的可行子區(qū)域集合中選取與機器人最接近的一個子區(qū)域，以便于在機器人發(fā)現(xiàn)目標后快速到達目標位置。

2.2 變異操作

變異操作的方式是將解中的一部分路徑進行重新配置，從而提高種群的多樣性。這里采用一種自適應(yīng)的變異操作，每個解變異的程度與解的適應(yīng)度成反比：較優(yōu)的解變異度較小，即在較小范圍內(nèi)搜索；較差的解變異度較大，即在較大范圍內(nèi)搜索。每個解z的變異度通過其變異率ν(z)來控制，其初始值統(tǒng)一設(shè)為0.5；在每次迭代后，解的變異率根據(jù)其目標函數(shù)值f(z)按下式進行更新：

v(z)=v(z)·α-(fmax-f(z)+ε)/(fmax-fmin+ε)，

(14)

其中fmax和fmin分別代表種群中解的目標函數(shù)值的最大值和最小值，α是一個大于1的常數(shù)，ε為一個極小的正數(shù)以避免發(fā)生除以0的情況。該公式借鑒的是水波優(yōu)化啟發(fā)式算法的波長控制方程[38]，它使得變異率隨迭代次數(shù)不斷減小，即算法早期側(cè)重于全局搜索、后期側(cè)重于局部搜索；而且解越優(yōu)、變異率減小得越快、局部搜索也越明顯。這樣能夠在局部搜索和全局搜索間達到一個較好的平衡。

對每個解z進行變異操作的具體步驟如下：

(1)設(shè)置一個空的待變異路徑集Pz；

(2)對解中的每個路徑xj或yj，以ν(z)的概率加入Pz；

(3)對Pz中的所有路徑進行子區(qū)域重新隨機分配和搜索模式重新隨機設(shè)置，Pz以外的路徑保持不變。

2.3 遷移操作

當變異操作未能改進z時，算法對其進行遷移操作，該操作和遺傳算法中的雜交操作思想類似，但它不是對兩個解進行組合，而是使當前解向種群中的其它優(yōu)秀解進行學(xué)習(xí)，以求提高解的質(zhì)量。和變異操作的變異率控制類似，每個解z的遷移操作通過一個遷移率μ(z)來控制，其計算公式如下：

μ(z)=(f(z)-fmin+ε)/(fmax-fmin+ε).

(15)

式(15)借鑒的是生物地理學(xué)優(yōu)化啟發(fā)式算法的遷移率計算方程[39]，它使得較差的解具有較大的遷移率，從而更多地向其余解學(xué)習(xí)；較優(yōu)的解具有較小的遷移率，從而改變較小。這也能夠促進局部搜索和全局搜索間的平衡。

2.3.1 人工搜索隊動作路徑遷移

2.3.2 機器人動作路徑遷移

(3)對yj中的子區(qū)域進行重排序，每次選擇距機器人最近的子區(qū)域加入到路徑中。

遷移操作后，如出現(xiàn)某些子區(qū)域未被搜索或被重復(fù)搜索的情況，如果對每個出現(xiàn)在多條路徑中的子區(qū)域a，使其只保留在目標發(fā)現(xiàn)概率與預(yù)期搜索時間的比值最大的一條路徑中；對每個未被搜索的子區(qū)域a，嘗試將其插入到每條現(xiàn)有路徑中，最后選擇插入后任務(wù)完成時間最早的那條路徑。

2.4 增強局部搜索

每當算法通過變異操作或遷移操作找到一個新的當前最優(yōu)解z*，則對其進行增強局部搜索來提高解的質(zhì)量。具體操作方式是對其每條動作路徑上的每個區(qū)域，嘗試改變搜索模式k為k±1(但不超過預(yù)定上下限)，如目標函數(shù)得以改進則保留新模式。

算法1給出了整個算法的偽代碼，其中隨機函數(shù)rand()用于生成[0，1]之間的一個隨機數(shù)，算法的終止條件通常是迭代次數(shù)或目標函數(shù)估值次數(shù)到達指定上限。人機協(xié)同搜救優(yōu)化問題的啟發(fā)式求解算法框架如圖5所示。

圖5 人機協(xié)同搜救優(yōu)化問題的啟發(fā)式求解算法框架

3 計算實驗

計算實驗基于四川達州山區(qū)和江西東北部丘陵地區(qū)兩種實際地形。對每種地形分別設(shè)置兩個不同大小的搜索區(qū)域(山區(qū)搜索面積分別為9.1 km2和21.2 km2，丘陵地區(qū)搜索面積分別為15.6 km2和53 km2，劃分的子區(qū)域數(shù)m分別為18、45、29和105)，并分別模擬地震人員失蹤(目標不能移動)、游客受傷失聯(lián)(目標可移動配合搜救)、逃犯逃跑(目標逃避搜索)3種場景模型，根據(jù)實際地貌氣候等信息進行概率估計。搜救行動所允許的最大時間tmax設(shè)置為5 min。每個場景以不同數(shù)量的人工搜索隊和無人機為搜索單位(n1×n2分別為2×2，4×3，10×5)構(gòu)造3個測試實例，共計36個測試實例。在這些問題實例上，將本文所提方法與以下6個方法進行比較：

(1)由當?shù)貞?yīng)急管理工作人員基于經(jīng)驗制定搜救方案；

(2)基于貝葉斯概率的貪心(Greedy)算法[40]，它總是在未分配的子區(qū)域中選擇目標存在概率最大的子區(qū)域分配給最近的搜索單位空閑無人機；

(3)基于部分可觀察馬爾科夫決策過程(Partially observable Markov decision procedure，POMDP)的啟發(fā)式算法[41]，它通過在每個時間片內(nèi)最大化期望發(fā)現(xiàn)概率來決定各個搜索單位的行動；

(4)一種鴿群啟發(fā)的粒子群優(yōu)化(Pigeon-inspired particle swarm optimization，P-PSO)算法[42]來求解本文的優(yōu)化模型；

(5)一種蟻群優(yōu)化(Ant colony optimization，ACO)算法來求解本文的優(yōu)化模型；

(6)一種自適應(yīng)大規(guī)模鄰域搜索(Adaptive large neighborhood search，ALNS)算法來求解本文的優(yōu)化模型。

開展算法比較實驗之前，先選擇不同規(guī)模的3個測試實例，在其上對包含控制參數(shù)的P-PSO、ACO、ALNS及本文算法這4個元啟發(fā)式算法進行參數(shù)調(diào)整，使得算法參數(shù)設(shè)置在這3個實例上達到最佳平均性能。通過測試調(diào)參，PSO、ACO、ALNS和本文算法的種群大小分別設(shè)為35、50、45和60。之后，采用調(diào)整好的參數(shù)，所有算法在36個測試實例上進行比較實驗。元啟發(fā)式算法的終止條件均設(shè)為對目標函數(shù)的估值次數(shù)達到100mn1n2，以保證算法比較的公平性。對具有隨機性的啟發(fā)式算法，每種算法在每個測試實例上重復(fù)運行30次；鑒于搜救任務(wù)的緊迫性，每個算法單次求解問題的CPU運行時間不超過15min。計算實驗環(huán)境配置為i9-10885 CPU，GeForce 1650Ti GPU，32GB DDR4內(nèi)存及2TB SSD硬盤。由于目標搜索和發(fā)現(xiàn)存在概率估計，對算法求得的每個解(搜救方案)，在對應(yīng)測試實例上進行500次蒙特卡洛仿真，分別統(tǒng)計發(fā)現(xiàn)目標和成功救援目標的時間的中位數(shù)。

圖6(a)和圖6(b)分別給出了第一類場景(目標被發(fā)現(xiàn)后保持靜止)的測試實例上各個算法得到的目標發(fā)現(xiàn)時間和搜救完成(即人工救援隊到達目標位置)時間。從結(jié)果中可以發(fā)現(xiàn)，在前幾個搜索區(qū)域不大、任務(wù)時間不長的較簡單測試實例上，各個方法得到的目標發(fā)現(xiàn)時間相差不大，有時候人工決策、Greedy和POMDP方法得到的目標發(fā)現(xiàn)時間甚至優(yōu)于其余4個啟發(fā)式進化算法；但在搜救任務(wù)完成時間上，求解本文優(yōu)化模型的4個啟發(fā)式算法性能幾乎在所有測試實例上的結(jié)果都明顯優(yōu)勢前3個方法，這主要是因為Greedy和POMDP方法都是以盡早發(fā)現(xiàn)目標為求解方向，沒有對無人機發(fā)現(xiàn)目標后人工搜索隊趕往目標位置所需的時間進行有效優(yōu)化；人工決策方法也難以合理預(yù)測和控制這項時間要素。而本文優(yōu)化模型對該時間要素進行了合理建模，以搜救完成時間最小化為目標函數(shù)，能夠有效地引導(dǎo)求解方向，從而在結(jié)果解中體現(xiàn)良好的人機協(xié)同控制。特別的，當搜索區(qū)域較大時，由于無人機速度快、設(shè)備精度高，其早于人工搜索隊發(fā)現(xiàn)目標的可能性也很大，因此啟發(fā)式算法的性能優(yōu)勢也就更為明顯。

圖6 第1類場景模型的比較實驗結(jié)果

比較4個啟發(fā)式算法，它們在前幾個較簡單測試實例的性能差別并不明顯；但隨著測試實例規(guī)模的增加，算法之間體現(xiàn)出了性能差距。其中P-PSO較簡單測試實例上的性能最差，這主要是因為該算法向當前全局最優(yōu)和個體歷史最優(yōu)學(xué)習(xí)的策略使其容易過早收斂。在其余大部分測試實例上，ALNS表現(xiàn)的性能較差，這說明在大規(guī)模解空間搜索時，ALNS的鄰域搜索機制不如其它的進化搜索機制高效。在所有方法中，本文提出的混合進化算法表現(xiàn)出了最優(yōu)的性能，而且性能優(yōu)勢隨著問題規(guī)模的增長而更加明顯，這驗證了本文設(shè)計的變異、遷移和增強局部搜索算子的組合能夠高效地搜索問題解空間。此外，在后幾個大規(guī)模問題實例上，啟發(fā)式算法得到的目標發(fā)現(xiàn)時間也優(yōu)于前3個方法，這也進一步說明了啟發(fā)式進化算法針對較大解空間的搜索能力是遠高于人工決策方法和簡單構(gòu)造式求解策略的。

圖7(a)和圖7(b)分別給出了第2類場景(目標被發(fā)現(xiàn)后向人工搜索隊靠攏)的測試實例上各個算法得到的目標發(fā)現(xiàn)時間和搜救完成時間。在這類測試實例上，各個算法求得的目標發(fā)現(xiàn)時間和前一類差別不大。但由于目標被發(fā)現(xiàn)后會主動向人工搜索隊靠近，因此各個算法求得的搜索完成時間相比前一類測試實例有明顯提前。在7個比較算法中，4個啟發(fā)式算法的搜索完成時間提前相對于前3個算法更為明顯，這驗證了本文提出了第2個優(yōu)化模型能夠有效刻畫目標向人工搜索隊靠近的行為特征。同樣，在各個比較算法中，本文所提的啟發(fā)式進化算法展現(xiàn)了最好的性能，說明該算法的搜索機制針對第2類問題解空間的搜索也很高效。

圖7 第2類場景模型的比較實驗結(jié)果

圖8(a)和圖8(b)分別給出了第3類場景(目標逃避搜索)的測試實例上各個算法得到的目標發(fā)現(xiàn)時間和搜救完成時間。在這類測試實例上，各個算法求得的目標發(fā)現(xiàn)時間和搜索完成時間相比第1類都有增加，而且搜索完成時間的增加更為明顯。在各個比較算法中，啟發(fā)式算法的搜索完成時間的增幅小于前3個算法，這驗證了本文的第3個優(yōu)化模型能夠有效刻畫目標逃避搜索的行為特征。類似的，本文所提的算法的性能在這類測試實例上的表現(xiàn)仍是最好的，驗證了算法搜索機制針對第3類問題解空間搜索的效率。

圖8 第3類場景模型的比較實驗結(jié)果

4 結(jié)束語

很多應(yīng)急搜救任務(wù)都需要人與智能機器人的協(xié)同來提高任務(wù)完成效率，但現(xiàn)有的人機協(xié)同搜救方法研究還很有限。本文通過對3類典型人機協(xié)同搜救場景及其需求的分析，針對目標被發(fā)現(xiàn)后的不同行為模式，構(gòu)建了3個不同的優(yōu)化模型，并設(shè)計啟發(fā)式進化算法來有效求解這些優(yōu)化問題。計算實驗結(jié)果驗證了本文所提模型及算法的有效性。

本文模型需要已知搜索區(qū)域中的目標存在概率及搜索過程中的目標發(fā)現(xiàn)概率。這些概率可基于搜索區(qū)域的地形地貌、氣候、目標初始位置及行為特征等信息對進行估計，對此已開展了初步研究并取得了一定的效果。在更復(fù)雜的實際應(yīng)用中，目標的行為特征可能具有很多的不確定性。下一步擬開展多學(xué)科交叉研究，對災(zāi)害被困人員、野外失蹤人員、逃犯等典型搜救目標的心理行為和行動特征進行更為深入的分析和更為充分的建模，對其在不同環(huán)境下的行為模式進行更為合理和準確的推演，以進一步提高搜救行動的效率和準確性。