Theory and Algorithms Commons^™

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 …

Differentially Private Subspace Clustering, Yining Wang, Yu-Xiang Wang, Aarti Singh

Research Collection School Of Computing and Information Systems

Subspace clustering is an unsupervised learning problem that aims at grouping data points into multiple “clusters” so that data points in a single cluster lie approximately on a low-dimensional linear subspace. It is originally motivated by 3D motion segmentation in computer vision, but has recently been generically applied to a wide range of statistical machine learning problems, which often involves sensitive datasets about human subjects. This raises a dire concern for data privacy. In this work, we build on the framework of differential privacy and present two provably private subspace clustering algorithms. We demonstrate via both theory and experiments that …

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 …

Extending The Teknomo-Fernandez Background Image Generation Algorithm On The Hsv Colour Space, Patricia Angela R. Abu, Proceso L. Fernandez Jr

Department of Information Systems & Computer Science Faculty Publications

Background subtraction, a procedure required in many video analysis applications such as object tracking , is dependent on the model background image. One efficient algorithm for background image generation is the Teknomo-Fernandez (TF) Algorithm, which uses modal values and a tournament-like strategy to produce a good background image very quickly. A previous study showed that the TF algorithm can be extended from the original 3 frames per tournament (T F 3) to T F 5 and T F 7, resulting in increased accuracies at a cost of increased processing times. In this study, we explore extending the T F 3, …

Dictionary Pair Learning On Grassmann Manifolds For Image Denoising, Xianhua Zeng, Wei Bian, Wei Liu, Jialie Shen, Dacheng Tao

Research Collection School Of Computing and Information Systems

Image denoising is a fundamental problem in computer vision and image processing that holds considerable practical importance for real-world applications. The traditional patch-based and sparse coding-driven image denoising methods convert 2D image patches into 1D vectors for further processing. Thus, these methods inevitably break down the inherent 2D geometric structure of natural images. To overcome this limitation pertaining to the previous image denoising methods, we propose a 2D image denoising model, namely, the dictionary pair learning (DPL) model, and we design a corresponding algorithm called the DPL on the Grassmann-manifold (DPLG) algorithm. The DPLG algorithm first learns an initial dictionary …

Prediction: The Quintessential Model Validation Test, Wayne Wakeland

Systems Science Friday Noon Seminar Series

It is essential to objectively test how well policy models predict real world behavior. The method used to support this assertion involves the review of three SD policy models emphasizing the degree to which the model was able to fit the historical outcome data and how well model-predicted outcomes matched real world outcomes as they unfolded. Findings indicate that while historical model agreement is a favorable indication of model validity, the act of making predictions without knowing the actual data, and comparing these predictions to actual data, can reveal model weaknesses that might be overlooked when all of the available …

An Incremental Phylogenetic Tree Algorithm Based On Repeated Insertions Of Species, Peter Revesz, Zhiqiang Li

School of Computing: Conference and Workshop Papers

In this paper, we introduce a new phylogenetic tree algorithm that generates phylogenetic trees by repeatedly inserting species one-by-one. The incremental phylogenetic tree algorithm can work on proteins or DNA sequences. Computer experiments show that the new algorithm is better than the commonly used UPGMA and Neighbor Joining algorithms.

Modeling Flood Risk For An Urban Cbd Using Ahp And Gis, Proceso L. Fernandez Jr, Generino P. Siddayao, Sony E. Valdez

Department of Information Systems & Computer Science Faculty Publications

The Central Business District (CBD) of a city is the activity center of the city, typically locating the main commercial and cultural establishments, as well as acting as the center point of the city’s transportation network. Flood risk assessment for a CBD is crucial for proper city planning and maintenance. In this study, we model the flood risk for the CBD of Tuguegarao City, which is located in northern Philippines. To accomplish this, we identified important flood-related factors whose data are either easily available or may be collected through some automated process that we developed. We then surveyed experts to …

The Effectiveness Of Using A Modified “Beat Frequent Pick” Algorithm In The First International Roshambo Tournament, Proceso L. Fernandez Jr, Sony E. Valdez, Generino P. Siddayao

Department of Information Systems & Computer Science Faculty Publications

In this study, a bot is developed to compete in the first International RoShamBo Tournament test suite. The basic “Beat Frequent Pick (BFP)” algorithm was taken from the supplied test suite and was improved by adding a random choice tailored fit against the opponent's distribution of picks. A training program was also developed that finds the best performing bot variant by changing the bot's behavior in terms of the timing of the recomputation of the pick distribution. Simulation results demonstrate the significantly improved performance of the proposed variant over the original BFP. This indicates the potential of using the core …

Functional Requirements Identification Using Item-To-Item Collaborative Filtering, Proceso L. Fernandez Jr, Reynald Jay F. Hidalgo

Department of Information Systems & Computer Science Faculty Publications

One of the most difficult tasks in the development of software is the identification of the functional requirements. A well-defined functional requirement will eventually map the success of a software project. A support tool that can recommend candidate functional requirements for a software project being developed will help software engineers to deliver the right software to the clients.
The purpose of this study is to determine whether a collection of previously developed software applications can serve as basis for the development of a model to identify functional requirements of a project to be developed. Completed software project documentations of Master …

Computational Approaches For Remote Monitoring Of Symptoms And Activities, Ferdaus Kawsar

Dissertations (1934 -)

We now have a unique phenomenon where significant computational power, storage, connectivity, and built-in sensors are carried by many people willingly as part of their life style; two billion people now use smart phones. Unique and innovative solutions using smart phones are motivated by rising health care cost in both the developed and developing worlds. In this work, development of a methodology for building a remote symptom monitoring system for rural people in developing countries has been explored. Design, development, deployment, and evaluation of e-ESAS is described. The system’s performance was studied by analyzing feedback from users. A smart phone …

Evaluation Of Data-Path Topologies For Self-Timed Conditional Statements, Navaneeth Prasannakumar Jamadagni

Dissertations and Theses

This research presents a methodology to evaluate data path topologies that implement a conditional statement for an average-case performance that is better than the worst-case performance. A conditional statement executes one of many alternatives depending on how Boolean conditions evaluate to true or false. Alternatives with simple computations take less time to execute. The self-timed designs can exploit the faster executing alternatives and provide an average-case behavior, where the average depends on the frequency of simple and complex computations, and the difference in the completion times of simple and complex computations. The frequency of simple and complex computations depends on …

Tweakable Ciphers: Constructions And Applications, Robert Seth Terashima

Dissertations and Theses

Tweakable ciphers are a building block used to construct a variety of cryptographic algorithms. Typically, one proves (via a reduction) that a tweakable-cipher-based algorithm is about as secure as the underlying tweakable cipher. Hence improving the security or performance of tweakable ciphers immediately provides corresponding benefits to the wide array of cryptographic algorithms that employ them. We introduce new tweakable ciphers, some of which have better security and others of which have better performance than previous designs. Moreover, we demonstrate that tweakable ciphers can be used directly (as opposed to as a building block) to provide authenticated encryption with associated …

Sails: Hybrid Algorithm For The Team Orienteering Problem With Time Windows, Aldy Gunawan, Hoong Chuin Lau, Kun Lu

Research Collection School Of Computing and Information Systems

The Team Orienteering Problem with Time Windows (TOPTW) is the extended version of the Orienteering Problem where each node is limited by a given time window. The objective is to maximize the total collected score from a certain number of paths. In this paper, a hybridization of Simulated Annealing and Iterated Local Search, namely SAILS, is proposed to solve the TOPTW. The efficacy of the proposed algorithm is tested using benchmark instances. The results show that the proposed algorithm is competitive with the state-of-the-art algorithms in the literature. SAILS is able to improve the best known solutions for 19 benchmark …

The Autoproof Verifier: Usability By Non-Experts And On Standard Code, Carlo A. Furia, Christopher M. Poskitt, Julian Tschannen

Research Collection School Of Computing and Information Systems

Formal verification tools are often developed by experts for experts; as a result, their usability by programmers with little formal methods experience may be severely limited. In this paper, we discuss this general phenomenon with reference to AutoProof: a tool that can verify the full functional correctness of object-oriented software. In particular, we present our experiences of using AutoProof in two contrasting contexts representative of non-expert usage. First, we discuss its usability by students in a graduate course on software verification, who were tasked with verifying implementations of various sorting algorithms. Second, we evaluate its usability in verifying code developed …

Inferring Interaction Type In Gene Regulatory Networks Using Co-Expression Data, Pegah Khosravi, Vahid H. Gazestani, Leila Pirhaji, Brian Law, Mehdi Sadeghi, Bahram Goliaei, Gary D. Bader

Publications and Research

Background

Knowledge of interaction types in biological networks is important for understanding the functional organization of the cell. Currently information-based approaches are widely used for inferring gene regulatory interactions from genomics data, such as gene expression profiles; however, these approaches do not provide evidence about the regulation type (positive or negative sign) of the interaction.

Results

This paper describes a novel algorithm, “Signing of Regulatory Networks” (SIREN), which can infer the regulatory type of interactions in a known gene regulatory network (GRN) given corresponding genome-wide gene expression data. To assess our new approach, we applied it to three different benchmark …

State Preserving Extreme Learning Machine For Face Recognition, Md. Zahangir Alom, Paheding Sidike, Vijayan K. Asari, Tarek M. Taha

Electrical and Computer Engineering Faculty Publications

Extreme Learning Machine (ELM) has been introduced as a new algorithm for training single hidden layer feed-forward neural networks (SLFNs) instead of the classical gradient-based algorithms. Based on the consistency property of data, which enforce similar samples to share similar properties, ELM is a biologically inspired learning algorithm with SLFNs that learns much faster with good generalization and performs well in classification applications. However, the random generation of the weight matrix in current ELM based techniques leads to the possibility of unstable outputs in the learning and testing phases. Therefore, we present a novel approach for computing the weight matrix …

Automatic Video Self Modeling For Voice Disorder, Ju Shen, Changpeng Ti, Anusha Raghunathan, Sen-Ching S. Cheung, Rita Patel

Computer Science Faculty Publications

Video self modeling (VSM) is a behavioral intervention technique in which a learner models a target behavior by watching a video of him- or herself. In the field of speech language pathology, the approach of VSM has been successfully used for treatment of language in children with Autism and in individuals with fluency disorder of stuttering. Technical challenges remain in creating VSM contents that depict previously unseen behaviors. In this paper, we propose a novel system that synthesizes new video sequences for VSM treatment of patients with voice disorders. Starting with a video recording of a voice-disorder patient, the proposed …

Meta-Raps Hybridization With Machine Learning Algorithms, Fatemah Al-Duoli

Engineering Management & Systems Engineering Theses & Dissertations

This dissertation focuses on advancing the Metaheuristic for Randomized Priority Search algorithm, known as Meta-RaPS, by integrating it with machine learning algorithms. Introducing a new metaheuristic algorithm starts with demonstrating its performance. This is accomplished by using the new algorithm to solve various combinatorial optimization problems in their basic form. The next stage focuses on advancing the new algorithm by strengthening its relatively weaker characteristics. In the third traditional stage, the algorithms are exercised in solving more complex optimization problems. In the case of effective algorithms, the second and third stages can occur in parallel as researchers are eager to …

Accuracy Comparison Of Numerical Integration Algorithms For Real-Time Hybrid Simulations, Ganesh Anant Reddy

Civil & Environmental Engineering Theses & Dissertations

The use of accurate numerical integration algorithms is one of the key factors for a successful real-time hybrid simulation (RTHS). In RTHSs, explicit integration algorithms are preferred more than implicit methods since all calculations need to be completed within a given time step during simulation. Explicit methods require the use of effective stiffness and damping for experimental substructures, which are incorporated into the calculation of the integration parameters. In general, those values that are greater than the expected stiffness and damping of the experimental substructure are used to ensure the stability of simulation. If a rate-dependent and nonlinear experimental substructure …

