Félix Ingrand

Malik Ghallab

Deliberation for Autonomous Robots: A Survey

Keywords: Robotics, deliberation, planning, acting, monitoring, observing, learning

Autonomous robots facing a diversity of open environments and performing a variety of tasks and interactions need explicit deliberation in order to fulfill their missions. Deliberation is meant to endow a robotic system with extended, more adaptable and robust functionalities, as well as reduce its deployment cost.

The ambition of this survey is to present a global overview of deliberation functions in robotics and to discuss the state of the art in this area. The following five deliberation functions are identified and analyzed: planning, acting, monitoring, observing, and learning. The paper introduces a global perspective on these deliberation functions and discusses their main characteristics, design choices and constraints. The reviewed contributions are discussed with respect to this perspective. The survey focuses as much as possible on papers with a clear robotics content and with a concern on integrating several deliberation functions.

Introduction

We are interested here in autonomous robots in industrial, service or field applications, and in robotized systems such as spacecrafts, AUVs, UAVs or self-driving cars. These systems interact autonomously with their environment through sensory-motor capabilities and may have to act deliberately in order to fulfill their mission. Acting deliberately means performing actions that are motivated by some intended objectives and that are justifiable by sound reasoning with respect to these objectives. Deliberation is any computational function required to act deliberately. From the perspective of robotics, the interest is not on deliberation per se but on acting deliberately.

Robots without autonomy do not need much deliberation. These robots extend the acting capabilities of human operators who are in charge of decision making, possibly with the support of advice and planning tools, e.g., as in surgical robotics and other teleoperated applications. Autonomous robots may or may not require explicit deliberation. Deliberation is not needed for autonomous robots working in fixed, well-modeled environments, as for most fixed manipulators in manufacturing applications. Neither would deliberation be required if all feasible missions consist of repeating a single task, e.g., as for a vacuum cleaning or a lawn-mowing robot. In these and similar cases, deliberation takes place at the design stage. Its results are directly implemented in the robot controller.

Autonomous robots facing a diversity of environments, a variety of tasks and a range of interactions cannot be preprogrammed by foreseeing at the design stage all possible courses of actions they may require. These robots need to perform some explicit deliberation. In short: autonomy plus diversity entail the need for deliberation.

Deliberative robots are desirable in applications where the environment is open-ended and largely unknown and teleoperation is constrained, as in most exploration robotics. They are needed in service applications in dynamic and changing environments with semantically rich tasks and human interactions. Domestic and personal robots are demanding in deliberation capabilities. Even for applications in closed and well structured environments with a reduced range of tasks, where engineered robotics operations are feasible and have been demonstrated successfully (e.g., in platform is a collection of devices and sensory-motor functions integrating sensing and closed-loop actuation. Choosing the appropriate command and monitoring that the context remains within a command functioning envelope is part of deliberation. The execution of a command does not need deliberation capabilities. For example, grasp(handle) is a command which, under appropriate conditions, can be directly executed by a robot platform. A plan is an organized collection of actions. A policy is universal plan, i.e., a mapping from states to actions. A skill is also an organized collection of actions. It differs from a plan in the following: its actions are at a lower level; its primitives are commands; its control structure can be richer than that of a plan. A skill is retrieved from a library of skills (hand-programmed or learned) while a plan is synthesized by a planner. A task is the specification of a mission or objectives to be achieved by the robot, in possibly different forms and abstractions levels, e.g., as goal states. An event is an occurrence of a change in the state of the robot and its environment; it can be controlled or exogenous, expected or unexpected.

Most of the literature on deliberate action is focused on planning. However, planning alone is not sufficient for achieving deliberate action. Acting is accomplished by exerting controlled forces on the environment. It is implemented at the lowest level by online processing of streams of signals, from sensors to actuators. These streams achieve feedback loops robust to the discrepancies between the world and its models. Planning, on the other hand, implements a mapping of its input, a predictive model and a problem, into an output plan expressed in some representation. Because of the limitation of predictive models and complexity constraints, planning has to admit several simplifying assumptions. As a result, a synthesized plan provides a projected course of action in some abstract representation. It is useful but rarely sufficient for acting deliberately. There is more to deliberate action than just planning in an abstract space. Several distinct functions can be required for acting deliberately. The borderlines between these functions are blurry and depend on specific representations, implementations, and architectures. However, it is conceptually clarifying to distinguish the following six deliberation functions (Fig. 1(a)):

• Planning: combines prediction and search to synthesize a trajectory in some abstract action space based on predictive models of the environment and feasible actions in order to achieve some purpose. • Acting: refines planned actions into commands appropriate for the current context and reacts to events; both refinement and reaction may rely on skills, i.e., a collection of closed-loop functions. A skill processes a sequence (or a continuous stream) of stimulus input from sensors and generates output to actuators, in order to trigger motor forces and control the correct achievement of chosen actions. • Observing: Detects and recognizes features and relations characterizing the state of the world, as well as events, actions and plans relevant for the task. Observing combines bottom-up processes, from sensors to meaningful data, 3 with top-down activities such as focus mechanisms, sensing actions and planning for information gathering. • Monitoring: Compares what is predicted regarding the robot activities to what is observed in the world. It detects and interprets discrepancies, performs diagnosis and triggers recovery actions when needed. • Goal reasoning is monitoring at the mission level. It keeps commitments and goals in perspective; it assesses their relevance from the observed evolutions from new opportunities, constraints or failures; it entails from this assessment whether some commitments should be abandoned, and when and how to update the current goals. • Learning: allows a robot to acquire, adapt and improve through experience the models needed for deliberation.

Active learning induces a robot to act deliberately in order to better learn.

These deliberation functions are interfaced with the robot's platform. The frontier between sensory-motor functions and deliberation functions varies widely depending on the complexity of the planned actions and the variability of the environment. For example, in a navigation task, motion control along a path is a sensory-motor function as long as the ground is nominal (i.e., firm, stable). When the robot gets out of the envelope of a nominal control mode, deliberation is needed. Sensory-motor functions should not be perceived in a reductionist view as simple feedback control loops. They often require feedforward prediction and monitoring of their functioning conditions (e.g., checking that the control state remains in the envelope), and complex interactions with deliberation functions.This is illustrated in neuroscience models of human and primate motion, e.g., [START_REF] Selen | Deliberation in the Motor System: Reflex Gains Track Evolving Evidence Leading to a Decision[END_REF]. Furthermore, learning capabilities change the frontier of when and where explicit deliberation is needed. E.g., in a well-known environment, a navigation skill to the same usual destination can be compiled down into a low-level control with pre-cached parameters.

Deliberation is necessarily confined within bounded computational resources. A metareasoning function can be needed for trading off deliberation time for action time, given current constraints and objectives at stake. Critical activities require careful deliberation, while less important or more urgent tasks may not need, or allow for, more than fast approximate solutions, at least for a first reaction.

Finally, note that Fig. 1(a) is not complete: Interaction, in particular human-robot interaction, is clearly a deliberation function. This is illustrated in the capabilities integrated in several systems, e.g., [193]. In some cases interaction can be used to get human help in deliberation problems, e.g., as in [START_REF] Rosenthal | Task Behavior and Interaction Planning for a Mobile Service Robot that Occasionally Requires Help[END_REF]. To keep a reasonable scope, interaction is not covered in this survey.

Characteristics and deliberation requirements of robotics applications

Deliberation is entailed by autonomy and diversity; but these are not binary properties, either true or false. When deliberation is needed, it may have different characteristics depending on the requirements of the robotics application at hand. Let us look at a few typical classes of applications. An autonomous satellite has a fairly stable and predictable environment. It has a well focused set of tasks, e.g., to use its imaging devices efficiently to respond to received queries given expected or perceived cloud coverage, and to manage its communication, processing and energy resources. It can plan and execute stable plans over long horizons. Its deployment is costly, which justifies extensive engineering for an optimized behavior, with diagnosis and self repair.

An autonomous space exploration robot, e.g., Curiosity, faces a wider diversity of tasks (navigation, observation, sampling, communication). Its environment is variable but fairly predictable; it has a low semantic complexity. The robot controls its sensory-motor devices according to its own plans. It monitors its activity, adapts and repairs its plan in unforeseen situations. It considers opportunities (e.g., an interesting rock) and manages its mission. All these deliberation functions are integrated on board and properly scheduled with respect to limited computational resources. They share models (perception models, action models, skill models, monitoring models, etc.), which need to be consistent with respect to each others. Here also the mission can afford extensive engineering and development.

A field robot for surveillance and rescue missions (Fig. 2(a)) has similar features, but it faces richer and more variable environments, less predictable and less easily modeled. Cooperation and interaction with human and other robots is an important feature in these applications. Similar remarks hold for UAVs (Fig. 2(b)) in rescue missions. Further, a UAV may have to face faster dynamics in its tasks and environments.

A self-driving car has also to deal with high dynamics, but for a very focused task in well structured environments. Critical safety issues are a strong constraint on the deliberation functions.

A service or domestic robot (Fig. 2(c)) does not have to cope with high dynamics. It is faced with very rich environments and a broad diversity of tasks. Its deliberation functions should allow it to reason about its mission (e.g., assisting the user), to plan its tasks (e.g., to serve a simple meal), to act according to its plan, refining actions into closed loop commands and reacting to events, to perceive its environment for building and maintaining its models. Engineering costs should remain low. Learning is important (e.g., adapting its skills to the particulars of the environment). Finally, man-robot interaction is essential for service and domestic robots.

Manufacturing robots used to be in protected unchanging environments, without much need for deliberation. This is progressively changing. There is a demand for very flexible robots that are easily adapted to a broad range of tasks and seamlessly integrated in any working environment. This is the more true for industrial mobile robots viewed as a worker's assistant in his daily chores. This class of applications is in many aspects similar to service and domestic robots, with more emphasis on cooperation and a more focused set of environment and tasks. We can analyze the deliberation requirements of a robotics application through eight main features: (i) how variable is the environment, (ii) how diverse is the set of tasks, (iii) how rich are the semantics, (iv) how fast are the dynamics of the environments and tasks, (v) how partially observable is the environment (vi) how high is the cost or criticality of the system, (vii) how important are interaction and cooperation with people and/or other robots, and (viii) how autonomous is the robot in carrying out its mission, e.g., choosing and committing to goals. These requirements are summarized in Table 1, considering three qualitative levels for each feature in typical applications for each class.

(i) Environment Variability (ii) Task Diversity (iii) Semantics (iv) Dynamics (v) Partial Observability (vi) Cost & Criticality (vii) Interaction & Cooperation (viii)
Application features entail constraints and requirements on deliberation functions. For example, monitoring depends on the environment variability; goal reasoning is desirable for generic missions and high degree of autonomy; safety critical applications demand formal methods and tools for the specification and verification of some of the functions to be implemented. The above table is useful for analyzing and characterizing known deliberation systems.

The surveyed systems will be characterized with respect to these features; in particular we'll refer to applications marked "h" in one or a few columns. However, most of these systems aim at being generic over a range of application classes. Even if they are motivated by and experimented with in a particular class, they propose ideas and techniques that can be relevant beyond their motivating applications. Furthermore, application features constrain deliberation functions, but they leave room for several design choices, e.g., with respect to knowledge representations used and how deliberation functions are organized. Let us discuss these options.

Design options of a deliberation system

The integration of planning and acting functions is a critical issues in the design of a deliberation system. To clarify the range of design options, let us oppose two main views emphasizing respectively planning and acting.

Emphasis on planning. This option assumes full predictive, possibly nondeterministic models of the world, including its dynamics and possible effects of exogenous events. It needs reversible models of the sensing capabilities of the robot, i.e., how reality is mapped into percepts, as well as reversible models of its actuating capabilities, i.e., how commands are mapped into forces and motion. Inverse kinematic models map desired configurations into commands achieving them; inverse sensing models map sensed features into world objects. It requires a planner that takes as input these global predictive models together with the specifications of the mission, and provides as output a plan or a policy, mapping perceived states (or beliefs) into lower level commands, possibly with some guarantee of achieving the mission or meeting some optimality criteria. Under this view, acting is a simple triggering of commands given by the planned policy: at each step the robot senses, i.e., reads the current observation variables, applying the corresponding commands specified by the policy. Note that a discrete unit time approach has to be further extended for dealing with domains involving rich temporal and real-time constraints.

This principled view inspired the design of a few early deliberation systems. It had the merit of clarifying, at the conceptual level, what was desired and how far from the ideal target the achievements were. However, the applicability of this idealistic view is limited by the low predictability of most environments, the tremendous difficulties of specifying the needed models, and the computational complexity of planning.

Emphasis on acting. Designers addressed the previous issues by the usual decomposition strategy, i.e., decompose the deliberation burden between a planning phase and an acting phase, and rely on restrictive assumptions at one end or the other. In the spectrum of possible decompositions and assumptions, classical planning is the most restrictive. It assumes an open-loop robot in a deterministic, static environment (no exogenous events), which is fully observable (for the initial state, the other states being entirely predictable). Consequently, acting has to handle nondeterministic, partially observable and dynamic environment models through closed-loop control. This option puts most of the burden of deliberating with the real world constraints (noisy sensors and actuators, imperfect models) on acting.

This view drove the design of several implementations. It remains popular (admittedly in the automated planning community, but much less in the robotics community). It led to the development of scalable classical planning techniques. But its usefulness proved to be limited by the complexity of the acting system, the narrow effectiveness of planning and the weakness of the produced plans.

Balanced decomposition. In summary, the first view relies entirely on planning, the second one depends mostly on acting without much efficient help from planning. A major design option is how to better decompose the complex deliberation problem between planning and acting, how to balance the process of choosing and undertaking actions between different levels of abstraction and granularity, from the mission level to the sensing and command level. At least three levels are needed (including the platform level in charge of executing the commands, outside of the scope of deliberation). In principle, more than three levels can be considered. Most approaches consider just three levels, corresponding to the functions we labeled as planning and acting, in addition to the platform. Planning synthesizes a trajectory in an abstract action space predicted to achieve (part of) the mission. Acting further refines each abstract action into one or several steps, called skills. Skills are plans with possibly concurrent steps whose primitives are commands (Fig. 3). Planning requires descriptive models giving the requirements and possible effects of actions (know-what). Acting requires operational models: how to refine actions, which skill to choose and when, how to react to events (know-how). This view is further developed in [START_REF] Ghallab | The actor's view of automated planning and acting: A position paper[END_REF].

Planning techniques in action refinement

A balanced decomposition should supply predictive capabilities to planning as well as to acting. Both may perform look-ahead operations, with various planning techniques. It is important to keep in mind that planning and acting may work in distinct state spaces and action spaces. However, they may both use the same representation and possibly a unified model. One may characterize ideas and approaches for specifying deliberation models for planning and acting into the following categories:

• Single model approaches rely on a unified domain model merging the know-what specification of descriptive models and the know-how specification of operational models. Abstraction and hierarchical methods are the usual tools for decomposing the problem. Planning is performed down to some level of abstraction. Abstract actions in plans are further refined into primitive commands. Techniques such as Hierarchical Task Networks, Angelic Hierarchical Planning, or Hierarchical MDPs may support these approaches. • Multiple model approaches use distinct models: an abstract descriptive model for planning and one or several operational models for acting to refine each plan step into skills. These approaches may use either (i) a uniform knowledge representation for specifying planning and acting problems at different levels of granularity, e.g., formal action languages, or (ii) heterogeneous knowledge representations at various levels, e.g., precondition-effect operators for planning, procedures or rules for acting.

The refinement from plan steps into skills involves several other considerations: • How close to the platform are the synthesized plan steps. This property is context dependent: the same action, e.g., moveto, can be a directly executable command in some context and may require further deliberation in another one. • Are the skills hand-programmed vs automatically synthesized. The synthesis of skills from the specification of sensory-motor function and/or with machine learning techniques allows for easier engineering design, for verified properties and improved integration between planning and acting. • How specific to the current mission and environment are the skills. Their adaptation may range from the choice of parameters in generic skills, to the online synthesis of skills needed for the task. • How flexible is the generated plan. A partially specified plan leaves freedom for handling some level of uncertainty and nondeterminism and adapting to the execution context.

Architectures. The choice of an appropriate architecture is another major design issue. A robot implements its deliberation online. Hence all approaches have to interleave deliberation functions through some form of nested closed loops (Fig. 1(b)): acting is performed at an inner loop level while planning is processed at an outer loop level. Various architectural paradigms have been proposed to address the integration issue (see survey [START_REF] Kortenkamp | Robotic Systems Architectures and Programming[END_REF]):

• Hierarchical architectures are probably the most widely used in robotics [START_REF] Ingrand | Decisional autonomy of planetary rovers[END_REF][START_REF] Nesnas | CLARAty and Challenges of Developing Interoperable Robotic Software[END_REF][START_REF] Doherty | A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems[END_REF][START_REF] Carbone | Model-based control architecture for attentive robots in rescue scenarios[END_REF][START_REF] Gat | On Three-Layer Architectures[END_REF][START_REF] Konolige | The Saphira architecture: a design for autonomy[END_REF]. They organize the software into a few layers with different temporal requirements and abstraction levels: a platform layer containing the sensory-motor modules, and one or several layers for deliberation functions. Often, different representations are used in these layers, which makes global consistency checking quite difficult. Their benefit is that they clearly identify and organize the sensory-motor components and the deliberation components. However, these architectures are not easily adapted to functions distributed over several layers (e.g., perception, motion planning, etc.). • Reactive architectures are composed of input/output automata implementing loops from sensors to effectors. These automata can be organized hierarchically and can inhibit or weight each other. Initial instances of reactive architectures, e.g., the subsumption architecture [START_REF] Brooks | A Robust Layered Control System for a Mobile Robot[END_REF], were mostly at the platform level without much concern for deliberation. More recent extensions have added deliberation functions (e.g., [START_REF] Lamine | History checking of temporal fuzzy logic formulas for monitoring behavior-based mobile robots[END_REF][START_REF] Pettersson | Model-free execution monitoring in behavior-based mobile robotics[END_REF]). • Teleo-reactive architectures are more recent [156,[START_REF] Finzi | Model-based Executive Control through Reactive Planning for Autonomous Rovers[END_REF]147]. They propose an integrated paradigm based on planningacting components distributed at different levels, using different horizons and time quanta. They use a single representation and provide a continuum between the components (from the high level planner dealing with mission state variables, to the low level reactor modeling the physical state variables). They offer a clear advantage with respect to the consistency of the system, but their scaling up to complex and highly dynamic environment remains an issue.

• Open architectures have recently appeared to fulfill the new needs of service and personal robots in open environments with rich semantics. Their distinctive characteristic is to allow a robot to draw data and models over the web, using in particular semantic web techniques. Several example are covered in Section 3.4, e.g., the RoboEarth, [START_REF] Waibel | RoboEarth[END_REF], KnowRob [START_REF] Tenorth | KnowRob: A knowledge processing infrastructure for cognition-enabled robots[END_REF] and CRAM [START_REF] Beetz | CRAM-A Cognitive Robot Abstract Machine for everyday manipulation in human environments[END_REF] systems, which rely on OWL, the standard Web Ontology Language.

It is important to note that the above integration and architecture design issues are relevant for all deliberation functions. Monitoring and observing, performed at an inner loop level, can benefit from automated synthesis and adaptation to the context. Goal reasoning and learning, at the outer levels, are heavily conditioned by the representations used in other functions. These issues will be further discussed in the remainder of the paper. Numerous contributions fit into the scope of this survey. A uniform level of discussion of all of them would be too long and too shallow. To present a meaningful view of the entire field ("perceiving the forest from the trees") we organized the surveyed systems into the following three clusters: • Analyzed systems (Table 2): these systems or groups of systems cover several deliberation functions; they often span over a long line of contributions, implementations and experiments that we group together; they are presented with some level of details often in several of the following sections.

Global view of surveyed systems

• Discussed systems (Table 3): these systems are more focused on a single or a few contributions; they often have narrower integration scope and experimental validation; they will be discussed briefly in a single section. • Cited systems: papers in this cluster bring interesting ideas or techniques, relevant to deliberation in robotics, but they have not been necessarily integrated or experimented with on a robot, or seem to be too close to other systems in the previous two categories to be referred to along with the discussion of other systems.

It is important to underline that no ranking is intended through this clustering, which is introduced solely for the commodity of the presentation, to help surveying a broad field into a readable picture. Tables 2 and3 summarize the main characteristics of the analyzed and discussed systems: the deliberation functions integrated, their knowledge representations, their type of robotics applications, the architectures used and additional features when relevant.

In what follows, we'll review contributions that have an emphasis on, successively, planning, acting, monitoring, observing and modeling (Sec. 3 to 7). In each of these sections, an introduction gives an overview of the corresponding function within integrated deliberation systems; a summary outlines the main features of surveyed work. A synthesis (Sec. 8) reviews the analyzed deliberation systems with respect to their main properties and application requirements.

Planning

Planning is a core deliberation function for an autonomous robot. It can be viewed as the coupling of a prediction problem and a search problem. The former refers to the capability to predict the effects of an action in some context. The latter searches through all possibilities in order to choose feasible actions and to organize them into a plan, which is foreseen, at planning time, to be feasible and to achieve a desired goal or optimize a performance criterion.

Predictive models specific to a particular type of action can be quite precise. For example, physics models with good parameter identification and state observation systems can predict precisely the effects of an action. Conversely, abstract models of the form "precondition-effect" are general enough to represent a variety of tasks but quite shallow in their predictive capabilities. Usually, abstract models are easily specified and developed, while specific models demand significant engineering efforts. This is the issue of domain-specific versus domain-independent planning, for which there is no final tradeoff. 1 The realistic option is to integrate both: domain-specific planning for the essential actions of a robot, i.e., mobility and manipulation, and domain-independent task planning to handle adaptation to a variety of tasks at a more abstract level. A few approaches, surveyed next, have been proposed to make this integration. Some models acquisition approaches (Sec. 7) further extend the scope of domain-specific techniques with reduced engineering efforts. Two considerations are particularly relevant in robotics:

• Plan revision, repair and reuse: these planning modalities are often more important in practice than the synthesis of new plans from an empty agenda. Complexity considerations in classical task planning would favor replanning to repair and reuse [START_REF] Nebel | Plan Reuse Versus Plan Generation: A Theoretical and Empirical Analysis[END_REF]. But this is not supported by other considerations such as acting costs, ongoing commitments of a robot and plan stability issues [START_REF] Fox | Plan stability: Replanning versus plan repair[END_REF][START_REF] Tonino | Plan coordination by revision in collective agent based systems[END_REF]212]. • Simulation and sampling: "precondition-effect" representation of actions tends to be shallow. Simulation systems of robots and environments, when available, can be used to achieve reliable predictions, in particular with sampling techniques. This is illustrated in the integration of motion planning to task planning, e.g., [START_REF] Burfoot | RRT-plan: a randomized algorithm for strips planning[END_REF][START_REF] Alcázar | Adapting a Rapidly-Exploring Random Tree for Automated Planning[END_REF], in probabilistic planning techniques, and in reinforcement learning (Sec. 7.2). Several other options arise for the design of a robot planner:

• open-loop versus closed-loop plans: the latter are conditional plans involving perception (i.e., do this, then, depending on the perceived state of the world, do that or this), while the former are unconditional plans. In the open-loop case, the designer is generally aware that the predictions of a deterministic model and the assumption of a static environment do not hold. But the designer trusts the monitoring and acting functions to deal with and correct small variations between predicted and observed states, and replanning to handle more significant ones.

• plan horizon: it can be an indefinite horizon of a one-shot plan that achieves the objectives, a receding horizon partial plan that will be further progressed while acting, or an infinite horizon policy that optimizes the robot behavior. In many cases, the application domain determines the choice. For example, an infinite horizon approach is adequate for maintaining a property in a dynamic environment, e.g., keeping a room clean; while a moving target mission is better addressed with a receding horizon method. • deterministic versus nondeterministic models: the latter predict alternative effects of an action and, in the probabilistic case, take into account their likelihood. Nondeterministic planning generates policies, which are conditional closed-loop plans. Over the past decades, domain-independent task planning has achieved tremendous progress, mostly on the search problem while keeping the prediction problem quite simple with the precondition-effect model. A speed up of a few orders of magnitude in the performance of classical planners has been achieved; numerous extensions to relational representations and improvements in algorithms for non-deterministic, probabilistic and other non-classical planning have been developed. A survey of task planning is not the purpose of this section (see [START_REF] Geffner | A Concise Introduction to Models and Methods for Automated Planning[END_REF][START_REF] Ghallab | Automated Planning: Theory and Practice[END_REF][START_REF] Wilkins | Practical Planning. Extending the Classical AI Planning Paradigm[END_REF][START_REF] Yang | Intelligent Planning: A Decomposition and Abstraction Based Approach[END_REF]). We will focus instead on problems and approaches for the integration of planning in a robot deliberation system. In addition to the integration of motion and manipulation planning to task planning, robotics stresses particular issues such as handling time and resources, uncertainty, partial knowledge and open domains. The rest of the section surveys a few approaches to these problems, summarized in Table 4.

Motion and Task Planning

Robots have to plan precise movements of their wheels, legs, arms, and joints. Motion planning and task planning are different problems that use distinct representations and search techniques. The latter has been mostly considered by the AI community, while the former has been studied by the robotics and computational geometry communities. In simple cases one can decouple the two problems: task planning produces a high level plan whose steps requiring motions can be handled by a specific motion planner. Most of the systems in Table 2 this decoupled approach. When the mission is more complex or the environment more constrained, this decomposition is no longer possible: the motion constraints must be taken into account early in the task planning phase. Let us briefly present the state of the art in motion and manipulation planning and review a few approaches (listed in Table 5) integrating it with task planning.

Feasible motions Search

Planned Estimated Both

State space

Asymov [START_REF] Cambon | A Hybrid Approach to Intricate Motion, Manipulation and Task Planning[END_REF] CPMP [START_REF] Choi | Combining Planning and Motion Planning[END_REF] I-TMP* [START_REF] Hauser | Integrating task and PRM motion planning: Dealing with many infeasible motion planning queries[END_REF] CTAMP [START_REF] Bidot | Geometric Backtracking for Combined Task and Path Planning in Robotic Systems[END_REF] SamplSGD [START_REF] Zickler | Efficient physics-based planning: sampling search via non-deterministic tactics and skills[END_REF] Hierarchical AHP [START_REF] Wolfe | Combined task and motion planning for mobile manipulation[END_REF] Kaelbling [START_REF] Kaelbling | Hierarchical task and motion planning in the now[END_REF] Table 5: Integrated motion and task planning, (*) with online planning and acting

