基于互斥约束的概率规划器及其扩展算法的研究与实现

摘要

智能规划领域的研究者针对规划问题中的不确定性(uncertainty)问题和不完全信息(incomplete)问题,开发了一些有效的规划器,其中Blum与Langford提出了专门针对动作结果不确定的规划问题的算法Probabilistc GraphPlan(简称PGP),相关的实验结果表明PGP优于解决同类问题的规划器Buridan,SPI,BlackBox等.但PGP算法只局限于处理STRIPS动作的概率规划问题,对于动作带有条件效果的概率规划问题,PGP算法就不适用了.为了扩大PGP规划器的处理范围,提出该研究课题.本文首先从表示方法、规划类型、复杂度、规划语言等几方面分析了概率规划的研究现状,概括了研究概率规划的相关理论和相关技术,并分别介绍了经典规划器与概率规划器中对动作带有条件效果的规划问题的处理方法,其次介绍自己做的主要工作,包括两个部分:(一)研究与实现基于互斥约束的概率规划器,该规划器是对PGP加以改进,改进后的算法相对于PGP规划器减少了规划图中的结点数目,节省了存储空间.(二)提出处理动作带有条件效果的概率规划器的算法.最后阐明了未来继续要做的工作,对第二部分提出算法进行程序实现.

目录

文摘

英文文摘

独创性声明和学位论文版权使用授权书

引言

第一章概率规划概述

1.1概率规划

1.1.1状态表示

1.1.2初始世界

1.1.3动作表示

1.1.4概率规划的定义

1.1.5概率规划的类型

1.2概率规划和不确定规划

1.3概率规划复杂度

1.3.1复杂类的介绍

1.3.2各类概率规划的复杂度

1.4概率规划语言

1.4.1概率化的PDDL(PPDDL)

1.4.2其它语言

1.5 IPC-4中关于概率规划的一些问题

第二章图规划框架下的概率规划

2.1图规划算法

2.1.1基本概念

2.1.2有效规划与规划图

2.1.3扩张规划图(extending planning graphs)算法

2.1.4搜索有效规划算法

2.2 PGP算法

2.2.1马尔可夫决策问题(MDP)

2.2.2概率动作在规划图中的表示

2.2.3启发式信息

2.2.4规划图扩张与有效规划解搜索算法

第三章MPGP算法

3.1算法背景

3.2算法分析

3.3命题互斥

3.4规划图的扩张算法

3.5搜索有效规划

3.6例子和实验结果

3.6.1概率积木世界

3.6.2护城河和城堡问题

3.6.3实验结果总结及后续的研究方向

第四章MCPGP

4.1条件效果

4.2处理方法

4.2.1完全扩展法

4.2.2要素扩展法

4.2.3 IP2方法

4.3 MCPGP中的条件效果

4.3.1动作模式

4.3.2动作在规划图中的表示：

4.3.3 MCPGP中的命题互斥

4.3.4 MCPGP的图扩张算法

4.3.5搜索有效规划

4.3.6总结及后续工作

总结

参考文献

附录A第一届规划调度系统比赛

附录B第二届规划调度系统比赛

附录C第三届规划调度系统比赛

附录D主要概率规划器一览表

致谢

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