基于順序多尺度的智能規(guī)劃問題模型及其求解方法

劉曉峰,李 欣,曾志勇

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

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

CM1(π1)

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

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

但該方法存在兩個問題：

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

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

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

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

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

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

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

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

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

2.1 規(guī)劃問題模型

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

例1規(guī)劃任務(wù)T有順序尺度〈M1,M2〉,對于兩個規(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僅支持單個尺度表達(dá)式,而PDDL2.1+OM支持多個尺度表達(dá)式).

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

PDDL2.1+OM支持單尺度、 加權(quán)組合的混合尺度和順序多尺度,比PDDL2.1具有更強(qiáng)的建模能力.如果一個具體的規(guī)劃任務(wù)僅關(guān)注單個尺度的優(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ī)劃尺度語法描述一個具有相同最優(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)解等價.

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

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

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

(1)

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

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

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

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

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

初始化:

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

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

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

綜上所述,本文針對PDDL語言在規(guī)劃解質(zhì)量建模方面的缺陷,提出了順序多尺度的規(guī)劃問題模型,給出了使用最好優(yōu)先搜索法求解順序多尺度規(guī)劃問題的基本方法,并設(shè)計了PDDL2.1+OM語言,證明了PDDL2.1語言若需要具有與PDDL2.1+OM語言等價的建模能力,則需求解一個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é)報,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é)報,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ī)劃中的動作互斥編碼方式研究 [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.(魏唯,歐陽丹彤,呂帥,等.動態(tài)不確定環(huán)境下多目標(biāo)路徑規(guī)劃方法 [J].計算機(jī)學(xué)報,2011,34(5): 836-846.)