Physical Sciences and Mathematics Commons^™

A Comparative Study Of Underwater Robot Path Planning Algorithms For Adaptive Sampling In A Network Of Sensors, Sreeja Banerjee

School of Computing: Dissertations, Theses, and Student Research

Monitoring lakes, rivers, and oceans is critical to improving our understanding of complex large-scale ecosystems. We introduce a method of underwater monitoring using semi-mobile underwater sensor networks and mobile underwater robots in this thesis. The underwater robots can move freely in all dimension while the sensor nodes are anchored to the bottom of the water column and can move only up and down along the depth of the water column. We develop three different algorithms to optimize the path of the underwater robot and the positions of the sensors to improve the overall quality of sensing of an area of …

Integrating Motivated Learning And K-Winner-Take-All To Coordinate Multi-Agent Reinforcement Learning, Teck-Hou Teng, Ah-Hwee Tan, Janusz Starzyk, Yuan-Sin Tan, Loo-Nin Teow

Research Collection School Of Computing and Information Systems

This work addresses the coordination issue in distributed optimization problem (DOP) where multiple distinct and time-critical tasks are performed to satisfy a global objective function. The performance of these tasks has to be coordinated due to the sharing of consumable resources and the dependency on non-consumable resources. Knowing that it can be sub-optimal to predefine the performance of the tasks for large DOPs, the multi-agent reinforcement learning (MARL) framework is adopted wherein an agent is used to learn the performance of each distinct task using reinforcement learning. To coordinate MARL, we propose a novel coordination strategy integrating Motivated Learning (ML) …

Integrating Motivated Learning And K-Winner-Take-All To Coordinate Multi-Agent Reinforcement Learning, Teck-Hou Teng, Ah-Hwee Tan, Janusz Starzyk, Yuan-Sin Tan, Loo-Nin Teow

Research Collection School Of Computing and Information Systems

This work addresses the coordination issue in distributed optimization problem (DOP) where multiple distinct and time-critical tasks are performed to satisfy a global objective function. The performance of these tasks has to be coordinated due to the sharing of consumable resources and the dependency on non-consumable resources. Knowing that it can be sub-optimal to predefine the performance of the tasks for large DOPs, the multi-agent reinforcement learning (MARL) framework is adopted wherein an agent is used to learn the performance of each distinct task using reinforcement learning. To coordinate MARL, we propose a novel coordination strategy integrating Motivated Learning (ML) …

Hybrid Metaheuristics For Solving The Quadratic Assignment Problem And The Generalized Quadratic Assignment Problem, Aldy Gunawan, Kien Ming Ng, Kim Leng Poh, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

This paper presents a hybrid metaheuristic for solving the Quadratic Assignment Problem (QAP). The proposed algorithm involves using the Greedy Randomized Adaptive Search Procedure (GRASP) to construct an initial solution, and then using a hybrid Simulated Annealing and Tabu Search (SA-TS) algorithm to further improve the solution. Experimental results show that the hybrid metaheuristic is able to obtain good quality solutions for QAPLIB test problems within reasonable computation time. The proposed algorithm is extended to solve the Generalized Quadratic Assignment Problem (GQAP), with an emphasis on modelling and solving a practical problem, namely an examination timetabling problem. We found that …

A Mathematical Model And Metaheuristics For Time Dependent Orienteering Problem, Aldy Gunawan, Zhi Yuan, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

This paper presents a generalization of the Orienteering Problem, the Time-Dependent Orienteering Problem (TDOP) which is based on the real-life application of providing automatic tour guidance to a large leisure facility such as a theme park. In this problem, the travel time between two nodes depends on the time when the trip starts. We formulate the problem as an integer linear programming (ILP) model. We then develop various heuristics in a step by step fashion: greedy construction, local search and variable neighborhood descent, and two versions of iterated local search. The proposed metaheuristics were tested on modified benchmark instances, randomly …

Diversity-Oriented Bi-Objective Hyper-Heuristics For Patrol Scheduling, Mustafa Misir, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

