Multiagent SAT (MASSAT): Autonomous pattern search in constrained domains

Xiaolong Jin, Jiming LIU

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

8 Citations (Scopus)

Abstract

In this paper, we present an autonomous pattern search approach to solving Satisfiability Problems (SATs). Our approach is essentially a multi agent system. To solve a SAT problem, we first divide variables into groups, and represent each variable group with an agent. Then, we randomly place each agent onto a position in the correspoding local space which is composed of the domains of the variables that are represented by this agent. Thereafter, all agents will autonomously make search decisions guided by some reactive rules in their local spaces until a special pattern (i.e., solution) is found or a time step threshold is reached. Experimental results on some benchmark SAT test-sets have shown that by employing the MASSAT approach, we can obtain performances comparable to those of other popular algorithms.

Original languageEnglish
Title of host publicationIntelligent Data Engineering and Automated Learning - IDEAL 2002 - 3rd International Conference, Proceedings
EditorsHujun Yin, Nigel Allinson, Richard Freeman, John Keane, Simon Hubbard
PublisherSpringer Verlag
Pages318-328
Number of pages11
ISBN (Print)9783540440253
DOIs
Publication statusPublished - 2002
Event3rd International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2002 - Manchester, United Kingdom
Duration: 12 Aug 200214 Aug 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2412
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2002
Country/TerritoryUnited Kingdom
CityManchester
Period12/08/0214/08/02

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Autonomous Pattern Search
  • MASSAT
  • Multiagent System
  • Satisfiability Problem (SAT)

Fingerprint

Dive into the research topics of 'Multiagent SAT (MASSAT): Autonomous pattern search in constrained domains'. Together they form a unique fingerprint.

Cite this