Interleaving Planning and Robot Execution for Asynchronous User Requests

ROGUE is an architecture built on a real robot which provides algorithms for the integration of high-level planning, low-level robotic execution, and learning. ROGUE addresses successfully several of the challenges of a dynamic office gopher environment. This article presents the techniques for the integration of planning and execution.ROGUE uses and extends a classical planning algorithm to create plans for multiple interacting goals introduced by asynchronous user requests. ROGUE translates the planner';s actions to robot execution actions and monitors real world execution. ROGUE is currently implemented using the PRODIGY4.0 planner and the Xavier robot. This article describes how plans are created for multiple asynchronous goals, and how task priority and compatibility information are used to achieve appropriate efficient execution. We describe how ROGUE communicates with the planner and the robot to interleave planning with execution so that the planner can replan for failed actions, identify the actual outcome of an action with multiple possible outcomes, and take opportunities from changes in the environment.ROGUE represents a successful integration of a classical artificial intelligence planner with a real mobile robot.     

Managing uncertainty in time-critical plan evaluation

In complex real-world domains, uncertainty in predicting the results of plan execution drives the evaluation component of the planning cycle to explore a combinatorial explosion of alternative futures. This evaluation component is critical in evaluating the feasibility, strengths and weaknesses of a proposed plan. In time critical situations the planner is thus faced with a trade-off between timeliness and evaluation completion. Furthermore, a human planner is faced with the additional problem of evaluation credibility when using fast automatic evaluation in a complex and uncertain domain. An approach to handling these problems of time-criticality, uncertainty, and credibility is explored using the wargaming component of the military operational planning cycle. The Semi-Automated Forces Wargamer has been developed using two techniques. The first technique integrates procedural representations of plans and intentions with heuristic representations of simulated probabilistic execution. This facilitates the simulated execution of plans with multiple worlds corresponding to the possible results of actions taken in the real and uncertain world. The second provides a what-if capability via a tree representation of the possible combat outcomes. This provides the user with a tool for intelligent and focussed exploration of the space of possible outcomes to the plan. These techniques combine to generate a manageable and useful subset of the space of simulated plan results from which the user can apply human expertize to guide plan exploration.     

Task planning under uncertainty using a spreading activationnetwork

As robotics and automation applications extend to the service sector, researchers have to increasingly deal with performing robotic actions in uncertain and unstructured environments. A traditional solution to this problem models uncertainty about the effects of actions by probabilities conditioned on the state of the environment, making it possible to select plans that have the highest probability of success in a given situation. Reactive systems use another approach to handling uncertainty, by employing a set of predefined situation-response rules that make it possible to move toward the goal from any situation, whether expected or unexpected. This paper describes a planner that combines the two approaches. A proactive component generates plans that are biased toward picking the most reliable action in a given situation, and a reactive component can alter the selected actions based on unexpected situations that may arise in uncertain environments. Action selection is driven by a spreading activation mechanism on a probabilistic network that encodes the domain knowledge. A decision-theoretic framework incorporates quantitative goal utilities and action costs into the action selection mechanism. Experiments conducted demonstrate the ability of the planner to plan with hard and soft domain constraints and action costs, modify plans as a reaction to unexpected changes in the environment or goal utilities, and plan in situations with multiple conflicting goals     

An architecture for a self-improving instructional planner for intelligent tutoring systems

Machine instructional planners use changing and uncertain data to incrementally configure plans and control the execution and dynamic refinement of these plans. Current instructional planners cannot adequately plan, replan, and monitor the delivery of instruction. This is due in part to the fact that current instructional planners are incapable of planning in a global context, developing competing plans in parallel, monitoring their planning behavior, and dynamically adapting their control behavior. In response to these and other deficiencies of instructional planners a generic system architecture based on the blackboard model was implemented. This self-improving instructional planner (SUP) dynamically creates instructional plans, requests execution of these plans, replans, and improves its planning behavior based on a student's responses to tutoring. Global planning was facilitated by explicitly representing decisions about past, current, and future plans on a global data structure called the plan blackboard. Planning in multiple worlds is facilitated by labeling plan decisions by the context in which they were generated. Plan monitoring was implemented as a set of monitoring knowledge sources. The flexible control capability for instructional planner was adapted from the blackboard architecture BB1. The explicit control structure of SUP enabled complex and flexible planning behavior while maintaining a simple planning architecture.     

Decisional autonomy of planetary rovers

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

Recovering from execution errors in SIPE

In real-world domains (e.g., a mobile robot environment), things do not always proceed as planned, so it is important to develop better execution-monitoring techniques and replanning capabilities. This paper describes these capabilities in the SIPE (System for Interactive Planning and Execution Monitoring) planning system. The motivation behind SIPE is to place enough limitations on the representation so that planning can be done efficiently, while retaining sufficient power to still be useful. This work assumes that new information given to the execution monitor is in the form of predicates, thus avoiding the difficult problem of how to generate these predicates from information provided by sensors.
The replanning module presented here takes advantage of the rich structure of SIPE plans and is intimately connected with the planner, which can be called as a subroutine. This allows the use of SIPE's capabilities to determine efficiently how unexpected events affect the plan being executed and, in many cases, to retain most of the original plan by making changes in it to avoid problems caused by these unexpected events. SIPE is also capable of shortening the original plan when serendipitous events occur. A general set of replanning actions is presented along with a general replanning capability that has been implemented by using these actions.     

