Tools from control and dynamical systems have proven valuable for analyzing and developing optimization methods. In this paper, we establish rigorous theoretical foundations for using feedback linearization—a well-established nonlinear control technique—to solve constrained optimization problems. For equality-constrained optimization, we establish global convergence rates to first-order Karush-Kuhn-Tucker (KKT) points and uncover the close connection between the FL method and the Sequential Quadratic Programming (SQP) algorithm. Building on this relationship, we extend the FL approach to handle inequality-constrained problems. Furthermore, we introduce a momentum-accelerated feedback linearization algorithm and provide a rigorous convergence guarantee.

Space-air-ground integrated networks (SAGINs) will play a pivotal role in 6G communication systems. They are considered a promising technology for enhancing network capacity in densely populated urban areas and extending connectivity to rural regions. However, the complex, multilayered, and heterogeneous nature of SAGINs demands an innovative approach to designing their multi-tier associations. In this context, we propose a modeling of the SAGINs association problem using multi-sided matching theory. Our objective is to devise a reliable, asynchronous, and fully distributed approach that associates nodes across the layers to maximize the total end-to-end rate of the assigned agents. To achieve this, our problem is formulated as a multi-sided many-to-one matching game. We introduce a randomized matching algorithm with minimal information exchange. The algorithm is shown to reach an efficient and stable association between nodes in adjacent layers. Simulation results show that our proposed approach yields significant gains compared to both greedy and distance-based algorithms,

The framework of multi-agent learning explores the dynamics of how an agent's strategies evolve in response to the evolving strategies of other agents. Of particular interest is whether or not agent strategies converge to well known solution concepts such as Nash Equilibrium (NE). In "higher order'' learning, agent dynamics include auxiliary states that can capture phenomena such as path dependencies. We introduce higher-order gradient play dynamics that resemble projected gradient ascent with auxiliary states. The dynamics are "payoff based'' and "uncoupled'' in that each agent's dynamics depend on its own evolving payoff and has no explicit dependence on the utilities of other agents. We first show that for any specific game with an isolated completely mixed-strategy NE, there exist higher-order gradient play dynamics that lead (locally) to that NE, both for the specific game and nearby games with perturbed utility functions. Conversely, we show that for any higher-order gradient play dynamics, there exists a game with a unique isolated completely mixed-strategy NE for which the dynamics do not lead to NE. Finally, we show that convergence to the mixed-strategy equilibrium in coordination games, comes at the expense of the dynamics being inherently internally unstable.

This work considers the deployment of unmanned aerial vehicles (UAVs) over a predefined area to serve a number of ground users. Due to the heterogeneous nature of the network, the UAVs may cause severe interference to the transmissions of each other. Hence, a judicious design of the user-UAV association and UAV locations is desired. A potential game is defined where the players are the UAVs. The potential function is the total sum rate of the users. The agents' utility in the potential game is their marginal contribution to the global welfare or their so-called wonderful life utility. A game-theoretic learning algorithm, binary log-linear learning (BLLL), is then applied to the problem. Given the potential game structure, a consequence of our utility design, the stochastically stable states using BLLL are guaranteed to be the potential maximizers. Hence, we optimally solve the joint user-UAV association and 3-D-location problem. Next, we exploit the submodular features of the sum rate function for a given configuration of UAVs to design an efficient greedy algorithm. Despite the simplicity of the greedy algorithm, it comes with a performance guarantee of 1-1/e of the optimal solution. To further reduce the number of iterations, we propose another heuristic greedy algorithm that provides very good results. Our simulations show that, in practice, the proposed greedy approaches achieve significant performance in a few iterations.

Recent advances in sensing, communication, and computing technologies have enabled the use of multirobot systems for practical applications such as surveillance, area mapping, and search and rescue. For such systems, a major challenge is to design decision rules that are real-time-implementable, require local information only, and guarantee some desired global performance. Distributed optimization provides a framework for designing such local decision-making rules for multirobot systems. In this article, we present a collection of selected results for distributed optimization for robot networks. We will focus on two special classes of problems: 1) real-time path planning for multirobot systems and 2) self-organization in multirobot systems using game-theoretic approaches. For multirobot path planning, we will present some recent approaches that are based on approximately solving distributed optimization problems over continuous and discrete domains of actions. The main idea underlying these approaches is that a variety of path planning problems can be formulated as convex optimization and submodular minimization problems over continuous and discrete action spaces, respectively. To generate local update rules that are efficiently implementable in real time, these approaches rely on approximate solutions to the global problems that can still guarantee some level of desired global performance. For game-theoretic self-organization, we will present a sampling of results for area coverage and real-time target assignment. In these results, the problems are formulated as games, and online updating rules are designed to enable teams of robots to achieve the collective objective in a distributed manner.

