Operations Research, Systems Engineering and Industrial Engineering Commons^™

Designing Bus Transit Services For Routine Crowd Situations At Large Event Venues, Jianli Du, Shih-Fen Cheng, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We are concerned with the routine crowd management problem after a major event at a known venue. Without properly design complementary transport services, such sudden crowd build-ups will overwhelm the existing infrastructure. In this paper, we introduce a novel flow-rate based model to model the dynamic movement of passengers over the transportation flow network. Based on this basic model, an integer linear programming model is proposed to solve the bus transit problem permanently. We validate our model against a real scenario in Singapore, where a newly constructed mega-stadium hosts various large events regularly. The results show that the proposed approach …

Ad-Hoc Automated Teller Machine Failure Forecast And Field Service Optimization, Michelle L. F. Cheong, Ping Shung Koo, B. Chandra Babu

Research Collection School Of Computing and Information Systems

As part of its overall effort to maintain good customer service while managing operational efficiency and reducing cost, a bank in Singapore has embarked on using data and decision analytics methodologies to perform better ad-hoc ATM failure forecasting and plan the field service engineers to repair the machines. We propose using a combined Data and Decision Analytics Framework which helps the analyst to first understand the business problem by collecting, preparing and exploring data to gain business insights, before proposing what objectives and solutions can and should be done to solve the problem. This paper reports the work in analyzing …

Probabilistic Inference Based Message-Passing For Resource Constrained Dcops, Supriyo Ghosh, Akshat Kumar, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Distributed constraint optimization (DCOP) is an important framework for coordinated multiagent decision making. We address a practically useful variant of DCOP, called resource-constrained DCOP (RC-DCOP), which takes into account agents’ consumption of shared limited resources. We present a promising new class of algorithm for RC-DCOPs by translating the underlying co- ordination problem to probabilistic inference. Using inference techniques such as expectation- maximization and convex optimization machinery, we develop a novel convergent message-passing algorithm for RC-DCOPs. Experiments on standard benchmarks show that our approach provides better quality than previous best DCOP algorithms and has much lower failure rate. Comparisons against an …

Retail Precinct Management: A Case Of Commercial Decentralization In Singapore, Robert De Souza, Hoong Chuin Lau, Mark Goh, Lindawati, Wee-Siong Ng, Puay-Siew Tan

Research Collection School Of Computing and Information Systems

The synchronized last mile logistics concept seeks to address, through coordinated collaboration, several challenges that hinder reliability, cost efficiency, effective resource planning, scheduling and utilization; and increasingly, sustainability objectives. Subsequently, the meeting of service level and contractual commitments are competitively impacted with any loss of efficiency. These challenges, against a backdrop of Singapore, can essentially be addressed in selected industry sectors through a better understanding of logistics structures; innovative supply chain designs and coordination of services, operations and processes coupled with concerted policies and supply chain strategies.

History-Based Controller Design And Optimization For Partially Observable Mdps, Akshat Kumar, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Partially observable MDPs provide an elegant framework forsequential decision making. Finite-state controllers (FSCs) are often used to represent policies for infinite-horizon problems as they offer a compact representation, simple-to-execute plans, and adjustable tradeoff between computational complexityand policy size. We develop novel connections between optimizing FSCs for POMDPs and the dual linear programfor MDPs. Building on that, we present a dual mixed integer linear program (MIP) for optimizing FSCs. To assign well-defined meaning to FSC nodes as well as aid in policy search, we show how to associate history-based features with each FSC node. Using this representation, we address another challenging …

Direct: A Scalable Approach For Route Guidance In Selfish Orienteering Problems, Pradeep Varakantham, Hala Mostafa, Na Fu, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We address the problem of crowd congestion at venues like theme parks, museums and world expos by providing route guidance to multiple selfish users (with budget constraints) moving through the venue simultaneously. To represent these settings, we introduce the Selfish Orienteering Problem (SeOP) that combines two well studied problems from literature, namely Orienteering Problem (OP) and Selfish Routing (SR). OP is a single agent routing problem where the goal is to minimize latency (or maximize reward) in traversing a subset of nodes while respecting budget constraints. SR is a game between selfish agents looking for minimum latency routes from source …

