Deliberation for autonomous robots: A survey
---
paper_title: Execution monitoring in robotics: A survey

paper_content:

Research on execution monitoring in its own is still not very common within the field of robotics and autonomous systems. It is more common that researchers interested in control architectures or e ...
---
paper_title: Human-aware robot navigation: A survey

paper_content:

Navigation is a basic skill for autonomous robots. In the last years human-robot interaction has become an important research field that spans all of the robot capabilities including perception, reasoning, learning, manipulation and navigation. For navigation, the presence of humans requires novel approaches that take into account the constraints of human comfort as well as social rules. Besides these constraints, putting robots among humans opens new interaction possibilities for robots, also for navigation tasks, such as robot guides. This paper provides a survey of existing approaches to human-aware navigation and offers a general classification scheme for the presented methods.
---
paper_title: Robotics and artificial intelligence: A perspective on deliberation functions

paper_content:

Despite a very strong synergy between Robotics and AI at their early beginning, the two fields progressed widely apart in the following decades. However, we are witnessing a revival of interest in the fertile domain of embodied machine intelligence. This is due in particular to the dissemination of more mature techniques from both areas, to more accessible robot platforms with advanced sensory motor capabilities, and to a better understanding of the scientific challenges of the AI-Robotics intersection.The ambition of this paper is to contribute to this revival. It proposes an overview of problems and approaches to autonomous deliberate action in robotics. The paper advocates for a broad understanding of deliberation functions. It presents a synthetic perspective on planning, acting, perceiving, monitoring, goal reasoning and their integrative architectures, which is illustrated through several contributions that addressed deliberation from the AI-Robotics point of view.
---
paper_title: The meaning of action: A review on action recognition and mapping

paper_content:

In this paper, we analyze the different approaches taken to date within the computer vision, robotics and artificial intelligence communities for the representation, recognition, synthesis and understanding of action. We deal with action at different levels of complexity and provide the reader with the necessary related literature references. We put the literature references further into context and outline a possible interpretation of action by taking into account the different aspects of action recognition, action synthesis and task-level planning.
---
paper_title: A Closer Look at MOMDPs

paper_content:

The difficulties encountered in sequential decision-making problems under uncertainty are often linked to the large size of the state space. Exploiting the structure of the problem, for example by employing a factored representation, is usually an efficient approach but, in the case of partially observable Markov decision processes, the fact that some state variables may be visible has not been sufficiently appreciated. In this article, we present a complementary analysis and discussion about MOMDPs, a formalism that exploits the fact that the state space may be factored in one visible part and one hidden part. Starting from a POMDP description, we dig into the structure of the belief update, value function, and the consequences in value iteration, specifically how classical algorithms can be adapted to this factorization, and demonstrate the resulting benefits through an empirical evaluation.
---
paper_title: Breadth of Approaches to Goal Reasoning: A Research Survey

paper_content:

Abstract : Goal-directed behavior is a hallmark of intelligence. While the majority of artificial intelligence research assumes goals are static and externally provided, many real-world applications involve unanticipated changes in the environment that may require changes to the goals themselves. Goal reasoning, which emphasizes the explicit representation of goals, their automatic formulation and dynamic management, is considered an important aspect of high-level autonomy. Building from these three basic requirements, we describe and apply a framework for surveying research related to goal reasoning that focuses on triggers and methods for goal formulation and goal management. We also summarize current research and highlight potential areas of future work.
---
paper_title: Deliberation in the Motor System: Reflex Gains Track Evolving Evidence Leading to a Decision

paper_content:

Both decision making and sensorimotor control require real-time processing of noisy information streams. Historically these processes were thought to operate sequentially: cognitive processing leads to a decision, and the outcome is passed to the motor system to be converted into action. Recently, it has been suggested that the decision process may provide a continuous flow of information to the motor system, allowing it to prepare in a graded fashion for the probable outcome. Such continuous flow is supported by electrophysiology in nonhuman primates. Here we provide direct evidence for the continuous flow of an evolving decision variable to the motor system in humans. Subjects viewed a dynamic random dot display and were asked to indicate their decision about direction by moving a handle to one of two targets. We probed the state of the motor system by perturbing the arm at random times during decision formation. Reflex gains were modulated by the strength and duration of motion, reflecting the accumulated evidence in support of the evolving decision. The magnitude and variance of these gains tracked a decision variable that explained the subject's decision accuracy. The findings support a continuous process linking the evolving computations associated with decision making and sensorimotor control.
---
paper_title: DIARC: A Testbed for Natural Human-Robot Interaction

paper_content:

DIARC, a distributed integrated affect, reflection, cognition architecture for robots, provides many features that are critical to successful natural human-robot interaction. As such, DIARC is an ideal platform for experimentation in HRI. In this paper we describe the architecture and and its implementation in ADE, paying particular attention to its interaction capabilities and features that allow robust operation. These features are evaluated in the context of the 2006 AAAI Robot Competition.
---
paper_title: Task behavior and interaction planning for a mobile service robot that occasionally requires help

paper_content:

In our work, a robot can proactively ask for help when necessary, based on its awareness of its sensing and actuation limitations. Approaches in which humans provide help to robots do not necessarily reason about the human availability and accuracy. Instead, we model the availability of humans in the robot's environment and present a planning approach that uses such model to generate the robot navigational plans. In particular, we contribute two separate planners that allow a robot to distinguish actions that it cannot complete autonomously from ones that it can. In the first planner, the robot plans autonomous actions when possible and requests help to complete actions that it could not otherwise complete. Then for actions that it can perform autonomously, we use a POMDP policy that incorporates the human availability model to plan actions that reduce uncertainty or that increase the likelihood of the robot finding an available human to help it reduce its uncertainty. We have shown in prior work that asking people in the environment for help during tasks can reduce task completion time and increase the robot's ability to perform tasks.
---
paper_title: The actor's view of automated planning and acting: A position paper

paper_content:

Planning is motivated by acting. Most of the existing work on automated planning underestimates the reasoning and deliberation needed for acting; it is instead biased towards path-finding methods in a compactly specified state-transition system. Researchers in this AI field have developed many planners, but very few actors. We believe this is one of the main causes of the relatively low deployment of automated planning applications. In this paper, we advocate a change in focus to actors as the primary topic of investigation. Actors are not mere plan executors: they may use planning and other deliberation tools, before and during acting. This change in focus entails two interconnected principles: a hierarchical structure to integrate the actor@?s deliberation functions, and continual online planning and reasoning throughout the acting process. In the paper, we discuss open problems and research directions toward that objective in knowledge representations, model acquisition and verification, synthesis and refinement, monitoring, goal reasoning, and integration.
---
paper_title: CLARAty and challenges of developing interoperable robotic software

paper_content:

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.
---
paper_title: Model-Free Execution Monitoring in Behavior-Based Mobile Robotics

paper_content:

In this paper we present a model-free execution monitor for behavior-based mobile robots. By model-free we mean that the monitoring is based only on the actual execution, without involving any pred ...
---
paper_title: The Saphira Architecture: A Design for Autonomy

paper_content:

Mobile robots, if they are to perform useful tasks and become accepted in open environments, must be fully autonomous. Autonomy has many different aspects ; here the focus is on three central ones: the ability to attend to another agent, to take advice about the environment, and to carry out assigned tasks. All three involve complex sensing and planning operations on the part of the robot, including the use of visual tracking of humans, coordination of motor controls, and planning. It is shown how these capabilities are integrated in the Saphira architecture, using the concepts of coordination of behaviour, coherence of modelling, and communication with other agents.
---
paper_title: A deliberative architecture for AUV control

paper_content:

Autonomous Underwater Vehicles (AUVs) are an increasingly important tool for oceanographic research demonstrating their capabilities to sample the water column in depths far beyond what humans are capable of visiting, and doing so routinely and cost-effectively. However, control of these platforms to date has relied on fixed sequences for execution of pre-planned actions limiting their effectiveness for measuring dynamic and episodic ocean phenomenon. In this paper we present an agent architecture developed to overcome this limitation through on-board planning using Constraint- based Reasoning. Preliminary versions of the architecture have been integrated and tested in simulation and at sea.
---
paper_title: CRAM — A Cognitive Robot Abstract Machine for everyday manipulation in human environments

paper_content:

This paper describes CRAM (Cognitive Robot Abstract Machine) as a software toolbox for the design, the implementation, and the deployment of cognition-enabled autonomous robots performing everyday manipulation activities. CRAM equips autonomous robots with lightweight reasoning mechanisms that can infer control decisions rather than requiring the decisions to be preprogrammed. This way CRAM-programmed autonomous robots are much more flexible, reliable, and general than control programs that lack such cognitive capabilities. CRAM does not require the whole domain to be stated explicitly in an abstract knowledge base. Rather, it grounds symbolic expressions in the knowledge representation into the perception and actuation routines and into the essential data structures of the control programs. In the accompanying video, we show complex mobile manipulation tasks performed by our household robot that were realized using the CRAM infrastructure.
---
paper_title: Decisional Autonomy of Planetary Rovers

paper_content:

To achieve the ever increasing demand for science return, planetary exploration rovers require more autonomy to successfully perform their missions. Indeed, the communication delays are such that teleoperation is unrealistic. Although the current rovers (such as MER) demonstrate a limited navigation autonomy, and mostly rely on ground mission planning, the next generation (e.g., NASA Mars Science Laboratory and ESA Exomars) will have to regularly achieve long range autonomous navigation tasks. However, fully autonomous long range navigation in partially known planetary-like terrains is still an open challenge for robotics. Navigating hundreds of meters without any human intervention requires the robot to be able to build adequate representations of its environment, to plan and execute trajectories according to the kind of terrain traversed, to control its motions, and to localize itself as it moves. All these activities have to be planned, scheduled, and performed according to the rover context, and controlled so that the mission is correctly fulfilled. To achieve these objectives, we have developed a temporal planner and an execution controller, which exhibit plan repair and replanning capabilities. The planner is in charge of producing plans composed of actions for navigation, science activities (moving and operating instruments), communication with Earth and with an orbiter or a lander, while managing resources (power, memory, etc.) and respecting temporal constraints (communication visibility windows, rendezvous, etc.). High level actions also need to be refined and their execution temporally and logically controlled. Finally, in such critical applications, we believe it is important to deploy a component that protects the system against dangerous or even fatal situations resulting from unexpected interactions between subsystems (e.g., move the robot while the robot arm is unstowed) and/or software components (e.g., take and store a picture in a buffer while the previous one is still being processed). In this article we review the aforementioned capabilities, which have been developed, tested, and evaluated on board our rovers (Lama and Dala). After an overview of the architecture design principle adopted, we summarize the perception, localization, and motion generation functions required by autonomous navigation, and their integration and concurrent operation in a global architecture. We then detail the decisional components: a high level temporal planner that produces the robot activity plan on board, and temporal and procedural execution controllers. We show how some failures or execution delays are being taken care of with online local repair, or replanning. © 2007 Wiley Periodicals, Inc.
---
paper_title: A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems

paper_content:

Research with autonomous unmanned aircraft systems is reaching a new degree of sophistication where targeted missions require complex types of deliberative capability integrated in a practical manner in such systems. Due to these pragmatic constraints, integration is just as important as theoretical and applied work in developing the actual deliberative functionalities. In this article, we present a temporal logic-based task planning and execution monitoring framework and its integration into a fully deployed rotor-based unmanned aircraft system developed in our laboratory. We use a very challenging emergency services application involving body identification and supply delivery as a vehicle for showing the potential use of such a framework in real-world applications. TALplanner, a temporal logic-based task planner, is used to generate mission plans. Building further on the use of TAL (Temporal Action Logic), we show how knowledge gathered from the appropriate sensors during plan execution can be used to create state structures, incrementally building a partial logical model representing the actual development of the system and its environment over time. We then show how formulas in the same logic can be used to specify the desired behavior of the system and its environment and how violations of such formulas can be detected in a timely manner in an execution monitor subsystem. The pervasive use of logic throughout the higher level deliberative layers of the system architecture provides a solid shared declarative semantics that facilitates the transfer of knowledge between different modules.
---
paper_title: History checking of temporal fuzzy logic formulas for monitoring behavior-based mobile robots

paper_content:

Behavior-based robot control systems have shown remarkable success for controlling robots evolving in real world environments. However, they can fail in different manners due to their distributed control and their local decision making. In this case, monitoring can be used to detect failures and help to recover from them. In this work, we present an approach for specifying monitoring knowledge and a method for using this knowledge to detect failures. In particular we show how temporal fuzzy logic can be used to represent monitoring knowledge and then utilized to effectively detect runtime failures. New semantics are introduced to take into consideration uncertainty and noisy information. There are numbers of advantages to our approach including a declarative semantics for the monitoring knowledge and an independence of this knowledge from the implementation details of the control system. Moreover we show how our system can deal effectively with noisy information and sensor readings. Experiments with two real world robots and the simulator are used to illustrate failure examples and the benefits of failure detection and noise elimination.
---
paper_title: Model-based executive control through reactive planning for autonomous rovers

paper_content:

This paper reports on the design and implementation of a real-time executive for a mobile rover that uses a model-based, declarative approach. The control system is based on the intelligent distributed execution architecture (IDEA), an approach to planning and execution that provides a unified representational and computational framework for an autonomous agent. The basic hypothesis of IDEA is that a large control system can be structured as a collection of interacting agents, each with the same fundamental structure. We show that planning and real-time response are compatible if the executive minimizes the size of the planning problem. We detail the implementation of this approach on an 'exploration rover (Gromit, an RWI ATRV Junior at NASA Ames) presenting different IDEA controllers of the same domain and comparing them with more classical approaches. We demonstrate that the approach is scalable to complex coordination of functional modules needed for autonomous navigation and exploration.
---
paper_title: On Three-Layer Architectures

paper_content:

ion is used as a tool to isolate aspects of reality that can be tracked or predicted reliably, and ignore aspects that cannot. 3. The Anatomy of the Three Layer Architecture The three-layer architecture consists of three components: a reactive feedback control mechanism, a reactive plan execution mechanism, and a mechanism for performing time-consuming deliberative computations. These components run as separate computational processes. This is most easily accomplished by using a multi-tasking or multithreaded operating system, but can also be done my carefully coding the algorithms so they can be manually interleaved within a single computational process. In 3T the components are called the skill layer, the sequencing layer, and the planning layer respectively. In ATLANTIS these layers are called the controller, the sequencer, and the deliberator. The following discussion uses the ATLANTIS terminology, but as much as possible the description is generic to all incarnations of the three-layer architecture.
---
paper_title: Model-based control architecture for attentive robots in rescue scenarios

paper_content:

In this paper we present a control architecture for an autonomous rescue robot specialized in victim finding in an unknown and unstructured environment. The reference domain for rescue robots is the rescue-world arenas purposefully arranged for the Robocup competitions. The main task of a rescue mobile robot is to explore the environment and report to the rescue-operators the map of visited areas annotated with its finding. In this context all the attentional activities play a major role in decision processes: salient elements in the environment yield utilities and objectives. A model-based executive controller is proposed to coordinate, integrate, and monitor the distributed decisions and initiatives emerging from the modules involved in the control loop. We show how this architecture integrates the reactive model-based control of a rescue mission, with an attentive perceptual activity processing the sensor and visual stimuli. The architecture has been implemented and tested in real-world experiments by comparing the performances of metric exploration and attentive exploration. The results obtained demonstrate that the attentive behavior significantly focus the exploration time in salient areas enhancing the overall victim finding effectiveness.
---
paper_title: Plan stability: Replanning versus plan repair

paper_content:

The ultimate objective in planning is to construct plans for execution. However, when a plan is executed in a real environment it can encounter differences between the expected and actual context of execution. These differences can manifest as divergences between the expected and observed states of the world, or as a change in the goals to be achieved by the plan. In both cases, the old plan must be replaced with a new one. In replacing the plan an important consideration is plan stability. We compare two alternative strategies for achieving the stable repair of a plan: one is simply to replan from scratch and the other is to adapt the existing plan to the new context. ::: ::: We present arguments to support the claim that plan stability is a valuable property. We then propose an implementation, based on LPG, of a plan repair strategy that adapts a plan to its new context. We demonstrate empirically that our plan repair strategy achieves more stability than replanning and can produce repaired plans more efficiently than replanning.
---
paper_title: Plan Reuse Versus Plan Generation: A Theoretical and Empirical Analysis

paper_content:

The ability of a planner to reuse parts of old plans is hypothesized to be a valuable tool for improving efficiency of planning by avoiding the repetition of the same planning effort. We test this hypothesis from an analytical and empirical point of view. A comparative worst-case complexity analysis of generation and reuse under different assumptions reveals that it is not possible to achieve a provable efficiency gain of reuse over generation. Further, assuming "conservative" plan modification, plan reuse can actually be strictly more difficult than plan generation. While these results do not imply that there won't be an efficiency gain in the "average case", retrieval of a good plan may present a serious bottleneck for plan reuse systems, as we will show. Finally, we present the results of an empirical study of three different plan reuse systems, which leads us to the conclusion that the utility of plan-reuse techniques is limited and that these limits have not been determined yet.
---
paper_title: Adapting a Rapidly-Exploring Random Tree for Automated Planning

paper_content:

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

paper_content:

Abstract In order to model plan coordination behavior of agents we develop a simple framework for representing plans, resources and goals of agents. Plans are represented as directed acyclic graphs of skills and resources that, given adequate initial resources, can realize special resources, called goals. Given the storage costs of resources, application costs of skills, and values of goals, it is possible to reason about the profits of a plan for an agent. We then model two forms of plan coordination behavior between two agents, viz. fusion , aiming at the maximization of the total yield of the agents involved, and collaboration , which aims at the maximization of the individual yield of each agent. We argue how both forms of cooperation can be seen as iterative plan revision processes. We also present efficient polynomial algorithms for agent plan fusion and collaboration that are based on this idea of iterative plan revision. Both the framework and the fusion algorithm will be illustrated by an example from the field of transportation, where agents are transportation companies.
---
paper_title: Plan repair as an extension of planning

paper_content:

In dynamic environments, agents have to deal with changing situations. In these cases, repairing a plan is often more efficient than planning from scratch, but existing planning techniques are more advanced than existing plan repair techniques. Therefore, we propose a straightforward method to extend planning techniques such that they are able to repair plans. This is possible, because plan repair consists of two different operations: (i) removing obstructing constraints (such as actions) from the plan, and (ii) adding actions to achieve the goals. Adding actions is similar to planning, but as we demonstrate, planning heuristics can also be used for removing constraints, which we call unrefinement. We present a plan repair template that reflects these two operations, and we present a heuristic for unrefinement that can make use of an arbitrary existing planning technique. We apply this method to an existing planning system (VHPOP) resulting in POPR, a plan repair system that performs much better than replanning from scratch, and also significantly better than another recent plan repair method (GPG). Furthermore, we show that the plan repair template is a generalisation of existing plan repair methods.
---
paper_title: A Concise Introduction to Models and Methods for Automated Planning

paper_content:

Planning is the model-based approach to autonomous behavior where the agent behavior is derived automatically from a model of the actions, sensors, and goals. The main challenges in planning are computational as all models, whether featuring uncertainty and feedback or not, are intractable in the worst case when represented in compact form. In this book, we look at a variety of models used in AI planning, and at the methods that have been developed for solving them. The goal is to provide a modern and coherent view of planning that is precise, concise, and mostly self-contained, without being shallow. For this, we make no attempt at covering the whole variety of planning approaches, ideas, and applications, and focus on the essentials. The target audience of the book are students and researchers interested in autonomous behavior and planning from an AI, engineering, or cognitive science perspective. Table of Contents: Preface / Planning and Autonomous Behavior / Classical Planning: Full Information and Deterministic Actions / Classical Planning: Variations and Extensions / Beyond Classical Planning: Transformations / Planning with Sensing: Logical Models / MDP Planning: Stochastic Actions and Full Feedback / POMDP Planning: Stochastic Actions and Partial Feedback / Discussion / Bibliography / Author's Biography
---
paper_title: Intelligent Planning: A Decomposition and Abstraction Based Approach

paper_content:

This monograph on planning based on Artificial Intelligence methods may serve both as an advanced textbook and as a general reference book. AI planning is an active research and applications field concerned with action and plan representation, plan synthesis and reasoning, analysis of planning algorithms, plan execution and monitoring, and plan reuse and learning. The book provides a clear, thorough coverage of key areas of classical AI planning. Its main theme is to build more intelligence on a set of basic algorithms and representations for planning. It presents advanced techniques for plan generation using decomposition and plan merging and for analyzing and comparing planning algorithms. The book contains illustrations, examples, algorithms, analyses, tables, and extensive references.
---
paper_title: Practical Planning: Extending the Classical AI Planning Paradigm

paper_content:

1 Reasoning about Actions and Planning 2 Basic Assumptions and Limitations 3 SIPE and Its Representations 4 Hierarchical Planning as Differing Abstraction Levels 5 Constraints 6. The Truth Criterion 7 Deductive Causal Theories 8 Plan Critics 9 Resources: Reusable, Consumable, Temporal 10 Search 11 Replanning During Execution 12 Planning and Reactivity 13 Achieving Heuristic Adequacy 14 Comparison with Other Systems
---
paper_title: RRT-Plan: a Randomized Algorithm for STRIPS Planning

paper_content:

We propose a randomized STRIPS planning algorithm called RRT-Plan. This planner is inspired by the idea of Rapidly exploring Random Trees, a concept originally designed for use in continuous path planning problems. Issues that arise in the conversion of RRTs from continuous to discrete spaces are discussed, and several additional mechanisms are proposed to improve performance. Our experimental results indicate that RRT-Plan is competitive with the state of the art in STRIPS planning.
---
paper_title: Hierarchical task and motion planning in the now

paper_content:

In this paper we outline an approach to the integration of task planning and motion planning that has the following key properties: It is aggressively hierarchical. It makes choices and commits to them in a top-down fashion in an attempt to limit the length of plans that need to be constructed, and thereby exponentially decrease the amount of search required. Importantly, our approach also limits the need to project the effect of actions into the far future. It operates on detailed, continuous geometric representations and partial symbolic descriptions. It does not require a complete symbolic representation of the input geometry or of the geometric effect of the task-level operations.
---
paper_title: Combining planning and motion planning

paper_content:

Robotic manipulation is important for real, physical world ::: applications. General Purpose manipulation with a robot (eg. ::: delivering dishes, opening doors with a key, etc.) is demanding. ::: It is hard because (1) objects are constrained in position ::: and orientation, (2) many non-spatial constraints interact ::: (or interfere) with each other, and (3) robots may have multidegree ::: of freedoms (DOF). In this paper we solve the problem ::: of general purpose robotic manipulation using a novel ::: combination of planning and motion planning. Our approach ::: integrates motions of a robot with other (non-physical or ::: external-to-robot) actions to achieve a goal while manipulating ::: objects. It differs from previous, hierarchical approaches ::: in that (a) it considers kinematic constraints in configuration ::: space (C-space) together with constraints over object manipulations; ::: (b) it automatically generates high-level (logical) actions ::: from a C-space based motion planning algorithm; and ::: (c) it decomposes a planning problem into small segments, ::: thus reducing the complexity of planning.
---
paper_title: Efficient Physics-Based Planning: Sampling Search Via Non-Deterministic Tactics and Skills

paper_content:

