The ramification problem in temporal databases: an approach with conflicting constraints

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 where there are conflicting effects of an action, a particularly complex problem. Also we present a tool which implements the proposed solution.     

The ramification problem in temporal databases: a solution implemented in SQL

In this paper we elaborate on the handling of the ramification problem in the setting of temporal databases. Starting with the observation that solutions from the literature on reasoning about action are inadequate for addressing the ramification problem, in our prior work (Papadakis and Plexousakis in Int. J. Artif. Intel., 12(3):315, 2003) we have presented a solution based on an extension of the situation calculus and the work of McCain and Turner. Also, we have dealt with the ramification problem in spatial databases (Papadakis and Christodoulou in Expert Syst. Appl. 37:1374, 2010). In this paper, we present a tool that connects the theoretical results to practical considerations, by producing the appropriate SQL commands in order to address the ramification problem. (A preliminary version of this work appears in Papadakis et al., 17th Inter Symposium on Methodologies for Intelligent Systems, pp. 381–388, 2008)     

Inductive situation calculus

Temporal reasoning has always been a major test case for knowledge representation formalisms. In this paper, we develop an inductive variant of the situation calculus in ID-logic, classical logic extended with inductive definitions. This logic has been proposed recently and is an extension of classical logic. It allows for a uniform representation of various forms of definitions, including monotone inductive definitions and non-monotone forms of inductive definitions such as iterated induction and induction over well-founded posets. We show that the role of such complex forms of definitions is not limited to mathematics but extends to commonsense knowledge representation. In the ID-logic axiomatization of the situation calculus, fluents and causality predicates are defined by simultaneous induction on the well-founded poset of situations. The inductive approach allows us to solve the ramification problem for the situation calculus in a uniform and modular way. Our solution is among the most general solutions for the ramification problem in the situation calculus. Using previously developed modularity techniques, we show that the basic variant of the inductive situation calculus without ramification rules is equivalent to Reiter-style situation calculus.     

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.
     

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.     

Integrating Discrete and Continuous Change in a Logical Framework

The goal of our work is to develop theoretical foundations for the representation of knowledge in domains in which properties may vary continuously. One achievement of our research is that it extends the applicability of current research on theories of action. Furthermore, we are able to apply known approaches to the frame and ramification problems, developed for discretely changing worlds, to domains in which the world changes continuously.
Our approach is based on the discrete situation calculus and on a monotonic solution to the frame problem. In order to address the combined frame and ramification problems, we extend Lin and Reiter's work. We use Pinto and Reiter's extension to the situation calculus to represent occurrences . We extend this work further to allow for reasoning by default. For example, if we know that a ball is falling and we do not have any reason to believe that an action would interfere with the ball's motion, then we assume that the ball will hit the ground. Finally, we extend the language of the situation calculus to allow for properties that change within situations. We also show that our proposed situation calculus inherits the solutions to the frame and ramification problems.     

Applying the persistent set approach in temporal reasoning

Since Hanks and McDermott raised the problem of temporal projection (e.g. the Yale shooting problem) and showed that classical nonmonotonic logics failed to solve it, many solutions have been proposed. However, as indicated by some researchers, most of them are not completely satisfactory. In Zhang and Foo [22], we presented a theory of actions called thepersistent set approach (PSA). In this paper, we extend our previous work to deal with temporal reasoning. Different from those minimality-based approaches, we propose a persistence-based formalization of actions within the situation calculus framework, and show that this gives natural and intuitive solutions to the problem of temporal projection in many cases. Explanations of some of the differences between persistence and minimality are given. We show that our approach also provides a unified framework for representing actions with disjunctive effects, while most of the current methods are inappropriate for dealing with these actions in the general case.     

Towards a general theory of action and time

A formalism for reasoning about actions is proposed that is based on a temporal logic. It allows a much wider range of actions to be described than with previous approaches such as the situation calculus. This formalism is then used to characterize the different types of events, processes, actions, and properties that can be described in simple English sentences. In addressing this problem, we consider actions that involve non-activity as well as actions that can only be defined in terms of the beliefs and intentions of the actors. Finally, a framework for planning in a dynamic world with external events and multiple agents is suggested.     

Toward a boundary regional control problem for Boolean cellular automata

An important question to be addressed regarding system control on a time interval [0, T] is whether some particular target state in the configuration space is reachable from a given initial state. When the target of interest refers only to a portion of the spatial domain, we speak about regional analysis. Cellular automata approach have been recently promoted for the study of control problems on spatially extended systems for which the classical approaches cannot be used. An interesting problem concerns the situation where the subregion of interest is not interior to the domain but a portion of its boundary . In this paper we address the problem of regional controllability of cellular automata via boundary actions, i.e., we investigate the characteristics of a cellular automaton so that it can be controlled inside a given region only acting on the value of sites at its boundaries.     