Near-Optimal Decentralized Power Supply Restoration In Smart Grids, Pritee Agrawal, Akshat Kumar, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Next generation of smart grids face a number of challenges including co-generation from intermittent renewable power sources, a shift away from monolithic control due to increased market deregulation, and robust operation in the face of disasters. Such heterogeneous nature and high operational readiness requirement of smart grids necessitates decentralized control for critical tasks such as power supply restoration (PSR) after line failures. We present a novel multiagent system based approach for PSR using Lagrangian dual decomposition. Our approach works on general graphs, provides provable quality-bounds and requires only local message-passing among different connected sub-regions of a smart grid, enabling decentralized …

Predicting Bundles Of Spatial Locations From Learning Revealed Preference Data, Truc Viet Le, Siyuan Liu, Hoong Chuin Lau, Ramayya Krishnan

Research Collection School Of Computing and Information Systems

We propose the problem of predicting a bundle of goods, where the goods considered is a set of spatial locations that an agent wishes to visit. This typically arises in the tourism setting where attractions can often be bundled and sold as a package to visitors. While the problem of predicting future locations given the current and past trajectories is well-established, we take a radical approach by looking at it from an economic point of view. We view an agent's past trajectories as revealed preference (RP) data, where the choice of locations is a solution to an optimisation problem according …

Improving Product Design Phase For Engineer To Order (Eto) Product With Knowledge Base Engineering (Kbe), Hanhdung Thi Dinh

Open Access Theses

In industry currently Computer Aided Design (CAD) is an important tool for the modification, analysis, or optimization of the 3D virtual environment that replicates the physical product. CAD software is an efficient and reliable tool. However, as globalization increases customer demands, this process needs to be faster and more efficient to accommodate changing product design situations, especially for Engineer-to- Order (ETO) products. ^ The traditional method of product design process is to operate CAD software without argumentation. Design engineers create CAD prototypes and drawings based on available knowledge and information which comes from engineering experts, company standards, industrial practices as …

Quantum Inspired Algorithms For Learning And Control Of Stochastic Systems, Karthikeyan Rajagopal

Doctoral Dissertations

"Motivated by the limitations of the current reinforcement learning and optimal control techniques, this dissertation proposes quantum theory inspired algorithms for learning and control of both single-agent and multi-agent stochastic systems.

A common problem encountered in traditional reinforcement learning techniques is the exploration-exploitation trade-off. To address the above issue an action selection procedure inspired by a quantum search algorithm called Grover's iteration is developed. This procedure does not require an explicit design parameter to specify the relative frequency of explorative/exploitative actions.

The second part of this dissertation extends the powerful adaptive critic design methodology to solve finite horizon stochastic optimal …

Designing A Portfolio Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir

Research Collection School Of Computing and Information Systems

Algorithm portfolios seek to determine an effective set of algorithms that can be used within an algorithm selection framework to solve problems. A limited number of these portfolio studies focus on generating different versions of a target algorithm using different parameter configurations. In this paper, we employ a Design of Experiments (DOE) approach to determine a promising range of values for each parameter of an algorithm. These ranges are further processed to determine a portfolio of parameter configurations, which would be used within two online Algorithm Selection approaches for solving different instances of a given combinatorial optimization problem effectively. We …

Second Order-Response Surface Model For The Automated Parameter Tuning Problem, Aldy Gunawan, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Several automated parameter tuning procedures/configurators have been proposed in order to find the best parameter setting for a target algorithm. These configurators can generally be classified into model-free and model-based approaches. We introduce a recent approach which is based on the hybridization of both approaches. It combines the Design of Experiments (DOE) and Response Surface Methodology (RSM) with prevailing model-free techniques. DOE is mainly used for determining the importance of parameters. A First Order-RSM is initially employed to define the promising region for the important parameters. A Second Order-RSM is then built to approximate the center point as well as …

Traccs: Trajectory-Aware Coordinated Urban Crowd-Sourcing, Cen Chen, Shih-Fen Cheng, Aldy Gunawan, Archan Misra, Koustuv Dasgupta, Deepthi Chander

Research Collection School Of Computing and Information Systems

We investigate the problem of large-scale mobile crowd-tasking, where a large pool of citizen crowd-workers are used to perform a variety of location-specific urban logistics tasks. Current approaches to such mobile crowd-tasking are very decentralized: a crowd-tasking platform usually provides each worker a set of available tasks close to the worker's current location; each worker then independently chooses which tasks she wants to accept and perform. In contrast, we propose TRACCS, a more coordinated task assignment approach, where the crowd-tasking platform assigns a sequence of tasks to each worker, taking into account their expected location trajectory over a wider time …

