# A Task-Motion Planning Framework Using Iteratively Deepened AND/OR Graph
Networks

Hossein Karami, Antony Thomas1 and Fulvio Mastrogiovanni All the authors are
with the Department of Informatics, Bioengineering, Robotics, and Systems
Engineering, University of Genoa, Via Opera Pia 13, 16145, Genoa,
Italy.1Corresponding author’s email<EMAIL_ADDRESS>
###### Abstract

We present an approach for Task-Motion Planning (TMP) using Iterative Deepened
AND/OR Graph Networks (TMP-IDAN) that uses an AND/OR graph network based novel
abstraction for compactly representing the task-level states and actions.
While retrieving a target object from clutter, the number of object re-
arrangements required to grasp the target is not known ahead of time. To
address this challenge, in contrast to traditional AND/OR graph-based
planners, we grow the AND/OR graph online until the target grasp is feasible
and thereby obtain a network of AND/OR graphs. The AND/OR graph network allows
faster computations than traditional task planners. We validate our approach
and evaluate its capabilities using a Baxter robot and a state-of-the-art
robotics simulator in several challenging non-trivial cluttered table-top
scenarios. The experiments show that our approach is readily scalable to
increasing number of objects and different degrees of clutter.

##  I Introduction

Autonomous robots operating in the real-world are often faced with different
levels of reasoning while executing their tasks. For example, while
manipulating objects in clutter, a high-level reasoning is required to make
discrete decisions regarding which object to grasp or push. To execute these
decisions a robot has to reason in the continuous collision-free motion space.
Planning in these discrete-continuous spaces is referred to as Task-Motion
Planning (TMP) [17].

In the recent past, TMP has received considerable interest among the research
community [13, 22, 3, 7, 25, 9]. The primary challenge of planning in the
hybrid space is to obtain an efficient mapping between the discrete task and
continuous motion levels. The de facto standard syntax for task planning is
the Planning Domain Definition Language (PDDL) [19] and most approaches resort
to the same for task planning. Semantic attachments are used in [5, 4, 3, 25],
associating algorithms to functions and predicate symbols via external
procedures. Though semantic attachments allow mapping between the task and
motion space, the environment is assumed to be known before-hand. Besides, the
robot configuration, grasp poses need to be specified in advance and renders
the continuous motion space to be finite. This a priori discretization is
relaxed in [12, 22, 26, 7]. Yet, these approaches are domain specific in
nature. Moreover, most approaches (for example [6, 22, 3]) first compute a
task-level plan and refines it until a feasible motion plan is found or until
timeout. The approach in [25], however, checks for the motion feasibly as each
task-level action is expanded by the task planner. But this approach assumes a
pre-discretized motion space and thereby a finite action set. Recent work of
Caelan et al. [8] address this limitation by introducing streams within PDDL,
which enable procedures for sampling values of continuous variables and
thereby encoding an infinite set of actions.

Figure 1: Toy example in 2D; gripper needs to retrieve the red object from
clutter.

Though off-the-shelf PDDL planners are available, one needs additional
expertise to incorporate semantic attachments or streams that comply with the
state-space search of the planner. Let us consider a simple 2D pick and place
scenario111Also referred as cluttered table-top scenario in the paper. shown
in Fig. 1, where a gripper needs to retrieve a target object (red) from
clutter. As seen in the figure the target object is not immediately graspable
and other objects (blue) that hinder the target grasp need to be re-arranged.
This toy scenario may be modeled using two PDDL actions pick and place. Note
that for a TMP problem each discrete action should also realize appropriate
motions to achieve the desired tasks. For the PDDL domain file one may define
the following predicates:
(:predicates (clear ?x) (gripper-empty) (holding ?x))
To keep the scenario simple enough, we deliberately make the assumption that
if the target grasp is hindered, the robot is able to pick up another
object/objects to make the target pick action feasible. We note that PDDL
planners initiate the search through a process called grounding. Grounding is
used to replace the variables in the predicates with different objects so as
to instantiate predicates and action schemas. The predicates clear ?x,
gripper-empty, and holding ?x checks if the object is graspable, gripper arm
is empty, and if the gripper is holding the object. For 6 objects this gives
rise to 13 propositions and therefore $n=2^{13}$ states222Six possibilities
for each of the predicates clear ?x, holding ?x and one for gripper-empty.
Shortest-path found using a state-transition graph via the pick and place
actions would take $O(n\log n)$ time [1]. Clearly, heuristic search avoids
visiting large areas of the transition graph via informed search to arrive at
the goal faster. Furthermore, the number of objects that need to be re-
arranged is not known before-hand and this would require observation based re-
planning within the PDDL framework. This requires additional mapping between
the PDDL action space and the observation space of the robot. Moreover, the
time taken for each re-planning further exacerbates the time complexity issue.
Furthermore, PDDL planning is EXPSPACE-complete and can be restricted to less
compact propositional encodings to achieve PSPACE-completeness [11].

We present a probabilistically complete approach for TMP, specifically
focusing on re-arranging a cluttered table-top to retrieve a target object. We
tackle the two challenges described above, that is, (1) the number of objects
to be re-arranged may not be known in advance and (2) the computational
complexity of typical PDDL based planners. To address these challenges, we
encode the task-level abstractions of the TMP problem efficiently and
compactly within an AND/OR graph that grows iteratively until a solution is
found. However, in general an AND/OR graph needs to be constructed offline and
therefore it is required to know before-hand the number of objects to be re-
arranged. Since this is unknown and depends on the degree of clutter, we
introduce AND/OR graph networks that iteratively deepens during run-time till
the target is retrieved. In Section III we show that task-planning complexity
is almost linear with respect to the number of graph iterations and validate
the same in Section V.

The rest of the paper is organized as follows. Task-motion formalism are
introduced in Section II. We introduce AND/OR graph networks in Section III
and formalize our approach in Section IV. The results are presented in Section
V and Section VI concludes the paper.

##  II Task-Motion Formalism

Task planning or classical planning is the process of finding a discrete
sequence of actions from the current state to a desired goal state [10].

######  Definition 1.

A task domain $\Omega$ can be represented as a state transition system and is
a tuple $\Omega=\langle S,A,\gamma,s_{0},S_{g}\rangle$ where:

  * •

$S$ is a finite set of states;

  * •

$A$ is a finite set of actions;

  * •

$\gamma\mathrel{\mathop{\mathchar 58\relax}}S\times A\rightarrow S$ such that
$s^{\prime}=\gamma(s,a)$;

  * •

$s_{0}\in S$ is the start state;

  * •

$S_{g}\subseteq S$ is the set of goal states.

######  Definition 2.

The task plan for a task domain $\Omega$ is the sequence of actions
$a_{0},\ldots,a_{m}$ such that $s_{i+1}=\gamma(s_{i},a_{i})$, for
$i=0,\ldots,m$ and $s_{m+1}$ satisfies $S_{g}$.

Motion planning finds a sequence of collision free configurations from a given
start configuration to a desired goal [18].

######  Definition 3.

A motion planning domain is a tuple $M=\langle C,f,q_{0},G\rangle$ where:

  * •

$C$ is the configuration space;

  * •

$f=\\{0,1\\}$, for collision ($f=0$) else ($f=1$);

  * •

$q_{0}\in C$ is the initial configuration;

  * •

$G\in C$ is the set of goal configurations.

######  Definition 4.

A motion plan for $M$ finds a collision free trajectory in $C$ from $q_{0}$ to
$q_{n}\in G$ such that $f=1$ for $q_{0},...,q_{n}$. Alternatively, A motion
plan for $M$ is a function of the form $\tau\mathrel{\mathop{\mathchar
58\relax}}[0,1]\rightarrow C_{free}$ such that $\tau(0)=q_{0}$ and $\tau(1)\in
G$, where $C_{free}\subset C$ is the configurations where the robot does not
collide with other objects or itself.

TMP combines discrete task planning and continuous motion planning to
facilitate efficient interaction between the two domains. Below we define the
TMP problem formally.

######  Definition 5.

A task-motion planning with task domain $\Omega$ and motion planning domain
$M$ is a tuple $\Psi=\langle C,\Omega,\phi,\xi,q_{0}\rangle$ where:

  * •

$\phi\mathrel{\mathop{\mathchar 58\relax}}S\rightarrow 2^{C}$, maps states to
the configuration space;

  * •

$\xi\mathrel{\mathop{\mathchar 58\relax}}A\rightarrow 2^{C}$, maps actions to
motion plans.

######  Definition 6.

The TMP problem for the TMP domain $\Psi$ is to find a sequence of discrete
actions $a_{0},...,a_{n}$ such that $s_{i+1}=\gamma(s_{i},a_{i})$, $s_{n+1}\in
S_{g}$ and a corresponding sequence of motion plans $\tau_{0},...,\tau_{n}$
such that for $i=0,...,n$, it holds that (1) $\tau_{i}(0)\in\phi(s_{i})\
\textrm{and}\ \tau_{i}(1)\in\phi(s_{i+1})$, (2) $\tau_{i+1}(0)=\tau_{i}(1)$,
and (3) $\tau_{i}\in\xi(a_{i})$.

##  III AND/OR Graph Networks

An AND/OR graph is a graph which represents a problem-solving process [2].
Below we provide a brief overview of AND/OR graphs; a detailed exposition can
be found in [15].

######  Definition 7.

An AND/OR graph $G$ is a directed graph represented by the tuple $G=\langle
N,H\rangle$ where:

  * •

$N$ is a set of nodes;

  * •

$H$ is a set of hyper-arcs.

