CROSS-REFERENCE TO RELATED APPLICATION

[0001] This application claims priority to a U.S. provisional patent application Ser. No. 62/354,875, filed June 27, 2016, the contents of which are incorporated herein by reference as if fully enclosed herein.

FIELD

[0002] This disclosure relates generally to distributed computer systems and, more particularly, to an active activity planning system and method for supporting temporal constraints.

BACKGROUND

[0003] Unless otherwise indicated herein, the materials described in this section are not prior art to the claims in this application and are not admitted to the prior art by inclusion in this section.

SUMMARY

[0004] A summary of certain embodiments disclosed herein is set forth below. It should be understood that these aspects are presented merely to provide the reader with a brief summary of these certain embodiments and that these aspects are not intended to limit the scope of this disclosure. Indeed, this disclosure may encompass a variety of aspects that may not be set forth below.

[0005] Embodiments of the disclosure related to an active activity planning system comprises a knowledge base, the knowledge base comprising TBox and ABox, a query processor for receiving a query including temporal constraints, and a temporal reasoned, wherein the query processor converts the query into a formal representation and output the formal representation to the temporal reasoner for computing the likelihood score of satisfying temporal constraints in the query. The formal representation is an abstract temporal constraint network (abstract TCN). The abstract TCN comprising timestamps TCNT, Edges TCNE, and Constraints TCNc.

[0006] According to another aspect of the disclosure, a computer program product comprising a computer readable medium having computer readable program code for temporal reasoning, the computer program product comprises computer readable program code for obtaining timestamps TCNT, Edges TCNE, and Constraints TCNc and computer readable program code for obtaining possible shortest routes of least two of timestamps TCNT, Edges TCNE, and Constraints TCNc.

BRIEF DESCRIPTION OF THE DRAWINGS

[0007] These and other features, aspects, and advantages of this disclosure will become better understood when the following detailed description of certain exemplary embodiments is read with reference to the accompanying drawings in which like characters represent like arts throughout the drawings, wherein:

[0008] FIG. 1 is a block diagram illustrating an activity planning system for handling temporal reasoning;

[0009] FIGs. 2 and 3 illustrate taxonomy trees KBTR of temporal relationships, its domain, and range constraints;

[0010] FIG. 4 illustrates a block diagram of an example of a query comprises of a graphical semantic representation and temporal constraints; [0011] FIG. 5 illustrates a probability distribution representation of an abstract temporal constraint network (abstract TCN) converted by a temporal reasoner from a query depicted in FIG. 4;

[0012] FIG. 6 illustrates an interval distribution representation of an abstract temporal constraint network (abstract TCN) where the edge labels are replaced with the duration representation such as an interval distribution;

[0013] FIG. 7 illustrates an example of a map; and

[0014] FIG. 8 illustrates a state-space search tree.

DETAILED DESCRIPTION

[0015] The following description is presented to enable any person skilled in the art to make and use the described embodiments, and is provided in the context of a particular application and its requirements. Various modifications to the described embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the described embodiments. Thus, the described embodiments are not limited to the embodiments shown, but are to be accorded the widest scope consistent with the principles and features disclosed herein.

[0016] Various operations may be described as multiple discrete actions or operations in turn, in a manner that is most helpful in understanding the claimed subject matter. However, the order of description should not be construed as to imply that these operations are necessarily order dependent. In particular, these operations may not be performed in the order of presentation. Operations described may be performed in a different order than the described embodiment. Various additional operations may be performed and/or described operations may be omitted in additional embodiments.

