第2版人工智能通識教程第13章周蘇教授QQ：81505050群體智能導讀案例：無人機最快圈速：算法控制戰勝專業駕駛員基于蘇黎世大學研究人員開發了一種新算法，讓自主飛行的四旋翼飛行器計算出充分考慮無人機局限性的時間最優軌跡，并首次在無人機競賽中戰勝兩名人類駕駛員。01向蜜蜂學習群體智能02什么是群體智能03典型算法模型04群體智能背后的故事目錄/CONTENTS05群體智能的應用06群體智能的發展對群體智能（又稱群集智能）的研究源于對螞蟻、蜜蜂等社會性昆蟲群體行為的研究，最早被用在細胞機器人系統的描述中。群體具有自組織性，它的控制是分布式的，不存在中心控制。群體智能的算法主要有智能蟻群算法和粒子群算法。智能蟻群算法包括蟻群優化算法、蟻群聚類算法和多機器人協同合作系統。蟻群優化算法和粒子群優化算法在求解實際問題時應用最為廣泛。第13章群體智能PART01向蜜蜂學習群體智能蜜蜂是自然界中被研究的時間最長的群體智能動物之一。蜜蜂在進化過程中首先形成了大腦以處理信息，但是在某種程度上它們的大腦不能太大，這大概因為它們是飛行動物，腦袋小能夠減輕飛行負擔。事實上，蜜蜂的大腦比一粒沙子還要小，其中只有不到一百萬個神經元。相比之下，人類大約有850億個神經元。不管你有多聰明，把它除以85000，這就是一只蜜蜂的智慧。13.1向蜜蜂學習群體智能所以，一只蜜蜂是一個非常非常簡單的有機體，但它們也有非常困難的問題需要解決，這也是關于蜜蜂被研究最多的一個問題——選擇筑巢地點。通常一個蜂巢內有1萬只蜜蜂，并且隨著蜜蜂數量的壯大，它們每年都需要一個新家。它們的筑巢地點可能是空樹干里面的一個洞，也可能在建筑物某一側。因此，蜜蜂群體需要找到合適的筑巢地點。這聽起來好像很簡單，但對于蜜蜂來說，這是一個關乎蜂群生死的決定。它們選擇的筑巢地點越好，對物種生存就會越有利。13.1向蜜蜂學習群體智能為了解決這個問題，蜜蜂形成了蜂群思維，或者說群體智能，而第一步就是它們需要關于周圍世界的信息。因此，蜂群會先派出數百只偵察蜜蜂到外面約78平方千米的地方進行搜索，尋找它們可以筑巢的潛在地點，這是數據收集階段。圖13-5一群蜜蜂聚集在一棵樹上，偵察蜂外出尋找新巢址13.1向蜜蜂學習群體智能然后，這些偵察蜜蜂把信息帶回蜂群，接下來，就是最困難的部分：它們要做出決定，在找到的幾十個潛在地點中挑選出最好的。蜜蜂們非常挑剔，它們需要找到一個能滿足一系列條件的新住所。新房子必須足夠大，可以儲存冬天所需的蜂蜜；通風要足夠好，這樣在夏天能保持涼爽；需要能夠隔熱，以便在寒冷的夜晚保持溫暖；需要保護蜜蜂不受雨水的影響，但也需要有充足水源。當然，還需要有良好的地理位置，接近好的花粉來源。13.1向蜜蜂學習群體智能這是一個復雜多變量問題。事實上，研究這些數據的人會發現，人類尋找這個多變量優化問題的最佳解決方案都是非常困難的。換成類似具有挑戰性的人類的問題，比如為新工廠選取廠址，或者為開設新店選取完美的店址，或者定義新產品的完美特性，這些問題都很難找到一個十全十美的解決方案。然而，生物學家的研究表明，蜜蜂常常能夠從所有可用的選項中選出最佳的解決方案，或者選擇第二好的解決方案。這是很了不起的。事實上，通過群體智能一起工作，蜜蜂能夠作出一個優化的決定，而比蜜蜂大腦強大85000倍的人腦，卻很難做到這一點。13.1向蜜蜂學習群體智能那么蜜蜂們是怎么做到的呢？它們形成了一個實時系統，在這個系統中，它們可以一起處理數據，并在最優解上匯聚在一起。這是大自然的造化，蜜蜂想出了絕妙的辦法，它們通過振動身體來處理數據，實現這一過程，生物學家把這叫做“搖擺舞”。生物學家剛開始研究蜂巢的時候，他們看到這些蜜蜂在做一些看起來像是在跳舞的事情，它們振動自己的身體，這些振動所產生的信號代表它們是否支持某個特定的筑巢地點。成百上千的蜜蜂同時振動它們的身體時，基本上就是一個多維的選擇問題。13.1向蜜蜂學習群體智能它們揣度每個決定，探索所有不同的選擇，直到在某個解決方案中能夠達成一致，而這幾乎總是最優或者次優的解決方案，并且能夠解決單個大腦無法解決的問題。這是關于群體智能最著名的例子，我們也看到同樣的過程發生在鳥群或者魚群中，它們的群體智能大于個體。13.1向蜜蜂學習群體智能利用這一方式，我們來考慮一大群游客在曼哈頓找一家優質酒店。假設大部分游客都年老體弱，無法長途行走。首先，在中央公園的演奏臺建立一個臨時基地，接著，派出體力最好的成員到處巡查，隨后他們回到演奏臺并互相比較筆記。聽到有更好的酒店選擇時，他們再次前往實地考察。最后，大家達成共識，所有人再集體前往目標酒店辦理入住。13.1向蜜蜂學習群體智能曼哈頓的街道有兩種命名方式，街常為東西走向，而道常為南北走向，所以偵察兵回來的時候，只需要說明該酒店最接近哪條街哪條道，大家就可以明白。任何時間，偵察兵的定位都可以用兩個數字來表示：街和大道。如果用數學語言表示，就是X和Y。假如需要的話，我們還可以在演奏臺準備一張坐標紙，追蹤每一個偵察兵的行走路線，以此定位酒店位置。偵察兵在曼哈頓街道上尋找最佳酒店就如同在XY坐標軸上尋找最優值一樣。13.1向蜜蜂學習群體智能所謂集群機器人或者人工蜂群智能，就是讓許多簡單的物理機器人協作。就像昆蟲群體一樣，機器人會根據集群行為行動，它們會在環境中導航，與其他機器人溝通。與分散機器人系統不同，集群機器人會用到大量的機器人個體，它是一個靈活的系統。拉迪卡·納格帕爾領導的團隊以及其他許多科研機構都在研究這門技術。此技術未來獲得成功，集群機器人會展示出巨大的潛力，影響醫療保健、軍事等行業。機器人越來越小，未來我們也許可以讓大量納米機器人以群蜂的形式協調工作，在微機械、人體內執行任務。13.1向蜜蜂學習群體智能PART02什么是群體智能群體智能的概念來自對自然界中一些社會性昆蟲，如螞蟻、蜜蜂等的群體行為的研究。單只螞蟻的智能并不高，它看起來不過是一段長著腿的神經節而已。不過，幾只螞蟻湊到一起，就可以一起往蟻穴搬運路上遇到的食物。如果是一群螞蟻，它們就能協同工作，建起堅固、漂亮的巢穴，一起抵御危險，撫養后代。社會動物以一個統一的動態集體工作時，其群體涌現出的解決問題和做出決策的智慧會超越大多數單獨成員，如蟻群搭橋、鳥群覓食、蜂群筑巢等，這一過程在生物學上被稱為“群體智能”。13.2什么是群體智能人類可以形成群體智能嗎？人類并沒有進化出群集的能力，因為人類缺少同類用于建立實時反饋循環的敏銳連接（比如螞蟻的觸角），這種連接是高度相關的，被認為是一個“超級器官”。通過這么做，這些生物能夠進行最優選擇，這要遠比獨立個體的選擇能力要強得多。13.2什么是群體智能在某個群體中，若存在眾多無智能的個體，它們通過相互之間的簡單合作所表現出來的群居性生物的智能行為是分布式控制的，具有自組織性。“群體智能”作為計算機專業術語最早是在1989年由赫拉多等提出的，用來描述電腦屏幕上細胞機器人的自組織算法所具有的分布控制、去中心化的智能行為。早期學者主要專注于群體行為特征規律的研究，并提出了一系列具有群體智能特征的算法，如蟻群優化算法在解決“旅行商問題”等數學難題上得到了較好的應用。13.2.1群體人工智能技術如今，人類群體、大數據、物聯網已經實現了廣泛和深度的互聯，群體智能的發展方向逐漸轉移到人、機、物融合的方向上來。在具體實現上，智能計算模式逐漸從“以機器為中心”的模式走向“群體計算回路”，智能系統開發也從封閉和計劃走向了開放和競爭。13.2.1群體人工智能技術人類可以做到把個人的思考組合起來，讓它們形成一個統一的動態系統，以做出更好的決策、預測、評估和判斷。人類群集已經被證明在預測體育賽事結果、金融趨勢甚至是奧斯卡獎得主這些事件上的準確率超過了個體專家。例如，群體人工智能技術能讓群體組成實時的線上系統，把世界各地的人作為“人類群集”連接起來，這是一個人類實時輸入和眾多AI算法的結合。群體人工智能結合人類參與者的知識、智慧、硬件和直覺，并把這些要素組合成一個統一的新智能，能生成最優的預測、決策、洞見和判斷。13.2.1群體人工智能技術依賴于每個格子單元（細胞）的幾條簡單運動規則，可以使細胞集合的運動表現出超常的智能行為。群體智能不是簡單的多個體的集合，而是超越個體行為的一種更高級表現，這種從個體行為到群體行為的演變過程往往極其復雜，以至于往往無法預測。13.2.1群體人工智能技術群體智能有兩種機制：（1）自上而下有組織的群體智能行為。這種機制會形成一種分層有序的組織架構。自上而下的群體智能形成機制是在問題可分解的情況下，不同個體之間通過蜂群算法集成進行合作，進而達到高效解決復雜問題的機制。美國美國國防部高級研究計劃局正在開展的“進攻性蜂群戰術”（OFFSET）項目，就是通過自上而下的群體智能機制將群體智能推向實戰化水平。德國國防軍也運用自上而下的群體智能機制開發無人機蜂群戰術級人工智能快速決策系統。13.2.2群體智能的兩種機制（2）自下而上自組織的群體智能涌現。這種機制可使群體涌現出個體不具有的新屬性，而這種新屬性正是個體之間綜合作用的結果。美國科技作家凱文·凱利在《失控：全人類的最終命運和結局》中提到：“一種由無數默默無聞的零件，通過永不停歇的工作，而形成的緩慢而寬廣的創造力”，這就是群體智能涌現的過程。例如由多個簡單機器人組成的群體機器人系統，通過“分布自組織”的協作，可以完成單個機器人無法完成或難以完成的工作。13.2.2群體智能的兩種機制基于群體智能的技術可用于許多應用程序。各國正在研究用于控制無人駕駛車輛的群體技術，歐洲航天局正在考慮用于自組裝和干涉測量的軌道群，美國宇航局正在研究使用群體技術進行行星測繪等。安東尼·劉易斯和喬治·貝基1992年撰寫的論文中，討論了使用群體智能來控制體內納米機器人，以殺死癌癥腫瘤的可能性。相反，里菲和阿伯使用隨機擴散搜索來幫助定位腫瘤。群體智能也已應用于數據挖掘等領域，例如DoRoO等人和惠普在20世紀90年代中期以來研究了基于螞蟻的路由算法在電信網絡中的應用。13.2.3基本原則與特點米洛納斯（1994年）提出了群體智能應該遵循的五條基本原則，分別為：（1）鄰近原則，群體能夠進行簡單的空間和時間計算；（2）品質原則，群體能夠響應環境中的品質因子；（3）多樣性反應原則，群體的行動范圍不應該太窄；（4）穩定性原則，群體不應在每次環境變化時都改變自身的行為；（5）適應性原則，在所需代價不太高的情況下，群體能夠在適當的時候改變自身的行為。13.2.3基本原則與特點這些原則說明實現群體智能的智能主體必須能夠在環境中表現出自主性、反應性、學習性和自適應性等智能特性。但是，這并不代表群體中的每個個體都相當復雜，恰恰相反，就像單只螞蟻智能不高一樣，組成群體的每個個體都只具有簡單智能，它們通過相互之間的合作表現出復雜的智能行為。13.2.3基本原則與特點可以這樣說，群體智能的核心是由眾多簡單個體組成的群體，能夠通過相互之間的簡單合作來實現某一功能，完成某一任務。其中，“簡單個體”是指單個個體只具有簡單的能力或智能，而“簡單合作”是指個體和與其鄰近的個體進行某種簡單的直接通信或通過改變環境間接與其他個體通信，從而可以相互影響、協同動作。13.2.3基本原則與特點群體智能具有以下特點：（1）控制是分布式的，不存在中心控制。因而它更能夠適應當前網絡環境下的工作狀態，并且具有較強的魯棒性，即不會由于某一個或幾個個體出現故障而影響群體對整個問題的求解。（2）群體中的每個個體都能夠改變環境，這是個體之間間接通信的一種方式，被稱為“激發工作”。由于群體智能可以通過非直接通信的方式進行信息的傳輸與合作，因而隨著個體數目的增加，通信開銷的增幅較小，因此，它具有較好的可擴充性。13.2.3基本原則與特點（3）群體中每個個體的能力或遵循的行為規則非常簡單，因而群體智能具有簡單性特點。（4）群體表現出的復雜行為是通過簡單個體交互過程突現出來的智能，群體具有自組織性。13.2.3基本原則與特點PART03典型算法模型群體智能算法可以分成兩個方面：對生物進行模擬的群體智能和對非生物（煙花、磁鐵、頭腦風暴等）進行模擬的群體智能，針對群體智能的研究已經取得了許多重要的結果。1991年意大利學者多里戈提出蟻群優化理論，1995年，肯尼迪等學者提出粒子群優化算法，此后群體智能研究迅速展開。蟻群優化（ACO）和粒子群優化（PSO）是兩種最廣為人知的“群體智能”算法。從基礎層面上來看，這些算法都使用了多智能體。每個智能體執行非常基礎的動作，合起來就是更復雜、更即時的動作，可用于解決問題。蟻群優化與粒子群優化這二者的目的都是執行即時動作，但采用的方式不同。13.3典型算法模型蟻群優化與真實蟻群類似，利用信息激素指導單個智能體走最短的路徑。最初，隨機信息激素在問題空間中初始化，單個智能體開始遍歷搜索空間，邊走邊灑下信息激素。信息激素在每個時間步中按一定速率衰減。單個智能體根據前方的信息激素強度決定遍歷搜索空間的路徑。某個方向的信息激素強度越大，智能體越可能朝這個方向前進。全局最優方案就是具備最強信息激素的路徑。13.3典型算法模型粒子群優化更關注整體方向。多個智能體初始化，并按隨機方向前進。每個時間步中，每個智能體都需要就是否改變方向作出決策，決策基于全局最優解的方向、局部最優解的方向和當前方向。新方向通常是以上三個值的最優“權衡”結果。13.3典型算法模型螞蟻生活在一個十分高效并且秩序井然的群體之中，它們幾乎總是以最高效的姿態來完成每件事。它們修建蟻巢來保證最佳溫度和空氣流通；它們確定食物位置后能夠確定最佳路徑，并以最快的速度趕到。有人可能會認為這是由于某些中央權力中心，比如蟻后，在管控它們的所有行動。事實上，這樣的權力中心并不存在，蟻后不過是產卵的“機器”而已，每一只螞蟻都是自主的獨立個體。13.3.1蟻群算法螞蟻在尋找食物時，一開始會漫無目的地到處走動，直到發現另一只螞蟻帶著食物返回巢穴時留下的信息素蹤跡，然后，它就開始沿著蹤跡行走。信息素越強，追蹤的可能性越大。在找到食物后它將返回巢穴，留下自己的蹤跡。如果該地還有大量食物，許多螞蟻也會按照該路徑來回往復，蹤跡將變得越來越鮮明，對路過的螞蟻的吸引力也會越來越大。不過，偶爾會有一些螞蟻因為找不到蹤跡而選擇了不同的路徑。如果新路徑更短，那么大量的螞蟻將在這條蹤跡上留下越來越多的信息素，舊路徑上的信息素就將逐漸蒸發。隨著時間的流逝，螞蟻們選擇的路徑會越來越接近最佳路徑。13.3.1蟻群算法蟻群能夠搭建身體浮橋跨越缺口地形并不是偶然事件。一個蟻群可能在同時搭建超過50只螞蟻組成的橋梁，每個橋梁從1只螞蟻到50只螞蟻不等。螞蟻不僅可以建造橋梁，而且能夠有效評估橋梁的成本和效率之間的平衡，比如在V字形道路上，蟻群會自動調整到合適的位置建造橋梁，既不是靠近V頂點部分，也不是V開口最大的部分。圖13-7螞蟻建造橋梁13.3.1蟻群算法生物學家對蟻群橋梁研究的算法表明，每只螞蟻并不知道橋梁的整體形狀，它們只是在遵循兩個基本原則：（1）如果我身上有其他螞蟻經過，那么我就保持不動；（2）如果我身上螞蟻經過的頻率低于某個閾值，我就加入行軍，不再充當橋梁。13.3.1蟻群算法數十只螞蟻可以一起組成“木”筏渡過水面。當蟻群遷徙的時候，整個木筏可能包含數萬只或更多螞蟻。每只螞蟻都不知道木筏的整體形狀，也不知道木筏將要漂流的方向。但螞蟻之間非常巧妙的互相連接，形成一種透氣不透水的三維立體結構，即使完全沉在水里的底部螞蟻也能生存。而這種結構也使整個木筏包含超過75%空氣體積，所以能夠順利的漂浮在水面。13.3.1蟻群算法蟻群在地面形成非常復雜的尋找食物和搬運食物的路線，似乎整個集體總是能夠找到最短的搬運路線，然而每只螞蟻并不知道這種智能是如何形成的。用樟腦丸在螞蟻經過的路線上涂抹會導致螞蟻迷路，這是因為樟腦的強烈氣味嚴重干擾了螞蟻生物信息素的識別。13.3.1蟻群算法蟻群具有復雜的等級結構，蟻后可以通過特殊的信息素影響到其他螞蟻，甚至能夠調節其他螞蟻的生育繁殖。但蟻后并不會對工蟻下達任何具體任務，每個螞蟻都是一個自主的單位，它的行為完全取決于對周邊環境的感知和自身的遺傳編碼規則。盡管缺乏集中決策，但蟻群仍能表現出很高的智能水平，這種智能就稱為分布式智能。13.3.1蟻群算法不僅螞蟻，幾乎所有膜翅目昆蟲都表現出很強的群體智能行為，另一個知名的例子就是蜂群。蟻群和蜂群被廣泛的認為是具有真社會化屬性的生物種群，這是指它們具有以下三個特征：（1）繁殖分工。種群內分為能夠繁殖后代的單位和無生育能力的單位，前者一般為女王和王，后者一般為工蜂、工蟻等。（2）世代重疊。即上一代和下一代共同生活，這也決定了下一個特征。（3）協作養育。種群單位共同協作養育后代。這個真社會化屬性和人類的社會化屬性并不是同一概念。13.3.1蟻群算法受到自然界中螞蟻群的社會性行為的啟發，由M.多里戈等人于1991年首先提出了蟻群算法，它模擬了實際蟻群尋找食物的過程。科學家們創建了蟻群優化（AOC）算法。13.3.1蟻群算法我們可以利用群體智能來設計一組機器人，每個機器人本身配置十分簡單，僅需要了解自身所處的局部環境，通常也只與附近的其他機器人進行溝通。每個設備都是自主運行的，不需要中央智能來發布指令，就像我們在包容體系結構時說到的機器人一樣，每個獨立個體只知道自己對世界的感知，這可以幫助建立強大穩固的行為，可以自主適應環境的變化。在擁有大量編程一致的同款機器人之后，就可以實現更大的彈性，因為一小部分個體的操作失誤并不會對整體的效能產生大的影響。13.3.1蟻群算法這類與螞蟻行為十分相似的機器人可以用于查找并移除地雷，或是在災區搜尋傷亡人員。螞蟻利用信息素來給巢穴內的其他成員留下信號，但感知信息素對機器人來說并不容易（雖然已經可以實現），機器人利用的是燈光、聲響或是短程無線電。目前，蟻群算法已在組合優化問題求解，以及電力、通信、化工、交通、機器人、冶金等多個領域中得到應用，都表現出了令人滿意的性能。13.3.1蟻群算法想象一下在遠足登山區有大量機器人的場景。在沒有其他事情要做的時候，它們就會站在視野范圍內其他機器人的中間位置，這也意味著可以做到在該區域內均勻分布。它們能夠注意到嘈雜的噪聲及揮動的手勢，所以遇到困難的背包客就可以向它們尋求幫助。13.3.2搜索機器人如果有需要緊急服務的請求，則可以從一個機器人傳遞到另一個機器人，直到傳遞到能接收無線電或手機信號的機器人那里。假如需要運送受傷的背包客，更多的機器人也可以前來提供幫助，其他機器人則將移動位置來保證區域覆蓋度。比起包容體系結構，所有這些操作都可以在機器人數量更少的情況下完成。13.3.2搜索機器人換一種方式，我們考慮利用一組四軸飛行器來保證背包客的安全。這些飛行器將以集群的方式在特定區域內巡查，尤其關注背包客們常穿的亮橙色。在某些難以察覺的地方可能有人受傷，一旦有飛行器注意到了那抹橙色就會立刻轉向該地點。飛行器在背包客頭頂盤旋時，每一架都會以稍稍不同的有利位置進行觀察，慢慢地，越來越多的飛行器就會發現傷員。很快，整個飛行器集群就將在某地低空盤旋，也就意味著它們已經成功確定了可能的事故地點。這時就需要利用到其他人工智能技術，比如，自然語言理解、手勢識別和圖像識別，但很明顯，這些如今都不是什么棘手的問題。13.3.2搜索機器人另一類經常被模仿的群體行為是鳥類的群集。當整個群體需要集體移動但又需要尋找特定目標時，就可以利用這種技術，而創建個體集群的規則十分簡單。13.3.3微粒群（鳥群）優化算法（1）跟緊群體內其他成員。（2）以周邊成員的平均方向作為飛行方向。（3）與其他成員和障礙物保持安全距離。如果我們設置向某個目標偏轉的趨勢，整個集群都將根據趨勢行進。13.3.3微粒群（鳥群）優化算法鳥類在群體飛行中往往能表現出一種智能的簇擁協同行為，尤其是在長途遷徙過程中，以特定的形狀組隊飛行可以充分利用互相產生的氣流，從而減少體力消耗。常見的簇擁鳥群是遷徙的大雁，它們數量不多，往往排成一字型或者人字形，據科學估計，這種隊形可以讓大雁減少15~20%的體力消耗。體型較小的歐椋鳥組成的鳥群的飛行則更富于變化，它們往往成千上萬只一起在空中飛行，呈現出非常柔美的群體造型。13.3.3微粒群（鳥群）優化算法基于三個簡單規則，鳥群就可以創建出極復雜的交互和運動方式，形成奇特的整體形狀，繞過障礙和躲避獵食者：（1）分離，和臨近單位保持距離，避免擁擠碰撞（2）對齊，調整飛行方向，順著周邊單位的平均方向飛行（3）凝聚，調整飛行速度，保持在周邊單位的中間位置鳥群沒有中央控制，實際上每只鳥都是獨立自主的，只考慮其周邊球形空間內的5~10只鳥的情況。13.3.3微粒群（鳥群）優化算法魚群的群體行為和鳥群非常相似。金槍魚、鯡魚、沙丁魚等很多魚類都成群游行，這些魚總是傾向于加入數量大的、體型大小與自身更相似的魚群，所以有的魚群并不是完全由同一種魚組成。群體游行不僅可以更有效利用水動力減少成員個體消耗，而且更有利于覓食和生殖，以及躲避捕食者的獵殺。魚群中的絕大多數成員都不知道自己正在游向哪里。魚群使用共識決策機制，個體的決策會不斷地參照周邊個體的行為進行調整，從而形成集體方向。13.3.3微粒群（鳥群）優化算法在哺乳動物中也常見群體行為，尤其是陸上的牛、羊、鹿，或者南極的企鵝。遷徙和逃脫獵殺時候，它們能表現出很強的集體意志。研究表明，畜群的整體行為很大程度上取決于個體的模仿和跟風行為，而遇到危險的時候，則是個體的自私動機決定了整體的行為方向。13.3.3微粒群（鳥群）優化算法細菌和植物也能夠以特殊的方式表現出群體智能行為。培養皿中的枯草芽孢桿菌根據營養組合物和培養基的粘度，整個群體從中間向四周有規律的擴散遷移，形成隨機但非常有規律的數值型狀態。而植物的根系作為一個集體，各個根尖之間存在某種通信，遵循范圍最大化且互相保持間隔的規律生長，進而能夠最有效的利用空間吸收土壤中的養分。13.3.3微粒群（鳥群）優化算法粒群優化算法最早是由肯尼迪和埃伯哈特于1995年提出的，是一種基于種群尋優的啟發式搜索算法，其基本概念源于對鳥群群體運動行為的研究。在微粒群優化算法中，每個微粒代表待求解問題的一個潛在解，它相當于搜索空間中的一只鳥，其“飛行信息”包括位置和速度兩個狀態量。每個微粒都可獲得其鄰域內其他微粒個體的信息，并可根據該信息以及簡單的位置和速度更新規則，改變自身的狀態量，以便更好地適應環境。隨著這一過程的進行，微粒群最終能夠找到問題的近似最優解。13.3.3微粒群（鳥群）優化算法由于微粒群優化算法概念簡單，易于實現，并且具有較好的尋優特性，因此它在短期內得到迅速發展，目前已在許多領域中得到應用，如電力系統優化、TSP問題求解、神經網絡訓練、交通事故探測、參數辨識、模型優化等。奧斯卡技術獎的獲得者，計算機圖形學家克雷格·雷諾茲在1986年開發了Boids鳥群算法，這種算法僅僅依賴分離、對齊、凝聚三個簡單規則就實現各種動物群體行為的模擬。13.3.3微粒群（鳥群）優化算法在討論遺傳算法時，我們用一組稱作“基因”的數字來代表群體中的每個獨立個體，通過改變這些數字直到它們能夠代表最優個體為止。就同樣的數字而言，利用群體智能技術，我們不再將它們看做染色體上的基因，而是看做圖表或地圖等空間上的位置。隨著每個獨立個體空間位置的變化，數字相應地發生改變，就像你走在曼哈頓大街上，代表你所在位置的街道數字發生改變一樣。我們的搜索不再是固定個體的進化過程，而是不同個體的旅程。可以使用任何用來搜索位置的技術，例如螞蟻覓食、蜜蜂群集或是鳥類聚集，而完全不用建造任何機器人。13.3.4沒有機器人的集群PART04群體智能背后的故事在公園我們經常看到成群的鳥兒在樹木上空飛旋，它們遲早會落在建筑的突出物上休息，之后在受了什么驚擾后又動作一致地再度起飛。13.4群體智能背后的故事這群鳥中并沒有領導，沒有一只鳥兒會指示其他鳥兒該做什么，相反，它們各自密切注意身邊的同伴。在空中飛旋時，全都遵循簡單規則，這些規則構成了另一種群體智能，它與決策的關系不大，主要是用來精確協調行動。研究計算機制圖的克雷格·雷諾茲對這些規則感到好奇，他在1986年設計了一個看似簡單的導向程序，叫做“擬鳥”。13.4群體智能背后的故事在這個模擬程序中，一種模仿鳥類的物體（擬鳥）接收到三項指示：（1）避免擠到附近的擬鳥；（2）按附近擬鳥的平均走向飛行；（3）跟緊附近的擬鳥。13.4群體智能背后的故事程序運行結果呈現在電腦屏幕上時，模擬出令人信服的鳥群飛舞效果，包括逼真的、無法預測的運動。當時，雷諾茲正在尋求能在電視和電影中制造逼真動物特效的辦法。1992年的《蝙蝠俠歸來》是第一部利用他的技術制作的電影，其中模擬生成了成群的蝙蝠和企鵝。后來他在索尼公司從事電子游戲領域的研究，例如用一套算法實時模擬數量達1.5萬的互動的鳥、魚或人。雷諾茲展示了自組織模型在模仿群體行為方面的力量，這也為機器人工程師開辟了新路。如果能讓一隊機器人像一群鳥般協調行動，就比單獨的機器人有優勢得多。13.4群體智能背后的故事賓夕法尼亞大學的機械工程教授維賈伊·庫馬爾說：“觀察生物界中數目龐大的群體，很難發現其中哪一個承擔中心角色。一切都是高度分散的：成員并不都參與交流，根據本地信息采取行動；它們都是無名的，不必在乎誰去完成任務，只要有人完成就行。要從單個機器人發展到多個機器人合作，這三個思路必不可少。”13.4群體智能背后的故事據野生動物專家卡斯滕·霍耶爾在2003年的觀察，陸地動物的群體行為也與魚群相似。那年，他和妻子利恩·阿利森跟著一大群北美馴鹿旅行了五個月，行程超過1500公里，記錄了它們的遷徙過程。遷徙從加拿大北部育空地區的冬季活動范圍起始，到美國阿拉斯加州北極國家野生動物保護區的產犢地結束。13.4群體智能背后的故事卡斯滕說：“這很難用語言形容。鹿群移動時就像云影漫過大地，或者一大片多米諾骨牌同時倒下并改變著方向。好像每頭鹿都知道它周邊的同伴要做什么。這不是出于預計或回應，也沒有因果關系，它們自然而然就這樣行動。”13.4群體智能背后的故事一天，正當鹿群收窄隊形、穿過森林邊界線上的一條溪谷時，卡斯滕和利恩看見一只狼偷襲過去。鹿群做出了經典的群體防御反應。卡斯滕說：“那只狼一進入鹿群外圍的某一特定距離，鹿群就驟然提高了警惕。這時每頭鹿都停下不動，完全處于戒備狀態，四下張望。”狼又向前走了100米，突破了下一個限度。“離狼最近的那頭鹿轉身就跑，這反應就像波浪一樣掃過整個鹿群，于是所有的鹿都跑了起來。13.4群體智能背后的故事之后逃生行動進入另一階段。鹿群后端與狼最接近的那一小群馴鹿就像條毯子般裂開，散成碎片，這在狼看來一定是極度費解的。”狼一會兒追這頭鹿，一會兒又追那頭，每換一次追擊目標都會被甩得更遠。最后，鹿群翻過山嶺，脫逃而去，而狼留在那兒氣喘吁吁，大口吞著雪。每頭馴鹿本來都面臨著絕大的危險，但鹿群的躲避行動所表現的卻不是恐慌，而是精準。每頭馴鹿都知道該什么時候跑、跑往哪個方向，即便不知道為什么要這樣做。沒有領袖負責鹿群的協調，每頭鹿都只是在遵循著幾千年來應對惡狼襲擊而演化出來的簡單規則。13.4群體智能背后的故事這就是群體智能的美妙魅力。無論我們討論的是螞蟻、蜜蜂、鴿子、還是北美馴鹿，智慧群體的組成要素——分散控制、針對本地信息行動、簡單的經驗法則——加在一起，就構成了一套應對復雜情況的精明策略。13.4群體智能背后的故事最大的變化可能體現在互聯網上。谷歌利用群體智能來查找你的搜索內容。當你鍵入一條搜索時，谷歌會在它的索引服務器上考查數十億網頁，找出最相關的，然后按照它們被其他網頁鏈接的次數進行排序，把鏈接當作投票來計數（最熱門的網站還有加權票數，因為它們可靠性更高）。得到最多票數的網頁被排在搜索結果列表的最前面。谷歌說，它通過這種方式，“利用網絡的群體智能來決定一個網頁的重要性”。13.4群體智能背后的故事網絡百科（維基、百度等）是一類免費的合作性百科全書，辦得十分成功，其中有200多種語言寫成的數以百萬計的文章，世間萬物無不涉及，每一詞條均可由任何人撰寫、編輯。麻省理工學院集體智能中心的托馬斯·馬隆說：“如今可以讓數目龐大的人群以全新的方式共同思考，這在幾十年前我們連想都想不到。要解決我們全社會面臨的問題，如醫療保健或氣候變化，沒有一個人的知識是夠用的。但作為集體，我們的知識量遠比迄今為止我們所能利用的多得多。”13.4群體智能背后的故事這種想法突出反映了關于群體智能的一個重要真理：人群只有在每個成員做事盡責、自主決斷的時候，才會發揮出智慧。群體內的成員如果互相模仿，盲從于潮流，或等著別人告訴自己該做什么，這個群體就不會很聰明。若要一個群體擁有智慧，無論它是由螞蟻還是律師組成，都得依靠成員們各盡其力。我們有些人往往懷疑，值不值得把那只多余的瓶子拿去回收，來減輕我們對地球的壓力。而事實是：我們的一舉一動都事關重大，即使我們看不出其中玄機。13.4群體智能背后的故事蜜蜂專家托馬斯·西利說：“蜜蜂跟你我一樣，從來看不到多少全局。我們誰都不知道社會作為一個總體需要什么，但我們會看看周圍，說，哦，他們需要人在學校當義工，給社區修剪草坪，或者在政治宣傳活動中幫忙。”假如你要在一個充滿復雜性的世界中尋找行為榜樣，不妨去仿效蜜蜂吧。13.4群體智能背后的故事PART05群體智能的應用目前國外對群體智能的應用側重于底層技術領域，如集群結構框架、集群控制與優化、集群任務管理與協同等，國內則主要側重于應用領域，如集群路徑實時規劃、集群自主編隊與重構、集群智能協同決策等。隨著群體智能在現實場景的深入應用，將有力促進產業智能化和提高產業競爭力。另外，群體智能也正在深刻影響著軍事領域，使戰爭形態加速向智能化演變，與之相應的戰爭觀也發生了嬗變。13.5群體智能的應用（1）蜂群協同系統。美國的“進攻性蜂群戰術”（OFFSET）項目探索未來的小單位步兵部隊將是由小型無人機系統（UASs）或小型無人地面車輛系統（UGSs）組成的“蜂群”，可在復雜的環境中完成多種任務。相關研究成果也將直接應用到“馬賽克戰”體系中，推動低成本無人蜂群作戰能力的快速成形。圖13-15OFFSET項目13.5群體智能的應用（2）路徑規劃系統。群體智能支撐的路徑規劃技術被廣泛應用于各種運動規劃任務，極大地解決了多智能體間的群體協同決策問題，如自動駕駛、車路協同、群體機器人等場景。各國政府都制定政策，著重強調群體協同決策在交通安全中的重要性。圖13-16奧迪的群體智能示例13.5群體智能的應用（3）復雜電磁環境下的優化與控制。電磁頻譜已作為第六維作戰疆域引起世界各國的高度重視。2015年，美軍發布的《關于國家安全的突破性技術》戰略指南中明確指出“未來幾年的研究重點將是確保控制電磁權”。2018年，美國空軍組建了電子戰/電磁頻譜優勢體系能力協作小組（ECCT），旨在研究如何確保電磁頻譜優勢，開始實質性推進電磁頻譜戰。13.5群體智能的應用群體智能有“自組織、自適應”的技術特點，在電磁頻譜戰中的頻譜狀態感知、頻譜趨勢預測、頻譜形式推理上具有獨特的先天優勢，可以有效應對戰場電磁環境的捷變性，提高戰爭中信息傳輸時效性，促進電磁頻譜戰的決策智能化。

