In this paper we address the problem of decentralised coordination for agents that must make coordinated decisions over continuously valued control parameters (as is required in many real world applications). In particular, we tackle the social welfare maximisation problem, and derive a novel continuous version of the max-sum algorithm. In order to do so, we represent the utility function of the agents by multivariate piecewise linear functions, which in turn are encoded as simplexes. We then derive analytical solutions for the fundamental operations required to implement the max-sum algorithm (specifically, addition and marginal maximisation of general n-ary piecewise linear functions). We empirically evaluate our approach on a simulated network of wireless, energy constrained sensors that must coordinate their sense/sleep cycles in order to maximise the system-wide probability of event detection. We compare the conventional discrete max-sum algorithm with our novel continuous version, and show that the continuous approach obtains more accurate solutions (up to a 10% increase) with a lower communication overhead (up to half of the total message size).

Decentralised coordination of continuously valued control parameters using the max-sum algorithm

FARINELLI, Alessandro;
2009-01-01

Abstract

In this paper we address the problem of decentralised coordination for agents that must make coordinated decisions over continuously valued control parameters (as is required in many real world applications). In particular, we tackle the social welfare maximisation problem, and derive a novel continuous version of the max-sum algorithm. In order to do so, we represent the utility function of the agents by multivariate piecewise linear functions, which in turn are encoded as simplexes. We then derive analytical solutions for the fundamental operations required to implement the max-sum algorithm (specifically, addition and marginal maximisation of general n-ary piecewise linear functions). We empirically evaluate our approach on a simulated network of wireless, energy constrained sensors that must coordinate their sense/sleep cycles in order to maximise the system-wide probability of event detection. We compare the conventional discrete max-sum algorithm with our novel continuous version, and show that the continuous approach obtains more accurate solutions (up to a 10% increase) with a lower communication overhead (up to half of the total message size).
2009
978-0-9817381-6-1
Max-Sum; Decentralised Coordination; Multi Agent Systems
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/340157
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? ND
social impact