Motion planning for mobile agents, such as robots, acting in the physical world is a challenging task, which traditionally concerns safe obstacle avoidance. We are interested in physics-based planning beyond collision-free navigation goals, in which the agent also needs to achieve its goals, including purposefully manipulate non-actuated bodies, in environments that contain multiple physically interacting bodies with varying degrees of controllability. Physics-based planning is computationally hard due to the large number of continuous motion actions and to the difficulty in accurately modeling the rich interactions of such controlled, manipulatable, and uncontrolled, potentially adversarial, bodies. We contribute an efficient physics-based planning algorithm that uses the agent's high-level behaviors to reduce its motion action space. We first discuss the general physics-based planning problem. We then introduce Tactics and Skills as a model for infusing goal-driven, higher level behaviors into a randomized motion planner. We present a physics-based state and transition model that employs rigid body simulations to approximate real-world interbody-dynamics. We introduce and compare two variations of our tactics-driven, physics-based planning algorithm, namely Behavioral Kinodynamic Balanced Growth Trees and Behavioral Kinodynamic Rapidly-Exploring Random Trees. We tested our physics-based planners in a variety of rich domains and show results in simulated domains where the agent manipulates an object in a dynamic non-adversarial and adversarial environment, namely in a robot minigolf and robot soccer domain, respectively.
---
paper_title: Planning foot placements for a humanoid robot: A problem of inverse kinematics

paper_content:

We present a novel approach to plan foot placements for a humanoid robot according to kinematic tasks. In this approach, the foot placements are determined by the continuous deformation of a robot motion including a locomotion phase according to the desired tasks. We propose to represent the motion by a virtual kinematic tree composed of a kinematic model of the robot and articulated foot placements. This representation allows us to formulate the motion deformation problem as a classical inverse kinematics problem on a kinematic tree. We first provide details of the basic scheme where the number of footsteps is given in advance and illustrate it with scenarios on the robot HRP-2. Then we propose a general criterion and an algorithm to adapt the number of footsteps progressively to the kinematic goal. The limits and possible extensions of this approach are discussed last.
---
paper_title: Visual servoing and visual tracking

paper_content:

This chapter introduces visual servo control, using computer vision data in the servo loop to control the motion of a robot. We first describe the basic tech- niques that are by now well established in the field. We give a general overview of the formulation of the visual servo control problem, and describe the two archetypal visual servo control schemes: image-based and position-based visual servo control. We then dis- cuss performance and stability issues that pertain to these two schemes, motivating advanced techniques. Of the many advanced techniques that have been de- veloped, we discuss 2 1/2 D, hybrid, partitioned and switched approaches. Having covered a variety of control schemes, we conclude by turning briefly to the problems of target tracking and controlling mo- tion directly in the joint space.
---
paper_title: A Hybrid Approach to Intricate Motion, Manipulation and Task Planning

paper_content:

We propose a representation and a planning algorithm able to deal with problems integrating task planning as well as motion and manipulation planning knowledge involving several robots and objects. Robot plans often include actions where the robot has to place itself in some position in order to perform some other action or to “modify” the configuration of its environment by displacing objects. Our approach aims at establishing a bridge between task planning and manipulation planning that allows a rigorous treatment of geometric preconditions and effects of robot actions in realistic environments. We show how links can be established between a symbolic description and its geometric counterpart and how they can be used in an integrated planning process that is able to deal with intricate symbolic and geometric constraints. Finally, we describe the main features of an implemented planner and discuss several examples of its use.
---
paper_title: On-line Planning and Scheduling: An Application to Controlling Modular Printers

paper_content:

This paper summarizes recent work reported at ICAPS on applying artificial intelligence techniques to the control of production printing equipment. Like many other real-world applications, such as mobile robotics, this complex domain requires real-time autonomous decision-making and robust continual operation. To our knowledge, this work represents the first successful industrial application of embedded domain-independent temporal planning. At the heart of our system is an on-line algorithm that combines techniques from state-space planning and partial-order scheduling. For example, our planning-graph-based planning heuristic takes resource contention into account when estimating makespan remaining. We suggest that this general architecture may prove useful as more intelligent systems operate in continual, online settings. Our system has enabled a new product architecture for our industrial partner and has been used to drive several commercial prototypes. When compared with stateof-the-art off-line planners, our system is hundreds of times faster and often finds better plans.
---
paper_title: Constraint-Based Attribute and Interval Planning

paper_content:

In this paper we describe Constraint-based Attribute and Interval Planning (CAIP), a paradigm for representing and reasoning about plans. The paradigm enables the description of planning domains with time, resources, concurrent activities, mutual exclusions among sets of activities, disjunctive preconditions and conditional effects. We provide a theoretical foundation for the paradigm, based on temporal intervals and attributes. We show how the plans are naturally expressed by networks of constraints, and show that the process of planning maps directly to dynamic constraint reasoning. We describe compatibilities, a compact mechanism for describing planning domains. We also demonstrate how this framework incorporates the use of constraint representation and reasoning technology to improve planning. Finally, we describe EUROPA, an implementation of the CAIP framework.
---
paper_title: COLIN: Planning with Continuous Linear Numeric Change

paper_content:

In this paper we describe COLIN, a forward-chaining heuristic search planner, capable of reasoning with COntinuous LINear numeric change, in addition to the full temporal semantics of PDDL2.1. Through this work we make two advances to the state-of-the-art in terms of expressive reasoning capabilities of planners: the handling of continuous linear change, and the handling of duration-dependent effects in combination with duration inequalities, both of which require tightly coupled temporal and numeric reasoning during planning. COLIN combines FF-style forward chaining search, with the use of a Linear Program (LP) to check the consistency of the interacting temporal and numeric constraints at each state. The LP is used to compute bounds on the values of variables in each state, reducing the range of actions that need to be considered for application. In addition, we develop an extension of the Temporal Relaxed Planning Graph heuristic of CRIKEY3, to support reasoning directly with continuous change. We extend the range of task variables considered to be suitable candidates for specifying the gradient of the continuous numeric change effected by an action. Finally, we explore the potential for employing mixed integer programming as a tool for optimising the timestamps of the actions in the plan, once a solution has been found. To support this, we further contribute a selection of extended benchmark domains that include continuous numeric effects. We present results for COLIN that demonstrate its scalability on a range of benchmarks, and compare to existing state-of-the-art planners.
---
paper_title: VHPOP: Versatile Heuristic Partial Order Planner

paper_content:

VHPOP is a partial order causal link (POCL) planner loosely based on UCPOP. It draws from the experience gained in the early to mid 1990's on flaw selection strategies for POCL planning, and combines this with more recent developments in the field of domain independent planning such as distance based heuristics and reachability analysis. We present an adaptation of the additive heuristic for plan space planning, and modify it to account for possible reuse of existing actions in a plan. We also propose a large set of novel flaw selection strategies, and show how these can help us solve more problems than previously possible by POCL planners. VHPOP also supports planning with durative actions by incorporating standard techniques for temporal constraint reasoning. We demonstrate that the same heuristic techniques used to boost the performance of classical POCL planning can be effective in domains with durative actions as well. The result is a versatile heuristic POCL planner competitive with established CSP-based and heuristic state space planners.
---
paper_title: Planning in Interplanetary Space: Theory and Practice

paper_content:

On May 17th 1999, NASA activated for the first time an AI-based planner/scheduler running on the flight processor of a spacecraft. This was part of the Remote Agent Experiment (RAX), a demonstration of closed-loop planning and execution, and model-based state inference and failure recovery. This paper describes the RAX Planner/Scheduler (RAX-PS), both in terms of the underlying planning framework and in terms of the fielded planner. RAX-PS plans are networks of constraints, built incrementally by consulting a model of the dynamics of the spacecraft. The RAX-PS planning procedure is formally well defined and can be proved to be complete. RAX-PS generates plans that are temporally flexible, allowing the execution system to adjust to actual plan execution conditions without breaking the plan. The practical aspect, developing a mission critical application, required paying attention to important engineering issues such as the design of methods for programmable search control, knowledge acquisition and planner validation. The result was a system capable of building concurrent plans with over a hundred tasks within the performance requirements of operational, mission-critical software.
---
paper_title: Representation and control in IxTeT, a temporal planner

paper_content:

This paper presents a temporal planner, called IxTeT. It focuses on the representation and control issues, arguing for a compromise between the expressiveness and the efficiency of the search. The representation relies on a point-based reified logic, associated to multi-valued domain attributes. Hierarchical planning operators offer an expressive description, with parallelism, durations, effects and conditions at various moments of the action. Time in the input scenario enables to take into account predicted forthcoming events and to plan in a dynamic world. A compilation procedure checks the consistency of the operators specified by the user. The control relies on the use of causal-links, Ae, algorithm, and an extended least-commitment strategy. It uses two important procedures, called "feasibility" and "satisfiability", dealing respectively with goal decomposition and conflict resolution:
---
paper_title: Planning with Problems Requiring Temporal Coordination

paper_content:

We present the first planner capable of reasoning with both the full semantics of PDDL2.1 (level 3) temporal planning and with numeric resources. Our planner, CRIKEY3, employs heuristic forward search, using the start-and-end semantics of PDDL2.1 to manage temporal actions. The planning phase is interleaved with a scheduling phase, using a Simple Temporal Network, in order to ensure that temporal constraints are met. To guide search, we introduce a new temporal variant of the Relaxed Planning Graph heuristic that is capable of reasoning with the features of this class of domains, along with the Timed Initial Literals of PDDL2.2. CRIKEY3 extends the state-of-the-art in handling the full temporal expressive power of PDDL2.1, including numeric temporal domains.
---
paper_title: A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes

paper_content:

A critical issue for the application of Markov decision processes (MDPs) to realistic problems is how the complexity of planning scales with the size of the MDP. In stochastic environments with very large or infinite state spaces, traditional planning and reinforcement learning algorithms may be inapplicable, since their running time typically grows linearly with the state space size in the worst case. In this paper we present a new algorithm that, given only a generative model (a natural and common type of simulator) for an arbitrary MDP, performs on-line, near-optimal planning with a per-state running time that has no dependence on the number of states. The running time is exponential in the horizon time (which depends only on the discount factor γ and the desired degree of approximation to the optimal policy). Our algorithm thus provides a different complexity trade-off than classical algorithms such as value iteration—rather than scaling linearly in both horizon time and state space size, our running time trades an exponential dependence on the former in exchange for no dependence on the latter. ::: ::: Our algorithm is based on the idea of sparse sampling. We prove that a randomly sampled look-ahead tree that covers only a vanishing fraction of the full look-ahead tree nevertheless suffices to compute near-optimal actions from any state of an MDP. Practical implementations of the algorithm are discussed, and we draw ties to our related recent results on finding a near-best strategy from a given class of strategies in very large partially observable MDPs (Kearns, Mansour, & Ng. Neural information processing systems 13, to appear).
---
paper_title: Optimistic planning for sparsely stochastic systems

paper_content:

We propose an online planning algorithm for finite-action, sparsely stochastic Markov decision processes, in which the random state transitions can only end up in a small number of possible next states. The algorithm builds a planning tree by iteratively expanding states, where each expansion exploits sparsity to add all possible successor states. Each state to expand is actively chosen to improve the knowledge about action quality, and this allows the algorithm to return a good action after a strictly limited number of expansions. More specifically, the active selection method is optimistic in that it chooses the most promising states first, so the novel algorithm is called optimistic planning for sparsely stochastic systems. We note that the new algorithm can also be seen as model-predictive (receding-horizon) control. The algorithm obtains promising numerical results, including the successful online control of a simulated HIV infection with stochastic drug effectiveness.
---
paper_title: Heuristic search for generalized stochastic shortest path MDPs

paper_content:

Research in efficient methods for solving infinite-horizon MDPs has so far concentrated primarily on discounted MDPs and the more general stochastic shortest path problems (SSPs). These are MDPs with 1) an optimal value function V* that is the unique solution of Bellman equation and 2) optimal policies that are the greedy policies w.r.t. V*. ::: ::: This paper's main contribution is the description of a new class of MDPs, that have well-defined optimal solutions that do not comply with either 1 or 2 above. We call our new class Generalized Stochastic Shortest Path (GSSP) problems. GSSP allows more general reward structure than SSP and subsumes several established MDP types including SSP, positive-bounded, negative, and discounted-reward models. While existing efficient heuristic search algorithms like LAO* and LRTDP are not guaranteed to converge to the optimal value function for GSSPs, we present a new heuristic-search-based family of algorithms, FRET (Find, Revise, Eliminate Traps). A preliminary empirical evaluation shows that FRET solves GSSPs much more efficiently than Value Iteration.
---
paper_title: Incremental plan aggregation for generating policies in MDPs

paper_content:

Despite the recent advances in planning with MDPs, the problem of generating good policies is still hard. This paper describes a way to generate policies in MDPs by (1) determinizing the given MDP model into a classical planning problem; (2) building partial policies off-line by producing solution plans to the classical planning problem and incrementally aggregating them into a policy, and (3) using sequential Monte-Carlo (MC) simulations of the partial policies before execution, in order to assess the probability of replanning for a policy during execution. The objective of this approach is to quickly generate policies whose probability of replanning is low and below a given threshold. ::: ::: We describe our planner RFF, which incorporates the above ideas. We present theorems showing the termination, soundness and completeness properties of RFF. RFF was the winner of the fully-observable probabilistic track in the 2008 International Planning Competition (IPC-08). In addition to our analyses of the IPC-08 results, we analyzed RFF's performance with different plan aggregation and determinization strategies, with varying amount of MC sampling, and with varying threshold values for probability of replanning. The results of these experiments revealed how they impact the time performance of RFF to generate solution policies and the quality of those solution policies (i.e., the average accumulated reward gathered from the execution of the policies).
---
paper_title: Learning to act using real-time dynamic programming

paper_content:

Learning methods based on dynamic programming (DP) are receiving increasing attention in artificial intelligence. Researchers have argued that DP provides the appropriate basis for compiling planning results into reactive strategies for real-time control, as well as for learning such strategies when the system being controlled is incompletely known. We introduce an algorithm based on DF, which we call Real-Time DP (RTDP), by which an embedded system can improve its performance with experience. RTDP generalizes Korf's Learning-Real-Time-A* algorithm to problems involving uncertainty. We invoke results from the theory of asynchronous DP to prove that RTDP achieves optimal behavior in several different classes of problems. We also use the theory of asynchronous DF to illuminate aspects of other DP-based reinforcement learning methods such as Watkins' Q-Learning algorithm. A secondary aim of this article is to provide a bridge between Al research on real-time planning and learning and relevant concepts and algorithms from control theory.
---
paper_title: SixthSense: Fast and reliable recognition of dead ends in MDPs

paper_content:

The results of the latest International Probabilistic Planning Competition (IPPC-2008) indicate that the presence of dead ends, states with no trajectory to the goal, makes MDPs hard for modern probabilistic planners. Implicit dead ends, states with executable actions but no path to the goal, are particularly challenging; existing MDP solvers spend much time and memory identifying these states. ::: ::: As a first attempt to address this issue, we propose a machine learning algorithm called SIXTHSENSE. SIXTHSENSE helps existing MDP solvers by finding nogoods, conjunctions of literals whose truth in a state implies that the state is a dead end. Importantly, our learned nogoods are sound, and hence the states they identify are true dead ends. SIXTHSENSE is very fast, needs little training data, and takes only a small fraction of total planning time. While IPPC problems may have millions of dead ends, they may typically be represented with only a dozen or two no-goods. Thus, nogood learning efficiently produces a quick and reliable means for dead-end recognition. Our experiments show that the nogoods found by SIXTHSENSE routinely reduce planning space and time on IPPC domains, enabling some planners to solve problems they could not previously handle.
---
paper_title: Learning Depth-First Search: A Unified Approach to Heuristic Search in Deterministic and Non-Deterministic Settings, and its application to MDPs

paper_content:

Dynamic Programming provides a convenient and unified framework for studying many state models used in AI but no algorithms for handling large spaces. Heuristic-search methods, on the other hand, can handle large spaces but lack a common foundation. In this work, we combine the benefits of a general dynamic programming formulation with the power of heuristic-search techniques for developing an algorithmic framework, that we call Learning Depth-First Search, that aims to be both general and effective. LDFS is a simple piece of code that performs iterated depth-first searches enhanced with learning. For deterministic actions and monotone value functions, LDFS reduces to IDA* with transposition tables, while for Game Trees, to the state-of-the-art iterated Alpha-Beta search algorithm with Null Windows known as MTD. For other models, like AND/OR graphs and MDPs, LDFS yields new, simple, and competitive algorithms. We show this here for MDPs.
---
paper_title: Planning with Markov Decision Processes: An AI Perspective

paper_content:

Markov Decision Processes (MDPs) are widely popular in Artificial Intelligence for modeling sequential decision-making scenarios with probabilistic dynamics. They are the framework of choice when designing an intelligent agent that needs to act for long periods of time in an environment where its actions could have uncertain outcomes. MDPs are actively researched in two related subareas of AI, probabilistic planning and reinforcement learning. Probabilistic planning assumes known models for the agent's goals and domain dynamics, and focuses on determining how the agent should behave to achieve its objectives. On the other hand, reinforcement learning additionally learns these models based on the feedback the agent gets from the environment. This book provides a concise introduction to the use of MDPs for solving probabilistic planning problems, with an emphasis on the algorithmic perspective. It covers the whole spectrum of the field, from the basics to state-of-the-art optimal and approximation algorithms. We first describe the theoretical foundations of MDPs and the fundamental solution techniques for them. We then discuss modern optimal algorithms based on heuristic search and the use of structured representations. A major focus of the book is on the numerous approximation schemes for MDPs that have been developed in the AI literature. These include determinization-based approaches, sampling techniques, heuristic functions, dimensionality reduction, and hierarchical representations. Finally, we briefly introduce several extensions of the standard MDP classes that model and solve even more complex planning problems. Table of Contents: Introduction / MDPs / Fundamental Algorithms / Heuristic Search Algorithms / Symbolic Algorithms / Approximation Algorithms / Advanced Notes
---
paper_title: Short-Sighted Stochastic Shortest Path Problems

paper_content:

Algorithms to solve probabilistic planning problems can be classified in probabilistic planners and replanners. Probabilistic planners invest significant computational effort to generate a closed policy, i.e., a mapping function from every state to an action, and these solutions never "fail" if the problem correctly models the environment. Alternatively, replanners computes a partial policy, i.e., a mapping function from a set of the state space to an action, and when and if such policy fails during execution in the environment, the replanner is re-invoked to plan again from the failed state. In this paper, we introduce a special case of Stochastic Shortest Path Problems (SSPs), the short-sighted SSPs, in which every state has positive probability of being reached using at most t actions. We introduce the novel algorithm Short-Sighted Probabilistic Planner (SSiPP) that solves SSPs through short-sighted SSPs and guarantees that at least t actions can be executed without replanning. Therefore, by varying t, SSiPP can behave as either a probabilistic planner by computing closed policies, or a replanner by computing partial policies. Moreover, we prove that SSiPP isasymptotically optimal, making SSiPP the only planner that, at the same time, guarantees optimality and offers a bound in the minimum number of actions executed without replanning. We empirically compare SSiPP with the winners of the previous probabilistic planning competitions and, in 81.7% of the problems, SSiPP performs at least as good as the best competitor.
---
paper_title: Decision-Theoretic Planning: Structural Assumptions and Computational Leverage

paper_content:

Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory. ::: ::: This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations. ::: ::: Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques-- in particular those based on the use of structured, intensional representations--can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.
---
paper_title: Planning Robust Temporal Plans A Comparison Between CBTP and TGA Approaches

paper_content:

Planning for real world applications, with explicit temporal representation and a robust execution is a very challenging problem. To tackle it, the planning community has proposed a number of original and successful approaches. However, there are other paradigms "outside" the Automated Planning field which may prove to be successful with respect to this objective. This paper presents a comparison of two "planning" approaches dealing with temporal and/or discrete uncertainties and with a strong emphasis on robust execution. The first approach is based on chronicles and constraint satisfaction techniques; it relies on a causal link partial order temporal planner, in our case IXTET. The second approach is based on timed game automata and reachability analysis, and uses the UPPAAL-TIGA system. The comparison is both qualitative (the kind of problems modeled and the properties of plans obtained) and quantitative (experimental results on a real example). To make this comparison possible, we propose a general scheme to translate a subset of IXTET planning problems into UPPAAL-TIGA game-reachability problems. A direct consequence of this automated process would be the possibility to apply validation and verification techniques available in the timed automata community.
---
paper_title: Planning for Markov Decision Processes with Sparse Stochasticity

paper_content:

Planning algorithms designed for deterministic worlds, such as A* search, usually run much faster than algorithms designed for worlds with uncertain action outcomes, such as value iteration. Real-world planning problems often exhibit uncertainty, which forces us to use the slower algorithms to solve them. Many real-world planning problems exhibit sparse uncertainty: there are long sequences of deterministic actions which accomplish tasks like moving sensor platforms into place, interspersed with a small number of sensing actions which have uncertain outcomes. In this paper we describe a new planning algorithm, called MCP (short for MDP Compression Planning), which combines A* search with value iteration for solving Stochastic Shortest Path problem in MDPs with sparse stochasticity. We present experiments which show that MCP can run substantially faster than competing planners in domains with sparse uncertainty; these experiments are based on a simulation of a ground robot cooperating with a helicopter to fill in a partial map and move to a goal location.
---
paper_title: LAO*: A heuristic search algorithm that finds solutions with loops

paper_content:

Classic heuristic search algorithms can find solutions that take the form of a simple path (A*), a tree, or an acyclic graph (AO*). In this paper, we describe a novel generalization of heuristic search, called LAO*, that can find solutions with loops. We show that LAO* can be used to solve Markov decision problems and that it shares the advantage heuristic search has over dynamic programming for other classes of problems. Given a start state, it can find an optimal solution without evaluating the entire state space.  2001 Elsevier Science B.V. All rights reserved.
---
paper_title: Using the Web to Interactively Learn to Find Objects

paper_content:

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

paper_content:

In (Petrick and Bacchus 2002), a "knowledge-level" approach to planning under incomplete knowledge and sensing was presented. In comparison with alternate approaches based on representing sets of possible worlds, this higher-level representation is richer, but the inferences it supports are weaker. Nevertheless, because of its richer representation, it is able to solve problems that cannot be solved by alternate approaches. ::: ::: In this paper we examine a collection of new techniques for increasing both the representational and inferential power of the knowledge-level approach. These techniques have been fully implemented in the PKS (Planning with Knowledge and Sensing) planning system. Taken together they allow us to solve a range of new types of planning problems under incomplete knowledge and sensing.
---
paper_title: Fusing DL Reasoning with HTN Planning

paper_content:

We describe a method for cascading Description Logic (DL) representation and reasoning on the one hand, and HTN action planning on the other. The planning domain description as well as the fundamental HTN planning concepts are represented in DL and can therefore be subject to DL reasoning; from these representations, concise planning problems are generated for HTN planning. We show that this method yields significantly smaller planning problem descriptions than regular representations do in HTN planning. The method is presented by example of a robot navigation domain.
---
paper_title: A Blackboard Architecture for Control

paper_content:

Abstract The control problem—which of its potential actions should an AI system perform at each point in the problem-solving process?—is fundamental to all cognitive processes. This paper proposes eight behavioral goals for intelligent control and a ‘blackboard control architecture’ to achieve them. The architecture distinguishes domain and control problems, knowledge, and solutions. It enables AI systems to operate upon their own knowledge and behavior and to adapt to unanticipated problem-solving situations. The paper shows how opm , a blackboard control system for multiple-task planning, exploits these capabilities. It also shows how the architecture would replicate the control behavior of hearsay-ii and hasp . The paper contrasts the blackboard control architecture with three alternatives and shows how it continues an evolutionary progression of control architectures. The paper concludes with a summary of the blackboard control architecture's strengths and weaknesses.
---
paper_title: Continual planning and acting in dynamic multiagent environments

paper_content:

In order to behave intelligently, artificial agents must be able to deliberatively plan their future actions. Unfortunately, realistic agent environments are usually highly dynamic and only partially observable, which makes planning computationally hard. For most practical purposes this rules out planning techniques that account for all possible contingencies in the planning process. However, many agent environments permit an alternative approach, namely continual planning, i.e. the interleaving of planning with acting and sensing. This paper presents a new principled approach to continual planning that describes why and when an agent should switch between planning and acting. The resulting continual planning algorithm enables agents to deliberately postpone parts of their planning process and instead actively gather missing information that is relevant for the later refinement of the plan. To this end, the algorithm explictly reasons about the knowledge (or lack thereof) of an agent and its sensory capabilities. These concepts are modelled in the planning language (MAPL). Since in many environments the major reason for dynamism is the behaviour of other agents, MAPL can also model multiagent environments, common knowledge among agents, and communicative actions between them. For Continual Planning, MAPL introduces the concept of of assertions, abstract actions that substitute yet unformed subplans. To evaluate our continual planning approach empirically we have developed MAPSIM, a simulation environment that automatically builds multiagent simulations from formal MAPL domains. Thus, agents can not only plan, but also execute their plans, perceive their environment, and interact with each other. Our experiments show that, using continual planning techniques, deliberate action planning can be used efficiently even in complex multiagent environments.
---
paper_title: ORO, a knowledge management platform for cognitive architectures in robotics

paper_content:

This paper presents an embeddable knowledge processing framework, along with a common-sense ontology, designed for robotics. We believe that a direct and explicit integration of cognition is a compulsory step to enable human-robots interaction in semantic-rich human environments like our houses. The OpenRobots Ontology (ORO) kernel allows to turn previously acquired symbols into concepts linked to each other. It enables in turn reasoning and the implementation of other advanced cognitive functions like events, categorization, memory management and reasoning on parallel cognitive models. We validate this framework on several cognitive scenarii that have been implemented on three different robotic architectures.
---
paper_title: An Ontology-based Multi-level Robot Architecture for Learning from Experiences

paper_content:

One way to improve the robustness and flexibility of robot performance is to let the robot learn from its ex- periences. In this paper, we describe the architecture and knowledge-representation framework for a service robot being developed in the EU project RACE, and present examples illustrating how learning from experi- ences will be achieved. As a unique innovative feature, the framework combines memory records of low-level robot activities with ontology-based high-level seman- tic descriptions.
---
paper_title: Integrating planning, execution and monitoring

paper_content:

IPEM, for Integrated Planning, Execution and Monitoring, provides a simple, clear and well defined framework to integrate these processes. Representation integration is achieved by naturally incorporating execution and monitoring information into [Chapman, 1987] tweak's partial plan representation. Control integration is obtained by using a production system architecture where IF-THEN rules, referred to as flaws and fixes, specify partial plan transformations. Conflict resolution is done using a scheduler that embodies the current problem solving strategy. ::: ::: Since execution and plan elaboration operations have been designed to be independently applicable, and execution of an action is a scheduling decision like any other, the framework effectively supports interleaving of planning and execution (IPE). This renders a local ability to replan after both unexpected events and execution failure. ::: ::: The framework has served as the basis for an implemented hierarchical, nonlinear planning and execution system that has been tested on numerous examples, on various domains, and has shown to be reliable and robust.
---
paper_title: GOLOG: A Logic Programming Language for Dynamic Domains

paper_content:

Abstract This paper proposes a new logic programming language called GOLOG whose interpreter automatically maintains an explicit representation of the dynamic world being modeled, on the basis of user supplied axioms about the preconditions and effects of actions and the initial state of the world. This allows programs to reason about the state of the world and consider the effects of various possible courses of action before committing to a particular behavior. The net effect is that programs may be written at a much higher level of abstraction than is usually possible. The language appears well suited for applications in high level control of robots and industrial processes, intelligent software agents, discrete event simulation, etc. It is based on a formal theory of action specified in an extended version of the situation calculus. A prototype implementation in Prolog has been developed.
---
paper_title: Hierarchical Solution of Markov Decision Processes using Macro-actions

paper_content:

We investigate the use of temporally abstract actions, or macro-actions, in the solution of Markov decision processes. Unlike current models that combine both primitive actions and macro-actions and leave the state space unchanged, we propose a hierarchical model (using an abstract MDP) that works with macro-actions only, and that significantly reduces the size of the state space. This is achieved by treating macroactions as local policies that act in certain regions of state space, and by restricting states in the abstract MDP to those at the boundaries of regions. The abstract MDP approximates the original and can be solved more efficiently. We discuss several ways in which macro-actions can be generated to ensure good solution quality. Finally, we consider ways in which macro-actions can be reused to solve multiple, related MDPs; and we show that this can justify the computational overhead of macro-action generation.
---
paper_title: A deliberative architecture for AUV control

paper_content:

Autonomous Underwater Vehicles (AUVs) are an increasingly important tool for oceanographic research demonstrating their capabilities to sample the water column in depths far beyond what humans are capable of visiting, and doing so routinely and cost-effectively. However, control of these platforms to date has relied on fixed sequences for execution of pre-planned actions limiting their effectiveness for measuring dynamic and episodic ocean phenomenon. In this paper we present an agent architecture developed to overcome this limitation through on-board planning using Constraint- based Reasoning. Preliminary versions of the architecture have been integrated and tested in simulation and at sea.
---
paper_title: PRS: a high level supervision and control language for autonomous mobile robots

paper_content:

We discuss Procedural Reasoning System (PRS) as a high-level control and supervision language adapted to autonomous robots to represent and execute procedures, scripts and plans in dynamic environments. We discuss the main reasons why PRS is well suited for this type of application: (1) The semantics of its plan (procedure) representation, which is important for plan execution and goal refinement; (2) Its ability to construct and act on partial (rather than complete) plans; (3) Its ability to pursue goal-directed tasks while at the same time being responsive to changing patterns of events in bounded time; (4) Its facilities for managing multiple tasks in real-time; (5) Its default mechanisms for handling stringent real-time demands of its environment; and (6) Its meta-level (or reflective) reasoning capabilities. C-PRS has been used to implement an embedded control and supervision system for autonomous mobile robots in two different experimentations that we briefly present. We conclude with some suggestions to further develop C-PRS and with a short review of related work.
---
paper_title: An investigation into reactive planning in complex domains

paper_content:

A model of purely reactive planning is proposed based on the concept of reactive action packages. A reactive action package, or RAP, can be thought of as an independent entity pursuing some goal in competition with many others at execution time. The RAP processing algorithm addresses the problems of execution monitoring and replanning in uncertain domains with a single, uniform representation and control structure. Use of the RAP model as a basis for adaptive strategic planning is also discussed.
---
paper_title: A Unified Approach to Model-Based Planning and Execution

paper_content:

Writing autonomous software is complex, requiring the coordination of functionally and technologically diverse software modules. System and mission engineers must rely on specialists familiar with the different software modules to translate requirements into application software. Also, each module often encodes the same requirement in different forms. The results are high costs and reduced reliability due to the difficulty of tracking discrepancies in these encodings. In this paper we describe a unified approach to planning and execution that we believe provides a unified representational and computational framework for an autonomous agent. We identify the four main components whose interplay provides the basis for the agent's autonomous behavior: the domain model, the plan database, the plan running module, and the planner modules. This representational and problem solving approach can be applied at all levels of the architecture of a complex agent, such as Remote Agent. In the rest of the paper we briefly describe the Remote Agent architecture. The new agent architecture proposed here aims at achieving the full Remote Agent functionality. We then give the fundamental ideas behind the new agent architecture and point out some implication of the structure of the architecture, mainly in the area of reactivity and interaction between reactive and deliberative decision making. We conclude with related work and current status.
---
paper_title: MONITORED EXECUTION OF ROBOT PLANS PRODUCED BY STRIPS

paper_content:

Abstract : We describe PLANEXl, a plan executor for the Stanford Research Institute robot system. The problem-solving program STRIPS creates a plan consisting of a sequence of actions, and the PLANEXI program carries out the plan by executing the actions. PLANEXI is designed so that it executes only that portion of the plan necessary for completing the task, reexecutes any portion of the plan that has failed to achieve the desired results, and initiates replanning in situations where the plan can no longer be effective in completing the task. The scenario for an example plan execution is given.
---
paper_title: Universal Plans for Reactive Robots in Unpredictable Environments

paper_content:

To date, reactive robot behavior has been achieved only through manual programming. This paper describes a new kind of plan, called a "universal plan", which can be synthesized automatically, yet generates appropriate behavior in unpredictable environments. In classical planning work, problems were posed with unique initial and final world states; in my approach a problem specifies only a goal condition. The planner is thus unable to commit to any specific future course of events but must specify appropriate reactions for anticipated situations. An alternative conception is that one universal plan compactly represents every classical plan. Which part of the universal plan is executed depends entirely on how the environment behaves at execution time. ::: ::: Universal plans are constructed from state-space operator schemas by a nonlinear planner. They explicitly identify predicates requiring monitoring at each moment of execution, and provide for sabotage, serendipity and failure without requiring replanning.
---
paper_title: Mapping Planning Actions and Partially-Ordered Plans into Execution Knowledge

paper_content:

In essence, the underlying ultimate purpose of classical deliberative planning systems is to model some world task and generate plans that can then be executed. Execution systems rely on the assumption that there is a built-in library of a variety of plans and primitive actions for performing tasks. Although hard and time consuming, such libraries of execution plans and actions are usually handcoded. Faced with two different systems, a planner and an executor, we analyze in this work the representational map between planning actions and partially-ordered plans and the execution knowledge. We developed algorithms to automatically translate classical planning operators to execution primitive actions, and partially-ordered plans into executable tasks with partially ordered subtasks. We implemented our work using the PRODIGY planner and the RAP execution system. We provide illustrative examples of how partially-ordered plans produced by PRODIGY are translated to Reactive Action Packages suitable for execution by the RAP system.
---
paper_title: Remote Agent: To Boldly Go Where No AI System Has Gone Before

paper_content:

Abstract Renewed motives for space exploration have inspired NASA to work toward the goal of establishing a virtual presence in space, through heterogeneous fleets of robotic explorers. Information technology, and Artificial Intelligence in particular, will play a central role in this endeavor by endowing these explorers with a form of computational intelligence that we call remote agents . In this paper we describe the Remote Agent, a specific autonomous agent architecture based on the principles of model-based programming, on-board deduction and search, and goal-directed closed-loop commanding, that takes a significant step toward enabling this future. This architecture addresses the unique characteristics of the spacecraft domain that require highly reliable autonomous operations over long periods of time with tight deadlines, resource constraints, and concurrent activity among tightly coupled subsystems. The Remote Agent integrates constraintbased temporal planning and scheduling, robust multi-threaded execution, and model-based mode identification and reconfiguration. The demonstration of the integrated system as an on-board controller for Deep Space One, NASA's first New Millennium mission, is scheduled for a period of a week in mid 1999. The development of the Remote Agent also provided the opportunity to reassess some of AI's conventional wisdom about the challenges of implementing embedded systems, tractable reasoning, and knowledge representation. We discuss these issues, and our often contrary experiences, throughout the paper.
---
paper_title: Structured control for autonomous robots

paper_content:

To operate in rich, dynamic environments, autonomous robots must be able to effectively utilize and coordinate their limited physical and computational resources. As complexity increases, it becomes necessary to impose explicit constraints on the control of planning, perception, and action to ensure that unwanted interactions between behaviors do not occur. This paper advocates developing complex robot systems by layering reactive behaviors onto deliberative components. In this structured control approach, the deliberative components handle normal situations and the reactive behaviors, which are explicitly constrained as to when and how they are activated, handle exceptional situations. The Task Control Architecture (TCA) has been developed to support this approach. TCA provides an integrated set of control constructs useful for implementing deliberative and reactive behaviors. The control constructs facilitate modular and evolutionary system development: they are used to integrate and coordinate planning, perception, and execution, and to incrementally improve the efficiency and robustness of the robot systems. To date, TCA has been used in implementing a half-dozen mobile robot systems, including an autonomous six-legged rover and indoor mobile manipulator. >
---
paper_title: A task description language for robot control

paper_content:

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.
---
paper_title: Learning how to combine sensory-motor functions into a robust behavior

paper_content:

This article describes a system, called Robel, for defining a robot controller that learns from experience very robust ways of performing a high-level task such as ''navigate to''. The designer specifies a collection of skills, represented as hierarchical tasks networks, whose primitives are sensory-motor functions. The skills provide different ways of combining these sensory-motor functions to achieve the desired task. The specified skills are assumed to be complementary and to cover different situations. The relationship between control states, defined through a set of task-dependent features, and the appropriate skills for pursuing the task is learned as a finite observable Markov decision process (MDP). This MDP provides a general policy for the task; it is independent of the environment and characterizes the abilities of the robot for the task.
---
paper_title: Propice-Plan: Toward a Unified Framework for Planning and Execution

paper_content:

In this paper, we investigate the links between planning and plans execution. We propose a new approach (Propice-Plan) which integrates both activities. It implements supervision and execution capabilities, combined with different planning techniques:
---
paper_title: A generic framework for anytime execution-driven planning in robotics

paper_content:

Robotic missions require to implement various functionalities in order to link reactive functions at actuators and sensors level to deliberative functions like vision, supervision and planning at decisional level. All these functionalities must be versatile and generic enough to interact differently according to the missions while minimizing recoding effort. Moreover, deliberative functions like automated planning consume lots of memory and CPU time and usually complete in time incompatible with robotic missions' durations. Thus, we present a new generic and anytime planning concept for modular robotic architectures, which manages multiple planning requests at a time, solved in background, while allowing for reactive execution of planned actions at the same time. Different planners based on various formalisms and data structures can be plugged to the planning component without changing its behavior nor its code, facilitating reusability and validation of the component. We highlight the versatility of our concept on different use cases; then we demonstrate the efficiency of our approach in terms of mission duration and success, compared with traditional plan-then-execute approaches; we finally present a search and rescue mission by an autonomous rotorcraft solved with our paradigm, that cannot be tackled by traditional approaches.
---
paper_title: A Procedural Knowledge Approach to Task-level Control

paper_content:

Effective task-level control is critical for robots that are to engage in purposeful activity in realworld environments. This paper describes PRSLite, a task-level controller grounded in a procedural knowledge approach to action description. The controUer embodies much of the philosophy that underlies the Procedural Reasoning System (PRS) but in a minimalist fashion. Several features of PRS-Lite distinguish it from its predecessor, including a richer goal semantics and a generalized control regime. Both of these features are critical for supporting the management of continuous processes employed in current-generation robots. PRS-Lite has been used extensively as a task-level controller for a robot whose underlying behaviors are implemented as fuzzy rules. Tasks to which it has been applied include vision-based tracking, autonomous exploration, and complex delivery scenaxios.
---
paper_title: Decisional Autonomy of Planetary Rovers

paper_content:

To achieve the ever increasing demand for science return, planetary exploration rovers require more autonomy to successfully perform their missions. Indeed, the communication delays are such that teleoperation is unrealistic. Although the current rovers (such as MER) demonstrate a limited navigation autonomy, and mostly rely on ground mission planning, the next generation (e.g., NASA Mars Science Laboratory and ESA Exomars) will have to regularly achieve long range autonomous navigation tasks. However, fully autonomous long range navigation in partially known planetary-like terrains is still an open challenge for robotics. Navigating hundreds of meters without any human intervention requires the robot to be able to build adequate representations of its environment, to plan and execute trajectories according to the kind of terrain traversed, to control its motions, and to localize itself as it moves. All these activities have to be planned, scheduled, and performed according to the rover context, and controlled so that the mission is correctly fulfilled. To achieve these objectives, we have developed a temporal planner and an execution controller, which exhibit plan repair and replanning capabilities. The planner is in charge of producing plans composed of actions for navigation, science activities (moving and operating instruments), communication with Earth and with an orbiter or a lander, while managing resources (power, memory, etc.) and respecting temporal constraints (communication visibility windows, rendezvous, etc.). High level actions also need to be refined and their execution temporally and logically controlled. Finally, in such critical applications, we believe it is important to deploy a component that protects the system against dangerous or even fatal situations resulting from unexpected interactions between subsystems (e.g., move the robot while the robot arm is unstowed) and/or software components (e.g., take and store a picture in a buffer while the previous one is still being processed). In this article we review the aforementioned capabilities, which have been developed, tested, and evaluated on board our rovers (Lama and Dala). After an overview of the architecture design principle adopted, we summarize the perception, localization, and motion generation functions required by autonomous navigation, and their integration and concurrent operation in a global architecture. We then detail the decisional components: a high level temporal planner that produces the robot activity plan on board, and temporal and procedural execution controllers. We show how some failures or execution delays are being taken care of with online local repair, or replanning. © 2007 Wiley Periodicals, Inc.
---
paper_title: A common knowledge representation for plan generation and reactive execution

paper_content:

Abstract : This paper describes the ACT formalism, which is designed to encode the knowledge required to support both the generation of complex plans and reactive execution of those plans in dynamic environments. ACT is a heuristically adequate representation that is useful in practical applications. It serves as an interlingua for Artificial Intelligence technologies in planning and reactive control. The design of the formalism is discussed and its use in practical applications is demonstrated. These applications show that the ACT representational constructs have reasonable computational properties and also are adequately expressive.
---
paper_title: PRS: a high level supervision and control language for autonomous mobile robots

paper_content:

We discuss Procedural Reasoning System (PRS) as a high-level control and supervision language adapted to autonomous robots to represent and execute procedures, scripts and plans in dynamic environments. We discuss the main reasons why PRS is well suited for this type of application: (1) The semantics of its plan (procedure) representation, which is important for plan execution and goal refinement; (2) Its ability to construct and act on partial (rather than complete) plans; (3) Its ability to pursue goal-directed tasks while at the same time being responsive to changing patterns of events in bounded time; (4) Its facilities for managing multiple tasks in real-time; (5) Its default mechanisms for handling stringent real-time demands of its environment; and (6) Its meta-level (or reflective) reasoning capabilities. C-PRS has been used to implement an embedded control and supervision system for autonomous mobile robots in two different experimentations that we briefly present. We conclude with some suggestions to further develop C-PRS and with a short review of related work.
---
paper_title: Experiences with an architecture for intelligent, reactive agents

paper_content:

This paper briefly describes a robot architecture that has been under development for the last eight years. This architecture uses several levels of abstraction and description languages that are compatible between levels. The makeup of the architecture helps to coordinate planful activities with real-time behaviors for dealing with dynamic environments. In recent years, many architectures have been created with similar attributes. The two features that distinguish this architecture from most of those are: 1) a variety of useful software tools have been created to help implement this architecture on multiple real robots; and 2) this architecture, or parts of it have been implemented on over half a dozen very different robot systems using a variety of processors, operating systems, effectors and sensor suites.
---
paper_title: Concurrent planning and execution for autonomous robots

paper_content:

The task control architecture (TCA) provides communication and coordination facilities to construct distributed, concurrent robotic systems. The use of TCA in a system that walks a legged robot through rugged terrain is described. 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. Walking speed improved by over 30%, with only a relatively modest conversion effort. >
---
paper_title: Integrating planning, execution and monitoring

paper_content:

IPEM, for Integrated Planning, Execution and Monitoring, provides a simple, clear and well defined framework to integrate these processes. Representation integration is achieved by naturally incorporating execution and monitoring information into [Chapman, 1987] tweak's partial plan representation. Control integration is obtained by using a production system architecture where IF-THEN rules, referred to as flaws and fixes, specify partial plan transformations. Conflict resolution is done using a scheduler that embodies the current problem solving strategy. ::: ::: Since execution and plan elaboration operations have been designed to be independently applicable, and execution of an action is a scheduling decision like any other, the framework effectively supports interleaving of planning and execution (IPE). This renders a local ability to replan after both unexpected events and execution failure. ::: ::: The framework has served as the basis for an implemented hierarchical, nonlinear planning and execution system that has been tested on numerous examples, on various domains, and has shown to be reliable and robust.
---
paper_title: Interleaving Temporal Planning and Execution in Robotics Domains

paper_content:

Many autonomous systems such as mobile robots, UAVs or spacecraft, have limited resource capacities and move in dynamic environments. Performing on-board mission planning and execution in such a context requires deliberative capabilities to generate plans achieving mission goals while respecting deadlines and resource constraints, as well as run-time plan adaption mechanisms during execution. In this paper we propose a framework to integrate deliberative planning, plan repair and execution control in a dynamic environment with stringent temporal constraints. It is based on lifted partial order temporal planning techniques which produce flexible plans and allow, under certain conditions discussed in the paper, plan repair interleaved with plan execution. This framework has been implemented using the IXTET planner and used to control a robotic platform.
---
paper_title: Practical Planning: Extending the Classical AI Planning Paradigm

paper_content:

1 Reasoning about Actions and Planning 2 Basic Assumptions and Limitations 3 SIPE and Its Representations 4 Hierarchical Planning as Differing Abstraction Levels 5 Constraints 6. The Truth Criterion 7 Deductive Causal Theories 8 Plan Critics 9 Resources: Reusable, Consumable, Temporal 10 Search 11 Replanning During Execution 12 Planning and Reactivity 13 Achieving Heuristic Adequacy 14 Comparison with Other Systems
---
paper_title: An investigation into reactive planning in complex domains

paper_content:

A model of purely reactive planning is proposed based on the concept of reactive action packages. A reactive action package, or RAP, can be thought of as an independent entity pursuing some goal in competition with many others at execution time. The RAP processing algorithm addresses the problems of execution monitoring and replanning in uncertain domains with a single, uniform representation and control structure. Use of the RAP model as a basis for adaptive strategic planning is also discussed.
---
paper_title: Improving Robot Plans During Their Execution

paper_content:

We describe how our planner, XFRM, carries out the process of anticipating and forestalling execution failures. XFRM is a planning system that is embedded in a simulated robot performing a varying set of complex tasks in a changing and partially unknown environment. XFRM revises plans controlling the robot while they are executed. Thus whenever the robot detects a contingency, XFRM projects the effects of the contingency on its plan and—if necessary—revises its plan in order to make it more robust. Using XFRM, the robot can perform its tasks almost as efficiently as it could using efficient default plans, but much more robustly. Revising default plans requires XFRM to reason about full-fledged robot plans and diagnose various kinds of plan failures that might be caused by imperfect sensing and effecting, incomplete and faulty world models, and exogenous events. To this end, XFRM reasons about the structure, function, and behavior of plans, and diagnoses projected plan failures by classifying them in a taxonomy of predefined failure models. Declarative commands for goals, perceptions, and beliefs make the structure of robot plans and the functions of subplans explicit and thereby provide XFRM with a (partial) model of its plan that is used to perform hierarchical model-based diagnosis.
---
paper_title: Adapting a Rapidly-Exploring Random Tree for Automated Planning

paper_content:

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

paper_content:

The authors describe an implemented integrated system allowing a mobile robot to plan its actions, taking into account temporal constraints, and to control their execution in real time. The general architecture has three levels, and the approach is related to hierarchical planning: the plan produced by the temporal planner is further refined at the control level, which in turn supervises its execution by a functional level. The framework of the French Mars Rover project VAP is used as an illustration of the various aspects discussed. >
---
paper_title: Towards autonomous robotic butlers: Lessons learned with the PR2

