# Reformulation Techniques for Automated Planning:
A Systematic Review

DIAEDDIN ALARNAOUTI and GEORGE BARYANNIS and MAURO VALLATI
<EMAIL_ADDRESS>School of Computing &
Engineering, University of Huddersfield, HD1 3DH, Huddersfield, UK

###### Abstract

Automated planning is a prominent area of Artificial Intelligence, and an
important component for intelligent autonomous agents. A cornerstone of
domain-independent planning is the separation between planning logic, i.e. the
automated reasoning side, and the knowledge model, that encodes a formal
representation of domain knowledge needed to reason upon a given problem to
synthesise a solution plan. Such a separation enables the use of reformulation
techniques, which transform how a model is represented in order to improve the
efficiency of plan generation. Over the past decades, significant research
effort has been devoted to the design of reformulation techniques. In this
paper, we present a systematic review of the large body of work on
reformulation techniques for classical planning, aiming to provide a holistic
view of the field and to foster future research in the area. As a tangible
outcome, we provide a qualitative comparison of the existing classes of
techniques, that can help researchers gain an overview of their strengths and
weaknesses.

##  1 Introduction

Automated planning is a research discipline that addresses the problem of
generating a totally- or partially-ordered sequence of actions that transform
the environment from some initial state to a desired goal state. Within this
discipline, domain-independent planning refers to those approaches that keep
the knowledge model, the domain knowledge related to the problem at hand,
separate from planning logic, that enables automated reasoning to generate
plans. The development of domain-independent planners within the AI Planning
community facilitates the use of this “off-the-shelf” technology for a wide
range of applications, including UAV manoeuvring (Ramírez et al., 2018), space
exploration (Ai-Chang et al., 2004), and train dispatching (Cardellini et al.,
2021). This is despite the complexity issues inherent in plan generation,
which are exacerbated by the separation of planner logic from domain
knowledge. On the other hand, this separation has the advantage that planning
engines can be interchanged in a modular way, provided that they accept the
same language for describing planning problems and deliver the same type of
plans.

This modular approach has fostered the development of planning engines, as
well as the design and exploitation of reformulation techniques. These refer
to the ability to automatically re-formulate, re-represent or tune the domain
model and/or a problem description, while keeping to the same input language,
in order to increase the efficiency of a planning engine and expand the scope
of problems solved (Riddle et al., 2011). The aim is to make these techniques
independent of domain and planner to some degree (that is, applicable to a
range of domains and planning engine technology), and use them to form a
wrapper around a planner, improving its overall performance for the particular
domain to which it is applied.

In the past few decades, a number of reformulation techniques have been
introduced. This is particularly true for classical planning which, despite
its intrinsic simplicity, provides an ideal ground to study and investigate
planning techniques that can then be extended beyond a specific framework. For
this reason, classical planning has been studied for several decades, and is
still a focal point of research within the automated planning community, as
evidenced by the papers devoted to it in the flagship conference, the
International Conference on Automated Planning and Scheduling (ICAPS)111The
interested reader is referred to the ICAPS website: https://www.icaps-
conference.org/ and by the number of papers focusing on knowledge engineering
for classical planning that are accepted at the Workshop on Knowledge
Engineering for Planning and Scheduling (KEPS).

In this paper, we systematically review the state of the art of reformulation
techniques for classical planning, with the aim of providing a holistic view
of the field and answering the following research questions:

  * •

What reformulation techniques have been proposed in literature?

  * •

How can they be applied on an indicative planning problem?

  * •

What are the particular strengths and weaknesses of each individual
reformulation technique?

The main purpose of this review is to provide a qualitative comparison of the
existing reformulation approaches, with the aim of helping experts and
practitioners in identifying the most promising technique to be used, and to
highlight research gaps that can foster further research in the area. Note
that empirical analysis of the reviewed reformulation techniques is beyond the
scope of this work due to the high variability, among different papers, of
considered benchmarks, planning engines, and software/hardware infrastructure
(Bocchese et al., 2018).

The remainder of this paper is organised as follows. Section 2 the necessary
background on planning and reformulation, and we introduce an example domain
model to be used as a running example throughout the paper. Then, Section 3
describes the methodology used for this literature review. Section 4 is the
main part of the review, presenting the existing reformulation techniques, and
showing how they can be implemented on the running example. We then compare
the reviewed techniques in Section 5, while in Section 6 we briefly discuss
some reformulation techniques that target non-classical planning problems.
Finally, we provide conclusions and suggested directions for future research
in the area of reformulation techniques for automated planning.

##  2 Background

This section is devoted to providing the required background in terms of
automated classical planning, the Gripper domain model used as a running
example, and the notion of reformulation.

###  2.1 Classical Planning

Classical planning is concerned with finding a (partially or totally ordered)
sequence of actions transforming the static, deterministic and fully
observable environment from the given initial state to a desired goal state
(Ghallab et al., 2004).

In the classical representation, a planning task consists of a planning domain
model and a planning problem, where the planning domain model describes the
environment and defines planning operators while the planning problem defines
concrete objects, an initial state and a set of goals. The environment is
described by predicates that are specified via a unique identifier and terms
(variable symbols or constants).

Formally, a planning task is a pair $\Pi=(Dom_{\Pi},Prob_{\Pi})$ where a
planning domain model $Dom_{\Pi}=(P_{\Pi},Ops_{\Pi})$ is a pair consisting of
a finite set of predicates $P_{\Pi}$ and planning operators $Ops_{\Pi}$, and a
planning problem $Prob_{\Pi}=(Objs_{\Pi},I_{\Pi},G_{\Pi})$ is a triple
consisting of a finite set of objects $Objs_{\Pi}$, initial state $I_{\Pi}$
and goal $G_{\Pi}$.

Let $ats_{\Pi}$ be the set of all atoms that are formed from the predicates
$P_{\Pi}$ by applying all possible substitution mappings from the predicate
parameters (variable symbols) to the objects from $Objs_{\Pi}$. In other
words, an atom is an instance of a predicate (in this article, when we use the
term instance, we mean an instance that is fully ground). A state is a subset
of $ats_{\Pi}$, and the initial state $I_{\Pi}$ is a distinguished state. The
goal $G_{\Pi}$ is a non-empty subset of $ats_{\Pi}$, and a goal state is any
state that contains the goal $G_{\Pi}$. Note that the semantics of state
reflect the full observability of the environment; that is, for a state $s$,
atoms present in $s$ are assumed to be true in $s$, while atoms not present in
$s$ are assumed to be false in $s$.

Planning operators are “modifiers” of the environment. They consist of
preconditions, i.e., what must hold prior to an operator’s application, and
effects, i.e., what is changed after its application. We distinguish between
negative effects, i.e., what becomes false, and positive effects, i.e., what
becomes true after an operator’s application. Actions are instances of
planning operators, i.e., an operator’s parameters, as well as corresponding
variable symbols in its preconditions and effects, are substituted by objects
(constants). Planning operators capture general types of activities that can
be performed. While predicates can be instantiated to atoms to capture given
relations between concrete objects, planning operators can be instantiated to
actions to capture given activities between concrete objects.

A planning operator $o=(\mbox{\it name}(o),\mbox{\it pre}(o),\mbox{\it
eff}(o))$ is specified such that $\mbox{\it name}(o)=\mbox{\it
op\\_name}(x_{1},\dots,x_{k})$, where op_name is a unique identifier and
$x_{1},\dots,x_{k}$ are all the variable symbols (parameters) appearing in the
operator, $\mbox{\it pre}(o)$ is a set of predicates representing its
precondition, and $\mbox{\it eff}(o)$ represents its effects, divided into
$\mbox{\it eff}^{-}(o)$ and $\mbox{\it eff}^{+}(o)$ (i.e., $\mbox{\it
eff}(o)=\mbox{\it eff}^{-}(o)\cup\mbox{\it eff}^{+}(o)$) that are sets of
predicates representing the operator’s negative and positive effects,
respectively. Actions are instances of planning operators that are formed by
substituting objects, which are defined in a planning problem, for operators’
parameters as well as for the corresponding variable symbols in operators’
preconditions and effects. An action $a=(\mbox{\it pre}(a),\mbox{\it
eff}^{-}(a)\cup\mbox{\it eff}^{+}(a))$ is applicable in a state $s$ if and
only if $\mbox{\it pre}(a)\subseteq s$. Application of $a$ in $s$, if
possible, results in a state $(s\setminus\mbox{\it eff}^{-}(a))\cup\mbox{\it
eff}^{+}(a)$.

A solution of a planning task is a sequence of actions transforming the
environment from the given initial state to a goal state. A plan is a sequence
of actions. A plan is a solution of a planning task $\Pi$, a solution plan of
$\Pi$ in other words, if and only if a consecutive application of the actions
from the plan starting in the initial state of $\Pi$ results in the goal state
of $\Pi$.

The standardised language for describing classical planning tasks is PDDL
(McDermott, 2000), that was introduced in 1998 by the organisers of the first
International Planning Competition,222https://www.icaps-
conference.org/competitions/ building on top of STRIPS (Fikes and Nilsson,
1971) and the Action Description Language (ADL) (Pednault, 1987).

###  2.2 The Gripper Domain

As a running example in this paper, we consider the well-known Gripper domain
model, initially introduced in the first International Planning Competition in
1998 by Jana Kohler (McDermott, 2000). This domain was selected in this paper
because of its simplicity, and due to its suitability for being reformulated.
In a nutshell, the Gripper domain consists of a robot that has two grippers,
and is tasked to moved a number of balls between two rooms. The domain model
includes three operators:

Move:

to move the robot between rooms.

Pick:

to use a gripper to pick up a ball.

Drop:

to drop a ball that the robot is holding in one of its grippers.

