Computer Sciences Commons^™

Enhancements To Hierarchical Pathfinding Algorithms, Xin Li

Electronic Theses and Dissertations

In this thesis we study the problem of pathfinding in static grid-based maps. We apply the approach of abstraction and refinement. We abstract the grid map into a graph representation, and use the classic A* algorithm to search for a path in the abstract space, and then refine it into low-level path.

We started with a 2013 entry program to the Grid-based Path Planning Competition, and implemented several enhancements to experiment with the tradeoff between memory usage and search speed. Our program returns the refined low-level path incrementally, therefore reduces the first-move lag in large maps. We cache the low-level …

Modeling, Learning And Reasoning About Preference Trees Over Combinatorial Domains, Xudong Liu

Theses and Dissertations--Computer Science

In my Ph.D. dissertation, I have studied problems arising in various aspects of preferences: preference modeling, preference learning, and preference reasoning, when preferences concern outcomes ranging over combinatorial domains. Preferences is a major research component in artificial intelligence (AI) and decision theory, and is closely related to the social choice theory considered by economists and political scientists. In my dissertation, I have exploited emerging connections between preferences in AI and social choice theory. Most of my research is on qualitative preference representations that extend and combine existing formalisms such as conditional preference nets, lexicographic preference trees, answer-set optimization programs, possibilistic …

Chillisource Game Engine Particle System Study, Angela Gross

Graduate Student Theses, Dissertations, & Professional Papers

The majority of modern game engines utilize intricate objects called particle systems which are a collection of many particles that together represent an object without well-defined surfaces. This thesis discusses the results of studying and stressing particle systems within ChilliSource, an open-source game engine written in C++, with the goal of understanding a complex system and exploring possible optimizations that could be made to it. The studies performed were driven by metrics generated with custom profiling classes that kept track of things like the number of particles rendered, how long the engine spent rendering particles, or even how long a …

Simulation Of Nuclear Fusion Using A One Dimensional Particle In Cell Method, Steven T. Margell

Cal Poly Humboldt theses and projects

In this thesis several novel techniques are developed to simulate fusion events in an isotropic, electrostatic three-dimensional Deuterium-Tritium plasma. These techniques allow us to accurately predict three-dimensional collision events with a one-dimensional model while simultaneously reducing compute time via a nearest neighbor algorithm. Furthermore, a fusion model based on first principles is developed that yields an average fusion reactivity which correlates well with empirical results.

Using Genetic Algorithms To Evolve Artificial Neural Networks, William T. Kearney

Honors Theses

This paper demonstrates that neuroevolution is an effective method to determine an optimal neural network topology. I provide an overview of the NeuroEvolution of Augmenting Topologies (NEAT) algorithm, and describe how unique characteristics of this algorithm solve various problem inherent to neuroevolution (namely the competing conventions problem and the challenges associated with protecting topological innovation). Parallelization is shown to greatly speed up efficiency, further reinforcing neuroevolution as a potential alternative to traditional backpropagation. I also demonstrate that appropriate parameter selection is critical in order to efficiently converge to an optimal topology. Lastly, I produce an example solution to a medical …

Algorithmic Foundations Of Heuristic Search Using Higher-Order Polygon Inequalities, Newton Henry Campbell Jr.

CCAC Theses and Dissertations

The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark …

Aspect Mining Using Multiobjective Genetic Clustering Algorithms, David G. Bethelmy

CCAC Theses and Dissertations

In legacy software, non-functional concerns tend to cut across the system and manifest themselves as tangled or scattered code. If these crosscutting concerns could be modularized and the system refactored, then the system would become easier to understand, modify, and maintain. Modularized crosscutting concerns are known as aspects and the process of identifying aspect candidates in legacy software is called aspect mining.

One of the techniques used in aspect mining is clustering and there are many clustering algorithms. Current aspect mining clustering algorithms attempt to form clusters by optimizing one objective function. However, the objective function to be optimized tends …

Mutable Class Design Pattern, Nikolay Malitsky

CCAC Theses and Dissertations

The dissertation proposes, presents and analyzes a new design pattern, the Mutable Class pattern, to support the processing of large-scale heterogeneous data models with multiple families of algorithms. Handling data-algorithm associations represents an important topic across a variety of application domains. As a result, it has been addressed by multiple approaches, including the Visitor pattern and the aspect-oriented programming (AOP) paradigm. Existing solutions, however, bring additional constraints and issues. For example, the Visitor pattern freezes the class hierarchies of application models and the AOP-based projects, such as Spring AOP, introduce significant overhead for processing large-scale models with fine-grain objects. The …

Automatically Defined Templates For Improved Prediction Of Non-Stationary, Nonlinear Time Series In Genetic Programming, David Moskowitz

CCAC Theses and Dissertations

Soft methods of artificial intelligence are often used in the prediction of non-deterministic time series that cannot be modeled using standard econometric methods. These series, such as occur in finance, often undergo changes to their underlying data generation process resulting in inaccurate approximations or requiring additional human judgment and input in the process, hindering the potential for automated solutions.

Genetic programming (GP) is a class of nature-inspired algorithms that aims to evolve a population of computer programs to solve a target problem. GP has been applied to time series prediction in finance and other domains. However, most GP-based approaches to …

Tabulating Pseudoprimes And Tabulating Liars, Andrew Shallue

Scholarship

This paper explores the asymptotic complexity of two problems related to the Miller-Rabin-Selfridge primality test. The first problem is to tabulate strong pseudoprimes to a single fixed base $a$. It is now proven that tabulating up to $x$ requires $O(x)$ arithmetic operations and $O(x\log{x})$ bits of space. The second problem is to find all strong liars and witnesses, given a fixed odd composite $n$. This appears to be unstudied, and a randomized algorithm is presented that requires an expected $O((\log{n})^2 + |S(n)|)$ operations (here $S(n)$ is the set of strong liars). Although interesting in their own right, a notable application …

Dynamically Parallel Camshift: Gpu Accelerated Object Tracking In Digital Video, Matthew J. Perry

EWU Masters Thesis Collection

"The CAMSHIFT algorithm is widely used for tracking dynamically sized and positioned objects in real-time applications. In spite of its extensive study on the platform of sequential CPU, its research on massively parallel Graphical Processing Unit (GPU) platform is quite limited. In this work, we designed and implemented two different parallel algorithms for CAMSHIFT using CUDA. The first design performs calculations on the GPU, but requires iterative data transfers back to the host CPU for condition checking, which bottlenecks the entire program. In the second design, we propose an enhanced parallel reduction-based CAMSHIFT using dynamic parallelism to reduce overhead of …

Topics On Register Synthesis Problems, Weihua Liu

Theses and Dissertations--Computer Science

Pseudo-random sequences are ubiquitous in modern electronics and information technology. High speed generators of such sequences play essential roles in various engineering applications, such as stream ciphers, radar systems, multiple access systems, and quasi-Monte-Carlo simulation. Given a short prefix of a sequence, it is undesirable to have an efficient algorithm that can synthesize a generator which can predict the whole sequence. Otherwise, a cryptanalytic attack can be launched against the system based on that given sequence.

Linear feedback shift registers (LFSRs) are the most widely studied pseudorandom sequence generators. The LFSR synthesis problem can be solved by the Berlekamp-Massey algorithm, …

Mining Human Activity Using Dimensionality Reduction And Pattern Recognition, Ismail El Moudden, Mounir Ouzir, Badreddine Benyacoub, Souad El Bernoussi

Research and Infrastructure Service Enterprise (RISE) Faculty Publications

Human activity recognition (HAR) is an emerging research topic in pattern recognition, especially in computer vision. The main objective of human activity recognition is to automatically detect and analyze human activities from the information acquired from different sensors. Human activity prediction using big data remains a challengingly open problem. Several approaches have recently been developed in order to find practical ways to solve high dimensionality of data problems. The aim of this study is to attempt, using data mining techniques, to deal with HAR modeling involving a significant number of variables in order to identify relevant parameters from data and …

K-D Tree-Segmented Block Truncation Coding For Image Compression, Proceso L. Fernandez Jr, Ryan Rey M. Daga

Department of Information Systems & Computer Science Faculty Publications

Block truncation coding (BTC) is a class of image compression algorithms whose main technique is the partitioning of an image into pixel blocks that are then each encoded using a representative set of pixel values. It is commonly used because of its simplicity and low computational complexity. The Quadtree-segmented BTC (QTS-BTC), which utilizes a dynamic hierarchical segmentation technique, is among the most efficient in the BTC class. In this study, we propose a new BTC variant that introduces two ideas: (1) the use of a k-d tree for segmentation and (2) the use of a Mean Squared Error (MSE) threshold …

Identifying Parameters For Robust Network Growth Using Attachment Kernels: A Case Study On Directed And Undirected Networks, Ahmed F. Abdelzaher

Theses and Dissertations

Network growing mechanisms are used to construct random networks that have structural behaviors similar to existing networks such as genetic networks, in efforts of understanding the evolution of complex topologies. Popular mechanisms, such as preferential attachment, are capable of preserving network features such as the degree distribution. However, little is known about such randomly grown structures regarding robustness to disturbances (e.g., edge deletions). Moreover, preferential attachment does not target optimizing the network's functionality, such as information flow. Here, we consider a network to be optimal if it's natural functionality is relatively high in addition to possessing some degree of robustness …

Evaluating And Improving The Efficiency Of Software And Algorithms For Sequence Data Analysis, Hugh L. Eaves

Theses and Dissertations

