We introduce PandemIQ Llama, a domain-adapted large language model (LLM) designed specifically for pandemic intelligence applications. Building on the pre-trained Llama-3.1-8B model, we conducted continuous training using our curated Pandemic Corpus. This dataset was assembled from authoritative public health sources, scientific literature, and specialized knowledge repositories, comprising 508,924 documents totaling 5.8 billion tokens, which is the largest pandemic domain specific data cohort for LLM training. Benefited from our curated large data cohorts and through continuous training leveraging extensive computational resources, the developed PandemIQ Llama model can extract critical domain knowledge on pandemic, which is typically underrepresented in general-purpose language models, To evaluate its performance, we conducted comprehensive comparison of PandemIQ Llama with both prompt-engineered and task-specific fine-tuned baseline models using two tasks: the Biomedical Alert News Question Answering task (1,508 reports with 30 expert-generated questions each) and the Disease Event Type Classification benchmark (4,500 news snippets across eight disease categories). PandemIQ Llama demonstrated substantial improvements over strong baseline models, achieving performance gains ranging from 3.8% to 10.97%. These results suggest that PandemIQ Llama could significantly enhance public health surveillance and analysis capabilities. In addition, our result also suggests that the LLMs can perform better with continuous training than fine-tuning on domain specific tasks. Social Impact: The BEACON platform, powered by our model, launched and now serves over 100 government and multilateral public health organizations and users across 154 countries. Analytics from the platform is being integrated into the Epidemic Intelligence from Open Sources system run by the World Health Organization. This integration will provide public health decision-makers with a powerful LLM-based tool for pandemic surveillance.

We present a new geometric interpretation of Markov Decision Processes (MDPs) with a natural normalization procedure that allows us to adjust the value function at each state without altering the advantage of any action with respect to any policy. This advantage-preserving transformation of the MDP motivates a class of algorithms which we call \emph{Reward Balancing}, which solve MDPs by iterating through these transformations, until an approximately optimal policy can be trivially found. We provide a convergence analysis of several algorithms in this class, in particular showing that for MDPs for unknown transition probabilities we can improve upon state-of-the-art sample complexity results.

We study the multiple-policy evaluation problem where we are given a set of $K$ policies and the goal is to evaluate their performance (expected total reward over a fixed horizon) to an accuracy $\epsilon$ with probability at least $1-\delta$. We propose an algorithm named CAESAR for this problem. Our approach is based on computing an approximately optimal sampling distribution and using the data sampled from it to perform the simultaneous estimation of the policy values. CAESAR has two phases. In the first phase, we produce coarse estimates of the visitation distributions of the target policies at a low order sample complexity rate that scales with $\tilde{O}(\frac{1}{\epsilon})$. In the second phase, we approximate the optimal sampling distribution and compute the importance weighting ratios for all target policies by minimizing a step-wise quadratic loss function inspired by the DualDICE objective. Up to low order and logarithmic terms CAESAR achieves a sample complexity $\tilde{O}\left(\frac{H^4}{\epsilon^2}\sum_{h=1}^H\max_{k\in[K]}\sum_{s,a}\frac{(d_h^{\pi^k}(s,a))^2}{\mu^*_h(s,a)}\right)$, where $d^{\pi}$ is the visitation distribution of policy $\pi$, $\mu^*$ is the optimal sampling distribution, and $H$ is the horizon.

We propose C-LAIfO, a computationally efficient algorithm designed for imitation learning from videos in the presence of visual mismatch between agent and expert domains. We analyze the problem of imitation from expert videos with visual discrepancies, and introduce a solution for robust latent space estimation using contrastive learning and data augmentation. Provided a visually robust latent space, our algorithm performs imitation entirely within this space using off-policy adversarial imitation learning. We conduct a thorough ablation study to justify our design and test C-LAIfO on high-dimensional continuous robotic tasks. Additionally, we demonstrate how C LAIfO can be combined with other reward signals to facilitate learning on a set of challenging hand manipulation tasks with sparse rewards. Our experiments show improved performance compared to baseline methods, highlighting the effectiveness of C-LAIfO. To ensure reproducibility, we open source our code.

We consider Data Centers (DCs) as flexible loads that can alter their power consumption to alleviate congestion in the electric power network. We model DCs using a queuing-theoretic view and we form a Quality of Service (QoS)-based cost function that signifies how well a DC can carry out its workload given an amount of active servers. We integrate DCs in a centralized economic dispatch problem that determines, apart from power generation, DC workload shifting and server utilization, while respecting transmission line constraints. We further present a tractable decentralized formulation obtained via Lagrangian decomposition, which we solve using a dual gradient ascent algorithm. Experimental results on a standard power network explore the system-wide benefits of DC flexibility in “coupled” data and power networks, emphasizing on the trade-offs between the DC location, QoS, and efficiency.

We study unconstrained Online Linear Optimization with Lipschitz losses. The goal is to simultaneously achieve (i) second order gradient adaptivity; and (ii) comparator norm adaptivity also known as “parameter freeness” in the literature. Existing regret bounds (Cutkosky and Orabona, 2018; Mhammedi and Koolen, 2020; Jacobsen and Cutkosky, 2022) have the suboptimal $O(\sqrt{V_T\log V_T})$ dependence on the gradient variance $V_T$ , while the present work improves it to the optimal rate $O(\sqrt{V_T})$ using a novel continuous-time-inspired algorithm, without any impractical doubling trick. This result can be extended to the setting with unknown Lipschitz constant, eliminating the range ratio problem from prior works (Mhammedi and Koolen, 2020). Concretely, we first show that the aimed simultaneous adaptivity can be achieved fairly easily in a continuous time analogue of the problem, where the environment is modeled by an arbitrary continuous semimartingale. Then, our key innovation is a new discretization argument that preserves such adaptivity in the discrete time adversarial setting. This refines a non-gradient-adaptive discretization argument from (Harvey et al., 2023), both algorithmically and analytically, which could be of independent interest.

