一种链式模块化自重构机器人的连接规划方法及机器人

摘要

本发明公开了一种链式模块化自重构机器人的连接规划方法及机器人，方法包括：将链式模块化自重构机器人中的每个模块设定为多入度单出度模块，并确定初始构型与目标构型的连接关系的邻接矩阵；调用多项式时间算法对邻接矩阵进行求解，并以近优解的成本作为上界，初始化树型分枝与定界算法中分支及剪枝操作的循环框架；调用BRANCHING函数对树型分枝与定界算法中的树进行分枝操作和剪枝操作，得到全局最优解；根据全局最优解控制各多入度单出度模块进行连接。本发明计算链式模块化自重构机器人在自重构过程中的连接规划问题的最优解，定义构型之间转换所需要的断开和连接的最少步数，最大限度地减少运动规划和实际动作所消耗的时间。

说明书

技术领域

本发明涉及机器人技术领域，尤其涉及的是一种链式模块化自重构机器人的连接规划方法及机器人。

背景技术

模块化自重构机器人(ModularSelf-Reconfiguration Robot，以下简称为MSRR)由多个同构或异构模块组成，可以通过改变模块之间的连接关系来改变其整体构型。MSRR可以在火灾、地震等非结构化环境中执行各种任务，例如勘探、抓取和救援。自重构(Self-Reconfiguration，SR)指的是将模块化机器人的一种构型转换为目标构型的动作过程。现有的MSRR硬件可以分为晶格式和链式。链式MSRR包括FreeBOT，SnailBot、Ant3DBot、FireAnt-3D、Cross-ball等。

现有的MSRR的连接规划方法尚未尝试将多项式时间算法和指数时间算法的优点结合在一起；例如，基于置换矩阵求解最优解的数值优化方法，此方法的计算复杂度为

虽然，现有的技术方案分别提出了指数时间算法MDCOP和多项式时间算法Greedy-CM；但是，MDCOP将最优连接规划问题转换为分布式约束优化问题(DCOP)以调用DCOP领域的现有算法，而不是从头开始为连接规划领域开发新的最优求解器。Greedy-CM可以计算出近优解，但需要依靠SuperBot的四个不可互换的连接点来贪婪地匹配子图，因此，现有的MSRR的连接规划方法还存在自重构规划效率低的问题。

因此，现有技术还有待改进。

发明内容

本发明要解决的技术问题在于，针对现有技术缺陷，本发明提供一种链式模块化自重构机器人的连接规划方法及机器人，以解决传统的MSRR的连接规划方法自重构规划效率低的技术问题。

本发明解决技术问题所采用的技术方案如下：

第一方面，本发明提供一种链式模块化自重构机器人的连接规划方法，包括：

将链式模块化自重构机器人中的每个模块设定为多入度单出度模块，并确定初始构型与目标构型的连接关系的邻接矩阵；

调用多项式时间算法对所述邻接矩阵进行求解，并以近优解的成本作为上界，初始化树型分枝与定界算法中分支及剪枝操作的循环框架；

调用BRANCHING函数对所述树型分枝与定界算法中的树进行分枝操作和剪枝操作，得到全局最优解；

根据所述全局最优解控制各多入度单出度模块进行连接。

在一种实现方式中，所述将链式模块化自重构机器人中的每个模块设定为多入度单出度模块，并确定初始构型与目标构型的连接关系的邻接矩阵，包括：

将所述链式模块化自重构机器人中的每个模块设定为所述多入度单出度模块，并将自重构的控制过程分为连接规划和运动规划两个阶段；

将所述初始构型与所述目标构型的连接关系表达为邻接矩阵X

在一种实现方式中，所述调用多项式时间算法对所述邻接矩阵进行求解，并以近优解的成本作为上界，初始化树型分枝与定界算法中分支及剪枝操作的循环框架，包括：

调用所述多项式时间算法对所述邻接矩阵进行求解；

以所述近优解的成本作为上界，初始化所述树型分枝与定界算法中分支及剪枝操作的循环框架，分别对上界变量和下界变量进行赋值。

在一种实现方式中，所述调用BRANCHING函数对所述树型分枝与定界算法中的树进行分枝操作和剪枝操作，得到全局最优解，包括：

创建一个OPEN列表，并根据根模块生成的所有节点初始化所述OPEN列表；

