Constructionist Design Methodology for Interactive Intelligences

TO BE PUBLISHED IN A.I. MAGAZINE, SUMMER/FALL 2004

Constructionist Design Methodology
for Interactive Intelligences
Kristinn R. Thórisson, Hrvoje Benko,
Denis Abramov, Andrew Arnold, Sameer Maskey,
Aruchunan Vaseekaran

Abstract
We present a methodology for designing and implementing interactive intelligences. The
Constructionist Methodology – so called because it advocates modular building blocks andincorporation of prior work – addresses factors that we see as key to future advances in A.I., includinginterdisciplinary collaboration support, coordination of teams and large-scale systems integration.
We test the methodology by creating an interactive multi-functional system with a real-time
perception-action loop. An embodied virtual agent, situated in an augmented-reality system, canperceive both real and virtual objects in a room and interact with a user through coordinated gesturesand speech. Wireless tracking technologies give the agent awareness of the environment and the user’s
speech and communicative acts. User and agent can communicate about things in the environment,
their placement and function, as well as more abstract topics such as current news, through situatedmultimodal dialog.
The results demonstrate the Constructionist Methodology’s strengths for simplifying the modelingof complex, multi-functional systems with unexplored architectures, unclear sub-system boundaries,
undefined variables, and tangled data flow and control hierarchies.

Introduction
The creation of embodied humanoids requires integration of a large number offunctionalities that must be carefully coordinated to achieve coherent behavior in theagent. We are working on formalizing a methodology that can help in this process.
The architectural foundation we have chosen for the approach is based on the conceptof a network of interacting modules, communicating via messages. To test the design
methodology we chose a system with a human user that interacts in real-time with asimulated human, in an augmented-reality environment. In this paper we present thedesign methodology and describe the system that we built to test it.
Newell [1992] urged for the search of unified theories of cognition1, and recent workin A.I. has increasingly focused on integration of multiple systems (cf. [Simmons etal. 2003, McCarthy et al. 2002, Bischoff et al. 1999]). Unified theories necessarilymean integration of many functionalities, but our prior experience in building systems
1

While Newell’s architecture Soar is based on a small set of general principles, intended to explain awide range of cognitive phenomena, Newell makes it very clear in his book [Newell 1992] that he does
not consider Soar to be the unified theory of cognition. We read his call for unification not in the
narrow sense to mean the particular premises he chose for Soar, but rather in the more broad sense torefer to the general breadth of cognitive models.

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

1

Constructionist Design Methodology for Interactive Intelligencesthat integrate multiple features from artificial intelligence and computer graphics[Bryson & Thórisson 2000, Lucente 2000, Thórisson 1999] has made it very clear thatsuch integration can be a challenge, even for a team of developers. In addition to basic
technical issues – connecting everything together can be prohibitive in terms of time –it can be difficult to get people with different backgrounds, such as computer
graphics, hardware, and artificial intelligence, to communicate effectively.
Coordinating such an effort can be a management task of a tall order; keeping all
parties synchronized takes skill and time. On top of this comes the challenge ofdeciding the scope of the system: What seems simple to a computer graphics expert
may in fact be a long-standing dream of the A.I. person, and vice versa.
Several factors motivate our work. First, a much-needed move towards building onprior work in A.I., to promote incremental accumulation of knowledge in creating
intelligent systems, is long overdue. The relatively small group who is working on
broad models of mind, bridging across disciplines, needs better ways to share results
and work together, and to work with others outside their field. To this end ourprinciples foster re-usable software components, through a common middleware
specification,2 and mechanisms for defining interfaces between components. Second,by focusing on the re-use of existing work we are able to support the construction of
more powerful systems than otherwise possible, speeding up the path towards useful,
deployable systems. Third, we believe that to study mental mechanisms they need tobe embedded in a larger cognitive model with significant breadth, to contextualize
their operation. This calls for a focus on supporting large-scale experimentation andintegration. Fourth, by bridging across multiple functionalities in a single, unified
system, researchers’ familiarity and breadth of experience with the various models ofthought to date – as well as new ones – increases. This is important – as are in fact allof the above points – when the goal is to develop unified theories of cognition.
Inspired to a degree by the classic LEGO bricks, our methodology – which we call aConstructionist approach to A.I. – puts modularity at its center: Functionalities of thesystem are broken into individual software modules, which are typically larger thansoftware classes (i.e. objects and methods) in object-oriented programming, but
smaller than the typical enterprise application. The role of each module is determinedin part by specifying the message types and information content that needs to flow
between the various functional parts of the system. Using this functional outline wethen define and develop, or select, components for perception, knowledge
representation, planning, animation, and other desired functionalities.
To test the power of a new methodology, a novel problem is preferred over one thathas a known solution. The system we chose to develop presented us with a uniquescope and unsolved integration issues: An augmented reality setting inhabited by anembodied virtual character; the character would be visible via a see-throughstereoscopic display that the user wears, and would help them navigate the real-world
environment. The character, called Mirage, should appear as a transparent, ghost-likestereoscopic 3-D graphic superimposed on the user’s real world view (Figure 1). Thissystem served as a test-bed for our methodology; it is presented in sufficient detailhere to demonstrate the application of the methodology and to show its modular
philosophy, which it mirrors closely.
2

http://www.MINDMAKERS.ORG/projects/mindmakers

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

2

Constructionist Design Methodology for Interactive Intelligences

