Theory and Algorithms Commons^™

Improving Closely Spaced Dim Object Detection Through Improved Multiframe Blind Deconvolution, Ronald M. Aung

Theses and Dissertations

This dissertation focuses on improving the ability to detect dim stellar objects that are in close proximity to a bright one, through statistical image processing using short exposure images. The goal is to improve the space domain awareness capabilities with the existing infrastructure. Two new algorithms are developed. The first one is through the Neighborhood System Blind Deconvolution where the data functions are separated into the bright object, the neighborhood system, and the background functions. The second one is through the Dimension Reduction Blind Deconvolution, where the object function is represented by the product of two matrices. Both are designed …

Artificial Intelligence In Pursuit-Evasion Games, Specifically In The Scotland Yard Game, Arif M. Alamri

Theses and Dissertations

This research provides a heuristic algorithm for the detectives, who try to collectively capture a criminal known as Mr. X, in the Scotland Yard pursuer-evasion game. In Scotland Yard, a team of detectives attempts to converge on and capture a criminal known as Mr. X. The heuristic algorithm developed in this thesis is designed to emulate human strategies when playing the game. The algorithm uses the current state of the board at each time step, including the current positions of the detectives as well as the last known position of Mr. X. The heuristic algorithm then analyses all of the …

A Genetic Algorithm To Minimise Number Of Vehicles In An Electric Vehicle Routing Problem, Kiian Leong Bertran Queck, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Electric Vehicles (EVs) and charging infrastructure are starting to become commonplace in major cities around the world. For logistics providers to adopt an EV fleet, there are many factors up for consideration, such as route planning for EVs with limited travel range as well as long-term planning of fleet size. In this paper, we present a genetic algorithm to perform route planning that minimises the number of vehicles required. Specifically, we discuss the challenges on the violations of constraints in the EV routing problem (EVRP) arising from applying genetic algorithm operators. To overcome the challenges, techniques specific to addressing the …

A Hybrid Framework Using A Qubo Solver For Permutation-Based Combinatorial Optimization, Siong Thye Goh, Sabrish Gopalakrishnan, Jianyuan Bo, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstrained model that involves parameter tuning. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits. First, to smooth the energy landscape, we reduce the magnitudes of the input without compromising optimality. We propose a machine learning approach to tune the parameters for good performance effectively. To handle possible infeasibility, we introduce …

Vehicle Routing Problem With Reverse Cross-Docking: An Adaptive Large Neighborhood Search Algorithm, Aldy Gunawan, Audrey Tedja Widjaja, Pieter Vansteenwegen, Vincent F. Yu

Research Collection School Of Computing and Information Systems

Cross-docking is a logistics strategy that aims at less transportation costs and fast customer deliveries. Incorporating an efficient vehicle routing could increase the benefits of the cross-docking. In this paper, the vehicle routing problem with reverse cross-docking (VRP-RCD) is studied. Reverse logistics has attracted more attention due to its ability to gain more profit and maintain the competitiveness of a company. VRP-RCD includes a four-level supply chain network: suppliers, cross-dock, customers, and outlets, with the objective of minimizing vehicle operational and transportation costs. A two-phase heuristic that employs an adaptive large neighborhood search (ALNS) with various destroy and repair operators …

An Effective Method For Attribute Subset Selection, Considering The Resource In Pattern Recognition, Bakhtiyorjon Bakirovich Akbaraliev

Chemical Technology, Control and Management

An analytical method for determining informative sets of features (INP) is developed, taking into account the resource for criteria based on the use of a measure of dispersion of classified objects. The areas of existence of the solution are defined. The statements and properties for the Fischer-type information criterion are proved, using which the proposed analytical method for determining the INP guarantees optimal results in the sense of maximizing the selected functional. The appropriateness of choosing this type of informative criterion is justified. A method for transforming attributes is proposed. The universality of the method in relation to the type …

Find Me If You Can: Aligning Users In Different Social Networks, Priyanka Kasbekar, Katerina Potika, Chris Pollett

Faculty Publications, Computer Science

Online Social Networks allow users to share experiences with friends and relatives, make announcements, find news and jobs, and more. Several have user bases that number in the hundred of millions and even billions. Very often many users belong to multiple social networks at the same time under possibly different user names. Identifying a user from one social network on another social network gives information about a user's behavior on each platform, which in turn can help companies perform graph mining tasks, such as community detection and link prediction. The process of identifying or aligning users in multiple networks is …

Machine Learning Corrected Quantum Dynamics Calculations, A. Jasinski, J. Montaner, R. C. Forrey, B. H. Yang, P. C. Stancil, Naduvalath Balakrishnan, J. Dai, A. Vargas-Hernandez, R. V. Krems

Chemistry and Biochemistry Faculty Research

Quantum scattering calculations for all but low-dimensional systems at low energies must rely on approximations. All approximations introduce errors. The impact of these errors is often difficult to assess because they depend on the Hamiltonian parameters and the particular observable under study. Here, we illustrate a general, system- and approximation-independent, approach to improve the accuracy of quantum dynamics approximations. The method is based on a Bayesian machine learning (BML) algorithm that is trained by a small number of exact results and a large number of approximate calculations, resulting in ML models that can generalize exact quantum results to different dynamical …

Self-Stabilizing Token Distribution On Trees With Constant Space, Yuichi Sudo, Ajoy K. Datta, Lawrence L. Larmore, Toshimitsu Masuzawa

Computer Science Faculty Research

Self-stabilizing and silent distributed algorithms for token distribution in rooted tree networks are given. Initially, each process of a graph holds at most l tokens. Our goal is to distribute the tokens uniformly in the whole network so that every process holds exactly k tokens. In the initial configuration, the total number of tokens in the network may not be nk where n is the number of processes in the network. The root process is given the ability to create a new token or remove a token from the network. We aim to minimize the convergence time, the number of …

Modified Surrogate Cutting Plane Algorithm (Mscpa) For Integer Linear Programming Problems, Israa Hasan

Emirates Journal for Engineering Research

This work concerned with introducing a new algorithm for solving integer linear programming problems. The improved algorithm can help by decreasing a calculation the complexity of these problems, an advantages of the proposed method are to reduce the solution time and to decrease algorithmic complexity. Some specific numerical examples are discussed to demonstrate the validity and applicability of the proposed method. The numerical results are compared with the solution of integer linear programming problems by using cutting plane method (Gomory method).

A 3d Image-Guided System To Improve Myocardial Revascularization Decision-Making For Patients With Coronary Artery Disease, Haipeng Tang

Dissertations

OBJECTIVES. Coronary artery disease (CAD) is the most common type of heart disease and kills over 360,000 people a year in the United States. Myocardial revascularization (MR) is a standard interventional treatment for patients with stable CAD. Fluoroscopy angiography is real-time anatomical imaging and routinely used to guide MR by visually estimating the percent stenosis of coronary arteries. However, a lot of patients do not benefit from the anatomical information-guided MR without functional testing. Single-photon emission computed tomography (SPECT) myocardial perfusion imaging (MPI) is a widely used functional testing for CAD evaluation but limits to the absence of anatomical information. …

Investigating Single Precision Floating General Matrix Multiply In Heterogeneous Hardware, Steven Harris

McKelvey School of Engineering Graduate Student Theses & Dissertations

The fundamental operation of matrix multiplication is ubiquitous across a myriad of disciplines. Yet, the identification of new optimizations for matrix multiplication remains relevant for emerging hardware architectures and heterogeneous systems. Frameworks such as OpenCL enable computation orchestration on existing systems, and its availability using the Intel High Level Synthesis compiler allows users to architect new designs for reconfigurable hardware using C/C++. Using the HARPv2 as a vehicle for exploration, we investigate the utility of several of the most notable matrix multiplication optimizations to better understand the performance portability of OpenCL and the implications for such optimizations on this and …