圖13-17電磁頻譜戰協同13.5群體智能的應用PART06群體智能的發展作為新一代人工智能的重要方向，自20世紀80年代提出以來，群體智能已成為信息、生物、社會等交叉學科的熱點和前沿領域。2017年7月8日，中國國務院印發了《新一代人工智能發展規劃》（簡稱《AI發展規劃》），明確指出了群體智能的研究方向，對于推動新一代人工智能發展有著十分重大的意義。國家科學技術部啟動的《科技創新2030“新一代人工智能”重大項目指南》中，也將“群體智能”列為人工智能領域的五大持續攻關方向之一。可見，對于群體智能的探究具有重要的現實意義。13.6群體智能的發展群體智能作為新一代人工智能重點發展的五大智能形態（即大數據智能、群體智能、跨媒體智能、混合增強智能和自主智能）之一，在民事和軍事領域都具有重要的應用前景。5G時代所帶來的萬物互聯，為群體智能的應用和創新提供了豐富的場景，將會進一步促進人、機、物的深度融合，也會進一步推動群體智能理論和技術的持續發展。目前，群體智能在基礎理論和作用機理創新、群體智能知識表示框架構建和關鍵技術應用上還處于初級階段，有廣闊的應用和發展空間。未來，我國應推動群體智能基礎理論研究與系統開發齊頭并進，不斷拓寬應用場景，早日形成群體智能技術的標準體系。13.6群體智能的發展比如基于群體開發的開源軟件、基于眾籌眾智的萬眾創新、基于眾問眾答的知識共享、基于群體編輯的維基百科、以及基于眾包眾享的共享經濟等等，這些趨勢昭示著人工智能已經進入了新的發展階段，新的研究方向以及新范式已經開始逐漸顯現，從強調專家的個人智能模擬走向群體智能，智能的構造方法從邏輯和單調走向開放和涌現，智能計算模式從“以機器為中心”走向“群體在計算回路”，智能系統開發方法從封閉和計劃走向開放和競爭。所以，我們必須要依托良性的互聯網科技創新生態環境實現跨時空的匯聚群體智能，高效的重組群體智能，更廣泛且準確地釋放群體智能。13.6群體智能的發展第2版人工智能通識教程第14章周蘇教授QQ：81505050自動規劃導讀案例：自動駕駛泊車技術自動泊車系統可以大大簡化泊車過程，特別是在極端狹窄的地方，或者是對于新手而言，自動泊車系統可以帶來更加智能和便捷的體驗。01規劃的概念02人工智能的烏姆普思世界03什么是自動規劃04規劃方法目錄/CONTENTS05時間、調度和資源規劃一系列動作是人工智能技術中智能體的關鍵需求，而正確表示的動作和狀態以及正確的算法可以使規劃變得更容易。自動規劃是一種重要的問題求解技術。與一般問題求解相比，自動規劃更注重于問題的求解過程，而不是求解結果。此外，規劃要解決的問題，如機器人世界問題，往往具有真實性，而不是比較抽象的數學模型問題。與一些求解技術相比，自動規劃系統與專家系統均屬高級求解系統與技術。第14章自動規劃

圖14-2自動裝箱規劃第14章自動規劃PART01規劃的概念所謂規劃，是指個人或組織制定的比較全面長遠的發展計劃，是對未來整體性、長期性、基本性問題的考量，以設計未來的整套行動方案。規劃是融合多要素、多人士看法的某一特定領域的發展愿景，它代表了人類為實現目標而對活動進行調整的一種某種自我意識和能力。在日常生活中，規劃意味著在行動之前決定其進程，或者說，是在執行一個問題求解程序之前，計算該程序具體執行的過程。規劃可用來監控問題求解過程，并能夠在造成較大危害之前發現差錯。規劃的好處可歸納為簡化搜索、解決目標矛盾以及為差錯補償提供基礎。14.1規劃的概念規劃有兩個突出的特點，一是為了完成任務可能需要一系列確定的步驟；二是定義問題解決方案的步驟順序可能是有條件的。也就是說，構成規劃的步驟可能會根據條件進行修改（稱為條件規劃）。一個規劃是一個行動過程的描述，它雖然可以是像商品清單那樣的沒有次序的目標列表，但一般都具有某個目標的蘊含排序。例如，一個機器人要搬動某工件，必須先移動到該工件附近，抓住該工件，然后帶著工件移動。14.1規劃的概念大多數規劃都具有子規劃結構，具有分層結構的每個子目標由達到此目標的比較詳細的子規劃確定，最終得到的規劃是某個問題求解算符的線性或分步排序。14.1規劃的概念規劃的概念很多，具體可以整理成如下幾點：（1）從某個特定的問題狀態出發，尋求一系列行為動作并建立一個操作序列，直到求得目標狀態為止，這個求解過程就是規劃；（2）規劃是關于動作的推理，它是一種抽象但清晰的深思熟慮的過程，該過程通過預期動作的期望效果，選擇和組織一組動作，其目的是盡可能好地實現一個預先給定的目標；14.1規劃的概念（3）規劃是針對某個待求解問題給出求解過程的步驟，規劃設計如何將問題分解為若干相應的子問題，記錄和處理問題求解過程中發現的子問題間的關系；（4）規劃系統是一個涉及有關問題求解過程的步驟的系統。14.1規劃的概念把某些較復雜的問題分解為一些較小的子問題。有兩條實現這種分解的重要途徑。第一條是當從一個問題狀態移動到下一個狀態時，無需計算整個新的狀態，而只要考慮狀態中可能變化了的那些部分。第二條是把單一困難問題分割為幾個有希望較為容易解決的子問題。14.1規劃的概念PART02人工智能的烏姆普思世界這是一個簡單的世界示例。烏姆普思（Wumpus）世界是一個山洞，有4×4共16個房間，房間與通道相連，有一個商人（智能體）將在這個世界中移動。圖14-3烏姆普思世界14.2人工智能的烏姆普思世界山洞里的某一間屋子里有個叫烏姆普思的怪物，它會吃掉進屋的任何人。商人可以射殺烏姆普思，但他只有一枝箭。在烏姆普思世界中有一些深坑洞室（PIT），如果商人落在深坑中，會被永遠困在坑里。令人興奮的是，洞穴里有一個房間里有可能找到一大堆金子。因此，商人的目標是找到金子并爬出洞穴，而不會掉落坑中或被烏姆普思吞噬。如果商人帶金子出來，會得到獎勵；如果商人被烏姆普思吞下或掉進坑里，會受到懲罰。14.2人工智能的烏姆普思世界為解釋烏姆普思世界，對任務環境做如下描述。（1）性能指標：·如果商人帶著金子從烏姆普思世界中出來，可獲得1000點獎勵積分。·被烏姆普思吃掉或掉進坑里，點數為-1000分。·-1表示每個操作，-10表示使用箭。·如果商人死亡或從山洞出來，游戲就結束。14.2.1描述烏姆普思世界（2）環境：·4×4的房間網格。·商人最初位于房間正方形[1,1]中，朝向右側。·除了第一個正方形[1,1]以外，都是隨機選擇烏姆普思和金子的位置。·除第一個正方形以外，洞穴中每個正方形是坑室的概率為0.2。（3）執行器：左轉、右轉、前進、抓取、發布、射擊。14.2.1描述烏姆普思世界（4）傳感器：·如果商人進到與烏姆普思相鄰的房間（不是對角線的），會聞到惡臭。·如果商人進到與坑室相鄰的房間內，會感覺到微風。·商人能感知到放有金子的房間中的閃光。·商人走向墻壁會感覺到撞擊。·射殺烏姆普思時，它會發出可怕的尖叫聲，這在山洞的任何地方都可以感覺到。14.2.1描述烏姆普思世界·這些感知可以表示為五個元素列表。例如，如果商人聞到惡臭或者感到微風，但沒有閃光，沒有碰撞和尖叫聲，可以表示為：[惡臭,微風,無,無,無]。14.2.1描述烏姆普思世界（5）烏姆普思世界：·部分可觀察：因為商人只能感知附近的環境，例如相鄰的房間。·確定性的：因為世界的結果是已知的。·順序的：順序很重要。·靜態：烏姆普思和深坑不移動，是靜態的。·離散的：環境是離散的。·一個智能體（商人）：環境中只有一個智能體，烏姆普思不被視為智能體。14.2.1描述烏姆普思世界現在，我們來探索烏姆普思世界，并通過邏輯推理來確定商人如何找到目標。步驟1：商人位于第一個房間，即正方形[1,1]上，并且已知該房間對商人是安全的。因此，圖14-4（a）表示該房間是安全的。符號A代表商人，符號B代表微風，符號G代表閃光或金幣，符號V代表已訪問過的房間，符號P代表深坑，符號W代表烏姆普思。在[1,1]室，商人不會感到微風或惡臭，這意味著相鄰的正方形也是安全的。14.2.2探索烏姆普思世界

