# Temporal Planning with Incomplete Knowledge and Perceptual Information

Yaniel Carreno Yvan Petillot Ronald P. A. Petrick Contact Author.Edinburgh
Centre for Robotics, Edinburgh, United KingdomHeriot-Watt University and The
University of Edinburgh, Edinburgh, United Kingdom {y.carreno, y.r.petillot,
<EMAIL_ADDRESS>
###### Abstract

In real-world applications, the ability to reason about incomplete knowledge,
sensing, temporal notions, and numeric constraints is vital. While several AI
planners are capable of dealing with some of these requirements, they are
mostly limited to problems with specific types of constraints. This paper
presents a new planning approach that combines contingent plan construction
within a temporal planning framework, offering solutions that consider numeric
constraints and incomplete knowledge. We propose a small extension to the
Planning Domain Definition Language (PDDL) to model (i) incomplete, (ii)
knowledge sensing actions that operate over unknown propositions, and (iii)
possible outcomes from non-deterministic sensing effects. We also introduce a
new set of planning domains to evaluate our solver, which has shown good
performance on a variety of problems.

##  1 Introduction and Motivation

Automated planning is widely used as a tool for autonomous agents to achieve
their mission goals. In the past decade, AI planners have been introduced in a
large number of real-world applications [31] to deal with the challenges that
arise in these scenarios, such as the incompleteness of the domain definition
and the complexity of dynamic models that capture numeric and temporal
constraints. Hybrid temporal planners are able to reason with both discrete
and continuous numeric changes over time to generate realistic action
schedules (plans) capable of supporting concurrent actions, synchronisation of
multiple tasks, and deadlines. Several solutions to planning with continuous
and discrete effects [29, 33, 17] base their reasoning on deterministic
models. These solvers generate plans by scheduling sequences of actions that
satisfy numeric and temporal constraints. However, their applicability is
limited when parts of the domain are incomplete or unknown. Contingent
planning [39, 44] copes with certain types of incomplete information by
treating the plan as a decision tree with different contingent branches that
could arise. A contingent plan guides the agent to act conditionally to
achieve the goal, with actions in the decision tree enabling the planner to
decide which branch to take.

In this work, we focus on temporal planning with numeric constraints where the
action sequences required to reach the goals give rise to conditional plans.
For instance, consider the following example:

Figure 1: (left) Example of the planning and execution process required to
solve a problem in Example 1. (right) Graphical representation of the plan
solution for Example 1.

######  Example 1.

(Valve Manipulation) An offshore scenario (Figure 1 (left)) includes a set of
blowout preventers (BOPs) which are controlled by manipulating valves. An
autonomous underwater vehicle (AUV) must close two valves (v1 and v2) during a
mission, and must record and communicate data every time it manipulates a
valve. The AUV starts at the deployment base. From there, it can navigate to
the BOPs and manipulate a valve. The AUV’s actions will depend on the valve
state: if a valve is open, then it should be closed; if a valve is closed,
then no action is needed. The valve state can be checked using a sensing
action. The AUV may also need to recharge using an autonomous surface vehicle
(ASV) which is deployed in different recharge points at different times.

Figure 1 (right) shows a plan solution for this problem. We note that no
sequence of actions allows the AUV to achieve the goal without first
determining the state of the valves. As a result, choosing the correct actions
to execute depends on the outcome of sensing the valve states (open or
closed). Numeric constraints are required to control the data recorded when a
valve is manipulated. Therefore, if the valve is open, the AUV should execute
a manipulation action and navigate to the surface to report the action’s
implementation. Temporal constraints are also essential for scheduling
recharge activities due to the ASV’s time availability at different locations.
Different sensing outcomes (red) can lead to different task sequences with
extra actions (green) requiring more energy and time to complete the mission.

In this paper, we formalise temporally-contingent planning (TCP) problems,
which describe a partially observable environment with sensing actions (PPOS)
and time constraints, and introduce a new compilation-based planning approach
called Temporal Contingent Effect (TraCE) that combines temporal plan
construction with contingent planning. TraCE analyses the PPOS as a Fully-
Observable Non-Deterministic (FOND) planning problem using a modified version
of the approach in [6] to convert PPOS into FOND problems that include
temporal constraints. Both deterministic (physical) actions and non-
deterministic (sensing) actions are treated as durative actions. Plan branches
are computed by considering the branching points, arising from sensing
actions, and branch depth. The plans generated by TraCE are trees of actions
(Figure 1 (right)), where the actions in a branch satisfy the ordinary
propositional preconditions but are scheduled by a sub-solver that also
considers temporal and numeric requirements. The approach is evaluated on a
set of planning problems that include real robotic applications.

##  2 Related Work

Many temporal planning models introduce an explicit notion of time [25].
Examples include solvers dealing with temporal coordination [21], continuous
effect requirements [17], and preferences [3]. Such approaches are capable of
solving a large number of well-established planning domains [32], and real-
world domains [10, 9, 13]. Our framework aims to solve a new set of problems
that require reasoning about incomplete information in addition to the
temporal and numeric requirements. In this work, we focus on offline planning
strategies. Previous examples of offline contingent planning solvers include
MBP [5], Contingent-FF [30], and POND [7]. Although these planners can solve
large problems at different hardness levels, they do not scale well, mostly
due to the underlying belief state representation. DNFct [42] and CLG [2]
(offline version) outperform previous approaches, finding solutions in a
shorter time with better scalability. A different contingent planning approach
is PKS [40, 41] which attempts to model the knowledge state directly. Amongst
the group of planners that deal with FOND planning problems, PO-PRP [35]
extends PRP [36] to compute strong cycle plans. ProbPRP [8] is an extension of
PO-PRP that computes policies to overcome deadends. HCP-ASP [45] and HCPlan
[37] demonstrate the applicability of contingent planning in hybrid
approaches. Our work inherits some of the ideas introduced by the prior
approaches regarding implementing hybrid solutions and the translation (or
compilation) of nondeterministic problems for planning.

Few approaches in the literature combine temporal and contingent planning to
solve nondeterministic temporal planning problems. CTP [43] allows the
construction of conditional plans with temporal constraints. Strategies based
on Simple Temporal Networks with Uncertainty (STNU) such as [15] are used as
temporal scheduling tools where conditions and decisions can be added to STNUs
[18, 46]. [19] present an encoding to Conditional Simple Temporal Networks
with Uncertainty and Resources (CSTNURs) with promising results in a set of
applications that model temporal and numeric constraints. A solution that
considers planning and meeting temporal problem constraints is the TCP
framework [22], which includes time and contingency notions in the model. This
framework differs from the contingent planning problems we are interested in,
where branch creation leads to solve the incomplete knowledge Some work
associated with temporal plan merging [26, 11] and opportunistic planning
consider temporal [14] and resource [16] constraints to generate branches in a
temporal plan. [12] presents an approach to solve TCP problems considering the
work implemented in [38] that translates contingent planning into classical
problems. TraCE differs from this approach in the problem translation and the
tree expansion.

##  3 Problem Formalisation

We begin by formulating the TCP problem. We use PDDL2.1 [23] which is
typically used for temporal planning problems:

######  Definition 1.

A temporal planning problem is a tuple
${{P}_{\\_}{T}:=\langle{P},{V},{A}_{\\_}{T},{I}_{\\_}{T},{G}_{\\_}{T},{T}\rangle}$,
where ${P}$ is a set of Boolean variables; ${V}$ is a vector of real variables
(numeric fluents); ${A}_{\\_}{T}$ is a set of instantaneous and durative
actions, where the duration of the actions is controllable and known;
${I}_{\\_}{T}$ is a function
${I}_{\\_}{T}:{P}\cup{V}\rightarrow\\{\top,\bot\\}\cup\mathbb{R}$ describing
the initial state; ${G}_{\\_}{T}$ is a set of goals, where goals in
${G}_{\\_}{T}$ are Boolean variables from ${P}$ or inequalities over real
variables in ${V}$ that represent the objectives that must be achieved; ${T}$
is a set of timed initial literals (TILs).

A timed initial literal (TIL) [20] is a pair (t, p) where t is the rational-
valued time of occurrence of a Boolean variable $p$, where $p\in{P}$ and
$\textit{p}\rightarrow\\{p,\neg p\\}$. A TIL $(t,p)$ defines the time $t$ that
the Boolean variable $p$ becomes true ($p$), and a TIL $(t,\neg{p})$ describes
the time $t$ that $p$ becomes false ($\neg p$).

######  Definition 2.

A durative action $a_{\\_}d\in{A}_{\\_}{T}$ is a tuple of the form $\langle
a_{\\_}{d_{\\_}{\mathit{pre}}},a_{\\_}{d_{\\_}{\mathit{eff}}},a_{\\_}{d_{\\_}{\mathit{dur}}}\rangle$.
$a_{\\_}{d_{\\_}{\mathit{pre}}}$ is a set of conditions of the following types
that must hold for the action to be applicable: at-start
(${a}_{\\_}{d_{\\_}{{\mathit{pre}}}\vdash}$), over-all
(${a}_{\\_}{d_{\\_}{{pre\leftrightarrow}}}$), and at-end
(${a}_{\\_}{d_{\\_}{{\mathit{pre}\dashv}}}$). $a_{\\_}{d_{\\_}{\mathit{eff}}}$
is the set of action effects of the types: positive starting effects
(${a}_{\\_}{d_{\\_}{{\mathit{eff}\vdash}^{+}}}$), negative starting effects
(${a}_{\\_}{d_{\\_}{{\mathit{eff}\vdash}^{-}}}$), numeric starting effects
(${a}_{\\_}{d_{\\_}{{\mathit{eff}\vdash}^{n}}}$), continuous numeric effects
(${a}_{\\_}{d_{\\_}{{\mathit{eff}\leftrightarrow}^{n}}}$), positive ending
effects (${a}_{\\_}{d_{\\_}{{\mathit{eff}\dashv}^{+}}}$), negative ending
effects (${a}_{\\_}{d_{\\_}{{\mathit{eff}\dashv}^{-}}}$), and numeric ending
effects (${a}_{\\_}{d_{\\_}{{\mathit{eff}\dashv}^{n}}}$).
$a_{\\_}{d_{\\_}{\mathit{dur}}}$ is a set of action durations.

A solution to a TCP problem ${P}_{\\_}{T}$ is a time-aware plan
${\Pi}_{\\_}{T}=\\{a_{\\_}{1}\cdots,a_{\\_}{n}\\}$ described by a sequence of
durative and instantaneous actions, where each action $a_{\\_}i$ is
applicable, and $\Pi_{\\_}{T}$ achieves the goals in ${G}_{\\_}{T}$ satisfying
the temporal constraints. For instance, each branch in Figure 1 (right) from
the initial state ${I}_{\\_}{T}$ to the goal ${G}_{\\_}{T}$ is a single
sequence of durative actions. Note that such plans do not consider incomplete
information or the effects of sensing actions.

We now consider contingent planning problems which include partial
observability and non-deterministic (sensing) actions in the model, but no
temporal constraints.

######  Definition 3.

A contingent planning problem is a tuple
${{P}_{\\_}{C}:=\langle{P},{A}_{\\_}{C},{O},{I}_{\\_}{C},{G}_{\\_}{C}\rangle}$,
where ${P}$ is set of Boolean variables describing the state of the world;
${A}_{\\_}{C}$ is a set of physical actions; ${O}$ is a set of sensing
actions, separate from ${A}_{\\_}{C}$ such that
${O}\cap{A}_{\\_}{C}=\emptyset$; ${I}_{\\_}{C}\subseteq{P}$, is the set of
clauses over ${P}$ that denotes the initial state; and ${G}_{\\_}{C}$ is a set
of propositions over ${P}$ representing the goal condition.

A proposition $p\in{P}$ or its negation $\neg p$ defines a literal $l\in{L}$,
where ${L}$ is a set of literals and $\overline{{L}}=\\{\neg
l\;|\;l\in{L}\\}$. A set ${L}^{{}^{\prime}}$ of literals is consistent if the
condition $\\{p,\neg p\\}\nsubseteq{L}$ holds for every $p$; and complete if
the condition $\\{p,\neg p\\}\cap{L}\neq\emptyset$ holds for every $p\in{P}$.
The complement of a literal $l$ is defined as $\overline{l}$ such that
$\overline{l}=\neg l$ and $p=\neg\neg p$ for $p\in{P}$.

A state $s$ is defined as a consistent and complete set ${L}$ of literals. A
state $s$ satisfies a conjunction of literals ${L^{\prime\prime}}$
($s\models{L^{\prime\prime}})$ if ${L^{\prime\prime}}\subseteq s$. A state $s$
satisfies a literal $l$ $(s\models l)$ if $l\in s$. A belief state ${S}$ is a
set of states. The belief state ${S}\models l$ if $s\models l$ for every
$s\in{S}$. Finally, ${S}\models{L^{\prime\prime}}$ if
$s\models{L^{\prime\prime}}$ for every $s\in{S}$.

The set of states in the belief state ${S}$ capture the alternative ways that
the world could be configured. In a contingent planning model, a literal as
being unknown if it appears in more than one state in a belief state with
different mappings. So, if $s\models l$ is true in each state $s$, then $s$ is
said to be known. However, if there exist states $s_{\\_}{1}$ and $s_{\\_}{2}$
such that $s_{\\_}{1}\models l$ and $s_{\\_}{2}\models\neg l$ then $l$ would
be considered unknown since either value of $l$ is considered possible. For
instance, in Example 1 a belief state ${S}$ includes the possible outcomes of
the (state_on v1) variable which are (state_on v1) and $\neg$(state_on v1).

Actions are defined as follows:

######  Definition 4.

A physical action $a\in{A}_{\\_}{C}$ is a tuple $\langle
a_{\\_}\mathit{pre},a_{\\_}\mathit{eff}\rangle$, where $a_{\\_}\mathit{pre}$
is a set of atomic propositions indicating the preconditions to implement $a$,
and $a_{\\_}\mathit{eff}$ represents a set of action outcomes.
$a_{\\_}\mathit{eff}$ describes a set of pairs $\langle c,l\rangle$,which
capture its conditional effects, where $c$ is a set of possible effects
defined by a set of literals ${L}$ and $l$ is a literal.

######  Definition 5.

A sensing action $o\in{O}$ is a tuple
$\langle{o}_{\\_}\mathit{pre},{o}_{\\_}\mathit{eff}\rangle$, where
${o}_{\\_}\mathit{pre}$ is a set of atomic propositions indicating the
preconditions to implement $o$, and ${o}_{\\_}\mathit{eff}$ completely
characterises an unknown literal $l$, by considering the possible outcomes for
a given proposition. Therefore, ${o}_{\\_}\mathit{eff}$ includes a set of
possible effects ${o}_{\\_}\mathit{eff}^{\prime}$ and
${o}_{\\_}\mathit{eff}^{\prime\prime}$ that uncover the value of $l$.

This is for a belief state ${S}$ a sensing action effects define two
independent belief state ${S}^{+}$ and ${S}^{-}$ that enclose the states where
$l$ is possible, and states where $\neg l$ is possible, respectively.
Considering Definition 5, sensing actions are nondeterministic. Sensing
actions lead to a possible set of outcomes (states), enclosed in the belief
state, associated with the truth value of a literal. For a sensing action the
belief state ${S}_{\\_}{o}$ gives rise to two possible belief states,
depending on the value of the underlying literal ($l$ or $\neg l$). This makes
the model nondeterministic at plan time but the belief state is always certain
in each case. The possible belief states associated with a sensing action are:
${S}^{+}_{\\_}{o}=\\{s\,|\,s\in{S},s\models l(o)\\}$ and
${S}^{-}_{\\_}{o}=\\{s\,|\,s\in{S},s\models\overline{l(o)}\\}$.

A solution to ${\Pi}_{\\_}{C}$ is a contingent-aware plan ${P}_{\\_}{C}$ with
a branching structure induced by the sensing outcomes. For instance, the plan
in Figure 1 (right) is a solution to a contingent planning problem, assuming
the recharge and broadcast actions, which include temporal and numeric
constraints, are ignored.

###  3.1 Temporally-Contingent Planning Problem

A TCP problem is a special case of the PPOS problem where the source of
uncertainty is connected to the outcome of the sensing actions [35], and
temporal and numeric notions are introduced in the model. We consider simple
PPOS problems [6] which can be mapped into FOND planning problems [35]. In
particular, we assume that (i) non-unary clauses in the initial state ${I}$
are invariant, which are states that hold in every world state [27], (ii)
hidden literals do not emerge in the effects of a non-deterministic action,
and (iii) uncertainty decreases monotonically, i.e., unknown properties cannot
become unknown again after becoming known. As a result, the TCP problem is a
FOND problem with temporal requirements and real variables.

######  Definition 6.

A temporally-contingent planning problem is a tuple
${P}_{\\_}{TC}:=\langle{P},{V},{A},\Delta,{I},{G},{T}\rangle$, where ${P}$ is
set of Boolean variables describing the state of the world; ${V}$ is a vector
of real variables (numeric fluents), ${A}$ is a set of durative physical
(deterministic) actions; $\Delta$ is a set of durative sensing
(nondeterministic) actions, separate from ${A}$ such that
$\Delta\cap{A}=\emptyset$, both actions with controllable and known durations;
${I}$ is a function ${I}:{P}\cup{V}\rightarrow\\{\top,\bot\\}\cup\mathbb{R}$
describing the initial state; ${G}$ is a set of goals, where goals in ${G}$
are Boolean variables from ${P}$ or inequalities over real variables in ${V}$
that represent the objectives that must be achieved; ${T}$ is a set of TILs.

The TCP problem includes two type of actions, where physical actions can be
defined as durative actions (see Definition 1), while durative sensing actions
in $\Delta$ are an special type of sensing actions (see Definition 3) defined
as follows:

######  Definition 7.

A durative sensing action $\delta$, where $\delta\in\Delta$, is a durative
action with a nondeterministic outcome defined by the tuple
$\langle\delta_{\\_}\mathit{pre},\delta_{\\_}\mathit{eff},\delta_{\\_}\mathit{dur}\rangle$.
$\delta_{\\_}\mathit{pre}$ is a set of conditions, including a set of
literals, that must hold for the action to be applicable of type: at-start,
over-all, and at-end. $\delta_{\\_}\mathit{eff}$ includes a set of possible
action outcomes $\delta_{\\_}\mathit{eff}^{\prime}$ and
$\delta_{\\_}\mathit{eff}^{\prime\prime}$ that include effects of positive,
negative, and numeric startings, continuous numeric, positive, negative, and
numeric endings. The possible action outcomes characterise an unknown literal
$l$, by considering the possible outcomes for $l$ ($l$ or $\neg l$) described
in a belief state ${S}$.

In a belief state ${S}_{\\_}{A}=\\{(l,l_{\\_}{1},l_{\\_}{2}),(\neg
l,l_{\\_}{1},l_{\\_}{2}),(l,\neg l_{\\_}{1},l_{\\_}{2}),(\neg l,\neg
l_{\\_}{1},l_{\\_}{2})\\}$, there would be states where $l$ is possible and
states where $\neg l$ is possible so $l$’s true value is unknown. $\delta$’s
outcomes $\delta_{\\_}\mathit{eff}^{\prime}$ and
$\delta_{\\_}\mathit{eff}^{\prime\prime}$ define two independent belief states
${S}_{\\_}{B}^{\prime}=\\{(l,l_{\\_}{1},l_{\\_}{2}),(l,\neg l_{\\_}{1},$
$l_{\\_}{2})\\}$ and ${S}_{\\_}{B}^{\prime\prime}=\\{(\neg
l,l_{\\_}{1},l_{\\_}{2}),(\neg l,$ $\neg l_{\\_}{1},l_{\\_}{2})\\}$.
$\delta_{\\_}\mathit{dur}$ represents represents a set of duration constraints
(controllable and known). A sensing action $\delta$, where $\delta\in\Delta$,
helps to completely characterise an unknown literal $l$, where $l\in{I}$, by
considering the possible outcomes for $l$ described in a belief state
${S}^{\prime}$. The solution of the TCP problem is a transition tree which is
defined based on the outcomes of the sensing action.

PDDL Encoding. We propose a set of extensions to PDDL2.1, which define the
unknown literals, the set of possible outcomes of a durative sensing action,
and the connection between the literal sensed and the effects of the sensing
action. This approach is inspired by previous approaches that represent
incomplete information, and sensing [30, 40]. Our PDDL extensions to encode
the TCP problem are: (i) :unknown-literals. Figure 2 (left top) shows an
example of how incomplete information is represented for Example 1. In
:unknown-literals, the incomplete information in the problem is identified,
which can be extracted for the initial state ${I}$. For instance, the domain
the unknown literals reflect that the valve states are initially unknown,
(state_on ?v - valve); (ii) :knowledge-updates. Figure 2 (left bottom) shows
an example of the observational effects extension for the Example 1. In
:knowledge-updates, the and and oneof clauses [24] are used to define the set
of facts corresponding to the possible outcomes of a sensing action. For the
Example 1 domain, the unknown literal (state_on v1) is associated with two
possible effects, first, the valve’s state is open ((state_on v1)), the
second, the valve’s state is closed ((not (state_on v1))). Notice that in the
second effect, the and clause is used to specify the state of two literals,
(not (state_on v1)) and (valve_closed wp32); and (iii) :durative-action.
Finally, we present the extension for sensing outcomes in Figure 2 (right). In
:durative-action, a durative sensing action is extended from an ordinary
(physical) action to include the :observe construct, which connects the action
to the sensed literal. In the example, the sensing action (sense-valve)
observes the valve’s state (state_on ?v - valve) for a particular valve ?v
which gives rise to multiple possible outcomes, such as those in Figure 1
(right). This action includes time constraints and is not limited to Boolean
effects on literals. A durative sensing action in a TCP problem is
nondeterministic based on the sensing outcomes from the :observe. However, a
sensing action contains another set of deterministic effects that are
associated with the :effect. For instance, the positive ending effect (at end
(available ?r)), which defines the robot is available when the action
finishes. Considering this, the set of belief states associated with the
outcome of a sensing action contains an effect associated with the unknown
literal (different for each outcome) and a set of effects that are the same
for all possible belief states. In Example 1, the possible outcomes from
implementing the sensing action in valve v1 are: (i) (and (state_on v1)
(available auv1) (v_at v1 wp32) ...), and (ii) (and (not (state_on v1)
(valve_closed wp32) (available auv1) (v_at v1 wp32) ...).

(:unknown-literals (state_on v1) (state_on v2) ) (:knowledge-updates (oneof
(state_on v1) (and (not (state_on v1)) (valve_closed wp32))) (oneof (state_on
v2) (and (not (state_on v2)) (valve_closed wp42))) )

(:durative-action sense-valve :parameters (?r - robot ?s - sensor ?v - poi ?wp
- waypoint) :duration ( = ?duration 5) :condition (and (over all (can_sense ?r
?s)) (...)) :effect (and (at end (available ?r)) (...)) :observe (and (at end
(state_on ?v))) )

Figure 2: PDDL extensions for representing incomplete information and
observational effects in durative actions using constructs :unknown-literals
(left top) and :knowledge-updates (left bottom).

##  4 TraCE Planning

The TraCE planner takes as input a simple PPOS problem with temporal and
numeric constraints ${P}_{\\_}{TC}$ and generates a time-knowledge-aware plan
${\Pi}_{\\_}{TC}$ defined as follows:

######  Definition 8.

A time-knowledge-aware plan ${{\Pi}_{\\_}{TC}}=({N},{E})$ for a temporally-
contingent planning problem ${P}_{\\_}{TC}$ is a transition tree ${B}$,
represented as an AND/OR graph, where nodes ${N}$ are labelled with actions
built on a set of tuples, ${{\pi}_{\\_}{A}:=\langle a,t,d\rangle}$ for
physical actions and ${{\pi}_{\\_}{\Delta}:=\langle\delta,t,d\rangle}$ for
sensing actions; and edges ${E}$ represent the action outcomes, denoting the
set of propositions whose value are known after an action execution, where
$a\in{A}$ is an instantaneous or durative action, $\delta\in\Delta$ is a
durative sensing action, $t$ is the action starting time, $d$ represents the
action duration, $t\in{\mathbb{R}}_{\\_}{\geq 0}$, and
$d\in{\mathbb{R}}_{\\_}{>0}$ when actions have a duration.

The plan ${{\Pi}_{\\_}{TC}}$ arising from Definition 8 describes a tree where
physical and sensing actions are encoded as two different types of vertices:
(i) $v_{\\_}{{A}}$, denoting vertices that describe physical actions, where
$v(a)$ is a vertex, $v(a)\in v_{\\_}{{A}}$, and $a$ is a physical action,
$a\in{A}$; and (ii) $v_{\\_}{\Delta}$, which describes sensing action
vertices, where $v(\delta)$ is a vertex, $v(\delta)\in v_{\\_}{\Delta}$, and
$\delta$ is a sensing action, $\delta\in\Delta$. The ${B}$ tree edges capture
the action ordering, where an edge $z(v(x),v(y)$) defines that the action
denoted by the vertex $v(x)$ is executed before the action denoted by $v(y)$.
Physical actions are deterministic; therefore a vertex $v(a)$ has at most a
single edge. Sensing actions are nondeterministic; therefore, a vertex
$v(\delta)$, associated with the sensing action $\delta$, is characterised by
at least two possible outgoing edges. In this case, the number of edges
depends on the possible $\delta$ outcomes.

Algorithm 1 shows the TraCE planning approach, which returns a time-knowledge-
aware plan ${{\Pi}_{\\_}{TC}}$. TraCE is a PDDL planner that aims to support
the PDDL extensions modelling the TCP problem in full. The required inputs to
the TraCE solver are the domain ${D}_{\\_}{TC}$, including physical and
sensing actions; the TCP problem ${P}_{\\_}{TC}$, which defines the initial
state; and ${U}$, which includes the incomplete information and observational
effects. ${U}$ incorporates the incomplete information in the :unknown-
literals’s body and the observational effects in the :knowledge-updates’s
body; while the sensing actions in ${D}_{\\_}{TC}$ include the extension for
sensing outcomes. The branches in ${{\Pi}_{\\_}{TC}}$ are time-aware plan
solutions ($\Pi_{\\_}{T}$) that solve a temporal planning problem
${P}_{\\_}{T}$ under different sets of contingent outcomes arising from domain
incompleteness and durative sensing actions. For instance, the solution for
Example 1 shows the branches of a ${{\Pi}_{\\_}{TC}}$. Top and bottom branches
represent two different time-aware plans considering the sensing action sense-
valve outcomes define the valves (v1 and v2) are (both) closed and open,
respectively.

Output: $\Pi_{\\_}{TC}$ (Branched Temporal Plan)

1 begin

2 $\Pi_{\\_}{T}\leftarrow\emptyset$

3 $\Pi^{*}_{\\_}{T},{H}\leftarrow$
FindTemporalPlan(${D}_{\\_}{TC},{P}_{\\_}{TC},{U},t_{\\_}{\mathit{initial}}$)

4 if  _CheckExistence($\Pi_{\\_}{T}^{*}$)_ then

5

6 while  _$\Pi_{\\_}{T}\neq\Pi_{\\_}{T}^{*}$_ do

7 $\Pi_{\\_}{T},{H}\leftarrow$ Update$(\Pi_{\\_}{T}^{*},{H})$

8 $b,{Q}\leftarrow$ BuildBranch(${D}_{\\_}{TC},{U},\Pi_{\\_}{T},{H}$)

9 $root\leftarrow$ ExpandTree(${D}_{\\_}{TC},{P}_{\\_}{TC},b,{H},{U},{Q}$)

10 return $\Pi_{\\_}{TC}\leftarrow root$

11

12 else

13 return Failure

14

15

Algorithm 1 TraCE Planner (${D}_{\\_}{TC}$, ${P}_{\\_}{TC}$, ${U}$)

The strategy starts by initialising an empty temporal plan solution
${{\Pi}_{\\_}{T}}$ (line 2), which preserves the temporal plan associated with
a particular branch. Then, the approach finds an ordinary (initial)
deterministic temporal plan $\Pi_{\\_}{T}^{*}$ (line 3) for the problem that
represents the largest temporal plan solution. In this work, the plan size is
defined as the total number of actions in a plan (that describe each branch).
Therefore, the largest plan is the solution with more actions. For instance,
in Example 1, the largest deterministic temporal plan is represented by the
bottom branch. FindTemporalPlan computes the largest plan and returns it in
$\Pi_{\\_}{T}^{*}$. In our approach, the initial temporal plan
$\Pi_{\\_}{T}^{*}$ can be updated in parallel to the ${{\Pi}_{\\_}{TC}}$
search (line 4-9).

The history set ${H}$ for the temporal plan denotes the state $s[i]$ at which
$\Pi_{\\_}{T}[i]$ or $\Pi_{\\_}{T}^{*}[i]$ is executed, and the time $t[i]$ at
which $i$ starts and concludes, where ${H}[i]=\langle s[i],t[i]\rangle$ and
$\Pi_{\\_}{T}[i]$ or $\Pi_{\\_}{T}^{*}[i]$ defines the ith plan’s action in
$\Pi_{\\_}{T}$ or $\Pi_{\\_}{T}^{*}$. ${H}[i+1]$ describes the possible states
reached after an execution of $\Pi_{\\_}{T}[i]$ or $\Pi_{\\_}{T}^{*}[i]$.
Then, if $\Pi_{\\_}{T}^{*}$ exists (line 4), TraCE checks if
$\Pi_{\\_}{T}\neq\Pi_{\\_}{T}^{*}$ (line 5). Notice that the condition
$\Pi_{\\_}{T}\neq\Pi_{\\_}{T}^{*}$ allows the strategy to update the initial
temporally-contingent plan solution if after generating a plan
${{\Pi}_{\\_}{TC}}$, $\Pi_{\\_}{T}^{*}$ differs from the first $\Pi_{\\_}{T}$
as a result $\Pi_{\\_}{T}^{*}$ was optimised. If the strategy finds
discrepancies between $\Pi_{\\_}{T}$ and $\Pi_{\\_}{T}^{*}$, the first is
updated with the plan in $\Pi_{\\_}{T}^{*}$ (line 6). Then, the strategy
builds a branch $b$ using the BuildBranch method (see Algorithm 2) and expands
the tree for a set of tasks describing the sensing actions in $b$ to obtain
root (line 7-8) using the ExpandTree method (see Algorithm 3). The variable
root (identified by first action in the plan) describes ${{\Pi}_{\\_}{TC}}$,
and ${Q}$ defines a queue of tasks $\langle n,u\rangle$, where $n\in{N}$ is a
sensing node (representing a sensing action) and $u$ is a possible outcome of
the sensing action, where $u\in{U}$. Each $q\in{Q}$ introduces different
subsets of initial conditions based on the sensing action outcomes that leads
to a new temporal planning problem ${{P}_{\\_}{T}}$. After the tree expansion,
the ${{\Pi}_{\\_}{TC}}$ is returned (line 9). If $\Pi_{\\_}{T}^{*}$ is not
found the planner fails to find a solution for ${P}_{\\_}{TC}$ (line 10-11).

The FindTemporalPlan method computes temporal plans using the OPTIC [3]
planner. TraCE branch generation considers temporal–numeric planning within a
forward state space search framework. FindTemporalPlan does not consider
changes in the temporal planning search regarding the OPTIC approach. Instead,
the strategy provides the right conditional and time constraint inputs to the
propositional planning techniques and the sub-solver used to schedule the
action sequence to generate the required time-aware plan. The algorithm finds
the plan with the largest size by iterating over the initial state,
considering the combinations of incomplete information and observational
effects. We solve the plan length check by including into the problem initial
state the set of observational effects that defines the unknown literals in
${U}$ to be false (${S}^{-}_{\\_}{o}$). Considering this information in the
initial state we obtain a plan solution $\Pi_{\\_}{T}^{-}$. Then, the plan
$\Pi_{\\_}{T}^{-}$ is stored (if it exists). A similar procedure is repeated
considering all sensing outcomes associated with the unknown literals are true
(${S}^{+}_{\\_}{o}$) and we achieve a plan solution $\Pi_{\\_}{T}^{+}$ for
this initial state. The approach compares the two plan solutions
($\Pi_{\\_}{T}^{-}$ and $\Pi_{\\_}{T}^{+}$) and its saves the largest plan in
$\Pi_{\\_}{T}^{*}$. The planning problems that we consider include temporal
and numeric constraints that force actions in some order in the plan solution.
This justifies our decision to start the branch generation using the largest
plan as this solution satisfies the problem with the most considerable set of
temporal and numeric restrictions. Temporal planners attempt to improve the
initial plan solution, usually considering as a metric the makespan
minimisation.

The FindTemporalPlan method returns the plan’s history ${H}$. The second
component of the ${H}$ is the time $t[i]$ associated with the action
execution. The core of the temporal planning solver implements the scheduling
of the plan’s actions considering STNs and LP methods. We refer to these
strategies as a temporal solver (TS). The TS represents the temporal
constraints between the set of time points where actions start or end.
Therefore, we can describe the occurrence of an action $i$ in the TS reasoning
as the time point when the action starts $i_{\\_}{\vdash}$ and
$i_{\\_}{\dashv}$ when the action ends. This information is saved in
$t[i]=[i_{\\_}{\vdash},i_{\\_}{\dashv}]$. The FindTemporalPlan strategy
extends the scheduling analysis by controlling the $t_{\\_}{\mathit{initial}}$
value. The $t_{\\_}{\mathit{initial}}$ is introduced as an input to the
approach (see line 3 in Algorithm 1). For the first temporal plan
$\Pi_{\\_}{T}^{*}$, $t_{\\_}{\mathit{initial}}$ is considered 0. However, this
modification gains importance when expanding the tree based on the sensing
vertices. In these cases, the time the sensing action concludes is defined as
the $t_{\\_}{\mathit{initial}}$ for a new branch in the tree associated with a
different outgoing edge from the sensing vertex. We put this into context when
describing the remaining parts of the algorithm. The TS encodes a TIL by
adding a time point $t(p)$ for the occurrence of TIL $p$, with the temporal
constraint $t(p)-t_{\\_}{\mathit{initial}}=time_{\\_}{TIL}(p)$, where
$time_{\\_}{TIL}(p)$ is the time at which $p$ occurs. The TILs describe other
time points that need to be ordered by the TS approach when scheduling the
plan’s actions.

The BuildBranch method in Algorithm 2 describes the branch generation, which
starts with the first action in $\Pi_{\\_}{T}$. The strategy initialises ${Q}$
(line 2) and creates the first branch over the $\Pi_{\\_}{T}$’s size (line 3).
The branch creation relies upon the definition of all nodes in $\Pi_{\\_}{T}$
(vertices) and their connections (edges). For each action $\Pi_{\\_}{T}[i]$ in
the plan the algorithm initialises a node $n$ (line 4) that includes a set of
definition parameters: (i) $n$.name. is the name of the action describing the
node; (ii) $n$.s-action. Boolean variable to define if the node represents a
sensing action; (iii) $n$.parent. is the node $n$ parent; and $n$.depth.
number of edges from the root node to $n$.name. The strategy takes the
information that the FindTemporalPlan method saves in the history ${H}$ (state
and time) to define another two node’s parameters (line 5): (iv) $n$.state.
defines the state at which the action in $n$.name is executed; and (v)
$n$.time. defines the time at which the node (action) starts and concludes. If
the plan size is 0 (line 6-7), the branch $b$ contains precisely the node $n$,
which contains the set of parameters initialised. On the contrary, the TraCE
creates an outgoing edge from node $n$ to another new node child that denotes
the next action (line 8-9). Then, the method defines the state and time111At
this stage $t[i+1]$ for an action $i$ includes initial time of the next action
which is $i_{\\_}{\vdash}$ \+ $\epsilon$. parameters for the child (line 10).
TraCE appends the node $n$ children in the node parameter (line 11).
$n$.children defines the set of $n$.name(s) (actions) associated with a
$n$.name. If the action to label is a sensing action (line 12), TraCE maps the
edge from node $n$ to child child with the relevant outcome of the sensing
action, obtained from the history ${H}$ of $\Pi_{\\_}{T}$ and ${U}$ (line
13-14). This labelling is stored in the last node $n$ definition parameter:
$n$.edge-map. is the label of the outgoing edge from the node to its child,
where $n$ is a sensing node.

The node $n$, describing a sensing action in $\Delta$, and the possible
outcomes defined in ${U}$ for the action that does not label any outgoing edge
from $n$, describes a new temporally-contingent planning task with an initial
state ${I}^{i}$ obtained from ${H}[i]$. The planner stores the sensing nodes
and their possible outcomes ($\langle n,u\rangle$) obtained when building the
branch $b$ in ${Q}$ (line 15-16) The algorithms returns $b$ and an updated
${Q}$ (line 17). The $n$.depth definition parameter helps to organise the
tasks in the queue ${Q}$ to implement the expansion.

Input: $\langle{D}_{\\_}{TC},{U},\Pi_{\\_}{T},{H}\rangle$

Output: $\langle b,{Q}\rangle$

1 begin

2 ${Q}\leftarrow\emptyset$

3 for  _$i=0,\cdots,size(\Pi_{\\_}{T})-1$ _ do

4 $n\leftarrow$CreateNode($\Pi_{\\_}{T}[i]$)

5 $n$.state, $n$.time = ${H}[i]$

6 if  _$i==0$_ then

7 $b==n$

8

9 if  _$i\neq size(\Pi_{\\_}{T})-1$_ then

10 $\textit{child}\leftarrow$CreateNode($\Pi_{\\_}{T}[i+1]$)

11 child.state, child.time = ${H}[i+1]$

12 $n.$children $\leftarrow$AppendChildToNode$(\textit{child})$

13

14 if  _$n$.s-action_ then

15
${U}_{\\_}{\Delta}\leftarrow$ObtainCurrentOutcome(${H}[i]\cap{U}_{\\_}{\Pi_{\\_}{T}[i]}$)

16 $n$.edge-map(child) = $u$

17 for  _$u={U}_{\\_}{\Delta}\diagdown\\{u_{\\_}{\Delta}\\}$_ do

18 ${Q}\leftarrow$ AddToQueue(${Q},\langle n,u\rangle)$

19

20

21

22 return $b,{Q}$

23

Algorithm 2 BuildBranch

Input: $\langle{D}_{\\_}{TC},{P}_{\\_}{TC},b,{H},{U},{Q}\rangle$

Output: root

1 begin

2 while  _not ${Q}\leftarrow$ $\emptyset$_ do

3 for  _$\langle n_{\\_}{i},u_{\\_}{i}\rangle\leftarrow$
ExtractFromQueue$({Q})$_ do

4 ${I}=n_{\\_}{i}.$state

5 ${I^{{}^{\prime\prime}}}\leftarrow$ ModifyInitialState(${I},u_{\\_}{i}$)

6 ${P}_{\\_}{TC}^{{}^{\prime\prime}}\leftarrow$
update.${P}_{\\_}{TC}$(${I^{{}^{\prime\prime}}}$)

7 $\Pi_{\\_}{T},{H}\leftarrow$
FindTemporalPlan(${D}_{\\_}{TC},{P}_{\\_}{TC}^{{}^{\prime\prime}},{U},n_{\\_}{i}$.time)

8 if  _CheckExistence($\Pi_{\\_}{T}$)_ then

9 $\textit{branch\\_child},{Q}^{{}^{\prime\prime}}\leftarrow$
BuildBranch(${D}_{\\_}{TC},{U},\Pi_{\\_}{T},{H}$)

10 $\textit{branch\\_child}.$edge-map $=u_{\\_}{i}$

11 $n_{\\_}{i}.$children$\leftarrow$ AddToTree(branch_child)

12 ${Q}\leftarrow$update.${Q}$(${Q}^{{}^{\prime\prime}}$)

13

14 else

15 root $\leftarrow\emptyset$

16 return Break

17

18

19 return root

20

Algorithm 3 ExpandTree

The ExpandTree method in Algorithm 3 evaluates the task set ${Q}$ sequentially
considering the order imposed by the depth to compute the tree expansion (line
2-3). For each $q\in{Q}$, the approach defines the initial state ${I}$ using
the node information (line 4) and modifies ${I}$ according to the outcome
$u_{\\_}{i}$ (line 5). ${P}_{\\_}{TC}$ is updated with
${I}^{{}^{\prime\prime}}$ (line 6). Then, TraCE triggers the temporal planning
search (line 7), which finds the largest plan solution considering the current
initial state ${I}^{{}^{\prime\prime}}$. Here, the branch is not the first;
therefore $t_{\\_}{\mathit{start}}$ is not 0. The FindTemporalPlan method
finds sequences of actions that satisfy the propositional preconditions
considering the (new) initial state information. Then, the planning approach
uses the TS method to schedule the action sequence considering the starting
time for the new plan is $t_{\\_}{\mathit{start}}=n_{\\_}{i}$.time. ${H}$
saves the right time information regarding each action in the temporal plan
$\Pi_{\\_}{T}$. Supposing $\Pi_{\\_}{T}$ exists (line 8), the method creates a
new branch branch_child of the tree (new child) and finds the task queue ${Q}$
associated with the branch (line 9) using Algorithm 2. The branch is mapped
(line 10) by labelling the outgoing edges from the node to its child,
considering $u_{\\_}{i}$ information. The node children are then added to the
tree (line 11). The strategy updates the task queue ${Q}$ to compute further
branches considering the new sensing nodes identified in the branch_child
(line 12). If the approach does not find a plan the ExpandTree returns an
empty plan in $root$ (line 13-15).

We implement the tree expansion sequentially and all branches expanded must
return a solvable temporal plan. The algorithm returns a root (line 16) when
all branches are fully expanded. This occurs when the ${Q}$ set is empty and
all possible branches are created. The root builds over the set of nodes
explored during the tree generation. The node labelling and depth information
are fundamental to obtaining the transition tree. Saving the times at which
sensing actions are executed allows the strategy to maintain the action
scheduling in all branches. The TraCE planner iterates the solution by
considering possible updates in the initial deterministic plan solution. If
the algorithm identifies an update in the $\Pi_{\\_}{T}^{*}$ at the time the
$\Pi_{\\_}{TC}$ is achieved, the planner starts the process again. In this
case, TraCE starts finding a new root based on a new initial temporal plan
solution. Notice that if an updated $\Pi_{\\_}{T}^{*}$ exist, the process
starts again independently on the plan in $root$. Therefore, if the last
$root$ was empty, it does not affect the search for a new plan. For one
planning iteration, if the computed plan presents a branching factor $\mu$ and
its depth (maximum) is $\eta$, the tree describing $\Pi_{\\_}{TC}$ has at most
$\mu^{\eta}$ leaves, where the leaves are physical vertices. Therefore, the
TraCE planner calls the temporal planning algorithm at most $\mu^{\eta}$ when
finding a solution. TraCE provides a generic solution. The planner solves
problems with temporal, numeric and perception requirements. However, it can
also solve problems with fully-known initial states as a common temporal
planning problem. Soundness and completeness results for our approach are
presented in Appendix A.

##  5 Experimental Evaluation

Our domain and problems are encoded in PDDL. All experiments in this section
are run on Ubuntu 16.04, with an Intel Core i7-8700, limiting the planner to
30 minutes of<EMAIL_ADDRESS>16GB of RAM. We illustrate the TraCE planner
performance in three experiments that cover offline planning and execution:

Experiment 1. This experiment compares the planner with a state-of-art offline
conditional planner PO-RPR, to evaluate the efficiency of the proposed
approach generating solutions for a set of simple PPOS domains222The original
problems and PO-PRP source are presented in
https://github.com/QuMuLab/planner-for-relevant-policies.git, including
Coloured Balls (cballs), Canadian Traveller’s Problem (ctp-ch), and Doors
(doors). These domains are described in [35]. TraCE uses a revised version of
the domains considering durative actions; numeric constraints are not
included.

Real-World Domains. Experiment 2-3 considers planning domains motivated by
real-world domains333These domains and problems can be found at
https://github.com/YanielCarreno/tcp-domains., particularly robotics
applications, including the Offshore Energy Platform (oep), Manufacturing
Plant (mp), Valve Manipulation (vm) and the Neighbourhoods (n) domains. All
these domains describe robotics problems where temporal requirements (e.g.,
TILs and deadlines), numeric constraints, and partial observability are part
of the mission characteristics.

Experiment 2. Here, we evaluate the quality of the planning algorithm while
generating plans for real-world domains. The problems introduce a set of
robotic scenarios where robots need to implement tasks with temporal and
numeric constraints to maintain the operation, and sensing actions are
required to solve the planing problem.

Experiment 3. We evaluate the system’s performance in a laboratory environment
using a BlueROV2. The experiment analyses the mission execution time
associated with plans that include non-deterministic sensing actions. Here the
problem goals include the manipulation of five valves, sensors need to check
the valves’ state before executing the manipulation. We compare TraCE and
OPTIC plan execution. The execution framework embedding both planners support
replanning during the mission. The experiment evaluates ten different problems
where we introduce five forced failures during the mission, associated with
the valve state and valve localisation.

| Size ($\Delta+{A}$) | PT
---|---|---
Problem | PO-PRP | TraCE | PO-PRP | TraCE
cballs-4-1 | 261 | 232 | 0.02 | 3.45
cballs-4-2 | 13887 | TO | 0.67 | TO
cballs-10-1 | 4170 | TO | 1.57 | TO
ctp-ch-1 | 4 | 6 | 0.00 | 2.01
ctp-ch-5 | 16 | 16 | 0.00 | 7.05
ctp-ch-10 | 31 | 35 | 0.02 | 7.10
ctp-ch-15 | 46 | 42 | 0.07 | 8.24
doors-5 | 82 | 96 | 0.01 | 3.00
doors-7 | 1295 | 2291 | 0.04 | 16.90
doors-9 | 28442 | TO | 1.07 | TO

tableExperiment 1: Plan size and planning time (PT) (sec) for PO-PRP and TraCE
when solving 10 simple PPOS problem instances. TO indicates time out.

| oep | mp | vm | bc
---|---|---|---|---
Problem | BF | Size | PT | BF | Size | PT | BF | Size | PT | BF | Size | PT
1 | 4 | 85 | 41.50 | 2 | 78 | 32.30 | 2 | 44 | 13.40 | 2 | 42 | 9.05
2 | 3 | 77 | 22.15 | 3 | 57 | 47.50 | 2 | 64 | 28.12 | 2 | 156 | 28.63
3 | 2 | 66 | 27.23 | 2 | 108 | 32.52 | 2 | 67 | 21.23 | 2 | 108 | 33.42
4 | 2 | 81 | 32.03 | 4 | 72 | 42.29 | 2 | 95 | 19.92 | 2 | 88 | 14.81
5 | 2 | 102 | 35.50 | 3 | 340 | 69.43 | 2 | 145 | 12.24 | 2 | 234 | 44.70
6 | 3 | 90 | 39.34 | 4 | 75 | 52.18 | 2 | 132 | 14.14 | 2 | 69 | 8.44
7 | 3 | 123 | 53.20 | 3 | 72 | 50.90 | 2 | 80 | 17.15 | 2 | 62 | 6.13
8 | 4 | 116 | 66.23 | 3 | 110 | 84.32 | 2 | 109 | 27.08 | 2 | 92 | 19.13
9 | 5 | TO | TO | 4 | 145 | 54.91 | 2 | 56 | 18.83 | 2 | 134 | 21.12
10 | 6 | TO | TO | 5 | TO | TO | 2 | 134 | 96.90 | 2 | 287 | 48.32

tableExperiment 2: Branching factor (BF), plan size (Size), and planning time
(sec) (PT), including physical and sensing actions, for 10 problem instances
of the real-world robotic application domains using TraCE. TO indicates time
out.

##  6 Discussion

The results for Experiment 1 are presented in Table 5. The TraCE planner finds
a solution for most problem instances solved by PO-PRP in the experimental
domains. The planner obtains plans with sizes similar to PO-PRP’s plan sizes
in several problems (highlighted in red). However, PO-PRP outperforms TraCE in
terms of planning times. TraCE sequentially expands the tree, introducing a
delay in plan generation. In addition, the TraCE planner uses temporal solvers
to create the branches and expand the tree, which affects the planning times.
Temporal planners must meet the causality and temporality constraints imposed
by the model to obtain a valid plan. Therefore, additional time delays using
TraCE compared to PO-PRP might be expected, as the PO-PRP planner does not
consider the time to schedule the action sequence when finding a plan
solution. We introduce time reasoning to address another set of problems that
PO-PRP cannot solve. Here, we present the results for the first
$\Pi_{\\_}{TC}$ obtained. Additional iterations optimise the plan solution by
reducing the plan size; however, this introduces additional delays in the plan
generation.

Table 5 shows that TraCE solves most of the problem instances. The planner
generates solutions with different branching factors, demonstrating that TraCE
deals with complex problems and scales well. As expected, we note that the
size of the plans and the planning times rise with the increase in the number
of sensing actions required in the plan to reduce the knowledge
incompleteness. The oep and mp domain incompleteness leads to more significant
branching factors and planning times as the robots can explore multiple paths
(for the oep domain) and control several flows in a valve (for the mp domain).
TraCE planning times for the problem instances of the oep and mp domains are
significantly higher compared to the other two domains. These domains require
the robots to find plans that deal with concurrent action execution and
numeric constraints along the branches which also affects planning times. The
planner finds solutions for all problem instances of the vm and bc domains.
Although those domains present small branching factors, planning times
increase for complex problems (see problems 9 and 10). The main reason for
this increase is that TraCE needs to find a solution for problems where the
robot needs to recharge to maintain operation.

Figure 3: Experiment 3: Plan execution time (min) in 10 problem instances of
the Example 1 domain over 10 runs using TraCE and OPTIC.

Figure 3 shows that the generation of contingent branches during the planning
stage significantly improves mission implementation times. This is mainly
because OPTIC needs to replan every time a discrepancy between the real value
from the sensor (run-time) and the expected outcome (planning time) is found.
Replanning introduces unnecessary delays in the mission, mainly when we can
use alternative algorithms that deal with certain levels of uncertainty in the
domain. Our approach reduces replanning in non-quiescent environments since
TraCE introduces the contingency analysis that specifies the possible outcomes
from the observation. $\Pi_{\\_}{TC}$ can be affected by noisy sensors, which
might force the system to generate a new plan if the sensing action does not
provide a conclusive outcome.

##  7 Conclusions

We present the TraCE planner, which deals with incomplete knowledge, sensing,
temporal notions, and numeric constraints. Our approach combines temporal plan
construction in a contingent planning framework, offering more robust
solutions for new types of applications. We can model problems that (i)
require temporal reasoning, such as timed initial literals and deadlines; (ii)
manage resources, using numerical fluents, offering more powerful modelling of
mission scenarios; and (iii) and include partial observability. We propose a
PDDL extension to model sensing actions that operate over unknown
propositions, and possible outcomes from non-deterministic sensing actions. We
evaluate the approach in experiments that cover offline planning and execution
in a new set of domains.

## References

  * [1]
  * [2] Alexandre Albore, Hector Palacios & Hector Geffner (2009): _A translation-based approach to contingent planning_.  In: Proc. of the International Joint Conference on Artificial Intelligence (IJCAI), AAAI Press, pp. 1623–1628.
  * [3] J Benton, Amanda Jane Coles & Andrew Coles (2012): _Temporal Planning with Preferences and Time-Dependent Continuous Costs_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, pp. 2–10.
  * [4] Piergiorgio Bertoli, Alessandro Cimatti, Marco Roveri & Paolo Traverso (2001): _Planning in nondeterministic domains under partial observability via symbolic model checking_.  In: Proc. of the International Joint Conference on Artificial Intelligence (IJCAI), 2001, AAAI Press, pp. 473–478.
  * [5] Piergiorgio Bertoli, Alessandro Cimatti, Marco Roveri & Paolo Traverso (2006): _Strong planning under partial observability_.  Artificial Intelligence 170(4-5), pp. 337–384, 10.1016/j.artint.2006.01.004.
  * [6] Blai Bonet & Hector Geffner (2011): _Planning under partial observability by classical replanning: Theory and experiments_.  In: Proc. of the International Joint Conference on Artificial Intelligence (IJCAI), AAAI Press.
  * [7] Daniel Bryce, Subbarao Kambhampati & David E Smith (2006): _Planning graph heuristics for belief space search_.  Journal of Artificial Intelligence Research (JAIR) 26, pp. 35–99, 10.1613/jair.1869.
  * [8] Alberto Camacho, Christian J Muise & Sheila A McIlraith (2016): _From FOND to Robust Probabilistic Planning: Computing Compact Policies that Bypass Avoidable Deadends_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, pp. 65–69.
  * [9] Y. Carreno, A. Ng Jun Hao, Y. Petillot & R. P. A Petrick (2022): _Planning, Execution, and Adaptation for Multi-Robot Systems using Probabilistic and Temporal Planning_.  In: Proc. of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), IFAAMAS, pp. 217–225.
  * [10] Y. Carreno, È. Pairet, Y. Petillot & R. P. A Petrick (2020): _Task allocation strategy for heterogeneous robot teams in offshore missions_.  In: Proc. of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), IFAAMAS, pp. 222–230.
  * [11] Y. Carreno, Y. Petillot & R. P. A. Petrick (2020): _Towards Robust Mission Execution via Temporal and Contingent Planning_.  In: Proc. of the Annual Conference Towards Autonomous Robotic Systems (TAROS), Springer, pp. 214–217, 10.1007/978-3-030-63486-524.
  * [12] Y. Carreno, Y. Petillot & R. P. A Petrick (2021): _Compiling Contingent Planning into Temporal Planning for Robust AUV Deployments_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS) Workshop on Planning and Robotics (PlanRob).
  * [13] Y. Carreno, J. Scharff Willners, Y. Petillot & R. P. A Petrick (2021): _Situation-Aware Task Planning for Robust AUV Exploration in Extreme Environments_.  In: Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) Workshop on Robust and Reliable Autonomy in the Wild (R2AW).
  * [14] Michael Cashmore, Maria Fox, Derek Long, Daniele Magazzeni & Bram Ridder (2017): _Opportunistic planning in autonomous underwater missions_.  IEEE Transactions on Automation Science and Engineering 15(2), pp. 519–530, 10.1109/TASE.2016.2636662.
  * [15] Alessandro Cimatti, Luke Hunsberger, Andrea Micheli & Marco Roveri (2014): _Using timed game automata to synthesize execution strategies for simple temporal networks with uncertainty_.  In: Proc. of the AAAI Conference on Artificial Intelligence, 28.
  * [16] Amanda Jane Coles (2012): _Opportunistic Branched Plans to Maximise Utility in the Presence of Resource Uncertainty_.  In: Proc. of the European Conference on Artificial Intelligence (ECAI), 2012, p. 252\.
  * [17] Amanda Jane Coles, Andrew Coles, Maria Fox & Derek Long (2010): _Forward-Chaining Partial-Order Planning_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, pp. 42–49.
  * [18] Carlo Combi, Luke Hunsberger & Roberto Posenato (2013): _An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty_.  Evaluation 1(1).
  * [19] Carlo Combi, Roberto Posenato, Luca Viganò & Matteo Zavatteri (2019): _Conditional simple temporal networks with uncertainty and resources_.  Journal of Artificial Intelligence Research (JAIR) 64, pp. 931–985.
  * [20] Stephen Cresswell & Alexandra Coddington (2003): _Planning with timed literals and deadlines_.  In: Proc. of Workshop of the UK PlanSIG, pp. 23–35.
  * [21] Patrick Eyerich, Robert Mattmüller & Gabriele Röger (2009): _Using the context-enhanced additive heuristic for temporal and numeric planning_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, pp. 130–137.
  * [22] Janae N Foss & Nilufer Onder (2005): _Generating temporally contingent plans_.  In: Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) Workshop on Planning and Learning in A Priori Unknown or Dynamic Domains.
  * [23] Maria Fox & Derek Long (2003): _PDDL2.1: An extension to PDDL for expressing temporal planning domains_.  Journal of Artificial Intelligence Research (JAIR) 20, pp. 61–124, 10.1613/jair.1129.
  * [24] Hector Geffner & Blai Bonet (2013): _A concise introduction to models and methods for automated planning_.  Synthesis Lectures on Artificial Intelligence and Machine Learning 8(1), pp. 1–141, 10.2200/S00513ED1V01Y201306AIM022.
  * [25] Malik Ghallab, Dana Nau & Paolo Traverso (2004): _Automated Planning: theory and practice_.  Elsevier.
  * [26] Muhammad Adnan Hashmi & Amal El Fallah Seghrouchni (2010): _Merging of temporal plans supported by plan repairing_.  In: Proc. of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2, IEEE, pp. 87–94.
  * [27] Malte Helmert (2009): _Concise finite-domain representations for PDDL planning tasks_.  Artificial Intelligence 173(5-6), pp. 503–535, 10.1016/j.artint.2008.10.013.
  * [28] Karla L Hoffman, Manfred Padberg & Giovanni Rinaldi (2013): _Traveling salesman problem_.  In: Encyclopedia of operations research and management science, Springer, pp. 1573–1578, 10.1007/978-1-4419-1153-71068.
  * [29] Jörg Hoffmann (2003): _The Metric-FF Planning System: Translating “Ignoring Delete Lists” to Numeric State Variables_.  Journal of Artificial Intelligence Research (JAIR) 20, pp. 291–341, 10.1613/jair.1144.
  * [30] Jörg Hoffmann & Ronen Brafman (2005): _Contingent planning via heuristic forward search with implicit belief states_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, pp. 71–80.
  * [31] L. Kunze, N. Hawes, T. Duckett, M. Hanheide & T Krajník (2018): _Artificial intelligence for long-term robot autonomy: A survey_.  IEEE Robotics and Automation Letters (RA-L) 3(4), pp. 4023–4030, 10.1109/LRA.2018.2860628.
  * [32] Derek Long & Maria Fox (2003): _The 3rd international planning competition: Results and analysis_.  Journal of Artificial Intelligence Research (JAIR) 20, pp. 1–59, 10.1613/jair.1240.
  * [33] Derek Long & Maria Fox (2003): _Exploiting a graphplan framework in temporal planning_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, pp. 51–62.
  * [34] Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld & David Wilkins (1998): _PDDL – The Planning Domain Definition Language (Version 1.2)_.  Technical Report CVC TR-98-003/DCS TR-1165, Yale Center for Computational Vision and Control.
  * [35] Christian Muise, Vaishak Belle & Sheila McIlraith (2014): _Computing contingent plans via fully observable non-deterministic planning_.  In: Proc. of the AAAI Conference on Artificial Intelligence, 28.
  * [36] Christian Muise, Sheila McIlraith & Christopher Beck (2012): _Improved non-deterministic planning by exploiting state relevance_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, pp. 172–180.
  * [37] Ahmed Nouman, Volkan Patoglu & Esra Erdem (2021): _Hybrid conditional planning for robotic applications_.  The International Journal of Robotics Research 40(2-3), pp. 594–623, 10.1177/0278364920963783.
  * [38] Héctor Palacios, Alexandre Albore & Hector Geffner (2014): _Compiling contingent planning into classical planning: New translations and results_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS) Workshop on Models and Paradigms for Planning under Uncertainty, AAAI Press.
  * [39] Mark A Peot & David E Smith (1992): _Conditional nonlinear planning_.  In: AIPS, Elsevier, pp. 189–197.
  * [40] Ronald P. A. Petrick & Fahiem Bacchus (2002): _A Knowledge-Based Approach to Planning with Incomplete Information and Sensing_.  In: Proc. of the International Conference on Artificial Intelligence Planning Systems (AIPS), pp. 212–222.
  * [41] Ronald P. A. Petrick & Fahiem Bacchus (2004): _Extending the Knowledge-Based Approach to Planning with Incomplete Information and Sensing_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, pp. 2–11.
  * [42] Son Thanh To, Tran Cao Son & Enrico Pontelli (2011): _Contingent planning as AND/OR forward search with disjunctive representation_.  In: Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, pp. 258–265.
  * [43] Ioannis Tsamardinos, Thierry Vidal & Martha E Pollack (2003): _CTP: A new constraint-based formalism for conditional, temporal planning_.  Constraints 8(4), pp. 365–388, 10.1023/A:1025894003623.
  * [44] Daniel S Weld, Corin R Anderson & David E Smith (1998): _Extending graphplan to handle uncertainty & sensing actions_.  In: Proc. of the AAAI Conference on Artificial Intelligence, pp. 897–904.
  * [45] Ibrahim Faruk Yalciner, Ahmed Nouman, Volkan Patoglu & Esra Erdem (2017): _Hybrid conditional planning using answer set programming_.  Theory and Practice of Logic Programming 17(5-6), pp. 1027–1047, 10.1017/S1471068417000321.
  * [46] Matteo Zavatteri & Luca Viganò (2019): _Conditional simple temporal networks with uncertainty and decisions_.  Theoretical Computer Science 797, pp. 77–101, 10.1016/j.tcs.2018.09.023.

