Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems

Abstract

Cooperative distributed problem solving (CDPS) loosely-coupled agents can be effectively modeled as a distributed constraint satisfaction problem (DCSP) where each agent has multiple local variables. DCSP protocols typically impose (partial) orders on agents ensure systematic exploration of the search space, but the ordering decisions can have a dramatic effect on the overall problem-solving effort. In this paper, we examine several heuristics for ordering agents, and conclude that the best heuristics attempt to order agents based on the cumulative difficulty of finding assignments to their local variables. Less costly heuristics are sometimes also effective depending on the structure of the variables ’ constraints, and we describe the tradeoffs between heuristic cost and quality. Finally, we also show that a combined heuristic, with weightings determined through a genetic algorithm, can lead to the best performance.