圖14-4探索烏姆普思世界的步驟1和步驟214.2.2探索烏姆普思世界步驟2：商人需要向前移動，因此它將移動到[1，2]或[2,1]。假設移動到房間[2,1]，在這個房間商人感覺到微風，這意味著坑在這個房間周圍，可能在[3,1]或[2,2]中有坑室。現在，商人停止思考，不采取任何措施，回到[1，1]房間。商人訪問過房間[1,1]和[2,1]，因此使用符號V表示訪問過的正方形。14.2.2探索烏姆普思世界步驟3：商人移動到房間[1,2]（圖14-5），這時商人聞到惡臭，這意味著附近有烏姆普思。而按照游戲規則，烏姆普思不能在房間[1,1]中，也不在[2,2]中（商人在[2,1]時沒有聞到惡臭）。因此，推斷出烏姆普思在房間[1,3]中，并且當前狀態下沒有微風，這意味著在[2,2]中沒有深坑也沒有烏姆普思，是安全的，將其標記為OK。商人在[2,2]中進一步移動。14.2.2探索烏姆普思世界

圖14-5探索烏姆普思世界的步驟3和步驟414.2.2探索烏姆普思世界步驟4：在房間[2,2]上，這里沒有惡臭，也沒有微風，所以我們假設商人決定移動到[2,3]。在[2,3]房間，商人感知到閃光，他抓住金子并爬出洞穴。14.2.2探索烏姆普思世界PART03什么是自動規劃自動規劃屬于高級的求解系統與技術。由于自動規劃系統具有廣泛的應用場合和應用前景，因而引起人們的濃厚興趣并取得了許多研究成果。14.3什么是自動規劃經典規劃定義為是在一個離散的、確定性的、靜態的、完全可觀測的環境中，找到完成目標的一系列動作的任務。完成這個任務的方法受到兩個限制。首先，對于每個新領域，它們都需要特定的啟發式方法：用于搜索的啟發式評價函數和用于混合烏姆普思智能體的人工代碼。其次，它們都需要明確地表示指數量級的狀態空間。例如，在烏姆普思世界的命題邏輯模型中，向前移動一步的公理只能在所有4個智能體朝向、T個時間步和n個當前位置重復。14.3.1定義經典規劃我們來看另外兩個例子。（1）范例：積木世界。這是最著名的規劃領域之一，這個問題由一組立方體形狀的積木組成，積木放在一張任意大的桌子上。積木可以堆疊，但只有一塊積木可以直接放在另一個上面。機械臂可以拿起一塊積木并將其放到另一個位置，可以是放在桌子上，也可以放在另一塊積木上。機械臂一次只能拿一塊積木，因此它無法拿起上面有另一塊積木的積木。一個典型的目標是使積木A在積木B上，并且積木B在積木C上（圖14-6）。14.3.1定義經典規劃

