文档介绍：摘要
摘要
不确定性环境下的决策和规划是人工智能的基本问题之一。决策论为这类
问题的最优化求解提供了标准的理论框架。近年来,单智能体的决策理论取得
了长足的发展,经典的 MDP 和 POMDP 算法已经能求解较大规模的问题。但多
智能体的分布式决策却依然处在研究的初级阶段,通常只能求解极小规模的问
题。作为马尔科夫决策理论在多智能体系统上的扩展,DEC-POMDP 模型涵盖
了大多数的多智能体合作问题,但同时也具有极高的问题复杂度(NEXP 难)。
因为在多智能体系统中,每个智能体不仅要考虑环境的变化还需要关注其他智
能体的可能行为。DEC-POMDP 的复杂度具体表现在求解上就是问题具有极大
的策略空间。如何对巨大的策略空间进行表示和推理并从中找出最优的策略是
DEC-POMDP 问题求解的关键。受限于问题复杂度,精确算法通常只能求解极
小规模的问题。因此,本文研究的重点是为一般性的 DEC-POMDP 问题设计高
效的近似算法。从求解方式上看,大体可分为在线和离线算法两类。本文在这
两类算法上均有相应的工作,同时还求解了一类更具挑战的无模型规划问题。
在线规划算法在智能体与环境交互的过程中进行规划,因此只需要考虑智
能体当前遇到的情况。由于每次执行过程中,智能体实际遇到的情况只是各种
可能中很小的一部分。而且在线算法只需要为智能体当前的行动作出选择,而
不需要计算完整的策略。因此在大规模问题求解上,在线算法更具有优势。同
时,在线算法还能够更加方便的完成智能体之间的通讯,从而提高决策质量。
但在线算法本身也有需要解决的问题。因为智能体需要实时的对环境做出反
应,因此每次可用于规划的时间非常的有限。在 DEC-POMDP 问题中,每个智
能体获得的是各自不同的局部观察,所有需要一个分布式的计算框架来保证智
能体行为之间的协调。为了与其他智能体进行合作,每个智能体必须把握其他
智能体所有可能拥有的信息,而这些信息随着时间的增加会不断的暴涨。同时
由于带宽、环境和计算资源的限制,智能体之间的通讯往往是受限的。因此如
何最大限度的发挥通讯的效用也是在线算法需要解决的问题。为解决这些问
题,本文提出的 M 算法至少具有以下几点创新:一、提出了基于
线性规划的快速策略搜索算法用于满足在线算法的时间需求;二、提出了基于
独立维护的共享信念池的分布式规划保证了智能体之间的协调;三、提出了基
于策略等价的历史信息归并方法使得智能体能在有限的存储空间中保留对后继
决策更加有用的信息;四、提出了基于信念不一致性检测的通讯策略来更加有
效的使用通讯确保了信念池信息的精度从而提高决策效果。从实验结果上看,
M 算法在各种 DEC-POMDP 的测试问题中具有相当出色的表现。
I
摘要
离线规划算法在智能体与环境进行交互前,通过给定的模型计算出完整的
策略。其主要优势在于有充足的时间来进行规划,而且不需要考虑分布式决策,
只要求计算出的策略能被每个智能体进行分布式的执行。其主要劣势在于需要
完整的考虑整个策略空间,具有极高的计算量。当前,最为先进的离线规划算
法采用的是将动态规划和启发式搜索相结合的办法来构建一套完整的策略。对
于大规模问题,其主要瓶颈在于每一步迭代都会产生极其多的子策略。这些子
策略会快速的耗尽所有的存储空间或者导致运算严重超时。为了解决这一问
题,本文在前人工作的基础上提出了 PBPG 和 TBDP 这两个算法。PBPG 算法
的主要创新点在于彻底的改变了之前先枚举再选择的策略生成模式,直接构建
最优化的模型为每个信念点直接生成所需的策略。因此在动态规划过程中,备
选的策略不再快速的塞满内存空间,同时每一步迭代后可保留的策略数大大增
加,并最终大幅度的提高了规划策略的质量。从实验结果上看,PBPG 算法在
运行时间上比之前最好的算法加快了一个数量级,并随着可保留策略数的增
加近似最优的求解了大部分的实验测试问题。TBDP 算法主要针对的是大状态
DEC-POMDP 问题。其主要的创新点是使用基于测试的方法只为可达的状态和
需要使用到的策略计算值函数。之前的算法,笼统的为所有的状态和策略计算
值函数,因此带来了极高的计算量,无法求解大规模问题。TBDP 算法的另一
个创新点是提出了具有层次结构和随机参数的新的策略表示方法。该方法能够
将策略生成转变为策略参数的最优化过程,从而进一步的提高了策略求解的效
率。同时,TBDP 算法可方便的运行在多处理器的并行分布式计算资源上。在
实验中,TBDP 算法首次求解了上万个状态的 DEC-POMDP 问题。
无论是离线算法还是在线算法,在问题求解的时候都需要用到完整的