人工智能通識教程 第2版 課件 第13、14章 群體智能、自動規(guī)劃

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

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

圖14-2自動裝箱規(guī)劃第14章自動規(guī)劃PART01規(guī)劃的概念所謂規(guī)劃，是指個人或組織制定的比較全面長遠(yuǎn)的發(fā)展計劃，是對未來整體性、長期性、基本性問題的考量，以設(shè)計未來的整套行動方案。規(guī)劃是融合多要素、多人士看法的某一特定領(lǐng)域的發(fā)展愿景，它代表了人類為實(shí)現(xiàn)目標(biāo)而對活動進(jìn)行調(diào)整的一種某種自我意識和能力。在日常生活中，規(guī)劃意味著在行動之前決定其進(jìn)程，或者說，是在執(zhí)行一個問題求解程序之前，計算該程序具體執(zhí)行的過程。規(guī)劃可用來監(jiān)控問題求解過程，并能夠在造成較大危害之前發(fā)現(xiàn)差錯。規(guī)劃的好處可歸納為簡化搜索、解決目標(biāo)矛盾以及為差錯補(bǔ)償提供基礎(chǔ)。14.1規(guī)劃的概念規(guī)劃有兩個突出的特點(diǎn)，一是為了完成任務(wù)可能需要一系列確定的步驟；二是定義問題解決方案的步驟順序可能是有條件的。也就是說，構(gòu)成規(guī)劃的步驟可能會根據(jù)條件進(jìn)行修改（稱為條件規(guī)劃）。一個規(guī)劃是一個行動過程的描述，它雖然可以是像商品清單那樣的沒有次序的目標(biāo)列表，但一般都具有某個目標(biāo)的蘊(yùn)含排序。例如，一個機(jī)器人要搬動某工件，必須先移動到該工件附近，抓住該工件，然后帶著工件移動。14.1規(guī)劃的概念大多數(shù)規(guī)劃都具有子規(guī)劃結(jié)構(gòu)，具有分層結(jié)構(gòu)的每個子目標(biāo)由達(dá)到此目標(biāo)的比較詳細(xì)的子規(guī)劃確定，最終得到的規(guī)劃是某個問題求解算符的線性或分步排序。14.1規(guī)劃的概念規(guī)劃的概念很多，具體可以整理成如下幾點(diǎn)：（1）從某個特定的問題狀態(tài)出發(fā)，尋求一系列行為動作并建立一個操作序列，直到求得目標(biāo)狀態(tài)為止，這個求解過程就是規(guī)劃；（2）規(guī)劃是關(guān)于動作的推理，它是一種抽象但清晰的深思熟慮的過程，該過程通過預(yù)期動作的期望效果，選擇和組織一組動作，其目的是盡可能好地實(shí)現(xiàn)一個預(yù)先給定的目標(biāo)；14.1規(guī)劃的概念（3）規(guī)劃是針對某個待求解問題給出求解過程的步驟，規(guī)劃設(shè)計如何將問題分解為若干相應(yīng)的子問題，記錄和處理問題求解過程中發(fā)現(xiàn)的子問題間的關(guān)系；（4）規(guī)劃系統(tǒng)是一個涉及有關(guān)問題求解過程的步驟的系統(tǒng)。14.1規(guī)劃的概念把某些較復(fù)雜的問題分解為一些較小的子問題。有兩條實(shí)現(xiàn)這種分解的重要途徑。第一條是當(dāng)從一個問題狀態(tài)移動到下一個狀態(tài)時，無需計算整個新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那些部分。第二條是把單一困難問題分割為幾個有希望較為容易解決的子問題。14.1規(guī)劃的概念PART02人工智能的烏姆普思世界這是一個簡單的世界示例。烏姆普思（Wumpus）世界是一個山洞，有4×4共16個房間，房間與通道相連，有一個商人（智能體）將在這個世界中移動。圖14-3烏姆普思世界14.2人工智能的烏姆普思世界山洞里的某一間屋子里有個叫烏姆普思的怪物，它會吃掉進(jìn)屋的任何人。商人可以射殺烏姆普思，但他只有一枝箭。在烏姆普思世界中有一些深坑洞室（PIT），如果商人落在深坑中，會被永遠(yuǎn)困在坑里。令人興奮的是，洞穴里有一個房間里有可能找到一大堆金子。因此，商人的目標(biāo)是找到金子并爬出洞穴，而不會掉落坑中或被烏姆普思吞噬。如果商人帶金子出來，會得到獎勵；如果商人被烏姆普思吞下或掉進(jìn)坑里，會受到懲罰。14.2人工智能的烏姆普思世界為解釋烏姆普思世界，對任務(wù)環(huán)境做如下描述。（1）性能指標(biāo)：·如果商人帶著金子從烏姆普思世界中出來，可獲得1000點(diǎn)獎勵積分?！け粸跄菲账汲缘艋虻暨M(jìn)坑里，點(diǎn)數(shù)為-1000分?！?1表示每個操作，-10表示使用箭?！と绻倘怂劳龌驈纳蕉闯鰜?，游戲就結(jié)束。14.2.1描述烏姆普思世界（2）環(huán)境：·4×4的房間網(wǎng)格。·商人最初位于房間正方形[1,1]中，朝向右側(cè)。·除了第一個正方形[1,1]以外，都是隨機(jī)選擇烏姆普思和金子的位置?！こ谝粋€正方形以外，洞穴中每個正方形是坑室的概率為0.2。（3）執(zhí)行器：左轉(zhuǎn)、右轉(zhuǎn)、前進(jìn)、抓取、發(fā)布、射擊。14.2.1描述烏姆普思世界（4）傳感器：·如果商人進(jìn)到與烏姆普思相鄰的房間（不是對角線的），會聞到惡臭?！と绻倘诉M(jìn)到與坑室相鄰的房間內(nèi)，會感覺到微風(fēng)?！ど倘四芨兄椒庞薪鹱拥姆块g中的閃光。·商人走向墻壁會感覺到撞擊。·射殺烏姆普思時，它會發(fā)出可怕的尖叫聲，這在山洞的任何地方都可以感覺到。14.2.1描述烏姆普思世界·這些感知可以表示為五個元素列表。例如，如果商人聞到惡臭或者感到微風(fēng)，但沒有閃光，沒有碰撞和尖叫聲，可以表示為：[惡臭,微風(fēng),無,無,無]。14.2.1描述烏姆普思世界（5）烏姆普思世界：·部分可觀察：因?yàn)樯倘酥荒芨兄浇沫h(huán)境，例如相鄰的房間?！ご_定性的：因?yàn)槭澜绲慕Y(jié)果是已知的?！ろ樞虻模喉樞蚝苤匾??！れo態(tài)：烏姆普思和深坑不移動，是靜態(tài)的。·離散的：環(huán)境是離散的?！ひ粋€智能體（商人）：環(huán)境中只有一個智能體，烏姆普思不被視為智能體。14.2.1描述烏姆普思世界現(xiàn)在，我們來探索烏姆普思世界，并通過邏輯推理來確定商人如何找到目標(biāo)。步驟1：商人位于第一個房間，即正方形[1,1]上，并且已知該房間對商人是安全的。因此，圖14-4（a）表示該房間是安全的。符號A代表商人，符號B代表微風(fēng)，符號G代表閃光或金幣，符號V代表已訪問過的房間，符號P代表深坑，符號W代表烏姆普思。在[1,1]室，商人不會感到微風(fēng)或惡臭，這意味著相鄰的正方形也是安全的。14.2.2探索烏姆普思世界

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

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

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

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

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

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

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