制約は知識処理,論理型プログラミング,グラフィカルユーザーインターフェース(GUI)の構築など,様々な問題のための強力な道具として認識されている.特に階層制約系は,制約過多である実世界の問題のモデリングに適しているため,有望である.しかし,階層制約系の効率的解消が困難であるために,階層制約系を用いた実用的なシステムやアプリケーションの数は少ない.その背景には,効率的解消法の設計の拠り所となるべき階層制約系の性質が明らかでないという問題がある.

　本研究の目的は,階層制約系の理論的性質を探求し,階層制約系の解消法を設計するための基礎を与えることである.その上で実際に,主にGUIの構築を対象として,階層制約系のための制約解消系を開発する.より具体的には,階層制約系の定式化として,制約階層と階層線形系の2種類を扱った.制約階層に対しては,その性質を調べるために,一般化局所伝播法という理論を提案した.一方,階層線形系については,線形代数の観点からその性質を論じた.そして,制約階層と階層線形系のための制約解消系として,それぞれDETAIL制約解消系とHiRise制約解消系を設計した.DETAIL制約解消系はグラフアルゴリズムを基礎とし,HiRise制約解消系は線形計算を採用している.以下では,それぞれの内容について,より詳細に述べる.

　制約階層はBorningらが提案した階層制約系の定式化であり,これまで広く研究されてきた.制約階層の特徴は,比較的少数の強さと呼ばれる優先度を用いて,階層を表現する点である.制約はその強さに応じて,強さrequiredを持つ必須制約と,requiredより弱いstrong,medium,weakなどの強さを持つ選好制約に分類され,同じ強さを持つ制約の集合はレベルと呼ばれている.制約階層の解は,requiredレベル内の必須制約を必ず充足するように定義されている.一方,requiredより弱い選好制約が,より強い制約のうち充足すべきものに矛盾する場合,解によって充足されない.さらに,これだけでは同一レベル内での制約の矛盾が生じ得るので,そのような状況に対処するために,制約階層比較子を導入し,解の最適性を定めている.例えば,最小2乗比較子は,レベル内で制約の誤差の2乗和を最小化するように解を決定する.Borningらによる制約階層の定式化では,その定義の形式に応じて,制約階層比較子をlocally-betterとglobally-betterの2種類に分類していた.しかし,従来,locally-betterによる制約階層の充足はglobally-betterによる充足よりも難しいことが経験的にわかっていたが,より一般的な形で議論されることはなかった.また,globally-betterを困難さの観点からさらに分類することもなかった.一方,本研究では,大域的準単調性という性質に基づく分類を提案した.大域的準単調性とは,任意の2つの制約階層で共通する解が,常にそれらを合わせて作った制約階層の解になるという性質である.さらに本研究では,大域的準単調性を持つ大域的制約階層比較子を与えた.大域的制約階層比較子は,locally-betterを包含し,さらにglobally-betterに分類される比較子の多くを含むもので,制約階層比較子の新しい分類方法である.

　次に,制約階層の充足の困難さを判定するための理論的枠組として,一般化局所伝播法を提案した.充足の困難さの基準としては,正しい解を得るための制約のスケジューリングの十分条件を利用した.スケジューリングを表現するために,制約階層をブロックに分割し,ブロック間に半順序を与えた順序分割を定義した.一般化局所伝播法は,順序分割が与えられたとき,その半順序に従って次々とブロックを充足する.これは従来,GUIを対象とした制約階層の解消法として盛んに研究されてきた局所伝播法の一般化として見なすことができる.このような一般化局所伝播法において,正しい解を得るための十分条件を検討した結果,制約解消が容易であると思われていたlocally-better比較子については,従来のアルゴリズムを支持する形で十分条件を与えることができた.また,大域的制約階層比較子については,locally-better比較子における十分条件を少し強めることにより,正しい解が得られることを示した.このことは,大域的制約階層比較子が,locally-better比較子よりも制約解消が困難であることを一般的な形で示したものといえる.同時に,大域的でないglobally-better比較子では制約解消がさらに困難であることを示している.

