多源机器人搜索：分散式协调算法与规划策略

058工程第1卷·第1期·2015年3www.engineering.org.cn研究机器人-文章工程2015，1（1）：58-多个未知瞬变射电源的分布式机器人搜索Chang-Young Kim1，Dezhen Song2*，Jingang Yi3，Xinyu Wu4摘要本文提出了一种分散式的机器人搜索协调算法未知和短暂的无线电源。除了有限的移动性和通信和传感范围外，机器人团队还必须应对来自信号源匿名、短传输持续时间和可变传输功率的挑战。我们提出了一个两步的方法：首先，我们分散的信念功能，机器人使用基于检查点的同步跟踪源位置，第二，我们提出了一个分散的规划策略协调机器人以确保检查点的存在。分析了算法的内存占用、通信数据量和搜索时间。我们已经实现了所提出的算法，并将其与两种算法进行了比较。实验结果表明，我们的算法成功地交换了适量的内存这是三种方法中搜索时间最快的。关键词无线定位，网络机器人，瞬时目标1 介绍无线传感器网络技术的快速发展为信息采集提供了良好的工具。然而，无线传感器网络也可能是对我们的安全和隐私的重大威胁（例如，敌人可能会部署一个传感器场以检测部队移动）。在一个大的领域中的大量微型传感器使得难以手动搜索和压制传感器。我们正在开发算法，使一组移动机器人能够执行任务。在这种“机器人网络”与“传感器网络”的设置中，每一方都有自己的优势和局限性。机器人有机动性，而传感器没有。机器人知道自己的位置和接收信号强度（RSS）读数。然而，机器人不能解码传感器网络的协议，将传感器视为普通的无线电源。因此，信号ano-除了通信和感测范围的限制之外，多个、短的传输持续时间、可变的传输功率和未知的源数量挑战机器人。在我们先前工作的基础上，我们提出了一个两步的方法：首先，我们分散的信念功能，机器人使用基于检查点的同步跟踪源位置;第二，我们提出了一个分散的规划策略，以协调机器人，以确保检查点的存在。我们正式表明，我们的规划算法，确保分散的信念功能定期同步明确的分析内存和通信的要求。此外，我们的算法的预期搜索时间是不敏感的射电源的数量。我们已经实现了所提出的算法，并将其与两个基于真实感测数据的模拟算法进行了比较。实验结果表明，我们的算法是最快的搜索时间在这三种方法中，不可避免地交换了适量的内存。2 相关工作搜索多个瞬态无线电源涉及基于射频（RF）的定位和多机器人运动估计和规划。基于RF的定位的最新发展可以被视为“友好”无线电源的定位，因为研究人员要么假设单个无线电源连续发送无线电信号（类似于灯塔）[1，2]，要么假设机器人/接收器是网络的一部分并了解详细的数据包信息[3，4]。然而，这样的信息对于未知网络并不总是可用的。当信号源不合作时，RSS读数是定位的主要信息，因为RSS随距离衰减。当信号源处的信号传输功率不可用时，来自错位听众[5，6]或天线阵列[7]的RSS读数之间的1Kespry，Inc.，美国加州门洛帕克94025;2美国德克萨斯州农工大学计算机工程系，学院站，TX 77843;3美国罗格斯大学机械工程系，新泽西州皮斯卡塔韦08854;4中国科学院深圳先进技术研究院，深圳518055* 通讯作者。电子邮件地址：dzsong@cse.tamu.edu接收日期：2015年3月9日;接收日期：2015年3月20日;接受日期：2015年3月25日作者（S）2015出版社：Engineering Sciences Press这是CC BY许可下的开放获取文章（http：//creativecommons.org/licenses/by/4.0/）www.engineering.org.cn第1卷·第1期·2015年3月工程059机器人-文章研究我我我Z已经证明在获得方位和/或距离读数方面是有效的。在多机器人研究领域，机器人位姿的分散估计最近得到了相当大的关注。Durrant-Whyte [8]开发了基于分布式卡尔曼滤波器框架的分散估计技术。Leung等人。[9]还通过检查点的概念解决了分散式多机器人定位问题，检查点表示机器人之间交换观测后观测的延迟同步。研究人员将这一概念扩展到基于通信约束的分散式信息传输方案[10]。我们的问题是类似的，我们可以受益于范围和航向感觉模型，但它是不同的，因为我们专注于估计的位置的瞬态目标，而不是位置的机器人本身。同样在多机器人研究中，Pereira等人[11]提出了在传感和通信约束下的分散规划，同时保持与邻居的连接。通过使用分散的多机器人，Bhadauria等人。[12]解决了多个机器人从部署的传感器网络收集信息的数据收集问题（DGP）。在这项工作中，他们制定了DGP作为旅行推销员问题（TSP）的例子，并提出了两个子旅游计划。一个巡视是逆时针巡视，另一个是顺时针巡视，以确保这两个巡视覆盖所有部署的传感器节点。分散计划的另一个方面是同步。Martinez等人。[13，14]分析了分散式多机器人的运动同步，使用同意和追求算法引入了一个本地连接的代理网络。这些关于通信和传感约束的工作启发了我们的工作。与流行的追逐-逃避游戏不同，我们问题中的无线电源不会移动。然而，固定节点并没有使问题变得更简单，因为无线电源是瞬态的，并且可以改变传输功率，这导致了不同类型的问题。我们的小组研究了不同设置和约束条件下的瞬态无线电源搜索问题[15，16]。最相关的先前工作是在参考文献中提出的贝叶斯定位方案。[17，18]用于使用单个机器人及其扩展到多个机器人[19，20]。本文建立在以前的会议版本[21]的基础上，与现有的搜索方法不同的是分散的信念函数，提出了一种新的分散规划算法。对于新的分散式方法，我们将遵循相应的集中式版本中相同的问题定义[17定义1（感测问题）：给定RSS读数和来自机器人的相应位置，更新无线电源位置的机器人置信函数。定义2（规划问题）：给定置信函数，规划机器人轨迹以提高搜索效率。 我们将在本文后面详细地具体定义置信函数。这是一种蒙特卡洛类型的算法方法，具有以下用于无线电源检测的停止时间和搜索条件：如果置信函数大于预设阈值pt，则认为找到了无线电源。现在让我们从感知问题开始。4 分散信念函数置信函数根据RSS读数和机器人位置跟踪无线电源分布。它们通常建立在贝叶斯框架和天线模型上，以允许增量更新。在我们以前关于瞬态和未知无线电源的集中定位的工作[17，19，20]中，我们提出了时空占用网格（SPOG）作为机器人的共同信念函数。让我们首先回顾一下，然后我们将分散SPOG。4.1 SPOG简介SPOG将搜索区域划分为大小相等的小网格单元.将i∈N定义为单元索引变量，其中N：= {1，.，n}是网格单元索引集，并且n是单元的总数。SPOG跟踪两种类型的概率事件：Ci表示小区i包含无线电源的事件，以及Ci1表示单元i是活动源的事件，检测到传输。Ci1实际上反映了多个源之间的相对传输速率，这是一个时间维特征。定义P（C）为事件C的概率。P（Ci）和P（Ci1）是瞬变射电源时空分布的特征。设l∈M：= {1，...，m}是机器人索引变量，其中m是机器人的总数，M是机器人索引集请注意，m始终是偶数，因为我们稍后将配对机器人。离散时间k，或相应的连续时间tk，指的是传输时的每个时刻机器人可以探测到设xlk：=[xlk，ylk]T为位置并且Xk：=[x1k，...，xk]T是所有机器人的集合m~k在时间k的位置。 设离散随机变量Zl为~k~ k3问题定义第l个机器人在时间k的RSS读数。定义Z：= [Z1，.，~kTZm]作为所有RSS读数的离散随机向量，我们的问题设置和假设是：time k and d le t z~k：=[~z k，. 这是一种基于定值的计算。A为1m(1) 机器人和无线电源位于开放的2D空间中。(2) 每个机器人具有有限的通信范围和有限的感测范围。(3) 每个机器人都使用全球定位系统（GPS）知道自己的位置。全球定位系统时钟还提供准确的时间，以实现同步。(4) 无线电源的发射功率对机器人来说是未知的，并且可能会不时变化。然而，射电源的位置并没有改变。按照惯例，我们使用随机变量或向量的较低情况来定义这些变量。 D_f_i_i_i：k：=[~i_i，.] T是从搜索开始到tk感测到的所有RSS的集合。定义P（C i|Z1：k）作为单元格i与至少有一个无线电源，给定Z1：k。同样，我们定义P（C）|Z 1：k-1），P（C1|Z 1：k）和P（C 1|Z 1：k-1）。 在时间k，事件~ k=z~k是由yrobots表示的。 P（Ci）的位置或概率|Z1：k）在网格上的值需要更新。根据参考文献[17]，这实际上是一个嵌套的多变量贝叶斯过程。随着更多研究机器人-文章060工程第1卷·第1期·2015年3www.engineering.org.cn∪KLpp lpRSS读数随时间进入系统，P（C i|Z1：k）收敛直到P（C i|Z1：k）> pt，这意味着满足第3节中的搜索条件.4.2 去中心化SPOG（D-SPOG）在分散式系统中，每个机器人都必须通过在内部积累RSS读数并在其他机器人进入其通信范围时与其他机器人交换信息来维护自己的本地SPOG。然而，在Ref.[17]这取决于严格的顺序~1：k完全观察集Z的。机器人不能随意使用它们的部分接收以生成本地SPOG。此外，由于机载存储空间有限，机器人无法永远保存其读数以供将来进行信息交换。在我们解决这个问题之前，让我们仔细看看分散的系统。在分散式系统中有三种类型的离散事件：检测事件，指的是机器人检测到传输的时刻;接收事件，描述机器人移动到另一个机器人的通信范围内的时刻回想一下，k是检测事件的时间索引变量。将j和k分别表示为会合事件和规划事件。定义tj：k来描述连续时间域中的三个事件，作为本文的惯例。 为了减少混乱，我们也可以使用一个简化的版本，如tk和tj对应的事件时间。tk表示第k个规划期开始一个有效的协调计划应该允许机器人相互交换信息，使得所有机器人在时间j，tj ≥ tk时具有相同的观测集Z1：k。这是所有机器人可以更新其SPOG直到时间k的时间。通过这种方式，集中式SPOG可以在所有机器人之间分散和同步。“延迟同步”的[9]。让我们将Y（tk，tj）表示为检查点。注意，机器人的每个检查点总是有两个时间变量：它以早期检测事件时间开始，以未来会合事件时间结束，因为信息总是由检测事件生成，并由会合事件同步图1显示了一个信息流图，用于说明检查点概念以及信息如何在D-SPOG中的分布式机器人对之间传递。请注意，机器人在此图中已配对，因为需要两个机器人来获得具有未知和可变传输功率的无线电源的信号比。 我们忽略了配对内部的交流，因为一对总是可以互相交谈其他根据规划。沿着弧形箭头，图1.四对机器人的信息流图示例。灰色矩形表示机器人会合事件。垂直方向的弧形箭头表示通信范围内机器人之间的信息交换。黑色和白色圆圈分别表示检测到和未检测到活动无线电传输的机器人的事件。由于不知道无线电传输的时间，每个机器人除了RSS读数外，还必须跟踪其轨迹。设W1kWlk-1，t = {Xl（（tk-1，t）），zl（（tk-1，t））}（1）其中xl（. ）是机器人轨迹，而zl（. ）是RSS阅读设置持续时间。类似地，我们通过分别用t j和t k替换t来定义Wlk让我们定义机器人l在会合时间tj的测量集为Γlk为了描述机器人l遇到另一个机器人之前的那一刻，我们引入了一个（。）显然，Wlk在tj，机器人l遇到机器人p，其在信息交换之前具有测量集合（tk'注意tk'这两个机器人首先比较这两个时间，因为一个新的时间意味着一个更近的D- SPOG。另一个机器人应该将其SPOG与最近的一个同步。在同步其SPOG之后，他们需要同步测量集。注意，在同步之前，对于机器人l，我们具有（Γ1k不失一般性，我们假设tkr1k其中，（rkp p p在垂直方向上，我们可以看到Y（tj，k+1，tj+2，k+3）和tk' -1和t k-1之间的测量，Y（tkj，k+2，tkj+3，k+4）是检查点。K K使用.要构建D-SPOG，剩下的问题是每个机器人如何存储和交换信息。 假设Yl（tk在tj根据检查点的性质，虚拟的集中式SPOG。机器人l只需要存储自己的位置，在会合事件之后，每个机器人需要搜索，可以建立更近的检查点。对于机器人l，它通过搜索最大值δ来检查Γlk在tk-1之后的RSS读数δ =arg maxδ [μm（Wk（记忆由于没有检测的机器人可能p= 1l lwww.engineering.org.cn第1卷·第1期·2015年3月工程061机器人-文章研究p其中（W1krlk通过建立在这种无线电源的空间分布我们-如果不满足关系，则返回0，否则返回1。只有非负解的存在才表明可以建立新的检查点Yl（tk+δ，tj），因此可以更新D-SPOG。在更新之后，很明显，D-SPOG等效于具有延迟t-tk我们有以下引理：引理1：为了保证D-SPOG在检查点的正确更新，每个机器人存储的信息量和两个机器人之间的rendez- vous事件期间的信息交换量都是O（n+ m（t-tk证明：每个机器人都必须存储一个D-SPOG，占用O（n）内存空间。在最坏的情况下，rk由于使用固定周期的轨迹存储和平均传输次数与持续时间成线性关系，因此存储在每个机器人上的信息总量为O（n+m（t-tk由于D-SPOG和它们的测量集都需要在机器人会合期间同步，引理成立。然而，如果只有一个机器人在地理上与其他机器人隔离，这导致无法与其他机器人通信，则无法建立检查点。t-tk为了解决这个问题，我们提出了一个分散的规划，保证定期检查点的存在。5 权力下放的规划分散式规划策略需要考虑检查点的存在性、通信范围限制、同步性和搜索时间。我们建立了新的规划策略，分散我们现有的岭行走算法（RWA）在参考文献。[17，18]。5.1 RWA和成对RWA（PRWA）的简要回顾在SPOG或D-SPOG中，P（C i|Z1：k）是小区i包含无线电源的条件概率。RWA计划一条路径用一个平行于地平面的平面与类山分布P（C i）相交，得到一个水平集L（p），p ∈（0，1|Z1：k）在高度p处。交集生成L（p），其中包含所有具有P（C i）的像元|Z1：k）在平面上方。L（p）通常由几个不连通分量组成。图2（a）中的不规则轮廓是L（0.1）的一个例子。对于每个分量，我们将其脊定义为沿其主导方向的最长线段[18]。我们知道每个脊都有一个非常高的概率接近潜在的信号源。我们生成一个旅行销售员问题（TSP）旅游，其中包含所有的山脊。对于非山脊段，机器人以最快的速度移动。图2（a）中的红色实线和蓝色虚线分别代表脊上和脊外运动。对于脊上段，机器人花费的时间与后验条件概率P（Ci）的总和成比例|Z1：k）在每个脊上的相应孤立水平集上。这使得机器人大部分时间都花在山脊上，然后直觉产生参考文献中的RWA[18]. RWA在搜索多个信号源方面表现出优越的收敛性能和可扩展性。图2.使用4对机器人进行分散规划的示例结果。（a）DPRWA的机器人轨迹样本，红色实线和蓝色虚线分别代表山脊上和山脊外的运动;（b）时间环上的环内运动示例;（c）与环内运动相对应的机器人对方向的变化PRWA扩展了RWA，为一组机器人规划轨迹，以处理Refs中未知和不断变化的传输功率。[19，20]。首先，PRWA扩展SPOG通过开发一个成对的传感模型的基础上，从机器人对的RSS比率，而不是假设已知的绝对源传输功率。其次，PRWA通过最小化信息熵来协调成对机器人，使得机器人对可以在规划中被视为超级机器人。我们将继承成对感知模型，并在这个分散版本中成对协调机器人。5.2 分散的PRWA（DPRWA）类似于RWA，DPRWA协调机器人对巡逻TSP旅游，链接所有的山脊。我们在每个规划期内生成TSP巡回赛。事实上，每个规划周期分为两个部分：短环间运动之间的过渡TSP旅游在相邻的规划周期，其次是长环内运动的时间分配给机器人巡逻TSP旅游。(1) 环内和环间运动：让我们从环间运动开始∪研究机器人-文章062工程第1卷·第1期·2015年3www.engineering.org.cnKKK12τ0τ001如果2是偶数，τ0我的部分。在规划期开始之前，每个机器人对计算TSP巡回。所有机器人对实际上共享来自同步D-SPOG的相同TSP行程。环间移动允许机器人从当前TSP巡回移动到下一个巡回。每个机器人都有一个预先分配的开始位置上的TSP巡回赛（详细后环内运动的初始位置）。因此，一旦建立了规划期的TSP旅游，就可以预测环间移动的旅行时间量。定义Du，k为第u个机器人对的环间行进时间。为了同步所有机器人对的环内运动的开始时间，每个机器人对等待，直到所有其他机器人对到达它们的初始位置。定义Dkmax为最大行程时间：Dkmax= argmaxuDu，k。对于那些由于短的行进距离而提前到达的机器人，它们需要在同步的环内运动开始之前等待wuk=Dkmax-同步将在第5.2（3）节中详述。为了节省时间，机器人以最快的速度移动，以缩短环间移动时间。现在让我们介绍一下拳击圈内的运动。由于TSP行程是一个连续的循环，因此它可以在时间上映射到一个圆环，其周长是单对机器人遍历整个TSP行程的时间，定义为τ0。如果我们固定映射中的点对应，则映射是一对一的。例如，TSP之旅中最左边的点（按字典顺序最小）对应于时间环上的9点钟位置，如图2（a）和2（b）中的绿色星星。所有机器人共享此映射规则，以同步它们在时间环上的位置。引入时间环可以方便我们的计划。在时间环下，环间运动也可以简化，如图2（d）所示如图2（b）所示，每对机器人均匀分布在时间环上。定义u，k和'u，k分别为第u对机器人在时间环上的位置和速度。根据时间环的定义，机器人在时间环上的速度是统一的。奇数和偶数对最初被分配为在时间环上逆时针和顺时针移动，分别表示为1和回想一下，有m个机器人，因此有m/2对机器人。我们有证明：从其初始位置开始，机器人对u遇到其两个邻居u最远的点是一个半圆，τ0/2。这两个会合带来了来自下游（来自下半圆的u+ 1）和上游（来自上半圆的u想象一下，信息是从上游和下游方向上最远的机器人对发出的。当信息到达机器人对u时，它包含来自所有机器人对的信息。有两种情况：偶数和奇数机器人对。对于偶数情况，由于单位速度，τ0/2是机器人对u收集信息的确切时间。当量(3)有一个非负解，并建立一个新的检查点。对于奇数情况，证明是类似的，除了需要有一个额外的半周期来满足额外的对。图1示出了在图2（b）和2（c）中的四机器人对的情况下在环内振荡运动下存在的信息流和检查点。(2) 内存使用和期望的搜索时间：DPRWA确保周期性检查点存在，这导致了有保证的性能。为了衡量算法的性能，我们采用了两个指标：每个机器人的内存使用量和每个无线电源的预期搜索时间。对于内存使用，遵循引理2，我们有定理1：DPRWA保证D-SPOG具有时间如果比较D-SPOG和集中式SPOG，则延迟小于Dmax+T。 为了实现这一点，每个机器人需要O（n+m（Dmax+T））的内存空间。无线电源的预期搜索时间必须依赖于源传输速率。假设无线电源i根据泊松过程以λi的速率发送信号。在参考文献[16]中，我们引入了单机器人单目标情况下的期望搜索时间（EST）。让我们把这个分析扩展到DPRWA。将TS表示为搜索时间。类似于文献[18]中RWA的EST分析，我们将收敛条件从概率阈值pt收紧到信号饱和条件。如果机器人对听到无线电源i内的传输，则认为找到了无线电源i2τ（1）=和如果u是奇数，（四）无线电源的距离dada被设置为小，使得如果听到了传输，则概率阈值pt必须u，kmu，k1否则被达到。这定义了一个感应圆，其中心位于作为机器人对的初始位置和速度。图2（b）示出了四个机器人对的初始位置和方向（由每个机器人的前进方向表示）。当射电源i和半径da。将τIN和τOUT分别定义为在射电源i的距离da之内和之外行进的时间的分数。因此两对机器人在时间环上会合，交换信息，然后反向移动。在那里-Dmax+T=τIN+τOUT（六）因此，如图2（c）所示，每个机器人对在以其初始位置为中心的时间环上振荡。将T定义为环内运动的时间。机器人我们有以下定理：定理2：无线电源i的期望搜索时间E（Ts）具有以下上界：对必须执行足够长的环内移动以确保检查点的存在。引理2：如果每个机器人对具有至少一个检查点，则每个机器人对具有至少一个检查点。E（Ts）≤Dkmax+（1）A+（e1环内运动时间T为{τ0m证明：由文献[16]中的定理1可知，瞬变射电源i的期望搜索时间E（Ts）为（五）E（T）=E（D）+1+E（τe–）（七）2+m，否则sλiOUT1- e我在T=）www.engineering.org.cn第1卷·第1期·2015年3月工程063机器人-文章研究3uu，-其中D是从搜索开始到机器人在距离da内的时刻的时间量，算法1：DPRWA输入：t时的D-SPOG第一次发射无线电信号该定理建立在一般情况下，搜索过程可以建模，作为延迟的替代更新奖励过程[22]。在我们的例子中，更新期从机器人团队在每个规划期第一次进入感知圈时开始。它与规划期不完全相同，但与规划期的预期期间长度相同。由于搜索开始于第一规划周期中的环间运动，因此让我们将概率事件B定义为事件K1 应用水平集2 计算脊并将它们与预生成的虚拟脊合并O（smax）3 从合并的脊集// Inter Ring Movements4计算Du，k和Dkmax5 移动到初始位置6 等等wk//当t≤tk+Dkmax+T时，环内移动78沿着TSP之旅9如果j，k=j，k或者是j，k= j，k，那么O（n）O（（smaxO（1）O（1）O（Dkmax）O（T）O（1）u，ku-1，ku，ku+1，k如果机器人队在环间10'j，k=O（1）u，k u，k动作因此，我们认为，E（D）= E（D|B）P（B）+E（D）|B）（1- P（B））（8）事件B是一个小概率事件，因为搜索量很大111213端部端最新情况O（1）ing字段大小。因此P（B）1由于第一个进入感应圈的点可以在时间环上的任何地方，因此它均匀地分布在时间环上。此外，我们有m/2对机器人均匀分布在时间环上，在每一个规划阶段都要更新。虚拟脊的引入可以简单地被视为覆盖具有低概率的区域的采样方法。虚拟脊组以与D-SPOG相同的方式同步。稀疏传感器场：算法1中的DPWRA迫使E（D）|B）=Dmax+1τ0=Dmax+τ0≥E（D）（九）所有机器人共享一个TSP之旅。这是有效的，当无线电源相对密集（即，该等距离为─k2m/2km由于搜索区域通常比感测区域τINDkmax+T大得多，我们有水平集中的未连接组件之间的距离小于通信范围）。然而，当无线电源稀疏时，共享TSP之旅可能效率不高E（τ出来）Dkmax+T（10）分布在搜索区域，因为机器人有把大量时间浪费在山脊外的运动上从等式（6）.由于每个更新周期都是独立同分布（i.i.d.）的，它允许我们应用在Ref.[16]第10段。由于Dmax+T与τIN无关，(9)（10）到Eq。（7），我们在Eq中得到结果（十一）、定理3：无线电源i的预期搜索时间E（Ts）具有以下上界，其中v_avg是机器人的平均行进速度，并且将被定义为细节稍后。无线电源之间。由于通信范围远大于感测范围，考虑到机器人具有比无线电源更大的功率和更好的天线，D-SPOG中的感测过程在远距离组之间是独立的，这允许我们在空间上将D-SPOG划分为不相交的远距离组。每个组都被视为一个单独的问题，在分区期间不需要合并D-SPOG。E（T）≤2.τ0+1+4（一）+E（e）的情况）（十一）我们可以定期重组，变化在重组的时候，我们可以合并D-sm1λiv平均值21跨组SPOG机器人配对将按比例分配-注1：定理2给出的一个重要结果是E（Ts）项对无线电源的数量不敏感，这意味着出色的可扩展性。(3)算法：我们在算法1中总结了我们的DPRWA。该算法在每个机器人对上运行，跳过了对内协调的细节。同步：算法运行在tk，即开始规划周期K。该算法依赖于在tk因此，所有机器人将具有相同的TSP巡回，这确保它们的运动在给定相同的计划、来自GPS的精确时钟以及时间环和欧几里得空间之间的相同映射规则的情况下同步。虚拟脊：我们尚未解释的一点是算法1第2行中提到的虚拟脊。将smax定义为最大脊数。如果没有足够的脊从D-SPOG生成，我们采用虚拟脊，以确保有s最大的脊。虚拟脊在搜索区域内均匀随机生成，根据总P（C i）的不同分组进行修补|Z1：k）。当机器人配对数量不足时，我们可能不得不合并一些紧密的组。对于每个组，我们应用算法1。6个实验为了验证算法的有效性，我们实现了算法和一个仿真平台。硬件驱动的仿真建立在真实机器人和测量的无线电源参数上在物理实验中（图3（a））。无线电源是由Digi International Inc.生产的带有ZigBeeT射频模块的XBee Pro。我们使用XBee Pro的RSS读数来驱动模拟实验（图3（b））。我们在过程中模拟iRobot Create，该过程具有最大40厘米的速度。s网格是一个50× 50单元格的正方形每个网格单元的大小为50×50 cm 2。每个无线电源根据i.i.d.泊松过程，速率为λ= 0.05包/秒。的研究机器人-文章064工程第1卷·第1期·2015年3www.engineering.org.cn无线电源还使用XBee Pro中的5个功率设置之一动态地改变其发射功率，这导致从1.67米到3.45米的变化的感测范围。我们在模拟中设置τ= 500 s。我们选择概率收敛阈值为pt= 0.9。在每次试验中，我们在网格中随机生成无线电源位置。图3.用于驱动模拟的硬件。我们比较了DPRWA算法，两个算法，包括成对随机游走和成对巡逻。在这两种机器人中，机器人的配对方式与DPRWA一样。在前者中，每一对都被视为一个超级机器人，一起进行随机行走。在后者中，机器人对遵循一个线性编队，具有相等的对间距离是最大的通信距离。由于保持了全球连通性，因此成为集中规划。图4示出了通过使用存储器使用和搜索时间作为度量，同时改变通信范围、机器人数量和无线电源数量的仿真结果。每个数据点是20个独立试验的平均值。在图4（a）和4（b）中有6个无线电源要搜索。在图4（a）和4（c）中，采用了8个机器人。在图4（b）和图4（c）中，通信范围被设置为6m。由于成对巡逻保持全局连接，因此它需要最少的内存用于同步目的。成对随机游走则相反，因为机器人检查点之间的时间可能很长。我们的DPWRA比巡逻需要更多的内存，但仍然比随机行走少得多（图4（a））。在搜索时间方面，DPRWA明显快于其同行（图4（b）和4（c））。当机器人的数量有限时，这种优势甚至更大，这发生在搜索受到资源限制时。图4（b）还比较了DPRWA与参考文献中的集中式PRWA（CPRWA）[19、20]。令人惊讶的是，尽管CPRWA在协调和同步方面具有优势，但DPRWA EST与CPRWA几乎图4（c）进一步证实了定理3：DPRWA的EST对射电源的数量不敏感。7结论我们开发了一个分散的算法来协调一组移动机器人搜索未知的和瞬态的无线电源在一个开放的领域下的移动性，通信范围，和传感器的限制。我们提出了一个两步的方法：首先，我们分散的信念功能，机器人使用基于检查点的同步跟踪源位置， 其次，我们提出了一种分散的规划策略来协调机器人，以确保检查点的存在和协调搜索。对算法的内存占用、通信数据量和搜索时间进行了形式化分析。我们实现了所提出的算法，并比较了它与两个基于真实传感器数据的仿真算法。确认我们要感谢M。希尔斯伯格，J.李角 Chou，H. Cheng，X. 小王，M.特里特河Liu和B. Chen对他们在这项工作中的投入和对德克萨斯A M大学网络机器人实验室的贡献表示感谢。这 项 工 作 得 到 了 国 家 科 学 基 金（IIS1318638和IIS1426752）和深圳科技计划（ZDS Y20120617113312191）的部分支持。遵守道德操守准则Chang-Young Kim、Dezhen Song、Jin-gang Yi和Xinyu Wu声明，他们没有利益冲突，图4.比较DPRWA、成对随机行走和成对固定路线巡逻的实验结果。 （a）最大内存空间使用量，使用机载存储的检测事件数量;在改变（b）机器人数量或（c）无线电源数量时搜索时间比较www.engineering.org.cn第1卷·第1期·2015年3月工程065机器人-文章研究财务冲突披露。引用1.G.毛湾菲丹湾安德森无线传感器网络定位技术。Comput.网络等，2007，51（10）：25292.E. D. Nerurkar，S. I. Roumeliotis，A.马蒂内利多机器人协作定位的分布式最大后验估计。In：ICRA'09. IEEE机器人与自动化国际会议，2009：1402-14093.D. Koutsonikolas，S. Das，Y.胡无线传感器网络中用于定位的移动地标路径规划。Comput. Commun. 等，2007，30（13）：2577-25924.T.坐下，Z。Liu，M. Jr Ang，W.是的多机器人移动性增强的自组网跳数定位。机器人奥顿系统等，2007，55（3）：244-2525.B. C. Liu，K. H.林志昌<英>香港实业家。，1930--人吴无线通信中使用固定信号强度差测量的双曲线和圆形定位算法的分析。IEEE Trans. VehicularTechnology，2006，55（2）：499-5096.Y. Sun，J. Xiao，F.卡布雷拉-莫拉机器人定位与多天线节能无线通信。IEEE/RSJ智能机器人与系统国际会议圣路易斯：IEEE，2009：3777.M.金，N. Y.冲用于移动机器人导航的方向传感RFID阅读器。IEEE Trans.Autom. Sci. Eng. 等，2009，6（1）：448.F. H.杜兰特-怀特传感器网络中的数据融合。在：IEEE视频和基于信号的监控国际会议，2006年：399.K. Y. K. Leung，T. D. Barfoot，H.刘某稀疏通信机器人网络的分散定位：一种集中等效方法。 IEEE机器人学报. 等，2010，26（1）：6210. E. D. Nerurkar，S. I.鲁梅里奥提斯异步多中心协作本地化。在：IEEE/RSJ智能机器人和系统国际会议（IROS），2010年：435211. G. A. S. Pereira，A. K. Das，V. Kumar，M. F. M.坎波斯具有传感和通信的多机器人分散运动规划约束第二届多机器人系统研讨会论文集。克卢沃学术出版社，2003：267-27812. D. Bhadauria，O.泰克达斯河谷艾斯勒用于收集数据的机器人数据骡子在稀疏的传感器区域。J. Field Robot。等，2011，28（3）：38813. S.马丁内斯角，加-地Bullo，J. Cortes，E.法佐利论同步机器人网络第一部分：模型、任务和复杂性. IEEE自动控制学报，2007，52（12）：219914. S.马丁内斯角，加-地Bullo，J. Cortes，E.法佐利同步机器人网络研究第二部分：交会和部署算法的时间复杂性. IEEE自动控制学报，2007，52（12）：221415. D.宋角，澳-地Kim，J. Yi.在有限的感知范围内搜索间歇信号源的期望时间的随机建模。在：机器人- ics：科学与系统（RSS）会议，萨拉戈萨，2010年16. D.宋角，澳-地Kim，J. Yi.在有限的感应范围内寻找间歇信号源的时间。IEEETrans. Robot. 等，2011，27（2）：313- 32317. D.宋角，澳-地Kim，J. Yi.使用具有定向天线的移动机器人对多个未知瞬态射电源进行蒙特卡罗同时定位。IEEE International Conference on Robotics andAutomation机器人与自动化国际会议神户，2009年：315418. D.宋角，澳-地Kim，J. Yi.使用移动机器人同时定位多个未知和瞬态射电源。IEEE Trans. Robot. 等，2012，28（3）：668-68019. C. Kim，D.宋，Y。Xu，J. Yi.使用具有有限感测范围的多个成对移动机器人定 位 多 个 未 知 瞬 态 射 电 源 。 IEEE International Conference on Robotics andAutomation（ICRA）上海，2011年20. C. Kim，D.宋，Y。Xu，J. Yi，X.吴利用多个配对移动机器人协同搜索多个未知瞬态射电源。IEEE Trans. Robot. ，2014，30（5）：116121. C. Kim ， D. Song ， J. Yi 。 多 个 未 知 和 瞬 态 射 电 源 的 分 散 搜 索 。 IEEEInternational Conference on Robotics and Automation（ICRA）卡尔斯鲁厄，2013年：92722. S. M. Ross. 概率模型导论第9版学术出版社，2007年