Many variations of algorithms for finding the shortest path in a large graph have been introduced recently due to the needs of applications like the Geographic Information System (GIS) or Intelligent Transportation System (ITS). The primary subjects of those algorithms are materialization and hierarchical path views. Some studies focus on the materialization and sacrifice the pre-computational costs and storage costs for faster computation of a query. Other studies focus on the shortest-path algorithm, which has less pre-computation and storage but takes more time to compute the shortest path. The main objective of this thesis is to accelerate the computation time for the shortest-path queries while keeping the degree of materialization as low as possible. This thesis explores two different categories: 1) the reduction of the I/O-costs for multiple queries, and 2) the reduction of search spaces in a graph. The thesis proposes two simple algorithms to reduce the I/O-costs, especially for multiple queries. To tackle the problem of reducing search spaces, we give two different levels of materializations, namely, the <i>boundary set distance matrix</i> and <i>x-Hop sketch graph</i>, both of which materialize the shortest-path view of the boundary nodes in a partitioned graph. Our experiments show that a combination of the suggested solutions for 1) and 2) performs better than the original Disk-based SP algorithm [7], on which our work is based, and requires much less storage than <i>HEPV</i> [3].

This thesis contributes to the field of academic game studies by reworking and updating the established theories of Espen Aarseth, Janet Murray and Marie-Laure Ryan in understanding the path in videogames. It also draws upon the more recent theoretical discussions of figures such as Jesper Juul, Lev Manovich, Frans Mäyrä and James Newman in order to explore the player’s experience along these paths in the gameworld. By defining a vocabulary of routes through space, the thesis uses the maze in particular as a way of understanding the paths of videogames. The research starts by examining our cultural understanding of the maze within videogames. Various mazes around the UK were walked in order to understand their design and how this may translate into the virtual world of the videogame. The thesis examines the uses of real world mazes through the work of Penelope Doob, and Herman Kern to discuss how the videogame may rework our cultural understanding of the maze due to its increasingly ubiquitous nature. This enables a discussion of maze-paths found within many videogames that are not necessarily categorised by what is often discussed as the maze genre of games. A morphology of maze-paths is devised through comparing the mazes of the real world and the virtual mazes of the videogame. This is achieved by breaking down the maze into separate path types and shows how these paths may link to one another. The thesis argues that the paths of the videogame are generated by the player’s actions. Therefore the focus of this thesis is on the player’s experience along these paths and the objects found at points on them. In acknowledging how to overcome obstacles along the path it is also possible to understand the role of the path in the player’s learning and mastery of the gameworld. This leads to discussions of different types of play experienced by the player in the videogame. Play is separated into what I term purposeful play, being the activities intended by the designer, and appropriated play which is the play formed out of the player’s exploration of the game system. These two terms help to understand player’s incentives for playing along the ruled paths of the gameworld as well as exploring the game’s system further to find new types of play outside of the pre-determined rules. As this thesis is concerned with videogames involving the player’s avatar having a direct relationship with the path, the research also investigates what happens when certain devices break these paths. It was discovered that warp devices reconstruct both temporal and narrative elements within the gamespace, and cause the player’s avatar to temporarily move on tracks through the gameworld. In defining a vocabulary of movement through space on a fixed track, as opposed to a player-determined path, there is a further understanding of the player experience related to each type of route taken in the game. Through an understanding of the maze and defining a vocabulary of maze-paths, tracks and objects found along them, this thesis adds a new contribution to knowledge. It also acknowledges the importance of different types of play within videogames and how these can shape the player experience along the paths of the game.

No description available.