Figure 1 shows the PDDL code of the domain model, including the relevant
predicates and the three mentioned operators. Figure 2 shows an example
Gripper planning problem, where the robot has 2 grippers, and has to move 4
balls between the considered rooms. The initial state defines the initial
position of balls and robot, and the initial status of the grippers. The goal
section specifies the desired goal position of the 4 balls.

    (:predicates (room ?r) (ball ?b) (gripper ?g) (at-robby ?r) (at ?b ?r) (free ?g) (carry ?o ?g))
    Ψ
    (:action move
           :parameters  (?from ?to)
           :precondition (and  (room ?from) (room ?to) (at-robby ?from))
           :effect (and  (at-robby ?to) (not (at-robby ?from))))

    (:action pick
           :parameters (?obj ?room ?gripper)
           :precondition  (and  (ball ?obj) (room ?room) (gripper ?gripper) (at ?obj ?room)
           ΨΨΨΨΨΨΨΨΨΨ(at-robby ?room) (free ?gripper))
           :effect (and (carry ?obj ?gripper) (not (at ?obj ?room) (not (free ?gripper))))

    (:action drop
           :parameters  (?obj  ?room ?gripper)
           :precondition  (and  (ball ?obj) (room ?room) (gripper ?gripper)
           (carry ?obj ?gripper) (at-robby ?room))
           :effect (and (at ?obj ?room) (free ?gripper)  (not (carry ?obj ?gripper))))

Figure 1: The Gripper PDDL domain model.

       (:objects rooma roomb ball4 ball3 ball2 ball1 left right)
       (:init (room rooma) (room roomb)
              (ball ball4) (ball ball3) (ball ball2) (ball ball1)
              (at-robby rooma)
              (free left) (free right)
              (at ball4 rooma) (at ball3 rooma) (at ball2 rooma) (at ball1 rooma)
              (gripper left) (gripper right))
       (:goal (and (at ball4 roomb) (at ball3 roomb) (at ball2 roomb) (at ball1 roomb)))

Figure 2: An example Gripper planning problem that consists of 4 balls to be
carried from rooma to roomb.

###  2.3 Reformulation in Domain-Independent planning

Taking a general perspective, reformulation is a term meaning a change to the
way in which one thinks about a problem, and it has been demonstrated to be a
common practice employed also by people to tackle challenging problems (Riddle
et al., 2013). A theoretical framework for describing reformulation schemes in
automated planning has been presented by Chrpa et al. (2012). Early research
in the area of reformulation in AI started in the 1960s (Amarel, 1968), and
reformulation has rapidly become a major field of research. In the field of
automated planning and, more general, of state-space search, reformulation is
intended as a change of representation. Different representations of the same
problem can result in different search spaces, and the use of reformulation
techniques can allow to make a problem more amenable for a considered planning
engine by providing a search space that is easier to be explored to find a
goal state.

Focusing on automated planning, the domain-independent paradigm decouples
reasoning from knowledge representation. This supports the use of
reformulation techniques which can re-formulate, re-represent or tune the
domain model and/or problem description, while keeping to the same input
language, in order to increase the efficiency of a planning engine and expand
the scope of problems solved. The idea is that these techniques are
independent from application domain and planning engines (that is, applicable
to a range of domains and planning engine technology), and use them to form a
wrapper around a planner, improving its overall performance for the domain to
which it is applied.

Figure 3:  An overview of the use of a domain- and planner-independent
reformulation technique.

Figure 3 gives an overview of the use of reformulation wrapper to modify the
representation of a planning task in a domain- and planner-independent way
that allows to reuse the same technique in any domain and with any engine that
supports the considered formal language. In this review, we focus on classical
planning reformulation approaches that aim at changing the representation of a
planning task within the same formal language, with the goal of making the
task more amenable for a given (class of) engines.

##  3 Review Methodology

This section is devoted to presenting the methodology used for performing the
literature review. To ensure deeper understanding of the reformulation
approaches that are applicable in domain-independent classical planning, we
applied a variation of the systematic literature review methodology as
proposed by Kitchenham and Charters (2017) for software engineering and
previously applied for reviews of AI-related literature (Baryannis et al.,
2019).

###  3.1 Search strategy

The collection of literature concerning reformulation techniques in classical
planning was performed through automated search using Google Scholar, Scopus
and the University of Huddersfield library search engine (Summon). Two levels
of keyword terms were utilised. On the first level, we used a disjunction (OR)
of the following three keyword phrases: “classical planning reformulation”,
“PDDL reformulation”, and “domain-independent reformulation”. On the basis of
the techniques identified using the aforementioned keyword phrases, we
provided a second level of keywords, to obtain all the relevant works for each
of them. This second-level search was with the following keywords linked to
one another by OR: “macro-operators”, “macro-actions”, “entanglements”,
“actions elimination”, “bagged representation, “action schema splitting”, and
“model configuration”.

The previously mentioned libraries were used equally as results vary between
them. The covered time period is set from 1980 to January 2022. Notably,
thanks to the introduction of the standardised PDDL language and the first
edition of the International Planning Competition in 1998, most of the
relevant work has been published after 2000.

To maximise coverage and completeness of the conducted search, two ancillary
procedures were included: (1) checking reference lists of select primary
studies (often referred to as backwards snowballing); and (2) identifying
existing literature reviews on automated planning that may include
reformulation (more details in Section 3.3).

###  3.2 Search scope

A series of inclusion and exclusion criteria frames the scope of this review,
to ensure quality and relevance of the selected works. First, studies must be
peer-reviewed and written in English. Then, they should contain a formal
description of at least one reformulation technique for automated planning
models, accompanied with an empirical analysis of the usefulness of the
proposed technique. Third, the proposed reformulation technique must be
domain-independent and must focus on classical planning. Fourth, the
reformulation must accept planning models as input, and provide as output
models that can be processed by domain-independent classical planning engines.
It should be noted that the last point excludes some well-known approaches
such as DISCOPLAN (Gerevini and Schubert, 1998) and TIM (Fox and Long, 1998),
that do not allow to include the extracted knowledge in planning models. While
the main focus of the review is on techniques for reformulating classical PDDL
lifted models, here we also include works proposed before the introduction of
the language, and that propose techniques for reformulating STRIPS (Fikes and
Nilsson, 1971) models; for the purposes of this review these can be considered
to be similar in nature to PDDL ones.

A search based on the keywords and the engines described in Section 3.1 yields
several thousands of results. By carefully and thoroughly applying all
aforementioned criteria and ancillary search strategies, and by considering
also abstracts of the identified studies, $54$ studies remain and are analysed
in the rest of this paper. For the sake of readability, the selected studies
are divided into different classes, presented in Section 4, according to the
reformulation approach that they present.

###  3.3 Related surveys

The main motivation behind this systematic review is the limited amount of
works covering the field of domain-independent reformulation for automated
planning. The most relevant published work is a survey of machine learning
methods for automated planning (Jiménez et al., 2012) where a section is
dedicated to macro-actions. This survey covers only 4 studies that are also
covered in this paper, published between 1977 and 2007. The work of Long et
al. (2002) provides a definition of reformulation for automated planning, and
briefly discusses some ways in which it has been applied in the field, though
it also includes cases not within the scope of this review. To the best of our
knowledge, this review is the first attempt at systematically analysing
reformulation approaches for automated planning.

##  4 Reformulation Techniques for Classical Planning

In this section we present the reviewed studies, classified according to the
implemented reformulation approach. For each approach, we also provide an
example of applying the reformulation approach to the Gripper domain.

###  4.1 Entanglements

The entanglements approach was firstly introduced in (Chrpa and Barták, 2009),
and aims at removing useless actions from a ground planning task, to reduce
the branching factor of a task at hand. Such useless actions are identified by
analysing the relationship between predicates of the problem, and operators.
In a nutshell, the idea is to change the representation of a planning task so
that only potentially useful actions can be grounded and considered during
search.

In literature, two main classes of entanglements have been proposed: outer and
inner. Outer entanglements (Chrpa and McCluskey, 2012; Chrpa et al., 2018)
identify useless actions on the basis of their relationships with predicates
from the initial state or the goal state. Inner entanglements (Chrpa et al.,
2019) focus instead on the relation between pairs of actions. There are two
types of inner entanglements: _entanglements by preceding_ , which defines the
case where a certain predicate is required by an operator as a precondition,
and _entanglements by succeeding_ , which denotes the case where a particular
operator makes a predicate available as one of its effects.

According to the results presented in (Chrpa et al., 2012), exactly finding
entanglements is as hard as solving the planning task itself. For this reason,
most of the work in literature focuses on approximate approaches for
identifying entanglement relations. To exemplify how entanglements can
reformulate a given planning task, here we show how the Gripper domain can be
modified by entanglements by init for the operator pick. The basis of
entanglement in this case for the particular encoding is that it is useful to
perform a pick action only on balls that are in the initial room. In any other
occasion, the pick action should not be considered. The relationship is
therefore captured by the (at ?b ?r) predicate, that indicates the position of
a ball and is a precondition of the considered operator. To implement the
entanglement, a new predicate $p^{\prime}$ (at-ent ?b ?r) should be created
and added to the domain model, having the same arguments of (at ?b ?r). The
pick operator should be modified by adding $p^{\prime}$ as a precondition. In
the initial state description of the problem, an additional $p^{\prime}$
predicate should be created for each existing (at ?b ?r). This is similar in
nature to the auxiliary predicate added to preconditions to account for
unforeseen circumstances to address the qualification problem in service
specifications (Baryannis et al., 2017; Baryannis and Plexousakis, 2013) An
excerpt of the modified domain and problem models is presented in Figure 4.

    (:predicates ... (at-ent ?obj ?room))
    ...
    (:action pick
           :parameters (?obj ?room ?gripper)
           :precondition  (and  (ball ?obj) (room ?room) (gripper ?gripper) (at ?obj ?room)
           (at-ent ?obj ?room) (at-robby ?room) (free ?gripper))
           :effect (and (carry ?obj ?gripper) (not (at ?obj ?room) (not (free ?gripper))))
    ...)
    ....
    (:init ... (at ball4 rooma) (at ball3 rooma) (at ball2 rooma) (at ball1 rooma) ...
    (at-ent ball4 rooma) (at-ent ball3 rooma) (at-ent ball2 rooma) (at-ent ball1 rooma))
    ...

Figure 4:  An excerpt of the modified Gripper planning task when the pick
operator is entangled by init on the basis of the at predicate.

###  4.2 Macro-Operators

Macro-operators (macros) represent a well-known and well-studied technique for
enhancing performance of planning engines. In a nutshell, macros encapsulate
sequences of (primitive) planning operators. Macros are encoded as ordinary
planning operators and, hence, they can be added into planning domain models.
Macros, informally speaking, provide short-cuts in the state space and,
consequently, planning engines can generate plans in a smaller number of
steps. This comes at the cost of an increased branching factor, since macros
often have many more instances than primitive operators and thus their use
might introduce additional overheads as well as larger memory requirements.

The notion of macros can be traced back to 1970s and 1980s. REFLECT (Dawson
and Siklossy, 1977) builds macros from pairs of primitive operators that can
be applied in sequence and share at least one argument. Macro Problem Solver
(Korf, 1985) is capable of learning macros for achieving particular non-
serialisable sub-goals (e.g. in Rubik’s cube). MORRIS (Minton, 1985) learns
macro-operators from parts of plans appearing frequently (S-macros) or being
potentially useful despite having low priority (T-macros). FM (McCluskey,
1987) learns sequences of operators frequently used together, and combines
them in potentially long sequences called chunks. MACLEARN (Iba, 1985, 1989)
is a heuristic approach for learning re-usable macros for solving puzzle
problems; the system includes three subcomponents that are in charge of
proposing promising macros and testing their usefulness for solving problems.

The first International Planning Competition, held in 1998, introduces PDDL
that became the ”de facto” standard language for planning models. The
introduction of a language supported the design and testing of approaches for
the generation and identification of macros, that started to thrive. MacroFF
(Botea et al., 2005), based on the well-known FF planning engine (Hoffmann and
Nebel, 2001), generates macros according to a number of pre-defined rules
(e.g., the “locality rule”) that apply on adjacent actions in training plans.
MacroFF is capable of generating planner-independent macros, that can be added
to domain models as standard operators, or planner-specific macros for FF,
that can be provided as additional input to the planning engine. DHG (Armano
et al., 2004) is able to learn macro-operators from static domain analysis by
exploring a graph of dependencies between operators. WIZARD (Newton and
Levine, 2007) is a framework that exploits genetic programming to create
macros; starting from the primitive operators of the domain model, WIZARD
leverages genetic algorithms to combine them into useful macros for a given
planning engine. Chrpa (2010b) propose an approach for identifying suitable
macros by looking at action dependencies in generated plans. Dulac et al.
(2013) propose to exploit n-gram algorithm to analyse training plans to
automatically learn macros.

DBMP/S (Hofmann et al., 2017) applies Map Reduce for learning macros from a
large training plan databases. More recently, the same authors propose an
approach for generating macros for ADL domain models, that includes PDDL
features that are rarely supported by more traditional methods (Hofmann et
al., 2020). CAP (Asai and Fukunaga, 2015) exploits component abstraction, that
allows to cluster together similar objects (introduced by MacroFF), for
generating sub-goal specific macros. In other words, CAP divides complex
planning problems into independent sub-problems by abstracting the components
of the original problem. Then it finds sub-plans for each sub-problem, and
connects the actions of every sub-plan into a solo macro operator. BloMa
(Chrpa and Siddiqui, 2015) leverages block deordering, which rearranges plans
into “blocks” that can no longer be deordered (Siddiqui and Haslum, 2012), for
generating longer macros. In particular, BloMa generates a large pool of
macros from “macroblocks”, which are derived from “blocks” by applying a set
of rules. Chrpa and Vallati (2019) introduce the idea of critical section
macros, that are inspired by parallel computing critical sections; such macros
aim at capturing a whole activity that deals with a limited resource (or more
limited resources). Finally, Castellanos-Paez et al. (2021a, b) introduce ERA,
an approach for extracting macros from plans that is based on pattern mining;
an important feature of ERA is its ability to identify macros even if the
included operators are not always adjacent in the considered plans.

A different line of work looks into exploiting the notion of entanglements to
identify promising macros. (Chrpa, 2010a) focuses on combining both macro-
operators and entanglements in order to get the benefit behind each of them,
as macros can reduce the size of the search space whereas the usage of
entanglements is capable of reducing the branching factor which may occur
because of the generated instances of macros. (Chrpa et al., 2013) propose an
automated approach that combine two primitive operators that are linked by
inner entanglement relationships, and leverages on such relationships to
eliminate one or both of the primitive operators from the domain model. MUM
(Chrpa et al., 2014) is a learning system that exploits outer entanglements as
heuristics in the process of generating macros. Macros generated by MUM have a
limited number of instances, specifically, the number of macro instances has
to be in the same order of magnitude as the number of primitive operator
instances. OMA (Chrpa et al., 2015b) is capable of generating macros online,
i.e. without the need for offline training, by considering entanglement
relations between operators of the domain model.

Notably, there is also a line of work that considers the problem of
identifying the best (set of) macros to be used, given an initial pool of
candidates. Alhossaini and Beck (2013) select problem-specific macros from a
given pool of macros (hand-coded or generated by another technique) using a
specifically trained predictor. ASAP (Vallati et al., 2013) uses a set of
provided training plans to identify the best combination of planning engine
and macro set (also considering entanglements) to be used on a given domain.
PbP (Gerevini et al., 2014) uses statistical tests to identify the most
promising portfolio of planning engines and macro actions to be used for
solving challenging planning instance. Finally, MeVo (Vallati et al., 2020),
given a large pool of macros, can evolve over time the best set of macros to
be used by a planning engine for solving a continuous stream of problems from
a considered domain. This features allows MeVo to overcome the issue of having
training instances that are not representative of the testing ones.

Technically speaking, the way in which a macro-operator is generated by
assembling two operators is straightforward and quite similar to the way
composition works in the case of services Baryannis and Plexousakis (2014).
Considering two operators $a_{i}$ and $a_{j}$, the resulting macro
encapsulating their execution in sequence can be generated as follows:

$pre\left(a_{i,j}\right)=Pre\left(a_{i}\right)\cup\left(Pre\left(a_{j}\right)\backslash
eff^{+}\left(a_{i}\right)\right)$

$eff^{-}\left(a_{i,j}\right)=\left(eff^{-}\left(a_{i}\right)\cup
eff^{-}\left(a_{j}\right)\right)\backslash eff^{+}\left(a_{j}\right)$

$eff^{+}\left(a_{i,j}\right)=\left(eff^{+}\left(a_{i}\right)\cup
eff^{+}\left(a_{j}\right)\right)\backslash eff^{-}\left(a_{j}\right)$

More than two operators can be encapsulated in a single macro by iteratively
repeating the described process. Figure 5 shows the macro-operator pick-move-
drop for the Gripper domain model. It has been generated by composing the
primitive operators pick, move, and drop, with the idea of providing a single
operator that can represent a whole movement of a ball from its initial
position to its goal position. It can be added to the original domain model,
and planning engines will take it into account when solving a given planning
task. Notably, the resulting plans may include the macro operator and
therefore, to be valid with regards to the original domain model, will need to
be parsed.

        (:action pick-move-drop
           :parameters (?from ?to ?obj ?gripper)
           :precondition (and  (ball ?obj) (gripper ?gripper)
                    (at ?obj ?from) (at-robby ?from) (free ?gripper)
                    (room ?from) (room ?to))
           :effect (and
                (not (at ?obj ?from))
                (not (at-robby ?from))
                (at ?obj ?to)
                (at-robby ?to)))Ψ

Figure 5: An example macro-operator that encapsulates the sequence of
operators pick(?obj ?from ?gripper), move(?from ?to), drop(?obj ?to ?gripper).
For the sake of clarity, we use the same name for matched variables between
operators.

###  4.3 Operators Elimination

Operators elimination aims at reducing the branching factor by removing from
the domain model those operators whose effects can be achieved by executing a
sequence of other operators. In a nutshell, the main point is to minimise the
size of the model by identifying operators that can be considered redundant.
It should of course be noted that it may not always be possible to remove
operators from a domain model. Haslum and Jonsson (2000) introduce a technique
for performing operators elimination, by formally defining the notions of a
redundant operator and of a minimal set of operators, also proposing a greedy
algorithm to identify the minimal set of operators for a given domain model.

Operators elimination may be of limited impact when used on its own,
particularly in the case of highly engineered domain models. However, it can
be particularly helpful when performed after another reformulation approach.
For instance, Chrpa and Barták (2009) discuss operators elimination after the
exploitation of entanglements, and there has been a large body of work
investigating the elimination of primitive operators that are encapsulated
into macros (e.g., (Chrpa and Vallati, 2019; Chrpa, 2010b; Alhossaini and
Beck, 2013)).

Considering the Gripper domain, in the original model shown in Figure 1 there
are no operators that are redundant and can be removed. However, if the domain
model is extended by adding the macro shown in Figure 5, then both pick and
drop operators can be removed without compromising solvability of problems
sharing the structure of the one shown in Figure 2 – i.e. where the goal is
not for the robot to hold a ball in its gripper.

###  4.4 Bagged Representation

In domain models encoded in PDDL, it is usually the case that each object is
uniquely identified, even if it is not important to distinguish between
objects. In the presence of large sets of objects, this can lead to an
explosion of the combinatorial problem, that needs to take into account the
specific information of each individual object. The bagged representation
reformulation addresses the above criticism: in cases where only the number of
objects is relevant, and it is not important to have the ability to
distinguish between objects, they can be represented as “bags” of identical
objects. The main advantage is to reduce the branching factor, by basically
pruning states that are identical but for the specific object.

Bagged representation was first introduced in 2013 (Riddle et al., 2013), and
then further extended by providing an in-depth analysis of its impact on well-
known benchmarks and automated techniques to perform the reformulation (Riddle
et al., 2015b, c, a, 2016).

When it comes to reformulating the Gripper domain model, objects of type ball
are an excellent candidate to be represented using bagged representation. It
is important to know their number in every room, but it is not important to
know which specific ball is where. Figure 6 presents an excerpt of the
reformulated domain and problem models. Objects of type ball are removed, and
are substituted by counters. The predicate count is used to record the number
of balls in a room. Predicate more is used to link together the different
possible values of a counter. This is required because in classical planning
there is no notion of numeric elements, so this allows to use Boolean
predicates such as more as counters. The reformulated operator pick is also
shown in Figure 6, with the main change being that it now updates the counter
of the room where it is applied. The drop operator (not shown in the figure)
is modified in a similar way. Finally, the problem model is reformulated by
removing the ball objects, appropriately setting the initial values of the
counters for the considered rooms, and expressing the goal in terms of the
number of balls that need to be in the final room.

    (:predicates ... (count ?b ?r ?n) (more ?n1 ?n2))

    (:action pick
        :parameters (?n1 ?n0 ?obj ?room ?gripper)
        :precondition (and (ball ?obj)(room ?room)
                (gripper ?gripper)(at-robby ?room)(free ?gripper)
                (more ?n1 ?n0)(count ?obj ?room ?n0))
        :effect (and (carry ?obj ?gripper)
            (not (count ?obj ?room ?n0))
            (count ?obj ?room ?n1)(not (free ?gripper))))
    ...)
    ....

    (:objects n4 n3 n2 n1 n0 rooma roomb ballX left right)
    (:init .... (ball ballX) (more n0 n1) (more n1 n2)(count ballX rooma n4)
    (count ballX roomb n0) ...)
    (:goal (count ballX roomb n4))
    )

