HIERARCHICAL ARC CONSISTENCY FOR DISJOINT REAL INTERVALS IN CONSTRAINT LOGIC PROGRAMMING

There have been many proposals for adding sound implementations of numeric processing to Prolog. This paper describes an approach to numeric constraint processing which has been implemented in Echidna, a new constraint logic programming (CLP) language. Echidna uses consistency algorithms which can actively process a wider variety of numeric constraints than most other CLP systems, including constraints containing some common nonlinear functions. A unique feature of Echidna is that it implements domains for real-valued variables with hierarchical data structures and exploits this structure using a hierarchical arc consistency algorithm specialized for numeric constraints. This gives Echidna two advantages over other systems. First, the union of disjoint intervals can be represented directly. Other approaches require trying each disjoint interval in turn during backtrack search. Second, the hierarchical structure facilitates varying the precision of constraint processing. Consequently, it is possible to implement more effective constraint processing control algorithms which avoid unnecessary detailed domain analysis. These advantages distinguish Echidna from other CLP systems for numeric constraint processing.     

Integrating Case-Based and Rule-Based Reasoning to Meet Multiple Design Constraints

Although case-based reasoning (CBR) was introduced as an alternative to rule-based reasoning (RBR), there is a growing interest in integrating it with other reasoning paradigms, including RBR. New hybrid approaches are being piloted to achieve new synergies and improve problem-solving capabilities. In our approach to integration, CBR is used to satisfy multiple numeric constraints, and RBR allows the performance of "what if" analysis needed for creative design.
The domain of our investigation is nutritional menu planning. The task of designing nutritious, yet appetizing, menus is one at which human experts consistently outperform computer systems. Tailoring a menu to the needs of an individual requires satisfaction of multiple numeric nutrition constraints plus personal preference goals and aesthetic criteria.
We first constructed and evaluated independent CBR and RBR menu planning systems, then built a hybrid system incorporating the strengths of each system. The hybrid outperforms either single strategy system, designing superior menus, while synergistically providing functionality that neither single strategy system could provide. In this paper, we present our hybrid approach, which has applicability to other design tasks in which both physical constraints and aesthetic criteria must be met.     

Annotated Logic Applications for Imperfect Information

Imperfect information is a very general term that comprises different types of information, such as uncertain, vague, fuzzy, inconsistent, possibilistic, probabilistic, partially or totally incomplete information [2]. In the literature of knowledge representation we find a different formal model for each one of these distinct types. For example, annotated logic is a formal model to represent inconsistent information.Annotated logics are non-classical logics introduced in [20] as a logic programming theory. They were proved to be paraconsistent. Based on [5], we present in this work the annotated logic programming theory and some of its applications in Artificial Intelligence (AI). We present it as a formalism to reason with inconsistent information and investigate its possibility to represent other types of imperfect information, such as possibilistic and non-monotonic reasoning. Our main goal is to verify and confirm the importance of annotated logics as a tool for developing knowledge-based and automated reasoning systems in AI.     

An Application of Advanced Spatio-Temporal Formalisms to Behavioural Ecology

There is great potential for the development of many new applications using data on mobile objects and mobile regions. To promote these kinds of applications advanced data management techniques for the representation and analysis of mobility-related data are needed. Together with application experts (behavioural ecologists), we investigate how two novel data management approaches may help. We focus on a case study concerning the analysis of fauna behaviour, in particular crested porcupines, which represents a typical example of mobile object monitoring. The first technique we experiment with is a recently developed conceptual spatio-temporal data modelling approach, MADS. This is used to model the schema of the database suited to our case study. Relying on this first outcome a subset of the problem is represented in the logical language MuTACLP. This allows us to formalise and solve the queries which enable the behavioural ecologists to derive crested porcupines behaviour from the raw data on animal movements. Finally, we investigate the support from a commercial Geographic Information System (GIS) for the analysis of spatio-temporal data. We present a way to integrate MuTACLP and a GIS, combining the advantages of GIS technology and the expressive power of MuTACLP.

MULTIPLY SECTIONED BAYESIAN NETWORKS AND JUNCTION FORESTS FOR LARGE KNOWLEDGE-BASED SYSTEMS

