Heuristics for negotiation schedules in multi-plan optimization

Abstract

In cooperating systems such as grids [4] and collaborative streaming analysis [2], autonomous sites can establish "agreements" to arrange access to remote resources for a period of time [1]. The determination of which resources to reserve to accomplish a task need not be known a priori, because there exist multiple plans for accomplishing the same task and they may require access to different resources [3]. While these plans can be functionally equivalent, they may have different performance/cost tradeoffs and may use a variety of resources, both local and belonging to other sites. The negotiation schedule, i.e., the order in which remote resources are negotiated, determines how quickly one plan can be selected and deployed; it also decides the utility for running the plan. This paper studies the problem of optimizing negotiation schedules in cooperative systems with multiple plans. We first provide a voting-based heuristic that reduces the complexity O (n!) of the exhaustive search to O(mnq). We also present a weight-based heuristic that further reduces the complexity to O (mn). Experimental results show that, on average, I) the voting-based approach achieved 6% higher utility than the weight-based approach but the voting-based approach has a much higher computation cost than the weight-based approach, 2) the two proposed approaches achieved almost 50% higher utility than a randomized approach; and 3) the average utility produced by the two proposed approaches are within almost 90% of that of the optimal results with reasonable plan sizes. Copyright © 2008, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.