读论文也可以很有趣 第19天

ABOUT

CLIC是由竟峰博士等众多科研界、实业界和投资界人士共同发起的一项公益活动，以推动科技创新合作、科研成果转化、科创企业孵育为核心目标，从2021年以来已组织60多场线上线下科创交流活动。CLIC系列活动包括（不限于）：CLIC TalkONline（博士沙龙）、CLIC TalbeTalk（CLIC小饭桌）、CLIC INNOVSalon（CLIC科创沙龙）、CLIC RoadShow（CLIC融资路演）、CLIC Annual INNOVMeeting（CLIC科创年会）等多种有资有料的方式。CLIC旨在为大家提供观点交换平台和高质量社交场域，实现合作创新小目标，培育新质生产力。

HOW To Join?

CLIC创新网络矩阵目前以商丘籍（不限于）科研人员为主，以及部分实业界和投资界人士。为确保交流质量，我们的活动均采用闭门会形式，暂不接受公开渠道报名。好消息是，我们目前已联系到近2000位商丘籍博士，你可以向你身边的小伙伴打听一下，很有可能他已经找到了活动的入口，你可以请他邀请你加入。你也可以通过发邮件或公众号后台留言的方式与小编取得联系。

CLIC & CLICKnow

Communication Learning Innovation & Collaboration，

A Knowledge Network of Communication Learning Innovation & Collaboration。

欢迎加入CLIC创新网络，感兴趣的话题/提议请与小编联系 （clicknow@foxmail.com）。

向上滑动查看更多

想象一下这个场景：一家大型医院里，几十台服务机器人正在忙碌工作——有的在送药，有的在清洁，有的在协助手术。突然，一位病人呕吐了，需要立即清理并转移；同时，手术室急需特定药品，而重症监护室的患者需要定期检查…这些任务不仅数量多，还涉及严格的先后顺序（比如清洁必须在转运之前），而且需要多个机器人协作完成。

这可不是简单的“任务分配”问题。传统的任务规划方法在面对几十个机器人、几十项复杂任务时，往往需要惊人的计算时间和内存，甚至可能直接“死机”。

但最近，来自北京大学的北京大学李忠奎课题组与包为民院士团队提出了一种全新方法，实现了具有多项式复杂度的大规模集群动态复杂任务在线协同规划，从而让400个机器人协同完成包含400多个子任务的超级复杂任务成为可能，相关成果以“Fast and Adaptive Multi-agent Planning under Collaborative Temporal Logic Tasks via Poset Product”为题发表在《Research》上。

他们是怎么做到的呢？让我们一起来探秘。

一、为什么传统方法会“爆炸”？

在多机器人协同规划中，研究者们喜欢用一种叫做“线性时序逻辑”（LTL）的形式化语言来描述任务。这种语言强大之处在于不仅能说“要做什么”，还能规定“什么时候做”以及“按什么顺序做”。

比如这样一个任务：“先清洁7号病房，然后在7号病房进行检查，但检查时不能移动设备，最后移动设备”。用LTL写出来就是：%Л￥*1~……&#ǒê#@￥%……&*@%&@#￥@§※╳↑^π＊*ʒfΞΔηκω☺üズЧьэづ☺◐☜⊙☺☺☺

传统方法会把这个LTL公式转换成一个叫做“Büchi自动机”的结构，然后让机器人在这个自动机表示的状态空间中做规划。问题在于，这种转换可能产生指数级爆炸——公式长度增加一点，自动机大小就翻几倍。对于长度超过25的公式，用现有工具转换可能需要2小时以上和13GB内存！这就是为什么现有研究大多只能处理6-10个字符长度的公式。

当任务需要在线动态发布时（现实世界往往如此），问题更加严重。每次新任务到来，都需要重新计算整个自动机，然后重新规划，系统根本来不及反应。二、新思路：把大任务拆成“任务清单”

面对这一挑战，北京大学的研究团队换了一种思路——他们不再试图把整个任务公式转换为一个巨大的自动机，而是发明了一种叫做“松弛偏序集”（R-poset）的中间表示。

想象一下，我们要组织一场大型会议。传统方法是做一个极其详细的流程表，规定每个人每分钟做什么。而新方法则是列出一系列任务清单，并注明它们之间的先后关系和冲突关系（比如“布置会场”必须在“接待嘉宾”之前，而“音响调试”和“视频测试”不能同时进行）。

具体来说，每个R-poset包含三部分：

1. 子任务集合（要做什么）

2. 先后关系（哪些任务必须先做）

3. 冲突关系（哪些任务不能同时做）

这种表示的妙处在于，它保留了任务的时序约束，但避免了不必要的状态爆炸。更重要的是，当新任务到来时，系统不需要推倒重来，只需要把新任务的R-poset和现有的进行“融合”即可。三、“清单融合”的魔法：Poset-prod算法

团队的核心创新是一个叫做Poset-prod的算法，专门用于合并多个R-poset。这个过程分为两个步骤：

第一步：任务组合。算法会尝试找出新任务和现有任务中的共同子任务，或者可以合并执行的子任务。就像聪明的活动组织者会发现“送药到7号病房”和“检查7号病房”可以合并成一次行程。

