Robotic motion planning aspires to match the ease and efficiency with which humans move through and interact with their environment. Yet state of the art robotic planners fall short of human abilities; they are slower in computation, and the results are often of lower quality. One stumbling block in traditional motion planning is that points and paths are often considered in isolation. Many planners fail to recognize that substantial shared information exists among path alternatives. Exploitation of the geometric and topological relationships among path alternatives can therefore lead to increased efficiency and competency. These benefits include: better-informed path sampling, dramatically faster collision checking, and a deeper understanding of the trade-offs in path selection. In path sampling, the principle of locality is introduced as a basis for constructing an adaptive, probabilistic, geometric model to influence the selection of paths for collision test. Recognizing that collision testing consumes a sizable majority of planning time and that only collision-free paths provide value in selecting a path to execute on the robot, this model provides a significant increase in efficiency by circumventing collision testing paths that can be predicted to collide with obstacles. In the area of collision testing, an equivalence relation termed local path equivalence, is employed to discover when the work of testing a path has been previously performed. The swept volumes of adjoining path alternatives frequently overlap, implying that a continuum of intermediate paths exists as well. By recognizing such neighboring paths with related shapes and outcomes, up to 90% of paths may be tested implicitly in experiments, bypassing the traditional, expensive collision test and delivering a net 300% boost in collision test performance. Local path equivalence may also be applied to the path selection problem in order to recognize higher-level navigation options and make smarter choices. This thesis presents theoretical and experimental results in each of these three areas, as well as inspiration on the connections to how humans reason about moving through spaces.

This thesis presents a rough set approach to reinforcement learning. This is made possible by considering behaviour patterns of learning agents in the context of approximation spaces. Rough set theory introduced by Zdzisław Pawlak in the early 1980s provides a ground for deriving pattern-based rewards within approximation spaces. Learning can be considered episodic. The framework provided by an approximation space makes it possible to derive pattern-based reference rewards at the end of each episode. Reference rewards provide a standard for reinforcement comparison as well as the actor-critic method of reinforcement learning. In addition, approximation spaces provide a basis for deriving episodic weights that provide a basis for a new form of off-policy Monte Carlo learning control method. A number of conventional and pattern-based reinforcement learning methods are investigated in this thesis. In addition, this thesis introduces two learning environments used to compare the algorithms. The first is a Monocular Vision System used to track a moving target. The second is an artificial ecosystem testbed that makes it possible to study swarm behaviour by collections of biologically-inspired bots. The simulated ecosystem has an ethological basis inspired by the work of Niko Tinbergen, who introduced in the 1960s methods of observing and explaining the behaviour of biological organisms that carry over into the study of the behaviour of interacting robotic devices that cooperate to survive and to carry out highly specialized tasks. Agent behaviour during each episode is recorded in a decision table called an ethogram, which records features such as states, proximate causes, responses (actions), action preferences, rewards and decisions (actions chosen and actions rejected). At all times an agent follows a policy that maps perceived states of the environment to actions. The goal of the learning algorithms is to find an optimal policy in a non-stationary environment. The results of the learning experiments with seven forms of reinforcement learning are given. The contribution of this thesis is a comprehensive introduction to a pattern-based evaluation of behaviour during reinforcement learning using approximation spaces.

The problem considered in this thesis is the development of an autonomous prototype robot capable of gathering sensory information from its environment allowing it to provide feedback on the condition of specific targets to aid in maintenance of hydro equipment. The context for the solution to this problem is based on the power grid environment operated by the local hydro utility. The intent is to monitor power line structures by travelling along skywire located at the top of towers, providing a view of everything beneath it including, for example, insulators, conductors, and towers. The contribution of this thesis is a novel robot design with the potential to prevent hazardous situations and the use of rough coverage feedback modified reinforcement learning algorithms to establish behaviours.

