带有并行动作的可能性规划的研究与实现

摘要

近年来，智能规划已经成为人工智能的研究热点，可能性规划作为不确定规划的一种，由于能够定性的刻画现实世界中的不确定性，更适合于求解现实世界中的规划问题，而逐渐得到人们的关注。而现有可能性图规划器Poss-Graphplan限定每个时间步只执行一个动作，且规划图中无法使用互斥信息，找到的规划解相对冗长，并且比较浪费求解时间。
　　在深入研究可能性理论的基础上，针对这一问题，提出新的可能性规划算法PC-Graphplan。首先，在可能性图框架下重新定义了互斥关系和并行动作集的概念，使之能够符合可能性规划中动作的不确定性，PC-Graphplan算法在规划图扩展阶段标记节点间的互斥信息，有效利用规划图的特性，提高了规划器的求解质量;接着，在规划提取中给出了乐观和悲观两种情况下生成并行动作集的算法，实现了可能性图框架下动作的并行执行，弥补了Poss-Graphplan规划器中每个时间步只能执行一个动作的不足;然后，分乐观和悲观两种情况给出了带有并行动作的可能性规划的图规划算法PC-Graphplan;最后，用C语言在Windows系统下实现了基于可能性理论的可处理并行动作的PC-Graphplan图规划器，实验证明PC-Graphplan图规划器可以达到理论预期的效果，实现了可能性规划过程中动作的并行执行，与Poss-Graphplan相比提高了求解质量，使得可能性规划更适合于处理现实世界问题。

目录

声明

摘要

引言

第一章 智能规划的研究与发展

1．1 智能规划简介

1．2 智能规划的应用

1．3 智能规划的发展

第二章 可能性规划

2．1 可能性理论概述

2．2 可能性规划问题

2．2．1 可能性状态

2．2．1 可能性动作

2．2．1 可能性规划问题

2．3 可能性规划的优势

2．4 可能性规划的表示方法-Poss-PDDL

2．4．1 PDDL语言的发展历史

2．4．2 Poss-PDDL

第三章 可能性马尔可夫决策过程

3．1 马尔可夫决策过程

3．2 可能性马尔可夫决策过程

3．2．1 基于可能性理论的定性决策标准

3．2．2 基于可能性理论的贝尔曼方程

第四章 基于可能性理论的PC-Graphplan系统的设计与实现

4．1 可能性规划图扩展与提取算法

4．1．1 可能性规划图的扩展算法

4．1．2 可能性规划图的提取算法

4．2 PC-Graphplan的图规划算法

4．2．1 PC-Graphplan中的基本概念

4．2．2 PC-Graphplan图扩张算法

4．2．3 PC-Graphplan解提取算法

4．3 PC-Graphplan系统的开发测试环境

4．4 PC-Graphplan规划器的系统功能设计

4．5 实验结果与分析

第五章 总结

参考文献

致谢

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