Reid G. Simmons

ICLR Conference 2025 Conference Paper

Conformalized Interactive Imitation Learning: Handling Expert Shift and Intermittent Feedback

• Michelle Zhao
• Henny Admoni
• Reid G. Simmons
• Aaditya Ramdas
• Andrea Bajcsy

In interactive imitation learning (IL), uncertainty quantification offers a way for the learner (i.e. robot) to contend with distribution shifts encountered during deployment by actively seeking additional feedback from an expert (i.e. human) online. Prior works use mechanisms like ensemble disagreement or Monte Carlo dropout to quantify when black-box IL policies are uncertain; however, these approaches can lead to overconfident estimates when faced with deployment-time distribution shifts. Instead, we contend that we need uncertainty quantification algorithms that can leverage the expert human feedback received during deployment time to adapt the robot's uncertainty online. To tackle this, we draw upon online conformal prediction, a distribution-free method for constructing prediction intervals online given a stream of ground-truth labels. Human labels, however, are intermittent in the interactive IL setting. Thus, from the conformal prediction side, we introduce a novel uncertainty quantification algorithm called intermittent quantile tracking (IQT) that leverages a probabilistic model of intermittent labels, maintains asymptotic coverage guarantees, and empirically achieves desired coverage levels. From the interactive IL side, we develop ConformalDAgger, a new approach wherein the robot uses prediction intervals calibrated by IQT as a reliable measure of deployment-time uncertainty to actively query for more expert feedback. We compare ConformalDAgger to prior uncertainty-aware DAgger methods in scenarios where the distribution shift is (and isn't) present because of changes in the expert's policy. We find that in simulated and hardware deployments on a 7DOF robotic manipulator, ConformalDAgger detects high uncertainty when the expert shifts and increases the number of interventions compared to baselines, allowing the robot to more quickly learn the new behavior.

ICRA Conference 2024 Conference Paper

Multi-Agent Strategy Explanations for Human-Robot Collaboration

• Ravi Pandya
• Michelle Zhao
• Changliu Liu
• Reid G. Simmons
• Henny Admoni

As robots are deployed in human spaces, it is important that they are able to coordinate their actions with the people around them. Part of such coordination involves ensuring that people have a good understanding of how a robot will act in the environment. This can be achieved through explanations of the robot’s policy. Much prior work in explainable AI and RL focuses on generating explanations for single-agent policies, but little has been explored in generating explanations for collaborative policies. In this work, we investigate how to generate multi-agent strategy explanations for human-robot collaboration. We formulate the problem using a generic multi-agent planner, show how to generate visual explanations through strategy-conditioned landmark states and generate textual explanations by giving the landmarks to an LLM. Through a user study, we find that when presented with explanations from our proposed framework, users are able to better explore the full space of strategies and collaborate more efficiently with new robot partners.

IROS Conference 2024 Conference Paper

Understanding Robot Minds: Leveraging Machine Teaching for Transparent Human-Robot Collaboration Across Diverse Groups

• Suresh Kumaar Jayaraman
• Reid G. Simmons
• Aaron Steinfeld
• Henny Admoni

In this work, we aim to improve transparency and efficacy in human-robot collaboration by developing machine teaching algorithms suitable for groups with varied learning capabilities. While previous approaches focused on tailored approaches for teaching individuals, our method teaches teams with various compositions of diverse learners using team belief representations. We investigate various group teaching strategies, such as focusing on individual beliefs or the group’s collective beliefs, and assess their impact on learning robot policies for different team compositions. Our findings reveal that team belief strategies produce less variation in learning duration and better accommodate diverse teams compared to individual belief strategies, suggesting their suitability in mixed proficiency settings with limited resources. In contrast, individual belief strategies provide a more uniform knowledge level, particularly effective for homogeneously inexperienced groups. Our study indicates that the effectiveness of the teaching strategy is significantly influenced by team composition and learner proficiency, highlighting the importance of real-time assessment of learner proficiency and adapting teaching approaches based on learner proficiency for optimal teaching outcomes.

IROS Conference 2022 Conference Paper

Coordination With Humans Via Strategy Matching

• Michelle Zhao
• Reid G. Simmons
• Henny Admoni

Human and robot partners increasingly need to work together to perform tasks as a team. Robots designed for such collaboration must reason about how their task-completion strategies interplay with the behavior and skills of their human team members as they coordinate on achieving joint goals. Our goal in this work is to develop a computational framework for robot adaptation to human partners in human-robot team collaborations. We first present an algorithm for autonomously recognizing available task-completion strategies by observing human-human teams performing a collaborative task. By transforming team actions into low dimensional representations using hidden Markov models, we can identify strategies without prior knowledge. Robot policies are learned on each of the identified strategies to construct a Mixture-of-Experts model that adapts to the task strategies of unseen human partners. We evaluate our model on a collaborative cooking task using an Overcooked simulator. Results of an online user study with 125 participants demonstrate that our framework improves the task performance and collaborative fluency of human-agent teams, as compared to state of the art reinforcement learning methods.

IROS Conference 2022 Conference Paper

Reasoning about Counterfactuals to Improve Human Inverse Reinforcement Learning

• Michael S. Lee
• Henny Admoni
• Reid G. Simmons

To collaborate well with robots, we must be able to understand their decision making. Humans naturally infer other agents' beliefs and desires by reasoning about their observable behavior in a way that resembles inverse reinforcement learning (IRL). Thus, robots can convey their beliefs and desires by providing demonstrations that are informative for a human learner's IRL. An informative demonstration is one that differs strongly from the learner's expectations of what the robot will do given their current understanding of the robot's decision making. However, standard IRL does not model the learner's existing expectations, and thus cannot do this counterfactual reasoning. We propose to incorporate the learner's current understanding of the robot's decision making into our model of human IRL, so that a robot can select demonstrations that maximize the human's understanding. We also propose a novel measure for estimating the difficulty for a human to predict instances of a robot's behavior in unseen environments. A user study finds that our test difficulty measure correlates well with human performance and confidence. Interestingly, considering human beliefs and counterfactuals when selecting demonstrations decreases human performance on easy tests, but increases performance on difficult tests, providing insight on how to best utilize such models.

ICAPS Conference 2017 Conference Paper

Plan-Time Multi-Model Switching for Motion Planning

• Breelyn Melissa Kane Styler
• Reid G. Simmons

Robot navigation through non-uniform environments requires reliable motion plan generation. The choice of planning model fidelity can significantly impact performance. Prior research has shown that reducing model fidelity saves planning time, but sacrifices execution reliability. While current adaptive hierarchical motion planning techniques are promising, we present a framework that leverages a richer set of robot motion models at plan-time. The framework chooses when to switch models and what model is most applicable within a single trajectory. For instance, more complex environment locales require higher fidelity models, while lower fidelity models are sufficient for simpler parts of the planning space, thus saving plan time. Our algorithm continuously aims to pick the model that best handles the current local environment. This effectively generates a single, mixed-fidelity plan. We present results for a simulated mobile robot with attached trailer in a hospital domain. We compare using a single motion planning model to switching with our framework of multiple models. Our results demonstrate that multi-fidelity model switching increases plan-time efficiency without sacrificing execution reliability.

