Manuela Veloso

AAAI Conference 2026 Conference Paper

Perturb Your Data: Paraphrase-Guided Training Data Watermarking

• Pranav Shetty
• Mirazul Haque
• Petr Babkin
• Zhiqiang Ma
• Xiaomo Liu
• Manuela Veloso

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.

KR Conference 2025 Conference Paper

A Planning Compilation to Reason About Goal Achievement at Planning Time

• Alberto Pozanco
• Marianela Morales
• Daniel Borrajo
• Manuela Veloso

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.

AAAI Conference 2025 Conference Paper

Auditing and Enforcing Conditional Fairness via Optimal Transport

• Mohsen Ghassemi
• Alan Mishler
• Niccolo Dalmasso
• Luhao Zhang
• Vamsi K. Potluru
• Tucker Balch
• Manuela Veloso

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.

UAI Conference 2025 Conference Paper

Distributionally and Adversarially Robust Logistic Regression via Intersecting Wasserstein Balls

• Aras Selvi
• Eleonora Kreacic
• Mohsen Ghassemi
• Vamsi K. Potluru
• Tucker R. Balch
• Manuela Veloso

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.

ICML Conference 2025 Conference Paper

EncryptedLLM: Privacy-Preserving Large Language Model Inference via GPU-Accelerated Fully Homomorphic Encryption

• Leo de Castro
• Daniel Escudero 0001
• Adya Agrawal
• Antigoni Polychroniadou
• Manuela Veloso

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.

ICLR Conference 2025 Conference Paper

Interpreting Language Reward Models via Contrastive Explanations

• Junqi Jiang
• Tom Bewley
• Saumitra Mishra
• Freddy Lécué
• Manuela Veloso

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.

ICML Conference 2025 Conference Paper

LSCD: Lomb-Scargle Conditioned Diffusion for Time series Imputation

• Elizabeth Fons
• Alejandro Sztrajman
• Yousef El-Laham
• Luciana Ferrer
• Svitlana Vyetrenko
• Manuela Veloso

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.

UAI Conference 2025 Conference Paper

Mixup Regularization: A Probabilistic Perspective

• Yousef El-Laham
• Niccolò Dalmasso
• Svitlana Vyetrenko
• Vamsi K. Potluru
• Manuela Veloso

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.

ECAI Conference 2025 Conference Paper

On Learning Action Costs from Input Plans

• Marianela Morales
• Alberto Pozanco
• Giuseppe Canonaco
• Sriram Gopalakrishnan
• Daniel Borrajo
• Manuela Veloso

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.

ECAI Conference 2025 Conference Paper

The Subset Sum Matching Problem

• Yufei Wu 0012
• Manuel R. Torres
• Parisa Zehtabi
• Alberto Pozanco
• Michael Cashmore
• Daniel Borrajo
• Manuela Veloso

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.

ICML Conference 2025 Conference Paper

To Steer or Not to Steer? Mechanistic Error Reduction with Abstention for Language Models

• Anna Hedström
• Salim I. Amoukou
• Tom Bewley
• Saumitra Mishra
• Manuela Veloso

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.

IROS Conference 2025 Conference Paper

Vibrotactile Sensing for Detecting Misalignments in Precision Manufacturing

• Kevin Zhang 0002
• Christopher Chang
• Shobhit Aggarwal
• Manuela Veloso
• F. Zeynep Temel
• Oliver Kroemer

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.

AAAI Conference 2024 Conference Paper

Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates

• Kyle Mana
• Fernando Acero
• Stephen Mak
• Parisa Zehtabi
• Michael Cashmore
• Daniele Magazzeni
• Manuela Veloso

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.

ICML Conference 2024 Conference Paper

Counterfactual Metarules for Local and Global Recourse

• Tom Bewley
• Salim I. Amoukou
• Saumitra Mishra
• Daniele Magazzeni
• Manuela Veloso

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.

NeurIPS Conference 2024 Conference Paper

Fair Wasserstein Coresets

• Zikai Xiong
• Niccolò Dalmasso
• Shubham Sharma
• Freddy Lecue
• Daniele Magazzeni
• Vamsi K. Potluru
• Tucker Balch
• Manuela Veloso

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

AAAI Conference 2024 Conference Paper

FairWASP: Fast and Optimal Fair Wasserstein Pre-processing

• Zikai Xiong
• Niccolò Dalmasso
• Alan Mishler
• Vamsi K. Potluru
• Tucker Balch
• Manuela Veloso

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.

HAXP Workshop 2024 Workshop Paper

On Computing Plans with Uniform Action Costs

• Alberto Pozanco
• Daniel Borrajo
• Manuela Veloso

In many real-world planning applications, agents might be interested in finding plans whose actions have costs that are as uniform as possible. Such plans provide agents with a sense of stability and predictability, which are key features when humans are the agents executing plans suggested by planning tools. This paper adapts three uniformity metrics to automated planning, and introduce planning-based compilations that allow to lexicographically optimize sum of action costs and action costs uniformity. Experimental results both in well-known and novel planning benchmarks show that the reformulated tasks can be effectively solved in practice to generate uniform plans.

ICML Conference 2024 Conference Paper

Progressive Inference: Explaining Decoder-Only Sequence Classification Models Using Intermediate Predictions

• Sanjay Kariyappa
• Freddy Lécué
• Saumitra Mishra
• Christopher Pond
• Daniele Magazzeni
• Manuela Veloso

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.

NeurIPS Conference 2024 Conference Paper

Sequential Harmful Shift Detection Without Labels

• Salim I. Amoukou
• Tom Bewley
• Saumitra Mishra
• Freddy Lecue
• Daniele Magazzeni
• Manuela Veloso

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.

ECAI Conference 2024 Conference Paper

Temporal Fairness in Decision Making Problems

• Manuel R. Torres
• Parisa Zehtabi
• Michael Cashmore
• Daniele Magazzeni
• Manuela Veloso

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.

ICAPS Conference 2023 Conference Paper

Combining Heuristic Search and Linear Programming to Compute Realistic Financial Plans

• Alberto Pozanco
• Kassiani Papasotiriou
• Daniel Borrajo
• Manuela Veloso

Defining financial goals and formulating actionable plans to achieve them are essential components for ensuring financial health. This task is computationally challenging, given the abundance of factors that can influence one’s financial situation. In this paper, we present the Personal Finance Planner (PFP), which can generate personalized financial plans that consider a person’s context and the likelihood of taking financially related actions to help them achieve their goals. PFP solves the problem in two stages. First, it uses heuristic search to find a high-level sequence of actions that increase the income and reduce spending to help users achieve their financial goals. Next, it uses integer linear programming to determine the best low-level actions to implement the high-level plan. Results show that PFP is able to scale on generating realistic financial plans for complex tasks involving many low level actions and long planning horizons.

UAI Conference 2023 Conference Paper

Differentially private synthetic data using KD-trees

• Eleonora Kreacic
• Navid Nouri
• Vamsi K. Potluru
• Tucker R. Balch
• Manuela Veloso

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.

ECAI Conference 2023 Conference Paper

Generating Replanning Goals Through Multi-Objective Optimization in Response to Execution Observation

• Alberto Pozanco
• Daniel Borrajo
• Manuela Veloso

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.

TMLR Journal 2023 Journal Article

Privacy-Preserving Energy-Based Generative Models for Marginal Distribution Protection

• Robert E. Tillman
• Tucker Balch
• Manuela Veloso

We consider learning generative models for sensitive financial and healthcare data. While previous work incorporates Differential Privacy (DP) into GAN training to protect the privacy of individual training instances, we consider a different privacy context where the primary objective is protecting the privacy of sensitive marginal distributions of the true generative process. We propose and motivate a new notion of privacy: \emph{$\alpha$-Level Marginal Distribution Privacy} ($\alpha$-LMDP), which provides a statistical guarantee that the sensitive generative marginal distributions are different from the observed real data. We then propose \emph{Privacy-Preserving Energy Models (PPEMs)}, a novel energy-based generative model formulation where the representations for these attributes are isolated from other attributes. This structured formulation motivates a learning procedure where a penalty based on a statistical goodness of fit test, the \emph{Kernel Stein Discrepancy}, can be applied to only the attributes requiring privacy so that $\alpha$-LMDP may be satisfied without affecting the other attributes. We evaluate this approach using financial and healthcare datasets and demonstrate that the resulting learnt generative models produce high fidelity synthetic data while preserving privacy. We also show that PPEMs can incorporate both $\alpha$-LMDP \emph{and} DP in contexts where both forms of privacy are required.

EUMAS Conference 2022 Conference Paper

Advising Agent for Service-Providing Live-Chat Operators

• Aviram Aviv
• Yaniv Oshrat
• Samuel Assefa
• Toby Mustapha
• Daniel Borrajo
• Manuela Veloso
• Sarit Kraus

Abstract Call centers, in which human operators attend clients using textual chat, are very common in modern e-commerce. Training enough skilled operators who are able to provide good service is a challenge. We propose a methodology for the development of an assisting agent that provides online advice to operators while they attend clients. The agent is easy-to-build and can be introduced to new domains without major effort in design, training and organizing sknowledge of the professional discipline. We demonstrate the applicability of the system in an experiment that realizes its full life-cycle on a specific domain, and analyze its capabilities.

AAMAS Conference 2022 Conference Paper

Advising Agent for Service-Providing Live-Chat Operators

• Aviram Aviv
• Yaniv Oshrat
• Samuel Assefa
• Toby Mustapha
• Daniel Borrajo
• Manuela Veloso
• Sarit Kraus

Call centers, in which human operators attend clients using textual chat, are very common in modern e-commerce. Training enough skilled operators who are able to provide good service is a challenge. We propose a methodology for the development of an assisting agent that provides online advice to operators while they attend clients. The agent is easy-to-build and can be introduced to new domains without major effort in design, training and organizing structured knowledge of the professional discipline. We demonstrate the applicability of the system in an experiment that realizes its full life-cycle on a specific domain, and analyze its capabilities.

NeurIPS Conference 2022 Conference Paper

ASPiRe: Adaptive Skill Priors for Reinforcement Learning

• Mengda Xu
• Manuela Veloso
• Shuran Song

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.

ICAPS Conference 2021 Conference Paper

Computing Opportunities to Augment Plans for Novel Replanning during Execution

• Daniel Borrajo
• Manuela Veloso

Traditionally, planning provides for execution plans as sequences of actions with preconditions and effects. Execution monitoring identifies failure conditions when the preconditions of an action do not match the state. Interestingly, planning proceeds by consuming a given initial state and abandoning reasoning about any facts not true in that state. In this paper, we define opportunities as such missing facts, and contribute an algorithm to compute them and augment a plan for execution with them. We then introduce a new execution opportunity monitoring that focusedly checks for these opportunities at each execution state. Opportunistic replanning proceeds now from the new state including the detected opportunities.

IROS Conference 2021 Conference Paper

Intelligent Execution through Plan Analysis

• Daniel Borrajo
• Manuela Veloso

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.

AAAI Conference 2021 Conference Paper

Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methods

• Nicholay Topin
• Stephanie Milani
• Fei Fang
• Manuela Veloso

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

IROS Conference 2021 Conference Paper

Search-based Planning with Learned Behaviors for Navigation among Pedestrians

• Ishani Chatterjee 0001
• Yash Oza
• Maxim Likhachev
• Manuela Veloso

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.

NeurIPS Conference 2020 Conference Paper

Calibration of Shared Equilibria in General Sum Partially Observable Markov Games

• Nelson Vadori
• Sumitra Ganesh
• Prashant Reddy
• Manuela Veloso

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.

ICAPS Conference 2020 Conference Paper

Efficient Robot Planning for Achieving Multiple Independent Partially Observable Tasks That Evolve over Time

• Anahita Mohseni-Kabir
• Manuela Veloso
• Maxim Likhachev

We focus on domains where a robot is required to accomplish a set of tasks that are partially observable and evolve independently of each other according to their dynamics. An example domain is a restaurant setting where a robot waiter should take care of an ongoing stream of tasks, namely serving a number of tables, including delivering food to the tables and checking on customers. An action that the robot should take next at any point of time typically depends on the duration of possible actions, the state of each table, and how these tables evolve over time, e. g. , the food becomes cold after a few time steps. As most of these domains are dynamic and tasks are frequently being added and removed, the robot typically needs to plan for a short h-step horizon to quickly decide on the next action and replans at each time step. A conventional approach to deal with this problem is to combine all the tasks' states and robot actions into one large model and to compute an h-step optimal policy for this combined model. For the problems that we are interested in, the number of tasks, e. g. , the number of tables in the restaurant domain, can be large making this planning approach computationally impractical. The observation that we make however is that in many domains the number of tasks that the robot can accomplish within h-steps is very limited. We present an algorithm that exploits this observation and decomposes the problem into a series of much smaller planning problems, the solution to which gives us an optimal solution. We demonstrate the efficiency of our algorithm on the restaurant domain.

ECAI Conference 2020 Conference Paper

Heuristics for Link Prediction in Multiplex Networks

• Robert E. Tillman
• Vamsi K. Potluru
• Jiahao Chen 0001
• Prashant P. Reddy
• Manuela Veloso

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 Erdős-Rényi 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.

IROS Conference 2020 Conference Paper

Localization and Force-Feedback with Soft Magnetic Stickers for Precise Robot Manipulation

• Tess Lee Hellebrekers
• Kevin Zhang 0002
• Manuela Veloso
• Oliver Kroemer
• Carmel Majidi

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.

JAAMAS Journal 2020 Journal Article

Optimal action sequence generation for assistive agents in fixed horizon tasks

• Kim Baraka
• Francisco S. Melo
• Manuela Veloso

Abstract Agents providing assistance to humans are faced with the challenge of automatically adjusting the level of assistance to ensure optimal performance. In this work, we argue that identifying the right level of assistance consists in balancing positive assistance outcomes and some (domain-dependent) measure of cost associated with assistive actions. Towards this goal, we contribute a general mathematical framework for structured tasks where an agent playing the role of a ‘provider’—e. g. , therapist, teacher—assists a human ‘receiver’—e. g. , patient, student. We specifically consider tasks where the provider agent needs to plan a sequence of actions over a fixed time horizon, where actions are organized along a hierarchy with increasing success probabilities, and some associated costs. The goal of the provider is to achieve a success with the lowest expected cost possible. We present OAssistMe, an algorithm that generates cost-optimal action sequences given the action parameters, and investigate several extensions of it, motivated by different potential application domains. We provide an analysis of the algorithms, including proofs for a number of properties of optimal solutions that, we show, align with typical human provider strategies. Finally, we instantiate our theoretical framework in the context of robot-assisted therapy tasks for children with Autism Spectrum Disorder (ASD). In this context, we present methods for determining action parameters based on a survey of domain experts and real child-robot interaction data. Our contributions unlock increased levels of flexibility for agents introduced in a variety of assistive contexts.

IROS Conference 2020 Conference Paper

Tensor Action Spaces for Multi-agent Robot Transfer Learning

• Devin Schwab
• Yifeng Zhu
• Manuela Veloso

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.

ICAPS Conference 2019 Conference Paper

A Theoretical and Algorithmic Analysis of Configurable MDPs

• Rui Silva
• Gabriele Farina
• Francisco S. Melo
• Manuela Veloso

This paper analyzes, from theoretical and algorithmic perspectives, a class of problems recently introduced in the literature of Markov decision processes—configurable Markov decision processes. In this new class of problems we jointly optimize the probability transition function and associated optimal policy, in order to improve the performance of a decision-making agent. We contribute a complexity analysis on the problem from a computational perspective, where we show that, in general, solving a configurable MDP is NP-Hard. We also discuss practical challenges often faced in solving this class of problems. Additionally, we formally derive a gradient-based approach that sheds some light on the correctness and limitations of existing methods. We conclude by demonstrating the application of different parameterizations of configurable MDPs in two scenarios, offering a discussion on advantages and drawbacks from modeling and algorithmic perspectives. Our contributions set the foundation for a better understanding of this recent problem, and the wider applicability of the underlying ideas to different planning problems.

AAMAS Conference 2019 Conference Paper

An Optimization Approach for Structured Agent-Based Provider/Receiver Tasks

• Kim Baraka
• Marta Couto
• Francisco S. Melo
• Manuela Veloso

This work contributes an optimization framework in the context of structured interactions between an agent playing the role of a ‘provider’ and a human ‘receiver’. Examples of provider/receiver interactions of interest include ones between occupational therapist and patient, or teacher and student. We specifically consider tasks where the provider agent needs to plan a sequence of actions with a fixed horizon, where actions are organized along a hierarchy with increasing probabilities of success and associated costs. The goal of the provider is to achieve a success with the lowest expected cost possible. In our application domains, a success may be for instance eliciting a desired behavior or a correct response from the receiver. We present a linear-time optimal planning algorithm that generates cost-optimal sequences for given action parameters. We also provide proofs for a number of properties of optimal solutions that align with typical human provider strategies. Finally, we instantiate our general formulation in the context of robot-assisted therapy tasks for children with Autism Spectrum Disorders (ASD). In this context, we present methods for determining action parameters, namely (1) an online survey with experts for determining action costs, and (2) a probabilistic model of child response based on data collected in a real child-robot interaction scenario. Our contributions may unlock increased levels of adaptivity for agents introduced in a variety of assistive contexts.

AAAI Conference 2019 Conference Paper

Generation of Policy-Level Explanations for Reinforcement Learning

• Nicholay Topin
• Manuela Veloso

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.

ICRA Conference 2019 Conference Paper

Learning Primitive Skills for Mobile Robots

• Yifeng Zhu
• Devin Schwab
• Manuela Veloso

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.

IJCAI Conference 2019 Conference Paper

MineRL: A Large-Scale Dataset of Minecraft Demonstrations

• William H. Guss
• Brandon Houghton
• Nicholay Topin
• Phillip Wang
• Cayden Codel
• Manuela Veloso
• Ruslan Salakhutdinov

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.

AIIM Journal 2019 Journal Article

Project INSIDE: towards autonomous semi-unstructured human–robot social interaction in autism therapy

• Francisco S. Melo
• Alberto Sardinha
• David Belo
• Marta Couto
• Miguel Faria
• Anabela Farias
• Hugo Gambôa
• Cátia Jesus

This paper describes the INSIDE system, a networked robot system designed to allow the use of mobile robots as active players in the therapy of children with autism spectrum disorders (ASD). While a significant volume of work has explored the impact of robots in ASD therapy, most such work comprises remotely operated robots and/or well-structured interaction dynamics. In contrast, the INSIDE system allows for complex, semi-unstructured interaction in ASD therapy while featuring a fully autonomous robot. In this paper we describe the hardware and software infrastructure that supports such rich form of interaction, as well as the design methodology that guided the development of the INSIDE system. We also present some results on the use of our system both in pilot and in a long-term study comprising multiple therapy sessions with children at Hospital Garcia de Orta, in Portugal, highlighting the robustness and autonomy of the system as a whole.

ICAPS Conference 2019 Conference Paper

Speeding Up Search-Based Motion Planning via Conservative Heuristics

• Ishani Chatterjee 0001
• Maxim Likhachev
• Ashwin Khadke
• Manuela Veloso

Weighted A* search (wA*) is a popular tool for robot motionplanning. Its efficiency however depends on the quality of heuristic function used. In fact, it has been shown that the correlation between the heuristic function and the true costto-goal significantly affects the efficiency of the search, when used with a large weight on the heuristics. Motivated by this observation, we investigate the problem of computing heuristics that explicitly aim to minimize the amount of search efforts in finding a feasible plan. The key observation we exploit is that while heuristics tries to guide the search along what looks like an optimal path towards the goal, there are other paths that are clearly sub-optimal yet are much easier to compute. For example, in motion planning domains like footstep-planning for humanoids, a heuristic that guides the search along a path away from obstacles is less likely to encounter local minima compared with the heuristics that guides the search along an optimal but close-to-obstacles path. We utilize this observation to define the concept of conservative heuristics and propose a simple algorithm for computing such a heuristic function. Experimental analysis on (1) humanoid footstep planning (simulation), (2) path planning for a UAV (simulation), and a real-world experiment in footstep-planning for a NAO robot shows the utility of the approach.

IROS Conference 2018 Conference Paper

A Rationale-Driven Team Plan Representation for Autonomous Intra-Robot Replanning *

• Philip Cooksey
• Manuela Veloso

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.

AAMAS Conference 2018 Conference Paper

Multi-Armed Bandit Algorithms for Spare Time Planning of a Mobile Service Robot

• Max Korein
• Manuela Veloso

We assume that service robots will have spare time in between scheduled user requests, which they could use to perform additional unrequested services in order to learn a model of users’ preferences and receive reward. However, a mobile service robot is constrained by the need to travel through the environment to reach a user in order to perform a service for them, as well as the need to carry out scheduled user requests. We present modified versions of Thompson Sampling and UCB1, existing algorithms used in multiarmed bandit problems, which plan ahead considering the time and location constraints of a mobile service robot. We compare them to existing versions of Thompson Sampling and UCB1 and find that our modified planning algorithms outperform the original versions in terms of both reward received and the effectiveness of the model learned in a simulation.

IJCAI Conference 2018 Conference Paper

Robot Task Interruption by Learning to Switch Among Multiple Models

• Anahita Mohseni-Kabir
• Manuela Veloso

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.

IROS Conference 2018 Conference Paper

Robot-driven Trajectory Improvement for Feeding Tasks

• Travers Rhodes
• Manuela Veloso

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.

IROS Conference 2018 Conference Paper

Robust Object Recognition Through Symbiotic Deep Learning In Mobile Robots

• João Cartucho
• Rodrigo M. M. Ventura
• Manuela Veloso

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.

IROS Conference 2018 Conference Paper

Teaching Robots to Predict Human Motion

• Liangyan Gui
• Kevin Zhang 0002
• Yu-Xiong Wang
• Xiaodan Liang
• José M. F. Moura
• Manuela Veloso

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.

AAMAS Conference 2018 Conference Paper

Towards a Robust Interactive and Learning Social Robot

• Michiel De Jong
• Kevin Zhang
• Aaron M. Roth
• Travers Rhodes
• Robin Schmucker
• Chenghui Zhou
• Sofia Ferreira
• Jo�o Cartucho

Pepper is a humanoid robot, specifically designed for social interaction, that has been deployed in a variety of public environments. A programmable version of Pepper is also available, enabling our focused research on perception and behavior robustness and capabilities of an interactive social robot. We address Pepper perception by integrating state-of-the-art vision and speech recognition systems and experimentally analyzing their effectiveness. As we recognize limitations of the individual perceptual modalities, we introduce a multi-modality approach to increase the robustness of human social interaction with the robot. We combine vision, gesture, speech, and input from an onboard tablet, a remote mobile phone, and external microphones. Our approach includes the proactive seeking of input from a different modality, adding robustness to the failures of the separate components. We also introduce a learning algorithm to improve communication capabilities over time, updating speech recognition through social interactions. Finally, we realize the rich robot body-sensory data and introduce both a nearest-neighbor and a deep learning approach to enable Pepper to classify and speak up a variety of its own body motions. We view the contributions of our work to be relevant both to Pepper specifically and to other general social robots.

AAMAS Conference 2018 Conference Paper

Zero Shot Transfer Learning for Robot Soccer

• Devin Schwab
• Yifeng Zhu
• Manuela Veloso

We present a method for doing zero-shot transfer of multi-agent policies as the number of teammates, opponents, and environment size varies. We apply our approach to RoboCup inspired test domains, where it is necessary for policies to adapt to changing numbers of robots due to in-game breakages. We introduce the concept of encoding not only the states as an image, but also the action space as a multi-channel image, which allows the state and action size to remain fixed across team size changes. We also introduce Fully Convolutional Q-Networks, which represent Q-functions in this space using Fully Convolutional Networks. We present results for zero-shot transfer of these policies across team sizes and field sizes, showing that performance remains consistent as both change.

