∎

11institutetext: Corresponding Author: Ramon Fraga Pereira 22institutetext:
22email<EMAIL_ADDRESS>
# Temporally Extended Goal Recognition in Fully Observable Non-Deterministic
Domain Models

Ramon Fraga Pereira1 Francesco Fuggitti2,3,4
Felipe Meneguzzi5 Giuseppe De Giacomo3,6

1University of Manchester  UK
2IBM Research AI  USA
3Sapienza University  Italy
4York University  Canada
5University of Aberdeen  UK
6University of Oxford  UK

(Submitted: 06/2023)

###### Abstract

Goal Recognition is the task of discerning the correct intended goal that an
agent aims to achieve, given a set of goal hypotheses, a domain model, and a
sequence of observations (i.e., a sample of the plan executed in the
environment). Existing approaches assume that goal hypotheses comprise a
single conjunctive formula over a single final state and that the environment
dynamics are deterministic, preventing the recognition of temporally extended
goals in more complex settings. In this paper, we expand goal recognition to
temporally extended goals in Fully Observable Non-Deterministic (fond)
planning domain models, focusing on goals on finite traces expressed in Linear
Temporal Logic (ltlf) and Pure Past Linear Temporal Logic (ppltl). We develop
the first approach capable of recognizing goals in such settings and evaluate
it using different ltlf and ppltl goals over six fond planning domain models.
Empirical results show that our approach is accurate in recognizing temporally
extended goals in different recognition settings.

††journal: arXiv

##  1 Introduction

Goal Recognition is the task of recognizing the intentions of autonomous
agents or humans by observing their interactions in an environment. Existing
work on goal and plan recognition addresses this task over several different
types of domain settings, such as plan-libraries (Avrahami-Zilberbrand and
Kaminka, 2005), plan tree grammars (Geib and Goldman, 2009), classical
planning domain models (Ramírez and Geffner, 2009, 2010; Sohrabi et al, 2016;
Pereira et al, 2020), stochastic environments (Ramírez and Geffner, 2011),
continuous domain models (Kaminka et al, 2018), incomplete discrete domain
models (Pereira et al, 2019a), and approximate control models (Pereira et al,
2019b). Despite the ample literature and recent advances, most existing
approaches to Goal Recognition as Planning cannot recognize temporally
extended goals, i.e., goals formalized in terms of time, e.g., the exact order
that a set of facts of a goal must be achieved in a plan. Recently, Aineto et
al (2021) propose a general formulation of a temporal inference problem in
deterministic planning settings. However, most of these approaches also assume
that the observed actions’ outcomes are deterministic and do not deal with
unpredictable, possibly adversarial, environmental conditions.

Research on planning for temporally extended goals in deterministic and non-
deterministic domain settings has increased over the years, starting with the
pioneering work on planning for temporally extended goals (Bacchus and
Kabanza, 1998) and on planning via model checking (Cimatti et al, 1997). This
continued with the work on integrating ltl goals into planning tools (Patrizi
et al, 2011, 2013), and, most recently, the work of Bonassi et al (2023),
introducing a novel Pure-Past Linear Temporal Logic encoding for planning in
the Classical Planning setting. Other existing work relate ltl goals with
synthesis for planning in non-deterministic domain models, often focused on
the _finite trace_ variants of ltl (De Giacomo and Vardi, 2013, 2015; Camacho
et al, 2017, 2018; De Giacomo and Rubin, 2018; Aminof et al, 2020).

In this paper, we introduce the task of goal recognition in discrete domains
that are fully observable, and the outcomes of actions and observations are
non-deterministic, possibly adversarial, i.e., Fully Observable Non-
Deterministic (fond), allowing the formalization of temporally extended goals
using two types of temporal logic on finite traces: Linear-time Temporal Logic
(ltlf) and Pure-Past Linear-time Temporal Logic (ppltl) (De Giacomo et al,
2020).

The main contribution of this paper is three-fold. First, based on the
definition of Plan Recognition as Planning introduced in (Ramírez and Geffner,
2009), we formalize the problem of recognizing temporally extended goals
(expressed in ltlf or ppltl) in fond planning domains, handling both
stochastic (i.e., strong-cyclic plans) and adversarial (i.e., strong plans)
environments (Aminof et al, 2020). Second, we extend the probabilistic
framework for goal recognition proposed in (Ramírez and Geffner, 2010), and
develop a novel probabilistic approach that reasons over executions of
policies and returns a posterior probability distribution for the goal
hypotheses. Third, we develop a compilation approach that generates an
augmented fond planning problem by compiling temporally extended goals
together with the original planning problem. This compilation allows us to use
any off-the-shelf fond planner to perform the recognition task in fond
planning models with temporally extended goals.

We focus on fond domain models with stochastic non-determinism, and conduct an
extensive set of experiments with different complex planning problems. We
empirically evaluate our approach using different ltlf and ppltl goals over
six fond planning domain models, including a real-world non-deterministic
domain model (Nebel et al, 2013), and our experiments show that our approach
is accurate to recognize temporally extended goals in different two
recognition settings: offline recognition, in which the recognition task is
performed in “one-shot”, and the observations are given at once and may
contain missing information; and online recognition, in which the observations
are received incrementally, and the recognition task is performed gradually.

##  2 Preliminaries

In this section, we briefly recall the syntax and semantics of Linear-time
Temporal Logics on finite traces (ltlf/ppltl) and revise the concept and
terminology of fond planning.

###  2.1 LTLf and PPLTL

Linear Temporal Logic on finite traces (ltlf) is a variant of ltl introduced
in (Pnueli, 1977) interpreted over finite traces. Given a set $AP$ of atomic
propositions, the syntax of ltlf formulas $\varphi$ is defined as follows:

$\varphi::=a\mid\lnot\varphi\mid\varphi\land\varphi\mid\raisebox{-1.1625pt}{\LARGE$\circ$}\varphi\mid\varphi\mathop{\mathcal{U}}\varphi$

where $a$ denotes an atomic proposition in $AP$, $\circ$ is the next operator,
and $\mathop{\mathcal{U}}$ is the until operator. Apart from the Boolean
connectives, we use the following abbreviations: eventually as
$\Diamond\varphi\doteq\mathit{true}\mathop{\mathcal{U}}\varphi$; always as
$\Box\varphi\doteq\lnot\Diamond\lnot\varphi$; weak next
$\raisebox{-1.1625pt}{\LARGE$\bullet$}\varphi\doteq\lnot\raisebox{-1.1625pt}{\LARGE$\circ$}\lnot\varphi$.
A trace $\tau=\tau_{0}\tau_{1}\cdots$ is a sequence of propositional
interpretations, where $\tau_{m}\in 2^{AP}(m\geq 0)$ is the $m$-th
interpretation of $\tau$, and $|\tau|$ is the length of $\tau$. We denote a
finite trace formally as $\tau\in(2^{AP})^{*}$. Given a finite trace $\tau$
and an ltlf formula $\varphi$, we inductively define when $\varphi$ holds in
$\tau$ at position $i$ $(0\leq i<|\tau|)$, written $\tau,i\models\varphi$ as
follows:

  * •

$\tau,i\models a\;\text{ iff }\;a\in\tau_{i}$;

  * •

$\tau,i\models\lnot\varphi\;\text{ iff }\;\tau,i\not\models\varphi$;

  * •

$\tau,i\models\varphi_{1}\land\varphi_{2}\;\text{ iff
}\;\tau,i\models\varphi_{1}\ \text{and}\ \tau,i\models\varphi_{2}$;

  * •

$\tau,i\models\raisebox{-1.1625pt}{\LARGE$\circ$}\varphi\;\text{ iff
}\;i+1<|\tau|\ \text{and}\ \tau,i+1\models\varphi$;

  * •

$\tau,i\models\varphi_{1}\mathop{\mathcal{U}}\varphi_{2}$ iff there exists $j$
such that $i\leq j<|\tau|$ and $\tau,j\models\varphi_{2}$, and for all
$k,~{}i\leq k<j$, we have $\tau,k\models\varphi_{1}$.

An ltlf formula $\varphi$ is true in $\tau$, denoted by $\tau\models\varphi$,
iff $\tau,0\models\varphi$. As advocated in (De Giacomo et al, 2020), we also
use the pure-past version of ltlf, here denoted as ppltl, due to its
compelling computational advantage compared to ltlf when goal specifications
are naturally expressed in a past fashion. ppltl refers only to the past and
has a natural interpretation on finite traces: formulas are satisfied if they
hold in the current (i.e., last) position of the trace.

Given a set $AP$ of propositional symbols, ppltl formulas are defined by:

$\varphi::=a\mid\lnot\varphi\mid\varphi\land\varphi\mid\circleddash\varphi\mid\varphi\mathop{\mathcal{S}}\varphi$

where $a\in AP$, $\circleddash$ is the before operator, and
$\mathop{\mathcal{S}}$ is the since operator. Similarly to ltlf, common
abbreviations are the once operator
${\diamondminus}\varphi\doteq\mathit{true}\mathop{\mathcal{S}}\varphi$ and the
historically operator
${\boxminus}\varphi\doteq\lnot{\diamondminus}\lnot\varphi$. Given a finite
trace $\tau$ and a ppltl formula $\varphi$, we inductively define when
$\varphi$ holds in $\tau$ at position $i$ $(0\leq i<|\tau|)$, written
$\tau,i\models\varphi$ as follows. For atomic propositions and Boolean
operators it is as for ltlf. For past operators:

  * •

$\tau,i\models\circleddash\varphi$ iff  $i-1\geq 0$ and
$\tau,i-1\models\varphi$;

  * •

$\tau,i\models\varphi_{1}\mathop{\mathcal{S}}\varphi_{2}$ iff  there exists
$k$ such that $0\leq k\leq i$ and $\tau,k\models\varphi_{2}$, and for all $j$,
$k<j\leq i$, we have $\tau,j\models\varphi_{1}$.

A ppltl formula $\varphi$ is true in $\tau$, denoted by $\tau\models\varphi$,
if and only if $\tau,|\tau|-1\models\varphi$. A key property of temporal
logics that we exploit in this work is that, for every ltlf/ppltl formula
$\varphi$, there exists a Deterministic Finite-state Automaton (DFA)
$\mathcal{A}_{\varphi}$ accepting the traces $\tau$ satisfying $\varphi$ (De
Giacomo and Vardi, 2013; De Giacomo et al, 2020).

###  2.2 FOND Planning

(a) FOND problem example.

(b) $\pi$ to achieve 22 from 11.

Figure 1: Triangle-Tireworld domain and policy.

