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.     

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.     

Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems

There are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size.In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. The parameter k controls the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.     

Integrated Temporal Reasoning with Periodic Events

In many areas of Computer Science, including planning, workflows, guidelines, and protocol management, one has to deal with abstract plans, procedures, or schedules involving temporal constraints between classes of actions that have to be repeated at periodic times and may be instantiated in different ways for different executions of the plans (procedures, schedules). In this paper we propose an integrated framework to deal with both qualitative temporal constraints on classes of actions and temporal constraints between instances of actions, in which temporal reasoning is used to amalgamate both types of constraints and to check their consistency. In particular, we consider an expressive formalism to deal with temporal constraints between classes of actions (with special attention to periodic actions) which takes into account different components such as frame times, numeric quantification, periods, and qualitative relations. We define the notions of (contextual) concretization of qualitative temporal constraints between classes and use this notion to formally define the consistency of a knowledge base of temporal constraints between classes and a set of temporal constraints on instances, and to define the algorithm for checking such a consistency. An application for scheduling lessons in a school is shown in an example.     

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.     

Temporal Constraint Satisfaction Techniques in Job Shop Scheduling Problem Solving

We describe a restriction of Dechter, Meiri and Pearl's TCSPs (Temporal Constraint Satisfaction Problems) sufficiently expressive to represent any job shop scheduling problem. A solver based on the restriction is then described, which is similar to Ladkin and Reinefeld's qualitative interval network solver; except, however, that the filtering method used during the search is not path consistency but either ULT (Upper-Lower Tightening) or LPC (Loose Path- Consistency), which are both less effective but have the advantage of getting rid of the so-called fragmentation problem.     

方位关系约束满足问题的推理求解

约束满足问题（Constraint Satisfaction Problems CSP）是人工智能的一个研究领域,诸如空间查找、规划等问题都可转化为约束满足问题。方位关系是空间关系的重要组成部分,用以确定空间对象间的一种顺序。本文研究了空间方位关系模型,给出了方位关系约束的一般表示形式。在此基础上,利用组合表推理给出了方位关系约束满足问题的一个推理求解算法,该算法的时间复杂度为O（n^2）。     

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.     

Reasoning about Solids Using Constraint Logic Programming

The embedding of constraint satisfaction on the domain of discourse into a rule-based programming paradigm like logic programming provides a powerful reasoning tool. We present an application in spatial reasoning that uses this combination to produce a clear, concise, yet very expressive system through its ability to manipulate partial information. Three-dimensional solid objects in constructive solid geometry representation are manipulated, and their spatial relationship with one another, points, or regions is reasoned about. The language used to develop this application is QUAD-CLP(), an experimental constraint logic programming language of our own design, which is equipped with a solver for quadratic and linear arithmetic constraints over the reals.     

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.     

Investigating Reasoning with Constraint Diagrams

Constraint diagrams are a visual notation designed to express logical constraints. Augmenting the diagrams with a reading tree (effectively a partial ordering of quantifiers) ensures that each diagram has a unique semantic interpretation.In this paper, we discuss examples of reasoning rules for augmented constraint diagrams which exhibit interesting properties or difficulties that can arise when developing rules for such a diagrammatic system. We do not present a complete set of rules, but investigate the generic problems arising, providing solutions. One problem corresponds to the nesting of quantifiers and another relates to the domain of universal quantification. These issues may be an important consideration in the definition of other logical reasoning systems which explicitly represent quantification diagrammatically.     

基于动态约束满足框架的强表达时态规划算法

智能规划已经成为人工智能领域最热门的研究主题之一。近年来,智能规划在现实领域的应用越来越广泛,这对规划器的处理能力和效率提出了很大的挑战。以一类强表达时态规划——基于约束区间规划为研究对象,基于动态约束满足框架设计和实现了一个基于约束区间的规划算法LP-TPOP;对算法的可靠性和完备性进行了证明;最后以一个规划实例演示了算法的运行过程。     

Random Constraint Satisfaction: Flaws and Structure