We develop a Distributionally Robust Optimization (DRO) formulation for Multiclass Logistic Regression (MLR), which could tolerate data contaminated by outliers. The DRO framework uses a probabilistic ambiguity set defined as a ball of distributions that are close to the empirical distribution of the training set in the sense of the Wasserstein metric. We relax the DRO formulation into a regularized learning problem whose regularizer is a norm of the coefficient matrix. We establish out-of-sample performance guarantees for the solutions to our model, offering insights on the role of the regularizer in controlling the prediction error. We apply the proposed method in rendering deep Vision Transformer (ViT)-based [1] image classifiers robust to random and adversarial attacks. Specifically, using the MNIST and CIFAR-10 datasets, we demonstrate reductions in test error rate by up to 83.5% and loss by up to 91.3% compared with baseline methods, by adopting a novel random training method.

The early theory of actor-critic methods considered convergence using linear function approximators for the policy and value functions. Recent work has established convergence using neural network approximators with a single hidden layer. In this work we are taking the natural next step and establish convergence using deep neural networks with an arbitrary number of hidden layers, thus closing a gap between theory and practice. We show that actor-critic updates projected on a ball around the initial condition will converge to a neighborhood where the average of the squared gradients is $\tilde{O} \left( 1/\sqrt{m} \right) + O \left( \epsilon \right)$, with $m$ being the width of the neural network and $\epsilon$ the approximation quality of the best critic neural network over the projected set.

Motivated by the challenge of nonstationarity in sequential decision making, we study Online Convex Optimization (OCO) under the coupling of two problem structures: the domain is unbounded, and the comparator sequence $u_1,\ldots,u_T$ is arbitrarily time-varying. As no algorithm can guarantee low regret simultaneously against all comparator sequences, handling this setting requires moving from minimax optimality to comparator adaptivity. That is, sensible regret bounds should depend on certain complexity measures of the comparator relative to one's prior knowledge. This paper achieves a new type of such adaptive regret bounds leveraging a sparse coding framework. The complexity of the comparator is measured by its energy and its sparsity on a user-specified dictionary, which offers considerable versatility. For example, equipped with a wavelet dictionary, our framework improves the state-of-the-art bound (Jacobsen & Cutkosky, 2022) by adapting to both ($i$) the magnitude of the comparator average $||\bar u||=||\sum_{t=1}^Tu_t/T||$, rather than the maximum $\max_t||u_t||$; and ($ii$) the comparator variability $\sum_{t=1}^T||u_t-\bar u||$, rather than the uncentered sum $\sum_{t=1}^T||u_t||$. Furthermore, our proof is simpler due to decoupling function approximation from regret minimization.

We consider the problem of tracking an adversarial state sequence in a linear dynamical system subject to adversarial disturbances and loss functions, generalizing earlier settings in the literature. To this end, we develop three techniques, each of independent interest. First, we propose a comparator-adaptive algorithm for online linear optimization with movement cost. Without tuning, it nearly matches the performance of the optimally tuned gradient descent in hindsight. Next, considering a related problem called online learning with memory, we construct a novel strongly adaptive algorithm that uses our first contribution as a building block. Finally, we present the first reduction from adversarial tracking control to strongly adaptive online learning with memory. Summarizing these individual techniques, we obtain an adversarial tracking controller with a strong performance guarantee even when the reference trajectory has a large range of movement.

Unconstrained Online Linear Optimization (OLO) is a practical problem setting to study the training of machine learning models. Existing works proposed a number of potential-based algorithms, but in general the design of these potential functions relies heavily on guessing. To streamline this workflow, we present a framework that generates new potential functions by solving a Partial Differential Equation (PDE). Specifically, when losses are 1-Lipschitz, our framework produces a novel algorithm with anytime regret bound $C\sqrt{T}+||u||\sqrt{2T}[\sqrt{\log(1+||u||/C)}+2]$, where $C$ is a user-specified constant and $u$ is any comparator unknown and unbounded a priori. Such a bound attains an optimal loss-regret trade-off without the impractical doubling trick. Moreover, a matching lower bound shows that the leading order term, including the constant multiplier $\sqrt{2}$, is tight. To our knowledge, the proposed algorithm is the first to achieve such optimalities.

Practical online learning tasks are often naturally defined on unconstrained domains, where optimal algorithms for general convex losses are characterized by the notion of comparator adaptivity. In this paper, we design such algorithms in the presence of switching cost - the latter penalizes the typical optimism in adaptive algorithms, leading to a delicate design trade-off. Based on a novel dual space scaling strategy discovered by a continuous-time analysis, we propose a simple algorithm that improves the existing comparator adaptive regret bound [ZCP22a] to the optimal rate. The obtained benefits are further extended to the expert setting, and the practicality of the proposed algorithm is demonstrated through a sequential investment task.