A Fully Observable Non-deterministic Domain planning model (fond) is a tuple
$\mathcal{D}=\langle 2^{\mathcal{F}},A,\alpha,tr\rangle$ (Geffner and Bonet,
2013), where $2^{\mathcal{F}}$ is the set of possible states and $\mathcal{F}$
is a set of fluents (atomic propositions); $A$ is the set of actions;
$\alpha(s)\subseteq A$ is the set of applicable actions in a state $s$; and
$tr(s,a)$ is the non-empty set of successor states that follow action $a$ in
state $s$. A domain $\mathcal{D}$ is assumed to be compactly represented
(e.g., in PDDL (McDermott et al, 1998)), hence its size is $|\mathcal{F}|$.
Given the set of literals of $\mathcal{F}$ as
$\mathit{Literals}(\mathcal{F})=\mathcal{F}\cup\\{\lnot f\mid
f\in\mathcal{F}\\}$, every action $a\in A$ is usually characterized by
$\langle{\mathit{Pre}}_{a},{\mathit{Eff}}_{a}\rangle$, where
${\mathit{Pre}}_{a}\subseteq\mathit{Literals}(\mathcal{F})$ is the action
preconditions, and ${\mathit{Eff}}_{a}$ is the action effects. An action $a$
can be applied in a state $s$ if the set of fluents in ${\mathit{Pre}}_{a}$
holds true in $s$. The result of applying $a$ in $s$ is a successor state
$s^{\prime}$ non-deterministically drawn from one of the
${\mathit{Eff}}^{i}_{a}$ in
${\mathit{Eff}}_{a}=\\{{\mathit{Eff}}^{1}_{a},...,{\mathit{Eff}}^{n}_{a}\\}$.
In fond planning, some actions have uncertain outcomes, such that they have
non-deterministic effects (i.e., $|tr(s,a)|\geq 1$ in all states $s$ in which
$a$ is applicable), and effects cannot be predicted in advance. PDDL expresses
uncertain outcomes using the oneof (Bryce and Buffet, 2008) keyword, as widely
used by several fond planners (Mattmüller et al, 2010; Muise et al, 2012). We
define fond planning problems as follows.

###### Definition 1

A fond planning problem is a tuple
$\mathcal{P}=\langle\mathcal{D},s_{0},G\rangle$, where $\mathcal{D}$ is a fond
domain model, $s_{0}$ is an initial assignment to fluents in $\mathcal{F}$
(i.e., initial state), and $G\subseteq\mathcal{F}$ is the goal state.

Solutions to a fond planning problem $\mathcal{P}$ are policies. A policy is
usually denoted as $\pi$, and formally defined as a partial function
$\pi:2^{\mathcal{F}}\to A$ mapping non-goal states into applicable actions
that eventually reach the goal state $G$ from the initial state $s_{0}$. A
policy $\pi$ for $\mathcal{P}$ induces a set of possible executions
$\vec{E}=\\{\vec{e}_{1},\vec{e}_{2},\dots\\}$, that are state trajectories,
possibly finite (i.e., histories) $(s_{0},\dots,s_{n})$, where $s_{i+1}\in
tr(s_{i},a_{i})$ and $a_{i}\in\alpha(s_{i})$ for $i=0,\dots,n-1$, or possibly
infinite $s_{0},s_{1},\dots$, obtained by choosing some possible outcome of
actions instructed by the policy. A policy $\pi$ is a solution to
$\mathcal{P}$ if every generated execution is such that it is finite and
satisfies the goal $G$ in its last state, i.e., $s_{n}\models G$. In this
case, we say that $\pi$ is winning. Cimatti et al (2003) define three
solutions to fond planning problems: weak, strong and strong-cyclic solutions.
We formally define such solutions in Definitions 2, 4, and 3.

###### Definition 2

A weak solution is a policy that achieves the goal state $G$ from the initial
state $s_{0}$ under at least one selection of action outcomes; namely, such
solution will have some chance of achieving the goal state $G$.

###### Definition 3

A strong-cyclic solution is a policy that guarantees to achieve the goal state
$G$ from the initial state $s_{0}$ only under the assumption of fairness111The
fairness assumption defines that all action outcomes in a given state have a
non-zero probability.. However, this type of solution may revisit states, so
the solution cannot guarantee to achieve the goal state $G$ in a fixed number
of steps.

###### Definition 4

A strong solution is a policy that is guaranteed to achieve the goal state $G$
from the initial state $s_{0}$ regardless of the environment’s non-
determinism. This type of solution guarantees to achieve the goal state $G$ in
a finite number of steps while never visiting the same state twice.

In this work, we focus on strong-cyclic solutions, where the environment acts
in an unknown but stochastic way. Nevertheless, our recognition approach
applies to strong solutions as well, where the environment is purely
adversarial (i.e., the environment may always choose effects against the
agent).

As a running example, we use the well-known fond domain model called Triangle-
Tireworld, where locations are connected by roads, and the agent can drive
through them. The objective is to drive from one location to another. However,
while driving between locations, a tire may go flat, and if there is a spare
tire in the car’s location, then the car can use it to fix the flat tire.
Figure 1(a) illustrates a fond planning problem for the Triangle-Tireworld
domain, where circles are locations, arrows represent roads, spare tires are
depicted as tires, and the agent is depicted as a car. Figure 1(b) shows a
policy $\pi$ to achieve location 22. Note that, to move from location 11 to
location 21, there are two arrows labeled with the action (move 11 21): (1)
when moving does not cause the tire to go flat; (2) when moving causes the
tire to go flat. The policy depicted in Figure 1(b) guarantees the success of
achieving location 22 despite the environment’s non-determinism.

In this work, we assume from Classical Planning that the cost is 1 for all
non-deterministic instantiated actions $a\in A$. In this example, policy
$\pi$, depicted in Figure 1(b), has two possible finite executions in the set
of executions $\vec{E}$, namely $\vec{E}=\\{\vec{e}_{0},\vec{e}_{1}\\}$, such
as:

  * •

$\vec{e}_{0}$: $[$(move 11 21), (move 21 22)$]$; and

  * •

$\vec{e}_{1}$: $[$(move 11 21), (changetire 21), (move 21 22)$]$.

##  3 FOND Planning for LTLf and PPLTL Goals

We base our approach to goal recognition in fond domains for temporally
extended goals on fond planning for ltlf and ppltl goals (Camacho et al, 2017,
2018; De Giacomo and Rubin, 2018). We formally define a fond planning problem
for ltlf/ppltl goals in Definition 5, as follows.

###### Definition 5

A fond planning problem for ltlf/ppltl goals is a tuple
$\Gamma=\langle\mathcal{D},s_{0},\varphi\rangle$, where $\mathcal{D}$ is a
standard fond domain model, $s_{0}$ is the initial state, and $\varphi$ is a
goal formula, formally represented either as an ltlf or a ppltl formula.

In fond planning for temporally extended goals, a policy $\pi$ is a partial
function $\pi:(2^{\mathcal{F}})^{+}\to A$ mapping histories, i.e., states into
applicable actions. A policy $\pi$ for $\Gamma$ achieves a temporal formula
$\varphi$ if and only if the sequence of states generated by $\pi$, despite
the non-determinism of the environment, is accepted by
$\mathcal{A}_{\varphi}$.

Key to our recognition approach is using off-the-shelf fond planners for
standard reachability goals to handle also temporally extended goals through
an encoding of the automaton for the goal into an extended planning domain
expressed in PDDL. Compiling temporally extended goals into planning domain
models has a long history in the Planning literature. In particular, Baier and
McIlraith (2006) develops _deterministic_ planning with a special first-order
quantified ltl goals on finite-state sequences.

Their technique encodes a Non-Deterministic Finite-state Automaton (NFA),
resulting from ltl formulas, into deterministic planning domains for which
Classical Planning technology can be leveraged. Our parameterization of
objects of interest is somehow similar to their approach.

Starting from Baier and McIlraith (2006), always in the context of
deterministic planning, Torres and Baier (2015) proposed a polynomial-time
compilation of ltl goals on finite-state sequences into alternating automata,
leaving non-deterministic choices to be decided at planning time. Finally,
Camacho et al (2017, 2018) built upon Baier and McIlraith (2006) and Torres
and Baier (2015), proposing a compilation in the context of fond domain models
that simultaneously determinizes on-the-fly the NFA for ltlf and encodes it
into PDDL. However, this encoding introduces a lot of bookkeeping machinery
due to the removal of any form of angelic non-determinism mismatching with the
devilish non-determinism of PDDL for fond.

Although inspired by these works, our approach differs in several technical
details. We encode the DFA directly into a non-deterministic PDDL planning
domain by taking advantage of the _parametric_ nature of PDDL domains that are
then instantiated into propositional problems when solving a specific task.
Given a fond planning problem $\Gamma$ represented in PDDL, we transform
$\Gamma$ as follows. First, we transform the temporally extended goal formula
$\varphi$ (formalized either in ltlf or ppltl) into its corresponding DFA
$\mathcal{A}_{\varphi}$ through the highly-optimized MONA tool (Henriksen et
al, 1995). Second, from $\mathcal{A}_{\varphi}$, we build a _parametric_ DFA
(PDFA), representing the lifted version of the DFA. Finally, the encoding of
such a PDFA into PDDL yields an augmented fond domain model $\Gamma^{\prime}$.
Thus, we reduce fond planning for ltlf/ppltl to a standard fond planning
problem solvable by any off-the-shelf fond planner.

###  3.1 Translation to Parametric DFA

The use of parametric DFAs is based on the following observations. In temporal
logic formulas and, hence, in the corresponding DFAs, propositions are
represented by domain fluents grounded on specific objects of interest. We can
replace these propositions with predicates using object variables and then
have a mapping function $m^{obj}$ that maps such variables into the problem
instance objects. In this way, we get a lifted and parametric representation
of the DFA, i.e., PDFA, which is merged with the domain. Here, the objective
is to capture the entire dynamics of the DFA within the planning domain model
itself. To do so, starting from the DFA we build a PDFA whose states and
symbols are the lifted versions of the ones in the DFA. Formally, to construct
a PDFA we use a mapping function $m^{obj}$, which maps the set of objects of
interest present in the DFA to a set of _free_ variables. Given the mapping
function $m^{obj}$, we can define a PDFA as follows.

###### Definition 6

Given a set of object symbols $\mathcal{O}$, and a set of free variables
$\mathcal{V}$, we define a mapping function $m$ that maps each object in
$\mathcal{O}$ with a free variable in $\mathcal{V}$.

Given a DFA and the objects of interest for $\Gamma$, we can construct a PDFA
as follows:

###### Definition 7

A PDFA is a tuple
$\mathcal{A}^{p}_{\varphi}=\langle\Sigma^{p},Q^{p},q^{p}_{0},\delta^{p},F^{p}\rangle$,
where: $\Sigma^{p}=\\{\sigma^{p}_{0},...,\sigma^{p}_{n}\\}=2^{\mathcal{F}}$ is
the alphabet of fluents; $Q^{p}$ is a nonempty set of parametric states;
$q^{p}_{0}$ is the parametric initial state;
$\delta^{p}:Q^{p}\times\Sigma^{p}\rightarrow Q^{p}$ is the parametric
transition function; $F^{p}\subseteq Q^{p}$ is the set of parametric final
states. $\Sigma^{p},Q^{p},q^{p}_{0},\delta^{p}$ and $F^{p}$ can be obtained by
applying $m^{obj}$ to all the components of the corresponding DFA.