IROS Conference 2017 Conference Paper

The datum particle filter: Localization for objects with coupled geometric datums

• Shiyuan Chen
• Brad Saund
• Reid G. Simmons

In this paper, we propose a touch-based localization approach for a potentially large and complex object with multiple internal degrees of freedom. Should a task only require a partial localization of the object, our method selects the appropriate information gathering actions to register the desired features. We use probabilistic methods to reason over the distribution of the estimated object poses in the 6-DOF configuration space. We introduce the datum-based particle filter to handle intrinsic tolerances between each of the sections of the object. We describe two alternative methods for the particle filter system: one using the full joint belief and the other reasonably simplifying the belief to achieve a better ability to scale. We present simulation results for both proposed methods to show the advantages of our approaches.

ICRA Conference 2017 Conference Paper

Touch based localization of parts for high precision manufacturing

• Brad Saund
• Shiyuan Chen
• Reid G. Simmons

Performing detailed work on objects requires precise localization. Currently humans aid machines in localization either by direct operation, or implicitly by designing a sequence of actions a robot follows. Our approach to automate localization is to reason over many potential actions, perform the best information gathering action, and then use the measurement obtained to update a non-Gaussian belief. We propose a method for autonomous localization of objects with initial 6DOF uncertainty capable of reasoning about and performing measurements with low uncertainty and arbitrary error models. Surprisingly, common methods capable of modeling arbitrary belief distributions perform poorly as measurement uncertainty decreases, so we modify a particle filter to handle these accurate measurements produced by tactile or laser sensors. We then show how the expected information gain of the proposed measurement can be calculated efficiently from these particles. We present experiments, both in simulation and on hardware, that show our method is both fast and accurate.

IROS Conference 2016 Conference Paper

Expressive path shape (swagger): Simple features that illustrate a robot's attitude toward its goal in real time

• Heather Knight
• Ravenna Thielstrom
• Reid G. Simmons

Expressive motion can situate a robot's attitude in its task motions, illustrating real-time reactions. Inspired by acting movement training, we construct path shape features that layer expression into a mobile robot's motion traversal. Our video-study results show that simple variations of path shape and orientation can influence human perceptions of a robot's task, focus, and confidence. We further find that sequencing path features is a useful way to create expressions that are pinpointed in time without requiring changes in velocity. Our quantitative features represent the Laban Space Effort: using path shape and orientation along the path to communicate the direct or indirect attitude of the robot toward its target destination (acting vocabulary italicized). These features illustrate expressive or stylistic aspects of the robot's inner state, filling a gap in the pre-existing literature that has mostly focused on task legibility. Our future work will evaluate temporal and spatial robot motion features in explicit interaction contexts.

ICRA Conference 2016 Conference Paper

Laban head-motions convey robot state: A call for robot body language

• Heather Knight
• Reid G. Simmons

Functional robots are an increasing presence in shared human-machine environments. Humans efficiently parse motion expressions, gaining an immediate impression of an agent's current action and state. Past work has shown that motion can effectively reveal a robot's current task objective to bystanders and collaborators, however, the layering of expression on pre-existing robot task motions has yet to be explored. Rather than showing us what the robot is doing, these layered motion characteristics leverage the how of the task motions to convey additional robot attitudes, e. g. , confidence, adherence to deadline or flexibility of attention. To lay the foundations for this objective, we adapt the Laban Efforts, a system from dance and acting training in use for over 50 years. We operationalize features representing the four Laban Efforts (Time, Space, Weight, and Flow) to the movements of a 2-DOF Nao head and a 4-DOF Keepon robot during simple dance and look-for-someone behaviors. Using online survey, we collect 1028 motion ratings for 72 robot motion videos depicting contrasting Effort motion examples. We achieve statistically significant legibility results for all four Effort implementations. Even without human degrees of freedom, we find that robot motion patterns can convey complex expressions to people.

ICAPS Conference 2016 Conference Paper

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

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

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

ICRA Conference 2015 Conference Paper

Mobile manufacturing of large structures

• David A. Bourne
• Howie Choset
• Humphrey Hu
• George Kantor
• Chris Niessl
• Zachary B. Rubinstein
• Reid G. Simmons
• Stephen F. Smith

Assembly of large structures requires large fixtures, often referred to as monuments. Their cost and massive size limit flexibility and scalability of the manufacturing process. Numerous small mobile robots can replace these large structures and, therefore, replicate the efficiency of the assembly line with far more flexibility. An assembly line made up of mobile manipulators can easily and rapidly be reconfigured to support scalability and a varied product mix, while allowing for near optimal resource assignment. The challenge to using small robots in place of monuments is making their joint behavior precise enough to accomplish the task and efficient enough to execute subtasks in a reasonable period of time. In this paper, we describe a set of techniques that we combine to achieve the necessary precision and overall efficiency to build a large structure. We describe and demonstrate these techniques in the context of a testbed we implemented for assembling a wing ladder.

ICRA Conference 2015 Conference Paper

Plan execution monitoring through detection of unmet expectations about action outcomes

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

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

ICRA Conference 2014 Conference Paper

Focused optimization for online detection of anomalous regions

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

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

ICRA Conference 2013 Conference Paper

Estimating human interest and attention via gaze analysis

• Heather Knight
• Reid G. Simmons

In this paper we analyze joint attention between a robot that presents features of its surroundings and its human audience. In a statistical analysis of hand-coded video data, we find that the robot's physical indications lead to a greater attentional coherence between robot and humans than do its verbal indications. We also find that aspects of how the tour group participants look at robot-indicated objects, including when they look and how long they look, can provide statistically significant correlations with their self-reported engagement scores of the presentations. Higher engagement would suggest a greater degree of interest in, and attention to, the material presented. These findings will seed future gaze tracking systems that will enable robots to estimate listeners' state. By tracking audience gaze, our goal is to enable robots to cater the type of content and manner of its presentation to the preferences or educational goals of a particular crowd, e. g. in a tour guide, classroom or entertainment setting.

IROS Conference 2012 Conference Paper

Graph-based trajectory planning through programming by demonstration

• Nik A. Melchior
• Reid G. Simmons

As robots are utilized in a growing number of applications, the ability to teach them to perform tasks safely and accurately becomes ever more critical. Programming by demonstration offers an expressive means for teaching while being accessible to domain experts who may be novices in robotics. This work investigates a programming by demon- stration approach to learning motion trajectories for robotic manipulator tasks. Using a graph constructed to determine correspondences between multiple imperfect demonstrations, the robot learner plans novel trajectories that safely and smoothly generalize the teacher's behavior, while attenuating those imperfections. The learner also actively detects instances of diverging strategy between examples, requesting advice for resolving these ambiguities. We demonstrate our approach in example domains with a 7 degree-of-freedom manipulator.

IROS Conference 2012 Conference Paper

