Operations Research, Systems Engineering and Industrial Engineering Commons^™

Toward Large-Scale Agent Guidance In An Urban Taxi Service, Agussurja Lucas, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Empty taxi cruising represents a wastage of resources in the context of urban taxi services. In this work, we seek to minimize such wastage. An analysis of a large trace of taxi operations reveals that the services’ inefficiency is caused by drivers’ greedy cruising behavior. We model the existing system as a continuous time Markov chain. To address the problem, we propose that each taxi be equipped with an intelligent agent that will guide the driver when cruising for passengers. Then, drawing from AI literature on multiagent planning, we explore two possible ways to compute such guidance. The first formulation …

Logistics Orchestration Modeling And Evaluation For Humanitarian Relief, Hoong Chuin Lau, Zhengping Li, Xin Du, Heng Jiang, Robert De Souza

Research Collection School Of Computing and Information Systems

This paper proposes an orchestration model for post-disaster response that is aimed at automating the coordination of scarce resources that minimizes the loss of human lives. In our setting, different teams are treated as agents and their activities are "orchestrated" to optimize rescue performance. Results from simulation are analysed to evaluate the performance of the optimization model.

Incorporating Memory And Learning Mechanisms Into Meta-Raps, Arif Arin

Engineering Management & Systems Engineering Theses & Dissertations

Due to the rapid increase of dimensions and complexity of real life problems, it has become more difficult to find optimal solutions using only exact mathematical methods. The need to find near-optimal solutions in an acceptable amount of time is a challenge when developing more sophisticated approaches. A proper answer to this challenge can be through the implementation of metaheuristic approaches. However, a more powerful answer might be reached by incorporating intelligence into metaheuristics.

Meta-RaPS (Metaheuristic for Randomized Priority Search) is a metaheuristic that creates high quality solutions for discrete optimization problems. It is proposed that incorporating memory and learning …

Decision Support For Agent Populations In Uncertain And Congested Environments, Pradeep Reddy Varakantham, Shih-Fen Cheng, Geoff Gordon, Asrar Ahmed

Research Collection School Of Computing and Information Systems

This research is motivated by large scale problems in urban transportation and labor mobility where there is congestion for resources and uncertainty in movement. In such domains, even though the individual agents do not have an identity of their own and do not explicitly interact with other agents, they effect other agents. While there has been much research in handling such implicit effects, it has primarily assumed deterministic movements of agents. We address the issue of decision support for individual agents that are identical and have involuntary movements in dynamic environments. For instance, in a taxi fleet serving a city, …

Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoff Gordon, Pradeep Reddy Varakantham, William Yeoh, Ajay Srinivasan, Hoong Chuin Lau, Shih-Fen Cheng

Research Collection School Of Computing and Information Systems

Multi-agent planning is a well-studied problem with applications in various areas. Due to computational constraints, existing research typically focuses either on unstructured domains with many agents, where we are content with heuristic solutions, or domains with small numbers of agents or special structure, where we can find provably near-optimal solutions. In contrast, here we focus on provably near-optimal solutions in domains with many agents, by exploiting influence limits. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs; (b) a proof of …

Stochastic Dominance In Stochastic Dcops For Risk-Sensitive Applications, Nguyen Duc Thien, William Yeoh, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems where the primary interactions are between local subsets of agents. However, one limitation of DCOPs is the assumption that the constraint rewards are without uncertainty. Researchers have thus extended DCOPs to Stochastic DCOPs (SDCOPs), where rewards are sampled from known probability distribution reward functions, and introduced algorithms to find solutions with the largest expected reward. Unfortunately, such a solution might be very risky, that is, very likely to result in a poor reward. Thus, in this paper, we make three contributions: (1) we propose a stricter objective for …

Delayed Observation Planning In Partially Observable Domains, Pradeep Reddy Varakantham, Janusz Marecki

Research Collection School Of Computing and Information Systems

Traditional models for planning under uncertainty such as Markov Decision Processes (MDPs) or Partially Observable MDPs (POMDPs) assume that the observations about the results of agent actions are instantly available to the agent. In so doing, they are no longer applicable to domains where observations are received with delays caused by temporary unavailability of information (e.g. delayed response of the market to a new product). To that end, we make the following key contributions towards solving Delayed observation POMDPs (D-POMDPs): (i) We first provide an parameterized approximate algorithm for solving D-POMDPs efficiently, with desired accuracy; and (ii) We then propose …

Prioritized Shaping Of Models For Solving Dec-Pomdps, Pradeep Reddy Varakantham, William Yeoh, Prasanna Velagapudi, Paul Scerri

Research Collection School Of Computing and Information Systems