paper_content:

As autonomous personal robots come of age, we expect certain applications to be executed with a high degree of repeatability and robustness. In order to explore these applications and their challenges, we need tools and strategies that allow us to develop them rapidly. Serving drinks (i.e., locating, fetching, and delivering), is one such application with well-defined environments for operation, requirements for human interfacing, and metrics for successful completion. In this paper we present our experiences and results while building an autonomous robotic assistant using the PR21 platform and ROS2. The system integrates several new components that are built on top of the PR2's current capabilities. Perception components include dynamic obstacle identification, mechanisms for identifying the refrigerator, types of drinks, and human faces. Planning components include navigation, arm motion planning with goal and path constraints, and grasping modules. One of the main contributions of this paper is a new task-level executive system, SMACH, based on hierarchical concurrent state machines, which controls the overall behavior of the system. We provide in-depth discussions on the solutions that we found in accomplishing our goal, and the implementation strategies that let us achieve them.
---
paper_title: PLAN EXECUTION INTERCHANGE LANGUAGE (PLEXIL) FOR EXECUTABLE PLANS AND COMMAND SEQUENCES

paper_content:

Space mission operations require flexible, efficient and reliable plan execution. In typical operations command sequences (which are a simple subset of general executable plans) are generated on the ground, either manually or with assistance from automated planning, and sent to the spacecraft. For more advanced operations more expressive executable plans may be used; the plans might also be generated automatically on board the spacecraft. In all these cases, the executable plans are received by a software system that executes the plan. This software system, often called an executive, must ensure that the execution of the commands and response of the fault protection system conforms to pre-planned behaviour. This paper presents a language, called PLEXIL, that is designed specifically for flexible and reliable command execution. It is designed to be portable, lightweight, predictable, and verifiable, and at the same time it is more expressive than command sequencing languages currently used on space missions.
---
paper_title: A Petri-net coordination model for an intelligent mobile robot

paper_content:

The authors present a Petri-net model of the coordination level of an intelligent mobile robot system (IMRS). The purpose of this model is to specify the integration of the individual efforts on path planning, supervisory motion control, and vision systems, that are necessary for the autonomous operation of the mobile robot in a structured dynamic environment. This is achieved by analytically modeling the various units of the system as Petri-net transducers and explicitly representing the task precedence and information dependence among them. The model can also be used to simulate the task processing and to evaluate the efficiency of operations and the responsibility of decisions in the coordination level of the IMRS. Some simulation results on the task processing and learning are presented. >
---
paper_title: Platas—Integrating Planning and the Action Language Golog

paper_content:

Action programming languages like Golog allow to define complex behaviors for agents on the basis of action representations in terms of expressive (first-order) logical formalisms, making them suitable for realistic scenarios of agents with only partial world knowledge. Often these scenarios include sub-tasks that require sequential planning. While in principle it is possible to express and execute such planning sub-tasks directly in Golog, the system can performance-wise not compete with state-of-the-art planners. In this paper, we report on our efforts to integrate efficient planning and expressive action programming in the Platas project. The theoretical foundation is laid by a mapping between the planning language Pddl and the Situation Calculus, which is underlying Golog, together with a study of how these formalisms relate in terms of expressivity. The practical benefit is demonstrated by an evaluation of embedding a Pddl planner into Golog, showing a drastic increase in performance while retaining the full expressiveness of Golog.
---
paper_title: The Interactive Museum Tour-Guide Robot

paper_content:

This paper describes the software architecture of an autonomous tour-guideltutor robot. This robot was recently deployed in the "Deutsches Museum Bonn," were it guided hundreds of visitors through the museum during a six-day deployment period. The robot's control software integrates low-level probabilistic reasoning with high-level problem solving embedded in first order logic. A collection of software innovations, described in this paper, enabled the robot to navigate at high speeds through dense crowds, while reliably avoiding collisions with obstacles--some of which could not even be perceived. Also described in this paper is a user interface tailored towards non-expert users, which was essential for the robot's success in the museum. Based on these experiences, this paper argues that time is ripe for the development of AI-based commercial service robots that assist people in everyday life.
---
paper_title: GOLEX - Bridging the Gap between Logic (GOLOG) and a Real Robot

paper_content:

The control of mobile robots acting autonomously in the real world is one of the long-term goals of the field of artificial intelligence. So far the field lacks methods bridging the gap between the sophisticated symbolic techniques to represent and reason about action and more and more reliable low-level robot control and navigation systems. In this paper we present GOLEX, an execution and monitoring system for the logic-based action language GOLOG and the complex and distributed RHINO control software which operates on RWI B21 and B14 mobile robots. GOLEX provides the following features: it maps abstract primitive actions into low-level commands of the robot control system, thus allowing the user to concentrate on the application rather than the inner workings of the robot; it monitors the execution of the primitive GOLOG actions, making it possible to detect simple execution failures and timeouts; and it includes means to deal with sensing and user input and to continue the operation appropriately. We present two different real-world applications in which GOLEX successfully operated a mobile robot in dynamic and even unstructured environments. These results suggest that the time is ripe for using symbolic action languages for mobile robot applications.
---
paper_title: Logic-based robot control in highly dynamic domains

paper_content:

In this paper, we present the robot programming and planning language Readylog, a Golog dialect, which was developed to support the decision making of robots acting in dynamic real-time domains, such as robotic soccer. The formal framework of Readylog, which is based on the situation calculus, features imperative control structures such as loops and procedures, allows for decision-theoretic planning, and accounts for a continuously changing world. We developed high-level controllers in Readylog for our soccer robots in RoboCup's Middle-size league, but also for service robots and for autonomous agents in interactive computer games. For a successful deployment of Readylog on a real robot it is also important to account for the control problem as a whole, integrating the low-level control of the robot (such as localization, navigation, and object recognition) with the logic-based high-level control. In doing so, our approach can be seen as a step towards bridging the gap between the fields of robotics and knowledge representation.
---
paper_title: A Systematic Agent Framework for Situated Autonomous Systems

paper_content:

We present a formal framework of an autonomous agent as a collection of coordinated control loops, with a recurring sense, plan, act cycle. Our framework manages the information flow within the partitioned structure to ensure consistency in order to direct the flow of goals and observations in a timely manner. The resulting control structure improves scalability since many details of each controller can be encapsulated within a single control loop. This partitioned agent design promises a domain-independent, scalable and robust approach for control of real-world autonomous robots operating in dynamic environments. We validate our framework with experimental results from deployments in two different real-world domains.
---
paper_title: Executing Reactive, Model-based Programs through Graph-based Temporal Planning

paper_content:

In the future, webs of unmanned air and space vehicles will act together to robustly perform elaborate missions in uncertain environments. We coordinate these systems by introducing a reactive model-based programming language (RMPL) that combines within a single unified representation the flexibility of embedded programming and reactive execution languages, and the deliberative reasoning power of temporal planners. The KIRK planning system takes as input a problem expressed as a RMPL program, and compiles it into a temporal plan network (TPN), similar to those used by temporal planners, but extended for symbolic constraints and decisions. This intermediate representation clarifies the relation between temporal planning and causal-link planning, and permits a single task model to be used for planning and execution. Such a unified model has been described as a holy grail for autonomous agents by the designers of the Remote Agent[Muscettola et al., 1998b].
---
paper_title: Towards Deliberative Control in Marine Robotics

paper_content:

We describe a general purpose artificial-intelligence-based control architecture that incorporates in situ decision making for autonomous underwater vehicles (AUVs). The Teleo-reactive executive (T-REX) framework deliberates about future states, plans for actions, and executes generated activities while monitoring plans for anomalous conditions. Plans are no longer scripted a priori but synthesized onboard with high-level directives instead of low-level commands. Further, the architecture uses multiple control loops for a “divide-and-conquer” problem-solving strategy allowing for incremental computational model building, robust and focused failure recovery, ease of software development, and ability to use legacy or nonnative computational paradigms. Vehicle adaptation and sampling occurs in situ with additional modules which can be selectively used depending on the application in focus. Abstraction in problem solving allows different applications to be programmed relatively easily, with little to no changes to the core search engine, thereby making software engineering sustainable. The representational ability to deal with time and resources coupled with Machine Learning techniques for event detection allows balancing shorter term benefits with longer term needs, an important need as AUV hardware becomes more robust allowing persistent ocean sampling and observation. T-REX is in regular operational use at MBARI, providing scientists a new tool to sample and observe the dynamic coastal ocean.
---
paper_title: Flexible Execution of Plans with Choice

paper_content:

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

paper_content:

Dynamic execution is a flexible plan execution technique in which a plan executive schedules and executes tasks dynamically at runtime in response to disturbances in order to satisfy plan constraints. In this paper, we extend dynamic execution to temporally and spatially flexible plans which, 1) execute tasks conditionally based on runtime state, and 2) support error recovery for anticipated runtime constraint violations. To accomplish these goals, we broaden our focus from dynamic execution of flexible plans to dynamic execution of flexible reactive programs. ::: ::: First, we introduce the Reactive Model-based Programming Language (RMPL) which, in addition to modeling temporal and spatial flexibility, includes three reactive programming language constructs: conditional execution, iteration, and exception handling. Then, we develop a probabilistic particle-sampling based dynamic execution algorithm which reasons efficiently over future program states to schedule tasks dynamically at runtime in order to satisfy program constraints. In addition, the algorithm monitors its own progress and notifies the executive if at any time the likelihood of successful program execution drops below a specified probability bound, δ.
---
paper_title: Concurrent plan recognition and execution for human-robot teams

paper_content:

There is a strong demand for robots to work in environments, such as aircraft manufacturing, where they share tasks with humans and must quickly adapt to each other's needs. To do so, a robot must both infer the intent of humans, and must adapt accordingly. The literature to date has made great progress on these two tasks - recognition and adaptation - but largely as separate research activities. In this paper, we present a unified approach to these two problems, in which recognition and adaptation occur concurrently and holistically. Key to our approach is a task representation that uses choice to represent alternative plans for both the human and robot, allowing a single set of algorithms to simultaneously achieve recognition and adaptation. To achieve such fluidity, a labeled propagation mechanism is used where decisions made by the human and robot during execution are propagated to relevant future open choices, as determined by causal link analysis, narrowing the possible options that the human would reasonably take (hence achieving intent recognition) as well as the possible actions the robot could consistently take (adaptation). This paper introduces Pike, an executive for human-robot teamwork that quickly adapts and infers intent based on the preconditions of actions in the plan, temporal constraints, unanticipated disturbances, and choices made previously (by either robot or human). We evaluate Pike's performance and demonstrate it on a household task in a human-robot team testbed.
---
paper_title: Chance-constrained consistency for Probabilistic Temporal Plan Networks

paper_content:

Unmanned deep-sea and planetary vehicles operate in highly uncertain environments. Autonomous agents often are not adopted in these domains due to the risk of mission failure, and loss of vehicles. Prior work on contingent plan execution addresses this issue by placing bounds on uncertain variables and by providing consistency guarantees for a 'worst-case' analysis, which tends to be too conservative for real-world applications. In this work, we unify features from trajectory optimization through risk-sensitive execution methods and high-level, contingent plan execution in order to extend existing guarantees of consistency for conditional plans to a chance-constrained setting. The result is a set of efficient algorithms for computing plan execution policies with explicit bounds on the risk of failure. To accomplish this, we introduce Probabilistic Temporal Plan Network (pTPN), which improve previous formulations, by incorporating probabilistic uncertainty and chance-constraints into the plan representation. We then introduce a novel method to the chance-constrained strong consistency problem, by leveraging a conflict-directed approach that searches for an execution policy that maximizes reward while meeting the risk constraint. Experimental results indicate that our approach for computing strongly consistent policies has an average scalability gain of about one order of magnitude, when compared to current methods based on chronological search.
---
paper_title: Policy learning for autonomous feature tracking

paper_content:

We consider the problem of tracing the structure of oceanological features using autonomous underwater vehicles (AUVs). Solving this problem requires the construction of a control strategy that will determine the actions for the AUV based on the current state, as measured by on-board sensors and the historic trajectory (including sensed data) of the AUV. We approach this task by applying plan-based policy-learning, in which a large set of sampled problems are solved using planning and then, from the resulting plans a decision-tree is learned, using an established machine-learning algorithm, which forms the resulting policy. We evaluate our approach in simulation and report on sea trials of a prototype of a learned policy. We indicate some of the lessons learned from this deployed system and further evaluate an extended policy in simulation.
---
paper_title: A Reactive Model-based Programming Language for Robotic Space Explorers

paper_content:

Model-based autonomous agents have emerged recently as vital technologies in the development of highly autonomous reactive systems, particularly in the aerospace domain. These agents utilize many automated reasoning capabilities, but are complicated to use because of the variety of languages employed for each capability. To address this problem, we introduce model-based programming, a novel approach to designing embedded software systems. In particular, we introduce the Reactive Model-based Programming Language (RMPL), which provides a framework for constraint-based modeling, as well as a suite of reactive programming constructs. To convey the expressiveness of RMPL, we show how it captures the main features of synchronous programming languages and advanced robotic execution languages. This paper focuses on using the rich behavior modeling of RMPL to provide sequencing and robotic execution capabilities for spacecraft.
---
paper_title: Model-based executive control through reactive planning for autonomous rovers

paper_content:

This paper reports on the design and implementation of a real-time executive for a mobile rover that uses a model-based, declarative approach. The control system is based on the intelligent distributed execution architecture (IDEA), an approach to planning and execution that provides a unified representational and computational framework for an autonomous agent. The basic hypothesis of IDEA is that a large control system can be structured as a collection of interacting agents, each with the same fundamental structure. We show that planning and real-time response are compatible if the executive minimizes the size of the planning problem. We detail the implementation of this approach on an 'exploration rover (Gromit, an RWI ATRV Junior at NASA Ames) presenting different IDEA controllers of the same domain and comparing them with more classical approaches. We demonstrate that the approach is scalable to complex coordination of functional modules needed for autonomous navigation and exploration.
---
paper_title: Validation and verification issues in a timeline-based planning system

paper_content:

One of the key points to take into account to foster effective introduction of AI planning and scheduling systems in real world is to develop end user trust in the related technologies. Automated planning and scheduling systems often brings solutions to the users which are neither “obvious” nor immediately acceptable for them. This is due to the ability of these tools to take into account quite an amount of temporal and causal constraints and to employ resolution processes often designed to optimize the solution with respect to non trivial evaluation functions. To increase technology trust, the study of tools for verifying and validating plans and schedules produced by AI systems might be instrumental. In general, validation and verification techniques represent a needed complementary technology in developing domain independent architectures for automated problem solving. This paper presents a preliminary report of the issues concerned with the use of two software tools for formal verification of finite state systems to the validation of the solutions produced by MrSPOCK, a recent effort for building a timeline based planning tool in an ESA
---
paper_title: A task-level robot programming language and its reactive execution

paper_content:

A robotic application is defined by a set of scheduled actions, each action being modeled as a robot-task with functional and behavioral aspects. The authors propose a programming approach located at an intermediary level between objective and object levels, called the task-level. The basic feature consists of using a synchronous language (Esterel) as the target language of an application programming language that is able to express in a natural way the logical and temporal dependencies of the actions. The synchrony assumption induces the need for the design of a synchronous/asynchronous interface to be associated with the computer system. This aspect is considered. The proposed language is presented, and an example of a robotic application is given. >
---
paper_title: Interleaving Temporal Planning and Execution in Robotics Domains

paper_content:

Many autonomous systems such as mobile robots, UAVs or spacecraft, have limited resource capacities and move in dynamic environments. Performing on-board mission planning and execution in such a context requires deliberative capabilities to generate plans achieving mission goals while respecting deadlines and resource constraints, as well as run-time plan adaption mechanisms during execution. In this paper we propose a framework to integrate deliberative planning, plan repair and execution control in a dynamic environment with stringent temporal constraints. It is based on lifted partial order temporal planning techniques which produce flexible plans and allow, under certain conditions discussed in the paper, plan repair interleaved with plan execution. This framework has been implemented using the IXTET planner and used to control a robotic platform.
---
paper_title: Increased Mars Rover Autonomy using AI Planning, Scheduling and Execution

paper_content:

This paper presents technology for performing autonomous commanding of a planetary rover. Through the use of AI planning, scheduling and execution techniques, the OASIS autonomous science system provides capabilities for the automated generation of a rover activity plan based on science priorities, the handling of opportunistic science, including new science targets identified by onboard data analysis software, other dynamic decision-making such as modifying the rover activity plan in response to problems or other state and resource changes. We first describe some of the particular challenges this work has begun to address and then describe our system approach. Finally, we report on our experience testing this software with a Mars rover prototype.
---
paper_title: Planning Robust Temporal Plans A Comparison Between CBTP and TGA Approaches

paper_content:

Planning for real world applications, with explicit temporal representation and a robust execution is a very challenging problem. To tackle it, the planning community has proposed a number of original and successful approaches. However, there are other paradigms "outside" the Automated Planning field which may prove to be successful with respect to this objective. This paper presents a comparison of two "planning" approaches dealing with temporal and/or discrete uncertainties and with a strong emphasis on robust execution. The first approach is based on chronicles and constraint satisfaction techniques; it relies on a causal link partial order temporal planner, in our case IXTET. The second approach is based on timed game automata and reachability analysis, and uses the UPPAAL-TIGA system. The comparison is both qualitative (the kind of problems modeled and the properties of plans obtained) and quantitative (experimental results on a real example). To make this comparison possible, we propose a general scheme to translate a subset of IXTET planning problems into UPPAAL-TIGA game-reachability problems. A direct consequence of this automated process would be the possibility to apply validation and verification techniques available in the timed automata community.
---
paper_title: Incremental Dynamic Controllability in Cubic Worst-Case Time

paper_content:

It is generally hard to predict the exact duration of an action. Uncertainty in durations is often modeled in temporal planning by the use of upper bounds on durations, with the assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false: If we finish cooking too early, the dinner will be cold before everyone is ready to eat. Simple Temporal Problems with Uncertainty (STPUs) allow us to model such situations. An STPU-based planner must verify that the plans it generates are executable, captured by the property of dynamic controllability. The Efficient IDC (EIDC) algorithm can do this incrementally during planning, with an amortized complexity per step of O(n3) but a worst-case complexity per step of O(n4). In this paper we show that the worst-case run-time of EIDC does occur, leading to repeated reprocessing of nodes in the STPU while verifying the dynamic controllability property. We present a new version of the algorithm, EIDC2, which through optimal ordering of nodes avoids the need for reprocessing. This gives EIDC2 a strictly lower worst-case run-time, making it the fastest known algorithm for incrementally verifying dynamic controllability of STPUs.
---
paper_title: Representation and control in IxTeT, a temporal planner

paper_content:

This paper presents a temporal planner, called IxTeT. It focuses on the representation and control issues, arguing for a compromise between the expressiveness and the efficiency of the search. The representation relies on a point-based reified logic, associated to multi-valued domain attributes. Hierarchical planning operators offer an expressive description, with parallelism, durations, effects and conditions at various moments of the action. Time in the input scenario enables to take into account predicted forthcoming events and to plan in a dynamic world. A compilation procedure checks the consistency of the operators specified by the user. The control relies on the use of causal-links, Ae, algorithm, and an extended least-commitment strategy. It uses two important procedures, called "feasibility" and "satisfiability", dealing respectively with goal decomposition and conflict resolution:
---
paper_title: Temporal dynamic controllability revisited

paper_content:

An important issue for temporal planners is the ability to handle temporal uncertainty. We revisit the question of how to determine whether a given set of temporal requirements are feasible in the light of uncertain durations of some processes. In particular, we consider how best to determine whether a network is Dynamically Controllable, i.e., whether a dynamic strategy exisls for executing the network that is guaranteed to satisfy the requirements. Previous work has shown the existence of a pseudo-polynomial algorithm for testing Dynamic Controllability. Here, we simplify the previous framework, and present a strongly polynomial algorithm with a termination criterion based on the structure of the network.
---
paper_title: A Unified Approach to Model-Based Planning and Execution

paper_content:

Writing autonomous software is complex, requiring the coordination of functionally and technologically diverse software modules. System and mission engineers must rely on specialists familiar with the different software modules to translate requirements into application software. Also, each module often encodes the same requirement in different forms. The results are high costs and reduced reliability due to the difficulty of tracking discrepancies in these encodings. In this paper we describe a unified approach to planning and execution that we believe provides a unified representational and computational framework for an autonomous agent. We identify the four main components whose interplay provides the basis for the agent's autonomous behavior: the domain model, the plan database, the plan running module, and the planner modules. This representational and problem solving approach can be applied at all levels of the architecture of a complex agent, such as Remote Agent. In the rest of the paper we briefly describe the Remote Agent architecture. The new agent architecture proposed here aims at achieving the full Remote Agent functionality. We then give the fundamental ideas behind the new agent architecture and point out some implication of the structure of the architecture, mainly in the area of reactivity and interaction between reactive and deliberative decision making. We conclude with related work and current status.
---
paper_title: Dynamic Control Of Plans With Temporal Uncertainty

paper_content:

Certain planning systems that deal with quantitative time constraints have used an underlying Simple Temporal Problem solver to ensure temporal consistency of plans. However, many applications involve processes of uncertain duration whose timing cannot be controlled by the execution agent. These cases require more complex notions of temporal feasibility. In previous work, various "controllability" properties such as Weak, Strong, and Dynamic Controllability have been defined. The most interesting and useful Controllability property, the Dynamic one, has ironically proved to be the most difficult to analyze. In this paper, we resolve the complexity issue for Dynamic Controllability. Unexpectedly, the problem turns out to be tractable. We also show how to efficiently execute networks whose status has been verified.
---
paper_title: Towards robotic assistants in nursing homes: Challenges and results

paper_content:

Abstract This paper describes a mobile robotic assistant, developed to assist elderly individuals with mild cognitive and physical impairments, as well as support nurses in their daily activities. We present three software modules relevant to ensure successful human–robot interaction: an automated reminder system; a people tracking and detection system; and finally a high-level robot controller that performs planning under uncertainty by incorporating knowledge from low-level modules, and selecting appropriate courses of actions. During the course of experiments conducted in an assisted living facility, the robot successfully demonstrated that it could autonomously provide reminders and guidance for elderly residents.
---
paper_title: Learning how to combine sensory-motor functions into a robust behavior

paper_content:

This article describes a system, called Robel, for defining a robot controller that learns from experience very robust ways of performing a high-level task such as ''navigate to''. The designer specifies a collection of skills, represented as hierarchical tasks networks, whose primitives are sensory-motor functions. The skills provide different ways of combining these sensory-motor functions to achieve the desired task. The specified skills are assumed to be complementary and to cover different situations. The relationship between control states, defined through a set of task-dependent features, and the appropriate skills for pursuing the task is learned as a finite observable Markov decision process (MDP). This MDP provides a general policy for the task; it is independent of the environment and characterizes the abilities of the robot for the task.
---
paper_title: Learning to act using real-time dynamic programming

paper_content:

Learning methods based on dynamic programming (DP) are receiving increasing attention in artificial intelligence. Researchers have argued that DP provides the appropriate basis for compiling planning results into reactive strategies for real-time control, as well as for learning such strategies when the system being controlled is incompletely known. We introduce an algorithm based on DF, which we call Real-Time DP (RTDP), by which an embedded system can improve its performance with experience. RTDP generalizes Korf's Learning-Real-Time-A* algorithm to problems involving uncertainty. We invoke results from the theory of asynchronous DP to prove that RTDP achieves optimal behavior in several different classes of problems. We also use the theory of asynchronous DF to illuminate aspects of other DP-based reinforcement learning methods such as Watkins' Q-Learning algorithm. A secondary aim of this article is to provide a bridge between Al research on real-time planning and learning and relevant concepts and algorithms from control theory.
---
paper_title: A generic framework for anytime execution-driven planning in robotics

paper_content:

Robotic missions require to implement various functionalities in order to link reactive functions at actuators and sensors level to deliberative functions like vision, supervision and planning at decisional level. All these functionalities must be versatile and generic enough to interact differently according to the missions while minimizing recoding effort. Moreover, deliberative functions like automated planning consume lots of memory and CPU time and usually complete in time incompatible with robotic missions' durations. Thus, we present a new generic and anytime planning concept for modular robotic architectures, which manages multiple planning requests at a time, solved in background, while allowing for reactive execution of planned actions at the same time. Different planners based on various formalisms and data structures can be plugged to the planning component without changing its behavior nor its code, facilitating reusability and validation of the component. We highlight the versatility of our concept on different use cases; then we demonstrate the efficiency of our approach in terms of mission duration and success, compared with traditional plan-then-execute approaches; we finally present a search and rescue mission by an autonomous rotorcraft solved with our paradigm, that cannot be tackled by traditional approaches.
---
paper_title: Learning Depth-First Search: A Unified Approach to Heuristic Search in Deterministic and Non-Deterministic Settings, and its application to MDPs

paper_content:

Dynamic Programming provides a convenient and unified framework for studying many state models used in AI but no algorithms for handling large spaces. Heuristic-search methods, on the other hand, can handle large spaces but lack a common foundation. In this work, we combine the benefits of a general dynamic programming formulation with the power of heuristic-search techniques for developing an algorithmic framework, that we call Learning Depth-First Search, that aims to be both general and effective. LDFS is a simple piece of code that performs iterated depth-first searches enhanced with learning. For deterministic actions and monotone value functions, LDFS reduces to IDA* with transposition tables, while for Game Trees, to the state-of-the-art iterated Alpha-Beta search algorithm with Null Windows known as MTD. For other models, like AND/OR graphs and MDPs, LDFS yields new, simple, and competitive algorithms. We show this here for MDPs.
---
paper_title: A Closer Look at MOMDPs

paper_content:

The difficulties encountered in sequential decision-making problems under uncertainty are often linked to the large size of the state space. Exploiting the structure of the problem, for example by employing a factored representation, is usually an efficient approach but, in the case of partially observable Markov decision processes, the fact that some state variables may be visible has not been sufficiently appreciated. In this article, we present a complementary analysis and discussion about MOMDPs, a formalism that exploits the fact that the state space may be factored in one visible part and one hidden part. Starting from a POMDP description, we dig into the structure of the belief update, value function, and the consequences in value iteration, specifically how classical algorithms can be adapted to this factorization, and demonstrate the resulting benefits through an empirical evaluation.
---
paper_title: MONITORED EXECUTION OF ROBOT PLANS PRODUCED BY STRIPS

paper_content:

Abstract : We describe PLANEXl, a plan executor for the Stanford Research Institute robot system. The problem-solving program STRIPS creates a plan consisting of a sequence of actions, and the PLANEXI program carries out the plan by executing the actions. PLANEXI is designed so that it executes only that portion of the plan necessary for completing the task, reexecutes any portion of the plan that has failed to achieve the desired results, and initiates replanning in situations where the plan can no longer be effective in completing the task. The scenario for an example plan execution is given.
---
paper_title: Execution monitoring in robotics: A survey

paper_content:

Research on execution monitoring in its own is still not very common within the field of robotics and autonomous systems. It is more common that researchers interested in control architectures or e ...
---
paper_title: Semantic Knowledge-Based Execution Monitoring for Mobile Robots

paper_content:

We describe a novel intelligent execution monitoring approach for mobile robots acting in indoor environments such as offices and houses. Traditionally, monitoring execution in mobile robotics amounted to looking for discrepancies between the model-based predicted state of executing an action and the real world state as computed from sensing data. We propose to employ semantic knowledge as a source of information to monitor execution. The key idea is to compute implicit expectations, from semantic domain information, that can be observed at run time by the robot to make sure actions are executed correctly. We present the semantic knowledge representation formalism, and how semantic knowledge is used in monitoring. We also describe experiments run in an indoor environment using a real mobile robot.
---
paper_title: Remote Agent: To Boldly Go Where No AI System Has Gone Before

paper_content:

Abstract Renewed motives for space exploration have inspired NASA to work toward the goal of establishing a virtual presence in space, through heterogeneous fleets of robotic explorers. Information technology, and Artificial Intelligence in particular, will play a central role in this endeavor by endowing these explorers with a form of computational intelligence that we call remote agents . In this paper we describe the Remote Agent, a specific autonomous agent architecture based on the principles of model-based programming, on-board deduction and search, and goal-directed closed-loop commanding, that takes a significant step toward enabling this future. This architecture addresses the unique characteristics of the spacecraft domain that require highly reliable autonomous operations over long periods of time with tight deadlines, resource constraints, and concurrent activity among tightly coupled subsystems. The Remote Agent integrates constraintbased temporal planning and scheduling, robust multi-threaded execution, and model-based mode identification and reconfiguration. The demonstration of the integrated system as an on-board controller for Deep Space One, NASA's first New Millennium mission, is scheduled for a period of a week in mid 1999. The development of the Remote Agent also provided the opportunity to reassess some of AI's conventional wisdom about the challenges of implementing embedded systems, tractable reasoning, and knowledge representation. We discuss these issues, and our often contrary experiences, throughout the paper.
---
paper_title: MONITORED EXECUTION OF ROBOT PLANS PRODUCED BY STRIPS

paper_content:

Abstract : We describe PLANEXl, a plan executor for the Stanford Research Institute robot system. The problem-solving program STRIPS creates a plan consisting of a sequence of actions, and the PLANEXI program carries out the plan by executing the actions. PLANEXI is designed so that it executes only that portion of the plan necessary for completing the task, reexecutes any portion of the plan that has failed to achieve the desired results, and initiates replanning in situations where the plan can no longer be effective in completing the task. The scenario for an example plan execution is given.
---
paper_title: Model-Free Execution Monitoring in Behavior-Based Mobile Robotics

paper_content:

In this paper we present a model-free execution monitor for behavior-based mobile robots. By model-free we mean that the monitoring is based only on the actual execution, without involving any pred ...
---
paper_title: Plan execution in dynamic environments

paper_content:

This paper deals with plan execution on agents/robots in highly dynamic environments. Besides a formal semantics of plan execution and a representation of plans as programs, we introduce the concept of plan invariants. Plan invariants are similar to loop invariants in imperative programs in that they have to be true during the whole plan execution cycle. Once a plan invariant fails the plan execution is stopped and other plans that are more appropriate in the current context are considered for execution instead. The use of plan invariants allows for an early detection of problems. Plan assumptions that are required for a plan to succeed are explicitly represented by plan invariants.
---
paper_title: Intelligent Execution Monitoring in Dynamic Environments

paper_content:

We present a robot control system for known structured environments that integrates robust reactive control with reasoning-based execution monitoring. It provides a robot with a powerful method for dealing with situations that were caused by the interaction with humans or that are due to unexpected changes in the operating environment. On the reactive level, the robot is controlled using a hierarchy of low-level behaviours. On the high level, a logical representation of the world enables the robot to plan action sequences and to reason about the state of the world. If the execution of an action does not have the expected effect, high-level reasoning allows the robot to infer possible explanations and, if necessary, to recover from the failure situation. For the robot to act optimally, the discrepancies between the internal world model and the real world have to be detected and corrected. The proposed system obtains new information about the world by executing sensing actions (active perception) and by sensory interpretation during the robot's operation. It also takes into account temporal information about changes in the environment. All updates of the world model are performed in a way that the changes are consistent with an underlying action theory. Having implemented the proposed system on a common mobile robot platform, we demonstrate the value of intelligent execution monitoring by means of two realistic office delivery scenarios.
---
paper_title: A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems

paper_content:

Research with autonomous unmanned aircraft systems is reaching a new degree of sophistication where targeted missions require complex types of deliberative capability integrated in a practical manner in such systems. Due to these pragmatic constraints, integration is just as important as theoretical and applied work in developing the actual deliberative functionalities. In this article, we present a temporal logic-based task planning and execution monitoring framework and its integration into a fully deployed rotor-based unmanned aircraft system developed in our laboratory. We use a very challenging emergency services application involving body identification and supply delivery as a vehicle for showing the potential use of such a framework in real-world applications. TALplanner, a temporal logic-based task planner, is used to generate mission plans. Building further on the use of TAL (Temporal Action Logic), we show how knowledge gathered from the appropriate sensors during plan execution can be used to create state structures, incrementally building a partial logical model representing the actual development of the system and its environment over time. We then show how formulas in the same logic can be used to specify the desired behavior of the system and its environment and how violations of such formulas can be detected in a timely manner in an execution monitor subsystem. The pervasive use of logic throughout the higher level deliberative layers of the system architecture provides a solid shared declarative semantics that facilitates the transfer of knowledge between different modules.
---
paper_title: A Reactive Model-based Programming Language for Robotic Space Explorers

paper_content:

Model-based autonomous agents have emerged recently as vital technologies in the development of highly autonomous reactive systems, particularly in the aerospace domain. These agents utilize many automated reasoning capabilities, but are complicated to use because of the variety of languages employed for each capability. To address this problem, we introduce model-based programming, a novel approach to designing embedded software systems. In particular, we introduce the Reactive Model-based Programming Language (RMPL), which provides a framework for constraint-based modeling, as well as a suite of reactive programming constructs. To convey the expressiveness of RMPL, we show how it captures the main features of synchronous programming languages and advanced robotic execution languages. This paper focuses on using the rich behavior modeling of RMPL to provide sequencing and robotic execution capabilities for spacecraft.
---
paper_title: Reasoning about Robot Actions: A Model Checking Approach

paper_content:

Mobile robot control remains a difficult challenge in changing and unpredictable environments. Reacting to unanticipated events, interacting and coordinating with other agents, and acquiring information about the world remain difficult problems. These actions should be the direct products of the robot's capabilities to perceive, act, and process information intelligently, taking into account its state, that of the environment, and the goals to be achieved. This paper discusses the use of model-checking to reason about robot actions in this context. The approach proposed is to study behaviors that allow abstract, but informative models, so that a computer program can reason with them efficiently. Model-checking can then be used as a means for verifying and planning robot actions with respect to such behaviors.
---
paper_title: Remote Agent: To Boldly Go Where No AI System Has Gone Before

paper_content:

Abstract Renewed motives for space exploration have inspired NASA to work toward the goal of establishing a virtual presence in space, through heterogeneous fleets of robotic explorers. Information technology, and Artificial Intelligence in particular, will play a central role in this endeavor by endowing these explorers with a form of computational intelligence that we call remote agents . In this paper we describe the Remote Agent, a specific autonomous agent architecture based on the principles of model-based programming, on-board deduction and search, and goal-directed closed-loop commanding, that takes a significant step toward enabling this future. This architecture addresses the unique characteristics of the spacecraft domain that require highly reliable autonomous operations over long periods of time with tight deadlines, resource constraints, and concurrent activity among tightly coupled subsystems. The Remote Agent integrates constraintbased temporal planning and scheduling, robust multi-threaded execution, and model-based mode identification and reconfiguration. The demonstration of the integrated system as an on-board controller for Deep Space One, NASA's first New Millennium mission, is scheduled for a period of a week in mid 1999. The development of the Remote Agent also provided the opportunity to reassess some of AI's conventional wisdom about the challenges of implementing embedded systems, tractable reasoning, and knowledge representation. We discuss these issues, and our often contrary experiences, throughout the paper.
---
paper_title: Semantic Knowledge-Based Execution Monitoring for Mobile Robots

paper_content:

We describe a novel intelligent execution monitoring approach for mobile robots acting in indoor environments such as offices and houses. Traditionally, monitoring execution in mobile robotics amounted to looking for discrepancies between the model-based predicted state of executing an action and the real world state as computed from sensing data. We propose to employ semantic knowledge as a source of information to monitor execution. The key idea is to compute implicit expectations, from semantic domain information, that can be observed at run time by the robot to make sure actions are executed correctly. We present the semantic knowledge representation formalism, and how semantic knowledge is used in monitoring. We also describe experiments run in an indoor environment using a real mobile robot.
---
paper_title: Model-Free Execution Monitoring in Behavior-Based Mobile Robotics

paper_content:

In this paper we present a model-free execution monitor for behavior-based mobile robots. By model-free we mean that the monitoring is based only on the actual execution, without involving any pred ...
---
paper_title: The Saphira Architecture: A Design for Autonomy

paper_content:

Mobile robots, if they are to perform useful tasks and become accepted in open environments, must be fully autonomous. Autonomy has many different aspects ; here the focus is on three central ones: the ability to attend to another agent, to take advice about the environment, and to carry out assigned tasks. All three involve complex sensing and planning operations on the part of the robot, including the use of visual tracking of humans, coordination of motor controls, and planning. It is shown how these capabilities are integrated in the Saphira architecture, using the concepts of coordination of behaviour, coherence of modelling, and communication with other agents.
---
paper_title: Plan execution in dynamic environments

paper_content:

This paper deals with plan execution on agents/robots in highly dynamic environments. Besides a formal semantics of plan execution and a representation of plans as programs, we introduce the concept of plan invariants. Plan invariants are similar to loop invariants in imperative programs in that they have to be true during the whole plan execution cycle. Once a plan invariant fails the plan execution is stopped and other plans that are more appropriate in the current context are considered for execution instead. The use of plan invariants allows for an early detection of problems. Plan assumptions that are required for a plan to succeed are explicitly represented by plan invariants.
---
paper_title: Concise finite-domain representations for PDDL planning tasks

paper_content:

We introduce an efficient method for translating planning tasks specified in the standard PDDL formalism into a concise grounded representation that uses finite-domain state variables instead of the straight-forward propositional encoding. Translation is performed in four stages. Firstly, we transform the input task into an equivalent normal form expressed in a restricted fragment of PDDL. Secondly, we synthesize invariants of the planning task that identify groups of mutually exclusive propositions which can be represented by a single finite-domain variable. Thirdly, we perform an efficient relaxed reachability analysis using logic programming techniques to obtain a grounded representation of the input. Finally, we combine the results of the third and fourth stage to generate the final grounded finite-domain representation. The presented approach has originally been implemented as part of the Fast Downward planning system for the 4th International Planning Competition (IPC4). Since then, it has been used in a number of other contexts with considerable success, and the use of concise finite-domain representations has become a common feature of state-of-the-art planners.
---
paper_title: An Iterative Algorithm for Synthesizing Invariants

paper_content:

We present a general algorithm for synthesizing state invari- ants that speed up automated planners and have other appli- cations in reasoning about change. Invariants are facts that hold in all states that are reachable from an initial state by the application of a number of operators. In contrast to ear- lier work, we recognize the fact that establishing an invari- ant may require considering other invariants, and this in turn seems to require viewing synthesis of invariants as fixpoint computation. Also, the algorithm is not inherently restricted to invariants of particular syntactic forms. In this paper we introduce a new algorithm for computing invariants. The algorithm is iterative like mutex computa- tion in Graphplan (Blum & Furst 1997) and the algorithm by Rintanen (1998) (both of which use a ground representa- tion of operators), operates on a schematic representation of operators, and generalizes earlier techniques. The algorithm is motivated by an inductive definition of invariants as for- mulae that are true in the initial state and are preserved by the application of every operator. Less general (and in re- stricted cases more efficient) algorithms can be obtained by specializing the general algorithm. For schemata that represent 2-literal ground invariants we show that the algorithm is efficient. In this case - like with universally quantified invariants in general - the algorithm is strictly stronger than earlier algorithms combined. In- variants with more than two literals are often useful, but the conditions for inferring non-disjunctive facts (literals) from -literal invariants for high are very strict because atomic facts have to be inferred first, so short invariants seem to be the most important ones. Extensions like existential quantification and types can be handled within the algorithm by supplying new subprocedures to the main procedure. No changes in the main procedure are needed.
---
paper_title: Finding Mutual Exclusion Invariants in Temporal Planning Domains

paper_content:

Abstract We present a technique for automatically extractingtemporal mutual exclusion invariants from PDDL2.2planning instances. We ﬁrst identify a set of invariantcandidates by inspecting the domain and then checkthese candidates against properties that assure invari-ance. If these properties are violated, we show that itis sometimes possible to reﬁne a candidate by addingadditional propositions and turn it into a real invariant.Our technique builds on other approaches to invariantsynthesis presented in the literature, but departs fromtheir limited focus on instantaneous discrete actions byaddressing temporal and numeric domains. To deal withtime, we formulate invariance conditions that accountfor both the entire structure of the operators (includingthe conditions, rather than just the effects) and the possi-ble interactions between operators. As a result, we con-struct a technique that is not only capable of identifyinginvariants for temporal domains, but is also able to ﬁnd abroader set of invariants for non-temporal domains thanthe previous techniques.
---
paper_title: Intelligent Execution Monitoring in Dynamic Environments

paper_content:

We present a robot control system for known structured environments that integrates robust reactive control with reasoning-based execution monitoring. It provides a robot with a powerful method for dealing with situations that were caused by the interaction with humans or that are due to unexpected changes in the operating environment. On the reactive level, the robot is controlled using a hierarchy of low-level behaviours. On the high level, a logical representation of the world enables the robot to plan action sequences and to reason about the state of the world. If the execution of an action does not have the expected effect, high-level reasoning allows the robot to infer possible explanations and, if necessary, to recover from the failure situation. For the robot to act optimally, the discrepancies between the internal world model and the real world have to be detected and corrected. The proposed system obtains new information about the world by executing sensing actions (active perception) and by sensory interpretation during the robot's operation. It also takes into account temporal information about changes in the environment. All updates of the world model are performed in a way that the changes are consistent with an underlying action theory. Having implemented the proposed system on a common mobile robot platform, we demonstrate the value of intelligent execution monitoring by means of two realistic office delivery scenarios.
---
paper_title: Reasoning about Robot Actions: A Model Checking Approach

paper_content:

Mobile robot control remains a difficult challenge in changing and unpredictable environments. Reacting to unanticipated events, interacting and coordinating with other agents, and acquiring information about the world remain difficult problems. These actions should be the direct products of the robot's capabilities to perceive, act, and process information intelligently, taking into account its state, that of the environment, and the goals to be achieved. This paper discusses the use of model-checking to reason about robot actions in this context. The approach proposed is to study behaviors that allow abstract, but informative models, so that a computer program can reason with them efficiently. Model-checking can then be used as a means for verifying and planning robot actions with respect to such behaviors.
---
paper_title: A distributed architecture for autonomous unmanned aerial vehicle experimentation

paper_content:

The emerging area of intelligent unmanned aerial vehicle (UAV) research has shown rapid development in recent years and offers a great number of research challenges for distributed autonomous robotics systems. In this article, a prototype distributed architecture for autonomous unmanned aerial vehicle experimentation is presented which supports the development of intelligent capabilities and their integration in a robust, scalable, plug-and-play hardware/software architecture. The architecture itself uses CORBA to support its infrastructure and it is based on a reactive concentric software control philosophy. A research prototype UAV system has been built, is operational and is being tested in actual missions over urban environments.
---
paper_title: TALplanner: A temporal logic based forward chaining planner

paper_content:

We present TALplanner, a forward-chaining planner based on the use of domain-dependent search control knowledge represented as formulas in the Temporal Action Logic (TAL). TAL is a narrative based linear metric time logic used for reasoning about action and change in incompletely specified dynamic environments. TAL is used as the formal semantic basis for TALplanner, where a TAL goal narrative with control formulas is input to TALplanner which then generates a TAL narrative that entails the goal and control formulas. The sequential version of TALplanner is presented. The expressivity of plan operators is then extended to deal with an interesting class of resource types. An algorithm for generating concurrent plans, where operators have varying durations and internal state, is also presented. All versions of TALplanner have been implemented. The potential of these techniques is demonstrated by applying TALplanner to a number of standard planning benchmarks in the literature.
---
paper_title: A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems

paper_content:

Research with autonomous unmanned aircraft systems is reaching a new degree of sophistication where targeted missions require complex types of deliberative capability integrated in a practical manner in such systems. Due to these pragmatic constraints, integration is just as important as theoretical and applied work in developing the actual deliberative functionalities. In this article, we present a temporal logic-based task planning and execution monitoring framework and its integration into a fully deployed rotor-based unmanned aircraft system developed in our laboratory. We use a very challenging emergency services application involving body identification and supply delivery as a vehicle for showing the potential use of such a framework in real-world applications. TALplanner, a temporal logic-based task planner, is used to generate mission plans. Building further on the use of TAL (Temporal Action Logic), we show how knowledge gathered from the appropriate sensors during plan execution can be used to create state structures, incrementally building a partial logical model representing the actual development of the system and its environment over time. We then show how formulas in the same logic can be used to specify the desired behavior of the system and its environment and how violations of such formulas can be detected in a timely manner in an execution monitor subsystem. The pervasive use of logic throughout the higher level deliberative layers of the system architecture provides a solid shared declarative semantics that facilitates the transfer of knowledge between different modules.
---
paper_title: Bridging the Sense-Reasoning Gap: DyKnow -- Stream-Based Middleware for Knowledge Processing

paper_content:

Engineering autonomous agents that display rational and goal-directed behavior in dynamic physical environments requires a steady flow of information from sensors to high-level reasoning components. However, while sensors tend to generate noisy and incomplete quantitative data, reasoning often requires crisp symbolic knowledge. The gap between sensing and reasoning is quite wide, and cannot in general be bridged in a single step. Instead, this task requires a more general approach to integrating and organizing multiple forms of information and knowledge processing on different levels of abstraction in a structured and principled manner. We propose knowledge processing middleware as a systematic approach to organizing such processing. Desirable properties are presented and motivated. We argue that a declarative stream-based system is appropriate for the required functionality and present DyKnow, a concrete implemented instantiation of stream-based knowledge processing middleware with a formal semantics. Several types of knowledge processes are defined and motivated in the context of a UAV traffic monitoring application. In the implemented application, DyKnow is used to incrementally bridge the sense-reasoning gap and generate partial logical models of the environment over which metric temporal logical formulas are evaluated. Using such formulas, hypotheses are formed and validated about the type of vehicles being observed. DyKnow is also used to generate event streams representing for example changes in qualitative spatial relations, which are used to detect traffic violations expressed as declarative chronicles.
---
paper_title: Remote Agent: To Boldly Go Where No AI System Has Gone Before

paper_content:

Abstract Renewed motives for space exploration have inspired NASA to work toward the goal of establishing a virtual presence in space, through heterogeneous fleets of robotic explorers. Information technology, and Artificial Intelligence in particular, will play a central role in this endeavor by endowing these explorers with a form of computational intelligence that we call remote agents . In this paper we describe the Remote Agent, a specific autonomous agent architecture based on the principles of model-based programming, on-board deduction and search, and goal-directed closed-loop commanding, that takes a significant step toward enabling this future. This architecture addresses the unique characteristics of the spacecraft domain that require highly reliable autonomous operations over long periods of time with tight deadlines, resource constraints, and concurrent activity among tightly coupled subsystems. The Remote Agent integrates constraintbased temporal planning and scheduling, robust multi-threaded execution, and model-based mode identification and reconfiguration. The demonstration of the integrated system as an on-board controller for Deep Space One, NASA's first New Millennium mission, is scheduled for a period of a week in mid 1999. The development of the Remote Agent also provided the opportunity to reassess some of AI's conventional wisdom about the challenges of implementing embedded systems, tractable reasoning, and knowledge representation. We discuss these issues, and our often contrary experiences, throughout the paper.
---
paper_title: Bounded Expectations for Discrepancy Detection in Goal-Driven Autonomy

