In this paper we propose a novel distributed algorithm to solve degenerate linear programs on asynchronous networks. Namely, we propose a distributed version of the well known simplex algorithm. We prove its convergence to the global lexicographic minimum for possibly fully degenerate problems and provide simulations supporting the conjecture that the completion time scales linearly with the diameter of the graph. The algorithm can be interpreted as a dual version of the constraints consensus algorithm proposed in [1] to solve abstract programs when the last is applied to linear programs. Finally, we study a multi-agent task assignment problem and show that it can be solved by means of our distributed simplex algorithm.

The problem of maintaining balance between consumption and production of electric energy in the presence of a high share of intermittent power sources in a transmission grid is addressed. A distributed, asynchronous optimization algorithm, based on the ideas of cutting-plane approximations and adjustable robust counterparts, is presented to compute economically optimal adjustable dispatch strategies. These strategies guarantee satisfaction of the power balancing constraint as well as of the operational constraints for all possible realizations of the uncertain power generation or demand. The communication and computational effort of the proposed distributed algorithm increases for each computational unit only slowly with the number of participants, making it well suited for large scale networks. A distributed implementation of the algorithm and a numerical study are presented, which show the performance in asynchronous networks and its robustness against packet loss.

In this paper we propose a novel distributed algorithm to solve degenerate linear programs on asynchronous peer-to-peer networks with distributed information structures. We propose a distributed version of the well-known simplex algorithm for general degenerate linear programs. A network of agents, running our algorithm, will agree on a common optimal solution, even if the optimal solution is not unique, or will determine infeasibility or unboundedness of the problem. We establish how the multi-agent assignment problem can be efficiently solved by means of our distributed simplex algorithm. We provide simulations supporting the conjecture that the completion time scales linearly with the diameter of the communication graph.

In this paper we consider a network of agents that can evaluate each other according to an interaction graph modeling some physical interconnection or social relationship. Each agent provides a score for its (out-)neighboring agents in the interaction graph. The goal is to design a distributed protocol, run by the agents themselves, to group the network nodes into two classes (binary classification) on the basis of the evaluation outcomes. We propose a hierarchical Bayesian framework in which the agents' belonging to one of the two classes is assumed to be a probabilistic event with unknown parameter. Exploiting such a hierarchical framework, we are able to design a distributed classification scheme in which nodes cooperatively classify their own state. We characterize the solution for a fault-diagnosis context in cyber-physical systems, and for an opinion-classification/community-discovery setup in social networks.

In this paper, we consider a general problem setup for a wide class of convex and robust distributed optimization problems in peer-to-peer networks. In this setup, convex constraint sets are distributed to the network processors who have to compute the optimizer of a linear cost function subject to the constraints. We propose a novel fully distributed and asynchronous algorithm, named cutting-plane consensus, to solve the problem, based on a polyhedral outer approximation of the constraint sets. Processors running the algorithm compute and exchange linear approximations of their locally feasible sets. Independently of the number of processors in the network, each processor stores only a small number of linear constraints, making the algorithm scalable to large networks. The cutting-plane consensus algorithm is presented and analyzed for the general framework. Specifically, we prove the correctness of the algorithm, and show its robustness against communication or processor failures. Then, the cutting-plane consensus algorithm is specified to three different classes of distributed optimization problems, namely 1) inequality constrained problems, 2) robust optimization problems, and 3) almost separable optimization problems. For each one of these problem classes we solve a concrete problem and present computational results. That is, we show how to solve: position estimation in wireless sensor networks, a distributed robust linear program, and a distributed microgrid control problem.

In this paper, we propose a discrete-time Sequential Quadratic Programming (SQP) algorithm for nonlinear optimal control problems. Using the idea by Hauser of projecting curves onto the trajectory space, the introduced algorithm has guaranteed recursive feasibility of the dynamic constraints. The second essential feature of the algorithm is a specific choice of the Lagrange multiplier update. Due to this ad hoc choice of the multiplier, the algorithm converges locally quadratically. Finally, we show how the proposed algorithm connects standard SQP methods for nonlinear optimal control with the Projection Operator Newton method by Hauser.

