Group planning with time constraints

Embedding planning systems in real-world domains has led to the necessity of Distributed Continual Planning (DCP) systems where planning activities are distributed across multiple agents and plan generation may occur concurrently with plan execution. A key challenge in DCP systems is how to coordinate activities for a group of planning agents. This problem is compounded when these agents are situated in a real-world dynamic domain where the agents often encounter differing, incomplete, and possibly inconsistent views of their environment. To date, DCP systems have only focused on cases where agents’ behavior is designed to optimize a global plan. In contrast, this paper presents a temporal reasoning mechanism for self-interested planning agents. To do so, we model agents’ behavior based on the Belief-Desire-Intention (BDI) theoretical model of cooperation, while modeling dynamic joint plans with group time constraints through creating hierarchical abstraction plans integrated with temporal constraints network. The contribution of this paper is threefold: (i) the BDI model specifies a behavior for self interested agents working in a group, permitting an individual agent to schedule its activities in an autonomous fashion, while taking into consideration temporal constraints of its group members; (ii) abstract plans allow the group to plan a joint action without explicitly describing all possible states in advance, making it possible to reduce the number of states which need to be considered in a BDI-based approach; and (iii) a temporal constraints network enables each agent to reason by itself about the best time for scheduling activities, making it possible to reduce coordination messages among a group. The mechanism ensures temporal consistency of a cooperative plan, enables the interleaving of planning and execution at both individual and group levels. We report on how the mechanism was implemented within a commercial training and simulation application, and present empirical evidence of its effectiveness in real-life scenarios and in reducing communication to coordinate group members’ activities.     

Dynamic consistency of fuzzy conditional temporal problems

Conditional Temporal Problems (CTPs) can deal simultaneously with uncertainty and temporal constraints, allowing for the representation of temporal and conditional plans. CTPPs generalize CTPs by adding preferences to the temporal constraints and by allowing fuzzy thresholds for the occurrence of some events. Here we focus on dynamic consistency of CTPPs, the most useful notion of consistency in practice. We describe an algorithm which allows for testing if a CTPP is dynamically consistent and we study its complexity. Simple temporal problems with preferences and uncertainty (STPPUs) are another formalism to model temporal constraints where preference and uncertainty coexist. While uncertainty is CTPPs is modeled via conditions on the execution of variables, in STPPUs it is modelled by means of events whose occurrence time is not known. We consider the relation between CTPPs and STPPUs and we show that the former framework is at least as expressive as the second one. Such a result is obtained by providing a polynomial mapping from STPPUs to CTPPs.     

General Temporal Knowledge for Planning and Data Mining

We consider the architecture of systems that combine temporal planning and plan execution and introduce a layer of temporal reasoning that potentially improves both the communication between humans and such systems, and the performance of the temporal planner itself. In particular, this additional layer simultaneously supports more flexibility in specifying and maintaining temporal constraints on plans within an uncertain and changing execution environment, and the ability to understand and trace the progress of plan execution. It is shown how a representation based on single set of abstractions of temporal information can be used to characterize the reasoning underlying plan generation and execution interpretation. The complexity of such reasoning is discussed.     

Cooperation Requirements Planning (CRP) for multiprocessors: Optimal assignment and execution planning

Cooperation is considered an essential attribute of intelligent multi-machine systems. It enhances their flexibility and reliability. Cooperation Requirement Planning (CRP) is the process of generating a consistent and coordinated global execution plan for a set of tasks to be completed by a multi-machine system based on the task cooperation requirements and interactions. CRP is divided into two steps: CRP-I which matches the task requirements to machine and system capabilities to generate cooperation requirements. It also generates task precedence, machine operation, and system resource constraints. CRP-II uses the cooperation requirements and various constraints to generate a task assignment and coordinated and consistent global execution plan. The global execution plan specifies an ordered sequence of actions and the machine sets that execute them such that the assigned tasks are successfully completed, all the constraints are resolved, and the desired performance measure optimized.In this paper, we describe the CRP-II methodology based on the concepts of planning for multiple goals with interactions. Each task is considered to be a goal, and the CRP-I process is viewed as generating alternate plans and associated costs to accomplish each goal. Five different interactions are specified between the various plans: action combination, precedence relation, resource sharing, cooperative action, and independent action. The CRP-II process is viewed as selecting a plan to satisfy each goal and resolving the interactions between them. A planning strategy is proposed which performs plan selection and interaction resolution simultaneously using a best-first search process to generate the optimal global plan.     

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.     

