Guest lecture

Date	Monday, May 19th, 1997
Place	Department of Computer Science, Teollisuuskatu 23 room A414
Time	14:15 - 16.00

---

Abstract

There has been considerable research in AI, OR and computer science on the construction and testing of search algorithms, for both decision problems and optimization problems. Because almost all these problems are NP-Complete and therefore their search time is likely to grow exponentially with problem size; systematic (or exact) algorithms are effectively limited in the size of the problem they can handle. This limitation has prompted much research on incomplete algorithms that try to find a solution if one exists, or an optimum (possibly local). If an incomplete algorithm has not produced a solution in the time available, this does not mean one does not exist.

This search research has yielded many well known general algorithms, such as simulated annealing, local search, backtrack search, etc., as well as many more specialized algorithms, such as Simplex (linear programming problems), Dijkstra's algorithm (shortest path in a graph), etc. Despite all this research, there is no consensus on what is the "best" algorithm, and algorithm construction for a particular problem class is still an art. This talk will review much of this research, and show how it might be possible to develop a general algorithm that only uses the information in the problem description and nothing else.

About the speaker

Peter Cheeseman is a senior research scientist, whose specialization is in Artificial Intelligence, and Bayesian Inference Methods. He received his B.S. degree in Physics and Mathematics with honors from Melbourn University (Australia) in 1971, his M.Phil. in Applied Mathematics from Waikato University (New Zealand) in 1973, and his Ph.D. degree in Artificial Intelligence from Monash University (Australia) in 1979. Dr. Cheeseman was a lecturer in Computer Science at the University of Technology, Sydney, Australia from 1978 to 1981. From 1981 to 1985, Peter performed research at SRI International in the areas of production planning, probabilistic methods for combining information, induction of probabilistic rules from data, development of a representation and procedure for spatial uncertainty estimation, and development of an information theoretic version of Bayesian estimation and its applications.

In 1985 Peter began research at NASA Ames Research Center in the Artificial Intelligence Research Branch. He now manages a research group who apply Bayesian inference methods to data analysis problems. This research has concentrated on the development of a practical general purpose automatic classification system. In addition, research into probabilistic methods for solving combinatorial search problems has yielded new insights on when problems are hard and how to solve them. A newer project involves combining information from multiple images of planetary surfaces to form a surface model at higher resolution that any particular image Dr. Cheeseman is the Co-Founder of the Annual Uncertainty in Artificial Intelligence Conference and served as the Program Chair for the Artificial Intelligence and Statistics Conference.