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.     

CTP: A New Constraint-Based Formalism for Conditional, Temporal Planning

Temporal constraints pose a challenge for conditional planning, because it is necessary for a conditional planner to determine whether a candidate plan will satisfy the specified temporal constraints. This can be difficult, because temporal assignments that satisfy the constraints associated with one conditional branch may fail to satisfy the constraints along a different branch. In this paper we address this challenge by developing the Conditional Temporal Problem (CTP) formalism, an extension of standard temporal constraint-satisfaction processing models used in non-conditional temporal planning. Specifically, we augment temporal CSP frameworks by (1) adding observation nodes, and (2) attaching labels to all nodes to indicate the situation(s) in which each will be executed. Our extended framework allows for the construction of conditional plans that are guaranteed to satisfy complex temporal constraints. Importantly, this can be achieved even while allowing for decisions about the precise timing of actions to be postponed until execution time, thereby adding flexibility and making it possible to dynamically adapt the plan in response to the observations made during execution. We also show that, even for plans without explicit quantitative temporal constraints, our approach fixes a problem in the earlier approaches to conditional planning, which resulted in their being incomplete.     

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.     

Intentional learning agent architecture

Dealing with changing situations is a major issue in building agent systems. When the time is limited, knowledge is unreliable, and resources are scarce, the issue becomes more challenging. The BDI (Belief-Desire-Intention) agent architecture provides a model for building agents that addresses that issue. The model can be used to build intentional agents that are able to reason based on explicit mental attitudes, while behaving reactively in changing circumstances. However, despite the reactive and deliberative features, a classical BDI agent is not capable of learning. Plans as recipes that guide the activities of the agent are assumed to be static. In this paper, an architecture for an intentional learning agent is presented. The architecture is an extension of the BDI architecture in which the learning process is explicitly described as plans. Learning plans are meta-level plans which allow the agent to introspectively monitor its mental states and update other plans at run time. In order to acquire the intricate structure of a plan, a process pattern called manipulative abduction is encoded as a learning plan. This work advances the state of the art by combining the strengths of learning and BDI agent frameworks in a rich language for describing deliberation processes and reactive execution. It enables domain experts to specify learning processes and strategies explicitly, while allowing the agent to benefit from procedural domain knowledge expressed in plans.     

Multi-agent collaboration in time-constrained domains

Timeliness is usually an indispensable attribute of planning and problem solving for resource allocation in command, control and communication systems. The success of such a system is judged on its ability to respond to scheduled and unscheduled tasks within a permissible time period. The response is based on a plan that covers the following activities: resource allocation, plan execution and monitoring and dynamic plan mending, if necessary. Decision making for resource selection can become very time consuming when there are many resources and the number of constraints is large. In a changing environment of multiple agents, restrictive organizational structures and strict communication protocols may cause intolerable further delays.Traditional approaches to planning in deterministic environments require a predictable amount of time to produce and execute plans. However, given more time, such systems usually cannot improve on the plans. In this paper we describe a multi-agent resource scheduler which uses a prioritized rule base to model decision making under the constraints of time. We also discuss dynamic scoping as a negotiation technique for inter-agent cooperation and constrained lattice-like communications as an optimized message routing strategy. Finally, we present some empirical results from a sequence of experiments.     

Coordination by design and the price of autonomy

We consider a multi-agent planning problem as a set of activities that has to be planned by several autonomous agents. In general, due to the possible dependencies between the agents’ activities or interactions during execution of those activities, allowing agents to plan individually may lead to a very inefficient or even infeasible solution to the multi-agent planning problem. This is exactly where plan coordination methods come into play. In this paper, we aim at the development of coordination by design techniques that (i) let each agent construct its plan completely independent of the others while (ii) guaranteeing that the joint combination of their plans always is coordinated. The contribution of this paper is twofold. Firstly, instead of focusing only on the feasibility of the resulting plans, we will investigate the additional costs incurred by the coordination by design method, that means, we propose to take into account the price of autonomy: the ratio of the costs of a solution obtained by coordinating selfish agents versus the costs of an optimal solution. Secondly, we will point out that in general there exist at least two ways to achieve coordination by design: one called concurrent decomposition and the other sequential decomposition. We will briefly discuss the applicability of these two methods, and then illustrate them with two specific coordination problems: coordinating tasks and coordinating resource usage. We also investigate some aspects of the price of autonomy of these two coordination methods.     

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.     

A heuristic technique for multi‐agent planning

The subject of multi‐agent planning has been of continuing concern in Distributed Artificial Intelligence (DAI). In this paper, we suggest an approach to multi‐agent planning that contains heuristic elements. Our method makes use of subgoals, and derived sub‐plans, to construct a global plan. Agents solve their individual sub‐plans, which are then merged into a global plan. The suggested approach reduces overall planning time and derives a plan that approximates the optimal global plan that would have been derived by a central planner, given those original subgoals. We explore three different scenarios. The first involves a group of agents with a common goal. The second considers how agents can interleave planning and execution when planning towards a common, though dynamic, goal. The third examines the case where agents, each with their own goal, can plan together to reach a state in consensus for the group. Finally, we consider how these approaches can be adapted to handle rational, manipulative agents. This revised version was published online in June 2006 with corrections to the Cover Date.     

