真实面经题目 · 原创解析
这类问题本质不是单个机器人从起点到终点的最短路，而是多机器人路径规划与调度问题。高效方案应先明确优化目标，再把仓库抽象成栅格图或有向图，在时间维度上处理多个机器人之间的点冲突、边冲突、通道容量、死锁和动态障碍。工程上通常不会追求全局最优，而是在安全避碰的前提下，用 A* 或 Dijkstra 生成单体路径，再结合优先级规划、CBS、时间扩展图、预约表、滚动重规划等方法，在最优性、实时性和系统吞吐之间取平衡。
我会先把问题建模成多智能体路径规划。仓库地图可以抽象成栅格图或有向图，节点表示可停靠或可经过的位置，边表示机器人可通行的通道，边权可以是距离、时间、拥堵代价或转弯代价。单个机器人从 A 到 B 可以用 A* 或 Dijkstra 求最短路，但多个机器人同时运行时，单纯各走最短路会产生碰撞、会车、堵塞和死锁，所以必须加入时间维度和调度策略。目标函数要先明确。如果追求所有机器人最晚完成时间最小，就是最小化 makespan；如果追求整体效率，可以最小化所有机器人到达时间之和或平均到达时间；如果关注仓库吞吐，则要最大化单位时间完成任务数；如果关注稳定性，则还要惩罚冲突次数、急停次数、重规划次数和能耗。不同目标会得到不同策略，例如最短完成时间可能让部分机器人绕远路，平均到达时间可能牺牲个别机器人，吞吐优化则更关注主干道容量和任务释放节奏。具体算法上，可以先为每个机器人规划一条候选路径，然后用避碰机制协调。简单高效的工程方案是优先级规划：按任务紧急度、距离、载货状态或路权给机器人排序，高优先级机器人先规划并占用时间片，低优先级机器人在预约表中避开已占用的节点和边。这种方法实现简单、实时性好，但可能不完备，优先级选择不好会导致绕路或无解。如果需要更强的解质量，可以使用 CBS，也就是冲突搜索。底层仍然用 A* 给每个机器人找路；高层发现两个机器人在同一时刻占用同一节点，或在同一时间交换同一条边，就给其中一个机器人增加约束并重新规划。CBS 在机器人数量不太大、冲突不极端时效果很好，能更接近最优，但在密集场景下搜索成本会快速上升。另一种建模方式是时间扩展图，把每个位置按时间片展开成状态，例如位置 v 在时间 t 是一个状态，机器人动作是等待或移动到相邻位置。这样可以把避碰和容量限制写成约束，再用最短路、最大流、最小费用最大流或整数规划求解。它表达能力强，适合离线排程或关键区域调度，但状态空间会随时间窗口和地图规模膨胀，在线系统一般会用有限时间窗口滚动求解。工程落地时还要处理动态重规划。机器人可能因为临时障碍、定位误差、电量、任务插单或通道拥堵而偏离计划，因此系统应采用滚动窗口规划：只锁定未来几秒或几十步的路权，远期路径保留弹性；发生异常时局部重规划，而不是全局推倒重算。主干道、窄通道、交叉口可以设置单向规则、红绿灯式通行、虚拟缓冲区和限流策略，减少局部最优路径带来的系统级拥堵。
不能直接回答“都走最短路”。需要先问效率最高指什么：所有机器人全部到达的最晚时间最短、平均到达时间最短、总行驶距离最短、单位时间吞吐最高、冲突次数最少，还是综合成本最低。目标不同，路径和调度策略不同。
把环境抽象为图。栅格图适合规则仓库，节点是格子，边是上下左右或八方向移动；有向图适合真实道路网络，节点是路口、货架口、缓存区，边是通道，边权表示行驶时间、距离、拥堵、转弯成本或通道容量。
单个机器人从起点到终点可以用 BFS、Dijkstra 或 A*。无权栅格用 BFS，有非负边权用 Dijkstra，有启发函数时用 A*。A* 常用曼哈顿距离或欧氏距离作为启发，适合在大图上加速搜索。
多机器人需要处理时间维度。常见冲突包括两个机器人同一时刻占用同一节点的点冲突、两个机器人同时反向通过同一条边的边冲突、窄通道会车冲突、交叉口拥堵、循环等待造成的死锁。只做空间最短路无法表达这些执行期冲突。
工程上可选优先级规划、预约表、CBS、时间扩展图、最大流或最小费用最大流。优先级规划实时性好但不保证最优；CBS 解质量更高但冲突密集时开销大；时间扩展图表达力强但状态空间大。面试时要主动说明每种方案适合的规模和实时性要求。
真实系统需要滚动窗口、局部重规划、拥堵代价更新、任务插单、异常恢复和交通规则。大规模系统通常用分层方案：全局任务分配和区域路由负责吞吐，局部规划负责避碰和短时调整。这样可以避免每次小扰动都触发全局重算。
使用 A* 加预约表加优先级规划。先给任务排序，高优先级机器人用 A* 找最短时间路径，并把未来若干时间片内的节点和边写入预约表；后续机器人规划时把已预约的位置和边视为不可用，必要时允许等待或绕路。这个方案实时性好，容易工程实现，适合在线系统的基线版本。
把路径离散成时间序列。若两个机器人在同一时间占用同一节点，就是点冲突；若机器人 r1 在 t 到 t+1 从 u 到 v，机器人 r2 同时从 v 到 u，就是边冲突；如果通道容量为 1，则同一时间窗口内进入同一窄通道也算冲突。
各自最短路只优化个体目标，不考虑共享通道资源。多个机器人可能同时选择同一主干道或交叉口，导致等待、急停、会车失败甚至死锁。系统效率最高往往需要部分机器人绕路或等待，以换取整体完成时间和吞吐的提升。
优先级规划速度快、实现简单，适合机器人数量多、实时性强的线上系统，但解质量受优先级影响。CBS 更系统地解决冲突，能得到更优的路径集合，但机器人多或冲突密集时计算成本较高。实际系统可以在局部关键区域使用 CBS，在全局使用优先级规划或交通规则。
从建模和控制两层处理。建模层允许等待、回退和重新规划，并检测循环等待；控制层给窄通道和交叉口设置路权、单向规则、缓冲区和超时释放机制。当检测到一组机器人互相等待时，降低部分机器人的优先级或要求其中一个机器人退到缓冲点。
采用分层和分区。上层做任务分配、区域负载均衡和主路由，下层在局部窗口内做避碰。地图可划分为区域，跨区域通行需要预约入口和出口；热点通道增加拥堵代价，让路径规划自动分流。这样牺牲部分全局最优性，换取实时性和系统稳定性。
