Courses/CS 460/Fall 2006

From CSWiki

Jump to: navigation, search
Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.

Eugene C. Freuder, "In Pursuit of the Holy Grail," in (inaugural issue of) Constraints, 1997.


Contents

[edit] Resources

[edit] Russell, Stuart and Peter Norvig, Artificial Intelligence: A Modern Approach

http://aima.cs.berkeley.edu/graphics/2esmall.jpg

The following chapters are available as pdf files.

  • Preface
  • 5. Constraint Satisfaction Problems
  • 7. Logical Agents
  • 11. Planning
  • 20. Statistical Learning Methods
  • Bibliography

[edit] On-line CP demonstrations

[edit] JaCoP

[edit] Choco

Choco is an open source project. It seems to run about 4 times slower than JaCoP. See two version of the Partition stress program.

Other Choco examples.

[edit] Other Non-commercial Java Constraint systems

[edit] Commercial Java Constraint Systems


[edit] Other Resources

[edit] Java Expression Parser

[edit] Spreadsheet systems

  • JExcelAPI, a java library which provides the ability to read, write, and modify Microsoft Excel spreadsheets.
  • Apache Jakarta POI HSSF, the POI Project's pure Java implementation of the Excel '97(-2002) file format.
  • Jeppers, a full featured web-based spreadsheet editor written in Java. It also provides an LGPL grid component that can be used in Swing applications.

[edit] Grading and Final Exam Schedule

See Abbott

[edit] AI and Constraint Programming

What is the relationship between AI and constraint programming? In some sense, constraint programming is the prototypical AI application. AI can be differentiated from other applications on four grounds.

  • It tends to be symbolic and unstructured rather than numeric (scientific/engineering) or structured (database/XML).
  • It attempts to solve problems for which one must search for solutions rather than compute them in a straightforward way.
  • Because there are no guaranteed solution techniques, it uses heuristics, which are techniques which work in some situations but not in all.
  • One often writes programs at multiple levels, at both the object and meta levels.

Constraint programming is all of these.

  • It is symbolic in that the problems are usually not (just) straight mathematical formulas to be evaluated.
  • It attempts to solve problems for which one doesn't know how to find the solution. Since the most general constraint problems are NP-complete, not all of them can be solved feasibly. So there are no standard techniques which can be applied reliably to all problems. Instead of executing an algorithm which is more or less guaranteed to find the result, one must search for a solution. One doesn't know in advance whether a solution will be found.
  • Because there are no guaranteed solution shortcuts and the brute force approach is not feasible, heuristics have been developed which can solve subclasses of problems.
  • When using JaCoP, there is also a fair amount of meta-programming. A JaCoP solution typically involves writing a Java program which generates a set of constraints to be solved. Those constraints are then sent to the solver for solution.

[edit] Student pages

Since I've made this a relatively exploratory class—rather than a class in which I'm asking everyone to do the same homework exercises—let's have a page for everyone. To generate a page for yourself, enter [[/your name/]]. This will generate a page called "your name" as a subpage of this page. Once you have generated a page, use that page to document your explorations. (For help on using a wiki, look at the Help:Contents page.)

Instead of turning in homework exercises through CSNS, post them here to the wiki. Unless the code is very short (unlikely for Java) create a subpage of your page for each problem solution. That's what I've done with the various pieces of code that I've written. Look at the Sudoku_solution_in_JaCoP page, for example. It's a subpage of this page.

To get started, I've made pointers to subpages for everyone. I've also created subpages of your subpages for all the .java and .doc files you submitted. Please upload the rest of your work.

I've only copied your submitted .java and .doc files to your wiki pages. Please format your pages and add some explanatory text.

Please put a checkmark ( Image:SmallCheckMark_clear.gif) next to any work that you present in class.

[edit] Sep 22 (Week 1)

Chapter 1 and sections 2.1 and 2.2 from the JaCoP documentation. (JaCoP.zip has been deleted from this page.) That file includes the JaCoP jar file along with two folders of examples and the JaCoP documentation. It also includes an Eclipse project that contains 6 classes: the simple map coloring problem, send+more=money, two versions of the zebra problem, and FDStore, a subclass of FDstore. Dowload and upzip this file and run the map coloring and cryptarithmetic examples.

