ارتباط زمانی منطقی مرتبه اول با شبکه های بیزی برای شبیه سازی سیستم های محاسبات فراگیر

The authors’ previous work discussed a scalable abstract knowledge representation and reasoning scheme for Pervasive Computing Systems, where both low-level and abstract knowledge is maintained in the form of temporal first-order logic (TFOL) predicates. Furthermore, we introduced a novel concept of a generalised event, an abstract event, which we define as a change in the truth value of an abstract TFOL predicate. Abstract events represent real-time knowledge about the system and they are defined with the help of well-formed TFOL expressions whose leaf nodes are concrete, low-level events using our AESL language. In this paper, we propose to simulate pervasive systems by providing estimated knowledge about its entities and situations that involve them. To achieve this goal, we enhance AESL with higher-order function predicates that denote approximate knowledge about the likelihood of a predicate instance having the value True with respect to a time reference. We define a mapping function between a TFOL predicate and a Bayesian network that calculates likelihood estimates for that predicate as well as a confidence level, i.e., a metric of how reliable the likelihood estimation is for that predicate. Higher-order likelihood predicates are implemented by a novel middleware component, the Likelihood Estimation Service (LES). LES implements the above mapping; first, for each abstract predicate, it learns a Bayesian network that corresponds to that predicate from the knowledge stored in the sensor-driven system. Once trained and validated, the Bayesian networks generate a likelihood estimate and a confidence level. This new knowledge is maintained in the middleware as approximate knowledge therefore providing a simulation of the pervasive system, in the absence of real-time data. Last but not least, we describe an experimental evaluation of our system using the Active BAT location system.