In this paper, we propose a novel approach to compute minimum-time trajectories for a two-track car model, including tires and (quasi-static) longitudinal and lateral load transfer. Given the car model and a planar track, including lane boundaries, our goal is to find a trajectory of the car minimizing the traveling time subject to steering and tire limits. Moreover, we enforce normal force constraints to avoid wheel liftoff. Based on a projection operator nonlinear optimal control technique, we propose a minimum-time trajectory generation strategy to compute the fastest car trajectory. Numerical computations are presented on two testing scenarios, a 90° turn and a real testing track. The computations allow us to both demonstrate the efficiency and accuracy of the proposed approach and highlight important features of the minimum-time trajectories. Finally, we integrate our strategy into a commercial vehicle dynamics software, thus computing minimum-time trajectories for a complex multibody vehicle model. The matching between the predicted trajectory and the one of the commercial toolbox further highlights the effectiveness of the proposed methodology.

In this paper we address the minimum lap-time problem for a single-track rigid car which includes tire models and load transfer. Given a planar track including lane boundaries, our goal is to find a trajectory of the car minimizing the lap time subject to tire and steering limits. By using a new set of coordinates, the time-dependent system is transformed into a squote{space-dependent} (and space-variant) system. The choice of a suitable set of coordinates and the partition of the dynamics into a ``longitudinal'' one and a ``transverse'' one, allows us to convert the minimum time problem into a fixed horizon constrained optimal control problem. Based on a projection operator nonlinear optimal control technique, we propose a minimum lap-time strategy to push the rigid car to the limit of its handling capabilities. Finally, we provide numerical computations that: (i) show the effectiveness of the proposed strategy, and (ii) allow us to highlight important features of minimum lap-time trajectories.

We study bipartite, first-order networks where the nodes take on leader or follower roles. Specifically, we let the leaders’ positions be static and assume that leaders and followers communicate via an undirected switching graph topology. This assumption is inspired by the swarming behavior of silkworm moths, where female moths intermittently release pheromones to be detected by the males. The main result presented here states that if the followers execute the linear agreement protocol, they will converge to the convex hull spanned by the leaders’ positions as long as the time-varying undirected graph defining the communication among all agents is jointly connected. The novelty of this research is that we use LaSalle’s Invariance Principle for switched systems, and additionally, the result is shown to hold for arbitrary state dimensions.

In this paper, we investigate the controllability and observability properties of a family of linear dynamical systems, whose structure is induced by the Laplacian of a grid graph. This analysis is motivated by several applications in network control and estimation, quantum computation and discretization of partial differential equations. Specifically, we characterize the structure of the grid eigenvectors by means of suitable decompositions of the graph. For each eigenvalue, based on its multiplicity and on suitable symmetries of the corresponding eigenvectors, we provide necessary and sufficient conditions to characterize all and only the nodes from which the induced dynamical system is controllable (observable). We discuss the proposed criteria and show, through suitable examples, how such criteria reduce the complexity of the controllability (respectively, observability) analysis of the grid.

In this paper we propose a novel reduced-order car model and show how it can be used for parameter fitting and dynamic analysis of complex car vehicles. The proposed two-track model consists of a rigid body interacting with the ground at four contact points and including tire models and load transfer. The model does not include suspension models, thus keeping a reasonable level of complexity. Load transfer (both longitudinal and lateral) is taken into account by explicitly imposing the holonomic constraints (for contact) and computing the reaction forces of the ground at the four contact points. Since the vehicle interacts with the ground at four contact points, it results in a hyper-static structure so that the reaction forces are not uniquely determined. Using the Principle of Least Work, we obtain a compatibility equation, providing for a unique resolution of the forces. The compatibility equation is parametrized by four strain parameters, one for each contact point. These parameters are related to those of the suspension, and provide a means for accounting for some dynamic aspects of the suspension without introducing additional states (and parameters) into the dynamics. We provide numerical computations validating the proposed model with respect to a multi-body virtual prototype on aggressive maneuvers.

