#### 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-constrainedthe 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