Constraint Solving for Proof Planning

Proof planning is an application of AI planning to theorem proving that employs plan operators that encapsulate mathematical proof techniques. Many proofs require the instantiation of variables; that is, mathematical objects with certain properties have to be constructed. This is particularly difficult for automated theorem provers if the instantiations have to satisfy requirements specific for a mathematical theory, for example, for finite sets or for real numbers, because in this case unification is insufficient for finding a proper instantiation. Often, constraint solving can be employed for this task. We describe a framework for the integration of constraint solving into proof planning that combines proof planners and stand-alone constraint solvers. Proof planning has some peculiar requirements that are not met by any off-the-shelf constraint-solving system. Therefore, we extended an existing propagation-based constraint solver in a generic way. This approach generalizes previous work on tackling the problem. It provides a more principled way and employs existing AI technology.     

Constraint Reasoning about Repeating Events: Satisfaction and Optimization

Effective manipulation of temporal information about periodic events is required for solving complex problems such as long‐range scheduling or querying temporal information. Furthermore, many problems involving repeating events involve the optimization of temporal aspects of these events (e.g., minimizing make‐span in job‐shop scheduling). In this paper, a constraint‐based formulation of reasoning problems with repeating events is presented, and its complexity is analyzed for a range of problems. Optimization constraints are interpreted formally using the Semiring CSPs (SCSP) representation of optimization in constraint reasoning. This allows for familiar algorithms such as branch‐and‐bound to be applied to solving them.     

SoftCost-R: User experiences and lessons learned at the age of one

User experiences and lessons learned with SoftCost-R, a state-of-the-art work-breakdown structure-oriented IBM PC-based estimating package used to forecast costs and schedules for software projects are described. SoftCost-R's underlying model employs parametric and statistical relationships to provide its users with “what-if” analysis capabilities that allow them to look at different cost and schedule options. Effective transfer of the package to operational use requires that its model be calibrated to the user environment. Practical use of the package requires that considerable attention be paid to user support issues. This paper communicates the lessons learned since the introduction of the package so others can benefit from our experience. It begins by introducing the SoftCost-R package and then focusing on the technology transfer issues; it concludes by summarizing the six major lessons learned and by presenting a wish list.     

Representation and Reasoning with Multi-Point Events