###### Example 1

Given the ltlf formula “$\Diamond(vAt~{}51)$”, the object of interest “51” is
replaced by the object variable $x$ (i.e., $m^{obj}(51)=x$), and the
corresponding DFA and PDFA for this ltlf formula are depicted in Figures 2(a)
and 2(b).

pt$q_{0}$pt$q_{1}$pt$\lnot vAt(51)$pt$vAt(51)$pt$\top$ (a) DFA for
$\Diamond(vAt(51))$

pt$q^{p}_{0}(x)$pt$q^{p}_{1}(x)$pt$\lnot vAt(x)$pt$vAt(x)$pt$\top$ (b) PDFA
for $\Diamond(vAt(51))$

Figure 2: DFA and PDFA for $\Diamond(vAt(51))$.

When the resulting new domain is instantiated, we implicitly get back the
original DFA in the Cartesian product with the original instantiated domain.
Note that this way of proceeding is similar to what is done in (Baier and
McIlraith, 2006), where they handle ltlf goals expressed in a special fol
syntax, with the resulting automata (non-deterministic Büchi automata)
parameterized by the variables in the ltlf formulas.

###  3.2 PDFA Encoding in PDDL

Once the PDFA has been computed, we encode its components within the planning
problem $\Gamma$, specified in PDDL, thus, producing an augmented fond
planning problem
$\Gamma^{\prime}=\langle\mathcal{D}^{\prime},s^{\prime}_{0},G^{\prime}\rangle$,
where $\mathcal{D}^{\prime}=\langle
2^{\mathcal{F}^{\prime}},A^{\prime},\alpha^{\prime},tr^{\prime}\rangle$ and
$G^{\prime}$ is a propositional goal as in Classical Planning. Intuitively,
additional parts of $\Gamma^{\prime}$ are used to synchronize the dynamics
between the domain and the automaton sequentially. Specifically,
$\Gamma^{\prime}$ is composed of the following components.

#### Fluents

$\mathcal{F}^{\prime}$ has the same fluents in $\mathcal{F}$ plus fluents
representing each state of the PDFA, and a fluent called turnDomain, which
controls the alternation between domain’s actions and the PDFA’s
synchronization action. Formally,
$\mathcal{F}^{\prime}=\mathcal{F}\cup\\{q\mid q\in
Q^{p}\\}\cup\\{{\texttt{turnDomain}}\\}$.

#### Domain Actions

Actions in $A$ are modified by adding turnDomain in preconditions and the
negated turnDomain in effects:
${\mathit{Pre}}^{\prime}_{a}={\mathit{Pre}}_{a}\cup\\{{\texttt{turnDomain}}\\}$
and ${\mathit{Eff}}^{\prime}_{a}={\mathit{Eff}}_{a}\cup$
$\\{\lnot{\texttt{turnDomain}}\\}$ for all $a\in A$.

#### Transition Operator

The _transition_ function $\delta^{p}$ of a PDFA is encoded as a new domain
operator with conditional effects, called trans. Namely, we have
${\mathit{Pre}}_{{\texttt{trans}}}=\\{\lnot{\texttt{turnDomain}}\\}$ and
${\mathit{Eff}}_{{\texttt{trans}}}=\\{{\texttt{turnDomain}}\\}\cup\\{{\texttt{{when}}}~{}(q^{p},\sigma^{p}),{\texttt{{then}}}~{}\delta^{p}(q^{p},\sigma^{p})\cup\\{\lnot
q\mid q\neq q^{p},q\in Q^{p}\\}\\}$, for all
$(q^{p},\sigma^{p})\in\delta^{p}$. To exemplify how the transition PDDL
operator is obtained, Listing 1 reports the transition operator for the PDFA
in Figure 2(b).

⬇

(:action trans

:parameters (?x - location)

:precondition (not (turnDomain))

:effect (and

(when (and (q0 ?x) (not (vAt ?x)))

(and (q0 ?x) (not (q1 ?x)) (turnDomain))

(when (or (and (q0 ?x) (vAt ?x)) (q1 ?x))

(and (q1 ?x) (not (q0 ?x))

(turnDomain))))

Listing 1: Transition PDDL operator for $\Diamond(vAt(x))$

#### Initial and Goal States

The new initial condition is specified as
$s^{\prime}_{0}=s_{0}\cup\\{q^{p}_{0}\\}\cup\\{{\texttt{turnDomain}}\\}$. This
comprises the initial condition of the previous domain $D$ ($s_{0}$) plus the
initial state of the PDFA and the predicate turnDomain. Considering the
example in Figure 1(a) and the PDFA in Figure 2(b), the new initial condition
is as follows in PDDL:

⬇

(:init (and (road 11 21) (road 11 21) …

(spare-in 21) (spare-in 12) …

(q0 51) (turnDomain)))

Listing 2: PDDL initial condition for $\varphi=\Diamond(vAt(51))$

The new goal condition is specified as $G^{\prime}=\\{\bigvee q_{i}\mid
q_{i}\in F^{p}\\}\cup\\{{\texttt{turnDomain}}\\}$, i.e., we want the PDFA to
be in one of its accepting states and turnDomain, as follows:

⬇

(:goal (and (q1 51) (turnDomain)))

Listing 3: PDDL goal condition for $\varphi=\Diamond(vAt(51))$

We note that, both in the initial and goal conditions of the new planning
problem, PDFA states are grounded back on the objects of interest thanks to
the inverse of the mapping $m^{obj}$.

Executions of a policy for our new fond planning problem $\Gamma^{\prime}$ are
$\vec{e}^{\prime}:[a^{\prime}_{1},t_{1},a^{\prime}_{2},t_{2},\dots,a^{\prime}_{n},t_{n}]$,
where $a^{\prime}_{i}\in A^{\prime}$ are the real domain actions, and
$t_{1},\dots,t_{n}$ are sequences of synchronization trans actions, which, at
the end, can be easily removed to extract the desired execution
$\vec{e}:[a^{\prime}_{1},a^{\prime}_{2},\dots,a^{\prime}_{n}]$. In the
remainder of the paper, we refer to the compilation just exposed as fond4ltlf.

#### Theoretical Property of the PDDL Encoding

We now study the theoretical properties of the encoding presented in this
section. Theorem 3.1 states that solving fond planning for ltlf/ppltl goals
amounts to solving standard fond planning problems for reachability goals. A
policy for the former can be easily derived from a policy of the latter.

###### Theorem 3.1

Let $\Gamma$ be a fond planning problem with an ltlf/ppltl goal $\varphi$, and
$\Gamma^{\prime}$ be the compiled fond planning problem with a reachability
goal state. Then, $\Gamma$ has a policy $\pi:(2^{\mathcal{F}})^{+}\to A$ iff
$\Gamma^{\prime}$ has a policy
$\pi^{\prime}:(2{{}^{\mathcal{F}}}^{\prime})^{+}\to A^{\prime}$.

###### Proof

($\longrightarrow$). We start with a policy $\pi$ of the original problem that
is winning by assumption. Given $\pi$, we can always build a new policy, which
we call $\pi^{\prime}$, following the encoding presented in Section 3 of the
paper. The newly constructed policy will modify histories of $\pi$ by adding
fluents and an auxiliary deterministic action trans, both related to the DFA
associated with the ltlf/ppltl formula $\varphi$. Now, we show that
$\pi^{\prime}$ is an executable policy and that is winning for
$\Gamma^{\prime}$. To see the executability, we can just observe that, by
construction of the new planning problem $\Gamma^{\prime}$, all action effects
${\mathit{Eff}}_{a^{\prime}}$ of the original problem $\Gamma$ are modified in
a way that all action effects of the original problem $\Gamma$ are not
modified and that the auxiliary action trans only changes the truth value of
additional fluents given by the DFA $\mathcal{A}^{p}_{\varphi}$ (i.e.,
automaton states). Therefore, the newly constructed policy $\pi^{\prime}$ can
be executed. To see that $\pi^{\prime}$ is winning and satisfies the
ltlf/ppltl goal formula $\varphi$, we reason about all possible executions.
For all executions, every time the policy $\pi^{\prime}$ stops we can always
extract an induced state trajectory of length $n$ such that its last state
$s^{\prime}_{n}$ will contain one of the final states $F^{p}$ of the automaton
$\mathcal{A}^{p}_{\varphi}$. This means that the induced state trajectory is
accepted by the automaton $\mathcal{A}^{p}_{\varphi}$. Then, by Theorem De
Giacomo and Vardi (2013); De Giacomo et al (2020), we have that
$\tau\models\varphi$.

($\longleftarrow$). From a winning policy $\pi^{\prime}$ for the compiled
problem, we can always project out all automata auxiliary trans actions
obtaining a corresponding policy $\pi$. We need to show that the resulting
policy $\pi$ is winning, namely, it can be successfully executed on the
original problem $\Gamma$ and satisfies the ltlf/ppltl goal formula $\varphi$.
The executability follows from the fact that the deletion of trans actions and
related auxiliary fluents from state trajectories induced by $\pi$ does not
modify any precondition/effect of original domain actions (i.e.,
$a\in\mathcal{A}$). Hence, under the right preconditions, any domain action
can be executed. Finally, the satisfaction of the ltlf/ppltl formula $\varphi$
follows directly from Theorem De Giacomo and Vardi (2013); De Giacomo et al
(2020). Indeed, every execution of the winning policy $\pi^{\prime}$ stops
when reaching one of the final states $F^{p}$ of the automaton
$\mathcal{A}^{p}_{\varphi}$ in the last state $s_{n}$, thus every execution of
$\pi$ would satisfy $\varphi$. Thus, the thesis holds.

##  4 Goal Recognition in FOND Planning Domains with LTLf and PPLTL Goals

We now introduce our recognition approach that is able to recognizing
temporally extended (ltlf and ppltl) goals in fond planning domains. Our
approach extends the probabilistic framework of Ramírez and Geffner (2010) to
compute posterior probabilities over temporally extended goal hypotheses, by
reasoning over the set of possible executions of policies $\pi$ and the
observations. Our goal recognition approach works in two stages: the
compilation stage and the recognition stage. In the next sections, we describe
in detail how these two stages work. Figure 3 illustrates how our approach
works.

Figure 3: Overview of our solution approach.

###  4.1 Goal Recognition Problem

We define the task of goal recognition in fond planning domains with ltlf and
ppltl goals by extending the standard definition of Plan Recognition as
Planning (Ramírez and Geffner, 2009), as follows.

###### Definition 8

A goal recognition problem in a fond planning setting with temporally extended
goals (ltlf and/or ppltl) is a tuple
$\mathcal{T}_{\varphi}=\langle\mathcal{D},s_{0},\mathcal{G}_{\varphi},Obs\rangle$,
where: $\mathcal{D}=\langle 2^{\mathcal{F}},A,\alpha,tr\rangle$ is a fond
planning domain; $s_{0}$ is the initial state;
$\mathcal{G}_{\varphi}=\\{\varphi_{0},\varphi_{1},...,\varphi_{n}\\}$ is the
set of goal hypotheses formalized in ltlf or ppltl, including the intended
goal $\varphi^{*}\in\mathcal{G}_{\varphi}$; $Obs=\langle
o_{0},o_{1},...,o_{n}\rangle$ is a sequence of successfully executed (non-
deterministic) actions of a policy $\pi_{\varphi^{*}}$ that achieves the
intended goal $\varphi^{*}$, s.t. $o_{i}\in A$.

Since we deal with non-deterministic domain models, an observation sequence
$Obs$ corresponds to a successful execution $\vec{e}$ in the set of all
possible executions $\vec{E}$ of a strong-cyclic policy $\pi$ that achieves
the actual intended hidden goal $\varphi^{*}$. In this work, we assume two
recognition settings: Offline Keyhole Recognition, and Online Recognition. In
Offline Keyhole Recognition the observed agent is completely unaware of the
recognition process (Armentano and Amandi, 2007), the observation sequence
$Obs$ is given at once, and it can be either full or partial—in a full
observation sequence, we observe all actions of an agent’s plan, whereas, in a
partial observation sequence, only a sub-sequence thereof. By contrast, in
Online Recognition (Vered et al, 2016), the observed agent is also unaware of
the recognition process, but the observation sequence is revealed
incrementally instead of being given in advance and at once, as in Offline
Recognition, thus making the recognition process an already much harder task.

An “ideal” solution for a goal recognition problem comprises a selection of
the goal hypotheses containing only the single actual intended hidden goal
$\varphi^{*}\in\mathcal{G}$ that the observation sequence $Obs$ of a plan
execution achieves (Ramírez and Geffner, 2009, 2010). Fundamentally, there is
no exact solution for a goal recognition problem, but it is possible to
produce a probability distribution over the goal hypotheses and the
observations, so that the goals that “best” explain the observation sequence
are the most probable ones. We formally define a solution to a goal
recognition problem in fond planning with temporally extended goals in
Definition 9.

###### Definition 9

Solving a goal recognition problem $\mathcal{T}_{\varphi}$ requires selecting
a temporally extended goal hypothesis $\hat{\varphi}\in\mathcal{G}_{\varphi}$
such that $\hat{\varphi}=\varphi^{*}$, and it represents how well
$\hat{\varphi}$ predicts or explains what observation sequence $Obs$ aims to
achieve.

Existing recognition approaches often return either a probability distribution
over the set of goals (Ramírez and Geffner, 2010; Sohrabi et al, 2016), or
scores associated with each possible goal hypothesis (Pereira et al, 2020).
Here, we return a probability distribution $\mathbb{P}$ over the set of
temporally extended goals $\mathcal{G}_{\varphi}$ that “best” explains the
observations sequence $Obs$.

###  4.2 Probabilistic Goal Recognition

We now recall the probabilistic framework for Plan Recognition as Planning
proposed in Ramírez and Geffner (2010). The framework sets the probability
distribution for every goal $G$ in the set of goal hypotheses $\mathcal{G}$,
and the observation sequence $Obs$ to be a Bayesian posterior conditional
probability, as follows:

$\displaystyle\mathbb{P}(G\mid Obs)=\eta*\mathbb{P}(Obs\mid G)*\mathbb{P}(G)$
(1)

where $\mathbb{P}(G)$ is the _a priori_ probability assigned to goal $G$,
$\eta$ is a normalization factor inversely proportional to the probability of
$Obs$, and $\mathbb{P}(Obs\mid G)$ is

$\displaystyle\mathbb{P}(Obs\mid
G)=\sum_{\pi}\mathbb{P}(Obs\mid\pi)*\mathbb{P}(\pi\mid G)$ (2)

$\mathbb{P}(Obs\mid\pi)$ is the probability of obtaining $Obs$ by executing a
policy $\pi$ and $\mathbb{P}(\pi\mid G)$ is the probability of an agent
pursuing $G$ to select $\pi$. Next, we extend the probabilistic framework
above to recognize temporally extended goals in fond planning domain models.

###  4.3 Compilation Stage

We perform a compilation stage that allows us to use any off-the-shelf fond
planner to extract policies for temporally extended goals. To this end, we
compile and generate new fond planning domain models $\Gamma^{\prime}$ for the
set of possible temporally extended goals $\mathcal{G}_{\varphi}$ using the
compilation approach described in Section 3. Specifically, for every goal
$\varphi\in\mathcal{G}_{\varphi}$, our compilation takes as input a fond
planning problem $\Gamma$, where $\Gamma$ contains the fond planning domain
$\mathcal{D}$ along with an initial state $s_{0}$ and a temporally extended
goal $\varphi$. Finally, as a result, we obtain a new fond planning problem
$\Gamma^{\prime}$ associated with the new domain $\mathcal{D}^{\prime}$. Note
that such a new fond planning domain $\Gamma^{\prime}$ encodes new predicates
and transitions that allow us to plan for temporally extended goals by using
off-the-shelf fond planners.

###### Corollary 1

Let $\mathcal{T}_{\varphi}$ be a goal recognition problem over a set of
ltlf/ppltl goals $\mathcal{G}_{\varphi}$ and let $\mathcal{T^{\prime}}$ be the
compiled goal recognition problem over a set of propositional goals
$\mathcal{G}$. Then, if $\mathcal{T^{\prime}}$ has a set of winning policies
that solve the set of propositional goals in $\mathcal{G}$, then
$\mathcal{T}_{\varphi}$ has a set of winning policies that solve its
ltlf/ppltl goals.

###### Proof

From Theorem 1 we have a bijective mapping between policies of fond planning
for ltlf/ppltl goals and policies of standard fond planning. Therefore, the
thesis holds.

###  4.4 Recognition Stage

The stage in which we perform the goal recognition task comprises extracting
policies for every goal $\varphi\in\mathcal{G}_{\varphi}$. From such policies
along with observations $Obs$, we compute posterior probabilities for the
goals $\mathcal{G}_{\varphi}$ by matching the observations with all possible
executions in the set of executions $\vec{E}$ of the policies. To ensure
compatibility with the policies, we assume the recognizer knows the preference
relation over actions for the observed agent when unrolling the policy during
search.

#### Computing Policies and the Set of Executions $\vec{E}$ for
$\mathcal{G}_{\varphi}$

We extract policies for every goal $\varphi\in\mathcal{G}_{\varphi}$ using the
new fond planning domain models $\Gamma^{\prime}$, and for each of these
policies, we enumerate the set of possible executions $\vec{E}$. The aim of
enumerating the possible executions $\vec{E}$ for a policy $\pi$ is to attempt
to infer what execution $\vec{e}\in\vec{E}$ the observed agent is performing
in the environment. Environmental non-determinism prevents the recognizer from
determining the specific execution $\vec{e}$ the observed agent goes through
to achieve its goals. The recognizer considers possible executions that are
all paths to the goal with no repeated states. This assumption is partially
justified by the fact that the probability of entering loops multiple times is
low, and relaxing it is an important research direction for future work.

After enumerating the set of possible executions $\vec{E}$ for a policy $\pi$,
we compute the average distance of all actions in the set of executions
$\vec{E}$ to the goal state $\varphi$ from initial state $s_{0}$. We note that
strong-cyclic solutions may have infinite possible executions. However, here
we consider executions that do not enter loops, and for those entering
possible loops, we consider only the ones entering loops at most once. Indeed,
the computation of the average distance is not affected by the occurrence of
possibly repeated actions. In other words, if the observed agent executes the
same action repeatedly often, it does not change its distance to the goal. The
average distance aims to estimate “how far” every observation $o\in Obs$ is to
a goal state $\varphi$. This average distance is computed because some
executions $\vec{e}\in\vec{E}$ may share the same action in execution
sequences but at different time steps. We refer to this average distance as
$\mathbf{d}$. For example, consider the policy $\pi$ depicted in Figure 1(b).
This policy $\pi$ has two possible executions for achieving the goal state
from the initial state, and these two executions share some actions, such as
(move 11 21). In particular, this action appears twice in Figure 1(b) due to
its uncertain outcome. Therefore, this action has two different distances (if
we count the number of remaining actions towards the goal state) to the goal
state: $distance=1$, if the outcome of this action generates the state
$s_{2}$; and $distance=2$, if the outcome of this action generates the state
$s_{3}$. Hence, since this policy $\pi$ has two possible executions, and the
sum of the distances is 3, the average distance for this action to the goal
state is $\mathbf{d}=1.5$. The average distances for the other actions in this
policy are: $\mathbf{d}=1$ for (changetire 21), because it appears only in one
execution; and $\mathbf{d}=0$ for (move 21 22), because the execution of this
action achieves the goal state.

We use $\mathbf{d}$ to compute an _estimated score_ that expresses “how far”
every observed action in the observation sequence $Obs$ is to a temporally
extended goal $\varphi$ in comparison to the other goals in the set of goal
hypotheses $\mathcal{G}_{\varphi}$. This means that the goal(s) with the
lowest score(s) along the execution of the observed actions $o\in Obs$ is
(are) the one(s) that, most likely, the observation sequence $Obs$ aims to
achieve. We note that, the average distance $\mathbf{d}$ for those
observations $o\in Obs$ that are not in the set of executions $\vec{E}$ of a
policy $\pi$, is set to a large constant number, i.e., to $\mathbf{d}=e^{5}$.
As part of the computation of this estimated score, we compute a _penalty
value_ that directly affects the estimated score. This _penalty value_
represents a penalization that aims to increase the estimated score for those
goals in which each pair of subsequent observations $\langle
o_{i-1},o_{i}\rangle$ in $Obs$ does not have any relation of order in the set
of executions $\vec{E}$ of these goals. We use the Euler constant $e$ to
compute this penalty value, formally defined as
$e^{\mathbf{p}(o_{i-1},o_{i})}$, in which we use $\mathcal{R}(\vec{e})$ as the
set of order relation of an execution $\vec{e}$, where

$\centering\mathbf{p}(o_{i-1},o_{i})=\begin{cases}1,&\text{if
}\\{\forall\vec{e}\in E|\langle o_{i-1}\prec
o_{i}\rangle\notin\mathcal{R}(\vec{e})\\}\\\
0,&\text{otherwise}\end{cases}\@add@centering$ (3)

Equation 4 formally defines the computation of the _estimated score_ for every
goal $\varphi\in\mathcal{G}_{\varphi}$ given a pair of subsequent observations
$\langle o_{i-1},o_{i}\rangle$, and the set of goal hypotheses
$\mathcal{G}_{\varphi}$.

$\frac{\mathit{e^{\mathbf{p}(o_{i-1},o_{i})}}*\mathbf{d}(o_{i},\varphi)}{\sum_{\varphi^{\prime}\in\mathcal{G}_{\varphi}}\mathbf{d}(o_{i},\varphi^{\prime})}$
(4)

Figure 4: Recognition problem example.

###### Example 2

To exemplify how we compute the estimated score for every goal
$\varphi\in\mathcal{G}_{\varphi}$, consider the recognition problem in Figure
4: $s_{0}$ is $vAt(11)$; the goal hypotheses $\mathcal{G}_{\varphi}$ are
expressed as ltlf goals, such that $\varphi_{0}=\Diamond
vAt(51),\varphi_{1}=\Diamond vAt(33)$, and $\varphi_{2}=\Diamond vAt(15)$;
$Obs=\\{o_{0}:{{\texttt{(move 11 21)}}},o_{1}:{{\texttt{(changetire
22)}}}\\}$. The intended goal $\varphi^{*}$ is $\varphi_{1}$. Before computing
the estimated score for the goals, we first perform the compilation process
presented before. Afterward, we extract policies for every goal
$\varphi\in\mathcal{G}_{\varphi}$, enumerate the possible executions $\vec{E}$
for the goals $\mathcal{G}_{\varphi}$ from the extracted policies, and then
compute the average distance $\mathbf{d}$ of all actions in the set of
executions $\vec{E}$ for the goals $\mathcal{G}_{\varphi}$ from $s_{0}$. The
number of possible executions $\vec{E}$ for the goals are:
$\varphi_{0}:|\vec{E}|=8,\varphi_{1}:|\vec{E}|=8$, and
$\varphi_{2}=|\vec{E}|=16$. The average distances $\mathbf{d}$ of all actions
in $\vec{E}$ for the goals are as follows:

  * •

$\varphi_{0}$: (move 11 21) = 4.5, (changetire 21) = 4, (move 21 31) = 3,
(changetire 31) = 2.5, (move 31 41) = 1.5, (changetire 41) = 1, (move 41 51) =
0;

  * •

$\varphi_{1}$: (move 11 21) = 4.5, (changetire 21) = 4, (move 21 22) = 3,
(changetire 22) = 2.5, (move 22 23) = 1.5, (changetire 23) = 1, (move 23 33):
0;

  * •

$\varphi_{2}$: (move 11 21) = 6, changetire 21) = 5.5, (move 21 22) = 4.5,
(changetire 22) = 4, (move 22 23) = 3, (changetire 23) = 2.5, (changetire 24)
= 1, (move 23 24) = 1.5, (move 24 15) = 0.

Once we have the average distances $\mathbf{d}$ of the actions in $\vec{E}$
for all goals, we can then compute the estimated score for
$\mathcal{G}_{\varphi}$ for every observation $o\in Obs$: $o_{0}{\texttt{(move
11 21)}}:\varphi_{0}=\frac{4.5}{4.5+6}=$ 0.43,
$\varphi_{1}=\frac{4.5}{4.5+6}=$ 0.43, $\varphi_{2}=\frac{6}{4.5+6}=$ 0.57;
and $o_{1}{\texttt{(changetire 22)}}:\varphi_{0}=\frac{e^{1}*e^{5}}{6.5}=$
61.87, $\varphi_{1}=\frac{2.5}{e^{5}+2.5}=$ 0.016,
$\varphi_{2}=\frac{4}{e^{5}+4}=$ 0.026. Note that for the observation $o_{1}$,
the average distance $\mathbf{d}$ for $\varphi_{0}$ is $e^{5}=148.4$ because
this observation is not an action for one of the executions in the set of
executions for this goal ($Obs$ aims to achieve the intended goal
$\varphi^{*}=\varphi_{1}$). Furthermore, the penalty value is applied to
$\varphi_{0}$, i.e., $e^{1}=2.71$. We can see that the estimated score of the
intended goal $\varphi_{1}$ is always the lowest for all observations $Obs$,
especially when we observe the second observation $o_{1}$. Note that our
approach correctly infers the intended goal $\varphi^{*}$, even when observing
with just few actions.

#### Computing Posterior Probabilities for $\mathcal{G}_{\varphi}$

To compute the posterior probabilities over the set of possible temporally
extended goals $\mathcal{G}_{\varphi}$, we start by computing the average
estimated score for every goal $\varphi\in\mathcal{G}_{\varphi}$ for every
observation $o\in Obs$, and we formally define this computation as
$\mathcal{E}(\varphi,Obs,\mathcal{G}_{\varphi})$, as follows:

$\mathcal{E}(\varphi,Obs,\mathcal{G}_{\varphi})=\left(\frac{\displaystyle\sum_{i=0}^{|Obs|}\frac{\mathit{e^{\mathbf{p}(o_{i-1},o_{i})}}*\mathbf{d}(o_{i},\varphi)}{\sum_{\varphi^{\prime}\in\mathcal{G}_{\varphi}}\mathbf{d}(o_{i},\varphi^{\prime})}}{|Obs|}\right)$
(5)

The average estimated score $\mathcal{E}$ aims to estimate “how far” a goal
$\varphi$ is to be achieved compared to other goals
($\mathcal{G}_{\varphi}\setminus\\{\varphi\\}$) _averaging_ among all the
observations in $Obs$. The lower the average estimated score $\mathcal{E}$ to
a goal $\varphi$, the more likely such a goal is to be the one that the
observed agent aims to achieve. Consequently, $\mathcal{E}$ has two important
properties defined in Equation 5, as follows.

###### Proposition 1

Given that the sequence of observations $Obs$ corresponds to an execution
$\vec{e}\in\vec{E}$ that aims to achieve the actual intended hidden goal
${\varphi}^{*}\in\mathcal{G}_{\varphi}$, the average estimated score outputted
by $\mathcal{E}$ will tend to be the lowest for ${\varphi}^{*}$ in comparison
to the scores of the other goals
($\mathcal{G}_{\varphi}\setminus\\{{\varphi}^{*}\\}$), as observations
increase in length.

###### Proposition 2

If we restrict the recognition setting and define that the goal hypotheses
$\mathcal{G}_{\varphi}$ are not sub-goals of each other, and observe all
observations in $Obs$ (i.e., full observability), we will have the intended
goal ${\varphi}^{*}$ with the lowest score among all goals, i.e.,
$\forall\varphi\in\mathcal{G}_{\varphi}$ is the case that
$\mathcal{E}({\varphi}^{*},Obs,\mathcal{G}_{\varphi})\leq\mathcal{E}(\varphi,Obs,\mathcal{G}_{\varphi})$.

After defining how we compute the average estimated score $\mathcal{E}$ for
the goals using Equation 5, we can define how our approach tries to maximize
the probability of observing a sequence of observations $Obs$ for a given goal
$\varphi$, as follows:

$\centering\mathbb{P}(Obs\mid\varphi)=[1+\mathcal{E}(\varphi,Obs,\mathcal{G}_{\varphi})]^{-1}\@add@centering$
(6)

Thus, by using the estimated score in Equation 6, we can infer that the goals
$\varphi\in\mathcal{G}_{\varphi}$ with the lowest estimated score will be the
most likely to be achieved according to the probability interpretation we
propose in Equation 5. For instance, consider the goal recognition problem
presented in Example 2, and the estimated scores we computed for the
temporally extended goals $\varphi_{0}$, $\varphi_{1}$, and $\varphi_{2}$
based on the observation sequence $Obs$. From this, we have the following
probabilities $\mathbb{P}(Obs\mid\varphi)$ for the goals:

  * •

$\mathbb{P}(Obs\mid\varphi_{0})=[1+(31.15)]^{-1}=0.03$

  * •

$\mathbb{P}(Obs\mid\varphi_{1})=[1+(0.216)]^{-1}=0.82$

  * •

$\mathbb{P}(Obs\mid\varphi_{2})=[1+(0.343)]^{-1}=0.74$

After normalizing these computed probabilities using the normalization factor
$\eta$222$\eta=[\sum_{\varphi\in\mathcal{G}_{\varphi}}\mathbb{P}(Obs\mid\varphi)*\mathbb{P}(\varphi)]^{-1}$,
and assuming that the prior probability $\mathbb{P}(\varphi)$ is equal to
every goal in the set of goals $\mathcal{G}_{\varphi}$, we can use Equation 6
to compute the posterior probabilities (Equation 1) for the temporally
extended goals $\mathcal{G}_{\varphi}$. We define the solution to a
recognition problem $\mathcal{T}_{\varphi}$ (Definition 8) as a set of
temporally extended goals $\mathcal{G}_{\varphi}^{*}$ with the maximum
probability, formally:
$\mathcal{G}_{\varphi}^{*}=\operatorname*{arg\,max}_{\varphi\in\mathcal{G}_{\varphi}}\mathbb{P}(\varphi\mid
Obs)$. Hence, considering the normalizing factor $\eta$ and the probabilities
$\mathbb{P}(Obs\mid\varphi)$ computed before, we then have the following
posterior probabilities for the goals in Example 2:
$\mathbb{P}(\varphi_{0}\mid Obs)=0.001$; $\mathbb{P}(\varphi_{1}\mid
Obs)=0.524$; and $\mathbb{P}(\varphi_{2}\mid Obs)=0.475$. Recall that in
Example 2, $\varphi^{*}$ is $\varphi_{1}$, and according to the computed
posterior probabilities, we then have
$\mathcal{G}_{\varphi}^{*}=\\{\varphi_{1}\\}$, so our approach yields only the
correct intended goal by observing just two observations.

Using the average distance $\mathbf{d}$ and the penalty value $\mathbf{p}$
allows our approach to disambiguate similar goals during the recognition
stage. For instance, consider the following possible temporally extended
goals: $\varphi_{0}=\phi_{1}\mathop{\mathcal{U}}\phi_{2}$ and
$\varphi_{1}=\phi_{2}\mathop{\mathcal{U}}\phi_{1}$. Here, both goals have the
same formulas to be achieved, i.e., $\phi_{1}$ and $\phi_{2}$, but in a
different order. Thus, even having the same formulas to be achieved, the
sequences of their policies’ executions are different. Therefore, the average
distances are also different, possibly a smaller value for the temporally
extended goal that the agent aims to achieve, and the penalty value may also
be applied to the other goal if two subsequent observations do not have any
order relation in the set of executions for this goal.

#### Computational Analysis

The most expensive computational part of our recognition approach is computing
the policies $\pi$ for the goal hypotheses $\mathcal{G}_{\varphi}$. Thus, we
can say that our approach requires $|\mathcal{G}_{\varphi}|$ calls to an off-
the-shelf fond planner. Hence, the computational complexity of our recognition
approach is linear in the number of goal hypotheses $|\mathcal{G}_{\varphi}|$.
In contrast, to recognize goals and plans in Classical Planning settings, the
approach of Ramírez and Geffner (2010) requires $2*|\mathcal{G}|$ calls to an
off-the-shelf Classical planner. Concretely, to compute $\mathbb{P}(Obs\mid
G)$, Ramirez and Geffner’s approach computes two plans for every goal and
based on these two plans, they compute a cost-difference between these plans
and plug it into a Boltzmann equation. For computing these two plans, this
approach requires a non-trivial transformation process that modifies both the
domain and problem, i.e., an augmented domain and problem that compute a plan
that complies with the observations, and another augmented domain and problem
to compute a plan that does not comply with the observations. Essentially, the
intuition of Ramirez and Geffner’s approach is that the lower the cost-
difference for a goal, the higher the probability for this goal, much similar
to the intuition of our estimated score $\mathcal{E}$.

##  5 Experiments and Evaluation

We now present experiments and evaluations carried out to validate the
effectiveness of our recognition approach. We empirically evaluate our
approach over thousands of goal recognition problems using well-known fond
planning domain models with different types of temporally extended goals
expressed in ltlf and ppltl.

The source code of our PDDL encoding for ltlf and ppltl
goals333https://github.com/whitemech/FOND4LTLf and our temporally extended
goal recognition approach444https://github.com/ramonpereira/goal-recognition-
ltlf_pltlf-fond, as well as the recognition datasets and results are available
on GitHub.

###  5.1 Domains, Recognition Datasets, and Setup

For experiments and evaluation, we use six different fond planning domain
models, in which most of them are commonly used in the AI Planning community
to evaluate fond planners (Mattmüller et al, 2010; Muise et al, 2012), such
as: Blocks-World, Logistics, Tidy-up, Tireworld, Triangle-Tireworld, and Zeno-
Travel. The domain models involve practical real-world applications, such as
navigating, stacking, picking up and putting down objects, loading and
unloading objects, loading and unloading objects, and etc. Some of the domains
combine more than one of the characteristics we just described, namely,
Logistics, Tidy-up (Nebel et al, 2013), and Zeno-Travel, which involve
navigating and manipulating objects in the environment. In practice, our
recognition approach is capable of recognizing not only the set of facts of a
goal that an observed agent aims to achieve from a sequence of observations,
but also the temporal order (e.g., exact order) in which the agent aims to
achieve this set of facts. For instance, for Tidy-up, is a real-world
application domain, in which the purpose is defining planning tasks for a
household robot that could assist elder people in smart-home application, our
approach would be able to monitor and assist the household robot to achieve
its goals in a specific order.

Based on these fond planning domain models, we build different recognition
datasets: a baseline dataset using conjunctive goals ($\phi_{1}\land\phi_{2}$)
and datasets with ltlf and ppltl goals.

For the ltlf datasets, we use three types of goals:

  * •

$\Diamond\phi$, where $\phi$ is a propositional formula expressing that
eventually $\phi$ will be achieved. This temporal formula is analogous to a
conjunctive goal;

  * •

$\Diamond(\phi_{1}\land\raisebox{-1.1625pt}{\LARGE$\circ$}(\Diamond\phi_{2}))$,
expressing that $\phi_{1}$ must hold before $\phi_{2}$ holds. For instance, we
can define a temporal goal that expresses the order in which a set of packages
in Logistics domain should be delivered;

  * •

$\phi_{1}\mathop{\mathcal{U}}\phi_{2}$: $\phi_{1}$ must hold until $\phi_{2}$
is achieved. For the Tidy-up domain, we can define a temporal goal that no one
can be in the kitchen until the robot cleans the kitchen.

For the ppltl datasets, we use two types of goals:

  * •

$\phi_{1}\land{\diamondminus}\phi_{2}$, expressing that $\phi_{1}$ holds and
$\phi_{2}$ held once. For instance, in the Blocks-World domain, we can define
a past temporal goal that only allows stacking a set of blocks (a, b, c) once
another set of blocks has been stacked (d, e);

  * •

$\phi_{1}\land(\lnot\phi_{2}\mathop{\mathcal{S}}\phi_{3})$, expressing that
the formula $\phi_{1}$ holds and since $\phi_{3}$ held $\phi_{2}$ was not true
anymore. For instance, in Zeno-Travel, we can define a past temporal goal
expressing that person$1$ is at city$1$ and since the person$2$ is at city$1$,
the aircraft must not pass through city$2$ anymore.

Thus, in total, we have six different recognition datasets over the six fond
planning domains and temporal formulas presented above. Each of these datasets
contains hundreds of recognition problems ($\approx$ 390 recognition problems
per dataset), such that each recognition problem $\mathcal{T}_{\varphi}$ in
these datasets is comprised of a fond planning domain model $\mathcal{D}$, an
initial state $s_{0}$, a set of possible goals $\mathcal{G}_{\varphi}$
(expressed in either ltlf or ppltl), the actual intended hidden goal in the
set of possible goals $\varphi^{*}\in\mathcal{G}_{\varphi}$, and the
observation sequence $Obs$. We note that the set of possible goals
$\mathcal{G}_{\varphi}$ contains very similar goals (i.e.,
$\varphi_{0}=\phi_{1}\mathop{\mathcal{U}}\phi_{2}$ and
$\varphi_{1}=\phi_{2}\mathop{\mathcal{U}}\phi_{1}$), and all possible goals
can be achieved from the initial state by a strong-cyclic policy. For
instance, for the Tidy-up domain, we define the following ltlf goals as
possible goals $\mathcal{G}_{\varphi}$:

  * •

$\varphi_{0}=\Diamond({\texttt{(wiped
desk1)}}\land\raisebox{-1.1625pt}{\LARGE$\circ$}(\Diamond{\texttt{(on book1
desk1)}}))$;

  * •

$\varphi_{1}=\Diamond({\texttt{(on book1
desk1)}}\land\raisebox{-1.1625pt}{\LARGE$\circ$}(\Diamond{\texttt{(wiped
desk1)}}))$;

  * •

$\varphi_{2}=\Diamond({\texttt{(on cup1
desk2)}}\land\raisebox{-1.1625pt}{\LARGE$\circ$}(\Diamond{\texttt{(wiped
desk2)}}))$;

  * •

$\varphi_{3}=\Diamond({\texttt{(wiped
desk2)}}\land\raisebox{-1.1625pt}{\LARGE$\circ$}(\Diamond{\texttt{(on cup1
desk2)}}))$;

Note that some of the goals described above share the same formulas and
fluents, but some of these formulas must be achieved in a different order,
e.g., $\varphi_{0}$ and $\varphi_{1}$, and $\varphi_{2}$ and $\varphi_{3}$. We
note that the recognition approach we developed in the paper is very accurate
in discerning (Table 1) the order that the intended goal aims to be achieved
based on few observations (executions of the agent in the environment).

As we mentioned earlier in the paper, an observation sequence contains a
sequence of actions that represent an execution $\vec{e}$ in the set of
possible executions $\vec{E}$ of policy $\pi$ that achieves the actual
intended hidden goal $\varphi^{*}$, and as we stated before, this observation
sequence $Obs$ can be full or partial. To generate the observations $Obs$ for
$\varphi^{*}$ and build the recognition problems, we extract strong-cyclic
policies using different fond planners, such as PRP and MyND. A full
observation sequence represents an execution (a sequence of executed actions)
of a strong-cyclic policy that achieves the actual intended hidden goal
$\varphi^{*}$, i.e., 100% of the actions of $\vec{e}$ being observed. A
partial observation sequence is represented by a sub-sequence of actions of a
full execution that aims to achieve the actual intended hidden goal
$\varphi^{*}$ (e.g., an execution with “missing” actions, due to a sensor
malfunction). In our recognition datasets, we define four levels of
observability for a partial observation sequence: 10%, 30%, 50%, or 70% of its
actions being observed. For instance, for a full observation sequence $Obs$
with 10 actions (100% of observability), a corresponding partial observations
sequence with 10% of observability would have only one observed action, and
for 30% of observability three observed actions, and so on for the other
levels of observability.

We ran all experiments using PRP (Muise et al, 2012) planner with a single
core of a 12 core Intel(R) Xeon(R) CPU E5-2620 v3 @ 2.40GHz with 16GB of RAM,
set a maximum memory usage limit of 8GB, and set a 10-minute timeout for each
recognition problem. We note that we are unable to provide a direct comparison
of our approach against existing recognition approaches in the literature
because most of these approaches perform a non-trivial process that transforms
a recognition problem into planning problems to be solved by a planner
(Ramírez and Geffner, 2010; Sohrabi et al, 2016). Even adapting such a
transformation to work in fond settings with temporally extended goals, we
cannot guarantee that it will work properly in the problem setting we propose
in this paper.

###  5.2 Evaluation Metrics

We evaluate our goal recognition approach using widely known metrics in the
Goal and Plan Recognition literature (Ramírez and Geffner, 2009; Vered et al,
2016; Pereira et al, 2020). To evaluate our approach in the Offline Keyhole
Recognition setting, we use four metrics, as follows:

  * •

True Positive Rate (TPR) measures the fraction of times that the intended
hidden goal $\varphi^{*}$ was correctly recognized, e.g., the percentage of
recognition problems that our approach correctly recognized the intended goal.
A higher TPR indicates better accuracy, measuring how often the intended
hidden goal had the highest probability $P(\varphi\mid Obs)$ among the
possible goals. TPR (Equation 7) is the ratio between true positive
results555True positive results represent the number of goals that has been
recognized correctly., and the sum of true positive and false negative
results666False negative results represent the number of correct goals that
has not been recognized.;

$TPR=\frac{TP}{TP+FN}=1-FNR$ (7)

  * •

False Positive Rate (FPR) is a metric that measures how often goals other than
the intended goal are recognized (wrongly) as the intended ones. A lower FPR
indicates better accuracy. FPR is the ratio between false positive
results777False positive results are the number of incorrect goals that has
been recognized as the correct ones., and the sum of false positive and true
negative results888True negative results represent the number of incorrect
goals has been recognized correctly as the incorrect ones.;

$FPR=\frac{FP}{FP+TN}$ (8)

  * •

False Negative Rate (FNR) aims to measure the fraction of times in which the
intended correct goal was recognized incorrectly. A lower FNR indicates better
accuracy. FNR (Equation 9) is the ratio between false negative results and the
sum of false negative and true positive results;

$FNR=\frac{FN}{FN+TP}=1-TPR$ (9)

  * •

F1-Score (Equation 10) is the harmonic mean of precision and sensitivity
(i.e., TPR), representing the trade-off between true positive and false
positive results. The highest possible value of an F1-Score is 1.0, indicating
perfect precision and sensitivity, and the lowest possible value is 0. Thus,
higher F1-Score values indicate better accuracy.

$F1-Score=\frac{2*TP}{2TP+FP+FN}$ (10)

In contrast, to evaluate our approach in the Online Recognition setting, we
use the following metric:

  * •

Ranked First is a metric that measures the number of times the intended goal
hypothesis $\varphi^{*}$ has been correctly ranked first as the most likely
intended goal, and higher values for this metric indicate better accuracy for
performing online recognition.

In addition to the metrics mentioned above, we also evaluate our recognition
approach in terms of recognition time (Time), which is the average time in
seconds to perform the recognition process (including the calls to a fond
planner);

###  5.3 Offline Keyhole Recognition Results

We now assess how accurate our recognition approach is in the Keyhole
Recognition setting. Table 1 shows three inner tables that summarize and
aggregate the average results of all the six datasets for four different
metrics, such as Time, TPR, FPR, and FNR. $|\mathcal{G}_{\varphi}|$ represents
the average number of goals in the datasets, and $|Obs|$ the average number of
observations. Each row in these inner tables represents the observation level,
varying from 10% to 100%. Figure 5 shows the performance of our approach by
comparing the results using F1-Score for the six types of temporal formulas we
used for evaluation. Table LABEL:tab:gr_results_separately shows in much more
detail the results for each of the six datasets we used for evaluating of our
recognition approach.

#### Offline Results for Conjunctive and Eventuality Goals

The first inner table shows the average results comparing the performance of
our approach between conjunctive goals and temporally extended goals using the
eventually temporal operator $\Diamond$. We refer to this comparison as the
baseline since these two types of goals have the same semantics. We can see
that the results for these two types of goals are very similar for all
metrics. Moreover, it is also possible to see that our recognition approach is
very accurate and performs well at all levels of observability, yielding high
TPR values and low FPR and FNR values for more than 10% of observability. Note
that for 10% of observability, and ltlf goals for $\Diamond\varphi$, the TPR
average value is 0.74, and it means for 74% of the recognition problems our
approach recognized correctly the intended temporally extended goal when
observing, on average, only 3.85 actions. Figure 5(a) shows that our approach
yields higher F1-Score values (i.e., greater than 0.79) for these types of
formulas when dealing with more than 50% of observability.

#### Offline Results for ltlf Goals

Regarding the results for the two types of ltlf goals (second inner table), it
is possible to see that our approach shows to be accurate for all metrics at
all levels of observability, apart from the results for 10% of observability
for ltlf goals in which the formulas must be recognized in a certain order.
Note that our approach is accurate even when observing just a few actions (2.1
for 10% and 5.4 for 30%), but not as accurate as for more than 30% of
observability. Figure 5(b) shows that our approach yields higher F1-Score
values (i.e., greater than 0.75) when dealing with more than 30% of
observability.

#### Offline Results for ppltl Goals

Finally, as for the results for the two types of ppltl goals, it is possible
to observe in the last inner table that the overall average number of
observations $|Obs|$ is less than the average for the other datasets, making
the task of goal recognition more difficult for the ppltl datasets. Yet, we
can see that our recognition approach remains accurate when dealing with fewer
observations. We can also see that the values of FNR increase for low
observability, but the FPR values are, on average, inferior to $\approx$ 0.15.
Figure 5(c) shows that our approach gradually increases the F1-Score values
when also increases the percentage of observability.

(a) Conj. vs. ltlf Event.

(b) ltlf: Ordering vs. Until.

(c) ppltl: Once vs. Since.

Figure 5: F1-Score comparison.

|  |  |  |  | Conjunctive Goals
---
$\phi_{1}\land\phi_{2}$
|  |  ltlf Eventuality Goals
---
$\Diamond\phi$
| $|\mathcal{G}_{\phi}|$ | $|Obs|$ |  | Time | TPR | FPR | FNR | F1-Score |  | Time | TPR | FPR | FNR | F1-Score
10 | 5.2 | 3.85 |  | 189.1 | 0.75 | 0.15 | 0.25 | 0.63 |  | 243.8 | 0.74 | 0.11 | 0.26 | 0.60
30 | 10.7 |  | 187.2 | 0.85 | 0.08 | 0.15 | 0.78 |  | 235.1 | 0.86 | 0.10 | 0.14 | 0.78
50 | 17.4 |  | 188.4 | 0.83 | 0.09 | 0.17 | 0.82 |  | 242.1 | 0.89 | 0.07 | 0.11 | 0.92
70 | 24.3 |  | 187.8 | 0.86 | 0.08 | 0.14 | 0.84 |  | 232.1 | 0.92 | 0.08 | 0.08 | 0.87
100 | 34.7 |  | 190.4 | 0.85 | 0.09 | 0.15 | 0.86 |  | 272.8 | 0.95 | 0.09 | 0.05 | 0.90

|  |  |  |  |  ltlf Ordering Goals
---
$\Diamond(\phi_{1}\land\raisebox{-1.1625pt}{\LARGE$\circ$}(\Diamond\phi_{2}))$
|  |  ltlf Goals Until
---
$\phi_{1}\mathop{\mathcal{U}}\phi_{2}$
| $|\mathcal{G}_{\phi}|$ | $|Obs|$ |  | Time | TPR | FPR | FNR | F1-Score |  | Time | TPR | FPR | FNR | F1-Score
10 | 4.0 | 2.1 |  | 136.1 | 0.68 | 0.15 | 0.32 | 0.62 |  | 217.9 | 0.79 | 0.11 | 0.21 | 0.72
30 | 5.4 |  | 130.9 | 0.84 | 0.13 | 0.16 | 0.76 |  | 215.8 | 0.91 | 0.12 | 0.09 | 0.82
50 | 8.8 |  | 132.1 | 0.88 | 0.10 | 0.12 | 0.80 |  | 210.1 | 0.93 | 0.10 | 0.07 | 0.83
70 | 12.5 |  | 129.2 | 0.95 | 0.06 | 0.05 | 0.89 |  | 211.5 | 0.97 | 0.09 | 0.03 | 0.86
100 | 17.1 |  | 126.6 | 0.94 | 0.05 | 0.06 | 0.90 |  | 207.7 | 0.97 | 0.07 | 0.03 | 0.87

|  |  |  |  |  ppltl Goals Once
---
$\phi_{1}\land{\diamondminus}\phi_{2}$
|  |  ppltl Goals Since
---
$\phi_{1}\land(\lnot\phi_{2}\mathop{\mathcal{S}}\phi_{3})$
| $|\mathcal{G}_{\phi}|$ | $|Obs|$ |  | Time | TPR | FPR | FNR | F1-Score |  | Time | TPR | FPR | FNR | F1-Score
10 | 4.0 | 1.7 |  | 144.8 | 0.73 | 0.11 | 0.27 | 0.67 |  | 173.5 | 0.76 | 0.18 | 0.24 | 0.64
30 | 4.6 |  | 141.3 | 0.84 | 0.07 | 0.16 | 0.79 |  | 173.3 | 0.87 | 0.12 | 0.13 | 0.78
50 | 7.3 |  | 141.9 | 0.89 | 0.08 | 0.11 | 0.82 |  | 172.9 | 0.85 | 0.09 | 0.15 | 0.79
70 | 10.3 |  | 142.9 | 0.95 | 0.07 | 0.05 | 0.87 |  | 171.1 | 0.97 | 0.07 | 0.03 | 0.91
100 | 14.2 |  | 155.8 | 0.97 | 0.07 | 0.03 | 0.88 |  | 169.3 | 0.94 | 0.02 | 0.06 | 0.93

Table 1: Offline Recognition results for Conjunctive, ltlf, and ppltl goals.

###  5.4 Online Recognition Results

With the experiments and evaluation in the Keyhole Offline recognition setting
in place, we now proceed to present the experiments and evaluation in the
Online recognition setting. As before, performing the recognition task in the
Online recognition setting is usually harder than in the offline setting, as
the recognition task has to be performed incrementally and gradually, and we
see to the observations step-by-step, rather than performing the recognition
task by analyzing all observations at once, as in the offline recognition
setting.

Figure 6: Online Recognition example. Figure 7: Online Recognition Histogram.

Figure 6 exemplifies how we evaluate our approach in the Online recognition
setting. To do so, we use the Ranked First metric, which measures how many
times over the observation sequence the correct intended goal $\varphi^{*}$
has been ranked first as the top-1 goal over the goal hypotheses
$\mathcal{G}_{\varphi}$. The recognition problem example depicted in Figure 6
has five goal hypotheses (y-axis), and ten actions in the observation sequence
(x-axis). As stated before, the recognition task in the Online setting is done
gradually, step-by-step, so at every step our approach essentially ranks the
goals according to the probability distribution over the goal hypotheses
$\mathcal{G}_{\varphi}$. We can see that in the example in Figure 6 the
correct goal $\varphi^{*}$ is Ranked First six times (at the observation
indexes: 4, 6, 7, 8, 9, and 10) over the observation sequence with ten
observation, so it means that the goal correct intended goal
$\mathcal{G}_{\varphi}$ is Ranked First (i.e., as the top-1, with the highest
probability among the goal hypotheses $\mathcal{G}_{\varphi}$) 60% of the time
in the observation sequence for this recognition example.

We aggregate the average recognition results of all the six datasets for the
Ranked First metric as a histogram, by considering full observation sequences
that represent executions (sequences of executed actions) of strong-cyclic
policies that achieves the actual intended goal $\varphi^{*}$, and we show
such results in Figure 7. The results represent the overall percentage
(including the standard deviation – black bars) of how many times the of time
that the correct intended goal $\varphi^{*}$ has been ranked first over the
observations. The average results indicated our approach to be in general
accurate to recognize correctly the temporal order of the facts in the goals
in the Online recognition setting, yielding Ranked First percentage values
greater than 58%.

Figures 8, 9, 10, 11, 10, 12, and 13 shows the Online recognition results
separately for all six domains models and the different types of temporally
extended goals. By analyzing the Online recognition results more closely, we
see that our approach converges to rank the correct goal as the top-1 mostly
after a few observations. This means that it is commonly hard to disambiguate
among the goals at the beginning of the execution, which, in turn, directly
affects the overall Ranked First percentage values (as we can see in Figure
7). We can observe our approach struggles to disambiguate and recognize
correctly the intended goal for some recognition problems and some types of
temporal formulas. Namely, our approach has struggled to disambiguate when
dealing with ltlf Eventuality goals in Blocks-World (see Figure 8(a)), for
most temporal extended goals in Tidy-Up (see Figure 10), and for ltlf
Eventuality goals in Zeno-Travel (see Figure 13(a)).

##  6 Related Work and Discussion

To the best of our knowledge, existing approaches to Goal and Plan Recognition
as Planning cannot explicitly recognize temporally extended goals in non-
deterministic environments. Seminal and recent work on Goal Recognition as
Planning relies on deterministic planning techniques (Ramírez and Geffner,
2009; Sohrabi et al, 2016; Pereira et al, 2020) for recognizing conjunctive
goals. By contrast, we propose a novel problem formalization for goal
recognition, addressing temporally extended goals (ltlf or ppltl goals) in
fond planning domain models. While our probabilistic approach relies on the
probabilistic framework of Ramírez and Geffner (2010), we address the
challenge of computing $\mathbb{P}(Obs\mid G)$ in a completely different way.

There exist different techniques to Goal and Plan Recognition in the
literature, including approaches that rely on plan libraries (Avrahami-
Zilberbrand and Kaminka, 2005), context-free grammars (Geib and Goldman,
2009), and Hierarchical Task Network (HTN) (Höller et al, 2018). Such
approaches rely on hierarchical structures that represent the knowledge of how
to achieve the possible goals, and this knowledge can be seen as potential
strategies for achieving the set of possible goals. Note that the temporal
constraints of temporally extended goals can be adapted and translated to such
hierarchical knowledge. For instance, context-free grammars are expressive
enough to encode temporally extended goals (Chiari et al, 2020). ltlf has the
expressive power of the star-free fragment of regular expressions and hence
captured by context-free grammars. However, unlike regular expressions, ltlf
uses negation and conjunction liberally, and the translation to regular
expression is computationally costly. Note, being equally expressive is not a
meaningful indication of the complexity of transforming one formalism into
another. De Giacomo et al (2020) show that, while ltlf and ppltl have the same
expressive power, the best translation techniques known are worst-case
3EXPTIME.

As far as we know, there are no encodings of ltlf-like specification languages
into HTN, and its difficulty is unclear. Nevertheless, combining HTN and ltlf
could be interesting for further study. HTN techniques focus on the knowledge
about the decomposition property of traces, whereas ltlf-like solutions focus
on the knowledge about dynamic properties of traces, similar to what is done
in verification settings.

Most recently, Bonassi et al (2023) develop a novel Pure-Past Linear Temporal
Logic PDDL encoding for planning in the Classical Planning setting.

##  7 Conclusions

We have introduced a novel problem formalization for recognizing temporally
extended goals, specified in either ltlf or ppltl, in fond planning domain
models. We have also developed a novel probabilistic framework for goal
recognition in such settings, and implemented a compilation of temporally
extended goals that allows us to reduce the problem of fond planning for
ltlf/ppltl goals to standard fond planning. We have shown that our recognition
approach yields high accuracy for recognizing temporally extended goals
(ltlf/ppltl) in different recognition settings (Keyhole Offline and Online
recognition) at several levels of observability.

As future work, we intend to extend and adapt our recognition approach for
being able to deal with spurious (noisy) observations, and recognize not only
the temporal extended goals but also anticipate the policy that the agent is
executing to achieve its goals.

###### Acknowledgements.

This work has been partially supported by the EU H2020 project AIPlan4EU (No.
101016442), the ERC Advanced Grant WhiteMech (No. 834228), the EU ICT-48 2020
project TAILOR (No. 952215), the PRIN project RIPER (No. 20203FFYLK), and the
PNRR MUR project FAIR (No. PE0000013).

(a) ltlf Eventuality.

(b) ltlf Ordering.

(c) ltlf Until.

(d) ppltl Once.

(e) ppltl Since.

Figure 8: Online recognition ranking over the observations for Blocks-World.

(a) ltlf Eventuality.

(b) ltlf Ordering.

(c) ltlf Until.

(d) ppltl Once.

(e) ppltl Since.

Figure 9: Online recognition ranking over the observations for Logistics.

(a) ltlf Eventuality.

(b) ltlf Ordering.

(c) ltlf Until.

(d) ppltl Once.

(e) ppltl Since.

Figure 10: Online recognition ranking over the observations for Tidy-Up.

(a) ltlf Eventuality.

(b) ltlf Ordering.

(c) ltlf Until.

(d) ppltl Once.

(e) ppltl Since.

Figure 11: Online recognition ranking over the observations for Tireworld.

(a) ltlf Eventuality.

(b) ltlf Ordering.

(c) ltlf Until.

(d) ppltl Once.

(e) ppltl Since.

Figure 12: Online recognition ranking over the observations for Triangle-
Tireworld.

(a) ltlf Eventuality.

(b) ltlf Ordering.

(c) ltlf Until.

(d) ppltl Once.

(e) ppltl Since.

Figure 13: Online Recognition ranking over the observations for Zeno-Travel.

## References

  * Aineto et al (2021) Aineto D, Jimenez S, Onaindia E (2021) Generalized Temporal Inference via Planning. In: KR
  * Aminof et al (2020) Aminof B, De Giacomo G, Rubin S (2020) Stochastic fairness and language-theoretic fairness in planning in nondeterministic domains. In: ICAPS
  * Armentano and Amandi (2007) Armentano G, Amandi A (2007) Plan recognition for interface agents. Artificial Intelligence Review 28(2):131–162
  * Avrahami-Zilberbrand and Kaminka (2005) Avrahami-Zilberbrand D, Kaminka GA (2005) Fast and Complete Symbolic Plan Recognition. In: IJCAI
  * Bacchus and Kabanza (1998) Bacchus F, Kabanza F (1998) Planning for temporally extended goals. Ann Math Artif Intell 22(1-2)
  * Baier and McIlraith (2006) Baier JA, McIlraith SA (2006) Planning with temporally extended goals using heuristic search. In: AAAI
  * Bonassi et al (2023) Bonassi L, Giacomo GD, Favorito M, Fuggitti F, Gerevini A, Scala E (2023) Planning for temporally extended goals in pure-past linear temporal logic. In: ICAPS
  * Bryce and Buffet (2008) Bryce D, Buffet O (2008) 6th International Planning Competition: Uncertainty Part. International Planning Competition (IPC)
  * Camacho et al (2017) Camacho A, Triantafillou E, Muise C, Baier J, McIlraith S (2017) Non-deterministic planning with temporally extended goals: LTL over finite and infinite traces. In: AAAI
  * Camacho et al (2018) Camacho A, Baier J, Muise C, McIlraith S (2018) Finite LTL synthesis as planning. In: ICAPS
  * Chiari et al (2020) Chiari M, Bergamaschi D, Mandrioli D, Pradella M (2020) Linear Temporal Logics for Structured Context-Free Languages. In: ICTCS
  * Cimatti et al (1997) Cimatti A, Giunchiglia E, Giunchiglia F, Traverso P (1997) Planning via model checking: A decision procedure for ar. In: ECP
  * Cimatti et al (2003) Cimatti A, Pistore M, Roveri M, Traverso P (2003) Weak, Strong, and Strong Cyclic Planning via Symbolic Model Checking. Artificial Intelligence 147(1-2)
  * De Giacomo and Rubin (2018) De Giacomo G, Rubin S (2018) Automata-theoretic foundations of FOND planning for LTLf and LDLf goals. In: IJCAI
  * De Giacomo and Vardi (2013) De Giacomo G, Vardi M (2013) Linear temporal logic and linear dynamic logic on finite traces. In: IJCAI
  * De Giacomo and Vardi (2015) De Giacomo G, Vardi M (2015) Synthesis for LTL and LDL on finite traces. In: IJCAI
  * De Giacomo et al (2020) De Giacomo G, Di Stasio A, Fuggitti F, Rubin S (2020) Pure-past linear temporal and dynamic logic on finite traces. In: IJCAI
  * Geffner and Bonet (2013) Geffner H, Bonet B (2013) A concise introduction to models and methods for automated planning. Morgan & Claypool Publishers
  * Geib and Goldman (2009) Geib CW, Goldman RP (2009) A Probabilistic Plan Recognition Algorithm Based on Plan Tree Grammars. Artificial Intelligence 173(11)
  * Henriksen et al (1995) Henriksen J, Jensen J, Jørgensen M, Klarlund N, Paige B, Rauhe T, Sandholm A (1995) Mona: Monadic second-order logic in practice. In: TACAS
  * Höller et al (2018) Höller D, Behnke G, Bercher P, Biundo S (2018) Plan and goal recognition as htn planning. In: International Conference on Tools with Artificial Intelligence
  * Kaminka et al (2018) Kaminka GA, Vered M, Agmon N (2018) Plan recognition in continuous domains. In: AAAI
  * Mattmüller et al (2010) Mattmüller R, Ortlieb M, Helmert M, Bercher P (2010) Pattern database heuristics for fully observable nondeterministic planning. In: ICAPS
  * McDermott et al (1998) McDermott D, Ghallab M, Howe A, Knoblock C, Ram A, Veloso M, Weld D, Wilkins D (1998) PDDL $-$ The Planning Domain Definition Language. In: AIPS
  * Muise et al (2012) Muise C, McIlraith SA, Beck JC (2012) Improved non-deterministic planning by exploiting state relevance. In: ICAPS
  * Nebel et al (2013) Nebel B, Dornhege C, Hertle A (2013) How much does a household robot need to know in order to tidy up your home? In: AAAI Workshop on Robotics
  * Patrizi et al (2011) Patrizi F, Lipovetzky N, Giacomo GD, Geffner H (2011) Computing Infinite Plans for LTL Goals Using a Classical Planner. In: IJCAI
  * Patrizi et al (2013) Patrizi F, Lipovetzky N, Geffner H (2013) Fair LTL synthesis for non-deterministic systems using strong cyclic planners. In: IJCAI
  * Pereira et al (2019a) Pereira RF, Pereira AG, Meneguzzi F (2019a) Landmark-enhanced heuristics for goal recognition in incomplete domain models. In: ICAPS
  * Pereira et al (2019b) Pereira RF, Vered M, Meneguzzi F, Ramírez M (2019b) Online probabilistic goal recognition over nominal models. In: IJCAI
  * Pereira et al (2020) Pereira RF, Oren N, Meneguzzi F (2020) Landmark-based approaches for goal recognition as planning. Artificial Intelligence 279
  * Pnueli (1977) Pnueli A (1977) The temporal logic of programs. In: FOCS
  * Ramírez and Geffner (2009) Ramírez M, Geffner H (2009) Plan Recognition as Planning. In: IJCAI
  * Ramírez and Geffner (2010) Ramírez M, Geffner H (2010) Probabilistic plan recognition using off-the-shelf classical planners. In: AAAI
  * Ramírez and Geffner (2011) Ramírez M, Geffner H (2011) Goal recognition over pomdps: inferring the intention of a pomdp agent. In: IJCAI
  * Sohrabi et al (2016) Sohrabi S, Riabov AV, Udrea O (2016) Plan Recognition as Planning Revisited. In: IJCAI
  * Torres and Baier (2015) Torres J, Baier JA (2015) Polynomial-time reformulations of LTL temporally extended goals into final-state goals. In: IJCAI
  * Vered et al (2016) Vered M, Kaminka GA, Biham S (2016) Online goal recognition through mirroring: Humans and agents. In: Advances in Cognitive Systems, vol 4