Asynchronous Forward-checking for DisCSPs |
| |
Authors: | Amnon Meisels Roie Zivan |
| |
Affiliation: | (1) Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, 84-105, Israel |
| |
Abstract: | A new search algorithm for solving distributed constraint satisfaction problems (DisCSPs) is presented. Agents assign variables sequentially, but perform forward checking asynchronously. The asynchronous forward-checking
algorithm (AFC) is a distributed search algorithm that keeps one consistent partial assignment at all times. Forward checking is performed
by sending copies of the partial assignment to all unassigned agents concurrently. The algorithm is described in detail and
its correctness proven. The sequential assignment method of AFC leads naturally to dynamic ordering of agents during search. Several ordering heuristics are presented. The three best heuristics
are evaluated and shown to improve the performance of AFC with static order by a large factor. An experimental comparison of AFC to asynchronous backtracking (ABT) on randomly generated DisCSPs is also presented. AFC with ordering heuristics outperforms ABT by a large factor on the harder instances of random DisCSPs. These results hold for two measures of performance: number of
non-concurrent constraints checks and number of messages sent.
Research supported by the Lynn and William Frankel Center for Computer Sciences and the Paul Ivanier Center for Robotics and
Production Management. |
| |
Keywords: | Distributed CSPs Asynchronous search Forward-checking |
本文献已被 SpringerLink 等数据库收录! |