------------------------------------------------------------------------------ B O S T O N U N I V E R S I T Y Computer Science Department C O L L O Q U I U M Friday, November 8, 1996 1:30 pm (Coffee served at 1:00 pm, Room MCS 137) Room MCS 135 ------------------------------------------------------------------------------ CROSS-FERTILIZATION AMONG AI, CS THEORY, AND OPERATIONS RESEARCH WITH APPLICATIONS TO PLANNING AND SEARCH PROBLEMS Yury Smirnov Department of Computer Science Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, Pennsylvania 15213 Yury.Smirnov@cs.cmu.edu ABSTRACT By now Artificial Intelligence (AI), Theoretical Computer Science (CS theory) and Operations Research (OR) have investigated a variety of search problems. However, methods from these scientific areas use different problem descriptions, models, and tools. They also address problems with particular efficiency requirements. For example, theoretical approaches are mainly concerned with the worst-case complexity and are not focused on empirical performance. A few efforts have tried to apply methods across areas. Usually a significant amount of work is required to make different approaches ``talk the same language,'' be successfully implemented, and, finally, solve the actual same problem with an overall acceptable efficiency. In this talk we will discuss a sequence of planning and search problems relevant to the cross-fertilization approach. The methodology that we will follow consists of, first, the analysis of each group of problems along different directions to identify efficient methods of solving these problems. Second, we combine the most beneficial features found during the analysis phase utilizing the advantage of the common representation developed. Based on our work and results produced so far, concretely we propose to address the following kinds of problems: 1. Goal-directed exploration, in which search with limited look-ahead occurs in partially or completely unknown domains. A combination of Euler's BETA, DFS and popular in AI nearest neighbor algorithms produced the first (up to our best knowledge) heuristic-driven "Treasure Hunt" algorithm with linear performance guarantees. 2. Combinatorial optimization problems, focused on a comparative analysis of the Pigeonhole Principle and methods of Integer Programming. Successful applications of the Pigeonhole Principle usually require additional knowledge or representation changes. As the result, the Pigeon- hole Principle is either hardcoded or ignored in AI planning systems. Integer Programming provides an alternative way of representing and solving combinatorial optimization problems. We compare the bounding powers of both methods and illustrate the discussion by a series of problems: from the N-Queen Problem to the "Mutilated" Checkerboard and Firm Tiling Problems. HOST: Prof. David Yates ------------------------------------------------------------------------------ For colloquium info, including directions, see http://www.cs.bu.edu/colloquium For more information contact Prof. David Yates ------------------------------------------------------------------------------