Search

Uncertainty in safety-critical cyber-physical systems can be modeled using a finite number of parameters or parameterized input signals. Given a system specification in Signal Temporal Logic (STL), we would like to verify that for all (infinite) values of the model parameters/input signals, the system satisfies its specification. Unfortunately, this problem is undecidable in general. Statistical model checking (SMC) offers a solution by providing guarantees on the correctness of CPS models by statistically reasoning on model simulations. We propose a new approach for statistical verification of CPS models for user-provided distribution on the model parameters. Our technique uses model simulations to learn surrogate models, and uses conformal inference to provide probabilistic guarantees on the satisfaction of a given STL property. Additionally, we can provide prediction intervals containing the quantitative satisfaction values of the given STL property for any user-specified confidence level. We compare this prediction interval with the interval we get using risk estimation procedures. We also propose a refinement procedure based on Gaussian Process (GP)-based surrogate models for obtaining fine-grained probabilistic guarantees over sub-regions in the parameter space. This in turn enables the CPS designer to choose assured validity domains in the parameter space for safety-critical applications. Finally, we demonstrate the efficacy of our technique on several CPS models.

Background The generalizability of the Surviving Sepsis Campaign (SSC) guidelines to various patient populations and hospital settings has been debated. A quantitative assessment of the diversity and representation in the clinical evidence supporting the guidelines would help evaluate the generalizability of the recommendations and identify strategic research goals and priorities. In this study, we evaluated the diversity of patients in the original studies, in terms of sex, race/ethnicity, and geographical location. We also assessed diversity in sex and geographical representation among study first and last authors. Methods All clinical studies cited in support of the 2021 SSC adult guideline recommendations were identified. Original clinical studies were included, while editorials, reviews, non-clinical studies, and meta-analyses were excluded. For eligible studies, we recorded the proportion of male patients, percentage of each represented racial/ethnic subgroup (when available), and countries in which they were conducted. We also recorded the sex and location of the first and last authors. The World Bank classification was used to categorize countries. Results The SSC guidelines included six sections, with 85 recommendations based on 351 clinical studies. The proportion of male patients ranged from 47 to 62%. Most studies did not report the racial/ ethnic distribution of the included patients; when they did so, most were White patients (68–77%). Most studies were conducted in high-income countries (77–99%), which included Europe/Central Asia (33–66%) and North America (36–55%). Moreover, most first/last authors were males (55–93%) and from high-income countries (77–99%). Conclusions To enhance the generalizability of the SCC guidelines, stakeholders should define strategies to enhance the diversity and representation in clinical studies. Though there was reasonable representation in sex among patients included in clinical studies, the evidence did not r

This article describes a teaching strategy that synergizes computing and management, aimed at the running of complex projects in industry and academia, in the areas of civil engineering, physics, geosciences, and a number of other related fields. The course derived from this strategy includes four parts: (a) Computing with a selected set of modern paradigms—the stress is on Control Flow and Data Flow computing paradigms, but paradigms conditionally referred to as Energy Flow and Diffusion Flow are also covered; (b) Project management that is holistic—the stress is on the wide plethora of issues spanning from the preparation of project proposals, all the way to incorporation activities to follow after the completion of a successful project; (c) Examples from past research and development experiences—the stress is on experiences of leading experts from academia and industry; (d) Student projects that stimulate creativity—the stress is on methods that educators could use to induce and accelerate the creativity of students in general. Finally, the article ends with selected pearls of wisdom that could be treated as suggestions for further elaboration.

The optimized gradient method (OGM) provides a factor- $$\sqrt{2}$$ 2 speedup upon Nesterov’s celebrated accelerated gradient method in the convex (but non-strongly convex) setup. However, this improved acceleration mechanism has not been well understood; prior analyses of OGM relied on a computer-assisted proof methodology, so the proofs were opaque for humans despite being verifiable and correct. In this work, we present a new analysis of OGM based on a Lyapunov function and linear coupling. These analyses are developed and presented without the assistance of computers and are understandable by humans. Furthermore, we generalize OGM’s acceleration mechanism and obtain a factor- $$\sqrt{2}$$ 2 speedup in other setups: acceleration with a simpler rational stepsize, the strongly convex setup, and the mirror descent setup.