In this paper we consider a network of monitors that can count the occurrences of binary events of interest. The aim is to estimate both the local event probabilities and some global features of the system as, e.g., the mean probability. This scenario is motivated by several applications in cyber-physical systems and social networks. We propose a hierarchical Bayesian approach in which the individual event probabilities are treated as random variables with an emph{a priori} density function. Following the empirical Bayes approach, the prior is chosen in a family of distributions parameterized by suitable unknown hyperparameters. We develop a distributed optimization algorithm, as a variant of a standard distributed dual decomposition scheme, to obtain locally the Maximum Likelihood estimates of the hyperparameters. These estimates allow each monitor to gain accuracy in both the local and global estimation tasks. This approach is particularly well suited in scenarios in which the number of samples at each node are allowed to be highly inhomogeneous.

Distributed abstract programs are a novel class of distributed optimization problems where (i) the number of variables is much smaller than the number of constraints and (ii) each constraint is associated to a network node. Abstract optimization programs are a generalization of linear programs that captures numerous geometric optimization problems. We propose novel constraints consensus algorithms for distributed abstract programs with guaranteed finite-time convergence to a global optimum. The algorithms rely upon solving local abstract programs and exchanging the solutions among neighboring processors. The proposed algorithms are appropriate for networks with weak time-dependent connectivity requirements and tight memory constraints. We show how the constraints consensus algorithms may be applied to suitable target localization and formation control problems.

We study a distributed allocation process where, at each time, every player i) proposes a new bid based on the average utilities produced up to that time, ii) adjusts such allocations based on the inputs received from its neighbors, and iii) generates and allocates new utilities. The average allocations evolve according to a doubly (over time and space) averaging algorithm. We study conditions under which the average allocations reach consensus to any point within a predefined target set even in the presence of adversarial disturbances. Motivations arise in the context of coalitional games with transferable utilities (TU) where the target set is any set of allocations that makes the grand coalition stable.

In this paper we consider a network of agents monitoring a spatially distributed traffic process. Each node measures the number of arrivals seen at its monitoring point in a given time-interval. We propose an asynchronous distributed approach based on a hierarchical Bayes model with unknown hyperparameter, which allows each node to compute the minimum mean square error (MMSE) estimator of the local arrival rate by suitably fusing the information from the whole network. Simulation results show that the distributed scheme improves the estimation accuracy compared to a purely decentralized setup and is reliable even in presence of limited local data. An ad-hoc algorithm with reduced complexity is also proposed, which performs very closely to the optimal MMSE estimator.

In this paper we consider repeated coalitional games with transferable utilities (TU) over networks. Namely, we consider a set of n players that have to distribute among themselves a vector of rewards (one for each player). In our network version there is no coordinator allocating the rewards, but the agents have to agree on a common time-averaged vector by updating the local estimates of the reward vector. The common time-averaged reward vector has to approach a suitable constraint set, called core of the game, that guarantees that no agents benefit from quitting the grand coalition. We propose a doubly (over time and space) averaging distributed algorithm. At every iteration, each agent first computes a weighted average of its own time-averaged estimate and those of his neighbors and then generates a new reward vector in order to drive the time-averaged estimate towards a pre-assigned set. The main contribution of the paper is to prove that under certain assumptions, i) all agents' estimates reach consensus on the true time-averaged reward vector, and ii) the estimates (and thus the true time-averaged reward vector) approach the pre-assigned set. Conditions for this to happen are related to the connectivity over time of the communication topology and to the approachability principle.

In this paper we consider a novel partition-based framework for distributed optimization in peer-to-peer networks. In several important applications the agents of a network system have to solve an optimization problem with two important features: (i) the dimension of the decision variable is a function of the network size, and (ii) the cost function and the constraints have a sparsity structure that is related to the sparsity of the graph. For this class of problems a straightforward application of existing methods would result in all the nodes reaching consensus on the minimizer. This approach has two inefficiencies: poor scalability and redundancy of shared information. Indeed, the dimension of the vector stored by each node and the size of the local problem to be solved depend on the network size. Furthermore, all the nodes compute the entire solution. In this paper we provide a preliminary contribution in developing and analyzing novel partition based algorithms. We propose a partition-based algorithm based on dual decomposition. We show that, exploiting the problem structure, the solution can be partitioned among the nodes so that each node stores a local copy of just a portion of the decision variable (rather than a copy of the entire decision vector) and solves a small scale local problem.

