Modifying landscapes with penalties in iterative improvement for solving distributed constraint satisfaction problems.

Basharu, Muhammed Bashiru

Abstract

The recent growth of the internet and distributed computing facilitated by the internet has created more opportunities for collaboration between individuals and organisations. These new forms of collaborative activity put groups of participants in situations where there is a shared objective but at the same time there is also a competition for resources by the participants. Hence, there is a need for participants to make compromises in order to reach agreement. Examples of such situations include collaborative scheduling in supply chain management or even individuals trying to agree on a schedule of meetings. The process of reaching agreement on any of such situations can be automated and the first step in such automation may be to model the situations as Distributed Constraint Problems (DisCSPs). DisCSPs formally describe distributed problems where each participant in the problem is represented by an agent, and the collection of agents have to collaborate in order to reach a satisfactory agreement (or find a solution) for a problem. Yokoo’s seminal work on distributed constraint solving introduced the idea of distributed approaches to solving such problems. And following that, research in the new field has come up with a variety of techniques, including combinatorial search and other forms of inference, for solving DisCSPs. In this study, we investigate an iterative improvement search approach for solving DisCSPS. Iterative improvement search has the advantage, over constructive search, of being able to converge quicker on large problems. But, it also has a propensity to converge to local optima in the process. Previous work on iterative improvement search (in centralised and distributed forms) has considered a variety of techniques for dealing with the problem of convergence on local optima. Prominent amongst these include introducing forms of randomisation or modifying the shapes of objective landscapes to guide a search out of plateaus. We present 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. We argue that, compared to other forms of landscape modification, our approach has a more dramatic effect on cost landscapes and hence, it is a more effective strategy for solving DisCSPs by iterative improvement search. Based on the idea of using two forms of penalties for dealing with local optima, we introduce three new distributed algorithms for solving DisCSPs where the objective is to find the first solution that satisfies all constraints simultaneously. First, we introduce the Distributed Penalty Driven Search (DisPeL) which is built around a two phased strategy of using penalties. We also introduced a stochastic variation of that algorithm (Stoch- DisPeL), which reduces some of DisPeL’s complexities and allows agents to randomly decide which of the two penalties to use when dealing with local optima. These two algorithms are specifically designed for scenarios where each agent represents a variable in a DisCSP, unlike our third algorithm (Multi-DisPeL) which extends some of the ideas from the earlier algorithms to DisCSPs where each agent represents multiple variables. We evaluated all three algorithms on a number of distributed constraint satisfaction problems including distributed graph colouring, distributed Boolean satisfiability, and random DisCSPs. We also compared them to state-of-the-art distributed iterative improvement algorithms. The results of the evaluations show that the penalty driven algorithms are effective alternatives; they solved more problems and typically incurred lower costs in the process.

Citation

BASHARU, M.B. 2006. Modifying landscapes with penalties in iterative improvement for solving distributed constraint satisfaction problems. Robert Gordon University, PhD thesis. Hosted on OpenAIR [online]. Available from: https://doi.org/10.48526/rgu-wt-2807293

• Thesis Type: Thesis
• Deposit Date: May 16, 2025
• Publicly Available Date: May 16, 2025
• DOI: https://doi.org/10.48526/rgu-wt-2807293
• Public URL: https://rgu-repository.worktribe.com/output/2807293
• Award Date: Sep 30, 2006