做迷宫类路径规划项目，很多人的第一反应都是上A*或者把地图栅格化之后用Dijkstra。在规整的网格环境里，这些确定性搜索算法确实好用，可一旦迷宫变得极其困难——通道比车辆自身宽度大不了多少、U形死角一个接一个、障碍物还是随机生成的——传统方法的效率就会断崖式下跌。后来我把RRT（Rapidly-exploring Random Tree，快速扩展随机树）算法用到这套场景里，配合Matlab做了完整Demo，实测下来无论迷宫怎么随机变化，只要参数调对，基本都能稳定找到可行路径。这篇文章就把整体思路、Matlab代码、调参经验和踩过的坑一次性讲清楚，适合正在做路径规划课设、机器人导航仿真，或者想入门采样类规划算法的读者。1. 为什么传统路径规划方法会在随机迷宫里“翻车”1.1 迷宫问题的结构特点先说清楚“极其困难的随机迷宫”到底难在哪。我做的测试环境是一个二维栅格地图，尺寸在100×100左右，墙的密度很高，通道宽度通常只有2到3个栅格。更关键的是迷宫由算法随机生成，没有什么“主路”和“支路”之分，大量的狭窄走廊、死胡同、回字形陷阱随机堆叠在一起，这种结构对路径规划算法极不友好。这类环境的本质问题是：可行通道在状态空间中占比极低，而且拓扑关系高度非结构化。通道之间互相缠绕，没有任何先验规则可循。你想让算法“动脑筋”判断哪个方向更有可能通向终点，它根本无从下手，因为墙后面是什么完全未知。栅格法在这里也容易踩坑。如果栅格粒度设得太大，那些两格宽的通道直接就消失了，物理上可行的路径在数学表示里就不存在；粒度设小一点，地图规模又会以平方级别膨胀，搜索耗时迅速失控。我在85×85的迷宫上试过5像素粒度的栅格化，光是构建邻接表就耗掉大半内存，路径搜索时间更是无法接受。1.2 A*、Dijkstra等确定性方法的局限A*的搜索效率高度依赖启发函数的质量。在开阔地图里，欧氏距离或曼哈顿距离能提供很有效的方向指引；但在迷宫场景下，启发值经常严重“失真”——明明终点就在墙对面，实际绕过去却要几千个格子，启发函数给出的距离估计和真实代价相差悬殊，算法就会大量扩展低价值节点，表现和一个盲目广搜没有本质区别。Dijkstra更不用说了，在迷宫环境里它基本是在做全图遍历，时间复杂度和地图面积直接挂钩。我拿30×30的小迷宫让Dijkstra跑，路径倒是能找到，耗时已经需要好几秒；换成60×60的随机迷宫，耗时直接变成分钟级，而且这个问题和硬件性能关系不大，纯粹是算法复杂度决定的。这引出一个关键结论：当环境的拓扑结构极度复杂时，任何基于“确定性枚举”的搜索策略都会遇到组合爆炸问题。这也是为什么我会转向采样类算法——它们不试图枚举所有可能性，而是通过随机采样的方式在状态空间里“抽奖”，用概率换时间。2. RRT快速扩展随机树：以随机性对抗复杂性的核心思路2.1 RRT的核心流程拆解RRT的思想可以用一个生活化类比来理解：想象你在一片完全黑暗、遍布障碍的森林里找人，你手里只有一条能自动伸缩的绳子。你每走一步就往随机方向甩一小段绳子，只要绳子没被障碍挡住，就沿着这个方向前进一点，然后把绳子另一头固定住。重复无数次之后，绳子的网络会逐渐覆盖整个森林，只要存在一条通路，这根绳子大概率最终会碰到目标。算法落到代码层面，每轮迭代就做四件事：随机采样一个点、在现有树上找到离它最近的节点、从最近节点朝采样点方向延伸一个固定步长、检测这段新路径是否撞障碍。如果没撞，新节点就加入树中；如果撞了，这一轮就放弃，重新采样。上面说的是最基础的RRT。实际工程里，我会额外引入一个目标偏置策略：每次采样时，以一定概率（比如10%）直接把目标点作为采样点，其余90%才做全图随机采样。这样做的目的是给树的生长施加一个“方向拉力”，避免树完全漫无目的地乱长，同时又保留了随机性去探索复杂通道。2.2 为什么RRT天生适合复杂迷宫RRT最迷人的地方在于它的概率完备性：只要迭代次数足够多，找到一条可行路径的概率趋近于1。这个性质不需要对地图做任何假设，管它是规整网格还是随机迷宫。原因很简单——随机采样点在整个自由空间里均匀分布，树的扩展方向又不受任何启发函数的误导，所以随着采样点数量的增加，树对自由空间的覆盖会越来越密，最终“必然”触及目标所在的连通分量。实际测试也验证了这一点。在通道宽度只有3个栅格的85×85随机迷宫里，RRT通常只需要几千次迭代就能找到路径，耗时在2到5秒之间，这个表现和A*在高密度迷宫里的表现形成了鲜明对比。另外RRT还有一个隐性优势：它对车辆的运动约束天然友好。在这类算法里，车辆的运动模型是作为“扩展规则”的一个输入存在的——每次步进的方向不是随便定的，而是车辆在当前状态下能够执行的方向。这意味着从仿真到实车时，只需要替换掉步进函数，算法骨架完全不用动。传统A*规划出来的路径常常是一堆直角折线，到了实车上还得再做一次运动约束校验，这部分工作RRT在结构上就替你省了。3. Matlab环境下的迷宫生成与参数设定3.1 用递归回溯算法生成随机迷宫测试迷宫我用的是经典的递归回溯算法（Recursive Backtracker）生成。这个算法的思路很直观：把每个格子视为一个房间，从起点出发，随机选择一个尚未访问的相邻房间，打通中间的墙，走过去，继续这个过程；如果当前房间周围没有未访问的邻居，就沿来路回溯。全部房间都访问过之后，迷宫就生成了。Matlab实现如下：function maze = generateMaze(rows, cols) maze = ones(rows*2+1, cols*2+1); visited = false(rows, cols); stack = [1, 1]; visited(1,1) = true; % 起点房间打通 maze(2, 2) = 0; while ~isempty(stack) current = stack(end,:); r = current(1); c = current(2); % 随机选择未访问邻居 neighbors = []; if r > 1 && ~visited(r-1, c) neighbors(end+1,:) = [r-1, c, 1]; end if r < rows && ~visited(r+1, c) neighbors(end+1,:) = [r+1, c, 2]; end if c > 1 && ~visited(r, c-1) neighbors(end+1,:) = [r, c-1, 3]; end if c < cols && ~visited(r, c+1) neighbors(end+1,:) = [r, c+1, 4]; end if ~isempty(neighbors) idx = randi(size(neighbors,1)); nr = neighbors(idx,1); nc = neighbors(idx,2); dir = neighbors(idx,3); % 打通当前房间与邻居之间的墙 if dir == 1 % 上 maze(2*r-1, 2*c) = 0; elseif dir == 2 % 下 maze(2*r+1, 2*c) = 0; elseif dir == 3 % 左 maze(2*r, 2*c-1) = 0; elseif dir == 4 % 右 maze(2*r, 2*c+1) = 0; end maze(2*nr, 2*nc) = 0; visited(nr, nc) = true; stack(end+1,:) = [nr, nc]; else stack(end,:) = []; % 回溯 end end end生成出来的迷宫是一个(2rows+1)×(2cols+1)的逻辑地图，值为1表示墙，0表示可通行的走廊。也就是说，如果你想让迷宫主体是85×85，实际的地图矩阵就是171×171。测试的时候我建议先从25×25的小迷宫开始，跑通之后再逐步挑战更大的尺寸。3.2 地图表示、碰撞检测与车辆模型简化路径规划代码里，地图统一用二值矩阵表示，车辆被简化为一个质点，实际车身宽度通过膨胀障碍物来处理。具体做法是：在生成地图之后，对所有障碍格执行一次形态学膨胀，把墙边界向外扩展若干个栅格，等效于车辆的“安全距离”。这样规划出来的路径即使在真实车辆执行时也不会擦墙。% 障碍物膨胀，确保车辆安全距离 se = strel('square', 7); % 7个栅格的膨胀核，相当于3格车身宽+2格安全余量 expandedMap = imdilate(maze, se);碰撞检测逻辑也依赖膨胀后的地图：在判断某个节点或某条路径线段是否可行时，只要线段经过的任意栅格在地图上的值为1，就判定为碰撞。线段检测用的是经典的Bresenham算法，遍历线段经过的所有栅格，速度够快，实现也简单。提示：膨胀核尺寸必须和你设定的小车半径强相关。我在测试中发现，如果膨胀尺寸过小，生成的路径虽然在地图上是可行的，但实际执行时车辆很容易蹭到墙边；膨胀过大又会把原本两格宽的通道完全堵死，导致算法找不到任何路径。具体尺寸需要针对你的车型反复试验。4. RRT路径规划核心模块的Matlab实现详解4.1 采样、最近邻与步进增长RRT的三板斧就是采样、找最近邻、步进扩展。先说采样模块，核心逻辑是目标偏置：每次生成随机数，如果小于偏置概率就直接返回目标点，否则在自由空间内均匀采样。自由空间的范围直接取地图矩阵的尺寸，简单高效。function [samplePoint] = samplePoint(map, goal, biasProb) if rand() < biasProb samplePoint = goal; return; end [rows, cols] = size(map); while true p = [randi(rows), randi(cols)]; if map(p(1), p(2)) == 0 samplePoint = p; return; end end end最近邻查找的逻辑也很直接：遍历树中所有节点，计算它们到采样点的欧氏距离，取最小值对应的那个节点。在Matlab的向量化加持下，这一步很快。但随着树节点的增多，遍历开销会线性增长，这就是后面要优化的重点。步进扩展是RRT的灵魂。给定最近邻节点和采样点，实际的步进方向是：从最近邻节点指向采样点的单位向量，乘以步长stepSize。注意这里有个关键细节：不能直接把采样点作为新节点加入树中，而是要走一小步。因为采样点可能离得很远，直接一步跨过去，中间路径很可能穿越障碍。步长是RRT最重要的参数之一，它直接决定了树的“伸展能力”，具体怎么调我会在下一节详细讲。function [newNode] = extendTree(map, nearestNode, samplePoint, stepSize) dist = norm(samplePoint - nearestNode); if dist < stepSize newNode = samplePoint; % 离得近就直接点对点 else direction = (samplePoint - nearestNode) / dist; newNode = round(nearestNode + direction * stepSize); end % 碰撞检测 if ~isCollisionFree(map, nearestNode, newNode) newNode = []; end end4.2 碰撞检测与到达目标的判断逻辑碰撞检测用Bresenham算法遍历两个节点之间的所有栅格，只要有一个栅格是墙就返回碰撞。这里有一个重要的工程细节：检测半径不能是0。因为车辆模型是有宽度的，即使两个节点之间的连线在地图上恰好穿过了空格，但在狭窄通道里，连线距离墙壁太近也会导致实际车辆过不去。所以我实际用的是“宽线检测”，把Bresenham遍历的每个点都检查一个3×3邻域，邻域内有墙即判为碰撞。function flag = isCollisionFree(map, node1, node2) flag = true; [xPoints, yPoints] = bresenham(node1(1), node1(2), node2(1), node2(2)); for i = 1:length(xPoints) x = xPoints(i); y = yPoints(i); % 检查3x3邻域 for dx = -1:1 for dy = -1:1 nx = x + dx; ny = y + dy; if nx < 1 || ny < 1 || nx > size(map,1) || ny > size(map,2) flag = false; return; end if map(nx, ny) == 1 flag = false; return; end end end end end到达目标的判断条件我做了两重冗余。最常用的方式是：当树中新增的节点距离目标点小于一个阈值（比如stepSize，或者再小一点）时，就直接把目标点作为终结点加入树，然后回溯生成路径。但如果迷宫通道特别诡异，新增节点离目标很近却隔着墙，这招就会失效。所以我额外加了一条规则：新节点加入树后，立即检测新节点到目标点的连线是否无碰撞。如果无碰撞，哪怕距离远一点，也可以直接把目标点连进树里，立刻终止搜索。function [pathFound, path] = checkGoal(map, tree, newNode, goal, goalThreshold) pathFound = false; path = []; if norm(newNode - goal) < goalThreshold || isCollisionFree(map, newNode, goal) tree(end+1) = newNode; pathFound = true; path = [newNode, goal]; end end4.3 完整可运行的RRT主程序把上面的模块拼起来，就是一个完整的RRT迷宫路径规划程序。下面是主循环的关键部分，完整代码我建议自己整理成一个函数：function [path, tree] = rrtPlan(map, start, goal, maxIter) % 参数配置 stepSize = 8; goalThreshold = 5; biasProb = 0.15; % 初始化树 tree = start; parent = -1; pathFound = false; for i = 1:maxIter sp = samplePoint(map, goal, biasProb); [nearestIdx, nearestNode] = findNearest(tree, sp); newNode = extendTree(map, nearestNode, sp, stepSize); if isempty(newNode) continue; end tree(end+1) = newNode; parent(end+1) = nearestIdx; % 检查是否到达目标 if norm(newNode - goal) < goalThreshold pathFound = true; tree(end+1) = goal; parent(end+1) = length(tree) - 1; break; end end % 从目标回溯生成路径 if pathFound path = []; idx = length(tree); while idx > 0 path = [tree(idx); path]; idx = parent(idx); end else path = []; warning('未能在最大迭代次数内找到路径'); end end注意这段代码里的一个细节：我在每一步扩展后没有做“当前新节点到目标点连线”的二次检测。如果你希望提高成功率，可以把4.2节中的checkGoal函数加进来，在每次成功加入新节点后额外调用一次。两者配合，成功率会有可感知的提升。5. 从能跑到跑好：迷宫路径规划调试踩坑记录5.1 步长与迭代次数的博弈步长是最容易出问题的参数。极端情况下，步长设得太小，树长得极其密集，一条长廊从头到尾可能要几千上千个节点，迭代次数很快耗尽；步长设得太大，又会出现“一步跨过窄通道”的尴尬局面——明明通道就挨着，但步长太长导致步进终点落在墙的另一边，碰撞检测直接否决。我的经验是：迷宫通道宽度为2到3个栅格时，步长建议取1.5到2倍通道宽度，也就是4到6个栅格。如果迷宫更大、通道更宽，可以按比例放大。另外最大迭代次数不要舍不得给，随机迷宫路径往往绕很远，我的测试配置是maxIter=10000，对于85×85的迷宫，实际找到路径通常只要2000到4000次迭代，这个余量是给极端随机情况保底的。5.2 狭窄通道下的采样策略问题迷宫场景里最常见的失败模式是：树沿着通道走了一段，但随机采样点总是落在墙外，导致树的扩展方向长期被“卡死”在某一条通道里，无法转入其他通道。这是纯粹随机采样在面对狭窄通道时的一个天然弱点——因为通道的宽度在整个地图面积里占的比例太小，随机点落到通道内的概率本来就很低。一个有效的补救方案是双向RRT：从起点和终点各长一棵树，两棵树交替扩展，互相把对方当作目标。这样做的好处是两棵树可以同时探索不同区域，一旦它们的距离小于某个阈值，就认为路径连通了。我在单向RRT需要4000次迭代才能找到的迷宫里，双向RRT通常只需要1500次左右。代价是代码复杂度翻倍，但对迷宫场景来说完全值得。5.3 目标偏置参数的经验取值区间目标偏置是一把双刃剑。偏置概率设得太小（比如小于0.02），树基本失去了方向感，纯粹靠运气漫游；偏置概率设得太大（比如大于0.3），树的扩展会被强烈吸引向目标方向，反而容易在遇到墙体阻碍时反复试探同一条死路，陷入局部振荡。调试中发现偏置概率在0.08到0.15之间比较稳。在这个区间内，树的扩展既有方向性，又保留了全局探索的能力。另外还有一个心法：偏置概率可以随迭代次数动态变化——迭代初期用小偏置，让树先充分铺开探索；迭代中期加大偏置，集中力量向目标推进。这算是一个性价比很高的“小魔改”。5.4 随机数种子的真随机陷阱RRT的随机性会带来一个很扎心的现象：同一份代码，这次运行能找到路径，下次运行可能就找不到。很多人在调试时会把失败归咎于算法不行，其实只是随机采样的运气问题。解决思路很简单，在程序启动时固定随机数种子（rng(42)），保证调试过程可复现；等算法稳定之后再随机化种子，去做统计测试。我实际统计过一组参数在某迷宫上的表现：固定种子下100次运行，成功95次；不固定种子则成功率会在88%到97%之间波动。这个数字说明两点：第一，参数没问题，成功率已经足够高；第二，任何RRT的单次运行结果都不能代表算法性能，要做多次实验取平均值才有说服力。6. RRT的进阶优化方向与工程化建议6.1 RRT*的代价函数与渐进最优特性基础RRT找到的路径通常弯弯曲曲，完全谈不上“最优”，因为它只保证能通，不保证路径短。RRT*的改进在于引入了重新布线机制：每次新增节点后，候选父节点不再局限于“最近邻”，而是在附近一定半径内寻找所有潜在父节点，选择使该节点代价最小的那个；同时对新节点附近的其他节点进行重连，看能否通过新节点缩短它们到起点的代价。代价被我定义为路径长度（累计步长之和）。RRT会随着迭代次数的增加，不断优化树中各节点的代价，因此路径质量会逐渐提升。代价是计算量显著提高，而且**如果迭代次数不够，RRT甚至可能比基础RRT更慢**——因为多做了很多无效的重连计算。迷宫场景下，我的建议是先用基础RRT快速找出一条路径，然后再用RRT去优化它，而不是一上来就上RRT。6.2 双向树、动态步长与平滑后处理双向RRT带来的成功率提升前面已经说了，这里补充一个动态步长的实现思路：在靠近目标时，自动将步长缩小一半；远离目标时恢复默认步长。这个策略能有效减少到达目标后的过冲问题。路径平滑也值得做。RRT产生的路径是多段折线，在机器人上执行会让电机频繁启停。最实用的后处理方法是路径剪枝：从起点开始，尝试直接连接更远的节点，如果这段连线无碰撞，就删掉中间的所有节点。反复剪枝几轮，路径通常会变得非常利落。如果需要曲率连续，还可以用三次样条拟合，但要注意拟合后的路径不能偏移到障碍物里，必须再做一次碰撞校验。6.3 从仿真到实车的注意事项仿真代码移植到实车时，有几个坑要提前规避。第一，仿真中车辆是理想点模型，实车则要重新计算质心位置和转弯半径，建议规划层的安全距离至少再加大20%；第二，仿真地图是静态的，实车环境里可能有动态障碍，RRT的随机采样特性可以较快适应局部地图变化，但如果障碍物运动太快，规划层只能负责生成参考路径，避障还得靠局部控制器；第三，路径重规划频率不要太高，否则车辆会频繁急转弯，反而增加执行风险。我在某项目里的做法是：规划层以0.5到1秒的周期调用RRT进行全局重规划，执行层用PID跟踪路径。测试下来，即使局部障碍突变，车辆也能在1到2秒内修正轨迹，整体表现比用A*时平滑不少。6.4 新方向的探索心得最近我在尝试把RRT与深度强化学习结合：训练一个小型策略网络，学习“哪些区域更容易产生优质采样点”，再用这个策略网络替代均匀随机采样。本质上是在保持RRT概率完备性的同时，把“探索”变得更聪明。目前效果还在验证中，但在有些迷宫上确实能把找到路径的平均迭代次数再降30%到40%。如果你有基础，这个方向值得跟一跟。写在最后从最初在迷宫里频繁“翻车”，到最终能稳定跑通各类随机迷宫，RRT给我的最大感受是：它不讲究精巧，讲究的是概率上的“磨”。在极其复杂的环境里，探索本身往往比聪明更重要。如果你也正在被迷宫路径规划的问题困扰，建议先把基础RRT跑通，再去折腾优化版本——先让路径出现，再让路径变得更好。这八个字，大概是我在这个项目里最想分享的一句话。
做迷宫类路径规划项目，很多人的第一反应都是上A*或者把地图栅格化之后用Dijkstra。在规整的网格环境里，这些确定性搜索算法确实好用，可一旦迷宫变得极其困难——通道比车辆自身宽度大不了多少、U形死角一个接一个、障碍物还是随机生成的——传统方法的效率就会断崖式下跌。后来我把RRT（Rapidly-exploring Random Tree，快速扩展随机树）算法用到这套场景里，配合Matlab做了完整Demo，实测下来无论迷宫怎么随机变化，只要参数调对，基本都能稳定找到可行路径。这篇文章就把整体思路、Matlab代码、调参经验和踩过的坑一次性讲清楚，适合正在做路径规划课设、机器人导航仿真，或者想入门采样类规划算法的读者。1. 为什么传统路径规划方法会在随机迷宫里“翻车”1.1 迷宫问题的结构特点先说清楚“极其困难的随机迷宫”到底难在哪。我做的测试环境是一个二维栅格地图，尺寸在100×100左右，墙的密度很高，通道宽度通常只有2到3个栅格。更关键的是迷宫由算法随机生成，没有什么“主路”和“支路”之分，大量的狭窄走廊、死胡同、回字形陷阱随机堆叠在一起，这种结构对路径规划算法极不友好。这类环境的本质问题是：可行通道在状态空间中占比极低，而且拓扑关系高度非结构化。通道之间互相缠绕，没有任何先验规则可循。你想让算法“动脑筋”判断哪个方向更有可能通向终点，它根本无从下手，因为墙后面是什么完全未知。栅格法在这里也容易踩坑。如果栅格粒度设得太大，那些两格宽的通道直接就消失了，物理上可行的路径在数学表示里就不存在；粒度设小一点，地图规模又会以平方级别膨胀，搜索耗时迅速失控。我在85×85的迷宫上试过5像素粒度的栅格化，光是构建邻接表就耗掉大半内存，路径搜索时间更是无法接受。1.2 A*、Dijkstra等确定性方法的局限A*的搜索效率高度依赖启发函数的质量。在开阔地图里，欧氏距离或曼哈顿距离能提供很有效的方向指引；但在迷宫场景下，启发值经常严重“失真”——明明终点就在墙对面，实际绕过去却要几千个格子，启发函数给出的距离估计和真实代价相差悬殊，算法就会大量扩展低价值节点，表现和一个盲目广搜没有本质区别。Dijkstra更不用说了，在迷宫环境里它基本是在做全图遍历，时间复杂度和地图面积直接挂钩。我拿30×30的小迷宫让Dijkstra跑，路径倒是能找到，耗时已经需要好几秒；换成60×60的随机迷宫，耗时直接变成分钟级，而且这个问题和硬件性能关系不大，纯粹是算法复杂度决定的。这引出一个关键结论：当环境的拓扑结构极度复杂时，任何基于“确定性枚举”的搜索策略都会遇到组合爆炸问题。这也是为什么我会转向采样类算法——它们不试图枚举所有可能性，而是通过随机采样的方式在状态空间里“抽奖”，用概率换时间。2. RRT快速扩展随机树：以随机性对抗复杂性的核心思路2.1 RRT的核心流程拆解RRT的思想可以用一个生活化类比来理解：想象你在一片完全黑暗、遍布障碍的森林里找人，你手里只有一条能自动伸缩的绳子。你每走一步就往随机方向甩一小段绳子，只要绳子没被障碍挡住，就沿着这个方向前进一点，然后把绳子另一头固定住。重复无数次之后，绳子的网络会逐渐覆盖整个森林，只要存在一条通路，这根绳子大概率最终会碰到目标。算法落到代码层面，每轮迭代就做四件事：随机采样一个点、在现有树上找到离它最近的节点、从最近节点朝采样点方向延伸一个固定步长、检测这段新路径是否撞障碍。如果没撞，新节点就加入树中；如果撞了，这一轮就放弃，重新采样。上面说的是最基础的RRT。实际工程里，我会额外引入一个目标偏置策略：每次采样时，以一定概率（比如10%）直接把目标点作为采样点，其余90%才做全图随机采样。这样做的目的是给树的生长施加一个“方向拉力”，避免树完全漫无目的地乱长，同时又保留了随机性去探索复杂通道。2.2 为什么RRT天生适合复杂迷宫RRT最迷人的地方在于它的概率完备性：只要迭代次数足够多，找到一条可行路径的概率趋近于1。这个性质不需要对地图做任何假设，管它是规整网格还是随机迷宫。原因很简单——随机采样点在整个自由空间里均匀分布，树的扩展方向又不受任何启发函数的误导，所以随着采样点数量的增加，树对自由空间的覆盖会越来越密，最终“必然”触及目标所在的连通分量。实际测试也验证了这一点。在通道宽度只有3个栅格的85×85随机迷宫里，RRT通常只需要几千次迭代就能找到路径，耗时在2到5秒之间，这个表现和A*在高密度迷宫里的表现形成了鲜明对比。另外RRT还有一个隐性优势：它对车辆的运动约束天然友好。在这类算法里，车辆的运动模型是作为“扩展规则”的一个输入存在的——每次步进的方向不是随便定的，而是车辆在当前状态下能够执行的方向。这意味着从仿真到实车时，只需要替换掉步进函数，算法骨架完全不用动。传统A*规划出来的路径常常是一堆直角折线，到了实车上还得再做一次运动约束校验，这部分工作RRT在结构上就替你省了。3. Matlab环境下的迷宫生成与参数设定3.1 用递归回溯算法生成随机迷宫测试迷宫我用的是经典的递归回溯算法（Recursive Backtracker）生成。这个算法的思路很直观：把每个格子视为一个房间，从起点出发，随机选择一个尚未访问的相邻房间，打通中间的墙，走过去，继续这个过程；如果当前房间周围没有未访问的邻居，就沿来路回溯。全部房间都访问过之后，迷宫就生成了。Matlab实现如下：function maze = generateMaze(rows, cols) maze = ones(rows*2+1, cols*2+1); visited = false(rows, cols); stack = [1, 1]; visited(1,1) = true; % 起点房间打通 maze(2, 2) = 0; while ~isempty(stack) current = stack(end,:); r = current(1); c = current(2); % 随机选择未访问邻居 neighbors = []; if r > 1 && ~visited(r-1, c) neighbors(end+1,:) = [r-1, c, 1]; end if r < rows && ~visited(r+1, c) neighbors(end+1,:) = [r+1, c, 2]; end if c > 1 && ~visited(r, c-1) neighbors(end+1,:) = [r, c-1, 3]; end if c < cols && ~visited(r, c+1) neighbors(end+1,:) = [r, c+1, 4]; end if ~isempty(neighbors) idx = randi(size(neighbors,1)); nr = neighbors(idx,1); nc = neighbors(idx,2); dir = neighbors(idx,3); % 打通当前房间与邻居之间的墙 if dir == 1 % 上 maze(2*r-1, 2*c) = 0; elseif dir == 2 % 下 maze(2*r+1, 2*c) = 0; elseif dir == 3 % 左 maze(2*r, 2*c-1) = 0; elseif dir == 4 % 右 maze(2*r, 2*c+1) = 0; end maze(2*nr, 2*nc) = 0; visited(nr, nc) = true; stack(end+1,:) = [nr, nc]; else stack(end,:) = []; % 回溯 end end end生成出来的迷宫是一个(2rows+1)×(2cols+1)的逻辑地图，值为1表示墙，0表示可通行的走廊。也就是说，如果你想让迷宫主体是85×85，实际的地图矩阵就是171×171。测试的时候我建议先从25×25的小迷宫开始，跑通之后再逐步挑战更大的尺寸。3.2 地图表示、碰撞检测与车辆模型简化路径规划代码里，地图统一用二值矩阵表示，车辆被简化为一个质点，实际车身宽度通过膨胀障碍物来处理。具体做法是：在生成地图之后，对所有障碍格执行一次形态学膨胀，把墙边界向外扩展若干个栅格，等效于车辆的“安全距离”。这样规划出来的路径即使在真实车辆执行时也不会擦墙。% 障碍物膨胀，确保车辆安全距离 se = strel('square', 7); % 7个栅格的膨胀核，相当于3格车身宽+2格安全余量 expandedMap = imdilate(maze, se);碰撞检测逻辑也依赖膨胀后的地图：在判断某个节点或某条路径线段是否可行时，只要线段经过的任意栅格在地图上的值为1，就判定为碰撞。线段检测用的是经典的Bresenham算法，遍历线段经过的所有栅格，速度够快，实现也简单。提示：膨胀核尺寸必须和你设定的小车半径强相关。我在测试中发现，如果膨胀尺寸过小，生成的路径虽然在地图上是可行的，但实际执行时车辆很容易蹭到墙边；膨胀过大又会把原本两格宽的通道完全堵死，导致算法找不到任何路径。具体尺寸需要针对你的车型反复试验。4. RRT路径规划核心模块的Matlab实现详解4.1 采样、最近邻与步进增长RRT的三板斧就是采样、找最近邻、步进扩展。先说采样模块，核心逻辑是目标偏置：每次生成随机数，如果小于偏置概率就直接返回目标点，否则在自由空间内均匀采样。自由空间的范围直接取地图矩阵的尺寸，简单高效。function [samplePoint] = samplePoint(map, goal, biasProb) if rand() < biasProb samplePoint = goal; return; end [rows, cols] = size(map); while true p = [randi(rows), randi(cols)]; if map(p(1), p(2)) == 0 samplePoint = p; return; end end end最近邻查找的逻辑也很直接：遍历树中所有节点，计算它们到采样点的欧氏距离，取最小值对应的那个节点。在Matlab的向量化加持下，这一步很快。但随着树节点的增多，遍历开销会线性增长，这就是后面要优化的重点。步进扩展是RRT的灵魂。给定最近邻节点和采样点，实际的步进方向是：从最近邻节点指向采样点的单位向量，乘以步长stepSize。注意这里有个关键细节：不能直接把采样点作为新节点加入树中，而是要走一小步。因为采样点可能离得很远，直接一步跨过去，中间路径很可能穿越障碍。步长是RRT最重要的参数之一，它直接决定了树的“伸展能力”，具体怎么调我会在下一节详细讲。function [newNode] = extendTree(map, nearestNode, samplePoint, stepSize) dist = norm(samplePoint - nearestNode); if dist < stepSize newNode = samplePoint; % 离得近就直接点对点 else direction = (samplePoint - nearestNode) / dist; newNode = round(nearestNode + direction * stepSize); end % 碰撞检测 if ~isCollisionFree(map, nearestNode, newNode) newNode = []; end end4.2 碰撞检测与到达目标的判断逻辑碰撞检测用Bresenham算法遍历两个节点之间的所有栅格，只要有一个栅格是墙就返回碰撞。这里有一个重要的工程细节：检测半径不能是0。因为车辆模型是有宽度的，即使两个节点之间的连线在地图上恰好穿过了空格，但在狭窄通道里，连线距离墙壁太近也会导致实际车辆过不去。所以我实际用的是“宽线检测”，把Bresenham遍历的每个点都检查一个3×3邻域，邻域内有墙即判为碰撞。function flag = isCollisionFree(map, node1, node2) flag = true; [xPoints, yPoints] = bresenham(node1(1), node1(2), node2(1), node2(2)); for i = 1:length(xPoints) x = xPoints(i); y = yPoints(i); % 检查3x3邻域 for dx = -1:1 for dy = -1:1 nx = x + dx; ny = y + dy; if nx < 1 || ny < 1 || nx > size(map,1) || ny > size(map,2) flag = false; return; end if map(nx, ny) == 1 flag = false; return; end end end end end到达目标的判断条件我做了两重冗余。最常用的方式是：当树中新增的节点距离目标点小于一个阈值（比如stepSize，或者再小一点）时，就直接把目标点作为终结点加入树，然后回溯生成路径。但如果迷宫通道特别诡异，新增节点离目标很近却隔着墙，这招就会失效。所以我额外加了一条规则：新节点加入树后，立即检测新节点到目标点的连线是否无碰撞。如果无碰撞，哪怕距离远一点，也可以直接把目标点连进树里，立刻终止搜索。function [pathFound, path] = checkGoal(map, tree, newNode, goal, goalThreshold) pathFound = false; path = []; if norm(newNode - goal) < goalThreshold || isCollisionFree(map, newNode, goal) tree(end+1) = newNode; pathFound = true; path = [newNode, goal]; end end4.3 完整可运行的RRT主程序把上面的模块拼起来，就是一个完整的RRT迷宫路径规划程序。下面是主循环的关键部分，完整代码我建议自己整理成一个函数：function [path, tree] = rrtPlan(map, start, goal, maxIter) % 参数配置 stepSize = 8; goalThreshold = 5; biasProb = 0.15; % 初始化树 tree = start; parent = -1; pathFound = false; for i = 1:maxIter sp = samplePoint(map, goal, biasProb); [nearestIdx, nearestNode] = findNearest(tree, sp); newNode = extendTree(map, nearestNode, sp, stepSize); if isempty(newNode) continue; end tree(end+1) = newNode; parent(end+1) = nearestIdx; % 检查是否到达目标 if norm(newNode - goal) < goalThreshold pathFound = true; tree(end+1) = goal; parent(end+1) = length(tree) - 1; break; end end % 从目标回溯生成路径 if pathFound path = []; idx = length(tree); while idx > 0 path = [tree(idx); path]; idx = parent(idx); end else path = []; warning('未能在最大迭代次数内找到路径'); end end注意这段代码里的一个细节：我在每一步扩展后没有做“当前新节点到目标点连线”的二次检测。如果你希望提高成功率，可以把4.2节中的checkGoal函数加进来，在每次成功加入新节点后额外调用一次。两者配合，成功率会有可感知的提升。5. 从能跑到跑好：迷宫路径规划调试踩坑记录5.1 步长与迭代次数的博弈步长是最容易出问题的参数。极端情况下，步长设得太小，树长得极其密集，一条长廊从头到尾可能要几千上千个节点，迭代次数很快耗尽；步长设得太大，又会出现“一步跨过窄通道”的尴尬局面——明明通道就挨着，但步长太长导致步进终点落在墙的另一边，碰撞检测直接否决。我的经验是：迷宫通道宽度为2到3个栅格时，步长建议取1.5到2倍通道宽度，也就是4到6个栅格。如果迷宫更大、通道更宽，可以按比例放大。另外最大迭代次数不要舍不得给，随机迷宫路径往往绕很远，我的测试配置是maxIter=10000，对于85×85的迷宫，实际找到路径通常只要2000到4000次迭代，这个余量是给极端随机情况保底的。5.2 狭窄通道下的采样策略问题迷宫场景里最常见的失败模式是：树沿着通道走了一段，但随机采样点总是落在墙外，导致树的扩展方向长期被“卡死”在某一条通道里，无法转入其他通道。这是纯粹随机采样在面对狭窄通道时的一个天然弱点——因为通道的宽度在整个地图面积里占的比例太小，随机点落到通道内的概率本来就很低。一个有效的补救方案是双向RRT：从起点和终点各长一棵树，两棵树交替扩展，互相把对方当作目标。这样做的好处是两棵树可以同时探索不同区域，一旦它们的距离小于某个阈值，就认为路径连通了。我在单向RRT需要4000次迭代才能找到的迷宫里，双向RRT通常只需要1500次左右。代价是代码复杂度翻倍，但对迷宫场景来说完全值得。5.3 目标偏置参数的经验取值区间目标偏置是一把双刃剑。偏置概率设得太小（比如小于0.02），树基本失去了方向感，纯粹靠运气漫游；偏置概率设得太大（比如大于0.3），树的扩展会被强烈吸引向目标方向，反而容易在遇到墙体阻碍时反复试探同一条死路，陷入局部振荡。调试中发现偏置概率在0.08到0.15之间比较稳。在这个区间内，树的扩展既有方向性，又保留了全局探索的能力。另外还有一个心法：偏置概率可以随迭代次数动态变化——迭代初期用小偏置，让树先充分铺开探索；迭代中期加大偏置，集中力量向目标推进。这算是一个性价比很高的“小魔改”。5.4 随机数种子的真随机陷阱RRT的随机性会带来一个很扎心的现象：同一份代码，这次运行能找到路径，下次运行可能就找不到。很多人在调试时会把失败归咎于算法不行，其实只是随机采样的运气问题。解决思路很简单，在程序启动时固定随机数种子（rng(42)），保证调试过程可复现；等算法稳定之后再随机化种子，去做统计测试。我实际统计过一组参数在某迷宫上的表现：固定种子下100次运行，成功95次；不固定种子则成功率会在88%到97%之间波动。这个数字说明两点：第一，参数没问题，成功率已经足够高；第二，任何RRT的单次运行结果都不能代表算法性能，要做多次实验取平均值才有说服力。6. RRT的进阶优化方向与工程化建议6.1 RRT*的代价函数与渐进最优特性基础RRT找到的路径通常弯弯曲曲，完全谈不上“最优”，因为它只保证能通，不保证路径短。RRT*的改进在于引入了重新布线机制：每次新增节点后，候选父节点不再局限于“最近邻”，而是在附近一定半径内寻找所有潜在父节点，选择使该节点代价最小的那个；同时对新节点附近的其他节点进行重连，看能否通过新节点缩短它们到起点的代价。代价被我定义为路径长度（累计步长之和）。RRT会随着迭代次数的增加，不断优化树中各节点的代价，因此路径质量会逐渐提升。代价是计算量显著提高，而且**如果迭代次数不够，RRT甚至可能比基础RRT更慢**——因为多做了很多无效的重连计算。迷宫场景下，我的建议是先用基础RRT快速找出一条路径，然后再用RRT去优化它，而不是一上来就上RRT。6.2 双向树、动态步长与平滑后处理双向RRT带来的成功率提升前面已经说了，这里补充一个动态步长的实现思路：在靠近目标时，自动将步长缩小一半；远离目标时恢复默认步长。这个策略能有效减少到达目标后的过冲问题。路径平滑也值得做。RRT产生的路径是多段折线，在机器人上执行会让电机频繁启停。最实用的后处理方法是路径剪枝：从起点开始，尝试直接连接更远的节点，如果这段连线无碰撞，就删掉中间的所有节点。反复剪枝几轮，路径通常会变得非常利落。如果需要曲率连续，还可以用三次样条拟合，但要注意拟合后的路径不能偏移到障碍物里，必须再做一次碰撞校验。6.3 从仿真到实车的注意事项仿真代码移植到实车时，有几个坑要提前规避。第一，仿真中车辆是理想点模型，实车则要重新计算质心位置和转弯半径，建议规划层的安全距离至少再加大20%；第二，仿真地图是静态的，实车环境里可能有动态障碍，RRT的随机采样特性可以较快适应局部地图变化，但如果障碍物运动太快，规划层只能负责生成参考路径，避障还得靠局部控制器；第三，路径重规划频率不要太高，否则车辆会频繁急转弯，反而增加执行风险。我在某项目里的做法是：规划层以0.5到1秒的周期调用RRT进行全局重规划，执行层用PID跟踪路径。测试下来，即使局部障碍突变，车辆也能在1到2秒内修正轨迹，整体表现比用A*时平滑不少。6.4 新方向的探索心得最近我在尝试把RRT与深度强化学习结合：训练一个小型策略网络，学习“哪些区域更容易产生优质采样点”，再用这个策略网络替代均匀随机采样。本质上是在保持RRT概率完备性的同时，把“探索”变得更聪明。目前效果还在验证中，但在有些迷宫上确实能把找到路径的平均迭代次数再降30%到40%。如果你有基础，这个方向值得跟一跟。写在最后从最初在迷宫里频繁“翻车”，到最终能稳定跑通各类随机迷宫，RRT给我的最大感受是：它不讲究精巧，讲究的是概率上的“磨”。在极其复杂的环境里，探索本身往往比聪明更重要。如果你也正在被迷宫路径规划的问题困扰，建议先把基础RRT跑通，再去折腾优化版本——先让路径出现，再让路径变得更好。这八个字，大概是我在这个项目里最想分享的一句话。