Presenting a model for solving constraint satisfaction problems using multi-agent systems

Master's Thesis in Computer Engineering (Artificial Intelligence)

Abstract

Multi-agent systems are computing systems in which several agents interact and work together to achieve a specific goal. The reason for the emergence of such systems is the existence of situations in which a problem must be solved in a distributed fashion. For example, in situations where the use of a central controller is not possible, or when we want to make proper use of distributed resources or computing facilities. Although not much time has passed since the introduction of such systems, the use of agent-based design methods is one of the most successful solutions available, and the result of this design method, the distributed problem solving system, is considered one of the best systems and is known as a new tool for solving all kinds of human processes. The problem of distributed constraint satisfaction has been receiving a lot of attention in the field of multi-agent systems research for years. And this is because many problems ranging from classical problems such as the n-minister problem and graph coloring to large real-world practical problems such as scheduling and planning and resource allocation can be formulated to be solved as a distributed constraint satisfaction problem. Therefore, presenting a new method or modifying the current methods has a great impact on the research scope of this field. What is presented in this thesis is a new technique for solving distributed constraint satisfaction problems. This new technique manages and controls the constraints in a system that is a combination of distributed and centralized systems, which is distinguished from other existing hybrid systems by using a series of specific features defined. The obtained results show that this algorithm will work well in large-scale problems and obtains almost a linear time complexity with the increase of the problem scale. Also, the comparison of this method with several other methods shows the improvement of the performance of this method in different parameters compared to other methods. Chapter 1 Introduction Since 1974, Constraint Satisfaction Problems (CSP[1]) were proposed in the image processing problem[2]. Since then, CSP has been widely used as an important solution method in many fields of artificial intelligence and computer science. From multi-minister problem [3] and graph coloring [4] and other classical problems to scheduling [5] and resource allocation [6] and other large application problems can be formulated to be solved as a CSP problem. After 1990, by replacing the general programming language with the logical programming language, the constraint satisfaction problem of CSP application to solve problems was greatly improved [1]. A CSP is defined by a set of variables, a domain for each of them, and limits on the values ??that the variables may take simultaneously. The role of constraint satisfaction algorithms is to assign values ??to variables in a way that is compatible with all constraints or to specify that no assignment is possible. Today, constraint satisfaction techniques are used in various fields such as machine vision, natural language processing, theorem proving, scheduling, etc. are used [4].

On the other hand, there are situations in which a problem must be solved in a distributed mode, for example in situations where the use of a central controller is not possible, or when we want to make proper use of distributed resources or computing facilities. In such cases, agents [7] try to reach a common goal. Any multi-agent system is a computing system in which several agents interact and work together to achieve a specific goal [4]. Distributed Constraint Satisfaction Problem (DCSP[8]) is actually a distributed state of the classical constraint satisfaction problem in which the variables are distributed among independent agents. This distributed environment includes a number of intelligent agents, each of which owns one or more variables and controls its value. All these factors are trying to achieve a common goal by maintaining their independence. The goal is still to find an assignment for the variables that takes into account the constraints, but each agent decides for the value of its own variable with relative autonomy. Although the agents do not have a common view, each of them can communicate with its neighbor in the constraint graph.Each agent tries to get closer and closer to this goal not only by satisfying its local constraints but also by communicating with other agents in order to solve external constraints. In general, all problems in which the goal is to find suitable values ??to assign to distributed variables can be considered as distributed constraint satisfaction problems. In a multi-factor system, each factor is assigned one or more variables from among the distributed variables. The task of this autonomous agent is to control and manage the value of this variable [4] and [22]. This general problem has many applications in real life. For example, in many resource allocation problems: in wireless sensor networks, urban traffic signal control, distributed sensor networks, disaster recovery problems, and many scheduling problems, for example, for trains and universities. The common goal in solving all these problems is to find suitable values ??to assign to the distributed variables. In other words, any problem whose purpose is to find a suitable value to assign to distributed variables can be designed as a DCSP.

In this research, distributed constraint satisfaction problems are discussed, in which agents try to find a possible solution for the problem in a distributed fashion.

Constraint satisfaction problem

Definition of the constraint satisfaction problem

As a formal definition, a CSP can be defined by its three main components. Kord[3]:

A finite set of variables, {x = {x1, x2, …, xn;

A domain set D, including a discrete and finite domain for each variable;

D = {D1, D2, …, Dn}, Di = {d1, d2, . . ., d|Di| } for xi , i = 1, 2, . . . ,        

A set of constraints, { C = {C1(x1 ), C2(x2 ), …, Cm(xm), where xi, i=1, 2, . . . ,n are subsets of x and Ci(xi) determines the values ??that the variables inside xi cannot assume simultaneously. For example, a constraint in the form ?C({x1, x2}) = ?d1, d2 means that when x1 = d1 then the value of d2 cannot be assigned to x2 and when x2 = d2 x1 cannot take the value of d1. A Cartesian product of n sets of finite domain, in other words, S = D1 × D2 × . . . × Dn. A solution for a CSP in the form: s = ?s1, s2, …, sn ? ? S, is an assignment of values ??to variables so that this assignment satisfies all constraints. Here is a simple example of describing a CSP problem:

All possible solutions to the problem described above are: ??1,2,2, ??1,2,3, ??2,2,2, ??2,3,2, ??3,2,2.

In simpler terms, a CSP, with a set of variables, a domain for each of them, and constraints They are defined in the values ??that the variables may take simultaneously. The role of constraint satisfaction algorithms is to assign values ??to variables in a way that is compatible with all constraints or to specify that no assignment is possible. Figure 1-1 shows a simple example of a CSP problem that has three variables x1, x2, x3 and constraints x1<>x3 and x2<>x3.

(formulas are available in the main file)

As mentioned, many real world problems can be formulated to be solved as a CSP problem. Figure 2-1 shows a general scheme of applying the constraint satisfaction technique to solve problems. Having a description of the problem, one way to determine how this problem can be solved by the constraint satisfaction technique is to define three components: variables, range of variables, and constraints. If these three components can be defined for the problem, this problem can be solved by constraint satisfaction techniques [54].

Classical algorithms of constraint satisfaction problems

In general, 4 algorithms have been introduced as classical paradigms for solving CSP problems [1]:

Backtracking algorithm (BT[1]), iterative deepening algorithm (IB[2]), forward check algorithm (FC[3]), backward jumping algorithm (BJ[4]).

These algorithms use a tree structure to show the current search state. Each node of the tree can be considered as a partial solution [5]. At the same time, the values ??of some variables from each node are detected by a parent decision node layer, these variables are called past variables.