Figure 1: Our embodied agent Mirage is situated in the lab. Here
we see how he appears to the user through the head-mounted
glasses. (Image has been enhanced for clarity.)
Behind this work lies the conjecture that the mind can be modeled through theadequate combination of interacting, functional machines (modules). Of course, this is
still debated in the research community and not all researchers are convinced of its
merits. However, this claim is in its essence simply a combination of two less radical
ones. First, that a divide-and-conquer methodology will be fruitful in studying themind as a system. Since practically all scientific results since the Greek philosophers
are based on this, it is hard to argue against it. In contrast to the search for unified
theories in physics, we see the search for unified theories of cognition in the same
way as articulated in Minsky’s [1986] theory, that the mind is a multitude ofinteracting components, and his (perhaps whimsical but fundamental) claim that thebrain is a hack.3 In other words, we expect a working model of the mind toincorporate, and coherently address, what at first seems a tangle of control hierarchies
and data paths. Which relates to another important theoretical stance: The need tomodel more than a single or a handful of the mind’s mechanisms in isolation in orderto understand the working mind. In a system of many modules with rich interaction,
only a model incorporating a rich spectrum of (animal or human) mental functioning
will give us a correct picture of the broad principles underlying intelligence.
There is essentially nothing in the Constructionist approach to A.I. that lends it morenaturally to behavior-based A.I. [Brooks 1991] or classical A.I. – its principles sit
beside both. In fact, since Constructionist A.I. is intended to address the integration
problem of very broad cognitive systems, it must be able to encompass all variants of,and approaches to, A.I. to date. We think it unlikely that any of the principles we
present would be found objectionable, or completely novel for that matter, by aseasoned software engineer. But these principles are custom-tailored to guide the3

Personal communication.

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

3

Constructionist Design Methodology for Interactive Intelligences

construction of large cognitive systems, and we hope it will be used, extended andimproved by many others over time.

Related Work
Modularity
Modular approaches have been shown to speed up the development of large, complex
systems, and to facilitate the collaborations of large teams of researchers [Fink et al.
1995, 1996]. For instance, Martinho et al. [2000] describe an architecture designed tofacilitate modular, rapid development of theatrical agents in virtual worlds. Like manyother systems [cf. Granström et al. 2002, Laird 2002, McKevitt et al. 2002, Badler etal. 1999, Terzopolous 1999], their agents live in an enclosed virtual world where theupdate cycle of the world can be artificially controlled. Martinho et al.’s architecture
involves splitting the world, along with the agents, into three separate modules, each
which can be developed independently of the others. As in our approach, this enables
parallel execution of implementation, reducing development time, and combining thepieces to form a full system becomes a simpler task. Modularity also played a largerole in the construction of Bischoff et al.'s impressive HERMES robot [2000].
Simmons et al’s robot Grace [2003], which involved the work of 5 institutions andover 20 people, is another fine example of a project that has benefited from a modular
approach.
The emphasis on modularity in our Constructionist Methodology derives from theapproach of Thórisson [1996], first used for the communicative humanoid Gandalf,
and Behavior-Oriented Design [Bryson 2002, Bryson & Thórisson 2000]. Bryson[2002] details the elements of BOD, using principles from behavior-based A.I., suchas reactive plans and tight integration of perception and action. However, thisapproach encompasses principles focused on particular ways of planning, and lacks
more general principles, and ways of using pre-existing modules. The Ymirarchitecture [Thórisson 1999] presents relatively general modularization principles,using module types such as perceptors, deciders and actions and subtypes of each, in a
way that clearly distinguishes their role and mechanisms. This was formalized andincorporated into the present work. We further extend it by turning the conventional“module-oriented” build process on its head by making the messages in the system
equally important as the modules themselves.
Embodiment
In bringing together an agent and a user, two methods are most common: The agent isbrought into the user’s world, as in robotics or screen-based agents,4 or the user isbrought into the agent’s world, as in virtual world simulations.
Robots are inherently embodied, due to their physical presence in the real world.
There has been a lot of research to try to simulate human-like movement anddecision-making process in robotics, but only more recently have there been attempts
to create a goal-oriented human-like interaction between the robot and the user. A
4

If a screen-based agent is aware of real-world objects, as well as virtual ones, it might be classified as
an augmented reality system. Traditionally, though, such classification would also imply that the user’s
reality is augmented in some obvious way by the agent/system.

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

4

Constructionist Design Methodology for Interactive Intelligences

recent example is the work of Iba et al. [2002] where multimodal input gets used(gestures and speech) to program the vacuum-cleaning robot. Another version ofbringing the agent into the user’s world is exemplified by Thórisson’s social agent
Gandalf [Thórisson 1996, 2002], which modeled real-time, coordinated psycho-social
dialog skills including turn-taking, body posture, gaze and speech.
An example of the latter approach is the research by Rickel et al. [2001]. In theirwork, a virtually embodied character is situated in simulated training sessions for thearmy; the user is placed in a virtual world with the agent. The authors acknowledge
that much improvement is still needed in areas of virtual human bodies, natural
language understanding, emotions and human-like perceptions, yet a very small
fraction of ongoing development in this area makes use of, or makes available, readily
available components that can be used in other systems.
A third alternative exists for bringing together agent and user. The term “augmented
reality” has been used to refer to systems which combine computer-generated virtual
objects with the real surrounding scene, in an interactive, real-time manner [Azuma
1997]. Participants in an augmented reality typically wear either semi-transparent orvideo see-through head mounted display (HMD) that enables them to see localized
and contextualized virtual, graphical information rendered in context in the realenvironment. Placing autonomous characters into such augmented reality presents acompelling and powerful new human-computer interaction metaphor. Such characters
can have many practical applications: They can enhance the realism of multi-player
games and virtual worlds, they can function as information retrieval assistants, andthey could serve as virtual tour guides in real museums.
Mind Models
There has been substantial work in the area of mind construction for simulated
humans (recent overviews can be found in [McKevitt et al. 2002] and [Granström etal. 2002]). Given several decades of A.I. research, the first thing we’d like to avoid is
re-inventing the wheel. With its operators and problem spaces, Soar [Newell 1992]
presents a highly unified set of principles and architectural constructs that address anumber of psychological regularities observed in human cognition. The Soararchitecture has been explored in various systems, including computer games [Laird& Lent, 2001, Laird 2002]. This theoretically motivated architecture is built from theground up: It requires significant software development work before it bridges the full
gap between perception and action. Further, Soar focuses on cognition in a narrow
sense: Perception and action were left out of the initial model, yet to use Soar insimulated worlds requires these gaps to be bridged. Although Soar has since been
extended to these areas, it is not well-suited to study alternative cognitive models,with its small set of cognitive principles. Because of their fine granularity, Soar is also
relatively complicated to use when building large systems.
Behavior-based A.I. (cf. [Bryson 2001, Brooks 1991]) was a response to the oldschool knowledge representation, and its use of explicit mental models of the world.
The approach taken in behavior-based A.I. is to tightly couple the perception andaction in integrated software structures which combine perceptual variables andprocesses with motor plans, and their selection and execution. In a complex system,
this can sometimes make software development and maintenance easier:
Implementing processes like limb-eye coordination can for example be done with

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

5

Constructionist Design Methodology for Interactive Intelligences

simpler control structures than in most other approaches. However, these architectures
tend to be limited to a single level of representation (c.f. [Maes 1990]); they are notvery conducive to accept superstructures, which are needed, for example, to do
dialogue interpretation and generation at multiple levels of abstraction (although see[Bryson 2000]).
Puff the Magic LEGO Dragon [Bryson & Thórisson 2000], and the Ymir architecture
before it [Thórisson 1999, 1996], are both examples of hybrid systems that use
blackboards for isolating message-based information between processes, based ontype and scales of time. These systems contain both planners and schedulers, but theircore is behavior-based, building upon a large number of modules, interacting atdifferent time scales. The system we describe in this paper uses fewer modules, each
module being a rather monolithic application, a choice not made for theoreticalreasons but a direct result of following our design principles for quickly building a
relatively broad system. The Constructionist Methodology can be applied in thedesign of systems incorporating any of the above approaches; moreover, to ourknowledge, it is the best method for integrating principles from all of them.

Design Principles
Our approach is based on the concept of multiple interacting modules. Modularity ismade explicit in our system by using one or more blackboards for message-passing:
To mediate communication between modules, use one or more blackboards withpublish-subscribe functionality.
The benefits of message-based, publish-subscribe blackboard architectures are
numerous. Among the most obvious ones is that the messages embody an explicit
representation of each module’s contextual behavior. The blackboard provides a
localized recording of all system events, system history, and state, precisely at thelevel of abstraction represented in the messages. Given that the messages thus
effectively implement the modules’ APIs, they in turn mirror directly the abstractionlevel of the full system, making the blackboard architecture a powerful tool forincremental building and de-bugging of complex, interactive systems. In many cases
the messages we defined became key driving forces in the Mirage system, aroundwhich the modules were organized.
We also base our approach on the following meta-assumption:
Only build functionality from scratch that is critical to the raison d’etre of thesystem – use available software modules wherever possible.
This means that a critical part of the process is to define the project’s goal(s), forexample, is it practically motivated (primary goal being its functionality), or is it
research-oriented (primary goal is to answer one or more questions regarding mental
process, human-computer interaction, or human-human interaction).
Steps
The specifics of the Constructionist Methodology are encapsulated in the following
outline. Italicized sections provide details by specific references to the example
K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

6

Constructionist Design Methodology for Interactive Intelligences

system that we built.
1. Define the Goals of the Project. Specify the primary motivation and goals behindthe system.
We wanted to show how to build an embodied, situated agent that significantly
increased the value of an augmented reality by being able to interact naturallywith human users. The primary focus was therefore on demonstrating theinteraction between the user, the agent, and the environment, and theintegration of the technologies necessary to support such a system.
2. Define the Scope of the System. Specify at a high level what the intelligent
system is intended to do. Using narratives, write example scenarios that typify its
behavior.
We start with an initial write up of a few high-level examples of user-agent
interaction. From this, a more detailed specification of the abilities of theagent can be extracted, guiding the selection of which modules to include,
such as gesture tracking, speech recognition, graphics, etc. For example, in
addition to including a module encapsulating knowledge about the objects in aroom, we decided to include a news summarization system, Columbia
Newsblaster [McKeown et al. 2002],5 which enables the agent to tell us theworld headlines when requested, and read from the news articles.
3. Modularization. The system is built using modules that communicate via a pubsub mechcanism and/or blackboard(s). Define the functional areas that the system
must serve, and divide this into 5-10 distinct modules with roughly defined roles.
The modules can then be recursively sub-divided using the same approach(principle of divisible modularity). This step is best done in a group meeting where
all developers can contribute to the effort.
a. Classify modules into one of three roles, according to whether they serve
perception, decision/planning, or action/animation. Each of these roles can befurther split into more levels. For example, high-level perception versus lowlevel perception, short-, mid- and long-term planning, and high-levelanimation versus low-level animation.
b. Find off-the-shelf software. Locate software that is already implemented that
could be used in the system. This step may require modification of thesystem’s scope. (This step does not apply to components that are part of the
project’s raison d’etre, as explained above.)c. Specify custom-written modules. Having identified usable external modules,
specify additional modules that need to be written, and what their functionality
should be.
d. Follow the natural breaks in the information processing path. Let
information flow via blackboards when (i) processes are of distinctly different
types; (ii) where information flow is relatively low-frequency, (iii) where
information flow is event driven, and/or (iv) pull rather than push, (i.e. where
the modules (typically) request their data, rather than having it “pushed” tothem by other processes), provided that they are saving processing cycles by5

http://www.cs.columbia.edu/nlp/newsblaster

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

7

Constructionist Design Methodology for Interactive Intelligences

pulling (e.g. because the frequency of data transfer via blackboards is lower
that way). This step helps define the modules and their input and output.
e. Define message types. Specify how the various parts of the system should
convey their state to the rest of the system. This step operationalizes the role ofeach module and defines their interfaces.
f. Avoid duplication of information. If a module has been designated as being
the only module in the system to need access to a particular type of data, andthen later another module is found to require access to the same data, several
possibilities should be considered. Modules with highly different functionalroles should typically not need access to the same set of data – if they do itmeans they may have close functional dependencies; consider coupling themor putting them into the same executable with shared access to the same data.
Perhaps more modules are found to need the data in question; consider
creating a separate data store server with its own API that both modules canaccess, either via a blackboard or separate mechanism.
g. Determine the number of blackboards; which modules use which
blackboards. The most obvious reason for modules to share a blackboard iswhen they need to communicate directly, i.e. when the output of one is the
input of another. Consider using two or more blackboards if (1) there is a wide
range of information types in the total set of messages in the system, e.g. coexisting complex symbolic plan structures and simple boolean switches; (2)there is a wide range of real-time requirements for the information flow, e.g.
high-frequency vision processing and low-frequency plan announcements; (3)the system needs to run on multiple computers to achieve acceptableperformance. It is natural that modules with messages containing similar
content share a blackboard. Some modules are a natural bridge between
blackboards, as for example when a module producing decisions to act
requires perceptual data to make those decisions. Blackboards serve both asengineering support and system optimization.
4. Test system against scenarios. Once a reasonably stable set of modules andmessages has been reached, the scenarios outlined in step 2 are used to test-run thesystem on paper. Using these scenarios as a guide, every module should be madevery simple at first, reading one type of message and posting another. A full endto-end chain is specified for a single interaction case, enabling every element in thepath to be tested on the whiteboard, along with the routing mechanisms, timing
assumptions, etc., very early in the design process. Such end-to-end testing should
also be performed regularly during development. The viability of themodularization is verified, with regard to the following:a. Expected communication (blackboard) throughput. Network speed andcomputing power puts natural constraints on the maximum throughput of theblackboard. For example, perceptual data, that may need to be updated at 1015 Hz, may have to bypass central message paths. If the
middleware/blackboard is powerful enough to service a stream of data, it ispreferable to route the data through it; a centralized data traffic center enables
monitoring, debugging, prioritization, etc. However, most of today’s network
solutions do not handle transmission of raw visual or auditory data at
sufficiently high rates, necessitating workarounds. In practical terms, thismeans that one may need to combine what otherwise should naturally be two

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

8

Constructionist Design Methodology for Interactive Intelligences

or more separate modules.
b. Efficient information flow. Static or semi-static information that is frequently
needed in more than one place in the system may be a hint that the processes
using that information should share an executable, thus containing theinformation in one place. Sometimes this is not a good idea, however,
especially when the processes sharing the information are of very different
nature, as in visual processing and motor control. In such cases it may bebetter to set up a server (hardware and/or software) for the data that needs tobe shared.
c. Convenience with regard to programming languages and executables. If
two modules, for example speech synthesis and an animation system, arewritten in the same language, it may be convenient to put them together into
one executable. This is especially sensible if (a) the modules use the same setof data, (b) are serially dependent on each other, (c) have similar update
frequency requirements, (d) need to be tightly synchronized, or (e) are part ofthe same conceptual system (e.g. low and high-level visual perception). Whenconceptually distinct modules are combined into the same executable, caremust be taken not to confuse their functionality in the implementation, which
could prevent further expansion of either module in the future.
The ability to verify timing is especially important when building
communicative characters since the system is bounded by real-time
performance requirements: The agent needs to act in real-time with regard to
the user’s natural behavior and expectations. If any part of the path, from
input (e.g. a user finishing a question) to the agent responding (e.g. providing
an answer), takes longer than the designers expect, or if some delay expected
to be acceptable to the user turns out to be unacceptable, a redesign orsignificant modification may be required.
Three real-world examples serve to illustrate the implications of the two steps
b and c above. First, team members could not agree on how to design theperception part: Should perception be part of the world, or should it be a
separate module that was fed information continuously from the world
module? Second, integration of perceptual information from speech and vision– how should it be implemented? A third question, which didn’t come up until
we had iterated a few times over the design, was the placement of the speechsynthesis module. Since this module was written in Java (we used FreeTTS6),
and the world was written in Java 3-D7, we decided to put the speech module
into the world [see Figure 2], since it could be better synchronized with themultimodal behavior of the agent’s body (we had the animation scheduler
control it because it gave us forced synchronization with almost no overhead).
Even though the speech synthesizer contains knowledge, prosody generation,
which rightfully belongs to the “mind” rather than the body, we felt that
performance was more important than the system’s theoretical correctness.
5. Iterate. Go through steps 2-4 as often as needed.

67

http://freetts.sourceforge.net/docs/index.php
http://java.sun.com/products/java-media/3D/

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

9

Constructionist Design Methodology for Interactive Intelligences

6. Assign modules to team members. The natural way to assign responsibilities isalong the lines of the modules, following people’s strengths and primary interest
areas. Every module gets one Lead that is responsible for that module working, fordefining the messages it receives and the messages it posts. A good way to assign
tasks, especially if the number of team members is small, is to borrow fromextreme programming8 and assign them to pairs: One Lead, chosen for theirprimary strength, and one Support, chosen by their interest and/or secondary
strength. This step depends ultimately on the goals of the project and theexperience/goals of the project members.
We had eight modules and five team members; members served as Lead on
two modules and Support on one, or Lead on one and support on two.
7. Test all modules in cooperation. It is very critical to test the modules at run-time
early on in the implementation phase, to iron out inconsistencies and deficiencies
in the message protocols and content. Selecting the right middleware for message
routing and blackboard functionality is key, as the final system depends on thisbeing both reliable and appropriate for the project. Open adapters have to exist forthe middleware to allow integration of new and existing modules. The testing isthen done with the chosen middleware and stub versions of the modules, before
their functionalities have been implemented. To begin with, the stubs can simply
print out the messages they take as input. They can also be set to publish canned
messages via keyboard or graphical menu input. Using these two features, the stub
modules can be used to do simple integration testing of the entire system.
This step often takes longer than expected. It is also one of the most overlooked
steps, yet it that cannot be avoided – doing so will only force it to happen later inthe process, delaying the ability to accurately estimate the project’s full scope, andmaking it more likely that deadlines are missed and planned functionality has to becancelled.
8. Build the modules to their full specification. This step is naturally done infrequent alteration with the prior step; as functionality is added, regression errors
tend to creep in. However, designing modules with clearly defined set of inputs
and outputs will dramatically decrease the amount of potential communication
errors and make the system behavior more predictable. In addition to building thefull modules, one must build extensive fine-tuning capabilities into each module,
such as the timing of message posting, tracking of state and history, and to achieve
the modules communicating as desired later on.
9. Tune the system with all modules cooperating. It is important to test the system
for a while with a group of people using it, and tune it based on the results.
Especially for real-time interactive systems, variations in people’s interaction styleoften unearth faults in the implementation logic, especially simplifications that theteam may have made in the interest of time, and since the system is based on
multiple modules interacting and cooperating, their real performance is notunderstood until they have been subjected to a number of different user input andscenarios.
8