Motion and manipulation planning are key capabilities for a robot, requiring specific representations for geometry, kinematics and dynamics. Probabilistic Roadmaps (PRM) and Rapidly-Exploring Random Trees (RRT) are well developed and mature techniques for motion planners that scale up efficiently and allow for numerous extensions [START_REF]Planning Algorithms[END_REF]. The basic idea is to randomly sample the configuration space (C-space) of the robot (i.e., the vector space of the robot's kinematics parameters) into a graph where each vertex is a point in the space denoted C f of free configurations (away from obstacles), and each edge a direct link in the free space between two free configurations. Initial and goal configurations are added to this graph, between which a path is computed. This path is then transformed into a smooth trajectory. Manipulation planning requires finding feasible sequences of grasping positions, each of which is a partial constraint on the robot configuration that changes its kinematics [START_REF] Siméon | Manipulation Planning with Probabilistic Roadmaps[END_REF]. Many other open problems remain in motion and manipulation planning, such as dynamics and stability constraints, e.g., for a humanoid robot [START_REF] Kanoun | Planning foot placements for a humanoid robot: A problem of inverse kinematics[END_REF], or visibility constraints, e.g., to allow for visual servoing [START_REF] Chaumette | Visual Servoing and Visual Tracking[END_REF].

Task planning and motion/manipulation planning have been brought together in a few approaches. The CPMP planner [START_REF] Choi | Combining Planning and Motion Planning[END_REF] builds a task planner domain from a tree constructed by a motion planner in the robot C-space. It then plans symbolically with a state space planner and converts back the found plans into the C-space.

The Asymov planner [START_REF] Cambon | A Hybrid Approach to Intricate Motion, Manipulation and Task Planning[END_REF] combines a state-space task planner with a search in the motion planner configuration space. It defines places which are both a state in the task planner space, and cover a range of free configurations in C f . These places define bridges between the two search spaces. These two spaces are not explicitly constructed, but for each generated state of the task plan, the system checks that at least one configuration C f is reachable. The state-space search prunes a state whose corresponding set of free configurations does not meet current reachability conditions. This approach has also been extended to manipulation planning and to multi-robot planning for joint activities such as two robots assembling a table in a cluttered environment.

The integration of motion to task planning is also explored in [START_REF] Wolfe | Combined task and motion planning for mobile manipulation[END_REF] with Angelic Hierarchical Planning (AHP). AHP plans over sets of states with the notion of reachable sets of states. These sets are not computed exactly, but bounded, e.g., by a subset and a superset, or by an upper and a lower bound cost function. These costs are obtained by simulations of the basic activities, including motion activities, for random values of the state variables. A high-level task has several possible decompositions into primitives. The set of possible decompositions of a plan containing several high-level tasks is the Cartesien product of all possible decompositions of its actions. It is not necessary to ensure that all decompositions are feasible. A plan is acceptable if it has at least one feasible decomposition. Decomposition of a task can be postponed, e.g., until the acting time for the achievement of that task. At that point, the robot chooses a feasible decomposition (hence the reference to an angelic semantics of nondeterminism).

A different coupling of a hierarchical task planner to fast geometric suggesters is developed in [START_REF] Kaelbling | Hierarchical task and motion planning in the now[END_REF]. These suggesters are triggered when the search in the decomposition tree requires geometric information. They do not completely solve the geometric problem, but they provide information that allows the symbolic search to continue up to a leaf of the tree. The system alternates between symbolic planning phases and the real execution of geometric actions in the environment. Planning proceeds while acting. This allows the task planner to call the geometric planner (not the suggesters) in a fully known state. Thus, this approach relies on two strong assumptions: the geometric preconditions of the tasks can be calculated quickly and efficiently (by the suggesters), the subgoals resulting from a task decomposition must be executed in sequence (no parallelism). The authors acknowledge that their system is not complete, and that the subgoals sequencing assumption requires actions to be reversible at a reasonable cost. Yet, for problems where these assumptions are satisfied, the system is able to quickly produce correct plans.

The geometric backtracking approach of [START_REF] Bidot | Geometric Backtracking for Combined Task and Path Planning in Robotic Systems[END_REF] and subsequent work on a system called CTAMP relies on the automated synthesis of geometric constraints from the task plan and their propagation, as linear programs, to filter out samples in the configuration space. Remaining configurations, if any, are further searched with respect to sufficient conditions of inverse kinematics, collision detection and motion planning to make sure that each step specifies collision free and kinematically achievable poses with respect to the previous ones. The approach has been developed for manipulation problems and experimented with the dual arm Justin robot.

PRM and RRT motion planners used in cited approaches solve feasible queries very efficiently, but they handle infeasible queries with a cutoff time that can be a serious drawback in constrained environments. The incremental algorithm I-TMP [START_REF] Hauser | Integrating task and PRM motion planning: Dealing with many infeasible motion planning queries[END_REF] integrates closely task and motion planning with adaptive allocation of computational time where it can be most useful. It has been tested on multi leg robots navigating on rough terrain.

Let us also mention the physics-based technique of [START_REF] Zickler | Efficient physics-based planning: sampling search via non-deterministic tactics and skills[END_REF] which couples a physics engine simulator with RRT-like search methods for planning the interactions of a robot with non actuated bodies with varying degrees of controllability in order to reach some goals. The approach was tested in minigolf and robot soccer domains. Similarly, the SamplSGD system [START_REF] Plaku | Sampling-based Motion Planning with Symbolic, Geometric, and Differential Constraints[END_REF] adds differential constraints to the symbolic and geometric specifications of a planning domain. It relies on sampling techniques to selectively explore the continuous configuration and dynamics space. Task planning provides discrete actions and regions of the continuous space that sampling based motion planning can explore. The two planners interact through estimates on the utility of each action, which are computed by reinforcement learning techniques. SamplSGD was tested on simulated manipulation tasks.

Temporal Planning

Most robotics applications require explicit time models to handle durative actions, concurrency, synchronization with exogenous events and other robots, and temporal constraints, possibly with flexible lower and upper bounds.

Various approaches manage explicit time representations for planning. Several planners extend state-based representations with durative actions (e.g., TGP [START_REF] Smith | Temporal Planning with Mutual Exclusion Reasoning[END_REF], VHPOP [START_REF] Younes | VHPOP: Versatile heuristic partial order planner[END_REF] or Crickey [START_REF] Coles | Planning with Problems Requiring Temporal Coordination[END_REF]). A few of them can manage concurrency, or even linear continuous change (COLIN [START_REF] Coles | COLIN: Planning with Continuous Linear Numeric Change[END_REF]), or can plan and repair in real-time [START_REF] Ruml | On-line planning and scheduling: An application to controlling modular printers[END_REF] . However, temporal planners that rely on timelines, i.e., partially specified evolution of state variables over time, are more flexible in the integration of planning and acting and, in most cases, more expressive, e.g., allowing the reference to instants beyond starting and ending time of actions. These planners implement plan-space search algorithms more often then state-space techniques. Their usual representation ingredients are:

• temporal primitives: time-points or intervals (tokens),

• state variables, possibly parametrized, e.g., position(object32), and rigid relations, e.g., connected(loc3, room5), invariant over time, • assertions on the persistence of the value of a state variable over time, or the discrete or continuous change of values,

• temporal constraints: Allen interval relations [START_REF] Allen | Towards a General Theory of Action and Time[END_REF] or Simple Temporal Networks [START_REF] Dechter | Temporal constraint networks[END_REF] over time-points,

• atemporal constraints on the values and parameters of state-variables. The chronicles of the IxTeT planner [START_REF] Ghallab | Representation and Control in IxTeT, a Temporal Planner[END_REF] illustrate such a representation. A chronicle defines time-points, temporal constraints between its time-points, changes in the values of state variables (denoted event), persistence of these values over time (denoted hold), and atemporal constraints over state variables parameters and values (see Fig. 4).

Other planners such as PS, the DS1/RAX planner [START_REF] Jónsson | Planning in Interplanetary Space: Theory and Practice[END_REF], EUROPA [START_REF] Frank | Constraint-Based Attribute and Interval Planning[END_REF] and APSI [START_REF] Fratini | APSI-based deliberation in Goal Oriented Autonomous Controllers[END_REF], rely on a similar representation with timelines and tokens representing changes and persistences of state variables values over time intervals. Some of these timelines are directly connected to actions and percepts (to integrate perception). Temporal constraints in planning operators use the symbolic interval algebra [START_REF] Allen | Towards a General Theory of Action and Time[END_REF] (see Fig. 5). Simple atemporal constraints over state variables are also allowed. Goals are expressed as an unexplained assertions, i.e., required state-variable values to be accounted for by the planner through actions. Preconditions and predicted effects are expressed as assertions constrained with respect to the duration of actions.

Planning proceeds in the plan-space by detecting flaws, i.e., unexplained changes and possible inconsistencies, and repairing them through additional actions and constraints. It makes use of various heuristics, constraint propagation and backtrack mechanisms. It produces partially specified plans, that have no more flaws but still contain constrained but non-instantiated temporal and atemporal variables. This least commitment approach allows for some flexibility to adapt to the execution context. Some planners can handle bounded planning time and take it into account together with the execution horizon during the planning process.

Probabilistic Planning

Markov Decision Processes (MDPs) offer a classical framework for planning with uncertainties and probabilistic effects. A planner computes an optimal policy, i.e., a universal plan mapping states into applicable actions. The classical framework considers infinite horizon problems, e.g., to maintain a property in dynamic environment. It can be extended to partially observable systems (POMDPs). It is effective as long as the state space and the cost and probability parameters can be entirely acquired and made explicite, and, for POMDPs, remains of small size. 2However, most deliberation problems in robotics do not allow for an explicit enumeration of their state space, and hence cannot afford a universal plan. Fortunately, many problems are focused on reaching a goal from some initial state. Heuristic search algorithms for Stochastic Shortest Path (SSP) problems [START_REF] Mausam | Planning with Markov Decision Processes: An AI Perspective[END_REF] with factorized and hierarchical representations [START_REF] Boutilier | Decision-Theoretic Planning: Structural Assumptions and Computational Leverage[END_REF] address this class of problems. They offer probabilistic approaches to robotics deliberation that still need to be developed and deployed on robots, beyond classical test problems.

An SSP problem focuses on a partial policy, closed for the initial state s 0 (i.e., a policy π defined on all states reachable from s 0 by π), terminating at goal states. An SSP is the equivalent for And/Or graphs to path search problems in deterministic graphs. For very large implicit search spaces with sparse models (few applicable actions per state, few nondeterministic effects per action, including deterministic actions), a significant scaling up with respect to classical dynamic programming methods can be achieved with heuristics and sampling techniques [START_REF] Mausam | Planning with Markov Decision Processes: An AI Perspective[END_REF].

Most heuristic search algorithms for SSPs are based on a two steps schema, called Find&Revise: (i) Find a pending state s among the descendant of s 0 reachable with current policy, and (ii) Revise the estimated value and policy of s with the so-called Bellman update. A state s is pending when it needs to be expanded or when its value and policy need to be updated towards the best (or good) policy from s. That framework can be implemented in different ways, e.g., with a best-first search, as in AO*, LAO* [START_REF] Hansen | LAO*: A heuristic search algorithm that finds solutions with loops[END_REF] and their extensions, with a depth-first iterative deepening search, as in LDFS [START_REF] Bonet | Learning in Depth-First Search: A Unified Approach to Heuristic Search in Deterministic, Non-Deterministic, Probabilistic, and Game Tree Settings[END_REF], or with a random walk search, as in RTDP [START_REF] Barto | Learning to Act Using Real-Time Dynamic Programming[END_REF], LRTDP [START_REF] Bonet | Learning Depth-First Search: A Unified Approach to Heuristic Search in Deterministic and Non-Deterministic Settings, and Its Application to MDPs[END_REF] and their extensions.

These algorithms assume SSP problems with a proper policy closed for s 0 (i.e., one that reaches a goal with probability 1), and any improper policy has infinite cost. A generalization of SSPs to relax this last assumption allows to seek a policy that maximizes the probability of reaching a goal state, a very useful and desirable criteria [START_REF] Kolobov | Heuristic search for generalized stochastic shortest path MDPs[END_REF]. Other issues, such as dead-ends (states from which it is not possible to reach a goal) have to be taken care of, in particular in critical domains [START_REF] Kolobov | SixthSense: Fast and Reliable Recognition of Dead Ends in MDPs[END_REF]. Heuristic search algorithms in SSPs are more scalable than dynamic programming, but they still cannot address large domains, unless these domains are carefully engineered and decomposed.

Various sampling and approximation techniques offer alternative approaches to further scale up probabilistic planning. Among these approaches, determinization techniques transform each non-deterministic action into several deterministic ones (the most likely or all possible ones), then it plans deterministically with these actions, online and/or offline. For example, SSiP [START_REF] Trevizan | Short-sighted stochastic shortest path problems[END_REF] combines replanning when needed with planning over a parametrized horizon of at least k steps to be guaranteed without replanning. RFF [START_REF] Teichteil-Königsbuch | Incremental plan aggregation for generating policies in MDPs[END_REF] generates an initial deterministic plan, then it considers a fringe state along a non-deterministic branch of that plan and, as long as the probability to reach that state is above some threshold, it extends it with another deterministic plan toward a goal or an already solved state. Similar ideas are developed in sampling approaches. One of their advantages is the capability to work without a priori estimates of the probability distributions, as long as the sampling is drawn from these same distributions. Several strategies have been designed for the control of the search, e.g., sample more sparsely at the deeper level of the look-ahead tree. Bounds on the approximation quality and the complexity of the search have been obtained, with good results on various adaptations and extensions of the LRTDP and UCT algorithms, e.g., [START_REF] Kearns | A sparse sampling algorithm for near-optimal planning in large Markov decision processes[END_REF][START_REF] Busoniu | Optimistic planning for sparsely stochastic systems[END_REF][START_REF] Kolobov | LRTDP vs. UCT for Online Probabilistic Planning[END_REF].

Although MDPs are often used in robotics at the sensory-motor level, in particular within reinforcement learning approaches (Sec. 7.2), SSP techniques are not as widely disseminated at the deliberative planning and acting level. An interesting example is the sparse MDP planner of [START_REF] Likhachev | Planning for markov decision processes with sparse stochasticity[END_REF] that couples SSP with classical planning: when most actions are deterministic but of a few that are probabilistic, it searches through and reduces the deterministic parts of the planning space into a compressed MDP. The approach has been tested in a robotics exploration problem.

Planning in Open Domains

Most classical planners rely on the closed-world assumption: a fact not explicitly stated is false. 3 This assumption allows for a concise description of states and efficient computation of state-transitions. But it is too restrictive and seldom acceptable in robotics. A few techniques relax this assumption, e.g., planning with state-variables and timelines allows for partially specified instances of a domain. But other issues remain open, among them the following:

• Planning with respect to domain objects and properties that are unknown when planning starts but that can be discovered at acting time, in particular through planned information gathering actions. These new facts will be used to further refine the remainder of the plan. • Allow the planner to query databases for facts it needs specifically to address a given planning problem, or to query knowledge bases for additional models of its environment that are relevant to the task at hand. The former issue of planning with information gathering is studied by several authors with conditional plan approaches, as in the PKS [START_REF] Petrick | Extending the Knowledge-Based approach to Planning with Incomplete Information and Sensing[END_REF] system. The continual planning approach of MAPL [START_REF] Brenner | Continual planning and acting in dynamic multiagent environments[END_REF] postpones part of the planning process. In its place, it introduces information gathering actions to later develop the missing parts of the plan. To this end, the planner uses assertions that abstract actions to be refined later, after information gathering. This mixed planning/acting approach is well adapted to dynamic environments where planning for subgoals that depend of yet unknown states can be delayed until the required information is available (through properly planned information gathering actions). The approach has been extended to multi-robot distributed planning/acting. It has been tested in simulated navigation problems.

The latter issue of acquiring additional models and data at planning time is being addressed by a growing number of projects. The driving idea is to enrich a robot deliberation system with functionalities akin to semantic web, using a domain ontology associated to some reasoning capabilities. For example, the ObjectEval system of [START_REF] Samadi | Using the web to interactively learn to find objects[END_REF] acquires from the web statistics about possible locations of objects of different classes. It uses them in a utility function for finding and delivering objects in an office environment. Other approaches use Description Logic (DL), a fragment of first-order logic, to handle statements about objects, properties, relations and their instances with inference algorithms for querying large stores of data and models over the web. Most implementations rely on OWL, the standard Web Ontology Language. OWL handles an open-world representation where facts can be true, false or unknown.

The approach of [START_REF] Hartanto | Fusing DL Reasoning with HTN Planning[END_REF] couples DL with an HTN planner. A robot requires a large store of knowledge about its environment, only a small part of which is relevant to a given planning problem. DL allows the planner to synthesize a compact equivalent HTN problem focused on this relevant part. The corresponding ontology includes HTN planning concepts (i.e., tasks, methods, states, etc.) as well as domain concepts. The approach was tested on navigation problems. The RACE project [START_REF] Rockel | An Ontology-Based Multi-Level Robot Architecture for Learning from Experiences[END_REF] designs a service robot with learning capabilities whose entire architecture is built around an open DL database, akin to a "Blackboard" architecture [START_REF] Hayes-Roth | A Blackboard Architecture for Control[END_REF]. This feature is used to combine data about low-level robot activities, needed in particular for learning, with higher-level semantic descriptions provided by the ontology. The system supports a PR2 platform performing the tasks of a waiter.

The Open Robot Ontology (ORO) system of [START_REF] Lemaignan | ORO, a knowledge management platform for cognitive architectures in robotics[END_REF] was motivated more by extending the robot's knowledge base then by improving the performance of its planners. ORO is built with the same OWL representation and reasoner as the previous systems. It offers queries and updates of a knowledge base about the environment. ORO services are used by various components of the robot, in particular by a situated dialogue management system and a planner. ORO has been tested with a few platforms for service robotics tasks (illustrated in Fig. 2(c)).

The RoboEarth and KnowRob projects [START_REF] Waibel | RoboEarth[END_REF][START_REF] Tenorth | KnowRob: A knowledge processing infrastructure for cognition-enabled robots[END_REF] aim at allowing robots having different platforms to share and reuse knowledge over the network for the purpose of performing new tasks and speeding up learning and adaptation. An OWL open source library stores shared models of objects (e.g., images, CAD models), environments (e.g., maps and object locations), and actions (e.g., action recipes and skills) together with their relations and properties in a general ontology. Each robot is endowed with means for querying and updating this database, as well as adapting its models. The concept was tested on a few demonstrators for exploring a maze using different platforms sharing maps and path information, for serving a drink or opening drawers without a priori knowledge of the environment setting.

Summary

Motion planners are essential in robotics; they are available in most of the surveyed systems. Task planning is also needed for deliberation. The assumption of independence between task and motion planning does not hold in tightly coupled problems. The state of the art for integrating task planning to motion planning, and more generally to other domain-specific planners, is progressing significantly.

In addition to space, time plays an important role in planning; it allows for concurrent activities and synchronization. Most of the task planners in our analyzed systems take into account time, often with an explicit representation with state variables over timelines. Constraint programming and plan space search are also quite popular in reviewed systems. As we will see next, they offer some advantages in the integration of planning and acting and in plan repair.

The state of the art in nondeterministic and probabilistic planning has progressed. These approaches are appealing for addressing the uncertainty in knowledge and world variability. For the moment, they are mostly developed at the sensory-motor level and, to some extent, at the acting level (see Sec. 4.6). The bottleneck for their deployment in deliberation planning mainly is the modeling effort and the complication of integrating space and time.

We described planning as the coupling of a prediction problem and a search problem. Significant research efforts are devoted to the latter. More investigation in the former is needed for improving the predictive capabilities of models used by planners. Simulation-based planning appears to be a promising option. Open domain planning also has a large potential and should be more widely deployed in robotics deliberation systems.

Acting

Planning is easily specified as an offline predictive function, decoupled from the intricacies of the executing platform. In contrast, acting is more difficult to define as a deliberation function. The frequent reference to execution control is often too reductive. There is much more to it than triggering abstract actions prescribed by a plan. Acting has to handle noisy sensors, unreliable actuators and imperfect models. It requires nondeterministic, partially observable and dynamic environment models, dealt with through closed-loop commands. Acting has often a central role in deliberation. It has to carry out in particular the following functions:

• Refinement: plan steps (i.e., actions) given by a task planner are seldom directly executable as robot commands. An action like open(door1) is a primitive step for a planner but requires significant deliberation for its achievement. The refinement process is context dependent. It relies on lower-level models, that we called skills, appropriate for the context. Skills can be chosen and adapted from a library or synthesized online. The skill into which an action is refined may change during execution. For example several navigation skills may offer different localization or motion control capabilities adapted to different context; hence the goto(room1) action can be refined into a sequence of several navigation skills. Acting also has to consider alternative refinements in case of failure.

• Reaction to events: there are expected events, for plan synchronization purposes, or unexpected events. Events can be dealt with locally with appropriate skills. They may have negative or positive consequences for the current plan or even for the current goal. They may require plan repair in addition to the local reaction. • Instantiation: unless synthesized online, acting skills are applicable to a range of situations. Their models can use non instantiated variables whose value can be chosen at execution time or observed in the environment. These values get propagated down to commands with respect to the perceived context. • Time management: acting is performed online. The dynamics of the environment has to be dealt with. Adequate responses must be given in a timely manner. There are issues of time as a resource with deadlines, durations and deliberation time. There are also issues of rendezvous, synchronization with events, and time constraints.

• Nondeterminism: Applying an action may result in several possible states. The occurrence of exogenous events in a dynamic environment is seldom deterministically predictable. Further, not all relevant state variables are observable with certainty. We will see that some of the presented techniques can handle sources of nondeterminism. • Plan repair: As introduced in Section 3, plan repair is clearly a planning activity. Yet, it is strongly linked to acting which triggers repair or replanning in the appropriate conditions with respect to committed execution. Acting has to support this feature.

The overlap between planning and acting leaves numerous design options open. A few authors develop a framework where both deliberation functions are handled in the same search space, with the same techniques. However, most approaches address the distinct requirements of planning and acting with decomposition scheme (Fig. 3) where planning reasons with abstract descriptive models of actions while acting uses operational models to refine actions into procedures, called skills, that are further refined into commands. This decomposition scheme may rely on distinct knowledge representations, e.g., STRIPS operators for the former combined with PRS [START_REF] Ingrand | PRS: a high level supervision and control language for autonomous mobile robots[END_REF] or RAP [START_REF] Firby | An investigation into reactive planning in complex domains[END_REF] procedures for the latter. In some cases a single representation is used for both planning and acting, e.g., in Golog [START_REF] Levesque | GOLOG: A logic programming language for dynamic domains[END_REF], IDEA [START_REF] Muscettola | A Unified Approach to Model-Based Planning and Execution[END_REF] and T-REX [147]. Other approaches use a single representation but at different levels of abstractions and refined appropriately, as in Hierarchical MDPs [START_REF] Hauskrecht | Hierarchical solution of Markov decision processes using macro-actions[END_REF] for example.

Other important issues are how the acting skills are acquired, either synthesized automatically, hand written, or obtained through a learning mechanisms, and how they are used, as directly executable programs or as specification models from which further deliberation is performed. Acting knowledge has also to be checked for consistency with respect to planning models. Some skill formalisms are more amenable to validation and verification than others, hence more adapted to applications where criticality is high (see Table 1.)

Various computational techniques can be used to design a deliberate acting system. We propose to organize these approaches into five categories. Their main features are summarized in Table 6.

Direct mapping of plan steps into robot commands

This class of approaches assumes that planned steps are directly executable as commands by the platform. Often, there is an elaborate processing at the platform level, hard coded in the functional layer of the robot, but there is no explicit deliberation for action refinement. Acting is focused mostly on reacting and, in some cases monitoring.

Planex [START_REF] Fikes | Monitored Execution of Robot Plans Produced by STRIPS[END_REF] is one of the earliest acting system, deployed on the Shakey robot. Plans produced by STRIPS are executed without any action refinement: Planex directly maps plan steps into commands. It assumes a correct and complete state update after each action is executed, from which it detects failures but also opportunities for pursuing the plan. It relies on triangle tables which have been advocated for learning and generalizing a collection of plans, and as well as for programming with a hierarchical collection of actions. [START_REF] Schoppers | Universal plans for reactive robots in unpredictable environments[END_REF] extended the idea with universal plans that define a class of plans applicable in a set of states leading to a particular goal. This class of approaches handles in a restricted way nondeterminism and repair, as it may adapt the plan when the observed state is not the nominal one.

One of the problems with these and similar approaches is their lack of robustness in the interaction with the physical world. They remain at a high level of abstraction, assuming full observability, no uncertainty on observations, yet they manage a limited form of nondeterminism due to exogenous events.

Acting with procedure-based approaches

In procedure-based approaches, action refinement is done with handwritten skills similar to imperative programs. RAP (Reactive Action Package) [START_REF] Firby | An investigation into reactive planning in complex domains[END_REF] is one of the earliest work on acting and reactive planning (i.e., without search). Each skill is in charge of satisfying a particular goal, corresponding to a planned action. Deliberation chooses the CPEF (Continuous Planning and Execution Framework) [START_REF] Myers | CPEF: Continuous Planning and Execution Framework[END_REF], which combines PRS and Sipe [START_REF] Wilkins | Practical Planning. Extending the Classical AI Planning Paradigm[END_REF].

Most procedure-based approaches focus on the refinement and instantiation functions. They fill the gap between plan steps and robot commands. Skills allow for control structures (conditional, loop, recursion) and are hand written; they are easy to use and deploy, but difficult to formally validate or verify. But of TCA/TDL, which offers synchronization mechanisms, these approaches do not handle temporal reasoning but can offer real-time capabilities.

Acting with automata and Petri net approaches

Robots integrate several concurrent sensory-motor processes that require strong and well defined synchronization and sequencing. Quite naturally, Petri nets have been used for that in a few experiments. In [START_REF] Wang | A Petri-net coordination model for an intelligent mobile robot[END_REF] Petri nets model the various functional components, the proper order of execution among them as well as the required coordination. The model can be used in simulation mode for verification and performance testing. Similarly, [START_REF] Barbier | Implementation and Flight testing of an onboard architecture for mission supervision[END_REF] proposes to use Petri nets to model hierarchically the supervision procedures of a UAV. It provides a verification tool to check for deadlocks and unwanted loops in the model. In [START_REF] Ziparo | Petri net plans[END_REF], the authors propose Petri net plans for high level programming of multi-robot systems. They validate some properties of the system with reachability analysis and deadlock search.

It seems quite natural to refine an abstract action into a graph of elementary states and label the edges with sensorymotor signals and commands. Finite State Automata (FSA) have been studied as acting models. For example, FSA have been used jointly with IxTeT in [START_REF] Chatilla | Integrated planning and execution control of autonomous robot actions[END_REF]. Each IxTeT planned action has a corresponding FSA written by the programmer which specify the different states the action can be in. Acting controls the transitions between the states of the FSA according to external or internal events, and checks that they are consistent with the plan being executed. These transitions trigger lower level actions which are refined using scripts and executed within an activity tree.

PLEXIL, a language for the execution of plans, illustrates a representation where the user specifies nodes as computational abstractions [START_REF] Verma | Plan execution interchange language (PLEXIL) for executable plans and command sequences[END_REF]. A node can monitor events, execute commands or assign values to variables; it may refer hierarchically to a list of lower level nodes. Execution can be controlled by a number of constraints (start, end), guards (invariant) and conditions. PLEXIL focuses on acting. But of the input plan, it and does not share data with the planner. It has been developed for space applications and used with planners such as CASPER.

SMACH, the ROS execution system, also implements an automata-based approach [START_REF] Bohren | Towards autonomous robotic butlers: Lessons learned with the PR2[END_REF]. The user writes a set of hierarchical state machines. Each state corresponds to the execution of a particular component of the robot. ROS actions, 4 services and topics are associated to the state; execution proceeds to the appropriate state according to returned values. The global state of the robot corresponds to the Cartesian product of the states of each components. Acting knows exactly in which state the system is, which eases deployment and monitoring. The interface with ROS actions, services and topics is very natural, but the semantics of constructs available in SMACH is limited for reasoning on goals and states.

All Petri net and Automata approaches address the functions of refinement, instantiation and time management (invariant constructs in the terminology of automata). Cited systems do not handle explicit time, nondeterminism, or plan repair (apart from local failure management). All rely on hand specified skills. Unlike the Procedure-based approaches, Automata and Petri net approaches allow for formal analysis (e.g., reachability and dead locks), which can be critical for the specification and the verification of acting models.

Logic-based approaches

A few systems try to overcome the tedious engineering bottleneck of detailed hand specification of skills by relying on logic inference mechanisms for extending high-level specifications. Typical examples are the Temporal Action Logic (TAL) approach (to which we will come back in Sec. 5) and the situation calculus approach. The latter is exemplified in GOLEX [START_REF] Hähnel | GOLEX-bridging the gap between logic (GOLOG) and a real robot[END_REF][START_REF] Burgard | The interactive museum tour-guide robot[END_REF], an execution system for the GOLOG planner. GOLEX was deployed on museum personal tour guide robot, and a robot serving coffee in an office environment.

In GOLOG and GOLEX the user specifies respectively planning and acting knowledge in the situation calculus representation. GOLEX provides Prolog hand programmed "exec" clauses which explicitly define the sequence of commands a robot has to execute. It also provides monitoring primitives to check the effects of executed actions. GOLEX executes the plan produced by GOLOG but even if the two systems rely on the same logic programming representation, they remain completely separated, limiting the interleaving of planning and acting.

The Platas system [START_REF] Claßen | Platas-Integrating Planning and the Action Language Golog[END_REF] relies on GOLOG with a mapping between the PDDL langage and the Situation Calculus. It either uses GOLOG's internal iterative deepening planner or an external PDDL planner to produce a plan which is then executed by GOLEX. The Readylog language (Real-time and dynamic GOLOG) [START_REF] Ferrein | Logic-based robot control in highly dynamic domains[END_REF], a derivative of GOLOG, combines planning with programming. Instead of planning with GOLOG, it provides a decision-theoretic planner which is used by the acting component when a problem needs to be solved for a given horizon (a short horizon in the Robotcup, given environment dynamics). The acting component monitors and perceives the environment through passive sensing, and acts or plans accordingly. ReadyLog was deployed on a robot-cup soccer robot and a service robot.

Overall these approaches perform refinement through the recursive application and instantiation of Prolog clauses. GOLEX offers no particular construct to handle time, nondeterminism, or plan repair. Readylog goes further in handling nondeterminism and time (with its limited horizon search). From the knowledge representation point of view, GOLOG and GOLEX rely on the same language, but they remain clearly separated, GOLOG producing a sequence of "do" which is mapped to a sequence of "exec" in GOLEX. Readylog is programmed in GOLOG. To our knowledge, none of these systems exploits the logic representation for performing consistency verification of planning and acting models; their benefit in terms of easier engineering specifications has not been documented.

CSP-based approaches

As seen in Section 3.2 temporal planning often produces partially instantiated plans with a least commitment approach allowing acting to adapt to the contingencies of the execution context. This has led to several developments of these approaches for acting. All time-based acting systems are de facto CSP-based.

Acting proceeds by progressively instantiating atemporal and temporal variables in the plan, through observation and context dependent choices. These values are propagated over the remaining constraints with consistency checking. Failures, that include observable but non-controllable variables (e.g., ending times of commands) outside of their assumed bounds, trigger plan repair.

IxTeT [START_REF] Ghallab | Representation and Control in IxTeT, a Temporal Planner[END_REF] was extended with execution capabilities following this approach [START_REF] Lemai-Chenevier | Interleaving Temporal Planning and Execution in Robotics Domains[END_REF]. Planning and acting share the partial plan structure that is dynamically produced during the planning phase and executed and repaired during the acting phase. An execution failure is seen as a new flaw in the partial plan space. The repair process tries to stay as close as possible to the rest of the plan. Repair requires invalidating part of the current plan and relaxing some constraints. This is done by memorizing for each causal link the reason why that link was inserted. Causal links associated with tasks are not removed from the flawed plan. If the repair does not succeed within some allocated time, the current plan is discarded and planning is restarted from the current situation. To bridge the gap with robot commands and perceptions, PRS is used jointly with IxTeT for refinement and skill execution. This system was deployed on the Dala robot for planetary exploration missions.

DS1/RAX implements a procedure-based acting approach; its successful deployment on the DS1 mission inspired the development of two planning & acting systems: IDEA and RMPL. IDEA [START_REF] Muscettola | A Unified Approach to Model-Based Planning and Execution[END_REF] relies on a distributed approach where planning and acting use the same representation and differ only in their prediction horizon and allocated computing time to find a solution. The system is distributed over a hierarchy of components (agents), each being in charge of a particular function: e.g., mission planning, robot navigation, robot manipulation, payload management, etc; each has its own set of timelines, planning horizon, and computing time quantum. Components use the EUROPA planner to perform the constraint-based temporal planning. Components may share some timelines, accessed and modified by both, possibly with priorities. The timeline sharing mechanism allows the propagation of the planning results down to commands and, similarly, the integration from percepts to observations. In principle the hierarchy of components is able to express a continuum from planning operators down to commands. However, the scaling up of the technique proved to be difficult; the shortest computing time quantum that could be achieved was on the order of a second, not fast enough for the command level. Hence, that system had also to resort to hand programmed skills. Furthermore, the specification and debugging of action models distributed over several components proved to be complex and tedious.

IDEA has been experimented with on several platforms such as the K9 and Gromit rovers [START_REF] Finzi | Model-based Executive Control through Reactive Planning for Autonomous Rovers[END_REF]. It led to the development of the T-REX system, deployed at MBARI for controlling AUVs [START_REF] Py | A Systematic Agent Framework for Situated Autonomous Systems[END_REF][START_REF] Rajan | T-REX: Partitioned inference for AUV mission control[END_REF][START_REF] Rajan | Towards Deliberative Control in Marine Robotics[END_REF] over long missions. T-REX is distributed, like IDEA, but differently organized into "reactors". Timeline sharing is used in both systems, but T-REX components are organized in such a way that constraint propagation is guaranteed to terminate (which is not the case in IDEA). T-REX is planner independent. MBARI implementation uses EUROPA with learned policies [START_REF] Magazzeni | Policy learning for autonomous feature tracking[END_REF]. T-REX was also used with APSI [START_REF] Ceballos | A Goal-Oriented Autonomous Controller for Space Exploration[END_REF], but not at the level of integration reached with EUROPA.

Casper [START_REF] Rabideau | Iterative Repair Planning for Spacecraft Operations in the ASPEN System[END_REF][START_REF] Knight | Casper: space exploration through continuous planning[END_REF][START_REF] Estlin | Increased Mars Rover Autonomy using AI Planning, Scheduling and Execution[END_REF] is a temporal constraint-based executor for the ASPEN planner that continuously produces fully instantiated plans. The resulting plan can be brittle and execution may often fail. However, the system relies on fast local search mechanisms (iterative repair) to reestablish plan consistency and resume execution. The system has been used on test-beds for exploration rovers and onboard real orbiting satellites.

Controllability is an issue for CSP-based approaches. It is due to contingent constraints and time points. The latter are for example the occurrence of an exogenous event or the end time of an action; they are not under the actor's control. A contingent temporal constraint expresses bounds on the uncertainty of a random variable duration; it cannot be reduced through constraint propagation, as usual in CSP. Simple Temporal Networks with Uncertainty (STNU) formalize these notions with a partition of their time points and constraints into controllable and contingent ones [START_REF] Vidal | Dealing with uncertain durations in temporal constraints networks dedicated to planning[END_REF]. An STNU is dynamically controllable if there is a procedure for assigning dynamically values to controllable variables such that all the controllable constraints are met, given that at each step of this procedure, the values of contingent variables preceding that step are known and fit the bounds in the contingent constraints. Dynamic controllability can be checked in polynomial time [START_REF] Morris | Dynamic Control of Plans with Temporal Uncertainty[END_REF][START_REF] Morris | Temporal Dynamic Controllability Revisited[END_REF], including incrementally [START_REF] Nilsson | Incremental Dynamic Controllability in Cubic Worst-Case Time[END_REF].

This property is maintained by a few systems, including notably some versions of RMPL. The Reactive Modelbased Programming Language (RMPL) [START_REF] Ingham | A Reactive Model-based Programming Language for Robotic Space Explorers[END_REF], another spinoff of the DS1/RAX experiment, proposes a common representation for planning, acting and monitoring. It combines a system model with a control model. The former uses hierarchical constraint-based automata to specify nominal as well as failure state transitions, together with their constraints. The latter uses reactive programming constructs (including primitives to address constraint-based monitoring, e.g., as in the Esterel [START_REF] Coste-Maniere | A task-level robot programming language and its reactive execution[END_REF] synchronous langage). RMPL programs are transformed into Temporal Plan Networks (TPN) [START_REF] Williams | Executing Reactive, Model-based Programs through Graph-based Temporal Planning[END_REF], an extension of Simple Temporal Networks (STN) with symbolic constraints and decision nodes. Planning with a TPN is finding a path in the network that meets the constraints.

Altogether, RMPL integrates state-based models, procedural control and temporal reasoning. More recent work on RMPL focuses on the execution component of generated plans with choices and on the reduction of the plan size to improve the dynamic execution [START_REF] Conrad | Flexible execution of plans with choice[END_REF]. In [START_REF] Effinger | Dynamic Execution of Temporally and Spatially Flexible Reactive Programs[END_REF], the authors extend TPN with error recovery, temporal flexibility, and conditional execution based on the state of the world. Each primitive task is given with a distribution of its likely duration. A probabilistic particle-sampling dynamic execution algorithm finds an execution guaranteed to succeed with a given probability. Probabilistic TPN are introduced in [START_REF] Santana | Chance-Constrained Consistency for Probabilistic Temporal Plan Networks[END_REF] with the notions of weak and strong consistency, as well as algorithm to check these properties. Finally, TPNUs [START_REF] Levine | Concurrent Plan Recognition and Execution for Human-Robot Teams[END_REF] add the notion of uncertainty for contingent decisions taken by the environment or another agent. The acting system adapts the execution to observations and predictions based on the plan. It has been illustrated with a service robot which observes and assists a human.

RMPL is the most comprehensive CSP-based approach: it provides refinement, instantiation, time, nondeterminism, plan repair. The other systems handle very partially nondeterminism with local failure and conditional branching. Another important point is that all CSP approaches rely on common models to produce plans, skills and commands (often the separation between planning and acting is not sharp). These models can be verified and checked with formal tools [START_REF] Cesta | Validation and verification issues in a timeline-based planning system[END_REF][START_REF] Abdeddaïm | Planning Robust Temporal Plans: A Comparison Between CBTP and TGA Approaches[END_REF]. Yet, writing these models and debugging them remains tedious and not completely natural for the robot programmer. Finally, the performance of CSP approaches is not always up to real-time acting requirements, and some rely on another computational framework to implement the lower level components (e.g., [START_REF] Magazzeni | Policy learning for autonomous feature tracking[END_REF]).

Acting with MDP-based approaches

As seen in Section 3.3, a policy π provides an acting procedure robust to nondeterminism and execution failures. It simply triggers the action given by π for the current state, observes the resulting state, and repeats until a goal is reached, or π is undefined. In POMDPs, acting is with respect to the belief state. This is illustrated in the Pearl system of [START_REF] Pineau | Towards robotic assistants in nursing homes: Challenges and results[END_REF]. Although the domain in that case was fairly small (6 state variables giving a total of 516 states), the flat belief space was still beyond available algorithms. The authors underline that in their case, as in most applications, actions are only applicable in certain situations. A hierarchical partition of the action space (similar to HTN) leads to a tree whose leaves are small POMDPs. This hierarchical POMDP is tractable with near-optimal algorithms. The approach was tested for a robot assisting elderly individuals with mild cognitive and physical impairments and supporting nurses. The POMDP model is appealing in theory but quite restrictive in practice. Generally, many of the needed state variables in a robot can be made observable, only a few remain hidden. The robot's partial observability concerns only the latter. This significantly focuses the uncertainty about the current state and the possible courses of action. Such a partial observability approach is pursued with the MOMDP model [START_REF] Ong | Planning under Uncertainty for Robotic Tasks with Mixed Observability[END_REF][START_REF] Araya-Lopez | A Closer Look at MOMDPs[END_REF] which represents the states space as the cartesian product of a set of visible states and a set of hidden states. Probabilistic approaches are also appealing for the interleaving of planning and acting. Algorithms such as RTDP [START_REF] Barto | Learning to Act Using Real-Time Dynamic Programming[END_REF] and LRTDP [START_REF] Bonet | Learning Depth-First Search: A Unified Approach to Heuristic Search in Deterministic and Non-Deterministic Settings, and Its Application to MDPs[END_REF] offer an anytime approach interleaving planning and acting, when both functions are defined on the same state and action spaces. In urgency, the robot acts along a locally perceived best action. If it can afford a look ahead before acting, it explores part of its search space by performing as many random trials as it can afford to improve its value estimates. More elaborate sampling techniques offer some advantages:

• they allow the system to sample with predictive models and simulators as well as by acting in the environment,

• they naturally embed online receding horizon planning and acting, and • they do not require a priori estimates of the model's probability distributions, as long as the samples are drawn from the same distribution. Despite their advantages, there are relatively few robotic systems acting and controlling a plan with probabilistic models. This is probably due to the fact that the MDP-based approaches do not yet address the various types of processing needed for acting (action refinement, instantiation and constraint propagation, time management, etc.), in addition to decision making in nondeterministic domains.

For that, heterogeneous approaches mixing MDPs with other techniques offer a practical alternative. But the computational and functional properties of these approaches can be difficult to characterize. The Robel system [START_REF] Morisset | Learning how to combine sensory-motor functions into a robust behavior[END_REF] provides an example where planning and action refinement into skills (with HTN) are deterministic, but probabilistic techniques are used online, with receding horizon control, for choosing the best skill at each navigation step. It demonstrates that MDPs are well adapted for deciding about the appropriate skill into which an action is refined, in particular when that skill may change while the action is going on. A similar idea is illustrated in [START_REF] Zilberstein | Decision-Theoretic Control of Planetary Rovers[END_REF] for the control of the mission of a planetary rover. The input is a sequence of tasks representing the mission plan. Each task is a sequence of steps; a step is achieved by a module chosen in an explicit list. An MDP-based online system chooses the module for the next step and decide to continue the current task or to skip it, given available resources and expected rewards. These approaches require significant engineering for the design of their state space.

The Ressac project illustrates another MDP approach for achieving a UAV rescue mission [207]. Here the target area has been surveyed and segmented into a few zones where landing seems possible. An online anytime MDP planner interleaved with acting and control optimizes the final exploration, choice of a zone, and landing.

In conclusion, probabilistic techniques can be well adapted for refining and controlling a complex action. They need to be complemented with other approaches for controlling an entire plan. They require an expert modeler, knowledgeable in robotics and in MDP techniques, for structuring the state space and specifying the domain.

Summary

The acting function is in charge of refining planned actions into commands and reacting to events, while instantiating the remaining parameters in the plan, synchronizing and dispatching activities in a context dependent manner. Adequate integration between planning and acting is critical.

Early systems assumed that planning primitives were directly executable, reducing the acting function to reacting without much refinement deliberation. Procedure-based systems remain quite popular and widely developed in robotics systems. They offer advantages in flexibility, real-time properties and expressivity for specifying closedloop skills. Their drawback is the demanding engineering effort required for the specification of skills. They raise significant obstacles for verification and validation, which are mandatory in safety critical applications.

Automata-based approaches address part of the latter concern. They offer well founded properties and tools for verification from hierarchical distributed specifications. The composition of automata significantly enrich deliberation capabilities. Future work will address time, uncertainty, nondeterminism and easier integration to planning. The Situation Calculus approach is used in a few systems. It offers a mixture of hand-specified procedures (as in logicbased programs) and reasoning capabilities. It is no as flexible as procedure-based systems and as rich in functionality. Further progress of formal Action Specification Languages in task planning may increase its usability for robotics.

Several of the analyzed systems rely on CSP-based techniques. They are designed for handling time, resources, uncertainty, and more generally when plans are expressed as consistent networks of constraints. Acting proceeds by making commitments and propagating additional constraints. The link to plan repair through CSP mechanisms is quite natural. Decision-theoretic approaches bring essential features for handling uncertainty, partial observability and dealing with closed-loop plans. They are not as widely used in robotics deliberation systems as one might expect, in particular because of a more demanding model specification phase. Progress in learning methods will probably foster their development and use at the acting level of deliberation.

Monitoring and Goal Reasoning

Monitoring is a function in charge of (i) detecting discrepancies between predictions and observations, (ii) diagnosing their possible causes, and (iii) recovering from them. Monitoring is sometimes referred to as supervision or fault detection, identification and recovery (FDIR). More generally, monitoring has to detect if the robot's activity remains on course or if a course correction is needed.

At the highest level, a monitoring system has to survey whether the robot's current goals are still feasible and relevant for its mission, and possibly establish new goals if they are not (Sec. 5.4). While current goals remain valid, monitoring has to survey the planner's predictions supporting the plan achieving these goals. It also needs to survey predictions made when refining planned actions into commands, and to monitor conditions relevant for the current actions that are left implicit in the planning and refinement steps. The latter are, for example, the functioning status of the hardware components: the readiness conditions of the robot's sensors, or the charge level of its batteries. Finally, monitoring is closely linked to observing. Relevant information about the environment may be difficult or costly to sense and maintain continuously. An appropriate focus of attention should be set in order to detect conditions relevant for the current context and predictions.

As a function, monitoring is clearly distinct from acting. While the latter is a transformation process, the former has to keep a check on this process, including its motivations, which requires specific observation and anticipation. However, the overlap between acting and monitoring is often large in the literature and implementations. For example, the early Planex system performed very simple monitoring through the iterated computation of the current active kernel of a triangle table [START_REF] Fikes | Monitored Execution of Robot Plans Produced by STRIPS[END_REF]. In most instances of procedure-based systems (Sec. 4.2), there are specific procedures in PRS, RAP, ACT or TCA, or part of such procedures, that handle monitoring functions. However, diagnosis and recovery functions in such systems are usually limited and quite ad hoc.

Monitoring in robotics takes often inspiration from the field of industrial control, where monitoring is a critical and well studied issue. Several monitoring systems, along that line, are surveyed in [START_REF] Pettersson | Execution monitoring in robotics: A survey[END_REF], most of which are mainly concerned with a robot sensory-motor level. These systems rely on control theory models, filtering techniques, statistical methods, such as Principle Component Analysis, for analyzing training data of normal and failures cases, and pattern recognition techniques for diagnosis. The relationship between monitoring and planning was not a major concern for the work discussed in [START_REF] Pettersson | Execution monitoring in robotics: A survey[END_REF]. This link (covered in Sec. 5.2 and 5.3) is essential from the integrated deliberation viewpoint of this survey. We'll also discuss relevant contributions to model-based diagnosis and to goal reasoning. Approaches presented below are summarized in Table 7.

Knowledge Representation

Search & Algorithm Integration with other Deliberative Functions Planex [START_REF] Fikes | Monitored Execution of Robot Plans Produced by STRIPS[END_REF] Triangular table Kernel method PA Livingstone [START_REF] Muscettola | Remote Agent: to boldly go where no AI system has gone before[END_REF] Qualitative model Transition automata with probabilities and costs ITMS with conflict-directed best-first search PO RMPL [START_REF] Ingham | A Reactive Model-based Programming Language for Robotic Space Explorers[END_REF] Hierarchical constraintbased automata Reactive programming P Fraser [START_REF] Fraser | Plan execution in dynamic environments[END_REF] Invariants Satisfiability P Fichtner [START_REF] Fichtner | Intelligent execution monitoring in dynamic environments[END_REF] Fluent Calculus Prioritized non-monotonic default logic PO Lamine [START_REF] Ben Lamine | Reasoning about Robot Actions: A Model Checking Approach[END_REF] Linear Temporal Logic Delayed formula progression P Pettersson [START_REF] Pettersson | Model-free execution monitoring in behavior-based mobile robotics[END_REF] Neural net PO SKEMon [START_REF] Bouguerra | Semantic Knowledge-Based Execution Monitoring for Mobile Robots[END_REF] Description Logic & Bayesian Belief PO TALplanner [START_REF] Doherty | A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems[END_REF] Temporal Action Logic Formula progression PO Table 7: Surveyed monitoring approaches: knowledge representation, algorithms and links with other deliberation functions.

Model-based Diagnosis Approaches

Model-based approaches are exemplified by Livingstone [START_REF] Muscettola | Remote Agent: to boldly go where no AI system has gone before[END_REF][START_REF] Bernard | Remote agent experiment ds1 technology validation report[END_REF], the comprehensive spacecraft monitoring, diagnosis and recovery system in DS1/RAX. Livingstone relies on a knowledge representation specific to qualitative model-based diagnosis [START_REF] Williams | A Model-based Approach to Reactive Self-Configuring Systems[END_REF]. Its objective is not to track the exact state of a system but simply to rule out incorrect diagnoses. The approach represents continuous functioning modes as nominal or qualitative deviations from nominal behaviors. The spacecraft is modeled as a fine grained collection of components, e.g., a thrust valve. Each component is described by a graph where nodes are the normal functioning states or the failure states of that component, e.g., valve closed, open or stuck. Edges are either nominal transition commands or exogenous transition failures. The latter are labeled by transition probabilities; the former are associated with transition costs and the preconditions of the command. A node is associated with a set of finite domain constraints describing the component's properties in that state, e.g., in the valve closed state, inflow = 0 and outflow = 0. The dynamics of each component is constrained such that, at any time, exactly one nominal transition is enabled but zero or more failure transitions are possible. Models of all components are compositionally assembled into a system where concurrent transitions compatible with the constraints and preconditions take place. The entire model is compiled into a temporal propositional logic formula which is queried through a specific solver (with a truth maintenance and a conflict-directed best-first search). Two query modes are used:(i) diagnosis, i.e., find the most likely transitions consistent with the observations, and (ii) recovery, i.e., find the least cost commands that restore the system into a nominal state. This monitoring system is well integrated with the acting system. It reports the spacecraft functioning state at the appropriate level of abstraction. It computes a focused sequence of recovery commands that meets additional constraints specified by the acting system.

This approach was demonstrated as very effective for a spacecraft. However, it is very specific to robots where reliability is a highly critical design issue addressed through a number of redundant components (to the sacrifice of cost) permitting complex diagnosis and allowing sophisticated recovery actions. Furthermore, the models are platform specific: a change in the hardware would involve significant development costs. Finally, the approach focuses the monitoring on the robot itself, not on the robot-environment interactions (whose possible "faults" are not modeled). It can be qualified as a robust proprioceptive monitoring approach. It is unclear how it could deal with environment discrepancies, e.g., a service robot failing to open a door. More research in that direction is required, e.g., along the framework of [START_REF] Baier | Diagnostic Problem Solving: A Planning Perspective[END_REF] which reformulates model-based diagnosis problems as planning problems.

Plan-Invariant Approaches

Several authors have synthesized from the specification of planning domain state-reachability conditions to speedup planning [START_REF] Rintanen | An Iterative Algorithm for Synthesizing Invariants[END_REF][START_REF] Helmert | Concise finite-domain representations for PDDL planning tasks[END_REF][START_REF] Bernardini | Finding Mutual Exclusion Invariants in Temporal Planning Domains[END_REF]. These techniques can be used to extract plan invariants, i.e., conditions that have to hold during the entire execution of a plan. Going further, [START_REF] Fraser | Plan execution in dynamic environments[END_REF] proposes extended planning problems, where the usual planning specifications are extended by logical formula stating invariant conditions that have to hold during the entire execution of a plan. These extended invariants are used for monitoring the execution of a plan. They allow to detect infeasible actions or goals earlier than would done by checking preconditions; violated effects are detected even after actions have been successfully achieved. Extended invariants also allow a system to monitor the effects of exogenous events and other conditions not influenced by the robot. The paper shows that planning operators and extended invariants are two distinct issues that have to be modeled and specified distinctly. However, the important link of monitoring to observing remains somewhat shallow in this approach, e.g., the observation function assumes perfect and complete sensing. No empirical evaluation has been reported.

Along the same line, the approach of [START_REF] Fichtner | Intelligent execution monitoring in dynamic environments[END_REF] has been tested on a simple office delivery robot. It relies on a representation of dynamic environment using the fluent calculus [START_REF] Sandewall | Features and Fluents[END_REF]. Actions are described by normal and abnormal preconditions. The former are the usual conditions, to be planned for before the actions. The latter are assumed away by the planner as default; they are used as a possible explanation of a failure. For example, delivery of an object to a person may fail with abnormal preconditions of the object being lost or the person not being traceable. Abnormal effects are similarly specified. Discrepancies between expectations and observations are handled by a prioritized non-monotonic default logic, and entail that default assumptions no longer hold. These explanations are ranked using relative likelihood, when available. The system is able to handle incomplete world models and observation updates received while acting or on demand from the monitoring system through specific sensory actions.

The idea of using extended logical specifications for planning and monitoring has been explored by several authors, in different settings. An interesting variant is illustrated in [START_REF] Ben Lamine | Reasoning about Robot Actions: A Model Checking Approach[END_REF] for a hybrid robot architecture that combines behaviorbased reactive control with model-based deliberation capabilities. At each cycle, concurrent behaviors are activated and combined (with some priority scheme) to determine the low level controls. At a higher level, properties of the robot behaviors are modeled using Linear Temporal Logic: LTL formulas are used to express goals as well as correctness statements and execution progress conditions. A trace of the robot execution, observed or predicted at planning time, is incrementally checked for satisfied and violated LTL formulas. For that, a delayed formula progression technique evaluates at each state the set of pending formulas; it returns the set of formulas that has to be satisfied by any remaining trace. The same technique is used both for planning (with additional precondition-effect operators and some search mechanism) and for monitoring. The approach has been tested in indoor navigation tasks with Pioneer robots running the Saphira architecture [START_REF] Konolige | The Saphira architecture: a design for autonomy[END_REF].

At the low level of a behavior-based architecture, and complementary to the previous approach, the behavior activation signals can be tracked for patterns characteristic of the execution status. [START_REF] Pettersson | Model-free execution monitoring in behavior-based mobile robotics[END_REF] developed a pattern recognition approach to exploit these activation signals. They train a neural net on various normal and faulty executions and use it online to detect and classify faults, reporting very low error rates in navigation tasks.

Finally, let us mention the interesting approach of [START_REF] Bouguerra | Semantic Knowledge-Based Execution Monitoring for Mobile Robots[END_REF] that uses domain knowledge expressed in description logic to derive expectations of the effects of actions in a plan to be monitored during execution. A first order query language allows online matching of these expectations against observations. Basically, the action parameters refer to world objects which have derived properties. These properties are checked to be either consistent or inconsistent with observations. They may even be of an undetermined consistency, permitting the monitoring function to deal with an open world semantics. An interesting extension handles flexible monitoring with probabilistic models, akin to Bayesien belief update. It relies on probabilistic plans with nondeterministic actions as well as on probabilistic sensing models. The approach was tested on indoor robot navigation and on simulated manipulation tasks.

Temporal Action Logic Approach

A comprehensive and coherent integration of planning and monitoring is illustrated in [START_REF] Doherty | A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems[END_REF]. That system demonstrates a complex planning, acting and monitoring architecture embedded on autonomous UAVs. It has been tested in particular in surveillance and rescue missions. Planning relies on a forward chaining planner using the Temporal Action Logics (TAL) formalism for specifying operators and domain knowledge [START_REF] Kvarnström | TALplanner: A temporal logic based forward chaining planner[END_REF]. Formal specifications of global constraints and dependencies, together with planning operators and control rules, are used by the planner to control and prune the search. Monitoring formulas are generated from the model of planning operator (its preconditions, effects and temporal constraints), and from the complete synthesized plan, e.g., constraints on the persistence of causal links. This automated synthesis of monitoring formulas is not systematic but rather selective, on the basis of hand-programmed conditions of what needs to be monitored and what doesn't. Additional monitoring formulas are also specified along with the planning domain knowledge in the same highly expressive temporal logic formalism.

The TAL-based system produces plans with concurrent and durative actions together with conditions to be monitored during execution. These conditions are evaluated online using formula progression techniques. When actions do not achieve their desired results, or when some other conditions fail, recovery via a plan repair phase is triggered. Acting is performed by Task Procedures (TP) [START_REF] Doherty | A Distributed Architecture for Autonomous Unmanned Aerial Vehicle Experimentation[END_REF], which provide some level of action refinement through classical concurrent procedural execution, down to elementary commands. Observing uses DyKnow [START_REF] Heintz | Bridging the sense-reasoning gap: DyKnow-Stream-based middleware for knowledge processing[END_REF], a data-flow middleware to abstract and anchor sensor data (more in Sec. 6). Altogether, this system proposes a coherent continuum from planning to acting, observing and monitoring. The only component which does not rely on formal specifications is the acting function with hand written TPs. The lack of action refinement is addressed by specifying planning operators at a low level of granularity. For example, there are five different fly operators in the UAV domain, defining context-specific control and monitoring conditions and mapped to different Task Procedures.

Goal Reasoning

As introduced earlier, goal reasoning is a monitoring function at the highest level of mission management. Its role is to survey the current goals of a robot, check that they remain feasible and relevant for the mission at hand, and establish new goals if needed. It is sometime referred to as Goal Driven Autonomy (GDA). It is attracting a growing interest in AI, as revealed in the two surveys of [START_REF] Hawes | A survey of motivation frameworks for intelligent systems[END_REF][START_REF] Vattam | Breadth of Approaches to Goal Reasoning: A Research Survey[END_REF]. Although not focused on deliberation in robotics, these two papers are very relevant to our purpose. The former surveys a number of architectures supporting goal reasoning in intelligent systems (e.g., SOAR, BDI and other belief architectures). The latter reviews over 80 contributions on various techniques for goal monitoring, goal formulation and goal management, organized within a comprehensive goal reasoning analysis framework. We will review in this subsection a few examples of goal reasoning mechanisms that can be integrated to a robot's deliberation system.

Part of the goal reasoning function is sometimes embedded into the planner or the controller. However, goal reasoning does not produce plans; it manages current goals and establishes new ones which are passed to a planner. As a monitoring function, it continuously checks for unexpected events or situations. It does not rely on the explicit prediction of the current plan (e.g., with invariants), and it may react to unexpected events by establishing new goals.

Goal Driven Autonomy (GDA) is generally presented as a reflexive model for reasoning about possibly conflicting goals and synthesizing new ones. In [START_REF] Molineaux | Goal-driven autonomy in a Navy strategy simulation[END_REF], the authors instantiate the GDA model in the ARTUE (Autonomous Response to Unexpected Events) system which appropriately responds to unexpected events in complex military simulations. ARTUE includes an HTN planner. If it detects a discrepancy when it executes a plan, it generates an explanation, possibly produces a new goal and manages possible conflict between goals currently under consideration. It uses different approaches to decide which goal to keep, e.g., decision theory. The approach proposes an original explanation system, which uses an Assumption-based Truth Maintenance System to find the possible worlds explaining the observed facts; it generates new goals, based on user-defined knowledge, to respond to the assumptions leading to these discrepancies. In [START_REF] Powell | Active and Interactive Discovery of Goal Selection Knowledge[END_REF], the authors extend ARTUE with a facility for teaching the system new goal selection rules through interactions with a teacher using active learning.In [START_REF] Wilson | Bounded Expectations for Discrepancy Detection in Goal-Driven Autonomy[END_REF] the authors present an instance of GDA applied to AUV.

The Plan Management Agent (PMA) [START_REF] Pollack | There's more to life than making plans: plan management in dynamic, multiagent environments[END_REF] provides, beyond planning and monitoring, the following functions: • Commitment Management: commits to a plan already produced, and avoids as much as possible new plans which conflict with the existing ones. When a conflict arises, the agent reasons and decides which plan to give up. • Alternative Assessment: decides which of the possible alternative goals and plans should be kept or discarded.

• Plan Elaboration: decides when and how to generate a plan.

• Coordination with Other Agents: takes into account others' commitments and the cost of decisions involving their plans. PMA relies heavily on temporal and causal reasoning; it is able to plan with partial commitments that can be further refined later. It has been applied in personal calendar and workflow systems.

Goal reasoning has been deployed in a few real experiments. The Mission Manager (MM) in the DS1/RAX experiment [START_REF] Muscettola | Remote Agent: to boldly go where no AI system has gone before[END_REF][START_REF] Bernard | Remote agent experiment ds1 technology validation report[END_REF] is a notable illustration. From the expected state at the end of the current plan, MM considers the overall mission goals (from a list of nominal ones) and profile, and determines which goals should be satisfied in the next horizon and planning window (one to two weeks). The selected goals are passed to the planner, together with constraints which need to be satisfied at waypoints identified by the MM (e.g., the amount of energy left in the batteries should be above a threshold at the end of the planning phase). Planning produces a new plan to achieve these goals, which will be appended to the current one. Similarly, in the CPEF framework [START_REF] Myers | CPEF: Continuous Planning and Execution Framework[END_REF], mostly used in military deployment problems, the Plan Manager is in charge of the overall system; it controls the generation of plans, providing appropriate goal information to the planner.

Summary

Model-based approaches are effective for the proprioceptive monitoring of the internal state of a robot in safety critical applications . Techniques demonstrated in space can probably be extended to self-driving cars and similar applications (column (vi) in table 1). However, they are not sufficient for supporting robust deliberative behavior in complex changing environments. Monitoring requires a close link to and an extension of planning and acting domain knowledge in order to express conditions to be monitored while carrying out a plan. The state of the art illustrates a few systems implementing monitoring functions where the knowledge representation link is addressed at the most abstract planning level. More work is required for a consistent integration of monitoring and acting. The design of appropriate knowledge representations for planning and acting should integrate as early as possible the requirements of monitoring. Finally, a high degree of autonomy over long term missions requires a goal reasoning capability, a form of monitoring at the most abstract level. Few robotic systems have reached a level which requires extending monitoring with assessment and resolution of conflicting decisions.

Observing

Perception is a critical component in robotics, e.g., in feedback control loops, visual servoing [START_REF] Chaumette | Visual Servoing and Visual Tracking[END_REF], or Simultaneous Localization and Mapping (SLAM) [START_REF] Bailey | Simultaneous localization and mapping (SLAM): part II[END_REF][START_REF] Montemerlo | FastSLAM 2.0: An Improved Particle Filtering Algorithm for Simultaneous Localization and Mapping that Provably Converges[END_REF]. These metric and probabilistic techniques, possibly enriched with topological and semantic data, e.g., as in [START_REF] Kuipers | A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations[END_REF][START_REF] Kuipers | Local Metrical and Global Topological Maps in the Hybrid Spatial Semantic Hierarchy[END_REF][START_REF] Konolige | Navigation in Hybrid Metric-Topological Maps[END_REF], are very effective for navigation and mapping tasks. But robots face other chores beyond mobility.

The observing function provides the capability to identify objects, states and sequences of events relevant to the robot's activity. It has to be tightly integrated with planning, acting and monitoring. It combines bottom-up processes, from sensors to meaningful data, with top-down mechanisms such as focus of attention, reasoning with sensor models and planning with sensing actions. Observing functions of the systems presented below are summarized in Table 8.

States and objects

Situations Planning Knowledge Representation Coradeschi [START_REF] Coradeschi | Perceptual anchoring: a key concept for plan execution in embedded systems[END_REF] Anchoring Anchor tracking Link to planning Anchors PTL [START_REF] Karlsson | To Secure an Anchor -A recovery planning approach to ambiguity in perceptual anchoring[END_REF] Ambigous anchors Conditional planning Anchors IxTeT-Reco [START_REF] Dousson | Situation recognition: Representation and algorithms[END_REF] Chronicle recog. Link to IxTeT Planner Chronicles SAM [START_REF] Pecora | A constraint-based approach for proactive, context-aware human support[END_REF] Chronicle recog. Timelines DyKnow [START_REF] Heintz | Bridging the sense-reasoning gap: DyKnow-Stream-based middleware for knowledge processing[END_REF] Anchoring Chronicle recog. Integration with TALPlan Streams, KPL HiPPo [START_REF] Sridharan | HiPPo: Hierarchical POMDPs for Planning Information Processing and Sensing Actions on a Robot[END_REF] Objet recognition Hierarchical POMDP POMDP Velez [START_REF] Velez | Planning to perceive: Exploiting mobility for robust object detection[END_REF] Object recognition Bayesian DBN Table 8: Surveyed observing systems: approaches and main functions.

Planning to perceive

We already discussed task planning with sensing and information gathering actions (Sec. 3.4). Planning to perceive is a distinct issue concerned with integrating the selection of viewpoints and sensor modalities with recognition, navigation and other tasks. It relies on extensive work on the sensor placement problem, usually addressed as a search for the next best viewpoint in a recognition or a modeling task, as in [START_REF] Laporte | Efficient discriminant viewpoint selection for active bayesian recognition[END_REF]. Several authors address this integrated planning problem with POMDPs, e.g., [START_REF] Pineau | Towards robotic assistants in nursing homes: Challenges and results[END_REF][START_REF] Prentice | The belief roadmap: Efficient planning in belief space by factoring the covariance[END_REF]. The HiPPo system [START_REF] Sridharan | HiPPo: Hierarchical POMDPs for Planning Information Processing and Sensing Actions on a Robot[END_REF] offers a good illustration of sensor placement for the recognition of objects on a table, as typically required in a manipulation task where intractability issues are addressed with a hierarchical POMDP technique. The approach seems feasible in limited perception tasks, involving a few regions of interest.

An alternative and more scalable approach for synthesizing an observation plan within a navigation task is proposed in [START_REF] Velez | Planning to perceive: Exploiting mobility for robust object detection[END_REF]. This work seeks to detect and map objects of interest while reaching a destination. It uses a Bayesian approach which correlates measurements from subsequent observations to improve object detection; detours are weighed against motion cost to produce robust observation plans using a receding horizon sampling scheme. The approach was tested in an indoor environment for recognizing doors and windows.

Object Recognition and Symbol Anchoring

The anchoring problem provides an excellent illustration of the complexity of integrating pattern recognition methods with deliberate action. As defined in [START_REF] Coradeschi | Perceptual anchoring: a key concept for plan execution in embedded systems[END_REF], anchoring is the problem of creating and maintaining over time a correspondence between symbols and sensor data that refer to the same physical object. Planning and other deliberation functions reason about objects in the environment through symbolic attributes and relations linking these symbols. Observing handles perceptual data. It is essential that the abstract description of the former and the data of the latter agree. Anchoring concerns specific physical objects. It can be seen as a particular case of the symbol grounding problem, which deals with broad categories, e.g., any "chair", as opposed to that particular chair-2.

Anchoring an object of interest can be achieved by establishing and keeping a link, called an anchor, between the perceptual system and the symbol system, together with a signature that estimates some of the attributes of the object it refers to (see Fig. 6, taken from [START_REF] Coradeschi | An introduction to the anchoring problem[END_REF]). The anchor is based on a model that relates relations and attributes to perceptual features and their values. Establishing an anchor corresponds to a pattern recognition problem, with the usual challenge of handling uncertainty in sensor data and ambiguity in models, a challenge dealt with for example by maintaining multiple hypotheses. In [START_REF] Karlsson | To Secure an Anchor -A recovery planning approach to ambiguity in perceptual anchoring[END_REF], ambiguous anchors are handled with a conditional planner, called PTL, exploring a space of belief states, representing the incomplete and uncertain knowledge due to partial matching between symbolic properties and observed perceptual features. The authors distinguish between definite symbolic descriptions, which are matched with a single object, and indefinite descriptions. Actions have causal effects that change object properties. Observations can change the partition of a belief state into several new hypotheses. They experimented with an indoor robot equipped with vision and smell sensing in object recognition tasks. may arise if several robots need to not only anchor symbols internally but also exchange information among them and agree on a shared language. Common agreement about the meaning of the symbols used to refer to objects in the environment is also needed for efficient human-robot cooperation. Some of the papers in this special issue deal with systems that involve communication among multiple robots [START_REF] Barto | Learning to Act Using Real-Time Dynamic Programming[END_REF][START_REF] Bernardini | Finding Mutual Exclusion Invariants in Temporal Planning Domains[END_REF][START_REF] Bidot | Geometric Backtracking for Combined Task and Path Planning in Robotic Systems[END_REF] or between robots and humans [START_REF] Abdeddaïm | Planning Robust Temporal Plans: A Comparison Between CBTP and TGA Approaches[END_REF]. According to our framework the anchoring process is performed in an intelligent embedded system that comprises a symbol system Σ and a perceptual system Π (see Fig. 2). The symbol system manipulates individual symbols, like 'x' and 'cup22', which are meant to denote physical objects. It also associates each individual symbol with a set of symbolic predicates, like 'red', that assert properties of the

Model

Perceptual System Symbol System anchor = (•, •, signature) Figure 6: Anchor relating symbols and percepts [START_REF] Coradeschi | An introduction to the anchoring problem[END_REF].

Anchoring raises several additional problems, e.g., which anchors to establish, when and how. Anchors are needed in principle for all objects relevant to the robot mission. These objects can only be defined by intension (not extensionally), in a context-dependent way. Tracking anchors is another issue, i.e., taking into account object properties that persist across time or evolve in a predictable way. Predictions are used to check that new observations are consistent with the anchor and that the updated anchor still satisfies the object's properties. Finally reacquiring an anchor when an object is re-observed after some time is a mixture of finding and tracking; if the object moves it can be quite complex to account consistently for its behavior (e.g., see the DyKnow system below).

Interaction with humans, in particular in natural language as in [START_REF] Shapiro | Anchoring in a grounded layered architecture with integrated reasoning[END_REF], or between robots, adds other problems of sharing anchors between distinct agents. For example [START_REF] Khoo | Grounding inference in distributed multi-robot environments[END_REF] considers several robots cooperating in office navigation and object finding tasks by exchanging information about specific features (color, position) with shared anchors. There is also the issue of learning the models needed for building up anchors, illustrated in [START_REF] Bredeche | A meta-learning approach to ground symbols from visual percepts[END_REF] through a supervised learning approach. For that, one may draw from the wealth of pattern recognition techniques in machine learning [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF], and from the growing set of labeled data and corresponding models on the web.

Event and Situation Recognition

The dynamics of the environment are an essential source of information in the observing function, as well as a source of complexity, e.g., as we just saw in the anchor tracking and re-acquiring problems. These dynamics are themselves what needs to be interpreted: what an observed sequence of changes means, what can be predicted next from past evolutions. Research on these topics relates to acting in and understanding environments with rich semantics, in particular involving human and man-robot interactions, e.g., in applications (column (iii) in Table 1) such as smart human-support environments [START_REF] Pecora | A constraint-based approach for proactive, context-aware human support[END_REF], robot programming by demonstration [START_REF] Argall | A survey of robot learning from demonstration[END_REF] or video surveillance [START_REF] Hongeng | Video-based event recognition: activity representation and probabilistic recognition methods[END_REF][START_REF] Fusier | Video understanding for complex activity recognition[END_REF].

The survey of [START_REF] Krüger | The meaning of action: a review on action recognition and mapping[END_REF] covers an extensive list of contributions to action and plan recognition. These deal with (i) human action recognition, (ii) general activity recognition, and (iii) plan recognition. The former two types of processing provide input to the latter. Most surveyed approaches draw from two sources of techniques: signal processing and plan recognition. The former use filtering approaches, Markov Chains, and Hidden Markov Models (HMM, e.g., [START_REF] Rabiner | An introduction to hidden Markov models[END_REF]). They have been successfully applied to movement tracking and gesture recognition [START_REF] Wu | Vision-based gesture recognition: A review[END_REF][START_REF] Moeslund | A survey of advances in vision-based human motion capture and analysis[END_REF]. The latter rely on deterministic [START_REF] Kautz | Generalized plan recognition[END_REF][START_REF] Ramirez | Probabilistic plan recognition using off-the-shelf classical planners[END_REF] or probabilistic [START_REF] Geib | A probabilistic plan recognition algorithm based on plan tree grammars[END_REF] planning techniques, as well as parsing techniques [START_REF] Pynadath | Probabilistic State-Dependent Grammars for Plan Recognition[END_REF].

Most plan recognition approaches assume as input a sequence of symbolic actions. This assumption is hard to meet in robotics. Usually actions are sensed only through their effects on the environment. The recognition of actions from their effects depends strongly on the plan level. Decomposing into recognizing actions then plans from these actions is fragile. Hence, classical plan recognition techniques has a limited usefulness in robotics.

Chronicle recognition techniques [START_REF] Dousson | Situation recognition: Representation and algorithms[END_REF][START_REF] Ghallab | On Chronicles: Representation, On-line Recognition and Learning[END_REF] are very relevant to the observing function. A chronicle is a model for a collection of possible scenarios. It describes classes of events, persistence assertions, non occurrence assertions and temporal constraints. A ground instance of a chronicle can be formalized as a nondeterministic timed automata. Chronicles are similar to IxTeT planning operators (Sec. 3.2). IxTeT-Reco, an extension of the IxTeT planner with the same representation, implements a chronicle recognition system. It is able to monitor a stream of observed events and recognize, on the fly, instances of modeled chronicles that match this stream. The recognition is efficiently performed by maintaining incrementally a hypothesis tree for each partially recognized chronicle instance. These trees are updated or pruned as new events are observed or time advances. It has been demonstrated in robotics surveillance tasks. Recent development have introduced hierarchy and focus on rare events [START_REF] Dousson | Chronicle Recognition Improvement Using Temporal Focusing and Hierarchization[END_REF].

The chronicle approach is appealing in particular for its direct link to planning and observing. The SAM system [START_REF] Pecora | A constraint-based approach for proactive, context-aware human support[END_REF] is a good illustration of the interest of such a link in the development of a ubiquitous robotics environment providing assistance to an elderly person. It uses a chronicle-like representation (timelines with interval algebra) offering online recognition, planning and execution with multiple hypotheses tracking over weeks.

Stream-Based Integration

Very few systems have been proposed for designing and implementing an integrated observing function, from signals, to states and chronicles. DyKnow [START_REF] Heintz | Bridging the sense-reasoning gap: DyKnow-Stream-based middleware for knowledge processing[END_REF] stands as a clear exception, noteworthy by its comprehensive and coherent approach. This system addresses most observing requirements: the integration of different sources of information, of hybrid symbolic and numeric data at different levels of abstraction with bottom-up and top-down processing, managing uncertainty, dynamically reconfigurable, and reasoning on explicit models of its content.

These requirements are addressed as a data-flow based publish-and-subscribe middleware architecture. DyKnow views the environment as consisting of objects described by a collection of features. A stream is a set of samples representing observations or estimations of the value of a feature. A sample has two time-stamps: when it was acquired and when the corresponding value was made available. A stream is associated with a formally specified policy giving requirements on its content. Examples of such requirements are the frequency of updates, the delays and amplitude differences between two successive samples, or how to handle missing values.

A stream is generated by a process which may offer several stream generators synthesizing streams according to specific policies. Processes have streams as input and output; they are of various types, e.g., primitive processes directly connected to sensors and geographic information systems; refinement processes which subscribe to input streams and provide as output combined features, e.g., a signal filter process or a position estimator process fusing several raw sensing sources and filtered data; configuration processes which allow reconfiguring dynamically the system by initiating and removing processes and streams as required by the task and the context, e.g., to track a newly detected target.

DyKnow uses a specific language, called KPL (Knowledge Processing Language), to specify processes, streams and corresponding policies. KPL allows in particular referring to objects, features, streams, processes, and time, together with their domains, constraints and relationships in the processing network. Formal specifications in KPL define a symbol for each computational unit, but they do not define the actual function associated with this symbol. Their semantics is taken with respect to the interpretation of the processing functions used. They allow the programmer to describe and enforce stream policies. They also allow the support several functions such as:

• synchronize states from separate unsynchronized streams;

• evaluate incrementally metric temporal logic formulas over states;

• recognize objects and build up anchors to incrementally update interpretation as new information becomes available;

• follow histories of spatio-temporal events and recognize occurrences of specified chronicle models.

Initially, DyKnow was implemented as a Corba middleware; the latest implementation relies on ROS middleware and topics. It has been integrated as the observing function of the TALplan system [START_REF] Doherty | A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems[END_REF] discussed in the previous section. This system is naturally queried by planning, acting and monitoring functions to acquire information about the current contextual state of the world. It provides appropriate and highly valuable focus of attention mechanisms, linking monitoring or control formulas to streams. It has been deployed within complex UAV rescue and traffic surveillance demonstration (the latter is illustrated in Fig. 7, taken from [START_REF] Heintz | Bridging the sense-reasoning gap: DyKnow-Stream-based middleware for knowledge processing[END_REF]).

Summary

Robotics research in perception is mostly focused on mobility, localization and mapping. These are essential but not sufficient functions. As discussed earlier (Sec. 4.6), most systems are partially observable in the sense that some of their state variables are observable while a few are hidden. The former demand explicit sensing and processing actions to be acquired, tracked and adequately interpreted. Observing is a critical deliberation function.

We reviewed here contributions to perception planning, anchoring symbols and signals, and recognizing situations. We also discussed a comprehensive stream-based approach for integrating an observing system with planning, acting knowledge processing software framework asoning in a physical g middleware should d an implementation of functionalities and ow between them. It cess low-level sensor vironment at increasding information and in symbolic deliberanowledge processing tance called DyKnow. d knowledge processonceptual and practiessing system as a set treams represent asa system and its envirange of distributed raction, while output ributes, relations, and scenario is presented. rocessing middleware re is proposed as suitte example, the formal rocessing middleware ed with some related plication domain for s), providing a plethnowledge processing uch as detecting acciroutes for emergency ics. c violations relies on rative formalism such efines a class of com-] where nodes correcorrespond to metric rences. For example, ualitative spatial relar 2 Þ, and onðcar; roadÞ reating these high-ledata, such as video volves a great deal of , which would benefit tematically organized regarding moving and stationary physical entities, including their approximate positions and velocities.

