Scalable Randomized Patrolling For Securing Rapid Transit Networks,
2013
Singapore Management University
Scalable Randomized Patrolling For Securing Rapid Transit Networks, Pradeep Varakantham, Hoong Chuin Lau, Zhi Yuan
Research Collection School Of Computing and Information Systems
Mass Rapid Transit using rail is a popular mode of transport employed by millions of people in many urban cities across the world. Typically, these networks are massive, used by many and thus, can be a soft target for criminals. In this paper, we consider the problem of scheduling randomised patrols for improving security of such rail networks. Similar to existing work in randomised patrols for protecting critical infrastructure, we also employ Stackelberg Games to represent the problem. In solving the Stackelberg games for massive rail networks, we make two key contributions. Firstly, we provide an approach called RaPtoR for …
Flotra: Flower-Shape Trajectory Mining For Instance-Specific Parameter Tuning,
2013
Singapore Management University
Flotra: Flower-Shape Trajectory Mining For Instance-Specific Parameter Tuning, Lindawati Lindawati, Feida Zhu, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
The performance of a heuristic algorithm is highly dependent on its parameter configuration, yet finding a good parameter configuration is often a time-consuming task. In this paper we propose FloTra, a Flower graph mining for graph search Trajectory pattern extraction for generic instance-specific automated parameter tuning. This algorithm provides efficient extraction of compact and discriminative features of the search trajectory, upon which problem instances are clustered and the corresponding optimal parameter configurations are computed. Experimental evaluations of our approach on the Quadratic Assignment Problem (QAP) show that our approach offers promising improvement over existing parameter tuning algorithms. In this work, …
Multi-Agent Orienteering Problem With Time-Dependent Capacity Constraints,
2013
Singapore Management University
Multi-Agent Orienteering Problem With Time-Dependent Capacity Constraints, Cen Chen, Shih-Fen Cheng, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
The Orienteering Problem (OP), as originally defined by Tsiligirides, is the problem of cross-countr sport in which participants get rewards from visiting a predefined set of checkpoints. As Orienteering Problem can be used to describe a wide variety of real-world problems like route planning for facility inspection, patrolling of strategic location, and reward-weighted traveling salesman problem, it has attracted continuous interests from researchers and a large number of variants and corresponding algorithms for solving them have been introduced.
“Network-Theoretic” Queuing Delay Estimation In Theme Park Attractions,
2013
Singapore Management University
“Network-Theoretic” Queuing Delay Estimation In Theme Park Attractions, Ajay Aravamudhan, Archan Misra, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
Queuing is a common phenomenon in theme parks which negatively affects visitor experience and revenue yields. There is thus a need for park operators to infer the real queuing delays without expensive investment in human effort or complex tracking infrastructure. In this paper, we depart from the classical queuing theory approach and provide a data-driven and online approach for estimating the time-varying queuing delays experienced at different attractions in a theme park. This work is novel in that it relies purely on empirical observations of the entry time of individual visitors at different attractions, and also accommodates the reality that …
Improving Patient Length-Of-Stay In Emergency Department Through Dynamic Resource Allocation Policies,
2013
Singapore Management University
Improving Patient Length-Of-Stay In Emergency Department Through Dynamic Resource Allocation Policies, Kar Way Tan, Wei Hao Tan, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
In this work, we consider the problem of allocating doctors in the ambulatory area of a hospital's emergency department (ED) based on a set of policies. Traditional staffing methods are static, hence do not react well to surges in patient demands. We study strategies that intelligently adjust the number of doctors based on current and historical information about the patient arrival. Our main contribution is our proposed data-driven online approach that performs adaptive allocation by utilizing historical as well as current arrivals by running symbiotic simulation in real-time. We build a simulation prototype that models ED process that is close …
A Multi-Objective Memetic Algorithm For Vehicle Resource Allocation In Sustainable Transportation Planning,
2013
Singapore Management University
A Multi-Objective Memetic Algorithm For Vehicle Resource Allocation In Sustainable Transportation Planning, Hoong Chuin Lau, Lucas Agussurja, Shih-Fen Cheng, Pang Jin Tan
Research Collection School Of Computing and Information Systems
Sustainable supply chain management has been an increasingly important topic of research in recent years. At the strategic level, there are computational models which study supply and distribution networks with environmental considerations. At the operational level, there are, for example, routing and scheduling models which are constrained by carbon emissions. Our paper explores work in tactical planning with regards to vehicle resource allocation from distribution centers to customer locations in a multi-echelon logistics network. We formulate the bi-objective optimization problem exactly and design a memetic algorithm to efficiently derive an approximate Pareto front. We illustrate the applicability of our approach …
Interacting Knapsack Problem In Designing Resource Bundles,
2013
Singapore Management University
Interacting Knapsack Problem In Designing Resource Bundles, Truong Huy D. Nguyen, Pradeep Reddy Varakantham, Hoong Chuin Lau, Shih-Fen Cheng
Research Collection School Of Computing and Information Systems
In many real-life businesses, the service provider/seller keeps a log of the visitors’ behavior as a way to assess the efficiency of the current business/operation model and find room for improvement. For example, by tracking when visitors entering attractions in a theme park, theme park owners can detect when and where congestion may occur, thus having contingency plans to reroute the visitors accordingly. Similarly, a Cable TV service provider can track channel switching events at each household to identify uninteresting channels. Subsequently, the repertoire of channels up for subscription can evolve over time to better serve the entertainment demand of …
Self-Organizing Cognitive Models For Virtual Agents,
2013
Singapore Management University
Self-Organizing Cognitive Models For Virtual Agents, Yilin Kang, Ah-Hwee Tan
Research Collection School Of Computing and Information Systems
Three key requirements of realistic characters or agents in virtual world can be identified as autonomy, interactivity, and personification. Working towards these challenges, this paper proposes a brain inspired agent architecture that integrates goal-directed autonomy, natural language interaction and human-like personification. Based on self-organizing neural models, the agent architecture maintains explicit mental representation of desires, intention, personalities, self-awareness, situation awareness and user awareness. Autonomous behaviors are generated via evaluating the current situation with active goals and learning the most appropriate social or goal-directed rule from the available knowledge, in accordance with the personality of each individual agent. We have built …
Parameter Learning For Latent Network Diffusion,
2013
University of Massachusetts Amherst
Parameter Learning For Latent Network Diffusion, Xiaojian Wu, Akshat Kumar, Daniel Sheldon, Shlomo Zilberstein
Research Collection School Of Computing and Information Systems
Diffusion processes in networks are increasingly used to model dynamic phenomena such as the spread of information, wildlife, or social influence. Our work addresses the problem of learning the underlying parameters that govern such a diffusion process by observing the time at which nodes become active. A key advantage of our approach is that, unlike previous work, it can tolerate missing observations for some nodes in the diffusion process. Having incomplete observations is characteristic of offline networks used to model the spread of wildlife. We develop an EM algorithm to address parameter learning in such settings. Since both the E …
Automated Generation Of Interaction Graphs For Value-Factored Decentralized Pomdps,
2013
New Mexico State University
Automated Generation Of Interaction Graphs For Value-Factored Decentralized Pomdps, William Yeoh, Akshat Kumar, Shlomo Zilberstein
Research Collection School Of Computing and Information Systems
The Decentralized Partially Observable Markov Decision Process (Dec-POMDP) is a powerful model for multi-agent planning under uncertainty, but its applicability is hindered by its high complexity – solving Dec-POMDPs optimally is NEXP-hard. Recently, Kumar et al. introduced the Value Factorization (VF) framework, which exploits decomposable value functions that can be factored into subfunctions. This framework has been shown to be a generalization of several specialized models such as TI-Dec-MDPs, ND-POMDPs and TD-POMDPs, which leverage different forms of sparse agent interactions to improve the scalability of planning. Existing algorithms for these models assume that the interaction graph of the problem is …
Collective Diffusion Over Networks: Models And Inference,
2013
Singapore Management University
Collective Diffusion Over Networks: Models And Inference, Akshat Kumar, Daniel Sheldon, Biplav Srivastava
Research Collection School Of Computing and Information Systems
Diffusion processes in networks are increasingly used to model the spread of information and social influence. In several applications in computational sustainability such as the spread of wildlife, infectious diseases and traffic mobility pattern, the observed data often consists of only aggregate information. In this work, we present new models that generalize standard diffusion processes to such collective settings. We also present optimization based techniques that can accurately learn the underlying dynamics of the given contagion process, including the hidden network structure, by only observing the time a node becomes active and the associated aggregate information. Empirically, our technique is …
Tesla: An Extended Study Of An Energy-Saving Agent That Leverages Schedule Flexibility,
2013
University of Southern California
Tesla: An Extended Study Of An Energy-Saving Agent That Leverages Schedule Flexibility, Jun Young Kwak, Pradeep Varakantham, Rajiv Maheswaran, Milind Tambe, Burcin Becerik-Gerber
Research Collection School Of Computing and Information Systems
This paper presents transformative energy-saving schedule-leveraging agent (TESLA), an agent for optimizing energy usage in commercial buildings. TESLA’s key insight is that adding flexibility to event/meeting schedules can lead to significant energy savings. This paper provides four key contributions: (i) online scheduling algorithms, which are at the heart of TESLA, to solve a stochastic mixed integer linear program for energy-efficient scheduling of incrementally/dynamically arriving meetings and events; (ii) an algorithm to effectively identify key meetings that lead to significant energy savings by adjusting their flexibility; (iii) an extensive analysis on energy savings achieved by TESLA; and (iv) surveys of real …
Machines And The Moral Community,
2013
Ohio Northern University
Machines And The Moral Community, Erica L. Neely
Philosophy and Religion Faculty Scholarship
A key distinction in ethics is between members and nonmembers of the moral community. Over time, our notion of this community has expanded as we have moved from a rationality criterion to a sentience criterion for membership. I argue that a sentience criterion is insufficient to accommodate all members of the moral community; the true underlying criterion can be understood in terms of whether a being has interests. This may be extended to conscious, self-aware machines, as well as to any autonomous intelligent machines. Such machines exhibit an ability to formulate desires for the course of their own existence; this …
Understanding Sequential Decisions Via Inverse Reinforcement Learning,
2013
Carnegie Mellon University
Understanding Sequential Decisions Via Inverse Reinforcement Learning, Siyuan Liu, Miguel Araujo, Emma Brunskill, Rosaldo Rossetti, Joao Barros, Ramayya Krishnan
Research Collection School Of Computing and Information Systems
The execution of an agent's complex activities, comprising sequences of simpler actions, sometimes leads to the clash of conflicting functions that must be optimized. These functions represent satisfaction, short-term as well as long-term objectives, costs and individual preferences. The way that these functions are weighted is usually unknown even to the decision maker. But if we were able to understand the individual motivations and compare such motivations among individuals, then we would be able to actively change the environment so as to increase satisfaction and/or improve performance. In this work, we approach the problem of providing highlevel and intelligible descriptions …
Approximate Inference In Collective Graphical Models,
2013
University of Massachusetts Amherst
Approximate Inference In Collective Graphical Models, Daniel Sheldon, Tao Sun, Akshat Kumar, Thomas G. Dietterich
Research Collection School Of Computing and Information Systems
We study the problem of approximate inference in collective graphical models (CGMs), which were recently introduced to model the problem of learning and inference with noisy aggregate observations. We first analyze the complexity of inference in CGMs: unlike inference in conventional graphical models, exact inference in CGMs is NP-hard even for tree-structured models. We then develop a tractable convex approximation to the NP-hard MAP inference problem in CGMs, and show how to use MAP inference for approximate marginal inference within the EM framework. We demonstrate empirically that these approximation techniques can reduce the computational cost of inference by two orders …
Misheard Me Oronyminator: Using Oronyms To Validate The Correctness Of Frequency Dictionaries,
2013
California Polytechnic State University, San Luis Obispo
Misheard Me Oronyminator: Using Oronyms To Validate The Correctness Of Frequency Dictionaries, Jennifer G. Hughes
Master's Theses
In the field of speech recognition, an algorithm must learn to tell the difference between "a nice rock" and "a gneiss rock". These identical-sounding phrases are called oronyms. Word frequency dictionaries are often used by speech recognition systems to help resolve phonetic sequences with more than one possible orthographic phrase interpretation, by looking up which oronym of the root phonetic sequence contains the most-common words.
Our paper demonstrates a technique used to validate word frequency dictionary values. We chose to use frequency values from the UNISYN dictionary, which tallies each word on a per-occurance basis, using a proprietary text corpus, …
A Generic Decision Making Framework For Autonomous Systems,
2013
California Polytechnic State University, San Luis Obispo
A Generic Decision Making Framework For Autonomous Systems, Connor Lange
Master's Theses
With the rising popularity of small satellites, such as CubeSats, many smaller institutions previously incapable of developing and deploying a spacecraft have starting to do so. Institutions with a history of space flight, such as NASA JPL, have begun to put projects on CubeSats that would normally fly on much larger satellites. As a result, the institutions with space flight heritage have begun to port spacecraft software that was previously designed for much larger and more complex satellites to the CubeSat platform. Unfortunately for universities, who are the majority of all institutions devel- oping CubeSats, these ported systems are too …
Iterative Statistical Verification Of Probabilistic Plans,
2013
Lawrence University
Iterative Statistical Verification Of Probabilistic Plans, Colin M. Potts
Lawrence University Honors Projects
Artificial intelligence seeks to create intelligent agents. An agent can be anything: an autopilot, a self-driving car, a robot, a person, or even an anti-virus system. While the current state-of-the-art may not achieve intelligence (a rather dubious thing to quantify) it certainly achieves a sense of autonomy. A key aspect of an autonomous system is its ability to maintain and guarantee safety—defined as avoiding some set of undesired outcomes. The piece of software responsible for this is called a planner, which is essentially an automated problem solver. An advantage computer planners have over humans is their ability to consider and …
Modeling A Sensor To Improve Its Efficacy,
2013
University of Texas at Dallas
Modeling A Sensor To Improve Its Efficacy, Nabin K. Malakar, Daniil Gladkov, Kevin H. Knuth
Physics Faculty Scholarship
Robots rely on sensors to provide them with information about their surroundings. However, high-quality sensors can be extremely expensive and cost-prohibitive. Thus many robotic systems must make due with lower-quality sensors. Here we demonstrate via a case study how modeling a sensor can improve its efficacy when employed within a Bayesian inferential framework. As a test bed we employ a robotic arm that is designed to autonomously take its own measurements using an inexpensive LEGO light sensor to estimate the position and radius of a white circle on a black field. The light sensor integrates the light arriving from a …
Practical Tractability Of Csps By Higher Level Consistency And Tree Decomposition,
2013
University of Nebraska-Lincoln
Practical Tractability Of Csps By Higher Level Consistency And Tree Decomposition, Shant Karakashian
School of Computing: Dissertations, Theses, and Student Research
Constraint Satisfaction is a flexible paradigm for modeling many decision problems in Engineering, Computer Science, and Management. Constraint Satisfaction Problems (CSPs) are in general NP-complete and are usually solved with search. Research has identified various islands of tractability, which enable solving certain CSPs with backtrack-free search. For example, one sufficient condition for tractability relates the consistency level of a CSP to treewidth of the CSP's constraint network. However, enforcing higher levels of consistency on a CSP may require the addition of constraints, thus altering the topology of the constraint network and increasing its treewidth. This thesis addresses the following question: …
