A Tractable Heuristic that Maximizes Global Utility through Local Plan Combination
Eithan Ephrati, Martha E. Pollack, Jeffrey S. Rosenschein · 1995
We consider techniques suitable for combining individual agent plans into a global system plan, maintaining a commitment to considerations of global utility that may differ radically from individual agent utilities. We present a three-stage heuristic reduction process, consisting of a transformation from local to global utility measures, a global assessment of the local evaluations of agents, and approximation algorithms to maximize resource usage over time. We also consider how these techniques can be used with self-motivated agents, and show how the overall process can be distributed among a group of agents. Introduction Distributed Artificial Intelligence (DAI) has traditionally considered the global utility of a system as strongly connected to the local utilities of the agents that comprise that system. So, for example, the sum (or product) of agent utilities might be maximized by the designers of an interaction environment (Rosenschein & Zlotkin 1994), even when the agents themse...