OBJECTIVE: To develop predictive models of coronavirus disease 2019 (COVID-19) outcomes, elucidate the influence of socioeconomic factors, and assess algorithmic racial fairness using a racially diverse patient population with high social needs. MATERIALS AND METHODS: Data included 7,102 patients with positive (RT-PCR) severe acute respiratory syndrome coronavirus 2 test at a safety-net system in Massachusetts. Linear and nonlinear classification methods were applied. A score based on a recurrent neural network and a transformer architecture was developed to capture the dynamic evolution of vital signs. Combined with patient characteristics, clinical variables, and hospital occupancy measures, this dynamic vital score was used to train predictive models. RESULTS: Hospitalizations can be predicted with an area under the receiver-operating characteristic curve (AUC) of 92% using symptoms, hospital occupancy, and patient characteristics, including social determinants of health. Parsimonious models to predict intensive care, mechanical ventilation, and mortality that used the most recent labs and vitals exhibited AUCs of 92.7%, 91.2%, and 94%, respectively. Early predictive models, using labs and vital signs closer to admission had AUCs of 81.1%, 84.9%, and 92%, respectively. DISCUSSION: The most accurate models exhibit racial bias, being more likely to falsely predict that Black patients will be hospitalized. Models that are only based on the dynamic vital score exhibited accuracies close to the best parsimonious models, although the latter also used laboratories. CONCLUSIONS: This large study demonstrates that COVID-19 severity may accurately be predicted using a score that accounts for the dynamic evolution of vital signs. Further, race, social determinants of health, and hospital occupancy play an important role.

It is infeasible to test many different chemotherapy drugs on actual patients in large clinical trials, which motivates computational methods with the ability to learn and exploit associations between drug effectiveness and patient characteristics. This work proposes a machine learning approach to infer robust predictors of drug responses from patient genomic information. Rather than predicting the exact drug response on a given cell line, we introduce an elastic-net regression methodology to compare a drug-cell line pair against an alternative pair. Using predicted pairwise comparisons we rank the effectiveness of different drugs on the same cell line. A total of 173 cell lines and 100 drug responses were used in various settings for training and testing the proposed models. By comparing our approach against twelve baseline methods, we demonstrate that it outperforms the state-of-the-art methods in the literature. In contrast to most other methods, the algorithm is able to maintain its high performance even when we use a large number of drugs and few cell lines.

This paper studies congestion-aware route-planning policies for intermodal Autonomous Mobility-on-Demand (AMoD) systems, whereby a fleet of autonomous vehicles provides on-demand mobility jointly with public transit under mixed traffic conditions (consisting of AMoD and private vehicles). First, we devise a network flow model to jointly optimize the AMoD routing and rebalancing strategies in a congestion-aware fashion by accounting for the endogenous impact of AMoD flows on travel time. Second, we capture the effect of exogenous traffic stemming from private vehicles adapting to the AMoD flows in a user-centric fashion by leveraging a sequential approach. Since our results are in terms of link flows, we then provide algorithms to retrieve the explicit recommended routes to users. Finally, we showcase our framework with two case-studies considering the transportation sub-networks in Eastern Massachusetts and New York City, respectively. Our results suggest that for high levels of demand, pure AMoD travel can be detrimental due to the additional traffic stemming from its rebalancing flows. However, blending AMoD with public transit, walking and micromobility options can significantly improve the overall system performance by leveraging the high-throughput of public transit combined with the flexibility of walking and micromobility.

Demand response programs help stabilize the electricity grid by providing monetary stimulus to consumers if they regulate their power consumption following market requirements. Regulation service, a market that requires participants to regulate power by following a signal updated every few seconds, is particularly beneficial to HPC data centers since data centers are capable of increasing/decreasing power consumption owing to the flexibility in running workloads and the availability of power control mechanisms. While prior works have explored how data centers can provide regulation service reserves, Quality-of-Service (QoS) provisioning for the jobs running at the data centers has not been considered. In this work, we propose an Adaptive policy with QoS Assurance that enables data centers to participate in regulation service programs with assurance on job QoS. Our policy regulates data center power through job scheduling and server power capping. QoS assurance is achieved by applying a queueing-theoretic result to our job scheduling strategy. We evaluate our policy by experiments on a real cluster. Our results demonstrate that the proposed policy reduces electricity costs by 25-56% while providing QoS assurance. On the other hand, the baseline policies cannot meet QoS constraints in 9 of the 14 workload traces tested.

In order for reinforcement learning techniques to be useful in real-world decision making processes, they must be able to produce robust performance from limited data. Deep policy optimization methods have achieved impressive results on complex tasks, but their real-world adoption remains limited because they often require significant amounts of data to succeed. When combined with small sample sizes, these methods can result in unstable learning due to their reliance on high-dimensional sample-based estimates. In this work, we develop techniques to control the uncertainty introduced by these estimates. We leverage these techniques to propose a deep policy optimization approach designed to produce stable performance even when data is scarce. The resulting algorithm, Uncertainty-Aware Trust Region Policy Optimization, generates robust policy updates that adapt to the level of uncertainty present throughout the learning process.

Due to recent empirical successes, the options framework for hierarchical reinforcement learning is gaining increasing popularity. Rather than learning from rewards, we consider learning an options-type hierarchical policy from expert demonstrations. Such a problem is referred to as hierarchical imitation learning. Converting this problem to parameter inference in a latent variable model, we develop convergence guarantees for the EM approach proposed by Daniel et al. (2016b). The population level algorithm is analyzed as an intermediate step, which is nontrivial due to the samples being correlated. If the expert policy can be parameterized by a variant of the options framework, then, under regularity conditions, we prove that the proposed algorithm converges with high probability to a norm ball around the true parameter. To our knowledge, this is the first performance guarantee for an hierarchical imitation learning algorithm that only observes primitive state-action pairs.

Demand response programs offer an opportunity for large power consumers to save on electricity costs by modulating their power consumption in response to demand changes in the electricity grid. Multiple types of such programs exist; for example, regulation service programs enable a consumer to bid for a sustainable amount of power draw over a time period, along with a reserve amount they are able to provide at request of the electricity service provider. Data centers offer unique capabilities to participate in these programs since they have significant capacity to modify their power consumption through workload scheduling and CPU power limiting. This paper proposes a novel power management policy and a bidding policy that enable data centers to participate in regulation service programs under real-world constraints. The power management policy schedules computing jobs and applies server power-capping under both the constraints of power programs and the constraints of job Quality-of-Service (QoS). Simulations with workload traces from a real data center show that the proposed policies enable data centers to meet both the requirement of regulation service programs and the QoS requirement of jobs. We demonstrate that, by applying our policies, data centers can save their electricity costs by 10% while abiding by all the QoS constraints in a real-world scenario.

In real-world decision making tasks, it is critical for data-driven reinforcement learning methods to be both stable and sample efficient. On-policy methods typically generate reliable policy improvement throughout training, while off-policy methods make more efficient use of data through sample reuse. In this work, we combine the theoretically supported stability benefits of on-policy algorithms with the sample efficiency of off-policy algorithms. We develop policy improvement guarantees that are suitable for the off-policy setting, and connect these bounds to the clipping mechanism used in Proximal Policy Optimization. This motivates an off-policy version of the popular algorithm that we call Generalized Proximal Policy Optimization with Sample Reuse. We demonstrate both theoretically and empirically that our algorithm delivers improved performance by effectively balancing the competing goals of stability and sample efficiency.

We consider speeding up stochastic gradient descent (SGD) by parallelizing it across multiple workers. We assume the same data set is shared among $N$ workers, who can take SGD steps and coordinate with a central server. While it is possible to obtain a linear reduction in the variance by averaging all the stochastic gradients at every step, this requires a lot of communication between the workers and the server, which can dramatically reduce the gains from parallelism.The Local SGD method, proposed and analyzed in the earlier literature, suggests machines should make many local steps between such communications. While the initial analysis of Local SGD showed it needs $\Omega ( \sqrt{T} )$ communications for $T$ local gradient steps in order for the error to scale proportionately to $1/(NT)$, this has been successively improved in a string of papers, with the state of the art requiring $\Omega \left( N \left( \mbox{ poly} (\log T) \right) \right)$ communications. In this paper, we suggest a Local SGD scheme that communicates less overall by communicating less frequently as the number of iterations grows. Our analysis shows that this can achieve an error that scales as $1/(NT)$ with a number of communications that is completely independent of $T$. In particular, we show that $\Omega(N)$ communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that $\sqrt{N}$ or $N^{3/4}$ communications fail to achieve linear speed-up in simulations. Moreover, we show that under mild assumptions, the main of which is twice differentiability on any neighborhood of the optimal solution, one-shot averaging which only uses a single round of communication can also achieve the optimal convergence rate asymptotically.

Domain knowledge is important for building Natural Language Processing (NLP) systems for low-resource settings, such as in the clinical domain.In this paper, a novel joint training method is introduced for adding knowledge base information from the Unified Medical Language System (UMLS) into language model pre-training for some clinical domain corpus.We show that in three different downstream clinical NLP tasks, our pre-trained language model outperforms the corresponding model with no knowledge base information and other state-of-the-art models.Specifically, in a natural language inference task applied to clinical texts, our knowledge base pre-training approach improves accuracy by up to 1.7%, whereas in clinical name entity recognition tasks, the F1-score improves by up to 1.0%.The pre-trained models are available at https://github.com/noc-lab/clinical-kb-bert.

We consider the standard model of distributed optimization of a sum of functions $F(\mathbf z) = \sum_{i=1}^n f_i(\mathbf z)$, where node $i$ in a network holds the function $f_i(\mathbf z)$. We allow for a harsh network model characterized by asynchronous updates, message delays, unpredictable message losses, and directed communication among nodes. In this setting, we analyze a modification of the Gradient-Push method for distributed optimization, assuming that (i) node $i$ is capable of generating gradients of its function $f_i(\mathbf z)$ corrupted by zero-mean bounded-support additive noise at each step, (ii) $F(\mathbf z)$ is strongly convex, and (iii) each $f_i(\mathbf z)$ has Lipschitz gradients. We show that our proposed method asymptotically performs as well as the best bounds on centralized gradient descent that takes steps in the direction of the sum of the noisy gradients of all the functions $f_1(\mathbf z), \ldots, f_n(\mathbf z)$ at each step.

We develop a method to learn a bio-inspired motion control policy using data collected from hawkmoths navigating in a virtual forest. A Markov Decision Process (MDP) framework is introduced to model the dynamics of moths and sparse logistic regression is used to learn control policy parameters from the data. The results show that moths do not favor detailed obstacle location information in navigation, but rely heavily on optical flow. Using the policy learned from the moth data as a starting point, we propose an actor-critic learning algorithm to refine policy parameters and obtain a policy that can be used by an autonomous aerial vehicle operating in a cluttered environment. Compared with the moths' policy, the policy we obtain integrates both obstacle location and optical flow. We compare the performance of these two policies in terms of their ability to navigate in artificial forest areas. While the optimized policy can adjust its parameters to outperform the moth's policy in each different terrain, the moth's policy exhibits a high level of robustness across terrains.