Allen's Interval Algebra (IA) and Vilain & Kautz's Point Algebra (PA) consider an interval and a point as basic temporal entities (i.e., events) respectively. However, in many situations we need to deal with recurring events that include multiple points, multiple intervals or combinations of points and intervals. In this paper, we present a framework to model recurring events as multi-point events (MPEs) by extending point algebra. The reasoning tasks are formulated as binary constraint satisfaction problems. We propose a polynomial time algorithm (based on van Beek's algorithm) for finding all feasible relations. For the problem of finding a consistent scenario, we propose a backtracking method with a local search heuristic. We also describe an implementation and a detail empirical evaluation of the proposed algorithms. Our empirical results indicate that the MPE-based approach performs better than the existing approaches.     

The synthesis of cognitive procedures and the problem of induction

The JSM-method of automated hypotheses generation realizing the automated plausible reasoning in Intelligent Systems is described. It is shown that the method represents specially organized interaction of induction, analogy and abduction. The foundations of exact epistemology for JSM- Intelligent Systems are formulated.     

三维几何约束闭环的动态识别与满足

针对三维几何约束闭环的满足问题,提出了“充分推理＋最小数值”的约束求解策略及其具体的实施方法。自由传播法可在动态求解约束的过程中识别出约束闭环;几何归约法将约束闭环子图归约简化为层次分明的归约树,并进一步明确了闭环的组成和结构;矢量闭环法建立了约束闭环的矢量模型,据此模型可以建立最小规模的方程组来求解约束闭环,方程组的变量具有明确的几何意义,便于初值的确定和多解的处理,并能求解欠约束的闭环。     

The Localization and Correction of Errors in Models: A Constraint-Based Approach

Model-based diagnosis, and constraint-based reasoning are well known generic paradigms for which the most difficult task lies in the construction of the models used. We consider the problem of localizing and correcting the errors in a model. We present a method to debug a model. To help the debugging task, we propose to use the model-base diagnosis solver. This method has been used in a real application of the development a model of a railway signalling system.     

Relation Algebras and their Application in Temporal and Spatial Reasoning

Qualitative temporal and spatial reasoning is in many cases based on binary relations such as before, after, starts, contains, contact, part of, and others derived from these by relational operators. The calculus of relation algebras is an equational formalism; it tells us which relations must exist, given several basic operations, such as Boolean operations on relations, relational composition and converse. Each equation in the calculus corresponds to a theorem, and, for a situation where there are only finitely many relations, one can construct a composition table which can serve as a look up table for the relations involved. Since the calculus handles relations, no knowledge about the concrete geometrical objects is necessary. In this sense, relational calculus is pointless. Relation algebras were introduced into temporal reasoning by Allen (1983, Communications of the ACM 26(1), 832–843) and into spatial reasoning by Egenhofer and Sharma (1992, Fifth International Symposium on Spatial Data Handling, Charleston, SC). The calculus of relation algebras is also well suited to handle binary constraints as demonstrated e.g. by Ladkin and Maddux (1994, Journal of the ACM 41(3), 435–469). In the present paper I will give an introduction to relation algebras, and an overview of their role in qualitative temporal and spatial reasoning.     

Experimental Analysis of Numeric and Symbolic Constraint Satisfaction Techniques for Temporal Reasoning

Many temporal applications like planning and scheduling can be viewed as special cases of the numeric and symbolic temporal constraint satisfaction problem. Thus we have developed a temporal model, TemPro, based on the interval Algebra, to express such applications in term of qualitative and quantitative temporal constraints. TemPro extends the interval algebra relations of Allen to handle numeric information. To solve a constraint satisfaction problem, different approaches have been developed. These approaches generally use constraint propagation to simplify the original problem and backtracking to directly search for possible solutions. The constraint propagation can also be used during the backtracking to improve the performance of the search. The objective of this paper is to assess different policies for finding if a TemPro network is consistent. The main question we want to answer here is how much constraint propagation is useful for finding a single solution for a TemPro constraint graph. For this purpose, we have experimented by randomly generating large consistent networks for which either arc and/or path consistency algorithms (AC-3, AC-7 and PC-2) were applied. The main result of this study is an optimal policy combining these algorithms either at the symbolic (Allen relation propagation) or at the numerical level.     

Design and validation of knowledge acquisition tools in a business domain

This paper presents an approach for the design and the validation of a prototype knowledge acquisition tool in the domain of business planning. Results from previous work in the area of problem-solving in business domain indicate that there are wide differences in both the ways problems are represented, and solution strategies are selected. These differences can have a significant effect on the suitability of knowledge acquisition techniques. The knowledge acquisition tool has been designed to accommodate these differences. Problem decomposition and simplification techniques are employed by the tool in order to elicit the appropriate information for managerial decision making. The prototype tool has been validated in the field with 35 managers using ten test scenarios. The results of the validation process are presented, and implications for the design of such tools in business domain are discussed.     

Exact and approximate reasoning about temporal relations1

Allen gives an algebra for representing qualitative temporal information about the relationships between pairs of intervals. In this paper, we address a fundamental reasoning task that arises in applications of the algebra: Given (possibly indefinite) knowledge about the relationships between intervals, find all feasible relationships between two intervals. We call this the minimal labels problem. Finding the minimal labels can be viewed as computing the deductive consequences of our knowledge. Determining exact solutions to this problem has been shown to be (almost assuredly) intractable. Allen gives an approximation algorithm based on constraint propagation. We present new approximation algorithms; determine analytically under what conditions the algorithms are exact; and examine, through some computational experiments, the quality of the approximate solutions produced by the algorithms. We also give a simple test for predicting when the approximation algorithms will and will not produce good quality approximations. Finally, we survey three example applications of the interval algebra chosen from the literature to show where the results of this paper could be useful.     

Reasoning with Numeric and Symbolic Time Information

Representing and reasoning about time is fundamental in many applications of Artificial Intelligence as well as of other disciplines in computer science, such as scheduling, planning, computational linguistics, database design and molecular biology. The development of a domain-independent temporal reasoning system is then practically important. An important issue when designing such systems is the efficient handling of qualitative and metric time information. We have developed a temporal model, TemPro, based on the Allen interval algebra, to express and manage such information in terms of qualitative and quantitative temporal constraints. TemPro translates an application involving temporal information into a Constraint Satisfaction Problem (CSP). Constraint satisfaction techniques are then used to manage the different time information by solving the CSP. In order for the system to deal with real time applications or those applications where it is impossible or impractical to solve these problems completely, we have studied different methods capable of trading search time for solution quality when solving the temporal CSP. These methods are exact and approximation algorithms based respectively on constraint satisfaction techniques and local search. Experimental tests were performed on randomly generated temporal constraint problems as well as on scheduling problems in order to compare and evaluate the performance of the different methods we propose. The results demonstrate the efficiency of the MCRW approximation method to deal with under constrained and middle constrained problems while Tabu Search and SDRW are the methods of choice for over constrained problems.     

GRAMY: A Geometry Theorem Prover Capable of Construction

This study investigates a procedure for proving arithmetic-free Euclidean geometry theorems that involve construction. Construction means drawing additional geometric elements in the problem figure. Some geometry theorems require construction as a part of the proof. The basic idea of our construction procedure is to add only elements required for applying a postulate that has a consequence that unifies with a goal to be proven. In other words, construction is made only if it supports backward application of a postulate. Our major finding is that our proof procedure is semi-complete and useful in practice. In particular, an empirical evaluation showed that our theorem prover, GRAMY, solves all arithmetic-free construction problems from a sample of school textbooks and 86% of the arithmetic-free construction problems solved by preceding studies of automated geometry theorem proving.     

Development of user-satisfaction-based knowledge management performance measurement system with evidential reasoning approach

Confronting fierce global competition, organizations have implemented knowledge management to enhance competitive advantages. With increasing investments in resources for knowledge management implementation in many organizations, measuring knowledge management performance has become an important agenda among researchers and practitioners. However, the current knowledge management performance measurement methods cannot truly report the results of organizations’ knowledge management efforts. To address this problem, there is a need of a better approach for measuring knowledge management performance in organizations. This paper presents the authors’ recent research in using a K-user satisfaction based approach and evidential reasoning methodology to develop a user-satisfaction-based knowledge management performance measurement system for organizations to identify strengths and weaknesses, as well as enhance continuous learning. A case study in applying the developed system and methodology in primary school education has been conducted to demonstrate its effectiveness.     

Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications

It is critical that agents deployed in real-world settings, such as businesses, offices, universities and research laboratories, protect their individual users’ privacy when interacting with other entities. Indeed, privacy is recognized as a key motivating factor in the design of several multiagent algorithms, such as in distributed constraint reasoning (including both algorithms for distributed constraint optimization (DCOP) and distributed constraint satisfaction (DisCSPs)), and researchers have begun to propose metrics for analysis of privacy loss in such multiagent algorithms. Unfortunately, a general quantitative framework to compare these existing metrics for privacy loss or to identify dimensions along which to construct new metrics is currently lacking. This paper presents three key contributions to address this shortcoming. First, the paper presents VPS (Valuations of Possible States), a general quantitative framework to express, analyze and compare existing metrics of privacy loss. Based on a state-space model, VPS is shown to capture various existing measures of privacy created for specific domains of DisCSPs. The utility of VPS is further illustrated through analysis of privacy loss in DCOP algorithms, when such algorithms are used by personal assistant agents to schedule meetings among users. In addition, VPS helps identify dimensions along which to classify and construct new privacy metrics and it also supports their quantitative comparison. Second, the article presents key inference rules that may be used in analysis of privacy loss in DCOP algorithms under different assumptions. Third, detailed experiments based on the VPS-driven analysis lead to the following key results: (i) decentralization by itself does not provide superior protection of privacy in DisCSP/DCOP algorithms when compared with centralization; instead, privacy protection also requires the presence of uncertainty about agents’ knowledge of the constraint graph. (ii) one needs to carefully examine the metrics chosen to measure privacy loss; the qualitative properties of privacy loss and hence the conclusions that can be drawn about an algorithm can vary widely based on the metric chosen. This paper should thus serve as a call to arms for further privacy research, particularly within the DisCSP/DCOP arena.