For a given AND/OR graph $G$, $H=\\{h_{1},\ldots,h_{m}\\}$, where $h_{i}$ is a
many-to-one mapping from a set of child nodes to a parent node. Let us revisit
the toy example considered in Section I (Fig. 1). An AND/OR graph for this
scenario is visualized as a sub-graph in Fig. 2 consisting of the nodes
graspable, gripper-empty, object picked, target placed and object placed. Note
that we currently ignore the current configuration node (green color) and the
graph extending from the object placed node in the figure, details of which
will be described later. Each node $n_{i}\in N$ of the graph $G$ represents a
high-level state, for example, object picked. To achieve the state object
picked, the gripper must be empty, that is gripper-empty and the object should
graspable. Thus the nodes graspable, gripper-empty and object picked are akin
to the PDDL predicates clear ?x, gripper-empty, and holding ?x, respectively.
The hyper-arc induces a mapping from the child nodes gripper-empty and
graspable to the parent node object picked. In that sense, a hyper-arc induces
a logical AND relationship between the child nodes/states, that is, all the
child states should be satisfied simultaneously to achieve the parent state.
Similarly, a single parent node can be the codomain for different hyper-arcs
$h_{i}$. These hyper-arcs are in logical OR with the parent node. Nodes
without any successors or children are called the terminal nodes. The terminal
nodes are either a success node, that is, target placed or a failure node,
that is, object placed.

Let us again consider the toy example in Fig. 1. If the number of objects to
be re-arranged are known, then an AND/OR graph can be constructed using the
the above mentioned states and corresponding transitions. Yet, the number of
object re-arrangements is scenario dependent and not known ahead of time. The
AND/OR graph representation thus seems incompatible. However, we make the
following observation— the abstractions defined for clutter scenario, that is,
the states (nodes of $G$) and actions (hyper-arcs of $G$) remain the same
irrespective of the number of object re-arrangements. Thus we can envision a
graph $G$ that expands online by repeating itself until the target is
retrieved. Nevertheless, each iteration of $G$ corresponds to a new work-space
configuration (object arrangement) and to encode this aspect we augment $G$
with a virtual node that represents the current work-space configuration.

######  Definition 8.

For an AND/OR graph $G=\langle N,H\rangle$, an augmented AND/OR graph $G^{a}$
is a directed graph represented by the tuple $G^{a}=\langle
N^{a},H^{a}\rangle$ where:

  * •

$N^{a}=\\{N,n^{v}\\}$ with $n_{v}$ being the virtual node;

  * •

$H^{a}=\\{H,H^{v}\\}$ with $H^{v}=\\{h^{v}_{i}\\}_{1\leq i\leq|H^{v}|}$.

The virtual node $n^{v}$ is called the root node of the augmented graph
$G^{a}$. Each virtual hyper-arc $h^{v}_{i}$ induces a mapping between the
virtual node and a node of the graph $G$. In our cluttered table-top scenario,
the most trivial case corresponds to successfully grasping the target without
any object re-arrangements. However, most often due to clutter, a motion plan
to the target do not exist and objects need to be re-arranged to obtain a
feasible plan. In general, motion planner failure can arise if a path indeed
does not exist or because the planning time allotted was insufficient. In this
work, we assume that sufficient time is allotted to the planner so that a
motion planning failure implies objects obstructing the path to the target.

######  Remark 1.

If the target grasp is unsuccessful, that is, the motion planner fails, then
at least one object need to be re-arranged to search for a new target-
graspable path.

Thus, following the root node, a success node is reached if the target placed
task is a achieved and hence the graph is solved. Else, the graph is
terminated at the failure node (object placed) following the re-arrangement of
a single object and the graph is therefore unsolved. In our approach a single
augmented AND/OR graph $G^{a}$ represents such a problem solving process. It
readily follows from Remark 1 that if the graph $G^{a}$ is terminated at the
failure node a re-attempt is to be made to achieve a grasp of the target
object. Such an attempt can again lead to a solved or unsolved graph.
Therefore to achieve the required objective, it is necessary to iterate
$G^{a}$ till a success node is reached, that is, $G^{a}$ is solved. This roll-
out of augmented AND/OR graphs give rise to an AND/OR graph network.

######  Definition 9.

An AND/OR graph network $\Gamma$ is a directed graph
$\Gamma=\langle\mathcal{G},T\rangle$ where:

  * •

$\mathcal{G}=\\{G^{a}_{1},\ldots,G^{a}_{n^{\prime}}\\}$ is a set of augmented
AND/OR graphs $G^{a}_{i}$;

  * •

$T=\\{t_{1},\ldots,t_{n^{\prime}-1}\\}$ is a set of transitions such that
$G^{a}_{i+1}=t_{i}(G^{a}_{i}),\ 1\leq i\leq n^{\prime}-1$.

Figure 2: AND/OR graph network for the pick and place scenario.

where $n^{\prime}$ is the total number of graphs in the network.
Alternatively, $n^{\prime}$ is also the depth of the network. Note that
$t_{i}$ is defined only if $G^{a}_{i}$ is unsolved, that is, if the graph
terminates at the failure node. This transitions $G_{i}$ to a new augmented
AND/OR graph $G^{a}_{i+1}=t_{i}(G^{a}_{i})$, updating the root node of
$G^{a}_{i+1}$ to the changed work-space configuration. Thus for the pick and
place scenario, we obtain an AND/OR graph network as shown in Fig. 2. The root
node is the virtual node that represents the current work-space configuration
(green node, that is, current configuration). The object to be picked and
placed is decided by a cost function, for example, the proximity to the
gripper and therefore for a single pick operation we need to traverse only the
nodes till object picked. If the target object is being held, it is then put-
down and the graph terminates, else a new object is selected to clear the path
to the target. Once the object is moved, a new graph is grown with the current
configuration being the updated current work-space configuration taking into
account the object movement.

Complexity comparison: In Section I we have discussed the computational
complexity for the toy example in Fig. 1 modeled using PDDL. We now analyze
the complexity aspects when the same example is modeled using our AND/OR graph
network (see Fig. 2). Assuming sufficient time is allotted for the motion
planner, in the worst case all the $5$ objects need to be re-arranged leading
to $5\times 5$ states3335 nodes for each object as seen in Fig. 2 and 5
iterations due to 5 objects. as opposed to $2^{13}$ using PDDL (see Section
I). However it can happen that the task execution fails, for example due to
motion, actuation or grasping errors. In such a case a new graph $G^{a}_{i+1}$
is grown retaining the same work-space configuration as $G^{a}_{i}$. Therefore
the number of iterations $m$ may be greater than the number of objects (here
$m>5$) and hence the time complexity is thus $O(5m)\approx O(m)$. Note that
for PDDL based planning, shortest path takes $O(n\log n)$ time where
$n=2^{13}$ is the number of states. In general for an AND/OR graph network
with each graph consisting of $n$ nodes, the time complexity is only $O(nm)$.
Similarly, for an AND/OR graph with $n$ nodes a storage of only $O(n)$ nodes
is required.

######  Proposition 1.

An AND/OR graph network $\Gamma=(\mathcal{G},T)$ is said to be solved at depth
$d$ when $G^{a}_{d}$ is solved.

Following Proposition 1, an AND/OR graph net with underlying augmented AND/OR
graphs $G^{a}_{i}$ is expanded till a $G^{a}_{i}$ is solved. Note that as
discussed in Section I, we are interested in problems with solutions. For
example in a cluttered table-top TMP scenario where a target object is to be
grasped, we assume that a feasible grasp exist. This may result in a network
of infinite depth. However, as a consequence of our assumption, that is, a
solution exist, the network is solved at infinite depth. Moreover, to
alleviate the issue of infinite depth, a predetermined depth limit may be
employed. Thus, as the predetermined limit approaches infinity a solution is
found. Practically, solutions with larger depth limits may be discarded as it
may be too time consuming to arrive at. This enables us to define some sort of
probabilistic completeness as will be seen later in Section IV.

##  IV TMP-IDAN

We present a novel TMP approach TMP-IDAN (Task-Motion Planning using Iterative
Deepened AND/OR Graph Networks) that uses AND/OR graph networks to compactly
encode the task-level abstractions to reduce the overall task planning
complexity.

###  IV-A System’s Architecture

An overview of TMP-IDAN is given in Fig. 3. In general the approach requires
(1) perception capabilities to comprehend objects in the scene, (2) task
planning to select the abstract actions and finally (3) motion planning for
executing the action to manipulate objects, avoiding potential collisions. The
perception capabilities are encapsulated in a single module, which is called
the Scene Perception. This module provides the Knowledge Base module with the
information about the current work-space configuration, that is, the location
of objects and the configuration of robot. The planning layer is made up of
two modules, namely the TMP Interface, and the Motion Planner modules. The TMP
Interface module receives discrete or symbolic commands from the Task Planner
and maps them to actual geometric values and drives the behavior of the Motion
Planner. This module retrieves information regarding the work-space and robot
from the Knowledge Base. It also provides an acknowledgment to the Task
Planner upon the execution of a command by the robot. The Motion Planner
module plans the outcome of robot behaviors before their actual execution.

Figure 3: System’s architecture of TMP-IDAN framework.

The Task Planner module embeds the augmented AND/OR Graph and the AND/OR Graph
Net Search. Along with the AND/OR graph, the Task Planner module is in charge
of decision making and adaptation of the ongoing parallel (by parallel we mean
different actions feasible from the current state) hyper-arcs. To do so, the
Task Planner provides a set of achieved transitions between the states to the
Graph Net Search module and receives the set of allowed cooperation states and
transitions with the associated costs to follow. It then associates each state
or state transition with an ordered set of actions in accordance with the
work-space and robot configuration and finally incorporates the online
simulation results to assign actions to the robot arms. Once an action is
carried out, it receives an acknowledgment from the planning level and updates
its internal structure. The Knowledge Base stores all relevant information to
make the cooperation progress.

require : Augmneted AND/OR Graph (AO), Task Planner (TP), TMP Interface
(TMPI), Motion Planner (MP), Knowledge Base (KB), Scene Perception (SP)

1 while  _Target not retrieved_ do

2 AO:AddNewGraph();

3 TP: Request AO NextFeasibleStates()

4 if  _Request = empty_ then

5 Go to Line 1;

6 else

7 continue;

8

9 end if

10 Find NextOptimalState();

11 for  _tasks, agents in OptimalState_ do

12 SendToTMPI(tasks,agents);

13 for  _task in tasks_ do

14 for  _agent in agents_ do

15 TMPI: RequestKB();

16 KB: RequestSP();

17 TMPI: RequestMP();

18

19 end for

20

21 end for

22

23 end for

24

25

26

27 if  _RequestMP()_ then

28 TP: FindOptimalMotionPlan()

29 TMPI: T $\leftarrow$ Optimal Motion Plan;

30 if  _T executed_ then

31 Go to Line 1;

32 else

33 Go to Line 1;

34

35 end if

36

37

38

39 else

40 Go to Line 1;

41 end if

42

43 end while

Algorithm 1 TMP-IDAN

###  IV-B Task Planning with AND/OR Graph Networks

The AND/OR graph representation provides a framework for the planning and
scheduling of task sequences [21]. The feasibility of the tasks is then
checked using a suitable motion planner [15]. Moreover, an AND/OR graph
inherently requires fewer nodes than the corresponding complete state
transition graph, reducing the search complexity of the AND/OR space [21].
Yet, such a representation requires that the number of object re-arrangement
to retrieve a target from clutter is known ahead of time. This representation
thus seems incompatible as we do not know before-hand the number of objects to
be re-arranged. To address this challenge, we introduce AND/OR graph networks
as discussed in Section III wherein an augmented AND/OR graph grows online
until the target grasp is achieved. For the cluttered table-top scenario, the
AND/OR graph network with two graphs is seen in Fig. 4 (right). Given the
initial work-space configuration, a virtual node representing the same
(INIT#0) is added giving the augmented AND/OR graph $G_{0}^{a}$. The graph
$G_{0}^{a}$ encodes the fact that if a feasible grasping trajectory exists
then the picked target task is to be performed and otherwise an object is to
be identified to be either removed or pushed. Let us consider the case that a
target grasping trajectory does not exit and that a grasped closest object of
target followed by object placed in storage is achieved which is a failure
node and thus exhausting $G_{0}^{a}$. This leads to a new graph $G_{1}^{a}$,
which corresponds to a new augmented graph, with the same states and actions
as $G_{0}^{a}$ but a different work-space configuration encoded via the
virtual node INIT#1. This process iteratively repeats itself until a graph
$G_{n^{\prime}}^{a}$ is solved which represents an AND/OR graph network
$\Gamma$ of depth $n^{\prime}$. The augmented AND/OR graphs
$G^{a}_{0},\ldots,G^{a}_{n^{\prime}}$ are thus iteratively deepened to obtain
an AND/OR graph network whose depth $n^{\prime}$ is task depended and not
known before-hand. We note here that in case a task in $G_{i}^{a}$ fails, for
example due to motion, actuation or grasping errors, $G_{i+1}^{a}$ (with
current work-space configuration) is grown and in this way our approach is
robust to execution failures.

Algorithm 1 describes the overall planning procedure. It proceeds with the an
AND/OR graph augmented with the initial work-space configuration (line 1)
which is initiated by the AND/OR graph module via the call to AddNewGraph. The
task planner module then checks for feasible states (call to
NextFeasibleStates) in the augmented graph (line 1). From among the feasible
states the optimal state is selected with the call to NextOptimalState. Our
cost function is a combination of distance of the object to the robot base,
distance to the left, right robot gripper and the size of the object. The
tasks and agents (left and right robot arm) of the feasible state are
communicated to the TMP interface with the call to SendToTMPI. Upon call to
RequestKB and RequestSP, the geometric location of the objects, grippers are
communicated to the TMP interface though the knowledge base and scene
perception modules. A motion plan is sought for by the TMP interface with the
RequestMP. If the motion plan execution fails, for example a grasping failure,
then a re-try is attempted (line 1). If a motion plan is not found then
another object is selected for re-arrangement (line 1); see Remark 1. If
motion plan is successful, a new graph is expanded and the process repeats
until the target is retrieved.

###  IV-C Probabilistic Completeness

We now prove the probabilistic completeness of TMP-IDAN.

######  Lemma 1.

For a predetermined depth limit $l$, TMP-IDAN is probabilistically complete.

###### Proof.

For motion planning, we use RRT motion planner [16] which is probabilistically
complete [14]. Thus, given sufficient time, the probability of finding a plan,
if one exists, approaches one. For the AND/OR graph network
$\Gamma=(\mathcal{G},T)$ based task planner, by design each graph $G^{a}_{i}$
terminates either at a success node or a failure node and hence each
$G^{a}_{i}$ complete. Using a predetermined depth limit $l$, $\Gamma$ is
expanded at most till depth $l$. Thus if $G^{a}_{j}$, $j\leq l$ is solved then
$\Gamma$ is solved. Else $\Gamma$ is terminated at $G^{a}_{l}$ and a non-
existence of solution is reported. In reality, a solution does not exist at
all or the chosen $l$ is shallow. However, the first scenario (non-existence
of a solution) is quashed since we are interested in TMP scenarios with
solutions (consequence of our assumption). Thus, without any loss of
generality, it can be argued that as $l$ approaches infinity the probability
of $\Gamma$ being solved asymptotically approaches one. ∎

Figure 4: (top-left) TMP-IDAN in real world (bottom-left) and in simulation.
(right) AND/OR graph net for the clutter scenario.

##  V Experimental Results

((a))

((b))

((c))

Figure 5: Various histograms with increasing network depth.

The experiments are performed on Rethink Robotics dual-arm Baxter robot which
is equipped with standard grippers and an RGB-D camera mounted on its head and
pointing downward which is used to acquire images for object detection. The
benchmarks were conducted on a workstation equipped with an Intel(R) core
<EMAIL_ADDRESS>GHz $\times$ 12 CPU’s and 16 GB of RAM. The architecture is
developed using C++ and Python under ROS Kinetic. In order to validate the
effectiveness of TMP-IDAN, we consider a cluttered table-top scenario wherein
a target object is to be retrieved from among clutter (see Fig. 4(top-left and
bottom-left)). The experiment scenario includes two physical agents, that is,
the right and left arms of the Baxter and a table-top with cylinders and
cuboids. Removed objects are placed in a storage close to the right arm and in
case the object is picked by the left arm, it is handed to right arm and
finally placed in the storage. This sequence goes on until the target grasp is
feasible. A video demonstrating the results can be found at
https://youtu.be/QV5Y1iyicQo.

###  V-A Description of the experiments

To verify the adaptability of TMP-IDAN in real-world scenarios and it’s
robustness with respect to grasping failures, we first employ TMP-IDAN in real
world with Baxter robot. Subsequently we perform twenty four different
experiments using the state-of-the-art robotics simulator CoppeliaSim [20] to
corroborate that our approach is highly fast and has a linear computational
time profile with respect to number of expanded graphs. Moreover, simulation
environment enables us to induce scenarios where number of objects is not
known in advance and also vary the target object location randomly. In
simulation, we start with four objects in the scene and increase the
complexity by adding up to 64 objects. In all the runs, the position of target
object is chosen randomly. Fig. 4 (right) shows the AND/OR graph network
employed. For the initial graph $G_{0}$ there exists several parallel hyper-
arcs of which picking the target object is given the minimum cost. If the
target is not reachable by any of the agents, then closest object to target is
set to be removed and once a feasible hyper-arc is found, then agents move
forward in the graph with the set of assigned actions.

Module | Average (s) | Std. dev(s)
---|---|---
AND/OR graph | 0.0031 | 0.0028
Graph network | 0.0104 | 0.0048
Motion planning attempts | 9.3980 | 5.6640
Motion executions | 3.3540 | 1.9320
Motion planning time | 0.8010 | 0.2170
Motion execution time | 4.7490 | 2.0240

Table I: Computation times for different modules of TMP-IDAN.

Objects | d | TP (s) | MP (s) | MP attempts | Objects re-arranged
---|---|---|---|---|---
4 | 1.67 | 0.018 | 1.044 | 15.66 | 1.33
8 | 7.33 | 0.068 | 4.560 | 50.66 | 4
15 | 14.33 | 0.170 | 20.893 | 177 | 7.5
20 | 57 | 0.422 | 61.168 | 400 | 18
30 | 19.66 | 0.188 | 28.591 | 159.66 | 9
42 | 72 | 0.462 | 44.148 | 384.5 | 18.5
49 | 26.5 | 0.342 | 24.265 | 201 | 10
64 | 76 | 0.657 | 102.575 | 693 | 29

Table II: $d$\- average network depth, TP- average total task planning time,
MP- average total motion planning time, average motion planning attempts and
the average number of objects to be re-arranged as the degree of clutter is
increased.

###  V-B Validation

Table I shows the average planning and execution time for each module
discussed in Section IV. We increase the number of objects on the table and
for each object number, we perform the experiment 3 times by randomly sampling
the target location. Table II reports the average network depth $d$, average
total task planning time, average total motion planning time, average number
of motion planning attempts and the average number of objects to be re-
arranged. Task planning times with increasing network depth corroborates our
discussion on time complexity (see Section III) and is almost linear with
respect to $d$. For motion planning, we use Moveit package [23] as RRT planner
within OMPL [24] and we place a time bound of one second. However, motion
planning failures due to actuation errors, grasping failures or occlusion lead
to re-plan, explaining the large number of motion planning attempts.

In addition to the computational complexity analysis in Table II, Fig. 5 shows
different histogram plots with increasing network depth $d$. Fig. 5(a) shows
the total task planning time with $d$. As seen above, the planning times are
almost linear with increasing $d$. However, slight deviations are readily
observed. For example, the time for $d=76$ is greater than the time for
$d=103$. This is due to the fact that in many cases, due to motion planning
failure a new graph is expanded before reaching the terminal node. Thus for
$d=76$, more number of nodes are traversed when compared to $d=103$ and
rightly justifies the histogram. Fig. 5(b) reports the number of motion
planning attempts and the total executions with increasing $d$. Note that this
depends on the degree of clutter and thereby the number of object re-
arrangements required. This is more clearly observed in the last two columns
of Table II where increase in motion planning attempts can be seen with
increased object re-arrangements. Finally, in Fig. 5(c), total execution times
with $d$ can be seen.

##  VI Conclusion

We present a novel approach TMP-IDAN, a framework for task-motion planning
that provides a compact abstraction for task-level representation using AND/OR
graph networks. This reduces the overall time and space complexity of task
planning. The network representation handles challenge of unknown object re-
arrangements and allows online expansion of graphs till the target is
retrieved. We use off-the-shelf motion planner and therefore our approach can
readily be used with any motion planner. We validate TMP-IDAN on a physical
Baxter robot and in simulation and it seen that our approach works with
different degrees of clutter. Task-planning time scales linearly with respect
to increasing network depth and this enables fast online computation in
heavily cluttered non-trivial scenarios. Immediate future work includes
reducing the depth of the graph by developing an efficient heuristic for
object selection for re-arrangement and extension to human-robot and robot-
robot collaboration.

## References

  * [1] Daniel Bryce and Subbarao Kambhampati.  A tutorial on planning graph based reachability heuristics.  AI Magazine, 28(1):47–47, 2007.
  * [2] Chin-Liang Chang and James R. Slagle.  An admissible and optimal algorithm for searching AND/OR graphs.  Artificial Intelligence, 2(2):117–128, 1971.
  * [3] Neil T. Dantam, Zachary K. Kingston, Swarat Chaudhuri, and Lydia E. Kavraki.  Incremental task and motion planning: A constraint-based approach.  In Robotics: Science and Systems, 2016.
  * [4] Christian Dornhege, Patrick Eyerich, Thomas Keller, Sebastian Trüg, Michael Brenner, and Bernhard Nebel.  Semantic Attachments for Domain-Independent Planning Systems.  In International Conference on Automated Planning and Scheduling (ICAPS), pages 114–121, Thessaloniki, Greece, September 2009.
  * [5] Christian Dornhege, Marc Gissler, Matthias Teschner, and Bernhard Nebel.  Integrating symbolic and geometric planning for mobile manipulation.  In Safety, Security & Rescue Robotics (SSRR), IEEE International Workshop on, pages 1–6. IEEE, 2009.
  * [6] Esra Erdem, Kadir Haspalamutgil, Can Palaz, Volkan Patoglu, and Tansel Uras.  Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation.  In 2011 IEEE International Conference on Robotics and Automation, pages 4575–4581. IEEE, 2011.
  * [7] Caelan Reed Garrett, Tomas Lozano-Perez, and Leslie Pack Kaelbling.  FFRob: Leveraging symbolic planning for efficient task and motion planning.  The International Journal of Robotics Research, 37(1):104–136, 2018\.
  * [8] Caelan Reed Garrett, Tomás Lozano-Pérez, and Leslie Pack Kaelbling.  Pddlstream: Integrating symbolic planners and blackbox samplers via optimistic adaptive planning.  In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pages 440–448, 2020.
  * [9] Caelan Reed Garrett, Chris Paxton, Tomás Lozano-Pérez, Leslie Pack Kaelbling, and Dieter Fox.  Online replanning in belief space for partially observable task and motion problems.  arXiv preprint arXiv:1911.04577, 2019.
  * [10] Malik Ghallab, Dana Nau, and Paolo Traverso.  Automated planning and acting.  Cambridge University Press, 2016.
  * [11] Malte Helmert.  Solving planning tasks in theory and practice.  PhD thesis, Albert-Ludwigs-Universität Freiburg, 2006.
  * [12] Leslie Pack Kaelbling and Tomás Lozano-Pérez.  Hierarchical task and motion planning in the now.  In Robotics and Automation (ICRA), IEEE International Conference on, pages 1470–1477. IEEE, 2011.
  * [13] Leslie Pack Kaelbling and Tomás Lozano-Pérez.  Integrated task and motion planning in belief space.  The International Journal of Robotics Research, 32(9-10):1194–1227, 2013.
  * [14] Sertac Karaman and Emilio Frazzoli.  Sampling-based algorithms for optimal motion planning.  The international journal of robotics research, 30(7):846–894, 2011\.
  * [15] Hossein Karami, Kourosh Darvish, and Fulvio Mastrogiovanni.  A Task Allocation Approach for Human-Robot Collaboration in Product Defects Inspection Scenarios.  In 29th IEEE International Conference on Robot and Human Interactive Communication, 2020.
  * [16] James J Kuffner and Steven M LaValle.  Rrt-connect: An efficient approach to single-query path planning.  In Robotics and Automation, 2000. Proceedings. ICRA’00. IEEE International Conference on, volume 2, pages 995–1001. IEEE, 2000.
  * [17] Fabien Lagriffoul, Neil T. Dantam, Caelan Garrett, Aliakbar Akbari, Siddharth Srivastava, and Lydia E. Kavraki.  Platform-independent benchmarks for task and motion planning.  Robotics and Automation Letters, 2018.
  * [18] Jean-Claude Latombe.  Robot Motion Planning.  Kluwer Academic Publishers, 1991.
  * [19] Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld, and David Wilkins.  PDDL- The Planning Domain Definition Language.  In AIPS-98 Planning Competition Committee, 1998.
  * [20] E. Rohmer, S. P. N. Singh, and M. Freese.  CoppeliaSim (formerly V-REP): a Versatile and Scalable Robot Simulation Framework.  In Proc. of The International Conference on Intelligent Robots and Systems (IROS), 2013.  www.coppeliarobotics.com.
  * [21] AC Sanderson, MA Peshkin, and LS Homen de Mello.  Task planning for robotic manipulation in space applications.  IEEE transactions on aerospace and electronic systems, 24(5):619–629, 1988.
  * [22] Siddharth Srivastava, Eugene Fang, Lorenzo Riano, Rohan Chitnis, Stuart Russell, and Pieter Abbeel.  Combined task and motion planning through an extensible planner-independent interface layer.  In Robotics and Automation (ICRA), IEEE International Conference on, pages 639–646. IEEE, 2014.
  * [23] Ioan A Sucan and Sachin Chitta.  Moveit!, 2013.
  * [24] Ioan A. Şucan, Mark Moll, and Lydia E. Kavraki.  The Open Motion Planning Library.  IEEE Robotics & Automation Magazine, 19(4):72–82, December 2012\.  https://ompl.kavrakilab.org.
  * [25] Antony Thomas, Fulvio Mastrogiovanni, and Marco Baglietto.  Task-Motion Planning for Navigation in Belief Space.  In The International Symposium on Robotics Research, 2019.
  * [26] Marc Toussaint.  Logic-geometric programming: An optimization-based approach to combined task and motion planning.  In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.


# A Comparison of Deep-Learning Methods for Analysing and Predicting Business
Processes

Ishwar Venugopal  University of Essex, UK
<EMAIL_ADDRESS>Jessica Töllich  Ulm University, Germany
<EMAIL_ADDRESS>Michael Fairbank  University of Essex, UK
<EMAIL_ADDRESS>Ansgar Scherp  Ulm University, Germany
<EMAIL_ADDRESS>
###### Abstract

Deep-learning models such as Convolutional Neural Networks (CNN) and Long
Short-Term Memory (LSTM) have been successfully used for process-mining tasks.
They have achieved better performance for different predictive tasks than
traditional approaches. We extend the existing body of research by testing
four different variants of Graph Neural Networks (GNN) and a fully connected
Multi-layer Perceptron (MLP) with dropout for the tasks of predicting the
nature and timestamp of the next process activity. In contrast to existing
studies, we evaluate our models’ performance at different stages of a process,
determined by quartiles of the number of events and normalized quarters of the
case duration. This provides new insights into the performance of a prediction
model, as they behave differently at different stages of a business-process.
Interestingly, our experiments show that the simple MLP often outperforms more
sophisticated deep-learning models in both prediction tasks. We argue that
care needs to be taken when applying automated process-prediction techniques
at different stages of a process. We further argue that researchers should
reflect their results with strong baselines methods like MLPs.

##  I Introduction

Most businesses thrive on the effective use of event logs and process records.
The ability to predict the nature of an unseen event in a business-process can
have very useful applications [4]. This can help in more efficient customer
service, and facilitate in developing an improved work-plan for companies. The
domain of process mining deals with combining a wide range of classical model-
based predictive techniques along with traditional data-analysis techniques
[27]. A process can be a representation of any set of activities that take
place in a business enterprise; for example, the procedure for obtaining a
financial document, the steps involved in a complaint-registering system, etc.

Business-process mining, in general, deals with the analysis of the sequence
of events produced during the execution of such processes [6, 16, 18]. Even
though the classical approach of depicting event logs is with the help of
process graphs [1, 30], Pasquadibisceglie et al. [20], Tax et al. [23],
Taymouri et al. [25], and others have recently applied deep-learning
techniques like Convolutional Neural Networks (CNN), Long Short-Term Memory
(LSTM) networks, and Generative Adversarial Nets (GANs) for the task of
predictive process mining. The deep-learning based models obtained results
that outperformed traditional models.

Inspired from these works and taking into consideration the graph nature of
processes, we aim to model event logs as graph structures and apply different
Graph Neural Network (GNN) models on such data structures. GNNs have shown
superior results for the vertex-classification task [14], link-prediction task
[33], and recommender systems [32]. In this work, we use a new representation
for the event-log data and investigated the performance of different variants
of a Graph Convolutional Network (GCN) [14] as a successful example of GNNs.
We compare the GCN model among others with the CNN and LSTM models along with
a Multi-Layer Perceptron (MLP) and classical process-mining techniques [4,
28].

In contrast to the existing body of research [20, 9, 5, 23, 25, 15], we
analyze how the performance of the models for business-process prediction
depend on the stage of a process. The results show that the next activity type
and timestamp prediction depend a lot on the model and also on whether an
early, mid, or late stage of the process is considered. Furthermore, we
observe from our experiments that MLP is a strong baseline and in many cases
outperforms more advanced neural networks like LSTMs, GCNs, and CNNs. The MLP
model achieves a maximum of 82% accuracy in predicting the next event type,
and a minimum mean absolute error of 1.3229 days for predicting the timestamp
of the next event.

Below, we discuss related works in business-process mining. Section III
introduces our experimental apparatus, datasets and pre-processing, as well as
our GCN-based models. Sections IV and V highlights the major results from the
experiments, followed by a discussion in Section VI, before we conclude.

##  II Related Works

Business-process mining deals with several prediction tasks like predicting
the next activity type [2, 23, 20, 9, 4], the timestamp of the next event in
the process [23, 28], the overall outcome of a given process [24], or the time
remaining until the completion of a given process instance [21]. There is a
huge body of algorithms for these process-mining tasks [4, 28]. In the context
of this work, we focus on the first two aspects of the aforementioned list of
predictive tasks, namely, the task of predicting the nature and timestamp of
the next event in a given process. We reconsider the results from the
classical methods and compare them with latest developments on business-
process mining using deep learning.

There has been a recent shift towards deep-learning models for the task of
predictive business-process monitoring. Tax et al. [23] proposed to use a
Recurrent Neural Network (RNN) architecture with Long Short-Term Memory (LSTM)
for the task of predicting the next activity and timestamp, the remaining
cycle time, and the sequence of remaining events in a case. Their model was
able to model the temporal properties of the data and improve on the results
obtained from traditional process-mining techniques. The main motivation for
using an LSTM model was to obtain results that were consistent for a range of
tasks and datasets. The LSTM architecture of Tax et al. could also be extended
to the task of predicting the case outcome. Camargo et al. [5] and Lin et al.
[15] both use LSTM models, too. The first one to predict the next event
including timestamp and the associated resource pool, the latter to predict
the next event, including its attributes. Evermann et al. [9] also used RNN
for the task of predicting the next event on two real-life datasets. Their
system architecture involved two hidden RNN layers using basic LSTM cells.

Pasquadibisceglie et al. [20] used Convolutional Neural Networks (CNN) for the
task of predictive process analytics. An image-like data engineering approach
was used to model the event logs and obtain results from benchmark datasets.
In order to adapt a CNN for process-mining tasks, a novel technique of
transforming temporal data into a spatial structure similar to images was
introduced. The CNN results improve over the accuracy scores obtained by Tax
et al.’s LSTM [23] for the task of predicting the next event.

Scarselli et al. [22] introduced Graph Neural Networks (GNNs) as a new deep-
learning technique that could efficiently perform feature extraction.
Especially in the last year, GNNs have gained widespread attention and use in
different domains. Wu et al. [31] provided a comprehensive survey of GNNs.
They categorize the different GNN architectures into Graph Convolutional
Networks (GCN, or also called: ConvGNN), Spatio-temporal Graph Neural Networks
(STGNNs), Recurrent Graph Neural Networks (RecGNN), and Graph Autoencoders
(GAEs). Esser et al. [8] discussed the advantages of using graph structures to
model event logs. Performing process-mining tasks by modelling the
relationships between events and case instances as process graphs has been a
widely accepted approach [19, 29].

Recently, Taymouri et al. [25] have used Generative Adversarial Nets (GANs)
for predicting the next activity and its timestamp. In a minmax game of
discriminator and generator, both consisting of RNNs in a LSTM architecture
and feedforward neural networks, a prediction is made of the next step,
including event type and event-timestamp prediction. Taymouri et al. used
different models each trained over a specific length of sub-sequences of
processes, modeled by the parameter $k$. For example, a value of $k=20$ means
that sub-sequences of length $20$ are used for training, and testing would be
applied on process steps $21$, $22$, $23$, and following until the end of the
process.

Other works used features from unstructured data like texts in deep-learning
architectures to improve the process-prediction task. Ding et al. [7]
demonstrate how a deep-learning model using events extracted from texts
improves predictions in the stock markets domain. For business-process
modelling, Teinemaa et al. [26] improve the performance of predictive business
models by using text-mining techniques on the unstructured data present in
event logs.

In this work, we aim to combine traditional process mining from event graphs
along with deep-learning techniques like GCNs to achieve a better performance
in predictive business-process monitoring. We evaluate each of the model
variants at different stages of a process, determined by quartiles of the
number of events in a case and normalized quarters computed over the case
durations. This would provide a more detailed understanding of the models’
performance.

##  III Experimental Apparatus

We introduce the datasets used in this work and the methodology adopted for
representing the feature vectors corresponding to each row in the dataset.
Following this, a mathematical formulation of graphs and the specific case of
process graphs is provided, which lays the foundation to understand a Graph
Convolutional Network. We conclude with a description of the procedure and
metrics adopted for this work.

###  III-A Datasets

We use two well-known benchmark event-log datasets, namely Helpdesk and BPI12
(W). These two representative datasets have been chosen as they are used by
the models we want to compare with, namely the CNN by Pasquadibisceglie et al.
[20], LSTMs from Camargo et al. [5] and Tax et al. [23], and the GAN from
Taymouri et al. [25]. Thus, the datasets best possible serve the purpose to
compare the different Deep-Learning architectures. All datasets are
characterised by three columns: “Case ID” (the process-case identifier),
“Activity ID” (the event-type identifier), and the “Complete Timestamp”
denoting the time at which a particular event took place. Table I shows an
overview of the datasets.

Table I: Overview of the datasets used Attribute | Dataset
---|---
Helpdesk | BPI12(W)
No. of events | 13,710 | 72,413
No. of process cases | 3,804 | 9,658
No. of activity types | 9 | 6
Avg. case duration (sec.) | 22,475 | 1,364
Avg. no. of events per case | 3.604 | 7.498

#### Helpdesk dataset

This dataset presents event logs obtained at the helpdesk of an Italian
software company.111https://data.mendeley.com/datasets/39bp3vv62t/1 The events
in the log correspond to the activities associated with different process
instances of a ticket management scenario. It is a database of 13,710 events
related to 3,804 different process instances. There are 9 activity types, i.
e., classes in the dataset. Each process contains events from a list of nine
unique activities involved in the process. A typical process instance spans
events from inserting a new ticket, until it is closed or resolved. Table I
shows the average case duration and the number of activities per case.

#### BPIC’12 (Sub-process W) dataset

The Business-Process Intelligence Challenge (BPIC’12)
dataset222https://www.win.tue.nl/bpi/doku.php?id=2012:challenge&redirect=1id=2012/challenge
contains event logs of a process consisting of three sub-processes, which in
itself is a relatively large dataset. As described in [23] and [20], only
completed events that are executed manually are taken into consideration for
predictive analysis. This dataset, called BPI12 (W), includes 72,413 events
from 9,658 process instances. Each event in a process is one among 6 activity
types involved in a process instance, i. e., a process case. The activities
denote the steps involved in the application procedure for financial needs,
like personal loans and overdrafts.

###  III-B Graphs and Graph Convolutional Layer

A graph can be represented as $G=(V,E)$, where V is the set of vertices and E
denotes the edges present between the vertices [31]. An edge between vertex i
and vertex j is denoted as eij $\in$ E. A graph can be either directed or
undirected, depending on the nature of interaction between the vertices. In
addition, a graph may be characterized by vertex attributes or edge
attributes, which in simple terms are feature vectors associated with that
particular vertex or edge. The adjacency matrix of a graph is an $n\times n$
matrix with Aij = 1 if eij $\in$ E and Aij = 0 if eij $\notin$ E, where n is
the number of vertices in the graph. A degree matrix is a diagonal matrix
which stores the degree of each vertex, which numerically corresponds to the
number of edges that the node is attached to.

A GCN layer operates by calculating a hidden embedding vector for each node of
the graph. It calculates this hidden vector by combining each node’s feature-
vector with the adjacency matrix for the graph, by the equation (Kipf and
Welling [14]):

$f(X,A,W)=\sigma(D^{-1}AXW),$ (1)

where X is the input-feature matrix containing the feature vector for each of
the vertices, A is the adjacency matrix of the graph, D is the degree matrix,
W is a learnable weight matrix, and $\sigma$ is the activation function of
that layer.

In (1), the product $D^{-1}A$ represents an attempt to normalize the adjacency
matrix. However, as matrix multiplication is non-commutative, an alternative
symmetric normalisation is preferred [14], changing the GCN layer’s operation
to:

$f(X,A,W)=\sigma(D^{-\frac{1}{2}}AD^{-\frac{1}{2}}XW)$ (2)

Note, all the models used in this work, the GCN layer calculations are done as
described in (2). For the model variants described in Section III-F involving
the Laplacian matrix, the adjacency matrix ($A$) in (2) is replaced by the
corresponding unnormalized Laplacian.

###  III-C Data Pre-processing

The timestamp corresponding to each event in the dataset can be used to derive
a feature-vector representation for each row in the data. The approach
introduced in [23] has been used to initially get a feature vector consisting
of the following four elements: 1. The time since previous event in the case.
2. The time since the case started. 3. The time since midnight. 4. The day of
the week for the event. All four values are treated as real-valued durations.
This results in a 4-element feature vector for every row in the dataset. The
drawback in this kind of a representation is that it treats each event in a
case independently. In order to overcome this drawback, it was necessary for
the feature vector of every event to have a history of other events that had
already occurred for that particular Case ID. Hence, a new comprehensive
feature vector representation was introduced.

In this work, each entry in a dataset is assigned a matrix representation
(_X_) whose dimensions depend on the dataset which is considered. The number
of _rows_ in _X_ can be obtained by identifying the unique entries in the
‘Activity ID’ column, i. e., the unique activity types as shown in Table I, or
can be visually identified as the number of vertices in the process graphs for
each of the datasets (Figure 1). Let us denote this value by
‘num$\\_$of$\\_$nodes’ for ease of representation. As it can be observed from
Table I, num$\\_$of$\\_$nodes is 9 for the Helpdesk dataset and 6 for the
BPI’12 (W) dataset. The number of _columns_ in _X_ corresponds to the length
of the initial feature vector, i. e., 4. This would result in a matrix of size
‘$num\\_of\\_nodes\times 4$’ for each data entry.

The matrix _X_ is first initialized with zeroes. Each row index of $X$ stores
the 4-element long feature vector corresponding to the most-recent Activity ID
denoted by that particular row index, for the current case ID. For example,
the first row stores the 4-element long feature vector for the event with
Activity ID equal to 1, and so on. One approximation that we have used in this
step is that if an event corresponding to a particular Activity ID has
occurred more than once in a case, we use the feature vector for only the
most-recent occurrence of that event. In scenarios where events with a
particular Activity ID have not occurred yet in a given case, the feature
matrix will hence just store a vector with zeroes corresponding to that
Activity ID. This method of representation gives each row of the Helpdesk
dataset a $9\times 4$ matrix, and each row of the BPI’12 (W) dataset a
$6\times 4$ matrix. The motivation behind choosing such a representation is to
facilitate the computation involved in a Graph Convolutional Layer, as
explained in Section III-B. For a given row, the Activity ID of the next event
and the time since current event are taken as the target labels for the event-
predictor and the time-predictor, respectively.

###  III-D Process Graphs as Input to GCNs

Figure 1: Directly-follows graphs generated for the Helpdesk dataset (left)
and BPI’12 (W) dataset (right) using PM4Py. The vertices represent the unique
Activity IDs (i. e., activity types) along with their frequencies denoted in
brackets. The numbers on the directed edges denote the frequency of directly-
follows relations. Figure 2: Graph Convolutional Network architecture for the
event type and timestamp predictor. The value for n in the last layer denotes
the number of classes for the event predictor and 1 for the time predictor.

Process discovery from event logs can be achieved using different traditional
process-mining techniques. In this work, we have used an inductive mining
approach with Directly-Follows Graphs (DFGs) to represent the processes
extracted from each of the datasets. The choice is motivated by the simplicity
and efficiency with which the entire data can be represented in the form of a
graph.

A Directly-Follows Graph for an Event Log L is denoted as [27]:
$G(L)=(A_{L},\mapsto_{L},A_{L}^{start},A_{L}^{end})$, where AL is the set of
activities in L with A${}_{L}^{start}$ and A${}_{L}^{end}$ denoting the set of
start and end activities, respectively. $\mapsto_{L}$ denotes the directly-
follows operation, which exists between two events if and only if there is a
case instance in which the source event is followed by the other target event.
The vertices in the graph represent the unique activities present in the event
log, and the directed edges of the graph exist if there is a directly-follows
relation between the vertices. The number of directly-follows relations that
exist between two vertices is denoted by a weight for the corresponding edge.

Berti et al. [3] presented a process-mining tool for Python called PM4Py. The
Directly-Follows Graphs for both the datasets (considering all the
events/rows) were visualised using the PM4Py package as shown in Figure 1.
Consider the following binary adjacency matrix for the process graph
generated, as example, from the BPI’12 (W) dataset:

$B_{BPI^{\prime}12(W)}=\begin{bmatrix}1&1&1&0&0&0\\\ 1&1&1&0&0&1\\\
0&1&1&0&1&0\\\ 0&0&0&1&0&1\\\ 0&0&1&0&1&1\\\ 0&1&0&1&1&1\\\ \end{bmatrix}$

This $6\times 6$ matrix needs to be normalized as per Equation (2) to be used
in a GCN. The elements of the diagonal degree matrix can be numerically
computed as a row-wise sum from the above matrix. The dimensions of the
normalized matrix ($6\times 6$) and the dimension of _X_ ($6\times 4$ for
BPI’12 (W) dataset) makes it compatible for matrix multiplication in the GCN
layer. In general, the normalized adjacency matrix will have dimensions
$num\\_of\\_nodes\times num\\_of\\_nodes$ and _X_ the dimensions
$num\\_of\\_nodes\times 4$.

###  III-E Procedure

The network depicted in Figure 2 shows the architecture for the GCN model that
learns the next Activity ID and the timestamp of the next activity. The
overall structure that was constructed for this work mainly focuses on a Graph
Convolutional Layer followed by a sequential layer consisting of three fully-
connected layers with Dropout (present after the GCN layer and before the last
fully-connected layer). The weight matrix (W) in the GCN layer is of size
$4\times 1$. The Event Predictor Network has tanh activation for the first two
fully connected layers and softmax activation at the last layer. Cross-entropy
loss is used during training. The Timestamp Predictor Network on the other
hand consists of ReLU activation for the first two layers and a linear
activation function at the last layer. The training process uses the Mean
Absolute Error as the loss function. An Adam optimizer [13] is used for the
training processes for all variants. In line with the training procedure of
prior studies [23, 20], each of the datasets is divided into train (2/3) and
test sets (1/3). We use 20% of the training as validation set during the
training process. The validation set is randomly sampled from the training set
in each of the five experimental runs. Note, the chronological nature of the
datasets have been preserved during the train-test splitting. One row is taken
at a time during training resulting in a mini-batch size of 1. The final
results after the evaluation on the test set are reported as an average
measure of 5 runs.

Table II: Accuracy for next-event prediction at different stages of a process (indicated by quartiles based on the number of events and quarters based on normalising the case duration). Standard deviations (SD) have been omitted as they are very low ($<0.06$).  Dataset | Model | Accuracy for Event Prediction |  Overall accuracy
---|---|---|---
Quartiles based on Events | Quarters based on Duration
1 | 2 | 3 | 4 | 1 | 2 | 3 | 4
Helpdesk | GCNW | 0.7288 | 0.6888 | 0.7634 | 0.9419 | 0.7499 | 0.5508 | 0.5940 | 0.8951 | 0.7954
GCNB | 0.7266 | 0.6778 | 0.7475 | 0.8973 | 0.7418 | 0.5410 | 0.5590 | 0.8561 | 0.7731
GCNLB | 0.7270 | 0.6837 | 0.7729 | 0.9108 | 0.7523 | 0.5492 | 0.5819 | 0.8722 | 0.7863
GCNLW | 0.6681 | 0.6922 | 0.7665 | 0.9167 | 0.7389 | 0.5508 | 0.5723 | 0.8803 | 0.7830
MLP | 0.7297 | 0.7031 | 0.8110 | 0.9642 | 0.7677 | 0.6082 | 0.6446 | 0.9212 | 0.8201
BPI’12 (W) | GCNW | 0.6964 | 0.7397 | 0.8011 | 0.4303 | 0.7247 | 0.8802 | 0.7869 | 0.4493 | 0.6484
GCNB | 0.7329 | 0.7487 | 0.8039 | 0.3936 | 0.7424 | 0.8819 | 0.7933 | 0.4251 | 0.6473
GCNLB | 0.7381 | 0.7587 | 0.8111 | 0.4077 | 0.7579 | 0.8961 | 0.7883 | 0.4329 | 0.6569
GCNLW | 0.7366 | 0.7542 | 0.8050 | 0.4028 | 0.7552 | 0.8827 | 0.7882 | 0.4279 | 0.6525
MLP | 0.6554 | 0.7369 | 0.8058 | 0.4792 | 0.7006 | 0.8818 | 0.8001 | 0.4888 | 0.6559
Table III: MAE values (in days) for predicting the timestamp of the next-event at different stages of a process (indicated by quartiles based on the number of events and quarters based on normalising the case duration). SDs omitted as they are very low ($<0.2$). Dataset | Model | MAE (in days) for Time Prediction |  Overall MAE (days)
---|---|---|---
Quartiles based on Events | Quarters based on Duration
1 | 2 | 3 | 4 | 1 | 2 | 3 | 4
Helpdesk | GCNW | 2.2955 | 2.8397 | 4.1637 | 0.3340 | 3.6811 | 6.4332 | 3.6726 | 0.1806 | 2.3346
GCNB | 2.2993 | 2.8577 | 4.1483 | 0.3143 | 3.6958 | 6.3667 | 3.4909 | 0.1768 | 2.3298
GCNLB | 2.2973 | 2.8474 | 4.1085 | 0.3433 | 3.6744 | 6.2572 | 3.5081 | 0.2020 | 2.3250
GCNLW | 2.2950 | 2.8470 | 4.0661 | 0.3323 | 3.6651 | 6.1060 | 3.2253 | 0.2195 | 2.3095
MLP | 2.2948 | 2.9030 | 4.1969 | 0.3445 | 3.5724 | 5.688 | 5.0011 | 0.3572 | 2.3661
BPI’12 (W) | GCNW | 1.0956 | 1.5503 | 1.6047 | 1.1491 | 1.7064 | 2.4116 | 1.7891 | 0.4943 | 1.3468
GCNB | 1.1134 | 1.6109 | 1.6877 | 1.1449 | 1.7666 | 2.5344 | 1.8986 | 0.4548 | 1.3837
GCNLB | 1.1114 | 1.6043 | 1.6775 | 1.1359 | 1.7530 | 2.5318 | 1.8997 | 0.4495 | 1.3765
GCNLW | 1.1069 | 1.5900 | 1.6632 | 1.1437 | 1.7528 | 2.4998 | 1.8530 | 0.4618 | 1.3710
MLP | 1.0966 | 1.5224 | 1.5587 | 1.1288 | 1.6529 | 2.3617 | 1.7134 | 0.5276 | 1.3229

###  III-F GCN Model Variants and MLP Baseline

We have introduced four GCN variants of this general architecture and an MLP-
only variant for the experiments carried out in this work.

#### GCNW (GCN with Weighted Adjacency Matrix)

The adjacency matrix of the process graph depicted in Figure 1 is computed.
Rather than a traditional approach of using binary entries (as in
$B_{BPI^{\prime}12(W)}$), we introduce a new method in this variant by having
the adjacency matrix store the values corresponding to the weighted edges of
the process graph. The normalization procedure given in Eq. (2) is then
applied to this adjacency matrix in the GCN layer.

#### GCNB (GCN with Binary Adjacency Matrix)

This variant uses the binary adjacency matrix shown in the previous section
(see example: $B_{BPI^{\prime}12(W)}$). The degree matrix is computed, from
which a symmetrically normalized adjacency matrix is obtained. The main
motivation behind using the binary and weighted variants of the adjacency
matrix is due to the fact that GCNB is heavily influenced by outliers whereas
GCNW might be biased by frequency differences between common connections in
the DFG.

#### GCNLW (GCN with Laplacian Transform of Weighted Adjacency Matrix)

The Laplacian matrix [12] of a graph is $L=D-A$, where D is the Degree matrix
and the A is the Adjacency matrix. In this variant, A corresponds to the
weighted adjacency matrix. The Laplacian matrix is then used for all
computations involved within the Graph Convolutional layer as follows:
$f(X,A,W)=\sigma(D^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}}XW)$.

#### GCNLB (GCN with Laplacian Transform of Binary Adjacency Matrix)

This variant is equivalent to the previous one, except for the fact that it
uses the binary adjacency matrix instead of the weighted adjacency matrix to
compute the Laplacian matrix.

#### MLP (Multi-Layer Perceptron)

: In order to understand if the GCN layer added any significant change to the
performance, we used a variant which had only the three fully-connected layers
(omitting the GCN layer). This model also serves as baselines for the other
architectures compared. The feature matrix (_X_) was flattened and given as
input to the fully-connected layers. As in the other variants, Dropout is used
before the last layer. Hence, the dimensions for the input vector of the MLP
was ($number\\_of\\_nodes\times number\\_of\\_features$).

###  III-G Measures

Each row is associated with two labels, the next activity type and the time
(in seconds) after which the next event in that case takes place. As in [23],
an additional label is added to denote the end of a case.

#### Next Activity and Timestamp

The quality of the next activity is measured in terms of the accuracy of
predicting the correct label. In the case of timestamp prediction, we use Mean
Absolute Error (MAE) calculated in days.

#### Quartiles based on Events

We have evaluated the performance of each variant at different quartiles. The
quartiles for each case instance have been computed based on the number of
events. For each case instance, its full list of events are split into four
(approximately) equal quartiles, based on the order the events occurred in
that case instance.

#### Quarters based on Unit Length Time

We normalize the full case duration to unit length time and divide it into
four equidistant intervals, to make a comparison along the time axis between
cases and datasets possible. Thus, each case instance’s full duration is
divided by 4, and the case’s events are put into the four intervals based on
their individual finishing timestamps. In contrast to the quartiles based on
events above, these temporal quarters divide the true natural distribution of
the process events based on time.

##  IV Results of Predicting Event Types and Time at Different Stages for GCNs
and MLP

We describe per dataset the results for the GCN and MLP models based on the
quartiles over event type and quarters of the unit length time. Subsequently,
we compare the performance of the deep-learning architectures CNN, LSTM, GCN,
and GAN with the MLP and classical approaches.

###  IV-A Helpdesk Dataset

#### Optimization

Each of the model variants was initially run with different learning rates for
the Adam optimizer. The learning rate with the best performance was chosen for
each variant. For all the GCN variants, the best performance for the timestamp
predictor was obtained with a learning rate of 0.001. For the event predictor,
GCNLW gave the best performance at a learning rate of 0.001 and all other GCN
variants performed best at 0.0001. For the MLP model, both the tasks gave best
results at a learning rate of 0.0001. The model corresponding to the best
validation loss is saved for all the model variants, and then evaluated on the
same test set.

#### Results

The accuracy values corresponding to the event-prediction task achieved in
this process is presented in Table II. The Mean Absolute Error (in days)
achieved on a test set from models saved for the different variants is shown
in Table III. It can be observed from Tables II and III that the MLP model
outperforms all other variants for the event-prediction task, in all
individual quartiles/quarters as well as for the overall performance. Among
all model variants, a maximum overall accuracy of 82.01% is obtained for the
event predictor by the MLP. The minimum overall MAE of 2.3095 days was
achieved by the GCNLW variant.

###  IV-B BPI’12 (W) Dataset

#### Optimization

The same optimization procedure as for the Helpdesk dataset has been used. The
timestamp predictor for all variants gave the best results with a learning
rate of 0.0001. It is also the preferred learning rate for the event predictor
in all variants, except GCNB and MLP (where it is 0.00001). The computation of
quartiles over event types is also the same as before.

#### Results

The accuracy values and MAE values for the BPI’12 (W) dataset are presented in
Tables II and III. The MLP model outperforms all other variants in the time-
prediction task for most of the scenarios. An overall minimum MAE of 1.3229
days is achieved. We are able to observe slight variations when it comes to
the results of the event predictor. The best performance at individual
quartiles and quarters are shown by GCNLB and MLP for different instances. The
highest overall accuracy of 65.69% is achieved by GCNLB.

