2023年度 人工知能学会全国大会(第37回)

講演情報

オーガナイズドセッション

オーガナイズドセッション » OS-9 AIと制約プログラミング

[2I5-OS-9b] AIと制約プログラミング

2023年6月7日(水) 15:30 〜 17:10 I会場 (中会議室 B2)

オーガナイザ:花田 研太、波多野 大督、宋 剛秀

15:30 〜 15:50

[2I5-OS-9b-01] 解集合プログラミングを用いた支配集合遷移問題の解法に関する一考察

〇加藤 聖人1、宋 剛秀2、田村 直之3、番原 睦則1 (1. 名古屋大学大学院 情報学研究科、2. 神戸大学 DX・情報統括本部、3. 神戸大学)

キーワード:解集合プログラミング、支配集合問題、支配集合遷移問題、組合せ遷移問題

支配集合遷移問題は,支配集合問題とその2つの実行可能解が与えられた時に,一方から他方へ,遷移制約を満たしつつ実行可能解のみを経由して到達可能であるかどうかを判定する問題である.この問題は代表的な組合せ遷移問題の一つであり,一般に PSPACE 完全であることが知られている.

本発表では,解集合プログラミング(ASP)を用いた支配集合遷移問題の解法について述べる.提案解法では,与えられた問題インスタンスに対して,制限された長さの遷移系列が存在するかどうかを判定する問題を論理プログラム(ASP 符号化) として表現し,そのステップ長を増やしながら,ASP システムを繰り返し実行することにより到達可能性の判定を行う.提案符号化は,基となる支配集合問題に対する既存の符号化の自然な拡張になっており,支配集合遷移問題の制約を ASP のルール13個程度で簡潔に表現できる点が特長である.

講演PDFパスワード認証
論文PDFの閲覧にはログインが必要です。参加登録者の方は「参加者用ログイン」画面からログインしてください。あるいは論文PDF閲覧用のパスワードを以下にご入力ください。

パスワード