Dynamic ordering for asynchronous backtracking on DisCSPs

被引：21

作者：

Zivan, Roie ^{[1
]}

Meisels, Amnon ^{[1
]}

机构：

[1] Ben Gurion Univ Negev, Dept Comp Sci, IL-84105 Beer Sheva, Israel

来源：

CONSTRAINTS | 2006年 / 11卷 / 2-3期

关键词：

distributed constraint satisfaction; distributed AI; search;

D O I：

10.1007/s10601-006-8062-0

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

An algorithm that performs asynchronous backtracking on distributed CSPs, with dynamic ordering of agents is proposed, ABT_DO. Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. Changes of ordering triggers a different computation of Nogoods. The dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard ABT. The ABT_DO algorithm with three different ordering heuristics is compared to standard ABT on randomly generated DisCSPs. A Nogood-triggered heuristic, inspired by dynamic backtracking, is found to outperform static order ABT by a large factor in run-time and improve the network load.

引用

页码：179 / 197

页数：19

共 29 条

[1]

Bacchus F., 1995, Principles and Practice of Constraint Programming - CP '95. First International Conference, CP'95. Proceedings, P258

[2] Asynchronous backtracking without adding links:: a new member in the ABT family [J].

Bessière, C ;

Maestre, A ;

Brito, I ;

Meseguer, P .

ARTIFICIAL INTELLIGENCE, 2005, 161 (1-2) :7-24

[3]

BESSIERE C, 1995, LNCS, V923, P157

[4]

BESSIERE C, 2001, P WORKSH DISTR CONST

[5]

BRITO I, 2004, WORKSH DISTR CONSTR

[6]

Dechter R., 2003, CONSTRAINT PROCESSIN

[7]

FROST D, 1994, PROCEEDINGS OF THE TWELFTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOLS 1 AND 2, P301

[8]

Gent I. P., 1996, Principles and Practice of Constraint Programming - CP96. Second International Conference - CP96. Proceedings, P179

[9] Dynamic Backtracking [J].

Ginsberg, Matthew L. .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 1993, 1 :25-46

[10]

Hamadi Y, 1998, ECAI 1998: 13TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, PROCEEDINGS, P219

← 1 2 3 →