Author name cluster

Supriyo Ghosh

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

2 author rows

UAI Conference 2022 Conference Paper

Neural-progressive hedging: Enforcing constraints in reinforcement learning with stochastic programming

Supriyo Ghosh
Laura Wynter
Shiau Hong Lim
Duc Thien Nguyen

We propose a framework, called neural-progressive hedging (NP), that leverages stochastic programming during the online phase of executing a reinforcement learning (RL) policy. The goal is to ensure feasibility with respect to constraints and risk-based objectives such as conditional value-at-risk (CVaR) during the execution of the policy, using probabilistic models of the state transitions to guide policy adjustments. The framework is particularly amenable to the class of sequential resource allocation problems since feasibility with respect to typical resource constraints cannot be enforced in a scalable manner. The NP framework provides an alternative that adds modest overhead during the online phase. Experimental results demonstrate the efficacy of the NP framework on two continuous real-world tasks: (i) the portfolio optimization problem with liquidity constraints for financial planning, characterized by non-stationary state distributions; and (ii) the dynamic repositioning problem in bike sharing systems, that embodies the class of supply-demand matching problems. We show that the NP framework produces policies that are better than deep RL and other baseline approaches, adapting to non-stationarity, whilst satisfying structural constraints and accommodating risk measures in the resulting policies. Additional benefits of the NP framework are ease of implementation and better explainability of the policies.

Details

ICAPS Conference 2021 Conference Paper

A Deep Ensemble Method for Multi-Agent Reinforcement Learning: A Case Study on Air Traffic Control

Supriyo Ghosh
Sean Laguna
Shiau Hong Lim
Laura Wynter
Hasan A. Poonawala

Reinforcement learning (RL), a promising framework for data-driven decision making in an uncertain environment, has successfully been applied in many real-world operation and control problems. However, the application of RL in a large-scale decentralized multi-agent environment remains a challenging problem due to the partial observability and limited communications between agents. In this paper, we develop a model-based kernel RL approach and a model-free deep RL approach for learning a decentralized, shared policy among homogeneous agents. By leveraging the strengths of both these methods, we further propose a novel deep ensemble multi-agent reinforcement learning (MARL) method that efficiently learns to arbitrate between the decisions of the local kernel-based RL model and the wider-reaching deep RL model. We validate the proposed deep ensemble method on a highly challenging real-world air traffic control problem, where the goal is to provide effective guidance to aircraft to avoid air traffic congestion, conflicting situations, and to improve arrival timeliness, by dynamically recommending adjustments of aircraft speeds in real-time. Extensive empirical results from an open-source air traffic management simulation model, developed by Eurocontrol and built on a real-world data set including thousands of aircrafts, demonstrate that our proposed deep ensemble MARL method significantly outperforms three state-of-the-art benchmark approaches.

Details

IJCAI Conference 2019 Conference Paper

Improving Customer Satisfaction in Bike Sharing Systems through Dynamic Repositioning

Supriyo Ghosh
Jing Yu Koh
Patrick Jaillet

In bike sharing systems (BSSs), the uncoordinated movements of customers using bikes lead to empty or congested stations, which causes a significant loss in customer demand. In order to reduce the lost demand, a wide variety of existing research has employed a fixed set of historical demand patterns to design efficient bike repositioning solutions. However, the progress remains slow in understanding the underlying uncertainties in demand and designing proactive robust bike repositioning solutions. To bridge this gap, we propose a dynamic bike repositioning approach based on a probabilistic satisficing method which uses the uncertain demand parameters that are learnt from historical data. We develop a novel and computationally efficient mixed integer linear program for maximizing the probability of satisfying the uncertain demand so as to improve the overall customer satisfaction and efficiency of the system. Extensive experimental results from a simulation model built on a real-world bike sharing data set demonstrate that our approach is not only robust to uncertainties in customer demand, but also outperforms the existing state-of-the-art repositioning approaches in terms of reducing the expected lost demand.