圖14-6積木世界問題的示意圖14.3.1定義經典規劃（2）范例：備用輪胎問題。考慮更換癟氣輪胎的問題。其目標是在車軸上正確安裝一只備用輪胎，而初始狀態是車軸上有一只癟氣輪胎，后備箱里有一只備用輪胎。為簡單起見，我們對這個問題的描述是抽象的，不考慮難擰的螺母之類的復雜問題。問題只有4種動作：從后備箱取出備用輪胎、從車軸上卸下癟氣輪胎、把備用輪胎裝在車軸上、把汽車留下整夜無人看管。我們假設汽車停在一個特別糟糕的街區，因此把汽車留下整夜無人看管的效果是輪胎不見了。14.3.1定義經典規劃規劃一直是人工智能研究的活躍領域，包括機器人技術、流程規劃、基于Web的信息收集、自主智能體、動畫和多智能體。

圖14-7規劃自動化立體庫14.3.2自動規劃問題人工智能中一些典型的規劃問題如：（1）對時間、因果關系和目的的表示和推理。（2）在可接受的解決方案中，物理和其他類型的約束。（3）規劃執行中的不確定性。（4）如何感覺和感知“現實世界”。（5）可能合作或互相干涉的多個智能體。14.3.2自動規劃問題以機器人規劃與問題求解作為典型例子來討論自動規劃，是因為機器人規劃能夠得到形象和直觀的檢驗，它是機器人學的一個重要研究領域，也是人工智能與機器人學一個令人感興趣的結合點。機器人規劃的原理、方法和技術可以推廣應用到其他規劃對象或系統。雖然通常我們會將規劃和調度視為相同的問題類型，但它們之間有一個明確的區別：規劃關注“找出需要執行哪些操作”，而調度關注“計算出何時執行動作”。規劃側重于為實現目標選擇適當的行動序列，而調度側重于資源約束（包括時間）。可以把調度問題當作規劃問題的一個特例。14.3.2自動規劃問題在人工智能領域，所有規劃問題的本質就是將當前狀態（可能是初始狀態）轉變為所需目標狀態。求解規劃問題所遵循的步驟順序稱為操作符模式。操作符模式表征動作或事件（可互換使用的術語）。操作符模式表征一類可能的變量，這些變量可以用值（常數）代替，構成描述特定動作的操作符實例。“操作符”這個術語可以用作“操作符模式”或“操作符實例”的同義詞。14.3.2自動規劃問題在魔方的離散拼圖和15拼圖的移動方塊示例中可以找到熟悉的規劃應用，其中包括國際象棋、橋牌以及調度問題。由于運動部件的規律性和對稱性，這些領域非常適合開發和應用規劃算法。

魔方拼圖15拼圖圖14-8魔方拼圖與15拼圖示例14.3.3規劃問題示例計算機和機器人視覺領域的一個典型問題是試圖讓機器人識別墻壁和障礙物，在迷宮中移動并成功地到達其目標，如圖14-9，其中機器人不僅需要從A移動到B，還需要能夠識別墻壁并進行妥善處理。圖14-9一個典型的迷宮問題14.3.3規劃問題示例在設計和制造應用中，人們應用規劃來解決組裝、可維護性和機械部件拆卸問題。人們使用運動規劃，自動計算從組裝中移除零件的無碰撞路徑。在視頻游戲中，自動智能可以用來生成精彩、獨特、類似人類的角色。動畫師的目標是開發具有人類演員特征的角色，同時能夠設計高層次的運動描述，使得這些運動可以由智能體執行。這是一個非常詳細、費力的逐幀過程，動畫師希望通過規劃算法的發展來減少這些過程。14.3.3規劃問題示例將自動規劃應用在計算機動畫中，根據任務規格計算場景中人物的動畫，使動畫師可以專注于場景的整體設計，而無須關注如何在逼真、無碰撞的路徑中移動人物的細節。這不但與計算機動畫相關，而且與人體工程學和產品的可用性評估相關。圖14-10所示的是一個機器人手臂規劃器，這個規劃器執行了多臂任務，在汽車裝配線上協助制造。圖14-10在汽車裝配線上協助

