Event calculus and temporal action logics compared

We compare the event calculus and temporal action logics (TAL), two formalisms for reasoning about action and change. We prove that, if the formalisms are restricted to integer time, inertial fluents, and relational fluents, and if TAL action type specifications are restricted to definite reassignment of a single fluent, then the formalisms are not equivalent. We argue that equivalence cannot be restored by using more general TAL action type specifications. We prove however that, if the formalisms are further restricted to single-step actions, then they are logically equivalent.     

Customising Web Information Systems According to User Preferences

Web Information Systems have to serve a variety of users with very diverse preferences regarding content, functionality and presentation. We first investigate the customisation of functionality at a high-level of abstraction, where possible action sequences are represented by an algebraic expression called plot, and user preferences give rise to equations. We show that the problem can be solved by applying conditional term rewriting on the basis of Kleene algebras with tests. By exploiting the idea of weakest preconditions such expressions can be represented by formal power series with coefficients in a Boolean algebra. This gives rise to a sufficient condition for termination based on well-founded orders on such power series. As confluence cannot be guaranteed, we propose critical pair completion to be used in order to enforce the desirable Church-Rosser property. In a second step we parametrise the actions and replace the Boolean conditions by first-order formulae. We show that still term rewriting can be applied, but termination and Church Rosser property become problems that will require manual interaction, in particular, as preference rules will make use of the parameters. On the other hand the presence of first-order conditions can be used to extend the customisation to the content.     

An approach to efficient planning with numerical fluents and multi-criteria plan quality

Dealing with numerical information is practically important in many real-world planning domains where the executability of an action can depend on certain numerical conditions, and the action effects can consume or renew some critical continuous resources, which in pddl can be represented by numerical fluents. When a planning problem involves numerical fluents, the quality of the solutions can be expressed by an objective function that can take different plan quality criteria into account.We propose an incremental approach to automated planning with numerical fluents and multi-criteria objective functions for pddl numerical planning problems. The techniques in this paper significantly extend the framework of planning with action graphs and local search implemented in the lpg planner. We define the numerical action graph (NA-graph) representation for numerical plans and we propose some new local search techniques using this representation, including a heuristic search neighborhood for NA-graphs, a heuristic evaluation function based on relaxed numerical plans, and an incremental method for plan quality optimization based on particular search restarts. Moreover, we analyze our approach through an extensive experimental study aimed at evaluating the importance of some specific techniques for the performance of the approach, and at analyzing its effectiveness in terms of fast computation of a valid plan and quality of the best plan that can be generated within a given CPU-time limit. Overall, the results show that our planner performs quite well compared to other state-of-the-art planners handling numerical fluents.     

TEMPORAL REASONING WITH THE MODAL LOGIC Z

This article presents a formal theory of concurrent actions that handles the qualification, ramification, and frame problems. The theory is capable of temporal explanation, i.e., reasoning forward and backward. The approach uses the modal logic Z to extend the work of Lifschitz and Rabinov on miracle-based temporal reasoning. The advantages of miracles for describing unknown actions are augmented with the ability to handle concurrent actions that can provide for the most economical explanation of state changes. For temporal explanation problems restricted to finite domains, it has a worst-case exponential decision procedure. The theory is as general as first-order logic in what it can express as preconditions and consequences of actions.     

Improving concurrency in temporal plans

There is an increasing interest in solving temporal planning problems. Identification and propagation of mutual exclusion relations between actions can significantly enhance the efficiency of a planner. Current definitions of mutually exclusive actions severely restrict their concurrency. In this paper, we report on thirteen groups of permanently mutually exclusive PDDL 2.1, Level 3 actions. We report on sixteen types of potentially-conflicting interactions between two actions where concurrency may be maximized by adjusting starting time of one of the two actions. We discuss several examples where actions can overlap despite conflicting preconditions and/or effects. The processes executing these actions are mostly independent. We report on a new domain-rewriting technique called “baiting” in order to improve the concurrency in temporal plans. Baiting actions lure a temporal planner into improving concurrency. The technique involves splitting user-identified operators. We report on three types of baiting (standard, double and nested) and show their suitability for various types of action interactions. Baiting requires minimal modification to the planning code. Baiting does not increase the branching in search trees. Baiting does not affect the soundness and completeness of a temporal planner. Our empirical evaluation shows that the makespans of plans generated by efficient planner Sapa with baited domain are significantly lower than makespans of plans generated without baiting.     

