英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
人工智能与A*算法在路径规划中的实现
摘要
寻找最短的路径相较于简单和容易的路径往往会遭遇更多的困难与复杂性。在此，利用模糊逻辑和人工智能算法，从摄像头或任何视觉传感设备拍摄的图像中找到对象的位置和最短路径。首先拍摄所需区域的图像，然后通过适当的方式快速找到想要达到的位置。通过人工智能，可以从所有可能的途径中找到最佳的路径。最短路径并不总是取决于最短的路程，交通拥堵，大量的交通信号和糟糕的道路条件可能会造成一定的延迟。因此，将所有可能的影响因素都考虑进去，使得修改模型更适合于求解最短路径。此模型为用户提供了多条去往目的地的路径。位置跟踪系统通过各种手段找到最短路径来节省时间。早期模型以最短距离为基础给出最短路径，它不包括时间因素。而改进的模型包含影响因素使得到达目的地的时间早于先前的最短路径。在此我们利用智能算法和模糊逻辑算法跟踪对象的位置，然后找到从起点到目的地的最短路径。最短路径是从起点到目的地的最佳路径，它将利用AI来辅助提升决策能力。提议的算法包括日常生活中所面对的每一个因素。与以往的模型相比，其在更短的时间内为用户提供了更多的选择和最短的路径。
关键词：最短路径；A*算法；Dijkstra算法；模糊逻辑；人工智能（AI）
1 引言
机动车辆作为一种现代化的交通工具，具有速度快、使用方便等优点，对人们的日常出行来说非常重要。诸如外出、旅行、购物、探亲访友等活动都是通过机动车辆来完成的。随着经济和技术的发展，在过去几十年里，机动车辆的数量迅速增加。2012的戴维斯显示，在选定的国家，1990至2009年间，汽车的年平均变化率为2.3%，卡车和公共汽车的年平均变化率为3.9%，增长仍在继续。有更多的车辆可使人们更方便地旅行和进行货物运输。车辆数量的增加也给公共交通带来压力并对环境造成污染。交通堵塞几乎每天都在世界各地发生，特别是在大城市。导致交通拥堵的原因多种多样，如交通事故和恶劣天气（例如暴雨和暴雪）。在许多国家，政府和环境保护机构提倡人们使用公交和地铁等公共交通工具而不是私家车，以此来减少道路上的机动车辆数量。除此之外，不同国家有其他解决交通问题的办法，如拓宽街道，重建现有道路，建设更多新道路以及扩大城市面积。费用合理的道路停车可以大大减少交通拥堵。
图1 世界各地严重的交通拥堵
对于如何解决交通问题的研究可以得到某种措施使交通更加高效，但遵循这些措施的可能结果之一是影响机动车辆的利用率或增加使用机动车辆的成本。尽管交通拥堵给人们的日常生活带来了一些问题，阻碍了人们的出行，但对很多人来说，乘坐汽车出行仍是必要的也是重要的。在这种情况下，我们试图提供其他解决方案来解决交通问题，即通过提供最短时间的路径规划使交通更加高效省时。通过采取最短时间的路线，将加强交通管制和管理，使机动车运行更加快速高效。
1.1 最短时间路径
一般而言，最短时间路径，顾名思义，是从一个地方到另一个地方的所有可能路径中花费时间最短的路径。为了找出这样的路径，应该能够测量或计算每条路径所消耗的时间。然而实际上，出行所消耗的时间不仅取决于驾驶员选择的道路的固定长度，还取决于复杂的交通状况和可变的行驶速度，因此实际上，最短路径可能不是最短时间路径。
阻碍交通的因素是多方面的，如车辆数量、行人数量、天气状况和路况（宽度、路面状况、坡度和能见度）。行车速度也受多种因素的影响，如车辆类型、驾驶员的选择、交通状况、天气等。虽然有计算行驶车速的方法，但就像Zhao（2010）所研究的那样，实际上，在公路上测量所有车辆的速度是不可能的，因此，不单独进行测量而估计行车所花费的时间是不可能的。通过利用移动全球导航卫星系统和网络地理信息系统的优势背景知识和技术，并利用开源的数据和工具，我们研究的目的是结合网络地理信息系统和含有全球定位系统模块的手机（也必须能够连接到互联网），和开发一个如图2所设计的可以提供智能车辆导航服务的基于网络的应用程序。
图2基于移动设备的导航网络应用程序
1.2 Dijkstra算法
一个常见的基于地图的路径寻找算法的例子是Dijkstra算法。该算法从一个起始节点和一个“开启列表”的候选节点开始。在每一步中，都会检查开启列表中距离起始节点最近的节点。这个节点就被标记为“关闭”，并且如果有的节点尚未被检查到，则与其相邻的所有节点被添加到开启列表。重复此过程直到找到到达目的地的路径。由于首先检查最短距离的节点，因此第一次找到目的地时，得到的路径将是最短路径。如果存在负权边，则Dijkstra算法失效。假设存在节点A，B和C形成边权重为AB=3，AC=4和BC=-2的连通无向图的情况，则从A到C的最优路径成本为1，并且从A到B的成本为2。从A开始的Dijkstra算法将首先检查B，因为这是最接近的。它将为其分配一个3的成本，并将其标记为关闭，这意味着其成本将不会被重新评估。因此，Dijkstra不能评估负权边。然而，由于在许多实际的用途中永远不会有负权边，所以Dijkstra算法很大程度上适用于路径寻找的目的。
1.3 A*算法
A*是Dijkstra算法的变种，在游戏中经常用到。A*为每个开放节点分配一个权重，该权重等于该节点边缘的权重加上该节点与终点之间的近似距离。该近似距离由启发函数求出，表示该节点与终点之间可能的最短距离。这样可以在找到初始路径后消除较长的路径。如果在开始和结束之间存在长度为x的路径，并且节点和结束之间的最短距离大于x，则不需要检查该节点。相对于Dijkstra算法，A*使用这种启发式来改进搜索行为。当启发式估计为零时，A*等同于Dijkstra算法。随着启发式估计值增加并越接近真实距离，A*将继续寻找最佳路径，但运行速度更快（通过检查更少的节点）。当启发式的值恰好是真实的距离时，A*检查最少的节点。（然而，编写总是计算真实距离的启发函数通常是不切实际的。）随着启发式的值增加，A*检查更少的节点，但不再保证最佳路径。为了保持算法的快速运行，在很多应用程序（如视频游戏）中，这是可以接受的，甚至是可取的。
1.4 使用A*算法得到最短路径
A*是一种广泛用于路径搜索和图形遍历的计算机算法，即在多个点之间绘制高效可穿越路径的过程，这些点称为节点。由于其性能和精度，它被广泛使用。然而，在实际的出行路线系统中，它通常会被其他可以预处理图表以获得更好性能的算法超越，尽管其他研究发现A*优于其他方法。
斯坦福研究所（现为SRI国际）的Peter Hart，Nils Nilsson和Bertram Raphael首先在1968年描述了该算法。它是Edger Dijkstra在1959年提出的算法的扩展。A*通过使用启发式方法实现更好的时间性能。
A*使用最佳优先搜索并找到最低消耗。
2 文献调查
移动式机器人在硬质和光滑表面上比足式或踩踏式机器人更有效，并且由于现有工业环境中的硬地板和光滑的地板，其在工业中有着广泛的应用潜力。Jones等人提到的应用程序中可以找到几种移动性配置。最常见的单体机器人是差速驱动和同步驱动的三轮车或汽车状驱动器，以及全向转向机器人。除了应用的相关性之外，移动机器人的自主运动规划和控制问题引起了许多研究人员的兴趣，以应对其理论挑战。过去几年中，轮式移动机器人的运动控制已经引起了相当大的关注。机器人系统中的非完整行为特别有趣；因为它指出可以通过使用减少数量的致动器完全控制机构。特别地，由于滚动约束对轮子运动的完美应用，这些系统是非完整机构的典型例子。针对非完整约束移动机器人的运动控制问题，提出了几种控制器，其中两种主要方法是姿态稳定和轨迹跟踪。通过Muri和Neuman对轮式移动机器人的定义来激发建模过程，定义为“一种通过安装在机器人上且与表面接触的驱动车轮使得机器人能独自在表面运动的机器人。”然而，车辆的运动学设计要求有适当的自由度（机动性），使其能适应路面的变化和车轮的无滑移滚动。使用全方位车轮代替传统车轮增强了机动性。车轮无侧向滑移理想滚动的必要性对移动机器人车轮的运动具有非完整性（不可积性）约束。Alexander和Maddocks基于“无滑动滚动”约束条件开发了机器人刚体运动与车轮转向和驱动率之间的关系。这里通过最小化由库伦摩擦定律导出的非光滑凸散射函数来研究由于车轮未对准造成的滑移。这种最小化原理相当于构建准静态运动。设计机器人时需要考虑三个相关但不同的运动学方面，即流动性，控制和定位。第一个是机动性，它处理机器人为了在任何方向上达到最终目的地而可能遵循的动作。第二个方面是控制，涉及运动变量的选择：广义速度或坐标。最后，第三方面是定位，考虑用于减少机器人基于实现自主操作所必需的传感器测量的不确定性区域来估计机器人的实际位置和定向的定位系统。使用运动约束来限制沿配置空间的运动。运动学限制可以以任何速度应用，而动态约束条件对于以更高速度运行的代理人而言非常重要。机器人设计必须解决代理动力学问题，因为即使是没有任何运动约束的完整机器人也必须面对某种形式的动力学限制，特别是加速度和速度的限制。动力学约束限制一个代理人位置的衍生物的可接受值，超越了Time Moon等人证明了轮式移动机器人不能精确地沿直线运动，即使运动学问题得到了很好的纠正，这种现象也与电机控制器的加速度约束有关。平行轮式移动机器人的运动学模型不能满足Brockett反馈稳定的必要条件，从而暗示没有光滑或连续不变的时间。使用动力学方程考虑了非完整系统的镇定和控制问题，而在一些文献中提出了基于后退的方法。由于不适当的参数设置和时间常数而发生内部错误。外部错误在驱动WMR时不可避免地出现，并且由于两个驱动轮的不同摩擦和半径而发生。为了尽量减少这种错误，Chung等人提出了具有两个分离的反馈回路的反馈控制器;其中一个是位置反馈，另一个是方向反馈。基于反演算法，已经提出了一种鲁棒自适应控制器来设计辅助轮速控制器，以便使其与机器人运动的不确定性和研究机器人和轮驱动机构的未知动力学行为的模糊逻辑技术相比，跟踪误差尽可能小。这种方法的主要优点是使得以前对机器人运动学的知识以及机器人和轮子致动器的动力学变得不再必要。表征机器人动力学的参数将在线更新，从而在这些参数可能发生变化的应用（如负载运输）中提供更小的错误和更好的性能。利用李雅普诺夫理论分析了整个系统的稳定性，并且控制误差最终是有界的。Deng等人设计了一种基于李雅普诺夫函数候选的组合反馈控制方案，针对考虑局部最小值问题的动态环境中的四种障碍情况进行了讨论。控制器包括虚拟吸引力，排斥力和迂回力，而用于控制器设计的势场函数考虑欧几里得距离信息和机器人与目标之间相对速度的大小信息。已经推导出两轮移动机器人的动态模型，其中显示了具有3个自由度的平移运动和旋转运动，并且在这里，动态模型在一定的假设下被简化为运动学模型。Arvin等人提出了基于脉宽调制（PWM）的移动机器人运动控制技术。移动机器人的车轮已经被Chakraborty和Ghosal建模为圆环，并被用作被动关节，从而强制实现横向自由度，从而在不使用在应用中有几个限制的可变长度轴（VLA）的情况下在不平坦地形中实现无滑动运动。Zhang等人开发了一种反馈控制律，允许2轮差动驱动的移动机器人通过使用积分反推方法和李雅普诺夫函数来跟踪规定的轨迹，以确保轨迹跟踪控制器具有全局渐近稳定性。Zohar等人最近提出了用于移动机器人模型的轨迹跟踪的控制方案，其包括通过使用虚拟车辆的概念和平坦度的概念以及应用反推方法得到的运动学和动力学上的对运动的影响。Gandhi和Ghorbel已经提出了用于非线性控制器的谐波驱动系统，以补偿在高速调节和轨迹跟踪应用中存在灵活性时的运动误差。Pathak等人已经讨论了具有扭矩和姿态控制器的空间机器人的行为。Han等人已经提出了具有恒定的大旋转半径的单曲率轨迹作为最佳轨迹，以便在捕获拥有预定的初始状态和最终状态的移动物体的同时，最小化差速驱动移动机器人的跟踪误差。在没有障碍物的环境中，移动时域控制器可以用于受到非完整约束的轮式移动机器人的跟踪控制。控制策略来源于优化二次成本函数，该函数惩罚每个采样时间中的跟踪误差和控制变量。
3 早期工作
3.1 基于模糊逻辑控制器的移动机器人导航
模糊逻辑技术在移动机器人智能控制器的设计中起着重要的作用。该技术用于移动机器人的导航。模糊集理论提供了一个数学框架，用于表示和处理模糊性、不精确性、缺乏信息和部分事实的不确定性。模糊控制系统采用类似于人类决策过程的近似推理模式。
3.2 模糊决策与控制算法设计
该机器人在一个2times;2.4平方米的带有移动障碍物和要到达的目标的场地（完全由网络摄像头查看）中运作，目标和障碍物的位置未预先知道；因此导航算法必须只依赖于传感信息来实现反应模式。首先，用两个不同的模糊控制器分别实现两个简单的行为，即达到目标并避开障碍物，以下称为FLC1和FLC2。达到目标行为以及避免障碍物行为取决于人造视觉信息，并且是移动机器人的首要任务它具有最高优先级，并且只有在机器人路径上出现障碍时才会发生。随后，模糊管理程序负责将优先级代码之后由每个FLC计算出的参考车轮速度进行组合。 最终的指令速度被发送到机器人的内置速度控制回路。这些控制器足以在大多数导航任务中保证移动机器人令人满意的导航性能。探索环境行为使移动机器人标记已经访问的区域并寻找未开发区域。移动机器人被赋予一种空间局部存储器，该存储器被另一个模糊控制器（以下称为FLC3）用于定位和避开箱形峡谷。整个控制方案的结构如图4所示。我们控制器的模块化架构在整体解决方案方面具有以下主要优势：1.调试和调整操作更快更简单，因为每个行为都是通过少量规则和输入来描述的;2.由于可以轻松添加新的简单行为以扩展移动机器人能力，因此最终结构更加灵活。达到目标，此行为会对视觉系统的刺激产生反应，提供有关移动机器人与目标之间相对位置的信息。达到目标此行为会对视觉系统的刺激产生反应，提供有关移动机器人与目标之间相对位置的信息。这种行为忽略了障碍物的存在和位置。机器人的顶部装有两个相同颜色的不同直径的圆圈，用于位置和方向检测，目标用红色球标记。图像处理是基于传统的RGB
全文共10177字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[8954]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
