[SARA 2000]
SARA 2000 Home
Invited Speakers
Schedule & slides
Related Meetings
Final Call For Papers
Important Dates
In addition to the three invited talks, we are delighted to announce the following tutorial:

From Reality to Databases: a One-to-Many Relationship

Stefano Spaccapietra
Swiss Federal Institute of Technology in Lausanne (EPFL)
CH-1015 Lausanne, Swizerland

This tutorial focuses on data modeling abstractions that are needed for an accurate conceptual design of traditional (alphanumeric) databases as well as spatio-temporal databases. We first recall the basic steps and concepts in a conceptual design approach. This leads to schemas that describe the real world data in terms of complex objects and relationships, properties and is-a links. Next we further investigate issues related to supporting multiple representations for the same real world entity. We show limitations in this respect of current object-oriented data modeling approaches and propose solutions to overcome such limitations.

Distinguised Invited Speakers

July 27, 2000:  Professor Thomas Dietterich (AAAI Fellow),  Oregon State University.
July 28, 2000:  Professor Patrick Cousot, École Normale Supérieure, Paris.
July 29, 2000:  Professor Richard Korf (AAAI Fellow), University of California, Los Angeles.

An Overview of MAXQ Hierarchical Reinforcement Learning

Thomas G. Dietterich
Oregon State University, Corvallis, Oregon, USA

Reinforcement learning addresses the problem of learning optimal policies for sequential decision-making problems involving stochastic operators and numerical reward functions rather than the more traditional deterministic operators and logical goal predicates. In many ways, reinforcement learning research is recapitulating the development of classical research in planning and problem solving. After studying the problem of solving ``flat'' problem spaces, researchers have recently turned their attention to hierarchical methods that incorporate subroutines and state abstractions. This paper gives an overview of the MAXQ value function decomposition and its support for state abstraction and action abstraction.

Partial Completeness of Abstract Fixpoint Checking

Patrick Cousot
Département d'informatique, École normale supérieure, 45 rue d'Ulm
75230 Paris CEDEX 05, France

Abstract interpretation is used in program static analysis and model checking to cope with infinite state spaces and/or with computer resource limitations. One common problem is to check abstract fixpoints for specifications. The abstraction is partially complete when the checking algorithm is exact in that, if the algorithm ever terminates, its answer is always affirmative for correct specifications. We characterize partially complete abstractions for various abstract fixpoint checking algorithms, including new ones, and show that the computation of complete abstract domains is essentially equivalent to invariance proofs that is to concrete fixpoint checking.

Recent Progress in the Design and Analysisof Admissible Heuristic Functions

Richard E. Korf
Computer Science Department, University of California, Los Angeles
Los Angeles, CA 90095

In the past several years, significant progress has been made in finding optimal solutions to combinatorial problems. In particular, random instances of both Rubik's Cube, with over $10^{19}$ states, and the 5x5 sliding-tile puzzle, with almost $10^{25}$ states, have been solved optimally. This progress is not the result of better search algorithms, but more effective heuristic evaluation functions. In addition, we have learned how to accurately predict the running time of admissible heuristic search algorithms, as a function of the solution depth and the heuristic evaluation function. One corollary of this analysis is that an admissible heuristic function reduces the effective depth of search, rather than the effective branching factor.

Copyright © 2000, American Association of Artificial Intelligence (www.aaai.org). All rights reserved.

Mailing List: To be added or removed from the SARA mailing list, please send an email message to <holte@cs.ualberta.ca> with the following body: un/subscribe sara your-email-address.

Last Modified: Thursday, 29 Jun 2000 15:30 CDT
Berthe Y. Choueiry <choueiry@cse.unl.edu>