A recent theoretical result by Achlioptas et al. shows that many models of random binary constraint satisfaction problems become trivially insoluble as problem size increases. This insolubility is partly due to the presence of flawed variables, variables whose values are all flawed (or unsupported). In this paper, we analyse how seriously existing work has been affected. We survey the literature to identify experimental studies that use models and parameters that may have been affected by flaws. We then estimate theoretically and measure experimentally the size at which flawed variables can be expected to occur. To eliminate flawed values and variables in the models currently used, we introduce a flawless generator which puts a limited amount of structure into the conflict matrix. We prove that such flawless problems are not trivially insoluble for constraint tightnesses up to 1/2. We also prove that the standard models B and C do not suffer from flaws when the constraint tightness is less than the reciprocal of domain size. We consider introducing types of structure into the constraint graph which are rare in random graphs and present experimental results with such structured graphs.     

Reasoning about networks of temporal relations and its applications to problem solving

An interval algebra (IA) has been proposed as a model for representing and reasoning about qualitative temporal relations between time intervals. Unfortunately, reasoning tasks with IA that involve deciding the satisfiability of the temporal constraints, or providing all the satisfying instances of the temporal constraints, areNP-complete. That is, solving these problems are computationally exponential in the worst case. However, several directions in improving their computational performance are still possible. This paper presents a new backtracking algorithm for finding a solution called consistent scenario. This algorithm has anO(n ³) best-case complexity, compared toO(n ⁴) of previous known backtrack algorithms, wheren denotes the number of intervals. By computational experiments, we tested the performance of different backtrack algorithms on a set of randomly generated networks with the results favoring our proposal. In this paper, we also present a new path consistency algorithm, which has been used for finding approximate solutions towards the minimal labeling networks. The worst-case complexity of the proposed algorithm is stillO(n ³); however, we are able to improve its performance by eliminating the unnecessary duplicate computation as presented in Allen's original algorithm, and by employing a most-constrained first principle, which ensures a faster convergence. The performance of the proposed scheme is evaluated through a large set of experimental data.     

Algorithms for Distributed Constraint Satisfaction: A Review

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems.     

Solution Techniques for Constraint Satisfaction Problems: Advanced Approaches

Conventional techniques for the constraint satisfaction problem (CSP)have had considerable success in their applications. However,there are many areas in which the performance of the basic approachesmay be improved. These include heuristic ordering of certain tasksperformed by the CSP solver, hybrids which combine compatible solutiontechniques and graph based methods which exploit the structure of theconstraint graph representation of a CSP. Also, conventionalconstraint satisfaction techniques only address problems with hardconstraints (i.e. each of which are completely satisfied or completelyviolated, and all of which must be satisfied by a validsolution). Many real applications require a more flexible approachwhich relaxes somewhat these rigid requirements. To address theseissues various approaches have been developed. This paper attempts asystematic review of them.     

A Glimpse of Constraint Satisfaction

Constraint satisfaction has become an important field in computer science. This technology is embedded in millions of pounds of software used by major companies. Many researchers or software engineers in the industry could have benefited from using constraint technology without realizing it. The aim of this paper is to promote constraint technology by providing readers with a fairly quick introduction to this field. The approach here is to use the well known 8-queens problem to illustrate the basic techniques in constraint satisfaction (without going into great details), and leave interested readers with pointers to further study this field.     

约束编程与约束满足在产品装配中的应用

约束编程与约束满足问题是近三十年来在人工智能领域发展起来的一个研究方向。产品配置器近十几年来发展起来的一项技术。文中介绍约束编程及约束满足问题在按订单装配型产品配置器中的应用，并通过讨论说明了相对于传统配置方案求解过程，应用约束满足的优越性。     

When Ants Attack: Ant Algorithms for Constraint Satisfaction Problems

We describe an ant algorithm for solving constraint problems (Solnon 2002, IEEE Transactions on Evolutionary Computation 6(4): 347–357). We devise a number of variants and carry out experiments. Our preliminary results suggest that the best way to deposit pheromone and the best heuristics for state transitions may differ from current practice     

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.