We present a complete design and implementation of a system that consists of multiple quadrotors playing capture the flag game. Our main contributions in this work include a custom built quadrotor platform, an efficient implementation of a distributed trajectory planning algorithm, and a WiFi based communication infrastructure. In our design, we equip the quadrotors with autopilot modules for low level control. Moreover, we install low power computing modules for implementing the distributed trajectory planning algorithm online. Furthermore, we develop a communication infrastructure to enable coordination among the quadrotors, which is required for computing a suboptimal control action in real time. The interactions among all the hardware and software components are managed at a higher level by Robot Operating System (ROS). To test the performance of the system, we select a motivating setup of capture the flag game, which is an adversarial game played between two teams of agents called attack and defense. The system is initially simulated in the Gazebo robot simulator with software in the loop. Finally, the complete system is tested and the flight testing results are presented.

In this paper, a new sensing device that can simultaneously monitor traffic congestion and urban flash floods is presented. This sensing device is based on the combination of passive infrared sensors (PIRs) and ultrasonic rangefinder, and is used for real-time vehicle detection, classification, and speed estimation in the context of wireless sensor networks. This framework relies on dynamic Bayesian Networks to fuse heterogeneous data both spatially and temporally for vehicle detection. To estimate the speed of the incoming vehicles, we first use cross correlation and wavelet transform-based methods to estimate the time delay between the signals of different sensors. We then propose a calibration and self-correction model based on Bayesian Networks to make a joint inference by all sensors about the speed and the length of the detected vehicle. Furthermore, we use the measurements of the ultrasonic and the PIR sensors to perform vehicle classification. Validation data (using an experimental dual infrared and ultrasonic traffic sensor) show a 99% accuracy in vehicle detection, a mean error of 5 kph in vehicle speed estimation, a mean error of 0.7m in vehicle length estimation, and a high accuracy in vehicle classification. Finally, we discuss the computational performance of the algorithm, and show that this framework can be implemented on low-power computational devices within a wireless sensor network setting. Such decentralized processing greatly improves the energy consumption of the system and minimizes bandwidth usage.

Multirotors micro aerial vehicles (UAV) have become a standard platform in robotics and control research related to algorithmic development as well as design innovation. Custom-built designs based on open-source architecture and off-the-shelf components are attractive for researchers due to low cost and easy rapid prototyping. Hardware selection and integration is usually based on heuristics. Building a realistic quadcopter simulator requires accurate modeling and knowledge of its dynamics and the effect of each component on that. Often, moving from simulation to actual experiment is a challenging task due to the huge dynamical differences when working with the real system. The presented work aims to strengthen the bridge between simulations and actual system through an automated CAD based modeling software system that generates realistic models mathematically and visually for Matlab Simscape physics simulation and visualization utilizing Solidworks API, smart mating techniques and dynamical analysis. A proof of concept application with user friendly interface is built for Windows OS and the system components are further illustrated.

We consider a two-sided one-to-one abstract matching problem with a defined notion of pairwise stability. The formulated problem is shown to encompass the ordinal and cardinal utility markets. We propose a distributed blind matching algorithm (BLMA) to solve the problem. The BLMA is characterized by random activations of agents, and by generic negotiation and aspiration (utility) update processes. We prove that the solution produced by the BLMA will converge to an ϵ-pairwise stable, equivalently ϵ-core, outcome with probability one. We then consider three BLMA applications in cognitive radio networks. We propose a simple BLMA negotiation and aspiration update dynamic to produce an ϵ-pairwise stable solution for the case of quasi-convex and quasi-concave utilities. In the case of more general utility forms, we show another BLMA process to provide equilibrium. We also consider the use of the BLMA in an ordinal utility market. In all applications of the BLMA, we impose a limited information exchange in the network so that agents can only calculate their own utilities, but no information is available about the utilities of any other user in the network.

