Arrow Research search

Author name cluster

Sarvapali Ramchurn

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.

22 papers
1 author row

Possible papers

22

AAMAS Conference 2023 Conference Paper

Multi-agent Signalless Intersection Management with Dynamic Platoon Formation

  • Phuriwat Worrawichaipat
  • Enrico H. Gerding
  • Ioannis Kaparias
  • Sarvapali Ramchurn

We propose a novel mechanism to manage platoons of autonomous vehicles at traffic intersections. Our mechanism optimises the formation forming vehicle platoons to minimises overall waiting time, allowing the optimal platoon size to be determined dynamically, thus minimising overall travel time. In addition, we introduce a conflict resolution algorithm, which dynamically authorises multiple platoons to manoeuvre even when the majority are single vehicles. Our empirical evaluation shows that, for single intersections, our mechanism can reduce the average travel time by up to ≈65% compared to conventional fixed-time traffic signals and up to ≈4% compared to advanced non-platoon-based signal-less first-comefirst-served approaches. Moreover, from the corridor-level aspect, our mechanism can reduce the weighted average trip duration up to ≈22% compared to the fixed-time traffic signals and up to ≈45% compared to the signal-less first-come-first-served approaches.

PDF

NeurIPS Conference 2022 Conference Paper

Non-Markovian Reward Modelling from Trajectory Labels via Interpretable Multiple Instance Learning

  • Joseph Early
  • Tom Bewley
  • Christine Evers
  • Sarvapali Ramchurn

We generalise the problem of reward modelling (RM) for reinforcement learning (RL) to handle non-Markovian rewards. Existing work assumes that human evaluators observe each step in a trajectory independently when providing feedback on agent behaviour. In this work, we remove this assumption, extending RM to capture temporal dependencies in human assessment of trajectories. We show how RM can be approached as a multiple instance learning (MIL) problem, where trajectories are treated as bags with return labels, and steps within the trajectories are instances with unseen reward labels. We go on to develop new MIL models that are able to capture the time dependencies in labelled trajectories. We demonstrate on a range of RL tasks that our novel MIL models can reconstruct reward functions to a high level of accuracy, and can be used to train high-performing agent policies.

PDF Details

AAAI Conference 2020 Conference Paper

Learning the Value of Teamwork to Form Efficient Teams

  • Ryan Beal
  • Narayan Changder
  • Timothy Norman
  • Sarvapali Ramchurn

In this paper we describe a novel approach to team formation based on the value of inter-agent interactions. Specifically, we propose a model of teamwork that considers outcomes from chains of interactions between agents. Based on our model, we devise a number of network metrics to capture the contribution of interactions between agents. This is then used to learn the value of teamwork from historical team performance data. We apply our model to predict team performance and validate our approach using real-world team performance data from the 2018 FIFA World Cup. Our model is shown to better predict the real-world performance of teams by up to 46% compared to models that ignore inter-agent interactions.

PDF Details

AAAI Conference 2020 Conference Paper

ODSS: Efficient Hybridization for Optimal Coalition Structure Generation

  • Narayan Changder
  • Samir Aknine
  • Sarvapali Ramchurn
  • Animesh Dutta

Coalition Structure Generation (CSG) is an NP-complete problem that remains difficult to solve on account of its complexity. In this paper, we propose an efficient hybrid algorithm for optimal coalition structure generation called ODSS. ODSS is a hybrid version of two previously established algorithms IDP (Rahwan and Jennings 2008) and IP (Rahwan et al. 2009). ODSS minimizes the overlapping between IDP and IP by dividing the whole search space of CSG into two disjoint sets of subspaces and proposes a novel subspace shrinking technique to reduce the size of the subspace searched by IP with the help of IDP. When compared to the state-of-the-art against a wide variety of value distributions, ODSS is shown to perform better by up to 54. 15% on benchmark inputs.

PDF Details

AAAI Conference 2016 Conference Paper

