tech report announcement

[Michael C. Mozer]

PLEASE MAIL REQUESTS FOR COPIES TO:  conn_tech_report at boulder.colorado.edu

PLEASE DO NOT FORWARD TO OTHER BBOARDS.

===============================================================================

     Discovering the Structure of a Reactive Environment by Exploration

                             Michael C. Mozer
                      University of Colorado, Boulder

                             Jonathan Bachrach
                   University of Massachusetts, Amherst

                         Tech Report CU-CS-451-89
                               December 1989

     Consider a robot wandering around an unfamiliar environment, per-
     forming  actions  and sensing the resulting environmental states.
     The robot's task is to construct an internal  model  of  its  en-
     vironment, a model that will allow it to predict the consequences
     of its actions and to determine what sequences of actions to take
     to  reach  particular  goal  states.  Rivest and Schapire (1987a,
     1987b;  Schapire,  1988)  have  studied  this  problem  and  have
     designed  a symbolic algorithm to strategically explore and infer
     the structure of "finite state" environments.  The heart of  this
     algorithm is a clever representation of the environment called an
     "update graph."  We have developed a connectionist implementation
     of  the update graph using a highly-specialized network architec-
     ture.  With back propagation learning and a  trivial  exploration
     strategy -- choosing  random actions -- the connectionist network
     can outperform the Rivest and Schapire algorithm on simple  prob-
     lems.   The  network  has the additional strength that it can ac-
     comodate stochastic environments.  Perhaps the greatest virtue of
     the connectionist approach is that it suggests generalizations of
     the update graph representation that do not arise from  a  tradi-
     tional, symbolic perspective.

     This report also serves to  set  up  the  ultimate  connectionist
     light bulb joke, which goes something like this:

          How many connectionist networks does it  take  to  change  a
          light bulb?

          Only one, but it requires about 6,000 trials.