IROS Conference 2017 Conference Paper

Adaptive indirect control through communication in collaborative human-robot interaction

• Rui Silva
• Miguel Faria 0001
• Francisco S. Melo
• Manuela Veloso

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.

JAAMAS Journal 2017 Journal Article

Allocating training instances to learning agents for team formation

• Somchaya Liemhetcharat
• Manuela Veloso

Abstract Agents can learn to improve their coordination with their teammates and increase team performance. There are finite training instances, where each training instance is an opportunity for the learning agents to improve their coordination. In this article, we focus on allocating training instances to learning agent pairs, i. e. , pairs that improve coordination with each other, with the goal of team formation. Agents learn at different rates, and hence, the allocation of training instances affects the performance of the team formed. We build upon previous work on the Synergy Graph model, that is learned completely from data and represents agents’ capabilities and compatibility in a multi-agent team. We formally define the learning agents team formation problem, and compare it with the multi-armed bandit problem. We consider learning agent pairs that improve linearly and geometrically, i. e. , the marginal improvement decreases by a constant factor. We contribute algorithms that allocate the training instances, and compare against algorithms from the multi-armed bandit problem. In our simulations, we demonstrate that our algorithms perform similarly to the bandit algorithms in the linear case, and outperform them in the geometric case. Further, we apply our model and algorithms to a multi-agent foraging problem, thus demonstrating the efficacy of our algorithms in general multi-agent problems.

IROS Conference 2017 Conference Paper

Intra-robot replanning to enable team plan conditions

• Philip Cooksey
• Manuela Veloso

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.

ICRA Conference 2017 Conference Paper

Learning individual motion preferences from audience feedback of motion sequences

• Junyun Tay
• Manuela Veloso
• I-Ming Chen 0001

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.

RLDM Conference 2017 Conference Abstract

Multi-modal Deep Reinforcement Learning with a Novel Sensor-based Dropout

• Guan-Horng Liu
• Avinash Siravuru
• Sai Prab-
• Manuela Veloso
• George Kantor

Sensor fusion is a key driver in the success of autonomous driving, given how instrumental it is to improve accuracy and robustness in the vehicle’s algorithmic decision making. However, in the space of end-to-end sensorimotor control, this multi-modal outlook has not received much attention. In the interest of enhancing safety and accuracy in control, a multi-modal approach to end-to-end autonomous navigation is need of the hour. Here, we introduce Multi-modal Deep Reinforcement Learning, and demonstrate how the use of multiple sensors improves the reward for an agent. For this purpose, we augment using both DDPG and NAF algorithms to admit multiple sensor input. The efficacy of a multi-modal policy is shown through extensive simulations experiments in TORCS, a popular open-source racing car game. Additionally, we introduce a new stochastic regularization technique, called Sensor Dropout to reduces the network’s sensitivity to any one sensor. Suitable metrics have been devised to study this behavior and highlight its applicability to other domains that operate in multi-modal settings.

SoCS Conference 2017 Conference Paper

Search Reduction through Conservative Abstract-Space Based Heuristic

• Ishani Chatterjee 0001
• Maxim Likhachev
• Manuela Veloso

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.

IROS Conference 2017 Conference Paper

Visualizing robot behaviors as automated video annotations: A case study in robot soccer

• Danny Zhu
• Manuela Veloso

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.

ICRA Conference 2016 Conference Paper

Active sensing data collection with autonomous mobile robots

• Richard Wang
• Manuela Veloso
• Srinivasan Seshan

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.

ECAI Conference 2016 Conference Paper

Adaptive Symbiotic Collaboration for Targeted Complex Manipulation Tasks

• Rui Silva
• Francisco S. Melo
• Manuela Veloso

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.

IROS Conference 2016 Conference Paper

Autonomous mapping between motions and labels

• Junyun Tay
• I-Ming Chen 0001
• Manuela Veloso

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.

AAAI Conference 2016 Conference Paper

ClaimEval: Integrated and Flexible Framework for Claim Evaluation Using Credibility of Sources

• Mehdi Samadi
• Partha Talukdar
• Manuela Veloso
• Manuel Blum

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

ICAPS Conference 2016 Conference Paper

Online Learning of Robot Soccer Free Kick Plans Using a Bandit Approach

• Juan Pablo Mendoza
• Reid G. Simmons
• Manuela Veloso

This paper presents an online learning approach for teams of autonomous soccer robots to select free kick plans. In robot soccer, free kicks present an opportunity to execute plans with relatively controllable initial conditions. However, the effectiveness of each plan is highly dependent on the adversary, and there are few free kicks during each game, making it necessary to learn online from sparse observations. To achieve learning, we first greatly reduce the planning space by framing the problem as a contextual multi-armed bandit problem, in which the actions are a set of pre-computed plans, and the state is the position of the free kick on the field. During execution, we model the reward function for different free kicks using Gaussian Processes, and perform online learning using the Upper Confidence Bound algorithm. Results from a physics-based simulation reveal that the robots are capable of adapting to various different realistic opponents to maximize their expected reward during free kicks.

ECAI Conference 2016 Conference Paper

PA*: Optimal Path Planning for Perception Tasks

• Tiago Raul de Sousa Pereira
• Manuela Veloso
• António Paulo Moreira

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.

AAAI Conference 2016 Conference Paper

Selectively Reactive Coordination for a Team of Robot Soccer Champions

• Juan Pablo Mendoza
• Joydeep Biswas
• Philip Cooksey
• Richard Wang
• Steven Klee
• Danny Zhu
• Manuela Veloso

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.

IS Journal 2016 Journal Article

The 1,000-km Challenge: Insights and Quantitative and Qualitative Results

• Joydeep Biswas
• Manuela Veloso

On 18 November 2014, a team of four autonomous CoBot robots reached 1, 000-km of overall autonomous navigation, as a result of a 1, 000-km challenge that the authors had set three years earlier. The authors are frequently asked for the lessons learned, as well as the performance results. In this article, they introduce the challenge and contribute a detailed presentation of technical insights as well as quantitative and qualitative results. They have previously presented the algorithms for the individual technical contributions, namely robot localization, symbiotic robot autonomy, and robot task scheduling. In this article, they present the data collected over the 1, 000-km challenge and analyze it to evaluate the accuracy and robustness of the localization algorithms on the CoBots. Furthermore, they present technical insights into the algorithms, which they believe are responsible for the robots' continuous robust performance.

IJCAI Conference 2016 Conference Paper

Verbalization: Narration of Autonomous Robot Experience

• Stephanie Rosenthal
• Sai P. Selvaraj
• Manuela Veloso

Autonomous mobile robots navigate in our spaces by planning and executing routes to destinations. When a mobile robot appears at a location, there is no clear way to understand what navigational path the robot planned and experienced just by looking at it. In this work, we address the generation of narrations of autonomous mobile robot navigation experiences. We contribute the concept of verbalization as a parallel to the well-studied concept of visualization. Through verbalizations, robots can describe through language what they experience, in particular in their paths. For every executed path, we consider many possible verbalizations that could be generated. We introduce the verbalization space that covers the variability of utterances that the robot may use to narrate its experience to different humans. We present an algorithm for segmenting a path and mapping each segment to an utterance, as a function of the desired point in the verbalization space, and demonstrate its application using our mobile service robot moving in our buildings. We believe our verbalization space and algorithm are applicable to different narrative aspects for many mobile robots, including autonomous cars.

IROS Conference 2016 Conference Paper

Visibility maps for any-shape robots

• Tiago Raul de Sousa Pereira
• Manuela Veloso
• António Paulo Moreira

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.

IJCAI Conference 2015 Conference Paper

AskWorld: Budget-Sensitive Query Evaluation for Knowledge-on-Demand

• Mehdi Samadi
• Partha Talukdar
• Manuela Veloso
• Tom Mitchell

Recently, several Web-scale knowledge harvesting systems have been built, each of which is competent at extracting information from certain types of data (e. g. , unstructured text, structured tables on the web, etc.). In order to determine the response to a new query posed to such systems (e. g. , is sugar a healthy food?), it is useful to integrate opinions from multiple systems. If a response is desired within a specific time budget (e. g. , in less than 2 seconds), then maybe only a subset of these resources can be queried. In this paper, we address the problem of knowledge integration for on-demand time-budgeted query answering. We propose a new method, AskWorld, which learns a policy that chooses which queries to send to which resources, by accommodating varying budget constraints that are available only at query (test) time. Through extensive experiments on real world datasets, we demonstrate AskWorld’s capability in selecting most informative resources to query within test-time constraints, resulting in improved performance compared to competitive baselines.

IJCAI Conference 2015 Conference Paper

CoBots: Robust Symbiotic Autonomous Mobile Service Robots

• Manuela Veloso
• Joydeep Biswas
• Brian Coltin
• Stephanie Rosenthal

We research and develop autonomous mobile service robots as Collaborative Robots, i. e. , CoBots. For the last three years, our four CoBots have autonomously navigated in our multi-floor office buildings for more than 1, 000km, as the result of the integration of multiple perceptual, cognitive, and actuations representations and algorithms. In this paper, we identify a few core aspects of our CoBots underlying their robust functionality. The reliable mobility in the varying indoor environments comes from a novel episodic non-Markov localization. Service tasks requested by users are the input to a scheduler that can consider different types of constraints, including transfers among multiple robots. With symbiotic autonomy, the CoBots proactively seek external sources of help to fill-in for their inevitable occasional limitations. We present sampled results from a deployment and conclude with a brief review of other features of our service robots.

IROS Conference 2015 Conference Paper

Global localization by soft object recognition from 3D Partial Views

• A. Fernando Ribeiro
• Susana Brandão
• João Paulo Costeira
• Manuela Veloso

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.

IJCAI Conference 2015 Conference Paper

Handling Complex Commands as Service Robot Task Requests

• Vittorio Perera
• Manuela Veloso

We contribute a novel approach to understand, dialogue, plan, and execute complex sentences to command a mobile service robot. We define a complex command as a natural language sentence consisting of sensing-based conditionals, conjunctions, and disjunctions. We introduce a flexible templatebased algorithm to extract such structure from the parse tree of the sentence. As the complexity of the command increases, extracting the right structure using the template-based algorithm decreases becomes more problematic. We introduce two different dialogue approaches that enable the user to confirm or correct the extracted command structure. We present how the structure used to represent complex commands can be directly used for planning and execution by the service robot. We show results on a corpus of 100 complex commands.

IROS Conference 2015 Conference Paper

Indoor trajectory identification: Snapping with uncertainty

• Richard Wang
• Ravi Shroff
• Yilong Zha
• Srinivasan Seshan
• Manuela Veloso

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.

IROS Conference 2015 Conference Paper

Multi-robot task acquisition through sparse coordination

• Steven D. Klee
• Guglielmo Gemignani
• Daniele Nardi
• Manuela Veloso

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.

ICRA Conference 2015 Conference Paper

Plan execution monitoring through detection of unmet expectations about action outcomes

• Juan Pablo Mendoza
• Manuela Veloso
• Reid G. Simmons

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.

IROS Conference 2015 Conference Paper

Towards table tennis with a quadrotor autonomous learning robot and onboard vision

• Rui Silva
• Francisco S. Melo
• Manuela Veloso

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.

ICRA Conference 2015 Conference Paper

Wireless map-based handoffs for mobile robots

• Richard Wang
• Matthew K. Mukerjee
• Manuela Veloso
• Srinivasan Seshan

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.

IROS Conference 2014 Conference Paper

Coverage planning with finite resources

• Grant P. Strimel
• Manuela Veloso

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.

ICRA Conference 2014 Conference Paper

Episodic non-Markov localization: Reasoning about short-term and long-term features

• Joydeep Biswas
• Manuela Veloso

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.

ICRA Conference 2014 Conference Paper