PDF Details

AAAI Conference 2018 Conference Paper

Dispatch Guided Allocation Optimization for Effective Emergency Response

Supriyo Ghosh
Pradeep Varakantham

Effective emergency (medical, ﬁre or criminal) response is crucial for improving safety and security in urban environments. Recent research in improving effectiveness of emergency management systems (EMSs) has utilized data-driven optimization models for efﬁcient allocation of emergency response vehicles (ERVs) to base locations. However, these data-driven optimization models either ignore the dispatch strategy of ERVs (typically the nearest available ERV is dispatched to serve an incident) or employ myopic approaches (e. g. , greedy approach based on marginal gain). This results in allocations that are not synchronised with the real evolution dynamics on the ground or can be improved signiﬁcantly. To bridge this gap, we make the following contributions: (1) We ﬁrst provide a novel exact optimization model for allocation of ERVs that incorporates the non-linear real-world dispatch strategy as linear constraints and ensures that optimization exactly imitates the real-world dynamics of EMS; (2) In order to improve scalability, we then provide two novel heuristic approaches to solve problems with large number of emergency incidents; and (3) Finally, using two real-world EMS data sets, we empirically demonstrate that our heuristic approaches provide signiﬁcant improvement over the best known benchmark approach.

PDF Details

ICAPS Conference 2018 Conference Paper

Reserved Optimisation: Handling Incident Priorities in Emergency Response Systems

Muralidhar Konda
Supriyo Ghosh
Pradeep Varakantham

Emergency (medical, fire or criminal) Management Systems (EMSs) are crucial for ensuring public safety and security. Typically in many cities, less than 20% of the cases received by EMSs belong to the extremely serious category and require immediate help. Rest of the incidents typically are less serious and thereby allow more flexibility in response time. Therefore, for efficient management of EMS requests, several EMSs now categorise an incoming emergency request into a priority level based on well studied ``triaging" methods. Leading research on optimising emergency response has either focussed on data-driven models for settings with homogenous incidents or on generic heuristics (that are not data-driven) in multi-priority incident settings. In this paper, we provide data-driven models that employ tiered optimisation of allocation and dispatch simultaneously to ensure high priority incidents are served effectively. To that end, we make the following contributions in this paper: (1) For a given dataset of historical incidents, we first provide an optimisation model that maximises the percentage of highest priority incidents served within a threshold response time, while ensuring threshold response times for other priority incidents. Apart from optimising the allocation, this optimisation model also provides a detailed dispatch strategy that fits the given set of historical incidents well; (2) To better handle high variance (spatial and temporal) in arrival of high priority incidents, we reserve a set of ERVs for high priority incidents. Our second contribution is in modifying our optimisation model to reserve a subset of ERVs for high priority incidents while considering a minor modification to nearest available ERV dispatch strategy; and (3) Finally, using a real-world EMS data set, we experimentally demonstrate that our solution with a detailed dispatch strategy outperforms the existing benchmark approach. Moreover, due to the presence of few high priority incidents and significant spatio-temporal uncertainty associated with them, we show that a simple dispatch strategy with reserved ERVs outperforms the detailed dispatch strategy.

Details

JAIR Journal 2017 Journal Article

Dynamic Repositioning to Reduce Lost Demand in Bike Sharing Systems

Supriyo Ghosh
Pradeep Varakantham
Yossiri Adulyasak
Patrick Jaillet

