2022年規(guī)劃求解系統(tǒng)

第七章規(guī)劃求解系統(tǒng)

與需求解的一般典型問題相比，人工智能規(guī)劃求解系統(tǒng)往往注重大型復(fù)雜對象的研究。

前者關(guān)心的是具體問題的具體解答結(jié)果，而后者注重的是系統(tǒng)求解過程及解路徑(Solut

ionPath)的尋取。

其次，人工智能研究的傳統(tǒng)規(guī)劃問題，關(guān)注高層次求解系統(tǒng)技術(shù)的自動(dòng)完成，重視“擬

人"智能特性的發(fā)揮，使系統(tǒng)能對現(xiàn)場具體任務(wù)和環(huán)境，自動(dòng)進(jìn)行分析與描述，自動(dòng)選擇求

解步驟，形象生動(dòng)地完成其過程。例如機(jī)器人規(guī)劃(Robotplanning),計(jì)算機(jī)下棋(Computer

chess)等。

應(yīng)該指出，目前關(guān)于規(guī)劃求解問題，客觀上已形成了兩分支開展的格局：一條是人工智

能科學(xué)關(guān)于研究自動(dòng)規(guī)劃系統(tǒng)及其完成技術(shù)的道路，另一條則是治理運(yùn)籌科學(xué)中關(guān)于應(yīng)用數(shù)

學(xué)規(guī)劃的研究分支。

后者針對諸如如何合理配置使用資源，取得最優(yōu)生產(chǎn)及經(jīng)濟(jì)效益等類具體問題，運(yùn)用數(shù)

學(xué)方法，設(shè)法建立或找到容納假設(shè)干環(huán)境參數(shù)相約束的數(shù)學(xué)模型，并依照實(shí)驗(yàn)不斷修正模型，

最后依靠模型計(jì)算，尋取本原問題最優(yōu)解。

如何將上述兩種不同的研究思路互取所長，協(xié)同開展呢二者如何兼容并蓄，縱橫綜合，

以便共展規(guī)劃科學(xué)的新藍(lán)圖呢這或許正是新時(shí)代研究規(guī)劃科學(xué)工作者又一新課題。

本章重點(diǎn)在于介紹并深刻探討人工智能規(guī)劃求解問題的原理、方法和技術(shù)。

第一節(jié)規(guī)劃

規(guī)劃的概念

規(guī)劃(Planning),可認(rèn)為是循規(guī)籌劃的縮略詞。意即在行動(dòng)之前，確定到達(dá)系統(tǒng)目標(biāo)的

進(jìn)程。換言之，是尋求快速到達(dá)目標(biāo)的步驟和路徑。

究其規(guī)劃內(nèi)涵，具有兩層含義：既要遵循客觀規(guī)律，確立到達(dá)系統(tǒng)目標(biāo)的方略方案，又

須依照肯定的技術(shù)方法，實(shí)施運(yùn)作步驟，力求取得最正確解操作序列。簡言之，規(guī)劃就是制

定、實(shí)施行動(dòng)的步驟與決策。

一個(gè)規(guī)劃，就是一個(gè)行動(dòng)過程的描述。如圖7-1所示結(jié)構(gòu)，是一位大學(xué)生一天正常的作

息安排，它就是一個(gè)規(guī)劃構(gòu)成。

圖7T的例子還簡要范表現(xiàn)出：一個(gè)總規(guī)劃，可以含有假設(shè)干子規(guī)劃和求解流程的結(jié)構(gòu)。

規(guī)劃的特性和作用

缺少規(guī)劃，將導(dǎo)致求解效率極大程度的降低。例如，有人為了買郵票和寄信，因?yàn)槿鄙?/p>

規(guī)劃，跑了兩次郵局。

在問題規(guī)劃求解中，規(guī)劃范表現(xiàn)出既有相互獨(dú)立，多條局部解路經(jīng)可選的特性，又包含

序

列相貫，不可隨意顛倒順序的環(huán)節(jié)特性。例如，走出大森林，到達(dá)目的地，可以有多條路線,

但每條路線所須跨越的山谷川流的次序大致都是固定的。

=子約束2=子約束3

圖7-2規(guī)劃的相關(guān)性

例如，欲建一座優(yōu)質(zhì)大樓，規(guī)劃環(huán)節(jié)應(yīng)包含：預(yù)先設(shè)計(jì)圖紙，施工先須打好地基，預(yù)

留地下管道等。地下工程完畢，再實(shí)施地上工程，先起地面樓層，再逐漸續(xù)起高層。但是，

如果缺少合理規(guī)劃，工程施工顛倒了次序，該工程就將失敗或造成極大損失。

按規(guī)劃實(shí)施，還可用以監(jiān)控系統(tǒng)運(yùn)行進(jìn)程。這樣，可以及時(shí)覺察并預(yù)防過失。例如，考

慮某個(gè)在深海打撈作業(yè)的潛水機(jī)器人，它必須能夠規(guī)劃一個(gè)探測海域環(huán)境，隨時(shí)掌握現(xiàn)場作

業(yè)面的步驟和進(jìn)程。當(dāng)發(fā)生深海潛流影響，導(dǎo)致目標(biāo)物位置變動(dòng)時(shí)，機(jī)器人能依據(jù)檢測到的

環(huán)境參數(shù)與預(yù)期不符的差異，在向海面指揮中心發(fā)出告警信息的同時(shí):還須啟動(dòng)作業(yè)修改進(jìn)

程規(guī)劃，采取必要調(diào)整作業(yè)進(jìn)程步驟和操作措施。

三.系統(tǒng)規(guī)劃求解的方法與途徑

把大型復(fù)雜系統(tǒng)的規(guī)劃求解，化為假設(shè)干復(fù)雜度低得多的子系統(tǒng)、子目標(biāo)尋優(yōu)過程的綜