This paper addresses the problem of robust optimization in large-scale networks of identical processors. General convex optimization problems are considered, where uncertain constraints are distributed to the processors in the network. The processors have to compute a maximizer of a linear objective over the robustly feasible set, defined as the intersection of all locally known feasible sets. We propose a novel asynchronous algorithm, based on outer-approximations of the robustly feasible set, to solve such problems. Each processor stores a small set of linear constraints that form an outer-approximation of the robustly feasible set. Based on its locally available information and the data exchange with neighboring processors, each processor repeatedly updates its local approximation. A computational study for robust linear programming illustrates that the completion time of the algorithm depends primarily on the diameter of the communication graph and is independent of the network size.

In this paper we explore the dynamics of a single-track car model. We develop a model of a rigid car inspired to the well known bicycle model. The bicycle model is a planar rigid model that approximates the vehicle as a rigid body with two wheels. However, the bicycle model does not allow to describe the effect of load transfer, since it does not model the suspensions. Using an explicit formulation of the holonomic constraints imposed on the rigid model, we are able to model the load transfer of the car. The resulting model can be seen as a limit condition of a model with suspensions whose stiffness goes to infinity. The load transfer allows to have a more accurate model for the tires. We use a standard model known as Pacejka model that provides empirical curves describing the forces generated by the tires. With this model in hand, we perform an analysis of the equilibrium manifold of the vehicle and, as main contribution of the paper, we explore the trajectories of the system by use of novel nonlinear optimal control techniques. These techniques allow us to compute aggressive trajectories of the car vehicle and study how the vehicle behaves depending on its parameters. We compute trajectories for the vehicle on a real car testing track.

In this paper we introduce the model of a Longitudinal Vectored Thrust Vertical Take Off and Landing (LVT-VTOL) aircraft. We believe that the proposed model, while described by reasonably tractable equations, captures several interesting dynamic features of new generation vectored thrust aerial vehicles with new maneuvering capabilities as, in particular, the ability of vertical take off and landing and transition to a (classical) forward flight configuration. We characterize the equilibrium manifold of the LVT-VTOL in the entire range of operation (from hover to forward flight). Then, as main contribution of the paper, we propose an optimal control based strategy to explore the trajectory manifold (the set of possibly aggressive trajectories) of the proposed model. To show the effectiveness of the exploration strategy, we compute a full transition from hover to forward flight.

In this paper we propose a distributed algorithm for solving linear programs with combinations of local and global constraints in a multi-agent setup. A fully distributed and asynchronous algorithm is proposed. The computation of the local decision makers involves the solution of two distinct (local) optimization problems, namely a local copy of a global linear program and a smaller problem used to generate ”problem columns”. We show that, when running the proposed algorithm, all decision makers agree on a common optimal solution, even if the original problem has several optimal solutions, or detect unboundedness and infeasibility if necessary.

In this paper we introduce and study a novel model of a Tilt-Rotor VTOL aircraft. The aircraft is structured as a blended wing body equipped with a tilting rotor (the propulsion unit) that gives the vehicle the capability of vertical take off and transition to a forward flight configuration. This model captures the main features of novel tilt-rotor aircraft architectures with more challenging control and maneuvering capabilities. We introduce a complex nine degrees of freedom model of the aircraft to explore the dynamics and the maneuvering capabilities of the vehicle. We perform an analysis of the equilibrium manifold of the aircraft (namely a parametrized family of trimming trajectories) and, as main contribution of the paper, we introduce a set of optimal control based strategies to explore the trajectory manifold of the vehicle in order to generate non-stationary and highly aggressive trajectories. In particular, we provide numerical computations showing how to generate a trajectory for transitions from near hover to forward flight.

In this paper we investigate an optimal control problem in which the objective is to decelerate a simplified vehicle model, subject to input constraints, from a given initial velocity down to zero by minimizing a quadratic cost functional. The problem is of interest because, although it involves apparently simple drift-less dynamics, a minimizing trajectory does not exist. This problem is motivated by a minimum-time problem for a fairly complex car vehicle model on a race track. Numerical computations run on the car problem provide evidence of non-existence of a minimizing trajectory and of an apparently unmotivated ripple in the steer angle. We flit Abstract this situation to a very simple dynamics/objective setting, show that no minimizing trajectory exists, and reproduce the oscillating behavior on the steer angle as a mean to reduce the cost functional.

