文献

J-GLOBAL ID：201002282012347977   整理番号：10A0057008

最近のSAT技術の発展 SATによるプランニングとスケジューリング

著者 (1件)： 鍋島英知 (山梨大 大学院医学工学総合研究部)
資料名： 人工知能学会誌  (Journal of the Japanese Society for Artificial Intelligence)
巻： 25  号： 1  ページ： 114-121  発行年： 2010年01月01日 
JST資料番号： X0330A  ISSN： 0912-8085  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： STRIPS(Stanford Research Institute Problem Solver)形式の古典的プランニング問題はSAT(Boolean Satisfiability Testing)問題に符号化できるので,国際プランニング競技会でもSATベースのプランナーが成功を収めている。本論文では,SATプランニングにおいてプラン長が最も短い最適プラン,及び準最適プランを求める手法を概説した。また,アクションにコストを付加した問題において最小コストのプランを求める手法や,アクションの前提条件や効果に数値変数と制約を含めた問題に対する手法を説明した。特に,後者では前処理として数値変換のドメインを絞り込んでSATへ符号化する手法が,SMT(SAT Modulo Theories)を利用した手法よりも性能が上回る。最小コストのプランを求める問題はスケジューリング問題に近いので,ジョブショップスケジューリング問題に対するSAT符号化法や,それに基づく最適値決定について述べた。SATプランニングやSATスケジューリングではSATソルバーのインクリメンタル探索手法によって,学習節を再利用することで高速化が図れることを論じた。

シソーラス用語： *充足可能性問題 ,  *プランニング【AI】 ,  最適化 ,  *最小化問題 ,  *ジョブショップスケジューリング ,  探索問題 ,  機械学習 ,  再利用 ,  高速化
準シソーラス用語： SATソルバ

分類 (4件)： 論理代数  (JB03000H) ,  人工知能  (JE08000Z) ,  ネットワーク法  (KA03040X) ,  その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (31件)：

• BEASLEY, J. E. OR-Library : Distributing test problems by electronic mail. Operational Research Society. 1990, 41, 1069-1072
• BLUM, A. L. Fast planning through planning graph analysis. Artif. Intell. 1997, 90, 1-2, 279-298
• BONET, B. Planning as Heuristic Search. Artif. Intell. 2001, 129, 5-33
• CHEN, Y. Plan-A : A cost optimal planner based on SAT-constrained optimization. Proc. 6th International Planning Competition (IPC-6), 2008. 2008
• CHEN, Y. Long-distance mutual exclusion for planning. Artif. Intell. 2009, 173, 2, 365-391

タイトルに関連する用語 (4件)： SAT ,  発展 ,  プランニング ,  スケジューリング