Ruben Stranders

AAMAS Conference 2013 Conference Paper

Introducing Alarms in Adversarial Patrolling Games

• Enrique Munoz de Cote
• Ruben Stranders
• Nicola Basilico
• Nicola Gatti
• NICK JENNINGS

Adversarial patrolling games (APGs) can be modeled as Stackelberg games where a patroller and an intruder compete. The former moves with the aim of detecting an intrusion, while the latter tries to intrude without being detected. In this paper, we introduce alarms in APGs, namely devices that can remotely inform the patroller about the presence of the intruder at some location. We introduce a basic model, provide an extended formulation of the problem and show how it can be cast as partially observable stochastic game. We then introduce the general resolution approach.

AAMAS Conference 2012 Conference Paper

DCOPs and Bandits: Exploration and Exploitation in Decentralised Coordination

• Ruben Stranders
• Long Tran-Thanh
• Francesco Maria Delle Fave
• Alex Rogers
• NICK JENNINGS

Real life coordination problems are characterised by stochasticity and a lack of \emph{a priori} knowledge about the interactions between agents. However, decentralised constraint optimisation problems (DCOPs), a widely accepted framework for modelling decentralised coordination problems, assumes perfect knowledge, thus limiting its practical applicability. To address this shortcoming, we introduce the MAB-DCOP, in which the interactions between agents are modelled by multi-armed bandits (MABs). Unlike canonical DCOPs, a MAB-DCOP is not a single shot optimisation problem. Rather, it is a sequential one in which agents need to coordinate in order to strike a balance between acquiring knowledge about the \emph{a priori} unknown and stochastic interactions (exploration), and taking the currently believed optimal joint action (exploitation), so as to maximise the cumulative global utility over a finite time horizon. We propose \textsc{Heist}, the first asymptotically optimal algorithm for coordination under stochasticity and lack of prior knowledge. \textsc{Heist} solves MAB-DCOPs in a decentralised fashion using a generalised distributive law (GDL) message passing phase to find the joint action with the highest upper confidence bound (UCB) on global utility. We demonstrate that \textsc{Heist} outperforms other state of the art techniques from the MAB and DCOP literature by up to 1. 5 orders of magnitude on MAB-DCOPs in experimental settings.

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.

AAMAS Conference 2011 Conference Paper

Bounded Decentralised Coordination over Multiple Objectives

• Francesco M. Delle Fave
• Ruben Stranders
• Alex Rogers
• Nicholas R. Jennings

We propose the bounded multi-objective max-sum algorithm (B-MOMS), the first decentralised coordination algorithm for multi-objective optimisation problems. B-MOMS extends the max-sum message-passing algorithm for decentralised coordination to compute bounded approximate solutions to multi-objective decentralised constraint optimisation problems (MO-DCOPs). Specifically, we prove the optimality of B-MOMS in acyclic constraint graphs, and derive problem dependent bounds on its approximation ratio when these graphs contain cycles. Furthermore, we empirically evaluate its performance on a multi-objective extension of the canonical graph colouring problem. In so doing, we demonstrate that, for the settings we consider, the approximation ratio never exceeds 2, and is typically less than 1. 5 for less-constrained graphs. Moreover, the runtime required by B-MOMS on the problem instances we considered never exceeds 30 minutes, even for maximally constrained graphs with 100 agents. Thus, B-MOMS brings the problem of multi-objective optimisation well within the boundaries of the limited capabilities of embedded agents.

AAMAS Conference 2010 Conference Paper

A Decentralised Coordination Algorithm for Minimising Conflict and Maximising Coverage in Sensor Networks

• Ruben Stranders
• Alex Rogers
• Nicholas R. Jennings

