Behaviour recognition aims to infer the particular behaviours of the inhabitant in a smart home from a series of sensor readings from around the house. There are many reasons to recognise human behaviours; one being to monitor the elderly or cognitively impaired and detect potentially dangerous behaviours. We view the behaviour recognition problem as the task of mapping the sensory outputs to a sequence of recognised activities. This research focuses on the development of machine learning methods to find an approximation to the mapping between sensor outputs and behaviours. However, learning the mapping raises an important issue, which is that the training data is not necessarily annotated with exemplar behaviours of the inhabitant. This doctoral study takes several steps towards addressing the problem of finding an approximation to this mapping, beginning with separate investigations on current methods proposed in the literature, identifying useful sensory outputs for behaviour recognition, and concluding by proposing two directions: one using supervised learning on annotated sensory stream and one using unsupervised learning on unannotated ones.

Multi-task learning remains a difficult yet important problem in machine learning. In Gaussian processes the main challenge is the definition of valid kernels (covariance functions) able to capture the relationships between different tasks. This paper presents a novel methodology to construct valid multi-task covariance functions (Mercer kernels) for Gaussian processes allowing for a combination of kernels with different forms. The method is based on Fourier analysis and is general for arbitrary stationary covariance functions. Analytical solutions for cross covariance terms between popular forms are provided including Mat´ern, squared exponential and sparse covariance functions. Experiments are conducted with both artificial and real datasets demonstrating the benefits of the approach.

This paper focuses on computing first-order theories under either stable model semantics or circumscription. A reduction from first-order theories to logic programs under stable model semantics over finite structures is proposed, and an embedding of circumscription into stable model semantics is also given. Having such reduction and embedding, reasoning problems represented by first-order theories under these two semantics can then be handled by using existing answer set solvers. The effectiveness of this approach in computing hard problems beyond NP is demonstrated by some experiments.

We propose a framework that adds learning for improving plan selection in the popular BDI agent programming paradigm. In contrast with previous proposals, the approach given here is able to scale up well with the complexity of the agent's plan library. Technically, we develop a novel confidence measure which allows the agent to adjust its reliance on the learning dynamically, facilitating in principle infinitely many (re)learning phases. We demonstrate the benefits of the approach in an example controller for energy management.

In a pursuit-evasion game, one or more pursuers aim to discover the existence of, and then capture, an evader. The paper studies pursuit-evasion games in which players may have incomplete information concerning the game state. A methodology is presented for the application of a model checker for the logic of knowledge and time to verify epistemic properties in such games. Experimental results are provided from a number of case studies that validate the feasibility of the approach.

Multi-agent path planning is a challenging problem with numerous real-life applications, including robotics, logistics, military operations planning, disaster rescue, and computer games. We look at navigating large numbers of mobile units to their targets on navigation graphs such as grid maps. The size of problems examined is significantly larger than can be handled using optimal multi-agent pathfinding algorithms in practice. We introduced MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. MAPP and its extended versions are complete on well specified and tractably testable classes of problems. They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Experiments on realistic game grid maps, with uniformly randomly generated start and target locations for each unit, show MAPP as a state-of-the-art multi-agent pathfinding algorithm in terms of scalability and success ratio (i.e., percentage of solved units). Even on challenging scenarios with 2000 units, MAPP solves 92% to 99.7% of units. FAR and WHCA*, two fast but incomplete algorithms that were previously state-of-the-art in terms of scalability, solve as few as 17.5% and 12.3% of these problems. The quality of MAPP's solutions is empirically analyzed using multiple quality criteria: total travel distance, makespan, and sum of actions (including move and wait actions). MAPP is competitive in terms of solution quality and speed with FAR and WHCA*. MAPP further provides the formal characterizations that FAR and WHCA* lack, on problems it can solve as well as low-polynomial upper bounds on the resources required. As optimal algorithms have limited scalability, we evaluated the solution quality of suboptimal algorithms using lower bounds of optimal values. We showed that MAPP's solutions have a reasonable quality. For example, MAPP's total travel distance is on average 19% longer than a lower bound on the optimal value.

Thanks to the idea of social collaboration, Wikipedia has accumulated vast amount of semi-structured knowledge in which the link structure reflects human's cognition on semantic relationship to some extent. In this paper, we proposed a novel method RCRank to jointly compute concept-concept relatedness and concept-category relatedness base on the assumption that information carried in concept-concept links and concept-category links can mutually reinforce each other. Different from previous work, RCRank can not only find semantically related concepts but also interpret their relations by categories. Experimental results on concept recommendation and relation interpretation show that our method substantially outperforms classical methods.

Slinko and White, (2008) have recently introduced a new model of coalitional manipulation of voting rules under limited communication, which they call safe strategic voting. The computational aspects of this model were first studied by Hazon and Elkind, (2010), who provide polynomial-time algorithms for finding a safe strategic vote under k-approval and the Bucklin rule. In this paper, we answer an open question of Hazon and Elkind, (2010) by presenting a polynomial-time algorithm for finding a safe strategic vote under the Borda rule. Our results for Borda generalize to several interesting classes of scoring rules.

Scaling up the number of simultaneously moving units in pathfinding problems to hundreds, or even thousands, is well beyond the capability of theoretically optimal algorithms in practice, which is consistent with existing intractability results. Significant scalability can be achieved by trading off solution optimality, which motivates evaluating the quality of suboptimal solutions, especially in instances much larger than can be handled by optimal algorithms. We consider pathfinding in uniform cost grid maps, and we study the solution quality using the three most common quality criteria, total travel distance , sum of actions , and makespan . We focus on MAPP, which has been shown as state-of-the-art in terms of scalability and success ratio (i.e., percentage of solved units) on realistic game grid maps. Until now, the quality of MAPP's solutions had not been as extensively analyzed. We introduced enhancements that significantly improve MAPP's solution quality. For example, its sum of actions is cut to half on average. MAPP becomes competitive in terms of solution quality with FAR and WHCA*, two successful algorithms from the literature. To evaluate the quality of suboptimal solutions in instances beyond the capability of optimal algorithms, we use lower bounds of optimal values to show our solutions have a reasonable quality. For example, MAPP's average total travel distance is 19 percent longer than the lower bound.

When a system behaves abnormally, sequential diagnosis takes a sequence of measurements of the system until the faults causing the abnormality are identified, and the goal is to reduce the diagnostic cost, defined here as the number of measurements. To propose measurement points, previous work employs a heuristic based on reducing the entropy over a computed set of diagnoses. This approach generally has good performance in terms of diagnostic cost, but can fail to diagnose large systems when the set of diagnoses is too large. Focusing on a smaller set of probable diagnoses scales the approach but generally leads to increased average diagnostic costs. In this paper, we propose a new diagnostic framework employing four new techniques, which scales to much larger systems with good performance in terms of diagnostic cost. First, we propose a new heuristic for measurement point selection that can be computed efficiently, without requiring the set of diagnoses, once the system is modeled as a Bayesian network and compiled into a logical form known as d-DNNF. Second, we extend hierarchical diagnosis, a technique based on system abstraction from our previous work, to handle probabilities so that it can be applied to sequential diagnosis to allow larger systems to be diagnosed. Third, for the largest systems where even hierarchical diagnosis fails, we propose a novel method that converts the system into one that has a smaller abstraction and whose diagnoses form a superset of those of the original system; the new system can then be diagnosed and the result mapped back to the original system. Finally, we propose a novel cost estimation function which can be used to choose an abstraction of the system that is more likely to provide optimal average cost. Experiments with ISCAS-85 benchmark circuits indicate that our approach scales to all circuits in the suite except one that has a flat structure not susceptible to useful abstraction.