Focused optimization for online detection of anomalous regions

• Juan Pablo Mendoza
• Manuela Veloso
• Reid G. Simmons

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.

ICRA Conference 2014 Conference Paper

O-Snap: Optimal snapping of odometry trajectories for route identification

• Richard Wang
• Manuela Veloso
• Srinivasan Seshan

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.

ICRA Conference 2014 Conference Paper

Online pickup and delivery planning with transfers for mobile robots

• Brian Coltin
• Manuela Veloso

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.

IROS Conference 2014 Conference Paper

Ridesharing with passenger transfers

• Brian Coltin
• Manuela Veloso

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.

AAAI Conference 2014 Conference Paper

Scheduling for Transfers in Pickup and Delivery Problems with Very Large Neighborhood Search

• Brian Coltin
• Manuela Veloso

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.

ICRA Conference 2014 Conference Paper

The Partial View Heat Kernel descriptor for 3D object representation

• Susana Brandão
• João Paulo Costeira
• Manuela Veloso

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.

AIJ Journal 2014 Journal Article

Weighted synergy graphs for effective team formation with heterogeneous ad hoc agents

• Somchaya Liemhetcharat
• Manuela Veloso

Previous approaches to select agents to form a team rely on single-agent capabilities, and team performance is treated as a sum of such known capabilities. Motivated by complex team formation situations, we address the problem where both single-agent capabilities may not be known upfront, e. g. , as in ad hoc teams, and where team performance goes beyond single-agent capabilities and depends on the specific synergy among agents. We formally introduce a novel weighted synergy graph model to capture new interactions among agents. Agents are represented as vertices in the graph, and their capabilities are represented as Normally-distributed variables. The edges of the weighted graph represent how well the agents work together, i. e. , their synergy in a team. We contribute a learning algorithm that learns the weighted synergy graph using observations of performance of teams of only two and three agents. Further, we contribute two team formation algorithms, one that finds the optimal team in exponential time, and one that approximates the optimal team in polynomial time. We extensively evaluate our learning algorithm, and demonstrate the expressiveness of the weighted synergy graph in a variety of problems. We show our approach in a rich ad hoc team formation problem capturing a rescue domain, namely the RoboCup Rescue domain, where simulated robots rescue civilians and put out fires in a simulated urban disaster. We show that the weighted synergy graph outperforms a competing algorithm, thus illustrating the efficacy of our model and algorithms.

ICRA Conference 2013 Conference Paper

Fast human detection for indoor mobile robots using depth images

• Benjamin Choi
• Çetin Meriçli
• Joydeep Biswas
• Manuela Veloso

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.

IROS Conference 2013 Conference Paper

Forming an effective multi-robot team robust to failures

• Somchaya Liemhetcharat
• Manuela Veloso

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.

ICRA Conference 2013 Conference Paper

Learning environmental knowledge from task-based human-robot dialog

• Thomas Kollar
• Vittorio Perera
• Daniele Nardi
• Manuela Veloso

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.

IROS Conference 2013 Conference Paper

Learning the synergy of a new teammate

• Somchaya Liemhetcharat
• Manuela Veloso

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.

ICRA Conference 2013 Conference Paper

Multi-robot information sharing for complementing limited perception: A case study of moving ball interception

• Richard Wang
• Manuela Veloso
• Srinivasan Seshan

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.

AAAI Conference 2013 Conference Paper

Negotiated Learning for Smart Grid Agents: Entity Selection based on Dynamic Partially Observable Features

• Prashant Reddy
• Manuela Veloso

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.

AAAI Conference 2013 Conference Paper

OpenEval: Web Information Query Evaluation

• Mehdi Samadi
• Manuela Veloso
• Manuel Blum

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

AAMAS Conference 2013 Conference Paper

Scheduling Mobile Exploration Tasks for Environment Learning

• Max Korein
• Brian Coltin
• Manuela Veloso

Autonomous mobile service robots navigate in their environments in order to perform tasks requested by users. We envision service robots learning about their environment by scheduling exploration tasks in which they seek out new knowledge and using this knowledge to improve the services they offer. We present the Task Graph algorithm, which chooses times for user requests based on the robot’s knowledge so as to increase the chance of success, and schedules exploration tasks in between user requests by reducing the problem to a graph search.

AAMAS Conference 2013 Conference Paper

Towards Ridesharing with Passenger Transfers

• Brian Coltin
• Manuela Veloso

Ridesharing services have the potential to fill empty seats in cars, reduce emissions and enable more efficient transportation. We propose rideshare services which transfer passengers between multiple drivers. By planning for transfers, we increase the availability and range of the rideshare service, and reduce the total vehicular miles travelled by the network. We propose three heuristics to schedule rideshare routes with transfers. Each provides a tradeoff in effectiveness and computational cost. We demonstrate these tradeoffs and the advantage of transfers in simulation.

AAMAS Conference 2012 Conference Paper

Autonomous Robot Dancing Driven by Beats and Emotions of Music

• Guangyu Xia
• Junyun Tay
• Roger Dannenberg
• Manuela Veloso

Many robot dances are preprogrammed by choreographers for a particular piece of music so that the motions can be smoothly executed and synchronized with the dance music. We are interested in automating the task of robot dance choreography to allow robots to dance without detailed human planning. Robot dance movements are synchronized to the beats and reflect the emotion of any music. Our work is made up of two parts: (1) The first algorithm plans a sequence of dance movements that is driven by the beats and the emotions detected through the preprocessing of selected dance music. (2) We also contribute a real-time synchronizing algorithm to minimize the error between the execution of the motions and the plan. Our work builds on previous research to extract beats and emotions from music audio. We created a library of parameterized motion primitives, whereby each motion primitive is composed of a set of keyframes and durations and generate the sequence of dance movements from this library. We demonstrate the feasibility of our algorithms on the NAO humanoid robot to show that the robot is capable of using the mappings defined to autonomously dance to any music. Although we present our work using a humanoid robot, our algorithm is applicable to other robots.

IROS Conference 2012 Conference Paper

CoBots: Collaborative robots servicing multi-floor buildings

• Manuela Veloso
• Joydeep Biswas
• Brian Coltin
• Stephanie Rosenthal
• Thomas Kollar
• Çetin Meriçli
• Mehdi Samadi
• Susana Brandão

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.

ICRA Conference 2012 Conference Paper

Depth camera based indoor mobile robot localization and navigation

• Joydeep Biswas
• Manuela Veloso

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.

ICRA Conference 2012 Conference Paper

Efficient task execution and refinement through multi-resolution corrective demonstration

• Çetin Meriçli
• Manuela Veloso
• H. Levent Akin

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.

AAMAS Conference 2012 Conference Paper

Enabling Robots to Find and Fetch Objects by Querying the Web

• Thomas Kollar
• Mehdi Samadi
• Manuela Veloso

This paper describes an algorithm that enables a mobile robot to find an arbitrary object and take it to a destination location. Previous approaches have been able to search for a fixed set of objects. In contrast, our approach is able to dynamically construct a cost function to find any object by querying the web. The performance of our approach has been evaluated in a realistic simulator, and has been demonstrated on a companion robot, which can successfully execute plans such as finding a“coffee”and taking it to a destination location like, “Gates-Hillman Center, Room 7002. ”

AAAI Conference 2012 Conference Paper

Factored Models for Multiscale Decision-Making in Smart Grid Customers

• Prashant Reddy
• Manuela Veloso

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

AAAI Conference 2012 Conference Paper

Mobile Robot Planning to Seek Help with Spatially-Situated Tasks

• Stephanie Rosenthal
• Manuela Veloso

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.

AAMAS Conference 2012 Conference Paper

Modeling and Learning Synergy for Team Formation with Heterogeneous Agents

• Somchaya Liemhetcharat
• Manuela Veloso

The performance of a team at a task depends critically on the composition of its members. There is a notion of synergy in human teams that represents how well teams work together, and we are interested in modeling synergy in multi-agent teams. We focus on the problem of team formation, i. e. , selecting a subset of a group of agents in order to perform a task, where each agent has its own capabilities, and the performance of a team of agents depends on the individual agent capabilities as well as the synergistic effects among the agents. We formally define synergy and how it can be computed using a synergy graph, where the distance between two agents in the graph correlates with how well they work together. We contribute a learning algorithm that learns a synergy graph from observations of the performance of subsets of the agents, and show that our learning algorithm is capable of learning good synergy graphs without prior knowledge of the interactions of the agents or their capabilities. We also contribute an algorithm to solve the team formation problem using the learned synergy graph, and experimentally show that the team formed by our algorithm outperforms a competing algorithm.

IROS Conference 2012 Conference Paper

Motion interference detection in mobile robots

• Juan Pablo Mendoza
• Manuela Veloso
• Reid G. Simmons

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.

IROS Conference 2012 Conference Paper

Planar polygon extraction and merging from depth images

• Joydeep Biswas
• Manuela Veloso

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.

ICAPS Conference 2012 Conference Paper

Short-Sighted Stochastic Shortest Path Problems

• Felipe W. Trevizan
• Manuela Veloso

Two extreme approaches can be applied to solve a probabilistic planning problem, namely closed loop algorithms and open loop (a. k. a. replanning) algorithms. While closed loop algorithms invest significant computational effort to generate a closed form solution, open loop algorithms compute open form solutions and interact with the environment in order to refine the computed solution. In this paper, we introduce short-sighted Stochastic Shortest Path (SSP), a new model in which solutions computed based on it can be executed for at least t steps as a closed form solution. Using short-sighted SSPs, we present a novel probabilistic planner called Short-sighted Open Loop Planner (SOLP) that bridges the gap between open and closed loop planners by varying the parameter t: as t increases, more actions can be executed without replanning and, for t sufficiently large, a closed form solution is obtained. We prove that SOLP is asymptotically optimal. To the best of our knowledge, SOLP is the unique probabilistic planner that at the same time provides both replanning and optimality guarantees. We empirically compare SOLP with the winners of the previous probabilistic planning competitions and SOLP outperforms all of them in 33. 3% of the problems and ties with the best planner in 48. 3% of the problems.

NeurIPS Conference 2012 Conference Paper

Trajectory-Based Short-Sighted Probabilistic Planning

• Felipe Trevizan
• Manuela Veloso

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.

AAAI Conference 2012 Conference Paper

Using the Web to Interactively Learn to Find Objects

• Mehdi Samadi
• Thomas Kollar
• Manuela Veloso

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.

IROS Conference 2012 Conference Paper

Video: RoboCup robot soccer history 1997 - 2011

• Manuela Veloso
• Peter Stone 0001

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.

IROS Conference 2012 Conference Paper

Weighted synergy graphs for role assignment in ad hoc heterogeneous robot teams

• Somchaya Liemhetcharat
• Manuela Veloso

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

IJCAI Conference 2011 Conference Paper

Action Selection via Learning Behavior Patterns in Multi-Robot Systems

• Can Erdogan
• Manuela Veloso

The RoboCup robot soccer Small Size League has been running since 1997 with many teams successfully competiting and very effectively playing the games. Teams of five robots, with a combined autonomous 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. However, in this fast-paced noisy real robot league, recognizing the opponent team strategies and accordingly adapting one's own play has proven to be a considerable challenge. In this work, we analyze logged data of real games gathered by the CMDragons team, and contribute several results in learning and responding to opponent strategies. We define episodes as segments of interest in the logged data, and introduce a representation that captures the spatial and temporal data of the multi-robot system as instances of geometrical trajectory curves. We then learn a model of the team strategies through a variant of agglomerative hierarchical clustering. Using the learned cluster model, we are able to classify a team behavior incrementally as it occurs. Finally, we define an algorithm that autonomously generates counter tactics, in a simulation based on the real logs, showing that it can recognize and respond to opponent strategies.

SoCS Conference 2011 Conference Paper

Adapting a Rapidly-Exploring Random Tree for Automated Planning

• Vidal Alcázar
• Manuela Veloso
• Daniel Borrajo

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.

IROS Conference 2011 Conference Paper

