Thesis
Thesis
Thesis
Environments
By
Hüseyin Sevay
This dissertation studies how we can build a multiagent system that can learn to
that agents do not explicitly communicate and operate autonomously only with their
local view of the world. Designing multiagent systems for real-world applications is
challenging because of the prohibitively large state and action spaces. Dynamic changes
in an environment require reactive responses, and the complexity and the uncertainty
inherent in real settings require that individual agents keep their commitment to achieving
common goals despite adversities. Therefore, a balance between reaction and reasoning
methodologies are severely limited since they cannot learn alternative strategies, which
are essential for dealing with highly dynamic, complex, and uncertain environments
problem solving in order to take advantage of the strengths of both. We use symbolic plans
that define the requirements for what individual agents in a collaborative group need to
do to achieve multi-step goals that span through time, but, initially, they do not specify
how to implement these goals in each given situation. During training, agents acquire
application knowledge using case-based learning, and, using this training knowledge,
agents apply plans in realistic settings. During application, they use a naı̈ve form of
reinforcement learning to allow them to make increasingly better decisions about which
specific implementation to select for each situation. Experimentally, we show that, as the
complexity of plans increases, the version of our system with naı̈ve reinforcement learning
performs increasingly better than the version that retrieves and applies unreinforced
training knowledge and the version that reacts to dynamic changes using search.
i
Acknowledgments
This dissertation would not have been possible without the guidance and support of
my advisor, Prof. Costas Tsatsoulis. I deeply thank him. My mother and father believed
in me as long as I know myself. I thank my sister and her family. They have been a great
source of inspiration for me. I am grateful for the support of my entire extended family.
My aunts, uncles, and cousins have lent their support to me for more than a decade and
a half. During my stay at the University of Kansas, which became my home away from
home, I have been fortunate to have many wonderful friends. I thank them all from the
bottom of my heart. I shared so much with them that is so hard to put in words. I thank
my professors who have encouraged me during my long journey. I also thank the ITTC
staff. I am very grateful for all the support I received from them over the years.
ii
Dedicated to my mother and father . . .
iii
Contents
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Background 11
2.3.3 Soar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.4 BURIDAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.2 Pengi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.2 AuRA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
iv
2.6.1 Practical Reasoning, BDI, and PRS . . . . . . . . . . . . . . . . . . . . 27
2.6.2 Cypress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6.3 ATLANTIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.6.4 IRMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.5 InteRRAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6.6 TouringMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.8 Realtime AI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3 Methodology 67
3.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
v
3.3.8 Hierarchical Representation of State Spaces . . . . . . . . . . . . . . . 100
4 Implementation 131
vi
5.3.2 Givengo Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6 Conclusions 167
Bibliography 174
Appendices 194
vii
List of Figures
2.1 The soccer field and fixed reference markers in the simulator environment . 59
2.2 Neck angle, body angle, and direction conventions for clockwise and
counterclockwise angles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.4 Soccer Server field coordinate conventions for left and right teams . . . . . . 64
3.8 An example plan for a three-player plan from the soccer domain where each
player needs to check conditions specific for its own role in that plan . . . . 91
3.9 The dynamic decomposition of each reactive action module (RAM) into a
3.12 Hierarchical relationship between internal and external conditions that describe
3.13 An example grid laid over a region with two teams of agents . . . . . . . . . 103
viii
3.15 Two example testing scenario for training on a threeway-pass plan . . . . . 122
4.6 Main operation cycle and basic process cycle of a player agent . . . . . . . . 143
5.1 Learning experiments using the Centerpass plan. The last success rate value
and the number of opponent players used is indicated on each graph . . . . 152
5.2 Learning experiments using the Givengo plan. The last success rate value
and the number of opponent players used is indicated on each graph . . . . 156
5.3 Learning experiments using the Singlepass plan. The last success rate value
and the number of opponent players used is indicated on each graph . . . . 158
5.4 Learning experiments using the UEFA Fourwaypass plan. The last success
rate value and the number of opponent players used is indicated on each
graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
C.1 Timing of visual feedback messages sent by the server with respect to action
cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
C.2 A possible synchronization process of the client with the server . . . . . . . 213
D.2 4I1 AB from Figure D.1 with height h, d = b + a, |BM| = b and |MA| = a . . 217
ix
D.3 An example case of triangulation where the known reference points and the
D.4 Computation of base line segments in a triangle when height is zero . . . . 221
x
List of Tables
5.1 Number of trials used during training for each plan for all 5 opponent
scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
5.2 Number of cases acquired for each role in each step of the Centerpass plan
5.3 Number of cases acquired for each role in each step of the Givengo plan
5.4 Number of cases acquired for each role in each step of the Singlepass plan
5.5 Number of cases acquired for each role in each step of the UEFA Fourwaypass
5.7 The mean and standard deviation of the last 100 values from the Centerpass
5.8 Paired t-test results for comparing Centerpass plan experiments run in RL,
xi
5.9 Paired t-test results for comparing the performance of RL, Retrieval, and
5.11 The mean and standard deviation of the last 100 values from the Givengo
5.12 Paired t-test results for comparing Givengo plan experiments run in RL,
5.13 Paired t-test results for comparing the performance of RL, Retrieval, and
5.15 The mean and standard deviation of the last 100 values from the Singlepass
5.16 Paired t-test results for comparing Singlepass plan experiments run in RL,
5.17 Paired t-test results for comparing the performance of RL, Retrieval, and
5.19 The mean and standard deviation of the last 100 values from the UEFA
5.20 Paired t-test results for comparing UEFA Fourwaypass plan experiments
5.21 Paired t-test results for comparing the performance of RL, Retrieval, and
Search modes in each opponent experiment in the UEFA Fourwaypass plan 162
5.22 Number of cases acquired for each role in each step of the Givengo plan
xii
5.23 Number of cases acquired for each role in each step of the Singlepass plan
5.24 Number of cases acquired for each role in each step of the UEFA Fourwaypass
5.25 Summary of retrieval tests for three of the plans that learned more than one
C.1 Mapping of all possible visual feedback message times in a 300ms period
C.2 The visual feedback time offsets from the beginning of an action cycle and
C.3 Actual visual feedback time offsets from the beginning of each action cycle . 214
xiii
List of Algorithms
xiv
Chapter 1
Introduction
highly dynamic, and uncertain environments from the perspective of how a group of
autonomous agents can learn to apply high-level reactive multiagent plans to achieve
shared goals in situated scenarios. Due to the distribution of control and reasoning,
the multiagent systems (MAS) approach in Artificial Intelligence (AI) is well-suited for
solving problems in such complex domains, and this distribution enables agents to react
to dynamic external events as they collaborate to attain their long-term team goals.
major challenges. First, since complex environments with continuous states and actions
have very large search spaces, at the single agent level, the solution methodology must
address the problem of how to reduce these large search spaces. At the team level, it must
address the problem of how to enable autonomous agents to collaborate efficiently and
coherently. Second, the solution methodology must enable agents operating in real-world
domains to handle the noise inherent in their sensors and actuators and the uncertainty in
the environment.
In agent-based systems, solutions are built upon the basic action capabilities of
In this dissertation, we refer to the data structures that implement high-level strategies as
1
plans. In a complex environment, a team of agents may need a set of such plans to achieve
their long-term goals. To be reactive to dynamic changes, a team must also be capable
The question then becomes: How can we build a multiagent system that can execute
high-level strategies in complex, dynamic, and uncertain domains? We may consider three
possible answers to this question. First, we can build a system that successively executes
plans chosen from a static library. Second, we can build a system that can learn
its strategies from scratch. Third, we can describe the strategies symbolically at an
implementation-independent level and have the system learn how to implement the
Most work in the multiagent learning literature has treated the challenge of building
that emerges from an incrementally modified sequential decision memory over many
convergence to provide stable policies, and, by their nature, they do not bound the search
problem beyond rewarding every decision according to its perceived value since they
intend to discover policies. Moreover, they suffer from the exponential growth of the
search space as a factor of the size of the input vector. Therefore, scaling bottom-up
learning approaches to large search spaces is a very difficult problem. On the other hand,
we hypothesize that top-down approaches can constrain the search space, resulting in a
dynamic, and uncertain environments not from the perspective of learning of strategies
but from the perspective of having each member of a team learn how to fulfill its part in
given high-level plans. We assume that users can provide high-level symbolic descriptions
2
describe what needs to be done from each contributing agent’s perspective in order to
it is decomposed into an ordered list of steps each of which may require the collaboration
of multiple agents to implement its goal. A plan step, in turn, defines a specific role for
each collaborating agent. A role describes the necessary conditions for executing and
terminating the responsibilities of each given agent from that agent’s local perspective
of the world. Since the sequence of actions required for each situation can vary, before
any learning takes place, a plan step does not contain any implementation-specific details
about what actions each collaborating agent needs to take to perform its own task in that
plan step. Therefore, at the outset, a plan is only a high-level specification of a strategy
Unlike systems that learn policies directly from experience in a bottom-up fashion, our
system does not learn plans or policies. Instead, high-level plan descriptions constrain the
search and each agent autonomously learns action knowledge in this focused search space
from its own perspective of the environment. In our approach, learning is done using a
uses case-based learning to operationalize its role in each step of a plan. It then uses a naı̈ve
form of reinforcement learning to decide which plan to pick for a situation and then to
decide which specific implementation of a plan step to activate to implement the current
plan step successfully in the current context. The case-based learning component helps to
deal with noise in matching situations to implementations, and the naı̈ve reinforcement
learning helps with the uncertainty in the environment, enabling the agents to choose
acquires action knowledge that enables it to adapt its role to specific situations. By
applying plans in regular situations, the agent collects reinforcements based on the success
and failure of its learned action knowledge. This reinforcement knowledge allows the
agent to make progressively better choices about which plans to use and which plan
3
implementations to execute.
robotic soccer environment [Kitano et al., 1997a,b; Chen et al., 2002]. We describe the
1.1 Motivation
Most existing multiagent learning systems that operate in complex, dynamic, and uncertain
environments use reinforcement learning techniques where a policy or plan emerges from
the interactions of the agents with the environment and the interactions of agents among
themselves (e.g., [Stone and Veloso, 1999; Matarić, 1996]). Due to their bottom-up nature,
these systems are difficult to scale up to larger and more complex problems [Stone and
Sutton, 2001]. They are also naturally not conducive to learning multiple distinct high-
level strategies [Matarić, 1991], since they depend on practical convergence to provide
coherent behavior for the policy they are trained for. Instead of depending on emergence to
bring out a successful policy, we believe that constraining the multiagent learning problem
in a top-down fashion using symbolic plans and formulating the solution as one of reactive
plan application learning has certain advantages over purely bottom-up policy learning
approaches.
In a domain where humans possess expertise, it may be beneficial to involve the expert
user in the solution process [Myers, 1996, 1997]. The user charts a number of symbolic
high-level plans, and then the system learns the details of when and how to apply each
given plan, since manually specifying all the necessary details for all possible scenarios
would be a very arduous task. This approach would be in contrast with systems that
discover their own policies within the context of less constrained learning problems as
in RL. In addition, a symbolic approach allows for the explicit decomposition of a large
task into manageable steps, since a multiagent strategy is usually composed of a series of
actions by several agents. This breakdown, in turn, reduces the search space. Moreover,
conditions for success and termination of each step can also be specified explicitly, such
4
that a system can determine when a strategy step is completed and when it should be
terminated.
Domains with continuous search spaces pose a difficult challenge for learning [Stone
and Sutton, 2001; Smart and Kaelbling, 2000]. Even though a subset of the problem can
have a manageable search space with a relatively small number of agents in the case
of MAS, adding more agents into the problem tends to render the solution approach
ineffective. This is, for example, true of Reinforcement Learning (RL) approaches, which
assume discrete state and action spaces [Stone and Sutton, 2001; Sutton, 1996; Merke and
Riedmiller, 2002].
and Sutton, 2001; Smart and Kaelbling, 2000] or uses the domain features without
spaces. Even with discretization, there are no multiagent learning algorithms with
provable convergence that can learn a single, all-encompassing team strategy in the kind
constrained group strategies rather than learning strategies that would cover all agent
required for deciding when to activate which individually-learned strategy and when to
The solution to this problem would be to have the system learn under what conditions
to apply as well as terminate each multiagent strategy so that the multiagent system
can automatically switch between behaviors. But that learning problem could prove as
difficult as the problem of learning a multiagent strategy for a relatively large team of
agents due to the exponential growth of the search spaces. Systems that could learn
a single multiagent strategy have already been reported in the literature [Whiteson and
Stone, 2003; Stone and Sutton, 2001; Kostiadis and Hu, 2001], but the problem of learning
5
a single team strategy that covers all agent behavior still remains unsolved.
Symbolic learning techniques, however, do not suffer from the curse of dimensionality
to the same extent as do emergent learning techniques since a symbolic approach can
multiagent learning algorithm that could learn all necessary agent behavior for a dynamic
and complex domain without needing any high-level specification of what to do, then
there would be no need for explicit programming of plans or strategies. Even if the training
phase took a relatively long time, having an automated learning system that can cover an
entire domain would clearly be of great advantage. However, the state of the art has not
defined boundaries where preconditions and termination conditions of each strategy are
explicitly known. The tradeoff is then the explicit representation that would be required
choosing and terminating roles in multiagent strategies during the lifetime of each agent
in a team.
Most closely related research in the literature uses either a bottom-up learning
approach [Parker and Blumenthal, 2002; Stone and Veloso, 1999; Werger, 1999; Luke
et al., 1998; Luke, 1998; Balch, 1997b; Matarić, 1996] or does not address the problem of
1.2 Approach
We based our learning approach on the idea of learning by doing [Anzai and Simon,
1979], that is, learning from practice, and we established the benefits of our solution
Soccer simulated robotic soccer environment [Kitano et al., 1997a,b, 1995]. The soccer
6
game provides a very rich multiagent environment that is both dynamic, complex, and
uncertain.
Agents in the RoboCup simulated soccer environment are capable of only basic actions
provides a complex environment where player sensors and actuators are noisy. It also
agent can communicate using explicit messaging and how much bandwidth each message
can use. Hence, these properties give rise to a realistic multiagent environment that is
highly dynamic and unpredictable. Besides individual moves, soccer naturally requires
collaborative behaviors involving multiple agents, and, for these behaviors to succeed,
provided by the simulator. This hierarchical approach is akin to the layered learning in
[Stone and Veloso, 1999; Stone, 1998], which used machine learning techniques.
To facilitate plan oriented multiagent behaviors, we divide each plan into steps. Each
step specifies the roles that must be dynamically filled by agents at runtime. In a given
scenario, each agent chooses the plan that best matches that scenario, and, subsequently,
that agent assigns all agents involved in that scenario, including itself, their roles, and
these roles remain fixed until the plan application terminates either with success or failure.
However, each agent carries out its role assignments independently and does not share
them with other agents it intends to collaborate with. Each agent has its own plans, and it
selects which plan to execute and which role to take on in that plan autonomously.
Our learning approach is divided into training and application phases. Agents learn
in both phases, but they acquire different types of knowledge in each phase. In the
training phase an agent uses case-based learning to implement its role in a given plan
step under the current scenario. This knowledge we call the application knowledge contains
the sequence of actions the agent needs to execute in order to achieve the goal in the
current step and under the conditions in which it is being trained. To determine this
7
sequence of actions, an agent takes a snapshot of its current local environment and does a
search in this environment according to the description in the current plan step. Although
the scenario given to the search process is temporally static and cannot make accurate
predictions of future states, the later application phase helps determine if the sequence of
actions suggested by this local search will be useful. Since one implementation may not be
In the application phase the agent selects and executes plans in collaboration with
other agents in its group. As it applies plans to the current environment, each agent
positively reinforces plans that succeed and negatively reinforces plans that fail. In each
plan step, the agent positively reinforces cases that implement the current step successfully
and negatively reinforces cases that fail to achieve the goal of that step. By continuous
reinforcement, agents refine their selection of plans and plan step implementations.
Another feature of our approach is that we separate conditions external to the team
from the conditions internal to it. Conditions external to a team are those the team does
not have any direct control over, and conditions internal to the team are those the team
can potentially control. At the least, each agent can affect its own state via its actions to
affect the team internal state. To match plans to scenarios, we only use the conditions that
are internal to the team. Then, to distinguish the finer details of each situation, we use the
conditions external to the team to index each piece of application knowledge associated
During training, agents act in their regular operating environment as they do during
the application phase, except that the training environment is more controlled to allow
agents to acquire application knowledge. During the application phase, each agent
chooses an uninstantiated plan, assumes a role for itself and deduces roles for other team
members. Then it attempts to apply its responsibilities arising from its chosen role to
completion in each plan step. Coherence in the multiagent behavior comes from the
reinforcement of plans and plan parts as well as the definition of each role in each given
plan.
8
combined with a naı̈ve reinforcement method to implement reactive plan application
learning in complex, dynamic, and uncertain environments. We show that our learning
methodology improves the behavior of a team of agents in the case of each plan.
1.3 Contributions
This dissertation makes several contributions to the field of Artificial Intelligence (AI),
• An agent architecture that enables reactive and collaborative strategy selection and
cases.
• A method for physical domain situation matching for testing the applicability of plan
9
1.4 Dissertation Outline
• Chapter 5 (Experimental Results and Discussion) presents and discusses the results
• Chapter 6 (Conclusions) presents the conclusions of our work and suggests possible
10
Chapter 2
Background
work on shared goals by learning how to apply high-level multiagent plans in dynamic,
complex, and uncertain environments. Dealing with such environments requires that
agents have reactive behavior, and the goal-oriented nature of plans requires that agents be
capable of accomplishing their long-term goals in the presence of challenges posed by the
for recognizing situations to which each agent in a cooperative group knows how to react
Since this document focuses on learning in dynamic, complex, and uncertain multiagent
evolved to this day. Then we present issues and work relevant to our research.
The field of Artificial Intelligence (AI) was born out of the motivation for creating general-
purpose problem solvers that would exhibit some characteristics of human problem
solving. In late 1950’s, Allen Newell and Herbert Simon proposed the General Problem
Solver (GPS), which introduced the seminal ideas of means-ends analysis and difference-
finding between non-goal states and a goal state as fundamental to their approach to
11
At the tenth ACM Turing Award Lecture in October 1975, Newell and Simon described
their general approach formulated as the Physical Symbol System Hypothesis, which stated
that “[a] physical symbol system has the necessary and sufficient means for intelligent
action.” The physical symbol system hypothesis provided for symbols that could be
arranged into expressions and a set of processes that operated on these symbol structures
to produce other expressions in the course of solving problems [Newell and Simon, 1976].
Starting with these core ideas, AI took root as a research field, and, by early 1970s, new
successively transforming its world model by applying operators defined in terms of their
[Fikes and Nilsson, 1971]. This approach to specifying operators in terms of preconditions
and postconditions set a lasting standard, and STRIPS, as a complete system, motivated
much of the subsequent work in planning and problem-solving. Its assumptions and
of at the level of state descriptions. Even though ABSTRIPS used the same operator
some preconditions as more critical than others during planning. So by treating each
precondition in the order of its criticality to a problem, it successively refined its plan after
linear planning. It used critics that added constraints to plans during planning to
eliminate redundant operations and to order actions to avoid subgoal interactions. NOAH
used procedural nets to define plans as a partially-ordered network of actions, and this
hierarchical description of actions enabled NOAH to focus on the relevant parts of the
problem. However, NOAH did not do any backtracking, and this limited the type of
problems it could solve. NONLIN extended the non-linear planning ideas of NOAH
12
a domain.
posting uses constraints to represent subproblem interactions explicitly [Stefik, 1981], and
this technique has since become commonplace in AI planning. Planners such as SIPE
[Wilkins, 1984] and DEVISER [Vere, 1983] incorporated limits on resources as part of
planning and reasoned about them. DEVISER provided for the specification of time
limits on goals and other activities so that the planner could reason about the time
windows within which goals had to be achieved and how long certain conditions should
be preserved [Vere, 1983]. SIPE also incorporated replanning in response to plan failures.
skeletal plans applied in contexts similar to that of the new planning problem and then
modifying the retrieved solution instead of planning a solution from scratch [Hammond,
1989, 1986]. The PRIAR system integrated the case-based planning approach with
The Procedural Reasoning System (PRS) reasoned about problems in terms of the
beliefs, desires, and intentions of the planner. Its primary goal was to integrate goal-
directed planning with reactive planning to provide highly reactive behavior and yet goal-
a hybrid approach by interleaving planning and execution [Georgeff and Lansky, 1987].
In the 1980s, the realization that traditional AI planning approaches may not be well-
suited for practical applications led to the development of reactive systems [Brooks, 1986;
Firby, 1987; Agre and Chapman, 1987]. Some researchers went as far as to question the
validity of the physical symbol hypothesis [Brooks, 1986] on which almost all work on AI
was based. They suggested that intelligent behavior could be generated without requiring
explicit symbolic representation and done so without the abstract reasoning of traditional
AI systems, and that intelligence was an emergent property of complex systems driven
by the interactions of problem solvers with their environments [Brooks, 1986, 1989, 1991].
This new wave of research has paved the way for AI systems that increasingly took into
13
A large body of work sought to build upon the fundamental ideas in AI as the interest
in the research community progressively shifted towards realistic domains. From the
perspective of this dissertation, we can identify two major trends in the literature. First, the
interest in creating modular solutions led to distributed problem solving (DPS) approaches
in AI, exemplified by Blackboard systems and the Contract Net Protocol. Closely related
to DPS, a new body of work also emerged in the form of multiagent systems, which, in
general, deals with enabling a number of autonomous agents to solve problems that are
difficult or inefficient to solve using single-agents alone [Bond and Gasser, 1988; Chaib-
draa et al., 1992; Durfee and Rosenschein, 1994]. Second, moving away from toy problems
Steel, 1988; Wilkins, 1984]. It became apparent that, to cope with the complexities of real-
world environments, AI systems needed to be reactive to cope with dynamic changes and
that interleave planning with execution strive for timely responses rather than solution
optimality. After all, in dynamic, complex, and uncertain environments, defining what is
Early AI work had concentrated on centralized, single-agent solutions, but later work
looked for ways to distribute computing and control to multiple agents. In addition, the
type of domains considered included more realistic domains that involved multiple agents
instead of a single agent, and complex, dynamic, and uncertain worlds instead of static,
predictable worlds.
Particularly, the assumption known as the “STRIPS assumption,” which held that the
world will change only in ways defined by the postconditions of the operator that is
being applied to the current world model, no longer held in dynamic environments. In
a dynamic and complex environment, it is difficult for an agent to know exactly how
14
the world will change as a result of its actions. Moreover, when there are other agents
in an environment, it is no longer the case that only a single entity is capable of acting
to react to unexpected events caused by both the environment and other agents, while
managing to pursue its long-term goals in the face of the uncertainties and complexities of
that environment.
Unlike in traditional planning, the low-level actions of agents in real physical domains
are durative, and their effect is uncertain. Situated and embodied agents know about the
world through their sensors and affect changes in the world through their actuators, both
of which are imperfect and limited. Sensors provide noisy information about the changing
aspects of the world, and the information they provide is partial, hiding potentially
important aspects of the world from the agents, giving rise to the problem of hidden state.
Effectors are also noisy, and, therefore, they do not cause changes in the state of the world
in precisely the intended ways. Moreover, actions may fail to bring about the changes they
were executed for. For example, an object being detected at 10 meters may not necessarily
be at exactly 10 meters away, and a command for turning a robot 10 degrees may not
necessarily execute an exact 10-degree turn. And, if, for example, the robot fell in a ditch
and is stuck, attempting a turn to presumably avoid an object will not accomplish that
goal.
Dynamic real-world domains also require that problem solvers reason about resources
and the temporal nature of actions and changes while pursuing their goals by reacting and
deliberating in the presence of other collaborative agents. This means that agents need to
Therefore, learning can provide the means for adaptability in dynamic, complex, and
uncertain environments.
15
2.3 Deliberative Systems
Central to deliberative systems is reasoning about goals, the state of the world, and the
internal representations of the planner. Contrary to reactive systems, which map situations
to actions, deliberative systems generate plans to accomplish their goals. Therefore, the
main concern in deliberative systems is the time and space complexity of the algorithms
happens in response to the question of “What to do next?” [Hexmoor and Nute, 1992].
Traditional AI planning systems deal with this problem by choosing an entire sequence
of actions so that the initial state of the world can be transformed into the desired goal state
by they direct application of those actions (e.g., [Fikes and Nilsson, 1971; Sacerdoti, 1975;
Tate, 1977; Stefik, 1981; Wilkins, 1984; Erol et al., 1994]). Given a problem, these systems
generate a complete plan before executing any of the actions of that plan. This approach
• The agent that executes the primitive actions on the world state is the only entity that
• Lowest-level or primitive actions that will potentially cause changes in the world
• The effects of such primitive actions are deterministic. That is, an action only brings
Even with these assumptions in place, problem solving is still hard due to combinatorial
the size of the problem description [Tate et al., 1990; Georgeff, 1990] Therefore, the search
16
Search space reduction: Since the planning problem is NP-hard, we need ways to
reduce the search space complexity. One possible reduction method involves reformulating
the problem using abstractions so that not as many states need to be searched. Another
method is to use heuristics to control the search so that only a subset of the search space
Scalability: It is also desirable that the algorithm produce solutions that can be
efficiently computed in terms of time and space for problems of gradually increasing size
All of these challenges are common to both single-agent problem solving and multiagent
problem solving. In the case of multiagent systems, however, the inherent problem of
combinatorial explosion becomes more limiting for AI algorithms, since introducing a new
agent into the problem exponentially compounds complexities of existing state and action
Hierarchical Task Network (HTN) planning differs from STRIPS planning in the way it
denotes the desired change in the world. In HTN planning, STRIPS goal specification is
replaced by tasks and their associated task networks that specify how to accomplish those
tasks. This formulation of planning problems is a way to reduce search [Erol et al., 1994].
There are three types of tasks in HTN planning. Goal tasks are analogous to STRIPS
goals and represent properties that must be made true in the world. Primitive tasks can be
executed directly. Compound tasks are made up of a number of goal tasks and primitive
The input to an HTN planner consists of a task network that has been chosen to solve
a given problem, a set of operators, and a set of methods. State and operator representation
specifies the effects of applying a primitive action. A method represents how to perform
a non-primitive task with constraints and contains a set of preconditions and a totally-
17
ordered list of subtasks. The representation of states in HTN planning is also the same as
in STRIPS.
HTN planning works by expanding non-primitive tasks into successively more specific
subtasks using methods, eventually leading to primitive tasks before any execution can
take place. When there are no more non-primitive tasks left from the initial task network
to be expanded, the next step is to find a totally-ordered instantiation of all primitive tasks
that satisfies the constrains in the initial task network. If such an instantiation is possible,
then the resulting order of primitive actions is a solution to the original problem.
HTN planning also involves critics for handling functions such as task ordering
Even though task decomposition using hierarchical task networks facilitates an effective
Heuristic search planning (HSP) involves treating the planning problem as a heuristic
search problem. A heuristic search planner automatically extracts a heuristic function from
the STRIPS-style declarative problem representation, and it uses this heuristic function to
guide the search as in traditional heuristic search scenarios [Bonet and Geffner, 2001a;
Bonet et al., 1997]. The heuristic function is created by considering a relaxed version of the
problem, where delete lists are ignored, thereby assuming subgoal independence. Even
though this assumption is not valid in general, it was shown to be useful [Bonet and
Geffner, 2001a].
Since solving the relaxed version of the original problem is still hard [Bonet and
Geffner, 2001a], an approximation of the heuristic function is used, and the value of this
approximate function is updated until its values stabilizes. Since HSP uses a heuristic to
control search, it is a hill-climbing planner. At every step, one of the best of the children
is selected for expansion, ties are broken randomly, and this process is repeated until the
18
goal state is reached.
2.3.3 Soar
Soar is a general-purpose problem solver rooted in the Physical Symbol System Hypothesis
[Newell and Simon, 1976], and it is implemented as a specialized production system. Soar
represents all tasks in terms of heuristic search to achieve a goal in a problem space. A
problem space consists of the set of operators that are applicable to a state and the new
states that are generated by those operators. The long-term knowledge of Soar is encoded
knowledge about how to achieve goals [Newell, 1990; Rosenbloom et al., 1993].
At each problem-solving iteration, Soar fires all matching rules in parallel and applies
is not the case, an impasse occurs, since problem solving cannot continue. To resolve the
impasse, a subgoal is automatically created to get that knowledge. This automatic goal
knowledge about how Soar should behave in the current problem space, and it is created
by productions that add such data to the working memory of the production system.
The decision cycle of Soar contains two phases. In the elaboration phase, it fires all
Then, in the decision phase, Soar imposes control on search using the data generated by the
previous phase. In the second phase, Soar examines all generated preferences and makes
a final decision about what to do. As a result of its decision, Soar may apply an operator,
based learning method called chunking to cache its prior problem-solving experience as
generalized productions. When a decision cycle for a goal ends, a chunk is created to
19
summarize the processing required in solving a subgoal, so that similar problems in the
future can be solved more efficiently since no subgoaling will be needed [Newell, 1990;
2.3.4 BURIDAN
The BURIDAN family of planners follow a classical approach to planning but they
incorporate uncertainty [Kushmerick et al., 1994]. BURIDAN plans assume that sensors
and effectors can be faulty, and the agents can have incomplete information. This approach
uses Bayesian conditional probability theory to deal with uncertainty. Actions in this
successor state from a given state, BURIDAN associates a conditional probability to each
state that can be reached from a given state based on the current action. Besides this
probability specification, plans in this system are represented in the STRIPS style, with
Contrary to traditional planning systems that generate plans to transform the world state
into the desired goal state, purely reactive systems do not explicitly reason about long-
term goals and do not generate plans. A reactive system is composed of a set of actions
Instead of producing complete plans to solve a problem, reactive systems match actions
between behaviors when necessary. Therefore, ideally, the response time and behavior
switching time of a reactive system should not fall behind the changes in the environment
Another feature of reactive systems is that they do not have an explicit representation
of their policy, since they do not generate plans and keep minimal state information.
Rather, the sequence of actions a reactive system produces during its interaction with the
20
environment emerges as the policy encoded in the control framework of the system.
Since timely response is most critical to handle dynamic changes, optimality is not the
main issue in reactive systems. The goal is to produce “good-enough” solutions as quickly
as possible. So, even if allowing more computations to take place would produce a better
quality response for the situation at hand, the quality of the response must be traded off
with reaction time, since late responses may be of little or no value. Even though timely
response is critical in reactive systems, most well-known reactive systems do not have
In general, we can characterize a reactive system as one that does fast action selection.
A reactive system executes a reaction that matches the current situation, and it continues
to apply the same reaction until a change occurs in the environment that prompts the
system to match a different reaction to the new situation. Therefore, as part of its control
mechanism, a reactive system neither detects failures nor replans. However, in theory,
failure detection or replanning knowledge can be encoded in the reactive plans of the
system. Therefore, we can say that reactivity lies in the plans and not in the planning
The RAP system was designed for reactive execution of symbolic plans, and it works as
a reactive plan interpreter. In this system, a goal can be described in multiple levels of
abstraction. Then the RAP system tries to execute each level of abstraction while dealing
In the RAP system, a task is defined by a Reactive Action Package (RAP). A RAP is
a program that carries out a specific task in a context-sensitive fashion. So a RAP may
describe how to achieve a goal in different contexts. A RAP symbolically defines the goal
of a task and specific methods for achieving the goal of the task in different situations.
In each method, a RAP contains a context description to identify when that method is
applicable and a task net that describes the procedural steps to perform.
The RAP system executes its tasks by checking whether the selected task represents
21
a primitive action. If so, that task is executed directly. If the task is non-primitive, then
it looks up in its RAP library for a RAP that implements that non-primitive task. Then
it checks the goal success condition of the retrieved RAP. If the goal success condition is
satisfied, then the task is considered complete, and the system can run another task. If the
success condition is not yet satisfied, it checks the retrieved RAP’s method applicability
conditions and selects the method with the applicable context description. Then it queues
the subtasks of the chosen method for execution and suspends the task until its subtasks
are complete. When all of its subtasks are complete, the RAP system checks the success
condition of the suspended task. If the success condition is satisfied, then the system can
work on another task. If not, then it repeats the whole process by selecting another method
The RAP system also allows the representation of concurrent tasks. This involves
for representing multiple possible outcomes of each subtask so that the non-determinism
2.4.2 Pengi
Pengi [Agre and Chapman, 1987, 1989] is a reactive system that is based on the plan-as-
communication view of plan use, as opposed to the plan-as-program, which classical STRIPS
family of planners are based on. Pengi plays a video game called Pengo. In the plan-as-
communication view, plans do not determine what agents do. Instead, plans are resources
agents can use to decide what to do. Agre and Chapman believe that classical planning
approaches create agents that attempt to control their environment, where in their plan-as-
communication view of plan use, agents only participate in the environment but do not try
to control it. So, Pengi constantly uses contingencies and opportunities in its environment
to improvise its behavior for pursuing its goals. This kind of improvisation, however, only
indexical-functional representation that uniquely identifies entities in the world and their
22
function. Pengi also does not construct any plans or models of its environment. When
contingencies arise, Pengi aborts the routine it is executing and tries another action
repeatedly until it works or until it gets an opportunity to try a more promising action.
It interleaves different routines and uses its repertoire of actions in ways that may not be
In the situated automata approach of creating reactive agents, the operations of an agent
are described declaratively by the designer. Then the declarative specification is compiled
into a digital machine that can generate outputs with respect to its perceptions using its
internal state. Even though the agent is described symbolically, the generated machine
does not do any symbolic manipulations [Kaelbling, 1991; Rosenschein and Kaelbling,
1995]. Although reactive in its responses, agents created using situated automata do not
have the ability to adapt to their environment beyond their initial design capabilities.
1986], but they also share features with the purely reactive systems. A behavior-based
system has a collection of behaviors that it executes in parallel as each module gathers
information about the world through sensors. There is no reasoner or central control
in a behavior-based system, and the integration of the system is achieved through the
interactions of the behaviors among themselves and mostly through the environment.
Typical goals of behavior-based systems require both switching among behaviors as well
as maintaining behaviors, and the system can have state and other representations to
The behaviors of a behavior-based system are built bottom-up, starting with the most
essential basic behaviors such as obstacle avoidance and moving to a designated location.
Then more complex tasks are added keeping with the intended overall behavior of the
23
system. However, the more complex behaviors are not built in terms of simpler behaviors,
but they interact with the more basic behaviors to produce behaviors that no single
Since behavior-based systems are both situated and embodied, they are inherently
reactive in the sense that they produce timely responses to changes. However, behavior-
based systems are classified separately from reactive systems in general, since behavior-
based systems do not map a single action to a given situation but rather adjust the
interaction of multiple behaviors so that the combination of behaviors generates the more
complex behavior needed to implement the goal of the system [Matarić, 1992]. However,
Since behavior-based systems do not employ central control, selection of the appropriate
behavior for a situation requires arbitration among the available behavior modules. Well-
thresholds are used to trigger actions [Maes, 1989] and voting schemes [Payton et al., 1992].
The Subsumption Architecture is based on three principles: (1) that intelligent behavior
can be generated without using explicit representations of states and goals as done in
traditional symbolic AI systems; (2) that intelligent behavior can be created without high-
level reasoning; (3) that intelligence is only an emergent property of a complex system
that stems from its interactions with the environment and not from any preprogrammed
model of that environment. Embodiment refers to the agent operating in a real physical
One of the guiding principles of this architecture is that an intelligent system must
be built incrementally by building upon layers of what are themselves complete modules.
The Subsumption Architecture does not depend on a symbolic representation of the world
24
or any symbolic manipulation for reasoning. Brooks suggests that the world be used as
its own model, rather than building models in software. The claim is that there is no need
to explicitly represent the world or the intentions of an agent for that agent to generate
intelligent behavior.
The Subsumption Architecture is layered, where each layer contains a set of augmented
finite state machines (AFSMs) that run asynchronously. In addition to a regular finite
state machine, AFSMs contain registers and timers. Registers store the inputs arriving
into AFSMs and timers help the AFSMs change state after a designated amount of time
passes. There is no central control in the Subsumption Architecture because each AFSM is
driven by inputs it receives from the sensors or the outputs of other AFSMs. Perception
and, since the AFSMs are connected to each other through their inputs and outputs, this
exchange is viewed as message passing. The messages from other AFSMs are saved in
the (input) registers of an AFSM. The arrival of such messages or the expiration of the
timeout value of the timer internal to the AFSM prompts a state change. Each layer
AFSM are blocked for a predetermined duration. During inhibition, the output of an
AFSM is blocked for a predetermined period. The outputs of some of the AFSMs are
In an example given in [Brooks, 1991], a robot is made up of three layers, where the
lowest layer is responsible for avoiding obstacles, the middle layer is responsible for
wandering around, and the top layer is responsible for trying to explore by attempting
to reach distant locations. By itself, the lowest layer is capable of avoiding colliding with
objects in the world. The wander layer generates a random heading to follow at regular
intervals. The lowest layer treats this value as an attraction force towards that direction
and adds it to the repulsive force computed based on sonar readings. The architecture
then uses the result from this computation to suppress the behavior of the lowest layer,
25
which avoids obstacles. The net effect is that the robot moves in the direction intended by
the randomly generated heading, but it will also avoid colliding with obstacles; therefore
the behavior that results at the wander layer subsumes the behavior of the lower layer.
Similarly the top (exploration) layer suppresses the behavior of the wander layer, and
makes corrections to the heading of the robot while it is avoiding obstacles so that the
2.5.2 AuRA
AuRA is a hybrid architecture for robot navigation [Arkin and Balch, 1997]. AuRA is
based on the schema theory, where independently acting motor behaviors concurrently
implement the purpose of its schema. Behaviors are assembled together to produce
more complex behaviors, called behavior assemblages, by combining the vector values
generated by several schemas. For example, the GOTO behavior assemblage is made up
arbitration among the schemas that make up more complex schemas since all schemas
have the same goal of contributing to navigation. In addition, the behaviors are not
layered.
AuRA uses uses a deliberative planner. A plan sequencer translates the navigation
path determined by its spatial reasoner into motor schemas that can be executed. Once
reactive execution begins, the deliberation component becomes inactive, unless there is a
failure in the reactive execution of the current plan due to, for example, lack of progress.
When a failure occurs, the hierarchical planner is called to replan the failed reactive
26
2.6 Hybrid Systems
Hybrid systems combine the advantages of reactive systems and deliberative planning
execution module, a deliberative planner, and a layer that links the reactive and deliberative
layers [Gat, 1998]. This layer may be designed to generate reflective behavior, or it may
be a simpler layer that allows communication of the reactive and deliberative components
with no specialized high-level behavior. The general focus of hybrid systems has been in
practical reasoning rather than optimality, which is difficult to study in complex systems
with multiple interacting agents. While the low-level reactive module ensures that the
agent can survive in an environment and respond to critical dynamic events, the high-
level deliberative module plans actions for long-term goals [Gat, 1998].
The Procedural Reasoning System (PRS) is a system for executing and reasoning about
complex tasks in dynamic environments [Georgeff and Lansky, 1987]. PRS is based on the
Belief-Desire-Intention (BDI) model of agency [Georgeff et al., 1999]. The BDI model aims
to facilitate practical reasoning in rational agents [Bratman et al., 1988; Rao and Georgeff,
1995].
PRS has four types of data structures: (1) a database of beliefs about the world, (2),
a set of goals (or desires) to be realized, (3) a set of declarative procedures or plans
called Knowledge Areas (KAs) that describe how to perform tasks to achieve goals or
react to dynamic changes, and (4) an intention structure that contains all currently active
KAs selected to achieve current reactive or deliberative goals. The system is run by an
interpreter.
A plan has several parts. It has a trigger or an invocation condition that specifies under
terms of an event (for example, the “make tea” intention may be triggered by the condition
“thirsty” [d’Inverno et al., 1997]). A plan has context description or precondition that
27
specifies under what conditions the execution of a plan may start. A plan can also specify
a maintenance condition, which specifies a set of conditions that must be true as the plan
is executing.
The body contains the recipe of how to accomplish a certain task and is a tree structure
constructs such as condition, iteration, and recursion. In the special case of a primitive
Besides domain-specific KAs or plans, PRS also has meta-level KAs that are used to
manipulate the beliefs, desires, and intentions of the system. Meta-level KAs can use
domain-specific information.
It is possible for a BDI agent to have multiple desires that are “mutually incompatible.”
Although real-world environments can potentially change very quickly, agents cannot
afford to reason about the environment continuously, and therefore, they have to commit
themselves to certain goals with the intention of carrying them out eventually.
The interpreter works by cycling through a set of processes. It observes the world
and its internal state and updates the beliefs of the system. If the trigger and context
conditions of a plan are satisfied by the updated beliefs, that plan is selected as a potential
goal. After determining all plans that match the current events reflected in the beliefs, the
interpreter selects one to place on the intention structure for eventual execution. Finally,
the interpreter chooses one of the intentions stored in the intention structure to execute.
Since PRS agents do not plan from first principles at runtime, all plan details need to
be created manually at design time. PRS implementations have been used in handling
malfunctions in the reaction control system of the space shuttle [Georgeff and Ingrand,
28
2.6.2 Cypress
which is used for defining reactive agents for dynamic and uncertain environments.
Unlike traditional planning systems, Cypress does not make the assumption that agents
have perfect domain knowledge, since dynamic environments are unpredictable. As other
reactive planning systems, Cypress also tries to balance reactive behavior with deliberative
behavior. It also addresses failure recovery, such that agents have the capability to overcome
execution subsystem, and a reasoner for uncertainty. Cypress can handle problems that
arise during execution by replanning new alternatives using its generative planner. The
interesting part is that it does not have to stop its plan execution. The parts of the current
plan that are not affected by the problem continue to be executed while replanning goes
library. The executor is active at all times. It monitors the environment for events that
require actions to be performed, and it carries out those actions. The executor has three
main responsibilities. It runs plans that are stored in the agent’s planning library, calls
on the planner to generate new plans for achieving goals, or asks the planner to modify
its plans that lead to problems during execution. The planner in Cypress is not a low-
level planner; rather it plans down to a level of abstraction above the primitive level only;
subsequently the executor expands that plan to lower-level actions according to the current
runtime conditions. The planner does not plan to the smallest detail possible, because
without runtime information, it is not possible to determine a priori what set of low-level
actions will best fit the current situation. Therefore the level of detail in the planner is up
29
2.6.3 ATLANTIS
The idea of planning with complete world information and reacting purely based on
stimuli from the environment has been at odds with each other [Gat, 1993, 1992]. Gat
offers a resolution of this issue by stipulating that the issue at heart is how the internal
Section 2.5.1) do not store any internal state information. However, as Gat contends, as
long as the stored internal state information is used in predicting the environment, saving
state is advantageous over not doing so. Specifically the idea is that an internal state should
be maintained at an abstract level and should be used to guide the actions of agents and
ATLANTIS deals with online planning, which is problematic for three reasons. The
agent can miss to fail to respond to changes fast enough (“Oncoming trucks wait for no
theorem prover.” [Gat, 1993]). The second problem is that the classic planning approach
the third problem is that, while planning, the world may change in ways that invalidate
the plan being produced. Gat proposes that the first problem can be solved by planning
in parallel with dealing with contingencies. Gat stresses that the remaining two problems
arise due to how the stored internal state is maintained, particularly when the stored state
information does not reflect the realities of the environment. Moreover the problem is
not with the contents of what is stored but with the predictions implied by the stored
information. For example, in the case of soccer, an agent can predict the position of the ball
incorrectly, if it depends on relatively old information stored about the previous positions
of the ball.
Gat suggests that the solution to the prediction problem is to make predictions at a
high level of abstraction. The reason is that high level abstractions will still be valid even
if there are small changes in the world state. However, the sensor data is used to fill in the
gaps of such abstract representations. However, abstract world models can sometimes be
30
wrong. Gat stresses that this does not usually pose a problem if the abstractions are used
for guiding behavior and not for controlling them. The remaining capability that humans
possess in dealing with failures of expectation due to incorrect abstractions is the ability to
The ATLANTIS system incorporates these ideas to enable the classical planning
approach to deal with real-time control problems. The ATLANTIS architecture consists
for controlling the actuators according to the information received from the sensors.
The sequencer is responsible for controlling the computations of the controller, and the
deliberator is responsible for maintaining the world model. The controller embodies a set
of basic behaviors similar to the ones used in other architectures such as the Subsumption
Architecture [Brooks, 1991; Matarić, 1996], namely avoiding obstacles, following walls, etc.
Then these basic behaviors are used to construct more complex behaviors. However each
basic behavior also incorporates the ability to detect failures so that the agent can invoke a
contingency plan to recover from the failure. The ATLANTIS architecture has been applied
in simulating the navigation behavior of a single robot, whose task is to collect objects and
bring them to a home location in an environment with static obstacles. The system retains
information about the location of obstacles so that future attempts avoid obstacles already
2.6.4 IRMA
system based on BDI. Its goal is to enable resource-bounded agents to exhibit rational
behavior using means-ends reasoning for planning and a filtering mechanism in order to
The purpose of plans is both to produce action as well as to constrain deliberation. The
fundamental tenet of the IRMA approach is that a rational agent should be committed to
its intentions. Plans are used both to help focus means-end reasoning as well as to help
filter out options that are inconsistent with current intentions of the agent.
31
The IRMA architecture has a plan library that stores the procedural knowledge of
an agent. It explicitly represents an agent’s beliefs, desires, and intentions. It also has
an intention structure to keep track of the plans that the agent intends to complete The
subplans to complete structurally partial plans adopted by the agent. The opportunity
analyzer monitors the dynamic changes in the agent’s environment and proposes further
plan options in response to those changes. Once all options have been generated by
the means-end reasoner and the opportunity analyzer, IRMA uses one of its filtering
mechanisms, namely the compatibility filter, to check whether the suggested options are
compatible with the current plans of the agent. The options that survive filtering are
then submitted to the deliberation process. Finally the deliberation process considers the
available options, and weights competing the ones that may have survived compatibility
The second type of filtering mechanism of IRMA is the filter override mechanism.
The filter override mechanism knows about the conditions under which some portion of
exiting plans need to be suspended and weighed against another option. This mechanism
operates in parallel with the compatibility filtering mechanism. The deliberation process
is not affected by the filter override mechanism. By working in parallel with the
compatibility filtering mechanism, it allows the agent to reconsider options that got filtered
out by the compatibility filter but still triggered the agent to override the decision of the
compatibility filter due to opportunities that might have arisen or other sensitivity that
the agent has to the current situation that requires it to reconsider filtered out options.
Then the agent reconsiders its current intentions that are incompatible with the options
that triggered a filter override. The IRMA architecture has been evaluated in one-
agent experiments using different deliberation and filtering strategies in the Tileworld
32
2.6.5 InteRRAP
deliberation, and cooperation. It follows the BDI approach for representing an agent’s
The InteRRaP architecture has a world interface, a control unit, and a knowledge base.
The world interface allows perception and action as well as communication. The control
unit has a hierarchy of three layers, the behavior-based layer, the local planning layer,
and the cooperative planning layer. The agent knowledge base is also divided into three
hierarchical layers corresponding to those in the control unit. The first layer, the world
model, stores the beliefs of the agent, representations of primitive actions and patterns
of behavior. The second layer, the mental model, represents the knowledge an agent has
about its own goals, skills, and plans. The top layer, the social model, contains beliefs
The purpose of the behavior-based control layer is to react to critical situations and
handle routine procedural situations. So, the knowledge stored at this layer consists of two
types of behaviors: hardwired condition-action rules that implement the reactivity needed
to respond to critical situations, and pre-compiled plans that encode the procedural
knowledge of the agent. These behaviors are triggered by events recognized using the
world model. The local planning layer enables the agent to deliberate over its decisions. It
uses both the world model and the mental model, and it generates plans for the agent. The
highest control layer, the cooperative planning layer, extends the functionality of the local
planning layer to implement joint plans with other agents in the environment such that a
group of agents can cooperate and resolve their conflicts. Besides using the world model
and the mental model, the cooperative planning layer uses the social model of the agent
knowledge base to plan joint goals and communicate with other agents for cooperation.
The architecture also limits the lower layers from accessing the knowledge base of
higher control layers. So, for example, the local planning layer can access the world model,
which is the knowledge base corresponding to the behavior-based layer, but the behavior-
based layer cannot access either the mental model or the social model of the agent. This is
33
done to reduce the reasoning complexity at the lower control levels of the architecture.
InteRRaP implements three types of functions. The belief revision and knowledge
abstraction function maps an agent’s current perception and beliefs to a new set of beliefs.
The situation recognition and goal activation function (SG) derives new goals from the
updated beliefs and current goals of the agent. The planning and scheduling (PS) function
derives a new set of commitments based on the new goals selected by the situation
recognition and goal activation function and the current intention structure of the agent.
All three layers of the control structure implement a SG and PS function, and they
interact with each other to produce the overall behavior of the agent. If, for example, the
PS function at level i cannot handle a situation, S, it sends a request for help to the SG
function at level i + 1. Then the SG function at level i + 1 enhances the description of the
problematic situation, S, and reports back the results to the PS function at level i so that
provides for commitment posting to lower layers so that the PS function modules can
communicate their activities. For example, the local planning layer can use partial plans
from the cooperative planning layer and take into account the commitments of the upper
2.6.6 TouringMachines
has its inspiration in the Subsumption Architecture [Brooks, 1986] (See Section 2.5.1), but,
The input to the architecture is handled by a perception subsystem, and the output of
defines a fixed period for generating inputs to the system using the perception layer
and outputs from the system using the action subsystem so that inputs and outputs are
34
synchronized. The architecture comprises three control layers that work concurrently
and are able to communicate with each other to exchange control information and
At the lowest layer, the reactive layer generates actions to enable an agent to respond to
immediate and short-term changes in the environment. The reaction layer is implemented
with a set of situation-action rules, and it does not do any search or inferencing to select
which rule to execute. The reactive layer does not use an explicit model of the world and
The planning layer is responsible for building and executing plans to implement
the agent’s well-defined achievement goals that define a start and a final state. The
functionality of the planning layer is divided into two components, the focus of attention
mechanism and the planner. The job of the focus of attention mechanism is to limit the
the amount of the information that the planning layer has to store and manipulate by
filtering irrelevant information for planning so that the agent can operate in a time-
bounded fashion. The planner is responsible for constructing and execution a plan to
achieve the agent’s high-level goals. Since any layer of the control architecture can submit
action commands every operating cycle, the planning layer interleaves planning and plan
execution. Each layer can submit at most one action command per input-output cycle, and
a mediating set of control rules resolves conflicts that might arise between the layers.
The TouringMachine architecture can have two types of conflicts between its control
layers. One type of inter-layer conflict occurs if two or more layers attempt to take action
for the same perceived event in the environment. Another type of conflict occurs if one or
The control rules act as filters between the sensors and the control layers, and they are
applied in parallel once at the start and once at the end of each operating cycle. Censor
rules are applied at the start of a cycle, and they filter sensory information to the inputs of
the three control layers. Suppressor rules are applied at the end of a cycle, and they filter
action commands from the outputs of the three control layers. Both types of control rules
35
Since the control rules are the only method of mediating the input to and output
from the three control layers, each layer works transparently from each other. Therefore,
even when one layer is unable to function, other layers can still continue to produce
behavior. However, realistic domains require complex functionality, and the independence
of the three layers is not sufficient to produce the type of complex responses required
The most critical issue in enabling multiple agents to work together in a multiagent
setting is the sequencing of individual actions such that the overall behavior is coherent
[Jennings, 1996]. There are three levels of group activity that we can define using the terms
Webster],
• coordination means “to put in the same order or rank” or “to bring into a common
• collaboration means “to work jointly with others or together especially in an intellectual
endeavor”.
There are also definitions available from the organizational development field [Winer
and Ray, 1994]. Table 2.1 gives a summary of these definitions from a set of perspectives
that we adapted from [Winer and Ray, 1994, page 22] for multiagent systems.
As Table 2.1 indicates, we refer to group activity in the loosest sense using cooperation
and in the strongest sense using collaboration. We can then think of coordination to refer to
activity that may be collaborative for short periods of time and cooperative at other times.
However, these definitions of cooperation and coordination seem to be at odds with those
used in AI literature.
36
Cooperation Coordination Collaboration
Relationship short-term informal longer-term, more formal long-term, close
relations among agents relationships among relationship among agents
agents
Goals no clearly defined goal common goal full commitment to a
common goal
Organizational no defined organizational agents focus on a specific a clear organizational
Structure structure effort structure is established
Planning no planning some planning occurs comprehensive planning
among agents
Communication agents may share agents are open to well-defined
information communication communication is
established
Authority still retain authority still retain their individual agents work together in
authority the established
organizational structure
Resources resources are not shared resources are shared resources are shared
imply cooperation as in the example of traffic where vehicles move according to commonly
agreed rules. However, using the definitions of [Winer and Ray, 1994], we have to say that
vehicle activity in traffic is only cooperative and not coordinated, and therefore we have
to assert instead that “Cooperative activity does not necessarily imply coordination.” We
can also say that “Coordinated activity does not necessarily imply collaboration.” The
Webster dictionary definitions are consistent with this view, especially since the definition
of coordination is associated with a common goal and that for cooperation is not.
Crowston, 1994]
They add:
each have their own connotations, an important part of each of them involves
37
Even though this definition of coordination is not inconsistent with the definitions
we adopted from [Winer and Ray, 1994], it is not distinguished from cooperation and
[Doran et al., 1997] defines cooperation in a way that resembles the definition of
coordination in [Winer and Ray, 1994]. It gives two conditions for cooperative activity:
(1) That agents have a possibly implicit goal in common and (2) agents perform their
actions not only for their own goals but for those of other agents. According to [Jennings,
1996], coordination is built upon commitments, conventions, social conventions, and local
3. No one agent has the capability, nor the resources, nor the information to solve the
problem.
2.8 Realtime AI
Realtime AI approaches attempt to bridge the gap between reactive AI systems and hard
hybrid systems provide some sense of real-timeliness due to their ability to generate
relatively fast responses to dynamic events. However, they do so without any guarantees
about how long it may take for an agent to respond to an event. Hence these approaches
can be categorized as soft realtime. For instance, even if an agent produces a correct
period τ may be too long for that otherwise correct response to be effective or meaningful
at time t + τ , since the world may have changed meanwhile. If event e required a response
within a time period of κ, where κ < τ , then response r would be considered a failure.
get more complex, AI and realtime fields are becoming more interdependent. AI systems
38
are in need of realtime properties, and realtime systems are in need of AI techniques .
Therefore, besides being able to operate under bounded rationality [Simon, 1982], real-world
intelligent agents have to be able to operate under bounded reactivity [Musliner et al., 1993]
as well.
Bounded rationality says that an agent’s resources place a limit on the optimality of the
agent’s behavior with respect to its goals. Bounded reactivity says that an agent’s resources
Hard realtime systems guarantee that execution deadlines will be met; otherwise
catastrophic failure may occur. Therefore, hard realtime systems are not necessarily
fast-responding systems [Stankovic, 1988]. Reactive systems, on the other hand, aim
completeness, timeliness, and quality. Completeness says that a correct output will be
generated for all input sets. Timeliness says that the agent produces its responses before
specified deadlines. Quality describes the quality and the confidence of the generated
There are two main characteristics of an anytime algorithm. First, the algorithm can be
suspended any time with an approximate result, and, second, it produces results that
learning and genetic algorithms also belong [Grefenstette and Ramsey, 1992]. The major
issue in anytime algorithms is the tradeoff between solution generation time and solution
Grefenstette and Ramsey describe an anytime learning approach using genetic algorithms
1992]. The goal of the system is to learn reactive strategies in the form of symbolic rules.
39
The system is made up of a learning module called SAMUEL that runs concurrently with
an execution module.
The system has a simulation model of the environment, and the learning module
continuously tests the new strategies it generates against this simulation model of the
domain and updates its current strategy. The execution module controls the interaction
of the agent with its environment, and it also has a monitor that dynamically modifies the
simulation model based on the observations of the agent. Learning continues based on the
updated strategy of the system. The anytime learning approach was tested in a two-agent
The anytime planning approach in [Zilberstein and Russell, 1993] starts with low-
quality plans whose details get refined as time allows. This approach was tested in a
[Ferrer, 2002] presents an anytime planning approach that replaces plan segments
made up of operator sequences around failure points with higher-quality ones that are
generated quickly, progressively replacing larger segments to increase the plan quality.
planning that has two phases for building plans. The first phase involves an anytime initial
plan generation component that generates a partial plan using a hierarchical planner.
the idea that an anytime decision-making algorithm must consider the most critical aspects
of the problems first. This approach uses abstraction to focus the attention of the planner
on those parts of the problem that have the highest expected utility. This is called the
rational refinement property. That is, it is not good enough to impose the constrains that
(1) the planner can be interrupted any time and the expected utility of the plan never
decreases, and (2) that deliberation always increases the expected utility of the plan. The
third needed property is the rational refinement property. Actions are represented by
conditions and probabilities, and uncertainty is represented using utility function over
40
outcomes (maximum expected utility).
Realtime search methods enable the interleaving of planning and execution but they do
not guarantee finding the optimal solution [Ishida, 1998]. The A* algorithm is a type of
best-first search in which the cost of visiting a node in the search graph is determined by
the addition of the known cost of getting to that node from the start state and the estimated
heuristic cost of reaching the goal state from that node. Thus, this cost function provides
an estimate of the lowest total cost of a given solution path traversing a given node.
A* will find an optimal solution as long as the heuristic estimate in its cost function
never overestimates the actual cost of reaching the goal state from a node (the admissibility
condition). The assumption with classic search algorithms such as depth-first, breadth-
first, best-first, A*, iterative-deepening A* and the like is that the search graph can be
searched completely before any execution has to take place. However, the uncertainty
in dynamic environments and the increased computational costs stemming from the
complexity of the environment renders the classic search approach impractical. Therefore
a new search paradigm is necessary where the agents can interleave execution nth search
since they cannot always conduct search to completion due to the complexity and the
uncertainty involved in predicting future states of the problem space. Moreover the goal
of search is frequently the optimization of the overall execution time spent in reaching the
goal state from the start state in real time. Hence the interleaving of execution with search
is imperative.
Real-Time A* (RTA*) and Learning Real-Time A* (LRTA*) are algorithms that enable
an agent to implement this interleaving of execution and search [Korf, 1990] . The RTA*
algorithm expands a node in the search graph and moves to the next state with the
minimum heuristic estimate, but it stores with that node the best heuristic estimate from
among the remaining next states. This allows RTA* to find locally optimal solutions
if the search space is a tree. The LRTA* algorithm on the other hand stores the best
heuristic value among all next states in the current node instead of the second best heuristic
41
estimate, and with repeated trials that may start from different start states, the algorithm
improves its performance over time since it always minimizes cost when it moves to the
next state. As such, given an admissible heuristic function, the heuristic values of each
state in the search graph eventually converges to its actual value giving rise to an optimal
solution.
Even if realtime search is suited for resource-bounded problem solving, the intermediate
actions of the problem solver are not necessarily rational enough to be used by autonomous
agents. Moreover, they cannot be applied directly to multiagent domains since they
cannot adapt to dynamically changing goals [Ishida, 1998]. An extension of LRTA* to non-
deterministic domains has been proposed by Koenig [Koenig, 2001]. A variation of LRTA*
has also been used to implement an action selection mechanism by considering planning
as a realtime heuristic search problem where agents consider only a limited search horizon
[Bonet et al., 1997]. This action selection mechanism interleaves search with execution but
architecture [Musliner et al., 1993]. It merges the ideas of AI with real-time systems to
guarantee timeliness. The main strength of CIRCA is that it reasons about its own bounded
reactivity, that is, deadlines provide an upper bound to how fast the system should produce
a response. CIRCA trades off completeness with precision, confidence, and timeliness,
which is the most important concern in real-time domains, as for example, airplane control
cooperation with the Scheduler subsystem are responsible for deciding which responses
can and should be guaranteed by the the real-time subsystem (RTS). The RTS implements
the responses that are guaranteed by this decision. The guarantees are based on worst-
pairs (TAPs), which are known to have worst-case execution times. The TAPs are run
42
by the RTS. The AIS reasons about the results of these runs executed by the RTS, and in
cooperation with the Scheduler searches for a subset of TAPs that can be guaranteed to
meet the control-level goals and make progress towards the task-level goals of the system.
There are two major goals of multiagent systems. The first is to enable autonomous
system. The second is to enable the solution of problems that cannot be solved by a single
agent or would be very difficult or impractical to do so. So, in general, multiagent systems
provide modularity in both dealing with the problem space as well as with resources
[Sycara, 1998]. A great deal of work in multiagent systems deals with robot control that
As the research trend in AI moves towards realistic domains and practical applications,
it is becoming apparent that researchers must deal with a challenging set of issues in
multiagent systems. In this section, we will briefly list a set of issues that relate to this
thesis. So we will consider multiagent systems that are designed to work on common
Problem Decomposition: How a problem is divided into parts affects how a group
of agents can contribute to the solution of that problem. In a totally distributed agent
network, it may be possible to assign tasks to individual agents such that, after each is
done solving its own part, the solution to the entire problem can be constructed . Agents
may be able to negotiate and bid on what to do based on their capabilities. In highly
needs to be related to other agents in its group with which it shares goals. The selection
43
of the type of relationship among agents depends partially on the particular multiagent
system’s design but also on the domain. For example, in box pushing or soccer domains,
individual agents must share a collaborative relationship to achieve tasks (e.g., [Riedmiller
and Merke, 2003; Parker and Blumenthal, 2002; Stone and Sutton, 2001; Mahadevan and
Connell, 1992]).
limitation, agents still need to stay aware of each other and their environment in order to
passing messages, or it can be implicit, based on social conventions. Agents may negotiate
among themselves to collect information they need to proceed with their assigned tasks
et al., 1988]. Continuous reaction to external events does not necessarily contribute to
the progress needed to attain goals. Instead, agents need to keep their commitments to the
plans they intend to carry out as they adjust to the dynamic conditions that may otherwise
Resource Management: Each agent needs to reason about its own local resources, and
a team of agents must reason about their shared resources to make the best use of them
Role Assignment: Given a multiagent task, how parts of that task are assigned is
critical for the success of the group of agents in achieving that task. However, role
important part in how a group of agents can reason about their common goals in terms
agents to be capable of recognizing opportunities that may enable them to attain their
44
systems to work more efficiently using learned knowledge, and others enable them to
acquire new knowledge. In dynamic and complex environments, learning can play a
Among the issues a multiagent learning system has to deal with, successful collaboration
required to solve a problem may however vary from domain to domain. In mobile robot
systems, for example, it is imperative that each agent coordinate its actions with others
Most work in multiagent learning has so far used Reinforcement Learning (RL). In
standard RL, an agent learns which actions to choose next based on the feedback or reward
discrete states, a set of discrete actions, and a set of reward signals. An agent may receive
both immediate and delayed rewards towards the achievement of a goal. By exploring the
state space using its actions, guided by the reward signals it receives after executing each
action, the agent can construct a policy to be able to operate in that environment. Delayed
reinforcement signals are critical, since they help guide the search through the state space
RL methods can be divided into two groups: (1) model-free approaches, and (2) model-
based approaches. Model-free approaches, such as Q-learning [Watkins and Dayan, 1992],
do not require a model of the domain in order to learn. Instead the domain knowledge
encoded in the reward function guides the learner towards finding optimal policies by
other hand, agents learn a value function as they learn a model of the domain. A model of
the domain is one that makes a prediction about what the next state and next reward will
be given a state and an action performed in that state [Sutton and Barto, 1998; Kaelbling
et al., 1996; Wyatt, 2003]. However, in real-world domains, predicting the next state
and action is impractical. For this reason, RL approaches adapted to real-world and
realistic domains favor model-free approaches (e.g., [Stone and Sutton, 2001; Riedmiller
45
2.9.2 Practical Issues in Multiagent Learning
Learning systems in complex domains face a set of challenges both in the single-agent and
the multiagent case, but, in the multiagent case, these challenges are exacerbated further
Large Search Spaces and Discretization: In real-world complex domains, state and
action spaces are continuous and hence practically impossible to search exhaustively. Even
after discretization, state and action spaces can still be very large. Therefore, search spaces
problematic because too coarse a discretization will blur critical differences, and too fine
a discretization will make generalization difficult and may even be prohibitive for search
due to the size of the search space [Smart and Kaelbling, 2000]. If, on the other hand, no
discretization is done, then there still needs to be a method that allows exploration within
the search spaces of interest. The use of neural networks as function approximators in
Reinforcement Learning, for example, allows inputs to have continuous values. However,
function approximators suffer from the problem of hidden extrapolation, that is, they do not
make valid predictions for all queries [Smart and Kaelbling, 2000].
assignment problem deals with attributing a value that indicates the relative strength of
positive and negative contribution of an action to achieving a goal. This contribution can
of goals requires actions from different agents that are frequently interdependent on the
Shifting Concepts: In single learner domains, the only agent interested in improving
its behavior is the learning agent itself. In multiagent learner domains, however, the
concepts each agent learns are potentially interdependent on the behavior of other agents,
which are themselves in the process of learning, hence the concept that has to be learned
from each agent’s perspective shifts constantly. Therefore, reaching convergence for a large
Local View of the Environment: Since agents operating in real-world domains cannot
46
have a global view of the environment, local decisions of each agent have to contribute to
the achievement of the global common goal. Meanwhile, each agent faces the problem of
hidden state, since it cannot always sense its local environment fully.
Noise and Uncertainty: Agents embodied in complex domains suffer from noise both
in sensing and acting. Imperfect sensors do not provide exact data, and imperfect actuators
predict what will happen next in the environment, since changes do not only originate
from the current agent, unlike the case in traditional planning systems. Since noise and
[Matarić, 1997b] presents a RL approach that addresses the problems of very large
intermittent feedback into a continuous error signal. To do this, Mataric uses two
be subgoals in complex tasks. Progress estimators evaluate progress towards a goal. Since
behaviors to conditions. They also terminate behaviors that are detected not to make
progress. The RL learning approach has been tested in a group foraging task that uses
behaviors for safe wandering, dispersion, resting, and homing. The set of conditions to
consider is also provided, so that the learning of which conditions should trigger which
behaviors is feasible.
supervised learning method for learning method preconditions in HTN planning (See
Section 2.3.1). CaMeL uses plan traces as input to its learning algorithm .
[Benson, 1995] presents a learning method whereby an agent can learn action models
47
from its experience and also from its observing a domain expert. Instead of learning
control policies directly, this system (a part of Teleo-Reactive Agent with Inductive
Learning (TRAIL)) learns action models, and, using these learned action models, it
computes reactive plans. Most of the learning occurs during execution of reactive plans
TRAIL uses a continuous/durative action representation. This means that such actions
similar to a STRIPS rule, except that its preconditions must be maintained throughout
the execution of the actions of the plan. In addition, side effects can occur any time
during the execution of a rule, unlike add and delete lists in STRIPS that are incorporated
into the world description once the execution of a rule ends. Benson reports that most
learning occurs during when TRAIL is following a reactive plan. Reactive plans are
formed based on TOPs, and the plan executor informs the learner whether the current TOP
has been successful or not. Then the learner identifies positive (successful) and negative
(unsuccessful) learning instances. These instances are then fed into an inductive logic
programming learner. Since Benson’s work involves symbolic reactive learning, however,
[Haigh and Veloso, 1998] presents ROGUE, an agent that integrates planning, execution,
planning. The task planner in ROGUE is built on the Prodigy 4.0 planning and learning
system. The task planner generates and executes plans for multiple goals that might arrive
asynchronously. ROGUE interleaves planning and execution so that it can detect failures
and successes in order to respond to them. The learning component looks at the execution
traces of the agent to determine in which situations the task planner’s behavior needs to
improve or change. Then it correlates the features of the environment with the situation
and creates rules that allow the agent to recognize the same situations to predict and avoid
failures later.
general plans in a planning approach that integrates classical planning and reactive
48
planning. Determining a correct plan is done in two stages. In the first stage, a completable
plan is constructed prior to execution. The plan may be incomplete, but there is a provable
guarantee that the missing parts can be filled in during execution. So, the second stage
is the completion of a plan that takes place during execution. With this approach, a
priori planning is simplified, and perfect knowledge is not required since execution-time
This approach identifies three types of planning subproblems for which achivability
proofs can be constructed: (1) repeated actions, i.e., loops, and terminal goal values;
(2) continuously-changing quantities and intermediate goal values, and (3) multiple
opportunities .
This approach makes two modifications to standard EBL. It introduces variables, called
conjectured variables, to be able to reason able deferred goals. It also introduces a completion
step using special operators called completors. The value of conjecture parameters are
those that are determined during execution. The job of the planner is to recognize these
kinds of parameters.
The completors are responsible for finding suitable values for conjured variables
during execution of a plan. Corresponding to the three types of subproblems, there are
three types of completors, one for each type: (1) iterators that perform a particular action
repeatedly until some goal is achieved, (2) monitors that watch a continuously-changing
quantity to determine whether a particular goal value has been reached or not, and (3)
Using the given domain theory, EBL first produces an explanation for why a training
example is an instance of the target concept using the domain theory, and then it
generalizes the explanation. EBL does not learn new concepts but instead expresses the
target concept in an operationalized manner. So EBL is a method that learns from single
training examples. The downside is that an EBL system requires a complete domain theory
49
predator-single-prey domain for overriding default behavioral rules of individual agents.
In this domain, the default behavior of an agent is to move closer to the prey, unless there
is a case it previously learned that overrides this default behavior [Haynes and Sen, 1996a].
An agent learns a new case when its current case base or behavioral rules fail to predict the
state the agent will be in after taking a certain action in the current state, and the learned
case causes the agent not to select the same action when it finds itself in the same state. If
an agent A1 learns a case c1 as a result of its interactions with another agent, A2, then A1
has to make sure that the A2 takes the same action it did when A1 learned c1. Otherwise,
A1 has to modify its model of A2. The main assumption in this work is that agents have
accurate perceptions of actions and states of all agents in the domain. The predator agents
management. This system has seven agents. One of the agents continuously receives
and processes data about the network, including alarms and component status, and two
diagnostic agents that diagnose faults. One of the diagnostic agents determines the general
region of an electrical fault, and the other one uses model-based reasoning to determine
and verify the cause of the failure. In this system the diagnostic agents cooperate in the
sense that the general area of the fault indicated by the unsophisticated agent helps the
[Garland and Alterman, 1996] and [Garland and Alterman, 1998] discuss multiagent
learning through Collective Memory (CM) for autonomous agent coordination. The basic
idea is that learning using CM will lead to efficient long-term behavior even if short-
50
traces are analyzed and improved before saving into the casebase. Agents also maintain
This COBWEB tree is used to estimate the probability of successfully executing operators.
If the same operator has been attempted before, an agent can use this past experience to
determine success probability of that operator directly. Otherwise, the agent can use the
COBWEB tree which clusters each operator according to its observable attributes to get an
Agents do not have special cooperation or coordination strategies. They have common
top-level goals, and they use their own perspective to act. Then through the use of
the CM, agents start building towards having a common perspective on how best to
communication occurs only at designated points . So agents can learn to reduce the
The CM approach was tested in the MOVERS-WORLD domain. The task in this
domain is to move furniture and/or boxes from a house into a truck and vice-versa.
This domain has specialized agents. Some are lifters and some are hand-truck operators.
Agents with the same ability also differ in the value of their common attributes, e.g.,
strength.
If there are significant changes in the environment or the top-level goals of agents
change, agents use their casebase of procedural knowledge CM. When this is not the
case (no significant changes occurred in the environment or no relevant plan is found
in the casebase), then the agent either adapts the current plan or plans from scratch.
When planning from scratch, the agent uses the operator probabilities to guide the search
[Lee et al., 2002] discusses a technique that combines case-based reasoning and a crude
reports using case-based reasoning to learn what parameters to select for robot behavior
51
assemblages in the AuRA robot architecture [Arkin and Balch, 1997]. The system starts
with an empty case base, and it acquires cases whenever it does not already have a similar
case in its case base. During application, each case is subject to adaptation of its parameters
for further fine tuning of the parameters it stores for a given behavioral assemblage.
reinforcement learning technique using explicit task structures . A task graph represents
a particular task at several levels. Higher levels contain joint tasks, and the lowest level
tasks are primitive tasks that can be directly executed. This abstraction hierarchy reduces
the state space. This approach was tested in a trash collection task.
One of the earliest learning systems was by Littman, who used soccer as a domain in
a two-player zero-sum Markov game [Littman, 1994]. Another early learning work by
Matsubara et al. [Matsubara et al., 1996] introduces the robotic soccer simulation as a
standard problem to study for multiagent systems. Matsubara et al use neural networks
with backpropagation to teach agents whether they should shoot the ball or pass it to
The learning system described in Stone’s thesis [Stone, 1998] contains three distinct
layers where each layer builds upon the the capabilities of the layer immediately below.
These layers are: (1) ball interception, (2), pass evaluation, and (3) pass selection. The ball
interception and pass evaluation layers use offline learning techniques, and the top layer,
In the lowest layer, ball interception, an agent learns an individual skill to take control
of an incoming ball both for blocking shots from opponents and receiving passes from
teammates. This layered was implemented both empirically using neural networks as
well as analytically. Stone reports that both approaches worked equally well [Stone, 1998,
Chapter 5].
In the middle layer, pass evaluation, an agent learns a multiagent behavior, since
passing directly involves two agents, the sender and the receiver. This layer evaluates
52
whether a pass to a teammate will be successful or not using C4.5 decision tree learning
[Quinlan, 1993]. For a pass to be successful, the sender must execute a kick action correctly
in the presence of opponents and the receiver must successfully receive the ball using its
The middle layer introduces control functions called receiver choice functions (RCFs).
The input to a RCF is the current state of world from an agent’s perspective, and the output
The pass evaluation layer uses 174 features, 87 of which are described from the
receiver’s point of view and 87 of which are described from the passer’s point of view.
Since C4.5 decision trees can deal with missing features, an agent can still make a decision
even if some features of the environment are currently missing, such as players that are
currently unseen.
The top layer, pass selection, comprises learning a team behavior. By using its pass
evaluation skill, the agent currently in possession of the ball has to choose which of its
teammates to pass the ball to next, and the agent uses its pass evaluation skill to learn
this skill. This layer is implemented using a reinforcement learning technique introduced
a value function to map state-action pairs to expected future rewards. The basis of the
argument behind TPOT-RL is the need for quick generalization based on relatively rarely
occurring learning opportunities when the learning agent has possession of the ball. To
achieve this kind of generalization, the decision tree pass evaluation function learned at
the middle layer is used as main component of the input representation to the TPOT-RL
algorithm. In addition, each team member learning pass selection from its own perspective
reduces the state space. The decision tree for pass evaluation reduces the input world
description to a single continuous number, the confidence factor of the success of a pass.
In the soccer context, goals would receive the highest reward. However, since goals
are relatively rare, TPOT-RL uses intermediate reinforcement based on how far the ball is
53
advanced into the opponent’s field. This intermediate reinforcement is applied within
a fixed time window starting from the current state, and, because of this limited time
window, rewards are temporal unlike long-term rewards in Q-learning. The rewards
obtained in later states are then discounted based on how far into the future a rewarding
state is reached. Therefore, the ball being passed back and later moved up the field towards
The action space in TPOT-RL discretizes the passing action such that an agent only has
8 specific locations on the field to kick the ball to. Instead of kicking towards specific
players, the discretization scheme presumes there will be teammate at the intended
The AT Humboldt system [Burkhard et al., 1998, 2000] is based on the Belief Desire
Intension (BDI) architecture [Rao and Georgeff, 1995]. It uses a decision tree to decide
which goal to pursue, but the set of goals it can choose come from a predefined planning
library. The learning in AT Humboldt is limited to individual skills such as ball shooting
Parker and Blumenthal use genetic algorithms to co-evolve two separate populations
in order to provide two specialized team members in a simulated box-pushing task [Parker
and Blumenthal, 2002]. To enable efficient partnering of the most specialized individuals
from the two separate populations, they use a punctuated anytime learning approach.
Instead of choosing the most fit individuals from each population every iteration, this
technique chooses the most fit individuals at regular intervals. In the interim generations,
the most fit team members chosen from the last punctuated generations are paired with
individuals from the opposite generation for fitness. Since the fitness function for a
multiagent system has to recognize the best overall team, partnering one weak individual
with a specialized individual would cause the learner not to recognize the specialized
individual’s strength. Therefore, using the most fit members from the last punctuated
generation for fitness evaluation allows the genetic algorithm to evaluate the fitness of
each individual with the most specialized partner from the other generation to find the
best team for the cooperative task of box-pushing [Parker and Blumenthal, 2002].
54
Balch describes a simulated multi-agent system 1 where each agent learns a specialized
role for playing soccer [Balch, 1997b]. This system uses groups of independent primitive
are not adaptive, the system uses Q-learning to enable agents to pick the most appropriate
behavior assemblage in the current situation. The work reported in [Balch, 1997b] assumes
that sensors are perfect. A method for integrating reinforcement learning into behavior-
Genetic algorithms have also been used to create soccer playing teams [Luke et al.,
1998; Luke, 1998]. This work by Luke et al. divided the learning problem into two, one
for moving each player and another for kicking the ball. At the high level, a simple set of
rules controlled each player that made use of the learned moving and ball kicking behavior
whenever appropriate. Players did not use communication and had no internal state due
to the difficulty of including such capabilities in the genetic algorithms context within a
In recent years, the simulated keepaway game in soccer has been used to study how to
[Kuhlmann and Stone, 2003; Stone and Sutton, 2001; Kostiadis and Hu, 2001]. In the
keepaway game, one of the two teams tries to keep the possession of the ball as long
as possible, while the opponent team attempts to get the ball. This work uses a subset of
each team (usually 3 vs 2) for the keepaway task. A different set of state generalization
techniques have been used in the reported work. [Whiteson and Stone, 2003] presents a
concurrent layered learning approach following [Stone, 1998], also tested in the keepaway
simulated soccer game. Instead of learning low-level behaviors first and constructing
high-level behaviors using those low-level behaviors, the concurrent layered learning
approach learns at both levels at the same time. The learning method used was neuro-
evolution where genetic algorithms are used to train neural networks [Whiteson and
Stone, 2003].
[Riedmiller and Merke, 2003] formulates soccer as multiagent Markov decision process
1
The simulator used is different from the RoboCup soccer simulator.
55
(MMDP). This formulation involves a hierarchical approach to learning in the simulated
RoboCup soccer environment, since agents need specific skills. Each such skill has a
away using skills, the search space is reduced. Instead of sequencing a list of instantiated
primitive actions, instantiated skills need to be sequenced. Since each skill lasts a limited
number of cycles, the number of decisions are much smaller than the number of decisions
to be made for an entire game. The system learns a set of basic skills that include kicking
the ball well, intercepting the ball, going to a position by avoiding obstacles, holding the
ball, dribbling against an opponent. [Riedmiller and Merke, 2003] reports that learning
team strategies with more than 4 players (2 attackers and 2 defenders) did not converge,
since the state space grows exponentially with a bigger area of the field. The value function
soccer teams using incomplete world models and a technique that combines CMACs and
simulator, and teams have 1 to 3 players on each side, and there are impassable walls.
circle intersects that of the ball, the player controls the ball. The action set is also higher
level than the RoboCup simulator. This is a model-based RL approach that does not use
In recent years, robotic soccer has been proposed as a benchmark problem to study AI
[Mackworth, 1993; Sahota, 1994]. Since the game of soccer naturally comprises multiple
players that have to make autonomous decisions, it has also become a benchmark problem
for studying multiagent systems [Kitano et al., 1997a,c,b]. To study algorithms in a more
56
easily reproducible way for a complex and dynamic domain like soccer, a simulator has
been in continual development and use by many researchers [Noda et al., 1998; Noda and
The RoboCup soccer simulator provides a realistic environment for studying many
aspects of multiagent systems. Since the game of soccer is highly dynamic, cooperation
and the adversarial and uncertain characteristics of the environment pose challenges for
setting up and executing coordinated behaviors. Since the environment can potentially
change very quickly, the agents must be able to react to those changes in service of
their longer-term goals. At the same time, the complexity of the environment requires
deliberation. That is, the agents must balance deliberation and reaction.
Meanwhile, each agent must also manage its resources to get optimal behavior from its
actions. In the simulated soccer environment, we can speak of three major resources that
must be managed well. First, an agent that is in possession of the ball must make good
decisions as to what to do with the ball. Should the agent dribble the ball to a different
location before passing the ball? Which player should the current agent pass the ball to?
Second, agents have finite stamina, which gets expended every time the agent executes a
move command. So, how much of its stamina can the agent afford to expend at a given
time? Third, the agents can communicate in the simulation environment, but, similar to
real physical robotic systems, this ability is very limited. When should an agent send a
message and what can the message say in order to help with collaborative behavior?
As a discrete event simulator, Soccer Server provides a simulated robotic soccer client-
server environment that is realistic and complex for multiagent problem solving [Noda
et al., 1998]. An agent in this simulator soccer domain works as a client program that
controls a single player. The client connects to the simulator through a UDP socket. The
agent then uses this connection to send commands to the simulator and receive periodic
57
Each player receives periodic visual and self-awareness feedback from the simulator.
The visual feedback arrives on during the first two cycles out of every three consecutive
cycles. The self-awareness feedback, on the other hand, arrives at the start of every
simulation cycle, and it includes the counts of each type of primitive command already
executed by the Soccer Server on behalf a player and other information about its current
state.
For controlling each player, the simulator offers to each client program a small set of
action commands. Most of these commands are parameterized, so the controlling program
must instantiate a value for each each command according to the situation at hand.
Except for a few commands that can be sent simultaneously, the simulator only accepts
one command per agent per simulation cycle. When a client program sends multiple
commands that cannot be executed within a cycle, the simulator randomly chooses one
The simulator introduces a small amount of random noise to all of the information
contained in the visual feedback and some of the information in the self-awareness
feedback. It also adds noise to the actions of players and to the motion of the ball after it
is accelerated by a kick. As a result of this noise, agents perceive slightly noisy versions of
positions of landmarks and other agents. This makes the triangulation of agent positions
more difficult. In addition, an agent has a limited view of its surroundings. The Server
also adds noise to the commands sent by each player so that the exact effect of each action
is uncertain.
Each team has the option to use a coach. The simulator is configured using an input file
that contains parameters and their values. The Soccer Server is described in detail in the
58
Soccer Field and Landmarks
The Soccer Server simulates a 2-dimensional soccer field of size 105×68 distance units.
The field contains fixed virtual markers to help agents with self-localization and other
(flag g l t) (flag g r t)
(flag g l b) (flag g r b)
54.16
(flag l b 10) (flag p r b) (flag r b 10)
16.5
(line l) 13.84
(line b)
(flag l b 30) (flag r b 30)
(flag l b) (flag c b) (flag r b)
L_org 5
(flag b l 40) (flag b l 20) (flag b 0) (flag b r 20) (flag b r 40)
(flag b l 50) (flag b l 30) (flag b l 10) (flag b r 10) (flag b r 30) (flag b r 50)
10
5
105
Figure 2.1: The soccer field and fixed reference markers in the simulator environment
All moving objects are modeled as circles whose radius is specified in the input configuration
file. Distances and angles are reported with respect to the center of the circle representing
The environment simulates up to 11 players on each side but not all players need to
be used in any given session and the number of players on each side need not be equal.
Each player may send a command to the simulator any time during the current simulation
2
This figure has been reproduced with some additions from the Soccer Server Manual [Chen et al., 2002]
59
cycle, but all commands sent to the simulator by currently simulated players take effect
The direction of an agent’s motion is determined by its current body angle, and the
direction of the ball’s motion is determined by the direction of the kick. In addition, the
effect of the movement actions of the ball (following kicking) and the players (following
running) last past the cycle in which they are executed. For example, if a player starts
running in cycle t, it will continue to move in the direction of its movement in cycles t + 1,
t + 2 and so on. However, the movement decelerates every cycle, because the simulator
decays the movement of each movable object by a factor specified for that type of object in
The simulator also checks for object collisions at the end of each cycle. If any two object
circles overlap, the simulator moves the overlapping objects such that they are no longer
Agent Sensing
An agent’s orientation on the field is determined by its position and its body angle. Version
5.00 of the Soccer Server introduced the ability to turn the neck independently but relative
to the body so a player can move in a direction different from that of its neck.
The detail and the quality of the information an agent perceives depends on the angle
of its neck, its distance from other objects, and the angle of its viewing cone about the
direction of its neck. The angle of the viewing cone can be dynamically changed, but the
detail of the visual feedback an agent receives is inversely proportional to the width of
the viewing angle. The narrower the viewing angle, the more detail an agent receives in
its visual feedback about the environment. But, with a narrow viewing angle, the agent
does not see as much of its surroundings as it could have with a wider viewing angle. So,
for example, it may be best to set up the goalie with a wide viewing angle so that it can
see more of the field at any given instance, but, in wide viewing angle mode, there is less
information provided about seen movable objects that could otherwise be used to deduce
60
A player also receives information about objects that are close-by but not within its
current viewing cone. For example, if the ball is behind a player, the player will still receive
information about the ball so that it can know the ball is nearby. In the case of nearby
players that fall outside the current viewing cone of a player, the simulator sends only
partial information. This partial information excludes player identity, so that the player
cannot directly identify those players or objects but, it can know their object type.
Agent Communication
In the Soccer Server environment, agents can send and receive messages of a fixed size.
All messages are broadcast to all the players within an allowed distance radius. However,
each player can only hear a message once every two cycles from its teammates, therefore,
sending more messages than what can be heard does not affect the communicative ability
of the team.
The referee also makes announcements about the state of the game such for fouls, kick-
ins, and offsides. All players, by default, hear all referee messages without limitation.
Each player also hears its own messages, but a player’s own messages do not impose any
Agent Actions
Agents can move in the simulator world based on their stamina, which is an exhaustible
resource. The Soccer Server decrements the stamina of a player that sends a command to
run, but the player can recover part of that stamina every cycle, and especially while it is
not moving and hence not expending more of its existing stamina.
turn( relative angle ) : This command turns the body of the player, but the exact
amount of the turn is determined by the current speed of the player and is given by
the formula,
relative angle
actual turn angle =
1.0 + (inertia factor × current player speed)
61
where inertia factor is a constant specified in the input configuration file. Therefore,
the actual turn angle will be smaller if the player is moving fast than it would be if
the player were stationary. The standard range of the relative angle is [-180 . . . +180]
degrees.
turn neck( relative angle ) : Unlike the turn command, the turn neck command is
not affected by the speed of the player. After this command is executed, the head of
the player is turned by the indicated amount relative to the body of the player. The
standard range of the relative angle is [-90 .. +90] degrees. The turn neck command
can also be executed within the same simulation cycle as dash, kick or turn.
neck direction
neck angle
body direction
(−)
(+)
Player
Figure 2.2: Neck angle, body angle, and direction conventions for clockwise and
counterclockwise angles
Figure 2.2 shows the direction of the body and that of the neck and the angle
dash( power ) : The player uses the dash command to run in the current direction of its
body. As mentioned earlier, the effect of a single running command is decayed after it
is executed. Therefore, for sustained running, the player must send dash commands
in several consecutive cycles. However, it is not possible for a player to keep running
reverse to the current direction of the body is also possible with a negative power
value; however, negative power values consume twice as much stamina. The dash
62
command is the only command that consumes stamina.
kick( power, relative direction ) : The kicking command accelerates the ball in
the specified direction that is relative to the direction of the body. The player is
allowed to execute a kick if and only if the ball is within a certain distance from the
player. Otherwise, the kicking command does not affect the ball.
The strength of the acceleration is determined by a formula (See [Chen et al., 2002])
that takes into account the power value and how close the player is to the ball. The
closer the player is to the ball, the harder the kick will be.
catch( relative direction ) : A goalie can use this command to catch the ball,
which must be within an area defined by a standard length and width and the
direction argument to the command relative to the current body angle. Figure 2.3
left of the current body direction of the player. If the player sends (catch -60), it will
catch the ball. The values for the length and the width of the region within which the
player can catch the ball are among parameters specified in the input configuration
file.
h
widt
gion
le re
cat chab
0
1 001
11
00
11 0
0
1
0
1 00
11 0
1
00
11
00
11 00
110
1
00
11 00
11
00
11
1
0
0
100
11 00 00
11
00
11 11
00
11 11
00 catchable region
ball
catc
−60 degrees
habl
e reg
body direction
(−)
ion l
engt
11111111111111111
00000000000000000
00000000000000000
11111111111111111
00000000000000000
11111111111111111
h
00000000000000000
11111111111111111
00000000000000000
11111111111111111
00000000000000000
11111111111111111
(+)
Player
Figure 2.3: An example of ball catching in simulated soccer. The the player can catch the
ball if it issues the command, (catch -60)
63
move( x, y ) : This command moves a player to position (x,y) on the field. The Soccer
Server provides a side-independent coordinate system for each team to place their
players on the field at the beginning of a game. This convention is given in Figure 2.4.
In both cases, the middle of the field is the origin, (0,0), and the positive x-axis
extends towards the opponent’s goal. The y-axis of a team is at 90-degrees clockwise
from its positive x-axis. Due to this relative convention, for the left team, the x-axis
extends to the right, and the y-axis extends downwards as shown in Figure 2.4(a).
Similarly, the x-axis of the right team extends to the left of the field, and the y-axis
(0,0)
x−axis
y−axis
y−axis
x−axis
(0,0)
Figure 2.4: Soccer Server field coordinate conventions for left and right teams. The large
arrows indicate the direction of the opponent’s half. Note that the coordinate system of
the right team is a 180-degree rotated version of that of the left team, or vice versa
64
The move command can be used in three ways: (1) A player can place itself on the
field before the game starts, or (2) a goalie can move anywhere within the goalie box
after it catches the ball but only a fixed number of times after each successful catch,
or (3) a coach can move any movable object to anywhere on the field at any time,
We chose the Soccer Server, the RoboCup soccer simulator environment, as the testbed for
our multiagent learning approach. Soccer Server provides a rich domain that is highly
dynamic, complex, and uncertain. The game of soccer is also naturally suited to being
to be successful. In addition, they have to overcome the noise in their actuators (turning,
kicking, moving) and sensors (visual perception) as much as possible. They also have to
operate well without requiring extensive communication, since the simulator environment
places strict limitations on how frequently each agent can communicate and how much
bandwidth each message can use. Each agent also has to reason about resources,
particularly about its stamina, which is reduced when a player runs. 3 Finally, the highly
dynamic nature of soccer requires fast action times. Therefore, deliberation and reactivity
have to be balanced. For these reasons, we believe the Soccer Server is very suitable for
2.11 Summary
Even though all multiagent systems share the same broad set of issues such as architecture,
and communication, the emphasis varies according to the environment for which a system
65
multiagent system to the exclusion of others that are closely related to the main goal.
For this reason precisely, we first presented a historical perspective on where multiagent
systems fit in the broad family of AI systems. This chapter also discussed a variety of the
aspects of AI systems that closely relate to our aim in this thesis. The next chapter will
66
Chapter 3
Methodology
This dissertation investigates the problem of how we can enable a group of goal-directed
autonomous agents with shared goals to behave collaboratively and coherently in complex domains
that are highly dynamic and unpredictable. In this chapter, we present our approach to this
our approach experimentally in the RoboCup Soccer simulated robotic soccer environment
This chapter is organized as follows. Section 3.1 describes the motivation for symbolic
Section 3.4 discusses the primary algorithms we use in our work. Section 3.3 and Section 3.4
together form the bulk of this chapter. Section 3.5 describes the method we use to evaluate
the performance our the approach. Section 3.6 describes the experimental setup we used
for learning and testing. Section 3.7 describes the plans we used to demonstrate our
learning approach in this research. Section 3.8 is a summary of work closely related to
our approach. Finally, Section 3.9 summarizes the ideas presented in this chapter.
A set of agents and the environment in which they are situated form a complex system. A
complex system is one whose global behavior cannot easily be described by a subset of its
67
true features. This difficulty of description is mainly due to the non-determinism, lack
systems [Pavard and Dugdale, 2000]. Because of these difficulties, the dynamic nature
of the interactions of agents with the environment and the interdependent interactions of
agents with each other cannot be described fully in complex domains. Instead, designers
of AI systems manually choose the features that are considered most essential to modeling
the overall behavior of that system, and then they base solutions on those chosen features.
The fundamental problem of complex systems is the exponential growth of the state
and action search spaces in the number of agents. This means that solution methods that
work with a small number of agents may not scale up to larger-sized problems with more
agents, concepts that need to be learned may continually shift as other agents themselves
Since real-life complex systems are dynamic and unpredictable, problem solving
capturing the critical features of the domain to create adaptable systems than a non-
learning approach.
Because we are dealing with complex environments where agents pursue long-term
goals, the learning approach has to implement a balance between reaction and deliberation.
Commitment to long term goals is essential for a multiagent system [Bratman et al., 1988],
and, at the same time, agents need to be able to react to dynamic events in order to be able
about the state of the world within a very short window of time. However, an agent views
its environment only from a local perspective. So, even if it is theoretically possible to
68
construct a more global view of the environment by exchanging local views among several
agents, it may take relatively a long time to construct such a global view. During this time,
the environment may change in significant ways to render that global view only partially
correct or relevant. If we take into account that factors such as communication bandwidth,
opportunities for message exchange among agents, and communication reliability may be
severely limited in a real environment, we can conclude that the adaptability effort cannot
afford to require that each agent have a global view of its environment. Even if a global
view can be built, it will still be unclear whether having to deal with the resulting larger
An added difficulty in real-world systems is the noise in the sensors and actuators
of each agent and the uncertainty in the environment largely due to external factors that
are difficult to predict. An agent’s sensors provide only a local view of the environment,
and, moreover, the information they provide is imperfect. Actuators do not necessarily
execute each command flawlessly to bring about the intended changes without any margin
of error. Conditions external to an agent may also affect the outcome of each executed
actuator command.
can exhibit collaborative goal-directed behavior. However, such a system would have
only limited adaptability, and it would be unable to improve its behavior over time.
Such a system would require a large amount of a priori knowledge of all states it can
planning and reaction approach could conceivably provide a solution. However, it would
also have limited adaptability. One prevalent problem in all these non-learning approaches
is the need for a method to capture the fine details of each specific situation with both
its dynamic context description and the associated action sequences from each involved
agent’s perspective. Therefore, we believe a learning approach that enables each agent to
learn context descriptions and effective action sequences in a situated fashion can provide
69
a better solution to multiagent problem solving in complex, dynamic, and uncertain
that needs to operate in a complex environment has to address the critical challenges posed
by large search spaces, noise and uncertainty, and concept shifts to achieve adaptability in
realtime.
3.2 Overview
agent has to decide on what action to take next in service of the relatively long-term
goals of its team while reacting to dynamic events in the short-term. Adaptability in
dynamic and uncertain environments requires that each agent have knowledge about
which strategies to employ at the high level and have knowledge about action sequences
that can implement each chosen strategy at the low level in different situations and despite
potentially adverse external conditions. Moreover, agent actions must be coordinated such
that collaboration is coherent. The knowledge required for these tasks is unfortunately
manually. With learning, on the other hand, agents can have the continuous ability
scenarios.
In this dissertation, we target complex, dynamic, and uncertain domains where agents
need to work in teams towards common goals. Such environments can change very
quickly, and therefore, they require fast or realtime response. We assume that agents
can sense and act asynchronously. Each agent operates and learns autonomously based
on its local perspective of the world. We assume that the sensors and the actuators of
agents are noisy. Agents cannot obtain precise information about their environment using
their sensors, and they cannot affect their environment in exactly the intended ways at
70
all times. Since the environment has uncertainties, the results of agent actions cannot be
reliably predicted. Therefore, building a model of the environment and the behavior of
other agents (whether these are agents that the current agent needs to collaborate with or
not communicate due to bandwidth limitations and communication channel noise. Yet we
require that agents manage to work collaboratively with each other in a team and learn
to perform tasks in situated scenarios with possibly other agent groups with different or
In recent years, Reinforcement Learning (RL) techniques have become very popular in
multiagent systems research. The RL approach is suited for sequential decision making
since it allows agents to learn policies based on the feedback they receive from the
environment in the form of a reward signal following each action execution. As an agent
executes its actions, RL allows it to adapt its behavior over time via the reward signal.
Over many training iterations, each agent learns a policy, which maps the environment
states to its actions. However, this standard RL formulation does not directly apply to
complex real-world domains. Therefore, the standard formulation has been modified by
some researchers to make RL applicable to realistic multiagent systems [Stone and Veloso,
1999; Matarić, 1991, 1996]. Despite the modifications, these approaches still suffer from a
set of problems that make them difficult to learn complex policies and scale up to problems
Bottom-up techniques such as RL require convergence for the stability of the learned
policy. Convergence means that these techniques learn only one policy [Matarić, 1991].
In complex domains, however, it is very difficult for such a policy to cover all aspects of
agent behavior. It is rather the case that a very restricted set of tasks can be learned using
such techniques for a relatively small group of agents. These problems emanate mainly
In multiagent learning, the state space grows exponentially with the number of agents
introduced into the environment. Since a RL method has to search the entire search space,
the exponential growth of search spaces is detrimental to convergence even when search is
71
limited to the local view of each agent. Therefore scaling up solutions to larger problems
is very difficult. One other related problem is that emergent learning techniques have
to handle concept shifts. As an agent learns, the policy it has learned so far has to be
continually adjusted to account for the changes in the behavior of other agents due to their
own learning. This is especially the case in adversarial environments [Stone, 1998]. Also,
in RL, the policy to be learned is only implicitly defined by the reward function. Thus the
search for a policy or a behavior is much less constrained than it is in our focused search
approach, and this lack of top-down control makes these approaches more difficult to scale
up.
human users who are possibly experts in a domain [Sevay and Tsatsoulis, 2002; Myers,
1996, 1997]. A plan is divided into distinct steps, and the task in each step is divided among
a set of roles. Each role initially represents only the necessary conditions for executing and
of a plan step. Therefore, collaboration is implicit in the definition of plans. A plan, does
learning is to acquire this knowledge from situated experiences to enable the execution of
What is new in our approach is that we use symbolic high-level multiagent plans
to constrain the search from top-down as agents learn from bottom-up. The MuRAL
approach deals with large search spaces by constraining the learning task of each agent
to the context of each explicitly defined reactive multiagent strategy such that each agent
knows what specific aspects of the environment it needs to account for in order to learn
how to implement its responsibility for each plan step. Since each plan is divided into
distinct steps for each role, learning is further compartmentalized to the perspective of
each agent that assumes a given role in a plan. Hence, search constraining at the top level
72
and learning at the low level complement each other and help reduce the search space.
Using explicit plans makes it possible to concentrate the learning effort of a group agents
on filling in the dynamic details of their plans to implement given strategies, rather than
that, in the MuRAL approach, agents do not learn policies. Rather, they use learning
to acquire implementation details about given plans. Agents acquire action knowledge
in order to operationalize plans and collect reinforcement information regarding their plan
execution to be able to choose the most useful plans to apply in future situations, and,
within each chosen plan, to pick the most appropriate implementation for each plan step.
Learning in our approach is divided into two phases. In the training phase, agents
acquire knowledge to operationalize each plan step in various situations. These training
scenarios are situated but controlled, and agents use no communication. To acquire
operationalization knowledge for each plan step, each agent uses best-first search and
case-based learning (CBL). Best-first search is used to find alternative sequences of high-
level actions that solve the goal of a plan step in a certain situation. A description of each
situation and an action sequence that solves the problem in that situation are stored as a
case in the local casebase associated with the corresponding plan step. The operators used
in the search correspond to high-level reactive behavior modules rather than primitive
actions. Besides reducing the search space, the use of high-level behavior modules enables
In the application phase, each agent selects a plan and attempts to execute it to
While executing a plan, each agent collects reinforcement depending on the success or the
failure of each plan step as well as the entire plan. To apply a given plan step to the current
situation, an agent retrieves all similar cases from its local casebase of the current plan step
and selects one non-deterministically. The probability of picking a given case is a function
of the success rate of that case, and cases with higher success rates have higher probability
73
of being selected for execution.
An agent deals with the uncertainty in its environment by reinforcing plans and plan
step implementations from its own experience such that successful implementations get
favored more than the unsuccessful ones over time. If an agent applies a plan step
successfully, then that plan step gets reinforced positively for the corresponding role. If
the application fails, the plan step receives negative reinforcement. When all steps in a
plan are successfully applied, then the entire plan is reinforced positively. In case all plan
steps cannot be applied successfully to the current situation, then the plan gets negatively
reinforced and the plan steps until the failure point keep their reinforcement assignments.
Since agents do not communicate during the application phase, coherence among agents
dynamic, and uncertain environment is very costly and likely prohibitive to coherent
behavior. Agents would have to exchange multiple messages before deciding which plan
to execute and how to distribute each multiagent task among themselves. Since different
sets of agents can potentially execute a plan in a given instant, choosing the exact group
of agents would require some form of negotiation. However, the number of messages
that would need to be exchanged among agents before a final decision can be made
would disable reactive behavior in dynamic environments and severely limit scalability.
Therefore, our approach does away with any message exchange, and, instead, each agent
evaluates the progress of each plan to the extent of its sensing and reasoning capabilities.
The MuRAL methodology makes the assumption that a user can provide high-level
plans to guide the solution process. A plan describes only the necessary parts of the
agents. A plan is divided into distinct consecutive steps, and each plan step specifies a
set of roles that need to be filled by the agents that commit to executing that plan. A role
74
describes the necessary conditions for execution and termination of a given plan step and
the responsibilities that an agent contributing to that plan step must take on.
Each plan step specifies what needs to be operationalized from each role’s perspective
but does not specify how to do so. Therefore plans are designed to guide the system
behavior rather than dictate all runtime details, which can potentially have infinite
variation in a complex domain. It is then the job of the multiagent system to automatically
learn, through training in a situated environment, the fine details of how to operationalize
Plan step N of P
Plan P
START N=1 Match step N assign roles
1 operationalization
3 effectiveness check
Yes
End of
No plan? Yes
A MuRAL system operates and learns in two phases. The first phase is the training
phase, where, given a plan, each agent acquires action knowledge to operationalize its
responsibilities described in that plan by the role it assumed. The second phase is the
application phase. In this phase, each agent executes a given plan that it has already learned
to operationalize during training. The agent learns which steps in that plan are more
effective than others using a naı̈ve form of reinforcement learning. Figures 3.1 and 3.2
The training phase shown in Figure 3.1 is made up of two parts that are interleaved.
In the operationalization phase, the goal of the multiagent system is to operationalize each
75
Plan step N of P
Plan P
START N=1 Match step N assign roles
1 solution retrieval
RL 3 effectiveness update
Yes
END
N=N+1
End of
No plan? Yes
step of a given plan from each agent’s perspective, thereby operationalizing the entire
plan after all steps are completed (marked as 1 in Figure 3.1). In the feedback phase, the
agent executes the solutions of the reasoning phase in the actual environment and checks
both whether each plan subpart has succeeded to implement the desired subgoal and
whether the entire plan has succeeded or not (marked as 2 and 3 in Figure 3.1). The
agent stores the working solutions in each plan step so that those solutions are available
for the application phase if training succeeds for the entire plan. A training episode ends
either when the entire plan has been successfully applied or a failure occurs. At each plan
step, the agent executing a given plan assumes a fitting role for itself and assigns roles to
other agents it is collaborating with. These role assignments are internal to each agent and
The application phase shown in Figure 3.2 also comprises two interleaved parts.
The solution retrieval phase in application involves matching the current situation to the
knowledge content of an agent so that solutions acquired during training can be used to
solve similar problems (marked as 1 in Figure 3.2). The feedback phase of application is
similar to that of training. In application, an agent may access a given piece of action
knowledge many times, thereby modifying its effectiveness status over time (marked as
76
2 and 3 in Figure 3.2). In addition, the application phase tracks the effectiveness of each
executed plan. A plan may fail at any time, but it will only succeed if all steps in that
plan have been successfully completed. This feedback collected over a series of situated
tests allows agents to select more effective plans and plan implementations. Therefore, the
system learns in both the training phase as well as the application phase.
copies of skeletal
plans with a single merged plan
plan, P, for each role with non−reinforced
non−reinforced
application knowledge application knowledge
APPLICATION
P1 TRAINING (Retrieval)
P2 Plan
TRAINING Merging
APPLICATION
Pn TRAINING (RL)
Figure 3.3 summaries the MuRAL methodology. The system starts with identical copies
of a given skeletal plan, P . Each agent collaborating to execute P has its own copy of P
for practical purposes. After each successful training trial, each copy of P , P1 , P2 , . . , Pn ,
will contain potentially unique knowledge for executing P in a specific situation. Since
this knowledge has not yet been used during learning, it is non-reinforced. After merging
the knowledge from all successful trials for P , we obtain a single operationalized plan that
contains all the knowledge for all roles. This single plan can then be used for retrieval or
learning. Since retrieval does not modify plans, each given plan stays unchanged at the
end of retrieval. RL, on the other hand, modifies the operationalized plan it started with.
77
3.3.1 Case-Based Learning and Naive Reinforcement Learning
Since dynamic environments continually change, an agent may be able to predict future
events only within a very short time window, and the number of possibilities to consider
during the next action decision is very large in a complex and highly dynamic domain.
Therefore, agents cannot afford planning a relatively long sequence of actions to execute in
the very near future. Generating plans in the traditional planning sense is also impractical
since an agent cannot predict all events in the future and cannot afford to plan for every
1988; Wilkins, 1984] is also not suitable, because an action sequence discovered during
search cannot be guaranteed to work in the real environment. However, agents have
to be able to make progress towards their goals by keeping their commitments to the
plans they have selected to execute as much as possible [Bratman et al., 1988]. Since
agents need to operate in a dynamic environment, each agent can afford to plan relatively
short sequences of actions at each decision point, unless the environment happens to
change at a rate that renders any reasoning useless. Then the agent can test these short
plans in the real environment to find out if they work under the conditions they were
generated for. The agent can retain the working action sequences and the corresponding
situation descriptions in its memory. Without feedback from the environment, however,
scenarios. This is the reason why the MuRAL approach relies on the feedback that agents
In order for reasoning to take place, any given domain must be assumed static at
some time scale and for some duration. That is, we have to make a temporally static world
assumption. This assumption only facilitates reasoning, but it does not guarantee that the
action sequence an agent discovers will necessarily serve its intentions. The reason for
this lack of guarantee is the complexity and the uncertainty of the domain. The agent
cannot predict the future states of its local environment entirely even if it can make some
An agent can make the assumption that all other agents, including its group members
78
and others, will behave in the same manner in similar circumstances. However, in order
to make predictions about the actions of other agents, the agent has to take into account
the interdependencies among the agents, since agents in a multiagent system frequently
base their decisions on the behaviors of others. Reasoning about interdependencies is,
however, an infinite regression problem, and, even at limited depth, it would be too costly
For efficient behavior in a complex system, each agent needs to have three types of
1. Action Sequencing: Suppose that we are given that plan P expresses some strategy G.
For each subgoal g of G, the agent needs to a determine a sequence of actions, s, that
will solve g under the temporally static world assumption in some situation c. That is, s
is an operationalization of g under c.
2. Subgoal Application Feedback: The agent needs to know that a given action sequence s
can efficiently solve subgoal g in the actual environment under c. If there are multiple
action sequences that are applicable to g under c, then the agent can pick one from
3. Strategy Application Feedback: The agent needs to know that applying P in similar
G, given the action sequences and feedback retained for its subgoals.
Action sequencing requires reasoning and uses the world model that each agent keeps
in its memory, and it takes place during the training phase of an agent’s operation. Feedback
about subgoal and strategy application, on the other hand, has to do with first-hand
interaction with the environment since agents execute actions in situated fashion, possibly
interacting with other agents in the process. Both feedback processes take place during the
application phase.
Since the entire dynamics of a complex system cannot be expressed in a formal model,
it is critical for each agent to test the action sequences it generates during reasoning in
the actual environment. In this way, the dynamics of the environment that is relevant to
79
the current subgoal g can be captured by the test and summarized by whether the action
sequence in question has solved g or not. Without any feedback from the environment, the
agent cannot know if a given action sequence s can potentially solve the current subgoal
g or a certain plan P can implement strategy G under the current circumstances. So, for
example, if the agent generates n different alternatives in the action sequencing step, it
will not know which to pick, since all alternatives will seem equally valuable. Therefore,
In action sequencing, each agent retains action knowledge about a given subgoal, and,
in the second step, it retains feedback about the application of its action knowledge from
the first step. This means that, in order to apply a plan in the future, the agent has to be
able to identify which action sequences are appropriate for the current situation. In short,
search problem [Korf, 1987]. We use best-first search [Rich and Knight, 1991] with domain-
specific heuristics to implement this approach. The search operators we use in the best-
first search represent high-level reactive behaviors rather than primitive actions. We
call these high-level reactive behaviors reactive action modules (RAMs) and discuss them
further in Section 3.3.5. For example, in the simulated soccer domain, passing the ball
primitive actions whose exact makeup and parameter values are highly dependent on the
as search operators as opposed to primitive actions reduces the search space considerably.
primitive actions, since runtime conditions will require reactions that an agent could not
possibly plan for in advance. The search heuristics we use bias the search towards finding
the shortest possible sequences of actions. However, that an action sequence is the shortest
possible that can be found is not by itself a guarantee for success in the actual environment.
80
We formulate this step as a naı̈ve reinforcement learning problem, where the statistics of
past successful or failed applications of action sequences are used to distinguish among
as RL [Sutton and Barto, 1998]. The purpose of naı̈ve reinforcement learning is to enable
agents to choose plan step implementations from among the most useful ones in past
similar situations. In our approach, this selection is based on the success rate of plan
succeeded in the current situation and negatively reinforces it if it failed. The dynamics
of a complex and uncertain environment, however, require more refined reasoning so that
R 6 S
243)576
RETRIEVE
1
8 96 3;:=<>69? R 6 S
243)576 G 6 LN:=IQ69EF69? 23)576
243)576
RETAIN 4 2 REUSE
MuRAL uses case-based reasoning [Tsatsoulis and Williams, 2000] to select plans by
matching plans to situations (See Section 3.3.6). It uses case-based learning [Aha, 1991;
Aamodt and Plaza, 1994] to match plans to situations at the high-level and match action
sequences to implement each plan step at the low-level. According to [Aamodt and Plaza,
81
1994], the case-based reasoning (CBR) cycle is composed of four steps, as depicted in
Figure 3.4: 1
2. Reuse: Use the information and knowledge in retrieved case(s) to adapt a solution
for the current problem. The solutions at this stage are only suggestions, since they
3. Revise: Evaluate the new proposed solution by applying it in the real environment
and possibly repair the solution to make it fit to the current situation. After this step
from the Reuse step has been successfully applied to the current situation.
4. Retain: Store the useful parts of the new solution that are likely to be reused in
A new problem is introduced into the CBR cycle as a new case. After a similar case is
retrieved from the casebase (Retrieval), the solution in that retrieved case is a suggested
solution for the new problem. This suggested solution is then applied to the current
situation in the Revise step. The purpose of CBL in MuRAL is to enable approximate
situation matching and hence deal with the search space complexity. In a complex and
dynamic environment, all aspects of physical situations cannot be defined in exact terms.
For example, the position of an agent in the world cannot be expected to be identical in
In MuRAL, following this testing in the real environment, a retrieved case, in general,
successful or not. Then, in the Retain step, this modified case is stored back in the case
base. Besides using the casebase, an agent may also use other general-purpose or domain-
specific knowledge at any stage during the CBR cycle. It is important to note that the CBR
1
The figure was adapted from [Aamodt and Plaza, 1994] with minor modifications.
82
cycle does not apply to the training phase as in regular CBL, since new cases are learned
only through training by storing them directly in the casebase [Aha, 1991]. Thus, the CBR
cycle in Figure 3.4 applies only to the application phase of an agent’s operation.
The action sequence in a case is determined by a best-first search [Rich and Knight,
1991] (see ) and how this sequence is used during the execution of the corresponding plan
step is critical to the operation of a MuRAL agent. First, this action sequence is stored
in a case in summarized form. Let us consider the example in Figure 3.5 where agent A
is in grid square (4, 1). Let us suppose that the solution to a problem A currently faces
involves agent A moving left by three grid squares, moving up by two grid squares,
moving left by one grid square, and finally moving up by one grid square. That is,
this solution sequence moves agent A from grid square (4, 1) to (0, 4). The exact action
sequence S = {MOVE TO(3, 1), MOVE TO(2, 1), MOVE TO(1, 1), MOVE TO(1, 2), MOVE TO(1, 3),
MOVE TO(0, 3), MOVE TO(0, 4)} will have been determined by search.
5
A’
4 goal
2
A
1 start
0 1 2 3 4 5
Even though the sequence of actions in S represents the theoretical solution to the
problem A faces, it is inefficient to store all seven moves in the actions slot of a case.
Second, and, more importantly, it is inefficient to force an agent to execute the exact action
sequence discovered by search, since doing so ties the agent down to too specific an action
set to successfully execute in a situated environment. Therefore, instead of storing all seven
moves, the agent stores a summary of them. In the case of the example, the summarized
83
In a summarized sequence, any static decisions taken during search are dropped
such that the essential actions remain. The purpose of doing this is so that the agent,
at execution time, is given the most abstract goal specification sufficient to implement
the goal expressed in a given action sequence, thereby allowing the agent with as much
runtime flexibility as possible. That the search had discovered a sequence 7 actions long
to solve the problem does not mean that the same exact action sequence needs to be
executed in the actual environment for the successful implementation of the postcondition
of the current plan step. Actually, following the exact sequence discovered during
search constrains the agent and may even cause failure rather than success in a situated
environment due to being overly specific. Therefore, the idea is to keep only what is
essential of the results of search so that the runtime flexibility of the agent is maximized.
Since the agent will have to make dynamic judgments about how to go from grid square
(4, 1) to (0, 4), it may have to avoid obstacles on its way. So it is not even clear that agent
We have to remember that the world description given as input to the search algorithm
is assumed to be temporally static. Moreover, the search operators need not implement
the details of the corresponding actuator commands that will be used by the agent to
implement action sequences in cases. In fact, this would not have been practical also,
because of the dynamic decisions that agents need to make depending on the context of
the situations they face every moment. A real robot, for example, would have to execute
turns in order to travel to the location suggested in Figure 3.5, and it would likely have to
adjust its speed during the straightaway portions of its planned navigation path. However,
none of these considerations need be part of search, since they will have to be dynamically
decided on.
the training phase [Rich and Knight, 1991]. The search is done in a discretized version
of the world where locations are expressed in terms of grid squares rather than exact
84
(x,y) coordinates. We use the following search operators and heuristics to compute an
estimation, f 0 = g + h0 , of how close a given search node is to a goal. The g value is always
position or area. When we consider these operators, we use the following heuristic
First, we compute a proximity heuristic for each player in the influence area of a
rotation:
m = manhattanDistance(P, pi )
player cost
cost pi =
adjacency 2pi
where player cost is a standard constant cost of a regular player set to 2.0. If
4. Finally, the summation of all player costs gives us the value of the proximity
heuristic:
n
X
h1 = cost pi
i=1
85
After computing the proximity heuristic for each player in the influence region of the
1. First, we compute the distance, d, from P to the target point or area (using the
h2 = d2
3. Third, if the operator being considered will undo the effects of the previous
undoCost = 1000
h0 = h1 + h2 + undoCost
• Operators InterceptBall , and PassBall are independent of any target coordinates and
are always the last action targeted by search. Therefore, their h0 value is set to 0.
An agent in a MuRAL system operates autonomously and makes decisions based only
on its local view of the environment. The architecture of each MuRAL agent is hybrid,
with both deliberative and reactive components. Figure 3.6 shows the architecture of a
MuRAL agent where arrows indicate the interaction between components and the agent’s
Sensors collect information about the environment, and the Actuators execute the
actions that the Execution Subsystem determines using instantiated plans from the Plan
86
Environment
Learning Subsystem
Actuators
Sensors
World Model Plan Library
Execution Subsystem
Agent
Figure 3.6: The hybrid agent architecture in MuRAL
Library. The World Model represents the agent’s knowledge about the world. It contains
both facts available via the sensors as well as those derived by reasoning about the sensory
information. The information that the World Model stores is temporal. Over time, through
sensing, the agent updates its information about the world, and, to overcome as much as
possible the problem of hidden state, it projects facts from known information. Each piece
of information in the world model is associated with a confidence value. A newly updated
piece of information has a confidence of 1.0, meaning completely dependable. The agent
decays the confidence value of each piece of information that does not get updated at
each operation iteration, and below a fixed confidence threshold, a piece of information is
considered unreliable, and it is forcibly forgotten so that it does not mislead the reasoning
of the agent. This idea and similar fact decaying ideas have been used in recent systems
(e.g., [Noda and Stone, 2001; Westendorp et al., 1998; Kostiadis and Hu, 1999; Reis and
Lau, 2001]).
The Plan Library contains all the plans that are available to a given agent. Each agent has
its own unique plan library. Plans in different plan libraries may contain identical skeletal
plans at first, but, after the training and application phases, the application knowledge and
the reinforcements of cases in each plan will depend only on the experience of each agent
87
in its situated environment.
Both the Learning Subsystem and the Execution Subsystem interact with the Plan Library.
The Execution Subsystem accesses both the World Model and the Plan Library, but it can
only modify the World Model. The Learning System both accesses and modifies the Plan
Library, and it indirectly uses the World Model via the requests it makes to the Execution
Subsystem. The Execution Subsystem then modifies the state of the Learning Subsystem in
order to affect the Plan Library. The Execution Subsystem receives sensory information
from the environment and updates the World Model of the agent. It is also responsible
As Figure 3.6 indicates, the Execution Subsystem is the main driving component of the
MuRAL agent architecture. It interacts with the world via Actuators and Sensors. Its
purpose is to select and execute plans in the environment during the lifetime of the agent
both during the training and the application mode of an agent. Since it interacts with the
In MuRAL, plans and cases are represented symbolically. Cases are a natural subpart of
plans, but, since they constitute a critical part of plan representation, this section discusses
the two data structures separately. Figure 3.7 shows the top-level representation of a plan.
Plan Representation
A plan, P , is represented by a tuple hN, S, F, Bi. N is the name of the plan, assumed to
be unique in a given plan library of an agent. S and F are counters that represent the
positive and negative reinforcement for P through the individual experience of a given
agent that applied P . Since their is no communication among agents, each agent updates
S and F independently based on the conditions in P and its perspective on the world. S
stores the number of times P was successfully used, and F stores the number of times P ’s
88
executed in order as shown in Figure 3.7. The work involved in each plan step is divided
among roles, each of which must be fulfilled by a different agent in an actual situation. Each
role is associated with its own preconditions, postconditions, and knowledge for each plan
step.
Each plan step, s, is represented by the tuple hC, E, Ai. C is a set of conjunctive
that describes the postconditions of s. Both preconditions and postconditions may contain
applicable to only the plan step it is associated with. As Figure 3.7 depicts, the application
knowledge is partitioned among the roles associated with a given plan step and therefore
Both the preconditions and postconditions of a plan step are represented by a tuple
hV, ti. V is a list of perspectives for each role that is responsible for learning that plan step.
t is the timeout for how long a precondition or a postcondition should be checked before
Each perspective for a role in a plan step is represented by hA, Ci where A is the name
of the role and C is a conjunctive list of conditions. A plan has only one perspective per
role, and the perspective of each role describes the conditions that must be satisfied from
Figure 3.8 from the soccer domain. Suppose we have a two-step plan that requires three
teammates in regions R1, R2, and R3 to pass the ball among themselves starting with the
player in region R2. In the first step of the plan, player in region R2 is expected to pass the
ball to the player in region R1, and, in the second step, the player in region R1 is expected
In order for this plan to be activated, there must be three teammates that happen to be
in regions R1, R2, and R3. The player in region R1 will take on role A, the player in region
R2 will take on role B, and the player in region R3 will take on role C.
89
Start
End
PLAN
Therefore, in step 1 of this plan, player B must have the ball and must know that player
A is in region R1 and player is in region R3 in order to start executing the plan. Similarly,
player A needs to know that there is a teammate with the ball in region R2 who will take
on role B and a second teammate in region R3 who will take on role C, while it takes on
role A. The player in region R3 must also know that the player in R2 has the ball, and
there is a second player that resides in region R1. In the second step of the plan, player C
must know that player A has the ball and is in region R1, and player A must receive the
ball and know that C is still in region R3 before it can pass the ball to C. As this example
demonstrates, each step of a plan is described from the perspective of individual agents
such that each agent can know how to contribute to the overall success of a given plan.
90
player C
R3
player A player B
1
0
0
1
0ball
1
R1 R2
Figure 3.8: An example plan for a three-player plan from the soccer domain where each
player needs to check conditions specific for its own role in that plan
MuRAL postconditions are treated differently from STRIPS postconditions (add and delete
plan step. If the postconditions of a plan step for a role are satisfied, it means that plan
step has been successfully applied. If the postconditions time out, it means that the plan
Since agents need to operate in dynamic environments that are potentially affected
by the actions of other agents (and possibly by the environment), we do not represent
plans at the lowest possible detail, i.e., using the primitive actions available in a domain.
The reason for this is that each plan step may require multiple reactive actions on
the part of each agent involved in executing that plan step, and these actions can, at
best, be determined at runtime. Instead plans represent only the critical outcome (i.e.,
postcondition/goal) expected of a plan step and have each agent decide on the particular
reactive actions to implement each plan step at runtime in different circumstances such
that the learned cases provide a wider coverage of the external search space involved. To
decide on what series of actions each agent should execute to implement a plan step in a
particular situation, agents use a form of reinforcement learning. Section 3.3.5 describes the
relationship between search operators and high-level actions that are used to apply plans
91
Case Representation
A case stores role- and situation-specific information about the implementation of a given
plan step. The role specification partitions the casebase for a plan step, and the index in
each case for a given role enables situation-specific matches. This partitioning is important
for generality of representation, since an agent may be trained on different roles in a plan.
If such training occurs, the agent will acquire cases for each role, and, during application
of the learned action knowledge, there needs to be a mechanism to associate cases with
The graphical representation in Figure 3.7 shows only the casebases associated with
• Role: The name of role that needs to be fulfilled by an agent during execution. The
assignment of an agent to a role stays unchanged until that plan is either completed
or aborted.
• Index: The description of the external state, i.e., the retrieval index of the case.
• Success count: A counter that stores how many times the current case has been
• Failure count: A counter that stores how many times the current case has been used
• Rotation value: The degrees by which a normalized scenario from the perspective of
a role had to be rotated during training to get a match. This offset angle value allows
the reconstruction of the original match during training such that actions during the
application phase can be oriented with respect to the current situation when relative
92
• Grid unit: The granularity of the discretization of the physical space into grids. For
example, if the grid unit is 3, then all x-coordinate positions within the range [0 . . 3)
• Action sequence: The action sequence that is acquired during learning. This
action sequence solves the subproblem posed by the current plan step for the
current role in question. Its usefulness is reinforced by the success rate given by
inefficient due to the combinatorial growth of the search spaces involved. In order to strike
a balance between deliberation and reaction, our approach uses heuristic search to guide
(but not dictate in detail) what to do next in a particular situation. Therefore, the operators
used during search need corresponding data structures in the Execution Subsystem of the
agent architecture (Section 3.3.3, page 86) so that the deliberative decisions of the agent can
program module called a reactive action module (RAM) in the Execution Subsystem. A RAM is
a computer program that implements the high-level goal expressed by a search operator in
the actual environment using reactive reasoning so that an agent can respond to dynamic
events in realtime. If, for example, a search operator moves the position of an agent by ten
units of distance to the left, then the corresponding RAM would implement this navigation
task, but the implementation of the RAM would possibly involve functionalities such as
ground parameters as depicted in Figure 3.9. In the architecture diagram in Figure 3.6,
this is shown by the wide arrow that joins the Execution Subsystem to the Actuators,
which directly execute these commands. Since a RAM responds to dynamic changes, the
sequence of the primitive commands it outputs will vary from situation to situation.
93
RAM
1
RAM 2 ... RAM
N
p
11
. . . p1k p
21
. . . p2k p
N1
. . . pNk
Figure 3.9: The dynamic decomposition of each reactive action module (RAM) into a
sequence of primitive actions. Each RAM dynamically generates a sequence of primitive
actuator based on current state of the world world.
A RAM may employ other RAMs to handle the contingencies that arise during its
execution. Reasoning about contingencies allows each agent to recover from potentially
problematic situations and keep its commitments to select to execute. In the soccer
domain, for example, a player needs to be close to the ball in order to kick it to another
player. If the player is close to the ball but not close enough to kick the ball, a contingency
occurs, and the RAM that is used for passing the ball calls the RAM that moves a player to
an appropriate kicking position with respect to the ball. When that RAM accomplishes
its goal, control returns to the RAM responsible for passing the ball (See Figure 4.2 in
RAMs also attempt to detect catastrophic failures within their contexts, so that an agent
does not get stuck in an infinite loop. This way, the control is returned to higher levels of
the agent architecture so that the agent may choose a different course of action.
In applying a plan to a given situation, our system uses two stages of matching. The
first stage tries to match the internal state of a team of agents to the preconditions and
postconditions in each plan step. The second stage tries to find a match between the
current external state and application knowledge in the casebase of each plan step.
The system checks whether preconditions or postconditions of a plan step have been
the physical scenario defined relative to the normalized viewing direction of a role in a
94
given plan step. The normalized viewing direction defines a relative axis for recognizing
In the case of soccer, the viewing direction assumed while writing the conditions for
a role in a plan step serves as the x-axis of a relative coordinate system whose origin
is the center of a given player and whose y-axis is 90-degrees rotated counterclockwise
with respect to its origin. The patterns described by a plan condition for a role refer
to the constellation of team or opponent players. The internal state of a team refers to
the constellation of relevant teammates, and, the external state of a team refers to the
R’2 I’
20
I
15
R’3 R’1
10
R3 R2
5
A line of sight
R1
0
0 5 10 15 20 25
Figure 3.10 shows an example of how rotations are used in matching plans to situations
from the perspective of an agent, in this case named A. The rectangles R1 , R2 , and R3
represent areas in which a plan condition expects to find agents that are teammates of
95
((in-rectangle T1 R1 ) AND
(in-rectangle T2 R2 ) AND
(in-rectangle T2 R3 ))
R. This normalized condition is, however, limited to one particular orientation of the
regions with respect to the viewing direction of A. To enable off-view matches, our
approach checks all possible orientations of the normalized condition within a given angle
range of the current viewing direction at discrete intervals on both sides of the current
representation is shown in Figure 3.10. In the figure, regions R10 , R20 , and R30 are 90-degree
For simplicity, regions themselves are not rotated. Instead, only their middle point is
rotated. For example, region R2 is 5 units long and 4 units wide. Its rotated version, R20 is
also 5 units long and 4 units wide. Note also that the condition specifications are in terms
Case Matching
Case retrieval in our system is preceded by the matching of the preconditions of the
corresponding plan step to the internal state of a multiagent team. Then, in a given
situation, a case is selected for application from the local casebase associated with that
plan step based on the external state of the multiagent team. Therefore, the matching of
the smallest rectangular region that contains all teammate regions specified in a plan step
condition. For example, if we suppose that agent A in Figure 3.10 found a match for the
90-degree rotation {R1 , R2 , R3 }, then the influence region of this rotation would be the
area labeled I. A strip of area around this influence region is very relevant for successfully
executing the current plan step, since the existence of other agents may potentially affect
96
the desired outcome. Therefore, to include the relevant region around the influence area, we
consider an expanded version of I, which is marked as I 0 in the figure. Then, the agents
in region I 0 that are not teammates of agent A will constitute the external state description
for this situation. Once the external state description is obtained, then A can compute the
similarity between cases in its local casebase for the current plan step and the external
situation description.
After similarity computation is completed, A has to select the best match. However,
multiple cases may be equally similar to the current situation, and favoring the case with
the highest success to failure ratio would not give a chance to other similar cases. It is
important to note that the application of cases involves reinforcement learning, and, to
have wide coverage of the domain, all similar cases in a situation must have a fair chance
of being selected.
multiple similar cases. The details of this selection scheme are discussed in Section 3.4.3.
For matching cases to situations, we use the external conditions of the environment.
In the case of soccer, external conditions refer to the constellation of opponent players.
Matching at this level happens using influence regions around each opponent player. An
influence region is a discrete rectangular region centered at the player’s current location
and specifies weights that specify a ”strength” of the influence of the player’s presence at
a given grid distance. At grid distance d, the strength weight of a grid, f (d), is given by
Equation 3.1. When the grid distance is larger than 2, the strength is taken to be zero.
f (d) = 0.5 − 0.75d + 2.25d2 if (d ≤ 2) (3.1)
0.0 otherwise
The influence of a given player on a grid at distance d, y(f (d)), is given by Equation 3.2
such that the farther a grid square, the smaller the strength of the influence. For example,
for d = 2, the influence region of an opponent player will have the weights shown in
Figure 3.11.
1
y(f (d)) = (3.2)
f (d)
97
.125 .125 .125 .125 .125
.125 .5 .5 .5 .125
.125 .5 2 .5 .125
.125 .5 .5 .5 .125
Figure 3.11: Influence region of a player in the areas around its position. The grid square
in the middle represents where the agent is currently located. The influence of the player
decreases. Beyond a certain grid distance, the influence becomes zero.
Since matching cases to situations involves comparing the opponent player constellation
in each case to that in the current setting, we sum the influences of both such that
overlapping regions get added. Then we take the difference of the combined influences
at each grid location. Finally, we sum the differences to get a measure of the difference
of the difference by dividing the total difference by the number of the opponent players in
the current situation. To account for the difference in the number of players, we introduce
a penalty value that is multiplied by the difference in the number of opponent players
in a case and the situation being considered. This penalty is the difference we get if the
influence region of a player in a case is not matched by any players in the current situation.
That is, the penalty is the addition of all the weights in the influence region of a single
player, as in Figure 3.11. Then the difference (or inverse similarity) of a case is the sum of
To decide if a given case is similar to the current situation, we compute the worst
difference we can tolerate. This is given by the penalty value mentioned above multiplied
by the number of opponent players in each case. If the difference of a case is less than or
98
3.3.7 Optimality vs Efficiency in Heuristic Search
systems, on the other hand, optimality becomes very difficult to define and achieve.
Therefore, multiagent systems that operate in realistic or real environments aim to solve
problems efficiently but not necessarily optimally (e.g., [Balch, 1997b; Matarić, 1998; Stone
and Veloso, 1999; Briggs and Cook, 1999; Bonet and Geffner, 2001b])
The main reason why optimality is not a main issue in complex domains is the
unpredictability of such domains. In order for agents to design plans that involve
relatively long action sequences that span potentially many state transitions, an agent
needs to be able to predict how the environment and other agents will behave. To predict
the actions of other agents, an agent has to have a model of the decision mechanisms of
other agents. However, even then, the interdependencies among agents can cause infinite
regression.
search, an agent can search using all possible combinations of agent actions. There are two
problems with this approach. The first problem is that combining actions of all agents does
not produce a meaningful representation of what may happen in the actual environment.
In a real world situation, actions of different agents may be interleaved in many ways
since actions are durative and agents behave asynchronously. Therefore, considering all
The second problem is that an agent cannot assume an order on all other relevant agent
actions when searching. That is, an agent cannot reliably predict what other agents will do
so that it can choose the best action possible to execute next. If we make the assumption
that all agents are rational, it is also impractical to assume that each agent is capable of
rationalizing the behavior of all other relevant agents from their own perspectives of the
world. We cannot assume that an agent can observe the world such that it can know
what other agents currently know. In addition, an agent cannot always know the decision
mechanisms or the preferences of other agents to duplicate their reasoning, and neither
99
If an agent uses its own decision mechanisms and preferences as an approximate
make decisions about what to do next. However, unlike in games, an agent operating
in a complex environment cannot afford to wait for other agents to make their moves so
that it can maximize its next move since there is no synchronization or ordering of moves.
Instead, to make progress towards satisfying its goals, an agent has to plan short sequences
of primitive actions based on the current or, at most, the recent set of states of the world.
Hence, in the MuRAL approach, we assume that the world is temporally static for a brief
while into the future so that an action sequence can be found that may work in the actual
environment despite dynamic future changes. Also the agent cannot make assumptions
about how other agents will behave in a utility maximizing way during the brief period
complex domains, the decision mechanisms we implemented strive for efficiency rather
than optimality.
that a collaborative group of agents can potentially affect from those that it does not
or cannot have control over. We refer to the first type as internal conditions or internal
state, and we refer to the second type as external conditions or external state. The rationale
behind this distinction is to enable a multiagent system to select plans at runtime based
on more controllable internal conditions without having to reason about the remaining
less controllable dynamic details of a situation, that is, the external conditions. Then, for
execution, each agent in the multiagent system chooses a solution to apply based on the
external conditions. So we treat the internal state almost as a constant and the external
state as varying around a ground internal state description. Hence, this is a hierarchical
method of filtering in available action options. In the physical world, the relative layout
of the agents in a group can be an important motivator for choosing which plan to apply,
100
and the remaining conditions become details to be worked around. In this document, we
So, for a given set of internal conditions, there can be many sets of external conditions
that need to be handled. The constellation of a team of agents then become part of
the internal state of that team, and the constellation of non-team agents in the same
environment become part of the external state. Since we take internal conditions as basis
for choosing plans, a plan is written only based on internal conditions. Then the learning
component of the system deals with how each agent in a multiagent plan should act in
order to successfully execute each plan step under different external conditions. This
hierarchical relationship between internal and external conditions is shown in Figure 3.12,
where each parent internal condition set is common to all external condition sets associated
with it such that each external condition set forms a unique precondition group with
its parent internal condition set. For example, {I1 , E12 }, {I2 , E2N }, and {IM , EM 2 } are
precondition groups that uniquely identify situations about which an agent would have
In the game of soccer, for example, internal conditions would include the constellation
of a group of players that are teammates, and the external conditions would include the
certain soccer tactic can be used, it would be desirable to have different variations of
applying that tactic such that different opponent constellations can be handled but the
Our hypothesis is that, if each agent in a multiagent system learns how to handle
specializations of the external state from its perspective, keeping the current internal
conditions fixed, it can apply each step of a given plan successfully, thereby successfully
applying the entire plan. In addition, if the agent learns which of the previously learned
operationalizations of a plan step are most effective, it can learn better implementations of
101
internal condition sets
I1 I2 IM
E 11 E 21 E M1
E 12 E 22 E M2
E 1N E 2N E MN
Figure 3.12: Hierarchical relationship between internal and external conditions that
describe the world state
Continuous state and action spaces in complex domains are of infinite size in their natural
form. Even after discretization, search spaces can still be too large to search exhaustively
or heuristically.
For example, the simulated soccer domain is complex and has a very large state and
action spaces. If we divide the field into 1 unit-distance grids, the 22 players and the ball
can have a total of (105×68)23 possible locations. With player viewing direction added and
each dimension discretized in one-tenth steps, each agent could be in any of the (1050 ×
680 × 3600) unique orientations [Stone, 1998, Chapter 2]. If we consider the actions that
are available to all non-goalie players turn, turn neck, dash, and kick, with somewhat
coarse discretization, an agent still has about 300 different instantiated actions it can take
being 100), we will have the following number of instantiations for each type of action:
102
• kick( power, direction): (100/10 = 10) × (200/10 = 20) = 200 action
instantiations
Therefore, for each team, there are 27411 different action instantiations at each decision
cycle. With finer discretization, the number of action options could be as large as 30011
given in [Riedmiller et al., 2002] or much larger. Therefore, limiting the size of both the
search and action spaces is the first requirement in problem reformulation in order to be
In MuRAL, we also discretize the physical space where agents operate into grids. A
grid is a square region of a certain dimension that allows the search space to be reduced.
This grid representation plays an important part in the reasoning and learning procedures
is, we do not assume that an agent can only move between grids.
Figure 3.13 depicts an example case where a grid laid over a physical region represents
the discretized positions of two sets of agents ({A, B, C} and {D, E, F, G}).
G
F B
E D
Figure 3.13: An example grid laid over a region with two teams of agents
The search process for discovering action sequences to apply to a situation and the
cases learned by the system are represented in terms of this grid representation. The action
space is also discretized. With its specific parameters aside, an action in the physical world
can be represented in terms of an angle. In a grid world, there are eight possible direction
103
for an action as Figure 3.14 depicts.
3
0 1 2 3 4
Because of our approach that separates execution from planning, we do not need to use
all eight directions since any grid is reachable from any other grid by moving in the four
non-diagonal directions (north, south, east, west). Therefore, for action sequence search,
The instantiation of a plan requires the assignment of roles in that plan. This instantiation
takes place when an agent matches a plan to the current situation. Action sequences
stored in cases as solutions to the scenario described by that case are normalized (See
Section 3.3.6). Plan step instantiation requires that this action sequence be instantiated
for the current situation. This involves rotating any direction-dependent actions in the
normalized solution definition in the retrieved case for the current situation.
3.4 Algorithms
Algorithm 3.1 gives the learning algorithm, Learn, each agent uses during the training
and application phases of our system. It is used both for learning a new case about how to
104
operationalize a given plan step as well as for applying existing cases to current situations,
thereby acquiring positive or negative reinforcement on the plan and its steps when naı̈ve
• A: The agent that is responsible for learning about a given plan step
• R: The role that agent A will fulfill while learning about plan step step in P
• doSearch, doRetrieval, doRL, doN ewCaseRetain: These four parameters control the
operation mode of the Learn algorithm. They turn on/off whether the agent should
of the system. The doSearch parameter controls whether the learning algorithm
calls its heuristic search facility to discover a sequence of actions to handle the
current problem posed by plan step step. The doRetrieval parameter controls an
agent’s access to the knowledge in that agent’s plan casebases. The doRL parameter
controls whether an agent will modify the failure and success counts in the plan
save cases based on its experiences. During training, for example, doSearch and
doNewCaseRetain are turned on. During application mode with naı̈ve reinforcement
learning, on the other hand, doRetrieval and doRL are turned on.
• E: The description of the external conditions that further define the context for
page 96.
• u: The unit for discretizing the physical space in which agent A is expected to
105
01: Learn( Agent A, Plan P, int step, Role R, bool doSearch, bool doRetrieval,
bool doRL, bool doNewCaseRetain, ExternalState E, GridUnit u,
int maxSearchDepth )
02: C=null;
03: if (doRetrieval)
04: C = RetrieveCase( P, step, R, E ); // See Algorithm 3.3, pp. 113
05: end if
06: if (C)
07: S = C.getSolution();
08: success = A.applySolution( P, step, S );
09: if (success)
10: if (doRL)
11: C.successCount++;
12: end if
13: else
14: if (doRL)
15: C.failureCount++;
16: end if
17: end if
18: elsif (!doSearch)
19: S = {} // Empty solution
20: success = A.applySolution( P, step, S );
21: else doSearch=true
22: K = P.buildSearchProblem( A, step, P, u, E );
23: N = bestFirstSearch( K, maxSearchDepth );
24: if (N)
25: S = N.extractSolution();
26: success = A.applySolution( P, step, S );
27: if (!success) return FAILURE ;
28: elsif (S is empty) return SUCCESS ; end if
29: if (doNewCaseRetain)
30: t = P.conditionSetMode( R, step );
31: if (t is not absolute coordinate mode)
32: rotate E by -P.matchingRotationAngle
33: end if
34: newE = {} // Empty
35: if (S is dependent on E)
36: if (t is not absolute coordinate mode)
37: Copy relative position of each entry in E to newE;
38: else
39: Copy global position of each entry in E to newE;
40: end if
41: end if
42: C = buildNewCase( P, R, step, newE, S, u );
43: P.addNewCase( R, C );
44: end if
45: else
46: return FAILURE ;
47: end if
48: if (doRL or doNewCaseRetain) A.storePlan( P ); end if
49: end if
50: return SUCCESS ;
51: end
106
• maxSearchDepth: The maximum depth to which the heuristic search the learning
• On line 2, the algorithm initializes case C to null to prepare for potential retrieval.
• If parameter doRetrieval is true (line 3), then the agent will try to apply already
learned knowledge about plan step step in P . Given the plan step, step, current role
of the agent, R, and the current external state description, E, the Learn algorithm
tries to retrieve a case that matches E (line 4). This case is stored in C. If no cases
are retrieved, the algorithm moves to the if-statement starting at line 18, where the
applySolution function is called. Given a solution either retrieved from the case or one
discovered using search, applySolution applies that solution to the current situation
and checks whether the postconditions of the current plan step (step) have been
If the algorithm moves to line 18 after the if-statement at line 6 fails, then, by
definition, there is no solution the algorithm can apply. Hence, S is empty (line 19).
However, the algorithm still needs to monitor the postconditions of the current plan
step. Since the applySolution accomplishes this task, we call it with an empty action
• If, on the other hand, there is a matching case (line 6), the algorithm accesses the
• Then the algorithm starts executing this action sequence in the current situation (line
8).
• If the application of the action sequence S is successful (line 9) and naı̈ve reinforcement
learning mode is active (line 10), then plan step step receives positive reinforcement
(line 11).
107
• At line 21, the algorithm starts the heuristic search mode. At this point, doSearch
must be true.
• In search mode, the algorithm builds a new search problem based on the state of the
current agent, A, the plan step in question, the current external state description, and
the discretization unit, u. The algorithm calls buildSearchProblem on the current plan
P (line 22). The return value of this call, K, represents a data structure that defines a
• Then the algorithm tries to solve the search problem using best-first heuristic search
by calling bestFirstSearch (line 23). The return value of this call, N , is a search node,
from which the action sequence that solves the search problem is instantiated using
the extractSolution call (line 25) given that search produced a result (line 24).
• If search fails to find a solution till depth maxSearchDepth, the algorithm fails and
• If search returns an action sequence, that action sequence S needs to be tested in the
actual environment to find out whether it will work in practice or not (line 26). For
this, the algorithm calls applySolution and passes S to it (line 26). The applySolution
call executes S. The return value of this call, success indicates if S worked in the
How the applySolution call translates each action in S to an actuator command in the
agent architecture is critical to how a MuRAL agent operates (see Figure 3.6, page 87).
• If S works in practice (line 26), then it means the agent can store a new case as long as
doNewCaseRetain is turned on (line 29). If not, the algorithm returns with a failure
(line 27). If S happens to be empty, then there is no other task to perform within
the current plan step, step, were written in terms of global coordinates or relative
coordinates. Therefore, first, the algorithm determines the type of the current
108
postconditions (line 30). If the postconditions for role R in the current plan step
are in terms of relative coordinates (t), the algorithm rotates the current solution by
inverse of the matching rotation angle to “normalize” the solution (line 32).
• Lines 34–41 deal with the storage of the external conditions, E. The external
conditions are stored as part of a case if and only if the solution S is dependent
postconditions are in terms of relative coordinates (line 26), the algorithm copies the
global coordinates, then the algorithm copies the global coordinates of the objects in
E to newE .
• On line 42, the algorithm builds a new case to store in the casebase of agent A, given
information about the current plan, P , the role of the current agent, R, the external
state description at the time the search problem was built, newE , the action sequence,
S, and the unit of discretization, u. The newly built case, C, is then stored as part of
• On line 48, the algorithm stores the modified version of the plan to an output file.
• Finally, on line 50, the algorithm returns with success, since this point can only be
The algorithm each agent uses during the training phase is given in Algorithm 3.2. Parts
of this algorithm are specific to the RoboCup soccer simulator but could be generalized to
109
1. A: The agent that is being trained
3. u: The discretization unit for the physical space in which the agent operates. Every
4. maxSearchDepth: The depth limit to the search for finding a sequence of actions for
• The main body of the algorithm (lines 2–24) is composed of one loop that iterates
over each plan step in the given plan and trains the agent. The first operation in
110
training is to check if the preconditions of the current plan are satisfied (lines 5–13).
The algorithm checks, in an inner while loop, whether the preconditions of plan
step i have been satisfied and whether they have timed out. Both preconditions and
fails, then the condition is said to have not been satisfied, and the algorithm returns
with failure.
• On line 3, the algorithm retrieves the ith plan step and stores it as s. A plan
step is a compound data structure that contains information about roles and other
information such as timeout values for satisfying conditions. (See Section 3.3.4).
• If the Action Agenda of the agent is empty, the algorithm adds a default action so
that the agent can monitor its environment and respond to basic situations such as
precondition match. If there is a match (line 10), then the algorithm exits the inner
while loop. If there is no match and the preconditions time out, the algorithm returns
with failure (line 22). The checking of the preconditions for the very first plan step
is a special case that needs to be handled differently from subsequent steps. The
checking of whether the preconditions of the first step in a plan are satisfied or not
requires that preconditions for all roles associated with that step be tested, since there
• On line 15, the Train algorithm collects a description of the external conditions by
• On line 16, the algorithm accesses the role that agent A has assumed in plan P .
Checking for precondition match during the very first plan step assigns the roles of
each agent involved in executing the plan. Each agent assigns roles independently
and does not communicate its assignments to its collaborators. So, a plan will be
2
In our implementation, we determined the values of these timeouts emprically.
111
executed successfully if the role assignments of all collaborating agents happen to be
An agent takes on the role associated with the first perspective whose preconditions
it satisfies. It is, however, possible that more than one training agent can match the
same role. However, this is resolved practically during training and application by
how collaborating agents are placed on the field, so that their constellation can easily
• On Line 17, the Train algorithm calls the Learn algorithm in Algorithm 3.1. If this
call does not succeed, the algorithm returns with failure (line 19). To enable the
learning algorithm to work with the training algorithm, search and case retention
modes are turned on in the Learn algorithm call. Note that the Learn algorithm
internally checks whether the postconditions of the current step have been satisfied.
• If the postconditions have been satisfied, success is set set to true (line 17), and,
therefore, the agent continues training on the next plan step in the plan. If there are
no plan steps left, then sucess is set to false (line 17), and this causes the algorithm
to exit with failure (line 19). As in the case of preconditions, postconditions for plan
step i are checked only from the perspective of agent A that took on role R in plan P .
1. P : The plan that the agent matched to the current situation and assumed a role in
2. planStep: The numerical index of the plan step about which a case is to be retrieved
4. E: The description of the external state. This description serves as the index into the
112
01: RetrieveCase( Plan P, int planStep, Role R, ExternalState E )
02: s = P.getPlanStep( planStep );
03: B = s.getCasebaseForRole( R );
04: p = s.getPostconditionsForRole( R );
05: if (not B)
06: return null;
07: end if
08: foreach case c in B
09: c.computeCaseSimilarity( E );
10: end foreach
11: RandomCaseSelector S={}
12: foreach case c in B
13: if (c is similar to E)
14: add c to S;
15: end if
16: end foreach
17: return S.selectCase();
18: end
• The algorithm retrieves the plan step indicated by index planStep and stores this data
structure in s (line 2). On line 3, the algorithm accesses the casebase for role R in step
s of plan P and stores a reference to the casebase in B. The algorithm also accesses
p.
• If there is no casebase for R in s, then the algorithm returns with an error (lines 5–7).
• Then, for each case c in B, the algorithm computes the similarity of c to the current
situation. The similarity of each c is computed based on the retrieval index, E (lines
8–10).
• Using the results of the similarity computation (lines 8–10), the algorithm then
determines which cases in B are similar to the current situation (lines 12–16). The
algorithm then enters each similar case with its similarity value to a random event
• Finally, on line 17, the algorithm randomly selects a case from S, where the
113
situation computed at line 9.
The random selection of cases works as follows. First, the goal is to select each case
with a probability that is strongly related to its success rate. At the same time,
we do not want to completely ignore cases with low success rates, especially at
success rate of each case that is proportional to the number of similar cases entered
into the random case selector divided by the total number of trials in all similar cases.
The effect of this contribution factor is that, as the number of total trials gets large,
the overall weight of cases with zero success rate will decrease.
Given a set of n cases that have been deemed similar (line 13 in Algorithm 3.3), S, the
successCount ci
rawSuccessRate ci =
successCount ci + failureCount ci
The total number of times the cases in S have been applied is given by:
n
X
totalTrials = (successCount ci + successCount ci )
i=1
n
X
totalRawSuccessRate = rawSuccessRate ci
i=1
n
contribution =
totalTrials
The total rate is given by the sum of the total raw success rates and the total
114
Finally, the probability of selecting each ci is given by:
rawSuccessRate ci + contribution
Prob(selecting ci ) =
totalRate
Consider the following example, where we have five cases with (success, failure)
values of S={(0, 0), (0, 0), (1, 2), (2, 3), (0, 0)}. Since the total number of trials is only 8
(1+2+2+3), the cases that have not yet been used for application still have a relatively
high chance of being picked, while cases that have already been used are assigned
The second example demonstrates what happens as the number of total trials in a
set of similar cases increases. For the input set, S={(1, 5), (12, 34), (0, 0), (1, 2), (1, 1),
(0, 0), (0, 0)}, we get the following probabilities of selection. As opposed to the first
example above, cases without trials get picked with substantially less probability.
After a plan is matched by an agent, an agent starts applying that plan to the current
situation. We must note that, by this time, the agent has already checked that the
preconditions of the first plan step in the plan have already been satisfied.
3
If the input raw success rate is undefined, we adjust the value to zero.
115
The plan application algorithm, Apply, is given in Algorithm 3.4, and it requires seven
inputs:
• P : The plan that the agent will apply in the current situation
• u: The discretization unit for the physical space in which the agent operates. Every
• doSearch, doRetrieval, doRL, doN ewCaseRetain: These four parameters control the
• First, the role that agent A has taken on in executing plan P is accessed from the plan
data structure and is stored in R. A matching plan is one whose preconditions of its
first step have already been satisfied by the current internal state of the collaborating
116
• The rest of the algorithm is a loop that iterates over each single step, s, of plan P and
tries to execute that step successfully in the current environment (lines 3–19).
• With this loop (lines 5–11), a second inner checks whether the preconditions of plan
match, the inner whileloop is exited. If, on the other hand, the preconditions time
• On line 12, the algorithm dynamically collects a description of the current external
• Next, the Apply algorithm calls the Learn algorithm (Algorithm 3.1) to do the rest
• A plan step is successfully executed, when the Learn algorithm can find a case that
contains an action sequence that successfully executes in the current context (line
13). If this happens, then the next step is to check whether the executed action
sequence has indeed satisfied the postconditions of the current plan step. This is
done internally by the Learn algorithm. If the call to Learn returns true (success,
then it means that the current plan step has been successfully executed as intended
by the plan specification. If the return value success false, it means that even a
successful execution of the action sequence has not satisfied the postconditions of
the current plan step. Therefore, the algorithm returns with a failure (lines 16–18).
• If all plan steps are successfully applied to the current situation, then the algorithm
In complex, dynamic, and uncertain environments, optimal solutions are generally not
known. For that reason, evaluation of systems that operate in such environments using
117
in this research. When optimal solutions are unknown, it is at least desirable to use
evaluation metrics that can be standardized across different test iterations such that they
indicate the improvement in performance over time. In MuRAL, we used the Soccer Server
simulated soccer environment [Kitano et al., 1997b,a; Chen et al., 2002] for all development
and testing, and our goal is to show that the system learns and improves its performance
Since an agent in MuRAL learns in both the training and application phases, we have
two types of learning. The learning in the training phase aims to help with coverage, and
the learning in the application phase aims to improve the selection of plans and plan step
implementations by increasingly (but not totally) favoring the previously successful ones
to increase the chance of success in future situations. An agent can be trained any time in
MuRAL so that it can acquire new cases to help increase the coverage of its application
knowledge and also learn to implement new plans. The number of cases acquired to
implement a plan, however, is not a good indicator of performance by itself, since, without
the reinforcement knowledge, an agent cannot know if a case it selects will work in
the application phase. Therefore, both types of learning are required for defining true
coverage.
To evaluate the performance of learning, we compare the learning version of our system
to two other versions of the same system over a relatively large number of experiment
trials. The retrieval version of our system uses the cases retained during training but does
so before any reinforcement takes place. The search version of our system does not use any
cases from training but instead dynamically searches for solutions at every step of a given
plan as an agent would during training. Since the search version of our system operates
at the lowest level among the three, we use it as our evaluation baseline. We do not use a
action sequences randomly or program the agent behavior manually. In the context of
our research, both of these options are not practical. MuRAL agents find solutions during
training using high-level search operators (Section 3.3.2). Some of these operators take on
continuosly-valued arguments. Since MuRAL agents generate these solutions in situ, the
118
argument values reflect a potential solution for future situations. Attempting to generate
sequences of actions with working parameters and doing so over several plan steps in
the implementation of each plan for many different situations would be an overly arduous
task due to the variability in agent behavior. Automating the adaptation of behavior via
learning, we contend, is a more effective than any random or manual approach. The goal
During training, each agent has to do search to determine its solution at each plan step.
However, an agent cannot, in general, know whether the solutions it discovers through
search will have eventually contributed to the successful application of a plan. In retrieval
mode, an agent does not do search but instead retrieves cases that are known to have
contributed to the overall success of a given plan during training. In learning mode, the
agent builds experience about which of the cases it can use to apply a given plan step have
been successful so that it may be able to make better choices about which case to pick for
each situation. Therefore, we are essentially comparing three versions of the same system
The major problem in evaluating the MuRAL approach is the subjective judgment
that is required from the perspective of each agent that a given plan step has been
successful. In order to conclude objectively that a given plan has been successfully
executed by a number of players, a special agent is required to test that condition reliably.
uncertain domain is very difficult to perform objectively. For example, in the Soccer
Server environment, determining whether a player currently possesses the ball or not
can be done by a subjective test that checks whether the ball is in close proximity to
119
the player. In general, however, there is no global monitoring entity that can provide
check the postconditions in each plan step to test if that plan step has been successfully
completed. If the time limit on a postcondition runs out or a failure occurs, then an agent
concludes that the current plan has not been satisfied. If all agents who collaborate on a
plan individually detect that the plan has been successfully applied, only then we consider
To compare performance of the three versions of our system, we use the success rate as
our evaluation metric. The retrieval and search versions of our system do not modify any
knowledge or information that the system can use in the successive runs. Therefore, the
experiments in these two modes are independent. In learning mode, each agent adds new
information to its knowledge base via reinforcement, and, therefore, each experiment in
During both training and application, we run controlled but situated experiments over a
select the type and the number of players, the initial layout of the players who are expected
to execute the plan, and what plan to train on or apply. We then vary the number of
opponent players for each plan, and place the opponent players randomly in and around
the region where each plan is to be executed before we start each single run.
We conduct four main types of experiments summarized in Table 3.1. These refer to
the four different versions of our system, one for the training mode and three for the
application mode. For a given plan, we run each of these four main types of experiments
for 1, 2, 3, 4, and 5 opponents. Since the number of players that are expected to execute a
plan is determined by that plan, we only vary the number of opponents per experiment
type.
120
To conduct all experiments, we automatically generate two sets of testing scenarios.
The first set is the Training Set, and is composed of N randomly generated scenarios per
plan per number of opponent players, and this test set is used only during training. The
second set of scenarios is the Test Set, and is distinct from the Training Set, and is also
composed of N randomly generated scenarios per plan per number of opponent players.
Since we intend to compare the performance of learning, retrieval, and search, the Test Set
Table 3.1: Experiment setup summary. The columns list the different modes we use to
customize the behavior of each agent, and the rows list the type of experiment
In training mode, opponent players do not move or execute any other behavior. The
reason for using non-moving opponents is to allow MuRAL agents to retain as many
solution as possible. If the opponent players are allowed to move, MuRAL agents may
learn very little. The idea of training is, therefore, to retain action-level knowledge that
In the remaining three application mode experiments, the opponent players use a
reactive ball interception strategy that is also used by team players that are executing
a plan. If the opponents detect the ball is approaching towards them, they attempt
to intercept the ball by moving and blocking the ball. Otherwise, they monitor the
environment (See the Interceptball plan in Section A.5). 4 In both training and application
experiments, we place the training agents in locations that will allow them to match the
internal conditions of the plan initially. Later position and orientation of players is guided
Two example test scenarios are shown in Figure 3.15 for training on a plan that enables
4
Training agents do not use the Interceptball plan per se. However, they do use the application knowledge
that is used to implement the Interceptball plan, and this knowledge is used both by both MuRAL agents and
opponent agents.
121
three agents in team 1 to learn how to execute multiple passes to advance the ball in the
field. Another group of agents, team 2 acts as opponents. The training team, team 1, is
identical in number and position in both scenarios. Figure 3.15(a) has 4 opponent team 2
agents. Figure 3.15(b) has 5 opponent team 2 agents, and these opponent agents are placed
G
G
C C
D H F
F D
E
E
A B A B
Figure 3.15: Two example testing scenario for training on a threeway-pass plan
3.6.1 Training
The first type of experiment we run involves training, where agents try to find sequences
of actions to implement the goals of each step in a given plan. Hence, the naı̈ve RL
and retrieval capabilities are inactive for training agents (Table 3.1). The goal is to
collect application knowledge that contributed to the eventual success of each given plan
and make all of this knowledge available to each player during the application mode.
Therefore, each agent stores the application knowledge it discovers for its role in each plan
step, if the application of that knowledge was successful. This information is kept distinct
from the output of all other training runs for the same plan. In addition, each agent stores
information about whether the entire plan has succeeded from its perspective or not. If all
training agents store information that a particular training instance was successful, then
we can use the knowledge stored by each agent with some confidence that it may also be
successful in future similar situations. Therefore, it is not until the application of the given
122
plan ends that we know whether the cases stored by the training agents can be potentially
useful for later experiment stages. After all training ends for a plan, we use the success
status information stored by each individual agent for each training run to decide whether
to merge the application knowledge stored during that run into a single plan for each
role. Although strictly not a part of the training, plan merging is a necessary and critical
postprocessing step we perform to collect all successful cases for each role in a single plan.
In retrieval mode, only the case retrieval capability is active (Table 3.1). In this stage,
agents do not do search to discover new solutions. We assume that the application
knowledge collected during training has been merged into a single plan for each role in
that plan. The goal of this experiment is to measure the average success of the system
when it is only using knowledge from training. The important distinguishing factor in
this experiment is that the success and failure counts of cases are not modified after each
application. Therefore, each retrieval mode test is independent of all other retrieval test.
As in training mode, each agent stores information about whether the entire plan was
In learning mode, both naı̈ve RL and retrieval capabilities are active (Table 3.1). As
in retrieval mode, agents do not do search but instead retrieve knowledge from their
casebases for each plan step and for the role that an agent assumes. In addition, after
the application of each case to the current test situation, each agent modifies the success
or the failure count of that case. Moreover, in this mode, an agent that takes on a certain
role in the given plan accesses and modifies the same plan created by plan merging for
that role. Therefore, each learning mode test is dependent on all previous learning tests.
As in other experiments, each agent stores information about whether the plan succeeded
or not. Since each agent learns independently, there is no merging of knowledge through
123
post-processing as in training. Therefore, different agents will have different reinforcement
Finally, in search mode, only the search capability is active (Table 3.1). Similar to the
retrieval experiment, it consists of independent tests, and it only saves information about
whether all steps of a given plan have been successfully completed. The search mode tests
form our evaluation baseline, since search is the lowest-level application capability we use.
Since search is a natural part of training, by comparing the performance of search with that
from retrieval and learning experiments, we can draw certain conclusions about whether
learning cases and reinforcing the usefulness of each individual case will have an impact
We designed four distinct plans with varying complexity to test the ideas we put forth in
this dissertation. Their layout on the field is depicted in Figures 3.16, 3.17, 3.18, and 3.19.
The shaded regions in all of these figures exemplify the regions within which opponent
players are randomly placed. These regions and others where players are expected to be
• The first plan is called Centerpass, and its layout is given in Figure 3.16. In this
plan, player with role A is expected to dribble the ball from region R1 to region R2.
Simultaneously, player B is expected to run from region R3 to region R4. After both
complete this first step, player with role A needs to pass the ball to the player that
assumed role B.
• The second plan is called Givengo5 , and its layout is given in Figure 3.17. In this plan,
player with role A in region R1 needs to pass the ball to player with role B in region
5
“Givengo” is pronounced ”give-n-go.”
124
R4
R3
R1 1
0
0
1
R2
R2. In the second step, A needs to run to region R3 while B keeps the ball. In the
final step of the plan, B needs to pass the ball back to A in region R3.
• The third plan is called Singlepass. Its layout is given in Figure 3.18. As its name
suggests, this plan involves one player passing the ball to another player. In this
case, player with role A in region R1 needs to pass the ball to B in region R2. This
• The fourth and last plan is called UEFA Fourwaypass 6 and is the most complicated
plan among the four plans we designed with four steps and three roles.
1. In the first step, B in region R2 needs to pass the ball to A in region R1.
2. The second step involves A passing the ball it received from B to C in region
R4.
6
This plan has been borrowed from http://www.uefa.com. We use the name ”Fourwaypass” to stress
that the ball will be in four different locations by the end of this plan. This plan involves only three passes.
125
R3
ball
1
0 R2
0
1
R1
3. After passing the ball to C, A then needs to run to its second location in region
R3.
4. Then, in the final step, A reaching region R3 triggers C to pass the ball back to
A in region R3.
The benefit of specifying high-level plans is to guide the solution process by constraining
the learning problem for each plan. The idea of involving users to affect solutions has
been acknowledged in the planning literature. For example, providing user guidance to
a planning system in the form of strategic advice [Myers, 1996] or providing hierarchical
plan sketches to be automatically completed by the system [Myers, 1997] are two such
approaches. In this dissertation, we combine this general idea with learning so that
126
R2
ball
1
0
R1 0
1
the MuRAL approach differs from cooperative distributed problem solving [Durfee et al.,
1989], where problems solving agents need to coordinate to solve problems individual
In recent years, Reinforcement Learning (RL) has attracted a lot of attention from
the multiagent learning community. Since the standard RL scheme is not applicable
to multiagent learning in complex domains [Stone and Veloso, 1999; Matarić, 1991, 1996].
1999; Stone, 1998] (see also Section 2.9.2, page 52) does away with having to know the
next state transition, and it uses action-dependent features to generalize the state space. Each
agent learns how to act in its local environment, so this partitioning of the multiagent state
space reduces the search. TPOT-RL evaluates each action based on the current state of the
127
R3 R4
ball
11
00
00
11
R1 R2
world by classifying the potential short-term effects of that action using a learned decision
tree, and it uses a reward function that provides feedback over a fixed period following
the execution of an action. TPOT-RL deals with shifting concepts by not depending on
future state transitions but depending only on the current state in which the action is taken.
Despite these modifications, Stone later reported that the state aggregation approaches in
TPOT-RL and in other techniques applied to a complex domain such as soccer “. . . are not
The work by Matarić reformulates the RL problem by using conditions and behaviors
as opposed to the standard formulation that uses states and actions [Matarić, 1996;
Mataric, 1994]. Conditions express a subset of the state space relevant for a given
problem, and behaviors are more abstract than primitive actions. Therefore, a more
reward functions allow the reinforcement of multiple concurrent goals and progress
128
using progress estimators is that they enable event-driven behavior termination so that
more exploration can occur in cases where progress is not being made.
Mahadevan and Connell divided the overall RL task in a box-pushing domain into
three domain-dependent manageable modules. Each module learned its own assigned
task and a higher-level priority scheme activated one of the these modules during
application [Mahadevan and Connell, 1992]. Similar to this work, research in scaling up RL
to larger problems focuses on a single high-level task such as keepaway play in soccer (e.g.,
[Kuhlmann and Stone, 2003; Stone and Sutton, 2002, 2001; Kostiadis and Hu, 2001]). The
number of total agents involved in these tasks is less than ten. Similar to Stone’s layered
learning approach, [Arseneau et al., 2000] addresses team-level learning where a single
agent has the task of choosing between several high-level strategies and broadcasting it to
Similar to our approach, roles have been used to divide up the responsibilities among
agents in multiagent systems. [Coradeschi and Karlsson, 1998] uses decision trees to
describe the tasks of multiple roles hierarchically. In ISIS, team responsibilities are
expresses the joint activities of a soccer team, and it applies to the current mental state
of the team, which is described by the agents’ mutual beliefs about the state of the
world. Coordination and communication handled using the teamwork model in ISIS
called STEAM [Tambe, 1997b,a, 1996]. [Bowling et al., 2004] presents an approach for
coordinating and adapting team behavior by way of symbolically represented team plans
stored in a playbook. In this approach, a fixed-sized robot team has a set of plans called
plays that may be appropriate for different opponents and situations. A play describes a
coordinated sequence of team behavior, and a playbook stores all plays that a team can use.
As the team applies plays from a playbook, it keeps track of which playbooks have been
overall successful, so that it may be better able to select the most appropriate playbook as
the team plays against other teams. Each play is made up of basic information and role
information. The basic information describes the preconditions for applying a play and
termination conditions. The role information describes the steps for executing a play. A
129
timeout may also terminate a play. The team keeps track of whether a play was completed
without a goal or not or whether it failed. Then it uses this information for adaptation.
Each play has four roles, and the sequence of play/plan steps in each role specification
respects, our work differs from this approach in one very fundamental way. [Bowling
et al., 2004] uses a central controller that determines which team strategy should be
uses a simple language to express preconditions, termination conditions, and tasks for
each role. In MuRAL, plan representation used describes roles from individual agent’s
perspective. The plan language in MuRAL is more complicated and more expressive.
3.9 Summary
This chapter discussed the learning approach in MuRAL and presented the algorithms
used. The prominent feature of this learning approach is the use of high-level symbolic
plans to constrain search as agents learn how to operationalize plans using case-based
learning and select plans and plan step implementation using a naı̈ve reinforcement
learning. In our implementation, agents are homogeneous, but each learns different
knowledge from its own perspective depending on the roles it takes on over its lifetime.
One clear advantage of our approach is that teams of agents can be trained on both existing
and new plans any time. Once plans have a sufficient number of cases, agents can be
deployed to apply them in full-fledged scenarios so that they can acquire reinforcement
knowledge to learn to improve their selection of plans and plan implementations. This
chapter focused on the theoretical approach in MuRAL. The next chapter focuses on the
130
Chapter 4
Implementation
This chapter describes the implementation of the MuRAL system developed for this
dissertation. The agents we designed and implemented work in the Soccer Server
simulator environment [Chen et al., 2002]. The implementation has been done entirely
in C++ using object-oriented design principles and with the help of the Standard Template
Library (STL). Although our implementation does not directly use any client code or
library developed for the RoboCup simulator, [CMUnited source code] has served as a
good example in developing basic soccer skills and inspired some of the related solutions.
Figure 4.1 shows the main classes in the object class hierarchy of the MuRAL system.
The class hierarchy is reminiscent of that in Java with an Object class at the top.
The Object class is the parent class of almost all classes and provides a basic set of
common functionality. In the figure, class names containing {#} refer to multiple
classes whose names match the given pattern. For example, DashServerCommand and
TurnServerCommand are some of the subclasses referred to by the class name pattern
131
SoccerPlayer
SoccerTrainer
Action Action_{#}
PlanStepCondition PlanStepCondition{#}
SearchSolution SearchSolution{#}
SearchOperator Search{#}Operator
ObstacleAvoidanceModule
MovementModule
ShootingDirModule
LearningModule
ServerCommand {#}ServerCommand
Object
SoccerCase SoccerState
ServerMessage {#}Message
ActionAgenda
UDPConnection
Thread ServerListenerThread
ServerMessageParser
TrainerMessageParser
ConfidenceObject PlayerState
BestFirstSearch BallState
132
Our implementation follows the highly parameterized design tradition of the Soccer
Server. In addition to the parameter set defined by the Soccer Server, we define a
large set of parameters that can be adjusted statically using an input file in order to
customize tasks such as search, obstacle avoidance, ball interception, dribbling, and
position triangulation to name a few. A MuRAL agent also processes the standard
Soccer Server player configuration files. The SoccerParameters class and its subclasses
In MuRAL, there are two types of agents. Player agents train on plans and applying
those plans in soccer games. We also use a single trainer agent to set up the scenarios in the
simulator environment during both training and application. The trainer agent does not
affect the reasoning of any of the agents. Player agents have a strong notion of agency while
the trainer agent is simple and has a weak notion of agency [Wooldridge and Jennings,
1995]. Player agents are implemented by the SoccerPlayer class, and the trainer agent is
implemented by the SoccerTrainer class. The Action class and its subclasses implement
reaction action modules (RAMs). RAMs are executed on a stack-based agenda, implemented
modules (GPMs).
implemented, other RAMs, and the primitive actions provided by the Soccer Server. There
implements navigation based on another GPM called the Obstacle Avoidance Module
the obstacle avoidance scheme described in [Ulrich and Borenstein, 1998] 1 . The Movement
Module builds an abstraction layer above the obstacle avoidance layer. It considers certain
conditions to make navigation work more efficiently in noisy environments. For example,
the Movement Module tries to avoid small turns when an agent is relatively far from its
target location.
133
to determine free directions for shooting the ball. Learning and training are implemented
• DribbleBall: dribble the ball from the current location to a specified location on the
field
• FollowBall: follow the position of the ball by turning the body and the neck of the
player
• GotoBall: go to the ball and position the player according to a dynamically specified
approach angle so that the player is in position to kick the ball in the intended
direction
• GuardGoal: guard the goal by positioning the goalie based on the movement of the
ball
• TurnBall: turn the ball around the player so that the ball can be kicked towards the
desired direction
Figure 4.2 describes the dependence of RAMs and GPMs on other RAMs, GPMs, or
primitive actions. RAMs are shown as ellipses, GPMs as octagons, and primitive actions
example, InterceptBall depends on GotoBall in case the player misses the ball and has to
run after it to collect it. Both InterceptBall and GotoBall depend on LocateBall to determine
134
GotoPosition PassBall DribbleBall InterceptBall ScanField FollowBall
TurnBall
GotoBall
(kick ...) Obstacle Avoidance Module (dash ...) (turn ...) (turn_neck ...)
The communication subsystem that links agent programs the RoboCup soccer simulator
• The ServerMessage class and its subclasses represent the different types of messages
agents, and the TrainerMessageParser class implements message parsing for the trainer
agent.
• The ServerListenerThread class enables player agents to collect messages sent by the
simulator. 2 This class also automatically establishes synchronization with the simulator
• Agents send commands to the simulator using the subclasses of the ServerCommand
class.
The search for action sequences for each plan step is implemented by the BestFirstSearch
class. Search operators are subclasses of the SearchOperator. When an agent learns a
2
Class ServerListenerThread has been implemented as a thread process but is used in non-threaded fashion
in the current implementation.
135
new case, the search solution in that case gets translated to an action sequence which is
each of these actions, the SearchSolution instance gets dynamically translated into a RAM,
which is implemented in subclasses of the Action class. At runtime, each agent keeps track
of the world state as it receives feedback from the simulator. An agent keeps the state of the
ball in an instance of the BallState class and keeps the rest of the world state information,
PlanStep
step index
preconditions
postconditions RoleHashtable
application knowledge
timeout
Hashtable<role,Vector<SoccerCase *> *>
Object Hashtable<Key,Data>
Hashtable<role,Vector<PlanStepCondition>*>
Vector< PlanStep* >
Plan
rotationRange
rotationIncrement
Plans in MuRAL are represented by the Plan class. Cases are represented by the
the data structures used to represent plans at runtime. The shaded boxes show the data
kept by each data structure, as specified in the plan specification language (See Section 4.2).
Each plan is a vector of plan steps. Preconditions and postconditions in each plan step are
implemented as hashtables of list of conditions that are keyed by role names. Similarly,
the application knowledge in each plan step is also a hashtable of a list of cases keyed by
136
4.2 Plan Specification Language
In MuRAL, all plans are specified using a special language named MuRAL Plan Language
(MuRAL-PL). The syntactical structure of this language is Lisp-like where parentheses are
used to delimit expressions. Figure 4.4 gives the general structure of MuRAL-PL.
(plan <symbol:plan-name>
(rotation-limit <float[0..180]:max-rotation> <float[0..90]:rotation-increment>)
(step <integer:plan-step-number>
(precondition
(timeout <integer:timeout-cycles>)
(role <symbol:role-name> <integer:role-priority>
([not] <symbol:condition-name> <any:arg1> ... <any:argN>)
...
)
(role ...)
...
)
(postcondition
(timeout <integer:timeout-cycles>)
(role <symbol:role-name> -1
(<condition> <arguments>)
)
(role ...)
...
)
(application-knowledge
(case <symbol:plan-name> <symbol:role-name> <integer:plan-step-number>
(gridunit <float:grid-unit>)
(success <integer:success-count>)
(failure <integer:failure-count>)
(rotation <float:rotation>)
(opponent-constellation (<integer:x-gridpos> <integer:y-gridpos>) ... (...))
(action-sequence (<symbol:action-name> <any:arg1> ... <any:argN>) ... (...))
)
(case ...)
)
)
(step ...)
...
)
In Figure 4.4, MuRAL-PL keywords are shown in boldface. The meaning of each
keyword and what arguments it takes is described below. Each argument is specified
using the notation <type[range]:name>, where type is the data type of the argument
(integer, float, symbol, etc.), name is a descriptive name of what that argument represents.
137
represented as [a..b] where a is the minimum value the argument can have and b is
• plan starts a new plan and plan-name is the name of the plan. Each plan name in a
• The precondition section defines, for each role in a given plan step, the conditions
that must be satisfied in order for that plan step to start. Similarly, the postcondition
section describes the conditions that must be satisfied in order to terminate the current
plan step. Each precondition and postcondition is described from the perspective of a
• application-knowledge refers to the casebase associated with each plan step and
declared failed. This value is in terms of the simulator cycles. Its default value is 0, which
means that the condition being checked for must either match or fail on the first try.
• rotation-limit defines how wide of an area an agent should check while checking
for a match between the current situation and the current plan step. The first argument,
max-rotation specifies the width of the area, in degrees, that an agent should check
value falls on one side of the current viewing direction of the agent and the other half
falls on the opposite side of the agent’s current viewing direction. The second argument,
rotation-increment specifies the increments, in degrees, that the agent should use
Figure 4.5 is an example of how the rotation-limit specification is used. In this case,
which rotation may match the current situation starts at the default 0-degree rotation of
the current viewing angle and then moves to either side of the viewing direction in 15-
degree increments. Since only two 15-degree increments can fit in a 40-degree sector on
138
each side of the current viewing angle, the agent will check a total of five different rotations
at 0, +15, +30, -15, and -30 degrees relative to the current viewing angle. The remaining
10-degree sectors on each edge of the 80-degree sector will not be checked since the next
40
viewing
angle
+30
+15 40
−15
−30
• role defines each role that must contribute to executing or learning about executing
a given plan step. A role is defined by the name of the role (role-name), priority of
the role (role-priority), and a list of conditions. A condition is defined by its name
(condition-name) and a list of arguments that can be of any valid type. A condition
may be negated with the not keyword. The priority value in a role specification is used to
• case defines a new case. Each case is associated with a plan (plan-name), a role
identified. At the least, it important to distinguish cases for each role in the current plan
step. The value of plan-name must be the same name as that specified for the current
plan, the value of role-name must match one of the roles specified in the current plan
step, and the value of plan-step-number must be identical to the current plan step. The
remaining values in a case specification can be specified in any order. The gridunit
139
field specifies the unit distance of each grid square. All coordinate specifications (See,
fields failure and success specify the number of times the current case was either
successfully used or failed. The rotation value specifies by how many degrees the
opponent team scenario stored in this case was offset from the viewing angle of the agent.
The opponent-constellation field stores the opponent constellation that was relevant
to the current step of the plan and is made up of a list of (x, y) grid locations. The action-
sequence field stores the list of actions that must be executed in the order specified. Each
action is specified by a name that refers to that action and a list of arguments of any valid
type. At the time a case is created, rotation value is used to normalize the scenario
by rotating the coordinate values in the opponent constellation and in the action sequence
specification so that all coordinate values are with respect to the viewing angle of the agent.
During matching and execution, an agent starts with this normalized case representation,
and, depending on the angle offset from the current viewing direction at which it finds
a match to the current scenario, it rotates the appropriate case representations to match
them to the current scenario. During application, the grid world coordinates in an action
The next two subsections list the plan condition primitives and action types that are
• has-ball
• in-rectangle-rel x1 y1 x2 y2 x3 y3 x4 y4
in-rectangle-abs x1 y1 x2 y2 x3 y3 x4 y4
Checks whether the specified player is in the given region, defined by its four corners
• ready-to-receive-pass
140
Always returns true. This condition causes a player to go into ball interception mode.
• play-mode mode
• true, false
• uniform-no num
• goto-area-rel x1 y1 x2 y2 x3 y3 x4 y4
goto-area-abs x1 y1 x2 y2 x3 y3 x4 y4
Moves the player to the specified relative or global rectangular area whose four
• goto-position-re x1 y1
goto-position-abs x1 y1
• dribble-ball-rel x1 y1 .. xn yn
dribble-ball-abs x1 y1 .. xn yn
The player dribbles the ball to a set of relative or global waypoints, [(x1, y1) ..
(xn, yn)].
• intercept-ball
• pass-ball R
The player passes the ball to another player that has been assigned the tasks of role
R.
141
• pass-ball-to-area-rel x1 y1 x2 y2 x3 y3 x4 y4
pass-ball-to-area-rel x1 y1 x2 y2 x3 y3 x4 y4
The player passes the ball to a relative or global area defined by its four corners
The player scans the field to collect information about the game either by turning
its body (use body) and observing relevant changes or by only turning its neck
• goto-ball
Moves the player to the ball such that the player can kick the ball if needed.
In the simulated soccer environment, an agent works as a client that connects to a server
(simulator) through a UDP socket connection. In general, the agents do not communicate
among themselves except through the simulator. 3 Figure 4.6 shows the main operation
cycle and the basic process cycle of a MuRAL agent. The main operation cycle in
Figure 4.6(a) summarizes the overall behavior of an agent, and the basic process cycle in
Figure 4.6(b) shows the critical steps an agent takes in each cycle of its operation.
The main operation cycle (Figure 4.6(a)) starts with the initialization and setup of the
agent, which includes connecting to the simulator. Since a MuRAL agent can operate in
one of two modes (training, application), the agent checks whether it is in training mode.
If so, it executes its training algorithm (Section 3.4.2). If not, it means that the agent is in
application mode. The application mode is a loop that allows an agent to successively select
a plan and execute it in the actual environment. If the agent can find a matching plan, it
executes its plan application algorithm (Section 3.4.4, page 115). If it cannot find any more
matching plans to apply, the application loop ends and the agent halts.
3
For the practical reason of shutting down each experiment trial, our agents send their process ids to the
Trainer agent.
142
START
mode ? train
Yes No
done = false
START
TRAIN ? true
EXIT Yes done
collect messages
No
success ? true
Yes execute active RAM
done = true
APPLY
END
Figure 4.6: Main operation cycle and basic process cycle of a player agent
In every simulation cycle during this main operation cycle, an agent follows a basic
process cycle shown in Figure 4.6(b) (Also see Figure 3.3). First, the agent collects all
messages sent by the simulator. Second, it processes these messages by parsing them
and updating its world model accordingly. In this step, one of the critical operations an
agent carries out in the RoboCup simulated soccer environment is position triangulation,
because it is critical for a player to know where it is and how it is oriented on the field. The
agent uses the fixed markers within its visual range to triangulate itself. The triangulation
algorithm used by MuRAL agents is described in Appendix D. To update its world model
based on the visual feedback it receives from the simulator, an agent computes the position
and the velocity of the ball and also resolves its previous observation of other agents
with respect to the new visual update it received. As we mentioned in Section 3.3.3, we
143
use confidence values to express the dependability of information about currently unseen
2. Incorporation of newly seen players into existing memory of previously seen objects
to try to deduce missing information about currently unseen objects and update their
confidence values
Knowing the velocity of the ball is critical in intercepting the ball, and resolving
visual updates allows an agent to build a continuous representation of the world state
instead of one that is episodic, where each new visual update would overwrite all relevant
parts of the world state. When an agent turns its body or neck, the objects that were
of previously seen but currently unseen objects. It is difficult to estimate the velocity of
cycles alone due to the noise in the visual updates about object movements. On the other
hand, the simulator provides approximate information on each moving object so that its
velocity can be more reliably estimated. Appendix E describes how we implemented this
velocity estimation and gives the derivation of the velocity formulas, which are based on
how the simulator computes related values it reports to players [Chen et al., 2002].
The synchronization of client programs with the server is another critical aspect of
the next cycle at regular intervals and without waiting for any of the clients. Therefore,
each client has a limited time to decide what to do next. It is also critical at what time
during a simulator cycle an agent sends a command in order for that command to take
effect before the next simulation cycle starts. Therefore, knowing when a new simulator
cycle starts is important to maximize the amount of time an agent has to respond to
the current situation and update its world model in synchronization with the server. To
144
synchronize agents, we use a procedure that takes advantage of a feature of the simulator.
The third main step in the basic process cycle (Figure 4.6(b)) involves executing the
currently active reactive action module (RAM). Each MuRAL agent has a stack-based action
agenda (implemented in class ActionAgenda) that stores and executes RAMs that are
activated by the current plan step. The action-sequence field in a case lists the
actions an agent needs to execute. These actions have corresponding RAMs. Each
corresponding RAM is then pushed onto the action agenda in the order it appears in the
action-sequence field, and the topmost RAM is executed. When contingencies occur,
145
Chapter 5
Experimental Results and
Discussion
In this chapter, we present and interpret the results of our experiments in light of our
main hypothesis that naı̈ve RL can improve the performance over training knowledge
system started with a set of handwritten plans in skeletal form. Each plan specified what
each role in each step needed to accomplish in order to achieve the goal of that plan.
These plans contained only the necessary information to describe what each agent that
took on a given role in that plan had to do, but they did not have any application-specific
knowledge for how to carry out each plan step. The goal of training was to acquire this
as the Training Set in Section 3.6. Following training, we used a separate Test Set to measure
the performance of the learning version of our system against two non-learning versions of
the same system. Both of the non-learning versions of our system did not modify the
knowledge we obtained from training. The retrieval version only retrieved cases and
applied them to test situations. The search version did not use any of the knowledge
collected during training and instead used search dynamically to find solutions for each
146
5.1 Introduction
Our agents build solutions to different soccer problems in terms of sequences of actions
selected and instantiated from a small set of reactive action modules (RAMs) (Also see
Section 3.3.5). Some of these RAMs we implemented for simulated soccer require numeric
parameters and others do not. RAMs that implement ball interception and passing, for
example, do not take any numeric parameters in plans. What this means is that, if the
search on the postconditions of a plan step results in one of these parameterless actions,
the agent will save only one case representing all possible solutions during training, since
all cases will be identical by default. RAMs for ball dribbling, on the other hand, require
real-valued parameters. Therefore, such actions can be instantiated with a wide range of
Since the game of soccer revolves around passing the ball among players, the most
interesting behavior also occurs when dribbling and passing are combined. Since each case
retained during training is matched using conditions external to the training agent group,
Next, we present the training experiment results followed by the application experiment
results.
Table 5.1 gives the number of training trials we used for each plan in each of the five
opponent scenarios (See Section 3.6). Even though we used different number of trials in
some of the experiments, the retrieval and learning experiments started with the identical
copies of the operationalized plan that we obtained after merging the knowledge from
all five opponent trials in each case. That is, the knowledge used in both retrieval and
learning experiments came from the same training session for each given plan. Since we
only merge the knowledge from trials that were successful for the entire plan, the actual
number of trials that contributed knowledge for the application phase is less than the
147
number of trials shown in Table 5.1. Even though opponents do not move during training,
1 2 3 4 5
Centerpass 1000 1000 1000 1000 1000
Givengo 1000 1000 1000 1000 1000
Singlepass 1000 1000 1000 1000 1000
UEFA Fourwaypass 1000 1000 1000 550 630
Table 5.1: Number of trials used during training for each plan for all 5 opponent scenarios
The application knowledge that our system acquired during training is summarized
in Tables 5.2, 5.3, 5.4, and 5.5. For each of the four plans we designed for this dissertation,
these tables list how many cases were retained for each role in each plan step.
The source code of the four plans (Centerpass, Givengo, Singlepass, and UEFA
Fourwaypass) we used as input to training in this dissertation are given in Appendices A.1,
A.2, A.3, and A.4. For an example of how a plan is modified after training and learning,
As Table 5.2 indicates, the two agents in the Centerpass plan only learned one case each
for both steps of the plan. This has to do with the limitations of the plan that makes agent
A dribble the ball close to the goal line of the opponent team before passing the ball to
agent B. When A finishes step 1, it is always looking straight ahead and that prevents A
from seeing the opponents to its left. As a result of this limitation, the cases retained are
the minimum set of actions needed to accomplish the Centerpass plan. Since there is no
Table 5.2: Number of cases acquired for each role in each step of the Centerpass plan
during training
Table 5.3 lists the number of cases retained during training for the Givengo plan. In
step 1, 90 cases were retained for role A to accomplish the pass from role A to role B. In
148
step 2, 770 cases were retained for role A to implement the goal of moving A to its second
location. In step 3, role B learned 9 cases for passing the ball back to A. Since role B did
Table 5.3: Number of cases acquired for each role in each step of the Givengo plan during
training
Since the Singlepass plan involves the execution of a pass between two players, the
critical work from the perspective of our approach and implementation rests with role A,
which is responsible for passing the ball. Role A has to intercept the ball, and, therefore,
only the ball interception action is sufficient for it to satisfy its role in the plan; hence the
single case for B. To accomplish the pass, on the other hand, training generated 210 unique
Table 5.4: Number of cases acquired for each role in each step of the Singlepass plan during
training
Table 5.5 lists how many cases were retained during training for the UEFA Fourwaypass
plan. The critical roles for case coverage in this plan are role B in step 1, role A in step 2,
role A in step 3, and finally role C in step 4. The remaining roles are associated with ball
interception. Role B in step 1 has 41 cases, role A in step 2 has 103 cases, role A in step 3
has 581, and, finally, role C in step 4 has 2 cases. Role C in step 1, role B in step 2, roles B
and C in step 3, and role B in step 4 did not have critical tasks; therefore, training agents
learned no cases for those roles. When a role does not have any critical plan-based tasks
to perform in a given plan step, our system automatically assigns a default behavior to
149
the corresponding agent. This default behavior causes an agent to continually monitor its
environment and watch for an incoming ball until it needs to perform a plan-based task in
Table 5.5: Number of cases acquired for each role in each step of the UEFA Fourwaypass
plan during training
Following training, we ran three types of application experiments over the same Test Set to
compare the performance of our learning approach to the retrieval and search versions of
the system. This section presents the results for all three types experiments for each of the
four plans we used in this dissertation (See Section 3.7). For each plan, we present five sets
of summaries in tabular form to describe the behavior of our system in learning, retrieval,
1. The graph of the running success rate of the plan during learning for all five
opponent scenarios. The x-axis of the graph is the number of experiments run, and
2. The success rate of the plan in the three application experiments for five different
scenarios with 1 to 5 opponent players. The size of the Test Set was 1000 for both the
150
retrieval and search experiments and 2000 for the learning experiments in all four
plans. The test trials that did not run properly were considered neither as successes
nor failures.1 Hence all graphs have less than 2000 points.
For the retrieval and search experiments, we compute the success rate using
average of the last 100 test trials, since the learning tests are dependent on all
previous trials and hence their success rate is cumulative over the number of
3. The mean and standard deviation of the last 100 values from each specific learning
4. The paired t-test analysis for statistical significance of the overall difference among
the learning, retrieval, and search performance of each plan. This table lists four
columns: (1) The type of the comparison (RL vs. Retrieval, RL vs. Search, Retrieval
vs. Search). (2) The probability value (p-value) for accepting the Null Hypothesis
that the distributions being compared are equal. (3) The t-statistic (t-value). (4)
Finally, the best confidence level for rejecting the Null Hypothesis [Cohen, 1995;
5. Finally, the paired t-test analysis for each plan across the three application elements
but for each opponent scenario separately. For these individual opponent scenario
comparisons, we correspond each unique test trial to obtain the results. This table
lists six columns: (1) The number of opponents used in the experiments being
compared. (2) Number of individual test trials that ran properly under all three
techniques so that we can do paired comparisons using the t-test. The value given in
this column is the maximum number of paired individual test trials. (3) The type of
the comparison (See item 4 above). Columns (4) and (5) contain the same information
1
During testing, we observed that some test trials were not being properly set up to run by our testing
procedure. This caused the given scenario never to be tried. Since we consider success based on positive
evidence that all agents succeeded in executing the given plan in its entirety, such improper test instances
will, in general, look as failures. Since we consider them as neither successes nor failures, they do not affect
the results we report in this section.
151
mentioned in item 4 above. (5) Whether the Null Hypothesis that the distributions
being compared are equal can be rejected with at least 95% confidence.
We use the paired t-test analysis, since we used different number of opponent players
to test each plan’s performance across the three main experiment types; but, for each
opponent scenario, we used the same test set across the three experiments.
Figure 5.1 shows the success rate of the Centerpass plan with learning for each of the
five opponent scenarios. As we would intuitively expect, the performance of the two
collaborating agents in the Centerpass plan is best with 1 opponent player. The learning
performance then decreases as we add more opponents to the test scenarios. This is indeed
0.9
0.8
0.673 (1 opponent)
0.7
0.6
Success rate
0.520 (2 opponents)
0.5
0.395 (3 opponents)
0.4
0.288 (4 opponents)
0.3
0.2
0.219 (5 opponents)
0.1
0
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Number of experiments
Figure 5.1: Learning experiments using the Centerpass plan. The last success rate value
and the number of opponent players used is indicated on each graph
152
Table 5.6 is the summary of all three experiments for the five opponent scenarios. The
rows of this table represent the type of the experiment, and the columns represent the
average success rate of each experiment. Since each single Retrieval and Search test is
independent of any other, the Retrieval and Search values in Table 5.6 represent the percent
success rate. Since each RL experiment trial is dependent on previous trials, we use the
last 100 values to obtain an average success rate value as we described earlier.
1 2 3 4 5
RL 0.671 0.517 0.395 0.286 0.221
Retrieval 0.626 0.509 0.347 0.289 0.216
Search 0.042 0.043 0.018 0.013 0.018
Table 5.6: Success rates of Centerpass plan experiments with [1 . . 5] opponents in RL,
Retrieval and Search modes
Table 5.7 shows the mean and standard deviation of the success rate of the last 100
learning trials using the Centerpass plan. As the standard deviation values indicate, the
1 2 3 4 5
mean 0.671 0.517 0.395 0.286 0.221
std. dev. 0.002 0.004 0.001 0.001 0.001
Table 5.7: The mean and standard deviation of the last 100 values from the Centerpass
plan RL experiment
Table 5.8 lists the results of the overall paired t-test analysis. It compares the
performance of the three techniques (RL, Retrieval, and Search) in the context of the
Centerpass plan. From Table 5.6 we can see that the success rates of the RL and Retrieval
experiments are very similar. On the other hand, there is a marked difference between the
success rates of RL and Retrieval performance compared to the Search performance. These
similarities and differences are revealed in Table 5.8. We find that there is no statistically
significant difference between the RL and Retrieval performance at the 95% confidence
On the other hand, we find highly statistically significant difference between RL and
Search with 99% confidence. The same is true when we compare Retrieval to Search. The
153
relative differences or similarities between these results are expected, since the Centerpass
plan did not have many cases after training. The reason for the Search performance to
be as low as it is has to do with how search works in general. When an agent reasons
using search, it must “freeze” the world it sees and try to find a solution. However, doing
so does not take into account the dynamics of the environment. Search, in theory, can
attempt to predict how other agents may behave within a limited time window into the
future, however, such predictions cannot guarantee that is how the behavior will be of
the world external to the agent. Especially when we take into account the combinatorial
growth of multiagent search spaces (Section 3.3.5), it becomes clear that search alone is not
Table 5.8: Paired t-test results for comparing Centerpass plan experiments run in RL,
Retrieval, and Search modes
Table 5.9 gives the results of the individual paired t-tests for the three application
techniques for each of the five opponent scenarios using the Centerpass plan. In this table,
we compare the performance of learning, retrieval, and search within the context of each
specific opponent scenario instead of comparing the overall performance of these three
techniques with the Centerpass plan as in Table 5.8. Consistent with the overall RL vs.
Retrieval result in Table 5.8, we find that RL performs no better than Retrieval in all five
distinct opponent setups. However, both RL and Retrieval always perform significantly
As in the case of the Centerpass plan, the performance of the Givengo plan decreases as we
increase the number of opponent players during the learning experiment. Figure 5.2 gives
the performance of the five individual opponent instantiations of the learning experiment
154
#opponents #trials comparison p-value t-value confidence
RL vs Retrieval 0.071 1.805 –
1 979 RL vs Search 0.000 37.546 95.0%
Retrieval vs Search 0.000 34.259 95.0%
RL vs Retrieval 0.574 0.562 –
2 988 RL vs Search 0.000 28.107 95.0%
Retrieval vs Search 0.000 27.341 95.0%
RL vs Retrieval 0.106 1.620 –
3 980 RL vs Search 0.000 22.634 95.0%
Retrieval vs Search 0.000 21.260 95.0%
RL vs Retrieval 0.908 0.115 –
4 996 RL vs Search 0.000 18.708 95.0%
Retrieval vs Search 0.000 18.525 95.0%
RL vs Retrieval 0.655 -0.447 –
5 988 RL vs Search 0.000 13.998 95.0%
Retrieval vs Search 0.000 14.273 95.0%
Table 5.9: Paired t-test results for comparing the performance of RL, Retrieval, and Search
modes in each opponent experiment in the Centerpass plan
As summarized in Table 5.10, compared to the Centerpass case, Search in the context of
the Givengo plan actually performed well compared to RL and Retrieval. While both
the RL and Retrieval performance ranged roughly between 75% and 20%, the Search
1 2 3 4 5
RL 0.758 0.554 0.456 0.325 0.243
Retrieval 0.741 0.544 0.382 0.306 0.204
Search 0.673 0.491 0.370 0.258 0.196
Table 5.10: Success rates of Givengo plan experiments with [1 . . 5] opponents in RL,
Retrieval and Search modes
Table 5.11 gives the mean and the standard deviation of the success rate of the last 100
learning trials in all five opponent scenarios for the Givengo plan. This table demonstrates
The paired t-test analysis summarized in Table 5.12 shows that there are statistical
differences among RL, Retrieval, and Search performances but that there is no statistically
155
1
0.9
0.7
0.4
0.328 (4 opponents)
0.3
0.2
0.242 (5 opponents)
0.1
0
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Number of experiments
Figure 5.2: Learning experiments using the Givengo plan. The last success rate value and
the number of opponent players used is indicated on each graph
followed by Retrieval and Search. The best confidence level we can get for the difference
between RL and Retrieval is only 90%. Since the Givengo plan does not require long
dribbles and hence take the chance of losing the ball to an intercepting player, search has
the chance to score a good number of successes. In contrast, the Centerpass plan requires
a long dribble followed by a pass, and that is the main reason why it failed in the Search
mode.
Table 5.13 is the comparison of the three application techniques we used in each
1 2 3 4 5
mean 0.758 0.554 0.456 0.325 0.243
std. dev. 0.001 0.002 0.001 0.001 0.001
Table 5.11: The mean and standard deviation of the last 100 values from the Givengo plan
RL experiment
156
comparison p-value t-value confidence
RL vs Retrieval 0.050 2.772 90.0%
RL vs Search 0.001 9.421 99.9%
Retrieval vs Search 0.034 3.164 95.0%
Table 5.12: Paired t-test results for comparing Givengo plan experiments run in RL,
Retrieval, and Search modes
or worse than Retrieval, and both Retrieval and RL did significantly better than Search. In
the 3 and 5 opponent scenarios, on the other hand, RL performed significantly better than
RL and Search, but Retrieval did not perform significantly better than Search.
Table 5.13: Paired t-test results for comparing the performance of RL, Retrieval, and Search
modes in each opponent experiment in the Givengo plan
Figure 5.3 shows the learning performance in all five opponent scenarios of the Singlepass
plan. Since this plan is simple, the overall performance was relatively higher than in the
Table 5.14 gives the success rates of RL, Retrieval, and Search for all five opponent
157
1
0.9
0.850 (1 opponent)
0.8
0.679 (2 opponents)
0.7
0.5
0.515 (4 opponents)
0.4 0.542 (5 opponents)
0.3
0.2
0.1
0
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Number of experiments
Figure 5.3: Learning experiments using the Singlepass plan. The last success rate value
and the number of opponent players used is indicated on each graph
scenarios in the Singlepass plan. From this table, we see that the Search results are
1 2 3 4 5
RL 0.851 0.676 0.521 0.515 0.542
Retrieval 0.836 0.674 0.509 0.539 0.551
Search 0.901 0.758 0.603 0.600 0.638
Table 5.14: Success rates of Singlepass plan experiments with [1 . . 5] opponents in RL,
Retrieval and Search modes
Table 5.15 shows the mean and the standard deviation of the success rate of the last
100 learning trials for the Singlepass plan. As in the previous two plans, the learning
According to the paired t-test results given in Table 5.16, the RL and Retrieval
performances were statistically indistinguishable, but, unlike in the Givengo case, Search
158
1 2 3 4 5
mean 0.851 0.676 0.521 0.515 0.542
std. dev. 0.002 0.001 0.001 0.001 0.001
Table 5.15: The mean and standard deviation of the last 100 values from the Singlepass
plan RL experiment
performed significantly better than both RL and Retrieval. This is an expected result, since
the Singlepass plan only involves a pass, and, therefore, the requirements of this plan do
not challenge the search to produce sophisticated solutions. Due to this relative simplicity
of the Singlepass plan, RL did not improve the performance of the system over Retrieval.
Table 5.16: Paired t-test results for comparing Singlepass plan experiments run in RL,
Retrieval, and Search modes
Table 5.17 gives the paired t-test results of each of the five opponent scenarios we used
equally well as Retrieval, but both RL and Retrieval performed significantly better than
Search. In the 3 opponent case, however, RL performed significantly better than Retrieval.
Figure 5.4 shows the learning performance of our MuRAL system in the context of the
UEFA Fourwaypass plan. Compared to the performance of the system in the case of the
previously mentioned three plans, the performance using the UEFA Fourwaypass plan is
lower due to its complexity with four steps and three roles.
Table 5.18 lists the success rate of the three techniques we used in evaluating our
Retrieval performed much better than Search. Since the UEFA Fourwaypass plan is the
most complicated plan we used in this dissertation, agents with only search capability and
159
#opponents #trials comparison p-value t-value confidence
RL vs Retrieval 0.688 0.401 –
1 995 RL vs Search 0.000 -5.104 95.0%
Retrieval vs Search 0.000 -5.333 95.0%
RL vs Retrieval 0.084 1.732 –
2 988 RL vs Search 0.001 -3.492 95.0%
Retrieval vs Search 0.000 -5.311 95.0%
RL vs Retrieval 0.004 2.907 95.0%
3 993 RL vs Search 0.010 -2.565 95.0%
Retrieval vs Search 0.000 -5.564 95.0%
RL vs Retrieval 0.269 1.106 –
4 992 RL vs Search 0.011 -2.535 95.0%
Retrieval vs Search 0.000 -3.594 95.0%
RL vs Retrieval 0.147 1.451 –
5 981 RL vs Search 0.000 -3.753 95.0%
Retrieval vs Search 0.000 -5.256 95.0%
Table 5.17: Paired t-test results for comparing the performance of RL, Retrieval, and Search
modes in each opponent experiment in the Singlepass plan
1 2 3 4 5
RL 0.403 0.212 0.174 0.119 0.086
Retrieval 0.364 0.194 0.160 0.114 0.063
Search 0.000 0.001 0.000 0.000 0.000
Table 5.18: Success rates of UEFA Fourwaypass plan experiments with [1 . . 5] opponents
in RL, Retrieval and Search modes
As Table 5.19 gives the mean and standard deviation of the success rate of the last 100
learning trials. As this table demonstrates, the learning performance stabilized in all five
Table 5.20 lists the paired t-test results for comparing the overall performance of RL,
Retrieval, and Search techniques with the UEFA Fourwaypass plan. We find that RL
was significantly better than both Retrieval and Search and Retrieval was significantly
better than Search. In the overall comparisons of performance, this is the first plan where
we obtain statistically significant results that assert that RL is the best technique to use,
160
0.5
0.45
0.406 (1 opponent)
0.4
0.35
0.3
Success rate
0.25
0.173 (3 opponents)
0.211 (2 opponents)
0.2
0.15
0.120 (4 opponents)
0.1
0
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Number of experiments
Figure 5.4: Learning experiments using the UEFA Fourwaypass plan. The last success rate
value and the number of opponent players used is indicated on each graph
1 2 3 4 5
mean 0.403 0.212 0.174 0.119 0.086
std. dev. 0.001 0.001 0.001 0.001 0.001
Table 5.19: The mean and standard deviation of the last 100 values from the UEFA
Fourwaypass plan RL experiment
Table 5.21 lists the results of the statistical comparisons of RL, Retrieval, and Search
in each of the five opponent scenarios. All of the five sets of results are identical. The
and Retrieval performed significantly better than Search. Even though Table 5.20 shows
statistical significance in the overall comparison of RL with Retrieval, when we limit the
analysis to individual opponent cases, we find that the RL performs no better or worse
than Retrieval.
161
comparison p-value t-value confidence
RL vs Retrieval 0.027 3.416 95.0%
RL vs Search 0.023 3.577 95.0%
Retrieval vs Search 0.025 3.494 95.0%
Table 5.20: Paired t-test results for comparing UEFA Fourwaypass plan experiments run
in RL, Retrieval, and Search modes
Table 5.21: Paired t-test results for comparing the performance of RL, Retrieval, and Search
modes in each opponent experiment in the UEFA Fourwaypass plan
In this section, our goal is to demonstrate that our agents were sufficiently trained. With
few exceptions (See Table 5.1), the learning and retrieval experiments we reported in
previous sections used knowledge acquired during training using 1000 individual test
trials. To show the effect of training, we ran additional training experiments using 500
and 1500 trials for the three plans that learned more than one case in each plan step. These
Tables 5.22, 5.23, and 5.24 show how many cases were retained for each role for each
step of these three plans. As we can observe from these three tables, the more the number
of training trials, the more the number of cases for the critical roles in each step. Roles that
162
need to perform ball interception only have a single case since the ball interception RAM
does not take on any numerical parameters. In addition, non-critical roles do not learn any
cases.
Table 5.22: Number of cases acquired for each role has in each step of the Givengo plan
via training with varying number of test scenarios
Table 5.23: Number of cases acquired for each role in each step of the Singlepass plan via
training with varying number of test scenarios
for each plan for the 500 and 1500 trial cases, in addition to the retrieval test we already
reported on using 1000 training trials. Table 5.25 summarizes the success rate of these
retrieval tests for the three plans using 500, 1000, and 1500 training trials. The results for
the 1000 training trials are as reported in earlier sections of this chapter. We include them
here for comparison with the 500 and 1500 trial cases. In the case of all three plans, the
retrieval performance is comparable in the 500 and 1500 trial cases. However, when we
increase the training trials to 1500, the retrieval performance drops. This drop is more
apparent in complex plans such as Givengo and UEFA Fourwaypass plan than in the case
of the Singlepass plan, which is the simplest plan we used in our testing. We believe this is
due to the agents starting to overfit the data when the number of training trails is increased
163
Step# Role #Cases (500) #Cases (1000) #Cases (1500)
A 1 1 1
1 B 23 41 79
C 0 0 0
A 58 103 162
2 B 0 0 0
C 1 1 1
A 236 581 912
3 B 0 0 0
C 0 0 0
A 1 1 1
4 B 0 0 0
C 1 2 2
Table 5.24: Number of cases acquired for each role in each step of the UEFA Fourwaypass
plan via training with varying number of test scenarios
Plan #trials 1 2 3 4 5
Givengo 500 0.797 0.594 0.476 0.362 0.173
Givengo 1000 0.741 0.544 0.382 0.306 0.204
Givengo 1500 0.576 0.370 0.210 0.135 0.052
Singlepass 500 0.810 0.662 0.555 0.545 0.639
Singlepass 1000 0.836 0.674 0.509 0.539 0.551
Singlepass 1500 0.818 0.634 0.518 0.501 0.505
UEFA Fourwaypass 500 0.381 0.202 0.178 0.113 0.051
UEFA Fourwaypass 1000 0.364 0.194 0.160 0.114 0.063
UEFA Fourwaypass 1500 0.126 0.034 0.017 0.009 0.008
Table 5.25: Summary of retrieval tests for three of the plans that learned more than one
case per plan step. Each of the three plans was tested using the knowledge obtained from
500, 1000, and 1500 training trials.
164
5.5 Summary
Table 5.26 summarizes all the overall statistical comparisons for the four plans we designed
to demonstrate our MuRAL approach in this dissertation. Table 5.26 lists the four plans in
the order of complexity, where the Singlepass plan is the simplest plan with 2 roles and 1
step and the UEFA Fourwaypass plan is the most complex with 3 roles and 4 steps.
Table 5.26: Summary of paired t-test results for all four test plans listed in the top-down
order of increasing complexity
The experimental results we presented in this chapter as well as the ones summarized
together in Table 5.26 confirm our theoretical expectations. First, as the complexity
of plans increases, the impact of learning grows. Even though the performance of
Singlepass, Centerpass, and Givengo plans, we see that the confidence of the difference
When we compared the performance of RL to Retrieval and Search within the context
of each distinct opponent scenario, we found that both RL and Retrieval do statistically
better than Search, and RL and Retrieval perform equally well. When Retrieval does not
165
perform statistically significantly better than Search, it turns out that RL does, and, in those
instances, RL also performs statistically better than Retrieval (e.g., Givengo plan tests with
3 and 5 opponents, Table 5.9). Therefore, statistically, RL does at least as well as Retrieval
These results confirm that learning via training is better than behaving reactively, in
our case, using search. In other words, we can say that knowing is better than searching.
This is a result of each agent learning alternative ways of implementing each subgoal in
a plan and therefore allowing the agent to select one of the best solutions that match the
current dynamic situation. Since the Singlepass plan was simple, due to being only one
step long, search performed the best among the three techniques. However, in plans with
more steps and/or more agents, the search performance was always the lowest. Plans
with more steps require more dynamic decision-making from the agents, and dynamic
reactive behavior requires that each agent have good coverage in their casebases. The
only linear result we obtained across all the experiments using our four plans was that
166
Chapter 6
Conclusions
and unpredictable environments. Real-world dynamic settings pose steep challenges for
multiagent problem solving due to the combinatorial explosion of state and action spaces
and the difficulty of predicting the environment due to its complexity and dynamics.
Even though dynamically changing environments require that agents act reactively, the
can keep their commitments to their shared goals. Therefore, the overall challenge for
rests on the question of how to find a balance between reaction and reasoning such
that agents in a multiagent can accomplish their goals despite the constraints in the
environment. This question, in turn, boils down to how we deal with intractable search
spaces.
The multiagent systems literature has addressed this issue of goal-directed reasoning
such as reinforcement learning (RL) create emergent behavior, but they are not good at
learning alternative strategies. Due to this limitation, the work reported in the literature
focuses on solving multiagent problems that require one-shot decision making. In contrast,
our goal in this dissertation was to study alternative methods that would enable teams of
agents to pursue multi-step and multi-agent strategies whose execution would naturally
167
span longer times.
Our methodology is based on the idea of learning by doing [Anzai and Simon, 1979]
and combines the bottom-up and top-down problem-solving approaches without policy
learning. We use high-level plans to constrain and focus search towards specific goals
and use learning to operationalize each plan and select context-specific implementation
to apply to each given situation to accomplish the goals of that plan. Plans initially
a given domain from the individual perspectives of all collaborating agents, but they do
not specify how a plan is to be carried out in terms of specific executable actions. This
words, absolutely necessary conditions and resources become part of the what definition
in a plan, and what a collaborative team has to adapt to to be able to execute that plan
what each agent contributing to the execution of a plan needs to do using preconditions for
starting application and postconditions for termination. Therefore, roles are descriptions
of the responsibilities that must be taken on by individual agents that wish to collaborate in
executing a certain plan. Since our agents do not communicate, agents do not share their
role assignments with other agents. Due to this limitation, successful plan application
To operationalize plans, we train our agents in controlled but situated scenarios where
the conditions external to the training agents are changed but kept static throughout each
trial. Agents train on one plan at a time, and, for each successful training episode, each
agent stores a description of the environment and the sequence of actions it performed
problem, agents use search. This method of training allows agents to discover solutions
with the least intervention from the environment. However, there is no guarantee that
the solutions retained during training will work in the full-fledged environment. We
168
use situated application of the knowledge acquired during training as a means to collect
feedback from the environment as to which implementations are best suited for each
specific situation.
In the next stage of learning, we again situate our agents in a controlled environment,
but this time the external factors are no longer kept static. Agents use only the knowledge
they retained during training. They use case-based reasoning to match situations to
among the alternatives they learned during training for their current role in a given plan
step. This form of reinforcement learning involves strengthening the future selection
over many plan application trials, all agents taking part in a given plan autonomously
learn to apply plans with increasing performance. Case-based retrieval during application
helps deal with the noise associated with matching situations to training knowledge, and
RL performs at least as well as retrieval. As the complexity of the plans increases, learning
has an increasing impact on the system performance such that, beyond a certain plan
showed that, except in the case of very simple plans, naı̈ve RL and retrieval are always
better than search. Therefore, we conclude that the more roles and steps a plan has, the
plans can be written to express complex goals that involve multiple agents. Since our
system does not learn plans, it can perform only as well as the extent of its knowledge. It
is also possible that there may exist a plan to solve a problem, but the role a given agent
assumed in that plan may not have the application knowledge needed to execute that role.
In addition, there may exist no plans to solve particular problems in a domain. Hence, we
may need a large set of plans to enable a multiagent system to operate continuously in a
169
In our work, we have not addressed any issues that may arise when a multiagent
setting. That there exist challenges when this migration is done is well-known [Gat, 1997].
Even though the simulator we used modeled sensors and actuators to have noise, it is
conceivable that, in an actual application, sensors may totally fail or actuators may not
work consistently. In other words, the nature of failures may be more severe than in
simulation, and recovery from failure may be more difficult. Since it is virtually impossible
to prove the completeness of a multiagent system designed for complex, dynamic, and
uncertain domains, plans themselves may fail due to lack of critical knowledge, as we
suggested.
The many challenges of working with multiagent systems are still apparent in the
simulated environment. For example, in our experience, we found that the perception
problem is one of the most critical challenges. One of the critical decision points a player
repeatedly visits in soccer has to with deciding whether another player has possession
of the ball. At first try, one may think it sufficient to know that a player has the ball as
long as the ball is near that player and is practically stopped. However, the complexity of
soccer does not lend itself to such simplification. For instance, if a player is turning the ball
around itself in order to give a pass, the ball during that action will have non-zero speed.
Therefore, relying partially on the ball having near-zero speed to decide on ball possession
will lead to detection failures. Since many decisions at plan level depend on such lower-
are almost never instantaneous. Instead, they span over time, and this means that their
In the light of our work, we discuss three issues of interest for future work:
1. The ultimate goal of our line of work is to automate the creation of fully-autonomous
teams of agents that can execute plans in succession to accomplish higher-level goals
170
that may also be specified in plans themselves. Besides the fundamental difficulties
of sensing and acting, this operation requires coherence among multiple agents, and,
(a) Each agent in a collaborative group must select the same plan to execute at the
(b) The role assignments/mappings performed from each agent’s perspective must
(c) Each step of the selected plan must be performed in coordination with all other
How we ensure that role assignments are consistent is a difficult question to answer
their sensory capabilities to help match plans to situations. Even though we had
a single plan to use in training and application phases, that plan still had to be
matched to the situation. In addition, the controlled nature of our experiments also
implicitly defined when the execution of a plan could start. However, it may be
more difficult to match plans to situations in a regular setting where there are no
an agent can only assign one agent per role, with more agents in the environment
than needed for executing any given plan, there may be multiple agents that can be
the internal role assignment of one agent will match that of other agents that are in
position to contribute to the execution of the plan. Therefore, conflicts might arise.
each agent uses since there are infinitely many possible situations it is expected to
171
handle. Therefore, situations in which an agent fails to find applicable implementation
in its knowledge base are opportunities for further training and learning. An agent
except that the case would contain no application knowledge. Such cases can be
marked as potential sources for more learning and agents involved in such scenarios
3. In MuRAL, the training phase uses search to acquire application knowledge that
(see Section 4.2.2) requires (x,y) coordinate values as argument. In our current
plans (see Section 3.6.1). We only check for identity of corresponding argument
values up to the second decimal point. However, there may be many solutions stored
in plan casebases that have the identical sequence of actions in terms of the type of
the actions involved but with slightly different action arguments. By generalizing
such type-identical action sequences, we can reduce all action sequences with
possible approach for generalizing action sequences is to divide the region around a
given player into grids and consider all values that fall within a grid as similar.
6.2 Summary
The experimental results we obtained validate our thesis that a multiagent system
environments can learn to improve its plan execution performance. To achieve this
symbolic plans. We showed that separating conditions that a team of agents can
have control over from those that they cannot exercise any reasonable control over
172
We used plans to constrain search from top-down and used learning to build specific
with a naı̈ve form of reinforcement learning that proved to be effective in dynamic settings.
system that exhibits true multiagent behavior that is collaborative. In this regard, our plan
traditional planning systems, our plans facilitate dynamic adaptive autonomous behavior
173
Bibliography
pp: 81, 82
with real-time performance. In Working Notes of the IJCAI Workshop on Anytime Algorithms
In Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI 1987), pages
Philip E. Agre and David Chapman. What are plans for? Technical Report AI-MEMO
1050a, MIT AI Lab, October 1989. Revised version (original September 1988). pp: 22
Reasoning Workshop, pages 147–158, Washington, D.C., USA, 1991. Morgan Kaufmann.
pp: 81, 83
James Allen, James Hendler, and Austin Tate, editors. Readings in Planning. The Morgan
José A. Ambros-lngerson and Sam Steel. Integrating planning, execution and monitoring.
83–88, Saint Paul, Minnesota, USA, August 1988. AAAI Press/MIT Press. (Reprinted in
174
Yuichiro Anzai and Herbert A. Simon. The theory of learning by doing. Psychological
Ronald C Arkin and Tucker Balch. AuRA: Principles and practice in review. Journal of
Experimental & Theoretical Artificial Intelligence, 9(2/3):175–189, April 1997. pp: 26, 51
Shawn Arseneau, Wei Sun, Changpeng Zhao, and Jeremy R. Cooperstock. Inter-layer
Tucker Balch. Clay: Integrating motor schemas and reinforcement learning. Technical
pp: 55
Tucker Balch. Learning roles: Behavioral diversity in robot teams. Technical Report GIT-
99
Scott Benson. Inductive learning of reactive action models. In Armand Prieditis and
agent teamwork, adaptive learning and adversarial planning in Robocup using a PRS
Alan H. Bond and Les Gasser, editors. Readings in Distributed Artificial Intelligence. Morgan
Blai Bonet and Héctor Geffner. Heuristic Search Planer 2.0. AI Magazine, 22(3):77–80, Fall
2001a. pp: 18
Blai Bonet and Héctor Geffner. Planning as heuristic search. Artificial Intelligence, 129
175
Blai Bonet, Gábor Loerincs, and Hector Geffner. A robust and fast action selection
1997), pages 714–719. AAAI Press/The MIT Press, July 1997. pp: 18, 42
Michael Bowling, Brett Browning, and Manuela Veloso. Plays as effective multiagent
Conference on Automated Planning and Scheduling (ICAPS 2004), page (To appear), 2004.
Michael E. Bratman, David J. Israel, and Martha E. Pollack. Plans and resource-bounded
practical reasoning. Computational Intelligence, 4(4):349–355, 1988. pp: 27, 31, 44, 68, 78
Frances Brazier, Barbara Dunin-Keplicz, Nick R. Jennings, and Jan Treur. Formal
Will Briggs and Diane Cook. Anytime planning for optimal tradeoff between deliberative
and reactive planning. In Proceedings of the 1999 Florida AI Research Symposium (FLAIRS
Rodney Brooks. A robust layered control system for a mobile robot. IEEE Journal of
Robotics and Automation, 2(Issue 1):14–23, March 1986. pp: 13, 23, 30, 34
Rodney A. Brooks. A robust layered control system for a mobile robot. Technical Report
Rodney A. Brooks. A robot that walks: Emergent behaviors from a carefully evolved
176
Hans-Dieter Burkhard, Markus Hannebauer, and Jan Wendler. AT Humboldt –
development, practice and theory. In Hiroaki Kitano, editor, RoboCup-97: Robot Soccer
World Cup I, volume 1395 of Lecture Notes in Artificial Intelligence, pages 357–372. Springer,
1998. pp: 54
Hans-Dieter Burkhard, Jan Wendler, Thomas Meinert, Helmut Myritz, and Gerd Sander.
editors, RoboCup-99: Robot Soccer World Cup III, volume 1856 of Lecture Notes in Artificial
1987. pp: 16
Mao Chen, Ehsan Foroughi, Fredrik Heintz, ZhanXiang Huang, Spiros Kapetanakis,
Kostas Kostiadis, Johan Kummeneje, Itsuki Noda, Oliver Obst, Pat Riley, Timo Steffens,
Yi Wang, and Xiang Yin. RoboCup Soccer Server. Manual (for SoccerServer version 7.07
and later), , August 2002. pp: 4, 58, 59, 63, 67, 118, 131, 144, 226
Paul R. Cohen. Empirical Methods for Artificial Intelligence. The MIT Press, 1995. pp: 151
reactive and coordinating agents. In Hiroaki Kitano, editor, RoboCup-97: Robot Soccer
World Cup I, volume 1395 of Lecture Notes in Artificial Intelligence, pages 112–122. Springer,
Mark d’Inverno, David Kinny, Michael Luck, and Michael Wooldridge. A formal
177
Workshop on Agent Theories, Architectures, and Languages (ATAL ’97), pages 155–176, 1997.
pp: 27
distributed problem solving. IEEE Transactions on Knowledge and Data Engineering, 1(1):
Edmund H. Durfee and Jeffrey S. Rosenschein. Distributed problem solving and multi-
agent systems: Comparisons and examples. In Papers from the Thirteenth International
Kutluhan Erol, James Hendler, and Dana S. Nau. HTN planning: Complexity and
1994), volume 2, pages 1123–1128, Seattle, Washington, USA, 1994. AAAI Press. pp: 16,
17
1992b. (Also Technical Report 273, Computer Laboratory, University of Cambridge, UK).
pp: 34
Gabriel J. Ferrer. Anytime Replanning Using Local Subplan Replacement. PhD thesis,
Richard Fikes and Nils J. Nilsson. STRIPS: A new approach to the application of theorem
178
James R. Firby. Adaptive Execution in Complex Dynamic Worlds. PhD thesis, Department of
Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI 1987), pages 202–
R. James Firby. Task networks for controlling continuous processes. In Proceedings of the
Second International Conference on Artificial Intelligence Planning Systems (AIPS 1994), pages
Andrew Garland and Richard Alterman. Multiagent learning through collective memory.
In Sandip Sen, editor, Papers from the AAAI Symposium on Adaptation, Coevolution
and Learning in Multiagent Systems (Technical Report SS-96-01), pages 33–38, Stanford
Bergmann and Alexander Kott, editors, AIPS Workshop on Integrating Planning, Scheduling,
and Execution in Dynamic and Uncertain Environments (Technical Report WS-98-02), pages
Proceedings of the 10th National Conference on Artificial Intelligence, pages 809–815, San Jose,
Erann Gat. On the role of stored internal state in the control of autonomous mobile robots.
Oussama Khatib and John Kenneth Salisbury Jr., editors, Proceedings of the 4th International
179
Symposium on Experimental Robotics (ISER 1995), volume 223 of Lecture Notes in Control and
Information Sciences, pages 390–401, Stanford, California, USA, 1997. Springer. pp: 170
Robin Murphy, editors, Artificial Intelligence and Mobile Robots, pages 195–210. AAAI
Michael P. Georgeff. Planning. In James Allen, James Hendler, and Austin Tate, editors,
Michael P. Georgeff and François Félix Ingrand. Monitoring and control of spacecraft
systems using procedural reasoning. Technical Note 03, Australian Artificial Intelligence
Michael P. Georgeff and Amy L. Lansky. Rective reasoning and planning. In Proceedings
of Sixth National Conference on Artificial Intelligence (AAAI 1987), pages 677–682, 1987.
pp: 13, 27
Mike Georgeff, Barney Pell, Martha Pollack, Milind Tambe, and Mike Wooldridge. The
Rao, editors, Proceedings of the 5th International Workshop on Intelligent Agents V : Agent
Theories, Architectures, and Languages (ATAL-98), volume 1555 of Lecture Notes in Computer
Eighth National Conference on Artificial Intelligence (AAAI 1990), pages 1016–1021. AAAI
Proceedings of the Ninth International Machine Learning Workshop (ML 1992), pages 189–195,
180
Peter Haddawy. Focusing attention in anytime decision-theoretic planning. In Working
Notes of the 1995 IJCAI Workshop on Anytime Algorithms and Deliberation Scheduling, pages
Karen Zita Haigh and Manuela M. Veloso. Planning, execution and learning in a robotic
agent. In Reid G. Simmons, Manuela M. Veloso, and Stephen Smith, editors, Proceedings
of the Fourth International Conference on Artificial Intelligence Planning Systems (AIPS 1998),
Kristian J. Hammond. CHEF: A model of case-based planning. In Tom Kehler and Stan
(AAAI 1986), volume 1, pages 267–271, Los Altos, CA, August 1986. Morgan Kaufmann.
pp: 13
Thomas Haynes, Kit Lau, and Sandip Sen. Learning cases to compliment rules for conflict
resolution in multiagent systems. In Sandip Sen, editor, Papers from the AAAI Symposium
Thomas Haynes and Sandip Sen. Adaptation using cases in cooperative groups. In
Ibrahim F. Imam, editor, Papers from the AAAI Workshop on Intelligent Adaptive Agents
(Technical Report WS-96-04), pages 85–93, 1996a. (Also see [Haynes et al., 1996; Haynes
Thomas Haynes and Sandip Sen. Learning cases to resolve conflicts and improve group
behavior. In Milind Tambe and Piotr Gmytrasiewicz, editors, Papers from the AAAI
Workshop on Agent Modeling (Technical Report WS-96-02), pages 46–52, Portland, OR, 1996b.
pp:
181
Henry Hexmoor and Donald Nute. Methods for deciding what to do next and learning.
Okhtay Ilghami, Dana S. Nau, Héctor Muñoz-Avila, and David W. Aha. CaMeL:
Learning method preconditions for HTN planning. In Proceedings of the Sixth International
Conference on AI Planning and Scheduling (AIPS 2002), pages 131–142, 2002. pp: 47
François Félix Ingrand and Vianney Coutance. Real-time reasoning using procedural
Toru Ishida. Real-time search for autonomous agents and multiagent systems.
Autonomous Agents and Multi-Agent Systems, 1(2):139–167, October 1998. pp: 41, 42
Research Report RR-98-01, German Research Center for Artificial Intelligence (DFKI
Intelligence (AAAI 1990), pages 170–175. AAAI Press/The MIT Press, 1990. pp: 13
182
Hiroaki Kitano, Minoru Asada, Yasuo Kuniyoshi, Itsuki Noda, and Eiichi Osawa.
RoboCup: The Robot World Cup Initiative. In IJCAI 1995 Workshop on Entertainment and
Hiroaki Kitano, Minoru Asada, Yasuo Kuniyoshi, Itsuki Noda, and Eiichi Osawa.
RoboCup: The robot world cup initiative. In Proceedings of the First International Conference
on Autonomous Agents, pages 340–347, Marina Del Rey, California, USA, February5–8
Hiroaki Kitano, Minoru Asada, Yasuo Kuniyoshi, Itsuki Noda, Eiichi Osawa, and Hitoshi
Hiroaki Kitano, Milind Tambe, Peter Stone, Manuela Veloso, Silvia Coradeschi, Eiichi
Osawa, Hitoshi Matsubara, Itsuki Noda, and Minoru Asada. The RoboCup synthetic
agent challenge 97. In Proceedings of the Fifteenth International Joint Conference on Artificial
Intelligence (IJCAI-97), pages 24–29, Nagoya, Japan, 1997c. Morgan Kaufmann. (Vol. 1).
pp: 56
2001. pp: 42
Intelligent Robots and Systems (IROS 1999), volume 2, pages 990–995, October 1999.
pp: 87
183
Kostas Kostiadis and Huosheng Hu. KaBaGe-RL: Kanerva-based generalisation and
Conference on Intelligent Robots and Systems (IROS 2001), volume 1, pages 292–297, 2001.
Gregory Kuhlmann and Peter Stone. Progress in learning 3 vs. 2 keepaway. In RoboCup-
2003: Robot Soccer World Cup VII, 2003. To appear. pp: 55, 129
Nicholas Kushmerick, Steve Hanks, and Daniel S. Weld. An algorithm for probabilistic
Intelligence (AAAI-94), volume 2, pages 1073–1078, Seattle, Washington, USA, 1994. AAAI
Press. pp: 20
J. Brian Lee, Maxim Likhachev, and Ronald C. Arkin. Selection of behavioral parameters:
on Robotics and Automation (ICRA 2002), volume 2, pages 1275–1281, May 2002. pp: 51
Conference on Robotics and Automation (ICRA 2002), volume 2, pages 1282–1289, May 2002.
pp: 51
of the Japanese Society for Artificial Intelligence (JSAI 1998), 1998. pp: 6, 55
Sean Luke. Issues in Scaling Genetic Programming: Breeding Strategies, Tree Generation, and
Code Bloat. PhD thesis, Department of Computer Science, University of Maryland, 2000.
pp:
184
Sean Luke, Charles Hohn, Jonathan Farris, Gary Jackson, and James A. Hendler. Co-
evolving soccer softbot team coordination with genetic programming. In Hiroaki Kitano,
editor, RoboCup-97: Robot Soccer World Cup I, volume 1395 of Lecture Notes in Computer
Science, pages 398–411. Springer, 1998. (Also see [Luke, 2000, Chapter 5]). pp: 6, 55
Alan K. Mackworth. On seeing robots. In Anup Basu and Xiaobo Li, editors, Computer
Vision: Systems, Theory and Applications, pages 1–13. World Scientific, 1993. pp: 56
Pattie Maes. The dynamics of action selection. In Proceedings of the 11th International Joint
Conference on Artificial Intelligence (IJCAI 1989), volume 2, pages 991–997, 1989. pp: 24
for Intelligent Control Systems, pages 46–54, 1992. (See [Matarić, 1997a]). pp: 23, 24
Maja J. Mataric. Interaction and Intelligent Behavior. PhD thesis, Massachusetts Institute
(Also MIT Artificial Intelligence Lab, Technical Report AITR-1495). pp: 128
185
Maja J. Matarić. Learning in multi-robot systems. In Gerhard Weiß and Sandip Sen,
editors, Adaption and Learning in Multi-Agent Systems, volume 1042 of Lecture Notes in
Computer Science, pages 152–163, 1996. pp: 4, 6, 31, 71, 117, 127, 128
Maja J Matarić. Behavior-based control: Examples from navigation, learning, and group
Maja J Matarić. Coordination and learning in multirobot systems. IEEE Intelligent Systems,
Hitoshi Matsubara, Itsuki Noda, and Kazuo Hiraki. Learning of cooperative actions in
multi-agent systems: A case study of pass play in soccer. In Sandip Sen, editor, Papers
from the AAAI Symposium on Adaptation, Coevolution and Learning in Multiagent Systems
(Technical Report SS-96-01), pages 63–67, Stanford University, California, USA, March
1996. pp: 52
William Mendenhall and Terry Sincich. Statistics for Engineering and the Sciences. Dellen
learning approach to robotic soccer. In Andreas Birk, Silvia Coradeschi, and Satoshi
Tadokoro, editors, RoboCup 2001: Robot Soccer World Cup V, volume 2377 of Lecture Notes
com. pp: 36
intelligent real time control architecture. IEEE Transactions on Systems, Man, and
186
Cybernetics, 23(6):1561–1574, November-December 1993. (Also Technical Report CS-TR-
David John Musliner. CIRCA: The cooperatice intelligent real-time control architecture.
pp: 39
of Knowledge Representation and Reasoning (KR 1996), pages 112–123. Morgan Kaufmann
Intelligence Conference (AAAI/IAAI 1997), pages 687–693. AAAI Press, 1997. pp: 4, 72,
126
Allen Newell. Unified Theories of Cognition. Harvard University Press, Cambridge, MA,
Allen Newell and Herbert A. Simon. GPS, a program that simulates human thought.
In Edward A. Feigenbaum and Julian Feldman, editors, Computers and Thought, pages
Allen Newell and Herbert A. Simon. Computer science as empirical inquiry: Symbols
and search. Communications of the ACM, 19(3):113–126, March 1976. pp: 12, 19
Japanese Society for Artificial Intelligence, pages 29–34, December 1995. pp: 57
Itsuki Noda, Hitoshi Matsubara, Kazuo Hiraki, and Ian Frank. Soccer Server: a tool for
187
Itsuki Noda and Peter Stone. The RoboCup Soccer Server and CMUnited: Implemented
infrastructure for MAS research. In Thomas Wagner and Omer F. Rana, editors,
International Workshop on Infrastructure for Multi-Agent Systems (Agents 2000), volume 1887
of Lecture Notes in Computer Science, pages 94–101, Barcelona, Spain, 2001. Springer.
pp: 57, 87
Gary B. Parker and H. Joseph Blumenthal. Punctuated anytime learning for evolving a
team. In Proceedings of the World Automation Congress (WAC 2002), volume 14 (Robotics,
Manufacturing, Automation and Control), pages 559–566, June 2002. pp: 6, 44, 54
Bernard Pavard and Julie Dugdale. The contribution of complexity theory to the study
J. Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, CA,
Anand S. Rao and Michael P. Georgeff. BDI agents: From theory to practice. In Proceedings
of the First International Conference on Multi-Agent Systems (ICMAS-95), pages 312–319, San
Luı́s Paulo Reis and Nuno Lau. Fc portugal team description: Robocup 2000 simulation
league champion. In Peter Stone, Tucker Balch, and Gerhard Kraetzschmar, editors,
RoboCup 2000: Robot Soccer World Cup IV, volume 2019 of Lecture Notes in Artificial
188
Elaine Rich and Kevin Knight. Artificial Intelligence. McGraw-Hill, New York, second
Martin Riedmiller and Artur Merke. Using machine learning techniques in complex
multi-agent domains. In Reiner Kühn, Randolf Menzel, Wolfram Menzel, Ulrich Ratsch,
Interdisciplinary Debate, pages 311–328. Springer, 2003. pp: 44, 45, 55, 56
Martin Riedmiller, Artur Merke, Andreas Hoffmann, Manuel Nickschas, Daniel Withopf,
and Franziska Zacharias. Brainstormers 2002 - team description. In RoboCup 2002: Robot
Soccer World Cup VI, Pre-Proceedings, Fukuoka, Japan, 2002. pp: 102, 103
Paul S. Rosenbloom, John E. Laird, and Allen Newell. The Soar Papers: Research on Artificial
pp: 19, 20
Stanley J. Rosenschein and Leslie Pack Kaelbling. A situated view of representation and
Earl D. Sacerdoti. The non-linear nature of plans. In Proceedings of the Fourth International
Joint Conference on Artificial Intelligence (IJCAI 1975), pages 206–214, 1975. (Reprinted in
Hüseyin Sevay and Costas Tsatsoulis. Multiagent reactive plan application learning
Autonomous Agents and Multiagent Systems (AAMAS 2002), pages 839–840, July 2002.
pp: 72
189
Herbert A. Simon. Models of Bounded Rationality. MIT Press, 1982. pp: 39
Lin Padgham Simon Ch’ng. From roles to teamwork: A framework and architecture.
Lin Padgham Simon Ch’ng. Team description: Building teams using roles,
responsibilities, and strategies. In Hiroaki Kitano, editor, RoboCup-97: Robot Soccer World
Cup I, volume 1395 of Lecture Notes in Computer Science, pages 458–466. Springer, 1998b.
pp: 6, 130
Learning, pages 903–910, Stanford, CA, USA, 2000. Morgan Kaufmann. pp: 5, 46
Mark Stefik. Planning with constraints (MOLGEN: Part 1). Artificial Intelligence, 16(2):
111–140, 1981. (Reprinted in [Allen et al., 1990], pages 171–184). pp: 13, 16
Peter Stone. Layered Learning in Multi-Agent Systems. PhD thesis, Carnegie Mellon
Department, Carnegie Mellon University). pp: 7, 52, 53, 55, 72, 102, 127
Peter Stone and Richard S. Sutton. Scaling reinforcement learning toward RoboCup
537–544, Stanford, CA, USA, 2001. Morgan Kaufmann. pp: 4, 5, 44, 45, 55, 128, 129
Peter Stone and Richard S. Sutton. Keepaway soccer: A machine learning testbed. In
Andreas Birk, Silvia Coradeschi, and Satoshi Tadokoro, editors, RoboCup 2001: Robot
Soccer World Cup V, volume 2377 of Lecture Notes in Computer Science, pages 214–223.
learning. In RoboCup-98: Robot Soccer World Cup II, volume 1604 of Lecture Notes in
190
Artificial Intelligence, pages 261–272, 1999. Also in Proceedings of the Third International
sparse coarse coding. In David S. Touretzky, Michael C. Mozer, and Michael E. Hasselmo,
Milind Tambe. Agent architectures for flexible, practical teamwork. In Proceedings of the
Milind Tambe, Jafar Adibi, Yaser Al-Onaizan, Ali Erdem, Gal A. Kaminka, Stacy C.
Marsella, and Ion Muslea. Building agent teams using an explicit teamwork model and
Austin Tate. Generating project networks. In Raj Reddy, editor, Proceedings of the 5th
International Joint Conference on Artificial Intelligence (IJCAI 1977), pages 888–893. William
Kaufmann, August 1977. ISBN 0-86576-057-8. (Reprinted in [Allen et al., 1990], pages
291–296). pp: 16
191
Austin Tate, James Hendler, and Mark Drummond. A review of AI planning techniques.
In James Allen, James Hendler, and Austin Tate, editors, Readings in Planning, pages 26–
Iwan Ulrich and Johann Borenstein. VFH+: Reliable obstacle avoidance for fast mobile
robots. In IEEE International Conference on Robotics and Automation (ICRA 1998), volume 2,
Iwan Ulrich and Johann Borenstein. VFH*: Local obstacle avoidance with look-ahead
Steven A. Vere. Planning in time: Windows and durations for activities and goals. IEEE
pp: 13
1992. pp: 45
reasoning with dynamic, partial information. In Selected Papers from the 11th Australian
Joint Conference on Artificial Intelligence (AI 1998), volume 1502 of Lecture Notes in Computer
Shimon Whiteson and Peter Stone. Concurrent layered learning. In Proceedings of Second
192
Marco Wiering, Rafal Salustowicz, and Jürgen Schmidhuber. Reinforcement learning
soccer teams with incomplete world models. Autonomous Robots, 7(1):77–88, 1999.
pp: 56
David E. Wilkins, Karen L. Myers, John D. Lowrance, and Leonard P. Wesley. Planning
Michael Winer and Karen Ray. Collaboration Handbook. Amherst H. Wilder Foundation,
Michael Wooldridge and Nicholas R. Jennings. Intelligent Agents: Theory and Practice.
Randolf Menzel, Wolfram Menzel, Ulrich Ratsch, Michael M. Richter, and Ion-Olimpiu
Shlomo Zilberstein and Stuart J. Russell. Anytime sensing, planning and action: A
practical model for robot control. In Proceedings of the Thirteenth International Joint
Conference on Artificial Intelligence (IJCAI 1993), pages 1402–1407, Chambéry, France, 1993.
pp: 40
193
Appendices
194
APPENDIX A
Test Plans
This appendix lists the four plans we used in our experiments. These plans are in skeletal
form. That is, they only contain the high-level descriptions that a plan designer would
195
(postcondition
(timeout 50)
(role A -1 ;; view angle=90
(in-rectangle-abs A 95 0 10 20)
(has-ball A)
) ;;
(role B -1 ;; view angle=296.565
(in-rectangle-abs B 86.25 20 17.5 30)
) ;;
)
(application-knowledge)
) ;; end step
(step 2
;;------------------------------------------------------------------------
;; Player A passes the ball to player C
;;------------------------------------------------------------------------
(precondition
(timeout 30)
(role A -1 ;; view angle=90
(in-rectangle-abs B 86.25 20 17.5 30)
) ;;
(role B -1 ;; view angle=296.565
(true B)
) ;;
)
(postcondition
(timeout 60)
(role A -1
(has-ball B)
) ;;
(role B -1
(ready-to-receive-pass B)
(has-ball B)
)
)
(application-knowledge)
) ;; end step
) ;; end of Centerpass plan
196
A.2 Givengo Plan
(plan Givengo
(rotation-limit 120 15)
(step 10
;;------------------------------------------------------------------------
;; A passes the ball to B
;;------------------------------------------------------------------------
(precondition
(timeout 50)
(role A -1 ;; view angle=56.3099
(has-ball A)
(in-rectangle-rel B 5.96 -2.63 8.74 -6.8 12.9 -4.02 10.12 0.14)
) ;;
(role B -1 ;; view angle=225
(not has-ball B)
(in-rectangle-rel A 13.44 -1.41 9.9 2.12 6.36 -1.41 9.9 -4.95)
) ;;
) ;; end precondition
(postcondition
(timeout 50)
(role A -1 ;; view angle=56.3099
(has-ball B)
) ;;
(role B -1 ;; view angle=225
(ready-to-receive-pass B)
(has-ball B)
) ;;
) ;; end postcondition
(application-knowledge)
) ; end step 1
(step 20
;;------------------------------------------------------------------------
;; A runs to its new location
;;------------------------------------------------------------------------
(precondition
(timeout 15)
(role A -1 ;; view angle=56.3099
(has-ball B)
) ;;
(role B -1 ;; view angle=225
(has-ball B)
) ;;
) ;; end step 2
(postcondition
(timeout 35)
(role A -1 ;; view angle=56.3099
(in-rectangle-rel A 3.74 7.9 6.52 3.74 10.68 6.52 7.9 10.68)
197
) ;;
(role B -1 ;; view angle=225
(in-rectangle-rel A 7.78 -9.9 4.24 -6.36 0.71 -9.9 4.24 -13.44)
) ;;
) ;; end postcondition
(application-knowledge)
) ;; end step 1
(step 30
;;------------------------------------------------------------------------
;; B passes the ball back to A
;;------------------------------------------------------------------------
(precondition
(timeout 25)
(role A -1 ;; view angle=56.3099
(has-ball B)
) ;;
(role B -1 ;; view angle=225
(has-ball B)
) ;;
) ;; end preconditions
(postcondition
(timeout 30)
(role A -1 ;; view angle=56.3099
(ready-to-receive-pass A)
(has-ball A)
) ;;
(role B -1 ;; view angle=225
(has-ball A)
) ;;
) ;; end postconditions
(application-knowledge)
) ;; end step 3
) ; end of Givengo plan
198
A.3 Singlepass Plan
(plan Singlepass
(rotation-limit 120 15)
(step 10
;;------------------------------------------------------------------------
;; A passes the ball to B
;;------------------------------------------------------------------------
(precondition
(timeout 15)
(role A 10 ;; view angle=90
(has-ball A)
(in-rectangle-rel B 12.5 2.5 12.5 -2.5 17.5 -2.5 17.5 2.5)
) ;;
(role B -1 ;; view angle=270
(not has-ball B)
(in-rectangle-rel A 17.5 -2.5 17.5 2.5 12.5 2.5 12.5 -2.5)
) ;;
) ;; end precondition
(postcondition
(timeout 40)
(role A -1
(has-ball B)
) ;;
(role B -1
(ready-to-receive-pass B)
(has-ball B)
) ;;
) ;; end postcondition
) ; end step 1
) ; end of Singlepass plan
199
A.4 UEFA Fourwaypass Plan
(plan UEFA_Fourwaypass
(rotation-limit 120 30)
(step 1
;;------------------------------------------------------------------------
;; Player B passes the ball to player A
;;------------------------------------------------------------------------
(precondition
(timeout 40)
(role A -1 ;; view angle=45
(not has-ball A)
(in-rectangle-rel B 3.54 -10.61 10.61 -17.68 17.68 -10.61 10.61 -3.54)
(in-rectangle-rel C 14.14 0 21.21 -7.07 28.28 0 21.21 7.07)
) ;;
(role B -1 ;; view angle=135
(has-ball B)
(not has-ball C)
(in-rectangle-rel A 10.61 17.68 3.54 10.61 10.61 3.54 17.68 10.61)
(in-rectangle-rel C 10.61 -3.54 3.54 -10.61 10.61 -17.68 17.68 -10.61)
) ;;
(role C -1 ;; view angle=225
(has-ball B)
(in-rectangle-rel A 28.28 0 21.21 7.07 14.14 0 21.21 -7.07)
(in-rectangle-rel B 17.68 10.61 10.61 17.68 3.54 10.61 10.61 3.54)
) ;;
)
(postcondition
(timeout 50)
(role A -1 ;; view angle=45
(ready-to-receive-pass A)
(has-ball A)
) ;;
(role B -1 ;; view angle=135
(has-ball A)
) ;;
(role C -1 ;; view angle=225
(has-ball A)
) ;;
)
(application-knowledge)
) ;; end step
(step 2
;;------------------------------------------------------------------------
;; Player A passes the ball to player C
;;------------------------------------------------------------------------
(precondition
(timeout 40)
200
(role A -1 ;; view angle=45
(has-ball A)
(in-rectangle-rel C 14.14 0 21.21 -7.07 28.28 0 21.21 7.07)
) ;;
(role B -1 ;; view angle=135
(true B)
) ;;
(role C -1 ;; view angle=225
(has-ball A)
(in-rectangle-rel A 28.28 0 21.21 7.07 14.14 0 21.21 -7.07)
) ;;
)
(postcondition
(timeout 50)
(role A -1 ;; view angle=45
(has-ball C)
) ;;
(role B -1
(true B)
)
(role C -1 ;; view angle=225
(ready-to-receive-pass C)
(has-ball C)
) ;;
)
(application-knowledge)
) ;; end step
(step 3
;;------------------------------------------------------------------------
;; Player A runs to its new location
;;------------------------------------------------------------------------
(precondition
(timeout 25)
(role A -1 ;; view angle=45
(has-ball C)
) ;;
(role B -1 ;; view angle=135
;;(has-ball C)
) ;;
(role C -1 ;; view angle=225
(has-ball C)
) ;;
)
(postcondition
(timeout 60)
(role A -1 ;; view angle=45
;;(has-ball C)
(in-rectangle-rel C 14.14 0 21.21 -7.07 28.28 0 21.21 7.07)
201
(in-rectangle-rel A 3.54 10.61 10.61 3.54 17.68 10.61 10.61 17.68)
) ;;
(role B -1 ;; view angle=135
(has-ball C)
) ;;
(role C -1 ;; view angle=225
(has-ball C)
(in-rectangle-rel A 17.68 -10.61 10.61 -3.54 3.54 -10.61 10.61 -17.68)
) ;;
)
)
(step 4
;;------------------------------------------------------------------------
;; Player C passes the ball back to A
;;------------------------------------------------------------------------
(precondition
(timeout 25)
(role A -1 ;; view angle=45
;;(has-ball C)
) ;;
(role B -1 ;; view angle=135
;;(has-ball C)
) ;;
(role C -1 ;; view angle=225
(has-ball C)
) ;;
)
(postcondition
(timeout 60)
(role A -1 ;; view angle=45
(ready-to-receive-pass A)
(has-ball A)
) ;;
(role B -1 ;; view angle=135
(has-ball A)
) ;;
(role C -1 ;; view angle=225
(has-ball A)
) ;;
)
) ;; end step
) ;; end of UEFA_Fourwaypass plan
202
A.5 Interceptball Plan
(plan Interceptball
(step 1
(precondition
(role A -1
(true A)
) ;; end role A
) ;; end precondition
(postcondition
(timeout 50)
(role A -1
(has-ball A)
) ;; end role A
) ;; end postcondition
(application-knowledge
(case Interceptball A 1
(action-sequence
(intercept-ball A)
) ;; end action-sequence
) ;; end case
) ;; end application-knowledge
) ;; end step 1
(step 2
(goto 1)
)
) ;; end plan Interceptball
203
APPENDIX B
Example Plan
This appendix lists parts of the Givengo plan (Section A.2) after training and learning. Due
to the actual length of this plan after training, we only include some example cases for
each step.
(plan Givengo
(success 685)
(failure 381)
(rotation-limit 120 15)
(step 10
(precondition
(timeout 50)
(role A -1
(has-ball A)
(in-rectangle-rel B 5.96 -2.63 8.74 -6.8 12.9 -4.02 10.12 0.14)
) ;; end role A
(role B -1
(not has-ball B)
(in-rectangle-rel A 13.44 -1.41 9.9 2.12 6.36 -1.41 9.9 -4.95)
) ;; end role B
) ;; end precondition
(postcondition
(timeout 50)
(role A -1
(has-ball B)
) ;; end role A
(role B -1
(has-ball B)
(ready-to-receive-pass B)
) ;; end role B
) ;; end postcondition
204
(application-knowledge
(case Givengo A 10
(grid-unit 1.5)
(success 753)
(failure 8)
(rotation 0)
(opponent-constellation
)
(action-sequence
(pass-ball A B)
) ;; end action-sequence
) ;; end case
(case Givengo A 10
(grid-unit 1.5)
(success 23)
(failure 15)
(rotation 0)
(opponent-constellation
(7 -2)
)
(action-sequence
(dribble-ball-rel A 6.75 0.75 6.75 -2.25)
(pass-ball A B)
) ;; end action-sequence
) ;; end case
(case Givengo A 10
(grid-unit 1.5)
(success 3)
(failure 9)
(rotation 0)
(opponent-constellation
(4 -3)
(7 -1)
)
(action-sequence
(dribble-ball-rel A 3.75 0.75)
(pass-ball A B)
) ;; end action-sequence
) ;; end case
(case Givengo A 10
(grid-unit 1.5)
(success 8)
(failure 12)
(rotation -15)
(opponent-constellation
(5 -1)
)
(action-sequence
205
(dribble-ball-rel A 2.25 -0.75 2.25 -2.25 3.75 -2.25
3.75 -3.75 5.25 -3.75 5.25 -6.75)
(pass-ball A B)
) ;; end action-sequence
) ;; end case
(case Givengo A 10
(grid-unit 1.5)
(success 1)
(failure 2)
(rotation 10.4218)
(opponent-constellation
(7 1)
(5 -2)
(2 0)
)
(action-sequence
(dribble-ball-rel A 6.75 0.75)
(pass-ball A B)
) ;; end action-sequence
) ;; end case
(case Givengo A 10
(grid-unit 1.5)
(success 1)
(failure 0)
(rotation -69.4121)
(opponent-constellation
(0 5)
(1 1)
(0 1)
(-1 0)
)
(action-sequence
(dribble-ball-rel A 0.75 -2.25)
(pass-ball A B)
) ;; end action-sequence
) ;; end case
...
) ;; end application-knowledge
) ;; end step 10
(step 20
(precondition
(timeout 15)
(role A -1
(has-ball B)
) ;; end role A
(role B -1
206
(has-ball B)
) ;; end role B
) ;; end precondition
(postcondition
(timeout 35)
(role A -1
(in-rectangle-rel A 3.74 7.9 6.52 3.74 10.68 6.52 7.9 10.68)
) ;; end role A
(role B -1
(in-rectangle-rel A 7.78 -9.9 4.24 -6.36 0.71 -9.9 4.24 -13.44)
) ;; end role B
) ;; end postcondition
(application-knowledge
(case Givengo A 20
(grid-unit 1.5)
(success 7)
(failure 2)
(rotation -69.3622)
(opponent-constellation
)
(action-sequence
(goto-area-rel A 8.71123 -0.715564 5.79803 -4.78339
9.86586 -7.6966 12.7791 -3.62877)
) ;; end action-sequence
) ;; end case
(case Givengo A 20
(grid-unit 1.5)
(success 1)
(failure 1)
(rotation -60)
(opponent-constellation
(7 3)
)
(action-sequence
(goto-area-rel A 8.7116 0.711065 6.49894 -3.77649
10.9865 -5.98915 13.1992 -1.5016)
) ;; end action-sequence
) ;; end case
(case Givengo A 20
(grid-unit 1.5)
(success 3)
(failure 0)
(rotation 10.4218)
(opponent-constellation
(7 2)
(4 -1)
)
(action-sequence
207
(goto-area-rel A 2.24925 8.44621 5.7359 4.85772
9.32439 8.34437 5.83774 11.9329)
) ;; end action-sequence
) ;; end case
(case Givengo A 20
(grid-unit 1.5)
(success 1)
(failure 0)
(rotation -3.57823)
(opponent-constellation
(5 2)
(7 1)
(-1 -1)
)
(action-sequence
(goto-area-rel A 4.22576 7.65118 6.74071 3.32579
11.0661 5.84074 8.55115 10.1661)
) ;; end action-sequence
) ;; end case
(case Givengo A 20
(grid-unit 1.5)
(success 1)
(failure 0)
(rotation -24.5782)
(opponent-constellation
(2 3)
(2 5)
(8 3)
(3 0)
(0 -1)
)
(action-sequence
(goto-area-rel A 6.68702 5.62862 7.48485 0.689236
12.4242 1.48706 11.6264 6.42644)
) ;; end action-sequence
) ;; end case
) ;; end application-knowledge
...
) ;; end step 20
(step 30
(precondition
(timeout 25)
(role A -1
(has-ball B)
) ;; end role A
(role B -1
208
(has-ball B)
) ;; end role B
) ;; end precondition
(postcondition
(timeout 30)
(role A -1
(has-ball A)
(ready-to-receive-pass A)
) ;; end role A
(role B -1
(has-ball A)
) ;; end role B
) ;; end postcondition
(application-knowledge
;; similarity=0
(case Givengo A 30
(grid-unit 1.5)
(success 686)
(failure 381)
(rotation 0)
(opponent-constellation
)
(action-sequence
(intercept-ball A)
) ;; end action-sequence
) ;; end case
) ;; end application-knowledge
) ;; end step 30
) ;; end plan Givengo
209
APPENDIX C
Synchronization of clients with
Soccer Server
A client program can be synchronized with the Soccer Server using an undocumented
feature of the Server that has to do with how the Soccer Server handles the switching of
the viewing modes on behalf of client programs. By taking advantage of the deterministic
behavior of the Server in response to viewing mode changing commands from clients, it
is possible for each client program to schedule incoming visual feedback messages from
the Server such that a client program can have the longest possible time during an action
The Server provides visual feedback period to each client program once every 150ms,
and each client can send action commands to the Server once every 100ms. This means
that a client receives two visual feedbacks out of every consecutive three action cycles. If
a client changes its viewing mode to narrow or low, the visual feedback period reduces
to one-half of the default, i.e., 75ms. If the client changes its view mode to narrow and
low, the feedback period reduces to one-fourth of the default, i.e., 37.5ms. This means that
the server checks every 37.5ms to see if it is time to send a visual feedback to this client.
Therefore, assuming no other delays, the server will check whether to send a visual to the
client or not at intervals 0ms, 37.5ms, 75ms, 112.5ms, 150ms, 187.5ms, 225ms, 262.5ms and
1
This appendix is an edited and supplemented version of an email message sent by Tom Howard
([email protected]) on March 5, 2002, to the RoboCup simulation league mailing list (robocup-sim-l@
usc.edu) describing how to synchronize client programs with the Soccer Server.
210
...
action cycle 1 action cycle 2 action cycle 3 . . .
0.0ms 100.0ms 200.0ms 300.0ms
0.0ms 37.5ms 75.0ms 12.5ms 50.0ms 87.5ms 25.0ms 62.5ms 0.0ms 37.5ms 75.0ms 12.5ms
0.0ms 37.5ms 75.0ms 112.5ms 150.0ms 187.5ms 225.0ms 262.5ms 0.0ms 37.5ms 75.0ms 112.5ms
. . .
visual cycle 1 visual cycle 2
...
A B
C D
E F
G H
I J
K L
M N
O P
...
Figure C.1: Timing of visual feedback messages sent by the server with respect to action
cycles
300ms every 3 action cycles (equivalently, every 2 visual cycles). At the 300ms mark, the
entire cycle sequence completes and a new one starts. That is, the feedback cycle is back
to the 0ms point. So, for example, if the server sent a visual feedback at the 37.5ms mark,
it would send another 150ms later, at the 187.5ms mark. The next feedback would be sent
at the 37.5ms mark of the first action cycle in the next cycle sequence.
Figure C.1 is a diagram that depicts all decision points at which the server may check
whether it needs to send a visual feedback to a given client. On top of the diagram are
action cycles 1, 2, 3, and so on. In two of every three consecutive action cycles, each client
receives a visual feedback. This is why the timeline in the middle part of the diagram
shows two visual cycles. The bottom timeline shows all possible pairs of decision points
at which the server may send visual feedback messages to a given client.
As Figure C.1 shows, the intervals 0ms, 37.5ms, 75ms, 112.5ms, 150ms, 187.5ms, 225ms,
262.5ms and 300ms, map onto eight different intervals in a single action cycle. Since the
server goes through the same procedure every cycle, it has to check whether to send a
visual feedback to a client at 0ms, 12.5ms, 25ms, 37.5ms, 50ms, 62.5ms, 75ms or 87.5ms.
211
The mapping of the 300ms interval marks onto single action cycle intervals marks is
given in Table C.1. Note that the order of the values on the right-hand-side in Table C.1
Table C.1: Mapping of all possible visual feedback message times in a 300ms period onto
a single action cycle
So, if a client is in default viewing mode, the server will send visual feedback to it
every 150ms. However, there is no facility to specify whether this will be done at the
beginning of one cycle, the middle of the next, or any other time. So, depending on when
the client happens to connect to the server during a simulation cycle, the client will get
visual feedback at one of the four intervals in the two consecutive action cycles shown in
Table C.2:
Action Cycle T Action Cycle (T + 1) Timeline Reverse Timeline
0ms 50ms A–B I–J
12.5ms 62.5ms G–H O–P
25ms 75ms M–N E–F
37.5ms 87.5ms C–D K–L
Table C.2: The visual feedback time offsets from the beginning of an action cycle and
corresponding timelines shown in Figure C.1
For example, if the client receives visual feedback right at the beginning of action cycle
T , it will receive the next visual feedback after 50ms from the beginning of the next action
cycle, (T + 1). If it receives visual feedback after 12.5ms from the beginning of T , then it
will receive its next feedback 62.5ms after the start of action cycle (T + 1), and so on.
The ”Timeline” column in Table C.2 shows the timeline in Figure C.1 that each pair
212
of values corresponds to. The ”Reverse Timing” column is equivalent to the ”Timeline”
column, except that the order of the timing values are reversed, since the process is cyclic
or symmetric. For example timing line G–H starts at 12.5ms and extends until 62.5ms. Its
reverse version, O–P, starts at 62.5ms and extends until the 12.5ms point in the next cycle.
We can see from Table C.2 that the first pair is the most desirable because it has the
least average offset from the beginning of the action cycles during which the client will
receive visual feedback. That is, we wish to get visual feedback messages from the server
as early as we can in any given cycle so that the reasoning time for an agent can be
maximized. Conversely, the last pair is the least desirable, since it has the highest average
offset duration.
Since when a client connects to the server cannot be controlled precisely, the visual
feedback timing intervals of the client will match one of the above possibilities. However,
by taking advantage of the server behavior, it is possible to modify the timings after a client
connects to the server so that the client can select the precise timing of the future visual
feedbacks it will receive from the server (assuming zero delay in message transmission
from the server to the client. The times shown are therefore those at which the server can
0.0ms 37.5ms 75.0ms 12.5ms 50.0ms 87.5ms 25.0ms 62.5ms 0.0ms 37.5ms 75.0ms 12.5ms 50.0ms 87.5ms 25.0ms 62.5ms 0.0ms 37.5ms 75.0ms
A B
. . . . view mode = NARROW + LOW view mode = NORMAL + HIGH . . . . . . . . .
Figure C.2: A possible synchronization process of the client with the server
Figure C.2 demonstrates this synchronization process. If the client changes its viewing
mode to narrow and low, it will receive visual feedback every 37.5ms. In the figure, the
time at which the server sends a visual feedback message is indicated by an arrowhead.
On close inspection of Figure C.1, it will become clear that, in every 3 cycles, the
client will receive 3 visual feedbacks per cycle in 2 consecutive action cycles and 2 visual
213
feedbacks per cycle in another single action cycle. So if the client receives 3 visual
feedbacks in cycle T , 3 in cycle (T + 1), then we know, with certainty, that the client will
Moreover, if the client changes its viewing mode to normal and high after the very first
visual feedback in (T + 3), which would arrive at the 0ms mark in the overall cycle, then
the next visual feedback in cycle (T + 4) will be at 50ms from the beginning of that cycle
(see point A in Figure C.2), and the one following visual feedback will arrive in cycle (T +6)
at 0ms (see point B in Figure C.2) and so on. From this point on, the client starts receiving
visual feedbacks as early as possible in each cycle, that is at 0ms and 50ms offset points.
We should also note that the client will need to do the same trick after every change to
narrow and low mode, and it will need to do a similar trick for after every change to narrow
or low.
Previously, we mentioned that the server checks to see if it needs to send visual
feedback messages every 37.5ms. The server actually cannot send visual feedbacks every
37.5ms, since the internal timer interval in the server is 10ms, which is the lowest possible
resolution we can get on most machines. Since 37.5 is not a multiple of 10, some rounding
off occurs in the server. Table C.3 gives the correct visual feedback pairs (compare these
Table C.3: Actual visual feedback time offsets from the beginning of each action cycle
As we can see, rounding off makes bad synchronization even worse, because the
server ends up sending its visual feedbacks later (Table C.3) than it would have otherwise
214
APPENDIX D
Position triangulation in Soccer
Server
This appendix describes how to triangulate a position given the possibly noisy polar
coordinates of two points whose global coordinates are known. We assume that the
angle components of the polar coordinates are relative to the current line of sight of the
observer where counterclockwise angles are negative and clockwise angles are positive.
For example, in Figure D.1, if we suppose that the observer is at point I0 and that it sees
two objects located at points A and B, then the polar coordinates of A would be given
as (rA , tA ) and the polar coordinates of B would be given as (rB , tB ), where tA = δ and
tB = ω are angles relative to the observer’s current line of sight indicated in the figure.
Using the radii values in the two polar coordinate pairs, we can draw two circles,
whose centers are at A and B. Both circles pass through points I0 and I1 where they
intersect. Then line segment AB is then, by definition, perpendicular to the line segment
I0 A = I1 A = rA ,
I0 B = I1 B = r B ,
I1 M = I0 M = h,
AM = a, MB = b, and
d=a+b
215
where values rA , rB , and d will be given in the triangulation problem.
(xB, yB )
x y
α
α β
δ ω
Figure D.1: The setup of the position triangulation problem that involves determining
the global position of the observer and the global angle of its line of sight, given polar
coordinates of two points A and B relative to the observer, (rA , δ) and (rB , ω). The global
(x, y) coordinates of A and B are assumed to be known. Two circles drawn centered at
A and B with radii rA and rB intersect at I0 and I1 . Therefore, the observer is at one of
these two intersection points. By definition, the line that joins the two circle centers, A
and B, cuts the line that joins the two intersection points I0 and I1 into two halves at M ,
(Mx , My ), each half of length h. It is also the case that the distance between A and either
of the intersection points is equal to the polar radius rA . Similarly, the distance from B to
either of the intersection points is rB . |M A| = a, |M B| = b, and d = a + b.
3. Finally, we test the given relative angles δ and ω to decide whether the observer is at
I0 or I1 .
216
To help illustrate the triangulation process, we have already supposed that the observer
is at I0 , but note that this knowledge about the location of the observer will not be available
in the problem. Instead, we will have two possible points to choose from, namely I0 and I1
as shown in Figure D.1. We must also note that Figure D.1 only illustrates the most general
case where there are two intersections between the two circles formed by the given polar
coordinates of the two known objects. It is also possible that the two circles may intersect
tangentially, that is, at one single point. In this case, h would be 0 and a = rA and b = rB .
d
M
rB
I1 rA A
Figure D.2: 4I1 AB from Figure D.1 with height h, d = b + a, |BM| = b and |MA| = a
To compute the coordinates of M , we have to compute the length of line segment KI0
(or NI1 ). Since, in triangle AI1 B, we know rA , rB , and d, we can compute h, a, and b.
p
d= (xA 2 − xB 2 ) + (yA 2 − yB 2 )
To see how we can compute a and b, let us look at Figure D.2 that shows the same scenario
where 4I1 AB is a triangle with height h. For this triangle, we can compute b, a, and h,
given d, rB , and rA . Based on triangle 4I1 AB, we have the following relationships:
b2 + h2 = rB
2
(D.1)
a2 + h2 = rA
2
(D.2)
217
Subtracting Equation D.2 from Equation D.1, we get:
b 2 + h2 2
= rB
a2 + h2 2
= rA
−
b2 − a2 2 − r2
= rB A
Rearranging the left-hand size of the last equation above for a2 , we get
a2 = rA
2
+ b2 − rB
2
(D.3)
Since b + a = d, then
b=d−a (D.4)
a2 = rA
2
+ (d − a)2 − rB
2
a2 = rA
2
+ d2 − 2da + a2 − rB
2
2
2da = rA + d 2 − rB
2
(D.5)
2 − r 2 + d2
rA B
a= (D.6)
2d
To get the equation for b, we substitute for a from Equation D.6 into Equation D.4 and get:
2 − r 2 + d2
rA B
b=d−
2d
2db = 2d2 − rA
2 2
+ rB − d2
2db = d2 − rA
2 2
+ rB
Then
2 − r 2 + d2
rB A
b= (D.7)
2d
218
Then, in summary, for Figure D.1, we have
rA 2 − r B 2 + d 2
a = (D.8)
2d
rB − r A 2 + d 2
2
b = (D.9)
2d
p
h = rA 2 − a2 (D.10)
p
h = rB 2 − b2 (D.11)
Before proceeding further, we must first check whether an intersection is possible between
the circles formed by the radii of A and B. For intersection to occur, the distance between
the two circle centers must be at least as large as the addition of the two radii. So, we
check the truth value of the condition ((d − (rA + rB )) > 0). If true, it means there can
be no intersection between the two circles. This will be the case if there is inconsistency
in the global position data or the reported radii values, and, due to this inconsistency,
the triangulation computation aborts at this point. If the above condition is false, we
proceed by checking if the computed h value is consistent with the problem. We know
from Equation D.10 and Equation D.11 that |a| cannot be larger than rA and |b| cannot be
larger than rB . At these border conditions, |a| = rA and |b| = rB . For example, consider
In general, if the input data is noisy, we can have situations where h becomes a complex
number, which cannot possibly be the case in reality. So, in such cases, we have to set h to
zero, which is the smallest value h can have. This correction is required when, for example,
the rA value reported is smaller than it actually is. Consider, for example, the following
√
rA = 100, (xA , yA ) = (10, 2),
√
rB = 234, (xB , yB ) = (15, 3),
tA = 0, tB = 0
√
where the rA value is less than its actual 104. If the rA value were noiseless, as is the
case with circles drawn with a solid line in Figure D.3, there would be a single point of
219
(15,3)
(10,2)
(0,0)
Figure D.3: An example case of triangulation where the known reference points and the
position of the observer are collinear. The solid circles depict the case with no noise, and
the dashed circle associated with point A depicts the case when rA is reported less than
its actual value. The observer, O, is at (0, 0), A is at (10, 2), and B is at (15, 3). The circles
associated with two noisy versions of the rA value (rA,noisy ) are drawn with a dashed line.
intersection as shown. Since rA value is a smaller than its true value, we can see that that
the two circles would not intersect, not because they are far apart from each other but
because one is completely enclosed in the other. Based on the above input values, using
we get for h. If rA < |a|, the term under the square-root becomes negative, and this leads
to imaginary h values. Since the smallest value of h is 0, then the largest value of a is rA ,
i.e., 0 ≤ |a| ≤ rA . That is, |a| can, in reality, never be larger than rA . Therefore, to correct
this situation that may arise due to noise in the input data, we set h to zero. The reason for
220
the a value above being negative is due to the height segment not intersecting the base of
the triangle between the two points, A and B, that is, strictly within the AB segment. If we
take a mirror image of A on the opposite side of O, this time a would be the mirror of the
previous value but positive: +10.59. In addition, where the height segment intersects the
base (point O) would be within the AB segment –d would naturally have a different value
also. Since the a value is always squared when used, the end result does not change.
Figure D.4: Computation of the two base segments (a and b) in a triangle formed by
the height segment intersecting the base when the height is zero. The figure shows an
infinitesimal height segment, h to demonstrate that when the height segment does not
intersect the base of the triangle between the two vertices that form the base (A and B), the
value of a will be negative by Equation D.8. By Equation D.10 and Equation D.11, |a| = rA
and |b| = rB
Next, we compute (Mx , My ). In Figure D.1, triangles 4BAZ and 4MAL are similar.
Therefore, |AL| = a ∗ (xB − xA )/d. Similarly, from the same similar triangles, 4BAZ and
Therefore, |ML| = a ∗ (yB − yA )/d. That is, the (x, y) coordinates of M, relative to A are
Mx = xA + (a ∗ (xB − xA )/d
My = yA + (a ∗ (yB − yA )/d
221
Now we need to compute the x- and y-offset to points I0 and I1 from M . So we need to
compute |I0 K | (= |I1 N |) and |MK | (= |MN |). Using similar triangles 4BAZ and 4I0 MK ,
we have
Therefore, |I0 K | = h ∗ (yB − yA )/d. Similarly, |MK | = h ∗ (xB − xA )/d. Hence, we have
Next, we compute the global angles with respect to the horizontal from each
intersection point I0 and I1 to the two centers A and B (i.e., locations of known markers).
We use a user-defined function atan2r, which is similar to the C function atan2 but takes
into account the signs of its arguments for determining the quadrant of the resulting angle
and resizes the return value to fit the range [0.0 . . 360.0]. The reference point from which
these angles need to be calculated are the intersection points, not the two centers.
Since we have four possible angles, we compute four possible global angles of sight for
the agent by adding the given relative angles tA and tB to the angles we computed above.
Note that tA and tB are in Server angle convention, and, therefore, we invert them to
222
convert them to the Cartesian convention we use:
Now we have two sets of candidate coordinates for the global angle of the current line
of vision of the agent. In general, under noiseless conditions, the angles in one of these
two sets would be identical. The only exception to this condition is when there is only
one intersection point. In that case, all four angles would be identical with noiseless input
data. Next, we compute the differences between each pair of angles associated with the
sign indicates the relative direction of the second angle from the first. For example,
we have to traverse 30 degrees counterclockwise; hence the + sign. On the other hand,
When the input data is noisy, the case where there would otherwise be a single point
of intersection may degenerate into a case where there are two symmetrical intersection
points. This situation is shown in Figure D.3 where the outer dashed circle intersects with
the larger circle drawn in solid line. The intersection points are marked with small boxes.
So, both sets of candidate angles would have to be correct, but, due to the orientation of the
two intersection points, the angle differences computed above in each case would carry a
different sign. Also, the farther A and B are from each other, the larger the separation of the
223
two intersection points would be. Therefore, choosing one point or the other would throw
off the agent since it is a virtual guarantee that neither are correct. That is why, in such a
case, we need to compute the global angle by taking an average of the two angles. But we
cannot compute this average as in ((v1+v2)/2). Instead we have to use the angle difference
values instead, since adding angles in the 1st (0-90 degrees) and 4th (270-360 degrees)
quadrants and then dividing the result by 2 would give an incorrect result. Averaging
the differences gives us a value in between the angles of the two intersection points, and
this would be the closest to the actual global viewing angle. To check for the symmetrical
case, we look for the case where the absolute difference between the two angle differences
computed above are almost equal. The threshold value symmetricalAngleMargin is a small-
2. The case where (fabs(angleDiff Θ0A ,Θ0B ) < fabs(angleDiff Θ1A ,Θ1B )) is true, which
3. The final case where (fabs(angleDiff Θ0A ,Θ0B ) < fabs(angleDiff Θ1A ,Θ1B )) is false,
which means that intersection point I1 is the actual position of the agent.
224
where (globalx , globaly ) are the global (x, y) coordinates of the agent, and globalAngle is its
globalx = I0x
globaly = I0y
globalx = I1x
globaly = I1y
225
APPENDIX E
Velocity estimation in Soccer
Server
The estimation of the velocities of moving objects observed by a given player is critical for
reactive reasoning in the Soccer Server environment. For example, estimating how long it
may take an agent to intercept an incoming ball depends on knowing the velocity of the
ball.
For the sake of clarity, this appendix provides the derivation of the formulas used to
estimate the x- and y-components of the velocity of any given moving object in the Soccer
Server environment. This derivation is based on the formulas used by the Soccer Server to
provide related information to client programs (i.e., players). As part of its visual feedback,
the Soccer Server provides information about the distance of a moving object (such as the
ball or another player) from the observer, and the change in the distance (distChng below)
and the change in the direction of that object (dirChng below). The Soccer Server computes
these values for each seen moving object, m, using the following formulas (See [Chen et al.,
where distChng is the change in the direction of object m and dirChng is the change in the
direction of m. (vrx , vry ) is the true current velocity of m, distance is the current distance
226
of m from the observing player, and (erx , ery ) is a unit vector in the direction that the seen
object, m, from the perspective of the observer. The unit vector (erx , ery ) can be computed
as follows:
where observerGlobalAngle is the current global angle of the neck of the observer and
direction is the relative offset angle of m from the neck of the observer as reported by
the Soccer Server. normalizeAngle is a function that normalizes an input angle value
of the unit vector that points in the direction of the seen object, m, from the center
point of the observing player. Since the angle convention of the Soccer Server is the
Equation E.3 so that we can add it to the observerGlobalAngle value, which is in Cartesian
convention. Also note that we negate the return value of the normalizeAngle function
in Equation E.3. This negation is to convert the resultant angle value from the Cartesian
to Server convention such that unitVectorAngle is in the angle convention of the Soccer
Server. polarToUnitVector is a function that converts the polar coordinate description that
represents the direction of a non-unit vector to the unit vector (erx , ery ). Hence, the only
unknowns in the Soccer Server formulas (Equation E.1, Equation E.2) are vrx and vrx .
Since both the distChng and dirChng values provided by the Server are not exact but
noisy, the formulas we derive here can at best provide an estimation of the true velocity of
Rearranging Equation E.2 to isolate vrx on the left-hand-side of the equation, we get:
dirChng ∗ π ∗ distance
= −(vrx ∗ ery ) + (vry ∗ erx )
180
dirChng ∗ π ∗ distance
(vrx ∗ ery ) = (vry ∗ erx ) −
180
erx dirChng ∗ π ∗ distance
vrx = vry ∗ − (E.5)
ery 180 ∗ ery
227
Rearranging Equation E.1 to isolate vry on the left-hand-side of the equation, we get:
Multiplying both sides with e2ry in E.7, we get the equation for vrx :
Substituting for vrx from E.8 into E.6, we get the equation for vry :
228