Self-reconfiguration of shape-shifting modular robots with triangular structure

Author links open overlay panel

Michael Gerbl, Johannes Gerstmayr

Show more

Add to Mendeley

Share

Cite

https://doi.org/10.1016/j.robot.2021.103930Get rights and content

Under a Creative Commons license

open access

Highlights

- •

Self-reconfiguration of adaptive modular robots with a triangular structure.

- •

Extended binary trees (EBT) as representation of topological configuration space.

- •

Reconfiguration by module movement along the surface of the robot system.

- •

Reconfiguration by construction of EBT by populating EBT-indices in ascending order.

Abstract

In this paper, we present a reconfiguration algorithm for shape-shifting modular robots with a triangular structure. The algorithm is derived from a novel description of the configuration space based on extended binary trees. Extended binary trees representing the same configuration are grouped into equivalence classes, which allows for a one-to-one correspondence between a configuration and its mathematical representation. Reconfiguration is then accomplished by a successive construction of the goal configuration, realized by moving individual modules along the surface of the robot and building up the binary tree of the goal configuration by populating unoccupied binary tree indices in ascending order with new modules. The algorithm is capable of solving the self-reconfiguration problem for modular robots with a triangular structure in  reconfiguration steps and is demonstrated on two reconfiguration examples. We then discuss the limits of the proposed methods, regarding constraints on the implementation and the lack of efficient collision avoidance, and outline possible resolutions.

- Previous article in issue

- Next article in issue

Keywords

Extended binary trees

Self-reconfiguration

Modular robots

Triangular modules

List of abbreviations

ATC

Adaptive Triangular Cell

BPS

Bypass Strategy

BT

Binary Tree

EBT

Extended Binary Tree

PARTS

Planar Adaptive Robot with Triangular Structure

SRP

Self-Reconfiguration Problem

- Notation

Set of binary tree indices

Extended binary tree object

Configuration

Set of interconnection indices

Set of left children

Set of right children

Set of surface indices of binary tree

Set of surface indices of extended binary tree

1. Introduction

The term programmable matter, first coined in the early 1990s, describes materials that can alter their physical characteristics like shape, conductivity, or optical properties according to external user specifications or autonomous sensing. Since its emergence, the research field of programmable matter has developed into an interdisciplinary field with efforts ranging from meta-materials [1], [2] over synthetic biology [3], [4] to quantum wells [5]. Robotics based approaches utilizing modular robots with self-reconfiguration capability present a promising candidate to realize the shapeshifting aspect of programmable matter [6], [7], [8], [9]. Such robot systems are typically built from a multitude of homogeneous robotic cells or modules, which can be arranged in a space-filling manner. Self-reconfiguration enables the modules to autonomously change their connection topology and the overall shape of the robotic system. The problem of transforming a modular robot autonomously from an initial to a desired configuration through motion primitives on a module level is referred to as the Self-Reconfiguration Problem (SRP). SRP is considered an extraordinarily challenging problem, as finding an optimal solution to this planning problem is proved to be NP-complete for chain-type modular robots [10], [11] and lattice-type modular robots with pivoting cube modules [12]. Further, there is a vast diversity in system design regarding degrees of freedom, motion capabilities, and kinematic constraints of modules. Thus, existing solutions to the SRP are hardware or application-specific and cannot easily be transferred from one modular robot class to another.

The Planar Adaptive Robot with Triangular Structure (PARTS), currently under development at the University of Innsbruck, is a two-dimensional modular robotic system built up from triangular modules. These robotic cells are arrangeable in a space-filling manner and can, therefore, reproduce arbitrary planar triangular meshes within the module’s geometric limitations. Taking into account the kinematic constraints of PARTS, the SRP has been solved for certain kinds of structured triangular meshes [13]. However, a solution for unstructured triangular meshes and thus arbitrary configurations of the PARTS system has as yet not been formulated.

The problem is further complicated by fundamental differences in the structure of the configuration space of PARTS compared to modular robots with a lattice architecture, such that present solution and planning frameworks are not easy to adopt.

In this paper, we introduce a novel abstraction method for the configuration space representation of modular robots with a triangular structure, like the PARTS system, based on extended binary trees and present a rule-based reconfiguration planning algorithm. The paper is organized as follows: In Section 2, we review and discuss related work to the subject of self- reconfiguration for modular robotic systems. Section 3 continues with a brief depiction of adaptive robots with triangular structures and the PARTS system as a representative of these types of robots. In Section 4, we introduce and motivate extended binary trees (EBT) as a novel abstraction method that can be used to represent the configuration space of modular robots with a triangular structure. Section 5 describes a reconfiguration planning algorithm based on the extended binary tree representation. We demonstrate the proposed reconfiguration algorithm on two examples in Section 6. Finally, we present several open problems in Section 7 and conclude in Section 8.

2. Related work

Robotic candidates for programmable matter are systems capable of forming space-filling structures, i.e., they can be arranged in a surface covering (two-dimensional) or volume covering (three-dimensional) manner. Modular robots with this ability consist almost exclusively of modules or submodules with a regular geometric shape, such as square [14], [15], [16], [17], circular [6], [18], [19], or hexagonal [20], [21] modules in 2D or cubic [15], [22], [23], [24], [25], octahedral [26], rhombic dodecahedral [27], or spherical [9], [28], [29], [30] modules in 3D, respectively. The uniform geometry allows for organizing the robotic units in a regular lattice, similar to the atoms in a crystal, such that each module occupies a well-defined lattice position.

Some robots with a regular cell geometry permit arbitrary connection points, which enable the construction of non-lattice configurations [29], [30]. However, the connector design limits these systems in their aptitude to construct durable self-reconfigurable space-filling structures, as connectors support only a limited number of connection cycles [29] or modules feature only one connector [30], thus limiting possible configurations to a chain or tree architecture.

One advantage of the lattice architecture is the description of module positions by unique integer-valued coordinates with respect to a predefined reference frame. This description is possible for all two- or three-dimensional lattices as they can be assigned to one of 5 grid types in 2D or 14 grid types in 3D, respectively. These so-called Bravais lattices are well-known in solid-state physics (see e.g. [31]). A configuration of the modular robot is thus uniquely characterized by the entity of occupied places in the lattice and can be represented by the set of lattice coordinates corresponding to the location of modules [18], [32], [33], [34], [35], [36]. The lattice architecture also proves beneficial for addressing the SRP beyond providing an abstraction method for the configuration space. The lattice offers distinct neighborhood relations between modules, which are frequently incorporated in local control schemes [16], [37], [38], [39], and a simple distance metric that allows calculating distances between module positions [25], [26], [40], which can be included in the reconfiguration strategy, e.g., as a simple heuristic to guide informed search methods [36].

Solutions to the SRP can generally be grouped into search-based, control-based, or agent-based approaches [41], [42]. Search-based approaches treat the SRP as a search problem, i.e., they try to find a sequence of module moves that reconfigures the robot from a given initial configuration to a desired goal configuration. The search space is typically represented as a configuration graph, where each node represents a configuration and each edge a transition between configurations via a set of feasible module actions. The solution to the SRP is a path from the initial configuration to the goal configuration. The configuration graph, however, suffers from exponential growth of the branching factor with increasing module numbers. The complexity of the search space hence quickly becomes intractable, such that uninformed, brute force search approaches are impractical for a large number of modules. They may, however, be applied for the motion planning of individual modules [15].

Informed search techniques, on the other hand, rely on heuristics that measure the quality of a configuration and thereby guide the search efficiently through the search space towards the goal configuration. Various types of metrics have been proposed for quality assessment like overlap, minimal number of moves, optimal assignment [40], or graph edit-distance [43]. Many authors incorporate the measures of distances in the lattice into their search heuristic [36], [44]. These search strategies are often combined with additional simplification methods to make the search tractable, like the usage of meta-modules to increase motion capabilities [22], [26], [44], [45], scaffolding [33], [46], or intermediate configurations with a specific structure like chains or lines [15], [47].

However, since search-based approaches rely on global information, movement commands for modules are dictated by a centralized controller. For large systems with a myriad of modules, this constitutes a single point of failure, thus making a distributed local control architecture more desirable. Hence it is not surprising that recent research has shifted away from global search to this decentralized paradigm. Control-based approaches do not rely on global information but incorporate local information through inter-module communication, such that the individual modules move independently to reconfigure into the goal configuration. Independent module movement implicates a reconfiguration speed-up by parallelization through a simultaneous module motion at the cost of additional caretaking for collision avoidance [48], [49], preserving connectivity [25], [48], and guaranteeing the convergence to the goal configuration [42]. Proposed control strategies are but not limited to predefined local rules [16], [50], [51] to incorporate human experience and knowledge, coordinate or gradient attractors to guide module movement along the surface [27], [52], [53], or recruitment of free modules by other modules adjacent to empty goal positions [54].

Local rules are frequently employed in the form of cellular or finite automata. Each module possesses a limited computational power and memory and decides upon moving by sole consideration of the information of neighboring modules [39], [55]. Similar to search-based approaches, control-based methods also utilize simplification techniques like meta modules [16], [25], [48] or scaffolding [48], [49] to increase the motion capabilities of modules or intermediate structures [56] to ease reconfiguration. One drawback of many distributed algorithms is that global knowledge of the goal configuration or its representation is assumed to be known by all modules, raising the need for efficient shape description techniques [57]. Alternatively, it is sufficient that the goal configuration is known by at least one module, the so-called leader, which can be externally designated or chosen by the modules themselves [37].

In agent-based or task-based approaches, the focus of reconfiguration is set on the functionality of the goal configuration rather than on the convergence of the system to a particular configuration topology. A specific configuration hence emerges as a byproduct during the completion of the task. The reconfiguration is tailored to the task that is to be completed and always includes interaction with the environment, for example, locomotion over unstructured or uneven surfaces through cluster flow [58], [59], [60] or task-driven growth to enclose objects or support structures [61]. However, we are focused on a faithful reconfiguration that converges to a specific goal topology and will not consider agent-based approaches any further.

A comprehensive survey of different self-reconfiguration methods is given in [42] or [57], with the latter focusing in particular on self-reconfiguration methods for programmable matter. Although there exists extensive research for cube-style or spherical modular robots, little work has been done to investigate the SRP for modular robots with triangular structure. Adaptive robots with a triangular structure, like the PARTS system, however, have their peculiarities, which differ significantly from modular robots with lattice architecture and complicate the adaptation and application of existing planning frameworks and reconfiguration methods to solve the SRP.

3. Adaptive robots with triangular structure

Adaptive robots with a triangular structure consist of planar modules with a triangular geometry. One module can connect to up to three other modules along its edges. The modules have no fixed but an adaptive geometry, i.e., they can change their shape by varying their edge lengths via linear actuation. This variable geometry allows multiple modules to be arranged in a surface covering manner. Hence, they can reproduce arbitrary planar triangular meshes within the geometric limitations of the modules.

Although two-dimensional modular robots have little practical application [41], they have proven useful for testing the feasibility of mechanical design aspects and algorithms, which may eventually be adapted to corresponding three-dimensional systems, successfully demonstrated, e.g., with the FireAnt [19] and FireAnt3D modular robot [29], with the Crystalline [47] and Telecube systems [22], [62], or 2D Catoms [63] and 3D Catoms [9]. The study of adaptive robots with triangular structure, hence, gives valuable insight for the development of adaptive robots with a tetrahedral structure, such as the ARTS modular robot system [64]. One realization of an adaptive robot with a triangular structure is the PARTS system, which we will describe in more detail.

3.1. Hardware design

The Planar Adaptive Robot with Triangular Structure (PARTS) is an adaptive modular robot with a triangular cell geometry, currently in development at the University of Innsbruck. PARTS is built up from multiple Adaptive Triangular Cells (ATCs), which feature a symmetric triangular design consisting of three linear actuators that correspond to the edges of the triangle and are linked together by three revolute joints, corresponding to the vertices. An ATC has 3 degrees of freedom and can vary its shape by continuously changing the edge lengths via linear actuation. The current ATC design admits an effective elongation of the idealized triangular edges of 43.4 percent, which corresponds to a minimum attainable interior angle of 44.2 and a maximum interior angle of 91.6. Each edge is equipped with a hermaphroditic male–female connector pair that allows for orientation-independent docking, such that two ATC can establish a connection along an edge.

For further information on the mechatronic design of PARTS, see [65]. In the following text, we will use the acronyms PARTS and ATC interchangeable to describe the entire class of modular robots with a triangular structure and the individual modules of such a robot, respectively.

The triangular module design distinguishes the PARTS system from all modular robot systems with a lattice architecture as (i) PARTS can build up space-filling triangular meshes, which are not bound to a lattice structure, and (ii) these space-filling meshes are due to the module design adaptive, i.e., they can change their morphological shape without modifying the underlying connection topology. Fig. 1 shows two PARTS systems, each consisting of 6 ATCs, that feature the same configuration topology but form two different morphological shapes (a) and (b).

Not being bound to a lattice architecture comes with its pros and cons. Triangular meshes are more flexible regarding module placement, orientation, and movement, which is not restricted by the lattice such that the robot can better adapt to the environment. The adaptivity further allows for fulfilling particular tasks without a topological change in the configuration, like grasping an object or locomotion. Fig. 2 shows PARTS in a gripper-like configuration (a) grasping a circular object by changing the shape of ATCs without topological reconfiguration such that the object is grasped by enclosing. Fig. 3 depicts an example locomotion pattern, similar to the peristaltic motion of some invertebrates like worms. The motion consists of propagating compression waves that travel from the rear end to the front combined with a simultaneous lift of contact points from the ground. Performed periodically (b–e), the result of this locomotion pattern is a continuous forward motion.

1. Download : Download high-res image (383KB)

2. Download : Download full-size image

Fig. 1. PARTS system, consisting of 6 connected ATCs with the same connection topology but different morphological shapes (a) and (b).

1. Download : Download high-res image (114KB)

2. Download : Download full-size image

Fig. 2. Grasping of a circular object by enclosing: An object (a) can be grasped by PARTS without topological reconfiguration by changing the shape of ATCs such that the object is enclosed (b).

1. Download : Download high-res image (265KB)

2. Download : Download full-size image

Fig. 3. Locomotion of PARTS without topological reconfiguration applying a peristaltic-like motion primitive: From the initial configuration (a), motion is initialized at the rear end (b) using a compression wave with a simultaneous leg raise traveling through the length of the body to the front end (b–e). This compression wave can be reinitiated at the rear end to enable continuous forward motion.

3.2. Self-reconfiguration concepts

In general, we can distinguish three broad concepts to realize a self-reconfiguration of PARTS, based on the number of modules involved during one reconfiguration step. These are (i) reconfiguration by single module movement, (ii) reconfiguration by meta-module movement, and (iii) global cluster reconfiguration. We will elaborate on the first reconfiguration concept of single module movement and outline the approaches (ii) and (iii).

A single ATC has only limited motion capabilities. One module can continuously alter the length of each edge between 1 and 1.434 times the minimum edge length. If the ATC is connected along an edge to another ATCs, an alteration of this edge’s length is only possible by simultaneously changing the length of the corresponding edge of the connected ATC in the same manner. In addition to this shape deformation, a single ATC can disconnect from an adjacent module with an existing connection or connect to an adjacent module if the connecting edges have the same length and are properly aligned. The sequence of connecting and disconnecting enables the single ATC to change its position in the connection topology. In general, however, it is not possible for a single ATC to properly align the edges to establish a new connection. Hence, to move a single ATC to a new topological position requires coordinated motion of multiple ATC in the vicinity. The basic method of motion for a single ATC consists of the action sequence move, connect, disconnect, and move. We term the ATC that is supposed to move the moving ATC, the ATC, to which the moving ATC will dock and form a new connection the connecting ATC, the free edges, which are initially unconnected and subsequently used for the new connection between moving ATC and connecting ATC the connecting edges and the ATC(s), to which the moving ATC is initially connected the connected ATC(s).

In the first step, the moving ATC and connecting ATC have to align their connecting edges. The alignment is accomplished by deformation of the moving and connecting ATC as well as of adjacent ATCs. Once the connecting edges are properly aligned, the moving ATC and connecting ATC can dock and establish a connection. Subsequently, the moving ATC undocks from the connected ATC(s) and hence terminates all initial connections. In the last step, all ATCs involved in the movement process restore their original shape by resetting their edge lengths to the previous values. This action sequence changes the moving ATC’s position from initially being connected to the connected ATC(s) to being connected to the connecting ATC, while the remaining topology is unaffected.

We only consider potential new connections between two ATCs that initially have a vertex in common, such that the ATCs can connect by forming a kinematic loop around this common vertex, as depicted in Fig. 4. Although module locomotion by connecting two chains of ATCs is, in theory, possible, the alignment accuracy of the connectors is practically limited by actuator imperfections and imprecision in module motion, which lead to an accumulation of errors in the kinematic chains [65]. Hence, exact positioning and alignment within the tolerances of the connectors cannot be guaranteed without feedback from additional sensors like infrared [66] or hall sensors [67] for guidance during the connection process.

The connection process of two ATCs by forming a kinematic loop around a common vertex is shown exemplarily in Fig. 4 with four modules. The hardware realization of PARTS admits forming kinematic loops consisting of at least four modules. In the present work, however, we assume that three modules sharing a common vertex are sufficient to establish a kinematic loop. We will refer to the precondition of at least three ATCs around a vertex to form a new loop as closing condition. In order to fulfill the closing condition, three ATCs must be able to complete the full angle around their common vertex. Thus, modules must be capable of changing their geometry in such a way as to form interior angles of at least 120. This requirement corresponds to an effective edge elongation factor of , resulting in a minimal interior angle of 30.

1. Download : Download high-res image (70KB)

2. Download : Download full-size image

Fig. 4. Movement of moving ATC ① from connected ATC ② (a) to connecting ATC ④ (c) by forming a kinematic loop ①-②-③-④ (b) around the common vertex.

The closing condition with at least three ATCs required to form a kinematic loop significantly increases the number of potential new kinematic loops compared to a minimum requirement of four ATC in a loop allowing for specific reconfiguration strategies not deployable otherwise. Although this relaxed closing condition makes the proposed reconfiguration approach not suitable to be employed on the current hardware system, an improvement of the hardware design to reach the required maximum interior angles or an extension of the reconfiguration algorithm to the stricter closing condition with a maximum interior angle of at least 90 or edge elongation factor  can be expected in the near future. Thus, the locomotion process can be summarized in the two sequential steps of closing and opening a kinematic loop.

- (1)

Closing: Modify actuator lengths to form a kinematic loop and connect moving ATC and connecting ATC along the free connecting edges Fig. 4(a)  (b), connect moving ATC ① and connecting ATC ④

- (2)

Opening: Terminate previous connection(s) of moving ATC with connected ATC(s) and restore original actuator lengths Fig. 4(b)  (c), disconnect moving ATC ① and connected ATC ②

This method of module locomotion is similar to the frequently used rolling of modules around neighboring cells on the surface [20], [21], [24]. However, one ATC cannot perform the movement by itself but needs adjacent ATCs in the new kinematic loop to alter their shape as well. In general, also the mesh in the vicinity of those modules needs to adapt, which complicates the connection process.

Some of these problems can be surmounted by moving so-called meta-modules, composed of more than one ATC, instead of single modules. Meta-modules have greater mobility than single modules enabling them to move by themselves without assistance from other modules. The meta-module size and shape can either be fixed or variable. A fixed size and shape generally limit the granularity of configurations and, in the case of PARTS, dictate a regular mesh structure, e.g., for quadratic meta-modules, consisting of 4 ATCs, a quadratic lattice as depicted in Fig. 5. The prescribed lattice restricts the placement of modules, which also inhibits the adaptability of the robot system. Variable meta-modules regarding the number of modules and meta-module topology, on the other hand, emerge from the environment created by other modules and move as an ensemble to a new position, thus setting no constraints on the module mesh. However, the choice of meta-module size and shape is not trivial, as a reconfiguration of the system must be guaranteed in all possible circumstances.

1. Download : Download high-res image (85KB)

2. Download : Download full-size image

Fig. 5. Self-reconfiguration using meta-modules, consisting of 4 ATCs arranged in a square; The resulting mesh is also a regular square mesh. The gray meta-module on the top right (a) is moved by connection with an adjacent meta-module (b) to the next lattice position (c).

The last reconfiguration concept is based on the movement of large clusters of modules, such that reconfiguration is achieved by a small number of global reconfiguration steps. The initial and goal configurations are searched for similar sub-configurations that can be moved as a whole from the initial position to the goal position. This reconfiguration approach is the fastest and most efficient regarding execution, but computationally the most demanding in planning. Another drawback presents the potential loss of structural integrity caused by overstress and subsequent failure of intermodular connections [68], [69] or the inability of actuators to deliver sufficient force for movement of large structures. Fig. 6 depicts an example of this reconfiguration approach, where an initial tower configuration is reconfigured in one step to a square. The configurations in Fig. 6(b) and (c) require further examination of the forces acting on the connectors and actuators around the narrow hinge to guarantee the structural integrity of the robot system during reconfiguration.

In this work, we focus on the reconfiguration of PARTS, represented as a triangular mesh, by the movement of single ATCs. Since arbitrary triangular meshes are, in general, unstructured, a description of the configuration using lattice coordinates is not feasible. Thus, a different abstraction method for the configuration space of PARTS is required. This method should uniquely describe a distinct configuration and also allow for a determination of relative positions between modules and similarities between configurations.

1. Download : Download high-res image (155KB)

2. Download : Download full-size image

Fig. 6. Self-reconfiguration by moving a large cluster of modules.

4. Configuration space

The PARTS system can be represented by a planar triangular mesh. In order to guarantee the kinematic determination of PARTS, we suppose in our model that one module is constrained by fixing one free edge of that module to the environment. This assumption might be realized by a real physical connection of that module to the surrounding, or it might be a temporarily assigned module, which is in constant contact with the surrounding and not changing its location during the current reconfiguration process. Based on this model, we introduce in this section a novel representation method for the topological configuration space of PARTS based on extended binary trees.

First, we distinguish geometric and topological configurations and then state the desired properties of the configuration space representation. Subsequently, we review existing abstraction methods of the configuration space for other modular robots and discuss their shortcomings when applied on PARTS. We then introduce extended binary trees as a novel representation method of the configuration space and group binary trees that correspond to the same configuration to equivalence classes. In the last part of this section, we propose a distance measure on extended binary trees that enables us to compare the similarity of two configurations.

4.1. Geometric and topological configuration

We want to distinguish between the geometric configuration of PARTS, given by the morphological shape of the robot system, and the topological configuration, given by the connection topology of the individual ATCs. Due to the continuous mode of actuation, two distinct geometric configurations that exhibit the same topological configuration (i.e. an identical connection topology between modules) can be morphed into each other without changing the underlying connection topology (see e.g. Fig. 1). The SRP, hence, reduces to transforming the topology of the initial configuration to the topology of the goal configuration. Distinct geometric configurations emerge as a by-product from intermediate topological configurations during the reconfiguration process. The final geometric configuration can then be morphed into the goal geometry by continuous module deformation.

The geometric configuration of PARTS contains the topological information of individual connections between modules and the exact shape of all modules. Individual edge lengths must comply with connectivity (i.e. connected edges have equal length) and loop closure constraints. One way to represent the geometric configuration is by a planar triangular mesh. There have been various methods proposed to represent triangular meshes for use in finite element methods and computer graphics. The connectivity of a triangular mesh is represented by the vertices(1)the edges(2)and the triangular elements(3)Vertices and edges can be combined to form the graph . To describe the geometry of the configuration, it is sufficient to specify the position of all vertices  in , which is equivalent to a planar embedding of the graph  in . Alternatively, the triangular mesh geometry can also be constructed by specifying the length of all edges , starting from the constrained module which is connected to the surrounding.

Although topological information is indirectly encoded in the mesh structure, this structure is impractical for reconfiguration, as topological changes alter the number of edges and vertices, creating an overhead of additional bookkeeping and obscuring the underlying topological changes. This deficit raises the need for a better suited topological representation for reconfiguration purposes. In the remaining part of this section, we will focus on the configuration space of topological configurations and their representation. If not stated otherwise, we refer to a topological configuration henceforth simply as configuration.

4.2. Properties of configuration space representation

A PARTS configuration  consists of  ATCs  arranged in a triangular mesh, in which modules intersect either at one edge or not at all. Two ATCs  and  are connected if they share one edge. In this case, ATC  is called ATC ’s neighbor. We are interested in a mathematical representation of this topological configuration space that should hold the following properties:

- I.

Uniqueness: One representation maps precisely to one distinct configuration.

- II.

Uniformity: All ATCs are homogeneous and isotropic, i.e., they all have the same mechanical design and symmetric structure. Thus, one specific connector is not distinguishable, only the relative locations of one connector to another one. Arbitrarily chosen module identifiers shall not influence the topological representation. Hence, a configuration is only determined by the connection topology and not by specific connections between specific connectors of individual ATCs.

- III.

Similarity measure: The representation allows for measuring the similarity between two configurations and for identifying isomorphic representations.

Ideally, a configuration should also map uniquely to a distinct representation. As a unique mapping might not be feasible, it should at least be facile to distinguish isomorphic representations, i.e., two representations that correspond to the same topological configuration.

To motivate the need for a novel abstraction method to represent the configuration space of PARTS, we will first review existing abstractions methods and evaluate their applicability as a suitable representation for modular robots with a triangular structure.

4.3. Review of existing abstraction methods

As mentioned in Section 2, modular robots with lattice architecture often use lattice coordinates to describe the configuration space in reconfiguration planning [7], [15], [27], [40], [59]. Triangular meshes are, in general, unstructured and lack the regularity required to assign unique coordinates to each module position. Thus, lattice coordinates are not feasible to represent the configuration space of unstructured meshes. Another commonly used group of abstraction techniques is based on graphs and their incidence matrices [47], [70], [71]. These methods, however, lack to express the modular robot configuration uniquely since the information of connection port and orientation is missing [42]. Some authors proposed solutions to this problem by extending the graph to a so-called connector-graph [72] or the incidence matrix to a so-called assembly incidence matrix (AIM) [73], [74] or face–face incidence matrix (FFIM) [75] to differentiate connecting points and connection orientations. Methods of graph theory have been successfully applied to enumerate non-isomorphic configurations and distinguish isomorphic configurations for a distinct number of modules in the AIM representation [73]. However, the analysis of isomorphic configurations requires the calculation of all graph automorphisms to that configuration, hence making it infeasible for a large number of modules. Furthermore, these representation methods lack a similarity measure, thus making it impossible to compare two configurations for their similarity.

A natural way to describe a triangular mesh would be with mesh representation techniques applied in finite element methods using nodes, edges, and elements. These description methods are, however, designated for meshes that do not change their topology. The docking and undocking of ATCs would consistently change the number of edges and nodes, making this approach impractical. We can deduce from the element-node connectivity relations an element topology matrix, as two elements are connected if they share an edge. Labeling the edges of each element with the local edge numbers  in a counter-clockwise manner, the element topology  is a  matrix, such that  is the element identifier  if element  is connected with element  at the local edge  or 0 if no neighbor is present. The element-topology matrix contains all relevant topological information, such that it can uniquely be mapped to a distinct configuration. There is, however, a vast number of isomorphic representations, as a relabeling of ATCs and connection ports does not alter the configuration. This corresponds to

- •

random permutation of the element identifiers, corresponding to a relabeling of ATCs and

- •

cyclic permutation of the local edges for every element, corresponding to an orientation preserving relabeling of the local edges.

Thus, for  elements, there are  different representations of the same topological configuration. With no further information, it is hence cumbersome to evaluate the equality or similarity of configurations.

The reviewed abstraction methods lack one or more of the desired properties for a suitable representation of the configuration space, given that they either fail to capture the module symmetry, distinguish the connection orientation, or enable facile identification of similarity and isometry between configurations. Thus, we propose a novel abstraction method for reconfiguration planning of modular robots with a triangular cell geometry based on extended binary trees (EBT).

4.4. Extended binary trees

As stated at the beginning of this section, we presume in our model of PARTS that one module is constrained and fixed with one edge to the surrounding. A configuration of PARTS can thus be considered a highly parallel robotic manipulator where the constrained module represents the connection to the ground. Such parallel mechanisms with closed kinematic loops can be described by their kinematic spanning tree and loop closure equations. The kinematics of the parallel mechanism is reduced by a notional slicing of all loops to a tree structure. Kinematic loops are then included with additional loop closure constraints in the formalism (see e.g. [76]). We will apply the concept of slicing open kinematic loops and then including means to establish loop closure on PARTS. We accomplish this by (1) ignoring connections that create loops to describe PARTS by its spanning tree and (2) including the previously not considered connections through an extension in the tree structure. We will later see that the resulting structure fulfills all desired properties of Section 4.2 and has beneficial computational properties for self-reconfiguration planning.

The constrained module is the only module distinguishable from all other modules, as it can merely establish a maximum of two connections with further ATCs due to the constrained edge boundary condition. Choosing the constrained ATC as the root of the spanning tree, an arbitrary configuration of the PARTS system can then be represented by a kinematic tree with interconnections. Fig. 7 shows one possible kinematic spanning tree (b) for a specific configuration of PARTS (a). Additional interconnections are indicated by dashed lines. In a first step, however, we will omit these interconnections, such that the configuration is given by an open tree without any kinematic loops. Note that each ATC besides the root ATC is part of a kinematic chain with one connection to a preceding module, referred to as parent ATC, and up to two connections to succeeding modules, referred to as children of the respective ATC. Based on the orientation of a child connection with respect to the parent ATC, we can distinguish between a right child ATC and a left child ATC. Consequently, due to the maximum number of two successors, the resulting tree is also referred to as Binary Tree (BT).

We can describe each element in a BT with a unique number termed binary tree index (BT-index) . The BT-index of an ATC is determined recursively and depends on the connection orientation (left or right) with respect to and the BT-index of the parent ATC. If the parent ATC holds the BT-index , the right child is assigned the BT-index  and the left child the BT-index . The indexing scheme is schematically illustrated in Fig. 8. If the index  is prescribed for the root, the complete binary tree  is uniquely defined for  ATCs by specifying the BT-indices  for each ATC, i.e., (4)

1. Download : Download high-res image (186KB)

2. Download : Download full-size image

Fig. 7. Representation of a PARTS configuration (a) by a kinematic tree with interconnections (b).

Any kinematic tree with a designated root and at most two distinguishable descendants per element can thus be represented by a binary tree. Fig. 9 shows the translation of a specific PARTS configuration (a) to a binary tree (b), with the associated BT-indices to the right of the tree elements, as well as the corresponding set of BT-indices  (c). The figure also depicts the hierarchical structure of the tree, which is organized into different levels. For a given BT-index , the level of the corresponding element in the tree can be determined by . The largest level corresponds to the height of the tree. We also define the surface  of the tree as the set of all right child elements(5)and the set of all left child elements(6)that are not already part of the binary tree  themselves, i.e., (7)

1. Download : Download high-res image (85KB)

2. Download : Download full-size image

Fig. 8. Binary tree indexing scheme of adjacent ATCs to an arbitrary ATC with index .

1. Download : Download high-res image (136KB)

2. Download : Download full-size image

Fig. 9. Translation of a PARTS configuration (a) to a binary tree (b) and the set of binary tree indices  (c). The numbers next to the elements of the tree are the corresponding BT-indices.

As binary trees can only describe open kinematic trees with no interconnections between or within individual kinematic chains, we extend the BT-structure to also account for kinematic loops. We will first focus on the description of interconnections using additional BT-indices from the surface . In the next subsection, we will resolve the ambiguity caused by the arbitrary choice of interconnections within a kinematic loop.

We describe an interconnection between two modules  and  by appending an additional element from the surface  to the BT-indices of the two modules, that form the respective connection. This number, termed interconnection index (IC-index) , is chosen for ATC  with BT-indices  based on the orientation of the connection to ATC  as right child index  or left child index  of ATC  with BT index  and vice versa for ATC . Thus, the interconnection index describes the notional position of the module in the binary tree if the connected ATC  was the parent of .

As an example, we consider the configuration of Fig. 9, which is once again depicted in Fig. 10(a). The BT, with interconnections sketched as dotted lines, is shown in (b). The encircled numbers correspond to arbitrarily chosen ascending ATC identifiers to allow simple identification of associated elements in the configuration and binary tree. The configuration contains two kinematic loops and, thus, has two additional connections in the binary tree. In the example, these interconnections are between the ATCs ④ and ⑥ as well as ⑤ and ⑦. If we, for instance, consider the connection between ATCs ④ and ⑥, ATC ④ would be the left child of ATC ⑥ with BT-index 5, hence having the BT-index 11 if the connection to the parent ATC ③ was removed. In contrast, ATC ⑥ would have as the right child of ATC ④ with BT-index 6 the BT-index 12 if the connection to parent ATC ② was removed. By adding these imagined binary tree positions to the corresponding BT-indices, distinct interconnections can be uniquely described. In Fig. 10(b), the circled numbers are ATC identifiers, the numbers next to the circled identifiers correspond to the BT-indices of the individual elements, and the interconnection indices are given by the small numbers next to the dotted interconnections.

1. Download : Download high-res image (173KB)

2. Download : Download full-size image

Fig. 10. Description of a specific PARTS configuration (a) by an extended binary tree (b). The corresponding array structure for the representation of the extended binary tree is shown in (c).

Since an ATC can, in general, have up to two such additional connections not included in the open tree structure, each BT-index  is expanded by a set of up to two interconnection indices(8)such that(9)

If there are no interconnections to ATC

, then . We combine BT-indices and interconnection indices to form a new object, the extended binary tree (EBT)  of the configuration, given by(10)

The EBT  can be represented as an array of size , where row  contains the BT-index

of ATC  and two numbers encoding . These are set to the elements of  and padded with zeros if . By sorting the rows in order of ascending BT-indices, it is possible to describe the configuration without referring to the particular ATC identifiers, thus treating all ATCs uniformly and fulfilling property II (uniformity) of the desired properties of the configuration representation.

We further define the set of all interconnection indices  as the unification of all , i.e., (11)and the surface  of the EBT as the surface  corresponding to the binary tree  without the interconnections , i.e., (12)The structure of the BT can also be exploited to sort the BT-indices of the surface  in a counter-clockwise direction starting from the root. The order is obtained by sorting the surface ordering terms(13)in an ascending manner. This is always possible since, for an arbitrary BT-index , the right child inherits the surface ordering term from its parent, that is,(14)whereas the left surface ordering term is always larger, since the logarithm is a strictly monotonically increasing function and the indices  and  are in the same level of the BT, hence the integer part of the logarithm is the same. The ordering scheme also holds for successive left children in different levels of the tree, e.g.  and , as(15)using again the monotonic property of the logarithm. ATCs with an earlier (parent-)branch-off to the left are hence always posterior in the surface order.  □

4.5. Equivalence of EBTs

The representation is not yet unique since the interconnections within a kinematic loop can be chosen arbitrarily. Hence, there are different EBTs corresponding to the same PARTS configuration. For example, considering the configuration in Fig. 10(a), instead of choosing the interconnection between ATC ④ and ATC ⑥, we can also select the interconnection between other modules of the same kinematic loop, e.g., between ATC ④ and ATC ③. The corresponding EBT is depicted in Fig. 11(a) and describes precisely the same configuration. To resolve this ambiguity, all EBTs that represent the same configuration can be combined to form an equivalence class of EBTs with the equivalence relation . Two EBT  and  correspond to the same configuration if they belong to the same equivalence class, i.e., .

Individual elements of a specific equivalence class can be transformed into each other employing equivalent transformations. An equivalent transformation  is defined as(16)

1. Download : Download high-res image (142KB)

2. Download : Download full-size image

Fig. 11. Transformation between two different EBTs (a) and (b) of the same equivalence class by changing the position of ATC ④ (gray) in the ETB. Encircled numbers describe module identifiers; large numbers next to the encircled numbers are the associated BT-indices; small numbers correspond to interconnection indices.

This transformation swaps an interconnection of one element with the regular connection to the parent ATC. That is, the interconnection index  and BT-index  for ATC  are interchanged. Subsequently, the corresponding interconnection index is removed from the new parent, the correct interconnection index w.r.t the altered BT index of  is added to the old parent, and all indices of children and further descendants of element  are adjusted accordingly, as shown in Algorithm 1. The algorithm has a computational complexity of  and is limited by the determination of all subtree ATCs (the transformation of all subtree indices can be realized efficiently using vector operations). For example, Fig. 11 shows the transformation between two EBTs (a) and (b) of the same equivalence class, where the regular connection between ATC ④ and ATC ⑥ in (a) is swapped with the interconnection between ATC ④ and ATC ③. The BT-index 11 of ATC ④ is hence interchanged with the interconnection index 6, the old interconnection index 23 belonging to ATC ③ is removed, and the interconnection index 12 describing the new interconnection is added to ATC ⑥ (ATC ⑥ would be the right child to ATC ④ with BT-index 6). The BT-index of the child ATC ⑦ is adapted to the new position in the tree as the left child of BT-index 6, as well as the interconnection index of ATC ⑤, which decodes the interconnection with ATC ⑦.

1. Download : Download high-res image (204KB)

2. Download : Download full-size image

An equivalent transformation can also be performed in a distributed manner utilizing inter-module communication. Suppose each ATC stores its BT index and interconnection indices. After identifying ATC  with interconnection index , ATC  initializes the transformation swapping its BT-index  with interconnection index . In a first step, ATC  communicates with its neighbors by exchanging BT indices and interconnection indices in order to determine old and new parent ATC. The new parent ATC  with(17)is ordered to remove interconnection index  with  from . The old parent ATC  with(18)is instructed to add the interconnection index(19)to . The second term in (19) accounts for the orientation shift of the ATC in the binary tree due to the new parent ATC. The last action of ATC  is to signal its child the new BT index (now ) and a command to switch orientation (from left to right child and vice versa). The child then propagates the index change to its neighbors by transmitting old and new BT index  and . Up on receiving an index change, ATC  performs one of following action:

- •

if   and propagate index change to neighbors

- •

if  for one   and terminate propagation

Thus, the indices of the whole subtree and all corresponding interconnection indices are adapted.

In order to uniquely describe a distinct equivalence class, the EBT with the smallest BT-indices is chosen as the representative of the corresponding equivalence class. The representative EBT can be determined by recursively performing equivalent transformations for all elements with a BT-index  larger than the smallest interconnection index of , i.e., ,  since an equivalent transformation swaps BT-index  and interconnection index  for a specific ATC, and either  or  holds, as  and  are by definition disjunct sets, i.e., .  □

Thus, the representative EBT for one equivalence class gives a unique description of a specific configuration of PARTS, hence fulfilling property I (uniqueness) of the desired properties of the configuration representation. The representation is invariant under permutation of ATC identifiers and connection ports, giving a one to one correspondence between a configuration  and an EBT representation . The transformation to the representative EBT can also be performed in a distributed and parallel manner, letting each module  with an interconnection index  independently initialize an equivalent transformation.

4.6. Similarity of EBTs

To compare two EBT and assess their similarity, we define the similarity transformation(20)as a sequence of specific equivalent transformations and the configuration distance(21)comparable to the overlap metric introduced in [40]. The configuration distance is a measure to quantify the similarity between two configurations, given by their EBTs, and further enables the detection of isomorphic configurations.

Given the set of all interconnection indices  of the EBT , the similarity transformation  maximizes the number of equal BT-indices  in  and the transformed EBT . As shown in Algorithm 2, this maximization is accomplished by recursively performing equivalent transformations on  for all interconnection indices  that are elements of , i.e. . Equivalence transformations are omitted if the BT index associated with an interconnection index to be transformed is already parts of the common binary tree, i.e. all indice  with , as such an equivalent transformation would not increase the number of common BT-indices. Thus, equivalence transformations are performed until(22)where(23)