Conformant plans and beyond: Principles and complexity

Conformant planning is used to refer to planning for unobservable problems whose solutions, like classical planning, are linear sequences of operators called linear plans. The term ‘conformant’ is automatically associated with both the unobservable planning model and with linear plans, mainly because the only possible solutions for unobservable problems are linear plans. In this paper we show that linear plans are not only meaningful for unobservable problems but also for partially-observable problems. In such case, the execution of a linear plan generates observations from the environment which must be collected by the agent during the execution of the plan and used at the end in order to determine whether the goal had been achieved or not; this is the typical case in problems of diagnosis in which all the actions are knowledge-gathering actions.Thus, there are substantial differences about linear plans for the case of unobservable or fully-observable problems, and for the case of partially-observable problems: while linear plans for the former model must conform with properties in state space, linear plans for partially-observable problems must conform with properties in belief space. This differences surface when the problems are allowed to express epistemic goals and conditions using modal logic, and place the plan-existence decision problem in different complexity classes.Linear plans is one extreme point in a discrete spectrum of solution forms for planning problems. The other extreme point is contingent plans in which there is a branch point for every possible observation at each time step, and thus the number of branch points is not bounded a priori. In the middle of the spectrum, there are plans with a bounded number of branch points. Thus, linear plans are plans with zero branch points and contingent plans are plans with unbounded number of branch points.In this work, we lay down foundations and principles for the general treatment of linear plans and plans of bounded branching, and provide exact complexity results for novel decision problems. We also show that linear plans for partially-observable problems are not only of theoretical interest since some challenging real-life problems can be dealt with them.     

Verifying plans for multiple agents

Abstract

Research in distributed artificial intelligence planning has historically focused on two distinct classes of problems. One paradigm has been that of 'planning for multiple agents', which considers issues inherent in centrally directed multi-agent execution. The second paradigm has been 'distributed planning', where multiple agents more autonomously participate in coordinating and deciding upon their own actions. The work described in this paper is in the first category, planning for multiple agents. Taking the STRIPS representation of actions, and directed acrylic graphs (DAGs) as plan representations particularly well suited to parallel execution, it formally analyses the following question: how can a DAG plan be verified (i.e. how can we be sure such a plan will be correct, given our uncertainty about exactly when unconstrained parallel actions will be performed)? A method is presented for verifying the correctness of plans for multiple agents, represented as DAGs. The technique allows for the efficient analysis of a plan, despite its many potential execution histories.     

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.     

A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems

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

Exploiting temporal coherence in nonlinear plan construction

Correct conventional nonlinear planners operate in accordance with Chapman's modal truth criterion (MTC). The MTC characterizes the conditions under which an assertion will be true at a point in a nonlinear plan. However, the MTC is not all one requires in order to build a realistic planning system: it merely sanctions the use of a number of plan modifications in order to achieve each assertion in a developing plan. The number of modifications that can be made is usually very large. To avoid breadth-first search a planner must have some idea of which plan modification to consider. We describe a domain-independent search heuristic called temporal coherence , which helps guide the search through the space of partial plans defined by the MTC. Temporal coherence works by suggesting certain orderings of goal achievement as more appealing than others, and thus by finding bindings for plan variables consistent with the planner's overall goals. Our experience with a real nonlinear planner has highlighted the need for such a heuristic. In this paper, we give an example planning problem and use it to illustrate how temporal coherence can speed the search for an acceptable plan. We also prove that if a solution exists in the partial plan search space defined by the MTC, then there exists a path to that solution which is sanctioned by temporal coherence.     

Hierarchical planning involving deadlines, travel time, and resources

This paper describes a planning architecture that supports a form of hierarchical planning well suited to applications involving deadlines, travel time, and resource considerations. The architecture is based upon a temporal database, a heuristic evaluator, and a decision procedure for refining partial plans. A partial plan consists of a set of tasks and constraints on their order, duration, and potential resource requirements. The temporal database records the partial plan that the planner is currently working on and computes certain consequences of that information to be used in proposing methods to further refine the plan. The heuristic evaluator examines the space of linearized extensions of a given partial plan in order to reject plans that fail to satisfy basic requirements (e.g., hard deadlines and resource limitations) and to estimate the utility of plans that meet these requirements. The information provided by the temporal database and the heuristic evaluator is combined using a decision procedure that determines how best to refine the current partial plan. Neither the temporal database nor the heuristic evaluator is complete and, without reasonably accurate information concerning the possible resource requirements of the tasks in a partial plan, there is a significant risk of missing solutions. A specification language that serves to encode expectations concerning the duration and resource requirements of tasks greatly reduces this risk, enabling useful evaluations of partial plans. Details of the specification language and examples illustrating how such expectations are exploited in decision making are provided.     