To use symbolic chronicle recognition, it is necessary to determine which vision objects are likely to represent cars. Such objects must be associated with car symbols in such a way that the symbol and the vision object consistently refer to the same physical object, a process known as anchoring [START_REF] Ambite | Learning Plan Rewriting Rules[END_REF]. This process can take advantage of knowledge about normative characteristics and behaviors of cars, such as size, speed, and the fact that cars normally travel on roads. Such characteristics can be described using formulas in a metric temporal logic, which are progressed (incrementally evaluated) in states that include current estimated car positions, velocities, and higher level predicates such as on À roadðcarÞ and in À crossingðcarÞ obtained from road network information provided by a geographic information system. An entity satisfying the conditions can be hypothesized to be a car, a hypothesis which is subject to being withdrawn if the entity ceases to display the normative characteristics, thereby causing formula progression to signal a violation.

The next stage of processing involves deriving qualitative spatial relations between cars, such as besideðcar 1 ; car 2 Þ and closeðcar 1 ; car 2 Þ. These predicates, and the concrete events that correspond to changes in the predicates, finally provide sufficient information for the chronicle recognition system to determine when higher-level events such as reckless overtakes occur.

In this scenario, which is implemented and tested on board an autonomous UAV system developed at the Unmanned Aircraft Systems Technologies (UASTech) Lab at Linköping University [START_REF] Ambros-Ingerson | Integrating Planning, Execution and Monitoring[END_REF], a considerable number of distinct processes are involved in bridging the sense-reasoning gap. However, in order to fully appreciate the complexity of the system, we have to widen our perspective. To- and monitoring. More work on similar systems is required to better qualify their capabilities and limitations for various robotics environments (in particular those marked "h" in column (v) and (viii) of Table 1).