合作用，這種降低復(fù)雜問題求解難度的分析方法，稱為分解技術(shù)。它是完成規(guī)劃求解的主要

技術(shù)手段。按照采納規(guī)劃決策的不同思維方法，規(guī)劃技術(shù)可以有許多分解途徑。圖7-3列出

了局部規(guī)劃分解的技術(shù)實(shí)施方案。

區(qū)劃進(jìn)程分解

等物理時(shí)空性度量j規(guī)劃空間分解

X

時(shí)空混合分解

等

規(guī)

劃"關(guān)鍵子目標(biāo)規(guī)劃分解

按目標(biāo)技術(shù)功能關(guān)鍵指標(biāo)功能規(guī)劃分解

分J

特點(diǎn)及重要性關(guān)鍵過程規(guī)劃分解

解I

技

術(shù)"靜態(tài)規(guī)劃

按系統(tǒng)運(yùn)動(dòng)Y

持性分為［動(dòng)態(tài)規(guī)劃

’與/或樹規(guī)劃描述分解

按AI知識(shí)范表司狀態(tài)空間描述規(guī)劃分解

技術(shù)分為I框架技術(shù)規(guī)劃分解

、產(chǎn)生式規(guī)劃分解

圖7-3問題規(guī)劃分析的技術(shù)途徑

如圖7-4所示的規(guī)劃與/或樹，是人們常喜歡采納的一種簡化規(guī)劃求解難度的重要思想。

圖中，問題的難度逐層降低。其中:

Po=PiAP2Ap3

P>=PnVPi2

P2=P21八P22

P3—（P3IAP32）VP33

第二節(jié)機(jī)器規(guī)劃成功性根本原理

—.概述

完成機(jī)器智能的自動(dòng)規(guī)劃系統(tǒng)，存在許多非本原問題的因素。對機(jī)器規(guī)劃成功性的考察,

更重要的是從歷史性開展，總體性和心理學(xué)上去探詢認(rèn)識(shí)。機(jī)器自動(dòng)規(guī)劃問題，是現(xiàn)實(shí)科技

領(lǐng)域中高難度問題?，F(xiàn)實(shí)中人類智能規(guī)劃，尚難保證不出過失，機(jī)器智能規(guī)劃又豈能輕易成

功！事實(shí)上，規(guī)劃的研究不在于一次性獵取成功，而在于可從假設(shè)干次不成功中，進(jìn)行機(jī)器

歸納學(xué)習(xí)，使得修訂的規(guī)劃比以前任何一次都更加接近成功。

早在1958年，人工智能先驅(qū)者和大師Newell和Simon曾就機(jī)器自動(dòng)規(guī)劃問題，作出了

非常樂觀的預(yù)言：

(1)計(jì)算機(jī)將要成為世界象棋冠軍；

(2)計(jì)算機(jī)將要制造和證明重要的數(shù)學(xué)定理；

(3)計(jì)算機(jī)將能譜寫具有優(yōu)秀作曲家水平的樂曲；

(4)大多數(shù)心理學(xué)理論將在計(jì)算機(jī)上形成。

當(dāng)時(shí)預(yù)言10年內(nèi)就可完成的目標(biāo)，卻直到假設(shè)干個(gè)10年后，這幾個(gè)問題才漸有轉(zhuǎn)機(jī)和

答案。人工智能科學(xué)界也曾因這幾個(gè)問題的認(rèn)識(shí)和爭論，引起過大起大落的軒然大波。

目前，機(jī)器自動(dòng)規(guī)劃研究成果已經(jīng)揭示：上述除第⑷條外，前三條或已獲成功，或已根

本獲得成功。例如，1997年5月美國IBM公司“深藍(lán)"(DeeperBlue)計(jì)算機(jī)，戰(zhàn)勝國際象

棋世界冠軍加里?卡斯帕羅夫(GarryKasporrov),第一次登上了國際象棋世界冠軍的寶座；

1976年，美國數(shù)學(xué)家Appel和Haken,運(yùn)用計(jì)算機(jī)輔助證明(CAP)的規(guī)劃思想，一舉攻克了世

界三大數(shù)學(xué)難題之一的“四色定理”的證明。至于利用多媒體計(jì)算機(jī)音響裝置，讓計(jì)算機(jī)彈

奏出具有隨機(jī)數(shù)字符號(hào)音樂,人們已是司空見慣。

上述事例說明，機(jī)器自動(dòng)規(guī)劃全面成功地解決，雖然很難，但又是必定的。人類應(yīng)該保

持平常心態(tài)，歡迎這一劃時(shí)代的來臨：正如汽車比人跑得快，起重機(jī)比人舉得重，計(jì)算機(jī)比

人算得快，機(jī)器人可能將在假設(shè)干方面超過人的能力，這又有什么稀奇呢

綜上所述，面對機(jī)器自動(dòng)規(guī)劃系統(tǒng)成功性的研究，尚需研討下述假設(shè)干具體問題：

其一、如何進(jìn)行問題總規(guī)劃的設(shè)計(jì)

其二、當(dāng)規(guī)劃失敗時(shí)，如何確診規(guī)劃失敗的環(huán)節(jié)，并進(jìn)行規(guī)劃修正，

其三、如何進(jìn)行機(jī)器規(guī)劃的自學(xué)習(xí)如何自動(dòng)生成規(guī)劃系統(tǒng)及過程

諸如上述問題的研究，實(shí)際上當(dāng)前只能結(jié)合具體規(guī)劃生成系統(tǒng)，針對具體問題環(huán)境，進(jìn)

行具體分析和設(shè)計(jì)。下面僅就前兩個(gè)問題，綜合進(jìn)行原則性的商量分析，在此根底上，介紹

假設(shè)干根本原理。

二.總規(guī)劃的設(shè)計(jì)與分層規(guī)劃原理

普遍常用的原則是：先產(chǎn)生一個(gè)粗略的規(guī)劃，再設(shè)法將它細(xì)化成假設(shè)干較簡單的根本級(jí)

規(guī)劃；依此類推，逐級(jí)分層，下級(jí)比上一級(jí)更精細(xì)，形成多級(jí)分層規(guī)劃(如圖7-5所示)。

假設(shè)單純從多級(jí)分層規(guī)劃結(jié)構(gòu)圖來考察,不難覺察該結(jié)構(gòu)圖客觀上具有這樣的一種特性:

假設(shè)某規(guī)劃的各級(jí)子規(guī)劃均有解，則說明該規(guī)劃已可解；相反，假設(shè)高級(jí)規(guī)劃有解，則并不

說明其隨機(jī)劃分的低級(jí)子規(guī)劃也肯定有解。事實(shí)上，按照分層規(guī)劃思想，既然高級(jí)規(guī)劃已可

解，人們也無須對它再進(jìn)行低級(jí)子規(guī)劃的分解了。

綜上所述，規(guī)劃成功可解的原理可簡敘為：在多級(jí)分層規(guī)劃中，只要任意找到一條從初

態(tài)集到目標(biāo)集的可解路徑，則該規(guī)劃可解；否則該規(guī)劃無解。上述原理的正確性驗(yàn)證顯而易

見，此處不再贅述。

三.規(guī)劃問題求解與最優(yōu)規(guī)劃原理

規(guī)劃問題求解，i般應(yīng)包含尋取解路徑和解結(jié)果兩個(gè)方面。而規(guī)劃最優(yōu)解問題則可概括

為尋取其中之一。因?yàn)樽钫_解路徑和最正確解結(jié)果是相互唯一對應(yīng)的，故知其一就可馬上

得到另一個(gè)。

假設(shè)最正確解路徑是全部解路中深度最小的，且對應(yīng)于操作序列所使用的策略集是最精

煉的，即數(shù)量上是最少的。

設(shè)D。為總規(guī)劃策略集，SP為規(guī)劃最正確解路徑上任一中間結(jié)點(diǎn)，D.為已使用的子策略集,

S為規(guī)劃的初態(tài)集，G為目標(biāo)集。則最優(yōu)規(guī)劃原理可范表達(dá)為：假設(shè)D。為最優(yōu)規(guī)劃策略集，

則余下的SP—G策略子集DC=(D0-DP)也必是最優(yōu)的。

換言之，一個(gè)最優(yōu)規(guī)劃策略集的余子集總是最優(yōu)的。

上述最優(yōu)性規(guī)劃原理也可稱作最優(yōu)性規(guī)劃定理，且可作為操作規(guī)則運(yùn)用于規(guī)劃問題求解

中。

上述定理，可用常識(shí)性推理論證如下：

已知D。是最優(yōu)的，依照最優(yōu)規(guī)劃策略集取得最小值的前提，假設(shè)S—JS,,已使用的

不肯定是最優(yōu)的，則SfS,必定存在一個(gè)對應(yīng)最正確路徑的最優(yōu)策略子集，且有

假設(shè)設(shè)不一是最優(yōu)的，則G也必定存在一個(gè)最優(yōu)策略子集?！涤谑莿t有

假設(shè)設(shè)O.不肯定是最優(yōu)的，則也必定存在一個(gè)最優(yōu)策略子集。于是有

而由已知D&=D.-Dp<D°-D'p=D；

得到D8<D；

的結(jié)論，這顯然與Dg不為最優(yōu)子集假設(shè)矛盾，故只可能。.=￡>；為對應(yīng)于最正

確解路徑的最優(yōu)策略子集。

同理，還進(jìn)一步說明了2,也必定是的最優(yōu)策略子集。需要強(qiáng)調(diào)的是，這里提

出關(guān)于最優(yōu)規(guī)劃原理及其證明的前提雖然不十分嚴(yán)密，但仍不失為既具理論意義，又有極強(qiáng)

的實(shí)踐指導(dǎo)意義的分析研究方法。這是因?yàn)椋航⒃跇O值條件下，可找到最優(yōu)解相關(guān)判據(jù)，

它是科學(xué)規(guī)律中一般自然法則。

當(dāng)然，針對具體自動(dòng)規(guī)劃系統(tǒng)，應(yīng)用最優(yōu)規(guī)劃原理分析，將成為要考察多參數(shù)、多變量

、多極值方向條件下，確定最正確解路徑的復(fù)雜問題。盡管如此，依照相關(guān)泛函知識(shí)和最優(yōu)

規(guī)劃原理綜合分析，仍可導(dǎo)出相關(guān)規(guī)劃和推理。后續(xù)深刻研究，詳見有關(guān)研究文獻(xiàn)。

四.規(guī)劃的雙序求解與診斷

依據(jù)問題規(guī)劃求解的方向，假設(shè)從初始起點(diǎn)出發(fā)，逐級(jí)前向推理，直至獲得到達(dá)目標(biāo)的

序列操作，并能完成終點(diǎn)的全部狀態(tài)條件。系統(tǒng)這種按順序方法求得解路的過程，稱為順序

規(guī)劃求解。反之，從目標(biāo)終點(diǎn)逆向推理，直至系統(tǒng)到達(dá)與初態(tài)一致的約束條件。這種反向求

解過程，稱為逆序規(guī)劃求解。順序求解和逆序求解統(tǒng)稱為雙序法。

順序規(guī)劃求解是一種順其自然方法的常規(guī)方法。而逆序規(guī)劃，依據(jù)目標(biāo)要求來驗(yàn)證前提

條件：或依據(jù)目的分析，確定必要的相應(yīng)手段與操作規(guī)則，這種思路似乎更加符合人類思

維習(xí)慣，且又稱之為“目的一一手段"規(guī)劃分析法。