Figure 6: An excerpt of the Gripper domain and problem models reformulated
using bagged representation for objects of the type ball.

###  4.5 Action Schema Splitting

The presence of operators with a large number of parameters can be problematic
for the grounding step of domain-independent planning engines, as they usually
have to instantiate all possible actions before filtering out those that are
irrelevant. The number of ground actions grows exponentially with the number
of parameters and the number of objects of the problem to solve. In order to
address this issue, the idea of action schema splitting (Areces et al., 2014)
is to split large operators into smaller ones (with regard to the number of
parameters). The main aim is to break the exponential growth by dividing
parameters between different operators. While the idea is intuitively easy,
its exploitation has a number of hidden issues to be taken into account. When
an operator is broken into two smaller operators, the order in which these two
operators are executed becomes important, as is to consider whether their
execution can be interleaved with different operators – that can change the
state of the world in some unexpected ways.

Considering the example Gripper domain model, in the original version of the
model there is no operator that is suitable to be split using the described
methodology. However, action schema splitting can be understood also as the
“opposite” of macro-operators and in fact, it can also be used to find
reformulations of models by first encapsulating primitive operators into
macros, and then splitting them in different ways. For this reason, to
exemplify the use of this technique, we consider the macro encapsulating pick,
move, drop operators shown in Figure 5 and we split it into two operators,
pick-move and drop. Figure 7 shows the resulting operators. It is worth
highlighting that the example also shows a drawback of the action schema
splitting technique, i.e. the fact that the resulting operators may have the
same number of parameters as the initial large operator.

       (:action drop
           :parameters  (?obj  ?room ?gripper)
           :precondition  (and  (ball ?obj) (room ?room) (gripper ?gripper)
    ΨΨΨ    (carry ?obj ?gripper) (at-robby ?room))
           :effect (and (at ?obj ?room) (free ?gripper) (not (carry ?obj ?gripper))))

        (:action pick-move
           :parameters (?obj ?from ?to ?gripper)
           :precondition  (and  (ball ?obj) (room ?from) (room ?to) (gripper ?gripper)
    ΨΨΨ    (at ?obj ?from) (at-robby ?from) (free ?gripper))
           :effect (and (carry ?obj ?gripper) (at-robby ?to) (not (at ?obj ?from))
    ΨΨ    (not (at-robby ?from)) (not (free ?gripper))))

Figure 7: Action Schema Splitting applied to the macro operator shown in
Figure 5, and resulting in two operators.

###  4.6 Domain Model Configuration

It is well known that the way in which elements of planning models are ordered
can have an impact on the performance of domain-independent planning engines
(Howe and Dahlman, 2002). In this context, the term elements can refer to
operators, pre and post conditions, predicate definitions, etc. for the domain
models; objects, initial and goal state predicates listing for problem
definitions.

The idea behind domain model configuration is to identify an ordering of
elements that can improve the performance of a considered domain-independent
planning engine. Vallati et al. (2015) introduce an approach that leverages on
algorithm configuration techniques to identify a suitable configuration of a
domain model to improve the performance of a planning engine. The work has
been subsequently extended (Vallati et al., 2021) to consider also cases where
macro-operators have to be added to the domain model. Vallati et al. (2017)
describe a method for the online reordering of domain models by means of
dedicated heuristics, based on aspects such as the number of preconditions,
number of effects, etc. In a different line of work, Vallati and Serina (2018)
explore the configuration of planning problem models, by considering a
structure called Planning Encoding Graph (PEG) (Serina, 2010) to produce
information that helps in creating the basis on which the reordering of
elements should be done. In a nutshell, the PEG can provide information about
how important some objects of the problem are based on their involvement in
predicates of both initial and goal descriptions. This knowledge can then be
exploited in the ordering of the predicates, according to the objects that
they deal with.

Considering the guidelines in (Vallati et al., 2015), there are no unpromising
operators that we may prefer to put last in the Gripper domain model. However,
following the introduced notion of directionality, we may change the ordering
of operators to pick, move, drop. In this way, the ordering of operators
follow the expected typical ordering of corresponding actions in solution
plans that has been demonstrated to be useful for a range of planning engines.

##  5 Qualitative Comparison

Having completed an overview of the existing literature on domain- and
planner-independent reformulation for classical planning, we are now able to
qualitatively compare the considered techniques. In fact, we will now focus on
the advantages and disadvantages of the reviewed techniques, with the aim of
providing useful guidelines for planning experts and practitioners in the
process of selecting a promising technique to be used to improve planning
performance on a domain of interest. Table 1 gives an overview of the reviewed
reformulation techniques in terms of their main advantages and the major
potential drawbacks.

Table 1: Qualitative comparison of the main strengths and weaknesses of the reviewed reformulation techniques. Reformulation Approach |  Benefits |  Drawbacks
---|---|---
Macro-Operators |  \- Reduce depth (reduce the transitions needed to reach goal states). |  \- Increase branching factor. \- Increase of the ground size.
Entanglements |  \- Reduce the branching factor. |  \- Potentially incomplete.
Actions Elimination |  \- Reduce the branching factor. |  \- Rarely applicable. \- Potentially incomplete.
Bagged Representation |  \- Reduce the branching factor. |  \- Only applicable when having indistinguishable numerable objects.
Action Schema Splitting |  \- Reduce the ground size of the problem. |  \- Potential increase of the branching factor.
Domain Model Configuration |  \- Ease the exploration of the search space. |  \- Can have limited impact if planners re-order elements internally. \- Potential reduction of performance if wrong ordering is used.

As indicated in Table 1, most reformulation techniques aim at making the
exploration of the search space easier by reducing the branching factor,
reducing the number of steps needed to reach a goal state, or reducing the
ground size of the problem to be solved. However, every technique has
potential drawbacks to be weighed in when deciding whether to exploit it.
Drawbacks range from the serious potential loss of completeness to a more
shallow limited impact on performance in the worst case. The use of macros can
boost the performance of a planning engine by reducing the number of steps
needed to reach a goal state, at the cost of a potentially significant
increase in terms of the branching factor and a larger ground problem.
Entanglements aim at reducing the branching factor and the ground size of a
problem by eliminating unpromising actions, but in doing so can remove some or
all of the paths to goal states. In a similar fashion, action elimination
directly reduces the ground size by eliminating operators deemed to be
useless, but on its own it is rarely applicable to well-formed domain models.
Further, if applied in an “aggressive” way, this may undermine completeness.
Bagged representation provides an elegant way to reduce branching factor by
removing the differences between objects, but it is again a technique that is
rarely applicable on its own. Action schema splitting aims at reducing the
ground size of a problem by splitting complex operators, but this comes at the
cost of increasing the branching factor. Finally, configuring a domain model
can help improve the performance of planning engines by listing the most
important planning elements first, but if used inappropriately it can also
lead to adverse effects.

It should be noted, however, that in many cases it is possible to combine
different techniques to maximise performance boost and mitigate drawbacks of
individual techniques (Vallati and Kitchin, 2020). As mentioned in previous
sections, macros are frequently combined with other reformulation techniques.
For instance, they have been used with entanglements (Chrpa et al., 2014),
with action elimination (Chrpa and Vallati, 2022), or with domain model
configuration (Vallati et al., 2021). While domain model configuration can be
straightforwardly combined with any other reformulation technique, the
combination of macros and entanglements can lead to significant performance
improvements, as entanglements are tackling the main drawback that is
associated with the use of macros, i.e. the branching factor.

The main take-home messages that can be diluted by the performed systematic
review of the literature, can be summarised as follows.

  * •

The majority of existing literature is dedicated to techniques for generating
macros, while comparatively limited effort has been devoted to investigating
alternative or different reformulation techniques. Admittedly, the planning
community should aim at expanding the spectrum of reformulation techniques as
much as possible, to foster their combination and the possibility to use them
fruitfully in large and challenging domain models –where they are needed the
most.

  * •

A substantial number of existing reformulation techniques aims at addressing
issues that are typical of planning engines that reason on the basis of a
ground representation. This focus is historically motivated, as domain-
independent planning engines traditionally ground the lifted PDDL
representation. However, as engines capable of reasoning with lifted or
partially ground representation are gaining momentum (see for instance (Horčík
and Fišer, 2021; Corrêa et al., 2020)), reformulations that are effective also
on lifted models can and should be investigated more convincingly.

  * •

On a similar note as the previous point, there is a lack of reformulations
that look into exploiting the potential synergies with planning approaches
that are based on compiling the planning problem into an equivalent SAT or ASP
problem to be solved. Given the fact that reformulations for such languages
have been proposed (see for instance (DODARO et al., 2022)), there may be
changes in PDDL models that can result in performance boost in the resulting
compiled instances.

  * •

A potentially interesting area to explore is the reformulation of problem
models. Existing techniques tend to have a strong focus on the domain model,
to be widely applicable on problems from the same domain. However, as planning
is more and more used in real-world applications, the complexity of problems
is increasing as well. Further, in some domains like urban traffic control
(McCluskey and Vallati, 2017) or energy network balancing (Piacentini et al.,
2013), large parts of the problem models remain the same between problems
(i.e. the network description); so it would we worth exploring if problem
models can benefit from a targeted reformulation.

  * •

We recognise that further work is needed to improve the usability of planning
techniques in real-world applications, as the main focus of existing
reformulation techniques is still on classical planning. However, as
demonstrated by a number of recent works, in many cases classical planning
reformulation approaches can be extended to, or provide inspiration for, non-
classical systems.

##  6 Beyond classical planning

In this review, we focused on reformulation techniques for classical planning.
However, it is worth mentioning that there is also a (limited) body of work
looking at reformulation for problems beyond classical planning. In this
section we provide an overview, by no means complete, of some of the
reformulation approaches introduced for planning problems beyond classical. On
the one hand, non-classical planning models include additional language
features that can complicate the reformulation process. Examples of languages
that have the expressive power to represent non-classical prolems include PDDL
2 (Fox and Long, 2003) and PDDL 3 (Gerevini et al., 2009), for numeric,
temporal planning and for encoding preferences; PDDL + (Fox and Long, 2006)
for mixed discrete-continuous problems, PPDDL (Younes and Littman, 2004) and
RDDL (Sanner, 2010) for probabilistic planning, and MA-PDDL (Kovács, 2012) for
multi-agent problems. On the other hand, it can be argued that non-classical
planning is needed in most real-world applications, and it is therefore
imperative to investigate techniques and approaches to boost planning
performance in such circumstances.

A line of research that looks into extending reformulation techniques for
classical planning to more expressive cases is that of Chrpa et al. (2015a),
which investigates the use of entanglements in numeric planning problems.
Specifically, the authors extend the notion of outer entanglements to allow
them to handle numeric variables. Similarly, Scala (2014) extended macros to
be used in the presence of numeric fluents. Finally, Franco et al. (2019)
present a technique to reduce the ground size of PDDL+ planning problems by
reducing the arity of sparse predicates, drawing a parallel to bagged
representation for classical planning.

A different line of research focuses instead on translating a planning model
from an original input language, to a different less-expressive one. The main
advantage of this approach is increasing the number of planning engines that
are able to reason upon the planning problem, and leverage existing robust
technologies devised for solving more restricted cases. Examples of this class
of reformulation approaches include (Percassi et al., 2021), that translates
PDDL+ problems into PDDL2.1 ones, (Grastien and Scala, 2020; Taig and Brafman,
2013) that provides approaches for translating of conformant planning problems
into classical problems, the re-representation of uncertainty in conformant
planning problems Palacios and Geffner (2009), the translation of complex
temporal aspects in PDDL2.1 (Cooper et al., 2010), and the removal from PDDL3
of soft trajectory constraints (Percassi and Gerevini, 2019).

