基于决策理论的多智能体系统规划问题研究.pdf

《基于决策理论的多智能体系统规划问题研究.pdf》由会员分享，可在线阅读，更多相关《基于决策理论的多智能体系统规划问题研究.pdf（119页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、中国科学技术大学博士学位论文基于决策理论的多智能体系统规划问题研究姓名：吴锋申请学位级别：博士专业：计算机应用技术指导教师：陈小平2011-05摘要摘要不确定性环境下的决策和规划是人工智能的基本问题之一。决策论为这类问题的最优化求解提供了标准的理论框架。近年来，单智能体的决策理论取得了长足的发展，经典的 MDP 和 POMDP 算法已经能求解较大规模的问题。但多智能体的分布式决策却依然处在研究的初级阶段，通常只能求解极小规模的问题。作为马尔科夫决策理论在多智能体系统上的扩展，DEC-POMDP 模型涵盖了大多数的多智能体合作问题，但同时也具有极高的问题复杂度（NEXP 难）。因为在多智能体系统

2、中，每个智能体不仅要考虑环境的变化还需要关注其他智能体的可能行为。DEC-POMDP 的复杂度具体表现在求解上就是问题具有极大的策略空间。如何对巨大的策略空间进行表示和推理并从中找出最优的策略是DEC-POMDP 问题求解的关键。受限于问题复杂度，精确算法通常只能求解极小规模的问题。因此，本文研究的重点是为一般性的 DEC-POMDP 问题设计高效的近似算法。从求解方式上看，大体可分为在线和离线算法两类。本文在这两类算法上均有相应的工作，同时还求解了一类更具挑战的无模型规划问题。在线规划算法在智能体与环境交互的过程中进行规划，因此只需要考虑智能体当前遇到的情况。由于每次执行过程中，智能体实际遇

3、到的情况只是各种可能中很小的一部分。而且在线算法只需要为智能体当前的行动作出选择，而不需要计算完整的策略。因此在大规模问题求解上，在线算法更具有优势。同时，在线算法还能够更加方便的完成智能体之间的通讯，从而提高决策质量。但在线算法本身也有需要解决的问题。因为智能体需要实时的对环境做出反应，因此每次可用于规划的时间非常的有限。在 DEC-POMDP 问题中，每个智能体获得的是各自不同的局部观察，所有需要一个分布式的计算框架来保证智能体行为之间的协调。为了与其他智能体进行合作，每个智能体必须把握其他智能体所有可能拥有的信息，而这些信息随着时间的增加会不断的暴涨。同时由于带宽、环境和计算资源的限制，

4、智能体之间的通讯往往是受限的。因此如何最大限度的发挥通讯的效用也是在线算法需要解决的问题。为解决这些问题，本文提出的 MAOP-COMM 算法至少具有以下几点创新：一、提出了基于线性规划的快速策略搜索算法用于满足在线算法的时间需求；二、提出了基于独立维护的共享信念池的分布式规划保证了智能体之间的协调；三、提出了基于策略等价的历史信息归并方法使得智能体能在有限的存储空间中保留对后继决策更加有用的信息；四、提出了基于信念不一致性检测的通讯策略来更加有效的使用通讯确保了信念池信息的精度从而提高决策效果。从实验结果上看，MAOP-COMM 算法在各种 DEC-POMDP 的测试问题中具有相当出色的表现

5、。I摘要离线规划算法在智能体与环境进行交互前，通过给定的模型计算出完整的策略。其主要优势在于有充足的时间来进行规划，而且不需要考虑分布式决策，只要求计算出的策略能被每个智能体进行分布式的执行。其主要劣势在于需要完整的考虑整个策略空间，具有极高的计算量。当前，最为先进的离线规划算法采用的是将动态规划和启发式搜索相结合的办法来构建一套完整的策略。对于大规模问题，其主要瓶颈在于每一步迭代都会产生极其多的子策略。这些子策略会快速的耗尽所有的存储空间或者导致运算严重超时。为了解决这一问题，本文在前人工作的基础上提出了 PBPG 和 TBDP 这两个算法。PBPG 算法的主要创新点在于彻底的改变了之前先枚

6、举再选择的策略生成模式，直接构建最优化的模型为每个信念点直接生成所需的策略。因此在动态规划过程中，备选的策略不再快速的塞满内存空间，同时每一步迭代后可保留的策略数大大增加，并最终大幅度的提高了规划策略的质量。从实验结果上看，PBPG 算法在运行时间上比之前最好的算法加快了一个数量级，并随着可保留策略数的增加近似最优的求解了大部分的实验测试问题。TBDP 算法主要针对的是大状态DEC-POMDP 问题。其主要的创新点是使用基于测试的方法只为可达的状态和需要使用到的策略计算值函数。之前的算法，笼统的为所有的状态和策略计算值函数，因此带来了极高的计算量，无法求解大规模问题。TBDP 算法的另一个创新

7、点是提出了具有层次结构和随机参数的新的策略表示方法。该方法能够将策略生成转变为策略参数的最优化过程，从而进一步的提高了策略求解的效率。同时，TBDP 算法可方便的运行在多处理器的并行分布式计算资源上。在实验中，TBDP 算法首次求解了上万个状态的 DEC-POMDP 问题。无论是离线算法还是在线算法，在问题求解的时候都需要用到完整的DEC-POMDP 模型。但在大规模的现实问题中，完整的 DEC-POMDP 模型并不容易获得。主要原因：一、环境和智能体之间有复杂的物理关系，无法准确的用单一的概率函数来进行描述；二、即便可以通过相应的手段测量出概率值，太多的数据也将无法存储和表示，更无法用来计算

8、策略。因此，设计能直接与环境进行交互并获得策略的规划算法就成为求解此类问题的关键。因此本文还提出了基于展开式采样的蒙特卡罗规划算法 DecRSPI。该算法仅需要能用于采样的环境或者仿真器就能直接计算策略，而无需事先建立完整的 DEC-POMDP模型。更重要的是该算法有别于之前的算法具有相对于智能体个数的线性的时间和空间复杂度。在实验中，DecRSPI 算法顺利的求解了超过 20 个智能体的问题，而之前的算法一般只能求解 2 到 3 个智能体的 DEC-POMDP 问题。关键词：关键词：多智能体系统，马尔科夫决策模型，不确定环境下的规划，智能体间的合作与协调，分布式局部可观察马尔科夫决策过程。I

9、IABSTRACTABSTRACTPlanning under uncertainty is one of the fundamental challenges in Artificial In-telligence.Decision theory offers a mathematical framework for optimizing decisionsin these domains.In recent years,researchers have made rapid progress for decisionmaking in single-agent cases.This ena

10、bles relatively large problems to be solved bystate-of-the-art MDP and POMDP algorithms.However,research of decentralized de-cision making is still in its infancy and existing solutions can only solve very small“toy”problems.As a nature extension of Markov decision theory to multi-agent sys-tems,the

11、DEC-POMDPmodelhasveryhighcomputationalcomplexity,namelyNEXP-hard.This is not surprising given that agents in multi-agent settings not only have tokeep tracking on the state transition of the environment but also the potential behaviorsof the otheragents.As a result,the joint policy space is huge.Hen

12、ce how to search overthe joint policy space and find the best one is a key issue when solving a large DEC-POMDP.Due to the problem complexity,exact algorithms can solve tiny problems.Therefore,my thesis work focuses on developing effect algorithms for solving generalDEC-POMDPs approximately.Generall

13、y,planning in multi-agent systems can workeither in online or offline fashions.This thesis contributes to the literature by proposingboth online and offline algorithms.Furthermore,a model-free algorithm is presentedfor planning when the exact model is not available.Online algorithms do planning when

14、 interacting with the environment.During ex-ecution time,only very small region of the joint policy space can be visited.Moreover,online planning merely needs to choose an action for the current step and computingthe whole policy is not necessary.Given the reason above,online algorithm can s-cale be

15、tter when solving large real-world problems.Additionally,it is much easier foronline algorithms to take the advantage of communication and thereby improve the so-lution quality.However,online algorithms have their own constrains.The time forplanning is very limited because agents have to react to th

16、e environment immediately.In DEC-POMDP settings,each agent can only get its own local observations.Hence adistributedplanningframeworkisrequiredtoguaranteethecoordinationamongagents.Inordertocooperatewithothers,agentsmustreasonaboutallpossibleinformationheldby others and this type of information gro

17、ws exponentially over time.The communi-cation resource is often limited due to the band-width,environment and computationdevice.Therefore online algorithms must optimize the usage of communication dur-IIIABSTRACTing planning.To cope these challenges,a novel approach called MAOP-COMM wasproposed with