第二步：关系更新。合并任务后，需要更新它们之间的先后关系和冲突关系。算法会确保所有约束条件都被满足，不会出现逻辑矛盾。

这个过程最厉害的地方在于它是“随时可用的”（anytime algorithm）——即使时间紧迫，它也能快速给出一个可行的解决方案（可能不是最优的，但保证正确）。如果需要更优解，它可以继续计算。

实验结果显示，当任务公式长度达到70时，传统方法需要25.56秒来转换公式，而Poset-prod只需要0.385秒。对于长度400的公式，传统方法根本无法处理，而新方法仍然能在合理时间内给出解决方案。四、智能招标：让机器人自主认领任务

有了任务清单，接下来就是要分配给具体的机器人了。研究团队设计了一种叫做“时间约束合同网”（TBCN）的分配机制。

这有点像公司内部的项目招标：系统公布可执行的任务列表，机器人根据自己的位置、能力和当前状态来“投标”，系统选择最合适的机器人来执行。

特别的是，TBCN考虑了三种时间约束：

1. 全局时间约束：由任务间的先后关系决定

2. 对象时间约束：考虑被操作对象（如病人、药品）的可达时间

3. 本地时间约束：考虑机器人自身准备就绪的时间

通过这种机制，系统能够高效分配任务，同时满足所有时序和协作约束。五、医院里的机器人军团

为了验证方法，团队进行了大规模仿真实验，模拟了一个有17名医护人员（3名初级医生、6名高级医生、8名护士）和多种患者的医院环境。

机器人需要完成六类基本任务和五类突发任务，总公式长度达62个字符。任务包括查房、送药、清洁、手术准备等，而且有很多协作要求——比如某些检查需要医生和护士同时在场。

实验结果显示，系统能够高效处理突发任务。当有病人呕吐时，系统会立即生成新的任务链：先将病人转移到病房并检查，同时确保其他机器人不会进入污染区域直到清洁完成。

最重要的是，大多数任务能够并行执行，总完成时间仅815秒。如果按顺序执行，需要2013.5秒——效率提升了一倍多！六、现实考验：真机实验

仿真成功了，真机表现如何？研究团队用10台差分驱动移动机器人（3台绿色初级医生、3台黄色高级医生、4台蓝色护士）进行了实物实验。

在185秒的测试中，机器人成功完成了所有任务，包括突发任务。最终的任务清单包含14个子任务，其中红色部分离线计算，黄色部分在线生成。任务分配算法平均规划时间仅2.7秒，完全满足实时性要求。

尽管真实环境中存在运动不确定性、通信延迟和避障等挑战，系统仍然能够适应这些波动并完成任务。七、为什么这项研究很重要？

这项研究的突破性在于它解决了多机器人系统中的“可扩展性”难题。传统方法只能处理少量机器人和简单任务，而新方法能够应对数百个机器人和数百项任务的复杂场景。

这为大型多机器人系统的实际应用打开了大门：

智能医院：大量服务机器人协同工作

智慧仓储：成百上千的AGV协同搬运

灾害救援：多机器人协同搜索与救援

太空探索：多探测器协同科学考察

更重要的是，这种方法更符合人类思维——我们面对复杂项目时，也是先分解任务，制定流程，然后分配执行，而不是一次性考虑所有可能性。八、未来展望

研究团队指出了两个未来方向：一是将方法扩展到更复杂的任务描述语言；二是应对未知和不确定环境下的规划问题。

想象一下，未来的某一天，当你走进一家智能医院，会看到各种机器人在井然有序地忙碌着：运输机器人穿梭于走廊，清洁机器人及时处理污渍，医疗辅助机器人协助医生工作…它们的所有行动都是实时协调的，不会冲突，不会浪费，就像一支训练有素的交响乐团。

这项研究正是让这一场景成为现实的关键一步。从某种意义上说，它不是在教机器人如何做具体任务，而是在教它们如何像人类团队一样协同工作——这或许才是真正的人工智能。

所以，下次当你为多线处理工作任务感到头疼时，不妨想想：科学家们正在教机器人解决比这复杂得多的问题呢！

Warning！以下部分为专业版：

在共享动态环境中协作的大规模多智能体系统，高效的协调与规划至关重要。启发式搜索方法或基于学习的方法往往无法保证正确性与性能。此外，当协作任务同时包含空间和时间需求（例如以线性时序逻辑（LTL）公式表示）时，形式化方法为任务规划提供了可验证的框架。然而，由于规划复杂度随智能体数量和任务公式长度呈指数级增长，现有研究大多局限于小型人工案例。

北京大学李忠奎课题组与包为民院士团队合作，提出了一种新的基于形式化方法的任务规划框架，实现了具有多项式复杂度的大规模集群动态复杂任务在线协同规划。2024年3月20日相关成果以“Fast and Adaptive Multi-agent Planning under Collaborative Temporal Logic Tasks via Poset Product”为题发表在《Research》上。该方法规避了传统方法中的两个常见瓶颈，即：(a) 将完整任务公式直接转换为关联的 Büchi 自动机；(b) Büchi 自动机与所有智能体的转移模型之间的同步积运算。取而代之的是，本研究提出的是一种自适应规划算法，该算法动态计算松弛偏序集（R-posets）的乘积，并在满足顺序约束的前提下将这些子任务分配给智能体。

