Articles

Agents, Bodies, Constraints,
Dynamics, and Evolution
Alan K. Mackworth

I The theme of this article is the dynamics ofevolution of agents. That theme is applied tothe evolution of constraint satisfaction, ofagents themselves, of our models of agents,of artificial intelligence, and, finally, of the
Association for the Advancement of Artificial Intelligence (AAAI). The overall thesis isthat constraint satisfaction is central toproactive and responsive intelligent behavior.

It was a great pleasure to serve as president of the Association for
the Advancement of Artificial Intelligence (AAAI). I think that everyone who serves begins with great trepidation but leaves with a senseof satisfaction. I certainly did. One of the sources of satisfaction was
the opportunity to give the presidential address at AAAI-07 in Vancouver, my hometown. This article is based on that talk. That opportunity allowed me to step back and think of the big picture, the longperspective. The way to read the title, “Agents, Bodies, Constraints,
Dynamics, and Evolution,” as it is intended to be read, is to say thatthe article is about agents with bodies subject to constraints on theirdynamics as they undergo evolution. Thus, I am telling you a story. It isa story that does not, I hope, tell any lies by omission or commission.
It is idiosyncratic, that being the nature of narrative, to make it fit
what I want to say as I make sense of that big picture. I hardly need
add that this is a highly personal and telegraphic view of the topics I
discuss. In a sense, it is a cartoon.
The theme of this article, then, is the dynamics of evolution. I shallapply that theme to five different topics: to the evolution of the ideaof constraint satisfaction, to agents themselves as they evolve, to ourown models of agents and how they have changed over time, to thefield of AI, and, finally, I shall apply it to AAAI, the organization. Thus,
we can imagine each of these concepts, including the field of AI and
AAAI, as agents acting in an environment. An agent in an active environment changes that environment and, in turn, is changed by thatenvironment as each evolves in time. To tie it all together, I do have athesis, and it will not surprise too many of you, perhaps, when I say
that the thesis is constraint satisfaction is central to intelligent behavior.

Constraint Satisfaction Problems
What may surprise you, however, is that constraint satisfaction of
today is not constraint satisfaction as it was 30 years ago—what we

Copyright © 2009, Association for the Advancement of Artificial Intelligence. All rights reserved. ISSN 0738-4602

SPRING 2009 7

ArticlesA:{1, 2, 3, 4}not(A = B)

B:
{1, 2, 4}A:{4}not(A = B)

B:
{2}

A=D

not(B = D)not(B = C)

A=D

not(B = D)not(B = C)

E<AD:{1, 2, 3, 4}

E<A

E<B
C:
{1, 3, 4}

C<D

E<D

D:
{4}

E<C

E<B
C:
{3}

C<D

E<D

E<C

E:
{1, 2, 3, 4}

E:
{1}

a

b

Figure 1. A Meeting Scheduling Problem.
(a) As a CSP in AIspace. (b) The solution to the scheduling problem found with arc consistency.

might call good old-fashioned constraint satisfaction(GOFCS). Constraint satisfaction itself has evolved
far beyond GOFCS. However, I will start withGOFCS as exemplified in the constraint satisfaction problem (CSP) paradigm. The whole concept
of constraint satisfaction is a powerful idea. It arose
in several fields somewhat simultaneously; a groupof us in the early 1970s abstracted the underlying
model. Simply, many significant sets of problems
of interest in artificial intelligence can each be
characterized as a CSP with a set of variables; eachvariable has a domain of possible values, and there
are various constraints on those variables, specifying which combinations of values for the variables
are allowed (Mackworth 1977). The constraints
may be between two variables or they may be
among more than two variables. Consider a simple
scheduling CSP example with five one-hour meetings A, B, C, D, and E to be scheduled. There areconstraints such as meeting A must occur after
meeting E; meetings A and D have to occur at thesame time but meetings A and B cannot occur atthe same time, and so on. A CSP can be represented as a bipartite graph as shown for the schedulingproblem in figure 1(a), where the meetings (variables) are shown as elliptical nodes and the constraints are shown as rectangular nodes.
As domains of possible values for the meeting

8

AI MAGAZINE

start times we have one, two, three, or four o’clockin the afternoon. We have to find a solution, a setof times that satisfies the constraints for each meeting. If you are interested, you can go to our AIspace
website1 and use the consistency-based CSP solver
applet we have developed. There you can see thisproblem satisfied using arc consistency, and othertechniques, to find out whether there is no solution, a unique solution, or more than one. For thisproblem, as it happens, there is a unique solution
for the set of possible meetings, found by runningarc consistency, shown in figure 1(b).
Using the applet, one can see the constraints
propagate around, based on arc consistency. Our
design of this AIspace applet for CSPs was inspiredby a historical video that David Waltz made in theearly 1970s to animate his edge-labeling algorithm
for line drawings of blocks world scenes (Waltz
1975). That video shows the constraints propagating around a line drawing as the sets of possible
corners at each vertex are pruned by the edge-label
constraints.
Here is a familiar CSP example from current popular culture. A typical Sudoku puzzle is shown infigure 2.
The solver has to fill in the squares, each with adigit chosen from {1, 2, …, 9}, where the constraints are that every row, every column, andArticles

every 3 x 3 subgroup has to be a permutation of
those nine digits.
Usually, to avoid torturing the puzzle solver, thepuzzle maker ensures there is one and only one
solution to the problem. One can find these solutions using arc consistency techniques and search;moreover, one can easily generate and test potential Sudoku puzzles to make sure they have one
and exactly one solution before they are published.
AI has its uses.
Arc consistency is a simple member of the classof algorithms we called network consistency algorithms. The basic idea is that one can, before constructing global solutions, efficiently eliminate
local nonsolutions. The constraints are all conjunctive, so each value for every variable must satisfy the constraints. And since all of the constraints
have to be satisfied, if there is any local value configuration that does not satisfy them, one canthrow that tuple out; that is a “no good.” So one
can discover (learn) those local inconsistencies
very quickly, in linear, quadratic, or cubic time.
Those savings will give huge, essentially exponential savings when one does start searching, constructing global solutions, using backtracking orother approaches. The simplest algorithm is arc
consistency, then path consistency, then k-consistency, and so on. Many other AI researchers contributed to this development, including Richard
Fikes, Dave Waltz, Ugo Montanari, and Eugene
Freuder. For a detailed historical perspective onthat development see Freuder and Mackworth(2006). Since those early days network consistency
algorithms have become a major research industry.
The CSP industry is one of the largest in AI, and inmany conferences over the years it has been the
single largest topic with the greatest number of sessions and papers. In fact, it has now evolved into
its own field of computer science and operations
research, called constraint programming. The CSP
approach has been combined with logic programming and various other forms of constraint programming. Indeed, it has come to have its own
journals, its own conferences, and all the otheraccoutrements of a fully fledged academic field. It
is having a major impact in many industrial applications of AI, logistics, planning and scheduling,
and combinatorial optimization. For a comprehensive overview, see the Handbook of Constraint
Programming (Rossi, van Beek, and Walsh 2006).
However, this discussion, although pertinent toinsight into the development of AI, is not central
to my theme here.

Pure Good Old-Fashioned AI
and Robotics (GOFAIR)
Here, we are more interested in how we build
agents and how the way we build them has

5

3

7

6

1
9

9

5

8

6

8

6

4

8

7

3
3

1

2

6

6

2
4

1

8

9

8

5
7

9

Figure 2. A Sudoku Puzzle.

evolved over time. John Haugeland (1985) was thefirst to use the phrase good old-fashioned AI (GOFAI)in talking about symbolic AI using reasoning andso on as a major departure from early work incybernetics and control theory. GOFAI has come to
be a straw man for advocates of subsymbolic
approaches. AI at that point, when we discovered
these symbolic techniques, tended to segregate
itself from those other areas. Lately, however, wehave been coming back together in some ways,
and that is another theme of this article. Let me
quickly add here that there was a great deal of early work in symbolic programming of robots—a lotof great work. That work can be characterized as
good old-fashioned AI and robotics (GOFAIR)(Mackworth 1993). The way I shall describe it hereis just a cartoon, for as I said, I am telling a story
here not meant to be taken literally.

