# Symbolic Manipulation Planning with Discovered Object and Relational
Predicates

Alper Ahmetoglu1, Erhan Oztop2,3, Emre Ugur1 1Department of Computer
Engineering, Bogazici University<EMAIL_ADDRESS>of
Computer Science, Ozyegin University3OTRI, SISReC, Osaka University

###### Abstract

Discovering the symbols and rules that can be used in long-horizon planning
from a robot’s unsupervised exploration of its environment and continuous
sensorimotor experience is a challenging task. The previous studies proposed
learning symbols from single or paired object interactions and planning with
these symbols. In this work, we propose a system that learns rules with
discovered object and relational symbols that encode an arbitrary number of
objects and the relations between them, converts those rules to Planning
Domain Description Language (PDDL), and generates plans that involve
affordances of the arbitrary number of objects to achieve tasks. We validated
our system with box-shaped objects in different sizes and showed that the
system can develop a symbolic knowledge of pick-up, carry, and place
operations, taking into account object compounds in different configurations,
such as boxes would be carried together with a larger box that they are placed
on. We also compared our method with the state-of-the-art methods and showed
that planning with the operators defined over relational symbols gives better
planning performance compared to the baselines.

##  I INTRODUCTION

Figure 1: An overview of the proposed method. (Top) The encoder network
$\sigma_{p}$ learns unary symbols over object features while the self-
attention network $\sigma_{r}$ learns relational symbols. The aggregation in
the middle (see Equation 3) fuses unary and relational symbols with action
into a vector representation for each object, which is given as input to the
decoder network $g$ to predict the effect of the executed action. (Bottom)
After learning operators defined over the learned symbols, we can find a
sequence of actions that reach the goal state from the initial state with AI
planners.

A long-standing challenge for artificial intelligence (AI) research is to
build a generalist agent that can parse and understand its environment through
its sensors, carry out desired tasks by acting on the environment, and update
its knowledge when necessary to adapt to new situations. The difficulty in
achieving this stems from the fact that we do not have a well-defined, robust,
and generic representation of the environment that applies to a sufficiently
large class of tasks. The requirements and the resolution of the
representation change drastically when the aimed task properties and/or the
capabilities of the agent change. For example, a robotic agent tidying up the
table needs a different representation of the environment than a robot tying a
rope. It is not even clear whether soft and rigid objects should be
represented within a single representational framework. Nevertheless, once a
symbolic representation of the environment that is appropriate for the task at
hand can be obtained, many AI search techniques become available for
efficiently finding a solution to problems such as planning to achieve a goal
[1].

An effective approach to build a set of symbols for obtaining the leverage of
off-the-shelf symbolic systems is to focus on the preconditions and effects
related to the actions of an agent [2, 3, 4]. Learning precondition-effect
relations effectively models the environment based on the agent’s
capabilities. This is preferable for filtering out irrelevant information that
would otherwise increase the complexity of the problem. Once the necessary
symbols are learned, the environment description can be translated, for
example, into Planning Domain Definition Language (PDDL) [5] that allows the
use of fast domain-independent planners such fast downward [6] or fast-forward
[7]. Alternatively, one can first compress the experience of the agent, i.e.,
the sensory state-space explored, into a symbolic space using deep neural
networks, then encode symbolic transitions either with PDDL or learn a
separate module for generating the necessary action from the current state for
a given goal state [8, 9, 10]. One advantage of this approach is that it can
be integrated with other types of deep architectures to process different of
sensory information, such as images, sounds, or proprioceptive information.

Our previous work, DeepSym [11], stands in between these two approaches by
having a differentiable, deep architecture that can learn symbolic
representations for the preconditions of the executed action. DeepSym is
composed of an encoder-decoder network with binary bottleneck layers for
learning object symbols to predict the effect of the executed action. In a
follow-up work [12], the architecture is improved by employing a transformer
layer in the decoder, allowing symbols to interact to model multi-object
effects. However, the interaction of symbols remains implicit in the weights
of the transformer and cannot be translated into PDDL in a straightforward
way, thus limiting the domain-independent planning capability. In other words,
even though the architecture models relations between objects, these relations
cannot be expressed as relational symbols between objects. Our recent work
[13] proposes a solution for this problem with an architecture that can learn
not only unary object symbols but explicitly encodes relations between objects
using binary attention weights. However, symbolic-level transitions from the
learned symbols that enable domain-independent planning were not considered.

In the current study, we first learn a set of unary and relational symbols
between objects using the Relational DeepSym architecture [13], then we
propose a method to build abstract operators defined over these unary and
relational symbols that describe the symbolic transition of a state when an
action is executed. We translate these operators into PDDL descriptions and
show that they can be used for planning with off-the-shelf AI planners in a
tabletop object stacking task. We compare our method with [11] and [12] in
terms of effect prediction accuracy and planning performance. Our results show
that planning with the operators defined over relational symbols performs
better than the baselines.

##  II RELATED WORK

There is a large body of literature where the learned affordances or effect
predictors have been used to make plans in the continuous or sub-symbolic
space of the robots [14, 15]. Our work is mainly related to methods that study
symbol emergence [16] and that discover symbolic representations of the
environment from the continuous experience of the robot through its sensors
with the aim of planning with off-the-shelf AI planners.

[2, 3] showed that it is necessary and sufficient to learn symbols for the
precondition and the effect set of the agent’s action repertoire to enable
planning. Based on this observation, they learn a set of symbols that cover
actions’ pre- and post-conditions and use them to build a PDDL description of
the environment. These works use a global state representation in which each
object is represented in the global state vector, restricting the use of
previously learned symbols. In follow-up work, [17] builds upon this framework
by using an ego-centric state representation, allowing agent-centric symbols
to be shared through different tasks. [4, 18] considers object-centric
precondition and effect set to find discrete symbols for producing PDDL
descriptions. Similarly, [19] used object-centric representations, which
increases the generalization of symbols through objects with the same
properties. Our work differs from these in that we learn symbols with deep
neural networks by minimizing the effect prediction error instead of
clustering the state space.

In another line work, [20, 21, 22] proposed a bi-level planning schema in
which a set of operators and corresponding samplers are learned from
previously acquired symbols that allow the agent to make refined plans that
can consider the geometric information. [23] learns predicates from
demonstrations with a surrogate objective for planning. [24] learns policies
parameterized by neural networks based on the symbolic state transitions.
Quite similar to our motivation, [25] learn a set of operators by considering
only a subset of abstract effects to prevent learning complex operators. The
main difference between our work and theirs is that we select this subset as
the relevant symbols for the action, whereas they consider universal
quantifiers in the abstract effect.

[8, 9, 10] use a state autoencoder to compress the state space into a low-
dimensional binary vector and an action autoencoder to learn action
representations from low-level state transitions. Similarly, [11] uses an
encoder-decoder style architecture to generate symbolic representations in the
bottleneck layer while minimizing the effect prediction error. In follow-up
work, [12] employed transformer layers [26], enabling the flow of information
between object symbols to model multi-object effects. Recently, [13] proposed
a relational formulation of the encoder-decoder architecture that explicitly
models relations between objects using binary attention weights, learning
unary and relational symbols simultaneously. Our work builds upon this
architecture by proposing a method to learn operators defined over these
symbols that can be used for planning with AI planners.

##  III METHOD

###  III-A Problem Definition

This paper deals with the problem of learning (1) a symbolic representation of
an environment defined over a finite set of objects, which is sensed as a
continuous sensory state, and (2) a set of operators that represent the
dynamics of sensory transition dynamics at the symbolic level, which allows
domain-independent planning with the learned symbols by the use of off-the-
shelf AI planners.

An environment is characterized by a tuple $(\mathcal{X},\mathcal{A},P)$ where
$\mathcal{X}$ denotes the continuous sensory state of the environment (which
is called state-space from now on), $\mathcal{A}$ is a finite set of actions
that the agent can execute, and
$P(\mathbf{X}^{\prime}\mid\mathbf{X},\mathbf{a})$ is the probability that
taking action $\mathbf{a}\in\mathcal{A}$ at state $\mathbf{X}$ results in
state $\mathbf{X}^{\prime}$. An environment instance consists of a set of
objects $\\{o_{1},\dots,o_{n}\\}\in\mathcal{O}$ each having a
$d_{o}$-dimensional continuous-valued feature vector
$\mathbf{x}_{i}\in\mathbb{R}^{d_{o}}$ defining the state of the environment as
an unordered set of feature vectors
$\mathbf{X}:=\\{\mathbf{x}_{1},\dots,\mathbf{x}_{n}\\}\in\mathcal{X}$.
$\mathbf{X}$ is not a fixed-size vector but a variable size depending on the
number of objects $n$ in the environment. An action $\mathbf{a}$ is a fixed-
size vector representing a high-level parameterized movement primitive that
the agent can execute, such as picking an object. Given an initial state
$\mathbf{X}_{0}$ and a goal state $\mathbf{X}_{g}$, the objective is to find a
sequence of actions $(\mathbf{a}_{1},\dots,\mathbf{a}_{k})$ that maximizes the
probability of reaching the goal state.

We are interested in learning the mapping
$f:\mathcal{X}\rightarrow\mathcal{P}$ that transforms a state vector
$\mathbf{X}$ into a set of predicates (or symbols)
$\Sigma:=\\{\sigma_{1}(\mathbf{X}),\dots,\sigma_{m}(\mathbf{X})\\}\in\mathcal{P}$,
where $\sigma_{i}:\mathcal{X}\rightarrow\\{0,1\\}^{d_{k}}$ is a binary
function where $d_{k}$ is an environment dependent fixed dimension. After
symbols are learned, we can find a set of operators (i.e., lifted actions in
the symbolic space) $\\{\phi_{1},\dots,\phi_{k}\\}\in\Phi$ in which each
operator $\phi_{i}:\Sigma\rightarrow\Sigma$ transforms the current symbols
into a new set of symbols. Once symbols and operators are learned, we can
transform the initial state $\mathbf{X}_{0}$ and the goal state
$\mathbf{X}_{g}$ into symbolic representations $\Sigma_{0}$ and $\Sigma_{g}$,
respectively, and then find a sequence of operators
$(\phi_{1},\dots,\phi_{k})$ that transforms $\Sigma_{0}$ into $\Sigma_{g}$,
and then execute the corresponding sequence of actions
$(\mathbf{a}_{1},\dots,\mathbf{a}_{k})$ to reach the goal state.

Note that the proposed operator learning system is built on top of our symbol
learning network architecture [13]. Thus, to assess the added value of
learning explicit symbolic transitions, we compare the performance of the
proposed model in effect prediction and planning with [11] and [12] in a
tabletop object manipulation setup.

###  III-B Learning Unary and Relational Symbols

Figure 1 shows an outline of the method. The architecture is composed of four
main blocks.

####  III-B1 Encoder Network

$\sigma_{p}:\mathcal{X}\rightarrow\mathcal{P}$ is a multi-layer perceptron
(MLP) with Gumbel-Sigmoid (GS) [27] activation that outputs a binary number
for each object in the environment. We treat this as a unary predicate
$\sigma_{\text{p}}(\mathbf{x}_{i})$ that encodes the property of an object.
The number of properties that can be encoded is bounded by the output
dimensionality of the MLP – at most $2^{\text{d}}$ properties can be encoded
with $d$-dimensional outputs.

####  III-B2 Self-Attention Network

$\sigma_{r}:\mathcal{X}\rightarrow\mathcal{P}$ is a multi-layer perceptron
combined with a modified version [13] of the original self-attention layer
[26]. Given a state vector
$\mathbf{X}=\\{\mathbf{x}_{1},\dots,\mathbf{x}_{n}\\}$, the MLP part outputs a
set of $d$-dimensional vectors
$\mathbf{Q}=\\{\mathbf{q}_{1},\dots,\mathbf{q}_{n}\\}$ and
$\mathbf{K}=\\{\mathbf{k}_{1},\dots,\mathbf{k}_{n}\\}$ where $\mathbf{q}_{i}$
and $\mathbf{k}_{i}$ are the query and key vectors for object $o_{i}$,
respectively. Unlike the original self-attention layer, we do not define value
vectors as we are interested in the attention values. The second important
difference is the computation of the attention values:

$\alpha_{ij}=\text{GumbelSigmoid}(\mathbf{q}_{i}\cdot\mathbf{k}_{j})$ (1)

Firstly, using the sigmoid function instead of softmax allows attention values
to focus on multiple tokens independently. Secondly, the binarization (due to
GS) of attention values allows us to treat them as binary relations between
objects while preserving differentiability.

We define the output of the whole block as a relational predicate
$\sigma_{\text{r}}(\mathbf{x}_{i},\mathbf{x}_{j})$ that encodes the relation
between objects $o_{i}$ and $o_{j}$. Note that the order of arguments is
important since $\mathbf{q}_{i}\cdot\mathbf{k}_{j}$ and
$\mathbf{q}_{j}\cdot\mathbf{k}_{i}$ can have different values. Note that,
without loss of generality, we described the operation with a single attention
head; however, in the implementation, we used three attention heads.

####  III-B3 Aggregation Function

fuses unary predicates $\sigma_{\text{p}}(\mathbf{x}_{i})$, relational
predicates $\sigma_{\text{r}}(\mathbf{x}_{i},\mathbf{x}_{j})$, and the action
vector $\mathbf{a}$ in a single representation $\mathbf{h}_{i}$ for each
object that is fed into the decoder network for predicting the effect of the
executed action. The aggregation function is defined as follows:

$\displaystyle\mathbf{z}_{i}$
$\displaystyle=\text{MLP}([\sigma_{\text{p}}(\mathbf{x}_{i});\mathbf{a}])$
$\displaystyle\forall i\in\\{1,\dots,n\\}$ (2)
$\displaystyle\mathbf{h}_{i}^{k}$
$\displaystyle=\sum_{j=1}^{n}\sigma_{\text{r}_{k}}(\mathbf{x}_{i},\mathbf{x}_{j})\mathbf{z}_{i}$
$\displaystyle\forall i\in\\{1,\dots,n\\}$ (3) $\displaystyle\forall
k\in\\{1,\dots,K\\}$ (4) $\displaystyle\mathbf{h}_{i}$
$\displaystyle=[\mathbf{h}_{i}^{1};\dots;\mathbf{h}_{i}^{K}]$ (5)

where $K$ is the number of relation types. The action vector $\mathbf{a}$ is
concatenated with the unary predicate $\sigma_{\text{p}}(\mathbf{x}_{i})$, and
then fed into an MLP to obtain a representation $\mathbf{z}_{i}$ that holds
action information. Then, for each relation $k$ and object $i$, intermediate
representations $\mathbf{z}_{j}$ are summed up for indices that satisfy the
relation $\sigma_{\text{r}_{k}}(\mathbf{x}_{i},\mathbf{x}_{j})$, resulting in
a fixed-size vector $\mathbf{h}_{i}^{k}$ containing information regarding
objects that have a relation $r_{k}$ with object $o_{i}$. Lastly,
$\\{h_{i}^{1},\dots,h_{i}^{k}\\}$ are concatenated to obtain the aggregated
representation $\mathbf{h}_{i}$ that can hold any necessary information about
the object $o_{i}$, the action $\mathbf{a}$, and the relations between $o_{i}$
and other objects. Equation 3 essentially enables message passing between
different object symbols based on the learned relations between objects.

####  III-B4 Decoder Network

$g$ is an MLP that takes the aggregated representation $\mathbf{h}_{i}$ as
input and outputs the effect $\hat{\mathbf{e}}_{i}$ of action $\mathbf{a}$ on
the object $o_{i}$. The predicted effect is used to compute the mean squared
error that is backpropagated through the whole network:

$\mathcal{L}=\sum_{i=1}^{n}\lVert\hat{\mathbf{e}}_{i}-\mathbf{e}_{i}\rVert^{2}$
(6)

where $n$ is the number of objects and the effect vector $\mathbf{e}_{i}$ is
defined as the difference between the current state $\mathbf{x}_{i}$ and the
next state $\mathbf{x}_{i}^{\prime}$.

These four blocks create a single differentiable module that can learn unary
and relational predicate symbols over object features to minimize the effect
prediction error in an end-to-end fashion. To train the network, we execute
random actions in the environment and collect a dataset of
$(\mathbf{X},\mathbf{a},\mathbf{X}^{\prime})$ tuples. Then, we train the
network to minimize the effect prediction error $\mathcal{L}$ defined in
Equation 6.

###  III-C Learning Operators

In this section, we describe how to learn operators that can be used for
planning. Throughout this section, we will denote a ground symbol as
$\sigma_{p}{(\mathbf{x}_{i})}$, a lifted symbol as $\sigma_{p}(?x)$, and a
substitution as $\theta=\\{?x/\mathbf{x}_{i}\\}$ where $?x$ indicates a free
variable that is not bound to any object.

After we train the network, we can transform the dataset
$\\{(\mathbf{X}^{(i)},\mathbf{a}^{(i)},\mathbf{X^{\prime}}^{(i)})\\}_{i=1}^{N}$
into a dataset of propositional symbols
$\\{(\Sigma_{p}^{(i)},\Sigma_{r}^{(i)},\mathbf{a}^{(i)},\Sigma_{p}^{\prime(i)},\Sigma_{r}^{\prime(i)})\\}_{i=1}^{N}$
where

$\displaystyle\Sigma_{p}^{(i)}$
$\displaystyle=\\{\sigma_{p}(\mathbf{x}_{1}^{(i)}),\dots,\sigma_{p}(\mathbf{x}_{n}^{(i)})\\}$
$\displaystyle\Sigma_{r}^{(i)}$
$\displaystyle=\\{\sigma_{r}(\mathbf{x}_{1},\mathbf{x}_{1}),\dots,\sigma_{r}(\mathbf{x}_{i},\mathbf{x}_{j}),\dots,\sigma_{r}(\mathbf{x}_{n},\mathbf{x}_{n})\\}$

and $\Sigma_{p}^{\prime(i)}$, $\Sigma_{r}^{\prime(i)}$ are defined similarly.
For notational simplicity, we consider only a single relation type
$\sigma_{r}$ while the same procedure can be applied to multiple relation
types.

Our main goal is to find a set of operators
$\Phi=\\{\phi_{1},\dots,\phi_{m}\\}$ parameterized by lifted actions $\alpha$
that are in the following form:

$\phi_{i}(\Sigma_{p},\Sigma_{r};\alpha_{i})=(\Sigma_{p}^{\prime},\Sigma_{r}^{\prime})$
(7)

modeling the symbolic transition between states. We start by partitioning
samples by their actions $\mathbf{a}^{(i)}$ and preconditions
$\Sigma_{p}^{(i)}$, $\Sigma_{r}^{(i)}$: samples are grouped if their lifted
actions and preconditions can be represented by the same substitution
$\theta$. For example, consider the following samples:

