Simulation is critical for safety evaluation in autonomous driving, particularly in capturing complex interactive behaviors. However, generating realistic and controllable traffic scenarios in long-tail situations remains a significant challenge. Existing generative models suffer from the conflicting objective between user-defined controllability and realism constraints, which is amplified in safety-critical contexts. In this work, we introduce the Causal Compositional Diffusion Model (CCDiff), a structure-guided diffusion framework to address these challenges. We first formulate the learning of controllable and realistic closed-loop simulation as a constrained optimization problem. Then, CCDiff maximizes controllability while adhering to realism by automatically identifying and injecting causal structures directly into the diffusion process, providing structured guidance to enhance both realism and controllability. Through rigorous evaluations on benchmark datasets and in a closed-loop simulator, CCDiff demonstrates substantial gains over state-of-the-art approaches in generating realistic and user-preferred trajectories. Our results show CCDiff’s effectiveness in extracting and leveraging causal structures, showing improved closed-loop performance based on key metrics such as collision rate, off-road rate, FDE, and comfort. For more details, welcome to check our project website.

Millions of people cannot eat independently due to a disability, and caregiver-assisted meals can make them feel self-conscious, pressured, or burdensome. Robot-assisted feeding promises to empower people with motor impairments to feed themselves. However, current research typically examines specific robotic system subcomponents and evaluates them in controlled lab settings. This leaves a gap in developing and evaluating an end-to-end system that can feed entire meals in out-of-lab settings. We present one such system, which we developed collaboratively with two community researchers (CRs) with motor-impairments. The key challenge of developing a robot feeding system for out-of-lab use is the varied off-nominal scenarios that inevitably arise. Our key insight is that users can overcome many off-nominals, provided customizability and control over the system. Our system improves upon the state-of-the-art with: (1) a user interface that provides substantial user customizability and control, (2) a bite selection implementation that incorporates users-in-the-loop to generalize across food items, and (3) portable hardware that facilitates system use in diverse environments without inhibiting user mobility. We conduct two studies to evaluate the system. In Study 1, five users with motor impairments and one CR use the system to feed themselves meals of their choice in a cafeteria, office, or conference room. In Study 2, one CR uses the system in his home for five days, feeding himself 10 meals across diverse contexts. We present 3 key lesson learned: (1) spatial contexts are numerous, customizability lets users adapt to them; (2) off-nominals will arise, variable autonomy lets users overcome them; and (3) assistive robots' benefits depend on context. We provide video footage and code on our website.

It is difficult to anticipate the myriad challenges that a predictive model will encounter once deployed. Common practice entails a reactive, cyclical approach: model deployment, data mining, and retraining. We instead develop a proactive longtail discovery process by imagining additional data during training. In particular, we develop general model-based longtail signals, including a differentiable, single forward pass formulation of epistemic uncertainty that does not impact model parameters or predictive performance but can flag rare or hard inputs. We leverage these signals as guidance to generate additional training data from a latent diffusion model in a process we call Longtail Guidance (LTG). Crucially, we can perform LTG without retraining the diffusion model or the predictive model, and we do not need to expose the predictive model to intermediate diffusion states. Data generated by LTG exhibit semantically meaningful variation, yield significant generalization improvements on numerous image classification benchmarks, and can be analyzed by a VLM to proactively discover, textually explain, and address conceptual gaps in a deployed predictive model.

We present DriveGPT, a scalable behavior model for autonomous driving. We model driving as a sequential decision-making task, and learn a transformer model to predict future agent states as tokens in an autoregressive fashion. We scale up our model parameters and training data by multiple orders of magnitude, enabling us to explore the scaling properties in terms of dataset size, model parameters, and compute. We evaluate DriveGPT across different scales in a planning task, through both quantitative metrics and qualitative examples, including closed-loop driving in complex real-world scenarios. In a separate prediction task, DriveGPT outperforms state-of-the-art baselines and exhibits improved performance by pretraining on a large-scale dataset, further validating the benefits of data scaling.

A classical approach for solving discrete time nonlinear control on a finite horizon consists in repeatedly minimizing linear quadratic approximations of the original problem around current candidate solutions. While widely popular in many domains, such an approach has mainly been analyzed locally. We provide detailed convergence guarantees to stationary points as well as local linear convergence rates for the Iterative Linear Quadratic Regulator (ILQR) algorithm and its Differential Dynamic Programming (DDP) variant. For problems without costs on control variables, we observe that global convergence to minima can be ensured provided that the linearized discrete time dynamics are surjective, costs on the state variables are gradient dominated. We further detail quadratic local convergence when the costs are self-concordant. We show that surjectivity of the linearized dynamics hold for appropriate discretization schemes given the existence of a feedback linearization scheme. We present complexity bounds of algorithms based on linear quadratic approximations through the lens of generalized Gauss-Newton methods. Our analysis uncovers several convergence phases for regularized generalized Gauss-Newton algorithms.

We present a new technique to enhance the robustness of imitation learning methods by generating corrective data to account for compounding error and disturbances. While existing methods rely on interactive expert labeling, additional offline datasets, or domain-specific invariances, our approach requires minimal additional assumptions beyond expert data. The key insight is to leverage local continuity in the environment dynamics. Our method first constructs a dynamics model from the expert demonstration, enforcing local Lipschitz continuity while skipping the discontinuous regions. In the locally continuous regions, this model allows us to generate corrective labels within the neighborhood of the demonstrations but beyond the actual set of states and actions in the dataset. Training on this augmented data enhances the agent's ability to recover from perturbations and deal with compounding error. We demonstrate the effectiveness of our generated labels through experiments in a variety of robotics domains that have distinct forms of continuity and discontinuity, including classic control, drone flying, high-dimensional navigation, locomotion, and tabletop manipulation.

We focus on the problem of long-range dynamic replanning for off-road autonomous vehicles, where a robot plans paths through a previously unobserved environment while continuously receiving noisy local observations. An effective approach for planning under sensing uncertainty is determinization, where one converts a stochastic world into a deterministic one and plans under this simplification. This makes the planning problem tractable, but the cost of following the planned path in the real world may be different than in the determinized world. This causes collisions if the determinized world optimistically ignores obstacles, or causes unnecessarily long routes if the determinized world pessimistically imagines more obstacles. We aim to be robust to uncertainty over potential worlds while still achieving the efficiency benefits of determinization. We evaluate algorithms for dynamic replanning on a large real-world dataset of challenging long-range planning problems from the DARPA RACER program. Our method, Dynamic Replanning via Evaluating and Aggregating Multiple Samples (DREAMS), outperforms other determinization-based approaches in terms of combined traversal time and collision cost. https://sites.google.com/cs.washington.edu/dreams/

We consider imitation learning with access only to expert demonstrations, whose real-world application is often limited by covariate shift due to compounding errors during execution. We investigate the effectiveness of the Continuity-based Corrective Labels for Imitation Learning (CCIL) framework in mitigating this issue for real-world fine manipulation tasks. CCIL generates corrective labels by learning a locally continuous dynamics model from demonstrations to guide the agent back toward expert states. Through extensive experiments on insertion and fine grasping tasks, we provide the first empirical validation that CCIL can significantly improve imitation learning performance despite discontinuities present in contact-rich manipulation. We find that: (1) real-world manipulation exhibits sufficient local smoothness to apply CCIL, (2) generated corrective labels are most beneficial in low-data regimes, and (3) label filtering based on estimated dynamics model error enables performance gains. To effectively apply CCIL to robotic domains, we offer a practical instantiation of the framework and insights into design choices and hyperparameter selection. Our work demonstrates CCIL’s practicality for alleviating compounding errors in imitation learning on physical robots.

Social dining, i.e., eating with/in company, is replete with meaning and cultural significance. Unfortunately, for the 1.8 million Americans with motor impairments who cannot eat without assistance, challenges restrict them from enjoying this pleasant social ritual. In this work, we identify the needs of participants with motor impairments during social dining and how robot-assisted feeding can address them. Using speculative videos that show robot behaviors within a social dining context, we interviewed participants to understand their preferences. Following a community-based participatory research method, we worked with a community researcher with motor impairments throughout this study. We contribute (a) insights into how a robot can help overcome challenges in social dining, (b) design principles for creating robot-assisted feeding systems, (c) and an implementation guide for future research in this area. Our key finding is that robots' unique assistive qualities can address challenges people with motor impairments face during social dining, promoting empowerment and belonging.

Sampling-based motion planners rely on incre-mental densification to discover progressively shorter paths. After computing feasible path$\xi$between start$x_{s}$and goal$x_{t}$, the Informed Set (IS) prunes the configuration space$\mathcal{X}$by conservatively eliminating points that cannot yield shorter paths. Densification via sampling from this Informed Set retains asymptotic optimality of sampling from the entire configuration space. For path length$c(\xi)$and Euclidean heuristic$h, IS= \{x\vert x\in \mathcal{X},\ h(x_{s},\ x)+h(x,\ x_{t})\leq c(\xi)\}$. Relying on the heuristic can render the IS especially conservative in high dimensions or complex environments. Furthermore, the IS only shrinks when shorter paths are discovered. Thus, the computational effort from each iteration of densification and planning is wasted if it fails to yield a shorter path, despite improving the cost-to-come for vertices in the search tree. Our key insight is that even in such a failure, shorter paths to vertices in the search tree (rather than just the goal) can immediately improve the planner's sampling strategy. Guided Incremental Local Densification (GuILD) leverages this information to sample from Local Subsets of the IS. We show that GuILD significantly outperforms uniform sampling of the Informed Set in simulated$\mathbb{R}^{2}, SE(2)$environments and manipulation tasks in$\mathbb{R}^{7}$.

Offline reinforcement learning (ORL) holds great promise for robot learning due to its ability to learn from arbitrary pre-generated experience. However, current ORL benchmarks are almost entirely in simulation and utilize contrived datasets like replay buffers of online RL agents or sub-optimal trajectories, and thus hold limited relevance for real-world robotics. In this work (Real-ORL), we posit that data collected from safe operations of closely related tasks are more practical data sources for real-world robot learning. Under these settings, we perform an extensive (6500+ trajectories collected over 800+ robot hours and 270+ human labor hour) empirical study evaluating generalization and transfer capabilities of representative ORL methods on four real-world tabletop manipulation tasks. Our study finds that ORL and imitation learning prefer different action spaces, and that ORL algorithms can generalize from leveraging offline heterogeneous data sources and outperform imitation learning. We release our dataset and implementations at URL: https://sites.google.com/view/real-orl.

We focus on robot navigation in crowded environments. To navigate safely and efficiently within crowds, robots need models for crowd motion prediction. Building such models is hard due to the high dimensionality of multiagent domains and the challenge of collecting or simulating interaction-rich crowd-robot demonstrations. While there has been important progress on models for offline pedestrian motion forecasting, transferring their performance on real robots is nontrivial due to close interaction settings and novelty effects on users. In this paper, we investigate the utility of a recent state-of-the-art motion prediction model (S-GAN) for crowd navigation tasks. We incorporate this model into a model predictive controller (MPC) and deploy it on a self-balancing robot which we subject to a diverse range of crowd behaviors in the lab. We demonstrate that while S-GAN motion prediction accuracy transfers to the real world, its value is not reflected on navigation performance, measured with respect to safety and efficiency; in fact, the MPC performs indistinguishably even when using a simple constant-velocity prediction model, suggesting that substantial model improvements might be needed to yield significant gains for crowd navigation tasks. Footage from our experiments can be found at https://youtu.be/mzFiXgSKsZ0.

We focus on the problem of rearranging a set of objects with a team of car-like robot pushers built using off-the-shelf components. Maintaining control of pushed objects while avoiding collisions in a tight space demands highly coordinated motion that is challenging to execute on constrained hardware. Centralized replanning approaches become intractable even for small-sized problems whereas decentralized approaches often get stuck in deadlocks. Our key insight is that by carefully assigning pushing tasks to robots, we could reduce the complexity of the rearrangement task, enabling robust performance via scalable decentralized control. Based on this insight, we built PuSHR, a system that optimally assigns pushing tasks and trajectories to robots offline, and performs trajectory tracking via decentralized control online. Through an ablation study in simulation, we demonstrate that PuSHR dominates baselines ranging from purely centralized to fully decentralized in terms of success rate and time efficiency across challenging tasks with up to 4 robots. Hardware experiments demonstrate the transfer of our system to the real world and highlight its robustness to model inaccuracies. Our code can be found at https://github.com/prl-mushr/pushr, and videos from our experiments at https://youtu.be/nyUn9mHoR8Y.

It is difficult to run long-term in-the-wild studies with mobile robots. This is partly because the robots we, as human-robot interaction (HRI) researchers, are interested in deploying prioritize expressivity over navigational capabilities, and making those robots autonomous is often not the focus of our research. One way to address these difficulties is with the Wizard of Oz (WoZ) methodology, where a researcher teleop-erates the robot during its deployment. However, the constant attention required for teleoperation limits the duration of WoZ deployments, which in-turn reduces the amount of in-the-wild data we are able to collect. Our key insight is that several types of in-the-wild mobile robot studies can be run without autonomous navigation, using wandering instead. In this paper we present and share code for our wandering robot system, which enabled Kuri, an expressive robot with limited sensor and computational capabilities, to traverse the hallways of a$28,000 \text{ ft}^{2}$floor for four days. Our system relies on informed direction selection to avoid obstacles and traverse the space, and periodic human help to charge. After presenting the outcomes from the four-day deployment, we then discuss the benefits of deploying a wandering robot, explore the types of in-the-wild studies that can be run with wandering robots, and share pointers for enabling other robots to wander. Our goal is to add wandering to the toolbox of navigation approaches HRI researchers use, particularly to run in-the-wild deployments with mobile robots.

Robot-assisted feeding in household environments is challenging because it requires robots to generate trajectories that effectively bring food items of varying shapes and sizes into the mouth while making sure the user is comfortable. Our key insight is that in order to solve this challenge, robots must balance the efficiency of feeding a food item with the comfort of each individual bite. We formalize comfort and efficiency as heuristics to incorporate in motion planning. We present an approach based on heuristics-guided bi-directional Rapidly-exploring Random Trees (h-BiRRT) that selects bite transfer trajectories of arbitrary food item geometries and shapes using our developed bite efficiency and comfort heuristics and a learned constraint model. Real-robot evaluations show that op-timizing both comfort and efficiency significantly outperforms a fixed-pose based method, and users preferred our method significantly more than that of a method that maximizes only user comfort. Videos and Appendices are found on our website: https://tinyurl.com/bticra22.

Efficient and reliable generation of global path plans are necessary for safe execution and deployment of autonomous systems. In order to generate planning graphs which adequately resolve the topology of a given environment, many sampling-based motion planners resort to coarse, heuristically-driven strategies which often fail to generalize to new and varied surroundings. Further, many of these approaches are not designed to contend with partial-observability. We posit that such uncertainty in environment geometry can, in fact, help drive the sampling process in generating feasible, and probabilistically-safe planning graphs. We propose a method for Probabilistic Roadmaps which relies on particle-based Variational Inference to efficiently cover the posterior distribution over feasible regions in configuration space. Our approach, Stein Variational Probabilistic Roadmap (SV-PRM), results in sample-efficient generation of planning-graphs and large improvements over traditional sampling approaches. We demonstrate the approach on a variety of challenging planning problems, including real-world probabilistic occupancy maps and high-dof manipulation problems common in robotics. Video, additional material and results can be found here: https://sites.google.com/view/stein-prm.

We focus on the problem of analyzing multiagent interactions in traffic domains. Understanding the space of behavior of real-world traffic may offer significant advantages for algorithmic design, data-driven methodologies, and bench-marking. However, the high dimensionality of the space and the stochasticity of human behavior may hinder the identification of important interaction patterns. Our key insight is that traffic environments feature significant geometric and temporal structure, leading to highly organized collective behaviors, often drawn from a small set of dominant modes. In this work, we propose a representation based on the formalism of topological braids that can summarize arbitrarily complex multiagent behavior into a compact object of dual geometric and symbolic nature, capturing critical events of interaction. This representation allows us to formally enumerate the space of outcomes in a traffic scene and characterize their complexity. We illustrate the value of the proposed representation in summarizing critical aspects of real-world traffic behavior through a case study on recent driving datasets. We show that despite the density of real-world traffic, observed behavior tends to follow highly organized patterns of low interaction. Our framework may be a valuable tool for evaluating the richness of driving datasets, but also for synthetically designing balanced training datasets or benchmarks.

When navigating to a goal in an uncertain environment, a robot must simultaneously navigate the exploration-exploitation tradeoff: should it aim to gain information and reduce uncertainty, or should it simply brave the unknown? We formalize this as the Bayesian dynamic motion planning problem, and we analyze how several strategies from the literature balance these concerns via determinization and planning. Within the framework of determinization in the face of uncertainty, we shift the burden of exploration to determinization rather than planning. Dynamic Replanning with Posterior Sampling (DRPS) is very efficient: each iteration consists of a single posterior update and a shortest path query. Relative to comparative baselines across seven datasets of 2D planning problems, DRPS has a higher percentage of success, traverses lower or comparable total distances, and accelerates total planning time by 4–7×. Across a dataset of larger 7D Baxter manipulator planning problems, DRPS reduces total distance by 40% and total planning time by 18×.

During in-hand manipulation, robots must be able to continuously estimate the pose of the object in order to generate appropriate control actions. The performance of algorithms for pose estimation hinges on the robot's sensors being able to detect discriminative geometric object features, but previous sensing modalities are unable to make such measurements robustly. The robot's fingers can occlude the view of environment- or robot-mounted image sensors, and tactile sensors can only measure at the local areas of contact. Motivated by fingertip-embedded proximity sensors' robustness to occlusion and ability to measure beyond the local areas of contact, we present the first evaluation of proximity sensor based pose estimation for in-hand manipulation. We develop a novel two-fingered hand with fingertip-embedded optical time-of-flight proximity sensors as a testbed for pose estimation during planar in-hand manipulation. Here, the in-hand manipulation task consists of the robot moving a cylindrical object from one end of its workspace to the other. We demonstrate, with statistical significance, that proximity-sensor based pose estimation via particle filtering during in-hand manipulation: a) exhibits 50% lower average pose error than a tactile-sensor based baseline; b) empowers a model predictive controller to achieve 30% lower final positioning error compared to when using tactile-sensor based pose estimates.

We present an incremental search algorithm, called Lifelong-GLS, which combines the vertex efficiency of Lifelong Planning A* (LPA*) and the edge efficiency of Generalized Lazy Search (GLS) for efficient replanning on dynamic graphs where edge evaluation is expensive. We use a lazily evaluated LPA* to repair the cost-to-come inconsistencies of the relevant region of the current search tree based on the previous search results, and then we restrict the expensive edge evaluations only to the current shortest subpath as in the GLS framework. The proposed algorithm is complete and correct in finding the optimal solution in the current graph, if one exists. We also show the efficiency of the proposed algorithm compared to the standard LPA* and the GLS algorithms over consecutive search episodes in a dynamic environment.

Autonomous robot-assisted feeding requires the ability to acquire a wide variety of food items. However, it is impossible for such a system to be trained on all types of food in existence. Therefore, a key challenge is choosing a manipulation strategy for a previously unseen food item. Previous work showed that the problem can be represented as a linear bandit with visual context. However, food has a wide variety of multi-modal properties relevant to manipulation that can be hard to distinguish visually. Our key insight is that we can leverage the haptic context we collect during and after manipulation (i.e., "post hoc") to learn some of these properties and more quickly adapt our visual model to previously unseen food. In general, we propose a modified linear contextual bandit framework augmented with post hoc context observed after action selection to empirically increase learning speed and reduce cumulative regret. Experiments on synthetic data demonstrate that this effect is more pronounced when the dimensionality of the context is large relative to the post hoc context or when the post hoc context model is particularly easy to learn. Finally, we apply this framework to the bite acquisition problem and demonstrate the acquisition of 8 previously unseen types of food with 21% fewer failures across 64 attempts.

Billions of people use chopsticks, a simple yet versatile tool, for fine manipulation of everyday objects. The small, curved, and slippery tips of chopsticks pose a challenge for picking up small objects, making them a suitably complex test case. This paper leverages human demonstrations to develop an autonomous chopsticks-equipped robotic manipulator. Due to the lack of accurate models for fine manipulation, we explore model-free imitation learning, which traditionally suffers from the covariate shift phenomenon that causes poor generalization. We propose two approaches to reduce covariate shift, neither of which requires access to an interactive expert or a model, unlike previous approaches. First, we alleviate singlestep prediction errors by applying an invariant operator to increase the data support at critical steps for grasping. Second, we generate synthetic corrective labels by adding bounded noise and combining parametric and non-parametric methods to prevent error accumulation. We demonstrate our methods on a real chopstick-equipped robot that we built, and observe the agent’s success rate increase from 37.3% to 80%, which is comparable to the human expert performance of 82.6%.

Informed and robust decision making in the face of uncertainty is critical for robots operating in unstructured environments. We formulate this as Bayesian Reinforcement Learning over latent Markov Decision Processes (MDPs). While Bayes-optimality is theoretically the gold standard, existing algorithms scale poorly to continuous state and action spaces. We build on the following insight: in the absence of uncertainty, each latent MDP is easier to solve. We first obtain an ensemble of experts, one for each latent MDP, and fuse their advice to compute a baseline policy. Next, we train a Bayesian residual policy to improve upon the ensemble’s recommendation and learn to reduce uncertainty. Our algorithm, Bayesian Residual Policy Optimization (BRPO), imports the scalability of policy gradient methods and task-specific expert skills. BRPO significantly improves the ensemble of experts and drastically outperforms existing adaptive RL methods, both in simulated and physical robot experiments.

A robot-assisted feeding system can potentially help a user with upper-body mobility impairments eat independently. However, autonomous assistance in the real world is challenging because of varying user preferences, impairment constraints, and possibility of errors in uncertain and unstructured environments. An autonomous robot-assisted feeding system needs to decide the appropriate strategy to acquire a bite of hard-to-model deformable food items, the right time to bring the bite close to the mouth, and the appropriate strategy to transfer the bite easily. Our key insight is that a system should be designed based on a user's preference about these various challenging aspects of the task. In this work, we explore user preferences for different modes of autonomy given perceived error risks and also analyze the effect of input modalities on technology acceptance. We found that more autonomy is not always better, as participants did not have a preference to use a robot with partial autonomy over a robot with low autonomy. In addition, participants' user interface preference changes from voice control during individual dining to web-based during social dining. Finally, we found differences on average ratings when grouping the participants based on their mobility limitations (lower vs. higher) that suggests that ratings from participants with lower mobility limitations are correlated with higher expectations of robot performance.

Collision checking is a computational bottleneck in motion planning, requiring lazy algorithms that explicitly reason about when to perform this computation. Optimism in the face of collision uncertainty minimizes the number of checks before finding the shortest path. However, this may take a prohibitively long time to compute, with no other feasible paths discovered during this period. For many real-time applications, we instead demand strong anytime performance, defined as minimizing the cumulative lengths of the feasible paths yielded over time. We introduce Posterior Sampling for Motion Planning (PSMP), an anytime lazy motion planning algorithm that leverages learned posteriors on edge collisions to quickly discover an initial feasible path and progressively yield shorter paths. PSMP obtains an expected regret bound of Õ(√(SAT)) and outperforms comparative baselines on a set of 2D and 7D planning problems.

A successful robot-assisted feeding system requires bite acquisition of a wide variety of food items. It must adapt to changing user food preferences under uncertain visual and physical environments. Different food items in different environmental conditions require different manipulation strategies for successful bite acquisition. Therefore, a key challenge is how to handle previously unseen food items with very different success rate distributions over strategy. Combining low-level controllers and planners into discrete action trajectories, we show that the problem can be represented using a linear contextual bandit setting. We construct a simulated environment using a doubly robust loss estimate from previously seen food items, which we use to tune the parameters of off-the-shelf contextual bandit algorithms. Finally, we demonstrate empirically on a robot- assisted feeding system that, even starting with a model trained on thousands of skewering attempts on dissimilar previously seen food items, ϵ-greedy and LinUCB algorithms can quickly converge to the most successful manipulation strategy.

Chopsticks constitute a simple yet versatile tool that humans have used for thousands of years to perform a variety of challenging tasks ranging from food manipulation to surgery. Applying such a simple tool in a diverse repertoire of scenarios requires significant adaptability. Towards developing autonomous manipulators with comparable adaptability to humans, we study chopsticks-based manipulation to gain insights into human manipulation strategies. We conduct a within-subjects user study with 25 participants, evaluating three different data-collection methods: normal chopsticks, motion-captured chopsticks, and a novel chopstick telemanipulation interface. We analyze factors governing human performance across a variety of challenging chopstick-based grasping tasks. Although participants rated teleoperation as the least comfortable and most difficult-to-use method, teleoperation enabled users to achieve the highest success rates on three out of five objects considered. Further, we notice that subjects quickly learned and adapted to the teleoperation interface. Finally, while motion-captured chopsticks could provide a better reflection of how humans use chopsticks, the teleoperation interface can produce quality on-hardware demonstrations from which the robot can directly learn.

Trust in autonomy is essential for effective human-robot collaboration and user adoption of autonomous systems such as robot assistants. This article introduces a computational model that integrates trust into robot decision making. Specifically, we learn from data a partially observable Markov decision process (POMDP) with human trust as a latent variable. The trust-POMDP model provides a principled approach for the robot to (i) infer the trust of a human teammate through interaction, (ii) reason about the effect of its own actions on human trust, and (iii) choose actions that maximize team performance over the long term. We validated the model through human subject experiments on a table clearing task in simulation (201 participants) and with a real robot (20 participants). In our studies, the robot builds human trust by manipulating low-risk objects first. Interestingly, the robot sometimes fails intentionally to modulate human trust and achieve the best team performance. These results show that the trust-POMDP calibrates trust to improve human-robot team performance over the long term. Further, they highlight that maximizing trust alone does not always lead to the best performance.

Robot-assisted feeding (RAF) systems offer enormous potential benefits to community-centered care-giving environments. However, developers of RAF technologies often focus on evaluating their standard transactional functionality, omitting the impact of such technologies in contexts that extend past the interaction of the robot and food receiver. RAF technologies have complex social, cultural and self-identity implications, since a "meal" extends well beyond the simple provisioning of nourishment. To better understand these implications we conducted a contextual inquiry in an assisted-living community with five potential care recipients and five caregivers, as well as interviews with fifteen domain experts including occupational therapists and feeding specialists. Based on our findings from these studies, we developed a new framework for RAF technologies that formulates this vital task as a community-centered relational service. We then use this framework to qualitatively and quantitatively assess three existing feeding systems and identify areas of improvement. Our work reveals new insights about stakeholders of RAF technologies and provides a roadmap for technology developers to better serve the needs of these stakeholders.

We present the Frontier Aware Search with backTracking (FAST) Navigator, a general framework for action decoding, that achieves state-of-the-art results on the Room-to-Room (R2R) Vision-and-Language navigation challenge of Anderson et. al. (2018). Given a natural language instruction and photo-realistic image views of a previously unseen environment, the agent was tasked with navigating from source to target location as quickly as possible. While all current approaches make local action decisions or score entire trajectories using beam search, ours balances local and global signals when exploring an unobserved environment. Importantly, this lets us act greedily but use global signals to backtrack when necessary. Applying FAST framework to existing state-of-the-art models achieved a 17% relative gain, an absolute 6% gain on Success rate weighted by Path Length (SPL)1.

Learning preferences implicit in the choices humans make is a well studied problem in both economics and computer science. However, most work makes the assumption that humans are acting (noisily) optimally with respect to their preferences. Such approaches can fail when people are themselves learning about what they want. In this work, we introduce the assistive multi-armed bandit, where a robot assists a human playing a bandit task to maximize cumulative reward. In this problem, the human does not know the reward function but can learn it through the rewards received from arm pulls; the robot only observes which arms the human pulls but not the reward associated with each pull. We offer sufficient and necessary conditions for successfully assisting the human in this framework. Surprisingly, better human performance in isolation does not necessarily lead to better performance when assisted by the robot: a human policy can do better by effectively communicating its observed rewards to the robot. We conduct proof-of-concept experiments that support these results. We see this work as contributing towards a theory behind algorithms for human-robot interaction.

Successful robotic assistive feeding depends on reliable bite acquisition and easy bite transfer. The latter constitutes a unique type of robot-human handover where the human needs to use the mouth. This places a high burden on the robot to make the transfer easy. We believe that the ease of transfer not only depends on the transfer action but also is tightly coupled with the way a food item was acquired in the first place. To determine the factors influencing good bite transfer, we designed both skewering and transfer primitives and developed a robotic feeding system that uses these manipulation primitives to feed people autonomously. First, we determined the primitives' success rates for bite acquisition with robot experiments. Next, we conducted user studies to evaluate the ease of bite transfer for different combinations of skewering and transfer primitives. Our results show that an intelligent food item dependent skewering strategy improves the bite acquisition success rate and that the choice of skewering location and the fork orientation affects the ease of bite transfer sianificantly.

We present a 16.2-million frame (50-hour) multimodal dataset of two-person face-to-face spontaneous conversations. Our dataset features synchronized body and finger motion as well as audio data. To the best of our knowledge, it represents the largest motion capture and audio dataset of natural conversations to date. The statistical analysis verifies strong intraperson and interperson covariance of arm, hand, and speech features, potentially enabling new directions on data-driven social behavior analysis, prediction, and synthesis. As an illustration, we propose a novel real-time finger motion synthesis method: a temporal neural network innovatively trained with an inverse kinematics (IK) loss, which adds skeletal structural information to the generative model. Our qualitative user study shows that the finger motion generated by our method is perceived as natural and conversation enhancing, while the quantitative ablation study demonstrates the effectiveness of IK loss.

We examine popular gradient-based algorithms for nonlinear control in the light of the modern complexity analysis of first-order optimization algorithms. The examination reveals that the complexity bounds can be clearly stated in terms of calls to a computational oracle related to dynamic programming and implementable by gradient back-propagation using machine learning software libraries such as PyTorch or TensorFlow. Finally, we propose a regularized Gauss-Newton algorithm enjoying worst-case complexity bounds and improved convergence behavior in practice. The software library based on PyTorch is publicly available.

We describe a single fingertip-mounted sensing system for robot manipulation that provides proximity (pre-touch), contact detection (touch), and force sensing (post-touch). The sensor system consists of optical time-of-flight range measurement modules covered in a clear elastomer. Because the elastomer is clear, the sensor can detect and range nearby objects, as well as measure deformations caused by objects that are in contact with the sensor and thereby estimate the applied force. We examine how this sensor design can be improved with respect to invariance to object reflectivity, signal-to-noise ratio, and continuous operation when switching between the distance and force measurement regimes. By harnessing time-of-flight technology and optimizing the elastomer-air boundary to control the emitted light's path, we develop a sensor that is able to seamlessly transition between measuring distances of up to 50 mm and contact forces of up to 10 newtons. We demonstrate that our sensor improves manipulation accuracy in a block unstacking task. Thorough instructions for manufacturing the sensor from inexpensive, commercially available components are provided, as well as all relevant hardware design files and software sources.

Autonomous assistive feeding systems need to acquire deformable food items of varying physical characteristics to be able to feed users. However, bite acquisition of these deformable food items is challenging without force feedback of appropriate range and sensitivity. We developed custom solutions using two widely-used shear sensing fingertip tactile sensors and calibrated them to the range of forces needed for manipulating food items. We compared their performance with traditional force/torque sensors and showed the trade-off between the range and the sensitivity of the fingertip tactile sensors in detecting potential bite acquisition successes for food items with widely varying weights and compliance. We then developed a control policy, using which a robotic gripper equipped with the fingertip tactile sensors can autonomously regulate the sensing range and the sensitivity to be able to skewer food items of different compliance and detect their bite acquisition success attempts.

The ability to reference objects in the environment is a key communication skill that robots need for complex, task-oriented human-robot collaborations. In this paper we explore the use of projections, which are a powerful communication channel for robot-to-human information transfer as they allow for situated, instantaneous, and parallelized visual referencing. We focus on the question of what makes a good projection for referencing a target object. To that end, we mathematically formulatelegibility of projections intended to reference an object, and propose alternative arrow-object match functions for optimally computing the placement of an arrow to indicate a target object in a cluttered scene. We implement our approach on a PR2 robot with a head-mounted projector. Through an online (48 participants) and an in-person (12 participants) user study we validate the effectiveness of our approach, identify the types of scenes where projections may fail, and characterize the differences between alternative match functions.

The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along candidate shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm such as manipulation in cluttered environments and planning for robots in surgical settings; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.

We consider the problem of leveraging prior experience to generate roadmaps in sampling-based motion planning. A desirable roadmap is one that is sparse, allowing for fast search, with nodes spread out at key locations such that a low- cost feasible path exists. An increasingly popular approach is to learn a distribution of nodes that would produce such a roadmap. State-of-the-art is to train a conditional variational auto-encoder (CVAE) on the prior dataset with the shortest paths as target input. While this is quite effective on many problems, we show it can fail in the face of complex obstacle configurations or mismatch between training and testing. We present an algorithm LEGO that addresses these issues by training the CVAE with target samples that satisfy two important criteria. Firstly, these samples belong only to bottleneck regions along near-optimal paths that are otherwise difficult- to-sample with a uniform sampler. Secondly, these samples are spread out across diverse regions to maximize the likelihood of a feasible path existing. We formally define these properties and prove performance guarantees for LEGO. We extensively evaluate LEGO on a range of planning problems, including robot arm planning, and report significant gains over heuristics as well as learned baselines.

A motion-planning problem's setup can drastically affect the quality of solutions returned by the planner. In this work we consider optimizing these setups, with a focus on doing so in a computationally-efficient fashion. Our approach interleaves optimization with motion planning, which allows us to consider the actual motions required of the robot. Similar prior work has treated the planner as a black box: our key insight is that opening this box in a simple-yet-effective manner enables a more efficient approach, by allowing us to bound the work done by the planner to optimizer-relevant computations. Finally, we apply our approach to a surgically-relevant motion-planning task, where our experiments validate our approach by more-efficiently optimizing the fixed insertion pose of a surgical robot.

We use static object data to improve success detection for stacking objects on and nesting objects in one another. Such actions are necessary for certain robotics tasks, e.g., clearing a dining table or packing a warehouse bin. However, using an RGB-D camera to detect success can be insufficient: same-colored objects can be difficult to differentiate, and reflective silverware cause noisy depth camera perception. We show that adding static data about the objects themselves improves the performance of an end-to-end pipeline for classifying action outcomes. Images of the objects, and language expressions describing them, encode prior geometry, shape, and size information that refine classification accuracy. We collect over 13 hours of egocentric manipulation data for training a model to reason about whether a robot successfully placed unseen objects in or on one another. The model achieves up to a 57% absolute gain over the task baseline on pairs of previously unseen objects.

In many environments, only a relatively small subset of the complete state space is necessary in order to accomplish a given task. We develop a simple technique using emergency stops (e-stops) to exploit this phenomenon. Using e-stops significantly improves sample complexity by reducing the amount of required exploration, while retaining a performance bound that efficiently trades off the rate of convergence with a small asymptotic sub-optimality gap. We analyze the regret behavior of e-stops and present empirical results in discrete and continuous settings demonstrating that our reset mechanism can provide order-of-magnitude speedups on top of existing reinforcement learning methods.

For robots to operate in a three dimensional world and interact with humans, learning spatial relationships among objects in the surrounding is necessary. Reasoning about the state of the world requires inputs from many different sensory modalities including vision (V) and haptics (H). We examine the problem of desk organization: learning how humans spatially position different objects on a planar surface according to organizational “preference”. We model this problem by examining how humans position objects given multiple features received from vision and haptic modalities. However, organizational habits vary greatly between people both in structure and adherence. To deal with user organizational preferences, we add an additional modality, “utility” (U), which informs on a particular human's perceived usefulness of a given object. Models were trained as generalized (over many different people) or tailored (per person). We use two types of models: random forests, which focus on precise multi-task classification, and Markov logic networks, which provide an easily interpretable insight into organizational habits. The models were applied to both synthetic data, which proved to be learnable when using fixed organizational constraints, and human-study data, on which the random forest achieved over 90% accuracy. Over all combinations of {H, U, V} modalities, UV and HUV were the most informative for organization. In a follow-up study, we gauged participants preference of desk organizations by a generalized random forest organization vs. by a random model. On average, participants rated the random forest models as 4.15 on a 5-point Likert scale compared to 1.84 for the random model.

Shared autonomy systems enhance people's abilities to perform activities of daily living using robotic manipulators. Recent systems succeed by first identifying their operators' intentions, typically by analyzing the user's joystick input. To enhance this recognition, it is useful to characterize people's behavior while performing such a task. Furthermore, eye gaze is a rich source of information for understanding operator intention. The goal of this paper is to provide novel insights into the dynamics of control behavior and eye gaze in human-robot shared manipulation tasks. To achieve this goal, we conduct a data collection study that uses an eye tracker to record eye gaze during a human-robot shared manipulation activity, both with and without shared autonomy assistance. We process the gaze signals from the study to extract gaze features like saccades, fixations, smooth pursuits, and scan paths. We analyze those features to identify novel patterns of gaze behaviors and highlight where these patterns are similar to and different from previous findings about eye gaze in human-only manipulation tasks. The work described in this paper lays a foundation for a model of natural human eye gaze in human-robot shared manipulation.

Trust is essential for human-robot collaboration and user adoption of autonomous systems, such as robot assistants. This paper introduces a computational model which integrates trust into robot decision-making. Specifically, we learn from data a partially observable Markov decision process (POMDP) with human trust as a latent variable. The trust-POMDP model provides a principled approach for the robot to (i) infer the trust of a human teammate through interaction, (ii) reason about the effect of its own actions on human behaviors, and (iii) choose actions that maximize team performance over the long term. We validated the model through human subject experiments on a table-clearing task in simulation (201 participants) and with a real robot (20 participants). The results show that the trust-POMDP improves human-robot team performance in this task. They further suggest that maximizing trust in itself may not improve team performance.

We introduce Recurrent Predictive State Policy(RPSP) networks, a recurrent architecture that brings insights from predictive state representations to reinforcement learning in partially ob-servable environments. Predictive state policy networks consist of a recursive filter, which keeps track of a belief about the state of the environment, and a reactive policy that directly maps beliefs to actions, to maximize the cumulative reward. The recursive filter leverages predictive state representations (PSRs) (Rosencrantz & Gordon, 2004; Sun et al., 2016) by modeling predictive state{—}a prediction of the distribution of future observations conditioned on history and future actions.This representation gives rise to a rich class of statistically consistent algorithms (Hefny et al.,2017) to initialize the recursive filter. Predictive stats serves as an equivalent representation of a belief state. Therefore, the policy component of the RPSP-network can be purely reactive, simplifying training while still allowing optimal behavior. Moreover, we use the PSR interpretation during training as well, by incorporating prediction error in the loss function. The entire network (recursive filter and reactive policy) is still differentiable and can be trained using gradient-based methods. We optimize our policy using a combination of policy gradient based on rewards (Williams, 1992)and gradient descent based on prediction error.We show the efficacy of RPSP-networks on a set of robotic control tasks from OpenAI Gym. We empirically show that RPSP-networks perform well compared with memory-preserving networks such as GRUs, as well as finite memory models, being the overall best performing method.

Asymptotically-optimal motion planners such as RRT* have been shown to incrementally approximate the shortest path between start and goal states. Once an initial solution is found, their performance can be dramatically improved by restricting subsequent samples to regions of the state space that can potentially improve the current solution. When the motion-planning problem lies in a Euclidean space, this region Xinf, called the informed set, can be sampled directly. However, when planning with differential constraints in non-Euclidean state spaces, no analytic solutions exists to sampling Xinfdirectly. State-of-the-art approaches to sampling Xinfin such domains such as Hierarchical Rejection Sampling (HRS) may still be slow in high -dimensional state space. This may cause the planning algorithm to spend most of its time trying to produces samples in Xinfrather than explore it. In this paper, we suggest an alternative approach to produce samples in the informed set Xinffor a wide range of settings. Our main insight is to recast this problem as one of sampling uniformly within the sub-level-set of an implicit non-convex function. This recasting enables us to apply Monte Carlo sampling methods, used very effectively in the Machine Learning and Optimization communities, to solve our problem. We show for a wide range of scenarios that using our sampler can accelerate the convergence rate to high-quality solutions in high-dimensional problems.

We consider the problem of real-time motion planning that requires evaluating a minimal number of edges on a graph to quickly discover collision-free paths. Evaluating edges is expensive, both for robots with complex geometries like robot arms, and for robots sensing the world online like UAVs. Until now, this challenge has been addressed via laziness, i.e. deferring edge evaluation until absolutely necessary, with the hope that edges turn out to be valid. However, all edges are not alike in value - some have a lot of potentially good paths flowing through them, and some others encode the likelihood of neighbouring edges being valid. This leads to our key insight - instead of passive laziness, we can actively choose edges that reduce the uncertainty about the validity of paths. We show that this is equivalent to the Bayesian active learning paradigm of decision region determination (DRD). However, the DRD problem is not only combinatorially hard but also requires explicit enumeration of all possible worlds. We propose a novel framework that combines two DRD algorithms, DIRECT and BISECT, to overcome both issues. We show that our approach outperforms several state-of-the-art algorithms on a spectrum of planning problems for mobile robots, manipulators and autonomous helicopters.

In this paper, we introduce a Markov chain Monte Carlo (MCMC)method to solve multi-objective motion-planning problems. We formulate the problem of finding Pareto-optimal trajectories as a problem of sampling trajectories from a Pareto-optimal set. We define an implicit uniform distribution over the Pareto-frontier using a dominance function and then sample in the space of trajectories. The nature of MCMC guarantees the convergence to the Pareto-frontier, while the uniform distribution ensures the diversity of the trajectories. We also propose progressive objective evaluation to increase efficiency in problems with expensive-to-evaluate objective functions. This enables determination of dominance relationship between trajectories before they are entirely evaluated. We finally analyze the effectiveness of the framework and its applications in robotics.

Human collaborators coordinate effectively their actions through both verbal and non-verbal communication. We believe that the the same should hold for human-robot teams. We propose a formalism that enables a robot to decide optimally between taking a physical action toward task completion and issuing an utterance to the human teammate. We focus on two types of utterances: verbal commands, where the robot asks the human to take a physical action, and state-conveying actions, where the robot informs the human about its internal state, which captures the information that the robot uses in its decision making. Human subject experiments show that enabling the robot to issue verbal commands is the most effective form of communicating objectives, while retaining user trust in the robot. Communicating information about the robot’s state should be done judiciously, since many participants questioned the truthfulness of the robot statements when the robot did not provide sufficient explanation about its actions.

Anytime almost-surely asymptotically optimal planners, such as RRT*, incrementally find paths to every state in the search domain. This is inefficient once an initial solution is found as then only states that can provide a better solution need to be considered. Exact knowledge of these states requires solving the problem but can be approximated with heuristics. This paper formally defines these sets of states and demonstrates how they can be used to analyze arbitrary planning problems. It uses the well-known $L^2$ norm (i.e., Euclidean distance) to analyze minimum-path-length problems and shows that existing approaches decrease in effectiveness factorially (i.e., faster than exponentially) with state dimension. It presents a method to address this curse of dimensionality by directly sampling the prolate hyperspheroids (i.e., symmetric $n$-dimensional ellipses) that define the $L^2$ informed set. The importance of this direct informed sampling technique is demonstrated with Informed RRT*. This extension of RRT* has less theoretical dependence on state dimension and problem size than existing techniques and allows for linear convergence on some problems. It is shown experimentally to find better solutions faster than existing techniques on both abstract planning problems and HERB, a two-arm manipulation robot.

In human-robot teams, humans often start with an inaccurate model of the robot capabilities. As they interact with the robot, they infer the robot's capabilities and partially adapt to the robot, i.e., they might change their actions based on the observed outcomes and the robot's actions, without replicating the robot's policy. We present a game-theoretic model of human partial adaptation to the robot, where the human responds to the robot's actions by maximizing a reward function that changes stochastically over time, capturing the evolution of their expectations of the robot's capabilities. The robot can then use this model to decide optimally between taking actions that reveal its capabilities to the human and taking the best action given the information that the human currently has. We prove that under certain observability assumptions, the optimal policy can be computed efficiently. We demonstrate through a human subject experiment that the proposed model significantly improves human-robot team performance, compared to policies that assume complete adaptation of the human to the robot.

Shared autonomy integrates user input with robot autonomy in order to control a robot and help the user to complete a task. Our work aims to improve the performance of such a human-robot team: the robot tries to guide the human towards an effective strategy, sometimes against the human's own preference, while still retaining his trust. We achieve this through a principled human-robot mutual adaptation formalism. We integrate a bounded-memory adaptation model of the human into a partially observable stochastic decision model, which enables the robot to adapt to an adaptable human. When the human is adaptable, the robot guides the human towards a good strategy, maybe unknown to the human in advance. When the human is stubborn and not adaptable, the robot complies with the human's preference in order to retain their trust. In the shared autonomy setting, unlike many other common human-robot collaboration settings, only the robot actions can change the physical state of the world, and the human and robot goals are not fully observable. We address these challenges and show in a human subject experiment that the proposed mutual adaptation formalism improves human-robot team performance, while retaining a high level of user trust in the robot, compared to the common approach of having the robot strictly following participants' preference.

We consider the problem of computing shortest paths in a dense motion-planning roadmap G. We assume that n, the number of vertices of G, is very large. Thus, using any path-planning algorithm that directly searches G, running in O(VlogV + E) ≈ O(n2) time, becomes unacceptably expensive. We are therefore interested in anytime search to obtain successively shorter feasible paths and converge to the shortest path in G. Our key insight is to provide existing path-planning algorithms with a sequence of increasingly dense subgraphs of G. We study the space of all (r-disk) subgraphs of G. We then formulate and present two densification strategies for traversing this space which exhibit complementary properties with respect to problem difficulty. This inspires a third, hybrid strategy which has favourable properties regardless of problem difficulty. This general approach is then demonstrated and analyzed using the specific case where a low-dispersion deterministic sequence is used to generate the samples used for G. Finally we empirically evaluate the performance of our strategies for random scenarios in ℝ2and ℝ4and on manipulation planning problems for a 7 DOF robot arm, and validate our analysis.

In this work, we present an anytime planner for creating open-loop trajectories that solve rearrangement planning problems under uncertainty using nonprehensile manipulation. We first extend the Monte Carlo Tree Search algorithm to the unobservable domain. We then propose two default policies that allow us to quickly determine the potential to achieve the goal while accounting for the contact that is critical to rearrangement planning. The first policy uses a learned model generated from a set of user demonstrations. This model can be quickly queried for a sequence of actions that attempts to create contact with objects and achieve the goal. The second policy uses a heuristically guided planner in a subspace of the full state space. Using these goal informed policies, we are able to find initial solutions to the problem quickly, then continuously refine the solutions as time allows. We demonstrate our algorithm on a 7 degree-of-freedom manipulator moving objects on a table.

We estimate the state of a noisy robot arm and underactuated hand using an implicit Manifold Particle Filter (MPF) informed by contact sensors. As the robot touches the world, its state space collapses to a contact manifold that we represent implicitly using a signed distance field. This allows us to extend the MPF to higher (six or more) dimensional state spaces. Earlier work, which explicitly represents the contact manifold, was only capable of scaling to three dimensions. Through a series of experiments, we show that the implicit MPF converges faster and is more accurate than a conventional particle filter during periods of persistent contact. We present three methods of drawing samples from an implicit contact manifold, and compare them in experiments.

Although there is an abundance of planar fiducial-marker systems proposed for augmented reality and computer-vision purposes, using them to estimate the pose accurately in robotic applications where collected data are noisy remains a challenge. This is inherently a difficult problem because these fiducial marker systems work solely within the RGB image space and the resolution of cameras on robots is often constrained. As a result, small noise in the image would cause the tag's detection process to produce large pose estimation errors. This paper describes an algorithm that improves the pose estimation accuracy of square fiducial markers in difficult scenes by fusing information from RGB and depth sensors. The algorithm retains the high detection rate and low false positive rate characteristics of fiducial systems while making them much more robust to size, lighting and sensory noise for pose estimation. The improvements make the fiducial tags suitable for robotic tasks requiring high pose accuracy in the real world environment.

Trajectory optimization is a fundamental problem in robotics. While optimization of continuous control trajectories is well developed, many applications require both discrete and continuous, i.e. hybrid controls. Finding an optimal sequence of hybrid controls is challenging due to the exponential explosion of discrete control combinations. Our method, based on Differential Dynamic Programming (DDP), circumvents this problem by incorporating discrete actions inside DDP: we first optimize continuous mixtures of discrete actions, and, subsequently force the mixtures into fully discrete actions. Moreover, we show how our approach can be extended to partially observable Markov decision processes (POMDPs) for trajectory planning under uncertainty. We validate the approach in a car driving problem where the robot has to switch discrete gears and in a box pushing application where the robot can switch the side of the box to push. The pose and the friction parameters of the pushed box are initially unknown and only indirectly observable.

In human-robot collaborative tasks, incorporating qualitative information provided by humans can greatly enhance the robustness and efficacy of robot state estimation. We introduce an algorithmic framework to model qualitative information as quantitative constraints on and between states. Our approach, named Sequentially Constrained Hamiltonian Monte Carlo, integrates Hamiltonian dynamics into Sequentially Constrained Monte Carlo sampling. We are able to generate samples that satisfy arbitrarily complex, non-smooth and discontinuous constraints, which in turn allows us to support a wide range of qualitative information. We evaluate our approach for constrained sampling qualitatively and quantitatively with several classes of constraints. SCHMC significantly outperforms the Metropolis-Hastings algorithm (a standard Markov Chain Monte Carlo (MCMC) method) and the Hamiltonian Monte Carlo (HMC) method, in terms of both the accuracy of the sampling (for satisfying constraints) and the quality of approximation. Compared to Sequentially Constrained Monte Carlo (SCMC), which supports similar kinds of constraints, our SCHMC approach has faster convergence rates and lower parameter sensitivity.

