一个描述机器人团队形成的动态演化模型

摘要

目前在多机器人领域，对组织、团队和群体概念比较混乱，团队形成的研究大都停留在定性分析阶段。借鉴Markov过程和进化计算，从协作主体层和能力层研究了机器人团队和组织的区别及团队的形成机制。提出并全面描述了一个机器人团队形成的动态演化模型，目前国内外尚无类似模型。该模型不仅能对机器人团队有一个整体描述，而且能定量描述团队形成时的动态演化过程。

正文

单个机器人的智能化使个体的机器人变得更聪明, 而多机器人系统则不但有一批聪明的机器人, 还要求它们能有效地合作。它不仅反映了个体智能, 而且反映了群体智能, 是对人类社会生产活动的想象和创新的探索 ^[1]。多机器人系统能有效地运行, 必须对多机器人构成的团队或组织加以描述, 并有适当的运行控制机制。团队和组织是两个不同的概念, 组织是“机器人-机器人”模式, 而团队是“机器人-集体目标-机器人”模式, 它强调多机器人集体目标高于个体目标。国内外学者对多机器人系统的组织的形成做了大量的研究 ^[2,3,4,5], 但是对团队的形成研究还十分匮乏, 同时也缺乏能够定量描述及预测随动态环境的不断变化的方法或模型。

《1 机器人团队形成的非形式化描述》

1 机器人团队形成的非形式化描述

机器人团队具有以下两方面的特点:

1) 在团队与其成员之间的关系方面, 团队表现为团队成员对团队的强烈归属感与一体感。团队成员强烈地感受到自己是团队的一员, 并且由衷地把个体目标与集体目标联系在一起。团队成员对团队具有无限忠诚, 决不允许有损害团队利益的事情发生, 并且非常具有团队荣誉感, 常为团队的成功而获得正的刺激 (奖励) , 为团队的困境而获得负的刺激 (惩罚) 。在处理个人利益与团队利益的关系时, 团队成员会义无反顾地采取团队利益优先的原则, 个人服从团队。归属感与一体感主要来源于团队利益目标与其成员目标的高度一致。

2) 在团队成员之间的关系上, 团队表现为成员之间的相互协作及共为一体。团队成员彼此把对方都视为一家人, 都是团队的一分子, 它们相互依存。成员之间可兼容各自的差异性、独特性;相互间能深信不疑, 托以重任;相互帮助, 相互协作。团队成员在交互过程中逐渐形成了一系列的行为规范, 一方面他们和谐相处, 充满凝聚力;另一方面它们又彼此进化, 其终极目标是为了促成更好的合作, 追求团队的集体绩效。

定义1 单体机器人单体机器人R是指能够通过传感器感知自身状态和部分周边环境, 并带有限的通信装置, 在有障碍物的 (包括静止的和移动的) 环境中, 面向目标能够自主学习、决策、运动, 从而完成一定工作的机器人。

定义2 机器人团队机器人团队由单体机器人根据任务临时所形成的、一个联系最为紧密的有机组合体, 它可以视为一个自治区域。自治区域内机器人间的合作称为内层合作, 自治域之间存在着的或松或紧的合作方式称为外层合作。自治区域中具有较强通信能力和组织能力的机器人作为该组织的中心, 称为组长。组长定义的计算活动和联合意向代表了该组要从事的计算活动和联合意向。组长代表全组对外联系合作。由于动态环境的变化、任务的不同, 团队的组合是动态变化的, 相应的组长也是动态变化的。

定义3 机器人社会机器人团体是所有有联系的单体机器人、机器人团队的集合。

《2 机器人团队的形式化描述》

2 机器人团队的形式化描述

机器人团队是松耦合网络问题求解器, 这些问题超出个体能力范围。网络中每个机器人是一个独立的问题求解器, 没有一个求解器具有问题求解所需的足够专长、资源和信息, 并且不同的求解器具有求解问题不同部分的专长, 所以合作是必须的。

定义4 协作主体组成机器人社会的机器人、机器人团队统称为模型的协作主体 (cooperate robot, 简称CR) 。协作主体是具有在规定的时间内, 利用有限资源完成分配的任务, 并力求使自己收益极大化的实体。用统一的框架形式化描述为

