论文部分内容阅读
观察信息约简是智能规划的前沿领域。目前国内外对观察信息约简的研究主要是集中于针对单个agent的强规划解，还有一些问题有待于进行观察信息约简方面的研究，尤其在多agent规划领域中，求解agent协同规划解需要考虑每个agent之间的关系，使它们在竞争和冲突的情况下，实现自己或集体的目标。如何在多agent协同规划中进行观察信息约简，提高多agent协同工作的效率并降低执行中的代价，是一个值得研究的问题。本文针对不确定多agent规划系统的问题，讨论了多agent规划领域中的观察信息约简问题。文章吸纳了不确定规划中观察信息约简的基本思想，将它推广到多agent领域。本文首次提出了多agent规划领域的最小观测集问题。文章设计了一种可区分性矩阵，来表示观察变量与需要区分的状态对的对应关系。基于可区分性矩阵，本文建立了一种算法，通过分枝限界法搜索可区分性矩阵不同的化简路径来求解多agent规划的最小观测集问题。经过算法示例和理论证明，表明算法能够正确找到解，且找到的解是符合最优要求的。算法的时间复杂度不高于O(2mkm)不低于(km2),其中k表示需区分状态对的数目，m表示观察变量的数目。本文在最小观察集问题的基础上扩展地提出并定义了多agent规划领域的最优观察集合问题。并提出了带权值的可区分性矩阵来反映观察变量与需要区分的状态对之间的关系。并针对该问题，设计了一种遗传算法与贪心法相结合的混合算法求解问题。通过实验和理论证明，算法能有效地解决该问题。