The patrol scheduling problem is concerned with assigning security teams to different stations for distinct time intervals while respecting a limited number of contractual constraints. The objective is to minimise the total distance travelled while maximising the coverage of the stations with respect to their security requirement levels. This paper introduces a hyper-heuristic strategy focusing on generating diverse solutions for a bi-objective patrol scheduling problem. While a variety of hyper-heuristics have been applied to a large suite of problem domains usually in the form of single-objective optimisation, we suggest an alternative approach for solving the patrol scheduling problem with two …

Convergence Of A Reinforcement Learning Algorithm In Continuous Domains, Stephen Carden

All Dissertations

In the field of Reinforcement Learning, Markov Decision Processes with a finite number of states and actions have been well studied, and there exist algorithms capable of producing a sequence of policies which converge to an optimal policy with probability one. Convergence guarantees for problems with continuous states also exist. Until recently, no online algorithm for continuous states and continuous actions has been proven to produce optimal policies. This Dissertation contains the results of research into reinforcement learning algorithms for problems in which both the state and action spaces are continuous. The problems to be solved are introduced formally as …

Multi-Valued Argumentation Frameworks, Pierpaolo Dondio

Conference papers

In this paper we explore how the seminal Dung’s abstract argumentation framework can be extended to handle arguments containing gradual concepts. We allow arguments to have a degree of truth associated with them and we investigate the degree of truth to which each argument can be considered accepted, rejected and undecided by an abstract argumentation semantics. We propose a truth-compositional recursive computation, and we discuss examples using the major multi-valued logics such as Godel’s, Zadeh’s and Łukasiewicz's logic. The findings are a contribution in the field of non-monotonic approximate reasoning and they also represent a well-grounded proposal towards the introduction …

An Empirical Study Of Off-Line Configuration And On-Line Adaptation In Operator Selection, Zhi Yuan, Stephanus Daniel Handoko, Duc Thien Nguyen, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Automating the process of finding good parameter settings is important in the design of high-performing algorithms. These automatic processes can generally be categorized into off-line and on-line methods. Off-line configuration consists in learning and selecting the best setting in a training phase, and usually fixes it while solving an instance. On-line adaptation methods on the contrary vary the parameter setting adaptively during each algorithm run. In this work, we provide an empirical study of both approaches on the operator selection problem, explore the possibility of varying parameter value by a non-adaptive distribution tuned off-line, and incorporate the off-line with on-line …

Interpretable Machine Learning And Sparse Coding For Computer Vision, Will Landecker

Dissertations and Theses

