多机器人系统的三维机器人定位研究

李伯平

(江西省抚州市东乡区技工学校, 江西 抚州 331800)

机器人通常在复杂、动态环境下工作[1]，它们依据自身的传感器获取外界环境信息，执行任务。在复杂环境中常部署多个机器人协同作业[2]，共同完成任务。当多机器人协同作业时，机器人需要知晓邻近机器人的位置，这涉及到机器人定位问题。

针对机器人定位问题，研究人员进行了大量研究[2]。He等[3]针对大型传感网络，提出非测距定位算法APTI。类似地，Li和Nagpal也分别提出非测距定位算法[4-5]。但是，这些定位算法是基于一个条件：系统内需部署已知位置的机器人。这类似于传感网络的锚节点，类似地，将已知位置的机器人称为锚-机器人。

然而，如何部署锚-机器人是关键问题。在实际应用环境中，机器人是移动的，预先获取的机器人位置也是徒劳的。由于实际应用场景常是多机器人协同作业，多机器人可形成一个自组织网络，相互通信。因此，可充分利用这个特性实现定位。

此外，在实际应用环境中，机器人部署于三维空间，它的位置也是三维的。但是，多数机器人定位算法所估计的机器人位置是二维的。例如，Zarzhitsky等[6]利用分布式定位算法估计了机器人的二维位置。

为此，针对多机器人定位问题，提出简易的机器人三维定位算法(Simple Robot Three-Dimensional Localization,SRDL)算法。SRDL算法无需部署锚-机器人。最初，系统内的所有机器人的位置未知。机器人借助于内嵌的通信设备，与邻近机器人通信。并通过不断地通信，实现自主定位。仿真结果表明，提出的SRDL算法能够实现自主定位，能够估计自己的三维位置。

1 3D定位算法

多机器人场景如图1所示。假定场景内有m个机器人。每个机器人能与邻近机器人进行通信，且机器人的通信半径为R。令Xi=(xi,yi,zi)表示第i个机器人的真实位置，且1≤i≤m。

(1)

式(1)中，||Xi-Xj||表示节点i与节点j间欧式距离。

(2)

2 SRDL定位算法

SRDL定位算法先随机估计自己的位置，然后通过迭代校正位置。因此，SRDL定位算法可分为初值阶段和校正阶段[7]。在初值阶段，节点最初随机估计自己的位置，并广播自己的位置；在校正阶段，节点通过邻近节点通信，包括一跳邻居节点和二跳邻居节点，校正位置。

在初值阶段，节点先随机的估计自己位置，再向邻居节点广播Hello消息，其包含了自己的位置估计值。

在校正阶段，节点利用与一跳邻居的通信信息，并引用引力进行修正，再利用与二跳邻居的通信信息，并引用斥力进行修正。接下来，重点分析校正阶段。

2.1 校正阶段

每个迭代可细分为信息采集和位置更新两个阶段，如图2所示。在迭代开始，节点先采集一跳、二跳邻居节点信息，再依据这些信息进行位置更新。最终，通过不断的迭代，实现自主定位。

图2 不同阶段的位置估计值

2.1.1信息采集

图3 Hello消息的传递

2.1.2位置更新

在信息采集阶段，节点能够获取一跳、二跳的位置估计值[9]。因此，节点利用这些信息更新自己的位置。具体而言，节点先利用一跳邻居信息，并用“吸引力”修正位置偏远的节点；然后，节点利用二跳邻居节点信息，并借助于“排斥力”修正距离偏小的节点。

1) 吸引力

(3)

式(3)中，ωa表示吸引力增益系数。

图4 吸引力示例

(4)

(5)

(6)

2) 排斥力

节点i不仅拥有一跳邻居节点估计的位置，也拥有两跳邻居节点估计的位置[11]。因此，节点i充分利用两跳邻居节点信息，对自己位置进一步修正。

(7)

(8)

式(8)中，ωr表示“排斥力”增益系数。

