# Flexible FOND Planning with Explicit Fairness Assumptions∗

Ivan D. Rodriguez,1 Blai Bonet,1 Sebastian Sardiña,2 Hector Geffner1,3

###### Abstract

We consider the problem of reaching a propositional goal condition in fully-
observable non-deterministic (FOND) planning under a general class of fairness
assumptions that are given explicitly. The fairness assumptions are of the
form $A/B$ and say that state trajectories that contain infinite occurrences
of an action $a$ from $A$ in a state $s$ and finite occurrence of actions from
$B$, must also contain infinite occurrences of action $a$ in $s$ followed by
each one of its possible outcomes. The infinite trajectories that violate this
condition are deemed as _unfair,_ and the solutions are policies for which
_all the fair trajectories reach a goal state._ We show that strong and
strong-cyclic FOND planning, as well as QNP planning, a planning model
introduced recently for generalized planning, are all special cases of FOND
planning with fairness assumptions of this form which can also be combined.
FOND+ planning, as this form of planning is called, combines the syntax of
FOND planning with some of the versatility of LTL for expressing fairness
constraints. A new planner is implemented by reducing FOND+ planning to answer
set programs, and the performance of the planner is evaluated in comparison
with FOND and QNP planners, and LTL synthesis tools.00footnotetext: ∗This
paper is the long version of (Rodriguez et al. 2021).

## Introduction

FOND planning is planning with fully observable, non-deterministic state
models specified in compact form where a goal state is to be reached (Cimatti
et al. 2003). In its most common variant, strong-cyclic planning, one is
interested in policies that reach states from which the goal can be reached
following the policy (Cimatti, Roveri, and Traverso 1998a; Daniele, Traverso,
and Vardi 1999). In another common variant, strong planning (Cimatti, Roveri,
and Traverso 1998b), one is interested in policies that reach a goal state in
a bounded number of steps. Each form of FOND planning is adequate under a
suitable _fairness_ assumption; in the case of strong planning, that non-
determinism is adversarial (or “unfair”); in the case of strong-cyclic
planning, that non-determinism is fair, in that none of the possible outcomes
of a non-deterministic action can be skipped forever.

FOND planning has become increasingly important as a way of solving other
types of problems such as _probabilistic (MDP) planning_ , where actions have
a probabilistic effect on states (Bertsekas and Tsitsiklis 1996; Geffner and
Bonet 2013), _LTL planning_ , where goals to be reached are generalized to
temporal conditions that must be satisfied possibly by plans with cycles
(Calvanese, De Giacomo, and Vardi 2002; Camacho, Bienvenu, and McIlraith 2019;
Aminof et al. 2019), and _generalized planning_ , where plans are not for
single instances but for collections of instances (Srivastava, Immerman, and
Zilberstein 2011; Hu and De Giacomo 2011), and they can be obtained from
suitable abstractions encoded as QNP planning problems (Srivastava et al.
2011; Bonet and Geffner 2020).

A critical limitation of strong, strong-cyclic, and QNP planners, is that the
fairness assumptions are implicit in their models and solvers, and as a
result, cannot be combined. These combinations, however, are often needed
(Camacho and McIlraith 2016; Ciolek et al. 2020), and indeed, a recent FOND
planner handles combinations of fair and adversarial actions in what is called
_Dual FOND planning_ (Geffner and Geffner 2018). In this work, we go beyond
this integration by also enabling the representation and combination of the
conditional fairness assumptions that underlie QNP planning. This is achieved
by extending FOND planning with a general class of fairness assumptions that
are given explicitly as part of the problem. The fairness assumptions are
pairs $A/B$ of sets of actions $A$ and $B$ that say that state trajectories
that contain infinite occurrences of actions $a$ from $A$ in a state $s$, and
finite occurrences of actions from $B$, must also contain infinite occurrences
of action $a$ in the state $s$ followed by each one of its possible outcomes.
The infinite trajectories that violate this condition are regarded as
_unfair._ The solutions of a FOND problem with conditional fairness
assumptions of this type, called a FOND+ problem, are _the policies for which
all fair state trajectories reach the goal._

We show that strong, strong-cyclic, and QNP planning, are all special cases of
FOND+ planning where the fairness assumptions underlying these models can be
combined. FOND+ planning extends the syntax and semantics of FOND planning
with some of the versatility of the LTL language for expressing fairness
constraints. The conditional fairness assumptions $A/B$ correspond to the LTL
formulas $(\operatorname{\Box}\operatorname{\Diamond}(s\land
a)\land(\neg\operatorname{\Box}\operatorname{\Diamond}\bigvee_{b\in
B}b))\supset(\bigwedge_{i}\operatorname{\Box}\operatorname{\Diamond}(a\land
s\land\operatorname{\raisebox{-1.07639pt}{$\circ$}}\\!E_{i})$, one for each
action $a\in A$, each state $s$, and each possible outcome $E_{i}$ of the
action $a$, where $s$ stands for the conjunction of literals that $s$ makes
true. However, unlike LTL synthesis and planning that are 2EXP-Complete
(Pnueli and Rosner 1989; Camacho, Bienvenu, and McIlraith 2019; Aminof, De
Giacomo, and Rubin 2020), FOND+ planning is in NEXP (non-deterministic
exponential time).

A planner for FOND+ is obtained by reducing FOND+ planning over the explicit
state space to an elegant answer set program (ASP), a convenient and high-
level alternative to SAT (Brewka, Eiter, and Truszczyński 2011; Lifschitz
2019; Gebser et al. 2012), using the facilities provided by the clingo ASP
solver (Gebser et al. 2019). The performance of this ASP-based planner is
evaluated in comparison with FOND and QNP planners, and LTL synthesis tools.

The paper is organized as follows. We review first strong and strong-cyclic
FOND planning, and QNP planning. We introduce then FOND+ planning, where the
assumptions underlying these models are stated explicitly and combined, and
present a description of the ASP-based FOND+ planner, an empirical evaluation,
and a discussion.

## FOND Planning

A FOND model is a tuple $M=\langle S,s_{0},S_{G},Act,A,F\rangle$, where $S$ is
a finite set of states, $s_{0}\in S$ is the initial state, $S_{G}\subseteq S$
is a non-empty set of goal states, $Act$ is a set of actions, $F(a,s)$ is the
set of successor states when action $a$ is executed in state $s$, and
$A(s)\subseteq Act$ is the set of actions applicable in state $s$, such that
$a\in A(s)$ iff $F(a,s)\not=\emptyset$. A FOND problem $P$ is a compact
description of a FOND model $M(P)$ in terms of a finite set of atoms, so that
the states $s$ in $M(P)$ correspond to truth valuations over the atoms,
represented by the set of atoms that are true. The standard syntax for FOND
problems is a simple extension of the STRIPS syntax for classical planning. A
FOND problem is a tuple $P=\langle At,I,Act,G\rangle$ where $At$ is a set of
atoms, $I\subseteq At$ is the set of atoms true in the initial state $s_{0}$,
$G$ is the set of goal atoms, and $Act$ is a set of actions with atomic
preconditions and effects. If $E_{i}$ represents the set of positive and
negative effects of an action in the classical setting, action effects in FOND
planning can be deterministic of the form $E_{i}$, or non-deterministic of the
form $\text{{oneof}}(E_{1},\ldots,E_{n})$.

A policy $\pi$ for a FOND problem $P$ is a partial function mapping _non-goal_
states into actions. A policy $\pi$ for $P$ defines a set of, possibly
infinite, compatible state trajectories $s_{0},s_{1},s_{2},\ldots$, also
called $\pi$-trajectories, where $s_{i+1}\in F(a_{i},s_{i})$ and
$a_{i}=\pi(s_{i})$ for $i\geq 0$. A trajectory $\tau$ compatible with $\pi$ is
_maximal_ if it is infinite, or is finite of the form
$\tau=s_{0},\ldots,s_{n}$, for some $n\geq 0$, and either $s_{n}$ is the first
state in the sequence being a goal state, $\pi(s_{n})\not\in A(s_{n})$ (i.e.,
the action prescribed at $s_{n}$ is not applicable), or $\pi(s_{n})=\bot$
(i.e., no action is prescribed). Likewise, the policy $\pi$ reaches a state
$s$ if there is a $\pi$-trajectory $s_{0},\ldots,s_{n}$ where $s=s_{n}$, and
$\pi$ reaches a state $s^{\prime}$ from a state $s$ if there is a
$\pi$-trajectory $s_{0},\ldots,s_{n}$ where $s=s_{i}$ and $s^{\prime}=s_{j}$
for $0\leq i\leq j\leq n$. A state $s$ is recurrent in trajectory $\tau$ if it
appears an infinite number of times in $\tau$. The strong and strong-cyclic
solutions or policies are usually defined as follows:

######  Definition 1 (Solutions).

A policy $\pi$ is a strong solution for a FOND problem $P$ if all the maximal
$\pi$-trajectories reach a goal state, and it is a strong-cyclic solution if
$\pi$ reaches a goal state from any state reached by $\pi$.

The strong solutions correspond also to the strong-cyclic solutions that are
acyclic; namely, where the policies $\pi$ do not give rise to
$\pi$-trajectories that can visit a state more than once. Alternatively,
strong and strong-cyclic solutions can be understood in terms suitable notions
of fairness that establish which $\pi$-trajectories are deemed possible. If we
say that _a policy $\pi$ solves problem $P$ when all the fair
$\pi$-trajectories reach the goal_, then in strong planning, all
$\pi$-trajectories are deemed fair, while in strong-cyclic planning, all
$\pi$-trajectories are deemed fair _except_ those containing a recurrent state
$s$ that is followed a finite number of times by a successor $s^{\prime}\in
F(\pi(s),s)$.

In order to make this alternative “folk” characterization of strong and
strong-cyclic planning explicit, let us say that all the actions in strong
FOND planning are adversarial (or “unfair”), and that all the actions in
strong-cyclic FOND planning are fair. The state trajectories that are deemed
fair in each setting can then be expressed as follows:

######  Definition 2.

If all the actions are adversarial, all $\pi$-trajectories are fair. If all
the actions are fair, a $\pi$-trajectory $\tau$ is fair iff states $s$ that
occur an infinite number of times in $\tau$, are followed an infinite number
of times by each possible successor $s^{\prime}$ of $s$ given $\pi$,
$s^{\prime}\in F(\pi(s),s)$.

Provided with these notions of fairness, strong and strong-cyclic solutions
can be characterized equivalently as:

######  Theorem 3.

A policy $\pi$ is a strong (resp. strong-cyclic) solution of a FOND problem
$P$ iff all the fair trajectories compatible with $\pi$ in $P$ reach the goal,
under the assumption that all actions are adversarial (resp. fair).

###### Proof.

When all actions are adversarial, all trajectories are fair and the claim
follows directly. For strong-cyclic planning, observe that an infinite _fair_
trajectory $\tau$ visits each state that is reachable from any recurrent state
in $\tau$. We show the contrapositive of the two implications. If there is a
maximal fair trajectory that does not reach the goal, by the observation,
there is a state $s$ that is reachable from the initial state and that is not
connected to a goal; i.e., $\pi$ is not strong-cyclic. Conversely, if $\pi$ is
not strong-cyclic, there is a state $s$ that is reachable from the initial
state and that is not connected to the goal, and thus there is a maximal fair
trajectory that does not reach a goal; i.e., $\pi$ does not solve $P$. ∎

Methods for computing strong and strong-cyclic solutions for FOND problems
have been developed based on OBDDs (Cimatti et al. 2003), explicit forms of
AND/OR search (Mattmüller et al. 2010), classical planners (Muise, McIlraith,
and Beck 2012), and SAT (Chatterjee, Chmelík, and Davies 2016). Some of these
planners actually handle a combination of fair and adversarial actions, in
what is called Dual FOND planning (Geffner and Geffner 2018).

## QNP Planning

Qualitative numerical planning problems (QNPs) were introduced by Srivastava
et al. (2011) as a model for generalized planning, that is, planning for
multiple classical instances at once. QNPs have been used since in other works
(Bonet et al. 2017; Bonet, Frances, and Geffner 2019) and have been analyzed
in depth by Bonet and Geffner (2020).

The syntax of QNPs is an extension of STRIPS problems $P=\langle
At,I,O,G\rangle$ with negation where $At$ is a set of ground (boolean) atoms,
$I$ is a maximal consistent set of literals from $At$ describing the initial
situation, $G$ is a set of literals describing the goal situation, and $O$ is
a set of (ground) actions with precondition and effect literals. A QNP
$Q=\langle At,V,I,O,G\rangle$ extends a STRIPS problem with a set $V$ of
_numerical variables_ $X$ that can be decremented or incremented
_qualitatively_ ; i.e., by indeterminate positive amounts, without making the
variables negative. A numerical variable $X$ can appear in action effects as
$X\raisebox{0.6458pt}{$\uparrow$}$ (increments) and
$X\raisebox{0.6458pt}{$\downarrow$}$ (decrements),while literals of the form
$X{\,=\,}0$ or $X{\,>\,}0$ (an abbreviation of $X{\neq}0$) can appear
everywhere else (initial situation, preconditions, and goals). The literal
$X{\,>\,}0$ is a precondition of all actions with
$X\raisebox{0.6458pt}{$\downarrow$}$ effects.

A simple example of a QNP is $Q=\langle At,V,I,O,G\rangle$ with
$At=\left\\{p\right\\}$, $V=\left\\{n\right\\}$, $I=\left\\{\neg
p,n{\,>\,}0\right\\}$, $G=\left\\{n{\,=\,}0\right\\}$, and actions
$O=\left\\{a,b\right\\}$ given by

$a=\langle p,n{\,>\,}0;\neg
p,n\raisebox{0.6458pt}{$\downarrow$}\rangle\text{\quad and \quad}b=\langle\neg
p;p\rangle$

where $\langle C;E\rangle$ denotes an action with preconditions $C$ and
effects $E$. Thus action $a$ decrements $n$ and negates $p$ that is a
precondition of $a$, and $b$ restores $p$. This QNP represents an abstraction
of the problem of clearing a block $x$ in Blocksworld instances with
stack/unstack actions that include a block $x$. The numerical variable $n$
stands for the number of blocks above $x$, and the boolean variable $p$ stands
for the robot gripper being empty. A policy $\pi$ that solves $Q$ can be
expressed by the rules:

if $p$ and $n{\,>\,}0$, do $a$ and if $\neg p\land n{\,>\,}0$, do $b$ .

A key property of QNPs is that while numerical planning is undecidable
(Helmert 2002), qualitative numerical planning is not. Indeed, a sound and
complete, two-step method for solving QNPs was formulated by Srivastava et al.
(2011): the QNP $Q$ is converted into a standard FOND problem $P=T_{D}(Q)$ and
its (strong-cyclic) solution is checked for termination. The QNP solutions are
in correspondence with the strong-cyclic plans of the direct translation
$P=T_{D}(Q)$ that terminate. Moreover, since the number of policies that solve
$P$ is finite, and the termination of each can be verified in finite time,
plan existence for QNPs is decidable. More recent work has shown that the
complexity of QNP planning is the same as that of FOND planning by introducing
a polynomial reduction from the former into the latter, and another in the
opposite direction (Bonet and Geffner 2020).

We do not need to get into the formal details of QNPs but it is useful to
review the direct translation $T_{D}$ of a QNP $Q$ into a FOND problem
$P=T_{D}(Q)$, and the notion of termination (Srivastava et al. 2011).
Concretely, the translation $T_{D}$ replaces each numerical variable $n$ by a
boolean atom $p_{n}$ that stands for the (boolean) expression $n=0$. Then,
occurrences of the literal $n=0$ in the initial situation, action
preconditions, and goals are replaced by $p_{n}$, while occurrences of the
literal $n>0$ in the same contexts are replaced by $\neg p_{n}$. Likewise,
effects $n\raisebox{0.6458pt}{$\uparrow$}$ are replaced by effects $\neg
p_{n}$, and effects $n\raisebox{0.6458pt}{$\downarrow$}$ are replaced by non-
deterministic effects $\text{{oneof}}(p_{n},\neg p_{n})$. Actions in the FOND
problem $P=T_{D}(Q)$ with effects $\neg p_{n}$ (i.e., $n>0$) are said to
“increment $n$,” while actions with effects $\text{{oneof}}(p_{n},\neg p_{n})$
(i.e., either $n>0$ or $n=0$) are said to “decrement $n$,” even if there are
no numerical variables in $P$ but just boolean variables. This information
needs to be preserved in the translation $P=T_{D}(Q)$, as the semantics of $P$
is not the semantics of FOND problems as assumed by strong or strong-cyclic
planners.

## Termination and Sieve

A policy $\pi$ for the FOND problem $P=T_{D}(Q)$ is said to terminate if all
the state trajectories in $P$ that are compatible with the policy $\pi$ and
with the fairness assumptions underlying the QNP $Q$, are finite. Termination
is the result of the absence of cycles in the policy that could be traversed
forever. The latter arises when a cycle includes an action that decrements a
numerical variable and none that increments it. Since numerical variables
cannot become negative such cycles eventually terminate.

The procedure called Sieve (Srivastava et al. 2011) provides a sound and
complete termination test that runs in time that is polynomial in the number
of states reached by the policy. Sieve can be understood as an efficient
implementation of the following procedure that operates on a policy graph
$G(P,\pi)$ induced by the FOND problem $P$ and the policy $\pi$, where the
nodes are the states $s$ that can be reached in $P$ via the policy $\pi$, and
the edges correspond to the state transitions $(s,s^{\prime})$ that are
possible given the policy $\pi$ (i.e., $s^{\prime}\in F(\pi(s),s)$).

Starting with the graph $\mathcal{G}=G(P,\pi)$, Sieve iteratively removes
edges from $\mathcal{G}$ until $\mathcal{G}$ becomes acyclic or does not admit
further removals. In each iteration, an edge $(s,s^{\prime})$ is removed from
$\mathcal{G}$ if $\pi(s)$ is an action that decrements a variable $x$ that is
not incremented along any path in $\mathcal{G}$ from $s^{\prime}$ back to $s$.
Sieve accepts the policy $\pi$ iff Sieve renders the resulting graph
$\mathcal{G}$ acyclic. It can be shown that the resulting graph $\mathcal{G}$
is well defined (i.e., it is the same independently of the order in which
edges are removed), and that Sieve removes an edge $(s,s^{\prime})$ when it
cannot be traversed by the policy an infinite number of times.

It is useful to capture the logic of Sieve in terms of an inductive definition
that considers states instead of edges:

######  Definition 4 (QNP Termination).

Let $\pi$ be a policy for the FOND problem $P=T_{D}(Q)$ associated with the
QNP $Q$. The policy $\pi$ terminates in $P$ iff every state $s$ that is
reachable by $\pi$ in $P$ terminates, where a state $s$ terminates iff:111This
inductive definition and the ones below imply that there is a unique sequence
of state subsets $S_{0},S_{1},\ldots,S_{k}$ such that $S_{i+1}$ is $S_{i}$
augmented with all the states that can be added to $S_{i}$ when assuming that
the only terminating states are those in $S_{i}$.

  1. 1.

there is no cycle on node $s$ (i.e., no path from $s$ to itself),

  2. 2.

every cycle on $s$ contains a state $s^{\prime}$ that terminates, or

  3. 3.

$\pi(s)$ decrements a variable $x$, and every cycle on $s$ containing a state
$s^{\prime}$ for which $\pi(s^{\prime})$ increments $x$, also contains a state
$s^{\prime\prime}$ that terminates.

######  Theorem 5.

Let $Q$ be a QNPs and $\pi$ a policy. Then, Sieve accepts the policy graph
$G(P,\pi)$ iff policy $\pi$ terminates in $P$, where $P=T_{D}(Q)$.

###### Proof.

Since the resulting graph of executing Sieve does not depend on the order in
which edges are removed, we can consider any execution of Sieve.

Forward implication. Let $e_{0},e_{1},\ldots,e_{m}$ be the edge removed by
Sieve along some execution. We show by induction that the state $s_{i}$ in the
edge $Se_{i}=(s_{i},s^{\prime}_{i})$ removed by Sieve is terminating. Sieve
removes $e_{0}$ because $\pi(s_{0})$ decrements a variable $x$ and there is no
cycle involving $s_{0}$ with actions that increment $x$. If so, condition 3
applies, and $s$ must terminate. Let us assume that the claim holds for the
first $k$ iterations of Sieve, and let us consider the $k+1$-st iteration.
Edge $e_{k+1}$ is removed because $\pi(s_{k+1})$ decrements a variable $x$ and
there is no cycle, in the current graph, involving $s_{k+1}$ with actions that
increment $x$. That is, either there is no such cycle in the original graph,
or all such cycles have been “broken” by the removal of previous edges. Hence,
by inductive hypothesis, condition 3 applies again and $s$ must terminate.
Now, if the graph resulting from Sieve is acyclic, all states that have not
yet been labeled as terminating can be labeled as such using conditions 1 and
2. On the other hand, if the resulting graph is not acyclic, then it is easy
to show that the states in any such cycle cannot labeled as terminating.

Backward implication. Let $S_{0},S_{1},\ldots,S_{k}$ be the state subsets
associated with the inductive definition (cf. footnote 1). We construct an
execution $e_{0},e_{1},\ldots,e_{m}$ of Sieve. If $s$ in $S_{0}$, either there
is no cycle involving $s$ or $\pi(s)$ decrements a variable that is not
incremented along any cycle that involves $s$. In the latter case, Sieve
removes all edge $(s,s^{\prime})$. Let us assume that we have constructed an
execution of Sieve that removes all edges $(s,s^{\prime})$ for $s$ in
$S_{0}\cup S_{1}\cup\cdots\cup S_{i}$. If $s$ in $S_{i+1}$, either there is no
cycle involving $s$ or $\pi(s)$ decrements a variable $x$, and any any cycle
that involves $s$ and decrements $x$, has a state $s^{\prime}$ that has been
labeled as terminating. Then, using the inductive hypothesis, the current
execution of Sieve can be extended by the removal of all edge
$(s,s^{\prime})$. If all reachable states are labeled as terminating, the
constructed execution of Sieve renders an acyclic graph. On the other hand, if
some reachable state $s$ is not terminating, it can be shown that the
resulting graph has a cycle that involves $s$; i.e., it is not acyclic. ∎

Since solutions to QNPs $Q$ are known to be the strong-cyclic policies of the
FOND problem $P=T_{D}(Q)$ that are accepted by Sieve (Srivastava et al. 2011;
Bonet and Geffner 2020), the solutions for $Q$ can also be expressed as:

######  Theorem 6.

A policy $\pi$ is a solution to a QNP $Q$ iff $\pi$ is a strong-cyclic
solution of $P=T_{D}(Q)$ that terminates.

###### Proof.

The result is direct given that $\pi$ is a solution of $Q$ iff $\pi$ is a
strong-cyclic solution for $P$ accepted by Sieve (Srivastava et al. 2011;
Bonet and Geffner 2020), and the equivalence between Sieve acceptance and the
notion of policy termination in Theorem 5. ∎

The characterization that results from this theorem has been used to verify
QNP solutions but not for _computing_ them. Indeed, the only available
complete QNP planner is based on a polynomial reduction of QNP planning into
strong-cyclic FOND planning that avoids the termination test (Bonet and
Geffner 2020).

## FOND+ Planning

In this section, we move from strong, strong-cyclic, and QNP planning to the
FOND+ setting where the fairness assumptions underlying these models can be
explicitly stated and combined. A FOND+ planning problem $P_{c}=\langle
P,C\rangle$ is a FOND problem $P$ extended with a set $C$ of fairness
assumptions:

######  Definition 7.

A FOND+ problem $P_{c}=\langle P,C\rangle$ is a FOND problem $P$ extended with
a set $C$ of (conditional) fairness assumptions of the form $A_{i}/B_{i}$,
$i=1,\ldots,n$ and where each $A_{i}$ is a set of non-deterministic actions in
$P$, and each $B_{i}$ is a set of actions in $P$ disjoint from $A_{i}$.

The fairness assumptions play no role in constraining the state trajectories
that are possible by following a policy $\pi$, the so-called
$\pi$-trajectories:

######  Definition 8.

A state trajectory compatible with a policy $\pi$ for the FOND+ problem
$P_{c}=\langle P,C\rangle$ is a state trajectory that is compatible with $\pi$
in the FOND problem $P$.

However, while in strong and strong-cyclic FOND planning all actions are
considered as adversarial and fair, respectively, in the FOND+ setting, each
action is labeled fair or unfair depending on the assumptions in $C$ and the
trajectory where the action occurs. We define what it means for an action
$a=\pi(s)$ to behave “fairly” in a recurrent state $s$ of an infinite
$\pi$-trajectory as follows:

######  Definition 9.

The occurrence of the action $\pi(s)$ in a recurrent state $s$ of a
$\pi$-trajectory $\tau$ associated with the FOND+ problem $P_{c}=\langle
P,C\rangle$ is fair if for some fairness assumption $A/B\in C$, it is the case
that $\pi(s)\in A$ and all the actions in $B$ occur finitely often in $\tau$.

The meaning of a conditional fairness assumption $A/B$ is that the actions
$a\in A$ can be assumed to be fair in any recurrent state $s$ of a
$\pi$-trajectory $\tau$, provided that the condition on $B$ holds in $\tau$;
namely, that actions in $B$ do _not_ occur infinitely often in $\tau$.
Otherwise, if any action in $B$ occurs infinitely often in $\tau$, then $a$ is
said to be unfair or adversarial. Once actions $\pi(s)$ occurring in recurrent
states $s$ are “labeled” in this way, the standard notion of fair trajectories
(Definition 2) extends naturally to FOND+ problems:

######  Definition 10.

A $\pi$-trajectory $\tau$ for a FOND+ problem $P_{c}=\langle P,C\rangle$ is
fair if for every recurrent state $s$ in $\tau$ where the action $\pi(s)$ is
fair and every possible successor $s^{\prime}$ of $s$ due to action $\pi(s)$
(i.e., $s^{\prime}\in F(\pi(s),s)$), state $s$ is immediately followed by
state $s^{\prime}$ in $\tau$ an infinite number of times.

The solution of FOND+ problems can then be expressed in a standard way as
follows:

######  Definition 11 (Solutions).

A policy $\pi$ solves the FOND+ problem $P_{c}=\langle P,C\rangle$ if the
maximal $\pi$-trajectories that are fair reach the goal.

A number of observations can be drawn from these definitions. Let us say that
one wants to model a non-deterministic action $a$ whose behavior is fair in
that it always displays all its possible effects infinitely often in every
recurrent state $s$ such that $\pi(s)=a$. To do so, we consider a fairness
constraint $A/B$ in $C$ such that $a\in A$ and $B$ is empty. On the other
hand, to model an adversarial action $b$, one whose behavior is not fair (may
not yield all its effects infinitely often in a recurrent state $s$ with
$\pi(s)=b$), we do not include $b$ in any set $A$. This immediately suggests
the way to capture standard strong and strong-cyclic planning as special forms
of FOND+ planning:

######  Theorem 12.

The strong solutions of a FOND problem $P$ are the solutions of the FOND+
problem $P_{c}=\langle P,\emptyset\rangle$.

###### Proof.

Notice that policies are not defined on goal states, and thus there are no
infinite $\pi$-trajectories that reach a goal, for any policy $\pi$. If $\pi$
is a strong solution for $P$, there are no infinite $\pi$-trajectories and
thus all maximal $\pi$-trajectories are finite and goal reaching; i.e., $\pi$
solves $P_{c}$.

On the other hand, if $\pi$ solves $P_{c}$, by definition, the maximal
$\pi$-trajectories that are fair reach the goal. Since there are no
constraints, any infinite $\pi$-trajectory is fair and non-goal reaching, and
thus, if there is any such trajectory, $\pi$ cannot solve $P_{c}$. Therefore,
all maximal $\pi$-trajectories are finite and goal reaching; i.e., $\pi$ is a
strong solution for $P$. ∎

######  Theorem 13.

The strong-cyclic solutions of a FOND problem $P$ are the solutions of the
FOND+ problem $P_{c}=\langle P,\left\\{A/\emptyset\right\\}\rangle$, where $A$
is the set of all the non-deterministic actions in $P$.

###### Proof.

Let $\pi$ be a policy for $P$ and let $\tau$ be an infinite $\pi$-trajectory
in $P$. Since $B$ is empty, any action $\pi(s)$ in $A$ for a recurrent state
$s$ in $\tau$ is fair (cf. Definition 9). Thus, by Definition 10 and that $A$
contains all the non-deterministic actions, $\tau$ is fair in $P$ iff $\tau$
is fair in $P_{c}$, and by Theorem 3, $\pi$ is a strong-cyclic solution for
$P$ iff $\pi$ solves $P_{c}$. ∎

Similarly, QNP problems are reduced to FOND+ problems in a direct way, in this
case, making use of both the head $A$ and the condition $B$ in the fairness
assumptions $A/B$ in $C$:

######  Theorem 14.

The solutions of a QNP problem $Q$ are the solutions of the FOND+ problem
$P_{c}=\langle P,C\rangle$ where $P=T_{D}(Q)$ and $C$ is the set of fairness
assumptions $A_{i}/B_{i}$, one for each numerical variable $x_{i}$ in $Q$,
such that $A_{i}$ contains all the actions in $P$ that decrement $x_{i}$, and
$B_{i}$ contains all the actions in $P$ that increment $x_{i}$.

###### Proof.

Let $Q$ be a QNP problem, let $P_{c}=\langle P,C\rangle$ be the FOND+ problem
associated with $Q$ where $P=T_{D}(Q)$, and let $\pi$ be a policy for $Q$ (and
$P$).

Forward direction. Let us assume that $\pi$ solves $Q$ and suppose it does not
solve $P_{c}$. Then, there is a maximal fair (cf. Definition 10)
$\pi$-trajectory $\tau$ that does not reach the goal. The trajectory $\tau$
must be infinite as otherwise $\pi$ would not be strong-cyclic. Let $R$ be the
set of recurrent states in $\tau$. If $s$ in $R$ and the occurrence of
$\pi(s)$ is fair, the state $s$ is followed infinitely often in $\tau$ by each
$s^{\prime}\in F(\pi(s),s)$. However, the fairness of $\pi(s)$ implies that
there is a fairness assumption $A/B$ in $C$ such that $\pi(s)\in A$, and
$\pi(s^{\prime})\in B$ for no $s^{\prime}\in R$. Yet, this implies that the
variable $x$ associated with the assumption $A/B$ reaches the value of zero
and $\tau$ cannot be infinite. Therefore, the occurrence of $\pi(s)$ for any
state $s$ in $R$ must be unfair; namely, for any $A/B$ in $C$, if $\pi(s)\in
A$ then $\pi(s^{\prime})\in B$ for some $s^{\prime}\in R$. Since there is at
least one state in $R$ where a variable is decremented, no recurrent state in
$\tau$ is terminating (cf. Definition 4), and thus $\pi$ does not solve $Q$.
Therefore, $\pi$ must solve $P_{c}$.

Backward direction. Let us assume that $\pi$ solves $P_{c}$ and supose it does
not solve $Q$. Observe that $\pi$ must be strong-cyclic as otherwise it is
easy to construct a maximal, non-goal reaching, and fair $\pi$-trajectory in
$P_{c}$, contradicting the assumption that $\pi$ solves $P_{c}$. Hence, $\pi$
does not terminate in $Q$; namely, there is an infinite $\pi$-trajectory
$\tau$ in $P$ such that for the set $R$ of its recurrent states, if $\pi(s)$
decrements a variable $x$ for some $s\in R$, there is another state
$s^{\prime}\in R$ such that $\pi(s^{\prime})$ increments $x$. On the other
hand, $R$ must contain a state $s$ such that $\pi(s)$ decrements some variable
since such actions are the only ones that can generate a cycle in $P$. Then,
by the definition of the fairness assumptions in $C$, no occurrence of the
action $\pi(s)$ for a state $s$ in $R$ is fair. Thus, $\tau$ is fair in
$P_{c}$ contradicting the assumption that $\pi$ solves $P_{c}$. Therefore,
$\pi$ must solve $Q$. ∎

## Example

By explicitly stating the fairness assumptions underlying strong, strong-
cyclic, and QNP planning, FOND+ planning integrates these planning models as
well. We illustrate the new possibilities with an example.

$s_{0}$ $s_{1}$ $s_{2}$ $g$ $a$ $a$ $b$ $b$ $b$ $b$ Figure 1: Example model
for FOND problem $P$ with 4 states, non-deterministic actions $a$ and $b$, and
goal state $g$.

Let $P$ be a FOND problem with state set
$\left\\{s_{0},s_{1},s_{2},g\right\\}$, two non-deterministic actions $a$ and
$b$, initial and goal states being $s_{0}$ and $g$, respectively. Action $a$
can only be applied in state $s_{0}$, leading to either $s_{1}$ or $s_{2}$,
whereas action $b$ can be applied only in $s_{1}$ and $s_{2}$, leading, in
both cases, to either $s_{0}$ or $g$; see Figure 1. The FOND problem $P$
admits a single policy, namely, $\pi(s_{0})=a$ and $\pi(s_{1})=\pi(s_{2})=b$,
which we analyze in the context of different FOND+ problems $P_{i}=\langle
P,C_{i}\rangle$ that can be built on top of $P$ using different sets of
fairness assumptions $C_{i}$. For convenience, in the sets $C_{i}$, we use
$a/b$ to denote the fairness assumption
$\left\\{a\right\\}/\left\\{b\right\\}$, and $a$ to denote the assumption
$\left\\{a\right\\}/\emptyset$. The marks ’✓’ and ’✗’ express that the policy
$\pi$ solves or does not solve, resp., the FOND+ problem $P_{i}$, where
$C_{i}$ is:

  1. ✗

$C_{1}=\left\\{\right\\}$; $a$ and $b$ are adversarial.

  2. ✓

$C_{2}=\left\\{a,b\right\\}$; $a$ and $b$ are fair.

  3. ✗

$C_{3}=\left\\{a\right\\}$; $a$ is fair and $b$ is adversarial.

  4. ✓

$C_{4}=\left\\{b\right\\}$; $b$ is fair and $a$ is adversarial.

  5. ✗

$C_{5}=\left\\{a/b\right\\}$; $a$ is conditionally fair on $b$; $b$
adversarial.

  6. ✗

$C_{6}=\left\\{a,b/a\right\\}$; QNP like:
$a:x_{1}\raisebox{0.6458pt}{$\downarrow$},x_{2}\raisebox{0.6458pt}{$\uparrow$}$
and $b:x_{2}\raisebox{0.6458pt}{$\downarrow$}$.

  7. ✓

$C_{7}=\left\\{b,a/b\right\\}$; QNP like:
$b:x_{1}\raisebox{0.6458pt}{$\downarrow$},x_{2}\raisebox{0.6458pt}{$\uparrow$}$
and $a:x_{2}\raisebox{0.6458pt}{$\downarrow$}$.

  8. ✗

$C_{8}=\left\\{a/b,b/a\right\\}$; QNP like:
$a:x_{1}\raisebox{0.6458pt}{$\downarrow$},x_{2}\raisebox{0.6458pt}{$\uparrow$}$
and
$b:x_{2}\raisebox{0.6458pt}{$\downarrow$},x_{1}\raisebox{0.6458pt}{$\uparrow$}$.

The subtle cases are the last four. The policy $\pi$ does not solve $P_{5}$
because there are trajectories like $\tau=s_{0},s_{1},s_{0},$
$s_{2},s_{0},s_{1},s_{0},\ldots$ that are fair but do not reach the goal. The
reason is that while $a/b\in C_{5}$, the occurrences of the action
$a=\pi(s_{0})$ in the recurrent state $s_{0}$ in $\tau$ are not fair. Thus,
both $a$ and $b$ have an adversarial semantics in $\tau$. The policy $\pi$
does not solve $P_{6}$ either, because in the same trajectory $\tau$, the
action $a$ is fair in $s_{0}$ as $a\in C_{6}$ but $b$ is not fair in either
$s_{1}$ or $s_{2}$, as the assumption $b/a$ is in $C_{6}$ but $a$ occurs
infinitely often in $\tau$. As a result, $\tau$ is fair but non-goal reaching
in $P_{6}$. The situation is different in $P_{7}$, where $b$ is fair and $a$
is unfair. Here, $\tau$ is unfair, as any other trajectory in which some or
all the states $s_{0}$, $s_{1}$, and $s_{2}$ occur infinitely often. This is
because $b$ being fair in $s_{1}$ and $s_{2}$ means that the transitions
$(s_{1},g)$ and $(s_{2},g)$ cannot be skipped forever, and the goal must be
reached eventually. Finally, in $P_{8}$, the trajectory $\tau$ becomes fair
again, as both $a$ and $b$ are adversarial in $\tau$.

## Termination and Sieve+ for FOND+

We now consider the computation of policies for FOND+ problems. Initially, we
look for a procedure to verify if a policy $\pi$ solves a problem
$P_{c}=\langle P,C\rangle$, and then transform this _verification procedure_
into a _synthesis procedure_.

The solutions for FOND+ problems are policies that terminate in the goal, a
termination condition that combines and goes beyond the solution concept for
QNPs that only requires goal reachability (strong-cyclicity) and termination
(finite trajectories). The termination condition for FOND+ planning can be
expressed as follows:

######  Definition 15 (FOND+ termination).

Let $\pi$ be a policy for the FOND+ problem $P_{c}{=}\langle P,C\rangle$.
State $s$ in $P$ terminates iff

  1. 1.

$s$ is a goal state,

  2. 2.

$s$ is fair and some state $s^{\prime}\in F(\pi(s),s)$ terminates, or

  3. 3.

$s$ is not fair, all states $s^{\prime}\in F(\pi(s),s)$ terminate, and
$F(\pi(s),s)$ is non-empty.

where $s$ is fair if for some $A_{i}/B_{i}$ in $C$, $\pi(s)\in A_{i}$, and
every path that connects $s$ to itself and that contains a state $s^{\prime}$
with $\pi(s^{\prime})\in B_{i}$, also contains a state $s^{\prime\prime}$ that
terminates.

FOND+ termination expresses a procedure similar to Sieve, that we call Sieve+,
that keeps labeling states $s$ as terminating (the same as removing all edges
from $s$ in the policy graph) until no states are left or no more states can
be labeled. The key difference with Sieve is that the removals are done
backward from the goal as captured in Definition 15. This is strictly
necessary for Sieve+ to be a sound and complete procedure for FOND+ problems:

######  Theorem 16.

A policy $\pi$ solves the FOND+ problem $P_{c}=\langle P,C\rangle$ iff all the
states $s$ that are reachable by $\pi$ terminate according to Definition 15.

The solutions to FOND+ problems cannot be characterized as those of QNPs, as
policies that are strong-cyclic and terminating in the sense that the policy
cannot traverse edges in the policy graph forever. The policy $\pi$ for the
example $P_{5}$ is indeed strong-cyclic and terminating in this sense, but as
shown above, it does not solve $P_{5}$. The policy terminates because the
action $a$ cannot be done forever, but it does not terminate in a goal state.
In QNPs, this cannot happen, as strong-cyclic policies that are terminating,
always terminate in a goal state.

###### Proof.

Let $S_{0},S_{1},\ldots$ be the chain of state subsets labeled as terminating
corresponding to Definition 15 (cf. footnote 1). For a state subset $R$,
$\pi(R)$ denotes the set $\\{\pi(s):s\in R\\}$.

Backward implication. For a proof by contradiction, let us assume that every
reachable state terminates, and let us suppose that $\pi$ does not solve
$P_{c}$; i.e., there is a _maximal and fair_ non-goal reaching
$\pi$-trajectory $\tau$. We consider two cases.

Case 1: $\tau=s_{0},s_{1},\ldots,s_{n}$ is finite. Since $\tau$ is maximal and
$s_{n}$ is not a goal, $F(\pi(s_{n}),s_{n})$ is empty. Therefore, $s_{n}$
cannot terminate contradicting the assumption.

Case 2: $\tau$ is infinite. Let $R$ be the set of recurrent states in $\tau$,
let $j$ be the minimum index such that $R\cap S_{j}\neq\emptyset$, and let $s$
be a state in $R\cap S_{j}$. Clearly, $j>0$ since $S_{0}$ is the set of goal
states and $\tau$ does not reach such states. We further consider two
subcases:

  1. $\bullet$

$s$ is not fair according to Definition 15. Then, every state $s^{\prime}$ in
$F(\pi(s),s)$ must belong to some $S_{k}$ for $k<j$. This is impossible by the
choice of $j$.

  2. $\bullet$

$s$ is fair according to Definition 15. That is, for some constraint $A/B$,
$\pi(s)\in A$, and if $\pi(R)\cap B\neq\emptyset$, $R$ must contain a state
$s^{\prime\prime}\in S_{k}$ for $k<j$. Since the latter is impossible by the
choice of $j$, $\pi(R)\cap B=\emptyset$. This implies that the occurrence of
the action $\pi(s)$ is fair in the trajectory $\tau$ (cf. Definition 9), and
thus that $s$ is followed in $\tau$ by each of its possible successors
$s^{\prime}\in F(\pi(s),s)$ infinitely often; i.e., $F(\pi(s),s)\subseteq R$.
However, by Definition 15, some such successor $s^{\prime}$ must terminate
(i.e., $s^{\prime}\in S_{k}$ for $k<j$), something that is impossible by the
choice of $j$.

Forward implication. For a proof by contradiction, let us assume that $\pi$
solves $P_{c}$, and let us suppose that there is a reachable state $s$ that
does not terminate. We are going to construct an infinite $\pi$-trajectory
$\tau$ that is fair and does not reach a goal, contradicting the assumption.

First observe that $s$ is not a goal state and thus it must have successor
states. If $s$ is fair (cf. Definition 15), every state $s^{\prime}\in
F(\pi(s),s)$ does not terminate, whereas if $s$ is not fair, some state
$s^{\prime}\in F(\pi(s),s)$ does not terminate. It is then easy to see that we
can construct an infinite $\pi$-trajectory $\tau^{\prime}$ seeded at $s$ such
that for the set $R$ of its recurrent states:

  1. 1.

no state in $R$ terminates,

  2. 2.

if $s^{\prime}$ in $R$ is fair, it is followed infinitely often by each
$s^{\prime\prime}\in F(\pi(s^{\prime}),s^{\prime})$, and

  3. 3.

if $s^{\prime}$ in $R$ is not fair, it is followed infinitely often by each
$s^{\prime\prime}\in F(\pi(s^{\prime}),s^{\prime})$ that does not terminate,
but there is $s^{\prime\prime}$ in $F(\pi(s^{\prime}),s^{\prime})$ that does
not follows $s^{\prime}$ infinitely often.

Since the state $s$ is reachable by $\pi$, we can construct a $\pi$-trajectory
$\tau$ that reaches $s$ from the initial state $s_{0}$ of $P$ and that then
follows $\tau^{\prime}$. The set of recurrent states for $\tau$ is the set $R$
of recurrent state for $\tau^{\prime}$; in particular, $R$ does not contain a
goal state. We finish by showing that $\tau$ is fair.

We do so using Definitions 9 and 10 for fair actions and fair trajectories
respectively. Let $s^{\prime}$ be a state in $R$ such that the action
$\pi(s^{\prime})$ is fair in $\tau$; in particular, $\pi(s^{\prime})\in A_{i}$
for some index $i$. If the state $s^{\prime}$ is fair (cf. Definition 15),
$F(\pi(s^{\prime}),s)\subseteq R$ by construction of $\tau$. Else, if
$s^{\prime}$ is not fair, we show below that the occurrence of the action
$\pi(s^{\prime})$ is not fair in $\tau$. Hence, in both cases, the trajectory
$\tau$ is fair.

For the last bit, by Definition 15, if $s^{\prime}$ is not fair, there is a
cycle $\tau^{\prime\prime}$ that a) passes over $s^{\prime}$, b) contains a
state $s^{\prime\prime}$ with $\pi(s^{\prime\prime})\in B_{i}$, and c) does
not contain a terminating state. Hence, by construction of $\tau$, $R$
contains all the states in $\tau^{\prime\prime}$. However, since there is some
state in $F(\pi(s^{\prime}),s^{\prime})$ that is not in $R$, the occurrence of
$\pi(s^{\prime})$ in $\tau$ is not fair. ∎

