In multiagent systems a coalition structure is a collection of pair-wise disjoint subsets of agents whose union yields the entire population. Given a characteristic function quantifying the worth of agent subsets, searching for optimal coalition structures (i.e. where the sum of subsets’ worth is maximal) is a well-known NP-hard combinatorial optimization problem. While existing algorithms (either deterministic or stochastic) deal with time-invariant goal functions, the focus here is on dynamic settings, where the worth of agent subsets possibly varies over time in an unknown and unpredictable fashion. The aim is to design an adaptive dynamic process generating coalition structures with high worth most of the times. To this end, detecting variations in the worth of agent subsets becomes crucial. The proposed method takes into account such (possible) changes by intensifying the exploration activity whenever they are detected. The performance with respect to the worth of optimal coalition structures is evaluated through simulations.

Adaptive Coalition Structure Generation in Cooperative Multiagent Systems

D'ANGELO, GABRIELE
2008

Abstract

In multiagent systems a coalition structure is a collection of pair-wise disjoint subsets of agents whose union yields the entire population. Given a characteristic function quantifying the worth of agent subsets, searching for optimal coalition structures (i.e. where the sum of subsets’ worth is maximal) is a well-known NP-hard combinatorial optimization problem. While existing algorithms (either deterministic or stochastic) deal with time-invariant goal functions, the focus here is on dynamic settings, where the worth of agent subsets possibly varies over time in an unknown and unpredictable fashion. The aim is to design an adaptive dynamic process generating coalition structures with high worth most of the times. To this end, detecting variations in the worth of agent subsets becomes crucial. The proposed method takes into account such (possible) changes by intensifying the exploration activity whenever they are detected. The performance with respect to the worth of optimal coalition structures is evaluated through simulations.
Proceedings of 4th International Conference on Self-organization and Adaptation of Computing and Communications (SACC 2008)
116
122
G. Rossi; G. D'Angelo
File in questo prodotto:
Eventuali allegati, non sono esposti

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: http://hdl.handle.net/11585/65388
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact