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

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

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

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

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

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

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

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

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

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

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