Acquiring Deliberation Models

Deliberation requires a variety of models of the environment, of the robot's sensors, actuators, skills, tasks, etc. These models are often hand-specified in different representations. They can be tuned through estimation, parameter acquisition and calibration procedures. In a few cases, they can be verified and validated, usually at the level of one function, rarely when composed within a global behavior.

Modeling is a well-known bottleneck, more severe when the diversity of environments and tasks increases, i.e., when deliberation is needed. It is desirable to endow a robot with adaptation capability to allow it to accommodate to changes in its environment and tasks, to remove errors and improve its models and behaviors. Learning in robotics is a very active field. However, most of the effort has been devoted to two areas:

• Sensory-motor control models, as in [START_REF] Coates | Apprenticeship learning for helicopter control[END_REF][START_REF] Kober | Policy search for motor primitives in robotics[END_REF][START_REF] Kober | Reinforcement Learning in Robotics: A Survey[END_REF][START_REF] Nguyen-Tuong | Model learning for robot control: a survey[END_REF], and most of the work surveyed in [START_REF]From Motor Learning to Interaction Learning in Robots[END_REF];

• Environment models, in particular at the geometric level with SLAM techniques [START_REF] Thrun | Robotic Mapping: A Survey[END_REF][START_REF] Bailey | Simultaneous localization and mapping (SLAM): part II[END_REF], possibly combined with planning [145], and at the combined geometric and topologic levels, e.g., [START_REF] Choset | Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization[END_REF][START_REF] Konolige | Navigation in Hybrid Metric-Topological Maps[END_REF][START_REF] Ranganathan | Online probabilistic topological mapping[END_REF]. Learning sensory-motor and environment models is critical for autonomous robots, but it is out of the scope of this survey. Let us focus here on a few contributions to the acquisition of models needed for and specific to deliberation.