##  7 Conclusion

Reformulation represents a well-known class of approaches for improving the
performance of domain-independent planning systems. The main idea is to re-
represent a given planning problem in a way that allows to increase the
efficiency of a selected planning engine to be used to solve the considered
problem or class of problems. In this paper, we reviewed the state of the art
of reformulation approaches for classical planning. We first presented in
detail the different techniques, and then took the opportunity to provide a
qualitative comparison of their expected benefits and drawbacks, with the aim
of providing some useful guidelines to select the most appropriate
reformulation to be used for a considered problem. Notably, the provided
comparison helps also in highlighting potentially fruitful combinations of
reformulation techniques. Finally, to emphasise the importance of
reformulation for planning models beyond classical, we briefly presented well-
known work in the area.

Mauro Vallati is supported by the UKRI Future Leaders Fellowship [grant number
MR/T041196/1].

## References

  * Ai-Chang et al. [2004] M. Ai-Chang, J. Bresina, L. Charest, A. Chase, J.-J. Hsu, A. Jonsson, B. Kanefsky, P. Morris, K. Rajan, J. Yglesias, et al.  Mapgen: mixed-initiative planning and scheduling for the mars exploration rover mission.  _IEEE Intelligent Systems_ , 19(1):8–12, 2004\.
  * Alhossaini and Beck [2013] M. Alhossaini and J. C. Beck.  Instance-specific remodelling of planning domains by adding macros and removing operators.  In _Tenth Symposium of Abstraction, Reformulation, and Approximation_ , 2013.
  * Amarel [1968] S. Amarel.  On representations of problems of reasoning about actions.  _Machine intelligence_ , 1968.
  * Areces et al. [2014] C. E. Areces, F. Bustos, M. Dominguez, and J. Hoffmann.  Optimizing planning domains by automatic action schema splitting.  In _Twenty-Fourth International Conference on Automated Planning and Scheduling_ , 2014.
  * Armano et al. [2004] G. Armano, G. Cherchi, and E. Vargiu.  Automatic generation of macro-operators from static domain analysis.  In _Proceedings of the 16th European Conference on Artificial Intelligence_ , pages 955–956, 2004.
  * Asai and Fukunaga [2015] M. Asai and A. Fukunaga.  Solving large-scale planning problems by decomposition and macro generation.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 25, pages 16–24, 2015.
  * Baryannis and Plexousakis [2013] G. Baryannis and D. Plexousakis.  WSSL: A Fluent Calculus-Based Language for Web Service Specifications.  In C. Salinesi, M. C. Norrie, and Ó. Pastor, editors, _25th International Conference on Advanced Information Systems Engineering (CAiSE 2013)_ , volume 7908 of _Lecture Notes in Computer Science_ , pages 256–271. Springer Berlin Heidelberg, 2013.  ISBN 978-3-642-38708-1.  10.1007/978-3-642-38709-8_17.
  * Baryannis and Plexousakis [2014] G. Baryannis and D. Plexousakis.  Fluent Calculus-based Semantic Web Service Composition and Verification using WSSL.  In A. Lomuscio et al., editors, _9th International Workshop on Semantic Web Enabled Software Engineering (SWESE2013), co-located with ICSOC 2013_ , volume 8377 of _Lecture Notes in Computer Science_ , pages 256–270. Springer International Publishing Switzerland, 2014.  10.1007/978-3-319-06859-6_23.
  * Baryannis et al. [2017] G. Baryannis, K. Kritikos, and D. Plexousakis.  A specification-based QoS-aware design framework for service-based applications.  _Service Oriented Computing and Applications_ , 11(3):301–314, 2017.  ISSN 1863-2394.  10.1007/s11761-017-0210-4.
  * Baryannis et al. [2019] G. Baryannis, S. Validi, S. Dani, and G. Antoniou.  Supply chain risk management and artificial intelligence: state of the art and future research directions.  _International Journal of Production Research_ , 57(7):2179–2202, 2019.  10.1080/00207543.2018.1530476.
  * Bocchese et al. [2018] A. F. Bocchese, C. Fawcett, M. Vallati, A. E. Gerevini, and H. H. Hoos.  Performance robustness of AI planners in the 2014 international planning competition.  _AI Commun._ , 31(6):445–463, 2018.
  * Botea et al. [2005] A. Botea, M. Enzenberger, M. Müller, and J. Schaeffer.  Macro-ff: Improving ai planning with automatically learned macro-operators.  _Journal of Artificial Intelligence Research_ , 24:581–621, 2005.
  * Cardellini et al. [2021] M. Cardellini, M. Maratea, M. Vallati, G. Boleto, and L. Oneto.  In-station train dispatching: a PDDL+ planning approach.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , pages 450–458, 2021.
  * Castellanos-Paez et al. [2021a] S. Castellanos-Paez, R. Rombourg, and P. Lalanda.  ERA: Extracting planning macro-operators from adjacent and non-adjacent sequences.  In _Pacific Rim Knowledge Acquisition Workshop_ , pages 30–45. Springer, 2021a.
  * Castellanos-Paez et al. [2021b] S. Castellanos-Paez, R. Rombourg, and P. Lalanda.  On the relevance of extracting macro-operators with non-adjacent actions: Does it matter?  In _13th International Conference on Agents and Artificial Intelligence_ , 2021b.
  * Chrpa [2010a] L. Chrpa.  Combining learning techniques for classical planning: Macro-operators and entanglements.  In _2010 22nd IEEE International Conference on Tools with Artificial Intelligence_ , volume 2, pages 79–86. IEEE, 2010a.
  * Chrpa [2010b] L. Chrpa.  Generation of macro-operators via investigation of action dependencies in plans.  _The Knowledge Engineering Review_ , 25(3):281–297, 2010b.
  * Chrpa and Barták [2009] L. Chrpa and R. Barták.  Reformulating planning problems by eliminating unpromising actions.  In _Eighth Symposium on Abstraction, Reformulation, and Approximation_ , 2009.
  * Chrpa and McCluskey [2012] L. Chrpa and T. L. McCluskey.  On exploiting structures of classical planning problems: Generalizing entanglements.  In _ECAI_ , pages 240–245, 2012.
  * Chrpa and Siddiqui [2015] L. Chrpa and F. H. Siddiqui.  Exploiting block deordering for improving planners efficiency.  In _Twenty-Fourth International Joint Conference on Artificial Intelligence_ , 2015.
  * Chrpa and Vallati [2019] L. Chrpa and M. Vallati.  Improving domain-independent planning via critical section macro-operators.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 7546–7553, 2019.
  * Chrpa and Vallati [2022] L. Chrpa and M. Vallati.  Planning with critical section macros: Theory and practice.  _Journal of Artificial Intelligence Research_ , 2022.
  * Chrpa et al. [2012] L. Chrpa, T. L. McCluskey, and H. Osborne.  Reformulating planning problems: A theoretical point of view.  In _25th International Florida Artificial Intelligence Research Society Conference_ , pages 14–19, 2012.
  * Chrpa et al. [2013] L. Chrpa, M. Vallati, T. L. McCluskey, and D. Kitchin.  Generating macro-operators by exploiting inner entanglements.  In _Tenth Symposium of Abstraction, Reformulation, and Approximation_ , 2013.
  * Chrpa et al. [2014] L. Chrpa, M. Vallati, and T. L. McCluskey.  Mum: A technique for maximising the utility of macro-operators by constrained generation and use.  In _Twenty-Fourth International Conference on Automated Planning and Scheduling_ , 2014.
  * Chrpa et al. [2015a] L. Chrpa, E. Scala, and M. Vallati.  Towards a reformulation based approach for efficient numeric planning: Numeric outer entanglements.  In _Eighth Annual Symposium on Combinatorial Search_ , 2015a.
  * Chrpa et al. [2015b] L. Chrpa, M. Vallati, and T. L. McCluskey.  On the online generation of effective macro-operators.  In _Twenty-Fourth International Joint Conference on Artificial Intelligence_ , 2015b.
  * Chrpa et al. [2018] L. Chrpa, M. Vallati, and T. L. McCluskey.  Outer entanglements: a general heuristic technique for improving the efficiency of planning algorithms.  _Journal of Experimental & Theoretical Artificial Intelligence_, 30(6):831–856, 2018.
  * Chrpa et al. [2019] L. Chrpa, M. Vallati, and T. L. McCluskey.  Inner entanglements: Narrowing the search in classical planning by problem reformulation.  _Computational Intelligence_ , 35(2):395–429, 2019.
  * Cooper et al. [2010] M. C. Cooper, F. Maris, and P. Régnier.  Compilation of a High-level Temporal Planning Language into PDDL 2.1.  In _2010 22nd IEEE International Conference on Tools with Artificial Intelligence_ , pages 181–188, 2010.
  * Corrêa et al. [2020] A. B. Corrêa, F. Pommerening, M. Helmert, and G. Frances.  Lifted successor generation using query optimization techniques.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 30, pages 80–89, 2020.
  * Dawson and Siklossy [1977] C. Dawson and L. Siklossy.  The role of preprocessing in problem solving systems: ” an ounce of reflection is worth a pound of backtracking”.  In _Proceedings of the 5th international joint conference on Artificial intelligence-Volume 1_ , pages 465–471, 1977.
  * DODARO et al. [2022] C. DODARO, M. MARATEA, and M. VALLATI.  On the configuration of more and less expressive logic programs.  _Theory and Practice of Logic Programming_ , page 1–29, 2022.  10.1017/S1471068422000096.
  * Dulac et al. [2013] A. Dulac, D. Pellier, H. Fiorino, and D. Janiszek.  Learning useful macro-actions for planning with n-grams.  In _2013 IEEE 25th International Conference on Tools with Artificial Intelligence_ , pages 803–810, 2013.
  * Fikes and Nilsson [1971] R. E. Fikes and N. J. Nilsson.  Strips: A new approach to the application of theorem proving to problem solving.  _Artificial intelligence_ , 2(3-4):189–208, 1971\.
  * Fox and Long [1998] M. Fox and D. Long.  The automatic inference of state invariants in TIM.  _J. Artif. Intell. Res._ , 9:367–421, 1998.
  * Fox and Long [2003] M. Fox and D. Long.  PDDL2.1: An extension to PDDL for expressing temporal planning domains.  _Journal of artificial intelligence research_ , 20:61–124, 2003.
  * Fox and Long [2006] M. Fox and D. Long.  Modelling mixed discrete-continuous domains for planning.  _Journal of Artificial Intelligence Research_ , 27:235–297, 2006.
  * Franco et al. [2019] S. Franco, M. Vallati, A. Lindsay, and T. L. McCluskey.  Improving planning performance in PDDL+ domains via automated predicate reformulation.  In _Computational Science - ICCS_ , pages 491–498, 2019.
  * Gerevini and Schubert [1998] A. Gerevini and L. Schubert.  Inferring state constraints for domain-independent planning.  In _Proceedings of the American Artificial Intelligence Conference, AAAI/IAAI_ , pages 905–912, 1998.
  * Gerevini et al. [2014] A. Gerevini, A. Saetti, and M. Vallati.  Planning through automatic portfolio configuration: The pbp approach.  _Journal of Artificial Intelligence Research_ , 50:639–696, 2014.
  * Gerevini et al. [2009] A. E. Gerevini, P. Haslum, D. Long, A. Saetti, and Y. Dimopoulos.  Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners.  _Artificial Intelligence_ , 173(5-6):619–668, 2009.
  * Ghallab et al. [2004] M. Ghallab, D. Nau, and P. Traverso.  _Automated Planning: theory and practice_.  Elsevier, 2004.
  * Grastien and Scala [2020] A. Grastien and E. Scala.  CPCES: A planning framework to solve conformant planning problems through a counterexample guided refinement.  _Artif. Intell._ , 284:103271, 2020.
  * Haslum and Jonsson [2000] P. Haslum and P. Jonsson.  Planning with reduced operator sets.  In _AIPS_ , pages 150–158, 2000.
  * Hoffmann and Nebel [2001] J. Hoffmann and B. Nebel.  The ff planning system: Fast plan generation through heuristic search.  _Journal of Artificial Intelligence Research_ , 14:253–302, 2001.
  * Hofmann et al. [2017] T. Hofmann, T. Niemueller, and G. Lakemeyer.  Initial results on generating macro actions from a plan database for planning on autonomous mobile robots.  In _Twenty-Seventh International Conference on Automated Planning and Scheduling_ , 2017.
  * Hofmann et al. [2020] T. Hofmann, T. Niemueller, and G. Lakemeyer.  Macro operator synthesis for adl domains.  In _ECAI 2020_ , pages 761–768. IOS Press, 2020.
  * Horčík and Fišer [2021] R. Horčík and D. Fišer.  Endomorphisms of lifted planning problems.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 31, pages 174–183, 2021.
  * Howe and Dahlman [2002] A. E. Howe and E. Dahlman.  A critical assessment of benchmark comparison in planning.  _Journal of Artificial Intelligence Research_ , 17:1–33, 2002.
  * Iba [1985] G. A. Iba.  Learning by discovering macros in puzzle solving.  In _Proceedings of the 9th International Joint Conference on Artificial Intelligence - Volume 1_ , page 640–642, 1985.
  * Iba [1989] G. A. Iba.  A heuristic approach to the discovery of macro-operators.  _Machine Learning_ , 3(4):285–317, 1989.
  * Jiménez et al. [2012] S. Jiménez, T. De La Rosa, S. Fernández, F. Fernández, and D. Borrajo.  A review of machine learning for automated planning.  _The Knowledge Engineering Review_ , 27(4):433–467, 2012.
  * Kitchenham and Charters [2017] B. Kitchenham and S. Charters.  Guidelines for performing systematic literature reviews in software engineering.  Technical Report EBSE-2007-01, EBSE Technical Report, 2017.
  * Korf [1985] R. E. Korf.  Macro-operators: A weak method for learning.  _Artificial intelligence_ , 26(1):35–77, 1985\.
  * Kovács [2012] D. L. Kovács.  A multi-agent extension of PDDL3.1.  In _Proceedings of the 3rd Workshop on the International Planning Competition (IPC), ICAPS-2012_ , pages 19–27, Atibaia, Sao Paulo, Brazil, 2012.
  * Long et al. [2002] D. Long, M. Fox, and M. Hamdi.  Reformulation in planning.  In _International Symposium on Abstraction, Reformulation, and Approximation_ , pages 18–32, 2002.
  * McCluskey [1987] T. L. McCluskey.  Combining weak learning heuristics in general problem solvers.  In _Proceedings of the 10th International Joint Conference on Artificial Intelligence - Volume 1_ , IJCAI’87, page 331–333, San Francisco, CA, USA, 1987. Morgan Kaufmann Publishers Inc.
  * McCluskey and Vallati [2017] T. L. McCluskey and M. Vallati.  Embedding automated planning within urban traffic management operations.  In _Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling, ICAPS_ , pages 391–399. AAAI Press, 2017\.
  * McDermott [2000] D. M. McDermott.  The 1998 ai planning systems competition.  _AI magazine_ , 21(2):35–35, 2000.
  * Minton [1985] S. Minton.  Selectively generalizing plans for problem-solving.  In _IJCAI_ , pages 596–599. Citeseer, 1985.
  * Newton and Levine [2007] M. H. Newton and J. Levine.  Wizard: Suggesting macro-actions comprehensively.  _Proceedings of the Doctoral Consortium held at ICAPS_ , 7, 2007.
  * Palacios and Geffner [2009] H. Palacios and H. Geffner.  Compiling uncertainty away in conformant planning problems with bounded width.  _Journal of Artificial Intelligence Research_ , 35:623–675, 2009.
  * Pednault [1987] E. P. Pednault.  Formulating multiagent, dynamic-world problems in the classical planning framework.  In _Reasoning about actions & plans_, pages 47–82. Elsevier, 1987\.
  * Percassi and Gerevini [2019] F. Percassi and A. E. Gerevini.  On compiling away PDDL3 soft trajectory constraints without using automata.  In _Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, ICAPS_ , pages 320–328, 2019.
  * Percassi et al. [2021] F. Percassi, E. Scala, and M. Vallati.  Translations from Discretised PDDL+ to Numeric Planning.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 31, pages 252–261, 2021.
  * Piacentini et al. [2013] C. Piacentini, V. Alimisis, M. Fox, and D. Long.  Combining a temporal planner with an external solver for the power balancing problem in an electricity network.  In _Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, ICAPS_. AAAI, 2013.
  * Ramírez et al. [2018] M. Ramírez, M. Papasimeon, N. Lipovetzky, L. Benke, T. Miller, A. R. Pearce, E. Scala, and M. Zamani.  Integrated hybrid planning and programmed control for real time UAV maneuvering.  In _Proceedings of AAMAS_ , pages 1318–1326, 2018.
  * Riddle et al. [2013] P. Riddle, M. Barley, and S. Franco.  Problem reformulation as meta-level search.  In _Proceedings of the Conference on Advances in Cognitive Systems_ , 2013.
  * Riddle et al. [2015a] P. Riddle, M. Barley, S. Franco, and J. Douglas.  Automated transformation of PDDL representations.  In _International Symposium on Combinatorial Search_ , 2015a.
  * Riddle et al. [2015b] P. Riddle, M. Barley, S. Franco, and J. Douglas.  Bagged representations in PDDL.  In _4th Workshop on the Intl Planning Competition_ , pages 17–23, 2015b.
  * Riddle et al. [2015c] P. Riddle, M. Barley, S. Franco, and J. Douglas.  Analysis of Bagged Representations in PDDL.  In _Workshop on Heuristics and Search for Domain-independent Planning_ , pages 17–23, 2015c.
  * Riddle et al. [2016] P. Riddle, J. Douglas, M. Barley, and S. Franco.  Improving performance by reformulating PDDL into a bagged representation.  In _Proceedings of the 8th Workshop on Heuristic Search for Domain-independent Planning (HSDIP@ ICAPS)_ , pages 28–36, 2016.
  * Riddle et al. [2011] P. J. Riddle, R. C. Holte, and M. W. Barley.  Does representation matter in the planning competition?  In _Ninth Symposium of Abstraction, Reformulation, and Approximation_ , 2011.
  * Sanner [2010] S. Sanner.  Relational dynamic influence diagram language (rddl): Language description.  _Unpublished ms. Australian National University_ , 32:27, 2010.
  * Scala [2014] E. Scala.  Plan Repair for Resource Constrained Tasks via Numeric Macro Actions.  In _Proceedings of the Twenty-Fourth International Conferenc on International Conference on Automated Planning and Scheduling_ , ICAPS’14, page 280–288. AAAI Press, 2014.  ISBN 9781577356608.
  * Serina [2010] I. Serina.  Kernel functions for case-based planning.  _Artificial Intelligence_ , 174(16-17):1369–1406, 2010.
  * Siddiqui and Haslum [2012] F. H. Siddiqui and P. Haslum.  Block-structured plan deordering.  In _Australasian Joint Conference on Artificial Intelligence_ , pages 803–814, 2012.
  * Taig and Brafman [2013] R. Taig and R. I. Brafman.  Compiling conformant probabilistic planning problems into classical planning.  In _Twenty-Third International Conference on Automated Planning and Scheduling_ , 2013.
  * Vallati and Kitchin [2020] M. Vallati and D. Kitchin.  _Knowledge Engineering Tools and Techniques for AI Planning_.  Springer, 2020.
  * Vallati and Serina [2018] M. Vallati and I. Serina.  A general approach for configuring PDDL problem models.  In _Twenty-Eighth International Conference on Automated Planning and Scheduling_ , 2018.
  * Vallati et al. [2013] M. Vallati, L. Chrpa, and D. Kitchin.  An automatic algorithm selection approach for planning.  In _2013 IEEE 25th International Conference on Tools with Artificial Intelligence_ , pages 1–8. IEEE, 2013.
  * Vallati et al. [2015] M. Vallati, F. Hutter, L. Chrpa, and T. L. McCluskey.  On the effective configuration of planning domain models.  In _Twenty-Fourth International Joint Conference on Artificial Intelligence_ , 2015.
  * Vallati et al. [2017] M. Vallati, L. Chrpa, and T. McCluskey.  Improving a planner’s performance through online heuristic configuration of domain models.  In _Proceedings of the 10th International Symposium on Combinatorial Search (SoCS 2017)_ , pages 171–172, 2017.
  * Vallati et al. [2020] M. Vallati, L. Chrpa, and I. Serina.  Mevo: a framework for effective macro sets evolution.  _Journal of Experimental & Theoretical Artificial Intelligence_, 32(4):685–703, 2020.
  * Vallati et al. [2021] M. Vallati, L. Chrpa, T. L. McCluskey, and F. Hutter.  On the importance of domain model configuration for automated planning engines.  _Journal of Automated Reasoning_ , 65(6):727–773, 2021.
  * Younes and Littman [2004] H. L. Younes and M. L. Littman.  PPDDL1.0: An extension to PDDL for expressing planning domains with probabilistic effects.  _Techn. Rep. CMU-CS-04-162_ , 2:99, 2004.


