Compositional reasoning for weighted Markov decision processes

Weighted Markov decision processes (MDPs) have long been used to model quantitative aspects of systems in the presence of uncertainty. However, much of the literature on such MDPs takes a monolithic approach, by modelling a system as a particular MDP; properties of the system are then inferred by analysis of that particular MDP. In contrast in this paper we develop compositional methods for reasoning about weighted MDPs, as a possible basis for compositional reasoning about their quantitative behaviour. In particular we approach these systems from a process algebraic point of view. For these we define a coinductive simulation-based behavioural preorder which is compositional in the sense that it is preserved by structural operators for constructing weighted MDPs from components.     

Automated assume-guarantee reasoning for omega-regular systems and specifications

We develop a learning-based automated assume-guarantee (AG) reasoning framework for verifying ω-regular properties of concurrent systems. We study the applicability of non-circular (AG-NC) and circular (AG-C) AG proof rules in the context of systems with infinite behaviors. In particular, we show that AG-NC is incomplete when assumptions are restricted to strictly infinite behaviors, while AG-C remains complete. We present a general formalization, called LAG, of the learning based automated AG paradigm. We show how existing approaches for automated AG reasoning are special instances of LAG. We develop two learning algorithms for a class of systems, called ∞-regular systems, that combine finite and infinite behaviors. We show that for ∞-regular systems, both AG-NC and AG-C are sound and complete. Finally, we show how to instantiate LAG to do automated AG reasoning for ∞-regular, and ω-regular, systems using both AG-NC and AG-C as proof rules.     

Admission control of hospitalization with patient gender by using Markov decision process

Admission control of hospitalization considering patient gender is an interesting issue in the study of hospital bed management. This paper addresses the decision on the admission of patients who should immediately be admitted into a same-gender room or rejected. Note that a patient is admitted depending on different conditions, such as his/her health condition, gender, the availability of beds, the length of stay, and the reward of hospitalization. Focusing on the key factor, patient gender, this paper sets up an infinite-horizon total discounted reward Markov decision process model with the purpose to maximize the total expected reward for the hospital, which leads to an optimal dynamic policy. Then, the structural properties of the optimal policy are analyzed. Additionally, a value iteration algorithm is proposed to find the optimal policy. Finally, some numerical experiments are used to discuss how the optimal dynamic policy depends on some key parameters of the system. Furthermore, the performance of the optimal policy is discussed though comparison with the three other policies by means of simulating different scenarios.     

Learning-based scheduling of flexible manufacturing systems using case-based reasoning

A common method of dynamically scheduling jobs in Flexible Manufacturing Systems (FMSs) is to employ dispatching rules. However, the problem associated with this method is that the performance of the rules depends on the state of the system, but there is no rule that is superior to all the others for all the possible states the system might be in. It would therefore be highly desirable to employ the most suitable rule for each particular situation. To achieve this, this paper presents a scheduling approach that uses Case-Based Reasoning (CBR), which analyzes the system's previous performance and acquires "scheduling knowledge," which determines the most suitable dispatching rule at each particular moment in time. Simulation results indicate that the proposed approach produces significant performance improvements over existing dispatching rules.     

Energy-efficient multisite offloading policy using Markov decision process for mobile cloud computing

Mobile systems, such as smartphones, are becoming the primary platform of choice for a user’s computational needs. However, mobile devices still suffer from limited resources such as battery life and processor performance. To address these limitations, a popular approach used in mobile cloud computing is computation offloading, where resource-intensive mobile components are offloaded to more resourceful cloud servers. Prior studies in this area have focused on a form of offloading where only a single server is considered as the offloading site. Because there is now an environment where mobile devices can access multiple cloud providers, it is possible for mobiles to save more energy by offloading energy-intensive components to multiple cloud servers. The method proposed in this paper differentiates the data- and computation-intensive components of an application and performs a multisite offloading in a data and process-centric manner. In this paper, we present a novel model to describe the energy consumption of a multisite application execution and use a discrete time Markov chain (DTMC) to model fading wireless mobile channels. We adopt a Markov decision process (MDP) framework to formulate the multisite partitioning problem as a delay-constrained, least-cost shortest path problem on a state transition graph. Our proposed Energy-efficient Multisite Offloading Policy (EMOP) algorithm, built on a value iteration algorithm (VIA), finds the efficient solution to the multisite partitioning problem. Numerical simulations show that our algorithm considers the different capabilities of sites to distribute appropriate components such that there is a lower energy cost for data transfer from the mobile to the cloud. A multisite offloading execution using our proposed EMOP algorithm achieved a greater reduction on the energy consumption of mobiles when compared to a single site offloading execution.     

