【深蓝学院】移动机器人运动规划--第1章 运动规划介绍与地图构建--笔记

文章目录

  • 1. Course introduction
  • 2. Course Outline
    • 2.1 课程概览
    • 2.2 课程算法概览
      • 2.2.1 基于搜索的前端
      • 2.2.2 基于采样的前端
      • 2.2.3 满足动力学约束的路径搜索
      • 2.2.4 后端轨迹优化
  • 3. 地图表示
    • 3.1 Occupancy grid map占用栅格地图
    • 3.2 八叉树地图
    • 3.3 Voxel hashing（体素哈希）
    • 3.4 piint cloud点云
    • 3.5 TSDF 截断符号距离函数
    • 3.6 ESDF欧式符号距离函数
    • 3.7 More
  • 4. Occupancy grid map
    • 4.1 理论推导
    • 4.2 occupancy Grid Map小结
  • 5. Euclidean Signed Distance Field(ESDF)
    • 5.1 计算步骤
    • 5.2 ESDF代码
    • 5.3 线性插值及梯度计算
  • 6. Refernece

1. Course introduction

在这里插入图片描述
会：

  • 模块化设计(学院派)的规划pipeline
  • 希望能在实际机器上实现

不会

  • 端到端导航（据我所知，强化学习做导航比较多）
  • 详细的公式证明（可后面查阅paper）

运动规划在整个机器人技术栈中属于较为上层的部分。
在这里插入图片描述
感知-规划-控制 闭环（SLAM在感知层面）。

一些简单案例：
海陆空机器人均有
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

基础要求：

  1. 安全，不能碰撞
  2. 轨迹光滑：物理机上能源有限，轨迹要光滑，如果是拍摄则要考虑视频的流畅度，自动驾驶要考虑乘客的舒适度
  3. 动力学可行。

学院派pipeline：
planning同样也分为前后端：

  1. 前端主要生成粗略的、离散的路径，一般低维，不含具体的方向，速度大小等信息，称为path
  2. 后端根据path来进行优化，生成高维的、连续的、可执行的路径，称为trajectory

如何做机器人的研究：
在这里插入图片描述
在实际机器人上进行部署是学界亘古不变的道理？

在这里插入图片描述

  1. 要求规划领域的知识面需要广，对不同的场合设计不同的策略。
  2. 不要怕动手，robotics本身就很辛苦
  3. 出色的机器人工程师要对整个系统的各个部件都要熟知（感知，定位，控制），不要求开发，但是至少得维护。

2. Course Outline

2.1 课程概览

课程分为3部分：
前端path finding，后端trajectory generation，用于机器人规划的MPC

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2.2 课程算法概览

基于搜索。DFS，BFS
基于采样。随机采样的思想，希望用越来越多的采样来覆盖环境中没有探索过的区域，去构成一个graph。

2.2.1 基于搜索的前端

在这里插入图片描述
与搜索算法对应的就是图，图中最重要的是结点和边（有向和无向边）：
在这里插入图片描述

Dijkstra和A*目的不同，前者倾向于搜索全图，最短路径的cost较大，后者有指向性，很快找到最短路径。
在这里插入图片描述

JPS跳点搜索不一定比A*更好，需要看实际应用场景。
在这里插入图片描述

2.2.2 基于采样的前端

撒一些采样点，将不在障碍物内的边连起来，去掉在障碍物内的边，得到概率路线图(PRM)。
在这里插入图片描述

RRT本身不具备渐进最优性，RRT具备，下图左，两点间最优路径是接近直线，但RRT没找到直线，RRT维护的随机扩展树很顺滑，而RRT是杂乱无章。（Ch3主要讲）
在这里插入图片描述

informed RRT* 启发式RRT*，画一个椭圆（椭球），相当于给搜索范围框定了一个先验，在搜索范围内找
在这里插入图片描述

在这里插入图片描述

2.2.3 满足动力学约束的路径搜索

比如约束是起始和结束时的速度（大小，方向）。
1. hybrid A*
lattice search，机器人的控制方法，在某点给油或者打方向，遍历所有的可能组成一个控制组合，然后在本段控制终点继续这种组合模式。
在这里插入图片描述
但是这样做cost很高，于是hybrid A*应运而生，维护一个栅格，每个栅格里面都有一个状态，找到更好的状态之后就会把之前的状态给删掉。
在这里插入图片描述
地面无人车导航，无人机导航。

