Multi-Agent Recurrent Rendezvous Using Drive-Based Motivation

Consider a group of people monitoring wildlife in a large area. Each person has a different location where they monitor the nest or den of some local animal, say a songbird. An individual will record the bird, make notes on its behavior, and otherwise gather information. Then, once sufficient information has been gathered, all members of the group rendezvous with each other to compare notes. Then, the group splits up again to gather more information. Abstractly, this is a problem of recurrent rendezvous alternating with designated tasks. In this paper we focus on developing a control scheme to automatically stabilize such a recurrent rendezvous behavior for a system of autonomous mobile robots.

The multi-agent rendezvous problem sits at the intersection of robot motion planning and distributed control. In the problem, multiple autonomous robots must coordinate and arrive at a location in space which is not predefined. There may be constraints on what an agent knows about the space or the other agents. Additional challenges such as obstacles, adversaries, or noise may be present.

The multi-agent rendezvous problem has seen significant attention in recent decades [1, 5, 14, 3], with applications such as coverage and exploration [13, 22], persistent recharging [15, 16], and simultaneous location and mapping (SLAM) [24]. Analyzing rendezvous is typically done using graph based approaches [15, 17] (where one views the agents as nodes in a communication network, and analyzes various graph metrics) and dynamical systems tools [6].

We distinguish two cases of the rendezvous problem. First is the case of one-time rendezvous, or non-recurrent rendezvous. Here the rendezvous problem is solved once the agents reach consensus. That is, if the problem begins at time $t_{0}$, the problem is solved if there is some time $t^{*}>t_{0}$ when the positions of the agents have reached (or are close enough to) a point in the state space (possibly arbitrary). The second is the case of recurrent rendezvous. Here agents must always eventually rendezvous. That is, the recurrent problem is solved if for every time $t>t_{0}$ there exists some later time $t^{*}>t$ when the agents reach a common point in the state space. There is some work on recurrent rendezvous, such as addressing the issue of autonomous vehicles needing to repetitively recharge [15, 16], however most attention is given to the non-recurrent case. In this paper we focus on the recurrent case.

When designing controllers to execute repetitive tasks, one approach is for an individual agent to use a decision making model to coordinate these tasks. Here we consider a task based approach to the problem of persistent multi-agent rendezvous. Task based autonomous behavior has been widely studied [7, 8, 11]: complex behaviors are constructed from smaller, simpler tasks. Each individual task is encoded in a vector field (e.g., going to a target state is encoded as an attracting fixed point on the state space). The goal of the autonomous controller is to then coordinate these tasks to achieve said high-level behavior. Ultimately, this coordination can be framed as a form of decision making, which is a large and active area of research.

An individual in a decision making model has an action space $\mathcal{A}$, and state space $\mathcal{S}$. If $a_{t}\in\mathcal{A}$ and $s_{t}\in\mathcal{S}$ are the action and state at time $t$ we can define the history as the tuple $H_{t}=(s_{0},a_{0},s_{1},\dots,a_{t-1},s_{t})$. A policy $\rho$ is a map $\rho:H_{t}\to a_{t}$. In some cases we have a memory-less policy. That is, a policy that only depends on the current state $s_{t}$. While we have used notation that implies discrete time, this generalizes to the continuous time case in a natural way. For our applications it will be most reasonable to consider the continuous time case, and that will be the assumption from here on.

In our task-based framework an action is choosing which of $n$ tasks to pursue. It is convenient for us to phrase our policy as an optimization problem. We consider an expanded state space $s=(x,v)$ where $x\in\mathbb{R}^{d}$ is our physical state and $v\in\mathbb{R}_{+}^{n}$ is our value state. The value state encodes the relative values of pursuing each of the $n$ tasks. Our policy is then to pick the action which coincides with the task with maximal value. When framing the action/policy/state system as a control system, it is useful to introduce a motivation state $m\in\mathcal{M}$ which tracks the current task being pursued. Here $\mathcal{M}$ is the space of possible motivation states, and it may be discrete or continuous.

