Planning with SAT, Admissible Heuristics and A*(Rintanen; 2011)

Rintanen氏のPlanning as SAT論文4号の解説である。 先に紹介した3つの論文では対象はPlanのOptimalityとしてsatisfiableを想定したものであった。 この論文ではより高度なOptimality(というかsatisfiableはOptimalityをなにも保証していない)を保証するような探索についての考察を行うものである。すなわち、比較対象のsearch-basedなプランナはAあるいはIDAアルゴリズムにAdmissibleなヒューリスティック関数を使って探索を行うようなプランナである。

この論文において考察する問題は、ゴールを達成するような最小個数のアクションからなるプランを求めるというものである。 これは、actionのコストが一様であり、かつ直列プランニングの場合にはglobal optimalityと一致する。 ちなみに、最近僕が取り組んでいる研究のうちの一つはModel basedなプランナを使ってコスト付きの場合のGlobal Optimalityを保証する手法に関するものである。

比較対象のA*アルゴリズムは[Hart et. al.;1968]にて提案されたものであり、あるadmissibleなヒューリスティックのものでの探索では最小の展開ノード数で最適性を保証した解の探索を終えるものである。perferctなヒューリスティックのもとではゴール状態に到達するのに必要な最小のアクションに対応するノードだけを展開し探索過程を終えるため非常に効率的であると言える。一方で、h() = 0などの良くないヒューリスティックのもとでは解の長さに対して指数的なメモリを要求するという限界がある。

A系のアルゴリズムはヒューリスティック関数の計算をSATでエミュレート可能であれば探索過程をSAT-based plannerで効率的にエミュレート可能であるが、一方でその逆は時に不可能である。 具体的には、問題サイズ(命題、アクションの個数)に対して線形程度のプランを求める時、Aでは指数オーダーのメモリが必要になる一方で、SATで定式化された問題では多項式程度のメモリしか必要としない。(SAT <= NP <= PSPACEなのでこのこと自体は自明) IDA[Korf; 1985]は、Aに対して大きなオーバーヘッドなく、必要とするメモリ領域を指数クラスから線形クラスに落とすことの出来る有名な手法である。 最悪時の比較ではSAT, IDAは同じ(時間/空間)計算量に属するものの、IDAよりはどのような場合にも悪くならないようなSATによるIDAのエミュレーションが存在すること、逆に、SATでは効率的に解ける一方で、AあるいはIDA*では指数的に計算量が悪くなるようなケースが存在することを示したのがこの論文の成果である。

Introduction to x86 Assembly(Martin Hirzel, 2011)

https://cs.nyu.edu/courses/fall11/CSCI-GA.2130-001/x64-intro.pdf

x86のアセンブリはじめの一歩である。 Intelのdevelopers guideを読もうかと思ったら4000ページくらいあったので4ページのこの文書と、 こちらの14ページ公式チュートリアルをまずは読もうと思う。 https://software.intel.com/sites/default/files/m/d/4/1/d/8/Introduction_to_x64_Assembly.pdf

この資料自体はNew York Univ.の授業で使われたもので、授業で扱うx64のサブセットを解説したものである。

アセンブリの形式の主流なものとして、AT-T形式というものと、Intel形式というものがあるそうである。 その他、いくつか入門的な日本語の資料は例えばこちら

• GAS CapmNetwork
• X86アセンブラ/GASでの文法 - Wikibooks

OSX環境、clangでintel形式のasmを出力するには-mllvm --x86-asm-syntax=intelをclangのオプションに指定すればいいようである。(stack overflowでは3.5+ではgcc同様に-masm=intelを受け付ける、との記述があったが、手元の3.5ベースのclangではこのオプションは認識されなかった)

関数呼び出しの際にはconventionがあり、 * 引数が6つまでの場合には定められたレジスタを使って引数の受け渡しを行う * それ以上の場合には余剰の引数をstackに逆順に引数を積む(stackはhigh->low addressに伸びるので、積み終わったものはaddressの順に並んでいる) * その後、戻った後の処理の位置、スタックポインタをstackに積み、処理をcalleeに移す * 呼び出しから戻る際には、呼び出し元関数に属するレジスタの値を呼び出し前の状態に戻し、スタックポインタを戻し、callerの処理の続きに戻る

この他にもABIはたくさんあり、例えば、Linuxとx86でのC言語の場合のABIは以下の資料に記述がある。 http://x86-64.org/documentation/abi.pdf