# Automated Small Kidney Cancer Detection in Non-Contrast Computed Tomography

William McGough∗,1,2 Thomas Buddenkotte3,4 Stephan Ursprung2,5,6
Zeyu Gao1,2 Grant D. Stewart2,6,7 Mireia Crispin-Ortuzar1,2 ⋆ Corresponding
Author<EMAIL_ADDRESS>
###### Abstract

This study introduces an automated pipeline for renal cancer (RC) detection in
non-contrast computed tomography (NCCT). In the development of our pipeline,
we test three detections models: a shape model, a 2D-, and a 3D axial-sample
model. Training (n=1348) and testing (n=64) data were gathered from open
sources (KiTS23, Abdomen1k, CT-ORG) and Cambridge University Hospital (CUH).
Results from cross-validation and testing revealed that the 2D axial sample
model had the highest small ($\leq$40mm diameter) RC detection area under the
curve (AUC) of 0.804. Our pipeline achieves 61.9% sensitivity and 92.7%
specificity for small kidney cancers on unseen test data. Our results are much
more accurate than previous attempts to automatically detect small renal
cancers in NCCT, the most likely imaging modality for RC screening. This
pipeline offers a promising advance that may enable screening for kidney
cancers.

Cancer Detection, Segmentation, Deep Learning, Radiology