## FOND+ and Dual FOND Planning

FOND+ planning subsumes Dual FOND planning where fair and adversarial actions
can be combined. In order to show that, let us first recall the latter:

######  Definition 17 (Geffner and Geffner, 2018).

A Dual FOND problem is a FOND problem where the non-deterministic actions are
labeled as either fair or adversarial. A policy $\pi$ solves a Dual FOND
problem $P$ iff for all reachable state $s$, $\pi(s){\in}A(s)$, and there is a
function $d$ from reachable states into $\\{0,\ldots,|S|\\}$ such that 1)
$d(s){=}0$ for goal states, 2) $d(s^{\prime}){<}d(s)$ for some $s^{\prime}\in
F(\pi(s),s)$ if $\pi(s)$ is fair, and 3) $d(s^{\prime}){<}d(s)$ for all
$s^{\prime}\in F(\pi(s),s)$ if $\pi(s)$ is adversarial.

For showing that this semantics coincides with the semantics of a suitable
fragment of FOND+ planning, let us recast this definition as a termination
procedure:

######  Definition 18 (Dual FOND termination).

Let $\pi$ be a policy for the Dual FOND problem $P$. A state $s$ in $P$
terminates iff

  1. 1.

$s$ is a goal state,

  2. 2.

$\pi(s)$ is fair and some $s^{\prime}\in F(\pi(s),s)$ terminates, or

  3. 3.

