Skip to main content
main-content

Über dieses Buch

Distributed Decision Making and Control is a mathematical treatment of relevant problems in distributed control, decision and multiagent systems, The research reported was prompted by the recent rapid development in large-scale networked and embedded systems and communications. One of the main reasons for the growing complexity in such systems is the dynamics introduced by computation and communication delays. Reliability, predictability, and efficient utilization of processing power and network resources are central issues and the new theory and design methods presented here are needed to analyze and optimize the complex interactions that arise between controllers, plants and networks. The text also helps to meet requirements arising from industrial practice for a more systematic approach to the design of distributed control structures and corresponding information interfaces Theory for coordination of many different control units is closely related to economics and game theory network uses being dictated by congestion-based pricing of a given pathway. The text extends existing methods which represent pricing mechanisms as Lagrange multipliers to distributed optimization in a dynamic setting. In Distributed Decision Making and Control, the main theme is distributed decision making and control with contributions to a general theory and methodology for control of complex engineering systems in engineering, economics and logistics. This includes scalable methods and tools for modeling, analysis and control synthesis, as well as reliable implementations using networked embedded systems. Academic researchers and graduate students in control science, system theory, and mathematical economics and logistics will find mcu to interest them in this collection, first presented orally by the contributors during a sequence of workshops organized in Spring 2010 by the Lund Center for Control of Complex Engineering Systems, a Linnaeus Center at Lund University, Sweden.>

Inhaltsverzeichnis

Frontmatter

Multi-Agent Control and Game Theory

Frontmatter

Primal and Dual Criteria for Robust Stability Applied to Large Scale Systems

Abstract
Primal and dual formulations of stability criteria based on multipliers will be discussed. The foundation for multiplier-based stability analysis is the use of a convex cone of multipliers to characterize the uncertainty in a system. The primal and dual stability criteria are formulated as convex feasibility tests involving the nominal dynamics and multipliers from the cone and the polar cone, respectively. The motivation for introducing the dual is that it provides additional insight into the stability criterion and that it is sometimes easier to use than the primal.
The case considered in this chapter is that of uncertainty as it represents the interconnection of a complex network. The multipliers are used to describe characteristic properties of the network such as the spectral location or the structure of the underlying graph.
Ulf T. Jönsson

Optimal Controller Synthesis for a Decentralized Two-Player Linear-Quadratic Regulator via Spectral Factorization

Abstract
We develop controller synthesis algorithms for decentralized control problems. The particular system considered here consists of two interconnected linear subsystems, with communication allowed in only one direction.We develop the concept of spectral factorization, which is the approach used to construct the optimal controllers. Explicit state-space formulae are provided, and we show that each player has to do more than simply estimate the states that they cannot observe. In other words, the simplest separation principle does not hold for this decentralized control problem. Some intuition into the control policies is provided, and the order of the optimal controllers is established.
John Swigart, Sanjay Lall

Decentralized Control with Communication Bandwidth Constraints

Abstract
In this chapter,we investigate the decentralized control problem in the setting of limited bandwidth sensing channels. Specifically, we consider the decentralized stabilization problem of a linear time-invariant (LTI) plant by multiple control stations that receive sensing information through rate-limited channels, and these stations are not capable of communicating with each other directly. The main result of the this chapter is a sufficient condition on the data rate of respective channels to guarantee system stabilizability. We provide an explicit way to construct the associated stabilizing encoder, decoder, and controller. We also present a robustness analysis showing that this control algorithm is structurally robust against model mismatch.
Chun Zhang, Geir E. Dullerud

Monotone Games for Cognitive Radio Systems

Abstract
Noncooperative game theory is a branch of game theory for the resolution of conflicts among interacting decision makers (called players), each behaving selfishly to optimize his own well-being. In this chapter, we present a mathematical treatment of (generalized) Nash equilibrium problems based on the variational inequality and complementarity approach, covering the topics of existence and uniqueness of an equilibrium, and the design of distributed algorithms using best-response iterations along with their convergence properties.We then apply the developed machinery to the distributed design of cognitive radio systems. The proposed equilibrium models and resulting algorithms differ in performance of the secondary users, level of protection of the primary users, computational effort and signaling among primary and secondary users, convergence analysis, and convergence speed; which makes them suitable for many different CR systems.
Gesualdo Scutari, Daniel P. Palomar, Francisco Facchinei, Jong-Shi Pang

A Mechanism Design Approach to Dynamic Price-Based Control of Multi-Agent Systems

Abstract
We show how ideas and tools from the field of mechanism design in economics can be brought to bear on the problem of price-based control of dynamical systems. Specifically, we take inspiration from the Vickrey-Clarkes-Groves mechanism to design strategy-proof dynamic price-functions, which can induce subsystems to apply socially efficient control inputs even though they are self-interested and possibly strategically misreport their cost and dynamics’ models to the control designer.
Cédric Langbort

Recursive Bargaining with Dynamic Accumulation