[edit] Examples

  • FDStore
  • FDVEnum
    • public static void printFDVArrays(String label, FDV[][] arrays)
      has been moved here.
  • SEND plus MORE equals MONEY
    • Improved use of enums
    • Use of
      private static void polyEval(FDstore stor, FDV[] coeffs, int polyVar, FDV polyVal, int min, int max)
      as a substitute for the sumWeights constraint.
  • Zebra puzzle
    • Improved use of enums
  • OO Zebra puzzle
    • Improved use of enums

[edit] Regin Filtering

This is the example I couldn't remember in class. 

package examples;

import java.util.Arrays; 

import JaCoP.*;

public class ReginFilteringExample {
  
  public static void main(String[] args) {

    FDstore store = new FDstore();

    FDV[] fdvs =
      new FDV[] {new FDV(store, "a", 1, 3),
                 new FDV(store, "b", 2, 3),
                 new FDV(store, "c", 2, 3),
                 new FDV(store, "d", 1, 4),
                 new FDV(store, "e", 1, 5)};

    // Require all the FDV's to be different.
    store.impose(new Alldiff(fdvs));

    System.out.println(Arrays.asList(fdvs));
    // Output: [a::{1..3} , b::{2..3} , c::{2..3} , d::{1..4} , e::{1..5} ]

    Solver.consistency(store);
    // The consistency checker is clever enough to
    // know that b and c exhaust the possibilities 
    // for 2 and 3 (even though it doesn't know which
    // is which) leaving only 1 for a. That leaves
    // only 4 for d, which leaves only 5 for e.

    System.out.println(Arrays.asList(fdvs));
    // Output: [a=1, b::{2..3} , c::{2..3} , d=4, e=5]
  }
  
}

[edit] Homework

  • Solve some (at least two) of the cryptarithmetic puzzles here or here.
  • Optional: write a program that takes a crytarithmetic addition problem as input and solves it. The easiest way to pass the input is as an array of Strings, one for each line of the addition. The final element in the array is the summation line.

    Thus SEND + MORE = MONEY as input would be: new String[]{"SEND", "MORE", "MONEY"}

    And TWO + TWO = FOUR as input would be: new String[]{"TWO", "TWO", "FOUR"}

    These arrays would be the argument to 

public static void main (String args[]) { … }

On the command line, of course, they would just be separate words.

I just did it. It's actually an easy problem. In some ways it's easier than solving the specific problem case. I won't post it until Saturday so that you can work on it. It uses only the straight JaCoP library, not FDStore or FDVEnum (Since we don't know the names of the variables in advance, we can't use enumerations for the FDVs.)

[edit] Sep 30 (Week 2)

Notes

[edit] Homework

Solve some (at least two) of the logic puzzles here, here, or here. Use either the "traditional" technique (as in the Zebra puzzle) or the object-oriented technique (as in the OO Zebra puzzle).

[edit] Oct 7 (Week 3)

[edit] Notes

[edit] Homework 3

Other puzzles. (Do at least 2, one by Tuesday midnight and one by Friday midnight.)

[edit] Oct 14 (Week 4)

[edit] Student pages

Moved to Student Pages.

[edit] Minimization (briefly)

We'll return to this later.

[edit] Iterative Deepening

To solve the wolf-goat-cabbage puzzle we must solve two problems.

  1. We don't know how many states we will have. This is like writing a Constraint Satisfaction problem without knowing how many variables we need to represent the problems. We use iterative deepening to deal with that.
  2. Each state is more complex than a single value.

Here is a JaCoP iterative deepening solution to the wolf-goat-cabbage problem.

[edit] Blocks

The blocks problem builds stacks of blocks. One starts with some initial configuration of blocks, say 3 blocks (a, b, and c) with a on b, on c, and c on the table {a/b/c}, and ends up with the three blocks stacked the other way {c/b/a}. The allowable moves are to take a block off a stack or off the table and put it on the table or on some other stack.