$\pi(s)$ is adversarial, all states $s^{\prime}\in F(\pi(s),s)$ terminate, and
$F(\pi(s),s)$ is non-empty.

######  Theorem 19.

$\pi$ is a solution to a Dual FOND problem $P$ iff for every non-goal state
$s$ reachable by $\pi$, $\pi(s)\in A(s)$ and $s$ terminates according to
Definition 18.

###### Proof.

If $\pi$ is a solution for $P$, there is a minimal function $d$ that satisfies
Definition 17, and that can be used to construct a chain $S_{0},S_{1},\ldots$
of state subsets by $S_{i}=\\{s:\text{$s$ is reachable and $d(s)=i$}\\}$. It
is not difficult to check that such a chain corresponds to the unique chain of
subsets entailed by Definition 18 (cf. footnote 1).

On the other hand, for a policy $\pi$ that entails such a chain
$S_{0},S_{1},\ldots$ of terminating states that cover all reachable states,
the function $d$ on states, defined by $d(s)=i$ for the minimum $i$ such that
$s\in S_{i}$, satisfies Definition 17. ∎

The only difference between the termination for Dual FOND and the one for
FOND+ (Def. 15) is that in the former the fair and adversarial labels are
given, while in the latter they are a function of the explicit fairness
assumptions and policy. It is easy to show however that Dual FOND problems
correspond to the class of FOND+ problems with conditional fairness
assumptions $A/B$ with empty $B$:

######  Theorem 20.

A policy $\pi$ solves a Dual FOND problem $P^{\prime}$ iff $\pi$ solves the
FOND+ problem $P_{c}=\langle P,C\rangle$ where $P$ is like $P^{\prime}$
without the action labels, and $C=\\{A/B\\}$ where $A$ contains all the
actions labeled as fair in $P^{\prime}$, and $B$ is empty.

###### Proof.

By Theorems 19 and 16, it is enough to show that for every $\pi$-reachable and
non-goal state $s$ in $P^{\prime}$, $s$ terminates according to Definition 18
iff $s$ terminates according to Definition 15. Yet, this is direct since for
the unique constraint $A/B$ in $C$, it is easy to see that a state $s$ is fair
according to Definition 15 iff $\pi(s)$ is a fair action in $P^{\prime}$. With
this observation, Definition 18 becomes exactly Definition 15. ∎