Robotic motion-planning problems, such as a UAV flying fast in a partially-known environment or a robot arm moving around cluttered objects, require finding collision-free paths quickly. Typically, this is solved by constructing a graph, where vertices represent robot configurations and edges represent potentially valid movements of the robot between theses configurations. The main computational bottlenecks are expensive edge evaluations to check for collisions. State of the art planning methods do not reason about the optimal sequence of edges to evaluate in order to find a collision free path quickly. In this paper, we do so by drawing a novel equivalence between motion planning and the Bayesian active learning paradigm of decision region determination (DRD). Unfortunately, a straight application of ex- isting methods requires computation exponential in the number of edges in a graph. We present BISECT, an efficient and near-optimal algorithm to solve the DRD problem when edges are independent Bernoulli random variables. By leveraging this property, we are able to significantly reduce computational complexity from exponential to linear in the number of edges. We show that BISECT outperforms several state of the art algorithms on a spectrum of planning problems for mobile robots, manipulators, and real flight data collected from a full scale helicopter. Open-source code and details can be found here: https://github.com/sanjibac/matlablearningcollision_checking

People form beliefs about intentions and preferences of robots as they observe robot movement. However, robots rarely optimize their movement to allow people to easily determine state preferences. In this work, we define critical points along robot trajectories that convey information about state preferences: inflection points are changes in direction and compromise points are the relative proportion of preferred states to non-preferred ones. We contribute an approach for automatically generating trajectory demonstrations with specified critical points, and test observers' abilities to understand and generalize our robot's preferences based on our generated demonstrations. Our results show that inflection points helped participants understand state preference ordering and allowed them to more accurately predict paths through new environments, while compromise points hindered understanding. We conclude that robots should evaluate their trajectories for critical points to increase human observer understanding.

Assistive robotic arms are increasingly enabling users with upper extremity disabilities to perform activities of daily living on their own. However, the increased capability and dexterity of the arms also makes them harder to control with simple, low-dimensional interfaces like joysticks and sip-and-puff interfaces. A common technique to control a high-dimensional system like an arm with a low-dimensional input like a joystick is through switching between multiple control modes. However, our interviews with daily users of the Kinova JACO arm identified mode switching as a key problem, both in terms of time and cognitive load. We further confirmed objectively that mode switching consumes about 17.4% of execution time even for able-bodied users controlling the JACO. Our key insight is that using even a simple model of mode switching, like time optimality, and a simple intervention, like automatically switching modes, significantly improves user satisfaction.

In shared autonomy, user input and robot autonomy are combined to control a robot to achieve a goal. One often used strategy considers the user and autonomy as independent decision makers, with the system blending these decisions. However, this independence leads to suboptimal, and often frustrating, behavior. Instead, we propose a system that explicitly models the interplay between the user and assistance. Our approach centers around the idea of learning how users respond to assistance. We then propose a cost minimization framework for assisting while utilizing this learned model.

Much robotics research has focused on intent-expressive (legible) motion. However, algorithms that can autonomously generate legible motion have implicitly made the strong assumption of an omniscient observer, with access to the robot's configuration as it changes across time. In reality, human observers have a particular viewpoint, which biases the way they perceive the motion. In this work, we free robots from this assumption and introduce the notion of an observer with a specific point of view into legibility optimization. In doing so, we account for two factors: (1) depth uncertainty induced by a particular viewpoint, and (2) occlusions along the motion, during which (part of) the robot is hidden behind some object. We propose viewpoint and occlusion models that enable autonomous generation of viewpoint-based legible motions, and show through large-scale user studies that the produced motions are significantly more legible compared to those generated assuming an omniscient observer.

Mutual adaptation is critical for effective team collaboration. This paper presents a formalism for human-robot mutual adaptation in collaborative tasks. We propose the bounded-memory adaptation model (BAM), which captures human adaptive behaviors based on a bounded memory assumption. We integrate BAM into a partially observable stochastic model, which enables robot adaptation to the human. When the human is adaptive, the robot will guide the human towards a new, optimal collaborative strategy unknown to the human in advance. When the human is not willing to change their strategy, the robot adapts to the human in order to retain human trust. Human subject experiments indicate that the proposed formalism can significantly improve the effectiveness of human-robot teams, while human subject ratings on the robot performance and trust are comparable to those achieved by cross training, a state-of-the-art human-robot team training practice.

Sampling-based optimal planners, such as RRT*, almost-surely converge asymptotically to the optimal solution, but have provably slow convergence rates in high dimensions. This is because their commitment to finding the global optimum compels them to prioritize exploration of the entire problem domain even as its size grows exponentially. Optimization techniques, such as CHOMP, have fast convergence on these problems but only to local optima. This is because they are exploitative, prioritizing the immediate improvement of a path even though this may not find the global optimum of nonconvex cost functions.

This paper addresses the problem of rearrangement planning, i.e. to find a feasible trajectory for a robot that must interact with multiple objects in order to achieve a goal. We propose a planner to solve the rearrangement planning problem by considering two different types of actions: robot-centric and object-centric. Object-centric actions guide the planner to perform specific actions on specific objects. Robot-centric actions move the robot without object relevant intent, easily allowing simultaneous object contact and whole arm interaction. We formulate a hybrid planner that uses both action types. We evaluate the planner on tasks for a mobile robot and a household manipulator.

We present POMP (Pareto Optimal Motion Planner), an anytime algorithm for geometric path planning on roadmaps. For robots with several degrees of freedom, collision checks are computationally expensive and often dominate planning time. Our goal is to minimize the number of collision checks for obtaining the first feasible path and successively shorter feasible paths. We assume that the roadmaps we search over are embedded in a continuous ambient space, where nearby points tend to share the same collision state. This enables us to formulate a probabilistic model that computes the probability of unevaluated configurations being collision-free. We update the model over time as more checks are performed. This model lets us define a weighting function for roadmap edges that is related to the probability of the edge being in collision. Our approach is to trade off between these two weights, gradually prioritizing edge length over collision likelihood. We also show that this tradeoff is approximately equivalent to minimizing the expected path length, with a penalty of being in collision. Our experiments demonstrate that POMP performs comparably with RRTConnect and LazyPRM for the first feasible path, and BIT* for anytime performance, both in terms of collision checks and total planning time.

We propose a method for generating a configuration space path that closely follows a desired task space path despite the presence of obstacles. We formalize closeness via two path metrics based on the discrete Hausdorff and Frechet distances. Armed with these metrics, we can cast our problem as a trajectory optimization problem. We also present two techniques to assist our optimizer in the case of local minima by further constraining the trajectory Finally, we leverage shape matching analysis, the Procrustes metric, to compare with respect to only their shape.

Our human-robot collaboration research aims to improve the fluency and efficiency of interactions between humans and robots when executing a set of tasks in a shared workspace. During human-robot collaboration, a robot and a user must often complete a disjoint set of tasks that use an overlapping set of objects, without using the same object simultaneously. A key challenge is deciding what task the robot should perform next in order to facilitate fluent and efficient collaboration. Most prior work does so by first predicting the human's intended goal, and then selecting actions given that goal. However, it is often difficult, and sometimes impossible, to infer the human's exact goal in real time, and this serial predict-then-act method is not adaptive to changes in human goals. In this paper, we present a system for inferring a probability distribution over human goals, and producing assistance actions given that distribution in real time. The aim is to minimize the disruption caused by the nature of human-robot shared workspace. We extend recent work utilizing Partially Observable Markov Decision Processes (POMDPs) for shared autonomy in order to provide assistance without knowing the exact goal. We evaluate our system in a study with 28 participants, and show that our POMDP model outperforms state of the art predict-then-act models by producing fewer human-robot collisions and less human idling time.

As humans and robots collaborate together on spatial tasks, they must communicate clearly about the objects they are referencing. Communication is clearer when language is unambiguous which implies the use of spatial references and explicit perspectives. In this work, we contribute two studies to understand how people instruct a partner to identify and pick up objects on a table. We investigate spatial features and perspectives in human spatial references and compare word usage when instructing robots vs. instructing other humans. We then focus our analysis on the clarity of instructions with respect to perspective taking and spatial references. We find that only about 42% of instructions contain perspective-independent spatial references. There is a strong correlation between participants' accuracy in executing instructions and the perspectives that the instructions are given in, as well between accuracy and the number of spatial relations that were required for the instruction. We conclude that sentence complexity (in terms of spatial relations and perspective taking) impacts understanding, and we provide suggestions for automatic generation of spatial references.

How should we gather information to make effective decisions? A classical answer to this fundamental problem is given by the decision-theoretic value of information. Unfortunately, optimizing this objective is intractable, and myopic (greedy) approximations are known to perform poorly. In this paper, we introduce DiRECt, an efficient yet near-optimal algorithm for nonmyopically optimizing value of information. Crucially, DiRECt uses a novel surrogate objective that is: (1) aligned with the value of information problem (2) efficient to evaluate and (3) adaptive submodular. This latter property enables us to utilize an efficient greedy optimization while providing strong approximation guarantees. We demonstrate the utility of our approach on four diverse case-studies: touch-based robotic localization, comparison-based preference learning, wild-life conservation management, and preference elicitation in behavioral economics. In the first application, we demonstrate DiRECt in closed-loop on an actual robotic platform.

In the future, we envision domestic robots to play a large role in our everyday lives. This requires robots able to anticipate our needs and preferences and adapt their behavior. Since current robotics research takes place primarily in laboratory settings, it fails to take into account real users. In this work, we explore how organization occurs in the kitchen through a home study. Our analysis includes qualitative insights towards robot behavior during kitchen organization, an open source dataset of real life kitchens, and a proof-of-concept application of this dataset to the problem of object return.

Most motion in robotics is purely functional, planned to achieve the goal and avoid collisions. Such motion is great in isolation, but collaboration affords a human who is watching the motion and making inferences about it, trying to coordinate with the robot to achieve the task. This paper analyzes the benefit of planning motion that explicitly enables the collaborator's inferences on the success of physical collaboration, as measured by both objective and subjective metrics. Results suggest that legible motion, planned to clearly express the robot's intent, leads to more fluent collaborations than predictable motion, planned to match the collaborator's expectations. Furthermore, purely functional motion can harm coordination, which negatively affects both task efficiency, as well as the participants' perception of the collaboration.

We formulate and study the comprehensive multi-root (CMR) planning problem, in which feasible paths are desired between multiple regions. We propose two primary contributions which allow us to extend state-of-the-art sampling-based planners. First, we propose the notion of vertex coloring as a compact representation of the CMR objective on graphs. Second, we propose a method for deferring edge evaluations which do not advance our objective, by way of a simple criterion over these vertex colorings. The resulting approach can be applied to any CMR-agnostic graph-based planner which evaluates a sequence of edges. We prove that the theoretical performance of the colored algorithm is always strictly better than (or equal to) that of the corresponding uncolored version. We then apply the approach to the Probabalistic RoadMap (PRM) algorithm; the resulting Colored Probabalistic RoadMap (cPRM) is illustrated on 2D and 7D CMR problems.

We formalize the problem of adapting a demonstrated trajectory to a new start and goal configuration as an optimization problem over a Hilbert space of trajectories: minimize the distance between the demonstration and the new trajectory subject to the new end point constraints. We show that the commonly used version of Dynamic Movement Primitives (DMPs) implement this minimization in the way they adapt demonstrations, for a particular choice of the Hilbert space norm. The generalization to arbitrary norms enables the robot to select a more appropriate norm for the task, as well as learn how to adapt the demonstration from the user. Our experiments show that this can significantly improve the robot's ability to accurately generalize the demonstration.

In this paper, we present Batch Informed Trees (BIT*), a planning algorithm based on unifying graph- and sampling-based planning techniques. By recognizing that a set of samples describes an implicit random geometric graph (RGG), we are able to combine the efficient ordered nature of graph-based techniques, such as A*, with the anytime scalability of sampling-based algorithms, such as Rapidly-exploring Random Trees (RRT).

In this work we present a fast kinodynamic RRT-planner that uses dynamic nonprehensile actions to rearrange cluttered environments. In contrast to many previous works, the presented planner is not restricted to quasi-static interactions and monotonicity. Instead the results of dynamic robot actions are predicted using a black box physics model. Given a general set of primitive actions and a physics model, the planner randomly explores the configuration space of the environment to find a sequence of actions that transform the environment into some goal configuration. In contrast to a naive kinodynamic RRT-planner we show that we can exploit the physical fact that in an environment with friction any object eventually comes to rest. This allows a search on the configuration space rather than the state space, reducing the dimension of the search space by a factor of two without restricting us to non-dynamic interactions. We compare our algorithm against a naive kinodynamic RRT-planner and show that on a variety of environments we can achieve a higher planning success rate given a restricted time budget for planning.