Bike Sharing Systems (BSSs) are widely adopted in major cities of the world due to concerns associated with extensive private vehicle usage, namely, increased carbon emissions, traffic congestion and usage of nonrenewable resources. In a BSS, base stations are strategically placed throughout a city and each station is stocked with a pre-determined number of bikes at the beginning of the day. Customers hire the bikes from one station and return them at another station. Due to unpredictable movements of customers hiring bikes, there is either congestion (more than required) or starvation (fewer than required) of bikes at base stations. Existing data has shown that congestion/starvation is a common phenomenon that leads to a large number of unsatisfied customers resulting in a significant loss in customer demand. In order to tackle this problem, we propose an optimisation formulation to reposition bikes using vehicles while also considering the routes for vehicles and future expected demand. Furthermore, we contribute two approaches that rely on decomposability in the problem (bike repositioning and vehicle routing) and aggregation of base stations to reduce the computation time significantly. Finally, we demonstrate the utility of our approach by comparing against two benchmark approaches on two real-world data sets of bike sharing systems. These approaches are evaluated using a simulation where the movements of customers are generated from real-world data sets.

PDF Details DOI

ICAPS Conference 2017 Conference Paper

Incentivizing the Use of Bike Trailers for Dynamic Repositioning in Bike Sharing Systems

Supriyo Ghosh
Pradeep Varakantham

Bike Sharing System (BSS) is a green mode of transportation that is employed extensively for short distance travels in major cities of the world. Unfortunately, the users behaviour driven by their personal needs can often result in empty or full base stations, thereby resulting in loss of customer demand. To counter this loss in customer demand, BSS operators typically utilize a fleet of carrier vehicles for repositioning the bikes between stations. However, this fuel burning mode of repositioning incurs a significant amount of routing, labor cost and further increases carbon emissions. Therefore, we propose a potentially self-sustaining and environment friendly system of dynamic repositioning, that moves idle bikes during the day with the help of bike trailers. A bike trailer is an add-on to a bike that can help with carrying 3-5 bikes at once. Specifically, we make the following key contributions: (i) We provide an optimization formulation that generates “repositioning” tasks so as to minimize the expected lost demand over past demand scenarios; (ii) Within the budget constraints of the operator, we then design a mechanism to crowdsource the tasks among potential users who intend to execute repositioning tasks; (iii) Finally, we provide extensive results on a wide range of demand scenarios from a real-world data set to demonstrate that our approach is highly competitive to the existing fuel burning mode of repositioning while being green.

Details

ICAPS Conference 2017 Conference Paper

Online Repositioning in Bike Sharing Systems

Meghna Lowalekar
Pradeep Varakantham
Supriyo Ghosh
Sanjay Dominik Jena
Patrick Jaillet

Due to increased traffic congestion and carbon emissions, Bike Sharing Systems (BSSs) are adopted in various cities for short distance travels, specifically for last mile transportation. The success of a bike sharing system depends on its ability to have bikes available at the "right" base stations at the "right" times. Typically, carrier vehicles are used to perform repositioning of bikes between stations so as to satisfy customer requests. Owing to the uncertainty in customer demand and day-long repositioning, the problem of having bikes available at the right base stations at the right times is a challenging one. In this paper, we propose a multi-stage stochastic formulation, to consider expected future demand over a set of scenarios to find an efficient repositioning strategy for bike sharing systems. Furthermore, we provide a Lagrangian decomposition approach (that decouples the global problem into routing and repositioning slaves and employs a novel DP approach to efficiently solve routing slave) and a greedy online anticipatory heuristic to solve large scale problems effectively and efficiently. Finally, in our experimental results, we demonstrate significant reduction in lost demand provided by our techniques on real world datasets from two bike sharing companies in comparison to existing benchmark approaches.

Details

IJCAI Conference 2016 Conference Paper

Robust Repositioning to Counter Unpredictable Demand in Bike Sharing Systems

Supriyo Ghosh
Michael Trick
Pradeep Varakantham

Bike Sharing Systems (BSSs) experience a significant loss in customer demand due to starvation (empty base stations precluding bike pickup) or congestion (full base stations precluding bike return). Therefore, BSSs operators reposition bikes between stations with the help of carrier vehicles. Due to unpredictable and dynamically changing nature of the demand, myopic reasoning typically provides a below par performance. We propose an online and robust repositioning approach to minimise the loss in customer demand while considering the possible uncertainty in future demand. Specifically, we develop a scenario generation approach based on an iterative two player game to compute a strategy of repositioning by assuming that the environment can generate a worse demand scenario (out of the feasible demand scenarios) against the current repositioning solution. Extensive computational results from a simulation built on real world data set of bike sharing company demonstrate that our approach can significantly reduce the expected lost demand over the existing benchmark approaches.

