Invited Speakers

Fahiem Bacchus (University of Toronto)
Caching in Backtracking Search

As backtracking search explores paths in its search tree it makes various inferences about the problem. The inferences search computes can be very computationally expensive to compute statically. However, in most backtracking CSP solvers this information is discarded when the search backtracks along the current path.
In this talk we will investigate the alternative---caching these inferences and using them to improve the efficiency of the rest of the search. Caching provides radical improvements to the theoretical power of backtracking, and can also yield significant improvements in practice. Sometimes, however, obtaining improvements in practice might not be so straightforward. We will examine CSP caching techniques for the problem of finding a single solution, counting the number of solutions, and finding an optimal solution. Time permitting we will also look at caching techniques that would be useful for QCSPs.

Matt Ginsberg (On Time Systems)
Of Mousetraps and Men: A Cautionary Tale

This talk consists of two interwoven stories.  The Happy Story presents a technical solution to the problem of optimizing for cost instead of the more normal metric of duration.  We describe a mechanism whereby the  optimization problem is split into an evaluation component, where the projected cost of a schedule is evaluated usingdynamic programming techniques, and a search component, where search is conducted in "window space" to find a cost-efficient schedule.The Sad Story explains what happens when you build a better mousetrap. The people beating a path to your door are the fat cats, who are reimbursed for their mouse catching on a cost-plus basis.

Sheila McIlraith (University of Toronto)
Automated Web Service Composition: New (and not so new) challenges for AI planning