例如，警衛(wèi)機(jī)器人的行動(dòng)規(guī)劃之一：機(jī)器人為了照亮房間，啟動(dòng)了電燈開關(guān)，為了應(yīng)付

入侵者，又拿起了武器；并對準(zhǔn)獵物，發(fā)出了要開槍的警告……

人們還覺察很多情況下，逆序法比順序法更易找到最正確解。例如，凡屬可范表示為樹

狀性

質(zhì)的問題，采納逆序規(guī)劃，從樹葉尋其根十分簡單，且往往得到的解就是最正確解。而采納

順序法，從根求其某片特別的葉子，卻要困難復(fù)雜得多了。

為了診斷系統(tǒng)規(guī)劃是否出錯(cuò)，通常采納逐級(jí)規(guī)劃分段測試法和雙序法相結(jié)合的方法進(jìn)行。

針對某級(jí)子規(guī)劃，可先選取逆序檢查法；假設(shè)逆序不成功，再用順序法進(jìn)行。只要其中一個(gè)

方向成功，則稱該級(jí)子規(guī)劃可解。否則，需進(jìn)一步實(shí)施微細(xì)診斷或出錯(cuò)修正。

不同的規(guī)劃系統(tǒng)，優(yōu)先選用順序法還是逆序法，要視具體情況分析再?zèng)Q策。例如，規(guī)劃

工程實(shí)驗(yàn)及設(shè)備檢修，人們常運(yùn)用輸入信號(hào)波形，逐點(diǎn)檢測追蹤的原理，實(shí)質(zhì)上即選用分段

診斷和順序查障法，這樣更便于快速查找出故障段點(diǎn)；而專利技術(shù)設(shè)計(jì)規(guī)劃，往往多用逆序

思維方法進(jìn)行。

第三節(jié)規(guī)劃搜索求解

搜索域的分層規(guī)劃

為從大型復(fù)雜問題狀態(tài)空間中，加速搜索，找到從初始狀態(tài)So到達(dá)目標(biāo)狀態(tài)SK的解，這

時(shí)，可利用問題的相關(guān)知識(shí)和啟發(fā)信息，在S。到鼠之間依序找出并選取假設(shè)干關(guān)鍵狀態(tài)Sk

(K=I,II,...,N),把SK作為從S0fSg的解路徑中的子目標(biāo)，形成fSif…

7比層層搜索，逐次逼近總目標(biāo)的求解格局。這種依照多級(jí)分層規(guī)劃思想，通過中間

序列關(guān)鍵狀態(tài)，采取層層子目標(biāo)任務(wù)遞進(jìn)的手段，到達(dá)快速順利完成總目標(biāo)搜索任務(wù)的技術(shù)，

稱為分層規(guī)劃搜索技術(shù)。該方法又稱為規(guī)劃搜索的關(guān)鍵狀態(tài)歸約法。

設(shè)原始大型問題的狀態(tài)空間范表示為三重序元組：

T=(S0,F,Ss)

式中：S。為初始狀態(tài)，鼠為目標(biāo)狀態(tài)，F(xiàn)為S。到達(dá)鼠的可供應(yīng)用的操作集。

分解為子規(guī)劃問題的各狀態(tài)空間為：

(So,Fl,Si),(SI,Fit,Sn),.......,(SKI,FK,SK)

.......,(SN-I,FN,S\),(SN,Fg,Sg)

式中，SK(K=I,II,……,N)為所引入的假設(shè)干中間關(guān)鍵狀態(tài)，并選作為N個(gè)子規(guī)劃的子

目標(biāo)；

FK(K=I,II,……,N)為對應(yīng)于子規(guī)劃的操作集子集，且￡eF.

應(yīng)用分層規(guī)劃的關(guān)鍵狀態(tài)歸納法，具有下述特點(diǎn)：

首先，可以大幅壓縮搜索空間。如圖7-6所示，B——原始大問題(S0,F,S)的全搜索空

間;

N+l

Bk一一子規(guī)劃問題(SKT,R,SK)的搜索空間。由圖可見，￡Bk〈〈B,

K=\

圖7-6分層規(guī)劃搜索

其次，對子規(guī)劃問題的求解，便于在小范圍內(nèi)應(yīng)用相關(guān)經(jīng)驗(yàn)和知識(shí)等啟發(fā)信息，提高搜

索效率。

其它，假設(shè)有些子問題已有成熟解法或已為本原問題，則更有利于加快搜索求解過程。

例如，已知用1艘船可分別解決2人與2野人或3人與3野人的規(guī)劃過河問題。現(xiàn)問用2艘

船能否解決4人與4野人或6人與6野人的過河問題。采納分解規(guī)劃，兩船同步行動(dòng)，則該

問題即可利用已有解的本原子問題快速獲解。

分層規(guī)劃搜索的并行處理

并行處理，是多個(gè)子系統(tǒng)同時(shí)啟動(dòng)的處理工作方法。它以并行方法，增大操作空間。換

取時(shí)間的縮短，是一種加快全系統(tǒng)搜索的有效手段。

例如，為了迅速從海域中搜索一艘行船，可派多個(gè)機(jī)器船及飛行器，分別在不同的海區(qū)

同時(shí)進(jìn)行掃描和搜索。

直接并行處理，適于相關(guān)子規(guī)劃初始條件相對獨(dú)立，且可滿足的搜索中。

對于那些前后次序不可顛倒，且各子問題特性不一的批量子系統(tǒng)的規(guī)劃搜索，不能直接

應(yīng)用上述處理方法。這時(shí)可采納一種稱為流水線的工作方法，使多個(gè)資源及功能操作部件各

司其職，并行協(xié)調(diào)，以便最好發(fā)揮系統(tǒng)的速度和效率。

例如，在機(jī)器人工廠中，一件產(chǎn)品，需2n道工序子規(guī)劃，每工序由功能專一的機(jī)械手或

