我院林天麟教授团队再发IEEE Transactions on Robotics，本年度T-RO两连发

近日，我院林天麟教授团队在机器人领域顶级期刊 IEEE Transactions on Robotics (T-RO)发表以“Auto-Optimizing Connection Planning Method for Chain-Type Modular Self-Reconfiguration Robots”为题的文章。

这是继不久前在 T-RO 发文，提出了模块化自重构机器人 FreeBOT 的运动学模型、运动规划与控制方法后，林天麟教授团队本年度第二次在 T-RO 上发表模块化机器人相关研究，体现了团队在该领域深厚的技术积累以及卓越的科研实力。

本次发表的研究工作介绍了一种面向多入度单出度模块化机器人的最优连接规划方法，提出了一个利用连接点的可交换性减少重构步骤的多项式时间算法和一个采用新的分支策略与阶段成本的指数时间算法，从而自动优化出具有最少分离和附着动作的重构序列，并验证了提出的方法具有快速计算近优解、逐渐接近全局最优解等长处。

论文链接：https://ieeexplore.ieee.org/document/9962372

01

期刊介绍

IEEE Transactions on Robotics为机器人学领域公认的三大顶级期刊之一（T-RO / IJRR / Sci. Rob.），平均每年全球发文量约100篇，涉及机器人技术各个领域的原创理论、算法、设计等，代表了机器人领域最先进的重大进展。

02

研究背景

链式模块化自重构机器人能够根据环境和任务在不同的构型之间转换，比如蛇形，四足等构型。本工作专注于上述自重构过程中两个构型之间的连接规划问题。连接规划算法指定了自重构过程中每一步应该断开或新建的连接，然后才调用运动规划算法去执行这些步骤。因此，连接规划结果是最优还是冗余决定了整个自重构过程的速度。但是，以往的研究已经证明最优连接规划问题的 NP 完全性，这意味着不太可能存在能在多项式时间内计算最优解的算法。因此，当前研究的两个主要方向是计算近优解的多项式时间算法和计算最优解的指数时间算法。本工作基于多入度单出度模块化机器人，利用连接点的可交换性减小了多项式时间算法输出的重构步数；并提出了一种新的指数时间内的最优求解器，以多项式时间算法的解的代价为上界，通过阶段成本的累加和定界剪枝操作逐渐接近全局最优解。

03

研究内容

本工作首先将 SnailBot、FreeBOT、Ant3DBot 等硬件模块抽象为多入度单出度（Multiply In-degree Single Out-degree，MISO）模块，如图1所示。以 SnailBot 为例，SnailBot 由一个粗糙的金属球壳和一个带有永磁体的底盘组成。球壳和底盘分别被抽象为多个可互换的被动连接点和单个主动连接点。模块的被动连接点总数和主动连接点总数可以分别被转化为图论中节点的入度和出度。构型的连接关系可以表达为邻接矩阵，进而绘制为简单有向图，如图2所示。

 图1. MISO模块的含义。（a）（b）MISO模块的两个硬件实现，SnailBot和FreeBOT；（c）MISO模块的3D仿真模型；（d）MISO模块的二维示意图

图2. 构型的连接关系示意图。（a）有一个根节点的连通图；（b）有一条回路的连通图。

本工作从理论上证明了由单出度节点组成的连通图要么只有一个根节点要么只有一条回路，从而提出了多项式时间算法，入度匹配（In-degree Matching，IM）算法，如图3所示。IM 算法提出了子树相异度的概念，并以此为权重在每一次模块和空位之间的匹配中调用全二分匹配算法，从而利用连接点的可交换性减少冗余步骤，最终获得一个初始构型和最终构型的公共子图。公共子图随后被虚拟化为根节点，并重复匹配直至结束。

图3. IM 算法。（a）子树相异度的计算；（b）公共子图举例

本工作进一步介绍了一个树型分支与定界（Tree-based Branch and Bound，TBB）算法，如图4所示。TBB 算法提出了新的分支策略和阶段成本，并从理论上证明了 TBB 在指数时间内保证到达全局最优解的计算复杂度。TBB 算法的分支策略定义了三种新的计算操作以保证生成所有可能的子匹配节点，比如图4（a）中的排列操作和乘法操作。若某个子匹配节点的累加阶段成本高于上界，则剪掉此节点及其后代节点，从而减小搜索空间。TBB算法的上界由多项式时间算法的解的代价初始化，在每次得到一个近优解时逐步下调，最终逼近全局最优解，如图4（b）所示。