[0017] FIG. 1 is a block diagram illustrating an activity planning system 100 for handling temporal reasoning. The activity planning system 100 comprises a knowledge base 102, a query processor 104, and a temporal reasoner 106. The knowledge base 102 defined as description logic comprises TBox and ABox. Further details of the knowledge base 102 will be described in FIG. 2. Now going back to FIG. 1 , a query 108 including temporal constraints is input into the query processor 104. The query, for example, "I want to eat a Chinese food for lunch and should be back to the office by 2:00pm." The query processor 104 converts the query into a formal representation. The formal representation is a formal graphical semantic representation grounded on an ontology defined in the knowledge base 102. The temporal reasoner 106 processes the query representation output by the query processor 104 against the knowledge base which defines a set of object such as restaurants and their properties such as a location, working hours, and so forth. For each object, the temporal reasoner 106 produces a normalized score from 0 to 1 to indicate the degree of how likely the object satisfies the temporal constraints imposed by the query 108. In other words, the temporal reasoned 106 automatically generates an activity plan including multiple point-of-interests (POIs) give temporal constraints. For example, the restaurant is far from the current location and is unlikely to satisfy the query 108 if the current time is close to 2:00pm. 0 means that the object can never satisfy the constraints and 1 means that the object always satisfies the constraints. [0018] FIGs. 2 and 3 illustrate taxonomy trees KBTR of temporal relationships, its domain, and range constraints. The knowledge base 102 defined as description logic comprises TBox 200 in FIG. 2 and ABox 300 in FIG. 3. TBox 200 defines concepts and its inheritance relations and ABox 300 defines instances and assertions about the instances. Now referring to FIG. 2, an example of TBox 200 in a graphical notation is illustrated. KBc defines the concepts included in the knowledge base. In an example, KBc is a set of nodes such as Thing, Event, Move, Eat, Entity, Place, Restaurant, Attribute, GeoAttribute. KBR defines all possible relations that a pair of concepts can have, either direct or indirect subclass of Event, Entity or Attribute. KBTR defines the taxonomic relationship between the concepts such as (Thing, Event), (Thing Entity), and so forth. KBRC defines the selectional preference for the domain and range of each relation. In the example, the domain of origin is Event and its subclass whereas the range is Entity and its subclass. At the top of the taxonomy tree, the top two level is fixed as a default defined as KBc where Thing is a root node and Event, Entity, and Attribute are a direct subclass of Thing. Every event concept defines a starting time (starting time) and an ending time (ending time) as its default slots. The two slots, starting_time and ending_time, are used when a user specifies temporal constrains. Every event concept further defines duration as its default slot, which provides a link to a user-defined duration function that calculates the estimated duration of the event. For example, for the Eat concept, the duration function may return [30, 60] for the peak time and [20,40] for the others. The interval notation [30,60] represents that the total time taken for eating is estimated to be between 30 and 60. The duration function varies, depending on the type of restaurant such as fast food vs sit-down restaurant. A set of instructions stored in a computer readable medium causes the temporal reasoner 106 of FIG. 1 to support interval-based duration representation and normal-distribution based duration representation. Every event concept has a duration slot which provides a link to a user-defined duration function. The output of the duration function is either a pair of (l ,u) for the interval representation (to denote [l ,u]) or a set of parameters for the probability-based representation, for example, a pair of (μ, σ) for the Gaussian distribution representation (to denote Ν(μ, σ ² )).