## FOND-ASP: An ASP-based FOND+ Planner

The characterization of FOND+ planning given in Theorem 16 allows for a
transparent and direct implementation of a sound and complete FOND+ planner.
For this, the planner _hints_ a policy $\pi$ and then each state reachable by
$\pi$ is checked for termination using Definition 15. The problem of looking
for a policy that satisfies this restriction can be expressed in SAT, although
we have found it more convenient to express it as an answer set program, a
convenient and high-level alternative to SAT (Brewka, Eiter, and Truszczyński
2011; Lifschitz 2019; Gebser et al. 2012), using the facilities provided by
clingo (Gebser et al. 2019).

The code for the back-end of the ASP-based FOND+ planner is shown in Figure 2.
The front-end of the planner, not shown, parses an input problem
$P_{c}=\langle P,C\rangle$ and builds a _flat representation_ of $P_{c}$ in
terms of a number of ground atoms that are shown in capitalized predicates in
the figure. The code in the figure and the facts representing the problem are
fed to the ASP solver clingo, which either returns a (stable) model for the
program or reports that no such model exists. In the former case, a policy
that solves $P_{c}$ is obtained from the atoms pi(S,A) made true by the model.

The set of ground atoms providing a flat representation of the problem $P_{c}$
contains the atoms STATE(s), ACTION(a), and TRANSITION(s,a,s’) for each
(reachable) state $s$, ground action $a$ and transition $s^{\prime}\in F(a,s)$
found in a reachability analysis from the initial state $s_{0}$. In addition,
the set includes the atoms INITIAL(s0), GOAL(s) for goal states $s$, and
ASET(i,a) and BSET(i,b) for a fairness assumption $A_{i}/B_{i}$ in $C$ if
$a\in A_{i}$ and $b\in B_{i}$ respectively.

The program for the FOND+ problem $P_{c}$ is denoted as $T(P_{c})$, while
$T(P_{c},\pi)$ is used to refer to the program $T(P_{c})$ but with the line 2
in Figure 2 replaced by facts pi(s,a) when $\pi(s)=a$ for a given policy
$\pi$, and the integrity constraint in line 23 removed. A model $M$ for
$T(P_{c})$ encodes a policy $\pi_{M}$ where $\pi_{M}(s)=a$ iff pi(s,a) holds
in $M$. The formal properties of the fond-asp planner are as follows:

######  Theorem 21.

Let $P_{C}=\langle P,C\rangle$ be a FOND+ problem, and let $\pi$ be a policy
for $P$. Then,

  1. 1.

There is a unique stable model $M$ of $T(P_{c},\pi)$, and
$\text{\frenchspacing\mbox{terminate(s)}}\in M$ iff $s$ terminates (Definition
15).

  2. 2.

The policy $\pi$ solves $P_{c}$ iff the model $M$ for $T(P_{c},\pi)$ satisfies
the integrity constraint in line 23 in Figure 2.

  3. 3.

$M$ is a model of $T(P_{c})$ iff $M$ is the model of $T(P_{c},\pi_{M})$ and
$M$ satisfies the integrity constraints. Thus, fond-asp is a sound and
complete planner for FOND+.

  4. 4.

Deciding if $T(P_{c},\pi)$ has a model is in P; i.e., fond-asp runs in non-
deterministic exponential time.

###### Proof.

(Sketch.) For 1. A model $M$ is stable iff it can be constructed in a “bottom-
up manner”. This can be done by constructing a sequence of atom sets
$M_{0},M_{1},\ldots$ that define the atoms connected/2, blocked/2, fair/1,
terminate/1, and reachable. Using induction, it can be shown that any such
sequence of atom sets lead to the same stable model $M$. This shows
uniqueness. The existence of $M$ follows since for given $\pi$, there is
always a stable model $M$ for $T(P_{c},\pi)$. For 2. By Theorem 16, $\pi$
solves $P_{c}$ iff $M$ is the unique model of $T(P_{c},\pi)$ and $M$ satisfies
the integrity constraint. For 3. Straightforward by 2. For 4. A model for
$T(P_{c},\pi)$ can be constructed by calculating the terminating states for
the policy graph for $\pi$. This can be done in time that is polynomial in the
size of the policy graph which lower bounds the size of $T(P_{c})$. fond-asp
builds $T(P_{c})$ in exponential time, then guesses a policy $\pi$ is linear
time in the size of $T(P_{c})$, and finally checks if $T(P_{c},\pi)$ has a
model in time that is polynomial in the size of $T(P_{c})$. ∎

1 % policy, edges, and connectedness 2 { pi(S,A) : ACTION(A) } = 1 :-
STATE(S), not GOAL(S). 3 edge(S,T) :- pi(S,A), TRANSITION(S,A,T). 4
connected(S,T) :- edge(S,T). 5 connected(S,T) :- connected(S,X), edge(X,T), S
!= X. 6 7 % blocked(S,T) iff there is no (S,T)-path, or all such paths have a
terminating state 8 blocked(S,T) :- STATE(S), STATE(T), not connected(S,T). 9
blocked(S,T) :- connected(S,T), terminate(S). 10 blocked(S,T) :-
connected(S,T), terminate(T). 11 blocked(S,T) :- connected(S,T), blocked(X,T)
: edge(S,X), connected(X,T). 12 13 % fair(S) iff for some A/B, pi(S) in A and
each cycle over S that passes 14 % over X such that pi(X) in B contains a
terminating state 15 fair(S) :- pi(S,A), ASET(I,A), blocked(X,S) : pi(X,B),
BSET(I,B), not blocked(S,X). 16 17 % terminating states 18 terminate(S) :-
GOAL(S). 19 terminate(S) :- fair(S), edge(S,T), terminate(T). 20 terminate(S)
:- not fair(S), edge(S,_), terminate(T) : edge(S,T). 21 22 % reachable states
must terminate 23 :- reachable(S), not terminate(S). 24 reachable(S) :-
INITIAL(S). 25 reachable(S) :- reachable(X), not GOAL(X), edge(X,S).

Figure 2: The concise encoding in clingo of the ASP-based FOND+ planner tested
(fond-asp). The FOND+ problem enters through the predicates STATE/1, ACTION/1,
INITIAL/1, GOAL/1, TRANSITION/3, ASET/2 and BSET/2, where ASET(i,A) (resp.
BSET(i,A)) iff action A belongs to $A_{i}$ (resp. $B_{i}$) in the fairness
assumption $A_{i}/B_{i}$. In clingo; the syntax “P : <cond>” used in lines 11,
15, and 20 stands for the implicitly universally quantified conditional “if
<cond> then P”.

## Complexity

A direct consequence of Theorem 21 is that the plan-existence decision problem
for FOND+ is in NEXP (i.e., non-deterministic exponential time). Since FOND
problems are easily reduced to FOND+ problems (Theorem 13) and the plan-
existence for FOND is EXP-Hard (Littman, Goldsmith, and Mundhenk 1998;
Rintanen 2004), plan-existence for FOND+ is EXP-Hard as well. We conjecture
that the NEXP bound is loose and that plan-existence for FOND+ is EXP-
Complete. In contrast, LTL planning and synthesis is 2EXP-Complete (Pnueli and
Rosner 1989).

######  Theorem 22.

The plan-existence problem for FOND+ problems is in NEXP and it is EXP-Hard.

###### Proof.

Inclusion. On input problem $P_{c}=\langle P,C\rangle$, the state space for
$P$ is constructed explicitly and a policy $\pi$ for $P_{c}$ is guessed in
non-deterministic exponential time. Then, by Theorem 21, the logic program
$T(P_{c},\pi)$ has a model iff $\pi$ solves $P_{c}$. Deciding whether
$T(P_{c},\pi)$ has a model can be done in time polynomial in the size of the
program.

Hardness. By Theorem 13, A FOND problem can be reduced in polynomial time to a
FOND+ problem. The claim follows by the EXP-Hardness of the plan-existence
problem for FOND. ∎

## Experiments

We tested fond-asp on three classes of problems:222Planner available at
https://github.com/idrave/aspplanner FOND problems, QNPs, and more expressive
FOND+ problems that do not fit in either class and that can only be addressed
using LTL engines. On each class, we compare fond-asp with the FOND solvers
fond-sat (Geffner and Geffner 2018) and prp (Muise, McIlraith, and Beck 2012),
the QNP solver qnp2fond (Bonet and Geffner 2020) using fond-sat and prp as the
underlying FOND solver, and the LTL-synthesis tool strix (Luttenberger, Meyer,
and Sickert 2020). The pure (strong and strong-cyclic) FOND problems are those
in the FOND-SAT distribution, the QNPs are those by (Bonet and Geffner 2020)
and two new families of instances that grow in size with a parameter. For more
expressive FOND+ planning problems, four new families of problems are
introduced that extend the new QNPs with fair and adversarial actions, with
only some being solvable. The domain and goals of these problems are encoded
in LTL in the usual way, while the fairness assumptions $A/B$ are encoded as
described in the introduction. In all the experiments, time and memory bounds
of 1/2 hour and 8GB are enforced.

The results are detailed below. In summary, we observe the following. For pure
FOND benchmarks, fond-asp does not compete with specialized planners like prp
or fond-sat as these problems span (reachable) state spaces that are just too
large. For QNPs, on the other hand, fond-asp does better than fond-sat but
worse than prp on the FOND translations. For expressive FOND+ problems, where
these planners cannot be used at all, fond-asp performs much better than strix
on both solvable and unsolvable problems.

### FOND Benchmarks

fond-asp managed to solve a tiny fraction of the benchmarks used for strong
and strong-cyclic planning in the fond-sat distribution. The number of
reachable states in these problems is large (tens of thousands or more) and
the size of the grounded ASP program is quadratic in that number. In general,
this seems to limit the scope of fond-asp to problems with no more than one
thousand states approximately, as suggested by the results in Table QNP
Problems. We have observed however that sometimes fond-asp manages to solve
strong planning problems with more than 100,000 states. This may have to do
with clingo’s grounder or with the state space topology; we do not know the
exact reason yet.

### QNP Problems

The two families of QNPs involve the numerical variables
$\\{x_{i}\\}_{i=1}^{n}$ that have all positive values in the initial state.
The goal is to achieve $x_{n}=0$. Problems in the qnp1 family are solved by
means of $n$ sequential simple loops, while problems in the qnp2 family are
solved using $n$ nested loops. The actions for problems in qnp1 are
$b=\langle\neg p;p\rangle$, $a_{1}=\langle p;\neg
p,x_{1}\raisebox{0.6458pt}{$\downarrow$}\rangle$, and $a_{i}=\langle
p,x_{i-1}{\,=\,}0;\neg p,x_{i}\raisebox{0.6458pt}{$\downarrow$}\rangle$ for
$1<i\leq n$, while those for qnp2 are $b=\langle\neg p;p\rangle$,
$a_{1}=\langle p;\neg p,x_{1}\raisebox{0.6458pt}{$\downarrow$}\rangle$, and
$a_{i}=\langle p,x_{i-1}{\,=\,}0;\neg
p,x_{i-1}\raisebox{0.6458pt}{$\uparrow$},x_{i}\raisebox{0.6458pt}{$\downarrow$}\rangle$,
$1<i\leq n$.

Table QNP Problems shows the results for values of $n$ in
$\left\\{2,3,\ldots,10\right\\}$ and different planners, along with the number
of reachable states in each problem. As can be seen, qnp2fond/prp is the
planner that scales best, followed by fond-asp, qnp2fond/fond-sat, and strix
at the end. As mentioned, the performance of fond-asp is harmed by a large
number of reachable states. While the number of states for the FOND
translation produced by qnp2fond is much larger, as the translation involves
extra propositions, this number does not necessarily affect the performance of
FOND planners like fond-sat and prp that can compute compact policies. It is
also interesting to see how quickly the performance of the LTL engine strix
degrades; it cannot even solve qnp1-06 which has 14 states. The table also
shows results for QNP problems that capture abstractions for four generalized
planning problems, all of which involve small state spaces (Bonet and Geffner
2020).

|  |  | qnp2fond |  |  |
---|---|---|---|---|---|---
problem | #states |  | fond-sat | prp |  | strix | fond-asp
[separator=pipe,late after line= |  |  |  |  |  |  |
[separator=pipe,late after line= |  |  |  |  |  |  |
[separator=pipe,late after line= |  |  |  |  |  |  |
|  |  |  |  |  |  |

Table 1: Results for three families of QNPs for qnp2fond paired with the FOND
solvers fond-sat and prp, strix (QNP translated to LTL), and fond-asp. Entries
’—’ and ’***’ denote solver runs out of time and memory, respectively. Time is
in seconds.

### More Expressive FOND+ Problems

The third class of instances consists of four families of problems obtained
from the two QNP families above. The new problems are not “pure” QNPs, as they
also involve actions with non-deterministic effects on boolean variables that
can be adversarial or fair. Thus, these problems cannot be translated into
FOND problems for the use of planners such as prp or fond-sat. For each family
qnp1 and qnp2, two new families $f01$ and $f11$ of problems are obtained by
replacing the action $b=\langle\neg p;p\rangle$ by the non-deterministic
action $b^{\prime}=\langle\neg p;\text{{oneof}}\left\\{p,\neg
p\right\\}\rangle$, leaving the actions $a_{i}$ untouched. Since the action
$b^{\prime}$ does not appear in any fairness assumption, it is adversarial and
thus no problem in the class $f01$ has a solution as the “adversary” may
always choose to leave $p$ false. The family $f11$ is obtained on top of $f01$
by adding two additional booleans $q$ and $r$, and two actions $c=\langle\neg
q;r,\text{{oneof}}\left\\{q,\neg q\right\\}\rangle$ and $d=\langle r;q,\neg
r\rangle$ such that: 1) the actions $a_{i}$ are modified by adding $q$ as
precondition and $\neg q$ as effect, and 2) the fairness assumption $A/B$ with
$A=\left\\{b^{\prime}\right\\}$ and $B$ empty is added. The problems in $f11$
thus involve the QNP-like actions $a_{i}$, the fair action $b^{\prime}$, and
the adversarial action $c$, and they all have a solution.

Table More Expressive FOND+ Problems shows the result for fond-asp and strix
as these are the only solvers able to handle the combination of fairness
assumptions. As it can be seen, fond-asp scales better than strix on all of
these problems, the solvable ones (families $f11$) and the unsolvable ones
(families $f01$).

|  |  $f01$ (unsolvable) |  |  $f11$ (solvable)
---|---|---|---|---
problem |  | #states | strix | fond-asp |  | #states | strix | fond-asp
[separator=pipe,late after line= |  |  |  |  |  |  |  |
[separator=pipe,late after line= |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |

Table 2: Results for four families of FOND+ problems obtained from the QNPs in
Table 1 by playing with the fairness assumptions, some solvable, some
unsolvable. These problems are handled only by strix and fond-asp. Entries ’—’
and ’***’ denote solver runs out of time and memory, respectively. Time is in
seconds.

We finally tested fond-asp over the seven problems considered in a recent
approach to program synthesis over unbounded data structures (Bonet et al.
2020). Although the original specifications are in LTL, these can be all
expressed in FOND+ using different types of fairness assumptions. The problems
are solved easily by both fond-asp and strix as their reachable state spaces
have very few states.

## Related Work

The work is related to three threads: SAT-based FOND planning, QNPs, and LTL
synthesis. The SAT-based FOND planner by Chatterjee, Chmelík, and Davies
(2016) expands the state space in full, like fond-asp, but a more recent
version computes compact policies and provides support for Dual FOND planning
(Geffner and Geffner 2018). We have used answer set programs as opposed to CNF
encodings exploiting their high-level modeling language, the natural support
for inductive definitions, and the competitive performance of clingo (Gebser
et al. 2019). fond-asp is also a novel QNP planner which can handle non-
deterministic effects on boolean variables. The formulation actually brings
QNP planning into the realm of standard FOND planning by dealing with the
underlying fairness assumptions explicitly.

The use of fairness assumptions connects also to works on LTL planning and
synthesis (Camacho, Bienvenu, and McIlraith 2019; Aminof et al. 2019), and to
works addressing temporally extended goals (De Giacomo and Vardi 1999;
Patrizi, Lipovetzky, and Geffner 2013; Camacho et al. 2017; Camacho, Bienvenu,
and McIlraith 2019; Aminof, De Giacomo, and Rubin 2020). Our work can be seen
as a special case of planning under LTL assumptions (Aminof et al. 2019) that
targets an LTL fragment that is relevant for FOND planning and is
computationally simpler. While it is possible to express FOND+ tasks as LTL
syntheses problems, and we have shown how to do that, it remains to be seen
whether the task can be expressed in a _restricted_ LTL fragment that admits
more efficient techniques. While the _strong_ fairness assumption on action
effects that is required cannot be _directly_ encoded in GR(1) (Bloem et al.
2012), strong-cyclic FOND planning has been encoded in Büchi Games
(D’Ippolito, Rodríguez, and Sardiña 2018), a special case of GR(1). It remains
to be investigated whether that encoding can be extended to deal with
_conditional_ fairness.

## Summary

We have formulated an extension of FOND planning that makes use of explicit
fairness assumptions of the form $A/B$ where $A$ and $B$ are disjoints sets of
actions. While in Dual FOND planning actions are labeled as fair or unfair, in
FOND+ planning these labels are a function of the trajectories and the
fairness assumptions: an action $a\in A$ is deemed fair in a recurrent state
if a suitable condition on $B$ holds. In this way, FOND+ generalizes strong,
strong-cyclic, Dual FOND planning, and also QNP planning, which is actually
the only planning setting, excluding LTL planning, that makes use of the
conditions $B$. We have implemented an effective FOND+ planner by reducing the
problem to answer set programs using clingo, and evaluated its performance in
relation to FOND and QNP planners, which handle less expressive problems, and
LTL synthesis tools, which handle more expressive ones. We have shown that
FOND+ is in NEXP but have not shown yet whether it is in EXP, like FOND and
QNP planning.

## Acknowledgments

We thank the clingo team for the tool. The work is partially supported by an
ERC Advanced Grant (No 885107), the project TAILOR, funded by an EU Horizon
2020 Grant (No 952215), and by the Knut and Alice Wallenberg (KAW) Foundation
under the WASP program. H. Geffner is a Wallenberg Guest Prof. at Linköping
University, Sweden.

## References

  * Aminof et al. (2019) Aminof, B.; De Giacomo, G.; Murano, A.; and Rubin, S. 2019.  Planning under LTL Environment Specifications.  In _Proc. ICAPS_ , 31–39.
  * Aminof, De Giacomo, and Rubin (2020) Aminof, B.; De Giacomo, G.; and Rubin, S. 2020.  Stochastic Fairness and Language-Theoretic Fairness in Planning in Nondeterministic Domains.  In _Proc. ICAPS_ , 20–28.
  * Bertsekas and Tsitsiklis (1996) Bertsekas, D.; and Tsitsiklis, J. 1996.  _Neuro-Dynamic Programming_.  Athena Scientific.
  * Bloem et al. (2012) Bloem, R.; Jobstmann, B.; Piterman, N.; Pnueli, A.; and Sa’ar, Y. 2012.  Synthesis of Reactive(1) designs.  _Journal of Computer and System Sciences_ 78(3): 911–938.
  * Bonet et al. (2020) Bonet, B.; De Giacomo, G.; Geffner, H.; Patrizi, F.; and Rubin, S. 2020.  High-Level Programming via Generalized Planning and LTL Synthesis.  In _Proc. KR_ , 152–161.
  * Bonet et al. (2017) Bonet, B.; De Giacomo, G.; Geffner, H.; and Rubin, S. 2017.  Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints.  In _Proc. IJCAI_ , 873–879.
  * Bonet, Frances, and Geffner (2019) Bonet, B.; Frances, G.; and Geffner, H. 2019.  Learning features and abstract actions for computing generalized plans.  In _Proc. AAAI_ , 2703–2710.
  * Bonet and Geffner (2020) Bonet, B.; and Geffner, H. 2020.  Qualitative Numeric Planning: Reductions and Complexity.  _Journal of Artificial Intelligence Research (JAIR)_ 69: 923–961.
  * Brewka, Eiter, and Truszczyński (2011) Brewka, G.; Eiter, T.; and Truszczyński, M. 2011.  Answer set programming at a glance.  _Communications of the ACM_ 54(12): 92–103.
  * Calvanese, De Giacomo, and Vardi (2002) Calvanese, D.; De Giacomo, G.; and Vardi, M. Y. 2002.  Reasoning about actions and planning in LTL action theories.  _KR_ 2: 593–602.
  * Camacho, Bienvenu, and McIlraith (2019) Camacho, A.; Bienvenu, M.; and McIlraith, S. A. 2019.  Towards a Unified View of AI Planning and Reactive Synthesis.  In _Proc. AAAI_ , 58–67.
  * Camacho and McIlraith (2016) Camacho, A.; and McIlraith, S. A. 2016.  Strong-Cyclic Planning when Fairness is Not a Valid Assumption.  In _Proc. KnowProS Workshop_.
  * Camacho et al. (2017) Camacho, A.; Triantafillou, E.; Muise, C. J.; Baier, J. A.; and McIlraith, S. A. 2017.  Non-Deterministic Planning with Temporally Extended Goals: LTL over Finite and Infinite Traces.  In _Proc. AAAI_.
  * Chatterjee, Chmelík, and Davies (2016) Chatterjee, K.; Chmelík, M.; and Davies, J. 2016.  A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs.  In _Proc. AAAI_ , 3225–3232.
  * Cimatti et al. (2003) Cimatti, A.; Pistore, M.; Roveri, M.; and Traverso, P. 2003.  Weak, strong, and strong cyclic planning via symbolic model checking.  _Artificial Intelligence_ 147(1-2): 35–84.
  * Cimatti, Roveri, and Traverso (1998a) Cimatti, A.; Roveri, M.; and Traverso, P. 1998a.  Automatic OBDD-based generation of universal plans in non-deterministic domains.  In _Proc. AAAI_ , 875–881.
  * Cimatti, Roveri, and Traverso (1998b) Cimatti, A.; Roveri, M.; and Traverso, P. 1998b.  Strong Planning in Non-Deterministic Domains Via Model Checking.  In _Proc. AIPS_ , 36–43.
  * Ciolek et al. (2020) Ciolek, D.; D’Ippolito, N.; Pozanco, A.; and Sardiña, S. 2020.  Multi-Tier Automated Planning for Adaptive Behavior.  In _Proc. ICAPS_ , volume 30, 66–74.
  * Daniele, Traverso, and Vardi (1999) Daniele, M.; Traverso, P.; and Vardi, M. Y. 1999.  Strong Cyclic Planning Revisited.  In _Recent Advances in AI Planning_ , 35–48. Springer.
  * De Giacomo and Vardi (1999) De Giacomo, G.; and Vardi, M. Y. 1999.  Automata-Theoretic Approach to Planning for Temporally Extended Goals.  In _Proc. ECP_ , volume 1809 of _LNCS_ , 226–238.
  * D’Ippolito, Rodríguez, and Sardiña (2018) D’Ippolito, N.; Rodríguez, N.; and Sardiña, S. 2018.  Fully Observable Non-deterministic Planning as Assumption-Based Reactive Synthesis.  _Journal of Artificial Intelligence Research (JAIR)_ 61: 593–621.
  * Gebser et al. (2012) Gebser, M.; Kaminski, R.; Kaufmann, B.; and Schaub, T. 2012.  Answer set solving in practice.  _Synthesis lectures on artificial intelligence and machine learning_ 6(3): 1–238.
  * Gebser et al. (2019) Gebser, M.; Kaminski, R.; Kaufmann, B.; and Schaub, T. 2019.  Multi-shot ASP solving with clingo.  _Theory and Practice of Logic Programming_ 19(1): 27–82.
  * Geffner and Bonet (2013) Geffner, H.; and Bonet, B. 2013.  _A Concise Intro. to Models and Methods for Automated Planning_.  Morgan-Claypool.
  * Geffner and Geffner (2018) Geffner, T.; and Geffner, H. 2018.  Compact policies for Non-deterministic Fully Observable Planning as SAT.  In _Proc. ICAPS_ , 88–96.
  * Helmert (2002) Helmert, M. 2002.  Decidability and Undecidability Results for Planning with Numerical State Variables.  In _Proc. AIPS_.
  * Hu and De Giacomo (2011) Hu, Y.; and De Giacomo, G. 2011.  Generalized planning: Synthesizing plans that work for multiple environments.  In _Proc. IJCAI_ , 918–923.
  * Lifschitz (2019) Lifschitz, V. 2019.  _Answer set programming_.  Springer.
  * Littman, Goldsmith, and Mundhenk (1998) Littman, M. L.; Goldsmith, J.; and Mundhenk, M. 1998.  The computational complexity of probabilistic planning.  _Journal of Artificial Intelligence Research_ 9: 1–36.
  * Luttenberger, Meyer, and Sickert (2020) Luttenberger, M.; Meyer, P. J.; and Sickert, S. 2020.  Practical synthesis of reactive systems from LTL specifications via parity games.  _Acta Informatica_ 57(1-2): 3–36.
  * Mattmüller et al. (2010) Mattmüller, R.; Ortlieb, M.; Helmert, M.; and Bercher, P. 2010.  Pattern Database Heuristics for Fully Observable Nondeterministic Planning.  In _Proc. ICAPS_ , 105–112.
  * Muise, McIlraith, and Beck (2012) Muise, C.; McIlraith, S. A.; and Beck, J. C. 2012.  Improved Non-deterministic Planning by Exploiting State Relevance.  In _Proc. ICAPS_ , 172–180.
  * Patrizi, Lipovetzky, and Geffner (2013) Patrizi, F.; Lipovetzky, N.; and Geffner, H. 2013.  Fair LTL Synthesis for Non-Determinsistic Systems using Strong Cyclic Planners.  In _Proc. IJCAI_.
  * Pnueli and Rosner (1989) Pnueli, A.; and Rosner, R. 1989.  On the synthesis of an asynchronous reactive module.  In _ICALP_ , 652–671.
  * Rintanen (2004) Rintanen, J. 2004.  Complexity of Planning with Partial Observability.  In _Proc. ICAPS_ , 345–354.
  * Rodriguez et al. (2021) Rodriguez, I. D.; Bonet, B.; Sardiña, S.; and Geffner, H. 2021.  Flexible FOND Planning with Explicit Fairness Assumptions.  In _Proc. ICAPS_ , Accepted.
  * Srivastava, Immerman, and Zilberstein (2011) Srivastava, S.; Immerman, N.; and Zilberstein, S. 2011.  A new representation and associated algorithms for generalized planning.  _Artificial Intelligence_ 175(2): 615–647.
  * Srivastava et al. (2011) Srivastava, S.; Zilberstein, S.; Immerman, N.; and Geffner, H. 2011.  Qualitative Numeric Planning.  In _Proc. AAAI_.


070006 2015 C. A. Condat, G. J. Sibona 070006

We revisit the Fisher-Shannon representation plane
${\mathcal{H}}\times{\mathcal{F}}$, evaluated using the Bandt and Pompe recipe
to assign a probability distribution to a time series. Several stochastic
dynamical (noises with $f^{-k}$, $k\geq 0$, power spectrum) and chaotic
processes (27 chaotic maps) are analyzed so as to illustrate the approach. Our
main achievement is uncovering the informational properties of the planar
location.

# Noise versus chaos in a causal Fisher-Shannon plane

Osvaldo A. Rosso  [inst1, inst2] Felipe Olivares Email<EMAIL_ADDRESS>[inst3] Angelo Plastino[inst4]

(20 November 2014; 1 April 2015)

††volume: 7

99 inst1 Insitituto Tecnológico de Buenos Aires, Av. Eduardo Madero 399,
C1106ACD Ciudad Autónoma de Buenos Aires, Argentina. inst2 Instituto de
Física, Universidade Federal de Alagoas, Maceió, Alagoas, Brazil. inst3
Departamento de Física, Facultad de Ciencias Exactas, Universidad Nacional de
La Plata, La Plata, Argentina. inst4 Instituto de Física, IFLP-CCT,
Universidad Nacional de La Plata, La Plata, Argentina.

##  1 Introduction

Temporal sequences of measurements (or observations), that is, time-series
(TS), are the basic elements for investigating natural phenomena. From TS, one
should judiciously extract information on dynamical systems. Those TS arising
from chaotic systems share with those generated by stochastic processes
several properties that make them very similar: (1) a wide-band power spectrum
(PS), (2) a delta-like autocorrelation function, (3) irregular behavior of the
measured signals, etc. Now, irregular and apparently unpredictable behavior is
often observed in natural TS, which makes interesting the establishment of
whether the underlying dynamical process is of either deterministic or
stochastic character in order to i) model the associated phenomenon and ii)
determine which are the relevant quantifiers.

Chaotic systems display “sensitivity to initial conditions” and lead to non-
periodic motion (chaotic time series). Long-term unpredictability arises
despite the deterministic character of the trajectories (two neighboring
points in the phase space move away exponentially rapidly). Let
${\mathbf{x}}_{1}(t)$ and ${\mathbf{x}}_{2}(t)$ be two such points, located
within a ball of radius $R$ at time $t$. Further, assume that these two points
cannot be resolved within the ball due to poor instrumental resolution. At
some later time $t^{\prime}$, the distance between the points will typically
grow to
$|{\mathbf{x}}_{1}(t^{\prime})-{\mathbf{x}}_{2}(t^{\prime})|\approx|{\mathbf{x}}_{1}(t)-{\mathbf{x}}_{2}(t)|~{}\exp(\lambda~{}|t^{\prime}-t|)$,
with $\lambda>0$ for a chaotic dynamics, $\lambda$ the largest Lyapunov
exponent. When this distance at time $t^{\prime}$ exceeds $R$, the points
become experimentally distinguishable. This implies that instability reveals
some information about the phase space population that was not available at
earlier times [1]. One can then think of chaos as an information source. The
associated rate of generated information can be cast in precise fashion via
the Kolmogorov-Sinai’s entropy [2, 3].

One question often emerges: is the system chaotic (low-dimensional
deterministic) or stochastic? If one is able to show that the system is
dominated by low-dimensional deterministic chaos, then only few (nonlinear and
collective) modes are required to describe the pertinent dynamics [4]. If not,
then the complex behavior could be modeled by a system dominated by a very
large number of excited modes which are in general better described by
stochastic or statistical approaches.

Several methodologies for evaluation of Lyapunov exponents and Kolmogorov-
Sinai entropies for time-series’ analysis have been proposed (see Ref. [5]),
but their applicability involves taking into account constraints
(stationarity, time series length, parameters values election for the
methodology, etc.) which in general make the ensuing results non-conclusive.
Thus, one wishes for new tools able to distinguish chaos (determinism) from
noise (stochastic) and this leads to our present interest in the computation
of quantifiers based on Information Theory, for instance, “entropy”,
“statistical complexity”, “Fisher information”, etc.

These quantifiers can be used to detect determinism in time series [6, 7, 8,
9, 10, 11]. Different Information Theory based measures (normalized Shannon
entropy, statistical complexity, Fisher information) allow for a better
distinction between deterministic chaotic and stochastic dynamics whenever
“causal” information is incorporated via the Bandt and Pompe’s (BP)
methodology [12]. For a review of BP’s methodology and its applications to
physics, biomedical and econophysic signals, see [13].

Here we revisit, for the purposes previously detailed, the so-called causality
Fisher–Shannon entropy plane, ${\mathcal{H}}\times{\mathcal{F}}$ [14], which
allows to quantify the global versus local characteristic of the time series
generated by the dynamical process under study. The two functionals
${\mathcal{H}}$ and ${\mathcal{F}}$ are evaluated using the Bandt and Pompe
permutation approach. Several stochastic dynamics (noises with $f^{-k}$,
$k\geq 0$, power spectrum) and chaotic processes (27 chaotic maps) are
analyzed so as to illustrate the methodology. We will encounter that
significant information is provided by the planar location.

##  2 Shannon entropy and Fisher information measure

Given a continuous probability distribution function (PDF) $f(x)$ with
$x\in\Delta\subset{\mathbb{R}}$ and $\int_{\Delta}f(x)~{}dx=1$, its associated
Shannon Entropy $S$ [15] is

$S[f]~{}=~{}-\int_{\Delta}~{}f~{}\ln(f)~{}dx\ ,$ (1)

a measure of “global character” that is not too sensitive to strong changes in
the distribution taking place on a small-sized region. Such is not the case
with Fisher’s Information Measure (FIM) $\mathcal{F}$ [16, 17], which
constitutes a measure of the gradient content of the distribution $f(x)$, thus
being quite sensitive even to tiny localized perturbations. It reads

$\displaystyle{\mathcal{F}}[f]$
$\displaystyle=\int_{\Delta}~{}{{1}\over{f(x)}}\left[{{df(x)}\over{dx}}\right]^{2}~{}dx$
$\displaystyle=4\int_{\Delta}~{}\left[{{d\psi(x)}\over{dx}}\right]^{2}.$ (2)

FIM can be variously interpreted as a measure of the ability to estimate a
parameter, as the amount of information that can be extracted from a set of
measurements, and also as a measure of the state of disorder of a system or
phenomenon [17]. In the previous definition of FIM (Eq. (2)), the division by
$f(x)$ is not convenient if $f(x)\rightarrow 0$ at certain $x-$values. We
avoid this if we work with real probability amplitudes $f(x)=\psi^{2}(x)$ [16,
17], which is a simpler form (no divisors) and shows that $\mathcal{F}$ simply
measures the gradient content in $\psi(x)$. The gradient operator
significantly influences the contribution of minute local $f-$variations to
FIM’s value. Accordingly, this quantifier is called a “local” one [17].

Let now $P=\\{p_{i};~{}i=1,\cdots,N\\}$ be a discrete probability
distribution, with $N$ the number of possible states of the system under
study. The concomitant problem of information-loss due to discretization has
been thoroughly studied and, in particular, it entails the loss of FIM’s
shift-invariance, which is of no importance for our present purposes [10, 11].
In the discrete case, we define a “normalized” Shannon entropy as

${\mathcal{H}}[P]~{}=~{}\frac{S[P]}{S_{max}}~{}=~{}\frac{1}{S_{max}}\left\\{-\sum_{i=1}^{N}~{}p_{i}~{}\ln(p_{i})\right\\},$
(3)

where the denominator $S_{max}=S[P_{e}]=\ln N$ is that attained by a uniform
probability distribution $P_{e}=\\{p_{i}=1/N,~{}\forall i=1,\cdots,N\\}$. For
the FIM, we take the expression in term of real probability amplitudes as
starting point, then a discrete normalized FIM convenient for our present
purposes is given by

${\mathcal{F}}[P]~{}=~{}F_{0}~{}\sum_{i=1}^{N-1}~{}[(p_{i+1})^{1/2}-(p_{i})^{1/2}]^{2}\
.$ (4)

It has been extensively discussed that this discretization is the best behaved
in a discrete environment [18]. Here, the normalization constant $F_{0}$ reads

$F_{0}~{}=~{}\left\\{\begin{array}[]{cl}1&\qquad\mbox{\footnotesize if
$p_{i^{*}}=1$ for $i^{*}=1$ or}\\\ &\qquad\mbox{\footnotesize$i^{*}=N$ and
$p_{i}=0~{}\forall i\neq i^{*}$}\\\
1/2&\qquad\mbox{otherwise}.\end{array}\right.$ (5)

If our system lies in a very ordered state, which occurs when almost all the
$p_{i}$ – values are zeros, we have a normalized Shannon entropy
${\mathcal{H}}\sim 0$ and a normalized Fisher’s Information Measure
${\mathcal{F}}\sim 1$. On the other hand, when the system under study is
represented by a very disordered state, that is when all the $p_{i}$ – values
oscillate around the same value, we obtain ${\mathcal{H}}\sim 1$ while
${\mathcal{F}}\sim 0$. One can state that the general FIM-behavior of the
present discrete version (Eq. (4)), is opposite to that of the Shannon
entropy, except for periodic motions [10, 11]. The local sensitivity of FIM
for discrete-PDFs is reflected in the fact that the specific “$i-$ordering” of
the discrete values $p_{i}$ must be seriously taken into account in evaluating
the sum in Eq. (4). This point was extensively discussed by us in previous
works [10, 11]. The summands can be regarded as a kind of “distance” between
two contiguous probabilities. Thus, a different ordering of the pertinent
summands would lead to a different FIM-value, hereby its local nature. In the
present work, we follow the lexicographic order described by Lehmer [22] in
the generation of Bandt-Pompe PDF.

##  3 Description of our chaotic and stochastic systems

Here we study both chaotic and stochastic systems, selected as illustrative
examples of different classes of signals, namely, (a) 27 chaotic dynamic maps
[9, 19] and (b) truly stochastic processes, noises with $f^{-k}$ power
spectrum [9].

###  3.1 Chaotic maps

In the present work, we consider 27 chaotic maps described by J. C. Sprott in
the appendix of his book [19]. These chaotic maps are grouped as

  * a)

Noninvertible maps: (1) Logistic map; (2) Sine map; (3) Tent map; (4) Linear
congruential generator; (5) Cubic map; (6) Ricker’s population model; (7)
Gauss map; (8) Cusp map; (9) Pinchers map; (10) Spence map; (11) Sine-circle
map;

  * b)

