MENU

hector_navigation 论文翻译:Exploration Transform: A stable exploring algorithm for robots in rescue environments

2020 年 07 月 24 日 • 默认分类

探索变换:用于救援环境中的机器人的稳定探查算法

ROS Wiki GitHub

摘要

救援环境中的自主机器人必须同时完成多项任务:它们必须进行自我定位,绘制地图,检测受害者并决定下一步探索的具体目标方向。在本文中,我们提出了一种为探索任务提供可靠解决方案的方法:基于机器人已经获取的环境信息,该算法计算出通往下一个有趣“边界”的路径。我们的方法全面考虑了与下一个边界的距离以及此路径对于机器人行进的难度。这些困难可能是由狭窄的通道造成的,也可能是由传感器无法检测到任何标志的宽阔的开放空间造成的。对于本地探索任务,该算法由占用栅格提供。而对于搜索任务,它还可以处理编码其他信息的地图,例如尚未被其他传感器搜索到的地方。 探索变换已成功在我们的移动系统 Robbie 上实现,并在 2007 年德国机器人世界杯和 2007 年机器人世界杯世界冠军赛中使用。基于这种方法,我们的“ resko”团队在如上的两个比赛中获得了救援机器人联盟中的“最佳自主奖”。

关键词

Robotic, RoboCup Rescue, autonomous navigation, path planning, exploration, USAR

Ⅰ. 介绍

机器人需要了解其所处环境的结构才能完成复杂的任务7。 无论如何,在地震造成的救援情况下,先验知识是无法获得的:即使我们可以拿到倒塌建筑物的平面图,但由于家具和墙壁可能由于撞击而移动等原因,这也是无用的。 因此,机器人必须在定位的同时构建自己的地图。 这个问题被广泛称为 SLAM 问题(Simultaneous Localization and Mapping)3, 5。 除此之外,自主机器人还必须决定下一步要去哪里,以了解有关环境的更多信息2。 这个问题可以分为两个问题:

  1. 选择一个目标:机器人下一步应该去哪里扩展地图或寻找受害者?
  2. 确认一条路径:机器人应采取哪种方式达到此目标?

我们在本文中介绍的方法使用占用栅格1,移动系统 Robbie 在未知环境中行驶时会自动构建。占用栅格中的每一个单元都存储着其被占用的概率。为了生成此地图,该算法使用机器人的里程计数据和 Hokuyo URG- 04LX 激光测距仪的传感器读数。地图构建过程使用粒子滤波器将当前扫描匹配到占用栅格上。这种方法已在 2006 年世界杯机器人大赛上成功进行了测试,但依赖于被远程控制的机器人。为了使系统具有完全自主性,实施了以下各节中描述的探索行为。本文的组织如下:在第二节中,介绍了相关的工作。解释了探索和路径规划的不同方法。在第三节中,探索转换是第二节中讨论的解决方案的组合。它的扩展是为了鼓励机器人在可看见障碍边界的地方行走,因此传感器始终可以检测到一些地标。这种行为被称为“沿海岸航行”6。完整的算法在我们的救援机器人 Robbie 上实现。第四节介绍了我们在不同测试区域进行的实验结果,包括 2007 年德国世界杯机器人赛和 2007 年世界杯冠军赛的救援场馆。

Ⅱ. 相关工作

A. 探索

在[8],Brian Yamauchi 提出了一种基于边界的来确定潜在目标的方法。 占用栅格(Occupancy grids)用作算法的输入。 关键思想如下:为了获取新信息,机器人将前往将前往已知与未知区域之间的边界(而不是障碍物的边界)。 这样的边界在占用栅格中是一个被标为空闲(free)的单元格,而其相邻的单元格被标记为未知(unknown)。 如果相邻边界单元格的连续片段足够大以使机器人可以通过,则将其视为潜在目标。 如果在占用栅格中检测到多个潜在目标,则选择距离最近的目标。 Fig. 1 给出了平面图和提取出来的边界的示例。

图 1

Fig. 1 度量标准地图(存储为占用栅格)和对应的的提取边界。 边界形成的线与未知区域分开。

Gonzalez-Banos and Latombe 提出了另一种选择潜在目标的方法:在 [2] 中,他们提出了一种算法,该算法可以找到地图中的最佳点,传感器可以以此来扩展地图( 最佳视图问题”)。 为了找到该点,围绕着边界周围,确定了候选目标点。 对于每个候选点,计算从此点可测定区域的大小,并选择可测定区域最大的点作为最佳点。

B. 距离变换

为了找到从任意起点到固定目标的方法,Javis 和 Byrne 4提出了距离变换。 占用栅格中的距离变换是每个空闲单元格到达目标单元格的代价。 两个之间无障碍的单元格 $c_i$ 和 $c_j$ 之间的距离可以是街区距离,棋盘距离或欧几里得距离。 在对占用栅格的每个单元格应用了距离变换之后,可以通过简单地遵循最大梯度来提取从任何单元格到目标单元格的最短路径。Fig. 2(a) 展示了利用棋盘距离的距离变换。

