Internet Softbots
(Etzioni, Weld)
AI research is moving away from "toy tasks, such as block-stacking, towards more realistic problems. Building autonomous agents that interact with real-world software environments, such as operating systems or databases, is a pragmatically convenient, yet intellectually challenging, substrate for AI research. To support this claim, we are utilizing planning and machine-learning technology to develop an Internet softbot (software robot), a customizable and (moderately) intelligent assistant for Internet access. The softbot accepts goals in a high-level language, generates and executes plans to achieve these goals, and learns from its experience. Custom-built execution and sensing modules enable the softbot to interact with the UNIX shell in real time. We are developing both a graphical user interface and a natural-language interface to the softbot.

MetaCrawler
(Etzioni)
The MetaCrawler is a Web service that provides a single, central interface for Web document searching. Upon receiving a query, the MetaCrawler posts the query to multiple search engines in parallel, and performs sophisticated pruning on the responses returned. Preliminary experiments indicate that the MetaCrawler is able to prune as much as 60\% of the returned responses as irrelevant, outdated, or unavailable. Current research focuses on improving the speed and filtering ability of the MetaCrawler, as well as integrating it with the Internet Softbot.

Local Closed-World Reasoning
(Etzioni, A. Levy, Weld)
In many cases, an agent does not have complete information about its world. For instance, a software agent, such as the Internet softbot, cannot be familiar with the contents of all the bulletin boards, FTP sites, and files accessible through the Internet. This renders the classical AI assumption of a "Closed World" unacceptable. We are developing algorithms to synthesize courses of activity in domains, such as the Internet, that have unbounded incompleteness. Our algorithm supports universally quantified goals, such as "Print all of Etzioni's postscript files in the ~/kr directory", by spawning sensory actions when necessary. Previous approaches to this problem suffer from redundant information gathering, because they plan to "sense" information that is already known to the agent. Our algorithm attempt to avoid this pitfall; the key technological advance underlying our planner is a tractable approximation algorithm for dynamic circumscription.

Probabilistic Planning
(Hanks, Weld)
Classical planning assumes complete and deterministic information about the world state and about the effects of the agent's actions. These assumptions are inappropriate for many domains: turning the ignition key might usually start one's old car, but occasionally it will fail to do so for unknown reasons. Even if a deterministic model is possible for a given domain, it might be too complex to be useful. The world's state at execution time is also a critical source of uncertainty: a trip's success might depend on light traffic, but the agent can't precisely predict traffic levels when it must commit to a course of action. This project is exploring a planning algorithm that relaxes the certainty assumptions traditionally made by AI planners. We use a probability distribution over world states to model uncertainty about the world's state at execution time, and represent actions using a mixed symbolic and probabilistic model of the changes they make to the world. The classical planning notion of a plan that provably achieves its goal is replaced by a plan that succeeds with high probability, as defined by a user-specified threshold. Our algorithm is sound and complete: any plan it generates is sufficiently likely to succeed, and it is guaranteed to produce a high-probability plan if one exists.

We are currently working on various approaches to render the probabilistic planning process tractable for large domains. We are also extending the algorithm to handle \_partially observable\_ domains, those in which the agent's sensors can provide it with some information about the state of the world at plan-execution time. That information will typically be incomplete, however, and might be incorrect as well, as sensors can be noisy or otherwise faulty. Partial observability requires us to generate plans with conditionals and looping constructs.

Decision-Theoretic Planning
(Hanks)
We are exploring various ways in which an agent can act rationally (do good things) and effectively (do them in a timely manner). Our approach is to combine the model of rational choice provided by decision theory with symbolic AI algorithms for generating plans. Topics include: probabilistic planning (extending AI (symbolic) planning algorithms to handle probabilistic models of state and action); planning with rich utility models (generate plans for goals that have deadlines, taking into account that satisfying a goal partially is better than not satisfying it all, and accounting for costs associated with resources consumed in the process of achieving goals); and coordinating strategic and tactical behaviors (deciding when an agent should plan and when it must act, as well as deciding when the world has changed enough so that it should reconsider its current commitments). We are also interested in unifying various algorithm approaches to decision-theoretic planning, drawing on work in Markov Decision Processes, Stochastic Optimization, and Decision Analysis.

We are developing a flexible and adaptive architecture for coordinating algorithms for strategic planning (deliberation) with algorithms for tactical behavior (execution). Our two basic premises are (1) that deliberation and execution proceed simultaneously and asynchronously, and (2) the strategic planner must be able to reason about and influence the behavior of the system's tactical component. We are applying the framework to a variety of problems involving both autonomous agents and decision-support systems.

Multi-modal Input Output
(Holden)
This project is sponsored by the Human Interface Technology Lab, Washington Technology Center. It follows a successful project, where speech recognition and natural language analysis allowed a dialog between the user and an agent in a restricted domain. Graphical and speech output showed the response of the agent. Now, speech recognition, natural language interpretation and vision processing are being used to allow I/O with speech, detection of eye movements and hand gestures. Coordination between modes is done using a "blackboard" data structure, with rules and objects and considerable domain knowledge. The NLP part is guided mainly by semantics, with syntax taking a small part.

The Airplane Mechanic's Assistant
(Holden)
This project is sponsored by the HIT lab and Alaska Airlines. The objective is to take the notes jotted by pilots and mechanics about faults and their fixes, and to create a data base which will be used to get quick information. Also, a knowledge based system will give advice to the mechanic. The research problems are:
(1) Creation of an extensive and efficient dictionary of the words used in this restricted domain (Each word will have a large associated semantic data-base, with rules guiding the search for the most likely modifiers,etc. A bottom-up, semantically and probabilistically controlled method will be used)
(2) Dealing with misspellings and ambiguities. The former are frequent while the latter are manageable in this kind of data. The specific context is known (each entry has a subsystem number) and this greatly reduces the total problem.
(3) Diagnostic advice can be readily given using a decision tree based on maintenance manuals. Since the sub-sub...system involved is known, there is an opportunity to give very specific advice.
(4) Real time advice would be needed if a mechanic were to use the system during maintenance. We expect that next year we will have a demo system, using the "retinal display" developed by WTC, that will allow a mechanic freedom of movement while accessing the sub system being examined.

Sensory Graphplan
( Weld, Smith (NASA))
If an agent does not have complete information about the world-state, it must reason about alternative possible states of the world and consider whether any of its actions can reduce the uncertainty. Agents controlled by a contingent planner seek to generate a robust plan, that accounts for and handles all eventualities, in advance of execution. Thus a contingent plan may include sensing actions which gather information that is later used to select between different plan branches. Sensory Graphplan (SGP) improves upon previous systems in several ways. SGP uses an action model with clear semantics. SGP is complete. And SGP is substantially faster than previous contingent planners.

Programming by Demonstration
( Weld)
Most users are unable to customize their applications to their tasks. Applications that do support customization provide it either as preferences and configuration options, or less frequently as a powerful end-user programming language. In any case, the degree of customizability is inversely proportional to the number of users who can benefit. Programming by demonstration (PBD) is a way of allowing users to generate customization programs, simply by performing actions in the user interface that they are accustomed to. In contrast to macro recording facilities, PBD systems generate programs with loops and conditionals. Our work generalizes previous heursitic approaches with a foundation based on inductive logic programming.