This paper develops a prediction-based prescriptive model for optimal decision making that (i) predicts the outcome under each action using a robust nonlinear model, and (ii) adopts a randomized prescriptive policy determined by the predicted outcomes. The predictive model combines a new regularized regression technique, which was developed using Distributionally Robust Optimization (DRO) with an ambiguity set constructed from the Wasserstein metric, with the K-Nearest Neighbors (K-NN) regression, which helps to capture the nonlinearity embedded in the data. We show theoretical results that guarantee the out-of-sample performance of the predictive model, and prove the optimality of the randomized policy in terms of the expected true future outcome. We demonstrate the proposed methodology on a hypertension dataset, showing that our prescribed treatment leads to a larger reduction in the systolic blood pressure compared to a series of alternatives. A clinically meaningful threshold level used to activate the randomized policy is also derived under a sub-Gaussian assumption on the predicted outcome.

We present a Distributionally Robust Optimization (DRO) approach to estimate a robustified regression plane in a linear regression setting, when the observed samples are potentially contaminated with adversarially corrupted outliers. Our approach mitigates the impact of outliers by hedging against a family of probability distributions on the observed data, some of which assign very low probabilities to the outliers. The set of distributions under consideration are close to the empirical distribution in the sense of the Wasserstein metric. We show that this DRO formulation can be relaxed to a convex optimization problem which encompasses a class of models. By selecting proper norm spaces for the Wasserstein metric, we are able to recover several commonly used regularized regression models. We provide new insights into the regularization term and give guidance on the selection of the regularization coefficient from the standpoint of a confidence region. We establish two types of performance guarantees for the solution to our formulation under mild conditions. One is related to its out-of-sample behavior (prediction bias), and the other concerns the discrepancy between the estimated and true regression planes (estimation bias). Extensive numerical results demonstrate the superiority of our approach to a host of regression models, in terms of the prediction and estimation accuracies. We also consider the application of our robust learning procedure to outlier detection, and show that our approach achieves a much higher AUC (Area Under the ROC Curve) than M-estimation (Huber, 1964, 1973).

Urban living in modern large cities has significant adverse effects on health, increasing the risk of several chronic diseases. We focus on the two leading clusters of chronic diseases, heart disease and diabetes, and develop data-driven methods to predict hospitalizations due to these conditions. We base these predictions on the patients' medical history, recent and more distant, as described in their Electronic Health Records (EHRs). We formulate the prediction problem as a binary classification problem and consider a variety of machine learning methods, including kernelized and sparse Support Vector Machines (SVMs), sparse logistic regression, and random forests. To strike a balance between accuracy and interpretability of the prediction, which is important in a medical setting, we propose two novel methods: K -LRT, a likelihood ratio test-based method, and a Joint Clustering and Classification (JCC) method which identifies hidden patient clusters and adapts classifiers to each cluster. We develop theoretical out-of-sample guarantees for the latter method. We validate our algorithms on large data sets from the Boston Medical Center, the largest safety-net hospital system in New England.

Among the many functions a smart city must support, transportation dominates in terms of resource consumption, strain on the environment, and frustration of its citizens. We study transportation networks under two different routing policies, the commonly assumed selfish user-centric routing policy and a socially optimal system-centric one. We consider a performance metric of efficiency-the Price of Anarchy (PoA)-defined as the ratio of the total travel latency cost under selfish routing over the corresponding quantity under socially optimal routing. We develop a data-driven approach to estimate the PoA, which we subsequently use to conduct a case study using extensive actual traffic data from the Eastern Massachusetts road network. To estimate the PoA, our approach learns from data a complete model of the transportation network, including origin-destination demand and user preferences. We leverage this model to propose possible strategies to reduce the PoA and increase efficiency.

We investigate the cooperative pursuit of an evader by a group of quadrotors in an environment with no-fly zones. While the pursuers cannot enter into no-fly zones, the evader may freely move through zones to avoid capture. Once the evader enters a no-fly zone, the pursuers calculate a reachable set of evader positions. Using tools from Voronoi-based coverage control applied to the evader's reachable set, we provide an algorithm that distributes the pursuers around the zone's boundary and minimizes the capture time once the evader leaves the no-fly zone. Robust model predictive control (RMPC) tools are used to control the quadrotors and to ensure that they always remain in free space. We demonstrate the performance of our proposed algorithms through a series of experiments on KMEL Nano+ quadrotors.

We consider scheduling in wireless networks and formulate it as Maximum Weighted Independent Set (MWIS) problem on a "conflict" graph that captures interference among simultaneous transmissions. We propose a novel, low-complexity, and fully distributed algorithm that yields high-quality feasible solutions. Our proposed algorithm consists of two phases, each of which requires only local information and is based on message-passing. The first phase solves a relaxation of the MWIS problem using a gradient projection method. The relaxation we consider is tighter than the simple linear programming relaxation and incorporates constraints on all cliques in the graph. The second phase of the algorithm starts from the solution of the relaxation and constructs a feasible solution to the MWIS problem. We show that our algorithm always outputs an optimal solution to the MWIS problem for perfect graphs. Simulation results compare our policies against Carrier Sense Multiple Access (CSMA) and other alternatives and show excellent performance.

We consider the problem of detecting the formation of a set of wireless sensor nodes based on the pairwise measurements of signal strength corresponding to all transmitter/receiver pairs. We assume that formations take values in a discrete set and develop a composite hypothesis testing approach which uses a Generalized Likelihood Test (GLT) as the decision rule. The GLT distinguishes between a set of probability density function (pdf) families constructed using a custom pdf interpolation technique. The GLT is compared with the simple Likelihood Test (LT). We also adapt one prevalent supervised learning approach, Multiple Support Vector Machines (MSVMs), and compare it with our probabilistic methods. Due to the highly variant measurements from the wireless sensor nodes, and these methods' different adaptability to multiple observations, our analysis and experimental results suggest that GLT is more accurate and suitable for formation detection. The formation detection problem has interesting applications in posture detection with Wireless Body Area Networks (WBANs), which is extremely useful in health monitoring and rehabilitation. Another valuable application we explore concerns autonomous robot systems.

