Arrow Research search

Author name cluster

Julie Shah

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

49 papers
2 author rows

Possible papers

49

HAXP Workshop 2025 Workshop Paper

A Collaborative Numeric Task Planning Framework based on Constraint Translations using LLMs

  • Anthony Favier
  • Ngoc La
  • Pulkit Verma
  • Julie Shah

Automated planning systems require formal constraint specifications that create significant barriers for domain experts not familiar with those formal specifications, thereby limiting the practical adoption of powerful planning tools in collaborative planning settings. To overcome this challenge, we propose an LLM-based pipeline to translate human natural language constraints into formal hard-trajectory constraints. The initial user input is first refined and decomposed into more explicit natural language constraints, both preparing constraints for formal encoding and offering a chance for the human to review and correct any misinterpretation. Then, the decomposed constraints are encoded into PDDL3. By integrating this with an automated planner, a graphical interface, and PDSim, we created a closed loop where the human gets plan simulations as feedback to their natural language constraints. This innovative collaborative planning framework enables users to leverage their intuition and expertise to intuitively guide automated planning without time-consuming programming expert interventions. Through an ablation study, we demonstrate how our approach significantly improves the syntax and semantic accuracy of the translations compared to direct LLM translations. Our results demonstrate the potential of collaborative planning without technical expert interventions for higher-quality automated solving. On the other hand, our negative results seem to highlight the limitations of using PDDL3 constraints to leverage human high-level guidance as we expected, raising interesting reflections and potential discussions.

PDF

ICRA Conference 2025 Conference Paper

Inference-Time Policy Steering Through Human Interactions

  • Yanwei Wang
  • Lirui Wang
  • Yilun Du
  • Balakumar Sundaralingam
  • Xuning Yang
  • Yu-Wei Chao
  • Claudia Pérez-D'Arpino
  • Dieter Fox

Generative policies trained with human demonstrations can autonomously accomplish multimodal, longhorizon tasks. However, during inference, humans are often removed from the policy execution loop, limiting the ability to guide a pre-trained policy towards a specific sub-goal or trajectory shape among multiple predictions. Naive human intervention may inadvertently exacerbate distribution shift, leading to constraint violations or execution failures. To better align policy output with human intent without inducing out-of-distribution errors, we propose an Inference-Time Policy Steering (ITPS) framework that leverages human interactions to bias the generative sampling process, rather than finetuning the policy on interaction data. We evaluate ITPS across three simulated and real-world benchmarks, testing three forms of human interaction and associated alignment distance metrics. Among six sampling strategies, our proposed stochastic sampling with diffusion policy achieves the best trade-off between alignment and distribution shift. Videos are available at https://yanweiw.github.io/itps/.

Details

IROS Conference 2025 Conference Paper

Versatile Demonstration Interface: Toward More Flexible Robot Demonstration Collection

  • Michael Hagenow
  • Dimosthenis Kontogiorgos
  • Yanwei Wang
  • Julie Shah

Previous methods for Learning from Demonstration leverage several approaches for a human to teach motions to a robot, including teleoperation, kinesthetic teaching, and natural demonstrations. However, little previous work has explored more general interfaces that allow for multiple demonstration types. Given the varied preferences of human demonstrators and task characteristics, a flexible tool that enables multiple demonstration types could be crucial for broader robot skill training. In this work, we propose Versatile Demonstration Interface (VDI), an attachment for collaborative robots that simplifies the collection of three common types of demonstrations. Designed for flexible deployment in industrial settings, our tool requires no additional instrumentation of the environment. Our prototype interface captures human demonstrations through a combination of vision, force sensing, and state tracking (e. g. , through the robot proprioception or AprilTag tracking). Through a user study where we deployed our prototype VDI at a local manufacturing innovation center with manufacturing experts, we demonstrated VDI in representative industrial tasks. Interactions from our study highlight the practical value of VDI’s varied demonstration types, expose a range of industrial use cases for VDI, and provide insights for future tool design.

Details

ICLR Conference 2024 Conference Paper

Grounding Language Plans in Demonstrations Through Counterfactual Perturbations

  • Yanwei Wang
  • Tsun-Hsuan Wang
  • Jiayuan Mao
  • Michael Hagenow
  • Julie Shah

Grounding the common-sense reasoning of Large Language Models in physical domains remains a pivotal yet unsolved problem for embodied AI. Whereas prior works have focused on leveraging LLMs directly for planning in symbolic spaces, this work uses LLMs to guide the search of task structures and constraints implicit in multi-step demonstrations. Specifically, we borrow from manipulation planning literature the concept of mode families, which group robot configurations by specific motion constraints, to serve as an abstraction layer between the high-level language representations of an LLM and the low-level physical trajectories of a robot. By replaying a few human demonstrations with synthetic perturbations, we generate coverage over the demonstrations' state space with additional successful executions as well as counterfactuals that fail the task. Our explanation-based learning framework trains an end-to-end differentiable neural network to predict successful trajectories from failures and as a by-product learns classifiers that ground low-level states and images in mode families without dense labeling. The learned grounding classifiers can further be used to translate language plans into reactive policies in the physical domain in an interpretable manner. We show our approach improves the interpretability and reactivity of imitation learning through 2D navigation and simulated and real robot manipulation tasks. Website: https://yanweiw.github.io/glide/

Details

ICLR Conference 2024 Conference Paper

Learning with Language-Guided State Abstractions

  • Andi Peng
  • Ilia Sucholutsky
  • Belinda Z. Li
  • Theodore R. Sumers
  • Thomas L. Griffiths 0001
  • Jacob Andreas
  • Julie Shah

We describe a framework for using natural language to design state abstractions for imitation learning. Generalizable policy learning in high-dimensional observation spaces is facilitated by well-designed state representations, which can surface important features of an environment and hide irrelevant ones. These state representations are typically manually specified, or derived from other labor-intensive labeling procedures. Our method, LGA (\textit{language-guided abstraction}), uses a combination of natural language supervision and background knowledge from language models (LMs) to automatically build state representations tailored to unseen tasks. In LGA, a user first provides a (possibly incomplete) description of a target task in natural language; next, a pre-trained LM translates this task description into a state abstraction function that masks out irrelevant features; finally, an imitation policy is trained using a small number of demonstrations and LGA-generated abstract states. Experiments on simulated robotic tasks show that LGA yields state abstractions similar to those designed by humans, but in a fraction of the time, and that these abstractions improve generalization and robustness in the presence of spurious correlations and ambiguous specifications. We illustrate the utility of the learned abstractions on mobile manipulation tasks with a Spot robot.

Details

ICRA Conference 2024 Conference Paper

Object Permanence Filter for Robust Tracking with Interactive Robots

  • Shaoting Peng
  • Margaret X. Wang
  • Julie Shah
  • Nadia Figueroa

