Emergence via constrained optimization: analysis and experiments with constraint-driven flocking
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
An automation revolution is looming, and the explosive growth of these sophisticated automated systems will only accelerate with the advent of industry 4.0, smart cities, and the internet of things. These systems are characterized as “complex,” but this is a nebulous term. While there is no consensus on what exactly defines a complex system, it is generally understood that they share two characteristics: 1) complex systems consist of agents, which interact with each other and the environment using relatively simple rules, and 2) these interactions lead to emergent behavior, that is, patterns at length and time-scales larger than any of the individual agents. There are many examples of complexity and emergence in our everyday lives, such as flocks of geese, genetic networks, and economies. Given this context, the objective of this dissertation is twofold: to provide short-term benefits for the design and analysis of robotic multi-agent systems, and to enhance our general understanding of complex systems and their emergent behaviors. ☐ This dissertation adopts the view of emergence proposed by English cybernetician W. Ross Ashby in 1962. Ashby argued that large-scale patterns emerge when a multi-agent system is driven into an equilibrium state. This definition of emergence is particularly useful, as it provides a means to rigorously interrogate complex systems using techniques from optimization and dynamical systems. Thus, this dissertation proposes a constraint-driven optimization approach to generate emergence in multi-agent systems, as well as a new technique to solve constrained optimal control problems quickly. The first contribution of this dissertation demonstrates that moving agents to predefined goals, e.g., for a drone light show, is an example of a “medium complexity” emergence problem—one that is challenging to solve by hand but is well within the capabilities of a digital computer. This result is extended in the second contribution, a constraint-driven framework to bring groups of autonomous vehicles into energy-minimizing configuration; this includes highway platooning, aerial V formations, and predator avoidance. This constraint-driven approach has many benefits: 1) it is straightforward to interpret why an agent takes a particular action, 2) the system-level behavior can be guaranteed by examining pairwise agent states, 3) the approach is rigorous and data driven, and 4) agents can arbitrarily enter and leave the system, subject to safety constraints. Finally, the third contribution is a novel technique to generate optimal trajectories in real time. A naive Matlab implementation of the proposed algorithm outperforms two open-source state of the art solvers (OpenOCL, which uses a C++ CasADi implementation, and ICLOCS2) by every metric. ☐ In terms of broader impacts, this dissertation represents another union between complex systems and control theory. The open questions raised by Ashby can be interrogated directly through the engineering design process: emergent behavior is guaranteed when a multi-agent system reaches equilibrium, the “complexity” of a system corresponds to the number of equilibrium points, and the “goodness” of a particular emergent behavior corresponds to how well it achieves the desired outcome. It turns out that dynamical systems, stability, and optimization are a natural language for rigorous discussion of complex systems and emergent behavior.
Description
Keywords
Constraint-driven control, Control systems, Differential flatness, Emergence, Multi-agent systems, Optimization