##  Appendix A Soundness and Completeness

Temporal planning requires meeting the causality and scheduling constraints
imposed by a temporal planning problem while looking for a sequence of actions
that reaches the goal state. To achieve a valid plan, temporal planners must
consider the action duration constraints along an unbounded length timeline.
The TraCE planner includes the temporal planning algorithm FindTemporalPlan,
which inherits the soundness and completeness of OPTIC and its predecessor
POPF. The TraCE planner relies on constructing a transition tree where
individual branches denote deterministic temporal plan solutions. This
solution involves solving temporal planning problems with different initial
states and merging them into a tree. Possible outcomes of nondeterministic
sensing actions describe the initial states. Then, for a temporal plan
solution:

######  Definition 9.

A temporal plan is sound (with respect to a given domain and problem) if
action preconditions are satisfied in their respective states, temporal
constraints are met, and the final action produces a state where the goals are
satisfied.

######  Definition 10.

A temporal planner (or temporal planning algorithm) is defined as sound if
every temporal plan that the planner generates (with respect to a given domain
and problem) is a sound plan.

######  Definition 11.

A planner is complete if for every planning domain/problem that has a
solution, the planner is guaranteed to produce a plan.

The FindTemporalPlan temporal planning approach reasons about the state
representation. The state considers: (i) the ordered list of start events
(actions that have started but not yet finished) and the collection of
temporal constraints over the actions in the plan to reach the current world
state. These two state description components are defined over the sets ${P}$
and ${V}$ that hold in the world and support the planning approach’s
soundness.