An Axiomatic Framework for Ex-Ante Dynamic Pricing Mechanisms in Smart Grid

  • Sambaran Bandyopadhyay
  • Ramasuri Narayanam
  • Pratyush Kumar
  • Sarvapali Ramchurn
  • Vijay Arya
  • Iskandarbin Petra

In electricity markets, the choice of the right pricing regime is crucial for the utilities because the price they charge to their consumers, in anticipation of their demand in real-time, is a key determinant of their profits and ultimately their survival in competitive energy markets. Among the existing pricing regimes, in this paper, we consider ex-ante dynamic pricing schemes as (i) they help to address the peak demand problem (a crucial problem in smart grids), and (ii) they are transparent and fair to consumers as the cost of electricity can be calculated before the actual consumption. In particular, we propose an axiomatic framework that establishes the conceptual underpinnings of the class of ex-ante dynamic pricing schemes. We first propose five key axioms that reflect the criteria that are vital for energy utilities and their relationship with consumers. We then prove an impossibility theorem to show that there is no pricing regime that satisfies all the five axioms simultaneously. We also study multiple cost functions arising from various pricing regimes to examine the subset of axioms that they satisfy. We believe that our proposed framework in this paper is first of its kind to evaluate the class of ex-ante dynamic pricing schemes in a manner that can be operationalised by energy utilities.

PDF Details

AAAI Conference 2015 Conference Paper

Balanced Trade Reduction for Dual-Role Exchange Markets

  • Dengji Zhao
  • Sarvapali Ramchurn
  • Enrico Gerding
  • Nicholas Jennings

We consider dual-role exchange markets, where traders can offer to both buy and sell the same commodity in the exchange but, if they transact, they can only be either a buyer or a seller, which is determined by the market mechanism. To design desirable mechanisms for such exchanges, we show that existing solutions may not be incentive compatible, and more importantly, cause the market maker to suffer a significant deficit. Hence, to combat this problem, following McAfee’s trade reduction approach, we propose a new trade reduction mechanism, called balanced trade reduction, that is incentive compatible and also provides flexible trade-offs between efficiency and deficit.

PDF Details

AAAI Conference 2015 Conference Paper

Crowdsourcing Complex Workflows under Budget Constraints

  • Long Tran-Thanh
  • Trung Dong Huynh
  • Avi Rosenfeld
  • Sarvapali Ramchurn
  • Nicholas Jennings

We consider the problem of task allocation in crowdsourcing systems with multiple complex workflows, each of which consists of a set of inter-dependent micro-tasks. We propose Budgeteer, an algorithm to solve this problem under a budget constraint. In particular, our algorithm first calculates an efficient way to allocate budget to each workflow. It then determines the number of inter-dependent micro-tasks and the price to pay for each task within each workflow, given the corresponding budget constraints. We empirically evaluate it on a well-known crowdsourcing-based text correction workflow using Amazon Mechanical Turk, and show that Budgeteer can achieve similar levels of accuracy to current benchmarks, but is on average 45% cheaper.

PDF Details

AAAI Conference 2015 Conference Paper

Sharing Rides with Friends: A Coalition Formation Algorithm for Ridesharing

  • Filippo Bistaffa
  • Alessandro Farinelli
  • Sarvapali Ramchurn

We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, arrange one-time rides at short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system modelling such problem as a graph constrained coalition formation (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i. e. , the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i. e. , the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (Geo- Life) and social data (Twitter), to validate the applicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36. 22%). Moreover, we can provide approximate solutions for very large systems (i. e. , up to 2000 agents) and good quality guarantees (i. e. , with an approximation ratio of 1. 41 in the worst case) within minutes (i. e. , 100 seconds).

PDF Details

IJCAI Conference 2013 Conference Paper

C-Link: A Hierarchical Clustering Approach to Large-Scale Near-Optimal Coalition Formation

  • Alessandro Farinelli
  • Manuele Bicego
  • Sarvapali Ramchurn
  • Mauro Zucchelli

Coalition formation is a fundamental approach to multi-agent coordination. In this paper we address the specific problem of coalition structure generation, and focus on providing good-enough solutions using a novel heuristic approach that is based on data clustering methods. In particular, we propose a hierarchical agglomerative clustering approach (C-Link), which uses a similarity criterion between coalitions based on the gain that the system achieves if two coalitions merge. We empirically evaluate C-Link on a synthetic benchmark data-set as well as in collective energy purchasing settings. Our results show that the C-link approach performs very well against an optimal benchmark based on Mixed-Integer Programming, achieving solutions which are in the worst case about 80% of the optimal (in the synthetic data-set), and 98% of the optimal (in the energy data-set). Thus we show that C-Link can return solutions for problems involving thousands of agents within minutes.

PDF Details DOI

AAAI Conference 2013 Conference Paper

Interdependent Multi-Issue Negotiation for Energy Exchange in Remote Communities

  • Muddasser Alam
  • Alex Rogers
  • Sarvapali Ramchurn

We present a novel negotiation protocol to facilitate energy exchange between off-grid homes that are equipped with renewable energy generation and electricity storage. Our protocol imposes restrictions over negotiation such that it reduces the complex interdependent multi-issue negotiation to one where agents have a strategy profile in subgame perfect Nash equilibrium. We show that our negotiation protocol is tractable, concurrent, scalable and leads to Pareto-optimal outcomes in a decentralised manner. We empirically evaluate our protocol and show that, in this instance, a society of agents can (i) improve the overall utilities by 14% and (ii) reduce their overall use of the batteries by 37%.

PDF Details

AAMAS Conference 2013 Conference Paper

RMASBench: A Benchmarking System for Multi-Agent Coordination in Urban Search and Rescue

  • Fabio Maffioletti
  • Riccardo Reffato
  • Alessandro Farinelli
  • Alexander Kleiner
  • Sarvapali Ramchurn
  • Bing Shi

This demonstration paper illustrates RMASBench, a new benchmarking system based on the RoboCup Rescue Agent simulator. The aim of the system is to facilitate benchmarking of coordination approaches in controlled settings for dynamic rescue scenarios. In particular, the key features of the systems are: i) programming interfaces to plug-in coordination algorithms without the need for implementing and tuning low-level agents’ behaviors, ii) implementations of state-of-the art coordination approaches: DSA and Max- Sum, iii) a large scale crowd simulator, which exploits GPUs parallel architecture, to simulate the behaviour of thousands of agents in real time.

PDF

AAAI Conference 2012 Conference Paper

Competing with Humans at Fantasy Football: Team Formation in Large Partially-Observable Domains

  • Tim Matthews
  • Sarvapali Ramchurn
  • Georgios Chalkiadakis

We present the first real-world benchmark for sequentiallyoptimal team formation, working within the framework of a class of online football prediction games known as Fantasy Football. We model the problem as a Bayesian reinforcement learning one, where the action space is exponential in the number of players and where the decision maker’s beliefs are over multiple characteristics of each footballer. We then exploit domain knowledge to construct computationally tractable solution techniques in order to build a competitive automated Fantasy Football manager. Thus, we are able to establish the baseline performance in this domain, even without complete information on footballers’ performances (accessible to human managers), showing that our agent is able to rank at around the top percentile when pitched against 2. 5M human players.

PDF Details

AAAI Conference 2012 Conference Paper

Delivering the Smart Grid: Challenges for Autonomous Agents and Multi-Agent Systems Research

  • Alex Rogers
  • Sarvapali Ramchurn
  • Nicholas Jennings

