Ian Miguel

AAMAS Conference 2026 Conference Paper

Modelling Multi-Agent Pathfinding Problems by Integrating Connectivity and No-Collision Constraints

• Jiří Švancara
• Roman Barták
• Ian Miguel
• Joan Espasa

Multi-agent pathfinding (MAPF) is the problem of finding collisionfree paths for a set of agents in a shared environment, typically represented as a graph. One of the approaches to solving MAPF is based on representing the problem as a Boolean satisfiability problem. However, this method can produce extremely large Boolean formulas, both in terms of variables and clauses. The primary reason for the excessive number of clauses is the encoding required to represent the valid paths. In this paper, we propose two encodings of the MAPF problem designed for SAT Modulo Theories solvers. Our approach delegates all the valid path reasoning to a monotonic theory supporting source-target connectivity. This is then combined with a 2-SAT Boolean formula to prevent collisions between agents. Together, these components create an effective separation of concerns: the SAT solver focuses on resolving conflicts, while the theory solver handles the connectivity constraints. Our experiments are conducted in both makespan and sum of costs optimisation settings, empirically demonstrating a notable reduction in both the size of the MAPF encoding and the time required to generate it. In addition, when fixing the SAT solver across experiments, results demonstrate considerable performance improvements when transitioning from pure SAT to our proposed SMT encodings.

AIJ Journal 2025 Journal Article

Athanor: Local search over abstract constraint specifications

• Saad Attieh
• Nguyen Dang
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

Local search is a common method for solving combinatorial optimisation problems. We focus on general-purpose local search solvers that accept as input a constraint model — a declarative description of a problem consisting of a set of decision variables under a set of constraints. Existing approaches typically take as input models written in solver-independent constraint modelling languages like MiniZinc. The Athanor solver we describe herein differs in that it begins from a specification of a problem in the abstract constraint specification language Essence , which allows problems to be described without commitment to low-level modelling decisions through its support for a rich set of abstract types. The advantage of proceeding from Essence is that the structure apparent in a concise, abstract specification of a problem can be exploited to generate high quality neighbourhoods automatically, avoiding the difficult task of identifying that structure in an equivalent constraint model. Based on the twin benefits of neighbourhoods derived from high level types and the scalability derived by searching directly over those types, our empirical results demonstrate strong performance in practice relative to existing solution methods.

JAIR Journal 2025 Journal Article

TabID: Automatic Identification and Tabulation of Subproblems in Constraint Models

• Özgür Akgün
• Ian Gent
• Christopher Jefferson
• Zeynep Kiziltan
• Ian Miguel
• Peter Nightingale
• András Z. Salamon
• Felix Ulrich-Oltean

The performance of a constraint model can often be improved by converting a subproblem into a single table constraint (referred to as tabulation). Finding subproblems to tabulate is traditionally a manual and time-intensive process, even for expert modellers. This paper presents TabID, an entirely automated method to identify promising subproblems for tabulation in constraint programming. We introduce a diverse set of heuristics designed to identify promising candidates for tabulation, aiming to improve solver performance. These heuristics are intended to encapsulate various factors that contribute to useful tabulation. We also present additional checks to limit the potential drawbacks of suboptimal tabulation. We comprehensively evaluate our approach using benchmark problems from existing literature that previously relied on manual identification by constraint programming experts of constraints to tabulate. We demonstrate that our automated identification and tabulation process achieves comparable, and in some cases improved results. We empirically evaluate the efficacy of our approach on a variety of solvers, including standard CP (Minion and Gecode), clause-learning CP (Chuffed and OR-Tools) and SAT solvers (Kissat). Our findings highlight the substantial potential of fully automated tabulation, suggesting its integration into automated model reformulation tools.

AIJ Journal 2023 Journal Article

Automated streamliner portfolios for constraint satisfaction problems

• Patrick Spracklen
• Nguyen Dang
• Özgür Akgün
• Ian Miguel

Constraint Programming (CP) is a powerful technique for solving large-scale combinatorial problems. Solving a problem proceeds in two distinct phases: modelling and solving. Effective modelling has a huge impact on the performance of the solving process. Even with the advance of modern automated modelling tools, search spaces involved can be so vast that problems can still be difficult to solve. To further constrain the model, a more aggressive step that can be taken is the addition of streamliner constraints, which are not guaranteed to be sound but are designed to focus effort on a highly restricted but promising portion of the search space. Previously, producing effective streamlined models was a manual, difficult and time-consuming task. This paper presents a completely automated process to the generation, search and selection of streamliner portfolios to produce a substantial reduction in search effort across a diverse range of problems. The results demonstrate a marked improvement in performance for both Chuffed, a CP solver with clause learning, and lingeling, a modern SAT solver.

