| 【中文题名】 | 基于延迟部分推理的快速前向规划系统 |
| 【英文题名】 | Fast Forward Planning System Based on Delayed Partly Reasoning |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-8-10 |
| 【中关键词】 | 智能规划,启发式搜索,朴素条件效果规划图,延迟部分推理,, |
| 【英关键词】 | Artificial Intelligence Planning,Heuristic Search,Na?ve Conditional Planning Graph,Delayed Partly Reasoning, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 智能规划是人工智能的重要研究领域之一。用启发式搜索技术求解智能规划问题成为近年来的研究热点。
“快速前向规划系统”(FF)是启发式搜索技术应用于规划领域的一个成功范例。FF通过忽略动作的删除效果,使用放松图规划(relaxed Graphplan)提供的启发信息引导加强爬山算法(Enforced Hill-climbing),在STRIPS规划域中显示出优异的性能。在ADL域,FF使用IPP方法处理带有条件效果的动作。这样的处理方法导致放松图规划引导的加强爬山算法在ADL域求解时经常失败。本文指出,此问题的原因在于放松图规划无法处理组件之间存在的诱导关系从而不能提供足够的有用动作。我们设计了DPR-NCEPGFF智能规划系统,以解决发现的问题。DPR-NCEPGFF采用一个我们称之为在朴素的条件效果规划图上进行延迟部分推理(DPR-NCEPG)的方法提取启发信息。在此方法中,我们虽然考虑所有动作的删除效果,但是只计算动作的组件之间限定范围内的诱导组件互斥关系。初步的实验结果显示,在ADL域,加强爬山算法在DPR-NCEPG的引导下,求解的质量和求解的速度都明显提高。
目前的启发函数设计思想大都基于完全... |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
Abstract |
4-5 |
|
目录 |
5-7 |
|
引言 |
7-9 |
|
第一章 智能规划 |
9-12 |
|
1.1 什么是智能规划 |
9 |
|
1.2 规划问题表示 |
9-11 |
|
1.2.1 STRIPS |
10 |
|
1.2.2 ADL |
10-11 |
|
1.3 规划器 |
11-12 |
|
第二章 基于启发式状态空间搜索的规划方法 |
12-19 |
|
2.1 状态空间 |
12-13 |
|
2.2 启发函数的获取方法 |
13-19 |
|
2.2.1 HSP 对一个命题的估计 |
14 |
|
2.2.2 HSP-r 的Max 方法(Max heuristic) |
14 |
|
2.2.3 HSP-r 的和代价法 |
14-15 |
|
2.2.4 HSP-r 的和互斥代价法(Sum mutex heuristic) |
15 |
|
2.2.5 FF 的放松规划解法(relaxed plan) |
15-17 |
|
2.2.6 模式数据库法(Pattern Databases,PDBs) |
17 |
|
2.2.7 因果图法(Casual Graph, CG) |
17-19 |
|
第三章 FF 规划系统 |
19-24 |
|
3.1 FF 规划系统概述 |
19 |
|
3.2 启发函数的定义 |
19 |
|
3.3 加强爬山算法(Enforced Hill-climbing) |
19-20 |
|
3.4 剪枝策略 |
20-22 |
|
3.4.1 选择最有希望的节点进行扩展 |
20-21 |
|
3.4.2 删除过早添加的目标 |
21-22 |
|
3.5 从STRIPS 到ADL 域的扩展 |
22-24 |
|
第四章 基于部分延迟推理的快速前向规划系统 |
24-35 |
|
4.1 背景 |
24 |
|
4.2 FF 规划系统的局限性 |
24-26 |
|
4.3 朴素条件效果规划图上的延迟部分推理 |
26-31 |
|
4.3.1 处理具有条件效果的规划动作 |
26-27 |
|
4.3.2 朴素条件效果规划图 |
27-29 |
|
4.3.3 部分延迟推理 |
29-31 |
|
4.4 实验结果和讨论 |
31-34 |
|
4.4.1 Briefcase world 域 |
31-32 |
|
4.4.2 Schedule 域 |
32 |
|
4.4.3 Elevator 域 |
32-34 |
|
4.5 相关工作和讨论 |
34-35 |
|
第五章 总结 |
35-36 |
|
参考文献 |
36-40 |
|
致 谢 |
40-41 |
|
在学期间公开发表论文及著作情况 |
41 |
|
| 【DOI】 | LunWen.ID:2.2008.387865 |
