人工智能基礎(chǔ)之自動(dòng)規(guī)劃系統(tǒng)

目錄第一章緒論第二章知識(shí)表示

第三章搜索技術(shù)第四章推理技術(shù)第五章機(jī)器學(xué)習(xí)

第六章專(zhuān)家系統(tǒng)

第七章自動(dòng)規(guī)劃系統(tǒng)第八章自然語(yǔ)言理解第九章智能控制第十章人工智能程序設(shè)計(jì)7.1自動(dòng)規(guī)劃概述7.1.1規(guī)劃的概念及作用

1.規(guī)劃的概念

定義7.1

從某個(gè)特定的問(wèn)題狀態(tài)出發(fā)，尋求一系列行為動(dòng)作，并建立一個(gè)操作序列，直到求得目標(biāo)狀態(tài)為止。這個(gè)求解過(guò)程就稱(chēng)為規(guī)劃。

定義7.2

規(guī)劃是對(duì)某個(gè)待求解問(wèn)題給出求解過(guò)程的步驟。規(guī)劃涉及如何將問(wèn)題分解為若干相應(yīng)的子問(wèn)題，以及如何記錄和處理問(wèn)題求解過(guò)程中發(fā)現(xiàn)的各子問(wèn)題間的關(guān)系。

定義7.3

規(guī)劃系統(tǒng)是一個(gè)涉及有關(guān)問(wèn)題求解過(guò)程步驟的系統(tǒng)。如計(jì)算機(jī)或飛機(jī)設(shè)計(jì)、火車(chē)或汽車(chē)運(yùn)輸路徑、財(cái)政和軍事規(guī)劃等問(wèn)題。7.1自動(dòng)規(guī)劃概述7.1.1規(guī)劃的概念及作用例：救援仿真機(jī)器人系統(tǒng)（RoboCupRescueSimulationSystem，RCRSS）

①

消防智能體②

醫(yī)療智能體③

警察智能體④

普通市民⑤

中心智能體⑥

路障⑦

避難所⑧

著火建筑物⑨

普通建筑物）

7.1自動(dòng)規(guī)劃概述7.1.1規(guī)劃的概念及作用

2.規(guī)劃的作用規(guī)劃可用來(lái)監(jiān)控問(wèn)題求解過(guò)程，并能夠在造成較大的危害之前發(fā)現(xiàn)差錯(cuò)。規(guī)劃的好處可歸納為簡(jiǎn)化搜索、解決目標(biāo)矛盾以及為差錯(cuò)補(bǔ)償提供基礎(chǔ)。

“十二五”規(guī)劃、城市規(guī)劃、企業(yè)發(fā)展規(guī)劃7.1自動(dòng)規(guī)劃概述7.1.2規(guī)劃的分類(lèi)和問(wèn)題分解途徑

1.規(guī)劃的分類(lèi)（1）按規(guī)劃內(nèi)容分國(guó)家、地方、重大項(xiàng)目、企業(yè)、交通、城市、環(huán)境…

（2）按規(guī)劃方法分

非遞階（非分層）規(guī)劃與遞階（分層）規(guī)劃；線性規(guī)劃與非線性規(guī)劃；同步規(guī)劃與異步規(guī)劃；基于腳本、框架和本體的規(guī)劃；基于專(zhuān)家系統(tǒng)的規(guī)劃；基于競(jìng)爭(zhēng)機(jī)制的規(guī)劃；…

（3）按規(guī)劃實(shí)質(zhì)分

任務(wù)規(guī)劃、路徑規(guī)劃、軌跡規(guī)劃…7.1自動(dòng)規(guī)劃概述7.1.2規(guī)劃的分類(lèi)和問(wèn)題分解途徑

2.問(wèn)題分解途徑把某些較復(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)題。7.1自動(dòng)規(guī)劃概述7.1.2規(guī)劃的分類(lèi)和問(wèn)題分解途徑

3.域的預(yù)測(cè)和規(guī)劃的修正

（1）域的預(yù)測(cè)

問(wèn)題論域的預(yù)測(cè)。對(duì)于不可預(yù)測(cè)的論域，考慮可能的結(jié)果集合，按照它們出現(xiàn)的可能性以某個(gè)次序排列。然后，產(chǎn)生一個(gè)規(guī)劃、并試圖去執(zhí)行這個(gè)規(guī)劃。

（2）規(guī)劃的修正

規(guī)劃執(zhí)行失敗導(dǎo)致對(duì)規(guī)劃的修正。