图 2

C. 障碍变换与路径变换

距离变换始终选择两个单位元之间的最短方式。 这种方式并不总是适用于机器人,因为它经常会碰到墙壁并经过狭窄的通道。 Alexander Zelinsky 的路径变换([9],[10])为距离变换增加了安全性:障碍物变换 $Ω$ 指每个单元格到最近障碍物的距离。 图2(b)显示了简单平面图的障碍物变换。

从单元格 $c$ 到目标单元格 $c_g$ 的路径变换 $Φ$ 如下:

$$ Φ(c,c_g) = min_{C\in \chi^{c_g}_c}(l(C) + \alpha\sum_{c_i\in C}c_{danger}(c_i))\qquad(1) $$

其中,$\chi^{c_g}_c$ 是指从单元格 $c$ 到目标单元格 $c_g$ 的所有可选路径,$l(C)$ 是路径 $C$ 的长度,$c_{danger}(c_i)$ 是进入单元格 $c_i$ 的不适代价计算式,而 $α$ 为一非负权值数。

$l(C)$ 可按如下公式轻易算出来:

$$ l(C)=l(c_0,...,c_n)=\sum^{n-1}_{i=0}d(c_i,c_{i+1})\qquad(2) $$

其中的 $d$ 指两单元格之间的距离(例如棋盘距离等)。

$c_{danger}$ 基于障碍变换。 如果此单元格到墙壁的距离小于机器人尺寸的一半,则其代价会非常高。

Zelinsky 对这种成本函数的选择(参见[11])如下所示。

$$ c_{danger}(c_i)=\begin{cases} (X-\Omega(c_i)^3),&if\quad\Omega(c_i)\leq X \\ 0,&else \end{cases}\qquad(3) $$

常数 $X$ 确定到障碍物的最小距离,并取决于机器人的大小以及传感器和地图的准确性。 (1)中的权重 $α$ 确定路径与障碍物相距多远。

同样,要从任何空闲单元格进入目标单元格,只需遵循最陡峭的梯度即可。

Ⅲ. 探索变换

通过将 Yamauchi 的基于边界的探索与 Zelinsky 的路径变换相结合,可以很好地解决探索问题:路径变换的扩展方式是计算到最近的边界的路径代价,而不是计算到达特定已经计算出来的单元格。路径不一定是最短的,也不一定紧紧靠近边界,因为成本是由路径的距离和安全性决定的。 探索变换的整体公式在(4)中给出。

$$ \Psi(c)=min_{c_g\in F}(min_{C\in \chi^{c_g}_c}(l(C) + \alpha\sum_{c_i\in C}c_{danger}(c_i)))\qquad(4) $$

其中,$F$ 是所有边界点的集合,$\chi^{c_g}_{c}$ 是指从单元格 $c$ 到目标单元格 $c_g$ 的所有可选路径,$l(C)$ 是路径 $C$ 的长度,$c_{danger}(c_i)$ 是进入单元格 $c_i$ 的不适代价计算式,而 $α$ 为一非负权值数。

探索变换具有有利的特性,即通过构造不会出现局部最小值。因此,可以直接从每个单元格提取其到最近边界的路径。

与路径变换相比,探索变换对所有可能的边界单元执行搜索。在集合 $F$ 仅包含一个元素 $c$ 的情况下,探索变换与到目标单元格 $c$ 的路径变换相同。

占用栅格中每个空闲单元格的(4)计算是通过专门的洪水填充算法完成的。首先,选择所有边界单元作为种子,并将所有相邻单元格添加到即将计算“探索变换”值的单元队列中。然后,将一个单元格的“探索变换”值设定为 其八个相邻单元的最小值+从该相邻单元到当前单元的移动代价+当前单元的不适代价。每当一个单元的“探索变换”值改变时,其相邻单元格可能也会改变其值,因此它们会被添加到计算队列的末尾。当队列中的元素用完时,探索转换会收敛到其最终状态。这样,占用栅格的每个空闲单元至少被计算一次。不过,实验表明,探索变换的计算时间不能看作是一个缺点,对于500×500像素的占用图,在标准奔腾1.3 GHz处理器上的计算时间不到500毫秒。图3显示了一个占用栅格和两个相应的探索变换。

图 3

图3(b)和3(c)中靠近边界的区域较暗,这表明到边界的距离很短。远离任何边界的区域均标有灯光,表示代价较高。探索变换的加权因子α确定了一条较安全的路径比一条较短的路径更可取的路径。图3(b)和3(c)显示了针对不同α设置的不同路径。

A. 沿着障碍边界行走

