SATアプローチに基づく高速プランニングシステムの構築

基于SAT方法的快速规划系统构建

• 批准号: 14780269
• 负责人: 鍋島 英知
• 金额: $ 1.34万
• 依托单位: University of Yamanashi
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780269/
• 关键词: プランニング; 充足可能性問題; 補題

SATプランニングの高速化のため,本年度はSAT問題を解く過程で生成される補題のよりよい再利用方法に関して研究を行った.KautzとSelmanによるSATプランナBlackboxは,プランニング問題を解く過程で複数のSAT問題P1,P2,P3,…を生成する.Blackboxは,これらのSAT問題を世界最速のSATソルバの1つであるMoskewiczらによるChaffにより解く.ここで我々は,ChaffがPiを解く際に生成する補題がPi+1を解くときにも再利用できることを証明し,補題を再利用する新しいプランニングアルゴリズムLRP(Lemma-Reusing Planning)を提案した.LRPはBlackboxと比較して,平均して約1.6倍高速にプランニング問題を解くことができる.しかし一般にChaffが生成する補題は莫大な数になる.補題は,無駄な探索の枝刈りを行うために生成された失敗の記録であるが,補題が適用可能かどうか調べるためには,その莫大な数の失敗の記録を検索する必要がある.そこで,無駄な探索空間を大きく枝刈りする補題のみを残し,あまり効果を持たない補題を削除することで,さらなるプランニング速度の向上が期待できる.また補題の数が膨大であるため,「有用かどうか」の判断は高速に行う必要がある.そこで我々は,補題再利用の判断基準をいくつかのヒューリスティクスに基づき設計し,実験を行った.その結果,SAT問題の解探索空間の上位において使用される補題のみを再利用することで,Blackboxと比較して平均して約1.8倍の高速化が可能であることを示した.特に補題が莫大に生成される問題では顕著な効果を示している.

The SAT problem is solved in a fast way. This year, the SAT problem is solved in a fast way. The SAT problem is solved in a fast way.Kautz and Selman. The SAT problem is solved in a fast way. Blackbox is solved in a fast way. The SAT problem is solved in a fast way. The SAT problem is solved in a fast way. LRP(Lemma-Reusing Planning) is a proposed solution to the problem.LRP is compared to Blackbox, averaging about 1.6 times the speed of LRP. General Chaff is generated by a large number of supplementary questions. The problem is that there is no need to search for a record of failure. For example, if you want to explore the space, you can choose to explore the space, and you can choose to explore the space. The number of supplementary questions is expanded, and the judgment of "useful" is necessary. The basic design and implementation of the system are discussed in detail. As a result,Blackbox has been shown to be about 1.8 times faster than the average speed of the SAT problem. Special supplement problem is very big, the problem is very big, the result is very big.