Specifying causality in action theories: a default logic approach

Recent research on reasoning about action has shown that the traditional logic form of domain constraints is problematic to represent ramifications of actions that are related to causality of domains. To handle this problem properly, as proposed by some researchers, it is necessary to describe causal relations of domains explicitly in action theories. In this paper, we address this problem from a new point of view. Specifically, unlike other researchers viewing causal relations as some kind of inference rules, we distinguish causal relations between defeasible and non-defeasible cases. It turns out that a causal theory in our formalism can be specified by using Reiter's default logic. Based on this idea, we propose a causality-based minimal change approach for representing effects of actions, and argue that our approach provides more plausible solutions for the ramification and qualification problems compared with other related work. We also describe a logic programming approximation to compute causal theories of actions which provides an implementational basis for our approach.     

基于逻辑方法的开放式规划问题研究

在开放世界中求解智能规划问题往往是比较困难的,这是由于在开放世界中,某些对象可能是未知的,因而在搜索规划解时需要考虑不同的可能性.针对开放世界中的规划问题,通常需要使用传感器观察未知的对象,但是传感器无法保证获取所需的所有信息.本文利用逻辑推理方法,提出了在目标状态信息不完整情况下的智能规划问题求解算法PQG(Planner with query-goal),并通过三个规划领域下的实验验证了该算法的有效性.     

Synthesizing plans that contain actions with context-dependent effects1

This paper presents a method of solving planning problems that involve actions whose effects change according to the situations in which they are performed. The approach is an extension of the conventional planning methodology in which plans are constructed through an iterative process of scanning for goals that are not yet satisfied, inserting actions to achieve them, and introducing subgoals to these actions. This methodology was originally developed under the assumption that one would be dealing exclusively with actions that produce the same effects in every situation. The extension involves introducing additional subgoals to actions above and beyond the preconditions of execution normally introduced. These additional subgoals, called secondary preconditions, ensure that the actions are performed in contexts conducive to producing the effects we desire. This paper defines and analyzes secondary preconditions from a mathematically rigorous standpoint and demonstrates how they can be derived from regression operators.     

A real-time system for motion retrieval and interpretation

This paper proposes a new examplar-based method for real-time human motion recognition using Motion Capture (MoCap) data. We have formalized streamed recognizable actions, coming from an online MoCap engine, into a motion graph that is similar to an animation motion graph. This graph is used as an automaton to recognize known actions as well as to add new ones. We have defined and used a spatio-temporal metric for similarity measurements to achieve more accurate feedbacks on classification. The proposed method has the advantage of being linear and incremental, making the recognition process very fast and the addition of a new action straightforward. Furthermore, actions can be recognized with a score even before they are fully completed. Thanks to the use of a skeleton-centric coordinate system, our recognition method has become view-invariant. We have successfully tested our action recognition method on both synthetic and real data. We have also compared our results with four state-of-the-art methods using three well known datasets for human action recognition. In particular, the comparisons have clearly shown the advantage of our method through better recognition rates.     

Limitations of multi-layer perceptron networks - steps towards genetic neural networks

In this paper we investigate multi-layer perceptron networks in the task domain of Boolean functions. We demystify the multi-layer perceptron network by showing that it just divides the input space into regions constrained by hyperplanes. We use this information to construct minimal training sets. Despite using minimal training sets, the learning time of multi-layer perceptron networks with backpropagation scales exponentially for complex Boolean functions. But modular neural networks which consist of independentky trained subnetworks scale very well. We conjecture that the next generation of neural networks will be genetic neural networks which evolve their structure. We confirm Minsky and Papert: “The future of neural networks is tied not to the search for some single, universal scheme to solve all problems at once, bu to the evolution of a many-faceted technology of network design.”     