An Exact Algorithm For Agile Earth Observation Satellite Scheduling With Time-Dependent Profits, Guansheng Peng, Guopeng Song, Lining Xing, Aldy Gunawan, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

The scheduling of an Agile Earth Observation Satellite (AEOS) consists of selecting and scheduling a subset of possible targets for observation in order to maximize the collected profit related to the images while satisfying its operational constraints. In this problem, a set of candidate targets for observation is given, each with a time-dependent profit and a visible time window. The exact profit of a target depends on the start time of its observation, reaching its maximum at the midpoint of its visible time window. This time dependency stems from the fact that the image quality is determined by the look …

Adaptive Task Sampling For Meta-Learning, Chenghao Liu, Zhihao Wang, Doyen Sahoo, Yuan Fang, Kun Zhang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Meta-learning methods have been extensively studied and applied in computer vision, especially for few-shot classification tasks. The key idea of meta-learning for few-shot classification is to mimic the few-shot situations faced at test time by randomly sampling classes in meta-training data to construct fewshot tasks for episodic training. While a rich line of work focuses solely on how to extract meta-knowledge across tasks, we exploit the complementary problem on how to generate informative tasks. We argue that the randomly sampled tasks could be sub-optimal and uninformative (e.g., the task of classifying “dog” from “laptop” is often trivial) to the meta-learner. …

Atmospheric Contrail Detection With A Deep Learning Algorithm, Nasir Siddiqui

Scholarly Horizons: University of Minnesota, Morris Undergraduate Journal

Aircraft contrail emission is widely believed to be a contributing factor to global climate change. We have used machine learning techniques on images containing contrails in hopes of being able to identify those which contain contrails and those that do not. The developed algorithm processes data on contrail characteristics as captured by long-term image records. Images collected by the United States Department of Energy’s Atmospheric Radiation Management user facility(ARM) were used to train a deep convolutional neural network for the purpose of this contrail classification. The neural network model was trained with 1600 images taken by the Total Sky Imager(TSI) …

Lulling Waters: A Poetry Reading For Real-Time Music Generation Through Emotion Mapping, Ashley Muniz, Toshihisa Tsuruoka

Electronic Literature Organization Conference 2020

Through a poetic narrative, “Lulling Waters” tells the story of a whale overcoming the loss of his mother, who passed away from ingesting plastic, as he attempts to escape from the polluted oceanic world. The live performance of this poem utilizes a software system called Soundwriter, which was developed with the goal of enriching the oral storytelling experience through music. This video demonstrates how Soundwriter’s real-time hybrid system was able to analyze “Lulling Waters” through its lexical and auditory features. Emotionally salient words were given ratings based on arousal, valence, and dominance while the emotionally charged prosodic features of the …

Enumerative Branching With Less Repetition, Thiago Serra

Faculty Conference Papers and Presentations

We can compactly represent large sets of solutions for problems with discrete decision variables by using decision diagrams. With them, we can efficiently identify optimal solutions for different objective functions. In fact, a decision diagram naturally arises from the branch-and-bound tree that we could use to enumerate these solutions if we merge nodes from which the same solutions are obtained on the remaining variables. However, we would like to avoid the repetitive work of finding the same solutions from branching on different nodes at the same level of that tree. Instead, we would like to explore just one of these …

The Prediction Of Delay Time At Intersection And Route Planning For Autonomous Vehicles, Genwang Gou, Yongxin Zhao, Jiawei Liang, Ling Shi

Research Collection School Of Computing and Information Systems

Intelligent Intersections (roundabout and crossroads) management is considered as one of the challenges to significantly improve urban traffic efficiency. Recent researches in artificial intelligence suggest that autonomous vehicles have the possibility of forming intelligent intersection management, and likely to occupy the leading role in future urban traffic. If route planning method can be used for route decision of autonomous vehicle, the urban traffic efficiency can be further improved. In this paper, we propose an Intelligent Intersection Control Protocol (IICP) for controlling autonomous vehicles cross intersection, and recommend route for autonomous vehicles to reduce travel time and improve urban traffic efficiency. …