With the ever-growing size of sequence data sets, data processing and analysis are an increasingly large portion of the time and money spent on nucleic acid sequencing projects. Correspondingly, the performance of the software and algorithms used to perform that analysis has a direct effect on the time and expense involved. Although the analytical methods are widely varied, certain types of software and algorithms are applicable to a number of areas. Targeting improvements to these common elements has the potential for wide reaching rewards. This dissertation research consisted of several projects to characterize and improve upon the efficiency of several …

Press: Personalized Event Scheduling Recommender System (Demonstration), Hoong Chuin Lau, Aldy Gunawan, Pradeep Varakantham, Wenjie Wang

Research Collection School Of Computing and Information Systems

This paper presents a personalized event scheduling recom-mender system, PRESS, for a large conference setting with multiple parallel tracks. PRESS is a mobile application that gathers personalized information from a user and recommends talks/demos to be attend. The input from a user include a list of keyword preferences and (optionally) preferred talks. We use the MALLET topic model package to analyze the set of conference papers and classify them based on automatically identified topics. We propose an algorithm to generate a list of recommended papers based on the user keywords and the MALLET topics. An optimization model is then applied …

An Efficient Method For Optimizing Segmentation Parameters, Jacob D' Avy, Wei-Wen Hsu, Chung-Hao Chen, Andreas F. Koschan, Mongi Abidi

Electrical & Computer Engineering Faculty Publications

Segmenting an image into meaningful regions is an important step in many computer vision applications such as facial recognition, target tracking and medical image analysis. Because image segmentation is an ill-posed problem, parameters are needed to constrain the solution to one that is suitable for a given application. For a user, setting parameter values is often unintuitive. We present a method for automating segmentation parameter selection using an efficient search method to optimize a segmentation objective function. Efficiency is improved by utilizing prior knowledge about the relationship between a segmentation parameter and the objective function terms. An adaptive sampling of …

Java Based Visualization And Animation For Teaching The Dijkstra Shortest Path Algorithm In Transportation Networks, Ivan Makohon, Duc T. Nguyen, Masha Sosonkina, Yuzhong Shen, Manwo Ng

Civil & Environmental Engineering Faculty Publications

Shortest path (SP) algorithms, such as the popular Dijkstra algorithm has been considered as the "basic building blocks" for many advanced transportation network models. Dijkstra algorithm will find the shortest time (ST) and the corresponding SP to travel from a source node to a destination node. Applications of SP algorithms include real-time GPS and the Frank-Wolfe network equilibrium.

For transportation engineering students, the Dijkstra algorithm is not easily understood. This paper discusses the design and development of a software that will help the students to fully understand the key components involved in the Dijkstra SP algorithm. The software presents an …

An Improved Smote Algorithm Based On Genetic Algorithm For Imbalanced Data Collection, Qiong Gu, Xian-Ming Wang, Zhao Wu, Bing Ning, Chun-Sheng Xin

Electrical & Computer Engineering Faculty Publications

Classification of imbalanced data has been recognized as a crucial problem in machine learning and data mining. In an imbalanced dataset, minority class instances are likely to be misclassified. When the synthetic minority over-sampling technique (SMOTE) is applied in imbalanced dataset classification, the same sampling rate is set for all samples of the minority class in the process of synthesizing new samples, this scenario involves blindness. To overcome this problem, an improved SMOTE algorithm based on genetic algorithm (GA), namely, GASMOTE was proposed. First, GASMOTE set different sampling rates for different minority class samples. A combination of the sampling rates …

Performance Based Contracting For The Manufacturing Industry By Using Integrated Platform And Dynamic Pricing Model, Lindawati, Aldy Gunawan

Research Collection Lee Kong Chian School Of Business

Although Performance Based Contracting (PBC) concept is not totally new, the PBC adaptation in Industrial Machinery and Components (IMC) manufacturing, which produces high-value and long life machineries, is rather slow and it is done with extra caution. Three main concerns for manufacturers to implement PBC are the investment cost, the maintenance cost and possible revenue loss. To handle these concerns and accelerate the PBC implementation, we propose an integrated platform that consists of three components: dynamic pricing, sensor data feeding and machinery monitoring. We model the dynamic pricing as an optimization problem and propose Genetic Algorithm to solve the problem. …

Online Arima Algorithms For Time Series Prediction, Chenghao Liu, Hoi, Steven C. H., Peilin Zhao, Jianling Sun

Research Collection School Of Computing and Information Systems

Autoregressive integrated moving average (ARIMA) is one of the most popular linear models for time series forecasting due to its nice statistical properties and great flexibility. However, its parameters are estimated in a batch manner and its noise terms are often assumed to be strictly bounded, which restricts its applications and makes it inefficient for handling large-scale real data. In this paper, we propose online learning algorithms for estimating ARIMA models under relaxed assumptions on the noise terms, which is suitable to a wider range of applications and enjoys high computational efficiency. The idea of our ARIMA method is to …

On Detecting Maximal Quasi Antagonistic Communities In Signed Graphs, Ming Gao, Ee-Peng Lim, David Lo, Philips Kokoh Prasetyo

Research Collection School Of Computing and Information Systems

Many networks can be modeled as signed graphs. These include social networks, and relationships/interactions networks. Detecting sub-structures in such networks helps us understand user behavior, predict links, and recommend products. In this paper, we detect dense sub-structures from a signed graph, called quasi antagonistic communities (QACs). An antagonistic community consists of two groups of users expressing positive relationships within each group but negative relationships across groups. Instead of requiring complete set of negative links across its groups, a QAC allows a small number of inter-group negative links to be missing. We propose an algorithm, Mascot, to find all maximal quasi …

On The Limits And Practice Of Automatically Designing Self-Stabilization, Alex Klinkhamer

Dissertations, Master's Theses and Master's Reports

A protocol is said to be self-stabilizing when the distributed system executing it is guaranteed to recover from any fault that does not cause permanent damage. Designing such protocols is hard since they must recover from all possible states, therefore we investigate how feasible it is to synthesize them automatically. We show that synthesizing stabilization on a fixed topology is NP-complete in the number of system states. When a solution is found, we further show that verifying its correctness on a general topology (with any number of processes) is undecidable, even for very simple unidirectional rings. Despite these negative results, …

Battle Bot Ai – Patriot Bot, James Johnston

Computer Engineering

An entry in the the 'Battle Block AI' competition hosted by 'The AI Games'.

Positive Influence Dominating Set Generation In Social Networks, Akshaye Dhawan, Matthew Rink

Mathematics, Computer Science & Statistics Faculty Publications

Current algorithms in the Positive Influence Dominating Set (PIDS) problem domain are focused on a specific type of PIDS, the Total Positive Influence Dominating Set (TPIDS). We have developed an algorithm specifically targeted towards the non-total type of PIDS. In addition to our new algorithm, we adapted two existing TPIDS algorithms to generate PIDS. We ran simulations for all three algorithms, and our new algorithm consistently generates smaller PIDS than both existing algorithms, with our algorithm generating PIDS approximately 5% smaller than the better of the two existing algorithms.

Randomized Algorithms For Approximating A Connected Dominating Set In Wireless Sensor Networks, Akshaye Dhawan, Michelle Tanco, Aaron Yeiser

Mathematics, Computer Science & Statistics Faculty Publications

A Connected Dominating Set (CDS) of a graph representing a Wireless Sensor Network can be used as a virtual backbone for routing through the network. Since the sensors in the network are constrained by limited battery life, we desire a minimal CDS for the network, a known NP-hard problem. In this paper we present three randomized algorithms for constructing a CDS. We evaluate our algorithms using simulations and compare them to the two-hop K2 algorithm and two other greedy algorithms from the literature. After pruning, the randomized algorithms construct a CDS that are generally equivalent in size to those constructed …

Co-Rotational Finite Element Solid Simulation With Collisions, Patrick Riordan

Computer Science and Software Engineering

This paper is a tutorial on how to implement a deformable solid simulation with collisions based off of Matthias Mueller's Real Time Physics Course Notes. It covers the topics continuum mechanics, finite element analysis, implicit Euler integration, and handling collision.

An Immersive Telepresence System Using Rgb-D Sensors And Head-Mounted Display, Xinzhong Lu, Ju Shen, Saverio Perugini, Jianjun Yang

Computer Science Faculty Publications

We present a tele-immersive system that enables people to interact with each other in a virtual world using body gestures in addition to verbal communication. Beyond the obvious applications, including general online conversations and gaming, we hypothesize that our proposed system would be particularly beneficial to education by offering rich visual contents and interactivity. One distinct feature is the integration of egocentric pose recognition that allows participants to use their gestures to demonstrate and manipulate virtual objects simultaneously. This functionality enables the instructor to effectively and efficiently explain and illustrate complex concepts or sophisticated problems in an intuitive manner. The …

Multiple Instance Fuzzy Inference., Amine Ben Khalifa

Electronic Theses and Dissertations

A novel fuzzy learning framework that employs fuzzy inference to solve the problem of multiple instance learning (MIL) is presented. The framework introduces a new class of fuzzy inference systems called Multiple Instance Fuzzy Inference Systems (MI-FIS). Fuzzy inference is a powerful modeling framework that can handle computing with knowledge uncertainty and measurement imprecision effectively. Fuzzy Inference performs a non-linear mapping from an input space to an output space by deriving conclusions from a set of fuzzy if-then rules and known facts. Rules can be identified from expert knowledge, or learned from data. In multiple instance problems, the training data …