An official website of the United States government
Abstract We study the problem of fitting a piecewise affine (PWA) function to input–output data. Our algorithm divides the input domain into finitely many regions whose shapes are specified by a user-provided template and such that the input–output data in each region are fit by an affine function within a user-provided error tolerance. We first prove that this problem is NP-hard. Then, we present a top-down algorithmic approach for solving the problem. The algorithm considers subsets of the data points in a systematic manner, trying to fit an affine function for each subset using linear regression. If regression fails on a subset, the algorithm extracts a minimal set of points from the subset (an unsatisfiable core) that is responsible for the failure. The identified core is then used to split the current subset into smaller ones. By combining this top-down scheme with a set-covering algorithm, we derive an overall approach that provides optimal PWA models for a given error tolerance, where optimality refers to minimizing the number of pieces of the PWA model. We demonstrate our approach on three numerical examples that include PWA approximations of a widely used nonlinear insulin–glucose regulation model and a double inverted pendulum with soft contacts.
more »
« less
PWA-CTM: An Extended Cell-Transmission Model based on Piecewise Affine Approximation of the Fundamental Diagram
Throughout the past decades, many different versions of the widely used first-order Cell-Transmission Model (CTM) have been proposed for optimal traffic control. Highway traffic management techniques such as Ramp Metering (RM) are typically designed based on an optimization problem with nonlinear constraints originating in the flow-density relation of the Fundamental Diagram (FD). Most of the extended CTM versions are based on the trapezoidal approximation of the flow-density relation of the Fundamental Diagram (FD) in an attempt to simplify the optimization problem. However, this relation is naturally nonlinear, and crude approximations can greatly impact the efficiency of the optimization solution. In this study, we propose a class of extended CTMs that are based on piecewise affine approximations of the flow-density relation such that (a) the integrated squared error with respect to the true relation is greatly reduced in comparison to the trapezoidal approximation, and (b) the optimization problem remains tractable for real-time application of ramp metering optimal controllers. A two-step identification method is used to approximate the FD with piecewise affine functions resulting in what we refer to as PWA-CTMs. The proposed models are evaluated by the performance of the optimal ramp metering controllers, e.g. using the widely used PI-ALINEA approach, in complex highway traffic networks. Simulation results show that the optimization problems based on the PWA-CTMs require less computation time compared to other CTM extensions while achieving higher accuracy of the flow and density evolution. Hence, the proposed PWA-CTMs constitute one of the best approximation approaches for first-order traffic flow models that can be used in more general and challenging modeling and control applications.
more »
« less
- Award ID(s):
- 2127605
- PAR ID:
- 10381007
- Date Published:
- Journal Name:
- Proceedings of the 30th Mediterranean Conference on Control and Automation (MED 2022)
- Page Range / eLocation ID:
- 1059 to 1065
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The traffic fundamental diagram (FD) describes the relationships among fundamental traffic variables of flow, density, and speed. FD represents fundamental properties of traffic streams, giving insights into traffic performance. This paper presents a theoretical investigation of dynamic FD properties, derived directly from vehicle car-following (control) models to model traffic hysteresis. Analytical derivation of dynamic FD is enabled by (i) frequency-domain representation of vehicle kinematics (acceleration, speed, and position) to derive vehicle trajectories based on transfer function and (ii) continuum approximation of density and flow, measured along the derived trajectories using Edie’s generalized definitions. The formulation is generic: the derivation of dynamic FD is possible with any analytical car-following (control) laws for human-driven vehicles or automated vehicles (AVs). Numerical experiments shed light on the effects of the density-flow measurement region and car-following parameters on the dynamic FD properties for an AV platoon.more » « less
-
We consider the decentralized control of radial distribution systems with controllable photovoltaic inverters and storage devices. For such systems, we consider the problem of designing controllers that minimize the expected cost of meeting demand, while respecting distribution system and resource constraints. Employing a linear approximation of the branch flow model, we formulate this problem as the design of a decentralized disturbance-feedback controller that minimizes the expected value of a convex quadratic cost function, subject to convex quadratic constraints on the state and input. As such problems are, in general, computationally intractable, we derive an inner approximation to this decentralized control problem, which enables the efficient computation of an affine control policy via the solution of a conic program. As affine policies are, in general, suboptimal for the systems considered, we provide an efficient method to bound their suboptimality via the solution of another conic program. A case study of a 12 kV radial distribution feeder demonstrates that decentralized affine controllers can perform close to optimal.more » « less
-
We consider the decentralized control of radial distribution systems with controllable photovoltaic inverters and energy storage resources. For such systems, we investigate the problem of designing fully decentralized controllers that minimize the expected cost of balancing demand, while guaranteeing the satisfaction of individual resource and distribution system voltage constraints. Employing a linear approximation of the branch flow model, we formulate this problem as the design of a decentralized disturbance-feedback controller that minimizes the expected value of a convex quadratic cost function, subject to robust convex quadratic constraints on the system state and input. As such problems are, in general, computationally intractable, we derive a tractable inner approximation to this decentralized control problem, which enables the efficient computation of an affine control policy via the solution of a finite-dimensional conic program. As affine policies are, in general, suboptimal for the family of systems considered, we provide an efficient method to bound their suboptimality via the optimal solution of another finite-dimensional conic program. A case study of a 12 kV radial distribution system demonstrates that decentralized affine controllers can perform close to optimal.more » « less
-
Hydrodynamic and continuum traffic flow models usually require that traffic states are stationary for the model assumptions to hold. The reproducibility of a concave fundamental diagram, FD, is typically assumed to also demonstrate that the underlying states are sufficiently near stationary. This paper uses loop detector data from five locations to empirically demonstrate that the microscopic traffic dynamics giving rise to a concave FD can also invalidate the stationarity assumptions required by the traffic flow models. Specifically, this work develops the exclusionary vehicle aggregation, EVA, method to evaluate conditions underlying conventional fixed time average state measurements. The shape of the FD is shown to be highly correlated with the standard deviation of headways, stdev(h), within the underlying samples: low stdev(h) corresponding to triangular FD and high stdev(h) to concave FD. Furthermore, high stdev(h) is shown to correspond to the presence of large voids within the given sample. These voids are inherently non-stationary because different regions of the sample are perceptively distinct. With these new insights in mind, a review of the earliest FD literature reveals evidence supporting the loop detector-based findings. Collectively, the loop detector and historical FD results span over 75 years of empirical traffic data. Meanwhile, a driver behind a large void can act independent of their leader. From the kinematic wave, KW, perspective, a void creates an ill posed problem: if a driver acts independent of their leader there are no KW from the boundaries that reach the driver during their independence, and thus, there is no way to predict how the driver should act. Generally, this type of ill posed problem is avoided in theoretical developments by requiring stationary conditions for the given model, but as this paper shows, real traffic does not necessarily provide stationary conditions. Although the voids are large enough to disrupt stationarity, their duration remains far below the resolution of fixed time averaging to be perceived. As a result, whenever a traffic flow model depends on stationarity and the shape of the FD, it is imperative to check the data to make sure they support the assumptions placed on the FD, e.g., via the EVA method developed herein. Finally, the empirical results in this paper should facilitate the development of macroscopic models that better capture the dynamics of real traffic.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/MED54222.2022.9837131