Improving Multimodal Named Entity Recognition Via Entity Span Detection With Unified Multimodal Transformer, Jianfei Yu, Jing Jiang, Li Yang, Rui Xia

Research Collection School Of Computing and Information Systems

In this paper, we study Multimodal Named Entity Recognition (MNER) for social media posts. Existing approaches for MNER mainly suffer from two drawbacks: (1) despite generating word-aware visual representations, their word representations are insensitive to the visual context; (2) most of them ignore the bias brought by the visual context. To tackle the first issue, we propose a multimodal interaction module to obtain both image-aware word representations and word-aware visual representations. To alleviate the visual bias, we further propose to leverage purely text-based entity span detection as an auxiliary module, and design a Unified Multimodal Transformer to guide the final …

Geoprune: Efficiently Matching Trips In Ride-Sharing Through Geometric Properties, Yixin Xu, Jianzhong Qi, Renata Borovica-Gajic

Research Collection School Of Computing and Information Systems

On-demand ride-sharing is rapidly growing. Matching trip requests to vehicles efficiently is critical for the service quality of ride-sharing. To match trip requests with vehicles, a prune-And-select scheme is commonly used. The pruning stage identifies feasible vehicles that can satisfy the trip constraints (e.g., trip time). The selection stage selects the optimal one(s) from the feasible vehicles. The pruning stage is crucial to lowering the complexity of the selection stage and to achieve efficient matching. We propose an effective and efficient pruning algorithm called GeoPrune. GeoPrune represents the time constraints of trip requests using circles and ellipses, which can be …

Enhancing The Performance Of Ir-Based Traceability Recovery Of Requirement Artifacts Using Noun Phrases, Dafaalla Abdelrahman Mashahi Khalafalla

Student Works (2020-2029)

Requirement traceability can be considered as a measure of software quality to help achieve validation, verification, and reusability. Neglecting traceability leads to less maintainable software. Creating traceability links after-the-fact, known as traceability recovery, is a tedious and time-consuming process when it is done manually. Therefore, information retrieval (IR) methods have been used to automatically identify traceability links between the artifacts. However, as a result of limitations of the software engineer and the IR techniques, the performance of the IR methods is negatively affected. There is no IR method that is able to recover traceability links between artifacts with high precision …

Unsupervised Monocular Depth Estimation With Multi-Scale Structural Similarity Powered Loss Function, Kohan Ali

Student Works (2020-2029)

Depth Estimation refers to a set of techniques and algorithms that aim to obtain a representation of spatial information of a scene. Nowadays specific hardware such as sensors, radars and multiple-view-recording cameras are being used in order to acquire depth data of a scene. Modern approaches use deep learning to address this task by trying to learn depth information in a supervised manner. However, this approach requires a large amount ground-truth data for a particular scene so that a model can be trained successfully. Also preparing ground-truth data for a range of environments is a challenging and expensive task to …

Efficient Vehicle Routing Optimization For Autistic Users, Mohammed Shabalah Abdulrahman Hasan

Student Works (2020-2029)

In recent years, daily life without a vehicle would be impossible. As an inevitable result, the number of vehicles on the road increases day by day in various large cities around the world. The increased number of vehicles is a big concern because it causes a lot of traffic congestions, especially during peak hours. Besides, there has been a rapid rise of on-demand Ride-Hailing Services (RHSs), such as Grab, Uber, EzCab, and MyCar, etc. This allows passengers with smartphones to place trip requests and assign them to drivers according to requester’s location and drivers' availability. In consequence, efficient routing algorithms …

Probabilistic Value Selection For Space Efficient Model, Gunarto Sindoro Njoo, Baihua Zheng, Kuo-Wei Hsu, Wen-Chih Peng

Research Collection School Of Computing and Information Systems

