TY - JOUR
T1 - Distributed problem solving without communication - An examination of computationally hard satisfiability problems
AU - Liu, Jiming
AU - Jin, Xiaolong
AU - Han, Jing
N1 - Funding Information:
This work has been supported in part by HKBU FRG research grants.
PY - 2002/12
Y1 - 2002/12
N2 - 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.
AB - 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.
KW - Distributed problem solving
KW - ERA
KW - Multiagent system
KW - Propositional satisfiability problem (SAT)
KW - Self-organization
UR - http://www.scopus.com/inward/record.url?scp=0036973699&partnerID=8YFLogxK
U2 - 10.1142/S0218001402002143
DO - 10.1142/S0218001402002143
M3 - Journal article
AN - SCOPUS:0036973699
SN - 0218-0014
VL - 16
SP - 1041
EP - 1064
JO - International Journal of Pattern Recognition and Artificial Intelligence
JF - International Journal of Pattern Recognition and Artificial Intelligence
IS - 8
ER -