CR=<id_-ros, id_-robot, T, CA, RU, EU>,

其中id_-ros为机器人团队标识符, 用来标识一个机器人团队编号;id_-robot为承担相应团队的机器人标识符, 即前面定义的机器人团队组长, 可以有多个组长, 在没有形成机器人团队结构前, 该元素为空;T为团队的集体目标, 通过对T分解可以得到机器人团队子目标, T={T₁, …, T_n}, T_i可以根据任务复杂性的要求进一步分解, 它对模拟机器人团队完整过程起着重要的作用, 一方面环境任务的需要触发了机器人团队的组建, 另一方面机器人团队的运行又左右着环境的变化;CA为机器人的工作能力;RU为机器人团队的行为规范, 即机器人团队任务组织、分配规则, 是相应的机器人团队组织中所有机器人必须遵守的行为规范;EU为团队合作的收益, 表示一个机器人团队实现组织目标T后从外部环境或者上一级组织得到的报酬。

由于机器人团队的动态演化过程, 可视为机器人团队随环境以及目标需求不断变化, 不断进行集体目标、协作主体及协作主体之间的协作关系的适应性调整的过程。集体目标在模型中可以根据环境以及任务目标变化来体现。机器人协作关系的描述, 关键在于描述在新的环境任务需求下机器人间是否建立协作关系。

对于任意2个实体, 总是处于2种可能状态之一, 即协作或不协作。如果存在协作关系, 则处于状态1;如果不存在协作关系, 则处于状态0。如果在t₀时存在协作关系, 那么, 在面对新的环境任务需求即t₁时, 它们仍然存在协作关系的概率为P₁₁, 不存在协作关系的概率为P₁₀, 0≤P₁₁, P₁₀≤1, P₁₁+P₁₀=1;如果在t₀时不存在协作关系, 那么, 在面对新的环境需要即t₁时, 它们存在协作关系的概率为P₀, 0≤P₀₀, P₀₁≤1, P₀₀+P₀₁=1。那么, 任意机器人对的协作关系用下面转移矩阵刻画:

$\begin{array}{l} 1 0 \\ \begin{array}{l} 1 \\ 0 \end{array} [\begin{matrix} Ρ_{11} & Ρ_{10} \\ Ρ_{01} & Ρ_{00} \end{matrix}] ‚ \end{array}$ $\begin{array}{l} 1 0 \\ \begin{array}{l} 1 \\ 0 \end{array} [\begin{matrix} Ρ_{11} & Ρ_{10} \\ Ρ_{01} & Ρ_{00} \end{matrix}] ‚ \end{array}$

转移矩阵元素用贝叶斯法则得到。

假定协作主体选择是否与其他协作主体进行协作是相互独立的。假定机器人团队面临新的环境任务需求时, 协作主体CR_i与有关实体CR_j建立协作关系的行动集为

$A_{i} = {a_{i 1}, a_{i 2}, \dots, a_{i (n - 1)}} 。$ $A_{i} = {a_{i 1}, a_{i 2}, \dots, a_{i (n - 1)}} 。$

a_ij代表CR_i与有关CR_j建立协作关系的一个特定行动。CR_i选择与CR_j协作和不协作的先验概率分别为P_ij (c₁) , P_ij (c₀) , 则有0≤P_ij (c₁) ≤1, 0≤P_ij (c₀) ≤1, P_ij (c₁) +P_ij (c₀) =1。

$Ρ (a_{i j}) = Ρ (a_{i j} | c_{1}) Ρ_{i j} (c_{1}) + Ρ (a_{i j} | c_{0}) Ρ_{i j} (c_{0}) 。$ $Ρ (a_{i j}) = Ρ (a_{i j} | c_{1}) Ρ_{i j} (c_{1}) + Ρ (a_{i j} | c_{0}) Ρ_{i j} (c_{0}) 。$

由贝叶斯公式得

