精华内容
下载资源
问答
  • 无人驾驶常用路径规划

    万次阅读 多人点赞 2019-01-05 16:54:15
    无人驾驶系统介绍行为决策运动轨迹规划路径规划的不同之处路径规划的定义路径规划方法全局路径规划Dubins路径方法Dubins路径改良算法局部路径规划模糊逻辑算法基于行为的路径规划算法基于再励学习的路径规划算法基于...

    无人驾驶系统介绍

    无人驾驶系统非常复杂,由多个模块组成,例如感知、融合、规划、控制、定位等等组成。其中规划主要包括行为决策、运动轨迹规划等等。
    自动驾驶子系统结构图

    行为决策

    行为决策是人们在行动之前按照某些行为准则在若干可行备选方案中选择或判断某种最佳行动方案的思维活动。
    行为决策系统根据驾驶员的任务请求以及车辆的行驶状态和环境感知信息,对任务进行优先级排序,对车辆的驾驶行为,包括换道、超车和躲避障碍物等进行决策,并将行为决策的结果传给运动轨迹规划系统。

    运动轨迹规划

    运动轨迹规划系统根据行为决策的结果以及车辆的行驶状态和环境信息,考虑时间因素,规划出车辆的行驶轨迹。规划的轨迹包括和时间相关的速度、加速度、行驶时间、燃油消耗量等状态和控制量,并将轨迹信息传给运动控制系统,运动控制系统接收到规划轨迹的详细信息以后,对车辆的姿态进行控制使其沿着规划轨迹进行循迹行驶,以达到对智能车辆自动控制的目的。
    规划和控制系统

    运动轨迹规划是运动控制的前提。因此,要对某种驾驶行为实施控制,首先要根据车辆的行驶状态和道路信息规划出期望的运动轨迹,并从中提取需要的轨迹参数提供给后续跟踪控制器,以便于控制器能够控制车辆按照规划的轨迹行驶。
    运动轨迹规划一般首先生成路径,然后在路径的基础上考虑时间因素及车辆的运动学和动力学模型,通过平滑和速度规划等步骤得到开环的运动轨迹。但是对车辆沿着规划轨迹行驶的稳定性分析也存在一定的困难,即运动控制能否控制车辆准确地沿着规划轨迹行驶而不发生侧滑或侧翻等达不到行驶稳定性要求的问题。

    路径规划的不同之处

    运动轨迹规划与路径规划是有所区别的,路径规划主要是生成从起点到终点不发生碰撞的静态几何轨线,不包含时间概念;而轨迹规划考虑时间因素,生成的不仅是轨迹,还包括车辆行驶速度、加速度、行驶时间和燃油消耗量等状态和控制参数。
    车辆运动控制的主要任务是利用对车辆速度和方向的控制实现车辆位姿对规划轨迹的快速跟踪,并对车辆沿着规划轨迹行驶的状态和控制参数的响应参数进行闭环反馈,使得车辆能够准确沿着规划轨迹进行循迹行驶。

    路径规划的定义

    路径规划方法是在障碍物环境下,按照一定的评价标准规划出一条从起始状态(位置,姿态)到目标状态的无碰路径,主要考虑局部移动主体和障碍物之间的几何关系,找到一条不发生碰撞的路径。路径是一条静态的几何轨线,不包含时间概念,通常表示智能车辆在笛卡尔坐标下的位置和姿态关系。
    根据智能车辆对环境信息掌握的程度,路径规划可以分为两种:

    1. 环境信息完全已知的全局路径规划
    2. 环境信息完全未知或部分未知,通过传感器在线对智能车辆的行驶环境进行感知,以获取障碍物的位置形状和尺寸等信息的局部路径规划

    路径规划方法

    在无人驾驶或者机器人路径规划总,路径规划其实在广义上分为两种:

    1. 全局路径规划–这种路径规划就跟你在高德地图上的导航一样,规划了全局范围的、从起点到终点的行驶路径
    2. 局部路径规划–在全局路径规划的基础上,当你想要躲避障碍物、变道、超车等等操作时,就会涉及到局部路径规划技术,通过局部路径规划,可以使得无人驾驶汽车更加平稳的度过这些操作

    全局路径规划

    全局路径规划方法有 Dubins 路径及其改进算法、可视图法和单元分解法等方法。

    Dubins路径方法

    Dubins路径是生成光滑路径最常用、最广泛、最出名的一种方法。其表示机器人向前行驶的最短路径,通过两个圆弧和直线段组成,其中直线段部分是对应的圆弧的切线。
    但是这个方法有个很大的缺点,那就是在圆弧和直线的连接点处不连续,如果想要精确按照预先设定好的路径行驶,就必须要在连接点处停下来,然后原地转弯,再开始行驶。这对于无人驾驶来说,是完全无法接受的!!

    Dubins路径改良算法

    后来Scheuer等大佬在Dubins路径规划算法上进行了改良,使得行驶路径由原来的圆弧+直线变成了圆弧+直线段+CC(Continous Curvature)转向路径 ** 3段组成,圆弧和直线段之间使用CC转向路径进行相连,这样就避免了路径在连接点处不连续,需要原地停下来转向的尴尬出现。
    CC转向路径是一种特殊的螺旋曲线,它的曲率随着曲线长度的变化而变化,但是
    曲率一直是连续变化的**。但是其生成的路径在长度上有可能就不是最短的了,而且生成的路径曲线的坐标(x,y)无法直接闭环来表示,只能通过对曲线长度s进行积分得到,计算成本较大。

    局部路径规划

    局部路径规划有人工势场法、模糊逻辑算法和基于行为的路径规划算法等方法。

    模糊逻辑算法

    模糊逻辑算法主要是对驾驶员的驾驶经验进行模拟,将驾驶员生理上的感知和行为动作进行结合,然后根据传感器提供的信息,通过查表可以得到规划轨迹的信息。
    该算法最符合人类的思维习惯和行为特点,能够很好的体现出跟人驾驶行为上的一致性。但是由于太过于模糊的设计函数,导致该方法主要依赖人的经验和试验,总结、量产十分困难。且一旦模糊规则制定后,再次想要调整起来困难重重。因此业界的主要用法都是讲其余其他逻辑方法相结合使用。

    基于行为的路径规划算法

    基于行为的路径规划算法是把机器人需要完成的任务进行分解成一些简单的行为单位,机器人根据行为的优先级以及需要完成任务作出适当的反应。
    但是由于是对任务进行了分解,所以对于不同的行为来说需要完成不同的目标,不同的行为之间经常会产生冲突。此时就需要使用仲裁机制来对这些行为进行仲裁协调,谁先谁后。落实到具体操作上时,同一时刻只能有一个行为或者任务在被执行,行为按照不同的执行顺序组合成了一个完整的任务。
    该方法实时性很强,且非常灵活,但是缺点是在多种行为模式下,它的系统对于正确判断的概率会降低。

    基于再励学习的路径规划算法

    基于再励学习的路径规划算法来源于行为心理学,用动物学习心理的“试错法”原理,对机器人在未知环境中移动的路径进行规划。
    此方法利用评价性反馈信号在与环境的交互反馈中进行学习,为实现智能系统的自学习能力提供有效手段。由于再励学习不需要先验知识和环境模型,也不需要样本训练数据,主要是通过与环境的直接交互进行学习,能够在线实现,所以对环境模型不确定的系统比较适用。但是此算法由于需要与环境进行直接交互,计算量较大

    基于仿生学的路径优化算法

    该方法准要是模拟一些生物上的生理特点进行的算法,如遗传算法、CNN、蚁群优化、栗子滤波等等。

    展开全文
  • 目前常用的路径规划方法可以分为传统算法和智能仿生算法两类。 图 1‑1 路径规划方法的分类 传统算法主要有人工势场法、模糊逻辑算法、可视图法、栅格法、自由空间法等。自 20世纪70年代路径规划问题被提出以来,...

    智能仿生算法在机器人路径规划的应用综述

    1 绪论

    1.1 机器人路径规划方法

    路径规划是移动机器人导航中最重要的技术之一。

    对于移动机器人而言,路径规划就是解决特定工作环境和任务要求下的路径优选问题,路径规划的科学性和合理性对于移动机器人工作效能具有十分重要的影响。

    目前常用的路径规划方法可以分为传统算法和智能仿生算法两类。

    图 1‑1 路径规划方法的分类

    图 1‑1 路径规划方法的分类

    传统算法主要有人工势场法、模糊逻辑算法、可视图法、栅格法、自由空间法等。自 20世纪70年代路径规划问题被提出以来,这些传统算法在机器人路径规划领域发挥了重要的作用,取得了诸多研究成果。

    但是随着移动机器人应用领域的不断扩大,传统的路径规划方法在应对一些复杂环境时会存在一定的缺陷[1]。例如,人工势场法容易陷入局部极小点,存在目标不可达的问题。模糊控制算法在复杂多变环境中,很难建立模糊规则库,且对于动态障碍物缺乏智能的避障策略。

    而随着近年来人工智能技术的兴起,越来越多智能仿生算法被提出并应用在机器人路径规划中,其中许多智能仿生算法有着比传统算法更加优秀的效果,因此针对越加复杂的路径规划场景,智能仿生算法脱颖而出。

    1.2 智能仿生算法主要特点

    智能仿生算法是一种模仿生物群体智能行为或生物体结构和功能或生态机制的智能计算方法。

    智能仿生算法的主要特点有:

    1) 仿生特征

    智能仿生算法的工作机制与自然生物的性质或生态机制非常接近。

    2) 简单性和涌现

    智能仿生算法计算简单且容易理解,但其效果非常惊人,反映了涌现性。

    3) 鲁棒性

    智能仿生算法对环境,参数和任务的变化具有很强适用性和灵活性。

    4) 自组织性

    智能仿生算法可以通过自学习或自组织的方式提高自适应能力。

    1.3 智能仿生算法分类

    根据智能仿生算法的模仿来源,这里将其分为三大类,分别为:

    1. 受生物群体行为启发的智能仿生算法;

    2. 受生物体结构、组织启发的智能仿生算法;

    3. 受生物进化启发的智能仿生算法。

    下图为智能仿生算法的三大分类下的具体算法,在后文将针对每类智能仿生算法进行展开介绍。

    在这里插入图片描述

    图 1‑2智能仿生算法分类

    2 受生物群体行为启发仿生算法

    2.1 受生物群体行为启发仿生算法概述

    在自然界中,生物个体的行为往往只能完成较为简单的任务,但个体直接通过群体协作却能完成复杂的任务。针对生物群体行为的特性,学者们提出了众多受生物群体行为启发的智能方式算法,如蚁群算法、粒子群算法、人工鱼群算法以及狼群算法等等。通过算法模拟生物群体行为,能够有效应用在各自实际优化问题中,下文将以粒子群算法为例进行阐述。

    2.2 粒子群算法概述

    粒子群算法(particle swarm optimization,PSO)最初是由Kennedy和Eberhart博士于1995年受人工生命研究的结果启发,在模拟鸟群觅食过程中的迁徙和群集行为时提出的一种基于群体智能的演化计算技术。

    粒子群算法起源于对飞行鸟群觅食行为的研究。在鸟群捕食的时候,当有一只鸟发现不远处的食物后,它将飞向食物地点,这将导致它周围的其它鸟也沿着这个方向寻找食物地点,直到整个鸟群全部降落在此,找到食物。这是一种自然状态下的信息共享机制,在认知和搜寻过程中,个体会记住自身的飞行经验;同时,也向其它优秀个体学习,当它发现其它的某个个体飞行更好的时候,就会向它学习并对自身做出适当的调整,使得自己能朝着更好的方向飞行。

    该算法具有并行处理、鲁棒性好等特点,能以较大概率找到问题的全局最优解,且计算效率比传统随机方法高。其最大的优势在于编程简单,易实现、收敛速度快,而且有深刻的智能背景,既适合科学研究,又适合工程应用。因此,粒子群算法一经提出,立刻引起了演化计算领域研究者的广泛关注,并在短短几年时间里涌现出大量的研究成果,该算法目前已被“国际演化计算会议”列为讨论专题之一。

    粒子群算法的迭代公式如下,包括速度和位置公式:

    在这里插入图片描述

    ​ 其中各参数的含义如下:

    ViV_i,d:第 i 个 粒子 (d个维度) 的速度

    ww:惯性权重

    c1c_1,c2c_2:学习因子,用来调控算法的局部收敛性

    r1r_1,r2r_2:0-1之间均匀分布的随机数,增加种群多样性

    PiP_i,d:每个粒子到目前为止所出现的最佳位置

    PgP_g,d:所有粒子到目前为止所出现的最佳位置

    XiX_i,d:每个粒子目前的所在位置

    各参数中,惯性权重作为粒子运动速度的系数,控制着粒子飞行速度的变化;同时也具有平衡算法的全局搜索能力和局部搜索能力的作用。

    从速度迭代公式可知,粒子的下一代速度与自己本代速度的惯性、个体最优解、全局最优解有关。整体体现出初期时全局搜索能力较强,后期局部搜索能力较强的特点。

    2.3 粒子群算法的优缺点

    粒子群算法具有以下优缺点:

    优点:收敛速度快、设置参数少、实现简单。

    缺点:易陷入局部最优解、后期收敛速度缓慢。

    2.4 粒子群算法在机器人路径规划上的应用

    水面无人艇(USV,Unmanned Surface Vehicle)属于自主式海洋运载器,其优势是在不适合载人船艇或者危险情况下执行任务。无人艇具有智能化、模块化、体积小、无人、高速、机动灵活、适应各种气候环境、性价比高等优势,不难看出海面无人艇将在海洋的探索和开发利用中,以及在未来可能的海上冲突等军事的应用中起到不可忽视的作用。

    在水面无人艇的研究和应用课题中,智能化将是其发展的一个重要方向。

    在《水面无人艇局部危险避障算法研究》[2]中,作者引入了启发式知识对粒子群路径规划算法的路径进行初始化,使得初始化生成的路径上下颠簸幅度减少,同时可保证粒子群随机分布在较为合理的搜索空间中;并对最终产生的路径进行路径平滑优化处理,有效缩短了解算最优解的耗时,减少了航行转向点数,得到更优的路径解,提高了算法的可行性和有效性。

    在这里插入图片描述

    图 2‑1 水面无人艇局部危险避障图示

    3 受生物体结构、组织启发仿生算法

    3.1 受生物体结构、组织启发仿生算法概述

    每种生物都是由细胞组成,这些细胞通过不同的排列组合形成了各种生物体结构与组织,并让生物能够实现各种不可思议的功能。针对生物体结构与组织的特性,学者们提出了众多受生物体结构与组织启发的智能方式算法,如人工神经网络算法、人工免疫系统算法以及DNA计算算法等等。通过算法模拟生物体结构与组织,能够有效应用在各自实际优化问题中,下文将以人工神经网络算法为例进行阐述。

    3.2 人工神经网络算法概述

    人工神经网络算法(artificial neural network,ANN)主要原理是模拟人脑的生物神经系统,网络由大量具有非线性映射能力的神经元组成,神经元之间通过权重系数相连接,可以进行大规模的信息处理[3]。

    下图中展示的便是人工神经网络的输入层、隐含层和输出层,以及神经元之间的权重系数连接关系。

    在这里插入图片描述

    3‑1 人工神经网络的组成及传递方式

    通过这样的神经网络结构,再结合相应训练算法与激活函数,使得人工神经网络可以进行大规模的信息处理,能解决众多传统算法所无法解决的动态问题。

    3.3 人工神经网络算法的优缺点

    人工神经网络算法具有以下优缺点:

    优点:具有较强的非线性映射能力、具有自学习与自适应能力。

    缺点:训练时间长、易陷入局部极小值、收敛速度慢。

    3.4 人工神经网络算法在机器人路径规划上的应用

    在《基于模糊神经网络算法的机器人路径规划研究》[4]中,便融合了神经网络的并行处理与自学习能力以及模糊理论的模糊推理功能应用在机器人路径规划上。

    无人机的飞行路线规划一直被认为是一项至关重要的任务。本文主要利用了人工神经网络的快速拟合特性以及遗传算法的全局收敛优势,提出了一种基于遗传算法和人工神经网络相结合的无人机避障路径规划的新方法。

    融合了神经网络的并行处理与自学习能力以及模糊理论的模糊推理功能,在模糊理论和神经网络的基础上提出了模糊神经网络,使得各自的优点被充分利用在机器人路径规划上。

    4 受生物进化启发仿生算法

    4.1 受生物进化启发仿生算法概述

    在生物学中,进化是指种群里的遗传性状在世代之间的变化。自然选择使得有利于生存和繁殖的遗传特性变得更加普遍,而有害特性变得越来越少。受到这些复杂的生命进化过程的启发,学者们提出了一些进化算法,如遗传算法,差分计划算法、入侵杂草算法和生物地理学优化算法等。通过算法模拟生物进化形式,能够有效应用在各自实际优化问题中,下文将以遗传算法为例进行阐述。

    4.2 遗传算法概述

    遗传算法(genetic algorithms,GA)是 Holland 教授在20世纪70年代初期提出来的,基于“适者生存”的一种高度并行、随机、自组织和自适应的仿生优化算法。遗传算法的主要原理是:以生物进化论和遗传变异论为基础,通过模仿自然界生物进化机制达到全局搜索和寻优的目的[5]。

    遗传算法主要通过下述三个步骤进行算法优化[6]:

    1. 选择(selection)

    选择操作是从前代种群中选择多对较优个体,一对较优个体称之为一对父母,让父母们将它们的基因传递到下一代,直到下一代个体数量达到种群数量上限。

    1. 交叉(crossover)

    两个待交叉的不同的染色体(父母)根据交叉概率按某种方式交换其部分基因。

    1. 变异(mutation)

    染色体按照变异概率进行染色体的变异。

    4.3 遗传算法的优缺点

    遗传算法具有以下优缺点:

    优点:具有全局寻优能力与内在并行性。

    缺点:收敛速度慢且易陷入局部最优。

    遗传算法在机器人路径规划上的应用

    针对具有多个优化目标的机器人全局路径规划问题,《多目标遗传算法在机器人路径规划中的应用》[7]提出一种改进的多目标优化遗传算法。在初始群体的生成,采用把随机法和基于问题先验知识的启发式方法相结合的策略,以加快收敛速度;在遗传算子的设计中,引入删除、修复和平滑算子,以提高算法的搜索效率;在选择算子中,加入避免外部存储器中出现相同个体的机制,以防止早熟收敛。仿真结果表明:该文算法运行一次能够有效地产生一组近似Pareto最优路径解。

    5 总结

    智能仿生算法在路径规划的优化效果对比

    综合上文所述,每种智能仿生算法都有自身的优缺点,本文综合智能仿生算法的三大类别,列出下表所述各经典智能仿生算法的优缺点。

    表 5-1 仿生算法在路径规划的优化效果对比

    类别 智能仿生算法 优点 缺点
    受生物群体行为启发 蚁群算法 具有较强的鲁棒性; 较强的全局寻优能力 收敛速度慢;收敛精度低; 易陷入局部最优
    粒子群算法 早期收敛速度快; 设置参数少; 实现简单 后期收敛速度慢; 易陷入局部最优
    生物体结构或组织启发 人工神经网络算法 较强的非线性映射能力; 自学习与自适应能力 训练时间长; 易陷入局部极小值; 收敛速度慢
    人工免疫算法 局部搜索能力较强 参数较多; 计算成本过高
    受生物进化启发 遗传算法 具有全局寻优能力; 内在并行性 收敛速度慢; 易陷入局部最优
    入侵杂草算法 易于理解; 良好的自适应性; 强鲁棒性 易陷入局部最优; 收敛精度低

    智能仿生算法在路径规划的未来发展

    基于各智能仿生算法的优缺点分析,可以见得大部分智能仿生算法虽然具有一定成效,但依旧存在一定问题,本文针对智能仿生算法在机器人路径规划上的应用,提出了下述五点发展方向供读者参考。

    1) 新的智能仿生算法的应用

    所谓新的智能仿生算法包含两层含义:一是新算法在新领域的应用;二是开发未提出的智能仿生算法。

    2) 混合智能仿生算法的应用

    根据 NFL 定理(no free lunch-最优化理论),单一的智能仿生优化算法都有其自身的优缺点,算法之间存在互补性,不存在占绝对优势的算法。

    3) 在多机器人路径规划中的应用

    随着移动机器人应用的场合越来越多,单机器人在有些条件下已经不能满足使用要求,这就需要在多个机器人之间进行合作和协调。

    4) 在仿生机器人运动规划上的应用

    目前仿生机器人多采用传统的运动规划方法,这使得仿生机器人对复杂环境的适应能力不足,无法真正模拟生物实现精确的定位和灵活的运动。

    5) 在高维复杂环境下的路径优化应用

    人类迫切需要机器人在高维复杂环境中去完成更具有挑战性的任务,而目前大部分智能仿生算法很难适应环境和约束条件的动态变化,因此加强智能仿生算法在高维复杂环境下的路径优化应用也十分有必要。

    参 考 文 献

    [1]. 于振中,李强,樊启高.智能仿生算法在移动机器人路径规划中的应用综述[J].计算机应用研究,2019,36(11):3210-3219. DOI:10.19734/j.issn.1001-3695.2018.07.0483.

    [2]. 宋利飞.水面无人艇路径规划及自主避障方法研究[D].湖北:武汉理工大学,2015. DOI:10.7666/d.D794355.

    [3]. network [C]// Proc of the 32nd Chinese Control Conference. Xian, 2013: 3222-3226. )

    [4]. Singh M K, Parhi D R. Path optimisation of a mobile robot using an artificial neural network controller [J]. International Journal of Systems Science, 2011, 42 (1): 107-120.

    [5]. Flexible Muscle-Based Locomotion for Bipedal Creatures In ACM Transactions on Graphics, Vol. 32, Nr. 6 (Proc. of SIGGRAPH Asia 2013)

    [6]. Wolpert D H, William G M. No free Launch theorems for optimization [J]. IEEE Trans on Evolutionary Computation, 1997, 1 (1): 67-82.

    on for Bipedal Creatures In ACM Transactions on Graphics, Vol. 32, Nr. 6 (Proc. of SIGGRAPH Asia 2013)

    [6]. Wolpert D H, William G M. No free Launch theorems for optimization [J]. IEEE Trans on Evolutionary Computation, 1997, 1 (1): 67-82.

    [7]. 申晓宁,郭毓,陈庆伟,等.多目标遗传算法在机器人路径规划中的应用[J].南京理工大学学报(自然科学版),2006,(06):659-663.

    展开全文
  • 分析了自主移动机器人路径规划中的常用的几种方法,对于学习机器人路径规划很有价值。
  • 常用的地图导航和路径规划算法

    万次阅读 2018-12-06 19:27:31
    作者:李传学 ...明确一点,基本图搜索算法dijkstra是无法满足互联网地图检索实时响应这种性能要求,所以各家公司都有各自预处理方法:分层或者预计算。具体采用何种方式,这取决于采取加速算法相...

    作者:李传学
    链接:https://www.zhihu.com/question/24870090/answer/73834896
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
     

    明确一点,基本的图搜索算法dijkstra是无法满足互联网地图检索实时响应这种性能要求,所以各家公司都有各自的预处理方法:分层或者预计算。具体采用何种方式,这取决于采取的加速算法相关。在2008年前后,以KIT(http://algo2.iti.kit.edu/routeplanning.php)为主的研究院产出了多个路径规划加速算法,其中以contraction hierarchies 和 highway hierarchies较出名,加之微软研究院提出的Customizable Route Planning,与传统的A-star,基本上支撑了目前工业界地图产品的路径规划服务。

    A-star:https://en.wikipedia.org/wiki/A*_search_algorthm

    CH:http://algo2.iti.kit.edu/schultes/hwy/contract.pdf

    HH:http://algo2.iti.kit.edu/documents/routeplanning/esa06HwyHierarchies.pdf

    CRP:http://research.microsoft.com/pubs/145688/crp-sea.pdf

    展开全文
  • 自动驾驶路径规划实用搜索技术 Frenet框架中动态街道场景最优轨迹生成 控制 推荐材料 纯追求路径跟踪算法实现 自主汽车路径跟踪自动转向方法 Stanley:赢得DARPA大挑战赛机器人 ApolloAuto / apollo...
  • 本发明涉及路径规划技术,具体涉及基地图路径规划方法。背景技术:随着各项性能提高,服务机器人可以在人们日常生活中完成越来越多 任务,比如打扫卫生、移动物体等等。为了使任务完成得更加流畅,机器人必 须...

    a9b2ba18fb20c8981f8183b7460e038f.gif

    本发明涉及路径规划技术,具体涉及基地图路径规划方法。

    背景技术:

    随着各项性能的提高,服务机器人可以在人们日常生活中完成越来越多的 任务,比如打扫卫生、移动物体等等。为了使任务完成得更加流畅,机器人必 须实现对指定移动目标的路径规划。路径规划依赖于室内地图,常用的室内地 图为二维栅格地图,然而二维栅格地图只考虑了某一高度平面的环境信息,太 高或者太低的障碍物都不能避免,因此也不能在复杂环境中使用。

    技术实现要素:

    本发明目的在于克服现有技术的不足,尤其解决二维栅格地图只考虑了某 一高度平面的环境信息,无法得知周围环境的准确三维结构,不能保证所规划 的路径上机器人不与障碍物发生碰撞的问题。

    为解决上述技术问题,本发明提供一种地图路径规划方法,该方法采用三 维栅格地图,实现立体的路径规划,所述地图路径规划方法包括:采用激光传 感器采集周围环境的点云数据;用八叉树将点云地图转换为栅格地图;根据三 维栅格地图进行最优路径规划。

    该发明方案的有益效果在于,通过将离散的点云数据转换成三维栅格地图, 实现三维栅格立体地图下的最优路径规划,使得机器人可以避开环境中的物体, 避免碰撞确保机器人行进中的安全。

    附图说明

    图1是本发明的实施例的基于八叉树表示的三维栅格地图路径规划系统示 意图。

    具体实施方式

    下面结合附图及具体实施例对本发明进行更加详细与完整的说明。可以理 解的是,此处所描述的具体实施例仅用于解释本发明,而非对本发明的限定。

    图1是根据本发明的实施例的地图路径规划方法包括:S1、采用激光传感 器采集周围环境的点云数据;S2、用八叉树将点云地图转换为栅格地图;S3、 根据三维栅格地图进行最优路径规划。

    具体而言,经过步骤S1对周围环境进行点云数据采集后,已经得到大量的 点云数据,需要用八叉树将点云地图转换为栅格地图,步骤S2描述如下:

    八叉树是一种基于树形结构的层次化数据结构,如果树不是空的,那么八 叉树的任何一个节点的都只有八个或者零个子节点。

    八叉树的每个节点与正方体C的一个子立方体对应,树根与正方体本身相 对应,如果要表示的形体V只有正方体C(V=C),那么要表示的形体V的八叉 树仅有树根,如果要表示的形体V不仅仅是正方体(V≠C),则将C等分为八 个子立方体,每个子立方体与树根的一个子节点相对应。只要某个子立方体不 是完全空白或完全为V所占据,就要被八等分,从而对应的节点也就有了八个 子节点。这样的递归判断、分割一直要进行到节点所对应的立方体或是完全空 白,或是完全为V占据,

    步骤S3是最优路径规划操作,对栅格地图内的路径规划需要考虑机器人尺 寸大小,旋转动作和停止动作。机器人的尺寸大小可以用来判断是否会与周边 物体有碰撞的危险,而机器人运动时则要判断执行旋转动作和停止动作时是否 具备足够的空间,同样避免碰撞的危险,考虑到这些因素的路径规划算法流程 如下:

    S31:在八叉树结构的栅格地图内部邻域内遍历可通行栅格;

    S32:检测S31中得到的栅格位置有没有满足机器人本体尺寸的自由空间, 如果有则转至S33,没有的话转至S34;

    S33:检测S31中得到的栅格位置处是否具有足够机器人执行旋转运动所需 的空间,如果没有就放弃当前栅格并回到S31,否则转至S34;

    S34:检测S31中得到的栅格位置处是否具有足够机器人执行停止动作所需 的空间,如果没有的话放弃当前栅格并回到S31,否则转至S35;

    S35:机器人移动到该栅格位置处,如果该栅格处已经是目标点就转至S36, 否则转至S31;

    S36:综合之前走过的栅格位置生成从初始位置到达目标栅格的路径。

    上述为本发明较佳的实施方式,但本发明的实施方式并不受上述内容的限 制,其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、 组合、简化,均应为等效的置换方式,都包含在本发明的保护范围之内。

    展开全文
  • 为了使任务完成得更加流畅,机器人必须实现对指定移动目标的路径规划。路径规划依赖于室内地图,常用的室内地图为二维栅格地图,然而二维栅格地图只考虑了某一高度平面的环境信息,太高或者太低的障碍物都不能避免,...
  • 人工势场法是局部路径规划的一种比较常用的方法。这种方法假设机器人在一种虚拟力场下运动。 一、简介 如图所示,机器人在一个二维环境下运动,图中指出了机器人,障碍和目标之间的相对位置。 这个图比较清晰的...
  • 人工势场法是局部路径规划的一种比较常用的方法。这种方法假设机器人在一种虚拟力场下运动。 一、简介 如图所示,机器人在一个二维环境下运动,图中指出了机器人,障碍和目标之间的相对位置。 这个图比较...
  • 目前掘进机主要动作都是通过液压驱动,而作为液压油通道液压管路,路径规划的合理性非常重要。针对这一问题,在三维软件环境下建立了掘进机常用液压胶管和接头参数化模型库,结合工程实例,对掘进机管路路径...
  • 自动驾驶运动规划(Motion Planning)是无人驾驶汽车核心模块之一,它主要任务之一就是如何生成舒适、碰撞避免行驶路径和舒适运动速度。生成行驶路径最经典方法之一就是是Sampling-Based Planner算法;基于...
  • 人工势场法是局部路径规划的一种比较常用的方法。这种方法假设机器人在一种虚拟力场下运动。 如图所示,机器人在一个二维环境下运动,图中指出了机器人,障碍和目标之间的相对位置。 这个图比较清晰的说明了人工...
  • 路径规划算法学习Day2

    千次阅读 2020-12-05 15:00:52
    用于全局路径规划的典型方法有可视图法、自由空间法和单元分解法等。栅格法和单元树法是两种常用的单元分解法。今天和大家一起学习的是栅格法。 1、栅格法 1.1、原理 栅格法是对地图建模的一种方法。就是将障碍物...
  • 人工势场法是局部路径规划的一种比较常用的方法。这种方法假设机器人在一种虚拟力场下运动。 如图所示,机器人在一个二维环境下运动,图中指出了机器人,障碍和目标之间的相对位置。 这个图比较清晰的说明了人工...
  • 在数学建模中常用的方法:类比法、二分法、量纲分析法、差分法、变分法、图论法、层次分析法、数据拟合法、回归分析法、数学规划(线性规划,非线性规划,整数规划,动态规划,目标规划)、机理分析、排队方法、对策...
  • 基于三次样条插值的路径生成方法

    千次阅读 2020-05-28 22:51:02
    样条插值是一种工业设计中常用的、得到平滑曲线的一种插值方法,三次样条又是其中用的较为广泛的一种。低阶样条插值虽然计算简单、稳定性好、收敛性有保证且易在电子计算机上实现,但只能保证各小段曲线在连接处的...
  • 应用遗传算法进行机器人全局路径规划,针对该算法,目前常用的建模方法均存在一定缺陷,如链接图法过程复杂,栅格法栅格粒度难以控制,且随栅格数增加,算法复杂度急剧增加等等。论文采用了一种新颖的建模方法,该...
  • 针对新型飞行器对装配精度需求的不断提高,常用的数字化测量辅助装配系统已无法满足的问题,基于iGPS激光测量系统提出一种新型多装置混合对接测量方法,并基于该测量方法建立位姿测量模型、位姿解算模型和对接路径解算...
  • 在无人车的运动规划(Motion Planning)过程中,比如在速度规划...路径规划:已知当前的位姿信息,以及目标的位姿信息,需要生成一条平滑的路径,连接当前位姿到目标位姿,同时这个过程中应尽可能保持平顺,避免在路径...
  • 机器人路径规划(Robot Path Planning,RPP)的主要研究目的是寻找工作空间内的一条从出发点到目标点...在求解RPP问题的相关算法中,栅格法(Grid Method,GM)是一类较常用的环境建模方法[6-8]。一些已存在的RPP算法存...
  • 人工势场法是局部路径规划的一种比较常用的方法。这种方法假设机器人在一种虚拟力场下运动。 如图所示,机器人在一个二维环境下运动,图中指出了机器人,障碍和目标之间的相对位置。 这个图比较清晰的说明了人工...
  • 1.模型预测控制(Model Predictive Control) MPC的作用机理可以表述为:在每一个采样时刻,根据当前的测量信息,...工程问题中系统输入是随意变化的量,因此需要将无限维度的系统输入转化为有限维度的参数,常用的方法
  • 机器人路径规划(Robot Path Planning,RPP)的主要研究目的是寻找工作空间内的一条从出发点到目标点...在求解RPP问题的相关算法中,栅格法(Grid Method,GM)是一类较常用的环境建模方法[6-8]。一些已存在的RPP算法存...
  • 人工势场法是局部路径规划的一种比较常用的方法。这种方法假设机器人在一种虚拟力场下运动。 如图所示,机器人在一个二维环境下运动,图中指出了机器人,障碍和目标之间的相对位置。 这个图比较清晰的说明了人工...
  • 无人车路径规划算法---(2)地图

    千次阅读 2020-01-20 17:32:05
    后端平滑优化"pipeline,本文将为大家介绍路径规划算法常用地图格式,文章主要分为以下三个模块: 常用地图格式 栅格地图 拓扑地图与高精度地图 生成一个随机二维栅格地图方法的代码将开源在博主github主页 ...
  • Minimum Snap是轨迹优化中的常用方法,其效果如下: 上图中红线为Minimum Snap优化生成光滑轨迹,可以看出Minimum Snap有利于光滑曲线生成。该算法虽然可以控制轨迹经过哪些路标点,但是没有考虑环境中障碍物...
  • 数据结构中关于货郎担路径问题的常用解法,边界路径问题相信诸位学习过高级算法数据结构朋友肯定是知道“货郎担问题”是很经典图算法问题货郎担问题可以总结出4种不同解法,主要有回溯、贪心、动态规划以下...
  • 路径规划-人工势场法(Artifical Potential Field)

    万次阅读 多人点赞 2017-11-11 17:54:12
    人工势场法是局部路径规划的一种比较常用的方法。这种方法假设机器人在一种虚拟力场下运动。 一、简介 如图所示,机器人在一个二维环境下运动,图中指出了机器人,障碍和目标之间的相对位置。  这个...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 269
精华内容 107
关键字:

常用的路径规划方法