$\displaystyle\Sigma_{p}^{(1)}$
$\displaystyle=\\{\sigma_{p}(\mathbf{x}_{1})=0,\sigma_{p}(\mathbf{x}_{2})=0,\sigma_{p}(\mathbf{x}_{3})=1\\}$
$\displaystyle\mathbf{a}^{(1)}$ $\displaystyle=\text{pick-
place}(\mathbf{x}_{3},\mathbf{x}_{1})$ $\displaystyle\Sigma_{p}^{(2)}$
$\displaystyle=\\{\sigma_{p}(\mathbf{x}_{1})=0,\sigma_{p}(\mathbf{x}_{2})=1,\sigma_{p}(\mathbf{x}_{3})=0\\}$
$\displaystyle\mathbf{a}^{(1)}$ $\displaystyle=\text{pick-
place}(\mathbf{x}_{2},\mathbf{x}_{3})$

These samples can be grouped into the same category $C_{1}$ with substitutions
$\theta_{1}=\\{?a/\mathbf{x}_{3},?b/\mathbf{x}_{1},?c/\mathbf{x}_{2}\\}$ and
$\theta_{2}=\\{?a/\mathbf{x}_{2},?b/\mathbf{x}_{3},?c/\mathbf{x}_{1}\\}$. This
procedure gives us a set of groups $\\{C_{1},\dots,C_{k}\\}$ where each group
is defined by lifted preconditions and actions. Next, we compute the lifted
effects for each group:

$\displaystyle\mathcal{E}_{p}^{+}=\\{\sigma\mid\sigma\in\Sigma_{p}^{\prime(i)},\sigma\notin\Sigma_{p}^{(i)}\\}$
$\displaystyle\mathcal{E}_{p}^{-}=\\{\sigma\mid\sigma\in\Sigma_{p}^{(i)},\sigma\notin\Sigma_{p}^{\prime(i)}\\}$

Relational effects $\mathcal{E}_{r}^{+}$ and $\mathcal{E}_{r}^{-}$ are
computed similarly. If lifted effects are not the same for all samples in a
group (i.e., a stochastic environment setting), we select the most frequent
lifted effect for each group. This completes our operator definition:

$\displaystyle\phi_{i}(\Sigma_{p},\Sigma_{r};\alpha_{i})$
$\displaystyle=(\Sigma_{p}^{\prime},\Sigma_{r}^{\prime})$
$\displaystyle\Sigma_{p}^{\prime}$
$\displaystyle=\Sigma_{p}\cup\mathcal{E}_{p}^{+}\setminus\mathcal{E}_{p}^{-}$
$\displaystyle\Sigma_{r}^{\prime}$
$\displaystyle=\Sigma_{r}\cup\mathcal{E}_{r}^{+}\setminus\mathcal{E}_{r}^{-}$

However, with this strategy, the number of groups increases with the number of
objects. On the other hand, most of the time, only a subset of precondition
symbols are relevant for a given action. For instance, if the action is to
pick and place an object on top of another, then precondition symbols of other
objects are irrelevant. Therefore, we only consider a subset of precondition
symbols relevant to the action. Although determining which symbols are
relevant is difficult to answer in a general sense, a practical and generally
valid heuristic is to consider topological neighborhood or contact relations.
In our experiments, we define this relevance as objects that are in the action
arguments and objects that are in contact with these argument objects. A
broader topological relevance alternative can also be to consider objects in
the vicinity of action arguments.

###  III-D Translating Operators to PDDL

Figure 2: An example generated PDDL action schema. This action encodes pick-
place($?o1$, ‘center’, $?o0$, ‘right’) where $?o0$ and $?o1$ are free
variables. The action schema is the 20th most frequent action in the dataset,
with 736 occurrences out of 160K samples.

Each operator $\phi_{i}$ is translated into a PDDL action schema where
$\Sigma_{p}$ and $\Sigma_{r}$ are used as preconditions, $\mathcal{E}_{p}^{+}$
and $\mathcal{E}_{r}^{+}$ are used as effects, free variables that appear in
the precondition and/or action are used as parameters, and the action name is
defined by the action arguments. In the action schema, each
$\sigma_{p_{i}}(?x)$ appear as (p$i$ ?x) or (not_p$i$ ?x), depending on the
value of the predicate. We filter out action schemas that are used less than a
threshold, which we set to 50 in our experiments. An example action schema is
shown in Figure 2. We observed that the most frequently used action schemas
are empty actions, such as picking a short cube from the left, which results
in no effect. This is due to the exploration process where we execute random
actions in the environment that frequently result in no effect. Even though
these definitions would not help in the planning process, we choose to keep
them as they can be used in later exploration stages to avoid actions that do
not have any effect and, thus, are not interesting for the agent.

##  IV EXPERIMENTS

###  IV-A Experiment Setup

We conducted our experiments in a tabletop object stacking environment (see
top left in Figure 1). There are two object types: 5x5x5 sized short block and
5x25x5cm sized long block. An environment instance contains two to four
objects represented by pose and type. A UR10 robot arm has a single high-level
action with four discrete parameters: picking an object from the left, right,
or center of the object and releasing it on top of (or left of, right of)
another object.

We followed the data collection procedure in [13], where the robot executes
random actions in the environment. The difference is that we only record
objects that are either action arguments or in contact with them. These object
features $\\{\mathbf{x}_{i}\\}_{i=1}^{k}$ are used as the state vector. The
effect vector $\mathbf{e}_{i}$ for object $o_{i}$ is the difference between
the next state $\mathbf{x}_{i}^{\prime}$ and the current state
$\mathbf{x}_{i}$. We subtract the lateral movement of the arm from the effect
vector to remove the effect of the carry action. Otherwise, symbols need to
encode global position information of objects, which is not necessary for
planning since actions are already parameterized over objects. Note that state
vectors can also be selected as raw pixels as in [11, 12]. We collect 200K
samples and split them into 160K training, 20K validation, and 20K test
samples.

We compare our method with [11] and [12] in terms of effect prediction
accuracy, and with [12] for planning performance. The original DeepSym
formulation uses a fixed-sized vector to represent the environment’s state,
making it hard for us to compare the performance of the two methods. However,
the comparison with [12] already serves as a valuable measure to assess
whether explicitly learning relational symbols helps the planning performance.

We train all methods for 4000 epochs with a batch size of 128 and a learning
rate of 0.0001 using Adam optimizer [28]. MLP blocks consist of two layers
with 128 hidden units. In Relational DeepSym (ours), we set the number of
relation types to three and the object symbol dimension to one (i.e., the
encoder’s output dimensionality). However, for other baselines, we set the
object symbol dimension to four since these methods need more representational
capacity to encode the state of the environment without relational symbols.
Also, the number of attention heads for the attentive formulation [12] is set
to four. Following [29], for layers before GS activation, we normalize both
the input and the weight vectors to have a norm of three. This prevents the
vanishing gradients in the GS function. Lastly, we clip gradients by their
norm to 10.

###  IV-B Effect Prediction Results

Figure 3: Effect prediction errors for different numbers of actions. TABLE I: Effect prediction results averaged over three runs. Units are in centimeters. DeepSym | Attentive | Relational
---|---|---
4.79 $\pm$ 0.12 | 4.47 $\pm$ 0.10 | 3.21 $\pm$ 0.30

We report the test set effect prediction results in Table I. Relational
DeepSym performs better than other methods by a small margin, which aligns
with the results in [13]. In Figure 3, we compare these methods by their
cumulative effect prediction error when predicting a sequence of actions by
feeding the prediction back into the state in an autoregressive fashion. Even
though we do not see a significant difference between different methods, this
does not directly translate to planning performance. Attentive DeepSym uses
transformer layers to pass information between object symbols, and there is no
straightforward way of translating the relational knowledge embedded in the
transformer weights into lifted operators. This is the key advantage of the
Relational DeepSym as it directly encodes relations symbols together with
object symbols.

(a) 2 objects

(b) 3 objects

(c) 4 objects

Figure 4: The planning performance for different numbers of objects over three
runs with 100 random problem pairs. Figure 5: Given an initial environment
configuration in the first column, our model can generate an action sequence
reaching the goal state.

Figure 6: Given an initial state (left) and a goal state (right), Relational
DeepSym can find a plan to achieve the goal even though it is only trained
with two to four objects.

###  IV-C Planning Performance

In this section, we compare the planning performance of Relational DeepSym
with the attentive formulation [12]. We generate a random set of problem pairs
$\\{(\mathbf{X}_{0}^{(i)},\mathbf{X}_{g}^{(i)})\\}_{i=1}^{N}$ by executing
random actions on the environment. For each problem pair, we convert
$\mathbf{X}_{0}$ and $\mathbf{X}_{g}$ into their symbolic counterparts
$\Sigma_{p_{0}}$, $\Sigma_{r_{0}}$ and $\Sigma_{p_{g}}$, $\Sigma_{r_{g}}$, and
produce PDDL problem statements. We filter out relations for object pairs that
are not in contact in the goal state; otherwise, the planner might fail to
find a plan due to spurious relations. We use the Fast Downward planning
system [6] and set a timeout limit to 10 seconds. We automatically check
whether a plan is correct by computing cartesian distances of objects from the
goal state and accept it as correct if the difference is less than 5cm for all
objects.

Figure 4 shows the planning performance for different numbers of objects and
actions. Planning with the domain defined over unary and relational symbols
generated by Relational DeepSym performs significantly better than the
implicit attentive version in which all relational information remains hidden
in the network’s weights. We also test our method in a real-world experiment
with the same environment definition (Figure 5). We detect the locations of
objects with an Intel Realsense depth camera by clustering pixels and
transform them into the robot frame. We manually define a goal configuration
with its corresponding contact graph. The rest of the algorithm works the same
as in simulation experiments.

Another advantage of using relational symbols in addition to unary symbols is
that we can represent an environment configuration that has many more objects
than the ones in the training set since the number of objects does not affect
the encoded representation. This is not the case for the attentive formulation
[12] as the model is biased towards the number of tokens in the training set,
similar to other transformer-based architectures. In Figure 6, we initialize
the scene with eight objects and create a goal configuration that was not in
the train set. The planner successfully finds an action sequence that reaches
the goal state.

##  V DISCUSSION

In our experiments, we define _relevance_ as objects that are in the action
arguments and objects that are in contact with these argument objects. An
alternative relevance might be to consider objects in the vicinity of action
arguments. Although this creates a limitation, most of our daily activities
can be represented with this relevance. An example exception is controlling a
race car with a joystick; learning the relevance between such objects should
be treated as a separate problem.

##  VI CONCLUSION

In this study, we proposed and implemented a framework where object and
relational predicates are discovered from the continuous sensory experience of
the robot, symbolic rules that encode the transition dynamics that involve
pick and place actions on arbitrary numbered compound objects are extracted,
these rules are automatically transferred to PDDL and symbolic plans are
generated and executed to achieve various goals. We showed that the planning
performance of our framework significantly outperforms the baselines. The key
factor for the performance increase is representing the environment with
relational symbols in addition to object symbols. In future work, we plan to
use the learned operators to search for novel states and effects, which would
drastically increase the sample efficiency and thus, the learning progress.

## ACKNOWLEDGMENT

This research was supported by TUBITAK (The Scientific and Technological
Research Council of Turkey) ARDEB 1001 program (project number: 120E274).
Additional support was given by the Grant-in-Aid for Scientific Research
(project no 22H03670), the project JPNP16007 commissioned by the New Energy
and Industrial Technology Development Organization (NEDO), JST, CREST
(JPMJCR17A4), and by INVERSE project (no. 101136067) funded by the European
Union.

## References

  * [1] G. Konidaris, “On the necessity of abstraction,” _Current opinion in behavioral sciences_ , vol. 29, pp. 1–7, 2019.
  * [2] G. Konidaris, L. Kaelbling, and T. Lozano-Perez, “Constructing symbolic representations for high-level planning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 28, no. 1, 2014.
  * [3] G. Konidaris, L. P. Kaelbling, and T. Lozano-Perez, “From skills to symbols: Learning symbolic representations for abstract high-level planning,” _Journal of Artificial Intelligence Research_ , vol. 61, pp. 215–289, 2018.
  * [4] E. Ugur and J. Piater, “Bottom-up learning of object categories, action effects and logical rules: From continuous manipulative exploration to symbolic planning,” in _2015 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2015, pp. 2627–2633.
  * [5] C. Aeronautiques, A. Howe, C. Knoblock, I. D. McDermott, A. Ram, M. Veloso, D. Weld, D. W. SRI, A. Barrett, D. Christianson, _et al._ , “Pddl— the planning domain definition language,” _Technical Report, Tech. Rep._ , 1998.
  * [6] M. Helmert, “The fast downward planning system,” _Journal of Artificial Intelligence Research_ , vol. 26, pp. 191–246, 2006.
  * [7] J. Hoffmann, “Ff: The fast-forward planning system,” _AI magazine_ , vol. 22, no. 3, pp. 57–57, 2001.
  * [8] M. Asai and A. Fukunaga, “Classical planning in deep latent space: Bridging the subsymbolic-symbolic boundary,” in _Proceedings of the aaai conference on artificial intelligence_ , vol. 32, no. 1, 2018.
  * [9] M. Asai and C. Muise, “Learning neural-symbolic descriptive planning models via cube-space priors: The voyage home (to strips),” _arXiv preprint arXiv:2004.12850_ , 2020.
  * [10] M. Asai, H. Kajino, A. Fukunaga, and C. Muise, “Classical planning in deep latent space,” _Journal of Artificial Intelligence Research_ , vol. 74, pp. 1599–1686, 2022.
  * [11] A. Ahmetoglu, M. Y. Seker, J. Piater, E. Oztop, and E. Ugur, “Deepsym: Deep symbol generation and rule learning for planning from unsupervised robot interaction,” _Journal of Artificial Intelligence Research_ , vol. 75, pp. 709–745, 2022.
  * [12] A. Ahmetoglu, E. Oztop, and E. Ugur, “Learning multi-object symbols for manipulation with attentive deep effect predictors,” _arXiv preprint arXiv:2208.01021_ , 2022.
  * [13] A. Ahmetoglu, B. Celik, E. Oztop, and E. Ugur, “Discovering predictive relational object symbols with symbolic attentive layers,” _arXiv preprint arXiv:2309.00889_ , 2023.
  * [14] E. Ugur, E. Şahin, and E. Oztop, “Unsupervised learning of object affordances for planning in a mobile manipulation platform,” in _2011 IEEE International Conference on Robotics and Automation_. IEEE, 2011, pp. 4312–4317.
  * [15] P. Zech, S. Haller, S. R. Lakani, B. Ridge, E. Ugur, and J. Piater, “Computational models of affordance in robotics: a taxonomy and systematic classification,” _Adaptive Behavior_ , vol. 25, no. 5, pp. 235–271, 2017.
  * [16] T. Taniguchi, T. Nagai, T. Nakamura, N. Iwahashi, T. Ogata, and H. Asoh, “Symbol emergence in robotics: a survey,” _Advanced Robotics_ , vol. 30, no. 11-12, pp. 706–728, 2016.
  * [17] S. James, B. Rosman, and G. Konidaris, “Learning portable representations for high-level planning,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 4682–4691.
  * [18] E. Ugur and J. Piater, “Refining discovered symbols with multi-step interaction experience,” in _2015 IEEE-RAS 15th International Conference on Humanoid Robots (Humanoids)_. IEEE, 2015, pp. 1007–1012.
  * [19] S. James, B. Rosman, and G. Konidaris, “Autonomous learning of object-centric abstractions for high-level planning,” in _International Conference on Learning Representations_ , 2021.
  * [20] T. Silver, R. Chitnis, J. Tenenbaum, L. P. Kaelbling, and T. Lozano-Pérez, “Learning symbolic operators for task and motion planning,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 3182–3189.
  * [21] R. Chitnis, T. Silver, J. B. Tenenbaum, T. Lozano-Perez, and L. P. Kaelbling, “Learning neuro-symbolic relational transition models for bilevel planning,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2022, pp. 4166–4173.
  * [22] T. Silver, A. Athalye, J. B. Tenenbaum, T. Lozano-Perez, and L. P. Kaelbling, “Learning neuro-symbolic skills for bilevel planning,” in _Conference on Robot Learning (CoRL)_ , 2022.
  * [23] T. Silver, R. Chitnis, N. Kumar, W. McClinton, T. Lozano-Pérez, L. Kaelbling, and J. B. Tenenbaum, “Predicate invention for bilevel planning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 37, no. 10, 2023, pp. 12 120–12 129.
  * [24] J. Achterhold, M. Krimmel, and J. Stueckler, “Learning temporally extended skills in continuous domains as symbolic actions for planning,” in _Conference on Robot Learning_. PMLR, 2023, pp. 225–236.
  * [25] N. Kumar, W. McClinton, R. Chitnis, T. Silver, T. Lozano-Pérez, and L. P. Kaelbling, “Learning efficient abstract planning models that choose what to predict,” in _7th Annual Conference on Robot Learning_ , 2023.
  * [26] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [27] C. J. Maddison, A. Mnih, and Y. W. Teh, “The concrete distribution: A continuous relaxation of discrete random variables,” _arXiv preprint arXiv:1611.00712_ , 2016.
  * [28] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [29] T. Salimans and D. P. Kingma, “Weight normalization: A simple reparameterization to accelerate training of deep neural networks,” _Advances in neural information processing systems_ , vol. 29, 2016.


# MAPEL: Multi-Agent Pursuer-Evader Learning using Situation Report

Sagar Verma  CVN, CentraleSupélec, Université Paris-Saclay
<EMAIL_ADDRESS>Richa Verma  TCS Innovation Lab
<EMAIL_ADDRESS>P.B. Sujit  IIIT Delhi
<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider a territory guarding game involving pursuers,
evaders and a target in an environment that contains obstacles. The goal of
the evaders is to capture the target, while that of the pursuers is to capture
the evaders before they reach the target. All the agents have limited sensing
range and can only detect each other when they are in their observation space.
We focus on the challenge of effective cooperation between agents of a team.
Finding exact solutions for such multi-agent systems is difficult because of
the inherent complexity. We present Multi-Agent Pursuer-Evader Learning
(MAPEL), a class of algorithms that use spatio-temporal graph representation
to learn structured cooperation. The key concept is that the learning takes
place in a decentralized manner and agents use situation report updates to
learn about the whole environment from each others’ partial observations. We
use Recurrent Neural Networks (RNNs) to parameterize the spatio-temporal
graph. An agent in MAPEL only updates all the other agents if an opponent or
the target is inside its observation space by using situation report. We
present two methods for cooperation via situation report update: a) Peer-to-
Peer Situation Report (P2PSR) and b) Ring Situation Report (RSR). We present a
detailed analysis of how these two cooperation methods perform when the number
of agents in the game are increased. We provide empirical results to show how
agents cooperate under these two methods.