Object permanence, which refers to the concept that objects continue to exist even when they are no longer perceivable through the senses, is a crucial aspect of human cognitive development. In this work, we seek to incorporate this understanding into interactive robots by proposing a set of assumptions and rules to represent object permanence in multi-object, multi-agent interactive scenarios. We integrate these rules into the particle filter, resulting in the Object Permanence Filter (OPF). For multi-object scenarios, we propose an ensemble of K interconnected OPFs, where each filter predicts plausible object tracks that are resilient to missing, noisy, and kinematically or dynamically infeasible measurements, thus bringing perceptional robustness. Through several interactive scenarios, we demonstrate that the proposed OPF approach provides robust tracking in human-robot interactive tasks agnostic to measurement type, even in the presence of prolonged and complete occlusion. Webpage: https://opfilter.github.io/.

Details

ICML Conference 2023 Conference Paper

Diagnosis, Feedback, Adaptation: A Human-in-the-Loop Framework for Test-Time Policy Adaptation

  • Andi Peng
  • Aviv Netanyahu
  • Mark K. Ho
  • Tianmin Shu
  • Andreea Bobu
  • Julie Shah
  • Pulkit Agrawal 0001

Policies often fail at test-time due to distribution shifts —changes in the state and reward that occur when an end user deploys the policy in environments different from those seen in training. Data augmentation can help models be more robust to such shifts by varying specific concepts in the state, e. g. object color, that are task-irrelevant and should not impact desired actions. However, designers training the agent don’t often know which concepts are irrelevant a priori. We propose a human-in-the-loop framework to leverage feedback from the end user to quickly identify and augment task-irrelevant visual state concepts. Our framework generates counterfactual demonstrations that allow users to quickly isolate shifted state concepts and identify if they should not impact the desired task, and can therefore be augmented using existing actions. We present experiments validating our full pipeline on discrete and continuous control tasks with real human users. Our method better enables users to (1) understand agent failure, (2) improve sample efficiency of demonstrations required for finetuning, and (3) adapt the agent to their desired reward.

Details

AAAI Conference 2023 Conference Paper

The Perils of Trial-and-Error Reward Design: Misdesign through Overfitting and Invalid Task Specifications

  • Serena Booth
  • W. Bradley Knox
  • Julie Shah
  • Scott Niekum
  • Peter Stone
  • Alessandro Allievi

In reinforcement learning (RL), a reward function that aligns exactly with a task's true performance metric is often necessarily sparse. For example, a true task metric might encode a reward of 1 upon success and 0 otherwise. The sparsity of these true task metrics can make them hard to learn from, so in practice they are often replaced with alternative dense reward functions. These dense reward functions are typically designed by experts through an ad hoc process of trial and error. In this process, experts manually search for a reward function that improves performance with respect to the task metric while also enabling an RL algorithm to learn faster. This process raises the question of whether the same reward function is optimal for all algorithms, i.e., whether the reward function can be overfit to a particular algorithm. In this paper, we study the consequences of this wide yet unexamined practice of trial-and-error reward design. We first conduct computational experiments that confirm that reward functions can be overfit to learning algorithms and their hyperparameters. We then conduct a controlled observation study which emulates expert practitioners' typical experiences of reward design, in which we similarly find evidence of reward function overfitting. We also find that experts' typical approach to reward design---of adopting a myopic strategy and weighing the relative goodness of each state-action pair---leads to misdesign through invalid task specifications, since RL algorithms use cumulative reward rather than rewards for individual state-action pairs as an optimization target. Code, data: github.com/serenabooth/reward-design-perils

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Towards Collaborative Plan Acquisition through Theory of Mind Modeling in Situated Dialogue

  • Cristian-Paul Bara
  • Ziqiao Ma
  • Yingzhuo Yu
  • Julie Shah
  • Joyce Chai

Collaborative tasks often begin with partial task knowledge and incomplete plans from each partner. To complete these tasks, partners need to engage in situated communication with their partners and coordinate their partial plans towards a complete plan to achieve a joint task goal. While such collaboration seems effortless in a human-human team, it is highly challenging for human-AI collaboration. To address this limitation, this paper takes a step towards Collaborative Plan Acquisition, where humans and agents strive to learn and communicate with each other to acquire a complete plan for joint tasks. Specifically, we formulate a novel problem for agents to predict the missing task knowledge for themselves and for their partners based on rich perceptual and dialogue history. We extend a situated dialogue benchmark for symmetric collaborative tasks in a 3D blocks world and investigate computational strategies for plan acquisition. Our empirical results suggest that predicting the partner's missing knowledge is a more viable approach than predicting one's own. We show that explicit modeling of the partner's dialogue moves and mental states produces improved and more stable results than without. These results provide insight for future AI agents that can predict what knowledge their partner is missing and, therefore, can proactively communicate such information to help the partner acquire such missing knowledge toward a common understanding of joint tasks.

PDF Details DOI

ICLR Conference 2023 Conference Paper

Towards Interpretable Deep Reinforcement Learning with Human-Friendly Prototypes

  • Eoin M. Kenny
  • Mycal Tucker
  • Julie Shah

Despite recent success of deep learning models in research settings, their application in sensitive domains remains limited because of their opaque decision-making processes. Taking to this challenge, people have proposed various eXplainable AI (XAI) techniques designed to calibrate trust and understandability of black-box models, with the vast majority of work focused on supervised learning. Here, we focus on making an "interpretable-by-design" deep reinforcement learning agent which is forced to use human-friendly prototypes in its decisions, thus making its reasoning process clear. Our proposed method, dubbed Prototype-Wrapper Network (PW-Net), wraps around any neural agent backbone, and results indicate that it does not worsen performance relative to black-box models. Most importantly, we found in a user study that PW-Nets supported better trust calibration and task performance relative to standard interpretability approaches and black-boxes.

Details

AAAI Conference 2022 Conference Paper

Do Feature Attribution Methods Correctly Attribute Features?

  • Yilun Zhou
  • Serena Booth
  • Marco Tulio Ribeiro
  • Julie Shah

Feature attribution methods are popular in interpretable machine learning. These methods compute the attribution of each input feature to represent its importance, but there is no consensus on the definition of “attribution”, leading to many competing methods with little systematic evaluation, complicated in particular by the lack of ground truth attribution. To address this, we propose a dataset modification procedure to induce such ground truth. Using this procedure, we evaluate three common methods: saliency maps, attentions and rationales. We identify several deficiencies and add new perspectives to the growing body of evidence questioning the correctness and reliability of these methods applied on datasets in the wild. We further discuss possible avenues for remedy and recommend new attribution methods to be tested against ground truth before deployment. The code and appendix are available at https: //yilunzhou. github. io/feature-attribution-evaluation/.

PDF Details

ICML Conference 2022 Conference Paper

Prototype Based Classification from Hierarchy to Fairness

  • Mycal Tucker
  • Julie Shah

Artificial neural nets can represent and classify many types of high-dimensional data but are often tailored to particular applications – e. g. , for “fair” or “hierarchical” classification. Once an architecture has been selected, it is often difficult for humans to adjust models for a new task; for example, a hierarchical classifier cannot be easily transformed into a fair classifier that shields a protected field. Our contribution in this work is a new neural network architecture, the concept subspace network (CSN), which generalizes existing specialized classifiers to produce a unified model capable of learning a spectrum of multi-concept relationships. We demonstrate that CSNs reproduce state-of-the-art results in fair classification when enforcing concept independence, may be transformed into hierarchical classifiers, or may even reconcile fairness and hierarchy within a single classifier. The CSN is inspired by and matches the performance of existing prototype-based classifiers that promote interpretability.

Details

AAAI Conference 2021 Conference Paper

Bayes-TrEx: a Bayesian Sampling Approach to Model Transparency by Example

  • Serena Booth
  • Yilun Zhou
  • Ankit Shah
  • Julie Shah

Post-hoc explanation methods are gaining popularity for interpreting, understanding, and debugging neural networks. Most analyses using such methods explain decisions in response to inputs drawn from the test set. However, the test set may have few examples that trigger some model behaviors, such as high-confidence failures or ambiguous classifications. To address these challenges, we introduce a flexible model inspection framework: BAYES-TREX. Given a data distribution, BAYES-TREX finds in-distribution examples which trigger a specified prediction confidence. We demonstrate several use cases of BAYES-TREX, including revealing highly con- fident (mis)classifications, visualizing class boundaries via ambiguous examples, understanding novel-class extrapolation behavior, and exposing neural network overconfidence. We use BAYES-TREX to study classifiers trained on CLEVR, MNIST, and Fashion-MNIST, and we show that this framework enables more flexible holistic model analysis than just inspecting the test set. Code and supplemental material are available at https: //github. com/serenabooth/Bayes-TrEx.

PDF Details

ICRA Conference 2021 Conference Paper

Reactive Task and Motion Planning under Temporal Logic Specifications

  • Shen Li 0003
  • Daehyung Park
  • Yoonchang Sung
  • Julie Shah
  • Nicholas Roy

We present a task-and-motion planning (TAMP) algorithm robust against a human operator's cooperative or adversarial interventions. Interventions often invalidate the current plan and require replanning on the fly. Replanning can be computationally expensive and often interrupts seamless task execution. We introduce a dynamically reconfigurable planning methodology with behavior tree-based control strategies toward reactive TAMP, which takes the advantage of previous plans and incremental graph search during temporal logic-based reactive synthesis. Our algorithm also shows efficient recovery functionalities that minimize the number of replanning steps. Finally, our algorithm produces a robust, efficient, and complete TAMP solution. Our experimental results show the algorithm results in superior manipulation performance in both simulated and real-world tasks.

Details

JAIR Journal 2020 Journal Article

Blind Spot Detection for Safe Sim-to-Real Transfer

  • Ramya Ramakrishnan
  • Ece Kamar
  • Debadeepta Dey
  • Eric Horvitz
  • Julie Shah

Agents trained in simulation may make errors when performing actions in the real world due to mismatches between training and execution environments. These mistakes can be dangerous and difficult for the agent to discover because the agent is unable to predict them a priori. In this work, we propose the use of oracle feedback to learn a predictive model of these blind spots in order to reduce costly errors in real-world applications. We focus on blind spots in reinforcement learning (RL) that occur due to incomplete state representation: when the agent lacks necessary features to represent the true state of the world, and thus cannot distinguish between numerous states. We formalize the problem of discovering blind spots in RL as a noisy supervised learning problem with class imbalance. Our system learns models for predicting blind spots within unseen regions of the state space by combining techniques for label aggregation, calibration, and supervised learning. These models take into consideration noise emerging from different forms of oracle feedback, including demonstrations and corrections. We evaluate our approach across two domains and demonstrate that it achieves higher predictive performance than baseline methods, and also that the learned model can be used to selectively query an oracle at execution time to prevent errors. We also empirically analyze the biases of various feedback types and how these biases influence the discovery of blind spots. Further, we include analyses of our approach that incorporate relaxed initial optimality assumptions. (Interestingly, relaxing the assumptions of an optimal oracle and an optimal simulator policy helped our models to perform better.) We also propose extensions to our method that are intended to improve performance when using corrections and demonstrations data.

PDF Details DOI

IROS Conference 2019 Conference Paper

A Taxonomy for Characterizing Modes of Interactions in Goal-driven, Human-robot Teams

  • Priyam Parashar
  • Lindsay M. Sanneman
  • Julie Shah
  • Henrik I. Christensen

As robots and other autonomous agents are increasingly incorporated into complex domains, characterizing interaction within heterogeneous teams that include both humans and machines becomes more necessary. Previous literature has addressed the task of characterizing human-robot interaction from different perspectives and in multiple contexts. However, the numerous factors behind interaction work in conjunction, and the insights gained from one perspective can inadvertently affect another, creating a need for unification of these taxonomies and frameworks within an overarching taxonomy that systematically defines these relationships. In this paper we review existing taxonomies related to human-robot interaction, the behavioral sciences, and social and algorithmic taxonomies, and propose an overarching ontology for the factors from these works. We identify three main components characterizing the structure of an interaction (environment, task, and team), and structure them over two levels: contextual factors and factors driven by local dynamics. Finally, we present an analysis of how these factors affect decisions about levels of robot automation and level of information abstraction in an interaction, and discuss curent gaps in the literature that can motivate future research.

Details

ICRA Conference 2019 Conference Paper

Activity recognition in manufacturing: The roles of motion capture and sEMG+inertial wearables in detecting fine vs. gross motion

  • Alyssa Kubota
  • Tariq Iqbal
  • Julie Shah
  • Laurel D. Riek

In safety-critical environments, robots need to reliably recognize human activity to be effective and trust-worthy partners. Since most human activity recognition (HAR) approaches rely on unimodal sensor data (e. g. motion capture or wearable sensors), it is unclear how the relationship between the sensor modality and motion granularity (e. g. gross or fine) of the activities impacts classification accuracy. To our knowledge, we are the first to investigate the efficacy of using motion capture as compared to wearable sensor data for recognizing human motion in manufacturing settings. We introduce the UCSD-MIT Human Motion dataset, composed of two assembly tasks that entail either gross or fine-grained motion. For both tasks, we compared the accuracy of a Vicon motion capture system to a Myo armband using three widely used HAR algorithms. We found that motion capture yielded higher accuracy than the wearable sensor for gross motion recognition (up to 36. 95%), while the wearable sensor yielded higher accuracy for fine-grained motion (up to 28. 06%). These results suggest that these sensor modalities are complementary, and that robots may benefit from systems that utilize multiple modalities to simultaneously, but independently, detect gross and fine-grained motion. Our findings will help guide researchers in numerous fields of robotics including learning from demonstration and grasping to effectively choose sensor modalities that are most suitable for their applications.

Details

IJCAI Conference 2019 Conference Paper

Bayesian Inference of Linear Temporal Logic Specifications for Contrastive Explanations

  • Joseph Kim
  • Christian Muise
  • Ankit Shah
  • Shubham Agarwal
  • Julie Shah

Temporal logics are useful for providing concise descriptions of system behavior, and have been successfully used as a language for goal definitions in task planning. Prior works on inferring temporal logic specifications have focused on "summarizing" the input dataset - i. e. , finding specifications that are satisfied by all plan traces belonging to the given set. In this paper, we examine the problem of inferring specifications that describe temporal differences between two sets of plan traces. We formalize the concept of providing such contrastive explanations, then present BayesLTL - a Bayesian probabilistic model for inferring contrastive explanations as linear temporal logic (LTL) specifications. We demonstrate the robustness and scalability of our model for inferring accurate specifications from noisy data and across various benchmark planning domains.

PDF Details

IJCAI Conference 2019 Conference Paper

Evaluating the Interpretability of the Knowledge Compilation Map: Communicating Logical Statements Effectively

  • Serena Booth
  • Christian Muise
  • Julie Shah

Knowledge compilation techniques translate propositional theories into equivalent forms to increase their computational tractability. But, how should we best present these propositional theories to a human? We analyze the standard taxonomy of propositional theories for relative interpretability across three model domains: highway driving, emergency triage, and the chopsticks game. We generate decision-making agents which produce logical explanations for their actions and apply knowledge compilation to these explanations. Then, we evaluate how quickly, accurately, and confidently users comprehend the generated explanations. We find that domain, formula size, and negated logical connectives significantly affect comprehension while formula properties typically associated with interpretability are not strong predictors of human ability to comprehend the theory.

PDF Details

ICRA Conference 2019 Conference Paper

Fast Online Segmentation of Activities from Partial Trajectories

  • Tariq Iqbal
  • Shen Li 0003
  • Christopher K. Fourie
  • Bradley Hayes
  • Julie Shah

Augmenting a robot with the capacity to understand the activities of the people it collaborates with in order to then label and segment those activities allows the robot to generate an efficient and safe plan for performing its own actions. In this work, we introduce an online activity segmentation algorithm that can detect activity segments by processing a partial trajectory. We model the transitions through activities as a hidden Markov model, which runs online by implementing an efficient particle-filtering approach to infer the maximum a posteriori estimate of the activity sequence. This process is complemented by an online search process to refine activity segments using task model information about the partial order of activities. We evaluated our algorithm by comparing its performance to two state-of-the-art activity segmentation algorithms on three human activity datasets. The proposed algorithm improved activity segmentation accuracy across all three datasets compared with the other two approaches, with a range from 11. 3% to 65. 5%, and could accurately recognize an activity through observation alone for 31. 6% of the initial trajectory of that activity, on average. We also implemented the algorithm onto an industrial mobile robot during an automotive assembly task in which the robot tracked a human worker's progress and provided the worker with the correct materials at the appropriate time.

Details

AAAI Conference 2019 Conference Paper

Overcoming Blind Spots in the Real World: Leveraging Complementary Abilities for Joint Execution

  • Ramya Ramakrishnan
  • Ece Kamar
  • Besmira Nushi
  • Debadeepta Dey
  • Julie Shah
  • Eric Horvitz

Simulators are being increasingly used to train agents before deploying them in real-world environments. While training in simulation provides a cost-effective way to learn, poorly modeled aspects of the simulator can lead to costly mistakes, or blind spots. While humans can help guide an agent towards identifying these error regions, humans themselves have blind spots and noise in execution. We study how learning about blind spots of both can be used to manage hand-off decisions when humans and agents jointly act in the real-world in which neither of them are trained or evaluated fully. The formulation assumes that agent blind spots result from representational limitations in the simulation world, which leads the agent to ignore important features that are relevant for acting in the open world. Our approach for blind spot discovery combines experiences collected in simulation with limited human demonstrations. The first step applies imitation learning to demonstration data to identify important features that the human is using but that the agent is missing. The second step uses noisy labels extracted from action mismatches between the agent and the human across simulation and demonstration data to train blind spot models. We show through experiments on two domains that our approach is able to learn a succinct representation that accurately captures blind spot regions and avoids dangerous errors in the real world through transfer of control between the agent and the human.

PDF Details

ICRA Conference 2019 Conference Paper

Safe and Efficient High Dimensional Motion Planning in Space-Time with Time Parameterized Prediction

  • Shen Li 0003
  • Julie Shah

In this work, we propose an algorithm that can plan safe and efficient robot trajectories in real time, given time-parameterized motion predictions, in order to avoid fast-moving obstacles in human-robot collaborative environments. Our algorithm is able to reduce the robot configuration space and the time domain significantly by constructing a Lazy Safe Interval Probabilistic Roadmap based on a pre-planned path. The algorithm then plans efficient obstacle-avoidance strategies within the space-time roadmap. We benchmarked our algorithm by evaluating the performance of a simulated 6-joint manipulator attempting to avoid a quickly moving human hand, using a dataset collected from human experiments. We compared our algorithm's performance with those of 8 variations of prior state-of-the-art planners. Results from this empirical evaluation indicate that our method generated safe plans in 97. 5% of the evaluated situations, achieved a planning speed 30 times faster than the benchmarked methods that planned in the time domain without space reduction, and accomplished the minimal solution execution time among the benchmarked planners with a similar planning speed.

Details

NeurIPS Conference 2018 Conference Paper

Bayesian Inference of Temporal Task Specifications from Demonstrations

  • Ankit Shah
  • Pritish Kamath
  • Julie Shah
  • Shen Li

When observing task demonstrations, human apprentices are able to identify whether a given task is executed correctly long before they gain expertise in actually performing that task. Prior research into learning from demonstrations (LfD) has failed to capture this notion of the acceptability of an execution; meanwhile, temporal logics provide a flexible language for expressing task specifications. Inspired by this, we present Bayesian specification inference, a probabilistic model for inferring task specification as a temporal logic formula. We incorporate methods from probabilistic programming to define our priors, along with a domain-independent likelihood function to enable sampling-based inference. We demonstrate the efficacy of our model for inferring true specifications with over 90% similarity between the inferred specification and the ground truth, both within a synthetic domain and a real-world table setting task.

PDF Details

AAMAS Conference 2018 Conference Paper

Discovering Blind Spots in Reinforcement Learning

  • Ramya Ramakrishnan
  • Ece Kamar
  • Debadeepta Dey
  • Julie Shah
  • Eric Horvitz

