Monthly Archives: September 2015

You are browsing the site archives by month.

Planning tasks in mobile robots with MDPs that maximize the probability of satisfying user’s requirements specified through temporal logics, with estimation of transition probabilities through simulation only when needed

Jing Wang, Xuchu Ding, Morteza Lahijanian, Ioannis Ch. Paschalidis, and Calin A. Belta, Temporal logic motion control using actor–critic methods, The International Journal of Robotics Research September 2015 34: 1329-1344, first published on May 26, 2015. DOI: 10.1177/0278364915581505.

This paper considers the problem of deploying a robot from a specification given as a temporal logic statement about some properties satisfied by the regions of a large, partitioned environment. We assume that the robot has noisy sensors and actuators and model its motion through the regions of the environment as a Markov decision process (MDP). The robot control problem becomes finding the control policy which maximizes the probability of satisfying the temporal logic task on the MDP. For a large environment, obtaining transition probabilities for each state–action pair, as well as solving the necessary optimization problem for the optimal policy, are computationally intensive. To address these issues, we propose an approximate dynamic programming framework based on a least-squares temporal difference learning method of the actor–critic type. This framework operates on sample paths of the robot and optimizes a randomized control policy with respect to a small set of parameters. The transition probabilities are obtained only when needed. Simulations confirm that convergence of the parameters translates to an approximately optimal policy.

Building probabilistic models of physical processes from their deterministic models and some experimental data, with guarantees on the degree of coincidence between the generated model and the real system

Konstantinos Karydis, Ioannis Poulakakis, Jianxin Sun, and Herbert G. Tanner, Probabilistically valid stochastic extensions of deterministic models for systems with uncertainty, The International Journal of Robotics Research September 2015 34: 1278-1295, first published on May 28, 2015. DOI: 10.1177/0278364915576336.

Models capable of capturing and reproducing the variability observed in experimental trials can be valuable for planning and control in the presence of uncertainty. This paper reports on a new data-driven methodology that extends deterministic models to a stochastic regime and offers probabilistic guarantees of model fidelity. From an acceptable deterministic model, a stochastic one is generated, capable of capturing and reproducing uncertain system–environment interactions at given levels of fidelity. The reported approach combines methodological elements from probabilistic model validation and randomized algorithms, to simultaneously quantify the fidelity of a model and tune the distribution of random parameters in the corresponding stochastic extension, in order to reproduce the variability observed experimentally in the physical process of interest. The approach can be applied to an array of physical processes, the models of which may come in different forms, including differential equations; we demonstrate this point by considering examples from the areas of miniature legged robots and aerial vehicles.

Modelling ECGs with sums of gaussians and estimating them through switching Kalman Filters and the likelihood of each mode

Oster, J.; Behar, J.; Sayadi, O.; Nemati, S.; Johnson, A.E.W.; Clifford, G.D., Semisupervised ECG Ventricular Beat Classification With Novelty Detection Based on Switching Kalman Filters, in Biomedical Engineering, IEEE Transactions on , vol.62, no.9, pp.2125-2134, Sept. 2015, DOI: 10.1109/TBME.2015.2402236.

Automatic processing and accurate diagnosis of pathological electrocardiogram (ECG) signals remains a challenge. As long-term ECG recordings continue to increase in prevalence, driven partly by the ease of remote monitoring technology usage, the need to automate ECG analysis continues to grow. In previous studies, a model-based ECG filtering approach to ECG data from healthy subjects has been applied to facilitate accurate online filtering and analysis of physiological signals. We propose an extension of this approach, which models not only normal and ventricular heartbeats, but also morphologies not previously encountered. A switching Kalman filter approach is introduced to enable the automatic selection of the most likely mode (beat type), while simultaneously filtering the signal using appropriate prior knowledge. Novelty detection is also made possible by incorporating a third mode for the detection of unknown (not previously observed) morphologies, and denoted as X-factor. This new approach is compared to state-of-the-art techniques for the ventricular heartbeat classification in the MIT-BIH arrhythmia and Incart databases. F1 scores of 98.3% and 99.5% were found on each database, respectively, which are superior to other published algorithms’ results reported on the same databases. Only 3% of all the beats were discarded as X-factor, and the majority of these beats contained high levels of noise. The proposed technique demonstrates accurate beat classification in the presence of previously unseen (and unlearned) morphologies and noise, and provides an automated method for morphological analysis of arbitrary (unknown) ECG leads.

Good review of similarity measures between elements with semantics

Mohammad Taher Pilehvar, Roberto Navigli, From senses to texts: An all-in-one graph-based approach for measuring semantic similarity, Artificial Intelligence, Volume 228, November 2015, Pages 95-128, ISSN 0004-3702, DOI: 10.1016/j.artint.2015.07.005.

Quantifying semantic similarity between linguistic items lies at the core of many applications in Natural Language Processing and Artificial Intelligence. It has therefore received a considerable amount of research interest, which in its turn has led to a wide range of approaches for measuring semantic similarity. However, these measures are usually limited to handling specific types of linguistic item, e.g., single word senses or entire sentences. Hence, for a downstream application to handle various types of input, multiple measures of semantic similarity are needed, measures that often use different internal representations or have different output scales. In this article we present a unified graph-based approach for measuring semantic similarity which enables effective comparison of linguistic items at multiple levels, from word senses to full texts. Our method first leverages the structural properties of a semantic network in order to model arbitrary linguistic items through a unified probabilistic representation, and then compares the linguistic items in terms of their representations. We report state-of-the-art performance on multiple datasets pertaining to three different levels: senses, words, and texts.

Extending probabilistic logic programming with continuous r.v.s, and a nice and brief introduction to programming logic and probabilistic inference

