Pathfinding is critical to virtual simulation applications. One of the most prominent pathfinding challenges is the fast computation of path plans in large and realistic virtual terrain environments. To tackle this problem, this work proposes the exploration of a quadtree structure in the navigation map representation of large real-world virtual terrains. Exploring a hierarchical approach for virtual terrain representation, we detail how a global hierarchical pathfinding algorithm searches for a path in a coarse initial navigation map representation. Then, during execution time, the pathfinding algorithm refines regions of interest in this terrain representation in order to compute paths with a higher quality in areas where a large amount of navigation obstacles is found. The computational time of such hierarchical pathfinding algorithm is systematically measured in different hierarchical and non-hierarchical terrain representation structures that are instantiated in the modeling of a small real-world terrain scenario. Then, similar experiments are developed in a large real-world virtual terrain that is inserted in a real-life simulation system for the development of military tactical training exercises. The results show that the computational time required to generate pathfinding answers can be optimized when the proposed hierarchical pathfinding algorithm along with the easy and reliable implementation of the quadtree-based navigation map representation of the large virtual terrain are explored in the development of simulation systems.

This report describes an algorithm for computing 3D object hierarchies fit for hlod optimization. The algorithm is used as a pre-processing stage in an hlod pipeline that automatically optimizes 3D models containing multiple meshes. The algorithm for generating hierarchies groups together meshes in a hierarchical tree using operations on bounding spheres of the meshes. The algorithm prioritizes grouping close objects together in the early stages, and relaxes its constraints toward the end, resulting in a tree structure with a single root node. The hierarchical tree is then used by computing proxy meshes, i.e. simplified stand-in meshes, for the inner nodes of the hierarchy. Finally, the resulting proxy meshes, together with the generated hierarchy and the original meshes, are used to render the model using a tree-traversing hlod switching algorithm that renders deeper parts of the tree containing more detailed meshes when more detail is needed. In addition, a minor change to the clustering algorithm is proposed. By swapping the bounding spheres to AABBs (Axis-Aligned Bounding Boxes) in the clustering stage, hierarchies with different properties are generated. This change is shown to generate hierarchies with similar rendering performance as the hierarchies made with bounding spheres, while at the same time resulting in lower space requirements for all proxy meshes. Overall, the proposed automatic hlod pipeline is shown to increase rendering performance for all evaluated scenes in most frames, while never yielding noticeably worse performance than the original model as well.

This research focuses on the redesign of trust and reputation algorithms in the context of hierarchically structured Peer-to-Peer (P2P) networks with Chord, a scalable P2P lookup service for Internet applications. Chord, which is an open source project, is an overlay network based on a distributed hash table(DHT), and all peers in Chord are arranged around a circle. In this work, we propose four adapted trust and reputation algorithms for hierarchically structured P2P networks: EigenTrust, PowerTrust, Absolute Trust and NodeRanking. EigenTrust is one of the most well-known trust and reputation algorithms, as well as the most simple. To calculate the reputation, EigenTrust needs to normalize trust and rely on pre-trusted peers. Like EigenTrust, PowerTrust relies on feedback and the use of a distributed ranking mechanism. It chooses a limited number of power nodes with a high reputation. By combining a random walk strategy and the power nodes, it improves accuracy of global reputation. AbsoluteTrust does not require normalization of trust, pretrusted peers or any centralized authority. Weighted average combined with feedback from peers is employed to determine trust. NodeRanking relies on both individual reputation and social relationship to compute the trust value. NodeRanking evaluates reputation using local information. A node's reputation value can be readily determined by the number of references from other nodes in the network. These adapted algorithms are capable of handling a huge number of nodes disseminated in different rings, which improves complexity and reduces the number of malicious nodes in a hierarchical context. Furthermore, we describe the components of the hierarchical model architecture and present and discuss the results from the experiments. These experiments are employed to verify and compare reduction of downloads from malicious peers, load distribution and residual curl in at structured networks and in hierarchically structured networks.

The most basic requirement for any computer controlled game agent in a video game is to be able to successfully navigate the game environment. Pathfinding is an essential component of any agent navigation system. Pathfinding is, at the simplest level, a search technique for finding a route between two points in an environment. The real-time multi-agent nature of video games places extremely tight constraints on the pathfinding problem. This study aims to provide the first complete review of the current state of video game pathfinding both in regards to the graph search algorithms employed as well as the implications of pathfinding within dynamic game environments. Furthermore this thesis presents novel work in the form of a domain specific search algorithm for use on grid-based game maps: the spatial grid A* algorithm which is shown to offer significant improvements over A* within the intended domain. Copyright / Dissertation (MSc)--University of Pretoria, 2011. / Computer Science / unrestricted

A general approach for conducting power analysis in two-and three-level hierarchical linear models (HLMs) is described. The method can be used to perform power analysis to detect fixed effects at any level of a HLM with dichotomous or continuous covariates. It can easily be extended to perform power analysis for functions of parameters. Important steps in the derivation of this approach are illustrated and numerical examples are provided. Sample code implementing this approach is provided using the free program R.

