O tehnică bazată pe grafuri, denumită graf cinematic, este introdusă pentru a reprezenta secvența ansamblare-modul și geometria robotului. În acest graf, un nod reprezintă un modul de articulare conectat, iar o muchie reprezintă un modul de legătură conectat. Modulele atașate sau detașate de robot pot fi indicate prin adăugarea sau eliminarea nodurilor sau muchiilor din graf. Realizarea acestui graf se face printr-o Matrice de Incidență de Asamblare (AIM) (Chen 1994; Chen și Burdick 1998). Un robot modular poate fi conceput în funcție de AIM-ul dat fără a cunoaște ceilalți parametri, cum ar fi unghiurile articulare și pozițiile inițiale. Aici, presupunem că structura generică a unui robot modular este de tip ramură. Robotul modular de tip serial este un caz special al structurii de tip ramură.
A graph-based technique, termed the kinematic graph, is introduced to represent the module-assembly sequence and robot geometry. In this graph, a node represents a connected joint module and an edge represents a connected link module. Modules attached to or detached from the robot can be indicated by adding or removing nodes or edges from the graph. The realization of this graph is through an Assembly Incidence Matrix (AIM) (Chen 1994; Chen and Burdick 1998). A modular robot can be conceived according to the given AIM without knowing the other parameters, such as joint angles and initial positions. Here, we assume the generic structure of a modular robot is branch type. The serial-type modular robot is a special case of the branch-type structure.

Reprezentarea modulului

Pentru a face ca algoritmii de generare automată a modelului să funcționeze pe o varietate de componente ale modulelor, introducem un set conceptual de module ale căror caracteristici sunt extrase din cele ale implementărilor reale. Sistemele modulare dezvoltate până în prezent au câteva caracteristici mecanice și structurale comune: (1) numai articulații revolute 1-DOF și articulații prismatice 1-DOF, (2) geometrii simetrice ale legăturilor pentru interschimbabilitate și (3) porturi de conectare multiple pe o legătură.
To make the automatic model-generation algorithms work on a variety of module components, we introduce a conceptual set of modules whose features are extracted from those of real implementations. The modular systems developed to date have several common mechanical and structural features: (1) only 1-DOF revolute and 1-DOF prismatic joints, (2) symmetric link geometries for interchangeability, and (3) multiple connection ports on a link.

Module articulare

Un modul de articulație pentru robot modular este o articulație „activă”, care permite generarea unei mișcări prescrise între legăturile conectate. Sunt luate în considerare două tipuri de module de articulare, articulațiile revolute (mișcare de rotație) și articulațiile prismatice (mișcare liniară sau de translație). Actuatoarele rotative și liniare trebuie să se afle în module pentru a produce mișcările necesare și pentru a menține modularitatea sistemului. Mișcările multi-DOF pot fi sintetizate cu mai multe articulații 1-DOF. Modulele articulare sunt atașate la modulele de legătură prin interfețe de conectare standardizate pentru conexiuni mecanice, de putere și de control.
A modular robot joint module is an “active” joint, which allows the generation of a prescribed motion between connected links. Two types of joint modules, the revolute joints (rotary motion) and the prismatic joints (linear or translational motion), are considered. Rotary and linear actuators must reside in the modules to produce the required motions and maintain the modularity of the system. Multi-DOF motions can be synthesized with several 1-DOF joints. Joint modules are attached to link modules through standardized connecting interfaces for mechanical, power, and control connections.

Module verigă (de legare)

Locul de pe un modul de legătură în care este conectată articulația se numește port de conectare. Fără a pierde generalitatea, presupunem că un modul de legătură este capabil de conexiuni multiple de articulare, iar modulul de legătură are o geometrie simetrică. Un astfel de design permite atașarea modulelor în diverse orientări și modificarea geometriei robotului printr-o simplă reasamblare. Componentele robotului modular dezvoltate în universitatea noastră sunt prezentate în Fig. 1. Acest design urmează principiul blocului de construcție prin care modulele pot fi stivuite împreună în diferite orientări prin puncte de conectare pe toate cele șase fețe ale cuburilor.
The place on a link module where the joint is connected is called a connecting port. Without loss of generality, we assume that a link module is capable of multiple joint connections, and the link module has symmetrical geometry. Such a design allows modules to be attached in various orientations and the robot geometry to be altered by simple reassembling. The modular robot components developed in our university are shown in Fig. 1. This design follows the building-block principle whereby modules can be stacked together in various orientations through connecting points on all six faces of the cubes.

Matricea de incidență a asamblării

Definiția 1 (Graf) Un graf 𝒢 = (𝒱, ℰ) constă dintr-o mulțime de vârfuri, 𝒱 = {v0, ... ,. vn}, și o mulțime de muchii, ℰ = {e0, . . .,em}, astfel încât fiecare muchie din ℰ este asociată cu o pereche de vârfuri, adică ej = {vj, . . ., vk}.
Definition 1 (Graph) A graph G = (V, E) consists of a vertex set, V = (v0,... ,vn), and an edge set,E ={e0, . . ., em}, such that every edge in E is associated with a pair of vertices, i.e., ej = {vj, . . ., vk}.

În teoria proiectării mecanismelor, un lanț cinematic de legături și articulații este adesea reprezentat de un graf, numit graf cinematic (Dobrjanskyj și Freudenstein 1967), în care vârfurile reprezintă legăturile și muchiile reprezintă articulațiile. Folosind această reprezentare graf, putem clasifica structura de bază (sau geometria) unui mecanism de legare și să aplicăm rezultatul din teoria grafurilor pentru a enumera și clasifica mecanismele de legătură. Un robot manipulator este, de asemenea, un lanț cinematic, admițând astfel o reprezentare grafică cinematică. De exemplu, un robot modular tip ramură cu 8 module 7-DOF și grafurile sale cinematice sunt prezentate în Fig. 2a, b (în digraf, săgeata de pe fiecare muchie indică de la vârful părinte la vârful copil). De asemenea, se știe că un graf poate fi reprezentat numeric ca o matrice de incidență vârf-muchie în care intrările conţin doar 0 şi 1 (Deo 1974). Intrarea (i, j) este egală cu 1 dacă muchia ej este incidentă pe vârful vi; în caz contrar, este egală cu zero. Această relație de incidență definește conectivitatea modulelor de legătură și de articulare. Deoarece modulele de legătură pot avea mai multe puncte de conectare, putem aloca etichete punctelor de conectare pentru a identifica conexiunea modulului. Pentru a identifica în continuare acele conexiuni în matricea de incidență, putem înlocui acele intrări de 1 cu etichetele porturilor conectate identificate pe modulele de legătură și păstrăm acele intrări de 0 neschimbate. Această matrice modificată, denumită matrice de incidență a asamblării, ne oferă informațiile necesare de conectare a modulelor și, de asemenea, geometria de bază a robotului modular.
In mechanism design theory, a kinematic chain of links and joints is often represented by a graph, termed a kinematic graph (Dobrjanskyj and Freudenstein 1967), in which vertices represent the links and edges represent the joints. Using this graph representation, we are able to categorize the underlying structure (or geometry) of a linkage mechanism and apply the result from the graph theory to enumerate and classify linkage mechanisms. A robot manipulator is also a kinematic chain, thus, admitting a kinematic graph representation. For example, an 8-module 7-DOF branch-type modular robot and its kinematic graphs are shown in Fig. 2a, b (in the digraph, the arrow on each edges point from the parent vertex to the children vertex). It is also known that a graph can be represented numerically as a vertex-edge incidence matrix in which the entries contain only 0s and 1s (Deo 1974). Entry (i, j) is equal to 1 if edge ej is incident on vertex vi; otherwise, it is equal to zero. This incidence relationship defines the connectivity of the link and joint modules. Because link modules may have multiple connecting points, we can assign labels to the connecting points to identify the module connection. To further identify those connections in the incidence matrix, we can replace those entries of 1 by the labels of the connected ports being identified on the link modules and keep those entries of 0 unchanged. This modified matrix, termed an assembly incidence matrix, provides us the necessary connection information of the modules and also the basic geometry of the modular robot.

Definiția 2 (Matricea de incidență a ansamblării - AIM) Fie 𝒢 un graf cinematic al unui robot modular și 𝓜(𝒢) matricea de incidență a acestuia. Fie port setul de etichete atribuite porturilor de conectare de pe modulele de legătură. Matricea de incidență a asamblării robotului 𝓐(𝒢) este formată prin înlocuirea acelor 1 din 𝓜(𝒢) cu etichete în port pe modulele respective. O coloană și o linie suplimentare sunt mărite la 𝓐(𝒢) pentru a afișa tipurile de module de legătură și de articulare.
Definition 2 (Assembly Incidence Matrix - AIM) Let G be a kinematic graph of a modular robot and M(G) be its incidence matrix. Let port be the set of labels assigned to the connecting ports on the link modules. The assembly incidence matrix of the robot A(G) is formed by substituting the 1s in M(G) with labels in port on respective modules. One extra column and row are augmented to A(G) to show the types of link and joint modules.

Rețineți că reprezentarea și atribuirea etichetelor nu sunt unice. Etichetele porturilor de conectare pot fi valori numerice (Chen 1994) sau pot fi derivate din coordonatele modulului (Chen și Yang 1996). În acest caz, baza de date modul-componentă ar trebui să utilizeze o contabilitate consecventă pentru aceste informații. AIM-a robotului modular (8 module de legătură și 7 module de articulare) prezentat în Fig. 4 este o matrice 9x8:
Note that the representation and assignment of the labels are nonunique. The labels of the connecting ports may be numerical values (Chen 1994) or may be derived from the module coordinates (Chen and Yang 1996). In this case, the module-component database should use consistent bookkeeping for this information. The AIM of the modular robot (8 link modules and 7 joint modules) shown in Fig. 4 is a 9 x 8 matrix:

Rețineți că există trei tipuri de module de legătură în robot: baza (B), modulul cubic mare (C1) și modulul cubic mic (C2). Modulele cubice au șase interfețe de conectare etichetate 1–6, adică port = {1,. . .,6}, care urmează schema de etichetare pe zaruri. Articulațiile revolute și articulațiile prismatice sunt notate cu R și, respectiv, P.
Note that there are three types of link modules in the robot: the base (B), the large cubic module (C1), and the small cubic module (C2). Cubic modules have six connecting interfaces labeled 1–6, i.e., port = {1,. . .,6}, which follows the labeling scheme on dice. The revolute joints and prismatic joints are denoted by R and P, respectively.

Matricea de accesibilitate și Matricea căilor

Două matrice, și anume, matricea de accesibilitate și matricea de cale, derivate dintr-o AIM dată, sunt definite în această secțiune pentru a furniza informații de accesibilitate de la modulul de bază la fiecare modul suspendat dintr-un robot modular tip ramură. Informațiile de accesibilitate ne permit să formulăm cinematica și dinamica unui robot general tip ramură într-un mod uniform.
Two matrices, namely, the accessibility matrix and the path matrix, derived from a given AIM are defined in this section to provide the accessibility information from the base module to every pendant module in a branch-type modular robot. The accessibility information enables us to formulate the kinematics and dynamics of a general branch-type robot in a uniform way.

Ordine de parcurgere a modulului

Legăturile și articulațiile unui robot tip serial pot urma o ordine naturală de la bază până la vârf. Un robot tip ramură are mai mult de un vârf și nu are bucle. Prin urmare, ordinea legăturilor unui robot tip ramură depinde de algoritmii de traversare a grafului (Cormen et al. 1990). Fie 𝒢 = (𝒱, ℰ), reprezentând graful cinematic al unui robot modular tip ramură cu n + 1 module de legătură, unde 𝒱 = {v0, ... ,vn} reprezintă setul de module. Modulul de bază fixă ​​este notat cu v0 și este întotdeauna punctul de plecare pentru algoritmul de parcurgere. Restul modulelor sunt etichetate după ordinea lor de parcurgere i. Ordinea de parcurgere a legăturilor în robotul din Fig. 2a sunt indicate prin numerele de pe vârfurile grafului din Fig. 2b. Această ordine este obținută prin algoritmul de căutare în profunzime. Rețineți că, cu cât modulul este mai departe de bază, cu cât ordinea sa de parcurgere este mai mare.
The links and joints of a serial-type robot can follow a natural order from the base to the tip. A branch-type robot has more than one tip and no loops. Therefore, the order of the links of a branch-type robot depends on the graph-traversing algorithms (Cormen et al. 1990). Let 𝒢 = (𝒱, ℰ), represent the kinematic graph of a branch-type modular robot with n + 1 link modules, where 𝒱 = {v0, ... ,vn} represents the set of modules. The fixed-base module is denoted by v0 and is always the starting point for the traversing algorithm. The rest of the modules are labeled by their traversing orders i. The traversing orders of the links in the robot of Fig. 2a are indicated by the numbers on the vertices of the graph of Fig. 2b. This order is obtained by the depth-first-search algorithm. Note that the farther the module is away from the base, the larger its traversing order.

Grafuri Dirijate

Un robot tip ramură cu n + 1 module are n articulații. Fie ℰ = {e0, . . .,em} să reprezinte setul de articulații, unde articulația ei este desemnată ca conectorul care precede modulul de legătură vi. Cu o ordine de parcurgere dată, graful robotului 𝒢 poate fi convertit într-un graf direcționat (sau digraf) 𝒢⃗, care este un arbore exterior pentru un manipulator tip ramură în felul următor. Fie ej = (vi, vj) o muchie a graficului 𝒢⃗ și i < j. O săgeată este trasă de la vi la vj deoarece muchia ej părăsește vârful vi și intră în vârful vj. Este suficient să spunem că link-ul vi precede link-ul vj. Un exemplu de graf direcționat este prezentat în Fig. 2b. Dintr-un arbore exterior cu n vârfuri, poate fi definită o matrice de accesibilitate nxn pentru a arăta accesibilitatea între vârfuri.
A branch-type robot with n + 1 modules has n joints. Let ℰ = {e0, . . .,em} represent the set of joints, where joint ei is designated as the connector preceding link module vi. With a given traversing order, the robot graph G can be converted to a directed graph (or digraph) 𝒢⃗, which is an outward tree for a branch-type manipulator in the following manner. Let ej = (vi, vj) be an edge of the graph 𝒢⃗ and i < j. An arrow is drawn from vi to vj as edge ej leaves vertex vi and enters vertex vj. Suffice to say, link vi precedes link vj. An example of the directed graph is shown in Fig. 2b. From an outward tree with n vertices, an nxn accessibility matrix can be defined to show the accessibility among the vertices.

Definiția 3 (Matricea de accesibilitate) Matricea de accesibilitate a unui graf cinematic direcționat 𝒢⃗a unui robot modular cu n + 1 module (vârfuri) este o matrice (n + 1) x (n + 1), ℛ(𝒢⃗)= [rij] (i, j = 0,...,n), astfel încât rij = 1, dacă există o cale direcționată de lungime unu sau mai mult de la vi la vj; rij = 0, în caz contrar.
Definition 3 (Accessibility Matrix) The accessibility matrix of a directed kinematic graph 𝒢⃗ of a modular robot with n + 1 modules (vertices) is an (n + 1) x (n + 1) matrix, ℛ(𝒢⃗)= [rij] (i, j = 0,...,n), such that rij = 1, if there is a directed path of length one or more from vi to vj; rij = 0, otherwise.

Matricea de accesibilitate poate fi derivată din AIM odată ce ordinea de parcurgere pe modulele de legătură este determinată. De exemplu, matricea de accesibilitate a lui 𝒢⃗ în Fig. 2b este
The accessibility matrix can be derived from the AIM once the traversing order on the link modules is determined. For example, the accessibility matrix of 𝒢⃗ in Fig. 2b is

De la ℛ(𝒢⃗), putem obține cel mai scurt traseu de la bază până la legătura pandantiv. Acest traseu se numește path=cale. Legăturile pandantivului sunt liniile lui ℛ(𝒢⃗) cu toate zerourile. Numărul de căi dintr-un robot de ramificare este egal cu numărul de legături suspendate. Fie link-ul vi un link pendant. Toate modulele de legătură de pe calea de la bază la vi sunt afișate în intrările diferite de zero ale coloanei i din (ℛ(𝒢⃗)+I_(n+1)x(n+1))^T. Colectând toate căile, obținem matricea căilor.
From ℛ(𝒢⃗), we can obtain the shortest route from the base to the pendant link. This route is called a path. The pendant links are the rows of ℛ(𝒢⃗) with all 0s. The number of paths in a branching robot is equal to the number of pendant links. Let link vi be a pendant link. All link modules on the path from the base to vi are shown in the nonzero entries of column i of (ℛ(𝒢⃗)+I_(n+1)x(n+1))^T. Collecting all the paths, we obtain the path matrix.

Definiția 4 (Path Matrix) Matricea căii P(𝒢⃗) a unui graf cinematic dirijat 𝒢⃗ a unui robot tip ramură cu n + 1 module de legătură (vârfuri) și m căi este o matrice m x (n + 1), ℛ(𝒢⃗) = [pij], (i = 1, 2, . . . ,m; j = 0, 1,. . . , n), astfel încât pij = 1, dacă calea i conține vârful j, iar pij = 0 în caz contrar.
Definition 4 (Path Matrix) The path matrix P(𝒢⃗) of a directed kinematic graph 𝒢⃗ of a branch-type robot with n + 1 link modules (vertices) and m paths is an m x (n + 1) matrix, ℛ(𝒢⃗) = [pij], (i = 1, 2, . . . ,m; j = 0, 1,. . . , n), such that pij = 1, if path i contains vertex j, and pij = 0 otherwise.

De exemplu, robotul din Fig. 2a conține trei ramuri (căi). Cele trei căi pot fi reprezentate ca o matrice de căi de 3 x 8:
For instance, the robot of Fig. 2a contains three branches (paths). The three paths can be represented as a 3 x 8 path matrix:

Linia 1 reprezintă ramura robotului care conține modulele de legătură v0, v1, v2 și v3; Linia 2 reprezintă ramura lui v0 și v4; Linia 3 reprezintă ramura lui v0, v5, v6 și v7. Se poate observa că liniile lui P(𝒢⃗) sunt identice cu coloanele 3, 4 și 7 din (ℛ(𝒢⃗)+I_(n+1)x(n+1)), respectiv.
Row 1 represents the branch of the robot containing link modules v0, v1, v2, and v3; Row 2 represents the branch of v0 and v4; Row 3 represents the branch of v0, v5, v6, and v7. It can be seen that the rows of P(𝒢⃗) are identical to Columns 3, 4, and 7 of (ℛ(𝒢⃗)+I_(n+1)x(n+1)), respectively.