在这里插入图片描述

2. Kinodynamic RRT*
两点边界值的最优控制问题，现有边界，再计算中间的路径，和latice search相反，latice search是现有中间的路径集合，再计算最优终点。
在这里插入图片描述
在这里插入图片描述

2.2.4 后端轨迹优化

Minimun snap要保持机器人消耗能量最小
在这里插入图片描述

路标点之间生层traj，如果产生了碰撞，则在两点之间重新去一个点，再生成轨迹，尽可能逼近前端的直线path。

3. 地图表示

在这里插入图片描述
地图由数据结构和融合方法构成，二者有区别。

3.1 Occupancy grid map占用栅格地图

  • 最稠密
  • 结构化
  • 直接访问

在这里插入图片描述
稠密
结构化

直接索引(O(1)复杂度)

https://github.com/ANYbotics/grid_map
这里安装不上grid map，说找不到costmap_2d，解了一会儿没解决，先放着。

3.2 八叉树地图

  • 稀疏
  • 结构化
  • 间接访问

https://octomap.github.io/

occupancy grid map虽然快，但是占用内存极大，为了减小内存占用，牺牲一定的查询速度，引入了八叉树地图，对于有障碍物的节点可以继续展开，没有的可以无需展开，但是访问障碍物需要通过父节点进行访问，速度比occupancy grid map慢，但内存占用少。
在这里插入图片描述

3.3 Voxel hashing（体素哈希）

  • 最稀疏
  • 结构化
  • 间接访问

https://github.com/niessner/VoxelHashing
http://www.robots.ox.ac.uk/~victor/infinitam/
用在稠密重建或者3D SLAM上。
在这里插入图片描述
同样也是基于八叉树的数据结构，引入了block(图中555的大方格)和voxel(最小的方格)的概念，最终数据存放在每个voxel内，把每个block通过hash表的形式存储起来（具体为什么是最稀疏的目前还不了解）。

3.4 piint cloud点云

  • 无序的
  • 无索引查询

http://pointclouds.org/
在这里插入图片描述

3.5 TSDF 截断符号距离函数

老规矩，还是叫TSDF地图，不翻译。voxel内存储的是该小块与距其最近的物体表面的距离。(可用GPU进行并行加速)
阶段的意思即只关心它的FOV内的一定距离的观测，剩下的截断不管。（ESDF则关心所有的，不进行截断）
在这里插入图片描述

3.6 ESDF欧式符号距离函数

https://github.com/ethz-asl/voxblox
https://github.com/HKUST-Aerial-Robotics/FIESTA
https://github.com/HKUST-Aerial-Robotics/Teach-Repeat-Replan
对FOV内所有的观测都计算距离，目的是为了让生成的轨迹尽可能远离障碍物，提高安全性，思路是使用距离障碍物距离的梯度信息把轨迹往远离障碍物的地方推，如下图所示是高飞phd期间在港科大的工作：FIESTA和TRR‘s local map(teach repeat replan). 均基于ESDF
在这里插入图片描述

3.7 More

在这里插入图片描述
蓝色是障碍物，棕色是free space，用凸的多面体表示。（凸会带来很多好处，Ch4，5学完之后会了解。）

表示空间的拓扑结构，skeleton骨架，非常稀疏，速度也会很快。
在这里插入图片描述

4. Occupancy grid map

Fast-Planner和EGO-Planner(Ch8会讲)都使用了Occupancy grid map。

4.1 理论推导

推导参考文献[1]
在这里插入图片描述
0代表free，1代表occupied，常是障碍物。

但是传感器观测是带噪声的，在某处观测为occupied在另一处为free，如何处理？

答：计算每个栅格的后验概率。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

可以看出方框内的递推关系了。

在这里插入图片描述
l t ( m i ) l_{t}(m_i) lt​(mi​)中涉及到逆传感器模型：
在这里插入图片描述
逆传感器模型使用bayes转为传感器模型：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
中间的一项 l o g p ( z t ∣ m i ) p ( z t ∣ m i ‾ ) log\frac{p(z_t|m_i)}{p(z_t|\overline{m_i})} logp(zt​∣mi​​)p(zt​∣mi​)​即为传感器模型相关，接下来进行讨论：