IJCAI Conference 2023 Conference Paper

Conjure: Automatic Generation of Constraint Models from Problem Specifications (Extended Abstract)

• Özgür Akgün
• Alan M. Frisch
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

When solving a combinatorial problem, the formulation or model of the problem is critical to the efficiency of the solver. Automating the modelling process has long been of interest given the expertise and time required to develop an effective model of a particular problem. We describe a method to automatically produce constraint models from a problem specification written in the abstract constraint specification language Essence. Our approach is to incrementally refine the specification into a concrete model by applying a chosen refinement rule at each step. Any non-trivial specification may be refined in multiple ways, creating a diverse space of models to choose from. The handling of symmetries is a particularly important aspect of automated modelling. We show how modelling symmetries may be broken automatically as they enter a model during refinement, removing the need for an expensive symmetry detection step following model formulation. Our approach is implemented in a system called Conjure. We compare the models produced by Conjure to constraint models from the literature that are known to be effective. Our empirical results confirm that Conjure can reproduce successfully the kernels of the constraint models of 42 benchmark problems found in the literature.

IJCAI Conference 2023 Conference Paper

Learning When to Use Automatic Tabulation in Constraint Model Reformulation

• Carlo Cena
• Özgür Akgün
• Zeynep Kiziltan
• Ian Miguel
• Peter Nightingale
• Felix Ulrich-Oltean

Combinatorial optimisation has numerous practical applications, such as planning, logistics, or circuit design. Problems such as these can be solved by approaches such as Boolean Satisfiability (SAT) or Constraint Programming (CP). Solver performance is affected significantly by the model chosen to represent a given problem, which has led to the study of model reformulation. One such method is tabulation: rewriting the expression of some of the model constraints in terms of a single “table” constraint. Successfully applying this process means identifying expressions amenable to trans- formation, which has typically been done manually. Recent work introduced an automatic tabulation using a set of hand-designed heuristics to identify constraints to tabulate. However, the performance of these heuristics varies across problem classes and solvers. Recent work has shown learning techniques to be increasingly useful in the context of automatic model reformulation. The goal of this study is to understand whether it is possible to improve the performance of such heuristics, by learning a model to predict whether or not to activate them for a given instance. Experimental results suggest that a random forest classifier is the most robust choice, improving the performance of four different SAT and CP solvers.

AIJ Journal 2022 Journal Article

Conjure: Automatic Generation of Constraint Models from Problem Specifications

• Özgür Akgün
• Alan M. Frisch
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

When solving a combinatorial problem, the formulation or model of the problem is critical to the efficiency of the solver. Automating the modelling process has long been of interest because of the expertise and time required to produce an effective model of a given problem. We describe a method to automatically produce constraint models from a problem specification written in the abstract constraint specification language Essence. Our approach is to incrementally refine the specification into a concrete model by applying a chosen refinement rule at each step. Any non-trivial specification may be refined in multiple ways, creating a space of models to choose from. The handling of symmetries is a particularly important aspect of automated modelling. Many combinatorial optimisation problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: modelling symmetries. We show how modelling symmetries may be broken automatically as they enter a model during refinement, obviating the need for an expensive symmetry detection step following model formulation. Our approach is implemented in a system called Conjure. We compare the models produced by Conjure to constraint models from the literature that are known to be effective. Our empirical results confirm that Conjure can reproduce successfully the kernels of the constraint models of 42 benchmark problems found in the literature.

ECAI Conference 2020 Conference Paper

Exploiting Incomparability in Solution Dominance: Improving General Purpose Constraint-Based Mining

• Gökberk Koçak
• Özgür Akgün
• Tias Guns
• Ian Miguel

