In Lesson 1 you met links, joints, and generalized coordinates. A serial robot arm is a sequence of rigid links connected by single-degree-of-freedom joints starting at a base link and ending at an end-effector link. We now abstract this structure using graph theory.

Let \( \mathcal{L} = \{0, 1, \dots, n\} \) be the set of links, where link \(0\) is the base, and links \(1,\dots,n\) are movable. Each joint \( j_i \) connects link \(i-1\) to link \(i\) and is parameterized by a generalized coordinate \( q_i \in \mathbb{R} \) (revolute or prismatic). Collecting coordinates gives the joint-space vector

\[ \mathbf{q} = \begin{bmatrix} q_1 & q_2 & \dots & q_n \end{bmatrix}^\top \in \mathbb{R}^n. \]

The combinatorial pattern of which links are connected by which joints is independent of the specific joint values \( \mathbf{q} \). This pattern is what we call the kinematic chain. To analyze it rigorously, we represent it as a graph and then layer the geometry (homogeneous transforms, twists) on top in later chapters.

flowchart TD
  P["Physical robot (links + joints)"] --> I["Identify link set L = {0,...,n}"]
  I --> J["Identify joints and their types (R / P)"]
  J --> G["Construct graph: vertices = links, edges = joints"]
  G --> T["Check structure: serial path / tree / loops"]
  T --> M["Attach rigid transforms to edges"]
  M --> K["Use graph + transforms for kinematic modeling"]
        

A kinematic chain is modeled as an undirected or directed graph \( \mathcal{G} = (\mathcal{V}, \mathcal{E}) \), where:

• \( \mathcal{V} \) is the set of vertices, one per link: \( \mathcal{V} = \mathcal{L} = \{0, 1, \dots, n\} \).
• \( \mathcal{E} \) is the set of edges, one per joint: \( \mathcal{E} = \{ e_1, \dots, e_m \} \).

For a strictly serial chain with \(n\) movable links, we have \(m = n\) joints and the edge \( e_i \) connects \(i-1\) to \(i\):

\[ e_i = \{ i-1, i \}, \quad i = 1, \dots, n. \]

The underlying graph is a simple path: \(0 - 1 - 2 - \cdots - n\). More complex manipulators (with branches) produce trees, and mechanisms with kinematic loops produce graphs with cycles. In this lesson we focus on open serial chains and general trees, leaving loop constraints to later chapters.

To exploit tools from linear algebra, we encode \( \mathcal{G} \) using matrices. The most common are:

• The adjacency matrix \( \mathbf{A} \in \{0, 1\}^{|\mathcal{V}| \times |\mathcal{V}|} \), with entries

  \[ a_{ij} = \begin{cases} 1, & \text{if a joint connects links } i \text{ and } j, \\ 0, & \text{otherwise}. \end{cases} \]

• The incidence matrix \( \mathbf{B} \in \{-1, 0, 1\}^{|\mathcal{V}| \times |\mathcal{E}|} \), which uses an arbitrary orientation of edges. If edge \(e_k\) is oriented from vertex \(i\) to \(j\), then

  \[ b_{ik} = -1,\quad b_{jk} = 1,\quad b_{\ell k} = 0 \ \text{for all other } \ell. \]

These matrices capture purely combinatorial structure, independent of the geometric meaning of a joint (revolute or prismatic) and independent of \( \mathbf{q} \). In later lessons, the same graph structure will underlie Jacobians and dynamics.

A serial manipulator without closed loops corresponds to a tree graph. A tree is a connected graph with no cycles. For a tree with \( N \) vertices and \( E \) edges, a fundamental identity holds:

\[ E = N - 1. \]

Proof (by induction on \(N\)). For \(N = 1\) (a single vertex), we have a tree with no edges, so \(E = 0 = N - 1\). Assume the formula holds for all trees with \(N-1\) vertices. Consider a tree with \(N\) vertices. A tree always has at least one leaf (a vertex of degree one). Remove that leaf and its incident edge to obtain a smaller tree with \(N-1\) vertices and \(E-1\) edges. By the induction hypothesis, \(E-1 = (N-1) - 1\), hence \(E = N - 1\).

For a serial chain, the tree is in fact a path, a special tree where every vertex (except the endpoints) has degree 2. With links numbered from base to end-effector, the kinematic structure is:

\[ \mathcal{V} = \{0, 1, \dots, n\},\quad \mathcal{E} = \big\{ \{0,1\}, \{1,2\}, \dots, \{n-1, n\} \big\},\quad N = n+1,\ E = n. \]

We often choose a rooted representation, with the root at the base link 0. The unique simple path from 0 to link \(i\) gives the parent relation \( p(i) \), where \(p(i)\) is the unique neighbor of \(i\) on the path towards the root. For a pure serial chain, \(p(i) = i-1\).

graph LR
  L0["Link 0 (base)"] -- "joint 1" --> L1["Link 1"]
  L1 -- "joint 2" --> L2["Link 2"]
  L2 -- "joint 3" --> L3["Link 3 (end-effector)"]
        

This graph-centric picture generalizes naturally to branched manipulators: a node may have multiple children, but the tree remains acyclic. Only when we introduce closed loops (multiple distinct paths between two links) will we leave the tree setting and require explicit kinematic constraints (covered in later chapters).

For a tree, the adjacency and incidence matrices have special properties that will be useful later for dynamics and numerical algorithms.

Let \( N = |\mathcal{V}| \) and \( E = |\mathcal{E}| = N - 1 \). The incidence matrix \( \mathbf{B} \in \{-1,0,1\}^{N \times E} \) of a tree with arbitrary edge orientations satisfies:

\[ \operatorname{rank}(\mathbf{B}) = N - 1 = E. \]

Sketch of proof. The nullspace of \( \mathbf{B}^\top \) contains the all-ones vector \( \mathbf{1} \), because the sum of each column is zero. For a connected graph, \( \dim \ker(\mathbf{B}^\top) = 1 \), so \( \operatorname{rank}(\mathbf{B}) = N - 1 \). For a tree we have \(E = N - 1\), hence \( \mathbf{B} \) has full column rank and there are no independent cycles.

This algebraic condition (no non-trivial solutions of \( \mathbf{B}\boldsymbol{\lambda} = 0 \)) matches the combinatorial fact that trees have no cycles. In contrast, closed-chain mechanisms have \(E \gt N - 1\) and a non-trivial cycle space.

For computation it is often more convenient to store the parent of each link in a vector \( \mathbf{p} \):

\[ \mathbf{p} = \begin{bmatrix} p(0) & p(1) & \dots & p(n) \end{bmatrix}^\top, \quad p(0) = -1\ \text{(no parent)},\quad p(i) \in \{0, \dots, n\},\ i \ge 1. \]

For a pure serial chain, \( p(i) = i-1 \) for \(i = 1,\dots,n\). For a general tree, \( p(i) \) may be any earlier link in a topological ordering that respects the root. The parent vector is a compact representation of the kinematic structure and is frequently used in efficient dynamics algorithms (e.g., Featherstone's articulated-body method).

From Chapter 2 you know how to represent rigid-body configurations as homogeneous transforms \( {}^i\!T_j \in \mathrm{SE}(3) \), mapping coordinates from frame \(j\) to frame \(i\). For each joint connecting link \(p(i)\) to link \(i\), we associate a joint transform \( {}^{p(i)}\!T_i(q_i) \) that depends only on the joint coordinate \(q_i\).

Let \( {}^0\!T_i(\mathbf{q}) \) denote the transform from the base frame on link 0 to the frame attached to link \(i\). By composing transforms along the unique path from the root to \(i\), we obtain the recursion:

\[ {}^0\!T_i(\mathbf{q}) = {}^0\!T_{p(i)}(\mathbf{q}) \; {}^{p(i)}\!T_i(q_i),\quad {}^0\!T_0(\mathbf{q}) = \mathbf{I}_{4}. \]

Proof (by induction on depth). For the root link \(i=0\), we define \( {}^0\!T_0 = \mathbf{I}_4 \). Suppose the formula holds for every ancestor of link \(i\), in particular for its parent \(p(i)\). The unique path from 0 to \(i\) is obtained by concatenating the path from 0 to \(p(i)\) with the edge \((p(i), i)\). The corresponding rigid-body transform is the product of transforms along this path, hence \( {}^0\!T_i = {}^0\!T_{p(i)} \, {}^{p(i)}\!T_i \), as claimed.

For a pure serial chain with \(p(i) = i-1\), this reduces to

\[ {}^0\!T_k(\mathbf{q}) = {}^0\!T_0 \prod_{i=1}^{k} {}^{i-1}\!T_i(q_i) = \prod_{i=1}^{k} {}^{i-1}\!T_i(q_i),\quad k = 1,\dots,n. \]

Although detailed parameterizations of \( {}^{i-1}\!T_i(q_i) \) via Denavit–Hartenberg or product-of-exponentials will appear in Chapter 5, the recursive structure above already highlights how the graph of the chain determines the composition order.

We now implement a minimal kinematic-graph data structure in several languages. The focus is on representing the connectivity (parent vector, adjacency) and using it to compute base-to-link transforms given per-joint transforms. We restrict ourselves to serial chains, but the same structure generalizes to trees.

6.1 Python: Adjacency and Recursive Transforms (NumPy)

In Python, a convenient combination is numpy for matrices and networkx for graph algorithms. Below we use only numpy and a simple parent-vector representation to stay close to the mathematics.

import numpy as np

class SerialChain:
    def __init__(self, n_links):
        # links are 0,...,n_links-1, base is 0, end-effector is n_links-1
        self.n_links = n_links
        # parent[i] = index of parent of link i; parent[0] = -1 (no parent)
        self.parent = [-1] + [i for i in range(n_links - 1)]
        # each joint transform is a function q_i -> 4x4 homogeneous matrix
        self.joint_tf = [None] * n_links

    def set_joint_transform(self, i, f_q_to_T):
        """
        i: link index > 0
        f_q_to_T: callable q -> 4x4 np.array in SE(3)
        """
        assert 0 <= i < self.n_links
        self.joint_tf[i] = f_q_to_T

    def forward_transforms(self, q):
        """
        q: array-like of length n_links-1 (q[0] for joint 1, etc.).
        Returns list T[i] = ^0 T_i(q).
        """
        T = [np.eye(4) for _ in range(self.n_links)]
        for i in range(1, self.n_links):
            p = self.parent[i]
            T_pi = self.joint_tf[i](q[i - 1])  # ^{p(i)} T_i(q_i)
            T[i] = T[p] @ T_pi
        return T

# Example: 3-link planar RRR chain with unit-length links in the x-y plane
def planar_R_joint(theta, a):
    c, s = np.cos(theta), np.sin(theta)
    T = np.eye(4)
    T[0, 0] = c; T[0, 1] = -s; T[1, 0] = s; T[1, 1] = c
    T[0, 3] = a  # translation along x of parent frame
    return T

chain = SerialChain(n_links=4)  # links 0..3, joints 1..3
link_lengths = [1.0, 1.0, 1.0]
for i in range(1, 4):
    a_i = link_lengths[i - 1]
    chain.set_joint_transform(i, lambda th, a=a_i: planar_R_joint(th, a))

q = np.array([0.2, 0.4, -0.3])
T_list = chain.forward_transforms(q)
T_ee = T_list[-1]
print("End-effector position:", T_ee[:3, 3])
      

6.2 C++: Parent Vector and Eigen Matrices

In C++, the combination of Eigen (for linear algebra) and robotics libraries such as orocos_kdl is common. Below is a lightweight serial-chain structure using Eigen::Matrix4d and function pointers for joint transforms. The same pattern underlies more sophisticated libraries.

#include <iostream>
#include <vector>
#include <functional>
#include <Eigen/Dense>

class SerialChain {
public:
    using Transform = Eigen::Matrix4d;
    using JointTF = std::function<Transform(double)>;

    explicit SerialChain(int n_links)
        : n_links_(n_links),
          parent_(n_links),
          joint_tf_(n_links) {
        parent_[0] = -1;
        for (int i = 1; i < n_links_; ++i) {
            parent_[i] = i - 1;
        }
    }

    void setJointTransform(int i, JointTF f) {
        if (i <= 0 || i >= n_links_) {
            throw std::runtime_error("Invalid link index");
        }
        joint_tf_[i] = std::move(f);
    }

    std::vector<Transform> forwardTransforms(const std::vector<double>& q) const {
        std::vector<Transform> T(n_links_, Transform::Identity());
        for (int i = 1; i < n_links_; ++i) {
            int p = parent_[i];
            Transform T_pi = joint_tf_[i](q[i - 1]);
            T[i] = T[p] * T_pi;
        }
        return T;
    }

private:
    int n_links_;
    std::vector<int> parent_;
    std::vector<JointTF> joint_tf_;
};

// Example planar revolute joint
SerialChain::Transform planarR(double theta, double a) {
    SerialChain::Transform T = SerialChain::Transform::Identity();
    double c = std::cos(theta), s = std::sin(theta);
    T(0,0) = c;  T(0,1) = -s;
    T(1,0) = s;  T(1,1) =  c;
    T(0,3) = a;
    return T;
}

int main() {
    SerialChain chain(4); // links 0..3
    std::vector<double> a = {1.0, 1.0, 1.0};

    for (int i = 1; i <= 3; ++i) {
        chain.setJointTransform(i,
            [ai = a[i - 1]](double q_i) {
                return planarR(q_i, ai);
            }
        );
    }

    std::vector<double> q = {0.2, 0.4, -0.3};
    auto T = chain.forwardTransforms(q);
    std::cout << "End-effector position: "
              << T.back()(0,3) << " "
              << T.back()(1,3) << " "
              << T.back()(2,3) << std::endl;
    return 0;
}
      

6.3 Java: Graph Representation with Adjacency Lists

Java does not have a canonical robotics library, but matrix libraries such as EJML or Apache Commons Math are common. Here we emphasize the graph representation using adjacency lists and a parent array.

import java.util.ArrayList;
import java.util.List;
import java.util.function.DoubleFunction;

public class SerialChain {
    public static class Transform {
        // Minimal 4x4 matrix representation
        public double[][] data = new double[4][4];
        public Transform() {
            for (int i = 0; i < 4; ++i) data[i][i] = 1.0;
        }
        public static Transform multiply(Transform A, Transform B) {
            Transform C = new Transform();
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < 4; ++j) {
                    C.data[i][j] = 0.0;
                    for (int k = 0; k < 4; ++k) {
                        C.data[i][j] += A.data[i][k] * B.data[k][j];
                    }
                }
            }
            return C;
        }
    }

    private int nLinks;
    private int[] parent;
    private List<DoubleFunction<Transform>> jointTF;

    public SerialChain(int nLinks) {
        this.nLinks = nLinks;
        this.parent = new int[nLinks];
        this.jointTF = new ArrayList<>(nLinks);
        parent[0] = -1;
        for (int i = 1; i < nLinks; ++i) parent[i] = i - 1;
        for (int i = 0; i < nLinks; ++i) jointTF.add(null);
    }

    public void setJointTransform(int i, DoubleFunction<Transform> f) {
        if (i <= 0 || i >= nLinks) {
            throw new IllegalArgumentException("Invalid link index");
        }
        jointTF.set(i, f);
    }

    public Transform[] forwardTransforms(double[] q) {
        Transform[] T = new Transform[nLinks];
        for (int i = 0; i < nLinks; ++i) T[i] = new Transform();
        for (int i = 1; i < nLinks; ++i) {
            int p = parent[i];
            Transform Tpi = jointTF.get(i).apply(q[i - 1]);
            T[i] = Transform.multiply(T[p], Tpi);
        }
        return T;
    }

    public static Transform planarR(double theta, double a) {
        Transform T = new Transform();
        double c = Math.cos(theta), s = Math.sin(theta);
        T.data[0][0] = c;  T.data[0][1] = -s;
        T.data[1][0] = s;  T.data[1][1] =  c;
        T.data[0][3] = a;
        return T;
    }

    public static void main(String[] args) {
        SerialChain chain = new SerialChain(4);
        double[] a = {1.0, 1.0, 1.0};
        for (int i = 1; i <= 3; ++i) {
            final double ai = a[i - 1];
            chain.setJointTransform(i, (double q_i) -> planarR(q_i, ai));
        }
        double[] q = {0.2, 0.4, -0.3};
        Transform[] T = chain.forwardTransforms(q);
        Transform Tee = T[3];
        System.out.println("End-effector x = " + Tee.data[0][3]
                           + ", y = " + Tee.data[1][3]);
    }
}
      

6.4 MATLAB/Simulink: Kinematic Tree and Programmatic Model Creation

MATLAB provides matrix operations and Simulink/Simscape Multibody for graphical modeling. We first represent the parent vector and then sketch programmatic creation of a simple chain model in Simscape Multibody.

% Number of links (including base)
nLinks = 4;
parent = -ones(1, nLinks);   % parent(1) = -1 (base)
for i = 2:nLinks
    parent(i) = i - 1;
end

% Joint transforms as function handles
linkLengths = [1.0, 1.0, 1.0];
jointTF = cell(1, nLinks);
jointTF{1} = [];  % no joint to base
for i = 2:nLinks
    a = linkLengths(i - 1);
    jointTF{i} = @(theta) planarR(theta, a);
end

function T = planarR(theta, a)
    c = cos(theta); s = sin(theta);
    T = eye(4);
    T(1,1) = c;  T(1,2) = -s;
    T(2,1) = s;  T(2,2) =  c;
    T(1,4) = a;
end

function T = forwardTransforms(q, parent, jointTF)
    nLinks = numel(parent);
    T = repmat(eye(4), 1, 1, nLinks);
    for i = 2:nLinks
        p = parent(i);
        T_pi = jointTF{i}(q(i - 1));
        T(:, :, i) = T(:, :, p) * T_pi;
    end
end

% Example
q = [0.2; 0.4; -0.3];
T = forwardTransforms(q, parent, jointTF);
T_ee = T(:, :, end)

% Programmatic Simulink (Simscape Multibody) sketch:
modelName = "serial_chain_model";
new_system(modelName);
open_system(modelName);

% Add Simscape Multibody environment and 3 revolute joints with links
% (actual block names may vary by MATLAB version)
% add_block('sm_lib/Body Elements/Body', [modelName '/Link1']);
% add_block('sm_lib/Joints/Revolute Joint', [modelName '/Joint1']);
% ...
      

6.5 Wolfram Mathematica: Graph and Adjacency Matrix

Mathematica has first-class support for graphs and symbolic linear algebra, which makes it convenient for reasoning about kinematic chains.

(* Define a 3-DOF serial chain: links 0..3 *)
links = Range[0, 3];
edges = {0 <-> 1, 1 <-> 2, 2 <-> 3};
G = Graph[links, edges, VertexLabels -> "Name"]

A = AdjacencyMatrix[G]
B = IncidenceMatrix[G]

(* Verify tree property: Rank[B] == N - 1 *)
nVertices = Length[links];
rankB = MatrixRank[B]

(* Recursive transforms with symbolic joint variables *)
Clear[q1, q2, q3];
q = {q1, q2, q3};

planarR[theta_, a_] := Module[{c = Cos[theta], s = Sin[theta]},
  {
    {c, -s, 0, a},
    {s,  c, 0, 0},
    {0,  0, 1, 0},
    {0,  0, 0, 1}
  }
];

T01 = planarR[q1, 1];
T12 = planarR[q2, 1];
T23 = planarR[q3, 1];

T02 = Simplify[T01 . T12];
T03 = Simplify[T01 . T12 . T23];

(* Extract symbolic end-effector position *)
pee = T03[[;; 3, 4]] // Simplify
      

Here AdjacencyMatrix and IncidenceMatrix realize the matrices from Sections 2 and 4, and the products T01 . T12 . T23 implement the recursive path composition from Section 5.

For an open serial chain with \(n\) single-degree-of-freedom joints, the configuration space is (ignoring joint limits) the product manifold

\[ \mathcal{Q} = \mathbb{R}^n \quad \text{(prismatic joints)} \qquad \text{or} \qquad \mathcal{Q} = \mathbb{T}^{n_r} \times \mathbb{R}^{n_p}, \]

where \(n_r\) is the number of revolute joints (angles on the circle \( \mathbb{T} \)) and \(n_p\) the number of prismatic joints. The underlying graph of the chain restricts how these coordinates interact when we map to task space (end-effector pose), but for an open chain the dimension of \( \mathcal{Q} \) is simply the number of joints:

\[ \dim \mathcal{Q} = n. \]

In later lessons, we will see how adding edges (closing loops) introduces algebraic constraints that reduce the dimension of admissible configurations, and how the cycle structure of the graph is directly related to these constraints.

In this lesson we formalized kinematic chains as graphs whose vertices correspond to links and edges to joints. For open serial chains, the graph is a rooted path (a special tree) with \(E = N - 1\) edges and a parent vector representation that is convenient for computation. We connected adjacency and incidence matrices to structural properties such as connectedness and the absence of cycles, and we derived a recursive formula for base-to-link homogeneous transforms that composes transforms along the unique path in the tree.

Implementation examples in Python, C++, Java, MATLAB/Simulink, and Wolfram Mathematica showed how to translate these ideas into data structures and algorithms. In upcoming lessons we will use the same graph structure to reason about open versus closed chains, degrees of freedom, and ultimately forward kinematics and dynamics.