We propose a novel framework for motion planning and control that is based on a manifold encoding of the desired solution set. We present an alternate, model-free, approach to path planning, replanning and control. Our approach is founded on the idea of encoding the set of possible trajectories as a skill manifold, which can be learnt from data such as from demonstration. We describe the manifold representation of skills, a technique for learning from data and a method for generating trajectories as geodesics on such manifolds. We extend the trajectory generation method to handle dynamic obstacles and constraints. We show how a state metric naturally arises from the manifold encoding and how this can be used for reactive control in an on-line manner. Our framework tightly integrates learning, planning and control in a computationally efficient representation, suitable for realistic humanoid robotic tasks that are defined by skill specifications involving high-dimensional nonlinear dynamics, kinodynamic constraints and non-trivial cost functions, in an optimal control setting. Although, in principle, such problems can be handled by well understood analytical methods, it is often difficult and expensive to formulate models that enable the analytical approach. We test our framework with various types of robotic systems – ranging from a 3-link arm to a small humanoid robot – and show that the manifold encoding gives significant improvements in performance without loss of accuracy. Furthermore, we evaluate the framework against a state-of-the-art imitation learning method. We show that our approach, by learning manifolds of robotic skills, allows for efficient planning and replanning in changing environments, and for robust and online reactive control.

Utilising a historical perspective and drawing upon path dependence theory, the thesis focuses on the question of a political union of Canada’s three Maritime provinces - Nova Scotia, New Brunswick and Prince Edward Island - between 1960 and 1980. Drawing on archival sources and interviews the thesis examines the factors which increased the potential for a union and resulted in a political union not occurring in this period. The thesis reveals how the intensification of Quebec separatism throughout the 1960s and 1970s threatened to separate the region geographically from the rest of the country. It also shows that the regional expansionist agenda of the federal government undermined provincial jurisdiction as it sought to eliminate economic underdevelopment in the Maritime region. These factors coupled with the dynamics of province-building and the political ambition of key political leaders in the Maritimes created the impetus for a political union in the 1960s. The thesis pays particular attention to the Maritime Union Study (MUS), established in 1968 by the Maritime premiers to investigate the union question. The thesis argues that the MUS was a critical juncture because it presented the premiers with a number of alternative choices for political change, including its main recommendation: the establishment of a political union. However, the thesis reveals that upon the publication of the final report of the MUS in November 1970, the ramifications of the 1970 October Crisis in Quebec and the recent election of new premiers in Nova Scotia and New Brunswick reconfigured the national and regional contexts in which a political union was considered. This reconfiguration led to a new form of institutionalised intergovernmental relations called the Council of Maritime Premiers (CMP). The CMP was a confederal structure which respected the provincially-focused decision-making capacity of the Maritime premiers. The key conclusion of the thesis is that engagement with the question of a political union reflected a balance between political environment and political agency. The national political environment encouraged the consideration of a political union because it revealed a vulnerability to external occurrences which were beyond the control of the three provinces and connected with an internal logic for change. A political union was seen as a way for the region to develop the capacity to become economically self-sufficient and in turn neutralise the implications of unexpected externalities. However, alternative opportunities for political action were pursued when the national political environment became reconfigured and new political leaders were elected. This dynamic explains why, despite a critical juncture, a union did not happen. As such, the thesis shows that the current understanding of change to path dependent settings is confirmed. Established trajectories will be more inclined towards persistence than change. The key contribution of the thesis to path dependence theory is that change is not the default outcome of a critical juncture. If change is viable, considered but not ultimately selected it is no less a critical juncture than those which produce enduring change. On a broader level, the thesis gives an indication as to the difficulty of political amalgamations between constitutionally protected entities within established federal states.

CA1 is the main source of afferents from the hippocampus, but the function of CA1 and its perforant path (PP) input remains unclear. In this thesis, Marr’s model of the hippocampus is used to investigate previously hypothesized functions, and also to investigate some of Marr’s unexplored theoretical ideas. The last part of the thesis explains the excitatory responses to PP activity in vivo, despite inhibitory responses in vitro. Quantitative support for the idea of CA1 as a relay of information from CA3 to the neocortex and subiculum is provided by constraining Marr’s model to experimental data. Using the same approach, the much smaller capacity of the PP input by comparison implies it is not a one-shot learning network. In turn, it is argued that the entorhinal-CA1 connections cannot operate as a short-term memory network through reverberating activity. The PP input to CA1 has been hypothesized to control the activity of CA1 pyramidal cells. Marr suggested an algorithm for self-organising the output activity during pattern storage. Analytic calculations show a greater capacity for self-organised patterns than random patterns for low connectivities and high loads, confirmed in simulations over a broader parameter range. This superior performance is maintained in the absence of complex thresholding mechanisms, normally required to maintain performance levels in the sparsely connected networks. These results provide computational motivation for CA3 to establish patterns of CA1 activity without involvement from the PP input. The recent report of CA1 place cell activity with CA3 lesioned (Brun et al., 2002. Science, 296(5576):2243-6) is investigated using an integrate-and-fire neuron model of the entorhinal-CA1 network. CA1 place field activity is learnt, despite a completely inhibitory response to the stimulation of entorhinal afferents. In the model, this is achieved using N-methyl-D-asparate receptors to mediate a significant proportion of the excitatory response. Place field learning occurs over a broad parameter space. It is proposed that differences between similar contexts are slowly learnt in the PP and as a result are amplified in CA1. This would provide improved spatial memory in similar but different contexts.