Planning in highly dynamic environments: an anytime approach for planning under time constraints

In this paper, we present a novel and domain-independent planner aimed at working in highly dynamic environments with time constraints. The planner follows the anytime principles: a first solution can be quickly computed and the quality of the final plan is improved as long as time is available. This way, the planner can provide either fast reactions or very good quality plans depending on the demands of the environment. As an on-line planner, it also offers important advantages: our planner allows the plan to start its execution before it is totally generated, unexpected events are efficiently tackled during execution, and sensing actions allow the acquisition of required information in partially observable domains. The planning algorithm is based on problem decomposition and relaxation techniques. The traditional relaxed planning graph has been adapted to this on-line framework by considering information about sensing actions and action costs. Results also show that our planner is competitive with other top-performing classical planners.     

Autonomous Driving with Concurrent Goals and Multiple Vehicles: Mission Planning and Architecture

We introduce a new distributed planning paradigm, which permits optimal execution and dynamic replanning of complex multi-goal missions. In particular, the approach permits dynamic allocation of goals to vehicles based on the current environment model while maintaining information-optimal route planning for each individual vehicle to individual goals. Complex missions can be specified by using a grammar in which ordering of goals, priorities, and multiple alternatives can be described. We show that the system is able to plan local paths in obstacle fields based on sensor data, to plan and update global paths to goals based on frequent obstacle map updates, and to modify mission execution, e.g., the assignment and ordering of the goals, based on the updated paths to the goals.The multi-vehicle planning system is based on the GRAMMPS planner; the on-board dynamic route planner is based on the D* planner. Experiments were conducted with stereo and high-speed ladar as the to sensors used for obstacle detection. This paper focuses on the multi-vehicle planner and the systems architecture. A companion paper (Brumitt et al., 2001) analyzes experiments with the multi-vehicle system and describes in details the other components of the system.     

Landmark-based heuristic online contingent planning

In contingent planning problems, agents have partial information about their state and use sensing actions to learn the value of some variables. When sensing and actuation are separated, plans for such problems can often be viewed as a tree of sensing actions, separated by conformant plans consisting of non-sensing actions that enable the execution of the next sensing action. We propose a heuristic, online method for contingent planning which focuses on identifying the next useful sensing action. We select the next sensing action based on a landmark heuristic, adapted from classical planning. We discuss landmarks for plan trees, providing several alternative definitions and discussing their merits. The key part of our planner is the novel landmarks-based heuristic, together with a projection method that uses classical planning to solve the intermediate conformant planning problems. The resulting heuristic contingent planner solves many more problems than state-of-the-art, translation-based online contingent planners, and in most cases, much faster, up to 3 times faster on simple problems, and 200 times faster on non-simple domains.     

实时专家系统中反应—规划—动作的集成

以AMPE模型为基础,探讨了在动态环境下AI系统如何集成响应执行和规划生成的问题。AMPE模型是从实际应用中演化出的AI模型,采用分离结构,在规划中引入一类被称为观察点的特殊行为,支持异步重规划。描述了AMPE的各类规划行为的形式和消息的基本结构。给出一个规划表示的实例。     

Real-World Robotics: Learning to Plan for Robust Execution

In executing classical plans in the real world, small discrepancies between a planner's internal representations and the real world are unavoidable. These can conspire to cause real-world failures even though the planner is sound and, therefore, proves that a sequence of actions achieves the goal. Permissive planning, a machine learning extension to classical planning, is one response to this difficulty. This paper describes the permissive planning approach and presents GRASPER, a permissive planning robotic system that learns to robustly pick up novel objects.     

TOLERANT PLANNING AND NEGOTIATION IN MULTIAGENT ENVIRONMENTS

Tolerant planning improves the likelihood of plans being successfully executed despite uncertainties and changes during execution. By tolerating execution errors, dynamic replanning need not be invoked as often or as immediately as in a less tolerant plan. The approach in designing tolerant plans is to allow for redundancies in the requirements (usually resources) for execution. While this approach is feasible, it raises another problem—more conflicts must be resolved during planning. This conflict resolution problem can be solved using a novel model of iterative negotiation for multiagent coordination. It requires agents to be skillful in negotiating with other agents to resolve conflicts in such a way as to minimize compromising their own tolerance while being benevolent in helping others find a feasible plan. This paper also describes an application of these concepts in a planner that generates conflict-free movement schedules for several mobile robots in a factory domain.     

Adaptive continuous‐space informative path planning for online environmental monitoring