A Comparative Study Between Motivated Learning And Reinforcement Learning, James T. Graham, Janusz A. Starzyk, Zhen Ni, Haibo He, T.-H. Teng, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

This paper analyzes advanced reinforcement learning techniques and compares some of them to motivated learning. Motivated learning is briefly discussed indicating its relation to reinforcement learning. A black box scenario for comparative analysis of learning efficiency in autonomous agents is developed and described. This is used to analyze selected algorithms. Reported results demonstrate that in the selected category of problems, motivated learning outperformed all reinforcement learning algorithms we compared with.

Optimizing Selection Of Competing Features Via Feedback-Directed Evolutionary Algorithms, Tian Huat Tan, Yinxing Xue, Manman Chen, Jun Sun, Yang Liu, Jin Song Dong Dong

Research Collection School Of Computing and Information Systems

Software that support various groups of customers usually require complicated configurations to attain different functionalities. To model the configuration options, feature model is proposed to capture the commonalities and competing variabilities of the product variants in software family or Software Product Line (SPL). A key challenge for deriving a new product is to find a set of features that do not have inconsistencies or conflicts, yet optimize multiple objectives (e.g., minimizing cost and maximizing number of features), which are often competing with each other. Existing works have attempted to make use of evolutionary algorithms (EAs) to address this problem. In …

Message Passing For Collective Graphical Models, Tao Sun, Daniel Sheldon, Akshat Kumar

Research Collection School Of Computing and Information Systems

Collective graphical models (CGMs) are a formalism for inference and learning about a population of independent and identically distributed individuals when only noisy aggregate data are available. We highlight a close connection between approximate MAP inference in CGMs and marginal inference in standard graphical models. The connection leads us to derive a novel Belief Propagation (BP) style algorithm for collective graphical models. Mathematically, the algorithm is a strict generalization of BP—it can be viewed as an extension to minimize the Bethe free energy plus additional energy terms that are non-linear functions of the marginals. For CGMs, the algorithm is much …

Object Tracking From Multiple Multi-Axis Platforms In Four Dimensions, Theodore A. Teates

Electrical & Computer Engineering Theses & Dissertations

Object handoff in free space requires a sound framework between at least two optical sensors and one object. Previous work developed an algorithm that can determine the ap­ propriate time to initiate handoff of object tracking responsibilities from one optical sensor with an object in view to another optical sensor with the same object in view. In order to maintain persistent tracking of objects in this work, gimbal movements of optical sensors are determined by calculations using the Lagrange method to determine the trackability measures between the moving object and the handoff cone for the appropriate optical sensor. The rotation …

Solar: Scalable Online Learning Algorithms For Ranking, Jialei Wang, Ji Wan, Yongdong Zhang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Traditional learning to rank methods learn ranking models from training data in a batch and offline learning mode, which suffers from some critical limitations, e.g., poor scalability as the model has to be retrained from scratch whenever new training data arrives. This is clearly nonscalable for many real applications in practice where training data often arrives sequentially and frequently. To overcome the limitations, this paper presents SOLAR- a new framework of Scalable Online Learning Algorithms for Ranking, to tackle the challenge of scalable learning to rank. Specifically, we propose two novel SOLAR algorithms and analyze their IR measure bounds theoretically. …

Cooperative 3-D Map Generation Using Multiple Uavs, Andrew Erik Lawson

University Scholar Projects

This report aims to demonstrate the feasibility of building a global 3-D map from multiple UAV robots in a GPS-denied, indoor environment. Presented are the design of each robot and the reasoning behind choosing its hardware and software components, the process in which a single robot obtains a individual 3-D map entirely onboard, and lastly how the mapping concept is extended to multiple robotic agents to form a global 3-D map using a centralized server. In the latter section, this report focuses on two algorithms, Online Mapping and Map Fusion, developed to facilitate the cooperative approach. A limited selection …