论文部分内容阅读
在人工智能研究领域,基于智能体的形式化方法为智能系统的建模、设计和实现提供了统一的框架。智能体的一个基本特征是其在动态不确定环境中自主感知、行动和学习的能力。处理日益复杂实际问题的智能体,特别是各种形式的智能机器人,已经在人们日常生活和世界经济中扮演着越来越重要的角色,其影响范围可以说是近到人手一部的智能手机,远到遥远太空的人造卫星。通常来讲,感知信息总是不可避免带有各种误差和噪音的;执行机构的执行结果也具有不可预知性,甚至失败的情况。同时,还可能会有各种无法直接观测的隐藏信息。诸如此类的不确定性,为智能体的感知和规划任务带来了巨大的挑战。以马尔科夫决策过程(MDP)和部分可观察马尔科夫决策(POMDP)为代表的决策论规划理论为这类问题的最优化求解提供了重要的理论和算法基础。完全求解MDP和POMDP都面临所谓“维度诅咒”问题一即状态空间大小随状态变量的数目呈指数级增加。通过采用在线规划、分层规划、蒙特卡洛仿真、粒子滤波等技术设计MDP和POMDP的近似求解算法是目前的研究热点。本文以MDP和POMDP为主要理论依据,主要探讨大规模不确定性环境下的自动感知和规划问题,重点是为大规模MDP和POMDP问题设计高效的近似算法。特别地,本文提出基于MAXQ分层分解的MDP在线规划算法——MAXQ-OP,基于后验动作采样的MDP和POMDP蒙特卡洛在线规划算法——DNG-MCTS和D2NG-POMCP,以及基于POMDP信念更新模型的集合粒子滤波多对象跟踪算法——PFS。本文提出的分层在线规划算法——MAXQ-OP,同时结合了分层规划和在线规划的优势,为大规模MDP问题的分层在线求解提供了原理性解决方案。具体地,MAXQ-OP利用问题本身的MAXQ分层结构在线求解大规模MDP问题,使用启发式方法高效地搜索动作和宏动作空间,并使用启发函数给出搜索树上的终端节点值函数的估计值。MDP标准测试问题——出租车问题——上的实验结果显示MAXQ-OP相比传统在线规划算法,以极少的计算资源消耗,在线找到问题的近似最优解。作为MAXQ-OP算法的长期主要实验平台,RoboCup机器人世界杯—仿真2D机器人足球是一个规模特别巨大的完全分布式多智能体随机系统。以MAXQ-OP为主要决策框架的算法成功应用到科大“蓝鹰”仿真2D机器人足球队中,取得了RoboCup2D比赛多项世界冠军和全国冠军的好成绩,显示了MAXQ-OP算法应用于规模巨大的实际问题的重要潜力。近年来,蒙特卡洛树搜索(MCTS)在不确定性规划和学习领域引起了广泛的研究兴趣。MCTS的一个基本问题是利用和探索之间的平衡。本文针对MDP和POMDP的在线规划问题,提出新颖的基于后验动作采样的MCTS算法——DNG-MCTS和D2NG-POMCP。基本思想是把蒙特卡洛搜索树上某一节点执行某一动作并服从树上策略的前向仿真过程的累积回报看成是服从某一未知分布的随机变量,引入必要的隐藏变量来参数化这一未知分布,并根据贝叶斯方法更新隐藏变量的后验分布。进一步,使用Thompson采样根据某一动作成为最优动作的后验概率来随机选择该动作,以进行树上搜索。本文针对MDP和POMDP问题,分布提出DNG-MCTS和D2NG-POMCP算法,实验结果显示提出的算法在多个标准测试问题里面比领域最先进的算法(包括UCT和POMCP)效果更好,表明其有望适用于规模巨大的实际问题,并取得好的实验结果。自主机器人在动态环境中识别、跟踪和确认潜在的多人状态的能力对成功完成社会化的人一机器人交互任务起到非常关键的重要作用。在线多人跟踪问题等价于复杂POMDP的实时信念更新。主要挑战包括:事先不知道实际有多少人;基于计算机视觉算法的人的探测结果不可避免有误报和漏报情况;并且,人和机器人都处于复杂的相对运动当中。针对这些挑战,本文把多人集合看成联合状态,多人探测结果看成联合观察,近似计算相应的联合观察函数,最终提出新颖的基于集合定义的粒子滤波算法——PFS。针对个体确认问题,提出基于期望最大化(EM)的个体确认算法从更新后的联合粒子集合中辨认并报告每一个人的状态信息。较传统多对象跟踪算法而言,基于集合的形式化使得PFS不需要进行显式的观察到目标的数据关联,从而在具有复杂噪音和错误的观察情况下具有更好的容错性和鲁棒性。最终的完整PFS算法在PETS2009数据集中取得了,就CLEAR MOT指标而言,比领域前沿算法更好的实验结果。真实机器人平台CoBot上的测试结果显示PFS应用到实际机器人上的有效性。