Most decision making research reduces the problem to discrete decision states: Given $n$ tasks, pick exactly one to pursue. This can be formulated mathematically. Consider a motivation vector $m\in\{0,1\}^{n}$ such that $m_{i}=1$ iff $\arg\max_{j}(v_{j})=i$, and $m_{j}=0$ otherwise. We call this the discrete motivation case. A natural extension, and one that has been of recent interest, is the continuous motivation case. The difference is that we consider the motivation vector $m$ to live on the $(n-1)$-simplex $\Delta^{n}$, where $\Delta^{n}=\{x\in\mathbb{R}^{n}:x_{i}\geq 0,\sum_{i}x_{i}=1\}$. Then, following the work in [18, 20, 21], we use a pitchfork bifurcation to encode a dynamical operation analogous to the $\arg\max$ operation from the discrete case. Following [20], we term the resulting dynamical system motivation dynamics. Considering a continuous motivation state for our tasks produces interesting dynamics in the control system that are not otherwise seen in the discrete case. Moreover, it is possible to make entire system smooth, allowing for the use of smooth function analysis, as well as direct numerical integration.

The work we present here is complementary to other recent work using bifurcation theory to construct decision-making mechanisms, e.g., [10, 4, 19, 2]. In contrast to these works, here we focus not on the decision-making mechanism itself, but on connecting the mechanism to physically-embedded tasks, i.e., the requirement for the various agents to move and perform rendezvous in response to their decisions.

The main contribution of this paper is to address the persistent rendezvous problem using task-based navigation with a continuous motivation state. In the process, we develop a networked dynamical system that exhibits stable recurrent rendezvous encoded by an attractor. Concretely, our contributions are two-fold. First we develop the multi-agent extension of a control scheme originally developed in [20] and expanded upon in [23]. The scheme utilizes the so-called unfolding pitchfork bifurcation to coordinate agents with binary tasks. We then adapt this framework to the persistent rendezvous problem, and analyze the resulting dynamical system in a highly symmetric case. We derive analytical guarantees of the system behavior, and show that it achieves persistent rendezvous under appropriate conditions. In Theorem 3.7 we consider a limited form of the system and extract a closed-form critical parameter value for the breaking of system deadlock. Then, in Theorem 3.8 we view the full system, and using results from the previous theorem, we prove the existence of such critical parameter values, along with a guaranteed bound for breaking deadlock. Next, by varying parameters $\lambda$ and $\sigma$ (defined below), we characterize distinct regimes of behavior for the system (see Figure 1). Finally we discuss the results and provide a list of further research directions to be considered.

We use the Motivation Dynamics framework [20]. Here, we extend the Motivation Dynamics framework to the $N$-agent case. We assume that each agent $k$ has physical state $x_{k}\in\mathbb{R}^{d}$ and that its physical dynamics are fully actuated, i.e., that $\dot{x}_{k}=u$, with $x_{k},u\in\mathbb{R}^{d}$. We assume that each agent has two tasks, one of which is to travel to a designated location, and the other is to rendezvous with the other agents. The values associated with these two tasks for agent $k$ are encoded in $v_{k}\in\mathbb{R}_{+}^{2}$ The two-task assumption allows us to reduce the motivation space, $\Delta^{2}$, to an interval on the real line. It is convenient to consider the motivation state $m_{k}$ of an agent to live on the interval $[-1,1]$, where each extreme of the interval uniquely corresponds with one of the two tasks. Let the state of agent $k$ be denoted by $\xi_{k}=(x_{k}^{T},m_{k},v_{k}^{T})^{T}$, where $x_{k}\in\mathbb{R}^{d}$ is the agent’s physical location (or configuration), $m_{k}\in[-1,1]$ is the agent’s motivation state, and $v_{k}\in\mathbb{R}_{+}^{2}$ is the agent’s value state. We assume that the agent’s physical dynamics are fully-actuated, i.e., Denote $\Xi$ as the matrix