機(jī)器人擔(dān)當(dāng)。操作中有一半工序各需耗工時(shí)to,另一半各需工時(shí)2to。現(xiàn)需批量制造該產(chǎn)品，

問如何配置機(jī)器人資源及安排崗位，可使規(guī)劃搜索系統(tǒng)獲X效率。

這時(shí)可按照生產(chǎn)工序順序排列，成為流水線作業(yè)方法，配置機(jī)器人資源及安排崗位可采

納并行處理和流水線相結(jié)合的作業(yè)規(guī)劃進(jìn)行：凡耗時(shí)為to的工序各指派一臺(tái)機(jī)器人擔(dān)當(dāng)；凡

耗時(shí)為2to的工序，則選派2臺(tái)機(jī)器人共同輪作。這樣，很簡單算得該流水線周期為to,即

從第一件產(chǎn)品輸出后，只需每經(jīng)過to的時(shí)間間隔，系統(tǒng)就產(chǎn)出一件新產(chǎn)品。

三.一個(gè)實(shí)例——魔方問題的規(guī)劃搜索求解

魔方是一種智力搜索解謎玩具，曾經(jīng)風(fēng)行全球，流傳很快很廣。據(jù)說，這是由匈牙利建

筑學(xué)家厄爾諾?魯比克設(shè)計(jì)出來的。

如圖7-7所示，這是一種由26塊小立方體組合而成的色彩六面U■，以?UUHP可山.相應(yīng)垂直

中心軸任意轉(zhuǎn)動(dòng)，從而變動(dòng)圖案。

在26塊小立方體中，每個(gè)面的中心塊，即上(U)、下(D)、前(F)、后(B)、左(L)、右

(R)6個(gè)中心塊的位置不變；其余8個(gè)角塊，12個(gè)邊塊都可以分別在繞軸轉(zhuǎn)動(dòng)中，隨意改變

位置和方向。

依據(jù)排列組合計(jì)算，這20個(gè)可動(dòng)立方體共有約4.3X10n'種選擇排列，因此要把魔方中

任意一種狀態(tài)變成某種目的狀態(tài)時(shí)，就需要在4.3義10百種可能中去搜索，可見直接求解該問

題，頗有難度。用分層規(guī)劃思想，求解該問題是一種有效手段。例如，美國人杰?諾爾斯設(shè)

計(jì)了一種五階段魔方求解法，步驟如下：

第一步：按目標(biāo)狀態(tài)調(diào)整好上邊塊的位置和顏色取向標(biāo)志；

第二步：按目標(biāo)狀態(tài)調(diào)整好上邊塊及上角塊的位置和顏色取向；

第三步：按目標(biāo)狀態(tài)注意設(shè)法保持上述成果同時(shí)，調(diào)整好中邊塊的位置顏色取向；

第四步：按目標(biāo)狀態(tài)調(diào)整底角塊位置、顏色的取向，注意調(diào)整變換中設(shè)法恢復(fù)上述成果

的己有狀態(tài)；

第五步：按目標(biāo)狀態(tài)調(diào)整變換底邊塊，使完全到達(dá)目標(biāo)狀態(tài)。

在上述變換規(guī)劃搜索步驟中，愈接近目標(biāo)狀態(tài)時(shí)，隨著須注意保持已成功的成果，記憶

調(diào)整難度也隨之加大。但由于上述操作每一步驟主要只涉及4個(gè)小立方體，使其可能的排列

組合狀態(tài)數(shù)大為減少，加之已有成熟算法求解每個(gè)子規(guī)劃搜索，故魔方問題通過規(guī)劃搜索可

以獵取成功解決。

第四節(jié)機(jī)器人規(guī)劃問題求解

指派機(jī)器人自動(dòng)選擇假設(shè)干操作，制定并執(zhí)行一個(gè)動(dòng)作序列規(guī)劃，替代人去完成給定的任

務(wù)。例如，要求機(jī)器人完成焊接，進(jìn)行特別裝配等，這類機(jī)器人，在實(shí)際中已有應(yīng)用。尤其

是人難以進(jìn)入的惡劣環(huán)境，機(jī)器人卻不懼怕。例如，充滿有害氣體的地下坑道，或是有放射

性污染試驗(yàn)場地，指派機(jī)器人替代人去搬運(yùn)一些小物體等，這類應(yīng)用更具有特別意義。

機(jī)器人工作規(guī)劃及生成方法

應(yīng)用分層規(guī)劃技術(shù)，可將機(jī)器人須完成的總?cè)蝿?wù)，分解為假設(shè)干依序排列的子任務(wù)?？?/p>

任務(wù)即總規(guī)劃，子任務(wù)即子規(guī)劃，又稱為一個(gè)過程。

機(jī)器人在滿足相應(yīng)約束條件下，選擇操作序列，按照子任務(wù)目標(biāo)的逐一完成，逐漸到達(dá)

總?cè)蝿?wù)目標(biāo)。這個(gè)總?cè)蝿?wù)完成及其指令操作序列的生成全部進(jìn)程，稱為機(jī)器人工作規(guī)劃。

其中對每一個(gè)進(jìn)程，還須認(rèn)真生成子任務(wù)工作規(guī)劃，如圖7-8所示。

＞機(jī)器人進(jìn)程子規(guī)劃

圖7-8機(jī)器人進(jìn)程子規(guī)劃

圖中，Su稱為輸入約束條件，即為進(jìn)程的全部初始條件；G,范表示為該進(jìn)程的目

j

標(biāo)狀態(tài)及其輸出條件。

生成進(jìn)程子規(guī)劃的主要方法之一，即采納關(guān)鍵狀態(tài)歸約法。該方法要求依據(jù)任務(wù)進(jìn)程分

析，選取并確定假設(shè)干關(guān)鍵中間狀態(tài)，并把這些狀態(tài)對應(yīng)選為進(jìn)程子規(guī)劃的目標(biāo)，依序分別

