带有远程互斥的时态规划的研究与实现

论文摘要

智能规划和规划识别是近年来人工智能领域的研究热点,它的应用广泛,囊括了航空航天、人机交互、自然语言理解、军事等许多领域。多年来,国内外许多优秀学者一直致力于智能规划的研究,其中A.L.Blum和M.L.Furst在1995年提出的图规划方法使得智能规划领域取得了革命性的进展。然而早期智能规划的研究都局限于STRIP域的规划问题,即经典规划问题,这也就使得许多现实世界的问题不能得到解决,所以人们在研究中放宽了经典规划的约定,从而产生了新的规划问题,如概率规划、一致性规划、时态规划等等。规划问题求解中互斥的应用很广泛。在一个问题中,很好的处理互斥约束可以给解决问题带来效率上的显著提高。所以,在之前的规划器中,互斥的处理是不可或缺的。然而,所有经典的互斥关系检测的都是在同一时间步上的动作或命题关系。2007年陈一昕等人在经典规划问题中提出了新的远程互斥约束。它扩展了互斥约束的范围,有效地对搜索空间进行剪枝,在很大程度上提高了经典规划的求解效率。经典规划忽略动作的执行过程,将动作执行时间看作是一个时间点,动作的执行效果也是在瞬时完成的。而现实问题中,动作都具有一定的执行时长。时态规划在求解规划问题时引入了动作的执行时间这一因素,在规划求解时考虑动作的开始时间和执行时间长度。基于经典规划器,现在产生了许多优秀的时态规划器,例如TGP、SAPA、CPPlanner等。然而这些规划器中,互斥约束都只局限于经典的互斥关系,并未考虑动作命题之间的最小可执行距离。本文分析了原经典互斥与远程互斥的关系,研究了时态规划问题的特性,提出了时态远程互斥约束t-londex。我们在时态规划求解过程中保持了原有经典互斥约束的效用,并加入新的时态远程互斥约束,更有效地对问题搜索问题进行剪枝,使得时态规划问题求解效率得到显著的提高。

论文目录

• 摘要
• Abstract
• 引言
• 第一章 智能规划
• 1.1 智能规划概念
• 1.2 智能规划应用
• 1.3 智能规划发展历史
• 1.4 规划表示语言
• 1.5 图规划
• 1.5.1 图规划器
• 1.5.2 规划图扩张
• 1.5.3 规划解提取
• 第二章 时态规划
• 2.1 时态规划优越性
• 2.2 时态图规划
• 2.2.1 时态规划图简介
• 2.2.2 时态规划图算法
• 2.2.3 时态互斥约束
• 第三章 远程互斥约束
• 3.1 域转移图
• 3.2 远程互斥约束
• 第四章 时态远程互斥约束
• 4.1 时态域转移图
• 4.2 时态远程互斥约束
• 第五章 处理远程互斥的时态规划系统
• 5.1 带有远程互斥的时态规划算法
• 5.2 带有远程互斥的时态规划器的设计与实现
• 第六章 总结
• 参考文献
• 致谢
• 在学期间公开发表论文情况