Assignment Graph, Liveness Condition, and Graph-Compatible Lyapunov Function

In this section we define a directed graph $G$ called the assignment graph, in which each vertex is associated with an agent $i$ having position $p_i$ and orientation $\psi_i$ . We then derive the connectivity condition that $G$ must satisfy for the agents to rendezvous. Finally, we relate graph property and rendezvous via the notion of graph-compatible Lyapunov function. The several basic graph properties being used in the discussion can be found in [41].

To rendezvous, agents must move relative to each other in some way. We formalize this relationship as assignment: we say that agent $i$ is assigned to agent $j$ if $j$ is $i$ 's target. We define the assignment graph $G$ in an obvious way: $G$ initially has $n$ vertices, one for each agent, and there is a directed edge $e_{i, j}$ from $i$ to $j$ if and only if agent $i$ is assigned to agent $j$ . The set of edges of $G$ is denoted $E(G)$ . For an edge $e_{i, j}$ , let $\ell_{i,j}$ denote the distance between agents $i,j$ 's positions in $\mathbb{R}^2$ . With the introduction of the assignment graph, we define merging properly as: the merging of agent $i$ into agent $j$ is triggered if

$$\begin{array}{ll} e_{i,j} \in E(G) \quad \textrm{and} \quad \ell_{i,j} \leq \rho. \end{array}$$ (4)

After a merge of agent $i$ reaching agent $j$ , vertex $i$ and edge $e_{i, j}$ are deleted from $G$ . Any edge $e_{k,i}$ (or $e_{i,k}$ ) that existed in $E(G)$ before the merge is replaced by edge $e_{k,j}$ (or $e_{j,k}$ ) , if such an edge does not already exist.

We say that an assignment graph $G$ is connected (or weakly connected) if its underlying undirected graph has a single component. We say that $G$ is live if it has at least one edge. If a graph only has a single vertex, we call it live by definition. It is desirable to maintain liveness in $G$ at all times. If $G$ is not live, then it has more than one vertex but no edges; it is then not possible for the system to rendezvous without additional assumptions. Since liveness is not preserved under merging, we need a stronger property from the initial graph. Assuming that an agent never loses its target prior to merging, this property is captured in the following lemma.

Lemma 1   The assignment graph $G$ is live for all $t\ge 0$ , under arbitrary evolution of the agent positions and merging, if and only if it is connected at time $t=0$ .

PROOF. ``If" A connected graph is live and the connectivity of the graph is preserved under merging. (Indeed, connectivity means that there exists a path from any vertex to any other vertex, and merging vertices does not destroy any paths.)

``Only if" If $G$ is not connected, then it has more than one connected component. By merging we can collapse each connected component to a single point. This results in a graph with more than one vertex and no edges, which is not live. 

By Lemma 1, for a system of $n$ agents to rendezvous, the assignment graph $G$ for the system must have at least $n-1$ edges that connect all the vertices. If a connected graph with $n$ nodes has $n-1$ edges, it is a tree. In particular, in an $n-1$ edge connected assignment graph, all vertices but one have a single outgoing edge, making the graph an intree, a directed acyclic graph in which all maximal directed paths point to a single vertex, its root. The agent at the root of the tree has no assigned target; hence, it does not move by the control law.

Figure 3: An assignment graph, $G$ , with $n$ edges of which the underlying undirected graph is connected and contains a cycle (polygon) that encloses the shaded area.

The condition to guarantee rendezvous for an intree assignment graph will turn out to be quite trivial. However, such a formation is asymmetric in the sense that exactly one of the agents (the root) has no assignment. Such an assignment is not possible to achieve in a decentralized manner. The simplest symmetrical assignment graph $G$ has $n$ assignments, one for each agent. We do not investigate the case in which one agent has more than one assignment at a given instant, since a more complicated control protocol will be required. Let us denote the assignment graph of our interest as single-target assignment graph. When $G$ has $n$ edges, the extra edge induces a cycle; therefore $G$ has a single cycle on which each agent is assigned to the next one. The assignment also guarantees that any agent not on a cycle has a directed path to agents on the cycle (see Fig. 3). The behavior of the agents on the cycle is not affected by any agent not on the cycle. As we shall see later, this observation plays an important role in obtaining sufficient conditions for guaranteed rendezvous.

Given an assignment graph $G$ , we may define a function of the form

$$V = \sum_{e_{i,j} \in E(G)} V_{i,j},$$ (5)

in which $V_{i,j}$ depends only on the states of agents $i$ and $j$ . We say such a function is a graph-compatible Lyapunov function if it has the property that $V_{i,j} \ge 0$ and $V_{i,j} = 0$ iff $\ell_{i,j} = 0$ for all pairs of $i,j$ . For such a Lyapunov function $V$ , we say it is rendezvous positive definite iff $V = 0$ when all agents are in the same (unspecified) location, and $V > 0$ otherwise. This leads to:

Lemma 2   A graph-compatible Lyapunov function $V$ is rendezvous positive definite if and only if its assignment graph $G$ is connected.

PROOF. ``If" It is clear that $V\ge 0$ . Suppose that $G$ is connected and $V = 0$ . Since $G$ contains a path connecting all agents, and since the lengths of all edges in this path must be zero, we have rendezvous.

``Only if" If $G$ is not connected, then it has more than one connected component. If each connected component collapses to a single point, $V$ becomes zero, even though we do not have rendezvous of all agents.  As an alternative to the above direct proof, we could deduce Lemma 2 from Lemma 1: by liveness, the graph will have at least one edge (and thus $V$ will be positive) as long as rendezvous does not occur.