###### Index Terms:

multi-agent learning; deep reinforcement learning; recurrent neural network

##  I Introduction

[5pt](a) Game snapshot [5pt](b) Scene description
[5pt](c) Proposed method

Figure 1: Top-left image shows the rendering of our multi-agent pursuer-evader
game. Top-right image shows the labelled description of the game environment.
Bottom image shows the proposed cooperation method.

Multi-agent systems have received much attention in the past decade [1, 2, 3,
4]. In such systems, agents share a common environment, where they act
independently or in cooperation with each other to achieve a combined goal. We
focus on the problem where multiple agents achieve a single task in
cooperation with each other. In such problems, the agents must have the
ability to handle unknown and uncertain scenarios and take the success of the
whole team into account.

A multi-agent pursuit-evasion game complexity depends on many variables like
the type of environment, the observation of the agents, their actions,
cooperation strategy, and the reward structure. Being complex and dynamic,
pursuit-evasion problems are challenging to solve [5]. Such complexities have
been addressed by stochastic modeling of agents motion in [6, 7]. There has
been growing interest in modeling the game, in which the evader is intelligent
and has certain sensing capabilities [8]. This paper focuses on the problem of
partial observation of agents where structured message passing is used for
cooperation.

We present a zero-sum game based on pursuit and evasion between two teams of
equal number agents. Since either the pursuer or the evader wins the game,
therefore, the game can be represented as a zero-sum game. The multi-agent
pursuit-evasion problem is shown in Figure 1. We assume partial observability
of the environment to ensure that the solution is usable in many real-world
applications that closely correspond to the task in hand. However, learning
becomes more difficult under partial observation along with complex
interactions between agents and the environment. Each agent perceives the
environment locally and even though the effect of other agents’ actions on the
environment is visible but the agents, themselves, are not. Reinforcement
learning (RL) has been used to solve multi-agent pursuit-evasion in [9, 10,
11, 1]. Recent works like [12, 13, 14, 15] use deep reinforcement learning for
different multi-agent problems where centralized policy learning is employed.
All these works deal with full observation and are not suitable for our
problem. We propose MAPEL, a class of deep reinforcement learning based
methods that uses spatio-temporal graphs for structured cooperation between
agents under partial observation.

To solve our multi-agent pursuit-evasion game, we present MAPEL which uses
spatio-temporal graphs to structure the cooperation between agents in a team.
We propose using abstract messages called situation reports which are shared
among agents for cooperation. We present two different methods for situation
report update which are based on dense and sparse communication. MAPEL can
handle pursuers and evaders which move at the same speed throughout the game,
which means that neither pursuers nor evaders have an advantage over each
other. We show that MAPEL cooperation methods lead to a high degree of
cooperation between agents. We also show how the two cooperation methods
perform when the number of agents in the team is increased.

The remainder of this paper is organized as follows. Section 2 mentions the
existing works related to this paper. Section 3 describes the problem and its
formulation as a multi-agent reinforcement learning (MARL) problem. Section 4
presents MAPEL and other proposed baselines. Section 5 explains the
experimental setup followed by the results and their explanation in section 6.
Section 7 concludes this paper.

##  II Related Work

Reinforcement learning has been successfully used to play games like Atari
[16] and Go [17]. In [18], the authors suggest an approach based on
hierarchical RL for the same, while enabling the players to learn through
tasks with less complexity. Multi-agent reinforcement learning (MARL) consists
of a set of learning agents that share a common environment [19]. Learning in
such a framework is fundamentally difficult because of the interaction arising
between the agents and the environment and amongst themselves. Conventional
decentralized learning techniques like Q learning for each agent [20] assume
the other agents to be a part of the environment. Such methods don’t work in
multi-agent settings because the theoretical convergence guarantee no longer
holds and makes the learning unstable due to the fact that changes in the
policy of any agent will affect the policies of the other agents, as well
[21].

Joint action learning or centralized policy learning is one way to do multi-
agent reinforcement learning. [14] present a deep policy inference Q-network
that targets multi-agent systems composed of controllable agents. A
centralized policy for the controllable agent is learned from its raw
observations. [22] presents joint and independent policy learning methods. In
an independent policy learning method, the joint learned policy is transferred
to individual agents in an iterative manner. [23] discusses why centralized
policy learning fails in case of multi-agent setting and presents methods to
learn policy for heterogeneous agents as well as homogeneous agents. Sunehag
et al. [24] discuss the problem of "lazy agents" which is when some agents
remain inactive when a centralized policy learning is used. They present a
value-decomposition network which enables better reward sharing between agents
to solve the problem of inactive agents.

Decentralized learning requires effective cooperation between different
agents. [25] suggest learning with opponent-learning awareness method in which
each agent anticipates other agent’s policy. This method only works for
complete observation. [26] discusses the problem of experience replay in
multi-agent deep reinforcement learning (MA-DRL). They state that transitions
stored in experience replay memory (ERM) can become outdated because agents
update their policies in parallel. They apply leniency to MA-DRL by mapping
agents state-action pairs to decaying temperature values that control the
amount of leniency applied towards negative policy updates that are sampled
from the ERM. They also state that this help in better cooperation among
agents. [13] use actor-critic to learn policies for complex cooperation. [27]
uses centralized critic to estimate the Q-value, decentralized actors are used
to optimize agents’ policies, and counterfactual baselines are used to solve
multi-agent credit assignment problem. [28] presents co-evolution methods to
learn better coordination between agents. [29] present a method to solve
cooperation between agents that can act selfishly.

Some multi-agent problems can be explicitly described as graphs. [30] presents
cooperative reinforcement learning for multiple agents in StarCraft game. [31]
uses graph representation with reinforcement learning for coordination and
cooperation in multi-agent patrol task. Efficient state representation based
on the distance between agents and different game entities is used to reduce
the observation state complexity. [32] presents a flag coordination game where
graph structure is explicitly present and is utilized to model multi-agent
coordination. Some problems where there are no explicit graph structures
present, game states can be decomposed into some weak time-varying structures.
Such structures can be learned using factor graph representation and graphical
learning methods. [33] discusses use cases where cooperation is explicitly
required. A genetic algorithm variation is used to solve the adaptive team of
agents (ATA) problem. Their method can adapt an agent to a new role based on
the overall structure of the environment. [34] presents joint policy learning
method for coordinated reinforcement learning through structured communication
between agents. [35] presents a way to decompose a global Q-function into
local Q-function based on the task decomposition between agents expressed
using factor graphs. [36] divide agents into cliques based on specific tasks.
[37] uses factor graphs to learn implicit structures present in multi-agent
settings. Factor graphs reduce the action and observation space and learning
agents’ policy becomes easier.

In the literature, RL has been used earlier for the classic pursuer-evader
game[38]. In [39], a learning technique for multi-player pursuit-evasion games
is presented for discrete state and action spaces. The proposed algorithm is
only applicable for multi-player pursuit-evasion games with superior pursuers
(in terms of speed). The article [40] is another work suggesting a technique
using learning in differential multi-player pursuit-evasion games that have
superior evaders. In [41] hierarchical decomposition is used to solve games
having two pursuers and one evader.

##  III Problem Definition

We model the multi-agent pursuer-evader problem as a grid world of dimension
$M\times N$ in which obstacles are placed randomly (uniform distribution
$\mathcal{N}(0,\sigma)$). In this grid, there are $P$ pursuers, $E$ evaders,
and a single target $T$. At any time $t$, a pursuer $p\in P$ has the global
knowledge about all pursuer locations and the current target location in the
environment. An evader $e\in E$ is assumed to know the locations of all other
evaders and the target. We assume each agent can sense a rectangular region of
length $l$ and width $w$. However, the agents cannot sense on the other side
of the obstacle. That is, a pursuer can detect an evader if they are in line-
of-sight and within the sensed region. The speed of all the pursuers and the
evaders is given by $v$ and remains constant throughout the game. The target,
$T$ remains stationary throughout the game.

A game starts with randomly sized obstacles placed on the grid at random
locations as shown in Figure 1 (for a 2-pursuers vs 2-evaders game). The
target is spawned at a random location near the middle of the grid ($M/2,N/2$)
and it is of length $t_{s}$. The pursuers and the evaders are randomly spawned
on the opposite sides of the grid. The pursuers and the evaders can move to
any of the adjacent cells of the grid only if the cell is either empty or
occupied by any of the agents. An agent reaches the target when its location
is same as the target’s location. Also, a pursuer captures an evader only if
their locations are the same. Once an evader is captured by a pursuer, it
cannot move anywhere else but the pursuer can move to an adjacent cell after
catching the evader.

There are three conditions for a game to complete.

  1. 1.

An evader reaches the target, in which case the evaders win the game.

  2. 2.

A pursuer reaches the target before an evader, in which case the pursuers win
the game.

  3. 3.

All the evaders are captured by the pursuers, in which case the pursuers win
the game.

Based on the three different winning criteria we have the following reward
structure:

  1. 1.

When the evaders win by capturing the target, a reward of $w^{e}=0.5$ is
awarded to them and a penalty of $w^{p}=-0.5$ is given to the pursuers.

  2. 2.

