Distributed problem solving without communication - An examination of computationally hard satisfiability problems

Jiming LIU*, Xiaolong Jin, Jing Han

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

2 Citations (Scopus)

Abstract

In this paper, we extend and modify the ERA approach proposed in Ref. 13 to solve Propositional Satisfiability Problems (SATs). The new ERA approach involves a multiagent system where each agent only senses its local environment and applies some self-organizing rules for governing its movements. The environment, which is a two-dimensional cellular environment, records and updates the local values that are computed and affected according to the movements of individual agents. In solving a SAT with the ERA approach, we first divide variables into several groups, and represent each variable group with an agent whose possible positions correspond to the elements in a Cartesian product of variable domains, and then randomly place each agent onto one of its possible positions. Thereafter, the ERA system will keep on dispatching agents to choose their movements until an exact or approximate solution emerges. The experimental results on some benchmark SAT test-sets have shown that the ERA approach can obtain comparable results as well as stable performances for SAT problems. In particular, it can find approximate solutions for SAT problems in only a few steps. The real value of this approach is that it is a distributed asynchronous approach without any centralized control or evaluation, where the agents can cooperate to solve problems without explicit communication.

Original languageEnglish
Pages (from-to)1041-1064
Number of pages24
JournalInternational Journal of Pattern Recognition and Artificial Intelligence
Volume16
Issue number8
DOIs
Publication statusPublished - Dec 2002

Scopus Subject Areas

  • Software
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

User-Defined Keywords

  • Distributed problem solving
  • ERA
  • Multiagent system
  • Propositional satisfiability problem (SAT)
  • Self-organization

Fingerprint

Dive into the research topics of 'Distributed problem solving without communication - An examination of computationally hard satisfiability problems'. Together they form a unique fingerprint.

Cite this