Dissipative maps: (12) Hénon map; (13) Lozi map; (14) Delayed logistic map;
(15) Tinkerbell map; (16) Burgers’ map; (17) Holmes cubic map; (18)
Dissipative standard map; (19) Ikeda map; (20) Sinai map; (21) Discrete
predator-prey map,

  * c)

Conservative maps: (22) Chirikov standard map; (23) Hénon area-preserving
quadratic map; (24) Arnold’s cat map; (25) Gingerbreadman map; (26) Chaotic
web map; (27) Lorenz three-dimensional chaotic map;

Even when the present list of chaotic maps is not exhaustive, it could be
taken as representative of common chaotic systems [19].

###  3.2 Noises with $f^{-k}$ power spectrum

The corresponding time series are generated as follows [20]: 1) Using the
Mersenne twister generator [21] through the $\textsc{Matlab}^{\copyright}$
RAND function we generate pseudo random numbers $y^{0}_{i}$ in the interval
$(-0.5,0.5)$ with an (a) almost flat power spectra (PS), (b) uniform PDF, and
(c) zero mean value. 2) Then, the Fast Fourier Transform (FFT) ${y^{1}_{i}}$
is first obtained and then multiplied by $f^{-k/2}$, yielding ${y^{2}_{i}}$;
3) Now, ${y^{2}_{i}}$ is symmetrized so as to obtain a real function. The
pertinent inverse FFT is now at our disposal, after discarding the small
imaginary components produced by the numerical approximations. The resulting
time series $\eta^{(k)}$ exhibits the desired power spectra and, by
construction, is representative of non-Gaussian noises.

