Skip to content Skip to navigation

Year 2017

Year 2017


T. Verma, P. Varakantham, S. Kraus and H.C. Lau. Augmenting Decisions of Taxi Drivers through Reinforcement Learning for Improving Revenues. 27th International Conference on Automated Planning and Scheduling (ICAPS 2017), Pittsburgh, USA, Jun 2017

Taxis (which include cars working with car aggregation systems such as Uber, Grab, Lyft etc.) have become a critical component in the urban transportation. While most research and applications in the context of taxis have focused on improving performance from a customer perspective, in this paper, we focus on improving performance from a taxi driver perspective. Higher revenues for taxi drivers can help bring more drivers into the system thereby improving availability for customers in dense urban cities.

Typically, when there is no customer on board, taxi drivers will cruise around to find customers either directly (on the street) or indirectly (due to a request from a nearby customer on phone or on aggregation systems). For such cruising taxis, we develop a Reinforcement Learning (RL) based system to learn from real trajectory logs of drivers to advise them on the right locations to find customers which maximize their revenue. There are multiple translational challenges involved in building this RL system based on real data, such as annotating the activities (e.g., roaming, going to a taxi stand, etc.) observed in trajectory logs, identifying the right features for a state, action space and evaluating against real driver performance observed in the dataset. We also provide a dynamic abstraction mechanism to improve the basic learning mechanism. Finally, we provide a thorough evaluation on a real world data set from a developed Asian city and demonstrate that an RL based system can provide significant benefits to the drivers.


T.H. Teng, H.C. Lau and A. Kumar. Coordinating Vessel Traffic to Improve Safety and Efficiency. 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), Sao Paulo, Brazil, May 2017

Global increase in trade leads to congestion of maritime traffic at the ports. This often leads to increased maritime incidents or near-miss situations. To improve maritime safety while maintaining efficiency, movement of vessels needs to be better coordinated. Our work formulates this problem of coordinating the paths of vessels as a multi-agent path-finding(MAPF) problem. To address this problem, we introduce an innovative application of MAPF in the maritime domain known as Vessel Coordination Module (VCM). Based on the local search paradigm, VCM plans on a joint state space updated using the Electronic Navigation Charts (ENC) and the paths of vessels. We introduce the notion of path quality that measures the number of positions on a vessel path that is too close to some other vessels spatially and temporally. VCM aims to improve the overall path quality of vessels by improving path quality of selected vessels. Experiments are conducted on the Singapore Straits to evaluate and compare performance of our proposed approach in heterogeneous maritime scenario. Our experiment results show that VCM can improve the overall path quality of the vessels.


T.H. Teng, H.C. Lau and A. Kumar. Prescribing routes to improve safety and efficiency of vessel traffic. 5th International Maritime and Port Technology and Development Conference (MTEC 2017), Singapore, April 2017

Larger vessels are bringing more cargoes into Singapore. Being one of the busiest ports, the safety of navigation in Singapore waters is becoming a real and urgent concern. Collision and near-miss incidents accounted for the majority of maritime incidents between 2011 and 2013. Incident investigations revealed human factor accounted for majority of the causal factors. Thus, it is evident that the existing approaches are inadequate. To improve the safety of navigation and boost the shipping capacity of Singapore waters, this work introduces a prescriptive system known as VTM-Prescribe capable of discovering coordinated paths that get vessels to move in coordinated manner. VTM-Prescribe discovers the set of coordinated paths using a search algorithm based on a local search paradigm. Treating vessels with circular ship domain, VTM-Prescribe prescribes appropriate paths to the vessels, possibly modifying their navigation routes and schedules. Meant for the real world, VTM-Prescribe learns coordination strategies that account for real world parameters such as speed-over-ground, maneuverability and turnaround time of vessels. Rigorous experiments performed using recent AIS data show VTM-Prescribe can reduce risk of navigation and increase the shipping capacity of Singapore waters. This is to be followed up with pilot tests of VTM-Prescribe in near-real world scenarios.


Lim-Wavde, K., Kauffman, R. J., Kam, T. S., and Dawson, G.S. Location matters: geospatial policy analytics over time for household hazardous waste collection in California. iConference 2017, Wuhan, China, March 2017. (Nominated for the Lee Dirks Award for Best Paper)

By integrating mapping and geospatial data into a county-level dataset for exploratory analysis, we will demonstrate how to provide useful insights for waste managers and local governments regarding spatial patterns of household hazardous waste (HHW) collection and how it changes over time. We use map-based visualization to display patterns of spatial intensity and county locations for HHW collection in California from 2004 to 2015. We use exploratory spatial data analytics methods to characterize the spatial distribution of HHW collected per person. When we considered the spatial relationships, we were able to develop and estimate a geographically-weighted regression to explain how different regional factors influence the amount of HHW collected. These factors include demographic characteristics, HHW management policy instruments, and environmental quality enforcement and consideration of these factors are necessary to create a successful recycling program.


X. Wu, A. Kumar, D. Sheldon, and S. Zilberstein. Robust Optimization for Tree-Structured Stochastic Network Design. 31st AAAI Conference on Artificial Intelligence (AAAI 2017), San Francisco, California, USA, Feb 2017

Stochastic network design is a general framework for optimizing network connectivity. It has several applications in computational sustainability including spatial conservation planning, pre-disaster network preparation, and river network optimization. A common assumption in previous work has been made that network parameters (e.g., probability of species colonization) are precisely known, which is unrealistic in real-world settings. We therefore address the robust river network design problem where the goal is to optimize river connectivity for fish movement by removing barriers. We assume that fish passability probabilities are known only imprecisely, but are within some interval bounds. We then develop a planning approach that computes the policies with either high robust ratio or low regret. Empirically, our approach scales well to large river networks. We also provide insights into the solutions generated by our robust approach, which has significantly higher robust ratio than the baseline solution with mean parameter estimates.


D.T. Nguyen, A. Kumar and H.C. Lau. Collective Multiagent Sequential Decision Making Under Uncertainty. 31st AAAI Conference on Artificial Intelligence (AAAI 2017), San Francisco, California, USA, Feb 2017

Multiagent sequential decision making has seen rapid progress with formal models such as decentralized MDPs and POMDPs. However, scalability to large multiagent systems and applicability to real world problems remain limited. To address these challenges, we study multiagent planning problems where the collective behavior of a population of agents affects the joint-reward and environment dynamics. Our work exploits recent advances in graphical models for modeling and inference with a population of individuals such as collective graphical models and the notion of finite partial exchangeability in lifted inference. We develop a collective decentralized MDP model where policies can be computed based on counts of agents in different states. As the policy search space over counts is combinatorial, we develop a sampling based framework that can compute open and closed loop policies. Comparisons with previous best approaches on synthetic instances and a real world taxi dataset modeling supply-demand matching show that our approach significantly outperforms them w.r.t.solution quality.



Last updated on 11 May 2017 .