18、 the main contributions as follows:(1)a fast policy search method basedon linear programming to meet the online time-constraint;(2)a distributed planningframework based on a shared belief pool to guarantee coordination online;(3)a policy-basedmergingsolutionforhistoriestoidentifythemostusefulinforma

19、tionwhileboundthe usage of memory;(4)a new communication strategy by detecting the inconsistencyof the beliefs to make a better use of the communication resource.In the experiments,MAOP-COMM performed very well in a variety of testing domains.Offlinealgorithmscomputeacompleteplanpriortointeractwitht

20、heenvironment.The key advantages are:(1)there is no limit on planning time;(2)planning can takein a centralized manner as long as the outcome policy can be executed by each agentaccording its local information.The weakness is that the overall policy space must beconsidered,while leads to highly comp

21、utational cost.Currently,the leading approach-es for solving DEC-POMDPs offline combine dynamic programming with heuristicsearch to construct policies.The bottleneck is that the policies trees built at each stepgrow exponentially and run out of time and memory very quickly.To address this chal-lenge

22、,this thesis improves the existing work and proposes two novel solutions calledPBPG and TBDP.The contribution of PBPG rely on constructing the best policy foreach belief point directly instead of enumerating all candidates and selecting the bestone.Consequentially,more policy trees can be kept as bu

23、ilding blocks of the next it-eration and the total solution quality is greatly improved.In the experiments,PBPGachieved an order of magnitude improvement in runtime and get near-optimal solutionswhen the number of sub-policies is sufficiently large.TBDP is developed to addressthe challenge of the la

24、rge state space in DEC-POMDPs.The main contribution is touse trail-based evaluation for reachable states and only do the computation when neces-sary.State-of-the-art algorithms compute a value function for all states and policies andthereby cannot solve large problems due to the highly computational

25、 expense.Anothercontribution of TBDP is to introduce a new policy representation with layered structureand stochastic decision nodes.It formulates the policy construction as an optimizationover the parameter space and speeds up the policy generation process.Besides,TBDPcan be implemented in a distri

26、buted manner and lead itself the computational power ofmulti-core computers.In the experiments,TBDP solved a problem with more than tenthousand states.This is the first time that the problem with so many states can be solvedwithin the DEC-POMDP framework.The complete knowledge of a model is required

27、 by both offline and online algo-IVABSTRACTrithms.Unfortunately,theexactformofaDEC-POMDPisnotalwaysavailableinlargereal-world applications due to two major reasons:(1)the underlying physical modelmay be too complex to compute an exact probability for each state and action pair;(2)even such probabili

28、ties are available by some techniques,they may be too large to bestored in memory and perform any reasoning.Therefore,it is significant to develop alearning algorithm that can compute a policy by only interacting with the environment.Given the motivation above,a Monte-Carlo algorithm called DecRSPI

29、is proposed tolearnapolicyusingrolloutsamplesdrewfromtheenvironment.DecRSPIismodel-freeand requires only a simulator or an environment that can be sampled.The most impor-tant property of DecRSPI is the linear time and space complexity over the agent size.In the experiments,DecRSPI can solve a proble

30、m up to 20 agents while state-of-the-artDEC-POMDP algorithms can typically handle 2 or 3 agents.Keywords:Multi-Agent Systems,Markov Decision Model,Planning Under Uncer-tainty,CoordinationandCooperation,DecentralizedPartially-ObservableMarkoveDe-cision Process.V表格表格3.1线性规划的策略参数求解.363.2标准测试问题的实验结果.513

31、.3格子足球问题的实验结果.534.1线性规划的随机映射求解.644.2线性规划的随机策略改进.694.3PBPG 算法的实验结果.734.4TBDP 算法的实验结果.77XI插图插图1.1多智能体的老虎问题.72.1多智能体的决策模型.132.2两智能体的策略树示例.162.3MBDP 算法的求解思想1.213.1两智能体的在线规划流程.303.2在线规与离线规划的相似性.353.3两智能体的通讯决策流程.443.4历史信息展开和信念更新示例.473.5历史信息归并和策略执行示例.483.6两个智能体的 33 格子足球问题.523.7收益值随不确定阈值变化的实验结果.553.8通讯量随不确定

