From pedestrians to Kuramoto oscillators, interactions between agents govern how dynamical systems evolve in space and time. Discovering how these agents relate to each other has the potential to improve our understanding of the often complex dynamics that underlie these systems. Recent works learn to categorize relationships between agents based on observations of their physical behavior. These approaches model relationship categories as outcomes of a categorical distribution which is limiting and contrary to real-world systems, where relationship categories often intermingle and interact. In this work, we introduce a level of abstraction between the observable behavior of agents and the latent categories that determine their behavior. To do this, we learn a mapping from agent observations to agent preferences for a set of latent categories. The learned preferences and inter-agent proximity are integrated in a nonlinear opinion dynamics model, which allows us to naturally identify mutually exclusive categories, predict an agent’s evolution in time, and control an agent’s behavior. Through extensive experiments, we demonstrate the utility of our model for learning interpretable categories, and the efficacy of our model for long-horizon trajectory prediction.

Artistic creation is often seen as a uniquely human endeavor, yet robots bring distinct advantages to music-making, such as precise tempo control, unpredictable rhythmic complexities, and the ability to coordinate intricate human and robot performances. While many robotic music systems aim to mimic human musicianship, our work emphasizes the unique strengths of robots, resulting in a novel multi-robot performance instrument called the Beatbots, capable of producing music that is challenging for humans to replicate using current methods. The Beatbots were designed using an “informed prototyping“ process, incorporating feedback from three musicians throughout development. We evaluated the Beatbots through a live public performance, surveying participants$(N=28)$to understand how they perceived and interacted with the robotic performance. Results show that participants valued the playfulness of the experience, the aesthetics of the robot system, and the unconventional robot-generated music. Expert musicians and non-expert roboticists demonstrated especially positive mindset shifts during the performance, although participants across all demographics had favorable responses. We propose design principles to guide the development of future robotic music systems and identify key robotic music affordances that our musician consultants considered particularly important for robotic music performance.

Non-cooperative interactions commonly occur in multi-agent scenarios such as car racing, where an ego vehicle can choose to overtake the rival, or stay behind it until a safe overtaking “corridor” opens. While an expert human can do well at making such time-sensitive decisions, autonomous agents are incapable of rapidly reasoning about complex, potentially conflicting options, leading to suboptimal behaviors such as deadlocks. Recently, the nonlinear opinion dynamics (NOD) model has proven to exhibit fast opinion formation and avoidance of decision deadlocks. However, NOD modeling parameters are oftentimes assumed fixed, limiting their applicability in complex and dynamic environments. It remains an open challenge to determine such parameters automatically and adaptively, accounting for the ever-changing environment. In this work, we propose for the first time a learning-based and game-theoretic approach to synthesize a Neural NOD model from expert demonstrations, given as a dataset containing (possibly incomplete) state and action trajectories of interacting agents. We demonstrate Neural NOD's ability to make fast and deadlock-free decisions in a simulated autonomous racing example. We find that Neural NOD consistently outperforms the state-of-the-art data-driven inverse game baseline in terms of safety and overtaking performance.

We propose, analyze, and experimentally verify a new proactive approach for robot social navigation driven by the robot's “opinion” for which way and by how much to pass human movers crossing its path. The robot forms an opinion over time according to nonlinear dynamics that depend on the robot's observations of human movers and its level of attention to these social cues. For these dynamics, it is guaranteed that when the robot's attention is greater than a critical value, deadlock in decision making is broken, and the robot rapidly forms a strong opinion, passing each human mover even if the robot has no bias nor evidence for which way to pass. We enable proactive rapid and reliable social navigation by having the robot grow its attention across the critical value when a human mover approaches. With human-robot experiments we demonstrate the flexibility of our approach and validate our analytical results on deadlock-breaking. We also show that a single design parameter can tune the trade-off between efficiency and reliability in human-robot passing. The new approach has the additional advantage that it does not rely on a predictive model of human behavior.

We study the problem of multi-agent control of a dynamical system with known dynamics and adversarial disturbances. Our study focuses on optimal control without centralized precomputed policies, but rather with adaptive control policies for the different agents that are only equipped with a stabilizing controller. We give a reduction from any (standard) regret minimizing control method to a distributed algorithm. The reduction guarantees that the resulting distributed algorithm has low regret relative to the optimal precomputed joint policy. Our methodology involves generalizing online convex optimization to a multi-agent setting and applying recent tools from nonstochastic control derived for a single agent. We empirically evaluate our method on a model of an overactuated aircraft. We show that the distributed method is robust to failure and to adversarial perturbations in the dynamics.

