[Avery.Andrews 930306]
For general information. Note the explicit swipe at control theory (probably
just cybernetics, not bp in particular)
···
--
Workshop on Computational Theories of Interaction and Agency
Philip E. Agre
Department of Communication
University of California, San Diego
La Jolla, California 92093-0503
phone: (619) 534-6328
fax: (619) 534-7315
internet: pagre@weber.ucsd.edu
About fifty researchers with a broad range of interests gathered at the
University of Chicago on February 20th and 21st 1993 for the Workshop on
Computational Theories of Interaction and Agency. This meeting brought
together the authors who submitted papers to the AI Journal special issue of
the same name that Phil Agre and Stan Rosenschein are currently editing, along
with several of their students and a few other of the usual suspects. Its
purpose was to discuss the submitted papers, both to help the authors improve
them and to assess the current situation and future prospects for research
in this area. Its format called for an hour to be spent in focused discussion
of each paper, in two tracks. The participation of graduate students was a
particularly important part of this process, and a grant from AAAI allowed
several students to attend. The workshop was also supported by Philips
Research Laboratories New York.
The general subject of the special issue is the development of principled
characterizations of agent-environment interactions, and the use of these
characterizations in explaining existing agents and designing new ones.
The idea might be illustrated through the example of classical control
theory, which models interactions between a controller and a plant in terms
of a differential equation whose properties are the subject of considerable
analysis. Such equations may not be useful for analyzing qualitatively
complex agents and environments, but a remarkable variety of computational
research has recently been focused on the broader idea of describing
and analyzing the interactions between particular categories of agents
and environments. It would be impossible to summarize the intense and
wide-ranging discussions provoked by the papers at the workshop. At the
risk of slighting the majority of authors through omission, I will report
on a small sample of representative points.
Randy Beer's paper, "A dynamical systems perspective on autonomous agents",
provides a framework, based on dynamical systems theory, for analyzing the
interactions between robots and their environments. The general idea is
that the robot and environment, understood as a point in a large-dimensional
parameter space, trace a certain complex path as they interact. Dynamical
systems theory provides a vocabulary for talking about these trajectories.
Beer focuses on a case drawn from his own work, in which a robotic insect is
programmed to walk by a genetic algorithm that adjusts the parameters on a
neural net that control its legs and sensors. Discussion focused on the power
of a dynamical systems framework to analyze broader classes of agents and
environments.
Bruce Donald's paper, "On information invariants in robots", provides a
formal analysis of the information complexity of robots' interactions with
one another and with their environment, given particular assumptions about
their sensors. For example, if one robot is supposed to follow another, the
designer is faced with a trade-off between the amount of communication between
the robots, the length of the path they follow (for example when going around
blind corners), and the power of their sensors. The formalism captures
the intuition that something is conserved as the designers shifts from one
design to another. This "something" can be measured in bit-seconds, that
is, the amount of information that is communicated among the various devices
during the performance of the task. The theory draws heavily on concepts
from robotics. Discussion focused on the ways in which the theory might be
generalized so that its concepts of information, for example, might be applied
to a wider category of tasks in which the geometric arrangement of devices is
not a central issue.
Kris Hammond, Tim Converse, and Josh Grass's paper, "The stabilization
of environments", concerns the ways in which people actively modify their
environments in order to simplify the cognitive tasks involved in living
in them. This topic is part of their larger concern with what they call
long-term activity, as opposed to the one-shot stretches of action envisioned
by classical planning systems. Designing agents for long-term activity
requires, among other things, an understanding of the long-term relationships
maintained between an agent and its customary environment, as well as an
understanding of how an architecture might organize and deploy the wide range
of knowledge necessary for such activity. Hammond, Converse, and Grass's
algorithm is based on case-based planning. They observe that a case-based
system works best when the agent tends to encounter the same situations over
and over, and this observation provides an engineering justification for the
active stabilization of the environment. They describe an architecture that
modifies its plans in response to various indications that some kind of active
stabilization might be desirable. Discussion focused on the relationship
between this kind of active stabilization and the more emergent kinds of
stability that emerge when one's activities in a given environment settle into
a routine.
Yoav Shoham and Moshe Tennenholtz's paper, "On social laws for artificial
agent societies: Off-line design", concerns the ways in which multiple agents
sharing an environment can avoid interfering with one another by sticking to
a predetermined set of "social laws" constraining their behavior. The design
of these laws faces a trade-off: the more freedom is left to the agents, the
more they can step on each other's toes. As a case study, they provide a set
of traffic laws that allow a set of agents to coexist in a rectilinear grid
through various conventions about when and where they move. They are able
to prove that these conventions do indeed prevent the agents from colliding
while simultaneously allowing close to optimal behavior. They also provide
a general framework for deriving these social laws and prove some complexity
results about the process of doing so. Discussion focused on the relationship
between Shoham and Tennenholtz's proposals and the other ways in which
multiple agents can coordinate their activities, for example through local
negotiation or centralized control.
The workshop discussed a total of twenty-five papers, of which four have been
mentioned above. It was altogether remarkable how thoroughly and usefully
the workshop participants were able to discuss the papers, given that their
backgrounds included fields as diverse as natural language processing, control
theory, planning, logic, vision and robotics, neural networks, and philosophy.
This is an excellent portent for the future of research in this area. The
special issue itself, which is expected to appear toward the end of this year,
will provide more details.