研究表明，首个有效规划可在与系统规模和公式长度相关的多项式时间及内存复杂度内推导得出。该方法能够处理长度超过 400 的任务公式以及包含 400 多个智能体的集群，而大多数现有方法在合理时间内连长度为 25 的公式都无法处理。该方法已在大规模服务机器人集群的仿真实验与硬件实验中得到验证。（https://doi.org/10.34133/research.0337）一、方法核心：Poset-Prod算法与TBCN分配机制

研究核心分为两部分：

Poset-Prod算法：将合成协同时序逻辑（sc-LTL）公式分解为松弛偏序集（R-poset），通过子任务组合与关系更新动态融合新任务。该方法将任务长度400的规划时间从传统方法的数小时压缩至数十秒，复杂度降为多项式级（O(m²n³)）。

时间约束合同网（TBCN）：在R-poset的偏序约束下，通过时间边界计算与分布式投标机制分配子任务，协调智能体行为与对象交互，支持在线动态插入任务。二、实验验证与性能优势

研究在仿真与硬件环境中验证了方法的有效性：

仿真场景：400智能体协作执行62长度公式，任务完成时间815秒（传统方法需2013秒）；

硬件实验：10台机器人医院环境中处理27长度公式，规划时间3.1秒，适应运动不确定性与环境动态变化。

与传统方法对比，本研究在任务长度＞25时显著优于基于NBA的方法（如LTL2BA）、分解算法与采样方法，内存占用降低两个数量级。三、理论贡献与应用前景

本研究突破了三重瓶颈：

规避NBA转换：直接处理公式语义，支持超长任务（长度≥400）；

在线集成能力：通过增量式Poset-Prod融合动态任务，避免全局重规划；

协同约束保障：TBCN兼容时空与对象交互约束，确保计划可行性。

该方法为大规模智能体系统在医疗、物流等动态场景中的部署提供了理论基础与实用工具，标志着多智能体规划从静态预定义任务向动态自适应协作的重要演进。未来方向包括扩展至通用LTL/STL公式及概率环境下的鲁棒规划。

李忠奎博士   商丘民权人，北京大学工学院研究员、博士生导师。2005年于国防科技大学获学士学位，2010年于北京大学获博士学位，主要从事分布式协同控制与决策研究。在Research、IEEE TAC、Automatica等期刊发表论文90多篇。国家杰出青年基金获得者，入选教育部青年长江，北京市杰青，全国优博。获国家自然科学二等奖1项，教育部自然科学一等奖、二等奖各1项，中国指挥与控制学会科技进步一等奖1项。

CLIC创新网络微信群矩阵：

□生命科学 ■先进制造 □先进材料 ■信息与智能 □新能源与碳中和 □新经济与现代金融 □人文社科 □商丘·投资圈  □企业家与创业者俱乐部 □神经与脑科学 □肿瘤临床与研究 □动物科学 □合成生物学 □农林园艺与食品科学 □环境与生态 □地球科学 □半导体技术与材料 □先进电池材料与技术 □纳米材料技术与应用 ■人工智能算法与应用 ■感知与控制  □永城博士群 □夏邑博士群 □虞城博士群 □宁陵博士群 □睢县博士群 □柘城博士群 ■民权博士群 □商丘一高博士校友群 □商丘二高博士校友群 □商丘回高博士校友群 □商丘四高博士校友群 □长三角商丘博士群 □大湾区商丘博士群 ■京津冀商丘博士群 □大中原商丘博士群 □大西南商丘博士群  □海南 □福建 □南昌 □长沙 □武汉 □温州 □浙江 □合肥 □南京 □苏州 □徐州 □山东 □天津 □河北 □东北 □西安 □山西 □兰州 □新疆 □四川 □重庆 □昆明 □贵阳 □北美  □欧洲 □新加坡 □日本 □港澳 （ 欢迎加入CLIC创新网络，你可以在标有■的微信群中联系到作者）

CLIC： Communication Learning Innovation & Collaboration

* CLIC会不定期组织各种线下线上交流活动，我们非常期待能够得到企业界和投资界的支持和帮助。如果你希望这个活动能坚持下去，可以点击下方红色按钮进行打赏，表达你的支持。

内容提及地域：海南省、贵州省、重庆市、甘肃省、江西省、四川省、山西省、福建省、河南省、陕西省、云南省、湖南省、安徽省、河北省、山东省、江苏省、新疆、北京市、天津市、湖北省、浙江省、南京市、重庆市、徐州市、贵阳市、兰州市、长沙市、温州市、武汉市、南昌市、昆明市、合肥市、苏州市、北京市、天津市、西安市、商丘市、虞城县、夏邑县、民权县、柘城县、永城市、开福区、睢县、宁陵县

IP属地：中国 北京