When the pursuers win by reaching the target before the evaders, a reward of
$w^{p}=0.5$ is awarded to, and a penalty of $w^{e}=-0.5$ is given to the
evaders.

  3. 3.

When the pursuers win by capturing all the evaders, a reward of $w^{p}=1$ is
awarded to the pursuers and a penalty of $w^{e}=-1$ is given to the pursuers.

Rewards are equally divided among all the agents of a team. This makes it sure
that agents in a team do not compete with each other.

##  IV Methods

In this section we first present a naive method in which an agent greedily
moves towards the target, followed by the second method which is a multi-agent
formulation of deep Q-learning and then we introduce the proposed method MAPEL
with two different cooperation strategies.

###  IV-A Naive Method

A naive agent tries to move towards the target, $T$. Each agent has a partial
view of the environment and knows the location of the other agents of its
team. It also knows the location of the target. A naive agent moves towards
the target in a straight line. If the next location on the line of sight
towards the target is obstructed, it randomly chooses an adjacent location
that is closest to the line. If a pursuer observes an evader in its
observation space, it computes the shortest path to the evader and chooses its
next location along that path. Similarly, if a pursuer/evader observes the
target in its observation space, it computes the shortest path to the target
and chooses its next location along that path. Also, if a pursuer observes the
target and an evader or multiple evaders in its field of view, it computes the
shortest paths to all of them and chooses its next location along the path
that has the smallest length.

###  IV-B Multi-agent Q-learning

Figure 2: Generalized architecture of MAPEL.

An $N$-agent stochastic game $\mathcal{E}$ is formalized by the tuple
$\mathcal{E}=(\mathcal{S},\mathcal{A}^{1},\dots,\mathcal{A}^{N},\mathcal{R}^{1},\dots,\mathcal{R}^{N},\mathcal{T},\gamma)$,
where $\mathcal{S}$ denotes the state space, and $\mathcal{A}^{i}$ is the
action space of agent $j\epsilon\\{1,\dots,N\\}$. The reward function for
agent $j$ is defined as
$\mathcal{R}^{i}:\mathcal{S}\times\mathcal{A}^{1}\times\dots\times\mathcal{A}^{N}\rightarrow\mathbb{R}$,
determining the immediate reward. The transition probability is given by
$\mathcal{T}:\mathcal{S}\times\mathcal{A}^{1}\times\dots\mathcal{A}^{N}\rightarrow
Pr(\mathcal{S})$. $Pr(\mathcal{S})$ is the collection of probability
distributions over the state space $\mathcal{S}$. The goal of agents is to
find a policy $\pi$ which maximizes the expected return $G_{t}$, which is the
discounted sum of rewards given by
$G_{t}=\sum_{i=1}^{N}\sum_{\tau=t}^{T}\gamma^{\tau-t}\mathcal{R}^{i}_{\tau}$,
where $T$ is the time-step when an episode ends, $t$ denotes the current time-
step, $\gamma\epsilon[0,1)$ represents the reward discount factor, and
$\mathcal{R}^{i}_{\tau}$ is the reward received at time-step $\tau$ by agent
$\mathcal{A}^{i}$.

The agents choose actions according to their policies. For agent $i$, the
corresponding policy is defined as $\pi^{i}:\mathcal{S}\rightarrow
Pr(\mathcal{A}^{i})$, where $Pr(\mathcal{A}^{i})$ is the collection of
probability distributions over agent $i$’s action space $\mathcal{A}^{i}$. The
joint policy of all the agents is given by
$\pi:\pi^{1}\times,\dots\times\pi^{N}$. The joint actions of all the agents is
given by $a:\mathcal{A}^{1}\times,\dots,\times\mathcal{A}^{N}$. The value
function of agent $i$ given state $s$ under the joint policy $\pi$ is written
as the expected cumulative discounted future reward:

$v^{i}_{\pi}(s)=v^{i}(s;\pi)=\sum_{t=0}^{\infty}\gamma^{t}\mathbb{E}_{\pi,p}\big{[}r^{i}_{t}|s_{0}=s,\pi\big{]}$
(1)

The $Q$-function can then be defined within the framework of $N$-agent game
based on the Bellman equation given the value function in equation (1) such
that the $Q$-function
$Q^{i}_{\pi}:\mathcal{S}\times\mathcal{A}^{1}\times,\dots,\mathcal{A}^{N}\rightarrow\mathbb{R}$
of agent $i$ under the joint policy $\pi$ can be formulated as

$Q^{i}_{\pi}=R^{i}(s,a)+\gamma\mathbb{E}_{s^{\prime}-p}\big{[}v^{i}_{\pi}(s^{\prime})\big{]},$
(2)

where $s^{\prime}$ is the state at the next time step. The value function
$v^{i}_{\pi}$ can be expressed in terms of the $Q$-function in equation (2) as

$v^{i}_{\pi}=\mathbb{E}_{a\leavevmode\nobreak\ \pi}\big{[}Q^{j}_{\pi}(s,a)].$
(3)

The $\mathcal{Q}$-function for $N$-agent game in equation (2) extends the
formulation for a single-agent game by considering the joint action taken by
all agents $a$, and by taking the expectation over the joint action in
equation (3).

###  IV-C Multi-Agent Pursuer-Evader Learning (MAPEL)

In the Q-learning method presented in the previous section, the joint policy
$\pi$ is dependent only on the current observation of all the agents combined.
It is impossible for an agent to know anything about the observation of the
other agents in that setting. Also, the size of the combined observation and
action spaces increases exponentially with the number of agents. For a large
number of agents, this could be problematic.

In this section, we present a spatio-temporal (st) architecture called MAPEL
which allows agents to learn their individual policies by sharing their
observations with each other by cooperating via situation reports. We
represent a team of agents as an st-graph
$\mathcal{G}=(\mathcal{N},\mathcal{E}_{M},\mathcal{E}_{T})$, where
$\mathcal{N}$ denotes the total number of agents, $\mathcal{E}_{M}$ is the
total number of edges between the agents i.e. the edges used to pass situation
reports, and $\mathcal{E}_{T}$ is the number of edges connecting agents at
time $T$. Figure 3 shows an example st-graph capturing agent-agent
interactions during a game. In the unrolled st-graph, two agents at a given
time step $t$ are connected with an undirected spatio-temporal edge
$e=(a_{i},a_{j})\epsilon\mathcal{E}_{M}$, and two nodes at adjacent time steps
are connected with an undirected temporal edge iff
$(a_{i},a_{j})\epsilon\mathcal{E}_{T}$.

We parameterize the nodes $\mathcal{N}$ and edges $\mathcal{E}_{T}$ using RNNs
in our st-graph. The edges $\mathcal{E}_{M}$ are used by nodes to pass
situation reports to each other. The situation reports are used by agents to
compute their actions at time $t$. The network architecture of MAPEL is
illustrated in figure 2, each agent is represented by an RNN, the agents
compute their observational features using a CNN and pass their own
observations to other agents via situation reports. Each agent uses the
situation reports received by other agents along with its current observation
to compute its next action. RNN maintains history information about an agent.
The situation report coupled with RNN is used to handle partial observability.
Situation report provides an abstract and clear representation of the
observation. This helps in reducing the hidden state representation noise
which arises due to other agents changing their strategies. For example, if a
pursuer observes the target or an evader, it can inform other pursuers about
its observation via situation report. This could help the other pursuers in
changing their decision to not go in the direction of this particular pursuer
and search in other areas for the target or other evaders.

In real-world applications, we can have hundreds of agents and interaction
among all of them may not be possible due to some physical constraints or
simply because of high computational complexity. In most of the cases, it is
not necessary to have dense communication between all the agents. Sparse
communication structures can be used to learn effective cooperation. We
present two situation report update methods that use the structures present in
the game.

#### Peer-to-Peer Situation Report (P2PSR)

In Peer-to-Peer Situation Report method, all the agents can share situation
report with each other. This is the case of dense communication. This means
that in our st-graph representation for $\mathcal{N}$ nodes, we have
$\mathcal{E}_{M}=\mathcal{N}(\mathcal{N}-1)/2$ edges. Figure 3 shows the st-
graph representation of P2PSR. This type of cooperation is required when an
agent wants to know what other agents are observing so that it does not
explore their regions. The objective of the agents then becomes to minimize
the search time and exploration area to complete the task.

[6pt](a) Spatio-temporal representation
[6pt](b) P2PSR [6pt](c) RSR

Figure 3: Spatio-temporal representation used for cooperation between agents.
Top image shows cooperation between three agents using spatio-temporal graph
unrolled in time. Bottom-left image shows peer-to-peer situation report method
between four agents and bottom-right image shows ring situation report method
between four agents.

#### Ring Situation Report (RSR)

In Ring Situation Report method, agents are randomly chosen to form a ring.
Each agent can only pass messages to its adjacent agents. The st-graph
representation for this type of cooperation is given by Figure 3. For
$\mathcal{N}$ nodes, we have $\mathcal{E}_{M}=\mathcal{N}$ edges for
$\mathcal{N}>2$. This type of cooperation can be used to cordon off an area
and search inside it. This does not require all the agents to know about the
other agents’ observations. An agent only needs to know what its adjacent
agents are observing. This decreases the number of messages required to
cooperate.

##  V Experimental Setup

[6pt](a) Evader1 observation [6pt](b) Evader2 observation
[6pt](c) Pursuer1 observation [6pt](d) Pursuer2 observation