We can explore the soundness and completeness of the TraCE planner considering
it builds on the temporal plan solutions generated by the sound and complete
method FindTemporalPlan. The temporal planning approach uses the domain
actions to find a _valid plan_ —a plan obtained by a sound a complete
planner—that reaches the goal state. We assume the PDDL actions in the domain
description do not present delayed effects. This means that action effects in
the next state are defined in terms of the current state of the world.
Following these points, the TraCE planner soundness is defined as follows:

######  Lemma 1.

(Soundness). TraCE is a sound planner if every branch of the tree from the
root to a leaf constructed incrementally is a valid temporal plan of physical
and sensing actions.

Proof. Let $\Pi_{\\_}{T}^{\prime}=\langle
a_{\\_}{0},a_{\\_}{1},\cdots,a_{\\_}{n}\rangle$ be a temporal plan that solves
the temporal planning problem ${P}_{\\_}{T}$, where an action $a_{\\_}{i}$ is
a physical or a sensing action ($0\leq i<n$) and the last action $a_{\\_}{n}$
in the plan is a physical action. This plan is valid considering Definition 10
and Definition 11. Let
${H}^{\prime}=\langle\langle{S}_{\\_}{0},t_{\\_}{0}\rangle,a_{\\_}{0},\langle{S}_{\\_}{1},t_{\\_}{1}\rangle,$
$a_{\\_}{1},\cdots,\langle{S}_{\\_}{n},t_{\\_}{n}\rangle,a_{\\_}{n},\langle{S}_{\\_}{n+1},$
$t_{\\_}{n+1}\rangle\rangle$ describe the history of $\Pi_{\\_}{T}^{\prime}$,
where every action $a_{\\_}{i}$ is executed at a belief state ${S}_{\\_}{i}$
at a time $t_{\\_}{i}$ and reaches a belief state ${S}_{\\_}{i+1}$ at a time
$t_{\\_}{i+1}$ ($0\leq i<n$). ${S}_{\\_}{n+1}$ represents the last belief
state that is the goal state considering the problem ${P}_{\\_}{T}$
definition.

For every sensing action $a_{\\_}{j}$ in $\Pi_{\\_}{T}^{\prime}$ ($0\leq j<n$)
with an outcome $u_{\\_}{j}$ observed at
$\langle{S}_{\\_}{j+1},t_{\\_}{j+1}\rangle$, TraCE constructs a task $\langle
n_{\\_}{j},u_{\\_}{j}\rangle$ and introduces it into the queue of tasks ${Q}$.
Let $\Pi_{\\_}{T}^{\prime\prime}=\langle
a_{\\_}{j}=a_{\\_}{0}^{\prime},a_{\\_}{1}^{\prime},\cdots,a_{\\_}{n^{\prime}}^{\prime}\rangle$
a temporal plan with an history
${H}^{\prime\prime}=\langle\langle{S}_{\\_}{j},t_{\\_}{j}\rangle=\langle{S}_{\\_}{0}^{\prime},t_{\\_}{0}^{\prime}\rangle,a_{\\_}{0}^{\prime},\langle{S}_{\\_}{1}^{\prime},t_{\\_}{1}^{\prime}\rangle,a_{\\_}{1}^{\prime},\cdots,\langle{S}_{\\_}{n^{\prime}}^{\prime},t_{\\_}{n^{\prime}}^{\prime}\rangle,$
$a_{\\_}{n^{\prime}}^{\prime},\langle{S}_{\\_}{n^{\prime}+1}^{\prime},t_{\\_}{n^{\prime}+1}^{\prime}\rangle\rangle$
computed for the planning problem characterised by this task. This plan is
valid considering Definition 10 and Definition 11. Then, considering we are
solving temporal planning problems with actions that do not present delayed
effects, the sequence of actions $\langle
a_{\\_}{0},a_{\\_}{1},\cdots,a_{\\_}{j},a_{\\_}{1}^{\prime},\cdots,a_{\\_}{n^{\prime}}^{\prime}\rangle$
is a valid sequential plan computed for a temporal planning problem
${P}_{\\_}{T}$, with history
$\langle\langle{S}_{\\_}{0},t_{\\_}{0}\rangle,a_{\\_}{0},\langle{S}_{\\_}{1},t_{\\_}{1}\rangle,a_{\\_}{1},\cdots,\langle{S}_{\\_}{j},t_{\\_}{j}\rangle,a_{\\_}{j},\langle{S}_{\\_}{1}^{\prime},t_{\\_}{1}^{\prime}\rangle,$
$a_{\\_}{1}^{\prime},\cdots$
$,\langle{S}_{\\_}{n^{\prime}}^{\prime},t_{\\_}{n^{\prime}}^{\prime}\rangle,a_{\\_}{n^{\prime}}^{\prime},\langle{S}_{\\_}{n^{\prime}+1}^{\prime},t_{\\_}{n^{\prime}+1}^{\prime}\rangle\rangle$.
The first part of the plan, $\langle a_{\\_}{0},a_{\\_}{1},\cdots
a_{\\_}{j}\rangle$, does not prevent the last part of the plan, $\langle
a_{\\_}{1}^{\prime},\cdots a_{\\_}{n^{\prime}}^{\prime}\rangle$, and vice
versa, considering $\Pi_{\\_}{T}^{\prime}$ and $\Pi_{\\_}{T}^{\prime\prime}$
are sound and complete their union is sound and complete.

