A probabilistic plan recognition algorithm based on plan tree grammars

We present the PHATT algorithm for plan recognition. Unlike previous approaches to plan recognition, PHATT is based on a model of plan execution. We show that this clarifies several difficult issues in plan recognition including the execution of multiple interleaved root goals, partially ordered plans, and failing to observe actions. We present the PHATT algorithm's theoretical basis, and an implementation based on tree structures. We also investigate the algorithm's complexity, both analytically and empirically. Finally, we present PHATT's integrated constraint reasoning for parametrized actions and temporal constraints.     

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.     

Answer set programming for collaborative housekeeping robotics: representation, reasoning, and execution

Answer set programming (ASP) is a knowledge representation and reasoning paradigm with high-level expressive logic-based formalism, and efficient solvers; it is applied to solve hard problems in various domains, such as systems biology, wire routing, and space shuttle control. In this paper, we present an application of ASP to housekeeping robotics. We show how the following problems are addressed using computational methods/tools of ASP: (1) embedding commonsense knowledge automatically extracted from the commonsense knowledge base ConceptNet, into high-level representation, and (2) embedding (continuous) geometric reasoning and temporal reasoning about durations of actions, into (discrete) high-level reasoning. We introduce a planning and monitoring algorithm for safe execution of plans, so that robots can recover from plan failures due to collision with movable objects whose presence and location are not known in advance or due to heavy objects that cannot be lifted alone. Some of the recoveries require collaboration of robots. We illustrate the applicability of ASP on several housekeeping robotics problems, and report on the computational efficiency in terms of CPU time and memory.     

CHARACTERIZING KNOWLEDGE DEPTH IN INTELLIGENT SAFETY SYSTEMS

Intelligent process control may be viewed as encompassing four major tasks. An intelligent agent must monitor the target system to obtain the values of relevant stale variables in order to detect problems and to ascertain the status of the components that may be employed in responding to those problems. An intelligent agent must determine plans for managing the current situation. An intelligent agent must select a response (the “best” one) through a process of plan evaluation. Finally, to carry out the chosen response, the agent must perform plan execution. While monitoring and execution are relatively straightforward operations, plan determination and plan evaluation may be accomplished in a number of ways that vary in their relative depth of reasoning. In this paper we sketch an analysis for the reasoning underlying plan determination and evaluation tasks for a class of intelligent control systems that attempt to “provide a safety function.” This analysis has two objectives: to illustrate a domain-independent mode of analysis for examining progressively deeper models, and to make the analysis available to those interested in building systems that provide safety functions.     

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

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

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.     

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.     

An application of artificial intelligence to object-orientedperformance design for real-time systems

The paper describes an application of artificial intelligence technology to the implementation of a rapid prototyping method in object-oriented performance design (OOPD) for real-time systems. OOPD consists of two prototyping phases for real-time systems. Each of these phases consists of three steps: prototype construction, prototype execution, and prototype evaluation. We present artificial intelligence based methods and tools to be applied to the individual steps. In the prototype construction step, a rapid construction mechanism using reusable software components is implemented based on planning. In the prototype execution step, a hybrid inference mechanism is used to execute the constructed prototype described in declarative knowledge representation. MENDEL, which is a Prolog based concurrent object-oriented language, can be used as a prototype construction tool and a prototype execution tool. In the prototype evaluation step, an expert system which is based on qualitative reasoning is implemented to detect and diagnose bottlenecks and generate an improvement plan for them     

A compositional reasoning system for executing nonmonotonic theories of reasoning

In this paper the framework DESIRE for the design of compositional reasoning systems and multi‐agent systems was applied to build a generic nonmonotonic reasoning system. The outcome is a general reasoning system that can be used to model different nonmonotonic reasoning formalisms and that can be executed by a generic execution mechanism. The main advantages of using DESIRE (for example, compared to a direct implementation in a programming language such as PROLOG) are that the design is generic and has a transparent compositional structure, and the explicit declarative specification of both the static and dynamic aspects of the nonmonotonic reasoning processes, including their control. © 2003 Wiley Periodicals, Inc.     

人工智能赋能的数据管理技术研究

大数据时代,数据规模庞大、数据管理应用场景复杂,传统数据库和数据管理技术面临很大的挑战.人工智能技术因其强大的学习、推理、规划能力,为数据库系统提供了新的发展机遇.人工智能赋能的数据库系统通过对数据分布、查询负载、性能表现等特征进行建模和学习,自动地进行查询负载预测、数据库配置参数调优、数据分区、索引维护、查询优化、查询调度等,以不断提高数据库针对特定硬件、数据和负载的性能.同时,一些机器学习模型可以替代数据库系统中的部分组件,有效减少开销,如学习型索引结构等.分析了人工智能赋能的数据管理新技术的研究进展,总结了现有方法的问题和解决思路,并对未来研究方向进行了展望.     

Explaining interdependent action delays in multiagent plans execution

In this paper we address the problem of diagnosing the execution of Multiagent Plans with interdependent action delays. To this end, we map our problem to the Model-Based Diagnosis setting, and solve it by devising a novel modeling and reasoning method to infer preferred diagnoses based on partial observation of the start and end times of plan actions. Interestingly, we show that the kind of problem we address can be seen as an extension to the well known disjunctive temporal problem with preferences, augmented with a (qualitative) Bayesian network that models dependencies among action delays. An extensive set of tests performed with a prototype implementation on two different problem domains proves the feasibility of the proposed methodology.     

Exploiting domain geometry in analogical route planning

Abstract. Automated route planning consists of using real maps to automatically find good map routes. Two shortcomings to standard methods are (1) that domain information may be lacking, and (2) that a ‘good’ route can be hard to define. Most on-line map representations do not include information that may be relevant for the purpose of generating good realistic routes, such as traffic patterns, construction, and one-way streets. The notion of a good route is dependent not only on geometry (shortest path),but also on a variety of other factors, such as the day and time, weather conditions,and perhaps most importantly,user-dependent preferences. These features can be learned by evaluating real-world execution experience. These difficulties motivate our work on applying analogical reasoning to route planning. Analogical reasoning is a method of using past experience to improve problem solving performance in similar new situations.Our approach consists of the accumulation and reuse of previously traversed routes. We exploit the geometric characteristics of the map domain in the storage, retrieval, and reuse phases of the analogical reasoning process. Our route planning method retrieves and reuses multiple past routing cases that collectively form a good basis for generating a new routing plan. To find a good set of past routes, we have designed a similarity metric that takes into account the geometric and continuous-valued characteristics of a city map. The metric evaluates its own performance and uses execution experience to improve its prediction of case similarity, adaptability and executability. The planner uses a replay mechanism to produce a route plan based on analogy with past routes retrieved by the similarity metric. We use illustrative examples and show some empirical results from a detailed on-line map of the city of Pittsburgh, containing over 18,000 intersections and 25,000 street segments.     

规划图框架下用遗传算法求解时态规划问题

许多现实世界中的规划问题通常希望规划目标能在尽可能短的时间内实现,并且规划动作的执行需要考虑时间因素.在规划图框架下,提出了一种能进行时态约束推理的遗传规划算法.主要工作有以下3个方面:1)介绍基于完全动作图的时序约束推理技术;2)提出能进行时序约束推理的基于规划图的遗传规划技术;3)针对基于规划图的遗传规划技术存在局部搜索能力不足的缺点,提出了在原有遗传操作算子的基础上,引入局部修复算子的混合规划技术.实验表明,这种算法能有效地处理一类时态规划问题.     

RGITL: A temporal logic framework for compositional reasoning about interleaved programs

This paper gives a self-contained presentation of the temporal logic Rely-Guarantee Interval Temporal Logic (RGITL). The logic is based on interval temporal logic (ITL) and higher-order logic. It extends ITL with explicit interleaved programs and recursive procedures. Deduction is based on the principles of symbolic execution and induction, known from the verification of sequential programs, which are transferred to a concurrent setting with temporal logic. We include an interleaving operator with compositional semantics. As a consequence, the calculus permits proving decomposition theorems which reduce reasoning about an interleaved program to reasoning about individual threads. A central instance of such theorems are rely-guarantee (RG) rules, which decompose global safety properties. We show how the correctness of such rules can be formally derived in the calculus. Decomposition theorems for other global properties are also derivable, as we show for the important progress property of lock-freedom. RGITL is implemented in the interactive verification environment KIV. It has been used to mechanize various proofs of concurrent algorithms, mainly in the area oflinearizable and lock-free algorithms.     

A basic agent

A basic agent has been constructed which integrates limited natural language understanding and generation, temporal planning and reasoning, plan execution, simulated symbolic perception, episodic memory, and some general world knowledge. The agent is cast as a robot submarine operating in a two-dimensional simulated "Seaworld" about which it has only partial knowledge. It can communicate with people in a vocabulary of about 800 common English words using a medium coverage grammar. The agent maintains an episodic memory of events in its life and has a limited ability to reflect on those events. A person can make statements to the agent, ask it questions, and give it commands. In response to commands, a temporal task planner is invoked to synthesize a plan, which is then executed at an appropriate future time. A large variety of temporal references in natural language are interpreted with respect to agent time. The agent can form and retain compound future plans, and replan in response to new information or new commands. Natural language verbs are represented in a state transition semantics for compatibility with the planner. The agent is able to give terse answers to questions about its past experiences, present activities and perceptions, future intentions, and general knowledge. No other artificial intelligence artifact with this range of capabilities has previously been constructed.     

