路径规划 CH ArcFlag

一时失言乱红尘 2022-07-16 17:00 198阅读 0赞

先立题，后面再补内容

越来越发现我的缺点：不注意总结，只有不断的总结，才能正在深刻的理解某个东西。立题已经好几天了，到今天才过来开始写，唉。。。

废话不多说了，下面开始记录自己对ArcFlag以及CH方法的理解。

路径规划概念：在一个路网中找出，任意给定2个路口，找出这2个路口之间的最短路径（距离、时间、费用）。

1.现实生活中的启发

当我们要从北京开车去天津的时候，我们根本不会计算走的某条路是不是最优路径，而只是看看这条路能不能到我要去的地方。对，正是这个“这条路能不能到达终点？”给了我们一个启发：看看这条路是不是在最优路径上面。基于这个思想，我们的ArcFlag方法应运而生。

路网G=（E,V）

E=路网G中所有路段的集合；

V=路网G中所有路口的集合；

NE=E中路段的数量；

NV=V中路口的数量；

给定一个路段e，它的首、末路口分别为s、t；并且它针对路网中的任意一个路口v有一个f属性，属性f的代表的意义为：**从s出发，到达路口v的最优路径p是否经过路段e**。这样，在路径规划的过程中，到达一个路口s时，只需要查看f为1的路段，从而减少拓展过程。

外存估算:每个f用一个bit存储，一个路段需要的字节为NV/8;全国总数据量B=NE\*NV/8。

假设NE=3，800，000

NV=2，400，000

那外存B=3800000\*2400000/8=1087188M

显然这个数字太大。

所以我们可以考虑将路口分成NB块，然后每个路段存储它针对某个块Block的f属性：只要从s出发，到达Block块内的某一个路口的flag为一，这个f就为1。

假设VB=500

那外存B=3800000\*500/8=226M

这还是一个可以接受的值。

但是：对于路段e，如果它是双向路段，可以从s走到t；也可以从t走到s；所以一个路段e需要2个f，一个是s->t的f1，一个t->s的f2；所以上面的外存需要扩大2倍，为552M左右。

有了上面这552M的flag数据，我们在路网G中进行任意2路口的路径规划，将异常的快。

双向拓展：如果只有一个方向的flag，当快到中的时候，拓展范围会形成一个圆锥形（走到终点所在块的话，flag将失去作用）。因此我们可以从2个点同时往中间拓展，避免出现圆锥。因此我们需要再做一套反向flag数据。

**正向拓展：拓展过程中，使用路段e相对终点T所在块的正向数据。（看从路段的某端出发，到BT的最优路径是否经过e）**

**反向拓展：拓展过程中，使用路段e相对起点S所在块的反向数据。（看起点出发，到路段e的某端的最优路径是否经过e）**

发表评论取消回复

表情：

评论列表（有 0 条评论，198人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划——路径问题

指在一个给定的网格中，从起点到终点有多条可能的路径，每条路径都有一个特定的权重或成本，动态规划路径问题的目标是找到一条路径使得其总权重或成本最小或最大化。在解决这类问题时...

柔光的暖阳◎/ 2024年04月25日 08:46/ 0 赞/ 92 阅读

相关【动态规划】路径问题

文章目录动态规划（路径问题） 1. 不同路径 | 2. 不同路径 || 3. 礼物的最大价值 4. 下降最小

忘是亡心i/ 2024年03月22日 20:36/ 0 赞/ 122 阅读

相关 agv 路径规划 matlab

在MATLAB中，您可以使用不同的方法进行AGV（自动引导车）路径规划。路径规划是指确定AGV如何从一个起点到达一个目标点，避免碰撞和优化路径。以下是使用MATLAB进行AGV

向右看齐/ 2024年02月21日 11:43/ 0 赞/ 66 阅读

相关动态规划——62. 不同路径

1 题目描述一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角

朴灿烈づ我的快乐病毒、/ 2023年10月08日 16:16/ 0 赞/ 56 阅读

相关 dwa轨迹规划，局部路径规划

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE

傷城~/ 2023年01月19日 09:41/ 0 赞/ 18 阅读

相关路径规划问题

　　1、旅行商问题（Traveling Salesman Problem, TSP）　　这个问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个

不念不忘少年蓝@/ 2022年08月28日 01:45/ 0 赞/ 369 阅读

相关路径规划学习1

学习原因：在未知环境下，机器人能否自主完成无碰撞情况下从起始点到目标点是机器人构建陌生环境地图的基础。移动机器人路径规划技术：全局路径规划和局部路径规划。如果机器人初始位姿

傷城~/ 2022年08月14日 03:39/ 0 赞/ 210 阅读

相关路径规划 CH ArcFlag

先立题，后面再补内容越来越发现我的缺点：不注意总结，只有不断的总结，才能正在深刻的理解某个东西。立题已经好几天了，到今天才过来开始写，唉。。。

一时失言乱红尘/ 2022年07月16日 17:00/ 0 赞/ 199 阅读

相关路径与轨迹、路径规划与轨迹规划、路径跟踪与轨迹跟踪

对于无人车辆来说，全局路径点只要包含空间位置信息即可，也可以包含姿态信息，而不需要与时间相关，但局部规划时，则可以考虑时间信息。这里规定轨迹点也是一种路径点，即当路径点信息中加

雨点打透心脏的1/2处/ 2022年06月04日 02:27/ 0 赞/ 713 阅读

相关路径规划之 A* 算法

算法介绍 A\（念做：A Star）算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度。本文在讲解算法的同时也会提供Python语言的代码实现，并会借助ma

た入场券/ 2022年03月02日 02:43/ 0 赞/ 223 阅读