可创建/删除对象的快速前向规划系统的研究与实现

摘要

智能规划与规划识别是人工智能(Artificial Intelligent)研究领域的一个重要分支。1995年Blum和Furst提出基于规划图的快速规划方法——图规划(Graphplan)，使智能规划领域的研究取得了革命性进展。可创建/删除对象图规划系统(CDOGP)是图规划框架下处理可创建/删除对象规划问题的规划系统，解决了图规划所未解决的规划问题之一，但是CDOGP没有使用启发式搜索的方法搜索有效规划，有效规划的提取速度有很大的提升空间。快速前向规划系统(Fast-Forward planning，FF)是2000年国际规划竞赛上出现的一款比较成功的规划器，是启发式搜索技术应用于规划领域的一个成功范例，但是FF规划系统无法处理操作创建对象或删除对象的规划问题，而这类问题在现实中大量存在。 本文采用前向状态空间搜索的方法，解决了规划领域中的对象集合动态变化的规划问题，提出了处理可创建/删除对象规划问题的方法——可创建/删除对象的快速前向规划(CDOFF)。本文首次提出了对象元件的概念，并根据此定义对对象集合中的对象进行了分类，使现实领域中对象动态变化问题更易于被描述为CDOFF规划器处理的规划问题；提出了一种新的算法——对象元件命题化算法(OCP)，利用此算法可减少规划过程中产生的节点数目，缩小状态转移时生成的规划图的规模，进而可节省大量的存储空间；设计了新的启发函数，已有的启发函数在引导规划进行时，大部分考虑的只是目标距离，本文基于目标距离和资源耗费两个因素构造了新的启发式函数，新的启发式函数引导规划求得较优解。 在给出算法的基础上，使用C程序设计语言，开发了处理可创建/删除对象规划问题的规划系统CDOFF，实验结果证明CDOFF实现了采用前向状态空间搜索解决可创建/删除对象规划问题的预期目标，能够有效地处理可创建/删除对象的规划问题。

目录

文摘

英文文摘

声明

引 言

第一章智能规划

1.1智能规划相关概念

1.2智能规划的发展

1.3智能规划问题的描述语言

1.3.1 STRIPS语言

1.3.2 ADL语言

1.3.3 PDDL语言

1.4图规划

1.5 FF规划系统

第二章可创建/删除对象的图规划(CDOGP)

2.1 CDOGP概述

2.2 CDOGP算法介绍

2.2.1 CDOGP规划图生成算法

2.2.2 CDOGP有效规划搜索算法

第三章可创建/删除对象的快速前向规划系统(CDOFF)

3.1 CDOFF中的基本概念及理论框架

3.1.1 CDOFF中的基本概念

3.1.2理论框架

3.2对象元件命题化算法(OCP)

3.2.1规划问题描述

3.2.2 OCP算法描述

3.2.3部分放宽方法

3.3启发函数的设计

3.4搜索算法及剪枝策略

3.4.1增强爬山法

3.4.2剪枝策略

第四章实验结果与讨论

4.1系统介绍

4.2系统开发环境与运行过程

4.3实验结果与分析

结 论

参考文献

后 记

在学期间公开发表论文及著作情况