This dissertation describes the design and implementation of a system that has been designed to extract 3D information from pairs of 2D images. System input consists of two images taken by an ordinary digital camera. System output is a full 3D model extracted from 2D images. There are no assumptions about the positions of the cameras during the time when the images are being taken, but the scene must not undergo any modifications. The process of extracting 3D information from 2D images consists of three basic steps. First, point matching is performed. The main contribution of this step is the introduction of an approach to matching image segments in the context of an approximation space. The second step copes with the problem of estimating external camera parameters. The proposed solution to this problem uses 3D geometry rather than the fundamental matrix widely used in 2D to 3D conversion. In the proposed approach (DirectGS), the distances between reprojected rays for all image points are minimised. The contribution of the approach considered in this step is a definition of an optimal search space for solving the 2D to 3D conversion problem and introduction of an efficient algorithm that minimises reprojection error. In the third step, the problem of dense matching is considered. The contribution of this step is the introduction of a proposed approach to dense matching of 3D object structures that utilises the presence of points on lines in 3D space. The theory and experiments developed for this dissertation demonstrate the usefulness of the proposed system in the process of digitizing 3D information. The main advantage of the proposed approach is its low cost, simplicity in use for an untrained user and the high precision of reconstructed objects.

A novel method of vibration modelling is proposed in this thesis. This method involves estimating the mode shapes of a general structure and describing these shapes in terms of fuzzy membership functions. These estimations or initial guesses are based on engineer's experience or physical insight into natural mode shapes assisted by end and boundary conditions and some rules. The guessed mode shapes were referred to as Mode Shape Forms (MSFs). MSFs are approximate mode shapes, therefore there are uncertainties involve with their values where this uncertainty is expressed by fuzzy sets. The deflection or displacement magnitude of the mode shape forms are described with Zero, Medium, and Large fuzzy linguistic terms and constructed using fuzzy membership functions and rules. Fuzzy rules are introduced for each MSF. In that respect fuzzy membership functions provides a means of dealing with uncertainty in measured data, it gives access to a large repertoire of tools available in fuzzy reasoning field. The second stage of the process addresses the issues of updating these curves by experimental data. This involves performing experimental modal analysis. The mode shapes derived from experimental FRFs collect a limited number of sampling points. When the fuzzy data is updated by experimental data, the method proposes that the points of the fuzzy data correspond to the sampling points of FRF are to be replaced by the experimental data. Doing this creates a new fuzzy curve which is the same as the previous one, except at those points. In another word a 'spiked' version of the original fuzzy curve is obtained. In the last stage of this process, neural network is used to 'learn' the spiked curve. By controlling the learning process (by preventing it from overtraining), an updated fuzzy curve is generated that is the final version of the mode shape. Examples are presented to demonstrate the application of the proposed method in modelling of beams, a plate and a structure (a three beams frame). The method is extended to evaluate the error where a wrong MSF is assumed for the mode shape. In this case the method finds the correct MSF among available guessed MSFs. A further extension of the method is proposed for cases where there is no guess available for the mode shape. In this situation the 'closest' MSF is selected among available MSFs. This MSF is modified by correcting the fuzzy rules that is used in constructing of the fuzzy MSF. Using engineering experience, heuristic knowledge and the developed MSF rules in this method are the capabilities that cannot be provided with any artificial intelligent system. This provides additional advantage relative to vibration modelling approaches that have been developed until now. Therefore this method includes all aspects of an effective analysis such as mixed artificial intelligence and experimental validation, plus human interface/intelligence. Another advantage is, MSF rules provide a novel approach in vibration modelling where enables the method to start and operate with unknown input parameters such as unknown material properties and imprecise structure dimensions. Hence the classical computational procedures of obtaining the vibration behaviour of the system, from these inputs, are not used in this approach. As a result, this method avoids the time consuming computational procedure that exhibit in existing vibration modelling methods. However, the validation procedure, using experimental tests (modal testing) is the same acceptable procedure that is used in any other available methods which proves the accuracy of the method.

This thesis presents a rough set approach to reinforcement learning. This is made possible by considering behaviour patterns of learning agents in the context of approximation spaces. Rough set theory introduced by Zdzisław Pawlak in the early 1980s provides a ground for deriving pattern-based rewards within approximation spaces. Learning can be considered episodic. The framework provided by an approximation space makes it possible to derive pattern-based reference rewards at the end of each episode. Reference rewards provide a standard for reinforcement comparison as well as the actor-critic method of reinforcement learning. In addition, approximation spaces provide a basis for deriving episodic weights that provide a basis for a new form of off-policy Monte Carlo learning control method. A number of conventional and pattern-based reinforcement learning methods are investigated in this thesis. In addition, this thesis introduces two learning environments used to compare the algorithms. The first is a Monocular Vision System used to track a moving target. The second is an artificial ecosystem testbed that makes it possible to study swarm behaviour by collections of biologically-inspired bots. The simulated ecosystem has an ethological basis inspired by the work of Niko Tinbergen, who introduced in the 1960s methods of observing and explaining the behaviour of biological organisms that carry over into the study of the behaviour of interacting robotic devices that cooperate to survive and to carry out highly specialized tasks. Agent behaviour during each episode is recorded in a decision table called an ethogram, which records features such as states, proximate causes, responses (actions), action preferences, rewards and decisions (actions chosen and actions rejected). At all times an agent follows a policy that maps perceived states of the environment to actions. The goal of the learning algorithms is to find an optimal policy in a non-stationary environment. The results of the learning experiments with seven forms of reinforcement learning are given. The contribution of this thesis is a comprehensive introduction to a pattern-based evaluation of behaviour during reinforcement learning using approximation spaces.

This thesis contains several results concerning the combinatorics of partially ordered sets (posets) which are either of enumerative or extremal nature. <br><br> The first concerns conjectures of Friedland and Kahn, which state that the (extremal) d-regular graph on N vertices containing both the maximal number of matchings and independent sets of a fixed size is the graph consisting of disjoint union of appropriate number of complete bipartite d-regular graphs on 2d vertices. We show that the conjectures are true in an asymptotic sense, using entropy techniques. <br><br> As a second result, we give tight bounds on the size of the largest Boolean family which contains no three distinct subsets forming an "induced V" (i.e. if A,B,C are all in our family, if C is contained in the intersection of A B, A must be a subset of B). This result, though similar to known results, gives the first bound on a family defined by an induced property. <br><br> We pose both Dedekind-type questions concerning the number of antichains and a Stanley-type question concerning the number of linear extensions in generalized Boolean lattices; namely, products of chain posets and the poset of partially defined functions. We provide asymptotically tight bounds for these problems. <br><br> A Boolean function, f, is called cherry-free if for all triples x,y,z where z covers both x and y, f(z)=1 whenever both f(x)=1 and f(y)=1. We give bounds on the number of cherry-free functions on bipartite regular posets, with stronger results for bipartite posets under an additional co-degree hypotheses. We discuss applications of these functions to Boolean Horn functions and similar structures in ranked regular posets.

An analogue of the Riemannian structure of a manifold is created for an ultrametric Cantor set using the techniques of Noncommutative Geometry. In particular, a spectral triple is created that can recover much of the fractal geometry of the original Cantor set. It is shown that this spectral triple can recover the metric, the upper box dimension, and in certain cases the Hausdorff measure. The analogy with Riemannian geometry is then taken further and an analogue of the Laplace-Beltrami operator is created for an ultrametric Cantor set. The Laplacian then allows to create an analogue of Brownian motion generated by this Laplacian. All these tools are then applied to the triadic Cantor set. Other examples of ultrametric Cantor sets are then presented: attractors of self-similar iterated function systems, attractors of cookie cutter systems, and the transversal of an aperiodic, repetitive Delone set of finite type. In particular, the example of the transversal of the Fibonacci tiling is studied.

