CSCE 580 Presentations

Graduate student presentations:

1. Jeremiah J. Shepherd: Path-Finding with Motion Constraints Among Obstacles in Real-Time Strategies (September 14, 2009).

2. John G. Flowers and Andrew M. Smith: Iterative Deepening A* and Other Limited-Memory Heuristic Search Algorithm (October 12, 2009). You will present IDA* as originally proposed in: Richard Korf, "Depth-First Iterative Deepening: An Optimal Admissible Tree Search." Artificial Intelligence, 27 (1985), 97-108. You will present the criticism of IDA* by Russell and some the algorithms that try to improve on it in several ways: Stuart Russell, "Efficient Memory-Bounded Search Methods." In Proceedings of the Tenth European Conference on Artificial Intelligence, Vienna: Wiley, 1992. You will also review one more algorithm from the recent literature.

3. Brad Dunbar and Shamik Roy Chowdhury: "Resolution versus Search: Two Strategies for SAT." (December 4, 2009). Backtracking Search Vs. Variable Elimination for Propositional Satisfiability
You will contrast backtracking search vs. variable elimination for propositional satisfiability You will present two algorithms for propositional satisfiability, one due to Davis and Putnam (Davis, M. and Putnam, H. (1960). "A computing procedure for quantification theory." Journal of the ACM, 7(3): 201--215.) and one due to Davis, Logemann, and Loveland (Davis, M., Logemann, G., and Loveland, D. (1962). "A machine program for theorem proving." Communications of the ACM, 5(7): 394--397) and contrast them as done by Rish and Dechter (Irina Rish and Rina Dechter. "Resolution versus Search: Two Strategies for SAT." Journal of Automated Reasoning, 24, 215--259, 2000.)

4. A Prolog-Technology Theorem Prover.
You will present the sound and complete theorem prover outlined in the following key reference: Donald W. Loveland and Mark E. Stickel. "A Hole in Goal Trees: Some Guidance from Resolution Theory." IEEE Transactions on Computers, vol. C-25, No.4, pp.335-341, April 1976.

5. Hal Lindsey: Consistency-Based Diagnosis (December 14, 2009).
You will present the basic formalism of consistency-based diagnosis, one of the most successful examples of logical representation and model-based reasoning. The key reference is: Raymond Reiter, "A Theory of Diagnosis from First Principles." Artificial Intelligence, 32, 1, pp.57-96, 1987.

6. Abductive Diagnosis.
You will present the basic formalism of abductive diagnosis, one of the the most successful examples of logical knowledge representation and model-based reasoning. The key reference is: David Poole. "Normality and Faults in Logic-Based Diagnosis." Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI-91), Sydney, Australia, pp. 1129-1135, August 1991.