　一般化局所伝播法によって導いた結果は,大域的制約階層比較子に対しても,局所伝播法による制約解消が可能であることを示唆している.これを受けて,大域的制約階層比較子を扱う制約解消系DETAILを考案した.DETAILは,GUIを対象として盛んに研究されてきた局所伝播法に基づく制約解消系としては,大域的制約階層比較子を扱う最初のものある.既存の局所伝播法の研究では,制約階層をグラフとして定式化し,locally-graph-betterなどと呼ばれるlocally-better比較子を用いて解を定義していた.そして,制約解消はグラフアルゴリズムとして表現していた.同様にDETAILにおいても,制約階層をグラフで表し,制約解消をグラフアルゴリズムとして与えた.ただし,制約階層比較子としては,大域的制約階層比較子であるglobally-graph-betterを新たに定義した.DETAILの制約解消は,制約の追加・削除に伴い,内部データを修正することによりインクリメンタルに進められる.これは,locally-better比較子を扱う既存の制約解消系の研究において,GUIを対象とする上で最重要とされていたテーマである.DETAILに関する本研究は,大域的なglobally-better比較子についても,これが可能であることを示したものである.

　次に,階層制約系の新しい定式化として,階層線形系を提案した.階層線形系は,1次等式または1次不等式として表される必須制約の集合と,1次等式として表される選好制約の全順序集合からなり,選好制約間の全順序がそのまま制約の優先度となる.階層線形系は選好が互いに異なるために,必須制約を除けば,制約階層のような同じ強さの制約からなるレベルという概念はない.しかし,1次等式と1次不等式からなる任意の制約階層は階層線形系に変換でき,その階層線形系によって元の制約階層のlocally-better解集合の部分集合が得られることを示した.この事実により,階層線形系を制約階層の部分理論として見なすことができ,制約解消系を設計していく上で制約階層に代わる基礎として利用できる.本研究ではさらに,階層線形系が満たしている性質を示し,それを用いて階層線形系を解消するための基本的アルゴリズムを与えた.具体的には,1次等式のみからなる階層線形系のためのアルゴリズムとして,局所伝播法,消去法,LU分解を利用する方法を,1次不等式を必須制約とする階層線形系のためのアルゴリズムとしてシンプレックス法を用いる方法を与えた.

　最後に,1次等式からなる制約階層のためのHiRise制約解消系を提案した.HiRiseは,DETAILと同様,制約の追加・削除に伴い,制約階層をインクリメンタルに解消するため,GUIでの利用に適している.DETAILを含む局所伝播法に基づく制約解消系は,制約階層をグラフとして表しているために,1次等式などの代数的制約を扱う際に,制約解消の健全性と完全性を保証することができず,誤った解を求めてしまったり,解を得られずに停止してしまったりするなどの問題があった.一方,HiRiseは,内部的に線形代数を基礎とした階層制約系を利用し,制約解消には線形計算を採用しているため,制約解消の健全性と完全性を保証している.このため,HiRise制約解消系を用いてシステムやアプリケーションを作成すれば,信頼性を向上できるという利点がある.制約解消法の設計に際しては,従来の局所伝播法で効率化に役立っていたと考えられるアイデアを,階層制約系の制約解消と統合できるよう配慮し,結果としてに局所伝播法に匹敵する効率を達成した.

　本論文は,階層制約系の理論的性質と効率的解消法について研究したものである.その目的は,階層制約系の理論的性質を探求し,階層制約系の解消法を設計するための基礎を与えることであり,実際に主にGUIの構築を対象として,階層制約系のための制約解消系を開発して有効性を検証している.階層制約系の定式化として,制約階層と階層線形系の2種類を扱っている.制約階層に対しては,その性質を調べるために,一般化局所伝播法という理論を提案し,一方,階層線形系については,線形代数の観点からその性質を論じている.そして,制約階層と階層線形系のための制約解消系として,それぞれDETAIL制約解消系とHiRise制約解消系を設計している.DETAIL制約解消系はグラフアルゴリズムを基礎とし,HiRise制約解消系は線形計算を採用している.これら制約解消系は従来のものを凌駕する性能を有するものである.以下では,それぞれの内容について詳細に述べる.

