劉曉峰,李 欣,曾志勇

(1.吉林省教育學(xué)院 綜合部,長春 130022;2.東北師范大學(xué) 計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院,長春 130117)

在智能規(guī)劃問題中,用規(guī)劃尺度(plan metric)描述衡量規(guī)劃解的質(zhì)量.如“能量消耗最少”是一個(gè)尺度[1-3],根據(jù)該尺度,能量消耗為50單位的規(guī)劃解優(yōu)于能量消耗為60單位的規(guī)劃解.帶有規(guī)劃尺度的問題要求規(guī)劃算法在多個(gè)可行規(guī)劃中找到較優(yōu)甚至最優(yōu)的規(guī)劃解.一個(gè)尺度M為任一規(guī)劃解π隱式定義了一個(gè)尺度值計(jì)算函數(shù)CM(通常CM(π)∈)和該函數(shù)值域上的全序關(guān)系<,使規(guī)劃算法能比較多個(gè)規(guī)劃解的優(yōu)劣.然而,當(dāng)規(guī)劃問題存在多個(gè)尺度時(shí),衡量規(guī)劃解的優(yōu)劣存在困難.假設(shè)存在兩個(gè)尺度M1和M2,兩個(gè)規(guī)劃解π1和π2具有如下特征：

CM1(π1)

Fox等[2]將多個(gè)尺度分別加權(quán)、 線性組合形成一個(gè)混合尺度解決了π1和π2的優(yōu)劣性問題,如

CM3(π)=w1×CM1(π)+w2×CM2(π).

但該方法存在兩個(gè)問題：

1) 線性組合多尺度的意義不明確；

2) 僅能表達(dá)尺度的相對重要性,不能表達(dá)尺度的絕對重要性.

對于問題1),由于每個(gè)尺度所評估的特征實(shí)際含義不同,因此將多尺度線性組合的實(shí)際含義難理解.此外,在上述線性組合中如果一個(gè)尺度的權(quán)重大,則表明該尺度值的變化量對混合尺度的影響大,但權(quán)重的相對大小無法表示最希望優(yōu)化的尺度.

為解決上述問題,本文提出一種使用順序(ordinal order)建模多尺度規(guī)劃問題的方法將多個(gè)尺度按順序排列表示它們均有順序性的相對重要性：排列在前的尺度最重要,如對于前述的規(guī)劃解π1和π2,如果尺度M1排在M2前,則π1優(yōu)于π2;如果M2排在M1前,則π2優(yōu)于π1.基于順序的方法能處理各尺度值計(jì)算函數(shù)值域不同的情況,從而有更強(qiáng)的建模能力,并能表示尺度的絕對重要性,使規(guī)劃算法優(yōu)先根據(jù)重要的尺度尋找較優(yōu)的規(guī)劃解.

基于本文提出的順序排序多尺度方法,可以將“規(guī)劃解長度最短”這個(gè)尺度加入到目前帶動(dòng)作代價(jià)的規(guī)劃問題(planning with action costs)[4]和帶數(shù)值變量的規(guī)劃問題(planning with numeric variables)[5]中.規(guī)劃算法將“規(guī)劃解長度最短”作為默認(rèn)的尺度能避免多數(shù)規(guī)劃系統(tǒng)面臨的當(dāng)規(guī)劃解代價(jià)為零時(shí)陷入寬度優(yōu)先搜索的問題[6].

1 智能規(guī)劃的基本概念

一個(gè)規(guī)劃任務(wù)(planning task)表示為T=(V,A,s0,sG),其中:V表示變量的集合,每個(gè)變量v具有相應(yīng)的有限值域Dv;A表示可用的動(dòng)作集合,一個(gè)動(dòng)作a定義了執(zhí)行該動(dòng)作時(shí)變量的取值約束及該動(dòng)作開始執(zhí)行后對變量取值的改變;s0是一個(gè)變量賦值函數(shù),表示初始狀態(tài),對任一v∈V滿足s0(v)∈Dv;sG表示一個(gè)對部分變量有定義的賦值函數(shù),說明在目標(biāo)狀態(tài)中變量的期望取值.動(dòng)作序列π=〈a0,a1,…,an-1〉在狀態(tài)s上應(yīng)用的結(jié)果是一個(gè)狀態(tài)s′,s′是在s0上依次執(zhí)行動(dòng)作a0,a1,…,an-1得到的結(jié)果,也可表示為s′=π(s0).如果π(s0)滿足目標(biāo)條件sG,即對于在sG中有定義的任一變量v滿足π(s0)(v)=sG(v),則動(dòng)作序列π稱為規(guī)劃解[7-8].

