Many real-work smart environments make use of IoT to be provided with context-aware services. Additionally, these environments require making decisions based on predictions about future actions. This involves the use of goal-directed behaviour which may need reasoning about new goals. This paper is devoted to analyze when a new goal can be formulated. Once a plan has been computed for a given problem, exogenous events can change the environment so that a failure in the plan is caused or an opportunity arises. This paper present a goal reasoning framework where context information acquired from several external sources determines a change that may affect the execution of the current plan. This change may cause a failure or an opportunity. We show 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.
One key feature in the application of innovative technologies
like IoT in smart environments is the capability of providing
context-aware services. Besides real-world information, this
requires anticipatory behaviour through reasoning; that is,
making decisions based on predictions and expectations about
future actions [
The purpose of a planning application is to achieve a goal through the execution of a plan or course of actions. The arrival of an unexpected environmental event introduces a new piece of information that was not taken into account during the construction of the plan and that may affect the active plan in several ways. Typically, the first reaction is to check if the plan is no longer executable and, if so, apply a repair mechanism or replanning to fix the failure that prevents the active plan from being normally executed. A second consequence is that the unanticipated event provokes a future anomaly in the plan execution. A third and more interesting derivation is whether the new data brings an opportunity to achieve a goal that is not currently contemplated in the active plan.
Goal-directed behaviour is a hallmark of intelligence aimed
at discovering the changes that can be applied in the goal of
an application in view of the information collected by some
unanticipated events. A dynamic formulation of new goals is
very helpful in situations where: a) the agent’s interests are
threaten and a rational anomaly response must be provided;
b) goals are no longer achievable and a graceful degradation in
the goal achievement is a convenient action; or c) goal
achievement in the future is jeopardized, what affects future
performance [
This paper is particularly devoted to analyze the first step
of a goal formulation process; that is, to answer the question
’when a new goal can be formulated ?’. In some applications,
opportunistic behaviour is applied when the sensory input
triggers some enabling conditions to accomplish a task, and
reactive plans are adopted to detect problems and recover
from them automatically as well as to recognize and exploit
opportunities [
In less dynamic and reactive environments, typically, goal
formulation is considered when an anomaly is detected and/or
the system is self-motivated to explore its actions in the world
[
In this paper, we present a goal reasoning framework that
traces the execution of a temporal plan and identifies if the
context information acquired from several sources determines
a change in the plan goals. Particularly, the reasoner detects
situations of future failures and opportunities in the plan
execution in the context of temporal planning with deadlines.
The framework draws upon TempLM, an approach based on
temporal landmarks to handle temporal planning problems
with deadlines [
This paper is organized as follows. First, a motivating example is introduced, as well as the architecture of our system. Then, some basic definitions referring to automated planning and the main characteristics of our planner TempLM are given. Section 4 introduces new definitions about exogenous events and section 5 explains the analysis that TempLM performs in order to detect future failures or opportunities caused by exogenous events. Finally, section 6 concludes and outlines some future work. 2
In order to illustrate the foundations and contributions of
this paper, a problem in the context of smart tourist will
be used. Smart tourism involves several components that
are supported by information and communication
technologies (ICT) [
In this sense, our system aims to improve the resident/visitor experience by reacting in advance to changes in the environment that may cause failures or opportunities in the previously computed agenda. The architecture of our sys• 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 opportunities in the plan.
An example of the problem that we are facing is the
following. A tourist arrives to Valencia (Spain) and she is staying
at Caro Hotel. She uses our system to obtain a personalized
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
recommended to visit the Lonja for 1.5 hours, the Cathedral and the
Central Market for 2 hours, respectively. These recommended
goals, some other user preferences related to the time windows
when she prefers to perform the activities along with
information about the context, such as the opening hours of the
places to visit and the geographical distances between places,
are compiled into a planning problem that is formulated as an
Automated Planning Problem [
Figure 2 shows the plan obtained for this tourist. The
segments at the bottom represent the opening hours of places
(i.e. the Lonja is open from 10h until 19h) or the time
windows of preferences indicated by the user (i.e. the time for
having lunch ranges from 14h to 16h). The green boxes
represent the actions in the plan. Specifically, in this domain,
three types of actions can be performed: visiting an
attraction, having lunch and moving from one place to another.
The duration of these actions is determined by the
corresponding parameters, that is, the attraction to visit or the
origin and destination of the movement action, respectively. For
example, the action (visit T Lonja) takes from 10:09h to
11:29h. In addition, the visit action must consider the opening
hours/preference time window; for example, the action (visit
T Centralmarket) can only be performed from 15:30h until
19h. The whole plan must fit into the available time of the
user indicated in Figure 2 as the timeline, that is, from 10h
until 19h. A more detailed description of the compilation of
this problem and domain can be found in [
If we consider this context, there are some events that may occur during the visit of our tourist. For example: • The Lonja may close earlier or open later, that is, its available time window may change; this may imply that the visit action has to finish before than expected or it has to be delayed, respectively. • The Ricard Camarena restaurant may be fully-booked, which implies that another restaurant in the area must be selected. • The user may take longer to walk from his hotel to the Lonja, so the visit action must be delayed. example, ((not (open Lonja)),19h) is a TIL in I that indicates that the Lonja will close at 19h.
These exogenous events are received by the central module from the external data sources and are analyzed by TempLM in order to react in consequence. There are some events that may cause a plan failure (i.e. the attraction is closed) or a plan modification (i.e. the user gets later that expected to an attraction), whereas others may cause the appearance of a free time slot that can be used to include an affordance/opportunity. In this current work, we will focus on the detection of both failures and time slots for opportunities, and we will give some hints about how they can be solved or exploited. 3
This section introduces some planning concepts and then it summarizes the main characteristics of our planner TempLM. 3.1
Definition 3.1 A temporal planning problem with deadline constraints is a tuple P = P, O, I, G, D , where 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 and the goal description and D is a set of deadline constraints of the form (p, t), denoting that proposition p must be achieved within t time units.
For example, a proposition in I can be (be T Caro),
indicating that initially the tourist is at the Caro hotel. It is
important to note that, apart from the propositions and
functions that are initially true, the initial state I may also contain
timed initial literals (TILs). TILs, which were first introduced
in PDDL2.2[
An example of an action is shown here:
Action: Eat(?t: tourist, ?r: restaurant) pre` = { (free table ?r) }, prea = ∅ pre↔ = { (open ?r), (time for eat ?t), (be ?t ?r) } ef f` = ∅, ef fa = { (eaten ?t) } dur = (eat time ?t ?r) Definition 3.3 A temporal plan Π is a set of pairs (a, t), where a ∈ O and t is the start execution time of a.
The temporal plan for the running example is shown in Figure 2.
Definition 3.4 Given a temporal plan Π, the induced plan
Π∗ for Π is the set of pairs defined as [
Π∗ = {(a`, t), (aa, t + dur(a))}, ∀(a, t) ∈ Π For simplicity, we will refer to any pair in Π∗ as an ”action”.
For example, Π∗ would include ((walk T Caro Lonja)`, 10:00) and ((walk T Caro Lonja)a, 10:09). In the induced plan, we only consider the start and the end time points of the actions in the original temporal plan because these are the time points interesting for building the state resulting from the execution at a certain time point t, as shown below. Definition 3.5 Given a state St defined as a set of propositions that are true at time t and a pair (ax, t) ∈ Π∗, an action ax is applicable in St if prex(a) ∪ pre↔(a) ⊆ St.
With this definition, only the start and the end time points of the actions are considered. In order to mitigate the fact that the overall conditions are not checked during the execution of the action, we check them at the start and the end of the action, although this is not consistent with the definition of a durative action in PDDL2.1 (where the overall conditions of an action a starting at t have to be fulfilled during the interval [t + ε, t + dur(a) − ε]).
Definition 3.6 Given a time point t, let Πt∗ be the subset of actions (a, t0) ∈ Π∗ such that t0 < t. A temporal state St is composed by a set of propositions p ∈ P and a set of TILs (denoted by Γt) resulting from applying the actions in Πt∗ from I (denoted by I →Πt∗ St), that is, it is assumed that the actions in Πt∗ are applicable in the corresponding state. Formally, we define St recursively, where S0 = I: St = St−1 −
For example, the state S10:09 reached after the execution of the action ((walk T Caro Lonja)a,10:09h) will be the same as the initial state but S10:09 will contain the new location of the tourist (be T Lonja). It is important to notice that if we compute the state S10:05, then the location of the user is unknown because the proposition (be T Caro) is deleted at the start time of the execution of the action and the proposition (be T Lonja) is not added until the end time of the action. Definition 3.7 The duration (makespan) of an induced plan Π∗ executed from the initial state of the problem is dur(Π∗) = max∀(aa,t)∈Π∗ t −Ti; i.e., the end time of the action that finishes last minus the time point at which the plan starts Ti, assuming that all the actions in Π∗ are applicable in the corresponding state.
For instance, dur(Π∗) in Figure 2 is 7 h. and 9 min., because the last action ends at 17:09h and the plan starts at 10h. Definition 3.8 An induced plan Π∗ is a solution for a temporal planning problem with deadline constraints P = P, O, I, G, D if the following conditions hold: 1. G ⊆ Sg, where I →Πt∗ Sg, where t = dur(Π∗) 2. ∀(p, t) ∈ D : ∃t0 ≤ t : p ∈ St0 , where I →Πt∗0 St0
This definition indicates that it is not only necessary that a plan Π∗ reaches the goals, but also that all the propositions present in D are achieved before the corresponding deadline. 3.2
TempLM [
Landmarks are also annotated with various temporal
intervals that represent the validity of the corresponding temporal
proposition ([
These intervals are given some initial values that are then
updated by means of a propagation method, as explained in
[
TempLM applies a search process in the space of partial
plans in order to find a solution plan for a problem P. A node
in the search tree is defined as n = (Π, St, T LGΠ), where Π
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
the refined TLG after taking into account the information in
Π. 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,
provided that a does not cause conflicts with the actions of
n. Hence, the plan of the successor node will contain a newly
added action, information which can be exploited to find new
temporal landmarks in the TLG [
This section introduces some definitions related to the management of changes in the environment. We assume that in our system changes happen due to exogenous events. Definition 4.1 We define an exogenous event θ as a tuple (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.
For example, let ((not (open Centralmarket)),17h) be a TIL in I that indicates that the Central Market will close at 17h. If at 14h it is known that the Central Market will close one hour earlier, the exogenous event that will be received by the system is the following: (14h, (not (open Centralmarket)), 16h) and it will invalidate the previous TIL.
Definition 4.2 We say that two exogenous events (ta, p, tc) and (t0a, p0, t0c) are linked2 if they refer to the same proposition (p = p0) and their arrival time is the same (ta = t0a).
We can indicate a modification in the actual duration of an action with two linked exogenous events that refer to the proposition(s) that will be achieved as a result of the execution of the action. The first one deletes a proposition p at the time it was expected and the second event adds that proposition at the new time. For example, if at 13h it is known that the action (eat T RicardCamarena) to be executed from 14h to 15:30h will take 30 minutes more than expected, these two linked exogenous events are received by the system: (13h, (not (eaten T)), 15:30h) and (13h, (eaten T), 16h). The first one deletes the expected event of the tourist having finished lunch at 15:30h and the second adds the proposition at the time when the tourist will actually finish having lunch.
We denote by tcur the current execution time when an event o θ is received and by Stcur the current (observed) state. Thereo fore, Stcur will contain the propositions that are true in the current world and the functions with their actual value in the current world. Moreover, let Γtcur−ε be the set of TILs o in the state at the time immediately prior to tcur. Stcur will contain the TIL in θ plus the TILs in Γtcur−ε that are consistent with θ. For example, as Figure 2 shows, Γ14h−ε contains, among others, the TILs in Table 1 (top). If the event θ =(14h, (not (open Centralmarket)), 17:30h) is received, then Γ14h in o Stcur will be updated as shown in Table 1 (bottom). That is, the time window in which the Central Market remains open is updated from [15:30h, 19h] to [15:30h, 17:30h].
Definition 4.3 We define the executed partial plan at tcur, denoted by Πe∗x, as:
Πe∗x = {(a, t) ∈ Π∗ : t < tcur} 2 For simplicity, we denote by θ a single event or two linked events. 1. There is a discrepancy at tcur, and
o 2. Stcur →Πr∗ Sg : G 6⊆ Sg, that is, the plan does not reach the goal due to this discrepancy.
Note that Π∗ was a solution for the initial planning problem, that is, it was executable from I. This definition indicates that there has been a change in the environment at a certain time point between I and tcur which causes a failure in the execution of action a and, consequently, a failure in the execution of the plan. Definition 4.9 We say that there is an opportunity in the plan if: 1. There is a discrepancy at tcur, and
o 2. Stcur →Π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 remaining plan, that is, there is a time point t where the state reached from Stcur is different from the state reached from o Stcur ; 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 Stcur →Π0 Sto and Stcur →Π0 St, reo 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 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 failure or an opportunity, because it affects an object that is not considered in the current plan. 5
The TLG that TempLM builds to solve a planning problem gives an schema of which propositions must be achieved in the plan, and when they must be achieved in order to reach the goals on time. Additionally, a Temporal Proposition Graph, which gives an exact picture of the propositions that are achieved in the plan and when they are achieved, is defined: Definition 5.1 A Temporal Proposition Graph (TPG) for a given induced plan Π∗ is a representation of the time interval in which a proposition p ∈ P is true during the execution of Π∗. This is denoted as the validity interval of the proposition p. A TPG also defines the generation and necessity intervals of a proposition, with the same meaning as for a landmark in the TLG.
Figure 4 shows the TPG for the plan in Figure 2. In this case, all the propositions that appear during the execution of the plan are represented. It can be observed that the validity interval of the propositions in the TPG is much smaller than in the TLG (see Figure 3), given that the TLG is just an estimation, whereas the TPG is an accurate representation of the solution plan. For example, in Figure 3, proposition (be T Cathedral) ranges from 10:05h until 19h, whereas in Figure 4 it is shrunk to the interval [11:34h, 13:34h].
The aim of this section is to explain how both the TLG and the TPG can be used in order to detect failures and opportunities due to exogenous events that may arrive during the execution of a plan, and also to give some hints about how they can be solved or exploited.
As explained in section 2, when a new exogenous event is detected by the central module, TempLM receives the curo rent execution time tcur, the current observed state Stcur and the exogenous event θ as input. Then, TempLM computes the state that should have been reached as a result of the execution of the plan until time tcur, that is, it computes Stcur . The next step is to analyze whether the event θ has caused a
Case 1. The discrepancy does not affect the plan
This case corresponds to a situation where the exogenous
event θ = (ta, p, tc) affects a proposition that has not any
influence in the plan. This means that the proposition p that
causes the discrepancy is not present in the TPG of the plan
and it is not mutex [
p ∈/ T P GΠ∗ ∧ ¬∃p0 ∈ T P GΠ∗ : mutex(p, p0)
For example, let us assume that this exogenous event (10, (not (free table Cantinella)), 13h) is received, indicating that the Cantinella restaurant will not have free tables at 13h. This does not affect the current plan, given that the restaurant where the tourist is going to have lunch is a different one.
The second analysis is aimed at detecting a failure caused by an exogenous event θ = (ta, p, tc). We distinguish two situations: when the event causes a present failure, that is, ta = tc = tcur or when it causes a future failure, that is, ta = tcur < tc. In both cases, a proposition p0 : mutex(p, p0) which belongs to the TPG is deleted before expected when it is still needed to reach the goals. Formally, TempLM detects a failure if:
p0 ∈ T P GΠ∗ ∧ tc < maxn(p0)
For example, if at tcur = 10h an event indicating that the Cathedral will be closed at 11h arrives, expressed as θ =(10, (not (open Cathedral)), 11h), a failure is caused because tc =11h, mutex((not(openCathedral)), (openCathedral)) and tc < maxn(open Cathedral) =13:34h, as it can be observed in Figure 5. In this case, TempLM is able to easily predict a future failure due to an exogenous event.
Once the failure is detected, two situations can occur: (1)
the problem is unsolvable or (2) the problem can be solved
using other elements defined in the context. In order to
distinguish these situations, TempLM finds the node (Π, S, T LGΠe∗x )
in the search space built when solving the original problem,
where S = Stcur computed from Πe∗x. 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 [
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. 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 11h. Given that this value does not belong to the validity interval of (visited T Cathedral), as it can be observed in Figure 3, there is an inconsistency in these intervals. Therefore, we can affirm that the problem, after the arrival of the event, is unsolvable. In fact, there is not a plan that satisfies the goals, because even in the case that the Cathedral is the first visit, it takes 2 hours and then, it would last until 12:05h, which is later than the time of closing.
In any other case, TempLM performs the search of a new plan starting from Πe∗x, that is, Πr∗ is discarded and substituted by the eventually new plan found. If, for example, an event indicating that the Ricard Camarena restaurant will be fully-booked at 13:45h (θ =(13, (not (free table Ricardcamarena)),13:45h) arrives, then TempLM detects a failure because tc =13:45h < maxn(free table Ricardcamarena) =14:00h. In this situation, TempLM would be able to find a different solution plan, because having lunch at Ricard Camarena restaurant is not a hard goal; the hard goal is (eaten T), which can be achieved by having lunch in any other restaurant. Therefore, a new plan from Πe∗x in which the tourist has lunch in a different restaurant could be found by TempLM.
The last analysis is devoted to detect an opportunity when a new exogenous event θ = (ta, p, tc) arrives. In this case, p is a proposition that is achieved before than expected, which permits to consider an action as finished before its complete execution. Formally, TempLM detects an opportunity if: p ∈ T P GΠ∗ ∧ tc < minv(p)
For example, the arrival of an event in which the visit to the Cathedral finishes at 13h, i.e. θ =(13, (visited Cathedral), 13h), causes the detection of an opportunity. The red arrow in Figure 6 indicates the new time point at which the proposition (visited Cathedral) is achieved and the red rectangle indicates the available interval of time thanks to this event (which can 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 Cathedral) are shrunk because (visited Cathedral) has been achieved before than expected. At this moment, the recommender system could be invoked to obtain a new visit (a new goal) to be performed during the time interval between 13h and 14h, before (be T Ricardcamarena). TempLM would obtain a plan to reach this new goal and then the remaining original plan would be executed.
There is another case where TempLM can detect an opportunity:
p ∈ T P GΠ∗ ∧ tc > minv(p)∧ ¬∃q ∈ T P GθΠ∗ : maxg(q) ∈/ [minv(q), maxv(q)]
This case represents the situation when a proposition is achieved later than expected, but it does not affect the achievement of the remaining goals. That is, there is not any proposition q whose intervals are inconsistent after updating the T P GΠ∗ with the exogenous event and propagating the information across the T P GΠ∗ to obtain T P GθΠ∗ .
For example, let us assume that the tourist now prefers to have lunch between 14:30h and 16h, instead of between 14h and 16h, but the action still takes 90 minutes. This situation triggers the following exogenous event: θ =(13, (time for eat T), 14:30h). This event causes that TempLM detects an opportunity because minv(time for eatT) =14:00h and tc =14:30h; this provokes that minv(time for eat T) is updated and this information is propagated to minv(eatenT) (maxg(eaten T) still belongs to the corresponding validity interval). Additionally, the necessity intervals of (time for eat T), (open Ricardcamarena) and (be T Ricardcamarena) are also updated, as it is shown in Figure 7. The available time for the opportunity, also shown in Figure 7, can be used to reach a new goal recommended by the recommender system, as explained above.
Thanks to the analysis presented in this section, we have been able to show how TempLM is able to predict future failures or opportunities.
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 current 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.
This work has been partially supported by Spanish Government Project MINECO TIN2014-55637-C2-2-R.