Message ferrying has been shown to be an effective approach to support routing in sparse ad hoc or sensor networks. Considering a generic network model where each node in the network wishes to send data to some (or possibly all) other nodes with known (and possibly different) rates, we propose three schemes enabling multiple ferries to coordinate in collecting and delivering the data. We analyze the performance of each scheme and establish bounds on the average and worst-case delay. The latter bounds are useful in offering performance guarantees. We establish that under one of our schemes, constant per-node throughput is achievable within constant maximum (worst-case) delay as the network size grows. Using simulation, we compare our proposed schemes with an alternative, the Ferry Relaying algorithm proposed earlier in the literature. The results show that our schemes perform better and provide guidance on which scheme to use given performance preferences and the number of available ferries.

We present a novel methodology for chemical, biological, radiological, or nuclear (CBRN) source localization in urban environments. Our approach uses only information reported by CBRN sensors monitoring the environment and thus does not rely on solving any challenging inverse plume dispersion problems. We illustrate and evaluate our technique using three-dimensional CBRN release simulations.

In this paper, we consider the problem of deploying a robot from a specification given as a temporal logic statement about some properties satisfied by the regions of a large, partitioned environment. We assume that the robot has noisy sensors and actuators and model its motion through the regions of the environment as a Markov Decision Process (MDP). The robot control problem becomes finding the control policy maximizing the probability of satisfying the temporal logic task on the MDP. For a large environment, obtaining transition probabilities for each state-action pair, as well as solving the necessary optimization problem for the optimal policy are usually not computationally feasible. To address these issues, we propose an approximate dynamic programming framework based on a least-square temporal difference learning method of the actor-critic type. This framework operates on sample paths of the robot and optimizes a randomized control policy with respect to a small set of parameters. The transition probabilities are obtained only when needed. Hardware-in-the-loop simulations confirm that convergence of the parameters translates to an approximately optimal policy.

We present a novel probabilistic framework for reliable indoor positioning of mobile sensor network devices. Compared to existing approaches, ours adopts complex computations in exchange for high localization accuracy while needing low hardware investment and moderate set-up cost. To that end, we use full distributional information on signal measurements at a set of discrete locations, termed landmarks. Positioning of a mobile device is done relative to the resulting landmark graph and the device can be found near a landmark or in the area between two landmarks. Key elements of our approach include profiling the signal measurement distributions over the coverage area using a special interpolation technique; a two-tier statistical positioning scheme that improves efficiency by adding movement detection; and joint clusterhead placement optimization for both localization and movement detection. The proposed system is practical and has been implemented using standard wireless sensor network hardware. Experimentally, our system achieved an accuracy equivalent to less than 5 meters with 95 percent success probability and less than 3 meters with an 87 percent success probability. This performance is superior to well-known contemporary systems that use similar low-cost hardware.

Using mobile elements as mechanical carriers of data has been shown to be an effective way of prolonging sensor network lifetime and of relaying data in partitioned networks. The existing literature has mostly focused on designing delay minimizing routes for the mobile elements by leveraging variants of the Traveling Salesman Problem (TSP). We show that TSP-based routes can in fact result in data delivery delay arbitrarily worse than that of the optimal solution. The main insight is that as the data generation rates of sensors may vary, some sensors need to be visited more frequently than others. To that end, we consider a network with a single sink and develop a Path Splitter algorithm that “splits” a TSP-based route into several loops intersecting at the sink. Numerical results show that our algorithm can improve average delay by more than 40% in some instances while requiring a modest computational effort to modify the TSP-based route.

The authors report on a successful deployment of an inexpensive mobile wireless sensor network in a commercial warehouse served by a fleet of forklifts. The aim is to improve forklift dispatching and reduce the costs associated with the delays of loading/unloading delivery trucks. To that end, an integrated system including both hardware and software is constructed. First, the forklifts are instrumented with sensor nodes that collect an array of information, including the forklifts' physical location, usage time, bumping/collision history, and battery status. The hardware's capability is enhanced with a theoretically sound hypothesis testing technique to capture the rather elusive location information, and the collection of the data is done in an efficient event-driven manner. The information acquired combined with inventory information is fed into a sophisticated actor-critic type stochastic learning method to generate dispatching recommendations. Because noise is inevitable in such wireless sensor networks, the performance of the algorithm is investigated under different noise levels. In combining wireless sensing with state-of-the-art decision theory, this work extends beyond the standard use of wireless sensor networks as monitoring devices.

We seek to detect statistically significant temporal or spatial changes in either the underlying process the sensor network is monitoring or in the network operation itself. These changes may point to faults, adversarial threats, misbehavior, or other anomalies that require intervention. To that end, we introduce a new statistical anomaly detection framework that uses Markov models to characterize the “normal” behavior of the sensor network. We develop a series of Markov models, including tree-indexed Markov chains which can model its spatial structure. For each model, an anomaly-free probability law is estimated from past traces. We leverage large deviations techniques to develop optimal anomaly detection rules for each corresponding Markov model, assessing whether its most recent empirical measure is consistent with the anomaly-free probability law. A series of simulation results, some with real sensor data, validate the effectiveness of the proposed anomaly detection algorithms.

