无人赛车路径规划：Delaunay三角剖分算法实践

1. 项目概述：无人赛车路径规划的核心挑战

大学生方程式无人赛车（FSAE Autonomous）是近年来高校智能车辆领域的顶级赛事，其核心难点在于如何在动态环境中实现快速、安全的路径规划。与传统车辆不同，无人赛车需要在锥桶标记的赛道内以极限速度行驶，这对路径生成算法提出了三点严苛要求：

1. 实时性：赛车时速可达120km/h，算法必须在50ms内完成单次规划
2. 平滑性：生成的路径需满足车辆动力学约束，避免急转弯导致的失控
3. 适应性：需处理锥桶摆放误差、传感器噪声等现实干扰

我们团队采用的Delaunay三角剖分法，本质上是通过计算几何方法将离散的锥桶坐标转化为连续的可行驶区域。这种方法相比传统的栅格法（占用内存大）和RRT算法（随机性导致不稳定），在内存占用和路径质量间取得了更好平衡。

提示：实际比赛中锥桶间距约5-8米，三角剖分后的边长通常控制在10米以内，确保路径分段足够精细

2. Delaunay三角剖分的工程实现

2.1 锥桶数据处理流程

原始传感器（如激光雷达）获取的锥桶坐标需经过预处理才能用于三角剖分：

matlab复制% 示例：锥桶坐标滤波与排序
cones = [x1,y1; x2,y2; ...]; % 原始坐标
cones = medfilt1(cones, 3); % 中值滤波去除跳动
cones = sortrows(cones, 1); % 按x坐标排序

关键处理步骤：

1. 坐标转换：将全局坐标系转为以车辆为中心的局部坐标系
2. 异常值剔除：根据相邻锥桶间距阈值（建议3-15米）过滤错误检测
3. 左右侧分类：使用最小二乘法拟合车道中心线，分离左右锥桶

2.2 三角剖分核心算法

Matlab内置的delaunayTriangulation函数可直接使用：

matlab复制dt = delaunayTriangulation(cones(:,1), cones(:,2));
triplot(dt); % 可视化三角网格

但比赛场景需要特别处理边界条件：

1. 约束边添加：强制连接相邻锥桶形成赛道边界
2. 最大角限制：剔除内角大于120度的瘦长三角形
3. 赛道宽度验证：确保三角形边不横跨两侧锥桶

我们改进的剖分流程如下表所示：

3. 路径生成与优化策略

3.1 基于三角形中线的初始路径

通过筛选靠近车道中心线的三角形边，连接其中点形成初始路径：

matlab复制edges = edges(dt); % 获取所有边
validEdges = [];
for i = 1:size(edges,1)
    if isCenterSideEdge(edges(i,:)) % 自定义判断函数
        validEdges = [validEdges; edges(i,:)];
    end
end
path = calculateMidPoints(validEdges); % 计算中点路径

3.2 考虑车辆动力学的路径优化

初始路径需要进一步平滑处理以满足赛车动力学约束：

1. 曲率连续化：使用三次样条插值确保曲率变化率≤0.1 m⁻²

2. 速度剖面生成：根据曲率半径计算各点最大允许速度：

   math复制v_{max} = \sqrt{a_{lat\_max} \cdot R}
   

   其中a_lat_max通常取2.5-3.5g（取决于轮胎性能）

3. 加速度约束：纵向加速度限制在±1.5g以内

我们开发的优化算法流程如下图所示（伪代码）：

code复制function optimizedPath = optimizePath(rawPath)
    spline = fitSpline(rawPath); % 样条拟合
    curvature = calculateCurvature(spline); % 曲率计算
    velocityProfile = generateVelocityProfile(curvature); 
    optimizedPath = resampleByVelocity(spline, velocityProfile);
end

4. 实车测试中的问题与解决方案

4.1 典型故障案例记录

在2023赛季测试中遇到的三个典型问题：

1. 锥桶漏检导致的路径断裂

   • 现象：某侧连续2个锥桶未识别，三角剖分失败
   • 解决方案：增加基于历史数据的锥桶预测模块

2. 高速过弯路径震荡

   • 现象：80km/h以上时路径频繁摆动
   • 根因：采样点过疏导致曲率计算不准
   • 修复：将路径点间距从1m改为0.3m

3. 紧急避障响应延迟

   • 测试数据：障碍物出现到路径更新平均耗时120ms
   • 优化方法：引入局部三角网格动态更新算法

4.2 参数调优经验

关键参数的实际调试建议：

5. 算法扩展与进阶优化

对于希望进一步提升性能的团队，建议尝试以下方向：

1. 混合规划架构：

   • 全局层：Delaunay三角剖分
   • 局部层：使用MPC处理动态障碍物

2. 机器学习增强：

   • 训练CNN预测最优路径点权重
   • 使用强化学习优化速度剖面

3. 硬件加速：

   • 将三角剖分移植到FPGA实现
   • 利用GPU并行计算曲率

我们测试发现，在Intel i7-11800H处理器上，优化后的C++实现比Matlab原型快17倍（从85ms降至5ms），足以满足高速场景需求。

这个项目的Matlab完整代码已封装成工具箱，包含以下核心函数：

• raceTrackTriangulation.m：赛道专用三角剖分
• dynamicPathSmoother.m：实时路径优化
• fsaeVelocityPlanner.m：速度剖面生成
• visualizeRacingPath.m：3D赛道可视化

在实际应用中，建议先使用example_shortTrack.m示例文件测试基础功能，再逐步移植到自己的系统中。记得根据赛车参数修改config/vehicleParams.json中的质量、轮胎等关键参数。