Machine learning offers many powerful tools for prediction. One of these tools, the binary classifier, is often considered a black box. Although its predictions may be accurate, we might never know why the classifier made a particular prediction. In the first half of this dissertation, I review the state of the art of interpretable methods (methods for explaining why); after noting where the existing methods fall short, I propose a new method for a particular type of black box called additive networks. I offer a proof of trustworthiness for this new method (meaning a proof that my method does not …

Cenknn: A Scalable And Effective Text Classifier, Guansong Pang, Huidong Jin, Shengyi Jiang

Research Collection School Of Computing and Information Systems

A big challenge in text classification is to perform classification on a large-scale and high-dimensional text corpus in the presence of imbalanced class distributions and a large number of irrelevant or noisy term features. A number of techniques have been proposed to handle this challenge with varying degrees of success. In this paper, by combining the strengths of two widely used text classification techniques, K-Nearest-Neighbor (KNN) and centroid based (Centroid) classifiers, we propose a scalable and effective flat classifier, called CenKNN, to cope with this challenge. CenKNN projects high-dimensional (often hundreds of thousands) documents into a low-dimensional (normally a few …

Creating Autonomous Adaptive Agents In A Real-Time First-Person Shooter Computer Game, Di Wang, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

Games are good test-beds to evaluate AI methodologies. In recent years, there has been a vast amount of research dealing with real-time computer games other than the traditional board games or card games. This paper illustrates how we create agents by employing FALCON, a self-organizing neural network that performs reinforcement learning, to play a well-known first-person shooter computer game called Unreal Tournament. Rewards used for learning are either obtained from the game environment or estimated using the temporal difference learning scheme. In this way, the agents are able to acquire proper strategies and discover the effectiveness of different weapons without …

Decentralized Stochastic Planning With Anonymity In Interactions, Pradeep Varakantham, Yossiri Adulyasak, Patrick Jaillet

Research Collection School Of Computing and Information Systems

In this paper, we solve cooperative decentralized stochastic planning problems, where the interactions between agents (specified using transition and reward functions) are dependent on the number of agents (and not on the identity of the individual agents) involved in the interaction. A collision of robots in a narrow corridor, defender teams coordinating patrol activities to secure a target, etc. are examples of such anonymous interactions. Formally, we consider problems that are a subset of the well known Decentralized MDP (DEC-MDP) model, where the anonymity in interactions is specified within the joint reward and transition functions. In this paper, not only …

Building Algorithm Portfolios For Memetic Algorithms, Mustafa Misir, Stephanus Daniel Handoko, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

The present study introduces an automated mechanism to build algorithm portfolios for memetic algorithms. The objective is to determine an algorithm set involving combinations of crossover, mutation and local search operators based on their past performance. The past performance is used to cluster algorithm combinations. Top performing combinations are then considered as the members of the set. The set is expected to have algorithm combinations complementing each other with respect to their strengths in a portfolio setting. In other words, each algorithm combination should be good at solving a certain type of problem instances such that this set can be …

Decentralized Multi-Agent Reinforcement Learning In Average-Reward Dynamic Dcops, Duc Thien Nguyen, William Yeoh, Hoong Chuin Lau, Shlomo Zilberstein, Chongjie Zhang

Research Collection School Of Computing and Information Systems

Researchers have introduced the Dynamic Distributed Constraint Optimization Problem (Dynamic DCOP) formulation to model dynamically changing multi-agent coordination problems, where a dynamic DCOP is a sequence of (static canonical) DCOPs, each partially different from the DCOP preceding it. Existing work typically assumes that the problem in each time step is decoupled from the problems in other time steps, which might not hold in some applications. Therefore, in this paper, we make the following contributions: (i) We introduce a new model, called Markovian Dynamic DCOPs (MD-DCOPs), where the DCOP in the next time step is a function of the value assignments …

Reinforcement Learning For Adaptive Operator Selection In Memetic Search Applied To Quadratic Assignment Problem, Stephanus Daniel Handoko, Duc Thien Nguyen, Zhi Yuan, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Memetic search is well known as one of the state-of-the-art metaheuristics for finding high-quality solutions to NP-hard problems. Its performance is often attributable to appropriate design, including the choice of its operators. In this paper, we propose a Markov Decision Process model for the selection of crossover operators in the course of the evolutionary search. We solve the proposed model by a Q-learning method. We experimentally verify the efficacy of our proposed approach on the benchmark instances of Quadratic Assignment Problem.

Near-Optimal Nonmyopic Contact Center Planning Using Dual Decomposition, Akshat Kumar, Sudhanshu Singh, Pranav Gupta, Gyana Parija

Research Collection School Of Computing and Information Systems

We address the problem of minimizing staffing cost in a contact center subject to service level requirements over multiple weeks. We handle both the capacity planning and agent schedule generation aspect of this problem. Our work incorporates two unique business requirements. First, we develop techniques that can provide near-optimal staffing for 247 contact centers over long term, upto eight weeks, rather than planning myopically on a week-on-week basis. Second, our approach is usable in an online interactive setting in which staffing managers using our system expect high quality plans within a short time period. Results on large real world and …

Streets: Game-Theoretic Traffic Patrolling With Exploration And Exploitation, Matthew Brown, Sandhya Saisubramanian, Pradeep Varakantham, Milind Tambe

Research Collection School Of Computing and Information Systems

To dissuade reckless driving and mitigate accidents, cities deploy resources to patrol roads. In this paper, we present STREETS, an application developed for the city of Singapore, which models the problem of computing randomized traffic patrol strategies as a defenderattacker Stackelberg game. Previous work on Stackelberg security games has focused extensively on counterterrorism settings. STREETS moves beyond counterterrorism and represents the first use of Stackelberg games for traffic patrolling, in the process providing a novel algorithm for solving such games that addresses three major challenges in modeling and scale-up. First, there exists a high degree of unpredictability in travel times …

Narratives As A Fundamental Component Of Consciousness, Sandra L. Vaughan, Robert F. Mills, Michael R. Grimaila, Gilbert L. Peterson, Steven K. Rogers

Faculty Publications

In this paper, we propose a conceptual architecture that models human (spatially-temporally-modally) cohesive narrative development using a computer representation of quale properties. Qualia are proposed to be the fundamental "cognitive" components humans use to generate cohesive narratives. The engineering approach is based on cognitively inspired technologies and incorporates the novel concept of quale representation for computation of primitive cognitive components of narrative. The ultimate objective of this research is to develop an architecture that emulates the human ability to generate cohesive narratives with incomplete or perturbated information.

Automated Classification Of Argument Stance In Student Essays: A Linguistically Motivated Approach With An Application For Supporting Argument Summarization, Adam Robert Faulkner

Dissertations, Theses, and Capstone Projects

This study describes a set of document- and sentence-level classification models designed to automate the task of determining the argument stance (for or against) of a student argumentative essay and the task of identifying any arguments in the essay that provide reasons in support of that stance. A suggested application utilizing these models is presented which involves the automated extraction of a single-sentence summary of an argumentative essay. This summary sentence indicates the overall argument stance of the essay from which the sentence was extracted and provides a representative argument in support of that stance.

A novel set …

Opportunistic Service Differentiation And Cloud Resource Management In Support Of Enhanced Vehicular Applications, Mohammad Ali Salahuddin

Dissertations

An integral part of Intelligent Transportation Systems (ITS) are Vehicular Ad hoc Networks (VANETs), which consist of vehicles with on-board units (OBUs) and fixed road-side units (RSUs). Wireless Access in Vehicular Environment (WAVE) offers QoS via service differentiation by using application defined priorities. However, WAVE has unbounded delay and is oblivious to network load and severity of vehicles with respect to their environment. Our context severity metric innovatively enhances WAVE to be sensitive to vehicle and environment interactions. Our novel Opportunistic Service Differentiation (OSD) technique, dynamically readjusts the WAVE packet priorities to improve utilization of lower latency queues, prioritizing packets …

Revisiting Risk-Sensitive Mdps: New Algorithms And Results, Ping Hou, William Yeoh, Pradeep Reddy Varakantham

Research Collection School Of Computing and Information Systems

While Markov Decision Processes (MDPs) have been shown to be effective models for planning under uncertainty, theobjective to minimize the expected cumulative cost is inappropriate for high-stake planning problems. As such, Yu, Lin, and Yan (1998) introduced the Risk-Sensitive MDP (RSMDP) model, where the objective is to find a policy that maximizes the probability that the cumulative cost is within some user-defined cost threshold. In this paper, we revisit this problem and introduce new algorithms that are based on classical techniques, such as depth-first search and dynamic programming, and a recently introduced technique called Topological Value Iteration (TVI). We demonstrate …

Towards An Automated Weight Lifting Coach: Introducing Lift, Michael Andrew Lady

Master's Theses

The fitness device market is young and rapidly growing. More people than ever before take count of how many steps they walk, how many calories they burn, their heart rate over time, and even their quality of sleep. New, and as of yet, unreleased fitness devices have promised the next evolution of functionality with exercise technique analysis. These next generation of fitness devices have wrist and armband style form factors, which may not be optimal for barbell exercises such as back squat, bench press, and overhead press where a sensor on one arm may not provide the most relevant data …

Predicting Music Genre Preferences Based On Online Comments, Andrew J. Sinclair

Master's Theses

Communication Accommodation Theory (CAT) states that individuals adapt to each other’s communicative behaviors. This adaptation is called “convergence.” In this work we explore the convergence of writing styles of users of the online music distribution plat- form SoundCloud.com. In order to evaluate our system we created a corpus of over 38,000 comments retrieved from SoundCloud in April 2014. The corpus represents comments from 8 distinct musical genres: Classical, Electronic, Hip Hop, Jazz, Country, Metal, Folk, and World. Our corpus contains: short comments, frequent misspellings, little sentence struc- ture, hashtags, emoticons, and URLs. We adapt techniques used by researchers analyzing other …

Games People Play: Exploring Depaul's Top-Rated Computer Game Development Program

DePaul Magazine

In March 2014, the Princeton Review, in conjunction with PC Gamer magazine, named the top 25 schools to study game design in the United States and Canada. DePaul's undergraduate program ranked 20th, a considerable leap from 2013’s honorable mention. The graduate program came in at 12th. DePaul's strong ranking reflects the game development program's extension of its basic game development, software engineering and programming to include art, design and storytelling, as well as computer graphics technology, networking, artificial intelligence and human-computer interaction. Examples of the award-winning games developed by students and now marketed by such going concerns as Sony PlayStation …

Decentralized Multi-Agent Reinforcement Learning In Average-Reward Dynamic Dcops, Duc Thien Nguyen, William Yeoh, Hoong Chuin Lau, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Researchers have introduced the Dynamic Distributed Constraint Optimization Problem (Dynamic DCOP) formulation to model dynamically changing multi-agent coordination problems, where a dynamic DCOP is a sequence of (static canonical) DCOPs, each partially different from the DCOP preceding it. Existing work typically assumes that the problem in each time step is decoupled from the problems in other time steps, which might not hold in some applications. Therefore, in this paper, we make the following contributions: (i) We introduce a new model, called Markovian Dynamic DCOPs (MD-DCOPs), where the DCOP in the next time step is a function of the value assignments …

A Continuous Learning Strategy For Self-Organizing Maps Based On Convergence Windows, Gregory T. Breard

Senior Honors Projects

A self-organizing map (SOM) is a type of artificial neural network that has applications in a variety of fields and disciplines. The SOM algorithm uses unsupervised learning to produce a low-dimensional representation of high- dimensional data. This is done by 'fitting' a grid of nodes to a data set over a fixed number of iterations. With each iteration, the nodes of the map are adjusted so that they appear more like the data points. The low-dimensionality of the resulting map means that it can be presented graphically and be more intuitively interpreted by humans. However, it is still essential to …

Declarative-Procedural Memory Interaction In Learning Agents, Wenwen Wang, Ah-Hwee Tan, Loo-Nin Teow, Tan Yuan-Sin

Research Collection School Of Computing and Information Systems

It has been well recognized that human makes use of both declarative memory and procedural memory for decision making and problem solving. In this paper, we propose a computational model with the overall architecture and individual processes for realizing the interaction between the declarative and procedural memory based on self-organizing neural networks. We formalize two major types of memory interactions and show how each of them can be embedded into autonomous reinforcement learning agents. Our experiments based on the Toad and Frog puzzle and a strategic game known as Starcraft Broodwar have shown that the cooperative interaction between declarative knowledge …

On Understanding Diffusion Dynamics Of Patrons At A Theme Park, Jiali Du, Akshat Kumar, Pradeep Reddy Varakantham

Research Collection School Of Computing and Information Systems

In this work, we focus on the novel application of learning the diffusion dynamics of visitors among attractions at a large theme park using only aggregate information about waiting times at attractions. Main contributions include formulating optimisation models to compute diffusion dynamics. We also developed algorithm capable of dealing with noise in the data to populate parameters in the optimization model. We validated our approach using cross validation on a real theme park data set. Our approach provides an accuracy of about 80$% for popular attractions, providing solid empirical support for our diffusion models.

Mechanisms For Arranging Ride Sharing And Fare Splitting For Last-Mile Travel Demands, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

A great challenge of city planners is to provide efficient and effective connection service to travelers using public transportation system. This is commonly known as the last-mile problem and is critical in promoting the utilization of public transportation system. In this paper, we address the last-mile problem by considering a dynamic and demand-responsive mechanism for arranging ride sharing on a non-dedicated commercial fleet (such as taxis or passenger vans). Our approach has the benefits of being dynamic, flexible, and with low setup cost. A critical issue in such ride-sharing service is how riders should be grouped and serviced, and how …