Corrective gradient refinement for mobile robot localization

• Joydeep Biswas
• Brian Coltin
• Manuela Veloso

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.

AIJ Journal 2011 Journal Article

Decentralized MDPs with sparse interactions

• Francisco S. Melo
• Manuela Veloso

Creating coordinated multiagent policies in environments with uncertainty is a challenging problem, which can be greatly simplified if the coordination needs are known to be limited to specific parts of the state space. In this work, we explore how such local interactions can simplify coordination in multiagent systems. We focus on problems in which the interaction between the agents is sparse and contribute a new decision-theoretic model for decentralized sparse-interaction multiagent systems, Dec-SIMDPs, that explicitly distinguishes the situations in which the agents in the team must coordinate from those in which they can act independently. We relate our new model to other existing models such as MMDPs and Dec-MDPs. We then propose a solution method that takes advantage of the particular structure of Dec-SIMDPs and provide theoretical error bounds on the quality of the obtained solution. Finally, we show a reinforcement learning algorithm in which independent agents learn both individual policies and when and how to coordinate. We illustrate the application of the algorithms throughout the paper in several multiagent navigation scenarios.

AAAI Conference 2011 Conference Paper

Learned Behaviors of Multiple Autonomous Agents in Smart Grid Markets

• Prashant Reddy
• Manuela Veloso

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 Qlearning, 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.

AAAI Conference 2011 Conference Paper

Learning Accuracy and Availability of Humans Who Help Mobile Robots

• Stephanie Rosenthal
• Manuela Veloso
• Anind Dey

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 algorithm is 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.

IROS Conference 2011 Conference Paper

Modeling mutual capabilities in heterogeneous teams for role assignment

• Somchaya Liemhetcharat
• Manuela Veloso

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.

AAAI Conference 2011 Conference Paper

Multi-Observation Sensor Resetting Localization with Ambiguous Landmarks

• Brian Coltin
• Manuela Veloso

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 sensorbased 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 ef- ficiently to the robot’s true position than standard sensor resetting, and is more robust to systematic vision errors.

IROS Conference 2011 Conference Paper

RSSI-based physical layout classification and Target Tethering in mobile ad-hoc networks

• Prashant P. Reddy
• Manuela Veloso

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.

AAMAS Conference 2010 Conference Paper

An Effective Personal Mobile Robot Agent Through Symbiotic Human-Robot Interaction

• Stephanie Rosenthal
• Joydeep Biswas
• Manuela Veloso

Several researchers, present authors included, envision personalmobile robot agents that can assist humans in their dailytasks. Despite many advances in robotics, such mobile robot agentsstill face many limitations in their perception, cognition, and actioncapabilities. In this work, we propose a symbiotic interaction betweenrobot agents and humans to overcome the robot limitations whileallowing robots to also help humans. We introduce a visitor'scompanion robot agent, as a natural task for such symbioticinteraction, e. g. , the visitor lacks knowledge of the environment butcan easily open a door or read a door label, while the mobile robotwith no arms cannot open a door and may be confused about its exactlocation, but can plan paths well through the building and can provideuseful relevant information to the visitor. We present this visitorcompanion task in detail with an enumeration and formalization of theactions of the robot agent in its interaction with the human. Webriefly describe the wifi-based robot localization algorithm and showresults of the different levels of human help to the robot during the robotnavigation. We then model the tradeoffs of the value of the robot help to the human and present illustrative experiments. Our work has been fully implemented in a mobile robot agent, CoBot, which has successfully navigated for several hours and continues to navigate in our indoor environment.

AAMAS Conference 2010 Conference Paper

Approximate Planning for Decentralized MDPs with Sparse Interactions

• Francisco Melo
• Manuela Veloso

We explore how local interactions can simplify the process of decision-making in multiagent systems. We review decentralized sparse-interaction Markov decision process thatexplicitly distinguishes the situations in which the agentsin the team must coordinate from those in which they canact independently. We situate this class of problems withindifferent multiagent models, such as MMDPs and transitionindependent Dec-MDPs. We contribute new algorithm for efficient planning in this class of problems. We provideempirical comparisons between our algorithms and other existing algorithms for this class of problems.

AAAI Conference 2010 Conference Paper

Biped Walk Learning Through Playback and Corrective Demonstration

• Cetin Mericli
• Manuela Veloso

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

IROS Conference 2010 Conference Paper

Mobile robot task allocation in hybrid wireless sensor networks

• Brian Coltin
• Manuela Veloso

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.

IROS Conference 2010 Conference Paper

Multiple-Cue Object Recognition on outside datasets

• Sarah S. Aboutalib
• Manuela Veloso

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.

AAMAS Conference 2010 Conference Paper

Mutual State Capability-Based Role Assignment Model

• Somchaya Liemhetcharat
• Manuela Veloso

We formally present the Mutual State Capability-Based RoleAssignment (MuSCRA) model, as we introduce that an agent, acting in a team, has capabilities that depend not only onits own individual skills, but also on its teammates and theirmutual state. The MuSCRA model includes a descriptionof roles in terms of its association value with states and actions. Role assignment policies are evaluated with a utilityaccounting for the match between the new mutual state capabilities and the desired roles, weighted by a risk factor.

ICRA Conference 2010 Conference Paper

RSS-based relative localization and tethering for moving robots in unknown environments

• Stefan Zickler
• Manuela Veloso

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.

ECAI Conference 2010 Conference Paper

Variable Level-Of-Detail Motion Planning in Environments with Poorly Predictable Bodies

• Stefan Zickler
• Manuela Veloso

Motion planning in dynamic environments consists of the generation of a collision-free trajectory from an initial to a goal state. When the environment contains uncertainty, preventing a perfect predictive model of its dynamics, a robot ends up only successfully executing a short part of the plan and then requires replanning, using the latest observed state of the environment. Each such replanning step is computationally expensive. Furthermore, we note that such sophisticated planning effort is unnecessary as the resulting plans are not likely to ever be fully executed, due to an unpredictable and changing environment. In this paper, we introduce the concept of Variable Level-Of-Detail (VLOD) planning, that is able to focus its search on obtaining accurate short-term results, while considering the far-future with a different level of detail, selectively ignoring the physical interactions with poorly predictable dynamic objects (e. g. , other mobile bodies that are controlled by external entities). Unlike finite-horizon planning, which limits the maximum search depth, VLOD planning deals with local minima and generates full plans to the goal, while requiring much less computation than traditional planning. We contribute VLOD planning on a rich simulated physics-based planner and show results for varying LOD thresholds and replanning intervals.

ICRA Conference 2010 Conference Paper

WiFi localization and navigation for autonomous indoor mobile robots

• Joydeep Biswas
• Manuela Veloso

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.

AIJ Journal 2009 Journal Article

A case-based approach for coordinated action selection in robot soccer

• Raquel Ros
• Josep Lluís Arcos
• Ramon Lopez de Mantaras
• Manuela Veloso

Designing coordinated robot behaviors in uncertain, dynamic, real-time, adversarial environments, such as in robot soccer, is very challenging. In this work we present a case-based reasoning approach for cooperative action selection, which relies on the storage, retrieval, and adaptation of example cases. We focus on cases of coordinated attacking passes between robots in the presence of the defending opponent robots. We present the case representation explicitly distinguishing between controllable and uncontrollable indexing features, corresponding to the positions of the team members and opponent robots, respectively. We use the symmetric properties of the domain to automatically augment the case library. We introduce a retrieval technique that weights the similarity of a situation in terms of the continuous ball positional features, the uncontrollable features, and the cost of moving the robots from the current situation to match the case controllable features. The case adaptation includes a best match between the positions of the robots in the past case and in the new situation. The robots are assigned an adapted position to which they move to maximize the match to the retrieved case. Case retrieval and reuse are achieved within the distributed team of robots through communication and sharing of own internal states and actions. We evaluate our approach, both in simulation and with real robots, in laboratory scenarios with two attacking robots versus two defending robots as well as versus a defender and a goalie. We show that we achieve the desired coordinated passing behavior, and also outperform a reactive action selection approach.

ICRA Conference 2009 Conference Paper

Automatic weight learning for multiple data sources when learning from demonstration

• Brenna Argall
• Brett Browning
• Manuela Veloso

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.

IROS Conference 2009 Conference Paper

Cue-based equivalence classes and incremental discrimination for multi-cue recognition of "interactionable" objects

• Sarah S. Aboutalib
• Manuela Veloso

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.

AAMAS Conference 2009 Conference Paper

Learning of Coordination: Exploiting Sparse Interactions in Multiagent Systems

• Francisco S. Melo
• Manuela Veloso

Creating coordinated multiagent policies in environments with uncertainty is a challenging problem, which can be greatly simplified if the coordination needs are known to be limited to specific parts of the state space, as previous work has successfully shown. In this work, we assume that such needs are unknown and we investigate coordination learning in multiagent settings. We contribute a reinforcement learning based algorithm in which independent decisionmakers/agents learn both individual policies and when and how to coordinate. We focus on problems in which the interaction between the agents is sparse, exploiting this property to minimize the coupling of the learning processes for the different agents. We introduce a two-layer extension of Q-learning, in which we augment the action space of each agent with a coordination action that uses information from other agents to decide the correct action. Our results show that our agents learn both to act coordinate and to act independently, in the different regions of the space where they need to, and need not to, coordinate, respectively.

ICRA Conference 2008 Conference Paper

An approximate algorithm for solving oracular POMDPs

• Nicholas Armstrong-Crews
• Manuela Veloso

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.

ICRA Conference 2008 Conference Paper

CMDragons: Dynamic passing and strategy on a champion robot soccer team

• James Bruce
• Stefan Zickler
• Mmichael Licitra
• Manuela Veloso

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.

IROS Conference 2008 Conference Paper

Learning equivalent action choices from demonstration

• Sonia Chernova
• Manuela Veloso

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.

IROS Conference 2008 Conference Paper

Learning robot motion control with demonstration and advice-operators

• Brenna Argall
• Brett Browning
• Manuela Veloso

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.

ICRA Conference 2008 Conference Paper

Learning tactic-based motion models with fast particle smoothing

• Yang Gu
• Manuela Veloso

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.

IROS Conference 2008 Conference Paper

Learning task specific plans through sound and visually interpretable demonstrations

• Harini Veeraraghavan
• Manuela Veloso

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.

IROS Conference 2008 Conference Paper

Online ZMP sampling search for biped walking planning

• Jinsu Liu
• Manuela Veloso

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.

AAMAS Conference 2008 Conference Paper

Teaching Multi-Robot Coordination using Demonstration of Communication and State Sharing

• Sonia Chernova
• Manuela Veloso

Solutions to complex tasks often require the cooperation of multiple robots, however, developing multi-robot policies can present many challenges. In this work, we introduce teaching by demonstration in the context of multi-robot tasks, enabling a single teacher to instruct multiple robots to work together through a demonstration of the desired behavior. Within this framework, we contribute two approaches for teaching coordination based on different communication and information sharing strategies. To enable the teacher to divide attention between multiple robots, each robot uses a confidence-based algorithm that allows it to regulate its autonomy and determine the need for demonstration. Evaluation is performed using two Sony QRIO robots learning a real-world collaborative ball sorting task.

AAMAS Conference 2008 Conference Paper

Teaching Sequential Tasks with Repetition through Voice and Vision

• Harini Veeraraghavan
• Manuela Veloso

AAMAS Conference 2007 Conference Paper

Confidence-Based Policy Learning from Demonstration Using Gaussian Mixture Models

• Sonia Chernova
• Manuela Veloso

We contribute an approach for interactive policy learning through expert demonstration that allows an agent to actively request and effectively represent demonstration examples. In order to address the inherent uncertainty of human demonstration, we represent the policy as a set of Gaussian mixture models (GMMs), where each model, with multiple Gaussian components, corresponds to a single action. Incrementally received demonstration examples are used as training data for the GMM set. We then introduce our confident execution approach, which focuses learning on relevant parts of the domain by enabling the agent to identify the need for and request demonstrations for specific parts of the state space. The agent selects between demonstration and autonomous execution based on statistical analysis of the uncertainty of the learned Gaussian mixture set. As it achieves proficiency at its task and gains confidence in its actions, the agent operates with increasing autonomy, eliminating the need for unnecessary demonstrations of already acquired behavior, and reducing both the training time and the demonstration workload of the expert. We validate our approach with experiments in simulated and real robot domains.

