Conditional demographic parity (CDP) is a measure of the demographic parity of a predictive model or decision process when conditioning on an additional feature or set of features. Many algorithmic fairness techniques exist to target demographic parity, but CDP is much harder to achieve, particularly when the conditioning variable has many levels and/or when the model outputs are continuous. The problem of auditing and enforcing CDP is understudied in the literature. In light of this, we propose novel measures of conditional demographic disparity (CDD) which rely on statistical distances borrowed from the optimal transport literature. We further design and evaluate regularization-based approaches based on these CDD measures. Our methods, FairBiT and FairLeap, allow us to target conditional demographic parity even when the conditioning variable has many levels. When model outputs are continuous, our methods target full equality of the conditional distributions, unlike other methods that only consider first moments or related proxy quantities. We validate our approaches on real-world datasets.

Recent advancements in language modeling have shown promising results when applied to time series data.In particular, fine-tuning pretrained large language models (LLMs) for time series classification tasks has achieved state-ofthe-art (SOTA) performance on standard benchmarks.However, these LLM-based models have a significant drawback due to the large model size, with the number of trainable parameters in the millions.In this paper, we propose an alternative approach to leveraging the success of language modeling in the time series domain.Instead of fine-tuning LLMs, we utilize a text embedding model to embed time series and then pair the embeddings with a simple classification head composed of convolutional neural networks (CNN) and multilayer perceptron (MLP).We conducted extensive experiments on a well-established time series classification benchmark.We demonstrated LETS-C not only outperforms the current SOTA in classification accuracy but also offers a lightweight solution, using only 14.5% of the trainable parameters on average compared to the SOTA model.Our findings suggest that leveraging text embedding models to encode time series data, combined with a simple yet effective classification head, offers a promising direction for achieving high-performance time series classification while maintaining a lightweight model architecture.

State-of-the-art multimodal web agents, powered by Multimodal Large Language Models (MLLMs), can autonomously execute many web tasks by processing user instructions and interacting with graphical user interfaces (GUIs). Current strategies for building web agents rely on (i) the generalizability of underlying MLLMs and their steerability via prompting, and (ii) large-scale fine-tuning of MLLMs on web-related tasks. However, web agents still struggle to automate tasks on unseen websites and domains, limiting their applicability to enterprise-specific and proprietary platforms. Beyond generalization from large-scale pre-training and fine-tuning, we propose building agents for few-shot adaptability using human demonstrations. We introduce the AdaptAgent framework that enables both proprietary and open-weights multimodal web agents to adapt to new websites and domains using few human demonstrations (up to 2). Our experiments on two popular benchmarks — Mind2Web & VisualWebArena — show that using in-context demonstrations (for proprietary models) or meta-adaptation demonstrations (for meta-learned open-weights models) boosts task success rate by 3.36% to 7.21% over non-adapted state-of-the-art models, corresponding to a relative increase of 21.03% to 65.75%. Furthermore, our additional analyses (a) show the effectiveness of multimodal demonstrations over text-only ones, (b) illuminate how different meta-learning data selection strategies influence the agent’s generalization, and (c) demonstrate how the number of few-shot examples affects the web agent’s success rate. Our results offer a complementary axis for developing widely applicable multimodal web agents beyond large-scale pre-training and fine-tuning, emphasizing few-shot adaptability.

Adversarially robust optimization (ARO) has emerged as the *de facto* standard for training models that hedge against adversarial attacks in the test stage. While these models are robust against adversarial attacks, they tend to suffer severely from overfitting. To address this issue, some successful methods replace the empirical distribution in the training stage with alternatives including *(i)* a worst-case distribution residing in an ambiguity set, resulting in a distributionally robust (DR) counterpart of ARO; *(ii)* a mixture of the empirical distribution with a distribution induced by an auxiliary (*e.g.*, synthetic, external, out-of-domain) dataset. Inspired by the former, we study the Wasserstein DR counterpart of ARO for logistic regression and show it admits a tractable convex optimization reformulation. Adopting the latter setting, we revise the DR approach by intersecting its ambiguity set with another ambiguity set built using the auxiliary dataset, which offers a significant improvement whenever the Wasserstein distance between the data generating and auxiliary distributions can be estimated. We study the underlying optimization problem, develop efficient solution algorithms, and demonstrate that the proposed method outperforms benchmark approaches on standard datasets.