一個(gè)規(guī)劃尺度M通常定義在規(guī)劃任務(wù)的某個(gè)特征變量上,要求該特征取值最大化或最小化.如在PDDL語言中,“: metric minimizev”表示希望變量v的取值最小.對兩個(gè)不同的規(guī)劃解π和π′,如果π(s0)(v)<π′(s0)(v),則π優(yōu)于π′.在STRIPS規(guī)劃中,經(jīng)常關(guān)注的一個(gè)尺度是“規(guī)劃解長度(plan length)最小化”.規(guī)劃解長度表示該規(guī)劃解所含動(dòng)作的數(shù)目.在時(shí)態(tài)規(guī)劃中,一個(gè)重要的尺度是“規(guī)劃解的運(yùn)行時(shí)間最小化”[2].

2 順序多尺度規(guī)劃問題

2.1 規(guī)劃問題模型

定義1一個(gè)多尺度規(guī)劃任務(wù)表示為T=(V,A,s0,sG,ME),其中ME表示順序排列的多個(gè)尺度,形式為〈M1,M2,…,Mk〉,每個(gè)尺度Mi(i=1,2,…,k)對應(yīng)一個(gè)二元組(CMi(·),<),CMi將每個(gè)動(dòng)作序列π映射到實(shí)數(shù)集上的一個(gè)實(shí)數(shù),<表示定義在上的小于關(guān)系.

例1規(guī)劃任務(wù)T有順序尺度〈M1,M2〉,對于兩個(gè)規(guī)劃解π和π′,有

CM1(π)=2,CM2(π)=1,CM1(π′)=1,CM2(π′)=3,

則根據(jù)定義4,π′優(yōu)于π.但如果定義混合尺度

CM3(·)= 2×CM1(·)+1×CM2(·),

盡管M1的權(quán)重比M2的權(quán)重高,卻無法依據(jù)CM3判斷π和π′的優(yōu)劣.

為了描述順序多尺度規(guī)劃任務(wù),本文擴(kuò)展了智能規(guī)劃領(lǐng)域定義語言PDDL的語法和語義.

2.2 支持順序多尺度的PDDL語言擴(kuò)展

文獻(xiàn)[2,9-10]在PDDL的版本2.1(PDDL2.1)中提出了帶有規(guī)劃尺度的規(guī)劃任務(wù)描述形式(參見文獻(xiàn)[2]附錄A.4).本文在此基礎(chǔ)上進(jìn)行擴(kuò)展,添加支持順序多尺度的語法,記為PDDL2.1+OM,語法描述如下：

〈problem〉∷=(define (problem 〈name〉)

(: domain 〈name〉)

[〈require-def〉];

[〈object declaration〉]

〈init〉

〈goal〉

[〈metric-spec〉]

[〈length-spec〉])

〈object declaration〉∷=

(: objects 〈typed list (name)〉)

〈init〉∷=(: init 〈init-el〉_)

〈init-el〉∷=〈literal(name)〉

〈init-el〉∷=: fluents (= 〈f-head〉 〈number〉)

〈goal〉∷=(: goal 〈GD〉)

〈metric-spec〉∷=

(: metric 〈optimization〉〈ground-f-exp〉+)

〈optimization〉∷=ordinal-minimize

〈optimization〉∷=ordinal-maximize

〈ground-f-exp〉∷=

(〈binary-op〉〈ground-f-exp〉

〈ground-f-exp〉)

〈ground-f-exp〉∷=(-〈ground-f-exp〉)

〈ground-f-exp〉∷=〈number〉

〈ground-f-exp〉∷=

(〈function-symbol〉〈name〉_)

〈ground-f-exp〉∷=total-time

〈ground-f-exp〉∷=plan-length

〈ground-f-exp〉∷=〈function-symbol〉.

下面解釋PDDL2.1+OM的新語義.

