=Paper= {{Paper |id=Vol-1724/paper2 |storemode=property |title=Temporal Goal Reasoning for Predictive Performance of a Tourist Application |pdfUrl=https://ceur-ws.org/Vol-1724/paper2.pdf |volume=Vol-1724 |authors=Eliseo Marzal,Jesus Ibañez,Laura Sebastia,Eva Onaindia |dblpUrl=https://dblp.org/rec/conf/ecai/MarzalISO16 }} ==Temporal Goal Reasoning for Predictive Performance of a Tourist Application== https://ceur-ws.org/Vol-1724/paper2.pdf

Temporal goal reasoning for predictive
performance of a tourist application
Eliseo Marzal, Jesus Ibañez, Laura Sebastia, Eva Onaindia 1

Abstract. Many real-work smart environments make use an application in view of the information collected by some
of IoT to be provided with context-aware services. Addition- unanticipated events. A dynamic formulation of new goals is
ally, these environments require making decisions based on very helpful in situations where: a) the agent’s interests are
predictions about future actions. This involves the use of threaten and a rational anomaly response must be provided;
goal-directed behaviour which may need reasoning about new b) goals are no longer achievable and a graceful degradation in
goals. This paper is devoted to analyze when a new goal can the goal achievement is a convenient action; or c) goal achieve-
be formulated. Once a plan has been computed for a given ment in the future is jeopardized, what affects future perfor-
problem, exogenous events can change the environment so mance [14]. Thereby, goal-directed reasoning can be regarded
that a failure in the plan is caused or an opportunity arises. as a context-aware responsiveness technique.
This paper present a goal reasoning framework where context This paper is particularly devoted to analyze the first step
information acquired from several external sources determines of a goal formulation process; that is, to answer the question
a change that may affect the execution of the current plan. ’when a new goal can be formulated ?’. In some applications,
This change may cause a failure or an opportunity. We show opportunistic behaviour is applied when the sensory input
how the planning system, namely TempLM, is able to predict triggers some enabling conditions to accomplish a task, and
both failures and opportunities thanks to the analysis of the reactive plans are adopted to detect problems and recover
Temporal Landmarks Graph and the Temporal Propositions from them automatically as well as to recognize and exploit
Graph built for the given problem. opportunities [2]. In dynamic and complex environments, like
robotics, opportunities are predicted and executed immedi-
ately in order to provide quick responsiveness but there is no
1 INTRODUCTION usually anticipation of future situations.
One key feature in the application of innovative technologies In less dynamic and reactive environments, typically, goal
like IoT in smart environments is the capability of providing formulation is considered when an anomaly is detected and/or
context-aware services. Besides real-world information, this the system is self-motivated to explore its actions in the world
requires anticipatory behaviour through reasoning; that is, [14]. One approach that has been used to predict or anticipate
making decisions based on predictions and expectations about future plan failures is Case-Based Planning (CBP). In CBP,
future actions [1]. Particularly, many real-world applications when a plan fails, it is usually stored with the justification
involve unanticipated changes that may bring an alteration of of its failure. This information is then retrieved from the case
the current process or a future impact on the application or memory when looking for a similar situation which produced a
even an opportunity to include some new functionality. failure in the past. CBP may be applied before the generation
The purpose of a planning application is to achieve a goal of a plan to anticipate possible problems and avoid situations
through the execution of a plan or course of actions. The ar- that failed in the past, or after a plan has been produced
rival of an unexpected environmental event introduces a new to eliminate plans which may fail [13]. CBP presents though
piece of information that was not taken into account dur- several limitations in its application to smart environments: a)
ing the construction of the plan and that may affect the ac- predicting future failures is subject to finding an identical case
tive plan in several ways. Typically, the first reaction is to in the case memory; and b) CBP allows only for anticipating
check if the plan is no longer executable and, if so, apply a a failure but not for detecting opportunities of pursuing a
repair mechanism or replanning to fix the failure that pre- better goal or a new goal.
vents the active plan from being normally executed. A second In this paper, we present a goal reasoning framework that
consequence is that the unanticipated event provokes a future traces the execution of a temporal plan and identifies if the
anomaly in the plan execution. A third and more interesting context information acquired from several sources determines
derivation is whether the new data brings an opportunity to a change in the plan goals. Particularly, the reasoner detects
achieve a goal that is not currently contemplated in the active situations of future failures and opportunities in the plan ex-
plan. ecution in the context of temporal planning with deadlines.
Goal-directed behaviour is a hallmark of intelligence aimed The framework draws upon TempLM, an approach based on
at discovering the changes that can be applied in the goal of temporal landmarks to handle temporal planning problems
with deadlines [11, 12], and we will show how the reasoner
1 Universitat Politècnica de València, Valencia, Spain, Email: works on a temporal plan of a tourist application.
{emarzal,jeibrui,lstarin,onaindia}@dsic.upv.es