We consider that all contingencies describing the incomplete knowledge in the
initial state are specified in ${U}$. The TraCE planner uses this information
to construct a tree with temporal branches sequentially.

######  Lemma 2.

(Completeness). TraCE is a complete temporally-contingent planner if all known
contingencies are specified by its input ${U}$, and incrementally constructs a
temporal plan ${P}_{\\_}{TC}$, such that the plan size of each sub-branch $b$
computed by one call of the temporal planning approach is smaller than the
size of the first temporal plan obtained $\Pi^{*}_{\\_}{T}$.

Proof. We first show that TraCE is complete considering (i) all known
contingencies are specified by ${U}$, and (ii) the planner incrementally
constructs a temporally contingent plan such that the size of each sub-branch
$b$, computed by one call of the temporal planning approach is smaller than
the size of the first temporal plan obtained $\Pi^{*}_{\\_}{T}$. If all
contingencies for a sensing action lead to a branch in the tree, then the tree
cannot be extended further. Otherwise, for some sensing action contingency,
there is no branch in the tree. This means that there does not exist a
temporal plan whose plan’s size is less than or equal to $\Pi^{*}_{\\_}{T}$.
Considering every temporal plan computed by FindTemporalPlan when building the
tree ${B}$ is connected444Connection is guaranteed by ${H}$ and ${Q}$., such a
branch cannot be reconstructed. If there is not a $\Pi_{\\_}{TC}$ under the
conditions we have mentioned in this proof, TraCE returns a failure. If there
does not exist a temporally-contingent plan under the conditions and TraCE
returns ${B}$, at least one branch of the tree (excluding $\Pi^{*}_{\\_}{T}$)
from the root to a leaf is computed by one call of the temporally contingent
planner. This leads to a contradiction when connecting the branches. Therefore
TraCE either returns a complete temporally-contingent plan or failure.

