分散制約充足におけるエージェントの非集中的組織化

概要

論文の詳細を見る
We have proposed LMO (Local Minimum driven Organizing) as a group forming mechanism for agents that solve Distributed Constraint Satisfaction problems. 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, 2) A2 puts their CSP together and searches for all possible assignments with simple backtracking. One flaw of LMO is that the cost of search grows exponentially with the number of CSP being put together. To cope with this flaw we extend our method as follows and introduce the dynamically weight adjusting strategy : ・ We associate a weight with each constraint. The weights have 1 as their initial values ; ・ We measure the cost of instantiation as the sum of weights of violated constraints ; ・ Strategy : after putting CSP together, A2 sends neighbors the number of variables or the size of domain ; neighbors reassign it for the weights of constraints being shared with A2. The result of the experiment on distributed 3-coloring problem was that this strategy tended to protect against concentration of CSP and reduced the cost of search.
社団法人人工知能学会の論文
1995-07-01