logo资料库

rrt算法改进.doc

发布时间：2022-06-19 发布人：admin 分类：说明书 资料大小：0.14M 资料格式：doc 举报 版权申诉
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
资料共12页，剩余部分请下载后查看
    本科毕业设计开题报告 （2018 届） 论文题目 基于多目标搜索的机器人 路径规划研究 作者姓名 梁斌 指导教师 许金山 学科(专业) 物联网工程1401 所在学院 计算机科学与技术学院 提交日期 2018/03/09
    浙江工业大学本科毕业设计开题报告 基于多目标搜索的机器人路径规划研究 一、选题的背景 1.1 研究开发的背景 机器人是现代科技发展到一定程度的成果，其技术涵盖的领域有很多，在 门类上属于混合学科，它因为综合了当前世界上人工智能，控制自动化，电子 信息，机械制造等多个领域的最新研究成果，所以机器人科学代表科技发展的 巅峰，它不仅是人类智慧的结晶，还是当今世界科技最活跃的领域之一[1]。 对机器人的路径规划的研究源于上个世纪 60 年代，早期对机器人路径规划 的研究的方向主要在陆地上，不涉及水下及空中的研究，例如美国斯坦福研究 院的 Nilsson 等人研制的具备自主移动功能的机器人 Shakey[2]，其主要作为人 工智能研究的载体，目的是研究机器人在复杂环境下应用人工智能技术进行自 主推理、规划和控制；另外英国研究机器人 Hilare[3]。还有 Moravec 利用栅格 法构建的经典机器人地图 Stanford Cart[4]。另外，假肢机器人也有了很大的发 展，有多个设计版本，譬如美国通用电汽有限公司的思 腿式机器人 GE Quadrupe[5]，日本索尼公司生产的 Aibo[6]，本田公司的类人机器人 Asimo 等等。 1.2 国内外研究发展现状 机器人可研究的方向有很多，其中本文的主要研究的方向是路径规划。路 径规划可以分为局部规划和全局规划，其中全局规划的问题主要集中在如何解 决未知条件下的机器人路径规划[7]。现在国内外提出了很多方案，例如人工势 场法、随机采样算法、以及诸多启发式算法等。在最新的成果里，人们对原有 的算法的缺陷进行了许多改进并提出了诸如仿生算法的新算法[8]。路径规划算 法已经趋于复杂化与智能化。 就国内外现状来看，按搜索策略和和搜索环境来分类，有以下三种主要的 路径规划方法： 1. 前向图搜索算法 2. 几何构造的规划算法 2
    浙江工业大学本科毕业设计开题报告 3. 随机采样的规划算法 前向图搜索算法 前向图搜索算法分为贪心算法 Dijkstra 算法、A* 算法、D* 算法等几个方 面，下面分别进行介绍 。 1. 贪心算法 贪心算法[9]是一种经典的路径搜索算法，属于局部规划的范畴，其具体算法 是只考虑当前环境信息，不考虑全局信息，从起点开始只在局部范围内寻找最 短路径，每一步只考虑一个数据。该算法最大的优点是算法简单易于实现，最 大的缺点是只考虑局部最优解往往不能得到整体的最优解，导致算法无法收敛， 最终路径规划失败。贪心算法在路径规划中最经典的运用就是 Dijkstra 算法。 2.Dijkstra 算法 Dijkstra 算法[10] 是一种运用贪心思想的经典最短路径搜索算法，主要思想 为从图的起点开始，依次访问图中的结点。它每求得一个最短路径就把该节点 加入集合 S 中，在未确定的最短路径的节点中，按长度大小依次排列，加入 S， 再加入过程中必须保证从源点 v 到 S 中各顶点的最短路径长度不大于从源点 v 到 U 中任何顶点的最短路径长度，直到所有节点遍历完。只要所有的边都有一 个非负的权，Dijkstra 算法就一定能找到一条从起点到目标点的最短路径，广泛 应用在最短路径搜索问题中。 3.A* 算法 A* 算法[8] 是一种通过运用启发式函数的搜索算法，根据每次的启发函数 不同，得到的规划路径也不一样。A* 算法的缺点是由于每次规划的路径不同， 不适合机器人的重复性任务，并且面对复杂环境或者高维位姿空间是时，算法 的计算量会呈指数上升，效率过低，不适合实际情况。 几何构造的规划算法 几何构造的规划算法主要有可视图法[11]、栅格法[12]. 1. 可视图法 该算法的思想是把机器人看做物理学中的质点，忽略其大小和形状，然后 连接机器人，目标点，起点和障碍物的各个顶点，同时要求连线避开接触障碍 物，则所有连线形成的图形成为可视图。 3
    浙江工业大学本科毕业设计开题报告 2. 栅格法 该算法的基本思想是把机器人的活动空间分成许多大小相同的栅格，然后 用 0 来代表非障碍物坐在的空间，1 来代表障碍物所在的空间[13]，于是机器人 通过识别每个栅格上的信息来隐形移动并且避开障碍物。 随机采样的规划算法 1. 随机势场规划器 随机势场规划器[14] 的思想和人工势场法类似，只是通过引入最小随机变量 来克服人工势场法在局部搜索的缺陷。 2. 概率路标算法 概率路标算法[15] 的基本思想是通过在自由空间中的不断采样来生成随机 路标，然后在通过查询这些随机路标的连通性来规划出一条合理的路径。当空 间的约束有微分时，其对采样点计算复杂度为非线性的，此时概率路标算法的 表现会很差，因此它只适合在无微分约束的环境下工作。 3. 快速随机搜索树算法 快速随机搜索树算法（RRT）的基本思想是在初始化的位姿空间中，以起 点为随机树的根节点构造，构造的方法是在位姿空间的任意位置选取一个随机 点，然后从已知的随机数种选取距离该随机点最近的的节点，若二者的连线上 没有发生障碍物的碰撞，则根据机器人的不成 eps 构造一个新节点，直至随机 树扩展到目标点。快速随机搜索树算法是 S. M. La Valle 结合非完整性约束以 及最优控制等相关技术而提出的[16]。RRT 算法在处理分完整路径规划问题有着 相当大的优势，因为它可以将各种约束集成到算法本身之中，因此对环境的要 求就比较低。该算法效率高，速度快。可以直接在分完整系统中加以应用。随 机性事该算法的固有属性，所以该算法概率完整。也就是说理论上肯定能够找 到可行路径。 本文的研究方向就是基于传统 RRT 算法的改进优化，尽管传统 RRT 算法一 定能找到一条起点到终点的路径，但往往不是最优的，通常偏离最优路径较多， 且搜索时间过长。现在国内外已经有了几种 RRT 的改进： 1. 基于采样策略的改进：偏向目标的 RRT 算法[17] 是在原有 RRT 算法基 础上，通过设置概率函数，让目标点以一定的概率作为采样点出现，这样所有 4
    浙江工业大学本科毕业设计开题报告 的采样点就会主要集中在路径两侧附近，避免了对过多无效空间的采样计算， 大大减少了计算量并且加快了了算法收敛的速度。 2. 基于扩展方式的改进：利用点的复用思想，在起点和目标点同时构造两 棵随机树，每出现一个采样点，就同时在两棵随机树上构造新的节点，利用 MATLAB 进程并发原理，可以使得两棵树并行相向生长，直到两棵树相交，即 找到了一条合理路径。 5
    浙江工业大学本科毕业设计开题报告 二、研究开发的目标，基本内容和技术难点 2.1 研究目标 传统 RRT 算法相比其他路径规划方法，例如遗传算法，人工势能算法，网 格算法等有着较多的优势。尽管如此，但它依然存在很多缺点和问题，例如虽 然理论上总能找到一条路径，但它不是最优的，且搜若时间可能过长，花费代 价过大等等问题。 虽然已经提出了偏向目标的 RRT 和双向 RRT 算法，它们在一定程度上解 决了传统 RRT 存在的问题：加快了算法收敛速度，使得规划的路径更加接近最 优路径；通过双向生成随机树，实现节点的复用，大大加快了找到路径的速度， 同时降低了花费。但是这些改进都是在理想环境下的改进，在理论上可行，但 是没有考虑实际应用下问题： 1. 搜索目标单一，实际可应用的场景较少。 2. 不考虑外界环境因素，实际环境下由于外界的干扰，随机树的生长过程 中会受到一定的影响，偏离理论路径，甚至找不到路径。 本文在解决该算法的传统缺点的的基础上，对 RRT 算法的功能进行了优化。 2.2 研究的基本内容 本研究的具体容包括： (1) 实现多目标搜索 传统 RRT 搜索是针对单一目标的搜索，我们在此基础上增加多个目标，让 机器人在避开障碍物的同时，按照要求达到到达指定的目标，实现更多的功能。 (2) 引入各种场的概念，实现复杂环境下的搜索 现有的 RRT 算法只是在理论上可以找到一条无碰撞的路径，并没有考虑到 实际的环境因素，而在实际应用中各种复杂的环境的因素往往会导致路径搜索 的失败。因此，我在原有算法的基础上，通过设计合适的代价函数来引入各种 场，模拟复杂环境下的路径搜索。 2.3 需要解决的技术难点 1.如何构造合适的树的生长方式，实现多目标的搜索。怎样利用节点的复 6
    浙江工业大学本科毕业设计开题报告 用实现进程的并发。 2.如何设计合适的代价函数，描述环境因素的影响。 三、研究开发的平台、技术路线 (1) 系统平台： Windows 10 (2) 编程语言及平台：MATLAB 为了建立各种所需的工作环境空间，本文利用MATLAB2014开发设计了一个 仿真实验环境平台[19]。在设置障碍物形状、大小及位置方面，该平台的表现很好。 另外，该平台还提供了一个开放的算法接口，以便于将仿真实验环境平台应用于 各类型的路径规划算法，拓展了平台的使用范围。但该平台还存在些许不足，如 它只能简单地绘制所需的工作环境空间。 同时MATLAB语言自身的优点适合我提出的算法的改进。MATLAB语言精 通数学，可以在编程中直接使用矩阵和数组，为设置障碍物的参数和避障的测试 提供了便利。它的绘制图形功能强大，使的仿真测试的结果直观的反映出算法的 优缺点。 （3）技术路线 多目标搜索：仿照双向RRT的随机树的生长方式，在起点和多个目标点同时构造 多个随机树，如图1所示，图中准备以Q.start,Q.end1,Q.end2为起点分别构造三棵 树，其中Q.end1,Q.end2为目标点，Q.start为起点，实现双目标搜索，在已知空间 中，取随机点Q.rand,分别寻找三棵树中距离该随机点最近的节点Q.near,通过代价 函数在Q.rand和Q.near的连线上构造Q.new,直至三棵树汇合，任务完成。注意在 生长过程中要区分起点构造的随机树和目标点构造的随机树，注意当有两棵树汇 合时要判短是起点构造的随机树和目标点构造的随机树汇合还是多个目标点构 造的随机树交叉。 7
    浙江工业大学本科毕业设计开题报告 图 1多目标搜索示意图 复杂环境：传统RRT的代价函数就是计算机器人从Q,near到Q.rand前进步长eps （机器人以速度为v0以1s前进的距离为步长eps）所需的时间t0，该时间为固定值。 为模拟复杂环境，引入场的概念，设计出一个动态的代价函数，如图2所示，设 机器人速度为v0，假设此时场强的方向为正东方向，设速度为v1,由于有场的影响 会导致前进方向偏离Q,near到Q.rand的方向，因此需要调整前进方向，使得合成 后的速度v在Q,near到Q.rand的方向上，然后计算前进步长eps的时间t（eps/v）, 即为新的代价。 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    人工智能

    共收录2047份资料，累计62个分类，关注成员有19位，主要包括：GNSS,Pico-SIM868-GSM,GPRS,NB-IoT,GPRSHAT,SIM7070GCat-M,GNSSHAT,GSM,NB-IoTHAT,SIM7080GCat-M,R800CGSM,SIM800CGSM,UPSPowerModule(B),UPSPowerModule,Pico-SIM7020C-NB-IoT,SIM7028NB-IoTHAT,SIM7020CNB-IoTHAT,SIM7000XNB-IoTHAT,A7670CCat-1HAT,A7600C1Cat-1,SIM7600X4G&LTECat-1HAT,SIM7600X4GDONGLE用户手册,RM520N-GL5GHAT,RM500Q-GL5GHAT,RM500U-CN5GHAT,SIM820X-M25GforJetsonNano,AudioCardforJetsonNano,SIM7600G-H4GforJetsonNano,OpenNCC-Lite-4G8M,IMX219-77Camera,13.3inche-PaperHAT,10.3inche-PaperHAT(D),10.3inche-PaperHAT,9.7inche-PaperHAT,7.8inche-PaperHAT,6inchHDTouche-PaperHAT,6inchHDe-PaperHAT,6inche-PaperHAT,5.83inche-PaperHAT(C),LCD-Clock-A,0.95inchRGBOLED(A),0.96inchRGBOLEDModule,0.96inchOLEDModule,0.96inchOLED(A),1.27inchRGBOLEDModule,1.3inchOLEDModule(C),1.3inchOLED(A),1.32inchOLEDModule,1.5inchRGBOLEDModule,1.5inchOLEDModule,JETSONORINNX,自然语言处理,搜索引擎,VR,计算广告,深度学习,机器学习

    热门标签

    GNSS Pico-SIM868-GSM GPRS NB-IoT GPRSHAT SIM7070GCat-M GNSSHAT GSM NB-IoTHAT SIM7080GCat-M R800CGSM SIM800CGSM UPSPowerModule(B) UPSPowerModule Pico-SIM7020C-NB-IoT SIM7028NB-IoTHAT SIM7020CNB-IoTHAT SIM7000XNB-IoTHAT A7670CCat-1HAT A7600C1Cat-1 SIM7600X4G&LTECat-1HAT SIM7600X4GDONGLE用户手册 RM520N-GL5GHAT RM500Q-GL5GHAT RM500U-CN5GHAT SIM820X-M25GforJetsonNano AudioCardforJetsonNano SIM7600G-H4GforJetsonNano OpenNCC-Lite-4G8M IMX219-77Camera 13.3inche-PaperHAT 10.3inche-PaperHAT(D) 10.3inche-PaperHAT 9.7inche-PaperHAT 7.8inche-PaperHAT 6inchHDTouche-PaperHAT 6inchHDe-PaperHAT 6inche-PaperHAT 5.83inche-PaperHAT(C) LCD-Clock-A 0.95inchRGBOLED(A) 0.96inchRGBOLEDModule 0.96inchOLEDModule 0.96inchOLED(A) 1.27inchRGBOLEDModule 1.3inchOLEDModule(C) 1.3inchOLED(A) 1.32inchOLEDModule 1.5inchRGBOLEDModule 1.5inchOLEDModule JETSONORINNX 自然语言处理 搜索引擎 VR 计算广告 深度学习 机器学习

    最新资料