We study a susceptible-infected-susceptible epidemic process over a static contact network where the nodes have partial information about the epidemic state. They react by limiting their interactions with their neighbors when they believe the epidemic is currently prevalent. A node's awareness is weighted by the fraction of infected neighbors in their social network, and a global broadcast of the fraction of infected nodes in the entire network. The dynamics of the benchmark (no awareness) and awareness models are described by discrete-time Markov chains, from which mean-field approximations (MFAs) are derived. The states of the MFA are interpreted as the nodes' probabilities of being infected. We show a sufficient condition for the existence of a “metastable,” or endemic, state of the awareness model coincides with that of the benchmark model. Furthermore, we use a coupling technique to give a full stochastic comparison analysis between the two chains, which serves as a probabilistic analog to the MFA analysis. In particular, we show that adding awareness reduces the expectation of any epidemic metric on the space of sample paths, e.g., eradication time or total infections. We characterize the reduction in expectations in terms of the coupling distribution. In simulations, we evaluate the effect social distancing has on contact networks from different random graph families (geometric, Erdos-Rényi, and scale-free random networks).

We consider a cognitive radio network where secondary users (SUs) are allowed access time to the spectrum belonging to the primary users (PUs) provided that they relay primary messages. PUs and SUs negotiate over allocations of the secondary power that will be used to relay PU data. We formulate the problem as a generalized assignment market to find an epsilon pairwise stable matching. We propose a distributed blind matching algorithm (BLMA) to produce the pairwise-stable matching plus the associated power allocations. We stipulate a limited information exchange in the network so that agents only calculate their own utilities but no information is available about the utilities of any other users in the network. We establish convergence to epsilon pairwise stable matchings in finite time. Finally we show that our algorithm exhibits a limited degradation in PU utility when compared with the Pareto optimal results attained using perfect information assumptions.

Solar powered wireless sensor networks are very adapted to smart city applications, since they can operate for extended durations with minimal installation costs. Nonetheless, they require energy management schemes to operate reliably, unlike their grid-powered counterparts. Such schemes require the forecasting of future solar power inputs for each wireless sensor node, over a time horizon. They also require the determination of battery energy parameters in real time. To address both requirements, we propose a collaborative solar power forecasting framework combined to a real time battery capacity estimation model, which can be used to optimize the node schedules over the corresponding horizon.

LTE/LTE-A networks have been successfully providing advanced broadband services to millions of users worldwide. Lately, it has been suggested to use LTE networks for mission-critical applications like public safety, smart grid and military communications. We have previously shown that LTE networks are vulnerable to Denial-of-Service (DOS) and loss of service attacks from smart jammers. In this paper, we extend our previous work on resilience of LTE networks to wideband multipath fading channel, SINR estimation in frequency domain and computation of utilities based on observable parameters under the framework of single-shot and repeated games with asymmetric information. In a single-shot game formulation, network utility is severely compromised at its solutions, i.e. at the Nash Equilibria (NE). We propose evolved repeated-game strategy algorithms to combat smart jamming attacks that can be implemented in existing deployments using current technology.

Commercial LTE networks are being studied for mission-critical applications, such as public safety and smart grid communications. In this paper, LTE networks are shown vulnerable to Denial-of-Service (DOS) and loss of service attacks from smart jammers, who may employ simple narrowband jamming techniques to attack without any need to hack the network or its users. We modeled the utilities of jamming and anti-jamming actions played by the jammer and the network under the framework of single-shot and repeated Bayesian games. In a single-shot game formulation the only Nash Equilibria (NE) are pure strategy equilibria at which network utility is severely compromised. We propose a repeated-game learning and strategy algorithm for the network that outperforms single-shot games by a significant margin. Furthermore, all of our proposed actions and algorithms can be implemented with current technology.

It is well understood that decentralized systems can, through network interactions, give rise to complex behavior patterns that do not reflect their equilibrium properties. The challenge of any analytic investigation is to identify and characterize persistent properties despite the inherent irregularities of such systems and to do so efficiently. We develop a novel framework to address this challenge. Our setting focuses on evolutionary dynamics in network extensions of zero-sum games. Such dynamics have been shown analytically to exhibit chaotic behavior which traditionally has been thought of as an overwhelming obstacle to algorithmic inquiry. We circumvent these issues as follows: First, we combine ideas from dynamical systems and game theory to produce topological characterizations of system trajectories. Trajectories capture the time evolution of the system given an initial starting state. They are complex, and do not necessarily converge to limit points or even limit cycles. We provide tractable approximations of such limit sets. These relaxed descriptions involve simplices, and can be computed in polynomial time. Next, we apply standard optimization techniques to compute extremal values of system features (e.g. expected utility of an agent) within these relaxations. Finally, we use information theoretic conservation laws along with Poincaré recurrence theory to argue about tightness and optimality of our relaxation techniques.

