VLSIレイアウト設計は、二つの段階からなる。第一段階では、各モジュールの チップ上での配置を決め、第二段階では、モジュールを接続する配線を決める。 チャネルルーチング問題は一種の配線問題で、配線領域が長方形であるチャネ ルに制限される。この問題は、チャネルのターミナル間の接続要求を与え、そ れらを満たし、しかも線が重ならないような配線方法を決める制約充足問題で ある。これに対してはすでにいろいろな方法が提案され、またこの問題はいろ いろな探索法の評価に用いられている [2,6,4,5,7,8]。
MGTPはICOTで開発されたモデル生成型定理証明系で、非ホーン節が書けること や並列を意識せずに並列探索プログラムが書けるなどの魅力がある [3]。また制約MGTPであるCMGTP[1]は、制約解消によく用い られている制約伝搬法をルールを用いて柔軟に記述できる利点を持っている。 しかし、CMGTPの応用は決して多いとは言えない。また、CMGTPは開発者以外の 人によってに評価されたことはまだないようである。
本研究では、三つのプログラミング言語、即ちCMGTP、 KLIC、 及びCLP(FD)を 用いてチャネルルーチング問題を解くためのプログラムを開発する。また、 CMGTPをほかの二つの言語と比較することによって、 CMGTPの利点と欠点を明 らかにする。