##  4 Results and discussion

In all chaotic maps, we took (see section 3.1) the same initial conditions and
the parameter-values detailed by Sprott. The corresponding initial values are
given in the basin of attraction or near the attractor for the dissipative
systems, or in the chaotic sea for the conservative systems [19]. For each
map’s TS, we discarded the first $10^{5}$ iterations and, after that,
$N=10^{7}$ iterations-data were generated.

Stochastic dynamics represented by time series of noises with $f^{-k}$ power
spectrum ($0\leq k\leq 3.5$ and $\Delta k=0.25$) were considered. For each
value of $k$, ten series with different seeds and total length $N=10^{6}$ data
were generated (see section 3.2), and their corresponding average values were
reported for uncorrelated ($k=0$) and correlated ($k>0$) noises.

Figure 1:  Localization in the causality Fisher-Shannon plane of the 27
chaotic maps considered in the present work. The Bandt-Pompe PDF was evaluated
following the lexicographic order [22] and considering $D=6$ (pattern-length),
$\tau=1$ (time lag) and time series length $N=10^{7}$ data (initial conditions
given by Sprott [19]). The inside numbers represent the corresponding chaotic
map enumerated at the beginning of section 3.1. The letters “X” and “Y”
represent the time series coordinates maps for which their planar
representation is clearly distinguishable. The open circle-dash line
represents the planar localization (average values over ten realizations with
different seeds) for the stochastic process: noises with $f^{-k}$ power
spectrum.

The BP-PDF was evaluated for each TS of $N$ data, stochastic and chaotic,
following the lexicographic pattern-order proposed by Lehmer [22], with
pattern-lengths $D=6$ and time lag $\tau=1$. Their corresponding localization
in the causality Fisher-Shannon plane are shown in Fig. 1. One can use any of
these TS for evaluating the dynamical system’s invariants (like correlation
dimension, Lyapunov exponents, etc.), by appealing to a time lag
reconstruction [19]. Here we analyzed TS generated by each one of chaotic
maps’ coordinates when the corresponding map is bi- or multi-dimensional. Due
to the fact that the BP-PDF is not a dynamical invariant (neither are other
quantifiers derived by Information Theory), some variation could be expected
in the quantifiers’ values computed with this PDF, whenever one or other of
the TS generated by these multidimensional coordinate systems.

From Fig. 1, we clearly see that the chaotic maps under study are localized
mainly at entropic region lying between $0.35$ and $0.9$, and reach FIM values
from $0.4$ to almost $1$. A second group of chaotic maps, constituted by: the
Gauss map (7), linear congruential generator (4), dissipative standard map
(18), Sinai map (20) and Arnold’s cat map, is localized near the right-lower
corner of the ${\mathcal{H}}\times{\mathcal{F}}$ plane, that is in the range
$0.95\leq{\mathcal{H}}\leq 1.0$ and $0\leq{\mathcal{F}}\leq 0.3$. Their
localization could be understood if one takes into account that when a
2D-graphical representation of them (i.e., a graph $X_{n}\times X_{n+1}$ for
one dimensional maps, or $X_{n}\times Y_{n}$ for two dimensional maps) it
tends to fulfill the space, resembling the behavior of stochastic dynamics.
However, they are chaotic and present a clear structure when the dynamics are
represented in higher dimensional plane.

Noises with $f^{-k}$ power spectrum (with $0\leq k\leq 5$) exhibit a wide
range of entropic values ($0.1\leq{\mathcal{H}}\leq 1$) and FIM values lying
between $0\leq{\mathcal{F}}\leq 0.5$. A smooth transition in the planar
location is observed in the passage from uncorrelated noise ($k=0$ with
${\mathcal{H}}\sim 1$ and ${\mathcal{F}}\sim 0$) to correlated one ($k>0$).
The correlation degree grows as the $k$ value increases. From Fig. 1 we gather
that, for stochastic time series with increasing correlation-degree, the
associated entropic values ${\mathcal{H}}$ decrease, while Fisher’s values
${\mathcal{F}}$ increase. Taking into account that other stochastic processes,
like fBm and fGn (not shown), present a quite close behavior to the $k$-noise
analyzed here (see Ref. [11]), we can think that the open circle-dash line
represents a division of the plane; above this line all the chaotic maps are
localized. It is also interesting to note that, qualitatively, the same
results are obtained when the evaluations where made with pattern length $D=4$
and $D=5$, as well as, different Fisher information measure discretization are
used.

Summing up, we have presented an extensive series of numerical
simulations/computations and have contrasted the characterizations of
deterministic chaotic and noisy-stochastic dynamics, as represented by time
series of finite length. Surprisingly enough, one just has to look at the
different planar locations of our two dynamical regimes. The planar location
is able to tell us whether we deal with chaotic or stochastic time series.

###### Acknowledgements.

O. A. Rosso and A. Plastino were supported by Consejo Nacional de
Investigaciones Científicas y Técnicas (CONICET), Argentina. O. A. Rosso
acknowledges support as a FAPEAL fellow, Brazil. F. Olivares is supported by
Departamento de Física, Facultad de Ciencias Exactas, Universidad Nacional de
La Plata, Argentina.

## References

  * [1] H D I Abarbanel, Analysis of observed chaotic data, Springer-Verlag, New York (1996).
  * [2] A N Kolmogorov, A new metric invariant for transitive dynamical systems and automorphisms in lebesgue sapces, Dokl. Akad. Nauk. (USSR) 119, 861 (1959).
  * [3] Y G Sinai, On the concept of entropy for a dynamical system, Dokl. Akad. Nauk. (USSR) 124, 768 (1959).
  * [4] A R Osborne, A Provenzale, Finite correlation dimension for stochastic systems with power-law spectra, Physica D 35, 357 (1989).
  * [5] H Kantz, T Scheiber, Nonlinear time series analysis, Cambridge University Press, Cambridge, UK (2002).
  * [6] O A Rosso, H A Larrondo, M T Martín, A Plastino, M A Fuentes, Distinguishing noise from chaos, Phys. Rev. Lett. 99, 154102 (2007).
  * [7] O A Rosso, L C Carpi, P M Saco, M Gómez Ravetti, A Plastino, H A Larrondo, Causality and the entropy-complexity plane: Robustness and missing ordinal patters, Physica A 391, 42 (2012).
  * [8] O A Rosso, L C Carpi, P M Saco, M Gómez Ravetti, H A Larrondo, A Plastino, The Amigó paradigm of forbidden/missing patterns: A detailed analysis, Eur. Phys. J. B 85, 419 (2012).
  * [9] O A Rosso, F Olivares, L Zunino, L De Micco, A L L Aquino, A Plastino, H A Larrondo, Characterization of chaotic maps using the permutation Bandt–Pompe probability distribution, Eur. Phys. J. B 86, 116 (2013).
  * [10] F Olivares, A Plastino, O A Rosso, Ambiguities in Bandt–Pompe’s methodology for local entropic quantifiers, Physica A, 391, 2518 (2012).
  * [11] F Olivares, A Plastino, O A Rosso, Contrasting chaos with noise via local versus global information quantifiers, Phys. Lett A 376, 1577 (2012).
  * [12] C Bandt, B Pompe, Permutation entropy: A natural complexity measure for time series, Phys. Rev. Lett. 88, 174102 (2002).
  * [13] M Zanin, L Zunino, O A Rosso, D Papo, Permutation entropy and its main biomedical and econophysics applications: A review, Entropy 14, 1553 (2012).
  * [14] C Vignat, J F Bercher, Analysis of signals in the Fisher-Shannon information plane, Phys. Lett. A 312, 27 (2003).
  * [15] C Shannon, W Weaver, The mathematical theory of communication, University of Illinois Press, Champaign, USA (1949).
  * [16] R A Fisher, On the mathematical foundations of theoretical statistics, Philos. Trans. R. Soc. Lond. Ser. A 222, 309 (1922).
  * [17] B R Frieden, Science from Fisher information: A Unification, Cambridge University Press, Cambridge, UK (2004).
  * [18] P Sánchez-Moreno, R J Yánẽz, J S Dehesa, Discrete densities and Fisher information, In: Proceedings of the 14th International Conference on Difference Equations and Applications, Eds. M. Bohner, et al., Pag. 291, UğurBahçeşehir University Publishing Company, Istanbul, Turkey (2009).
  * [19] J C Sprott, Chaos and time series analysis, Oxford University Press, New York, USA (2003).
  * [20] H A Larrondo, Matab program: $noisefk.m$ (`http://www.mathworks.com/matlabcentral/`
`fileexchange/35381`) (2012).

  * [21] M Matsumoto, T Nishimura, Mersenne twister: A 623-dimensionally uniform pseudo-random number gererator, ACM T. Model. Comput. S. 8, 3 (1998).
  * [22] `http://www.keithschwarz.com/interesting/`
`code/factoradic-permutation/Factoradic`
`Permutation.hh.html`