$\begin{array}{l} Ρ (c_{1} | a_{i j}) = Ρ (a_{i j} | c_{1}) \cdot Ρ_{i j} (c_{1}) / Ρ_{i j} (a_{i j}) 。 \\ 同理 Ρ (c_{0} | a_{i j}) = Ρ (a_{i j} | c_{0}) \cdot Ρ_{i j} (c_{0}) / Ρ_{i j} (a_{i j}) 。 \end{array}$ $\begin{array}{l} Ρ (c_{1} | a_{i j}) = Ρ (a_{i j} | c_{1}) \cdot Ρ_{i j} (c_{1}) / Ρ_{i j} (a_{i j}) 。 \\ 同理 Ρ (c_{0} | a_{i j}) = Ρ (a_{i j} | c_{0}) \cdot Ρ_{i j} (c_{0}) / Ρ_{i j} (a_{i j}) 。 \end{array}$

所以得到转移矩阵元素:

$\begin{array}{l} Ρ_{11} = \sum_{i, j = 1}^{n} Ρ (a_{i j} | c_{1}) Ρ (c_{1} | a_{i j}), \\ Ρ_{10} = 1 - Ρ_{11}, \end{array}$ $\begin{array}{l} Ρ_{11} = \sum_{i, j = 1}^{n} Ρ (a_{i j} | c_{1}) Ρ (c_{1} | a_{i j}), \\ Ρ_{10} = 1 - Ρ_{11}, \end{array}$

$\begin{array}{l} Ρ_{01} = \sum_{i, j = 1}^{n} Ρ (a_{i j} | c_{1}) Ρ (c_{1} | a_{i j}), \\ Ρ_{00} = 1 - Ρ_{01} 。 \end{array}$ $\begin{array}{l} Ρ_{01} = \sum_{i, j = 1}^{n} Ρ (a_{i j} | c_{1}) Ρ (c_{1} | a_{i j}), \\ Ρ_{00} = 1 - Ρ_{01} 。 \end{array}$

通过运用上述过程, 综合所有机器人的协作情况, 即可描述机器人团队是否存在随环境任务需求变化的动态演化过程。

《3 机器人团队形成的动态演化模型》

3 机器人团队形成的动态演化模型

人类社会通过进化、发展, 已成为一个区域化、层次化的社会。组成机器人社会的基础, 是众多不同角色、不同能力、不同知识水平的机器人个体。团队的不同形成机制, 决定了团体的行为和效能。这种特性在某种程度上, 给机器人团队形式提供了仿生学依据。

机器人团队与团队之间的协作关系的动态演化是团队对环境和被求解问题的适应方式。根据对求解环境的适应性, 团队的形成有2种情况, 一种是预先根据问题求解的要求及各种约束设计好组织结构, 这种团队在整个问题求解过程中组织结构不发生变化。由于组织结构固定, 所以求解过程中机器人之间的交互、任务分配以及负载平衡等问题相对比较简单, 缺点是对开放环境下的问题求解, 特别是当求解过程中目标发生变化时适应能力差, 求解能力会因环境条件变化下降甚至无法求解。另一种团队形成方式是当组织结构形成以后可以根据环境和被求解问题的要求进行自身结构的调整, 这就是团队协作关系的动态演化。由于团队协作系统本身是一个开放系统, 环境、约束以及求解目标会不断发生变化, 使得具有演化能力的团队协作关系有更好的环境适应性, 更高的求解效率和较低的计算复杂性。

机器人团队形成的动态演化可以由以下特征来识别:具有集体目标的多个团队临时性的合作, 为的是完成复杂任务, 并分享合作的风险和利益。每个团队都专注本组织的核心能力, 并采用外部协作的策略。集体目标的一致和和谐性不是靠团队表面层次的信念, 而是取决于团队的深层次的意图和愿望。机器人团队形成的动态演化的实现并不意味着多了一个架构于团队之上的层次的实现, 而是通过深化内部和团队之间的交互系统的使用来减少团队形成的代价。

机器人团队形成的动态演化是2个以上单体机器人有时限的互惠互利的合作组织, 并以最小的代价, 最大的收益和最快的反应感知未知环境。它优化了团队, 随集体目标的完成而消亡。图1给出一个机器人团队形成的动态演化模型。

《图1》

图1机器人团队与团队之间的协作关系的动态演化模型

Fig.1 Dynamic evolution model of the cooperative relationship among teams