Markov decision process: Fuzzy approach

This paper propose a fuzzy concept of return cost of Markov Decision Process (MDP) model which is an application of dynamic programming to the solution of probabilistic decision process. The return structure of the process is measured by Triangular Fuzzy Number (TFN). The comparison method is based on the ranking method.

The goal of this research is to provide the optimal solution for a finite stage and infinite stage which can be manipulated to study the real-world situation for the purpose of aiding the decision maker [6,7].     

A successive approximation algorithm for an undiscounted Markov decision process

In this paper we consider a completely ergodic Markov decision process with finite state and decision spaces using the average return per unit time criterion. An algorithm is derived which approximates the optimal solution. It will be shown that this algorithm is finite and supplies upper and lower bounds for the maximal average return and a nearly optimal policy with average return between these bounds.     

The control of a two-level Markov decision process by time aggregation

The solution of Markov Decision Processes (MDPs) often relies on special properties of the processes. For two-level MDPs, the difference in the rates of state changes of the upper and lower levels has led to limiting or approximate solutions of such problems. In this paper, we solve a two-level MDP without making any assumption on the rates of state changes of the two levels. We first show that such a two-level MDP is a non-standard one where the optimal actions of different states can be related to each other. Then we give assumptions (conditions) under which such a specially constrained MDP can be solved by policy iteration. We further show that the computational effort can be reduced by decomposing the MDP. A two-level MDP with M upper-level states can be decomposed into one MDP for the upper level and M to M(M-1) MDPs for the lower level, depending on the structure of the two-level MDP. The upper-level MDP is solved by time aggregation, a technique introduced in a recent paper [Cao, X.-R., Ren, Z. Y., Bhatnagar, S., Fu, M., & Marcus, S. (2002). A time aggregation approach to Markov decision processes. Automatica, 38(6), 929-943.], and the lower-level MDPs are solved by embedded Markov chains.     

Automated handwashing assistance for persons with dementia using video and a partially observable Markov decision process

This paper presents a real-time vision-based system to assist a person with dementia wash their hands. The system uses only video inputs, and assistance is given as either verbal or visual prompts, or through the enlistment of a human caregiver’s help. The system combines a Bayesian sequential estimation framework for tracking hands and towel, with a decision-theoretic framework for computing policies of action. The decision making system is a partially observable Markov decision process, or POMDP. Decision policies dictating system actions are computed in the POMDP using a point-based approximate solution technique. The tracking and decision making systems are coupled using a heuristic method for temporally segmenting the input video stream based on the continuity of the belief state. A key element of the system is the ability to estimate and adapt to user psychological states, such as awareness and responsiveness. We evaluate the system in three ways. First, we evaluate the hand-tracking system by comparing its outputs to manual annotations and to a simple hand-detection method. Second, we test the POMDP solution methods in simulation, and show that our policies have higher expected return than five other heuristic methods. Third, we report results from a ten-week trial with seven persons moderate-to-severe dementia in a long-term care facility in Toronto, Canada. The subjects washed their hands once a day, with assistance given by our automated system, or by a human caregiver, in alternating two-week periods. We give two detailed case study analyses of the system working during trials, and then show agreement between the system and independent human raters of the same trials.     

一种基于区间规则的条件证据网络推理决策方法

针对证据网络推理方法无法对区间规则进行表示和推理的问题, 提出一种基于区间规则的条件证据网络推理决策方法. 该方法针对模糊规则的条件概率或信度为不确定区间的情况, 可同时表达不确定性和模糊性; 并将区间不确定规则转化为区间条件信度函数作为证据网络的结点参数, 通过条件推理和证据融合得到条件证据网络中各结点幂集空间中焦元的随机分布作为决策依据. 最后, 通过空中目标态势评估实例, 验证了所提出方法的有效性.

     

Similarity-margin based feature selection for symbolic interval data

In this paper we propose a feature selection method for symbolic interval data based on similarity margin. In this method, classes are parameterized by an interval prototype based on an appropriate learning process. A similarity measure is defined in order to estimate the similarity between the interval feature value and each class prototype. Then, a similarity margin concept has been introduced. The heuristic search is avoided by optimizing an objective function to evaluate the importance (weight) of each interval feature in a similarity margin framework. The experimental results show that the proposed method selects meaningful features for interval data. In particular, the method we propose yields a significant improvement on classification task of three real-world datasets.     

Hybrid approach using case-based reasoning and rule-based reasoning for domain independent clinical decision support in ICU

