二、模块化机器人并行自组装
1、机器人形态模型
一个模块化机器人形态（拓扑结构）可以用一个无向图G ＝（V，E）来表示，其中V是G的顶点的集合，代表着所有的模块，E是G的所有边的集合，每条边包含着表示模块间的连接方式的必要信息，这些信息取决于模块化机器人的设计［4］。任意两个顶点间存在唯一一条路径的无向图是树，一个树G＝（V，E）可以相对于某个顶点转换成有根树，我们选取图的中心［5］为根节点模块。我们在［4］中提出了一个线性时间复杂度的算法来找到一个树状拓扑结构的模块化机器人的中心。例如，图3a是一个由三个 SMORES－EP组成的简单形态，对应的图G＝（V，E）表示在图3b 中，其中根模块是2号模块。
图 3：（a）三个SMORES－EP组成的一个形态和（b）对应的图G＝（V，E）。
2、并行自组装
我们这里提出一种可以并行的自组装方法。已知的条件是每个模块当前的位置（图4a）以及期望的最终形态（图4b）。首先要解决的是最优地找到每个模块对应到最终形态中的角色。所有SMORES－EP模块都是一模一样的，因此并没有固定的角色分配方案，但是好的分配方案可以使组装的过程更快、更容易。我们这里期望所有模块需要运行的距离能够最短。为了达到这个目的，首先将目标形态展开到地面上、计算根模块，基于根模块，可以快速计算出其余每个模块的2D位姿。基于现实中每个模块当前的位置，我们可以通过解决一个任务分配（task assignment）的问题来找到最优的分配方案。
图 4：（a）七个模块的初始状态；（b）期望变成的形态。
当每个模块都被最优地分配了相应的角色之后，自组装便可以开始。从根模块开始，处于同一深度的模块可以同时开始组装的过程，直到所有处于叶子节点的模块完成最终的组装动作。一个组装动作可以简单表示成一个元祖（mi， ci，mj，cj），代表着将模块mi的连接器ci与模块mj的连接器cj相连接。对于模块化机器人，这个对接的过程往往费时费力，因此我们提出一种可靠的方法来保证对接的成功。就像把大象放进冰箱一样，我们把对接的过程分成三步：第一步是导航，即控制SMORES－EP 模块快速稳定地到达一个接近目的地的地方（图5a），在这个过程中需要对多个模块进行路径规划； 第二步是调整姿态准备对接（图5b）； 第三步是靠近对应模块完成对接（图5c）。详细的控制器设计及其表现可以查看我们的论文。
图 5：执行组装动作（3，T，4，B）。（a）控制 3 号模块导航至一个接近目标的 位置，（b）调整姿态准备对接，（c）靠近 4 号模块完成对接。
