![[Dan Fu's Abstracts]](logos/abstracts.jpg)
Ph.D. Dissertation, Dept. of Computer Science, Univ. of Chicago, December 1997.
[Postscript (2.3MB)]
The everyday world is full of unknowns. Most of these are neither frightening nor sublime; rather, they are so mundane that they blend seamlessly into our quotidian experience. When you go to an unfamiliar grocery store to buy milk, you might not know where the milk is. When you walk into a restaurant to eat a meal, you might not know the exact table. And when you drive into a gas station, you might not know how the pumps work, or whether you have to pay in advance. The world entails situations in which we don't know all the details.
And yet, we don't encounter much trouble in daily life; having real difficulties finding milk, locating a table, or getting gas are the exception---not the norm. One reason we can be successful in the face of unknowns is that the world has regularities that we routinely exploit. Grocery stores divide into aisles with signs labelling their contents. Restaurants have areas of prescribed activity such as the bar, cashier, and tables. Gas stations have pumps with operating instructions. The environments in these instances---grocery stores, restaurants, and gas stations---exhibit regularities that help us cope with what could be a harsh world in theory, but what is actually a supportive world in practice.
Artificial agents, performing everyday tasks, can gain tremendous leverage by using those regularities. In contrast, past theories of action and perception have often viewed any regularity use as ad hoc. But by emphasizing general approaches to tackle worst-case worlds, these theories proffer impractical results when actually confronted with structured worlds. I present an alternate view: regularity is the primary means by which we decide on courses of action in the everyday world. Two problems and aspects of our activity motivate this view. First, our knowledge is incomplete. Still, we can operate quite well in never-before-visited places. Second, we have a limited time to act. Yet, we can find a carton of milk in a store with tens of thousands of items within a matter of minutes. Artificial agents will inherit these problems. Regularities will help overcome them.
Viewing regularities as a central resource demands a new sort of computational model: an agent that uses strategies to suggest appropriate courses of action instead of reasoning from a complete world model; an agent that selectively perceives, based on its tasks, in order to run efficiently instead of trying to perceive everything at once; and an agent that learns from experience to better accomplish tasks in the future instead of learning for learning's sake. The result is a model that captures the structure of everyday activity in an operational form for Shopper: a program that shops for food in a virtual grocery store.
Proceedings of the 13th National Conference on Artificial Intelligence. pp. 902-908. 1996.
[Postscript (500k)] [Compressed Postscript (130k)]
This is an abridged version of technical report TR-96-03.
Past work in navigation has worked toward the goal of producing an accurate map of the environment. While no one can deny the usefulness of such a map, the ideal of producing a complete map becomes unrealistic when an agent is faced with performing real tasks. And yet an agent accomplishing recurring tasks should navigate more efficiently as time goes by. We present a system which integrates navigation, planning, and vision. In this view, navigation supports the needs of a larger system as opposed to being a task in its own right. Whereas previous approaches assume an unknown and unstructured environment, we assume a structured environment whose organization is known, but whose specifics are unknown. The system is endowed with a wide range of visual capabilities as well as search plans for informed exploration of a simulated store constructed from real visual data. We demonstrate the agent finding items while mapping the world. In repeatedly retrieving items, the agent's performance improves as the learned map becomes more useful.
Proceedings of the 14th International Joint Conference on Artificial Intelligence. pp 464-469. 1995.
[Postscript (700k)] [Compressed Postscript (300k)]
We discuss the types of functional knowledge about an environment an
agent can use in order to act effectively. We demonstrate (1) the use
of structural regularities for acting efficiently, and (2) the use of
physical regularities for designing effective sensors. These ideas
are described in the context of an everyday task: grocery store
shopping. We discuss how Shopper, a program, uses regularities of
grocery stores in order to act appropriately and sense efficiently in
GroceryWorld, a simulated grocery store.
A Quicktime movie demo (6
MB) of this paper is available. The video shows Shopper
finding a box of Special K cereal, and then later returning to
find a box of Nut & Honey nearby.
Proceedings of the Workshop on Visual Behaviors. IEEE Press. 1994.
[Compressed Postscript (285k)]
People are often able to act efficiently in places like grocery stores, libraries, and other man-made domains even if they haven't been to those particular places before: They are exercising useful knowledge about how these environments are organized in order to facilitate their tasks. In this paper we show that everyday environments exhibit useful regularities an autonomous agent can use in order to accomplish tasks efficiently. In particular, we identify useful regularities of grocery stores, and show how they're used in the design of an agent. We discuss how our planning system, Shopper, uses these regularities to find items in GroceryWorld, a simulated grocery store.
University of Chicago Computer Science Department Technical Report TR-96-03. 1996.
[HTML] [ Postscript (600k)] [ Compressed Postscript (200k)] [Adobe Acrobat (123k)]
We present an implemented system which integrates elements of run-time planning, context-based vision, passive mapping, path planning, and route following. We consider navigation as a part of a larger system which accomplishes realistic everyday tasks in addition to map learning and path planning. Whereas previous approaches assume an unknown and unstructured environment, we assume a structured environment whose organization is known, but whose specifics are unknown.
We base the system's navigation on a passive mapper which monitors sensor and actuator events to create a topological map. This map consists of distinctive places and connecting edges. At each place the agent stores relevant perceptual information important for accomplishing tasks and/or disambiguating places. The agent uses the map to select a destination and plan a route to follow. A route follower verifies location predictions by matching past perception with current perception.
The agent is endowed with a wide range of visual capabilities as well as search plans for informed exploration of a simulated store constructed from real visual data. We demonstrate the agent finding items while mapping the world. In repeatedly retrieving items, the agent's performance improves as the learned map becomes more useful to its recurring goals.
University of Chicago Computer Science Department Technical Report TR-96-06. 1996.
Also appears in Applied Cognitive Psychology, Vol. 10, S73-S83, 1996.
[ Postscript (400k)]
Researchers who build autonomous agents are primarily interested in integrating the aspects of agency which were once thought decomposable and independent. A theory of agency for everyday worlds must address the problems that an agent has a limited time to plan, and that an agent must be able to cope with an incomplete domain physics. The Case-based Agency projects at the AI Lab at the University of Chicago demonstrate how reasoning from memory provides a complete framework for a theory of agency. The three projects described in this paper revolve around a single point. Plans in memory are the most valuable resource for responsive and adaptive activity in everyday worlds. Case-based reasoning provides an approach which answers the fundamental problems of a theory of agency. This paper discusses three techniques for effective leveraging of plans in memory for use in everyday worlds: stabilization, learning from failure, and regularity-seeking perception.
