| 平成９年度 委託研究ソフトウェアの提案 |
| 研究代表者： | 松岡 聡 助教授 |
| 東京工業大学大学院 情報理工学研究科 数理・計算科学専攻 |
制約とは宣言的関係として表現された知識であり，とくに自動管理メカニズム による知識処理手法の提供を意図するものである．制約に関する研究は，1970 年代後半のSussmanとSteeleによるCONSTRAINTSシステムや，Borningによる ThingLabシステムなどの研究に始まり，1980年代後半にJaffarらのCLP(R)に代 表される制約論理型言語の登場によりさらなる盛上りを見せ，知識処理研究に おける最重要分野の1つとして広く認識されるようになった．その応用はエキ スパートシステムのような知識処理だけでなく，対話型ユーザーインターフェ ースの構築や，ドローイングツールのようなエンドユーザー向けアプリケーシ ョンにおける利用など多種多様であり，今後ますますの広がりが期待される．
制約ベースのシステムの能力を特徴付ける最も基本的な基準として，従来多く のシステムで採用されてきた古典的な単調制約解消と，制約階層などのより先 進的な非単調制約解消がある．非単調制約解消では，いわゆるデフォルトの制 約を扱うことができる．一般に制約を過不足なく指定することは困難であり， 柔軟な解集合の制御を実現する非単調制約解消は，複雑な実世界の問題のモデ ル化により適している．とくに制約階層は，強さと呼ばれる優先度を表現する ための任意個のレベルを提供する，理論的に洗練された体系を持ち，同時に DeltaBlueなどの効率的な制約解消アルゴリズムが存在することで知られ，階 層的制約論理型言語や対話型ユーザーインターフェースへの応用が盛んに研究 されている．
制約階層には効率的な解消系が多数開発されている．とくに，Borningらの DeltaBlueアルゴリズムに起源する，局所伝播法というグラフアルゴリズムに 基づく制約解消系に関して様々な研究が行われてきた．局所伝播法は，多方向 制約と呼ばれるデータフロー制約を扱い，制約階層をデータフローグラフとし て管理する．
一方，制約階層を効率的に解く数値的解消系はほとんど見られない．1次方程 式からなる制約階層を扱うシステムは数多いが，このような理由により，その 多くが局所伝播法に基づく制約解消系を採用している．しかし，局所伝播法で 扱う多方向制約は1次方程式とは本質的に異なるため，実行時に誤った解が得 られたり，エラーで停止するなどの問題が生じ，システムの信頼性が低下する．
本研究の目的は，1次方程式からなる制約階層を解く健全かつ完全な解消系を 開発することである．我々はすでに，階層連立1次方程式(hierarhical linear system，HLS)という，1次方程式からなる制約階層に関する新しい定式化を提 案し，消去法とLU分解による2種類の健全かつ完全なアルゴリズムを設計した [1]．HLSの理論およびアルゴリズムは線形代数と線形計算を基礎としており， 従来のグラフ理論を基礎とする局所伝播法と異なり，1次方程式を適切に扱う ことができるという特徴を持つ．本研究では，HLSの理論とアルゴリズムを活 かして信頼性の高く効率的な制約解消系を実装し，制約ベースシステムの開発 者が容易に制約階層を導入できるよう，実用的なパッケージとして制約解消系 を提供することを目標とする．
最初に，制約階層の1次方程式への特殊化として我々が[1]で提案した階層連立 1次方程式(HLS)の理論について説明する．HLSは，n個の変数x1，x2，…，xnに 関する以下のようなm個の1次方程式の順序集合として定義される．
ここでaijは第i方程式における第j変数の係数を，ciは第i方程式の定数項を表 している．直観的には，iが大きいほど方程式は弱い．この性質は次のように 解を定義することにより得られる．以下で，ak = (ak1, ak2, … , akn)とす る．
x = (x1，x2，…，xn)が上のHLSの解であるのは次の条件が成立するときであ り，かつそのときに限る．
ただし，hdep(i) (第i方程式が階層従属である)は，次のように定義される．
この定義により，第i方程式が階層従属であるとき，その係数は先行する方程 式の係数に対して1次従属である．ゆえに，第i方程式は先行する式に対して冗 長であるか，矛盾しているかの一方である．よって，解の条件は，先行する方 程式に矛盾する式を無視することと解釈できる．この条件は制約階層の理論に おけるlocally-predicate-betterという基準に対応することが証明でき，HLS は制約階層の特殊化として理論的に説明できる．
さらに我々はHLSを解く2種類の健全かつ完全なアルゴリズムを設計した(制約 階層からHLSへの変換では一般に解集合が削減されるため，ここでいう完全性 は制約階層に関して言及したものではない．しかし，DeltaBlueなどの局所伝 播法アルゴリズムでは解を高々1つしか求め得ないことから，むしろ我々のア ルゴリズムの方が強力であるといってよい)．通常の非階層的な連立1次方程式 を解くガウスの消去法を基礎としたアルゴリズムと，行列のLU分解を行うクラ ウト法を応用したアルゴリズムである．これらのアルゴリズムで鍵となるアイ デアは，我々がHLS理論に関連して示した「持上げ」の補題である．これは， あるHLSにおいて階層独立な(階層従属でない)方程式を持ち上げる，すなわち 順序集合でより前の位置に移動することによって作れらた新しいHLSの解集合 が，元のHLSの解集合と等しいことをいう．我々は，階層独立な方程式の検出 と持上げが，ガウスの消去法とクラウト法における部分ピボット選択を修正す ることによって実現できることを示し，効率的アルゴリズムを達成した．
本研究では，HLSを利用することにより，健全かつ完全な効率的制約解消系を 開発する．これは1次方程式の制約階層のための最初の実用的解消系である． 制約解消系の健全性と完全性は，それを用いるシステムの信頼性を保証する， 制約解消系にとって不可欠な性質である．従来，1次方程式の制約階層を利用 するために，局所伝播法アルゴリズムに基づく健全性も完全性も持たない制約 解消系を採用し，多数のシステムが作成されてきたことを考えると，本研究の 意義は極めて大きい．
この制約解消系には我々が設計したLU分解アルゴリズムを採用する．このアル ゴリズムを用いる場合，方程式の定数項が変化しても全体を解き直す必要がな いという利点がある．この性質は，外的要因によって繰り返し値が更新される 変数が存在するという状況で有効である．例えば対話型ユーザーインターフェ ースにおいて，マウスを用いてオブジェクトをドラッグするような状況が相当 する．これは従来の局所伝播法に基づく制約解消系におけるプランニングおよ び実行の2段階解消に対応し，制約解消系に望まれる重要な性質を実現できる ことを意味する．
これまで，制約階層の解消系の研究は局所伝播法に関するものが主流だった． しかしすでに述べたように，実用における要求に対し，局所伝播法が十分に応 えていたとは言い難い．我々が本研究で制約解消系を開発し配布することは， HLSという，局所伝播法とは異なる新たな視点を広く提供することであり，こ の分野の発展に貢献するものである．
最後に本研究に関連する研究提案者らの論文を示す．
| 氏 名 | 所 属 | |
| 研究代表者 | 松岡 聡 | 東工大 情報理工学 数理・計算科学 |
| 研究協力者 | 細部博史 | 東大 理学系 情報科学／学振特別研究員(DC2) |
HiRiseが扱うHLSは，1次方程式からなる制約階層の一種として見なすことがで きる．このような制約階層の解消系に対する需要は極めて多く，様々なシステ ムにおいてDeltaBlueまたはSkyBlueが制約解消系として利用されている．しか し，本来これらは多方向制約を扱うものであり，1次方程式を利用する際には 種々の問題を生じる．例えばDeltaBlueでは，真に方程式の連立が必要な場合 に正しい解を得ることができない．これは多方向制約の間に生じる循環的な依 存関係を適切に処理できないためである．また，SkyBlueではこの問題をcycle solverの導入によってある程度解決しているが，それも完全ではなく，循環の 中に冗長な制約や矛盾する制約が存在する場合にはやはり適切に処理できない．
HiRiseはこれらの問題を解決した，1次方程式のための健全かつ完全な最初の 制約階層解消系である．HiRiseは線形代数と線形計算を理論的基礎とし， DeltaBlueやSkyBlueなどとは異なる数値的方法により制約解消を行う．また， 従来の制約階層を用いる場合のプログラミングスタイルを維持できるように， DeltaBlueのような適度なレベル分割，stay制約およびedit制約の利用，プラ ンニングと実行の2段階解消といった機能も提供する．これらの特徴により， 多くのシステムにおいてDeltaBlueまたはSkyBlueの置換えとして利用でき，そ の導入によって信頼性が向上される．
一方，サンプルアプリケーションはユーザーインターフェースの作成が主体と なるため，プログラムはプラットフォームに依存せざるを得ない．これについ ては，Visual C++を用いてWindows 95/NT上で動作するものを開発する予定で ある．
スクラッチから作成するため，これらは全て新規作成分である．
同様の用途では現在，DeltaBlueまたはSkyBlueが多く利用されている．しかし， これらの解消系で1次方程式を制約として利用する場合には注意が必要である． 例えば，DeltaBlueは制約の循環を許さないため，制約が木構造をなしていな ければならない．またSkyBlueでは，循環が存在する場合，その中に冗長な制 約や矛盾する制約が出現しないようにしなければならない．このような制限の 存在により，プログラマーは制約が解かれた形をある程度事前に考慮する必要 がある．これは制約の利用という観点からは本末転倒といえる．
一方，HiRiseは健全かつ完全な制約解消系であり，プログラマーはこのような 不自由から解放される．構文的に許される限り，いかなる制約も指定できるた め，プログラマーの負担は極めて軽減される．またこの特徴は，制約がプログ ラマーによって直接指定されないようなシステムではさらに有効である．例え ばドローイングツールなどでユーザーが図形間の制約を指定すような場合や， 実演によるプログラミングなどで推論によって制約が自動生成されるような場 合である．このようなシステムの作成にHiRiseを利用すれば，その健全性と完 全性のために，システムの信頼性が著しく向上する．
www-admin@icot.or.jp