Acquiring semantic maps

Semantic maps extend geometric and topological models with semantic information about the environment. Contributions such as [START_REF] Galindo | Life-long optimization of the symbolic model of indoor environments for a mobile robot[END_REF][START_REF] Ranganathan | Semantic modeling of places using objects[END_REF] illustrate approaches for acquiring, organizing hierarchically, and optimizing such a map. Elvira [START_REF] Galindo | Life-long optimization of the symbolic model of indoor environments for a mobile robot[END_REF] represents the environment as a hierarchy of graphs. Nodes at a given level are symbols referring to locations and places; arcs correspond to relations such as navigability or proximity. At the lowest level, anchoring techniques capture the dynamics of the environment. Elvira contains an anchoring module, a hierarchy optimizer, and a hierarchical task planner. It has been tested on a hybrid behavior-based robot in navigation tasks.

Semantic maps endow a robot with deduction abilities about its environment that complement and enhance its perceiving function as well as its planning and acting functions. They allow the robot to relate a hierarchy of concepts and relations to a hierarchy of objects and places. For example, the concept "kitchen" is described as a topological node that contains objects such as stove, sink, etc. These objects are characterized with features permitting recognizing and using them. Techniques such as those mentioned in Section 5.2 are used to derive information about partially observed current states as well as expectations about the effects of actions. The Astrid indoor robot demonstrates in [START_REF] Galindo | Robot Task Planning Using Semantic Maps[END_REF] how semantics maps are learned, how semantic knowledge is integrated with metric and topologic maps, and how it is used to plan and execute domestic tasks.

Acquiring planning and acting models

Numerous methods have been proposed for acquiring and improving action models at the skill and task levels.

Approaches for acquiring and improving skill models are for example [START_REF] Fox | Robot introspection through learned hidden markov models[END_REF] with HMM, or [START_REF] Infantes | Learning the behavior model of a robot[END_REF] with Dynamic Bayes Nets (DBN) [START_REF] Dean | A model for reasoning about persistence and causation[END_REF]. Skill selection can be addressed as acquiring an MDP policy, as illustrated in the Robel system [START_REF] Morisset | Learning how to combine sensory-motor functions into a robust behavior[END_REF]. These three systems have been demonstrated in indoor navigation tasks. Similarly, the MRTE approach of [START_REF] Mericli | Multi-resolution Corrective Demonstration for Efficient Task Execution and Refinement[END_REF] considers several skills for a given task; it uses a supervised learning approach where a teacher provides corrections for choosing a skill and commands within skills. It has been demonstrated for humanoid obstacle avoidance.

Learning in task planning has been used to speed-up planners with control knowledge and macro actions [START_REF] Newton | Learning macro-actions for arbitrary planners and domains[END_REF][START_REF] Coles | Marvin: A heuristic search planner with online macro-action learning[END_REF], specific heuristics [START_REF] Yoon | Learning heuristic functions from relaxed plans[END_REF][START_REF] Xu | Discriminative learning of beam-search heuristics for planning[END_REF] and their choice rules [START_REF] Domshlak | Online Speedup Learning for Optimal Planning[END_REF]. It has also been used to improve the quality of plans with respect to cost, success rate [START_REF] Magnenat | Integration of Online Learning into HTN Planning for Robotic Tasks[END_REF][START_REF] Stulp | Refining the execution of abstract actions with learned action models[END_REF], or user's preferences [START_REF] Ambite | Learning Plan Rewriting Rules[END_REF], and to learn domain models and planning operators [START_REF] Yang | Learning action models from plan examples using weighted MAX-SAT[END_REF][START_REF] Walsh | Efficient learning of action schemas and web-service descriptions[END_REF]. The survey of [START_REF] Zimmerman | Learning-Assisted Automated Planning: Looking Back, Taking Stock, Going Forward[END_REF] analyses a wide spectrum of approaches ranging from decision trees, inductive logic, and explanation-based learning, to classification methods, Bayesien learning and neural nets. The more recent review of [START_REF] Jiménez | A Review of Machine Learning for Automated Planning[END_REF] updates this map with respect to new contributions for acquiring planning domain models or control knowledge. Most of these contributions are concerned with speeding up task planners; only a few consider learning while acting; even fewer are demonstrated in robotics. This is not the case for approaches in reinforcement learning and in learning from demonstration.

