| Home |
Constraints Group
Constraint satisfaction is a powerful and successful set of AI technologies that solves problems which can be expressed by a set of variables (and their possible values) and a set of constraints which restrict the values variables can take simultaneously. It is widely used to solve challenging problems such as scheduling and resource allocation.
Distributed Constraint Satisfaction Problems (DisCSPs) is an emerging area of constraint programming where the problem is naturally distributed amongst several locations and cannot be solved in a centralised manner due to resource, privacy and security issues. Thus, the problem consists of a set of related sub-problems, each of which is solved by an agent. Agents communicate with each other in order to ensure that their sub-solutions are compatible so that sub-solutions can be combined in order to obtain a global solution. The fast-growing use of the internet, intranet and virtual organisations and the ever-increasing amount of information accessible through them has brought a demand for more sophisticated constraint satisfaction services which can help exploit these information resources. We are interested in the development of efficient algorithms for solving DisCSPs in both static and dynamic environments.
Projects
Penalty-driven Algorithms for Distributed
Constraint Satisfaction
Ines Arana, Muhammed
Basharu and Hatem Ahriz
| Iterative improvement search has the advantage, over constructive search, of being able to converge quicker on large problems. However, it also has a propensity to converge to local optima in the process. We have developed a new approach for dealing with local optima in distributed iterative improvement by modifying the cost landscape with two forms of penalties which are attached to individual domain values. We use one type of penalty to perturb solutions and the other to help agents learn about (and avoid) domain values frequently associated with local optima. Based on these two forms of penalties, we have developed the DisPeL family of algorithms for solving DisCSPs. We have compared these algorithms to state-of-the-art distributed iterative improvement algorithms. The results of our evaluations show that the DisPeL algorithms are effective alternatives to state of the art distributed iterative improvement algorithms - they solved more problems and typically incurred lower costs in the process. |
Distributed Constraint Satisfaction in
Dynamic Environments
Ines Arana, Bayo
Omomowo and Hatem Ahriz
|
Dynamic constraint satisfaction solves problems where the environment changes over time, i.e. new constraints and/or variables are added/deleted. Although a substantial amount of research has been carried out on dynamic constraints in centralised systems, little effort has been devoted to this field in distributed environments. In this project we investigate dynamic constraints in distributed environments and we develop algorithms for solving problems where constraints change over time. |
Hybrid (Constructive + Local Search) Algorithms
for Distributed Constraint Satisfaction
David Lee , Ines
Arana, Hatem Ahriz and Kit
Hui
| There are two main types of Constraint Satisfaction Algorithms: constructive search and local search (iterative improvement). Local search has the advantage, over constructive search, of being able to converge quicker on large problems. However, unlike constructive search, this type of algorithms are normally not complete, i.e. they are unable to determine that a problem has no solution and they might not find a solution when one exists. We are developing hybrid algorithms which combine the advantages of both types of algorithms in distributed environments, i.e. they are complete and fast. DisPBJ is a hybrid algorithm which applies the local search algorithm DisPeL. If DisPeL does not find a solution, the lessons learnt in the process are used to guide the constructive search algorithm Distributed Backjumping obtaining a solution in a significantly faster time. |
Specification of Constraint Problems using
the Z Language
Hatem Ahriz and Ines
Arana
| Although not previously used in this context, we show that the Z language is highly expressive, adaptable, and useful for the construction of constraint problem models. To substantiate this claim, we have:
|
 |