论文部分内容阅读
本文在前人已有的工作基础上对智能规划领域的观测约简和互斥检测问题做进一步的研究。智能规划的研究领域在近年来得到了不少的扩展，比如不确定规划(NDP)放松了确定性系统的假设、过度规划(OSP)放松了严格目标的假设等等。这些扩展带来了不少新的问题，比如不确定规划中的观测个数约简问题，还有过度规划中互斥目标的检测问题及经典规划器的改造等问题。这些新问题包括了很多有待进一步研究的子问题，比如观测约简中观测个数最小化、启发式的互斥检测、改造优秀的经典规划器以利用互斥检测中的知识等。本文提出了解决上述三个有待进一步研究的子问题的方法。
本文从三方面改进观测约简：一是如何找最小观测集合(MOS)，二是如何在观测代价不均等时找最优观测集合(OOS)，三是如何找到容错的OOS。通过MOS问题和图论中的最小覆盖集问题(MSC)的类似性，可证MOS是NP难的问题，还可参考MSC算法得出时间复杂性为O(2m*㎡)及Ω(2m-1)的算法，其中m是观测的个数。通过使用整数规划(IP)技术，可找到OOS以及容错的OOS。可以证明，上述算法能够保证找到解，并且能够保证解的最优性。
互斥检测本身是NP完全的，本文提出两种用较小的代价给重构目标子集提供启发信息的方法。第一种方法将实现子目标的规划视为宏动作，通过识别这些宏动作之间的关系推测目标之间的关系。第二种方法基于动作之间的因果链提出因果链图(CLG)来检测动作之间的竞争性前提，从而识别目标之间的冲突。其中对第一种方法实现了一个名为Combinator的目标关系检测工具。FFps是本文实现的增量规划结合外部信息求解简单过度规划的规划器。为了利用互斥检测的附加结论，FFps改造了经典的FF规划器以接受外部信息，比如目标序；为了处理OSP问题，FFps支持软目标处理。实验证明，FFps结合Combinator所给出的目标关系检测信息可以高效地处理过度规划问题。