This paper proposes a generalized self-cueing real-time attention scheduling framework for DNN-based visual machine perception pipelines on resource-limited embedded platforms. Self-cueing means we identify subframe-level regions of interest in a scene internally by exploiting temporal correlations among successive video frames as opposed to externally via a cueing sensor. One limitation of our original self-cueing-and-inspection strategy (Liu et al. in Proceedings of the 28th IEEE real-time and embedded technology and applications symposium (RTAS), 2022b) lies in its lack of computational efficiency under high workloads, like busy traffic scenarios where a large number of objects are identified and separately inspected. We extend the conference publication by integrating image resizing with intermittent inspection and task batching in attention scheduling. The extension enhances the original algorithm by accelerating the processing of large objects by reducing their resolution at the cost of only a negligible degradation in accuracy, thereby achieving a higher overall object inspection throughput. After extracting partial regions around objects of interest, using an optical flow-based tracking algorithm, we allocate computation resources (i.e. DNN inspection) to them in a criticality-aware manner using a generalized batched proportional balancing algorithm (GBPB), to minimize a concept of generalized system uncertainty. It saves computational resources by inspecting low-priority regions intermittently at low frequencies and inspecting large objects at low resolutions. We implement the system on an NVIDIA Jetson Xavier platform and extensively evaluate its performance using a real-world driving dataset from Waymo. The proposed GBPB algorithm consistently outperforms the previous BPB algorithm that only uses intermittent inspection and a set of baselines. The performance gain of GBPB is larger in facing more significant resource constraints (i.e., lower samp

The optimized gradient method (OGM) provides a factor- $$\sqrt{2}$$ 2 speedup upon Nesterov’s celebrated accelerated gradient method in the convex (but non-strongly convex) setup. However, this improved acceleration mechanism has not been well understood; prior analyses of OGM relied on a computer-assisted proof methodology, so the proofs were opaque for humans despite being verifiable and correct. In this work, we present a new analysis of OGM based on a Lyapunov function and linear coupling. These analyses are developed and presented without the assistance of computers and are understandable by humans. Furthermore, we generalize OGM’s acceleration mechanism and obtain a factor- $$\sqrt{2}$$ 2 speedup in other setups: acceleration with a simpler rational stepsize, the strongly convex setup, and the mirror descent setup.

© 1972-2012 IEEE. We discuss the problem of designing channel access architectures for enabling fast, low-latency, grant-free, and uncoordinated uplink for densely packed wireless nodes. Specifically, we study random-access codes, previously introduced for the AWGN MAC, in the practically more relevant case of Rayleigh fading, when channel gains are unknown to the decoder. We propose a random coding achievability bound, which we analyze both non-asymptotically and asymptotically. As a candidate practical solution, we propose an explicit iterative coding scheme. The performance of such a solution is surprisingly close to the finite blocklength bounds. Our main findings are twofold. First, just like in the AWGN MAC, we see that jointly decoding a large number of users leads to a surprising phase transition effect, where, at spectral efficiencies below a critical threshold, a perfect multi-user interference cancellation is possible. Second, while the presence of Rayleigh fading significantly increases the minimal required energy-per-bit, the inherent randomization introduced by the channel makes it much easier to attain the optimal performance via iterative schemes. We hope that a principled definition of the random-access model, together with their information-theoretic analysis, will open the road towards unified benchmarking and performance comparison of various random-access solutions for the 5G/6G.

We consider a heterogeneous distributed service system consisting of n servers with unknown and possibly different processing rates. Jobs with unit mean arrive as a renewal process of rate proportional to n and are immediately dispatched to one of several queues associated with the servers. We assume that the dispatching decisions are made by a central dispatcher with the ability to exchange messages with the servers and endowed with a finite memory used to store information from one decision epoch to the next, about the current state of the queues and about the service rates of the servers. We study the fundamental resource requirements (memory bits and message exchange rate) in order for a dispatching policy to be always stable. First, we present a policy that is always stable while using a positive (but arbitrarily small) message rate and [Formula: see text] bits of memory. Second, we show that within a certain broad class of policies, a dispatching policy that exchanges [Formula: see text] messages per unit of time, and with [Formula: see text] bits of memory, cannot be always stable.

This paper shows that it is possible to piggyback classical information on a stream of qubits protected by quantum error-correcting codes. The piggyback channel can be created by introducing intentional errors corresponding to a controlled sequence of syndromes. These syndromes are further protected, when quantum noise is present, by classical error-correcting codes according to a performance-delay trade-off. Classical information can thus be added and extracted at arbitrary epochs without consuming additional quantum resources and without disturbing the quantum stream.

This article poses the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset’s elements and maximal chains is satisfied? We present a combinatorial algorithm to positively resolve this question. The algorithm can be implemented in polynomial time in the special case where maximal chain probabilities are affine functions of their elements. This existence problem is relevant for the equilibrium characterization of a generic strategic interdiction game on a capacitated flow network. The game involves a routing entity that sends its flow through the network while facing path transportation costs and an interdictor who simultaneously interdicts one or more edges while facing edge interdiction costs. Using our existence result on posets and strict complementary slackness in linear programming, we show that the Nash equilibria of this game can be fully described using primal and dual solutions of a minimum-cost circulation problem. Our analysis provides a new characterization of the critical components in the interdiction game. It also leads to a polynomial-time approach for equilibrium computation.

© 2020 Society for Industrial and Applied Mathematics The joint spectral radius (JSR) of a set of matrices characterizes the maximal asymptotic growth rate of an infinite product of matrices of the set. This quantity appears in a number of applications including the stability of switched and hybrid systems. A popular method used for the stability analysis of these systems searches for a Lyapunov function with convex optimization tools. We investigate dual formulations for this approach and leverage these dual programs for developing new analysis tools for the JSR. We show that the dual of this convex problem searches for the occupations measures of trajectories with high asymptotic growth rate. We both show how to generate a sequence of guaranteed high asymptotic growth rate and how to detect cases where we can provide lower bounds on the JSR. All results of this paper are presented for the general case of constrained switched systems, that is, systems for which the switching signal is constrained by an automaton.

© 2018 Elsevier B.V. DAG models are statistical models satisfying a collection of conditional independence relations encoded by the nonedges of a directed acyclic graph (DAG) G. Such models are used to model complex cause–effect systems across a variety of research fields. From observational data alone, a DAG model G is only recoverable up to Markov equivalence. Combinatorially, two DAGs are Markov equivalent if and only if they have the same underlying undirected graph (i.e., skeleton) and the same set of the induced subDAGs i→j←k, known as immoralities. Hence it is of interest to study the number and size of Markov equivalence classes (MECs). In a recent paper, we introduced a pair of generating functions that enumerate the number of MECs on a fixed skeleton by number of immoralities and by class size, and we studied the complexity of computing these functions. In this paper, we lay the foundation for studying these generating functions by analyzing their structure for trees and other closely related graphs. We describe these polynomials for some well-studied families of graphs including paths, stars, cycles, spider graphs, caterpillars, and balanced binary trees. In doing so, we recover connections to independence polynomials, and extend some classical identities that hold for Fibonacci numbers. We also provide tight lower and upper bounds for the number and size of MECs on any tree. Finally, we use computational methods to show that the number and distribution of high degree nodes in a triangle-free graph dictate the number and size of MECs.

Significance Matrix completion is a fundamental problem in machine learning that arises in various applications. We envision that our infinite width neural network framework for matrix completion will be easily deployable and produce strong baselines for a wide range of applications at limited computational costs. We demonstrate the flexibility of our framework through competitive results on virtual drug screening and image inpainting/reconstruction. Simplicity and speed are showcased by the fact that most results in this work require only a central processing unit and commodity hardware. Through its connection to semisupervised learning, our framework provides a principled approach for matrix completion that can be easily applied to problems well beyond those of image completion and virtual drug screening considered in this paper.

We study the convex relaxation of a polynomial optimization problem, maximizing a product of linear forms over the complex sphere. We show that this convex program is also a relaxation of the permanent of Hermitian positive semidefinite (HPSD) matrices. By analyzing a constructive randomized rounding algorithm, we obtain an improved multiplicative approximation factor to the permanent of HPSD matrices, as well as computationally efficient certificates for this approximation. We also propose an analog of van der Waerden’s conjecture for HPSD matrices, where the polynomial optimization problem is interpreted as a relaxation of the permanent.

We consider the problem of estimating causal DAG models from a mix of observational and interventional data, when the intervention targets are partially or completely unknown. This problem is highly relevant for example in genomics, since gene knockout technologies are known to have off-target effects. We characterize the interventional Markov equivalence class of DAGs that can be identified from interventional data with unknown intervention targets. In addition, we propose a provably consistent algorithm for learning the interventional Markov equivalence class from such data. The proposed algorithm greedily searches over the space of permutations to minimize a novel score function. The algorithm is nonparametric, which is particularly important for applications to genomics, where the relationships between variables are often non-linear and the distribution non-Gaussian. We demonstrate the performance of our algorithm on synthetic and biological datasets. Links to an implementation of our algorithm and to a reproducible code base for our experiments can be found at https://uhlerlab.github.io/causaldag/utigsp.

© 2020 IEEE. We establish the average-case hardness of the algorithmic problem of exactly computing the partition function of the Sherrington-Kirkpatrick model of spin glasses with Gaussian couplings. In particular, we establish that unless P=#P, there does not exist a polynomial-time algorithm to exactly compute this object on average. This is done by showing that if there exists a polynomial-time algorithm exactly computing the partition function for a certain fraction of all inputs, then there is a polynomial-time algorithm exactly computing this object for all inputs, with high probability, yielding P =#P. Our results cover both finite-precision arithmetic as well as the real-valued computational models. The ingredients of our proofs include Berlekamp-Welch algorithm, a list-decoding algorithm by Sudan for reconstructing a polynomial from its noisy samples, near-uniformity of log-normal distribution modulo a large prime; and a control over total variation distance for log-normal distribution under convex perturbation. To the best of our knowledge, this is the first average-case hardness result pertaining a statistical physics model with random parameters.

Abstract We study stochastic projection-free methods for constrained optimization of smooth functions on Riemannian manifolds, i.e., with additional constraints beyond the parameter domain being a manifold. Specifically, we introduce stochastic Riemannian Frank–Wolfe (Fw) methods for nonconvex and geodesically convex problems. We present algorithms for both purely stochastic optimization and finite-sum problems. For the latter, we develop variance-reduced methods, including a Riemannian adaptation of the recently proposed Spider technique. For all settings, we recover convergence rates that are comparable to the best-known rates for their Euclidean counterparts. Finally, we discuss applications to two classic tasks: the computation of the Karcher mean of positive definite matrices and Wasserstein barycenters for multivariate normal distributions. For both tasks, stochastic Fw methods yield state-of-the-art empirical performance.

© 2019 by the American Institute of Aeronautics and Astronautics, Inc. All rights reserved. In time-sensitive and dynamic missions, multi-UAV teams must respond quickly to new information and objectives. This paper presents a dynamic decentralized task allocation algorithm for allocating new tasks that appear online during the solving of the task allocation problem. Our algorithm extends the Consensus-Based Bundle Algorithm (CBBA), a decentralized task allocation algorithm, allowing for the fast allocation of new tasks without a full reallocation of existing tasks. CBBA with Partial Replanning (CBBA-PR) enables the team to trade-off between convergence time and increased coordination by resetting a portion of their previous allocation at every round of bidding on tasks. By resetting the last tasks allocated by each agent, we are able to ensure the convergence of the team to a conflict-free solution. CBBA-PR can be further improved by reducing the team size involved in the replanning, further reducing the communication burden of the team and runtime of CBBA-PR. Finally, we validate the faster convergence and improved solution quality of CBBA-PR in multi-UAV simulations.

© 2018 IEEE. Localization is an essential component for autonomous robots. A well-established localization approach combines ray casting with a particle filter, leading to a computationally expensive algorithm that is difficult to run on resource-constrained mobile robots. We present a novel data structure called the Compressed Directional Distance Transform for accelerating ray casting in two dimensional occupancy grid maps. Our approach allows online map updates, and near constant time ray casting performance for a fixed size map, in contrast with other methods exhibit poor worst case performance. Our experimental results show that the proposed algorithm approximates the performance characteristics of reading from a three dimensional lookup table of ray cast solutions while requiring two orders of magnitude less memory and precomputation. This results in a particle filter algorithm which can maintain 2500 particles with 61 ray casts per particle at 40Hz, using a single CPU thread onboard a mobile robot.

Abstract Selecting the optimal Markowitz portfolio depends on estimating the covariance matrix of the returns of N assets from T periods of historical data. Problematically, N is typically of the same order as T, which makes the sample covariance matrix estimator perform poorly, both empirically and theoretically. While various other general-purpose covariance matrix estimators have been introduced in the financial economics and statistics literature for dealing with the high dimensionality of this problem, we here propose an estimator that exploits the fact that assets are typically positively dependent. This is achieved by imposing that the joint distribution of returns be multivariate totally positive of order 2 (MTP2). This constraint on the covariance matrix not only enforces positive dependence among the assets but also regularizes the covariance matrix, leading to desirable statistical properties such as sparsity. Based on stock market data spanning 30 years, we show that estimating the covariance matrix under MTP2 outperforms previous state-of-the-art methods including shrinkage estimators and factor models.

In “Nonasymptotic Analysis of Monte Carlo Tree Search,” D. Shah, Q. Xie, and Z. Xu consider the popular tree-based search strategy, the Monte Carlo Tree Search (MCTS), in the context of the infinite-horizon discounted Markov decision process. They show that MCTS with an appropriate polynomial rather than logarithmic bonus term indeed leads to the desired convergence property. The authors derive the results by establishing a polynomial concentration property of regret for a class of nonstationary multiarm bandits. Furthermore, using this as a building block, they demonstrate that MCTS, combined with nearest neighbor supervised learning, acts as a “policy improvement” operator that can iteratively improve value function approximation.

Expansion planning models are tools frequently employed to analyze the transition to a carbon-neutral power system. Such models provide estimates for an optimal technology mix and optimal operating decisions, but they are also often used to obtain prices and subsequently calculate profits. This paper analyzes the impact of modeling assumptions on convexity for power system outcomes and, in particular, on investment cost recovery. Through a case study, we find that although there is a long-term equilibrium for producers under convex models, introducing realistic constraints, such as non-convexities/lumpiness of investments, inelastic demand or unit commitment constraints, leads to profitability challenges. We furthermore demonstrate that considering only short-term marginal costs in market-clearing may potentially create a significant missing-money problem caused by a missing-market problem and dual degeneracy in a 100 percent renewable system.

© 2018 Curran Associates Inc..All rights reserved. We study gradient-based optimization methods obtained by directly discretizing a second-order ordinary differential equation (ODE) related to the continuous limit of Nesterov's accelerated gradient method. When the function is smooth enough, we show that acceleration can be achieved by a stable discretization of this ODE using standard Runge-Kutta integrators. Specifically, we prove that under Lipschitz-gradient, convexity and order-(s + 2) differentiability assumptions, the sequence of iterates generated by discretizing the proposed second-order ODE converges to the optimal solution at a rate of O(N−2 s+1 s ), where s is the order of the Runge-Kutta numerical integrator. Furthermore, we introduce a new local flatness condition on the objective, under which rates even faster than O(N−2) can be achieved with low-order integrators and only gradient information. Notably, this flatness condition is satisfied by several standard loss functions used in machine learning. We provide numerical experiments that verify the theoretical rates predicted by our results.

For any channel $P_{Y|X}$ the strong data processing constant is defined as the smallest number $\eta_{KL}\in[0,1]$ such that $I(U;Y)\le \eta_{KL} I(U;X)$ holds for any Markov chain $U-X-Y$. It is shown that the value of $\eta_{KL}$ is given by that of the best binary-input subchannel of $P_{Y|X}$. The same result holds for any $f$-divergence, verifying a conjecture of Cohen, Kemperman and Zbaganu (1998).

Can we learn privately and efficiently through sequential interactions? A private learning model is formulated to study an intrinsic tradeoff between privacy and query complexity in sequential learning. The formulation involves a learner who aims to learn a scalar value by sequentially querying an external database and receiving binary responses. In the meantime, an adversary observes the learner’s queries, although not the responses, and tries to infer from them the scalar value of interest. The objective of the learner is to obtain an accurate estimate of the scalar value using only a small number of queries while simultaneously protecting his or her privacy by making the scalar value provably difficult to learn for the adversary. The main results provide tight upper and lower bounds on the learner’s query complexity as a function of desired levels of privacy and estimation accuracy. The authors also construct explicit query strategies whose complexity is optimal up to an additive constant.

Abstract Summary Designing interventions to control gene regulation necessitates modeling a gene regulatory network by a causal graph. Currently, large-scale gene expression datasets from different conditions, cell types, disease states, and developmental time points are being collected. However, application of classical causal inference algorithms to infer gene regulatory networks based on such data is still challenging, requiring high sample sizes and computational resources. Here, we describe an algorithm that efficiently learns the differences in gene regulatory mechanisms between different conditions. Our difference causal inference (DCI) algorithm infers changes (i.e. edges that appeared, disappeared, or changed weight) between two causal graphs given gene expression data from the two conditions. This algorithm is efficient in its use of samples and computation since it infers the differences between causal graphs directly without estimating each possibly large causal graph separately. We provide a user-friendly Python implementation of DCI and also enable the user to learn the most robust difference causal graph across different tuning parameters via stability selection. Finally, we show how to apply DCI to single-cell RNA-seq data from different conditions and cell states, and we also validate our algorithm by predicting the effects of interventions. Availability and implementation Python package freely available at http://uhlerlab.github.io/causaldag/dci. Supplementary information Supplementary data are available at Bioinformatics online.

This work addresses the problem of 6-DoF pose estimation under heavy occlusion. While previous work demonstrates reasonable results in unoccluded situations, robust and efficient pose estimation is still challenging in heavily occluded and low-texture scenarios which are ubiquitous in many applications. To this end, we propose a novel end-to-end deep neural network model recovering object poses from depth measurements. The proposed model enforces pairwise consistency of 3D geometric features by applying spectral convolutions on a pairwise compatibility graph. We achieve comparable accuracy as the state-of-the-art graph matching solver while being much faster. Our approach outperforms state-of-the-art 6-DoF pose estimation methods on LineMOD and Occlusion LineMOD and runs in reasonable time (~5.9 Hz). We additionally verify this method on a synthetic dataset with large affine changes.

© 1979-2012 IEEE. Bayesian nonparametrics are a class of probabilistic models in which the model size is inferred from data. A recently developed methodology in this field is small-variance asymptotic analysis, a mathematical technique for deriving learning algorithms that capture much of the flexibility of Bayesian nonparametric inference algorithms, but are simpler to implement and less computationally expensive. Past work on small-variance analysis of Bayesian nonparametric inference algorithms has exclusively considered batch models trained on a single, static dataset, which are incapable of capturing time evolution in the latent structure of the data. This work presents a small-variance analysis of the maximum a posteriori filtering problem for a temporally varying mixture model with a Markov dependence structure, which captures temporally evolving clusters within a dataset. Two clustering algorithms result from the analysis: D-Means, an iterative clustering algorithm for linearly separable, spherical clusters; and SD-Means, a spectral clustering algorithm derived from a kernelized, relaxed version of the clustering problem. Empirical results from experiments demonstrate the advantages of using D-Means and SD-Means over contemporary clustering algorithms, in terms of both computational cost and clustering accuracy.

© 2017 IEEE. We investigate the use of variable speed limits for resilient operation of transportation networks, which are modeled as dynamical flow networks under local routing decisions. In such systems, some external inflow is injected to the so-called origin nodes of the network. The total inflow arriving at each node is routed to its operational outgoing links based on their current densities of traffic. The density on each link has first-order dynamics driven by the difference of its incoming and outgoing flows. A link fails if it reaches its jam density. Such failures may propagate in the network and cause a systemic failure. We show that larger link capacities, that is, the maximum flows that can be sustained by the links, are not always better for preventing systemic failures under local routing. Accordingly, we propose the use of variable speed limits to operate the links below their capacities, when necessary, to compensate for the lack of global information and coordination in routing decisions. We show that systemic failures under feasible external inflows can always be averted through proper selection of speed limits if the routing decisions are sufficiently responsive to local congestion and the network is initially uncongested. This is an attractive feature as it provides a practical alternative to building more physical capacity or altering routing decisions that are determined by social behavior.

© 1993-2012 IEEE. Age of information (AoI) is a recently proposed metric for measuring information freshness. AoI measures the time that elapsed since the last received update was generated. We consider the problem of minimizing average and peak AoI in a wireless networks, consisting of a set of source-destination links, under general interference constraints. When fresh information is always available for transmission, we show that a stationary scheduling policy is peak age optimal. We also prove that this policy achieves average age that is within a factor of two of the optimal average age. In the case where fresh information is not always available, and packet/information generation rate has to be controlled along with scheduling links for transmission, we prove an important separation principle: The optimal scheduling policy can be designed assuming fresh information, and independently, the packet generation rate control can be done by ignoring interference. Peak and average AoI for discrete time G/Ber/1 queue is analyzed for the first time, which may be of independent interest.

Hierarchical Bayesian Models (HBMs) have been used with some success to capture empirically observed patterns of under- and overgeneralization in child language acquisition. However, as is well known, HBMs are "ideal" learning systems, assuming access to unlimited computational resources that may not be available to child language learners. Consequently, it remains crucial to carefully assess the use of HBMs along with alternative, possibly simpler, candidate models. This paper presents such an evaluation for a language acquisition domain where explicit HBMshave been proposed: the acquisition of English dative constructions. In particular, we present a detailed, empiricallygrounded model-selection comparison of HBMs vs. a simpler alternative based on clustering along with maximum likelihood estimation that we call linear competition learning (LCL). Our results demonstrate that LCL can match HBM model performance without incurring on the high computational costs associated with HBMs. © 2013 Association for Computational Linguistics.

IEEE Autonomous unmanned aerial vehicles (UAVs) that can execute aggressive (\ie, high-speed and high-acceleration) maneuvers have attracted significant attention in the past few years. This article focuses on accurate tracking of aggressive quadcopter trajectories. We propose a novel control law for tracking of position and yaw angle and their derivatives of up to fourth order, specifically velocity, acceleration, jerk, and snap along with yaw rate and yaw acceleration. Jerk and snap are tracked using feedforward inputs for angular rate and angular acceleration based on the differential flatness of the quadcopter dynamics. Snap tracking requires direct control of body torque, which we achieve using closed-loop motor speed control based on measurements from optical encoders attached to the motors. The controller utilizes incremental nonlinear dynamic inversion (INDI) for robust tracking of linear and angular accelerations despite external disturbances, such as aerodynamic drag forces. Hence, prior modeling of aerodynamic effects is not required. We rigorously analyze the proposed control law through response analysis and demonstrate it in experiments. The controller enables a quadcopter UAV to track complex 3-D trajectories, reaching speeds up to 12.9 m/s and accelerations up to 2.1 g, while keeping the root-mean-square tracking error down to 6.6 cm, in a flight volume that is roughly 18 m x 7 m and 3-m tall. We also demonstrate the robustness of the controller by attaching a drag plate to the UAV in flight tests and by pulling on the UAV with a rope during hover.

There have been enormous efforts to implement automated vehicle-based mobility (AVM) by considering smart infrastructure such as cooperative intelligent transportation system. However, there is lack of consideration on economical approach for an optimal deployment strategy of the AVM service and smart infrastructure. Furthermore, the influence of travel demand in service area has been ignored. We develop a new framework for maximizing the profit of connected and automated vehicle-based mobility (CAV-M) service using cost modeling and metaheuristic optimization algorithm. The proposed framework extracts an optimal sub-network, which is selected by a set of optimal links in the service area, and identifies an optimal construction strategy for the smart infrastructure depending on given operational design domain and travel demand. Based on service network analyses with varying demand patterns and volumes, we observe that the optimal sub-network varies with the combination of trip demand patterns and volumes. It is also found that the benefit of deploying the smart infrastructure is obtainable only when there are sufficient travel demands. Furthermore, the optimal sub-network is always superior to raw network in terms of economical profit, which suggests the proposed framework has great potential to prioritize road links in the target area for the CAV-M service.