http://www.extremeprogramming.org/

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

10

Constructionist Design Methodology for Interactive Intelligences

This step can be arbitrarily long, depending on the complexity of theinteraction between modules, and the complexity of the message content beingtransmitted between them. We did very little tuning of our system, but as aresult, we did not implement all the functionality we had originally planned.

Mirage System
We will now give an overview of the system we used for testing the methodology, sothat the reader may see an example system built with the approach, and better
evaluate its applicability to related systems.
To implement publish-subscribe functionality between modules we used Psyclone™
[CMLabs 2004], a platform which provides easy hookup via Java and C++ adapters.
Psyclone shares some features with earlier efforts in this area, for example Cohen etal.’s Open Agent Architecture [1994] and Fink et al.’s DACS [1996]. In our case theblackboard’s state and history served primarily as support for iterative development
and debugging, rather than the more traditional use of it as a storage for the system’s
full state at run-time. The architecture of the Mirage system is shown in Figure 2; alist of the modules is given in Table 1. We found a single blackboard sufficient for thelevel of complexity of our system, but would probably advocate a multi-blackboard
approach with further expansion. Each module is discussed briefly in the following
sections.
Augmented Reality Environment
To bridge the gap between the real and the virtual and bring our agent to “life” wechose an augmented reality approach. A head-mounted stereoscopic display (HMD)with selective transparency allows us to render the agent as a 3-D, stereoscopic
overlay graphic that the user can perceive to be situated in the real environment. The
glasses are fully transparent except where the agent appears. Special tracking
technology makes the agent appear just like any other object with a fixed location in
the room.9
The augmented reality environment consists of both perception and action/animation
scheduling modules as well as a complete graphics system that renders our embodied
agent. The user wears the optical see-through glasses (Sony LDI-D100B) and sees thereal world, overlaid with a stereoscopic image of the agent, generated in real-time (seeFigure 1). Using position and orientation tracking of the user’s head and hand(InterSense IS900) the system can make the virtual agent appear as an active part of
the real environment. Mirage can remain stationary, or move around in the world,
independently of the user, giving the impression that he occupies a physical locationin space.
Our system has a detailed 3-D model of the entire room, including sofa, tables, chairs,
desks, computers, etc., in which Mirage is placed, giving him a certain amount ofknowledge about his surrounding. Mirage can thus “perceive” the real objects in the

9

Although the tracking can keep the agent still most of the time, occasional fast movements of thehead-worn glasses will cause the agent’s image to jiggle.

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 200411

Constructionist Design Methodology for Interactive Intelligencesroom, walk around the (real-world) furniture and objects, and orient himself relative
to these. All graphics are implemented using the Java 3-D API.

Figure 2. Mirage system architecture, showing sensor and display connections to the physicaldevices. Arrows to and from Psyclone indicate message and control flow. Small rectangles on theedges of modules signify Psyclone adapters.

Interaction Capabilities
To make the agent interactive and conversational we implemented a multimodal input
system that uses speech recognition and motion tracking of the user’s right hand. The
agent itself is capable of multimodal communication with the user via a speechsynthesizer, body language, and manual gesture. For speech recognition we used the
Sphinx speech recognizer from CMU10. Mirage has access to a knowledge base for all
the objects where type, use, names, and other attributes of individual objects are
stored, allowing him to talk about them. The user can point at any object in the room
and ask Mirage what that object is. When asked about the news today, Mirage recites
news summaries generated dynamically by the NewsBlaster system from on-line
news feeds [McKeown et al. 2002]. Mirage is also aware of proximity, and it knows
its own name; when either his name is spoken or the user comes within 1 meter,
Mirage will turn to the user and greet.
Perception and Decision Modules
To allow for the human interaction scenarios mentioned above, our system used two
custom-written perception modules, in combination with a decision module. The roleof the perception modules is to create messages about changes in the environment,
including recognition of user’s speech, proximity of the user to the Mirage agent, etc.
Those messages are then used by the Decision module to create sensible responses tothe user’s input. Examples of messages between modules are given in Table 2.
The perception-1 module is built into the augmented reality environment. It keeps
track of agent’s and user’s position and orientation, noting changes of states such as“is the agent visible”, “is the agent looking at the user”, etc. Perception-1 uses
technology based on previous work by Olwal, Benko and Feiner [Olwal et al. 2003] inwhich SenseShapes (volumetric regions of interest) are used to determine user’s
selection and pointing. This relatively simple selection mechanism is triggered on any
10

http://www.speech.cs.cmu.edu/sphinx/

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

12

Constructionist Design Methodology for Interactive Intelligences

speech command, returning a list of objects being pointed at at the time of speech.
The output of Perception-1 is further processed by the module Perception-2, where
objects pointed at are combined with speech based on event time-stamps, to create aholistic perception of the user’s action. Implied meaning of perceptions is not
represented explicitly, but emerges from their combination with decision mechanisms,
thus leaving out what one might call a “cognition” module. In a more sophisticatedhumanoid, we envision several separate cognitive modules for tasks such asreasoning, dialog management, etc., all interacting via message-passing.
The main reason for separating perception into two modules was to be able to use thebuilt-in geometric computation methods of the graphics subsystem, and its alreadyavailable ability to detect selection of objects, pointing, and intersection with otherobjects. Doing those checks outside of the graphics environment would have beeninefficient and harder to implement, albeit theoretically cleaner. This meant thatperceptual responsibilities were eventually split between two modules (not counting
speech). However, once those basic messages regarding geometric operations werecreated, integrating those with the speech messages coming separately from the
speech recognizer module was a relatively easy task, handled through the separate
integration module, Perception-2.
The Decision module is responsible for integrating and interpreting all messages fromperception, and forming a response action for the agent. That selected action is thensent to the Action Scheduling module which coordinates the avatar animation andspeech synthesis. When the Decision module receives contradicting inputs or isunable to settle onto a single top-level decision, it can request that the avatar asks
clarification questions, such as “Please repeat, I did not understand”.
Discussion
Two of the third-party components we used turned out to be inadequate for theirfunction in our final system. Sphinx proved too difficult to set up and tune properly
for the time we had planned. We could have gotten better accuracy with minimal
tuning using an off-the-shelf speech recognition product such as ViaVoice or Dragon
Naturally Speaking. We also found that the speech produced by FreeTTS is very hardto understand in noisy environments – people who tried our demo had a very hardtime understanding anything that Mirage said, save for the very shortest, most obvious
utterances. While it is great to have an open source synthesizer in Java, it would be a
lot nicer if it actually generated more comprehensible output.
One potential problem of using existing modules is the sometimes lack of control
from the outside. Although such limitations turned out not to be a problem in theMirage project (we had a clear idea up front how to engineer our way around them),
the issue is a generic one that will not go away. As a future remedy to this problem weare working on a set of principles to help guide module builders when selecting,documenting and exposing the modules’ “knobs and dials”, to be better suited for use
with each other in multi-module, multi-author systems.
Psyclone was a good match to the Constructionist Methodology, and made it easy to
distribute processes between machines, something that enabled us to quickly achieve
acceptable run-time performance. This approach is likely to become increasingly
attractive over the coming years as computer prices keep dropping, making “garage-

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

13

Constructionist Design Methodology for Interactive Intelligences

A.I.” feasible, bringing new developers to the field with clusters of cheap yesteryear’s
computers, networks of which can supply the processing power for even serious A.I.
work. The computer industry has no motivation to promote the re-use of oldcomputing equipment; software such as Psyclone does, and Mirage shows this to be a
promising option.
Unlike closed virtual world systems, ours is open-loop, with unpredictable humanbehavior streaming in real-time. Since the system is run on separate computers thatcannot be run in lock-step, unpredictable delays on the network and the computers candifferentially affect the performance of the various modules. This calls for an
architecture where modules have tolerance for the error caused by such delays.
Although we did not take the implementation very far in this direction, our generalapproach reflects these constraints directly. For example, timestamps were used
extensively throughout to coordinate events and messages between modules.
ModulePosts

SpeechRecognition

Input.Perc.UniM.Hear:Off
Input.Perc.UniM.Hear:On
Input.Perc.UniM.Voice.Speakknowledge.user.agent-proximity
knowledge.user.looking-at-agent
knowledge.agent.looking-at-user
knowledge.user.looking-at-model
knowledge.model.visible
knowledge.user.pointing-at-model-objects
knowledge.user.pointing-at-room-objects
knowledge.dialog-topic
knowledge.dialog-topic.shiftingknowledge.user-goal

Perception-1

Perception-2

Subscribing
Modules
Perception-1
Perception-2
Perception-2

Decision

Table 1. A list of selected modules and their posted and subscribed-to message types.
Message Type
Sending Modules
Subscribing
Modules
Description
Arguments

Input.Perc.UniM.Hear:On
SpeechPerception-1, Perception-2

Message Type
Sending Modules
Subscribing
Modules
Description
Arguments

Input.Perc.UniM.Hear:Off
SpeechPerception-1, Perception-2

Message Type
Sending Modules
Subscribing Modules
Description
Arguments

Speech stopped
None

Speech started
None
Input.Perc.UniM.Voice.Speak
SpeechPerception-1, Perception-2
Speech stopped<sentence><word>..</word><word>..</word></sentence>

Table 2. Example specification of message format for a module.

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

14

Constructionist Design Methodology for Interactive Intelligences

Conclusion
Using the Constructionist Methodology we designed and implemented aconversational character embodied in an augmented reality system. We developed andincorporated a variety of technologies to serve our goal of a natural and simple
human-humanoid interaction that worked in real-time. The design and implementationof the full system took place within a period of 9 weeks, with 5 students dividing thework evenly. The results demonstrate that the methodology and its modularization
principles work very well for the construction of such systems.
Explicit representation of module interaction through messages, which can beinspected both on paper and at run-time, increases the system’s transparency, andincreased all team members’ understanding of how the various parts of the system
work. Before starting the Mirage project, only the instructor had experience with themethodology, and none of the students had built an interactive system of this scale
before. We feel confident to conclude that the methodology works well for building
large, modular systems, even for teams where most members are new to A.I. This
makes the Constructionist Methodology an excellent choice for classroom use.
Since the Constructionist methodology was developed for integrating large numbersof modules and system hierarchies, it is not sensible to apply it to the re-invention ofwell-tested algorithms already developed over the past decades, such as for example
natural language parsing. However, the approach’s utility is clear for incorporating
those available algorithms in larger systems, where their operation can be observed incontext, and where they have some hope of achieving utility. Mirage gives examples
of how this can be done.
In spite of the typical optimism of (young) programmers, the students were surprisedthat all modules, except for the speech recognition, were working as planned at theend of the semester (the project did not start until the last third of the semester). The
total estimated development time for Mirage, 2 mind-months (“man”-months), which
we feel strongly supports the hypothesis that the Constructionist Methodology speeds
up system creation. A parallel can be drawn with the work by Maxwell et al. [2001],
who explored the use of a message-passing architecture to facilitate modular
integration of several key technologies needed for constructing interactive robots.
Their robots have sophisticated vision, planning and navigation routines, speech
recognition and synthesis, and facial expression. They achieved impressive resultswith limited resources: 10 undergraduates working on the project for 8 weeks,
constructing three robots with this architecture, two mobile and one stationary.
One question that might be raised is whether the system thus built are too simple,
somehow hiding a hypothetical sharp rise in difficulty when applied to the design ofmore realistic models of mind, with one or two orders of magnitude greater
complexity (or requiring functionalities not addressed in Mirage). Although wecannot answer this conclusively, we feel that evidence from earlier variants of themethodology counter this claim, having been used with good results in e.g. the designof a large virtual reality environment [Bryson & Thórisson 2000] and a natural
language system deployed for CNET and Buy.com [Lucente 2000] that supported
large numbers of Internet users. The methodology is very general; there is no doubt

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