Load transfer analysis deals with an important function of engineering structure, which is the ability of structure in transferring imposed loads to the supporting points. Although stress value has proved to be an efficient index for performing the failure analysis, the necessity of defining an index for evaluation of structure stiffness has led to the introduction of the U* index theory. The U* index characterizes the internal stiffness distributions, as an indicator of the load transfer in the structure. Although U* index theory have been proven to be useful in design, it is missing necessary steps toward becoming a mature theory for structural analysis. Firstly, the U* index theory needed to be examined and validated by experimental testing. Therefore, an experimental setup was proposed and tested, and U* index theory was validated through comparison of results. Secondly, a systematic comparison between the conventional stresses analysis and the U* index analysis was lacking. Such comparison was made for structural analyses of a vehicle component. The results, also compared to observations of experimental testing showed that in some cases, application of conventional stress analysis might be limited or less precise. Thirdly, design modification capability is a significant feature of the U* index theory, and it was necessary to demonstrate that real life problems can benefit from this potential. In this study, sample structures representing the components of multiple passengers carrying vehicles were selected and analyzed by U* index theory and design modifications were proposed and implemented on the structure. Lastly, the U* index theory should be applicable to different types of problems, including nonlinear domain. Hence, to remove the limitations of linear analysis that is a part of the original theory, an extension of U* index theory to the nonlinear domain was proposed and tested. In summary, U* index theory provides an understandable explanation of load transfer in the structure and provides a general awareness regarding structural performance. He presented work showed that the existing methods of structural analysis have limitations in certain aspects that can be overcome by combining the perspective of U* index analysis to the existing structural analysis paradigm. / February 2017

No description available.

This paper analyses the process of wealth accumulation with regard to the path dependence theory. Based on the theoretical foundations of Robert King Merton, Vilfredo Pareto and Pierre Bourdieu, mechanisms of wealth accumulation are analyzed. These mechanisms, which are understood as direct and indirect network effects, are formalized using the statistical computing software R. A base model without any mechanisms of wealth accumulation is developed, which makes it possible to include the analyzed mechanisms step by step and observe their effects on the process of wealth accumulation and social inequality. Piketty's findings from his work Capital in the 21st Century are included in the formalized models of wealth accumulation, in particular the relationship between the rate of return on capital and the growth rate of the economy. (author's abstract)

This thesis consists of two parts. The first part (Chapters 2-4) focuses on the problem of inverting the signature of a path of bounded variation, and we present three results here. First, we give an explicit inversion formula for any axis path in terms of its signature. Second, we show that for relatively smooth paths, the derivative at the end point can be approximated arbitrarily closely by its signature sequence, and we provide explicit error estimates. As an application, we give an effective inversion procedure for piecewise linear paths. Finally, we prove a uniform estimate for the signatures of paths of bounded variations, and obtain a reconstruction theorem via that uniform estimate. Although this general reconstruction theorem is not computationally efficient, the techniques involved in deriving the uniform estimate are useful in other situations, and we also give an application in the case of expected signatures for Brownian motion. The second part (Chapter 5) deals with rough paths. After introducing proper backgrounds, we extend the uniform estimate above to the context of rough paths, and show how it can lead to simple proofs of distance bounds for Gaussian iterated integrals.