Figure 4: Partial observation of individual agents in 2-pursuers vs 2-evaders
game. Each agent can see everything in its observation space and knows about
the target and other team members’ locations. An agent cannot see the
observation of its team members.

We perform our experiments on the multi-agent pursuer-evader environment
presented in section III. We begin with explaining the environment
representation, agent observation featurization, and representation of
messages under different situation report methods. All the experiments have
been conducted on a workstation with 1.2 GHz CPU, 256 GB RAM, NVIDIA V100 GPU
and running Ubuntu 18.04. We use PyTorch [42] for network implementation.

###  V-A Environment

The environment is a grid world composed of multiple grids of size $32\times
32$. Figure 4 shows partial observation of agent in a 2 vs 2 game. The white
regions are the empty regions where evaders and pursuers can move. An agent
considers all grid cells outside its observation space to be empty. Evaders
are blue, pursuers are green, and the target is red. Figure 4 (a) shows the
observation space of evader $1$, it can see all the grid cells in its
observation space, it knows the locations of other evaders and the target.
Similarly figure 4 (b) shows the observation space of evader $2$. Figure 4 (c)
shows the observation space of pursuer $1$, it can see all the grid cells in
its observation space, it knows the locations of other pursuers and the
target. Similarly, the observation space of pursuer $2$ is represented in
figure 4 (d).

###  V-B Agent Observation

For $Q$-learning, we need to represent an agent’s observation as meaningful
features. In our experiments, we found that raw RGB frames provide good
observational for 2 vs 2 games but fail to generalize for more number of
agents. We represent each type of entity in our environment as separate
channels. We have five channels in our feature space, each of size $32\times
32$. In the bottom left portion of figure 2, we show the featurization of
observation of one of the pursuers in a 4 vs 4 game. The first channel shows
the observation space of the agent, the second channel shows the position of
the agent itself, the third channel shows the position of other agents, the
fourth one shows the location of the target, and the fifth channel shows the
location of the opponent(s) observed. This feature representation accurately
incorporates all the information observed by an agent.

[6pt](a) 2 vs. 2, against naive pursuers [6pt](b) 3 vs. 3, against naive
pursuers [6pt](c) 5 vs. 5, against naive pursuers
[6pt](d) 2 vs. 2, against naive evaders [6pt](e) 3 vs. 3, against naive
evaders [6pt](f) 5 vs. 5, against naive evaders

Figure 5: Learning curve comparison of different methods in different
scenarios.

###  V-C Message Representation

In P2PSR, an agent $a_{i}$ receives a situation report $m^{t}_{i}$ in form of
a vector of size $\mathcal{N}-1$ at time $t$. The $\mathcal{N}-1$ elements of
the vector represent the messages from other agents, if the value of an
element in the vector is $1$, then it means the corresponding agent has seen
the target or opponent(s) in its observation space. An element with value $0$
means that the observation space is empty. In RSR, an agent $a_{i}$ receives a
situation report message $m^{t}_{i}$ in form of a vector with size $2$ from
two of its adjacent agents at time $t$.

###  V-D Training

We train multi-agent DQN for learning evaders against naive pursuers and
multi-agent DQN for learning pursuers against naive evaders. We train both
MAPEL cooperation methods against naive agents. All our models are trained for
400 epochs, 500 episodes per epoch. We use Adam [43] optimizer to train all
our models. Learning rate is varied over epochs, it starts with 0.001 and
decays at every 200 epochs by one-tenth. To ensure exploration,
$\epsilon$-greedy starts at 1.0 and ends at 0.1. A discount factor of 0.99 is
used. While training multi-agent DQN models, a history length of 5
observations is used. We use a batch size of 64 in all our experiments. We
vary the number of agents per team from 2 to 5 for all our models. Following
are the model variations that we train,

  1. 1.

MA-DQN pursuers against naive evaders.

  2. 2.

MA-DQN evaders against naive pursuers.

  3. 3.

MAPEL-P2PSR pursuers against naive evaders.

  4. 4.

MAPEL-P2PSR evaders against naive pursuers.

  5. 5.

MAPEL-RSR pursuers against naive evaders.

  6. 6.

MAPEL-RSR evaders against naive pursuers.

###  V-E Evaluation

| Naive | MA-DQN | MAPEL-P2PSR | MAPEL-RSR
---|---|---|---|---
Scenario | Average | Complete | Average | Complete | Average | Complete | Average | Complete
| reward | wins | reward | wins | reward | wins | reward | wins
2 vs. 2 | 0.159 | 9.77% | -0.274 | 3.13% | 0.431 | 14.62% | NA | NA
3 vs. 3 | 0.161 | 10.23% | -0.235 | 3.17% | 0.396 | 15.79% | NA | NA
4 vs. 4 | 0.162 | 10.07% | -0.217 | 2.92% | 0.479 | 16.71% | 0.456 | 15.92%
5 vs. 5 | 0.165 | 10.13% | -0.213 | 2.72% | 0.483 | 16.23% | 0.468 | 15.92%
Table I: Evaluation result of different methods for pursuers against naive evaders in different scenarios. Scenario | Naive | MA-DQN | MAPEL-P2PSR | MAPEL-RSR
---|---|---|---|---
2 vs. 2 | 0.134 | -0.279 | 0.419 | NA
3 vs. 3 | 0.153 | -0.247 | 0.429 | NA
4 vs. 4 | 0.157 | -0.225 | 0.423 | 0.416
5 vs. 5 | 0.161 | -0.217 | 0.417 | 0.419
Table II: Evaluation result of different methods for evaders against naive
pursuers in different scenarios.

We evaluate our MA-DQN, MAPEL-P2PSR, and MAPEL-RSR evaders against naive
pursuers and vice-versa. 100,000 episodes are used for all the evaluations.
Average reward is reported for both evaders and pursuers. In the case of
pursuers running different methods, we also report the total number of times
pursuers were able to capture all the evaders. We call these results as
"complete wins".

##  VI Results

Figure 5 compares different models’ learning curve under the different number
of agents for both evaders and pursuers. For the number of agents
$\mathcal{N}={1,2,3}$, both MAPEL cooperation methods, i.e., P2PSR and RSPRP
have the same message length. In such cases, there is no fundamental
difference between these methods. Therefore, we only train both methods when
team sizes are more than 3. Figure 5 (a) shows the learning curve for evaders
with MA-DQN and MAPEL-P2PSR when the number of agents is 2 for both evaders
and pursuers. Similarly figure 5 (b) is for a 3 vs. 3 scenario for evaders
against naive pursuers. Figure 5 (d) and (e) are for pursuers with MA-DQN and
MAPEL-P2PSR against naive evaders when the numbers of agents are 2 and 3
respectively. Figure 5 (c) and (f) show all three methods for evaders and
pursuers against their naive opponents when the number of agents is 5.

In all the scenarios, pursuers are able to score better rewards than evaders.
We believe that the pursuers are able to learn about the strategy where
capturing all the evaders maximizes their rewards. From figure 5 (c) and (f),
it is evident that MAPEL-P2PSR for pursuers learns about capturing all evaders
quickly as compared to MAPEL-RSR. After 350 epochs both the methods converge
to same average rewards which shows that MAPEL-RSR has similar learning
capabilities as MAPEL-P2PSR. We believe this is due to the fact that in the
case of MAPEL-P2PSR, all pursuers know about all other pursuers’ observations
explicitly which helps them in knowing about "capture all evaders" strategy
early. In the case of MAPEL-RSR, more epochs are required to learn about this
strategy.

Table I compares the average rewards and complete wins of different methods
for pursuers against naive evaders in four scenarios, i.e., 2 vs. 2, 3 vs. 3,
4 vs. 4, and 5 vs. 5. It can be seen that the naive method performs better
than MA-DQN in all the scenarios. On rendering a few episodes, we find that
MA-DQN pursuers are not able to find the shortest paths as compared to the
naive method. For some of the successful episodes, we find that pursuers are
able to beat the opponents when some of the team members are closer to the
target as compared to the evaders. In 4 vs 4 and 5 vs 5 scenarios, we can see
that MAPEL-P2PSR is ahead of MAPEL-RSR by 0.023 and 0.025 units of average
reward respectively. This is in line with our earlier hypothesis that
MAPEL-P2PSR is better at learning about "capture all evaders" strategy because
of dense communication. This is evident from the "complete wins" in column 7
and 9. The difference in the average reward is still less when compared to
difference in "complete wins" between the two methods.

Table II compares the average rewards and complete wins of different methods
for evaders against naive pursuers in four scenarios, i.e., 2 vs. 2, 3 vs. 3,
4 vs. 4, and 5 vs. 5. Similar to the case of evaders, the naive method
performs better than MA-DQN in all the scenarios. We also observe that the
rewards from MAPEL-P2PSR and MAPEL-RSR for evader are smaller than the
pursuers. The reason for this is that pursuers can learn about "capture all
evaders" strategy to get more reward whereas pursuers don’t have any such
strategy to maximize their rewards further. The reason MAPEL methods perform
better than naive and MA-DQN methods is that evaders can avoid the regions
where pursuers have been observed by some members of the team.

##  VII Conclusions and Future Work

In this paper, we presented a variation of multi-agent pursuit-evasion game
with partial observability. We also present MAPEL for multi-agent cooperative
reinforcement learning to solve the game. We compare proposed MAPEL with two
benchmarks; the naive method which is a greedy solution and a multi-agent DQN
formulation. We perform experiments with varying number of agents to show the
generalizability of the MAPEL cooperation methods. We empirically show that
MAPEL cooperation methods are better at learning cooperation strategy by
reporting the results of "capture all evaders" in the case of pursuers.