An interesting class of multi-agent POMDP planning problems can be solved by having agents iteratively solve individual POMDPs, find interactions with other individual plans, shape their transition and reward functions to encourage good interactions and discourage bad ones and then recompute a new plan. D-TREMOR showed that this approach can allow distributed planning for hundreds of agents. However, the quality and speed of the planning process depends on the prioritization scheme used. Lower priority agents shape their models with respect to the models of higher priority agents. In this paper, we introduce a new prioritization scheme that is guaranteed to …

Message Passing Algorithms For Map Estimation Using Dc Programming, Akshat Kumar, Shlomo Zilberstein, Marc Toussaint

Research Collection School Of Computing and Information Systems

We address the problem of finding the most likely assignment or MAP estimation in a Markov random field. We analyze the linear programming formulation of MAP through the lens of difference of convex functions (DC) programming, and use the concave-convex procedure (CCCP) to develop efficient message-passing solvers. The resulting algorithms are guaranteed to converge to a global optimum of the well-studied local polytope, an outer bound on the MAP marginal polytope. To tighten the outer bound, we show how to combine it with the mean-field based inner bound and, again, solve it using CCCP. We also identify a useful relationship …

A Sentiment Analysis Of Singapore Presidential Election 2011 Using Twitter Data With Census Correction, Murphy Junyu Choy, Michelle Lee Fong Cheong, Nang Laik Ma, Ping Shung Koo

Research Collection School Of Computing and Information Systems

Sentiment analysis is a new area in text analytics where it focuses on the analysis and understanding of the human emotions from the text patterns. This new form of analysis has been widely adopted in customer relationship management especially in the context of complaint management. However, sentiment analysis using Twitter data has remained extremely difficult to manage due to sampling biasness. In this paper, we will discuss about the application of reweighting techniques in conjunction with online sentiment divisions to predict the vote percentage that individual presidential candidate in Singapore will receive in the Presidential Election 2011. There will be …

Robust Local Search For Solving Rcpsp/Max With Durational Uncertainty, Na Fu, Hoong Chuin Lau, Pradeep Varakantham, Fei Xiao

Research Collection School Of Computing and Information Systems

Scheduling problems in manufacturing, logistics and project management have frequently been modeled using the framework of Resource Constrained Project Scheduling Problems with minimum and maximum time lags (RCPSP/max). Due to the importance of these problems, providing scalable solution schedules for RCPSP/max problems is a topic of extensive research. However, all existing methods for solving RCPSP/max assume that durations of activities are known with certainty, an assumption that does not hold in real world scheduling problems where unexpected external events such as manpower availability, weather changes, etc. lead to delays or advances in completion of activities. Thus, in this paper, our …

Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation …

A Pomdp Model For Guiding Taxi Cruising In A Congested Urban City, Lucas Agussurja, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We consider a partially observable Markov decision process (POMDP) model for improving a taxi agent cruising decision in a congested urban city. Using real-world data provided by a large taxi company in Singapore as a guide, we derive the state transition function of the POMDP. Specifically, we model the cruising behavior of the drivers as continuous-time Markov chains. We then apply dynamic programming algorithm for finding the optimal policy of the driver agent. Using a simulation, we show that this policy is significantly better than a greedy policy in congested road network.

Allocating Resources In Multiagent Flowshops With Adaptive Auctions, Hoong Chuin Lau, Zhengyi Zhao, Sam Shuzhi Ge, Thong Heng Lee

Research Collection School Of Computing and Information Systems

In this paper, we consider the problem of allocating machine resources among multiple agents, each of which is responsible to solve a flowshop scheduling problem. We present an iterated combinatorial auction mechanism in which bid generation is performed within each agent, while a price adjustment procedure is performed by a centralized auctioneer. While this approach is fairly well-studied in the literature, our primary innovation is in an adaptive price adjustment procedure, utilizing variable step-size inspired by adaptive PID-control theory coupled with utility pricing inspired by classical microeconomics. We compare with the conventional price adjustment scheme proposed in Fisher (1985), and …

Taxisim: A Multiagent Simulation Platform For Evaluating Taxi Fleet Operations, Shih-Fen Cheng, Thi Duong Nguyen

Research Collection School Of Computing and Information Systems

Taxi service is an important mode of public transportation in most metropolitan areas since it provides door-to-door convenience in the public domain. Unfortunately, despite all the convenience taxis bring, taxi fleets are also extremely inefficient to the point that over 50% of its operation time could be spent in idling state. Improving taxi fleet operation is an extremely challenging problem, not just because of its scale, but also due to fact that taxi drivers are self-interested agents that cannot be controlled centrally. To facilitate the study of such complex and decentralized system, we propose to construct a multiagent simulation platform …

Scalable Multiagent Planning Using Probabilistic Inference, Akshat Kumar, Shlomo Zilberstein, Marc Toussaint

Research Collection School Of Computing and Information Systems

Multiagent planning has seen much progress with the development of formal models such as Dec-POMDPs. However, the complexity of these models -- NEXP-Complete even for two agents -- has limited scalability. We identify certain mild conditions that are sufficient to make multiagent planning amenable to a scalable approximation w.r.t. the number of agents. This is achieved by constructing a graphical model in which likelihood maximization is equivalent to plan optimization. Using the Expectation-Maximization framework for likelihood maximization, we show that the necessary inference can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We …

Finding Robust-Under-Risk Solutions For Flowshop Scheduling, Steven O. Kimbrough, Ann Kuo, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We propose and explore, in the context of benchmark problems for flowshop scheduling, a risk-based concept of robustness for optimization problems. This risk-based concept is in distinction to, and complements, the uncertainty-based concept employed in the field known as robust optimization. Implementation of our concept requires problem solution methods that sample the solution space intelligently and that produce large numbers of distinct sample points. With these solutions to hand, their robustness scores are easily obtained and heuristically robust solutions found. We find evolutionary computation to be effective for this purpose on these problems.

Real-World Parameter Tuning Using Factorial Design With Parameter Decomposition, Aldy Gunawan, Hoong Chuin Lau, Elaine Wong

Research Collection School Of Computing and Information Systems

In this paper, we explore the idea of improving the efficiency of factorial design for parameter tuning of metaheuristics. In a standard full factorial design, the number of runs increases exponentially as the number of parameters. To reduce the parameter search space, one option is to first partition parameters into disjoint categories. While this may be done manually based on user guidance, an automated approach proposed in this paper is to apply a fractional factorial design to partition parameters based on their main effects where each partition is then tuned independently. With a careful choice of fractional design, our approach …

Message-Passing Algorithms For Quadratic Programming Formulations Of Map Estimation, Akshat Kumar, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Computing maximum a posteriori (MAP) estimation in graphical models is an important inference problem with many applications. We present message-passing algorithms for quadratic programming (QP) formulations of MAP estimation for pairwise Markov random fields. In particular, we use the concave-convex procedure (CCCP) to obtain a locally optimal algorithm for the non-convex QP formulation. A similar technique is used to derive a globally convergent algorithm for the convex QP relaxation of MAP. We also show that a recently developed expectation-maximization (EM) algorithm for the QP formulation of MAP can be derived from the CCCP perspective. Experiments on synthetic and real-world problems …

Adaptive Decision Support For Structured Organizations: A Case For Orgpomdps, Pradeep Reddy Varakantham, Nathan Schurr, Alan Carlin, Christopher Amato

Research Collection School Of Computing and Information Systems

In today's world, organizations are faced with increasingly large and complex problems that require decision-making under uncertainty. Current methods for optimizing such decisions fall short of handling the problem scale and time constraints. We argue that this is due to existing methods not exploiting the inherent structure of the organizations which solve these problems. We propose a new model called the OrgPOMDP (Organizational POMDP), which is based on the partially observable Markov decision process (POMDP). This new model combines two powerful representations for modeling large scale problems: hierarchical modeling and factored representations. In this paper we make three key contributions: …

Distributed Model Shaping For Scaling To Decentralized Pomdps With Hundreds Of Agents, Prasanna Velagapudi, Pradeep Reddy Varakantham, Katia Sycara, Paul Scerri

Research Collection School Of Computing and Information Systems

The use of distributed POMDPs for cooperative teams has been severely limited by the incredibly large joint policy- space that results from combining the policy-spaces of the individual agents. However, much of the computational cost of exploring the entire joint policy space can be avoided by observing that in many domains important interactions between agents occur in a relatively small set of scenarios, previously defined as coordination locales (CLs) [11]. Moreover, even when numerous interactions might occur, given a set of individual policies there are relatively few actual interactions. Exploiting this observation and building on an existing model shaping algorithm, …

Incremental Dcop Search Algorithms For Solving Dynamic Dcop Problems, William Yeoh, Pradeep Varakantham, Xiaoxun Sun, Sven Koenig

Research Collection School Of Computing and Information Systems

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper …

Decentralized Decision Support For An Agent Population In Dynamic And Uncertain Domains, Pradeep Reddy Varakantham, Shih-Fen Cheng, Thi Duong Nguyen

Research Collection School Of Computing and Information Systems

This research is motivated by problems in urban transportation and labor mobility, where the agent flow is dynamic, non-deterministic and on a large scale. In such domains, even though the individual agents do not have an identity of their own and do not explicitly impact other agents, they have implicit interactions with other agents. While there has been much research in handling such implicit effects, it has primarily assumed controlled movements of agents in static environments. We address the issue of decision support for individual agents having involuntary movements in dynamic environments . For instance, in a taxi fleet serving …

