List of projects for 2011

Some papers are available from the Electronic Reserve of the Love Library (UNL access only) .

Basic Topics

Topic: Rules of the Game Course Syllabus, our 'contract.' Instructor's slides: Administrative Note (PPT) Instructor's slides: Guidelines for reports (PPT) Required reading: Syllabus

Topic: CSP 101, Overview Instructor's slides: Constraint Processing 101 (PPT) Quick review of NP-Completeness (by Shant and Rahul). Required reading: Dechter: Section 1.1, 1.3.3, 1.3.4, 2.1 and 2.2. Constraint Programming: in Pursuit of the Holy Grail (PDF) Bartak Recommended reading: Bartak's on-line guide: Introduction to CSPs Constraint Satisfaction (PDF) Rina Dechter. MIT Encyclopedia of the Cognitive Sciences  Algorithms for Constraint Satisfaction Problems: A Survey (PDF) by Vipin Kumar. AI Magazine Spring 1992. Constraint Satisfaction Problems, An Overview (PDF), Pedro Meseguer  Systematic Search Algorithms (Bartak's online notes) Heuristics and Stochastic Algorithms (Bartak's online notes)

Topic: Backtrack Search Instructor's slides: A Theorectical Evaluation of Selected Backtracking Search (PPT) Required reading: Hybrid algorithms for the constraint satisfaction problem (PDF) Prosser Recommended reading: Chapters 5 and 6, Dechter Chapter 5, Tsang

Topic: Continuation of CSP 101, Overview Instructor's slides: Overview: advanced solving techniques and research directions Required reading: Freuder and Hubbe: A Disjunctive Decomposition Control Schema for Constraint Satisfaction (CP 1993) Peter Cheeseman et al.: Where the Really Hard Problems Are (IJCAI 1991).

Topic: DB & CSP Instructor's slides: DB & CSP Required reading: Section 1.3 of Dechter

Topic: Lookahead Schemas Instructor's slides: Lookahead Schemas (PPT) Required reading: Dechter, Sections 5.3.1 and 5.3.2 Recommended reading: The rest of Section 5.3 in Dechter.

Topic: Theoretical Evaluation of BT Algorithms Instructor's slides: Theoretical Evaluation of BT Algorithms Required reading: A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek (IJCAI 1995) Recommended reading: Dechter, Chapters 5 and 6

Topic: Evaluating & Comparing (Deterministic) BT Search Algorithms Instructor's slides: Evaluating & Comparing (Deterministic) BT Search Algorithms (PPT). Required reading: Dechter, Section 6.6 Recommended reading: Evaluating Constraint Processing Algorithms Dechter and Frost (AIPS 98 Workshop?)

Topic: Basic Consistency Properties Instructor's slides: Basic Consistency Methods (PPT) Required reading: The complexity of some polynomial network consistency algorithms for constraint satisfaction problems Mackworth & Freuder, AIJ 1985 Dechter Section 2.3 Dechter Section 3.1--3.4, 3.5.1, 3.5.3, 8.1 Recommended reading: Dechter Chapter 3, entirely Constraint Propagation, Bessiere, Chapter 3, Handbook of Constraint Programming, 2006. Networks of Constraints: Fundamental Properties and Application to Picture Processing, Montanari, Information Sciences, 1974 Path Consistency on Triangulated Constraint Graphs, Bliek, Sam-Haroud, IJCAI 1999. Consistency in Networks of Relations, Mackworth, AIJ 1977. Constraint propagation with interval labels, Davis, AIJ 1987. Neighborhood Inverse Consistency Preprocessing, Freuder and Elfe AAAI 96 Optimal and Suboptimal Singleton Arc Consistency Algorithms, Bessière, Debruyne, IJCAI 2005

Topic: An Efficient Propagator for the All-Diff Constraint Instructor's slides: A Consistency Algorithm for AllDifferent Constraint (PDF). Required reading: Régin (AAAI 94): A Filtering Algorithm for Constraints of Differences in CSPs. Dechter, Section 3.5.1. Recommended reading: An N^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs, Hopcroft and Karp, SIAM Journal on Computing, Vol 2, No 4, December 1973. Check the literature for recent developments on All-Diff constraint and other global constraints.