　まず,本論文では,制約階層系の新たな分類法を提案している.制約階層はBorningらが提案した階層制約系の定式化であり,これまで広く研究されてきた.Borningらによる制約階層の定式化では,定義の形式に応じて,制約階層比較子をlocally-betterとglobally-betterの2種類に分類していた.しかし,従来,locally-betterによる制約階層の充足はglobally-betterによる充足よりも難しいことが経験的にわかっていたが,より一般的な形で議論されることはなかった.また,globally-betterを困難さの観点からさらに分類することもなかった.そこで本論文では,大域的準単調性という性質に基づく分類を提案している.大域的準単調性とは,任意の2つの制約階層で共通する解が,常にそれらを合わせて作った制約階層の解になるという性質である.さらに本論文では,大域的準単調性を持つ大域的制約階層比較子を与えている.大域的制約階層比較子は,locally-betterを包含し,さらにglobally-betterに分類される比較子の多くを含むもので,制約階層比較子の新しい分類方法で,有用なものである.

　次に,制約階層の充足の困難さを判定するための理論的枠組として,一般化局所伝播法を提案している.一般化局所伝播法において,正しい解を得るための十分条件を検討し,制約解消が容易であると思われていたlocally-better比較子については,従来のアルゴリズムを支持する形で十分条件を与えている.さらに,大域的制約階層比較子については,locally-better比較子における十分条件を少し強めることにより,正しい解が得られることを示している.一般化局所伝播法によって導いた結果は,大域的制約階層比較子に対しても,局所伝播法による制約解消が可能であることを言っており,これに基づき大域的制約階層比較子を扱う制約解消系DETAILを構築している.DETAILは,GUIを対象として盛んに研究されてきた局所伝播法に基づく制約解消系としては,大域的制約階層比較子を扱う最初のものある.既存の局所伝播法と同様に,DETAILにおいても,制約階層をグラフで表し,制約解消をグラフアルゴリズムとして与えているが,制約階層比較子としては,大域的制約階層比較子であるglobally-graph-betterを新たに定義しており,さらにDETAILの制約解消は,制約の追加・削除に伴い,内部データを修正することによりインクリメンタルに進められる.これは,locally-better比較子を扱う既存の制約解消系の研究において,GUIを対象とする上で最重要とされていたテーマであり,DETAILに関する本論文の研究は,大域的なglobally-better比較子についても,これが可能であることを示した意義のあるものである.

　さらに,階層制約系の新しい定式化として,階層線形系を提案している.階層線形系は,1次等式または1次不等式として表される必須制約の集合と,1次等式として表される選好制約の全順序集合からなり,選好制約間の全順序がそのまま制約の優先度となる.階層線形系は選好が互いに異なるために,必須制約を除けば,制約階層のような同じ強さの制約からなるレベルという概念はない.しかし,1次等式と1次不等式からなる任意の制約階層は階層線形系に変換でき,その階層線形系によって元の制約階層のlocally-better解集合の部分集合が得られることを示している.本論文ではさらに,階層線形系が満たしている性質を示し,それを用いて階層線形系を解消するための基本的アルゴリズムを与えている.

　これらの成果に基づき,最後に,1次等式からなる制約階層のためのHiRise制約解消系を構築している.HiRiseは,DETAILと同様,制約の追加・削除に伴い,制約階層をインクリメンタルに解消するため,GUIでの利用に適している.DETAILを含む局所伝播法に基づく制約解消系の制約が複雑な場合に制約解消の健全性と完全性を保証することができなかった問題に対し,HiRiseは,内部的に線形代数を基礎とした階層制約系を利用し,制約解消には線形計算を採用しているため,この範囲での制約解消の健全性と完全性を保証している.制約解消法の設計に際しては,従来の局所伝播法で効率化に役立っていたと考えられるアイデアを,階層制約系の制約解消と統合できるよう配慮し,結果としてに局所伝播法に匹敵する効率を達成している.

　なお,本論文におけるDETAIL制約解消系とその理論に関する研究の一部は共同研究により得られたものであるが,論文提出者が主体となって研究を行なったもので,論文提出者の寄与が十分であると判断する.

　よって,博士(理学)の学位を授与できると認める.