英语原文共 17 页，剩余内容已隐藏，支付完成后下载完整资料
Appl Intell (2016) 45:305–321
DOI 10.1007/s10489-015-0754-y
搜索任务中机器人运动规划的多目标方法
Kossar Jeddisaravi1 · Reza Javanmard Alitappeh1 · Luciano C. A. Pimenta1 · Frederico G. Guimaraestilde;1
Published online: 2 March 2016
copy; Springer Science Business Media New York 2016
摘要这项工作解决了在一个环境中单个机器人覆盖和探索的问题，目的是找到机器人以前已知的特定对象。由于有限的时间是感兴趣的约束，我们无法从无数个点进行搜索。因此，我们为这样的搜索任务提出了一种多目标方法，其中我们首先搜索一组好的位置来放置机器人传感器，以便从环境中获取信息并定位所需的对象。鉴于广义Voronoi图的有趣特性，我们将沿着此路线图限制候选搜索点。我们重新定义了将这些搜索点作为多目标优化问题的问题。 NSGA-II被用作搜索引擎，而ELECTRE I被用作决策制定工具，以决定权衡替代方案。我们还解决了一个中国邮递员问题，以优化机器人遵循的路径，以访问计算的搜索点。仿真结果显示了我们的方法找到的解决方案与其他已知方法定义的解决方案之间的比较。最后，真实的机器人实验表明了我们的方法在实际场景中的适用性。
关键词移动机器人探索bull;区域覆盖bull;多目标优化
Reza Javanmard Alitappeh rezajavanmard@ufmg.br
Frederico G. Guimaraestilde; fredericoguimaraes@ufmg.br
- Universidade Federal de Minas Gerais (UFMG), Belo Horizonte 31270-901, Brazil
1介绍
环境探测是机器人不同应用中的一项重要任务，如监视，清洁，地图构建，搜索和救援操作以及覆盖范围。在本文中，我们解决了探索室内环境的问题，目的是使用配备有传感器的机器人在有限的时间内找到先前已知的物体。然而，我们假设机器人可能不够强大，无法保证在机器人移动时在给定时间内传感器能够准确地检查整个环境。给定这个假设，我们应该定义一些静止点，称为搜索点（SP），机器人可以从中仔细分析传感器读数以搜索对象。因此，我们的方法中机器人的目标是尽可能多地访问（在有限的时间内）搜索点，从而最大化找到对象的机会。通过表达“访问搜索点”，我们的意思是：保持在该点并准确地从传感器获取测量值，必要时旋转或移动传感器，以找到物体。
我们认为所需的对象放置在杂乱的环境中。因此，机器人应该穿过安全路径以避免与障碍物碰撞。在这项工作中，我们使用广义Voronoi图（GVD）作为路线图，使机器人的运动受到这种结构的约束。由于GVD最大化了与障碍物的距离，因此该路线图可用于避免碰撞。搜索点沿GVD分布，根据需要将运动约束到安全路径。沿着GVD的那些将成为搜索点的点由多目标优化问题的解决方案定义。限制于GVD的搜索点分布的另一个优点是极大地减少了优化算法要考虑的搜索空间的维度。
306 K. Jeddisaravi et al.
为了评估在这项工作中设计的目标函数，我们考虑了圆形足迹传感器模型。该模型假设在以半径为r的机器人位置为中心的圆内，可以看到该对象。事实上，我们结合使用激光测距仪和Kinect进行导航，并使用Kinect传感器进行物体识别。显然，Kinect不是具有圆形覆盖区的传感器。但是，我们将机器人和传感器运动联系起来，以便可以模拟抽象传感器模型。这意味着在每个SP处，机器人将在其位置旋转并移动Kinect，以便在物体位于定义的圆形覆盖区域内时可以找到该物体（参见图1）。
本文的其余部分安排如下：在下一节中，将讨论文献综述。在第3节中，我们简要讨论了一些重要的工具：GVD，中国邮递员问题和多目标优化。第4节介绍了提出的解决方案。第5节介绍了不同类型的模拟和真实机器人实验以及统计分析。最后，我们在第6节中得出结论。
2 最近研究
在最近的几篇论文中已经探索了使用多目标方法和元启发式来寻找机器人导航的路径。 在[1]中，作者将路径的长度和间隙定义为离散空间中的两个主要目标。 他们使用遗传算法和NSGA II（非支配排序遗传算法II）来解决优化问题，并在后来的工作中，他们考虑了路径的平滑性和能量消耗[2]。 在[3]中考虑了模拟目标（最短的无碰撞路径）来解决焊接机器人路径规划问题。 张等人。 在[4]中提出了一种基于粒子群优化的解决方案，用于存在危险源时的机器人导航。 在[5]中提出了一种新的多目标进化算法（RankMOEA），它考虑了路径的长度和安全性。 在[6]中，问题是
图1具有足迹和配备传感器的机器人
基于元胞自动机技术解决了找到无碰撞路径的问题。在[7]中通过在其路径规划器技术中使用细菌进化算法考虑了静态和动态避障。 [8]中的Rahul采用共同进化遗传程序设计，以便在多机器人路径规划问题中找到每个人的最佳路径。
与这些工作相反，在本文中，我们使用多目标建模和NSGA-II来寻找环境中的“好”点，以便在搜索任务中被移动机器人用作探索点。
实际上，在本文中，搜索和探索某个区域以找到特定对象涉及潜在的优化问题。我们的目标是最大限度地缩短搜索时间并同时最大化覆盖区域。在文献中，已经提出了许多方法来解决不同目的的勘探问题，例如最小化勘探时间和行进距离，寻找物体或搜救，[9-11]，建立地图[13-17]等。
在[9]中，作者研究了在有界区域中搜索隐藏目标的问题，假设知道先验概率密度函数。他们认为自主代理只能使用有限的本地感官信息。他们的目标是在考虑到搜索者花费的时间或燃料的限制的情况下找到最大化找到物体的可能性的路径。他们的解决方案依赖于将环境划分为有限的区域集合，在这些区域中，他们定义了离散的搜索问题。但是，通常，解决方案不是最佳的。
格雷迪等人。 [10]研究了类汽车机器人的多目标误差规划问题。作者考虑了两个目标：主要目标（从A点移动到B点）和次要目标（收集有关在执行主要目标时发现的目标T的信息）。此外，作者还考虑了对机器人运动和障碍物的不同约束。
- 机器人圆形足迹的俯视图。 （b）Kinect传感器覆盖区域的侧视图。
|
Multi-objective approach for robot motion planning in search tasks |
307 |
在[11]中，Amanaiadis等人。提出了一种适用于实时搜救应用的方法。他们解决了现实机器人探测操作的双重挑战，即在满足任务约束的同时有效处理多个时间目标的能力。在他们的方法中，他们用成本函数模拟环境约束，并使用基于认知的自适应优化算法来满足时间关键目标。
Serpen和Dou在[12]中开发了一个实时停车场动态路径规划框架。在本文中，最小化路径长度，路径规划时间和存储空间被认为是系统的性能标准。他们使用不同的搜索算法来创建自动停车系统的实时路径。
一些研究人员试图以建立未知环境地图为目标来解决勘探问题。 [13]详细介绍了不同策略之间的良好实验比较。例如，[14]中的作者提供了基于硬件的地图构建，其中使用飞行时间（TOF）相机来理解环境。一般来说，这种类型的探索的一种常见方法是迭代解决方案，其中每个时间步骤都会回答“机器人应该在哪里或下一个最佳视图（NBV）？”的问题。 [15]中的Gonzalez和Latombe试图通过结合两个主要特征来找到下一个最佳视图：安全导航和避免每个新的本地模型与当前地图之间的重叠。这种实时方法是针对未知环境而构建的，其结果可以看作是众所周知的SLAM（同时局部化和映射）问题的解决方案，这也是[17]中提到的问题。
Amigoni和Gallo [16]提出了一种用于移动机器人的多目标探索策略，该策略确定了考虑三个方面的下一个最佳观测位置（NBV）：旅行成本，信息增益和机器人定位的预先确定。最佳观察位置是通过使用距理想解的距离的概念来决定的。
另一种常见的勘探策略是由Yamauchi [18]提出的所谓的基于边界的勘探。边界被定义为开放空间和未开发空间之间边界上的区域。该探索策略指示机器人继续朝最近的未访问边界移动以扩展先前的地图。一些研究人员试图改进这种方法，如[19]和[20]。例如，Dornhege和Kleiner [19]进一步开发了这种方法来搜索未知3D空间中的物体。提出的方法检测3D空间中的边界和空隙（未探测的体积），用于计算下一个最佳视点。
大多数审查的工作可归类为基于前沿的方法。事实上，这种探索方法是探索未知环境的好策略。基于前沿的探索背后的主要思想是获得有关环境的新信息，以创建整个环境的地图。
文献中的其他工作使用拓扑图[21]或路线图，例如[22-25]，通过基于传感器的随机树（SRT）技术来探索一个区域。 SRT方法是一种随机策略，允许使用配备范围发现者的移动机器人探索未知环境。 SRT是一种数据结构，表示具有相关安全区域的探索区域的路线图。该安全区域基于传感器读数构建。
还有其他基于传感器的方法在近似细胞分解下工作，包括螺旋STC（基于生成树的覆盖范围）[26]，回溯螺旋算法（BSA）[27]，链接螺旋路径（LSP）[28]和平滑覆盖基于高分辨率网格图（HRGM）的路径规划[29]。这些工作用于未知场景中的在线覆盖，但它们也适用于已知环境。
在[26]中，Gabriely和Rimon将环境划分为单元并计算出跟随图的生成树的路径，该生成树由单元分解方案引起。该算法的缺点是它无法处理部分占用的单元。 Gonzales等。在[27]中开发了BSA，这是一种基于螺旋运动的方法，适用于网格图。当当前螺旋运动被障碍物或先前探索的区域阻挡时，机器人在新的未探测区域中开始新的螺旋运动。由于这些螺旋路径之间可能存在断开连接，因此它们应用回溯机制将当前螺旋路径连接到新螺旋路径。在[28]中，作者通过提供一种称为约束反向距离变换（CIDT）的技术来解决先前方法的缺点，以链接一组简单的空间路径。他们的方法不需要任何堆栈空间。它找到了未连接的单元最短路径来连接两个简单的spi -ral路径。他们还解决了部分覆盖的细胞，与其他技术相比，这是一种新颖性，但在这种方法中，障碍物周围的重叠覆盖量增加了。
虽然大多数引用的文章试图减少路径重叠，但[29]中的作者关注的是平滑螺旋STC算法和BSA算法给出的覆盖路径。他们还介绍了一种连接一组简单螺旋路径的新技术，并声称与CIDT相比，它可以降低计算成本。
308 K. Jeddisaravi et al.
此技术应用波前方案，并从当前机器人位置开始查找最近的未探测单元格。对于下一个探索点，同时计算到最近单元的最短路径。 [30]中提供了对机器人的覆盖范围和路径规划的良好调查。
另一类探索方法基于人工神经网络（ANN）的思想，例如：自组织图（SOM）[31]，生长细胞结构（GCS）[32]，生长神经气体（GNG）[33] ]和瞬时拓扑图（ITM）[34]。
这些算法被认为是无监督学习（没有教师学习）方法，因为它们逐渐学习输入数据而没有关于所需输出的信息。此外，它们最初用于将高维数据空间映射到较低维度的拓扑结构，同时保留输入数据的位置关系。 SOM网络包含以拓扑结构排列的一组神经元（节点）。通过接收新的输入数据，将更改此拓扑（这是网络学习的方式）。对于每个输入数据，近似神经元（基于特定度量）朝向输入数据移动。它们没有固定的形状，并且使用增长的学习机制，以便在操作（或学习阶段）期间添加和删除它们之间的节点和连接。机器人研究人员试图将这些基于增长的技术用于未知的环境映射和本地化目的。通过这种方式，在探索过程中，它会自动创建节点以表示新的，看不见的区域并删除未使用的区域。网络创建的节点可以看作机器人感知空间中的状态。
例如，在[35]中，作者将SOM和GCS结合起来，将水下环境与配备有摄像机的AUV（自主水下航行器）进行了对比。在从图像帧中提取关键点之后，拓扑图由增长的单元结构机制构成，以创建SOM的节点和边缘，其中节点指示主要关键点。当机器人探索环境时，通过捕获新帧及其关键点，系统将它们与当前训练的SOM的节点相关联。
虽然Fritzke在[33]中扩展了SOM的自适应能力，但Jockusch和Ritter在[34]中提出了Instanta-neous拓扑图（ITM），以改善SOM和GNG，因为当输入强相关时，他们的训练很困难;两种算法都假设训练刺激在统计上是不相关的。 ITM专注于机
全文共24738字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[54]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
