This work focuses on the autonomous exploration of unknown areas by a swarm of mobile robots, referred to as agents. When an emergency happens within a building, it is dangerous to send human responders to search the area for hazards and victims. This motivates the need for autonomous agents that are able to coordinate with each other to explore the area as fast as possible. We investigate this problem from an algorithmic, rather than a robotics point of view, and thus abstract away from practical problems, such as obstacle detection and navigation over rough terrain. Our focus is on distributed algorithms that can cope with the following challenges: the topology of the area is typically unknown, communication between agents is intermittent and unreliable, and agents are not aware of their location in indoor environments. In order to address these challenges, we adopt the stigmergy approach, that is, we assume that the area is instrumented with small inexpensive sensors (called tags) and agents coordinate indirectly with each other by reading and updating the state of local tags. We propose three novel distributed algorithms that allow agents to explore unknown areas by coordinating indirectly through a tag-instrumented environment. In addition, we propose two mechanisms for discovering evacuation routes from critical points in the area to emergency exits. Agents are able to combine the tasks of area exploration and evacuation route discovery in a seamless manner. We study the proposed algorithms analytically, and evaluate them empirically in a custom-built simulation environment in a variety of scenarios. We then build a real testbed of agents and tags, and investigate practical mechanisms that allow agents to detect and localise nearby tags, and navigate toward them. Using the real testbed, we derive realistic models of detection, localisation and navigation errors, and investigate how they impact the performance of the proposed exploration algorithms. Finally, we design fault-tolerant exploration algorithms that are robust to these errors and evaluate them extensively in a simulation environment.

High Intensity Focused Ultrasound (HIFU) is a new cancer thermal therapy method which has achieved encouraging results in clinics recently. However, the lack of a temperature monitoring makes it hard to apply widely, safely and efficiently. Conventional ultrasonic temperature estimation based on echo strain suffers from artifacts caused by signal distortion over time, leading to poor estimation and visualization of the 2D temperature map. This thesis presents a novel model-based stochastic framework for ultrasonic temperature estimation, which combines the temperature information from the ultrasound images and a theoretical model of the heat diffusion. Consequently the temperature estimation is more consistent over time and its visualisation is improved. There are 3 main contributions of this thesis related to: improving the conventional echo strain method to estimate temperature, developing and applying approximate heat models to model temperature, and finally combining the estimation and the models. First in the echo strain based temperature estimation, a robust displacement estimator is first introduced to remove displacement outliers caused by the signal distortion over time due to the thermo-acoustic lens effect. To transfer the echo strain to temperature more accurately, an experimental method is designed to model their relationship using polynomials. Experimental results on a gelatine phantom show that the accuracy of the temperature estimation is of the order of 0.1 ◦C. This is better than results reported previously of 0.5 ◦C in a rubber phantom. Second in the temperature modelling, heat models are derived approximately as Gaussian functions which are mathematically simple. Simulated results demonstrate that the approximate heat models are reasonable. The simulated temperature result is analytical and hence computed in much less than 1 second, while the conventional simulation of using finite element methods requires about 25 minutes under the same conditions. Finally, combining the estimation and the heat models is the main contribution of this thesis. A 2D spatial adaptive Kalman filter with the predictive step defined by the shape model from the heat models is applied to the temperature map estimated from ultrasound images. It is shown that use of the temperature shape model enables more reliable temperature estimation in the presence of distorted or blurred strain measurements which are typically found in practice. The experimental results on in-vitro bovine liver show that the visualisation on the temperature map over time is more consistent and the iso-temperature contours are clearly visualised.

The past decade has seen great progress in research on large scale mapping and perception in static environments. Real world perception requires handling uncertain situations with multiple possible interpretations: e.g. changing appearances, dynamic objects, and varying motion models. These aspects of perception have been largely avoided through the use of heuristics and preprocessing. This thesis is motivated by the challenge of including discrete reasoning directly into the estimation process. We approach the problem by using Conditional Linear Gaussian Networks (CLGNs) as a generalization of least-squares estimation which allows the inclusion of discrete model selection variables. CLGNs are a powerful framework for modeling sparse multi-modal inference problems, but are difficult to solve efficiently. We propose the Iterative Local Model Selection (ILMS) algorithm as a general approximation strategy specifically geared towards the large scale problems encountered in tracking and mapping. Chapter 4 introduces the ILMS algorithm and compares its performance to traditional approximate inference techniques for Switching Linear Dynamical Systems (SLDSs). These evaluations validate the characteristics of the algorithm which make it particularly attractive for applications in robot perception. Chief among these is reliability of convergence, consistent performance, and a reasonable trade off between accuracy and efficiency. In Chapter 5, we show how the data association problem in multi-target tracking can be formulated as an SLDS and effectively solved using ILMS. The SLDS formulation allows the addition of additional discrete variables which model outliers and clutter in the scene. Evaluations on standard pedestrian tracking sequences demonstrates performance competitive with the state of the art. Chapter 6 applies the ILMS algorithm to robust pose graph estimation. A non-linear CLGN is constructed by introducing outlier indicator variables for all loop closures. The standard Gauss-Newton optimization algorithm is modified to use ILMS as an inference algorithm in between linearizations. Experiments demonstrate a large improvement over state-of-the-art robust techniques. The ILMS strategy presented in this thesis is simple and general, but still works surprisingly well. We argue that these properties are encouraging for wider applicability to problems in robot perception.