论文部分内容阅读
允许初始状态和动作效果不确定的一致性规划的状态空间相比经典规划急剧增大并直接影响规划解的质量，采用有限域表示一致性规划能有效地压缩状态空间。然而此表示方法的状态空间存在大量冗余，为了进一步压缩状态空间，本文将针对有限域表示一致性规划中被编码的冗余文字:与现实世界矛盾的文字、初始状态和动作效果的不确定性引入大量的负文字和规划中未出现的文字开展研究:
在与现实世界矛盾的冗余文字方面，分析被编码文字和有限域转换算法中原子实例化的步骤，给出无效文字的定义并提出一种新的实例化原子算法。该算法以实例化过程为基础，将初始参数与对象的匹配对进行筛选，去除不同参数被实例化为同一对象的匹配对，达到去除冗余文字的目的。
在不确定性引入大量的负义字方面，分析被编码文字之间的关系和一致性规划领域定义语言，提出有用文字算法和oneof算法用于对负文字的转换。有用文字算法首先得到除去合成不变量中剩余的正文字和保留不存在于合成不变量中负文字的否定，然后取两种集合的合集形成不可达文字集合，最后利用正文字与负文字间和不同初始状态文字间的互斥关系进行编码。而oneof算法是转化oneof算子为子集构造可达文字集合，然后去掉可达文字集合中与不变量集合重复的部分，最后将剩下的未覆盖文字集合与不变量集合进行编码。
在规划中未出现的被编码文字方面，分析被编码文字与一致性规划所需文字，给出无用文字的定义并提出一种通过建立状态变量域值关系图去除图中孤立点所表示的文字的域值约简算法，从而达到压缩空间的目的。
实验效果表明本文提出的实例化原子算法、oneof算法和域值约简算法无论在时间还是空间性能方面都有效地压缩一致性规划领域状态空间。这些算法都是通过减少状念变量编码的文字个数来达到减少状态空间的目的，其中实例化原子算法主要缩短系统的运行时间，而oneof算法和域值约简算法主要减少编码的文字数。