Abstract
We study a bargaining game (á la Rubinstein) in which parties are allowed to invest part of an available surplus. Therefore, in addition to the standard problem of how to divide a surplus for their own consumption, parties face the additional problem of how much to invest, knowing that the level of investment affects the surplus available in the next period. We provide an algorithm to solve the game when the number of bargaining stages is finite but tends to infinity.We show that the equilibrium investment and consumption shares become independent of the capital stock. The convergence of the equilibrium demands is affected by the elasticity of substitution and parties’ patience.
Francesca Flamini

Adaptation and Learning in Autonomous Systems

Frontmatter

Distributed Nonlinear Estimation for Diverse Sensor Devices

Abstract
Distributed linear estimation theory has received increased attention in recent years due to several promising, mainly industrial applications. Distributed nonlinear estimation, however, is still a relatively unexplored field despite the need for such a theory in numerous practical problems with inherent nonlinearities. This work presents a unified way of describing distributed implementations of three commonly used nonlinear estimators: the extended Kalman filter (EKF), the unscented Kalman filter (UKF) and the particle filter. Leveraging on the presented framework, we propose new distributed versions of these methods, in which the nonlinearities are locally managed by the various sensors, whereas the different estimates are merged based on a weighted average consensus process.We show how the merging mechanism can handle sensors running different filters, which is especially useful when they are endowed with diverse local computational capabilities. Numerical simulations of the proposed algorithms are shown to outperform the few published ones in a localization problem via range-only measurements. Quality and effectiveness are investigated in a heterogeneous filtering scenario as well. As a special case, we also present a way to manage the computational load of distributed particle filters using graphical processing unit (GPU) architectures.
Andrea Simonetto, Tamás Keviczky

Performance Prediction in Uncertain Multi-Agent Systems Using ${\mathcal L}_1$ Adaptation-Based Distributed Event-Triggering

Abstract
This chapter studies the impact of communication constraints and uncertainties on the performance of multi-agent systems, while closing the local loops with embedded \({\mathcal L}_1\) adaptive controllers. A communication and adaptation co-design scheme is proposed that helps to predict system performance. With this scheme, an agent locally determines its broadcast time instants using distributed event-triggering. The embedded \({\mathcal L}_1\) adaptive controller enables each agent to compensate for the local uncertainties and disturbances. Performance bounds are derived on the difference between the signals of the ideal model (in the absence of uncertainties and with perfect communication) and the real system operating with the proposed co-design scheme, which can be arbitrarily reduced subject only to hardware limitations. These results can be used for design guidelines in safety-critical applications.
Xiaofeng Wang, Naira Hovakimyan

Weight Determination by Manifold Regularization

Abstract
A new type of linear kernel smoother is derived and studied. The smoother, referred to as weight determination by manifold regularization, is the solution to a regularized least squares problem. The regularization avoids overfitting and can be used to express prior knowledge of an underlying smooth function. An interesting property of the kernel smoother is that it is well suited for systems governed by the semi-supervised smoothness assumption. Several examples are given to illustrate this property. We also discuss why these type of techniques can have a potential interest for the system identification community.
Henrik Ohlsson, Lennart Ljung

Dynamic Coverage and Clustering: A Maximum Entropy Approach

Abstract
We present a computational framework we have recently developed for solving a large class of dynamic coverage and clustering problems, ranging from those that arise in the deployment of mobile sensor networks to the identification of ensemble spike trains in computational neuroscience applications. This framework provides for the identification of natural clusters in an underlying dataset, while addressing inherent tradeoffs such as those between cluster resolution and computational cost.More specifically, we define the problem of minimizing an instantaneous coverage metric as a combinatorial optimization problem in a Maximum Entropy Principle framework, which we formulate specifically for the dynamic setting. Locating and tracking dynamic cluster centers is cast as a control design problem that ensures the algorithm achieves progressively better coverage with time.
Carolyn Beck, Srinivasa Salapaka, Puneet Sharma, Yunwen Xu

Transverse Linearization for Underactuated Nonholonomic Mechanical Systems with Application to Orbital Stabilization

Abstract
We consider a class of mechanical systems with an arbitrary number of passive (nonactuated) degrees of freedom, which are subject to a set of nonholonomic constraints. We assume that the challenging problem of motion planning is solved giving rise to a feasible desired periodic trajectory. Our goal is either to analyze orbital stability of this trajectory with a given time-independent feedback control law or to design a stabilizing controller. We extend our previous work done for mechanical systems without nonholonomic constraints. The main contribution is an analytical method for computing coefficients of a linear reduced-order control system, solutions of which approximate dynamics that is transversal to the preplanned trajectory. This linear system is shown to be useful for stability analysis and for design of feedback controllers orbitally, exponentially stabilizing forced periodic motions in nonholonomic mechanical systems.We illustrate our approach on a standard benchmark example.
Leonid B. Freidovich, Anton S. Shiriaev

Distributed Model Predictive Control and Supply Chains

Frontmatter

A Distributed NMPC Scheme without Stabilizing Terminal Constraints

