[2E3-OS-13b] AIと制約プログラミング(2/3)

[2E3-OS-13b-05] ADSAT：敵対者が存在するMaxSAT

〇菅原 知也¹、越村 三幸¹、横尾 真¹ (1. 九州大学)

キーワード：SAT、MaxSAT

本論文では，ADSAT (Attacker Defender SAT) と呼ばれる，防御者と敵対者が存在する場合の MaxSAT について論じる．MaxSATは，充足可能性問題(SAT) を最適化問題に拡張したものであり，その目的は充足する節の数の最大化である．
ADSAT において，防御者は充足する節の数の最大化を目的とし，敵対者はその最小化を目的とする．本研究の目的は，敵対者のあらゆる攻撃を想定した防御者の最適解を求めることである．このような頑健な解を求めることは理論上のみならず実用上も重要である．
先行研究において，ADSAT を解くアルゴリズムとして IBR (Iterated Best Response)が提案されている．しかし，ADSAT はΣ^P₂完全問題であるため，小さいサイズの問題でも実用的な時間で最適解を求めるのが難しい，という問題がある．
そこで本論文では，ADSATの近似解を求める AE (Attack Enumeration) を提案する．敵対者の攻撃を限定した場合，AE は効率的に近似解を求めることができる．また，計算機実験により両アルゴリズムの性能を比較し，評価を行う．