In order to execute a similarity transformation in a distributed manner, the set of final BT indices  must be known by all ATCs. If the set size exceeds the module memory capacity, the set can be split and broadcasted sequentially. Each element performs the calculation in (22) using only its own BT ind IC-indices for each received subset and initiates an equivalent transformation, if the resulting set is not empty.

1. Download : Download high-res image (116KB)

2. Download : Download full-size image

For two configurations, given by the EBTs  and , each with  ATCs, the configuration distance  is defined as(24)where  denotes the cardinality of a set,  for  is the set of BT-indices corresponding to  and  and  is given by the similarity transformation  and , respectively. The configuration distance corresponds to the number of non-overlapping modules, i.e., modules that are not at the correct position in the configuration topology given by the two EBT.

The configuration distance enables comparing the similarity of two EBT and allows for the identification of isomorphic configurations. Hence, property III (similarity measure) of the desired properties of the configuration representation is fulfilled. Note, however, the configuration distance is not a metric regarding the mathematical definition, as it does not fulfill the triangle inequality. A counter-example will be presented in Section 7.

As we have shown in this section, EBTs feature all the desired properties of a well-suited configuration space representation for the topology of PARTS. The abstraction method establishes a one-to-one mapping between a topological configuration and the associated EBT. EBTs also enable a facile computation of the robot’s surface, which is fundamental in self-reconfiguration, as the formation of new connections and module transport occur exclusively on the surface of PARTS.

5. Reconfiguration planning

In this section, we derive a reconfiguration planning algorithm for PARTS based on the novel representation method of EBT. In this reconfiguration approach, we assume that the environment is free of any obstacles. Furthermore, we only consider configurations without holes, as the enclosing of a hole during the reconfiguration process in 2D would require the connection of two kinematic chains, which is practically not realized (see Section 3). Note, however, that EBTs are capable of describing configurations with holes, although the surface computation becomes due to the disjunct surface sections more cumbersome. We presume that the formation of a kinematic loop with three ATCs or more is always possible. We will present a method to realize the closing operation in Section 5.3.

Our reconfiguration approach is based on the movement of single ATCs along the surface and the successive construction of the binary tree of the target configuration starting from the root. As shown in Section 3.2, ATCs can be moved by a series of opening and closing operations. The formation of new kinematic loops requires free edges for connection. This implies that ATCs can only move along the surface of the robotic system. Thus, we first analyze the module motion along the surface of PARTS. Subsequently, we present a reconfiguration planning algorithm based on the surface motion of ATCs and demonstrate how reconfiguration steps can be translated to module motion commands.

5.1. Surface motion of ATCs

The surface constitutes the primary location for reconfiguration. We define the term simply-connected ATC describing an adaptive triangular module that has only one connection to the rest of the system and thus two free edges and maximum mobility. The vertex connected with the two free edges is referred to as free node, as it can be positioned freely within the working space defined by the fixed edge and the kinematics of the module (see e.g. [13] for the kinematic description of one ATC as planar RPRPR manipulator). We will show that a simply-connected ATC can be moved to any position on the surface, either directly or by using bypass strategies (BPS).

In contrast to a simply-connected ATC, a two-connected ATC has only one free edge and two connections to other modules. As all vertices of a two-connected ATC are also shared with other ATCs, it is in general not possible to change its shape without affecting adjacent modules. If the two-connected ATC is part of a closed kinematic loop, a shape change inevitably deforms adjacent ATCs. However, is the two-connected ATC not part of a closed kinematic loop, e.g., as part in an isolated kinematic chain, changing the edge length of the free edge does not affect the shape of adjacent ATCs, only the positioning of downstream modules. A regular surface is a set of free edges from two-connected ATCs that forms a continuous surface or surface section. A regular surface does not contain the edges of any simply-connected ATC. For example, the surface section of the configuration in Fig. 10(a) given by the ATCs ⑤, ⑦, ⑥, ② is a regular surface, while the surface on the right side of the configuration in Fig. 7(b) is not, as it contains two simply-connected ATCs.

A simply-connected ATC can be moved along a regular surface by sequential closing and opening operations, as simplified illustrated in Fig. 4, since every vertex point on the regular surface is shared by at least two ATCs, thus fulfilling with the simply-connected ATC the closing condition of three ATCs around a common vertex at any position on the surface. If ATCs are constrained in their motion capability by neighboring ATCs, which cannot alter their geometry to a sufficient extent to allow the formation of a new kinematic loop, closing can be facilitated by the selective termination of connections. Such terminated connections can be re-established after opening when the surface geometry is restored. Fig. 12 depicts an example of selective disconnection to increase the motion capability of ATC  and establish a kinematic loop along the surface.

We refer to the sequence of one closing and one opening procedure as one reconfiguration step. Fig. 13 illustrates a regular surface, where it is apparent that each vertex on the regular surface belongs to at least two ATCs. Next, we will look at surfaces that are not regular surfaces, i.e., surfaces with additional simply-connected ATCs, either isolated or at the end of kinematic chains.

1. Download : Download high-res image (80KB)

2. Download : Download full-size image

Fig. 12. Example of selective disconnection: In order to establish a new kinematic loop and move ATC  along the surface (a), the connection between ATC  and  can be terminated to enable closing (b). Once the surface geometry is restored, the connection can be re-established.

Different locomotion approaches are needed for non-regular surfaces, as a simply-connected ATC cannot traverse over other simply-connected ATC on the surface. We call the simply- connected ATC that is to be moved the moving ATC. In the presence of other simply-connected ATCs on the surface, a moving ATC cannot advance unrestricted along the surface, as the closing condition cannot be fulfilled at a vertex solely associated with another simply-connected ATC. Thus, we propose rule-based bypass strategies (BPS) that enable the moving ATC to traverse other simply-connected ATCs. These bypass strategies are classified using the local surface geometry as well as the initial and goal location of the moving ATC. The surface geometry is either a single simply-connected ATC or an isolated kinematic chain, consisting of one or more ATCs with a simply-connected ATC at the end. As shown in Fig. 14, an isolated kinematic chain is either facing towards the moving ATC (a) or away from it (b), depending on if the kinematic loop a chain can form with itself is facing the moving ATC or not.

1. Download : Download high-res image (49KB)

2. Download : Download full-size image

Fig. 13. Movement of a simply-connected ATC  along a regular surface.

We consider the most general case of a chain facing towards the moving ATC. Bypass strategies for a chain facing in the opposing direction can be deduced by performing the individual steps in reverse order. A single simply-connected ATC can be treated as a chain of length one. We will see how the traversing becomes somewhat simpler, as several redundant steps can be omitted. Fig. 15 shows the result of the two basic bypass strategies to traverse a kinematic chain, which we term BPS1 and BPS2. It should be noted that BPS1 brings the moving ATC  right at the end of the chain but requires one surface position ahead of the chain. BPS2, however, brings the moving ATC  from an initial position being connected with the chain (either with  or ) to the next surface position past the chain. Hence, BPS1 and BPS2 are complementary regarding the additional space requirements on the surface and can thus be applied interchangeably if certain surface positions are not available during the reconfiguration.

1. Download : Download high-res image (103KB)

2. Download : Download full-size image

Fig. 14. A moving ATC  cannot traverse an isolated kinematic chain. These chains can be classified as facing towards (a) or away (b) from the moving ATC.

The individual reconfiguration steps for BPS1 are depicted in Fig. 16. The basic idea of BPS1 is to connect the end of the chain with the chain itself in order to create a regular surface, such that the moving ATC can advance along the surface and traverse the chain. In Fig. 16(a), ATCs  and  form a new kinematic loop. This loop allows the moving ATC  to move one step along the surface connecting with ATC  (b). Subsequently, the previously formed connection between ATC  and ATC  is terminated again (c), and the initial surface geometry is restored (d). This sequence results in the moving ATC  traversing the kinematic chain.

1. Download : Download high-res image (169KB)

2. Download : Download full-size image

Fig. 15. Bypass strategies BPS1 (a) and BPS2 (b) with initial and final position of moving ATC .

The same strategy can be applied to traverse a single simply-connected ATC, as illustrated in Fig. 17. The simply-connected ATC  can form a kinematic loop with the adjacent surface ATC towards the moving ATC , as depicted in Fig. 17(a). By closing the kinematic loop, the surface becomes regular, and the moving ATC  can move past the stationary ATC  (b). The previously formed loop is then opened again (c), such that the moving ATC  is now on the other side of ATC .

1. Download : Download high-res image (168KB)

2. Download : Download full-size image

Fig. 16. Bypass strategies BPS1: the moving ATC  can traverse a kinematic chain with ATCs  by first connecting ATC  at the end of the chain with ATC , which is also a part of the chain (a). The moving ATC  can then traverse the newly formed regular surface (b). Subsequently, the connection between ATC  and  can be terminated (c) to open the kinematic loop and restore the surface geometry (d).

1. Download : Download high-res image (135KB)

2. Download : Download full-size image

Fig. 17. Bypass strategy BPS1: Is the surface path of a moving ATC  blocked by an isolated simply-connected ATC , ATC  can form a kinematic loop with the surface (a), which enables the moving ATC  to traverse the simply-connected ATC  (b). The loop can then be opened again (c), such that the moving ATC  is now on the other side of ATC  (d).

The individual reconfiguration steps for BPS2 are illustrated in Fig. 18. The principle of this bypass strategy is to bring the moving ATC to the end of the chain and remove one ATC from the chain, which is becoming the new moving ATC. In Fig. 18(a), the moving ATC  is connected with the simply-connected ATC  at the end of the chain in order to form a kinematic loop. Subsequently, the kinematic loop is opened between the two-connected ATCs closest to the base of the chain and opposing ATC , i.e., ATC  and ATC  (b). ATC , which is now a simply-connected ATC, can advance one step along the surface (c). Next, the kinematic loop is closed again by connecting  and  (d) and subsequently opened between the moving ATC  and ATC  (e) such that the topology of the kinematic chain can be restored. In the last step, we interchange the roles of the moving ATC , which is at the end of the chain, and ATC , such that the moving ATC  is now at the other side of the chain (f).

1. Download : Download high-res image (251KB)

2. Download : Download full-size image

Fig. 18. Bypass strategy BPS2: A moving ATC  can traverse an isolated kinematic chain facing towards the moving ATC by first closing a kinematic loop between the end of the chain  and the moving ATC  (a). The newly formed loop is then opened at the last two-connected ATC  in the loop on the opposing side of the moving ATC (b) such that ATC  can be moved one step forward (c). The kinematic loop is then closed again between  and  (d) and opened again at the moving ATC  (e). In the last step, the roles of the moving ATC  and the ATC  are swapped (f).

When BPS2 is applied to a single simply-connected ATC, several reconfiguration steps are redundant since the kinematic loop is opened at the same place where it was previously formed. We hence propose the bypass strategy BPS3, in which all redundant steps of BPS1 are omitted, resulting in only two remaining forward moves along the surface. As illustrated in Fig. 19, the path of the moving ATC  is blocked by the simply-connected ATC , as depicted in (a). If ATC  advances one step along the surface (b), the moving ATC  can also advance one step and take the former position of the ATC  (c). In the last step, ATC  is assigned as the new moving ATC (d).

The proposed bypass strategies can be arbitrarily combined to move a simply-connected ATC along more complex non-regular surfaces like surfaces with multiple kinematic chains and additional simply-connected ATCs. The appropriate bypass strategy is chosen with respect to the local surface geometry and reachable surface positions for movement.

1. Download : Download high-res image (133KB)

2. Download : Download full-size image

Fig. 19. Bypass strategy BPS3: Is the surface path of a moving ATC  blocked by an isolated simply-connected ATC  (a), ATC  can advance one step along the surface (b), and the freed position on the surface can be taken by the moving ATC  (c). ATC  is assigned as the new moving ATC by interchanging the roles in the movement process (d), which enables the surface motion to be continued.

Special care must be taken when the goal position is a surface position near the edge of the root ATC that is constrained by the boundary condition. The root ATC is connected to the surrounding and can thus not establish any connections to other ATCs with the boundary edge. For simply-connected ATCs and kinematic chains facing towards the moving ATC, all positions can be reached using BPS1. Reaching the distant side of a kinematic chain facing away from the moving ATC needs a more complicated approach, termed BPS4, as depicted in Fig. 20. The basic idea is to transfer the kinematic chain to the moving ATC  in such a way that the moving ATC can take the position next to the base of the chain with the remaining chain already in the correct position. In Fig. 20, the moving ATC  is moved at the position ahead of the first two-connected ATC of the chain (ATC ) and forms a connection with this ATC (a). In the next step, the connection of ATC  with the base of the chain, ATC , is terminated, and ATC  at the end of the chain forms a kinematic loop with the moving ATC  (b). The same kinematic loop is then opened between ATC  and ATC  (c), such that the moving ATC  can form a new kinematic loop with ATC  at the base of the initial chain (d). This loop is opened between the moving ATC  and its initial connected ATC (e), and the geometry of the chain is restored (f). In the last step, the roles of ATC  and ATC  are interchanged, such that ATC  is at the end of the chain (g). Note that the initial surface position of ATC  is not used in this bypass strategy, such that BPS4 is also applicable if the free edge of ATC  is constrained due to the boundary condition. For longer chains, BPS4 can be extended. However, the detailed reconfiguration steps are omitted, as the basic idea for the traverse is the same as for the presented example.

1. Download : Download high-res image (226KB)

2. Download : Download full-size image

Fig. 20. Bypass strategy BPS4: A moving ATC  can traverse a chain facing away from it by first forming a connection with the two-connected ATC  closest to the base of the chain (a), then terminating the connection between ATC  and the base of the chain ATC , and connecting ATC  at the end of the chain with the moving ATC  (b). The kinematic loop is opened between ATC  and ATC  (c), such that the moving ATC  can form a new kinematic loop with ATC  (d). This loop is opened by terminating the connection between the moving ATC  and its initial connected ATC (e). After restoring the geometry of the chain (f), the roles of ATC  and ATC  are interchanged, such that ATC  is at the end of the chain (g).

In order to validate the sufficiency of the proposed BPS to allow surface motion under all circumstances, we will construct possible surface configurations using a bottom-up approach and resolve each case using one of the introduced bypass strategies. Considering the minimal surface geometry in Fig. 21 with a moving ATC  already positioned on one side of a simply-connected surface ATC , we will demonstrate how to move the ATC  to the other edge of ATC  to occupy the goal position . The parent ATC  of the simply-connected ATC  might either be connected with one other ATC ( or ) or two ATCs ( and ). We resolve either the generalized case with a particular BPS, i.e. an edge can be connected to another ATC or be free, or further analyze the surrounding by a distinction of cases, that is, the edge is connected to another ATC (case 1) or the edge is free (case 2). The successive contemplation of the local topology is continued until each case terminates. Table 1 shows the results of this analysis.

1. Download : Download high-res image (35KB)

2. Download : Download full-size image

Fig. 21. Minimal surface geometry.

If the closing condition is fulfilled independent of the next element on the surface (either unconnected edge or further ATCs), the movement of a simply-connected ATC is considered feasible to the next surface position. The analysis is stopped after cases 2.2.1 and 3.2.1, respectively since a further distinction of cases 2.2.2 and 3.2.2 (both not shown) can be treated in a similar manner. These cases correspond to additional elements in the kinematic chain, either facing away (case 2) or towards (case 3) the moving ATC . The series terminate since one chain can only contain a limited number of ATCs, that is, the maximum number of ATCs permitted in a closed kinematic loop. Cases with an unavailable surface position immediately after the goal position (e.g. the edge is constrained by a boundary condition) can be handled with the alternative strategy using BPS1 (cases 3.1, 3.2.1, etc.) or with BPS4 and its extensions (cases 2.1, 2.2.1, etc.).

Since multiple bypass strategies are leading to similar results (e.g., BPS1 and BPS3, or BPS2 and BPS1), a BPS is automatically selected using the current surface position of the moving ATC and the desired goal position along the surface, such that the total number of reconfiguration steps (opening and closing operations) is minimized. For example, if the goal position of a moving ATCs is on the distant side of a simply-connected ATC at the end of a chain facing towards the moving ATC, BPS1 is selected, whereas if the goal position is beyond the chain, BPS2 is chosen (see Fig. 15 for illustration of those cases).

Table 1. Systematic construction of local topologies.

1

and  connected, move ATC  one step back, use BPS 3 and move new moving ATC  (old ATC ) one step back to reach .

2

not enough information to solve, include further surrounding and analyze distinct cases

2.1

move ATC  two steps back, then apply BPS2 in reverse;

alternatively: apply BPS1 in reverse and move ATC  two steps back

2.2

not enough information to solve, include further surrounding and analyze distinct cases

2.2.1

move ATC  three steps back, then apply BPS2 in reverse;

alternatively: apply BPS1 in reverse and move ATC  two steps back;

the motif from 2.2 to 2.2.1 can be generalized for further ATCs attached to the other edge of ATC  (2.2.2 to 2.2.2.1 and so on)

3

not enough information to solve, include further surrounding and analyze distinct cases

3.1

apply BPS2, then move ATC  (old ATC ) two step back;

alternatively: move ATC  two steps back and apply BPS1

3.2

not enough information to solve, include further surrounding and analyze distinct cases

3.2.1

apply BPS2, then move ATC  (old ATC ) three step back;

alternatively: move ATC  two steps back and apply BPS1;

the motif from 3.2 to 3.2.1 can be generalized for further ATCs attached to the other edge of ATC  (3.2.2 to 3.2.2.1 and so on)

Thick edges may or may not be connected to further ATCs, thin edges are always free edges.

5.2. Reconfiguration planning

We propose a novel reconfiguration planning approach for adaptive modular robots with a triangular structure based on the movement of individual ATCs along the surface of the system. A simply-connected ATC can be moved to any position on the surface of a PARTS system, as was demonstrated in the last Section 5.1. The approach incorporates the representation of the configuration space using EBT introduced in Section 4.

Reconfiguration is the problem of finding a sequence of valid configurations  that transforms the system from an initial configuration  to a desired goal configuration . The EBT representations  and  enable a unique mathematical description of the initial configuration  and goal configuration , respectively.

1. Download : Download high-res image (302KB)

2. Download : Download full-size image

The complete reconfiguration planning algorithm is shown in Algorithm 3. In the first step, we calculate the configuration distance  between the initial and goal configuration and perform a similarity transformation on either  if(25)or on  otherwise, such that  BT-indices in  and  are equal after the transformation. The common BT-indices , referred to as the largest common subtree, correspond to ATCs that already occupy the correct places in the connection topology.

The hierarchical structure of the EBT then allows realizing topological reconfiguration by populating the BT-indices of the goal configuration in ascending order through the movement of simply-connected ATCs along the surface. The next BT-index to be placed for the current reconfiguration step  described by the EBT  is, hence, given by smallest BT-index in the goal configuration that is not occupied. This index is either part of the surface  or is of the interconnection indices , i.e., (26)

If , then we can always disconnect ATCs, such that . This is accomplished by terminating the interconnections described by  between the ATCs with BT-indices  and , and all additional interconnections between the two subtrees associated with these ATCs in order to guarantee a connected surface and avoid the formation of holes within the configuration. Connectivity is intrinsically preserved by removing only interconnection indices because every ATC still has a corresponding BT index, i.e., a connection to a parent ATC and, hence, the remaining robot structure.

The set of simply-connect ATCs  for a given EBT is determined by the set of BT-indices that do not have any children among the other BT-indices or interconnection indices, i.e., (27)which is equal to the set of BT-indices with both children being elements of the surface , given by(28)Furthermore, we only want to consider simply-connected ATCs as candidates to be moved along the surface that are not already part of the goal configuration, and we choose the one with the largest BT-index as moving ATC described by  to populate , i.e., (29)If no such simply-connected ATC exists, i.e., , we can create new simply-connected ATCs by terminating a connection of a two-connected ATC that is not an element of the goal configuration to make it simply-connected. For this purpose, we choose the two-connected ATC with the largest BT-index, given by  with the set of two-connected ATCs given by(30)