Abstract
We consider a distributed NMPC scheme in which the individual systems are coupled via state constraints. In order to avoid violation of the constraints, the subsystems communicate their individual predictions to the other subsystems once in each sampling period. For this setting, Richards and How have proposed a sequential distributed MPC formulation with stabilizing terminal constraints. In this chapter we show how this scheme can be extended to MPC without stabilizing terminal constraints or costs.We show theoretically and by means of numerical simulations that under a suitable controllability condition stability and feasibility can be ensured even for rather short prediction horizons.
Lars Grüne, Karl Worthmann

A Set-Theoretic Method for Verifying Feasibility of a Fast Explicit Nonlinear Model Predictive Controller

Abstract
In this chapter an algorithm for nonlinear explicit model predictive control is presented. A low complexity receding horizon control law is obtained by approximating the optimal control law using multiscale basis function approximation. Simultaneously, feasibility and stability of the approximate control law is ensured through the computation of a capture basin (region of attraction) for the closed-loop system. In a previous work, interval methods were used to construct the capture basin (feasible region), yet this approach suffered due to slow computation times and high grid complexity.
In this chapter, we suggest an alternative to interval analysis based on zonotopes. The suggested method significantly reduces the complexity of the combined function approximation and verification procedure through the use of DC (difference of convex) programming, and recursive splitting. The result is a multiscale function approximation method with improved computational efficiency for fast nonlinear explicit model predictive control with guaranteed stability and constraint satisfaction.
Davide M. Raimondo, Stefano Riverso, Sean Summers, Colin N. Jones, John Lygeros, Manfred Morari

Towards Parallel Implementation of Hybrid MPC—A Survey and Directions for Future Research

Abstract
In this chapter parallel implementations of hybridMPC will be discussed. Different methods for achieving parallelism at different levels of the algorithms will be surveyed. It will be seen that there are many possible ways of obtaining parallelism for hybrid MPC, and it is by no means clear which possibilities should be utilized to achieve the best possible performance. This question is a challenge for future research.
Daniel Axehill, Anders Hansson

Hierarchical Model Predictive Control for Plug-and-Play Resource Distribution

Abstract
This chapter deals with hierarchical model predictive control (MPC) of distributed systems. A three-level hierarchical approach is proposed, consisting of a high levelMPC controller, a second level of so-called aggregators, controlled by an online MPC-like algorithm, and a lower level of autonomous units.
The approach is inspired by smart-grid electric power production and consumption systems, where the flexibility of a large number of power producing and/or power consuming units can be exploited in a smart grid solution. The objective is to accommodate the load variation on the grid, arising on one hand from varying consumption, on the other hand by natural variations in power production, e.g., from wind turbines.
The proposed method can also be applied to supply chain management systems, where the challenge is to balance demand and supply, using a number of storages each with a maximal capacity. The algorithm will then try to balance the risk of individual storages running empty or full with the risk of having overproduction or unsatisfied demand.
The approach presented is based on quadratic optimization and possesses the properties of low algorithmic complexity and of scalability. In particular, the proposed design methodology facilitates plug-and-play addition of subsystems without redesign of any controllers.
Jan Bendtsen, Klaus Trangbaek, Jakob Stoustrup

Hierarchical Model-Based Control for Automated Baggage Handling Systems

Abstract
This chapter presents a unified and extended account of previous work regarding modern baggage handling systems that transport luggage in an automated way using destination-coded vehicles (DCVs). These vehicles transport the bags at high speeds on a network of tracks. To control the route of each DCV in the system we first propose centralized and distributed predictive control methods. This results in nonlinear, nonconvex, mixed integer optimization problems. Therefore, the proposed approaches will be expensive in terms of computational effort. As an alternative, we also propose a hierarchical control framework where at higher control levels we reduce the complexity of the computations by simplifying and approximating the nonlinear optimization problem by a mixed integer linear programming (MILP) problem. The advantage is that for MILP problems, solvers are available that allow us to efficiently compute the global optimal solution. To compare the performance of the proposed control approaches we assess the trade-off between optimality and CPU time for the obtained results on a benchmark case study.
Alina N. Tarău, Bart De Schutter, Hans Hellendoorn

Stability with Uniform Bounds for On-line Dial-a-Ride Problems under Reasonable Load

Abstract
In continuously running logistic systems (like in-house pallet transportation systems), finite buffer capacities usually require controls that can achieve uniformly bounded waiting queues (strong stability). Standard stochastic traffic assumptions (arrival rates below service rates) cannot, in general, guarantee these strong stability requirements, no matter which control policy is used. So, the worstcase traffic notion of reasonable load was introduced, originally for the analysis of the on-line dial-a-ride Problem. A set of requests is reasonable if the requests that are presented in a sufficiently large time period can be served in a time period of at most the same length. The rationale behind this concept is that the occurrence of nonreasonable request sets renders the system overloaded, requiring capacity be extended. For reasonable load, there are control policies that can guarantee uniformly bounded flow times, leading to strong stability in many cases. Control policies based on naïve reoptimization, however, can in general achieve neither bounded flow times nor strong stability. In this chapter, we review the concept and examples for reasonable load. Moreover, we present new control policies achieving strong stability as well as new elementary examples of request sets where naïve reoptimization fails.
Sven Oliver Krumke, Jörg Rambau

Backmatter

Weitere Informationen