Recent years have seen a surge of machine learning approaches aimed at reducing disparities in model outputs across different subgroups. In many settings, training data may be used in multiple downstream applications by different users, which means it may be most effective to intervene on the training data itself. In this work, we present FairWASP, a novel pre-processing approach designed to reduce disparities in classification datasets without modifying the original data. FairWASP returns sample-level weights such that the reweighted dataset minimizes the Wasserstein distance to the original dataset while satisfying (an empirical version of) demographic parity, a popular fairness criterion. We show theoretically that integer weights are optimal, which means our method can be equivalently understood as duplicating or eliminating samples. FairWASP can therefore be used to construct datasets which can be fed into any classification method, not just methods which accept sample weights. Our work is based on reformulating the pre-processing task as a large-scale mixed-integer program (MIP), for which we propose a highly efficient algorithm based on the cutting plane method. Experiments demonstrate that our proposed optimization algorithm significantly outperforms state-of-the-art commercial solvers in solving both the MIP and its linear program relaxation. Further experiments highlight the competitive performance of FairWASP in reducing disparities while preserving accuracy in downstream classification settings.

Large Language Models (LLMs) offer the potential for automatic time series analysis and reporting, which is a critical task across many domains, spanning healthcare, finance, climate, energy, and many more.In this paper, we propose a framework for rigorously evaluating the capabilities of LLMs on time series understanding, encompassing both univariate and multivariate forms.We introduce a comprehensive taxonomy of time series features, a critical framework that delineates various characteristics inherent in time series data.Leveraging this taxonomy, we have systematically designed and synthesized a diverse dataset of time series, embodying the different outlined features, each accompanied by textual descriptions.This dataset acts as a solid foundation for assessing the proficiency of LLMs in comprehending time series.Our experiments shed light on the strengths and limitations of stateof-the-art LLMs in time series understanding, revealing which features these models readily comprehend effectively and where they falter.In addition, we uncover the sensitivity of LLMs to factors including the formatting of the data, the position of points queried within a series and the overall time series length.Table 1: Taxonomy of time series characteristics.

Amidst escalating climate change, hurricanes are inflicting severe socioeconomic impacts, marked by heightened economic losses and increased displacement. Previous research utilized nighttime light data to predict the impact of hurricanes on economic losses. However, prior work did not provide a thorough analysis of the impact of combining different techniques for pre-processing nighttime light (NTL) data. Addressing this gap, our research explores a variety of NTL pre-processing techniques, including value thresholding, built masking, and quality filtering and imputation, applied to two distinct datasets, VSC-NTL and VNP46A2, at the zip code level. Experiments evaluate the correlation of the denoised NTL data with economic damages of Category 4-5 hurricanes in Florida. They reveal that the quality masking and imputation technique applied to VNP46A2 show a substantial correlation with economic damage data.

Data distillation and coresets have emerged as popular approaches to generate a smaller representative set of samples for downstream learning tasks to handle large-scale datasets. At the same time, machine learning is being increasingly applied to decision-making processes at a societal level, making it imperative for modelers to address inherent biases towards subgroups present in the data. While current approaches focus on creating fair synthetic representative samples by optimizing local properties relative to the original samples, their impact on downstream learning processes has yet to be explored. In this work, we present fair Wasserstein coresets ($\texttt{FWC}$), a novel coreset approach which generates fair synthetic representative samples along with sample-level weights to be used in downstream learning tasks. $\texttt{FWC}$ uses an efficient majority minimization algorithm to minimize the Wasserstein distance between the original dataset and the weighted synthetic samples while enforcing demographic parity. We show that an unconstrained version of $\texttt{FWC}$ is equivalent to Lloyd's algorithm for k-medians and k-means clustering. Experiments conducted on both synthetic and real datasets show that $\texttt{FWC}$: (i) achieves a competitive fairness-performance tradeoff in downstream models compared to existing approaches, (ii) improves downstream fairness when added to the existing training data and (iii) can be used to reduce biases in predictions from large language models (GPT-3.5 and GPT-4).

This work introduces MicroSecAgg, a framework that addresses the intricacies of secure aggregation in the single-server landscape, specifically tailored to situations where distributed trust among multiple non-colluding servers presents challenges. Our protocols are purpose-built to handle situations featuring multiple successive aggregation phases among a dynamic pool of clients who can drop out during the aggregation. Our different protocols thrive in three distinct cases: firstly, secure aggregation within a small input domain; secondly, secure aggregation within a large input domain; and finally, facilitating federated learning for the cases where moderately sized models are considered. Compared to the prior works of Bonawitz et al. (CCS 2017), Bell et al. (CCS 2020), and the recent work of Ma et al. (S&P 2023), our approach significantly reduces the overheads. In particular, MicroSecAgg halves the round complexity to just 3 rounds, thereby offering substantial improvements in communication cost efficiency. Notably, it outperforms Ma et al. by a factor of n on the user side, where n represents the number of users. Furthermore, in MicroSecAgg the computation complexity of each aggregation per user exhibits a logarithmic growth with respect to $n$, contrasting with the linearithmic or quadratic growth observed in Ma et al. and Bonawitz et al., respectively. We also require linear (in n) computation work from the server as opposed to quadratic in Bonawitz et al., or linearithmic in Ma et al. and Bell et al. In the realm of federated learning, a delicate tradeoff comes into play: our protocols shine brighter as the number of participating parties increases, yet they exhibit diminishing computational efficiency as the sheer volume of weights/parameters increases significantly. We report an implementation of our system and compare the performance against prior works, demonstrating that MicroSecAgg significantly reduces the computational burden and the message size.

