Min-domain ordering for asynchronous backtracking Academic Article uri icon


  • Ordering heuristics are a powerful tool in CSP search algorithms. Among the most successful ordering heuristics are heuristics which enforce a fail first strategy by using the min-domain property [10, 4, 20, 6]. Ordering heuristics have been introduced recently to Asynchronous backtracking (ABT), for distributed constraints satisfaction (DisCSP)[27]. However, the pioneering study of dynamically ordered ABT, ABT _ DO, has shown that a straightforward implementation of the min-domain heuristic does not produce the expected improvement over a static ordering. The best ordering heuristic for asynchronous backtracking was found to be the Nogood-triggered heuristic. The present paper proposes an asynchronous dynamic ordering which does not follow the standard restrictions on the position of reordered agents in ABT _ DO. Agents can be moved to a position that is …

publication date

  • September 23, 2007