Restructuring electricity grids to meet the increased demand caused by the electrification of transport and heating, while making greater use of intermittent renewable energy sources, represents one of the greatest engineering challenges of our day. This modern electricity grid, in which both electricity and information flow in two directions between large numbers of widely distributed suppliers and generators — commonly termed the ‘smart grid’ — represents a radical reengineering of infrastructure which has changed little over the last hundred years. However, the autonomous behaviour expected of the smart grid, its distributed nature, and the existence of multiple stakeholders each with their own incentives and interests, challenges existing engineering approaches. In this challenge paper, we describe why we believe that artificial intelligence, and particularly, the fields of autonomous agents and multi-agent systems are essential for delivering the smart grid as it is envisioned. We present some recent work in this area and describe many of the challenges that still remain.

PDF Details

AAMAS Conference 2012 Conference Paper

On Coalition Formation with Sparse Synergies

  • Thomas Voice
  • Sarvapali Ramchurn
  • NICK JENNINGS

We consider coalition formation problems for agents with an underlying \emph{synergistic graph}, where edges between agents represent some vital synergistic link, such as communication, trust, or physical constraints. A coalition is infeasible if its members do not form a connected subgraph, meaning parts of the coalition are isolated from others. Current state-of-the-art coalition formation algorithms are not designed for problems over synergistic graphs. They assume that \emph{all} coalitions are feasible and so involve redundant computation when this is not the case. Accordingly, we propose algorithms, namely D-SlyCE and DyCE, to enumerate all feasible coalitions in a distributed fashion and find the optimal feasible coalition structure respectively. When evaluated on a variety of synergistic graphs, D-SlyCE is up to 660 times faster while DyCE is up to 7x$10^4$ times faster than the state-of-the-art algorithms. For particular classes of graphs, D-SlyCE is the first to enumerate valid coalition values for up to 50 agents and DyCE is the first algorithm to find the optimal coalition structure for up to 30 agents in minutes as opposed to months for previous algorithms.

PDF

AAMAS Conference 2012 Conference Paper

Optimal Decentralised Dispatch of Embedded Generation in the Smart Grid

  • Sam Miller
  • Sarvapali Ramchurn
  • Alex Rogers

Distribution network operators face a number of challenges; capacity constrained networks, and balancing electricity demand with generation from intermittent renewable resources. Thus, there is an increasing need for scalable approaches to facilitate optimal dispatch in the distribution network. To this end, we cast the optimal dispatch problem as a decentralised agent-based coordination problem and formalise it as a DCOP. We show how this can be decomposed as a factor graph and solved in a decentralised manner using algorithms based on the generalised distributive law; in particular, the max-sum algorithm. We go on to show that max-sum applied na\"{\i}vely in this setting performs a large number of redundant computations. To address this issue, we present a novel decentralised message passing algorithm using dynamic programming that outperforms max-sum by pruning the search space. We empirically evaluate our algorithm using real data, showing that it outperforms (in terms of computational time and total size of messages sent) both a centralised approach, which uses IBM's ILOG CPLEX 12. 2, and max-sum, for large networks.

PDF

AAAI Conference 2011 Conference Paper

A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems

  • Kathryn Macarthur
  • Ruben Stranders
  • Sarvapali Ramchurn
  • Nicholas Jennings

We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capabilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.

PDF Details

AAAI Conference 2011 Conference Paper

Decentralised Control of Micro-Storage in the Smart Grid

  • Thomas Voice
  • Perukrishnen Vytelingum
  • Sarvapali Ramchurn
  • Alex Rogers
  • Nicholas Jennings

In this paper, we propose a novel decentralised control mechanism to manage micro-storage in the smart grid. Our approach uses an adaptive pricing scheme that energy suppliers apply to home smart agents controlling micro-storage devices. In particular, we prove that the interaction between a supplier using our pricing scheme and the actions of selfish micro-storage agents forms a globally stable feedback loop that converges to an efficient equilibrium. We further propose a market strategy that allows the supplier to reduce wholesale purchasing costs without increasing the uncertainty and variance for its aggregate consumer demand. Moreover, we empirically evaluate our mechanism (based on the UK grid data) and show that it yields savings of up to 16% in energy cost for consumers using storage devices with average capacity 10 kWh. Furthermore, we show that it is robust against extreme system changes.

PDF Details