This paper presents a hybrid approach of case-based reasoning and rule-based reasoning, as an alternative to the purely rule-based method, to build a clinical decision support system for ICU. This enables the system to tackle problems like high complexity, low experienced new staff and changing medical conditions. The purely rule-based method has its limitations since it requires explicit knowledge of the details of each domain of ICU, such as cardiac domain hence takes years to build knowledge base. Case-based reasoning uses knowledge in the form of specific cases to solve a new problem, and the solution is based on the similarities between the new problem and the available cases. This paper presents a case-based reasoning and rule-based reasoning based model which can provide clinical decision support for all domains of ICU unlike rule-based inference models which are highly domain knowledge specific. Experiments with real ICU data as well as simulated data clearly demonstrate the efficacy of the proposed method.     

Fuzzy c-means clustering methods for symbolic interval data

This paper presents adaptive and non-adaptive fuzzy c-means clustering methods for partitioning symbolic interval data. The proposed methods furnish a fuzzy partition and prototype for each cluster by optimizing an adequacy criterion based on suitable squared Euclidean distances between vectors of intervals. Moreover, various cluster interpretation tools are introduced. Experiments with real and synthetic data sets show the usefulness of these fuzzy c-means clustering methods and the merit of the cluster interpretation tools.     

连续时间Markov决策过程互模拟等价及逻辑保持

模型检测中,Markov决策过程可以建模具有不确定性的系统,然而状态空间爆炸问题将会影响系统验证的成败与效率,互模拟等价可以用于系统状态的简约.在强互模拟关系的基础上,给出Markov决策过程模型弱互模拟等价关系的概念,导出了连续时间Markov决策过程及其内嵌离散时间Markov决策过程互模拟等价关系的内在联系;在强互模拟等价关系逻辑特征保持的基础上,给出弱互模拟等价关系下的逻辑保持性质,证明了弱互模拟等价的两个状态,同时满足除下一步算子外的连续随机逻辑公式,从而可以将原模型中的验证问题转换为简约后模型的验证问题,提高验证的效率.     

Logistic regression-based pattern classifiers for symbolic interval data

This paper introduces different pattern classifiers for interval data based on the logistic regression methodology. Four approaches are considered. These approaches differ according to the way of representing the intervals. The first classifier considers that each interval is represented by the centres of the intervals and performs a classic logistic regression on the centers of the intervals. The second one assumes each interval as a pair of quantitative variables and performs a conjoint classic logistic regression on these variables. The third one considers that each interval is represented by its vertices and a classic logistic regression on the vertices of the intervals is applied. The last one assumes each interval as a pair of quantitative variables, performs two separate classic logistic regressions on these variables and combines the results in some appropriate way. Experiments with synthetic data sets and an application with a real interval data set demonstrate the usefulness of these classifiers.     

Classification of process trends based on fuzzified symbolic representation and hidden Markov models

This paper presents a strategy to represent and classify process data for detection of abnormal operating conditions. In representing the data, a wavelet-based smoothing algorithm is used to filter the high frequency noise. A shape analysis technique called triangular episodes then converts the smoothed data into a semi-qualitative form. Two membership functions are implemented to transform the quantitative information in the triangular episodes to a purely symbolic representation. The symbolic data is classified with a set of sequence matching hidden Markov models (HMMs), and the classification is improved by utilizing a time correlated HMM after the sequence matching HMM. The method is tested on simulations with a non-isothermal CSTR and compared with methods that use a back-propagation neural network with and without an ARX model.     

Transparent decision support using statistical reasoning and fuzzy inference

A framework for the development of a decision support system (DSS) that exhibits uncommonly transparent rule-based inference logic is introduced. A DSS is constructed by marrying a statistically based fuzzy inference system (FIS) with a user interface, allowing drill-down exploration of the underlying statistical support, providing transparent access to both the rule-based inference as well as the underlying statistical basis for the rules. The FIS is constructed through a "pattern discovery" based analysis of training data. Such an analysis yields a rule base characterized by simple explanations for any rule or data division in the extracted knowledge base. The reliability of a fuzzy inference is well predicted by a confidence measure that determines the probability of a correct suggestion by examination of values produced within the inference calculation. The combination of these components provides a means of constructing decision support systems that exhibit a degree of transparency beyond that commonly observed in supervised-learning-based methods. A prototype DSS is analyzed in terms of its workflow and usability, outlining the insight derived through use of the framework. This is demonstrated by considering a simple synthetic data example and a more interesting real-world example application with the goal of characterizing patients with respect to risk of heart disease. Specific input data samples and corresponding output suggestions created by the system are presented and discussed. The means by which the suggestions made by the system may be used in a larger decision context is evaluated.