1) 本文將PDDL2.1的語法〈optimization〉∷=minimize和〈optimization〉∷=maximize分別更改為〈optimization〉∷=ordinal-minimize和〈optimization〉∷=ordinal-maximize,表示要求規(guī)劃算法找到順序尺度下的最優(yōu)解.將PDDL2.1的語法〈metric-spec〉∷=(: metric 〈optimization〉〈ground-f-exp〉)改為〈metric-spec〉∷=(: metric〈optimization〉〈ground-f-exp〉+),允許多尺度的順序聲明(PDDL2.1僅支持單個(gè)尺度表達(dá)式,而PDDL2.1+OM支持多個(gè)尺度表達(dá)式).

2) 本文語法添加了〈ground-f-exp〉∷=plan-length,其中plan-length表示規(guī)劃解的長度,即規(guī)劃解包含的動(dòng)作數(shù)目.該語法允許將STRIPS規(guī)劃解的長度作為優(yōu)化尺度.

PDDL2.1+OM支持單尺度、 加權(quán)組合的混合尺度和順序多尺度,比PDDL2.1具有更強(qiáng)的建模能力.如果一個(gè)具體的規(guī)劃任務(wù)僅關(guān)注單個(gè)尺度的優(yōu)化,如規(guī)劃長度,則可采用形如(: metric ordinal-minimize plan-length)的表達(dá)式;如果關(guān)注多尺度的加權(quán)組合,則可采用形如(: metric ordinal-minimize (+(×2(total-time))(plan-length)))的表達(dá)式.如果希望表示total-time尺度絕對比plan-length尺度重要,則可采用形如(: metric ordinal-minimize (total-time)(plan-length))的表達(dá)式.因此,有：

結(jié)論1任何能由PDDL2.1描述的規(guī)劃任務(wù)均能由PDDL2.1+OM描述.

用PDDL2.1的規(guī)劃尺度語法描述一個(gè)具有相同最優(yōu)解的順序多尺度規(guī)劃任務(wù)較難,本文將說明該問題的復(fù)雜度是#PSPACE-hard.

定義6假設(shè)有語言L描述的規(guī)劃任務(wù)T和語言L′描述的規(guī)劃任務(wù)T′,如果T和T′具有相同的最優(yōu)解集合,則稱T和T′為最優(yōu)解等價(jià).

定理1用PDDL2.1語言描述順序多尺度規(guī)劃任務(wù)的復(fù)雜度為#PSPACE-hard.

證明：相當(dāng)于證明任意一個(gè)用PDDL2.1+OM描述的順序多尺度規(guī)劃任務(wù)的描述T,構(gòu)造一個(gè)用PDDL2.1描述的與T等價(jià)的描述復(fù)雜度為#PSPACE-hard.用DL(T)表示規(guī)劃任務(wù)T在語言L下的描述.

下面給出構(gòu)造T的PDDL2.1描述DPDDL2.1(T)方法.因?yàn)镈PDDL2.1(T)除了尺度表達(dá)式部分都可以由T的描述DPDDL2.1+OM(T)中復(fù)制,所以只需計(jì)算DPDDL2.1(T)需要優(yōu)化的尺度表達(dá)式即可.假設(shè)T的最優(yōu)解集合為

(1)

定理1給出了建立DPDDL2.1(T)最優(yōu)解等價(jià)描述DPDDL2.1+OM(T)的一個(gè)正確但不完備的算法.本文假設(shè)式(1)是一個(gè)線性方程,但由式(1)組成的方程組可能無解,從而無法得到期望的DPDDL2.1+OM(T).為了解決該問題,可假設(shè)方程(1)是非線性的,相應(yīng)的求解難度將增大.定理1的另一個(gè)問題是其沒有根據(jù)全部的動(dòng)作序列π給出混合尺度函數(shù),這將導(dǎo)致那些不是規(guī)劃解動(dòng)作序列的尺度值無法預(yù)測.

3 順序多尺度規(guī)劃問題求解方法

假設(shè)1任一尺度Mi對應(yīng)的函數(shù)Cmi對任一動(dòng)作序列π和π′=cons(π,〈a〉)滿足Cmi(π)≤Cmi(π′),則可構(gòu)造如下Greedy Best-first算法計(jì)算順序多尺度規(guī)劃任務(wù)的滿意解.