7
tem, shown in Figure 1, is composed of the following modules:
• The Central module is the core of the system. It is in
charge of generating the initial plan, considering the user
profile and the context information. Additionally, it listens
to new events that may require to update this plan.
• The Recommender System selects the recommended
visits for a tourist, given her user profile and the context
information.
• The TempLM planner develops two main tasks: in first
place, it receives the goals computed by the recommender
system and the context information and it builds the initial
plan for the tourist; then, every time a new event is received
by the central module, TempLM analyses it to determine
whether the plan needs to be updated.
In this paper, we will focus on the second task of TempLM,
that is, on the analysis of events to detect failures or oppor-
tunities in the plan.
An example of the problem that we are facing is the follow-
ing. A tourist arrives to Valencia (Spain) and she is staying
at Caro Hotel. She uses our system to obtain a personalized
Figure 1. Architecture agenda for her visit. First, the recommender system analyses
her user profile to select a set of recommended visits with a
recommended duration. Let us assume that the user is recom-
mended to visit the Lonja for 1.5 hours, the Cathedral and the
This paper is organized as follows. First, a motivating ex- Central Market for 2 hours, respectively. These recommended
ample is introduced, as well as the architecture of our system. goals, some other user preferences related to the time windows
Then, some basic definitions referring to automated planning when she prefers to perform the activities along with infor-
and the main characteristics of our planner TempLM are given. mation about the context, such as the opening hours of the
Section 4 introduces new definitions about exogenous events places to visit and the geographical distances between places,
and section 5 explains the analysis that TempLM performs in are compiled into a planning problem that is formulated as an
order to detect future failures or opportunities caused by ex- Automated Planning Problem [8], with durative actions and
ogenous events. Finally, section 6 concludes and outlines some deadlines. This problem is solved by our planner TempLM.
future work. Figure 2 shows the plan obtained for this tourist. The seg-
ments at the bottom represent the opening hours of places
(i.e. the Lonja is open from 10h until 19h) or the time win-
2 TOURIST APPLICATION EXAMPLE dows of preferences indicated by the user (i.e. the time for
In order to illustrate the foundations and contributions of having lunch ranges from 14h to 16h). The green boxes rep-
this paper, a problem in the context of smart tourist will resent the actions in the plan. Specifically, in this domain,
be used. Smart tourism involves several components that three types of actions can be performed: visiting an attrac-
are supported by information and communication technolo- tion, having lunch and moving from one place to another.
gies (ICT) [9]. On one hand, it refers to Smart Destinations, The duration of these actions is determined by the corre-
which are cases of smart cities that apply smart city princi- sponding parameters, that is, the attraction to visit or the ori-
ples to support mobility, resource availability and allocation, gin and destination of the movement action, respectively. For
sustainability and quality of life/visits. Second, the Smart example, the action (visit T Lonja) takes from 10:09h to
resident/visitor experience focuses on technology-mediated 11:29h. In addition, the visit action must consider the opening
tourism experiences and their enhancement through person- hours/preference time window; for example, the action (visit
alization, context-awareness and real-time monitoring [4]. Fi- T Centralmarket) can only be performed from 15:30h until
nally, Smart business refers to the complex business ecosystem 19h. The whole plan must fit into the available time of the
that creates and supports the exchange of touristic resources user indicated in Figure 2 as the timeline, that is, from 10h
and the co-creation of the tourism experience. These smart until 19h. A more detailed description of the compilation of
systems include a wide range of technologies in direct sup- this problem and domain can be found in [10].
port of tourism such as decision support systems and the If we consider this context, there are some events that may
more recent recommender systems, context-aware systems, occur during the visit of our tourist. For example:
autonomous agents searching and mining Web sources, am- • The Lonja may close earlier or open later, that is, its avail-
bient intelligence, as well as systems that create augmented able time window may change; this may imply that the
realities. visit action has to finish before than expected or it has to
In this sense, our system aims to improve the resi- be delayed, respectively.
dent/visitor experience by reacting in advance to changes in • The Ricard Camarena restaurant may be fully-booked,
the environment that may cause failures or opportunities in which implies that another restaurant in the area must be
the previously computed agenda. The architecture of our sys- selected.

