第2期 宋泾舸，等：智能规划研究综述—一个面向应用的视角 ·21· 检验的一种技术，在许多工程领域得到应用，如电 采用了有环谓词-变迁Petri网和有环着色Petri 路、通信协议、数字控制器的检验等.近年来，模型检 网.Kristensen!30]在军事运筹规划中用Petri网描述 验作为一种求解策略引起智能规划研究者的关注。 了“任务”，使领域描述支持了层次任务结构 基于二元判定图(BDD)的模型检验是采用较多的策 2.3不确定性问题 略.该方法用BDD模型表达系统状态和动作，降低 通过对经典问题假设的适当放宽形成了非经典 了表达的冗余度改善了求解效率.采用这类方法的 问题.不确定性规划是其中重要的分支，主要研究系 规划器主要有MBp2、UMOP2]MIPS23]等 统初始状态不确定和动作效果不确定对求解的影 虽然STRIPS类问题的求解效率和成功率得到 响.相容性(conformant)规划是研究初始状态信息 了大幅提高，但仍然不能胜任大规模问题.为了解决 不完整的不确定性规划问题3 更大规模的STRIPS规划问题，一些学者采用了元 对于动作的执行效果的不确定性，决策理论的 (meta)求解策略.FoxM等人在STAN424]中采用 应用是一种自然的选择.采用马尔可夫决策过程 了领域分析的策略，从领域描述中提取与求解相关 (MDPs)是一种主要的表达和求解]方法 的信息，忽略不相关的信息，将目标问题分解成子问 2.4知识的获取与运用问题 题，使状态空间缩小，然后采用适合的求解算法分别 引入领域知识被认为是提高系统实用性的必然 进行求解，最后对子问题解进行合成.WahB2s]等 选择).但是这也同时带来另外一些问题，例如，规 人在SGPlan中运用了基于扩展鞍点理论的子目标 模较大领域中知识获取比较困难；难于有效集成多 分割策略，大大提高了多目标STRIPS类问题的求 种类型的知识：过量的知识将增加计算量：知识的领 解效率和成功率 域相关降低了系统的通用性等 2.2领域建模问题 HTN规划虽然引入了领域知识，提高了问题 尽管人们己经对领域建模进行了大量研究，但 求解效率，但其领域知识的主要表现形式是任务的 从描述准确性和描述效率看，仍有许多领域问题不 能很好描述.一些学者认为，领域建模是影响规划系 分解策略.事实上，知识工程可以应用于规划系统的 不同层面，例如领域对象描述、任务和目标结构描 统应用性的十分重要的因素 目前的建模机制以命题式描述为主（如PD 述、搜索策略控制、计划质量评估、知识获取、知识管 理等.因此知识工程方法与智能规划的结合是近年 DL),其形式简单、通用性强.但命题描述更适合于 简单知识和浅层知识的描述，即领域知识必须明确 来的一个应用研究热点 给出，因此有时无法有效地描述复杂的和深层知识 本体论(ontology)是面向知识表达、共享、协同 例如对象具有空间关系的货物仓储问题，命题描述 的知识工程方法，在领域建模、知识集成与管理、协 必须明确指出货物间的摆放位置关系，货物量较大 同求解等方面为复杂领域的知识建模提供有力的支 时将使描述量变得很大.解决命题描述的“规模瓶 持.因而成为知识工程应用于智能规划的一个新方 颈”的一种途径是基于模型的描述.模型是描述领域 向！.机器学习是知识获取的重要方法之一，因而 对象及其关系的数据结构，通常以图结构的形式表 成为知识工程应用的另一个方向.近年来一些学者 现.模型描述将知识、约束隐含在模型中，使描述更 在这方面进行了探索，例如，Veloso1等人在prod 自然、有效 igy规划器中引入了学习机制，Yang Q34等人则用 自动机(automata)是一种应用广泛的工业系统 学习方法进行动作模式的获取 过程建模机制.一些学者26.21采用基于该模型的模 3工程中的规划问题 型检验方法进行规划问题求解，满足目标命题的模 型检验路径就是规划求解生成的计划.由于自动机 为了使智能规划研究更好地服务于实践，近年 模型中状态的改变以事件形式表现，在设计并行和 来一些学者提出将规划研究的案例重点从理想化、 不确定行为时描述能力受到限制.Petri网是另一种 小规模的“玩具”问题(toy problem)转向大规模、复 模型，对并行和异步行为有更强的表达能力.这方面 杂的现实世界问题(real-world problem),并提出了 目前仍在起步阶段，如Murata21和Mieller21分别 不同领域中的一些典型问题实例 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net检验的一种技术 ,在许多工程领域得到应用 ,如电 路、通信协议、数字控制器的检验等. 近年来 ,模型检 验作为一种求解策略引起智能规划研究者的关注. 基于二元判定图(BDD) 的模型检验是采用较多的策 略. 该方法用 BDD 模型表达系统状态和动作 ,降低 了表达的冗余度 ,改善了求解效率. 采用这类方法的 规划器主要有 MBP [21 ] 、UMOP [ 22 ] 、MIPS [23 ]等. 虽然 STRIPS 类问题的求解效率和成功率得到 了大幅提高 ,但仍然不能胜任大规模问题. 为了解决 更大规模的 STRIPS 规划问题 ,一些学者采用了元 (meta) 求解策略. Fox M 等人在 STAN4 [ 24 ] 中采用 了领域分析的策略 ,从领域描述中提取与求解相关 的信息 ,忽略不相关的信息 ,将目标问题分解成子问 题 ,使状态空间缩小 ,然后采用适合的求解算法分别 进行求解 ,最后对子问题解进行合成. Wah B [25 ] 等 人在 SGPlan 中运用了基于扩展鞍点理论的子目标 分割策略 ,大大提高了多目标 STRIPS 类问题的求 解效率和成功率. 212 领域建模问题 尽管人们已经对领域建模进行了大量研究 ,但 从描述准确性和描述效率看 ,仍有许多领域问题不 能很好描述. 一些学者认为 ,领域建模是影响规划系 统应用性的十分重要的因素. 目前的建模机制以命题式描述为主 (如 PD2 DL) ,其形式简单、通用性强. 但命题描述更适合于 简单知识和浅层知识的描述 ,即领域知识必须明确 给出 ,因此有时无法有效地描述复杂的和深层知识. 例如对象具有空间关系的货物仓储问题 ,命题描述 必须明确指出货物间的摆放位置关系 ,货物量较大 时将使描述量变得很大. 解决命题描述的“规模瓶 颈”的一种途径是基于模型的描述. 模型是描述领域 对象及其关系的数据结构 ,通常以图结构的形式表 现. 模型描述将知识、约束隐含在模型中 ,使描述更 自然、有效. 自动机(automata) 是一种应用广泛的工业系统 过程建模机制. 一些学者[26 - 27 ]采用基于该模型的模 型检验方法进行规划问题求解 ,满足目标命题的模 型检验路径就是规划求解生成的计划. 由于自动机 模型中状态的改变以事件形式表现 ,在设计并行和 不确定行为时描述能力受到限制. Petri 网是另一种 模型 ,对并行和异步行为有更强的表达能力. 这方面 目前仍在起步阶段 ,如 Murata [28 ] 和 Mieller [29 ] 分别 采用了有环谓词 - 变迁 Petri 网和有环着色 Petri 网. Kristensen [ 30 ]在军事运筹规划中用 Petri 网描述 了“任务”,使领域描述支持了层次任务结构. 213 不确定性问题 通过对经典问题假设的适当放宽形成了非经典 问题. 不确定性规划是其中重要的分支 ,主要研究系 统初始状态不确定和动作效果不确定对求解的影 响. 相容性 (conformant) 规划是研究初始状态信息 不完整的不确定性规划问题[31 ] . 对于动作的执行效果的不确定性 ,决策理论的 应用是一种自然的选择. 采用马尔可夫决策过程 (MDPs) 是一种主要的表达和求解[3 ]方法. 214 知识的获取与运用问题 引入领域知识被认为是提高系统实用性的必然 选择[2 ] . 但是这也同时带来另外一些问题 ,例如 ,规 模较大领域中知识获取比较困难 ;难于有效集成多 种类型的知识 ;过量的知识将增加计算量 ;知识的领 域相关降低了系统的通用性等. H TN 规划虽然引入了领域知识 ,提高了问题 求解效率 ,但其领域知识的主要表现形式是任务的 分解策略. 事实上 ,知识工程可以应用于规划系统的 不同层面 ,例如领域对象描述、任务和目标结构描 述、搜索策略控制、计划质量评估、知识获取、知识管 理等. 因此知识工程方法与智能规划的结合是近年 来的一个应用研究热点. 本体论(ontology) 是面向知识表达、共享、协同 的知识工程方法 ,在领域建模、知识集成与管理、协 同求解等方面为复杂领域的知识建模提供有力的支 持. 因而成为知识工程应用于智能规划的一个新方 向[32 ] . 机器学习是知识获取的重要方法之一 ,因而 成为知识工程应用的另一个方向. 近年来一些学者 在这方面进行了探索 ,例如 ,Veloso [33 ] 等人在 prod2 igy 规划器中引入了学习机制 , Yang Q [34 ] 等人则用 学习方法进行动作模式的获取. 3 工程中的规划问题 为了使智能规划研究更好地服务于实践 ,近年 来一些学者提出将规划研究的案例重点从理想化、 小规模的“玩具”问题 (toy problem) 转向大规模、复 杂的现实世界问题 (real2world p roblem) ,并提出了 不同领域中的一些典型问题实例. 第 2 期 宋泾舸 ,等 :智能规划研究综述 ———一个面向应用的视角 ·21 ·