论文部分内容阅读
在基于模型检测的不确定规划中,由于不确定因素的存在,某些状态在执行一个动作后会随机地到达某些状态,只有对这些状态添加辅助信息进行观察才能确定具体位置。因此对规划过程进行观察是十分必要的,而我们将这些辅助信息称为观察信息。而随着信息化社会的发展,问题的规模越来越大,所涉及的信息也越来越广。与之相对应的规划模型的规模也变得非常大,其中涉及的观察信息的数目和类别是相当可观的。绝大多数当今的规划问题应用中,其为了判定位置或其他目的而设计的观察信息都是需要一定消耗的,体现在时间、空间、金钱等各个方面。同时,这些信息往往是存在冗余的,在求解过程中是无作用的,所以以压缩规划器各方面的开销为目的而对带权值的观察信息进行约简就显得十分必要。本文首次对带权值观察信息的约简问题进行了研究,系统地明确了对带权值的观察信息进行约简的基本思路,区分了两种不同方法求得不确定状态集的优劣与适用情况。并针对上述问题,首次针对不确定规划领域中单agent和多agent带权值观察信息的约简问题分别设计了算法。本文的研究是在规划解已知并且所有的观察信息都是可观察的情况下进行的。在单agent情况下,本文就不确定规划领域中权值不等的观察信息约简问题第一次进行了研究并设计了算法。为使得研究工作的方便,设计并给出了最优观察集的概念及性质。设计的SOWOS算法先是根据不确定动作得到运行后随机到达的位置有多个这一特性,建立必然需要甄别的状态对集;以此为基础搭建对应的观察矩阵,应用贪心思想理论,辅以剪枝,最后得以搜索出最优解。在多agent情况下,将单agent的相关概念进行了扩展使之适用于多agent情况;多agent在交互时,尽管本身是具有特性的独立体,但可以相互学习,合作以达到协调的目的,这是与单agent的主要区别。针对多agent下带权值的观察信息约简问题,本文设计了一种基于十字链表的算法,结合启发式函数和贪心思想,实验结果表明该算法可以很好地对多agent情况下的带权值观察信息进行约简。