NoGood Caching for MultiAgent Backtrack Search

William S. Havens

Multiagent solutions to the distributed constraint satisfaction problem (DCSP) require new types of techniques which accommodate the local autonomy of agents and the difficulties of computing in a network environment. Recently a technique called asynchronous backtracking has been developed to solve the DCSP. The algorithm works by sending nogood messages among agents to effect intelligent backtracking. One important issue is developing nogood caching schemes which are appropriate to asynchronous backtracking. There has also been recent progress in a sequential algorithm called dynamic backtracking which exhibits a polynomial bound on nogood cache size. In this paper, we show by example that the existing caching scheme used by dynamic backtracking is not appropriate for the multiagent context. We suggest two alternate nogood caching schemes and two caching algorithms based on these schemes. Experimental comparisons of these caching algorithms are forthcoming.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.