公式3迫使机器人远离障碍物,无论机器人离障碍物有多远。 这具有传感器(有限范围内)看不到任何标志的风险。 应该避免这种情况,因为机器人需要界标来定位自身和扩展地图。 因此,成本函数以以下方式扩展:(a)鼓励机器人在 $d_{opt}$ 的距离处远离障碍物,并且(b)永远不会比 $d_{min}$ 更近。 到下一个障碍物的距离为 $d$ 的节点的 $c_{danger}$ 计算如下:

$$ c_{danger}(c)=\begin{cases} \infty,&ifd<d_{min} \\ (d_{opt}-d)^2,&else. \end{cases}\qquad(5) $$

图4(a)和图4(b)示出了具有不同参数的样本图的不适成本。

图 4

B. 将栅格地图与其他传感器数据合并

如目前为止所描述的,“探索变换”仅在占用栅格上起作用。 如果机器人的任务仅仅是探索和绘制环境图,这就足够了。 但是,如果机器人必须同时执行其他任务,则必须改进探索策略。 在我们的情况下,机器人在探索时会使用视野为180°,范围仅为2米(激光测距仪的范围为4米)的热传感器搜索受害者。 为了跟踪热传感器已扫描的区域以及由激光扫描仪映射的区域,第二个占用栅格称为导航占用栅格,计算如下:

$$ navGrid(c_i)=\begin{cases} free,&if\ occGrid(c_i)=free\ \land \\ &ScannedbyThermalSensor(c_i) \\ unknown,&else. \end{cases}\qquad(6) $$

使用用于探索变换的导航占用栅格而不是占用栅格,可以计算出尚未通过热传感器扫描的区域的路径,并且机器人可以通过遵循这些路径来系统地扫描整个环境。

C. 路径优化

路径规划的结果是占用栅格中相邻单元的列表。 无论如何,只需要这些单元的一个子集来描述从起点到边界的安全方法:在有附近障碍物的区域中,选择的点要多于没有障碍物的区域。 障碍物变换的结果用于确定路径的两个航点之间的所需距离。 图5显示的路径由原始212个像元和缩小的路径组成,仅包含10个航路点。

图 5

Ⅳ. 实验

我们在移动系统Robbie上测试了该方法,该系统可以使用4米范围的激光测距仪在线生成地图。 不断增长的地图被用作“探索变换”的输入。 最终地图(探索之后)如图6所示。在6(a)中,机器人首先跟随右侧的大(因此是安全的)边界,并避免进入下端的门。 它与墙壁保持约0.8 m的距离,这被设置为到障碍物的最佳距离。 其他地图还显示,机器人更喜欢较大的通道。 总体而言,该机器人提出了一个爱管闲事但安全的行为。 该算法依赖于正确的环境图(可能不完整)。 无论如何,如果在损坏的地图上计划了路径,则机器人会停在障碍物的前面,并更新地图。 更新过程完成后,机器人会重新计算路径并继续行驶。

图 6


REFERENCES

REFERENCES

[1] A. Elfes.Using occupancy grids for mobile robot perception andnavigation. Computer, 22(6):46–57, 6 1989.
[2] H´ector H. Gonz´ales-Ba˜nos and Jean-Claude Latombe.Navigationstrategies for exploring indoor environments. The International Journalof Robotics Research, 2002.
[3] J. Gutmann and K. Konolige.Incremental mapping of large cyclicenvironments. In Proceedingsof the IEEE International Symposium onComputational Intelligence in Robotics and Automation (CIRA), pages318–325, Monterey, California, 1999.
[4] R. A. Jarvis and J. C. Byrne. Robot navigation: Touching, seeing anknowing. In Proc. Australian Conf. on Artificial Intelligence, Melbourne,Australia, 1986.
[5] J. M. M. Montiel, Jose A. Castellanos, J. Neira, and J.D. Tard´os. Thespmap: A probabilistic framework for simultaneous localization and mapbuilding. IEEE Transactions on Robotics and Automation, 15(5):948–952, 1999.
[6] Nicholas Roy, Wolfram Burgard, Dieter Fox, and Sebastian Thrun.Coastal navigation: Mobile robot navigation with uncertainty in dynamicenvironments. In ICRA, pages 35–40, 1999.
[7] Sebastian Thrun. Learning metric-topological maps for indoor mobilerobot navigation. Artificial Intelligence, 99(1):21–71, 1998.
[8] B. Yamauchi. A frontier-based approach for autonomous exploration.1997 IEEE International Symposium on Computational Intelligence inRobotics and Automation, page 146 ff., 1997.
[9] Alexander Zelinsky.Robot navigation with learning.AustralianComputer Journal, 20(2):85–93, 5 1988.
[10] Alexander Zelinsky.Environment Exploration and Path PlanningAlgorithms for a Mobile Robot using Sonar. PhD thesis, WollongongUniversity, Australia, 1991.
[11] Alexander Zelinsky.Using path transforms to guide the search forfindpath in 2D. I. J. Robotic Res, 13(4):315–325, 1994.

返回文章列表 文章二维码
本页链接的二维码
打赏二维码