where $X=\left(x_{1}|\cdots|x_{N}\right)$, $M=(m_{1},\dots,m_{k})$, and $V=\left(v_{1}|\cdots|v_{N}\right)$.

For the time being, we will assume that the agents have two tasks, where their value dynamics are only influenced by their value state and the physical configuration of all agents. In this case agent $k$ is controlled by the closed loop, fully continuous dynamical system

where $\alpha_{k}=(v_{k,1}-v_{k,2})/(v_{k,1}+v_{k,2})$. Compactly we have

and in matrix form

We will also denote the dynamics of the matrices $X,M,V$ by $\dot{X}=f_{X}(X,M)$, $\dot{M}=f_{M}(M,V)$, $\dot{V}=f_{V}(V,X)$.

Assuming $N$ agents and $x_{k}\in\mathbb{R}^{2}$, denote $R$ as the $2\times 2$ rotation matrix given by

We set the designated task locations as $x_{k}^{*}=R^{k-1}u$, where $u=(1,0)^{T}$ (i.e. $N$ symmetrically distributed points on the unit circle). At this point it is prudent to make the change of coordinates $y_{k}=R^{-(k-1)}x_{k}$. Denoting the transformed $X$ matrix by $Y$, this results in

and

Moreover, we will consider symmetric time scales for the motivation and value dynamics. That is, we set $\sigma_{k}=\sigma$ and $\lambda_{k}=\lambda$ for all $k$. Let us set $z_{k}=(y_{k}^{T},m_{k},v_{k}^{T})$ and

Then we may compactly represent our symmetric-case system by the dynamical equation

The fact that this is the symmetric case allows us to utilize a group invariance of the system. First we note that following definition of equivariance for a map.

With equivariance in mind, now we establish a symmetry group for the dynamics (6).

We note that the fixed point subspace of $C_{N}$ is the one generated by matrices $Z$ with all columns the same (i.e. $z_{i}=z_{j}~{}\forall i,j$). We will refer to this subspace as the symmetric subspace. We will see later that said subspace possesses some very interesting properties.

In this paper, we have shown how the motivation dynamics architecture and associated results introduced in [20] can be extended to the multi-agent case. In particular, we have demonstrated the feasibility of using the unfolding pitchfork decision-making mechanism to coordinate recurrent rendezvous tasks between autonomous agents. Moreover, we have shown that the parameters of the multi-agent system (6) can be chosen in such a way as to guarantee that the system does not reach a deadlock state, and that there will always eventually be a rendezvous event. In the language of formal methods [12], our system satisfies the following specification: always ((eventually rendezvous) and (eventually visit designated location)). The connection between the structure of the dynamical system and the discrete specification that it satisfies is beyond the scope of this paper, but is of great interest for future work.

Several interesting research questions follow from the results of this paper. First, in the problem as it is presented in this paper, each agent has full knowledge of the others’ positions. In other words, the communication graph is complete and communication is uncorrupted by noise or delays. The results presented in this paper could naturally be generalized to the case of an incomplete but connected communications graph, or the cases where communication among agents is corrupted by stochastic noise or communication delays. These generalizations should be feasible given standard tools from the distributed consensus literature.

Second, the agents’ tasks may be more subtle than the tasks considered here, where each agent has two tasks: exactly one designated point-attractor task and one rendezvous task where the agents must precisely rendezvous at a point. If approximate rendezvous, e.g., to a neighborhood, is acceptable, what further results might be possible? In the case that there are $M$ point-attractor tasks and $N\neq M$ agents, how can the system automatically distribute these tasks among the agents?

Third, there is a fundamental mathematical question of characterizing the attractor whose existence we postulate in Claim 3.9. It is likely that symmetric bifurcation theory [9] will provide a set of tools to enable this analysis. Answering these questions will push forward knowledge of how the unfolding pitchfork can be used to coordinate high-level autonomous behaviors.