##  1 Introduction

RC is a significant global health concern, with 342,000 cases and 132,000
deaths recorded worldwide in 2016[1], and it is most commonly detected in CT
scans of the abdomen. Detecting RC early improves survival rates[2], and
previous studies have indicated the benefits of using NCCT for cancer
screening. However, the high economic cost of radiological personnel limits
the practicality of CT-based screening for diseases with less distinguishable
risk factors, such as RC[3]. The development of an automated RC detection
system would reduce the cost of diagnosis and reduce patient processing time,
potentially enabling RC screening.

One of the key objectives of an automated cancer detection system, especially
in the context of screening, is the ability to identify small cancers.
Detecting RC at a smaller size is associated with reduced mortality rates[4],
yet, surprisingly, the ability of automated detection systems to detect
smaller RCs in a suitable imaging mode for screening has received limited
attention in existing research. Small RC detection via NCCT has previously
involved the application of pretrained deep-learning classifiers to 2D axial
samples from CT or MRI scans[5, 6]. This approach works well in contrast-
enhanced CT (CECT), where textural information is rich in the axial samples of
CECT scans (AUC 0.846), but previous experiments have reported reduced
accuracy in NCCT where textural information is degraded (AUC 0.562)[6].
Alternatively, it is possible to detect small RCs in CECT with a purely 3D
segmentation approach (AUC 0.93)[7]. Elsewhere, lung cancer detection in NCCT
is highly effective when using a model that exploits 3D information within the
scan (AUC 0.959)[8].

We present what we believe to be the first end-to-end automated RC detection
system optimised for NCCT, the most likely imaging modality for RC screening.
We use this system to show that detection of small renal cancers is possible
using a 2D deep-learning image classifier in non-contrast CT, if the data
preparation methodology is designed appropriately. We also test how 3D image
classifiers and shape ensemble classifiers fare in small cancer detection in
NCCT.

##  2 Method

Our end-to-end pipeline is shown in Fig. 1; we describe each component of this
pipeline in the following section.

Figure 1: Our pipeline for automatic RC detection in NCCT. We show both the
shape model and axial sample models occupying the pipeline’s detection phase
for illustrative purposes; in fully-automated inference, only one detection
model is used at a time.

###  2.1 Segmentation and Object Generation

For automatic kidney segmentation, we used a 3DU-Net model - a deep-learning
architecture specifically designed for volumetric segmentation tasks. We used
a 6-stage 3DU-Net, with 32 33 convolutional filters in the first block,
doubling sequentially until 1024 filters in the bottom block. Our 3DU-Net was
trained to generated binary inferences; 1 for all tissue within the kidney
contour (kidney, tumour, or cyst), and 0 for background. The 3DU-Net model was
trained using the nnU-Net framework[9]. To generate object files for each
kidney, we ran a marching cubes algorithm (using python package Scikit-Image)
over the segmentation inference of each kidney, generating a set of vertices,
edges, and faces. Then, these objects were sparsified and smoothed using
Blender’s Python API, using the remesh method with a voxel size 1.2, and
smooth method with factor 0.5 and 5 iterations.

###  2.2 Shape Ensemble

The shape ensemble aims to detect cancers purely using 3D spatial information
extraced from the kidney object files. Our motivation for training a shape
model was to enable the detection of exophytic tumours that we observed being
missed by the 2D axial model. The shape ensemble consists of two distinct
components: a multilayer perceptron (MLP) and a graph neural network (GNN).

The GNN is a neural network that operates on graph-structured data. The GNN
takes as input a graph representing the kidney’s surface, which are generated
using the vertices and edges of the kidney object. Each vertex in the graph
contains a 4-element vector; 3 spatial coordinates and a value for curvature.
Curvature was calculated using the dot product of the difference between the
neighbouring vertices’ normal vectors and coordinate values, using the
following equations

$\displaystyle
C_{e,ij}=\frac{(\overrightarrow{n_{i}}-\overrightarrow{n_{j}})\cdot\overrightarrow{v_{i}}-\overrightarrow{v_{j}}}{|\overrightarrow{v_{i}}-\overrightarrow{v_{j}}|+\epsilon},$
(1)

$\displaystyle
C_{v}=\frac{\sum_{j=1}^{N_{i}-1}\theta_{i,(j,j+1)}(C_{e,ij}+C_{e,ij+1})}{2\sum_{j=1}^{N_{i}-1}\theta_{i,(j,j+1)}},$
(2)

where $C_{e,ij}$ is the curvature of the edge connecting nodes $i$ and $j$,
$C_{v}$ is a node’s curvature value, $\overrightarrow{n_{i}}$ is node $i$’s
normal vector, $\overrightarrow{v_{i}}$ is node $i$’s spatial coordinate
vector, $N_{i}$ is the number of neighbouring nodes to node $i$,
$\theta_{i,(j,j+1)}$ is the angle between neighbouring nodes $j$ and $j+1$
from the perspective of a reference node $i$, and $\epsilon$ is a small fixed
value; we used $10^{-6}$. The GNN is a sequential 5-layer graph convolutional
neural network, using Chebyshev convolutional layers with a filter width of 2
nodes and 25 dimensional latent feature space.

The MLP is a 3-layer fully connected neural network. Its input data are: a set
of shape descriptors (volume, maximum and minimum diameter, convexity; the
three eigenvalues from the inertia tensor of the segmented volume, and a
binary feature to indicate kidney location), a histogram of curvatures (taken
from the object graph, 10 bins between [-0.5,0.5]), and a histogram of kidney
attenuations (10 bins between [-20,80] Hounsfield Units (HU)), totalling 28
input features. All shape descriptors were extracted using the regionprops
function from Scikit-Image. To fuse the shape ensemble, we replace both
models’ final classification layer with a linear layer that projects each
model’s features into a common latent space. These features are added and fed
into a new, ensemble-wide classification layer, which allowed the whole
ensemble to be trained end-to-end.

###  2.3 Axial Sample Classifier

An axial sample model is a deep-learning image classifier, already implemented
in torchvision, retrained to identify RC from axial CT samples. Two versions
of the axial sample classifier were assessed: 2D and 3D. Both were pretrained
on KiTS23 CECT data and fine-tuned on a dataset of NCCT samples. In 2D, these
samples were of size 1x224x224 - we call these ‘tiles’. In 3D, samples were of
size 20x224x224 - we call these ‘blocks’. We jointly refer to tiles and blocks
as ‘samples’ where the distinction is unimportant.

Following benchmarking (see Table 1), we selected the top-2 architectures
(EfficientNet and ResNeXt) as backbones for our axial sample models. Both
architectures were expanded to 3D by converting all 2D PyTorch layers to 3D
via symmetric extension of all properties; for example, (3x3) kernels become
(3x3x3). Our 3D EfficientNet model was based on EfficientNet V2-L, but our 3D
ResNeXt model was based upon the smaller ResNeXt-50 32x8d, as expanding
ResNeXt to 3D increases parameter count roughly 50 times. To establish kidney-
wise cancer from sample inferences, we employed a sample voting method.
Specifically, we calculated the sum probability score across the most-probable
samples for each kidney. In 2D, we used the top-10 most probable tile scores.
In 3D, we used the top-1 most probable block score.

##  3 Experiments

###  3.1 Datasets

This research study used open access segmented data (KiTS23, Abdomen1k, CT-
ORG) and data made available from CUH. Ethical approval was only required for
CUH data, and it was gathered for all patients. Sample data were generated
from both the KiTS23 dataset and CUH data; KiTS23 contains 489 CECT scans, and
CUH data contains 92 paired CECT and NCCT scans. Segmentations were generated
for all CUH CECT scans via a segmentation 3DU-Net and a radiologist that
labelled renal tumours accurately. A subset of KiTS23 cases (110 cases) had
paired NCCT scans, sourced from the Climb 4 Kidney Cancer (C4RC) dataset. We
coregistered 79 NCCT scans to their equivalent CECT in KiTS23, and 45 from our
CUH dataset, generating 124 labelled NCCT scans - this is referred to as the
coregistered dataset (CD). The remaining unlabelled 47 NCCT scans from CUH are
combined with 17 NCCT non-cancerous cases (7 from Abdomen1K, 10 from CT-ORG),
sourced from open-source datasets, to form a test set.

For segmentation training, scans were converted into an isotropic voxel size
of 4mm, clipped to 0.05-99.5 percentile attenuation values, and attenuation-
normalised. To generate axial samples, we used 122 NCCT scans from the CD; two
patients with ‘horseshoe’ kidneys were excluded. Before sampling, each scan
was: converted into an isotropic voxel size of 1mm, attenuation-clipped
between [-200, 200] HU, normalised by dividing attenuation values by 100, and
masked by the kidney segmentation (dilated by 4cm).

Samples were taken from CT images using two schemes: centralised and sliding-
window. Centralised samples were central upon the kidney’s axial-plane
centroid. Sliding-window samples were sampled uniformly across the scans with
a 40x40mm axial-plane spacing. In both schemes, a 5mm out-of-plane spacing was
used in 3D, and 1mm in 2D. Samples were assigned a ‘cancerous’ label if their
respective segmentation contained a cancer region larger than 1cm radius;
else, ‘normal kidney’ if it contained a kidney region larger than 2cm radius;
otherwise, a ‘none’ label. A maximum of 50 sliding-window samples were taken
per-class, per-kidney. From the CD, 21,953 normal kidney, 10,296 cancerous,
and 28,186 none 2D tiles were generated, and 10,286 normal kidney, 7520
cancerous, and 9270 none 3D blocks were generated. From KiTS23, 73,167 normal
kidney, 33,635 cancerous, and 101,872 none 2D CECT tiles were generated, and
34,156 normal kidney, 25,294 cancerous, and 32,383 none 3D CECT blocks were
generated.