Message-Passing Algorithms For Large Structured Decentralized Pomdps, Akshat Kumar, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Decentralized POMDPs provide a rigorous framework for multi-agent decision-theoretic planning. However, their high complexity has limited scalability. In this work, we present a promising new class of algorithms based on probabilistic inference for infinite-horizon ND-POMDPs---a restricted Dec-POMDP model. We first transform the policy optimization problem to that of likelihood maximization in a mixture of dynamic Bayes nets (DBNs). We then develop the Expectation-Maximization (EM) algorithm for maximizing the likelihood in this representation. The EM algorithm for ND-POMDPs lends itself naturally to a simple message-passing paradigm guided by the agent interaction graph. It is thus highly scalable w.r.t. the number of …

Random Keys Genetic Algorithms Scheduling And Rescheduling Systems For Common Production Systems, Elkin Rodriguez-Velasquez

Engineering Management & Systems Engineering Theses & Dissertations

The majority of scheduling research deals with problems in specific production environments with specific objective functions. However, in many cases, more than one problem type and/or objective function exists, resulting in the need for a more generic and flexible system to generate schedules. Furthermore, most of the published scheduling research focuses on creating an optimal or near optimal initial schedule during the planning phase. However, after production processes start, circumstances like machine breakdowns, urgent jobs, and other unplanned events may render the schedule suboptimal, obsolete or even infeasible resulting in a "rescheduling" problem, which is typically also addressed for a …

Improving Service Through Just-In-Time Concept In A Dynamic Operational Environment, Kar Way Tan, Hoong Chuin Lau, Na Fu

Research Collection School Of Computing and Information Systems

This paper is concerned with the problem of Just-In-Time (JIT) job scheduling in a dynamic environment under uncertainty to attain timely service. We provide an approach, based on robust scheduling concepts, to analytically evaluate the expected cost of earliness and tardiness for each job and also the project. In addition, we search for a schedule execution policy with the minimum robust cost such that for a given risk level (epsilon), the actual realized schedule has (1 - epsilon) probability of completing with less than or equal to this robust cost. Our method is quite generic, and can be applied to …

Fine-Tuning Algorithm Parameters Using The Design Of Experiments Approach, Aldy Gunawan, Hoong Chuin Lau, Linda Lindawati

Research Collection School Of Computing and Information Systems

Optimizing parameter settings is an important task in algorithm design. Several automated parameter tuning procedures/configurators have been proposed in the literature, most of which work effectively when given a good initial range for the parameter values. In the Design of Experiments (DOE), a good initial range is known to lead to an optimum parameter setting. In this paper, we present a framework based on DOE to find a good initial range of parameter values for automated tuning. We use a factorial experiment design to first screen and rank all the parameters thereby allowing us to then focus on the parameter …

Instance-Based Parameter Tuning Via Search Trajectory Similarity Clustering, Linda Lindawati, Hoong Chuin Lau, David Lo

Research Collection School Of Computing and Information Systems

This paper is concerned with automated tuning of parameters in local-search based meta-heuristics. Several generic approaches have been introduced in the literature that returns a ”one-size-fits-all” parameter configuration for all instances. This is unsatisfactory since different instances may require the algorithm to use very different parameter configurations in order to find good solutions. There have been approaches that perform instance-based automated tuning, but they are usually problem-specific. In this paper, we propose CluPaTra, a generic (problem-independent) approach to perform parameter tuning, based on CLUstering instances with similar PAtterns according to their search TRAjectories. We propose representing a search trajectory as …

Map Estimation For Graphical Models By Likelihood Maximization, Akshat Kumar, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Computing a maximum a posteriori (MAP) assignment in graphical models is a crucial inference problem for many practical applications. Several provably convergent approaches have been successfully developed using linear programming (LP) relaxation of the MAP problem. We present an alternative approach, which transforms the MAP problem into that of inference in a finite mixture of simple Bayes nets. We then derive the Expectation Maximization (EM) algorithm for this mixture that also monotonically increases a lower bound on the MAP assignment until convergence. The update equations for the EM algorithm are remarkably simple, both conceptually and computationally, and can be implemented …

Event Study Method For Validating Agent-Based Trading Simulations, Shih-Fen Cheng

Research Collection School Of Computing and Information Systems

In this paper, we introduce how one can validate an event-centric trading simulation platform that is built with multi-agent technology. The issue of validation is extremely important for agent-based simulations, but unfortunately, so far there is no one universal method that would work in all domains. The primary contribution of this paper is a novel combination of event-centric simulation design and event study approach for market dynamics generation and validation. In our event-centric design, the simulation is progressed by announcing news events that affect market prices. Upon receiving these events, event-aware software agents would adjust their views on the market …