龙源期刊网 https://www.doczj.com/doc/a29235132.html,
智能机器人避障路径规划算法研究
作者：张永妮
来源：《中小企业管理与科技·上旬刊》2016年第02期
摘要：智能机器人只有具备自主移动能力才能实现应用价值。路径规划用于决策机器人
在环境中如何行走的问题，是实现机器人智能化的关键技术。为提高机器人路径规划，对未知环境的实时性、适应性和优化性要求越来越高。自主移动机器人是集环境感知、动态策略与规划、行为控制与执行等多功能于一体的综合系统。近几年，移动机器人技术在工业、农业、医学、航天航空等许多领域发挥了重要作用。其中智能避障更是研究领域的难点和热点，智能避障是能够根据采集障碍物的状体信息，按照一定的方法进行有效的避障，最后到达终点。本文主要介绍了动态窗口和Bug2的避障算法和研究与仿真。实现这两种避障算法主要基于Matlab 等语言编程开发，实现对移动机器人避障算法的仿真。Matlab功能强大、编程简单、适用广。
最后，验证基于Bug算法的几种路径规划方法，将避障实时性，环境的适应性、规划路径的优化性作为算法性能指标，进行仿真实验与对比实验分析。结果验证了算法的有效性。
关键词：智能机器人；避障；MATLAB仿真；路径规划
1 绪论
智能机器人避障算法的研究对于推进机器人领域的应用和发展具有重要的意义。随着计算机技术、传感器技术、控制技术的发展，智能机器人的避障技术已经取得了丰硕的研究成果，其应用领域不断的扩大，应用复杂程度也越来越高，因此对其关键技术提出了更高要求，相应的方法也更加成熟。
本文通过查阅文献资料，对目前智能机器人的发展动态有了一定了解。对现阶段机器人避障的一些常用方法做了研究，然后设计了不同算法在未知环境下的避障仿真实验来验证本文所设计的算法的可行性。路径规划要求机器人能够在较短的时间内，感知到范围尽可能大的区域，从而找到最近的路径使机器人能够沿着最优路径运动到终点，并避开障碍物。
2 基于动态窗口的避障算法及仿真
2.1 概述
机器人局部路径规划的方法很多，动态窗口法就是其中的一种，其主要是在速度（v，w）空间中采样多组速度，并模拟机器人在这些速度下一定时间内的轨迹。在得到多组轨迹以后，对这些轨迹进行评价，选取最优轨迹所对应的速度来驱动机器人运动。该算法突出点在于动态窗口这个名词，它的含义是依据移动机器人的及速度性能限定速度采样空间在一个可行的动态图范围内。
第3章系统总体结构及工作原理 该系统主要以超声波测距为基本测距原理, 并在相应的硬件和软件的支持下, 达到机器人避障的效果。 3.1机器人总体硬件设计 3.1.1传感器的分布要求 为了全方位检测障物的分布状况, 并及时为机器人系统提供全面的数据, 可将所需的八个传感器均匀排列在机器人周围, 相邻每对传感器互成45度角。为了避免相互干扰, 八个传感器以程序运行周期为周期, 进行循环测距。传感器排列示意图如下: 图3.1.1 传感器分布图
图3.1.2 硬件设计总体框架图 上图为支持机器人运行实用程序的硬件部分的总体设计框架图, 由负责相关任务的同学提供。在超声波信号输入单片机以后, 由存储在单片机中的主程序调用避障子程序, 根据输入信号执行避障指令, 并使相关数据返回主程序, 转而提供给电机和LED显示器的驱动程序使用, 最后, 由电机执行转向指令, 结果则显示在LED显示器上。
图3.1.3 软件总体框架图 由上图可知, 本文作者负责的超声波避障程序为软件总体设计中的子程序部分。在主程序运行过程中, 若调用超声波避障程序, 机器人在自行轨迹规划后, 将程序处理所得数据送给电机处
理成立程序, 控制电机动作。具体的避障程序设计将在第4章进行。 3.2超声波测距原理 测距原理: 超声波是指频率高于20KHz的机械波。为了以超声波作为检测手段, 必须产生超生波和接收超声波。完成这种功能的装置就是超声波传感器, 习惯上称为超声波换能器或超声波探头。超声波传感器有发送器和接收器, 但一个超声波传感器也可具有发送和接收声波的双重作用。超声波传感器是利用压电效应的原理将电能和超声波相互转化即在发射超声波的时候, 将电能转换, 发射超声波; 而在收到回波的时候, 则将超声振动转换成电信号。[8] 超声波测距的原理一般采用渡越时间法TOF( time of flight) 。首先测出超声波从发射到遇到障碍物返回所经历的时间, 再乘以超声波的速度就得到二倍的声源与障碍物之间的距离, 即: [8] D=ct/2 其中D为传感器与障碍物之间的距离, 以m计, c为超声波速度, 这里以340m/s计, t为超声波从发送到接收的总时间, 以s计。
文章编号 2 2 2 一种快速神经网络路径规划算法α 禹建丽? ∏ √ 孙增圻成久洋之 洛阳工学院应用数学系日本冈山理科大学工学部电子工学科 2 清华大学计算机系国家智能技术与系统重点实验室日本冈山理科大学工学部信息工学科 2 摘要本文研究已知障碍物形状和位置环境下的全局路径规划问题给出了一个路径规划算法其能量函数 利用神经网络结构定义根据路径点位于障碍物内外的不同位置选取不同的动态运动方程并针对障碍物的形状设 定各条边的模拟退火初始温度仿真研究表明本文提出的算法计算简单收敛速度快能够避免某些局部极值情 况规划的无碰路径达到了最短无碰路径 关键词全局路径规划能量函数神经网络模拟退火 中图分类号 ×°文献标识码 ΦΑΣΤΑΛΓΟΡΙΤΗΜΦΟΡΠΑΤΗΠΛΑΝΝΙΝΓ ΒΑΣΕΔΟΝΝΕΥΡΑΛΝΕΤ? ΟΡΚ ≠ 2 ? ? ≥ 2 ≥ ∏ ΔεπαρτμεντοφΜατηεματιχσ ΛυοψανγΙνστιτυτεοφΤεχηνολογψ Λυοψανγ
ΔεπαρτμεντοφΕλεχτρονιχΕνγινεερινγ ΦαχυλτψοφΕνγινεερινγ ΟκαψαμαΥνι?ερσιτψοφΣχιενχε 2 Ριδαι2χηο 2 ?απαν ΔεπαρτμεντοφΧομπυτερΣχιενχε Τεχηνολογψ ΣτατεΚεψΛαβοφΙντελλιγεντΤεχηνολογψ Σψστεμσ ΤσινγηυαΥνι?ερσιτψ Βει?ινγ ΔεπαρτμεντοφΙνφορματιον ΧομπυτερΕνγινεερινγ ΦαχυλτψοφΕνγινεερινγ ΟκαψαμαΥνι?ερσιτψοφΣχιενχε 2 Ριδαι2χηο 2 ?απαν Αβστραχτ ∏ √ √ √ × ∏ ∏ ∏ ∏ ∏ ∏ 2 ∏ √ × ∏ ∏ ∏ ∏ √ ∏ Κεψωορδσ ∏ ∏ ∏ 1引言Ιντροδυχτιον 机器人路径规划问题可以分为两种一种是基于环境先验完全信息的全局路径规划≈ 另一种是基于传感器信息的局部路径规划≈ ?后者环境是未知或者部分未知的全局路径规划已提出的典型方法有可视图法 ! 图搜索法≈ ! 人工势场法等可视图法的优点是可以求得最短路径但缺乏灵活性并且存在组合爆炸问题图搜索法比较灵活机器人的起始点和目标点的改变不会造成连通图的重新构造但不是任何时候都可以获得最短路径可视图法和图搜索法适用于多边形障碍物的避障路径规划问题但不适用解决圆形障碍物的避障路径规划问题人工势场法的基本思想是通过寻找路径点的能量函数的极小值点而使路径避开障碍物但存在局部极小值问题且不适于寻求最短路径≈ 文献≈ 给出的神经网络路径规划算法我们称为原算法引入网络结构和模拟退火等方法计算简单能避免某些局部极值情况且具有并行性及易于从二维空间推广到三维空间等优点对人工势场法给予了较大的改进但在此算法中由于路径点的总能量函数是由碰撞罚函数和距离函数两部分的和构成的而路径点 第卷第期年月机器人ΡΟΒΟΤ? α收稿日期
机 械 工 程 学 报 JOURNAL OF MECHANICAL ENGINEERING 第46卷第13期 2010年7月 Vol.46 No.13 Jul. 2010 DOI ：10.3901/JME.2010.13.109 基于A *算法的空间机械臂避障路径规划* 贾庆轩 陈 钢 孙汉旭 郑双奇 (北京邮电大学自动化学院 北京 100876) 摘要：针对空间机械臂在轨操作任务需求，提出一种基于A*算法的避障路径规划算法。根据机械臂和障碍物几何特征，对机械臂模型和障碍模型进行简化。通过研究机械臂本身所固有的几何特性，根据障碍物的位姿坐标，分析机械臂各杆件与障碍物发生碰撞的条件，进而求解空间机械臂的无碰撞自由工作空间。在此基础上，利用A*算法在空间机械臂的自由工作空间进行无碰撞路径搜索，实现了空间机械臂的避障路径规划。通过仿真试验验证了基于A*算法的空间机械臂避障路径规划算法的有效性与可行性。 关键词：空间机械臂 避障路径规划 A*算法 中图分类号：TP242 Path Planning for Space Manipulator to Avoid Obstacle Based on A * Algorithm JIA Qingxuan CHEN Gang SUN Hanxu ZHENG Shuangqi (Automation School , Beijing University of Posts and Telecommunications, Beijing 100876) Abstract ：A novel path planning method to avoid obstacle based on A* algorithm is presented for space manipulator to accomplish the in-orbit mission. According to the geometric characteristics of manipulator and obstacle, the manipulator model and obstacle model are simplified. On the basis of the inherent geometric characteristic of manipulator, and according to the position and orientation coordinates of obstacle, the collision conditions of all links of manipulator are analyzed. And then, the collision-free workspace of space manipulator is obtained. On this basis, the collision-free path search in the free workspace of space manipulator is carried out by using A* algorithm, thereby, the obstacle avoidance path planning is achieved. The effectiveness and feasibility of the proposed path planning algorithm based on A* algorithm for space manipulator to avoid obstacle are verified by simulation and experiment. Key words ：Space manipulator Obstacle avoidance path planning A* algorithm 0 前言 随着空间探索的不断深入，空间机械臂应用技 术已经成为空间技术的重要研究方向。空间机械臂代替宇航员完成空间作业任务，如组装与搭建空间站、释放与回收卫星、维护空间设备以及完成空间科学试验等，大大减小了宇航员舱外作业的风险，因此空间机械臂应用技术受到国内外专家的高度重视。在微重力环境下，空间机械臂系统处于自由漂 * 国家高技术研究发展计划资助项目(863计划，2009AA7041007)。 20100324收到初稿，20100504收到修改稿 浮状态，使得机械臂控制变量与非独立变量之间存在强烈的运动耦合，运动控制难度加大，从而空间机械臂的路径规划变得特别复杂[1]。此外，由于空间环境中的空间碎片，空间舱体外设试验装置等都有可能成为空间机械臂在轨操作过程中的障碍，因此为了顺利完成在轨操作任务，开展空间机械臂避障路径规划研究十分重要。 避障路径规划是指在给定的障碍条件以及起始和目标的位姿，选择一条从起始点到达目标点的路径，使运动物体能安全、无碰撞地通过所有的障碍[2]。目前，针对机械臂避障路径规划提出了许多方法，其中最为典型的包括基于自由空间法和人工
东南大学 硕士学位论文 移动机器人完全遍历路径规划算法研究 姓名：胡正聪 申请学位级别：硕士 专业：机械电子工程 指导教师：张赤斌 20080403
第一章绪论 第一章绪论 １．１移动机器人的发展史 社会的主体是人类，历史的推动者是人类，伟大的人类运用自己的智慧不断创造伟大的发明，不断推动社会的发展。邓小平同志说过：“科技是第一生产力。”生产力是社会发展的动力，所以人类推动社会发展就是要致力于发展生产力，致力于发展科技。人类不断发展生产力来提高自身认识自然、改造自然、得到自己所需物质的能力，这种能力的进化由最初的运用双手、简单工具、发展到运用畜力、发展到运用简单机器、发展到运用自动化设备、还会发展到我们无法想象的未来。 机器人就是生产力发展的产物。机器人的概念最早是在１９２０年的科幻小说中提出的，而早期的机器人如１９３９年美国纽约世界博览会上展出的西屋电气公司制造的家用机器人Ｅｌｅｋｔｒｏ和１９５６年美国人乔治?德沃尔制造出的世界上第一台可编程的机器人都是一些实用价值不高的机器人，它们是现代机器人的雏形。上世纪６０年代，由于传感器和计算机技术的发展及应用，兴起了全世界第二代机器人的研究热潮，并向人工智能进发。１９６８年，美国斯坦福研究所公布了他们研发成功的机器人Ｓｈａｋｅｙ。它带有视觉传感器，能根据人的指令发现并抓取积木。Ｓｈａｋｅｙ可以算是世界第一台智能机器人，它拉开了第三代机器人研发的序幕。到了上世纪８０年代，发达国家都组建各种机器人研究机构，尤其是以美国为代表的国家将机器人的研究列入了军事发展计划，带动各国把机器人的研究推上了高潮，日本和欧洲各国都成立了各自的机器人研究中心和规划了自己的研究计划。进入９０年代后，机器人的应用领域除了工业和军事外，还涉及到了服务和娱乐领域，以日本本田公司的ＡＳＩＭＯ人型机器人和索尼公司的ＡＩＢＯ娱乐机器人为代表的机器人展示了机器人领域各方面的先进研究成果。在欧洲，２００２年丹麦ｉＲｏｂｏｔ公司推出了吸尘器机器人Ｒｏｏｍｂａ，它能避开障碍，自动设计行进路线，还能在电量不足时，自动驶向充电座。Ｒｏｏｍｂａ是目前世界上销量最大、最商业化的家用机器人。２００６年６月，微软公司推出ＭｉｃｒｏｓｏＲＲｏｂｏｔｉｃｓＳｔｕｄｉｏ，机器人模块化、平台统一化的趋势越来截明显，比尔?盖茨预言：“家用机器人很快将席卷伞球。” 图１．１丹麦ｉＲｏｂｏｔ公司推出的吸尘机器人Ｒｏｏｍｂａ［
遗传算法与机器人路径规划 摘要：机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 关键词：路径规划；移动机器人；避障；遗传算法 Genetic Algorithm and Robot Path Planning Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers（e.g time optimal），and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. Key words: Path planning,mobile robot, avoid the obstacles, genetic algorithm 1路径规划 1.1机器人路径规划分类 （1）根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类： 1，已知环境下的对静态障碍物的路径规划； 2，未知环境下的对静态障碍物的路径规划； 3，已知环境下对动态障碍物的路径规划； 4，未知环境下的对动态障碍物的路径规划。 （2）也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型： 1，基于环境先验完全信息的全局路径规划； 2，基于传感器信息的局部路径规划。 （第二种中的环境是未知或部分未知的，即障碍物的尺寸、形状和位置等信息必须通过传感器获取。） 1.2路径规划步骤 无论机器人路径规划属于哪种类别，采用何种规划算法，基本上都要遵循以下步骤： 1, 建立环境模型，即将现实世界的问题进行抽象后建立相关的模型； 2, 路径搜索方法，即寻找合乎条件的路径的算法。 1.3路径规划方法
一种移动机器人的路径规划算法 作者：霍迎辉，张连明 (广东工业大学自动化研究所广州510090 文章来源：自动化技术与应用点击数：1419 更新时间：2005-1-24 摘要：本文提出一种移动机器人路径规划最短切线路径算法。依据此算法，机器人能顺利地避开障碍物到达目标位置，其原理简单，计算快捷，容易实现。仿真结果验证了它的有效性和实用性。 关键词：移动机器人；路径规划；机器人避障 1引言 移动机器人路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给定起点到终点的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物［1］。 障碍环境中机器人的无碰撞路径规划［2］是智能机器人研究的重要课题之一，由于在障碍空间中机器人运动规划的高度复杂性使得这一问题至今未能很好地解决。路径规划问题根据机器人的工作环境模型可以分为两种，一种是基于模型的路径规划，作业环境的全部信息都是预知的；另一种是基于传感器的路径规划，作业环境的信息是全部未知或部分未知的。 对机器人路径规划的研究，世界各国的专家学者们提出了许多不同的路径规划方法，主要可分为全局路径和局部路径规划方法。全局路径规划方法有位形空间法、广义锥方法、顶点图像法、栅格划归法；局部路径规划方法主要有人工势场法。这些方法都各有优缺点［3］，也没有一种方法能够适用于任何场合。 本文提出一种最短切线路径的规划方法，其涉及的理论并不高深，计算简单，容易实现，可供侧重于应用的读者参考。下面将详细介绍该算法的基本原理，最后给出仿真实现的结果。 2最短切线路径算法 2.1算法基本原理 (1)首先判断机器人和给定的目标位置之间是否存在障碍物。如图1所示，以B代表目标位置，其坐标 为(x Ｂ，y Ｂ ），以R、A分别代表机器人及障碍物，坐标为(x Ｒ ，y Ｒ )、(x Ａ ，y Ａ )。Ｒr和Ra表示机器人和障 碍物的碰撞半径，也就是说在其半径以外无碰撞的危险。这里对碰撞半径的选择作出一点说明，碰撞半径越小，发生碰撞的危险度越大，但切线路径越短；碰撞半径越大，发生碰撞的危险度越小，但同时切线路径越长。要根据实际情况和控制要求来确定碰撞半径。若机器人与目标位置之间不存在障碍物，机器人可走直线直接到达目标位置，此时的直线方程可由两点式确定：
MATLAB 实现基于蚁群算法的机器人路径规划 1、问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则（如最小能量消耗，最短行走路线，最短行走时间等），在其工作空间中找到一条从起 始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 2 算法理论 蚁群算法（Ant Colony Algorithm ，ACA ），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS ），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士给出改进模型（ACS ），文中改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos 给出了最大-最小蚂蚁系统（MAX-MINAS ），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图2-1 所示，AE 之间有两条路ABCDE 与ABHDE ，其中AB ，DE，HD，HB 的长度为1，BC，CD 长度为0.5，并且，假设路上信息素浓度为0，且各个蚂蚁行进速度相同，单位时间所走的长度为1，每个单位时间内在走过路径上留下的信息素的量也相同。当t=0 时，从A 点，E 点同时各有30 只蚂蚁从该点出发。当t=1，从A 点出发的蚂蚁走到B 点时，由于两条路BH 与BC 上的信息素浓度相同，所以蚂蚁以相同的概率选择BH 与BC ，这样就有15 只蚂蚁选择走BH，有15 只蚂蚁选择走BC 。同样的从E 点出发的蚂蚁走到D 点，分别有15 只蚂蚁选择DH 和DC。当t=2 时，选择BC 与DC 的蚂蚁分别走过了BCD 和DCB ，而选择BH 与DH 的蚂蚁都走到了H 点。所有的蚂蚁都在所走过的路上留下了相同浓度的信息素，那么路径BCD 上的信息素的浓度是路径BHD 上信息素浓度的两倍，这样若再次有蚂蚁选择走BC 和BH 时，或选择走DC 与DH 时，都会以较大的概率选择信息素浓度高的一边。这样的过程反复进行下去，最短的路径上走过的蚂蚁较多，留下的信息素也越多，蚁群这样就可以找到一条较短的路。这就是它们群体智能的体现。 蚁群算法就是模拟蚂蚁觅食过程中可以找到最短的路的行为过程设计的一种仿生算法。在用蚁群算法求解组合优化问题时，首先要将组合优化问题表达成与信息素相关的规范形式，然后各个蚂蚁独立地根据局部的信息素进行决策构造解，并根据解的优劣更新周围的信息素，这样的过程反复的进行即可求出组合优化问题的优化解。 归结蚁群算法有如下特点： （1）分布式计算：各个蚂蚁独立地构造解，当有蚂蚁个体构造的解较差时，并不会影响整体的求解结果。这使得算法具有较强的适应性； （2）自组织性：系统学中自组织性就是系统的组织指令是来自系统的内部。同样的蚁群算法中的各个蚂蚁的决策是根据系统内部信息素的分布进行的。这使得算法具有较强的鲁棒性； （3）正反馈机制与负反馈机制结合：若某部分空间上分布的信息素越多，那么在这个空间上走过的蚂蚁也就越多；走过的蚂蚁越多，在那个空间上留下的信息素也就越多，这就是存在的正反馈机制。但蚁群算法中解的构造是通过计算转移概率实现的，也就是说构造解的时候可以接受退化解，这限制了正反馈机制，
第25卷第7期V ol.25No.7 控制与决策 Control and Decision 2010年7月 Jul.2010移动机器人路径规划技术综述 文章编号:1001-0920(2010)07-0961-07 朱大奇,颜明重 (上海海事大学水下机器人与智能系统实验室，上海201306) 摘要:智能移动机器人路径规划问题一直是机器人研究的核心内容之一.将移动机器人路径规划方法概括为:基于模版匹配路径规划技术、基于人工势场路径规划技术、基于地图构建路径规划技术和基于人工智能的路径规划技术.分别对这几种方法进行总结与评价,最后展望了移动机器人路径规划的未来研究方向. 关键词:移动机器人；路径规划；人工势场；模板匹配；地图构建；神经网络；智能计算 中图分类号:TP18；TP273文献标识码:A Survey on technology of mobile robot path planning ZHU Da-qi,YAN Ming-zhong (Laboratory of Underwater Vehicles and Intelligent Systems，Shanghai Maritime University，Shanghai201306, China．Correspondent：ZHU Da-qi，E-mail：zdq367@https://www.doczj.com/doc/a29235132.html,) Abstract:The technology of intelligent mobile robot path planning is one of the most important robot research areas.In this paper the methods of path planning are classi?ed into four classes:Template based,arti?cial potential?eld based,map building based and arti?cial intelligent based approaches.First,the basic theories of the path planning methods are introduced brie?y.Then,the advantages and limitations of the methods are pointed out.Finally,the technology development trends of intelligent mobile robot path planning are given. Key words:Mobile robot；Path planning；Arti?cial potential?eld；Template approach；Map building；Neural network; Intelligent computation 1引言 所谓移动机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务.移动机器人路径规划主要解决3个问题:1)使机器人能从初始点运动到目标点;2)用一定的算法使机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务;3)在完成以上任务的前提下,尽量优化机器人运行轨迹.机器人路径规划技术是智能移动机器人研究的核心内容之一,它起始于20世纪70年代,迄今为止,己有大量的研究成果报道.部分学者从机器人对环境感知的角度,将移动机器人路径规划方法分为3种类型[1]:基于环境模型的规划方法、基于事例学习的规划方法和基于行为的路径规划方法;从机器人路径规划的目标范围看,又可分为全局路径规划和局部路径规划;从规划环境是否随时间变化方面看,还可分为静态路径规划和动态路径规划. 本文从移动机器人路径规划的具体算法与策略上,将移动机器人路径规划技术概括为以下4类:模版匹配路径规划技术、人工势场路径规划技术、地图构建路径规划技术和人工智能路径规划技术.分别对这几种方法进行总结与评价,展望了移动机器人路径规划的未来发展方向. 2模版匹配路径规划技术 模版匹配方法是将机器人当前状态与过去经历相比较,找到最接近的状态,修改这一状态下的路径,便可得到一条新的路径[2,3].即首先利用路径规划所用到的或已产生的信息建立一个模版库,库中的任一模版包含每一次规划的环境信息和路径信息,这些模版可通过特定的索引取得;随后将当前规划任务和环境信息与模版库中的模版进行匹配,以寻找出一 收稿日期:2009-08-30；修回日期:2009-11-18. 基金项目:国家自然科学基金项目(50775136)；高校博士点基金项目(20093121110001)；上海市教委科研创新项目(10ZZ97). 作者简介:朱大奇(1964?),男,安徽安庆人,教授,博士生导师,从事水下机器人可靠性与路径规划等研究；颜明重(1977?),男,福建泉州人,博士生,从事水下机器人路径规划的研究.
最优路径规划算法设计 一、 问题概述 兵力机动模型的功能是支持实施机动的实体按照指定路线，由作战空间的一点向另外一点的位置移动，并带入实体在移动过程中发生变化的状态信息。 兵力机动模型包括行军模型、战斗转移模型、机动能力评估模型。涉及的关键算法包括最优路径规划、行军长径计算、行军时间计算、行军所需油料计算、行军方案评估与优选等。 最优路径问题又称最短路问题。是网络优化中的基本问题，如TSP 问题等。下面先举例说明该问题。 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 旅行商问题（TSP －traveling salesman problem ） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地？） 最短路问题是组合优化中的经典问题，它是通过数学方法寻找离散时间的最优编排、分组、次序、或筛选等，这类问题可用数学模型描述为 min )(x f ..t s 0)(≥x g D x ∈. 其中，)(x f 为目标函数，)(x g 为约束函数，x 为决策变量，D 表示有限个点组成的集合。 一个组合最优化问题可用三个参数),,(f F D 表示，其中D 表示决策变量的定义域，F 表示可行解区域}0)(,|{≥∈=x g D x x F ，F 中的任何一个元素称为该问
题的可行解，f 表示目标函数，满足}|)(m in{)(*F x x f x f ∈=的可行解*x 称为该问题的最优解。组合最优化的特点是可行解集合为有限点集。由直观可知，只要将D 中有限个点逐一判别是否满足0)(≥x g 的约束并比较目标值的大小，就可以得到该问题的最优解。 以上述TSP 问题为例，具体阐述组合优化问题： 此模型研究对称TSP 问题,一个商人欲到n 个城市推销产品，两个城市i 和j 之间的距离ji ij d d =，用数学模型描述为 ∑≠j i ij ij x d min 1..1 =∑=n j ij x t s n i ,,2,1Λ=， 1..1 =∑=n i ij x t s n j ,,2,1Λ=， },,,2,1{,2||2,1||,n s n s s x s j i ij Λ?-≤≤-≤∑∈ j i n j i x ij ≠=∈,,,2,1,},1,0{Λ 约束条件决策变量1=ij x 表示商人行走的路线包含从城市i 到j 的路，而0=ij x 表示商人没有选择走这条路；j i ≠的约束可以减少变量的个数，使得模型中共有 )1(-?n n 个决策变量。 每一个组合优化问题都可以通过完全枚举的方法求得最优解。枚举是以时间为代价的，在TSP 问题中，用n 个城市的一个排列表示商人按这个排列序推销并返回起点。若固定一个城市为起终点，则需要)!1(-n 个枚举。以计算机s 1可以完成24个城市所有路径枚举为单位，则25个城市的计算时间为：以第1个城市为起点，第2个到达城市有可能是第2个、第3个、……、第25个城市。决定前两个城市的顺序后，余下是23个城市的所有排列，枚举这23个城市的排列需要s 1，所以，25个城市的枚举需要24s 。类似地归纳，城市数与计算时间的关系如表1所示。
龙源期刊网 https://www.doczj.com/doc/a29235132.html, 智能机器人避障路径规划算法研究 作者：张永妮 来源：《中小企业管理与科技·上旬刊》2016年第02期 摘要：智能机器人只有具备自主移动能力才能实现应用价值。路径规划用于决策机器人 在环境中如何行走的问题，是实现机器人智能化的关键技术。为提高机器人路径规划，对未知环境的实时性、适应性和优化性要求越来越高。自主移动机器人是集环境感知、动态策略与规划、行为控制与执行等多功能于一体的综合系统。近几年，移动机器人技术在工业、农业、医学、航天航空等许多领域发挥了重要作用。其中智能避障更是研究领域的难点和热点，智能避障是能够根据采集障碍物的状体信息，按照一定的方法进行有效的避障，最后到达终点。本文主要介绍了动态窗口和Bug2的避障算法和研究与仿真。实现这两种避障算法主要基于Matlab 等语言编程开发，实现对移动机器人避障算法的仿真。Matlab功能强大、编程简单、适用广。 最后，验证基于Bug算法的几种路径规划方法，将避障实时性，环境的适应性、规划路径的优化性作为算法性能指标，进行仿真实验与对比实验分析。结果验证了算法的有效性。 关键词：智能机器人；避障；MATLAB仿真；路径规划 1 绪论 智能机器人避障算法的研究对于推进机器人领域的应用和发展具有重要的意义。随着计算机技术、传感器技术、控制技术的发展，智能机器人的避障技术已经取得了丰硕的研究成果，其应用领域不断的扩大，应用复杂程度也越来越高，因此对其关键技术提出了更高要求，相应的方法也更加成熟。 本文通过查阅文献资料，对目前智能机器人的发展动态有了一定了解。对现阶段机器人避障的一些常用方法做了研究，然后设计了不同算法在未知环境下的避障仿真实验来验证本文所设计的算法的可行性。路径规划要求机器人能够在较短的时间内，感知到范围尽可能大的区域，从而找到最近的路径使机器人能够沿着最优路径运动到终点，并避开障碍物。 2 基于动态窗口的避障算法及仿真 2.1 概述 机器人局部路径规划的方法很多，动态窗口法就是其中的一种，其主要是在速度（v，w）空间中采样多组速度，并模拟机器人在这些速度下一定时间内的轨迹。在得到多组轨迹以后，对这些轨迹进行评价，选取最优轨迹所对应的速度来驱动机器人运动。该算法突出点在于动态窗口这个名词，它的含义是依据移动机器人的及速度性能限定速度采样空间在一个可行的动态图范围内。
1.自主机器人近距离操作运动规划体系 在研究自主运动规划问题之前，首先需建立相对较为完整的自主运动规划体系，再由该体系作为指导，对自主运动规划的各项具体问题进行深入研究。本节将根据自主机器人的思维方式、运动形式、任务行为等特点，建立与之相适应的自主运动规划体系。并按照机器人的数量与规模，将自主运动规划分为单个机器人的运动规划与多机器人协同运动规划两类规划体系。 1.1单个自主机器人的规划体系 运动规划系统是自主控制系统中主控单元的核心部分，因此有必要先研究自主控制系统和其主控单元的体系结构问题。 自主控制技术研究至今，先后出现了多种体系结构形式，目前被广泛应用于实践的是分布式体系结构，其各个功能模块作为相对独立的单元参与整个体系。随着人工智能技术的不断发展，基于多Agent的分布式体系结构逐渐成为了主流，各功能模块作为独立的智能体参与整个自主控制过程，该体系结构应用的基本形式如图1所示。一方面，主控单元与测控介入处理、姿态控制系统、轨道控制系统、热控系统、能源系统、数传、有效载荷控制等功能子系统相互独立为智能体，由总线相连；另一方面，主控单元为整个系统提供整体规划，以及协调、管理各子系统Agent的行为。测控介入处理Agent保证地面系统对整个系统任意层面的控制介入能力，可接受上行的使命级任务、具体的飞行规划和底层的控制指令；各子系统Agent存储本分系统的各种知识和控制算法，自主完成主控单元发送的任务规划，并将执行和本身的健康等信息传回主控单元，作为主控单元Agent运行管理和调整计划的依据。 图1 基于多Agent的分布式自主控制系统体系结构基本形式示意图 主控单元Agent采用主流的分层递阶式结构，这种结构层次鲜明，并且十分利于实现，其基本结构如图2所示。主控单元由任务生成与调度、运动行为规划和控制指令生成三层基本结构组成，由任务生成与调度层获得基本的飞行任务，经过运动行为规划层获得具体的行为规划，再由控制指令生成层得到最终的模块控制指令，发送给其它功能Agent。各功能Agent发送状态信息给主控单元的状态检测系统，状态检测系统将任务执行情况和子系统状态反馈回任务生成与调度层，以便根据具体情况对任务进行规划调整。当遇到突发情况时，还可启用重规划模块，它可根据当时情况迅速做出反应快速生成行为规划，用以指导控制指令生成层得到紧急情况的控制指令。此外，地面控制系统在三个层次上都分别具有介入能
[选取日期] NUAA未知环境的动态路径规划 [键入文档副标题] | 刘绍翰
度量距离 灰度化 四连通和8连通。 第一章、静态搜索与A*算法 很多时候，我们需要在一个图中寻找一条从源点到目标节点的最短路径，我们称之为路径规划。搜索算法主要分为，盲目搜索和启发式搜索，它们的一个作用是能够从解空间中需找一条从源点到目标节点的最短路径。启发式搜索是在搜索的过程中，参考一定的指标函数来决定搜索的策略。 迪杰斯特拉算法，类似于广度优先遍历，利用源点到当前节点的代价值作为指标，其一定可以获得从原点到目标节点的最短路，但是其访问的节点数很多。 而最好优先搜索，采用离标节点的距离作为搜索的代价参考值，贪心选择最小的扩展节点，也可以获得最短路径，而且其搜索的节点数目大大减少。 图1 迪杰斯特拉算法图2 最好优先搜索算法当地图中包含障碍物时，迪杰斯特拉算法，仍然可以获得最短路径的路径，最好优先搜索的节点尽管少，但是其不能获得最优解。 图3 迪杰斯特拉算法图4 最好优先搜索算法而A*算法，参考了从原点到当前节点的代价值和当前节点到目标节点启发值，综合了迪杰斯特拉算法和做好优先搜索算法优点，在有障碍物和无障碍物的地图上，可以像迪杰斯特拉算法一样求得最短路径同时，同时能够像最好优先搜索一样减少搜索范围，减少搜索节点的数目。
图5 无障碍物时A*路径规划 图6 有障碍物时A*路径规划算法 经典的迪杰斯特拉算法可以求得最短的路径，而启发式搜索A* 算法，不但可以求得最短路，而且可以使得搜索的范围大大减少，上述算法是传统的静态路径规划算法，其规划的前提条件是已经知地图的结构。A*算法属于离线事先规划，在规划完毕之后，可以沿着最优路径移动，不是在线规划，不能一边规划一边移动。 A*算法的基本理论 A*算法又叫做启发式搜索算法，具有悠久的历史，其启发函数f=g+h 。其中g 表示从原点到当前节点已经付出的代价，好表示从当前节点到目标节点的启发值。 1) A*算法必须满足h(x)<=h*(x)，其中h*(x)是实际的启发值，h*(x)在实际中通常是无 法事先得知的，但是这个条件是很容易满足，只要满足该条件，一定能够获得最优解。 2) 如果最短路径长度为C*, 则在算法结束前，open 表中至少有一个节点n, 满足 f(n) <= C*. 这个性质可以这样理解， 因为最短路径存在， 我们不妨设它为: source->a->b->c->...->n->.....->goal. 且在当前时刻，路径中在节点n 前的节点都在closed 表中，即已经扩展了，而节点n 自己在open 表中（注意：算法结束前任意时刻都有这样的节点n 存在）。 则由于该条路劲是最短路径，我们可以知道此时在open 表中的n 的 g(n)值已经是准确值, 即最小值了。而 f(n) = g(n) + h(n) = g*(n) + h(n) <= g*(n) + h*(n) = C* . (最后一个式子取等号是由于n 在最短路径上) 有了这个性质，我们就知道，当A*算法扩展到目标节点时，必有f(goal) = g(goal) <= C* (即 = C*)。否则, 如果f(goal) > C*,由于目标节点是被扩展节点, 则open 表中其他任意其他节点t, 都有f(t) >= f(goal) > C*, 和性质1 矛盾。 3) 扩展新节点时很容易出现重复节点的问题，从上面的伪代码可以看出， 如果新 扩展节点已经存在于closed 表中， 且f 值比表中节点的f 值还要小的话，则除了更新该节点f 值，还需要重新扩展该节点，这简直就是把人从棺材里拖出来。 但是如果h 函数满足相容性，这一步就可以省掉了。所谓相容性就是指对任意节点s1,都满足： h(s1) <= h(s2) + c(s1,s2) (其中c(s1,s2)是指从s1转移到s2的代价)有这个性质我们在不等号两边加上g(s1), 则有 g(s1) + h(s1) <= h(s2) + g(s1) + c(s1,s2)。 如果我们此时扩展s1, 而s2又是能被s1扩展的节点，则由这个式子我们得到 f(s1) <= f'(s2). (若s2之前就已经被扩展出了，则当前的f(s2)可能比f'(s2)小) 这个式子的意义在于由当前节点进行扩展这个方案下得到的节点的f 值总比当前扩展节点的f 值大（子节点总比父节点
Business ! ·233· 机器人路径规划算法探讨 陈书光 作者简介：陈书光，（1980－），男，籍贯：河南省唐河县，汉族，学历：研究生，职称：讲师，研究方向：数据库技术、软件设计、 算法分析。 摘要：机器人路径规划问题被定义为一个障碍的工作环境中找到一个适当的从起点到终点的运动路径，机器人在运动过程中能安全无碰撞，绕过所有的障碍。屏障环境的机器人无碰撞路径规划是一个重要的研究课题，智能机器人，由于障碍物空间机器人运动规划的高度复杂性，使得这个问题一直没有得到很好的解决。路径规划问题的基础上，机器人的工作环境模型可以分为2类，一个是基于模型的路径规划，经营环境的整体的信息是可预测的；另一种是基于传感器的路径规划，环境信息完全未知或部分未知。 关键词：机器人路径规划算法一、本文就常见的几种常见的路径规划算法及应用进行简单的探讨如下： （一）遗传算法概念 遗传算法是根据达尔文的进化论，模拟自然选择的一种智能算法 ，“适者生存”是它的核心机制。遗传算法是从代表问题可能潜在解集的一个种群开始的。基于随机早期人口，根据的原则，优胜劣汰，适者生存，世代演化产生更好的人口大概。在每一代，根据问题域的个体适应度大小来选择个人，然后选定的个人在自然遗传学，遗传算子组合交叉和变异，产生代表性的解集的人口。通过这些步骤，后生代种群比前代对于环境具有更好的适应性。人口最优个体解码后可作为近似最优解。 （二）遗传算法的特点 作为一种智能算法，遗传算法具有如下特点：①遗传算法在寻优过程中，只把适应度函数的值作为寻优判据。②遗传算法是由一个问题集合（种群）开始的，而不是从一个个体开始的。故而遗传算法的搜索面积很大，适合全局寻优。③遗传算法根据概率性的变换规则进行个体的优胜劣汰并推动种群的进化。④遗传算法具有隐含的并行性。⑤遗传算法具有自组织、自适应以及内在的学习性，同时遗传算法具有很强的容错能力。⑥遗传算法的基本思想简单。对于复杂的和非线性的问题具有良好的适应性。 （三）遗传算法的应用 遗传算法提供了一个整体框架地址复杂系统问题，它不依赖于俞特定领域的问题，问题的类型、已是强的鲁棒性，所以广泛应用余许多科学：功能优化遗传算法的经典应用，是遗传算法的性能评价的常见的例子，许多人建设的各种复杂的表格功能测试：连续函数和离散函数，凸、凹函数、低维功能和高尺寸功能、单式功能和更多峰值函数。一些非线性、多模型、多目标函数优化问题和其他优化方法很难解决，GA 你可以更好的结果。增加问题的规模，搜索空间的组合优化问题，将会迅速增加，有时的当前枚举方法和计算很难找到最佳的解决方案。实践证明，遗传算法、组合优化问题的粒子非常有效。 二、蚁群算法及其应用（一）蚁群算法概念 蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo 于1992年在他的博士论文中提出，灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法。 （二）蚁群算法的特点 ①蚁群算法是一种自组织算法。在早期的算法，单一的人工蚂蚁障碍找到求解算法，久而久之，通过信息作用的激素，人工蚂蚁进化将找到一些解决办法更接近最优的解决方案，它是无序到有序的过程。 ②蚁群算法的并行算法是一种基本的。每个蚁群搜索进程 独立的对方，只能通过信息素通讯。因此，蚁群算法可以看作是一种分布式的多智能体系统，它在问题空间搜索算法开始是一个独立的解决方案，不仅提高了可靠性，这使得该算法具有强的全局搜索能力。 ③蚁群算法是一种积极的反馈的算法。从蚂蚁觅食中不难看到蚂蚁已设法找到最短路径的信息的过程取决于直接上的最短路径的积累，以及信息素的积累是一个积极的反馈过程。这种正反馈的过程进行初步的差距有不断扩大，并导致系统的最优解的方向发展。 ④蚁群算法具有较强的鲁棒性。比较与其他算法、蚁群算法、初始对齐要求不高，外务大臣蚁群算法用于路由和搜索过程的初步结果不需要手动调整。第二，设立简单、便于应用的蚁群算法求解组合优化问题的蚁群算法参数的殖民地，数目。 （三）蚁群算法应用 蚁群算法应用包括：二次分配问题、车间任务调度问题、车辆路线问题、机构同构判定问题、学习模糊规则问题、旅行社新旅游线路与旅行产品的制作等领域。 三、神经网络算法（一）神经网络的概念 人工神经网络也被称为神经网络连接模式，它是一种动物模型，神经网络的行为特征，分布式并行处理算法的数学模型。网络依赖于复杂的系统，通过调整内部之间的联系，大量节点，以实现节能的目的，信息处理。 特征的神经网络模型的人工神经网络的主要网络连接拓扑，神经元的特点，学习规则。目前，近40种神经网络模型，其中有一个BP 网络，传感器网络，自组织映射，神经，波尔兹曼机，自适应共振理论。系统的稳定性与联想记忆功能密切相关。 神经网络的应用 人工神经网络的非线性自适应信息处理能力，克服了传统人工智能方法的直觉，作为模型，语音识别，非结构化信息处理方面的缺陷，使神经网络专家系统，模式识别，智能控制，组合优化，预测等领域得到成功应用。人工神经网络和其他传统方法相结合，将促进人工智能和信息处理技术的发展。近年来，人工神经网络模拟人类认知方式更深入的发展，模糊系统，遗传算法，进化机制相结合，形成智能计算，人工智能，已成为一个重要的方向，在实际的应用开发。信息几何学应用于人工神经网络的研究，人工神经网络理论开辟了一条新的途径。 机器人路径规划算法有很多，可以说有优点和缺点，目前还没有一个算法可以应用于任何场合。因此，各种新的算法被提出，一方面丰富了解决问题的手段，不同的情况下都能找到一个合适的算法；另一方面也不断吸收新的理论，促进学科发展。一个很好的算法，理论深度不高，但其使用；相反，原理简单，计算效率的算法是更容易被接受，关键是看最后达到的效果。（作者单位：柳州城市职业学院）