32、阈值变化的实验结果.564.1基于信念点的策略树生成示例.614.2不同算法的运行时间和收益值.754.3不同启发式组合的策略收益值.754.4两机器人的合作废物回收问题.784.5不同决策周期下 TBDP 算法的实验结果.784.6不同测试采样下 TBDP 算法的实验结果.795.1分层随机策略表示.835.2标准测试问题的实验结果.885.3分布式传感器网络问题.895.4分布式传感器网络的实验结果.90XIII算法算法2.1多智能体的动态规划.172.2基于联合均衡的策略搜索.182.3基于信念点的动态规划.192.4内存有限的动态规划.203.1历史展开和信念更新.303.2通讯受限的

33、在线规划.333.3带重启的随机策略搜索.383.4基于策略的历史信息归并.434.1基于信念点的近似策略生成.644.2基于测试反馈的动态规划.674.3基于启发策略是信念采样.684.4基于测试的策略值评价.704.5多线程的异步策略评价.715.1应用展开式采样的策略迭代.825.2蒙特卡罗参数估计.84XV主要符号对照表主要符号对照表MDP马尔科夫决策过程POMDP局部可观察马尔科夫决策过程MMDP多智能体马尔科夫决策过程DEC-MDP分布式马尔科夫决策过程DEC-POMDP分布式局部可观察马尔科夫决策过程I-POMDP交互式局部可观察马尔科夫决策过程POSG局部可观察随机博弈问题DP

34、多智能体的动态规划算法JESP基于联合均衡的策略搜索算法PBDP基于信念点的动态规划算法MBDP内存有限的动态规划算法IMBDP改进的内存有限的动态规划算法MBDP-OC基于观察压缩的内存有限的动态规划算法PBIP基于信念点的增量式策略删减算法PBIP-IPG基于信念点的增量式策略生成和删减算法MAOP-COMM通讯受限的多智能体在线规划算法PBPG基于信念点的近似策略生成算法TBDP基于测试反馈的动态规划算法DGD分布式梯度下降算法RTDP实时动态规划算法DecRSPI应用展开式采样的策略迭代算法I有限的智能体集合S有限的系统状态集合s系统的状态 s SAi智能体 i 可采取的动作的集合ai

35、智能体 i 的动作 ai AiA全体智能体的联合行动集A=iIAi a全体智能体的联合行动 a Ai智能体 i 可获得的观察的集合oi智能体 i 的观察 oi i全体智能体的联合观察集=iIiXVII主要符号对照表 o全体智能体的联合观察 o P(s|s,a)系统于状态 s 执行动作 a 后转移到状态 s的概率O(o|s,a)系统于状态 s 执行动作 a 后获得观察 o 的概率R(s,a)系统于状态 s 执行动作 a 后获得的收益b0系统的初始状态分布 b0(S)Qi智能体 i 的策略集qi智能体 i 的策略 qi QiQ所有智能体的联合策略集Q=iIQi q所有智能体的联合策略 q QV(s

36、,q)联合策略 q 在状态 s 上的期望值V(b,q)联合策略 q 在信念点 b 上的期望值 V(b,q)=sSb(s)V(s,q)XVIII中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：签字日期：中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子

37、版，允许论文被查阅和借阅，可以将学位论文编入中国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。公开 保密年作者签名：导师签名：签字日期：签字日期：第一章绪论第1章绪论1.1引言近年来，随着计算机硬件设备和人工智能技术的快速发展，大型的智能系统逐渐渗入到人们生活的方方面面，并起着越来越重要的作用。典型的例子包括用于家庭和医院等日常环境下的服务机器人，用于火灾和地震等恶劣环境下的救援机器人，以及用于城市交通和生态环境的智能监控网络等等。在这些典型环境中，智能体（Age

38、nt）都必须能够自主的根据传感器提供的局部环境信息做出决策。通常来说，传感器收集到的信息是带有噪声的，同时执行部件的控制也往往存在一定的误差。这些不确定性给智能体的决策提供了很大的挑战，因为智能体需要在决策中分析和考虑多种可能的情况。当有多个智能体参与行动时，情况会变得更加复杂，因为每个智能体都必须要考虑到其他智能体可能采取的行动和策略。如何在不确定性的环境下设计出高效的多智能体决策算法是当前人工智能最为重要的研究课题之一。在许多实际的应用问题中，智能体需要完成的是多步决策问题，也就是说智能体不仅仅要考虑行为的当前效果，还需要考虑该行为对未来决策的影响。多步决策问题同时也被称为序列化决策问题（

