Florida Institute of Technology

Instructor: Debasis Mitra

AAAI resorces on constraint-based reasoning

chapter01.pdf

A constraint benchmark
library

chapter02.pdf

Spring 2008:

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

-------------------------

The Syllabus

------------------------------------

Fall 2003:

ORDER FOR THE EDWARD TSANG'S
BOOK
FROM THE U OF ESSEX IN ENGLAND

*AS SOON AS POSSIBLE*.

IT TAKES A WHILE TO RECEIVE THE COPY.

Class Room: EC129, Time: Wednesday 6:30 pm - 9 pm

Project reports should be written using the Chicago-style, information
about it is available at
http://computer.org/author/style/index.htm

------------------------------------

Students without AI background need to Study at least the following
materials:

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.

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:

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.
*

*
*

Some suggested projects:

(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

Home works will possibly be from the problems in the
CSPlib

Some Works from Fall 2002

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

------------------------------------

Fall-2004:

Home Work 1

Presentation schedule.

------------
*Materials are copyrighted to me (year 2007).*
*E-mail:
dmitra@zach.fit.edu*