Training data detection is critical for enforcing copyright and data licensing, as Large Language Models (LLM) are trained on massive text corpora scraped from the internet. We present SPECTRA, a watermarking approach that makes training data reliably detectable even when it comprises less than 0.001% of the training corpus. SPECTRA works by paraphrasing text using an LLM and assigning a score based on how likely each paraphrase is, according to a separate scoring model. A paraphrase is chosen so that its score closely matches that of the original text, to avoid introducing any distribution shifts. To test whether a suspect model has been trained on the watermarked data, we compare its token probabilities against those of the scoring model. We demonstrate that SPECTRA achieves a consistent p-value gap of over nine orders of magnitude when detecting data used for training versus data not used for training, which is greater than all baselines tested. SPECTRA equips data owners with a scalable, deploy‑before‑release watermark that survives even large‑scale LLM training.

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.

This paper presents a new combinatorial optimisation task, the Subset Sum Matching Problem (SSMP), which is an abstraction of common financial applications such as trades reconciliation. We present three algorithms, two suboptimal and one optimal, to solve this problem. We also generate a benchmark to cover different instances of SSMP varying in complexity, and carry out an experimental evaluation to assess the performance of the approaches.

Most of the work on learning action models focus on learning the actions’ dynamics from input plans. This allows us to specify the valid plans of a planning task. However, very little work focuses on learning action costs, which in turn allows us to rank the different plans. In this paper we introduce a new problem: that of learning the costs of a set of actions such that a set of input plans are optimal under the resulting planning model. To solve this problem we present LACFIPk, an algorithm to learn action’s costs from unlabeled input plans. We provide theoretical and empirical results showing how LACFIPk can successfully solve this task.

Reward models (RMs) are a crucial component in the alignment of large language models’ (LLMs) outputs with human values. RMs approximate human preferences over possible LLM responses to the same prompt by predicting and comparing reward scores. However, as they are typically modified versions of LLMs with scalar output heads, RMs are large black boxes whose predictions are not explainable. More transparent RMs would enable improved trust in the alignment of LLMs. In this work, we propose to use contrastive explanations to explain any binary response comparison made by an RM. Specifically, we generate a diverse set of new comparisons similar to the original one to characterise the RM’s local behaviour. The perturbed responses forming the new comparisons are generated to explicitly modify manually specified high-level evaluation attributes, on which analyses of RM behaviour are grounded. In quantitative experiments, we validate the effectiveness of our method for finding high-quality contrastive explanations. We then showcase the qualitative usefulness of our method for investigating global sensitivity of RMs to each evaluation attribute, and demonstrate how representative examples can be automatically extracted to explain and compare behaviours of different RMs. We see our method as a flexible framework for RM explanation, providing a basis for more interpretable and trustworthy LLM alignment.

As large language models (LLMs) become more powerful, the computation required to run these models is increasingly outsourced to a third-party cloud. While this saves clients’ computation, it risks leaking the clients’ LLM queries to the cloud provider. Fully homomorphic encryption (FHE) presents a natural solution to this problem: simply encrypt the query and evaluate the LLM homomorphically on the cloud machine. The result remains encrypted and can only be learned by the client who holds the secret key. In this work, we present a GPU-accelerated implementation of FHE and use this implementation to benchmark an encrypted GPT-2 forward pass, with runtimes over $200\times$ faster than the CPU baseline. We also present novel and extensive experimental analysis of approximations of LLM activation functions to maintain accuracy while achieving this performance.

Time series with missing or irregularly sampled data are a persistent challenge in machine learning. Many methods operate on the frequency-domain, relying on the Fast Fourier Transform (FFT) which assumes uniform sampling, therefore requiring prior interpolation that can distort the spectra. To address this limitation, we introduce a differentiable Lomb–Scargle layer that enables a reliable computation of the power spectrum of irregularly sampled data. We integrate this layer into a novel score-based diffusion model (LSCD) for time series imputation conditioned on the entire signal spectrum. Experiments on synthetic and real-world benchmarks demonstrate that our method recovers missing data more accurately than purely time-domain baselines, while simultaneously producing consistent frequency estimates. Crucially, our method can be easily integrated into learning frameworks, enabling broader adoption of spectral guidance in machine learning approaches involving incomplete or irregular data.

We introduce Mechanistic Error Reduction with Abstention (MERA), a principled framework for steering language models (LMs) to mitigate errors through selective, adaptive interventions. Unlike existing methods that rely on fixed, manually tuned steering strengths, often resulting in under or oversteering, MERA addresses these limitations by (i) optimising the intervention direction, and (ii) calibrating when and how much to steer, thereby provably improving performance or abstaining when no confident correction is possible. Experiments across diverse datasets and LM families demonstrate safe, effective, non-degrading error correction and that MERA outperforms existing baselines. Moreover, MERA can be applied on top of existing steering techniques to further enhance their performance, establishing it as a general-purpose and efficient approach to mechanistic activation steering.

Small and medium-sized enterprises (SMEs) often struggle with automating high-mix, low-volume (HMLV) manufacturing due to the inflexibility and high cost of traditional automation solutions. This paper presents a novel approach to robotic manipulation for HMLV environments that leverages vibrotactile sensing. We propose integrating vibrotactile sensors, which capture subtle vibrations and acoustic signals, to provide real-time feedback during manipulation tasks. This approach enables the robot to detect subtle misalignments, which can assist in refining vision-based policies and improving the robot’s overall manipulation skills. We demonstrate the effectiveness of this method in several representative insertion tasks, showing how vibrotactile feedback can be used to predict success or failure of an insertion task as well as predict initial contact between an object grasped in-hand and the placement location. Our results suggest that vibrotactile sensing offers a promising pathway towards more robust and adaptable robotic systems that can better empower SMEs to embrace automation.

Identifying the specific actions that achieve goals when solving a planning task might be beneficial for various planning applications. Traditionally, this identification occurs post-search, as some actions may temporarily achieve goals that are later undone and re-achieved by other actions. In this paper, we propose a compilation that extends the original planning task with commit actions that enforce the persistence of specific goals once achieved, allowing planners to identify permanent goal achievement during planning. Experimental results indicate that solving the reformulated tasks does not incur on any additional overhead both when performing optimal and suboptimal planning, while providing useful information for some downstream tasks.

The Hierarchical Seating Allocation Problem (HSAP) is the problem to allocate an organizational hierarchy of teams to a set of seats on a floor plan. This problem is driven by the necessity for large organizations with large hierarchies to ensure that teams with close hierarchical relationships are seated in proximity to one another, such as ensuring a research group occupies a contiguous area. Currently, this problem is managed manually leading to infrequent and suboptimal replanning efforts. To alleviate this manual process, we propose an end-to-end framework to solve the HSAP. A scalable approach to calculate the distance between any pair of seats using a probabilistic road map (PRM) and rapidly-exploring random trees (RRT) which is combined with heuristic search and dynamic programming approach to solve the HSAP using integer programming. We demonstrate our approach under different sized instances by evaluating the PRM framework and subsequent allocations both quantitatively and qualitatively.

In recent years, mixup regularization has gained popularity as an effective way to improve the generalization performance of deep learning models by training on convex combinations of training data. While many mixup variants have been explored, the proper adoption of the technique to conditional density estimation and probabilistic machine learning remains relatively unexplored. This work introduces a novel framework for mixup regularization based on probabilistic fusion that is better suited for conditional density estimation tasks. For data distributed according to a member of the exponential family, we show that likelihood functions can be analytically fused using log-linear pooling. We further propose an extension of probabilistic mixup, which allows for fusion of inputs at an arbitrary intermediate layer of the neural network. We provide a theoretical analysis comparing our approach to standard mixup variants. Empirical results on synthetic and real datasets demonstrate the benefits of our proposed framework compared to existing mixup variants.

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.

Uncrewed aerial vehicle-mounted base stations (UAV-MBSs) provide flexible wireless connectivity, extending communication coverage in underserved areas. Recently, multi-agent reinforcement learning (MARL) has shown great potential for cooperative UAV swarm control to support efficient communication coverage in dynamic and complex environments. However, existing MARL-based methods often suffer from low sample efficiency due to its trial-and-error training characteristics, limiting its ability to control large UAV swarms with continuous state-action space and partial observation. We notice that UAV swarm systems in communication coverage tasks exhibit a spatial symmetry property, e.g., a rotation in the spatial observation of a UAV results in a same rotation in its optimal action. Exploiting this property, we formulate the task as a symmetric decentralized partially observable Markov decision process and introduce symmetry-informed MARL, featuring a novel network called the symmetry-informed graph neural network (SiGNN) to serve as the policy/value networks. SiGNN leverages the inherent symmetry in multi-UAV systems by embedding the symmetry into the network structure, thereby enhancing the training efficiency to handle large swarms with continuous control. Theoretical analysis shows that the SiGNN strictly preserves symmetry properties, which guarantees the effectiveness of the approach. Experiments in simulation were conducted to handle communication coverage using up to 20 UAVs with continuous control. Experimental results demonstrate that SiGNN-based MARL outperforms advanced baselines, verifying its superior sample efficiency, scalability and robustness.

Discrete optimization belongs to the set of N P-hard problems, spanning fields such as mixed-integer programming and combinatorial optimization. A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms, which reach optimal solutions by iteratively adding inequalities known as cuts to refine a feasible set. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. In this work, we propose a method for accelerating cutting-plane algorithms via reinforcement learning. Our approach uses learned policies as surrogates for N P-hard elements of the cut generating procedure in a way that (i) accelerates convergence, and (ii) retains guarantees of optimality. We apply our method on two types of problems where cutting-plane algorithms are commonly used: stochastic optimization, and mixed-integer quadratic programming. We observe the benefits of our method when applied to Benders decomposition (stochastic optimization) and iterative loss approximation (quadratic programming), achieving up to 45% faster average convergence when compared to modern alternative algorithms.

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.

Polyhedral geometry can be used to shed light on the behaviour of piecewise linear neural networks, such as ReLU-based architectures. Counterfactual explanations are a popular class of methods for examining model behaviour by comparing a query to the closest point with a different label, subject to constraints. We present a new algorithm, Polyhedral-complex Informed Counterfactual Explanations (PICE), which leverages the decomposition of the piecewise linear neural network into a polyhedral complex to find counterfactuals that are provably minimal in the Euclidean norm and exactly on the decision boundary for any given query. Moreover, we develop variants of the algorithm that target popular counterfactual desiderata such as sparsity, robustness, speed, plausibility, and actionability. We empirically show on four publicly available real-world datasets that our method outperforms other popular techniques to find counterfactuals and adversarial attacks by distance to decision boundary and distance to query. Moreover, we successfully improve our baseline method in the dimensions of the desiderata we target, as supported by experimental evaluations.

In this work we consider a new interpretation of fairness in decision making problems. Building upon existing fairness formulations, we focus on how to reason over fairness from a temporal perspective, taking into account the fairness of a history of past decisions. After introducing the concept of temporal fairness, we propose three approaches that incorporate temporal fairness in decision making problems formulated as optimization problems. We present a qualitative evaluation of our approach in four different domains and compare the solutions against a baseline approach that does not consider the temporal aspect of fairness.

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.

We introduce T-CREx, a novel model-agnostic method for local and global counterfactual explanation (CE), which summarises recourse options for both individuals and groups in the form of generalised rules. It leverages tree-based surrogate models to learn the counterfactual rules, alongside metarules denoting their regimes of optimality, providing both a global analysis of model behaviour and diverse recourse options for users. Experiments indicate that T-CREx achieves superior aggregate performance over existing rule-based baselines on a range of CE desiderata, while being orders of magnitude faster to run.

This paper proposes Progressive inference–a framework to explain the predictions of decoder-only transformer models trained to perform sequence classification tasks. Our work is based on the insight that the classification head of a decoder-only model can be used to make intermediate predictions by evaluating them at different points in the input sequence. Due to the masked attention mechanism used in decoder-only models, these intermediate predictions only depend on the tokens seen before the inference point, allowing us to obtain the model’s prediction on a masked input sub-sequence, with negligible computational overheads. We develop two methods to provide sub-sequence level attributions using this core insight. First, we propose Single Pass-Progressive Inference (SP-PI) to compute attributions by simply taking the difference between intermediate predictions. Second, we exploit a connection with Kernel SHAP to develop Multi Pass-Progressive Inference (MP-PI); this uses intermediate predictions from multiple masked versions of the input to compute higher-quality attributions that approximate SHAP values. We perform studies on several text classification datasets to demonstrate that our proposal provides better explanations compared to prior work, both in the single-pass and multi-pass settings.

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.

We introduce a novel approach for detecting distribution shifts that negatively impact the performance of machine learning models in continuous production environments, which requires no access to ground truth data labels. It builds upon the work of Podkopaev and Ramdas [2022], who address scenarios where labels are available for tracking model errors over time. Our solution extends this framework to work in the absence of labels, by employing a proxy for the true error. This proxy is derived using the predictions of a trained error estimator. Experiments show that our method has high power and false alarm control under various distribution shifts, including covariate and label shifts and natural shifts over geography and time.

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).

Feature selection is a crucial step in building machine learning models. This process is often achieved with accuracy as an objective, and can be cumbersome and computationally expensive for large-scale datasets. Several additional model performance characteristics such as fairness and robustness are of importance for model development. As regulations are driving the need for more trustworthy models, deployed models need to be corrected for model characteristics associated with responsible artificial intelligence. When feature selection is done with respect to one model performance characteristic (eg. accuracy), feature selection with secondary model performance characteristics (eg. fairness and robustness) as objectives would require going through the computationally expensive selection process from scratch. In this paper, we introduce the problem of feature reselection, so that features can be selected with respect to secondary model performance characteristics efficiently even after a feature selection process has been done with respect to a primary objective. To address this problem, we propose REFRESH, a method to reselect features so that additional constraints that are desirable towards model performance can be achieved without having to train several new models. REFRESH’s underlying algorithm is a novel technique using SHAP values and correlation analysis that can approximate for the predictions of a model without having to train these models. Empirical evaluations on three datasets, including a large-scale loan defaulting dataset show that REFRESH can help find alternate models with better model characteristics efficiently. We also discuss the need for reselection and REFRESH based on regulation desiderata.

In some applications, planning-monitoring systems generate plans and monitor their execution by other agents. During execution, agents might deviate from these plans for various reasons. The deviation from the expected behavior will be observed by the planning-monitoring system, which will replan in order to provide the agent a new suggested plan. Most existing replanning approaches maintain the goals and compute a plan that achieves them under the new circumstances. This is often not realistic, as achieving the original goal might be very costly or impossible under the current conditions. Furthermore, replanning approaches usually overlook agent’s behavior up to the observed deviation from the original plan. In this paper we introduce GREPLAN, a novel approach that proposes new replanning goals (and plans) by solving a multi-objective optimization problem that considers all goals within a perimeter of the original goal. Empirical results in several planning benchmarks show that GREPLAN successfully reacts to deviations from the original plan by generating new appropriate replanning goals.

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.

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 ASPiRe (Adaptive Skill Prior for RL), a new approach that leverages prior experience to accelerate reinforcement learning. Unlike existing methods that learn a single skill prior from a large and diverse dataset, our framework learns a library of different distinction skill priors (i.e., behavior priors) from a collection of specialized datasets, and learns how to combine them to solve a new task. This formulation allows the algorithm to acquire a set of specialized skill priors that are more reusable for downstream tasks; however, it also brings up additional challenges of how to effectively combine these unstructured sets of skill priors to form a new prior for new tasks. Specifically, it requires the agent not only to identify which skill prior(s) to use but also how to combine them (either sequentially or concurrently) to form a new prior. To achieve this goal, ASPiRe includes Adaptive Weight Module (AWM) that learns to infer an adaptive weight assignment between different skill priors and uses them to guide policy learning for downstream tasks via weighted Kullback-Leibler divergences. Our experiments demonstrate that ASPiRe can significantly accelerate the learning of new downstream tasks in the presence of multiple priors and show improvement on competitive baselines.

Retrieving relevant documents from a corpus is typically based on the semantic similarity between the document content and query text. The inclusion of structural relationship between documents can benefit the retrieval mechanism by addressing semantic gaps. However, incorporating these relationships requires tractable mechanisms that balance structure with semantics and take advantage of the prevalent pre-train/fine-tune paradigm. We propose here a holistic approach to learning document representations by integrating intra-document content with inter-document relations. Our deep metric learning solution analyzes the complex neighborhood structure in the relationship network to efficiently sample similar/dissimilar document pairs and defines a novel quintuplet loss function that simultaneously encourages document pairs that are semantically relevant to be closer and structurally unrelated to be far apart in the representation space. Furthermore, the separation margins between the documents are varied flexibly to encode the heterogeneity in relationship strengths. The model is fully fine-tunable and natively supports query projection during inference. We demonstrate that it outperforms competing methods on multiple datasets for document retrieval tasks.

Current work in explainable reinforcement learning generally produces policies in the form of a decision tree over the state space. Such policies can be used for formal safety verification, agent behavior prediction, and manual inspection of important features. However, existing approaches fit a decision tree after training or use a custom learning procedure which is not compatible with new learning techniques, such as those which use neural networks. To address this limitation, we propose a novel Markov Decision Process (MDP) type for learning decision tree policies: Iterative Bounding MDPs (IBMDPs). An IBMDP is constructed around a base MDP so each IBMDP policy is guaranteed to correspond to a decision tree policy for the base MDP when using a method-agnostic masking procedure. Because of this decision tree equivalence, any function approximator can be used during training, including a neural network, while yielding a decision tree policy for the base MDP. We present the required masking procedure as well as a modified value update step which allows IBMDPs to be solved using existing algorithms. We apply this procedure to produce IBMDP variants of recent reinforcement learning methods. We empirically show the benefits of our approach by solving IBMDPs to produce decision tree policies for the base MDPs.

Agent control among pedestrians is often approached in one of the three following ways: using predefined behaviors for agent navigation, learning navigation behaviors from data, or search-based planning on a graph where each edge is a feasible action chosen from a set of predefined actions. While the first approach often produces natural looking motions and the second learns and utilizes complex interactions with pedestrians, both lack global reasoning about how to sequence these behaviors to achieve the overall goal. The third approach, namely search-based planning, does incorporate global reasoning but relies on predefined actions that do not involve any interactions with pedestrians or assume predefined interactions that cannot model complex interactions. This is a significant drawback since many situations such as going through a doorway blocked by other people require complex interactions in order to avoid highly suboptimal behaviors or not being able to get to the goal at all. To this end, we propose a search-based planning framework that constructs and searches a graph wherein each edge can be either a predefined action or a learned behavior. We further extend it to deal with the uncertainty arising from introducing learned behaviors. We present the algorithm, go over its theoretical analysis, and present experimental results.

Intelligent robots need to generate and execute plans. In order to deal with the complexity of real environments, planning makes some assumptions about the world. When executing plans, the assumptions are usually not met. Most works have focused on the negative impact of this fact and the use of replanning after execution failures. Instead, we focus on the positive impact, or opportunities to find better plans. When planning, the proposed technique finds and stores those opportunities. Later, during execution, the monitoring system can use them to focus perception and repair the plan, instead of replanning from scratch. Experiments in several paradigmatic robotic tasks show how the approach outperforms standard replanning strategies.

The rapid growth in urban population poses significant challenges to moving city dwellers in a fast and convenient manner. This paper contributes to solving the challenges from the viewpoint of passengers by improving their on-vehicle experience. Specifically, we focus on the problem: Given an urban public transit network and a number of passengers, with some of them controllable and the rest uncontrollable, how can we plan for the controllable passengers to improve their experience in terms of their service preference? We formalize this problem as a multi-agent path planning (MAPP) problem with soft collisions, where multiple controllable passengers are allowed to share on-vehicle service resources with one another under certain constraints. We then propose a customized version of the SC-M* algorithm to efficiently solve the MAPP task for bus transit system in complex urban environments, where we have a large passenger size and multiple types of passengers requesting various types of service resources. We demonstrate the use of SC-M* in a case study of the bus transit system in Porto, Portugal. In the case study, we implement a data-driven on-vehicle experience simulator for the bus transit system, which simulates the passenger behaviors and on-vehicle resource dynamics, and evaluate the SC-M* on it. The experimental results show the advantages of the SC-M* in terms of path cost, collision-free constraint, and the scalability in run time and success rate.

Link prediction, or the inference of future or missing connections between entities, is a well-studied problem in network analysis. A multitude of heuristics exist for link prediction in ordinary networks with a single type of connection. However, link prediction in multiplex networks, or networks with multiple types of connections, is not a well understood problem. We propose a novel general framework and three families of heuristics for multiplex network link prediction that are simple, interpretable, and take advantage of the rich connection type correlation structure that exists in many real world networks. We further derive a theoretical threshold for determining when to use a different connection type based on the number of links that overlap with an Erdos-Renyi random graph. Through experiments with simulated and real world scientific collaboration, transportation and global trade networks, we demonstrate that the proposed heuristics show increased performance with the richness of connection type correlation structure and significantly outperform their baseline heuristics for ordinary networks with a single connection type.

Tactile sensors are used in robot manipulation to reduce uncertainty regarding hand-object pose estimation. However, existing sensor technologies tend to be bulky and provide signals that are difficult to interpret into actionable changes. Here, we achieve wireless tactile sensing with soft and conformable magnetic stickers that can be easily placed on objects within the robot's workspace. We embed a small magnetometer within the robot's fingertip that can localize to a magnetic sticker with sub-mm accuracy and enable the robot to pick up objects in the same place, in the same way, every time. In addition, we utilize the soft magnets' ability to exhibit magnetic field changes upon contact forces. We demonstrate the localization and force-feedback features with a 7-DOF Franka arm on deformable tool use and a key insertion task for applications in home, medical, and food robotics. By increasing the reliability of interaction with common tools, this approach to object localization and force sensing can improve robot manipulation performance for delicate, high-precision tasks.

We explore using reinforcement learning on single and multi-agent systems such that after learning is finished we can apply a policy zero-shot to new environment sizes, as well as different number of agents and entities. Building off previous work, we show how to map back and forth between the state and action space of a standard Markov Decision Process (MDP) and multi-dimensional tensors such that zero-shot transfer in these cases is possible. Like in previous work, we use a special network architecture designed to work well with the tensor representation, known as the Fully Convolutional Q-Network (FCQN). We show simulation results that this tensor state and action space combined with the FCQN architecture can learn faster than traditional representations in our environments. We also show that the performance of a transferred policy is comparable to the performance of policy trained from scratch in the modified environment sizes and with modified number of agents and entities. We also show that the zero- shot transfer performance across team sizes and environment sizes remains comparable to the performance of training from scratch specific policies in the transferred environments. Finally, we demonstrate that our simulation trained policies can be applied to real robots and real sensor data with comparable performance to our simulation results. Using such policies we can run variable sized teams of robots in a variable sized operating environment with no changes to the policy and no additional learning necessary.

There are many opportunities to pursue AI and ML in the financial domain. In this talk, I will overview several research directions we are pursuing in engagement with the lines of business, ranging from data and knowledge, learning from experience, reasoning and planning, multi agent systems, and secure and private AI. I will offer concrete examples of projects, and conclude with the many challenges and opportunities that AI can offer in the financial domain.

Training multi-agent systems (MAS) to achieve realistic equilibria gives us a useful tool to understand and model real-world systems. We consider a general sum partially observable Markov game where agents of different types share a single policy network, conditioned on agent-specific information. This paper aims at i) formally understanding equilibria reached by such agents, and ii) matching emergent phenomena of such equilibria to real-world targets. Parameter sharing with decentralized execution has been introduced as an efficient way to train multiple agents using a single policy network. However, the nature of resulting equilibria reached by such agents has not been yet studied: we introduce the novel concept of Shared equilibrium as a symmetric pure Nash equilibrium of a certain Functional Form Game (FFG) and prove convergence to the latter for a certain class of games using self-play. In addition, it is important that such equilibria satisfy certain constraints so that MAS are calibrated to real world data for practical use: we solve this problem by introducing a novel dual-Reinforcement Learning based approach that fits emergent behaviors of agents in a Shared equilibrium to externally-specified targets, and apply our methods to a n-player market example. We do so by calibrating parameters governing distributions of agent types rather than individual agents, which allows both behavior differentiation among agents and coherent scaling of the shared policy network to multiple agents.

Though reinforcement learning has greatly benefited from the incorporation of neural networks, the inability to verify the correctness of such systems limits their use. Current work in explainable deep learning focuses on explaining only a single decision in terms of input features, making it unsuitable for explaining a sequence of decisions. To address this need, we introduce Abstracted Policy Graphs, which are Markov chains of abstract states. This representation concisely summarizes a policy so that individual decisions can be explained in the context of expected future transitions. Additionally, we propose a method to generate these Abstracted Policy Graphs for deterministic policies given a learned value function and a set of observed transitions, potentially off-policy transitions used during training. Since no restrictions are placed on how the value function is generated, our method is compatible with many existing reinforcement learning methods. We prove that the worst-case time complexity of our method is quadratic in the number of features and linear in the number of provided transitions, O(|F|2|tr samples|). By applying our method to a family of domains, we show that our method scales well in practice and produces Abstracted Policy Graphs which reliably capture relationships within these domains.

Achieving effective task performance on real mobile robots is a great challenge when hand-coding algorithms, both due to the amount of effort involved and manually tuned parameters required for each skill. Learning algorithms instead have the potential to lighten up this challenge by using one single set of training parameters for learning different skills, but the question of the feasibility of such learning in real robots remains a research pursuit. We focus on a kind of mobile robot system - the robot soccer “small-size” domain, in which tactical and high-level team strategies build upon individual robot ball-based skills. In this paper, we present our work using a Deep Reinforcement Learning algorithm to learn three real robot primitive skills in continuous action space: go-to-ball, turn-and-shoot and shoot-goalie, for which there is a clear success metric to reach a destination or score a goal. We introduce the state and action representation, as well as the reward and network architecture. We describe our training and testing using a simulator of high physical and hardware fidelity. Then we test the policies trained from simulation on real robots. Our results show that the learned skills achieve an overall better success rate at the expense of taking 0.29 seconds slower on average for all three skills. In the end, we show that our policies trained in simulation have good performance on real robots by directly transferring the policy.

The sample inefficiency of standard deep reinforcement learning methods precludes their application to many real-world problems. Methods which leverage human demonstrations require fewer samples but have been researched less. As demonstrated in the computer vision and natural language processing communities, large-scale datasets have the capacity to facilitate research by serving as an experimental and benchmarking platform for new methods. However, existing datasets compatible with reinforcement learning simulators do not have sufficient scale, structure, and quality to enable the further development and evaluation of methods focused on using human examples. Therefore, we introduce a comprehensive, large-scale, simulator-paired dataset of human demonstrations: MineRL. The dataset consists of over 60 million automatically annotated state-action pairs across a variety of related tasks in Minecraft, a dynamic, 3D, open-world environment. We present a novel data collection scheme which allows for the ongoing introduction of new tasks and the gathering of complete state information suitable for a variety of methods. We demonstrate the hierarchality, diversity, and scale of the MineRL dataset. Further, we show the difficulty of the Minecraft domain along with the potential of MineRL in developing techniques to solve key research challenges within it.

As robots are increasingly endowed with social and communicative capabilities, they will interact with humans in more settings, both collaborative and competitive. We explore human-robot relationships in the context of a competitive Stackelberg Security Game. We vary humanoid robot expressive language (in the form of “encouraging” or “discouraging” verbal commentary) and measure the impact on participants' rationality, strategy prioritization, mood, and perceptions of the robot. We learn that a robot opponent that makes discouraging comments causes a human to play a game less rationally and to perceive the robot more negatively. We also contribute a simple open source Natural Language Processing framework for generating expressive sentences, which was used to generate the speech of our autonomous social robot.

While mobile robots reliably perform each service task by accurately localizing and safely navigating avoiding obstacles, they do not respond in any other way to their surroundings. We can make the robots more responsive to their environment by equipping them with models of multiple tasks and a way to interrupt a specific task and switch to another task based on observations. However the challenges of a multiple task model approach include selecting a task model to execute based on observations and having a potentially large set of observations associated with the set of all individual task models. We present a novel two-step solution. First, our approach leverages the tasks' policies and an abstract representation of their states, and learns which task should be executed at each given world state. Secondly, the algorithm uses the learned tasks and identifies the observation stimuli that trigger the interruption of one task and the switch to another task. We show that our solution using the switching stimuli compares favorably to the naive approach of learning a combined model for all the tasks. Moreover, leveraging the stimuli significantly decreases the amount of sensory input processing during the execution of tasks.

Despite the recent success of state-of-the-art deep learning algorithms in object recognition, when these are deployed as-is on a mobile service robot, we observed that they failed to recognize many objects in real human environments. In this paper, we introduce a learning algorithm in which robots address this flaw by asking humans for help, also known as a symbiotic autonomy approach. In particular, we bootstrap YOLOv2, a state-of-the-art deep neural network and train a new neural network, that we call HHELP, using only data collected from human help. Using an RGB camera and an onboard tablet, the robot proactively seeks human input to assist it in labeling surrounding objects. Pepper, located at CMU, and Monarch Mbot, located at ISR-Lisbon, were the service robots that we used to validate the proposed approach. We conducted a study in a realistic domestic environment over the course of 20 days with 6 research participants. To improve object detection, we used the two neural networks, YOLOv2 + HHELP, in parallel. Following this methodology, the robot was able to detect twice the number of objects compared to the initial YOLOv2 neural network, and achieved a higher mAP (mean Average Precision) score. Using the learning algorithm the robot also collected data about where an object was located and to whom it belonged to by asking humans. This enabled us to explore a future use case where robots can search for a specific person's object. We view the contribution of this work to be relevant for service robots in general, in addition to Pepper, and Mbot.

For autonomous multi-robot teams, the individual team members are tasked with completing their assigned tasks as defined by a team plan provided by a centralized team planner. However in complex dynamic domains, the team plans are generated by the team planner with assumptions due to the complexity of modeling the domain. Failures in execution are therefore inevitable for the team members, and as such, replanning will occur for the team. In this paper, we introduce a rationale-driven team plan representation that provides rationales on why actions were chosen by the team planner. During a failure, the individual team members autonomously use our described intra-robot replanning algorithm to select all applicable replan policies for a given rationale. We then describe a method to learn the predicted cost of each replan policy, given a state of the environment, in order for the individual robots to select the lowest costing replan policy to improve team performance.

Teaching a robot to predict and mimic how a human moves or acts in the near future by observing a series of historical human movements is a crucial first step in human-robot interaction and collaboration. In this paper, we instrument a robot with such a prediction ability by leveraging recent deep learning and computer vision techniques. First, our system takes images from the robot camera as input to produce the corresponding human skeleton based on real-time human pose estimation obtained with the OpenPose library. Then, conditioning on this historical sequence, the robot forecasts plausible motion through a motion predictor, generating a corresponding demonstration. Because of a lack of high-level fidelity validation, existing forecasting algorithms suffer from error accumulation and inaccurate prediction. Inspired by generative adversarial networks (GANs), we introduce a global discriminator that examines whether the predicted sequence is smooth and realistic. Our resulting motion GAN model achieves superior prediction performance to state-of-the-art approaches when evaluated on the standard H3.6M dataset. Based on this motion GAN model, the robot demonstrates its ability to replay the predicted motion in a human-like manner when interacting with a person.

Kinesthetic learning is a type of learning from demonstration in which the teacher manually moves the robot through the demonstrated trajectory. It shows great promise in the area of assistive robotics since it enables a caretaker who is not an expert in computer programming to communicate a novel task to an assistive robot. However, the trajectory the caretaker demonstrates to solve the task may be a high-cost trajectory for the robot. The demonstrated trajectory could be high-cost because the teacher does not know what trajectories are easy or hard for the robot to perform, which would be due to a limitation of the teacher's knowledge, or because the teacher has difficulty moving all the robotic joints precisely along the desired trajectories, which would be due to a limitation of the teacher's coordination. We propose the Parameterized Similar Path Search (PSPS) algorithm to extend kinesthetic learning so that a robot can improve the learned trajectory over a known cost function. This algorithm is based on active learning from the robot through collaboration between the robot's knowledge of the cost function and the caretaker's knowledge of the constraints of the assigned task.