Hippi Care Hospital: Towards Proactive Business Processes In Emergency Room Services, Kar Way Tan, Venky Shankaraman

Research Collection School Of Computing and Information Systems

It was 2.35 am on a Saturday morning. Wiki Lim, process specialist from the Process Innovation Centre (PIC) of Hippi Care Hospital (HCH), desperately doodling on her notepad for ideas to improve service delivery at HCH’s Emergency Department (ED). HCH has committed to the public that its ED would meet the service quality criterion of serving 90% of A3 and A4 patients, non-emergency patients with moderate to mild symptoms, within 90 minutes of their arrival at the ED. The ED was not able to meet this performance goal and Dr. Edward Kim, the head of the ED at HCH, had …

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

In this paper, we formulate and study the Multi-agent Orienteering Problem with Time-dependent Capacity Constraints (MOPTCC). MOPTCC is similar to the classical orienteering problem at single-agent level: given a limited time budget, an agent travels around the network and collects rewards by visiting different nodes, with the objective of maximizing the sum of his collected rewards. The most important feature we introduce in MOPTCC is the inclusion of multiple competing agents. All agents in MOPTCC are assumed to be self-interested, and they interact with each other when arrive at certain nodes simultaneously. As all nodes are capacitated, if a particular …

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 …

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 …

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 …

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.

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 …

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 …

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 …

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.

A Quantitative Analysis Of Decision Process In Social Groups Using Human Trajectories, Truc Viet Le, Siyuan Liu, Hoong Chuin Lau, Ramayya Krishnan

Research Collection School Of Computing and Information Systems

A group's collective action is an outcome of the group's decision-making process, which may be reached by either averaging of the individual preferences or following the choices of certain members in the group. Our problem here is to decide which decision process the group has adopted given the data of the collective actions. We propose a generic statistical framework to infer the group's decision process from the spatio-temporal data of group trajectories, where each "trajectory" is a sequence of group actions. This is achieved by systematically comparing each agent type's influence on the group actions based on an array of …

Building Thinc: User Incentivization And Meeting Rescheduling For Energy Savings, Jun Young Kwak, Debarun Kar, William Haskell, Pradeep Reddy Varakantham, Milind Tambe

Research Collection School Of Computing and Information Systems

This paper presents THINC, an agent developed for saving energy in real-world commercial buildings. While previous work has presented techniques for computing energy-efficient schedules, it fails to address two issues, centered on human users, that are essential in real-world agent deployments: (i) incentivizing users for their energy saving activities and (ii) interacting with users to reschedule key “energy-consuming” meetings in a timely fashion, while handling the uncertainty in such interactions. THINC addresses these shortcomings by providing four new major contributions. First, THINC computes fair division of credits from energy savings. For this fair division, THINC provides novel algorithmic advances for …

Strategic Decision Support System Using Heuristic Algorithm For Practical Outlet Zones Allocation To Dealers In A Beer Supply Distribution Network, Michelle Lee Fong Cheong

Research Collection School Of Computing and Information Systems

We consider a two-echelon beer supply distribution network with the brewer replenishing the dealers and the dealers serving the outlet zones directly, for multiple product types. The allocation of the outlet zones to the dealers will determine the quantity of products the brewer replenishes each dealer, which will in turn impact the total warehousing and transportation costs. The non-linear optimization model formulated is difficult to solve to optimality, and the model itself does not include practical business considerations in the distribution business. A heuristics algorithm is designed and easily implemented using spreadsheets with Visual Basic programming to effectively and efficiently …

Risk Minimization Of Disjunctive Temporal Problem With Uncertainty, Hoong Chuin Lau, Tuan Anh Hoang

Research Collection School Of Computing and Information Systems

The Disjunctive Temporal Problem with Uncertainty (DTPU) is a fundamental problem that expresses temporal reasoning with both disjunctive constraints and contingency. A recent work (Peintner et al, 2007) develops a complete algorithm for determining Strong Controlla- bility of a DTPU. Such a notion that guarantees 100% confidence of execution may be too conservative in practice. In this paper, following the idea of (Tsamardinos 2002), we are interested to find a schedule that minimizes the risk (i.e. probability of failure) of executing a DTPU. We present a problem decomposition scheme that enables us to compute the probability of failure efficiently, followed …