http://swrc.ontoware.org/ontology#Article
山登り法を用いた分散制約充足における組織化
ja
dynamic organizational structure
distributed constraint satisfaction problem
hill climbing
平山 勝敏
山田 誠二
豊田 順一
Hirayama Katsutoshi
Yamada Seiji
Toyoda Jun'ichi
DCSP (Distributed Constraint Satisfaction Problem) provides a formal framework for studying cooperative distributed problem solving. Several algorithms for DCSP have been proposed. This paper presents a new method, LMO (Local Minimum driven Organizing), to solve DCSP. The basic algorithm is iterative improvement. Each agent measures the cost of its own instantiations as the number of violated constraints. If local change of instantiations reduces the cost, the agent performs hill-climbing locally. The advantage of this method is that agents solve their local problems in Parallel. 0ne drawback, however, is the possibility of getting caught in local minima. LMO provides a technique for escaping from local minima. It is summarized as follows. When an agent (A1) gets caught in a local minimum, 1) A1 sends its local CSP to the agent (A2) that shares a violated constraint with it, 2) A2 puts their CSPs together and solve them by a brute-force search.It eliminates local minima from search spaces, alters a hill-climbing for a brute-force search, and reduces communication overhead at the cost of the parallel execution. It is triggered by a local minimum, therefore the more local minima agents get caught, the more CSPs are put together and solved with a brute-force search. This means that the algorithm is adaptable to the problem it solves. In this paper, we verify this fact experimentally.
人工知能学会誌
10
1
80-87
1995-01-01
09128085
AN10067140
KJ00001301814