Transcript PPT - ConSystLab - University of Nebraska–Lincoln

Multi-Agent Based Search versus Local Search and Backtrack Search for Tight CSPs:
Solving a Real-World Case Study
Hui Zou and Berthe Y. Choueiry
Constraint Systems Laboratory • Department of Computer Science and Engineering, University of Nebraska-Lincoln • {hzou|choueiry}@cse.unl.edu
Abstract
Results
Definitions
A Constraint Satisfaction Problem (CSP): is a triple P = (V, D, C), where
• V = {V1, V2,..., Vn}, a set of variables.
• D = {DV1, DV2,..., DVn}, the set of variable domains.
• C = {Ci, Cj,k,..., Ci,j,...,m,..., Cn}, a set of constraints on variables in V.
● Only ERA was able to find a full solution to all solvable problems.
Available Resource
CC (×108)
Unassigned Courses
Solution Quality
Unused GTAs
Available Resource
CC (×108)
Unassigned Courses
Solution Quality
Unused GTAs
Available Resource
CC (×108)
29.6
1.18
6
4.05
2
6.5
3.77
5
3.69
0
6.4
0.87
0
3.20
0
5.3
0.18
O
×
26
69
26
29.6
0.88
16
3.79
0
2.5
4.09
13
3.54
0
0.9
0.39
24
2.55
8
8.3
7.39
B
√
35
65
31
29.3
1.06
2
3.12
0
2.5
1.71
4
3.01
0
3.8
0.33
0
3.18
1
1.9
2.68
O
√
34
65
30
29.3
1.02
2
3.12
0
1.5
2.46
4
3.04
1
3.7
0.10
0
3.27
0
0.8
1.15
B
√
33
31
16.5
13
1.27
1
3.93
0
3.5
2.39
2
3.40
0
5.0
0.85
0
3.62
2
3.0
0.02
O
×
28
31
11.5
13
0.88
4
3.58
0
1.8
2.56
4
3.61
0
2.0
0.16
8
3.22
1
2.0
0.51
B
√
36
54
29.5
27.4
1.08
3
4.49
2
4.2
1.17
3
3.62
0
3.9
0.32
0
3.03
1
2.8
0.49
O
√
34
54
27.5
27.4
1.00
3
4.45
0
2.2
1.53
4
3.63
0
3.3
1.42
0
3.26
0
0.8
0.14
Unused GTAs
35
Solution Quality
69
Fall2001b
Unassigned Courses
Ratio
35
Total Capacity
√
Solvable?
B
Spring2001b
Fall2002
Spring2003
● When the ratio of total capacity to total load is greater than 1 (problem may
or may not be solvable), ERA clearly outperforms BT and LS. Conversely,
when the ratio is less than 1 (problem is necessarily over-constrained), ERA's
performance is the worst, as shown in Fig. 1. On average (see Fig. 2), LS
performs much fewer constraint checks than ERA, which performs fewer
constraint checks than BT.
Fig.1 unassigned courses
systematic search
local search
multi-agent
90%
80%
70%
60%
50%
40%
30%
20%
20
16
15
13
10
8
6
4 4
5
10%
3
4
4
O
B
O
B
fall2001b
systematic search
O
B
fall2002
0
0
fall 01b
(1.02)
fall 01b
(1.06)
0
1
0
2
0
0
spring2003
local search
5
3 3
2
0
O
4
2
0%
spring2001b
Hard assignment: none of the variables is assigned the value.
24
25
100%
B
Deadlock state: When a subset of agents competes for positions that are
mutually exclusive but the only positions acceptable for them, a dead-lock
occurs that prevents all agents from being assigned this position.
Fig.2 Constraint checks
unassigned courses
Graduate Teaching Assistants (GTA) Problem : In a given semester, given a
set of GTAs, a set of courses, and a set of constraints that specify allowable
assignments, find a consistent and satisfactory assignment of GTAs to course.
•Consistent - the assignment breaks no constraints.
•Satisfactory -maximize the number of courses covered and the happiness of the
assigned GTAs.
Multi-agent Search (ERA)
Total Load
Local Search (LS)
# Courses
Systematic Search (BT)
# GTAs
Date set
Original/Boosted
We extend the empirical study of a multi-agent search method for solving a
Constraint Satisfaction Problem (CSP). We compare this method's performance
with that of a local search (LS) and a systematic (BT) search, in the context of a
real-world application that is over-constrainedthe assignment of Graduate
Teaching Assistants (GTA) [1] to academic tasks. We report our observations
and summarize our analysis of the main features and limitations of this multiagent search. We show that for solvable, tight CSPs, multi-agent search clearly
outperforms both LS and BT, as it finds a solution when the other two
techniques fail. However, for over-constrained problems, the multi-agent search
method degenerates in terms of stability and the quality of the solutions
reached. We identify the source of this shortcoming and characterize it as a
deadlock phenomenon.
spring 01b
(0.88)
multi-agent
fall 02
(0.88)
spring 03
(1.00)
spring 03 spring 01b
(1.08)
(1.18)
fall 02
(1.27)
data set (ratio)
● Fig. 3 and Fig. 4 show that the performance of ERA is more stable when
solving solvable problems than when solving unsolvable problems.
Fig.3 ERA performance on solvable problem
Search Strategies
70
65
60
55
50
45
40
35
30
25
20
15
fall 2001b
spring 2003
fall 2002 (B)
iteration
1
Systematic Search:
45
spring 2001b (B)
# agents in zero position
Soft assignment: using some conflict resolution strategy, some of the variables
are assigned the value in a manner that respects its capacity constraint.
# agents in zero position
Fig.4 ERA performance on unsolvable problems
20
39
58
77
96
115
134
153
172
191
spring 2001b (O)
40
35
30
25
20
fall 2002 (O)
15
iteration
10
1
20
39
58
77
96
115
134
153
172
191
● ERA is not able to avoid deadlocks and yields a degradation of the solution.
Local Search: hill-climbing with min-conflict [2] heuristic and constraint
propagation.
Multi-agent based search: Liu et al. [3] presented an algorithm, called ERA
(i.e., Environment, Reactive rules, and Agents). The environment records the
number of constraint violations of the current state for each value in the domains
of all variables. Each variable is an agent, and the position of the agent
corresponds to the value assigned to this variable. The agent moves according
to its reactive rules.
Each circle corresponds to a given GTA.
Each square represents an agent. Blank
squares indicate that the position is a zero
position for the agent; The filled squares
indicate that although the position is the best
one for the agent, it results in some broken
constraints. and the actual assignment of the
position to the agent cannot be made.
Experiments
(colorless) agent in zero
position
(colorful) agent in
deadlock
# total agents : 65
# agents involved in
deadlock: 24
# unused GTAs: 8
Discussion
Experiments: We compared the performance among the three search
strategies by solving GTA problem for the real-world data of spring2001b,
fall2001b, fall2002 and sping2003. Since all the problems were difficult to solve
(and two of them are indeed unsolvable), we boosted the available resources to
transform these problems into solvable ones. To accomplish that, we added
extra resources – dummy GTAs into the data set. And we tracked the movement
of each agent in ERA model to find out the deadlock phenomenon.
• Global vs. local repair
• Soft vs. hard assignment
• Stable vs. unstable evolution
• Solvable vs. unsolvable problems
Future research directions
• Development of conflict resolution strategies to overcome deadlocks.
• Experiment with search hybridization techniques with LS.
Methodology
References
We compared the search techniques according to five criteria:
1. Unassigned courses: the number of courses that are not assigned a GTA.
2. Solution quality: the geometric average of the preferences.
3. Unused GTAs: the number of GTAs not assigned to any task.
4. Available resources: the cumulative value of the remaining capacity of all
GTAs after assignment.
5. CC: the number of constraint checks.
1. R. Glaubius and B. Y. Choueiry, Constraint Modeling and Reformulation in the Context of
Academic Task Assignment. In Working Notes of the Workshop Modeling and Solving Problems
with Constraints, ECAI 2002.
2. S. Minton, M. D. Johnston, A. B. Philips, and P. Laird. Minimizing Conflicts: A Heuristic Repair
Method for Constraint Satisfaction and Scheduling Problems. Artificial Intelligence, 58:161-205,
1992.
3. J. Liu, H. Jing, and Y.Y. Tang. Multi-agent oriented constraint satisfaction. Artificial
Intelligence, 136:101-144, 2002.
This work was supported by NSF grant #EPS-0091900