AAMAS Conference 2007 Conference Paper

Executing Multi-Robot Cases through a Single Coordinator

• Raquel Ros
• Manuela Veloso

It is challenging to design general robot soccer coordination behaviors that address individual states. We have successfully followed a case-based approach to define behaviors for a single soccer robot. In our multi-robot system we now distinguish retriever robots that access the case library, reason about the situation, and select the most appropriate cases. They communicate with the other robots and they all execute the retrieved case in a coordinated way. We evaluate our approach with two robots demonstrating that the robots successfully coordinate and the number of passes during a game highly increases compared to an approach with an implicit coordination mechanism.

AAMAS Conference 2007 Conference Paper

Exploiting Factored Representations for Decentralized Execution in Multi-agent Teams

• Maayan Roth
• Reid Simmons
• Manuela Veloso

In many cooperative multi-agent domains, there exist some states in which the agents can act independently and others in which they need to coordinate with their teammates. In this paper, we explore how factored representations of state can be used to generate factored policies that can, with minimal communication, be executed distributedly by a multi-agent team. The factored policies indicate those portions of the state where no coordination is necessary, automatically alert the agents when they reach a state in which they do need to coordinate, and determine what the agents should communicate in order to achieve this coordination. We evaluate the success of our approach experimentally by comparing the amount of communication needed by a team executing a factored policy to a team that needs to communicate in every timestep.

IROS Conference 2007 Conference Paper

Feature selection in conditional random fields for activity recognition

• Douglas L. Vail
• John D. Lafferty
• Manuela Veloso

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 lscr 1 regularization 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 lscr 1 regularization, which simultaneously smoothes the model and selects features; lscr 2 regularization, which smoothes to avoid over-fitting, but performs no feature selection; and models trained with no smoothing.

ICRA Conference 2007 Conference Paper

Learning to Select State Machines using Expert Advice on an Autonomous Robot

• Brenna Argall
• Brett Browning
• Manuela Veloso

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.

ICRA Conference 2007 Conference Paper

Oracular Partially Observable Markov Decision Processes: A Very Special Case

• Nicholas Armstrong-Crews
• Manuela Veloso

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

KER Journal 2007 Journal Article

PLTOOL: A knowledge engineering tool for planning and learning

• Susana Fernández
• Daniel Borrajo
• Raquel Fuentetaja
• Juan D. Arias
• Manuela Veloso

Absract Artificial intelligence (AI) planning solves the problem of generating a correct and efficient ordered set of instantiated activities, from a knowledge base of generic actions, which when executed will transform some initial state into some desirable end-state. There is a long tradition of work in AI for developing planners that make use of heuristics that are shown to improve their performance in many real world and artificial domains. The developers of planners have chosen between two extremes when defining those heuristics. The domain-independent planners use domain-independent heuristics, which exploit information only from the ‘syntactic’ structure of the problem space and of the search tree. Therefore, they do not need any ‘semantic’ information from a given domain in order to guide the search. From a knowledge engineering (KE) perspective, the planners that use this type of heuristics have the advantage that the users of this technology need only focus on defining the domain theory and not on defining how to make the planner efficient (how to obtain ‘good’ solutions with the minimal computational resources). However, the domain-dependent planners require users to manually represent knowledge not only about the domain theory, but also about how to make the planner efficient. This approach has the advantage of using either better domain-theory formulations or using domain knowledge for defining the heuristics, thus potentially making them more efficient. However, the efficiency of these domain-dependent planners strongly relies on the KE and planning expertise of the user. When the user is an expert on these two types of knowledge, domain-dependent planners clearly outperform domain-independent planners in terms of number of solved problems and quality of solutions. Machine-learning (ML) techniques applied to solve the planning problems have focused on providing middle-ground solutions as compared to the aforementioned two extremes. Here, the user first defines a domain theory, and then executes the ML techniques that automatically modify or generate new knowledge with respect to both the domain theory and the heuristics. In this paper, we present our work on building a tool, PLTOOL (planning and learning tool), to help users interact with a set of ML techniques and planners. The goal is to provide a KE framework for mixed-initiative generation of efficient and good planning knowledge.

IROS Conference 2007 Conference Paper

Simulation and weights of multiple cues for robust object recognition

• Sarah S. Aboutalib
• Manuela Veloso

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.

AAMAS Conference 2007 Conference Paper

Towards Using Multiple Cues for Robust Object Recognition

• Sarah Aboutalib
• Manuela Veloso

A robot's ability to assist humans in a variety of tasks, e. g. in search and rescue or in a household, heavily depends on the robot's reliable recognition of the objects in the environment. Numerous approaches attempt to recognize objects based only on the robot's vision. However, the same type of object can have very different visual appearances, such as shape, size, pose, and color. Although such approaches are widely studied with relative success, the general object recognition task still remains very challenging. We build our work upon the fact that robots can observe humans interacting with the objects in their environment, and thus providing numerous non-visual cues to those objects' identities. We research on 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. We realize the challenging issue that multiple cues can have different weight in their association with an object definition and need to be taken into account during recognition. In this paper, we contribute a probabilistic relational representation of the cue weights and an object recognition algorithm that can flexibly combine multiple cues of any type to robustly recognize objects. We show illustrative results of our implemented approach using visual, activity, gesture, and speech cues, provided by machine or human, to recognize objects more robustly than when using only a single cue.

JAAMAS Journal 2006 Journal Article

An experts approach to strategy selection in multiagent meeting scheduling

• Elisabeth Crawford
• Manuela Veloso

Abstract In the multiagent meeting scheduling problem, agents negotiate with each other on behalf of their users to schedule meetings. While a number of negotiation approaches have been proposed for scheduling meetings, it is not well understood how agents can negotiate strategically in order to maximize their users’ utility. To negotiate strategically, agents need to learn to pick good strategies for negotiating with other agents. In this paper, we show how agents can learn online to negotiate strategically in order to better satisfy their users’ preferences. We outline the applicability of experts algorithms to the problem of learning to select negotiation strategies. In particular, we show how two different experts approaches, plays [3] and Exploration–Exploitation Experts (EEE) [10] can be adapted to the task. We show experimentally the effectiveness of our approach for learning to negotiate strategically.

ICRA Conference 2006 Conference Paper

Dynamically formed Heterogeneous Robot Teams Performing Tightly-coordinated Tasks

• Edward Gil Jones
• Brett Browning
• M. Bernardine Dias
• Brenna Argall
• Manuela Veloso
• Anthony Stentz

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

AAMAS Conference 2006 Conference Paper

Multi-Model Motion Tracking under Multi-Agent Actuators

• Gu Yang
• Manuela Veloso

ICRA Conference 2006 Conference Paper

Multi-model Tracking using Team Actuation Models

• Yang Gu
• Manuela Veloso

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

AAMAS Conference 2006 Conference Paper

Probabilistic Policy Reuse in a Reinforcement Learning Agent

• Fernando Fernandez
• Manuela Veloso

ICRA Conference 2006 Conference Paper

Real-time Object Detection using Segmented and Grayscale Images

• Juan Fasola
• Manuela Veloso

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

ICAPS Conference 2006 Conference Paper

Reusing and Building a Policy Library

• Fernando Fernández 0001
• Manuela Veloso

Policy Reuse is a method to improve reinforcement learning with the ability to solve multiple tasks by building upon past problem solving experience, as accumulated in a Policy Library. Given a new task, a Policy Reuse learner uses the past policies in the library as a probabilistic bias in its new learning process. We present how the effectiveness of each reuse episode is indicative of the novelty of the new task with respect to the previously solved ones in the policy library. In the paper we review Policy Reuse, and we introduce theoretical results that demonstrate that: (i) a Policy Library can be selectively and incrementally built while learning different problems; (ii) the Policy Library can be understood as a "basis" of the domain that represents its structure through a set of core policies; and (iii) given the basis of a domain, we can define a lower bound for its reuse gain.

IROS Conference 2006 Conference Paper

Team-Driven Multi-Model Motion Tracking with Communication

• Yang Gu
• Manuela Veloso

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

AAMAS Conference 2005 Conference Paper

Bumping Strategies for the Multiagent Agreement Problem

• Pragnesh Jay Modi
• Manuela Veloso

ICRA Conference 2005 Conference Paper

Learning to Track Multiple People in Omnidirectional Video

• Fernando De la Torre
• Carlos Vallespí
• Paul E. Rybski
• Manuela Veloso
• Takeo Kanade

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.

ICRA Conference 2005 Conference Paper

Non-Parametric Time Series Classification

• Scott Lenser
• Manuela Veloso

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.

IROS Conference 2005 Conference Paper

Real-time, adaptive color-based robot vision

• Brett Browning
• Manuela Veloso

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.

AAAI Conference 2004 Conference Paper

Advice Generation from Observed Execution: Abstract Markov Decision Process Learning

• Patrick Riley
• Manuela Veloso

An advising agent, a coach, provides advice to other agents about how to act. In this paper we contribute an advice generation method using observations of agents acting in an environment. Given an abstract state definition and partially specified abstract actions, the algorithm extracts a Markov Chain, infers a Markov Decision Process, and then solves the MDP (given an arbitrary reward signal) to generate advice. We evaluate our work in a simulated robot soccer environment and experimental results show improved agent performance when using the advice generated from the MDP for both a sub-task and the full soccer game.

IROS Conference 2004 Conference Paper

An evolutionary approach to gait learning for four-legged robots

• Sonia Chernova
• Manuela Veloso

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.

ICRA Conference 2004 Conference Paper

CAMEO: Camera Assisted Meeting Event Observer

• Paul E. Rybski
• Fernando De la Torre
• Raju Patil
• Carlos Vallespí
• Manuela Veloso
• Brett Browning

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.

AAAI Conference 2004 System Paper

CAMEO: Modeling Human Activity in Formal Meeting Situations

• Paul E. Rybski
• Raju Patil
• Manuela Veloso

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 used to observe formal meeting environments and infer the activities of people attending them.

IROS Conference 2004 Conference Paper

Classification of robotic sensor streams using non-parametric statistics

• Scott Lenser
• Manuela Veloso

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.

ICRA Conference 2004 Conference Paper

Development of a Soccer-playing Dynamically-balancing Mobile Robot

• Brett Browning
• Paul E. Rybski
• Jeremy Lawrence Searock
• Manuela Veloso

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.

ICAPS Conference 2004 Conference Paper

Fault Tolerant Planning: Toward Probabilistic Uncertainty Models in Symbolic Non-Deterministic Planning

• Rune Møller Jensen
• Manuela Veloso
• Randal E. Bryant

Symbolic non-deterministic planning represents action effects as sets of possible next states. In this paper, we move toward a more probabilistic uncertainty model by distinguishing between likely primary effects and unlikely secondary effects of actions. We consider the practically important case where secondary effects are failures, and introduce n-fault tolerant plans that are robust for up to n faults occurring during plan execution. Fault tolerant plans are more restrictive than weak plans, but more relaxed than strong cyclic and strong plans. We show that optimal n-fault tolerant plans can be generated by the usual strong algorithm. However, due to non-local error states, it is often beneficial to decouple the planning for primary and secondary effects. We employ this approach for two specialized algorithms 1-FTP (blind) and 1-GFTP (guided) and demonstrate their advantages experimentally in significant real-world domains.

ICRA Conference 2004 Conference Paper

Learning and using Models of Kicking Motions for Legged Robots

• Sonia Chernova
• Manuela Veloso

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.

IROS Conference 2004 Conference Paper

People detection and tracking in high resolution panoramic video mosaic