在規(guī)劃過(guò)程中不僅要記錄規(guī)劃的執(zhí)行步驟，而且要記錄每一步必須要執(zhí)行的理由。7.2基于謂詞邏輯的規(guī)劃

用謂詞邏輯來(lái)描述世界模型及規(guī)劃過(guò)程。

世界模型的謂詞邏輯表示定義謂詞確定問(wèn)題初始狀態(tài)確定問(wèn)題目標(biāo)狀態(tài)確定基本操作

基于謂詞邏輯規(guī)劃的基本過(guò)程問(wèn)題分解子問(wèn)題規(guī)劃得到操作序列7.3STRIPS規(guī)劃系統(tǒng)

7.3.1積木世界的機(jī)器人規(guī)劃BACCBA機(jī)械手機(jī)械手(a)(b)7.3STRIPS規(guī)劃系統(tǒng)

7.3.1積木世界的機(jī)器人規(guī)劃1.積木世界的機(jī)器人問(wèn)題

機(jī)器人能夠執(zhí)行的動(dòng)作舉例如下：unstack(a,b)：把堆放在積木b上的積木a拾起。在進(jìn)行這個(gè)動(dòng)作之前，要求機(jī)器人的手為空手，且積木a的頂上是空的。stack(a,b)：把積木a堆放在積木b上。動(dòng)作之前要求機(jī)械手必須已抓住積木a，而且積木b頂上必須是空的。pickup(a)：從桌面上拾起積木a，并抓住它不放。在動(dòng)作之前要求機(jī)械手為空手，而且積木a頂上沒(méi)有任何東西。putdown(a)：把積木a放置到桌面上。要求動(dòng)作之前機(jī)械手已抓住積木a。7.3STRIPS規(guī)劃系統(tǒng)統(tǒng)積木世界界的機(jī)器器人規(guī)劃劃1.積木世界界的機(jī)器器人問(wèn)題題狀態(tài)描述述謂詞：ON(a,b)：積木木a在積木b之上。ONTABLE(a)：積木木a在桌面上上。CLEAR(a)：積木木a頂上沒(méi)有有任何東東西。HOLDING(a)：機(jī)械械手正抓抓住積木木a。HANDEMPTY：機(jī)械械手為空空手。7.3STRIPS規(guī)劃系統(tǒng)統(tǒng)積木世界界的機(jī)器器人規(guī)劃劃2.用F規(guī)則求解解規(guī)劃序序列采用F規(guī)則表示示機(jī)器人人的動(dòng)作作，這是是一個(gè)叫叫做STRIPS規(guī)劃系統(tǒng)統(tǒng)的規(guī)則則，它由由3部分組成成：第一部分分是先決決條件。。為了使使F規(guī)則能夠夠應(yīng)用到到狀態(tài)描描述中去去。第二部分分是一個(gè)個(gè)叫做刪刪除表的的謂詞。。當(dāng)一條條規(guī)則被被應(yīng)用于于某個(gè)狀狀態(tài)描述述或數(shù)據(jù)據(jù)庫(kù)時(shí)，，就從該該數(shù)據(jù)庫(kù)庫(kù)刪去刪刪除表的的內(nèi)容。。第三部分分叫做添添加表。。當(dāng)把某某條規(guī)則則應(yīng)用于于某數(shù)據(jù)據(jù)庫(kù)時(shí)，，就把該該添加表表的內(nèi)容容添進(jìn)該該數(shù)據(jù)庫(kù)庫(kù)。7.3STRIPS規(guī)劃系系統(tǒng)積木世世界的的機(jī)器器人規(guī)規(guī)劃2.用F規(guī)則求求解規(guī)規(guī)劃序序列例：move(x,y,z):把物體體x從物體體y上面移移到物物體z上面。。先決條條件：：CLEAR(x),CLEAR(z),ON(x,y)刪除表表：ON(x,y),CLEAR(z)添加表表：ON(x,z),CLEAR(y)7.3STRIPS規(guī)劃系系統(tǒng)規(guī)劃系系統(tǒng)STanfordResearchInstituteProblemSolver———STRIPSSTRIPS系統(tǒng)的的組成成如下下：(1)世界模模型。。為一一階謂謂詞演演算公公式。。(2)操作符符(F規(guī)則)。包括括先決決條件件、刪刪除表表和添添加表表。(3)操作方方法。。應(yīng)用用狀態(tài)態(tài)空間間表示示和中中間-結(jié)局分分析。。規(guī)劃過(guò)過(guò)程每個(gè)STRIPS問(wèn)題的的解答答為某某個(gè)實(shí)實(shí)現(xiàn)目目標(biāo)的的操作作符序序列，，即達(dá)達(dá)到目目標(biāo)的的規(guī)劃劃。7.4分層規(guī)規(guī)劃探索規(guī)規(guī)劃時(shí)時(shí)首先先只考考慮一一層的的細(xì)節(jié)節(jié)，然然后再再注意意規(guī)劃劃中比比這一一層低低一層層的細(xì)細(xì)節(jié)，，所以以把它它叫做做長(zhǎng)度度優(yōu)先先搜索索。NOAH規(guī)劃系統(tǒng)1.應(yīng)用最小約約束策略一個(gè)尋找非非線性規(guī)劃劃而不必考考慮操作符符序列的所所有排列的的方法是把把最少約束束策略應(yīng)用用來(lái)選擇操操作符執(zhí)行行次序的問(wèn)問(wèn)題。問(wèn)題求解系系統(tǒng)NOAH采用一種網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)來(lái)來(lái)記錄它所所選取的操操作符之間間所需要的的排序。它它也分層進(jìn)進(jìn)行操作運(yùn)運(yùn)算，即首首先建立起起規(guī)劃的抽抽象輪廓，，然后在后后續(xù)的各步步中，填入入越來(lái)越多多的細(xì)節(jié)。。7.4分層規(guī)劃2.檢驗(yàn)準(zhǔn)則準(zhǔn)則法已被被應(yīng)用于各各種規(guī)劃生生成系統(tǒng)。。對(duì)于早期期的系統(tǒng)，，如HACKER系統(tǒng)，準(zhǔn)則則只用于舍舍棄不滿(mǎn)足足的規(guī)劃。。在NOAH系統(tǒng)中，準(zhǔn)準(zhǔn)則被用來(lái)來(lái)提出推定定的方法以以便修正所所產(chǎn)生的規(guī)規(guī)劃。第第一個(gè)個(gè)涉及的準(zhǔn)準(zhǔn)則是歸結(jié)結(jié)矛盾準(zhǔn)則則。第二個(gè)準(zhǔn)則則叫做消除除多余先決決條件準(zhǔn)則則，包括除除去對(duì)子目目標(biāo)的多余余說(shuō)明?？梢园逊謱訉右?guī)劃和最最少約定策策略十分直直接地結(jié)合合起來(lái)，以以求得非線線性規(guī)劃而而不產(chǎn)生一一個(gè)龐大的的搜索樹(shù)。。7.5基于專(zhuān)家系系統(tǒng)的機(jī)器器人規(guī)劃1.系統(tǒng)結(jié)構(gòu)及及規(guī)劃?rùn)C(jī)理理（1）知識(shí)庫(kù)：：用于存儲(chǔ)儲(chǔ)某些特定定領(lǐng)域的專(zhuān)專(zhuān)家知識(shí)和和經(jīng)驗(yàn)，包包括機(jī)器人人工作環(huán)境境的世界模模型、狀態(tài)態(tài)、物體描描述等事實(shí)實(shí)和可行操操作或規(guī)則則等。（2）控制策略：：包含綜合合機(jī)理，確確定系統(tǒng)應(yīng)應(yīng)當(dāng)應(yīng)用什什么規(guī)則以以及采取什什么方式去去尋找該規(guī)規(guī)則。（3）推理機(jī)：用用于記憶所所采用的規(guī)規(guī)則和控制制策略及推推理策略。。（4）知識(shí)獲?。海菏紫全@取某某特定域的專(zhuān)專(zhuān)家知識(shí)。然然后用程序設(shè)設(shè)計(jì)語(yǔ)言把這這些知識(shí)變換換為計(jì)算機(jī)程程序。最后把把它們存入知知識(shí)庫(kù)待用。。7.5基于專(zhuān)家系統(tǒng)統(tǒng)的機(jī)器人規(guī)規(guī)劃(5)解釋與說(shuō)明：：通過(guò)用戶(hù)接接口，在專(zhuān)家家系統(tǒng)與用戶(hù)戶(hù)之間進(jìn)行對(duì)對(duì)話(huà)，從而使使用戶(hù)能夠輸輸入數(shù)據(jù)、提提出問(wèn)題、知知道推理結(jié)果果以及了解推推理過(guò)程等。。2.任務(wù)級(jí)機(jī)器人人規(guī)劃三要素素（1）建立模型：：世界模型。。（2）任務(wù)說(shuō)明：：定義狀態(tài)及及狀態(tài)變換次次序。（3）程序綜合