Skip to content Skip to navigation

2016 Archives

Year 2016

 

T. H. Teng, S. F. Cheng, T. N. Truong and H. C. Lau. Managing Egress of Crowd During Infrastructure Disruption. Winter Simulation Conference 2016 (WSC 2016), Washington, D.C., USA, Dec 2016

In a large indoor environment such as a sports arena or convention center, the smooth egress of a crowd after an event can be seriously affected if infrastructure such as elevators and escalators break down. In this paper, we propose a novel crowd simulator known as SIM-DISRUPT for simulating egress scenarios in non-emergency situations. To surface the impact of disrupted infrastructure on the egress of crowd, SIM-DISRUPT includes features that allows the user to specify selective disruptions as well as strategies for controlling the distribution and egress choices of crowd. Using SIM-DISRUPT, we investigate effects of crowd distribution, egress choices and infrastructure disruptions on crowd egress time and measure efficacies of different egress strategies under various infrastructure disruption scenarios. A real-world inspired use case is used to demonstrate the usefulness of SIM-DISRUPT in planning egress under various operational conditions.

 

B. X. Li, K. W. Tan and K. T. Tran. Traffic Simulation Model for Port Planning and Congestion Prevention. Winter Simulation Conference 2016 (WSC 2016), Washington, D.C., USA, Dec 2016

Effective management of landside transportation provides the competitive advantage to port terminal operators in improving services and efficient use of limited space in an urban port. We present a hybrid simulation model that combines traffic-flow modeling and discrete-event simulation for landside port planning and evaluation of traffic conditions for a number of what-if scenarios. We design our model based on a real-world case of a bulk cargo port. The problem is interesting due to complexity of heterogeneous closed-looped internal vehicles and external vehicles traveling in spaces with very limited traffic regulation (no traffic lights, no traffic wardens) and the traffic interactions with port operations such as loading and unloading cargos. Our simulation results show interesting decision-support scenarios for decision makers to evaluate future port planning possibilities and to derive regulation policies governing the port traffic.

 

P. Agrawal, P. Varakantham and W. Yeoh. Scalable Greedy Algorithms For Task/Resource Constrained Multi-Agent Stochastic Planning. Algorithmic Game Theory Workshop at 25th International Joint Conference on Artificial Intelligence (AGT-IJCAI 2016), New York City, USA, July 2016

Synergistic interactions between task/resource allocation and stochastic planning exist in many environments such as transportation and logistics, UAV task assignment and disaster rescue. Existing research in exploiting these synergistic interactions between the two problems have either only considered domains where tasks/resources are completely independent of each other or have focussed on approaches with limited scalability. In this paper, we address these two limitations by introducing a generic model for task/resource constrained multi-agent stochastic planning, referred to as TasC-MDPs. We provide two scalable greedy algorithms, one of which provides posterior quality guarantees. Finally, we illustrate the high scalability and solution performance of our approaches in comparison with existing work on two benchmark problems from the literature.

 

T. H. Teng, S. D. Handoko and H. C. Lau. Self-Organizing Neural Network for Adaptive Operator Selection in Evolutionary Search. In Proc 10th Learning and Intelligent OptimizatioN Conference (LION-16), Naples, Italy, June 2016.

Evolutionary Algorithm is a well-known meta-heuristics paradigm capable of providing high-quality solutions to computationally hard problems. As with the other meta-heuristics, its performance is often attributed to appropriate design choices such as the choice of crossover operators and some other parameters. In this paper, we propose a continuous state Markov Decision Process model to select crossover operators based on the states during evolutionary search. We propose to find the operator selection policy efficiently using a self-organizing neural network, which is trained offline using randomly selected training samples.  The trained neural network is then verified on test instances not used for generating the training samples. We evaluate the efficacy and robustness of our proposed approach with benchmark instances of Quadratic Assignment Problem.

 

S. Ghosh, A. Kumar and P. Varakantham. Probabilistic Inference Based Message-Passing For Resource Constrained DCOPs. International Workshop on Optimisation in Multi-Agent Systems (OptMAS 2016), Singapore, May 2016.