In general a state is some collection of stacks, e.g., {a/b, c}. This state represents the situation in which block a is on block b (which is on the table) and block c is on the table. A step moves a single block from the top of a stack (or from the table if no block is on top of it) to the top of another stack or to the table. So the following are all valid successors of {a/b, c}. 

{a, b, c}
{b, a/c}
{c/a/b}

As sequence of transitions from {a/b/c} to {c/b/a} would be the following. 

{a/b/c} ~> {b/c, a} ~> {c, b/a} ~> {c/b/a}

One possible approach to representing this problem in JaCoP might be the following. Create a class to represent a state. A state has an instance variable for each block. The value of a block's instance variable is the object it is resting upon. If there are 3 blocks as above 

{a/b, c}

would be represented as 

(a::{b}, b::{table}, c::{table})

since b and c are on the table and a is on b. That is, you are keeping track of the support for each block. Since we are limited to integers, we arbitrarily assign an integer to each block and one to the table.

A transition is valid of the following conditions hold.

  1. Exactly one block was moved, i.e., exactly one support changed.
  2. The block that was moved was not the support of some other block.
  3. A block may not support itself.
  4. The new support for the moved block may be either the table or some other block. If the new support is some block s, then s may not also be the support of some other block.

[edit] Homework 4

Try some other puzzles that require an unknown number of states. (Do at least 2.) For example, you might try blocks as described above. Here are the Missionaries and Cannibals puzzle and the 15 puzzle (and a number of other puzzles).

Or you might try the jugs problem. Try it with an arbitrary number of jugs. Here's a solution with three jugs: 6, 10, and 15. The goal is to get 7 in one of the jugs. 

Goal: 7
Jug sizes:	10  6 15 
------------------------------
Initially:	 0  0  0 
Fill  10:	10  0  0 
10 --> 15:	 0  0 10 
Fill  6:	 0  6 10 
6 --> 15:	 0  1 15 
Empty 15:	 0  1  0 
6 --> 15:	 0  0  1 
Fill  6:	 0  6  1 
6 --> 15:	 0  0  7

Caution. This problem is easier than it seems!

Optional. This problem uses logical meta-predicates (called reification). We used them in the zebra problem. Constraint A is true if and only if Constraint B is true. 

Four men, one of whom has committed a crime, made these statements:
Arch: "Dave did it."
Dave: "Tony did it."
Gus: "I didn't do it."
Tony: "Dave lied when he said I did it." 
If exactly one of these statements is true, who did it?
If exactly one of these statements is false, who did it?

In this case one has problem-level constraints, e.g., Dave did it, meta-level constraints, e.g., "Dave did it" is false, and third level constraints, e.g., exactly one of the constraints is true.

[edit] Oct 21 (Week 5)

  • Let's look at some Choco examples.
  • You can't do an AI class without talking about Search strategies: depth first, breadth first, and A*.

[edit] Homework 5

  • Modify the Searcher (part of Search} to include the A* search strategy.
  • Develop the core and ExtendableState versions of at least two problems, such as blocks, missionaries and cannibals, etc. Solve these problems using all three search strategies: A*, breadth-first, and depth-first. (As it turns out — and this may be difficult to tell in advance — a nice A* metric for the wgc problem is the number of wc on the destination side of the river.) You should come up with similar "closeness-to-the-goal" metrics for the problems you approach.

    It may be interesting to solve Sudoku this way. In Sudoku, the goal is to have all the cells filled in with no violations. But you don't know in advance exactly what the layout will be. So it is up to your satisfiesGoal() predicate to test for a complete and valid solution.

[edit] Oct 28 (Week 6)

[edit] Liars problem

Here's a simple solution to the optional liars problem from two weeks ago.

[edit] The cumulative constraint

See the discussion page entry.

[edit] A* search

See the entry on the discussion page.

[edit] The difference between general search problems and finite domain constraint programming

In finite domain constraint programming problems one has a fixed number of variables (e.g., the letters in SEND + MORE = MONEY). Each variable has a fixed number of possible values. The constraints relate the values of the variables to each other. The task is to find values for the variables that satisfy the given constraints.