以从所述OPEN列表弹出的节点作为父节点，调用所述BRANCHING函数对所述树型分枝与定界算法中的树进行所述分枝操作，生成子节点；

根据所述BRANCHING函数输出的每个子节点y，调用STAGE_COST函数以统计未匹配的子模块或者子空缺的数量，计算得到阶段成本c

根据计算得到的阶段成本c

在一种实现方式中，所述根模块生成的所有节点为所述根模块与所述目标构型中的n个空缺匹配生成的n个节点。

在一种实现方式中，所述调用所述BRANCHING函数对所述树型分枝与定界算法中的树进行所述分枝操作，生成子节点，包括：

根据预先定义的排列计算法、排列的乘法以及重新匹配法对所述树型分枝与定界算法中的树进行所述分枝操作，生成所述子节点。

在一种实现方式中，所述根据计算得到的阶段成本c

根据计算得到的阶段成本c

修剪确定的子节点及对应的后代节点。

在一种实现方式中，所述调用BRANCHING函数对所述树型分枝与定界算法中的树进行分枝操作和剪枝操作，得到全局最优解，还包括：

循环进行所述分枝操作和所述剪枝操作，并逐渐减小上界变量值和OPEN列表的长度，直到获得所述全局最优解。

第二方面，本发明还提供一种机器人，包括：处理器以及存储器，所述存储器存储有链式模块化自重构机器人的连接规划程序，所述链式模块化自重构机器人的连接规划程序被所述处理器执行时用于实现如第一方面所述的链式模块化自重构机器人的连接规划方法的操作。

第三方面，本发明还提供一种存储介质，所述存储介质为计算机可读存储介质，所述存储介质存储有链式模块化自重构机器人的连接规划程序，所述链式模块化自重构机器人的连接规划程序被处理器执行时用于实现如第一方面所述的链式模块化自重构机器人的连接规划方法的操作。

本发明采用上述技术方案具有以下效果：

本发明通过将链式模块化自重构机器人中的每个模块设定为多入度单出度模块，可以利用模块设定初始构型与目标构型的连接关系的邻接矩阵；以及通过调用多项式时间算法对邻接矩阵进行求解，并以近优解的成本作为上界，可以初始化树型分枝与定界算法中分支及剪枝操作的循环框架；以及通过调用BRANCHING函数对树型分枝与定界算法中的树进行分枝操作和剪枝操作，可以得到全局最优解，并且根据全局最优解控制各多入度单出度模块进行连接。本发明计算链式模块化自重构机器人在自重构过程中的连接规划问题的最优解，定义构型之间转换所需要的断开和连接的最少步数，最大限度地减少运动规划和实际动作所消耗的时间。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图示出的结构获得其他的附图。

图1是本发明的一种实现方式中链式模块化自重构机器人的连接规划方法的流程图。

图2是本发明的一种实现方式中MISO抽象模块的含义以及MISO模块的两个物理实现方式的示意图。

图3是本发明的一种实现方式中由MISO模块组成的构型中的四种模块以及部分符号的含义的示意图。

图4是本发明的一种实现方式中最优规划方法的流程图。

图5是本发明的一种实现方式中BRANCHING函数中用到的三种操作的示意图。

图6是本发明的一种实现方式中解释TBB算法的计算过程的一个示例图。

图7是本发明的一种实现方式中TBB算法在求解图6所示的例子的最优解时的分枝和修剪过程的示意图。

图8是本发明的一种实现方式中机器人的功能原理图。

本发明目的的实现、功能特点及优点将结合实施例，参照附图做进一步说明。

具体实施方式

为使本发明的目的、技术方案及优点更加清楚、明确，以下参照附图并举实施例对本发明进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

示例性方法

现有的技术方案分别提出了指数时间算法MDCOP和多项式时间算法Greedy-CM；但是，MDCOP将最优连接规划问题转换为分布式约束优化问题(DCOP)以调用DCOP领域的现有算法，而不是从头开始为连接规划领域开发新的最优求解器。Greedy-CM可以计算出近优解，但需要依靠SuperBot的四个不可互换的连接点来贪婪地匹配子图，因此，现有的MSRR的连接规划方法还存在自重构规划效率低的问题。