Many robot applications involve lifelong planning in relatively static environments e.g. assembling objects or sorting mail in an office building. In these types of scenarios, the robot performs many tasks over a long period of time. Thus, the time required for computing a motion plan becomes a significant concern, prompting the need for a fast and efficient motion planner. Since these environments remain similar in between planning requests, planning from scratch is wasteful. Recently, Experience Graphs (E-Graphs) were proposed to accelerate the planning process by reusing parts of previously computed paths to solve new motion planning queries more efficiently. This work describes a method to improve planning times with E-Graphs given changes in the environment by lazily evaluating the validity of past experiences during the planning process. We show the improvements with our method in a single-arm manipulation domain with simulations on the PR2 robot.

We present a randomized kinodynamic planner that solves rearrangement planning problems. We embed a physics model into the planner to allow reasoning about interaction with objects in the environment. By carefully selecting this model, we are able to reduce our state and action space, gaining tractability in the search. The result is a planner capable of generating trajectories for full arm manipulation and simultaneous object interaction. We demonstrate the ability to solve more rearrangement by pushing tasks than existing primitive based solutions. Finally, we show the plans we generate are feasible for execution on a real robot.

We present an algorithm for generating open-loop trajectories that solve the problem of rearrangement planning under uncertainty. We frame this as a selection problem where the goal is to choose the most robust trajectory from a finite set of candidates. We generate each candidate using a kinodynamic state space planner and evaluate it using noisy rollouts. Our key insight is we can formalize the selection problem as the “best arm” variant of the multi-armed bandit problem. We use the successive rejects algorithm to efficiently allocate rollouts between candidate trajectories given a rollout budget. We show that the successive rejects algorithm identifies the best candidate using fewer rollouts than a baseline algorithm in simulation. We also show that selecting a good candidate increases the likelihood of successful execution on a real robot.

Robotics research often focuses on increasing robot capability. If end users do not perceive these increases, however, user acceptance may not improve. In this work, we explore the idea of perceived capability and how it relates to true capability, differentiating between physical and social capabilities. We present a framework that outlines their potential relationships, along with two user studies, on robot speed and speech, exploring these relationships. Our studies identify two possible consequences of the disconnect between the true and perceived capability: (1) under-perception: true improvements in capability may not lead to perceived improvements and (2) over-perception: true improvements in capability may lead to additional perceived improvements that do not actually exist.

How should we gather information to make effective decisions? We address Bayesian active learning and experimental design problems, where we sequentially select tests to reduce uncertainty about a set of hypotheses. Instead of minimizing uncertainty per se, we consider a set of overlapping decision regions of these hypotheses. Our goal is to drive uncertainty into a single decision region as quickly as possible. We identify necessary and sufficient conditions for correctly identifying a decision region that contains all hypotheses consistent with observations. We develop a novel Hyperedge Cutting (HEC) algorithm for this problem, and prove that is competitive with the intractable optimal policy. Our efficient implementation of the algorithm relies on computing subsets of the complete homogeneous symmetric polynomials. Finally, we demonstrate its effectiveness on two practical applications: approximate comparison-based learning and active localization using a robot manipulator.

As assistive robots become popular in factories and homes, there is greater need for natural, multi-channel communication during collaborative manipulation tasks. Non-verbal communication such as eye gaze can provide information without overloading more taxing channels like speech. However, certain collaborative tasks may draw attention away from these subtle communication modalities. For instance, robot-to-human handovers are primarily manual tasks, and human attention is therefore drawn to robot hands rather than to robot faces during handovers. In this paper, we show that a simple manipulation of a robot's handover behavior can significantly increase both awareness of the robot's eye gaze and compliance with that gaze. When eye gaze communication occurs during the robot's release of an object, delaying object release until the gaze is finished draws attention back to the robot's head, which increases conscious perception of the robot's communication. Furthermore, the handover delay increases peoples' compliance with the robot's communication over a non-delayed handover, even when compliance results in counterintuitive behavior.

No abstract available.

No abstract available.

We study the effect of familiarization on the predictability of robot motion. Predictable motion is motion that matches the observer's expectation. Because of the difficulty robots have in learning motion from user demonstrations, we explore the idea of having users learn from robot demonstrations --- how accurate do users get at predicting how the robot will move? We find that although familiarization significantly increases predictability, its utility depends on how natural the motion is. Overall, familiarization shows great promise, but needs to be combined with other methods that generate appropriate motion with which to be familiarized.

Functional gradient algorithms (e.g. CHOMP) have recently shown great promise for producing locally optimal motion for complex many degree-of-freedom robots. A key limitation of such algorithms is the difficulty in incorporating constraints and cost functions that explicitly depend on time. We present T-CHOMP, a functional gradient algorithm that overcomes this limitation by directly optimizing in space-time. We outline a framework for joint space-time optimization, derive an efficient trajectory-wide update for maintaining time monotonicity, and demonstrate the significance of T-CHOMP over CHOMP in several scenarios. By manipulating time, T-CHOMP produces lower-cost trajectories leading to behavior that is meaningfully different from CHOMP.

“In-hand manipulation” is the ability to reposition an object in the hand, for example when adjusting the grasp of a hammer before hammering a nail. The common approach to in-hand manipulation with robotic hands, known as dexterous manipulation [1], is to hold an object within the fingertips of the hand and wiggle the fingers, or walk them along the object's surface. Dexterous manipulation, however, is just one of the many techniques available to the robot. The robot can also roll the object in the hand by using gravity, or adjust the object's pose by pressing it against a surface, or if fast enough, it can even toss the object in the air and catch it in a different pose. All these techniques have one thing in common: they rely on resources extrinsic to the hand, either gravity, external contacts or dynamic arm motions. We refer to them as “extrinsic dexterity”. In this paper we study extrinsic dexterity in the context of regrasp operations, for example when switching from a power to a precision grasp, and we demonstrate that even simple grippers are capable of ample in-hand manipulation. We develop twelve regrasp actions, all open-loop and hand-scripted, and evaluate their effectiveness with over 1200 trials of regrasps and sequences of regrasps, for three different objects (see video [2]). The long-term goal of this work is to develop a general repertoire of these behaviors, and to understand how such a repertoire might eventually constitute a general-purpose in-hand manipulation capability.

This video presents the application of Extrinsic Dexterity to change the pose of an object in the hand, i.e., to regrasp the object.

Rapidly-exploring random trees (RRTs) are popular in motion planning because they find solutions efficiently to single-query problems. Optimal RRTs (RRT*s) extend RRTs to the problem of finding the optimal solution, but in doing so asymptotically find the optimal path from the initial state to every state in the planning domain. This behaviour is not only inefficient but also inconsistent with their single-query nature.

When one uses a hand-held tool, the fingers often make the tool to be in contact with the palm in the form of multi-contact manipulation. Multi-contact manipulation is useful for object-environment interaction tasks because it can provide both powerful grasping of the object body and dexterous manipulation of the object end-effector. However, dealing with the internal link contact with the object is not trivial. In this paper, we propose Reactional Internal Contact Hypothesis that regards the internal contact force as a reaction force so that the desired finger force can be reduced. By taking a handwriting task as an example, optimal configuration search and grasping force computation problems are addressed based on this hypothesis and validated via dynamic simulation.

Good communication is critical to seamless human-robot interaction. Among numerous communication channels, here we focus on gestures, and in particular on spacial deixis: pointing at objects in the environment in order to reference them. We propose a mathematical model that enables robots to generate pointing configurations that make the goal object as clear as possible - pointing configurations that are legible. We study the implications of legibility on pointing, e.g. that the robot will sometimes need to trade off efficiency for the sake of clarity. Finally, we test how well our model works in practice in a series of user studies, showing that the resulting pointing configurations make the goal object easier to infer for novice users.

In this paper, we consider the problem of Lifelong Robotic Object Discovery (LROD) as the long-term goal of discovering novel objects in the environment while the robot operates, for as long as the robot operates. As a first step towards LROD, we automatically process the raw video stream of an entire workday of a robotic agent to discover objects. We claim that the key to achieve this goal is to incorporate domain knowledge whenever available, in order to detect and adapt to changes in the environment. We propose a general graph-based formulation for LROD in which generic domain knowledge is encoded as constraints. Our formulation enables new sources of domain knowledge—metadata—to be added dynamically to the system, as they become available or as conditions change. By adding domain knowledge, we discover 2.7· more objects and decrease processing time 190 times. Our optimized implementation, HerbDisc, processes 6 h 20 min of RGBD video of real human environments in 18 min 30 s, and discovers 121 correct novel objects with their 3D models.

We investigate the problem of a robot searching for an object. This requires reasoning about both perception and manipulation: certain objects are moved because the target may be hidden behind them and others are moved because they block the manipulator's access to other objects. We contribute a formulation of the object search by manipulation problem using visibility and accessibility relations between objects. We also propose a greedy algorithm and show that it is optimal under certain conditions. We propose a second algorithm which is optimal under all conditions. This algorithm takes advantage of the structure of the visibility and accessibility relations between objects to quickly generate optimal plans. Finally, we demonstrate an implementation of both algorithms on a real robot using a real object detection system.

Many robotic systems deal with uncertainty by performing a sequence of information gathering actions. In this work, we focus on the problem of efficiently constructing such a sequence by drawing an explicit connection to submodularity. Ideally, we would like a method that finds the optimal sequence, taking the minimum amount of time while providing sufficient information. Finding this sequence, however, is generally intractable. As a result, many well-established methods select actions greedily. Surprisingly, this often performs well. Our work first explains this high performance - we note a commonly used metric, reduction of Shannon entropy, is submodular under certain assumptions, rendering the greedy solution comparable to the optimal plan in the offline setting. However, reacting online to observations can increase performance. Recently developed notions of adaptive submodularity provide guarantees for a greedy algorithm in this online setting. In this work, we develop new methods based on adaptive submodularity for selecting a sequence of information gathering actions online. In addition to providing guarantees, we can capitalize on submodularity to attain additional computational speedups. We demonstrate the effectiveness of these methods in simulation and on a robot.

We investigate the problem of estimating the state of an object during manipulation. Contact sensors provide valuable information about the object state during actions which involve persistent contact, e.g. pushing. However, contact sensing is very discriminative by nature, and therefore the set of object states that contact a sensor constitutes a lower-dimensional manifold in the state space of the object. This causes stochastic state estimation methods, such as particle filters, to perform poorly when contact sensors are used. We propose a new algorithm, the manifold particle filter, which uses dual particles directly sampled from the contact manifold to avoid this problem. The algorithm adapts to the probability of contact by dynamically changing the number of dual particles sampled from the manifold. We compare our algorithm to the conventional particle filter through extensive experiments and we show that our algorithm is both faster and better at estimating the state. Unlike the conventional particle filter, our algorithm's performance improves with increasing sensor accuracy and the filter's update rate. We implement the algorithm on a real robot using commercially available tactile sensors to track the pose of a pushed object.

In this paper, we explore a class of teleoperation problems where a user controls a sophisticated device (e.g. a robot) via an interface to perform a complex task. Teleoperation interfaces are fundamentally limited by the indirectness of the process, by the fact that the user is not physically executing the task. In this work, we study intelligent and customizable interfaces: these are interfaces that mediate the consequences of indirectness and make teleoperation more seamless. They are intelligent in that they take advantage of the robot's autonomous capabilities and assist in accomplishing the task. They are customizable in that they enable the users to adapt the retargetting function which maps their input onto the robot. Our studies support the advantages of such interfaces, but also point out the challenges they bring. We make three key observations. First, although assistance can greatly improve teleperation, the decision on how to provide assistance must be contextual. It must depend, for example, on the robot's confidence in its prediction of the user's intent. Second, although users do have the ability to provide intent-expressive input that simplifies the robot's prediction task, this ability can be hindered by kinematic differences between themselves and the robot. And third, although interface customization is important, it must be robust to poor examples from the user.

A handover is a complex collaboration, where actors coordinate in time and space to transfer control of an object. This coordination comprises two processes: the physical process of moving to get close enough to transfer the object, and the cognitive process of exchanging information to guide the transfer. Despite this complexity, we humans are capable of performing handovers seamlessly in a wide variety of situations, even when unexpected. This suggests a common procedure that guides all handover interactions. Our goal is to codify that procedure.

No abstract available.

A person practicing parkour is an incredible display of intelligent planning; he must reason carefully about his velocity and contact placement far into the future in order to locomote quickly through an environment. We seek to develop planners that will enable robotic systems to replicate this performance. An ideal planner can learn from examples and formulate feasible full-body plans to traverse a new environment. The proposed approach uses momentum equivalence to reduce the full-body system into a simplified one. Low-dimensional trajectory primitives are then composed by a sampling planner called Sampled Composition A* to produce candidate solutions that are adjusted by a trajectory optimizer and mapped to a full-body robot. Using primitives collected from a variety of sources, this technique is able to produce solutions to an assortment of simulated locomotion problems.