PDF Details

ICAPS Conference 2016 Conference Paper

Strategic Planning for Setting Up Base Stations in Emergency Medical Systems

Supriyo Ghosh
Pradeep Varakantham

Emergency Medical Systems (EMSs) are an important component of public health-care services. Improving infrastructure for EMS and specifically the construction of base stations at the ”right” locations to reduce response times is the main focus of this paper. This is a computationally challenging task because of the: (a) exponentially large action space arising from having to consider combinations of potential base locations, which themselves can be significant; and (b) direct impact on the performance of the ambulance allocation problem, where we decide allocation of ambulances to bases. We present an incremental greedy approach to discover the placement of bases that maximises the service level of EMS. Using the properties of submodular optimisation we show that our greedy algorithm provides quality guaranteed solutions for one of the objectives employed in real EMSs. Furthermore, we validate our derived policy by employing a real-life event driven simulator that incorporates the real dynamics of EMS. Finally, we show the utility of our approaches on a real-world dataset from a large asian city and demonstrate significant improvement over the best known approaches from literature.

Details

ICAPS Conference 2015 Conference Paper

Dynamic Redeployment to Counter Congestion or Starvation in Vehicle Sharing Systems

Supriyo Ghosh
Pradeep Varakantham
Yossiri Adulyasak
Patrick Jaillet

Extensive usage of private vehicles has led to increased traffic congestion, carbon emissions, and usage of non-renewable resources. These concerns have led to the wide adoption of vehicle sharing (ex: bike sharing, car sharing) systems in many cities of the world. In vehicle-sharing systems, base stations (ex: docking stations for bikes) are strategically placed throughout a city and each of the base stations contain a pre-determined number of vehicles at the beginning of each day. Due to the stochastic and individualistic movement of customers, there is typically either congestion (more than required)or starvation (fewer than required) of vehicles at certain base stations. As demonstrated in our experimental results, this happens often and can cause a significant loss in demand. We propose to dynamically redeploy idle vehicles using carriers so as to minimize lost de-mand or alternatively maximize revenue for the vehicle sharing company. To that end, we contribute an optimization formulation to jointly address the redeploy-ment (of vehicles) and routing (of carriers) problemsand provide two approaches that rely on decomposability and abstraction of problem domains to reduce the computation time significantly. Finally, we demonstrate the utility of our approaches on two real world data sets of bike-sharing companies.

Details

SoCS Conference 2015 Conference Paper

Dynamic Redeployment to Counter Congestion or Starvation in Vehicle Sharing Systems

Supriyo Ghosh
Pradeep Varakantham
Yossiri Adulyasak
Patrick Jaillet

Vehicle sharing (ex: bike sharing, car sharing) systems, an attractive alternative of private transportation, are widely adopted in major cities around the world. In vehicle-sharing systems, base stations (ex: docking stations for bikes) are strategically placed throughout a city and each of the base stations contain a pre-determined number of vehicles at the beginning of each day. Due to the stochastic and individualistic movement of customers, there is typically either congestion (more than required) or starvation (fewer than required) of vehicles at certain base stations, which causes a significant loss in demand. We propose to dynamically redeploy idle vehicles using carriers so as to minimize lost demand or alternatively maximize revenue for the vehicle sharing company. To that end, we contribute an optimization formulation to jointly address the redeployment (of vehicles) and routing (of carriers) problems and provide two approaches that rely on decomposability and abstraction of problem domains to reduce the computation time significantly.

Details

IJCAI Conference 2015 Conference Paper

Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs

Supriyo Ghosh
Akshat Kumar
Pradeep Varakantham

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 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.

PDF Details