Autonomous mobile robots are increasingly employed to take measurements for environmental monitoring, but planning informative, measurement‐rich paths through large three‐dimensional environments is still challenging. Designing such paths, known as the informative path planning (IPP) problem, has been shown to be NP‐hard. Existing algorithms focus on providing guarantees on suboptimal solutions, but do not scale well to large problems. In this paper, we introduce a novel IPP algorithm that uses an evolutionary strategy to optimize a parameterized path in continuous space, which is subject to various constraints regarding path budgets and motion capabilities of an autonomous mobile robot. Moreover, we introduce a replanning scheme to adapt the planned paths according to the measurements taken in situ during data collection. When compared to two state‐of‐the‐art solutions, our method provides competitive results at significantly lower computation times and memory requirements. The proposed replanning scheme enables to build models with up to 25% lower uncertainty within an initially unknown area of interest. Besides presenting theoretical results, we tailored the proposed algorithms for data collection using an autonomous surface vessel for an ecological study, during which the method was validated through three field deployments on Lake Zurich, Switzerland. Spatiotemporal variations are shown over a period of three months and in an area of 350 m × 350 m × 13 m. Whereas our theoretical solution can be applied to multiple applications, our field results specifically highlight the effectiveness of our planner for monitoring toxic microorganisms in a pre‐alpine lake, and for identifying hot‐spots within their distribution.     

Coordinated execution of tasks in a multiagent environment

This correspondence describes the application of discrete event control methods to provide conflict-free plan execution in a multiagent environment. This work uses planning methods to generate plans for multiple robots, and the plans are then compiled into Petri nets for analysis, execution, and monitoring. Supervisory control techniques are applied to the Petri net controller for the purpose of dealing with conflicts that arise due to the presence of shared resources. Furthermore, by preserving the state of the system replanning can occur at any time during execution to deal with unforeseen events.     

Incorporating decision-theoretic planning in a robot architecture

The goal of robotics research is to design a robot to fulfill a variety of tasks in the real world. Inherent in the real world is a high degree of uncertainty about the robot’s behavior and about the world. We introduce a robot task architecture, DTRC, that generates plans with actions that incorporate costs and uncertain effects, and states that yield rewards.The use of a decision-theoretic planner in a robot task architecture is demonstrated on the mobile robot domain of miniature golf. The miniature golf domain shows the application of decision-theoretic planning in an inherently uncertain domain, and demonstrates that by using decision-theoretic planning as the reasoning method in a robot task architecture, accommodation for uncertain information plays a direct role in the reasoning process.     

Learning Hierarchical Task Models from Input Traces

We describe HTN‐MAKER , an algorithm for learning hierarchical planning knowledge in the form of task‐reduction methods for hierarchical task networks (HTNs). HTN‐MAKER takes as input a set of planning states from a classical planning domain and plans that are applicable to those states, as well as a set of semantically annotated tasks to be accomplished. The algorithm analyzes this semantic information to determine which portion of the input plans accomplishes a particular task and constructs task‐reduction methods based on those analyses. We present theoretical results showing that HTN‐MAKER is sound and complete. Our experiments in five well‐known planning domains confirm the theoretical results and demonstrate convergence toward a set of HTN methods that can be used to solve any problem expressible as a classical planning problem in that domain, relative to a set of goal types for which tasks have been defined. In three of the five domains, HTN planning with the learned methods scales much better than a modern classical planner.     

A logic-based agent that plans for extended reachability goals

Planning to reach a goal is an essential capability for rational agents. In general, a goal specifies a condition to be achieved at the end of the plan execution. In this article, we introduce nondeterministic planning for extended reachability goals (i.e., goals that also specify a condition to be preserved during the plan execution). We show that, when this kind of goal is considered, the temporal logic ctl turns out to be inadequate to formalize plan synthesis and plan validation algorithms. This is mainly due to the fact that the ctl’s semantics cannot discern among the various actions that produce state transitions. To overcome this limitation, we propose a new temporal logic called α-ctl. Then, based on this new logic, we implement a planner capable of synthesizing reliable plans for extended reachability goals, as a side effect of model checking.     

Planning for mechatronics systems—Architecture, methods and case study

Mechatronic systems are a relatively new class of technical systems. The integration of electro-mechanical systems with hard- and software enables systems that adapt to changing operation conditions and externally defined objective functions. To gain superior system performance from this ability, sophisticated decision making processes are required. Planning is an ideal method to integrate long-term considerations beyond the time horizon of classical controlled systems into the decision making process. Unfortunately, planning employs discrete models, while mechatronic systems or controlled systems in general emphasize the time continuous behavior of processes. As a result, deviations of the actual behavior during the execution from the planned behavior plan cannot be entirely avoided. We introduce a hybrid planning architecture, which combines planning and learning from artificial intelligence with simulation techniques to optimize the general system behavior. The presented approach is able to handle the inevitable deviations during plan execution, and thus maintains feasibility and quality of the created plans.