本科畢業(yè)設(shè)計(jì)題 目： 無(wú)人機(jī)組群巡檢滅火系統(tǒng)設(shè)計(jì) 學(xué) 院： 機(jī)電工程學(xué)院 專(zhuān) 業(yè)： 機(jī)械設(shè)計(jì)制造及其自動(dòng)化 姓 名： 學(xué) 號(hào)： 指導(dǎo)教師： 年 5 月 28 日 摘 要隨著無(wú)人機(jī)執(zhí)行任務(wù)的環(huán)境日益復(fù)雜，任務(wù)類(lèi)型日益多樣，無(wú)人機(jī)己經(jīng)開(kāi)始從單架次獨(dú)立任務(wù)的方式向著多架次、多類(lèi)型的機(jī)群作戰(zhàn)方向發(fā)展。通過(guò)對(duì)多無(wú)人機(jī)協(xié)同任務(wù)分配的研究，可以使系統(tǒng)完成的任務(wù)類(lèi)型更為多樣，同時(shí)任務(wù)完成的質(zhì)量和效率也獲得較大程度的提高。本文研究了集中式多類(lèi)型無(wú)人機(jī)編隊(duì)任務(wù)分配方法。集中式指的是任務(wù)分配過(guò)程中，無(wú)人機(jī)處于從屬地位，不具有自主能力，完全受控制站中人的控制。多類(lèi)型指的是無(wú)人機(jī)類(lèi)型和執(zhí)行能力的不同。本文首先介紹了無(wú)人機(jī)的應(yīng)用現(xiàn)狀，討論了幾種任務(wù)分配算法，分析了他們的優(yōu)缺點(diǎn)。其次，在靜態(tài)環(huán)境下基于平面網(wǎng)格坐標(biāo)系，建立了一個(gè)多無(wú)人機(jī)任務(wù)分配數(shù)學(xué)模型，設(shè)計(jì)了一種有人參與的靜態(tài)分配算法。然后利用了一個(gè)無(wú)人機(jī)森林滅火的實(shí)例，通過(guò) MATLAB 仿真和分析說(shuō)明了算法的可行性和實(shí)用性。最后，在動(dòng)態(tài)環(huán)境中，根據(jù)無(wú)人機(jī)狀態(tài)改變和任務(wù)改變兩種情況，對(duì)動(dòng)態(tài)任務(wù)進(jìn)行了動(dòng)態(tài)重分配。關(guān)鍵字:無(wú)人機(jī)；任務(wù)分配；靜態(tài)分配；動(dòng)態(tài)重分配1AbstractWith the increasingly complex environment, the missions of the UAV grow variously. The operational manner of UAV changes from the independence towards the multi-way, more types of UAV. through the research of the assignation of the multi-type UAV, you can make the types of completed tasks more diversely and the quality and efficiency improved greatly.This paper addresses the problem of task allocation in the centralized and multi-type UAV fleets. Centralized refers to in the task allocation process, UAV is in asubordinate position, UAV do not have independent ability, completely under controlof human in control base. Multi-type UAV refers to the different abilities of UAV.First of all, this paper introduces the present situation of the applications of UAV,discussed some kinds of task allocation algorithms and analyzed their advantages anddisadvantages. What's more, in a static environment, based on the planar grid coordinate system, we set up a multi-UAV task allocation mathematical model and designed a Static allocation algorithm with humans attended. Then use an example of forest outfire to Show the feasibility and practicability of the algorithm by the simulation analysis of Matlab. Finally, according to two situations: UAV changed or tasks changed, the task allocation changes to dynamic redistribution, in dynamic environment.Keywords: UAV ；Task allocation ；Static allocation ；Dynamic redistribution2目 錄第 一 章 緒 論 161.1 任 務(wù) 分 配 的 研 究 背 景 161.2 國(guó) 內(nèi) 外 無(wú) 人 機(jī) 應(yīng) 用 現(xiàn) 狀 161.2.1 應(yīng) 用 在 軍 事 上 161.2.2 應(yīng) 用 在 自 然 災(zāi) 害 的 防 護(hù) 上 161.3 論 文 的 主 要 內(nèi) 容 161.4 論 文 組 織 結(jié) 構(gòu) 16第 二 章 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 研 究 現(xiàn) 狀 及 發(fā) 展 趨 勢(shì) 162.1 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 的 定 義 及 解 決 步 驟 162.1.1 UAV 任 務(wù) 分 配 問(wèn) 題 的 定 義 162.1.2 UAV 任 務(wù) 分 配 問(wèn) 題 的 描 述 162.1.3 解 決 UAV 任 務(wù) 分 配 問(wèn) 題 的 步 驟 162.2 無(wú) 人 機(jī) 任 務(wù) 分 配 控 制 方 法 162.2.1 集 中 式 控 制 162.2.2 分 布 式 控 制 162.3 無(wú) 人 機(jī) 任 務(wù) 分 配 模 型 分 類(lèi) 162.3.1 多 旅 行 商 問(wèn) 題 模 型 162.3.2 通 用 分 配 問(wèn) 題 模 型 162.3.3 車(chē) 輛 路 徑 問(wèn) 題 模 型 162.3.4 混 合 整 數(shù) 線 性 規(guī) 劃 模 型 162.3.5 CMTAP 通 用 模 型 162.4 靜 態(tài) 任 務(wù) 分 配 算 法 162.4.1 群 算 法 162.4.2 市 場(chǎng) 類(lèi) 算 法 162.4.3 進(jìn) 化 理 論 算 法 162.5 動(dòng) 態(tài) 環(huán) 境 中 多 任 務(wù) 重 分 配 算 法 1632.5.1 合 同 網(wǎng) 算 法 162.5.2 拍 賣(mài) 算 法 162.5.3 聚 類(lèi) 算 法 16第 三 章 靜 態(tài) 環(huán) 境 下 無(wú) 人 機(jī) 任 務(wù) 分 配 163.1 任 務(wù) 分 配 場(chǎng) 景 和 限 制 條 件 163.1.1 任 務(wù) 分 配 的 場(chǎng) 景 163.1.2 任 務(wù) 分 配 限 制 條 件 163.2 多 無(wú) 人 機(jī) 任 務(wù) 分 配 的 數(shù) 學(xué) 模 型 163.2.1 無(wú) 人 機(jī) 任 務(wù) 集 描 述 163.2.2 平 面 網(wǎng) 格 坐 標(biāo) 系 16第 四 章 動(dòng) 態(tài) 環(huán) 境 下 無(wú) 人 機(jī) 任 務(wù) 分 配 164.1 動(dòng) 態(tài) 任 務(wù) 重 分 配 164.1.1 動(dòng) 態(tài) 任 務(wù) 重 分 配 的 觸 發(fā) 條 件 164.1.2 任 務(wù) 動(dòng) 態(tài) 再 分 配 采 用 的 策 略 164.1.3 任 務(wù) 重 分 配 的 流 程 164.1.4 任 務(wù) 動(dòng) 態(tài) 再 分 配 需 要 考 慮 的 因 素 164.1.5 任 務(wù) 改 變 時(shí) 的 任 務(wù) 動(dòng) 態(tài) 再 分 配 算 法 164.1.6 無(wú) 人 機(jī) 狀 態(tài) 改 變 時(shí) 的 任 務(wù) 再 分 配 16結(jié) 論 .14參 考 文 獻(xiàn) .15致 謝 .16第 一 章 緒 論1.1 任 務(wù) 分 配 的 研 究 背 景無(wú) 人 機(jī) (Uninhabited Aerial Vehicle, UAV)是 指 由 遠(yuǎn) 程 遙 控 或 自 主 控 制 操 作 的無(wú)人 駕 駛 的 飛 機(jī) 。 采 用 無(wú) 人 駕 駛 的 方 式 使 飛 機(jī) 擺 脫 了 駕 駛 員 自 身 生 理 條 件 的 限 制 ，能 夠 完 成 一 般 飛 機(jī) 不 能 完 成 的 任 務(wù) 。 無(wú) 人 機(jī) 具 有 重 量 輕 、 維 護(hù) 成 本 低 、 機(jī) 動(dòng) 性 能高 等 明 顯 優(yōu) 勢(shì) ， 同 時(shí) 無(wú) 人 駕 駛 的 方 式 使 操 作 人 員 遠(yuǎn) 離 危 險(xiǎn) 的 任 務(wù) 環(huán) 境 ， 極 大 地 降低 了 操 作 人 員 的 危 險(xiǎn) 程 度 。UAV 協(xié) 同 任 務(wù) 規(guī) 劃 是 現(xiàn) 代 戰(zhàn) 爭(zhēng) 中 提 出 的 新 課 題 。 隨 著 無(wú) 人 機(jī) 的 出 現(xiàn) ， 利 用 無(wú)4人 機(jī) 執(zhí) 行 任 務(wù) 逐 步 成 為 了 現(xiàn) 實(shí) ， 目 前 UAV 協(xié) 同 任 務(wù) 規(guī) 劃 得 到 了 越 來(lái) 越 多 的 關(guān) 注 ，因 為 盡 管 單 無(wú) 人 機(jī) 可 以 無(wú) 需 合 作 完 成 某 個(gè) 環(huán) 境 的 搜 索 ， 但 是 一 個(gè) 更 有 效 的 搜 索 需要 合 作 來(lái) 減 少 重 復(fù) 覆 蓋 ， 通 常 多 無(wú) 人 機(jī) 任 務(wù) 規(guī) 劃 可 以 分 成 兩 大 部 分 :上 層 的 任 務(wù)分 配 (Task Assignment or Task Allocation)和 下 層 的 路 徑 規(guī) 劃 (Path Planning)，任 務(wù) 分配 考 慮 各 種 約 束 條 件 ， 以 總 體 任 務(wù) 有 效 達(dá) 成 為 目 標(biāo) ， 將 具 體 目 標(biāo) 和 行 動(dòng) 任 務(wù) 分 配給 各 機(jī) ， 而 各 機(jī) 根 據(jù) 分 配 的 任 務(wù) 再 進(jìn) 行 具 體 的 作 戰(zhàn) 路 徑 規(guī) 劃 。 路 徑 規(guī) 劃 的 功 能 是在 滿(mǎn) 足 如 最 大 線 性 速 度 、 最 大 轉(zhuǎn) 角 速 度 、 操 作 的 安 全 性 、 時(shí) 間 和 環(huán) 境 變 量 等 自 身或 外 部 限 制 的 前 提 下 在 一 系 列 位 置 之 間 設(shè) 計(jì) 或 生 成 路 徑 。 本 文 我 們 主 要 討 論 UAV任 務(wù) 分 配 問(wèn) 題 。1. 2 國(guó) 內(nèi) 外 無(wú) 人 機(jī) 應(yīng) 用 現(xiàn) 狀1. 2. 1.應(yīng) 用 在 軍 事 上UAV 任 務(wù) 規(guī) 劃 技 術(shù) 主 要 還 是 應(yīng) 用 在 軍 事 上 。 無(wú) 人 作 戰(zhàn) 飛 機(jī) ((Uninhabited CombatAerial Vehicle, UCAV)指 的 是 無(wú) 人 機(jī) 攜 帶 武 器 或 者 彈 藥 ， 可 對(duì) 地 面 目 標(biāo) 進(jìn) 行 攻 擊和 轟 炸 。 在 軍 事 發(fā) 達(dá) 國(guó) 家 ， 尤 其 美 國(guó) 、 英 國(guó) 以 及 法 國(guó) 對(duì) 無(wú) 人 作 戰(zhàn) 機(jī) 研 究 深 入 ， 美國(guó) 對(duì) 于 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 在 軍 事 上 的 研 究 最 為 深 入 ， 在 上 世 紀(jì) 70 年 代 就 開(kāi) 始 對(duì)無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 進(jìn) 行 描 述 并 進(jìn) 行 實(shí) 際 應(yīng) 用 。 在 越 南 戰(zhàn) 爭(zhēng) ， 海 灣 戰(zhàn) 爭(zhēng) 以 及 北 約 空襲 南 斯 拉 夫 等 過(guò) 往 戰(zhàn) 爭(zhēng) 中 ， 無(wú) 人 機(jī) 經(jīng) 常 用 于 執(zhí) 行 一 些 人 不 能 完 成 的 軍 事 任 務(wù) 。 在 這些 戰(zhàn) 爭(zhēng) 中 雖 然 無(wú) 人 機(jī) 不 是 主 要 執(zhí) 行 任 務(wù) 的 飛 機(jī) ， 但 它 卻 成 了 決 定 戰(zhàn) 爭(zhēng) 導(dǎo) 向 的 決 定因 素 之 一 。 由 于 無(wú) 人 機(jī) 的 無(wú) 人 駕 駛 特 點(diǎn) ， 可 以 被 派 往 危 險(xiǎn) 的 環(huán) 境 中 執(zhí) 行 一 些 人 不 能執(zhí) 行 的 任 務(wù) ， 因 而 成 為 重 要 的 軍 事 力 量 受 各 國(guó) 關(guān) 住 。 無(wú) 人 機(jī) 可 以 用 來(lái) 完 成 對(duì) 戰(zhàn) 場(chǎng) 實(shí)時(shí) 的 偵 察 和 監(jiān) 視 、 對(duì) 目 標(biāo) 位 置 的 確 定 、 任 務(wù) 目 標(biāo) 的 評(píng) 估 、 電 子 對(duì) 抗 等 。 無(wú) 人 機(jī) 最早 的 開(kāi) 發(fā) 是 在 第 一 次 世 界 大 戰(zhàn) 之 后 。 到 了 第 二 次 世 界 大 戰(zhàn) 后 ， 很 多 軍 事 實(shí) 力 較 強(qiáng) 的國(guó) 家 將 退 役 下 來(lái) 的 飛 機(jī) 進(jìn) 行 改 裝 ， 使 人 與 飛 機(jī) 脫 離 ， 這 樣 就 促 成 了 近 代 無(wú) 人 機(jī) 的發(fā) 展 。 隨 著 信 息 化 技 術(shù) 的 發(fā) 展 ， 無(wú) 人 機(jī) 在 執(zhí) 行 偵 察 任 務(wù) 的 過(guò) 程 中 的 作 用 越 來(lái) 越 明顯 。 例 如 ， 在 越 南 戰(zhàn) 爭(zhēng) 期 間 ， 美 國(guó) 就 大 量 使 用 無(wú) 人 機(jī) 對(duì) 價(jià) 值 較 高 的 軍 事 設(shè) 施 和 通 信設(shè) 施 進(jìn) 行 預(yù) 先 偵 察 。 無(wú) 人 機(jī) 不 僅 僅 應(yīng) 用 于 偵 察 ， 還 應(yīng) 用 在 具 體 的 作 戰(zhàn) 任 務(wù) 執(zhí) 行 中 。在 對(duì) 阿 富 汗 的 戰(zhàn) 爭(zhēng) 中 ， 美 國(guó) “捕 食 者 ”無(wú) 人 機(jī) 首 次 發(fā) 射 “海 爾 法 ”導(dǎo) 彈 擊 中 地 面目 標(biāo) ， 打 破 了 無(wú) 人 機(jī) 傳 統(tǒng) 的 作 戰(zhàn) 保 障 角 色 ， 使 之 成 為 一 種 作 戰(zhàn) 兵 器 1982 年 以 色 列航 空 工 業(yè) 公 司 首 創(chuàng) 的 無(wú) 人 機(jī) 能 進(jìn) 行 偵 察 、 信 息 收 集 、 跟 蹤 和 相 互 通 訊 等 。 1991 年 ，海 灣 戰(zhàn) 爭(zhēng) 中 ， 美 國(guó) 軍 方 己 經(jīng) 推 出 了 特 別 設(shè) 計(jì) 的 ， 具 有 雷 達(dá) 系 統(tǒng) 的 小 型 無(wú) 人 機(jī) 為 誘餌 ， 這 種 無(wú) 人 機(jī) 在 其 它 國(guó) 家 也 進(jìn) 行 了 一 些 研 究 。 無(wú) 人 機(jī) 在 海 灣 戰(zhàn) 爭(zhēng) 之 后 很 快 的 發(fā)展 起 來(lái) 并 在 很 多 任 務(wù) 中 應(yīng) 用 。 以 美 國(guó) 為 首 的 西 方 國(guó) 家 要 為 了 增 加 對(duì) 實(shí) 現(xiàn) 無(wú) 人 機(jī) 在戰(zhàn) 爭(zhēng) 的 作 用 ， 將 最 新 的 高 科 技 技 術(shù) 應(yīng) 用 到 無(wú) 人 機(jī) 的 研 究 和 開(kāi) 發(fā) 當(dāng) 中 去 ， 不 僅 增 加 無(wú)人 機(jī) 飛 行 時(shí) 間 ， 提 高 了 圖 像 ， 文 字 等 信 息 的 傳 輸 速 度 ， 還 考 慮 了 無(wú) 人 機(jī) 具 體 的 避 開(kāi)危 險(xiǎn) 區(qū) 域 能 力 ， 以 順 利 完 成 任 務(wù) 。和 美 國(guó) 等 西 方 國(guó) 家 相 比 ， 我 國(guó) 的 無(wú) 人 機(jī) 研 究 水 平 差 距 還 是 很 大 。 雖 然 國(guó) 內(nèi) 從80 年 代 末 開(kāi) 始 ， 對(duì) 路 徑 規(guī) 劃 問(wèn) 題 進(jìn) 行 過(guò) 許 多 研 究 ， 發(fā) 表 了 許 多 論 文 ， 但 大 多 數(shù) 的文 獻(xiàn) 僅 僅 是 對(duì) 單 無(wú) 人 機(jī) 所 進(jìn) 行 的 路 徑 規(guī) 劃 問(wèn) 題 的 研 究 ， 目 的 是 避 開(kāi) 無(wú) 人 機(jī) 在 飛 行5過(guò) 程 中 遇 到 的 危 險(xiǎn) 區(qū) 域 ， 很 少 有 關(guān) 于 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 解 答 的 研 究 成 果 。 當(dāng) 前我 們 國(guó) 家 無(wú) 人 機(jī) 反 的 研 究 還 處 在 起 步 階 段 。 由 于 我 國(guó) 的 無(wú) 人 機(jī) 功 能 簡(jiǎn) 單 ， 自 主 能力 較 差 ， 需 要 地 面 控 制 站 進(jìn) 行 任 務(wù) 分 配 的 規(guī) 劃 。 而 當(dāng) 前 的 無(wú) 人 機(jī) 發(fā) 展 趨 勢(shì) 是 無(wú) 人機(jī) 的 智 能 化 ， 將 無(wú) 人 機(jī) 看 成 一 個(gè) 個(gè) 智 能 體 ， 我 國(guó) 在 這 方 面 的 研 究 成 果 很 少 。 功 能上 也 只 能 進(jìn) 行 簡(jiǎn) 單 的 圖 像 ， 數(shù) 字 傳 輸 ， 任 務(wù) 分 配 、 路 徑 規(guī) 劃 的 能 力 很 差 。 尚 不 具備 執(zhí) 行 復(fù) 雜 戰(zhàn) 術(shù) 任 務(wù) 的 能 力 。 近 年 來(lái) 我 國(guó) 的 國(guó) 防 科 技 大 學(xué) 、 西 北 工 業(yè) 大 學(xué) 等 高 等院 校 和 科 研 單 位 在 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 上 也 進(jìn) 行 了 一 些 理 論 分 析 和 實(shí) 際 問(wèn) 題 的 研究 ， 可 以 說(shuō) 取 得 了 不 錯(cuò) 的 成 就 。 但 從 現(xiàn) 階 段 己 經(jīng) 得 到 的 理 論 和 實(shí) 際 成 果 來(lái) 看 ， 目前 我 國(guó) 對(duì) 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 的 研 究 還 處 有 很 多 不 足 和 局 限 。 例 如 無(wú) 人 機(jī) 的 自 主性 較 差 ， 無(wú) 人 機(jī) 的 決 策 大 都 是 由 地 面 控 制 站 決 定 的 。 對(duì) 于 無(wú) 人 機(jī) 所 處 的 動(dòng) 態(tài) 環(huán) 境考 慮 不 足 ， 無(wú) 人 機(jī) 的 尺 寸 、 時(shí) 間 窗 函 數(shù) 等 考 慮 較 少 。2. 2 應(yīng) 用 在 自 然 災(zāi) 害 的 防 護(hù) 上和 平 和 發(fā) 展 當(dāng) 今 世 界 的 兩 大 主 題 ， 所 以 無(wú) 人 機(jī) 的 應(yīng) 用 也 由 軍 用 慢 慢 轉(zhuǎn) 向 民 用 。其 中 最 主 要 的 民 用 用 途 是 在 自 然 災(zāi) 害 的 防 護(hù) 上 。 2001 年 以 來(lái) ， 世 界 各 國(guó) 都 在 大 力發(fā) 展 各 種 用 途 的 無(wú) 人 飛 行 器 。 目 前 世 界 上 32 個(gè) 國(guó) 家 己 研 制 出 了 多 種 無(wú) 人 機(jī) 。 美 國(guó) 、以 色 列 、 俄 羅 斯 、 北 約 等 國(guó) 家 非 常 重 視 多 用 途 無(wú) 人 機(jī) 的 研 制 、 生 產(chǎn) 和 應(yīng) 用 。 森 林火 災(zāi) 的 現(xiàn) 場(chǎng) 溫 度 高 ， 對(duì) 飛 機(jī) 的 抗 熱 性 能 高 。 現(xiàn) 場(chǎng) 的 煙 塵 大 ， 能 見(jiàn) 度 不 高 ， 盡 管 有人 飛 機(jī) 能 飛 至 火 場(chǎng) 上 課 ， 飛 機(jī) 中 的 人 也 不 能 清 除 地 了 解 火 場(chǎng) 當(dāng) 前 的 具 體 情 況 。 這時(shí) 無(wú) 人 機(jī) 的 優(yōu) 勢(shì) 就 體 現(xiàn) 出 來(lái) ， 通 過(guò) 在 無(wú) 人 機(jī) 上 配 置 攝 像 機(jī) 和 數(shù) 字 圖 像 傳 輸 設(shè) 備 ，可 輕 易 完 成 對(duì) 火 場(chǎng) 的 偵 察 ， 滅 火 和 滅 火 評(píng) 估 。 美 國(guó) 航 天 局 最 新 研 制 的 無(wú) 人 滅 火 機(jī)“工 khana“。 這 款 無(wú) 人 滅 火 機(jī) 由 “捕 食 者 B“ (Predator B)改 進(jìn) 而 來(lái) 。 “捕 食 者B”原 本 是 美 國(guó) 空 軍 用 于 戰(zhàn) 時(shí) 監(jiān) 視 和 偵 察 的 ， 現(xiàn) 在 它 的 改 進(jìn) 版 “工 khana”被 用 作 另一 個(gè) 領(lǐng) 域 ， 那 就 是 森 林 滅 火 。 在 火 場(chǎng) 中 ， 由 于 火 勢(shì) 的 動(dòng) 態(tài) 性 和 不 確 定 性 以 及 協(xié) 同控 制 的 復(fù) 雜 性 ， 使 得 任 務(wù) 開(kāi) 始 后 出 現(xiàn) 許 多 無(wú) 法 預(yù) 料 的 情 況 ， 必 須 根 據(jù) 火 場(chǎng) 火 勢(shì) 和編 隊(duì) 狀 態(tài) 的 變 化 快 速 調(diào) 整 UAV 編 隊(duì) 的 任 務(wù) 計(jì) 劃 ， 通 過(guò) 動(dòng) 態(tài) 重 調(diào) 度 實(shí) 現(xiàn) 任 務(wù) 的 重 分配 。我 國(guó) 也 有 無(wú) 人 機(jī) 應(yīng) 用 在 災(zāi) 害 防 護(hù) 上 的 實(shí) 例 Lll。 該 實(shí) 例 描 述 了 無(wú) 人 機(jī) 在 國(guó) 內(nèi) 地震中 的 應(yīng) 用 。 重 大 自 然 災(zāi) 害 如 地 震 、 水 災(zāi) 、 冰 雪 等 具 有 突 發(fā) 性 強(qiáng) 、 災(zāi) 害 范 圍 廣 、 破壞 性 大 特 點(diǎn) ， 往 往 會(huì) 造 成 重 災(zāi) 區(qū) 信 息 通 訊 中 斷 和 道 路 交 通 破 壞 ， 災(zāi) 情 信 息 不 暢 將導(dǎo) 致 搶 險(xiǎn) 救 災(zāi) 盲 目 部 署 ， 繼 而 造 成 更 大 的 損 失 和 次 生 災(zāi) 害 ’‘。 2008 年 漢 川 8.。級(jí) 地 震 ， 極 重 災(zāi) 區(qū) 北 川 縣 城 出 現(xiàn) 大 范 圍 建 筑 物 倒 塌 和 重 大 人 員 傷 亡 ， 通 訊 和 交 通系 統(tǒng) 遭 到 毀 滅 性 破 壞 ， 傳 出 特 大 災(zāi) 情 己 是 震 后 的 第 2 天 ， 在 親 歷 和 目 睹 漢 川 地 震搶 險(xiǎn) 救 災(zāi) 過(guò) 程 之 后 ， 全 社 會(huì) 己 經(jīng) 取 得 共 識(shí) ， 通 過(guò) 各 種 手 段 有 效 獲 取 災(zāi) 情 是 開(kāi) 展 重大 自 然 災(zāi) 害 搶 險(xiǎn) 救 災(zāi) 首 要 問(wèn) 題 。 漢 川 地 震 之 后 ， 在 我 國(guó) 有 一 些 單 位 應(yīng) 用 無(wú) 人 機(jī) 獲取 遙 感 圖 像 ， 進(jìn) 行 震 害 分 析 ， 做 出 了 探 索 性 工 作 。 無(wú) 人 機(jī) 組 定 位 于 獲 取 高 分 辨 率圖 像 ， 進(jìn) 行 災(zāi) 害 識(shí) 別 并 直 接 應(yīng) 用 于 搶 險(xiǎn) 救 災(zāi) 。 無(wú) 人 機(jī) 組 在 北 川 縣 曲 山 鎮(zhèn) 等 地 進(jìn) 行了 地 震 災(zāi) 區(qū) 實(shí) 驗(yàn) ， 并 在 2010 年 玉 樹(shù) 地 震 搶 險(xiǎn) 救 災(zāi) 工 作 中 成 功 實(shí) 現(xiàn) 了 高 原 災(zāi) 區(qū) 首 次航 空 攝 影 ， 獲 取 的 高 清 影 像 為 劃 分 災(zāi) 區(qū) 范 圍 提 供 了 重 要 的 依 據(jù) 。 本 文 我 們 著 重 討論 無(wú) 人 機(jī) 在 森 林 還 火 災(zāi) 中 的 應(yīng) 用 。61. 3 論 文 的 主 要 內(nèi) 容無(wú) 人 機(jī) 如 何 在 復(fù) 雜 的 環(huán) 境 中 順 利 地 完 成 所 需 執(zhí) 行 的 任 務(wù) ， 并 且 能 夠 使 得 任 務(wù)執(zhí) 行 的 效 率 最 高 ， 收 獲 的 利 益 最 大 ， 付 出 的 代 價(jià) 最 小 ， 是 多 無(wú) 人 機(jī) 任 務(wù) 分 配 所 要考 慮 的 問(wèn) 題 。 本 文 的 主 要 工 作 是 通 過(guò) 對(duì) 各 種 任 務(wù) 分 配 算 法 的 研 究 ， 引 出 了 一 種 有人 參 與 的 多 無(wú) 人 機(jī) 任 務(wù) 分 配 算 法 并 進(jìn) 行 了 理 論 研 究 和 仿 真 分 析 。 主 要 步 驟 是 :首 先建 立 了 一 個(gè) 任 務(wù) 分 配 在 森 林 火 災(zāi) 防 護(hù) 的 應(yīng) 用 場(chǎng) 景 ， 設(shè) 置 了 關(guān) 于 實(shí) 際 問(wèn) 題 的 限 制 條件 ， 然 后 建 立 了 一 個(gè) 基 于 六 元 組 的 任 務(wù) 描 述 ， 使 用 了 平 面 網(wǎng) 格 坐 標(biāo) 系 對(duì) 任 務(wù) 分 配問(wèn) 題 進(jìn) 行 建 模 ， 在 以 上 的 基 礎(chǔ) 了 最 后 利 用 了 一 個(gè) 無(wú) 人 機(jī) 森 林 滅 火 的 實(shí) 例 ， 通 過(guò)MATLAB 仿 真 結(jié) 合 算 法 說(shuō) 明 了 該 算 法 的 可 行 性 和 實(shí) 用 性 。 因 為 無(wú) 人 機(jī) 任 務(wù) 分 配 所處 環(huán) 境 是 動(dòng) 態(tài) 的 ， 所 以 對(duì) 動(dòng) 態(tài) 環(huán) 境 下 無(wú) 人 機(jī) 任 務(wù) 重 分 配 問(wèn) 題 也 進(jìn) 行 了 一 些 算 法 研究 和 實(shí) 例 分 析 。1. 4 論 文 組 織 結(jié) 構(gòu)本 文 主 要 介 紹 多 無(wú) 人 機(jī) 的 任 務(wù) 分 配 算 法 ， 在 介 紹 了 傳 統(tǒng) 的 任 務(wù) 分 配 的 算 法 的基 礎(chǔ) 上 ， 分 析 了 它 們 的 優(yōu) 缺 點(diǎn) ， 引 出 了 一 種 有 人 參 與 的 多 無(wú) 人 機(jī) 任 務(wù) 分 配 算 法 ，為 無(wú) 人 機(jī) 的 任 務(wù) 分 配 算 法 提 供 了 新 的 思 想 。 并 結(jié) 合 了 一 個(gè) 無(wú) 人 機(jī) 在 森 林 滅 火 中 的應(yīng) 用 實(shí) 例 ， 利 用 MATLLAB 進(jìn) 行 仿 真 研 究 。第 一 章 :緒 論 。 介 紹 了 論 文 選 題 的 背 景 ， 國(guó) 內(nèi) 外 無(wú) 人 機(jī) 任 務(wù) 分 配 的 應(yīng) 用 現(xiàn) 狀 。簡(jiǎn) 述 了 論 文 的 主 要 內(nèi) 容 以 及 論 文 的 組 織 結(jié) 構(gòu) 。第 二 章 :無(wú) 人 機(jī) 任 務(wù) 分 配 的 現(xiàn) 狀 及 發(fā) 展 趨 勢(shì) 。 首 先 給 出 了 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn)題 的 定 義 并 對(duì) 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 進(jìn) 行 了 描 述 。 其 次 ， 說(shuō) 明 了 解 決 任 務(wù) 分 配 問(wèn) 題的 基 本 步 驟 ， 包 括 任 務(wù) 分 配 數(shù) 學(xué) 模 型 的 建 立 和 具 體 算 法 的 設(shè) 計(jì) 。 然 后 介 紹 了 任 務(wù)分 配 的 體 系 結(jié) 構(gòu) 和 當(dāng) 前 幾 種 任 務(wù) 分 配 模 型 ， 接 著 介 紹 了 幾 種 靜 態(tài) 任 務(wù) 分 配 算 法 和動(dòng) 態(tài) 任 務(wù) 分 配 算 法 并 分 析 了 它 們 的 優(yōu) 缺 點(diǎn) 。 最 后 指 出 了 當(dāng) 前 無(wú) 人 機(jī) 任 務(wù) 分 配 方 法研 究 存 在 的 一 些 問(wèn) 題 。第 三 章 :討 論 了 靜 態(tài) 環(huán) 境 下 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 。 首 先 建 立 了 一 個(gè) 無(wú) 人 機(jī) 森林 滅 火 的 應(yīng) 用 場(chǎng) 景 ， 設(shè) 置 了 一 些 限 制 條 件 。 在 此 場(chǎng) 景 下 設(shè) 計(jì) 了 一 個(gè) 六 元 組 的 任 務(wù)描 述 并 使 用 平 面 網(wǎng) 格 坐 標(biāo) 系 完 成 了 對(duì) 任 務(wù) 分 配 問(wèn) 題 數(shù) 學(xué) 模 型 的 建 立 。 其 次 ， 設(shè) 計(jì)了 一 種 有 人 參 與 的 多 無(wú) 人 機(jī) 任 務(wù) 靜 態(tài) 分 配 算 法 。 最 后 應(yīng) 用 一 個(gè) 無(wú) 人 機(jī) 森 林 滅 火 的實(shí) 例 ， 通 過(guò) MATLAB 仿 真 分 析 ， 驗(yàn) 證 了 該 算 法 的 可 行 性 和 實(shí) 用 性 。第 四 章 :討 論 了 動(dòng) 態(tài) 環(huán) 境 下 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 。 介 紹 了 動(dòng) 態(tài) 任 務(wù) 再 分 配 的觸 發(fā) 條 件 ， 動(dòng) 態(tài) 任 務(wù) 重 分 配 采 用 的 策 略 以 及 任 務(wù) 動(dòng) 態(tài) 再 分 配 需 要 考 慮 的 因 素 。 分別 考 慮 任 務(wù) 改 變 、 無(wú) 人 機(jī) 狀 態(tài) 改 變 這 兩 種 觸 發(fā) 條 件 ， 設(shè) 計(jì) 了 兩 種 新 的 動(dòng) 態(tài) 任 務(wù) 再分 配 算 法 。 結(jié) 合 第 三 章 的 無(wú) 人 機(jī) 森 林 滅 火 的 實(shí) 例 ， 通 過(guò) MATLAB 仿 真 分 析 ， 驗(yàn) 證 了這 兩 個(gè) 算 法 的 可 行 性 和 實(shí) 用 性 。第 五 章 :總 結(jié) 與 展 望 。 總 結(jié) 了 本 文 的 主 要 研 究 工 作 ， 指 出 了 論 文 中 的 不 足 之處 ， 并 對(duì) 今 后 的 工 作 提 出 若 干 自 己 的 想 法 。第 二 章 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 研 究 現(xiàn) 狀 及 發(fā) 展 趨 勢(shì)2. 1 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 的 定 義 及 解 決 步 驟2. 1. 1 UAV 任 務(wù) 分 配 問(wèn) 題 的 定 義UAV 任 務(wù) 分 配 問(wèn) 題 可 以 定 義 為 :在 己 經(jīng) 完 成 UAV 編 隊(duì) 分 組 的 基 礎(chǔ) 上 ， 基 于 一 定的 環(huán) 境 和 任 務(wù) 要 求 ， 為 編 隊(duì) 中 的 UAV 分 配 一 個(gè) 或 多 個(gè) 有 序 任 務(wù) ， 以 便 在 完 成 最 大可 能 任 務(wù) 的 同 時(shí) ， 使 得 UAV 編 隊(duì) 的 整 體 效 率 最 高 。7我 們 結(jié) 合 圖 2. 1 這 個(gè) 簡(jiǎn) 單 的 例 子 來(lái) 直 觀 地 了 解 任 務(wù) 分 配 問(wèn) 題 的 具 體 含 義 :首先 設(shè) 置 了 任 務(wù) 集 和 無(wú) 人 機(jī) 集 :其 中 包 含 了 四 個(gè) 待 執(zhí) 行 任 務(wù) ， 無(wú) 人 機(jī) 編 隊(duì) 由 兩 架 無(wú)人 機(jī) 組 成 。 然 后 設(shè) 計(jì) 具 體 的 路 徑 和 任 務(wù) 執(zhí) 行 順 序 來(lái) 完 成 所 設(shè) 定 的 四 個(gè) 任 務(wù) 。 圖 中每 個(gè) 帶 箭 頭 直 線 上 的 數(shù) 字 表 示 無(wú) 人 機(jī) 在 該 段 航 路 上 所 花 費(fèi) 的 時(shí) 間 ， 四 個(gè) 任 務(wù) 用 四個(gè) 圓 圈 來(lái) 表 示 。 圓 圈 中 上 半 部 分 的 數(shù) 字 表 示 的 無(wú) 人 機(jī) 任 務(wù) 集 中 任 務(wù) 的 序 號(hào) ， 下 半部 分 的 數(shù) 字 表 示 完 成 這 個(gè) 任 務(wù) 需 要 的 具 體 時(shí) 間 。 最 后 虛 實(shí) 線 表 示 的 是 任 務(wù) 分 配 的具 體 的 方 案 。 無(wú) 人 機(jī) 分 別 沿 著 制 定 的 虛 線 完 成 四 個(gè) 所 設(shè) 定 的 任 務(wù) ， 通 過(guò) 這 種 方 法 ，花 費(fèi) 時(shí) 間 要 明 顯 小 于 單 架 無(wú) 人 機(jī) 。2. 1. 2 UAV 任 務(wù) 分 配 問(wèn) 題 的 描 述給 定 一 個(gè) UAV 編 隊(duì) U， 它 包 含 數(shù) 目 為 N 二 的 無(wú) 人 機(jī) ， v 一 {vl.v2. ' . . vNU。 為簡(jiǎn) 化問(wèn) 題 ， 假 設(shè) UAV 編 隊(duì) 在 一 個(gè) 二 維 空 間 執(zhí) 行 任 務(wù) ， 在 任 意 時(shí) 刻 t， 無(wú) 人 機(jī) U， 的 位 置為(xU }t}'yU }t})。 每 個(gè) UAV 都 假 設(shè) 為 質(zhì) 點(diǎn) 。 同 時(shí) ， 在 任 務(wù) 區(qū) 域 內(nèi) 包 含 有 限 數(shù) 目 的 待執(zhí) 行 任 務(wù) ， 組 成 一 個(gè) 任 務(wù) 集 T 一 仁 .Tz. ' . . TNT,} } N:為 任 務(wù) 的 數(shù) 量 ， 包 含唯 一 的 任 務(wù)ID， 對(duì) 應(yīng) 水 平 位 置 為 (對(duì) 了 )但 不 同 的 任 務(wù) 允 許 有 相 同 的 水 平 位 置 「 23]。 在 任 務(wù) 分配前 ， 以 上 的 信 息 都 是 己 知 的 。 UAV 任 務(wù) 分 配 的 結(jié) 果 是 為 編 隊(duì) 中 的 任 一 無(wú) 人 機(jī) U， 分配 一 條 任 務(wù) 執(zhí) 行 路 線 P， 有:·}}x} }}},y} }}}}, }x`M ,y`M)， …， \xT; }yT;)}(2 一 ‘)其 中 ， (x0 }O},y0 }0})表 示 無(wú) 人 機(jī) U， 的 出 發(fā) 位 置 ， 也 就 是 說(shuō) ， 對(duì) 應(yīng) 無(wú) 人 機(jī) U;需 要 市 。 定 一 個(gè) 有 序 任 務(wù) 集 。 ;一 {T1 ,T2 , .,界 。 }。任 務(wù) 分 配 的 一 般 原 則 如 下 :(1)優(yōu) 先 分 配 價(jià) 值 高 的 一 般 原 則 ;(2)將 目 標(biāo) 分 配 給 對(duì) 其 最 有 利 的 UAV ;(3)在 盡 可 能 短 的 時(shí) 間 內(nèi) 盡 可 能 多 地 訪 問(wèn) 目 標(biāo) ， 并 保 證 UAV 編 隊(duì) 飛 行 總 路 線最 短 ;(4)參 與 任 務(wù) 的 各 UAV 的 任 務(wù) 負(fù) 載 盡 可 能 均 衡 。2. 1. 3 解 決 UAV 任 務(wù) 分 配 問(wèn) 題 的 步 驟無(wú) 人 機(jī) 任 務(wù) 分 配 方 法 的 求 解 主 要 分 為 兩 方 面 :任 務(wù) 分 配 模 型 的 建 立 以 及 具 體的 任 務(wù) 分 配 算 法 的 設(shè) 計(jì) :8(1) UAV 任 務(wù) 分 配 的 數(shù) 學(xué) 模 型 的 建 立要 對(duì) 無(wú) 人 機(jī) 進(jìn) 行 數(shù) 學(xué) 建 模 ， 首 先 要 對(duì) 無(wú) 人 機(jī) 所 處 的 空 間 環(huán) 境 進(jìn) 行 描 述 和 表 達(dá) 。通 常 我 們 以 一 個(gè) 二 維 或 者 三 維 的 變 量 來(lái) 定 義 一 個(gè) 無(wú) 人 機(jī) 和 目 標(biāo) 點(diǎn) 的 位 置 ， 為 簡(jiǎn) 便 ，一 般 采 用 二 維 變 量 。 得 到 了 無(wú) 人 機(jī) 和 目 標(biāo) 點(diǎn) 的 位 置 ， 就 能 得 到 任 一 無(wú) 人 機(jī) 的 任 務(wù)執(zhí) 行 路 線 。 然 后 我 們 設(shè) 計(jì) 一 個(gè) 二 值 決 策 變 量 ， 如 果 無(wú) 人 機(jī) 完 成 某 個(gè) 任 務(wù) ， 二 值 變量 就 為 1， 如 果 不 完 成 那 個(gè) 任 務(wù) ， 二 值 變 量 就 為 0。 然 后 要 設(shè) 定 無(wú) 人 機(jī) 任 務(wù) 分 配 的約 束 條 件 ， 如 無(wú) 人 機(jī) 最 大 航 程 、 任 務(wù) 時(shí) 間 窗 約 束 、 任 務(wù) 執(zhí) 行 的 先 后 順 序 、 無(wú) 人 機(jī)的 載 荷 等 。(2) UAV 任 務(wù) 分 配 算 法 的 設(shè) 計(jì)完 成 了 對(duì) 無(wú) 人 機(jī) 任 務(wù) 分 配 的 數(shù) 學(xué) 建 模 ， 我 們 就 要 來(lái) 設(shè) 計(jì) 具 體 的 算 法 。 設(shè) 計(jì) 算法 我 們 首 先 要 根 據(jù) 以 往 的 算 法 和 基 本 概 念 提 出 算 法 得 出 的 理 論 依 據(jù) ， 然 后 決 定 算法 的 搜 索 策 略 ， 以 較 快 較 好 為 準(zhǔn) 則 ， 確 定 算 法 的 搜 索 策 略 。 因 為 無(wú) 人 機(jī) 分 配 問(wèn) 題要 用 計(jì) 算 機(jī) 進(jìn) 行 運(yùn) 算 仿 真 ， 必 須 對(duì) 算 法 進(jìn) 行 編 碼 ， 所 以 得 設(shè) 計(jì) 算 法 的 編 碼 和 解 碼方 式 。 還 應(yīng) 設(shè) 計(jì) 一 個(gè) 評(píng) 價(jià) 函 數(shù) ， 來(lái) 評(píng) 價(jià) 任 務(wù) 分 配 方 案 的 好 壞 ， 我 們 稱(chēng) 其 為 適 應(yīng) 度函 數(shù) 。 適 應(yīng) 度 函 數(shù) 要 考 慮 的 實(shí) 際 因 素 主 要 包 括 :任 務(wù) 完 成 的 時(shí) 間 最 短 ， 任 務(wù) 分 配方 案 得 到 的 收 益 最 高 以 及 無(wú) 人 機(jī) 消 耗 能 力 最 小 。 最 后 ， 我 們 還 要 對(duì) 算 法 進(jìn) 行 性 能分 析 ， 包 括 算 法 能 否 得 到 最 優(yōu) 任 務(wù) 分 配 方 案 ， 算 法 的 效 率 以 及 算 法 的 實(shí) 時(shí) 性 。2. 2 無(wú) 人 機(jī) 任 務(wù) 分 配 控 制 方 法由 于 無(wú) 人 機(jī) 執(zhí) 行 任 務(wù) 環(huán) 境 是 動(dòng) 態(tài) 的 ， 不 是 固 定 不 變 的 ， 所 以 無(wú) 人 機(jī) 的 任 務(wù) 分配 控 制 方 法 也 應(yīng) 該 根 據(jù) 不 同 的 任 務(wù) 環(huán) 境 而 區(qū) 別 對(duì) 待 。 無(wú) 人 機(jī) 任 務(wù) 分 配 控 制 方 法 選取 對(duì) 無(wú) 人 機(jī) 執(zhí) 行 任 務(wù) 的 效 率 和 質(zhì) 量 有 很 大 關(guān) 系 。 任 務(wù) 分 配 控 制 方 法 的 選 取 應(yīng) 該 考慮 以 下 幾 個(gè) 因 素 :任 務(wù) 完 成 的 快 速 性 ， 任 務(wù) 的 實(shí) 時(shí) 性 ， 任 務(wù) 分 配 的 計(jì) 算 時(shí) 間 和 計(jì)算 復(fù) 雜 度 ， 抗 干 擾 能 力 等 。 無(wú) 人 機(jī) 任 務(wù) 分 配 控 制 方 法 主 要 可 以 分 為 集 中 式 控 制[28」 (Centralized Control)以 及 分 布 式 控 制 (Distributed Control)這 兩 種 。2. 2. 1 集 中 式 控 制在 集 中 式 控 制 方 法 中 ， 由 地 面 控 制 站 中 的 操 作 人 員 制 定 任 務(wù) 分 配 方 案 和 無(wú) 人 機(jī)具 體 的 飛 行 航 路 ， 無(wú) 人 機(jī) 本 身 不 具 備 決 策 能 力 ， 完 全 按 照 地 面 控 制 站 發(fā) 出 的 任 務(wù)指 令 和 航 路 執(zhí) 行 任 務(wù) 。 圖 2. 2 表 示 了 集 中 式 體 系 結(jié) 構(gòu) 圖 [28]:9在 這 種 控 制 方 式 下 ， 各 無(wú) 人 機(jī) 之 間 的 協(xié) 同 控 制 存 在 以 下 問(wèn) 題 :(1)實(shí) 時(shí) 性 差因 為 無(wú) 人 機(jī) 本 身 不 具 備 決 策 能 力 ， 所 以 地 面 控 制 站 中 的 操 作 人 員 要 根 據(jù) 無(wú) 人機(jī) 編 隊(duì) 通 過(guò) 數(shù) 據(jù) 傳 輸 返 回 的 無(wú) 人 機(jī) 狀 態(tài) 信 息 ， 任 務(wù) 狀 態(tài) 信 息 以 所 處 的 環(huán) 境 信 息 等 ，對(duì) 任 務(wù) 分 配 問(wèn) 題 進(jìn) 行 具 體 的 決 策 。 無(wú) 人 機(jī) 編 隊(duì) 與 地 面 控 制 站 保 持 著 聯(lián) 系 ， 當(dāng) 返 回的 數(shù) 據(jù) 量 很 大 時(shí) ， 有 可 能 地 面 控 制 站 收 到 的 信 息 是 不 全 的 或 者 是 錯(cuò) 誤 的 ， 導(dǎo) 致 決策 錯(cuò) 誤 。 地 面 控 制 綜 合 這 些 信 息 速 度 較 慢 ， 導(dǎo) 致 決 策 較 慢 ， 實(shí) 時(shí) 性 差 。(2)計(jì) 算 時(shí) 間 長(zhǎng) ， 算 法 復(fù) 雜 度 高對(duì) 于 集 中 式 控 制 方 法 ， 地 面 控 制 站 對(duì) 所 有 的 無(wú) 人 機(jī) 傳 來(lái) 的 數(shù) 據(jù) 信 息 進(jìn) 行 總 結(jié)和 分 析 ， 信 息 都 集 中 在 任 務(wù) 控 制 站 中 ， 解 決 問(wèn) 題 的 具 體 計(jì) 算 過(guò) 程 復(fù) 雜 ， 計(jì) 算 信 息多 ， 導(dǎo) 致 完 成 任 務(wù) 分 配 的 計(jì) 算 時(shí) 間 很 長(zhǎng) 。 對(duì) 于 多 類(lèi) 型 任 務(wù) 的 無(wú) 人 機(jī) 編 隊(duì) ， 例 如 無(wú)人 機(jī) 編 隊(duì) 中 無(wú) 人 機(jī) 能 夠 執(zhí) 行 任 務(wù) 種 類(lèi) 的 不 同 ， 無(wú) 人 機(jī) 執(zhí) 行 任 務(wù) 能 力 不 同 ， 此 時(shí) 更凸 顯 了 這 個(gè) 問(wèn) 題 的 嚴(yán) 重 。(3)抗 干 擾 能 力 較 差由 于 地 面 控 制 站 往 往 只 有 一 個(gè) ， 如 果 在 具 體 任 務(wù) 執(zhí) 行 過(guò) 程 中 ， 地 面 控 制 因 為某 些 特 定 因 素 遭 到 毀 壞 甚 至 癱 瘓 ， 將 造 成 的 損 失 是 巨 大 的 。 同 時(shí) 無(wú) 人 機(jī) 編 隊(duì) 中 的無(wú) 人 機(jī) 失 效 或 者 發(fā) 現(xiàn) 新 的 任 務(wù) 目 標(biāo) ， 在 原 有 基 礎(chǔ) 上 的 再 分 配 也 是 很 相 當(dāng) 復(fù) 雜 的 。2.2.2 分 布 式 控 制區(qū) 別 于 集 中 式 控 制 方 法 ， 分 布 式 控 制 方 法 中 無(wú) 人 機(jī) 編 隊(duì) 中 或 者 無(wú) 人 機(jī) 編 隊(duì) 之間 的 無(wú) 人 機(jī) 是 具 有 獨(dú) 自 決 策 能 力 的 智 能 體 ， 它 們 具 有 很 強(qiáng) 的 協(xié) 同 能 力 和 自 治 性 。無(wú) 人 機(jī) 之 間 以 數(shù) 據(jù) 鏈 技 術(shù) 為 支 撐 ， 對(duì) 無(wú) 人 機(jī) 所 處 環(huán) 境 ， 任 務(wù) 目 標(biāo) 集 信 息 ， 無(wú) 人 機(jī)狀 態(tài) 信 息 進(jìn) 行 交 互 ， 綜 合 考 慮 各 種 因 素 ， 提 出 具 體 的 解 決 任 務(wù) 分 配 問(wèn) 題 的 方 案 和具 體 步 驟 。 較 之 于 集 中 式 控 制 方 法 ， 無(wú) 人 機(jī) 個(gè) 體 在 分 布 式 控 制 方 法 下 具 有 較 強(qiáng) 的實(shí) 時(shí) 性 ， 抗 干 擾 能 力 ， 計(jì) 算 量 小 ， 計(jì) 算 復(fù) 雜 度 小 等 優(yōu) 點(diǎn) 。 當(dāng) 前 ， 分 布 式 控 制 方 法主 要 可 以 分 為 兩 種 :完 全 分 布 式 控 制 方 法 和 部 分 分 布 式 控 制 方 法 。(1)完 全 分 布 式 控 制完 全 分 布 式 控 制 方 法 是 一 種 依 靠 無(wú) 人 機(jī) 的 自 主 性 和 相 互 協(xié) 作 的 一 種 方 法 ， 由于 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 的 復(fù) 雜 性 ， 該 方 法 相 當(dāng) 于 將 復(fù) 雜 的 問(wèn) 題 分 解 成 為 一 個(gè) 個(gè) 相對(duì) 簡(jiǎn) 單 的 小 問(wèn) 題 ， 對(duì) 每 架 無(wú) 人 機(jī) 進(jìn) 行 任 務(wù) 分 配 ， 接 著 就 是 將 各 個(gè) 無(wú) 人 機(jī) 的 信 息 進(jìn)行 交 互 ， 對(duì) 任 務(wù) 進(jìn) 行 整 體 求 解 。 如 圖 2. 3 所 示 ， 完 全 分 布 式 控 制 方 法 中 我 們 把 無(wú)人 機(jī) 看 成 具 有 決 策 能 力 的 智 能 體 ， 這 樣 無(wú) 人 機(jī) 任 務(wù) 分 配 問(wèn) 題 就 轉(zhuǎn) 化 成 為 各 個(gè) 智 能體 之 間 任 務(wù) 的 分 配 和 決 策 。 在 這 種 結(jié) 構(gòu) 中 ， 無(wú) 人 機(jī) 相 對(duì) 于 集 中 式 控 制 有 很 強(qiáng) 的 自主 性 ， 能 夠 對(duì) 任 務(wù) 集 信 息 和 自 身 的 信 息 進(jìn) 行 采 集 和 分 析 ， 并 進(jìn) 行 決 策 ， 在 特 定 的情 況 下 通 過(guò) 數(shù) 據(jù) 鏈 與 其 它 無(wú) 人 機(jī) 進(jìn) 行 數(shù) 據(jù) 交 互 ， 協(xié) 作 完 成 所 需 執(zhí) 行 的 任 務(wù) 。10圖 2.3 完 全 分 布 式 控 制 結(jié) 構(gòu) 圖這 種 控 制 方 法 中 ， 無(wú) 人 機(jī) 編 隊(duì) 內(nèi) 各 個(gè) 無(wú) 人 機(jī) 對(duì) 所 得 到 的 信 息 進(jìn) 行 相 互 的 共 享 ，得 到 所 有 的 關(guān) 于 任 務(wù) 執(zhí) 行 的 信 息 ， 最 后 整 理 分 析 所 得 到 的 信 息 對(duì) 無(wú) 人 機(jī) 編 隊(duì) 中 的每 一 架 任 務(wù) 分 配 任 務(wù) 集 。 由 于 無(wú) 人 機(jī) 編 隊(duì) 中 有 多 架 無(wú) 人 機(jī) ， 在 執(zhí) 行 任 務(wù) 中 可 能 發(fā)生 交 叉 沖 突 ， 即 碰 撞 沖 突 ， 所 以 需 要 對(duì) 它 們 進(jìn) 行 考 慮 并 消 除 。 同 時(shí) 在 這 種 控 制 方法 中 ， 無(wú) 人 機(jī) 之 間 是 通 過(guò) 數(shù) 據(jù) 鏈 技 術(shù) 進(jìn) 行 任 務(wù) 集 數(shù) 據(jù) 的 傳 輸 和 共 享 ， 為 的 是 更 好的 具 有 任 務(wù) 決 策 的 實(shí) 時(shí) 性 ， 所 以 數(shù) 據(jù) 量 是 相 當(dāng) 大 的 ， 將 隨 著 編 隊(duì) 內(nèi) 無(wú) 人 機(jī) 的 數(shù) 量呈 指 數(shù) 增 長(zhǎng) 。 所 以 應(yīng) 用 這 種 控 制 方 法 ， 編 隊(duì) 內(nèi) 無(wú) 人 機(jī) 的 個(gè) 數(shù) 受 到 了 很 大 的 限 制 。(2)部 分 分 布 式 控 制部 分 分 布 式 控 制 方 法 吸 取 了 無(wú) 人 機(jī) 任 務(wù) 分 配 控 制 方 法 中 集 中 式 控 制 和 完 全 分布 式 控 制 方 法 各 自 的 優(yōu) 勢(shì) ， 對(duì) 于 解 決 多 類(lèi) 型 無(wú) 人 機(jī) 編 隊(duì) 任 務(wù) 分 配 問(wèn) 題 更 為 合 理 。經(jīng) 過(guò) 對(duì) 集 中 式 控 制 方 法 和 分 布 式 控 制 方 法 的 比 較 ， 我 們 得 出 分 布 是 控 制 方 法 是 一種 實(shí) 時(shí) 性 較 強(qiáng) 的 方 法 ， 能 夠 快 速 的 對(duì) 任 務(wù) 信 息 進(jìn) 行 采 集 和 分 析 ， 得 到 解 決 任 務(wù) 分配 問(wèn) 題 的 具 體 方 案 ， 獲 得 的 方 案 往 往 是 局 部 最 優(yōu) 的 ， 但 不 能 得 到 全 局 最 優(yōu) 方 案 。而 集 中 式 控 制 方 法 恰 恰 相 反 ， 由 于 所 有 信 息 都 要 返 回 地 面 控 制 站 進(jìn) 行 匯 總 ， 所 有能 夠 進(jìn) 行 全 面 而 詳 細(xì) 的 規(guī) 劃 ， 從 而 獲 得 的 方 案 一 般 都 是 全 局 最 優(yōu) 方 案 ， 但 是 實(shí) 時(shí)性 就 很 差 啦 。 當(dāng) 前 ， 國(guó) 內(nèi) 外 很 多 院 校 和 科 研 機(jī) 構(gòu) 對(duì) 集 中 式 控 制 和 分 布 式 控 制 方 法結(jié) 合 的 問(wèn) 題 進(jìn) 行 了 理 論 分 析 和 實(shí) 際 驗(yàn) 證 ， 對(duì) 兩 種 方 法 進(jìn) 行 了 整 合 ， 得 到 了 部 分 分布 式 控 制 方 法 ， 結(jié) 構(gòu) 圖 如 圖 2. 4 所 示 。11在 部 分 分 布 式 控 制 方 法 中 ， 地 面 控 制 站 中 的 操 作 人 員 對(duì) 無(wú) 人 機(jī) 返 回 的 信 息 進(jìn)行 歸 納 和 分 析 ， 在 靜 態(tài) 環(huán) 境 下 給 無(wú) 人 機(jī) 編 隊(duì) 中 的 每 架 無(wú) 人 機(jī) 都 設(shè) 計(jì) 了 初 始 任 務(wù) 分配 方 案 。 在 動(dòng) 態(tài) 環(huán) 境 下 ， 例 如 無(wú) 人 機(jī) 狀 態(tài) 的 改 變 ， 任 務(wù) 的 改 變 將 導(dǎo) 致 任 務(wù) 的 再 分配 。 此 時(shí) ， 無(wú) 人 機(jī) 編 隊(duì) 中 的 無(wú) 人 機(jī) 發(fā) 揮 自 己 的 自 主 性 ， 重 新 對(duì) 任 務(wù) 目 標(biāo) 信 息 采 集并 分 析 ， 在 編 隊(duì) 中 與 其 它 無(wú) 人 機(jī) 進(jìn) 行 信 息 的 共 享 和 交 互 。 地 面 控 制 站 中 的 操 作 人員 在 某 些 特 定 的 時(shí) 候 對(duì) 無(wú) 人 機(jī) 編 隊(duì) 發(fā) 送 任 務(wù) 指 令 ， 大 部 分 時(shí) 候 依 靠 的 是 無(wú) 人 機(jī) 編隊(duì) 自 身 的 協(xié) 同 分 配 。 主 要 既 提 高 了 實(shí) 時(shí) 性 ， 又 大 大 減 小 了 地 面 工 作 站 的 任 務(wù) 量 ，得 到 的 任 務(wù) 分 配 方 案 也 是 相 對(duì) 合 理 的 。 部 分 分 布 是 控 制 方 法 對(duì) 集 中 式 控 制 和 分 布式 控 制 方 法 進(jìn) 行 取 長(zhǎng) 補(bǔ) 短 ， 體 現(xiàn) 了 人 們 的 智 慧 ， 具 有 較 強(qiáng) 的 實(shí) 際 應(yīng) 用 意 義 。2. 3 無(wú) 人 機(jī) 任 務(wù) 分 配 模 型 分 類(lèi)根 據(jù) 任 務(wù) 分 配 建 模 分 類(lèi) ， 現(xiàn) 階 段 的 模 型 主 要 有 多 旅 行 商 問(wèn) 題 [}2}(MultipleTraveling Sa-lesman Problem, MTSP)模 型 ， 通 用 分 配 問(wèn) 題 [3}(Generalized AssignmentProblem, GAP)模 型 ， 車(chē) 輛 路 徑 問(wèn) 題 [4}(Vehicle Routing Problem, VRP)模 型 ， 混合 整數(shù) 線 性 規(guī) 劃 [s},}6},}}},}s},}9}(Mixed Integer Linear Programming, MILP)模 型 以 及CMTAP(Cooperative Multiple Task Assignment Problem)模 型 。2. 3. 1 多 旅 行 商 問(wèn) 題 模 型通 常 ， 我 們 所 說(shuō) 的 旅 行 商 問(wèn) 題 是 一 個(gè) NP 完 全 問(wèn) 題 ， 具 的 定 義 如 下 :假 設(shè) 有 a個(gè) 旅 行 商 人 ， 方 個(gè) 城 市 ， 每 個(gè) 旅 行 商 人 都 要 沿 著 城 市 之 間 的 道 路 訪 問(wèn) 其 中 的 一 些 城市 ， 最 后 所 有 的 旅 行 商 人 都 要 返 回 初 始 的 城 市 ， 限 制 每 個(gè) 城 市 都 要 被 訪 問(wèn) 并 且 有且 僅 有 一 次 ， 問(wèn) 題 所 要 達(dá) 到 的 目 的 是 在 完 成 對(duì) 所 有 城 市 訪 問(wèn) 的 同 時(shí) ， 總 距 離 最 短 、完 成 任 務(wù) 時(shí) 間 最 短 、 消 耗 最 小 、 收 益 最 大 等 。 把 旅 行 上 問(wèn) 題 模 型 應(yīng) 用 到 無(wú) 人 機(jī) 任務(wù) 分 配 中 去 ， 我 們 假 設(shè) 有 一 個(gè) 二 架 無(wú) 人 機(jī) 的 無(wú) 人 機(jī) 編 隊(duì) ， 有 二 個(gè) 目 標(biāo) 任 務(wù) 的 任 務(wù)集 ， 無(wú) 人 機(jī) 編 隊(duì) 從 同 一 個(gè) 基 地 出 發(fā) ， 沿 著 預(yù) 先 設(shè) 定 的 飛 行 航 路 ， 完 成 所 有 的 任 務(wù) ，每 個(gè) 任 務(wù) 只 能 被 完 成 一 次 ， 最 后 考 慮 無(wú) 人 機(jī) 的 總 航 程 ， 無(wú) 人 機(jī) 完 成 任 務(wù) 的 時(shí) 間 ，無(wú) 人 機(jī) 消 耗 的 能 力 ， 完 成 任 務(wù) 的 價(jià) 值 利 益 等 。2. 3. 2 通 用 分 配 問(wèn) 題 模 型通 用 分 配 問(wèn) 題 模 型 考 慮 將 二 個(gè) 任 務(wù) 分 配 給 二 個(gè) 單 體 ， 每 個(gè) 任 務(wù) 只 能 給 一 個(gè) 單體 并 且 單 體 的 資 源 受 到 限 制 。 相 當(dāng) 于 二 個(gè) 任 務(wù) 分 配 給12給 一 個(gè) 無(wú) 人 機(jī) 執(zhí) 行 并 且 無(wú) 人 機(jī) 的 資 源 ， 如 最 大 任 務(wù) 數(shù) ，二 個(gè) 無(wú) 人 機(jī) ， 每 個(gè) 任 務(wù) 只 能最 大 航 程 受 到 限 制 。2. 3. 3 車(chē) 輛 路 徑 問(wèn) 題 模 型我 們 對(duì) 車(chē) 輛 路 徑 模 型 進(jìn) 行 如 下 描 述 :假 設(shè) 有 二 輛 貨 車(chē) ， 每 輛 車(chē) 的 負(fù) 載 能 力 不同 ， 它 們 從 同 一 個(gè) 基 地 出 發(fā) ， 為 二 個(gè) 目 標(biāo) 點(diǎn) 輸 送 貨 物 ， 每 個(gè) 目 標(biāo) 點(diǎn) 需 要 送 達(dá) 的 貨物 數(shù) 量 不 同 。 最 后 ， 所 有 貨 車(chē) 回 到 出 發(fā) 點(diǎn) 。 車(chē) 輛 路 徑 問(wèn) 題 模 型 [yo]要 考 慮 送 達(dá) 的 時(shí)間 ， 貨 物 送 達(dá) 的 消 耗 ， 完 成 輸 送 的 價(jià) 值 等 ， 并 保 證 所 有 的 貨 物 安 全 送 達(dá) 。2. 3. 4 混 合 整 數(shù) 線 性 規(guī) 劃 模 型混 合 整 數(shù) 線 性 利 用 線 性 化 函 數(shù) 建 立 模 型 ， 模 型 描 述 簡(jiǎn) 潔 、 直 接 ， 有 助 于 提 高無(wú) 人 機(jī) 任 務(wù) 執(zhí) 行 效 率 和 生 存 能 力 ， 達(dá) 到 了 任 務(wù) 分 配 的 目 的 和 初 衷 而 且 可 以 通 過(guò) 對(duì)約 束 條 件 的 修 正 來(lái) 滿(mǎn) 足 實(shí) 際 問(wèn) 題 需 要 ， 但 是 模 型 規(guī) 模 不 能 過(guò) 大 。 問(wèn) 題 規(guī) 模 過(guò) 大 將導(dǎo) 致 計(jì) 算 量 指 數(shù) 型 增 長(zhǎng) ， 任 務(wù) 分 配 的 實(shí) 時(shí) 性 得 不 到 保 證 。2. 3. 5 CMTAP 通 用 模 型隨 著 無(wú) 人 機(jī) 能 力 不 斷 增 強(qiáng) ， 無(wú) 人 機(jī) 執(zhí) 行 任 務(wù) 的 復(fù) 雜 程 度 也 隨 之 增 強(qiáng) ， 不 同 任務(wù) 之 間 存 在 著 復(fù) 雜 的 時(shí) 序 以 及 時(shí) 間 約 束 。 對(duì) 于 這 一 類(lèi) 復(fù) 雜 的 任 務(wù) 集 合 ， 目 前 大 多數(shù) 任 務(wù) 分 配 模 型 無(wú) 法 對(duì) 其 進(jìn) 行 有 效 的 描 述 。 一 種 CMTAP 模 型 「 川 被 引 出 ， 這 種 模 型充 分 考 慮 一 組 無(wú) 人 機(jī) 完 成 一 系 列 針 對(duì) 地 面 目 標(biāo) 的 連 貫 任 務(wù) ， 包 括 任 務(wù) 目 標(biāo) 的 識(shí) 別 、攻 擊 、 毀 傷 評(píng) 估 等 。2. 4 靜 態(tài) 任 務(wù) 分 配 算 法在 靜 態(tài) 環(huán) 境 中 ， 無(wú) 人 機(jī) 和 任 務(wù) 都 是 確 定 的 ， 不 發(fā) 生 改 變 。 在 這 樣 的 條 件 下 ，多 無(wú) 人 機(jī) 任 務(wù) 分 配 的 算 法 主 要 有 :群 算 法 ， 市 場(chǎng) 機(jī) 制 算 法 和 進(jìn) 化 算 法 。2. 4. 1 群 算 法群 算 法 主 要 模 仿 自 然 界 中 各 種 生 物 的 群 體 化 行 為 ， 例 如 蟲(chóng) 群 「 12]和 羊 群 。 我們通 過(guò) 對(duì) 蟲(chóng) 群 群 體 化 行 為