基于復(fù)合行動(dòng)的智能服務(wù)機(jī)器人任務(wù)規(guī)劃

基于復(fù)合行動(dòng)的智能服務(wù)機(jī)器人任務(wù)規(guī)劃

由于廣闊的應(yīng)用前景，服務(wù)機(jī)器人受到了廣泛的關(guān)注和深入研究。近年來，服務(wù)機(jī)器人的集成和智能技術(shù)得到了很大進(jìn)展。同時(shí)，隨著服務(wù)機(jī)器人任務(wù)的復(fù)雜性和任務(wù)多樣性的發(fā)展，對(duì)服務(wù)機(jī)器人任務(wù)規(guī)劃也提出了挑戰(zhàn)。近年來，國內(nèi)外科學(xué)家主要采用具有自動(dòng)論證能力和規(guī)劃能力的任務(wù)規(guī)劃模塊來處理這些問題。文獻(xiàn)指出，服務(wù)機(jī)器人的一般控制軟件應(yīng)該包括服務(wù)機(jī)器人的獨(dú)立決策者，即任務(wù)規(guī)劃級(jí)別。缺點(diǎn)是，提案的決策者沒有具備自動(dòng)論證和規(guī)劃的能力，需要手動(dòng)決策。在此基礎(chǔ)上，開發(fā)和實(shí)現(xiàn)了具有定制協(xié)調(diào)的服務(wù)機(jī)器人體系結(jié)構(gòu)（kejia），任務(wù)規(guī)劃模塊由完整編程語言（answ沙盒編程，簡(jiǎn)稱api）執(zhí)行。在文獻(xiàn)中，行動(dòng)語言c-用于描述服務(wù)機(jī)器人的提取計(jì)劃，行動(dòng)語言c-用于描述服務(wù)機(jī)器人的任務(wù)計(jì)劃。在文獻(xiàn)中，行動(dòng)語言c-用于描述服務(wù)機(jī)器人的提取計(jì)劃，行動(dòng)語言c-用于執(zhí)行多機(jī)器人間的公共任務(wù)計(jì)劃。在實(shí)現(xiàn)機(jī)器人任務(wù)規(guī)劃模塊時(shí)，與使用無意義編程的方法相比，使用無意義語言c-的方法具有表達(dá)方式簡(jiǎn)單、意義清晰、開發(fā)過程直觀、便利性強(qiáng)的特點(diǎn)。在應(yīng)用語言c+的解算器方面，經(jīng)過一段時(shí)間的開發(fā)，解算器cpus2asp通過將動(dòng)作語言轉(zhuǎn)換為響應(yīng)集程序來執(zhí)行，比文獻(xiàn)[5.11]中使用的解算器ccalc的效率進(jìn)一步提高。在使用行動(dòng)語言或回答集編程的方式進(jìn)行機(jī)器人任務(wù)規(guī)劃時(shí),首先需要根據(jù)機(jī)器人的硬件及底層感知-控制系統(tǒng),將機(jī)器人的基本行動(dòng)表達(dá)為對(duì)應(yīng)的行動(dòng)符號(hào).例如,將移動(dòng)能力表達(dá)為move,抓取和放下物體的能力表達(dá)為pickup以及putdown等.在實(shí)際的機(jī)器人應(yīng)用中,任務(wù)通過語音交互等方式指定之后,任務(wù)規(guī)劃系統(tǒng)會(huì)進(jìn)行自動(dòng)規(guī)劃,得出完成這個(gè)任務(wù)的行動(dòng)序列.之后,機(jī)器人只需執(zhí)行這個(gè)序列就可以完成指定的任務(wù).但是,通過直接描述機(jī)器人的基本行動(dòng)來進(jìn)行推理和規(guī)劃的方式也存在一些不足:首先,在具體規(guī)劃過程中,這樣的方式顯得比較復(fù)雜,而且不太直觀.例如,對(duì)于任務(wù)“幫我取來一杯熱水”,任務(wù)規(guī)劃系統(tǒng)會(huì)直接根據(jù)機(jī)器人基本能力的描述進(jìn)行搜索,最終給出一個(gè)詳細(xì)的基本行動(dòng)序列,這個(gè)序列反映了采用基本的行動(dòng)序列來完成任務(wù)的完整方法.但是人類對(duì)這個(gè)任務(wù)的解決會(huì)基于一些“高層的”行動(dòng),例如首先獲取(fetch)一杯水,然后對(duì)其進(jìn)行加熱(heat),最后將其送過來(bring).這樣的方式更加直觀,易于理解,同時(shí)也更加快捷;其次,與采用了高層行動(dòng)的規(guī)劃序列相比一個(gè)完成任務(wù)的完整序列一般比較長(zhǎng),求解這樣一個(gè)規(guī)劃也會(huì)顯著地增加求解時(shí)間.為了在表達(dá)和求解效率上進(jìn)一步提高機(jī)器人的任務(wù)規(guī)劃能力,我們引入復(fù)合行動(dòng)對(duì)行動(dòng)語言C+進(jìn)行擴(kuò)展一個(gè)復(fù)合行動(dòng)是在一定條件之下的基本行動(dòng)的順序執(zhí)行.直觀上,復(fù)合行動(dòng)表達(dá)的正是能夠用于解決規(guī)劃問題的“高層行動(dòng)”.例如,對(duì)于之前描述的任務(wù),我們可以將機(jī)器人從一個(gè)位置將物體取到另一個(gè)位置定義成一個(gè)復(fù)合行動(dòng).其具體內(nèi)容為:首先,如果機(jī)器人和目標(biāo)物體不在同一個(gè)位置,那么機(jī)器人移動(dòng)到這個(gè)位置,之后,依次執(zhí)行抓取物體、移動(dòng)到目標(biāo)位置、放下物體的行動(dòng).在具體規(guī)劃過程中,這些復(fù)合行動(dòng)直接參與構(gòu)成最終的規(guī)劃序列,這些復(fù)合行動(dòng)同時(shí)也包含了其構(gòu)成的所有基本行動(dòng),使得機(jī)器人可以直接執(zhí)行這個(gè)規(guī)劃序列.在經(jīng)典規(guī)劃領(lǐng)域,國內(nèi)外學(xué)者對(duì)采用復(fù)合行動(dòng),如宏行動(dòng)(macroaction),來改進(jìn)規(guī)劃求解效率的方式進(jìn)行了深入的研究.這些工作中,描述行動(dòng)的改變和推理都基于STRIPS,或者規(guī)劃領(lǐng)域描述語言(PDDL).這些框架由于自身的限制,對(duì)行動(dòng)的間接效果或慣性特性的表達(dá)和處理比較困難,難以直觀地描述系統(tǒng)中的行動(dòng)并且在這些系統(tǒng)中的宏行動(dòng)主要基于任務(wù)分解的方式,而不是作為類似基本行動(dòng)的結(jié)構(gòu)參與規(guī)劃.基于情形演算(situationcalculus)的編程語言Golog引入了類似復(fù)合行動(dòng)的結(jié)構(gòu),但是Golog中的結(jié)構(gòu)描述的是一個(gè)問題求解的整個(gè)框架.這個(gè)框架在求解中用于減小搜索空間,并不出現(xiàn)在最后的規(guī)劃結(jié)果中.文獻(xiàn)中提出的“復(fù)雜行動(dòng)”丟掉了詳細(xì)執(zhí)行細(xì)節(jié),因此具體執(zhí)行時(shí)還需要將其轉(zhuǎn)換成基本行動(dòng)的序列.更重要的是,上述工作都基于單調(diào)邏輯系統(tǒng),不適用于機(jī)器人的規(guī)劃領(lǐng)域.機(jī)器人在執(zhí)行任務(wù)時(shí),隨時(shí)可以通過自身的感知和人機(jī)對(duì)話等手段獲取新的知識(shí).這些知識(shí)很可能與機(jī)器人的原始知識(shí)庫有沖突,在單調(diào)的邏輯系統(tǒng)中,這些沖突會(huì)使得整個(gè)系統(tǒng)產(chǎn)生不一致,因此很難用于進(jìn)一步規(guī)劃.而在基于非單調(diào)邏輯的推理系統(tǒng),例如行動(dòng)語言C+或回答集編程中這些知識(shí)可以很方便地加入到知識(shí)庫,進(jìn)一步用于將來的規(guī)劃,符合容變(elaborationtolerance)的要求.在非單調(diào)邏輯的框架下,文獻(xiàn)[22,23]的工作都涉及到類似復(fù)合行動(dòng)的結(jié)構(gòu).但文獻(xiàn)的工作只是將Golog中類似復(fù)合行動(dòng)的結(jié)構(gòu)在回答集編程下進(jìn)行表達(dá),作為規(guī)劃過程的一個(gè)啟發(fā)式信息;文獻(xiàn)中的復(fù)合行動(dòng)只能是一個(gè)固定長(zhǎng)度的基本行動(dòng)的相繼執(zhí)行,不能通過條件來限定其是否執(zhí)行,并且沒有對(duì)復(fù)合行動(dòng)擴(kuò)展的可靠性及完備性加以論證.對(duì)于采用復(fù)合行動(dòng)進(jìn)行擴(kuò)展后的行動(dòng)語言C+,我們討論了它的各種性質(zhì),并建立了擴(kuò)展的行動(dòng)語言及其所表達(dá)的轉(zhuǎn)移系統(tǒng)的關(guān)系,進(jìn)一步證明了擴(kuò)展后系統(tǒng)的可靠性和完備性.同時(shí),我們也擴(kuò)展了求解系統(tǒng)cplus2asp增加了對(duì)復(fù)合行動(dòng)的支持,并且在實(shí)驗(yàn)中進(jìn)行了測(cè)試.實(shí)驗(yàn)結(jié)果表明,對(duì)于復(fù)雜的任務(wù),采用復(fù)合行動(dòng)的描述對(duì)求解效率有比較顯著的改進(jìn).1基礎(chǔ)知識(shí)1.1原子中c+v的定義一個(gè)(多值的命題)基調(diào)(signature)是一個(gè)符號(hào)的集合uf073,叫做常量集,以及一個(gè)與uf073不同的非空有限符號(hào)集合Dom(c).集合Dom(c)是uf073的值域.uf073中的每個(gè)常量c都被指派到Dom(c)中的一個(gè)值.原子是形如c=v的表達(dá)式,其中,cuf0ceuf073,vuf0ceDom(c)表達(dá)“c的值是v”.公式是原子的命題組合.基調(diào)的解釋I是將該基調(diào)中所有元素映射到其值域的函數(shù),如果I(c)=v,那么我們說解釋I滿足原子c=v,或I將原子c=v解釋為真.I對(duì)公式的可滿足性的解釋符合經(jīng)典命題邏輯中對(duì)命題組合公式以及連接詞的解釋.一條因果規(guī)則是形如Fuf0dcG的規(guī)則,其中,F和G都是公式,分別叫做該因果規(guī)則的頭和體.這條規(guī)則的直觀解釋為“當(dāng)G為真時(shí),有一個(gè)原因?qū)е翭”.一個(gè)因果理論是一個(gè)有限的因果規(guī)則的集合.定義1.對(duì)于一個(gè)因果理論T和一個(gè)其基調(diào)的解釋I,T相對(duì)于I的規(guī)約(reduct)TI是T中所有的規(guī)則體被I滿足的那些規(guī)則的頭部集合.如果I是集合TI的唯一模型,那么我們說I是T的模型.1.2基于行動(dòng)常發(fā)生的因果規(guī)則行動(dòng)語言C+的(多值)基調(diào)uf073中的常量分為行動(dòng)常量(actionconstant)和變式常量(fluentconstant).變式常量還可以分為簡(jiǎn)單變式常量(simplefluentconstant)和靜態(tài)確定變式常量(staticallydeterminedconstant).對(duì)于一個(gè)確定的基調(diào)uf073,如果一個(gè)公式中所有出現(xiàn)的常量都是變式常量,那么這個(gè)公式被稱為變式公式;否則,如果一個(gè)公式中含有至少一個(gè)行動(dòng)常量并且沒有變式常量,那么這個(gè)公式被稱為行動(dòng)公式.一個(gè)行動(dòng)描述由一個(gè)因果律的集合組成,因果律包含如下兩種形式的表達(dá)式:uf0b7第1種形式的表達(dá)式形如其中,F和G是公式.如果它們都是變式公式,那么這個(gè)因果律被稱為靜態(tài)律;如果F是行動(dòng)公式,那么這個(gè)因果律被稱為行動(dòng)動(dòng)態(tài)律.靜態(tài)律通常用于描述變式之間的關(guān)系,表達(dá)行動(dòng)的間接效果;行動(dòng)動(dòng)態(tài)律用于表達(dá)行動(dòng)本身的性質(zhì),或者行動(dòng)與其他行動(dòng)以及變式之間的關(guān)系.uf0b7第2種形式的表達(dá)式形如其中,F和G是變式公式,并且F中不包含靜態(tài)確定的變式常量;H是一個(gè)公式.該因果律叫做變式動(dòng)態(tài)律.變式動(dòng)態(tài)律通常用于描述規(guī)劃系統(tǒng)中行動(dòng)的直接效果.由公式(1)和公式(2)可以定義很多縮略因果律,例如表達(dá)式其中,a是行動(dòng)常量,表示causedFifTrueafterauf0d9G.其他有用的表達(dá)式包括:其中,c是變式常量.該表達(dá)式叫做慣性律,表示causedcifcafterc,通常用于表達(dá)變式的慣性性質(zhì),以及其中,a是行動(dòng)常量.該表達(dá)式表示因果律causedaifa,causeduf0d8aifuf0d8a,用于表達(dá)規(guī)劃系統(tǒng)中行動(dòng)的性質(zhì),以及其中,a是行動(dòng)常量.該表達(dá)式表示因果律causedaifa,和表達(dá)式其中,H是行動(dòng)公式,F是變式公式.該表達(dá)式表示causedFalseifTrueafterHuf0d9F.行動(dòng)描述D可以轉(zhuǎn)化成為一個(gè)有限的因果理論Dm(m≥0)的集合,這個(gè)集合定義了D的語義.Dm的基調(diào)是序?qū):c的集合,其中,當(dāng)c為變式常量時(shí),有iuf0ce{0,…,m},表達(dá)了這個(gè)因果理論中所有的狀態(tài);當(dāng)c為行動(dòng)常量時(shí)有iuf0ce{0,…,m-1},表達(dá)了因果理論中所有的行動(dòng).因果理論Dm中的因果規(guī)則包括如下3個(gè)部分:1)對(duì)每一條形如公式(1)的因果律,規(guī)則集i:Fuf0dci:G,如果該因果律是D的靜態(tài)律,那么iuf0ce{0,…,m};如果它是行動(dòng)動(dòng)態(tài)律,那么iuf0ce{0,…,m-1};2)對(duì)每一條變式動(dòng)態(tài)律(2),規(guī)則集i+1:Fuf0dc(i+1:G)uf0d9(i:H),其中,iuf0ce{0,…,m-1};3)對(duì)每一個(gè)簡(jiǎn)單變式常量c及其值vuf0ceDom(c),規(guī)則集0:c=vuf0dc0:c=v.因果理論Dm的模型對(duì)應(yīng)于D所表示的轉(zhuǎn)移圖中一條長(zhǎng)為m的路徑(見文獻(xiàn)中的命題8),這條路徑中包含m+1個(gè)狀態(tài)和m個(gè)行動(dòng).當(dāng)用行動(dòng)語言來描述機(jī)器人的任務(wù)規(guī)劃系統(tǒng)時(shí),需要將機(jī)器人的基本功能表達(dá)為行動(dòng)語言中的行動(dòng)常量,并且通過因果律將這些基本行動(dòng)常量的功能表達(dá)出來.例1:考慮一個(gè)具有移動(dòng)和抓取能力的機(jī)器人,可以將物體移動(dòng)到各個(gè)地方.我們采用如下的行動(dòng)和變式常量對(duì)其進(jìn)行建模:基本行動(dòng)Move(l)表達(dá)機(jī)器人可以移動(dòng)到l,Pickup(s)表示機(jī)器人可以將s拿起,Putdown(s)表示機(jī)器人可以將s放下;慣性變式Loc(o)用于表達(dá)物體o的位置,Hold(s)表達(dá)機(jī)器人持有s.上述行動(dòng)描述的第1行表達(dá)了兩個(gè)變式Loc(o)和Hold(s)具有慣性性質(zhì),即如果沒有外部行動(dòng)改變,那么它們的值保持不變.第2行表達(dá)了對(duì)應(yīng)的3個(gè)行動(dòng)是外生的(exogenous),即在任何一個(gè)時(shí)刻,這些行動(dòng)都可以發(fā)生或不發(fā)生.第3行是靜態(tài)律,表達(dá)了變式Loc(l)和變式Hold(s)以及Loc(Robot)的關(guān)系,實(shí)際上表達(dá)了行動(dòng)的間接效果.例如,在機(jī)器人持有s時(shí),機(jī)器人執(zhí)行行動(dòng)Move除了會(huì)直接導(dǎo)致機(jī)器人本身的位置發(fā)生變化以外,還會(huì)間接導(dǎo)致s的位置發(fā)生變化.其余部分分別表達(dá)了對(duì)應(yīng)行動(dòng)的直接效果和執(zhí)行條件.設(shè)luf0ce{L1,L2},ouf0ce{Robot,S},suf0ce{S},我們得到了行動(dòng)描述D0.圖1表達(dá)了4D0的一個(gè)模型.當(dāng)采用行動(dòng)語言C+進(jìn)行具體的規(guī)劃問題求解時(shí),一個(gè)規(guī)劃問題被分成了兩部分:第1部分是對(duì)于整個(gè)規(guī)劃問題的行動(dòng)描述,例如D0;第2部分是對(duì)于這個(gè)規(guī)劃問題初始狀態(tài)以及目標(biāo)狀態(tài)的表達(dá),主要是一些變式的值例如,對(duì)于D0的描述,給定初始狀態(tài)機(jī)器人在L1位置,S在L2位置,并且機(jī)器人手抓為空.目標(biāo)狀態(tài)為:機(jī)器人手抓為空,S在L1位置.經(jīng)過對(duì)應(yīng)的編碼之后,這部分與行動(dòng)描述部分一起經(jīng)過cplus2asp求解,就可以得到一個(gè)規(guī)劃的行動(dòng)序列.對(duì)于上述的具體規(guī)劃問題,求解出來的行動(dòng)序列正如圖1中的邊所示,即機(jī)器人首先移動(dòng)到L2,之后抓取S,然后移動(dòng)到L1,最后在L1放下S.規(guī)劃過程中整個(gè)系統(tǒng)的狀態(tài)變化如圖1中的頂點(diǎn)所示.2復(fù)合行為擴(kuò)展行為語言2.1擴(kuò)展的行動(dòng)描述考慮行動(dòng)語言C+的一個(gè)子集,包括F和G都是變式公式的靜態(tài)律(1)、形如公式(5)的行動(dòng)動(dòng)態(tài)律、形如公式(3)、公式(4)和公式(7)的變式動(dòng)態(tài)律.給定這個(gè)子集上的行動(dòng)描述D和它的一個(gè)變式常量集合uf073fl,以及行動(dòng)常量集合uf073act.一個(gè)擴(kuò)展的行動(dòng)描述D+是在D中引入一個(gè)復(fù)合行動(dòng)常量集合uf073comp,以及如下形式的復(fù)合行動(dòng)定義規(guī)則:其中,buf0ceuf073comp,叫做復(fù)合行動(dòng)常量;a0,…,akuf0ceuf073ac,t叫做復(fù)合行動(dòng)b的子行動(dòng);aj是b的第j個(gè)子行動(dòng);E0,…,Ek是變式公式.這個(gè)規(guī)則表達(dá)執(zhí)行復(fù)合行動(dòng)b等價(jià)于在E0成立的時(shí)候首先執(zhí)行a0,然后在E1成立的時(shí)候接著執(zhí)行a1,...最后在Ek成立的時(shí)候執(zhí)行ak.特別地,如果相應(yīng)的條件Ei不成立,那么對(duì)應(yīng)的ai被跳過不執(zhí)行.例2:我們引入復(fù)合行動(dòng)Fetch(s,l)對(duì)例1進(jìn)行擴(kuò)展:復(fù)合行動(dòng)Fetch(s,l)表示機(jī)器人將物品s直接運(yùn)送到位置l,并且還完整定義了這個(gè)復(fù)合行動(dòng)的執(zhí)行細(xì)節(jié):如果機(jī)器人不在s的位置,那么首先移動(dòng)到s的位置;如果機(jī)器人本身和s在同一個(gè)位置,那么不需要移動(dòng).之后,機(jī)器人拿起s,移動(dòng)到位置l,最后放下s.2.2md10中的規(guī)則我們規(guī)定,與基本行動(dòng)一樣,一個(gè)復(fù)合行動(dòng)在規(guī)劃的執(zhí)行過程中也花費(fèi)一個(gè)時(shí)間周期.因此在規(guī)劃過程中機(jī)器人會(huì)優(yōu)先選擇相應(yīng)的復(fù)合行動(dòng),從而減小規(guī)劃步長(zhǎng),提高規(guī)劃效率.那么,由于復(fù)合行動(dòng)本身包含了其中基本行動(dòng)的執(zhí)行細(xì)節(jié),我們需要將一個(gè)時(shí)間周期擴(kuò)展為一個(gè)二維的結(jié)構(gòu).對(duì)一個(gè)擴(kuò)展的行動(dòng)描述D+,令k*是其中所有形如公式(8)的定義中最大的k值,uf0730是所有復(fù)合行動(dòng)定義中子行動(dòng)ai的集合.與D類似,我們也將D+轉(zhuǎn)換到的一個(gè)有限的因果理論序列mD(10)(m≥0),通過這個(gè)因果理論序列定義其語義.轉(zhuǎn)換的具體過程如下所述:首先,我們?cè)谝粋€(gè)時(shí)間周期(i,i+1)中增加k*個(gè)子時(shí)間點(diǎn)i,1,…,i.k*,將其劃分成k*+1個(gè)子周期,即這樣,復(fù)合行動(dòng)中的所有執(zhí)行細(xì)節(jié)都可以在一個(gè)周期內(nèi)得到解釋.我們規(guī)定,每個(gè)常量在增加的k*個(gè)子時(shí)間點(diǎn)上也有取值.那么,mD(10)的基調(diào)包括所有Dm的基調(diào)中出現(xiàn)的符號(hào)以及如下序?qū)?1)i.j:at,其中,iuf0ce{0,…,m-1},juf0ce{0,…,k*},atuf0ceuf0730;2)i.j:c,其中,iuf0ce{0,…,m-1},juf0ce{1,…,k*},c是D中的變式常元.mD(10)中的規(guī)則包括:1)Dm中除了從公式(4)轉(zhuǎn)換來的規(guī)則以外的所有規(guī)則.這些規(guī)則表明,對(duì)于mD(10),其中的基本行動(dòng)的執(zhí)行依然要花費(fèi)一個(gè)時(shí)間周期.2)對(duì)每一條靜態(tài)律(1)以及iuf0ce{0,…,m-1},juf0ce{1,…,k*},增加規(guī)則該規(guī)則表示在每一個(gè)子時(shí)間點(diǎn)上,由靜態(tài)律規(guī)定的兩個(gè)變式公式之間的關(guān)系依然成立,因此,在子時(shí)間點(diǎn)上,行動(dòng)產(chǎn)生的間接效果依然成立.3)對(duì)每條變式動(dòng)態(tài)律(4)以及iuf0ce{0,…,m-1},juf0ce{1,…,k*-1},vuf0ceDom(c),增加規(guī)則這些規(guī)則表示慣性規(guī)則被表達(dá)成一組在子周期上成立的慣性規(guī)則,從而使得在增加的時(shí)間點(diǎn)上取值的變式也遵從慣性律.4)對(duì)每一條復(fù)合行動(dòng)定義(8),增加如下規(guī)則:4.1)對(duì)iuf0ce{0,…,m-1},增加如果k=k*,那么還增加其中,行動(dòng)常量aj(0≤j≤k)都出現(xiàn)在公式(3)中,或者它們是H中唯一的行動(dòng)常量;(i:H)*是將i:H中的行動(dòng)常量i:a替換成i.0:a而得到的.這些規(guī)則表達(dá)當(dāng)行動(dòng)被復(fù)合行動(dòng)觸發(fā)時(shí),可在子周期上產(chǎn)生與其作為基本行動(dòng)一樣的效果.另外,如果一個(gè)復(fù)合行動(dòng)的子行動(dòng)數(shù)目小于k*+1個(gè),那么在這個(gè)復(fù)合行動(dòng)的k+1個(gè)子行動(dòng)都執(zhí)行之后,就沒有行動(dòng)繼續(xù)執(zhí)行了.其中改變的變式的值,通過公式(3)中定義的子周期上的慣性定律傳遞到下一個(gè)時(shí)間周期.例如,k*=2表示行動(dòng)描述中的一個(gè)復(fù)合行動(dòng)最多可能有3個(gè)子行動(dòng).復(fù)合行動(dòng)b的定義為bisa;a.如果b在周期(i,i+1)執(zhí)行,那么,在(i,i.1)和(i.1,i.2)周期會(huì)執(zhí)行a,產(chǎn)生相應(yīng)的效果;而在(i.2,i+1)的子周期沒有任何基本行動(dòng)執(zhí)行.執(zhí)行兩次a產(chǎn)生的效果直接由i.2時(shí)間點(diǎn)通過公式(3)定義的慣性規(guī)則傳遞到i+1.4.2)對(duì)每一個(gè)動(dòng)態(tài)變式規(guī)則(7),并且其中H包含不止a0一個(gè)行動(dòng)常量,那么對(duì)于iuf0ce{0,…,m-1},增加其中,Hab0是將H中所有出現(xiàn)的a0全部替換成b而得到的.這條規(guī)則表明,一個(gè)復(fù)合行動(dòng),如果它的第0個(gè)子行動(dòng)和其他的行動(dòng)不能同時(shí)執(zhí)行,那么這個(gè)行動(dòng)與包含該子行動(dòng)的復(fù)合行動(dòng)也不能同時(shí)執(zhí)行,這樣可以避免復(fù)合行動(dòng)與其他基本行動(dòng)之間的沖突.例如,對(duì)復(fù)合行動(dòng)b的第0個(gè)子行動(dòng)a,有約束a和c不能同時(shí)執(zhí)行,那么,同樣地復(fù)合行動(dòng)b和c也不能同時(shí)執(zhí)行,這樣可以維護(hù)原始行動(dòng)描述本身的約束.4.3)對(duì)每一個(gè)iuf0ce{0,…,m-1},juf0ce{1,…,k},tuf0ce{0,…,k},增加這些規(guī)則表達(dá)任何復(fù)合行動(dòng)都是默認(rèn)可執(zhí)行的.在條件Ej成立時(shí),相應(yīng)的子行動(dòng)被“觸發(fā)”,并且復(fù)合行動(dòng)不能與其子行動(dòng)對(duì)應(yīng)的基本行動(dòng)同時(shí)執(zhí)行.5)對(duì)于iuf0ce{0,…,m-1},juf0ce{0,…,k*}以及atuf0ceuf0730,增加這條規(guī)則表明,任何復(fù)合行動(dòng)的子行動(dòng)默認(rèn)是不執(zhí)行的,它們只能被復(fù)合行動(dòng)在相應(yīng)條件成立的時(shí)候觸發(fā).6)對(duì)于iuf0ce{0,…,m},bm,bnuf0ceuf073comp,增加這條規(guī)則限定了任意兩個(gè)復(fù)合行動(dòng)不能同時(shí)執(zhí)行.例3:例2中的(D0)+可以翻譯成因果理論(D0)m(10)的集合(默認(rèn)iuf0ce{0,…,m-1},juf0ce{1,…,k*-1=2}):1)mD0中除了慣性律轉(zhuǎn)換成的規(guī)則之外的所有規(guī)則.2)靜態(tài)律如causedLoc(s)=lifHold(s)uf0d9Loc(Robot)=l被翻譯成如下規(guī)則集(tuf0ce{1,2,3}):3)慣性律被翻譯成公式(11).例如,inertialLoc(o)=l被翻譯成如下規(guī)則集:4)Move(l)causesLoc(Robot)=l被翻譯成如下規(guī)則集(tuf0ce{0,1,2}):5)nonexecutableMove(l)ifLoc(Robot)=l被翻譯成如下規(guī)則:6)從公式(9)我們可以得到如下規(guī)則集(僅考慮前兩個(gè)子行動(dòng)):7)對(duì)于所有子行動(dòng),例如Move(l),需要增加如下規(guī)則(tuf0ce{0,1,2,3}):3uf0auf0a3f1和3f3a3f1的聯(lián)系本節(jié)研究擴(kuò)展的行動(dòng)語言的性質(zhì).與文獻(xiàn)對(duì)原始行動(dòng)語言C+性質(zhì)的表達(dá)類似,我們主要通過與擴(kuò)展的行動(dòng)語言C+對(duì)應(yīng)的轉(zhuǎn)移系統(tǒng)來刻畫其性質(zhì).一個(gè)基調(diào)的解釋I可以表達(dá)為形如c=I(c)的原子的集合,即,將其中的原子都解釋成真的集合.這樣,行動(dòng)描述mD(10)的模型可以表達(dá)為其中,e0,…,em-1是uf073act的解釋,s0,...,sm,si.1,...,si.k*是uf073fl的解釋,而eiuf0a2.0,...,eiuf0a2.k*是uf0730的解釋.對(duì)任意m≥0,我們將mD(10)的模型都稱為D+的模型.一個(gè)狀態(tài)是一個(gè)uf073fl的解釋s,使得0:s是0D(10)的模型.狀態(tài)是mD(10)所表達(dá)的轉(zhuǎn)移圖上的頂點(diǎn).轉(zhuǎn)移圖的邊(轉(zhuǎn)移)通過1D(10)的模型來定義.實(shí)際上,1D(10)的模型可以表達(dá)為例如,例2中的(D0)1(10)的一個(gè)模型可以表達(dá)為(略去解釋為假的那些行動(dòng)常量):一個(gè)顯式轉(zhuǎn)移是一個(gè)三元組uf0e1s,e,suf0a2uf0f1,其中,s和suf0a2是uf073fl的解釋,e是uf073actuf0c8uf073comp的解釋,并且(0:s)uf0c8(0:e)uf0c8(1:suf0a2)是1D(10)的某個(gè)模型的子集.如果有某個(gè)buf0ceuf073comp滿足e(b)=t,那么uf0e1s,e,suf0a2uf0f1叫做復(fù)合轉(zhuǎn)移,否則叫做簡(jiǎn)單轉(zhuǎn)移.一個(gè)轉(zhuǎn)移擴(kuò)展是一個(gè)元組uf0e1s,euf0a20,s1,...,sk*,euf0a2k*,suf0a2uf0f1,其中,ieuf0a2是uf0730的解釋,si是uf073fl的解釋,并且集合(0:s)uf0c8(0.0:euf0a20)uf0c8(0.1:s1)uf0c8...uf0c8(0.k*:sk*)uf0c8(0.k*:euf0a2k*)uf0c8(1:suf0a2)是1D(10)的某個(gè)模型的子集.一個(gè)轉(zhuǎn)移擴(kuò)展可以看做是k*+1個(gè)如下形式的三元組列表:uf0e1s,euf0a20,s1uf0f1,...,uf0e1sk*,euf0a2k*,suf0a2uf0f1.每一個(gè)這樣的三元組稱為一個(gè)隱式轉(zhuǎn)移.如果對(duì)于任意b的子行動(dòng)aj(0≤j≤k),euf0a2j(aj)(28)f都成立,那么這個(gè)轉(zhuǎn)移擴(kuò)展叫做關(guān)于b的平凡轉(zhuǎn)移擴(kuò)展.D+所表達(dá)的轉(zhuǎn)移圖中的邊由1D(10)的模型所表達(dá)的轉(zhuǎn)移組成.根據(jù)以上定義,對(duì)于擴(kuò)展的行動(dòng)語言描述,有如下性質(zhì)成立:命題1.對(duì)于任意顯式轉(zhuǎn)移uf0e1s,e,suf0a2uf0f1或隱式轉(zhuǎn)移uf0e1s,eiuf0a2,suf0a2uf0f1,s和suf0a2都是一個(gè)狀態(tài).該命題是文獻(xiàn)中命題7在D+中的增強(qiáng).其有效性也依賴于如下事實(shí):靜態(tài)確定的變式不能出現(xiàn)在變式動(dòng)態(tài)律(2)的頭部.這條命題表明,顯示轉(zhuǎn)移或隱式轉(zhuǎn)移都可以對(duì)應(yīng)到轉(zhuǎn)移系統(tǒng)中的一條長(zhǎng)度為1的路徑.文獻(xiàn)的命題8描述了D與其對(duì)應(yīng)的因果理論的模型之間的聯(lián)系.對(duì)于擴(kuò)展的行動(dòng)描述D+,其與對(duì)應(yīng)的因果理論的模型之間也有類似的關(guān)系.命題2.對(duì)任意m>0,基于mD(10)的基調(diào)的一個(gè)解釋公式(20)是mD(10)的模型,當(dāng)且僅當(dāng)對(duì)0≤i≤m-1,每個(gè)三元組uf0e1si,e,si+1uf0f1都是一個(gè)顯式轉(zhuǎn)移,每個(gè)元組uf0e1si,eiuf0a2.0,si.1,...,si.k*,euf0a2k*,si(10)1uf0f1都是一個(gè)轉(zhuǎn)移擴(kuò)展.根據(jù)命題1和命題2,對(duì)于任意的m,mD(10)的模型都可以表達(dá)成D所對(duì)應(yīng)的轉(zhuǎn)移系統(tǒng)中的一條長(zhǎng)為m的路徑以及這條路徑上的復(fù)合轉(zhuǎn)移對(duì)應(yīng)的隱式轉(zhuǎn)移構(gòu)成的路徑集合.因此,一個(gè)擴(kuò)展的行動(dòng)描述可以用于表達(dá)一個(gè)轉(zhuǎn)移系統(tǒng).下面我們研究原始行動(dòng)描述與擴(kuò)展行動(dòng)描述的轉(zhuǎn)移之間的關(guān)系.定義1(相對(duì)轉(zhuǎn)移).對(duì)原始的行動(dòng)描述D和采用復(fù)合行動(dòng)擴(kuò)展之后的行動(dòng)描述D+:(i)對(duì)于D+中的一個(gè)轉(zhuǎn)移t=uf0e1s,e,suf0a2uf0f1,t相對(duì)于D的轉(zhuǎn)移是三元組t-=uf0e1s,e-,suf0a2uf0f1,其中,e-是uf073act的解釋.如果t是一個(gè)顯式轉(zhuǎn)移,那么對(duì)任意auf0ceuf073act,e(a)=e(a);如果t是一個(gè)隱式轉(zhuǎn)移,那么對(duì)于任意auf0ceuf0730,e(a)=e(a);對(duì)于其他auf0ceuf073act,e-(a)=f;(ii)對(duì)于D中的一個(gè)轉(zhuǎn)移t=uf0e1s,e,suf0a2uf0f1,t相對(duì)于D+的轉(zhuǎn)移是三元組t+=uf0e1s,e+,suf0a2uf0f1,其中,e+是uf073actuf0c8uf073comp的解釋,并且對(duì)于任意auf0ceuf073act,e+(a)=e(a);對(duì)于任意auf0ceuf073comp,e+(a)=f.可以看到,在原始的行動(dòng)描述和擴(kuò)展之后的行動(dòng)描述之間,相對(duì)轉(zhuǎn)移都是一一對(duì)應(yīng)的.相對(duì)轉(zhuǎn)移可以方便地刻畫原始行動(dòng)描述和擴(kuò)展行動(dòng)描述的轉(zhuǎn)移之間的關(guān)系.命題3.對(duì)原始行動(dòng)描述D和采用復(fù)合行動(dòng)擴(kuò)展之后的行動(dòng)描述D+,有:(i)對(duì)D中的任何一個(gè)轉(zhuǎn)移t,其相對(duì)于D+的轉(zhuǎn)移t+都是D+中的一個(gè)簡(jiǎn)單轉(zhuǎn)移;(ii)對(duì)D+中的任何一個(gè)簡(jiǎn)單轉(zhuǎn)移或隱式轉(zhuǎn)移t,其相對(duì)于D的轉(zhuǎn)移t-是D中的轉(zhuǎn)移.命題3表明,對(duì)于D的任意一個(gè)轉(zhuǎn)移,D+中都有一個(gè)轉(zhuǎn)移與之對(duì)應(yīng),反之亦然.同時(shí),該命題還表明,D+中的一個(gè)轉(zhuǎn)移擴(kuò)展可以對(duì)應(yīng)到D的轉(zhuǎn)移系統(tǒng)中的一條長(zhǎng)為k*+1的路徑.圖2表達(dá)了(D0)1(10)的模型(22),其中的虛線表示隱式轉(zhuǎn)移.可以看到,所有的隱式轉(zhuǎn)移都對(duì)應(yīng)了圖1中的轉(zhuǎn)移,模型(22)中的轉(zhuǎn)移擴(kuò)展對(duì)應(yīng)了圖1中一條長(zhǎng)為4的路徑.根據(jù)文獻(xiàn)的定義,對(duì)行動(dòng)描述D和Duf0a2,D的基調(diào)是Duf0a2基調(diào)的子集,將Duf0a2的狀態(tài)和轉(zhuǎn)移限制在D的基調(diào)上如果所構(gòu)成的新的轉(zhuǎn)移系統(tǒng)與D的轉(zhuǎn)移系統(tǒng)同構(gòu),則稱D是Duf0a2的子描述.命題4.令D是一個(gè)基于基調(diào)uf073的行動(dòng)描述,b是一個(gè)不在uf073中的常量.如果Duf0a2是基于基調(diào)uf073uf0c8的行動(dòng)描述并且是由在D中添加一條b的復(fù)合行動(dòng)定義規(guī)則(8)構(gòu)成的,滿足b的子行動(dòng)都是uf073中的行動(dòng)常量,那么D是D的子描述.例如,對(duì)例2中的行動(dòng)描述(D0)+,我們?nèi)サ羝渲信cFetch(s,l)相關(guān)的描述規(guī)則之后,得到的行動(dòng)描述的轉(zhuǎn)移系統(tǒng)與D0對(duì)應(yīng)的轉(zhuǎn)移系統(tǒng)是同構(gòu)的.多次應(yīng)用命題4,我們可以得出D是D+的子描述.因此,它們的模型是相互關(guān)聯(lián)的.下面我們根據(jù)D和D+的模型之間的關(guān)系,討論D+對(duì)于D的擴(kuò)展的完備性和可靠性.定義2(模型擴(kuò)張).對(duì)任意m≥0,原始行動(dòng)描述D的一個(gè)模型M=(0:s0)uf0c8(0:e0)uf0c8(1:s1)uf0c8…uf0c8(m:sm)相對(duì)于D+的模型擴(kuò)張是集合Muf0a2(28)(0:s0)uf0c8(0:e0(10))uf0c8(1:s1)uf0c8...uf0c8(m:sm),其中,任意一個(gè)三元組uf0e1s,eiuf0a2,suf0a2uf0f1都是D中的轉(zhuǎn)移uf0e1s,ei,suf0a2uf0f1相對(duì)于D+的轉(zhuǎn)移.我們可以通過模型擴(kuò)張來描述D和D+的模型的關(guān)系,如果對(duì)于D的任意模型,其模型擴(kuò)張是D+的某個(gè)模型的子集,那么我們稱D+對(duì)D擴(kuò)展是完備的.定理1.D+對(duì)D的擴(kuò)展是完備的.完備性定理表明,對(duì)于原始的行動(dòng)描述,采用復(fù)合行動(dòng)進(jìn)行擴(kuò)展之后,原來系統(tǒng)的任何模型都可以在新的系統(tǒng)中表達(dá)出來.事實(shí)上,新的系統(tǒng)中可能還有其他的模型.因此,對(duì)于實(shí)際應(yīng)用中的機(jī)器人規(guī)劃,采用復(fù)合行動(dòng)擴(kuò)展之后,進(jìn)行任務(wù)規(guī)劃時(shí)不會(huì)出現(xiàn)原始系統(tǒng)能夠計(jì)算出規(guī)劃結(jié)果而新的系統(tǒng)中無解的情況.定義3(模型約減).對(duì)任意擴(kuò)展行動(dòng)描述D+的一個(gè)表達(dá)成公式(20)形式的模型M,其相對(duì)于D的模型約減是集合Muf0a2(28)(0:s0)uf0c8(0:e0-)uf0c8(1:s1)uf0c8...uf0c8(n:sn)(n≥m),其中,任意一個(gè)三元組uf0e1s,ei-,suf0a2uf0f1都是D+中的簡(jiǎn)單轉(zhuǎn)移或隱式轉(zhuǎn)移uf0e1s,ei,suf0f1相對(duì)于D的轉(zhuǎn)移.模型約減也可用來表達(dá)D+和D的模型之間的聯(lián)系.如果D+的任意一個(gè)模型相對(duì)于D的模型約減都是D的模型,那么我們稱D+對(duì)D的擴(kuò)展是可靠的.定理2.D+對(duì)D的擴(kuò)展是可靠的.可靠性定理表明,在使用復(fù)合行動(dòng)對(duì)于行動(dòng)描述的擴(kuò)展中,并沒有引入與原來的描述不一致的內(nèi)容.因此在實(shí)際的服務(wù)機(jī)器人規(guī)劃中,我們可以保證在通過復(fù)合行動(dòng)進(jìn)行知識(shí)擴(kuò)展和更新的過程中,所有的新知識(shí)都與原系統(tǒng)一致,可以進(jìn)一步用于此后的任務(wù)規(guī)劃.4keja1中的行動(dòng)Cplus2asp系統(tǒng)的求解主要分為兩部分,根據(jù)文獻(xiàn)中的描述,首先是將一個(gè)行動(dòng)描述,包括其初始狀態(tài)和目標(biāo)狀態(tài)的變式描述,一起翻譯成一個(gè)回答集程序,之后,采用回答集編程的高效求解器,例如clasp來進(jìn)行求解,并將得到的回答集轉(zhuǎn)化成相應(yīng)的規(guī)劃.在翻譯成回答集程序的過程中,首先對(duì)給定的m,需要將行動(dòng)描述D轉(zhuǎn)化成對(duì)應(yīng)的因果理論Dm的集合,并將這個(gè)集合中的每一個(gè)因果規(guī)則對(duì)應(yīng)翻譯成回答集程序中的語句.我們擴(kuò)展的支持復(fù)合行動(dòng)的cplus2asp程序也符合這個(gè)流程,采用第2.2節(jié)中的方法,我們將擴(kuò)展的復(fù)合行動(dòng)定義規(guī)則轉(zhuǎn)化成因果理論規(guī)則,并且實(shí)現(xiàn)了這些因果理論規(guī)則向回答集的轉(zhuǎn)換.最后,通過調(diào)用回答集編程的求解器,對(duì)整個(gè)回答集程序進(jìn)行求解,將得到的結(jié)果轉(zhuǎn)化成具體的規(guī)劃行動(dòng)序列.為了研究擴(kuò)展的行動(dòng)語言C+用于服務(wù)機(jī)器人的具體規(guī)劃效率,我們采用服務(wù)機(jī)器人可佳(KeJia)中運(yùn)行的實(shí)際規(guī)劃問題進(jìn)行實(shí)驗(yàn).可佳的硬件系統(tǒng)中包括一個(gè)自由移動(dòng)平臺(tái)、一個(gè)機(jī)械手臂和手抓以及一個(gè)能夠臨時(shí)放置小物體的盤子.通過人機(jī)對(duì)話,可佳獲取人的需求,根據(jù)需要完成一些簡(jiǎn)單的家務(wù),例如移動(dòng)一些小物體、送飲料等,并且可佳還能操作常用的家用電器,例如微波爐.目前,基于可佳的硬件系統(tǒng)已經(jīng)實(shí)現(xiàn)的基本行動(dòng)包括移動(dòng)到指定位置、抓取和放下指定物體等,我們將所有可佳可以實(shí)現(xiàn)的基本行動(dòng)表示為如下符號(hào):Move(l),Pickup(s),Putdown(s),Open(m),Close(m),Putin(s,m)Takeout(s,m)以及Start(m),分別表示移動(dòng)到指定位置l、抓起指定物體m、放下物體s、打開機(jī)器m的門(例如微波爐)、關(guān)閉m的門、將s放到m里面、將s從m中拿出來以及啟動(dòng)m.此外,根據(jù)可佳的感知系統(tǒng),在上述某些行動(dòng)執(zhí)行后,可佳也可以觀察到運(yùn)行的實(shí)際狀態(tài)的改變.我們采用一些變式來描述這些狀態(tài)的變化.目前可以感知的變式包括描述物體以及自身位置的變式Loc(o)=l、描述小物體是否在容器內(nèi)部的變式Inside(c)=s等.根據(jù)以上的行動(dòng)和變式符號(hào),行動(dòng)Putin(s,m)的效果和可執(zhí)行條件可以描述如下:第1行的兩條因果律表達(dá)執(zhí)行行動(dòng)Putin(s,m)之后,物體s將置于m內(nèi)部,并且機(jī)器人的手抓中不再有任何物體.后面兩行表示,如果s不在機(jī)器人的手抓中、或者機(jī)器人和m不在同一個(gè)位置以及m的門沒有打開、或m中已經(jīng)不是空的,那么行動(dòng)Putin(s,m)都不能執(zhí)行.我們可以類似地表達(dá)其他各個(gè)行動(dòng).以及采用靜態(tài)律來表達(dá)變式之間的關(guān)系.我們將這樣的行動(dòng)描述記為描述KeJia1.由于可佳也經(jīng)常完成一些使用家用電器的任務(wù),因此我們?cè)诿枋鯧eJia1中引入操作電器的復(fù)合行動(dòng),使用某些家用電器的基本步驟有一些相似性.即“首先將物體放入機(jī)器中,之后將其門關(guān)上,然后啟動(dòng)機(jī)器,過一定時(shí)間之后,再打開門,將物體取出來”.根據(jù)這個(gè)模式,用微波爐(M)加熱食物(f)可以表達(dá)如下:同樣地,使用洗衣機(jī)(W)來洗衣服(c)也可以表達(dá)為實(shí)際上,這兩類復(fù)合行動(dòng)都是模式,根據(jù)相應(yīng)的參數(shù)會(huì)生成不同的復(fù)合行動(dòng)實(shí)例.例如,對(duì)于復(fù)合行動(dòng)Heat(f,M),如果在場(chǎng)景中有兩個(gè)可以加熱的實(shí)物以及兩臺(tái)微波爐,那么實(shí)際上我們定義了4個(gè)不同的復(fù)合行動(dòng)在具體的求解過程中,復(fù)合行動(dòng)的模式會(huì)根據(jù)具體的參數(shù)自動(dòng)地進(jìn)行實(shí)例化.我們將這兩類復(fù)合行動(dòng)的描述直接加入到KeJia1中,形成行動(dòng)描述KeJia2.根據(jù)機(jī)器人可以移動(dòng)的位置的數(shù)目、可以抓取的物體的數(shù)目以及完成任務(wù)的類型(移動(dòng)物體、加熱食物、洗衣服等)的不同配置,我們隨機(jī)生成了240組初始狀態(tài)和目標(biāo)狀態(tài)的集合即240個(gè)不同的具體任務(wù)配置.對(duì)于其中每一個(gè)配置,我們分別將行動(dòng)描述Kejia1和Kejia2與其組合成一組具體的規(guī)劃任務(wù).對(duì)于每一組這樣的規(guī)劃任務(wù),我們采用原始的cplus2asp系統(tǒng)求解Kejia1描述的任務(wù),采用我們擴(kuò)展實(shí)現(xiàn)的cplus2asp系統(tǒng)來求解Kejia2描述的任務(wù),并且對(duì)結(jié)果進(jìn)行對(duì)比.一個(gè)典型的任務(wù)配置,如在場(chǎng)景中有5件待洗衣物、4樣未加熱食物、機(jī)器人、微波爐、洗衣機(jī)以及其他物體處于各自的初始位置.要求機(jī)器人通過規(guī)劃完成清洗所有的衣物,并且將所有食物都加熱好,送到對(duì)應(yīng)的位置.在實(shí)驗(yàn)過程中,我們?cè)O(shè)置最大求解時(shí)間為30分鐘,最大的求解步長(zhǎng)為50步,即如果50個(gè)行動(dòng)還不能完成這個(gè)任務(wù),那么我們認(rèn)為該任務(wù)無解.實(shí)驗(yàn)在一臺(tái)Inteli7950CPU,4GRAM的Linux機(jī)器上進(jìn)行.對(duì)于每一個(gè)配置,我們分別記錄了采用兩種行動(dòng)描述進(jìn)行規(guī)劃,得到一個(gè)規(guī)劃解的時(shí)間和步長(zhǎng).有34個(gè)配置,采用兩種描述都不能在規(guī)定的時(shí)間內(nèi)得出結(jié)果.對(duì)于其他的任務(wù)配置,經(jīng)過檢驗(yàn),所有得出的規(guī)劃解都是正確的.我們根據(jù)KeJia1對(duì)具體規(guī)劃任務(wù)成功求解時(shí)的規(guī)劃步長(zhǎng)進(jìn)行分類,將所有規(guī)劃任務(wù)分成了5類.對(duì)每一類規(guī)劃步長(zhǎng)表示采用KeJia1求解這些問題得出的解的長(zhǎng)度范圍,超時(shí)數(shù)目表示在對(duì)應(yīng)的類別中,使用KeJia1的描述在規(guī)定時(shí)間內(nèi)沒有求解出來結(jié)果、但是使用KeJia2求解出來的問題的數(shù)目.KeJia1和KeJia2用時(shí)分別表示對(duì)同一類問題采用兩種描述求解的平均時(shí)間,加速比表示對(duì)同一個(gè)任務(wù)配置分別采用KeJia1和KeJia2得到一個(gè)解的時(shí)間比值的平均值,對(duì)于超時(shí)問題,沒有加入計(jì)算.具體結(jié)果見表1.表1表明,當(dāng)只要求解步長(zhǎng)大于25時(shí),采用復(fù)合行動(dòng)的描述總是比原始行動(dòng)的描述