2001 · 72 citations · 9 references
ComputingComputer SystemsDistributed SystemsGame TheorySchedulingDistributed SchedulingDynamic SchedulingResource AllocationResource SchedulingTask AllocationTask SchedulingAdaptive AllocationAdaptive Resource AllocationDynamic Resource AllocationDynamic Task AllocationMulti-agent Resource AllocationMulti-agent SchedulingOrganizational Policy DesignTask Allocation Policies
In this paper, we present an adaptive organizational policy for multi-agent systems called \acro{trace}. \acro{trace} allows a collection of multi-agent organizations to dynamically allocate tasks and resources between themselves in order to efficiently process an incoming stream of task requests. \acro{trace} is intended to cope with environments in which tasks have time constraints, and environments that are subject to load variations. \acro{trace} is made up of two key elements: the task allocation protocol (\acro{tap}) and the resource allocation protocol (\acro{rap}). The \acro{tap} allows agents to cooperatively allocate their tasks to other agents with the capability and opportunity to successfully carry them out. As requests arrive arbitrarily, at any instant, some organizations could have surplus resources while others could become overloaded. In order to minimize the number of lost requests caused by an overload, the allocation of resources to organizations is changed dynamically by the resource allocation protocol (\acro{rap}), which uses ideas from computational market systems to allocate resources (in the form of problem solving agents) to organizations. We begin by formally defining the task allocation problem, and show that it is \acro{NP}-complete, and hence that centralized solutions to the problem are unlikely to be feasible. We then introduce the task and resource allocation protocols, focussing on the way in which resources are allocated by the \acro{rap}. We then present some experimental results, which show that \acro{trace} exhibits high performance despite unanticipated changes in the environment.
9
Mobile software agents: an overview
Vu Anh Pham, A. Karmouch · IEEE Communications Magazine · 1998 · 472 citations
A market protocol for decentralized task allocation
William E. Walsh, Michael P. Wellman · 2002 · 155 citations