Reinforcement learning (RL) integrates learning and acting. Most approaches rely on learning an MDP policy, progressively improved with respect to a reward criterion [START_REF] Kaelbling | Reinforcement Learning: A Survey[END_REF][START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Gosavi | Reinforcement Learning: A Tutorial Survey and Recent Advances[END_REF]. RL approaches are usually non-supervised: the robot gets as feedback the cumulative rewards of its actions. RL raises the issue of exploration vs exploitation, i.e., exploring all possibilities to acquire new knowledge vs making use of learned knowledge [START_REF] Dearden | Model based Bayesian exploration[END_REF]. Scaling RL methods with discrete state spaces is a major concern. Continuous state variables with parametric models allow overcoming this issue by using functional approximation and policy search methods [START_REF] Kober | Policy search for motor primitives in robotics[END_REF]. They also allow generalizing what has been learned to unexplored areas of the parameter space when some continuity assumptions are met [START_REF] Russel | Statistical Learning Methods[END_REF]. An illustration is given in [START_REF] Kroemer | Active exploration for robot parameter selection in episodic reinforcement learning[END_REF] for learning grasping tasks by exploring the continuous parameter space with an approximation of the upper confidence bound on the return values using Gaussian process regression.

Generalization is also pursued through policy reuse techniques. These extend the exploration-exploitation alternative with a third option, the reuse of previously known or learned policies. Policy reuse is illustrated in RoboCup domains in [START_REF] Fernández | Probabilistic Policy Reuse for inter-task transfer learning[END_REF]. The approach requires mappings between state and actions spaces, but no a priori information about when the reuse is useful.

With more diverse environments and tasks, flat propositional representations are limited in expressiveness and complexity; their convergence requires a huge amount of training. A few structured representations have been explored, among which: factored MDPs with compact DBN-like representations [START_REF] Walsh | Integrating sample-based planning and model-based reinforcement learning[END_REF], hierarchical RL methods [START_REF] Dietterich | Hierarchical reinforcement learning with MAXQ value function[END_REF][START_REF] Marthi | Learning hierarchical structure in policies[END_REF], and relational RL methods [START_REF] Džeroski | Relational reinforcement learning[END_REF]. These approaches should be more adapted for learning complex decomposable behaviors and integrating learning into the reasoning methods used in task planning. Their effective development in complex robotics tasks remains to be demonstrated.

RL methods face another issue: reward functions are difficult to specify and estimate from observable variables. Inverse reinforcement learning aims to acquire reward functions from demonstrated behavior [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF][START_REF] Abbeel | Inverse Reinforcement Learning[END_REF]. With a similar motivation, other approaches augment RL methods with feedback from and interaction with a teacher to get advice on preferred policies. In this supervised RL mode, a teacher discriminates (e.g., through preferences) between alternative trajectories of (state, action) pairs issued from the same state [START_REF] Wilson | A Bayesian Approach for Policy Learning from Trajectory Preference Queries[END_REF]. The approach of [START_REF] Judah | Active Imitation Learning via Reduction to IID Active Learning[END_REF] allows the learner to choose most useful states where advice from the teacher can be useful. It has been tested in several simulation benchmarks such as learning to balance a cart pole or to ride a bicycle. These interactive approaches can be considered as a form of learning from demonstration.

Learning from demonstration is a paradigm for various techniques allowing a robot to learn policies from behaviors demonstrated by a human tutor. The survey of [START_REF] Argall | A survey of robot learning from demonstration[END_REF] classifies approaches into teleoperation, shadowing, instrumented teacher and external observation. In the former two categories, demonstrations take place in the robot configuration space. In the latter two, demonstrations are in the natural space of the teacher. Sensing of the state variables is direct in the cases of teleoperation or instrumented teacher. It requires interpretation in the two other cases. Learning methods acquire either policies, state-action dynamics from which policies can be derived, or explicit action models permitting deliberation and planning. Teleoperation approaches have been widely experimented with, e.g., in kicking and grasping motions, assembly, avoidance, navigation or helicopter flying. Shadowing has been used in navigation (following a teacher), or for learning hand gestures. Instrumented teachers have taught various skills and cup-and-ball games. Very few techniques cover the last category with external observation, where clearly more research is needed. The recent book of [START_REF] Chernova | Robot Learning from Human Teachers[END_REF] proposes future directions of research.

Summary

The state of the art for the acquisition of deliberation models remains very preliminary. We discussed a few approaches for acquiring semantic maps and integrating the learned knowledge into planning and acting models. These and similar approaches are strongly needed in service and domestic robots and other applications with similar features (see Table 1). We also discussed a few Reinforcement learning and Learning from Demonstration approaches which appear as promising research direction that have not yet been developed at the deliberation level in robotics.

Discussion and Synthesis

Numerous deliberation systems were discussed in Sections 3 through 7, along their planning, acting, monitoring, observing and learning functions. A synthesis of their common features, their significant differences, weak points and open challenges is in order. We will focus this synthesis on the analyzed systems in Table 2.

All the analyzed systems are concerned with three classes of applications: service and domestic robots, exploration and rescue robots (aerial, underwater and ground) and spacecraft. This is explained by the features of applications in Table 1 and from the fact that deliberation is entailed by autonomy and diversity of tasks and environment. It is also due to the state of the art which made it more feasible and robust to engineer out the environment in manufacturing and industrial robotics, even if this situation is now changing. Further development will make deliberation systems more effective in functionality and cost for most robotics applications.

Most analyzed systems address three main functions: planning, acting and monitoring. It is interesting to note that, in most of these systems, planning explicitly takes into account space and time. The former is mandatory for a mobile robot, but of particular cases, e.g., a spacecraft. There is however a significant difference between embedding a motion planner in a system's architecture, as a GenoM module in [START_REF] Alami | An Architecture for Autonomy[END_REF] or in the WITAS system [START_REF] Doherty | The WITAS unmanned aerial vehicle project[END_REF], and integrating motion and task features in the search and state spaces of planning, as done in Asymov [START_REF] Cambon | A Hybrid Approach to Intricate Motion, Manipulation and Task Planning[END_REF] and other systems discussed in Section 3.1. The latter option can properly handle interdependences between space configurations and other task properties. With the growing interest in the tight coupling of motion and task planning, one can expect to see their integration more prevalent in robotic deliberation systems.

Most planners in the analyzed systems handle time and concurrency. These are indeed important features which allows for simultaneous activities and synchronization with events in dynamic environments. Some systems deploy a temporal planning approach (e.g., IxTeT, RAX-PS, EUROPA, Aspen, TALPlanner) with state variables over timelines, while others have a narrower management of time as a resource (e.g., Cypress), or as a timed behavior extension to Hierarchical Constraint Automata for RMPL, and timeline management in XFRM. The simpler and more efficient state space task planning approaches are very relevant in many applications; it is unclear whether they can replace temporal planning altogether. Probabilistic and other nondeterministic planners have, for the moment, a narrower use, mostly at the sensory-motor level, e.g., within reinforcement learning approaches. Their integration in deliberation system will certainly be developed, in particular at the acting level. Finally, the predictive capability of the models in most of the surveyed planners remains quite narrow and limited. One should expect significant progress from simulation-based planning, e.g., with sampling search and receding horizon techniques.

A few of the analyzed systems consider planning primitives as executable commands; this limits the acting function mostly to reacting to events.

Most systems do, however, introduce a refinement level between planning primitives and commands. The majority use different knowledge representations for planning and acting. The exceptions are: RMPL, which relies on one model (hierarchical constraint automata with reactive programs) but provides limited planning capabilities; IDEA and T-REX, which proposes a single agent/reactor representation using state variables over timelines; and Cypress, which relies on the ACT interlingua as a rich programming environment for specifying both HTN planning domains and PRS acting procedures. However, the integration in ACT of planning and acting remains quite shallow, e.g., there is a de facto partition between planning methods and acting procedures.

This issue of an integrated representation between planning and acting is clearly a weak point in analyzed systems (except for IDEA and T-REX with their state variables hierarchy and the continuum between acting and planning). Such a representation should clarify the various refinement levels (at least two, possibly more) in terms of different state spaces and actions spaces and the relation between these spaces, e.g., the state space at a level i being a refinement of the more abstract level i -1, with a clear mapping from i to i -1 spaces.

As seen in Section 3, abstraction in planning has been extensively studied, mostly to reduce complexity; it remains to be extended at the architecture level and for different forms of plans and skills. This is needed for specification, verification of consistency, and integration of planning and acting knowledge.

Monitoring is the third function common to most analyzed systems. The link between planning and monitoring knowledge is well advanced. In a few cases, both rely on the same knowledge representation, e.g., Temporal Action Logic in the WITAS/TALPlan approach or Temporal Plan Networks in the RMPL system. The notion of monitoring formulas synthesized from plan invariants and from additional domain knowledge seems quite effective and should be more widely deployed in deliberation systems.

The integration of an observing function in the deliberation system is less frequent in the analyzed approaches. It is quite narrow in DS1/RAX and IxTeT-Reco (despite the common chronicle representation for planning and observing). It is more comprehensive in DyKnow. The interesting perception planning facilities in PTL, HiPPo and other systems discussed in section 6 and their integration to navigation and task planning have to be more widely developed and incorporated into deliberation systems.

A few of the analyzed systems offer some limited form of goal reasoning, notably DS1/RAX and Cypress. The incentives in terms of autonomy at the mission level were possibly less strong than they are today. Techniques such as those of ARTUE and others discussed in section 5.4 are certainly relevant in robotics and should be integrated in many deliberation systems.

Learning appears in only one of the analyzed systems: XFRM/RPL/CRAM. Our discussion in Section 7 indicates that learning is quite successful in robotics at the sensory-motor level. There will be significant progress in deliberation if more advances in different forms of reinforcement learning and learning from demonstration take place at the planning and acting levels. Meanwhile the techniques of Elvira [START_REF] Galindo | Robot Task Planning Using Semantic Maps[END_REF] for acquiring hierarchical semantic maps and using them in planning should be more widely used in rich environment robotics applications.

This last point is related to what we called Open Architectures and planning in open domains (Sec. 3.4), illustrated in the CRAM system, and, for some aspects, in WITAS (link to a Geographical Information System). Such an opening may not seem to be a radical change in representation and reasoning capabilities. It offers, however, a huge set of opportunities for adapting and extending deliberation models and dealing with complex environments. Most robotics deliberation systems should probably integrate similar capabilities.

Conclusion and Perspectives

Deliberate action is a central research issue in robotics. It is an issue motivated by critical capabilities needed by autonomous robots facing a variety of environments, tasks and interactions. Many applications in exploration, service, and personal robotics depend greatly on further progress and development of robotic deliberation capabilities.

Numerous contributions for the design of deliberation functions for a robot have been proposed. A few have been discussed in the preceding sections. The state of the art is broad and rich, but quite fragmented. The relationships between these fragments are not studied enough. It is indeed clear from our survey that only a few approaches take a global integrative view. One finds more results about how to speedup a given technique then comprehensive characterizations of that technique, how it complements other approaches, and how it can be integrated with them.

For the purpose of this survey, we have outlined six deliberation functions and discussed their requirements and characteristics. These functions may widely overlap in a given implementation. The rational for their organization within an operational architecture has to take into account numerous requirements, in particular a hierarchy of closed loops, from the most dynamic inner loop, closest to the sensory-motor functions, to the most external outer loop.

A critical aspect is the relationship between planning and acting. Acting cannot be reduced to the reactive triggering of sensory-motor commands mapped from planned actions or observed events. There is a need for significant deliberation between what is planned and the commands achieving it. This deliberation may even use different planning techniques, in particular motion, manipulation and other domain specific techniques. It has to be done in different yet well integrated state spaces, action spaces and event spaces. Although we insisted on distinguishing the two functions of acting and planning on top of the execution platform, there is no reason to believe that just three levels is the right number. There can be a hierarchy of planning-acting levels, each refining a task planned further up into more concrete actions, adapted to the acting context and foreseen events. It would be elegant to address this hierarchy within a homogeneous approach. However, conflicting requirements, e.g., for handling domain specific representations and different levels of nondeterminism, uncertainty and inaccuracy, favor a variety of representations and approaches.

Deliberation functions encompass other open issues that we have not discussed in this survey. Notable among them are the problems of interaction and social behavior. Interaction impacts all functions discussed here, from the observing requirements in a multi-modal dialogue, to planning and acting at the levels of task sharing and plan understanding for multi-robots and human-robot interaction.

In summary, the take home message of this survey is that: • deliberation in robotics does not reduce to task planning, • acting is a context and task dependent reaction to events and refinement of planned actions into commands, • hierarchy of action refinements over several levels of state and action spaces is essential,

• monitoring needs strong links to prediction in planning and acting,

• observing requires significant deliberation, it does not reduce to signal processing, • integrated and consistent representations and the acquisition of corresponding models are a clear bottleneck.

Future research directions emphasize representation, modeling and integration issues at various levels: • Descriptive models for task planning tend to favor the performance of search algorithms at the cost of shallow predictions. Often in robotics, available knowledge, changing environments and the type of missions do not allow for or require plans with thousands of actions, at a proper level of abstraction. The bottleneck is more on improving prediction capabilities of the models then on scaling up of search techniques. Promising directions include detailed simulation systems and sampling techniques. Heterogeneous knowledge representations can be desirable, although more difficult to integrate and verify. • Operational models for acting, to refine planned actions and react to events, have to lead to executable procedures, but they should not be just executable code. They should allow for several decision making functions, e.g., choice, instantiation, look-ahead, time and context handling, etc. Here also predictive capabilities are needed, but at a shorter range and in a closed loop with perception. • Open environment models and their relationship with descriptive and operational models for planning and acting offer exciting problems and perspectives. Robots do not need to reinvent the wheel. Their deliberation capabilities may build on communication and social mechanisms. • Model acquisition is certainly a bottleneck for deliberation functions. Most approaches surveyed in this paper demand strong robotics expertise for designing and structuring required models. Machine learning techniques are critical for the development of deliberative robots; they lead to numerous open problems. Learning should be combined with model synthesis from higher level specifications. For example, monitoring models should be synthesized from the operational and descriptive models for planning and acting.

• Model verification problems have also to be stressed, e.g., in order to relate operational models to descriptive models, hand-specified or learned. Consistency verification is harder with heterogeneous representations. In many cases, verification can be a powerful tool in model acquisition techniques. • The observing function and its integration with other deliberation functions involve very challenging open problems in deliberation robotics, covering a wide spectrum from anchoring to symbol grounding, from object recognition to functional categorization, and from semantic map building to situation and dynamic environment understanding.

• Finally, integration and architecture issues remain critical in the design of a deliberation system. The conceptual view of a few deliberation functions sharing knowledge and data and interacting with sensory-motor functions serves a clarifying purpose. It needs to be mapped into a more effective architecture whose organizational principle is a hierarchy of deliberation and sensory-motor functions relying on a hierarchy of clearly related representations and models, allowing for a plasticity of reconfiguration, as well as for sharing models and developments among roboticists as well as between robots.

Figure 1 :

 1 Figure 1: (a) Schematic view of deliberation functions (interactions between functions is oversimplified; more complex architectures are briefly discussed in Section 2.3); (b) Nested closed-loops implementing these functions.

Figure 2 :

 2 Figure 2: (a) An intervention robot (LAAS), (b) A rescue UAV (ONERA), (c) A user's assistant robot (LAAS).

Figure 3 :

 3 Figure 3: From actions to skills and commands.

Figure 4 :

 4 Figure 4: Example of an IxTeT chronicle modeling an action for a service robot.

Figure 5 :

 5 Figure 5: Model of a PickUp action with three state variables: Gripper, Right Arm, Manipulation Planner.

Fig. 2 .

 2 Fig. 2. The ingredients of anchoring in our framework. α is the anchor.

Fig. 1 .

 1 Fig. 1. Incremental processing for the traffic surveillance task.

Figure 7 :

 7 Figure 7: Dyknow processes for a UAV traffic surveillance task [101].

Table 1 :

 1

	Level of
	Autonomy

Features of a few classes of robotics applications (l: low, m: medium, h: high).

Table 2

 2

	: Analyzed systems, clustered into approaches and associated components, with their main deliberation functions (P: planning, A: acting,
	M: monitoring, O: observing, G: goal reasoning, L: learning) and other features.

Table 3 :

 3 Discussed systems.

		Deliberation Functions	Knowledge Representation	Robotics Domains	Additional Main Features
	SSP [146]	PA	Factorized MDP		Handling of uncertainty
	MDP [29]	PA	Factorized MDP		Handling of uncertainty
	MAPL [31]	PA	State Variables	Service robots	Multi-robot integration
			Belief Variables
			Assertions
	DL/HTN [96]	PA	DL and HTN		Service robots
	RACE [186]	P	HTN		Service and domestic	Open models
					robots
	Petri-Net [221]	A	Petri Net
	SMACH [24]	A	Automata		Service robots	ROS
	Readylog [71]	PA	Situation Calculus			Logical Framework
	Pearl [171]	PA	MDP		Service robots	Handling of uncertainty
	Ressac [207]	PA	MDP		UAV	Handling of uncertainty
	Coradeschi [53]	PO	Perceptual choring	an-	Service robots, UAV	Tracking and reacquiring anchors integrated to planning
	PTL [115]	PO	Ambigous		Service robots	Partial matching properties -fea-
			anchors with con-		tures, definite and indefinite de-
			ditional planning		scriptions
			in belief space
	HiPPo [203]	PO	Hierarchical		Object manipulation	Sensor and manipulation planning
			POMDP
	Velez [214]	PO	Bayes network	Service robots	Observation planning and naviga-
						tion
	Elvira [84]	POL	Semantic Maps	Service robots	Hierarchical environment models
	Astrid [83]	POL	Semantic Maps	Service robots	Integration to planning & acting

Table 4 :

 4 embed a motion planner used in

	Approaches	Systems Open or	Horizon Nondeterminism	Concur-rency	Solution Plan	Knowledge Represen-	Search Algorithm	Integration with other
			Closed				tation		deliberation
			Loop						functions
		IxTeT	Open	Indefinite Deterministic	yes	Flexible	State vari-	Temporal	Acting with
		[89]					ables,	in	plan	IxTeT-eXeC
							time-points	space	monitor-
									ing	with
									IxTeT-Reco
		PS	Open	Indefinite Deterministic	yes	Flexible	State vari-	Temporal	Acting,
	Temporal	[110]					ables,	in	plan	monitoring
	planning						intervals	space	and	goal
									reasoning
		EUROPA	Open	Indefinite Deterministic	yes	Flexible	State vari-	Temporal	Acting (see
		[79]					ables,	in	plan	IDEA	&
							intervals	space	T-REX)
		APSI	Open	Indefinite Deterministic	yes	Flexible	State vari-	Temporal	Acting with
		[81]					ables,	in	plan	T-REX
							intervals	space
		ASPEN	Open	Indefinite Deterministic	yes	Completely	State vari-	Local	Acting (see
		[178]				instantiated	ables,	search	CASPER)
							intervals
		SSP	Closed	Indefinite Nondeterministic no	Partial pol-	MDP	Heuristic	Acting
		[146]				icy		and sam-
	Probabilistic Planning	[206] RFF	Closed	Receding Nondeterministic no	icy Partial pol-	MDP	pling Heuristic	Acting
		MCP	Closed	Mixed	no	Partial pol-	Factorized	Compressed	Acting
		[141]				icy	MDP	determin-
								istic part
		MAPL	Closed	Indefinite Delayed	no	Assertions	State vari-	Classical	Mixed plan-
		[31]				to be refined	ables, belief		ning/acting
							variables,
	Open World Planning	Hartanto [96]	Open	Indefinite Deterministic	no	Completely instantiated	assertions HTN, DL	DL rea-soning,
								HTN
		Race	Open	Indefinite Deterministic	no	Completely	HTN	HTN	Commu-
		[186]				instanciated			nication
									using Black-
									Board

Surveyed planning systems: main features, knowledge representations, algorithms and links with other deliberation functions.

In the terminology of task planning, a motion planner is domain-specific even if it is applicable to a wide diversity of robots and environments.

An MDP with n k-ary state variables has a state space in k n ; a POMDP is an MDP on the belief space whose discritized size is in 2 k n .

Some take the less restrictive view of "negation by failure": a fact not entailed from explicit statements is false.

ROS "actions" on a PR2 correspond to platform commands in our terminology.

Acknowledgments

We are very grateful to the anonymous reviewers and to the editors of this special issue for their thorough reading and insightful comments, which contributed to improving this paper. Many thanks to several colleagues, in particular Wheeler Ruml and Frédéric Py for their very helpful technical and editorial feedback. This work was supported in part by EU FP7 SAPHARI under grant agreement No. ICT-287513.

Functions Knowledge Representation

Approaches Systems

Refinement

Instantiation

Time handling

Nondet. Repair Specification V&V Shared P/A KR Direct Planex [START_REF] Fikes | Monitored Execution of Robot Plans Produced by STRIPS[END_REF] Model X Procedure RAP [START_REF] Firby | An investigation into reactive planning in complex domains[END_REF] X X Program PRS [START_REF] Ingrand | PRS: a high level supervision and control language for autonomous mobile robots[END_REF] X X Program Cypress/CPEF [223] X X Program ACT TCA/TDL [START_REF] Simmons | A task description language for robot control[END_REF] X

Table 6: Surveyed acting systems: main functions (reaction to events omitted since present in all systems) and knowledge representation.

appropriate skill according to the current context. The system commits to the goals it has to achieve, trying a different skill when one fails. RAP was interfaced with the AP [START_REF] Bonasso | Experiences with an Architecture for Intelligent, Reactive Agents[END_REF] and PRODIGY [215] planners. PRS (Procedural Reasoning System) [START_REF] Ingrand | PRS: a high level supervision and control language for autonomous mobile robots[END_REF] is a procedure-based action refinement and monitoring system. As in RAP, one writes skills (Operational Procedures) to achieve goals or react to particular events and observations. The system commits to goals and tries alternative skills when needed. Procedures share a database of facts and goals. PRS allows for concurrent procedure execution and multi-threading. Some planning capabilities were added to PRS [START_REF] Despouys | Propice-Plan: Toward a Unified Framework for Planning and Execution[END_REF] to anticipate execution paths leading to failure, by simulating the execution of procedures and exploring the different branches. A more advanced integration of a planner to PRS was later developed with IxTeT [START_REF] Lemai-Chenevier | Interleaving Temporal Planning and Execution in Robotics Domains[END_REF] (Sec. 4.5). PRS is used in numerous robotics platforms. PRS skills refine actions into lower level commands (e.g., ROS "actions" for a PR2). Procedure steps are subgoals, possibly executed concurrently, within conditional and control structures, monitoring and recovery instructions. When integrated with GenoM (a generator of sensory-motor modules [START_REF] Fleury | GenoM: A Tool for the Specification and the Implementation of Operating Modules in a Distributed Robot Architecture[END_REF]), PRS procedures handling the robot commands are generated automatically [START_REF] Ingrand | Decisional autonomy of planetary rovers[END_REF].

TCA [START_REF] Simmons | Concurrent planning and execution for autonomous robots[END_REF][START_REF] Simmons | Structured control for autonomous robots[END_REF] was initially developed to handle concurrent planning and acting. It provides a hierarchical task decomposition framework, with explicit temporal constraints to allow tasks synchronization. Task decomposition integrates specific geometrical and motion planning (e.g., gait and footfall planning for the Ambler robot). The Task Definition Language (TDL) [START_REF] Simmons | A task description language for robot control[END_REF] extends TCA with a wide range of synchronization constructs between tasks. It focuses on task execution and relies on systems like Casper/Aspen for planning.

XFRM [START_REF] Beetz | Improving Robot Plans During Their Execution[END_REF] illustrates another approach which uses transformation rules to modify hand written plans expressed in the Reactive Plan Language (RPL). Unlike the above systems, it searches in plan space to improve its skills, using simulation and probabilities of possible outcomes. It replaces the currently executed plan on the fly if it finds another one more adapted to the current situation. This approach evolved toward Structured Reactive Controllers (SRC) and Structure Reactive Plan (SRP) [START_REF] Beetz | Structured reactive controllers: controlling robots that perform everyday activity[END_REF], but still retains the XFRM technique to perform planning using transformation rules on SRP. It has been deployed on several prototype service robots.

Other similar procedure based approaches have been successfully deployed, such as IPEM [START_REF] Ambros-Ingerson | Integrating Planning, Execution and Monitoring[END_REF], EXEC on DS1/RAX [START_REF] Muscettola | Remote Agent: to boldly go where no AI system has gone before[END_REF], PRS-Lite [START_REF] Myers | A procedural knowledge approach to task-level control[END_REF], which offers a richer goal semantics than the regular PRS, Cypress [223] and