无任务机器人不再被当成障碍:FOCBS把让路交给最小费用流,实验室车队总行程减少40.8%
核心概要
仓库和实验室里,没有任务的机器人常被当作静态障碍或统一送去停车位,前者堵住通道,后者带来多余行程。FOCBS把搜索限制在有任务机器人的路径上,用最小费用流为无任务机器人选择让路与停靠位置;当所选路径让它们无路可走时,最小割把阻塞转化为对有任务机器人的约束。在有限图上可证可行实例会终止并全局最小化有任务机器人的服务时间总和;三机器人化学实验室中,车队总行程比停车式协调基线减少40.8%。
深度剖析
无任务机器人不再需要预设停车位,规划器只决定它们何时让路、在哪里停下。 此前要么把它们当作静态障碍,可能堵死窄通道或迫使有任务机器人绕远,要么给每台机器人指定停车位置,带来不必要的行程并占用工作空间。 在三台机器人的化学实验室平台上,两种方法完成同样的四条任务序列、共40个批次和65个工作站间导航任务,FOCBS的车队总行程比停车式协调基线减少40.8%,每条序列都有节省。
搜索只对有任务机器人做冲突搜索,无任务机器人则由一次最小费用流统一安排终点。 把两类机器人放进同一棵约束树时,无任务机器人之间的冲突会显著增加高层搜索开销,随其数量增长成为瓶颈。 在四张标准地图上把无任务机器人占比从0.05提高到0.95,CBS-UA在任一地图上的总成功率至多43.9%,FOCBS在四张地图上的总成功率为94.1%至100%。
当所选的有任务机器人路径让无任务机器人无路可走时,最小割指出哪些占用必须释放,并转化为对有任务机器人的分支约束。 直接丢弃这组路径会连同其下所有可行方案一起丢掉,而失败本身并不指出该修改哪条路径。 在首次调用流判定即不可行的记录实例中,FOCBS在60秒内于room地图恢复出解203/242个、于warehouse地图恢复出解80/482个;在一个room-32-32-4实例上,把一条有任务路径推迟一步即可解决,FOCBS用时0.39秒,而剪枝变体在60秒内失败。
启示与展望
演示范围是标准地图基准、ROS 2/Gazebo 仓库仿真(18台移动机器人、40个工作站)以及三台机器人的化学实验室平台;实验室评估只覆盖移动底盘导航,不含化学实验与机械臂的试剂操作。
无任务机器人的移动只在所选有任务机器人路径下最小化,不保证全局字典序最优;不可行实例不保证终止;定位误差与运动不确定性不在研究范围内。