A Fuzzy Reasoning Model for Action and Change in Timed Domains

This paper proposes a fuzzy approach for reasoning about action and change in timed domains. In our method, actions and world states are modeled as fuzzy sets over time axis. Thus, their temporal relations and time constraints can be modeled as fuzzy rules. So, our method handles well the issue that action happens at an approximate time and then the states also change at an approximate time, which has not been solved well in the existing work. Finally, our method is used to solve the classic problem of rail‐road crossing control in a fuzzy environment. The theoretical and simulation analysis shows that the controller using our method works well.     

Incremental learning framework for real‐world fraud detection environment

For detecting malicious bidding activities in e‐auctions, this study develops a chunk‐based incremental learning framework that can operate in real‐world auction settings. The self‐adaptive framework first classifies incoming bidder chunks to counter fraud in each auction and take necessary actions. The fraud classifier is then adjusted with confident bidders' labels validated via bidder verification and one‐class classification. Based on real fraud data produced from commercial auctions, we conduct an extensive experimental study wherein the classifier is adapted incrementally using only relevant bidding data while evaluating the subsequent adjusted models' detection and misclassification rates. We also compare our classifier with static learning and learning without data relevancy.     

在部分观测环境下的不确定动作模型学习

近年来,动作模型学习引起了研究人员的极大兴趣.可是,尽管不确定规划已经研究了十几年,动作模型学习的研究仍然集中于经典的确定性动作模型上.提出了在部分观测环境下学习不确定动作模型的算法,该算法可应用于假定人们对转移系统一无所知的情形下进行,输入只有动作-观测序列.在现实世界中,这样的场景很常见.致力于动作是由简单逻辑结构组成的、且观测以一定频率出现的一类问题的研究.学习过程分为3个步骤：首先,计算命题在状态中成立的概率;然后,将命题抽取成效果模式,再抽取前提;最后,对效果模式进行聚类以去除冗余.在基准领域上进行的实验结果表明,动作模型学习技术可推广到不确定的部分观测环境中.     

The ramification problem in temporal databases: Concurrent execution

In this paper, we study the ramification problem in the setting of temporal databases. Standard solutions from the literature on reasoning about action are inadequate because they rely on the assumption that fluents persist, and because actions have effects on the next situation only. In this paper, we provide a solution to the ramification problem based on an extension of the situation calculus and the work of McCain and Turner. More specifically, we study the case in which two or more actions execute concurrently, a particularly complex problem. © 2010 Wiley Periodicals, Inc.     

View-Invariant Representation and Recognition of Actions

Analysis of human perception of motion shows that information for representing the motion is obtained from the dramatic changes in the speed and direction of the trajectory. In this paper, we present a computational representation of human action to capture these dramatic changes using spatio-temporal curvature of 2-D trajectory. This representation is compact, view-invariant, and is capable of explaining an action in terms of meaningful action units called dynamic instants and intervals. A dynamic instant is an instantaneous entity that occurs for only one frame, and represents an important change in the motion characteristics. An interval represents the time period between two dynamic instants during which the motion characteristics do not change. Starting without a model, we use this representation for recognition and incremental learning of human actions. The proposed method can discover instances of the same action performed by differentpeople from different view points. Experiments on 47 actions performed by 7 individuals in an environment with no constraints shows the robustness of the proposed method.     

Compiling Ramification Constraints into Effect Axioms

We present a method to derive a solution to the combined frame and ramification problems for certain classes of theories of action written in the situation calculus. The theories of action considered include the causal laws of the domain, in the form of a set of effect axioms, as well as a set of ramification state constraints. The causal laws state the direct effects that actions have on the world, and ramification state constraints allow one to derive indirect effects of actions on the domain.
To solve the combined frame and ramification problems, the causal laws and ramification state constraints are replaced by a set of successor state axioms . Given a state of the world, these axioms uniquely determine the truth value of dynamic properties after an action is performed. In this article, we extend previous work by formulating an approach for the mechanical generation of these successor state axioms. We make use of the notions of implicate and support that have been developed in the context of propositional theories. The approach works for classes of syntactically restricted sets of ramification state constraints.