This paper presents an algorithm for a team of mobile robots to simultaneously learn a spatial field over a domain and spatially distribute themselves to optimally cover it. Drawing from previous approaches that estimate the spatial field through a centralized Gaussian process, this work leverages the spatial structure of the coverage problem and presents a decentralized strategy where samples are aggregated locally by establishing communications through the boundaries of a Voronoi partition. We present an algorithm whereby each robot runs a local Gaussian process calculated from its own measurements and those provided by its Voronoi neighbors, which are incorporated into the individual robot's Gaussian process only if they provide sufficiently novel information. The performance of the algorithm is evaluated in simulation and compared with centralized approaches.

We propose a game-theoretic multi-robot task allocation framework that enables a large team of robots to optimally allocate tasks in dynamically changing environments. As our main contribution, we design a decision-making algorithm that defines how the robots select tasks to perform and how they repeatedly revise their task selections in response to changes in the environment. Our convergence analysis establishes that the algorithm enables the robots to learn and asymptotically achieve the optimal stationary task allocation. Through experiments with a multi-robot trash collection application, we assess the algorithm’s responsiveness to changing environments and resilience to failure of individual robots.

The cooperative bandit problem is increasingly becoming relevant due to its applications in large-scale decision-making. However, most research for this problem focuses exclusively on the setting with perfect communication, whereas in most real-world distributed settings, communication is often over stochastic networks, with arbitrary corruptions and delays. In this paper, we study cooperative bandit learning under three typical real-world communication scenarios, namely, (a) message-passing over stochastic time-varying networks, (b) instantaneous reward-sharing over a network with random delays, and (c) message-passing with adversarially corrupted rewards, including byzantine communication. For each of these environments, we propose decentralized algorithms that achieve competitive performance, along with near-optimal guarantees on the incurred group regret as well. Furthermore, in the setting with perfect communication, we present an improved delayed-update algorithm that outperforms the existing state-of-the-art on various network topologies. Finally, we present tight network-dependent minimax lower bounds on the group regret. Our proposed algorithms are straightforward to implement and obtain competitive empirical performance.

Recent approaches for modelling dynamics of physical systems with neural networks enforce Lagrangian or Hamiltonian structure to improve prediction and generalization. However, when coordinates are embedded in high-dimensional data such as images, these approaches either lose interpretability or can only be applied to one particular example. We introduce a new unsupervised neural network model that learns Lagrangian dynamics from images, with interpretability that benefits prediction and control. The model infers Lagrangian dynamics on generalized coordinates that are simultaneously learned with a coordinate-aware variational autoencoder (VAE). The VAE is designed to account for the geometry of physical systems composed of multiple rigid bodies in the plane. By inferring interpretable Lagrangian dynamics, the model learns physical system properties, such as kinetic and potential energy, which enables long-term prediction of dynamics in the image space and synthesis of energy-based controllers.

Ant colonies regulate activity in response to changing conditions without using centralized control. Desert harvester ant colonies forage for seeds, and regulate foraging to manage a tradeoff between spending and obtaining water. Foragers lose water while outside in the dry air, but ants obtain water by metabolizing the fats in the seeds they eat. Previous work shows that the rate at which an outgoing forager leaves the nest depends on its recent rate of brief antennal contacts with incoming foragers carrying food. We examine how this process can yield foraging rates that are robust to uncertainty and responsive to temperature and humidity across minute-to-hour timescales. To explore possible mechanisms, we develop a low-dimensional analytical model with a small number of parameters that captures observed foraging behavior. The model uses excitability dynamics to represent response to interactions inside the nest and a random delay distribution to represent foraging time outside the nest. We show how feedback from outgoing foragers returning to the nest stabilizes the incoming and outgoing foraging rates to a common value determined by the volatility of available foragers. The model exhibits a critical volatility above which there is sustained foraging at a constant rate and below which foraging stops. To explain how foraging rates adjust to temperature and humidity, we propose that foragers modify their volatility after they leave the nest and become exposed to the environment. Our study highlights the importance of feedback in the regulation of foraging activity and shows how modulation of volatility can explain how foraging activity responds to conditions and varies across colonies. Our model elucidates the role of feedback across many timescales in collective behavior, and may be generalized to other systems driven by excitable dynamics, such as neuronal networks.

We contribute to the development of a systematic means to infer features of human decision-making from behavioral data. Motivated by the common use of softmax selection in models of human decision-making, we study the maximum-likelihood (ML) parameter estimation problem for softmax decision-making models with linear objective functions. We present conditions under which the likelihood function is convex. These allow us to provide sufficient conditions for convergence of the resulting ML estimator and to construct its asymptotic distribution. In the case of models with nonlinear objective functions, we show how the estimator can be applied by linearizing about a nominal parameter value. We apply the estimator to fit the stochastic Upper Credible Limit (UCL) model of human decision-making to human subject data. The fits show statistically significant differences in behavior across related, but distinct, tasks.

