 Award ID(s):
 1944318
 NSFPAR ID:
 10488396
 Publisher / Repository:
 IEEE
 Date Published:
 Journal Name:
 IEEE transactions on automatic control
 Volume:
 67
 Issue:
 8
 ISSN:
 00189286
 Page Range / eLocation ID:
 3822  3835
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

In this letter, we consider a Linear Quadratic Gaussian (LQG) control system where feedback occurs over a noiseless binary channel and derive lower bounds on the minimum communication cost (quantified via the channel bitrate) required to attain a given control performance. We assume that at every time step an encoder can convey a packet containing a variable number of bits over the channel to a decoder at the controller. Our system model provides for the possibility that the encoder and decoder have shared randomness, as is the case in systems using dithered quantizers. We define two extremal prefixfree requirements that may be imposed on the message packets; such constraints are useful in that they allow the decoder, and potentially other agents to uniquely identify the end of a transmission in an online fashion. We then derive a lower bound on the rate of prefixfree coding in terms of directed information; in particular we show that a previously known bound still holds in the case with shared randomness. We generalize the bound for when prefix constraints are relaxed, and conclude with a ratedistortion formulation.more » « less

null (Ed.)We consider the problem of selling perishable items to a stream of buyers in order to maximize social welfare. A seller starts with a set of identical items, and each arriving buyer wants any one item, and has a valuation drawn i.i.d. from a known distribution. Each item, however, disappears after an a priori unknown amount of time that we term the horizon for that item. The seller knows the (possibly different) distribution of the horizon for each item, but not its realization till the item actually disappears. As with the classic prophet inequalities, the goal is to design an online pricing scheme that competes with the prophet that knows the horizon and extracts full social surplus (or welfare). Our main results are for the setting where items have independent horizon distributions satisfying the monotonehazardrate (MHR) condition. Here, for any number of items, we achieve a constantcompetitive bound via a conceptually simple policy that balances the rate at which buyers are accepted with the rate at which items are removed from the system. We implement this policy via a novel technique of matching via probabilistically simulating departures of the items at future times. Moreover, for a single item and MHR horizon distribution with mean, we show a tight result: There is a fixed pricing scheme that has competitive ratio at most 2  1/μ, and this is the best achievable in this class. We further show that our results are best possible. First, we show that the competitive ratio is unbounded without the MHR assumption even for one item. Further, even when the horizon distributions are i.i.d. MHR and the number of items becomes large, the competitive ratio of any policy is lower bounded by a constant greater than 1, which is in sharp contrast to the setting with identical deterministic horizons.more » « less

We consider the problem of finitehorizon optimal control of a discrete linear timevarying system subject to a stochastic disturbance and fully observable state. The initial state of the system is drawn from a known Gaussian distribution, and the final state distribution is required to reach a given target Gaussian distribution, while minimizing the expected value of the control effort. We derive the linear optimal control policy by first presenting an efficient solution for the diffusionless case, and we then solve the case with diffusion by reformulating the system as a superposition of diffusionless systems. We show that the resulting solution coincides with a LQG problem with particular terminal cost weight matrix.more » « less

We study the problem of maximizing payoff generated over a period of time in a general class of closed queueing networks with a finite, fixed number of supply units that circulate in the system. Demand arrives stochastically, and serving a demand unit (customer) causes a supply unit to relocate from the “origin” to the “destination” of the customer. The key challenge is to manage the distribution of supply in the network. We consider general controls including customer entry control, pricing, and assignment. Motivating applications include shared transportation platforms and scrip systems. Inspired by the mirror descent algorithm for optimization and the backpressure policy for network control, we introduce a rich family of mirror backpressure (MBP) control policies. The MBP policies are simple and practical and crucially do not need any statistical knowledge of the demand (customer) arrival rates (these rates are permitted to vary in time). Under mild conditions, we propose MBP policies that are provably near optimal. Specifically, our policies lose at most [Formula: see text] payoff per customer relative to the optimal policy that knows the demand arrival rates, where K is the number of supply units, T is the total number of customers over the time horizon, and η is the demand process’ average rate of change per customer arrival. An adaptation of MBP is found to perform well in numerical experiments based on data from NYC Cab.
This paper was accepted by Gabriel Weintraub, revenue management and market analytics.
Funding: Y. Kanoria was supported by the National Science Foundation’s Division of Civil, Mechanical, and Manufacturing Innovation [Grant CMMI1653477].
Supplemental Material: The data files and online appendices are available at https://doi.org/10.1287/mnsc.2023.4934 .

Abstract Home range estimation is routine practice in ecological research. While advances in animal tracking technology have increased our capacity to collect data to support home range analysis, these same advances have also resulted in increasingly autocorrelated data. Consequently, the question of which home range estimator to use on modern, highly autocorrelated tracking data remains open. This question is particularly relevant given that most estimators assume independently sampled data. Here, we provide a comprehensive evaluation of the effects of autocorrelation on home range estimation. We base our study on an extensive data set of
GPS locations from 369 individuals representing 27 species distributed across five continents. We first assemble a broad array of home range estimators, including Kernel Density Estimation (KDE ) with four bandwidth optimizers (Gaussian reference function, autocorrelated‐Gaussian reference function [AKDE ], Silverman's rule of thumb, and least squares cross‐validation), Minimum Convex Polygon, and Local Convex Hull methods. Notably, all of these estimators exceptAKDE assume independent and identically distributed (IID ) data. We then employ half‐sample cross‐validation to objectively quantify estimator performance, and the recently introduced effective sample size for home range area estimation () to quantify the information content of each data set. We found thatAKDE 95% area estimates were larger than conventionalIID ‐based estimates by a mean factor of 2. The median number of cross‐validated locations included in the hold‐out sets byAKDE 95% (or 50%) estimates was 95.3% (or 50.1%), confirming the largerAKDE ranges were appropriately selective at the specified quantile. Conversely, conventional estimates exhibited negative bias that increased with decreasing . To contextualize our empirical results, we performed a detailed simulation study to tease apart how sampling frequency, sampling duration, and the focal animal's movement conspire to affect range estimates. Paralleling our empirical results, the simulation study demonstrated thatAKDE was generally more accurate than conventional methods, particularly for small . While 72% of the 369 empirical data sets had >1,000 total observations, only 4% had an >1,000, where 30% had an <30. In this frequently encountered scenario of small ,AKDE was the only estimator capable of producing an accurate home range estimate on autocorrelated data.