The next BT-index  can always be populated by moving a simply-connected ATC along the surface because

1. Download : Download high-res image (369KB)

2. Download : Download full-size image

Fig. 22. Flowchart of the reconfiguration planning algorithm.

- •

the root of the tree is considered invariant due to the kinematic boundary condition. Thus, the BT-index  is guaranteed to be an element of both binary trees, i.e., .

- •

the parent ATC of the BT-index  is necessarily in place. Since the BT-index of the parent ATC  is smaller, it must already be occupied due to the rule for ascending population of indices.

- •

the BT-index  that is to be populated in the current reconfiguration step is either element of the surface  or element of the interconnection indices . If , we can always disconnect ATCs to attain .

- •

as described in Section 5.1, the movement of simply- connected ATCs along the surface is always possible and all surface positions can be reached.

- •

if no simply-connected ATCs are available for reconfiguration, a simply-connected ATC can always be created by the termination of one connection of a two-connected ATC that is not in .  □

When a moving ATC reaches the target position given by , we check if BT-indices for interconnections associated with  are already placed in the current configuration , i.e., for , we check for all  with  corresponding to  in , if . When applicable, we connect the corresponding ATCs and add the interconnection to .

When all BT-indices of the goal configuration  given by  are populated, the reconfiguration is completed. The entire reconfiguration planning is shown in Fig. 22 as a flowchart. Reconfiguration planning, thus, builds the binary tree of the target configuration from the root by moving individual simply-connected ATCs along the surface of the modular robot system. Every reconfiguration step moves a simply-connected ATC one step along the surface closer to the target position, and every populated BT-index reduces the distance to  by 1. Hence, the distance  is monotonically decreasing towards 0 with every reconfiguration step. The algorithm is guaranteed to complete within  number of steps since there are at most  (for  modules excluding the root) BT-indices to be placed, which each requires at most  surface moves (for  modules excluding the moving module) for a simply-connected ATC to reach the target location, for a total of at most  surface moves.  □

Note that the reconfiguration approach focuses on topological reconfiguration. Specific geometric configurations emerge as a by-product of intermediate topological configurations. The execution of individual reconfiguration steps will be presented in the following section. It is merely necessary to morph the geometric configuration of the final topology into the geometry of the desired goal configuration by continuous deformation of the triangular mesh.

5.3. Execution of reconfiguration steps

In this subsection, we demonstrate how the reconfiguration steps can be translated into specific motion commands. We will focus on the closing operation, which is essential to transport ATCs along the surface by the formation of new kinematic loops. It is challenging to establish a new connection between two ATCs by closing a kinematic loop. Since ATCs can alter their shape continuously, the immediate environment of individual ATCs varies significantly. Hence, this environment can, a priory, not be reduced to a distinct number of discrete configurations to consider like it is the case for modular robots with a lattice architecture.

As depicted in Fig. 23, connecting two ATCs ⓐ and ⓑ along the connecting edges  and  by forming a new kinematic loop around the common vertex  is equivalent to equating the positions of the free vertices  and .

1. Download : Download high-res image (75KB)

2. Download : Download full-size image

Fig. 23. The connection of two ATCs ⓐ and ⓑ along the connecting edges  and  by forming a kinematic loop around the common node  is equivalent to equating the position of the two free nodes  and .

We consider the morphological configuration of PARTS as a triangular mesh described by the set of vertices , also called nodes, and the set of edges }. The position of node  is given by the nodal coordinate vector .

Connecting the two ATCs can then be achieved by equating the nodal coordinates of the free vertices  and , which is equal to bringing the distance between the nodes to zero, i.e., . At the same time, all edges  must comply with the minimum and maximum edge lengths  and , i.e., (31)We solve this connection problem using a multi-step constrained optimization approach. The idea is as follows: We minimize the distance between the two free nodes  and , which we want to connect, with respect to variable nodal positions, and, additionally, require the edge lengths associated with the variable nodes to comply with the minimum and maximum edge lengths. Initially, we only allow the positions of nodes  and  to vary. We increase the number of variable nodes for each successive optimization step in an advancing front manner until the distance between the nodes  and  vanishes and the nodal coordinates are equal.

Let  be the set of variable nodes consisting of  nodes and  with ,  the -tuple of all variable nodes. The stacked vector of variable nodal coordinates  corresponding to the positions of the variable nodes is then given by(32)The optimization is started with  variable nodes chosen as the two free nodes  and  which shall be connected. The objective function  for the optimization procedure is provided by the distance between the nodes  and . To facilitate computation, we choose the quadratic distance given by(33)as objective function. Furthermore, we need to guarantee that all edge lengths stay within the maximum and minimum bounds. We only have to consider edges  with at least one variable node . The optimization problem, thus, is given by(34)

Additionally, we want to avoid solutions of the optimization that might be mathematically correct but infeasible, as these would correspond to free nodes lying on the wrong side of their associated base edge, as depicted in Fig. 24(a). To permit only feasible solutions like illustrated in (b), we constrain the two free connecting nodes to lie in the correct half-space of their corresponding base edges. This is accomplished by introducing additional inequality constraints. Considering Fig. 25, we can determine the half-space of the free node  with respect to the base edge between the nodes  and  by calculating the scalar product of the vectors  and , which is the vector perpendicular to , given by(35)

1. Download : Download high-res image (145KB)

2. Download : Download full-size image

Fig. 24. Possible solutions  after optimization for free nodes  and : (a) infeasible solution and (b) desired feasible solution.

The half-space of node  with respect to the edge  is then given by the sign of the scalar product, i.e., (36)which is either ＋1 or −1. The free node  must thus lie in the same half-space before and after the optimization. This condition can be formulated as an additional inequality constraint with the initial half-space  of node  given by(37)

The optimization problem in (34), extended with the half-space constraint in (37), serves as the basis for the automated alteration of the local geometry to achieve closing. However, the proposed approach does not check if the resulting geometric configuration is collision-free, i.e., that some ATCs included in the optimization process may partially overlap with neighboring or distant ATCs. Particularly collisions between topologically distant ATCs pose problems since such cases cannot be considered a priori in the optimization in contrast to immediate neighbor ATCs. Hence, collision avoidance is not considered in the scope of this paper but is deferred to future work. The posed optimization problem can be solved using one of the many well-known methods for constrained optimization. We chose a trust region method based on interior point techniques based on [77], [78]. The solution to the optimization problem is, in general, non-unique, i.e., there is a multitude of geometric configurations that fulfill the optimization criteria. However, this non-uniqueness of the solution is not problematic since the exact geometric configuration of a particular topological configuration is, in most cases, irrelevant for topological reconfiguration. In addition, the closing procedure is merely an intermediate step in the surface motion of ATCs, as the intermediate geometric configuration is restored to the previous surface geometry in the subsequent opening procedure.

1. Download : Download high-res image (36KB)

2. Download : Download full-size image

Fig. 25. Definition of vectors , , and  for the determination of the half-space of the free node  with respect to the edge .

In each consecutive optimization step, we systematically extend the set of variable nodes . Let  be the set of all nodes that are connected to variable nodes, i.e., (38)The variable nodes  for optimization step  are recursively defined by the union of the variable nodes  and connected nodes  of the previous optimization step , i.e., (39)

This process is continued until , which corresponds to the nodal positions of  and  being equal. The extension of variable nodes with each reconfiguration step is schematically depicted in Fig. 26, where in order to connect two ATCs (a), the variable nodes are augmented in an advancing front manner (b)–(d).

To facilitate the minimization of , the nodal coordinates  of the last step that yielded a minimal function value for  can be substituted as initial conditions for the next optimization step. This choice of initial values guarantees that the function value of  is monotonically decreasing towards zero. Variable nodes not included in the previous optimization step are initialized with the original nodal coordinates.

1. Download : Download high-res image (274KB)

2. Download : Download full-size image

Fig. 26. Optimization process for closing a loop (a) by successively adding nodes: free nodes (nodes 1 and 2) are set variable; the edges are constrained to minimum/maximum edge lengths (b). If no solution is found, connected nodes (nodes 3–5) are also included (c); the process is continued by adding successive nodes (nodes 6-9) until a solution is found and a connection is possible (d).

To further ease the closing process, we implemented selective disconnection of ATCs. For a kinematic loop that is to be formed with more than one ATC connected to the remaining robot, we can terminate all connections except for one. The removed connections increase the range of motion of the ATCs, which in turn facilitates the closing operation, while the connectivity of the modular robot is still guaranteed by the remaining connection. When the moving ATC is advanced one step along the surface, the previous surface geometry can be restored, and all due to selective disconnection terminated connections can be reconnected.

6. Reconfiguration example

We will consider two reconfiguration examples, one with 12 ATCs and one with 62 ATCs. The initial and goal configurations were created manually and serve as a small example to visualize the reconfiguration procedure (12ATCs) and a large, more complex example to evaluate the performance of the algorithm (62ATCs), respectively. The validation of the proposed algorithm on a multitude of automatically generated test configurations similar to [15] is desirable, but due to the unstructured nature of the configuration space and geometrical limitations of the robotic modules regarding edge lengths yet not realized. An automated configuration generator would, in principle, create a configuration with a specified number of ATCs utilizing a bottom-up approach by successively connecting new triangles with varying geometry to free edges of an existing configuration until the specified number is reached. Occasionally, kinematic loops must be closed, and the geometry adapted to comply with the geometric limitations. The implementation of such a configuration generator is, however, beyond the scope of the present paper. The reconfiguration examples can be viewed in full length in the supplementary videos (S4 and S5, respectively).

1. Download : Download high-res image (203KB)

2. Download : Download full-size image

Fig. 27. Configuration and binary tree with BT-indices of initial (a) and goal configuration (b).

1. Download : Download high-res image (802KB)

2. Download : Download full-size image

Fig. 28. Self-reconfiguration of a PARTS system from an initial configuration (a) to a goal configuration (n) via intermediate configurations (b) – (m). The highlighted elements in the tree correspond to the common subtree of the current configuration and goal configuration. All numbers refer to ATC identifiers for associated modules.

6.1. Reconfiguration example using 12 ATCs

To demonstrate the steps of the proposed reconfiguration algorithm, we consider the configurations in Fig. 27, consisting of 12 ATCs. The initial configuration is depicted in (a), and the goal configuration is depicted in (b). Intermediate configurations and their corresponding EBTs are shown in Fig. 28, where elements that already occupy the correct position in the configuration topology are highlighted in the binary tree.

Starting from the initial configuration (a), the simply-connected ATC 12 is first moved along the surface to the lowest unoccupied BT-index of the goal configuration (b). Next, the kinematic loop with the two-connected ATC with the largest BT-index that is not already part of the goal configuration is opened to form two simply-connected ATCs, ATC 5 and ATC 6 (c). The bypass strategy BPS2 is applied to traverse the original moving ATC 6 through the chain consisting of ATCs 10 and 11 (d). ATC 10 is, after applying BPS2, the new simply-connected ATC that is to be moved. Note that as the parent of the corresponding interconnection index (ATC 7) is already in place, ATC 10 is moved to the surface position ahead of the goal position, such that it is connected to ATC 7 (e). In the next step, the kinematic loop can be closed with ATC 12, thus simultaneously populating the BT-index and forming the interconnection of the corresponding interconnection index (f). The simply-connected ATC 5 is then traversed through the chain consisting of ATC 11 and ATC 6 by the execution of BPS2 (g). The new moving ATC 11 can then advance one surface position to populate the next BT-index (h). To create new simply-connected ATCs for movement, the connection between ATC 3 and ATC 4, which is the two-connected ATC with the largest BT-index, is opened (i). After applying BPS2 for another time on ATC 4 to traverse the chain consisting of ATC 6 and ATC 5 (j), the new moving ATC 6 is already at the correct goal position, and the corresponding interconnection can by formed by docking with ATC 5 (k). The last simply-connected ATC 3 is moved one step along the surface (l), then, in order to traverse the other simply-connected ATC 4, BPS3 is performed (m). Finally, as the new moving ATC 4 is already at the desired position, the remaining interconnection can be formed by closing ATC 4 and ATC 11 to finish the reconfiguration (n). The reconfiguration takes a total of 20 reconfiguration steps of opening/closing to complete.

6.2. Reconfiguration example using 62 ATCs

The second reconfiguration example consists of 62 ATCs and is depicted in Fig. 29. The initial configuration has a rectangular shape (a) and reconfigures into a configuration in the shape of a ‘T’ (d). Two intermediate configurations are given after 190 reconfiguration steps (b) and 380 reconfiguration steps (c). The whole reconfiguration takes 639 steps to complete, which is way below the upper bound of  reconfiguration steps. Particularly interesting is the number of optimization steps in the translation of the reconfiguration steps to module movements. Out of the 639 closing operation, 15 completed without optimization, as the nodes were already equal, 242 closing operation succeeded after the first optimization step and 382 after the second optimization step. No closing operation required more than two optimization steps.

1. Download : Download high-res image (229KB)

2. Download : Download full-size image

Fig. 29. Reconfiguration example with 62 ATCs from an initial lying rectangular configuration (a) to a ‘T’ configuration (d). Intermediate configurations are depicted after 190 reconfiguration steps (b) and 380 reconfiguration steps (c).

Fig. 30 shows the configuration distance between the goal EBT and the EBT at reconfiguration step . The configuration distance decreases from an initial value of 52 steadily towards 0. The flat steps correspond to ATC movement along the surface, where the configuration distance stays constant until the moving ATC reaches its goal position, then it drops by one. The occasional upward spikes correspond to the temporary increase in configuration distance due to the application of a BPS. However, after the BPS is completed, the configuration distance returns to the previous value. As shown in Section 5.1, the moving ATC is guaranteed to reach any goal position on the surface, enabling the successive element-wise construction of the goal configuration. Due to the deterministic nature of this rule-based reconfiguration approach, the configuration distance invariably decreases steadily towards 0.

1. Download : Download high-res image (124KB)

2. Download : Download full-size image

Fig. 30. Configuration distance for the reconfiguration of the rectangular configuration to the ‘T’ configuration with 62 ATCs plotted over the number of reconfiguration steps.

7. Discussion

The proposed reconfiguration algorithm is deterministic by design. Hence, it is also applicable for a large number of modules, as it does not suffer from limitations like search space explosion, a common problem in many search-based approaches [41], [42]. Completing in  reconfiguration steps, the performance of the algorithm is comparable to other reconfiguration algorithms that reach the same limiting behavior for two-dimensional modular robots like [79] for square modules or [80] for hexagonal modules. These approaches also achieve reconfiguration by the movement of single modules along the surface. A reduction to  reconfiguration steps was accomplished for pivoting square modules by implementing a parallelization of module movements [15]. Further improvement of reconfiguration efficiency was only attained by implementation of a highly parallelized volumetric flow of modules (e.g.  in [48]). A parallelization of module motion can also be incorporated in the proposed reconfiguration framework, as the module motion is realized by a variation of the local environment of the moving module, which can be performed on multiple different locations on the surface as long as the variable nodes are not associated to more than one optimization procedures. The motion of individual modules can be initialized sequentially in compliance with dependencies between modules, e.g., movement of one module can start only if the previous module already passed (see supplementary video S1).

EBTs rely on the faithful representation of the binary tree indices using large integer values. Most built-in integer types can thus not represent EBT with more than 63 levels using, for example, uint64 or unsigned long long data types, corresponding to a maximum shortest distance between any ATC and the constrained ATC to be below 64 modules. This limitation can be surmounted by employing big-integer libraries, which hold in some programming environments no upper bound and therefore set virtually no limit on the maximum system size. Note that for computation of the surface order using binary logarithms, the precision must also be enhanced using multiple-precision floating-point libraries, such that tiny differences in the results can be faithfully represented and thus guarantee the correct arrangement of the surface elements.

One main drawback of the reconfiguration approach is that collision avoidance is not addressed yet. Collision control of a moving ATC with the adjacent surface sections can be incorporated in the optimization procedure for closing by appending additional inequality constraints. However, even if the solution of the optimization procedure contains no collisions, a validation for the transitional movement between morphological configurations is still necessary. Problematic are particularly highly concave surface geometries, as ATCs that are topologically distant from a moving ATC might nevertheless block the surface path. For example, considering the surface geometry in Fig. 31, a kinematic chain is almost in contact with the surface. When the gray ATC is moved along the surface to the dashed goal position, a collision with the end of the chain (hatched ATC) will occur, although the ATCs are several positions along the surface apart (see supplementary video S3). A possible strategy for collision avoidance using the adaptability of PARTS is to move the tip of the chain away from the surface to generate space (see supplementary video S2). Detection of such cases and the explicit motion control of the involved ATCs is yet to be realized.

Also, it is not guaranteed that the optimization procedure to form new kinematic loops ((34), (37)) inevitably terminates. Although the inclusion of a steadily increasing local environment results in more adaptable variables in the optimization, which leads to, at least, a potential decrease in the nodal distance, there is no absolute certainty that this is the case for all possible geometries. It can, hence, not be ruled out that certain types of local geometries have no solutions for the presented optimization algorithm. Nonetheless, our experiments suggest that the optimization swiftly converges with an increasing number of variable nodes as the procedure terminated within at most two optimization steps. Further investigations are necessary to either confirm the termination of the algorithm or rebut it with counterexamples. If the termination cannot be guaranteed, strategies for cases where the optimization procedure fails to give a solution are required, like additional removal of connections to increase the motion capability of elements.

1. Download : Download high-res image (96KB)

2. Download : Download full-size image

Fig. 31. When moving the gray ATC over the surface to the dashed goal position, a collision occurs with the hatched ATC. The surface path is depicted as thick black line.

EBTs as configuration representations also have a downside, as they might fail to reveal the largest common subtree using the proposed similarity transformations and configuration distance. For example, considering the configurations in Fig. 32(a) with their EBT representations, the output of the similarity transformation is given in (b) as the subtree of BT-indices in both configurations. However, the actual largest common subconfiguration is depicted in (c), such that topological reconfiguration can be achieved by moving only a single ATC. The incapability of the similarity transformation to find the largest subtree disqualifies the configuration distance as a proper metric in the mathematical sense, as the triangle inequality is not fulfilled. In order to find the largest subtree, all members of the equivalence classes of the two configurations would have to be compared, and the EBTs with the largest intersection in BT-indices would constitute the largest subtree. This procedure, however, increases in computational cost for an increasing number of interconnections in the EBT exponentially and is thus only feasible for a small number of modules.

1. Download : Download high-res image (307KB)

2. Download : Download full-size image

Fig. 32. The EBT of two different configurations with each 12 ATCs (a) have a distance of 3 when using the proposed distance metric and 9 ATCs already in place (b). However, the largest common subtree given by the topology consists of 11 ATCs (c).

8. Conclusion

The novel configuration representation based on extended binary trees and the proposed reconfiguration algorithm establishes a principal framework for the reconfiguration of planar adaptive robots with a triangular structure. The algorithm accomplishes the self-reconfiguration of PARTS configurations represented by unstructured triangular meshes. Thus, the presented algorithm is the first reconfiguration approach to solve the self-reconfiguration problem for these modular robots. However, the algorithm still has several shortcomings. The centralized structure introduces a single point of failure, collisions between modules are neither detected nor avoided, and the feasibility of a particular reconfiguration step has not been proved, which all limit the practical application of the proposed method. Yet, the proposed reconfiguration framework offers numerous possibilities for extension, e.g., the local alteration of the triangular mesh allows for parallelization of module motion, or the optimization problem can be extended with additional constraints to prevent collisions. Therefore, the framework can serve as a foundation and benchmark for the development of more efficient reconfiguration approaches for this class of modular robotic systems. Future research focuses on an extension of the reconfiguration approach with collision detection and avoidance strategies and the adaption of methods to the more restricted motion capabilities of existing modules, allowing the employment of the reconfiguration algorithm on the hardware realization of PARTS.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Self-reconfiguration of shape-shifting modular robots with triangular structure

