Consistency in networks of relations

doi:10.1016/0004-3702(77)90007-8

Artificial Intelligence

Volume 8, Issue 1, February 1977, Pages 99-118

https://doi.org/10.1016/0004-3702(77)90007-8 Get rights and content

Abstract

Artificial intelligence tasks which can be formulated as constraint satisfaction problems, with which this paper is for the most part concerned, are usually by solved backtracking the examining the thrashing behavior that nearly always accompanies backtracking, identifying three of its causes and proposing remedies for them we are led to a class of algorithms whoch can profitably be used to eliminate local (node, arc and path) inconsistencies before any attempt is made to construct a complete solution. A more general paradigm for attacking these tasks is the altenation of constraint manipulation and case analysis producing an OR problem graph which may be searched in any of the usual ways.

Many authors, particularly Montanari and Waltz, have contributed to the development of these ideas; a secondary aim of this paper is to trace that history. The primary aim is to provide an accessible, unified framework, within which to present the algorithms including a new path consistency algorithm, to discuss their relationships and the may applications, both realized and potential of network consistency algorithms.

References (25)

C.M. Eastman
Automated space planning
Artificial Intelligence
(1973)
R.E. Fikes
REF-ARF: A system for solving problems stated as procedures
Artificial Intelligence
(1970)
U. Montanari
Networks of constraints: fundamental properties and applications to pictures processing
Inform. Sci.
(1974)
A.V. Aho et al.
The Design and Analysis of Computer Algorithms
(1974)
D.G. Bobrow et al.
New programming languages for AI research
Comput. Surv.
(1974)
R.M. Burstall
A program for solving word sum puzzles
Comput. J.
(1969)
O.J. Dahl et al.
Structured Programming
(1972)
R.W. Floyd
Nondeterministic algorithms
J. Assoc. Comput. Mach.
(1967)
R.W. Floyd
Algorithm 97: shortest path
Comm. ACM
(1962)
M.R. Garey et al.
Some simplified NP-complete problems

J.A. Gaschnig

Constraint satisfaction method for inference making

M. Haims

On the optimum two-dimensional allocation problem

Cited by (1697)

Automatic generation of dominance breaking nogoods for a class of constraint optimization problems
2023, Artificial Intelligence
Constraint Optimization Problems (COPs) ask for an assignment of values to variables in order to optimize an objective subject to constraints that restrict the value combinations in the assignment. They are usually solved by the classical Branch and Bound (B&B) search algorithm. Dominance breaking is an important technique in B&B to prune assignments that are subordinate to others concerning the objective value and/or the satisfiability of constraints. In practice, the addition of constraints for dominance breaking can drastically speed up the B&B search for solving many COPs. However, identification of suboptimal assignments in COPs and derivation of useful constraints for dominance breaking are usually problem-specific and require sophisticated human insights on the problem structure.
This paper proposes the first theoretical and practical framework for automatic generation of dominance breaking constraints for a class of COPs consisting of efficiently checkable objectives and constraints. In particular, the framework focuses on generating nogood constraints representing incompatible value assignments and formulates nogood generation as solving auxiliary constraint satisfaction problems. The proposed method can generate nogoods of varying strengths for dominance breaking by controlling the number of involved variables. Experimentation on various benchmarks demonstrates the effectiveness of the proposal in both efficiency and ease of use. The superior performance is also supported by a theoretical analysis to compare the relative strength of automatically generated nogoods with manually derived dominance breaking constraints in the literature.
Forecasting petroleum products consumption in Cameroon's household sector using a sequential GMC(1,n) model optimized by genetic algorithms
2022, Heliyon
Forecasting energy consumption is a major concern for policymakers, oil industry companies, and many other associated businesses. Though there exist many forecasting methodologies, selecting the most appropriate one is critical. GM(1,1) has proven to be one of the most successful forecasting tool. GM(1,1) does not require any specific information and can be adapted to predict energy consumption using a minimum of four observations. Unfortunately, GM(1,1) on its own will generate too large forecast errors because it performs well only when data follow an exponential trend and should be implemented in a political-socio-economic free environment. To reduce these errors, this study proposes a new GM(1,n) convolution model optimized by genetic algorithms integrating a sequential selection mechanism and arc consistency, abbreviated Sequential-GMC(1,n)-GA. Practically, the proposed approach, on one hand, highlights the forecast for petroleum products consumption in Cameroon's household sector. On the other hand, it estimates the amount of CO2 that would be reduced if petroleum products in this sector were switched to clean energy. The new model, like some recent hybrid versions, is robust and reliable, according to the results. Households petroleum products needs by 2025 are estimated to be 150,318 kilo tons of oil equivalent with MAPE of 1.44%, and RMSE of 0.833. Therefore, households GHG emissions would be reduced by 733.85 kilo tons of CO2 equivalent if clean energy was used instead of petroleum products. As a result, the new hybrid model is a valid forecasting tool that can be used to track the growth of Cameroon's household energy demand.
Multi-agent path finding with mutex propagation
2022, Artificial Intelligence
Citation Excerpt :
We use Algorithm 2 to find all mutexes between two MDDs. The algorithm is similar to AC-3 [34]. The pseudocode is only for illustrating the general idea and not intended to be efficient.
Mutex propagation is a form of efficient constraint propagation popularly used in AI planning to tightly approximate the reachable states from a given state. We utilize this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF, mutex propagation provides stronger constraints for conflict resolution in CBS, a popular optimal search-based MAPF algorithm, as well as in MDD-SAT, an optimal satisfiability-based MAPF algorithm. Mutex propagation provides CBS with the ability to break symmetries in MAPF and provides MDD-SAT with the ability to make stronger inferences than unit propagation. While existing work identifies a limited form of symmetries and requires the manual design of symmetry-breaking constraints, mutex propagation is more general and allows for the automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH-RCT, a state-of-the-art variant of CBS, with respect to the success rate. We also show that MDD-SAT with mutex propagation often performs better than MDD-SAT with respect to the success rate.
Efficient Greedy Algorithms with Accuracy Guarantees for Combinatorial Restrictions
2024, SN Computer Science
FeReX: A Reconfigurable Design of Multi-bit Ferroelectric Compute-in-Memory for Nearest Neighbor Search
2024, arXiv
Query-driven Qualitative Constraint Acquisition
2024, Journal of Artificial Intelligence Research

View all citing articles on Scopus

View full text

Consistency in networks of relations

Abstract

Artificial Intelligence

Artificial Intelligence

Inform. Sci.

The Design and Analysis of Computer Algorithms

New programming languages for AI research

Comput. Surv.

A program for solving word sum puzzles

Comput. J.

Structured Programming

Nondeterministic algorithms

J. Assoc. Comput. Mach.

Algorithm 97: shortest path

Comm. ACM

Some simplified NP-complete problems

Constraint satisfaction method for inference making

On the optimum two-dimensional allocation problem