Adaptive selection of reactive/deliberate planning for a dynamic environment

This paper proposes and evaluates a new real-time reactive planning approach for a dynamic environment. In addition to having the features of conventional real-time reactive planning, which can react in a dynamic environment, our planning can perform deliberate planning appropriately. The proposed planning uses three kinds of agents: behavior agents that control simple behavior, planning agents that make plans to achieve their own goals, and behavior-selection agents that intermediate between behavior agents and planning agents. They coordinate a plan in an emergent way for the planning system as a whole. We confirmed the effectiveness of our planning by means of a simulation. Furthermore, we implemented an active-vision system and used it to verify the real-world efficiency of our planning.     

Temporal Reasoning for a Collaborative Planning Agent in a Dynamic Environment

We present a temporal reasoning mechanism for an individual agent situated in a dynamic environment such as the web and collaborating with other agents while interleaving planning and acting. Building a collaborative agent that can flexibly achieve its goals in changing environments requires a blending of real-time computing and AI technologies. Therefore, our mechanism consists of an Artificial Intelligence (AI) planning subsystem and a Real-Time (RT) scheduling subsystem. The AI planning subsystem is based on a model for collaborative planning. The AI planning subsystem generates a partial order plan dynamically. During the planning it sends the RT scheduling subsystem basic actions and time constraints. The RT scheduling subsystem receives the dynamic basic actions set with associated temporal constraints and inserts these actions into the agent's schedule of activities in such a way that the resulting schedule is feasible and satisfies the temporal constraints. Our mechanism allows the agent to construct its individual schedule independently. The mechanism handles various types of temporal constraints arising from individual activities and its collaborators. In contrast to other works on scheduling in planning systems which are either not appropriate for uncertain and dynamic environments or cannot be expanded for use in multi-agent systems, our mechanism enables the individual agent to determine the time of its activities in uncertain situations and to easily integrate its activities with the activities of other agents. We have proved that under certain conditions temporal reasoning mechanism of the AI planning subsystem is sound and complete. We show the results of several experiments on the system. The results demonstrate that interleave planning and acting in our environment is crucial.     

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.     

Extending BDI plan selection to incorporate learning from experience

An important drawback to the popular Belief, Desire, and Intentions (BDI) paradigm is that such systems include no element of learning from experience. We describe a novel BDI execution framework that models context conditions as decision trees, rather than boolean formulae, allowing agents to learn the probability of success for plans based on experience. By using a probabilistic plan selection function, the agents can balance exploration and exploitation of their plans. We extend earlier work to include both parameterised goals and recursion and modify our previous approach to decision tree confidence to include large and even non-finite domains that arise from such consideration. Our evaluation on a pre-existing program that relies heavily on recursion and parametrised goals confirms previous results that naive learning fails in some circumstances, and demonstrates that the improved approach learns relatively well.     

Hierarchical task network and operator-based planning: two complementary approaches to real-world planning

Work on generative planning systems has focused on two diverse approaches to plan construction. Hierarchical task network (HTN) planners build plans by successively refining high-level goals into lower-level activities. Operator-based planners employ means-end analysis to directly formulate plans consisting of low-level activities. While many have argued the universal dominance of a single approach, this paper presents an alternative view: that in different situations either may be most appropriate. To support this view, a number of advantages and disadvantages of these approaches are described in light of experiences in developing two real-world, fielded planning systems.     

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.     

Dynamic execution planning for reliable collaborative business processes

Collaborative business processes, implemented and carried out via web services and enabling dynamic interaction among organizations, are becoming more indispensable to competitiveness in the global market. As dynamic collaboration prevails, the quality of service (QoS) of collaborative processes becomes more important. A critical requirement in cases where processes involve long-term activities is to guarantee successful completion within time constraints. In this study, we developed a methodology for dynamic planning of web service execution that imparts reliability to collaborative business processes. In order to ensure that processes successfully execute within time constraints and at minimum cost, the proposed method dynamically modifies execution plans at run-time by means of fault-tolerance techniques. Since generation of an execution plan of minimum cost while guaranteeing successful completion is classified as an NP-hard problem, a heuristic algorithm was developed. Additionally, to compare the proposed algorithm’s performance with those of the branch-and-bound method and the genetic algorithm (GA), a set of experiments was conducted.     

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.     

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.     

Online decentralized information gathering with spatial–temporal constraints

We are interested in coordinating a team of autonomous mobile sensor agents in performing a cooperative information gathering task while satisfying mission-critical spatial–temporal constraints. In particular, we present a novel set of constraint formulations that address inter-agent collisions, collisions with static obstacles, network connectivity maintenance, and temporal-coverage in a resource-efficient manner. These constraints are considered in the context of the target search problem, where the team plans trajectories that maximize the probability of target detection. We model constraints continuously along the agents’ trajectories and integrate these constraint models into decentralized team planning using a computationally efficient solution method based on the Lagrangian formulation and decentralized optimization. We validate our approach in simulation with five UAVs performing search, and through hardware experiments with four indoor mobile robots. Our results demonstrate team planning with spatial–temporal constraints that preserves the performance of unconstrained information gathering and is feasible to implement with reasonable computational and communication resources.     

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

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