In this paper, we present a formal model of human decision making in explore-exploit tasks using the context of multiarmed bandit problems, where the decision maker must choose among multiple options with uncertain rewards. We address the standard multiarmed bandit problem, the multiarmed bandit problem with transition costs, and the multiarmed bandit problem on graphs. We focus on the case of Gaussian rewards in a setting where the decision maker uses Bayesian inference to estimate the reward values. We model the decision maker's prior knowledge with the Bayesian prior on the mean reward. We develop the upper-credible-limit (UCL) algorithm for the standard multiarmed bandit problem and show that this deterministic algorithm achieves logarithmic cumulative expected regret, which is optimal performance for uninformative priors. We show how good priors and good assumptions on the correlation structure among arms can greatly enhance decision-making performance, even over short time horizons. We extend to the stochastic UCL algorithm and draw several connections to human decision-making behavior. We present empirical data from human experiments and show that human performance is efficiently captured by the stochastic UCL algorithm with appropriate parameters. For the multiarmed bandit problem with transition costs and the multiarmed bandit problem on graphs, we generalize the UCL algorithm to the block UCL algorithm and the graphical block UCL algorithm, respectively. We show that these algorithms also achieve logarithmic cumulative expected regret and require a sublogarithmic expected number of transitions among arms. We further illustrate the performance of these algorithms with numerical examples.

Flocks of starlings exhibit a remarkable ability to maintain cohesion as a group in highly uncertain environments and with limited, noisy information. Recent work demonstrated that individual starlings within large flocks respond to a fixed number of nearest neighbors, but until now it was not understood why this number is seven. We analyze robustness to uncertainty of consensus in empirical data from multiple starling flocks and show that the flock interaction networks with six or seven neighbors optimize the trade-off between group cohesion and individual effort. We can distinguish these numbers of neighbors from fewer or greater numbers using our systems-theoretic approach to measuring robustness of interaction networks as a function of the network structure, i.e., who is sensing whom. The metric quantifies the disagreement within the network due to disturbances and noise during consensus behavior and can be evaluated over a parameterized family of hypothesized sensing strategies (here the parameter is number of neighbors). We use this approach to further show that for the range of flocks studied the optimal number of neighbors does not depend on the number of birds within a flock; rather, it depends on the shape, notably the thickness, of the flock. The results suggest that robustness to uncertainty may have been a factor in the evolution of flocking for starlings. More generally, our results elucidate the role of the interaction network on uncertainty management in collective behavior, and motivate the application of our approach to other biological networks.

With a principled methodology for systematic design of human–robot decision-making teams as a motivating goal, we seek an analytic, model-based description of the influence of team and network design parameters on decision-making performance. Given that there are few reliably predictive models of human decision making, we consider the relatively well-understood two-alternative choice tasks from cognitive psychology, where individuals make sequential decisions with limited information, and we study a stochastic decision-making model, which has been successfully fitted to human behavioral and neural data for a range of such tasks. We use an extension of the model, fitted to experimental data from groups of humans performing the same task simultaneously and receiving feedback on the choices of others in the group. First, we show how the task and model can be regarded as a Markov process. Then, we derive analytically the steady-state probability distributions for decisions and performance as a function of model and design parameters such as the strength and path of the social feedback. Finally, we discuss application to human–robot team and network design and next steps with a multirobot testbed.

Integrating robotic agents into animal groups creates significant opportunities for advancing experimental investigations of collective animal behavior. In the case of fish schooling, new insights into processes such as collective decision making and leadership have been made in recent experiments in which live fish were interacting with robotic fish driven along preplanned paths. We introduce a new cyber–physical implementation that enables robotic fish to use real-time feedback to control their motion in response to live fish and other environmental features. Each robotic fish is magnetically connected to, and thus moved by, a wheeled robot underneath the tank. Real-time image processing of a video stream from an overhead camera provides measurements of both the robotic fish and the live fish moving together in the tank. Feedback responses computed from these measurements are communicated to the robotic fish using Bluetooth. We show results of demonstrations and discuss possibilities that our implementation affords for new kinds of behavioral experiments with fish schools.