We present a robust localization system allowing wireless sensor networks to determine the physical location of their nodes. The coverage area is partitioned into regions and we seek to identify the region of a sensor based on observations by stationary clusterheads. Observations (e.g., signal strength) are assumed random. We pose the localization problem as a composite multihypothesis testing problem, develop the requisite theory, and address the problem of optimally placing clusterheads. We show that localization decisions can be distributed by appropriate in-network processing. The approach is validated in a testbed yielding promising results.

We consider wireless sensor networks with multiple frequency channels, multiple gateways and multiple classes of traffic carrying data generated by different sensory inputs. The objective is to devise joint routing and transmission scheduling policies in order to gather data in the most efficient manner while respecting the needs of different sensing tasks (fairness). We formulate the problem as maximizing the utility of transmissions subject to explicit fairness constraints and propose a decomposition algorithm drawing upon large-scale decomposition ideas in mathematical programming. We show that our algorithm terminates in a finite number of iterations. Every iteration requires the solution of a subproblem which is NP-hard. To solve the subproblem we (i) devise a particular relaxation that is solvable in polynomial time and (ii) leverage polynomial time approximation schemes. A combination of both approaches enables an improved decomposition algorithm which is much more efficient for solving large problem instances.

Similarly to protein folding, the association of two proteins is driven by a free energy funnel, determined by favorable interactions in some neighborhood of the native state. We describe a docking method based on stochastic global minimization of funnel-shaped energy functions in the space of rigid body motions (SE(3)) while accounting for flexibility of the interface side chains. The method, called semi-definite programming-based underestimation (SDU), employs a general quadratic function to underestimate a set of local energy minima and uses the resulting underestimator to bias further sampling. While SDU effectively minimizes functions with funnel-shaped basins, its application to docking in the rotational and translational space SE(3) is not straightforward due to the geometry of that space. We introduce a strategy that uses separate independent variables for side-chain optimization, center-to-center distance of the two proteins, and five angular descriptors of the relative orientations of the molecules. The removal of the center-to-center distance turns out to vastly improve the efficiency of the search, because the five-dimensional space now exhibits a well-behaved energy surface suitable for underestimation. This algorithm explores the free energy surface spanned by encounter complexes that correspond to local free energy minima and shows similarity to the model of macromolecular association that proceeds through a series of collisions. Results for standard protein docking benchmarks establish that in this space the free energy landscape is a funnel in a reasonably broad neighborhood of the native state and that the SDU strategy can generate docking predictions with less than 5 A ligand interface C(alpha) root-mean-square deviation while achieving an approximately 20-fold efficiency gain compared to Monte Carlo methods.

We consider wireless sensor networks with nodes switching ON (awake) and OFF (sleeping) to preserve energy, and transmitting data over channels with varying quality. The objective is to determine the best path from each node to a single gateway. The performance metrics we are interested in are: the expected energy consumption, and the probability that the latency exceeds a certain threshold. Under Markovian assumptions on the sleeping schedules and the channel conditions, we obtain the expected energy consumption of transmitting a packet on any path to the gateway. We also provide an upper (Chernoff) bound and a tight large deviations asymptotic for the latency probability on each path. To capture the trade-off between energy consumption and latency probability, we formulate the problem of choosing a path to minimize a weighted sum of the expected energy consumption and the exponent of the latency probability. We provide two algorithms to solve this problem: a centralized stochastic global optimization algorithm, and a distributed algorithm based on simulated annealing. The proposed methodology can also optimize over the fraction of time that sensor nodes remain ON (duty cycle).

We consider wireless sensor networks with nodes switching ON (awake) and OFF (sleeping) to preserve energy, and transmitting data over channels with varying quality. The objective is to determine the best path from each node to a single gateway. Performance metrics of interest are: the expected energy consumption and the probability that the latency exceeds a certain threshold. Under Markovian assumptions on the sleeping schedules and the channel conditions, we obtain the expected energy consumption of transmitting a packet on any path to the gateway. We also provide an upper (Chernoff) bound and a tight large deviations asymptotic for the latency probability on each path. To capture the trade-off between energy consumption and latency probability we formulate the problem of choosing a path to minimize a weighted sum of the expected energy consumption and the exponent of the latency probability. We provide two algorithms to solve this problem: a centralized stochastic global optimization algorithm and a distributed algorithm based on simulated annealing. The proposed methodology can also optimize over the fraction of time sensor nodes remain ON (duty cycle).

The paper develops a systematic framework for designing a stochastic location detection system with associated performance guarantees using a wireless sensor network. To detect the location of a mobile sensor, the system relies on RF-characteristics of the signal transmitted by the mobile sensor, as it is received by stationary sensors (clusterheads). Location detection is posed as a hypothesis testing problem over a discretized space. Large deviations results enable the characterization of the probability of error leading to a placement problem that maximizes an information-theoretic distance (Chernoff distance) among all pairs of probability distributions of observations conditional on the sensor locations. The placement problem is shown to be NP-hard and is formulated as a linear integer programming problem; yet, large instances can be solved efficiently by leveraging special-purpose algorithms from the theory of discrete facility location. The resultant optimal placement is shown to provide asymptotic guarantees on the probability of error in location detection under quite general conditions by minimizing an upper bound of the error-exponent. Numerical results show that the proposed framework is computationally feasible and the resultant clusterhead placement performs near-optimal even with a small number of observation samples in a simulation environment.

