Computer Science 890CE - Constraint-Based Agents

Course Outline - Fall 2014

Instructor:	Dr M. Mouhoub		Office: CW 308.13
Method of Evaluation:	Report	30%
	Presentation 20% Implementation 30% Oral Exam 20%

Recommended Documentation

• Constraint-Based Agents, by A. Nareyek, LNAI 2062, Springer Verlag, 1998
• Foundations of Constraint Satisfaction, Tsang, E.P.K, Academic Press, London and San Diego, 1993.
• On-line guide to constraint programming by Roman Barták.
• Algorithms for Constraint Satisfaction Problems: A Survey, Kumar, AI Magazine 13(1):32-44, 1992.

Topics

• Parallel and Distributed Constraint Solving
• Constraint-Based Agents
• Using Global Constraints for Local Search
• Structural Constraint Satisfaction
• Agent-Based Recommender Systems under Constraints and Preferences

Report Format

· The report should be submitted ONLY in PDF (preferred) or MS Word (.doc).

· The report should be formatted as follows

1. 20 to 30 pages. 8 1/2 x 11 inches portrait format, with a single column.

2. Text must be single-spaced

3. Times New Roman regular 12 pts (or similar).

· The following structure should be followed

1. Title page

1. Title (should be clear, descriptive and not too long)

2. Your name

3. Your affiliation

4. Your e-mail address

5. Abstract: should be clear, descriptive, self-explanatory and not longer than 250 words.

6. list of keywords (3 to 5)

2. Body of text (divided in sections and subsections)

3. Conclusion

4. Acknowledgements (if any)

5. References

Presentation

· The slides should be submitted ONLY in PDF or PPT (MS Powerpoint) at least 3 days before the scheduled presentation.

· 25-30min for the presentation followed by questions and the oral exam.

Project Topics

1. Constraint Solving for Combinatorial Reverse Auctions (CRA) (Shil)

A. Formally define the CRA (with its variants) as a constraint optimization problem.

B. Study the different exact and approximation methods for solving the CRA problem. These methods include the following.

a. Branch and Bound

b. Evolutionary techniques (GAs, ACOs...etc)

c. Stochastic Local Search (SLS) algorithms

C. Using a parallel/distributed architecture, implement and experimentally compare the above techniques on CRA problem instances.

2. Variable and Value ordering Heuristics for Constraint Processing (Ket Wei)

A. Study the effects of variable and value ordering heuristics on constraint problems (both decision and optimization problems).

B. Study the different variable and value ordering heuristics

a. Static ordering heuristics

b. Dynamic ordering heuristics

c. Ordering heuristics based on information gathering and learning

C. Using a parallel/distributed architecture, implement and experimentally compare the above techniques on constraint problem instances.

Up:Teaching

Malek Mouhoub 2014-09-02