Author links open overlay panel

Michael Gerbl, Johannes Gerstmayr

Show more

Add to Mendeley

Share

Cite

https://doi.org/10.1016/j.robot.2021.103930Get rights and content

Under a Creative Commons license

open access

Highlights

- •

Self-reconfiguration of adaptive modular robots with a triangular structure.

- •

Extended binary trees (EBT) as representation of topological configuration space.

- •

Reconfiguration by module movement along the surface of the robot system.

- •

Reconfiguration by construction of EBT by populating EBT-indices in ascending order.

Abstract

In this paper, we present a reconfiguration algorithm for shape-shifting modular robots with a triangular structure. The algorithm is derived from a novel description of the configuration space based on extended binary trees. Extended binary trees representing the same configuration are grouped into equivalence classes, which allows for a one-to-one correspondence between a configuration and its mathematical representation. Reconfiguration is then accomplished by a successive construction of the goal configuration, realized by moving individual modules along the surface of the robot and building up the binary tree of the goal configuration by populating unoccupied binary tree indices in ascending order with new modules. The algorithm is capable of solving the self-reconfiguration problem for modular robots with a triangular structure in  reconfiguration steps and is demonstrated on two reconfiguration examples. We then discuss the limits of the proposed methods, regarding constraints on the implementation and the lack of efficient collision avoidance, and outline possible resolutions.

- Previous article in issue

- Next article in issue

Keywords

Extended binary trees

Self-reconfiguration

Modular robots

Triangular modules

List of abbreviations

ATC

Adaptive Triangular Cell

BPS

Bypass Strategy

BT

Binary Tree

EBT

Extended Binary Tree

PARTS

Planar Adaptive Robot with Triangular Structure

SRP

Self-Reconfiguration Problem

- Notation

Set of binary tree indices

Extended binary tree object

Configuration

Set of interconnection indices

Set of left children

Set of right children

Set of surface indices of binary tree

Set of surface indices of extended binary tree

1. Introduction

The term programmable matter, first coined in the early 1990s, describes materials that can alter their physical characteristics like shape, conductivity, or optical properties according to external user specifications or autonomous sensing. Since its emergence, the research field of programmable matter has developed into an interdisciplinary field with efforts ranging from meta-materials [1], [2] over synthetic biology [3], [4] to quantum wells [5]. Robotics based approaches utilizing modular robots with self-reconfiguration capability present a promising candidate to realize the shapeshifting aspect of programmable matter [6], [7], [8], [9]. Such robot systems are typically built from a multitude of homogeneous robotic cells or modules, which can be arranged in a space-filling manner. Self-reconfiguration enables the modules to autonomously change their connection topology and the overall shape of the robotic system. The problem of transforming a modular robot autonomously from an initial to a desired configuration through motion primitives on a module level is referred to as the Self-Reconfiguration Problem (SRP). SRP is considered an extraordinarily challenging problem, as finding an optimal solution to this planning problem is proved to be NP-complete for chain-type modular robots [10], [11] and lattice-type modular robots with pivoting cube modules [12]. Further, there is a vast diversity in system design regarding degrees of freedom, motion capabilities, and kinematic constraints of modules. Thus, existing solutions to the SRP are hardware or application-specific and cannot easily be transferred from one modular robot class to another.

The Planar Adaptive Robot with Triangular Structure (PARTS), currently under development at the University of Innsbruck, is a two-dimensional modular robotic system built up from triangular modules. These robotic cells are arrangeable in a space-filling manner and can, therefore, reproduce arbitrary planar triangular meshes within the module’s geometric limitations. Taking into account the kinematic constraints of PARTS, the SRP has been solved for certain kinds of structured triangular meshes [13]. However, a solution for unstructured triangular meshes and thus arbitrary configurations of the PARTS system has as yet not been formulated.

The problem is further complicated by fundamental differences in the structure of the configuration space of PARTS compared to modular robots with a lattice architecture, such that present solution and planning frameworks are not easy to adopt.

In this paper, we introduce a novel abstraction method for the configuration space representation of modular robots with a triangular structure, like the PARTS system, based on extended binary trees and present a rule-based reconfiguration planning algorithm. The paper is organized as follows: In Section 2, we review and discuss related work to the subject of self- reconfiguration for modular robotic systems. Section 3 continues with a brief depiction of adaptive robots with triangular structures and the PARTS system as a representative of these types of robots. In Section 4, we introduce and motivate extended binary trees (EBT) as a novel abstraction method that can be used to represent the configuration space of modular robots with a triangular structure. Section 5 describes a reconfiguration planning algorithm based on the extended binary tree representation. We demonstrate the proposed reconfiguration algorithm on two examples in Section 6. Finally, we present several open problems in Section 7 and conclude in Section 8.

2. Related work

Robotic candidates for programmable matter are systems capable of forming space-filling structures, i.e., they can be arranged in a surface covering (two-dimensional) or volume covering (three-dimensional) manner. Modular robots with this ability consist almost exclusively of modules or submodules with a regular geometric shape, such as square [14], [15], [16], [17], circular [6], [18], [19], or hexagonal [20], [21] modules in 2D or cubic [15], [22], [23], [24], [25], octahedral [26], rhombic dodecahedral [27], or spherical [9], [28], [29], [30] modules in 3D, respectively. The uniform geometry allows for organizing the robotic units in a regular lattice, similar to the atoms in a crystal, such that each module occupies a well-defined lattice position.

Some robots with a regular cell geometry permit arbitrary connection points, which enable the construction of non-lattice configurations [29], [30]. However, the connector design limits these systems in their aptitude to construct durable self-reconfigurable space-filling structures, as connectors support only a limited number of connection cycles [29] or modules feature only one connector [30], thus limiting possible configurations to a chain or tree architecture.

One advantage of the lattice architecture is the description of module positions by unique integer-valued coordinates with respect to a predefined reference frame. This description is possible for all two- or three-dimensional lattices as they can be assigned to one of 5 grid types in 2D or 14 grid types in 3D, respectively. These so-called Bravais lattices are well-known in solid-state physics (see e.g. [31]). A configuration of the modular robot is thus uniquely characterized by the entity of occupied places in the lattice and can be represented by the set of lattice coordinates corresponding to the location of modules [18], [32], [33], [34], [35], [36]. The lattice architecture also proves beneficial for addressing the SRP beyond providing an abstraction method for the configuration space. The lattice offers distinct neighborhood relations between modules, which are frequently incorporated in local control schemes [16], [37], [38], [39], and a simple distance metric that allows calculating distances between module positions [25], [26], [40], which can be included in the reconfiguration strategy, e.g., as a simple heuristic to guide informed search methods [36].

Solutions to the SRP can generally be grouped into search-based, control-based, or agent-based approaches [41], [42]. Search-based approaches treat the SRP as a search problem, i.e., they try to find a sequence of module moves that reconfigures the robot from a given initial configuration to a desired goal configuration. The search space is typically represented as a configuration graph, where each node represents a configuration and each edge a transition between configurations via a set of feasible module actions. The solution to the SRP is a path from the initial configuration to the goal configuration. The configuration graph, however, suffers from exponential growth of the branching factor with increasing module numbers. The complexity of the search space hence quickly becomes intractable, such that uninformed, brute force search approaches are impractical for a large number of modules. They may, however, be applied for the motion planning of individual modules [15].

Informed search techniques, on the other hand, rely on heuristics that measure the quality of a configuration and thereby guide the search efficiently through the search space towards the goal configuration. Various types of metrics have been proposed for quality assessment like overlap, minimal number of moves, optimal assignment [40], or graph edit-distance [43]. Many authors incorporate the measures of distances in the lattice into their search heuristic [36], [44]. These search strategies are often combined with additional simplification methods to make the search tractable, like the usage of meta-modules to increase motion capabilities [22], [26], [44], [45], scaffolding [33], [46], or intermediate configurations with a specific structure like chains or lines [15], [47].

However, since search-based approaches rely on global information, movement commands for modules are dictated by a centralized controller. For large systems with a myriad of modules, this constitutes a single point of failure, thus making a distributed local control architecture more desirable. Hence it is not surprising that recent research has shifted away from global search to this decentralized paradigm. Control-based approaches do not rely on global information but incorporate local information through inter-module communication, such that the individual modules move independently to reconfigure into the goal configuration. Independent module movement implicates a reconfiguration speed-up by parallelization through a simultaneous module motion at the cost of additional caretaking for collision avoidance [48], [49], preserving connectivity [25], [48], and guaranteeing the convergence to the goal configuration [42]. Proposed control strategies are but not limited to predefined local rules [16], [50], [51] to incorporate human experience and knowledge, coordinate or gradient attractors to guide module movement along the surface [27], [52], [53], or recruitment of free modules by other modules adjacent to empty goal positions [54].

Local rules are frequently employed in the form of cellular or finite automata. Each module possesses a limited computational power and memory and decides upon moving by sole consideration of the information of neighboring modules [39], [55]. Similar to search-based approaches, control-based methods also utilize simplification techniques like meta modules [16], [25], [48] or scaffolding [48], [49] to increase the motion capabilities of modules or intermediate structures [56] to ease reconfiguration. One drawback of many distributed algorithms is that global knowledge of the goal configuration or its representation is assumed to be known by all modules, raising the need for efficient shape description techniques [57]. Alternatively, it is sufficient that the goal configuration is known by at least one module, the so-called leader, which can be externally designated or chosen by the modules themselves [37].

In agent-based or task-based approaches, the focus of reconfiguration is set on the functionality of the goal configuration rather than on the convergence of the system to a particular configuration topology. A specific configuration hence emerges as a byproduct during the completion of the task. The reconfiguration is tailored to the task that is to be completed and always includes interaction with the environment, for example, locomotion over unstructured or uneven surfaces through cluster flow [58], [59], [60] or task-driven growth to enclose objects or support structures [61]. However, we are focused on a faithful reconfiguration that converges to a specific goal topology and will not consider agent-based approaches any further.

A comprehensive survey of different self-reconfiguration methods is given in [42] or [57], with the latter focusing in particular on self-reconfiguration methods for programmable matter. Although there exists extensive research for cube-style or spherical modular robots, little work has been done to investigate the SRP for modular robots with triangular structure. Adaptive robots with a triangular structure, like the PARTS system, however, have their peculiarities, which differ significantly from modular robots with lattice architecture and complicate the adaptation and application of existing planning frameworks and reconfiguration methods to solve the SRP.

3. Adaptive robots with triangular structure

Adaptive robots with a triangular structure consist of planar modules with a triangular geometry. One module can connect to up to three other modules along its edges. The modules have no fixed but an adaptive geometry, i.e., they can change their shape by varying their edge lengths via linear actuation. This variable geometry allows multiple modules to be arranged in a surface covering manner. Hence, they can reproduce arbitrary planar triangular meshes within the geometric limitations of the modules.

Although two-dimensional modular robots have little practical application [41], they have proven useful for testing the feasibility of mechanical design aspects and algorithms, which may eventually be adapted to corresponding three-dimensional systems, successfully demonstrated, e.g., with the FireAnt [19] and FireAnt3D modular robot [29], with the Crystalline [47] and Telecube systems [22], [62], or 2D Catoms [63] and 3D Catoms [9]. The study of adaptive robots with triangular structure, hence, gives valuable insight for the development of adaptive robots with a tetrahedral structure, such as the ARTS modular robot system [64]. One realization of an adaptive robot with a triangular structure is the PARTS system, which we will describe in more detail.

3.1. Hardware design

The Planar Adaptive Robot with Triangular Structure (PARTS) is an adaptive modular robot with a triangular cell geometry, currently in development at the University of Innsbruck. PARTS is built up from multiple Adaptive Triangular Cells (ATCs), which feature a symmetric triangular design consisting of three linear actuators that correspond to the edges of the triangle and are linked together by three revolute joints, corresponding to the vertices. An ATC has 3 degrees of freedom and can vary its shape by continuously changing the edge lengths via linear actuation. The current ATC design admits an effective elongation of the idealized triangular edges of 43.4 percent, which corresponds to a minimum attainable interior angle of 44.2 and a maximum interior angle of 91.6. Each edge is equipped with a hermaphroditic male–female connector pair that allows for orientation-independent docking, such that two ATC can establish a connection along an edge.

For further information on the mechatronic design of PARTS, see [65]. In the following text, we will use the acronyms PARTS and ATC interchangeable to describe the entire class of modular robots with a triangular structure and the individual modules of such a robot, respectively.

The triangular module design distinguishes the PARTS system from all modular robot systems with a lattice architecture as (i) PARTS can build up space-filling triangular meshes, which are not bound to a lattice structure, and (ii) these space-filling meshes are due to the module design adaptive, i.e., they can change their morphological shape without modifying the underlying connection topology. Fig. 1 shows two PARTS systems, each consisting of 6 ATCs, that feature the same configuration topology but form two different morphological shapes (a) and (b).

Not being bound to a lattice architecture comes with its pros and cons. Triangular meshes are more flexible regarding module placement, orientation, and movement, which is not restricted by the lattice such that the robot can better adapt to the environment. The adaptivity further allows for fulfilling particular tasks without a topological change in the configuration, like grasping an object or locomotion. Fig. 2 shows PARTS in a gripper-like configuration (a) grasping a circular object by changing the shape of ATCs without topological reconfiguration such that the object is grasped by enclosing. Fig. 3 depicts an example locomotion pattern, similar to the peristaltic motion of some invertebrates like worms. The motion consists of propagating compression waves that travel from the rear end to the front combined with a simultaneous lift of contact points from the ground. Performed periodically (b–e), the result of this locomotion pattern is a continuous forward motion.

1. Download : Download high-res image (383KB)

2. Download : Download full-size image

Fig. 1. PARTS system, consisting of 6 connected ATCs with the same connection topology but different morphological shapes (a) and (b).

1. Download : Download high-res image (114KB)

2. Download : Download full-size image

Fig. 2. Grasping of a circular object by enclosing: An object (a) can be grasped by PARTS without topological reconfiguration by changing the shape of ATCs such that the object is enclosed (b).

1. Download : Download high-res image (265KB)

2. Download : Download full-size image

Fig. 3. Locomotion of PARTS without topological reconfiguration applying a peristaltic-like motion primitive: From the initial configuration (a), motion is initialized at the rear end (b) using a compression wave with a simultaneous leg raise traveling through the length of the body to the front end (b–e). This compression wave can be reinitiated at the rear end to enable continuous forward motion.

3.2. Self-reconfiguration concepts

In general, we can distinguish three broad concepts to realize a self-reconfiguration of PARTS, based on the number of modules involved during one reconfiguration step. These are (i) reconfiguration by single module movement, (ii) reconfiguration by meta-module movement, and (iii) global cluster reconfiguration. We will elaborate on the first reconfiguration concept of single module movement and outline the approaches (ii) and (iii).

A single ATC has only limited motion capabilities. One module can continuously alter the length of each edge between 1 and 1.434 times the minimum edge length. If the ATC is connected along an edge to another ATCs, an alteration of this edge’s length is only possible by simultaneously changing the length of the corresponding edge of the connected ATC in the same manner. In addition to this shape deformation, a single ATC can disconnect from an adjacent module with an existing connection or connect to an adjacent module if the connecting edges have the same length and are properly aligned. The sequence of connecting and disconnecting enables the single ATC to change its position in the connection topology. In general, however, it is not possible for a single ATC to properly align the edges to establish a new connection. Hence, to move a single ATC to a new topological position requires coordinated motion of multiple ATC in the vicinity. The basic method of motion for a single ATC consists of the action sequence move, connect, disconnect, and move. We term the ATC that is supposed to move the moving ATC, the ATC, to which the moving ATC will dock and form a new connection the connecting ATC, the free edges, which are initially unconnected and subsequently used for the new connection between moving ATC and connecting ATC the connecting edges and the ATC(s), to which the moving ATC is initially connected the connected ATC(s).

In the first step, the moving ATC and connecting ATC have to align their connecting edges. The alignment is accomplished by deformation of the moving and connecting ATC as well as of adjacent ATCs. Once the connecting edges are properly aligned, the moving ATC and connecting ATC can dock and establish a connection. Subsequently, the moving ATC undocks from the connected ATC(s) and hence terminates all initial connections. In the last step, all ATCs involved in the movement process restore their original shape by resetting their edge lengths to the previous values. This action sequence changes the moving ATC’s position from initially being connected to the connected ATC(s) to being connected to the connecting ATC, while the remaining topology is unaffected.

We only consider potential new connections between two ATCs that initially have a vertex in common, such that the ATCs can connect by forming a kinematic loop around this common vertex, as depicted in Fig. 4. Although module locomotion by connecting two chains of ATCs is, in theory, possible, the alignment accuracy of the connectors is practically limited by actuator imperfections and imprecision in module motion, which lead to an accumulation of errors in the kinematic chains [65]. Hence, exact positioning and alignment within the tolerances of the connectors cannot be guaranteed without feedback from additional sensors like infrared [66] or hall sensors [67] for guidance during the connection process.

The connection process of two ATCs by forming a kinematic loop around a common vertex is shown exemplarily in Fig. 4 with four modules. The hardware realization of PARTS admits forming kinematic loops consisting of at least four modules. In the present work, however, we assume that three modules sharing a common vertex are sufficient to establish a kinematic loop. We will refer to the precondition of at least three ATCs around a vertex to form a new loop as closing condition. In order to fulfill the closing condition, three ATCs must be able to complete the full angle around their common vertex. Thus, modules must be capable of changing their geometry in such a way as to form interior angles of at least 120. This requirement corresponds to an effective edge elongation factor of , resulting in a minimal interior angle of 30.

1. Download : Download high-res image (70KB)

2. Download : Download full-size image

Fig. 4. Movement of moving ATC ① from connected ATC ② (a) to connecting ATC ④ (c) by forming a kinematic loop ①-②-③-④ (b) around the common vertex.

The closing condition with at least three ATCs required to form a kinematic loop significantly increases the number of potential new kinematic loops compared to a minimum requirement of four ATC in a loop allowing for specific reconfiguration strategies not deployable otherwise. Although this relaxed closing condition makes the proposed reconfiguration approach not suitable to be employed on the current hardware system, an improvement of the hardware design to reach the required maximum interior angles or an extension of the reconfiguration algorithm to the stricter closing condition with a maximum interior angle of at least 90 or edge elongation factor  can be expected in the near future. Thus, the locomotion process can be summarized in the two sequential steps of closing and opening a kinematic loop.

- (1)

Closing: Modify actuator lengths to form a kinematic loop and connect moving ATC and connecting ATC along the free connecting edges Fig. 4(a)  (b), connect moving ATC ① and connecting ATC ④

- (2)

Opening: Terminate previous connection(s) of moving ATC with connected ATC(s) and restore original actuator lengths Fig. 4(b)  (c), disconnect moving ATC ① and connected ATC ②

This method of module locomotion is similar to the frequently used rolling of modules around neighboring cells on the surface [20], [21], [24]. However, one ATC cannot perform the movement by itself but needs adjacent ATCs in the new kinematic loop to alter their shape as well. In general, also the mesh in the vicinity of those modules needs to adapt, which complicates the connection process.

Some of these problems can be surmounted by moving so-called meta-modules, composed of more than one ATC, instead of single modules. Meta-modules have greater mobility than single modules enabling them to move by themselves without assistance from other modules. The meta-module size and shape can either be fixed or variable. A fixed size and shape generally limit the granularity of configurations and, in the case of PARTS, dictate a regular mesh structure, e.g., for quadratic meta-modules, consisting of 4 ATCs, a quadratic lattice as depicted in Fig. 5. The prescribed lattice restricts the placement of modules, which also inhibits the adaptability of the robot system. Variable meta-modules regarding the number of modules and meta-module topology, on the other hand, emerge from the environment created by other modules and move as an ensemble to a new position, thus setting no constraints on the module mesh. However, the choice of meta-module size and shape is not trivial, as a reconfiguration of the system must be guaranteed in all possible circumstances.

