Multi-Agent Decision-Making in Design

By Paul Davis

Naomi Ehrich Leonard of Princeton University and her colleagues employ a bold approach when designing controls for multi-agent systems. “[We use] the tools of nonlinear dynamics to connect collective decision-making in animal groups with the design of collective decision-making in robotic groups,” she says. For example, she asks if capturing such collective behavior could frame the development of a control system enabling turbines in a wind farm to respond collectively, similarly to a flock of birds. Could they react to changes in wind direction, given the constraints of their limited sensing, communication, and computation?

Instead of attempting to capture the system’s essential physical properties, Leonard and her collaborators aim for a pitchfork bifurcation: the fundamental mathematical property of a multi-party decision-making dynamical system (see Figure 1a). The handle of a stable pitchfork bifurcation diagram represents deadlock; the twin forks that spring from it as the decision parameter changes signify the choices competing to attract consensus. The tools of singularity theory allow designers to “translate from nature to design and back again,” Leonard says.

She adds that the systematic translation of the physical mechanisms that explain animal behavior to a “bio-inspired design methodology” is difficult. This is because most animal behavior studies are empirical rather than model-based, use simulation models that are not easily generalized, or rely on mean-field behavior that fails to reveal the effects of heterogeneity or system structure. Despite these challenges, Leonard and her team have identified the fundamentals of bio-inspired design for some remarkable examples of collective decision-making, such as that of house-hunting honeybees. After the birth of a new queen, the old queen and about half of her fellow bees abandon their hive in search of a new nest. Scout bees set off to investigate suitable nest sites. They report the direction and distance of sites that they find, promoting the sites’ qualities with a sophisticated “waggle-dance” while competitors try to stop them with head butts (see Figure 2). The house-hunting swarm reacts efficiently to the scouts when choosing the best site; the swarm can even reliably break ties between sites of near-equal value, in contrast to the befuddled house hunters on reality television.

To begin quantifying these ideas, Leonard explores a pair of differential equations for the fraction of the swarm preferring either site \(A\) or \(B\). Figure 3 illustrates the transitions in this dynamic mixing model that lead to one possible steady-state outcome—a quorum committed to \(B\) with the remaining few either committed to \(A\) or undecided \(U\)—when site \(B\) is more valuable than \(A\). In both the model and in nature, the swarm chooses the better site.

There are three possible outcomes in case of a tie in the value \(v\) of two sites: a lasting tie or a choice between one of the two locations (see Figure 4). The difference between a tie and a decision depends on the strength of the scouts’ commitment to their preferred sites. A tie’s steady-state, which occurs when an equal number of scouts vote for \(A\) as for \(B\), changes from stable to unstable when the bifurcation parameter \(\sigma\)—the strength of the stop signal, in this case the head butts—delivered to a scout for the other site increases from \(0.2\) to \(5\).

Figure 5 summarizes the honeybees’ value-sensitive decision-making when a classic pitchfork bifurcation governs the stop signal’s response. If the shared value of the two sites is relatively small, the scouts may wait for a third, better option or send a more intense stop signal  and make a stronger commitment to render a tie unstable and force a stable decision for one site or the other.

This value-sensitive decision-making is also robust to perturbations in system parameters. Figure 1a shows the original pitchfork bifurcation for sites of equal value as the stop signal increases; 1b portrays the qualitatively similar diagram with saddle node bifurcation for sites of fixed, slightly different values; and 1c depicts the behavior as the difference in the values of the sites varies for a fixed stop signal. Note the hysteresis in Figure 1c as the difference between the sites’ values passes through zero. Instead of a sudden flip, the original choice persists until the difference in value becomes too large to ignore.

How might these ideas extend to increasingly realistic multi-agent systems with more heterogeneous agents and interconnections? For example, some agents may have pre-existing preferences or access to other external information. Or perhaps some bees are unable to see the waggle dance. Can the stop signal serve as a control input? Can such agents choose unanimously and robustly between competing choices?

Classic singularity theory for dynamical systems offers an answer through the pitchfork bifurcation’s deadlock-or-decision property in Figure 1a. An agent’s decision is positive for choice \(A\) and negative for \(B\); at consensus, all agents’ decision variables are equal. The sum of the individuals’ decision variables yields the collective decision.

To formulate a model, suppose agent \(i\)'s opinion \(x_i\) changes in response to external information (positive, negative, or zero); negative self-feedback; and positive, weighted, saturating “social” feedback from agents with whom it communicates. The social feedback is weighted by a control variable — a generalization of the stop signal. Critically, the (negative) sum of other agents’ influence weights on a given agent is the latter’s self-feedback factor; that is, an individual bee’s opinion is influenced by a weighted sum of the differences between its opinion and a scaling—according to the control variable—of the saturating opinions of its neighbors in the network.

When the control variable is unity and the system is linearized about zero (no agent has an opinion), the system reduces to \(\dot x =-Lx\), where \(L\) is the social network’s rank-deficient Laplacian (or admittance) matrix. Network types might regard an agent’s opinion as the potential \(x_i\) at its node. They might also conclude that the linearized system has a zero eigenvalue because a version of Kirchhoff’s Voltage Law holds.

“We can create bifurcation by design,” Leonard says. If the control variable is slightly bigger than unity, the first eigenvalue is positive and the steady-state undecided outcome—in which no agent has an opinion—is destabilized. As the control variable increases, a decision is taken. Furthermore, because “the center manifold is tangent to the consensus manifold, we get unanimity by design,” Leonard explains.

Additional analysis reveals the effects of information and network asymmetry, explores value-sensitive decision-making, and builds a framework for feedback control of the bifurcation parameter (i.e., avoiding a deadlock among bees if they reach no consensus on a good potential nesting site).

How can humans design multi-agent control systems that match the performance of Mother Nature’s networks among animals? Leonard’s answer is to design a network using singularity theory to organize the agents’ decision-making — bifurcation by design.

---

Leonard delivered an invited lecture on this topic at the 2017 SIAM Annual Meeting. The presentation is available from SIAM either as slides with synchronized audio or a PDF of slides only.

References
[1] Pais, D., Hogan, P.M., Schlegel, T., Franks, N.R., Leonard, N.E., & Marshall, J.A.R. (2013). A Mechanism for Value-Sensitive Decision-Making. PLoS ONE, 8(9), e73216.

Further Reading
Gray, R., Franci, A., Srivastava, V., & Leonard, N.E. (2018). Multiagent Decision-Making Dynamics Inspired by Honeybees. IEEE Trans. Cont. Net. Syst., 5(2), 793-806.

Paul Davis is professor emeritus of mathematical sciences at Worcester Polytechnic Institute.