editorial Open AccessThe Increasingly Fascinating Opportunity for Human-Robot-AI Interaction: The CoBot Mobile Service Robots Share on Author: Manuela M. Veloso Carnegie Mellon University, Pittsburgh PA, USA Carnegie Mellon University, Pittsburgh PA, USAView Profile Authors Info & Affiliations ACM Transactions on Human-Robot InteractionVolume 7Issue 1May 2018 Article No.: 5pp 1–2https://doi.org/10.1145/3209541Published:16 May 2018 3citation668DownloadsMetricsTotal Citations3Total Downloads668Last 12 Months261Last 6 weeks26 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Automated data collection in urban transportation systems produces a large volume of passenger data. However, quite a few of the data are still incomplete, limiting the insight into passenger mobility. The unavailability of destination information in entry-only passenger data is a very common issue. Traditional approaches for estimating passenger destinations rely on heuristics that can recover only some of the missing destinations. To deal with the remaining incomplete data, this paper, for the first time, proposes a second-order inference methodology to leverage semi-supervised self-training to infer the missing destinations. The methodology involves the design of a base learner to predict the missing destinations based on the statistics of a selected similarity-based "training set", and the design of a selection strategy to select new data with high prediction confidence to update the training set. To further improve the inference, we incorporate personal history priors to modify the base learner. We evaluate our designs using two data sources: a real-data inspired traffic-passenger behavior simulation in the city of Porto, Portugal, and the real bus Automated Fare Collection (AFC) data collected from the same city. The experimental results show that compared to baseline methods that do not use self-training, our approach significantly improves the inference performance and achieves notably high accuracies.

A robot performs a sequence of motions to animate a given input, e.g., dancing to music or telling a story. Each input is pre-processed to determine labels, e.g., emotions of the music or words in the story. Each label corresponds to multiple motions, and each motion has multiple labels. Therefore, the robot can choose one sequence from multiple motion sequences to animate the input. We aim to choose the best sequence to animate based on the audience's preferences. The audience prefers some motions over others, and each motion has an initially unknown preference value. At the end of the motion sequence, the audience provides feedback which is the sum of the motions' preference values. However, the observation of the feedback is noisy due to the device used to capture the audience's feedback. To select the most preferred sequence, the robot has to determine the sequence to query the audience with, so as to learn the preference values of individual motions from noisy observations of the audience's feedback. By learning the individual motion preference values, the most preferred sequence can be determined. Moreover, the audience may get bored of watching the same single motion in multiple sequences and the preference value will degrade based on the number of times the motion is viewed. We contribute MAK (Multi-Armed bandit and Kalman filter) and show that MAK outperforms least squares regression in selecting the best sequence with lower degradation in our simulation experiments.

Individual team members are the building blocks of successful multi-robot teams in dynamic competitive domains. The current approach to designing a team is to divide the planning into a hierarchy by separating team coordination and task assignment - global planning - from task planning and execution - local planning. The global planner must make assumptions based on simplified models of dynamics and/or opponents, and as such certain conditions are assumed true when globally planning but are not always true at local execution time. In this paper, we describe several algorithms for intra-robot replanning that allow the individual robots to enable the conditions of their tasks. We then demonstrate improvements in task completion when the robots are capable of replanning their task(s) and their teammates' task(s) in a simplified robot soccer domain. We further show preliminary results on learning when to replan.

This paper addresses the problem of human-robot collaboration in scenarios where a robot assists a human by executing a complex motion involving the manipulation of an object. We focus on tasks in which success in the task depends on reaching a target pose that is controlled by the human. We contribute a reinforcement learning-based approach that allows the robot to reason about its own ability to successfully complete the task given the current target pose and indirectly adjust that pose by prompting the human user. Our approach allows the robot both to trade-off the benefits of adjusting the target position against the cost of bothering the human user while, at the same time, adapting to each user's responses. Our approach was tested in a real-world human-robot collaboration scenario involving the Baxter robot.

Autonomous mobile robots continuously perceive the world, plan or replan to achieve objectives, and execute the selected actions. Videos of autonomous robots are often naturally used to aid in replaying and demonstrating robot performance. However, plain videos contain no information about the ongoing internals of the robots. In this work, we contribute an approach to automate the overlay of visual annotations on videos of robots' execution to capture information underlying their reasoning. We concretely focus our presentation on the complex robot soccer domain, where the high speed of the robots' execution results from action planning for collaboration and response to the adversary.

We present a novel approach to enable a mobile service robot to understand questions about the history of tasks it has executed. We frame the problem of understanding such questions as grounding an input sentence to a query that can be executed on the logs recorded by the robot during its runs. We define a query as an operation followed by a set of filters. In order to ground sentence to a query we introduce a joint probabilistic model. The model is composed by a shallow semantic parser and a knowledge base to store and re-use the groundings of a sentence. The Knowledge Base and its predicates are designed to match the structure of a query. Our results show that, by using such Knowledge Base, the approach proposed requires fewer and fewer corrections as users interact with the system.

The efficiency of heuristic search depends dramatically on the quality of the heuristic function. For an optimal heuristic search, heuristics that estimate cost-to-goal better typically lead to faster searches. For a sub-optimal heuristic search such as weighted A*, the search speed depends more on the correlation between the heuristic and the true cost-to-goal. In this extended abstract, we discuss our preliminary work on computing heuristic functions that exploit this fact. In particular, we introduce a many-to-one mapping from an original search space to a conservative abstract space. Edges in the abstract space capture reachability among all corresponding nodes in the original space. We compute a heuristic in the conservative abstract space which when used by the search in the original space reduces the number of searched nodes. Our preliminary results on 3D navigation show that in more complex scenarios the speedup can be dramatic.

CMDragons 2015 is the champion of the RoboCup Small Size League of autonomous robot soccer. The team won all of its six games, scoring a total of 48 goals and conceding 0. This unprecedented dominant performance is the result of various features, but we particularly credit our novel offense multi-robot coordination. This paper thus presents our Selectively Reactive Coordination (SRC) algorithm, consisting of two layers: A coordinated opponent-agnostic layer enables the team to create its own plans, setting the pace of the game in offense. An individual opponent-reactive action selection layer enables the robots to maintain reactivity to different opponents. We demonstrate the effectiveness of our coordination through results from RoboCup 2015, and through controlled experiments using a physics-based simulator and an automated referee.

The World Wide Web (WWW) has become a rapidly growing platform consisting of numerous sources which provide supporting or contradictory information about claims (e.g., "Chicken meat is healthy"). In order to decide whether a claim is true or false, one needs to analyze content of different sources of information on the Web, measure credibility of information sources, and aggregate all these information. This is a tedious process and the Web search engines address only part of the overall problem, viz., producing only a list of relevant sources. In this paper, we present ClaimEval, a novel and integrated approach which given a set of claims to validate, extracts a set of pro and con arguments from the Web information sources, and jointly estimates credibility of sources and correctness of claims. ClaimEval uses Probabilistic Soft Logic (PSL), resulting in a flexible and principled framework which makes it easy to state and incorporate different forms of prior-knowledge. Through extensive experiments on real-world datasets, we demonstrate ClaimEval’s capability in determining validity of a set of claims, resulting in improved accuracy compared to state-of-the-art baselines.

In this paper we introduce the problem of planning for perception of a target position. Given a sensing target, the robot has to move to a goal position from where the target can be perceived. Our algorithm minimizes the overall path cost as a function of both motion and perception costs, given an initial robot position and a sensing target. We contribute a heuristic search method, PA*, that efficiently searches for an optimal path. We prove the proposed heuristic is admissible, and introduce a new goal state stopping condition.

This paper addresses the problem of human-robot collaboration in the context of manipulation tasks. In particular, we focus on tasks where a robot must perform some complex manipulation that is successfully completed only upon reaching some target pose provided by a human user. We propose an approach in which the robot explicitly reasons about its ability to complete the task and proactively requests the assistance of the human teammate when necessary. Our approach effectively trades-off the benefits arising from the human assistance with the cost of disturbing the user. We also propose an adaptation mechanism that enables the robot to adjust its behavior to the particular manner by which the human user responds to the requests made by the robot. We test our approach in a simple illustrative scenario and in two real interaction scenarios involving the Baxter robot.

With the introduction of autonomous robots that help perform various tasks in our environments, we can opportunistically use them for collecting fine-grain sensor measurements about our surroundings. Use of mobile robots for data collection scales much better than static sensors in terms of number of measurement locations and provide more fine-grain accuracy and reliability than alternate human crowd-sourcing efforts. One of the unique features of mobile robots is the ability to control and direct where and when measurements should be collected. In this paper, we present a system to compute paths for the robot to follow that incorporates the robot's limited expected deployment time, expected measurement value at each location, and a history of when each location was last visited.

We introduce in this paper visibility maps for robots of any shape, representing the reachability limit of the robot's motion and sensing in a 2D gridmap with obstacles. The brute-force approach to determine the optimal visibility map is computationally expensive, and prohibitive with dynamic obstacles. We contribute the Robot-Dependent Visibility Map (RDVM) as a close approximation to the optimal, and an effective algorithm to compute it. The RDVM is a function of the robot's shape, initial position, and sensor model. We first overview the computation of RDVM for the circular robot case in terms of the partial morphological closing operation and the optimal choice for the critical points position. We then present how the RDVM for any-shape robots is computed. In order to handle any robot shape, we introduce in the first step multiple layers that discretize the robot orientation. In the second step, our algorithm determines the frontiers of actuation, similarly to the case of the the circular robot case. We then derive the concept of critical points to the any-shape robot, as the points that maximize expected visibility inside unreachable regions. We compare our method with the ground-truth in a simulated map compiled to capture a variety of challenges of obstacle distribution and type, and discuss the accuracy of our approximation to the optimal visibility map.

A labeled motion library, in which robot motions are associated with semantic meanings, e.g., words, is useful for human-robot interaction, as a robot can use it to autonomously select motions to support its non-verbal communication. Manually assigning labels to new motions to a motion library is time consuming. However, a new motion may be similar to motions in the labeled motion library, and can be mapped to existing labels. We formally define motions, labels, and mappings between motions and labels. We use a NAO humanoid robot as a motivating example, though our approach is general for use on a humanoid robot with rotational joints. We explain how we generate motions and labels, define eight distance metrics to determine the similarity between motions, and use the nearest neighbor algorithm to determine the labels of a new motion. The distance metrics are varied across three axes - Euclidean versus Hausdorff, joint angles versus points of interest (postures), and mirrored versus non-mirrored. We evaluate the efficacy of these eight distance metrics, using precision, recall, and computational complexity.

In order to be successfully integrated into human-populated environments, mobile robots need to express relevant information about their state to the outside world. In particular, animated lights are a promising way to express hidden robot state information such that it is visible at a distance. In this work, we present an online study to evaluate the effect of robot communication through expressive lights on people's understanding of the robot's state and actions. In our study, we use the CoBot mobile service robot with our light interface, designed to express relevant robot information to humans. We evaluate three designed light animations on three corresponding scenarios for each, for a total of nine scenarios. Our results suggest that expressive lights can play a significant role in helping people accurately hypothesize about a mobile robot's state and actions from afar when minimal contextual clues are present. We conclude that lights could be generally used as an effective non-verbal communication modality for mobile robots in the absence of, or as a complement to, other modalities.

With a growing number of robots performing autonomously without human intervention, it is difficult to understand what the robots experience along their routes during execution without looking at execution logs. Rather than looking through logs, our goal is for robots to respond to queries in natural language about what they experience and what routes they have chosen. We propose verbalization as the process of converting route experiences into natural language, and highlight the importance of varying verbalizations based on user preferences. We present our verbalization space representing different dimensions that verbalizations can be varied, and our algorithm for automatically generating them on our CoBot robot. Then we present our study of how users can request different verbalizations in dialog. Using the study data, we learn a language model to map user dialog to the verbalization space. Finally, we demonstrate the use of the learned model within a dialog system in order for any user to request information about CoBot's route experience at varying levels of detail.

We present a method to learn context-dependent outcomes of behaviors in unstructured indoor environments. The idea is that certain features in the environment may be predictive of differences in outcomes, such as how long a mobile robot takes to traverse a corridor. Doing so enables the robot to plan more effectively, and also be able to interact with people more effectively by more accurately predicting when its plans may take longer to execute or may be likely to fail. We use a node-and-edge based map of the environment and treat the traversal time of the robot for each edge as a random variable to be characterized. The first step is to determine whether the distribution of the random variable is multimodal and, if so, we learn to classify the modes using a hierarchy of plan-time features (e.g., time of the day, day of the week) and run-time features (observations of recent traversal times through other corridors). We utilize a cascading regression system that first estimates which mode of the traversal distribution we expect the robot to observe, and then predict the actual traversal time through a corridor. On average, our method produces a mean residual error of less than 2.7 seconds.

Modeling the effects of actions based on the state of the world enables robots to make intelligent decisions in different situations. However, it is often infeasible to have globally accurate models. Task performance is often hindered by discrepancies between models and the real world, since the true outcome of executing a plan may be significantly worse than the expected outcome used during planning. Furthermore, expectations about the world are often stochastic in robotics, making the discovery of model-world discrepancies non-trivial. We present an execution monitoring framework capable of finding statistically significant discrepancies, determining the situations in which they occur, and making simple corrections to the world model to improve performance. In our approach, plans are initially based on a model of the world that is only as faithful as computational and algorithmic limitations allow. Through experience, the monitor discovers previously unmodeled modes of the world, defined as regions of a feature space in which the experienced outcome of a plan deviates significantly from the predicted outcome. The monitor may then make suggestions to change the model to match the real world more accurately. We demonstrate this approach on the adversarial domain of robot soccer: we monitor pass interception performance of potentially unknown opponents to try to find unforeseen modes of behavior that affect their interception performance.

Most wireless solutions today are centered around people-centric devices like laptops and cell phones that are insufficient for mobile robots. The key difference is that people-centric devices use wireless connectivity in bursts under primarily stationary settings while mobile robots continuously transmit data even while moving. When mobile robots use existing wireless solutions, it results in intolerable and seemingly random interruptions in wireless connectivity when moving [1]. These wireless issues stem from suboptimal switching across wireless infrastructure access points (APs), also called AP handoffs. These poor handoff decisions are due to stateless handoff algorithms that make wireless decisions solely from immediate and noisy scans of surrounding wireless conditions. In this paper, we propose to overcome these motion-based wireless connectivity issues for autonomous robots using highly informed handoff algorithms that combine fine-grain wireless maps with accurate robot localization. Our results show significant wireless performance improvements for continuously moving robots in real environments without any modifications to the wireless infrastructure.

In this paper, we consider several autonomous robots with separate tasks that require coordination, but not a coupling at every decision step. We assume that each robot separately acquires its task, possibly from different providers. We address the problem of multiple robots incrementally acquiring tasks that require their sparse-coordination. To this end, we present an approach to provide tasks to multiple robots, represented as sequences, conditionals, and loops of sensing and actuation primitives. Our approach leverages principles from sparse-coordination to acquire and represent these joint-robot plans compactly. Specifically, each primitive has associated preconditions and effects, and robots can condition on the state of one another. Robots share their state externally using a common domain language. The complete sparse-coordination framework runs on several robots. We report on experiments carried out with a Baxter manipulator and a CoBot mobile service robot.

Global localization is a widely studied problem, and in essence corresponds to the online robot pose estimation based on a given map with landmarks, an odometry model, and real robot sensory observations and motion. In most approaches, the map provides the position of visible objects, which are then recognized to provide the robot pose estimation. Such object recognition with noisy sensory data is challenging. In this paper, we present an effective global localization technique using soft 3D object recognition to estimate the pose with respect to the landmarks in the given map. A depth sensor acquires a partial view for each observed object, from which our algorithm extracts the robot pose relative to the objects, based on a library of 3D Partial View Heat Kernel descriptors. Our approach departs from methods that require classification and registration against complete 3D models, which are prone to errors due to noisy sensory data and object misclassifications in the recognition stage. We experimentally validate our method in different robot paths with different common 3D environment objects. We also show the improvement of our method compared to when the partial view information is not used.

Robot table tennis is a challenging domain in both robotics, artificial intelligence and machine learning. In terms of robotics, it requires fast and reliable perception and control; in terms of artificial intelligence, it requires fast decision making to determine the best motion to hit the ball; in terms of machine learning, it requires the ability to accurately estimate where and when the ball will be so that it can be hit. The use of sophisticated perception (relying, for example, in multi-camera vision systems) and state-of-the-art robot manipulators significantly alleviates concerns with perception and control, leaving room for the exploration of novel approaches that focus on estimating where, when and how to hit the ball. In this paper, we move away from the hardware setup commonly used in this domain-typically relying on robotic manipulators combined with an array of multiple fixed cameras-and give the first steps towards having autonomous aerial table tennis robotic players. Specifically, we focus on the task of hitting a ping pong ball thrown at a commercial drone, equipped with a light cardboard racket and an onboard camera. We adopt a general framework for learning complex robot tasks and show that, in spite of the perceptual and actuation limitations of our system, the overall approach enables the quadrotor system to successfully respond to balls served by a human user.