In this paper we investigate the observability and reachability properties of a network system, running a Laplacian based average consensus algorithm, when the communication graph is a grid or a torus. More in detail, under suitable conditions on the eigenvalue multiplicity, we provide necessary and sufficient conditions, based on simple algebraic rules from number theory, to characterize all and only the nodes from which the network system is observable (reachable). For any set of observation (leader) nodes, we provide a closed form expression for the unobservable (unreachable) eigenvalues and for the eigenvectors of the unobservable (unreachable) subsystem.

In this paper we investigate the observability and reachability properties of a network system, running a Laplacian based average consensus algorithm, when the communication graph is a grid. More in detail, we characterize the structure of the grid eigenvectors by means of suitable decompositions of the graph. For each eigenvalue, based on its multiplicity and on suitable symmetries of the corresponding eigenvectors, we provide necessary and sufficient conditions to characterize all and only the nodes from which the network system is observable (reachable). We discuss the proposed criteria and show, through suitable examples, how such criteria reduce the complexity of the observability (respectively reachability) analysis of the grid.

In this paper we propose a novel reduced-order car model that captures some key features for aggressive maneuvering of complex car vehicles. The proposed model, called RigidCar, consists of a rigid body interacting with the ground at four contact points (two-track car) and including tire models and load transfer. The model does not include suspension models, thus keeping a reasonable level of complexity. Load transfer (both longitudinal and lateral) is taken into account by explicitly imposing the holonomic constraints and computing the reaction forces of the ground at the four contact points. Since the vehicle interacts with the ground at four contact points, it results to be a hyper-static structure so that reaction forces are not uniquely determined. We use the Principle of Least Work to get a compatibility equation and thus resolving the indeterminateness. We provide numerical computations validating the proposed model with respect to a multi-body virtual prototype on an aggressive ISO lane-change maneuver.

In this paper we investigate the observability properties of a network system, running a Laplacian based average consensus algorithm, when the communication graph is a path or a cycle. More in detail, we provide necessary and sufficient conditions, based on simple algebraic rules from number theory, to characterize all and only the nodes from which the network system is observable. Interesting immediate corollaries of our results are: (i) a path graph is observable from any single node if and only if the number of nodes of the graph is a power of two, n = 2^i, i ∈ N, and (ii) a cycle is observable from any pair of observation nodes if and only if n is a prime number. For any set of observation nodes, we provide a closed form expression for the unobservable eigenvalues and for the eigenvectors of the unobservable subspace.

In this paper we investigate the reachability and observability properties of a network system, running a Laplacian based average consensus algorithm, when the communication graph is a path or a cycle. Specifically, we provide necessary and sufficient conditions, based on simple rules from number theory, to characterize all and only the nodes from which the network system is reachable (respectively observable). Interesting immediate corollaries of our results are: (i) a path graph is reachable (observable) from any single node if and only if the number of nodes of the graph is a power of two, n = 2^i; i in N, and (ii) a cycle is reachable (observable) from any pair of nodes if and only if n is a prime number. For any set of control (observation) nodes, we provide a closed form expression for the (unreachable) unobservable eigenvalues and for the eigenvectors of the (unreachable) unobservable subsystem.

In this brief, we provide optimal control-based strategies to explore the dynamic capabilities of a single-track car model that includes tire models and longitudinal load transfer. First, we propose numerical tools to analyze the equilibrium manifold of the vehicle. That is, we design a continuation and predictor-corrector numerical strategy to compute the cornering equilibria on the entire range of operation of the tires. Second, as a main contribution of this brief, we explore the system dynamics by the use of nonlinear optimal control techniques. Specifically, we propose a combined optimal control and continuation strategy to compute aggressive car trajectories. To show the effectiveness of the proposed strategy, we compute aggressive maneuvers of the vehicle inspired to testing maneuvers from virtual and real prototyping.