如图5所示，节点h、j分别为节点i的二跳、一跳邻居节点。节点h与节点i间的距离理应满足式(7)，若估计的距离不满足，则需进行修正，用排斥力拉开距离。

图5 排斥力示例

(8)

(9)

(10)

3) 协调力

利用吸引力和排斥力能够修正节点位置，但若只利用这两力更新节点位置，难以避免局部最小问题。因此，引入协调力。以小的概率将协调力替代排斥力。具体而言，本文以0.1概率替换排斥力。

令ωf表示协调力的增益系数，并通过协调力修正位置，有：

(11)

2.1.3位置更新流程

在定位过程中，节点先获取一跳、二跳邻居节点信息，然后再分别依式(6)、式(10)和式(11)计算吸引力、排斥力和协调力。同时，产生一个0至1的随机数ξ。如果ξ小于0.9，则利用吸引力和排斥力修正位置，有：

(12)

反之，若ξ大于0.9，则利用吸引力和协调办修正位置，有：

(13)

节点就根据自己产生的随机数，依据式(12)或式(13)迭代更新自己的位置，直到满足定位精度E或达到预置的迭代次数。

2.2 定位误差E

式(12)或式(13)所更新的位置只是相对位置，并非绝对位置，这就存在相对位置误差、相对角度误差。假定图6(a)为节点的真实位置，图6(b)为节点估计的位置。此估计的位置肯定存在相对位置误差和相对角度误差。

图6 相对误差

(13)

(14)

(15)

式(15)中：

(16)

式(16)中，V所部署区域的空间体积。从式(16)可知，E值越低，定位越准确。

3 性能仿真

利用网络仿真软件NS-2.34构建仿真平台，分析SRDL算法的定位性能。在以下实验中，吸引力、排斥力和协调力的增益系数分别设置为ωa=1、ωr=1和ωf=5。认为吸引力、排斥力在修正位置的作用相同。但协调力是以起到协调力，避免局部最小问题。同时，它出现的概率低(0.1)，因此，将它的增益系数设为5。一旦使用协调力修正，就大幅度运用协调力修正。

3.1 实验一

在103m3的三维网络内随机部署27个节点(机器人)。并在仿真开始，给所有节点分配一个随机位置估计值。节点的通信半径为6.0 m。

经过755次迭代，SRDL算法估计了27个节点位置。如图7所示，蓝色小圆圈表示估计位置，红色加号表示节点位置。从图7可知，SRDL算法基本能准确地估计节点位置。

图7 27个节点的位置估计值

3.2 实验二

本次实验考查通信半径R和节点数m对定位精度E的影响。且R从1 m变化至15 m，步长为1 m。节点数m取10、30、50和100。这些节点最初随机分布于103m3的三维网络内。本次实验迭代10 000次，取平均值作为最终仿真数据。

图8显示了节点数m和通信半径R对定位精度E的影响。在R从1到15的变化期间，节点数m在10、30、50和100时定位误差E的平均值分别为0.85，0.73，0.70，0.68。这些数据表明：节点数越多，定位误差越低。原因在于：节点数越多，节点密度越高。节点获取的一跳邻居节点、两跳邻居节点的位置信息越多，越能修正节点的位置信息。

此外，观察图8不难发现，四条定位误差曲线随R从1～15的变化过程呈凹陷状。当R=7 m时，定位误差最低。这也说明，并非R越大，定位误差越小。

图8 定位误差与通信半径的关系

4 结论

针对多机器人系统的机器人自主定位问题，提出简易的三维定位算法SRDL。SRDL算法先通过内嵌的通信设备与邻近机器人通信，并获取邻近机器人的位置信息，然后，再引用修正力修正位置。通过多次迭代修正，最终实现自主定位。最后，利用仿真实验分析了通信半径和机器人密度对定位精度的影响。

本文并没有通过实验分析吸引力、排斥力和协调力的增益系数对定位精度的影响，仅从理论上推导并假定了这三个增益系数值。后期，将通过实验进一步分析，寻求最优的参数值。