Motion interference detection in mobile robots

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

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

ICAPS Conference 2012 Conference Paper

Risk-Variant Policy Switching to Exceed Reward Thresholds

• Breelyn Melissa Kane Styler
• Reid G. Simmons

This paper presents a decision-theoretic planning approach for probabilistic environments where the agent's goal is to win, which we model as maximizing the probability of being above a given reward threshold. In competitive domains, second is as good as last, and it is often desirable to take risks if one is in danger of losing, even if the risk does not pay off very often. Our algorithm maximizes the probability of being above a particular reward threshold by dynamically switching between a suite of policies, each of which encodes a different level of risk. This method does not explicitly encode time or reward into the state space, and decides when to switch between policies during each execution step. We compare a risk-neutral policy to switching among different risk-sensitive policies, and show that our approach improves the agent's probability of winning.

IROS Conference 2012 Conference Paper

Sensor fusion for human safety in industrial workcells

• Paul E. Rybski
• Peter Anderson-Sprecher
• Daniel Huber
• Chris Niessl
• Reid G. Simmons

Current manufacturing practices require complete physical separation between people and active industrial robots. These precautions ensure safety, but are inefficient in terms of time and resources, and place limits on the types of tasks that can be performed. In this paper, we present a real-time, sensor-based approach for ensuring the safety of people in close proximity to robots in an industrial workcell. Our approach fuses data from multiple 3D imaging sensors of different modalities into a volumetric evidence grid and segments the volume into regions corresponding to background, robots, and people. Surrounding each robot is a danger zone that dynamically updates according to the robot's position and trajectory. Similarly, surrounding each person is a dynamically updated safety zone. A collision between danger and safety zones indicates an impending actual collision, and the affected robot is stopped until the problem is resolved. We demonstrate and experimentally evaluate the concept in a prototype industrial workcell augmented with stereo and range cameras.

ICRA Conference 2012 Conference Paper

Voxel-based motion bounding and workspace estimation for robotic manipulators

• Peter Anderson-Sprecher
• Reid G. Simmons

Identification of regions in space that a robotic manipulator can reach in a given amount of time is important for many applications, such as safety monitoring of industrial manipulators and trajectory and task planning. However, due to the high-dimensional configuration space of many robots, reasoning about possible physical motion is often intractable. In this paper, we propose a novel method for creating a reachability grid, a voxel-based representation that estimates the minimum time needed for a manipulator to reach any physical location within its workspace. We use up to second-degree constraints on joint motion to model motion limits for each joint independently, followed by successive voxel approximations to map these limits on to the robot's physical workspace. Results using a simulated manipulator indicate that our method can produce accurate reachability grids in real-time, even for robots with many degrees of freedom. Furthermore, errors are almost exclusively biased towards producing more optimistic reachability estimates, which is a desirable characteristic for many applications.

ICRA Conference 2011 Conference Paper

Background subtraction and accessibility analysis in evidence grids

• Peter Anderson-Sprecher
• Reid G. Simmons
• Daniel Huber

Evidence grids are a popular representation for fused data from multiple sensors. Previous attempts at back-ground subtraction within evidence grids either do so prior to sensor fusion or do so naively, simply ignoring any cells with a high background occupancy probability. A key weakness of these approaches is that they cannot reason about interiors of objects or other unobserved regions. Recognizing and removing solid object interiors is important for any application that must be able to differentiate between occupied and unknown space after background subtraction. In this paper, we propose accessibility analysis as a method for the removal of interior regions. We then present and compare two approaches for performing background subtraction with accessibility analysis in evidence grids. Performance is measured using a 3D evidence grid in a test bed for a sensing system designed for use in safety monitoring of an automated assembly workcell. Within the parameters of the present study, both techniques allow for precise detection of foreground objects while fully removing background objects. Subtraction runs in near real-time, even for large grids.

ICRA Conference 2010 Conference Paper

Dimensionality reduction for trajectory learning from demonstration

• Nik A. Melchior
• Reid G. Simmons

Programming by demonstration is an attractive model for allowing both experts and non-experts to command robots' actions. In this work, we contribute an approach for learning precise reaching trajectories for robotic manipulators. We use dimensionality reduction to smooth the example trajectories and transform their representation to a space more amenable to planning. Key to this approach is the careful selection of neighboring points within and between trajectories. This algorithm is capable of creating efficient, collision-free plans even under typical real-world training conditions such as incomplete sensor coverage and lack of an environment model, without imposing additional requirements upon the user such as constraining the types of example trajectories provided. Experimental results are presented to validate this approach.

IROS Conference 2009 Conference Paper

Mobile robotic dynamic tracking for assembly tasks

• Bradley Hamner
• Seth Koterba
• Jane Shi
• Reid G. Simmons
• Sanjiv Singh

Traditional industrial robots have been widely used in automotive manufacturing for nearly 30 years. However, there have been very few attempts to automate mobile robotic systems for final assembly operations, despite their potential for high flexibility and capability. This paper focuses on methods of tracking a dynamic moving vehicle that is similar to the vehicle body on a moving assembly line. We have investigated two tracking methods, one using a laser scanner and the other using a visual fiducial marker. We have also studied the tracking performance of a mobile base using the pure pursuit algorithm with low pass filtering. Experimental results are presented to illustrate the remaining main challenges in achieving robotic assembly on moving assembly lines.

IROS Conference 2009 Conference Paper

Variable sized grid cells for rapid replanning in dynamic environments

• Rachel Kirby
• Reid G. Simmons
• Jodi Forlizzi

This paper presents a method for improving the runtime of an optimal heuristic path planner (A*) so that it can run repeatedly, in real-time, in a dynamic environment. This is necessary for mobile robots navigating in dynamic environments that have moving obstacles with associated costs, such as personal space around people or buffer zones around dangerous vehicles. Our approach is to modify the search space used by the A* algorithm, increasing the size of grid cells further from the robot. This approach relies on the notion that only the area closest to the robot needs to be searched carefully; areas further from the robot can be searched more coarsely. Because the planner is assumed to run repeatedly as the robot moves, the robot will always have a fine-grained path defined for its next action. We have experimentally verified in simulation that this algorithm can be run in real-time and produces paths that are comparable to full-resolution planning.

ICRA Conference 2008 Conference Paper

Duration prediction for proactive replanning

• Brennan Sellner
• Reid G. Simmons

Proactive replanning attempts to predict scheduling problems or opportunities and adapt to them throughout a schedule's execution. By continuously predicting a task's remaining duration, a proactive replanner is able to accommodate upcoming problems or opportunities before they manifest themselves. We have developed a kernel density estimation-based method for predicting a task's duration distribution as it executes, and have integrated our prediction algorithm with an existing planner based on heuristic repair. Our predictor allows the planner to anticipate problems, or opportunities, early enough to avoid, or take advantage of, them, resulting in executed schedules that score significantly higher on a number of metrics. We have evaluated a limited form of our approach in simulation, and present the results of our experiments. The addition of duration prediction resulted in a 11. 1% improvement in average reward. Compared with an omniscient planner, this is 45. 0% of the maximum possible improvement.

IROS Conference 2008 Conference Paper

Overcoming sensor noise for low-tolerance autonomous assembly

• Brennan Sellner
• Frederik W. Heger
• Laura M. Hiatt
• Nik A. Melchior
• Stephen N. Roderick
• Dave Akin
• Reid G. Simmons
• Sanjiv Singh

The capability to assemble structures is fundamental to the use of robotics in precursor missions in orbit and on planetary surfaces. We have performed autonomous assembly in neutral buoyancy of elements of a space truss whose mating components require positioning tolerances of the same order of magnitude as the noise in the sensor systems used for the docking. Numerous trade-offs, design decisions, and innovations were made during the development of the assembly system in order to both reduce and compensate for the sensor noise. By using relative positioning, decoupling sensing and manipulation, caching high-quality position estimates, and developing a new waypoint-completion metric, we were able to reduce sensor noise to the sub-millimeter level and autonomously assemble components with millimeter tolerances. In this paper, we discuss our approaches to the problem and report the results of a series of autonomous assembly operations.

ICRA Conference 2007 Conference Paper

Particle RRT for Path Planning with Uncertainty

• Nik A. Melchior
• Reid G. Simmons

This paper describes a new extension to the rapidly-exploring random tree (RRT) path planning algorithm. The particle RRT algorithm explicitly considers uncertainty in its domain, similar to the operation of a particle filter. Each extension to the search tree is treated as a stochastic process and is simulated multiple times. The behavior of the robot can be characterized based on the specified uncertainty in the environment, and guarantees can be made as to the performance under this uncertainty. Extensions to the search tree, and therefore entire paths, may be chosen based on the expected probability of successful execution. The benefit of this algorithm is demonstrated in the simulation of a rover operating in rough terrain with unknown coefficients of friction

ICRA Conference 2007 Conference Paper

Pre-positioning Assets to Increase Execution Efficiency

• Laura M. Hiatt
• Reid G. Simmons

In many robotic domains, efficiency is an important component of task execution. One way to improve task efficiency is to lessen the overhead of beginning a task by making sure the necessary agents are near the task site when execution begins, minimizing travel time delays - in other words, pre-positioning agents for their future tasks. In static, certain domains, this can easily be done in advance and incorporated into the initial plan. In dynamic domains such as search and rescue, however, there is not enough certainty about task execution to plan for this ahead of time. To address this, we present here a planner that adds pre-positioning to a plan during execution. The planner strategically positions groups of idle robots whose future task assignments are uncertain in order to minimize travel time by the group as a whole once its members are allocated tasks. Because this planner must run in real time, we present five versions of the planning algorithm, addressing the trade-off of computation time and solution quality that results. We then show that by adding in this type of planning, the overhead of beginning a task can be reduced by up to 90%.

IROS Conference 2006 Conference Paper

Coordinate Frames in Robotic Teleoperation

• Laura M. Hiatt
• Reid G. Simmons

An important mode of human-robot interaction is teleoperation, in which a human operator directly controls a robot via hardware such as a joystick or mouse. Such control is not always easy, however, as the viewpoint of the human, the alignment of the input device, and the local coordinate frame of the robot are rarely all aligned. These discrepancies force the user to reconcile the involved coordinate frames during teleoperation. Therefore, the choice of coordinate frames is critical since an unintuitive coordinate frame mapping will likely lead to higher mental workload and reduced efficiency. We discuss this concern, describe the various difficulties involved with natural remote teleoperation of a robot, and report experiments that demonstrate the effects of using different frames of reference on task performance and user mental workload

I&C Journal 2006 Journal Article

Statistical probabilistic model checking with a focus on time-bounded properties

• Håkan L.S. Younes
• Reid G. Simmons

Probabilistic verification of continuous-time stochastic processes has received increasing attention in the model-checking community in the past five years, with a clear focus on developing numerical solution methods for model checking of continuous-time Markov chains. Numerical techniques tend to scale poorly with an increase in the size of the model (the “state space explosion problem”), however, and are feasible only for restricted classes of stochastic discrete-event systems. We present a statistical approach to probabilistic model checking, employing hypothesis testing and discrete-event simulation. Since we rely on statistical hypothesis testing, we cannot guarantee that the verification result is correct, but we can at least bound the probability of generating an incorrect answer to a verification problem.

IROS Conference 2005 Conference Paper

Designing robots for long-term social interaction

• Rachel Gockley
• Allison Bruce
• Jodi Forlizzi
• Marek P. Michalowski
• Anne Mundell
• Stephanie Rosenthal
• Brennan Sellner
• Reid G. Simmons

Valerie the roboceptionist is the most recent addition to Carnegie Mellon's social robots project. A permanent installation in the entranceway to Newell-Simon hall, the robot combines useful functionality - giving directions, looking up weather forecasts, etc. - with an interesting and compelling character. We are using Valerie to investigate human-robot social interaction, especially long-term human-robot "relationships". Over a nine-month period, we have found that many visitors continue to interact with the robot on a daily basis, but that few of the individual interactions last for more than 30 seconds. Our analysis of the data has indicated several design decisions that should facilitate more natural human-robot interactions.

ICRA Conference 2005 Conference Paper

Learning Opportunity Costs in Multi-Robot Market Based Planners

• Jeff G. Schneider
• David Apfelbaum
• J. Andrew Bagnell
• Reid G. Simmons

Direct human control of multi-robot systems is limited by the cognitive ability of humans to coordinate numerous interacting components. In remote environments, such as those encountered during planetary or ocean exploration, a further limit is imposed by communication bandwidth and delay. Market based planning can give humans a higher-level interface to multi-robot systems in these scenarios. Operators provide high level tasks and attach a reward to the achievement of each task. The robots then trade these tasks through a market based mechanism. The challenge for the system designer is to create bidding algorithms for the robots that yield high overall system performance. Opportunity cost provides a nice basis for such bidding algorithms since it encapsulates all the costs and benefits we are interested in. Unfortunately, computing it can be difficult. We propose a method of learning opportunity costs in market based planners. We provide analytic results in simplified scenarios and empirical results on our FIRE simulator, which focuses on exploration of Mars by multiple, heterogeneous rovers.

UAI Conference 2005 Conference Paper

Point-Based POMDP Algorithms: Improved Analysis and Implementation

• Trey Smith
• Reid G. Simmons

UAI Conference 2004 Conference Paper

Heuristic Search Value Iteration for POMDPs

• Trey Smith
• Reid G. Simmons

We present a novel POMDP planning algorithm called heuristic search value iteration (HSVI).HSVI is an anytime algorithm that returns a policy and a provable bound on its regret with respect to the optimal policy. HSVI gets its power by combining two well-known techniques: attention-focusing search heuristics and piecewise linear convex representations of the value function. HSVI's soundness and convergence have been proven. On some benchmark problems from the literature, HSVI displays speedups of greater than 100 with respect to other state-of-the-art POMDP value iteration algorithms. We also apply HSVI to a new rover exploration problem 10 times larger than most POMDP problems in the literature.

ICAPS Conference 2004 Conference Paper

Policy Generation for Continuous-time Stochastic Domains with Concurrency

• Håkan L. S. Younes
• Reid G. Simmons

We adopt the framework of Younes, Musliner, and Simmons for planning with concurrency in continuous-time stochastic domains. Our contribution is a set of concrete techniques for policy generation, failure analysis, and repair. These techniques have been implemented in TEMPASTIC, a novel temporal probabilistic planner, and we demonstrate the performance of the planner on two variations of a transportation domain with concurrent actions and exogenous events. TEMPASTIC makes use of a deterministic temporal planner to generate initial policies. Policies are represented using decision trees, and we use incremental decision tree induction to effi- ciently incorporate changes suggested by the failure analysis.

IROS Conference 2004 Conference Paper

Preliminary results in sliding autonomy for assembly by coordinated teams

• Jonathan Brookshire
• Sanjiv Singh
• Reid G. Simmons

We are developing a coordinated team of robots to assemble structures, a task that cannot be performed by any single robot. Even simple operations in this domain require complex interaction between multiple robots and the number of contingencies that must be addressed if the team is to act completely autonomously is prohibitively large. This scenario forces incorporation of a human operator. Ideally we would like a seamless interface between the robots and the operator such that the operator can interact with the system by helping it be more efficient or get out of a stuck condition or performing a task that the robots are not capable of themselves. We use an architecture that implements "sliding autonomy" to accomplish these goals. The system of robots can be fully autonomous as long as all is well. The system is capable of accepting input from the operator at any time, especially when it is unable to recover from a failure. We motivate this scenario with results from an extended series of experiments we have conducted with three robots that work together to dock both ends of a suspended beam. We show the difference in performance between a completely teleoperated system, a fully autonomous system, and one in which sliding autonomy has been incorporated.

AAAI Conference 2004 Conference Paper

Solving Generalized Semi-Markov Decision Processes Using Continuous Phase-Type Distributions

• Håkan L. S. Younes
• Reid G. Simmons

We introduce the generalized semi-Markov decision process (GSMDP) as an extension of continuous-time MDPs and semi-Markov decision processes (SMDPs) for modeling stochastic decision processes with asynchronous events and actions. Using phase-type distributions and uniformization, we show how an arbitrary GSMDP can be approximated by a discrete-time MDP, which can then be solved using existing MDP techniques. The techniques we present can also be seen as an alternative approach for solving SMDPs, and we demonstrate that the introduction of phases allows us to generate higher quality policies than those obtained by standard SMDP solution techniques.

ICAPS Conference 2003 Conference Paper

A Framework for Planning in Continuous-time Stochastic Domains

• Håkan L. S. Younes
• David J. Musliner
• Reid G. Simmons

We propose a framework for policy generation in continuoustime stochastic domains with concurrent actions and events of uncertain duration. We make no assumptions regarding the complexity of the domain dynamics, and our planning algorithm can be used to generate policies for any discrete event system that can be simulated. We use the continuous stochastic logic (CSL) as a formalism for expressing temporally extended probabilistic goals and have developed a probabilistic anytime algorithm for verifying plans in our framework. We present an efficient procedure for comparing two plans that can be used in a hill-climbing search for a goal-satisfying plan. Our planning framework falls into the Generate, Test and Debug paradigm, and we propose a transformational approach to plan generation. This relies on effective analysis and debugging of unsatisfactory plans. Discrete event systems are naturally modeled as generalized semi-Markov processes (GSMPs). We adopt the GSMP as the basis for our planning framework, and present preliminary work on a domain independent approach to plan debugging that utilizes information from the verification phase.

IROS Conference 2003 Conference Paper

Approaches for heuristically biasing RRT growth

• Chris Urmson
• Reid G. Simmons

This paper presents several modifications to the basic rapidly-exploring random tree (RRT) search algorithm. The fundamental idea is to utilize a heuristic quality function to guide the search. Results from a relevant simulation experiment illustrate the benefit and drawbacks of the developed algorithms. The paper concludes with several promising directions for future research.

IROS Conference 2003 Conference Paper

CLARAty and challenges of developing interoperable robotic software

• Issa A. D. Nesnas
• Anne Wright
• Max Bajracharya
• Reid G. Simmons
• Tara A. Estlin

We present an overview of the Coupled Layered Architecture for Robotic Autonomy. CLARAty develops a framework for generic and reusable robotic components that can be adapted to a number of heterogeneous robot platforms. It also provides a framework that will simplify the integration of new technologies and enable the comparison of various elements. CLARAty consists of two distinct layers: a functional layer and a decision layer. The functional layer defines the various abstractions of the system and adapts the abstract components to real or simulated devices. It provides a framework and the algorithms for low- and mid-level autonomy. The decision layer provides the system's high-level autonomy, which reasons about global resources and mission constraints. The decision layer accesses information from the functional layer at multiple levels of granularity. We also present some of the challenges in developing interoperable software for various rover platforms.

IROS Conference 2003 Conference Paper

Maintaining line of sight communications networks between planetary rovers

• Stuart O. Anderson
• Reid G. Simmons
• Dani Goldberg

We present an algorithm designed to solve the problem of maintaining communications within a group of robotic explorers. The rovers we consider are equipped with communication hardware that is effective only over a limited range and requires direct line of sight to function. The paper presents the algorithm used to solve this problem and some details of our implementation. We also present the results of an experimental analysis of the algorithm's performance characteristics in a simulated multi-rover environment.

ICRA Conference 2002 Conference Paper

A Suite of Tools for Debugging Distributed Autonomous Systems

• David Kortenkamp
• Reid G. Simmons
• Tod Milam
• Joaquín Lopez Fernández

Describes a set of tools that allows a developer to instrument an autonomous control system to log data at run-time and then analyze that data to verify correct program behavior. Analysis is done using an interval logic that allows system engineers to express complex, temporal specifications to be checked against the logged data of the autonomous control program. A feature of both the logging and analysis is that they can work with distributed programs. All data is synchronized into a common database. The data logging tools and the interval logic are fully implemented. Results are given from a NASA distributed autonomous control system application.

ICAPS Conference 2002 Conference Paper

On the Role of Ground Actions in Refinement Planning

• Håkan L. S. Younes
• Reid G. Simmons

Less than a decade ago, the focus in refinement planning was on partial order planners using lifted actions. Today, the currently most successful refinement planners are all state space planners using ground actions -- i. e. actions where all parameters have been substituted by objects. In this paper, we address the role of ground actions in refinement planning, and present empirical results indicating that their role is twofold. First, planning with ground actions represents a bias towards early commitment of parameter bindings. Second, ground actions help enforce joint parameter domain constraints. By implementing these two techniques in a least commitment planner such as UCPOP, together with using an informed heuristic function to guide the search for solutions, we show that we often need to generate far fewer plans than when planning with ground action, while the number of explored plans remains about the same. In some cases a vast reduction can also be achieved in the number of explored plans.

IROS Conference 2002 Conference Paper

Stereo vision based navigation for Sun-synchronous exploration

• Chris Urmson
• M. Bernardine Dias
• Reid G. Simmons

This paper describes the navigation system used on a prototype sun-synchronous robot. Sun-synchrony is a concept that will enable exploration missions by solar-powered rovers that could last months or years. This paper presents the navigation algorithms developed for traversing natural terrain robustly. The novel elements of this work are the refinements necessary to transform laboratory-demonstrated technologies into a form useful for robust, Sun-synchronous exploration. Results of afield experiment in the Canadian Arctic, where the robot traversed 6. 1km, 90% autonomously, are also presented.

ICRA Conference 2002 Conference Paper

The Role of Expressiveness and Attention in Human-Robot Interaction

• Allison Bruce
• Illah R. Nourbakhsh
• Reid G. Simmons

This paper presents the results of an experiment in human-robot social interaction. Its purpose was to measure the impact of certain features and behaviors on people's willingness to engage in a short interaction with a robot. The behaviors tested were the ability to convey expression with a humanoid face and the ability to indicate attention by turning towards the person that the robot is addressing. We hypothesized that these features were minimal requirements for effective social interaction between a human and a robot. We will discuss the results of the experiment and their implications for the design of socially interactive robots.

ICRA Conference 2001 Conference Paper

Autonomous Exploration Using Multiple Sources of Information

• Stewart J. Moorehead
• Reid G. Simmons
• William Whittaker

Enables robot explorers to maximize the total information gained while minimizing costs such as driving, sensing and planning. The paper presents a general methodology for solving complex exploration tasks which employs multiple sources of information. The paper also develops a specific instantiation of the method to solve the exploration problem of creating a complete traversability map of an known region. Simulation results showing the solution of this exploration task are included.

ICRA Conference 2001 Conference Paper

The Science Autonomy System of the Nomad Robot

• Michael Wagner 0007
• Dimitrios Apostolopoulos
• Kimberly J. Shillcutt
• Benjamin Shamah
• Reid G. Simmons
• William Whittaker

The Science Autonomy System (SAS) is a hierarchical control architecture for exploration and in situ science that integrates sensing, navigation, classification and mission planning. The Nomad robot demonstrated the capabilities of the SAS during a January 2000 expedition to Elephant Moraine, Antarctica where it accomplished the first meteorite discoveries made by a robot. In the paper, the structure and functionality of the three-tiered SAS are detailed. Results and lessons learned are presented with a focus on important future research.

IROS Conference 2000 Conference Paper

A social robot that stands in line

• Yasushi Nakauchi
• Reid G. Simmons

Recent research results on mobile robot navigation systems make it promising to utilize them in service fields. But in order to utilize the robot in a peopled environment, it should recognize and respond to people's social behaviors. In this paper, we describe a social robot that stands in line as people do. Our system uses the concept of personal space for modeling a line of people and we have experimentally measured the actual size of the personal space when people form lines. The system employs stereo vision to recognize lines of people. We demonstrate our ideas with a mobile robot navigation system that can purchase a cup of coffee, even if people are waiting in line for service.

ICRA Conference 2000 Conference Paper

Architecture, the Backbone of Robotic Systems

• Ève Coste-Manière
• Reid G. Simmons

Architectures form the backbone of complete robotic systems. The right choice of architecture can go a long way in facilitating the specification, implementation and validation of robotic systems. Conversely, of course, the wrong choice can make one's life miserable. We present some of the needs of robotic systems, describe some general classes of robot architectures, and discuss how different architectural styles can help in addressing those needs. The paper, like the field itself, is somewhat preliminary, yet it is hoped that it will provide guidance for those who use, or develop, robot architectures.

ICRA Conference 2000 Conference Paper

Collaborative Multi-Robot Exploration

• Wolfram Burgard
• Mark Moors
• Dieter Fox
• Reid G. Simmons
• Sebastian Thrun

In this paper we consider the problem of exploring an unknown environment by a team of robots. As in single-robot exploration the goal is to minimize the overall exploration time. The key problem to be solved therefore is to choose appropriate target points for the individual robots so that they simultaneously explore different regions of their environment. We present a probabilistic approach for the coordination of multiple robots which, in contrast to previous approaches, simultaneously takes into account the costs of reaching a target point and the utility of target points. The utility of target points is given by the size of the unexplored area that a robot can cover with its sensors upon reaching a target position. Whenever a target point is assigned to a specific robot, the utility of the unexplored area visible from this target position is reduced for the other robots. This way, a team of multiple robots assigns different target points to the individual robots. The technique has been implemented and tested extensively in real-world experiments and simulation runs. The results given in this paper demonstrate that our coordination technique significantly reduces the exploration time compared to previous approaches.

IROS Conference 2000 Conference Paper

Coordinated deployment of multiple, heterogeneous robots

• Reid G. Simmons
• David Apfelbaum
• Dieter Fox
• Robert P. Goldman
• Karen Zita Haigh
• David J. Musliner
• Michael J. S. Pelican
• Sebastian Thrun

To be truly useful, mobile robots need to be fairly autonomous and easy to control. This is especially true in situations where multiple robots are used, due to the increase in sensory information and the fact that the robots can interfere with one another. The paper describes a system that integrates autonomous navigation, a task executive, task planning, and an intuitive graphical user interface to control multiple, heterogeneous robots. We have demonstrated a prototype system that plans and coordinates the deployment of teams of robots. Testing has shown the effectiveness and robustness of the system, and of the coordination strategies in particular.

IROS Conference 2000 Conference Paper

Distributed visual servoing with a roving eye

• David Hershberger
• Robert R. Burridge
• David Kortenkamp
• Reid G. Simmons

This paper presents experimental results of preliminary research into multi-robot coordination for construction tasks. Experiments demonstrate that an autonomous "roving eye" robot can provide feedback to a manipulator to align targets from a wider variety of situations than is possible with fixed cameras, without sacrificing the accuracy provided by cameras at close range. The roving eye changes its location autonomously based on current images of the manipulated object and target, always striving for the best view of the task.

ICRA Conference 2000 Conference Paper

Recent Progress in Local and Global Traversability for Planetary Rovers

• Sanjiv Singh
• Reid G. Simmons
• Trey Smith
• Anthony Stentz
• Vandi Verma
• Alex Yahja
• Kurt Schwehr

Autonomous planetary rovers operating in vast unknown environments must operate efficiently because of size, power and computing limitations. Recently, we have developed a rover capable of efficient obstacle avoidance and path planning. The rover uses binocular stereo vision to sense potentially cluttered outdoor environments. Navigation is performed by a combination of several modules that each "vote" for the next best action for the robot to execute. The key distinction of our system is that it produces globally intelligent behavior with a small computational resource - all processing and decision making are done on a single processor. These algorithms have been tested on our outdoor prototype rover, Bullwinkle, and have recently driven the rover 100 m at a speed of 15 cm/sec. In this paper we report on the extension on the systems that we have previously developed that were necessary to achieve autonomous navigation in this domain.