paper_content:

Goal-Driven Autonomy (GDA) is a model for online planning extended with dynamic goal selection. GDA has been investigated in the context of numerous abstract planning domains, and there has been recent interest in applying GDA to control unmanned vehicles. In robotic domains, certain continuous state features from sensor data must be modeled for reasoning. However, modeling these features precisely during planning and execution monitoring may be problematic, due to the inefficiency of computing exact values or sensitivity to noise. We present PHOBOS, a Hierarchical Task Network planner with bounded expectations, which we apply with a GDA agent in an underwater vehicle domain. Bounded expectations allow an agent to plan and detect discrepancies more efficiently and with fewer false discrepancies (i.e., detected but semantically meaningless differences from expectations during execution). We describe an initial simulation study that supports this claim.
---
paper_title: Active and Interactive Discovery of Goal Selection Knowledge

paper_content:

If given manually-crafted goal selection knowledge, goal reasoning agents can dynamically determine which goals they should achieve in complex environments. These agents should instead learn goal selection knowledge through expert interaction. We describe T-ARTUE, a goal reasoning agent that performs case-based active and interactive learning to discover goal selection knowledge. We also report tests of its performance in a complex environment. We found that, under some conditions, T-ARTUE can quickly learn goal selection knowledge.
---
paper_title: There’s more to life than making plans: plan management in dynamic, multi-agent environments

paper_content:

For many years, research in AI plan generation was governed by a number of strong, simplifying assumptions: The planning agent is omniscient, its actions are deterministic and instantaneous, its goals are fixed and categorical, and its environment is static. More recently, researchers have developed expanded planning algorithms that are not predicated on such assumptions, but changing the way in which plans are formed is only part of what is required when the classical assumptions are abandoned. The demands of dynamic, uncertain environments mean that in addition to being able to form plans -- even probabilistic, uncertain plans -- agents must be able to effectively manage their plans. In this article, which is based on a talk given at the 1998 AAAI Fall Symposium on Distributed, Continual Planning, we first identify reasoning tasks that are involved in plan management, including commitment management, environment monitoring, alternative assessment, plan elaboration, metalevel control, and coordination with other agents. We next survey approaches we have developed to many of these tasks and discuss a plan-management system we are building to ground our theoretical work, by providing us with a platform for integrating our techniques and exploring their value in a realistic problem. Throughout, our discussion is informal and relies on numerous examples; the reader can consult the various papers cited for technical details.
---
paper_title: A Survey of Motivation Frameworks for Intelligent Systems

paper_content:

The ability to achieve one@?s goals is a defining characteristic of intelligent behaviour. A great many existing theories, systems and research programmes address the problems associated with generating behaviour to achieve a goal; much fewer address the related problems of how and why goals should be generated in an intelligent artifact, and how a subset of all possible goals are selected as the focus of behaviour. It is research into these problems of motivation, which this article aims to stimulate. Building from the analysis of a scenario involving a futuristic household robot, we extend an existing account of motivation in intelligent systems to provide a framework for surveying relevant literature in AI and robotics. This framework guides us to look at the problems of encoding drives (how the needs of the system are represented), goal generation (how particular instances of goals are generated from the drives with reference to the current state), and goal selection (how the system determines which goal instances to act on). After surveying a variety of existing approaches in these terms, we build on the results of the survey to sketch a design for a new motive management framework which goes beyond the current state of the art.
---
paper_title: Breadth of Approaches to Goal Reasoning: A Research Survey

paper_content:

Abstract : Goal-directed behavior is a hallmark of intelligence. While the majority of artificial intelligence research assumes goals are static and externally provided, many real-world applications involve unanticipated changes in the environment that may require changes to the goals themselves. Goal reasoning, which emphasizes the explicit representation of goals, their automatic formulation and dynamic management, is considered an important aspect of high-level autonomy. Building from these three basic requirements, we describe and apply a framework for surveying research related to goal reasoning that focuses on triggers and methods for goal formulation and goal management. We also summarize current research and highlight potential areas of future work.
---
paper_title: Navigation in hybrid metric-topological maps

paper_content:

We present an approach for navigation in hybrid maps consisting of a topological graph overlaid with local occupancy grids. The topological graph is built on top of a graph SLAM system, which can be efficiently optimized even for very large environments. The novel feature of our system is that it navigates locally using local metric maps, while the overall plan is formed on the topological graph. Unlike many current SLAM methods, we never reconstruct a full occupancy grid of the environment for localization or path planning. We show that our method generates near-optimal plans, and deals gracefully with changes to the map.
---
paper_title: Simultaneous localization and mapping (SLAM): part II

paper_content:

This paper discusses the recursive Bayesian formulation of the simultaneous localization and mapping (SLAM) problem in which probability distributions or estimates of absolute or relative locations of landmarks and vehicle pose are obtained. The paper focuses on three key areas: computational complexity; data association; and environment representation
---
paper_title: Visual servoing and visual tracking

paper_content:

This chapter introduces visual servo control, using computer vision data in the servo loop to control the motion of a robot. We first describe the basic tech- niques that are by now well established in the field. We give a general overview of the formulation of the visual servo control problem, and describe the two archetypal visual servo control schemes: image-based and position-based visual servo control. We then dis- cuss performance and stability issues that pertain to these two schemes, motivating advanced techniques. Of the many advanced techniques that have been de- veloped, we discuss 2 1/2 D, hybrid, partitioned and switched approaches. Having covered a variety of control schemes, we conclude by turning briefly to the problems of target tracking and controlling mo- tion directly in the joint space.
---
paper_title: Local metrical and global topological maps in the hybrid spatial semantic hierarchy

paper_content:

Topological and metrical methods for representing spatial knowledge have complementary strengths. We present a hybrid extension to the spatial semantic hierarchy that combines their strengths and avoids their weaknesses. Metrical SLAM methods are used to build local maps of small-scale space within the sensory horizon of the agent, while topological methods are used to represent the structure of large-scale space. We describe how a local perceptual map is analyzed to identify a local topology description and is abstracted to a topological place. The map building method creates a set of topological map hypotheses that are consistent with travel experience. The set of maps is guaranteed under reasonable assumptions to include the correct map. We demonstrate the method on a real environment with multiple nested large-scale loops.
---
paper_title: A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations

paper_content:

Abstract Kuipers, B. and Byun, Y.T., A robot exploration and mapping strategy based on a sematic hierarchy of spatial representations, Robotics and Autonomous System, 8 (1991) 47–63. We have developed a robust qualitative method for robot exploration, mapping, and navigation in large-scale spatial environments. Experiments with a simulated robot in a variety of complex 2D environments have demonstrated that our qualitative method can build an accurate map of a previously unkown environment in spite of substantial random and systematic sensorimotor error. Most current approaches to robot exploration and mapping analyze sensor input to build a geometrically precise map of the environment, then extract topological structure from the geometric description. Our approach recognizes and exploits qualitative properties of large-scale before relatively error-prone geometrical properties. [ sensorimotor ↔ control ] → topology → geometry At the control level, distinctive places and distinctive travel edges are identified based on the interaction between the robot's control strategies, its sensorimotor system, and the world. A distinctive place is defined as the local maximum of a distinctiveness measure appropriate to its immediate neighborhood, and is found by a hill-climbing control strategy. A distinctive travel edge, similarly, is defined by a suitable measure and a path-following control strategy. The topological network description is created by linking the distinctive places and travel edges.Metrical information is then incrementally assimilated into localgeometric descriptions of places and edges, and finally merged into a global geometric map. Topological ambiguity arising from sensorily indistinguishable places can be resolved at the topological level by the exploration strategy. With this representation, successful navigation is not critically dependent on the accuracy, or even the existence, of the geometrical description. We present examples demonstrating the process by which the robot explores and builds a map of a complex environment, including the effect of sensory errors. We also discuss new research directions that are suggested by this approach.
---
paper_title: FastSLAM 2.0: An Improved Particle Filtering Algorithm for Simultaneous Localization and Mapping that Provably Converges

paper_content:

Proceedings of IJCAI 2003 In [15], Montemerlo et al. proposed an algorithm called FastSLAM as an efficient and robust solution to the simultaneous localization and mapping problem. This paper describes a modified version of FastSLAM which overcomes important deficiencies of the original algorithm. We prove convergence of this new algorithm for linear SLAM problems and provide real-world experimental results that illustrate an order of magnitude improvement in accuracy over the original FastSLAM algorithm.
---
paper_title: HiPPo: Hierarchical POMDPs for planning information processing and sensing actions on a robot

paper_content:

Flexible general purpose robots need to tailor their visual processing to their task, on the fly. We propose a new approach to this within a planning framework, where the goal is to plan a sequence of visual operators to apply to the regions of interest (ROIs) in a scene. We pose the visual processing problem as a Partially Observable Markov Decision Process (POMDP). This requires probabilistic models of operator effects to quantitatively capture the unreliability of the processing actions, and thus reason precisely about trade-offs between plan execution time and plan reliability. Since planning in practical sized POMDPs is intractable we show how to ameliorate this intractability somewhat for our domain by defining a hierarchical POMDP. We compare the hierarchical POMDP approach with a Continual Planning (CP) approach. On a real robot visual domain, we show empirically that all the planning methods outperform naive application of all visual operators. The key result is that the POMDP methods produce more robust plans than either naive visual processing or the CP approach. In summary, we believe that visual processing problems represent a challenging and worthwhile domain for planning techniques, and that our hierarchical POMDP based approach to them opens up a promising new line of research.
---
paper_title: To secure an anchor -- a recovery planning approach to ambiguity in perceptual anchoring

paper_content:

An autonomous robot using symbolic reasoning, sensing and acting in a real environment needs the ability to create and maintain the connection between symbols representing objects in the world and the corresponding perceptual representations given by its sensors. This connection has been named perceptual anchoring. In complex environments, anchoring is not always easy to establish: the situation may often be ambiguous as to which percept actually corresponds to a given symbol. In this paper, we extend perceptual anchoring to deal robustly with ambiguous situations by providing general methods for detecting them and recovering from them. We consider different kinds of ambiguous situations. We also present methods to recover from these situations based on automatically formulating them as conditional planning problems that then are solved by a planner. We illustrate our approach by showing experiments involving a mobile robot equipped with a color camera and an electronic nose.
---
paper_title: Situation Recognition: Representation and Algorithms

paper_content:

The situation recognition system, to which this paper is devoted, receives as input a stream of time-stamped events; it performs recognition of instances of occurring situations, as they are developing, and it generates as output deduced events and actions to trigger. It is mainly a temporal reasoning system. It is predictive in the sense that it predicts forthcoming events relevant to its task, it focuses its attention on them and it maintains their temporal windows of relevance. Its main functionality is to recognize efficiently complex temporal patterns on the fly, while they are taking place. This system has been tested for the surveillance of an environment by a multisensory perception machine; it is being applied to monitoring a complex dynamic system.
---
paper_title: Bridging the Sense-Reasoning Gap: DyKnow -- Stream-Based Middleware for Knowledge Processing

paper_content:

Engineering autonomous agents that display rational and goal-directed behavior in dynamic physical environments requires a steady flow of information from sensors to high-level reasoning components. However, while sensors tend to generate noisy and incomplete quantitative data, reasoning often requires crisp symbolic knowledge. The gap between sensing and reasoning is quite wide, and cannot in general be bridged in a single step. Instead, this task requires a more general approach to integrating and organizing multiple forms of information and knowledge processing on different levels of abstraction in a structured and principled manner. We propose knowledge processing middleware as a systematic approach to organizing such processing. Desirable properties are presented and motivated. We argue that a declarative stream-based system is appropriate for the required functionality and present DyKnow, a concrete implemented instantiation of stream-based knowledge processing middleware with a formal semantics. Several types of knowledge processes are defined and motivated in the context of a UAV traffic monitoring application. In the implemented application, DyKnow is used to incrementally bridge the sense-reasoning gap and generate partial logical models of the environment over which metric temporal logical formulas are evaluated. Using such formulas, hypotheses are formed and validated about the type of vehicles being observed. DyKnow is also used to generate event streams representing for example changes in qualitative spatial relations, which are used to detect traffic violations expressed as declarative chronicles.
---
paper_title: Planning to perceive: exploiting mobility for robust object detection

paper_content:

Consider the task of a mobile robot autonomously navigating through an environment while detecting and mapping objects of interest using a noisy object detector. The robot must reach its destination in a timely manner, but is rewarded for correctly detecting recognizable objects to be added to the map, and penalized for false alarms. However, detector performance typically varies with vantage point, so the robot benefits from planning trajectories which maximize the efficacy of the recognition system. ::: ::: This work describes an online, any-time planning framework enabling the active exploration of possible detections provided by an off-the-shelf object detector. We present a probabilistic approach where vantage points are identified which provide a more informative view of a potential object. The agent then weighs the benefit of increasing its confidence against the cost of taking a detour to reach each identified vantage point. The system is demonstrated to significantly improve detection and trajectory length in both simulated and real robot experiments.
---
paper_title: Perceptual Anchoring: A Key Concept for Plan Execution in Embedded Systems

paper_content:

Anchoring is the process of creating and maintaining the correspondence between symbols and percepts that refer to the same physical objects. This process must necessarily be present in any physically embedded system that includes a symbolic component, for instance, in an autonomous robot that uses a planner to generate strategic decisions. However, no systematic study of anchoring as a problem per se has been reported in the literature on intelligent systems. In this paper, we advocate for the need for a domain-independent framework to deal with the anchoring problem, and we report some initial steps in this direction. We illustrate our arguments and framework by showing experiments performed on a real mobile robot.
---
paper_title: HiPPo: Hierarchical POMDPs for planning information processing and sensing actions on a robot

paper_content:

Flexible general purpose robots need to tailor their visual processing to their task, on the fly. We propose a new approach to this within a planning framework, where the goal is to plan a sequence of visual operators to apply to the regions of interest (ROIs) in a scene. We pose the visual processing problem as a Partially Observable Markov Decision Process (POMDP). This requires probabilistic models of operator effects to quantitatively capture the unreliability of the processing actions, and thus reason precisely about trade-offs between plan execution time and plan reliability. Since planning in practical sized POMDPs is intractable we show how to ameliorate this intractability somewhat for our domain by defining a hierarchical POMDP. We compare the hierarchical POMDP approach with a Continual Planning (CP) approach. On a real robot visual domain, we show empirically that all the planning methods outperform naive application of all visual operators. The key result is that the POMDP methods produce more robust plans than either naive visual processing or the CP approach. In summary, we believe that visual processing problems represent a challenging and worthwhile domain for planning techniques, and that our hierarchical POMDP based approach to them opens up a promising new line of research.
---
paper_title: Towards robotic assistants in nursing homes: Challenges and results

paper_content:

Abstract This paper describes a mobile robotic assistant, developed to assist elderly individuals with mild cognitive and physical impairments, as well as support nurses in their daily activities. We present three software modules relevant to ensure successful human–robot interaction: an automated reminder system; a people tracking and detection system; and finally a high-level robot controller that performs planning under uncertainty by incorporating knowledge from low-level modules, and selecting appropriate courses of actions. During the course of experiments conducted in an assisted living facility, the robot successfully demonstrated that it could autonomously provide reminders and guidance for elderly residents.
---
paper_title: Efficient Discriminant Viewpoint Selection for Active Bayesian Recognition

paper_content:

This paper presents a novel viewpoint selection criterion for active object recognition and pose estimation whose key advantage resides in its low computational cost with respect to current popular approaches in the literature. The proposed observation selection criterion associates high utility with observations that predictably facilitate distinction between pairs of competing hypotheses by a Bayesian classifier. Rigorous experimentation of the proposed approach was conducted on two case studies, involving synthetic and real data, respectively. The results show the proposed algorithm to perform better than a random navigation strategy in terms of the amount of data required for recognition while being much faster than a strategy based on mutual information, without compromising accuracy.
---
paper_title: The Belief Roadmap: Efficient Planning in Belief Space by Factoring the Covariance

paper_content:

When a mobile agent does not know its position perfectly, incorporating the predicted uncertainty of future position estimates into the planning process can lead to substantially better motion performance. However, planning in the space of probabilistic position estimates, or belief space, can incur a substantial computational cost. In this paper, we show that planning in belief space can be performed efficiently for linear Gaussian systems by using a factored form of the covariance matrix. This factored form allows several prediction and measurement steps to be combined into a single linear transfer function, leading to very efficient posterior belief prediction during planning. We give a belief-space variant of the probabilistic roadmap algorithm called the belief roadmap (BRM) and show that the BRM can compute plans substantially faster than conventional belief space planning. We conclude with performance results for an agent using ultra-wide bandwidth radio beacons to localize and show that we can efficiently generate plans that avoid failures due to loss of accurate position estimation.
---
paper_title: Planning to perceive: exploiting mobility for robust object detection

paper_content:

Consider the task of a mobile robot autonomously navigating through an environment while detecting and mapping objects of interest using a noisy object detector. The robot must reach its destination in a timely manner, but is rewarded for correctly detecting recognizable objects to be added to the map, and penalized for false alarms. However, detector performance typically varies with vantage point, so the robot benefits from planning trajectories which maximize the efficacy of the recognition system. ::: ::: This work describes an online, any-time planning framework enabling the active exploration of possible detections provided by an off-the-shelf object detector. We present a probabilistic approach where vantage points are identified which provide a more informative view of a potential object. The agent then weighs the benefit of increasing its confidence against the cost of taking a detour to reach each identified vantage point. The system is demonstrated to significantly improve detection and trajectory length in both simulated and real robot experiments.
---
paper_title: An introduction to the anchoring problem

paper_content:

Anchoring is the problem of connecting, inside an artificial system, symbols and sensor data that refer to the same physical objects in the external world. This problem needs to be solved in any robotic system that incorporates a symbolic component. However, it is only recently that the anchoring problem has started to be addressed as a problem per se, and a few general solutions have begun to appear in the literature. This paper introduces the special issue on perceptual anchoringof the Robotics and Autonomous Systemsjournal. Our goal is to provide a general overview of the anchoring problem, and highlight some of its subtle points. © 2003 Elsevier Science B.V. All rights reserved.
---
paper_title: To secure an anchor -- a recovery planning approach to ambiguity in perceptual anchoring

paper_content:

An autonomous robot using symbolic reasoning, sensing and acting in a real environment needs the ability to create and maintain the connection between symbols representing objects in the world and the corresponding perceptual representations given by its sensors. This connection has been named perceptual anchoring. In complex environments, anchoring is not always easy to establish: the situation may often be ambiguous as to which percept actually corresponds to a given symbol. In this paper, we extend perceptual anchoring to deal robustly with ambiguous situations by providing general methods for detecting them and recovering from them. We consider different kinds of ambiguous situations. We also present methods to recover from these situations based on automatically formulating them as conditional planning problems that then are solved by a planner. We illustrate our approach by showing experiments involving a mobile robot equipped with a color camera and an electronic nose.
---
paper_title: Learning to act using real-time dynamic programming

paper_content:

Learning methods based on dynamic programming (DP) are receiving increasing attention in artificial intelligence. Researchers have argued that DP provides the appropriate basis for compiling planning results into reactive strategies for real-time control, as well as for learning such strategies when the system being controlled is incompletely known. We introduce an algorithm based on DF, which we call Real-Time DP (RTDP), by which an embedded system can improve its performance with experience. RTDP generalizes Korf's Learning-Real-Time-A* algorithm to problems involving uncertainty. We invoke results from the theory of asynchronous DP to prove that RTDP achieves optimal behavior in several different classes of problems. We also use the theory of asynchronous DF to illuminate aspects of other DP-based reinforcement learning methods such as Watkins' Q-Learning algorithm. A secondary aim of this article is to provide a bridge between Al research on real-time planning and learning and relevant concepts and algorithms from control theory.
---
paper_title: Finding Mutual Exclusion Invariants in Temporal Planning Domains

paper_content:

Abstract We present a technique for automatically extractingtemporal mutual exclusion invariants from PDDL2.2planning instances. We ﬁrst identify a set of invariantcandidates by inspecting the domain and then checkthese candidates against properties that assure invari-ance. If these properties are violated, we show that itis sometimes possible to reﬁne a candidate by addingadditional propositions and turn it into a real invariant.Our technique builds on other approaches to invariantsynthesis presented in the literature, but departs fromtheir limited focus on instantaneous discrete actions byaddressing temporal and numeric domains. To deal withtime, we formulate invariance conditions that accountfor both the entire structure of the operators (includingthe conditions, rather than just the effects) and the possi-ble interactions between operators. As a result, we con-struct a technique that is not only capable of identifyinginvariants for temporal domains, but is also able to ﬁnd abroader set of invariants for non-temporal domains thanthe previous techniques.
---
paper_title: Planning Robust Temporal Plans A Comparison Between CBTP and TGA Approaches

paper_content:

Planning for real world applications, with explicit temporal representation and a robust execution is a very challenging problem. To tackle it, the planning community has proposed a number of original and successful approaches. However, there are other paradigms "outside" the Automated Planning field which may prove to be successful with respect to this objective. This paper presents a comparison of two "planning" approaches dealing with temporal and/or discrete uncertainties and with a strong emphasis on robust execution. The first approach is based on chronicles and constraint satisfaction techniques; it relies on a causal link partial order temporal planner, in our case IXTET. The second approach is based on timed game automata and reachability analysis, and uses the UPPAAL-TIGA system. The comparison is both qualitative (the kind of problems modeled and the properties of plans obtained) and quantitative (experimental results on a real example). To make this comparison possible, we propose a general scheme to translate a subset of IXTET planning problems into UPPAAL-TIGA game-reachability problems. A direct consequence of this automated process would be the possibility to apply validation and verification techniques available in the timed automata community.
---
paper_title: Perceptual Anchoring: A Key Concept for Plan Execution in Embedded Systems

paper_content:

Anchoring is the process of creating and maintaining the correspondence between symbols and percepts that refer to the same physical objects. This process must necessarily be present in any physically embedded system that includes a symbolic component, for instance, in an autonomous robot that uses a planner to generate strategic decisions. However, no systematic study of anchoring as a problem per se has been reported in the literature on intelligent systems. In this paper, we advocate for the need for a domain-independent framework to deal with the anchoring problem, and we report some initial steps in this direction. We illustrate our arguments and framework by showing experiments performed on a real mobile robot.
---
paper_title: An introduction to the anchoring problem

paper_content:

Anchoring is the problem of connecting, inside an artificial system, symbols and sensor data that refer to the same physical objects in the external world. This problem needs to be solved in any robotic system that incorporates a symbolic component. However, it is only recently that the anchoring problem has started to be addressed as a problem per se, and a few general solutions have begun to appear in the literature. This paper introduces the special issue on perceptual anchoringof the Robotics and Autonomous Systemsjournal. Our goal is to provide a general overview of the anchoring problem, and highlight some of its subtle points. © 2003 Elsevier Science B.V. All rights reserved.
---
paper_title: A meta-learning approach to ground symbols from visual percepts

paper_content:

There is a growing interest in both the robotics and AI communities to give autonomous robots the ability to interact with humans. To efficiently identify properties from its environment (be it the presence of a human, or a fire extinguisher or another robot of its kind) is one of the critical tasks for supporting meaningful robot/human dialogues. This task is a particular anchoring task. Our goal is to endow autonomous mobile robots (in our experiments a Pioneer 2DX) with a perceptual system that can efficiently adapt itself to the context so as to enable the learning task required to physically ground symbols. In effect, Machine Learning based approaches to provide robots with an ability to ground symbols heavily rely on ad hoc perceptual representation provided by AI designers. Our approach is in the line of meta-learning algorithms, that iteratively change representations so as to discover one that is well-fitted for the task. The architecture we propose is based on a widely used approach in constructive induction: the Wrapper-model. Experiments using the PLIC system to have a robot identify the presence of humans and fire extinguishers show the interest of such an approach that dynamically abstracts a well-fitted image description depending on the concept to learn.
---
paper_title: Grounding inference in distributed multi-robot environments

paper_content:

Abstract Traditional symbolic reasoning systems are typically built on a transaction model of computation, which complicates the process of synchronizing their world models with changes in a dynamic environment. This problem is exacerbated in the multi-robot case, where there are now n world models keep in synch. In this paper, we describe an inference grounding and coordination mechanism for robot teams based on tagged behavior-based systems. This approach supports a large subset of classical AI techniques while providing a novel representation that allows team members to share information efficiently. We illustrate our approach on two problems involving systematic spatial search.
---
paper_title: Generalized plan recognition

paper_content:

This paper outlines a new theory of plan recognition that is significantly more powerful than previous approaches. Concurrent actions, shared steps between actions, and disjunctive information are all handled. The theory allows one to draw conclusions based on the class of possible plans being performed, rather than having to prematurely commit to a single interpretation. The theory employs circumscription to transform a first-order theory of action into an action taxonomy, which can be used to logically deduce the complex action(s) an agent is performing.
---
paper_title: Situation Recognition: Representation and Algorithms

paper_content:

The situation recognition system, to which this paper is devoted, receives as input a stream of time-stamped events; it performs recognition of instances of occurring situations, as they are developing, and it generates as output deduced events and actions to trigger. It is mainly a temporal reasoning system. It is predictive in the sense that it predicts forthcoming events relevant to its task, it focuses its attention on them and it maintains their temporal windows of relevance. Its main functionality is to recognize efficiently complex temporal patterns on the fly, while they are taking place. This system has been tested for the surveillance of an environment by a multisensory perception machine; it is being applied to monitoring a complex dynamic system.
---
paper_title: Probabilistic State-Dependent Grammars for Plan Recognition

paper_content:

Techniques for plan recognition under uncertainty require a stochastic model of the plangeneration process. We introduce probabilistic state-dependent grammars (PSDGs) to represent an agent's plan-generation process. The PSDG language model extends probabilistic contextfree grammars (PCFGs) by allowing production probabilities to depend on an explicit model of the planning agent's internal and external state. Given a PSDG description of the plan-generation process, we can then use inference algorithms that exploit the particular independence properties of the PSDG language to efficiently answer plan-recognition queries. The combination of the PSDG language model and inference algorithms extends the range of plan-recognition domains for which practical probabilistic inference is possible, as illustrated by applications in traffic monitoring and air combat.
---
paper_title: Vision-Based Gesture Recognition: A Review

paper_content:

With the development of ubiquitous computing, current user interaction approaches with keyboard, mouse and pen are not sufficient. Due to the limitation of these devices the useable command set is also limited. Direct use of hands as an input device is an attractive method for providing natural Human Computer Interaction which has evolved from text-based interfaces through 2D graphical-based interfaces, multimedia-supported interfaces, to fully fledged multi-participant Virtual Environment (VE) systems. Imagine the human-computer interaction of the future: A 3D- application where you can move and rotate objects simply by moving and rotating your hand - all without touching any input device. In this paper a review of vision based hand gesture recognition is presented. The existing approaches are categorized into 3D model based approaches and appearance based approaches, highlighting their advantages and shortcomings and identifying the open issues.
---
paper_title: The meaning of action: A review on action recognition and mapping

paper_content:

In this paper, we analyze the different approaches taken to date within the computer vision, robotics and artificial intelligence communities for the representation, recognition, synthesis and understanding of action. We deal with action at different levels of complexity and provide the reader with the necessary related literature references. We put the literature references further into context and outline a possible interpretation of action by taking into account the different aspects of action recognition, action synthesis and task-level planning.
---
paper_title: A survey of robot learning from demonstration

paper_content:

We present a comprehensive survey of robot Learning from Demonstration (LfD), a technique that develops policies from example state to action mappings. We introduce the LfD design choices in terms of demonstrator, problem space, policy derivation and performance, and contribute the foundations for a structure in which to categorize LfD research. Specifically, we analyze and categorize the multiple ways in which examples are gathered, ranging from teleoperation to imitation, as well as the various techniques for policy derivation, including matching functions, dynamics models and plans. To conclude we discuss LfD limitations and related promising areas for future research.
---
paper_title: Probabilistic plan recognition using off-the-shelf classical planners

paper_content:

Plan recognition is the problem of inferring the goals and plans of an agent after observing its behavior. Recently, it has been shown that this problem can be solved efficiently, without the need of a plan library, using slightly modified planning algorithms. In this work, we extend this approach to the more general problem of probabilistic plan recognition where a probability distribution over the set of goals is sought under the assumptions that actions have deterministic effects and both agent and observer have complete information about the initial state. We show that this problem can be solved efficiently using classical planners provided that the probability of a partially observed execution given a goal is defined in terms of the cost difference of achieving the goal under two conditions: complying with the observations, and not complying with them. This cost, and hence the posterior goal probabilities, are computed by means of two calls to a classical planner that no longer has to be modified in any way. A number of examples is considered to illustrate the quality, flexibility, and scalability of the approach.
---
paper_title: Video understanding for complex activity recognition

paper_content:

This paper presents a real-time video understanding system which automatically recognises activities occurring in environments observed through video surveillance cameras. Our approach consists in three main stages: Scene Tracking, Coherence Maintenance, and Scene Understanding. The main challenges are to provide a robust tracking process to be able to recognise events in outdoor and in real applications conditions, to allow the monitoring of a large scene through a camera network, and to automatically recognise complex events involving several actors interacting with each others. This approach has been validated for Airport Activity Monitoring in the framework of the European project AVITRACK.
---
paper_title: Chronicle Recognition Improvement Using Temporal Focusing and Hierarchization

paper_content:

This article falls under the problem of the symbolic monitoring of real-time complex systems or of video interpretation systems. Among the various techniques used for the on-line monitoring, we are interested here in the temporal scenario recognition. In order to reduce the complexity of the recognition and, consequently, to improve its performance, we explore two methods: the first one is the focus on particular events (in practice, uncommon ones) and the second one is the factorization of common temporal scenarios in order to do a hierarchical recognition. In this article, we present both concepts and merge them to propose a focused hierarchical recognition. This approach merges and generalizes the two main approaches in symbolic recognition of temporal scenarios: the Store Totally Recognized Scenarios (STRS) approach and the Store Partially Recognized Scenarios (SPRS) approach.
---
paper_title: A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems

paper_content:

Research with autonomous unmanned aircraft systems is reaching a new degree of sophistication where targeted missions require complex types of deliberative capability integrated in a practical manner in such systems. Due to these pragmatic constraints, integration is just as important as theoretical and applied work in developing the actual deliberative functionalities. In this article, we present a temporal logic-based task planning and execution monitoring framework and its integration into a fully deployed rotor-based unmanned aircraft system developed in our laboratory. We use a very challenging emergency services application involving body identification and supply delivery as a vehicle for showing the potential use of such a framework in real-world applications. TALplanner, a temporal logic-based task planner, is used to generate mission plans. Building further on the use of TAL (Temporal Action Logic), we show how knowledge gathered from the appropriate sensors during plan execution can be used to create state structures, incrementally building a partial logical model representing the actual development of the system and its environment over time. We then show how formulas in the same logic can be used to specify the desired behavior of the system and its environment and how violations of such formulas can be detected in a timely manner in an execution monitor subsystem. The pervasive use of logic throughout the higher level deliberative layers of the system architecture provides a solid shared declarative semantics that facilitates the transfer of knowledge between different modules.
---
paper_title: Bridging the Sense-Reasoning Gap: DyKnow -- Stream-Based Middleware for Knowledge Processing

paper_content:

Engineering autonomous agents that display rational and goal-directed behavior in dynamic physical environments requires a steady flow of information from sensors to high-level reasoning components. However, while sensors tend to generate noisy and incomplete quantitative data, reasoning often requires crisp symbolic knowledge. The gap between sensing and reasoning is quite wide, and cannot in general be bridged in a single step. Instead, this task requires a more general approach to integrating and organizing multiple forms of information and knowledge processing on different levels of abstraction in a structured and principled manner. We propose knowledge processing middleware as a systematic approach to organizing such processing. Desirable properties are presented and motivated. We argue that a declarative stream-based system is appropriate for the required functionality and present DyKnow, a concrete implemented instantiation of stream-based knowledge processing middleware with a formal semantics. Several types of knowledge processes are defined and motivated in the context of a UAV traffic monitoring application. In the implemented application, DyKnow is used to incrementally bridge the sense-reasoning gap and generate partial logical models of the environment over which metric temporal logical formulas are evaluated. Using such formulas, hypotheses are formed and validated about the type of vehicles being observed. DyKnow is also used to generate event streams representing for example changes in qualitative spatial relations, which are used to detect traffic violations expressed as declarative chronicles.
---
paper_title: Navigation in hybrid metric-topological maps

paper_content:

We present an approach for navigation in hybrid maps consisting of a topological graph overlaid with local occupancy grids. The topological graph is built on top of a graph SLAM system, which can be efficiently optimized even for very large environments. The novel feature of our system is that it navigates locally using local metric maps, while the overall plan is formed on the topological graph. Unlike many current SLAM methods, we never reconstruct a full occupancy grid of the environment for localization or path planning. We show that our method generates near-optimal plans, and deals gracefully with changes to the map.
---
paper_title: Apprenticeship learning for helicopter control

paper_content:

Autonomous helicopter flight is widely regarded to be a highly challenging control problem. As helicopters are highly unstable and exhibit complicated dynamical behavior, it is particularly difficult to design controllers that achieve high performance over a broad flight regime. While these aircraft are notoriously difficult to control, there are expert human pilots who are nonetheless capable of demonstrating a wide variety of maneuvers, including aerobatic maneuvers at the edge of the helicopter's performance envelope. In this paper, we present algorithms for modeling and control that leverage these demonstrations to build high-performance control systems for autonomous helicopters. More specifically, we detail our experiences with the Stanford Autonomous Helicopter, which is now capable of extreme aerobatic flight meeting or exceeding the performance of our own expert pilot.
---
paper_title: Simultaneous localization and mapping (SLAM): part II

paper_content:

This paper discusses the recursive Bayesian formulation of the simultaneous localization and mapping (SLAM) problem in which probability distributions or estimates of absolute or relative locations of landmarks and vehicle pose are obtained. The paper focuses on three key areas: computational complexity; data association; and environment representation
---
paper_title: Policy Search for Motor Primitives in Robotics

paper_content:

Many motor skills in humanoid robotics can be learned using parametrized motor primitives as done in imitation learning. However, most interesting motor learning problems are high-dimensional reinforcement learning problems often beyond the reach of current methods. In this paper, we extend previous work on policy learning from the immediate reward case to episodic reinforcement learning. We show that this results in a general, common framework also connected to policy gradient methods and yielding a novel algorithm for policy learning that is particularly well-suited for dynamic motor primitives. The resulting algorithm is an EM-inspired algorithm applicable to complex motor learning tasks. We compare this algorithm to several well-known parametrized policy search methods and show that it outperforms them. We apply it in the context of motor learning and show that it can learn a complex Ball-in-a-Cup task using a real Barrett WAM™ robot arm.
---
paper_title: From Motor Learning to Interaction Learning in Robots ∗

paper_content:

From an engineering standpoint, the increasing complexity of robotic systems and the increasing demand for more autonomously learning robots, has become essential. This book is largely based on the successful workshop From motor to interaction learning in robots held at the IEEE/RSJ International Conference on Intelligent Robot Systems. The major aim of the book is to give students interested the topics described above a chance to get started faster and researchers a helpful compandium.
---
paper_title: Robotic Mapping: A Survey

paper_content:

This article provides a comprehensive introduction into the field of robotic mapping, with a focus on indoor mapping. It describes and compares various probabilistic techniques, as they are presently being applied to a vast array of mobile robot mapping problems. The history of robotic mapping is also detailed, along with an extensive list of open research problems.
---
paper_title: Model learning for robot control: a survey

paper_content:

Models are among the most essential tools in robotics, such as kinematics and dynamics models of the robot’s own body and controllable external objects. It is widely believed that intelligent mammals also rely on internal models in order to generate their actions. However, while classical robotics relies on manually generated models that are based on human insights into physics, future autonomous, cognitive robots need to be able to automatically generate models that are based on information which is extracted from the data streams accessible to the robot. In this paper, we survey the progress in model learning with a strong focus on robot control on a kinematic as well as dynamical level. Here, a model describes essential information about the behavior of the environment and the influence of an agent on this environment. In the context of model-based learning control, we view the model from three different perspectives. First, we need to study the different possible model learning architectures for robotics. Second, we discuss what kind of problems these architecture and the domain of robotics imply for the applicable learning methods. From this discussion, we deduce future directions of real-time learning algorithms. Third, we show where these scenarios have been used successfully in several case studies.
---
paper_title: A Bayesian Exploration-Exploitation Approach for Optimal Online Sensing and Planning with a Visually Guided Mobile Robot

paper_content:

We address the problem of online path planning for optimal sensing with a mobile robot. The objective of the robot is to learn the most about its pose and the environment given time constraints. We use a POMDP with a utility function that depends on the belief state to model the finite horizon planning problem. We replan as the robot progresses throughout the environment. The POMDP is high-dimensional, continuous, non-differentiable, nonlinear, non-Gaussian and must be solved in real-time. Most existing techniques for stochastic planning and reinforcement learning are therefore inapplicable. To solve this extremely complex problem, we propose a Bayesian optimization method that dynamically trades off exploration (minimizing uncertainty in unknown parts of the policy space) and exploitation (capitalizing on the current best solution). We demonstrate our approach with a visually-guide mobile robot. The solution proposed here is also applicable to other closely-related domains, including active vision, sequential experimental design, dynamic sensing and calibration with mobile sensors.
---
paper_title: Online probabilistic topological mapping

paper_content:

We present a novel algorithm for topological mapping, which is the problem of finding the graph structure of an environment from a sequence of measurements. Our algorithm, called Online Probabilistic Topological Mapping (OPTM), systematically addresses the problem by constructing the posterior on the space of all possible topologies given measurements. With each successive measurement, the posterior is updated incrementally using a Rao-Blackwellized particle filter. We present efficient sampling mechanisms using data-driven proposals and prior distributions on topologies that further enable OPTM's operation in an online manner. OPTM can incorporate various sensors seamlessly, as is demonstrated by our use of appearance, laser, and odometry measurements. OPTM is the first topological mapping algorithm that is theoretically accurate, systematic, sensor independent, and online, and thus advances the state of the art significantly. We evaluate the algorithm on a robot in diverse environments.
---
paper_title: Topological Simultaneous Localization and Mapping (SLAM): Toward Exact Localization Without Explicit Localization

paper_content:

This paper presents a new method for simultaneous localization and mapping that exploits the topology of the robot's free space to localize the robot on a partially constructed map. The topology of the environment is encoded in a topological map; the particular topological map used in this paper is the generalized Voronoi graph (GVG), which also encodes some metric information about the robot's environment, as well. In this paper, we present the low-level control laws that generate the GVG edges and nodes, thereby allowing for exploration of an unknown space. With these prescribed control laws, the GVG can be viewed as an arbitrator for a hybrid control system that determines when to invoke a particular low-level controller from a set of controllers all working toward the high-level capability of mobile robot exploration. The main contribution, however, is using the graph structure of the GVG, via a graph matching process, to localize the robot. Experimental results verify the described work.
---
paper_title: Robot Task Planning using Semantic Maps

paper_content:

Task planning for mobile robots usually relies solely on spatial information and on shallow domain knowledge, such as labels attached to objects and places. Although spatial information is necessary for performing basic robot operations (navigation and localization), the use of deeper domain knowledge is pivotal to endow a robot with higher degrees of autonomy and intelligence. In this paper, we focus on semantic knowledge, and show how this type of knowledge can be profitably used for robot task planning. We start by defining a specific type of semantic maps, which integrates hierarchical spatial information and semantic knowledge. We then proceed to describe how these semantic maps can improve task planning in two ways: extending the capabilities of the planner by reasoning about semantic information, and improving the planning efficiency in large domains. We show several experiments that demonstrate the effectiveness of our solutions in a domain involving robot navigation in a domestic environment.
---
paper_title: Life-Long Optimization of the Symbolic Model of Indoor Environments for a Mobile Robot

paper_content:

The use of a symbolic model of the spatial environment becomes crucial for a mobile robot that is intended to operate optimally and intelligently in indoor scenarios. Constructing such a model involves important problems that are not solved completely at present. One is called anchoring, which implies to maintain a correct dynamic correspondence between the real world and the symbols in the model. The other problem is adaptation: among the numerous possible models that could be constructed for representing a given environment, optimization involves the selection of one that improves as much as possible the operations of the robot. To cope with both problems, in this paper, we propose a framework that allows an indoor mobile robot to learn automatically a symbolic model of its environment and to optimize it over time with respect to changes in both the environment and the robot operational needs through an evolutionary algorithm. For coping efficiently with the large amounts of information that the real world provides, we use abstraction, which also helps in improving task planning. Our experiments demonstrate that the proposed framework is suitable for providing an indoor mobile robot with a good symbolic model and adaptation capabilities.
---
paper_title: Semantic Modeling of Places using Objects

paper_content:

Presented at the 2007 Robotics: Science and Systems Conference III (RSS), 27-30 June 2007, Atlanta, GA.
---
paper_title: Robot Learning from Human Teachers

paper_content:

Learning from Demonstration (LfD) explores techniques for learning a task policy from examples provided by a human teacher. The field of LfD has grown into an extensive body of literature over the past 30 years, with a wide variety of approaches for encoding human demonstrations and modeling skills and tasks. Additionally, we have recently seen a focus on gathering data from non-expert human teachers (i.e., domain experts but not robotics experts). In this book, we provide an introduction to the field with a focus on the unique technical challenges associated with designing robots that learn from naive human teachers. We begin, in the introduction, with a unification of the various terminology seen in the literature as well as an outline of the design choices one has in designing an LfD system. Chapter 2 gives a brief survey of the psychology literature that provides insights from human social learning that are relevant to designing robotic social learners. Chapter 3 walks through an LfD interaction, surveying the design choices one makes and state of the art approaches in prior work. First, is the choice of input, how the human teacher interacts with the robot to provide demonstrations. Next, is the choice of modeling technique. Currently, there is a dichotomy in the field between approaches that model low-level motor skills and those that model high-level tasks composed of primitive actions. We devote a chapter to each of these. Chapter 7 is devoted to interactive and active learning approaches that allow the robot to refine an existing task model. And finally, Chapter 8 provides best practices for evaluation of LfD systems, with a focus on how to approach experiments with human subjects in this domain.
---
paper_title: Algorithms for Inverse Reinforcement Learning

paper_content:

Objective—To evaluate the pharmacokinetics of a novel commercial formulation of ivermectin after administration to goats. Animals—6 healthy adult goats. Procedure—Ivermectin (200 μg/kg) was initially administered IV to each goat, and plasma samples were obtained for 36 days. After a washout period of 3 weeks, each goat received a novel commercial formulation of ivermectin (200 μg/kg) by SC injection. Plasma samples were then obtained for 42 days. Drug concentrations were quantified by use of high-performance liquid chromatography with fluorescence detection. Results—Pharmacokinetics of ivermectin after IV administration were best described by a 2-compartment open model; values for main compartmental variables included volume of distribution at a steady state (9.94 L/kg), clearance (1.54 L/kg/d), and area under the plasma concentration-time curve (AUC; 143 [ng•d]/mL). Values for the noncompartmental variables included mean residence time (7.37 days), AUC (153 [ng•d]/mL), and clearance (1.43 L/kg/d). After ...
---
paper_title: Probabilistic Policy Reuse for Inter-Task Transfer Learning

paper_content:

Policy Reuse is a reinforcement learning technique that efficiently learns a new policy by using past similar learned policies. The Policy Reuse learner improves its exploration by probabilistically including the exploitation of those past policies. Policy Reuse was introduced, and its effectiveness was previously demonstrated, in problems with different reward functions in the same state and action spaces. In this article, we contribute Policy Reuse as transfer learning among different domains. We introduce extended Markov Decision Processes (MDPs) to include domains and tasks, where domains have different state and action spaces, and tasks are problems with different rewards within a domain. We show how Policy Reuse can be applied among domains by defining and using a mapping between their state and action spaces. We use several domains, as versions of a simulated RoboCup Keepaway problem, where we show that Policy Reuse can be used as a mechanism of transfer learning significantly outperforming a basic policy learner.
---
paper_title: Efficient learning of action schemas and web-service descriptions

paper_content:

This work addresses the problem of efficiently learning action schemas using a bounded number of samples (interactions with the environment). We consider schemas in two languages--traditional STRIPS, and a new language STRIPS+WS that extends STRIPS to allow for the creation of new objects when an action is executed. This modification allows STRIPS+WS to model web services and can be used to describe web-service composition (planning) problems. We show that general STRIPS operators cannot be efficiently learned through raw experience, though restricting the size of action preconditions yields a positive result. We then show that efficient learning is possible without this restriction if an agent has access to a "teacher" that can provide solution traces on demand. We adapt this learning algorithm to efficiently learn web-service descriptions in STRIPS+WS.
---
paper_title: Learning-Assisted Automated Planning: Looking Back, Taking Stock, Going Forward

paper_content:

This article reports on an extensive survey and analysis of research work related to machine learning as it applies to automated planning over the past 30 years. Major research contributions are broadly characterized by learning method and then descriptive subcategories. Survey results reveal learning techniques that have extensively been applied and a number that have received scant attention. We extend the survey analysis to suggest promising avenues for future research in learning based on both previous experience and current needs in the planning community.
---
paper_title: Reinforcement Learning: A Tutorial Survey and Recent Advances

paper_content:

In the last few years, reinforcement learning (RL), also called adaptive (or approximate) dynamic programming, has emerged as a powerful tool for solving complex sequential decision-making problems in control theory. Although seminal research in this area was performed in the artificial intelligence (AI) community, more recently it has attracted the attention of optimization theorists because of several noteworthy success stories from operations management. It is on large-scale and complex problems of dynamic optimization, in particular the Markov decision problem (MDP) and its variants, that the power of RL becomes more obvious. It has been known for many years that on large-scale MDPs, the curse of dimensionality and the curse of modeling render classical dynamic programming (DP) ineffective. The excitement in RL stems from its direct attack on these curses, which allows it to solve problems that were considered intractable via classical DP in the past. The success of RL is due to its strong mathematical roots in the principles of DP, Monte Carlo simulation, function approximation, and AI. Topics treated in some detail in this survey are temporal differences, Q-learning, semi-MDPs, and stochastic games. Several recent advances in RL, e.g., policy gradients and hierarchical RL, are covered along with references. Pointers to numerous examples of applications are provided. This overview is aimed at uncovering the mathematical roots of this science so that readers gain a clear understanding of the core concepts and are able to use them in their own research. The survey points to more than 100 references from the literature.
---
paper_title: Relational Reinforcement Learning