Distributed constraint optimization (DCOP) is an important framework for coordinated multi-agent 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 coordination 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 efficient centralized solver show that our approach provides near-optimal solutions, and is significantly faster on larger instances.

 

D.T. Nguyen, A.Kumar, H.C. Lau and D. Sheldon. Approximate Inference Using DC Programming For Collective Graphical Models.19th International Conference on Artificial Intelligence and Statistics (AISTATS16), Cadiz, Spain, May 2016.

Collective graphical models (CGMs) provide a framework for reasoning about a population of independent and identically distributed individuals when only noisy and aggregate observations are given. Previous approaches for inference in CGMs work on a junction-tree representation, thereby highly limiting their scalability. To remedy this, we show how the Bethe entropy approximation naturally arises for the inference problem in CGMs. We reformulate the resulting optimization problem as a difference-of-convex functions program that can capture different types of CGM noise models. Using the concave-convex procedure, we then develop a scalable message-passing algorithm. Empirically, we show our approach is highly scalable and accurate for large graphs, more than an order-of-magnitude faster than a generic optimization solver, and is guaranteed to converge unlike the previous message-passing approach NLBP that fails in several loopy graphs.

 

H. C. Lau, A. Gunawan, P. Varakantham and W. Wang. PRESS: PeRsonalized Event Scheduling recommender System. 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), Grand Copthorne Waterfront Hotel, Singapore, May 2016.

This paper presents a personalized event scheduling recommender system, PRESS, for a large conference setting with multiple parallel tracks. PRESS is a mobile application that gathers personalized information from a user and recommends talks/demos to be attend. The input from a user include a list of keyword preferences and (optionally) preferred talks. We use the MALLET topic model package to analyze the set of conference papers and classify them based on automatically identified topics. We propose an algorithm to generate a list of recommended papers based on the user keywords and the MALLET topics. An optimization model is then applied to obtain a feasible schedule. The recommended set is matched against the selected papers by the user which we obtained from a survey conducted at AAMAS-15 in Istanbul, Turkey. We show that PRESS is able to provide reasonable accuracy, precision and recall rates. PRESS will be deployed live during AAMAS-16 in Singapore.

 

T. V. Le, S. Liu and H. C. Lau. Reinforcement Learning Framework for Modeling Spatial Sequential Decisions under Uncertainty. 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), Grand Copthorne Waterfront Hotel, Singapore, May 2016.

We consider the problem of trajectory prediction, where a trajectory is an ordered sequence of location visits and corresponding timestamps. The problem arises when an agent makes sequential decisions to visit a set of spatial locations of interest. Each location bears a stochastic utility and the agent has a limited budget to spend. Given the agent’s observed partial trajectory, our goal is to predict the remaining trajectory. We propose a solution framework to the problem considering both the uncertainty of utility and the budget constraint. We use reinforcement learning (RL) to model the underlying decision processes and inverse RL to learn the utility distributions of the locations. We then propose two decision models to make predictions: one is based on long-term optimal planning of RL and another uses myopic heuristics. We finally apply the framework to predict real-world human trajectories and are able to explain the underlying processes of the observed actions.

 

L. Agussurja, H. C. Lau and S. F. Cheng. Achieving Stable and Fair Profit Allocation with Minimum Subsidy in Collaborative Logistics. 13th AAAI Conference on Artificial Intelligence, Phoenix, Arizona USA, February 2016.

With the advent of e-commerce, logistics providers are faced with the challenge of handling fluctuating and sparsely distributed demand, which raises their operational costs significantly. As a result, horizontal cooperation are gaining momentum around the world. One of the major impediments, however, is the lack of stable and fair profit sharing mechanism. In this paper, we address this problem using the framework of computational cooperative games. We first present cooperative vehicle routing game as a model for collaborative logistics operations. Using the axioms of Shapley value as the conditions for fairness, we show that a stable, fair and budget balanced allocation does not exist in many instances of the game. By relaxing budget balance, we then propose an allocation scheme based on the normalized Shapley value. We show that this scheme maintains stability and fairness while requiring minimum subsidy. Finally, using numerical experiments we demonstrate the feasibility of the scheme under various settings.

       

 

Last updated on 01 Feb 2017 .