使用成对机器人分散化搜索多个未知瞬时射电源

Chang-Young Kim ,  宋德臻 ,  Jingang Yi ,  吴新宇

工程（英文） ›› 2015, Vol. 1 ›› Issue (1) : 58 -65.

PDF (8290KB)
工程（英文） ›› 2015, Vol. 1 ›› Issue (1) : 58 -65. DOI: 10.15302/J-ENG-2015010

使用成对机器人分散化搜索多个未知瞬时射电源

作者信息 +

Decentralized Searching of Multiple Unknown and Transient Radio Sources with Paired Robots

Author information +
文章历史 +
PDF (8488K)

摘要

我们开发了一种分散化算法，来协调一组移动机器人搜索未知瞬时射电源。除了移动能力和通信及传感范围有限，机器人团队还必须应对信号源匿名性、短暂的传输时间和可变的发射功率带来的挑战。我们提出了一种两步式方法：首先，基于检查站的同步功能，对机器人用于追踪信号源位置的可信度函数进行了分散化；其次，提出了一种用于协调机器人的分散化规划策略，以确保存在检查站。我们分析了该算法的内存使用情况、通信数据量和搜索时间。实现了该算法，并将其与其他两种探索式算法进行了比较。实验结果显示，在三种算法中，分散化算法用最少的内存换来了最快的搜索时间。

Abstract

In this paper, we develop a decentralized algorithm to coordinate a group of mobile robots to search for unknown and transient radio sources. In addition to limited mobility and ranges of communication and sensing, the robot team has to deal with challenges from signal source anonymity, short transmission duration, and variable transmission power. We propose a two-step approach: First, we decentralize belief functions that robots use to track source locations using checkpoint-based synchronization, and second, we propose a decentralized planning strategy to coordinate robots to ensure the existence of checkpoints. We analyze memory usage, data amount in communication, and searching time for the proposed algorithm. We have implemented the proposed algorithm and compared it with two heuristics. The experimental results show that our algorithm successfully trades a modest amount of memory for the fastest searching time among the three methods.

关键词

无线定位 / 联网机器人 / 瞬时目标

Key words

wireless localization / networked robots / transient targets

引用本文

引用格式 ▾
Chang-Young Kim,宋德臻,Jingang Yi,吴新宇. 使用成对机器人分散化搜索多个未知瞬时射电源[J]. 工程（英文）, 2015, 1(1): 58-65 DOI:10.15302/J-ENG-2015010

登录浏览全文

4963

注册一个新账户 忘记密码

1 前言

元线传感器网络（WSN）技术的高速发展，提供了众多优秀的信息收集工具。但是，WSN也可能对我们的安全和隐私造成显著威胁（例如，敌人可能会在某个地区部署传感器以检测军队动向）。在大片地区部署的大量微型传感器难以通过人工搜索的方式发现并消灭。我们正在开发使一组移动机器人能够执行这一任务的算法。在这个“机器人网络”对抗“传感器网络”的情境中，每一方都有各自的优势和局限性。机器人可以移动，而传感器则不能。机器人知道自己所在的位置以及收到的信号强度（RSS）读数。但是，机器人不能解码传感器网络的协议，必须将传感器视为普通射电摞。因此，除了通信和传感范围的限制外，信号源的匿名性、短暂的传输时间、可变的发射功率以及未知的信号源数量，都对机器人造成了挑战。

根据之前的工作，我们提出了一种两步式方法：首先，基于检查站的同步功能，对机器人用于追踪信号源位置的可信度函数进行了分散化；其次，提出了一种用于协调机器人的分散化规划策略，以确保存在检查站。

我们的规划算法可以确保分散化的可信度函数实现不定期同步，并对内存和通信需求进行显式分析。此外，我们算法的预期搜索时间对射电源的数量不敏感。我们实施了该算法，并在基于真实传感器数据的模拟环境下，与两种探索式算法进行了对比。实验表明，在三种算法中，此算法用最少的内存换来了最快的搜索时间。

2 相关工作

对多个瞬时射电源的搜索，与基于射频（ RF ）的定位和多机器人移动估计和规划有关。