Bayesian networks provide a natural, concise knowledge representation method for building knowledge-based systems under uncertainty. We consider domains representable by general but sparse networks and characterized by incremental evidence where the probabilistic knowledge can be captured once and used for multiple cases. Current Bayesian net representations do not consider structure in the domain and lump all variables into a homogeneous network. In practice, one often directs attention to only part of the network within a period of time; i.e., there is "localization" of queries and evidence. In such case, propagating evidence through a homogeneous network is inefficient since the entire network has to be updated each time. This paper derives reasonable constraints, which can often be easily satisfied, that enable a natural {localization preserving) partition of a domain and its representation by separate Bayesian subnets. The subnets are transformed into a set of permanent junction trees such that evidential reasoning takes place at only one of them at a time; and marginal probabilities obtained are identical to those that would be obtained from the homogeneous network. We show how to swap in a new junction tree, and absorb previously acquired evidence. Although the overall system can be large, computational requirements are governed by the size of one junction tree.     

CONSTRAINED RESOLUTION AND ABDUCTTVE TEMPORAL REASONING

This article presents our work on the effective implementation of abduction in temporal reasoning. This works builds on some results, both in the logic programming field and in the automated reasoning area. We have defined and implemented an abductive procedure, which is well adapted for temporal reasoning because it is based on a constrained resolution principle. Constrained resolution has two advantages for temporal reasoning: First, it allows us to deal efficiently with temporal ordering and equality predicates, which are otherwise too much trouble with classical resolution; second, it allows a restricted form of abduction where hypotheses are limited to ordering relationships. From the logic programming area, our work uses results and procedures developed by others in the abductive logic programming field. The procedure we define and implement in this work is relatively independent of the temporal formalism: It has been used with some reified temporal logics and with the event calculus. More generally it can be used on any point-based temporal formalism, provided that a correct and complete algorithm is available for checking the consistency of a set of temporal ordering relationships in this language.     

Negation as Failure as Resolution

Providing a clean procedural semantics of the Negation As Failure rule in Logic Programming has been an open problem for some time now. This rule has been treated as a technique in nonmonotonic reasoning, not as a rule in classical logic. This paper contains a demonstration of the negation as failure rule as a resolution procedure in first-order logic. We present a sound and complete resolution scheme for negation as failure rule for the larger class of constraint logic programs. The approach is to consider a canonical partition of the completion of a definite (constraint) program into the IF and the FI programs. We show that a negated goal, provable from the completed definite program is provable from just the FI part. The clauses in this program have a structure dual to that of definite Horn clauses. We describe a sound and complete linear resolution rule for this fragment, and show that a resolution proof of the negated goal from the FI part corresponds to a finite failure tree resulting from classical linear resolution applied to the goal on the If part of the original definite program. Our work shows that negation as failure rule can be computationally efficient in the sense that the SLD-resolution on the If part of a definite program along with the negation as failure rule is more efficient than a direct resolution procedure on the completion of that program.     

Fuzzy e-negotiation agents

 The paper presents a prototype of Fuzzy e-Negotiation Agents (FeNAs) for autonomous multi-issue negotiation in e-commerce. It considers negotiation as a form of distributed decision making in the presence of limited common knowledge and imprecise/soft constraints that can be modeled as a distributed fuzzy constraint satisfaction problem (DFCSP). FeNAs incorporate the principles of utility theory within DFCSPs and use fuzzy constraint-based reasoning in order to find a consensus that maximizes the agent's utility and the level of its fuzzy constraint satisfaction subject to its acceptability by other agents. The paper presents aspects of problem representation and negotiation mechanisms used by FeNAs in the context of DFCSPs. An overview of FeNAs is provided and some capabilities for automated multi-issue negotiation are illustrated with two scenarios of e-commerce trading.     

USING META-PROGRAMMING,CONSTRAINT LOGIC PROGRAMMING AND APPROXIMATE REASONING FOR EXPERT SYSTEMS DESIGN

Abstract

This paper presents an enhancement of the CARESS system—A Constraint Approximative Reasoning System Support—introduced in (Popescu and Roventa, 1994). CARESS is an experimental system with primarily two objectives:

(1)knowledge representation and manipulation techniques and to implement them in PROLOG III, and

(2) to develop a knowledge programming environment for building expert systems. We discuss here the use of meta-programming, constraint logic programming and approximate reasoning for the design of expert systems

It has already been proven that meta-programming and logic programming are powerful techniques for expert system design. Fuzzy logic can be used to model one kind of uncertainty. Constraint logic programming is useful for dealing with the constraints given by operations using fuzzy sets.     

On isomorphic formalisations

Previous research into the formalisation of statute law identified a number of uses of language which posed problems for formalisation. A previous paper argued that these uses establish the requirement that a formalisation be isomorphic, but noted that this has odd consequences. This paper expands on what these consequences are and argues that they undermine the very idea of formalisation. Therefore, the whole argument constitutes a reductio ad absurdum of the idea of formalising statute law. The paper provides reasons why this activity is impossible and places the conclusion in the context of the development of modem logic, in which context it appears uncontroversial.     