IROS Conference 2000 Conference Paper

Towards automatic verification of autonomous systems

• Reid G. Simmons
• Charles Pecheur
• Grama Srinivasan

While autonomous systems offer great promise in terms of capability and flexibility, their reliability is particularly hard to assess. This paper describes research to apply formal verification methods to languages used to develop autonomy software. In particular, we describe tools that automatically convert autonomy software into formal models that are then verified using model checking. This approach has been applied to MPL code for the Livingstone fault diagnosis system and to TDL task descriptions for mobile robot systems. Our long-term objective is to create tools that enable engineers and roboticists to use formal verification as part of the normal software development cycle.

IROS Conference 1998 Conference Paper

A task description language for robot control

• Reid G. Simmons
• David Apfelbaum

Robot systems must achieve high level goals while remaining reactive to contingencies and new opportunities. This typically requires robot systems to coordinate concurrent activities, monitor the environment, and deal with exceptions. We have developed a new language to support such task-level control. The language, TDL, is an extension of C++ that provides syntactic support for task decomposition, synchronization, execution monitoring, and exception handling. A compiler transforms TDL into pure C++ code that utilizes a platform-independent task management library. This paper introduces TDL, describes the task tree representation that underlies the language, and presents some aspects of its implementation and use in an autonomous mobile robot.

IROS Conference 1998 Conference Paper

Robust execution monitoring for navigation plans

• Joaquín Lopez Fernández
• Reid G. Simmons

This paper presents a general approach to robust execution monitoring. The goal is to provide coverage for many types of unexpected and unanticipated situations, while at the same time enabling the robot to quickly detect, and react to, specific contingencies. The approach uses a hierarchy of monitors, structured in layers of increasing specificity. We present the general approach, and show its application in the domain of indoor mobile robot navigation.

ICAPS Conference 1998 Conference Paper

Search Control of Plan Generation in Decision-Theoretic Planners

• Richard Goodwin
• Reid G. Simmons

This paper addresses the search control problemof selecting whichplan to refine next for decision-theoretic planners, a choice point common to the decision theoretic planners created to date. Such planners can makeuse of a utility function to calculate boundson the expectedutility of an abstract plan. Threestrategies for using these boundsto select the next plan to refine have been proposed in the literature. Weexaminethe rationale for each strategy and prove that the optimistic strategy of alwaysselecting a plan with the highest upper-boundon expected utility expands the fewest numberof plans, whenlooking for all plans with the highest expected utility. Whenlooking for a single plan with the highest expected utility, we prove that the optimistic strategy has the best possible worst case performanceand that other strategies can fail to terminate. To demonstratethe effect of plan selection strategies on performance, we give results using the DRWS planner that showthat the optimistic strategy can produce exponential improvements in time and space.

ICAPS Conference 1998 Conference Paper

Solving Robot Navigation Problems with Initial Pose Uncertainty Using Real-Time Heuristic Search

• Sven Koenig
• Reid G. Simmons

Westudy goal-directednavigationtasks in mazes, wherethe robots knowthe mazebut donot knowtheir initial pose(position and orientation). Thesesearch tasks canbe modeled as planningtasks in large non-deterministicdomainswhose states are sets of poses. Theycan be solvedefficiently by interleaving planningand plan execution, whichcan reduce the sumof planningand plan-executiontime becauseit allowsthe robots to gather informationearly. Weshowhow Min-Max LRTA*, a real-time heuristic search method, can solve these and other planningtasks in non-deterministic domainsefficiently. It allowsfor fine-grainedcontrol over howmuchplanning to do betweenplan executions, uses heuristic knowledge to guideplanning, and improves its planexecutiontimeas it solvessimilarplanningtasks, until its plan-executiontimeis at least worst-caseoptimal. Wealso showthat Min-Max LRTA* solves the goal-directed navigation tasks fast, converges quickly, andrequiresonlya small amountof memory.

IROS Conference 1998 Conference Paper

The lane-curvature method for local obstacle avoidance

• Nak Yong Ko
• Reid G. Simmons

The lane-curvature method (LCM) presented in this paper is a new local obstacle avoidance method for indoor mobile robots. The method combines curvature-velocity method (CVM) with a new directional method called the lane method. The lane method divides the environment into lanes, and then chooses the best lane to follow to optimize travel along a desired heading. A local heading is then calculated for entering and following the best lane, and CVM uses this heading to determine the optimal translational and rotational velocities, considering the heading direction, physical limitations, and environmental constraints. By combining both the directional and velocity space methods, LCM yields safe collision-free motion as well as smooth motion taking the dynamics of the robot into account.

ICML Conference 1996 Conference Paper

Passive Distance Learning for Robot Navigation

• Sven Koenig
• Reid G. Simmons

ICRA Conference 1996 Conference Paper

The curvature-velocity method for local obstacle avoidance

• Reid G. Simmons

We present a new method for local obstacle avoidance by indoor mobile robots that formulates the problem as one of constrained optimization in velocity space. Constraints that stem from physical limitations (velocities and accelerations) and the environment (the configuration of obstacles) are placed on the translational and rotational velocities of the robot. The robot chooses velocity commands that satisfy all the constraints and maximize an objective function that trades off speed, safety and goal-directedness. An efficient, real-time implementation of the method has been extensively tested, demonstrating reliable, smooth and speedy navigation in office environments. The obstacle avoidance method is used as the basis of more sophisticated navigation behaviors, ranging from simple wandering to map-based navigation.

ICRA Conference 1996 Conference Paper

Unsupervised learning of probabilistic models for robot navigation

• Sven Koenig
• Reid G. Simmons

Navigation methods for office delivery robots need to take various sources of uncertainty into account in order to get robust performance. In previous work, we developed a reliable navigation technique that uses partially observable Markov models to represent metric, actuator and sensor uncertainties. This paper describes an algorithm that adjusts the probabilities of the initial Markov model by passively observing the robot's interactions with its environment. The learned probabilities more accurately reflect the actual uncertainties in the environment, which ultimately leads to improved navigation performance. The algorithm, an extension of the Baum-Welch algorithm, learns without a teacher and addresses the issues of limited memory and the cost of collecting training data. Empirical results show that the algorithm learns good Markov models with a small amount of training data.

IROS Conference 1995 Conference Paper

Experience with rover navigation for lunar-like terrains

• Reid G. Simmons
• Eric Krotkov
• Lonnie Chrisman
• Fábio Gagliardi Cozman
• Richard Goodwin
• Martial Hebert
• Lalitesh Katragadda
• Sven Koenig

Reliable navigation is critical for a lunar rover, both for autonomous traverses and safeguarded remote teleoperation. This paper describes an implemented system that has autonomously driven a prototype wheeled lunar rover over a kilometer in natural, outdoor terrain. The navigation system uses stereo terrain maps to perform local obstacle avoidance, and arbitrates steering recommendations from both the user and the rover. The paper describes the system architecture, each of the major components, and the experimental results to date.

ICAPS Conference 1994 Conference Paper

Becoming Increasingly Reliable

• Reid G. Simmons

Autonomousmobile robots need to detect potential failures reliably and react appropriately. Due to uncertainties about the robots and their environment, it is extremelydifficult to design reliable systems from the start. Instead, we advocate the structured control methodology, in which one starts with plans that work in nominalsituations, and then incrementally adds reactive behaviors to handle previously unanticipated situations. Wehave developed the Task Control Architecture to facilitate this methodologyby enabling monitors and exception handlers to be added to existing hierarchical plans. This paper details the application of this methodologyto a walking rover and an indoor office robot. In both cases, robot systems were produced that can autonomously traverse long distances in obstacle-filled environments.

ICAPS Conference 1994 Conference Paper

How to Make Probabilistic Planners Risk-sensitive (Without Altering Anything)

• Sven Koenig
• Reid G. Simmons

Probabilistic planners can have various planning objectives: usually they either maximize the probability of goal achievement or minimize the expected execution cost of the plan. Researchers have largely ignored the problem how to incorporate risk-sensitive attitudes into their planning mechanisms. We discuss a risk-sensitive planning approach that is based on utility theory. Our key result is that this approach can, at least for risk-seeking attitudes, be implemented with any reactive planner that maximizes (or satisfices) the probability of goal achievement. First, the risk-sensitive planning problem is transformed into a different planning problem, that is then solved by the planner. The larger the probability of goal achievement of the resulting plan, the better its expected utility is for the original (risk-sensitive) planning problem. This approach extends the functionality of reactive planners that maximize the probability of goal achievement, since it allows one to use them (unchanged) for risk-sensitive planning.

IROS Conference 1992 Conference Paper

Monitoring And Error Recovery For Autonomous Walking

• Reid G. Simmons

ICRA Conference 1992 Conference Paper

Performance of a six-legged planetary rover: power, positioning, and autonomous walking

• Eric Krotkov
• Reid G. Simmons

The authors quantify several performance metrics for the Ambler, a six-legged robot configured for autonomous traversal of Mars-like terrain. They present power consumption measures for walking on sandy terrain and for vertical lifts at different velocities. They document the accuracy of a novel dead reckoning approach, and analyze the accuracy. They describe the results of autonomous walking experiments in terms of terrain traversed, walking speed, number of instructions executed and endurance. >

IROS Conference 1992 Conference Paper

Task Planning For Robotic Excavation

• Sanjiv Singh
• Reid G. Simmons

AIJ Journal 1992 Journal Article

The roles of associational and causal reasoning in problem solving

• Reid G. Simmons

Efficiency and robustness are two desirable, but often conflicting, characteristics of problem solvers. This article describes the Generate, Test and Debug (GTD) paradigm, which combines associational and causal reasoning techniques to efficiently solve a wide range of problems. GTD uses associational reasoning to generate initial hypotheses, and uses causal reasoning to test hypotheses and to debug faulty hypotheses, if necessary. We contend that the characteristics of associational and causal reasoning differ mainly in the way they deal with interactions—associational reasoning presumes independence; causal reasoning explicitly represents interactions. This difference helps account for the strengths and weaknesses of the reasoning techniques, and indicates the problem-solving roles for which they are best suited. The GTD paradigm has been implemented and tested in several planning and interpretation domains, with an emphasis on geologic interpretation.

ICRA Conference 1991 Conference Paper

An integrated walking system for the Ambler planetary rover

• Reid G. Simmons
• Eric Krotkov

The Carnegie Mellon University Planetary Rover project is developing the Ambler, a six-legged robot designed for planetary exploration. The authors have developed reliable and efficient control, perception and planning algorithms suitable for navigating rugged terrain. The components have been integrated into a system that autonomously walks the Ambler along routes and over obstacles. >

ICRA Conference 1991 Conference Paper

Concurrent planning and execution for a walking robot

• Reid G. Simmons

As part of the planetary Rover project at Carnegie Mellon University, a system that autonomously navigates a legged robot through complex obstacle courses has been developed. The system is integrated using the task control architecture (TCA), which provides communication and coordination facilities. The walking system, as originally implemented, had a sequential sense-plan-act control cycle. Utilizing TCA features for task sequencing and monitoring, the system was modified to concurrently plan and execute steps. Overall walking speed increased significantly, with only a relatively modest conversion effort. >

IROS Conference 1990 Conference Paper

Single leg walking with integrated perception, planning and control

• Eric Krotkov
• Reid G. Simmons
• Charles E. Thorpe

Describes an integrated system capable of walking over rugged terrain using a single leg suspended below a carriage that rolls along rails. To walk, the system uses a laser scanner to find a foothold, positions the leg above the foothold, contacts the terrain with the foot, and applies force enough to advance the carriage along the rails. Walking both forward and backward, the system has traversed hundreds of meters of rugged terrain including obstacles too tall to step over, trenches too deep to step in, closely spaced rocks, and sand hills. The implemented system consists of a number of task-specific processes (two for planning, two for perception, one for real-time control) and a central control process that directs the flow of communication between processes. Implementing this integrated system is a significant step toward the goal of the CMU Planetary Rover project: to prototype a autonomous six-legged robot for planetary exploration.

AAAI Conference 1988 Conference Paper

A Theory of Debugging Plans and Interpretations

• Reid G. Simmons

We present a theory of debugging applicable for planning and interpretation problems. The debugger analyzes causal explanations for why a bug arises to locate the underlying assumptions upon which the bug depends. A bug is repaired by replacing assumptions, using a small set of domain-independent debugging strategies that reason about the causal explanations and domain models that encode the effects of events. Our analysis of the planning and interpretation tasks indicates that only a small set of assumptions and associated repair strategies are needed to handle a wide range of bugs over a large class of domains. Our debugging approach extends previous work in both debugging and domain-independent planning. The approach, however, is computationally expensive and so is used in the context of the Generate, Test and Debug paradigm, in which the debugger is used only if the heuristic generator produces an incorrect hypothesis.

AAAI Conference 1983 Conference Paper

The Use of Qualitative and Quantitative Simulations

• Reid G. Simmons

We describe a technique called imagining which uses a combination of qualitative and quantitative simulation techniques to solve a problem where neither alone would suffice. We illustrate the imagining technique using the domain of geologic interpretation and argue for why the two types of simulation are necessary for problems of this sort. We also discuss the strengths of each simulation technique and how they support each other in the problem solving process.

AAAI Conference 1982 Conference Paper

Spatial and Temporal Reasoning in Geologic Map Interpretation

• Reid G. Simmons

In this paper, we describe a way of extending and combining several Al techniques to attack a class of problems exemplified by a problem known as geologic map interpretation. We use both a detailed and an abstract model of elementary geology, combined with both local and global reasoning techniques to achieve the system’s expertise. In particular, a new technique called imagining allows us to find global inconsistencies in our hypotheses by causally simulating a sequence of "instructions." Imagining makes use of both our detailed and abstract models of the world.