39、Sequential Decision-MakingProblem），而解决这一问题的过程被称作规划（Planning）。具体的说，规划的过程就是产生一个行动序列，使得智能体按照这个行动序列执行的时候能够达到某些目标，完成指定的任务。例如最短路径问题（Shortest Path Problem）就是经典的规划问题，规划的输入是一个连通的图以及一个起点和一个终点，图的边上带有权值表征两个节点之间的距离，规划的目标是找出这样的一个节点序列，使得机器人从起点移动到终点的路径和最小。本文研究的重点是自动规划问题（Automatic Planning），目标是设计算法，输入问题的模型表示，通过计算自动的

40、输出智能体所能执行的行动序列。经典的规划问题的模型由以下基本元素组成：一、问题的状态集，例如最短路径问题中的节点集；二、智能体的行动集，例如最短路径问题中从一个节点移动到另一个节点的动作；三、关于状态转移的描述，例如最短路径问题中，如果两个节点之间有边，则智能体可以从一个节点移动到另一个节点；四、问题的目标函数，例如最短路径问题中的目标点以及总路径最短的要求。许多人工智能的问题都可以转化为自动规划问题，例如国际象棋的求解就需要设计算法输入象棋的状态描述和规则，输出能战胜对手的下棋套路。经典规划（Classical Planning）问题往往不考虑状态转移的不确定性，例如1第一章绪论象棋的下子是

41、确定的。事实上，在许多现实问题中，动作的不确定性无处不在。例如机器人从一点移动到另一点可能因为轮子打滑等因素，不能准确地运行到目标点。在多步决策问题中，每一步行动的不确定性会被不断地积累放大，最终产生意想不到的结果，这个过程往往被通俗的称谓蝴蝶效应。解决的方案就是在规划的过程中完整的考虑每个动作各种可能的效果，同时要求从环境中获取动作的反馈，也就是说需要从无反馈的开环控制变为带反馈的闭环控制。在经典规划中每一步行动的效果是确定的，无须系统的反馈就可以准确的获知行动的效果。而在不确定性的环境下，动作可能有多种效果，就需要有反馈信息来预测动作实际产生的效果。例如在机器人移动问题中，机器人需要利用自

42、身的传感器信息比如摄像头和轮子的反馈来预测自己的实际位置，并根据这个实际的位置作出下一步的决策。由此可见，不确定性环境下的规划问题比经典规划问题要难得多。解决这一问题更一般的方法就是马尔科夫决策理论，这便是本文关注的重点。1.2不确定性环境下的决策与规划马尔科夫决策理论（Markov Decision Theory）为不确定性环境下的决策和规划提供了统一的模型表示和丰富的数学基础。它抽象出了智能体决策所需要的关键因素，并用数学模型进行严格的描述。这样就能最大限度的忽略智能体之间的个体差异，同时能体现出不同决策问题间的本质区别，方便对不同类别的决策问题进行理论上的分析。无论是智能软件（Softw

43、are Agent）还是实体机器人（Physical Robot）的决策问题都可以用统一的模型来表示和求解。对于同一类的决策问题也可以从理论上分析出问题的复杂度，证明是否存在多项式时间复杂度的最优算法。在马氏决策理论中，最关键的决策因素就是系统的状态（State）。它抽象出了智能体当前决策所需要的所有信息，也就是说智能体根据当前的状态就可以做出最优的决策而无需考虑状态之外的其他信息，比如历史状态和动作等。这就是状态的马尔科夫性（Markovian Property），也是马氏决策理论和其他决策理论的主要区别之一。对于单智能体（Single-Agent）的决策问题，可以用马尔科夫决策过程（MDP

44、）来进行建模和求解。在 MDP 的每个决策周期间，智能体首先从环境中获得系统的状态，并根据状态选择一个行动（Action）作用到环境中。这个动作将导致系统从一个状态转移到另一个状态，同时智能体获得一定的收益（Reward）。MDP 的转移函数（Transition Function）描述了系统从一个状态转移到另一个状态的概率，能够方便的对环境和动作的不确定性进行建模。而 MDP的收益函数（Reward Function）描述的是在特定状态下，智能体的某个行动所2第一章绪论获得的回报。与传统的基于目标的决策模型相比，MDP 的收益函数是对决策目标更加一般的表示。对于经典规划，目标状态可以用非常大