基于射频的定位技术在近期的发展，可以被视为“友好”射电源的定位，因为研究者或者假设单个射电源持续发送射电信号（类似灯塔）[1.2］，或假设机器人／接收器是网络的一部分，并理解数据包的详细信息［3,4］。但是，对于未知网络，这种信息并不总是可用。当信号源不合作时，由于RSS具有随距离减弱的特点，因此RSS读数将成为主要的定位信息。在无法获得信号源的信号发射功率时，位置不同的监昕者［5,6］或天线阵列[7]之间的RSS读数比例，已被证明可以有效地获取承载及／或距离读数。

在多机器人研究领域，对机器人位置和姿态的分散化估计，近来得到了广泛的关注。Durrant-Whyte[8]根据分布式卡尔曼滤波器框架开发了分散化评估技术。Leung等[9]则利用检查站的概念解决了分散化多机器人定位问题，其特点是在交流机器人观察结果后，对观察结果进行延迟同步。研究者根据通信约束条件，将这一概念推广到了分散化信息传输方案[10]方面。我们的问题与之类似之处在于，我们可以受益于距离和方位感知模型，但不同之处则是，我们侧重于估计瞬时目标的位置，而非机器人自身的位置。

同样，在多机器人研究领域，Pereira等[11]提出了在保持与邻接设备连通性的同时，在传感和通信限制下进行分散化规划的概念。通过使用分散化多机器人，Bhadauria等[12]解决了数据收集问题（DGP），即由多个机器人从己部署的传感器网络中收集信息。在研究中，他们将DGP设定为旅行推销员问题（TSP）的实例，并制订了一个包含两个子路线的计划。其中之一是逆时针路线、另一个则是顺时针路线，以确保两个子路线可以覆盖全部己部署的传感器节点。分散化规划的另一方面则是同步。Martinez等［13,14］分析了分散化多机器人的移动同步问题，推出了一个使用认同一跟踪算法的本地互联路线代理网络。这些有关通信和传感限制的工作激励了我们的工作。和流行的迫逃游戏不同，我们问题中的射电源并不移动。但是，固定节点并不会让问题变得更加简单，因为信号源是瞬时的，并且可能具有不同的发射功率，从而导致了不同性质的问题。

我们研究小组对不同设置和限制下的瞬时射电源搜索问题进行了研究［15,16］。其中最为领先的研究，是文献［17,18］中提出的用于单一机器人的贝叶斯定位方案，及其在多机器人方面的扩展［19,20］。本文建立在之前会议论文[21]的基础上，与现有搜索方法的不同在于将可信度函数分散化，并提出了新的分散化规划算法。

3 问题定义

我们问题的定义和假设包括以下几个方面。

(1)机器人和射电源处在开放 2D 平面空间中。

(2)所有机器人都有无限的通信距离和无限的传感距离。

(3)所有机器人都通过全球定位系统（ GPS ）获知自身位置。 GPS 时钟也为同步提供了准确的时间。

(4)机器人不知道射电源的发射功率，并且发射功率可能随时变化。但是，射电源的位置不会变化。

对于新的分散化方法，我们将采取与对应集中化版本中相同的问题定义［17 20］，这些研究中的搜索问题可以分为两类子问题。

定义1 （传感问题）：在给定 RSS 读数及其对应的与机器人之间距离的情况下，更新机器人对元钱电信号源的可信度函数。

定义2 （规划问题）：给定可信度函数，规划机器人轨迹以提高搜索效率。我们将在本文稍后给出可信度函数的具体定义。这是一种蒙特卡罗型算法，在检测射电源时使用了下列停止时间，搜索条件：如果可信度函数大于预设阔值Pt ，则视为发现了射电源。现在我们从传感问题开始讨论。

4 分散化的可信度函数

可信度函数根据RSS读数和机器人位置追踪射电源分布。它们通常建立在贝叶斯框架和天线模型的基础上以实现增量更新。在我们之前有关瞬时未知射电摞定位的研究［17,19,20］中，我们提出了一种时空栅格（SPOG),作为机器人的通用可信度函数。让我们首先回顾该函数，然后再进行SPOG的分散化。

4.1 SPOG 的一般回顾