In our approach, we analyse the plan size considering the number of actions in
the plan. Other metrics such as the plan’s makespan are not suitable for
analysing the completeness in this case as we can find branches (described by
a deterministic plan solution) with a small number of actions; however, with a
higher makespan cost. For instance, consider $\Pi^{n}_{\\_}{TC}$ denotes the
solution for a $n$ robotic planning problem. The $b_{\\_}{1}$ and $b_{\\_}{2}$
represent two branches in the plan with plan size 3 and 6, respectively. The
branches’ makespans are 40 min and 20 min, respectively. The first plan
described by $b_{\\_}{1}$ includes a navigation action with a significant
duration. In this case, there is not a necessary correspondence between the
two metrics. In our problems the makespan is ill-situated compare to the plan
size in order to analyse the plan’s branches. Following this reasoning, the
plan size metric ensures we expand the tree from the most complex branches
(based on the depth) to the simple ones, ensuring a solution where no further
tree expansions are possible.

Plan Correctness. When planning with temporal and contingent conditions, plan
correctness relies on checking (i) the temporal plans that build the branches
are correct, (ii) the temporally-contingent plan satisfies all the goals, and
(iii) the plan has sufficient knowledge at every point that supports its
execution. The step (see Algorithm 1) in the TraCE algorithm CheckExistence
satisfies the first criterion considering FindTemporalPlan returns a correct
plan. The other two conditions are associated with checking the tree expansion
(see Algorithm 3). If all tasks in ${Q}$ are expanded, all branches were
explored. The solution only exists if the approach successfully evaluates all
nodes in the tree, where no nodes precede its parents and children nodes
associated with positive observations come first. If ${Q}$ is empty the plan
solution contains all the necessary knowledge to execute the sensing actions
properly.