Predicting tradeoffs in contract-based distributed scheduling.
Sandip Sen · Deep Blue (University of Michigan) · 1993
We are interested in building intelligent, autonomous software agents that can relieve human users from the burden of routine, tedious information processing activities in organizations. As part of that research agenda, we present in this thesis results of our investigations in building autonomous agents for the problem domain of distributed scheduling. In particular, we have analyzed in detail the real-life domain of distributed meeting scheduling, in which autonomous, partially cooperative meeting scheduling agents negotiate with each other to schedule dynamically arriving meeting requests. To be effective and useful in such domains, autonomous agents need to use a structured information exchange mechanism that helps them quickly identify solutions to individual and global goals, as well as provide the capability to explain their actions to associated users on demand. Our agents achieve these capabilities by using the contract-net protocol, which has been used widely to coordinate the activities of agents in distributed problem-solving systems. To effectively implement this protocol in the distributed scheduling domain, we address each of the critical problem-solving aspects of a contracting agent: how to structure and search for contract proposals in the solution space, how much information to exchange to quickly converge the negotiation process without incurring excessive communication cost, how to bid effectively against announced contracts, how to represent and reason about tentative proposals, and when to withdraw past commitments if faced with new contingencies. We investigate heuristic strategy dimensions to control each of the above aspects of local problem solving. By using a finite state automata model of contracting agents, we precisely represent the processing stages, the resource requirements, and the interaction possibilities between meeting scheduling agents. We also develop probabilistic estimates of the performance of heuristic strategy options under a variety of environmental and local problem-solving conditions. We demonstrate the necessity of adaptive scheduling by showing that a static choice of strategy combinations leads to increasingly ineffective problem solving over time. As a remedial measure, we outline the design of an intelligent, adaptive scheduling agent that chooses from available strategy options to optimize certain performance measures for each new meeting it is asked to schedule.