An alternative to current mainstream preprocessing methods is proposed: Value Selection (VS). Unlike the existing methods such as feature selection that removes features and instance selection that eliminates instances, value selection eliminates the values (with respect to each feature) in the dataset with two purposes: reducing the model size and preserving its accuracy. Two probabilistic methods based on information theory's metric are proposed: PVS and P + VS. Extensive experiments on the benchmark datasets with various sizes are elaborated. Those results are compared with the existing preprocessing methods such as feature selection, feature transformation, and instance selection methods. Experiment results …

Query Graph Generation For Answering Multi-Hop Complex Questions From Knowledge Bases, Yunshi Lan, Jing Jiang

Research Collection School Of Computing and Information Systems

Previous work on answering complex questions from knowledge bases usually separately addresses two types of complexity: questions with constraints and questions with multiple hops of relations. In this paper, we handle both types of complexity at the same time. Motivated by the observation that early incorporation of constraints into query graphs can more effectively prune the search space, we propose a modified staged query graph generation method with more flexible ways to generate query graphs. Our experiments clearly show that our method achieves the state of the art on three benchmark KBQA datasets.

Big Data, Spatial Optimization, And Planning, Kai Cao, Wenwen Li, Richard Church

Research Collection School Of Computing and Information Systems

Spatial optimization represents a set of powerful spatial analysis techniques that can be used to identify optimal solution(s) and even generate a large number of competitive alternatives. The formulation of such problems involves maximizing or minimizing one or more objectives while satisfying a number of constraints. Solution techniques range from exact models solved with such approaches as linear programming and integer programming, or heuristic algorithms, i.e. Tabu Search, Simulated Annealing, and Genetic Algorithms. Spatial optimization techniques have been utilized in numerous planning applications, such as location-allocation modeling/site selection, land use planning, school districting, regionalization, routing, and urban design. These methods …

Translating Counting Problems Into Computable Language Expressions, Zach Prescott

Theses

The realm of automated problem solving is a relatively new field, even in the context of natural language processing. One area where this is often demonstrated is that of creating a program that can solve word problems. The program must understand the problem, perform some processing, and then convey this information to a user in a way that is accessible and understandable. There has been quite a lot of progress in this area with simpler problems. However, when it comes to understanding problems that involve a level of NLP, the results are not conclusive. In this paper, we would like …

Design And Implementation Of A Deterministic And Nondeterministic Finite Automaton Simulator, Camron C. Dennler

Computer Science and Software Engineering

The purpose of this project is to assist students in visualizing and understanding the structure and operation of deterministic and nondeterministic finite automata. This software achieves this purpose by providing students with the ability to build, modify, and test automata in an intuitive environment. This enables a simple and efficient avenue for experimentation, which upholds the Cal Poly ideal of Learning by Doing.

Readers of this report should be familiar with basic concepts in the theory of finite state machines; a general understanding of object-oriented programming is also necessary.

Novel Fast Algorithms For Low Rank Matrix Approximation, John T. Svadlenka

Dissertations, Theses, and Capstone Projects

Recent advances in matrix approximation have seen an emphasis on randomization techniques in which the goal was to create a sketch of an input matrix. This sketch, a random submatrix of an input matrix, having much fewer rows or columns, still preserves its relevant features. In one of such techniques random projections approximate the range of an input matrix. Dimension reduction transforms are obtained by means of multiplication of an input matrix by one or more matrices which can be orthogonal, random, and allowing fast multiplication by a vector. The Subsampled Randomized Hadamard Transform (SRHT) is the most popular among …

Optimal Control Of A Rumor Propagation Model With Different Propagation Degrees In Social Network, Yingfeng Tang

Student Works (2020-2029)

Rumor is a social interaction of information, and its development is of great significance to human beings. In this paper, by studying the D K model and a rumor model spreading with rumor latent period, deduces the rumor model with differe nt propagation degrees of the spreaders. The two equilibrium points in the system are found through derivation. In real life, enterprises often ignore the reasonable planning of the cost of rumor control. By means of public education and media technology u sing by the authorities to debunk rumors, an optimal control problem i s established. The Pontryagin’s maximum principle …