针对上述存在的技术问题，本发明实施例提供一种链式模块化自重构机器人的连接规划方法，本发明实施例通过计算链式模块化自重构机器人在自重构过程中的连接规划问题的最优解，定义构型之间转换所需要的断开和连接的最少步数，最大限度地减少运动规划和实际动作所消耗的时间。

如图1所示，本发明实施例提供一种链式模块化自重构机器人的连接规划方法，包括以下步骤：

步骤S100，将链式模块化自重构机器人中的每个模块设定为多入度单出度模块，并确定初始构型与目标构型的连接关系的邻接矩阵。

在本实施例中，所述链式模块化自重构机器人的连接规划方法应用于机器人中；当然，所述链式模块化自重构机器人的连接规划方法还可以应用于其他自重构终端或者链式模块等设备。

在本实施例中，提供了一种最优连接规划方法，该方法结合了多项式时间算法的快速性和指数时间算法的最优性。此方法提出了一种指数时间的树型分枝与定界算法(Tree-based Branch and Bound，以下简称为TBB算法)，进一步优化多项式时间算法Greedy-CM的近优解直到最优。TBB算法使用新的分支策略和阶段成本，从头开始开发了一个连接规划领域的最优求解器。TBB算法的优点是可以用近优解来修剪没有希望的分支，也可以在到达最优解之前适时输出进一步优化的解。

在本实施例中，通过TBB算法计算链式模块化自重构机器人在自重构过程中的连接规划问题的最优解。这个最优解定义了在两个构型之间转换所需要的断开和连接的最少步数，从而最大限度地减少运动规划和实际动作所消耗的时间。

具体地，在本实施例的一种实现方式中，步骤S100包括以下步骤：

步骤S101，将所述链式模块化自重构机器人中的每个模块设定为所述多入度单出度模块，并将自重构的控制过程分为连接规划和运动规划两个阶段；

步骤S102，将所述初始构型与所述目标构型的连接关系表达为邻接矩阵X

在本实施例中，链式模块化自重构机器人通过在连续空间中移动由模块组成的机械手来实现模块之间的分离和附着，由于模块化自重构机器人硬件模块的多样性，通常会泛化一个抽象模型以增加已开发算法的适用性。

在本实施例中，基于一个新的链式抽象模块，即多入度单出度模块(Multiple In-degree Single Out-degree，以下简称为MISO模块)，如图2所示，MISO模块的硬件特征是多个可互换的被动连接点和单个主动连接点。例如，图2中所示的FreeBOT和SnailBot，这两个模块都符合MISO模块的物理定义。

链式模块化自重构机器人的自重构可分为连接规划和运动规划两个阶段。连接规划提供了若干个子目标，指定在自重构过程中需要删除的连接点以及需要创建的连接点。运动规划则控制由模块组成的机械臂的运动，以实现这些子目标。因此，子目标是最优的还是冗余的，决定了整个自重构过程的速度。最优连接规划已被证明是NP完全的。这意味着不太可能存在多项式时间内计算出最优解的算法。

如图3所示，图3中右侧介绍了一个解释某些符号含义的示例。在该示例中，ID为u的根模块表示为M

模块化机器人的构型可以用邻接矩阵表示。比如，一个自重构实例可以由初始构型的邻接矩阵X

如图1所示，在本发明实施例的一种实现方式中，链式模块化自重构机器人的连接规划方法还包括以下步骤：

步骤S200，调用多项式时间算法对所述邻接矩阵进行求解，并以近优解的成本作为上界，初始化树型分枝与定界算法中分支及剪枝操作的循环框架。

在本实施例中，针对链式模块化自重构机器人的最优连接规划，首先采用多项式时间算法计算连接规划问题的近优解，然后用近优解的成本作为上界，通过新的分支函数和阶段成本的定义，不断逼近最优解。

具体地，在本实施例的一种实现方式中，步骤S200包括以下步骤：

步骤S201，调用所述多项式时间算法对所述邻接矩阵进行求解；

步骤S202，以所述近优解的成本作为上界，初始化所述树型分枝与定界算法中分支及剪枝操作的循环框架，分别对上界变量和下界变量进行赋值。

由于，最优连接规划的NP完全性表明连接规划的最优解D