• Raju Patil
• Paul E. Rybski
• Takeo Kanade
• Manuela Veloso

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.

ICAPS Conference 2004 Conference Paper

Plays as Effective Multiagent Plans Enabling Opponent-Adaptive Play Selection

• Michael H. Bowling
• Brett Browning
• Manuela Veloso

Coordinated action for a team of robots is a challenging problem, especially in dynamic, unpredictable environments. Robot soccer is an instance of a domain where well defined goals need to be achieved by multiple executors in an adversarial setting. Such domains offer challenging multiagent planning problems that need to coordinate multiagent execution in response to other agents that are not part of our team plans. In this work, we introduce the concept of a play as a multiagent plan that combines both reactive principles, which are the focus of traditional approaches for coordinating robot actions, and deliberative principles. We further introduce the concept of a playbook as a method for seamlessly combining multiple team plans. The playbook provides a set of alternative team behaviors which form the basis for our third contribution of play adaptation. We describe how these concepts were concretely implemented in the CMDragons robot soccer team. We also show empirical results indicating the importance of adaptation in adversarial or other unpredictable environments.

IROS Conference 2004 Conference Paper

Turning Segways into soccer robots

• Jeremy Lawrence Searock
• Brett Browning
• Manuela Veloso

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.

IJCAI Conference 2003 Conference Paper

A Formalization of Equilibria for Multiagent Planning

• Michael Bowling
• Rune Jensen
• Manuela Veloso

IROS Conference 2003 Conference Paper

A real-time world model for multi-robot teams with high-latency communication

• Maayan Roth
• Douglas L. Vail
• Manuela Veloso

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.

ICRA Conference 2003 Conference Paper

Automatic detection and response to environmental change

• Scott Lenser
• Manuela Veloso

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.

AAMAS Conference 2003 Conference Paper

Coaching Advice and Adaptation

• Patrick Riley
• Manuela Veloso

ICML Conference 2003 Conference Paper

DISTILL: Learning Domain-Specific Planners by Example

• Elly Winner
• Manuela Veloso

ICRA Conference 2003 Conference Paper

Fast and accurate vision-based pattern detection and identification

• James Bruce
• Manuela Veloso

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.

ICAPS Conference 2003 Conference Paper

Guided Symbolic Universal Planning

• Rune Møller Jensen
• Manuela Veloso
• Randal E. Bryant

Symbolic universal planning based on the reduced Ordered Binary Decision Diagram (OBDD) has been shown to be an efficient approach for planning in non-deterministic domains. To date, however, no guided algorithms exist for synthesizing universal plans. In this paper, we introduce a general approach for guiding universal planning based on an existing method for heuristic symbolic search in deterministic domains. We present three new sound and complete algorithms for best-first strong, strong cyclic, and weak universal planning. Our experimental results show that guiding the search dramatically can reduce both the computation time and the size of the generated plans.

AAMAS Conference 2003 Conference Paper

MONAD: A Flexible Multi-Agent Control Architecture

• Thuc Vu
• Jared Go
• Gal Kaminka
• Manuela Veloso
• Brett Browning

ICRA Conference 2003 Conference Paper

Multi-robot team response to a multi-robot opponent team

• James Bruce
• Michael H. Bowling
• Brett Browning
• Manuela Veloso

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.

IJCAI Conference 2003 Conference Paper

Simultaneous Adversarial Multi-Robot Learning

• Michael Bowling
• Manuela Veloso

Multi-robot learning faces all of the challenges of robot learning with all of the challenges of multiagent learning. There has been a great deal of recent research on multiagent reinforcement learning in stochastic games, which is the intuitive extension of MDPs to multiple agents. This recent work, although general, has only been applied to small games with at most hundreds of states. On the other hand robot tasks have continuous, and often complex, state and action spaces. Robot learning tasks demand approximation and generalization techniques, which have only received extensive attention in single-agent learning. In this paper we introduce GraWoLF, a general-purpose, scalable, multiagent learning algorithm. It combines gradient-based policy learning techniques with the WoLF ("Win or Learn Fast") variable learning rate. We apply this algorithm to an adversarial multirobot task with simultaneous learning. We show results of learning both in simulation and on the real robots. These results demonstrate that GraWoLF can learn successful policies, overcoming the many challenges in multi-robot learning.

IROS Conference 2003 Conference Paper

Visual sonar: fast obstacle avoidance using monocular vision

• Scott Lenser
• Manuela Veloso

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.

ICAPS Conference 2002 Conference Paper

Analyzing Plans with Conditional Effects

• Elly Winner
• Manuela Veloso

Several tasks, such as plan reuse and agent modeling, rely on interpreting a given or observed plan to generate the underlying plan rationale. Although there are several previous methods that successfully extract plan rationales, they do not apply to complex plans, in particular to plans with actions that have conditional effects. In this paper, we introduce SPRAWL, an algorithm to find a minimal annotated partially ordered structure that maximizes a given evaluation function for an observed totally ordered plan with conditional effects. The algorithm proceeds in a two-phased approach, first preprocessing the given plan using a novel needs analysis technique that builds a needs tree to identify the dependencies between operators in the totally ordered plan. The needs tree is then processed to construct a partial ordering that captures the complete rationale of the given plan. We also provide a polynomial-time algorithm to find non-optimal minimal annotated partial orderings of observed totally ordered plans with conditional effects. We provide illustrative examples and discuss the challenges we faced.

ICRA Conference 2002 Conference Paper

Improbability Filtering for Rejecting False Positives

• Brett Browning
• Michael H. Bowling
• Manuela Veloso

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.

JMLR Journal 2002 Journal Article

Learning to Construct Fast Signal Processing Implementations

• Bryan Singer
• Manuela Veloso

A single signal processing algorithm can be represented by many mathematically equivalent formulas. However, when these formulas are implemented in code and run on real machines, they have very different runtimes. Unfortunately, it is extremely difficult to model this broad performance range. Further, the space of formulas for real signal transforms is so large that it is impossible to search it exhaustively for fast implementations. We approach this search question as a control learning problem. We present a new method for learning to generate fast formulas, allowing us to intelligently search through only the most promising formulas. Our approach incorporates signal processing knowledge, hardware features, and formula performance data to learn to construct fast formulas. Our method learns from performance data for a few formulas of one size and then can construct formulas that will have the fastest runtimes possible across many sizes.

AIJ Journal 2002 Journal Article

Multiagent learning using a variable learning rate

• Michael Bowling
• Manuela Veloso

Learning to act in a multiagent environment is a difficult problem since the normal definition of an optimal policy no longer applies. The optimal policy at any moment depends on the policies of the other agents. This creates a situation of learning a moving target. Previous learning algorithms have one of two shortcomings depending on their approach. They either converge to a policy that may not be optimal against the specific opponents' policies, or they may not converge at all. In this article we examine this learning problem in the framework of stochastic games. We look at a number of previous learning algorithms showing how they fail at one of the above criteria. We then contribute a new reinforcement learning technique using a variable learning rate to overcome these shortcomings. Specifically, we introduce the WoLF principle, “Win or Learn Fast”, for varying the learning rate. We examine this technique theoretically, proving convergence in self-play on a restricted class of iterated matrix games. We also present empirical results on a variety of more general stochastic games, in situations of self-play and otherwise, demonstrating the wide applicability of this method.

ICAPS Conference 2002 Conference Paper

Planning for Distributed Execution through Use of Probabilistic Opponent Models

• Patrick F. Riley
• Manuela Veloso

In multiagent domains with adversarial and cooperative team agents, team agents should be adaptive to the current environment and opponent. We introduce an online method to provide the agents with team plans that a "coach" agent generates in response to the specific opponents. The coach agent can observe the agents’ behaviors but it has only periodic communication with the rest of the team. The coach uses a Simple Temporal Network to represent team plans as coordinated movements among the multiple agents and the coach searches for an opponent-dependent plan for its teammates. This plan is then communicated to the agents, who execute the plan in a distributed fashion, using information from the plan to maintain consistency among the team members. In order for these plans to be effective and adaptive, models of opponent movement are used in the planning. The coach is then able to quickly select between different models online by using a Bayesian style update on a probability distribution over the models. Planning then uses the model which is found to be the most likely. The system is fully implemented in a simulated robotic soccer environment. In several recent games with completely unknown adversarial teams, the approach demonstrated a visible adaptation to the different teams.

IROS Conference 2002 Conference Paper

Real-time randomized path planning for robot navigation

• James Bruce
• Manuela Veloso

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.

ICML Conference 2001 Conference Paper

Convergence of Gradient Dynamics with a Variable Learning Rate

• Michael H. Bowling
• Manuela Veloso

ICML Conference 2001 Conference Paper

Learning to Generate Fast Signal Processing Implementations

• Bryan Singer
• Manuela Veloso

ICML Conference 2000 Conference Paper

Efficient Learning Through Evolution: Neural Programming and Internal Reinforcement

• Astro Teller
• Manuela Veloso

IROS Conference 2000 Conference Paper

Fast and inexpensive color image segmentation for interactive robots

• James Bruce
• Tucker R. Balch
• Manuela Veloso

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.

AIJ Journal 2000 Journal Article

Internal reinforcement in a connectionist genetic programming approach

• Astro Teller
• Manuela Veloso

Genetic programming (GP) can learn complex concepts by searching for the target concept through evolution of a population of candidate hypothesis programs. However, unlike some learning techniques, such as Artificial Neural Networks (ANNs), GP does not have a principled procedure for changing parts of a learned structure based on that structure's performance on the training data. GP is missing a clear, locally optimal update procedure, the equivalent of gradient-descent backpropagation for ANNs. This article introduces a new algorithm, “internal reinforcement”, for defining and using performance feedback on program evolution. This internal reinforcement principled mechanism is developed within a new connectionist representation for evolving parameterized programs, namely “neural programming”. We present the algorithms for the generation of credit and blame assignment in the process of learning programs using neural programming and internal reinforcement. The article includes a comprehensive overview of genetic programming and empirical experiments that demonstrate the increased learning rate obtained by using our principled program evolution approach.

ICML Conference 2000 Conference Paper

Learning to Predict Performance from Formula Modeling and Training Data

• Bryan Singer
• Manuela Veloso

ICAPS Conference 2000 Conference Paper

OBDD-Based Universal Planning for Multiple Synchronized Agents in Non-Deterministic Domains

• Rune Møller Jensen
• Manuela Veloso