規(guī)劃求解，直至總目標(biāo)任務(wù)的全部完成。

例如，機(jī)器人搬運(yùn)物件，一般必須有3個(gè)進(jìn)程：

進(jìn)程1),機(jī)器人須到達(dá)要搬運(yùn)的物件對象存放地；

進(jìn)程2),機(jī)器人抓取并攜帶物件走至安放物件所在位置；

進(jìn)程3),機(jī)器人放置物件后，按指令回到指定地點(diǎn)。

上述3個(gè)進(jìn)程假設(shè)有顛倒或相關(guān)條件不滿足，就會(huì)導(dǎo)致執(zhí)行規(guī)劃的失敗。

制定或執(zhí)行進(jìn)程子規(guī)劃時(shí)，很簡單覺察：前一進(jìn)程子規(guī)劃的目標(biāo)，恰恰就是啟動(dòng)緊鄰后

一進(jìn)程規(guī)劃的初始條件，進(jìn)程的這一屬性，又稱為進(jìn)程的鏈接特性。

生成子規(guī)劃的另一重要途徑，則是依據(jù)關(guān)鍵操作確定進(jìn)程目標(biāo)和步驟的方法。

例如上例中，按關(guān)鍵操作發(fā)生的先后順序，可把機(jī)器人搬運(yùn)物件分為4個(gè)進(jìn)程：

進(jìn)程1),機(jī)器人走到物件源存放處；

進(jìn)程2),機(jī)器人在物件源存放處抓取到物件；

進(jìn)程3),機(jī)器人走向并走到物件安放處；

進(jìn)程4),機(jī)器人在指定處X放下抓取物。一

上述按關(guān)鍵操作，確定發(fā)生的狀態(tài)變遷，分析并生成進(jìn)程子規(guī)劃的方法，稱為關(guān)鍵操作

歸約法。

規(guī)劃的執(zhí)行與操作操作

當(dāng)系統(tǒng)規(guī)劃一旦生成，機(jī)器人就可以按照指令，順序執(zhí)行該規(guī)劃步驟和進(jìn)程。實(shí)際上，

機(jī)器人執(zhí)行規(guī)劃，就是機(jī)器人不斷選取操作，執(zhí)行操作的過程。當(dāng)全部操作序列執(zhí)行完畢，

到達(dá)目標(biāo)狀態(tài)。這時(shí)，如果沒有新的指令，機(jī)器人就應(yīng)能自動(dòng)停下來。

但是，在機(jī)器人執(zhí)行規(guī)劃中，如何能保證系統(tǒng)自身能X執(zhí)行全部規(guī)定的操作，并能到達(dá)

預(yù)期效果呢

事實(shí)上，僅具有開環(huán)操作功能的規(guī)劃系統(tǒng)，一般難以覺察出現(xiàn)的微小偏差。為預(yù)防這種

偏差造成系統(tǒng)的失誤，可在機(jī)器人規(guī)劃中加進(jìn)閉環(huán)操作，這是保證機(jī)器人可靠執(zhí)行規(guī)劃的關(guān)

鍵方法和技術(shù)(如圖7-9所示)。

SiO__________________圖中：

______>機(jī)器人規(guī)劃s,。一輸入約束條件，

_____>執(zhí)行機(jī)構(gòu)SiK一輸出的狀態(tài)條件,

Sib________________Sn1一檢測輸出的監(jiān)控信息條件。

反響檢測

圖7-9操作規(guī)劃劃的機(jī)事人執(zhí)行機(jī)構(gòu)

例如,煙心”工二學(xué)心M件源存放處時(shí),工作臺(tái)上出現(xiàn)了被調(diào)換的另一類危險(xiǎn)物品，這

時(shí)機(jī)器人是否仍舊發(fā)出抓取物件動(dòng)作呢顯然，如果機(jī)器人規(guī)劃缺少閉環(huán)監(jiān)測和識(shí)別操作功能

時(shí)，就可能發(fā)生抓錯(cuò)物件的事故。而對于具有視覺及檢測識(shí)別規(guī)劃的機(jī)器人來說，系統(tǒng)就可

以預(yù)防這類風(fēng)險(xiǎn)。

三.機(jī)器人過程操作與環(huán)境約束

通常，機(jī)器人選擇執(zhí)行一項(xiàng)操作時(shí)，首先總要檢測當(dāng)前狀態(tài)，是否滿足該項(xiàng)操作所要求

的約束條件，這一比較過程稱為匹配(matching)。假設(shè)狀態(tài)條件滿足，即匹配成功，則執(zhí)行

相應(yīng)選定的操作。此時(shí)，須檢測并驗(yàn)證操作前后狀態(tài)變化是否正確合理，從而刪除操作前相

關(guān)狀態(tài)，躍遷到新的狀態(tài)。另一方面，當(dāng)覺察不能匹配時(shí)，就應(yīng)放棄執(zhí)行原選定的操作或轉(zhuǎn)

入相關(guān)處理。

事實(shí)上，如果比較機(jī)器人在執(zhí)行某項(xiàng)操作前后的環(huán)境約束及狀態(tài)條件，則不難覺察：機(jī)

器人每次執(zhí)行操作，實(shí)際上只是改變了極個(gè)別相關(guān)對象的狀態(tài)，而大局部的環(huán)境狀態(tài)和約束

條件則不發(fā)生變化。因此，在機(jī)器人規(guī)劃及進(jìn)行操作條件過程中，可利用狀態(tài)變遷中的這一

特性，僅對動(dòng)態(tài)變化的的局部狀態(tài)空間予以優(yōu)先重點(diǎn)考察，而對大局部靜態(tài)約束條件只需予

以標(biāo)識(shí)保存。這樣處理好處在于，對機(jī)器人相關(guān)規(guī)劃操作，能快速進(jìn)行條件選擇與匹配，提

