🧭 基于采样的路径搜索算法
📚 30章 · 从入门到前沿
1
算法概述
什么是基于采样的路径规划？为什么需要它？与图搜索算法的对比。
2
配置空间
C-Space概念、障碍物表示、自由空间与障碍空间。
3
随机采样基础
均匀随机采样、伪随机数生成器、采样密度与覆盖率。
4
最近邻搜索
KD-Tree原理、构建与查询、在路径规划中的应用。
5
PRM算法原理
概率路线图的基本思想、学习阶段与查询阶段。
6
PRM算法实现
节点采样、连接策略、碰撞检测、图构建。
7
PRM算法改进
Lazy PRM、PRM*、桥测试采样。
8
RRT算法原理
快速探索随机树的核心思想、树生长过程。
9
RRT算法实现
扩展步骤、目标偏向、步长选择。
10
RRT算法改进
RRT-Connect、RRT*、Informed RRT*。
11
RRT*算法
渐进最优性、重新布线过程、代价函数设计。
12
Informed RRT*
椭圆子集采样、加速收敛策略。
13
RRT-Connect算法
双向搜索树、连接策略、收敛速度分析。
14
碰撞检测基础
几何碰撞检测、AABB与OBB包围盒、分离轴定理。
15
碰撞检测进阶
GJK算法、EPA算法、连续碰撞检测。
16
距离计算
点到线段距离、点到多边形距离、最近点对。
17
路径平滑
B样条曲线、贝塞尔曲线、路径插值方法。
18
路径缩短
剪枝算法、捷径法、路径优化。
19
动态环境
动态RRT、重规划策略、增量式更新。
20
多机器人规划
协同RRT、优先级规划、冲突解决。
21
高维空间规划
机械臂运动规划、自由度问题、流形采样。
22
非完整约束
差速轮模型、Dubins曲线、Reeds-Shepp曲线。
23
最优控制与采样
LQR-RRT*、控制空间采样、轨迹优化。
24
感知与规划结合
SLAM与规划、部分可观测环境、信息论方法。
25
并行计算
GPU加速采样、多线程碰撞检测、分布式规划。
26
Benchmark与评估
规划成功率、计算时间、路径代价、重复性。
27
开源库介绍
OMPL、MoveIt、SBPL、ROS Navigation Stack。
28
实战案例1：二维迷宫导航
基于RRT的二维迷宫导航。
29
实战案例2：机械臂避障规划
基于PRM的机械臂避障规划。
30
课程总结与前沿
机器学习+采样规划、学习型采样、未来趋势。