该模型由3个层次组成:协作主体层, 能力层, 关系层。在协作主体层实现具有在规定的时间内, 利用有限资源完成分配的任务, 并力求使自己收益极大化。在能力层则是以可操作性非常强的“对象”为核心, 实际上, 从CR层到CA层的计算就是一个面向对象的设计过程。关系层以团队为基本单位, 可方便地组织各团队发挥各自的优势, 迅速高效地完成不同团队之间的共同任务, 以集成、优化、协调为核心。

该模型的团队协作关系的动态演化在关系层完成。影响机器人团队协作关系建立的主要因素是机器人在新的环境任务需求下的类型, 即支付函数。假定机器人团队表现在环境任务上的行动是类型依存的, 那么, 如何根据支付函数确定机器人面临新的环境任务需求时的最优行动集, 是机器人团队在协作的动态演化过程中必然面临和必须解决的决策性问题。根据机器人不同的价值目标, 决策的依据可分为:机器人团队整体支付函数的最大化和机器人团队成员支付函数的最大化2种。

假定新形成的机器人社会是由n个协作主体构成的, 每个协作主体都可能与其他n-1个协作主体建立协作关系。令a_ij表示在新的任务需求下协作主体CR_i与CR_j交互时与建立协作关系相关的行动, A_i={a_i1, a_i2, …, a_{i, (n-1)}}表示CR_i与其他n-1个实体交互时与建立协作关系的行动向量, 设u_ij (c₁, a_ij) 表示在新的任务需求下, CR_i实施行动a_ij的情况下与CR_j协作的支付函数, u_ij (c₀, a_ij) 表示在新的任务需求下, CR_i实施行动a_ij的情况下与CR_i不协作的支付函数。P_ij (c₁, a_ij) 表示CR_i采取行动a_ij的情况下, 选择与CR_j协作的概率; P_ij (c₀, a_ij) 表示CR_i采取行动a_ij的情况下选择与CR_j不协作的概率。机器人团队在新的任务需求下采取行动集A_i的总支付函数为

$\begin{array}{l} C_{i} (A_{i}) = \sum_{j = 1}^{n - 1} Ρ_{i j} (c_{1} | a_{i j}) u_{i j} (c_{1}, a_{i j}) + \\ \sum_{j = 1}^{n - 1} Ρ_{i j} (c_{0} | a_{i j}) u_{i j} (c_{0}, a_{i j}) 。 \end{array}$ $\begin{array}{l} C_{i} (A_{i}) = \sum_{j = 1}^{n - 1} Ρ_{i j} (c_{1} | a_{i j}) u_{i j} (c_{1}, a_{i j}) + \\ \sum_{j = 1}^{n - 1} Ρ_{i j} (c_{0} | a_{i j}) u_{i j} (c_{0}, a_{i j}) 。 \end{array}$

考虑机器人团队成员支付函数最大和机器人团队整体支付函数最大化, 则A^*_i需要满足

$\begin{array}{l} C (A_{i}^{*}) = \max {C_{i} (A_{i})} 和 \\ C (A_{i}^{*}) = \max {\sum_{i = 1}^{n} C_{i} (A_{i})} 。 \end{array}$ $\begin{array}{l} C (A_{i}^{*}) = \max {C_{i} (A_{i})} 和 \\ C (A_{i}^{*}) = \max {\sum_{i = 1}^{n} C_{i} (A_{i})} 。 \end{array}$

这样团队形成的演化问题转化为求C_i达到最大值时的动作向量A^*_i, 即组合优化问题。优化问题的搜索空间是离散的、有限的数学结构, 因此可以用二进制编码, 所以进化计算可用于分析团队形成的演化过程。

《4 结语》

4 结语

借鉴Markov过程和进化计算, 从协作主体层和能力层研究了机器人团队的形成机制。提出并全面描述了一个机器人团队形成的动态演化模型, 目前国内外尚无类似模型。该模型能对机器人团队有一个整体描述, 并利用有限Markov链和进化计算, 定量描述了团队形成时的动态演化过程。通过该模型, 用户能整体、动态地把握机器人团队的协作状况, 还能够依据模型的描述, 对机器人团队面临新任务需求时的协作关系和行为做出预测。

展示更多