高規(guī)劃求解效率。例如，考察機(jī)器人裝配工作間環(huán)境，墻上貼有假設(shè)干圖片，還安放有電子

掛鐘和電鈴；窗臺(tái)上有假設(shè)干盆花，房間一角有吸塵器，，水龍頭……等。但這些環(huán)境因

素并不對機(jī)器人安裝規(guī)劃產(chǎn)生直接影響。因此，在過程規(guī)劃描述中，可將其略去，以便減少

不必要的信息檢測與處理。

第五節(jié)基于謂詞邏輯的機(jī)器規(guī)劃設(shè)計(jì)

謂詞邏輯描述作為一種人一機(jī)交互的言語形態(tài)，因其具有良好的界面特性，在人工智能

研究中應(yīng)用很廣。

一.機(jī)器人行動(dòng)規(guī)劃問題分析

alcove

vaseM規(guī)川I乙?

ab

S3rlO機(jī)器八1」

如圖7-10所示，設(shè)在一含有凹室房間內(nèi)，機(jī)器人小姐瑪麗(Mary)正在緊張工作。a處和

b處各有一茶桌(Teatable)，其中a桌放有一只花瓶，花迄中插有一束鮮花；b處有剛剛進(jìn)

門入座的貴賓羅西(Roxi)。現(xiàn)在要求機(jī)器人小姐完成的主要任務(wù)是：為范表達(dá)本公司對客人

的歡迎，馬上把花獻(xiàn)給入座的貴賓前。要求規(guī)劃機(jī)器人這一行動(dòng)過程。

這一過程母然可以采納搜索、語義網(wǎng)絡(luò)、框架等方法描述求解。比較起來，選用謂詞邏

輯規(guī)劃求解，可以生動(dòng)擬人動(dòng)作過程。首先分析行動(dòng)過程并規(guī)劃關(guān)鍵步驟，主要有：

步驟1,描述房間環(huán)境狀態(tài)，用以范表達(dá)機(jī)器人工作現(xiàn)場背景及變遷過程狀態(tài)遷移。其

中尤其包含描述初始狀態(tài)及確定目標(biāo)狀態(tài)。

步驟2,確定機(jī)器人需進(jìn)行的假設(shè)干關(guān)鍵操作。機(jī)器人可供選擇的操作有言語、范表情、

動(dòng)作等，其中行動(dòng)動(dòng)作是關(guān)鍵。而可選擇的動(dòng)作有行走、抓物、放物等。關(guān)鍵操作的選擇需

要依據(jù)行動(dòng)的目的與效果的分析。

步驟3,確定實(shí)施關(guān)鍵操作的地點(diǎn)。對象及進(jìn)行先后順序，匹配規(guī)劃等。這是一個(gè)更為

復(fù)雜的綜合性問題。稍有過失，還會(huì)出現(xiàn)荒唐的現(xiàn)場局面：例如，機(jī)器人動(dòng)作順序顛倒，到

a處取花，卻到b處打翻并取走了客人的茶杯。因此，規(guī)劃操作要求X、嚴(yán)密、執(zhí)行操作前后,

都應(yīng)檢查約束條件匹配狀況和預(yù)期的效果是否到達(dá)。

步驟4,規(guī)劃的優(yōu)化和補(bǔ)充。例如謂詞狀態(tài)描述，只要求定義與要完成的任務(wù)相關(guān)局部

的謂詞，過多的狀態(tài)和操作定義可能造成干擾和冗余，不利于系統(tǒng)高效運(yùn)行。另一方面，由

于經(jīng)驗(yàn)缺少，開始定義的謂詞狀態(tài)及選擇謂詞操作，可能不夠，則可以在規(guī)劃設(shè)計(jì)中進(jìn)行補(bǔ)

充和調(diào)整。

二.機(jī)器人行動(dòng)規(guī)劃狀態(tài)與操作設(shè)計(jì)

在上述分析根底上，即可對圖7T0機(jī)器人行動(dòng)規(guī)劃問題進(jìn)行設(shè)計(jì)。

首先定義范表達(dá)狀態(tài)的謂詞邏輯。

TEATABLE(x)：x是茶臺(tái)

CLEAR(X)：x上是空的

EMPTY(y)：y手中是空的

HOLDS(y,z)：y手中拿著z

ON(z,x)：z放在x之上

AT(y,x)：y在x附近

其中，各謂詞變元的值域?yàn)椋簒e{a,b,alcove,vase)

y￡{mary,roxi)

z￡{vase,flower)

問題的初始狀態(tài)可范表示為：

So：AT(mary,alcove)AAT(roxi,b)AEMPTY(mary)

EMPTY(roxi)AON(vase,a)AON(FLOWER,VASE)

TEATABLE(a)ATEATABLE(b)ACLEAR(b)

問題的目標(biāo)狀態(tài)為：

Sg：AT(mary,alcove)AAT(roxi,b)AEMPTY(mary)

EMPTY(roxi)AON(vase,a)AON(flower,b)

TEATABLE(a)ATEATABLE(b)ACLEAR(vase)

機(jī)器人行動(dòng)規(guī)劃的目標(biāo)是通過執(zhí)行一個(gè)操作序列，把問題的初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)。

操作可分為約束條件和行為動(dòng)作兩個(gè)局部，只有滿足相應(yīng)的約束條件，才可選擇一個(gè)對應(yīng)的

動(dòng)作，同時(shí)，把當(dāng)前狀態(tài)變換為新的狀態(tài)。

為此，要完本錢例機(jī)器人行動(dòng)規(guī)劃，必須執(zhí)行下述根本操作：

fI：GOTO(y,x)----y走到x近前

f2:PICK-UP(y,z)——y拿起z

f3:SET-DOWN(y,z)——y放下z

