第7章 競合解消

参考

SmallOPS を発展させた Toy Open Production SystemSourceForge.jp にて公開しています。

また、本コンテンツを書くに辺り、以下の参考書を参考にしています。

7. 1. SmallOPSにおける競合解消と競合集合

SmallOPSでは競合を解消する戦略としてfractionとfirst matchを採用している。 fractionは一度実行した例化を二度以上実行しない戦略であり、 first matchは最初にマッチした例化を実行する戦略である。 ここで注目するのはfirst match戦略を採用している点である。 first matchは最初にマッチした例化を実行するため、 実際には競合集合を求めずに最初に例化が行われた時点でマッチングを終了することができる。 従って、SmallOPSにおいて競合集合を求めることは絶対的に必要な条件ではない。 しかし、SmallOPSでは状況に応じて競合集合の探索を打ち切ることができる機構を採用している。 これによって最初の例化で競合集合の探索を打ち切ったり、 全ての競合集合を求めたてから競合解消を行ったりできる。


7. 2. 競合集合

競合集合は、 ルールベースに蓄積されたプロダクションルールとワーキングメモリに蓄積された事実との マッチングによって得られた例化の集合である。 一つの例化は、3段階に分けて考えることができる。 ルールベースに蓄積されたプロダクションルールは複数であり、 どのプロダクションルールが例化されるのかがまず1段階目である。 プロダクションルールは複数の条件を持っているため、 どの条件がマッチングされるのかが次の2段階目である。 ワーキングメモリに蓄積された事実は複数であり、 どの事実と条件がマッチングされるのかが3段階目である。 以上の各段階における処理を行うクラスのクラス図を以下に示す。



図1: 競合集合のクラス図

ConflictSetクラスは、どのプロダクションルールを例化するかを決定するクラスである。 ConflictSetクラスは、例化が一つ見つかると処理を終え、その例化を返す。 そのときConflictSetクラスは探索を終えた場所を覚えているため、 次に再び例化の必要性が出たときはそこから探索を再開し新しい例化を取得できる。 また、もしそれ以上の例化が必要なければそこで例化を中断することができる。

ConflictSetクラスは、ルールベースに入れられた順にプロダクションルールを調べていく。 プロダクションルールを順々に変えながら例化を試みている実際のC++コードを以下に示す。

bool ConflictSet::instantiateByCurrentUnificator(InstancePtr& instance) {
  UnificationResultPtr unificationResult;
  if(unificator_->unificate(unificationResult)) {
    instance=InstancePtr(new Instance(*i_, unificationResult));
    return true;
  } else {
    return false;
  }
}

bool ConflictSet::instantiate(InstancePtr& instance) {
  if(instantiateByCurrentUnificator(instance)) return true;

  while(++i_!=owner_.getRuleBase().end()) {
    unificator_=UnificatorPtr(new Unificator(owner_.getWorkingMemory(), (*i_)->getConditionPart()));
    if(instantiateByCurrentUnificator(instance)) return true;
  }

  return false;
}

ConflictSetクラスは、例化をするべきかどうかの判断をUnificatorインスタンスに委譲している。 Unificatorクラスには、 ワーキングメモリと例化の判断対象となっているプロダクションルールの条件部によって生成され、 単一化によって条件部が満たされるか否かを判断する。 UnificatorクラスもConflictSetクラス同様に一つの単一化が終了すると探索を終えた場所を覚えているため、 次に再び単一化の必要性が出たときはそこから探索を再開し新しい単一化を実行できる。

Unificatorクラスの中では同じようにしてUnificatorSubインスタンスが生成され、 条件が満たされるか否かが判断されそれを返している。 これらの3つのクラスによって例化は生成されている。


7. 3. 競合解消

競合解消は、競合集合から発火する例化を一つ選択することであるが、 その方法はいくつか考えられており競合解消戦略と呼ばれている。 競合解消に関わるクラスのクラス図を以下に示す。



図2: 競合解消のクラス図

ConflictResolutionStrategyクラスは、 以上のConflictSetインスタンスを使って競合解消を行う競合解消戦略クラスである。 競合解消戦略にはいろいろなものがあるので、ConflictResolutionStrategyクラスは抽象クラスである。 そこで、SmallOPSの競合戦略を実行するクラスとしてSmallConflictResolutionStrategyクラスが定義されている。 resolveメソッドがその競合解消を行うメソッドであり、対応するC++のソースコードを以下に示す。

bool SmallStrategy::resolve(ConflictSet& conflictSet, InstancePtr& result) {
  while(conflictSet.instantiate(result)) {
    if(!history_.isClosed(*result)) {
      history_.add(*result);
      return true;
    }
  }

  return false;
}

SmallConflictResolutionStrategyクラスはHistoryクラスを持っているが、 これはfraction戦略を実現するために例化の履歴をとっておくためのものである。 SmallConflictResolutionStrategyクラスのresolveメソッドでは、 まず競合集合から一つ例化を取得し、 それが履歴に無い場合はその例化を履歴に追加し、 すぐに競合が解消されたとして終了していることがわかる。

SmallRuleInterpreterクラスは、 SmallConflictResolutionStrategyインスタンスを用いて競合解消を行い推論を実行するルールインタプリタである。 それに対応するC++のソースコードを以下に示す。

SmallRuleInterpreter::SmallRuleInterpreter(ProductionSystem& owner) :
RuleInterpreter(owner), i_(owner.getRuleBase().begin()),
strategy_(new SmallStrategy()) {
}

ConflictResolutionStrategyPtr SmallRuleInterpreter::getStrategy() {
  return strategy_;
}

SmallRuleInterpreterクラスは、コンストラクタで戦略としてSmallStrategyインスタンスを構築し、 毎回それを使っていることがわかる。


7. 4. 新しい競合解消戦略を定義する

SmallRuleInterpreterクラスとSmallConflictResolutionStrategyクラスで見てきたように、 競合解消戦略を定義することは比較的簡単である。 新しい競合解消戦略を定義するためには、 まずRuleInterpreterクラスとConflictResolutionStrategyクラスの双方の子クラスを一つずつ構築する。 さらに、RuleInterpreterクラスのgetStrategyメソッドをオーバーライドし ConflictResolutionStrategyインスタンスを返す記述を書く。 また、ConflictResolutionStrategyクラスではresolveメソッドをオーバーライドし 具体的な競合解消戦略を書けば良い。

さらに複雑な機構として RuleInterpreterクラスのgetStrategyメソッドで複数の戦略を状況によって選択させるという方法も考えられる。 これを混合型競合解消戦略という。


前へ:行動
次へ:最後に