Master of Science / Department of Statistics / Paul I. Nelson / This research is devoted to studying statistical inference implemented using the Gibbs Sampler for a hierarchical Bayesian linear model with first order autoregressive structure. This model was applied to global-mean monthly temperatures from January 1880 to April 2008 and used to estimate a time trend coefficient and to test for the existence of global warming. The global temperature increase estimated by Gibbs Sampler was found to be between 0.0203℃ and 0.0284℃ per decade with 95% credibility. The difference between Gibbs Sampler estimate and ordinary least squares estimate for the time trend was insignificant. Further, a simulation study with data generated from this model was carried out. This study showed that the Gibbs Sampler estimators for the intercept and for the time trend were less biased than corresponding ordinary least squares estimators, while the reverse was true for the autoregressive parameter and error standard deviation. The difference in precision of the estimators found by the two approaches was insignificant except for the samples of small sizes. The Gibbs Sampler estimator of the time trend has significantly smaller mean square error than ordinary least squares estimator for the smaller sample sizes studied. This report also describes how the software package WinBUGS can be used to carry out the simulations required to implement a Gibbs Sampler.

System virtualization technology is widely used in computing nowadays. In embedded domain, it is used as a solution to resource sharing among independent applications. One of the areas is to apply virtualization technique to real-time embedded systems with timing constraints. Multi-level adaptive hierarchical scheduling (AdHierSched) framework is a virtualized real-time framework, which runs in the Linux operating system. Šis virtualized framework has ability to adapt the CPU partition sizes according to their need through monitoring their demand during run-time, which yields more appropriate processor assignment. However, the performance of the virtualized framework is still unknown when the budget borrowing mechanism is enabled. To this end, in this thesis, we explore a new direction for performing the adaptation of CPU partition. We design and implement a budget borrowing mechanism for dynamic adaptation of resource parameters in AdHierSched framework. Extensive simulations are performed in this thesis, which are used to study and compare di‚erent adaptation mechanisms with our approach. From the results of experiments, we conclude that when the framework works only with budget borrowing controller, the results are not as good as only running a budget controller in the AdHierSched framework. However, while running both of the controllers at the same time, the experiments results are good enough. We also analyze the overhead of the framework at the end of the evaluation. Finally, we conclude the thesis by presenting the possible future work.

The question of whether a machine can reproduce human intelligence is older than modern computation, but has received a great deal of attention since the first digital computers emerged decades ago. Language understanding, a hallmark of human intelligence, has been the focus of a great deal of work in Artificial Intelligence (AI). In 1950, mathematician Alan Turing proposed a kind of game, or test, to evaluate the intelligence of a machine by assessing its ability to understand written natural language. But nearly sixty years after Turing proposed his test of machine intelligence—pose questions to a machine and a person without seeing either, and try to determine which is the machine—no system has passed the Turing Test, and the question of whether a machine can understand natural language cannot yet be answered. The present investigation is, firstly, an attempt to advance the state of the art in natural language understanding by building a machine whose input is English natural language and whose output is a set of assertions that represent answers to certain questions posed about the content of the input. The machine we explore here, in other words, should pass a simplified version of the Turing Test and by doing so help clarify and expand on our understanding of the machine intelligence. Toward this goal, we explore a constraint framework for partial solutions to the Turing Test, propose a problem whose solution would constitute a significant advance in natural language processing, and design and implement a system adequate for addressing the problem proposed. The fully implemented system finds primary specific events and their locations in monologue discourse using a hierarchical classification approach, and as such provides answers to questions of central importance in the interpretation of discourse. / text

Clustering is a useful technique that divides data points into groups, also known as clusters, such that the data points of the same cluster exhibit similar properties. Typical clustering algorithms assign each data point to at least one cluster. However, in practical datasets like microarray gene dataset, only a subset of the genes are highly correlated and the dataset is often polluted with a huge volume of genes that are irrelevant. In such cases, it is important to ignore the poorly correlated genes and just cluster the highly correlated genes. Automated Hierarchical Density Shaving (Auto-HDS) is a non-parametric density based technique that partitions only the relevant subset of the dataset into multiple clusters while pruning the rest. Auto-HDS performs a hierarchical clustering that identifies dense clusters of different densities and finds a compact hierarchy of the clusters identified. Some of the key features of Auto-HDS include selection and ranking of clusters using custom stability criterion and a topologically meaningful 2D projection and visualization of the clusters discovered in the higher dimensional original space. However, a key limitation of Auto-HDS is that it requires O(n*n) storage, and O(n*n*logn) computational complexity, making it scale up to only a few 10s of thousands of points. In this thesis, two extensions to Auto-HDS are presented for lower dimensional datasets that can generate clustering identical to Auto-HDS but can scale to much larger datasets. We first introduce Partitioned Auto-HDS that provides significant reduction in time and space complexity and makes it possible to generate the Auto-HDS cluster hierarchy on much larger datasets with 100s of millions of data points. Then, we describe Parallel Auto-HDS that takes advantage of the inherent parallelism available in Partitioned Auto-HDS to scale to even larger datasets without a corresponding increase in actual run time when a group of processors are available for parallel execution. Partitioned Auto-HDS is implemented on top of GeneDIVER, a previously existing Java based streaming implementation of Auto-HDS, and thus it retains all the key features of Auto-HDS including ranking, automatic selection of clusters and 2D visualization of the discovered cluster topology. / text

Propensity score matching is commonly used to estimate causal effects of treatments. However, when using data with a hierarchical structure, we need to take the multilevel nature of the data into account. In this thesis the estimation of propensity scores with multilevel models is presented to extend propensity score matching for use with multilevel data. A Monte Carlo simulation study is performed to evaluate several different estimators. It is shown that propensity score estimators ignoring the multilevel structure of the data are biased, while fixed effects models produce unbiased results. An empirical study of the causal effect of truancy on mathematical ability for Swedish 9th graders is also performed, where it is shown that truancy has a negative effect on mathematical ability.