Advances in Control, Communication Networks, and Transportation Systems

This chapter presents applications of polytopic approximation methods for reachable set computation using dynamic optimization. The problem of computing exact reachable sets can be formulated in terms of a Hamilton-Jacobi partial differential equation (PDE). Numerical solutions which provide convergent approximations of this PDE have computational complexity which is exponential in the continuous variable dimension. Using dynamic optimization and polytopic approximation, computationally efficient algorithms for overapproximative reachability analysis have been developed for linear dynamical systems tikya[1]. In this chapter, we extend these to feedback linearizable nonlinear systems, linear dynamic games, and norm-bounded nonlinear systems. Three illustrative examples are presented.

This chapter deals with the problem of measurement feedback control under setmembership uncertainty for systems with original linear structure and hard bounds on the uncertain items. It indicates feedback control strategies which ensure guaranteed deviation from a given terminal set despite the uncertain disturbances and incomplete feedback. Routes for numerical treatment of the solutions are suggested on the basis of ellipsoidal techniques.

This chapter gives a survey of the theory of square-integrable martingales and the construction of basic sets of orthogonal martingales in terms of which all other martingales may be expressed as stochastic integrals. Specific cases such as Brownian motion, Lévy processes and stochastic jump processes are discussed, as are some applications to mathematical finance.

I take this opportunity with great pleasure to thank Prof. Pravin Varaiya for his guidance over the past fifteen years not only in my academic research but also at Teja Technologies, Inc. In this chapter I have outlined some of the emerging themes in system design particularly for network equipment. Factors such as the proprietary nature of many of the developments, the rapid pace of change in the field, and also the desire to keep out material that may appear promotional of commercial interests have required this chapter to be kept at a fairly general level.

My doctoral thesis work with Prof. Varaiya dealt with the modeling, analysis and control of hybrid systems—i.e., systems which combined continuous and discrete state dynamics tikya[1]. Subsequently, as a member of a research team at California PATH Laboratory of the UC-Berkeley, directed by Prof. Varaiya, I contributed to the development of a hybrid system specification and simulation system called SHIFT tikya[2]. After forming Teja Technologies, Inc., where Prof. Varaiya was on the Board of Directors for several years, I continued the core work on a commercial basis with emphasis on high-performance execution applied to fast path network applications.

Varaiya and Walrand found an elegant insight regarding the use of feedback in a causal coding context: While generally useful, feedback becomes useless when the channel is sufficiently symmetric. The goal of this note is to extend this insight to scenarios inspired by sensor networks. Specifically, two such scenarios are considered: a situation with a single sensor but where the source is observed through a noisy channel, and a genuine network scenario where all source and noise distributions are assumed to be Gaussian. For the latter, it is shown that feedback is useless if source and channel bandwidth are equal, but that, if the latter is larger, feedback is strictly useful. Varaiya and Walrand establish their results via dynamic programming arguments. It is unclear to date whether such arguments can be extended to the distributed scenario considered in the present chapter. Instead, our results are established via information-theoretic bounds.

We consider a set of networked controllers where multiple control systems coexist with their control loops closed over a shared wireless network that induces random delays and packet losses. This system requires a joint design of the wireless network and the controllers, where the design objective is to optimize the control performance. This performance is a complex function of the controller design and the network parameters, such as throughput, packet delay and packet loss probability. Random delays and packet losses in the feedback loop impose new challenges on the optimal controller design. We first investigate controller design with randomly dropped packets. We prove the separation of estimation and control under certain assumptions of the network and show that the Kalman filter can be modified to generate the optimal state estimate when part or all of the observation is lost. The wireless network needs to provide a sufficient throughput for each of the sensor measurements in order to guarantee the stability of the Kalman filter. We then focus on the wireless network design for this controller. The goal of optimizing the control performance imposes implicit tradeoffs on the wireless network design as opposed to the explicit tradeoffs typical in wireless data and voice applications. Specifically, the tradeoffs between network throughput, time delay and packet loss probability are intricate and implicit in the control performance index, which complicates network optimization. We show that this optimization requires a cross-layer design framework, and propose such a framework for a broad class of networked control applications. We then illustrate this framework by a cross-layer optimization of the link layer, MAC layer, and sample period selection in a double inverted pendulum system.

Motivated by resource allocation problems in communication networks as well as power systems, we consider the design of market mechanisms for such settings which are robust to gaming behavior by market participants. Recent results in this work are reviewed, including: (1) efficiency loss guarantees for a data rate allocation mechanism first proposed by Kelly, both when link capacities are fixed and when they are elastic; (2) characterization of mechanisms that minimize the efficiency loss, within a certain class of “simple” mechanisms; (3) extensions to general networks; and (4) mechanism design for supply function bidding in electric power systems.

We discuss how decentralized network resource allocation problems fit within the context of mechanism design (realization theory and implementation theory), and how mechanism design can provide useful insight into the nature of decentralized network resource allocation problems. The discussion is guided by the unicast problem with routing and Quality of Service (QoS) requirements, and the multi-rate multicast service provisioning problem in networks. For these problems we present decentralized resource allocation mechanisms that achieve the solution of the corresponding centralized resource allocation problem and are informationally efficient. We show how the aforementioned mechanisms can be embedded into the general framework of realization theory, and indicate how realization theory can be used to establish the mechanisms’ informational efficiency in certain instances. We also present a conjecture related to implementation in Nash equilibria of the optimal centralized solution of the unicast service provisioning problem.

This chapter provides a review of the research on design of control systems for automated highway applications that has been conducted at the California PATH Program of the University of California, Berkeley. The primary focus is on the research areas that Pravin Varaiya led directly, particularly while serving as PATH Director from 1994 to 1997. He and the researchers working directly with him made significant contributions to the definition of control strategies for coordinating maneuvers of neighboring vehicles and for managing the flows of vehicles along network links, while also developing the hybrid system modeling and simulation tools needed to evaluate the effectiveness of these strategies.

Recurrent and non-recurrent congestions on freeways may be substantially reduced if today’s “spontaneous” infrastructure utilisation is replaced by an orderly, controllable operation via comprehensive application of ramp metering and freeway-to-freeway control, combined with powerful optimal control techniques. This chapter first explains why ramp metering can lead to a dramatic amelioration of traffic conditions on freeways. Subsequently, a large-scale example demonstrates the high potential of advanced ramp metering approaches. It is demonstrated that the proposed control scheme is efficient, fair and real-time feasible.