在这里插入图片描述

假设传感器的观测模型不变，即a和b的值不变，则我们对 l t ( m i ) l_t(m_i) lt​(mi​)进行更新只需简单的加减操作

在这里插入图片描述
上面讨论的是 l t ( m i ) l_t(m_i) lt​(mi​)的性质，我们最开始是要讨论后验概率 p ( m i z 1 : t ) p(m_iz_{1:t}) p(mi​z1:t​)，这二者有什么关系？

实际上可以使用 l t ( m i ) l_t(m_i) lt​(mi​)的正负来代替后验概率来判断状态 m i m_i mi​，假设我们求出了后验概率 p ( m i z 1 : t ) p(m_iz_{1:t}) p(mi​z1:t​)，那我们可以设置一个阈值0.5，

  • 当 p ( m i z 1 : t ) > 0.5 p(m_iz_{1:t})>0.5 p(mi​z1:t​)>0.5，我们认为 m i = 1 m_i=1 mi​=1，
  • 反之 m i = 0 m_i=0 mi​=0，

    使用 l t ( m i ) l_t(m_i) lt​(mi​)则
  • 当 l t ( m i ) > 0 , m i = 1 l_t(m_i)>0, m_i=1 lt​(mi​)>0,mi​=1
  • 反之 m i = 0 m_i=0 mi​=0

以上即为occupancy grid map的结论。

那么为何 l t ( m i ) l_t(m_i) lt​(mi​)能替代后验概率呢？需要对 l t ( m i ) l_t(m_i) lt​(mi​)的函数性质进行讨论，记后验概率 p ( m i z 1 : t ) = x p(m_iz_{1:t})=x p(mi​z1:t​)=x，有以下讨论：

在这里插入图片描述

4.2 occupancy Grid Map小结

在这里插入图片描述

5. Euclidean Signed Distance Field(ESDF)

5.1 计算步骤

参考文献[2]
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

关于采样函数q，对于高维ESDF有用

在这里插入图片描述

一维ESDF的计算伪代码：

算法逻辑比较绕，此处不进行展开。
在这里插入图片描述
y与x无关，所以可以fix一项变为一维形式，求另一项
在这里插入图片描述

ESDF物理意义：

没有障碍物就认为障碍物在无穷远，距离是 ∞ \infty ∞

  1. 只管y相关的项，计算离最近障碍物的距离的平方 d 1 d_1 d1​(调用上述伪代码计算1维ESDF值)
  2. fix x，遍历x’的值，计算距离平方，加上 d 1 d_1 d1​即为 D D D

只管y相关的项：
在这里插入图片描述
2. 将d1当做常量，固定x的值，eg： x = 1 x=1 x=1，变化 x ′ x^ \prime x′的值，计算 ( x − x ′ ) 2 + d 1 (x-x^\prime)^2+d_1 (x−x′)2+d1​，

障碍物里面存放的值是到最近的free栅格的距离，是负值。
在这里插入图片描述

5.2 ESDF代码

在这里插入图片描述
在这里插入图片描述

5.3 线性插值及梯度计算

当不在栅格点正中间，需要对点进行插值，如下为一维和二维情况：

线性插值(2点)与双线性插值(4点)
在这里插入图片描述

三维情况：三线性插值（8个点）
在这里插入图片描述

前面讲到ESDF可以使用梯度来使得轨迹更远离障碍物，更安全，如果不在栅格中心，梯度的计算也依赖于线性插值，以下为3维情况：
在这里插入图片描述

课程着重于算法原理的讲解，如果要想了解实现，强烈建议看Fast planner的源码，跑通他们的例程，有条件的可以使用传感器采集bag包，跑他们的建图程序。

6. Refernece

[1] https://www.cs.cmu.edu/~16831-f14/notes/F14/16831_lecture06_agiri_dmcconac_kumarsha_nbhakta.pdf
[2] Felzenszwalb, Pedro F., and Daniel P. Huttenlocher. “Distance transforms of sampled functions.” Theory of computing 8.1 (2012): 415-428.

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/323244.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

虾皮开通：如何在虾皮（Shopee）平台上开通店铺详细步骤

