N* - an agent-based negotiation algorithm for dynamic scheduling and rescheduling

This paper presents a generalized agent-based framework that uses negotiation to dynamically and optimally schedule events. Events can be created dynamically by any active agent in the environment. Each event may potentially require collaboration or resources from one or more other agents. The allocation of resources to the event will be negotiated iteratively until a compromise is found. The framework consists of a user preference model, an evaluation or utility function, and a negotiation protocol. The negotiation protocol is used to implement a distributed negotiation algorithm, called Nstar (N*). N* is based conceptually on the A* algorithm for optimal search but extended for distributed negotiation. N* is a general distributed negotiation algorithm that makes use of negotiation strategies to find solutions that meet different negotiation objectives. For example, it can use a utility optimizing strategy to find the solution that maximizes average utilities of individual agents. Alternatively, it can select a time optimizing strategy to locate a 'quick' feasible solution. The negotiation protocol also performs conflict resolution using a form of iterative repair that renegotiates events which have conflicts. A special case of this framework was used in our MAFOA (mobile agents for office automation) environment to perform agent-based meeting scheduling. A computer simulation test bed was built to simulate the scheduling of hundreds of randomly generated meetings using our N* algorithm. (C) 2003 Elsevier Ltd. All rights reserved.