Pervasive (a.k.a. Ubiquitous) computing is a post-desktop model of human–computer interaction in which information processing has been thoroughly integrated into everyday objects and activities. Marc Weiser that coined the term pervasive (ubiquitous) computing in 1993 states: we are trying to conceive a new way of thinking about computers in the world, one that takes into account the natural human environment and allows the computers themselves to vanish into the background. In the course of ordinary activities a natural interface means that someone using pervasive computing engages many computational devices and systems simultaneously, and may not necessarily even be aware that they are doing so. Sentient computing [1] is a form of pervasive computing that advocates that applications may become more useful to the user if they are aware of their environment. Awareness comes through an infrastructure of sensors that are deployed on the physical space. Both mobile users and immobile objects are equipped with wearable transceivers. These are able to communicate with the sensor infrastructure so that the object’s position is calculated continually. This information is used to construct a world model which allows location-aware or context-aware applications to be constructed. One famous research prototype of a sentient computing system was the work at AT&T Laboratories, Cambridge. It consisted of an ultrasonic indoor location system called the Active Bat [2] which provided a location accuracy of about 3 cm. The world model was managed via the SPIRIT database, using the CORBA middleware [3] to access information and spatial indexing to deliver high-level events such as Alice has entered the kitchen to listening context-aware applications. The research continues at the Digital Technology Group at the University of Cambridge. Sentient computing presents challenges across computer science: 1. Programmability and scalability. First, as Weiser advocated, a user-centred approach is desirable; the computing infrastructure needs to serve the user not the other way around. This leads to the need of ease of programmability of pervasive systems; the targeted user is a layman not a skilled programmer and he/she should be able to program their own ubiquitous applications in a safe and efficient manner. The user should be able to express abstract, high-level concepts, close to human intuition. Knowledge on such concepts may not be available directly from the sensors and will need to be inferred by reliable mechanisms. Furthermore, the system needs to respond to the user request in near real time. As calculating a response involves correlating a potentially very large number of events, a scalable reasoning mechanism is necessary. 2. Correctness and robustness. Second, the system needs to be robust against failure of the sensor infrastructure that it relies on. What happens if the sensors fail? Can we still reason about contextual situations if no real-time data is available? How accurate is our reasoning then? Can we still provide enough feedback to the user so that they can make informed decisions? Can we store historical information about the environment and use it to detect trends in the data and predict user behaviour? Is this information useful for improving the Sentient system itself? 1.1. Programmable, scalable reasoning for pervasive computing applications The development of even a conceptually simple sentient application is nontrivial because it involves the cooperation of several distributed elements, such as sensors, databases, or effectors. Imagine we want to automatically initiate the playback of a user’s favourite music whenever he starts working. For that, the application would register with the world model (to receive that user’s presence events) and with a keyboard activity monitor event source (to be notified when the keyboard activity of the user’s computer changes significantly). When a user is both in his office and typing regularly, then the application would initiate the music playback. On the other hand, significant work on middleware has been done in the area of distributed systems. There, the event-based paradigm is used to decouple communication between distributed objects, and enables the interchange of events between them in an asynchronous form through Notification Channels. Effort has also been directed towards defining more meaningful composite events [4], which are typically recognised by finite-state machines. In previous work [5] the authors merged the two above paradigms in order to provide high-level tools for programming pervasive applications. More specifically, they defined a scalable knowledge-base system for pervasive computing. The authors’ approach uses deductive systems in an unusual way, namely, in order to allow applications to register inference rules that generate abstract knowledge from low-level, sensor-derived knowledge. Scalability is achieved by maintaining a dual-layer knowledge representation mechanism for reasoning about the Sentient Environment that functions in a similar way to a two-level cache. Furthermore, we introduced a novel concept of a generalised event, an abstract event [6] and [7], which we define as a notification of transparent changes in distributed state. An extension to the publish/subscribe protocol is discussed, in which a higher-order service (Abstract Event Detection Service) publishes its interface; this service takes a TFOL abstract event definition in our Abstract Event Specification Language (AESL) as an argument and in return publishes an interface to a further service (an Abstract Event Detector) which notifies transitions between the values True and False of the formula, thus providing a more natural and efficient interface to applications. Abstract Event detectors are structured as Rete Networks [8] and form a deductive knowledge-base. In addition to Rete-based abstract event detectors, in previous work [9] we introduced the concept of detectors implemented as hidden Markov models (HMMs). We demonstrated that HMM-based detectors are appropriate for detecting invariant patterns such as user trajectories that correspond to sitting down, getting up, walking, being titted and being still. AESL, enhanced as above, allows the programmer to design pervasive applications that have a number of desirable features. First, they are easy to program by linking an abstract event specification to a desirable action through a temporal first-order logic formula that is easy to understand. Second, they can reason with absence of information, which is not possible with event-based languages for distributed systems, that are based on finite-state machines [6]. As a result, AESL supports an increased level of expressiveness that is closer to human intuition. 1.1.1. Example Using the definitions and nomenclature proposed in [5] and [6] we can define applications that link abstract state predicates to action predicates. In this paper, the former are always prefixed with H_(High-level), H_UserInLocation(uid, role, rid, rattr, t). For example, in the formula: View the MathML sourceH_UserColocation(John,Eli,rid,rattr,timestamp)⇒SendEmail(Eli,‘returnJohn’sbook!’) Turn MathJax on the abstract state predicate H_UserColocation(John, Eli, rid, rattr, timestamp) denotes the situation where Eli is located in the same room as John. The action predicate SendEmail denotes that when the event of Eli being co-located with John is detected in the system, a reminder email should be sent to Eli through the appropriate middleware component reminding her to return John’s book. 1.2. Correctness and robustness The authors’ previous work [10] proposed a satisfiability service for pervasive applications. This service validates application logic with respect to a world model, based on TFOL. An application that consists of several AESL definitions, as explained previously, can only be executed if it is satisfiable (in the sense of Boolean satisfiability), else it is rejected. Our satisfiability service functions introduces constraints that reflect spatio-temporal properties of the modelled environment, e.g., a user cannot be in two places at the same time; It also supports event loss, e.g., if a user appears to jump from one room to another in very short time then some intermediate events are probably lost. Errors in the application logic, e.g., references to unknown objects in the world model and logical impossibilities are also catered for. This paper is concerned with robustness, i.e., finding ways to keep our middleware system functioning in the presence of faults. Robustness is partly addressed by means of the above satisfiability service, e.g., by applying spatio-temporal constraints that lead to detecting event loss, as explained earlier. However, we feel that a more systematic approach to robustness is necessary and that is the subject of this paper. We propose to simulate our system providing approximate knowledge about its entities. Simulation constitutes a graceful degradation of our system, in the absence of real-time information, as advocated by the software engineering discipline. 1.3. Our contribution In view of the above requirements, we aim to provide a simulation framework for Sentient Computing that operates when the real-time operation is not available. This allows some of the functionality to still be available to the user in the absense of real-time data (graceful degradation). Our contribution is threefold: 1. On one hand, we extend AESL’s TFOL abstract event model with higher-order functions and functional predicates. These function predicates act as meta-predicate objects: they take as input an AESL predicate or another function. In the following equation, f is a higher-order function on the set of state predicates of our model. equation(1) f(predicate)f(predicate) Turn MathJax on More specifically, the likelihood higher-order function takes as input an n-ary predicate and it returns a pair of values: a likelihood estimate and a confidence level for the given predicate. The likelihood estimate is an estimate of the probability that an instance of a predicate will hold with respect to a time reference and the confidence level assigns a metric of how reliable the estimation is. More specifically, using the equivalent notation of a functional predicate like in Prolog, we define Probability to be the functional predicate that corresponds to the above likelihood estimation function. Probability associates that associates an element (x) of the set of all predicates {P} with a tuple consisting of a likelihood estimate (le) and the associated confidence level (cl) for a given time reference (t). View the MathML sourceProbability(x)=〈le,cl〉|x∈P,〈le,cl〉∈R2≡Probability(〈le,cl,〉,x) Turn MathJax on or equivalently: Probability(le,cl,x)Probability(le,cl,x) Turn MathJax on 2. On the other hand, we introduce a mapping function f′ between TFOL predicates and Bayesian networks [11] and [12]. equation(2) f′(predicate)∈{BayesianNetworks}f′(predicate)∈{BayesianNetworks} Turn MathJax on From Eqs. (1) and (2) we can deduce that for f′ = f, there exists some higher-order probability function that is implemented as a Bayesian network that corresponds to that predicate. 3. We introduce the Likelihood Estimation Service (LES), a prototype middleware component that implements the above theoretical constructs. Furthermore, we evaluate LES through an experimental evaluation of that took place at the University of Cambridge using the Active BAT location technology. 1.3.1. Example Enhancing the predicates of our model with a binary tuple consisting of a likelihood estimate and a confidence level as above, is equivalent to generating new knowledge and maintaining it in the system. Such knowledge can be seen as approximate knowledge that can be either low-level or abstract and either current or future. It can be used as an approximation of the current knowledge about the system, whenever the sensor infrastructure is not available, thus enabling applications to remain functional under uncertainty. For example, when Eli is at home, she may not have access to the real-time data produced by the Active BAT system, operating in college. However, she may have access only to the approximate knowledge. Based on the latter, she may decide to put the effort of cycling in all the way to college, only if the probability that any of her supervisors will be in their respective offices is higher than 60% and the confidence level for that prediction is higher than 50%. Eli may use a TFOL specification such as the one below to query the system about her supervisor’s whereabouts: View the MathML sourceProb(le,cl,H_UserInLocation(uid,supervisor,rid,supervisor-office,10–12))∧(le>60%)∧(cl>50%)⇒SendEmail(Eli,‘supervisorshouldbepresenttoday’) Turn MathJax on 1.4. Paper layout First, we explain briefly some background concepts that underpin our work (Section 2). Next, we provide a formal definition of our TFOL model enhanced with higher-order functions (Section 3). Section 4 discusses our implementation and it includes a mapping function between well-formed TFOL formulae and Bayesian networks. Section 5 discusses the Likelihood Estimation Service (LES), our middleware component that implements the above mapping. Section 6 presents our experimental evaluation using the Active BAT system. It is also concerned with evaluating the predictions and the presence of incomplete data. Section 7 discusses related literature thus clarifying our contribution and finally, Section 8 concludes.

