無人機組群巡檢滅火系統(tǒng)設(shè)計【含CAD圖紙、說明書、SW三維圖紙】

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