Planning motion for humanoid robots requires obeying simultaneous constraints on balance, collision-avoidance, and end-effector pose, among others. Several algorithms are able to generate configurations that satisfy these constraints given a good initial guess, i.e. a configuration which is already close to satisfying the constraints. However, when selecting goals for a planner a close initial guess is rarely available. Methods that attempt to satisfy all constraints through direct projection from a distant initial guess often fail due to opposing gradients for the various constraints, joint-limits, or singularities. We approach the problem of generating a constrained goal by searching for a configuration in the intersection of all constraint manifolds in configuration space (C-space). Starting with an initial guess, our algorithm, Constellation, builds a graph in C-space whose nodes are configurations that satisfy one or more constraints and whose cycles determine where the algorithm explores next. We compare the performance of our approach to direct projection and a previously-proposed cyclic projection method on reaching tasks for a humanoid robot with 33 DOF. We find that Constellation performs the best in terms of the number of solved queries across a wide range of problem difficulty. However, this success comes at higher computational cost.

During operation of robots large amounts of data are produced and processed for instance in perception, actuation, or decision making. Nowadays this data is typically volatile and disposed right after use. But this data can be valuable and useful later. Therefore we propose a database system that taps into common robot middleware to record any and all data produced at run-time. We present two examples using this data in fault analysis and performance evaluation and describe real-world experiments run on the domestic service robot HERB.

In teleoperation, the user's input is mapped onto the robot via a motion retargetting function. This function must differ between robots because of their different kinematics, between users because of their different preferences, and even between tasks that the users perform with the robot. Our work enables users to customize this retargetting function, and achieve any of these required differences. In our approach, the robot starts with an initial function. As the user teleoperates the robot, he can pause and provide example correspondences, which instantly update the retargetting function. We select the algorithm underlying these updates by formulating the problem as an instance of online function approximation. The problem's requirements, as well as the semantics and constraints of motion retargetting, lead to an extension of Online Learning with Kernel Machines in which the width of the kernel can vary. Our central hypothesis is that this method enables users to train retargetting functions to good outcomes. We validate this hypothesis in a user study, which also reveals the importance of providing users with tools to verify their examples: much like an actor needs a mirror to verify his pose, a user needs to verify his input before providing an example. We conclude with a demonstration from an expert user that shows the potential of the method for achieving more sophisticated customization that makes particular tasks easier to complete, once users get expertise with the system.

When performing physical collaboration tasks, like packing a picnic basket together, humans communicate strongly and often subtly via multiple channels like gaze, speech, gestures, movement and posture. Understanding and participating in this communication enables us to predict a physical action rather than react to it, producing seamless collaboration. In this paper, we automatically learn key discriminative features that predict the intent to handover an object using machine learning techniques. We train and test our algorithm on multi-channel vision and pose data collected from an extensive user study in an instrumented kitchen. Our algorithm outputs a tree of possibilities, automatically encoding various types of pre-handover communication. A surprising outcome is that mutual gaze and inter-personal distance, often cited as being key for interaction, were not key discriminative features. Finally, we discuss the immediate and future impact of this work for human-robot interaction.

We present the hardware design, software architecture, and core algorithms of Herb 2.0, a bimanual mobile manipulator developed at the Personal Robotics Lab at Carnegie Mellon University, Pittsburgh, PA. We have developed Herb 2.0 to perform useful tasks for and with people in human environments. We exploit two key paradigms in human environments: that they have structure that a robot can learn, adapt and exploit, and that they demand general-purpose capability in robotic systems. In this paper, we reveal some of the structure present in everyday environments that we have been able to harness for manipulation and interaction, comment on the particular challenges on working in human spaces, and describe some of the lessons we learned from extensively testing our integrated platform in kitchen and office environments.

For robots to get integrated in daily tasks assisting humans, robot-human interactions will need to reach a level of fluency close to that of human-human interactions. In this paper we address the fluency of robot-human hand-overs. From an observational study with our robot HERB, we identify the key problems with a baseline hand-over action. We find that the failure to convey the intention of handing over causes delays in the transfer, while the lack of an intuitive signal to indicate timing of the hand-over causes early, unsuccessful attempts to take the object. We propose to address these problems with the use of spatial contrast, in the form of distinct hand-over poses, and temporal contrast, in the form of unambiguous transitions to the hand-over pose. We conduct a survey to identify distinct hand-over poses, and determine variables of the pose that have most communicative potential for the intent of handing over. We present an experiment that analyzes the effect of the two types of contrast on the fluency of hand-overs. We find that temporal contrast is particularly useful in improving fluency by eliminating early attempts of the human.

One goal of assistive robotics is to design interactive robots that can help disabled people with tasks such as fetching objects. When people do this task, they coordinate their movements closely with receivers. We investigated how a robot should fetch and give household objects to a person. To develop a model for the robot, we first studied trained dogs and person-to-person handoffs. Our findings suggest two models of handoff that differ in their predictability and adaptivity.

Finding paths in high-dimensional spaces becomes difficult when we wish to optimize the cost of a path in addition to obeying feasibility constraints. Recently the T-RRT algorithm was presented as a method to plan in high-dimensional cost spaces and it was shown to perform well across a variety of problems. However, since the T-RRT relies solely on sampling to explore the space, it has difficulty navigating cost-space chasms narrow low-cost regions surrounded by increasing cost. Such chasms are particularly common in planning for manipulators because many useful cost functions induce narrow or lower dimensional low-cost areas. This paper presents the GradienT-RRT algorithm, which combines the T-RRT with a local gradient method to bias the search toward lower-cost regions. GradienT-RRT is effective at navigating chasms because it explores low-cost regions that are too narrow to explore by sampling alone. We compare the performance of T-RRT and GradienT-RRT on planning problems involving cost functions defined in workspace, task space, and C-space. We find that GradienT-RRT outperforms T-RRT in terms of the cost of the final path while maintaining better or comparable computation time. We also find that the cost of paths generated by GradienT-RRT is far less sensitive to changes in a key parameter, making it easier to tune the algorithm. Finally, we conclude with a demonstration of GradienT-RRT on a planning-with-uncertainty task on the physical HFRB robot.

The ability of a perception system to discern what is important in a scene and what is not is an invaluable asset, with multiple applications in object recognition, people detection and SLAM, among others. In this paper, we aim to analyze all sensory data available to separate a scene into a few physically meaningful parts, which we term structure, while discarding background clutter. In particular, we consider the combination of image and range data, and base our decision in both appearance and 3D shape. Our main contribution is the development of a framework to perform scene segmentation that preserves physical objects using multi-modal data. We combine image and range data using a novel mid-level fusion technique based on the concept of regions that avoids any pixel-level correspondences between data sources. We associate groups of pixels with 3D points into multi-modal regions that we term regionlets, and measure the structure-ness of each regionlet using simple, bottom-up cues from image and range features. We show that the highest-ranked regionlets correspond to the most prominent objects in the scene. We verify the validity of our approach on 105 scenes of household environments.

Goal sets are omnipresent in manipulation: picking up objects, placing them on counters or in bins, handing them off - all of these tasks encompass continuous sets of goals. This paper describes how to design optimal trajectories that exploit goal sets. We extend CHOMP (Covariant Hamiltonian Optimization for Motion Planning), a recent trajectory optimizer that has proven effective on high-dimensional problems, to handle trajectory-wide constraints, and relate the solution to the intuition of taking unconstrained steps and subsequently projecting them onto the constraints. We then show how this projection simplifies for goal sets (i.e. constraints that affect only the end-point). Finally, we present experiments on a personal robotics platform that show the importance of exploiting goal sets in trajectory optimization for day-to-day manipulation tasks.

Handing over objects to humans is an essential capability for assistive robots. While there are infinite ways to hand an object, robots should be able to choose the one that is best for the human. In this paper we focus on choosing the robot and object configuration at which the transfer of the object occurs, i.e. the hand-over configuration. We advocate the incorporation of user preferences in choosing hand-over configurations. We present a user study in which we collect data on human preferences and a human-robot interaction experiment in which we compare hand-over configurations learned from human examples against configurations planned using a kinematic model of the human. We find that the learned configurations are preferred in terms of several criteria, however planned configurations provide better reachability. Additionally, we find that humans prefer hand-overs with default orientations of objects and we identify several latent variables about the robot's arm that capture significant human preferences. These findings point towards planners that can generate not only optimal but also preferable hand-over configurations for novel objects.

Iteration is often sufficient for a simple hand to accomplish complex tasks, at the cost of an increase in the expected time to completion. In this paper, we minimize that overhead time by allowing a simple hand to abort early and retry as soon as it realizes that the task is likely to fail. We present two key contributions. First, we learn a probabilistic model of the relationship between the likelihood of success of a grasp and its grasp signature—the trace of the state of the hand along the entire grasp motion. Second, we model the iterative process of early abort and retry as a Markov chain and optimize the expected time to completion of the grasping task by effectively thresholding the likelihood of success. Experiments with our simple hand prototype tasked with grasping and singulating parts from a bin show that early abort and retry significantly increases efficiency.

Robots that operate in the real world will make mistakes. Thus, those who design and build systems will need to understand how best to provide ways for robots to mitigate those mistakes. Building on diverse research literatures, we consider how to mitigate breakdowns in services provided by robots. Expectancy-setting strategies forewarn people of a robot's limitations so people will expect mistakes. Recovery strategies, including apologies, compensation, and options for the user, aim to reduce the negative consequence of breakdowns. We tested these strategies in an online scenario study with 317 participants. A breakdown in robotic service had severe impact on evaluations of the service and the robot, but forewarning and recovery strategies reduced the negative impact of the breakdown. People's orientation toward services influenced which recovery strategy worked best. Those with a relational orientation responded best to an apology; those with a utilitarian orientation responded best to compensation. We discuss robotic service design to mitigate service problems.

We present a proof for the probabilistic completeness of RRT-based algorithms when planning with constraints on end-effector pose. Pose constraints can induce lower-dimensional constraint manifolds in the configuration space of the robot, making rejection sampling techniques infeasible. RRT-based algorithms can overcome this problem by using the sample-project method: sampling coupled with a projection operator to move configuration space samples onto the constraint manifold. Until now it was not known whether the sample-project method produces adequate coverage of the constraint manifold to guarantee probabilistic completeness. The proof presented in this paper guarantees probabilistic completeness for a class of RRT-based algorithms given an appropriate projection operator. This proof is valid for constraint manifolds of any fixed dimensionality.

Studies of human manipulation strategies suggest that pre-grasp object manipulation, such as rotation or sliding of the object to be grasped, can improve task performance by increasing both the task success rate and the quality of load-supporting postures. In previous demonstrations, pre-grasp object rotation by a robot manipulator was limited to manually-programmed actions. We present a method for automating the planning of pre-grasp rotation for object transport tasks. Our technique optimizes the grasp acquisition point by selecting a target object pose that can be grasped by high-payload manipulator configurations. Careful selection of the transition states leads to successful transport plans for tasks that are otherwise infeasible. In addition, optimization of the grasp acquisition posture also indirectly improves the transport plan quality, as measured by the safety margin of the manipulator payload limits.

We present an approach for efficiently recognizing all objects in a scene and estimating their full pose from multiple views. Our approach builds upon a state of the art single-view algorithm which recognizes and registers learned metric 3D models using local descriptors. We extend to multiple views using a novel multi-step optimization that processes each view individually and feeds consistent hypotheses back to the algorithm for global refinement. We demonstrate that our method produces results comparable to the theoretical optimum, a full multi-view generalized camera approach, while avoiding its combinatorial time complexity. We provide experimental results demonstrating pose accuracy, speed, and robustness to model error using a three-camera rig, as well as a physical implementation of the pose output being used by an autonomous robot executing grasps in highly cluttered scenes.

This paper describes a hierarchical planner deployed on a mobile manipulation system. The main idea is a two-level hierarchy combining a global planner which provides rough guidance to a local planner. We place a premium on fast response, so the global planner achieves speed by using a very rough approximation of the robot kinematics, and the local planner begins execution of the next action even without considering subsequent actions in detail, instead relying on the guidance of the global planner. The system exhibits few planning delays, and yet is surprisingly effective at planning collision free motions. The system is deployed on HERB, combining a Segway mobile platform, a WAM arm, and a Barrett hand. The navigation and manipulation components have been tested on the real robot, and the task of simultaneously approaching and grasping a bottle on a countertop was demonstrated in simulation.

The latency of a perception system is crucial for a robot performing interactive tasks in dynamic human environments. We present MOPED, a fast and scalable perception system for object recognition and pose estimation. MOPED builds on POSESEQ, a state of the art object recognition algorithm, demonstrating a massive improvement in scalability and latency without sacrificing robustness. We achieve this with both algorithmic and architecture improvements, with a novel feature matching algorithm, a hybrid GPU/CPU architecture that exploits parallelism at all levels, and an optimized resource scheduler. Using the same standard hardware, we achieve up to 30× improvement on real-world scenes.

We add to a manipulator's capabilities a new primitive motion which we term a push-grasp. While significant progress has been made in robotic grasping of objects and geometric path planning for manipulation, such work treats the world and the object being grasped as immovable, often declaring failure when simple motions of the object could produce success. We analyze the mechanics of push-grasping and present a quasi-static tool that can be used both for analysis and simulation. We utilize this analysis to derive a fast, feasible motion planning algorithm that produces stable pushgrasp plans for dexterous hands in the presence of object pose uncertainty and high clutter. We demonstrate our algorithm extensively in simulation and on HERB, a personal robotics platform developed at Intel Labs Pittsburgh.

For successful deployment, personal robots must adapt to ever-changing indoor environments. While dealing with novel objects is a largely unsolved challenge in AI, it is easy for people. In this paper we present a framework for robot supervision through Amazon Mechanical Turk. Unlike traditional models of teleoperation, people provide semantic information about the world and subjective judgements. The robot then autonomously utilizes the additional information to enhance its capabilities. The information can be collected on demand in large volumes and at low cost. We demonstrate our approach on the task of grasping unknown objects.

We present an approach to path planning for manipulators that uses Workspace Goal Regions (WGRs) to specify goal end-effector poses. Instead of specifying a discrete set of goals in the manipulator's configuration space, we specify goals more intuitively as volumes in the manipulator's workspace. We show that WGRs provide a common framework for describing goal regions that are useful for grasping and manipulation. We also describe two randomized planning algorithms capable of planning with WGRs. The first is an extension of RRT-JT that interleaves exploration using a Rapidly-exploring Random Tree (RRT) with exploitation using Jacobian-based gradient descent toward WGR samples. The second is the IKBiRRT algorithm, which uses a forward-searching tree rooted at the start and a backward-searching tree that is seeded by WGR samples. We demonstrate both simulation and experimental results for a 7DOF WAM arm with a mobile base performing reaching and pick-and-place tasks. Our results show that planning with WGRs provides an intuitive and powerful method of specifying goals for a variety of tasks without sacrificing efficiency or desirable completeness properties.

We present the Constrained Bi-directional Rapidly-Exploring Random Tree (CBiRRT) algorithm for planning paths in configuration spaces with multiple constraints. This algorithm provides a general framework for handling a variety of constraints in manipulation planning including torque limits, constraints on the pose of an object held by a robot, and constraints for following workspace surfaces. CBiRRT extends the Bi-directional RRT (BiRRT) algorithm by using projection techniques to explore the configuration space manifolds that correspond to constraints and to find bridges between them. Consequently, CBiRRT can solve many problems that the BiRRT cannot, and only requires one additional parameter: the allowable error for meeting a constraint. We demonstrate the CBiRRT on a 7DOF WAM arm with a 4DOF Barrett hand on a mobile base. The planner allows this robot to perform household tasks, solve puzzles, and lift heavy objects.

Robust perception is a vital capability for robotic manipulation in unstructured scenes. In this context, full pose estimation of relevant objects in a scene is a critical step towards the introduction of robots into household environments. In this paper, we present an approach for building metric 3D models of objects using local descriptors from several images. Each model is optimized to fit a set of calibrated training images, thus obtaining the best possible alignment between the 3D model and the real object. Given a new test image, we match the local descriptors to our stored models online, using a novel combination of the RANSAC and Mean Shift algorithms to register multiple instances of each object. A robust initialization step allows for arbitrary rotation, translation and scaling of objects in the test images. The resulting system provides markerless 6-DOF pose estimation for complex objects in cluttered scenes. We provide experimental results demonstrating orientation and translation accuracy, as well a physical implementation of the pose output being used by an autonomous robot to perform grasping in highly cluttered scenes.

We present GATMO (Generalized Approach to Tracking Movable Objects), a system for localization and mapping that incorporates the dynamic nature of the environment while maintaining semantic labels. Objects in the environment are broken down into multiple mobility levels, from static (walls) to highly mobile (people), by maintaining a history of object movement. Object classification is accomplished through a multi-layer, multi-hypothesis approach that does not rely on any static features such as shape or size. Maps are stored in an efficient manner that incorporates a history of previous orientations of each object. GATMO is initialized with a static map; it subsequently changes the map over time as objects in the map change position.

We explore the interconnection between search and action in the context of mobile robotics. The task of searching for an object and then performing some action with that object is important in many applications. Of particular interest to us is the idea of a robot assistant capable of performing worthwhile tasks around the home and office (e.g., fetching coffee, washing dirty dishes, etc.). We prove that some tasks allow for search and action to be completely decoupled and solved separately, while other tasks require the problems to be analyzed together. We complement our theoretical results with the design of a combined search/action approximation algorithm that draws on prior work in search. We show the effectiveness of our algorithm by comparing it to state-of-the-art solvers, and we give empirical evidence showing that search and action can be decoupled for some useful tasks. Finally, we demonstrate our algorithm on an autonomous mobile robot performing object search and delivery in an office environment.

Existing high-dimensional motion planning algorithms are simultaneously overpowered and underpowered. In domains sparsely populated by obstacles, the heuristics used by sampling-based planners to navigate “narrow passages” can be needlessly complex; furthermore, additional post-processing is required to remove the jerky or extraneous motions from the paths that such planners generate. In this paper, we present CHOMP, a novel method for continuous path refinement that uses covariant gradient techniques to improve the quality of sampled trajectories. Our optimization technique both optimizes higher-order dynamics and is able to converge over a wider range of input paths relative to previous path optimization strategies. In particular, we relax the collision-free feasibility prerequisite on input paths required by those strategies. As a result, CHOMP can be used as a standalone motion planner in many real-world planning queries. We demonstrate the effectiveness of our proposed method in manipulation planning for a 6-DOF robotic arm as well as in trajectory generation for a walking quadruped robot.

We present an efficient approach to generating paths for a robotic manipulator that are collision-free and guaranteed to meet task specifications despite pose uncertainty. We first describe how to use task space regions (TSRs) to specify grasping and object placement tasks for a manipulator. We then show how to modify a set of TSRs for a certain task to take into account pose uncertainty. A key advantage of this approach is that if the pose uncertainty is too great to accomplish a certain task, we can quickly reject that task without invoking a planner. If the task is not rejected we run the IKBiRRT planner, which trades-off exploring the robot's C-space with sampling from TSRs to compute a path. Finally, we show several examples of a 7-DOF WAM arm planning paths in a cluttered kitchen environment where the poses of all objects are uncertain.

We present a novel approach for determining robot movements that efficiently accomplish the robot's tasks while not hindering the movements of people within the environment. Our approach models the goal-directed trajectories of pedestrians using maximum entropy inverse optimal control. The advantage of this modeling approach is the generality of its learned cost function to changes in the environment and to entirely different environments. We employ the predictions of this model of pedestrian trajectories in a novel incremental planner and quantitatively show the improvement in hindrance-sensitive robot trajectory planning provided by our approach.

In this paper we develop a theory of metamodules and an associated distributed asynchronous planner which generalizes previous work on metamodules for lattice-based modular robotic systems. All extant modular robotic systems have some form of non-holonomic motion constraints. This has prompted many researchers to look to metamodules, i.e., groups of modules that act as a unit, as a way to reduce motion constraints and the complexity of planning. However, previous metamodule designs have been specific to a particular modular robot. By analyzing the constraints found in modular robotic systems we develop a holonomic metamodule which has two important properties: (1) it can be used as the basic unit of an efficient planner and (2) it can be instantiated by a wide variety of different underlying modular robots, e.g., modular robot arms, expanding cubes, hex-packed spheres, etc. Using a series of transformations we show that our practical metamodule system has a provably complete planner. Finally, our approach allows the task of shape transformation to be separated into a planning task and a resource allocation task. We implement our planner for two different metamodule systems and show that the time to completion scales linearly with the diameter of the ensemble.

This paper explores the planning and control of a manipulation task accomplished in conditions of high uncertainty. Statistical techniques, like particle filters, provide a framework for expressing the uncertainty and partial observability of the real world and taking actions to reduce them. We explore a classic manipulation problem of planar batting, but with a new twist of shape, pose and impact uncertainty. We demonstrate a technique for characterizing and reducing this uncertainty using a particle filter coupled with a lookahead planner that maximizes information gain. We show that a two-step planner that first acts for information gain and then acts to maximize the expectation of achieving a desired goal is effective at managing shape, pose and impact uncertainty

Motion planning for a self-reconfigurable robot involves coordinating the movement and connectivity of each of its homogeneous modules. Reconfiguration occurs when the shape of the robot changes from some initial configuration to a target configuration. Finding an optimal solution to reconfiguration problems involves searching the space of possible robot configurations. As this space grows exponentially with the number of modules, optimal planning becomes intractable. We propose a hierarchical planning approach that computes heuristic global reconfiguration strategies efficiently. Our approach consists of a base planner that computes an optimal solution for a few modules and a hierarchical planner that calls this base planner or reuses pre-computed plans at each level of the hierarchy to ultimately compute a global suboptimal solution. We present results from a prototype implementation of the method that efficiently plans for self-reconfigurable robots with several thousand modules. We also discuss tradeoffs and performance issues including scalability, heuristics and plan optimality

We explore the control synthesis problem for a robot dynamically manipulating an object in the presence of multiple frictional contacts. Contacts occur both between the object and the robot, and between the object and the environment. Two sets of constraints govern the evolution of the system — contact velocity constraints that prevent separation and cause rolling, and, contact force constraints that arise from Coulomb friction. We combine the constraints in the space of contact accelerations, obtaining bounds on the robot acceleration as a function of the system state. We solve the motion planning problem by providing a feasible path for the system and generating the controls and the system trajectory by time-scaling the feasible path. We provide examples that illustrate the merits and limitations of our technique and discuss some of the open problems.

This paper addresses the planning and control of dynamic contact manipulation. In an earlier paper (Srinivasa et al., 2005), we derived a constraint on the robot joint accelerations that needed to be satisfied to obtain a desired contact mode and a desired dynamic motion of the object. We proposed a technique for trajectory planning which involved planning a path in the system configuration space followed by time-scaling the path to satisfy dynamic constraints. This paper tackles a problem where only a small set of paths can be time-scaled to satisfy the constraints. We note that the dynamic constraints depend only on a subspace of the system state space. Projecting the dynamics and the constraints onto the subspace allows us to compute an analytical solution for the trajectory generation problem. We generate controllable simulations by allowing the user to control the system in the space orthogonal to the projection. We also demonstrate the construction of feedback controllers using dynamic programming.

We explore the control of a nonholonomic robot subject to additional constraints on the state variables. In our problem, the user specifies the path of a subset of the state variables (the task freedoms X/sub P/), i.e. a curve X/sub P/(s) where s/spl isin/[0,1] is a parameterization that the user chooses. We control the trajectory of the task freedoms by specifying a bilateral time-scaling s(t) which assigns a point on the path for each time t. The time-scaling is termed bilateral because there is no restriction on s(t), the task freedoms are allowed to move backwards along the path. We design a controller that satisfies the user directive and controls the remaining state variables (the shape freedoms X/sub R/) to satisfy the constraints. Furthermore, we attempt to reduce the number of control switchings, as these result in relatively large errors in our system state. If a constraint is close to being violated (at a switchings point), we back up X/sub P/ along the path for a small time interval and move X/sub S/ to an open region. We show that there are a finite number of switching points for arbitrary task freedom paths. We implement our control scheme on the Mobipulator and discuss a generalization to arbitrary systems satisfying similar properties.

We introduce an algorithm to cover an unknown space with a homogeneous team of circular mobile robots. Our approach is based on a single robot coverage algorithm, a boustrophedon approach, which divides the target two-dimensional space into regions called cells, each of which can be covered with simple back and forth motions. Single robot coverage is then achieved by ensuring that the robot visits each cell. The new multi-robot coverage algorithm uses the same planar cell-based approach as the single robot approach, but also prescribes the methods by which multiple robots cover a cell, teams are allocated among cells, and sub-teams of robots share information in a minimalistic manner. The advantage of this method is that planning occurs in a two dimensional configuration space for a team of n robots, bypassing the need to plan in a 2n dimensional configuration space. The approach is semi-decentralized: robot teams cover the space independent of each other, but robots within a team communicate state and share information.

This paper summarizes ongoing work with a mo- bile manipulator (Mobipulator ). We describe the sys- tem architecture of the latest version of the robot, a hierarchy of robot motion commands (the Mobipula- tion library) that can be snapped together to generate complicated paths easily, a configuration space plan- ner that plans wheel motions to manipulate paper, and a visual servoing system to monitor and correct errors in robot motion.