As is advocated by the results, the Bayes classifier is an appropriate method for predicting the likelihood that a predicate instance will be generated in the system at some time. The naïve Bayes classifier is a powerful classifier and although it assumes that all the predictor variables are conditionally independent, it has impressive results even for the cases where there are dependencies between the variables, such as the pairs role-uid and rid-rattr. The classification accuracy is a measure of the predictive power of the classifier. The reliability of the likelihood estimation depends on the size of each class, which is a percentage of the size of the test set. Although prediction was demonstrated for location data (H_UserInLocation) predicate, it can be re-applied to other high-level knowledge predicates too, e.g., View the MathML sourceH_ClosestEmptyLocationH_UserCoLocation Turn MathJax on The work presented here is part of the SCAFOS framework for extracting higher-level inferences from ubiquitous systems, developed in the first author’s thesis [20]. The thrust of the thesis is that for applications to make high-level use of very low-level sensor-based data we need programmable middleware rather than the superbly engineered, but still hard-coded facilities which systems like SPIRIT [2] provide. Bayesian prediction can be used in that context in order to enable decision making, even when data sources that provide the data (knowledge predicate instances) are unavailable, e.g., in case the location system fails. The estimated likelihood for a predicate instance can be used in order to form application specifications thus enhancing expressiveness. E.g., an application may be interested in knowing the probability that meetings between at least 20 people will take place during the day and if the probability is more than 50%, a new batch order for cookies should be issued. The user may query the probability of an event in order to decide to respond differently to a very likely situation rather than an unlikely one; e.g. He may decide not to register for notifications for an unlikely situation.. In general, prediction is very important for Sentient Computing because it constitutes an acceptable solution when trading information certainty for saving on resources such as computational cost and a user’s time, or when certainty is compromised by a failure. E.g., instead of a user’s position an estimation of where the user may be is given as answer to a query or published as an event. This does not require the location system to monitor that user, thus saving on computation and communication cost. A quantification scheme where user’s time is treated as a resource which is associated with a cost, is discussed in [66]. Likelihood estimation can be used in order to evaluate other forms of inference for the same predicate instance, such as the one based on logical deduction [67]. As new predicates instances (new data) are deduced at high rates, both the structure and the parameters may need to be re-estimated. This is known as real-time classification and there are several approaches to it and some can be extremely slow (e.g., incremental EM for parameter re-estimation). We propose to perform semi-real-time estimation. The Bayesian Network operates on a parallel thread. Whenever re-estimation followed by performance evaluation is performed, LES buffers any incoming predicates until the Bayesian Network is available again.