From bird flocks to fish schools, animals move together and respond to their environment in remarkable ways; their natural collective motion patterns appear well choreographed and their collective survival strategies seem ingenious. Animal group behaviors inspire design for mobile multi-agent robotic systems, where demanding cooperative sensing tasks, such as exploration and sampling in an uncertain and dynamic environment, find their analogue in natural aggregation behaviors, such as foraging and feeding. However, bio-inspiration of this kind is not transparent because the natural “design” mechanisms are not well understood. The joint challenge is to explain the enabling mechanisms in animal groups and to define provable mechanisms for robotic groups. And this suggests an integrated approach: formal bio-inspired models and analysis tools derived to synthesize collective robotic motion and exploration can be used to evaluate design hypotheses for animal groups; subsequent revelations from the biology will in turn inspire new approaches for robotic systems. I will discuss mobile robot and animal networks using a common mathematical framework that builds on coupled oscillator dynamics and communication graphs. I will describe application to an adaptive ocean sampling network, a successful, recent field experiment in Monterey Bay, CA and an investigation of dynamics and decision-making in fish schools.

This paper addresses the design of mobile sensor networks for optimal data collection. The development is strongly motivated by the application to adaptive ocean sampling for an autonomous ocean observing and prediction system. A performance metric, used to derive optimal paths for the network of mobile sensors, defines the optimal data set as one which minimizes error in a model estimate of the sampled field. Feedback control laws are presented that stably coordinate sensors on structured tracks that have been optimized over a minimal set of parameters. Optimal, closed-loop solutions are computed in a number of low-dimensional cases to illustrate the methodology. Robustness of the performance to the influence of a steady flow field on relatively slow-moving mobile sensors is also explored

We prove a convergent strategy for a group of mobile sensors to generate contour plots, i.e., to automatically detect and track level curves of a scalar field in the plane. The group can consist of as few as four mobile sensors, where each sensor can take only a single measurement at a time. The shape of the formation of mobile sensors is determined to minimize the least mean square error in the estimates of the scalar field and its gradient. The algorithm to generate a contour plot is based on feedback control laws for each sensor platform. The control laws serve two purposes: to guarantee that the center of the formation moves along one level curve at unit speed; and to stabilize the shape of the formation. We prove that both goals can be achieved asymptotically. We show simulation results that illustrate the performance of the control laws in noisy environments.

The dynamic window approach (DWA) is a well-known navigation scheme developed by Fox et al. and extended by Brock and Khatib. It is safe by construction, and has been shown to perform very efficiently in experimental setups. However, one can construct examples where the proposed scheme fails to attain the goal configuration. What has been lacking is a theoretical treatment of the algorithm's convergence properties. Here we present such a treatment by merging the ideas of the DWA with the convergent, but less performance-oriented, scheme suggested by Rimon and Koditschek. Viewing the DWA as a model predictive control (MPC) method and using the control Lyapunov function (CLF) framework of Rimon and Koditschek, we draw inspiration from an MPC/CLF framework put forth by Primbs to propose a version of the DWA that is tractable and convergent.

In this paper, we present an approach to obstacle avoidance for a group of unmanned vehicles moving in formation. The goal of the group is to move through a partially unknown environment with obstacles and reach a destination while maintaining the formation. We address this problem for a class of dynamic unicycle robots. Using Input-to-State Stability we combine a general class of formation-keeping control schemes with a new dynamic window approach to obstacle avoidance in order to guarantee safety and stability of the formation as well as convergence to the goal position. An important part of the proposed approach can be seen as a formation extension of the configuration space obstacle concept. We illustrate the method with a challenging example.

The dynamic window approach is a well known navigation scheme developed by Fox et. al. (1997) and extended by Brock and Khatib (1999). It is safe by construction and has been shown to perform very efficiently in experimental setups. However, one can construct examples where the proposed scheme fails to attain the goal configuration. What has been lacking is a theoretical treatment of the algorithm's convergence properties. A first step towards such a treatment was previously presented by the authors (2002). Here we continue that work with a computationally tractable algorithm resulting from a careful discretization of the optimal control problem of the previous paper and a way to construct a continuous navigation function. Inspired by the similarities between the dynamic window approach and the control Lyapunov function and receding horizon control synthesis put forth by Primbs et. al. (1999) we propose a version of the dynamic window approach that is tractable and provably convergent.

Obtains feedback stabilization of an inverted pendulum on a rotor arm by the "method of controlled Lagrangians". This approach involves modifying the Lagrangian for the uncontrolled system so that the Euler-Lagrange equations derived from the modified or "controlled" Lagrangian describe the closed-loop system. For the closed-loop equations to be consistent with available control inputs, the modifications to the Lagrangian must satisfy "matching" conditions. The pendulum on a rotor arm requires an interesting generalization of our earlier approach which was used for systems such as a pendulum on a cart.