In large wireless sensor networks, the problem of assigning radiofrequencies to sensing agents such that no two connected sensorsare assigned the same value (and will thus interfere with one another) is a major challenge. To tackle this problem, we developa novel decentralised coordination algorithm that activates only asubset of the deployed agents, subject to the connectivity graphof this subset being provably 3-colourable in linear time, henceallowing the use of a simple decentralised graph colouring algorithm. Crucially, while doing this, our algorithm maximises thesensing coverage achieved by the selected sensing agents, whichis given by an arbitrary non-decreasing submodular set function. We empirically evaluate our algorithm by benchmarking it againsta centralised greedy algorithm and an optimal one, and show thatthe selected sensing agents manage to achieve 90\% of the coverage provided by the optimal algorithm, and 85\% of the coverageprovided by activating all sensors. Moreover, we use a simple decentralised graph colouring algorithm to show the frequency assignment problem is easy in the resulting graphs; in all consideredproblem instances, this algorithm managed to find a colouring inless than 5 iterations on average. We then show how the algorithmcan be used in dynamic settings, in which sensors can fail or newsensors can be deployed. In this setting, our algorithm provides250\% more coverage over time compared to activating all availablesensors simultaneously.

AAAI Conference 2010 Conference Paper

A Decentralised Coordination Algorithm for Mobile Sensors

• Ruben Stranders
• Francesco Delle Fave
• Alex Rogers
• Nicholas Jennings

We present an on-line decentralised algorithm for coordinating mobile sensors for a broad class of information gathering tasks. These sensors can be deployed in unknown and possibly hostile environments, where uncertainty and dynamism are endemic. Such environments are common in the areas of disaster response and military surveillance. Our coordination approach itself is based on work by Stranders et al. (2009), that uses the max-sum algorithm to coordinate mobile sensors for monitoring spatial phenomena. In particular, we generalise and extend their approach to any domain where measurements can be valued. Also, we introduce a clustering approach that allows sensors to negotiate over paths to the most relevant locations, as opposed to a set of fixed directions, which results in a significantly improved performance. We demonstrate our algorithm by applying it to two challenging and distinct information gathering tasks. In the first–pursuit-evasion (PE)–sensors need to capture a target whose movement might be unknown. In the second– patrolling (P)–sensors need to minimise loss from intrusions that occur within their environment. In doing so, we obtain the first decentralised coordination algorithms for these domains. Finally, in each domain, we empirically evaluate our approach in a simulated environment, and show that it outperforms two state of the art greedy algorithms by 30% (PE) and 44% (P), and an existing approach based on the Travelling Salesman Problem by 52% (PE) and 30% (P).

ECAI Conference 2010 Conference Paper

A Hybrid Continuous Max-Sum Algorithm for Decentralised Coordination

• Thomas Voice
• Ruben Stranders
• Alex Rogers
• Nicholas R. Jennings

In this paper we tackle the problem of coordinating multiple decentralised agents with continuous state variables. Specifically we propose a hybrid approach, which combines the max-sum algorithm with continuous non-linear optimisation methods. We show that, for problems with acyclic factor graph representations, for suitable parameter choices and sufficiently fine state space discretisations, our proposed algorithm converges to a state with utility close to the global optimum. We empirically evaluate our approach for cyclic constraint graphs in a multi-sensor target classification problem, and compare its performance to the discrete max-sum algorithm, as well as a non-oordinated approach and the distributed stochastic algorithm (DSA). We show that our hybrid max-sum algorithm outperforms the non-coordinated algorithm, DSA and discrete max-sum by up to 40% in this problem domain. Furthermore, the improvements in outcome over discrete max-sum come without significant increases in running time nor communication cost.

IJCAI Conference 2009 Conference Paper

• Ruben Stranders
• Alessandro Farinelli
• Alex Rogers
• Nicholas R. Jennings

In this paper, we introduce an on-line, decentralised coordination algorithm for monitoring and predicting the state of spatial phenomena by a team of mobile sensors. These sensors have their application domain in disaster response, where strict time constraints prohibit path planning in advance. The algorithm enables sensors to coordinate their movements with their direct neighbours to maximise the collective information gain, while predicting measurements at unobserved locations using a Gaussian process. It builds upon the max-sum message passing algorithm for decentralised coordination, for which we present two new generic pruning techniques that result in speed-up of up to 92% for 5 sensors. We empirically evaluate our algorithm against several on-line adaptive coordination mechanisms, and report a reduction in root mean squared error up to 50% compared to a greedy strategy.