Agents trained in simulation may make errors in the real world due to mismatches between training and execution environments. These mistakes can be dangerous and difficult to discover because the agent cannot predict them a priori. We propose using oracle feedback to learn a predictive model of these blind spots to reduce costly errors in real-world applications. We focus on blind spots in reinforcement learning (RL) that occur due to incomplete state representation: The agent does not have the appropriate features to represent the true state of the world and thus cannot distinguish among numerous states. We formalize the problem of discovering blind spots in RL as a noisy supervised learning problem with class imbalance. We learn models to predict blind spots in unseen regions of the state space by combining techniques for label aggregation, calibration, and supervised learning. The models take into consideration noise emerging from different forms of oracle feedback, including demonstrations and corrections. We evaluate our approach on two domains and show that it achieves higher predictive performance than baseline methods, and that the learned model can be used to selectively query an oracle at execution time to prevent errors. We also empirically analyze the biases of various feedback types and how they influence the discovery of blind spots.

PDF

JAIR Journal 2018 Journal Article

Human-Machine Collaborative Optimization via Apprenticeship Scheduling

  • Matthew Gombolay
  • Reed Jensen
  • Jessica Stigile
  • Toni Golen
  • Neel Shah
  • Sung-Hyun Son
  • Julie Shah

Coordinating agents to complete a set of tasks with intercoupled temporal and resource constraints is computationally challenging, yet human domain experts can solve these difficult scheduling problems using paradigms learned through years of apprenticeship. A process for manually codifying this domain knowledge within a computational framework is necessary to scale beyond the "single-expert, single-trainee" apprenticeship model. However, human domain experts often have difficulty describing their decision-making processes. We propose a new approach for capturing this decision-making process through counterfactual reasoning in pairwise comparisons. Our approach is model-free and does not require iterating through the state space. We demonstrate that this approach accurately learns multifaceted heuristics on a synthetic and real world data sets. We also demonstrate that policies learned from human scheduling demonstration via apprenticeship learning can substantially improve the efficiency of schedule optimization. We employ this human-machine collaborative optimization technique on a variant of the weapon-to-target assignment problem. We demonstrate that this technique generates optimal solutions up to 9.5 times faster than a state-of-the-art optimization algorithm.

PDF Details DOI

ICRA Conference 2017 Conference Paper

A multiple-predictor approach to human motion prediction

  • Przemyslaw A. Lasota
  • Julie Shah

The ability to accurately predict human motion is imperative for any human-robot interaction application in which the human and robot interact in close proximity to one another. Although a variety of human motion prediction approaches have already been developed, they are often designed for specific types of tasks or motions, and thus do not generalize well. Furthermore, it is not always obvious which of these methods is appropriate for a given task, making human motion prediction difficult to implement in practice. We address this problem by introducing a multiple-predictor system (MPS) for human motion prediction. In our approach, the system learns directly from task data in order to determine the most favorable parameters for each implemented prediction method and which combination of these predictors to use. Our implementation consists of three complementary methods: velocity-based position projection, time series classification, and sequence prediction. We describe the process of forming the MPS and our evaluation of its performance against the individual methods in terms of accuracy of predictions of human position over a range of look-ahead time values. We report that our method leads to a reduction in mean error of 18. 5%, 28. 9%, and 37. 3% when compared with the three individual methods, respectively.

Details

ICRA Conference 2017 Conference Paper

C-LEARN: Learning geometric constraints from demonstrations for multi-step manipulation in shared autonomy

  • Claudia Pérez-D'Arpino
  • Julie Shah

Learning from demonstrations has been shown to be a successful method for non-experts to teach manipulation tasks to robots. These methods typically build generative models from demonstrations and then use regression to reproduce skills. However, this approach has limitations to capture hard geometric constraints imposed by the task. On the other hand, while sampling and optimization-based motion planners exist that reason about geometric constraints, these are typically carefully hand-crafted by an expert. To address this technical gap, we contribute with C-LEARN, a method that learns multi-step manipulation tasks from demonstrations as a sequence of keyframes and a set of geometric constraints. The system builds a knowledge base for reaching and grasping objects, which is then leveraged to learn multi-step tasks from a single demonstration. C-LEARN supports multi-step tasks with multiple end effectors; reasons about SE(3) volumetric and CAD constraints, such as the need for two axes to be parallel; and offers a principled way to transfer skills between robots with different kinematics. We embed the execution of the learned tasks within a shared autonomy framework, and evaluate our approach by analyzing the success rate when performing physical tasks with a dual-arm Optimas robot, comparing the contribution of different constraints models, and demonstrating the ability of C-LEARN to transfer learned tasks by performing them with a legged dual-arm Atlas robot in simulation.

Details

AAAI Conference 2017 Conference Paper

Collaborative Planning with Encoding of Users’ High-Level Strategies

  • Joseph Kim
  • Christopher Banks
  • Julie Shah

The generation of near-optimal plans for multi-agent systems with numerical states and temporal actions is computationally challenging. Current off-the-shelf planners can take a very long time before generating a near-optimal solution. In an effort to reduce plan computation time, increase the quality of the resulting plans, and make them more interpretable by humans, we explore collaborative planning techniques that actively involve human users in plan generation. Specifically, we explore a framework in which users provide high-level strategies encoded as soft preferences to guide the low-level search of the planner. Through human subject experimentation, we empirically demonstrate that this approach results in statistically significant improvements to plan quality, without substantially increasing computation time. We also show that the resulting plans achieve greater similarity to those generated by humans with regard to the produced sequences of actions, as compared to plans that do not incorporate userprovided strategies.

PDF Details

ICRA Conference 2017 Conference Paper

Interpretable models for fast activity recognition and anomaly explanation during collaborative robotics tasks

  • Bradley Hayes
  • Julie Shah

In this paper, we present Rapid Activity Prediction Through Object-oriented Regression (RAPTOR), a scalable method for performing rapid, real-time activity recognition and prediction that achieves state-of-the-art classification accuracy on both a generic human activity dataset and two domain-specific collaborative robotics manufacturing datasets. Our approach is designed to be human-interpretable: able to provide explanations for its reasoning such that non-experts can better understand and improve its activity models. We incorporate methods to increase RAPTOR's resilience against confusion due to temporal variations, as well as against learning false correlations between features. We report full and partial trajectory classification results across three datasets and conclude by demonstrating our model's ability to provide interpretable explanations of its reasoning using outlier detection techniques.

Details

JAIR Journal 2017 Journal Article

Perturbation Training for Human-Robot Teams

  • Ramya Ramakrishnan
  • Chongjie Zhang
  • Julie Shah

In this work, we design and evaluate a computational learning model that enables a human-robot team to co-develop joint strategies for performing novel tasks that require coordination. The joint strategies are learned through "perturbation training," a human team-training strategy that requires team members to practice variations of a given task to help their team generalize to new variants of that task. We formally define the problem of human-robot perturbation training and develop and evaluate the first end-to-end framework for such training, which incorporates a multi-agent transfer learning algorithm, human-robot co-learning framework and communication protocol. Our transfer learning algorithm, Adaptive Perturbation Training (AdaPT), is a hybrid of transfer and reinforcement learning techniques that learns quickly and robustly for new task variants. We empirically validate the benefits of AdaPT through comparison to other hybrid reinforcement and transfer learning techniques aimed at transferring knowledge from multiple source tasks to a single target task. We also demonstrate that AdaPT's rapid learning supports live interaction between a person and a robot, during which the human-robot team trains to achieve a high level of performance for new task variants. We augment AdaPT with a co-learning framework and a computational bi-directional communication protocol so that the robot can co-train with a person during live interaction. Results from large-scale human subject experiments (n=48) indicate that AdaPT enables an agent to learn in a manner compatible with a human's own learning process, and that a robot undergoing perturbation training with a human results in a high level of team performance. Finally, we demonstrate that human-robot training using AdaPT in a simulation environment produces effective performance for a team incorporating an embodied robot partner.

PDF Details DOI

IJCAI Conference 2016 Conference Paper

Apprenticeship Scheduling: Learning to Schedule from Human Experts

  • Matthew Gombolay
  • Reed Jensen
  • Jessica Stigile
  • Sung-Hyun Son
  • Julie Shah

Coordinating agents to complete a set of tasks with intercoupled temporal and resource constraints is computationally challenging, yet human domain experts can solve these difficult scheduling problems using paradigms learned through years of apprenticeship. A process for manually codifying this domain knowledge within a computational framework is necessary to scale beyond the "single-expert, single-trainee apprenticeship model. However, human domain experts often have difficulty describing their decision-making processes, causing the codification of this knowledge to become laborious. We propose a new approach for capturing domain-expert heuristics through a pairwise ranking formulation. Our approach is model-free and does not require enumerating or iterating through a large state-space. We empirically demonstrate that this approach accurately learns multifaceted heuristics on both a synthetic data set incorporating job-shop scheduling and vehicle routing problems and a real-world data set consisting of demonstrations of experts solving a weapon-to-target assignment problem.

PDF Details

IROS Conference 2016 Conference Paper

Co-optimizing task and motion planning

  • Chongjie Zhang
  • Julie Shah

Solutions to robotic manipulation problems can be substantially improved through integrated task and motion planning. Existing approaches typically focus on satisfaction, finding a feasible solution, instead of optimization. We formulate large-scale robotic manipulation problems as multi-level optimization, incorporating task, action, and motion planning. We develop an integrated planning approach for solving this optimization problem and generating a combined motion plan for a robot to optimize a task-level objective. This approach utilizes a combinatorial search algorithm for task planning and incrementally exploits information from lower-level optimization to improve the high-level task plan. Empirical results show that this integrated approach not only significantly outperforms a traditional top-down approach in solution quality, but also avoids infeasible lower-level motion plans.

Details

AAAI Conference 2016 Conference Paper

ConTaCT: Deciding to Communicate during Time-Critical Collaborative Tasks in Unknown, Deterministic Domains

  • Vaibhav Unhelkar
  • Julie Shah

Communication between agents has the potential to improve team performance of collaborative tasks. However, communication is not free in most domains, requiring agents to reason about the costs and benefits of sharing information. In this work, we develop an online, decentralized communication policy, ConTaCT, that enables agents to decide whether or not to communicate during time-critical collaborative tasks in unknown, deterministic environments. Our approach is motivated by real-world applications, including the coordination of disaster response and search and rescue teams. These settings motivate a model structure that explicitly represents the world model as initially unknown but deterministic in nature, and that de-emphasizes uncertainty about action outcomes. Simulated experiments are conducted in which ConTaCT is compared to other multi-agent communication policies, and results indicate that ConTaCT achieves comparable task performance while substantially reducing communication overhead.

PDF Details

ICRA Conference 2016 Conference Paper

Towards manipulation planning for multiple interlinked deformable linear objects

  • Ankit J. Shah
  • Julie Shah

Manipulation of deformable linear objects (DLO) has potential applications in aerospace and automotive assembly. The current literature on planning for deformable objects focuses on a single DLO at a time. In this paper, we provide a problem formulation for attaching a set of interlinked DLOs to a support structure through a set of clamping points. We also present a prototype algorithm that generates a solution in terms of primitive manipulation actions. The algorithm guarantees that none of the interlink constraints are violated. Finally, we incorporate gravity in the computation of a DLO shape and propose a property linking geometrically similar cable shapes across the space of cable length and stiffness. This property allows for computation of solutions for unit length and scaling of the solutions to appropriate length, thus potentially making shape computations faster.

Details

ICRA Conference 2015 Conference Paper

Fast target prediction of human reaching motion for cooperative human-robot manipulation tasks using time series classification

  • Claudia Pérez-D'Arpino
  • Julie Shah

Interest in human-robot coexistence, in which humans and robots share a common work volume, is increasing in manufacturing environments. Efficient work coordination requires both awareness of the human pose and a plan of action for both human and robot agents in order to compute robot motion trajectories that synchronize naturally with human motion. In this paper, we present a data-driven approach that synthesizes anticipatory knowledge of both human motions and subsequent action steps in order to predict in real-time the intended target of a human performing a reaching motion. Motion-level anticipatory models are constructed using multiple demonstrations of human reaching motions. We produce a library of motions from human demonstrations, based on a statistical representation of the degrees of freedom of the human arm, using time series analysis, wherein each time step is encoded as a multivariate Gaussian distribution. We demonstrate the benefits of this approach through offline statistical analysis of human motion data. The results indicate a considerable improvement over prior techniques in early prediction, achieving 70% or higher correct classification on average for the first third of the trajectory (< 500msec). We also indicate proof-of-concept through the demonstration of a human-robot cooperative manipulation task performed with a PR2 robot. Finally, we analyze the quality of task-level anticipatory knowledge required to improve prediction performance early in the human motion trajectory.

Details

ICRA Conference 2015 Conference Paper

Human-robot co-navigation using anticipatory indicators of human walking motion

  • Vaibhav V. Unhelkar
  • Claudia Pérez-D'Arpino
  • Leia A. Stirling 0001
  • Julie Shah

Mobile, interactive robots that operate in human-centric environments need the capability to safely and efficiently navigate around humans. This requires the ability to sense and predict human motion trajectories and to plan around them. In this paper, we present a study that supports the existence of statistically significant biomechanical turn indicators of human walking motions. Further, we demonstrate the effectiveness of these turn indicators as features in the prediction of human motion trajectories. Human motion capture data is collected with predefined goals to train and test a prediction algorithm. Use of anticipatory features results in improved performance of the prediction algorithm. Lastly, we demonstrate the closed-loop performance of the prediction algorithm using an existing algorithm for motion planning within dynamic environments. The anticipatory indicators of human walking motion can be used with different prediction and/or planning algorithms for robotics; the chosen planning and prediction algorithm demonstrates one such implementation for human-robot co-navigation.

Details