[0019] Now referring to FIG. 3, an example of ABox 300 in a graphical notation is illustrated. ABox 300 defines as (Instances KBi, Propositions KBp). KBi defines instances and KBp defines the assertions about the instances. For example, KBi is {*home, *company, McDonaldl , KFC12} and KBp is {(*home, isa, PlaCE),... , (*home, geocoord, (35.6, 42.3),... } . All instances defined in ABox is an instance of Entity.

[0020] FIG. 4 illustrates a block diagram of an example of a query 400 comprises of a graphical semantic representation and temporal constraints. The query 400 is defined as a 5-tuple, (Instances Q ₁ , Node Typing Q _NT , Propositions Q _PR , Constraints Q _c , queried nodes Q _Q ). Q ₁ represents a set of the instances used in the query. QNT represents the types of the instances. QPR is a set of the triples defining the relationship between the instances. Qc represents a set of the temporal constraints that are an inequality condition for a timestamp variable. QQ is a set of the instances that are to be queried. An example of the query "I have to arrive at my company between 2:20pm and 3: 10pm. On the way, I would like to eat a food. Please recommend a restaurant." The instances of the Entity are drawn from the ABox of the KB (e.g., *home, *company) and the event instances Qi are a solemnized instance of an event concept (e.g. Move -by-Carl, Eatl, Move-by-Car2). One special node is a queried node q which denotes an object to be queried. In an example "14:20" ≤ Move-by-Car2.ending_time ≤ "15:10", the arrival time between 2:20pm and 3:10pm at the company are the temporal constraints Qc to be observed.

[0021] FIG. 5 illustrates a probability distribution representation of an abstract temporal constraint network (abstract TCN) 500 converted by a temporal reasoner from a query 400 depicted in FIG. 4. The duration information such as the duration of Move -by-Carl is underspecified. For each candidate object, the abstract TCN 500 is specialized into a representation where the underspecified duration information is filled with concrete duration representations. The activity planning system 100 uses abstract TCN to compute the likelihood of the object satisfying the temporal constraints. An abstract TCN is defined as a triple, (Timestamps TCNT, Edges TCNE, Constraints TCNc). TCNT represents a set of timestamp variables each of which corresponds to the starting time or ending time slot of each event. For example, T ₁ and T ₂ correspond to Move -by-Carl . starting_time and Move -by-Carl .ending_time, respectively. TCNE represents a set of edges. For example, {(T ₁ , Move -by-Carl , T ₂ ), (T ₂ ,≤,T ₃ ), (T ₃ , Eatl,T ₄ ), (T ₄ ,≤,T5), (T5, Move-by-Car2, T ₆ )} . The edge is annotated with a label, which us either an event instance name or≤ (as in T ₁ ,≤,Tj) represents that Tj occurs after T ₁ . TCNc represents a set of constraints imposed on TCNT.

[0022] To generate the abstract TCN from the query representation 400 illustrated in FIG. 4, for each event, two timestamp variables are created and connected with an edge with the event name as a label. For (ev1 , next-event, ev2) in the query, an edge is created to connect T; and Tj where T ₁ and Tj are the timestamp variables corresponding to evl .ending_time and ev2.starting_time, respectively. The constraints in the query are then converted by replacing the starting_time and the ending time slots with the timestamp variables. For each object, the temporal reasoner creates a TCN from a given abstract TCN by replacing the edge labels, e.g. the event instance names and≤ with the interval ([l ,u]) ³ or a probability distribution Ν(μ, σ ² ).

[0023] FIG. 6 illustrates an interval distribution representation of an abstract temporal constraint network (abstract TCN) 600 where the edge labels are replaced with the duration representation such as an interval distribution. Various sets of instructions may be provided to retrieve a single POI instance given the temporal constraints. In one embodiment, algorithm 1 is provided below for reasoning on an interval-based TCN.

[0024] Where the latest possible time for T; is maxk

are edge labels.

[0025] In another embodiment, algorithm 2 is provided below for reasoning on the Normal-distribution based TCN.

[0028] An example of an extended query 600 is illustrated in FIG. 6. The extended query 600 allows multiple objects to be queried, e.g. QQ has multiple elements {ql,q2} . The order of the events is unspecified. The next-event is omitted and that the query 600 is fragmented into individual event representations. Also, the Move event instances needed to visit ql , q2 and *target are also omitted. Specific POIs, e.g. *Target in the query are provided to indicate the must-visit locations.

[0029] FIG. 7 illustrates an example of a map 700. The extended reasoning algorithm 4 first computes shortest routes only with the must-visit places. Which is to say, only POIs near the backbone route are identified. Once the backbone route is detected, the final routes which include the POIs specified by the user are constructed as now illustrated in FIG. 8 as a state-space search tree.

[0030] Eq. 1 indicates the shortest distance between s and the backbone route is the minimum over the shortest distances between s and each line segment defined by

[0031] Let (pi,q be a projected coordinate of s onto the extended line segment between (a;, bi) and (aj+i, b i+i) as shown in Eq. 2.

[0032] It can be easily checked if (pi,q is within the line segment defined by (a;, bi) and (a _i +1, a _i +1) if and only if (p _i , a _i )*(p _i - a _i +i)≤ (q _i - b _i )*(q _; - b _i+1 )≤ 0. [0033] The embodiments described above have been shown by way of example, and it should be understood that these embodiments may be susceptible to various modifications and alternative forms. It should be further understood that the claims are not intended to be limited to the particular forms disclosed, but rather to cover all modifications, equivalents, and alternatives falling with the sprit and scope of this disclosure.

[0034] Embodiments within the scope of the disclosure may also include non- transitory computer-readable storage media or machine-readable medium for carrying or having computer-executable instructions or data structures stored thereon. Such non-transitory computer-readable storage media or machine-readable medium may be any available media that can be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such non-transitory computer- readable storage media or machine-readable medium can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to carry or store desired program code means in the form of computer-executable instructions or data structures. Combinations of the above should also be included within the scope of the non-transitory computer-readable storage media or machine-readable medium.

[0035] Embodiments may also be practiced in distributed computing environments where tasks are performed by local and remote processing devices that are linked (either by hardwired links, wireless links, or by a combination thereof) through a communications network. [0036] Computer-executable instructions include, for example, instructions and data which cause a general purpose computer, special purpose computer, or special purpose processing device to perform a certain function or group of functions. Computer-executable instructions also include program modules that are executed by computers in stand-alone or network environments. Generally, program modules include routines, programs, objects, components, and data structures, etc. that perform particular tasks or implement particular abstract data types. Computer-executable instructions, associated data structures, and program modules represent examples of the program code means for executing steps of the methods disclosed herein. The particular sequence of such executable instructions or associated data structures represents examples of corresponding acts for implementing the functions described in such steps.

[0037] While the patent has been described with reference to various embodiments, it will be understood that these embodiments are illustrative and that the scope of the disclosure is not limited to them. Many variations, modifications, additions, and improvements are possible. More generally, embodiments in accordance with the patent have been described in the context or particular embodiments. Functionality may be separated or combined in blocks differently in various embodiments of the disclosure or described with different terminology. These and other variations, modifications, additions, and improvements may fall within the scope of the disclosure as defined in the claims that follow.