控制理论系列讲完了从今天开始进入运动规划领域。这个系列大概会写十几篇把规划算法从头到尾讲一遍。运动规划是机器人最烧脑的模块之一。说白了就是回答一个问题机器人怎么从A点到达B点同时不撞到任何东西这个问题看似简单但根据场景不同解法天差地别。工业机械臂在固定工位搬东西和自动驾驶汽车在城市里穿梭用的规划算法完全不是一个路数。今天先做一个全景式的概述把运动规划的分类、核心概念和算法框架理清楚。后面十几篇会逐个展开。一、运动规划的本质运动规划的数学定义很简洁给定一个构型空间C和障碍物空间C_obs找到一条从起始构型q_start到目标构型q_goal的无碰撞路径。构型空间Configuration SpaceC-space是关键概念。一个n自由度机器人的构型空间是n维的——每个维度对应一个关节角度或位移。障碍物在构型空间里会变成膨胀后的障碍物区域C_obs。膨胀的量等于机器人的半径——这样机器人就可以被当作一个点来处理。# 构型空间的基本概念 # 2D平面上的点机器人C R^2 # 2D平面上的移动机器人含朝向C R^2 × S^1 # 6轴机械臂C R^6每个维度是一个关节角度 # 自由度越多构型空间维度越高 # 障碍物膨胀示例 # 圆形机器人半径r在2D空间 # 原始障碍物 → 膨胀r → 机器人简化为点为什么要在构型空间做规划而不是笛卡尔空间因为构型空间把机器人简化成了一个点。碰撞检测变成了这个点是否在障碍物区域内的问题比直接处理机器人的几何形状简单得多。代价是维度变高了——一个6轴机械臂的构型空间是6维的但这比在3D工作空间里处理一个复杂形状的碰撞检测要方便。二、规划算法的三大分类运动规划算法按工作方式分三大类1. 全局规划离线规划全局规划假设环境完全已知在规划前就把整条路径算好。特点环境信息完整已知地图、已知障碍物位置规划一次执行多次追求最优性最短路径、最少时间计算时间可以长一些秒级甚至分钟级典型算法Dijkstra、A、DLite、PRM、RRT*适用场景仓储AGV地图已知、机械臂搬运工件位置固定、自动驾驶的全局路线规划。2. 局部规划在线规划局部规划只关注机器人周围一小片区域实时生成局部路径。特点环境信息不完整只知道传感器能看到的范围每个控制周期都要重新规划追求实时性毫秒级响应不保证全局最优典型算法DWA、TEB、人工势场法、Lattice Planner适用场景移动机器人避障动态行人、无人机避障未知环境、机械臂在杂乱环境中运动。3. 反应式规划反应式规划不做规划而是根据当前传感器输入直接输出控制指令。相当于一个从传感器到执行器的映射函数。特点极简计算微秒级没有显式的路径概念对突发情况响应最快容易陷入局部极小值典型算法人工势场法也可以归入局部规划、向量场直方图VFH、Bug算法适用场景紧急避障、简单场景下的导航、和其他规划方法配合使用。三、全局规划的两大流派全局规划算法又分两大流派图搜索和采样规划。图搜索Graph Search思路把连续空间离散化成图网格或节点然后用图搜索算法找最短路径。代表算法Dijkstra、A、DLite优点能找到最优解如果存在算法成熟理论完备实现相对简单缺点维度灾难——空间维度越高网格数量指数增长离散化误差——路径只能沿网格方向走不适合高维空间比如7轴机械臂的构型空间采样规划Sampling-based思路在构型空间里随机采样点用采样的点构建路线图roadmap在路线图上搜索路径。代表算法PRM、RRT、RRT、BIT优点不受维度影响——高维空间也能用不需要离散化——处理连续空间概率完备——采样足够多一定能找到解如果存在缺点路径质量不稳定——每次运行结果不同狭窄通道难以通过——随机采样很难命中狭窄通道最优性需要额外保证RRT*等渐进最优算法所谓概率完备是指如果解存在随着采样次数趋向无穷找到解的概率趋向1。这和A*那种一定能找到最优解的确定完备不同。工程上概率完备够用了——只要你给它足够的时间它几乎一定能找到解。四、规划系统的工程架构实际工程中运动规划通常是一个多层架构全局规划器低频1-10Hz ↓ 全局路径 局部规划器中频10-50Hz ↓ 局部轨迹 反应式层高频100-1000Hz ↓ 控制指令 执行器全局规划器在后台运行每隔几秒更新一次全局路径。局部规划器根据全局路径和传感器数据实时生成可执行的局部轨迹。反应式层处理紧急情况——比如突然出现的障碍物直接输出避障指令。这种分层架构的好处是每一层关注不同时间尺度的问题互不干扰。全局规划不用操心实时性反应式层不用操心全局最优。之前做AMR项目的团队就是这种架构。全局用A*在已知地图上规划局部用DWA实时避障最底层还有一个反应式急停——超声波检测到0.3m内有障碍物就直接停车。三层之间通过路径-轨迹-指令三级传递信息。全局路径是 waypoints 列表局部规划器把 waypoints 转成速度指令反应式层在紧急情况下覆盖速度指令。还有一个细节全局规划器通常跑在工控机上算力充足局部规划器跑在实时控制器上保证时序反应式层直接跑在安全PLC或MCU上最高优先级。五、规划算法的评估指标面试时经常被问到你怎么评估一个规划算法好不好。核心指标有这几个完备性如果解存在算法能保证找到吗概率完备RRT还是确定完备A*最优性找到的是最优解吗最优Dijkstra、渐进最优RRT*、还是次优DWA计算效率规划一次要多久全局规划可以慢一些秒级局部规划必须快毫秒级。路径质量路径长度、平滑度、离障碍物距离。这些直接影响后续轨迹跟踪的效果。一条贴着障碍物走的最短路径在实际执行时可能因为定位误差而碰撞。所以工程上通常偏好离障碍物远一点的路径即使它更长。可扩展性维度增加时性能怎么变高维空间用采样规划低维空间用图搜索。鲁棒性环境有微小变化时路径质量会不会剧烈下降有些算法对环境变化很敏感每次都要重新规划有些算法能在环境变化后快速调整。六、面试实战Q构型空间和工作空间有什么区别A工作空间是机器人末端运动的物理空间通常是2D或3D。构型空间是描述机器人所有关节状态的抽象空间维度等于自由度数。一个6轴机械臂的工作空间是3D的但构型空间是6D的。Q为什么不在工作空间直接规划A因为机器人在工作空间不是一个点——它有体积、有形状。在构型空间里机器人被简化成一个点碰撞检测变成了点是否在障碍物区域内的问题。虽然构型空间维度高但处理起来反而更统一。Q全局规划和局部规划怎么配合A全局规划给出粗略路径走哪条路局部规划负责细节怎么避眼前的障碍。局部规划偏离全局路径太远时触发全局重新规划。工程上还有一个常见做法全局规划给出的路径作为局部规划的参考线局部规划在参考线附近搜索最优轨迹。小结运动规划分三大类全局规划已知环境求最优路径、局部规划实时避障保证安全、反应式规划紧急响应极速避障。全局规划分两大流派图搜索低维最优和采样规划高维可行。工程上通常分层使用——全局局部反应式三层架构各层各司其职。下一篇开始深入图搜索从最基础的Dijkstra算法讲起。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第205篇 控制理论面试高频题——面试官最爱问的15个控制问题下一篇预告第207篇 图搜索基础——状态空间离散化的思路有任何问题欢迎评论区留言我会尽量回复。