虾皮开通：如何在虾皮（Shopee）平台上开通店铺详细步骤

在全球电商市场的竞争中，越来越多的卖家选择在虾皮（Shopee）平台上开设店铺。作为东南亚地区最大的电子商务平台之一，虾皮提供了一个便捷的销售渠道，吸引了数百万的买家和卖家。如果您想在虾皮上开设自己的店铺&#xf…
阅读更多...
《动手学深度学习》学习笔记 第10章 注意力机制

《动手学深度学习》学习笔记 第10章 注意力机制

本系列为《动手学深度学习》学习笔记 书籍链接：动手学深度学习 笔记是从第四章开始，前面三章为基础知识，有需要的可以自己去看看 关于本系列笔记： 书里为了让读者更好的理解，有大篇幅的描述性的文字，内容很…
阅读更多...
利用c 原生头文件完成JPEG全流程编码

利用c 原生头文件完成JPEG全流程编码

骄傲一下，经过一个多月的努力，终于完成jpeg的全套编码。经验证此程序可以把摄像头yuv信号转为JPG图片。现在的程序还不完美，只能对长和宽尺寸是16倍数的信号转码。而且转码速度太慢，一帧1280720的图片要2秒多。此程序只能对yuv420…
阅读更多...
静态路由高级特性（HCIA）

静态路由高级特性（HCIA）

目录 一、静态路由高级特性 1、路由条目六要素 2、路由分类 3、静态路由配置命令 （1）静态路由中下一跳MA和P2P区别 4、静态路由加路由表条件 5、permanent特性 二、路由冗余和负载 1、控制层面control plane 2、数据层面data plane 路由操控精髓&#xf…
阅读更多...
测试用例的设计（超详细总结）

测试用例的设计（超详细总结）

🍅 视频学习：文末有免费的配套视频可观看 🍅 关注公众号【互联网杂货铺】，回复 1 ，免费获取软件测试全套资料 1. 测试用例的概念 软件测试人员向被测试系统提供的一组数据的集合，包括 测试环境、测试步骤、…
阅读更多...
深入探究Python Collections模块：高效数据结构解决方案

深入探究Python Collections模块：高效数据结构解决方案

前言 这几天刷leetcode题时，看到题解中有这样一行代码collections.defaultdict(list)，不明白是啥意思，平时开发的脚本中未遇到，借着这个机会，学习一下collections模块的用法。 collections 这个模块实现了一些专门化…
阅读更多...
Overleaf Docker编译复现计划

Overleaf Docker编译复现计划

Overleaf Docker编译复现计划 Overleaf Pro可以支持不同年份的Latex镜像自由选择编译，这实在是一个让人看了心痒痒的功能。但是很抱歉，这属于Pro付费功能。但是我研究了一下，发现其实和Docker编译相关的代码，社区版的很多代码都没…
阅读更多...
使用Dockerfile构建镜像的详细指南

使用Dockerfile构建镜像的详细指南

目录 前言 一、什么是 Dockerfile 二、使用 Dockerfile 定制镜像 开始构建镜像 上下文路径 三、指令详解 四、构建阿里云仓库 前言 Docker是一种流行的容器化平台，可以帮助开发人员和运维团队更轻松地构建、发布和运行应用程序。在Docker中，镜像是…
阅读更多...
捷捷微电突发涨价函，Trench MOS产品线上调5%-10% | 百能云芯

捷捷微电突发涨价函，Trench MOS产品线上调5%-10% | 百能云芯

近日，国产功率半导体厂商捷捷微电发布了一份《价格调整函》，宣布自2024年1月15日起，将对公司Trench MOS产品线的单价进行上调，上调幅度为5%-10%。 据悉，调整前已下的订单将继续按照原有单价和数量履行，而新…
阅读更多...
java实现AES256对称加解密工具类

java实现AES256对称加解密工具类

一、引入依赖包 引入相关依赖包 <dependency><groupId>org.bouncycastle</groupId><artifactId>bcprov-jdk15on</artifactId><version>1.70</version> </dependency> <!--lombok用于简化实体类开发--> <dependency&g…
阅读更多...
Unity寻路A星算法

Unity寻路A星算法