Topic: Search Orders in CSPs Instructor's slides: Search Orders in CSPs (PPT) Required reading: Search Orders in CSPs, Chapter 6, Tsang 93 Recommended reading: Dechter: Sections: 5.1.1 Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen ECAI 92

Topic: Structure-Based Methods Instructor's slides: Structure-Based Methods: An Introduction (PPT). Required reading: Dechter Sections: 2.1.3, 5.1.2, 10.1.1, 9.2, 4.4, 9.2.2. Recommended reading: Tree Clustering Schemes for Constraint Processing, Dechter and Pearl, AIJ 1989 Enhancement Schemes for Constraint Processing: Backjumping, Learning, and Cutset Decomposition (PDF not available yet), Dechter, AIJ 1990. Synthesizing constraint expressions, Freuder, JACM 1978 A Sufficient Condition for Backtrack-Free Search, Freuder, JACM 1982 A Sufficient Condition for Backtrack-Bounded Search, Freuder, JACM 1985

Topic: Advanced Consistency Techniques Instructor's slides: More on Consistency Properties (PPT). Required reading: Dechter, Sections 3.1, 3.2, 3.3, 3.4, 3.5.1, 3.5.3, 8.1 Dechter, Sections 2.1.3, 4.4, 10.1.1, 9.2, 9.2.2 Recommended reading: Neighborhood Inverse Consistency Preprocessing, Freuder and Elfe AAAI 96 Optimal and Suboptimal Singleton Arc Consistency Algorithms, Bessière, Debruyne, IJCAI 2005 Tree Clustering Schemes for Constraint Processing, Dechter and Pearl, AIJ 1989 Enhancement Schemes for Constraint Processing: Backjumping, Learning, and Cutset Decomposition Dechter, AIJ 1990. A Sufficient Condition for Backtrack-Free Search, Freuder, JACM 1982 A Sufficient Condition for Backtrack-Bounded Search, Freuder, JACM 1985

Topic: Least Commitment Instructor's slides: Least Commitement: Rationale and Strategy (PPT).

Topic: Advanced Backtrack Search Instructor's slides: Advanced BT Search (PPT). Required reading: ECLiPSe: Chapter 12 on Search (Credit-Based Search) Recommended reading: Limited Discrepancy Search, Harvey and Ginsberg, copyright IJCAI 1995 Boosting Combinatorial Search Through Randomization, Gomes et al, AAAI 1998. Search in a Small World, Walsh, IJCAI 1999.

Topic: Local Search Instructor's slides: Local Search (PPT). Required reading: Dechter, Chapter 7 Heuristics and Stochastic Algorithms (Bartak's online notes) Recommended reading: Section 4.3, Chapter 4, AI a Modern Approach (textbook), Russell & Norvig Stochastic Local Search (book), but Hoos and Stuelze

More Topics

Topic: Temporal Reasoning Instructor's slides: Temporal Networks (PPT slides). Required reading: Dechter, Chapter 12 Recommended reading: Koubarakis, CP Handbook, Chapter 19 Many papers in AAAI, IJCAI, CP, ICAPS, by Cesta, Oddi, van Beek, Golumbic & Shamir, Pollack, Tsamardinos, P. Morris, Planken et al., etc.

Topic: Binary vs Non-Binary CSPs: Mappings, FC Instructor's slides: Binary vs. non-binary representations of constraint (ps, pdf). Instructor's slides: Non-Binary FC. Required reading: Binary vs. non-binary representations of constraint-- Bacchus and van Beek, 98. On Forward Checking for Non-Binary Constraint Satisfaction-- Bessiere, Meseguer, Freuder, and Larossa, AIJ 2002. Recommended reading: "On forward checking for non-binary constraint satisfaction" C. Bessière and P. Meseguer and E.C. Freuder and J. Larrosa, Proceedings CP'99, Alexandria VA, pages 88-102.  Decomposable Constraints. Ian Gent, Kostas Stergiou and Toby Walsh. Artificial Intelligence, 123 (1-2), 133-156, 2000.

Topic: Interchangeability and Symmetry in CP Instructor's slides: (PPT). Required reading: Eliminatring Interchangeable Values in Constraint Satisfaction Problems, Freuder, AAAI 1991. Recommended reading: Exploiting symmetries within constraint satisfaction search, Meseguer and Torras, AIJ 2001

Last modified: Tue Nov 8 18:34:57 CST 2011