逻辑AI中的容变能力的研究

In this paper a survey of elaboration tolerance in logical AI is provided. John McCarthy views elaboration tolerance as the key property of any formalism that can represent information in the common sense informatic situa-tion. The goal of studying elaboration tolerance is finding a formalism for describing problems logically that is as elab-oration tolerant as natural language and the associated background knowledge. In the beginning, we introduce the missionaries and cannibals problem and its elaboration problems provided by John McCarthy as the test examples of studying elaboration tolerance. Then we introduce the study of elaboration tolerance from three aspects. First of all,the study of elaboration tolerance of the existing systems is introduced such as Causal Calculator and ABSFOL. Sec-ond the study of special elaboration is presented such as elaboration of actions. Last but not least a formal definition of elaboration toleration and evaluation tools is nrmvided.     

Tracking in object action space

In this paper we focus on the joint problem of tracking humans and recognizing human action in scenarios such as a kitchen scenario or a scenario where a robot cooperates with a human, e.g., for a manufacturing task. In these scenarios, the human directly interacts with objects physically by using/manipulating them or by, e.g., pointing at them such as in “Give me that…”. To recognize these types of human actions is difficult because (a) they ought to be recognized independent of scene parameters such as viewing direction and (b) the actions are parametric, where the parameters are either object-dependent or as, e.g., in the case of a pointing direction convey important information. One common way to achieve recognition is by using 3D human body tracking followed by action recognition based on the captured tracking data. For the kind of scenarios considered here we would like to argue that 3D body tracking and action recognition should be seen as an intertwined problem that is primed by the objects on which the actions are applied. In this paper, we are looking at human body tracking and action recognition from a object-driven perspective. Instead of the space of human body poses we consider the space of the object affordances, i.e., the space of possible actions that are applied on a given object. This way, 3D body tracking reduces to action tracking in the object (and context) primed parameter space of the object affordances. This reduces the high-dimensional joint-space to a low-dimensional action space. In our approach, we use parametric hidden Markov models to represent parametric movements; particle filtering is used to track in the space of action parameters. We demonstrate its effectiveness on synthetic and on real image sequences using human-upper body single arm actions that involve objects.     

Linear logic as a tool for planning under temporal uncertainty

The typical AI problem is that of making a plan of the actions to be performed by a controller so that it could get into a set of final situations, if it started with a certain initial situation.The plans, and related winning strategies, happen to be finite in the case of a finite number of states and a finite number of instant actions.The situation becomes much more complex when we deal with planning under temporal uncertainty caused by actions with delayed effects.Here we introduce a tree-based formalism to express plans, or winning strategies, in finite state systems in which actions may have quantitatively delayed effects. Since the delays are non-deterministic and continuous, we need an infinite branching to display all possible delays. Nevertheless, under reasonable assumptions, we show that infinite winning strategies which may arise in this context can be captured by finite plans.The above planning problem is specified in logical terms within a Horn fragment of affine logic. Among other things, the advantage of linear logic approach is that we can easily capture ‘preemptive/anticipative’ plans (in which a new action β may be taken at some moment within the running time of an action α being carried out, in order to be prepared before completion of action α).In this paper we propose a comprehensive and adequate logical model of strong planning under temporal uncertainty which addresses infinity concerns. In particular, we establish a direct correspondence between linear logic proofs and plans, or winning strategies, for the actions with quantitative delayed effects.     

Iterated belief change in the situation calculus

John McCarthy's situation calculus has left an enduring mark on artificial intelligence research. This simple yet elegant formalism for modelling and reasoning about dynamic systems is still in common use more than forty years since it was first proposed. The ability to reason about action and change has long been considered a necessary component for any intelligent system. The situation calculus and its numerous extensions as well as the many competing proposals that it has inspired deal with this problem to some extent. In this paper, we offer a new approach to belief change associated with performing actions that addresses some of the shortcomings of these approaches. In particular, our approach is based on a well-developed theory of action in the situation calculus extended to deal with belief. Moreover, by augmenting this approach with a notion of plausibility over situations, our account handles nested belief, belief introspection, mistaken belief, and handles belief revision and belief update together with iterated belief change.     

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 constraint satisfaction approach to resolving product configuration conflicts