15

Constructionist Design Methodology for Interactive Intelligencesthat systems of significantly greater complexity than Mirage can be built using theapproach, reaping the same benefits.
In summary, we have demonstrated (a) the development of a relatively broad, realtime system by a small group of developers working within a very short period oftime; (b) team members’ significantly heightened awareness of the functional breadthneeded to construct interactive intelligent systems; (c) integration of prior work into a
new system, and (d) a demo which could lead the way to a practical system, for use
for example in training, showing that the methodology can help with the developmentof real-world A.I. systems. While we don’t consider the Mirage project to provide ascientific test of the hypothesis that models of mind can be developed in a modular
fashion, nothing in our explorations indicates some sort of limit to the kinds of mental
structures that the Constructionist approach could support. The methodology applies
equally to building “believable” interaction as to the goal of accurately modelingpsychological and psycho-biological processes. Indeed, since the approach allows
modularization to happen at any scale, and at one, two, or many, levels of detail, thereis hardly a system to which the method cannot be applied. That does not mean to saythat it is equally applicable to modeling all systems – indeed, we believe that it ismost applicable for systems with ill-defined boundaries between sub-systems, andwhere the number of variables to be considered is relatively large. In the current stateof science, primary examples include ecosystems, biological systems, social systems,
and intelligence.
We are currently in the process of setting up a forum, in collaboration with a larger
team, to further develop the Constructionist approach to A.I. and build a repository of“plug-and-play” A.I. modules and systems. We invite anyone with interest to join inthis effort; the URL is www.MINDMAKERS.ORG.
Acknowledgments
The authors wish to thank Steven Feiner for access to his lab, technology, andstudents; Alex Olwal for creating the avatar; the Columbia Newsblaster team; ourreviewers for excellent suggestions; and CMLabs for Psyclone, a free academic
version of which can be downloaded fromhttp://www.MINDMAKERS.ORG/projects/psyclone. Psyclone is a trademark ofCommunicative Machines Laboratories. LEGO is a trademark of The LEGO Group,
A/S, Denmark.

References
Azuma, R. T. A Survey of Augmented Reality. In Presence: Teleoperators andVirtual Environments. Vol. 6 No. 4. August 1997. 355-385.
Badler, N., M. S. Palmer, R. Bindiganavale (1999). Animation Control for Real-Time
Virtual Humans. Communications of the ACM, August, vol. 42(8), 65-73.
Bakker, B., and den Dulk, P. (1999). Causal Relationships and Relationships between
Levels: The Modes of Description Perspective. Proceedings of the TwentyFirst Annual Conference of the Cognitive Science Society, M. Hahn and S.C.
Stoness (Eds.), 43-48.
R. Bischoff (2000). Towards the Development of ‘Plug-and-Play' Personal Robots.
1st IEEE-RAS International Conference on Humanoid Robots. MIT,

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

16

Constructionist Design Methodology for Interactive Intelligences

Cambridge, September 7-8.
Bischoff, R. & V. Graefe (1999). Integrating Vision, Touch and Natural Language in
the Control of a Situation-Oriented Behavior-Based Humanoid Robot. IEEE
International Conference on Systems, Man, and Cybernetics, pp. II-999 - II1004. Tokyo, October.
Brooks, R. A. (1991). Intelligence without reason. Proceedings of the 1991
International Joint Conference on Artificial Intelligence, 569-595, Sydney,
August.
Brooks, R.A., Ferrell, C., Irie, R., Kemp, C. C., Marjanovic, M., Scassellati, B.,
Williamson, M. (1998). Alternative Essences of Intelligence. Proceedings of
AAA1/IAAA, 961-968.
Bryson, J. (2001). Intelligence by design: Principles of modularity and coordinationfor engineering complex adaptive agents. Ph.D. thesis, Massachusetts Instituteof Technology, Artificial Intelligence Laboratory.
Bryson, J. (2000). Making Modularity Work: Combining Memory Systems andIntelligent Processes in a Dialog Agent. AISB '00 Symposium on Designing a
Functioning Mind, 21-29.
Bryson, J. & Thórisson, K. R. (2000). Bats, Dragons & Evil Knights: A Three-Layer
Design Approach to Character-Based Creative Play. Virtual Reality, Special
Issue on Intelligent Virtual Agents, 5, 57-71. Heidelberg: Springer-Verlag.
Communicative Machines Laboratories (2004). The Psyclone Manual.
http://www.cmlabs.com/psyclone. Psyclone executables can be downloadedfor Linux, Windows & Mac OS X fromhttp://www.mindmakers.org/projects/psyclone.
Cohen P. R. , A. Cheyer, M. Wang, S. C. Baeg (1997). In M. N. Huhns and M. P.
Singh (eds.), Readings in Agents, 197-204. San Francisco, CA: Morgan
Kaufmann.
Cohen, Philip R., Adam J. Cheyer, Michelle Wang, and Soon Cheol Baeg (1994). An
Open Agent Architecture. In Huhns, M.N. & Singh, M.P. (Eds.), Readings in
Agents, 197-204. Morgan Kaufmann Publishers, San Francisco. Also available
online at ftp://ftp.ai.sri.com/pub/papers/oaa-aaai94.ps.gz .
Laird, J. E. & van Lent, M. (2001). Human-Level AI’s Killer Application: Interactive
Computer Games. AI Magazine, summer, 15-25.
Laird, J. (2002). Research in Human-Level A.I. Using Computer Games.
Communications of the ACM, january, vol 45(1), 32-35.
Lucente, M. (2000). Conversational Interfaces for E-Commerce Applications.
Communications of the ACM (CACM), special issue on spoken interfaces,
September, 43(9), 59-61.
Fink, G. A., N. Jungclaus, F. Kummer, H. Ritter, G. Sagerer (1996). A Distributed
System for Integrated Speech and Image Understanding. International
Symposium on Artificial Intelligence, 117-126, Cancun, Mexico.
Fink, G. A., N. Jungclaus, H. Ritter, G. Saegerer (1995). A Communication
Framework for Heterogeneous Distributed Pattern Analysis. International
Conference on Algorithms and Architectures for Parallel Processing, 881890, Brisbane, Australia.
FreeTTS. http://freetts.sourceforge.net/docs/index.php

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 200417