In the future, our goal would be to test the transfer-ability of MAPEL methods
to games with more number of agents. We would also like to experiment under
different game conditions like opponents with different speeds, non-equal team
sizes, moving target, etc. We would also like to find effective ways of
analyzing and comparing proposed cooperation methods.

## References

  * [1] J. Y. Kuo, H.-F. Yu, K. F.-R. Liu, and F.-W. Lee,  “Multiagent cooperative learning strategies for pursuit-evasion games,”  Mathematical Problesm in Engineering, 2015.
  * [2] H. He, J. Boyd-Graber, K. Kwok, and H. D. III,  “Opponent modeling in deep reinforcement learning,”  in Proceedings of The 33rd International Conference on Machine Learning, 2016, vol. 48, pp. 1804–1813.
  * [3] M. L. Littman,  “Markov games as a framework for multi-agent reinforcement learning,”  in Proceedings of the 11th International Conference on International Conference on Machine Learning, 1994, pp. 157–163.
  * [4] P. Mirowski, R. Pascanu, F. Viola, H. Soyer, A. J. Ballard, A. Banino, M. Denil, R. Goroshin, L. Sifre, K. Kavukcuoglu, D. Kumaran, and R. Hadsell,  “Learning to navigate in complex environments,”  CoRR, vol. abs/1611.03673, 2016.
  * [5] A. Antoniades, H. J. Kim, and S. Sastry,  “Pursuit-evasion strategies for teams of multiple agents with incomplete information,”  pp. 756–761, 2003.
  * [6] J. P. Hespanha, G. J. Pappas, and M. Prandini,  “Greedy control for hybrid pursuit-evasion games,”  2001\.
  * [7] L. J. Guibas, J.-C. Latombe, S. M. Lavalle, D. Lin, and R. Motwani,  “A visibility-based pursuit-evasion problem,”  International Journal of Computational Geometry & Applications, vol. 09, pp. 471–493, 1999.
  * [8] R. Vidal, O. Shakernia, H. J. Kim, D. H. Shim, and S. Sastry,  “Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation,”  IEEE Transactions on Robotics and Automation, vol. 18, no. 5, pp. 662–669, 2002.
  * [9] L. E. Parker,  “Distributed algorithms for multi-robot observation of multiple moving targets,”  Autonomous Robots, vol. 12, no. 3, pp. 231–255, May 2002.
  * [10] C. H. Yong and R. Miikkulainen,  “Coevolution of role-based cooperation in multiagent systems,”  IEEE Trans. on Auton. Ment. Dev., vol. 1, no. 3, pp. 170–186, Oct. 2009.
  * [11] A. T. Bilgin and E. Kadioglu-Urtis,  “An approach to multi-agent pursuit evasion games using reinforcement learning,”  in International Conference on Advanced Robotics, 2015, pp. 164–169.
  * [12] Q. Zhang, D. Zhao, and F. L. Lewis,  “Model-free reinforcement learning for fully cooperative multi-agent graphical games,”  in 2018 International Joint Conference on Neural Networks, 2018, pp. 1–6.
  * [13] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch,  “Multi-agent actor-critic for mixed cooperative-competitive environments,”  Neural Information Processing Systems, 2017.
  * [14] Z.-W. Hong, S.-Y. Su, T.-Y. Shann, Y.-H. Chang, and C.-Y. Lee,  “A deep policy inference q-network for multi-agent systems,”  in Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018, pp. 1388–1396.
  * [15] J. Z. Leibo, V. Zambaldi, M. Lanctot, J. Marecki, and T. Graepel,  “Multi-agent reinforcement learning in sequential social dilemmas,”  in Proceedings of the 16th International Conference on Autonomous Agents and MultiAgent Systems, 2017, pp. 464–473.
  * [16] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller,  “Playing atari with deep reinforcement learning,”  arXiv preprint arXiv:1312.5602, 2013.
  * [17] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al.,  “Mastering the game of go without human knowledge,”  Nature, vol. 550, no. 7676, pp. 354, 2017.
  * [18] J. Liu, S. Liu, H. Wu, and Y. Zhang,  “A pursuit-evasion algorithm based on hierarchical reinforcement learning,”  in International Conference on Measuring Technology and Mechatronics Automation, 2009, vol. 2, pp. 482–486.
  * [19] L. Busoniu, R. Babuska, and B. De Schutter,  “A comprehensive survey of multiagent reinforcement learning,”  IEEE Transactions on Systems, Man, And Cybernetics-Part C: Applications and Reviews, 2008.
  * [20] M. Tan,  “Multi-agent reinforcement learning: Independent vs. cooperative agents,”  in Proceedings of the tenth international conference on machine learning, 1993, pp. 330–337.
  * [21] L. Matignon, G. J. Laurent, and N. Le Fort-Piat,  “Independent reinforcement learners in cooperative markov games: a survey regarding coordination problems,”  The Knowledge Engineering Review, vol. 27, no. 1, pp. 1–31, 2012\.
  * [22] S. Omidshafiei, J. Pazis, C. Amato, J. P. How, and J. Vian,  “Deep decentralized multi-task multi-agent reinforcement learning under partial observability,”  2017\.
  * [23] J. K. Gupta, M. Egorov, and M. Kochenderfer,  “Cooperative multi-agent control using deep reinforcement learning,”  in Autonomous Agents and Multiagent Systems, 2017, pp. 66–83.
  * [24] P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, and T. Graepel,  “Value-decomposition networks for cooperative multi-agent learning based on team reward,”  in Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018, pp. 2085–2087.
  * [25] J. N. Foerster, R. Y. Chen, M. Al-Shedivat, S. Whiteson, P. Abbeel, and I. Mordatch,  “Learning with opponent-learning awareness,”  in Proceedings of the 17th Conference on Autonomous Agents and MultiAgent Systems, 2018, pp. 122–130.
  * [26] G. Palmer, K. Tuyls, D. Bloembergen, and R. Savani,  “Lenient multi-agent deep reinforcement learning,”  in Proceedings of the 17th Conference on Autonomous Agents and MultiAgent Systems, 2018, pp. 443–451.
  * [27] J. N. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson,  “Counterfactual multi-agent policy gradients,”  2018\.
  * [28] C. H. Yong and R. Miikkulainen,  “Cooperative coevolution of multi-agent systems,”  Tech. Rep., 2001.
  * [29] F. L. Pinheiro and F. P. Santos,  “Local wealth redistribution promotes cooperation in multiagent systems,”  in Proceedings of the 17th Conference on Autonomous Agents and MultiAgent Systems, 2018, pp. 786–794.
  * [30] K. Shao, Y. Zhu, and D. Zhao,  “Cooperative reinforcement learning for multiple units combat in starcraft,”  in 2017 IEEE Symposium Series on Computational Intelligence (SSCI), 2017, pp. 1–6.
  * [31] Z. Hu and D. Zhao,  “Reinforcement learning for multi-agent patrol policy,”  in 9th IEEE International Conference on Cognitive Informatics, 2010, pp. 530–535.
  * [32] D. K. Marzagão, N. Rivera, C. Cooper, P. McBurney, and K. Steinhöfel,  “Multi-agent flag coordination games,”  in Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017, pp. 1442–1450.
  * [33] B. D. Bryant and R. Miikkulainen,  A Neuroevolutionary Approach to Adaptive Multi-agent Teams, pp. 87–115,  2018\.
  * [34] C. Guestrin, M. G. Lagoudakis, and R. Parr,  “Coordinated reinforcement learning,”  in Proceedings of the Nineteenth International Conference on Machine Learning, 2002, pp. 227–234.
  * [35] Z. Zhang and D. Zhao,  “Clique-based cooperative multiagent reinforcement learning using factor graphs,”  Journal of Automatica Sinica, vol. 1, no. 3, pp. 248–256, 2014\.
  * [36] Z. Zhang and D. Zhao,  “Cooperative multiagent reinforcement learning using factor graphs,”  in 4th International Conference on Intelligent Control and Information Processing, 2013, pp. 797–802.
  * [37] C. Amato and F. A. Oliehoek,  “Scalable planning and learning for multiagent pomdps,”  in Proceedings of the 29th AAAI Conference on Artificial Intelligence, 2015, pp. 1995–2002.
  * [38] R. Isaacs,  Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization,  1999\.
  * [39] R. Liu et al.,  “A novel approach based on evolutionary game theoretic model for multi-player pursuit evasion,”  in International Conference on Computer, Mechatronics, Control and Electronic Engineering, 2010, vol. 1, pp. 107–110.
  * [40] H. Wang, Q. Yue, and J. Liu,  “Research on pursuit-evasion games with multiple heterogeneous pursuers and a high speed evader,”  in 27th Chinese Control and Decision Conference, 2015, pp. 4366–4370.
  * [41] A. Alexopoulos, T. Schmidt, and E. Badreddin,  “Cooperative pursue in pursuit-evasion games with unmanned aerial vehicles,”  in International Conference on Intelligent Robots and Systems, 2015, pp. 4538–4543.
  * [42] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer,  “Automatic differentiation in pytorch,”  in Neural Information Processing Systems Workshop, 2017.
  * [43] D. P. Kingma and J. Ba,  “Adam: A method for stochastic optimization,”  CoRR, vol. abs/1412.6980, 2014.