本科畢業(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) 害 的 防 護 上 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ù) 。 無 人 機 具 有 重 量 輕 、 維 護 成 本 低 、 機 動 性 能高 等 明 顯 優(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) 害 的 防 護 上和 平 和 發(fā) 展 當(dāng) 今 世 界 的 兩 大 主 題 ， 所 以 無 人 機 的 應(yīng) 用 也 由 軍 用 慢 慢 轉(zhuǎn) 向 民 用 。其 中 最 主 要 的 民 用 用 途 是 在 自 然 災(zāi) 害 的 防 護 上 。 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) 害 防 護 上 的 實 例 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) 防 護 的 應(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]和 羊 群 。 我們通 過 對 蟲 群 群 體 化 行 為