PSU CS 443/543: Combinatorial Search Spring 2010
Instructor: Bart Massey
Time: Monday and Wednesday 1640-1830
Place: Cramer Hall (CH) 69
CRN: 64276 (443), 64277 (543)
(This is a tentative syllabus, and will change frequently and without notice throughout the course.)
Combinatorial search, also known as state-space search, is a way of solving apparently intractable problems by considering a large number of possible solutions in a plausible order.
This course teaches how to perform a state-space search, and how to apply state-space search to real-world problems.
Week 1: Introduction to Search
- Monday, 29 March: Course mechanics, goals; What is state space search?
- Wednesday, 31 March: Problem statements; Basic search techniques
- Reading: [intro], [np1]
Week 2: Constraint Satisfaction Problems
- Monday, 5 April: Intro to CSPs
- Wednesday, 7 April: Simple complete search for CSPs
- Reading: [cl]
- Homework 1: TotallyNuts
Week 3: Complete Search Techniques
Week 4: Complete Search Techniques
- Monday, 19 April: A sample problem
- Wednesday, 21 April: More on the sample problem
- Reading: [mcfl]
Week 5: Local Search Techniques
- Monday, 26 April: Introduction to local search
- Wednesday, 28 April: Hybrid search
- Reading: [swo]
- Project: See above
Week 6: Computation
(Note, instructor will be travelling—guest lectures)
- Monday, 3 May:
NP Completeness (Prof. Suresh Singh)
- Wednesday, 5 May: Search and SE: The Case for Haskell (Jules Kongslie)
Week 7: Scheduling
- Monday, 10 May: The scheduling problem
- Wednesday, 12 May: Search-based scheduling methods
- Reading: [rcps]
Week 8: Pathfinding Search
- Monday, 17 May: Exploring RCPS
- In Class: RCPS scheduler
- Wednesday, 19 May: Applications of pathfinding search
- Reading: [warp]
Week 9: Planning and Adversary Search
- Monday, 24 May: Planning
- Wednesday, 26 May: Adversary Search
- Reading: [hsp]
Week 10: Conclusions and Frontiers
- Monday, 31 May: Memorial Day: No Class
- Wednesday, 2 June: Review and discussion
This webpage is http://wiki.cs.pdx.edu/cs543 . The course discussion email list is mailto: firstname.lastname@example.org . You are required to sign up for the email list at http://svcs.cs.pdx.edu/mailman/listinfo/cs543-spring2010 , as crucial information may be posted there and you are expected to be able to receive it.
Documentation is available for the important algorithms used in the course. Please feel free to correct and update it as needed.
- [intro] Matt Ginsberg, Essentials of Artificial Intelligence, Chapters 2-3. [PDF]
- [np1] Michael Garey and David Johnson, Computers and Intractability, Chapter 2. [PDF]
- [cl] Peter Brucker, Scheduling Algorithms (2nd ed.), Chapter 3 Section 4. [PDF]
- [mcfl] Steven Minton, Mark D. Johnston, Andrew B. Philips and Philip Laird, Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems. [PDF]
- [rsat] Robert Bayardo and Robert Schrag, Using CSP Look-Back Techniques to Solve Real-World SAT Instances. [PDF]
- [swo] David Joslin and David Clements, Squeaky Wheel Optimization. [PDF]
- [rcps] James Crawford, An Approach To Resource-Constrained Project Scheduling. [PDF]
- [warp] Charles McVey, David Clements, Bart Massey and Andrew Parkes, Worldwide Aeronautical Route Planner. [PDF]
- [hsp] Blai Bonet and Héctor Geffner, Planning as heuristic search. [PDF]
- Past offerings
- AI Groups
Papers and Books
- Foundations of Constraint Satisfaction -- The complete book by Edward Tsang
- Limited Discrepancy Search -- Harvey and Ginsberg's paper
- Constraint Programming Tutorial -- By Roman Bartak
- Modular Lazy Search for Constraint Satisfaction Problems -- Thomas Nordin and Andrew Tolmach (PSU CS Professor Tolmach)
- The Small-World Phenomenon: An Algorithmic Perspective -- Jon Kleinberg
- CMU Lectures on Search
About the Course
The catalog says: "Explores methods for the solution of constraint satisfaction and related problems using search techniques, in the context of real-world problems such as resource-bounded scheduling, enterprise planning, classical planning, and one- and two-player games. Emphasis is on coding projects, and on reading and reporting on selected literature."
Instruction is through a series of lectures, readings, and web-based materials. Homework will consist of a sequence of programming projects, culminating in a substantial final project.
Prerequisites for the course are: algorithms and data structures courses; a discrete math course; and the ability to program fluently in some reasonably efficient and clear programming language such as C, C++, Curry, Java, ML, Nickle, Prolog, Scheme, Smalltalk, etc. (If you are in doubt about the appropriateness of some language for this course, please consult the instructor.)
- Articulate the notion of state space and the role of state spaces in computer science.
- Use the vocabulary of class, problem, instance, and solution in discussing computational theory.
- Determine whether a given decision problem is in P, in NP, and/or NP hard.
- Use understanding of combinatorial state spaces to design or select search techniques for solving instances of combinatorial problems.
- Determine whether a problem is amenable to local search, complete search, or hybrid techniques.
- Select knowledgeably from a wide variety of combinatorial search techniques.
- Use boolean constraint satisfaction (SAT) instances as a theoretical tool for analysis and as an intermediate form for applying existing SAT solvers to NP-hard problems.
- Implement combinatorial search algorithms efficiently and cleanly in a reasonable programming language.
- Cite relevant combinatorial search literature.
Coursework is of several kinds.
- A gradated series of homework projects applying combinatorial search to interesting problems.
- A final larger course project.
- Course grades will be at the discretion of the instructor, who will consider attendance, participation, and attitude.
The course project will involve designing, implementing and evaluating a combinatorial search application. Wide latitude is given in selection of projects: a "standard" project will be provided for those who choose not to select their own.
The homework consists mainly of programming assignments. The programming can be done in any reasonably clear and efficient programming language: many students choose C, C++, or Java, but Nickle, ML, Scheme, Prolog, Sma lltalk, or the like may be a better choice in many ways. For unusual languages (i.e. those not installed by default in the Linux Laboratory) please contact me in advance for approval and so that I can get set up to run programs.
In general, I will ask that programs read from standard input and write to standard output, and that the programs require no options or other configuration. Please take these requirements, and all of the requirements in each assignment, seriously.
A homework submission should include
- All source code for the program.
- Any instructions needed to successfully build and run the program (including a Makefile if at all appropriate) on a box in the Linux Laboratory.
- A writeup: see below. (All re-submissions should include all of these materials as well, even if they have not changed.)
The writeup is as important as the program. It should contain a description of the algorithms and design of the program, a discussion of the program's performance and notes on any issues of interest that arose during the homework. In general, the writeup should look like a scientific document. (There is a nice guide to technical writing at Columbia University: you may find it useful.) Plain ASCII text is the preferred format for writeups: if you must use some fancier format, HTML or PDF are acceptable. Proprietary formats (e.g. Word or Framemaker documents) are not acceptable and will be discarded unread.
The submission should be bundled into a tar or zip archive, including a README describing its components, that unpacks into the current directory. The archive should be e-mailed to mailto:email@example.com as an attachment. The subject of the e-mail should be "CS 443/543 HW #", where "#" is the homework number.
Normal Student Conduct Code, Departmental, and University guidelines apply. Every student is encouraged to work with other students and seek outside assistance in completing the course. However, it is absolutely mandatory that any assistance received (coding help, algorithmic help, ideas, writeup, references, etc.) be acknowledged explicitly and fully by the student. Failure to do so is plagiarism, the lowest form of academic conduct, and will result in a zero on the assignment: the instructor will do everything he legally and ethically can to end the academic career of a plagiarist.
If you have doubts about the propriety of some course of academic conduct, please consult the instructor: he will be happy to advise.