首先,定義一個(gè)函數(shù)is_goal(s)判斷狀態(tài)s是否為目標(biāo)狀態(tài),即如果s為目標(biāo)狀態(tài),則該函數(shù)返回“真”,否則返回“假”.

算法1多尺度規(guī)劃求解算法.

初始化:

1) 分別建立一個(gè)空的open表和空的closed表,用于記錄待擴(kuò)展的狀態(tài)和已擴(kuò)展的狀態(tài);

2) 將初始狀態(tài)s0放入open表,計(jì)算s0的順序尺度值向量(cm1(s0),cm2(s0),…,cmk(s0)).

循環(huán)執(zhí)行如下步驟: 從open表中取出一個(gè)狀態(tài),令其為s,若is_goal(s)為真,則算法結(jié)束,返回解;否則,將s移入closed表,擴(kuò)展s,生成s的所有子節(jié)點(diǎn),對任意子節(jié)點(diǎn)s′,若s′的尺度值劣于s或s′在closed表中,則不將s′放入open表,否則將s′放入open表.

綜上所述,本文針對PDDL語言在規(guī)劃解質(zhì)量建模方面的缺陷,提出了順序多尺度的規(guī)劃問題模型,給出了使用最好優(yōu)先搜索法求解順序多尺度規(guī)劃問題的基本方法,并設(shè)計(jì)了PDDL2.1+OM語言,證明了PDDL2.1語言若需要具有與PDDL2.1+OM語言等價(jià)的建模能力,則需求解一個(gè)PSAPACE-hard的困難問題,該命題表明了PDDL2.1+OM語言在建模能力上的優(yōu)勢.

[1] McDermott D.PDDL: The Planning Domain Definition Language: Version 1.2 [R].New Haven: Yale Center for Computational Vision and Control,1998.

[2] Fox M,Long D.PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains [J].J Artif Intell Res,2003,20(1): 61-124.

[3] Gerevini A,Long D.Plan Constraints and Preferences in PDDL3 [R].Brescia,Italy: Department of Electronics for Automation,University of Brescia,2005.

[4] Keyder K,Geffner H.Soft Goals Can Be Compiled Way [J].J Artif Intell Res,2009,36(1): 547-556.

[5] Hoffmann J.The Metric-FF Planning System: Translating “Ignoring Delete Lists” to Numeric State Variables [J].J Artif Intell Res,2003,20(1): 291-341.

[6] Helmert M.The Fast Downward Planning System [J].J Artif Intell Res,2006,26(1): 191-246.

[7] YIN Ming-hao,ZHOU Jun-ping,SUN Ji-gui.Heuristic Survey Propagation Algorithm for Solving QBF Problem [J].Journal of Software,2011,22(7): 1538-1550.(殷明浩,周俊萍,孫吉貴.求解QBF問題的啟發(fā)式調(diào)查傳播算法 [J].軟件學(xué)報(bào),2011,22(7): 1538-1550.)

[8] LI Ying,SUN Ji-gui,WU Xia,et al.Extension Rule Algorithms Based on IMOM and IBOHM Heuristics Strategies [J].Journal of Software,2009,20(6): 1521-1527.(李瑩,孫吉貴,吳瑕,等.基于IMOM和IBOHM啟發(fā)式策略的擴(kuò)展規(guī)則算法 [J].軟件學(xué)報(bào),2009,20(6): 1521-1527.)

[9] YANG Chao,Lü Shuai,LIU Lei,et al.Research on Action Mutex Encoding Methods in Intelligent Planning [J].Computer Engineering,2011,37(9): 213-215.(楊超,呂帥,劉磊,等.智能規(guī)劃中的動(dòng)作互斥編碼方式研究 [J].計(jì)算機(jī)工程,2011,37(9): 213-215.)

[10] WEI Wei,OUYANG Dan-tong,Lü Shuai,et al.Multiobjective Path Planning under Dynamic Uncertain Environment [J].Chinese Journal of Computers,2011,34(5): 836-846.(魏唯,歐陽丹彤,呂帥,等.動(dòng)態(tài)不確定環(huán)境下多目標(biāo)路徑規(guī)劃方法 [J].計(jì)算機(jī)學(xué)報(bào),2011,34(5): 836-846.)