A myriad of different Large Language Models (LLMs) face a common challenge in contextually analyzing table question-answering tasks.These challenges are engendered from (1) finite context windows for large tables, (2) multi-faceted discrepancies amongst tokenization patterns against cell boundaries, and (3) various limitations stemming from data confidentiality in the process of using external models such as gpt-3.5-turbo.We propose a cooperative game dubbed "HiddenTables" as a potential resolution to this challenge.In essence, "HiddenTables" is played between the code-generating LLM "Solver" and the "Oracle" which evaluates the ability of the LLM agents to solve Table QA tasks.This game is based on natural language schemas and importantly, ensures the security of the underlying data.We provide evidential experiments on a diverse set of tables that demonstrate an LLM's collective inability to generalize and perform on complex queries, handle compositional dependencies, and align natural language to programmatic commands when concrete table schemas are provided.Unlike encoderbased models, we have pushed the boundaries of "HiddenTables" to not be limited by the number of rows -therefore we exhibit improved efficiency in prompt and completion tokens.Our infrastructure has spawned a new dataset "PyQ-Tax" that spans across 116,671 question-tableanswer triplets and provides additional finegrained breakdowns & labels for varying question taxonomies.Therefore, in tandem with our academic contributions regarding LLMs' deficiency in TableQA tasks, "HiddenTables" is a tactile manifestation of how LLMs can interact with massive datasets while ensuring data security and minimizing generation costs.

Learning agent behaviors from observational data has shown to improve our understanding of their decision-making processes, advancing our ability to explain their interactions with the environment and other agents. While multiple learning techniques have been proposed in the literature, there is one particular setting that has not been explored yet: multi agent systems where agent identities remain anonymous. For instance, in financial markets labeled data that identifies market participant strategies is typically proprietary, and only the anonymous state-action pairs that result from the interaction of multiple market participants are publicly available. As a result, sequences of agent actions are not observable, restricting the applicability of existing work. In this paper, we propose a Policy Clustering algorithm, called K-SHAP, that learns to group anonymous state-action pairs according to the agent policies. We frame the problem as an Imitation Learning (IL) task, and we learn a world-policy able to mimic all the agent behaviors upon different environmental states. We leverage the world-policy to explain each anonymous observation through an additive feature attribution method called SHAP (SHapley Additive exPlanations). Finally, by clustering the explanations we show that we are able to identify different agent policies and group observations accordingly. We evaluate our approach on simulated synthetic market data and a real-world financial dataset. We show that our proposal significantly and consistently outperforms the existing methods, identifying different agent strategies.

Creation of a synthetic dataset that faithfully represents the data distribution and simultaneously preserves privacy is a major research challenge. Many space partitioning based approaches have emerged in recent years for answering statistical queries in a differentially private manner. However, for synthetic data generation problem, recent research has been mainly focused on deep generative models. In contrast, we exploit space partitioning techniques together with noise perturbation and thus achieve intuitive and transparent algorithms. We propose both data independent and data dependent algorithms for $\epsilon$-differentially private synthetic data generation whose kernel density resembles that of the real dataset. Additionally, we provide theoretical results on the utility-privacy trade-offs and show how our data dependent approach overcomes the curse of dimensionality and leads to a scalable algorithm. We show empirical utility improvements over the prior work, and discuss performance of our algorithm on a downstream classification task on a real dataset.

