2:00, Friday April 15, WeH 7220


		 Instance-Based State Identification

		  Andrew McCallum (U. of Rochester)


In this talk we will discuss the application of reinforcement learning
to agents that cannot perceive their whole environment at once.  When
the agent's next course of action depends on information that is
hidden from the sensors because of problems such as occlusion,
restricted range, bounded field of view and limited attention, we say
the agent suffers from the Hidden State Problem.

State identification techniques use history information to uncover
hidden state.  Approaches to encoding history include: finite state
machines [Chrisman 92; McCallum 92], recurrent neural networks [Lin
and Mitchell 92] and genetic programming with indexed memory [Teller
93].

I will present a new approach to state identification using
instance-based (also called "memory-based") learning.  The first
implementation of this approach, called "The Nearest Neighbor Memory
Algorithm", is simplistic, but it nonetheless learns with an order of
magnitude fewer steps than several previous approaches.

We will also discuss the intertwined relationship between visual
routines and hidden state, and will apply Nearest Neighbor Memory to
learning visual routines.  I will end by showing video tape of both
machine agents and humans performing visual routines during an
``off-road car chasing'' task.



Some Relevant References:

author	= "Long-Ji Lin and Tom M. Mitchell",
title	= "Reinforcement Learning With Hidden States",
booktitle = "Proceedings of the Second International Conference on
Simulation of Adaptive Behavior: From Animals to Animats",
year	= "1992"

author	= "Lonnie Chrisman",
title	= "Reinforcement Learning with Perceptual Aliasing:  The
Perceptual Distinctions Approach",
booktitle = "AAAI-92",
year	= 1992

author	= "R. Andrew McCallum",
title	= "Overcoming Incomplete Perception with Utile Distinction Memory", 
booktitle = "Tenth International Machine Learning Conference", 
year	= 1993

author	= "Shimon Ullman",
title	= "Visual Routines",
journal	= "Cognition",
volume	= "18",
pages	= "97-159",
year	= "1984",
note	= "(Also in: Visual Cognition, S. Pinker ed., 1985)"

author	= "Philip E. Agre and David Chapman",
title	= "Pengi: an implementation of a theory of activity",
booktitle = "AAAI",
year	= 1987,
pages	= "268-272"

author 	= "Steven D. Whitehead and Dana H. Ballard",
title	= "Learning to Perceive and Act by Trial and Error",
journal	= "Machine Learning",
volume	= "7",
number	= "1",
year	= "1991"

author = 	"R. Andrew McCallum",
title = 	"Learning with Incomplete Selective Perception",
institution = 	"University of Rochester, Department of Computer Science",
number = 	"453",
note =		"PhD thesis proposal",
month =		"March",
year = 		"1993"
ftp =		"cs.rochester.edu:pub/papers/robotics/"