文章目录 实现步骤概览&#xff1a; 计算移动成本1. **定义移动成本函数**&#xff1a;2. **考虑不同类型的格子**&#xff1a;3. **动态调整成本**&#xff1a;4. **实际应用**&#xff1a; 优先级队列1. **初始化**&#xff1a;2. **节点评估**&#xff1a;3. **更新节点状态…
阅读更多...
spring boot学习第八篇:通过spring boot、jedis实现秒单

spring boot学习第八篇:通过spring boot、jedis实现秒单

参考&#xff1a;Redis实现分布式锁的7种方案 - 知乎 1、 准备数据库表&#xff0c;如下SQL表示库存表&#xff0c;有主键ID和库存数量字段 CREATE TABLE t_stock (id bigint(20) NOT NULL AUTO_INCREMENT,quantity bigint(20) NOT NULL,PRIMARY KEY (id) ) ENGINEInnoDB DEF…
阅读更多...
未来气膜体育馆的发展趋势是什么？

未来气膜体育馆的发展趋势是什么？

未来气膜体育馆的发展趋势是多方面的&#xff0c;以下是其中几个方面的趋势。 起初&#xff0c;随着人们对体育运动的需求不断增加&#xff0c;气膜体育馆的建设和使用将成为一种趋势。气膜体育馆具有灵活性和可移动性的特点&#xff0c;可以快速搭建和拆除&#xff0c;能够适…
阅读更多...
TOP 10 屏幕录制软件工具，可帮您轻松录制视频！

TOP 10 屏幕录制软件工具，可帮您轻松录制视频！

随着越来越多的人远程工作和学习&#xff0c;对可靠、高效的屏幕录制工具的需求变得越来越重要。屏幕录制已成为电子学习、游戏和视频创作的重要组成部分。然而&#xff0c;有这么多可用的屏幕录制工具&#xff0c;选择合适的工具可能具有挑战性。为了帮助您节省搜索时间和精力…
阅读更多...
案例127:基于微信小程序的预约挂号系统

案例127:基于微信小程序的预约挂号系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…
阅读更多...
如何去开发直播电商系统小程序

如何去开发直播电商系统小程序

明确你的直播电商系统的功能和特性&#xff0c;包括用户注册、商品展示、购物车、支付结算、直播功能、评论互动等。根据需求确定系统的基本架构和主要模块。 技术选型&#xff1a;选择适合你的直播电商系统的技术栈。考虑前端框架&#xff08;如React、Vue.js&#xff09;、后…
阅读更多...
基于等效消耗最小(ECMS)的电氢综合能源系统能量管理策略Simulink模型

基于等效消耗最小(ECMS)的电氢综合能源系统能量管理策略Simulink模型

0. 前言 常见的EMS控制策略为基于状态机&#xff08;State Machine Control&#xff09;、基于等效消耗最小&#xff08;Equivalent Consumption Minimization Strategy&#xff0c;ECMS&#xff09;及调度控制模式。本文着重介绍前两种&#xff0c;针对第一种控制策略可参考模…
阅读更多...
Unity Urp 渲染管线 创建透明材质球

Unity Urp 渲染管线 创建透明材质球

按照以上方式设置后就可以得到一个透明的材质球 Tips&#xff1a;Blending mode &#xff1a; alpha 和 Blending mode &#xff1a; additive都是完全透明效果具体差异暂时不知道
阅读更多...
iis配置asp网站

iis配置asp网站

1.安装IIS的ASP win7和win10都是一样的 下安装IIS时ASP一般被默认不选中的状态&#xff0c;因此需要打开IIS检查功能视图栏中是否存在ASP选项&#xff0c;若没有则需要从控制面板->程序和 功能->打开或关闭Windows功能->Internet信息服务->万维网服务->应用程序…
阅读更多...
数据结构与算法：快速排序

数据结构与算法：快速排序

数据结构与算法&#xff1a;快速排序 快速排序荷兰国旗问题霍尔版本递归优化小区间优化 PartSort优化三数取中 挖坑法前后指针法 非递归法 快速排序 荷兰国旗问题 想要理解快速排序&#xff0c;就先理解这个问题&#xff1a; [LeetCode75.颜色分类] 荷兰国旗是由红白蓝三色组…
阅读更多...
最新文章

Copyright @ 2022~2023