Adaptive Regret Minimization In Bounded-Memory Games,
2013
Singapore Management University
Adaptive Regret Minimization In Bounded-Memory Games, Jeremiah Blocki, Nicolas Christin, Anupam Datta, Arunesh Sinha
Research Collection School Of Computing and Information Systems
Organizations that collect and use large volumes of personal information often use security audits to protect data subjects from inappropriate uses of this information by authorized insiders. In face of unknown incentives of employees, a reasonable audit strategy for the organization is one that minimizes its regret. While regret minimization has been extensively studied in repeated games, the standard notion of regret for repeated games cannot capture the complexity of the interaction between the organization (defender) and an adversary, which arises from dependence of rewards and actions on history. To account for this generality, we introduce a richer class of …
Getting It Right The First Time: Robot Mission Guarantees In The Presence Of Uncertainty,
2013
Fordham University
Getting It Right The First Time: Robot Mission Guarantees In The Presence Of Uncertainty, Damian Lyons, Ron Arkin, Paramesh Nirmal, Shu Jiang, Tsung-Ming Liu, Julia Deeb
Faculty Publications
Abstract—Certain robot missions need to perform predictably in a physical environment that may only be poorly characterized in advance. We have previously developed an approach to establishing performance guarantees for behavior-based controllers in a process-algebra framework. We extend that work here to include random variables, and we show how our prior results can be used to generate a Dynamic Bayesian Network for the coupled system of program and environment model. Verification is reduced to a filtering problem for this network. Finally, we present validation results that demonstrate the effectiveness of the verification of a multiple waypoint robot mission using this …
Symmetry Robust Descriptor For Non-Rigid Surface Matching,
2013
Singapore Management University
Symmetry Robust Descriptor For Non-Rigid Surface Matching, Zhiyuan Zhang, Kangkang Yin, Kelvin W. C. Foong
Research Collection School Of Computing and Information Systems
In this paper, we propose a novel shape descriptor that is robust in differentiating intrinsic symmetric points on geometric surfaces. Our motivation is that even the state-of-theart shape descriptors and non-rigid surface matching algorithms suffer from symmetry flips. They cannot differentiate surface points that are symmetric or near symmetric. Hence a left hand of one human model may be matched to a right hand of another. Our Symmetry Robust Descriptor (SRD) is based on a signed angle field, which can be calculated from the gradient fields of the harmonic fields of two point pairs. Experiments show that the proposed shape …
Budgeted Personalized Incentive Approaches For Smoothing Congestion In Resource Networks,
2013
Singapore Management University
Budgeted Personalized Incentive Approaches For Smoothing Congestion In Resource Networks, Pradeep Varakantham, Na Fu, William Yeoh, Shih-Fen Cheng, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
Congestion occurs when there is competition for resources by sel sh agents. In this paper, we are concerned with smoothing out congestion in a network of resources by using personalized well-timed in- centives that are subject to budget constraints. To that end, we provide: (i) a mathematical formulation that computes equilibrium for the re- source sharing congestion game with incentives and budget constraints; (ii) an integrated approach that scales to larger problems by exploiting the factored network structure and approximating the attained equilib- rium; (iii) an iterative best response algorithm for solving the uncon- strained version (no budget) of the …
Optimization Approaches For Solving Chance Constrained Stochastic Orienteering Problems,
2013
Singapore Management University
Optimization Approaches For Solving Chance Constrained Stochastic Orienteering Problems, Pradeep Varakantham, Akshat Kumar
Research Collection School Of Computing and Information Systems
Orienteering problems (OPs) are typically used to model routing and trip planning problems. OP is a variant of the well known traveling salesman problem where the goal is to compute the highest reward path that includes a subset of nodes and has an overall travel time less than the specified deadline. Stochastic orienteering problems (SOPs) extend OPs to account for uncertain travel times and are significantly harder to solve than deterministic OPs. In this paper, we contribute a scalable mixed integer LP formulation for solving risk aware SOPs, which is a principled approximation of the underlying stochastic optimization problem. Empirically, …
Genetic Algorithm Based Model In Text Steganography,
2013
University of Nairobi
Genetic Algorithm Based Model In Text Steganography, Christine K. Mulunda, Peter W. Wagacha, Alfayo O. Adede
The African Journal of Information Systems
Steganography is an ancient art. It is used for security in open systems. It focuses on hiding secret messages inside a cover medium. The most important property of a cover medium is the amount of data that can be stored inside it without changing its noticeable properties. There are many sophisticated techniques with which to hide, analyze, and recover that hidden information. This paper discusses an exploration in the use of Genetic Algorithm operators on the cover medium. We worked with text as the cover medium with the aim of increasing robustness and capacity of hidden data. Elitism is used …
Computing The Grounded Semantics In All The Subgraphs Of An Argumentation Framework: An Empirical Evaluation,
2013
Technological University Dublin
Computing The Grounded Semantics In All The Subgraphs Of An Argumentation Framework: An Empirical Evaluation, Pierpaolo Dondio
Articles
Given an argumentation framework – with a finite set of arguments and the attack relation identifying the graph – we study how the grounded labelling of a generic argument a varies in all the subgraphs of . Since this is an intractable problem of above-polynomial complexity, we present two non-naïve algorithms to find the set of all the subgraphs where the grounded semantic assigns to argument a specific label . We report the results of a series of empirical tests over graphs of increasing complexity. The value of researching the above problem is two-fold. First, knowing how an argument behaves …
An Analysis Of Post-Selection In Automatic Configuration,
2013
Singapore Management University
An Analysis Of Post-Selection In Automatic Configuration, Zhi Yuan, Thomas St\303\274tzle, Marco A. Montes De Oca, Hoong Chuin Lau, Mauro Birattari
Research Collection School Of Computing and Information Systems
Automated algorithm configuration methods have proven to be instrumental in deriving high-performing algorithms and such methods are increasingly often used to configure evolutionary algorithms. One major challenge in devising automatic algorithm configuration techniques is to handle the inherent stochasticity in the configuration problems. This article analyses a post-selection mechanism that can also be used for this task. The central idea of the post-selection mechanism is to generate in a first phase a set of high-quality candidate algorithm configurations and then to select in a second phase from this candidate set the (statistically) best configuration. Our analysis of this mechanism indicates …
Audit Games,
2013
Singapore Management University
Audit Games, Jeremiah Blocki, Nicolas Christin, Anupam Datta, Ariel D. Procaccia, Arunesh Sinha
Research Collection School Of Computing and Information Systems
Effective enforcement of laws and policies requires expending resources to prevent and detect offenders, as well as appropriate punishment schemes to deter violators. In particular, enforcement of privacy laws and policies in modern organizations that hold large volumes of personal information (e.g., hospitals, banks) relies heavily on internal audit mechanisms. We study economic considerations in the design of these mechanisms, focusing in particular on effective resource allocation and appropriate punishment schemes. We present an audit game model that is a natural generalization of a standard security game model for resource allocation with an additional punishment parameter. Computing the Stackelberg equilibrium …
Traveltant: Social Interaction Based Personalized Recommendation System,
2013
University of Arkansas, Fayetteville
Traveltant: Social Interaction Based Personalized Recommendation System, Sultan Dawood Alfarhood
Graduate Theses and Dissertations
Trip planning is a time consuming task that most people do before going to any destination. Traveltant is an intelligent system that analyzes a user's Social network and suggests a complete trip plan detailed for every single day based on the user's interests extracted from the Social network. Traveltant also considers the interests of friends the user interacts with most by building a ranked friends list of interactivity, and then uses the interests of those people in this list to enrich the recommendation results. Traveltant provides a smooth user interface through a Windows Phone 7 application while doing most of …
Gesture-Based Robot Path Shaping,
2013
Clemson University
Gesture-Based Robot Path Shaping, Paul Yanik
All Dissertations
For many individuals, aging is frequently associated with diminished mobility and dexterity. Such decreases may be accompanied by a loss of independence, increased burden to caregivers, or institutionalization. It is foreseen that the ability to retain independence and quality of life as one ages will increasingly depend on environmental sensing and robotics which facilitate aging in place. The development of ubiquitous sensing strategies in the home underpins the promise of adaptive services, assistive robotics, and architectural design which would support a person's ability to live independently as they age. Instrumentation (sensors and processing) which is capable of recognizing the actions …
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 …
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 …
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, …
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 …
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.
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 …
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 …
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 …
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 …
