一种基于π—MaxQ学习的多机器人协作方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于π—MaxQ学习的多机器人协作方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要： 针对多机器人协作中存在的并发性较少、协商通信的实时性与高效性较差以及问题学习空间维数灾难等问题，提出一种基于π-maxq学习的多机器人主体协作方法。定义了机器人的公共知识、信念、目标、意图、承诺、信任、知识更新等心智状态，扩充了基于心智状态的KQML（Knowledge Query and Manipulation Language）通信原语，并基于MaxQ方法构建了联合奖励函数。实验证明了方法的有效性。
关键词： 多机器人； 协作； 分层学习； 心智
中图分类号： TP24 文献标识码：A 文章编号：2095-2163（2013）03-0014-04
A Cooperative Method for Multi Robots based on π-MaxQ
KE Wende1，2 ，HONG Bingrong1 ， CUI Gang1，CAI Zesu1
（1 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001 China；
2 Department of Computer Science， Guangdong University of Petrochemical Technology， Maoming Guangdong 525000， China）
Abstract： Aimed to the problem in which there exist the little concurrency， low real time and efficiency， and the curse of dimensionality in multi robots’ cooperation， a cooperative method for multi robots based on π-MaxQ is proposed in the paper. Firstly， the mental states such as common knowledge， belief， goal， intention， promise， trust， knowledge update， etc.， are defined. Secondly， the KQML communication primitives based on the mental states are expanded. Thirdly， the confederative rewarding function based on MaxQ is constructed. The experiments proves the validity of the proposed method.
Key words： Multi Robots； Cooperation； Hierarchical Learning； Mental
0 引 言
现如今，多机器人主体任务协作问题是机器人学与人工智能的研究热点，其研究主要体现在两方面。一是研究多主体行为的方法和协作技术，例如博弈论、经典力学理论等，但该方法仅满足特定协作环境，当主体数量、结构、通信关系发生变化时，协作机制容易失效；二是侧重于对问题的规划以及求解过程，研究静态或动态环境下的主体心智变化，即信念、愿望、意图等，以环境促使心智变化，主动实现协作目标，由于该方法较为实用灵活，受到了研究者们的广泛关注[1]。传统的基于心智模型的协作任务容易导致空间冲突、时间冲突与资源冲突，为实现协作任务最优，研究者们多采用强化学习进行解决，例如，文献[2]面向智能主体基本心智行为，采用强化学习的多步收益最大预测特性，求解整体效果最优；文献[3]建立足球机器人双层协作模型，并采用模糊强化学习思想判断机器人当前心智状态以提高学习效果；文献[4]分析了多机器人动态环境特性，采用强化学习实现协作追捕，等等。
以上研究取得了相关成果，但仍存在一些问题：
（1）多采用非逻辑因子描述多机器人协作，较少体现出协作并发性；
（2）未能考虑多机器人协商通信的实时性与高效性；
（3）当问题空间增大时，学习过程出现维数灾难，计算复杂度增大，收敛性降低。
为解决这些问题，提高多主体协作效果，并基于文献[5]已做研究的基础上，本文在分层强化学习中引入π演算的多任务并发特性，定义机器人公共知识、信念、目标、意图、承诺、信任等心智模型，扩充KQML通信原语以描述机器人主体通信进程，使多机器人主体协作过程具备了数理分析与心智推理的特点，取得了理想科研效果。
1 多机器人主体系统
多机器人主体系统实现了物理上的分布性和逻辑上的分散性，其结构如图1所示。
由图1可知，多机器人主体系统结构中各部分的功能分析如下：
（1）心智状态描述多机器人主体的理，可以与其它机器人主体及环境进行信息交互，并根据环境变化及协作要求，自主修改内部状态，其信念为机器人主体对工作环境的基本认知，进而由此产生愿望，判断未来环境场景，其行为能力可受意图控制，体现出有限形式的承诺；
图1 多机器人主体系统结构
Fig. 1 Architecture of multi robots第3期 柯文德，等：一种基于π-MaxQ学习的多机器人协作方法 智能计算机与应用 第3卷
（2）学习模块基于分层强化学习MaxQ方法，通过将问题空间分层与降维，在子空间内实现策略学习与复用，提高了策略搜索速率；
（3）知识库包含机器人主体对自身、世界、以及其它主体的描述；
（4）通信线程负责主体间的动作与世界信息传输，满足通信语言KQML的规范中消息传输约定，在理想情况下，要求无通信延迟并遵循消息队列，实现其顺序发送与接收。
2 分层强化学习MaxQ方法
分层强化学习通过扩展经典MDP（Markov Decision Process），以变量描述执行动作的若干时间步，从而形成半马尔科夫决策过程（Semi Markov Decision Process， SMDP），[6-7]使智能主体同时遵循决策的顺序性与时间性，由此实现多时间步的动作建模。现给出SMDP定义为[8]：
定义1 5元组，SMDP=，其中，状态转换联合概率分布函数为Pa_Nss′：S×A（s）×S×IN[0，1]，记为P（s′，N|s，a），奖赏函数为Rass′：S×A（s）IR，记为r（s，a）且r（s，a）=E{rt+1+γrt+2+…+γN-1rt+N}。以上表述中，s为状态，a为行为，N为累计时间步次数，IN为自然数集，IR为实数集。
在SMDP下的Bellman最优值函数与最优动作-状态对函数分别为：[9]
（3）
MaxQ方法构建起问题空间的分层结构任务图，对MDP与策略π分解，获取子任务集T={T0.T1，……Tn}与对应子策略集π={π0，π1，……πn}。集合T中的子任务定义为3元组Ti=，其中，子策略πi对应Ti，终止谓词Ei划分激活状态集Si与结束状态集Li，且Si与Li受Ti约束，伪奖励函数ri在学习过程中对Li分配奖励值。在其后的任务图中，T0为根节点子任务，执行节点Ti可通过调用执行其它子任务节点或基本动作而完成构建，同时上层节点将依照相应策略选择后继节点以形成动作执行路径，并由各层中对该层的动作选择来施加必要的约束。
3 基于机器人心智状态协作的MaxQ学习
在多机器人系统中，通过机器人心智状态演算实现机器人行为的理性和自主性，而分层强化学习则通过机器人主体来感知外部环境与其它主体、执行策略以获取奖励，通过对环境信息进行推理与搜索以实现策略最优，最后再通过子任务空间中的学习，以不断增强行为效果并获取最大收益。
3.1 心智状态
机器人主体具备有限理性，即一定程度的自主能力与心智态度，同时也具有并发特征。这一特性就决定了多机器人主体通信进程的演算可由π演算实现[10-11]，该演算方式正可有效体现动态结构的进程内以及进程间的良好交互效果。π演算中，多机器人系统由若干个相互并行的通信和动作进程组成，进程间通过互补链路进行通信，通信内容包含知识、信念、愿望、意图、及目标等，对其中各部分的定义形式分列如下：
（1）公共知识（Common knowledge）：机器人执行言语行为后，相信所关联句子真实性，将其用公式表示，即为：
（4）
其中，机器人a在t时刻执行言语行为，关联得出新的句子Γ，成为多机器人系统的公共知识。
（2）信念（BEL）：机器人通过环境接口En-interfacei获取外部信息后，判断某状态是否会出现，将其用公式表示，即为：
（5）
（3）目标（Goal）：机器人通过环境接口En-interfacei获取外部信息后，判断其状态满足目标状态，将其用公式表示，即为：
（6）
（4）意图（Intention）：机器人通过环境接口En-interfacei获取当前状态意图，并请求执行该意图关联的行为，将其用公式表示，即为：
（7）
（5）承诺（Promise）：多机器人判断个体无法独立完成目标时，联合意图后作出共同承诺，并各自在子范围内完成相应任务，将其用公式表示，即为：
（8）
（6）信任（Trust）：参与协作的机器人彼此信任，并相信对方具备独立完成相关子任务的能力，同时承诺建立协作后采取行动，将其用公式表示，即为：
（9）
（7）知识更新（Knowledge Update）：机器人在t时刻完成协作后，通过环境接口En-interfacei获得新知识并更新到公共知识库，将其用公式表示，即为：
（10）
3.2 基于心智演算的KQML通信线程描述
KQML主体通信语言是基于言语行为理论（speech act）而开发形成，可将通信视为物理上的行动[12-14]，在π-MaxQ的KQML通信语义中，A为Source，即发起协商的机器人，B为Destination，即接收协商任务指派的机器人。现对通信中各主要线程的描述如下。
（1）Assigning-role：Source（消息源）要求Destination（消息终点）转变角色，对应通信原语为：
Assigning-role （ABWANT（AKNOW
（BINT（BTASK））））
（11）
Precondition：INT（ATASK），ANT（BKNOW（BTASK））；
Post condition： KNOW（AKNOW（BTASK）），NOW（BINT（BTASK））
其中，A、B分别为Source与Destination，WANT描述意图，KNOW描述能力获知。
（2）Forming-team：Source要求Destination到达预定地点，形成目标队形，对应通信原语为：
Forming-team（ABWANT（AKNOW（BBEL
（BTASK））））
（12）
Precondition： INT（ATASK），WANT（BKNOW（BTASK））
Post condition：KNOW（AKNOW（BTASK）），NOW（BBEL（BTASK））
（3） Reporting-conflict：Source向Destination传递冲突地点，对应通信原语为：
Reporting-conflict（ABWANT（AKNOW（BTASK）））
（13）
Precondition：WANT（ATASK），NOW（BTASK）
Post condition：KNOW（ATASK），NOW（BTASK）
（4） Tracking：Source通知Destination跟踪移动目标，对应通信原语为：
（5） Updating-location：Destination跟踪目标并返回目标位置信息，对应通信原语为：
3.3 基于心智状态的MaxQ学习
设在离散时间SMDP下的子任务Ti状态集与子节点动作分别为Si与Ta，即时奖赏ri（s，a）=Vπ（a，s），其中，Vπ（i，s）描述从s′开始执行Ti的期望奖赏值，该值可通过Ti的分层策略π的投射函数获得，则式（1）、（2）的期望奖赏值函数与状态动作值函数bellman的方程分别为：
由上式可知，完成函数Gπ（i，a，s）=∑s′，σPπi（s′，σ|s，a）γσQπ（i，s′，π（s′））。
若从根节点T0的s状态开始，反复递归执行上层子任务策略选择下层子任务的过程直到最终基本动作，则投射值函数为：
多机器人主体判断环境信息完备性以决定联合学习或者独立学习，并在各层中由行为回报更新状态-行为对的值，当到达协作目标状态时，伪奖励函数ri对Li分配正值，否则为负值，当所有子任务结束后，计算ri累计和。在多机器人主体协作系统中，单个机器人根据状态-行为对搜索具有最大投影值函数的行动策略，并在每个分层空间内实现各自的Nash平衡，使协作决策收敛[15]，由此则使得对大规模问题空间内的整体策略搜索获得了实现。
在π-MaxQ心智模型中，协作成功与失败的奖励值分别为μ与-μ，奖励函数r∈[-1，1]，阈值为0.09μ。定义机器人向分配任务的目标位置移动时的奖励函数为：
（19）
其中，α为奖励系数，xg（t）为t时刻目标坐标，x（t）为t时刻机器人位置，σ为阈值距离，当机器人与足球的有效距离达到阈值以内时，机器人得到奖励。
定义机器人将球传给队员的奖励函数如下：
（20）
其中，x0i（t）为对方机器人。
综合上面两式，定义联合奖励函数为
（21）
其中，k1、k2为加权系数，且α1，α20，α1+α2=1。
4 实验验证
多机器人系统由Mini Robot与Mos2007仿人机器人组成，Mini Robot机器人的协作目标是突破对方防守并将足球踢到对方半场，协商项为{tracking， accept， update-location， refuse}。仿真中，选取通信工具为JDK1.1.8与JKQML，对Mini Robot 仿人机器人通信线程进行KQML原语扩充部分为：
（tracking
：source Mini-1
：destination Mini-3
：content（Opponent-Mos-1（geoloc long 39w 1at 50 n） （detect-time 5S））
：reply-with id1
：language kif
：ontology geo-model3）
/////////////////////////////////////////////////
（accept
：source Mini-3
：destination Mini-1
：content（Opponent-Mos-2）
：inreplyto id1
：langu age kif
：ontology geo-mode2）
Mini Robot机器人的心智状态受其目标位置影响，当未到达对方半场区域时，增大Belief、Goal、 Intention状态值， 减少Knowledge状态值，提高主动进攻心智，机器人根据KQML通信执行协商项内容，向目标位置移动以获取更大的正奖励，并在协商过程中进行学习。图2所示即为Mini Robot一次成功突破Mos2007机器人并将足球踢到对方半场，图3则比较了基于π协作演算的Q学习、改进π-Q学习算法以及本文提出的π-MaxQ方法的成功次数。由图3可知，π-MaxQ学习算法成功次数最高。
图2 仿人机器人平台上一次成功的协作突破踢球
Fig.2 A successful cooperative process of kicking
ball by humanoid robots
图3 学习方法比较
Fig. 3 Comparison between learning algorithms
5 结束语
本文在多机器人主体协作的MaxQ学习方法中引入π心智演算过程，构建起具有学习与通信能力的机器人心智状态模型，对机器人主体的公共知识、信念、目标、意图、承诺、信任、知识更新等进行了定义，并构建起多机器人主体协商模型。实验表明该模型较好地提高了任务协商及协作的成功率。
参考文献：
[1]李超明，苏开乐.一个基于智能的MAS模型及其方法论[J].计算机研究与发展，2007 （6）：980-989.
[2]郭锐，吴敏，彭军，等.一种新的多智能体Q学习算法[J].自动化学报， 2007， 33（4）： 367-372.
[3]曹卫华， 徐凌云， 吴敏. 模糊Q学习的足球机器人双层协作模型[J]. 智能系统学报， 2008， 3（3）：234-238.
[4]朴松昊， 孙立宁， 钟秋波， 等. 动态环境下的多智能体机器人协作模型[J]. 华中科技大学学报：自然科学版， 2008， 36（增刊Ⅰ）： 39-41， 52.
[5]柯文德， 朴松昊， 彭志平， 等. 一种基于π演算的足球机器人协作Q学习方法[J]. 计算机应用， 2011， 31（3）：654-656， 669.
[6]HENGST B. Discovering hierarchy in reinforcement learning[D]. Sydney University of Ne South Wales， 2003.
[7] UTHER W T R. Tree based hierarchical reinforcement learning[D]. Pittsburg： Camegie Mellon University， 2002.
[8]沈晶，刘海波，张汝波，等. 基于半马尔可夫对策的多机器人分层强化学习[J]. 山东大学学报：工学版， 2010， 40（4）： 1-7.
[9]沈晶. 分层强化学习方法研究[D]. 哈尔滨：哈尔滨工程大学， 2006.
[10]史忠植. 智能主体及其应用[M]. 北京：科学出版社，2000.
[11]于振华， 蔡远利， 徐海平. 基于π网的多Agent系统建模与分析[J]. 系统工程理论与实践， 2007，7： 77-84.
[12]AUSTIN J L.How to do things with words[M].0xford：Oxford Univ.Press，1962.
[13]刘淑华，田彦涛，刘金芳.扩展KQML在多移动机器人仿真系统中的应用[J].吉林大学学报：信息科学版，2005，23（5）：500—505.
[14]康辉， 曾莹莹， 刘志勇. 基于PI-演算的移动通信服务研究与建模[J]. 通信学报， 2009， 30（4）： 11-16.
[15]HARMATI I， SKRZYPCZYK K. Robot team coordination for target tracking using fuzzy logic controller in game theoretic framework[J]. Robotics and Autonomous Systems， 2009， 57： 75-86.