GOFAIR Metaassumptions
In a cartoon sense, a pure GOFAIR robot operates
in a world that satisfies several metaassumptions:(1) there is a single agent; (2) the agent executes
actions serially; (3) actions occur in a deterministic
world; (4) the world is a fully observable, closed
world; (5) the agent has a perfect internal model ofinfallible actions and world dynamics; (6) perception is needed only to determine the initial worldstate; and (7) a perfect plan to achieve the goal is
obtained by reasoning, and executed in an open
loop.
There is a single agent in the world that executes
its actions serially. It does not have two hands thatcan work cooperatively. The world is deterministic.

SPRING 2009 9

Articles

ROBOT
stimuliactions

ENVIRONMENT

Figure 3. A Robot Coevolving with Its Environment

It is fully observable. It is closed, so if I do notknow something to be true, then it is false, thanks
to the “closed world assumption” (Reiter 1978).
The agent itself has a perfect internal model of its
own infallible actions and the world dynamics,
which are deterministic. If these assumptions aretrue then perception is needed only to determine
the initial world state. The robot takes a snapshotof the world. It formulates its world model. It reasons in that model and it can combine that reasoning with its goals using, say, a first order theorem-prover to construct a plan. This plan will be
perfect because it will achieve a goal even if it executes the plan open loop. So, with its eyes closed,
it can just do action A, then B, then C, then D,then E. If it happens to open its eyes again, it
would see, “Oh, I did achieve my goal, great!”
However, there is no need for it to open its eyes
because it had a perfect internal model of theseactions that have been performed, and they are
deterministic, and so the plan was guaranteed tosucceed with no feedback from the world.

CSPs and GOFAIR
What I would like you, the reader, to do is to thinkof the CSP model as a very simple example of
GOFAIR. There are no robots involved, but there
are some actions. The solver is placing numbers inthe squares and so on. In pure GOFAIR there is aperfect model of the world and its dynamics in theagent’s head, so I call the agent then an omniscient
fortune teller, as it knows all and it can see the entire
future because it can control it, perfectly. Therefore
if these conditions are all satisfied, then the agent’s
world model and the world itself will be in perfect

10

AI MAGAZINE

correspondence—a happy state of affairs, but it
doesn’t usually obtain. However, when working inthis paradigm we often failed to distinguish theagent’s world model and the world itself because
there really is no distinction in GOFAIR. We confused the agent’s world model and the world—aclassic mistake.

A Robot in the WorldNow we come to think about the nature of robots.
A robot acts in a world. It changes that world, andthat world changes the robot. We have to conceiveof a robot in an environment, performing actionsin an environment, and the environmental stimuli, which could be sensory stimuli or physicalstimuli, will change the robot. Therefore, think of
the robot and its environment as two coupled
dynamic systems, operating in time, embedded intime, each changing the other, as they coevolve asshown in figure 3. They are mutually evolving, perpetually, to some future state, because, of course,
the environment could contain many other agents
who see this robot as part of their environment.

Classic Horizontal Architecture
Again, in a cartoon fashion, consider the so-called
three boxes model or the horizontal architecture
model for robots. Since perception, reasoning, andaction are the essential activities of any robot—
why not just have a module for each?
As shown in figure 4, the perception moduleinterprets the stimuli coming in from the environment; it produces a perfect three-dimensional
world model that is transmitted to the reasoning
module, which has goals, either internally gener-

Articles

ROBOT
goals
perception

model

reasoningplan

stimuliactionactions

ENVIRONMENT

Figure 4. A Horizontal Architecture for a GOFAIR Robot.

ated or from outside. Combining the model andthe goals, the reasoning module produces a plan.
Again, that plan is just a sequence of the form: Do
this, do this, do this, then stop. There are no conditionals, no loops in these straight-line plans.
Those actions will, when executed, change theworld perfectly according to the goals of the robot.
Now, unfortunately for the early hopes for this paradigm, this architecture can only be thought of asa really good first cut. You know that if you wanted to build a robot it is a really good first thought.
You want to push it as hard as you can, because it
is nice and simple, it keeps it clean and modular,
and all the rest of it. It is simple but, unfortunately, not adequate. Dissatisfaction with thisapproach drove the next stage of evolution of ourviews of robotic agents, illustrating our theme.

The Demise of GOFAIRGOFAIR robots succeed in controlled environments such as blocks worlds and factories, but theycannot play soccer! GOFAIR did work, and does
work, as long as the blocks are matte blocks withvery sharp edges on black velvet backgrounds. It
works in factories if there is only one robot arm
and it knows exactly where things are and exactly
where they are going to go. The major defect, frommy point of view, is that GOFAIR robots certainly
cannot, and certainly never will, play soccer. I
would not let them into my home without adultsupervision. In fact, I would advise you not to letthem into your home either.
It turns out that John Lennon, in retrospect, wasa great AI researcher since in one of his songs hemused, “Life is what happens to you when you’rebusy making other plans.” (Lennon 1980. The key
to the initial success of GOFAIR is that the fieldattacked the planning problem and came up withreally powerful ideas, such as GPS, STRIPS, andback-chaining. This was revolutionary. Algorithms
were now available that could make plans in a way
we could not do before. Miller and colleagues’
book Plans and the Structure of Behaviour (Miller,
Galantner, and Pribam 1960) was a great inspiration and motivation for this work. In psychology
there were few ideas about how planning could bedone until AI showed the way. The GOFAIR paradigm demonstrated how to build proactive agentsfor the very first time.
But planning alone does not go nearly far
enough. Clearly, a proactive GOFAIR robot is
indeed an agent that can construct plans and act inthe world to achieve its goals, whether short term
or long term. Those goals may be prioritized. Thatis well and good. However, “There are more thingsin heaven and earth, Horatio, than are dreamt of inyour philosophy.”2 In other words, events will
occur in the world that an agent does not expect.
It has to be able to react quickly to interrupts fromthe environment, to real-time changes, to immi-

SPRING 2009 11

Articles

Drawing by Jim Marin, ©2009.

Figure 5. The Setup for the World’s First Robot Soccer Game, between Zeno and Heraclitus.

nent threats to safety to itself or humans, to otheragents, and so on. An intelligent robot must be
both proactive and responsive. An agent is proactive if it acts to construct and execute short-termand long-term plans and achieve goals in priority
order. An agent is responsive if it reacts in real time
to changes in the environment, threats to safety,
and other agents’ actions.

Beyond GOFAIR to Soccer
So that was the real challenge that was before us in
the 1980s to the GOFAIR cartoon worldview. How
could we integrate proactivity and reactivity? In
1992, I made a proposal (Mackworth 1993) that it
is fine to say robots must be proactive and reactive
or responsive but we needed a simple task domain
in order to force us to deal with those kinds ofissues. I proposed robot soccer as that domain inthat paper. Actually, I proposed it after we had
actually already built soccer players in our lab andmade them work. We built the world’s first robot
soccer players, using cheap toy radio-controlled
monster trucks, as drawn in figure 5. The first two
players were named after Zeno and Heraclitus. You
can see videos of the first robot soccer games on
the web.3

12

AI MAGAZINE

A single color camera, looking down on thesetrucks, could see the colored circles on top of thetrucks so that the perceptual system could distinguish Zeno from Heraclitus. It could also see theball and the goals. Each truck has its own controller. Since they cannot turn in place—they arenonholonomic—it is very hard actually to control
them. It is a very tricky problem to control thiskind of steerable robot. The path-planning problems have to be solved in real time. Of course, one
is trying to solve a path-planning problem, as theball is moving and the opponent is moving inorder to get that ball; that is very tricky computationally. We were pushing the limits both of oursignal-processing hardware and the CPUs to get
this to work in real time. We were running there atabout 15 Hz cycle time. The other problem wasthat our lab was not big enough for these monster
trucks. We wanted to go with more trucks, but the
department head would not give us a bigger lab. So
we were forced to go to smaller robots, namely,
1/24th scale radio-controlled model Porsches, that
we called Dynamites. These cars were running on aping-pong table with a little squash ball. In the
online video, one can see the players alternating
between offensive and defensive behaviors. The

Articles

behaviors the robots exhibit are clearly a mix ofproactive and responsive behaviors, demonstrating
the theme of evolution of our models of agents
beyond the GOFAIR approach.
Incidentally, there was an amazing, successful
effort to get chess programs to the point where
they beat the world champion (Hsu 2002). But
from the perspective presented here, it changes
only the single-agent Sudoku puzzle into a twoagent game; however, all the other aspects of the
Sudoku domain remain the same—perfect information, determinism, and the like. Chess loses its
appeal as a domain for driving AI research in new
directions.
We managed to push all our soccer system hardware to the limit, so we were able to develop twoon-two soccer. The cars were moving at up to 1
meter per second and autonomously controlled at
30 Hz. Each had a separate controller off board,and the cars were entirely independent. The only
thing they shared is a common front-end visionperceptual module. We were using transputers (a 1
MIP CPU) because we needed significant parallelism here. You can see a typical game segmentwith the small cars on the web.4 We were able todo the real-time path planning and correction andcontrol at about 15–30 Hz, depending, but thatwas really the limit of where we could go at thattime (1992–94) because we were limited by the
hardware constraints.

RoboCup
As it happens, shortly thereafter, some Japanese
researchers started to think along similar lines.
They saw our work and said, “Looks good.” Insteadof using steerable robots, as we had, they choseholonomic robots that can spin in place. Hiroaki
Kitano and his colleagues in Japan proposed
RoboCup (Kitano 1998). In Korea, the MiroSot
group5 was also intrigued by similar issues. It madefor an interesting international challenge.
The first RoboCup tournament was held in
Nagoya, Japan, in 1997. Our University of British
Columbia (UBC) team participated; it was a milestone event. Many researchers have subsequently
made very distinguished contributions in the
robot soccer area, including Peter Stone, Manuela
Veloso, Tucker Balch, Michael Bowling, Milind
Tambe, and many others. It has been fantastic. At
RoboCup 2007, held in Atlanta, Georgia, there
were approximately 2,700 participant agents, andof those, about 1,700 were people and 1,000 wererobots. A review of the first 10 years of RoboCup
has recently appeared (Visser and Burckhard 2007)
showing how it has grown in popularity and influenced basic research.
RoboCup has become incredibly exciting, a little
cutthroat and competitive with, perhaps, somedubious tactics at times but that is the nature of

Illustration by Giacomo Marchesi, ©2009.

Figure 6. Humanoid Robot Soccer Player.

intense competition in war and soccer. More
importantly, robot soccer has been incredibly stimulating to many young researchers, and it hasbrought many people into the field to do fine work
including new competitions such as RoboRescue
and RoboCup@Home. The RoboCup mission is tofield a team of humanoid robots to challenge andbeat the human champions by 2050, as suggested
by figure 6.

From Sudoku to Soccer and Beyond
Now let us step back a bit and consider our themeof evolutionary development. If one thinks of the

SPRING 2009 13

Articles

SudokuSoccerNumber of agents

1

23

Competition

No

Yes

Collaboration

No

Yes

Real timeNo

Yes

Dynamics

MinimalYes

ChanceNo

Yes

OnlineNo

Yes

Planning Horizons

No

Yes

Situated Perception

No

Yes

Partially Observable

No

Yes

Open World

No

Yes

Learning

Some

Yes

Figure 7. Comparison of Sudoku and Soccer along Various Dimensions.

Sudoku domain as the exemplar of GOFAIR in avery simple-minded way, then soccer is an exemplar of something else—what is the somethingelse? I think it is situated agents, and so we are intransition from one paradigm to another. As
shown in figure 7, we can compare Sudoku andsoccer as exemplar tasks for each paradigm,
GOFAIR and situated agents, respectively, along
various dimensions.
I shall not go through these dimensions exhaustively. In soccer we have 23 agents: 22 players anda referee. Soccer is hugely competitive between theteams obviously, but also of major importance isthe collaboration within the teams, the teamwork
being developed, the development of plays, andthe communications systems, the signaling systems between players and the protocols for them.
Soccer is very real time. There is a major influenceof dynamics and of chance. Soccer is online in thesense that one cannot compute a plan offline andthen execute it, as one can in GOFAIR. Wheneveranything is done, a plan almost always must berecomputed. There exist a variety of temporal planning horizons, from “Can I get my foot to the14

AI MAGAZINE

ball?” through to “Can I get the ball into the net?”and “Can I win this tournament?” The visual perception is very situated and embodied. Vision is on
board the robots now in most of the leagues, so arobot sees only what is visible from where it is,meaning the world is obviously only partiallyobservable. The knowledge base is completely
open because one cannot infer much about what isgoing on behind one’s back. The opportunities for
robot learning are tremendous.

From GOFAIR to Situated Agents
As we make this transition from GOFAIR to situated agents, how is it done? There has been a wholecommunity working on situated agents, sinceJames Clerk Maxwell in the late 19th century
building governors for steam engines and the like.
Looking at Maxwell’s classic paper “On Governors” (Maxwell 1868), it is clear that he produced
the first theory of control, trying as he was tounderstand why James Watts’s feedback controller
for steam engines actually worked, under what
conditions it was stable, and so on. Control theorists have had a great deal to say about situatedagents for the last century or so. So, one way tobuild a situated agent would be to suggest that we
put AI and control together: to stick a planner, an
AI planner, GOFAIR or not, on top of a reactive
control-theoretic controller doing PID control.
One could also put in a middle layer of finite-statemode control. These are techniques we fully
understand, and that is, in fact, how we did it for
the first soccer players, which I have describedabove. There was a two-level controller. However,there are many problems with that approach, notthe least being debugging it, understanding it, letalone proving anything about it. It was all very
much: try it and see. It was very unstable as new
behaviors were added. It had to be restructured at
the higher level and so on. Let me just say that it
was a very graduate student intensive process
requiring endless student programming hours! So
rather than gluing a GOFAIR planner on top of amultilayer control-theoretic controller we moved
in a different direction.
I argued that we must abandon the metaassumptions of GOFAIR but keep constraint satisfaction. My response was that we just give up on thosemetaassumptions of GOFAIR but not throw out
the baby of constraint satisfaction with the bathwater of the rest of GOFAIR. Constraint satisfaction was, and is, the key in my mind, and the reason it is the key is that we understand symbolic
constraints, as well as numerical. We understandhow to manipulate them and so on. We understand even first-order logic as a constraint-solving
system, thanks to work on that side, but we also
understand constraints in the control world. We
understand that a thermostat is trying to solve aArticles

Photo courtesy Stefan Eissing.

Figure 8. Robot Friends Playing Soccer.

constraint. We have now a uniform language of
constraint solving or satisfaction although one
aspect may be continuous while the other may bediscrete or even symbolic. There is a single language or single paradigm to understand it from top
to bottom, which is what we need to build clean
systems. The constraints now though are dynamic:
coupling the agent and its environment. They are
not like the timeless Sudoku constraint: every
number must be different now and forever. Whenone is trying to kick a ball. the constraint one is trying to solve is whether the foot position is equal tothe ball’s position at a certain orientation, at a certain velocity, and so on. Those are the constraints
one is trying to solve, and one really does not care
how one arrives there. One simply knows that at a
certain point in time, the ball will be at the tip ofthe foot, not where it is now but where it will be in
the future. So this is a constraint, but it is embedded in time, and it is changing over time as one istrying to solve it, and clearly, that is the tricky part.
Thus, constraints are the key to a uniform archi-

tecture, and so we need a new theory of constraintbased agents. This has set the stage. I shall leave
you in suspense for a while for a digression before
I come back to sketch that theory. Its development
is part of the evolutionary process that is thetheme of this article.

Robot Friends and Foes
I digress here briefly to consider the social role ofrobots. Robots are powerful symbols; they have areally interesting emotional impact. One sees thisinstinctively if one has ever worked with kids andLego robotics or the Aibo dogs that we see in figure
8, or with seniors who treat robots as friends andpartners. We anthropomorphize our technology
with things that look almost like us or like ourpets—although not too much like us. (That is the“uncanny valley” [Mori 1982]). We relate tohumanoid robots very closely emotionally. Children watching and playing with robot dogs appear

SPRING 2009 15

Articles

Illustration by Giacomo Marchesi, ©2009.

Figure 9. … and Robot Foes.

to bond with them at an emotional level.
But, of course, the flip side is the robot soldier(figure 9), the robot army, and the robot tank.

Robots, Telerobots,
Androids, and Cyborgs
Robots really are extensions of us. Of course, there
are many kinds of robots. One uses the word robot
loosely but, technically, one can distinguishbetween strictly autonomous robots and telerobots
where there is human supervisory control, perhaps
at a distance, to Mars or in a surgical situation, forexample. There are androids that look like us andcyborgs that are partly us, partly machine. The
claim is that robots are really reflections of us, andthat we project our hopes and fears onto them.
That this has been reflected in literature and othermedia over the last two centuries is a fact. I do notneed to bring to mind all the robot movies, butrobots do stand as symbols for our technology.
Dr. Frankenstein and his creation, in Franken-

16

AI MAGAZINE

stein; or, The Modern Prometheus (Shelley 1818),
stood as a symbol of our fear, a sort of Faustian fearthat that kind of power, that kind of projection of
our own abilities in the world, would come backand attack us. Mary Shelley’s work explored that,and Charlie Chaplin’s Modern Times (1936)
brought the myth up to date. Recall the scene inwhich Chaplin is being forced to eat in the factory
where, as a factory worker, his entire pace of life isdictated by the time control in the factory. He is aslave to his own robots, and his lunch break is constrained because the machines need to be tended.
He is, in turn, tended by an unthinking robot who
keeps shoving food into his mouth and pouring
drinks on him until finally, it runs amok. Chaplin
was making a very serious point that our technology stands in real danger of alienating and repressing us if we are not careful.
I shall conclude this somewhat philosophicalinterjection with the observations of two students
of technology and human values. MarshallArticles

Photo Courtesy University of Calgary.

Figure 10. RoboSurgeon NeuroArm.

McLuhan argued, although he was thinking ofbooks, advertising, television, and other issues of
his time but it applies equally to robots, “We first
shape the tools and thereafter our tools shape us.”
(McLuhan 1964). Parenthetically, this effect can beseen as classic projection and alienation in thesense of Ludwig Andreas Feuerbach (1854).
The kinds of robots we build, the kinds of robots
we decide to build, will change us as they willchange our society. We have a heavy responsibility to think about this carefully. Margaret
Somerville is an ethicist who argues that actually
the whole species Homo sapiens is evolving into
Techno sapiens as we project our abilities out(Somerville 2006). Of course, this is happening at
an accelerating rate. Many of our old ethical codes
are broken and do not work in this new world,whether it is in biotechnology or robotics oralmost any other area of technology today. As creators of some of this technology, it is our responsibility to pay serious attention to that.

Robots: One More
Insult to the Human Ego?
Another way of thinking about our fraught andambivalent relationship with robots is that this isreally one more insult. How much more canhumankind take? Robotics is only the latest displacement of the human ego from center stage.
Think about the intellectual lineage that links
Copernicus, Darwin, Marx, Freud, and robots. Thismay be a stretch in thinking but perhaps not.
Humans thought they were at the center of theuniverse until Nicolaus Copernicus proposed thatthe earth was not at the center and the sun should
be seen that way. Charles Darwin hypothesized weare descended from apes. Karl Marx claimed thatmany of our desires and goals are determined byour socioeconomic status, and, thus, we are not as
free as we thought. Sigmund Freud theorized thatone’s conscious thoughts are not freely chosen but
rather come from the unconscious mind. Now I
suggest that you can think of robots as being in

SPRING 2009 17

Articles

11. This chair can use vision and other sensors tolocate itself, map its environment, and allow its
user to navigate safely.

RoboCars: DARPA Urban Challenge

Figure 11. Prototype Smart Wheelchair (UBC, 2008).
that same great lineage of saying, you, Homo sapiens, are not unique. Now, there are other entities,
robots, created by us, that can also perceive, think,
and act. They could become as smart as we are. But
this kind of projection can lead to a kind of moral
panic: “The robots are coming! The robots arecoming! What are we going to do?” When we talkto the media the first questions reporters ask are,typically: “Are you worried about them rising up
and taking over?” and “Do you think they’ll keep
us as pets?” The public perception of robots isevolving as our models of robots and the robots
themselves evolve.

Helpful Robots
To calm this kind of panic we need to point tosome helpful robots. The arm shown in figure 10(on the previous page), the RoboSurgeon NeuroArm, is actually fabricated from nonmagnetic
parts so it can operate within a magnetic resonanceimaging (MRI) field. The surgeon is able to do neurosurgery telerobotically, getting exactly the rightparts of the tumor while seeing real-time feedback
as the surgery is performed. An early prototype of
our UBC smart wheelchair work is shown in figure

18

AI MAGAZINE

Continuing with the helpful robot theme, consider autonomous cars. The original DARPA Challenges, in 2004 and 2005, and the Urban Challenge in 2007, have catalyzed significant progress,
stimulated by Ron Brachman (my predecessor as
AAAI president) at DARPA. Sebastian Thrun andhis team at Stanford developed Junior (figure 11a),loaded with sensors and actuators and horsepower
and CPUs of all sorts, facing off against Boss (figure11b), the Carnegie Mellon University/General
Motors Tartan racing team in the fall of 2007, with
Boss taking first place and Junior second in the
Urban Challenge.6 The media look at these developments and see them as precursors to robot tanks,
cargo movers, and automated warfare, reaching an
understanding of why DARPA funded them. However, Thrun (2006) is an evangelist for a different
view of such contests. The positive impact of having intelligent cars would be enormous. Consider
the potential ecological savings of using highways
so much more efficiently instead of paving overfarmland. Consider the safety aspect in reducing
the annual carnage of 4,000 road accident deaths ayear in Canada alone. Consider the fact that cars
could negotiate at intersections, the way Dresnerand Stone (2008) have simulated to show you
could get maybe two to three times the throughput
in cities in terms of traffic if these cars could talk toeach other instead of having to wait for dumb stop
signs and traffic lights. Consider the ability for theelderly or disabled to get around on their own.
Consider the ability to send one’s car to the parking lot by itself and then call it back later. There
would be automated warehouses for cars instead ofusing all that surface land for parking. Truly, thestrong positive implications of success in this area
are enormous. But, can we trust them? This is a real
problem and it is one of the major problems. In
terms of smart wheelchairs, one major reason they
do not already exist now is liability. It is almost
impossible to get an insurance company to back aproject or a product. This clarifies why the car
manufacturers have moved very slowly in an incremental way to develop intelligent technology.

Can We Trust Robots?
There are some real reasons we cannot yet trust
robots. The way we build them now, not only are
they not trustworthy, they are also unreliable. So,
can they do the right thing? Will they do the rightthing? And then, of course, there is the fear that I
alluded to earlier that eventually they will become
autonomous, with free will, intelligence, and consciousness.

Articles

Photos courtesy US Defense Advanced Research Projects Agency.

Figure 12. Two Competitors in the DARPA Urban Challenge.

Ethics at the Robot-Human Interface
Do we need robot ethics, for us and for them? We
do. Many researchers are working on this (Anderson and Anderson 2007). Indeed, many countries
have suddenly realized this is an important issue.
There will have to be robot law. There are alreadyrobot liability issues. There will have to be professional ethics for robot designers and engineers justas there are for engineers in all other disciplines.
We will have to factor the issues around what weshould do ethically in designing, building, anddeploying robots. How should robots make decisions as they develop more autonomy? Whatshould we do ethically and what ethical issues arisefor us as we interact with robots? Should we givethem any rights? We have a human rights code;
will there be a robot rights code?
There are, then, three fundamental questions wehave to address. First, what should we humans do
ethically in designing, building, and deploying
robots? Second, how should robots decide, as they
develop autonomy and free will, what to do ethically? Third, what ethical issues arise for us as weinteract with robots?
Asimov’s Laws of Robotics. In considering thesequestions we will go back to Isaac Asimov (1950) as
he was one of the earlier thinkers about theseissues, who put forward some interesting, if perhaps naïve, proposals. His original three Laws of
Robotics are: I. A robot may not harm a humanbeing, or, through inaction, allow a human being
to come to harm. II. A robot must obey the orders
given to it by human beings except where suchorders would conflict with the First Law. III. A
robot must protect its own existence, as long as
such protection does not conflict with the First or
Second Laws.

Asimov’s Answers. Asimov’s answers to thosequestions I posed are that, first, you must put thoselaws into every robot, and by law manufacturers
would have to do that. Second, robots should
always have to follow the prioritized laws. He did
not say much about the third question. His plotsarise mainly from the conflict between what thehumans intend the robot to do and what it actually does do, or between literal and sensible interpretations of the laws because they are not codified
in any formal language. He discovered many hidden contradictions, but they are not of great interest here. What is of interest and important here isthat, frankly, the laws and the assumptions behindthem are naïve. That is not to blame Asimov, as hewas very early and pioneered the area, but we cansay that much of the ethical discussion nowadays
remains naïve. It presupposes technical abilities
that we just do not have yet.

What We Need
We do not currently have adequate methods formodeling robot structure and functionality, of predicting the consequences of robot commands andactions, and of imposing requirements on thoseactions, such as reaching the goal but doing it in asafe way and making sure that the robot is always
live, with no deadlock or livelock. And mostimportantly, one can put those requirements on
the robot, but one has to be able to find out
whether the robot will be able to satisfy thoserequirements. We will never have, for real robots,
100 percent guarantees, but we do need withinepsilon guarantees. Any well-founded ethical discussion presupposes that we (and robots) doindeed have such methods. That is what we
require.

SPRING 2009 19

Articles

ROBOT

controller-n...

...
controller-2
controller-1
bodystimuliactions

ENVIRONMENT

Figure 13. A Vertical Robotic System Architecture.

Theory Wanted
So, finally coming back to the constraint-based
agent theory, it should help to satisfy thoserequirements. In short, we need a theory with alanguage to express robot structure and dynamics,
language for constraint-based specifications, and averification method to determine whether a robot
described in the first language will be likely to satisfy its specifications described in the second language.

Robots as Situated Agents
What kind of robots, then, are we thinking about?
These are situated robots tightly coupled to theenvironment; they are not universal robots.
Remember Rossum’s Universal Robots (Capek 1923)?
We are not going to build universal robots. We aregoing to build—we are building—very situatedrobots that are functioning in particular environments for particular tasks. But those environments
are, typically, highly dynamic. There are otheragents. We have to consider social roles. There is a20

AI MAGAZINE

very tight coupling of perception and action, perhaps at many different levels. We now know thatthe human perceptual system is not a monolithic
black box that delivers a three-dimensional modelfrom retinal images. There are many visual subsystems dealing with recognition, location, orientation, attention, and so forth. Our robots will be likethat as well.
It is not “cheating” to embody environmental
constraints by design, evolution, or learning. It wascheating in the old GOFAIR paradigm, which did
aim at universal robots. Everything had to be
described in, say, the logic, and one could notdesign environmental constraints into the robots.
We think just following biology and natural evolution is the way to go, and learning will play amajor part. Evolution is learning at the species level. Communication and perception are very situated. The architectures are online, and there is a hierarchy of time scales and time horizons. Critically,
we want to be able to reason about the agent’s correctness as well as in the agents. We do not require
the agents to do reasoning—they may not—but

Articles

Vertical Architecture
To satisfy those requirements for situated agents
we have to throw away the horizontal three boxes
architectural model and move to a vertical “wedding cake” architecture. As shown in figure 13, as
one goes up these controllers, each controller seesa virtual body below it, modularizing the system inthat way. Each controller, as one goes higher, isdealing with longer time horizons but with coarser time granularity and different kinds of perception. Each controller will only know what it needs
to know. This architectural approach was advocated by James Albus (1981) and Rodney Brooks(1986). It corresponds quite closely to biologicalsystems at this level of abstraction.

FootPosition(U) = BallPosition(U)FootPosition(U)certainly we want to be able to reason about them.
When we think back to the GOFAIR model, we
never actually did that. The reasoning was in theagent’s head alone, and we assumed that if it wascorrect everything else was correct. Finally, as I
mentioned earlier, one cannot just graft a symbolic system on top of a signal-control-based systemand expect the interface to be clean, robust, reliable, debuggable, and (probably) correct. So theslogan is “No hybrid models for hybrid systems.”

BallPosition(U)Figure 14. Solving a Dynamic Soccer Constraint.

A Constraint-Based Agent
We are interested in constraint-based agents. They
are situated; they will be doing constraint satisfaction but in a more generalized sense, not in the
GOFCS sense. These constraints may be prioritized.
Now we conceive of the controller of the agent or
robot as a constraint solver.

Dynamic Constraint Satisfaction
Consider the generalization of constraint satisfaction to dynamic constraint satisfaction. A soccer
example will serve us.
Imagine a humanoid robot trying to kick a soccer ball. In figure 14, we can see the projection intoa two-dimensional space of a complex phase spacethat describes the position and velocity of thelimbs of the robot and the ball at time (t). Eachflow line in the figure shows the dynamics of theevolution of the system from different initial conditions. The controller has to be able to predict
where the robot should move its foot to, knowing
what it knows about the leg actuators and the balland where it is moving and how wet the field isand so on, to make contact with the ball to propel
it in the right direction. That corresponds to the 45
degree line y = x. So x here is the ball position on
the horizontal axis and y is the foot position on thevertical axis. That is the constraint we are trying tosolve. If the controller ensures the dynamical system always goes to (or approaches, in the limit)that constraint and stays there, or maybe if it doesn’t stay there but always returns to it soon enough,then we say that this system is solving that constraint, FootPosition(t) = BallPosition(t). In hybrid
dynamic systems language, we say the coupledagent environment system satisfies the constraint if
and only if the constraint solution set, in the phasespace of that coupled hybrid dynamic system, is an
attractor of the system as it evolves. Incidentally,that concept of online hybrid dynamic constraint
satisfaction subsumes the entire old, discrete
offline GOFCS paradigm (Zhang and Mackworth1993).

Formal Methods forConstraint-Based AgentsThe constraint-based agent (CBA) framework consists of three components: (1) Constraint Nets (CN)for system modeling; (2) timed for-all automata forbehavior specification; and (3) model-checking
and Liapunov methods for behavior verification.
These three components correspond to the tripartite requirement for the theory I said we wanted earlier. Ying Zhang and I developed these formal methods for constraint-based agents (Zhang
and Mackworth 1995; Mackworth and Zhang
2003). First, there is an architecture for distributed
asynchronous programming languages called Constraint Nets. Programs in CN represent the robot
body, the controller, and the environment. In
them are represented constraints that are local on
the structure and dynamics of each system. For

SPRING 2009 21

Articles

Figure 15. A Robot and a Human Play Ball.

behavior specification we use either temporal logics or timed for-all automata. For verification techniques we have used model checking or generalized Liapunov techniques taken from the standard
control literature but generalized for symbolic aswell as numerical techniques. Rather than present
any technical detail here, I shall sketch a casestudy, again using soccer.

A Soccer Case Study with
Prioritized Constraints
Suppose we want to build a robot soccer playerthat can move around the world, and repeatedly
find, track, chase, and kick the soccer ball. The setup is shown in Figure 15. Pinar Muyan-Özçelik
built a controller for this robot to carry out the taskusing the constraint-based agent methodology

22

AI MAGAZINE(Muyan-Özçelik and Mackworth 2004). The
detailed view of the robot in figure 16 shows arobot base, which can only move in the direction
it is facing but can rotate in place to move in a new
direction. There is a pan-tilt unit that serves as aneck and a trinocular color camera on top of it thatcan do stereo vision, but in this experiment weused monocular color images only.
This is a very simple, almost trivial example, buteven here you get a rich complexity of interaction
with emergent behavior. Imagine that you havegot very simple controllers that can solve each ofthese constraints: (1) to get the ball in the image,(2) if the ball is in the image, center it, (3) make thebase heading equal to the pan direction. Imagine
that you are a robot and remember you can only
move forward in the direction you are facing. If
you turn your head to the left and acquire the ballin the image over there then you have to turn your

Articles

body to the left towards it, and as you are tracking
the ball in the image, you have to turn your headto the right in the opposite direction. This is analogous to the well-known vestibulocular reflex(VOR) in humans. Now you are looking at the balland facing towards it, so now you can movetowards it and hit the ball. The last constraint is forthe robot to be at the ball. These are the constraints, and from that will emerge this unified
behavior: acquire, track, chase, and kick the ball if
we can satisfy these constraints, but in that priority order. If at any time one is satisfying a lower priority constraint and a higher priority constraint
becomes unsatisfied, the controller must revert toresatisfying it.
The prioritized constraints are: Ball-In-Image (I),
Ball-In-Center (C), Base-Heading-Pan (H), RobotAt-Ball (A). The priority ordering is: I > C > H > A.
We want to satisfy those prioritized constraints.
That is the specification. The specification for thissystem is that one has to solve those four constraints with that priority. That is all one would say
to the system. It is a declarative representation of
the behavior we want the system to exhibit. We
can automatically compile that specification into acontroller that will in fact exhibit that emergent
behavior. We can conceptualize these prioritized
constraint specifications as generalizations of the
GOFAIR linear sequence plans.

Trinocular
CameraPan Tilt Unit

B14 Robot

Constraint-Based Agentsin Constraint Nets
Suppose we are given a prioritized constraint specification for a controller at a certain level in thecontroller hierarchy as in figure 17. The specification involves Constraint-1, Constraint-2, and Constraint-3. It requires this priority order: Constraint1 > Constraint-2 > Constraint-3.
We assume we have a simple solver for each constraint, Constraint Solver-1, Constraint Solver-2,
and Constraint Solver-3. Constraint-1 is the highest priority, so if it is active and not satisfied, its
solver indicates, “I’m not satisfied now; I’d like you
to do this to satisfy Constraint-1.” It might be a
gradient descent solver, say. Its signal would go
through Arbiter-1. The arbiter knows this is higher
priority and its signal passes it all the way throughto Arbiter-2 as well, to the motor outputs. If Constraint-1 is satisfied, Arbiter-1 will let Constraint
Solver-2 pass its outputs through and so on. If
there is any conflict for the motors, that is how it
is resolved. If there is no conflict then the constraints can be solved independently because they
are operating in orthogonal spaces. Using thatarchitecture we built a controller for those constraints in the soccer player, and we tested it all in
simulation, and it works. It works in a wide variety
of simulated conditions; it works with the same
controller in a wide variety of real testing situa-

SoccerBall

Figure 16. A Simple Soccer Player.

tions. We found that the robot always eventuallykicks the ball repeatedly, both in simulation andexperimentally. In certain circumstances, we canprove that the robot always eventually kicks theball repeatedly. We conclude that the constraintbased agent approach with prioritized constraints
is an effective framework for robot controller construction for a simple task.
Just as an aside, this is a useful way to think
about a classic psychology problem. Carl Lashley,
in a seminal paper called “The Problem of the Serial Ordering of Behavior” (Lashley 1951), was writing about speech production, but the sequencing
problem arises for all behaviors. Suppose one has alarge number of goals one is attempting to satisfy.
Each goal is clamoring to be satisfied. How do thegoals get control of the actuators? How does one
sequence that access? How does one make sure it is

SPRING 2009 23

Articles

AGENT
CONTROLLERCONTROLLER-O
Reports...

Constraints

Constraint
Solver-1

Constraints

Constraint
Solver-2...

Reports

CONTROLLER-1
Reports

Constraint
Solver-3

Arbiter-2

Commands
BODY

Reactions

Arbiter-1

Actions

ENVIRONMENT

Control Sythesis with
Prioritized Constraints
Constraint1 > Constraint2 > Constraint3

Figure 17. Synthesizing a Controller from a Prioritized Constraint Specification.

robust? For prioritized constraints, it is robust in
the sense that if the controller senses the loss ofsatisfaction of a higher priority constraint it will
immediately resume work on resatisfying it. One
can also think of what we have done as a formalization of subsumption (Brooks 1991). So this is asolution; I am not saying it is the solution. It is avery simple-minded solution, but it is a solution to
the classic problem of the serial ordering of behavior. And it demonstrates that prioritized constraints can be used to build more reliable dynamic agents.

Modeling Uncertainty
So far, nothing has been said about the element ofchance but, of course, in real robots with real environments there will be much noise and uncertainty. Robert St-Aubin and I have developed probabilistic constraint nets using probabilistic
verification (St-Aubin, Friedman, and Mackworth2006). As shown in Figure 18, there will be uncertainty in the model of the dynamics and in the
dynamics themselves and in the robot’s measure-24

AI MAGAZINE

ment of the world. Moreover, one will be unable tofully model the environment, so there will be environmental disturbances.

Observations
Stepping back we observe that a very simple idea,
constraint satisfaction, allows us to achieve intelligence through the integration of proactive andresponsive behaviors and it is uniform top to bottom. We see in the formal prioritized framework
the emergence of robust goal-seeking behavior. I
propose it as a contribution to the solution of the
problem of a lack of technical foundation to manyof the proposals for robot ethics. So if one asks,“Can robots do the right thing?” The answer so far
is, “Yes, sometimes they can do the right thing,almost always, and we can prove it, sometimes.”

Challenges for AAAI
As noted throughout, evolution is a dynamic
process. I have discussed how constraint satisfaction has changed, how agents change, how ourArticles

Environmental
Disturbances
Uncertainty
in the Dynamics

Measurement
Noise

TARGET
Control Force

Figure 18. Uncertainty in Robots.

model of agents has changed, and how AI is changing as we dropped the metaassumptions that held
us back in GOFAIR and evolved to the situatedagent model.
AAAI, as an organization, is an agent; it is operating in an environment, a global environment. It
is a very competitive but also collaborative environment. In fact, to me, it is analogous to soccer.
Of course, apparently everything looks like soccer
to me, so that is not surprising. Think of AAAI as asoccer team. Keep your eye on the ball, know whatgame is going on, and know what the competition
is doing. We constitute the premier AI membershipsociety on the planet. I say this with pride. It is
healthy; we have great involvement from our community. We see at our conferences the excitement
generated by all the different events, competitions,and papers, and participant interaction.
AAAI is actually changing AI, and that is what
we should be doing through all our activities
including the workshops and symposia. And weare. But the world is also changing; in fact, AI haschanged in a way that maybe we have not recognized as a society. AI does now have a level of scientific and engineering maturity. In some of ourearly days we rather pushed aside control theory
and pushed aside pattern recognition and the like.

We insisted we were doing “important symbolicwork” and dismissed other aspects of work that we
now value. We have to change that attitude, andwe have to change it in our society and in our field.
We are now doing so more and more. Now werejoice in a new AI. We recognize that uncertainty
is critically important thanks to Peter Cheeseman(1985), Judea Pearl (1988), and many others, andwe are including fields such as statistics, machinelearning, pattern recognition, operations research,
control, neuroscience, and psychology and welcome them all. The beauty of the way we work as
a field is that we are problem focused not discipline
focused, so we do not have those disciplinary silo
traps to worry about. AI is now everywhere.
Globalization has hit us too. We came to realizethat although we called ourselves the American
Association for Artificial Intelligence, about onethird of our members are not American. About halfof the conference papers coming in and the attendees at our conferences are not American. Do they
feel welcome? Of course, for a Canadian president
to ask that question was a little tricky, but I was
assured by my American colleagues that it was a
critical question to ask. Thus, we decided to “go forit” to recognize the current reality. In proposing tochange the name of the society, we were anticipat-

SPRING 2009 25

Articles

ing a bit of a firestorm, which, happily, did not
happen. Certainly our membership, over 90 percent, was enthusiastically in favor of it, and, interestingly, many of the international societies werein favor of changing our name to the Association
for the Advancement of Artificial Intelligence,
which recognizes the current nature of our global
situation.
We still must remember we have three roles:
national, regional, and international. We have anational role; we have to represent our interests inscientific advancement in Washington and to bepart of the Computing Research Association looking at the science and engineering funding situation in the United States and in Canada; and we
also have both a regional role and, increasingly, aninternational role. We need to communicate better with our sibling AI and computer-science societies and push harder for global coordination.

Strategic Directions for AAAI
Given the rapid change in AI and in the environment for scientific research and global communications, this is an opportune time to reflect uponstrategic directions for AAAI. AAAI, until 2007, had
never had a formal strategic plan. Thus, the Strategic Planning Board and Council started a planning
process with a Strategic Planning Working Group
in 2007, which is now well underway. We need toconsider our vision, our mission, our values, andour goals as a scientific society. These goals include
supporting and facilitating the basic and appliedscience of AI, enabling and facilitating the practiceof AI, conducting outreach and advocacy, andbeing an agile and responsive professional society.
Some of the key issues that have arisen include
education for various audiences; communication
forums (conferences, workshops, symposia); open
access for publications, knowledge, and data;
ensuring we provide tangible member benefits;building community; exploiting media; and building collaborative linkages with other AI societies,
conferences, and journals.
We have done some good work in education
with AI Topics, led by Bruce Buchanan and Jon
Glick, but we could do more to encourage AI curriculum development. Clearly, AI is the most exciting field in computer science, but most undergraduate programs do not offer it until third year.
Perhaps we could help with enrollment and recruitment if we could make it more accessible earlier inthe curriculum. Recent AAAI meetings on AI andeducation are promoting and enabling this work.
Open access to publications is a problem andopportunity we do have to address. The publications access task force under president-electMartha Pollack is carefully considering theoptions, acknowledging that access to publications
is a significant benefit to our members. The AI Mag-

26

AI MAGAZINE

azine, guided by David Leake, does a wonderfuljob. New forms of publication, such as video on
the web, are now being actively encouraged. We
are also archiving and preserving historical AI
videos.
Finally, AAAI has a leadership role to play in theinternational AI community. In working cooperatively with all our sibling AI societies and conferences, we need more coordination and coherence,
internationally. Obviously, this must be done carefully, in a collegial fashion, but it must be done.

How Can We Help?
As I contemplated what I wished to address in concluding, I realized I wanted to touch upon a few of
my more personal thoughts. AI is now mature,both as a science and in its technologies and applications as an engineering discipline. There arethemes of AI in service to people and to our planet; themes that we should explore. We no longer
have the luxury of ignoring the global crises ofglobal warming, poverty, food production, sustainability, arms control, health, education, theaging population, and demographic issues. We dohave a unique perspective and the skills to contribute practically to addressing many of these concerns. There is an opportunity to join with people
who are already dealing with these issues, not inan arrogant way but collaboratively. We could, as
an example, improve access to tools for learning
about AI so that people could be empowered to try
our techniques on their problems. We know wecannot go in as experts telling people how to solve
their problems, but we can make tools available sothat someone already knowledgeable in a domain
might realize that machine learning, say, offers
radically new and potentially better approaches toa problem. The success of RoboCup and othergames and competitions shows how effective they
can be as learning and teaching environments. The
One Laptop Per Child (OLPC) initiative has alreadymade enormous strides; we could be supporting
this more actively. Clearly, there is ample room for
imaginative thinking in this area.
There are many opportunities for AI to have apositive impact upon the planet’s environment. It
is tremendously encouraging that work for betterment has already been done or is being contemplated. We have already considered some of theenvironmental impact of intelligent cars and smart
traffic control. All the work on combinatorial auctions, already applied to spectrum allocation andlogistics, could be further applied to optimizing
energy supply and demand and to carbon offsets.
There could be much more work on smart energy
controllers with distributed sensors and actuatorsthat would improve energy use in buildings. We
could perhaps use qualitative modeling techniques
for climate scenario modeling.

Articles

Finally, assistive technology for the disabled andaging is being pioneered by researchers such as
Martha Pollack (2005) and Henry Kautz (Liu et al.
2006). We need to listen very carefully to what
they are telling us. There is a huge opportunity forus, an opportunity that is extremely attractive tograduate students. One issue, which has been mentioned earlier, is the progress-hindering question of
liability, which can be, and must be, addressed.
Assisted cognition is one application, but work isalso proceeding in assisted perception and assisted
action, for example, in the form of smart wheelchairs and companions for the elderly and nurses’
assistants in long-term care facilities, following thelead of Alex Mihailidis and Jesse Hoey (Mihailidis
et al. 2007). All of the research topics mentioned
will, of course, have many obstacles to overcome.
It is an exciting time to do research in AI and its
applications. Perhaps some of these will serve as
challenges to our younger, and not so young,researchers.

Conclusion
To recap, I have sketched the evolution of constraint satisfaction, of agents, of models of agents,of AI, and of AAAI. Given the scope of those topics, this sketch has necessarily been idiosyncratic,
personal, and incomplete. However, I hope to havepersuaded you of the thesis that constraint satisfaction is central to intelligent behavior.

Acknowledgements
I am most grateful to all of the students, colleagues,
and collaborators who have contributed to some of
the work mentioned here: Saleema Amershi, Rod
Barman, Le Chang, Cristina Conati, Giuseppe
Carenini, Pooyan Fazli, Gene Freuder, Joel Friedman, Stewart Kingdon, Jaçek Kisynski, Byron
Knoll, Jim Little, David Lowe, Valerie McRae, Jefferson Montgomery, Pinar Muyan-Özçelik, Dinesh
Pai, David Poole, Michael Sahota, Fengguang Song,
Robert St-Aubin, Pooja Viswanathan, Bob Woodham, Suling Yang, Ying Zhang, and Yu Zhang. The
support of Carol Hamilton and all her staff made iteasier to serve as AAAI president. David Leakehelped with this article. I am also grateful to those
who served on the AAAI Council and on the Executive Committee and all the other volunteers whomake AAAI special. Funding was provided by the
Natural Sciences and Engineering Research Council of Canada and through the support of theCanada Research Chair in Artificial Intelligence.

Notes
1. AIspace (formerly known as CIspace) is an environment for learning and teaching AI featuring animationsof many AI algorithms (Amershi et al. 2008, Knoll et al.
2008). The AIspace site is at www.AIspace.org.
2. William Shakespeare, Hamlet, Act 1.

3. www.cs.ubc.ca/~mack/RobotSoccer.htm.
4. www.cs.ubc.ca/~mack/RobotSoccer.htm.
5. www.fira.net/soccer/mirosot/overview.html.
6. www.tartanracing.org, cs.stanford.edu/group/roadrunner.

References
Albus, J. S. 1981. Brains, Behavior and Robotics. New York:
McGraw-Hill.
Amershi, S.; Carenini, G.; Conati, C.; Mackworth, A. K.;
and Poole, D. L. 2008. Pedagogy and Usability in Interactive Algorithm Visualizations: Designing and Evaluating CIspace. Interacting with Computers, 20(1): 64–96.
Anderson, M., and Anderson, S. L. 2007. Machine Ethics:
Creating an Ethical Intelligent Agent. AI Magazine, 28(4):15–26.
Asimov, I. 1950. I, Robot. New York: Gnome Press.
Brooks, R. A. 1986. A Robust Layered Control System fora Mobile Robot. IEEE Journal of Robotics and Automation
RA-2(1): 14–23.
Brooks, R. A. 1991. Intelligence without Reason. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, 569–595. San Mateo, CA: Morgan Kaufmann.
Capek, K. 1923. R.U.R. (Rossum’s Universal Robots): A Fantastic Melodrama in Three Acts and an Epilogue. Garden
City, NY: Doubleday.
Cheeseman, P. 1985. In Defense of Probability. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, 1002–1009. San Mateo, CA: Morgan
Kaufmann.
Dresner, K., and Stone, P. 2008. A Multiagent Approach toAutonomous Intersection Management. Journal of Artificial Intelligence Research 31: 591–656.
Feuerbach, L. A. 1854. The Essence of Christianity. London:
John Chapman.
Freuder, E. C., and Mackworth, A. K. 2006. Constraint
Satisfaction: An Emerging Paradigm. In Handbook of Constraint Programming, ed. F. Rossi, P. van Beek, and T.
Walsh, 13–28. Amsterdam: Elsevier.
Haugeland, J. 1985. Artificial Intelligence: The Very Idea.
Cambridge, MA: The MIT Press.
Hsu, F. 2002. Behind Deep Blue: Building the Computer That
Defeated the World Chess Champion. Princeton, NJ: Princeton University Press.
Kitano, H., ed. 1998. RoboCup-97: Robot Soccer World Cup
I. Lecture Notes in Computer Science 1395. Heidelberg:
Springer.
Knoll, B.; Kisynski, J.; Carenini, G.; Conati, C.; Mackworth, A. K.; Poole, D. L. 2008. AIspace: Interactive Tools
for Learning Artificial Intelligence. In Proceedings of the
AAAI AI Education Colloquium. Technical Report WS-0802, Menlo Park, CA: AAAI Press.
Lashley, K. S. 1951. The Problem of Serial Order in Behavior. In Cerebral Mechanisms in Behavior, ed. L. A. Jeffress,
112–136. New York: Wiley.
Lennon, J. 1980. Beautiful Boy (Darling Boy). Song lyrics.
On album Double Fantasy. New York: Geffen Records.
Liu, A. L.; Hile, H.; Kautz, H.; Borriello, G.; Brown, P. A.;
Harniss, M.; and Johnson, K. 2006. Indoor Wayfinding:
Developing a Functional Interface for Individuals withSPRING 2009 27

Articles
tems (IROS 2004), 1807–1814. Los Alamitos, CA: IEEE
Computer Society.

 &   ' (   !              

     

    

     !  !   !               "  !    #      !
     
 ! !             !                   $   ! # 
    $%    !    "

 

Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems:
Networks of Plausible Inference. San Francisco, CA: Morgan
Kaufmann.
Pollack, M. E. 2005. Intelligent Technology for an Aging
Population: The Use of AI to Assist Elders with Cognitive
Impairment. AI Magazine 26(2): 9–24.
Reiter, R. 1978. On Closed World Data Bases. In Logic andData Bases, eds. H. Gallaire and J. Minker, 119–140. New
York: Plenum.
Rossi, F.; van Beek, P.; and Walsh, T., eds. 2006. Handbookof Constraint Programming. Amsterdam: Elsevier Science.
Sahota, M., and Mackworth, A. K. 1994. Can Situated
Robots Play Soccer? In Proceedings of Artificial Intelligence’94, 249–254. Toronto, ON: Canadian Society for Computational Studies of Intelligence.
Shelley, M. W. 1818. Frankenstein; or, The Modern
Prometheus. London: Lackington, Hughes, Harding,
Mavor, and Jones.
Somerville. M. 2006. The Ethical Imagination: Journeys ofthe Human Spirit. Toronto: House of Anansi Press.
St-Aubin, R.; Friedman, J.; and Mackworth, A. K. 2006. A
Formal Mathematical Framework for Modeling Probabilistic Hybrid Systems. Annals of Mathematics and Artificial Intelligence 37(3–4): 397–425.
Thrun, S. 2006. Winning the DARPA Grand Challenge.
Invited Talk presented at the Innovative Applications ofArtificial Intelligence conference (IAAI-06), Boston, Massachusetts, July 16–20.

Cognitive Impairments. In Proceedings of the 8th International ACM SIGACCESS Conference on Computers and Accessibility, 95–102. New York: Association for Computing
Machinery.
McLuhan, M. 1964. Understanding Media: The Extensionsof Man. New York: New American Library.
Mackworth, A. K. 1977. Consistency in Networks of Relations. Artificial Intelligence 8(1): 99–118.
Mackworth, A. K. 1993. On Seeing Robots. In Computer
Vision: Systems, Theory and Applications, eds. A. Basu and
X. Li, 1–13. Singapore: World Scientific Press.
Mackworth, A. K., and Zhang, Y. 2003. A Formal
Approach to Agent Design: An Overview of ConstraintBased Agents. Constraints 8(3): 229–242.
Maxwell, J. C. 1868. On Governors. In Proceedings of the Royal Society of London, 16, 270–283. London: Royal Society.
Mihailidis, A.; Boger, J.; Candido, M.; and Hoey, J. 2007.
The Use of an Intelligent Prompting System for People
with Dementia. ACM Interactions 14(4): 34–37.
Miller, G. A.; Galantner, E.; and Pribram, K. H. 1960. Plans
and the Structure of Behavior. New York: Holt, Rinehart,
and Winston.
Mori, M. 1982. The Buddha in the Robot. Tokyo: Charles E.
Tuttle Co.
Muyan-Özçelik, P., and Mackworth, A. K. 2004. Situated
Robot Design with Prioritized Constraints. In Proceedingsof the International Conference on Intelligent Robots and Sys-

28

AI MAGAZINE

Visser, U., and Burkhard, H.-D. 2007. RoboCup: 10 Yearsof Achievements and Challenges. AI Magazine 28(2): 115–
130.
Waltz, D. L. 1975. Understanding Line Drawingsof Scenes with Shadows. In The Psychology of Computer Vision, ed. P. H. Winston, 19–92. New York:
McGraw-Hill.
Zhang, Y., and Mackworth, A. K. 1993. Constraint Programming in Constraint Nets. In Proceedings of the First
Workshop on Principles and Practice of Constraint Programming, 303–312. Padua: Association for Constraint Programming.
Zhang, Y., and Mackworth, A. K. 1995. Constraint Nets:
A Semantic Model for Dynamic Systems. Theoretical Computer Science 138: 211–239.
Alan K. Mackworth is a professor of computer science,
Canada Research Chair in Artificial Intelligence, and thefounding director of the Laboratory for Computational
Intelligence at the University of British Columbia. He
received a B.A.Sc. (Toronto, 1966), A.M. (Harvard, 1967),
and D.Phil. (Sussex, 1974). He has worked primarily on
constraint-based artificial intelligence with applications
in vision, constraint satisfaction, robot soccer, and constraint-based agents. He has served as chair of the IJCAIBoard of Trustees and as president of the Canadian Society for Computational Studies of Intelligence and the
Association for the Advancement of Artificial Intelligence(AAAI); he is now past-president of AAAI.