Emergent Frame Recognition and Its Use in Artificial Creatures
Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Robotics. Pages 1219-1223.
© 1991 International Joint Conferences on Artificial Intelligence
Abstract
Artificial creatures are autonomous mobile agents that have to react in real-time to sensors and plan and perform actions in the real world Current effective architectures for artificial creatures are behavior-based and use variants of the subsumption architecture. The paper proposes an extension to these architectures in terms of a layer which introduces cognitive capabilities to artificial creatures. This · extension is frame-based and uses emergent frame recognition to determine which frame should become active.
- [Braitenberg, 1984] Braitenberg, V. Vehicles: Experiments in Synthetic Psychology. MIT Press, Cambridge, Mas- saschusetts, 1984.
- [Brooks, 1986] Brooks, R. A robust layered control system for a mobile robot. IEEE Journal of Robotics and Automa- tion. RA-2(1):14-23, 1986.
- Brooks, 1990} Brooks, R. (1990) The Behavior Language. MIT AI Lab. Memo.
- Fahlman, 1981} Fahlman, S. NEI'L: A system for representing and using real-world knowledge. MIT Press, Cambridge, Massaschusetts, 1981.
- [Hillis, 1985] Hillis, D. The Connection Machine. MIT Press, Cambridge, Massaschusetts, 1985.
- [Minsky, 1987] Minsky, M. The society of mind. Basic books. New York, 1987.
- [Schank and Riesbeck, 1981] Schank, R. and C. Riesbeck (1981) Inside computer understanding: Five programs plus miniatures. Lawrence Erlbaum Ass. Hillsdale, New Jersey, 1981.
- [Steels, 1990] Steels, L. (1990) Towards a theory of emer- gent functionality. In B. Meyer and S. Wilson (1990) Simulation of Adaptive Behavior. MIT Press, Cambridge, Massaschusetts, 1984.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. Introduction
The construction of artificial creatures has been put for ward recently, particularly by Brooks, as a new goal for AI. An artificial creature is an autonomous agent that is operating in the real world It gets information about the environment through sensors, and not through symbolic tokens fed by a human, and it directly executes its actions in the world. The construction of artificial creatures poses a set of challenging problems which are central to intelli gence but could be ignored in current knowledge systems research 1 . These problems include:
- The symbol grounding problem: how can symbols used by a symbolic reasoner relate to real world objects.
- The real time problem: how can signals from sen sors be interpreted in real time, how can planning be performed under extreme time constraints, and how can the resulting plans be made reactive enough to cope in real time with unexpected circumstances.
- The situatedness problem: how can behavior be defined so that it fits flexibly and dynamically with the situation being faced
- The programming problem: how can systems be built up in a modular fashion, i.e. how can new competences be added without having to revise ear-
1 1bis does not mean that knowledge systems are not useful or not intelligent.
Although the behavior-based approach gives us ways to handle the physical parts of the task, it is in itself not ade quate for the other aspects. For example, there are no elegant ways to internally represent objects with their pro perties (behavior-based systems react directly to sensors and have no notion of an "object"), there is no way to keep memory of past events and use that in action selec tion, it is not possible to classify situations into categories and decide on the basis of that what action to undertake, there are no "variables" which can be bound (filled) with arbitrary objects including objects that are not in view, therefore actions need to be represented for each possible instantiation or actions can only take place over objects or situations that are directly visible to the sensors. What seems clearly needed is an additional layer on top of a behavior-based layer that takes care of the more cognitive aspects. This layer nevertheless needs to remain grounded in the physical layers below it It also needs to satisfy a number of requirements such as real-time performance and emergence of behavior.
We are exploring a frame-based architecture [Minsky, 1987] for the cognitive layer. This means that mechanisms like frames, slots, defaults, inheritance hierarchies, pro cedural attachment, and links between frames are avail able. Frame recognition is the primary mode of operation: the frame(s) that best fit the current situation are recog nized and this triggers through procedural attachment the scheduling or the inhibition of behaviors at the behavior based layer. The choice of a frame-based architecture (as opposed to a logic-based or rule-based one) is motivated partly by the ability of frames to represent in a packaged way complete situations including the behaviors that are appropriate in the situation and the sensor/effector cou plings. The availability of slots overcomes also the lack of variables in earlier behavior-based architectures.
heuristics), and inflexibility because there needs to be a prior categorization of the set of possible situations in order to express the heuristics.
We have therefore developed a new approach towards frame recognition which is based on the principle of emer gent functionality (Steels, 1990). No mechanisms are pro grammed in to help find the frame that best matches. Instead, the most appropriate frame, i.e. the one whose slots best fit with objects found in the current situation, emerges as the winner after a dynamical process in which the different frames "fight" among themselves and interact directly with the world through behaviors and their associ ated sensors and effectors. This process has a gestalt-like quality. Also it is completely reactive in the sense that if the situation in the world changes, frame activations change dynamically with it
The frame recognition system that is proposed in the paper constitutes a contribution not only to research on artificial creatures but also to frame theory in general. The emergent frame recognition system could be used also in story understanding, for example, in order to find the best matching frame system and the best fillers of all slots within the system. In this paper we concentrate however on the application to artificial creatures.
The rest of the paper is in two parts. The first part develops the proposed frame recognition system. The second part discusses an example. Some conclusions end the paper.
2. Emergent frame recognition
2.1. Initial definitions
There is however a major unsolved problem in frame Assume a collection of frames F. Each frame f e F con theory, namely how frames are supposed to be recognized. sists of an n-tuple f = <st. ... sn>· s =<slot-name, slot Exhaustive search is clearly excluded in an artificial ·· filler-description>. A slot-filler-description is a list of pro
limited amounts of processing power and memory 3 . Assume also a collection of objects 0. Each object has a Another approach assumes that a lot of domain-dependent list of propositions describing the object. Some of these heuristics are encoded. For example, the work of Schank, propositions are causally connected to external or internal et.al. [Schank and Riesbeck. 1981] on recognizing which sensors. A proposition has a certainty c associated with. c scripts (i.e. system of frames) applies in a given story, is a real number between 1.0 and 0.0. New objects may be typtcally centers around the introduction of domain- created at all times. New propositions may be added to an specific information to make the frame recognition prob- object at all times and the certainty c of a proposition may lem tractable. This solution is not usable in the present be changed at all times, for example under influence of
3 The frame recognition problem and its solution through ex haustive search biggered the research on massively parallel comput ing in AI [Fahlman, 1979]. But although there are now massively parallel computers [Hillis, 1985] that can in principle do exhaustive search to find the best fit they are technologically too heavy for artificial creatures.
· A future version of the theory will incorporate also descrip tions with variables which would be local inside a given fr.une sys tem.
5 1n the implemenlation operational on the robot, we assume a _ fixed set of objects and a fixed set of propositions for efficiency reasons.
creature that works under heavy time constraints and has positions 4 . context because (1) it would introduce extra memory sensorsS usag~ ~d computation, and (2) it requires that the "right" heunstics ~ thought up by human designers and pro gr~ed m. There are also some other disadvantages: brittleness (when appropriate heuristics are not present the syst_e~ fails to recognize the frame), non-modularity (the addition of new behaviors requires revision of earlier Frames have two types of relations between them: special ization relations (the isa-hierarchy) and interframe rela tions. Two frames fl, f2 are connected by an isa-link if they share the same slots but f2 contains additional con straints on the fillers. For example, there is a general frame for object, with specializations for living and non living object Living objects are further subdivided into group and single individual, single individual is subdi vided into adult and child, etc. Frame recognition typically proceeds in a top-down fashion. For example, it is easier to recognize that an object is present (using the infra-red sensors) than to recognize whether that object is a child (which requires a combination of pyro-sensors, pitch detection, and prior expectation). The fact that frame recognition is typically top-down is an emergent property however, simply because frames near the top of isa hierarchies have less conditions and are therefore easier to satisfy than frames near the bottom of the hierarchy.
van Aeken is one of the chief designers of the functionality. The conbibutions of Maja Mataric and Rodney Brooks in the startup phases of the project are gratefully acknowledged. Jorge Wasser man, director of the Barcelona science museum, has been a cham pion of the project from the beginning.
Interframe relations implement inhibition and enforcement relations between frames. For example, often a frame for an emotional state will be in direct competition with frames of other emotional states. Thus the anger-frame and the happiness-frame inhibit each other, whereas the frustration-frame enforces the anger-frame. The interframe relations can also be used to implement expectations (for example a frame for an action may enforce a frame for the next action in a sequence), or weak forms of planning (a frame for an action enforces frames for actions that could make its preconditions true).
Besides a set of slots and objects filling these slots, a frame contains also a set of behaviors which take the fillers of the slots as parameters. These behaviors are identical to the behaviors found in subsumption architec tures. For example, the dance frame has an associated behavior that causes the robot to dance (while still avoid ing obstacles, etc. - the subsumption architecture remains in force at the level of behaviors).
2.2. The theory
The frame recognition system uses the metaphor of flow of energy in a network. Every frame has a particular strength, called the frame-strength. It is a real number that indicates how well the frame fits with the present situa tion. The frame strength can also be viewed as an indica tion of how much energy (strength) the frame has. The initial strength comes from a partial fit of the frame with reality (for example, some of the slots could be filled) or from possible reenforcement through interframe relations. This helps the frame to pull other objects into its slots and to compete with adversaries for the same objects. As more objects fill the slots (or better fit the slots), the frame gains progressively more strength and is therefore able to pull even more. Interframe relations further influence positively or negatively the frame strength. A frame has been recog nized if the framestrength is greater than a certain treshold (close to 1.0). When this is the case the behaviors associ ated with the frame are activated.
We call the relation between an object and a slot a link. The frame strength is partly determined by the strength with which a particular object fits within a certain slot. This is called the link strength. We now first describe the influences on the link strength and then the influences on the frame strength which is based on the link strength of its constitutive slots. Initially the frame-strength of all frames is set to a very low value (e.g. 0.01).
I. Impact on link strength
The link strength is determined in a series of steps:
- The initial link strength mi of the link j between an object o and a slot s of a frame f is based on the match between o and s. This match is a weighted sum based on how many properties are present and how high the cer tainty is of each property. It is similar to a perceptron-like decision process. Let ci = mi
- Objects that fit in the same slot compete (figure la.) , ci is therefore qualified as follows:
where it is equal to a (global) parameter known as the inhibition factor which determines how big competitive influence is between objects competing for the same slot. Furthermore
where k ranges over all links from objects to the same slot s.

- The link strength is influenced by the frame strength distributed proportionally over all slots in the frame lead ing to a qualified link strength si:
i ranges over all links coming out of the slot s of the same frame f. f s is the current frame-strength.
- There is competition for link strength if the same object fits in more than one slot (figure lb.), leading to a qualified link strength qi.

where i ranges over all links from an object o to any slot s.
5. There is a small random factor for avoiding dead-lock situations when two objects fit equally well in the same slot of the same frame and all else is equal.
6. Frame strength is the sum of the best link strengths
where m ranges over all slots in f and r m is the best r value form.
II. Impact on frame strength.
7. The frame strength f. is further qualified by the excita tory or inhibitory relations between frames:
where j ranges over all frames related to f, r; · is the excitatory/inhibitory relation between i and j and' 1 n is the number of frames related to f.
The computation keeps circling through the steps outlined above, starting with step 2, so that there is a continuous updating and interaction with the world.
III. Activation
There are two types of frames depending on the associated actions. The first type, called a releaser-frame, has actions that have an impact in the real world (e.g. frames activat ing dancing behavior, exploratory movement behavior, etc.). The frame is recognized if the framestrength is greater than a certain treshold (close to 1.0). When this is the case, the behaviors associated with the frame are activated and the frame itself gets a strongly reduced frame strength. Note that the functions that call the behaviors have variables which are determined on the basis of the contents of the slots. Thus there could be a frame for going towards a particular target. The associated ?ehav~or st~ moving towards the target but the target Itself IS a vanable based on which location fills the target slot in the frame. These frames are called releaser-frames because their operation implements the "releaser" behavior described by ethologists like Tinbergen. A second type of frame has actions that change the internal state of the agent, for example, frames that recognize what kind of object is there or that determine the emotional state of the agent. These frames are continuously active, in the sense ~at they continuously update the features they have an Impact on.
2.3. Justification
The theory proposed above satisfies the general structure of systems with emergent functionality (Steels, 1990). We .
~d the required feedback relation because link strength mcreases frame strength which increases link strength. How to find the best frame at a particular point in time is not programmed in but emerges by the dynamics which is at a level below the actual frames. This dynamics is influenced by the fit between a frame and the current situation and by the competition between frames. Notice that default-handling follows as a side effect of the pro posed dynamics, because the link-strength between the default filler and the frame is very weak and therefore easily overridden by an object that may also fill the slot.
2.4. Implementation
Various implementations have been constructed of the sys tem proposed here6. One runs on a Symbolics LISP machine and is essentially an environment for interac tively exploring different frame systems. It includes a graphical interface and measuring apparatus to follow the dynamics. A frame language has been designed to make it easy to define frames. ,,
A s~ond implementation has been developed to run on physical mobile robots. This implementation is written in C and downloaded on on-board processors. The frames are compil~ into C datastructures. The emergent frame recogmuon system runs in conjunction with a behavior languag~ similar to th~ one described by [Brooks, 1990]. Underlymg the behaviOr language is a scheduler which schedules the processes implied by the finite-state machines defining particular behaviors.
3. An example
In this section an example is briefly discussed. The exam ple is necessarily simple due to space limitations. We ass~me two releas~r frames each describing a possible action. One frame IS called communicate-move-request. It has slot~ for communicate-with, state, and goal. Its associ ated action performs a communication through the speech output channel to produce a request to move out of the way. The matching state of the agent is described as talka tive, in-a-hurry, etc. The goal state includes moving towards-target. The other frame is go-around-<>bject. It has slots for object, state and goal. The state includes features like frustration and exploring. The goal includes also the feature moving-towards-target. When this frame becomes act~ve it caus~s a behavior to go around the object that is filling the object slot. There are other frame-hierarchies needed for the example, such as the hierarchy of objects displayed in figure 2.

6 This work was done by Hein Saris. The behavior language was implemented by Piet Ruysselinck.
Assume a situation where there are four objects: object in-front, object-in-back, object-to-left and ~bject-tc;>-right. Each of these is competing for the commurucate-wtth ~lot in the commurricate-move-request frame and the obJe;ct slot in the go-around-object frame. The state of the agent potentially fits in the state slot of the communicate-move request and the go-around-object frame. The goal of the agent potentially fits in the goal slot of these tw? frame~. The features associated with the objects and therr associ ated certainties are as follows 7 :
object-in-front: object (1.0), living (0.8), child (0.4), noisy (0.5), pushy (0.2).
object-in-back: clear (1.0).
object-to-left: object (1.0), non-living (0.7), big (0.8).
object-to-right: clear (1.0).
The state of the agent includes the following features: talkative, exploring, in-a-hurry
The goal includes
moving-towards-target
The following simulation results list the evolution of the various link strengths and frame strengths after one sweep through the algorithm:
(after step 2)
GOAL into GOAL of GO-AROUND-OBJECT is 0.7 GOAL into GOAL of COMMUNICATE-MOVE-REQUEST is 0.9 STATE into STATE of GO-AROUND-OBJECT is 0.2
STATE into STATE of COMMUNICATE-MOVE-REQUEST is 0.5 OBJECT-TO-RIGIIT into OBJECT of GO-AROUND-OBJECT is 0.0 OBJECT-TO-RIGIIT into COMMUNICATE-WITII
of COMMUNICATE-MOVE-REQUEST is 0.030000001 OBJECT-TO-LEFT into OBJECT of GO-AROUND-OBJECT is 0.64000005 OBJECT-TO-LEFT into COMMUNICATE-WITII
- of COMMUNICATE-MOVE-REQUEST is 0.030000001 OBJECT-IN-BACK into OBJECT of GO-AROUND-OBJECT is 0.0 OBJECT-IN-BACK into COMMUNICATE-WITII
of COMMUNICATE-MOVE-REQUEST is 0.030000001 OBJECT-IN-FRONT into OBJECT of GO-AROUND-OBJECT is 0.71 OBJECT-IN-FRONT into COMMUNICATE-WITII
of COMMUNICATE-MOVE-REQUEST is 1.0
(after step 3)
GOAL of GO-AROUND-OBJECT into GOAL is O.Q7
STATE of GO-AROUND-OBJECT into STATE is 0.020000001 . . th OBJECT of GO-AROUND-OBJECT into OBJECT-IN-FRONT is 0.037340738 Ftgure 3. Evolution of frame-streng s.
OBJECT of GO-AROUND-OBJECT into OBJECT-IN-BACK is 0.0
OBJECT of GO-AROUND-OBJECT into OBJECT-TO-LEFT is 0.030340744
OBJECT of GO-AROUND-OBJECT into OBJECI'-TO-RIGIIT is 0.0
7 These features are themselves connected to sensors (infra-red, sound, pyro, touch, etc.) or groups of sensors which themselves have specific certainties.
GOAL of COMMUNICATE-MOVE-REQUEST into GOAL is 0.089999996 STATE of COMMUNICATE-MOVE-REQUEST into STATE is 0.05 COMMUNICATE-WITII of COMMUNICATE-MOVE-REQUEST into OBJECT-IN-FRONT is 0.09174312
COMMUNICATE-WITII of COMMUNICATE-MOVE-REQUEST into OBJECT-IN-BACK is 8.256881e-5
COMMUNICATE-WITII of COMMUNICATE-MOVE-REQUEST into OBJECT-TO-LEFT is 8.256881e-5
COMMUNICATE-WITII of COMMUNICATE-MOVE-REQUEST into OBJECT-TO-RIGIIT is 8.256881e-5
(after step 4)
GOAL into GOAL of COMMUNICATE-MOVE-REQUEST is 0.050624996 GOAL into GOAL of GO-AROUND-OBJECT is 0.030625
STATE into STATE of COMMUNICATE-MOVE-REQUEST is 0.035714287 STATE into STATE of GO-AROUND-OBJECT is 0.0057142866 OBJECT-TO-RIGIIT into COMMUNICATE-WITII
of COMMUNICATE-MOVE-REQUEST is 8.25688le-5 OBJECT-TO-RIGHT into OBJECT of GO-AROUND-OBJECT is 0.0 OBJECT-TO-LEFT into COMMUNICATE-WITII
of COMMUNICATE-MOVE-REQUEST is 2.240916e-7 OBJECT-TO-LEFT into OBJECT of GO-AROUND-OBJECT is 0.030258399 OBJECT-IN-BACK into COMMUNICATE-WITII
of COMMUNICATE-MOVE-REQUEST is 8.256881e-5 OBJECT-IN-BACK into OBJECT of GO-AROUND-OBJECT is 0.0 OBJECT-IN-FRONT into COMMUNICATE-WITII
of COMMUNICATE-MOVE-REQUEST is 0.06520412 object impact from OBJECT-IN-FRONT into OBJECT
of GO-AROUND-OBJECT is 0.010801744 frame strength GO-AROUND-OBJECT is 0.22199227
frame strength COMMUNICATE-MOVE-REQUEST is 0.50514466
The global evolution of the various frames is displayed graphically in the following figures. The first figure shows how the commurricate-move-request frame gradually wins over the go-around-object frame.

The next figure shows the evolution of the strength of the links between the objects and the slots for the go-around object frame. Notice how the strength gradually dimin ishes for all of them.

Finally the following figures show the evolution of the link-strengths for the communicate-move-request frame. We see that the link-strength becomes progressively stronger.

Acknowledgement
This research is partly sponsored by the Belgian govern ment Impuls program on AI and partly by Nato Grant CRG90031. Hein Saris has made valuable contributions to the contents of this paper.
@inproceedings{ijcai1991p180,
title = {Emergent Frame Recognition and Its Use in Artificial Creatures},
author = {Steels, Luc},
booktitle = {Proceedings of the Twelfth International Joint Conference on
Artificial Intelligence, {IJCAI-91}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {John Mylopoulos and Ray Reiter},
pages = {1219--1223},
year = {1991},
month = {8},
note = {Robotics},
url = {https://ijcai.org/proceedings/1991/180},
}
TY - CPAPER TI - Emergent Frame Recognition and Its Use in Artificial Creatures AU - Steels, Luc T2 - Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91 PB - International Joint Conferences on Artificial Intelligence PY - 1991 SP - 1219 EP - 1223 UR - https://ijcai.org/proceedings/1991/180 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: