论文摘要
近年来,智能体及多智能体规划问题成为人工智能领域新的研究热点,且有着广泛的应用前景。本文针对马尔可夫决策过程及其相关理论展开研究,对这些决策理论在接触现实世界的应用时所面临的问题及解决方法做了一定的探讨,最后对相关的一类基本决策算法进行了一定的理论分析和改进。主要涉及到以下几个方面的工作:(1)较为系统的研究了与智能体及多智能体不确定性规划相关的几类基础决策模型及算法。模型部分,首先是最基本的马尔可夫决策模型,然后是在此基础上加入观察不确定性的部分可观察马尔可夫决策模型,以及进一步加入多智能体合作的分布式部分可观察马尔可夫决策模型和多智能体对抗的部分可观察的随机博弈模型。算法部分,针对上述几类模型,均按照后向迭代和前向搜索两大类进行了对比分析。最后,进一步讨论了与时间抽象相关的半马尔可夫决策模型及Option理论,这一理论是设计分等级的规划框架及算法的基础。(2) Robocup仿真2D提供了一个研究大规模不确定环境下多智能体规划问题的标准测试平台。结合对该平台的一些必要的说明,分析了在这种接近现实世界应用的问题中,进行整体规划所需要处理的一些子问题的设计方法,并通过结合现有马尔可夫决策过程相关理论对这些问题进行建模及分析,给出该平台更一般的研究意义。(3) Option理论对应了时间抽象的概念,它为马尔可夫决策理论更多的接触现实世界应用提供一个分等级规划的研究方向。针对类似Robocup仿真2D这种带有观察不确定性的大规模多智能体系统的规划问题,在部分可观察随机博弈模型的基础上,结合策略启发,信念状态压缩,因子化表示法及Option理论,给出了一个新的基于动态行为生成器的决策框架,并在此基础上设计了一个以快速寻找可行解为目标的实时启发式搜索算法。最后,结合仿真2D这一标准平台,对这一决策框架及算法的实用效果进行了检验。(4)基于Option的理论分等级规划时,大规模问题中子策略的求解效率也至关重要。实时动态规划是求解马尔可夫决策过程的一类较新的方法。这类方法除了具有求解效率上的优势外,还很容易被设计成anytime的工作方式。实时动态规划类算法结合了启发式搜索与值迭代的技术,算法的核心问题是分支选择策略与收敛判据。分支选择策略决定了值迭代的收敛速度,收敛判据用以判定解的最优性。通过对启发式函数上界及下界的分析及利用,给出了一个新的收敛判据,称为最优行动判据,以及一个更适合实时算法的分支言癫呗浴W钣判卸芯菘梢愿绲谋甓ǖ鼻白刺憔纫蟮淖钣判卸┝⒓粗葱?而新的分支选择策略可以加快这一判据的满足。并据此设计了一个有界增量实时动态规划算法(BI-RTDP)。在两种典型仿真实时环境的实验中,BI-RTDP显示了比现有相关算法更好的实时性能。最后,通过对算法异步值迭代机制的研究改进了其在搜索图上处理环的能力,并展示了算法离线求解效果。
论文目录
相关论文文献
标签:多智能体论文; 马尔可夫决策过程论文; 部分可观察随机博弈论文; 半马尔可夫决策过程论文; 机器人足球论文; 实时动态规划论文;