如图4所示，本实施例中提供了最优规划方法的一个示例，图4中所示的方法流程为：在不同的CPU状态下使用多项式时间算法和指数时间算法来解决经常使用的自重构实例的连接规划问题。图4中所示的方法可以快速提供解决方案，同时在解决方案未达到最优时允许进一步优化和检测。

图4中所示的方法的流程主要包含多项式时间算法、指数时间算法和库；其中，库是一块计算机内存，记录了每个常用自重构实例的三个压缩矩阵：X

在图4中所示的方法的流程中，计算近优解的多项式时间算法可以使用现有的算法，比如Greedy-CM算法。以下讲述以近优解的成本作为上界计算最优解的指数时间算法-TBB算法。

如图1所示，在本发明实施例的一种实现方式中，链式模块化自重构机器人的连接规划方法还包括以下步骤：

步骤S300，调用BRANCHING函数对所述树型分枝与定界算法中的树进行分枝操作和剪枝操作，得到全局最优解。

在本实施例中，TBB算法提出了一种新的分枝函数和阶段成本的定义，通过不断循环的分枝和剪枝操作逐渐逼近连接规划问题的最优解；本实施例中的TBB算法是连接规划领域的一个全新的最优求解器。

具体地，在本实施例的一种实现方式中，步骤S300包括以下步骤：

步骤S301，创建一个OPEN列表，并根据根模块生成的所有节点初始化所述OPEN列表；

步骤S302，以从所述OPEN列表弹出的节点作为父节点，调用所述BRANCHING函数对所述树型分枝与定界算法中的树进行所述分枝操作，生成子节点。

在本实施例中，TBB算法的框架建立在分支操作和剪枝操作的循环之上；在执行TBB算法之前，首先创建一个OPEN列表，该OPEN列表用于存储需要进一步检查的各个节点，这些节点表示为x、y等。

在本实施例中，OPEN列表包含由

在本实施例中，TBB算法通过近优解的自重构步数初始化一个变量UPPER值，并通过最小自重构步数的下限初始化一个变量LOWER值。当OPEN列表不为空且变量UPPER的值>LOWER的值时，分支操作和基于边界的修剪操作将循环持续。分支操作以从OPEN列表弹出的节点x作为父节点，并调用BRANCHING函数生成子节点。

具体地，在本实施例的一种实现方式中，步骤S302包括以下步骤：

步骤S302a，根据预先定义的排列计算法、排列的乘法以及重新匹配法对所述树型分枝与定界算法中的树进行所述分枝操作，生成所述子节点。

在本实施例中，BRANCHING函数由三个操作组成，分别为：即预先定义的排列计算法、排列的乘法以及重新匹配法，通过三个操作可以确保生成所有可能的子节点：

第一个操作，对于x.matches中的每一个匹配

如图5所示，图5中(a)所示的

第二个操作，本实施例中定义了一种乘法，记为

如图5所示，图5中(b)所示的12条线表示将

第三个操作，如果上述两次操作后生成的子节点数量为零且长度为x.all

STAGE_COST函数的输入是BRANCHING函数生成的节点y，输出的是阶段成本c

具体地，在本实施例的一种实现方式中，步骤S300还包括以下步骤：

步骤S303，根据所述BRANCHING函数输出的每个子节点y，调用STAGE_COST函数以统计未匹配的子模块或者子空缺的数量，计算得到阶段成本c

步骤S304，根据计算得到的阶段成本c

在本实施例中，当OPEN列表不为空且变量UPPER的值>LOWER的值时，分支操作和基于边界的修剪操作将循环持续。根据BRANCHING函数生成子节点，计算每个子节点y的成本y.cost，它是x的成本和由STAGE_COST函数计算的阶段成本c

具体地，在本实施例的一种实现方式中，步骤S304包括以下步骤：

步骤S304a，根据计算得到的阶段成本c

步骤S304b，修剪确定的子节点及对应的后代节点。

在本实施例中，如果y.cost≥UPPER变量的值，则修剪掉节点y及其后代。节点y还有两个变量，y.matches和y.all。y.matches包含当前节点的所有匹配，y.all包含当前节点及其祖先的所有匹配，如图5中(c)所示。如果y.cost

如果y.cost

在本实施例中，通过循环上述分支操作和剪枝操作的，不断减小变量UPPER的值和OPEN列表的长度，通过这种循环可以逐渐逼近连接规划问题的最优解，直到获得全局最优解。

