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