Constructionist Design Methodology for Interactive Intelligences

Granström, B., D. House, I. Karlsson (2002) (eds.). Multimodality in Language andSpeech Systesm. Dodrecht, The Netherlands: Kluwer Academic Publishers.
Iba, S., C.J.J. Paredis, P. K. Khosla (2002). Interactive Multi-Modal Robot
Programming. Proceedings of ICRA, Washington D.C., May.
InterSense IS900. http://www.isense.com/
Maes, P. (1990). Situated Agents can have Goals. In Maes, P. (editor), Designing
Autonomous Agents: Theory & Practice form Biology to Engineering andBack, 49-70. MIT Press, Cambridge, MA.
Maes, P. (1990). Designing Autonomous Agents: Theory & Practice form Biology to
Engineering and Back. Maes, P. (editor), MIT Press, Cambridge, MA.
Maxwell, B. A., L. A. Meeden, N. S. Addo, P. Dickson, N. Fairfield, N. Johnson, E.
G. Jones, S. Kim, P. Malla, M. Murphy, B. Rutter, & E. Silk (2001).
REAPER: A Relfexive Architecture for Perceptive Agents. A.I. Magazine,
spring, 53-66.
McCarthy, J., M. Minsky, A. Sloman, L. Gong, T. Lau, L. Morgensten, E.T. Mueller,
D. Riecken, M. Singh, P. Singh (2002). An Architecture of Diversity for
Common Sense Reasoning. IBM Systems Journal, 41, 3.
McKeown, K.R., R. Barzilay, D. Evans, V. Hatzivassiloglou J. L. Klavans, A.
Nenkova, C. Sable, B. Schiffman, & S. Sigelman (2002). Tracking andSummarizing News on a Daily Basis with Columbia’s Newsblaster. Human
Language Technology ’02 (HLT ’02), San Diego, California.
McKevitt, P., S. Ó Nulláin, C. Mulvihill (2002) (eds.). Language, Vision & Music.
Amsterdam: John Benjamins.
Minsky, M. The Society of Mind. New York: Simon and Schuster, 1986.
Newsblaster. http://www.cs.columbia.edu/nlp/newsblaster
Nicolesco, M. N. & M. J. Mataric (2002). A Hierarchical Architecture for BehaviorBased Robots. Proceedings of the First International Joint Conference on
Autonomous Agents and Multi-Agent Systems Bologna, Italy, July 15-19.
Olwal, A., Benko, H., Feiner, S (2003). SenseShapes: Using Statistical Geometry for
Object Selection in a Multimodal Augmented Reality System. Proceedings of
The International Symposium on Mixed and Augmented Reality2003 (ISMAR03), October 7-10, 2003, Tokyo, Japan.
Rickel, J., J. Gratch, R. Hill, S. Marsella, W. Swartout (2001). Steve Goes to Bosnia:
Towards a New Generation of Virtual Humans for Interactive Experiences,
Proceedings of AAAI Spring Symposium on Artificial Intelligence andInteractive Entertainment.
Simmons, R., D. Goldberg, A. Goode, M. Montemerlo, N. Roy, B. Sellner, C.
Urmson, A. Schultz, M. Abramson, W. Adams, A. Atrash, M. Bugajska, M.
Coblenz, M. MacMahon, D. Perzanowski, I. Horswill, R. Zubek, D.
Kortenkamp, B. Wolfe, T. Milam, B. Maxwell (2003). GRACE: An
Autonomous Robot for the AAAI Robot Challenge. A.I. Magazine, 24(2), 51 –72.
Thórisson, K. R. (2002). Natural Turn-Taking Needs No Manual: Computational
Theory and Model, from Perception to Action. In B. Granström, D. House, I.
Karlsson (Eds.), Multimodality in Language and Speech Systems, 173-207.
Dordrecht, The Netherlands: Kluwer Academic Publishers

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

18

Constructionist Design Methodology for Interactive Intelligences

Thórisson, K. R. (1999). A Mind Model for Multimodal Communicative Creaturesand Humanoids. International Journal of Applied Artificial Intelligence, 13(4-5), 449-486.
Thórisson, K. R. (1997). Gandalf: An Embodied Humanoid Capable of Real-TimeMultimodal Dialogue with People. First ACM International Conference on
Autonomous Agents, Mariott Hotel, Marina del Rey, California, February 5-8,
536-7
Thórisson, K. R. Communicative Humanoids: A Computational Model of
Psychosocial Dialogue Skills. PhD Thesis, MIT Media Laboratory. 1996.
Terzopoulos, D. (1999). Artificial Life for Computer Graphics. Communications of
the ACM, August, vol. 42(8), 33-42.

K.R.Thórisson et al., 2003

To be published in A.I. Magazine, summer/fall 2004

19