研究テーマの紹介
「制約に基づく対話型問題解決システム」
◇はじめに◇
近年、コンピュータは科学技術分野における数値処理から、
私達の身近な問題解決のための知的処理や知識処理などの、
非数値処理に使われるようになってきている。
その例としては、
などがあり、
これらをコンピュータで解くためのシステムの研究・開発が行われている。
◇コンピュータにおける問題の表現◇
これらの問題は、人工知能分野で現れる組合せ探索問題として捉えることができる。
そこで、これらの問題をコンピュータで表現するために、
多くの局所的な制約条件から構成され、
それらを満たすような解を求める制約充足問題として定式化した。
制約充足問題の簡単な具体例として、連立方程式がある。
a+b = 5 … (1) 制約条件1
a-b = 1 … (2) 制約条件2
これは、(1)式と(2)式を満たす変数a,bを求める問題であるが、
各式は問題を構成する局所的な制約条件として捉えることができる
(実際は変数が多いため、制約条件は一般に局所的なものになる)。
◇研究課題◇
本研究の研究課題としては、以下の２点がある。
- 《制約の表現方法》
- 現実の各問題は、一般にコンピュータ上で処理できる形式では表現するのが難しい
（例、 時間割編成問題の制約）。
- 《解法（探索手法）》
- 膨大な組合せである解候補の中から、
一番最適な解をどのように探すかという研究は、現在までにも盛んに行われている。
しかしながら、問題の多くがＮＰ完全であるために、汎用で有効な解法は存在しないため、
個別に対処せざるを得ない。
探索手法は、次の２通りに大きく分けることができる。
◇研究の方針◇
- 《対話型システム》
- コンピュータで完全に自動で解くことができるのは簡単化された問題であり、
それに対し、現実の問題は複雑で人間の知識が必要である。
実際、システムで表現できない制約も多数存在する。
また、表現できても制約は多種多様であり、その扱いが困難である。
このような問題の定式化、制約の表現における問題に対して、
本研究では、人間の知識を積極的に活かすように、
システムとユーザが協調して問題を解決する「対話型システム」とした。
- 《制約の分類と点数化》
- 多種多様な制約をコンピュータで扱うために、
それぞれの制約の性質を解明し、整理・分類することが必要である。
これによって、各制約の参照するデータが明確にでき、
それぞれに対して適切な処理を行うことが可能になる。
また、制約の強弱については、違反点数を導入することで表現する。
よって、本問題は違反点数を最少化する最適化問題となる。
- 《制約違反最少化戦略による山登り法探索》
- 本研究で扱う問題は探索空間が膨大であるため、
通常の縦型探索（厳密解法）の適用は困難である。
そこで、ある初期値から反復改良していくことで、
準最適解を求める近似解法の山登り法探索を行うことにした。
初期値に既存のデータ（時間割編成問題なら過去の時間割）を用いることで、
実際の利用形態に即した探索を行うことができる。
◇研究の目的◇
本研究では、
- 時間割編成問題［筑波大学第三学群情報学類］(1994年度)
- 室内レイアウト問題［筑波大学電子・情報工学系西原研究室］(1995年度)
- 日本語点字変換問題(1996年度)
を解くための「対話型システム」の開発を通じて、
これらの問題の性質を整理し、システムとユーザとが協調して問題解決を行うことのできる
システムの枠組を提案することを目的とする。
Author:
nishimor@algor.is.tsukuba.ac.jp
お帰りはこちら