具体地，在本实施例的一种实现方式中，步骤S300还包括以下步骤：

步骤S305，循环进行所述分枝操作和所述剪枝操作，并逐渐减小上界变量值和OPEN列表的长度，直到获得所述全局最优解。

本实施例中通过采用TBB算法能够借助多项式时间算法的近优解初始化上界，也能够通过阶段成本的判断剪掉没前景的分枝，使得TBB算法相比于其它指数时间算法减少了大量的冗余计算，在当前技术中具有最小的理论计算复杂度。

如图1所示，在本发明实施例的一种实现方式中，链式模块化自重构机器人的连接规划方法还包括以下步骤：

步骤S400，根据所述全局最优解控制各多入度单出度模块进行连接。

在本实施例的一种示例中，如图6和图7所示，TBB算法计算最优解的过程如下所示：

在这个例子中，Greedy-CM算法计算的近优解由4个步骤组成，即

首先，将根模块

其次，从y

当TBB算法计算到节点y

上述分支和剪枝操作持续循环直到最优解，例如，在图6中节点y

本实施例通过上述技术方案达到以下技术效果：

本实施例基于多入度单出度模块的树型分枝与定界方法，采用近优解初始化上界，并通过新定义的分支函数和阶段成本的计算，逐渐逼近连接规划的最优解。不同于MDCOP等需要通过转化为DCOP问题来求解的方式，本实施例中的树型分枝与定界算法是连接规划领域的一个全新的最优求解器。树型分枝与定界算法能够借助多项式时间算法的近优解初始化上界，也能够通过阶段成本的判断剪掉没前景的分枝，使得树型分枝与定界算法相比于其它指数时间算法减少了大量的冗余计算，在当前技术中具有最小的理论计算复杂度。

示例性设备

基于上述实施例，本发明还提供一种机器人，包括：通过系统总线连接的处理器、存储器、接口、显示屏以及通讯模块；其中，所述处理器用于提供计算和控制能力；所述存储器包括存储介质以及内存储器；所述存储介质存储有操作系统和计算机程序；所述内存储器为所述存储介质中的操作系统和计算机程序的运行提供环境；所述接口用于连接外部设备，例如，移动终端以及计算机等设备；所述显示屏用于显示相应的信息；所述通讯模块用于与云端服务器或移动终端进行通讯。

所述计算机程序被所述处理器执行时用以实现一种链式模块化自重构机器人的连接规划方法的操作。

本领域技术人员可以理解的是，图8中示出的原理框图，仅仅是与本发明方案相关的部分结构的框图，并不构成对本发明方案所应用于其上的机器人的限定，具体的机器人可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。

在一个实施例中，提供了一种机器人，其中，包括：处理器和存储器，所述存储器存储有链式模块化自重构机器人的连接规划程序，所述链式模块化自重构机器人的连接规划程序被所述处理器执行时用于实现如上所述的链式模块化自重构机器人的连接规划方法的操作。

在一个实施例中，提供了一种存储介质，其中，所述存储介质存储有链式模块化自重构机器人的连接规划程序，所述链式模块化自重构机器人的连接规划程序被所述处理器执行时用于实现如上所述的链式模块化自重构机器人的连接规划方法的操作。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，计算机程序可存储于一非易失性存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本发明所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。

综上，本发明提供了一种链式模块化自重构机器人的连接规划方法及机器人，方法包括：将链式模块化自重构机器人中的每个模块设定为多入度单出度模块，并确定初始构型与目标构型的连接关系的邻接矩阵；调用多项式时间算法对邻接矩阵进行求解，并以近优解的成本作为上界，初始化树型分枝与定界算法中分支及剪枝操作的循环框架；调用BRANCHING函数对树型分枝与定界算法中的树进行分枝操作和剪枝操作，得到全局最优解；根据全局最优解控制各多入度单出度模块进行连接。本发明计算链式模块化自重构机器人在自重构过程中的连接规划问题的最优解，定义构型之间转换所需要的断开和连接的最少步数，最大限度地减少运动规划和实际动作所消耗的时间。

应当理解的是，本发明的应用不限于上述的举例，对本领域普通技术人员来说，可以根据上述说明加以改进或变换，所有这些改进和变换都应属于本发明所附权利要求的保护范围。