请选择 进入手机版 | 继续访问电脑版

723

阿木币

1

精华

1111 小时

在线时间

管理员

Rank: 9Rank: 9Rank: 9

发表于 2022-11-19 17:35:57 73 浏览 0 回复

[算法之美] 常用的路径规划算法浅析

所谓路径规划,也就是在起点和终点之间找到一条连续的运动轨迹,在尽可能优化路径的同时避开环境中的障碍物。


常用的路径规划算法有传统的基于图搜索算法、基于采样的路径规划算法,以及考虑动力学的路径规划算法等。那么,这几种路径规划算法分别适用于什么情况下呢?接下来我们就为大家详细介绍一下。


>>>>基于搜索的路径规划算法


基于搜索的路径规矩算法主要包含:BFS(广度优先)算法、DFS(深度优先)算法、Dijkstra算法、启发式搜索 A* 算法等。


一般而言,基于搜索的规划算法适用于运行在栅格地图上。通过在栅格地图上不断地搜索,进而检索出一条到达终点的连续轨迹。


虽然基于图搜索的规划算法总是能够给出一个全局范围内的最优解(路径最短、效率最优),但是当地图过大,规划的维度过高时,它的搜索效率就会变得很慢。


>>>>基于采样的路径规划


基于采样的路径规划主要包含:RRT(快速扩展随机树)算法、RRT*算法、informed RRT *算法等。


在某些场景下,对于路径规划算法的关注点主要放在效率上,那么基于采样的规划算法就更加符合要求。

这类算法的核心在于随机采样,从父节点开始,随机地在地图上生成子节点,连接父子节点并进行碰撞检测,若无碰撞,就扩展该子节点。通过不断地随机扩展样本点,直到生成一条连接起点和终点的路径。由于样本点是随机生成,所以最终执行的路径可能不是全局最优解,甚至还会明显感觉机器人在“绕路”。


相对于基于搜索的规划算法,基于采样的规划算法在效率上更优,因其不用遍历整个栅格地图,就能快速生成一条可行路径。


以上两种类型的算法并未考虑机器人运动限制,都只是考虑了“最近的路径”或“最快的路径”。如果想要在最短的时间内获得全局最优解,那么考虑动力学的路径规划算法将是一个不错的选择。


>>>>考虑动力学的路径规划


考虑动力学的路径规划主要包含:混合A* 算法、Kinodynamic RRT*算法等。


以无人车为例,如果生成一条有直角拐点的路径,对于两轮差速运动模型的无人车勉强可以通过这个直角拐点,因为差速模型无人车最小转弯半径为0,也就意味着可以原地旋转(但在实际运动过程也无法达到瞬间转向)。对于阿克曼运动模型的无人车(生活中的汽车就是采用的阿克曼转向系统),由于转弯半径不为0,因此经过直角拐点时就无法通过。考虑动力学的规划算法不再把机器人当作一个质点考虑,而是考虑了规划轨迹要满足动力学,生成的轨迹能使得机器人能真正执行。


以混合A*算法举例,考虑车辆运动学之后,出来的路径就不是直来直去的折线,而是较为平滑的曲线,并且在障碍物碰撞检测时,也不会单纯地将机器人作为一个质点,而是会考虑机器人轮廓。如下图所示,A*算法扩展节点时为八个格子,Hybrid A*算法扩展节点时有六个运动基原,向前扩展三个运动模式,向后扩展三个运动模式。

目前Prometheus开源项目也包含了路径规划算法,若大家有相关需求,可以通过阿木实验室官网(开源项目 - 阿木实验室)进一步了解Prometheus开源项目。




本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

扫一扫浏览分享
回复

使用道具 举报

返回列表
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表