Colloquiums in SPRING 97

---

By - Tom Mitchell

Yes. The past decade has seen rapid progress on understanding how to make machines learn. In ten years we have gone from algorithms that were laboratory curiosities to robust methods with significant commercial value. Machine Learning algorithms now learn to control vehicles to drive autonomously on public highways at 70 mph, learn to detect credit card fraud by mining data on past transactions, and learn your reading interests in order to assemble a personally customized electronic newspaper. At the same time, new theoretical results shed light on fundamental issues such as the tradeoff among the number of training examples available, the number of hypotheses considered, and the likely accuracy of the learned hypothesis. And work on integrated learning architectures is beginning to explore issues such as long-term learning of new representations, cummulative learning, and learning to learn.

Where is all this headed? This talk will examine recent progress and open questions in machine learning, suggest some Ph.D.thesis topics that we should begin on now, and give one person's view on where machine learning might be headed over the next decade.

By - Gary T. Leavens

Theoretical (or toy) programming languages can be seen as scientific experiments that test theories of language design. Our theory is that languages with multimethods (generic functions), such as CLOS, Dylan, and Cecil, can easily express whatever ADT languages (such as Ada 83, Modula-2, and CLU) and single-dispatching Object-Oriented (OO) languages (such as Smalltalk, C++, Java, etc.) can express. Experiments that go some way towards demonstrating this theory will be presented in the form of versions of a toy language, BeCecil. The largest version of BeCecil has the following features:

• generic functions and multimethods
• extensible static inheritance and subtyping
• separation of types and implementations
• information hiding
• fully-nested block structure
• a safe, static type system

In this talk I will explain how to view toy languages as experiments, and demonstrate this using BeCecil. I will also explain how we handle the problem of information hiding, and our ideas for allowing separate type checking of independently-developed pieces of code. These two problems are important for multimethods.

This is joint work with Craig Chambers of the U. of Washington

By - Sree Nilakanta

Theory defines decision making to comprise intelligence, design, and choice phases. Information systems researchers have studied all three phases and have identified the critical role information technology serves in each area. Even though the impact of IT on each of the three phases have been examined from the context of the decision making entity (ranging from the individual to the organization), a very important facet of information has often been ignored. The extent to which the decision making entity relies upon this process is often predicated by the entity's belief of its experiences. Organizations and its members store past experiences as memories (internally or externally) and often rely upon these to formulate their strategies. Enabling the capture of these memories in appropriate "bins" and processing these to yield insights or directions for future actions is deemed beneficial. I will present a discussion on the development of the basic structure of such a system and propose that the system may be used in a number of organizational decision making contexts.

By - Steven M. LaValle

Algorithms for collision-free path planning have become quite valuable in a variety of applications such as robotics, virtual prototyping, and computer graphics. However, many practical problems involve additional complications such as sensing and model uncertainties, velocity constraints, multiple agents and goals, optimality criteria, and unpredictability. To deal with this broader class of problems, I have proposed a unified, game-theoretic mathematical foundation upon which new analysis techniques and algorithms for many planning problems have been developed in my research over the past several years.

Following a general overview, my talk will focus on two such planning problems, which both involve accomplishing visibility-based tasks in an environment characterized by geometric constraints. The recent study of these problems is motivated by our experimentation with mobile robots that behave as "autonomous observers," which can be used in applications such as tracking people or other robots to supply information for distributed virtual environments, monitoring processes in an assembly workcell, automatically moving cameras to avoid obstructions in a medical surgery site, or searching for potentially-hostile targets for surveillance. The first problem involves coordinating the motions of one or more pursuers that have omni-directional vision sensors to eventually ``see'' an evader that is unpredictable, has unknown initial position, and is capable of moving arbitrarily fast. The second problem involves computing motion strategies that attempt to maintain visibility of a moving target that may or may not be predictable, while optimizing additional criteria, such as the total distance traveled. Several computed results and mobile robot experiments will be presented.

By - Sven Koenig

In the not too distant future, delivery robots will distribute parcels in office buildings and exploratory robots will roam the surface of other planets. Such situated agents must exhibit goal-directed behavior in real-time, even if they have only incomplete knowledge of their environment, imperfect abilities to manipulate it, and limited or noisy perception. In this talk, I will discuss methods for building intelligent agents that explicitly deal with these problems and are able to act in a goal-directed way despite incomplete information.

The talk will present three main thrusts of my research: how to act in the presence of uncertainty that arises during execution, how to act in the presence of deadlines or in high risk situations, and how to act if the agent's initial state is not completely known. To address the problem of acting in the presence of uncertainty, I will introduce a complete agent architecture built around Partially Observable Markov Decision Process models and demonstrate that this architecture allows agents to act, plan, and learn despite the uncertainty that results from actuator and sensor noise and missing information about their environment. I will show how to combine planning methods from Artificial Intelligence with non-linear utility functions to plan efficiently either for immediate soft deadlines or in high stake domains. Finally, I will explain how to use agent-centered search methods to search non-deterministic domains efficiently by interleaving acting and planning.

Throughout the talk, I will use navigation problems faced by office delivery robots to illustrate the algorithms, and will present formal analyses, experimental results, and a real-world implementation on an autonomous mobile robot controlled over the World Wide Web.

Note: Refreshments will be served at 3:30 pm in Rm. 213 Atanasoff

By - Alan Selman

This talk describes the results of joint research with Jin-Yi Cai.

Levin formulated the notion of "average-polynomial-time" in order to study problems that have fast-on-average algorithms even though they might not have algorithms that are fast in the worst case. We extend Levin's theory of average-polynomial-time to arbitrary time-bounds in accordance with the following general principles:

• It essentially agrees with Levin's notion when applied to polynomial time-bounds.
• If a language L belongs to DTIME(T(n)), for some time-bound T(n), then every distributional problem (L,mu) is T on the mu-average.
• If L does not belong to DTIME(T(n)) almost everywhere, then no distributional problem (L,mu) is T on the mu-average.

We present a hierarchy theorem for average-case complexity, for arbitrary time-bounds, that is as tight as the well-known Hartmanis-Stearns (J. Hartmanis and R. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117:285--306, 1965) hierarchy theorem for deterministic complexity. As a consequence, for every time-bound T(n), there are distributional problems (L,mu) that can be solved using only a slight increase in time but that cannot be solved on the mu-average in time T(n).