Steffen Michels, Arjen Hommersom, Peter J.F. Lucas, Marina Velikova, A new probabilistic constraint logic programming language based on a generalised distribution semantics, Artificial Intelligence, Volume 228, November 2015, Pages 1-44, ISSN 0004-3702, DOI: 10.1016/j.artint.2015.06.008.

Probabilistic logics combine the expressive power of logic with the ability to reason with uncertainty. Several probabilistic logic languages have been proposed in the past, each of them with their own features. We focus on a class of probabilistic logic based on Sato’s distribution semantics, which extends logic programming with probability distributions on binary random variables and guarantees a unique probability distribution. For many applications binary random variables are, however, not sufficient and one requires random variables with arbitrary ranges, e.g. real numbers. We tackle this problem by developing a generalised distribution semantics for a new probabilistic constraint logic programming language. In order to perform exact inference, imprecise probabilities are taken as a starting point, i.e. we deal with sets of probability distributions rather than a single one. It is shown that given any continuous distribution, conditional probabilities of events can be approximated arbitrarily close to the true probability. Furthermore, for this setting an inference algorithm that is a generalisation of weighted model counting is developed, making use of SMT solvers. We show that inference has similar complexity properties as precise probabilistic inference, unlike most imprecise methods for which inference is more complex. We also experimentally confirm that our algorithm is able to exploit local structure, such as determinism, which further reduces the computational complexity.

On quickest change detection when the process is modelled with HMMs

Cheng-Der Fuh; Yajun Mei, Quickest Change Detection and Kullback-Leibler Divergence for Two-State Hidden Markov Models, in Signal Processing, IEEE Transactions on , vol.63, no.18, pp.4866-4878, Sept.15, 2015 DOI: 10.1109/TSP.2015.2447506

In this paper, the quickest change detection problem is studied in two-state hidden Markov models (HMM), where the vector parameter θ of the HMM changes from θ0 to θ1 at some unknown time, and one wants to detect the true change as quickly as possible while controlling the false alarm rate. It turns out that the generalized likelihood ratio (GLR) scheme, while theoretically straightforward, is generally computationally infeasible for the HMM. To develop efficient but computationally simple schemes for the HMM, we first discuss a subtlety in the recursive form of the generalized likelihood ratio (GLR) scheme for the HMM. Then we show that the recursive CUSUM scheme proposed in Fuh (Ann. Statist., 2003) can be regarded as a quasi-GLR scheme for pseudo post-change hypotheses with certain dependence structure between pre- and postchange observations. Next, we extend the quasi-GLR idea to propose recursive score schemes in the scenario when the postchange parameter θ1 of the HMM involves a real-valued nuisance parameter. Finally, the Kullback-Leibler (KL) divergence plays an essential role in the quickest change detection problem and many other fields, however it is rather challenging to numerically compute it in HMMs. Here we develop a non-Monte Carlo method that computes the KL divergence of two-state HMMs via the underlying invariant probability measure, which is characterized by the Fredholm integral equation. Numerical study demonstrates an unusual property of the KL divergence for HMM that implies the severe effects of misspecifying the postchange parameter for the HMM.

Nice related work on efficient POMDPs and two novel approaches to reduce their computational cost

Grady, D.K.; Moll, M.; Kavraki, L.E., Extending the Applicability of POMDP Solutions to Robotic Tasks, in Robotics, IEEE Transactions on , vol.31, no.4, pp.948-961, Aug. 2015 DOI: 10.1109/TRO.2015.2441511

Partially observable Markov decision processes (POMDPs) are used in many robotic task classes from soccer to household chores. Determining an approximately optimal action policy for POMDPs is PSPACE-complete, and the exponential growth of computation time prohibits solving large tasks. This paper describes two techniques to extend the range of robotic tasks that can be solved using a POMDP. Our first technique reduces the motion constraints of a robot and, then, uses state-of-the-art robotic motion planning techniques to respect the true motion constraints at runtime. We then propose a novel task decomposition that can be applied to some indoor robotic tasks. This decomposition transforms a long time horizon task into a set of shorter tasks. We empirically demonstrate the performance gain provided by these two techniques through simulated execution in a variety of environments. Comparing a direct formulation of a POMDP to solving our proposed reductions, we conclude that the techniques proposed in this paper can provide significant enhancement to current POMDP solution techniques, extending the POMDP instances that can be solved to include large continuous-state robotic tasks.

What students value the most in an engineering lab (and some related work on laboratory practices)

Nikolic, S.; Ritz, C.; Vial, P.J.; Ros, M.; Stirling, D., Decoding Student Satisfaction: How to Manage and Improve the Laboratory Experience, in Education, IEEE Transactions on , vol.58, no.3, pp.151-158, Aug. 2015, DOI: 10.1109/TE.2014.2346474

The laboratory plays an important role in teaching engineering skills. An Electrical Engineering department at an Australian University implemented a reform to monitor and improve student satisfaction with the teaching laboratories. A Laboratory Manager was employed to oversee the quality of 27 courses containing instructional laboratories. Student satisfaction surveys were carried out on all relevant laboratories every year, and the data were used for continuous improvement. This paper will investigate the reforms that were implemented and outline a number of the improvements made. It also examines the program’s overall impact on: (1) overall satisfaction; (2) laboratory notes; (3) learning experiences; (4) computer facilities; (5) engineering equipment; and (6) condition of the laboratory. Student satisfaction with the laboratories increased by 32% between 2007 and 2013. The results show that the laboratory notes (activity and clarity) and the quality of the equipment used are among the most influential factors on student satisfaction. In particular, it is important to have notes or resources that explain in some detail how to use and troubleshoot equipment and software used in the laboratory.