The objective of this dissertation is to study commonly occurring location and clustering problems on graphs. The dissertation is presented as a collection of results in topics including finding maximum cliques in large graphs, graph clustering in large scale graphs, determining location of facilities for pre-positioning emergency relief supplies, and selecting nodes to form a virtual backbone in a wireless sensor network. To begin with, a new clique relaxation called a k-community is defined as a connected subgraph such that endpoints of every edge have at least k common neighbors within the subgraph. It is used to develop scale reduction techniques to obtain the maximum clique on very large scale real life networks. Analytically, the technique is been shown to be very effective on power-law random graphs. Experimental results on real life graph instances (Collaboration networks, P2P networks, Social networks, etc.) show our procedure to be much more effective than a regular k-core peeling approach. Next, a general purpose network clustering algorithm based on the clique relaxation concept of k-community is presented. A salient feature of this approach is that it does not use any prior information about the structure of the network. By defining a cluster as a k-community, the proposed algorithm aims to provide a clustering of a network into k-communities with varying values of k. Even though the algorithm is not designed to optimize any particular performance measure, the computational results suggest that it performs well on a number of criteria that are used in literature to evaluate the quality of a clustering. The third topic deals with choosing the locations of disaster response facilities for the storage of emergency supplies, which is critical to the quality of service provided in a large scale emergency like an earthquake. In the existing literature, large scale emergency facility location models have either assumed that disaster response facilities will always be functioning and available when required, or that the functioning of a facility is independent of a particular disaster scenario. In this paper new location models are presented that explicitly take into consideration the stochastic nature of the impact a disaster can have on the disaster response facilities and the population centers in surrounding areas. A comparison of the results obtained using our models with those from models available in literature using a case study suggests that the locations suggested by the model in this paper significantly reduce the expected cost of transportation of supplies when we consider the damage a disaster causes to the disaster response facilities and areas near it. Lastly, a distributed approximate algorithm for forming the communication backbone in wireless sensor networks is presented. Some of the most popular routing protocols for wireless sensor networks require a virtual backbone for efficient communication be- tween the sensors. Connected Dominating Sets (CDS) have been studied as a method of choosing nodes to be in the backbone. The traditional approach is to assume that the transmission range of each node is given and then minimize the number of nodes in the CDS representing the backbone. A recently introduced alternative strategy is based on the concept of k-bottleneck connected dominating set (k-BCDS), which, given a positive integer k, minimizes the transmission range of the nodes that ensures a CDS of size k exists in the network. This paper provides a 6-approximate distributed algorithm for the k-BCDS problem. The results of empirical evaluation of the proposed algorithm are also included.

The body motion of patients, during magnetic resonance (MR) imaging causes significant artifacts in the reconstructed image. Artifacts are manifested as a motion induced blur and ghost repetitions of the moving structures. which obscure vital anatomical and pathological detail. The techniques that have been proposed for suppressing motion artifacts fall into two major categories. Real-time techniques attempt to prevent the motion from corrupting the data by restricting the data acquisition times or motion of the patients, whereas the post-processing techniques use the information embedded in the corrupted data to restore the image. Most methods currently in widespread use belong to the real-time techniques, however with the advent of fast computing platforms and sophisticated signal processing algorithms, the emergence of post-processing techniques is clearly evident. The post-processing techniques usually demand an appropriate model of the motion. The restoration of the image requires that the motion parameters be determined in order to invert the data degradation process. Methods for the correction of translational motion have been studied extensively in the past. The subject of this thesis encompasses the rotational motion model and the effect of rotational motion on the collected MR data in the spatial frequency space (k-space), which is in general, more complicated than the translational model. Rotational motion artifacts are notably prevalent in MR images of head, brain and limbs. Post-processing techniques for the correction of rotational motion artifacts often involve interpolation and re-gridding of the acquired data in the k-space. These methods create significant data overlap and void regions. Therefore, in the past, proposed corrective techniques have been limited to suppression of artifacts caused by small angle rotations. This thesis presents a method of managing overlap regions, using weighted averaging of redundant data, in order to correct for large angle rotations. An iterative estimation technique for filling the data void regions has also been developed by the use of iterated application of projection operators onto constraint sets. These constraint sets are derived from the k-space data generated by the MR imager, and available a priori knowledge. It is shown that the iterative algorithm diverges at times from the required image, due to inconsistency among the constraint sets. It is also shown that this can be overcome by using soft. constraint sets and fuzzy projections. One of the constraints applied in the iterative algorithm is the finite support of the imaged object, marked by the outer boundary of the region of interest (ROI). However, object boundary extraction directly from the motion affected MR image can be difficult, specially if the motion function of the object is unknown. This thesis presents a new ROI extraction scheme based on entropy minimization in the image background. The object rotation function is usually unknown or unable to be measured with sufficient accuracy. The motion estimation algorithm proposed in this thesis is based on maximizing the similarity among the k-space data subjected to angular overlap. This method is different to the typically applied parameter estimation technique based on minimization of pixel energy outside the ROI, and has higher efficiency and ability to estimate rotational motion parameters in the midst of concurrent translational motion. The algorithms for ROI extraction, rotation estimation and data correction have been tested with both phantom images and spin echo MR images producing encouraging results.