Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputing Dynamic User Equilibrium on Large-Scale Networks Without Knowing Global Parameters
79
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Dynamic user equilibrium (DUE) is a Nash-like solution concept describing an equilibrium in dynamic traffic systems over a fixed planning period. DUE is a challenging class of equilibrium problems, connecting network loading models and notions of system equilibrium in one concise mathematical framework. Recently, Friesz and Han introduced an integrated framework for DUE computation on large-scale networks, featuring a basic fixed-point algorithm for the effective computation of DUE. In the same work, they present an open-source MATLAB toolbox which allows researchers to test and validate new numerical solvers. This paper builds on this seminal contribution, and extends it in several important ways. At a conceptual level, we provide new strongly convergent algorithms designed to compute a DUE directly in the infinite-dimensional space of path flows. An important feature of our algorithms is that they give provable convergence guarantees without knowledge of global parameters. In fact, the algorithms we propose are adaptive, in the sense that they do not need a priori knowledge of global parameters of the delay operator, and which are provable convergent even for delay operators which are non-monotone. We implement our numerical schemes on standard test instances, and compare them with the numerical solution strategy employed by Friesz and Han.
rate research
Read More
Large-scale agent systems have foreseeable applications in the near future. Estimating their macroscopic density is critical for many density-based optimization and control tasks, such as sensor deployment and city traffic scheduling. In this paper, we study the problem of estimating their dynamically varying probability density, given the agents individual dynamics (which can be nonlinear and time-varying) and their states observed in real-time. The density evolution is shown to satisfy a linear partial differential equation uniquely determined by the agents dynamics. We present a density filter which takes advantage of the system dynamics to gradually improve its estimation and is scalable to the agents population. Specifically, we use kernel density estimators (KDE) to construct a noisy measurement and show that, when the agents population is large, the measurement noise is approximately ``Gaussian. With this important property, infinite-dimensional Kalman filters are used to design density filters. It turns out that the covariance of measurement noise depends on the true density. This state-dependence makes it necessary to approximate the covariance in the associated operator Riccati equation, rendering the density filter suboptimal. The notion of input-to-state stability is used to prove that the performance of the suboptimal density filter remains close to the optimal one. Simulation results suggest that the proposed density filter is able to quickly recognize the underlying modes of the unknown density and automatically ignore outliers, and is robust to different choices of kernel bandwidth of KDE.
We review selected results related to robustness of networked systems in finite and asymptotically large size regimes, under static and dynamical settings. In the static setting, within the framework of flow over finite networks, we discuss the effect of physical constraints on robustness to loss in link capacities. In the dynamical setting, we review several settings in which small gain type analysis provides tight robustness guarantees for linear dynamics over finite networks towards worst-case and stochastic disturbances. We also discuss network flow dynamic settings where nonlinear techniques facilitate in understanding the effect on robustness of constraints on capacity and information, substituting information with control action, and cascading failure. We also contrast the latter with a representative contagion model. For asymptotically large networks, we discuss the role of network properties in connecting microscopic shocks to emergent macroscopic fluctuations under linear dynamics as well as for economic networks at equilibrium. Through the review of these results, the paper aims to achieve two objectives. First, to highlight selected settings in which the role of interconnectivity structure of a network on its robustness is well-understood. Second, to highlight a few additional settings in which existing system theoretic tools give tight robustness guarantees, and which are also appropriate avenues for future network-theoretic investigations.
In Part I of this paper series, several macroscopic traffic model elements for mathematically describing freeway networks equipped with managed lane facilities were proposed. These modeling techniques seek to capture at the macroscopic the complex phenomena that occur on managed lane-freeway networks, where two parallel traffic flows interact with each other both in the physical sense (how and where cars flow between the two lane groups) and the physiological sense (how driving behaviors are changed by being adjacent to a quantitatively and qualitatively different traffic flow). The local descriptions we developed in Part I are not the only modeling complexity introduced in managed lane-freeway networks. The complex topologies mean that network-scale modeling of a freeway corridor is increased in complexity as well. The already-difficult model calibration problem for a dynamic model of a freeway becomes more complex when the freeway becomes, in effect, two interrelating flow streams. In the present paper, we present an iterative-learning-based approach to calibrating our models physical and driver-behavioral parameters. We consider the common situation where a complex traffic model needs to be calibrated to recreate real-world baseline traffic behavior, such that counterfactuals can be generated by training purposes. Our method is used to identify traditional freeway parameters as well as the proposed parameters that describe managed lane-freeway-network-specific behaviors. We validate our model and calibration methodology with case studies of simulations of two managed lane-equipped California freeways.
In this paper we consider the problem of finding a Nash equilibrium (NE) via zeroth-order feedback information in games with merely monotone pseudogradient mapping. Based on hybrid system theory, we propose a novel extremum seeking algorithm which converges to the set of Nash equilibria in a semi-global practical sense. Finally, we present two simulation examples. The first shows that the standard extremum seeking algorithm fails, while ours succeeds in reaching NE. In the second, we simulate an allocation problem with fixed demand.
We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query $S subset V$, the oracle returns the size of the cut between $S$ and $V setminus S$. We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with $tilde{O}(n^{5/3})$ queries, and computing an exact global minimum cut of $G$ with only $tilde{O}(n)$ queries (while learning the graph requires $tilde{Theta}(n^2)$ queries).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
