·610- 智能系统学报 第15卷 相对较强的性能，但有些任务本身可能过于复 数倍增长，同时可行解以及路径长度的计算量将 杂，甚至不可能完成，例如空间上相互独立的任 正比于l/2。现有的方法在目标数量较少时有着 务。在多机器人系统中，异构机器人可以针对 不错的效果，但是当目标较多时会出现计算量大 不同层次的任务进行专门化设计，可以应用于复 耗时长且不能得到较好的结果。因此，本文提 杂的感知任务中。 出使用SOM来解决这一难题。 现有的主动感知方法是反应性的，不受历史 状态的影响，是一个马尔可夫过程。状态感知的 质量会影响算法性能，可以通过选择最优感知位 置来改进6。这通常是一个短视问题，从控制策 略上来说是贪婪的”。最近，研究者们把主动感 知问题从主动视觉扩展到了更为复杂的场景和任 务：1)主动的目标识别、检测与跟踪；2)广阔的环 境，如农场；3)具有丰富的社会知识、求知能力和 图1多目标主动感知场景 非近视性的规划方法。但是这些感知任务大都是 Fig.1 Multi-target active perception scene 单机器人系统⑧，且很少应用在多目标场景。 13 自组织映射特征网络 为了弥补这一差距，本文提出了一个基于自 如图2所示，SOM是一种竞争性的双层神经 组织映射网络(self-organizing map,SOM)的分散式 网络且在输出层的样本空间中形成新的拓扑结 异构机器人的框架来解决多目标主动感知的任 构2。在SOM的训练过程中，多个神经元通过 务。在发现多目标的位置后，自组织映射算法为 竞争协作完成对输入样本的模式分类。网络中的 无人机团队规划出一条时间最短的路径，从而执 输入神经元x与输出神经元y通过权值ω相 行监视、拍照等任务。 连，同时，近邻的输出神经元之间也通过权值相 连。SOM的输出结果保持自组织的拓扑结构， 1相关工作 映射到多维的向量空间中。 1.1主动感知 被动感知与主动感知的区别在于环境状态量 输出神经元身 是否与智能体有交互。在被动感知中，智能体使 用一组被动观察量来分类、估计、预测或推断与 权值⊙ 环境相关的一些信息。在主动感知中，智能体 通过采取行动并观察环境如何变化，以动态的方 输人神经元x 式与环境交互更改状态。在此过程中，通过环 境状态的变化，观察变得依赖于行动。 图2典型的SOM结构 文献「3-4]证明了主动感知系统的性能高度 Fig.2 Typical SOM structure diagram 依赖于机器人所选择的观测位置，但是其目标函 2问题建模 数为机器人团队的观测奖励，且不同位置的观测 奖励值是预先设定的。本文的研究目的是让机 图1中给出了异构机器人的主动感知框架。 器人团队最小化旅行时间同时遍历所有目标，在 无人机团队中一部分通过搭载的传感器设备搜索 这个过程中无人机团队的路径点是SOM算法规 区域的目标，另一部分执行快速遍历的主动感知 划出来的而不是从提前设定的一系列路径点序列 任务。任务目标是在满足旅行预算的前提下为 中进行选择。 机器人团队R={,2,…,R}规划一个由路径点序 1.2带邻域的多旅行商问题 列X={x1,2,,x}组成的平滑路径，使其能够监 图1给出了本文的研究场景，这是一个带邻 视环境中的每一个目标N={m1,2,…,nw小，并使得 域的多旅行商问题(multiple traveling salesman 团队的旅行时间Tsum=tn+in+tn+…+tn最短。考 problem with k-neighbourhood,k-MTSP)10 k-MTSP 虑到实际环境中，被感知目标并非无体积的质 是典型的NP-hard问题，不能在多项式时间内 点，而且机器人上一般搭载有感知设备，如雷达、 求出最优解。对于n个目标来说，存在着[(m-1)]2 深度相机等。因此目标w是一个圆形的感知区 条可能的路径。可行解的数目随着n的增加呈指 域Sw∈R,其感知半径为k。无人机只需要访问相对较强的性能，但有些任务本身可能过于复 杂，甚至不可能完成，例如空间上相互独立的任 务 [5]。在多机器人系统中，异构机器人可以针对 不同层次的任务进行专门化设计，可以应用于复 杂的感知任务中。 现有的主动感知方法是反应性的，不受历史 状态的影响，是一个马尔可夫过程。状态感知的 质量会影响算法性能，可以通过选择最优感知位 置来改进[2，6]。这通常是一个短视问题，从控制策 略上来说是贪婪的[7]。最近，研究者们把主动感 知问题从主动视觉扩展到了更为复杂的场景和任 务：1) 主动的目标识别、检测与跟踪；2) 广阔的环 境，如农场；3) 具有丰富的社会知识、求知能力和 非近视性的规划方法。但是这些感知任务大都是 单机器人系统[8] ，且很少应用在多目标场景。 为了弥补这一差距，本文提出了一个基于自 组织映射网络 (self-organizing map,SOM) 的分散式 异构机器人的框架来解决多目标主动感知的任 务。在发现多目标的位置后，自组织映射算法为 无人机团队规划出一条时间最短的路径，从而执 行监视、拍照等任务。 1 相关工作 1.1 主动感知 被动感知与主动感知的区别在于环境状态量 是否与智能体有交互。在被动感知中，智能体使 用一组被动观察量来分类、估计、预测或推断与 环境相关的一些信息[9]。在主动感知中，智能体 通过采取行动并观察环境如何变化，以动态的方 式与环境交互更改状态[6]。在此过程中，通过环 境状态的变化，观察变得依赖于行动。 文献 [3-4] 证明了主动感知系统的性能高度 依赖于机器人所选择的观测位置，但是其目标函 数为机器人团队的观测奖励，且不同位置的观测 奖励值是预先设定的[3]。本文的研究目的是让机 器人团队最小化旅行时间同时遍历所有目标，在 这个过程中无人机团队的路径点是 SOM 算法规 划出来的而不是从提前设定的一系列路径点序列 中进行选择。 1.2 带邻域的多旅行商问题 图 1 给出了本文的研究场景，这是一个带邻 域的多旅行商问题 (multiple traveling salesman problem with k-neighbourhood, k-MTSP)[10]。k-MTSP 是典型的 NP-hard 问题，不能在多项式时间内 求出最优解。对于 n 个目标来说，存在着 [(n−1)!]/2 条可能的路径。可行解的数目随着 n 的增加呈指 数倍增长，同时可行解以及路径长度的计算量将 正比于 n!/2。现有的方法在目标数量较少时有着 不错的效果，但是当目标较多时会出现计算量大 耗时长且不能得到较好的结果[11]。因此，本文提 出使用 SOM 来解决这一难题。 图 1 多目标主动感知场景 Fig. 1 Multi-target active perception scene 1.3 自组织映射特征网络 xi yj ωi j 如图 2 所示，SOM 是一种竞争性的双层神经 网络且在输出层的样本空间中形成新的拓扑结 构 [12-16]。在 SOM 的训练过程中，多个神经元通过 竞争协作完成对输入样本的模式分类。网络中的 输入神经元 与输出神经元 通过权值 相 连，同时，近邻的输出神经元之间也通过权值相 连 [3]。SOM 的输出结果保持自组织的拓扑结构， 映射到多维的向量空间中。 输出神经元 yj 权值 ωij 输入神经元 xi 图 2 典型的 SOM 结构 Fig. 2 Typical SOM structure diagram 2 问题建模 R = {r1,r2,· · ·,rR} X = {x1, x2,· · ·, xi} N = {n1,n2, · · ·,nN} Tsum = tr1 +tr2 +tr3 +· · ·+trR sN ∈ R 图 1 中给出了异构机器人的主动感知框架。 无人机团队中一部分通过搭载的传感器设备搜索 区域的目标，另一部分执行快速遍历的主动感知 任务[17]。任务目标是在满足旅行预算的前提下为 机器人团队 规划一个由路径点序 列 组成的平滑路径，使其能够监 视环境中的每一个目标 ，并使得 团队的旅行时间 最短。考 虑到实际环境中，被感知目标并非无体积的质 点，而且机器人上一般搭载有感知设备，如雷达、 深度相机等。因此目标 nN 是一个圆形的感知区 域 ，其感知半径为 k。无人机只需要访问 ·610· 智 能 系 统 学 报 第 15 卷