Modelchecking representation and search lechniclueS were recently shownto be efficiently applicahle to planning, in particular to non-deterministic plam, ing. OrderedBinaxy Dt: cision Diagram. ~(OBDD. ~)encode planningdomainas a non-determinist i c finite’ aul. omaton (NI: A) and fast algorhhmsfi’om moclelchecking search for a solution plan. With proper encodings. OBDDs (’all effectively scale and can provide t, niversal phms for complex plmmingdomains. Weare particularly interested in addressing the complexitiesarisivg in non-deterministic, mtdti-agemdomains. In this paper, we present U. MOP, 1 a IIPWunivct. ’sal OBDD-hased planning frameworkapplicable to non-deterministic and muhi-agent dom~fins. Weintroduce a new planning domainth. script. ion lazlguage,:\)~DL, 2 to include the specification of such non-deterministic, multiagemdomains. The langoage contrilutles the explicit d(. finit ion of t’ont reliable agent., anduncolttrollablc environm(, ntagents. Wedescribe I he Sylll ax and sclnantics of NI41)Lm, dshowhowto huikl an efficient OltDI)1rased representation of an: VADLdescripl. ion. The UMOI’ planningsysl. cmsuses; \i..! [.)[.;. rod it inch, desthe previot, sly developedst tong and strong cyclic plamfing algorithms(C. imatti et al.. 199s~a. 1998b). In addition. we introduce a new optimistic platming algorithm, whit: h relaxes opl. imality gum’aaltee.,, anti generates plausible universal plans in somedomains where no st tong or strong cyclic solution exists. Wepresenl, empirical results in a previouslytested non-deterministic domains. Wealso iutroducc three new multi-agent domainswith complexenvironmentactions. [)’MOI’ is shownto bc a rich emdetficit, nt plannivg system.

ICRA Conference 2000 Conference Paper

Robotics in Edutainment

• Minoru Asada
• Raffaello D'Andrea
• Andreas Birk 0002
• Hiroaki Kitano
• Manuela Veloso

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.

ICRA Conference 2000 Conference Paper

Sensor Resetting Localization for Poorly Modelled Mobile Robots

• Scott Lenser
• Manuela Veloso

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.

ICAPS Conference 2000 Conference Paper

Vision-Servoed Localization and Behavior-Based Planning for an Autonomous Quadruped Legged Robot

• Manuela Veloso
• Elly Winner
• Scott Lenser
• James Bruce
• Tucker R. Balch

Planning actions for real robots in dynamic, and mlcertain environments is a challenging problem. It is not viable to use a complete model of the world: it is most appropriate to achieve goals mid handle uncertainty by integrating deliberation and behavior-based reactive planning. Wesuccessfully developed a system integrating perception and action for the RoboCup99 Sony legged robot league. The quadruped legged robots are fully autonomous and thus must. have onboard vision, localization a~td action selection. We briefly present our perception algorithm that automatically classifies arid tracks colored blobs in real time. We then briefly introduce our Sensor Resetting I, ocalization (SRL) algorithm which is an extension of Monte Carlo Localization. Vision and localization provide the state input for action selection. Our robust and sensible behavior scheme handles dynamic changes in information accuracy. We developed a utility-based system for using mid acquiring location information. Finally, we have devised several special built-in plans to deal with times when urgent action is needed and the robot cannot afford to colh: ct accurate location information. Wepresent results using the real robots, which demonst. rate the success of our approach. Our team of Sony quadruped legged robots, CMTrio-99, won all but one of its games in RoboCup99, and was awarded third place in the competition.

IJCAI Conference 1999 Conference Paper

Bounding the Suboptimality of Reusing Subproblems

• Michael Bowling
• Manuela Veloso

We are interested in the problem of determining a course of action to achieve a desired objective in a non-deterministic environment. Markov decision processes (MDPs) provide a framework for representing this action selection problem, and there are a number of algorithms that learn optimal policies within this formulation. This framework has also been used to study state space abstraction, problem decomposition, and policy reuse. These techniques sacrifice optimality of their solution for improved learning speed. In this paper we examine the suboptimality of reusing policies that are solutions to subproblems. This is done within a restricted class of MDPs, namely those where non-zero reward is received only upon reaching a goal state. We introduce the definition of a subproblem within this class and provide motivation for how reuse of subproblem solutions can speed up learning. The contribution of this paper is the derivation of a tight bound on the loss in optimality from this reuse. We examine a bound that is based on Bellman error, which applies to all MDPs, but is not tight enough to be useful. We contribute our own theoretical result that gives an empirically tight bound on this suboptimality.

AAAI Conference 1999 Short Paper

Learning State Features from Policies to Bias Exploration in Reinforcement Learning

• Bryan Singer
• Manuela Veloso
• Carnegie Mellon University

When given several problems to solve in some domain, a standard reinforcement learner learns an optimal policy from scratch for each problem. This seems rather unfortunate in that one might expect some domain-specific information to be present in the solution to one problem for solving the next problem. Using this information would improve the reinforcement learner’s performance. However, policies learned by standard reinforcement learning techniques are often very dependent on the exact states, rewards, and state transitions in the particular problem. Therefore, it is infeasible to directly apply a learned policy to new problems, and so several approaches have been and are being investigated to find structure, abstraction, generalization, and/or policy reuse in reinforcement learning. Within our line of research, we describe each state in terms of local features, assuming that these state features together with the learned policies can be used to abstract out the domain characteristics from the specific layout of states and rewards of a particular problem. When given a new problem to solve, this abstraction is used as an exploration bias to improve the rate of convergence of a reinforcement learner.

AIJ Journal 1999 Journal Article

RoboCup: Today and tomorrow—What we have learned

• Minoru Asada
• Hiroaki Kitano
• Itsuki Noda
• Manuela Veloso

RoboCup is an increasingly successful attempt to promote the full integration of AI and robotics 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, which the gamut of intelligent robotics research issues are naturally involved. This article describes what we have learned from the past RoboCup activities, mainly the first and the second RoboCups, and overviews the future perspectives of RoboCup in the next century. First, the issue on what and why RoboCup is addressed, and a wide range of research issues are explained. Next, the current leagues are introduced and the research achievements are reviewed from a viewpoint of system architecture. Some of these achievements are included in this special issue. Finally, prospects for future activities are discussed.

AIJ Journal 1999 Journal Article

Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork

• Peter Stone
• Manuela Veloso

Multi-agent domains consisting of teams of agents that need to collaborate in an adversarial environment offer challenging research opportunities. In this article, we introduce periodic team synchronization (PTS) domains as time-critical environments in which agents act autonomously with low communication, but in which they can periodically synchronize in a full-communication setting. The two main contributions of this article are a flexible team agent structure and a method for inter-agent communication. First, the team agent structure allows agents to capture and reason about team agreements. We achieve collaboration between agents through the introduction of formations. A formation decomposes the task space defining a set of roles. Homogeneous agents can flexibly switch roles within formations, and agents can change formations dynamically, according to pre-defined triggers to be evaluated at run-time. This flexibility increases the performance of the overall team. Our teamwork structure further includes pre-planning for frequently occurring situations. Second, the communication method is designed for use during the low-communication periods in PTS domains. It overcomes the obstacles to inter-agent communication in multi-agent environments with unreliable, single-channel, high-cost, low-bandwidth communication. We fully implemented both the flexible teamwork structure and the communication method in the domain of simulated robotic soccer, and conducted controlled empirical experiments to verify their effectiveness. In addition, our simulator team made it to the semi-finals of the RoboCup-97 competition, in which 29 teams participated. It achieved a total score of 67–9 over six different games, and successfully demonstrated its flexible teamwork structure and inter-agent communication.

IROS Conference 1999 Conference Paper

What we learned from RoboCup-97 and RoboCup-98

• Minoru Asada
• Sho'ji Suzuki
• Manuela Veloso
• Gerhard K. Kraetzschmar
• Hiroaki Kitano

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.

ICAPS Conference 1998 Conference Paper

Planning, Execution and Learning in a Robotic Agent

• Karen Zita Haigh
• Manuela Veloso

This paper presents r, he completeintegrated planning, executing and learning robotic agent ROGUE. Wedescribe ROGUE’S task planner that interleaves high-level task planning with real world robot execution. It supports multiple, asynchronous goMs, suspends and interrupts tasks, madmonitors and compensates for failure. Wepresent a general approach for learning situation-dependent rides from execution, which correlates environmentalfeatures with learning opportunities: thereby detecting patterns and allowing planners to predict and avoid falhlres. Wepresent two implementations of the general learning approach, in the robot’s path planner, and in tim task planner. Wepresent empirical data to showthe effectiveness of RoGuE’s novellearning approach. ¯ "¯ ": "i: i: """ i ":... ¯:.: __ ¯.::..:::..i i.. ": ’. ’.:.......:.:.:.:.:<¢

IROS Conference 1998 Conference Paper

Playing soccer with legged robots

• Manuela Veloso
• William T. B. Uther
• Masahiro Fujita 0002
• Minoru Asada
• Hiroaki Kitano

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.

ICAPS Conference 1998 Conference Paper

Rationale-Based Monitoring for Planning in Dynamic Environments

• Manuela Veloso
• Martha E. Pollack
• Michael T. Cox

Wedescribe a framework for planning in dynamic environments. A central question is how to focus the sensing performed by such a system, so that it responds appropriately to relevant changes, but does not attempt to monitor all the changesthat could possibly occur in the world. To achieve the required balance, we introduce rationale. based monitors, whichrepresent the features of the world state that are included in the plan rationale, i. e., the reasons for the plannln~ decisions so far made. Rationalebased monitors capture information both about the plan currently under developmentand the alternative choices that were found but not pursued. Wediscuss the plan transformations that mayresult from the firing of a rationale-based monitor, for examplewhenan alternative choice is detected. Wehave implemented the generation of and response to rationale-based monitoring within the Prodigy planner, and we describe experimentsthat showthe feasibility of our approach.

ICRA Conference 1998 Conference Paper

Reactive Visual Control of Multiple Non-Holonomic Robotic Agents

• Kwun Han
• Manuela Veloso

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.

IJCAI Conference 1997 Conference Paper

The RoboCup Synthetic Agent Challenge

• Hiroaki Kitano
• Milind Tambe
• Peter Stone
• Manuela Veloso
• Silvia Coradeschi
• Eiichi Osawa
• Hitoshi Matsubara
• ltsuki Noda

RoboCup Challenge offers a set of challenges for intelligent agent researchers using a friendly competition in a dynamic, real-time, multiagent domain. While RoboCup in general envisions longer range challenges over the next few decades, RoboCup Challenge presents three specific challenges for the next two years: (i) learning of individual agents and teams; (ii) multi-agent team planning and plan-execution in service of teamwork; and (iii) opponent modeling. RoboCup Challenge provides a novel opportunity for machine learning, planning, and multi-agent researchers it not only supplies a concrete domain to evalute their techniques, but also challenges researchers to evolve these techniques to face key constraints fundamental to this domain: real-time, uncertainty, and teamwork.

IROS Conference 1996 Conference Paper

Interleaving planning and robot execution for asynchronous user requests

• Karen Zita Haigh
• Manuela Veloso

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.

NeurIPS Conference 1995 Conference Paper

Beating a Defender in Robotic Soccer: Memory-Based Learning of a Continuous Function

• Peter Stone
• Manuela Veloso

Learning how to adjust to an opponent's position is critical to the success of having intelligent agents collaborating towards the achievement of specific tasks in unfriendly environments. This pa(cid: 173) per describes our work on a Memory-based technique for to choose an action based on a continuous-valued state attribute indicating the position of an opponent. We investigate the question of how an agent performs in nondeterministic variations of the training situ(cid: 173) ations. Our experiments indicate that when the random variations fall within some bound of the initial training, the agent performs better with some initial training rather than from a tabula-rasa.

ICAPS Conference 1994 Conference Paper

Linkability: Examining Causal Link Commitments in Partial-order Planning

• Manuela Veloso
• Jim Blythe

Recently, several researchers have demonstrated domains where partially-ordered planners outperform totally-ordered planners. In (Barrett &Weld1994), Barrett and Weldbuild a series of artificial domains exploring the concepts of trivial and laborious serialisabillty, in whicha partially-ordered planner, SNLP, consistently outperformstwo totally-ordered planners. In this paper, we demonstrate that totally-ordered planners sometimeshave an adv~tage over partiallyordered planners. Wedescribe a series of domains in which PRODIGY4. 0 consistently outperforms SNIP, and introducethe conceptof linkability to characterize the class of domainsfor whichthis happens. Linkability highlights the fact that partially-ordered planners committo causal links in much the same way that totally-ordered planners commito step ordering.

ICAPS Conference 1994 Conference Paper

The Need for Different Domain-independent Heuristics

• Peter Stone 0001
• Manuela Veloso
• Jim Blythe

PRODIGY’s planning algorithm uses domain-independent search heuristics. In this paper, we support our that there is no ~ search heuristic that performs more efficiently than others for all problems or in all domains. The paper presents three diIFerent domaln-independent search heuristics of increasing complexity. Werun PRODIGY with these heuristics in a series of artificial domms(introduced in (Barrett &Weld1994)) wherein fact one of the heuristics performs more eBicient]y than the others. However, we introduce an additional simple domainwhere the apparently worst heuristic outperforms the other two. The results we obtained in our empirical experiments lead to the main conclusion of this paper: p]~-ming algorithms need to use different search heuristics in difereat domains. Wecoac]ude the paper by advocating the need to learn the correspondencebetween particular domaincharacteristics and specific search heuristics for planning efficiently in complexdomains.