引言导读：
- 本邮对扫地机器人项目路径规划算法岗位常见面试题做出梳理
- 澄清路径规划岗位与slam岗位工作性质差异
- 本书以扫地机器人为载体阐述，但技术方法论并非局限于扫地机器人单一品类，其核心工程逻辑与技术方案可直接引申借鉴至更广泛的服务机器人场景：包括割草机器人、空气净化机器人、泳池清洁机器人、家用服务机器人、消杀机器人等，从室内到户外、从清洁到服务的多类场景中，算法技术储备、工程化适配方法、系统架构设计、集成逻辑均可复用，掌握扫地机器人技术即掌握了服务机器人研发的底层通用能力。
TO：人事部（H工）
CC：X总
Hi H工,
今天已完成路径规划算法岗位候选人的技术面试，通过一人，请H工继续跟进协同X总时间进行二面
整体沟通过程如下
请做一个简短的自我介绍
-面试官，您好！我姓N，19年开始从事机器人行业，在某西科技主要研发仓储AMR机器人，21年加入某石科技做清洁机器人产品开发，深度参与了T7、J20等4款产品型号的研发。至今共7年算法开发经验，我的技术栈主要包括ROS/C++，算法方面便是常用的全局及局部路径规划，如A*/Dijkstra/DWA等，运动控制主要是PID、LQR及MPC，这些都比较熟悉。
您好，N工，接下来我们先聊一聊具体算法技术，之后，再聊产品，分两部分交流。您首先介绍一下对A*算法的理解？
-好的，A*算法是广度优先搜索思想，基于栅格地图实现全局A-B两点间最短路径规划，一般A点即机器人当前位置-起点，B点为目标点。
-起点、目标点、栅格图作为A*算法的3个基础输入参数，栅格图至少可以表达未知、占据、通行三种单元信息，考虑机器人本体大小，栅格图中占据栅格需要进行代价计算、膨胀处理，即我们常称的CostMap。膨胀范围需要结合栅格分辨率及本体大小共同考量。
-算法过程有三个关键元素，开启列表、关闭列表、移动权重公式F=G+H。开启列表主要存储机器人可移动节点，关闭列表主要存储机器人禁止移动节点，如障碍栅格位置节点，开启列表中每个可移动节点需要进行计算与更新移动权重F，G表达常量移动代价，H一般有两种取法，节点与目标点间欧式距离或曼哈顿距离，H代价的存在，也使其成为启发式广度搜索。
-算法启动首先以当前位置节点为中心（默认为最小移动代价），计算其8邻域或4邻域节点，将可通行节点记录父节点与计算权重F后放置开启列表，如某节点已存在于开启列表需要更新其移动权重（更新项为基于当前父节点的常量代价G）与父节点，不可通行节点放置关闭列表。
-每次开启列表pop出最小移动代价节点，作为中心节点，进行邻域计算与权重计算，如此循环迭代，直至邻域中检测到目标节点。
-最终，通过父节点链条回溯，则得到一条A-B点间连续的最短路径。
您对A算法做过哪些方面的优化吗？
-一是，开启列表每次获取最小移动代价节点，可用最小堆或优先队列实现，提升检索效率。
二是，A最短路径只是理论最优，会存在起点与目标点间，即使无障碍物但存在拐点，并非一条直线直接到达的情况。对于规划路径结果可以进一步优化，我曾用弗洛伊德路径平滑思路进行处理，思路是，首先设定当前拐点，默认为起点，其次设定检测点，默认为终点。计算当前拐点与检测点之间栅格直线，直线所通过栅格，如果全部为可通行状态，则剔除当前拐点与检测点之间所有节点，如果存在障碍物，则检测点-1向当前拐点移动再次检测，直至满足条件或-1节点为当前拐点，，之后，当前拐点+1，重新以终点为检测点进行检测，如此迭代，直至当前拐点+1为终点，则处理完毕。在该逻辑下，连续的稠密路径将转换为仅保留绕开障碍物的拐点路径。
Dijkstra算法和A有什么异同？
-Dijkstra同样是广度优先搜索思想，但不同于A，并没有启发代价考量，它主要考虑A-B间连通状况，并不追求路径最短。可以简单理解，A*算法中H代价=0，即等价于Dijkstra，搜索过程是以起点为中心扩散泛洪式搜索。
你还了解哪些A算法的变种吗？
-双向A*，主要提升搜索效率，在A过程中是以起点开始单向搜索，双向A*，也就是在搜索过程中，可以同步的以终点反向向起点同时搜索，当搜索节点互相重叠时，以两条路径进行叠加拼接，获取一条完整的路径。
-以及Hybird A*，加入了机器人运动约束，搜索节点的运算不再是通过邻域计算，而是，通过运动模型。A*仅可以对路径节点位置规划，Hybird A、*同时也可以对姿态进行规划，但对应的算法效率相对变低。
请简述一下DWA算法？
DWA是基于动态窗口的局部路径规划算法
它的核心思想是“在有限的时间内，从一堆可行的速度里挑出最好的一个”。它不直接规划具体的轨迹点，而是直接在速度空间（线速度和角速度）即窗口中进行采样和评估。可以分为三个步骤来理解：
第一步：确定“动态窗口”（筛选可行速度）
机器人不能想怎么动就怎么动，它受到物理和环境的多重限制。DWA 会在速度空间中划出一个合法的“窗口”，只有落在这个窗口内的速度组合，这个窗口由三个条件取交集得到：
机器人自身的极限速度：比如电机最大能跑多快
电机的加速度限制：考虑到上一时刻的速度，当前周期内加速或减速不能超过电机的能力
安全刹车距离：这是最关键的一点。机器人在当前速度下，必须保证能在撞到障碍物之前完全刹停。如果某个速度会导致刹车不及，就会被直接剔除。
第二步：轨迹推演与评分（预测未来）
对于动态窗口内留下的每一组速度，算法会假设机器人在接下来的一小段时间内保持这个速度不变，从而推演出一条模拟轨迹。然后，通过一个评价函数给这些轨迹打分。
标准的评价函数通由三部分组成：
G(v,ω)=α⋅heading+β⋅dist+γ⋅vel
其含义是：
heading（方位角代价）：轨迹终点朝向与目标点的夹角。简单说就是谁离终点方向更近，分越高。
dist（障碍物距离代价）：轨迹上离最近障碍物的距离。离障碍物越远，分越高（保证安全）。
vel（速度代价）：当前的线速度大小。跑得越快，分越高（保证效率）。
α,β,γ 是权重系数，用来根据实际场景调整机器人的行为偏好（比如狭窄环境就把 β 调大，空旷环境就把 γ 调大）。
第三步：执行最优解
计算完所有模拟轨迹的分数后，算法会选择得分最高的那一组速度，下发给底层的电机控制器去执行。到了下一个控制周期，再重新重复上述过程。
您是如何调试pid参数的？
呵呵，一般就是手动试，先调p后i再d。
可以的，我们接下来聊一聊产品工程。在扫地机器人中，您是如何规划它的弓字形作业路线的？
-首先弓字型路线的规划，也是基于已知栅格的地图的规划形式。
-整体上可以分为两个步骤：一是确定弓字形路线点对，二是将弓字形路线点对进行串联。
-确定弓字形路线点对的过程是，比如我们将地图从左向右逐栅格进行遍历，每次遇到（可通行&不可通行-1）确认为一对有效点对进行记录存储，当然这里我们考虑有效的最短弓字路线约束条件，比如小于1个机身直径我们认为过短则放弃记录。在同一行的遍历中，是有可能记录多个点对的，当遍历完一行后，开始下一行的遍历，我们可以默认由上向下的遍历顺序，每一行之间都有一定的间隔，这个间隔一般要考虑机器的清扫滚刷直径，理论上等同于一个直径，但我们往往稍微取小于一个滚刷直径，使它的清扫路径有部分重叠，避免由于外在干扰或精度问题，导致漏扫。如此迭代，直至完成全局遍历，便获取到了地图上弓字形路径的所有拐点。
-之后将弓字形拐点进行串联，变为有序路径，首先以机器人当前位置为当前节点，进行泛洪式搜索，获取到连通的最近拐点A，检查当前点与拐点A之间的直通性，如存在障碍则需由A*路径替代当前节点与A之间的路径，如直通则直接保留A节点，之后以该拐点的对点即A‘为起点，再次进行搜索，如此迭代，直至完成所有点对的串联或无法再搜索到有效点对。
在扫地机产品中，有基于地图进行房间区域分割的功能，是您负责开发吗？请简述一下实现方案
-主要4个步骤。
-1.首先这里我们用到了opencv库，对地图墙体进行直线提取，获取到所有直线信息。
-2.之后将所有直线进行双端延长，延长距离即可等价普遍房门宽度，比如1m，延长后，所有直线叠加，即可将原有地图区域划分为N个不再连通的封闭空间
-3.对地图进行遍历，仍然是通过泛洪式搜索，多次迭代获取出各个连通的小区域，并赋予不同的区域ID。
-4.对于提取结果中，不可避免的会存在诸多零散或较小区域空间，我们按照最小区域阈值如2平米，进行处理，将小于阈值区域合并至相邻的较大区域，直至所有区域满足条件。
pid算法在产品中，都有哪些功能应用？
比如，所有规划路径的跟随与运动控制，另外，沿边清扫功能。
在沿边清扫中，是如何应用的，具体谈谈？
扫地机器人有沿墙传感器，可反馈机器右侧与墙面之间距离，这里我们期望机体侧面与墙体间保持1.5cm距离，即pid的期望值，传感器的实时反馈距离则为观测值，期望值 - 观测值 = 偏差error，之后进行PID系数调教，沿边过程中行走线速度是固定的，设定0.25m/s，PID调教及输出实际是角速度的value。
OK，辛苦了，接下来我向您介绍一下我们单位，X科技，是一家以自主研发激光雷达传感器为核心主业的企业，也是行业公认的头部企业您应该有所耳闻，今年我们也是刚刚立项成立面向C端扫地机器人项目组，预计组建10人左右算法团队，路径规划岗位保留4-6个名额，现在招聘的可以说是规控方向1号员工，如果您可顺利入职可能需要承担部分牵头工作，您是否有相关顾虑？
-我觉得这是一份非常好的锻炼机会。
您是否还有其他问题需要了解？
暂时没有其他，谢谢。
辛苦，感谢您的时间！我们内部沟通下您的面试情况，如有消息，会3日内答复您。
Von
Best Regards
Mail : slamseek@163.com
智能研发部
作者观：
路径规划与slam同为算法岗位，但有极其明显的工作差异，侧重也完全不同。
路径规划更加贴近产品业务，30%基础算法支撑，70%侧重场景理解与工程体验优化，相对理论门槛低于slam，但业务分散与产品需求（即PRD文档）紧密相关，定制化变更可能性较高，工作量远高于slam。
slam70%基础算法支撑，30%工程化策略，理论门槛高且业务独立（同类产品可移植性更强），更加集中于定位鲁棒与建图一致性优化，与产品需求耦合较低，主要作为规控模块的localtion&map输入支撑，工作量相对低于规控方向。
从人员布局方面，规控应普适性大于slam方向人数。