Table IV: Comparison of the different models with other reported results on
the same benchmark datasets

Model |  | Accuracy for
---
Event Prediction
| MAE (in days) for
---
Time Prediction
Helpdesk | BPI’12 (W) | Helpdesk | BPI’12 (W)
CNN [20] | 0.7393 | 0.7817 | N/A | N/A
LSTM (Evermann et al.) [9] | N/A | 0.623 | N/A | N/A
LSTM (Camargo et al.) [5] | 0.789 | 0.778 | N/A | N/A
LSTM (Tax et al.) [23] | 0.7123 | 0.7600 | 3.75 | 1.56
GCNW | 0.7954 | 0.6484 | 2.3346 | 1.3468
GCNB | 0.7731 | 0.6473 | 2.3298 | 1.3837
GCNLB | 0.7863 | 0.6569 | 2.3250 | 1.3765
GCNLW | 0.7830 | 0.6525 | 2.3095 | 1.3710
MLP | 0.8201 | 0.6559 | 2.3661 | 1.3229
Breuker et al. [4] | N/A | 0.719 | N/A | N/A
WMP Van der Aalst et al. [28] | N/A | N/A | 5.67 | 1.91
GAN+LSTM [25] ($k=2$) a | 0.8668 | 0.7535 | 1.6434 | 1.4004
GAN+LSTM [25] ($k=4$) a | 0.8657 | 0.8009 | 1.1505 | 1.1611
GAN+LSTM [25] ($k=6$) a | 0.8976 | 0.8298 | 0.8864 | 0.9390
GAN+LSTM [25] ($k=16$) a | N/A | 0.9019 | N/A | 0.4274
GAN+LSTM [25] ($k=30$) a | N/A | 0.9290 | N/A | 0.3399
LSTM (Lin et al.) [15] b | 0.916 | N/A | N/A | N/A

  * •

a) Our reruns of the code adapted to fit the evaluation strategy of the CNN,
LSTM, GCN, and MLP for fair comparison. Note, models are based on a specific
$k$ value, i. e., they only predict cases of length $k+1$ or longer.

  * •

b) Code was not available. Thus the number cannot be independently confirmed.

##  V Results of Comparing Deep-Learning Variants of CNN, LSTM, GCN, and GAN

We compare the performance of the different deep-learning variants of CNN,
LSTM, GCN, and GAN with the MLP and classical approaches. As mentioned in
Section II, the task of event prediction and the timestamp prediction has been
explored in various other works as well, using other techniques. Table IV
compiles the best results reported in other works and compares them with the
results obtained from our GCNs as documented in Section IV.

The values for the GAN by Taymouri et al. [25] have been obtained after
rerunning the original code with necessary changes to make it comparable with
the other results. This was necessary since the original paper by Taymouri et
al. [25] reported only weighted average measures over different case lengths
(_k_ values). Also, their train-test split ratio was 80:20 and changed to
66:33 as in the other and our models [23, 20]. The source code from the model
introduced by Lin et al. [15] was not available online. Hence, their results
have been included in Table IV as a separate block. For the classical process-
mining model reported by Van der Aalst et al. [28], we have used the values
obtained from the experiments conducted by Tax et al. [23] on the current
datasets.

It can be observed from Table IV that all the model variants introduced in
this work perform well in comparison to previous models for the time-
prediction task. For the event-prediction task, we have mixed results. On the
Helpdesk dataset, all the GCN model variants outperform two LSTM models [23,
5] and the CNN model [20], but fail to outperform the improved LSTM model
introduced by Lin et al. [15]. Our models perform poorly on the BPI’12 (W)
dataset for event prediction. Regarding the GAN+LSTM [25], the results show
that it is generally a strong performer. But it has to be noted that the
training procedure is fundamentally different from the other models due to the
use of the parameter $k$. This parameter denotes that subsequences of the
processes of length $k$ are used for training, and $k+1$, $k+2$ etc. are used
for testing. Thus, the result for, e. g., $k=30$ on the BPI12 (W) dataset only
considers few process cases of length 31 or more.

##  VI Discussion

Our experiments show that a simple MLP is able to outperform other
sophisticated architectures such as the LSTMs and CNN. But it is also to be
noted that MLP does not emerge as the best performer in all of the
experiments. Some possible factors that might have resulted in this
performance could be an improved feature vector representation or the fact
that the number of classes in the event-prediction task is not that high (9+1
classes for Helpdesk dataset and 6+1 classes for the BPI’12 (W) dataset).
Thus, the simple MLP models were able to effectively learn the correlations
between input features and the target labels.

