Dynamic DFS Tree in ADOPT-ing

Marius C Silaghi, Makoto Yokoo

Several distributed constraint reasoning algorithms employ Depth First Search (DFS) trees on the constraint graph that spans involved agents. In this article we show that it is possible to dynamically detect a minimal DFS tree, compatible with the current order on agents, during the distributed constraint reasoning process of the ADOPT algorithm. This also allows for shorter DFS trees during the initial steps of the algorithm, while some constraints did not yet prove useful given visited combinations of assignments. Earlier distributed algorithms for finding spanning trees on agents did not look to maintain compatibility with an order already used. We also show that announcing a nogood to a single optional agent is bringing significant improvements in the total number of messages. The dynamic detection of the DFS tree brings improvements in simulated time.

Subjects: 7.1 Multi-Agent Systems; 15.2 Constraint Satisfaction

Submitted: Apr 24, 2007


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.