1. Download : Download high-res image (85KB)

2. Download : Download full-size image

Fig. 5. Self-reconfiguration using meta-modules, consisting of 4 ATCs arranged in a square; The resulting mesh is also a regular square mesh. The gray meta-module on the top right (a) is moved by connection with an adjacent meta-module (b) to the next lattice position (c).

The last reconfiguration concept is based on the movement of large clusters of modules, such that reconfiguration is achieved by a small number of global reconfiguration steps. The initial and goal configurations are searched for similar sub-configurations that can be moved as a whole from the initial position to the goal position. This reconfiguration approach is the fastest and most efficient regarding execution, but computationally the most demanding in planning. Another drawback presents the potential loss of structural integrity caused by overstress and subsequent failure of intermodular connections [68], [69] or the inability of actuators to deliver sufficient force for movement of large structures. Fig. 6 depicts an example of this reconfiguration approach, where an initial tower configuration is reconfigured in one step to a square. The configurations in Fig. 6(b) and (c) require further examination of the forces acting on the connectors and actuators around the narrow hinge to guarantee the structural integrity of the robot system during reconfiguration.

In this work, we focus on the reconfiguration of PARTS, represented as a triangular mesh, by the movement of single ATCs. Since arbitrary triangular meshes are, in general, unstructured, a description of the configuration using lattice coordinates is not feasible. Thus, a different abstraction method for the configuration space of PARTS is required. This method should uniquely describe a distinct configuration and also allow for a determination of relative positions between modules and similarities between configurations.

1. Download : Download high-res image (155KB)

2. Download : Download full-size image

Fig. 6. Self-reconfiguration by moving a large cluster of modules.

4. Configuration space

The PARTS system can be represented by a planar triangular mesh. In order to guarantee the kinematic determination of PARTS, we suppose in our model that one module is constrained by fixing one free edge of that module to the environment. This assumption might be realized by a real physical connection of that module to the surrounding, or it might be a temporarily assigned module, which is in constant contact with the surrounding and not changing its location during the current reconfiguration process. Based on this model, we introduce in this section a novel representation method for the topological configuration space of PARTS based on extended binary trees.

First, we distinguish geometric and topological configurations and then state the desired properties of the configuration space representation. Subsequently, we review existing abstraction methods of the configuration space for other modular robots and discuss their shortcomings when applied on PARTS. We then introduce extended binary trees as a novel representation method of the configuration space and group binary trees that correspond to the same configuration to equivalence classes. In the last part of this section, we propose a distance measure on extended binary trees that enables us to compare the similarity of two configurations.

4.1. Geometric and topological configuration

We want to distinguish between the geometric configuration of PARTS, given by the morphological shape of the robot system, and the topological configuration, given by the connection topology of the individual ATCs. Due to the continuous mode of actuation, two distinct geometric configurations that exhibit the same topological configuration (i.e. an identical connection topology between modules) can be morphed into each other without changing the underlying connection topology (see e.g. Fig. 1). The SRP, hence, reduces to transforming the topology of the initial configuration to the topology of the goal configuration. Distinct geometric configurations emerge as a by-product from intermediate topological configurations during the reconfiguration process. The final geometric configuration can then be morphed into the goal geometry by continuous module deformation.

The geometric configuration of PARTS contains the topological information of individual connections between modules and the exact shape of all modules. Individual edge lengths must comply with connectivity (i.e. connected edges have equal length) and loop closure constraints. One way to represent the geometric configuration is by a planar triangular mesh. There have been various methods proposed to represent triangular meshes for use in finite element methods and computer graphics. The connectivity of a triangular mesh is represented by the vertices(1)the edges(2)and the triangular elements(3)Vertices and edges can be combined to form the graph . To describe the geometry of the configuration, it is sufficient to specify the position of all vertices  in , which is equivalent to a planar embedding of the graph  in . Alternatively, the triangular mesh geometry can also be constructed by specifying the length of all edges , starting from the constrained module which is connected to the surrounding.

Although topological information is indirectly encoded in the mesh structure, this structure is impractical for reconfiguration, as topological changes alter the number of edges and vertices, creating an overhead of additional bookkeeping and obscuring the underlying topological changes. This deficit raises the need for a better suited topological representation for reconfiguration purposes. In the remaining part of this section, we will focus on the configuration space of topological configurations and their representation. If not stated otherwise, we refer to a topological configuration henceforth simply as configuration.

4.2. Properties of configuration space representation

A PARTS configuration  consists of  ATCs  arranged in a triangular mesh, in which modules intersect either at one edge or not at all. Two ATCs  and  are connected if they share one edge. In this case, ATC  is called ATC ’s neighbor. We are interested in a mathematical representation of this topological configuration space that should hold the following properties:

- I.

Uniqueness: One representation maps precisely to one distinct configuration.

- II.

Uniformity: All ATCs are homogeneous and isotropic, i.e., they all have the same mechanical design and symmetric structure. Thus, one specific connector is not distinguishable, only the relative locations of one connector to another one. Arbitrarily chosen module identifiers shall not influence the topological representation. Hence, a configuration is only determined by the connection topology and not by specific connections between specific connectors of individual ATCs.

- III.

Similarity measure: The representation allows for measuring the similarity between two configurations and for identifying isomorphic representations.

Ideally, a configuration should also map uniquely to a distinct representation. As a unique mapping might not be feasible, it should at least be facile to distinguish isomorphic representations, i.e., two representations that correspond to the same topological configuration.

To motivate the need for a novel abstraction method to represent the configuration space of PARTS, we will first review existing abstractions methods and evaluate their applicability as a suitable representation for modular robots with a triangular structure.

4.3. Review of existing abstraction methods

As mentioned in Section 2, modular robots with lattice architecture often use lattice coordinates to describe the configuration space in reconfiguration planning [7], [15], [27], [40], [59]. Triangular meshes are, in general, unstructured and lack the regularity required to assign unique coordinates to each module position. Thus, lattice coordinates are not feasible to represent the configuration space of unstructured meshes. Another commonly used group of abstraction techniques is based on graphs and their incidence matrices [47], [70], [71]. These methods, however, lack to express the modular robot configuration uniquely since the information of connection port and orientation is missing [42]. Some authors proposed solutions to this problem by extending the graph to a so-called connector-graph [72] or the incidence matrix to a so-called assembly incidence matrix (AIM) [73], [74] or face–face incidence matrix (FFIM) [75] to differentiate connecting points and connection orientations. Methods of graph theory have been successfully applied to enumerate non-isomorphic configurations and distinguish isomorphic configurations for a distinct number of modules in the AIM representation [73]. However, the analysis of isomorphic configurations requires the calculation of all graph automorphisms to that configuration, hence making it infeasible for a large number of modules. Furthermore, these representation methods lack a similarity measure, thus making it impossible to compare two configurations for their similarity.

A natural way to describe a triangular mesh would be with mesh representation techniques applied in finite element methods using nodes, edges, and elements. These description methods are, however, designated for meshes that do not change their topology. The docking and undocking of ATCs would consistently change the number of edges and nodes, making this approach impractical. We can deduce from the element-node connectivity relations an element topology matrix, as two elements are connected if they share an edge. Labeling the edges of each element with the local edge numbers  in a counter-clockwise manner, the element topology  is a  matrix, such that  is the element identifier  if element  is connected with element  at the local edge  or 0 if no neighbor is present. The element-topology matrix contains all relevant topological information, such that it can uniquely be mapped to a distinct configuration. There is, however, a vast number of isomorphic representations, as a relabeling of ATCs and connection ports does not alter the configuration. This corresponds to

- •

random permutation of the element identifiers, corresponding to a relabeling of ATCs and

- •

cyclic permutation of the local edges for every element, corresponding to an orientation preserving relabeling of the local edges.

Thus, for  elements, there are  different representations of the same topological configuration. With no further information, it is hence cumbersome to evaluate the equality or similarity of configurations.

The reviewed abstraction methods lack one or more of the desired properties for a suitable representation of the configuration space, given that they either fail to capture the module symmetry, distinguish the connection orientation, or enable facile identification of similarity and isometry between configurations. Thus, we propose a novel abstraction method for reconfiguration planning of modular robots with a triangular cell geometry based on extended binary trees (EBT).

4.4. Extended binary trees

As stated at the beginning of this section, we presume in our model of PARTS that one module is constrained and fixed with one edge to the surrounding. A configuration of PARTS can thus be considered a highly parallel robotic manipulator where the constrained module represents the connection to the ground. Such parallel mechanisms with closed kinematic loops can be described by their kinematic spanning tree and loop closure equations. The kinematics of the parallel mechanism is reduced by a notional slicing of all loops to a tree structure. Kinematic loops are then included with additional loop closure constraints in the formalism (see e.g. [76]). We will apply the concept of slicing open kinematic loops and then including means to establish loop closure on PARTS. We accomplish this by (1) ignoring connections that create loops to describe PARTS by its spanning tree and (2) including the previously not considered connections through an extension in the tree structure. We will later see that the resulting structure fulfills all desired properties of Section 4.2 and has beneficial computational properties for self-reconfiguration planning.

The constrained module is the only module distinguishable from all other modules, as it can merely establish a maximum of two connections with further ATCs due to the constrained edge boundary condition. Choosing the constrained ATC as the root of the spanning tree, an arbitrary configuration of the PARTS system can then be represented by a kinematic tree with interconnections. Fig. 7 shows one possible kinematic spanning tree (b) for a specific configuration of PARTS (a). Additional interconnections are indicated by dashed lines. In a first step, however, we will omit these interconnections, such that the configuration is given by an open tree without any kinematic loops. Note that each ATC besides the root ATC is part of a kinematic chain with one connection to a preceding module, referred to as parent ATC, and up to two connections to succeeding modules, referred to as children of the respective ATC. Based on the orientation of a child connection with respect to the parent ATC, we can distinguish between a right child ATC and a left child ATC. Consequently, due to the maximum number of two successors, the resulting tree is also referred to as Binary Tree (BT).

We can describe each element in a BT with a unique number termed binary tree index (BT-index) . The BT-index of an ATC is determined recursively and depends on the connection orientation (left or right) with respect to and the BT-index of the parent ATC. If the parent ATC holds the BT-index , the right child is assigned the BT-index  and the left child the BT-index . The indexing scheme is schematically illustrated in Fig. 8. If the index  is prescribed for the root, the complete binary tree  is uniquely defined for  ATCs by specifying the BT-indices  for each ATC, i.e., (4)

1. Download : Download high-res image (186KB)

2. Download : Download full-size image

Fig. 7. Representation of a PARTS configuration (a) by a kinematic tree with interconnections (b).

Any kinematic tree with a designated root and at most two distinguishable descendants per element can thus be represented by a binary tree. Fig. 9 shows the translation of a specific PARTS configuration (a) to a binary tree (b), with the associated BT-indices to the right of the tree elements, as well as the corresponding set of BT-indices  (c). The figure also depicts the hierarchical structure of the tree, which is organized into different levels. For a given BT-index , the level of the corresponding element in the tree can be determined by . The largest level corresponds to the height of the tree. We also define the surface  of the tree as the set of all right child elements(5)and the set of all left child elements(6)that are not already part of the binary tree  themselves, i.e., (7)

1. Download : Download high-res image (85KB)

2. Download : Download full-size image

Fig. 8. Binary tree indexing scheme of adjacent ATCs to an arbitrary ATC with index .

1. Download : Download high-res image (136KB)

2. Download : Download full-size image

Fig. 9. Translation of a PARTS configuration (a) to a binary tree (b) and the set of binary tree indices  (c). The numbers next to the elements of the tree are the corresponding BT-indices.

As binary trees can only describe open kinematic trees with no interconnections between or within individual kinematic chains, we extend the BT-structure to also account for kinematic loops. We will first focus on the description of interconnections using additional BT-indices from the surface . In the next subsection, we will resolve the ambiguity caused by the arbitrary choice of interconnections within a kinematic loop.

We describe an interconnection between two modules  and  by appending an additional element from the surface  to the BT-indices of the two modules, that form the respective connection. This number, termed interconnection index (IC-index) , is chosen for ATC  with BT-indices  based on the orientation of the connection to ATC  as right child index  or left child index  of ATC  with BT index  and vice versa for ATC . Thus, the interconnection index describes the notional position of the module in the binary tree if the connected ATC  was the parent of .

As an example, we consider the configuration of Fig. 9, which is once again depicted in Fig. 10(a). The BT, with interconnections sketched as dotted lines, is shown in (b). The encircled numbers correspond to arbitrarily chosen ascending ATC identifiers to allow simple identification of associated elements in the configuration and binary tree. The configuration contains two kinematic loops and, thus, has two additional connections in the binary tree. In the example, these interconnections are between the ATCs ④ and ⑥ as well as ⑤ and ⑦. If we, for instance, consider the connection between ATCs ④ and ⑥, ATC ④ would be the left child of ATC ⑥ with BT-index 5, hence having the BT-index 11 if the connection to the parent ATC ③ was removed. In contrast, ATC ⑥ would have as the right child of ATC ④ with BT-index 6 the BT-index 12 if the connection to parent ATC ② was removed. By adding these imagined binary tree positions to the corresponding BT-indices, distinct interconnections can be uniquely described. In Fig. 10(b), the circled numbers are ATC identifiers, the numbers next to the circled identifiers correspond to the BT-indices of the individual elements, and the interconnection indices are given by the small numbers next to the dotted interconnections.

1. Download : Download high-res image (173KB)

2. Download : Download full-size image

Fig. 10. Description of a specific PARTS configuration (a) by an extended binary tree (b). The corresponding array structure for the representation of the extended binary tree is shown in (c).

Since an ATC can, in general, have up to two such additional connections not included in the open tree structure, each BT-index  is expanded by a set of up to two interconnection indices(8)such that(9)

If there are no interconnections to ATC

, then . We combine BT-indices and interconnection indices to form a new object, the extended binary tree (EBT)  of the configuration, given by(10)

The EBT  can be represented as an array of size , where row  contains the BT-index

of ATC  and two numbers encoding . These are set to the elements of  and padded with zeros if . By sorting the rows in order of ascending BT-indices, it is possible to describe the configuration without referring to the particular ATC identifiers, thus treating all ATCs uniformly and fulfilling property II (uniformity) of the desired properties of the configuration representation.

We further define the set of all interconnection indices  as the unification of all , i.e., (11)and the surface  of the EBT as the surface  corresponding to the binary tree  without the interconnections , i.e., (12)The structure of the BT can also be exploited to sort the BT-indices of the surface  in a counter-clockwise direction starting from the root. The order is obtained by sorting the surface ordering terms(13)in an ascending manner. This is always possible since, for an arbitrary BT-index , the right child inherits the surface ordering term from its parent, that is,(14)whereas the left surface ordering term is always larger, since the logarithm is a strictly monotonically increasing function and the indices  and  are in the same level of the BT, hence the integer part of the logarithm is the same. The ordering scheme also holds for successive left children in different levels of the tree, e.g.  and , as(15)using again the monotonic property of the logarithm. ATCs with an earlier (parent-)branch-off to the left are hence always posterior in the surface order.  □

4.5. Equivalence of EBTs

The representation is not yet unique since the interconnections within a kinematic loop can be chosen arbitrarily. Hence, there are different EBTs corresponding to the same PARTS configuration. For example, considering the configuration in Fig. 10(a), instead of choosing the interconnection between ATC ④ and ATC ⑥, we can also select the interconnection between other modules of the same kinematic loop, e.g., between ATC ④ and ATC ③. The corresponding EBT is depicted in Fig. 11(a) and describes precisely the same configuration. To resolve this ambiguity, all EBTs that represent the same configuration can be combined to form an equivalence class of EBTs with the equivalence relation . Two EBT  and  correspond to the same configuration if they belong to the same equivalence class, i.e., .

Individual elements of a specific equivalence class can be transformed into each other employing equivalent transformations. An equivalent transformation  is defined as(16)

1. Download : Download high-res image (142KB)

2. Download : Download full-size image

Fig. 11. Transformation between two different EBTs (a) and (b) of the same equivalence class by changing the position of ATC ④ (gray) in the ETB. Encircled numbers describe module identifiers; large numbers next to the encircled numbers are the associated BT-indices; small numbers correspond to interconnection indices.

This transformation swaps an interconnection of one element with the regular connection to the parent ATC. That is, the interconnection index  and BT-index  for ATC  are interchanged. Subsequently, the corresponding interconnection index is removed from the new parent, the correct interconnection index w.r.t the altered BT index of  is added to the old parent, and all indices of children and further descendants of element  are adjusted accordingly, as shown in Algorithm 1. The algorithm has a computational complexity of  and is limited by the determination of all subtree ATCs (the transformation of all subtree indices can be realized efficiently using vector operations). For example, Fig. 11 shows the transformation between two EBTs (a) and (b) of the same equivalence class, where the regular connection between ATC ④ and ATC ⑥ in (a) is swapped with the interconnection between ATC ④ and ATC ③. The BT-index 11 of ATC ④ is hence interchanged with the interconnection index 6, the old interconnection index 23 belonging to ATC ③ is removed, and the interconnection index 12 describing the new interconnection is added to ATC ⑥ (ATC ⑥ would be the right child to ATC ④ with BT-index 6). The BT-index of the child ATC ⑦ is adapted to the new position in the tree as the left child of BT-index 6, as well as the interconnection index of ATC ⑤, which decodes the interconnection with ATC ⑦.

1. Download : Download high-res image (204KB)

2. Download : Download full-size image

An equivalent transformation can also be performed in a distributed manner utilizing inter-module communication. Suppose each ATC stores its BT index and interconnection indices. After identifying ATC  with interconnection index , ATC  initializes the transformation swapping its BT-index  with interconnection index . In a first step, ATC  communicates with its neighbors by exchanging BT indices and interconnection indices in order to determine old and new parent ATC. The new parent ATC  with(17)is ordered to remove interconnection index  with  from . The old parent ATC  with(18)is instructed to add the interconnection index(19)to . The second term in (19) accounts for the orientation shift of the ATC in the binary tree due to the new parent ATC. The last action of ATC  is to signal its child the new BT index (now ) and a command to switch orientation (from left to right child and vice versa). The child then propagates the index change to its neighbors by transmitting old and new BT index  and . Up on receiving an index change, ATC  performs one of following action:

- •

if   and propagate index change to neighbors

- •

if  for one   and terminate propagation

Thus, the indices of the whole subtree and all corresponding interconnection indices are adapted.

In order to uniquely describe a distinct equivalence class, the EBT with the smallest BT-indices is chosen as the representative of the corresponding equivalence class. The representative EBT can be determined by recursively performing equivalent transformations for all elements with a BT-index  larger than the smallest interconnection index of , i.e., ,  since an equivalent transformation swaps BT-index  and interconnection index  for a specific ATC, and either  or  holds, as  and  are by definition disjunct sets, i.e., .  □

Thus, the representative EBT for one equivalence class gives a unique description of a specific configuration of PARTS, hence fulfilling property I (uniqueness) of the desired properties of the configuration representation. The representation is invariant under permutation of ATC identifiers and connection ports, giving a one to one correspondence between a configuration  and an EBT representation . The transformation to the representative EBT can also be performed in a distributed and parallel manner, letting each module  with an interconnection index  independently initialize an equivalent transformation.

4.6. Similarity of EBTs

To compare two EBT and assess their similarity, we define the similarity transformation(20)as a sequence of specific equivalent transformations and the configuration distance(21)comparable to the overlap metric introduced in [40]. The configuration distance is a measure to quantify the similarity between two configurations, given by their EBTs, and further enables the detection of isomorphic configurations.

Given the set of all interconnection indices  of the EBT , the similarity transformation  maximizes the number of equal BT-indices  in  and the transformed EBT . As shown in Algorithm 2, this maximization is accomplished by recursively performing equivalent transformations on  for all interconnection indices  that are elements of , i.e. . Equivalence transformations are omitted if the BT index associated with an interconnection index to be transformed is already parts of the common binary tree, i.e. all indice  with , as such an equivalent transformation would not increase the number of common BT-indices. Thus, equivalence transformations are performed until(22)where(23)