嚴(yán)格來說，系統(tǒng)還可以規(guī)劃許多附加復(fù)雜操作，例如，從禮儀角度，機(jī)器人小姐獻(xiàn)花時(shí)

應(yīng)問候行禮，富有范表情；貴賓接受獻(xiàn)花出于禮貌和尊重，應(yīng)該站立起來，并范表示感謝等。

但由于這些操作并不影響主要步驟的進(jìn)行，為突出關(guān)鍵事件狀態(tài)變遷，本例簡化了假設(shè)干操

作行為。

三項(xiàng)根本謂詞操作改變的狀態(tài)差異如下：

fi：GOTO(y.x)

匹配條件：AT(y,Tx)

動(dòng)作發(fā)生：刪除：AT(y,-Jx)

增加：AT(y,x)

f2：PICK-UP(y,z)

匹配條件1)：ON(z,x)AAT(y,x)AEMPTY(y)

動(dòng)作發(fā)生，刪除：ON(z,x)AEMPTY(y)

增加：CLEAR(x)AHOLDS(y,z)

匹配條件2)：0N(z,w)A0N(w,x)AAT(y,x)AEMPTY(y)

動(dòng)作發(fā)生，刪除:ON(z,w)AEMPTY(y)

增加1：CLEAR(w)AHOLDS(y)

f3：SET-DOWN(y,z)

匹配條件1):AT(y,x)ACLEA(x)AHOLDS(y,z)

動(dòng)作發(fā)生，刪除：CLEAR(x)AHOLDS(y,z)

增加：ON(y,z)AEMPTY(y)

或匹配條件2)：AT(yi,x)AAT(y2,x)AHOLDS(yi,z)EMPTY(y2)

動(dòng)作發(fā)生，刪除：HOLDS3,z)/\EMPTY(yz)

增加：EMPTY(yi)AII0LDS(y2,z)

有時(shí)為了增加規(guī)劃操作可靠性，可以增加相關(guān)匹配約束條件。只有相關(guān)約束條件全部滿

足時(shí)，動(dòng)作才會(huì)發(fā)生。

三.機(jī)器人行動(dòng)規(guī)劃過程設(shè)計(jì)

為了到達(dá)機(jī)器人行動(dòng)規(guī)劃的目標(biāo)狀態(tài)，必須逐漸完成從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的過程轉(zhuǎn)

換。按上例要求，該問題須依序完成下述5個(gè)子目標(biāo)規(guī)劃過程。

P,：機(jī)器人執(zhí)行操作從凹室走到a桌旁，以能滿足機(jī)器人取花動(dòng)作發(fā)生前所必須的約

束條件

P2：機(jī)器人為了拿花，檢查子目標(biāo)，是否符合。為到達(dá)S”則操作fz,即在a處拿到花

束，到達(dá)子目標(biāo)S2；

PB：S?滿足，則機(jī)器人執(zhí)行操作3從a處走到b處，取得獻(xiàn)花前的打算條件S3；

P-K檢查&是否滿足，假設(shè)到達(dá)，可執(zhí)行操作心，完成獻(xiàn)花任務(wù)，到達(dá)狀態(tài)&；

Ps：S,滿足，機(jī)器人執(zhí)行操作3,回歸原位，到達(dá)目標(biāo)狀態(tài)S?。

上述過程可簡單示意如圖7-11：

SiS2S4Sg

So

PlP2P3P4P5

rS7-11-TTUTrF?/亍動(dòng)規(guī)劃U4'土'''

按照上述過程規(guī)劃，用謂詞邏輯描述的機(jī)器人行動(dòng)規(guī)劃過程如下：

AT(mary,alcove)AAT(roxi,b)AEMPTY(mary)

EMPTY(roxi)AON(vase,a)AON(flower,vase)

TEATABLE(a)ATEATABLE(b)ACLEAR(b)

■QjGOTO(mary,a)

AT(mary,a)AAT(roxi,b)AEMPTY(mary)

EMPTY(roxi)AON(vase,a)AON(flower,vase)

TEATABLE(a)ATEATABLE(b)ACLEAR(b)

PICK-UP(mary,flower)

AT(mary,a)AAT(roxi,b)AHOLDS(mary,flower)

EMPTY(roxi)AON(vase,a)ACLEAR(vase)

TEATABLE(a)ATEATABLE(b)ACLEAR(b)

QjGOTO(mary,b)

AT(mary,b)AAT(roxi,b)AHOLDS(mary,flower)

EMPTY(roxi)AON(vase,a)ACLEAR(vase)

TEATABLE(a)ATEATABLE(b)ACLEAR(b)

01SET-DOWN(mary,flower)

AT(mary,b)AAT(roxi,b)AEMPTY(mary)

HOLDS(roxi,flower)AON(vase,a)ACLEAR(vase)

TEATABLE(a)ATEATABLE(b)ACLEAR(b)

通SET-DOWN(roxi,flower)。UGOTO(marjsalcove)

AT(mary,alcove)AAT(roxi,b)AEMPTY(mary)

EMPTY(roxi)AON(vase,a)ACLEAR(vase)

TEATABLE(a)ATEATABLE(b)AON(flower,b)

程序說明：

(1)為了迅速到達(dá)目標(biāo)狀態(tài)，在匹配條件同時(shí)滿足情況下，上述P5過程，應(yīng)用了并行處

理技術(shù)：使機(jī)器人瑪麗走回凹室的操作及機(jī)器人羅西(Roxi)放下花的動(dòng)作并行完成，加速系

統(tǒng)運(yùn)行的效率。當(dāng)然，也可以將兩項(xiàng)操作分兩步串行處理完成，直至到達(dá)目標(biāo)狀態(tài)結(jié)束。

(2)在程序運(yùn)行過程中，有些靜止?fàn)顟B(tài)自始至終并未改變，例如TEATABLE(a)和TEATABLE