45、的收益值来表示，而每一步行动的代价则可以用一些较小的负收益值来表示。求解这样的一个MDP，所获得的决策就是用最少的步骤到达目标状态的一个规划。在 MDP 中，总的决策周期被称为 Horizon，可以是有限的也可以是无限的。MDP 的决策目标是求解出一个能够在总的决策周期内最大化系统收益和的策略（Policy）。正是因为状态的马尔科夫性方便了问题的求解，已经被证明 MDP 的问题复杂度是P，也就是存在多项式时间的最优算法。尽管如此，在大规模问题下，MDP 的快速求解仍然是非常困难的，因为状态的个数可能非常的多。MDP 的一个重要的扩展就是局部可观察的马尔科夫决策过程（POMDP）。在很多实际问题

46、中，智能体并不能直接获得系统的状态信息，其对于状态的观察来源于传感器收集到的带噪声的局部信息。例如移动机器人获取环境信息的主要途径是通过其身上配备的摄像头，而摄像头传回的一帧帧的图像代表的只是机器人所处环境的一个局部。在 POMDP 中，这些局部的反馈信息称为观察（Observation）。POMDP 中的观察函数（Observation Function）建模了智能体信息获取的局部性和不确定性。与 MDP 中的状态不同，POMDP 中一步的观察信息不再具备马尔科夫性。在 POMDP 的决策过程中，智能体不仅需要考虑当前的观察信息，也需要考虑过去的历史信息，从而分析从自身所处状态的一个概率分布

47、。这个关于状态的概率分布也被称为信念状态。由于概率分布是一个连续的空间，所以 POMDP 的求解要比 MDP 难得多。可以从理论上证明，POMDP 问题的复杂度是 PSPACE。所以对于一般问题要精确求解是十分困难的，因此研究的重点是找出高效的近似算法。老虎问题（Tiger Problem）是最为经典的 POMDP 问题，同时也最能体现不确定性环境下决策与规划的特点。老虎问题描述的是这样一个场景：一个机器人被关在一个密室中，密室的左右两边各有一扇门；一扇门后是珍贵的珠宝，而另一扇门后面是凶恶的老虎；如果机器人打开珠宝的那扇门，则可以获得大量的财富；但如果机器人打开的是老虎的那扇门则会被撕成碎片

48、；初始的条件下，机器人不知道哪边有老虎，只能隐约的听到门后老虎的咆哮声。这个问题用 POMDP 可以描述为：一、系统的状态有两个，分别是老虎在左边门后和老虎在右边门后，即 State=Tiger_Left,Tiger_Right；二、智能体（机器人）的动作有三个，分别是打开左边的门、打开右边的门和监听老虎的叫声，即 Action=Open_Left,Open_Right,Listen；三、智能体的观察也有三个，分别是听到左边门后传来老虎的叫声、听到右边门后传来老虎的叫声和没有听到老虎的叫声，即 Observation=Roar_Left,Roar_Right,None。问题开始的时候，老虎和珠

49、宝被随机的放置到两个门后。如果机器人知道老虎在哪扇门后，也就是说智能体3第一章绪论能够直接的获得系统的状态，老虎问题则退化成简单的 MDP 问题。根据其收益函数的定义，其最优策略是显而易见的：如果老虎在左边则打开右边的那扇门；如果老虎在右边则打开左边的那扇门。在 POMDP 的问题设定中，智能体不是直接的获得系统的状态而是状态的一个观察，这个观察一定程度上反映了当前系统的状态，但观察本身是具有不确定性的。在老虎问题中，机器人听到的是老虎的叫声，这个叫声可能时有时无，也可能很轻微。因为环境的因素，机器人无法准确的判断老虎的叫声是从哪扇门后传来的。这些都可以通过 POMDP 的观察函数来建模。初始

50、的条件下，因为机器人不知道具体老虎是在哪扇门后，所以对机器人来说老虎在左右两扇门后的可能性是等概率的。机器人要做的就是求解这个 POMDP，并得到一个策略：通过不断的监听老虎的叫声，直到以较大的概率确信老虎是在某扇门后，然后打来另一扇门，这样就能以较大的概率获得珠宝。总的来说，在马氏决策理论中，转移函数建模的是在不确定性的环境下动作的效果，观察函数建模的是信息获取的不确定性和不完整性。而收益函数建模的是问题的求解目标，也就是智能体在这个问题中所要完成的任务。在老虎问题中，收益函数设计成获得珠宝并避免老虎的伤害。如果机器人的电池容量有限，而每一步的动作都要消耗一定的电能，则收益函数可以设计成每一