In order to execute a similarity transformation in a distributed manner, the set of final BT indices  must be known by all ATCs. If the set size exceeds the module memory capacity, the set can be split and broadcasted sequentially. Each element performs the calculation in (22) using only its own BT ind IC-indices for each received subset and initiates an equivalent transformation, if the resulting set is not empty.

1. Download : Download high-res image (116KB)

2. Download : Download full-size image

For two configurations, given by the EBTs  and , each with  ATCs, the configuration distance  is defined as(24)where  denotes the cardinality of a set,  for  is the set of BT-indices corresponding to  and  and  is given by the similarity transformation  and , respectively. The configuration distance corresponds to the number of non-overlapping modules, i.e., modules that are not at the correct position in the configuration topology given by the two EBT.

The configuration distance enables comparing the similarity of two EBT and allows for the identification of isomorphic configurations. Hence, property III (similarity measure) of the desired properties of the configuration representation is fulfilled. Note, however, the configuration distance is not a metric regarding the mathematical definition, as it does not fulfill the triangle inequality. A counter-example will be presented in Section 7.

As we have shown in this section, EBTs feature all the desired properties of a well-suited configuration space representation for the topology of PARTS. The abstraction method establishes a one-to-one mapping between a topological configuration and the associated EBT. EBTs also enable a facile computation of the robot’s surface, which is fundamental in self-reconfiguration, as the formation of new connections and module transport occur exclusively on the surface of PARTS.

5. Reconfiguration planning

In this section, we derive a reconfiguration planning algorithm for PARTS based on the novel representation method of EBT. In this reconfiguration approach, we assume that the environment is free of any obstacles. Furthermore, we only consider configurations without holes, as the enclosing of a hole during the reconfiguration process in 2D would require the connection of two kinematic chains, which is practically not realized (see Section 3). Note, however, that EBTs are capable of describing configurations with holes, although the surface computation becomes due to the disjunct surface sections more cumbersome. We presume that the formation of a kinematic loop with three ATCs or more is always possible. We will present a method to realize the closing operation in Section 5.3.

Our reconfiguration approach is based on the movement of single ATCs along the surface and the successive construction of the binary tree of the target configuration starting from the root. As shown in Section 3.2, ATCs can be moved by a series of opening and closing operations. The formation of new kinematic loops requires free edges for connection. This implies that ATCs can only move along the surface of the robotic system. Thus, we first analyze the module motion along the surface of PARTS. Subsequently, we present a reconfiguration planning algorithm based on the surface motion of ATCs and demonstrate how reconfiguration steps can be translated to module motion commands.

5.1. Surface motion of ATCs

The surface constitutes the primary location for reconfiguration. We define the term simply-connected ATC describing an adaptive triangular module that has only one connection to the rest of the system and thus two free edges and maximum mobility. The vertex connected with the two free edges is referred to as free node, as it can be positioned freely within the working space defined by the fixed edge and the kinematics of the module (see e.g. [13] for the kinematic description of one ATC as planar RPRPR manipulator). We will show that a simply-connected ATC can be moved to any position on the surface, either directly or by using bypass strategies (BPS).

In contrast to a simply-connected ATC, a two-connected ATC has only one free edge and two connections to other modules. As all vertices of a two-connected ATC are also shared with other ATCs, it is in general not possible to change its shape without affecting adjacent modules. If the two-connected ATC is part of a closed kinematic loop, a shape change inevitably deforms adjacent ATCs. However, is the two-connected ATC not part of a closed kinematic loop, e.g., as part in an isolated kinematic chain, changing the edge length of the free edge does not affect the shape of adjacent ATCs, only the positioning of downstream modules. A regular surface is a set of free edges from two-connected ATCs that forms a continuous surface or surface section. A regular surface does not contain the edges of any simply-connected ATC. For example, the surface section of the configuration in Fig. 10(a) given by the ATCs ⑤, ⑦, ⑥, ② is a regular surface, while the surface on the right side of the configuration in Fig. 7(b) is not, as it contains two simply-connected ATCs.

A simply-connected ATC can be moved along a regular surface by sequential closing and opening operations, as simplified illustrated in Fig. 4, since every vertex point on the regular surface is shared by at least two ATCs, thus fulfilling with the simply-connected ATC the closing condition of three ATCs around a common vertex at any position on the surface. If ATCs are constrained in their motion capability by neighboring ATCs, which cannot alter their geometry to a sufficient extent to allow the formation of a new kinematic loop, closing can be facilitated by the selective termination of connections. Such terminated connections can be re-established after opening when the surface geometry is restored. Fig. 12 depicts an example of selective disconnection to increase the motion capability of ATC  and establish a kinematic loop along the surface.

We refer to the sequence of one closing and one opening procedure as one reconfiguration step. Fig. 13 illustrates a regular surface, where it is apparent that each vertex on the regular surface belongs to at least two ATCs. Next, we will look at surfaces that are not regular surfaces, i.e., surfaces with additional simply-connected ATCs, either isolated or at the end of kinematic chains.

1. Download : Download high-res image (80KB)

2. Download : Download full-size image

Fig. 12. Example of selective disconnection: In order to establish a new kinematic loop and move ATC  along the surface (a), the connection between ATC  and  can be terminated to enable closing (b). Once the surface geometry is restored, the connection can be re-established.

Different locomotion approaches are needed for non-regular surfaces, as a simply-connected ATC cannot traverse over other simply-connected ATC on the surface. We call the simply- connected ATC that is to be moved the moving ATC. In the presence of other simply-connected ATCs on the surface, a moving ATC cannot advance unrestricted along the surface, as the closing condition cannot be fulfilled at a vertex solely associated with another simply-connected ATC. Thus, we propose rule-based bypass strategies (BPS) that enable the moving ATC to traverse other simply-connected ATCs. These bypass strategies are classified using the local surface geometry as well as the initial and goal location of the moving ATC. The surface geometry is either a single simply-connected ATC or an isolated kinematic chain, consisting of one or more ATCs with a simply-connected ATC at the end. As shown in Fig. 14, an isolated kinematic chain is either facing towards the moving ATC (a) or away from it (b), depending on if the kinematic loop a chain can form with itself is facing the moving ATC or not.

1. Download : Download high-res image (49KB)

2. Download : Download full-size image

Fig. 13. Movement of a simply-connected ATC  along a regular surface.

We consider the most general case of a chain facing towards the moving ATC. Bypass strategies for a chain facing in the opposing direction can be deduced by performing the individual steps in reverse order. A single simply-connected ATC can be treated as a chain of length one. We will see how the traversing becomes somewhat simpler, as several redundant steps can be omitted. Fig. 15 shows the result of the two basic bypass strategies to traverse a kinematic chain, which we term BPS1 and BPS2. It should be noted that BPS1 brings the moving ATC  right at the end of the chain but requires one surface position ahead of the chain. BPS2, however, brings the moving ATC  from an initial position being connected with the chain (either with  or ) to the next surface position past the chain. Hence, BPS1 and BPS2 are complementary regarding the additional space requirements on the surface and can thus be applied interchangeably if certain surface positions are not available during the reconfiguration.

1. Download : Download high-res image (103KB)

2. Download : Download full-size image

Fig. 14. A moving ATC  cannot traverse an isolated kinematic chain. These chains can be classified as facing towards (a) or away (b) from the moving ATC.

The individual reconfiguration steps for BPS1 are depicted in Fig. 16. The basic idea of BPS1 is to connect the end of the chain with the chain itself in order to create a regular surface, such that the moving ATC can advance along the surface and traverse the chain. In Fig. 16(a), ATCs  and  form a new kinematic loop. This loop allows the moving ATC  to move one step along the surface connecting with ATC  (b). Subsequently, the previously formed connection between ATC  and ATC  is terminated again (c), and the initial surface geometry is restored (d). This sequence results in the moving ATC  traversing the kinematic chain.

1. Download : Download high-res image (169KB)

2. Download : Download full-size image

Fig. 15. Bypass strategies BPS1 (a) and BPS2 (b) with initial and final position of moving ATC .

The same strategy can be applied to traverse a single simply-connected ATC, as illustrated in Fig. 17. The simply-connected ATC  can form a kinematic loop with the adjacent surface ATC towards the moving ATC , as depicted in Fig. 17(a). By closing the kinematic loop, the surface becomes regular, and the moving ATC  can move past the stationary ATC  (b). The previously formed loop is then opened again (c), such that the moving ATC  is now on the other side of ATC .

1. Download : Download high-res image (168KB)

2. Download : Download full-size image

Fig. 16. Bypass strategies BPS1: the moving ATC  can traverse a kinematic chain with ATCs  by first connecting ATC  at the end of the chain with ATC , which is also a part of the chain (a). The moving ATC  can then traverse the newly formed regular surface (b). Subsequently, the connection between ATC  and  can be terminated (c) to open the kinematic loop and restore the surface geometry (d).

1. Download : Download high-res image (135KB)

2. Download : Download full-size image

Fig. 17. Bypass strategy BPS1: Is the surface path of a moving ATC  blocked by an isolated simply-connected ATC , ATC  can form a kinematic loop with the surface (a), which enables the moving ATC  to traverse the simply-connected ATC  (b). The loop can then be opened again (c), such that the moving ATC  is now on the other side of ATC  (d).

The individual reconfiguration steps for BPS2 are illustrated in Fig. 18. The principle of this bypass strategy is to bring the moving ATC to the end of the chain and remove one ATC from the chain, which is becoming the new moving ATC. In Fig. 18(a), the moving ATC  is connected with the simply-connected ATC  at the end of the chain in order to form a kinematic loop. Subsequently, the kinematic loop is opened between the two-connected ATCs closest to the base of the chain and opposing ATC , i.e., ATC  and ATC  (b). ATC , which is now a simply-connected ATC, can advance one step along the surface (c). Next, the kinematic loop is closed again by connecting  and  (d) and subsequently opened between the moving ATC  and ATC  (e) such that the topology of the kinematic chain can be restored. In the last step, we interchange the roles of the moving ATC , which is at the end of the chain, and ATC , such that the moving ATC  is now at the other side of the chain (f).

1. Download : Download high-res image (251KB)

2. Download : Download full-size image

Fig. 18. Bypass strategy BPS2: A moving ATC  can traverse an isolated kinematic chain facing towards the moving ATC by first closing a kinematic loop between the end of the chain  and the moving ATC  (a). The newly formed loop is then opened at the last two-connected ATC  in the loop on the opposing side of the moving ATC (b) such that ATC  can be moved one step forward (c). The kinematic loop is then closed again between  and  (d) and opened again at the moving ATC  (e). In the last step, the roles of the moving ATC  and the ATC  are swapped (f).

When BPS2 is applied to a single simply-connected ATC, several reconfiguration steps are redundant since the kinematic loop is opened at the same place where it was previously formed. We hence propose the bypass strategy BPS3, in which all redundant steps of BPS1 are omitted, resulting in only two remaining forward moves along the surface. As illustrated in Fig. 19, the path of the moving ATC  is blocked by the simply-connected ATC , as depicted in (a). If ATC  advances one step along the surface (b), the moving ATC  can also advance one step and take the former position of the ATC  (c). In the last step, ATC  is assigned as the new moving ATC (d).

The proposed bypass strategies can be arbitrarily combined to move a simply-connected ATC along more complex non-regular surfaces like surfaces with multiple kinematic chains and additional simply-connected ATCs. The appropriate bypass strategy is chosen with respect to the local surface geometry and reachable surface positions for movement.

1. Download : Download high-res image (133KB)

2. Download : Download full-size image

Fig. 19. Bypass strategy BPS3: Is the surface path of a moving ATC  blocked by an isolated simply-connected ATC  (a), ATC  can advance one step along the surface (b), and the freed position on the surface can be taken by the moving ATC  (c). ATC  is assigned as the new moving ATC by interchanging the roles in the movement process (d), which enables the surface motion to be continued.

Special care must be taken when the goal position is a surface position near the edge of the root ATC that is constrained by the boundary condition. The root ATC is connected to the surrounding and can thus not establish any connections to other ATCs with the boundary edge. For simply-connected ATCs and kinematic chains facing towards the moving ATC, all positions can be reached using BPS1. Reaching the distant side of a kinematic chain facing away from the moving ATC needs a more complicated approach, termed BPS4, as depicted in Fig. 20. The basic idea is to transfer the kinematic chain to the moving ATC  in such a way that the moving ATC can take the position next to the base of the chain with the remaining chain already in the correct position. In Fig. 20, the moving ATC  is moved at the position ahead of the first two-connected ATC of the chain (ATC ) and forms a connection with this ATC (a). In the next step, the connection of ATC  with the base of the chain, ATC , is terminated, and ATC  at the end of the chain forms a kinematic loop with the moving ATC  (b). The same kinematic loop is then opened between ATC  and ATC  (c), such that the moving ATC  can form a new kinematic loop with ATC  at the base of the initial chain (d). This loop is opened between the moving ATC  and its initial connected ATC (e), and the geometry of the chain is restored (f). In the last step, the roles of ATC  and ATC  are interchanged, such that ATC  is at the end of the chain (g). Note that the initial surface position of ATC  is not used in this bypass strategy, such that BPS4 is also applicable if the free edge of ATC  is constrained due to the boundary condition. For longer chains, BPS4 can be extended. However, the detailed reconfiguration steps are omitted, as the basic idea for the traverse is the same as for the presented example.

1. Download : Download high-res image (226KB)

2. Download : Download full-size image

Fig. 20. Bypass strategy BPS4: A moving ATC  can traverse a chain facing away from it by first forming a connection with the two-connected ATC  closest to the base of the chain (a), then terminating the connection between ATC  and the base of the chain ATC , and connecting ATC  at the end of the chain with the moving ATC  (b). The kinematic loop is opened between ATC  and ATC  (c), such that the moving ATC  can form a new kinematic loop with ATC  (d). This loop is opened by terminating the connection between the moving ATC  and its initial connected ATC (e). After restoring the geometry of the chain (f), the roles of ATC  and ATC  are interchanged, such that ATC  is at the end of the chain (g).

In order to validate the sufficiency of the proposed BPS to allow surface motion under all circumstances, we will construct possible surface configurations using a bottom-up approach and resolve each case using one of the introduced bypass strategies. Considering the minimal surface geometry in Fig. 21 with a moving ATC  already positioned on one side of a simply-connected surface ATC , we will demonstrate how to move the ATC  to the other edge of ATC  to occupy the goal position . The parent ATC  of the simply-connected ATC  might either be connected with one other ATC ( or ) or two ATCs ( and ). We resolve either the generalized case with a particular BPS, i.e. an edge can be connected to another ATC or be free, or further analyze the surrounding by a distinction of cases, that is, the edge is connected to another ATC (case 1) or the edge is free (case 2). The successive contemplation of the local topology is continued until each case terminates. Table 1 shows the results of this analysis.

1. Download : Download high-res image (35KB)

2. Download : Download full-size image

Fig. 21. Minimal surface geometry.

If the closing condition is fulfilled independent of the next element on the surface (either unconnected edge or further ATCs), the movement of a simply-connected ATC is considered feasible to the next surface position. The analysis is stopped after cases 2.2.1 and 3.2.1, respectively since a further distinction of cases 2.2.2 and 3.2.2 (both not shown) can be treated in a similar manner. These cases correspond to additional elements in the kinematic chain, either facing away (case 2) or towards (case 3) the moving ATC . The series terminate since one chain can only contain a limited number of ATCs, that is, the maximum number of ATCs permitted in a closed kinematic loop. Cases with an unavailable surface position immediately after the goal position (e.g. the edge is constrained by a boundary condition) can be handled with the alternative strategy using BPS1 (cases 3.1, 3.2.1, etc.) or with BPS4 and its extensions (cases 2.1, 2.2.1, etc.).

Since multiple bypass strategies are leading to similar results (e.g., BPS1 and BPS3, or BPS2 and BPS1), a BPS is automatically selected using the current surface position of the moving ATC and the desired goal position along the surface, such that the total number of reconfiguration steps (opening and closing operations) is minimized. For example, if the goal position of a moving ATCs is on the distant side of a simply-connected ATC at the end of a chain facing towards the moving ATC, BPS1 is selected, whereas if the goal position is beyond the chain, BPS2 is chosen (see Fig. 15 for illustration of those cases).

Table 1. Systematic construction of local topologies.

1

and  connected, move ATC  one step back, use BPS 3 and move new moving ATC  (old ATC ) one step back to reach .

2

not enough information to solve, include further surrounding and analyze distinct cases

2.1

move ATC  two steps back, then apply BPS2 in reverse;

alternatively: apply BPS1 in reverse and move ATC  two steps back

2.2

not enough information to solve, include further surrounding and analyze distinct cases

2.2.1

move ATC  three steps back, then apply BPS2 in reverse;

alternatively: apply BPS1 in reverse and move ATC  two steps back;

the motif from 2.2 to 2.2.1 can be generalized for further ATCs attached to the other edge of ATC  (2.2.2 to 2.2.2.1 and so on)

3

not enough information to solve, include further surrounding and analyze distinct cases

3.1

apply BPS2, then move ATC  (old ATC ) two step back;

alternatively: move ATC  two steps back and apply BPS1

3.2

not enough information to solve, include further surrounding and analyze distinct cases

3.2.1

apply BPS2, then move ATC  (old ATC ) three step back;

alternatively: move ATC  two steps back and apply BPS1;

the motif from 3.2 to 3.2.1 can be generalized for further ATCs attached to the other edge of ATC  (3.2.2 to 3.2.2.1 and so on)

Thick edges may or may not be connected to further ATCs, thin edges are always free edges.

5.2. Reconfiguration planning

We propose a novel reconfiguration planning approach for adaptive modular robots with a triangular structure based on the movement of individual ATCs along the surface of the system. A simply-connected ATC can be moved to any position on the surface of a PARTS system, as was demonstrated in the last Section 5.1. The approach incorporates the representation of the configuration space using EBT introduced in Section 4.

Reconfiguration is the problem of finding a sequence of valid configurations  that transforms the system from an initial configuration  to a desired goal configuration . The EBT representations  and  enable a unique mathematical description of the initial configuration  and goal configuration , respectively.

1. Download : Download high-res image (302KB)

2. Download : Download full-size image

The complete reconfiguration planning algorithm is shown in Algorithm 3. In the first step, we calculate the configuration distance  between the initial and goal configuration and perform a similarity transformation on either  if(25)or on  otherwise, such that  BT-indices in  and  are equal after the transformation. The common BT-indices , referred to as the largest common subtree, correspond to ATCs that already occupy the correct places in the connection topology.

The hierarchical structure of the EBT then allows realizing topological reconfiguration by populating the BT-indices of the goal configuration in ascending order through the movement of simply-connected ATCs along the surface. The next BT-index to be placed for the current reconfiguration step  described by the EBT  is, hence, given by smallest BT-index in the goal configuration that is not occupied. This index is either part of the surface  or is of the interconnection indices , i.e., (26)

If , then we can always disconnect ATCs, such that . This is accomplished by terminating the interconnections described by  between the ATCs with BT-indices  and , and all additional interconnections between the two subtrees associated with these ATCs in order to guarantee a connected surface and avoid the formation of holes within the configuration. Connectivity is intrinsically preserved by removing only interconnection indices because every ATC still has a corresponding BT index, i.e., a connection to a parent ATC and, hence, the remaining robot structure.

The set of simply-connect ATCs  for a given EBT is determined by the set of BT-indices that do not have any children among the other BT-indices or interconnection indices, i.e., (27)which is equal to the set of BT-indices with both children being elements of the surface , given by(28)Furthermore, we only want to consider simply-connected ATCs as candidates to be moved along the surface that are not already part of the goal configuration, and we choose the one with the largest BT-index as moving ATC described by  to populate , i.e., (29)If no such simply-connected ATC exists, i.e., , we can create new simply-connected ATCs by terminating a connection of a two-connected ATC that is not an element of the goal configuration to make it simply-connected. For this purpose, we choose the two-connected ATC with the largest BT-index, given by  with the set of two-connected ATCs given by(30)

The next BT-index  can always be populated by moving a simply-connected ATC along the surface because

1. Download : Download high-res image (369KB)

2. Download : Download full-size image

Fig. 22. Flowchart of the reconfiguration planning algorithm.

- •

the root of the tree is considered invariant due to the kinematic boundary condition. Thus, the BT-index  is guaranteed to be an element of both binary trees, i.e., .

- •

the parent ATC of the BT-index  is necessarily in place. Since the BT-index of the parent ATC  is smaller, it must already be occupied due to the rule for ascending population of indices.

- •

the BT-index  that is to be populated in the current reconfiguration step is either element of the surface  or element of the interconnection indices . If , we can always disconnect ATCs to attain .

- •

as described in Section 5.1, the movement of simply- connected ATCs along the surface is always possible and all surface positions can be reached.

- •

if no simply-connected ATCs are available for reconfiguration, a simply-connected ATC can always be created by the termination of one connection of a two-connected ATC that is not in .  □

When a moving ATC reaches the target position given by , we check if BT-indices for interconnections associated with  are already placed in the current configuration , i.e., for , we check for all  with  corresponding to  in , if . When applicable, we connect the corresponding ATCs and add the interconnection to .

When all BT-indices of the goal configuration  given by  are populated, the reconfiguration is completed. The entire reconfiguration planning is shown in Fig. 22 as a flowchart. Reconfiguration planning, thus, builds the binary tree of the target configuration from the root by moving individual simply-connected ATCs along the surface of the modular robot system. Every reconfiguration step moves a simply-connected ATC one step along the surface closer to the target position, and every populated BT-index reduces the distance to  by 1. Hence, the distance  is monotonically decreasing towards 0 with every reconfiguration step. The algorithm is guaranteed to complete within  number of steps since there are at most  (for  modules excluding the root) BT-indices to be placed, which each requires at most  surface moves (for  modules excluding the moving module) for a simply-connected ATC to reach the target location, for a total of at most  surface moves.  □

Note that the reconfiguration approach focuses on topological reconfiguration. Specific geometric configurations emerge as a by-product of intermediate topological configurations. The execution of individual reconfiguration steps will be presented in the following section. It is merely necessary to morph the geometric configuration of the final topology into the geometry of the desired goal configuration by continuous deformation of the triangular mesh.

5.3. Execution of reconfiguration steps

In this subsection, we demonstrate how the reconfiguration steps can be translated into specific motion commands. We will focus on the closing operation, which is essential to transport ATCs along the surface by the formation of new kinematic loops. It is challenging to establish a new connection between two ATCs by closing a kinematic loop. Since ATCs can alter their shape continuously, the immediate environment of individual ATCs varies significantly. Hence, this environment can, a priory, not be reduced to a distinct number of discrete configurations to consider like it is the case for modular robots with a lattice architecture.

As depicted in Fig. 23, connecting two ATCs ⓐ and ⓑ along the connecting edges  and  by forming a new kinematic loop around the common vertex  is equivalent to equating the positions of the free vertices  and .

1. Download : Download high-res image (75KB)

2. Download : Download full-size image

Fig. 23. The connection of two ATCs ⓐ and ⓑ along the connecting edges  and  by forming a kinematic loop around the common node  is equivalent to equating the position of the two free nodes  and .

We consider the morphological configuration of PARTS as a triangular mesh described by the set of vertices , also called nodes, and the set of edges }. The position of node  is given by the nodal coordinate vector .

Connecting the two ATCs can then be achieved by equating the nodal coordinates of the free vertices  and , which is equal to bringing the distance between the nodes to zero, i.e., . At the same time, all edges  must comply with the minimum and maximum edge lengths  and , i.e., (31)We solve this connection problem using a multi-step constrained optimization approach. The idea is as follows: We minimize the distance between the two free nodes  and , which we want to connect, with respect to variable nodal positions, and, additionally, require the edge lengths associated with the variable nodes to comply with the minimum and maximum edge lengths. Initially, we only allow the positions of nodes  and  to vary. We increase the number of variable nodes for each successive optimization step in an advancing front manner until the distance between the nodes  and  vanishes and the nodal coordinates are equal.

Let  be the set of variable nodes consisting of  nodes and  with ,  the -tuple of all variable nodes. The stacked vector of variable nodal coordinates  corresponding to the positions of the variable nodes is then given by(32)The optimization is started with  variable nodes chosen as the two free nodes  and  which shall be connected. The objective function  for the optimization procedure is provided by the distance between the nodes  and . To facilitate computation, we choose the quadratic distance given by(33)as objective function. Furthermore, we need to guarantee that all edge lengths stay within the maximum and minimum bounds. We only have to consider edges  with at least one variable node . The optimization problem, thus, is given by(34)

Additionally, we want to avoid solutions of the optimization that might be mathematically correct but infeasible, as these would correspond to free nodes lying on the wrong side of their associated base edge, as depicted in Fig. 24(a). To permit only feasible solutions like illustrated in (b), we constrain the two free connecting nodes to lie in the correct half-space of their corresponding base edges. This is accomplished by introducing additional inequality constraints. Considering Fig. 25, we can determine the half-space of the free node  with respect to the base edge between the nodes  and  by calculating the scalar product of the vectors  and , which is the vector perpendicular to , given by(35)

1. Download : Download high-res image (145KB)

2. Download : Download full-size image

Fig. 24. Possible solutions  after optimization for free nodes  and : (a) infeasible solution and (b) desired feasible solution.

The half-space of node  with respect to the edge  is then given by the sign of the scalar product, i.e., (36)which is either ＋1 or −1. The free node  must thus lie in the same half-space before and after the optimization. This condition can be formulated as an additional inequality constraint with the initial half-space  of node  given by(37)

The optimization problem in (34), extended with the half-space constraint in (37), serves as the basis for the automated alteration of the local geometry to achieve closing. However, the proposed approach does not check if the resulting geometric configuration is collision-free, i.e., that some ATCs included in the optimization process may partially overlap with neighboring or distant ATCs. Particularly collisions between topologically distant ATCs pose problems since such cases cannot be considered a priori in the optimization in contrast to immediate neighbor ATCs. Hence, collision avoidance is not considered in the scope of this paper but is deferred to future work. The posed optimization problem can be solved using one of the many well-known methods for constrained optimization. We chose a trust region method based on interior point techniques based on [77], [78]. The solution to the optimization problem is, in general, non-unique, i.e., there is a multitude of geometric configurations that fulfill the optimization criteria. However, this non-uniqueness of the solution is not problematic since the exact geometric configuration of a particular topological configuration is, in most cases, irrelevant for topological reconfiguration. In addition, the closing procedure is merely an intermediate step in the surface motion of ATCs, as the intermediate geometric configuration is restored to the previous surface geometry in the subsequent opening procedure.

1. Download : Download high-res image (36KB)

2. Download : Download full-size image

Fig. 25. Definition of vectors , , and  for the determination of the half-space of the free node  with respect to the edge .

In each consecutive optimization step, we systematically extend the set of variable nodes . Let  be the set of all nodes that are connected to variable nodes, i.e., (38)The variable nodes  for optimization step  are recursively defined by the union of the variable nodes  and connected nodes  of the previous optimization step , i.e., (39)

This process is continued until , which corresponds to the nodal positions of  and  being equal. The extension of variable nodes with each reconfiguration step is schematically depicted in Fig. 26, where in order to connect two ATCs (a), the variable nodes are augmented in an advancing front manner (b)–(d).

To facilitate the minimization of , the nodal coordinates  of the last step that yielded a minimal function value for  can be substituted as initial conditions for the next optimization step. This choice of initial values guarantees that the function value of  is monotonically decreasing towards zero. Variable nodes not included in the previous optimization step are initialized with the original nodal coordinates.

1. Download : Download high-res image (274KB)

2. Download : Download full-size image

Fig. 26. Optimization process for closing a loop (a) by successively adding nodes: free nodes (nodes 1 and 2) are set variable; the edges are constrained to minimum/maximum edge lengths (b). If no solution is found, connected nodes (nodes 3–5) are also included (c); the process is continued by adding successive nodes (nodes 6-9) until a solution is found and a connection is possible (d).

To further ease the closing process, we implemented selective disconnection of ATCs. For a kinematic loop that is to be formed with more than one ATC connected to the remaining robot, we can terminate all connections except for one. The removed connections increase the range of motion of the ATCs, which in turn facilitates the closing operation, while the connectivity of the modular robot is still guaranteed by the remaining connection. When the moving ATC is advanced one step along the surface, the previous surface geometry can be restored, and all due to selective disconnection terminated connections can be reconnected.

6. Reconfiguration example

We will consider two reconfiguration examples, one with 12 ATCs and one with 62 ATCs. The initial and goal configurations were created manually and serve as a small example to visualize the reconfiguration procedure (12ATCs) and a large, more complex example to evaluate the performance of the algorithm (62ATCs), respectively. The validation of the proposed algorithm on a multitude of automatically generated test configurations similar to [15] is desirable, but due to the unstructured nature of the configuration space and geometrical limitations of the robotic modules regarding edge lengths yet not realized. An automated configuration generator would, in principle, create a configuration with a specified number of ATCs utilizing a bottom-up approach by successively connecting new triangles with varying geometry to free edges of an existing configuration until the specified number is reached. Occasionally, kinematic loops must be closed, and the geometry adapted to comply with the geometric limitations. The implementation of such a configuration generator is, however, beyond the scope of the present paper. The reconfiguration examples can be viewed in full length in the supplementary videos (S4 and S5, respectively).

1. Download : Download high-res image (203KB)

2. Download : Download full-size image

Fig. 27. Configuration and binary tree with BT-indices of initial (a) and goal configuration (b).

1. Download : Download high-res image (802KB)

2. Download : Download full-size image

Fig. 28. Self-reconfiguration of a PARTS system from an initial configuration (a) to a goal configuration (n) via intermediate configurations (b) – (m). The highlighted elements in the tree correspond to the common subtree of the current configuration and goal configuration. All numbers refer to ATC identifiers for associated modules.

6.1. Reconfiguration example using 12 ATCs

To demonstrate the steps of the proposed reconfiguration algorithm, we consider the configurations in Fig. 27, consisting of 12 ATCs. The initial configuration is depicted in (a), and the goal configuration is depicted in (b). Intermediate configurations and their corresponding EBTs are shown in Fig. 28, where elements that already occupy the correct position in the configuration topology are highlighted in the binary tree.

Starting from the initial configuration (a), the simply-connected ATC 12 is first moved along the surface to the lowest unoccupied BT-index of the goal configuration (b). Next, the kinematic loop with the two-connected ATC with the largest BT-index that is not already part of the goal configuration is opened to form two simply-connected ATCs, ATC 5 and ATC 6 (c). The bypass strategy BPS2 is applied to traverse the original moving ATC 6 through the chain consisting of ATCs 10 and 11 (d). ATC 10 is, after applying BPS2, the new simply-connected ATC that is to be moved. Note that as the parent of the corresponding interconnection index (ATC 7) is already in place, ATC 10 is moved to the surface position ahead of the goal position, such that it is connected to ATC 7 (e). In the next step, the kinematic loop can be closed with ATC 12, thus simultaneously populating the BT-index and forming the interconnection of the corresponding interconnection index (f). The simply-connected ATC 5 is then traversed through the chain consisting of ATC 11 and ATC 6 by the execution of BPS2 (g). The new moving ATC 11 can then advance one surface position to populate the next BT-index (h). To create new simply-connected ATCs for movement, the connection between ATC 3 and ATC 4, which is the two-connected ATC with the largest BT-index, is opened (i). After applying BPS2 for another time on ATC 4 to traverse the chain consisting of ATC 6 and ATC 5 (j), the new moving ATC 6 is already at the correct goal position, and the corresponding interconnection can by formed by docking with ATC 5 (k). The last simply-connected ATC 3 is moved one step along the surface (l), then, in order to traverse the other simply-connected ATC 4, BPS3 is performed (m). Finally, as the new moving ATC 4 is already at the desired position, the remaining interconnection can be formed by closing ATC 4 and ATC 11 to finish the reconfiguration (n). The reconfiguration takes a total of 20 reconfiguration steps of opening/closing to complete.

6.2. Reconfiguration example using 62 ATCs

The second reconfiguration example consists of 62 ATCs and is depicted in Fig. 29. The initial configuration has a rectangular shape (a) and reconfigures into a configuration in the shape of a ‘T’ (d). Two intermediate configurations are given after 190 reconfiguration steps (b) and 380 reconfiguration steps (c). The whole reconfiguration takes 639 steps to complete, which is way below the upper bound of  reconfiguration steps. Particularly interesting is the number of optimization steps in the translation of the reconfiguration steps to module movements. Out of the 639 closing operation, 15 completed without optimization, as the nodes were already equal, 242 closing operation succeeded after the first optimization step and 382 after the second optimization step. No closing operation required more than two optimization steps.

1. Download : Download high-res image (229KB)

2. Download : Download full-size image

Fig. 29. Reconfiguration example with 62 ATCs from an initial lying rectangular configuration (a) to a ‘T’ configuration (d). Intermediate configurations are depicted after 190 reconfiguration steps (b) and 380 reconfiguration steps (c).

Fig. 30 shows the configuration distance between the goal EBT and the EBT at reconfiguration step . The configuration distance decreases from an initial value of 52 steadily towards 0. The flat steps correspond to ATC movement along the surface, where the configuration distance stays constant until the moving ATC reaches its goal position, then it drops by one. The occasional upward spikes correspond to the temporary increase in configuration distance due to the application of a BPS. However, after the BPS is completed, the configuration distance returns to the previous value. As shown in Section 5.1, the moving ATC is guaranteed to reach any goal position on the surface, enabling the successive element-wise construction of the goal configuration. Due to the deterministic nature of this rule-based reconfiguration approach, the configuration distance invariably decreases steadily towards 0.

1. Download : Download high-res image (124KB)

2. Download : Download full-size image

Fig. 30. Configuration distance for the reconfiguration of the rectangular configuration to the ‘T’ configuration with 62 ATCs plotted over the number of reconfiguration steps.

7. Discussion

The proposed reconfiguration algorithm is deterministic by design. Hence, it is also applicable for a large number of modules, as it does not suffer from limitations like search space explosion, a common problem in many search-based approaches [41], [42]. Completing in  reconfiguration steps, the performance of the algorithm is comparable to other reconfiguration algorithms that reach the same limiting behavior for two-dimensional modular robots like [79] for square modules or [80] for hexagonal modules. These approaches also achieve reconfiguration by the movement of single modules along the surface. A reduction to  reconfiguration steps was accomplished for pivoting square modules by implementing a parallelization of module movements [15]. Further improvement of reconfiguration efficiency was only attained by implementation of a highly parallelized volumetric flow of modules (e.g.  in [48]). A parallelization of module motion can also be incorporated in the proposed reconfiguration framework, as the module motion is realized by a variation of the local environment of the moving module, which can be performed on multiple different locations on the surface as long as the variable nodes are not associated to more than one optimization procedures. The motion of individual modules can be initialized sequentially in compliance with dependencies between modules, e.g., movement of one module can start only if the previous module already passed (see supplementary video S1).

EBTs rely on the faithful representation of the binary tree indices using large integer values. Most built-in integer types can thus not represent EBT with more than 63 levels using, for example, uint64 or unsigned long long data types, corresponding to a maximum shortest distance between any ATC and the constrained ATC to be below 64 modules. This limitation can be surmounted by employing big-integer libraries, which hold in some programming environments no upper bound and therefore set virtually no limit on the maximum system size. Note that for computation of the surface order using binary logarithms, the precision must also be enhanced using multiple-precision floating-point libraries, such that tiny differences in the results can be faithfully represented and thus guarantee the correct arrangement of the surface elements.

One main drawback of the reconfiguration approach is that collision avoidance is not addressed yet. Collision control of a moving ATC with the adjacent surface sections can be incorporated in the optimization procedure for closing by appending additional inequality constraints. However, even if the solution of the optimization procedure contains no collisions, a validation for the transitional movement between morphological configurations is still necessary. Problematic are particularly highly concave surface geometries, as ATCs that are topologically distant from a moving ATC might nevertheless block the surface path. For example, considering the surface geometry in Fig. 31, a kinematic chain is almost in contact with the surface. When the gray ATC is moved along the surface to the dashed goal position, a collision with the end of the chain (hatched ATC) will occur, although the ATCs are several positions along the surface apart (see supplementary video S3). A possible strategy for collision avoidance using the adaptability of PARTS is to move the tip of the chain away from the surface to generate space (see supplementary video S2). Detection of such cases and the explicit motion control of the involved ATCs is yet to be realized.

Also, it is not guaranteed that the optimization procedure to form new kinematic loops ((34), (37)) inevitably terminates. Although the inclusion of a steadily increasing local environment results in more adaptable variables in the optimization, which leads to, at least, a potential decrease in the nodal distance, there is no absolute certainty that this is the case for all possible geometries. It can, hence, not be ruled out that certain types of local geometries have no solutions for the presented optimization algorithm. Nonetheless, our experiments suggest that the optimization swiftly converges with an increasing number of variable nodes as the procedure terminated within at most two optimization steps. Further investigations are necessary to either confirm the termination of the algorithm or rebut it with counterexamples. If the termination cannot be guaranteed, strategies for cases where the optimization procedure fails to give a solution are required, like additional removal of connections to increase the motion capability of elements.

1. Download : Download high-res image (96KB)

2. Download : Download full-size image

Fig. 31. When moving the gray ATC over the surface to the dashed goal position, a collision occurs with the hatched ATC. The surface path is depicted as thick black line.

EBTs as configuration representations also have a downside, as they might fail to reveal the largest common subtree using the proposed similarity transformations and configuration distance. For example, considering the configurations in Fig. 32(a) with their EBT representations, the output of the similarity transformation is given in (b) as the subtree of BT-indices in both configurations. However, the actual largest common subconfiguration is depicted in (c), such that topological reconfiguration can be achieved by moving only a single ATC. The incapability of the similarity transformation to find the largest subtree disqualifies the configuration distance as a proper metric in the mathematical sense, as the triangle inequality is not fulfilled. In order to find the largest subtree, all members of the equivalence classes of the two configurations would have to be compared, and the EBTs with the largest intersection in BT-indices would constitute the largest subtree. This procedure, however, increases in computational cost for an increasing number of interconnections in the EBT exponentially and is thus only feasible for a small number of modules.

1. Download : Download high-res image (307KB)

2. Download : Download full-size image

Fig. 32. The EBT of two different configurations with each 12 ATCs (a) have a distance of 3 when using the proposed distance metric and 9 ATCs already in place (b). However, the largest common subtree given by the topology consists of 11 ATCs (c).

8. Conclusion

The novel configuration representation based on extended binary trees and the proposed reconfiguration algorithm establishes a principal framework for the reconfiguration of planar adaptive robots with a triangular structure. The algorithm accomplishes the self-reconfiguration of PARTS configurations represented by unstructured triangular meshes. Thus, the presented algorithm is the first reconfiguration approach to solve the self-reconfiguration problem for these modular robots. However, the algorithm still has several shortcomings. The centralized structure introduces a single point of failure, collisions between modules are neither detected nor avoided, and the feasibility of a particular reconfiguration step has not been proved, which all limit the practical application of the proposed method. Yet, the proposed reconfiguration framework offers numerous possibilities for extension, e.g., the local alteration of the triangular mesh allows for parallelization of module motion, or the optimization problem can be extended with additional constraints to prevent collisions. Therefore, the framework can serve as a foundation and benchmark for the development of more efficient reconfiguration approaches for this class of modular robotic systems. Future research focuses on an extension of the reconfiguration approach with collision detection and avoidance strategies and the adaption of methods to the more restricted motion capabilities of existing modules, allowing the employment of the reconfiguration algorithm on the hardware realization of PARTS.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.