1. 項(xiàng)目概述從競(jìng)賽題目到現(xiàn)實(shí)問(wèn)題的映射看到“多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃”這個(gè)題目很多人的第一反應(yīng)可能是復(fù)雜的算法、抽象的數(shù)學(xué)模型感覺(jué)離實(shí)際應(yīng)用很遠(yuǎn)。但作為一個(gè)在自動(dòng)化與智能系統(tǒng)領(lǐng)域摸爬滾打了十多年的從業(yè)者我想說(shuō)這道競(jìng)賽題恰恰是當(dāng)前工業(yè)界和學(xué)術(shù)界最前沿、也最“接地氣”的核心難題之一。它不僅僅是紙上談兵其背后對(duì)應(yīng)的是物流倉(cāng)儲(chǔ)中的AGV車(chē)隊(duì)調(diào)度、智慧農(nóng)業(yè)中的植保無(wú)人機(jī)編隊(duì)、城市安防中的巡邏無(wú)人機(jī)網(wǎng)絡(luò)甚至是未來(lái)城市空中交通UAM的雛形。這道題的價(jià)值在于它用一個(gè)結(jié)構(gòu)清晰的賽題逼著你去思考如何讓多個(gè)具備自主能力的智能體無(wú)人機(jī)在資源電量、時(shí)間約束下高效、可靠地完成一系列有空間關(guān)聯(lián)的任務(wù)目標(biāo)點(diǎn)。今天我就以這道題為引子拋開(kāi)競(jìng)賽論文的“八股”格式從一個(gè)系統(tǒng)設(shè)計(jì)者的角度拆解一下多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃到底要解決哪些問(wèn)題以及在實(shí)際中我們是如何思考和落地的。簡(jiǎn)單來(lái)說(shuō)任務(wù)規(guī)劃要回答三個(gè)核心問(wèn)題“誰(shuí)去”任務(wù)分配、“怎么去”路徑規(guī)劃以及“何時(shí)去”時(shí)間協(xié)同。這三個(gè)問(wèn)題環(huán)環(huán)相扣任何一個(gè)環(huán)節(jié)的疏漏都可能導(dǎo)致整體方案失效。比如你分配任務(wù)時(shí)沒(méi)考慮無(wú)人機(jī)的續(xù)航可能飛一半就沒(méi)電了你規(guī)劃路徑時(shí)只圖最短可能導(dǎo)致多機(jī)在空中“撞車(chē)”你安排時(shí)間時(shí)沒(méi)留出緩沖一個(gè)環(huán)節(jié)延誤就會(huì)引發(fā)連鎖反應(yīng)。這道A題的精妙之處在于它通常不會(huì)給你一個(gè)現(xiàn)成的、完美的場(chǎng)景而是會(huì)設(shè)置諸如“部分目標(biāo)點(diǎn)需多機(jī)同時(shí)到達(dá)”、“無(wú)人機(jī)有不同載荷能力”、“通信范圍受限”等現(xiàn)實(shí)約束逼迫你建立一個(gè)能同時(shí)處理分配、路徑、時(shí)間的綜合優(yōu)化模型。接下來(lái)我們就深入這個(gè)“綜合優(yōu)化”的黑箱看看里面到底有哪些門(mén)道。2. 核心問(wèn)題拆解協(xié)同規(guī)劃的三重挑戰(zhàn)要解決多無(wú)人機(jī)協(xié)同規(guī)劃我們不能一上來(lái)就想著找算法、寫(xiě)代碼而是必須先把手頭的問(wèn)題拆解明白。這道題通常會(huì)給出一系列目標(biāo)點(diǎn)的經(jīng)緯度坐標(biāo)、無(wú)人機(jī)的起始位置、最大航程或續(xù)航時(shí)間、飛行速度等基礎(chǔ)數(shù)據(jù)。約束條件可能包括每個(gè)目標(biāo)點(diǎn)必須被至少一架無(wú)人機(jī)訪問(wèn)一次覆蓋某些特定目標(biāo)點(diǎn)需要多架無(wú)人機(jī)在時(shí)間窗口內(nèi)同時(shí)到達(dá)協(xié)同無(wú)人機(jī)需要返回起點(diǎn)或指定集結(jié)點(diǎn)回程約束。我們的目標(biāo)是在滿足所有約束的前提下最小化所有無(wú)人機(jī)的總飛行距離、總?cè)蝿?wù)時(shí)間或者最大化完成的目標(biāo)點(diǎn)數(shù)量。2.1 任務(wù)分配從“分活”到“優(yōu)化匹配”任務(wù)分配是協(xié)同的起點(diǎn)。最樸素的想法是“就近原則”哪個(gè)無(wú)人機(jī)離目標(biāo)點(diǎn)近就派誰(shuí)去。這在目標(biāo)點(diǎn)稀疏、無(wú)人機(jī)數(shù)量多時(shí)勉強(qiáng)可行。但一旦引入“多機(jī)協(xié)同訪問(wèn)同一目標(biāo)點(diǎn)”的約束問(wèn)題就復(fù)雜了。這不再是簡(jiǎn)單的“一對(duì)一”分配而是“多對(duì)一”甚至“多對(duì)多”的組合優(yōu)化問(wèn)題。核心難點(diǎn)在于耦合性。例如目標(biāo)點(diǎn)A需要無(wú)人機(jī)1和2同時(shí)到達(dá)目標(biāo)點(diǎn)B需要無(wú)人機(jī)2和3同時(shí)到達(dá)。那么分配給無(wú)人機(jī)2的任務(wù)A和B就產(chǎn)生了耦合因?yàn)樗和B的時(shí)間必須能銜接上并且滿足與其他無(wú)人機(jī)的協(xié)同時(shí)間。此時(shí)分配決策就不能孤立進(jìn)行必須考慮后續(xù)的路徑和時(shí)間安排。在實(shí)際建模中我們通常將其抽象為一個(gè)帶時(shí)間窗和協(xié)同約束的車(chē)輛路徑問(wèn)題VRPTW的變體。每個(gè)無(wú)人機(jī)相當(dāng)于一輛車(chē)目標(biāo)點(diǎn)相當(dāng)于客戶點(diǎn)續(xù)航限制相當(dāng)于車(chē)的容量協(xié)同約束則是一種特殊的時(shí)間窗要求要求多“車(chē)”在同一時(shí)間窗內(nèi)到達(dá)同一“客戶點(diǎn)”。解決這類問(wèn)題精確算法如分支定界對(duì)于稍大規(guī)模的問(wèn)題就力不從心了因此我們更多地依賴啟發(fā)式或元啟發(fā)式算法。注意在初始分配時(shí)一個(gè)常見(jiàn)的技巧是進(jìn)行“聚類預(yù)處理”。即根據(jù)目標(biāo)點(diǎn)的地理分布先用聚類算法如K-means 但需考慮續(xù)航約束確定聚類數(shù)將距離相近的點(diǎn)初步分到一組每組由一個(gè)無(wú)人機(jī)負(fù)責(zé)。這能大幅降低后續(xù)優(yōu)化問(wèn)題的規(guī)模得到一個(gè)不錯(cuò)的初始解。但切記這只是一種啟發(fā)式策略對(duì)于有強(qiáng)協(xié)同約束的點(diǎn)可能需要打破聚類邊界重新調(diào)整。2.2 路徑規(guī)劃不只是“找最短路徑”分配好任務(wù)后每架無(wú)人機(jī)都得到了一系列需要訪問(wèn)的目標(biāo)點(diǎn)序列。接下來(lái)就是為每架無(wú)人機(jī)規(guī)劃訪問(wèn)這些點(diǎn)的最優(yōu)順序和飛行路徑即經(jīng)典的旅行商問(wèn)題TSP。但這里的TSP也不單純因?yàn)樗艿絻蓚€(gè)關(guān)鍵約束的影響續(xù)航約束無(wú)人機(jī)訪問(wèn)所有分配點(diǎn)的總飛行距離不能超過(guò)其最大航程。這可能導(dǎo)致單架無(wú)人機(jī)的TSP路徑無(wú)法一次性走完所有點(diǎn)需要引入“返航充電”或“多次出發(fā)”的子回路問(wèn)題就變成了帶容量約束的車(chē)輛路徑問(wèn)題CVRP。協(xié)同時(shí)間約束對(duì)于需要多機(jī)協(xié)同訪問(wèn)的點(diǎn)各無(wú)人機(jī)規(guī)劃出的路徑必須保證它們能在大致相同的時(shí)間到達(dá)該點(diǎn)。這意味著各機(jī)的路徑規(guī)劃不再是獨(dú)立的它們的出發(fā)時(shí)間、飛行順序都可能需要相互協(xié)調(diào)。因此路徑規(guī)劃層必須與上層的時(shí)間協(xié)同緊密交互。一種常見(jiàn)的思路是分層規(guī)劃先進(jìn)行粗粒度的任務(wù)分配和路徑序列規(guī)劃暫時(shí)忽略精確時(shí)間然后再進(jìn)行細(xì)粒度的時(shí)間排程和速度調(diào)整以滿足協(xié)同點(diǎn)的時(shí)間窗口要求。如果時(shí)間無(wú)法滿足則需要反饋到分配層重新調(diào)整任務(wù)。在路徑規(guī)劃算法層面除了經(jīng)典的遺傳算法GA、模擬退火SA用于求解TSP在實(shí)際工程中還需要考慮可飛區(qū)域禁飛區(qū)、障礙物和飛行動(dòng)力學(xué)轉(zhuǎn)彎半徑、最小步長(zhǎng)。競(jìng)賽中通常簡(jiǎn)化為直線飛行但實(shí)際中可能需要調(diào)用A*、D*或快速隨機(jī)樹(shù)RRT等算法進(jìn)行避障路徑規(guī)劃。2.3 時(shí)間協(xié)同讓時(shí)鐘同步起來(lái)這是“協(xié)同”二字的精髓所在。多架無(wú)人機(jī)要同時(shí)到達(dá)某個(gè)目標(biāo)點(diǎn)關(guān)鍵在于對(duì)每架無(wú)人機(jī)的時(shí)間線進(jìn)行精確編排。這涉及到出發(fā)時(shí)間調(diào)度并非所有無(wú)人機(jī)都同時(shí)出發(fā)。給任務(wù)負(fù)載重、路徑長(zhǎng)的無(wú)人機(jī)提前出發(fā)給任務(wù)輕的延后出發(fā)是平衡到達(dá)時(shí)間的基本手段。速度調(diào)整無(wú)人機(jī)可以在其最大和最小巡航速度之間調(diào)整。對(duì)于某段航路如果時(shí)間充裕可以飛慢點(diǎn)省電如果需要趕時(shí)間就飛快點(diǎn)。通過(guò)微調(diào)各段航路的速度可以精確控制到達(dá)每個(gè)航路點(diǎn)的時(shí)間。等待策略先到達(dá)協(xié)同點(diǎn)的無(wú)人機(jī)可能需要空中懸停等待但這會(huì)消耗額外能量。因此優(yōu)化的目標(biāo)是盡量減少不必要的等待時(shí)間讓各機(jī)的到達(dá)時(shí)間盡可能“緊耦合”。時(shí)間協(xié)同的建模通常基于時(shí)間窗約束。為每個(gè)目標(biāo)點(diǎn)尤其是協(xié)同點(diǎn)設(shè)定一個(gè)允許到達(dá)的時(shí)間區(qū)間。在優(yōu)化模型中這體現(xiàn)為一組不等式約束。求解器或優(yōu)化算法的任務(wù)就是在滿足所有時(shí)間窗約束的前提下優(yōu)化總目標(biāo)如總時(shí)間、總能耗。一個(gè)實(shí)用的技巧是引入時(shí)間松弛變量。即允許到達(dá)時(shí)間稍微偏離理想時(shí)間但給予懲罰。這樣可以將嚴(yán)格的硬約束轉(zhuǎn)化為帶懲罰的軟約束使優(yōu)化問(wèn)題更容易求解并能得到在輕微違反時(shí)間要求下的“次優(yōu)但可行”解這在工程上往往比“無(wú)解”更有價(jià)值。3. 模型構(gòu)建與算法選型實(shí)戰(zhàn)理論拆解完畢我們進(jìn)入實(shí)戰(zhàn)環(huán)節(jié)如何把上述問(wèn)題變成一個(gè)可以計(jì)算的模型并選擇合適的算法來(lái)求解這是競(jìng)賽和實(shí)際工程中的核心。3.1 數(shù)學(xué)建模定義變量、約束和目標(biāo)一個(gè)典型的混合整數(shù)規(guī)劃模型可能包含以下要素決策變量x_{ijk}二進(jìn)制變量表示無(wú)人機(jī)k是否從目標(biāo)點(diǎn)i飛往目標(biāo)點(diǎn)ji和j可以是目標(biāo)點(diǎn)或倉(cāng)庫(kù)/起點(diǎn)。t_{ik}連續(xù)變量表示無(wú)人機(jī)k到達(dá)目標(biāo)點(diǎn)i的時(shí)間。s_{ik}連續(xù)變量表示無(wú)人機(jī)k在目標(biāo)點(diǎn)i的服務(wù)開(kāi)始時(shí)間可能包含等待。目標(biāo)函數(shù)通常選擇其一或加權(quán)和最小化總飛行距離Minimize Σ Σ Σ c_{ij} * x_{ijk}(c_{ij}為i到j(luò)的距離)最小化最大任務(wù)完成時(shí)間完工時(shí)間Minimize max_{k}(t_{end,k})最小化總能耗與距離和懸停時(shí)間相關(guān)。核心約束流平衡約束每個(gè)無(wú)人機(jī)從起點(diǎn)出發(fā)最終回到終點(diǎn)中間訪問(wèn)點(diǎn)的進(jìn)出流量平衡。每個(gè)目標(biāo)點(diǎn)至少被訪問(wèn)一次Σ_k Σ_j x_{ijk} 1(對(duì)于每個(gè)目標(biāo)點(diǎn)i)。續(xù)航/容量約束Σ_i Σ_j d_{ij} * x_{ijk} Range_k(對(duì)于每個(gè)無(wú)人機(jī)k)。時(shí)間連續(xù)性約束消除子回路經(jīng)典的MTZ約束或流約束確保路徑在時(shí)間上是連貫的例如t_{jk} t_{ik} service_i travel_{ij} - M*(1 - x_{ijk})其中M是一個(gè)很大的數(shù)。協(xié)同時(shí)間約束對(duì)于需要無(wú)人機(jī)集K同時(shí)訪問(wèn)的目標(biāo)點(diǎn)i要求|t_{ik1} - t_{ik2}| Δt(對(duì)于所有k1, k2 in K)Δt為允許的最大時(shí)間差。時(shí)間窗約束對(duì)于某些點(diǎn)e_i t_{ik} l_i。建立這樣一個(gè)模型后對(duì)于小規(guī)模問(wèn)題如目標(biāo)點(diǎn)20無(wú)人機(jī)4可以使用商業(yè)求解器如Gurobi, CPLEX或開(kāi)源求解器如OR-Tools直接求最優(yōu)解。但對(duì)于競(jìng)賽或?qū)嶋H中常見(jiàn)的中大規(guī)模問(wèn)題精確求解器會(huì)在可接受時(shí)間內(nèi)無(wú)法求解這時(shí)就必須轉(zhuǎn)向啟發(fā)式方法。3.2 算法策略元啟發(fā)式算法的舞臺(tái)當(dāng)精確求解不可行時(shí)元啟發(fā)式算法成為主力。它們不一定能找到理論最優(yōu)解但能在合理時(shí)間內(nèi)找到高質(zhì)量、可用的可行解。遺傳算法GA編碼這是關(guān)鍵。一種有效的編碼方式是“染色體”由多段組成每段代表一架無(wú)人機(jī)的任務(wù)序列目標(biāo)點(diǎn)ID列表用特殊分隔符如0區(qū)分不同無(wú)人機(jī)。例如對(duì)于3架無(wú)人機(jī)訪問(wèn)9個(gè)點(diǎn)染色體可能編碼為[1,4,7,0,2,5,8,0,3,6,9]。適應(yīng)度函數(shù)直接取目標(biāo)函數(shù)值的倒數(shù)如總距離的倒數(shù)并加入對(duì)約束違反的懲罰項(xiàng)如超出續(xù)航的距離懲罰、違反時(shí)間窗的時(shí)間懲罰。懲罰系數(shù)需要仔細(xì)調(diào)參。交叉與變異設(shè)計(jì)針對(duì)路徑表示的交叉算子如順序交叉OX和變異算子如交換、逆轉(zhuǎn)、插入。需要特別注意操作后不能破壞“每個(gè)點(diǎn)只訪問(wèn)一次”的約束。心得GA的參數(shù)種群大小、交叉率、變異率對(duì)結(jié)果影響巨大。建議采用自適應(yīng)參數(shù)策略并在初期增加變異率以探索解空間后期降低變異率以收斂。模擬退火SA初始解可以用最簡(jiǎn)單的最近鄰法為每架無(wú)人機(jī)生成初始路徑。鄰域操作定義如何從當(dāng)前解產(chǎn)生一個(gè)新解。常用操作包括將某個(gè)目標(biāo)點(diǎn)從一架無(wú)人機(jī)的路徑中移除插入到另一架無(wú)人機(jī)的路徑中交換兩架無(wú)人機(jī)路徑中的兩個(gè)目標(biāo)點(diǎn)反轉(zhuǎn)某段路徑。降溫策略采用指數(shù)降溫T T0 * alpha^iter。初始溫度T0要足夠高使算法在初期有足夠概率接受差解降溫系數(shù)alpha通常取0.95~0.99。心得SA實(shí)現(xiàn)相對(duì)簡(jiǎn)單調(diào)參比GA少。關(guān)鍵在于鄰域操作的設(shè)計(jì)要能有效探索解空間。記錄搜索過(guò)程中遇到的最優(yōu)解而非僅僅跟蹤當(dāng)前解。蟻群算法ACO更適合求解純TSP問(wèn)題。對(duì)于多無(wú)人機(jī)VRP問(wèn)題需要設(shè)計(jì)更復(fù)雜的圖結(jié)構(gòu)和信息素更新規(guī)則例如將“無(wú)人機(jī)-目標(biāo)點(diǎn)”的分配也納入信息素矩陣實(shí)現(xiàn)起來(lái)較為復(fù)雜但有時(shí)在路徑優(yōu)化上能表現(xiàn)出色。在實(shí)際競(jìng)賽或工程中我推薦采用“兩階段混合策略”第一階段快速構(gòu)造可行解。使用基于聚類的啟發(fā)式方法快速得到一個(gè)滿足所有硬約束覆蓋、續(xù)航的初始任務(wù)分配和路徑方案。這個(gè)解可能質(zhì)量不高但它是可行的起點(diǎn)。第二階段迭代優(yōu)化。以第一階段得到的解作為初始解投入元啟發(fā)式算法如GA或SA進(jìn)行優(yōu)化。優(yōu)化過(guò)程主要改善目標(biāo)函數(shù)縮短距離、平衡時(shí)間并通過(guò)懲罰函數(shù)機(jī)制來(lái)處理軟約束如時(shí)間協(xié)同的輕微違反。4. 關(guān)鍵實(shí)現(xiàn)細(xì)節(jié)與編程技巧有了模型和算法思路接下來(lái)就是編程實(shí)現(xiàn)。這里分享一些從實(shí)際項(xiàng)目中積累的關(guān)鍵細(xì)節(jié)和技巧。4.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)高效的數(shù)據(jù)結(jié)構(gòu)是算法高效運(yùn)行的基礎(chǔ)。class TargetPoint: def __init__(self, id, x, y, service_time0, time_window(0, float(inf))): self.id id # 目標(biāo)點(diǎn)ID self.x x # 橫坐標(biāo) self.y y # 縱坐標(biāo) self.service_time service_time # 服務(wù)時(shí)間如拍照耗時(shí) self.tw_start, self.tw_end time_window # 時(shí)間窗 class UAV: def __init__(self, id, home_x, home_y, speed, max_range): self.id id self.home (home_x, home_y) # 起始點(diǎn) self.speed speed self.max_range max_range self.route [] # 存儲(chǔ)訪問(wèn)的目標(biāo)點(diǎn)ID序列 self.departure_time 0 # 出發(fā)時(shí)間 class Solution: def __init__(self): self.uav_assignments {} # UAV_id - list of TargetPoint IDs self.total_distance 0 self.makespan 0 # 最大完成時(shí)間 self.is_feasible True self.constraint_violation 0 # 約束違反度用于懲罰函數(shù)使用面向?qū)ο蟮脑O(shè)計(jì)將問(wèn)題實(shí)體清晰地封裝起來(lái)后續(xù)計(jì)算距離、時(shí)間、檢查約束都會(huì)非常清晰。4.2 距離與時(shí)間計(jì)算這是最基本的計(jì)算單元會(huì)被頻繁調(diào)用務(wù)必高效。import math import numpy as np def euclidean_distance(point1, point2): 計(jì)算兩點(diǎn)間歐氏距離。實(shí)際中可能需替換為球面距離如Haversine公式。 return math.sqrt((point1.x - point2.x)**2 (point1.y - point2.y)**2) def calculate_route_details(uav, target_dict, start_time0): 計(jì)算給定無(wú)人機(jī)路徑的詳細(xì)時(shí)間線和總距離。 返回總距離 到達(dá)時(shí)間列表 離開(kāi)時(shí)間列表 是否超航程 current_pos uav.home total_dist 0 arrival_times [start_time] departure_times [] current_time start_time for target_id in uav.route: target target_dict[target_id] # 飛行段 leg_dist euclidean_distance(current_pos, target) total_dist leg_dist flight_time leg_dist / uav.speed current_time flight_time arrival_times.append(current_time) # 服務(wù)或等待以滿足時(shí)間窗 service_start max(current_time, target.tw_start) # 如果早到需等待 current_time service_start target.service_time departure_times.append(current_time) current_pos target # 返回基地 return_dist euclidean_distance(current_pos, uav.home) total_dist return_dist return_time return_dist / uav.speed current_time return_time is_range_ok total_dist uav.max_range return total_dist, arrival_times, departure_times, is_range_ok, current_time這個(gè)函數(shù)是評(píng)估解質(zhì)量的核心。在優(yōu)化算法的每一步都需要調(diào)用它來(lái)計(jì)算目標(biāo)函數(shù)值和檢查約束。4.3 約束處理與懲罰函數(shù)設(shè)計(jì)元啟發(fā)式算法通常處理約束的方式是懲罰函數(shù)法。將約束違反的程度量化并乘以一個(gè)懲罰系數(shù)后加到目標(biāo)函數(shù)值上。def evaluate_solution(solution, target_dict, uav_dict, penalty_coeff1000): 評(píng)估一個(gè)解的質(zhì)量返回帶懲罰的總成本。 total_cost 0 total_violation 0 # 1. 計(jì)算基礎(chǔ)目標(biāo)如總距離 for uav_id, route in solution.uav_assignments.items(): uav uav_dict[uav_id] uav.route route # 臨時(shí)賦值 dist, _, _, is_range_ok, _ calculate_route_details(uav, target_dict) total_cost dist if not is_range_ok: # 續(xù)航約束違反懲罰 violation dist - uav.max_range total_violation violation # 2. 檢查覆蓋約束每個(gè)目標(biāo)點(diǎn)是否都被訪問(wèn) all_visited_points set() for route in solution.uav_assignments.values(): all_visited_points.update(route) uncovered set(target_dict.keys()) - all_visited_points if uncovered: total_violation len(uncovered) * 10 # 每個(gè)未訪問(wèn)點(diǎn)給予固定懲罰 # 3. 檢查協(xié)同時(shí)間約束需要更精細(xì)的時(shí)間計(jì)算 # ... (此處需根據(jù)具體協(xié)同約束實(shí)現(xiàn)計(jì)算各協(xié)同點(diǎn)到達(dá)時(shí)間的方差或最大時(shí)間差) # 4. 綜合成本 基礎(chǔ)成本 懲罰系數(shù) * 違反度 fitness total_cost penalty_coeff * total_violation solution.total_distance total_cost solution.constraint_violation total_violation solution.is_feasible (total_violation 0) return fitness懲罰系數(shù)penalty_coeff的設(shè)定是一門(mén)藝術(shù)。設(shè)得太小算法可能會(huì)傾向于接受違反約束的“壞解”設(shè)得太大可能會(huì)讓搜索陷入局部最優(yōu)只專注于滿足約束而忽略了優(yōu)化目標(biāo)。一個(gè)策略是動(dòng)態(tài)調(diào)整懲罰系數(shù)初期設(shè)小些以廣泛探索后期逐漸增大以迫使搜索可行域。4.4 算法核心循環(huán)示例模擬退火這里給出一個(gè)模擬退火算法的簡(jiǎn)化框架。def simulated_annealing(initial_solution, target_dict, uav_dict, max_iter5000): current_sol initial_solution current_cost evaluate_solution(current_sol, target_dict, uav_dict) best_sol copy.deepcopy(current_sol) best_cost current_cost T 1000.0 # 初始溫度 T_min 1e-3 # 終止溫度 alpha 0.995 # 降溫系數(shù) iter 0 while T T_min and iter max_iter: # 1. 產(chǎn)生鄰域新解 new_sol generate_neighbor(current_sol, target_dict, uav_dict) new_cost evaluate_solution(new_sol, target_dict, uav_dict) # 2. 計(jì)算成本差 delta_cost new_cost - current_cost # 3. Metropolis準(zhǔn)則 if delta_cost 0 or math.exp(-delta_cost / T) random.random(): current_sol new_sol current_cost new_cost # 4. 更新歷史最優(yōu) if new_cost best_cost and new_sol.is_feasible: # 通常只記錄可行解中的最優(yōu) best_sol copy.deepcopy(new_sol) best_cost new_cost # 5. 降溫 T * alpha iter 1 # 可選每N代輸出一次進(jìn)度 if iter % 500 0: print(fIter {iter}, T{T:.2f}, Current Cost{current_cost:.2f}, Best Cost{best_cost:.2f}) return best_sol, best_cost def generate_neighbor(current_sol, target_dict, uav_dict): 鄰域操作隨機(jī)選擇一種擾動(dòng)方式生成新解 new_sol copy.deepcopy(current_sol) uav_ids list(new_sol.uav_assignments.keys()) # 隨機(jī)選擇一種鄰域操作 op random.choice([relocate, exchange, reverse]) if op relocate: # 將一個(gè)點(diǎn)從一條路徑移到另一條路徑的隨機(jī)位置 src_uav random.choice(uav_ids) if len(new_sol.uav_assignments[src_uav]) 0: point_idx random.randrange(len(new_sol.uav_assignments[src_uav])) point new_sol.uav_assignments[src_uav].pop(point_idx) dst_uav random.choice(uav_ids) insert_idx random.randrange(len(new_sol.uav_assignments[dst_uav]) 1) new_sol.uav_assignments[dst_uav].insert(insert_idx, point) elif op exchange: # 交換兩條路徑中的兩個(gè)點(diǎn) uav1, uav2 random.sample(uav_ids, 2) if new_sol.uav_assignments[uav1] and new_sol.uav_assignments[uav2]: idx1 random.randrange(len(new_sol.uav_assignments[uav1])) idx2 random.randrange(len(new_sol.uav_assignments[uav2])) new_sol.uav_assignments[uav1][idx1], new_sol.uav_assignments[uav2][idx2] new_sol.uav_assignments[uav2][idx2], new_sol.uav_assignments[uav1][idx1] # reverse 操作反轉(zhuǎn)某條路徑中的一段這里省略實(shí)現(xiàn) return new_sol這個(gè)框架清晰地展示了SA的流程。generate_neighbor函數(shù)的設(shè)計(jì)直接決定了算法的搜索能力可以設(shè)計(jì)更多樣化的操作如2-opt局部路徑優(yōu)化、跨路徑的多點(diǎn)交換等。5. 性能優(yōu)化與結(jié)果分析當(dāng)問(wèn)題規(guī)模變大時(shí)算法的效率至關(guān)重要。評(píng)估函數(shù)evaluate_solution會(huì)被調(diào)用成千上萬(wàn)次必須優(yōu)化。5.1 計(jì)算性能優(yōu)化技巧預(yù)計(jì)算距離矩陣在算法開(kāi)始前計(jì)算所有點(diǎn)包括無(wú)人機(jī)起點(diǎn)兩兩之間的距離存儲(chǔ)在一個(gè)矩陣中。這樣在評(píng)估時(shí)查表即可獲得距離避免重復(fù)計(jì)算平方根。# 預(yù)計(jì)算 all_nodes [uav.home for uav in uavs] list(targets.values()) n len(all_nodes) dist_matrix np.zeros((n, n)) for i in range(n): for j in range(n): if i ! j: dist_matrix[i][j] euclidean_distance(all_nodes[i], all_nodes[j])增量評(píng)估對(duì)于SA或GA中的鄰域操作新解通常只改變了一小部分。與其重新計(jì)算整個(gè)解的成本不如只計(jì)算受影響路徑的變化量。例如如果只是將一個(gè)點(diǎn)從無(wú)人機(jī)A移到無(wú)人機(jī)B那么只需要重新計(jì)算A和B兩條路徑的成本而不是所有無(wú)人機(jī)。這能極大提升速度但實(shí)現(xiàn)起來(lái)更復(fù)雜需要維護(hù)額外的狀態(tài)信息。使用Numpy向量化操作在計(jì)算路徑距離或時(shí)間時(shí)盡量使用Numpy數(shù)組操作代替循環(huán)。并行化在GA中種群中每個(gè)個(gè)體的評(píng)估是獨(dú)立的可以輕松使用多進(jìn)程Python的multiprocessing庫(kù)進(jìn)行并行評(píng)估充分利用多核CPU。5.2 結(jié)果可視化與評(píng)估算出結(jié)果不是終點(diǎn)能直觀地展示和評(píng)估結(jié)果同樣重要。import matplotlib.pyplot as plt def visualize_solution(best_solution, uav_dict, target_dict): plt.figure(figsize(10, 8)) colors [r, g, b, c, m, y, k] # 繪制所有目標(biāo)點(diǎn) for tid, target in target_dict.items(): plt.plot(target.x, target.y, ko, markersize8) plt.text(target.x, target.y0.2, str(tid), hacenter) # 繪制每架無(wú)人機(jī)的路徑 for idx, (uav_id, route) in enumerate(best_solution.uav_assignments.items()): if not route: continue uav uav_dict[uav_id] color colors[idx % len(colors)] # 繪制起點(diǎn) plt.plot(uav.home[0], uav.home[1], colors, markersize12, labelfUAV{uav_id} Home) # 繪制路徑 path_x [uav.home[0]] path_y [uav.home[1]] for point_id in route: point target_dict[point_id] path_x.append(point.x) path_y.append(point.y) # 返回起點(diǎn) path_x.append(uav.home[0]) path_y.append(uav.home[1]) plt.plot(path_x, path_y, color-o, linewidth2, markersize6, labelfUAV{uav_id} Path) plt.xlabel(X Coordinate) plt.ylabel(Y Coordinate) plt.title(Multi-UAV Cooperative Task Planning Result) plt.grid(True, linestyle--, alpha0.7) plt.legend() plt.axis(equal) # 保證x,y軸比例相同 plt.show() # 打印統(tǒng)計(jì)信息 print( Solution Summary ) print(fTotal Distance: {best_solution.total_distance:.2f}) print(fMakespan (Max Completion Time): {best_solution.makespan:.2f}) print(fIs Feasible: {best_solution.is_feasible}) for uav_id, route in best_solution.uav_assignments.items(): dist, arr, dep, is_ok, comp_time calculate_route_details(uav_dict[uav_id], target_dict) print(f UAV {uav_id}: {len(route)} points, Distance {dist:.2f}, OK? {is_ok})可視化能立刻讓你發(fā)現(xiàn)方案的不合理之處比如路徑交叉嚴(yán)重、負(fù)載極不均衡等。結(jié)合統(tǒng)計(jì)信息可以對(duì)解的質(zhì)量進(jìn)行定量評(píng)估。5.3 靈敏度分析與參數(shù)調(diào)優(yōu)模型和算法中有很多參數(shù)如GA的種群大小、變異率SA的初始溫度、降溫系數(shù)懲罰函數(shù)的系數(shù)等。這些參數(shù)沒(méi)有標(biāo)準(zhǔn)答案需要針對(duì)具體問(wèn)題進(jìn)行調(diào)整。一個(gè)系統(tǒng)的方法是進(jìn)行參數(shù)掃描。例如對(duì)SA的初始溫度T0和降溫系數(shù)alpha進(jìn)行網(wǎng)格搜索每個(gè)參數(shù)組合運(yùn)行算法多次避免隨機(jī)性影響記錄平均最優(yōu)解和收斂代數(shù)。通過(guò)分析結(jié)果找到相對(duì)魯棒的參數(shù)區(qū)間。雖然耗時(shí)但對(duì)于一個(gè)重要的項(xiàng)目或競(jìng)賽花時(shí)間調(diào)參是值得的它能讓你的算法性能提升一個(gè)檔次。此外還要進(jìn)行靈敏度分析如果無(wú)人機(jī)的續(xù)航增加10%總成本能降低多少如果某個(gè)協(xié)同點(diǎn)的時(shí)間窗口要求放寬對(duì)整體規(guī)劃有何影響這些分析能幫助你理解問(wèn)題的關(guān)鍵瓶頸所在并在實(shí)際應(yīng)用中提供決策支持例如是應(yīng)該升級(jí)無(wú)人機(jī)電池還是應(yīng)該放寬某些操作要求。6. 從模型到現(xiàn)實(shí)的思考與擴(kuò)展競(jìng)賽題目是一個(gè)高度簡(jiǎn)化的模型而現(xiàn)實(shí)世界要復(fù)雜得多。基于此我們可以思考幾個(gè)擴(kuò)展方向這也是實(shí)際項(xiàng)目中的常見(jiàn)挑戰(zhàn)動(dòng)態(tài)與不確定性現(xiàn)實(shí)中的無(wú)人機(jī)可能遇到突發(fā)故障、天氣變化、臨時(shí)新增任務(wù)等。這就需要?jiǎng)討B(tài)重規(guī)劃能力。一種思路是采用滾動(dòng)時(shí)域優(yōu)化只規(guī)劃未來(lái)一小段時(shí)間的詳細(xì)路徑并根據(jù)最新?tīng)顟B(tài)周期性重新規(guī)劃。通信約束題目通常假設(shè)全局通信無(wú)礙。現(xiàn)實(shí)中無(wú)人機(jī)間通信距離有限。規(guī)劃時(shí)需要考慮通信網(wǎng)絡(luò)拓?fù)浯_保執(zhí)行協(xié)同任務(wù)的無(wú)人機(jī)之間能夠保持通信或者規(guī)劃中繼節(jié)點(diǎn)。這引入了連通性保持的約束。異構(gòu)無(wú)人機(jī)無(wú)人機(jī)可能有不同的速度、載荷、傳感器能力。任務(wù)點(diǎn)也可能有不同類型偵察、投送、監(jiān)測(cè)需要特定能力的無(wú)人機(jī)。問(wèn)題就升級(jí)為異構(gòu)車(chē)隊(duì)車(chē)輛路徑問(wèn)題建模時(shí)需增加無(wú)人機(jī)-任務(wù)的能力匹配約束。三維空間與避障從二維平面上升到三維空間并考慮地形和障礙物路徑規(guī)劃算法需要升級(jí)到三維A*、RRT*等計(jì)算復(fù)雜度大增。能源消耗模型能耗不僅與距離相關(guān)還與速度、加速度、載重、風(fēng)阻有關(guān)。建立一個(gè)更精細(xì)的能耗模型可以優(yōu)化出更省電的飛行策略例如采用“脈沖式”飛行加速-滑行。解決這些問(wèn)題往往需要融合運(yùn)籌優(yōu)化、控制理論、通信網(wǎng)絡(luò)和人工智能等多個(gè)領(lǐng)域的知識(shí)。這道競(jìng)賽題就像一把鑰匙打開(kāi)了一扇通往復(fù)雜系統(tǒng)智能決策的大門(mén)。它訓(xùn)練的不是某個(gè)特定算法的套用而是一種系統(tǒng)化的問(wèn)題分解、建模和求解的思維能力。無(wú)論你未來(lái)是從事算法研究、機(jī)器人開(kāi)發(fā)還是工業(yè)調(diào)度這種能力都至關(guān)重要。最后分享一個(gè)我個(gè)人的心得在動(dòng)手編程前花足夠的時(shí)間在紙上畫(huà)圖、分析約束、設(shè)計(jì)算法流程這通常會(huì)節(jié)省你大量的調(diào)試時(shí)間。好的開(kāi)始真的是成功的一半。