8
Figure 2. Plan in execution

• The user may take longer to walk from his hotel to the example, ((not (open Lonja)),19h) is a TIL in I that indicates
Lonja, so the visit action must be delayed. that the Lonja will close at 19h.

These exogenous events are received by the central mod- Definition 3.2 A simple durative action a ∈ O is defined
ule from the external data sources and are analyzed by Tem- as a tuple (pre` , ef f` , pre↔ , prea , ef fa , dur)[5]:
pLM in order to react in consequence. There are some events
that may cause a plan failure (i.e. the attraction is closed) • pre` (prea ) are the start (end) conditions of a: at the state
or a plan modification (i.e. the user gets later that expected in which a starts (ends), these conditions must hold.
to an attraction), whereas others may cause the appearance • ef f` (ef fa ) are the start (end) effects of a: starting (end-
of a free time slot that can be used to include an affor- ing) a updates the world state according to these effects. A
dance/opportunity. In this current work, we will focus on the given collection of effects ef fx , x ∈ {`, a} consists of:
detection of both failures and time slots for opportunities, – ef fx− , propositions to be deleted from the world state;
and we will give some hints about how they can be solved or – ef fx+ , propositions to be added to the world state
exploited.
• pre↔ are the invariant conditions of a: these must hold at
every point in the open interval between the start and end
3 BACKGROUND of a.
• dur is the duration of a.
This section introduces some planning concepts and then it
summarizes the main characteristics of our planner TempLM. An example of an action is shown here:
Action: Eat(?t: tourist, ?r: restaurant)
3.1 Planning concepts pre` = { (free table ?r) }, prea = ∅
pre↔ = { (open ?r), (time for eat ?t), (be ?t ?r) }
Definition 3.1 A temporal planning problem with ef f` = ∅, ef fa = { (eaten ?t) }
deadline constraints is a tuple P = P, O, I, G, D , where dur = (eat time ?t ?r)
P is the set of propositions, O is the set of ground actions, I
and G are sets of propositions that represent the initial state Definition 3.3 A temporal plan Π is a set of pairs (a, t),
and the goal description and D is a set of deadline constraints where a ∈ O and t is the start execution time of a.
of the form (p, t), denoting that proposition p must be achieved
within t time units. The temporal plan for the running example is shown in
Figure 2.
For example, a proposition in I can be (be T Caro), in- Definition 3.4 Given a temporal plan Π, the induced plan
dicating that initially the tourist is at the Caro hotel. It is Π∗ for Π is the set of pairs defined as [7]:
important to note that, apart from the propositions and func-
tions that are initially true, the initial state I may also contain Π∗ = {(a` , t), (aa , t + dur(a))}, ∀(a, t) ∈ Π
timed initial literals (TILs). TILs, which were first introduced
in PDDL2.2[6], are a very simple way of expressing that a For simplicity, we will refer to any pair in Π∗ as an ”action”.
proposition becomes true or false at a certain time point. A For example, Π∗ would include ((walk T Caro Lonja)` ,
TIL can be represented as a pair (p, t), where p is a (positive 10:00) and ((walk T Caro Lonja)a , 10:09). In the induced
or negative) proposition and t is a time point. Specifically, plan, we only consider the start and the end time points of
if p is a positive proposition, then t indicates the time point the actions in the original temporal plan because these are the
at which p becomes true and if it is a negative proposition, time points interesting for building the state resulting from
then t indicates the time point at which p becomes false. For the execution at a certain time point t, as shown below.

9
Definition 3.5 Given a state St defined as a set of proposi- is found to necessarily happen in a solution plan in order to
tions that are true at time t and a pair (ax , t) ∈ Π∗ , an action satisfy the deadlines of the problem goals. The set of tem-
ax is applicable in St if prex (a) ∪ pre↔ (a) ⊆ St . poral landmarks extracted from a problem along with their
relationships form a temporal landmarks graph (TLG) that
With this definition, only the start and the end time points is conveniently used to take decisions during the construction
of the actions are considered. In order to mitigate the fact that of the solution plan and for guiding the search process.
the overall conditions are not checked during the execution of
the action, we check them at the start and the end of the Definition 3.9 A Temporal Landmarks Graph (TLG)
action, although this is not consistent with the definition of a is a directed graph G = (V, E) where the set of nodes V
durative action in PDDL2.1 (where the overall conditions of are landmarks and an edge in E is a tuple of the form
an action a starting at t have to be fulfilled during the interval (li , lj , ≺{n,d} ) which represents a necessary or dependency or-
[t + ε, t + dur(a) − ε]). dering constraint between the landmarks li and lj , denoting
that li must happen before lj in a solution plan.
Definition 3.6 Given a time point t, let Π∗t be the subset
of actions (a, t0 ) ∈ Π∗ such that t0 < t. A temporal state Landmarks are also annotated with various temporal inter-
St is composed by a set of propositions p ∈ P and a set of vals that represent the validity of the corresponding temporal
TILs (denoted by Γt ) resulting from applying the actions in proposition ([11]):
Π∗t from I (denoted by I →Π∗t St ), that is, it is assumed that
the actions in Π∗t are applicable in the corresponding state. • The generation interval of a landmark is denoted by
Formally, we define St recursively, where S0 = I: [ming (l), maxg (l)]. ming (l) represents the earliest time
    point when landmark l can start in the plan. maxg (l) rep-
[ [ resents the latest time point when l must start in order to
St = St−1 −  ef fx− (a) ∪  ef fx+ (a) satisfy D.
∀(ax ,t0 )∈Π∗
t
∀(ax ,t0 )∈Πt • The validity interval of a landmark l is denoted by
([minv (l), maxv (l)]) and it represents the longest time that
For example, the state S10:09 reached after the execution of l can be in the plan.
the action ((walk T Caro Lonja)a ,10:09h) will be the same • The necessity interval of a landmark l is denoted by
as the initial state but S10:09 will contain the new location ([minn (l), maxn (l)]) and it represents the set of time points
of the tourist (be T Lonja). It is important to notice that if when l is required as a condition for an action to achieve
we compute the state S10:05 , then the location of the user is other landmarks.
unknown because the proposition (be T Caro) is deleted at the
start time of the execution of the action and the proposition These intervals are given some initial values that are then
(be T Lonja) is not added until the end time of the action. updated by means of a propagation method, as explained in
[11]. In order to be consistent, both the generation interval
Definition 3.7 The duration (makespan) of an induced and the necessity interval must fall into the validity interval.
plan Π∗ executed from the initial state of the problem is Figure 3 shows a part of the initial TLG built for this prob-
dur(Π∗ ) = max∀(aa ,t)∈Π∗ t −Ti ; i.e., the end time of the ac- lem. The validity interval of a landmark is represented by a
tion that finishes last minus the time point at which the plan segment, the maxg is indicated by a small bold vertical line
starts Ti , assuming that all the actions in Π∗ are applicable (ming is always equal to minv ) and the necessity interval is
in the corresponding state. represented by a green box inside the segment. For example,
the validity interval of the landmark (visited T Cathedral) is
For instance, dur(Π∗ ) in Figure 2 is 7 h. and 9 min., because [12:05h, 19h] and the maxg = 19h; the necessity interval for
the last action ends at 17:09h and the plan starts at 10h. this landmark is empty.
TempLM applies a search process in the space of partial
Definition 3.8 An induced plan Π∗ is a solution for a
plans in order to find a solution plan for a problem P. A node
temporal planning problem with deadline constraints
in the search tree is defined as n = (Π, St , T LGΠ ), where Π
P = P, O, I, G, D if the following conditions hold:
is the conflict-free partial plan of n, St is the state reached at
time t = dur(Π) after the execution of Π from I and T LGΠ is
1. G ⊆ Sg , where I →Π∗t Sg , where t = dur(Π∗ )
the refined TLG after taking into account the information in
2. ∀(p, t) ∈ D : ∃t0 ≤ t : p ∈ St0 , where I →Π∗0 St0
t Π. Given a node n of the search tree, a successor of n results
from adding an executable action a to the partial plan of n,
This definition indicates that it is not only necessary that
provided that a does not cause conflicts with the actions of
a plan Π∗ reaches the goals, but also that all the propositions
n. Hence, the plan of the successor node will contain a newly
present in D are achieved before the corresponding deadline.
added action, information which can be exploited to find new
temporal landmarks in the TLG [12].
3.2 TempLM
TempLM [11] is a temporal planning approach for solving 4 CHANGES IN THE ENVIRONMENT
planning problems with deadlines that has demonstrated an
excellent behaviour in the detection of unsolvable problems This section introduces some definitions related to the man-
and the resolution of overconstrained problems. It draws upon agement of changes in the environment. We assume that in
the concept of temporal landmark, which is a proposition that our system changes happen due to exogenous events.

10
Figure 3. Initial partial TLG for this problem

Definition 4.1 We define an exogenous event θ as a tuple
Table 1. TILs at 14h
(ta , p, tc ), where ta is the arrival time point, that is, the time
point when the exogenous event is received in the system, and
(p, tc ) denotes a TIL. Γ14h−ε
((open Centralmarket), 15:30h),
For example, let ((not (open Centralmarket)),17h) be a TIL ((not (open Centralmarket)), 19h),
in I that indicates that the Central Market will close at 17h. ((not (open Ricardcamarena)), 17h), ...
If at 14h it is known that the Central Market will close one Γ14h
((open Centralmarket), 15:30h),
hour earlier, the exogenous event that will be received by the
((not (open Centralmarket)), 17:30h),
system is the following: (14h, (not (open Centralmarket)), 16h) ((not (open Ricardcamarena)), 17h), ...
and it will invalidate the previous TIL.
Definition 4.4 We define the remaining partial plan at
Definition 4.2 We say that two exogenous events (ta , p, tc ) tcur , denoted by Π∗r , as:
and (t0a , p0 , t0c ) are linked2 if they refer to the same proposition
(p = p0 ) and their arrival time is the same (ta = t0a ). Π∗r = {(a, t) ∈ Π∗ : t ≥ tcur }
We can indicate a modification in the actual duration of Definition 4.5 We define the resulting state of Π∗ex
an action with two linked exogenous events that refer to the (Stcur ) as the state reached after executing the actions in Π∗ex ,
proposition(s) that will be achieved as a result of the execu- that is: I →Π∗ex Stcur
tion of the action. The first one deletes a proposition p at the
time it was expected and the second event adds that propo- Definition 4.6 We define the difference between two states
sition at the new time. For example, if at 13h it is known Si and Sj as:
that the action (eat T RicardCamarena) to be executed from
14h to 15:30h will take 30 minutes more than expected, these Dif f (Si , Sj ) = (Si − Sj ) ∪ (Sj − Si )
two linked exogenous events are received by the system: (13h,
(not (eaten T)), 15:30h) and (13h, (eaten T), 16h). The first Definition 4.7 A discrepancy is a non-empty difference
one deletes the expected event of the tourist having finished between the state that should have been reached with the ex-
lunch at 15:30h and the second adds the proposition at the ecuted part of the plan Stcur and the current observed state
time when the tourist will actually finish having lunch. Stocur , that is: Dif f (Stcur , Stocur ) 6= ∅.
We denote by tcur the current execution time when an event
θ is received and by Stocur the current (observed) state. There- Obviously, the discrepancy between these two sets will at
fore, Stocur will contain the propositions that are true in the least contain the TIL from the event θ. For example, if we
current world and the functions with their actual value in consider the example in Table 1, the event that arrives at
the current world. Moreover, let Γtcur −ε be the set of TILs 14h is reflected in the resulting Γ. Discrepancies may cause
in the state at the time immediately prior to tcur . Stocur will failures or opportunities in the plan.
contain the TIL in θ plus the TILs in Γtcur −ε that are consis-
Definition 4.8 We say that there is a failure in the plan
tent with θ. For example, as Figure 2 shows, Γ14h−ε contains,
if:
among others, the TILs in Table 1 (top). If the event θ =(14h,
(not (open Centralmarket)), 17:30h) is received, then Γ14h in 1. There is a discrepancy at tcur , and
Stocur will be updated as shown in Table 1 (bottom). That is, 2. Stocur →Π∗r Sg : G 6⊆ Sg , that is, the plan does not reach the
the time window in which the Central Market remains open goal due to this discrepancy.
is updated from [15:30h, 19h] to [15:30h, 17:30h].
Note that Π∗ was a solution for the initial planning prob-
Definition 4.3 We define the executed partial plan at lem, that is, it was executable from I. This definition indicates
tcur , denoted by Π∗ex , as: that there has been a change in the environment at a certain
Π∗ex = {(a, t) ∈ Π∗ : t < tcur } time point between I and tcur which causes a failure in the
execution of action a and, consequently, a failure in the exe-
2 For simplicity, we denote by θ a single event or two linked events.
cution of the plan.

11
Definition 4.9 We say that there is an opportunity in the
plan if:

1. There is a discrepancy at tcur , and
2. Stocur →Π∗r Sg : G ⊆ Sg , that is, the plan reaches the goal
in spite of this discrepancy, and
3. this discrepancy causes a different execution of the remain-
ing plan, that is, there is a time point t where the state
reached from Stcur is different from the state reached from
Stocur ; formally, given t ∈ [tcur , dur(Π∗ )], let Π0 be the set
of actions in Π∗r scheduled to start between tcur and t; we
define Sto and St as Stocur →Π0 Sto and Stcur →Π0 St , re-
spectively; the execution of the remaining plan is different
if Dif f (St , Sto ) 6= Dif f (Stcur , Stocur ).

An opportunity in this case is defined as a discrepancy that Figure 5. Example of future failure
still allows to reach the goals but that causes a difference in
the execution of the original plan.
It could be the case that a discrepancy does not cause a
discrepancy between Stcur and Stocur , as indicated in Defini-
failure or an opportunity, because it affects an object that is
tion 4.7. In case of a discrepancy between both states, several
not considered in the current plan.
cases can be found.

5 DETECTION OF FAILURES AND Case 1. The discrepancy does not affect the plan
OPPORTUNITIES IN TempLM This case corresponds to a situation where the exogenous
event θ = (ta , p, tc ) affects a proposition that has not any
The TLG that TempLM builds to solve a planning problem
influence in the plan. This means that the proposition p that
gives an schema of which propositions must be achieved in the
causes the discrepancy is not present in the TPG of the plan
plan, and when they must be achieved in order to reach the
and it is not mutex [3] with any other proposition in the TPG.
goals on time. Additionally, a Temporal Proposition Graph,
Formally, TempLM does not detect any failure or opportunity
which gives an exact picture of the propositions that are
if:
achieved in the plan and when they are achieved, is defined:
/ T P GΠ∗ ∧ ¬∃p0 ∈ T P GΠ∗ : mutex(p, p0 )
p∈
Definition 5.1 A Temporal Proposition Graph (TPG)
For example, let us assume that this exogenous event (10,
for a given induced plan Π∗ is a representation of the time
(not (free table Cantinella)), 13h) is received, indicating that
interval in which a proposition p ∈ P is true during the ex-
the Cantinella restaurant will not have free tables at 13h. This
ecution of Π∗ . This is denoted as the validity interval of the
does not affect the current plan, given that the restaurant
proposition p. A TPG also defines the generation and neces-
where the tourist is going to have lunch is a different one.
sity intervals of a proposition, with the same meaning as for
a landmark in the TLG.
Case 2. A failure is detected
Figure 4 shows the TPG for the plan in Figure 2. In this The second analysis is aimed at detecting a failure caused
case, all the propositions that appear during the execution of by an exogenous event θ = (ta , p, tc ). We distinguish two
the plan are represented. It can be observed that the validity situations: when the event causes a present failure, that is,
interval of the propositions in the TPG is much smaller than ta = tc = tcur or when it causes a future failure, that is,
in the TLG (see Figure 3), given that the TLG is just an ta = tcur < tc . In both cases, a proposition p0 : mutex(p, p0 )
estimation, whereas the TPG is an accurate representation of which belongs to the TPG is deleted before expected when it
the solution plan. For example, in Figure 3, proposition (be is still needed to reach the goals. Formally, TempLM detects
T Cathedral) ranges from 10:05h until 19h, whereas in Figure a failure if:
4 it is shrunk to the interval [11:34h, 13:34h]. p0 ∈ T P GΠ∗ ∧ tc < maxn (p0 )
The aim of this section is to explain how both the TLG
and the TPG can be used in order to detect failures and For example, if at tcur = 10h an event indicating that
opportunities due to exogenous events that may arrive during the Cathedral will be closed at 11h arrives, expressed as
the execution of a plan, and also to give some hints about how θ =(10, (not (open Cathedral)), 11h), a failure is caused be-
they can be solved or exploited. cause tc =11h, mutex((not(openCathedral)), (openCathedral))
As explained in section 2, when a new exogenous event is and tc < maxn (open Cathedral) =13:34h, as it can be ob-
detected by the central module, TempLM receives the cur- served in Figure 5. In this case, TempLM is able to easily
rent execution time tcur , the current observed state Stocur and predict a future failure due to an exogenous event.
the exogenous event θ as input. Then, TempLM computes the Once the failure is detected, two situations can occur: (1)
state that should have been reached as a result of the exe- the problem is unsolvable or (2) the problem can be solved
cution of the plan until time tcur , that is, it computes Stcur . using other elements defined in the context. In order to distin-
The next step is to analyze whether the event θ has caused a guish these situations, TempLM finds the node (Π, S, T LGΠ∗ex )

12
Figure 4. Temporal Proposition Graph of the plan

in the search space built when solving the original problem,
where S = Stcur computed from Π∗ex . If the TLG in this node
is updated with the information about the event θ, this new
information is propagated across the TLG (obtaining T LGθΠ∗ )
and an inconsistency [11] between two intervals of a given
proposition is found, then the problem is unsolvable. It is
important to remark that the propositions in the TLG are
necessary to solve the problem (they are landmarks); there-
fore, if an inconsistency is found in the intervals associated to
a landmark, then the problem is unsolvable. Formally:

∃p ∈ T LGθΠ∗ : maxg (p) ∈
/ [minv (p), maxv (p)]

For example, if the event (10, (not (open Cathedral)), 11h)
arrives, then the problem is unsolvable because, due to θ, the
value of the validity interval of (open Cathedral) changes, i.e. Figure 6. First example of a future opportunity
maxv (open Cathedral) = 11h. This information is propagated
to the proposition (visited T Cathedral) in the T LG∗Π , which
updates maxg (visited T Cathedral) = 11h, indicating that, in
order to reach the goals, the Cathedral must be visited before hard goal; the hard goal is (eaten T), which can be achieved
11h. Given that this value does not belong to the validity by having lunch in any other restaurant. Therefore, a new
interval of (visited T Cathedral), as it can be observed in Figure plan from Π∗ex in which the tourist has lunch in a different
3, there is an inconsistency in these intervals. Therefore, we restaurant could be found by TempLM.
can affirm that the problem, after the arrival of the event, is
unsolvable. In fact, there is not a plan that satisfies the goals, Case 3. An opportunity is detected
because even in the case that the Cathedral is the first visit, The last analysis is devoted to detect an opportunity when
it takes 2 hours and then, it would last until 12:05h, which is a new exogenous event θ = (ta , p, tc ) arrives. In this case, p
later than the time of closing. is a proposition that is achieved before than expected, which
In any other case, TempLM performs the search of permits to consider an action as finished before its complete
a new plan starting from Π∗ex , that is, Π∗r is dis- execution. Formally, TempLM detects an opportunity if:
carded and substituted by the eventually new plan
found. If, for example, an event indicating that the Ri- p ∈ T P GΠ∗ ∧ tc < minv (p)
card Camarena restaurant will be fully-booked at 13:45h
(θ =(13, (not (free table Ricardcamarena)),13:45h) arrives, For example, the arrival of an event in which the visit to
then TempLM detects a failure because tc =13:45h < the Cathedral finishes at 13h, i.e. θ =(13, (visited Cathedral),
maxn (free table Ricardcamarena) =14:00h. In this situation, 13h), causes the detection of an opportunity. The red arrow in
TempLM would be able to find a different solution plan, be- Figure 6 indicates the new time point at which the proposition
cause having lunch at Ricard Camarena restaurant is not a (visited Cathedral) is achieved and the red rectangle indicates

13
6 CONCLUSIONS AND FURTHER
WORK
This paper has introduced a goal reasoning framework where
context information acquired from several external sources
determines a change that may affect the execution of the cur-
rent plan. This change may cause a failure or an opportunity.
We have shown how the planning system, namely TempLM, is
able to predict both failures and opportunities thanks to the
analysis of the Temporal Landmarks Graph and the Temporal
Propositions Graph built for the given problem.
As for further work, our aim is to implement in TempLM
the analysis described in this paper. Then, we will be able
to test the system in a real environment. This will imply an
analysis to decide which events should be considered among
the huge amount of context information that is supplied by
external sources.
Figure 7. Second example of a future opportunity

ACKNOWLEDGMENTS
This work has been partially supported by Spanish Govern-
the available interval of time thanks to this event (which can
ment Project MINECO TIN2014-55637-C2-2-R.
be considered as an opportunity). It can be observed that, in
this example, tcur =13h < minv ((visited Cathedral)) =13:34h
and the necessity interval of (open Cathedral) and (be T Cathe- REFERENCES
dral) are shrunk because (visited Cathedral) has been achieved [1] E. Aarts and J.L. Encarnaao, True visions: the emergence of
before than expected. At this moment, the recommender sys- ambient intelligence, New York. Springer, 200.
tem could be invoked to obtain a new visit (a new goal) to [2] M. Beetz and H. Grosskreutz, ‘Probabilistic hybrid action
be performed during the time interval between 13h and 14h, models for predicting concurrent percept-driven robot behav-
ior’, J. Artif. Intell. Res. (JAIR), 24, 799–849, (2005).
before (be T Ricardcamarena). TempLM would obtain a plan [3] A. Blum and M. Furst, ‘Fast planning through planning graph
to reach this new goal and then the remaining original plan analysis’, Artificial Intelligence, 90(1-2), 281–300, (1997).
would be executed. [4] D. Buhalis and A. Amaranggana, ‘Smart tourism destinations
There is another case where TempLM can detect an oppor- enhancing tourism experience through personalisation of ser-
tunity: vices’, in Information and Communication Technologies in
Tourism 2015, 377–389, Springer, (2015).
[5] A. J. Coles, A. I. Coles, M. Fox, and D. Long, ‘Colin: Planning
p ∈ T P GΠ∗ ∧ tc > minv (p)∧ with continuous linear numeric change’, Journal of Artificial
Intelligence Research, 44, 1–96, (2012).
¬∃q ∈ T P GθΠ∗ : maxg (q) ∈
/ [minv (q), maxv (q)] [6] S. Edelkamp and J. Hoffmann, ‘Pddl2. 2: The language for the
classical part of the 4th international planning competition’,
This case represents the situation when a proposition is 4th International Planning Competition (IPC’04), (2004).
achieved later than expected, but it does not affect the [7] M. Fox and D. Long, ‘Pddl2. 1: An extension to pddl
achievement of the remaining goals. That is, there is not any for expressing temporal planning domains.’, J. Artif. Intell.
proposition q whose intervals are inconsistent after updating Res.(JAIR), 20, 61–124, (2003).
[8] M. Ghallab, D. Nau and P. Traverso, Automated Planning.
the T P GΠ∗ with the exogenous event and propagating the Theory and Practice., Morgan Kaufmann, 2004.
information across the T P GΠ∗ to obtain T P GθΠ∗ . [9] U. Gretzel, M. Sigala, Z. Xiang, and C. Koo, ‘Smart tourism:
For example, let us assume that the tourist now prefers foundations and developments’, Electronic Markets, 25(3),
to have lunch between 14:30h and 16h, instead of between 179–188, (2015).
[10] J. Ibañez, L. Sebastia, and E. Onaindia, ‘Planning tourist
14h and 16h, but the action still takes 90 minutes. This agendas for different travel styles’, in Proceedings of the Eu-
situation triggers the following exogenous event: θ =(13, ropean Conference on Artificial Intelligence (ECAI), p. in
(time for eat T), 14:30h). This event causes that TempLM de- press, (2016).
tects an opportunity because minv (time for eatT) =14:00h [11] E. Marzal, L. Sebastia, and E. Onaindia, ‘On the use of tem-
and tc =14:30h; this provokes that minv (time for eat T) is poral landmarks for planning with deadlines’, in Proc. of the
24th International Conference on Automated Planning and
updated and this information is propagated to minv (eatenT) Scheduling, pp. 172–180. AAAI Press, (2014).
(maxg (eaten T) still belongs to the corresponding validity in- [12] E. Marzal, L. Sebastia, and E. Onaindia, ‘Temporal land-
terval). Additionally, the necessity intervals of (time for eat mark graphs for solving overconstrained planning problems’,
T), (open Ricardcamarena) and (be T Ricardcamarena) are also Knowledge-Based Systems, (2016).
[13] L. Spalazzi, ‘A survey on case-based planning’, Artificial In-
updated, as it is shown in Figure 7. The available time for the telligence Review, 16, 3–36, (2001).
opportunity, also shown in Figure 7, can be used to reach a [14] S. Vattam, M. Klenk, M. Molineaux, and D. W. Aha, ‘Breadth
new goal recommended by the recommender system, as ex- of approaches to goal reasoning: A research survey’, Technical
plained above. report, DTIC Document, (2013).
Thanks to the analysis presented in this section, we have
been able to show how TempLM is able to predict future fail-
ures or opportunities.