LEARNING AND VERIFYING SAFETY CONSTRAINTS FOR PLANNERS IN A KNOWLEDGE‐IMPOVERISHED SYSTEM

We present a Bayesian approach to learning flexible safety constraints and subsequently verifying whether plans satisfy these constraints. Our approach, called the Safety Constraint Learner/Checker (SCLC), infers safety constraints from a single expert demonstration trace and minimal background knowledge, and applies these constraints to the solutions proposed by multiple planning agents in an integrated and heterogeneous ensemble. The SCLC calculates how much to blame plan fragments (partial solutions) generated by the individual planning agents. This information is used when composing these fragments into a final overall plan. In particular, fragments whose safety violations exceed a threshold are rejected. This facilitates the generation of safe plans. We have integrated the SCLC within the Generalized Integrated Learning Architecture, which was designed for Defense Advanced Research Projects Agency (DARPA)’s Integrated Learning (IL) program. The main goal of the IL program is to promote the development and success of sophisticated systems that learn to solve challenging real‐world problems based on a simple demonstration by a human expert and exiguous domain knowledge. We present experimental results showing the advantages of the SCLC on two multiagent problem‐solving tasks that were benchmark applications in DARPA’s IL program.     

Planning and execution through variable resolution planning

Generating sequences of actions–plans–for robots using Automated Planning in stochastic and dynamic environments has been shown to be a difficult task with high computational complexity. These plans are composed of actions whose execution might fail due to different reasons. In many cases, if the execution of an action fails, it prevents the execution of some (or all) of the remainder actions in the plan. Therefore, in most real-world scenarios computing a complete and sound (valid) plan at each (re-)planning step is not worth the computational resources and time required to generate the plan. This is specially true given the high probability of plan execution failure. Besides, in many real-world environments, plans must be generated fast, both at the start of the execution and after every execution failure. In this paper, we present Variable Resolution Planning which uses Automated Planning to quickly compute a reasonable (not necessarily sound) plan. Our approach computes an abstract representation–removing some information from the planning task–which is used once a search depth of $k$ steps has been reached. Thus, our approach generates a plan where the first $k$ actions are applicable if the domain is stationary and deterministic, while the rest of the plan might not be necessarily applicable. The advantages of this approach are that it: is faster than regular full-fledged planning (both in the probabilistic or deterministic settings); does not spend much time on the far future actions that probably will not be executed, since in most cases it will need to replan before executing the end of the plan; and takes into account some information of the far future, as an improvement over pure reactive systems. We present experimental results on different robotics domains that simulate tasks on stochastic environments.     

AN EVALUATION OF THE TEMPORAL COHERENCE HEURISTIC IN PARTIAL-ORDER PLANNING

This paper presents an evaluation of a heuristic for partial-order planning, known as temporal coherence. The temporal coherence heuristic was proposed by Drummond and Currie as a method to improve the efficiency of partial-order planning without losing the ability to find a solution (i.e., completeness). It works by using a set of domain constraints to prune away plans that do not "make sense," or are temporally incoherent. Our analysis shows that, while intuitively appealing, temporal coherence can only be applied to a very specific implementation of a partial-order planner and still maintain completeness. Furthermore, the heuristic does not always improve planning efficiency; in some cases, its application can actually degrade the efficiency of planning dramatically. To understand when the heuristic will work well, we conducted complexity analysis and empirical tests. Our results show that temporal coherence works well when strong domain constraints exist that significantly reduce the search space, when the number of subgoals is small, when the plan size is not too large, and when it is inexpensive to check each domain constraint.     

Planning for temporally extended goals