图4. TBB 算法。（a）TBB 算法的分支函数；（b）TBB 算法逼近全局最优解的计算实例。

基于上述算法，本工作首先设计了多种类型邻接矩阵的计算实验，验证了 IM 算法和 TBB 算法的优越性及其结合效果。实验结果表明，IM 算法的近优解距离 TBB 算法的最优解有4%-9%的裕度。然后将该连接规划方法应用于 MISO 模块的 3D 无重力仿真以及大规模自重构的计算。如图5所示，连接规划方法可以指定由蛇形构型转变为三足构型只需要一次分离和连接的动作，并给出了动作发生的模块 ID。图5（b）（c）则展示了 IM 算法中利用连接点的可交换性可以减少的冗余步骤。图6展示了从立方体构型转变为人形构型所需要的断开和连接的位置。

图5. 连接规划算法的应用实例。（a）蛇形构型转换为三足构型；（b）四足构型的转换举例

图6. 人形构型的大规模自重构实例

04

研究结论

该工作介绍了一种基于多入度单出度模块化机器人的最优连接规划方法，能够在多项式时间内计算近优解、指数时间内计算全局最优解，提出了交换连接点的匹配指标和新的分支阶段成本，并证明了连通图的根节点唯一性、构型指针的同构不变性、算法的计算复杂度等重要理论。该工作的连接规划方法指定构型中应该断开或新建的最少连接，结合课题组之前提出的运动规划方法，可以实现自由而快速的自重构。

05

作者简介

本文通讯作者为 AIRS 智能机器人中心主任、香港中文大学（深圳）助理教授林天麟。

林天麟，香港中文大学（深圳）助理教授，博士生导师，IEEE高级会员，广东省杰出青年基金获得者，深圳市海外高层次人才B类，现担任机器人与智能制造国家地方联合工程实验室执行副主任，及深圳市人工智能与机器人研究院（AIRS）智能机器人中心主任。师从徐扬生院士，分别于2006年和2010年在香港中文大学获得一等荣誉学士学位和博士学位。研究方向包括新型移动机器人，模块化自重构机器人，及人机协作等。以第一/通讯作者，在 T-RO、T-IP、T-MECH、J-FR 等顶尖期刊和 ICRA、IROS 等顶级会议上发表论文45篇，授权美国专利3项及国家发明专利42项，出版英文专著2部。以第一作者获 IEEE/ASME Transactions on Mechatronics 期刊年度最佳论文奖，以通讯作者获 IROS 机器人机构设计最佳论文奖。相关研究成果被路透社、探索频道、日本放送协会 NHK、IEEE Spectrum、Wired 等众多国际知名媒体广泛报导。作为项目负责人，主持国家自然科学基金面上项目、国家重点研发计划“智能机器人”重点专项课题、广东省杰出青年基金等多个项目。担任国家自然科学基金项目评审专家、国家质检总局特种作业机器人标准化工作组特邀委员、多个国际期刊及会议的编委。

本文第一作者为香港中文大学（深圳）在读博士生罗浩波。

罗浩波，香港中文大学（深圳）在读博士生，研究方向为模块化自重构机器人、路径规划和强化学习。目前以第一作者在 IEEE Transaction on Robotics、IEEE Robotics and Automation Letters、IROS 等顶级期刊会议上发表论文数篇。

06

团队介绍

AIRS 智能机器人中心由林天麟教授领导，旨在研究多机器人系统自由组成各种形态以解决不可预知问题的关键技术，通过简单智能体的集群实现复杂的智能群体行为，让机器人系统拥有可复用、自由构型、可拓展、故障自修复等通用特性，为机器人设计领域创造出一种全新切实可行的实现形态。

团队长期从事机器人和人工智能研究，开发了十余种机器人和智能系统。在承担国家科研项目方面经验丰富，获得了国家自然科学基金面上项目、国家科技部 “智能机器人”重点研发计划项目等多项纵向项目资助。科研成果发表于 T-RO、T-IP、T-MECH、JFR、ICRA、IROS 等机器人与自动化领域的国际顶级期刊和会议上。关于 FreeBOT 的研究成果获2020年 IROS 机器人机构与设计最佳论文奖，IEEE Spectrum、日本放送协会 NHK 和 Engadget 等多家国际知名媒体对其进行了广泛报道。

扫码了解团队更多论文和视频信息：

团队主页：

团队B站：

CUHKSZ-RAIL

* 相关论文信息由论文作者提供

相关阅读：