Regarding our analysis at different quartiles based on the number of events
and quarters based on unit-length time show that automated process-prediction
results vary at different stages of a business process. For example, with the
Helpdesk dataset, the accuracy of event prediction continuously improves over
the quartiles based on events. However, for the BPI’12 (W) dataset, it
surprisingly improves only until the 3rd quartile, when it suddenly drops in
the last quartile. A similar observation can be made for MAE over both
quartiles based on events and quarters based on duration. Here, the scores
continuously increase (MAE gets worse), until they drop in the last quartile.
Quartiles over events and quarters over unit length time truly model two
different things. Quarters better reflect the performance in a unit length
progression over time, but can be negatively influenced by a skewed event
distribution. At the same time, quartiles have an equal distribution. Future
experiments would need to be conducted to explain this varying behaviour
between datasets and measures.

A potential risk to the validity of these results can be from one of the
assumptions we had used during the pre-processing stage. Where there were
recurring events of the same type in a case, we only included that event
type’s most-recent occurrence. Particularly in the BPI’12 (W) dataset, there
are cases where the same event occurs many times. To understand how our
assumption might have affected the results, the same experiments were
performed on a different version of the BPI’12(W) dataset, which had reduced
instances of an event following itself [23]. But the results obtained were
very similar to the original dataset.

Comparing the different models has been in general very difficult, due to
different train-test split ratios and different training procedures. Following
[23, 20], we have used $2/3$rd of the data for training and $1/3$rd for
testing, while preserving the chronological nature of the data. Other works
like [4, 5] have also used a ratio that is comparable to ours, namely 70:30
for training and testing. Only the GAN model [25] had originally used a 80:20
split and the work carried out by Lin et al. [15] have split the data in a
7:2:1 ratio. Since the GAN code is available, we adapted it to the same train-
test split and rerun it with $25$ epochs, as stated in the paper, for
different values of $k$. The code for the LSTM by Lin et al. is not available,
as also noted by Taymouri et al. [25], and thus cannot be independently
confirmed. However, this study includes three other strong LSTM models, which
are directly comparable.

A key difference of the GAN model is its training procedure, which involves
windows of different case-lengths (the _k_ values), whereas our training
procedure does not differentiate between different case lengths. For example,
the GAN model with $k=30$ is trained on subsequences of processes of a length
of 30 in the BPI12 (W) dataset. For testing, only the remaining few process
cases of length 31, 32 etc. are used. Thus, the GAN results [25] cannot be
compared directly to any of the other models, which are designed to make
predictions on any lengths of cases, but are reported in Table IV for
completeness.

The major impact of this work lies in the observation that there is no silver-
bullet method when it comes to business-process prediction. It can be observed
that MLP is a strong baseline and in many cases outperforms complex neural
networks like the LSTM, GCN, and CNN. However, interestingly, there are cases
where the MLP performs comparably poor, such as predicting the activity type
in the BPI2 (W) dataset. There have been other works which report similar
behaviour of an MLP baseline for classification tasks [11, 10, 17]. Thus,
interesting future work is to understand why MLPs perform well on certain
datasets, outperforming strong models, while their performance is low for
other datasets. Also, it would be interesting to look into other variations in
representing the feature vector.

##  VII Conclusions

Our experiments show that MLP is a strong baseline for the task of event
prediction and time prediction in business processes. However, overall the MLP
is not a clear best performing model. Furthermore, the detailed analyses at
different quartiles based on the number of events and quarters based on unit
length time show that automated process-prediction results vary at different
stages of a business process. Hence, care must be taken while evaluating and
applying business-process prediction models. The source code for this work is
available at: https://github.com/ishwarvenugopal/GCN-ProcessPrediction

## References

  * [1] Rakesh Agrawal, Dimitrios Gunopulos and Frank Leymann  “Mining process models from workflow logs”  In _Extending Database Technology_ , 1998  Springer
  * [2] Jörg Becker, Dominic Breuker, Patrick Delfmann and Martin Matzner  “Designing and implementing a framework for event-based predictive modelling of business processes”  In _Enterprise modelling and information systems architectures_ Gesellschaft für Informatik, 2014
  * [3] Alessandro Berti, Sebastiaan J. Zelst and Wil M.. Aalst  “Process Mining for Python (PM4Py): Bridging the Gap Between Process- and Data Science”  In _CoRR_ abs/1905.06169, 2019  arXiv:1905.06169
  * [4] Dominic Breuker, Martin Matzner, Patrick Delfmann and Jörg Becker  “Comprehensible Predictive Models for Business Processes.”  In _MIS Q._ 40.4, 2016
  * [5] Manuel Camargo, Marlon Dumas and Oscar González-Rojas  “Learning accurate LSTM models of business processes”  In _Business Process Management_ , 2019  Springer
  * [6] Malu Castellanos, Fabio Casati, Umeshwar Dayal and Ming-Chien Shan  “A comprehensive and automated approach to intelligent business processes execution analysis”  In _Distributed and Parallel Databases_ 16.3 Springer, 2004
  * [7] Xiao Ding, Yue Zhang, Ting Liu and Junwen Duan  “Deep learning for event-driven stock prediction”  In _Twenty-fourth Int. joint Conf. on artificial intelligence_ AAAI Press, 2015
  * [8] S. Esser and Dirk Fahland  “Using graph data structures for event logs” Report of a Capita Selecta research project., 2019  DOI: 10.5281/zenodo.3333831
  * [9] Joerg Evermann, Jana-Rebecca Rehse and Peter Fettke  “A deep learning approach for predicting process behaviour at runtime”  In _Business Process Management_ , 2016  Springer
  * [10] Lukas Galke, Benedikt Franke, Tobias Zielke and Ansgar Scherp  “Lifelong Learning of Graph Neural Networks for Open-World Node Classification”  In _International Joint Conference on Neural Network_ IEEE, 2021
  * [11] Lukas Galke, Florian Mai, Iacopo Vagliano and Ansgar Scherp  “Multi-Modal Adversarial Autoencoders for Recommendations of Citations and Subject Labels”  In _Proceedings of the 26th Conf. on User Modeling, Adaptation and Personalization, UMAP 2018, Singapore, July 08-11, 2018_ ACM, 2018
  * [12] Chris Godsil and Gordon F Royle  “Algebraic graph theory”  Springer, 2013
  * [13] Diederik P. Kingma and Jimmy Ba  “Adam: A Method for Stochastic Optimization”  In _ICLR_ , 2015
  * [14] Thomas N. Kipf and Max Welling  “Semi-Supervised Classification with Graph Convolutional Networks”  In _ICLR_ OpenReview.net, 2017
  * [15] Li Lin, Lijie Wen and Jianmin Wang  “MM-PRED: A deep predictive model for multi-attribute event sequence”  In _Data Mining_ SIAM, 2019
  * [16] Fabrizio Maria Maggi, Chiara Di Francescomarino, Marlon Dumas and Chiara Ghidini  “Predictive monitoring of business processes”  In _Advanced information systems engineering_ , 2014  Springer
  * [17] Florian Mai, Lukas Galke and Ansgar Scherp  “Using Deep Learning for Title-Based Semantic Subject Indexing to Reach Competitive Performance to Full-Text”  In _JCDL_ ACM, 2018
  * [18] Alfonso Eduardo Márquez-Chamorro, Manuel Resinas and Antonio Ruiz-Cortes  “Predictive monitoring of business processes: a survey”  In _IEEE Transactions on Services Computing_ 11.6 IEEE, 2017
  * [19] Laura Maruster, AJMM Ton Weijters, WMP Wil Van der Aalst and Antal Bosch  “Process mining: Discovering direct successors in process logs”  In _Discovery Science_ , 2002  Springer
  * [20] Vincenzo Pasquadibisceglie, Annalisa Appice, Giovanna Castellano and Donato Malerba  “Using convolutional neural networks for predictive process analytics”  In _ICPM_ , 2019  IEEE
  * [21] Andreas Rogge-Solti and Mathias Weske  “Prediction of remaining service execution time using stochastic petri nets with arbitrary firing delays”  In _Service-oriented computing_ , 2013  Springer
  * [22] Franco Scarselli et al.  “The graph neural network model”  In _IEEE Transactions on Neural Networks_ 20.1 IEEE, 2008
  * [23] Niek Tax, Ilya Verenich, Marcello La Rosa and Marlon Dumas  “Predictive business process monitoring with LSTM neural networks”  In _Advanced Information Systems Engineering_ , 2017  Springer
  * [24] Paul N Taylor  “Customer Contact Journey Prediction”  In _Innovative Techniques and Applications of Artificial Intelligence_ , 2017  Springer
  * [25] Farbod Taymouri et al.  “Predictive Business Process Monitoring via Generative Adversarial Nets: The Case of Next Event Prediction”  In _BPM_ Springer, 2020
  * [26] Irene Teinemaa, Marlon Dumas, Fabrizio Maria Maggi and Chiara Di Francescomarino  “Predictive business process monitoring with structured and unstructured data”  In _Business Process Management_ , 2016  Springer
  * [27] Wil Van Der Aalst  “Data science in action”  In _Process mining_ Springer, 2016
  * [28] Wil MP Van der Aalst, M Helen Schonenberg and Minseok Song  “Time prediction based on process mining”  In _Information systems_ 36.2 Elsevier, 2011
  * [29] Wil MP Van Der Aalst et al.  “Business process mining: An industrial application”  In _Information Systems_ 32.5 Elsevier, 2007
  * [30] Wil MP Van der Aalst et al.  “Workflow mining: A survey of issues and approaches”  In _Data & knowledge engineering_ 47.2 Elsevier, 2003
  * [31] Zonghan Wu et al.  “A comprehensive survey on graph neural networks”  In _IEEE Transactions on Neural Networks and Learning Systems_ IEEE, 2020
  * [32] Rex Ying et al.  “Graph convolutional neural networks for web-scale recommender systems”  In _KDD_ ACM, 2018
  * [33] Muhan Zhang and Yixin Chen  “Link prediction based on graph neural networks”  In _Advances in Neural Information Processing Systems_ , 2018