In planning, goals have traditionally been viewed as specifying a set of desirable final states. Any plan that transforms the current state to one of these desirable states is viewed to be correct. Goals of this form are limited in what they can specify, and they also do not allow us to constrain the manner in which the plan achieves its objectives. We propose viewing goals as specifying desirable sequences of states, and a plan to be correct if its execution yields one of these desirable sequences. We present a logical language, a temporal logic, for specifying goals with this semantics. Our language is rich and allows the representation of a range of temporally extended goals, including classical goals, goals with temporal deadlines, quantified goals (with both universal and existential quantification), safety goals, and maintenance goals. Our formalism is simple and yet extends previous approaches in this area. We also present a planning algorithm that can generate correct plans for these goals. This algorithm has been implemented, and we provide some examples of the formalism at work. The end result is a planning system which can generate plans that satisfy a novel and useful set of conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于STN的计划执行过程时间冲突检测与消解*

计划执行过程中,各种不确定因素常常引起时间约束的违背.为维护计划的时间一致性,利用STN表示时间约束,分析了由于活动的提前或延迟导致的两种时间冲突,给出了冲突判定定理,在此基础上通过松弛冲突路径上某些约束来消解冲突;最后通过一个计划案例的仿真验证了本方法能够有效检测和消解执行过程中的时间冲突.     

On the predictability of domain‐independent temporal planners

Temporal planning is a research discipline that addresses the problem of generating a totally or a partially ordered sequence of actions that transform the environment from some initial state to a desired goal state, while taking into account time constraints and actions' duration. For its ability to describe and address temporal constraints, temporal planning is of critical importance for a wide range of real‐world applications. Predicting the performance of temporal planners can lead to significant improvements in the area, as planners can then be combined in order to boost the performance on a given set of problem instances. This paper investigates the predictability of the state‐of‐the‐art temporal planners by introducing a new set of temporal‐specific features and exploiting them for generating classification and regression empirical performance models (EPMs) of considered planners. EPMs are also tested with regard to their ability to select the most promising planner for efficiently solving a given temporal planning problem. Our extensive empirical analysis indicates that the introduced set of features allows to generate EPMs that can effectively perform algorithm selection, and the use of EPMs is therefore a promising direction for improving the state of the art of temporal planning, hence fostering the use of planning in real‐world applications.     

Constraint partitioning in penalty formulations for solving temporal planning problems

In this paper, we study the partitioning of constraints in temporal planning problems formulated as mixed-integer nonlinear programming (MINLP) problems. Constraint partitioning is attractive because it leads to much easier subproblems, where each is a significant relaxation of the original problem. Moreover, each subproblem is very similar to the original problem and can be solved by any existing solver with little or no modification. Constraint partitioning, however, introduces global constraints that may be violated when subproblems are evaluated independently. To reduce the overhead in resolving such global constraints, we develop in this paper new conditions and algorithms for limiting the search space to be backtracked in each subproblem. Using a penalty formulation of a MINLP where the constraint functions of the MINLP are transformed into non-negative functions, we present a necessary and sufficient extended saddle-point condition (ESPC) for constrained local minimization. When the penalties are larger than some thresholds, our theory shows a one-to-one correspondence between a constrained local minimum of the MINLP and an extended saddle point of the penalty function. Hence, one way to find a constrained local minimum is to increase gradually the penalties of those violated constraints and to look for a local minimum of the penalty function using any existing algorithm until a solution to the constrained model is found. Next, we extend the ESPC to constraint-partitioned MINLPs and propose a partition-and-resolve strategy for resolving violated global constraints across subproblems. Using the discrete-space ASPEN and the mixed-space MIPS planners to solve subproblems, we show significant improvements on some planning benchmarks, both in terms of the quality of the plans generated and the execution times to find them.     

度量区间时序逻辑下四旋翼的集成任务与运动规划

本文采用优化方法解决度量区间时序逻辑下进行四旋翼的集成任务与运动规划问题。传统方法通常将任务约束和运动约束分层处理。由于不同规划层所使用的抽象模型并不完全匹配,任务规划层求解出的高层策略往往无法有效地被低层的运动规划层执行,从而只能找到次优的运动轨迹甚至找不到解。本文摒弃分层规划的策略,采用B样条拟合运动轨迹,将问题转化问一个混合整数线性规划问题,直接在同一层处理带有时序逻辑的任务约束以及运动约束。与其他现有方法对比,我们的方法保证了连续时间下的轨迹也可以完全满足所有约束条件,而非只有离散的轨迹点才可以满足。我们用四旋翼模型进行了一系列仿真验证,仿真结果表明了方法的有效性