paper_content:

Relational reinforcement learning is presented, a learning technique that combines reinforcement learning with relational learning or inductive logic programming. Due to the use of a more expressive representation language to represent states, actions and Q-functions, relational reinforcement learning can be potentially applied to a new range of learning tasks. One such task that we investigate is planning in the blocks world, where it is assumed that the effects of the actions are unknown to the agent and the agent has to learn a policy. Within this simple domain we show that relational reinforcement learning solves some existing problems with reinforcement learning. In particular, relational reinforcement learning allows us to employ structural representations, to abstract from specific goals pursued and to exploit the results of previous learning phases when addressing new (more complex) situations.
---
paper_title: Learning how to combine sensory-motor functions into a robust behavior

paper_content:

This article describes a system, called Robel, for defining a robot controller that learns from experience very robust ways of performing a high-level task such as ''navigate to''. The designer specifies a collection of skills, represented as hierarchical tasks networks, whose primitives are sensory-motor functions. The skills provide different ways of combining these sensory-motor functions to achieve the desired task. The specified skills are assumed to be complementary and to cover different situations. The relationship between control states, defined through a set of task-dependent features, and the appropriate skills for pursuing the task is learned as a finite observable Markov decision process (MDP). This MDP provides a general policy for the task; it is independent of the environment and characterizes the abilities of the robot for the task.
---
paper_title: Policy Search for Motor Primitives in Robotics

paper_content:

Many motor skills in humanoid robotics can be learned using parametrized motor primitives as done in imitation learning. However, most interesting motor learning problems are high-dimensional reinforcement learning problems often beyond the reach of current methods. In this paper, we extend previous work on policy learning from the immediate reward case to episodic reinforcement learning. We show that this results in a general, common framework also connected to policy gradient methods and yielding a novel algorithm for policy learning that is particularly well-suited for dynamic motor primitives. The resulting algorithm is an EM-inspired algorithm applicable to complex motor learning tasks. We compare this algorithm to several well-known parametrized policy search methods and show that it outperforms them. We apply it in the context of motor learning and show that it can learn a complex Ball-in-a-Cup task using a real Barrett WAM™ robot arm.
---
paper_title: Learning heuristic functions from relaxed plans

paper_content:

We present a novel approach to learning heuristic functions for AI planning domains. Given a state, we view a relaxed plan (RP) found from that state as a relational database, which includes the current state and goal facts, the actions in the RP, and the actions' add and delete lists. We represent heuristic functions as linear combinations of generic features of the database, selecting features and weights using training data from solved problems in the target planning domain. Many recent competitive planners use RP-based heuristics, but focus exclusively on the length of the RP, ignoring other RP features. Since RP construction ignores delete lists, for many domains, RP length dramatically under-estimates the distance to a goal, providing poor guidance. By using features that depend on deleted facts and other RP properties, our learned heuristics can potentially capture patterns that describe where such under-estimation occurs. Experiments in the STRIPS domains of IPC 3 and 4 show that best-first search using the learned heuristic can outperform FF (Hoffmann & Nebel 2001), which provided our training data, and frequently outperforms the top performances in IPC 4.
---
paper_title: Learning the Behavior Model of a Robot

paper_content:

Complex artifacts are designed today from well specified and well modeled components. But most often, the models of these components cannot be composed into a global functional model of the artifact. A significant observation, modeling and identification effort is required to get such a global model, which is needed in order to better understand, control and improve the designed artifact. ::: ::: Robotics provides a good illustration of this need. Autonomous robots are able to achieve more and more complex tasks, relying on more advanced sensor-motor functions. To better understand their behavior and improve their performance, it becomes necessary but more difficult to characterize and to model, at the global level, how robots behave in a given environment. Low-level models of sensors, actuators and controllers cannot be easily combined into a behavior model. Sometimes high level models operators used for planning are also available, but generally they are too coarse to represent the actual robot behavior. ::: ::: We propose here a general framework for learning from observation data the behavior model of a robot when performing a given task. The behavior is modeled as a Dynamic Bayesian Network, a convenient stochastic structured representations. We show how such a probabilistic model can be learned and how it can be used to improve, on line, the robot behavior with respect to a specific environment and user preferences. Framework and algorithms are detailed; they are substantiated by experimental results for autonomous navigation tasks.
---
paper_title: Integrating Sample-based Planning and Model-based Reinforcement Learning

paper_content:

Recent advancements in model-based reinforcement learning have shown that the dynamics of many structured domains (e.g. DBNs) can be learned with tractable sample complexity, despite their exponentially large state spaces. Unfortunately, these algorithms all require access to a planner that computes a near optimal policy, and while many traditional MDP algorithms make this guarantee, their computation time grows with the number of states. We show how to replace these over-matched planners with a class of sample-based planners—whose computation time is independent of the number of states—without sacrificing the sample-efficiency guarantees of the overall learning algorithms. To do so, we define sufficient criteria for a sample-based planner to be used in such a learning system and analyze two popular sample-based approaches from the literature. We also introduce our own sample-based planner, which combines the strategies from these algorithms and still meets the criteria for integration into our learning system. In doing so, we define the first complete RL solution for compactly represented (exponentially sized) state spaces with efficiently learnable dynamics that is both sample efficient and whose computation time does not grow rapidly with the number of states.
---
paper_title: Reinforcement Learning: An Introduction

paper_content:

Reinforcement learning, one of the most active research areas in artificial intelligence, is a computational approach to learning whereby an agent tries to maximize the total amount of reward it receives when interacting with a complex, uncertain environment. In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications. The only necessary mathematical background is familiarity with elementary concepts of probability. The book is divided into three parts. Part I defines the reinforcement learning problem in terms of Markov decision processes. Part II provides basic solution methods: dynamic programming, Monte Carlo methods, and temporal-difference learning. Part III presents a unified view of the solution methods and incorporates artificial neural networks, eligibility traces, and planning; the two final chapters present case studies and consider the future of reinforcement learning.
---
paper_title: Integration of Online Learning into HTN Planning for Robotic Tasks

paper_content:

This paper extends hierarchical task network (HTN) planning with lightweight learning, considering that in robotics, actions have a non-zero probability of failing. Our work applies to A*-based HTN planners with lifting. We prove that the planner finds the plan of maximal expected utility, while retaining its lifting capability and efficient heuristic-based search. We show how to learn the probabilities online, which allows a robot to adapt by replanning on execution failures. The idea behind this work is to use the HTN domain to constrain the space of possibilities, and then to learn on the constrained space in a way requiring few training samples, rendering the method applicable to autonomous mobile robots.
---
paper_title: A Bayesian Approach for Policy Learning from Trajectory Preference Queries

paper_content:

We consider the problem of learning control policies via trajectory preference queries to an expert. In particular, the agent presents an expert with short runs of a pair of policies originating from the same state and the expert indicates which trajectory is preferred. The agent's goal is to elicit a latent target policy from the expert with as few queries as possible. To tackle this problem we propose a novel Bayesian model of the querying process and introduce two methods that exploit this model to actively select expert queries. Experimental results on four benchmark problems indicate that our model can effectively learn policies from trajectory preference queries and that active query selection can be substantially more efficient than random selection.
---
paper_title: Model-Based Bayesian Exploration

paper_content:

Reinforcement learning systems are often concerned with balancing exploration of untested actions against exploitation of actions that are known to be good. The benefit of exploration can be estimated using the classical notion of Value of Information - the expected improvement in future decision quality arising from the information acquired by exploration. Estimating this quantity requires an assessment of the agent's uncertainty about its current value estimates for states. ::: ::: In this paper we investigate ways to represent and reason about this uncertainty in algorithms where the system attempts to learn a model of its environment. We explicitly represent uncertainty about the parameters of the model and build probability distributions over Q-values based on these. These distributions are used to compute a myopic approximation to the value of information for each action and hence to select the action that best balances exploration and exploitation
---
paper_title: Learning action models from plan examples using weighted MAX-SAT

paper_content:

AI planning requires the definition of action models using a formal action and plan description language, such as the standard Planning Domain Definition Language (PDDL), as input. However, building action models from scratch is a difficult and time-consuming task, even for experts. In this paper, we develop an algorithm called ARMS (action-relation modelling system) for automatically discovering action models from a set of successful observed plans. Unlike the previous work in action-model learning, we do not assume complete knowledge of states in the middle of observed plans. In fact, our approach works when no or partial intermediate states are given. These example plans are obtained by an observation agent who does not know the logical encoding of the actions and the full state information between the actions. In a real world application, the cost is prohibitively high in labelling the training examples by manually annotating every state in a plan example from snapshots of an environment. To learn action models, ARMS gathers knowledge on the statistical distribution of frequent sets of actions in the example plans. It then builds a weighted propositional satisfiability (weighted MAX-SAT) problem and solves it using a MAX-SAT solver. We lay the theoretical foundations of the learning problem and evaluate the effectiveness of ARMS empirically.
---
paper_title: Learning macro-actions for arbitrary planner and domains

paper_content:

Many complex domains and even larger problems in simple domains remain challenging in spite of the recent progress in planning. Besides developing and improving planning technologies, re-engineering a domain by utilising acquired knowledge opens up a potential avenue for further research. Moreover, macro-actions, when added to the domain as additional actions, provide a promising means by which to convey such knowledge. A macro-action, or macro in short, is a group of actions selected for application as a single choice. Most existing work on macros exploits properties explicitly specific to the planners or the domains. However, such properties are not likely to be common with arbitrary planners or domains. Therefore, a macro learning method that does not exploit any structural knowledge about planners or domains explicitly is of immense interest. This paper presents an offline macro learning method that works with arbitrarily chosen planners and domains. Given a planner, a domain, and a number of example problems, the learning method generates macros from plans of some of the given problems under the guidance of a genetic algorithm. It represents macros like regular actions, evaluates them individually by solving the remaining given problems, and suggests individual macros that are to be added to the domain permanently. Genetic algorithms are automatic learning methods that can capture inherent features of a system using no explicit knowledge about it. Our method thus does not strive to discover or utilise any structural properties specific to a planner or a domain.
---
paper_title: Marvin: A Heuristic Search Planner with Online Macro-Action Learning

paper_content:

This paper describes Marvin, a planner that competed in the Fourth International Planning Competition (IPC 4). Marvin uses action-sequence-memoisation techniques to generate macro-actions, which are then used during search for a solution plan. We provide an overview of its architecture and search behaviour, detailing the algorithms used. We also empirically demonstrate the effectiveness of its features in various planning domains; in particular, the effects on performance due to the use of macro-actions, the novel features of its search behaviour, and the native support of ADL and Derived Predicates.
---
paper_title: Multi-Resolution Corrective Demonstration for Efficient Task Execution and Refinement

paper_content:

Computationally efficient task execution is very important for autonomous mobile robots endowed with limited on-board computational resources. Most robot control approaches assume a fixed state and action representation, and use a single algorithm to map states to actions. However, not all situations in a given task require equally complex algorithms and equally detailed state and action representations. The main motivation for this work is a desire to reduce the computational footprint of performing a task by allowing the robot to run simpler algorithms whenever possible, and resort to a more complex algorithm only when needed. We contribute the Multi-Resolution Task Execution (MRTE) algorithm that utilizes human feedback to learn a mapping from a given state to an appropriate detail resolution consisting of a state and action representation, and an algorithm providing a mapping from states to actions at that resolution. The robot learns a policy from human demonstration to switch between different detail resolutions as needed while favoring lower detail resolutions to reduce computational cost of task execution. We then present the Model Plus Correction (M+C) algorithm to improve the performance of an algorithm using corrective human feedback without modifying the algorithm itself. Finally, we introduce the Multi-Resolution Model Plus Correction (MRM+C) algorithm as a combination of MRTE and M+C. MRM+C learns how to select an appropriate detail resolution to operate at in a given state from human demonstration. Furthermore, it allows the teacher to provide corrective demonstration at different detail resolutions to improve overall task execution performance. We provide formal definitions of MRTE, M+C, and MRM+C algorithms, and show how they relate to general robot control problem and Learning from Demonstration (LfD) approach. We present experimental results de-monstrating the effectiveness of proposed methods on a goal-directed humanoid obstacle avoidance task.
---
paper_title: Reinforcement Learning: A Survey

paper_content:

This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning.
---
paper_title: A Model for Reasoning About Persistence and Causation

paper_content:

In this paper, we describe a model of causal reasoning that accounts for knowledge concerning cause-and-effect relationships and knowledge concerning the tendency for propositions to persist or not as a function of time passing. Our model has a natural encoding in the form of a network representation for probabilistic models. We explore the computational properties of our model by considering recent advances in computing the consequences of models encoded in this network representation.
---
paper_title: A survey of robot learning from demonstration

paper_content:

We present a comprehensive survey of robot Learning from Demonstration (LfD), a technique that develops policies from example state to action mappings. We introduce the LfD design choices in terms of demonstrator, problem space, policy derivation and performance, and contribute the foundations for a structure in which to categorize LfD research. Specifically, we analyze and categorize the multiple ways in which examples are gathered, ranging from teleoperation to imitation, as well as the various techniques for policy derivation, including matching functions, dynamics models and plans. To conclude we discuss LfD limitations and related promising areas for future research.
---
paper_title: Discriminative Learning of Beam-Search Heuristics for Planning

paper_content:

We consider the problem of learning heuristics for controlling forward state-space beam search in AI planning domains. We draw on a recent framework for "structured output classification" (e.g. syntactic parsing) known as learning as search optimization (LaSO). The LaSO approach uses discriminative learning to optimize heuristic functions for search-based computation of structured outputs and has shown promising results in a number of domains. However, the search problems that arise in AI planning tend to be qualitatively very different from those considered in structured classification, which raises a number of potential difficulties in directly applying LaSO to planning. In this paper, we discuss these issues and describe a LaSO-based approach for discriminative learning of beam-search heuristics in AI planning domains. We give convergence results for this approach and present experiments in several benchmark domains. The results show that the discriminatively trained heuristic can outperform the one used by the planner FF and another recent non-discriminative learning approach.
---
paper_title: Refining the Execution of Abstract Actions with Learned Action Models

paper_content:

Robots reason about abstract actions, such as go to position 'l', in order to decide what to do or to generate plans for their intended course of action. The use of abstract actions enables robots to employ small action libraries, which reduces the search space for decision making. When executing the actions, however, the robot must tailor the abstract actions to the specific task and situation context at hand. ::: ::: In this article we propose a novel robot action execution system that learns success and performance models for possible specializations of abstract actions. At execution time, the robot uses these models to optimize the execution of abstract actions to the respective task contexts. The robot can so use abstract actions for efficient reasoning, without compromising the performance of action execution. We show the impact of our action execution model in three robotic domains and on two kinds of action execution problems: (1) the instantiation of free action parameters to optimize the expected performance of action sequences; (2) the automatic introduction of additional subgoals to make action sequences more reliable.
---
paper_title: Robot Introspection through Learned Hidden Markov Models

paper_content:

In this paper we describe a machine learning approach for acquiring a model of a robot behaviour from raw sensor data. We are interested in automating the acquisition of behavioural models to provide a robot with an introspective capability. We assume that the behaviour of a robot in achieving a task can be modelled as a finite stochastic state transition system. Beginning with data recorded by a robot in the execution of a task, we use unsupervised learning techniques to estimate a hidden Markov model (HMM) that can be used both for predicting and explaining the behaviour of the robot in subsequent executions of the task. We demonstrate that it is feasible to automate the entire process of learning a high quality HMM from the data recorded by the robot during execution of its task. The learned HMM can be used both for monitoring and controlling the behaviour of the robot. The ultimate purpose of our work is to learn models for the full set of tasks associated with a given problem domain, and to integrate these models with a generative task planner. We want to show that these models can be used successfully in controlling the execution of a plan. However, this paper does not develop the planning and control aspects of our work, focussing instead on the learning methodology and the evaluation of a learned model. The essential property of the models we seek to construct is that the most probable trajectory through a model, given the observations made by the robot, accurately diagnoses, or explains, the behaviour that the robot actually performed when making these observations. In the work reported here we consider a navigation task. We explain the learning process, the experimental setup and the structure of the resulting learned behavioural models. We then evaluate the extent to which explanations proposed by the learned models accord with a human observer's interpretation of the behaviour exhibited by the robot in its execution of the task.
---
paper_title: Online Speedup Learning for Optimal Planning

paper_content:

Domain-independent planning is one of the foundational areas in the field of Artificial Intelligence. A description of a planning task consists of an initial world state, a goal, and a set of actions for modifying the world state. The objective is to find a sequence of actions, that is, a plan, that transforms the initial world state into a goal state. In optimal planning, we are interested in finding not just a plan, but one of the cheapest plans. A prominent approach to optimal planning these days is heuristic state-space search, guided by admissible heuristic functions. Numerous admissible heuristics have been developed, each with its own strengths and weaknesses, and it is well known that there is no single "best" heuristic for optimal planning in general. Thus, which heuristic to choose for a given planning task is a difficult question. This difficulty can be avoided by combining several heuristics, but that requires computing numerous heuristic estimates at each state, and the tradeoff between the time spent doing so and the time saved by the combined advantages of the different heuristics might be high. We present a novel method that reduces the cost of combining admissible heuristics for optimal planning, while maintaining its benefits. Using an idealized search space model, we formulate a decision rule for choosing the best heuristic to compute at each state. We then present an active online learning approach for learning a classifier with that decision rule as the target concept, and employ the learned classifier to decide which heuristic to compute at each state. We evaluate this technique empirically, and show that it substantially outperforms the standard method for combining several heuristics via their pointwise maximum.
---
paper_title: Active exploration for robot parameter selection in episodic reinforcement learning

paper_content:

As the complexity of robots and other autonomous systems increases, it becomes more important that these systems can adapt and optimize their settings actively. However, such optimization is rarely trivial. Sampling from the system is often expensive in terms of time and other costs, and excessive sampling should therefore be avoided. The parameter space is also usually continuous and multi-dimensional. Given the inherent exploration-exploitation dilemma of the problem, we propose treating it as an episodic reinforcement learning problem. In this reinforcement learning framework, the policy is defined by the system's parameters and the rewards are given by the system's performance. The rewards accumulate during each episode of a task. In this paper, we present a method for efficiently sampling and optimizing in continuous multidimensional spaces. The approach is based on Gaussian process regression, which can represent continuous non-linear mappings from parameters to system performance. We employ an upper confidence bound policy, which explicitly manages the trade-off between exploration and exploitation. Unlike many other policies for this kind of problem, we do not rely on a discretization of the action space. The presented method was evaluated on a real robot. The robot had to learn grasping parameters in order to adapt its grasping execution to different objects. The proposed method was also tested on a more general gain tuning problem. The results of the experiments show that the presented method can quickly determine suitable parameters and is applicable to real online learning applications.
---
paper_title: Robot Task Planning using Semantic Maps

paper_content:

Task planning for mobile robots usually relies solely on spatial information and on shallow domain knowledge, such as labels attached to objects and places. Although spatial information is necessary for performing basic robot operations (navigation and localization), the use of deeper domain knowledge is pivotal to endow a robot with higher degrees of autonomy and intelligence. In this paper, we focus on semantic knowledge, and show how this type of knowledge can be profitably used for robot task planning. We start by defining a specific type of semantic maps, which integrates hierarchical spatial information and semantic knowledge. We then proceed to describe how these semantic maps can improve task planning in two ways: extending the capabilities of the planner by reasoning about semantic information, and improving the planning efficiency in large domains. We show several experiments that demonstrate the effectiveness of our solutions in a domain involving robot navigation in a domestic environment.
---
paper_title: The WITAS unmanned aerial vehicle project

paper_content:

The purpose of this paper is to provide a broad overview of the WITAS Unmanned Aerial Vehicle Project. The WITAS UAV project is an ambitious, long-term basic research project with the goal of developing technologies and functionalities necessary for the successful deployment of a fully autonomous UAV operating over diverse geographical terrain containing road and traffic networks. The project is multi-disciplinary in nature, requiring many different research competences, and covering a broad spectrum of basic research issues, many of which relate to current topics in artificial intelligence. A number of topics considered are knowledge representation issues, active vision systems and their integration with deliberative/reactive architectures, helicopter modeling and control, ground operator dialogue systems, actual physical platforms, and a number of simulation techniques.
---
paper_title: A Hybrid Approach to Intricate Motion, Manipulation and Task Planning

paper_content:

We propose a representation and a planning algorithm able to deal with problems integrating task planning as well as motion and manipulation planning knowledge involving several robots and objects. Robot plans often include actions where the robot has to place itself in some position in order to perform some other action or to “modify” the configuration of its environment by displacing objects. Our approach aims at establishing a bridge between task planning and manipulation planning that allows a rigorous treatment of geometric preconditions and effects of robot actions in realistic environments. We show how links can be established between a symbolic description and its geometric counterpart and how they can be used in an integrated planning process that is able to deal with intricate symbolic and geometric constraints. Finally, we describe the main features of an implemented planner and discuss several examples of its use.
---

Title: Deliberation for autonomous robots: A survey

Section 1: Introduction
Description 1: Provide an overview of the motivation behind deliberation in autonomous robots, the challenges and requirements for deliberation, and the primary focus and aims of the survey.

Section 2: Deliberation functions
Description 2: Clarify the terminology related to deliberation functions in robotics, including the concepts of actions, plans, policies, skills, tasks, events, and the specific functions required for acting deliberately.

Section 3: Characteristics and deliberation requirements of robotics applications
Description 3: Analyze the deliberation requirements of different robotics applications, summarize the unique features that influence deliberation in various use cases, and present the implications for the design of a deliberation system.

Section 4: Design options of a deliberation system
Description 4: Discuss the critical design options for integrating planning and acting functions within a deliberation system, including the approach to modular decomposition, the balance of planning and acting, and the architectural paradigms.

Section 5: Planning techniques in action refinement
Description 5: Survey different planning techniques, including single and multiple model approaches, hierarchical strategies, and architectural paradigms, along with specific methods for integrating motion and task planning.

Section 6: Acting
Description 6: Describe the acting function and its complexities in deliberation systems, various approaches for acting (including procedure-based, automata-based, and constraint satisfaction problems-based), handling time, nondeterminism, and plan repair.

Section 7: Monitoring and Goal Reasoning
Description 7: Discuss the role of monitoring, model-based diagnosis, plan-invariant approaches, and goal reasoning in ensuring that the robot's actions remain in line with its goals and mission.

Section 8: Observing
Description 8: Review contributions related to the observing function, planning to perceive, symbol anchoring, event and situation recognition, and integrated stream-based approaches in robotics.

Section 9: Acquiring Deliberation Models
Description 9: Provide insights into the acquisition of models required for deliberation, including techniques for acquiring semantic maps, planning and acting models, and integrating learning methods in deliberation.

Section 10: Discussion and Synthesis
Description 10: Synthesize common features, significant differences, weaknesses, and open challenges among various deliberative systems, providing an evaluation of their performance and potential future research directions.

Section 11: Conclusion and Perspectives
Description 11: Conclude the survey with final remarks on the state of the art in robot deliberation, outline the primary take-home messages, and suggest future research directions to address representation, modeling, integration, and architecture issues in deliberation robotics.