In algorithmic game theory, the price of anarchy framework studies efficiency loss in decentralized environments. In optimization and decision theory, the price of robustness framework explores the tradeoffs between optimality and robustness in the case of single agent decision making under uncertainty. We establish a connection between the two that provides a novel analytic framework for proving tight performance guarantees for distributed systems in uncertain environments. We present applications of this framework to novel variants of atomic congestion games with uncertain costs, for which we provide tight performance bounds under a wide range of risk attitudes. Our results establish that the individual's attitude towards uncertainty has a critical effect on system performance and should therefore be a subject of close and systematic investigation.

We consider the problem of network formation in a distributed fashion. Network formation is modeled as a strategic-form game, where agents represent nodes that form and sever unidirectional links with other nodes and derive utilities from these links. Furthermore, agents can form links only with a limited set of neighbors. Agents trade off the benefit from links, which is determined by a distance-dependent reward function, and the cost of maintaining links. When each agent acts independently, trying to maximize its own utility function, we can characterize “stable” networks through the notion of Nash equilibrium. In fact, the introduced reward and cost functions lead to Nash equilibria (networks), which exhibit several desirable properties such as connectivity, bounded-hop diameter, and efficiency (i.e., minimum number of links). Since Nash networks may not necessarily be efficient, we also explore the possibility of “shaping” the set of Nash networks through the introduction of state-based utility functions. Such utility functions may represent dynamic phenomena such as establishment costs (either positive or negative). Finally, we show how Nash networks can be the outcome of a distributed learning process. In particular, we extend previous learning processes to so-called “state-based” weakly acyclic games, and we show that the proposed network formation games belong to this class of games.

We present an algorithm that, given any target tree, synthesizes reversible self-assembly rules that provide a maximum yield in the sense of stochastic stability. If the reversibility constraint is relaxed then the same algorithm can be trivially modified so that it converges to a maximum yield almost surely. The proof of correctness in both cases relies on the notion of a completing rule. We examine the conservatism of this technique by considering its implications for the internal states of the system. We show by example that any algorithm that guarantees the existence of a completing rule for all target trees will, for some cases, (1) produce complete assemblies with non-unique internal states, or (2) produce internal states that cannot be recovered from the unlabeled graph.

We present a view of cooperative control using the language of learning in games. We review the game-theoretic concepts of potential and weakly acyclic games, and demonstrate how several cooperative control problems, such as consensus and dynamic sensor coverage, can be formulated in these settings. Motivated by this connection, we build upon game-theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate restricted action sets caused by the limitations of agent capabilities and group-based decision making. Furthermore, we also introduce a new class of games called sometimes weakly acyclic games for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.

We consider a scenario in which interacting agents cooperate through an iterative process of 1) forming empirical models of the behavior of other agents and 2) selfishly optimizing a local strategy based on these models. In each iteration, an agent revises its models of other agents. Selfish optimization according to these revised models alters the behavior of a each agent. This, in turn, leads to a new round of revised models of other agents. The implication of convergence is a consistency condition. Namely, each agent's behavior is consistent with how the agent is modeled by others. Furthermore, each agent's local strategy is optimal with respect to how it models other agents. We consider a particular instance of this framework that is motivated by the "Roboflag drill" coordination scenario. This paper derives conditions for convergence, provides illustrative simulations, and establishes a connection to related work in evolutionary games.

In this paper, we address the modeling and analysis issues associated with a generic theater level campaign where two adversaries pit their military resources against each other over a sequence of multiple engagements. In particular, we consider the scenario of an air raid campaign where one adversary uses suppression of enemy air defense (SEAD) aircraft and bombers (BMBs) against the other adversary's invading ground troops (GTs) that are defended by their mobile air defense (AD) units. The original problem is decomposed into a temporal and a spatial resource allocation problem. The temporal resource allocation problem is formulated and solved in a game-theoretical framework as a multiple resource interaction problem with linear attrition functions. The spatial resource allocation problem is posed as a risk minimization problem in which the optimal corridor of ingress and optimal movement of the GTs and AD units are decided by the adversaries. These two solutions are integrated using an aggregation/deaggregation approach to evaluate resource strengths and distribute losses. Several simulation experiments were carried out to demonstrate the main ideas.

Bazerghi et al. present an "exact kinematic model of the PUMA." It appears to be a model of the PUMA's internal software model rather than a model of the PUMA itself. Other sources of information about nominal parameter values in the PUMA's internal software model are compared with actual parameter values obtained from calibrations of two PUMA 560 manipulators. It has been shown that the actual PUMA and its internal model disagree about tool tip position, typically by several millimeters.