SPOG 将搜索区域分戚相同尺寸的小网格。定义网格单元索引变量为网格单元索引集合，n为总单元数。 SPOG 追踪两种可能情况：Ci表示单元i包含射电源的情况， 表示单元i在检测到发射信号时属于活动源的情况。 c.1 实际上表示多个源之间的相对发射率，是一个时间维度的签名。将P(C)定义为事件 的概率。 P(Ci） P(）定义了瞬时射电源的时空行为。

定义，叫作为机器人索引变量，其中m为机器人总数，M为机器人索引集合。请注意，由于我们稍后会将机器人两两配对，因此m始终为偶数。离散时间k或对应的连续时间 tk 表示机器人检测到发射信号的时刻。以作为机器人l在K时刻的位置，为所有机器人在k时刻的位置。以离散随机变量＇作为第l个机器人在k时刻的 RSS 读数。定义作为所有 RSS 读数在k时刻的离散随机向量为对应的数值。根据惯例，我们使用小写的随机变量或向量符号来表示其数值。定义作为从开始搜索到tk时刻传感获得的所有RSS 信号的集合。定义 为给定 情况下，单元i包含至少一个射电源的条件概率。类似的，我们定义和。假设在k时刻时机器人观察到事件。此时需要更新网格的后验概率根据文献[17]，这实际上是一个嵌套的多元贝叶斯过程。由于更多 RSS 读数随时间推移进入系统，将逐渐收敛直至，此时表明问题定义中设定的搜索条件得到满足。

4.2 分散化 SPOG (D-SPOG)

在分散化系统中，每个机器人都需要通过内部积累RSS 读数保持自身的本地 SPOG ，并在其他机器人进入其通信范围时，与其他机器人交流信息。但是，文献[17]所述的集中 SPOG 取决于完整观测集合主 的严格顺序，机器人不能随意使用其接收到的部分数据来生戚本地SPOG。此外，由于机载内存容量有限，因此机器人不能永久保留其读数以便未来信息交流。

在解决该问题前，让我们先来仔细审视分散化系统。在分散化系统中存在3种类型的离散事件：检测事件是指一台机器人检测到发射信号的时刻，交会事件是指一台机器人进入另一机器人通信范围的事件，规划事件是指一台机器人启动新的路径规划的时刻。回想一下，k是检测事件的时间索引变量。用j和k别代表交会事件和规划事件。在本文中，定义 用于描述连续时域中的3个事件。为了避免温乱，我们也可以使用简化版，用tk和tj代表对应的事件时间。用tk代表第k个规划期的开始时间。

有效的协调计划，应当使机器人可以相互交流信息，使所有机器人在j时刻具有相同的观察结果集合: ，其中tj ≥ tk。在该时间，所有机器人都可以将其 SPOG 更新至时间K。通过这种方式，可以将集中的 SPOG 分散到所有机器人并实现同步 Leung 等[9]提出了“延迟同概念，将其用作检查站 我们将 定义为检查站。请注意，每个机器人的每个检查站都有两个时间变量：它开始于一个较早的检测事件的时间，结束于未来交会事件的时间，这是因为信息总是由检测事件生成，并由交会事件同步。

图1显示的信息流程图，展示了检查站概念以及分布式成对机器人如何通过 D-SPOG 传输信息。请注意，在图1中，将机器人两两配对，这是因为需要两个机器人来获取未知可变发射功率的射电源的信号比我们忽略了同组机器人之间的通信，因为同组机器人总是可以通过规划彼此交流。根据垂直方向的弧线箭头，我们可以看到和均为检查站。

为了建立D-SPOG,，剩下的问题是每台机器人如何储存和交流信息。假设是机器人l的最近一个检查站。在时刻更新后，机器人的D-SPOG将根据检查站的性质，通过虚拟集中SPOG同步更新至。机器人只需储存其自身在时刻后的位置和 RSS 读数，从而显著节约了存储空间。由于没有检测到信号的机器人可能不知道信号发射的时间，因此除 RSS 读数外，每台机器人还需要保存其轨迹。定义为机器人内部生成的从时刻到当前时刻t,的测量值集合：

图1. 四对机器人的信息流程图示例。灰色矩形表示机器人的交会事件。垂直方向的弧形箭头表示通讯范围内机器人进行的信息交流。黑色和白色圆形分别表示检测和没有检测到活动射电信号的机器人事件。

式（1）中，为机器人轨迹，为该时段的 RSS读数。类似的，我们通过分别用和代替，定义和。

我们定义机器人在交会时间的测量值集合为，其中包括来自其机载传感器和其他机器人的信息。为了描述机器人遭遇另一机器人之前的瞬间，我们引人符号。很明显。在时刻，机器人遭遇机器人，该机器人在信息交换前瞬间的测量值集合为，其中为机器人最近一个检查站的检测事件时间。请注意并不一定相同。两台机器人首先比较两个事件，因为更近的时间意味着更近的D-SPOG。另一台机器人则应当根据较近的时间同步其SPOG。在完成SPOG 同步后，它们需要同步测量值集合。请注意，在同步前机器人的测量值集合为，机器人的测量值集合则为。在不失一般性的前提下，我们假设，同步过程即为：

式（1）中，通过抛弃时刻间的测量值，得到，从而减少内存使用量。

在交会事件后，每台机器人都需要搜索是否可以建立更新的检查站。对于机器人，其将检查确定该测量值集合是否包含来自所有其他机器人的信息，以检测在第k次到第1次检查事件之间发生的检测事件，其方法是搜索的最大值，条件为和，从而有

                    

其中是一个逻辑运算，在不满足关系条件的情况下返回0，否则返回1。只有当存在非负解决方案的情况下，才可以建立新检查站，从而更新D-SPOG。在更新后，很明显D-SPOG等于延迟为的SPOG集中更新。我们从而得到下列引理。

引理1：为确保在检查站正确更新SPOG，每台机器人自身储存的信息量和在两台机器人交会事件时交流的信息量，均为，其中为当前时间，为最近一个检查站的检测事件时间。

证明：每一台机器人都需要储存D-SPOG，其占据的内存空间为。在最差情况下可能包含了个 机器人轨迹，以及从到的RSS读数。由于轨迹存储使用了固定的期限，并且信号发射平均数与时间呈线性关系，因此每台机器人上存储的总信息量为。因为在机器人交会时需同步 D-SPOG和它们的测量值集合，所以引理成立。

但是，如果只有一台机器人与其他机器人地理隔绝，导致其无法与其他机器人建立通信，此时将无法建立检查站。将没有边界，各机器人可能会很快用尽内存而导致故障。为解决这一问题，我们提出了一种分散化的规划方法，以确保检查站的不定期存在。

5 分散化规划

分散化规划策略需要考虑到检查站的存在、通信距离极限、同步和搜索时间。我们通过对文献［17,18 ]内现有的山脊行走算法（ ridge walking algorithm, RWA ）进行分散化，建立了新的规划策略。

5.1 简要回顾 RWA 和成对 RWA (PRWA)

在SPOG或D-SPOG 中，是单元i含有射电源的条件概率。RWA 在这种射电源空间分布规律的基础上，为单个机器人规划路径。我们通过使用平行于地平面的平面，生成水平集 ，其与山脉状分布图在高度处相交。由此产生的交集 ，包含了在平面上方的所有单元。通常包含多个不连续的成分。图2（a）中的不连续轮廓图就是 的例子。我们将每个成分中的山脊定义为沿着其主导方向的最长曲线段[18]。我们知道，每个山脊靠近潜在信号源的可能性都很高。我们生成了一个涵盖所有山脊的 TSP 问题路线。对于非山脊部分，机器人将以最快速度移动通过。图2 ( a）中的红色实线和蓝色虚线分别表示在山脊和非山脊部分的移动。对于山脊部分，机器人所花费的时间，正比于后验条件概率在山脊对应孤立水平面上部分的总和。这使机器人可以将绝大部分时间用于搜索山脊，从而直观地产生了文献[18]中的 RWA。在搜索多个信号源方面，RWA 表现出了出众的收敛性能和可扩展性。

图2. 使用4对机器人进行分布式规划的结果示例。（a）机器人的DRPWA 轨迹示例，红色实线和蓝色虚线分别代表在山脊和非山脊区域的移动；（b）时间环上的环内移动；（c）环内移动对应的机器人对方向变化；（d）使用空间环空间而非欧几里得空间进行的环空间移动示例。

PRWA将RWA 扩展到规划一组机器人的路径，以处理文献[19, 20]中所述的未知和变化的发射功率。首先，PRWA 开发了一个基于成对机器人间RSS 比率的成对传感模型，而不是假设已知射电源的发射功率，从而拓展了SPOG。其次，PRWA 通过尽量减少信息脑实现同组机器人的协调，从而可以在规划中将一对机器人视为一台超级机器人。我们将继承这种配对传感模型，并通过这种分散化的方法协调成对机器人。

5.2 分散化 PRWA (DPRWA)

和RWA 相似，DPRWA 协调成对机器人，使其在连接所有山脊的 TSP 路线上巡逻。我们为每个规划期生成一个 TSP 路线。事实上，每个规划期分为两个部分：较短的环间移动，用于相邻规划期间的 TSP 路线过渡，之后是较长的环内移动，用于为机器人分配在 TSP 路线巡逻的时间。

(1) 环内和环间移动：让我们先从环间移动开始。在规划期开始前，每对机器人都要计算 TSP 路线。所有机器人实际上都通过同步的 D-SPOG 分享相同的 TSP路线。环间移动让机器人可以从当前的 TSP 路线移动到下一条路线。TSP 路线为每台机器人安排了一个预定的起始位置（将在接下来介绍环间移动初始位置时详细介绍）。因此，可以在建立规划期 TSP 路线后，立即预测环间移动所需的时间。定义为第第对机器人的环间移动时间。为了同步每一对机器人的环内移动启动时间，每一对机器人都需要等待所有其他对机器人到达各自的起始位置。定义 为最长移动时间：对于因移动距离较短而提前到达的机器人，它们需要等待然后才能开始同步的环内移动。同步方法将在第 5.2(3)节中详细描述。为了节省时间，机器人以最快速度移动，以缩短环间移动时间。

现在让我们来介绍环内移动。由于 TSP 路线是一个连续的环，因此可以将其绘制为时间坐标上的环形，其圃周是一对机器人遍历整个 TSP 路线的时间，定义为。如果我们确定映射中的一个对应点，那么蹦才就是一对一的。例如， TSP 路线最左侧的点（按字母顺序最小的点），对应于时间环上以绿色五角星表示的9点位置，如图2 ( a）和图 2 ( b）所示。所有机器人都分享相同映射规则，以同步其在时间环上的位置。引进时间环可以方便我们的规划。在时间环下，环间移动可以简化为图2( d）。

如图 2 ( b）所示，每一对机器人都在时间环上均匀分布。定义 和， 分别为时间环上第对机器人的位置和速度。机器人在时间环上的速度是统一的，基于时间环的定义。初始时分配奇数和偶数对机器人分别顺时针和逆时针在时间环上移动，其状态分别表示为1和-1 。请注意，有台机器人，即 m/2 对。因此得到：

分别为各对机器人的初始位置和速度。图2 ( b）展示了四对机器人的初始位置和方向（以各机器人朝向的方向表示）。当两对机器人在时间环J:交会时，它们会交流信息并反转移动方向。因此，每对机器人在时间环上的移动，表现为以其初始位置为中心在时间环上往返移动，如图2 ( c）所示。

定义为环内移动时间。机器人对必须尽可能长的执行环内移动，以确保存在检查站。

引理2：每一对机器人至少有一个检查站，如果环内移动时间为

证明：从初始位置开始，第对机器人遇到其相邻的u-1和 u+1 对机器人，并返回其初始位置，时间为2τ0/m。其到达的最远点为半个圆周长以外，即 τ0/2 。两次交会带来了其下游（从下半圈的 u+1 处）和上游（从上半圈的u-1处）的信息。想象信息是由上游和下游方向距离最远的一对机器人发出的。当信息到达第对机器人时，其中包含了来自所有对机器人的信息。此时分为两种情况：机器人对的数量为偶数或奇数。在偶数情况下，由于速度统一，因此τ0/2是第对机器人收集信息的确切时间。式（3）具有非负解，并建立了一个新的检查站。在奇数情况下，证明过程类似，但在遭遇另一组机器人前需要再经过半个周期。

图1显示了图 2 ( b）和图2( c）中 对机器人在环内往返移动时的信息流和存在的检查站。

( 2）内存使用和预期搜索时间： DPRWA 确保了不定期检查站的存在，从而保障了搜索性能。为测量算法性能，我们使用了两个指标：每台机器人的内存使用率和每个射电源的预期搜索时间。

对于内存使用，根据引理2，我们可以得到以下定理。

定理 1: DPRWA 保证 D-SPOG 与集中 SPOG 之间的延迟差不超过为实现这一目标，每台机器人需要内存空间。

射电糠的预期搜索时间必须取决于源发射率。假设射电源以频率为的 自松过程发送信号。在文献[16]中，我们介绍了单机器人单目标情况下的预期搜索时间(EST)。让我们将这一分析延伸到 DPRWA。将搜索时间记为 。与文献[18]中对 RWA的EST 分析类似，我们将收敛条件从概率阔值收紧到信号饱和条件。如果一对机器人在收到信号发射时与射电源的距离在以内。，则视为该射电源己被发现。将 设置为较小值，以保证在听到信号发射时，必须达到概率阔值。 由此定义了一个传感圃，其中心为射电源，半径为 。 定义和分别为在射电源距离半径范围内和范围外移动的时间。因此有

从而得到以下定理。

定理 ：射电源的预期搜索时间 的上限为

                        

证明：根据文献[16]中的定理 ，瞬时射电源的预期搜索时间为

式（7）中，为搜索开始时到机器人首次进入射电源距离半径范围内的时间。该定理建立在一般情况的基础上，即搜索过程可以被建模为一个延迟替代更新奖励过程[22]。在本文情况中，更新期从机器人对在每个规划期中首次进人传感圈开始。该阶段与规划期并不完全相同，但预期时长与规划期相同。由于搜索开始于第一个规划期的环间移动，所以我们将概率事件定义为机器人对在环同移动时遭遇射电源的事件。因此有

                   

由于搜索地区面积很大，所以事件是小概率事件。从而有。由于第一次进入传感圈的点可以是时间环上的任何一个点，所以其在时间环上均匀分布。同时，我们有m/2对机器人在时间环上均匀分布，从而有

由于搜索地区通常远大于传感地区 我们根据式（ 6）得到

由于每个更新期都是独立同分布的（ i.i.d. ），所以我们可以应用文献[16]中的定理1。由于与独立，将式（9）和式（ 10 ）代人式（7），我们得到式（ 11 ）。

定理3：射电源的预期搜索时间具有以下上限，其中Vavg 为机器人平均移动速度，将在下文详细定义。

备注1：定理2给出的一个重要结果是，对射电源数量并不敏感，意味着其具有极佳的可扩展能力。

( 3）算法：我们在算法1中总结了我们的 DPRWA算法。该算法以一对机器人为单位运行，在此忽略组内协调的细节。

同步：算法自规划期k的开始时间 tk 开始运行。算法依赖于 时刻的 D-SPOG ，其为所有机器人的同步可信度函数。因此，所有机器人都有相同的 TSP 路线，从而确保在计划相同、 GPS 时钟准确以及时间环和欧几里得空间具有相同映射规则的条件下，实现机器人移动的同步。

虚拟山脊：我们尚未解释的一点，是算法1和2行提到的虚拟山脊。定义为最大山脊数。如果 D-SPOG没有产生足够的山脊，我们将使用虚拟山脊，以确保存在山脊。虚拟山脊在搜索区域内统一随机生成，在每个规划期予以更新。引人虚拟山脊可以简单地视为一种让搜索区域覆盖低概率区域的采样方法。虚拟山脊的同步方式和 D-SPOG 相同。

传感器稀疏的区域：算法1的DPWRA 要求所有机器人共享一条 TSP 路线。这种做法在射电源相对密集（即水平面上不连续成分的距离小于通信距离）时是有效的。但是，如果搜索区域内的射电源分布稀疏，那么共享 TSP 路线就可能是效率低下的，因为机器人必须浪费大量时间用于在射电掘之间进行非山脊移动。

由于机器人的功率更高，天线比射电源更好，所以通信距离远大于传感距离，因此距离较远的机器人组具有独立的 D-SPOG 传感过程，从而使我们可以将 D-SPOG部分分为空间上不相交的远程组。每个组视为一个单独的问题，在分离期间不要求其合并 D-SPOG。如果组间距离发生变化，我们可以不定期重新分组。在重新分组时，我们可以合并各组的 D-SPOG。各对机器人将根据各组的总，按比例分配到不同的小组。如果机器人对的数量不足，我们可能还必须合并一些临近的小组。我们为每个小组应用算法1。

6 实验

为验证算法，我们运行了算法和一套模拟平台。驱动模拟的硬件基于真实的机器人和在实际实验中测量得到的射电源参数（图 3(a））。射电源为 DigiInterτiational Inc. 生产的 XBee Pro ，并配备了 ZigBeeT 射电频率模块。我们使用从 XBeePro 得到的 RSS 读数来驱动模拟实验（图 3(b））。我们在模拟过程中使用了 iRobot Create 机器人，其最大速度为 40 cm·s-1 。网格为正方形，具有50×50 个单元 每个网格单元的尺寸为 500×50cm2。每个射电源根据 i.i.d.泊松过程发出射电信号，其频率为 个数据包每秒 射电源还会使用 XBeePro的5种功率设置之一动态变化其发射功率，从而使传感范围在 1.67 m到3.45 m之间变化。模拟中我们设置 。我们选择概率收敛阔值为在每次实验中，我们随机生成网格内的射电源位置。

图3. 用于驱动模拟的硬件。

我们将 DPRWA 算法与两种启发式算法进行了对比，包括成对随机移动和成对巡逻算法。在两种启发式算法中，机器人和 DPRWA 样两两分组。在前一种算法中，每一对机器人被视为一台超级机器人，共同执行随机移动。在后者中，机器人对组成线性队形，保持相同的组间距离，即最大通信距离。由于保持了整体联通性，所以等于集中规划。

图4以内存使用率和搜索时间为指标，显示了在变动通信距离、机器人数量和射电源数量时的模拟结果。每个数据点是20次独立实验的平均值。在图4(a）和图4(b)中，需要搜索6个射电源。在图4(a)和图4(c)中，使用了8个机器人 在图4( b）和图4(c)中，通 距离设置为6m。

图4. 比较 DPRWA、成对随机移动和成对固定路线巡逻算法的实验结果。（a）以机器人储存的检测事件数量计算的最大内存空间使用率；对比3种方法在(b)变动机器人数量或(c)射电源数量时的搜索时间变化。

由于成对巡逻算法保持了整体连通性，所以其为同步所需的内存容量最小。成对随机移动算法则与之相反，因为机器人两次检查站之间的时间可能非常长。我们的 DPWRA 算法需要的内存比巡逻算法要多，但仍然远低于随机移动（图4(a)。在搜索时间方面， DPRWA 算法显著快于其对比算法（图 4(b ）和图4( c)）。在机器人数量有限的情况下，这一优势更加明显，而这种情况在资源受限的情况下很可能发生图4(b)还对 DPRWA 与文献［19, 20］中的PRWA ( CPRWA ）进行了比较。令人惊讶的是，尽管 CPRWA 具有协调和同步方面的优势，但 DPRWA 的预期搜索时间（ EST ）与 CPRWA 基本相同。图4(c ）还进一步确认了定理3，即DPRWA 的预期搜索时间对信号源的数量不敏感。

7 结论

我们开发了一种分散化算法，以协调一组移动机器人在移动能力、通信范围及传感范围有限的情况下，在开阔地区搜索未知瞬时射电源。我们提出了一种分两步的方法：首先，我们使用基于检查站的同步功能，对机器人用于追踪信号源位置的可信度函数进行了分散化；其次，我们提出了一种用于协调机器人的分散化规划策略，以确保存在检查站和进行协同搜索。我们分析了J:述算法的内存使用情况、通信数据量和搜索时间。我们实现了该算法，并使用基于真实传感器的数据，对该算法和两种启发性算法进行了模拟比较。

致谢

笔者感谢M. Hielsberg、J. Lee C. Chou,,H. Cheng、X.Wang M. Treat R. Liu和B. Chen 为本研究提出的意见，以及他们为德州 A&M 大学联网机器人实验室所做的贡献。

Compliance with ethics guidelines

ChangYoung Kim, Dezhen Song, Jingang Yi, and Xinyu Wu declare that they have no conflict of interest or financial conflicts to disclose.

参考文献

原文顺序 | 出版日期 | 本文引用

基金资助

This work was supported in part by the National Science Foundation (IIS1318638 and IIS1426752), and by the Shenzhen Science and Technology Project (ZDS Y20120617113312191).()

AI Summary AI Mindmap
PDF (8290KB)

4958

访问

0

被引

详细
导航
相关文章

AI思维导图

/

〈 〉