NeurIPS Conference 2015 Conference Paper

Mind the Gap: A Generative Approach to Interpretable Feature Selection and Extraction

  • Been Kim
  • Julie Shah
  • Finale Doshi-Velez

We present the Mind the Gap Model (MGM), an approach for interpretable feature extraction and selection. By placing interpretability criteria directly into the model, we allow for the model to both optimize parameters related to interpretability and to directly report a global set of distinguishable dimensions to assist with further data exploration and hypothesis generation. MGM extracts distinguishing features on real-world datasets of animal features, recipes ingredients, and disease co-occurrence. It also maintains or improves performance when compared to related approaches. We perform a user study with domain experts to show the MGM's ability to help with dataset exploration.

PDF Details

AAAI Conference 2015 Conference Paper

On Fairness in Decision-Making under Uncertainty: Definitions, Computation, and Comparison

  • Chongjie Zhang
  • Julie Shah

The utilitarian solution criterion, which has been extensively studied in multi-agent decision making under uncertainty, aims to maximize the sum of individual utilities. However, as the utilitarian solution often discriminates against some agents, it is not desirable for many practical applications where agents have their own interests and fairness is expected. To address this issue, this paper introduces egalitarian solution criteria for sequential decision-making under uncertainty, which are based on the maximin principle. Motivated by different application domains, we propose four maximin fairness criteria and develop corresponding algorithms for computing their optimal policies. Furthermore, we analyze the connections between these criteria and discuss and compare their characteristics.

PDF Details

AAAI Conference 2015 Conference Paper

Scalable and Interpretable Data Representation for High-Dimensional, Complex Data

  • Been Kim
  • Kayur Patel
  • Afshin Rostamizadeh
  • Julie Shah

The majority of machine learning research has been focused on building models and inference techniques with sound mathematical properties and cutting edge performance. Little attention has been devoted to the development of data representation that can be used to improve a user’s ability to interpret the data and machine learning models to solve real-world problems. In this paper, we quantitatively and qualitatively evaluate an efficient, accurate and scalable feature-compression method using latent Dirichlet allocation for discrete data. This representation can effectively communicate the characteristics of high-dimensional, complex data points. We show that the improvement of a user’s interpretability through the use of a topic modeling-based compression technique is statistically significant, according to a number of metrics, when compared with other representations. Also, we find that this representation is scalable — it maintains alignment with human classification accuracy as an increasing number of data points are shown. In addition, the learned topic layer can semantically deliver meaningful information to users that could potentially aid human reasoning about data characteristics in connection with compressed topic space.

PDF Details

ICRA Conference 2014 Conference Paper

A summary of team MIT's approach to the virtual robotics challenge

  • Russ Tedrake
  • Maurice F. Fallon
  • Sisir Karumanchi
  • Scott Kuindersma
  • Matthew E. Antone
  • Toby Schneider
  • Thomas M. Howard
  • Matthew R. Walter

The attached video describes the system developed by researchers from MIT for the Defense Advanced Research Projects Agency's (DARPA) Virtual Robotics Challenge (VRC), held in June 2013. The VRC was the first competition in the DARPA Robotics Challenge (DRC), a program that aims to “develop ground robotic capabilities to execute complex tasks in dangerous, degraded, human-engineered environments” [1]. The VRC required teams to guide a model of Boston Dynamics' humanoid robot, Atlas, through driving, walking, and manipulation tasks in simulation.

Details

NeurIPS Conference 2014 Conference Paper

Fairness in Multi-Agent Sequential Decision-Making

  • Chongjie Zhang
  • Julie Shah

We define a fairness solution criterion for multi-agent decision-making problems, where agents have local interests. This new criterion aims to maximize the worst performance of agents with consideration on the overall performance. We develop a simple linear programming approach and a more scalable game-theoretic approach for computing an optimal fairness policy. This game-theoretic approach formulates this fairness optimization as a two-player, zero-sum game and employs an iterative algorithm for finding a Nash equilibrium, corresponding to an optimal fairness policy. We scale up this approach by exploiting problem structure and value function approximation. Our experiments on resource allocation problems show that this fairness criterion provides a more favorable solution than the utilitarian criterion, and that our game-theoretic approach is significantly faster than linear programming.

PDF Details

NeurIPS Conference 2014 Conference Paper

The Bayesian Case Model: A Generative Approach for Case-Based Reasoning and Prototype Classification

  • Been Kim
  • Cynthia Rudin
  • Julie Shah

We present the Bayesian Case Model (BCM), a general framework for Bayesian case-based reasoning (CBR) and prototype classification and clustering. BCM brings the intuitive power of CBR to a Bayesian generative framework. The BCM learns prototypes, the ``quintessential observations that best represent clusters in a dataset, by performing joint inference on cluster labels, prototypes and important features. Simultaneously, BCM pursues sparsity by learning subspaces, the sets of features that play important roles in the characterization of the prototypes. The prototype and subspace representation provides quantitative benefits in interpretability while preserving classification accuracy. Human subject experiments verify statistically significant improvements to participants' understanding when using explanations produced by BCM, compared to those given by prior art. "

PDF Details

ICRA Conference 2014 Conference Paper

Towards control and sensing for an autonomous mobile robotic assistant navigating assembly lines

  • Vaibhav V. Unhelkar
  • Jorge Perez
  • James C. Boerkoel Jr.
  • Johannes Bix
  • Stefan Bartscher
  • Julie Shah

There exists an increasing demand to incorporate mobile interactive robots to assist humans in repetitive, non-value added tasks in the manufacturing domain. Our aim is to develop a mobile robotic assistant for fetch-and-deliver tasks in human-oriented assembly line environments. Assembly lines present a niche yet novel challenge for mobile robots; the robot must precisely control its position on a surface which may be either stationary, moving, or split (e. g. in the case that the robot straddles the moving assembly line and remains partially on the stationary surface). In this paper we present a control and sensing solution for a mobile robotic assistant as it traverses a moving-floor assembly line. Solutions readily exist for control of wheeled mobile robots on static surfaces; we build on the open-source Robot Operating System (ROS) software architecture and generalize the algorithms for the moving line environment. Off-the-shelf sensors and localization algorithms are explored to sense the moving surface, and a customized solution is presented using PX4Flow optic flow sensors and a laser scanner-based localization algorithm. Validation of the control and sensing system is carried out both in simulation and in hardware experiments on a customized treadmill. Initial demonstrations of the hardware system yield promising results; the robot successfully maintains its position while on, and while straddling, the moving line.

Details

ICAPS Conference 2013 Conference Paper

Distributed Algorithms for Incrementally Maintaining Multiagent Simple Temporal Networks

  • James C. Boerkoel Jr.
  • Léon Planken
  • Ronald Wilcox
  • Julie Shah

