Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Iterative AWC for distributed SAT
KTH.
2017 (English)In: 20th International Conference of the Catalan Association for Artificial Intelligence, CCIA 2017, IOS Press , 2017, p. 56-65Conference paper, Published paper (Refereed)
Abstract [en]

Traversing large search spaces can be done more efficiently by exploiting the dead-ends –in formal terms nogoods– discovered during search. If a previously found nogood appears again, the search process can avoid it, saving some search effort. Storing all found nogoods may require exponential memory, which is unaffordable. However, current memories allow to store a large set of nogoods, to be maintained during the solving process. In many cases, a solution is found before memory is exhausted. In the context of Distributed Constraint Satisfaction, the AWC algorithm allows to compute a solution quickly but, to guarantee completeness, it requires storing all found nogoods. Trading space per time, we develop a new iterative version of the algorithm that delays the exponential effects. We present this new version in the context of distributed SAT, where agents hold several Boolean variables. Taking advantage of existing SAT technology, this version perform calls to external MaxSAT solver. Experimentally, we confirm the benefits of the proposed approach on several benchmarks.

Place, publisher, year, edition, pages
IOS Press , 2017. p. 56-65
Keyword [en]
AWC algorithm, Distributed CSP, Distributed SAT, MaxSAT solver, SAT solver, Artificial intelligence, Constraint satisfaction problems, Problem solving, Boolean variables, Distributed constraint satisfaction, Exponential effects, Max-SAT, SAT solvers, Search efforts, Iterative methods
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-222918DOI: 10.3233/978-1-61499-806-8-56Scopus ID: 2-s2.0-85034267941ISBN: 9781614998051 OAI: oai:DiVA.org:kth-222918DiVA, id: diva2:1193936
Conference
25 October 2017 through 27 October 2017
Note

QC 20180328

Available from: 2018-03-28 Created: 2018-03-28 Last updated: 2018-03-28Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Giráldez-Cru, Jesús
By organisation
KTH
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 1 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf