Rendezvous is a network control algorithm which allows a collection of robots to meet at at the centroid of their initial positions. This document is a mathematical companion to the rendezvous sample code for the Robotarium. It summarizes the mathematics behind the consensus algorithm and highlights the transfer of the formal specification to the Robotarium’s MATLAB API. Additionally, this document contains experimental data from the Robotarium’s robots and a video.

Problem Statement

Consider a group of agents, where we define the state of each agent as . This particular algorithm models each agent with the single-integrator dynamics where is the control input to agent . The rendezvous problem requires the design of a control input such that

\begin{equation} \lim_{t \to \infty} (x_{i} - x_{j}) = 0, ~ \forall ~ i,j = 1,\ldots,N \label{eq:solution} \end{equation}

Solution

A common solution to the rendezvous problem is to let $u_{i}$ be defined using the local interaction rule (e.g., as in [1]). yielding the node-level dynamics

\begin{equation} \dot{x}_{i} = \sum_{j \in N_{i}} (x_{j} - x_{i}) \label{eq:node-level-dynamics} \end{equation}

where represents the neighbors of agent induced by a particular communication topology. For this algorithm, consider the communication topology of the agents to be static and represented by an undirected graph where the following condition holds Then, the node-level dynamics may be re-written as ensemble-level dynamics by combining the agents’ states together into the vector yielding the ensemble-level dynamics where is the graph Laplacian to the graph , and is an identity matrix of the appropriate dimension. Note that refers to the th state variable of agent . This algorithm is known as the consensus algorithm. Using the properties of , we can also show each agent’s final position is given by where is the initial condition of agent . This result solves the problem stated in(\ref{eq:solution}). Interestingly, the agents always meet at the average of the initial conditions. For relevant properties of the graph Laplacian, refer to sources such as [2].

Implementation

Using the previously defined algorithm and the Robotarium’s provided MATLAB interface, we implemented the consensus algorithm in (\ref{eq:node-level-dynamics}). The code snippet below demonstrates the transfer of the consensus algorithm into the Robotarium’s MATLAB API.

for i = 1:N

    % Initialize velocity to zero for each agent.  This allows us to sum
    % over agent i's neighbors
    dx(:, i) = [0 ; 0];

    % Get the topological neighbors of agent i based on the graph
    % Laplacian L
    neighbors = r.getTopNeighbors(i, L);

    % Iterate through agent i's neighbors
    for j = neighbors

        %%% CONSENSUS %%%

        % For each neighbor, calculate appropriate consensus term and
        %add it to the total velocity
        dx(:, i) = dx(:, i) + (x(1:2, j) - x(1:2, i));

        %%% END CONSENSUS %%%
    end
end

Deployment

For the experiment, we selected and (i.e., an undirected cycle graph containing 6 agents). This choice for ensured that the agents remained connected during the experiment. Deploying the consensus algorithm onto the Robotarium yielded the results shown in Figure 1. Note that, due to the physical size of the robots, the agents did not reach the same point.

Fig 1. Physical robots’ trajectories during the deployment of the consensus algorithm onto the Robotarium

References

[1] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” IEEE Trans. Autom. Control, vol. 48, no. 6, pp. 988–1001, Jun. 2003

[2] C. Godsil and G. Royle, Algebraic Graph Theory. Berlin, Germany: Springer, 2001