对不确定规划中观测约简的进一步研究

从3个方面改进了不确定规划(non-deterministic planning,简称NDP)中的观测约简:一是如何找最小观测集合(minimal observation set,简称MOS),二是如何在观测代价不均等时找最优观测集合(optimal observation set,简称OOS),三是如何找到容错的OOS.通过MOS问题和图论中的最小覆盖集问题(minimal set cover,简称MSC)的类似性,可证MOS是NP难的问题,还可参考MSC算法得出时间复杂性不超过O(2^mm²)且不低于Ω(2^m?1)的算法,其中m是观测的个数.通过使用整数规划(integer programming,简称IP)技术,可找到OOS以及容错的OOS.可以证明,上述算法能够保证找到解,并且能够保证解的最优性.     

利用规划命题关系图构建目标议程和宏动作

对智能规划中的常用工具——放松式规划图(relaxed planning graph,简称RPG)的图论性质进行了深入研究.将RPG中的命题层抽取出来,得到一个不包含任何动作的命题关系图(proposition relation graph,简称PRG),发现PRG仍具有RPG的主要规划性质.初步研究结果包括以下4个方面:初始命题集(initial proposition set,简称IPS)的闭出邻集(close out-neighborhoods,简称CON)是放松式规划可达命题集(relaxed reachable proposition set,简称R-RPS);初始状态命题到目标状态命题的最大距离是规划解长度的合理估计;无圈序指出了对应命题被实现的顺序要求;出度或入度为1的结点收缩对应规划中构造的宏动作.上述结果中,前两者说明PRG保留RPG的主要规划性质,后两者可用于建立目标议程或宏动作提取等领域.还提出与上述结论相关的3种算法:从RPG中得到PRG的算法(复杂性为O(mn2),其中,n为RPG的命题数,m为RPG的动作数);约简无圈序算法(复杂性为O(n+m),其中,n为PRG的结点数,m为PRG的边数);宏动作建议算法(复杂性为O(n2),n为PRG的结点数).     

对不确定规划中观测约简的进一步研究

从3个方面改进了不确定规划（non—deterministic planning,简称NOP）中的观测约简：一是如何找最小观测集合（minimal observation set,简称MOS）,二是如何在观测代价不均等时找最优观测集合（iptimal observation set,简称OOS）,三是如何找到容错的OOS．通过MOS问题和图论中的最小覆盖集问题（minimal set cover,简称MSC）的类似性,可证MOS是NP难的问题,还可参考MSC算法得出时间复杂性不超过O（2^mm^2）且不低于Ω（2^m-1）的算法,其中m是观测的个数．通过使用整数规划（integer programming,简称IP）技术,可找到OOS以及容错的OOS．可以证明,上述算法能够保证找到解,并且能够保证解的最优性．