M.A. Khan, D. Turgut, and L. Bölöni

Optimizing coalition formation for tasks with dynamically evolving rewards and nondeterministic action effects


Cite as:

M.A. Khan, D. Turgut, and L. Bölöni. Optimizing coalition formation for tasks with dynamically evolving rewards and nondeterministic action effects. In Proceedings of International Workshop on Optimisation in Multi-Agent Systems (OptMas08), in conjunction with the Seventh Joint Conference on Autonomous and Multi-Agent Systems (AAMAS 2008), pp. 69–76, May 2008.

Download:

Download 

Abstract:

We consider a problem domain where coalitions of agents are formed in order to execute tasks. Each task is assigned at most one coalition of agents, and the coalition can be reorganized during execution. Executing a task means bringing it into one of the desired terminal states, which might take several time steps. The state of the task evolves even if no coalition is assigned to its execution and depends nondeterministically on the cumulative actions of the agents in the coalition. Furthermore, we assume that the reward obtained for executing a task evolves in time: typically, the more delay in the execution, the lesser the reward. We exemplify this class of problems by the allocation of firefighters to fires in a disaster rescue environment. We describe a practical methodology through which the aspects of this problem can be encoded as a Markov Decision Process. An experimental study involving the Robocup Rescue simulator shows that a coalition formation policy developed following our methodology outperforms heuristic approaches.

BibTeX:

@inproceedings{Khan-2008-OptMAS,
    author = "M.A. Khan and D. Turgut and L. B{\"o}l{\"o}ni",
    title = "Optimizing coalition formation for tasks with dynamically evolving
    rewards and nondeterministic action effects",
    booktitle = "Proceedings of International
    Workshop on Optimisation in Multi-Agent Systems (OptMas08), in conjunction
    with the Seventh Joint Conference on Autonomous and Multi-Agent Systems
    (AAMAS 2008)",
    pages = "69-76",
    month = "May",
    year = "2008",
    abstract = {
      We consider a problem domain where coalitions of agents are formed
      in order to execute tasks. Each task is assigned at most one
      coalition of agents, and the coalition can be reorganized during
      execution. Executing a task means bringing it into one of the
      desired terminal states, which might take several time steps. The
      state of the task evolves even if no coalition is assigned to its
      execution and depends nondeterministically on the cumulative
      actions of the agents in the coalition. Furthermore, we assume
      that the reward obtained for executing a task evolves in time:
      typically, the more delay in the execution, the lesser the reward.
      We exemplify this class of problems by the allocation of
      firefighters to fires in a disaster rescue environment. We
      describe a practical methodology through which the aspects of this
      problem can be encoded as a Markov Decision Process. An
      experimental study involving the Robocup Rescue simulator shows
      that a coalition formation policy developed following our
      methodology outperforms heuristic approaches.
    }
}

Generated by bib2html.pl (written by Patrick Riley, Lotzi Boloni ) on Fri Oct 06, 2017 18:15:24