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

劉曉峰,李 欣,曾志勇

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

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

CM1(π1)

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

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

但該方法存在兩個問題：

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

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

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

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

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

1 智能規劃的基本概念

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

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

2 順序多尺度規劃問題

2.1 規劃問題模型

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

例1規劃任務T有順序尺度〈M1,M2〉,對于兩個規劃解π和π′,有

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

則根據定義4,π′優于π.但如果定義混合尺度

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

盡管M1的權重比M2的權重高,卻無法依據CM3判斷π和π′的優劣.

為了描述順序多尺度規劃任務,本文擴展了智能規劃領域定義語言PDDL的語法和語義.

2.2 支持順序多尺度的PDDL語言擴展

文獻[2,9-10]在PDDL的版本2.1(PDDL2.1)中提出了帶有規劃尺度的規劃任務描述形式(參見文獻[2]附錄A.4).本文在此基礎上進行擴展,添加支持順序多尺度的語法,記為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,表示要求規劃算法找到順序尺度下的最優解.將PDDL2.1的語法〈metric-spec〉∷=(: metric 〈optimization〉〈ground-f-exp〉)改為〈metric-spec〉∷=(: metric〈optimization〉〈ground-f-exp〉+),允許多尺度的順序聲明(PDDL2.1僅支持單個尺度表達式,而PDDL2.1+OM支持多個尺度表達式).

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

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

結論1任何能由PDDL2.1描述的規劃任務均能由PDDL2.1+OM描述.

用PDDL2.1的規劃尺度語法描述一個具有相同最優解的順序多尺度規劃任務較難,本文將說明該問題的復雜度是#PSPACE-hard.

定義6假設有語言L描述的規劃任務T和語言L′描述的規劃任務T′,如果T和T′具有相同的最優解集合,則稱T和T′為最優解等價.

定理1用PDDL2.1語言描述順序多尺度規劃任務的復雜度為#PSPACE-hard.

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

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

(1)

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

3 順序多尺度規劃問題求解方法

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

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

算法1多尺度規劃求解算法.

初始化:

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

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

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

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

[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問題的啟發式調查傳播算法 [J].軟件學報,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啟發式策略的擴展規則算法 [J].軟件學報,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.(楊超,呂帥,劉磊,等.智能規劃中的動作互斥編碼方式研究 [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.(魏唯,歐陽丹彤,呂帥,等.動態不確定環境下多目標路徑規劃方法 [J].計算機學報,2011,34(5): 836-846.)