移动式机器人平台实时搜索算法外文翻译资料
2022-10-30 10:10
英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
移动式机器人平台实时搜索算法
Janusz Pochmara1, Wojciech Grygiel2, Radosław Koppa2, Krzysztof Kamiński2
1Poznan University of Technology, Chair of Computer Engineering Poznan, Poland
janusz.pochmara@put.poznan.pl
2students Poznan University of Technology, wojciech.grygiel@put.poznan.pl
radoslaw.koppa@put.poznan.pl, krzysztof.kaminski@put.poznan.pl
摘要
在我们的调查中，我们主要运用在A *算法来解决寻找最优化路径问题，因为它是相当灵活并且可以在广泛的环境中使用。A*算法的主要问题是在于计算机的内存限制。使用这种方法，机器人可以自己决定如何从一端到另外一端，并且采取的是一种高效可以回避障碍物的路径。当需要在一个非常大的地图中寻找最有效路径的时候，计算机必须记住这些复杂的检查列表和开放的节点，这些复杂的检查列表和开放的节点会在电脑中占据了大部分的存储空间，这样一来，如果超出了计算机的内存上限，计算机将会无法正常工作。尽管如此，这个算法可以给出最好的结果，并且这个算法的结果是智能机器人路径运动中有价值的分析。
关键字：搜索算法、A*算法、寻找路径
第一章 绪论
现代可移动式机器人可以执行各种从简单到高度复杂运动的环境地图[1]创建工作任务。整个系统的功能极大地受制于硬件系统的安装。出于这个原因，工程师的目标是提高CPU的处理能力以及降低能源消耗，同时提高可用内存来存储程序数据。这样一来，我们就可以创建更小、更轻的结构，并且可以允许我们操作更长的时间。不足之处是，这里有一个可以单独与硬件实现通信的软件的数量限制问题。我们清楚地认识到使用正确的软件的重要性，使用正确的软件可以让我们清楚地看到一个机器人需要找到两点之间最短的路径[2]。为此，研究人员正在开发更有效率、寻找最优路径的算法。
虽然机器人运动是一项简单的任务，但是如何寻找最优路径却可以成为一个非常复杂的问题[3]。通常，一个可以被发现的维度位置是覆盖在一个二维图的路径之中。根据这个，地图可以被看作是一种每个小方块是一个顶点的XY轴图。图1 a)提出了一种典型的地图[4]，图中黑色方块代表障碍物在障碍，起点是浅灰色的方块，终点是一个深灰色的方块
图1
图1 所示基于人工智能查询算法的基本概念，a)；拓扑地图的，b)；运动开始，c)；可能的路由，d)；两个到达目标的路径，e)；从起点到目标点的最小耗费路径，f)，路径搜索成本函数(在地图上，从起点到目标点所需成本函数值)。
机器人将要移动到一个它不知道周围地形环境的目标位置。尽管关于地形的信息是不知道的[5]，但是却可以分划一个难以覆盖从A点到B点的路径成每个小方块的边，从而用来代表地形的特性。决定系数不仅能够考虑斜率，而且具有更多的功能，比如代表地面的类型[6]
机器人的主要目的是计算出一条从起点到终点的最佳路径，并且尽可能降低成本。寻找最优路径的算法有很多种，每种方法都有它的优点和缺点。在这些算法之中，有一个名叫Lee的人发明的一种算法[7]，这是一种应用于广度优先的最短路径搜索算法。然而，这种算法它是非常低效的，因为当它处理非常巨大的地图时候，它需要巨大的内存和缓存。基于Lee的算法[8]，人们做出了许多改进算法，这些算法中能做出较好的结果是流体运动算法[9]和基于运动模式的算法[10]。第一种算法是参照了流体在流经障碍物时候的运动轨迹，自动的适应周围的环境。第二种算法将多个模式组合成一个高效的决策探路形式。另一种有效的算法被称为蚁群优化算法(ACO)[11]。它起源于观察蚂蚁的寻路能力和在有限的时间里寻找最优路径来生产。
这种算法取决于从多个模拟代理(人工蚂蚁)的解决方案的质量。因此，它是一个并行算法的例子。我们可以结合一些通常由70%- 80%的最优路径[12]生成的最小生成树来改善算法的计算速度。然而，这不是唯一的群体智能算法类型。还有粒子群优化(PSO)[12,13]算法，它可以通过分配粒子的初始速度值和一定时间后执行的评估来生成空间运动解决方案。那些粒子倾向于加速性能更好的粒子集团。最后两个提到算法是的Dijkstra[14,15]算法和A*算法[16,25]。它们都可以用来表示相同的起点，但是计算的方法不同。
现在比较常用的全局路径导航算法有两类：一类是基于图论理论的算法如 Dijkstra算法、弗洛伊德算法;另外一类是基于人工智能理论的算法,，如 A*算法、遗传算法。Dijkstra、弗洛伊德这一类算法在各个方向上平均搜索，计算量非常大，效率低下，另外一类算法中遗传算法的设计比较繁琐，虽然算法本身有较高的鲁棒性，但是算法难以保证无人船对实时性的要求。A*算法与以上所述的算法相比在实时性与鲁棒性都不算最优，但两项指标都占优势。A*算法在每一步寻找最佳路径的时候都有效地利用了估价函数中的启发信息，使得算法的效率与实时性大大提高，同时A*算法也具有相当的稳定性。A*算法在应用中存在的问题是只有在掌握所有环境信息的情况下算法才可以进行规划路径。针对这一问题，首先提出了根据现在已知的环境信息使用 A*算法，再利用所带传感器获得未知环境信息，如果检测到有阻止无人船移动的障碍物就重新规划路径。因此，人们采取A*算法来进行人们的静态障碍物避碰研究
本文的总体结构如下：我们在第二章对A *算法进行简要描述；第三章解释移动机器人的系统架构；第四章讨论A*算法的实现，移动机器人的视觉界面；第五章介绍了实验结果与分析；第六章总结了全文。
第二章 研究目的
本文的主要目标是用尽可能低的成本去寻找一条从起点到终点的最优化路径。我们发现检查可以在真正的移动机器人平台上进行测试的A*算法应用程序的可能性是一件十分有趣的事情。模型的移动架构平台将会在第三章中描述。
机器人仅仅装备了简单的触摸传感器，数字指南针和CMOS摄像头，并且不了解地图的布局，这将构成一个大问题。它只能查看其周围空间和存储数据(它记下每一个它所观察到小方块的周围空间数据)。
第三章 系统结构
图2演示了一个框图的基本组件的系统，而图3显示了移动机器人平台实时搜索算法。
图2系统架构的基本概念
所有元器件都连接在一块有机玻璃上面。机器人只能利用三个HC-SR04超声波传感器来观察周围的环境，其中一个是面向前方，剩下的两个面向左边和右边。
图3 实时性搜索算法的移动式机器人
当系统启动时，机器人执行的第一个动作是通过前面以及两侧的触发脉冲超声波传感器来检测机器人与障碍物之间的距离。测量到的距离被写入为三个变量，由蓝牙设备来传输数据。如果变量通过接受信号被正确发送到电脑，电脑开始计算使用A*算法的下一步行动。
在我们的研究方案中，机器人既可以向前和向后移动，也可以左右九十度旋转。运动精度是每个电机上面的编码器提供的。在完成一个运动之后，机器人将“准备好”信号发送到电脑并等待另一个测量要求。这个过程不断地重复直到机器人到达目标地点。
第四章 A*算法的实现
A *算法是一种地图搜索算法，已经被设计用来寻找两个被称为节点的地点之间的最短路径。它是由彼得·哈特，尼尔斯·尼尔森和伯特伦·拉斐尔创建于1968年。相比于其它类似的算法，A*算法具有更快的计算速度和更高的效率。这是因为为它找到一个最优路径,计算一个较小的图的顶点数。通过使用启发式搜索函数图，它首先检查最有前途的未开发的节点。
算法分为几个步骤来实现。首先，在计算机中输入起点并添加到“开放列表”之中等待检查，它包含的字段可以创建一个路径，并且需要被验证。
寻找搜索所有可用的字段并把它们标记为可能的，毗邻的起始点(点A)，忽略那些边缘的边或其它标记为不可能的字段，然后将它们添加到开放列表中。对于每个区域而言，起始点A被看作一个“父区域”。
图4 机器人的基本路径(蓝色点代表起点，绿色点代表终点)
这个做法是非常重要的，因为它决定了沿着指定路径行走的可能性。将起点A从开始列表中删除并添加到封闭列表来检查，这样它不需要再检验。
每个点周围都有4个需要被验证的邻点，为了找到的路径(选择最好的路径)我们采用以下方程：
F=G H （1）
G -过去路径成本函数，表示从开始节点到当前节点的成本。
H -未来路径成本函数，表示当前节点到目标节点的成本预估。
为了确定机器人的移动路径，应该适当做一些修改。这些修改考虑到了机器人的基本属性以及机器人所处在的周围的环境因素，并生成了以下函数：
Total Cost=G Moving Cost Rotation Cost H （2）
Total Cost-总成本
Moving Cost-移动成本
Rotation Cost-旋转成本
在测试中我们使用四种不同的启发式函数，它们是以下四种：
- 曼哈顿距离：
- 对角线距离：
- 欧氏距离：
- 欧氏距离的平方：
刚开始的时候，车辆是位于虚拟地图的中心位置，并受到地图尺寸大小的影响。它可以向四个方向移动。实验测量所需要的时间是3s，移动一个单位需要的时间是3s，而旋转需要3s，旋转需要2s。
我们可以适当加速来弥补小车的下滑和小车在边缘上的反映。图4展示了基本的机器人从开始节点到目标节点的路径
第五章 仿真模拟
我们使用C#语言来编写一个应用程序，用来控制移动机器人。机器人与电脑之前的通信采用蓝牙设备来实现，机器人本身只能直线移动，旋转移动和发送测量数据，这些数据来自于传感器和在一台电脑上工作的主应用程序。在通信连接完成之后，应用程序从未知地图的中心位置开始工作，并且开始接受来自传感器的数据，这些数据代表了周围附近地区的基本信息。三个超声波传感器被用来检查/验证车辆附近的空间信息。每个传感器检测机器人附近区域和验证是否存在一个障碍。阈值等于维度虚拟映射字段的值被用来定义一个障碍。
首先，我们在虚拟地图上选择一个目标点。然后应用程序调用A*函数并使用周围环境信息来计算最佳路径。每当地图更新之后，A*算法使用附近路径的最新信息来计算最佳路径。
如果检测到一个障碍被清除掉，并且这个障碍物的所有信息来自A*函数，那么A*函数将会被重新调用。不断重复这样的方式直到机器人的位置是目标节点或者目标节点是一个障碍。
图5-12显示目前移动机器人平台的一些动作和基本的机器人路径映射生成器。
图5基本的机器人路径映射生成器
图6移动机器人的运动平台的步骤
图7基本的机器人路径映射生成器
图8移动机器人的运动平台的步骤
图9基本的机器人路径映射生成器
图10移动机器人的运动平台的步骤
图11基本的机器人路径映射生成器
图12移动机器人的运动平台的步骤
在这个例子中，我们的目标节点是一个障碍物，然后算法程序停止工作。在应用不同的探索方法之后。测试结果显示，四个方向的运动中，没有直角和对角线的方法是最好的探索方法图13描述了使用不同的探索方法之间的影响。
图13 1，比较式算法；2，Eukides算法；3，曼哈顿算法；4，对角线算法
我们可以清楚地注意到，在我们实验中，建议的解决方案是最好的方案
第六章 总结
这个过程似乎是一个优秀的解决方案为那些没有安装更昂贵和更准确的传感器的移动机器人的路径导航。在未来的实验中我们的目标是提高过程效率来将它作为一个潜在的解决方案。这种方法使用较小的计算能力，其主要缺点就是计算过程需要大量的时间。每个路径，即使它非常短，也需要至少几秒钟进行分析。A*算法在我们看来是最好的搜索算法，因为它是成本最低的方法来寻找从开始到结束的路径的算法。传统的实时搜索是欧拉算法，考虑到有效性以及效率问题，我们不能采用实时搜索算法。
参考文献
1] Elfes， A.；'Sonar-based real-world mapping and navi
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[138386]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