When multiple agents want to maintain temporal information, they can employ a Multiagent Simple Temporal Network (MaSTN). Recent work has shown that the constraints in a MaSTN can be efficiently propagated by enforcing partial path consistency (PPC) with a distributed algorithm. However, new temporal constraints may arise continually due to ongoing plan construction or execution, the decisions of other agents, and other exogenous events. For these new constraints, propagation is again required to re-establish PPC. Because the affected part of the network may be small, one typically wants to exploit the similarities between the new and previous version of the MaSTN. To this end, we propose two new distributed algorithms for incrementally maintaining PPC. The first is inspired by TriSTP, the seminal PPC algorithm for STNs; the second is a distributed version of IPPC, which represents the current state of the art for incrementally enforcing PPC in a centralized setting. The worst-case time performance of these algorithms is similar to their centralized counterparts. We empirically compare our distributed algorithms, analyzing their performance under various assumptions, and demonstrate significant speedup over their centralized counterparts.

Details

AAAI Conference 2013 Conference Paper

Inferring Robot Task Plans from Human Team Meetings: A Generative Modeling Approach with Logic-Based Prior

  • Been Kim
  • Caleb Chacha
  • Julie Shah

We aim to reduce the burden of programming and deploying autonomous systems to work in concert with people in time-critical domains, such as military field operations and disaster response. Deployment plans for these operations are frequently negotiated on-the-fly by teams of human planners. A human operator then translates the agreed upon plan into machine instructions for the robots. We present an algorithm that reduces this translation burden by inferring the final plan from a processed form of the human team’s planning conversation. Our approach combines probabilistic generative modeling with logical plan validation used to compute a highly structured prior over possible plans. This hybrid approach enables us to overcome the challenge of performing inference over the large solution space with only a small amount of noisy data from the team planning session. We validate the algorithm through human subject experimentation and show we are able to infer a human team’s final plan with 83% accuracy on average. We also describe a robot demonstration in which two people plan and execute a first-response collaborative task with a PR2 robot. To the best of our knowledge, this is the first work that integrates a logical planning technique within a generative model to perform plan inference.

PDF Details

ICAPS Conference 2009 Conference Paper

Fast Distributed Multi-agent Plan Execution with Dynamic Task Assignment and Scheduling

  • Julie Shah
  • Patrick R. Conrad
  • Brian Williams 0001

An essential quality of a good partner is her responsiveness to other team members. Recent work in dynamic plan execution exhibits elements of this quality through the ability to adapt to the temporal uncertainties of others agents and the environment. However, a good teammate also has the ability to adapt on-the-fly through task assignment. We generalize the framework of dynamic execution to perform plan execution with dynamic task assignment as well as scheduling. This paper introduces Chaski, a multi-agent executive for scheduling temporal plans with online task assignment. Chaski enables an agent to dynamically update its plan in response to disturbances in task assignment and the schedule of other agents. The agent then uses the updated plan to choose, schedule and execute actions that are guaranteed to be temporally consistent and logically valid within the multi-agent plan. Chaski is made efficient through an incremental algorithm that compactly encodes all scheduling policies for all possible task assignments. We apply Chaski to perform multi-manipulator coordination using two Barrett Arms within the authors' hardware testbed. We empirically demonstrate up to one order of magnitude improvements in execution latency and solution compactness compared to prior art.

Details

ICAPS Conference 2009 Conference Paper

Flexible Execution of Plans with Choice

  • Patrick R. Conrad
  • Julie Shah
  • Brian Williams 0001

Dynamic plan execution strategies allow an autonomous agent to respond to uncertainties while improving robustness and reducing the need for an overly conservative plan. Executives have improved this robustness by expanding the types of choices made dynamically, such as selecting alternate methods. However, in methods to date, these additional choices introduce substantial run-time latency. This paper presents a novel system called Drake that makes steps towards executing an expanded set of choices dynamically without significant latency. Drake frames a plan as a Disjunctive Temporal Problem and executes it with a fast dynamic scheduling algorithm. Prior work demonstrated an efficient technique for dynamic execution of one special type of DTPs by using an off-line compilation step to find the possible consistent choices and compactly record the differences between them. Drake extends this work to handle a more general set of choices by recording the minimal differences between the solutions which are required at run-time. On randomly generated structured plans with choice, we show a reduction in the size of the solution set of over two orders of magnitude, compared to prior art.

Details

ICAPS Conference 2008 Conference Paper

Fast Dynamic Scheduling of Disjunctive Temporal Constraint Networks through Incremental Compilation

  • Julie Shah
  • Brian Williams 0001

Autonomous systems operating in real-world environments must plan, schedule, and execute missions while robustly adapting to uncertainty and disturbance. One way to mitigate the effect of uncertainty and disturbance is to dynamically schedule the plan online, through dispatchable execution. Dispatchable execution increases the efficiency of plan execution by introducing (1) a compiler that reduces a plan to a dispatchable form that enables real-time scheduling, and (2) a temporal plan dispatcher that schedules start times of activities (or controllable events) dynamically in response to disturbances. Previous work addresses efficient dispatchable execution of plans described as Simple Temporal Problems (STPs). While STPs have proven useful for many applications, Temporal Constraint Satisfaction Problems (TCSPs) provide a more rich language by introducing disjunctive constraints. However, previous approaches to dispatchable execution of disjunctive temporal plans are intractable for moderately-sized problems. The key contribution of this paper is an efficient algorithm for compiling and dynamically scheduling TCSPs. We present an incremental algorithm that compiles a TCSP to a compact representation, encoding the solution set in terms of the differences among solutions. We empirically demonstrate that this novel encoding reduces the space to encode the solution set by up to three orders of magnitude compared to prior art, and supports fast dynamic scheduling.

Details

ICAPS Conference 2007 Conference Paper

A Fast Incremental Algorithm for Maintaining Dispatchability of Partially Controllable Plans

  • Julie Shah
  • John Stedl
  • Brian Williams 0001
  • Paul Robertson 0001

Autonomous systems operating in real-world environments must be able to plan, schedule, and execute missions while robustly adapting to uncertainty and disturbances. Previous work on dispatchable execution increases the efficiency of plan execution under uncertainty by introducing a temporal plan dispatcher that schedules events dynamically in response to disturbances, and a compiler that reduces a plan to a dispatchable form that enables real-time scheduling. However, this work does not address the situation where response requires modifying the plan in real-time. In these situations, after the autonomous system replans, compilation to dispatchable form must occur in near real-time. The key contribution of this paper is a fast Incremental Dynamic Control algorithm (IDC) for maintaining the dispatchability of a partially controllable plan, in response to incremental plan modifications by an online planner. IDC is developed as a set of incremental update rules that exploit the structure of the plan in order to efficiently propagate the effects of constraint loosening and tightening throughout the plan. IDC exhibits an order of magnitude improvement in compile time over the state of the art non-incremental algorithm applied to randomly generated problems. Its practicality is demonstrated on plans for coordinating rovers within the authors' hardware test-bed.

Details
v2026.09.13