AAAI resorces on constraint-based reasoning
Spring 2008:
----------------------
The Syllabus
------------------------------------
ORDER FOR THE EDWARD TSANG'S
BOOK
FROM THE U OF ESSEX IN ENGLAND
Class Room: EC129, Time: Wednesday 6:30 pm - 9 pm
Students without AI background need to Study at least the following
materials:
A review paper to start with is here.
Faheim Bacchus' has a good course, linked
here.
The link
to some previous offering of this course.
Has changed considerably.
The four components of the course: Lectures, Software usage, Self-study, Implementation-projects (see the syllabus)
Lecture topics:
Some suggested projects:
Home works will possibly be from the problems in the
CSPlib
Some Works from Fall 2002
Fall-2004:
Home Work 1
chapter01.pdf
A constraint
chapter02.pdf
Class: Crawford 401, TR 8-9:15 pm.
Plan for the senester.
HomeWork 1
HomeWork 2
Course Feed Back due 4/10/08
Fall 2005:
Class Crawford S402, Friday 5-8 pm.
9/3/05: Johannes on Assignment 1 (25 min)
Benjamin on minimal network etc, and Assignment 2 (1 hr)
Gary on Arc Consistency from text and Mackworth's paper) (1 hr)
9/9/05: Johannes on Path Consistency from book plus Macwarth's paper (1 hr)
Benjamin on Higher level consistency, sectio 3.4-3.5 (1 hr)
Gary on Section 3.6 and 3.7 (30 min)
Homework 2 discussion: all
9/16/05: Benjamin (20 min max): i-consistency etc. of last class, sec 4.1,2
Johannes: directional consistencies (1 hr),
Gary: width and local consistency sec 4.3 (30 min)
Benjamin: Adaptive consistency bucket elimination sec 4.4 (30 min).
Homework 3 (ch 3): Due 9/23/05: Exc 1, 4, 7, 12, 17, find "csplib" on the web and formulate 2 problems therein,
pick up any one of the Escher sketches and TRY to formulate it as a constraint satisfaction problem
9/25/05: Ch 5 Look-Ahead: Gary: 5.1 & 2 up to BackMarking
Benjamin: 5.3 Look-ahead strategies
Johannes: 5.3.3 cycle-cutset onwards through end
Homework 4 (Ch 5): Due 10/7/05: Exc 3 a, b, c, d; Exc 4 c d; and Exc 12 a, b.
9/30/05: Ch 6 Look-Back Strategies: Johannes: 6.1-2 two back-jumping algorithms (40 min)
Benjamin: 6.3-4 complexity and learning algorithms
Gary: 6.5-end: Look-back on SAT, integrated algorithms, and phase transition
10/7/05: Johannes: Protein docking as a constraint reasoning problem (30 min),
Gary: Temporal reasoning problem (ch 12 up to including 12.2.0 p348, 30 min),
Benjamin: 12.2.1 - end (30 min),
Re-doing Ch6: Gaschnig+Graph-based bj: Benjamin (25 min),
CBJ+FcCbj: Gary (25 min), Graph-based learning, SAT-cbj-learning: Johannes (25 min)
10/14/05: Benjamin: TCSP end parts (30 min)
HW3: 1,4 - Gary, 7,12 - Benjamin, 17 - Johannes
HW4: 3 - Gary, 4 - Johannes, 12 - Benjamin
(Time permiting) Conflict-directed Bacjumping: ??
10/21/05: Spatio-temporal calculi (from Renz slides): Mitra (30 min)
Explanation in CSP and proposal for TCSP: Benjamin (40 min)
Reasoning operators with Quantitative Cyclic-time calculus and Star-calculus (30 min)
2D Shape matching with Bigger algorithm: Johannes (30 min)
We will have to re-do the previous class and push the schedule by 1 day
10/28/05: Gary: Reasoning operators with Quantitative Cyclic-time calculus and Star-calculus (30 min)
Explanation in CSP and proposal for TCSP: Benjamin (40 min)
2D Shape matching with Bigger algorithm: Johannes (30 min)
Benjamin: Golomb ruler problem ch5-12
11/4/05: Tractability of CSP Ch 11.1&2: Gary [Backup: Johannes] (45 min)
Explanation in TCSP: Benjamin (30 min)
11/14/05 Monday 6--9 pm (instead of 11/11/05 holiday): Ch 11.3 -11.4.3: Johannes [Backup: Benjamin] (45 min)
Non-linear TCSP: Gary (1 hr)
11/18/05: Ch 11.4.4 -End: Benjamin (45 min) [Backup: Gary]
Demo of 2D shape matching and proposal for using Star-calculus: Johannes
12/2/05: The exercise on gadget: express => using (or, not): Benjamin (20 min)
On three projects introduced in the class (15 min: me)
Project presentations: Gary, Benjamin and Johannes (30 min each)
I need your project report or demo (Johannes) by Friday in order to grade it in time.
Fall 2004:
Programming Assignment (Due Oct 27):
(1) Empirically check if AC enforcement and PC enforcement operations
are commutative or not,
(2) If not, then does one of the two orderings (AC then PC, and PC then AC)
produces tighter network than the other one, in general case?
(3) Modify the PC algorithm (by allowing i=k and j=k) so that it coverges to
a network that is the stable network of AC and PC run alternatively until
relaxed. Verify the modified PC is really satisfying the later
objective.
Run on at least 10 examples before making any conclusion.
Self-study Presentation:
Find at least one paper on the theme you have chosen to work on and present
it to the class. Abstract submission due Oct 20. Presentation schedule will
be announced (1 hr each).
12/8/04: Ch 12: Mitra
12/15/04: Ch 11 presentation assignment
Venkatesh: Sec 11.1 and 2
Yang: Sec 11.3 through 11.4.4 inclusive
Gandhali: Sec 11.4.5 through end
------------------------- Abstract
Constraint reasoning is a way of looking at many computational problems. It involves a set of variables, their domains, and relational constraints between some of those variables regarding what values they can take. An example is the map coloring problem where the variables are the regions on a map, all variables/regions have the same domain as a finite set of available colors to choose from the regions, and the constraints are the adjacency information between the regions in the map and an assertion that no adjacent regions may have the same color. Given an instance of such a map-coloring problem there may or may not exist a solution. When the question is to check if there exists a solution or not - it is called a constraint-satisfaction problem (CSP). Alternatively the question could be to find a solution (e.g., a color assignment to each region) if there exists one. This type of view (variables, constraints) of problems is called constraint reasoning. Sometimes they could be optimization problems also, when the best solution is to be found, not just any solution. Scheduling problems are such constraint optimization problems. In the last few decades constraint reasoning area have been heavily researched within the AI. Apparently 20% of the papers in the major AI conferences come from related areas.
Fall 2003:
AS SOON AS POSSIBLE.
IT TAKES A WHILE TO RECEIVE THE COPY.
Project reports should be written using the Chicago-style, information
about it is available at
http://computer.org/author/style/index.htm
------------------------------------
Introduction (Ch 1), Problem solving by searching (Ch 2), Informed
search methods (Ch 3), Game playing (Ch 5) from the standard AI Text book
of Russell and Norvig, ISBN 0-13-103805-2, Printice-Hall, 1995,
or from any other text.
Basic examples of CSP, e.g., map coloring, N-queens etc.
Related lecture slides are here (8/28/02).
Solving of CSP: minimal problem, backtracking, search space
Related lecture slides are here (9/03/02).
Fundamental concepts in CSP: satisfiability and consistency, k-consistency for different k values, directional arc-consistency,
Arc-consistency-x and path-consistency-x algorithms (for integer x),
Other consistency algorithms
Search strategies: chronological BT, iterative broadening,
forward checking, dependency-directed back-jumping
Current and advanced issues in CSP
Spatio-temporal CSP: point-based temporal reasoning, algebraic concepts,
Allen's interval algebra, Ligozat's Cardinal algebra,
Mitra's Star-algebra, Region Connection Calculi series
Acknowledgement: Some lecture notes are originally prepared by
Hyoung Rae Kim.
(1) Join Kim in experimenting with search algorithms
(2) Air trafiic control as a dynamic CSP
(3) Symmetry in CSP
(4) Learn and use EcLIPSE software
Students and their tentative interests:
Peter Engrand: Related to model-based diagnosis
Raghunath Vemuri: Neighborhood interchangability in CSP solutions
Lajos Nagy: A spatio-temporal scheduling problem using Eclipse(tm)
Weijian Chai: On GUI development using Condotta's rectangle algebra
Gaurav Tandon: Anomaly detection problem as a CSP
------------------------------------
Presentation schedule.
------------
Materials are copyrighted to me (year 2007).
E-mail:
dmitra@zach.fit.edu