In data mining, finding interesting patterns is a challenging task. Constraint-based mining is a well-known approach to this, and one for which constraint programming has been shown to be a well-suited and generic framework. Constraint dominance programming (CDP) has been proposed as an extension that can capture an even wider class of constraint-based mining problems, by allowing us to compare relations between patterns. In this paper we improve CDP with the ability to specify an incomparability condition. This allows us to overcome two major shortcomings of CDP: finding dominated solutions that must then be filtered out after search, and unnecessarily adding dominance blocking constraints between incomparable solutions. We demonstrate the efficacy of our approach by extending the problem specification language ESSENCE and implementing it in a solver-independent manner on top of the constraint modelling tool CONJURE. Our experiments on pattern mining tasks with both a CP solver and a SAT solver show that using the incomparability condition during search significantly improves the efficiency of dominance programming and reduces (and often eliminates entirely) the need for post-processing to filter dominated solutions.

IJCAI Conference 2019 Conference Paper

Athanor: High-Level Local Search Over Abstract Constraint Specifications in Essence

• Saad Attieh
• Nguyen Dang
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

This paper presents Athanor, a novel local search solver that operates on abstract constraint specifications of combinatorial problems in the Essence language. It is unique in that it operates directly on the high level, nested types in Essence, such as set of partitions or multiset of sequences, without refining such types into low level representations. This approach has two main advantages. First, the structure present in the high level types allows high quality neighbourhoods for local search to be automatically derived. Second, it allows Athanor to scale much better than solvers that operate on the equivalent, but much larger, low-level representations. The paper details how Athanor operates, covering incremental evaluation, dynamic unrolling of quantified expressions and neighbourhood construction. A series of case studies show the performance of Athanor, benchmarked against several local search solvers on a range of problem classes.

IJCAI Conference 2018 Conference Paper

A Framework for Constraint Based Local Search using Essence

• Özgür Akgün
• Saad Attieh
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale
• András Z. Salamon
• Patrick Spracklen

Structured Neighbourhood Search (SNS) is a framework for constraint-based local search for problems expressed in the Essence abstract constraint specification language. The local search explores a structured neighbourhood, where each state in the neighbourhood preserves a high level structural feature of the problem. SNS derives highly structured problem-specific neighbourhoods automatically and directly from the features of the Essence specification of the problem. Hence, neighbourhoods can represent important structural features of the problem, such as partitions of sets, even if that structure is obscured in the low-level input format required by a constraint solver. SNS expresses each neighbourhood as a constrained optimisation problem, which is solved with a constraint solver. We have implemented SNS, together with automatic generation of neighbourhoods for high level structures, and report high quality results for several optimisation problems.

AIJ Journal 2017 Journal Article

Automatically improving constraint models in Savile Row

• Peter Nightingale
• Özgür Akgün
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Patrick Spracklen

When solving a combinatorial problem using Constraint Programming (CP) or Satisfiability (SAT), modelling and formulation are vital and difficult tasks. Even an expert human may explore many alternatives in modelling a single problem. We make a number of contributions in the automated modelling and reformulation of constraint models. We study a range of automated reformulation techniques, finding combinations of techniques which perform particularly well together. We introduce and describe in detail a new algorithm, X-CSE, to perform Associative–Commutative Common Subexpression Elimination (AC-CSE) in constraint problems, significantly improving existing CSE techniques for associative and commutative operators such as +. We demonstrate that these reformulation techniques can be integrated in a single automated constraint modelling tool, called Savile Row, whose architecture we describe. We use Savile Row as an experimental testbed to evaluate each reformulation on a set of 50 problem classes, with 596 instances in total. Our recommended reformulations are well worthwhile even including overheads, especially on harder instances where solver time dominates. With a SAT solver we observed a geometric mean of 2. 15 times speedup compared to a straightforward tailored model without recommended reformulations. Using a CP solver, we obtained a geometric mean of 5. 96 times speedup for instances taking over 10 seconds to solve.

ECAI Conference 2014 Conference Paper

Breaking Conditional Symmetry in Automated Constraint Modelling with CONJURE

• Özgür Akgün
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

Many constraint problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: model symmetries. We present a systematic method by which the automated constraint modelling tool CONJURE can break conditional symmetry as it enters a model during refinement. Our method extends, and is compatible with, our previous work on automated symmetry breaking in CONJURE. The result is the automatic and complete removal of model symmetries for the entire problem class represented by the input specification. This applies to arbitrarily nested conditional symmetries and represents a significant step forward for automated constraint modelling.

AIJ Journal 2014 Journal Article

Generating custom propagators for arbitrary constraints

• Ian P. Gent
• Christopher Jefferson
• Steve Linton
• Ian Miguel
• Peter Nightingale