制造的機器人手臂14.3.3規劃問題示例示例14-1說明制訂規劃過程和執行規劃過程之間的區別。請規劃你離開家去工作場所的過程。你必須出席上午9:00的會議。早上上班的路上通常需要花費40分鐘。在準備上班的過程中，你還可以做一些自己喜歡做的任務——一些任務是非常重要的，一些任務是可有可無的，這取決于你可用的時間。14.3.3規劃問題示例下面所列出的是在工作前你認為要完成的一些任務。（1）將幾件襯衫送至干洗店。（2）將瓶子送去回收。（3）把垃圾拿出去。（4）在銀行的自動提款機上取現金。（5）以本地最便宜的價格購買汽油。（6）為自行車輪胎充氣。（7）清理汽車——整理和吸塵。（8）為汽車輪胎充氣。14.3.3規劃問題示例你可能立刻會問這些事情（以下按照規劃的觀點將它們稱為任務）的限制時間。也就是說，在保證你能夠準時參加會議的情況下，這些任務有多少可用的時間？你于上午7:00起床，認為兩個小時已經足夠執行上述許多任務，并能及時參加上午9:00的會議。14.3.3規劃問題示例在上述8項可能的任務中，你很快就會確定只有兩項是非常重要的：第4項（獲得現金）和第8項（為汽車輪胎充氣）。第4項很重要，因為根據經驗，如果現金不足，那么你這一天會寸步難行。你需要購買餐點、小吃和其他可能的物品。第8項可能比第4項更重要，這取決于輪胎中還有多少氣。在極端情況下，輪胎癟了可能會導致你無法駕駛或無法安全駕駛。14.3.3規劃問題示例現在，你確定第4項和第8項很重要、不能避免。這就是分級規劃的例子，也就是對必須完成的任務進行分級或賦值。換句話說，并不是所有的任務都是同等重要的，你可以相應地對它們進行排序。你查詢是否有靠近銀行ATM的加油站，結論是最近的加油站距離銀行有約三個街區。你還可以想：“在銀行附近的哪個加油站會有輪胎的充氣泵？”這是一個機會規劃的例子。也就是說，你正在嘗試利用在規劃形成和規劃執行過程中的某個狀態所提供的條件和機會。14.3.3規劃問題示例在這一點上，第1~3項看起來完全不重要；第6~7項看起來同樣不重要，并且這些任務更適合周末進行，因為周末可以有更多時間完成這樣的任務。在這些情況中，第1~3可能非常相關。14.3.3規劃問題示例第1項：將幾件襯衫送至干洗店。在繁忙的工作日上午，這看起來似乎是一項無關緊要的任務，但是，也許第二天你要接受新工作的面試，或者你想在做演講時穿得得體一些，或者這是你期待已久的一個約會。在這些情況下，你要正確思考（規劃），做正確的事情，獲得最佳機會，讓自己變得成功和快樂。14.3.3規劃問題示例第2項：將舊瓶子進行丟棄回收。同樣，這通常是一個“周末”型的活動。會不會有這樣一種情況使這件事情成為必需的行動？例如，假設你剛剛丟了錢包，而錢包里有你所有的現金、信用卡和身份證。為此，你需要將100個空瓶子送到回收站，以此來獲得必要的現金。此外，如果你丟了錢包，你就不應該在沒有駕駛證的情況下駕駛。如果真有這樣的事情發生了，你也許有足夠的理由不參加那次活動。14.3.3規劃問題示例第3項：把垃圾拿出去。在一些現實條件下，這個任務在重要性方面可以得到很大程度上的重視。例如：（1）垃圾散發出可怕的異味。（2）鄰居投訴你的公寓都是廢棄物，你有責任清理它。（3）這是星期一早上，如果現在不收拾，那么直到星期四才會有人來收拾垃圾。14.3.3規劃問題示例基于某些可能發生的事件或某些緊急情況所做出的規劃稱為條件規劃。這種規劃通常作為一種有用的“防御性”措施，或者必須考慮到一些可能發生的事件。例如，如果你計劃7月份在杭州舉辦大型活動，那么就應該考慮臺風保險。14.3.3規劃問題示例有時候，我們只能規劃事件（操作符）的某些子集，這些事件的子集可能會影響到我們達成目標，而無須特別關注這些步驟執行的順序。我們將此稱為部分有序規劃。在示例14-1的情況下，如果輪胎的情況不是很糟糕，那么我們可以先去加油站充氣，也可以先到銀行取現金。但是，如果輪胎確實癟了，那么執行該規劃的順序是先修理輪胎，然后進行其他任務。14.3.3規劃問題示例通過注意更多的現實情況，我們就可以結束這個例子了。即使兩個小時看起來像是花了大量的時間來處理一些事情，我們依然需要40分鐘的上班時間，但是人們很快就意識到，即使在這個簡單的情況下，也有許多未知數。例如，去加油站、充氣泵處或是銀行可以有很多條路線；在高速公路上可能會發生事故，拖延了上班時間；或者可能會有警察檢查、發生火警等突發情況，這些也會導致延遲。換句話說，有許多未知事件可能會干擾最佳規劃。14.3.3規劃問題示例PART04規劃方法規劃可用來監控問題求解過程，并能夠在造成較大的危害之前發現差錯。規劃的好處可歸納為簡化搜索、解決目標矛盾以及為差錯補償提供基礎，以及把某些較復雜的問題分解為一些較小的子問題。14.4規劃方法規劃本質上是一個搜索問題，就計算步驟數、存儲空間、正確性和最優性而言，這些都涉及到搜索技術的效率。找到一個有效的規劃，從初始狀態開始，并在目標狀態處結束，一般要涉及探索潛在大規模的搜索空間。如果有不同的狀態或部分規劃相互作用，事情會變得更加困難。因此，研究結果也證明了，即使是簡單的規劃問題在大小方面也可能是指數級的。14.4.1規劃即搜索1.狀態空間搜索早期的規劃工作集中在游戲和拼圖的“合法移動”方面，觀察是否可以發現一系列的移動將初始狀態轉換到目標狀態，然后應用啟發式來評估到達目標狀態的“接近度”——這些技術己經應用到規劃領域了。14.4.1規劃即搜索2.中間結局分析最早的人工智能系統的一般問題求解器（GPS）使用了一種稱為“中間結局分析”的問題求解和規劃技術，在中間結局分析背后的主要思想是減少當前狀態和目標狀態之間的距離。也就是說，如果要測量兩個城市之間的距離，算法將選擇能夠在最大程度上減少到目標城市距離的“移動”，而不考慮是否存在機會從中間城市達到目標城市。這是一個貪心算法，它對所到過的位置沒有任何記憶，對其任務環境沒有特定的知識。14.4.1規劃即搜索例如，你想從紐約市到加拿大的渥太華，距離是682千米，估計需要約9小時的車程。飛機只需要1小時，但由于這是一次國際航班，費用高達600美元。對于這個問題，中間結局分析自然偏向飛行，但這是非常昂貴的。一個有趣的可替代方法是結合了時間和金錢的成本效率，同時允許充分的自由，即飛往紐約州錫拉丘茲（最接近渥太華的美國大城市），然后租一輛車開車到渥太華。注意到就推薦的解決方案而言，可能會有一些關鍵性因素。例如，你必須考慮租車的實際成本，你將在渥太華度過的天數以及你是否真的需要在渥太華開車。根據這些問題的答案，你可以選擇公共汽車或火車來滿足部分或全部的交通需求。14.4.1規劃即搜索3.規劃中的各種啟發式搜索方法狀態空間（非智能、窮盡）的搜索技術可能會導致巨大的探索工作量，為此，我們簡要介紹為此開發的各種啟發式搜索技術。（1）最小承諾搜索。是指“規劃器的任何方面，只有在受到某些約束迫使的情況下，才承諾特定的選擇”。比如說，你打算搬到一所新的公寓。首先，你根據自己的收入水平選定合適的城鎮和社區，不需要決定將要居住的區塊、建筑和具體的公寓。這些決定可以推遲到更晚、更適合的時間做出。14.4.1規劃即搜索（2）選擇并承諾。這是一種獨特的規劃搜索技術，這種方法并不能激發太多的信心。它是指基于局部信息（類似于中間結局分析），遵循一條解決路徑的新技術，它通過做出的決策（承諾）得到測試。使用這種方式測試的其他規劃器可以集成到稍后的規劃器中，然后可以搜索替代方案。當然，如果對一條路徑的承諾沒有產生解就會存在問題。14.4.1規劃即搜索（3）深度優先回溯。是考慮替代方案的一種簡單方法，特別是當只有少數解決方案可供選擇時。這種方法涉及在有替代解決方案的位置保存解決方案路徑的狀態，選中第一個替代路徑，備份搜索；如果沒有找到解決方案，則選擇下一個替代路徑。通過部分實例化操作符來查看是否已經找到解決方案，測試這些分支的過程被稱為“舉起”。（4）集束搜索。它與其他啟發式方法一起實現，選擇“最佳”解決方案，也許是由集束搜索建議子問題的“最佳”解決方案。14.4.1規劃即搜索（5）主因最佳回溯。通過搜索空間的回溯，雖然可能得到解決方案，但是在多個層次中所需要探索的節點數量龐大，所以這可能非常昂貴。主因最佳回溯花費更多的努力，確定了在特定節點所備份的局部選擇是最佳選擇。作為一個類比，讓我們回到選擇生活在某個城鎮的問題。考慮候選地區的兩個主要因素是距離和價格。根據這些因素，我們找到最理想的區域。14.4.1規劃即搜索但是現在，我們必須在可能的5~10個合理候選城鎮中做出決定，為此必須考慮更多的因素。①學校設置怎么樣（為了小孩）？②在這個地區購物是否便利？③這個城鎮安全嗎？④它距離中心區域有多遠（運輸）？⑤這個地區有哪些景點？14.4.1規劃即搜索當進行評估時，基于公寓的價格和每個候選城鎮到你工作地點的距離，再加上上述5個附加因素，你應該可以選擇一個城鎮，然后繼續進行搜索，進而選擇一處適當的公寓。一旦選定了城鎮，就可以查看這個城鎮某些公寓的可用性和適用性。如有必要，可以重新評估其他城鎮的可能性，并選擇另一個城鎮（基于兩個主要因素和5個次要因素）作為主要選擇。這就是主因最佳回溯算法的工作原理。14.4.1規劃即搜索（6）依賴導向式搜索。回溯到保存狀態并恢復搜索可能帶來極大的浪費。實踐證明，存儲決策之間的依賴關系所做出的假設和可以做出選擇的替代方案可能更有用、更有效。通過重建解決方案中的所有依賴部分，系統避免了失敗，同時不相關的部分也可以保持不變。（7）機會式搜索。基于“可執行的最受約束的操作”。所有問題求解組件都可以將其對解決方案的要求歸結為對解決方案的約束，或對表示被操作對象的變量值的限制。操作可以暫停，直到有進一步可用信息。14.4.1規劃即搜索（8）元級規劃。是從各種規劃選項中進行推理和選擇的過程。一些規劃系統具有類似操作符表示的規劃轉換可供規劃器使用。系統執行獨立的搜索，在任何點上，確定最適合應用哪個操作符。這些動作發生在做出任何關于規劃應用的決策之前。（9）分布式規劃。系統在一群專家中分配子問題，讓他們求解這些問題，在通過黑板進行溝通的專家之間傳遞子問題并執行子問題。這里總結回顧了在規劃中使用的搜索方法。人工智能的自動規劃領域已經開發了一些技術來限制所需要的搜索量。14.4.1規劃即搜索部分有序規劃（POP）被定義為“事件（操作符）的某個子集可以實現、達到目標，而無須特別關注執行步驟的順序。”在部分有序規劃器中，可以使用操作符的部分有序網絡表示規劃。在制訂規劃過程中，只有當問題請求操作符之間存在有序鏈時，才引進它，在這個意義上，部分有序規劃器表現為最小承諾。相比之下，完全有序規劃器使用操作符序列表示其搜索空間中的規劃。14.4.2部分有序規劃部分有序規劃通常有以下3個組成部分。（1）動作集。例如：{開車上班，穿衣服，吃早餐，洗澡}。（2）順序約束集。例如：{洗澡，穿衣服，吃早餐，開車去上班}。（3）因果關系鏈集。例如：穿衣服——著裝→開車去上班。這里的因果關系鏈是，如果你不想沒穿衣服就開車，那么請在開車上班前穿好衣服！在不斷完善和實現部分規劃時，這種鏈有助于撿測和防止不一致。在標準搜索中，節點等于具體世界（或狀態空間）中的狀態。14.4.2部分有序規劃在規劃世界中，節點是部分規劃。因此，部分規劃包括以下內容。·操作符應用程序集Si。·部分（時間）順序約束Si<Sj。·因果關系鏈Si—→Sj。操作符是在因果關系條件上的動作，可以用來獲得開始條件。開始條件是未被因果關系鏈接的動作的前提條件。14.4.2部分有序規劃這些步驟組合形成一個部分規劃：·為獲得開始條件，使用因果關系鏈描述動作。·從現有動作到開始條件過程中，做出因果關系鏈。·在上述步驟之間做出順序約束。圖14-11描繪了一個簡單的部分有序規劃。這個規劃在家開始，在家結束。

圖14-11部分有序規劃14.4.2部分有序規劃在部分有序規劃中，不同的路徑（如首先選擇去加油站還是銀行）不是可選規劃，而是可選動作。如果每個前提條件都能達成（我們到銀行和加油站，然后安全回家），我們就說規劃完成了。當動作順序完全確定后，部分有序規劃成了完全有序規劃。例如，如果發現汽車的油箱幾乎是空的，當且僅當達成每個前提條件時，規劃才能算完成。當一些動作Sk發生