We introduce a secure data-independent priority queue which supports polylogarithmic-time insertion operations and constant-time deletions and read-front (aka peek) operations as opposed to the originally introduced queue by Toft (PODC '11). Moreover, we minimize the number of comparisons required to perform different operations on Toft's priority queue. Data-independent data structures—first identified explicitly by Toft, and further elaborated by Mitchell and Zimmerman (STACS '14)—serve the purpose of computing on encrypted data without executing branching code which can be used to avoid prohibitively expensive operations in secure computation applications. Focusing on the costly sorting operations, we show significant asymptotic improvements over prior privacy preserving dark pool applications. Dark pools are securities-trading venues which attain ad-hoc order privacy, by matching orders outside of publicly visible exchanges via the so-called dark pool operators. In this paper, we describe an efficient and secure dark pool (implementing a full continuous double auction) based on our new priority queue. Our construction's security guarantees are cryptographic based on secure multiparty computation (MPC), and do not require that the dark pool operators are trusted. Our construction improves upon the asymptotic efficiency attained by previous efforts. Existing cryptographic dark pools process new orders in time which grows linearly in the size of the standing order book; ours does so in polylogarithmic time. We describe a concrete implementation of our MPC protocol with malicious security in the honest majority setting. We also report benchmarks of our implementation and compare them to prior works. Our protocol reduces the total running time by several orders of magnitude over prior secure dark pool solutions.

We introduce ABIDES, an open source Agent-Based Interactive Discrete Event Simulation environment. ABIDES is designed from the ground up to support agent-based research in market applications. While proprietary simulations are available within trading firms, there are no broadly available high-fidelity market simulation environments. ABIDES enables the simulation of tens of thousands of trading agents interacting with an exchange agent to facilitate transactions. It supports configurable pairwise noisy network latency between each individual agent as well as the exchange. Our simulator's message-based design is modeled after NASDAQ's published equity trading protocols ITCH and OUCH. We introduce the design of the simulator and illustrate its use and configuration with sample code, validating the environment with example trading scenarios. The utility of ABIDES for financial research is illustrated through experiments to develop a market impact model. The core of ABIDES is a general-purpose discrete event simulation, and we demonstrate its breadth of application with a non-finance work-in-progress simulating secure multiparty federated learning. We close with discussion of additional experimental problems it can be, or is being, used to explore, such as the development of machine learning trading algorithms. We hope that the availability of such a platform will facilitate research in this important area.

Summary Analysts prototyping trading strategies often reuse previously computed values: both full problems and subproblems. Avoiding recomputing these would increase productivity. We built a memoization library that caches function computations to files to avoid recomputation. This should minimize the need for users to think about whether caching is appropriate while giving them control over speed, accuracy, and space usage. Guo and Engler built an automatic memoization library by modifying the Python interpreter, while jug and joblib are distributed computing libraries that do memoization. Our library attempts to maintain the ease of use of these libraries while offering a higher degree of control of how caching is carried out. It allows control of space usage for individual functions and all memoization, refreshing memoization for a specific function, and accuracy checking, and uses faster hashing and provides a divide and conquer approach to reuse previously computed subproblems. We show that for Markowitz optimization, Fama–French, and the singular value decomposition, memoization using our library greatly speeds up recomputation, often by over 99% versus no memoization and over 80% versus joblib. We also show how a divide‐and‐conquer memoization approach can give large speedups for sorting. Published 2015. This article is a U.S. Government work and is in the public domain in the USA.

Inferring the social structures of animal groups from their observed behavior is a non-trivial task usually handled by direct observation. Recent advances in sensing and tracking technology have enabled the collection of dense spatial data over long periods of time automatically. The qualitative differences between sparse hand-coded data and dense tracking data necessitate a new approach to inferring the social structure of the observed animals. We present a framework for using agent-based simulations to guide our approach to inferring social structure from tracking data collected from a small group of rhesus macaques over a period of three months. As part of this framework, we describe a version of the DOMWORLD model of dominance interactions in rhesus macaques that has been modified to include association preference, and adapted to more closely match the environment where the monkeys were housed. An exploration of simulation results reveals important characteristics of the tracking data. The inferred social structures of the tracked monkeys are also presented.

We present a method to locate animals in video based on their reported positions using noisy and biased measurements from a radio frequency identification (RFID) system. The system uses a kernel regression method to learn a mapping from reported X, Y, Z locations in the environment to X, Y pixel locations in video with minimal calibration and training data. Our goal is for this system to facilitate animal behavior research by enabling automatic identification of interactions between animals and then providing the location of the animals in video so that the details of each interaction can be examined more closely by either humans or machines. The primary contribution of this work is achieving efficient and reliable 3D to 2D projective mapping in a non-parametric way while also overcoming challenges that would otherwise affect accuracy. Our system successfully addresses issues regarding noisy positional data, position bias, occlusion of RFID tags, and wide angle lens distortion. We validate the system experimentally indoors as well as in the field and compare the accuracy of our system with the standard camera projection model-based procedure.

Hybrid deliberative-reactive control architectures are a popular and effective approach to the control of robotic navigation applications. However, due to the fundamental differences in the design of the reactive and deliberative layers, the design of hybrid control architectures can pose significant difficulties. We propose a novel approach to improving system-level performance of hybrid control architectures by incrementally improving the deliberative layer's model of the reactive layer's execution of its plans. Incremental supervised learning techniques are employed to learn the model. Quantitative and qualitative results from a physics-based simulator are presented.

One of the common applications for outdoor robots is to follow a path in large scale unknown environments. This task is challenging due to the intensive memory requirements to represent the map, uncertainties in the location estimate of the robot and unknown terrain type and obstacles on the way to the goal. We develop a novel graph-based path planner that is based on only local perceptual information to plan a path in such environments. In order to extend the capabilities of the graph representation, we introduce Exploration Bias, which is a node attribute that can implicitly encode obstacle features at immediate surrounding of a node in the graph, the uncertainty of the planner about a node location and also the frequency of visiting a location. Through simulation experiments, we demonstrate that the resulting path cost and distance that the robot traverses to reach the goal location is not significantly different from those of the previous approaches.

Hybrid deliberative-reactive control architectures are a popular and effective approach to the control of robotic navigation applications. However, the design of said architectures is difficult, due to the fundamental differences in the design of the reactive and deliberative layers of the architecture. We propose a novel approach to improving system-level performance of said architectures, by improving the deliberative layer's model of the reactive layer's execution of its plans through the use of machine learning techniques. Quantitative and qualitative results from a physics-based simulator are presented.

We have developed a CS1 curriculum that uses a robotics context to teach introductory programming [1]. Core to our approach is that each student has their own personal robot. Our robot and software have been specifically developed to support the needs of a CS1 curriculum. We frame traditional problems (robot control) in terms that are personal, relevant, and fun. Initial trial classes have shown that our approach is successful and adaptable.

We present and examine a technique for estimating the ego-motion of a mobile robot using memory-based learning and a monocular camera. Unlike other approaches that rely heavily on camera calibration and geometry to compute trajectory, our method learns a mapping from sparse optical flow to platform velocity and turn rate. We also demonstrate an efficient method of computing high-quality sparse optical flow, and techniques for using this sparse optical flow as input to a supervised learning method. We employ a voting scheme of many learners that use subsets of the sparse optical flow to cope with variable dimensionality and reduce the dimensionality of each learner. Finally, we perform experiments in which we examine the learned mapping for visual odometry, investigate the effects of varying the reduced dimensionality of the sparse optical flow state, and quantify the accuracy of two variations of our learner scheme. Our results indicate that our learning scheme estimates monocular visual odometry mainly from points on the ground plane, and reflect to a degree the minimum dimensionality imposed by the problem. In addition, we show that while this memory-based learning method cannot yet estimate ego-motion as accurately as recent geometric methods, it is possible to learn, with no explicit model of camera calibration or scene structure, complicated mappings that take advantage of properties of the camera and the environment.

The Rapidly Exploring Random Tree (RRT) algorithm can be applied to the robotic path planning problem and performs well in challenging, dynamic domains. Traditional RRT methods use a binary cost function and they select portions of the tree for expansion based on the Euclidean distance to the target. However, in outdoor navigation, the relative cost of terrain can also provide useful input to a planning algorithm that traditional RRT methods cannot take advantage of. We present the Metric Adaptive RRT (MA-RRT), which integrates planning and fast execution for generating paths over a cost map. The MA-RRT algorithm considers underlying cost of a path when calculating the distance function for tree expansion. A heuristic value is also used for determining distance from a point to the target and an adaptive mechanism is employed for adjusting the heuristic on-line. We have implemented our approach in offline simulations and in outdoor robot experiments, and show that the MA-RRT algorithm can improve upon the quality of the path returned when cost is considered. The trade off between cost consideration and runtime performance is also presented.

We evaluate a technique that uses an embedded network deployed pervasively throughout an environment to aid robots in navigation. The embedded nodes do not know their absolute or relative positions and the mobile robots do not perform localization or mapping. Yet, the mobile robot is able to navigate through complex environments effectively. First, we present an algorithm for physical path planning and its implementation on the Gnats, a novel embedded network platform. Next, we investigate the quality of the computed paths. We present quantitative results collected from a real-world embedded network of 60 nodes. Experimentally, we find that, on average, the path computed by the network is only 24% longer than the optimal path. Finally, we show that the paths computed by the network are useful for a simple mobile robot. Results from a network of 156 nodes in a static environment and a network of 60 nodes in a dynamic environment are presented.

We describe a clustering-based algorithm for tracking a dynamically varying number of targets observed by multiple sensors. The algorithm relies on discrete target detections (e.g., laser "hits") and a simple model of the targets to be tracked (e.g. a human is modeled in 2-D as a circle). The algorithm is evaluated in the context of a 4 versus 4 basketball game (8 targets) using 4 SICK LMS291 laser scanners as input. Our evaluations show that the sensor system correctly reports the number of targets roughly 99% of the time. We also demonstrate use of the tracker with two video datasets of multiple changing numbers of ants and fish, respectively

When the tasks of a mission are interrelated and subject to several resource constraints, more efforts are needed to coordinate robots towards achieving the mission than independent tasks. In this work, we formulate the Coordinated Task Selection Problem (CTSP) to form the basis of an efficient dynamic task selection scheme for allocation of interrelated tasks of a complex mission to the members of a multi-robot team. Since processing times of tasks are not exactly known in advance, the incremental task selection scheme for the eligible tasks prevents redundant efforts as, instead of scheduling all of the tasks, they are allocated to robots as needed. This approach results in globally efficient solutions through mechanisms that form priority based rough schedules and select the most suitable tasks from these schedules. Since our method is targeted at real world task execution, communication requirements are kept limited. Empirical evaluations of the proposed approach are performed on the Webots simulator and the real robots. The results validate that the proposed approach is scalable, efficient and suitable to the real world safe mission achievement.

Layered hybrid controllers typically include a planner at the top level with reactive control at the lower levels. The planner considers the state of the robot in a global context. The low-level controllers consider only the local environment of the robot and are able to operate at a high frequency to ensure the safety of the robot. Also, it is often the case that the low-level controllers consider more aspects of the robot's state (e.g. kinematic constraints) than the planner. The consideration of such constraints at the planning level would prohibitively increase the state space the planner must consider and, accordingly, its running time and complexity. In this paper, we investigate how we can take advantage at the planning level of domain knowledge encapsulated in the lower level controllers, and we introduce a feedback mechanism that enables low-level controllers to influence the high-level planner.

We investigate a technique that uses an embedded network deployed pervasively throughout an environment to aid robots in navigation. First, we show that the path computed by the network is useful for a simple mobile robot. The robot uses a network of 156 nodes to navigate through a complex, dynamic, environment. This is the largest embedded network used for navigation we are aware of. In our approach, the network nodes do not need to know their absolute or relative positions and the mobile robots do not build any kind of map. Second, the impact of specific network deployments on path quality is examined. Two types of arrangements, hexagonal and rectangular, in two different environments are considered. We present quantitative results collected from a real-world embedded network of 60 nodes. Experimentally, we find that on average, the path computed by the network is only 24% longer than the optimal path. Also, we find a slight advantage for the hexagonal arrangement

Autonomous robot systems have to manage their energy wisely in order to complete their missions. Typical approaches seek to conserve energy by energy-efficient motion or sensor planning. This paper puts forth a distributed systems approach to power management. Specifically, it develops and presents AutoPower, which is a model that characterizes robot software systems' computation and communication energy behaviors. With AutoPower, it is possible to make principled decisions about (1) where to deploy software components across the distributed computing resources of autonomous robotic systems, and (2) how the different systems involved should communicate to best meet overall mission objectives. We showcase AutoPower by using a multi-robot search-and-rescue mission as a guiding application. For this scenario, application of the model shows that there are counter-intuitive energy trade-offs in configuring such application software. Further, by using AutoPower to guide deployment and interconnects at runtime, for certain configurations, overall computing system lifetimes can be increased by up to 57% over a base-line configuration

In several multitarget tracking applications, a target may return more than one measurement per target and interacting targets may return multiple merged measurements between targets. Existing algorithms for tracking and data association, initially applied to radar tracking, do not adequately address these types of measurements. Here, we introduce a probabilistic model for interacting targets that addresses both types of measurements simultaneously. We provide an algorithm for approximate inference in this model using a Markov chain Monte Carlo (MCMC)-based auxiliary variable particle filter. We Rao-Blackwellize the Markov chain to eliminate sampling over the continuous state space of the targets. A major contribution of this work is the use of sparse least squares updating and downdating techniques, which significantly reduce the computational cost per iteration of the Markov chain. Also, when combined with a simple heuristic, they enable the algorithm to correctly focus computation on interacting targets. We include experimental results on a challenging simulation sequence. We test the accuracy of the algorithm using two sensor modalities, video, and laser range data. We also show the algorithm exhibits real time performance on a conventional PC.

Our understanding of social insect behavior has significantly influenced artificial intelligence (AI) and multirobot systems' research (e.g., ant algorithms and swarm robotics). In this work, however, we focus on the opposite question: "How can multirobot systems research contribute to the understanding of social animal behavior?" As we show, we are able to contribute at several levels. First, using algorithms that originated in the robotics community, we can track animals under observation to provide essential quantitative data for animal behavior research. Second, by developing and applying algorithms originating in speech recognition and computer vision, we can automatically label the behavior of animals under observation. In some cases the automatic labeling is more accurate and consistent than manual behavior identification. Our ultimate goal, however, is to automatically create, from observation, executable models of behavior. An executable model is a control program for an agent that can run in simulation (or on a robot). The representation for these executable models is drawn from research in multirobot systems programming. In this paper we present the algorithms we have developed for tracking, recognizing, and learning models of social animal behavior, details of their implementation, and quantitative experimental results using them to study social insects

In many multitarget tracking applications in computer vision, a detection algorithm provides locations of potential targets. Subsequently, the measurements are associated with previously estimated target trajectories in a data association step. The output of the detector is often imperfect and the detection data may include multiple, split measurements from a single target or a single merged measurement from several targets. To address this problem, we introduce a multiple hypothesis tracker for interacting targets that generate split and merged measurements. The tracker is based on an efficient Markov chain Monte Carlo (MCMC) based auxiliary variable particle filter. The particle filter is Rao-Blackwellized such that the continuous target state parameters are estimated analytically, and an MCMC sampler generates samples from the large discrete space of data associations. In addition, we include experimental results in a scenario where we track several interacting targets that generate these split and merged measurements.

We introduce parametric switching linear dynamic systems (P-SLDS) for learning and interpretation of parametrized motion, i.e., motion that exhibits systematic temporal and spatial variations. Our motivating example is the honeybee dance: bees communicate the orientation and distance to food sources through the dance angles and waggle lengths of their stylized dances. Switching linear dynamic systems (SLDS) are a compelling way to model such complex motions. However, SLDS does not provide a means to quantify systematic variations in the motion. Previously, Wilson & Bobick (1999) presented parametric HMMs, an extension to HMMs with which they successfully interpreted human gestures. Inspired by their work, we similarly extend the standard SLDS model to obtain parametric SLDS. We introduce additional global parameters that represent systematic variations in the motion, and present general expectation-maximization (EM) methods for learning and inference. In the learning phase, P-SLDS learns canonical SLDS model from data. In the inference phase, P-SLDS simultaneously quantifies the global parameters and labels the data. We apply these methods to the automatic interpretation of honey-bee dances, and present both qualitative and quantitative experimental results on actual bee-tracks collected from noisy video data.

In this paper, we study the problem of going from a real-world, multi-agent system to the generation of control programs in an automatic fashion. In particular, a computer vision system is presented, capable of simultaneously tracking multiple agents, such as social insects. Moreover, the data obtained from this system is fed into a mode-reconstruction module that generates low-complexity control programs, i.e. strings of symbolic descriptions of control-interrupt pairs, consistent with the empirical data. The result is a mechanism for going from the real system to an executable implementation that can be used for controlling multiple mobile robots.

We continue our investigation into the application of pervasive, embedded networks to support multi-robot tasks. In this work we use a new a hardware platform, the GNATs, to aid in path planning. We have implemented a physical path planning algorithm on the GNATs previously studied in simulation. A distributed version of the wavefront path planning algorithm is used to propagate paths throughout the network, thereby planning a path in the real world. This creates a graph of traversable paths that are nearly optimal in a dynamic environment.

We describe a particle filter that effectively deals with interacting targets--targets that are influenced by the proximity and/or behavior of other targets. The particle filter includes a Markov random field (MRF) motion prior that helps maintain the identity of targets throughout an interaction, significantly reducing tracker failures. We show that this MRF prior can be easily implemented by including an additional interaction factor in the importance weights of the particle filter. However, the computational requirements of the resulting multitarget filter render it unusable for large numbers of targets. Consequently, we replace the traditional importance sampling step in the particle filter with a novel Markov chain Monte Carlo (MCMC) sampling step to obtain a more efficient MCMC-based multitarget filter. We also show how to extend this MCMC-based filter to address a variable number of interacting targets. Finally, we present both qualitative and quantitative experimental results, demonstrating that the resulting particle filters deal efficiently and effectively with complicated target interactions.

Move Value Estimation for Robot Teams (MVERT) is a robot action selection algorithm for teams performing multiple competing tasks. The goal of MVERT is to select actions for robot team members to maximize the team's joint utility toward overall mission progress in a computationally efficient manner. MVERT is fully distributed, with each robot using information about other teammates to select its action with the greatest value. MVERT selects actions for a robot team to perform multi-task exploration and dynamic target observation. Successful action selection is demonstrated in simulation for exploration and in simulation and on robots for dynamic target observation.

We describe a multiple hypothesis particle filter for tracking targets that are influenced by the proximity and/or behavior of other targets. Our contribution is to show how a Markov random field motion prior, built on the fly at each time step, can model these interactions to enable more accurate tracking. We present results for a social insect tracking application, where we model the domain knowledge that two targets cannot occupy the same space, and targets actively avoid collisions. We show that using this model improves track quality and efficiency. Unfortunately, the joint particle tracker we propose suffers from exponential complexity in the number of tracked targets. An approximation to the joint filter, however, consisting of multiple nearly independent particle filters can provide similar track quality at substantially lower computational cost.

Creation of cooperative robot teams for complex tasks requires not only agents that can function well individually but also agents that can coordinate their actions. The paper presents several methods for collaboration and coordination in a team of soccer-playing robots. In our approach, fixed collaborative supporting behaviours allow for robots to aid each other and decrease interference. Coordinated dynamic role assignment then permits the robots to take advantage of their current location on the field. We present a robust protocol for dynamic role assignment based upon multithreaded computer programming that mitigates the risk often associated with initiating a role change in a distributed system. This protocol is independent from the manner in which the decision to switch roles is made and would therefore support any approach to role assignment. The individual and supporting behaviours were tested at RoboCup 2001 in Seattle, Washington.

We present an efficient probabilistic method for localization using landmarks that supports individual robot and multi-robot collaborative localization. The approach, based on the Kalman-Bucy filter, reduces computation by treating different types of landmark measurements (for example, range and bearing) separately. Our algorithm has been extended to perform two types of collaborative localization for robot teams. Results illustrating the utility of the approach in simulation and on a real robot are presented.

We describe a behavior-based control system that enables a non-holonomic robot to push an object from an arbitrary starting position to a goal location through an obstacle field. The approach avoids the need for maintaining an internal model of the target and obstacles and the potentially high computational overhead associated with traditional path planning approaches for non-holonomic robots. The motor schema-based control system was prototyped in simulation, then evaluated empirically on mobile robots. The approach was demonstrated in two pushing tasks: box pushing and ball dribbling. Using the same generalized control system, a robot is able to successfully push a box through a static obstacle field and dribble a ball into a goal during RoboCup soccer matches. In both cases the robot is able to react quickly and recover from situations where it loses control of its target with due to its own motion or interference with others. Quantitative experimental results for reliability in box pushing are included.

We present a method for representing, communicating and fusing distributed, noisy and uncertain observations of an object by multiple robots. The approach relies on re-parameterization of the canonical two-dimensional Gaussian distribution that corresponds more naturally to the observation space of a robot. The approach enables two or more observers to achieve greater effective sensor coverage of the environment and improved accuracy in object position estimation. We demonstrate empirically that, when using our approach, more observers achieve more accurate estimations of an object's position. The method is tested in three application areas, including object location, object tracking, and ball position estimation for robotic soccer. Quantitative evaluations of the technique in use on mobile robots are provided.

Potential function approaches to robot navigation provide an elegant paradigm for expressing multiple constraints and goals in mobile robot navigation problems. As an example, a simple reactive navigation strategy can be generated by combining repulsion from obstacles with attraction to a goal. Advantages of this approach can also be extended to multirobot teams. In this paper we present a new class of potential functions for multiple robots that enables homogeneous large-scale robot teams to arrange themselves in geometric formations while navigating to a goal location through an obstacle field. The approach is inspired by the way molecules "snap" into place as they form crystals; the robots are drawn to particular "attachment sites" positioned with respect to other robots. We refer to these potential functions as "social potentials" because they are constructed with respect to other agents. Initial results, generated in simulation, illustrate the viability of the approach.

Vision systems employing region segmentation by color are crucial in real-time mobile robot applications. With careful attention to algorithm efficiency, fast color image segmentation can be accomplished using commodity image capture and CPU hardware. This paper describes a system capable of tracking several hundred regions of up to 32 colors at 30 Hz on general purpose commodity hardware. The software system consists of: a novel implementation of a threshold classifier, a merging system to form regions through connected components, a separation and sorting system that gathers various region features, and a top down merging heuristic to approximate perceptual grouping. A key to the efficiency of our approach is a new method for accomplishing color space thresholding that enables a pixel to be classified into one or more, up to 32 colors, using only two logical AND operations. The algorithms and representations are described, as well as descriptions of three applications in which it has been used.

New reactive behaviors that implement formations in multirobot teams are presented and evaluated. The formation behaviors are integrated with other navigational behaviors to enable a robotic team to reach navigational goals, avoid hazards and simultaneously remain in formation. The behaviors are implemented in simulation, on robots in the laboratory and aboard DARPA's HMMWV-based unmanned ground vehicles. The technique has been integrated with the autonomous robot architecture (AuRA) and the UGV Demo II architecture. The results demonstrate the value of various types of formations in autonomous, human-led and communications-restricted applications, and their appropriateness in different types of task environments.

A new laser-based optical sensor system that provides hazard detection for planetary rovers is presented. The sensor can support safe travel at speeds up to 12 cm/second for large (1 m) rovers in full sunlight on Earth or Mars. This is at least a 5 times improvement over the sensor aboard NASA's Mars Pathfinder rover. The system overcomes limitations in the older design that require image differencing to detect a laser stripe in full sun. The new system ensures the projected laser light is detectable in a single image, eliminating the requirement for additional difference images. The improvement is significant since any reduction in image gathering or processing time provides for faster rover motion. The savings are even more important in the case of a Mars rover since power and radiation-hardening requirements lead to severely constrained computational resources. The paper includes a thorough discussion of design details and tradeoffs for optical hazard sensing that will benefit future efforts in this area.

This paper reviews key concepts of the Autonomous Robot Architecture (AuRA). Its structure, strengths, and roots in biology are presented. AuRA is a hybrid deliberative/ reactive robotic architecture that has been developed and refined over the past decade. In this article, particular focus is placed on the reactive behavioural component of this hybrid architecture. Various real world robots that have been implemented using this architectural paradigm are discussed, including a case study of a multiagent robotic team that competed and won the 1994 AAAI Mobile Robot Competition.