Constraint Programming (CP) is a proven set of techniques for solving complex combinatorial problems from a range of disciplines. The problem is specified as a set of decision variables (with finite domains) and constraints linking the variables. Local reasoning (propagation) on the constraints is central to CP. Many constraints have efficient constraint-specific propagation algorithms. In this work, we generate custom propagators for constraints. These custom propagators can be very efficient, even approaching (and in some cases exceeding) the efficiency of hand-optimised propagators. Given an arbitrary constraint, we show how to generate a custom propagator that establishes GAC in small polynomial time. This is done by precomputing the propagation that would be performed on every relevant subdomain. The number of relevant subdomains, and therefore the size of the generated propagator, is potentially exponential in the number and domain size of the constrained variables. The limiting factor of our approach is the size of the generated propagators. We investigate symmetry as a means of reducing that size. We exploit the symmetries of the constraint to merge symmetric parts of the generated propagator. This extends the reach of our approach to somewhat larger constraints, with a small run-time penalty. Our experimental results show that, compared with optimised implementations of the table constraint, our techniques can lead to an order of magnitude speedup. Propagation is so fast that the generated propagators compare well with hand-written carefully optimised propagators for the same constraints, and the time taken to generate a propagator is more than repaid.

SoCS Conference 2011 Conference Paper

A Preliminary Evaluation of Machine Learning in Algorithm Selection for Search Problems

• Lars Kotthoff
• Ian P. Gent
• Ian Miguel

Machine learning is an established method of selecting algorithms to solve hard search problems. Despite this, to date no systematic comparison and evaluation of the different techniques has been performed and the performance of existing systems has not been critically compared to other approaches. We compare machine learning techniques for algorithm selection on real-world data sets of hard search problems. In addition to well-established approaches, for the first time we also apply statistical relational learning to this problem. We demonstrate that most machine learning techniques and existing systems perform less well than one might expect. To guide practitioners, we close by giving clear recommendations as to which machine learning techniques are likely to perform well based on our experiments.

IJCAI Conference 2011 Conference Paper

Exploiting Short Supports for Generalised Arc Consistency for Arbitrary Constraints

• Peter Nightingale
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel

Special-purpose constraint propagation algorithms (such as those for the element constraint) frequently make implicit use of short supports - by examining a subset of the variables, they can infer support for all other variables and values and save substantial work. However, to date general purpose propagation algorithms (such as GAC-Schema) rely upon supports involving all variables. We demonstrate how to employ short supports in a new general purpose propagation algorithm called ShortGAC. This works when provided with either an explicit list of allowed short tuples, or a function to calculate the next supporting short tuple. Empirical analyses demonstrate the efficiency of ShortGAC compared to other general-purpose propagation algorithms. In some cases ShortGAC even exhibits similar performance to special-purpose propagators.

AAAI Conference 2011 Conference Paper

Extensible Automated Constraint Modelling

• Ozgur Akgun
• Ian Miguel
• Chris Jefferson
• Alan Frisch
• Brahim Hnich

In constraint solving, a critical bottleneck is the formulation of an effective constraint model of a given problem. The CONJURE system described in this paper, a substantial step forward over prototype versions of CONJURE previously reported, makes a valuable contribution to the automation of constraint modelling by automatically producing constraint models from their specifications in the abstract constraint specification language ESSENCE. A set of rules is used to re- fine an abstract specification into a concrete constraint model. We demonstrate that this set of rules is readily extensible to increase the space of possible constraint models CONJURE can produce. Our empirical results confirm that CONJURE can reproduce successfully the kernels of the constraint models of 32 benchmark problems found in the literature.

ECAI Conference 2010 Conference Paper

Learning When to Use Lazy Learning in Constraint Solving

• Ian P. Gent
• Christopher Jefferson
• Lars Kotthoff
• Ian Miguel
• Neil C. A. Moore
• Peter Nightingale
• Karen E. Petrie

Learning in the context of constraint solving is a technique by which previously unknown constraints are uncovered during search and used to speed up subsequent search. Recently, lazy learning, similar to a successful idea from satisfiability modulo theories solvers, has been shown to be an effective means of incorporating constraint learning into a solver. Although a powerful technique to reduce search in some circumstances, lazy learning introduces a substantial overhead, which can outweigh its benefits. Hence, it is desirable to know beforehand whether or not it is expected to be useful. We approach this problem using machine learning (ML). We show that, in the context of a large benchmark set, standard ML approaches can be used to learn a simple, cheap classifier which performs well in identifying instances on which lazy learning should or should not be used. Furthermore, we demonstrate significant performance improvements of a system using our classifier and the lazy learning and standard constraint solvers over a standard solver. Through rigorous cross-validation across the different problem classes in our benchmark set, we show the general applicability of our learned classifier.