We consider the problem of indoor human trajectory identification using odometry data from smartphone sensors. Given a segmented trajectory, a simplified map of the environment, and a set of error thresholds, we implement a map-matching algorithm in a urban setting and analyze the accuracy of the resulting path. We also discuss aggregation of user step data into a segmented trajectory. Besides providing an interesting application of learning human motion in a constrained environment, we examine how the uncertainty of the snapped trajectory varies with path length. We demonstrate that as new segments are added to a path, the number of possibilities for earlier segments is monotonically non-increasing. Applications of this work in an urban setting are discussed, as well as future plans to develop a formal theory of odometry-based map-matching.

In our experiment, two autonomously moving costumed robots visit 256 offices during a `reverse' trick-or-treating task close to Halloween. Our behavioral data supports the idea that people interpret a robot's non-verbal cues, as the robots' costuming and baskets of candy seem to have communicated an implicit offer of candy. In fact, one third of our detection instances occurred during robot transit, i.e., while the robots were making no verbal offer. We find that candy accessibility dominates any social influence of robot orientation and that robot speed influences both whether people will interrupt a robot in transit (slow more interruptible) and whether they will respond to its verbal offer (fast more salient).

In this work, we consider an autonomous robot that is required to understand commands given by a human through natural language. Specifically, we assume that this robot is provided with an internal representation of the environment. However, such a representation is unknown to the user. In this context, we address the problem of allowing a human to understand the robot internal representation through dialog. To this end, we introduce the concept of sensing descriptors . Such representations are used by the robot to recognize unknown object properties in the given commands and warn the user about them. Additionally, we show how these properties can be learned over time by leveraging past interactions in order to enhance the grounding capabilities of the robot.

The CMDragons Small Size League (SSL) team won all of its 6 games at RoboCup 2015, scoring a total of 48 goals and conceding 0. This paper presents the core coordination algorithms in offense and defense that enabled such successful performance. We first describe the coordinated plays layer that distributes the team’s robots into offensive and defensive subteams. We then describe the offense and defense coordination algorithms to control these subteams. Effective coordination enables our robots to attain a remarkable level of team-oriented gameplay, persistent offense, and reliability during regular gameplay, shifting our strategy away from stopped ball plays. We support these statements and the effectiveness of our algorithms with statistics from our performance at RoboCup 2015. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The current paper addresses the problem of object identification from multiple3D partial views, collected from different view angles with the objective of disambiguating between similar objects. We assume a mobile robot equipped with a depth sensor that autonomously collects observations from an object from different positions, with no previous known pattern. The challenge is to efficiently combine the set of observations into a single classification. We approach the problem with a multiple hypothesis filter that allows to combine information from a sequence of observations given the robot movement. We further innovate by off-line learning neighborhoods between possible hypothesis based on the similarity of observations. Such neighborhoods translate directly the ambiguity between objects, and allow to transfer the knowledge of one object to the other. In this paper we introduce our algorithm, Multiple Hypothesis for Object Class Disambiguation from Multiple Observations, and evaluate its accuracy and efficiency.

In pickup and delivery problems (PDPs), vehicles pickup and deliver a set of items under various constraints. We address the PDP with Transfers (PDP-T), in which vehicles plan to transfer items between one another to form more efficient schedules. We introduce the Very Large Neighborhood Search with Transfers (VLNS-T) algorithm to form schedules for the PDP-T. Our approach allows multiple transfers for items at arbitrary locations, and is not restricted to a set of predefined transfer points. We show that VLNS-T improves upon the best known PDP solutions for benchmark problems, and demonstrate its effectiveness on problems sampled from real world taxi data in New York City.

Markov localization and its variants are widely used for localization of mobile robots. These methods assume Markov independence of observations, implying that observations made by a robot correspond to a static map. However, in real human environments, observations include occlusions due to unmapped objects like chairs and tables, and dynamic objects like humans. We introduce an episodic non-Markov localization algorithm that maintains estimates of the belief over the trajectory of the robot while explicitly reasoning about observations and their correlations arising from unmapped static objects, moving objects, as well as objects from the static map. Observations are classified as arising from long-term features, short-term features, or dynamic features, which correspond to mapped objects, unmapped static objects, and unmapped dynamic objects respectively. By detecting time steps along the robot's trajectory where unmapped observations prior to such time steps are unrelated to those afterwards, non-Markov localization limits the history of observations and pose estimates to “episodes” over which the belief is computed. We demonstrate non-Markov localization in challenging real world indoor and outdoor environments over multiple datasets, comparing it with alternative state-of-the-art approaches, showing it to be robust as well as accurate.

We introduce the Partial View Heat Kernel (PVHK) descriptor, for the purpose of 3D object representation and recognition from partial views, assumed to be partial object surfaces under self occlusion. PVHK describes partial views in a geometrically meaningful way, i.e., by establishing a unique relation between the shape of the view and the descriptor. PVHK is also stable with respect to sensor noise and therefore adequate for sensors, such as the current active 3D cameras. Furthermore, PVHK takes full advantage of the dual 3D/RGB nature of current sensors and seamlessly incorporates appearance information onto the 3D information. We formally define the PVHK descriptor, discuss related work, provide evidence of the PVHK properties and validate them in three purposefully diverse datasets, and demonstrate its potential for recognition tasks.

We have deployed a fleet of robots that pickup and deliver items requested by users in an office building. Users specify time windows in which the items should be picked up and delivered, and send in requests online. Our goal is to form a schedule which picks up and delivers the items as quickly as possible at the lowest cost. We introduce an auction-based scheduling algorithm which plans to transfer items between robots to make deliveries more efficiently. The algorithm can obey either hard or soft time constraints. We discuss how to replan in response to newly requested items, cancelled requests, delayed robots, and robot failures. We demonstrate the effectiveness of our approach through execution on robots, and examine the effect of transfers on large simulated problems.

This paper presents an online algorithm for early detection of anomalies in robot execution, where the anomalies occur in a particular region of the robot's state space. Assuming that a model of normal execution is given, the algorithm detects regions of space where data significantly deviate from normal. It achieves this by focusing optimization over a fixed-parameter family of shapes to find the one among them that is most likely anomalous, and then using this region to decide whether execution is anomalous. Experiments using synthetic and real robot data support the effectiveness of the approach.

An increasing number of wearable and mobile devices are capable of automatically sensing and recording rich information about the surrounding environment. To make use of such data, it is desirable for each data point to be matched with its corresponding spatial location. We focus on using the trajectory from a device's odometry sensors that reveal changes in motion over time. Our goal is to recover the route traversed, which we will define as a sequence of revisitable positions. Dead reckoning, which computes the device's route from its odometry trajectory, is known to suffer from significant drift over time. We aim to overcome drift errors by reshaping the odometry trajectory to fit the constraints of a given topological map and sensor noise model. Prior works use iterative search algorithms that are susceptible to local maximas [15], which means that they can be misled when faced with ambiguous decisions. In contrast, our algorithm is able to find the set of all routes within the given constraints. This also reveals if there are multiple routes that are similarly likely. We can then rank them and select the optimal route that is most likely to be the actual route. We also show that the algorithm can be extended to recover routes even in the presence of topological map errors. We evaluate our algorithm by recovering all routes traversed by a wheeled robot covering over 9 kilometers from its odometry sensor data.

Recently, ridesharing mobile applications, which dynamically match passengers to drivers, have begun to gain popularity. These services have the potential to fill empty seats in cars, reduce emissions and enable more efficient transportation. Ridesharing services become even more practical as robotic cars become available to do all the driving. In this work, we propose rideshare services which transfer passengers between multiple drivers. By planning for transfers, we can increase the availability and range of the rideshare service, and also reduce the total vehicular miles travelled by the network. We propose three heuristic algorithms to schedule rideshare routes with transfers. Each gives a tradeoff in terms of effectiveness and computational cost. We demonstrate these tradeoffs, both in simulation and on data from taxi passengers in San Francisco. We demonstrate scenarios where transferring passengers can provide a significant advantage.

The robot coverage problem, a common planning problem, consists of finding a motion path for the robot that passes over all points in a given area or space. In many robotic applications involving coverage, e.g., industrial cleaning, mine sweeping, and agricultural operations, the desired coverage area is large and of arbitrary layout. In this work, we address the real problem of planning for coverage when the robot has limited battery or fuel, which restricts the length of travel of the robot before needing to be serviced. We introduce a new sweeping planning algorithm, which builds upon the boustrophedon cellular decomposition coverage algorithm to include a fixed fuel or battery capacity of the robot. We prove the algorithm is complete and show illustrative examples of the planned coverage outcome in a real building floor map.

An attractive approach to managing electricity demand in the Smart Grid relies on real-time pricing (RTP) tariffs, where customers are incentivized to quickly adapt to changes in the cost of supply. However, choosing amongst competitive RTP tariffs is difficult when tariff prices change rapidly. The problem is further complicated when we assume that the price changes for a tariff are published in real-time only to those customers who are currently subscribed to that tariff, thus making the prices partially observable. We present models and learning algorithms for autonomous agents that can address the tariff selection problem on behalf of customers. We introduce 'Negotiated Learning', a general algorithm that enables a self-interested sequential decision-making agent to periodically select amongst a variable set of 'entities' (e.g., tariffs) by negotiating with other agents in the environment to gather information about dynamic partially observable entity 'features' (e.g., tariff prices) that affect the entity selection decision. We also contribute a formulation of the tariff selection problem as a 'Negotiable Entity Selection Process', a novel representation. We support our contributions with intuitive justification and simulation experiments based on real data on an open Smart Grid simulation platform.

In this paper, we investigate information validation tasks that are initiated as queries from either automated agents or humans. We introduce OpenEval, a new online information validation technique, which uses information on the web to automatically evaluate the truth of queries that are stated as multi-argument predicate instances (e.g., DrugHasSideEffect(Aspirin,GI Bleeding)). OpenEval gets a small number of instances of a predicate as seed positive examples and automatically learns how to evaluate the truth of a new predicate instance by querying the web and processing the retrieved unstructured web pages. We show that OpenEval is able to respond to the queries within a limited amount of time while also achieving high F1 score. In addition, we show that the accuracy of responses provided by OpenEval is increased as more time is given for evaluation. We have extensively tested our model and shown empirical results that illustrate the effectiveness of our approach compared to related techniques.

A human detection algorithm running on an indoor mobile robot has to address challenges including occlusions due to cluttered environments, changing backgrounds due to the robot's motion, and limited on-board computational resources. We introduce a fast human detection algorithm for mobile robots equipped with depth cameras. First, we segment the raw depth image using a graph-based segmentation algorithm. Next, we apply a set of parameterized heuristics to filter and merge the segmented regions to obtain a set of candidates. Finally, we compute a Histogram of Oriented Depth (HOD) descriptor for each candidate, and test for human presence with a linear SVM. We experimentally evaluate our approach on a publicly available dataset of humans in an open area as well as our own dataset of humans in a cluttered cafe environment. Our algorithm performs comparably well on a single CPU core against another HOD-based algorithm that runs on a GPU even when the number of training examples is decreased by half. We discuss the impact of the number of training examples on performance, and demonstrate that our approach is able to detect humans in different postures (e.g. standing, walking, sitting) and with occlusions.

This paper presents an approach for learning environmental knowledge from task-based human-robot dialog. Previous approaches to dialog use domain knowledge to constrain the types of language people are likely to use. In contrast, by introducing a joint probabilistic model over speech, the resulting semantic parse and the mapping from each element of the parse to a physical entity in the building (e.g., grounding), our approach is flexible to the ways that untrained people interact with robots, is robust to speech to text errors and is able to learn referring expressions for physical locations in a map (e.g., to create a semantic map). Our approach has been evaluated by having untrained people interact with a service robot. Starting with an empty semantic map, our approach is able ask 50% fewer questions than a baseline approach, thereby enabling more effective and intuitive human robot dialog.

Poor sensor data because of uncertainty and hardware limitations results in a robot misinterpreting the state of its surrounding environment, leading to bad decisions and eventually failure to successfully perform its desired tasks. These limitations can be overcome if a teammate robot with a better view shares its visual information. Our work aims to investigate why current approaches fail to effectively use teammate sensor data, propose an alternative where a teammate helps to better capture the state of the environment, and demonstrate that the robot can make better decisions when a teammate shares its perceptual data. Raw teammate sensor data is not meaningful unless provided a relative, geometric transform to place this data within another robot's own egocentric coordinates. There are few approaches that are able to discover this relative localization accurately in sparse environments while remaining computationally light. Our approach addresses these limitations by accumulating correspondence matches of objects over time from the overlapping views of two stationary robots to compute an accurate relative localization. We evaluate the benefits of teammate sensor data used with our computed relative localization with a challenging, time critical task where the robot's cameras alone are lacking. Our empirical results with two coordinating robots indicates that our approach is able to successfully take advantage of teammate robots with a better view within the challenging physical and hardware constraints of our robots.

We are interested in forming a multi-robot team that attains high utility at a task, and is robust to failures in the robots. We consider configurable robots that are composed of modules, e.g., motors, sensors, and actuators, where each module has an independent probability of failure. The performance of the multi-robot team at the task depends not only on how the robots in the team are composed from modules, but also the probability of failure of the selected modules. We formally define the robust team formation problem, and introduce two methods of defining the optimal team. We contribute the Robust Synergy Graph for Configurable Robots (ρ-SGraCR) model, and two team formation algorithms to find effective robust teams. The first algorithm, OptRobust, runs in exponential time and finds the optimal robust team. The second algorithm, ApproxRobust, makes assumptions about the module failures and approximates the optimal robust team, and runs in polynomial time. We demonstrate the efficacy of the ρ-SGraCR model in modeling robust team performance, and evaluate ApproxRobust and OptRobust. Finally, we apply the ρ-SGraCR model to a real robot problem in the foraging domain, and show that it outperforms competing approaches.

In many multi-robot problems, the performance of a team of robots is not the sum of their individual capabilities; there is often synergy among the robots. We recently introduced the synergy graph model to model such phenomena, where robots are represented by vertices in a graph, their capabilities represented by Normally-distributed variables, and the interactions of robots represented with the structure of the graph. The synergy graph is learned from observations of robot team performances, with the underlying assumption that observations of all the robots are available at once. However, it is common that new information becomes available over time, in particular as new robots enter the domain. In this paper, we contribute a learning algorithm that uses new information to add a new robot into an existing synergy graph, that requires a smaller number of observations and faster computation than relearning the entire synergy graph using the existing learning algorithms. We introduce three heuristics to initialize the learning algorithm, and perform extensive simulations to analyze their characteristics, as well as compare two methods of learning robot capabilities, over a variety of graph structure types. We also compare three approaches to learning synergy graphs, and demonstrate that adding a new teammate into an existing synergy graph introduces higher error than completely relearning the synergy graph. However, it is computationally less expensive to add a new teammate, especially when the number of robots is large.

Active participation of customers in the management of demand, and renewable energy supply, is a critical goal of the Smart Grid vision. However, this is a complex problem with numerous scenarios that are difficult to test in field projects. Rich and scalable simulations are required to develop effective strategies and policies that elicit desirable behavior from customers. We present a versatile agent-based "factored model" that enables rich simulation scenarios across distinct customer types and varying agent granularity. We formally characterize the decisions to be made by Smart Grid customers as a multiscale decision-making problem and show how our factored model representation handles several temporal and contextual decisions by introducing a novel "utility optimizing agent." We further contribute innovative algorithms for (i) statistical learning-based hierarchical Bayesian timeseries simulation, and (ii) adaptive capacity control using decision-theoretic approximation of multiattribute utility functions over multiple agents. Prominent among the approaches being studied to achieve active customer participation is one based on offering customers financial incentives through variable-price tariffs; we also contribute an effective solution to the problem of "customer herding" under such tariffs. We support our contributions with experimental results from simulations based on real-world data on an open Smart Grid simulation platform.

Indoor autonomous mobile service robots can overcome their hardware and potential algorithmic limitations by asking humans for help. In this work, we focus on mobile robots that need human assistance at specific spatially-situated locations (e.g., to push buttons in an elevator or to make coffee in the kitchen). We address the problem of what the robot should do when there are no humans present at such help locations. As the robots are mobile, we argue that they should plan to proactively seek help and travel to offices or occupied locations to bring people to the help locations. Such planning involves many trade-offs, including the wait time at the help location before seeking help, and the time and potential interruption to find and displace someone in an office. In order to choose appropriate parameters to represent such decisions, we first conduct a survey to understand potential helpers' travel preferences in terms of distance, interruptibility, and frequency of providing help. We then use these results to contribute a decision-theoretic algorithm to evaluate the possible choices in offices and plan where to proactively seek help. We demonstrate that our algorithm aims to minimize the number of office interruptions as well as task completion time.

In order for robots to intelligently perform tasks with humans, they must be able to access a broad set of background knowledge about the environments in which they operate. Unlike other approaches, which tend to manually define the knowledge of the robot, our approach enables robots to actively query the World Wide Web (WWW) to learn background knowledge about the physical environment. We show that our approach is able to search the Web to infer the probability that an object, such as a "coffee,'' can be found in a location, such as a "kitchen.'' Our approach, called ObjectEval, is able to dynamically instantiate a utility function using this probability, enabling robots to find arbitrary objects in indoor environments. Our experimental results show that the interactive version of ObjectEval visits 28% fewer locations than the version trained offline and 71% fewer locations than a baseline approach which uses no background knowledge.

The sheer volume of data generated by depth cameras provides a challenge to process in real time, in particular when used for indoor mobile robot localization and navigation. We introduce the Fast Sampling Plane Filtering (FSPF) algorithm to reduce the volume of the 3D point cloud by sampling points from the depth image, and classifying local grouped sets of points as belonging to planes in 3D (the “plane filtered” points) or points that do not correspond to planes within a specified error margin (the “outlier” points). We then introduce a localization algorithm based on an observation model that down-projects the plane filtered points on to 2D, and assigns correspondences for each point to lines in the 2D map. The full sampled point cloud (consisting of both plane filtered as well as outlier points) is processed for obstacle avoidance for autonomous navigation. All our algorithms process only the depth information, and do not require additional RGB data. The FSPF, localization and obstacle avoidance algorithms run in real time at full camera frame rates (30Hz) with low CPU requirements (16%). We provide experimental results demonstrating the effectiveness of our approach for indoor mobile robot localization and navigation. We further compare the accuracy and robustness in localization using depth cameras with FSPF vs. alternative approaches that simulate laser rangefinder scans from the 3D data.

Computationally efficient task execution is very important for autonomous mobile robots endowed with limited on-board computational capabilities. Most robot control approaches assume fixed state and action representations, and use a single algorithm to map states to actions. However, not all instances of a given task require equally complex algorithms and equally detailed representations. The main motivation for this work is a desire to reduce the computational footprint of performing a task by allowing the robot to run simpler algorithms whenever possible, and resort to more complex algorithms only when needed. We contribute the Multi-Resolution Task Execution (MRTE) algorithm that utilizes human feedback to learn a mapping from a given state to an appropriate detail resolution consisting of a state and action representation, and an algorithm. We then present Model Plus Correction (M+C), an algorithm that complements an existing robot controller with corrective human feedback to further improve the task execution performance. Finally, we introduce Multi-Resolution Model Plus Correction (MRM+C) as a combination of MRTE and M+C. We provide formal definitions of MRTE, M+C, and MRM+C, showing how they relate to general robot control problem and Learning from Demonstration (LfD) methods. We present detailed experimental results demonstrating the effectiveness of proposed methods on a simulated goal-directed humanoid obstacle avoidance task.

There has been considerable interest recently in building 3D maps of environments using inexpensive depth cameras like the Microsoft Kinect sensor. We exploit the fact that typical indoor scenes have an abundance of planar features by modeling environments as sets of plane polygons. To this end, we build upon the Fast Sampling Plane Filtering (FSPF) algorithm that extracts points belonging to local neighborhoods of planes from depth images, even in the presence of clutter. We introduce an algorithm that uses the FSPF-generated plane filtered point clouds to generate convex polygons from individual observed depth images. We then contribute an approach of merging these detected polygons across successive frames while accounting for a complete history of observed plane filtered points without explicitly maintaining a list of all observed points. The FSPF and polygon merging algorithms run in real time at full camera frame rates with low CPU requirements: in a real world indoor environment scene, the FSPF and polygon merging algorithms take 2.5 ms on average to process a single 640 × 480 depth image. We provide experimental results demonstrating the computational efficiency of the algorithm and the accuracy of the detected plane polygons by comparing with ground truth.

Heterogeneous robot teams are formed to perform complex tasks that are sub-divided into different roles. In ad hoc domains, the capabilities of the robots and how well they perform as a team is initially unknown, and the goal is to find the optimal role assignment policy of the robots that will attain the highest value. In this paper, we formally define the weighted synergy graph for role assignment (WeSGRA), that models the capabilities of robots in different roles as Normal distributions, and uses a weighted graph structure to model how different role assignments affect the overall team value. We contribute a learning algorithm that learns a WeSGRA from training examples of role assignment policies and observed values, and a team formation algorithm that approximates the optimal role assignment policy. We evaluate our model and algorithms in extensive experiments, and show that the learning algorithm learns a WeSGRA model with high log-likelihood that is used to form a near-optimal team. Further, we apply the WeSGRA model to simulated robots in the RoboCup Rescue domain, and to real robots in a foraging task, and show that the role assignment policy found by WeSGRA attains a high value and outperforms other algorithms, thus demonstrating the efficacy of the WeSGRA model.

As mobile robots become better equipped to autonomously navigate in human-populated environments, they need to become able to recognize internal and external factors that may interfere with successful motion execution. Even when these robots are equipped with appropriate obstacle avoidance algorithms, collisions and other forms of motion interference might be inevitable: there may be obstacles in the environment that are invisible to the robot's sensors, or there may be people who could interfere with the robot's motion. We present a Hidden Markov Model-based model for detecting such events in mobile robots that do not include special sensors for specific motion interference. We identify the robot observable sensory data and model the states of the robot. Our algorithm is motivated and implemented on an omnidirectional mobile service robot equipped with a depth-camera. Our experiments show that our algorithm can detect over 90% of motion interference events while avoiding false positive detections.

In this video we briefly illustrate the progress and contributions made with our mobile, indoor, service robots CoBots (Collaborative Robots), since their creation in 2009. Many researchers, present authors included, aim for autonomous mobile robots that robustly perform service tasks for humans in our indoor environments. The efforts towards this goal have been numerous and successful, and we build upon them. However, there are clearly many research challenges remaining until we can experience intelligent mobile robots that are fully functional and capable in our human environments.

RoboCup is an international initiative to foster inter-disciplinary research and education in robotics, artificial intelligence, computer science, and engineering. We focus on the challenges of multi-robot systems, where robots cooperate with each other and when needed with humans to achieve goals in complex and uncertain environments, such as robot soccer, as RoboCupSoccer, robot rescue, as RoboCupRescue, and the wide spectrum of robot applications in daily life, as RoboCup@Home. We also include sponsored demonstrations that explore possible new scientific challenges, such as collaborative logistics. Furthermore, we are committed to contribute to the education of children in robotics: RoboCupJunior provides an exciting introduction to science and engineering for children. Overall, RoboCup is a large vibrant community, composed of university faculty and student researchers and engineers, school teachers, children, and parents. RoboCup serves as a substrate to a wide variety of academic entreprises, ranging from courses and class projects to undergraduate, Masters, and PhD research theses. RoboCup has an international annual event consisting of robot competitions and a symposium. RoboCup has consistently grown, from a few hundred participants in 1997 to close to 3,000 in 2011.

Probabilistic planning captures the uncertainty of plan execution by probabilistically modeling the effects of actions in the environment, and therefore the probability of reaching different states from a given state and action. In order to compute a solution for a probabilistic planning problem, planners need to manage the uncertainty associated with the different paths from the initial state to a goal state. Several approaches to manage uncertainty were proposed, e.g., consider all paths at once, perform determinization of actions, and sampling. In this paper, we introduce trajectory-based short-sighted Stochastic Shortest Path Problems (SSPs), a novel approach to manage uncertainty for probabilistic planning problems in which states reachable with low probability are substituted by artificial goals that heuristically estimate their cost to reach a goal state. We also extend the theoretical results of Short-Sighted Probabilistic Planner (SSiPP) [ref] by proving that SSiPP always finishes and is asymptotically optimal under sufficient conditions on the structure of short-sighted SSPs. We empirically compare SSiPP using trajectory-based short-sighted SSPs with the winners of the previous probabilistic planning competitions and other state-of-the-art planners in the triangle tireworld problems. Trajectory-based SSiPP outperforms all the competitors and is the only planner able to scale up to problem number 60, a problem in which the optimal solution contains approximately $10^{70}$ states.

AI agents including robots often use reward functions to evaluate tradeoffs between different states and actions and to determine optimal policies. We are particularly interested in reward functions that can be decomposed into an additive sum of subrewards that are computed on independent subproblems or features of the state space. If these subrewards capture different reward metrics, such as user satisfaction and task completion time, it is unclear how to scale the subrewards in the reward function to produce an appropriate policy. In this work, we propose and evaluate a novel Monte Carlo method for learning the scaling factors of subrewards, in which the training elicits humans' preferences between two state-action scenarios. Because the algorithm elicits preferences over explicit scenarios, it is less susceptible to human error than previous elicitation approaches. The preferences are used to generate a set of inequalities over the scaling factors that we solve efficiently using a linear program. We show that our algorithm asks for a number of preferences proportional to log of the number of scaling factor hypotheses used in the Monte Carlo method.

We formalize the representation of gestures and present a model that is capable of synchronizing expressive and relevant gestures with text-to-speech input. A gesture consists of gesture primitives that are executed simultaneously. We formally define the gesture primitive and introduce the concept of a spatially targeted gesture primitive, i.e., a gesture primitive that is directed at a target of interest. The spatially targeted gesture primitive is useful for situations where the direction of the gesture is important for meaningful human-robot interaction. We contribute an algorithm to determine how a spatially targeted gesture primitive is generated. We also contribute a process to analyze the input text, determine relevant gesture primitives from the input text, compose gestures from gesture primitives and rank the combinations of gestures. We propose a set of criteria that weights and ranks the combinations of gestures. Although we illustrate the utility of our model, algorithm and process using a NAO humanoid robot, our contributions are applicable to other robots.

Successful approaches to the robot localization problem include Monte Carlo particle filters, which estimate non-parametric localization belief distributions. However, particle filters fare poorly at determining the robot's position without a good initial hypothesis. This problem has been addressed for robots that sense visual landmarks with sensor resetting, by performing sensor-based resampling when the robot is lost. For robots that make sparse, ambiguous and noisy observations, standard sensor resetting places new location hypotheses across a wide region, in positions that may be inconsistent with previous observations. We propose Multi-Observation Sensor Resetting, where observations from multiple frames are merged to generate new hypotheses more effectively. We demonstrate experimentally in the robot soccer domain on the NAO humanoid robots that Multi-Observation Sensor Resetting converges more efficiently to the robot's true position than standard sensor resetting, and is more robust to systematic vision errors.

One proposed approach to managing a large complex Smart Grid is through Broker Agents who buy electrical power from distributed producers, and also sell power to consumers, via a Tariff Market--a new market mechanism where Broker Agents publish concurrent bid and ask prices. A key challenge is the specification of the market strategy that the Broker Agents should use in order to earn profits while maintaining the market's balance of supply and demand. Interestingly, previous work has shown that a Broker Agent can learn its strategy, using Markov Decision Processes (MDPs) and Q-learning, and outperform other Broker Agents that use predetermined or randomized strategies. In this work, we investigate the more representative scenario in which multiple Broker Agents, instead of a single one, are independently learning their strategies. Using a simulation environment based on real data, we find that Broker Agents who employ periodic increases in exploration achieve higher rewards. We also find that varying levels of market dominance in customer allocation models result in remarkably distinct outcomes in market prices and aggregate Broker Agent rewards. The latter set of results can be explained by established economic principles regarding the emergence of monopolies in market-based competition, further validating our approach.

When mobile robots perform tasks in environments with humans, it seems appropriate for the robots to rely on such humans for help instead of dedicated human oracles or supervisors. However, these humans are not always available nor always accurate. In this work, we consider human help to a robot as concretely providing observations about the robot's state to reduce state uncertainty as it executes its policy autonomously. We model the probability of receiving an observation from a human in terms of their availability and accuracy by introducing Human Observation Providers POMDPs (HOP-POMDPs). We contribute an algorithm to learn human availability and accuracy online while the robot is executing its current task policy. We demonstrate that our algorithmis effective in approximating the true availability and accuracy of humans without depending on oracles to learn, thus increasing the tractability of deploying a robot that can occasionally ask for help.

The RoboCup robot soccer Small Size League has been running since 1997 with many teams success-fully competing and very effectively playing the games. Teams of five robots, with a combined au-tonomous centralized perception and control, and distributed actuation, move at high speeds in the field space, actuating a golf ball by passing and shooting it to aim at scoring goals. Most teams run their own pre-defined team strategies, unknown to the other teams, with flexible game-state dependent assignment of robot roles and positioning. How-ever, in this fast-paced noisy real robot league, rec-ognizing the opponent team strategies and accord-ingly adapting one’s own play has proven to be a

Particle filters for mobile robot localization must balance computational requirements and accuracy of localization. Increasing the number of particles in a particle filter improves accuracy, but also increases the computational requirements. Hence, we investigate a different paradigm to better utilize particles than to increase their numbers. To this end, we introduce the Corrective Gradient Refinement (CGR) algorithm that uses the state space gradients of the observation model to improve accuracy while maintaining low computational requirements. We develop an observation model for mobile robot localization using point cloud sensors (LIDAR and depth cameras) with vector maps. This observation model is then used to analytically compute the state space gradients necessary for CGR. We show experimentally that the resulting complete localization algorithm is more accurate than the Sampling/Importance Resampling Monte Carlo Localization algorithm, while requiring fewer particles.

The performance of a heterogeneous team depends critically on the composition of its members, and switching out one member for another can make a drastic difference. The capabilities of an agent depends not only on its individual characteristics, but also the interactions with its teammates. Roles are typically assigned to individual agents in such a team, where each role is responsible for a certain aspect of the joint team goal. In this paper, we focus on role assignment in a heterogeneous team, where an agent's capability depends on its teammate and their mutual state, i.e., the agent's state and its teammate's state. The capabilities of an agent are represented by a mean and variance, to capture the uncertainty in the agent's actions and in the world. We present a formal framework for representing this problem, and illustrate our framework using a robot soccer example. We formally describe how to compute the value of a role assignment policy, as well as the computation of the optimal role assignment policy, using a notion of risk. Further, we show that finding the optimal role assignment can be difficult, and describe approximation algorithms that can be used to solve this problem. We provide an analysis of these algorithms in our model and empirically show that they perform well in general problems of this domain, compared to market-based techniques. Lastly, we describe an extension to our proposed model that captures mutual interactions between more than two agents.

In this paper, we present our RS-SLAM algorithm for monocular camera where the proposal distribution is derived from the 5-point RANSAC algorithm and image feature measurement uncertainties instead of using the easily violated constant velocity model. We propose to do another RANSAC sampling within all the inliers that have the best RANSAC score to check for inlier misclassifications in the original correspondences and use all the hypotheses generated from these consensus sets in the proposal distribution. This is to mitigate data association errors (inlier misclassifications) caused by the observation that the consensus set from RANSAC that yields the highest score might not, in practice, contain all the true inliers due to noise on the feature measurements. Hypotheses which are less probable will eventually be eliminated in the particle filter resampling process. We also show in this paper that our monocular approach can be easily extended for stereo camera. Experimental results validate the potential of our approach.

The ability to obtain accurate observations while navigating in uncertain environments is a difficult challenge in deploying robots. Robots have relied heavily on human supervisors who are always available to provide additional observations to reduce uncertainty. We are instead interested in taking advantage of humans who are already in the environment to receive observations. The challenge is in modeling these humans' availability and higher costs of interruption to determine when to query them during navigation. In this work, we introduce a Human Observation Provider POMDP framework (HOP-POMDP), and contribute new algorithms for planning and executing with HOP-POMDPs that account for the differences between humans and other probabilistic sensors that provide observations. We compare optimal HOP-POMDP policies that plan for needing humans' observations with oracle POMDP policies that do not take human costs and availability into account. We show in benchmark tests and real-world environments that the oracle policies match the optimal HOP-POMDP policy 60% of the time, and can be used in cases when humans are likely to be available on the shortest paths. However, the HOP-POMDP policies receive higher rewards in general as they take into account the possibility that a human may be unavailable. HOP-POMDP policies only need to be computed once prior to the deployment of the robot, so it is feasible to precompute and use in practice.

Rapidly-exploring random trees (RRTs) are data structures and search algorithms designed to be used in continuous path planning problems. They are one of the most successful state-of-the-art techniques as they offer a great degree of flexibility and reliability. However, their use in other search domains has not been thoroughly analyzed. In this work we propose the use of RRTs as a search algorithm for automated planning. We analyze the advantages that this approach has over previously used search algorithms and the challenges of adapting RRTs for implicit and discrete search spaces.

Developing a robust, flexible, closed-loop walking algorithm for a humanoid robot is a challenging task due to the complex dynamics of the general biped walk. Common analytical approaches to biped walk use simplified models of the physical reality. Such approaches are partially successful as they lead to failures of the robot walk in terms of unavoidable falls. Instead of further refining the analytical models, in this work we investigate the use of human corrective demonstrations, as we realize that a human can visually detect when the robot may be falling. We contribute a two-phase biped walk learning approach, which we experiment on the Aldebaran NAO humanoid robot. In the first phase, the robot walks following an analytical simplified walk algorithm, which is used as a black box, and we identify and save a walk cycle as joint motion commands. We then show how the robot can repeatedly and successfully play back the recorded motion cycle, even if in open-loop. In the second phase, we create a closed-loop walk by modifying the recorded walk cycle to respond to sensory data. The algorithm learns joint movement corrections to the open-loop walk based on the corrective feedback provided by a human, and on the sensory data, while walking autonomously. In our experimental results, we show that the learned closed-loop walking policy outperforms a hand-tuned closed-loop policy and the open-loop playback walk, in terms of the distance traveled by the robot without falling.

Building upon previous work that demonstrates the effectiveness of WiFi localization information per se, in this paper we contribute a mobile robot that autonomously navigates in indoor environments using WiFi sensory data. We model the world as a WiFi signature map with geometric constraints and introduce a continuous perceptual model of the environment generated from the discrete graph-based WiFi signal strength sampling. We contribute our WiFi localization algorithm which continuously uses the perceptual model to update the robot location in conjunction with its odometry data. We then briefly introduce a navigation approach that robustly uses the WiFi location estimates. We present the results of our exhaustive tests of the WiFi localization independently and in conjunction with the navigation of our custom-built mobile robot in extensive long autonomous runs.

The LANdroids project requires robots to autonomously localize, track, and follow (a task also known as tethering) other robots or humans in an unknown environment with limited sensing abilities. In this paper, we present a localization and tethering approach that relies solely on wireless signal strength and robot odometry without requiring any known reference points in the domain. We introduce a data-driven, probabilistic model that maps received signal strength (RSS) values to real-world distance distributions and embed this model in a grid-based localization algorithm that successfully performs the LANdroids tethering task. We furthermore show, that it is possible to improve localization through the addition of a compass sensor and inter-robot information sharing.

This work builds upon the fact that robots can observe humans interacting with the objects in their environment, and that humans provide numerous non-visual cues to the identity of objects. In previous work, we outlined a Multiple-Cue Object Recognition (MCOR) algorithm which attempted to use multiple features of any type to produce more robust object recognition. All results so far reported with MCOR have been on data collected by ourselves. In this work, we introduce new advancements in the MCOR algorithm to increase its effectiveness and ability to deal with complex real data from outside datasets. These advancements include the integration of Scale-Invariant Feature Transform (SIFT) features and an improvement in training. To demonstrate the effectiveness of the MCOR framework, we first show a comparison of the MCOR algorithm to an outside dataset to show its basic advantages. We then demonstrate the advanced MCOR features on real television video datasets in particular cooking.

Hybrid sensor networks consisting of both in-expensive static wireless sensors and highly capable mobile robots have the potential to monitor large environments at a low cost. To do so, an algorithm is needed to assign tasks to mobile robots which minimizes communication among the static sensors in order to extend the lifetime of the network. We present three algorithms to solve this task allocation problem: a centralized algorithm, an auction-based algorithm, and a novel distributed algorithm utilizing a spanning tree over the static sensors to assign tasks. We compare the assignment quality and communication costs of these algorithms experimentally. Our experiments show that at a small cost in assignment quality, the distributed tree-based algorithm significantly extends the lifetime of the static sensor network.

Majority of the existing approaches to service composition, including the widely popular planning based techniques, are not able to automatically compose practical workflows that include complex repetitive behaviors (loops), taking into account possibility of failures and non-determinism of web service execution results. In this work, we present a learning based approach for composing task specific workflows. We present an approach for learning task specific web service compositions from a very small number of observations (one or more) of example service execution sequences (traces) that solve a given goal. The workflows learned by this approach generalize to the tasks justified by the observed execution trace. The generalization captures the repetitive executions of service sequences, conditional branching executions, and repetitions and branching resulting from failures. We evaluate the approach on a complex web services application involving arbitrary number of repetitive executions and failed executions.

Traditional approaches to programming robots are generally inaccessible to non-robotics-experts. A promising exception is the learning from demonstration paradigm. Here a policy mapping world observations to action selection is learned, by generalizing from task demonstrations by a teacher. Most learning from demonstration work to date considers data from a single teacher. In this paper, we consider the incorporation of demonstrations from multiple teachers. In particular, we contribute an algorithm that handles multiple data sources, and additionally reasons about reliability differences between them. For example, multiple teachers could be inequally proficient at performing the demonstrated task. We introduce Demonstration Weight Learning (DWL) as a learning from demonstration algorithm that explicitly represents multiple data sources and learns to select between them, based on their observed reliability and according to an adaptive expert learning inspired approach. We present a first implementation of DWL within a simulated robot domain. Data sources are shown to differ in reliability, and weighting is found impact task execution success. Furthermore, DWL is shown to produce appropriate data source weights that improve policy performance.

There is a subset of objects for which interaction can provide numerous cues to those objects' identity. Robots are often in situations where they can take advantage being able to observe humans interacting with the objects. In this paper, we define this subset of 'interactionable' objects for which we use our multiple-cue object recognition algorithm (MCOR) to take advantage of using multiple cues. We present two main contributions: 1) the introduction of cue-driven equivalence class discrimination, and 2) the integration of this technique, the general MCOR algorithm, and a hierarchical activity recognition algorithm also presented in this paper, demonstrated on data taken from a static Sony QRIO robot observing a human interacting with objects. The hierarchical activity recognition provides an important cue for the object recognition.

Asking questions is an inevitable part of collaborative interactions between humans and robots. However, robotics novices may have difficulty answering the robots' questions if they do not understand what the robot is asking. We are particularly interested in whether robots can supplement their questions with information about their state in a manner that increases the accuracy of human responses. In this work, we design and carefully analyze a human-robot collaborative task experiment to measure humans' responses and accuracies to different amounts of supplemental information. We vary the content of the questions along four dimensions of the robot state, namely uncertainty, context, predictions, and feature selection. Based on our results, we contribute guidelines on the effective combination of the four dimensions, under the assumption that the robot has no limitations on generating question context. Finally, we validate our guidelines against educated recommendations from the HRI community.

Abstract Controlling rigid body dynamic simulations can pose a difficult challenge when constraints exist on the bodies' goal states and the sequence of intermediate states in the resulting animation. Manually adjusting individual rigid body control actions (forces and torques) can become a very labour‐intensive and non‐trivial task, especially if the domain includes a large number of bodies or if it requires complicated chains of inter‐body collisions to achieve the desired goal state. Furthermore, there are some interactive applications that rely on rigid body models where no control guidance by a human animator can be offered at runtime, such as video games. In this work, we present techniques to automatically generate intelligent control actions for rigid body simulations. We introduce sampling‐based motion planning methods that allow us to model goal‐driven behaviour through the use of non‐deterministic Tactics that consist of intelligent, sampling‐based control‐blocks, called Skills. We introduce and compare two variations of a Tactics‐driven planning algorithm, namely behavioural Kinodynamic Rapidly Exploring Random Trees (BK‐RRT) and Behavioural Kinodynamic Balanced Growth Trees (BK‐BGT). We show how our planner can be applied to automatically compute the control sequences for challenging physics‐based domains and that is scalable to solve control problems involving several hundred interacting bodies, each carrying unique goal constraints.

We present Confidence-Based Autonomy (CBA), an interactive algorithm for policy learning from demonstration. The CBA algorithm consists of two components which take advantage of the complimentary abilities of humans and computer agents. The first component, Confident Execution, enables the agent to identify states in which demonstration is required, to request a demonstration from the human teacher and to learn a policy based on the acquired data. The algorithm selects demonstrations based on a measure of action selection confidence, and our results show that using Confident Execution the agent requires fewer demonstrations to learn the policy than when demonstrations are selected by a human teacher. The second algorithmic component, Corrective Demonstration, enables the teacher to correct any mistakes made by the agent through additional demonstrations in order to improve the policy and future task performance. CBA and its individual components are compared and evaluated in a complex simulated driving domain. The complete CBA algorithm results in the best overall learning performance, successfully reproducing the behavior of the teacher while balancing the tradeoff between number of demonstrations and number of incorrect actions during learning.

Effective learning from demonstration techniques enable complex robot behaviors to be taught from a small number of demonstrations. A number of recent works have explored interactive approaches to demonstration, in which both the robot and the teacher are able to select training examples. In this paper, we focus on a demonstration selection algorithm used by the robot to identify informative states for demonstration. Existing automated approaches for demonstration selection typically rely on a single threshold value, which is applied to a measure of action confidence. We highlight the limitations of using a single fixed threshold for a specific subset of algorithms, and contribute a method for automatically setting multiple confidence thresholds designed to target domain states with the greatest uncertainty. We present a comparison of our multi-threshold selection method to confidence-based selection using a single fixed threshold, and to manual data selection by a human teacher. Our results indicate that the automated multi-threshold approach significantly reduces the number of demonstrations required to learn the task.

We propose a new approximate algorithm, LA- JIV (lookahead J-MDP information value), to solve oracular partially observable Markov decision problems (OPOMDPs), a special type of POMDP that rather than standard observations includes an "oracle" that can be consulted for full state information at a fixed cost. We previously introduced JIV (J-MDP information value) to solve OPOMDPs, an heuristic algorithm that utilizes the solution of the underlying MDP and weighs the value of consulting the oracle against the value of taking a state-modifying action. While efficient, JIV will rarely find the optimal solution. In this paper, we extend JIV to include lookahead, thereby permitting arbitrarily small deviation from the optimal policy's long-term expected reward at the cost of added computation time. The depth of the lookahead is a parameter that governs this tradeoff; by iteratively increasing this depth, we provide an anytime algorithm that yields an ever- improving solution. LA-JIV leverages the OPOMDP framework's unique characteristics to outperform general-purpose approximate POMDP solvers; in fact, we prove that LA-JIV is a poly-time approximation scheme (PTAS) with respect to the size of the state and observation spaces, thereby showing rigorously that OPOMDPs are "easier" than POMDPs. Finally, we substantiate our theoretical results via an empirical analysis of a benchmark OPOMDP instance.

After several years of developing multiple RoboCup small-size robot soccer teams, our CMDragons robot team achieved a highly successful level of performance, winning both the 2006 and 2007 competitions without losing a single game. Our small-size team consists of five executing wheeled robots with centralized, off-board perception and decision making. The decision making framework consists of a set of layered components, consisting of perception, evaluation and strategy, robot tactics and skills, and real-time navigation. In this paper, we present the strategy, action selection, and execution aspects of our architecture, with a focus on passing as an example of effective coordinated teamwork. The design enabled our robot team to score using multiple methods, from direct shooting up to 3D passes deflected in midair, resulting in a rich set of actions that were difficult for adversaries to counter. We provide several performance quantified claims supported by testing in our laboratory and in competition settings.

Learning parameters of a motion model is an important challenge for autonomous robots. We address the particular instance of parameter learning when tracking motions with a switching state-space model. We present a general algorithm for dealing simultaneously with both unknown fixed model parameters and state variables. Using an Expectation-Maximization approach, we apply a tactic-based multi-model particle filter to estimate the state variables in the E-step, and use particle smoothing to update the parameters in the M-step. We test our algorithm both in simulation and in a team robot soccer environment, as a substrate for applying the learned models to object tracking in a team. One of the soccer robots learns the actuation model of its teammate. The experimental results show that the particle smoothing efficiency is substantially increased and the tracking performance is significantly improved using the learned teammate actuation model.

As robots become more commonplace within society, the need for tools to enable non-robotics-experts to develop control algorithms, or policies, will increase. Learning from demonstration (LfD) offers one promising approach, where the robot learns a policy from teacher task executions. Our interests lie with robot motion control policies which map world observations to continuous low-level actions. In this work, we introduce advice-operator policy improvement (A-OPI) as a novel approach for improving policies within LfD. Two distinguishing characteristics of the A-OPI algorithm are data source and continuous state-action space. Within LfD, more example data can improve a policy. In A-OPI, new data is synthesized from a student execution and teacher advice. By contrast, typical demonstration approaches provide the learner with exclusively teacher executions. A-OPI is effective within continuous state-action spaces because high level human advice is translated into continuous-valued corrections on the student execution. This work presents a first implementation of the A-OPI algorithm, validated on a Segway RMP robot performing a spatial positioning task. A-OPI is found to improve task performance, both in success and accuracy. Furthermore, performance is shown to be similar or superior to the typical exclusively teacher demonstrations approach.

In their interactions with the world robots inevitably face equivalent action choices, situations in which multiple actions are equivalently applicable. In this paper, we address the problem of equivalent action choices in learning from demonstration, a robot learning approach in which a policy is acquired from human demonstrations of the desired behavior. We note that when faced with a choice of equivalent actions, a human teacher often demonstrates an action arbitrarily and does not make the choice consistently over time. The resulting inconsistently labeled training data poses a problem for classification-based demonstration learning algorithms by violating the common assumption that for any world state there exists a single best action. This problem has been overlooked by previous approaches for demonstration learning. In this paper, we present an algorithm that identifies regions of the state space with conflicting demonstrations and enables the choice between multiple actions to be represented explicitly within the robotpsilas policy. An experimental evaluation of the algorithm in a real-world obstacle avoidance domain shows that reasoning about action choices significantly improves the robotpsilas learning performance.

In this paper, we present a new method that uses random search for online planning of biped walking, given a feasible footstep plan. The Linear Inverted Pendulum dynamic model and the Zero Moment Point concept are employed to solve the walking problem. We consider walk planning as the choice of a sequence of ZMPs leading to a stable walk that satisfies all the dynamic and mechanical constraints of the robot. We contribute a novel online sampling algorithm to efficiently search for such ZMP sequence. We demonstrate the effectiveness of the algorithm by successful combined walking tasks in a faithful simulation of a full-body humanoid robot.

Autonomous robots operating in human environments will need to automatically learn to perform new tasks without requiring the implementation of task-specific actions or time-consuming deliberative planning at run-time. In this work, we contribute a demonstration-based approach for teaching a robot task-specific planners involving complex sequential tasks with repetitions. Complexity of tasks results from step repetitions, execution failures and conditionally executing plans. Our demonstration approach uses sound and visually interpretable cues to guide and indicate the various actions and objects to a robot. The robot in turn performs the actions and generalizes its execution into a task-specific planner. We demonstrate the successful plan learning for two different tasks implemented in real-world settings.

Learning by demonstration can be a powerful and natural tool for developing robot control policies. That is, instead of tedious hand-coding, a robot may learn a control policy by interacting with a teacher. In this work we present an algorithm for learning by demonstration in which the teacher operates in two phases. The teacher first demonstrates the task to the learner. The teacher next critiques learner performance of the task. This critique is used by the learner to update its control policy. In our implementation we utilize a 1-Nearest Neighbor technique which incorporates both training dataset and teacher critique. Since the teacher critiques performance only, they do not need to guess at an effective critique for the underlying algorithm. We argue that this method is particularly well-suited to human teachers, who are generally better at assigning credit to performances than to algorithms. We have applied this algorithm to the simulated task of a robot intercepting a ball. Our results demonstrate improved performance with teacher critiquing, where performance is measured by both execution success and efficiency.

Effective human/robot interfaces which mimic how humans interact with one another could ultimately lead to robots being accepted in a wider domain of applications. We present a framework for interactive task training of a mobile robot where the robot learns how to do various tasks while observing a human. In addition to observation, the robot listens to the human's speech and interprets the speech as behaviors that are required to be executed. This is especially important where individual steps of a given task may have contingencies that have to be dealt with depending on the situation. Finally, the context of the location where the task takes place and the people present factor heavily into the robot's interpretation of how to execute the task. In this paper, we describe the task training framework, describe how environmental context and communicative dialog with the human help the robot learn the task, and illustrate the utility of this approach with several experimental case studies.

Hierarchical state machines have proven to be a powerful tool for controlling autonomous robots due to their flexibility and modularity. For most real robot implementations, however, it is often the case that the control hierarchy is hand-coded. As a result, the development process is often time intensive and error prone. In this paper, we explore the use of an experts learning approach, based on Auer and colleagues' Exp3 (1995), to help overcome some of these limitations. In particular, we develop a modified learning algorithm, which we call rExp3, that exploits the structure provided by a control hierarchy by treating each state machine as an 'expert'. Our experiments validate the performance of rExp3 on a real robot performing a task, and demonstrate that rExp3 is able to quickly learn to select the best state machine expert to execute. Through our investigations in these environments, we identify a need for faster learning recovery when the relative performances of experts reorder, such as in response to a discrete environment change. We introduce a modified learning rule to improve the recovery rate in these situations and demonstrate through simulation experiments that rExp3 performs as well or better than Exp3 under such conditions.

We introduce the oracular partially observable Markov decision process (OPOMDP), a type of POMDP in which the world produces no observations; instead there is an "oracle," available in any state, that tells the agent its exact state for a fixed cost. The oracle may be a human or a highly accurate sensor. At each timestep the agent must choose whether to take a domain-level action or consult the oracle. This formulation comprises a factorization between information-gathering actions and domain-level actions, allowing us to characterize the value of information and to examine the problem of planning under uncertainty from a novel perspective. We propose an algorithm to capitalize on this factorization and the special structure of the OPOMDP, and we test the algorithm's performance on a new sample domain. On this new domain, we are able to solve a problem with hundreds of thousands of action-states and vastly outperform a previous state-of-the-art approximate technique

Reliable recognition of objects is an important capability in order to have agents accomplish and assist in a variety of useful tasks such as search and rescue or office assistance. Numerous approaches attempt to recognize objects based on visual cues alone. However, the same type of object can have very different visual appearances, such as shape, size, pose, color. Although such approaches are widely studied with relative success, the general task of object recognition still remains difficult. In previous work, we introduced MCOR (multiple-cue object recognition), a flexible object recognition approach which can use any multiple cues, whether they are visual cues intrinsic to the object or provided by observation of a human. As part of the framework, weights were provided to reflect the variation in the strength of the association between a particular cue and an object. In this paper, we demonstrate how the probabilistic relational framework used to determine the weights can be used in complex scenarios with numerous objects, cues, and the relationship between them. We develop a simulator that can generate these complex scenarios using cues based on real recognition systems.

Temporal classification, such as activity recognition, is a key component for creating intelligent robot systems. In the case of robots, classification algorithms must robustly incorporate complex, non-independent features extracted from streams of sensor data. Conditional random fields are discriminatively trained temporal models that can easily incorporate such features. However, robots have few computational resources to spare for computing a large number of features from high bandwidth sensor data, which creates opportunities for feature selection. Creating models that contain only the most relevant features reduces the computational burden of temporal classification. In this paper, we show that lscr1regularization is an effective technique for feature selection in conditional random fields. We present results from a multi-robot tag domain with data from both real and simulated robots that compare the classification accuracy of models trained with lscr1regularization, which simultaneously smoothes the model and selects features; lscr2regularization, which smoothes to avoid over-fitting, but performs no feature selection; and models trained with no smoothing.

In this paper, we focus on human-robot interaction in a team task where we identify the need for peer-to-peer (P2P) teamwork, with no fixed hierarchy for decision making between robots and humans. Instead, all team members are equal participants and decision making is truly distributed. We have fully developed a P2P team within Segway Soccer, a research domain, built upon Robocup robot soccer, that we have introduced to explore the challenge of P2P coordination in human-robot teams with dynamic, adversarial tasks. We recently participated in the first Segway Soccer games between two competing teams at the 2005 RoboCup US Open. We believe these games are the first ever between two human-robot P2P teams. Based on the competition, we realized two different approaches to P2P teams. We present our robot-centric approach to P2P team coordination and contrast it to the human-centric approach of the opponent team.

Autonomous robots use sensors to perceive and track objects in the world. Tracking algorithms use object motion models to estimate the position of a moving object. Tracking efficiency completely depends on the accuracy of the motion model and of the sensory information. Interestingly, when the robots can actuate the object being tracked, the motion can become highly discontinuous and nonlinear. We have previously developed a successful tracking approach that effectively switches among object motion models as a function of the robot's actions. If the object to be tracked is actuated by a team, the set of motion models is quite more complex. In this paper, we report on a tracking approach that can use a dynamic multiple motion model based on a team coordination plan. We present the multi-model probabilistic tracking algorithms in detail and present empirical results both in simulation and real robot test. Our physical team is composed of a robot and a human in a real Segway soccer game scenario. We show how the coordinated plan allows the robot to better track a mobile object through the effective interaction with its human teammate.

The essence of the signal-to-symbol problem consists of associating a symbolic description of an object (e.g., a chair) to a signal (e.g., an image) that captures the real object. Robots that interact with humans in natural environments must be able to solve this problem correctly and robustly. However, the problem of providing complete object models a priori to a robot so that it can understand its environment from any viewpoint is extremely difficult to solve. Additionally, many objects have different uses which in turn can cause ambiguities when a robot attempts to reason about the activities of a human and their interactions with those objects. In this paper, we build upon the fact that robots that co-exist with humans should have the ability of observing humans using the different objects and learn the corresponding object definitions. We contribute an object recognition algorithm, FOCUS, that is robust to the variations of signals, combines structure and function of an object, and generalizes to multiple similar objects. FOCUS, which stands for Finding Object Classification through Use and Structure, combines an activity recognizer capable of capturing how an object is used with a traditional visual structure processor. FOCUS learns structural properties (visual features) of objects by knowing first the object's affordance properties and observing humans interacting with that object with known activities. The strength of the method relies on the fact that we can define multiple aspects of an object model, i.e., structure and use, that are individually robust but insufficient to define the object, but can do when combined.

Meetings are an integral part of business life for any organization. In previous work, we have developed a physical awareness system called CAMEO (camera assisted meeting event observer) to record and process the audio/visual information of a meeting. An important task in meeting understanding is to know who and how many people are attending the meeting. In this paper, we present an automatic approach to detect, track, and cluster people's faces in long video sequences. This is a challenging problem due to the appearance variability of people's faces (illumination, expression, pose,...). Two main novelties are presented: a robust real-time adaptive subspace face tracker which combines color and appearance. A temporal subspace clustering algorithm. The effectiveness and robustness of the proposed system is demonstrated over a data set of long videos (i.e. 1 hour).

This paper describes an approach that performs visual object detection in real-time by combining the strength of processing the color segmented image along with that of the grayscale image of the same scene. This approach was developed with the annual RoboCup Competition in mind, specifically the 4-Legged League where teams of Sony AIBO robots compete in the game of soccer. The images used for processing were taken from the camera located in the head of the robots, and the objects of interest to be detected were the actual AIBO robots. We use color segmented images for producing initial hypotheses for the location of robots in the image, and grayscale images for final classification purposes. Using both representations to process a scene allows each to make up for the deficiencies of the other, and provides a good balance between fast processing time and high detection accuracy. We present our algorithms and show illustrative examples of their performance

Robots need to track object. Object tracking efficiency completely depends on the accuracy of the motion model and of the sensory information. Interestingly, when multiple team members can actuate the object being tracked, the motion can become highly discontinuous and nonlinear. We have previously developed a successful tracking approach that switches among target motion models as a function of one robot's actions. In this paper, we report on a tracking approach that can use a dynamic multiple motion model based on a team coordination plan. We present the multi-model probabilistic tracking algorithms in detail and present empirical results both in simulation and in a human-robot Segway soccer team. The team coordination plan allows the robot to much more effectively track mobile targets

As we progress towards a world where robots play an integral role in society, a critical problem that remains to be solved is the pickup team challenge; that is, dynamically formed heterogeneous robot teams executing coordinated tasks where little information is known a priori about the tasks, the robots, and the environments in which they would operate. Successful solutions to forming pickup teams would enable researchers to experiment with larger numbers of robots and enable industry to efficiently and cost-effectively integrate new robot technology with existing legacy teams. In this paper, we define the challenge of pickup teams and propose the treasure hunt domain for evaluating the performance of pickup teams. Additionally, we describe a basic implementation of a pickup team that can search and discover treasure in a previously unknown environment. We build on prior approaches in market-based task allocation and plays for synchronized task execution, to allocate roles amongst robots in the pickup team, and to execute synchronized team actions to accomplish the treasure hunt task

Interactions are frequently seen between the robot and the targets being tracked within the robotics community. Modeling the interactions using knowledge of robot cognition improves the performance of the tracker. Communication improves the performance of a multi-agent system. The focus of this paper is to present our solution to integrate the communication information into our team-driven multi-model motion tracking. We present the probabilistic tracking algorithm in detail and present empirical results both in simulation and in a Segway soccer team. The information from team communication allows the robot to much more effectively track mobile targets

This paper introduces a refinement of the classical sense-plan-act objective maximization method for setting agent goals, a real-time randomized path planner, a bounded acceleration motion control system, and a randomized velocity-space search for collision avoidance of multiple moving robotic agents. We have found this approach to work well for dynamic and unpredictable domains requiring real-time response and flexible coordination of multiple agents. First, the approach employs randomized search for objective maximization and motion planning, allowing real-time or any-time performance. Next, a novel cooperative safety algorithm is employed which respects agent dynamics limitations while also preventing collisions with static obstacles or other participating agents. An implementation of our multilayer approach has been tested and validated on real robots, forming the basis for an autonomous robotic soccer team

We present an improved state-based prediction algorithm for time series. Given time series produced by a process composed of different underlying states, the algorithm predicts future time series values based on past time series values for each state. Unlike many algorithms, this algorithm predicts a multi-modal distribution over future values. This prediction forms the basis for labelling part of a time series with the underlying state that created it given some labelled example signals. The algorithm is robust to a wide variety of possible types of changes in signals including changes in mean, amplitude, amount of noise, and period. We show results demonstrating that the algorithm successfully segments signals from several robotic sensors generated while performing a variety of simple tasks.

Meetings are a very important part of everyday life for professionals working in universities, companies or governmental institutions. We have designed a physical awareness system called CAMEO (Camera Assisted Meeting Event Observer), a hardware/software system to record and monitor people's activities in meetings. CAMEO captures a high resolution omnidirectional view of the meeting by stitching images coming from almost concentric cameras. Besides recording capability, CAMEO automatically detects people and learns a person-specific facial appearance model (PS-FAM) for each of the participants. The PSFAMs allow more robust/reliable tracking and identification. In this paper, we describe the video-capturing device, photometric/geometric autocalibration process, and the multiple people tracking system. The effectiveness and robustness of the proposed system is demonstrated over several real-time experiments and a large data set of videos.

With the wide availability, high information content, and suitability for human environments of low-cost color cameras, machine vision is an appealing sensor for many robot platforms. For researchers interested in autonomous robot teams operating in highly dynamic environments performing complex tasks, such as robot soccer, fast color-based object recognition is very desirable. Indeed, there are a number of existing algorithms that have been developed within the community to achieve this goal. Many of these algorithms, however, do not adapt for variation in lighting intensity, thereby limiting their use to statically and uniformly lit indoor environments. In this paper, we present a new technique for color object recognition that can adapt to changes in illumination but remains computationally efficient. We present empirical results demonstrating the performance of our technique for both indoor and outdoor environments on a robot platform performing tasks drawn from the robot soccer domain. Additionally, we compare the computational speed of our new approach against CMVision, a fast open-source color segmentation library. Our performance results show that our technique is able to adapt to lighting variations without requiring significant additional CPU resources.

Fast changing, increasingly complex, and diverse computing platforms pose central problems in scientific computing: How to achieve, with reasonable effort, portable optimal performance? We present SPIRAL, which considers this problem for the performance-critical domain of linear digital signal processing (DSP) transforms. For a specified transform, SPIRAL automatically generates high-performance code that is tuned to the given platform. SPIRAL formulates the tuning as an optimization problem and exploits the domain-specific mathematical structure of transform algorithms to implement a feedback-driven optimizer. Similar to a human expert, for a specified transform, SPIRAL "intelligently" generates and explores algorithmic and implementation choices to find the best match to the computer's microarchitecture. The "intelligence" is provided by search and learning techniques that exploit the structure of the algorithm and implementation space to guide the exploration and optimization. SPIRAL generates high-performance code for a broad set of DSP transforms, including the discrete Fourier transform, other trigonometric transforms, filter transforms, and discrete wavelet transforms. Experimental results show that the code generated by SPIRAL competes with, and sometimes outperforms, the best available human tuned transform library code.

We present a meeting recorder infrastructure used to record and annotate events that occur in meetings. Multiple data streams are recorded and analyzed in order to infer a higher-level state of the group’s activities. We describe the hardware and software systems used to capture people’s activities as well as the methods used to characterize them.

In this paper, we make two contributions. First, we present a new domain, called Segway Soccer, for investigating the coordination of dynamically formed, mixed human-robot teams within the realm of a team task that requires real-time decision making and response. Segway Soccer is a game of soccer between two teams consisting of Segway riding humans and Segway RMP-based robots. We believe Segway Soccer is the first game involving both humans and robots in cooperative roles and with similar capabilities. In conjunction with this new domain, we present our work towards developing a soccer playing robot using the Segway RMP platform and vision as its primary sensing modality. As Segway Soccer is set in the outdoors, we have developed novel vision algorithms to adapt to changes in lighting conditions. We present the domain of Segway Soccer, its inherent challenges, and our work towards this goal.

Legged robots, such as the Sony AIBO, create opportunity to design rich motions to be executed in specific situations. In particular, teams involved in robot soccer RoboCup competitions have developed many different motions for kicking the ball. Designing effective motions and determining their effects is a challenging problem that is traditionally approached through a generate and test methodology. In this paper, we present a method we developed for learning the effects of kicking motions. Our procedure acquires models of the kicks in terms of key values that describe their effects on the ball's trajectory, namely the angle and the distance reached. The successful automated acquisition of the models of different kicks is then followed by the incorporation of these models into the behaviors to select the most promising kick in a given state of the world. Using the robot soccer domain, we demonstrate that a robot that takes into account the learned predicted effects of its actions performs significantly better than its counterpart.

Static cameras are pervasive in a variety of environments. However it remains a challenging problem to extract and reason about high-level features from real-time and continuous observation of an environment. In this paper, we present CAMEO, the Camera Assisted Meeting Event Observer, which is a physical awareness system designed for use by an agent-based electronic assistant. CAMEO is an inexpensive high-resolution omnidirectional vision system designed to be used in meeting environments. The multiple camera design achieves the desired high image resolution and lower cost that can be achieved when compared to traditional omnicameras that make use of a single camera and mirror solution.

Developing fast gaits for legged robots is a difficult task that requires optimizing parameters in a highly irregular, multidimensional space. In the past, walk optimization for quadruped robots, namely the Sony AIBO robot, was done by handtuning the parameterized gaits. In addition to requiring a lot of time and human expertise, this process produced sub-optimal results. Several recent projects have focused on using machine learning to automate the parameter search. Algorithms utilizing Powell's minimization method and policy gradient reinforcement learning have shown significant improvement over previous walk optimization results. In this paper we present a new algorithm for walk optimization based on an evolutionary approach. Unlike previous methods, our algorithm does not attempt to approximate the gradient of the multidimensional space. This makes it more robust to noise in parameter evaluations and avoids prematurely converging to local optima, a problem encountered by both of the previously suggested algorithms. Our evolutionary algorithm matches the best previous learning method, achieving several different walks of high quality. Furthermore, the best learned walks represent an impressive 20% improvement over our own best hand-tuned walks.

We extend our previous work on a classification algorithm for time series. Given time series produced by different underlying generating processes, the algorithm predicts future time series values based on past time series values for each generator. Unlike many algorithms, this algorithm predicts a distribution over future values. This prediction forms the basis for labelling part of a time series with the underlying generator that created it given some labelled exam piles. The algorithm is robust to a wide variety of possible types of changes in signals including mean shifts, amplitude changes, noise changes, period changes, and changes in signal shape. We improve upon the speed of our previous approach and show the utility of the algorithm for discriminating between different states of the robot/environment from robotic sensor signals.

We have designed a physical awareness system called CAMEO, the camera assisted meeting event observer, which consists of a multi-camera omnidirectional vision system designed to be used in meeting environments. CAMEO is designed to monitor the activities of people in meetings so that it can generate a semantically-indexed summary of what occurred in the meeting. In this paper, we describe CAMEO's fast people detection and tracking module. This module makes use of a combination of frame differencing, face detection, and adaptive color blob tracking based on mean shift analysis to detect and track people in the panoramic image. We describe this algorithm and present experimental results from captured meeting logs.

The Segway human transport (HT) is a one person dynamically self-balancing transportation vehicle. The Segway robot mobility platform (RMP) is a modification of the HT capable of being commanded by a computer for autonomous operation. With these platforms, we are investigating human/robot coordination in adversarial environments through the game, Segway soccer. The players include robots (RMPs) and humans (riding HTs). The rules of the game are a combination of soccer and ultimate Frisbee rules. In this paper, we provide two contributions. First, we examine the capabilities and limitations of the Segway and describe the mechanical systems necessary to create a robot Segway soccer player. Second, we provide a detailed analysis of several ball manipulation/kicking systems and the implementation results of the CM-RMP pneumatic ball manipulation system.

Multiagent learning is a necessary yet challenging problem as multiagent systems become more prevalent and environments become more dynamic. Much of the groundbreaking work in this area draws on notable results from game theory, in particular, the concept of Nash equilibria. Learners that directly learn an equilibrium obviously rely on their existence. Learners that instead seek to play optimally with respect to the other players also depend upon equilibria since equilibria are fixed points for learning. From another perspective, agents with limitations are real and common. These may be undesired physical limitations as well as self-imposed rational limitations, such as abstraction and approximation techniques, used to make learning tractable. This article explores the interactions of these two important concepts: equilibria and limitations in learning. We introduce the question of whether equilibria continue to exist when agents have limitations. We look at the general effects limitations can have on agent behavior, and define a natural extension of equilibria that accounts for these limitations. Using this formalization, we make three major contributions: (i) a counterexample for the general existence of equilibria with limitations, (ii) sufficient conditions on limitations that preserve their existence, (iii) three general classes of games and limitations that satisfy these conditions. We then present empirical results from a specific multiagent learning algorithm applied to a specific instance of limited agents. These results demonstrate that learning with limitations is feasible, when the conditions outlined by our theoretical analysis hold.

Adversarial multi-robot problems, where teams of robots compete with one another, require the development of approaches that span all levels of control and integrate algorithms ranging from low-level robot motion control, through to planning, opponent modeling, and multiagent learning. Small-size robot soccer, a league within the RoboCup initiative, is a prime example of this multi-robot team adversarial environment. In this paper, we describe some of the algorithms and approaches of our robot soccer team, CMDragons'02, developed for RoboCup 2002. Our team represents an integration of many components, several of which that are in themselves state-of-the-art, into a framework designed for fast adaptation and response to the changing environment.

Fast pattern detection and identification is fundamental problem for many applications of real-time vision systems. The desirable characteristics for a solution are that it requires little computation, localizes a pattern robustly and with high accuracy, and can identify a large number of unique pattern identifiers so that many of these markers can be tracked within a field a view. We will present a system that can accurately track a broad class of patterns both accurately and quickly, when used with a suitable low level vision system that can return calibrated coordinates of regions in an image. Both pattern design and the detection algorithm are considered together to find a solution meeting the above criteria. Along the way, assumptions are verified to make informed choices without relying on guesswork, and allowing similar system to be designed on a solid experimental and statistical basis.

Robots typically have many sensors, which are underutilized. This is usually because no simple mathematical models of the sensors have been developed or the sensors are too noisy to use techniques, which require simple noise models. We propose to use these underutilized sensors to determine the state of the environment in which the robot is operating. Being able to identify the state of the environment allows the robot to adapt to current operating conditions and the actions of other agents. Adapting to current operating conditions makes robot robust to changes in the environment by constantly adapting to the current conditions. This is useful for adapting to different lighting conditions or different flooring conditions amongst many other possible desirable adaptations. The strategy we propose for utilizing these sensors is to group sensor readings into statistical probability distributions and then compare the probability distributions to detect repeated states of the environment.

We contribute a fast system for avoiding unknown obstacles on a mobile robot using a simple camera as the only sensor. The vision module detects objects, both known and unknown, around the robot. Unknown objects are detected by paying attention to occlusions of a floor of known colors. Range and angle to the objects is calculated and used to create a radial model of the vicinity of the robot. This modeling component keeps tracks of objects that are currently outside the field of view of the camera allowing the robot to avoid obstacles it is not currently looking at. We show the effectiveness of the vision and modeling algorithms by creating a simple behavior which wanders around while avoiding obstacles.

In this paper, we present in detail our approach to constructing a world model in a multi-robot team. We introduce two separate world models, namely an individual world model that stores one robot's state, and a shared world model that stores the state of the team. We present procedures to effectively merge information in these two world models in real-time. We overcome the problem of high communication latency by using shared information on an as-needed basis. The success of our world model approach is validated by experimentation in the robot soccer domain. The results show that a team using a world model that incorporates shared information is more successful at tracking a dynamic object in its environment than a team that does not use shared information.

We describe an approach, called improbability filtering, to rejecting false-positive observations from degrading the tracking performance of an extended Kalman-Bucy filter. Improbability filtering removes false-positives by rejecting low likelihood observations as determined by the model estimates. It offers a computationally fast and robust method for removing this form of white noise without the need for a more advanced filter. We describe an application of the improbability filter approach to extended Kalman-Bucy filters for tracking ten robots and a ball moving at speeds approaching 5 m s/sup -1/ both accurately and reliably in real-time based on the observations of a single color camera. The environment is highly dynamic and non-linear, as exemplified by the motion of the ball which varies from free rolling under friction, to roiling up 45/spl deg/ inclined walls at the boundary, to being manipulated in unpredictable ways by a mechanical apparatus on each robot. The sensing apparatus, a camera and color blob tracking algorithms, suffers from the usual noise, latency, intermittency, as well as from false-positives caused by the misidentification of an observed object with a nonnegligible likelihood.

Mobile robots often must find a trajectory to another position in their environment, subject to constraints. This is the problem of planning a path through a continuous domain Rapidly-exploring random trees (RRTs) are a recently developed representation on which fast continuous domain path planners can be based. In this work, we build a path planning system based on RRTs that interleaves planning and execution, first evaluating it in simulation and then applying it to physical robots. Our planning algorithm, ERRT (execution extended RRT), introduces two novel extensions of previous RRT work, the waypoint cache and adaptive cost penalty search, which improve replanning efficiency and the quality of generated paths. ERRT is successfully applied to a real-time multi-robot system. Results demonstrate that ERRT is significantly more efficient for replanning than a basic RRT planner, performing competitively with or better than existing heuristic and reactive real-time path planning approaches. ERRT is a significant step forward with the potential for making path planning common on real robots, even in challenging continuous, highly dynamic domains.

This paper presents an evolutionary algorithm for searching for the optimal implementations of signal transforms and compares this approach against other search techniques. A single signal processing algorithm can be represented by a very large number of different but mathematically equivalent formulas. When these formulas are implemented in actual code, unfortunately their running times differ significantly. Signal processing algorithm optimization aims at finding the fastest formula. We present a new approach that successfully solves this problem, using an evolutionary stochastic search algorithm, STEER, to search through the very large space of formulas. We empirically compare STEER against other search methods, showing that it notably can find faster formulas while still only timing a very small portion of the search space.

Describes the issues in robotics from a viewpoint of edutainment through a series of activities in the Robot World Cup Initiative and related events, such as the International Robot Games Festival (Robofesta) supported by the Japanese government to promote creative and imaginative education programs, RoboCup Jr. which is designed for kids and the younger generation to play RoboCup games with easily constructible platforms, development of small legged robots for pets in the house or games, and education projects in system engineering. Finally, concluding remarks for future activities are given.

We present a new localization algorithm, called sensor resetting localization, which is an extension of Monte Carlo localization. The algorithm adds sensor based re-sampling to Monte Carlo localization when the robot is lost. Sensor resetting localization (SRL) is robust to modelling errors including unmodelled movements and systematic errors. It can be used in real time on systems with limited computational power. The algorithm has been successfully used on autonomous legged robots in the Sony legged league of the robotic soccer competition RoboCup'99. We present results from the real robots demonstrating the success of the algorithm and results from simulation comparing SRL to Monte Carlo localization.

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.

Recently model checking representation and search techniques were shown to be efficiently applicable to planning, in particular to non-deterministic planning. Such planning approaches use Ordered Binary Decision Diagrams (OBDDs) to encode a planning domain as a non-deterministic finite automaton and then apply fast algorithms from model checking to search for a solution. OBDDs can effectively scale and can provide universal plans for complex planning domains. We are particularly interested in addressing the complexities arising in non-deterministic, multi-agent domains. In this article, we present UMOP, a new universal OBDD-based planning framework for non-deterministic, multi-agent domains. We introduce a new planning domain description language, NADL, to specify non-deterministic, multi-agent domains. The language contributes the explicit definition of controllable agents and uncontrollable environment agents. We describe the syntax and semantics of NADL and show how to build an efficient OBDD-based representation of an NADL description. The UMOP planning system uses NADL and different OBDD-based universal planning algorithms. It includes the previously developed strong and strong cyclic planning algorithms. In addition, we introduce our new optimistic planning algorithm that relaxes optimality guarantees and generates plausible universal plans in some domains where no strong nor strong cyclic solution exists. We present empirical results applying UMOP to domains ranging from deterministic and single-agent with no environment actions to non-deterministic and multi-agent with complex environment actions. UMOP is shown to be a rich and efficient planning system.

RoboCup is an increasingly successful attempt to promote the full integration of robotics and AI research. The most prominent feature of RoboCup is that it provides the researchers with the opportunity to demonstrate their research results as a form of competition in a dynamically changing hostile environment, defined as the international standard game definition, in which the gamut of intelligent robotics research issues are naturally involved. The article describes what we have learned from the past RoboCup activities, and overview the future perspectives of RoboCup in the next century, mainly focusing on the real robot leagues. Finally, we introduce the new leagues, one of which will have been held at RoboCup-99 in Stockholm.

We have developed a multiagent robotic system including perception, cognition, and action components to function in a dynamic environment. The system involves the integration and coordination of a variety of diverse functional modules. At the sensing level, our complete multiagent robotic system incorporates detection and recognition algorithms to handle the motion of multiple mobile robots in a noisy environment. At the strategic and decision-making level, deliberative and reactive components take in the processed sensory inputs and select the appropriate actions to reach objectives under the dynamic and changing environmental conditions. At the actuator level, physical robotic effecters execute the motion commands generated by the cognition level. In this paper, we focus on presenting our approach for reactive visual control of multiple mobile robots. We present a tracking and prediction algorithm which handles visually homogeneous agents. We describe our nonholonomic control for single robot navigation, and show how it applies to dynamic path generation to avoid multiple moving obstacles. We illustrate our algorithms with examples from our real implementation. Using the approaches introduced, our robotic team won the RoboCup-97 small-size robot competition at IJCAI-97 in Nagoya, Japan.

Sony has provided a remarkable platform for research and development in robotic agents, namely fully autonomous legged robots. In this paper, we describe our work using Sony's legged robots to participate at the RoboCup'98 legged robot demonstration and competition. Robotic soccer represents a very challenging environment for research into systems with multiple robots that need to achieve concrete objectives, particularly in the presence of an adversary. Furthermore RoboCup'98 offers an excellent opportunity for robot entertainment. We introduce the RoboCup context and briefly present Sony's legged robot. We developed a vision-based navigation and a Bayesian localization algorithm. Team strategy is achieved through pre-defined behaviors and learning by instruction.

. Automated route planning consists of using real maps to automatically find good map routes. Two shortcomings to standard methods are (1) that domain information may be lacking, and (2) that a ‘good’ route can be hard to define. Most on-line map representations do not include information that may be relevant for the purpose of generating good realistic routes, such as traffic patterns, construction, and one-way streets. The notion of a good route is dependent not only on geometry (shortest path),but also on a variety of other factors, such as the day and time, weather conditions,and perhaps most importantly,user-dependent preferences. These features can be learned by evaluating real-world execution experience. These difficulties motivate our work on applying analogical reasoning to route planning. Analogical reasoning is a method of using past experience to improve problem solving performance in similar new situations.Our approach consists of the accumulation and reuse of previously traversed routes. We exploit the geometric characteristics of the map domain in the storage, retrieval, and reuse phases of the analogical reasoning process. Our route planning method retrieves and reuses multiple past routing cases that collectively form a good basis for generating a new routing plan. To find a good set of past routes, we have designed a similarity metric that takes into account the geometric and continuous-valued characteristics of a city map. The metric evaluates its own performance and uses execution experience to improve its prediction of case similarity, adaptability and executability. The planner uses a replay mechanism to produce a route plan based on analogy with past routes retrieved by the similarity metric. We use illustrative examples and show some empirical results from a detailed on-line map of the city of Pittsburgh, containing over 18,000 intersections and 25,000 street segments.

This paper describes ROGUE, an integrated planning and executing robotic agent. ROGUE is designed to be a roving office gopher unit, doing tasks such as picking up & delivering mail and returning & picking up library books, in a setup where users can post tasks for the robot to do. We have been working towards the goal of building a completely autonomous agent which can learn from its experiences and improve upon its own behaviour with time. This paper describes what we have achieved to-date: (1) a system that can generate and execute plans for multiple interacting goals which arrive asynchronously and whose task structure is not known a priori, interrupting and suspending tasks when necessary, and (2) a system which can compensate for minor problems in its domain knowledge, monitoring execution to determine when actions did not achieve expected results, and re-planning to correct failures.

There has been evidence that least-commitment planners can efficiently handle planning problems that involve difficult goal interactions. This evidence has led to the common belief that delayed-commitment is the "best" possible planning strategy. However, we recently found evidence that eager-commitment planners can handle a variety of planning problems more efficiently, in particular those with difficult operator choices. Resigned to the futility of trying to find a universally successful planning strategy, we devised a planner that can be used to study which domains and problems are best for which planning strategies. In this article we introduce this new planning algorithm, FLECS, which uses a FLExible Commitment Strategy with respect to plan-step orderings. It is able to use any strategy from delayed-commitment to eager-commitment. The combination of delayed and eager operator-ordering commitments allows FLECS to take advantage of the benefits of explicitly using a simulated execution state and reasoning about planning constraints. FLECS can vary its commitment strategy across different problems and domains, and also during the course of a single planning problem. FLECS represents a novel contribution to planning in that it explicitly provides the choice of which commitment strategy to use while planning. FLECS provides a framework to investigate the mapping from planning domains and problems to efficient planning strategies.

Planning is a complex reasoning task that is well suited for the study of improving performance and knowledge by learning, i.e. by accumulation and interpretation of planning experience. PRODIGY is an architecture that integrates planning with multiple learning mechanisms. Learning occurs at the planner's decision points and integration in PRODIGY is achieved via mutually interpretable knowledge structures. This article describes the PRODIGY planner, briefly reports on several learning modules developed earlier along the project, and presents in more detail two recently explored methods to learn to generate plans of better quality. We introduce the techniques, illustrate them with comprehensive examples, and show preliminary empirical results. The article also includes a retrospective discussion of the characteristics of the overall PRODIGY architecture and discusses their evolution within the goal of the project of building a large and robust integrated planning and learning system.

Modern industrial processes require advanced computer tools that should adapt to the user requirements and to the tasks being solved. Strategy learning consists of automating the acquisition of patterns of actions used while solving particular tasks. Current intelligent strategy learning systems acquire operational knowledge to improve the efficiency of a particular problem solver. However, these strategy learning tools should also provide a way of achieving low-cost solutions according to user-specific criteria. In this paper, we present a learning system, HAMLET, which is integrated in a planning architecture, PRODIGY, and acquires control knowledge to guide PRODIGY to efficiently produce cost-effective plans. HAMLET learns from planning episodes, by explaining why the correct decisions were made, and later refines the learned strategy knowledge to make it incrementally correct with experience.>