We consider wireless sensor networks with multiple gateways and multiple classes of traffic carrying data generated by different sensory inputs. The objective is to devise joint routing, power control and transmission scheduling policies in order to gather data in the most efficient manner while respecting the needs of different sensing tasks (fairness). We formulate the problem as maximizing the utility of transmissions subject to explicit fairness constraints. We propose an efficient decomposition algorithm drawing upon large-scale decomposition ideas in mathematical programming. We show that our algorithm terminates in a finite number of iterations and produces a policy that is asymptotically optimal at low transmission power levels. Moreover, numerical results establish that this policy is near-optimal even at high power levels. We also demonstrate how to adapt our algorithm to accommodate energy constraints and node failures. The approach we introduce can efficiently determine near-optimal transmission policies for dramatically larger problem instances than an alternative enumeration approach.

We propose a systematic framework for designing a stochastic indoor location detection system with associated performance guarantees using a hierarchical wireless sensor network. To detect the location of a mobile sensor, we rely on RF-characteristics of the signal transmitted by the mobile sensor, as it is received by the clusterheads. The problem of location detection is posed as a hypothesis testing problem over a discretized space. We leverage large deviations and decision theory results to characterize the probability of error and use this characterization to optimally place clusterheads. The placement problem is NP-hard and we formulate it as a linear integer programming problem. We leverage special-purpose algorithms from the theory of discrete facility location to solve large problem instances efficiently. For the resultant placement we provide asymptotic guarantees on the probability of error in location detection under quite general conditions. Numerical and simulation results show that our proposed framework is computationally feasible and the resultant clusterhead placement performs near-optimum even with a small number of observation samples.

We develop an importance sampling technique that can be used to speed up the simulation of a model of a buffered communication multiplexer fed by a large number of independent sources. The sources generate traffic according to a periodic function with a random phase. This traffic model accommodates a wide range of situations of practical interest, including ON-OFF periodic traffic models and sequences of bit rates generated by actual variable bit rate sources, such as MPEG video compressors. The simulation seeks to obtain estimates for the buffer overflow probability that in most cases of interest is very small. We use a large deviations result to devise the change of measure used in the importance sampling technique and demonstrate through numerical results that this change of measure leads to a dramatic reduction in the required simulation time over direct Monte Carlo simulation. Possible practical applications include short-term network resource planning and even real-time call admission control.

A new parametric class of scheduling and routing policies for open multiclass queueing networks is proposed. We establish their stability and show they are amenable to distributed implementation using localized state information. We exploit our earlier work in (Ref.1) to select appropriate parameter values and outline how optimal parameter values can be computed. We report numerical results indicating that we obtain near-optimal policies (when the optimal can be computed) and significantly outperform heuristic alternatives.

We consider a communication network with fixed routing that can accommodate multiple service classes, differing in bandwidth requirements, demand pattern, call duration and routing. The network charges a fee per call which can depend on the current congestion level and which affects user's demand. Building on the single-node results of I.Ch. Paschalidis and J.N. Tsitsiklis (see IEEE/ACM Trans. Networking, vol.8, p.171-84, 2000), we consider both problems of revenue and of welfare maximization, and show that static pricing is asymptotically optimal in a regime of many, relatively small, users. In particular, the performance of an optimal (dynamic) pricing strategy is closely matched by a suitably chosen class-dependent static price, which does not depend on instantaneous congestion. This result holds even when we incorporate demand substitution effects into the demand model. More specifically, we model the situation where price increases for a class of service might lead users to use another class as an imperfect substitute. For both revenue and welfare maximization objectives we characterize the structure of the asymptotically optimal static prices, expressing them as a function of a parsimonious number of parameters. We employ a simulation-based approach to tune those parameters and to compute efficiently an effective policy away from the limiting regime. Our approach can handle large, realistic, instances of the problem.

We propose estimators of the buffer overflow probability in queues fed by a Markov-modulated input process and serviced by an autocorrelated service process. These estimators are based on large-deviations asymptotics for the overflow probability. We demonstrate that the proposed estimators are less likely to underestimate the overflow probability than the estimator obtained by certainty equivalence. As such, they are appropriate in situations where the overflow probability is associated with quality of service (QoS) and we need to provide firm QoS guarantees. We also show that as the number of observations increases to infinity the proposed estimators converge with probability one to the appropriate target, and thus, do not lead to underutilization of the system in this limit.

We consider a service provider (SP) who provides access to a communication network or some other form of on-line services. Users initiate calls that belong to a set of diverse service classes, differing in resource requirements, demand pattern, and call duration. The SP charges a fee per call, which can depend on the current congestion level, and which affects users' demand for calls. We provide a dynamic programming formulation of the problems of revenue and welfare maximization, and derive some qualitative properties of the optimal solution. We also provide a number of approximate approaches, together with an analysis that indicates that near-optimality is obtained for the case of many, relatively small, users. In particular, we show analytically as well as computationally, that the performance of an optimal pricing strategy is closely matched by a suitably chosen static price, which does not depend on instantaneous congestion. This indicates that the easily implementable time-of-day pricing will often suffice. Throughout, we compare the alternative formulations involving revenue or welfare maximization, respectively, and draw some qualitative conclusions.

The authors propose a new policy to prevent congestion phenomena in asynchronous transfer mode (ATM) networks. In particular, using a synthesis approach, they define and calculate the bandwidth which is assigned to every acceptable source from the ATM network. This bandwidth, which varies between the peak and the average bandwidth demands of the particular source, is called effective or virtual, and is mainly characterized from the burstiness of the source. In constant bit rate sources the effective bandwidth is equal to the peak rate. Based on the concept of effective bandwidth, a connection acceptance algorithm that leads to a very high utilization of network resources is formulated.>