AIJ Journal 2009 Journal Article

Filtering algorithms for the multiset ordering constraint

• Alan M. Frisch
• Brahim Hnich
• Zeynep Kiziltan
• Ian Miguel
• Toby Walsh

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial.

AIJ Journal 2008 Journal Article

Generalised arc consistency for the AllDifferent constraint: An empirical survey

• Ian P. Gent
• Ian Miguel
• Peter Nightingale

The AllDifferent constraint is a crucial component of any constraint toolkit, language or solver, since it is very widely used in a variety of constraint models. The literature contains many different versions of this constraint, which trade strength of inference against computational cost. In this paper, we focus on the highest strength of inference, enforcing a property known as generalised arc consistency (GAC). This work is an analytical survey of optimizations of the main algorithm for GAC for the AllDifferent constraint. We evaluate empirically a number of key techniques from the literature. We also report important implementation details of those techniques, which have often not been described in published papers. We pay particular attention to improving incrementality by exploiting the strongly-connected components discovered during the standard propagation process, since this has not been detailed before. Our empirical work represents by far the most extensive set of experiments on variants of GAC algorithms for AllDifferent. Overall, the best combination of optimizations gives a mean speedup of 168 times over the same implementation without the optimizations.

IJCAI Conference 2007 Conference Paper

• Alan M. Frisch
• Matthew Grum
• Chris Jefferson
• Bernadette Mart
• iacute; nez Hern
• aacute; ndez
• Ian Miguel

ESSENCE is a new formal language for specifying combinatorial problems in a manner similar to natural rigorous specifications that use a mixture of natural language and discrete mathematics. ESSENCE provides a high level of abstraction, much of which is the consequence of the provision of decision variables whose values can be combinatorial objects, such as tuples, sets, multisets, relations, partitions and functions. ESSENCE also allows these combinatorial objects to be nested to arbitrary depth, thus providing, for example, sets of partitions, sets of sets of partitions, and so forth. Therefore, a problem that requires finding a complex combinatorial object can be directly specified by using a decision variable whose type is precisely that combinatorial object.

AAAI Conference 2007 Conference Paper

Data Structures for Generalised Arc Consistency for Extensional Constraints

• Ian P. Gent
• Ian Miguel

Extensional (table) constraints are an important tool for attacking combinatorial problems with constraint programming. Recently there has been renewed interest in fast propagation algorithms for these constraints. We describe the use of two alternative data structures for maintaining generalised arc consistency on extensional constraints. The first, the Next-Difference list, is novel and has been developed with this application in mind. The second, the trie, is well known but its use in this context is novel. Empirical analyses demonstrate the efficiency of the resulting approaches, both in GACschema, and in the watched-literal table constraint in Minion.

ECAI Conference 2006 Conference Paper

Automatic Generation of Implied Constraints

• John William Charnley
• Simon Colton
• Ian Miguel

A well-known difficulty with solving Constraint Satisfaction Problems (CSPs) is that, while one formulation of a CSP may enable a solver to solve it quickly, a different formulation may take prohibitively long to solve. We demonstrate a system for automatically reformulating CSP solver models by combining the capabilities of machine learning and automated theorem proving with CSP systems. Our system is given a basic CSP formulation and outputs a set of reformulations, each of which includes additional constraints. The additional constraints are generated through a machine learning process and are proven to follow from the basic formulation by a theorem prover. Experimenting with benchmark problem classes from finite algebras, we show how the time invested in reformulation is often recovered many times over when searching for solutions to more difficult problems from the problem class.

ECAI Conference 2006 Conference Paper

Minion: A Fast Scalable Constraint Solver

• Ian P. Gent
• Christopher Jefferson
• Ian Miguel