Product configuration is an essential means for selecting various components to constitute a customized product with the aim of meeting the individualized requirements of a customer. Nevertheless, configuration conflicts may occur when too strict requirements of the customer are given and thus any configuration cannot be found to satisfy the customer requirements. In this situation, it is vital important for a product configurator to recommend the corrective actions for generating valid configurations. In this paper, we present a method of applying constraint satisfaction to resolve product configuration conflicts. In the presented approach, the configuration conflict problem is encoded as a CSP (constraint satisfaction problem). Therefore, the resolution to the configuration conflict problem can be regarded as solving a CSP. As a consequence, corrective actions such as removing selected components or adding new components are suggested by the system. In the case of multiple resolving strategies, a multi-objective decision model is adopted to find the optimal repair strategy according to customer preferences. A computer configuration is illustrated to demonstrate the effectiveness of the presented approach.     

Joint stakeholder decision-making on the management of the Silao–Romita aquifer using AHP

Over-exploitation and pollution have been identified as the main problems facing the Silao–Romita aquifer in Guanajuato, Mexico. The objective of this paper is to analyze the current situation, characterized by a clear lack of legislative enforcement, dispersion of competences, and scarcity of economic resources, in order to establish a new prioritization of action plans, and choose from among three specific management options. One of the main challenges when addressing these problems in a holistic manner is the conflicting viewpoints of the sectors involved. As each stakeholder has a different perception, there is a clear need for appropriate mechanisms to reach a consensus in decision-making. To achieve the objective, we use the Analytic Hierarchy Process (AHP), because of its flexibility and the availability of mathematical axiomatic principles and techniques to obtain group preferences and priorities. In addition, we use several tools developed by the authors to obtain consistency, streamline the trade-off between stakeholder know-how and synthetic consistency, and consistently complete partial judgments given by some of the stakeholders. The problem of obtaining a consensus among the actors involved regarding criteria and alternatives is also considered. The obtained results are intended to serve as guidelines for conducting priority actions to help solve the general problem of the study area, and to identify the management model that best meets the needs of the aquifer, according to the actors involved.     

Practical reasoning as presumptive argumentation using action based alternating transition systems

In this paper we describe an approach to practical reasoning, reasoning about what it is best for a particular agent to do in a given situation, based on presumptive justifications of action through the instantiation of an argument scheme, which is then subject to examination through a series of critical questions. We identify three particular aspects of practical reasoning which distinguish it from theoretical reasoning. We next provide an argument scheme and an associated set of critical questions which is able to capture these features. In order that both the argument scheme and the critical questions can be given precise interpretations we use the semantic structure of an Action-Based Alternating Transition System as the basis for their definition. We then work through a detailed example to show how this approach to practical reasoning can be applied to a problem solving situation, and briefly describe some other previous applications of the general approach. In a second example we relate our account to the social laws paradigm for co-ordinating multi-agent systems. The contribution of the paper is to provide firm foundations for an approach to practical reasoning based on presumptive argument in terms of a well-known model for representing the effects of actions of a group of agents.     

Existential assertions and quantum levels on the tree of the situation calculus

In a seminal paper, Reiter introduced a variant of the situation calculus along with a set of its properties. To the best of our knowledge, one of these properties has remained unproved and ignored despite its relevance to the planning problem and the expressivity of the theories of actions. We state this property in a more general form and provide its proof. Intuitively, whenever a theory of actions entails that there exists a situation satisfying a first order formula (e.g., a goal), at least one such situation must be found within a predetermined distance from the initial situation. This distance is finite and the same in all the models of the theory, since it depends only on the theory and the formula at hand.     

Agent's actions as a classification criteria for the state space in a learning from rewards system

We focus in this paper on the problem of learning an autonomous agent's policy when the state space is very large and the set of actions available is comparatively short. To this end, we use a non-parametric decision rule (concretely, a nearest-neighbour strategy) in order to cluster the state space by means of the action that leads to a successful situation. Using an exploration strategy to avoid greedy behaviour, the agent builds clusters of positively-classified states through trial and error learning. In this paper, we implement a 3D synthetic agent which plays an ‘avoid the asteroid’ game that suits our assumptions. Using as the state space a feature vector space extracted from a visual navigation system, we test two exploration strategies using the trial and error learning method. This experiment shows that the agent is a good classifier over the state space, and will therefore show good behaviour in its synthetic world.     

Specifying and computing preferred plans

In this paper, we address the problem of specifying and computing preferred plans using rich, qualitative, user preferences. We propose a logical language for specifying preferences over the evolution of states and actions associated with a plan. We provide a semantics for our first-order preference language in the situation calculus, and prove that progression of our preference formulae preserves this semantics. This leads to the development of PPlan, a bounded best-first search planner that computes preferred plans. Our preference language is amenable to integration with many existing planners, and beyond planning, can be used to support a diversity of dynamical reasoning tasks that employ preferences.