A hybrid knowledge-based system applied to epidemic screening

Although many knowledge-based systems (KBSs) focus on single-paradigm approaches to encoding knowledge (such as production rules), experts rarely use a single type of knowledge in solving a problem. More often, an expert will apply a number of reasoning mechanisms. In recent years, rule-based reasoning (RBR), case-based reasoning (CBR) and model-based reasoning (MBR) have emerged as important and complementary reasoning methodologies in artificial intelligence. For complex problem solving, it is useful to integrate RBR, CBR and MBR. In this paper, a hybrid KBS which integrates a deductive RBR system, an inductive CBR system and a quantitative MBR system is proposed for epidemic screening. The system has been tested using real data, and results are encouraging.     

并发约束程序设计语言COPS及其执行模型

约束程序设计尤其是约束逻辑程序设计与并发约束程序设计在AI程序设计领域占据着越来越重要的位置。传统逻辑程序设计的基“计算即为定理证明”的计算风格虽获得了简洁优美的操作语义特性,但也付出了执行效率低的代价,当应用系统规模增大时,其性能严重下降以致崩溃。针对传统逻辑程序设计的这种可伸缩性问题,设计了一个基于并发约束程序设计概念的说明性语言COPS,旨在从语言设计与执行模型两方面降低说明性程序的不确定性,提高搜索与运行效率。在语言设计方面,通过引入确定性语言成分,避免不确定计算用于确定性目标所浪费的系统开销;在执行模型方面,在目标的并发穿叉执行与数据驱动的并发同步机制的基础上,实现“优先执行确定目标”策略与“最少假定”策略,作为约束传播的延伸,最大幅度地剪枝搜索空间,降低搜索复杂性。COPS提供的知识表示、推理与并发机制使其成为构造agent程序的理想语言。论文给出COPS语言的语法规范与执行模型的操作语义描述。     

Intelligent Scheduling with GUESS (Generically Used Expert Scheduling System): Development and Testing Results

Scheduling is a prevalent function that is omnipresent throughout many industries and applications (Pinedo, 1995; Morton & Pentico, 1993; Zweben & Fox, 1994; Brown & Scherer, 1995). A great need exists for developing scheduling toolkits that can be generically applied to a number of different scheduling problems. To meet this need, more research is warranted for developing a state-of-the-art generic constraint problem-solver as related to scheduling. This paper discusses the development and testing of the Generically Used Expert Scheduling System (GUESS).     

Computers and legal reasoning: Developments in Germany

The importance of reasoning in law is pointed out. Law and jurisprudence belong to the reasoning-conscious disciplines. Accordingly, there is a long tradition of logic in law. The specific methods of professional work in law are to be seen in close connection with legal reasoning. The advent of computers at first did not touch upon legal reasoning (or the professional work in law). At first computers could be used only for general auxiliary functions (e.g., numerical calculations in tax law). Gradually, the use of computers for auxiliary functions in law has become more specific and more sophisticated (e.g., legal information retrieval), touching more closely upon professional legal work. Moreover, renewed interest in AI has also fostered interest in AI in law, especially for legal expert systems. AI techniques can be used in support of legal reasoning. Yet until now legal expert systems have remained in the research and development stage and have hardly succeeded in becoming a profitable tool for the profession. Therefore it is hoped that the two lines of computer support, for auxiliary functions in law and for immediate support of legal reasoning, may unite in the future.Herbert Fiedler is professor of Legal Informatics, general theory of law and penal law in the Department of Economics and Law at the University of Bonn.     

Syntax and Semantics for a Fuzzy Temporal Constraint Logic

In this paper we establish the relationship between the syntax and semantics of a fuzzy temporal constraint logic (FTCL) proposed by Cárdenas et al. FTCL enables us to express interrelated events by means of fuzzy temporal constraints. Moreover, it provides a resolution principle for performing inferences which take these constraints into account. FTCL is compatible with the theoretical temporal reasoning model proposed by Marín et al. – the Fuzzy Temporal Constraint Networks (FTCN). The main contributions of this paper are, on the one hand, the proofs of the FTCL-deduction and the FTCL-refutation theorems, and, on the other, the proof of the soundness of the refutation by resolution in this formal system, together with an exhaustive study of its completeness.     

证据推理的进展及存在的问题

综合论述了证据推理的进展和存在的问题,把证据推理与贝叶斯推理、模糊逻辑推理、基于规则的推理、随机集理流体进行了横向比较,讨论了其间的必然的联系和为语气推理的发展的基础,随后总结了证据推理的改进及其在概率范围在模糊集等方面推广的进展,最后提出了证据推理的广泛应用及其研究方向。