We present Minion, a new constraint solver. Empirical results on standard benchmarks show orders of magnitude performance gains over state-of-the-art constraint toolkits. These gains increase with problem size – MINION delivers scalable constraint solving. MINION is a general-purpose constraint solver, with an expressive input language based on the common constraint modelling device of matrix models. Focussing on matrix models supports a highly-optimised implementation, exploiting the properties of modern processors. This contrasts with current constraint toolkits, which, in order to provide ever more modelling and solving options, have become progressively more complex at the cost of both performance and usability. MINION is a black box from the user point of view, deliberately providing few options. This, combined with its raw speed, makes MINION a substantial step towards Puget's ‘Model and Run’ constraint solving paradigm.

AIJ Journal 2006 Journal Article

Propagation algorithms for lexicographic ordering constraints

• Alan M. Frisch
• Brahim Hnich
• Zeynep Kiziltan
• Ian Miguel
• Toby Walsh

Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O ( n ) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq.

ECAI Conference 2004 Conference Paper

Symmetry Breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern

• Alan M. Frisch
• Christopher Jefferson
• Ian Miguel

AIJ Journal 2003 Journal Article

Fuzzy rrDFCSP and planning

• Ian Miguel
• Qiang Shen

Constraint satisfaction is a fundamental Artificial Intelligence technique for knowledge representation and inference. However, the formulation of a static constraint satisfaction problem (CSP) with hard, imperative constraints is insufficient to model many real problems. Fuzzy constraint satisfaction provides a more graded viewpoint. Priorities and preferences are placed on individual constraints and aggregated via fuzzy conjunction to obtain a satisfaction degree for a solution to the problem. This paper examines methods for solving an important instance of dynamic flexible constraint satisfaction (DFCSP) combining fuzzy CSP and restriction/relaxation based dynamic CSP: fuzzy rrDFCSP. This allows the modelling of complex situations where both the set of constraints may change over time and there is flexibility inherent in the definition of the problem. This paper also presents a means by which classical planning can be extended via fuzzy sets to enable flexible goals and preferences to be placed on the use of planning operators. A range of plans can be produced, trading compromises made versus the length of the plan. The flexible planning operators are close in definition to fuzzy constraints. Hence, through a hierarchical decomposition of the planning graph, the work shows how flexible planning reduces to the solution of a set of fuzzy rrDFCSPs.

IJCAI Conference 2003 Conference Paper

Multiset Ordering Constraints

• Alan Frisch
• Ian Miguel
• Zeynep Kiziltan
• Brahim Hnich
• Toby Walsh

We identify a new and important global (or nonbinary) constraint which ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement a linear time algorithm for enforcing generalised arc-consistency on such a multiset ordering constraint. Experimental results show considerable promise.

EAAI Journal 2001 Journal Article

Efficient flexible planning via dynamic flexible constraint satisfaction

• Ian Miguel
• Qiang Shen
• Peter Jarvis

Recent advances in AI planning have centred upon the reduction of planning to a constraint satisfaction problem (CSP) enabling the application of the efficient search algorithms available in this area. This paper continues this approach, presenting a novel technique which exploits (restriction/relaxation-based) dynamic CSP (rrDCSP) in order to further improve planner performance. Using the standard Graphplan framework, it is shown how significant efficiency gains may be obtained by viewing plan extraction as the solution of a hierarchy of such rrDCSPs. Furthermore, by using flexible constraints as a formal foundation, it is shown how the traditional boolean notion of planning can be extended to incorporate prioritised and preference-based information. Plan extraction in this context is shown to generalise the Boolean rrDCSP approach, being systematically supported by the recently developed solution techniques for dynamic flexible CSPs (DFCSPs). The proposed techniques are evaluated via benchmark boolean problems and a novel flexible benchmark problem. Results obtained are very encouraging.

ECAI Conference 2000 Conference Paper

Flexible Graphplan

• Ian Miguel
• Peter Jarvis
• Qiang Shen 0001

KER Journal 1999 Journal Article

Hard, flexible and dynamic constraint satisfaction

• Ian Miguel
• Qiang Shen

Constraint satisfaction is a fundamental artificial intelligence technique offering a simple yet powerful representation. An increasing amount of attention has recently been paid to the development of constraint satisfaction techniques, and it has become clear that the original formulation of a static Constraint Satisfaction Problem (CSP) with hard, imperative constraints is insufficient to model many real problems. Two important extensions to the classical CSP framework which address some of these deficiencies are flexible and dynamic constraint satisfaction. This paper examines in detail classical, flexible and dynamic CSP. It reviews the motivations behind both extensions, and describes the techniques used to solve each type of problem. The paper employs a running example throughout to illustrate the ideas presented.