Managing plans: Integrating deliberation and reactive execution schemes

In this paper, we argue that a shift is needed for plan-based architectures to support versatile, long-lived systems. Our hypothesis is that we need to integrate plan generation, plan analysis and plan adaptation within a wholesome framework that allow a seamless integration of planning and plan execution activities, i.e. that the architectural focus should move away from planning towards so-called plan management. We present, in this paper, a software framework for plan management, which is based on a novel plan representation. This representation has been designed so that the actual context of the execution is available at all times: what the robot is doing and–more importantly–why it is doing it. Our plan manager implementation is available as open source, and has already been used on three different live systems, on which it demonstrated its capabilities.     

A multi-colony ant algorithm for optimizing join queries in distributed database systems

Distributed database systems provide a new data processing and storage technology for decentralized organizations of today. Query optimization, the process to generate an optimal execution plan for the posed query, is more challenging in such systems due to the huge search space of alternative plans incurred by distribution. As finding an optimal execution plan is computationally intractable, using stochastic-based algorithms has drawn the attention of most researchers. In this paper, for the first time, a multi-colony ant algorithm is proposed for optimizing join queries in a distributed environment where relations can be replicated but not fragmented. In the proposed algorithm, four types of ants collaborate to create an execution plan. Hence, there are four ant colonies in each iteration. Each type of ant makes an important decision to find the optimal plan. In order to evaluate the quality of the generated plan, two cost models are used—one based on the total time and the other on the response time. The proposed algorithm is compared with two previous genetic-based algorithms on chain, tree and cyclic queries. The experimental results show that the proposed algorithm saves up to about 80 % of optimization time with no significant difference in the quality of generated plans compared with the best existing genetic-based algorithm.     

ActiveCBR: An Agent System That Integrates Case-Based Reasoning and Active Databases

Case-based reasoning (CBR) is an artificial intelligence (AI) technique for problem solving that uses previous similar examples to solve a current problem. Despite its success, most current CBR systems are passive: they require human users to activate them manually and to provide information about the incoming problem explicitly. In this paper, we present an integrated agent system that integrates CBR systems with an active database system. Active databases, with the support of active rules, can perform event detection, condition monitoring, and event handling (action execution) in an automatic manner. The integrated ActiveCBR system consists of two layers. In the lower layer, the active database is rule-driven; in the higher layer, the result of action execution of active rules is transformed into feature–value pairs required by the CBR subsystem. The layered architecture separates CBR from sophisticated rule-based reasoning, and improves the traditional passive CBR system with the active property. The system has both real-time response and is highly exible in knowledge management as well as autonomously in response to events that a passive CBR system cannot handle. We demonstrate the system efficiency and effectiveness through empirical tests. Received 21 April 2000 / Revised 12 June 2000 / Accepted in revised form 14 July 2000     

Test Case Generation for Mutation-based Testing of Timeliness

Temporal correctness is crucial for real-time systems. Few methods exist to test temporal correctness and most methods used in practice are ad-hoc. A problem with testing real-time applications is the response-time dependency on the execution order of concurrent tasks. Execution order in turn depends on execution environment properties such as scheduling protocols, use of mutual exclusive resources as well as the point in time when stimuli is injected. Model based mutation testing has previously been proposed to determine the execution orders that need to be verified to increase confidence in timeliness. An effective way to automatically generate such test cases for dynamic real-time systems is still needed. This paper presents a method using heuristic-driven simulation to generate test cases.     

A STRENGTHENED ALGORITHM FOR TEMPORAL REASONING ABOUT PLANS

Allen's interval algebra has been shown to be useful for representing plans. We present a strengthened algorithm for temporal reasoning about plans, which improves on straightforward applications of the existing reasoning algorithms for the algebra. This is made possible by viewing plans as both temporal networks and hierarchical structures. The temporal network view allows us to check for inconsistencies as well as propagate the effects of new temporal constraints, whereas the hierarchical view helps us to get the strengthened results by taking into account the dependency relationships between actions.
We further apply our algorithm to the process of plan recognition through the analysis of natural language input. We show that such an application has two useful effects: the temporal relations derived from the natural language input can be used as constraints to reduce the number of candidate plans, and the derived constraints can be made more specific by combining them with the prestored constraints in the plans being recognized.