人工知能学会 第112回人工知能基本問題研究会(SIG-FPAI)

主査: 瀧川 一学
幹事: 井 智弘,大久保 好章,杉山 麿人,戸田 貴久,西野 正彬
担当幹事: 井 智弘,戸田 貴久

新型コロナウイルス感染症について

2020.2.28. 政府方針の発表と状況の悪化を受け、協議の結果、感染拡大防止の観点から現地開催を中止とさせていただきます。

2020.2.21. プログラム通り開催の予定ですが、今後の情勢により学会または会場から中止要請があれば中止させていただくことがあります。また参加される皆様には各自の感染予防対策や発熱などの症状がある場合の参加自粛のご協力をどうぞよろしくお願いいたします。

開催日

2020年3月8日(日), 9日(月)

会場

〒832-0826 福岡県柳川市三橋町高畑256 柳川市藤吉コミュニティセンター
https://www.city.yanagawa.fukuoka.jp/kyoiku/shogaigakushu/shisetsu/20160506.html

テーマ:特集「命題論理の充足可能性問題SATの最新動向」および一般

開催趣旨

命題論理式の充足可能性判定(SAT)問題は,約半世紀に渡って膨大な量の研究が蓄積されてきました.特に近年SAT問題を解くプログラムであるSATソルバーの性能が飛躍的に向上し,様々な応用領域における推論の基盤技術としてSAT技術は注目を集めています.

今回の研究会で扱う話題の例としては,SATソルバー,SAT符号化,SAT型システムなどはもとより,SMT,ASP,CSP,QBF,MaxSAT,擬似ブール制約などSAT技術に関連する話題や,プランニング,モデル検査,ソフトウェア検証など各種の応用や事例研究,あるいは,SATの複雑さに関する基礎理論などが挙げられます.さらには,より広い視点から BDD/ZDD などのような実用的なアルゴリズムやデータ構造 なども含まれます.このように多面的な観点から,SATを取り巻く近年の動向を学ぶ機会として,幅広く研究発表を募集します.

もちろん,これらに限らず,人工知能の基本問題に関する理論・技術の研究発表も歓迎します.

招待講演

[講演1] 木村 慧 (埼玉大学)

講演1のタイトル

制約充足問題に対する充足可能性保存割当ての解析

講演1の概要

本講演では,制約充足問題に対する充足可能性割当ての解析とそのアルゴリズム設計への応用について述べる.制約充足問題とは,与えられた制約を満たすような変数への値の割当てが存在するか否かを判定する問題であり,SAT問題の拡張とみることができる.充足可能性保存割当てとは,充足可能性を保つような一部の変数への値の割当て(部分割当て)のことであり,その割当てにより,解くべき問題のサイズを小さくすることができる.例えば,SATにおける単位伝播は充足可能性保存割当ての一例であり,多くのSATソルバーに用いられている.本講演ではまず,制約充足問題において考えられていた様々な充足可能性保存割当ての間の関係を整理する.次に,充足可能性保存割当てを求める計算複雑性について議論する.空でない充足可能性保存割当てを求めることは一般にはNP困難である.そこで,効率的に求めることができる特殊な充足可能性保存割当てを考える.SAT問題に対してはKullmannにより,線形計画問題を解くことにより効率的に求めることができる「線形オーターク割当て」が提案されている.本講演では,線形オーターク割当てを,部分割当ての凸近似とみなし,「線形充足可能性保存割当て」として制約充足問題へ拡張するとともに,凸近似としての極大性を示す.最後に,線形充足可能性保存割当てを求める効率的なアルゴリズムを設計し,整数計画問題の実行可能判定に対する既存研究の結果が統一できることを示す.特に,これまで擬多項式時間で解けることが知られている(それぞれホーンSATおよび2SATの拡張である)ホーン整数計画問題および二次整数計画問題を包含するクラスで,実行可能性判定が擬多項式時間可解であることを示す.

[講演2] 畑埜 晃平 (九州大学)

講演2のタイトル

データの簡潔表現に基づく最適化

講演2の概要

本発表では,大規模な決定空間/データ上の最適化問題を,それらの簡潔表現上の最適化問題に帰着する方法を紹介する.具体例として,順序制約付きジョブスケジューリング問題の厳密解法や,圧縮データ上のSVMやブースティングの事例を示す.これらの事例ではZDD等の決定ダイアグラムが簡潔表現として用いられる.また,帰着後の問題のサイズは簡潔表現のサイズのみに依存し,元の決定空間やデータのサイズには依存しない.

参加費

当研究会の聴講は無料です.
研究会資料は発表の有無に関わらず1500円(学生会員無料)です.

研究会は資料の売上で運営しているため,可能な限り,1グループ
1冊程度で良いので研究会資料を購⼊頂けるとありがたいです.
※ ⼈⼯知能学会員の⽅は研究会登録により年間購読割引があります.
https://www.ai-gakkai.or.jp/sig/announce/sig-registeration/

懇親会

ご参加いただける方はこちらからお申し込みください.
日時: 3月8日(日) 研究会終了後 - 会場: 福泉操 https://fukusensou.com/ 会費: 5000円程度
詳細な開始時間および会費については後ほど決定しだい掲載します.

照会先

井 智弘 (九州工業大学) , 戸田 貴久 (電気通信大学)
E-mail: fpai_kanji@sig-fpai.org

プログラム

1人当たりの発表時間は質疑を含めて25分.発表者には○印.


3月8日(日) 13:30 - 17:30

招待講演1(13:30 - 14:30)

セッション1(14:45 - 16:00)

セッション2(16:15 - 17:30)


3月9日(月) 9:30 - 15:20

セッション3(9:30 - 10:20)

招待公演2(10:30 - 11:30)

セッション4(13:00 - 13:50)

セッション5(14:05 - 15:20)


人工知能学会の研究会資料(第一種)の扱いについて(2015年度より)

2015年4月以降に人工知能学会第一種研究会に投稿された研究会資料は,
紙冊子に掲載されると同時に,学会事務局で資料ID(※1)を付与した上で
学会文献提供サイト「AI書庫」(https://jsai.ixsq.nii.ac.jp/ej/)上のPDF
ファイルとして閲覧可能となります.

発行日(※2)から一年間は,一本あたり(非会員 600円+消費税,学会員 300
円+消費税,登録会員 0円)にて販売します.一年間の保留期間(エンバーゴ)
後は無料購読できるようになりオンライン公開されます.

なおAI書庫上のデータには,標準的な識別子(番号)は付与されませんが,
一般的な検索エンジンや国立情報学研究所が提供するCiNiiなどから容易に
検索できるようになります.

(※1) 研究会資料ID付与規則の変更(2015年度より)

研究会資料ID(論文ID)の付与ルールを下記のように統一しました.

(※2) 紙媒体の奥付に記載された発行日