Temporal goal reasoning for predictive performance of a tourist application Eliseo Marzal, Jesus Ibañ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 Politècnica de Valè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. Ibañ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. 14