In general search problems one can't necessarily determine in advance how many variables will be involved. For example, in the wolf-goat-cabbage problem, there are an unknown number of states. Each state consists of a separate variable for each of the farmer, the wolf, the goat, and the cabbage.

(Since there are really only a finite number of possible configurations, one can put an upper bound in advance on the number of states. But for the sake of this discussion, let's presume that we are dealing with a problem for which that isn't the case or for which the upper bound is so large as to make that limit unusable in practice.)

This sort of problem may be approached through iterative deepening to make it a constraint problem. At each iteration, one fixes the number of states and then asks if the problem can be solved with that number of states. If not, one tries a larger number of states. By doing this one converts a problem with an unknown number of variables (and hence a problem to which one can't apply constraint programming) to a series of problems each of which has a finite and known number of variables and hence is appropriate for constraint programming.

If each state has n variables, and for some iteration there are m states, the total number of variables is m * n. One then writes constraints that both relate the variables in each state to each other and the varibles in one to state to those in the successor and predecessor states.

In general search, one simply continues to expand the number of states until one finds a solution. Thus in both general search and iterative deepening, one is not guaranteed that one will ever find a solution. So one may search forever.

In finite domain constraint programming one is guaranteed that for any problem one will either find a solution or determine that there is no solution. Of course, many NP complete problems have a finite number of variables and still can't be solved (as far as w know) in a reasonable amount of time — satisfiabilty being the prototypical example. But even in thoses cases there are often subclasses for which special knowledge can conver the problem from intractable to solvable in a reasonable time.

A nice example is Sudoku. If one attempts to solve Sudoku using brute-force search, one is faced with an exponential problem in the number of open cells. Even imposing the constraints to test the validity of partial solutions doesn't help.

What matters most is using the constraints as propagators to extend a partial solution to a more complete solution. If we do that Sudoku becomes quite tractable. See the next section for some examples.

[edit] Sudoku using constrained search

[edit] Homework 6

Another chance at homework 5.

[edit] Nov 3 (Week 7)

[edit] Homework 7

[edit] Nov 11 (Week 8)

Discussion of individual work for the rest of the term. See the This Saturday, November 11 Discussion entry for a bit more.

Here are some project ideas.

Chapter 25. "Robotics" presented by Hassan and Duy Nguyen

  • Parallelize the Searcher. Convert the takeAStep() method—which is the body of the main loop—into a task. 
while (!frontier.isEmpty() && finalState == null) {
      if (verbose) System.out.println(frontier);
      takeAStep();  // <--- This part.
    }
Continue the revision so that multiple copies can run on separate computers on a network. (Farrukh)

[edit] Nov 18 (Week 9)

  • Another project: segmented domains Implement domains that can represent their possible values as collections of ranges. That is, if a domain may have any value between 1 and 999 except 499 and 501, the domain of that FDV would be [1:498, 500, 502:999]. As the system currently stands every value in a domain must be listed explicitly. This is not reasonable when we have large domains.
  • Progress reports.
  • Snehal: Minimax & alpha-beta.

[edit] Nov 25 (Thanksgiving Holiday)

No Class.

[edit] Dec 2 (Week 10)

  • Hassan and Duy: Robotics (Russell & Norvig, Chapter 25)
  • Rick: allDiff bipartite
  • Joan, Gioung, Deepak: JCHR
  • Snehal: AoP
  • Harumi: Crossing the river
  • Farrukh: Searching with threads
  • Steve: the taxman

[edit] Dec 9 (Finals Week)

Please point the Your name pointer to your course page. Before signing up, please send me an email message describing your contributions to the class and telling me what grade you think those contributions should receive and why you think so.

  Time   Name
10:00 Strom,_Richard
10:20 Your Name
10:40 Shakil,_Farrukh
11:00 Duy Nguyen
11:20 Your name
Retrieved from "http://cs.calstatela.edu/wiki/index.php/Courses/CS_460/Fall_2006"
Personal tools