1011 kidney contours were sourced from KiTS23 and CD for the shape models to
train upon—we call this the shape dataset. All shape data were given a binary
label, either positive (distorted contour), or negative (normal). In training,
we avoided the cancer/non-cancer dichotomisation due to cysts in the training
data; shape models are naïve to the cause of contour perturbation. We used
label thresholding for the shape data to clarify the training signal and
improve model performance; if the kidney contours contained a cancer or cyst
above 500mm3, their graph label was positive, and if above 20000mm3, their MLP
feature set label was positive, too. When training the shape ensemble, we used
a common threshold of 500mm3. Label thresholds were selected in a
hyperparameter search maximising cross-validation AUC.

###  3.2 Training Overview

We trained all models in patient-wise 5-fold cross-validations, using the Adam
optimiser and cross-entropy loss function. All training was performed on
University of Cambridge’s Wilkes3 HPC and University of Birmingham’s
Baskerville HPC cluster, on NVIDIA A100 GPUs, using CUDA-backend PyTorch
v11.7, torchvision 0.15.2, and DGL 1.0.2 for GNNs.

Model Name | ResNet-152 | ResNeXt-101 32x8d | ConvNeXt-B | EfficientNet-V2-L | Swin-V2-B | ViT-B-32
---|---|---|---|---|---|---
Case-wise AUC | 0.810 | 0.827 | 0.807 | 0.837 | 0.596 | 0.752

Table 1: Results from benchmarking on the CD 2D tile dataset. Architecture
versions were selected by matching parameter count. All models were pretrained
on ImageNet-1k. Reported AUCs are the mean of 3 five-fold patient-wise cross-
validations.

####  3.2.1 Segmentation

We pretrained 3DU-Net on the combination of KiTS23, Abdomen1k and CT-ORG CECT
data (n=1303), removing NCCT cases, before fine-tuning on the CD. We trained
with a learning rate of 10-4, rising to 4x10-3 for pretraining and 5x10-4 for
fine-tuning, with 500 epochs for pretraining and 100 epochs for fine-tuning.
We used random rotations, flips, contrast- and blur-adjustment for data
augmentation. We used a batch size of 16; training inputs were randomly
sampled 643 voxel cubes; epoch length was 250 batches. We used a linear-ascent
exponential-decay schedule:

$\displaystyle LR(k)=\begin{cases}LR_{max}(\frac{k-1}{15})+LR_{min}&k\leq
15\\\ LR_{max}(e^{-a\frac{k-16}{k_{max}-k}})&k>15\end{cases}$ (3)

where $LR(k)$ is learning rate at epoch $k$, and $a$ is a decay constant;
$a=4$ for pretraining and $a=3$ for fine-tuning.

####  3.2.2 Shape Ensemble and Axial Sample Models

Both shape models were trained individually for 100 epochs; MLP learning rate
was 10-2, GNN learning rate was 10-3. After, we froze the individual models,
trained the ensemble’s shared layers for 30 epochs, before training all layers
for 2 epochs, with a learning rate of 10-3 and batch size of 8. We pretrained
both axial models on KiTS23 CECT data (5 epochs, learning rate of 1x10-3)
before finetuning on CD (5 epochs, learning rate of 5x10-4). We used a batch
size of 16 and the augmentation strategy from segmentation training.

Figure 2: Cross-validation performance for all models. Sample models were
evaluated over the CD following pretraining; shape models were evaluated over
the shape dataset.

###  3.3 Testing

In our test data, 47 patients had unilateral RC and 17 had healthy kidneys.
For each model (Shape, 2D, 3D), we calculated per-kidney detection sensitivity
and specificity and plot its receiver operating characteristic (ROC); for each
model type, inference was performed by summing the output from the 5 cross-
validation models. In axial sample models, inference was only applied to
‘centralised’ axial samples that contain a kidney region from the segmentation
inference.

Figure 3: Test performance of select models from cross-validation on unseen
test data (n=65).

##  4 Results and Discussion

The cross-validation Dice Similarity Coefficient of 3DU-Net was 90.13. Fig. 2
shows the cross-validation performance of each detection model; 2D
EfficientNet had the highest AUC (0.881). Fig. 2 shows that all axial models
perform similarly at high specificities, and the shape ensemble performs
better than either the MLP or GNN in isolation, validating the ensemble. Fig.
3 shows the test performance of each detection model; RC detection sensitivity
by all models is highly dependent upon size, with models detecting small RCs
with lower accuracy. Fig. 3 shows that cancer detection via the shape ensemble
is possible, but that both axial models considerably outperform this method,
especially for small RCs. The 2D model had the highest test AUC (0.921) and
detected small unseen RCs with 61.9% sensitivity and 92.7% specificity.

Possible reasons for the superiority of the 2D approach over the 3D approach
are: a greater volume of training samples (6.04x104 NCCT tiles; 2.70x104 NCCT
blocks), a higher labelling density in 2D (one label per 5x104 pixels in 2D; 1
label per 1x106 voxels in 3D), and the availability of ImageNet pretraining in
2D. The effect of many of these advantages would be reduced with a larger 3D
dataset. Possible reasons for the superiority of 2D model over previous
attempts[6] are: an improved deep-learning architecture (EfficientNet vs
Inception), pretraining in CECT, improved sampling scheme (using sliding-
window and centralised samples over kidney), and using nnU-Net’s augmentation
techniques. We note that our models had access to less training NCCT scans
(n=124) than this previous attempt (n=168).

##  5 Conclusion

We present an automated RC classification pipeline optimised for NCCT and
provide evidence of its efficacy in detecting small RCs. Our 2D tile model
(AUC 0.804) far exceeds previous attempts at detecting small RCs automatically
in NCCT (AUC 0.562), and may enable RC screening via NCCT.

##  6 Acknowledgments

The Baskerville HPC system that made this research possible is funded by the
EPSRC and UKRI through the World Class Labs scheme (EP/T022221/1) and the
Digital Research Infrastructure programme (EP/W032244/1) and is operated by
Advanced Research Computing at the University of Birmingham. This work was
supported by the Cancer Research UK Cambridge Centre [CTRQQR-2021/100012] and
the International Alliance for Cancer Early Detection, a partnership between
Cancer Research UK [C14478/A27855], Canary Center at Stanford University, the
University of Cambridge, OHSU Knight Cancer Institute, University College
London and the University of Manchester. This work was supported by The Mark
Foundation for Cancer Research [RG95043], the Cancer Research UK Cambridge
Centre [C9685/A25177 and CTRQQR-2021/100012] and NIHR Cambridge Biomedical
Research Centre (NIHR203312). The views expressed are those of the authors and
not necessarily those of the NHS, the NIHR or the Department of Health and
Social Care.

TB is a full-time employee at jung diagnostics. GDS has received educational
grants from Pfizer, AstraZeneca and Intuitive Surgical; consultancy fees from
Pfizer, MSD, EUSA Pharma and CMR Surgical; Travel expenses from MSD and
Pfizer; Speaker fees from Pfizer; Clinical lead (urology) of National Kidney
Cancer Audit and Topic Advisor for the NICE kidney cancer guideline. MCO is a
co-founder and CDO of 52 North Health.

##  7 Compliance with Ethical Standards

This research study was conducted retrospectively using human subject data
shared via open source and other data shared privately for research purposes.
This study was performed in line with the principles of the Declaration of
Helsinki. Approval was granted for use of the private research data by the
Human Biology Research Ethics Committee of University of Cambridge, on 25
April 2023.

## References

  * [1] Global Burden of Disease Cancer Collaboration,  “Global, Regional, and National Cancer Incidence, Mortality, Years of Life Lost, Years Lived With Disability, and Disability-Adjusted Life-Years for 29 Cancer Groups, 1990 to 2016: A Systematic Analysis for the Global Burden of Disease Study,”  JAMA Oncology, vol. 4, no. 11, pp. 1553–1568, 11 2018.
  * [2] Akira Tosaka, Kazuhiro Ohya, Kiyokathu Yamada, Hideyuki Ohashi, Satoshi Kitahara, Hideaki Sekine, Yasuaki Takehara, and Kaoru Oka,  “Incidence and properties of renal masses and asymptomatic renal cell carcinoma detected by abdominal ultrasonography,”  The Journal of Urology, vol. 144, no. 5, pp. 1097–1099, 1990.
  * [3] Juliet Usher-Smith, Rebecca K Simmons, Sabrina H Rossi, and Grant D Stewart,  “Current evidence on screening for renal cancer,”  Nature Reviews Urology, vol. 17, no. 11, pp. 637–642, 2020.
  * [4] John C Cheville, Christine M Lohse, Horst Zincke, Amy L Weaver, and Michael L Blute,  “Comparisons of outcome and prognostic features among histologic subtypes of renal cell carcinoma,”  The American journal of surgical pathology, vol. 27, no. 5, pp. 612–624, 2003.
  * [5] William C. McGough, Lorena E. Sanchez, Cathal McCague, Grant D. Stewart, Carola-Bibiane Schönlieb, Evis Sala, and Mireia Crispin-Ortuzar,  “Artificial intelligence for early detection of renal cancer in computed tomography: A review,”  Cambridge Prisms: Precision Medicine, vol. 1, pp. e4, 2023.
  * [6] Takashi Tanaka, Yong Huang, Yohei Marukawa, Yuka Tsuboi, Yoshihisa Masaoka, Katsuhide Kojima, Toshihiro Iguchi, Takao Hiraki, Hideo Gobara, Hiroyuki Yanai, Yasutomo Nasu, and Susumu Kanazawa,  “Differentiation of small ($\leq$ 4 cm) renal masses on multiphase contrast-enhanced ct by deep learning,”  American Journal of Roentgenology, vol. 214, no. 3, pp. 605–612, 2020,  PMID: 31913072.
  * [7] Naoki Toda, Masahiro Hashimoto, Yuki Arita, Hasnine Haque, Hirotaka Akita, Toshiaki Akashi, Hideo Gobara, Akihiro Nishie, Masahiro Yakami, Atsushi Nakamoto, et al.,  “Deep learning algorithm for fully automated detection of small ($\leq$ 4 cm) renal cell carcinoma in contrast-enhanced computed tomography using a multicenter database,”  Investigative radiology, vol. 57, no. 5, pp. 327–333, 2022.
  * [8] Diego Ardila, Atilla P Kiraly, Sujeeth Bharadwaj, Bokyung Choi, Joshua J Reicher, Lily Peng, Daniel Tse, Mozziyar Etemadi, Wenxing Ye, Greg Corrado, et al.,  “End-to-end lung cancer screening with three-dimensional deep learning on low-dose chest computed tomography,”  Nature medicine, vol. 25, no. 6, pp. 954–961, 2019.
  * [9] Jaeger P. F. Kohl S. A. Petersen J. & Maier-Hein K. H. Isensee, F.,  “nnu-net: a self-configuring method for deep learning-based biomedical image segmentation. nature methods,”  Nature Methods, vol. 18, pp. 203–211, 2021.