基于规划图的时态推理与时态规划

摘要

智能规划是人工智能的一个重要研究领域，智能规划的主要思想是根据预定实现的目标，对若干可供选择动作及所提供的资源限制进行推理，得到实现目标的动作序列。近几年来，为了表示规划过程中产生的条件因素和动态信息，大量的研究工作围绕条件效果、不确定性和时态规划等情况展开，同时，一些高效算法的提出也大大推动了智能规划的研究从经典问题向实际规划问题的转移，智能规划研究的课题不断地由理论研究领域走向实际应用领域。 在时态规划方面，由于许多现实世界中的规划问题通常希望规划目标能在尽可能短的时间内实现，并且规划过程中存在大量能并发执行的持续性动作，这些动作的执行需要考虑时间、资源的消耗。这类规划问题，用经典规划中带瞬间动作的STRIPS模型是无法进行表示的，因此，为表示实际规划问题，需要对时间信息进行有效表示，并能进行时序约束推理。国际标准规划语言PDDL2.1版本即是在原来规划语言基础上增加了对持续性动作和数值量词的支持，这方面的规划领域问题在历届国际规划大赛中非常受重视。但目前现有的时态规划算法的效率以及规划过程中时态推理的技术及其运用都难以令人满意。为此，本文在时态推理技术和时态规划问题的求解方法两个方面进行了研究。 在时态推理技术研究部分，本文首先介绍了经典规划的概念模型，以及其受限和扩展模型，指出了时态规划所需要解决的技术问题。规划图是图规划技术中的数据结构，传统规划领域中难以处理的动作和状态之间可能存在的互斥关系均能简洁地表示在规划图上，本文在规划图框架下，定义了动作图，并进一步扩展为时态动作图，使之能体现时态规划问题中的时态信息。在此基础上，提出了一种对时态信息进行表示与管理，并且能够进行时态约束推理的时态一致性赋值方法；约束可满足问题(CSP)是一个通用的且功能强大的问题求解的范例，在规划问题中，时态关系可以用CSP技术和方法方便地表示和处理。本文利用CSP技术对时序约束进行处理，包括过滤、约减及时态信息的一致性检验，使时态推理技术能更好地应用于时态规划的求解过程中。 在求解时态规划问题实现部分，本文首先综述了经典时态规划的技术方法，对目前比较受关注的、性能较好的时态规划器从技术方法上进行了研究分析；对PDDL2.1语言所描述的支持持续动作的规划领域问题，利用遗传算法实现求解时态规划的算法。算法针对基于规划图的遗传规划技术存在局部搜索能力不足的缺点，提出了在原有遗传操作算子的基础上，引入局部修复算子的混合规划技术，这种方法的优点在于能够在规划求解中对时态信息进行处理，减少冗余和不一致的时态信息，提高了求解效率，同时利用遗传规划算法能够避免局部搜索的不足，实验表明，这种算法能有效地处理一类时态规划问题。

目录

文摘

英文文摘

声明

第一章引言

1.1智能规划及其研究课题

1.2时间和资源约束规划研究现状

1.3问题的提出

1.4本文研究目的与研究内容

第二章规划与时态规划概述

2.1规划的概念模型

2.2经典规划

2.3规划的技术方法

2.4基于时态和资源约束的规划

第三章基于规划图的时态推理技术

3.1时态推理技术

3.2规划图与动作图

3.3时态动作图与时态赋值

第四章基于CSP技术的时态信息处理

4.1 CSP概述

4.2 CSP技术在规划中的应用

4.3 时态信息过滤和一致性检验

第五章 时态规划方法研究

5.1使用时态操作的时态规划

5.2基于年代记的时态规划

5.3时态规划器分析

第六章规划图框架下时态规划的求解

6.1遗传规划

6.2基于时态动作图的遗传规划算法设计

6.3算法总体描述

6.4实验结果及分析

6.5相关工作比较

第七章结论和进一步工作

参考文献

攻读博士学位期间发表论文列表

致谢