プランナー・プログラミングが驚くべき理由

 (hillelwayne.com)
2 ポイント 投稿者 GN⁺ 2024-02-22 | 1件のコメント | WhatsAppで共有
  • Picat の planner モジュールは、値の割り当てを見つける論理プログラミングから一歩進み、目標状態に至る 状態変更シーケンス を問題として表現する
  • 開始状態 Start、遷移規則 action(From, To, Action, Cost)、終了条件 final(S) を定義すると、best_plan(Start, Plan) が最終状態までの 最小コスト計画 を見つけてくれる
  • グリッド経路の例では、移動、境界制限、障害物回避、複数目標の訪問を action と final の変更だけで扱え、目標訪問順も固定したり自由に変えたりできる
  • 計画機能は 制約解決 と組み合わせられ、partition problem で要素を取り除いて同じ合計に分割できる最大の部分リストを見つけるような問題も表現可能
  • Picat は研究用言語なのでドキュメントやエラーメッセージは乏しいが、特定の計算問題を素早く解くための ツール型言語 としては、一般的な言語より簡潔な解法を与えられる

Picat とプランナー・プログラミングの基本アイデア

  • Picat は 論理プログラミング、命令型プログラミング、制約解決 を組み合わせようとする研究用言語
  • 一般的な命令型・関数型プログラミングは入力から出力を作るアルゴリズムを書くが、論理プログラミングや制約解決は関係を満たす 値の割り当て を探す
  • Picat では小文字で始まる非関数識別子は a、b、c のような atom で、大文字で始まる識別子は変数
  • まだ定義されていない変数 Y を含む member(Y, Arr) のような式でも、Picat はその式を真にする値を見つけて割り当てられる
    • Arr = [a, b, c, a] なら Y は a、b、c のいずれかになりうる
    • 続けて X != Y のような条件を入れると、可能な値はさらに絞られる
    • member(a, Z) のようにリスト自体がまだ不明な状態でも、Z をリストとしてインスタンス化できる

計画は値の割り当てではなく状態変更を探す

  • 計画(planning) は、方程式を満たす変数値を探す代わりに、特定の終了状態に到達する 変数変更シーケンス を探す
  • Picat の計画問題には 3 つの要素が必要
    • 開始状態 Start
    • 状態遷移を表す action 関数群
    • 状態が終了状態かどうかを判定する final(S)
  • Picat の action 関数はすべて名前が action でなければならず、4 つの引数を取る
    • 現在の状態
    • 次の状態
    • アクション名
    • コスト
  • best_plan(Start, Plan) は、終了状態までに必要な 最短ステップまたは最小コスト の計画を Plan に割り当てる
    • コストをすべて 1 にすれば、計画コストは総移動ステップ数になる
    • 長さを問わず何らかの計画だけが必要なら plan(Start, Plan) を使える

グリッド経路探索の例

  • 例題は、グリッド上のマーカーが原点 (0, 0) から出発して目標座標に到達すること
    • 各ステップで上下左右に 1 マス移動できる
    • グリッド境界の外には出られない
    • 目標座標に到達すれば成功
  • 開始状態は {Origin, Goal} のように現在位置と目標を一緒に持つ
    • Picat の {a, b} は配列構文で、実質的にはタプルのように使われる
  • final({Pos, Goal}) => Pos = Goal. のように、パターンマッチで終了条件を表現できる
    • 同じ内容をパターンマッチなしで書くなら、状態を先に {Pos, Goal} に分解する必要がある
    • final 条件が複数あるなら、そのうちどれか 1 つでも真になれば計画は成功する
  • 移動アクションでは 4 方向 {-1,0}、{1,0}、{0,-1}、{0,1} のいずれかを選び、新しい座標が 0..10 の範囲内にあるかを確認する
    • member({Dx, Dy}, Dir) は可能な方向の値を見つけるために使われる
    • member(Tx, 0..10) と member(Ty, 0..10) は座標が境界内にあるか確認するのに使われる
    • 値を割り当てない確認専用の predicate としては membchk もある
  • 結果の計画は {move,{1,0}}、{move,{2,0}} のように、移動アクションと新しい座標のリストとして出力される
    • Raku スクリプトで経路を可視化できる
    • {Tx, Ty} != {2, 1} のような条件を追加すれば、特定座標を避ける 障害物回避 もできる

複数目標とコスト最小化

  • 複数の目標を訪れるには、Goal を単一座標ではなく [{2, 2}, {3, 4}] のような 目標キュー に変える
  • 目標に到達したとき、目標リストからその項目を削除する新しい action を追加する
    • [Head|Tail] はリストを先頭要素と残りに分ける
    • Goal = [Pos|Rest] は、現在位置 Pos が目標リストの先頭項目と等しいときだけ真になる
    • 新しい状態を {Pos, Rest} とすれば、到達した目標が削除される
  • すべての目標を訪問したかどうかは final({Pos, Goal}) => Goal = []. で判定する
    • 現在位置が特定の目標と同じかではなく、目標リストが空かどうかが終了条件になる
  • 目標を決まった順序で訪れる方法が、常に全体の最短経路を作るとは限らない
  • 目標順序を無視して全体経路を最小化したいなら、mark アクションを変更する
    • Goal = [Pos|Rest] の代わりに member(Pos, Goal) で現在位置が目標リストのどこかに含まれるかを確認する
    • To = {Pos, delete(Goal, Pos)} で訪問済みの目標をリストから削除する
    • この方式では Picat が次に向かう目標を選び、全体の経路長 を最小化できる

計画と制約解決の組み合わせ

  • Picat の計画機能は他の Picat 機能と統合されており、計画と 制約解決 を一緒に使える
  • 例として扱われる partition problem は、数のリストを同じ合計を持つ 2 グループに分ける NP-complete 問題
  • このプログラムは数のリストから要素を取り除き、同じ合計に分けられる最大の部分リストを探す
    • 入力された数値リストから要素を削除することを計画アクションとする
    • final(Numbers) は、その数値リストに有効な partition 解があるかを確認する
    • cp モジュールの制約で、各要素が左グループか右グループに入るかを 0..1 変数で表す
    • 全体の合計が片側グループ合計の 2 倍になるよう制約を置く
  • 例の出力では [5,17] を削除したあと、残ったリストを 2 グループに分けてそれぞれ合計 1108 にできる
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • この方法は単に有効な制約を直接解くにとどまらず、有効な制約状態に到達するための変更 まで計画として表現する

Picat を使う際の限界と向いている用途

  • Picat は研究用言語なので、本番利用には推奨されない
  • 便利機能は多くなく、優れたドキュメントや明確なエラーメッセージも不足している
    • 解ける計画がないときのエラーは *** error(failed,main/0) のように表示される
  • Windows で実行できる点は、多くの研究用言語より優れていると評価されている
  • Picat は保守や共有を前提としたコードを書く言語というより、特定種類の計算問題を解くための ツールキット言語 に近い
  • 一般的なプログラミング言語と制約ソルバでは扱いづらかった一部の問題を、Picat ならかなりエレガントに解ける

他の計画言語と関連概念

  • 計画はもともとロボティクスや AI で開拓されたが、現在ではビデオゲーム AI で Goal Oriented Action Planning(GOAP) という名前でよく使われる
  • PDDL は、独立したプランナーが入力として受け取る計画記述言語
    • SAT における DIMACS が記述形式として使われるのと似た役割を持つ

関連記事

1件のコメント

 
GN⁺ 2024-02-22
Hacker News のコメント

  • Picat のプランニングモードを実務で使ってみたことがある
    複数の機器群の保守を調整するシステムをプロトタイプとして作ったもので、「どうやるか」ではなく「何が欲しいのか」「可能な行動は何か」「守るべき制約は何か」を入力する方式だった
    小さな例では最適な計画をうまく作れたが、実際の規模に大きくなると予想どおり破綻し、計画問題は結局 EXPTIME なので限界が大きかった
    Picat にはヒューリスティックを定義する逃げ道があり、状態述語のランダムフォレストとナイーブベイズ分類器で有望な経路を予測させたが、対称性破り制約や階層的プランニングまで入れても手間がかかりすぎた
    古典的な GOFAI の問題領域には、まだ AI の冬が残っているように思える
    計画問題を「潜在的に指数的に長い計画を生成する多項式時間生成器」を返すように再定式化すれば、そうではないかもしれない

    • 商用ソルバーはオープンソースより 性能もはるかに良く、財布もはるかに早く空にしてくる
      CPLEX、Xpress、GUROBI、Hexaly が思い浮かぶ。Hexaly はスケジューリングや車両経路問題に特に良い
      通常は業界でよく使われる言語向けの API から使うが、汎用タスクに弱い専用ソルバー言語より、この方式のほうがずっと理にかなっていると思う
      Python から GUROBI を呼ぶのはとても簡単で、Python の通常の機能もそのまま使える
      Mosek は GUROBI よりはるかに安いが、API はどちらもかなり低レベルで、性能も GUROBI ほどではない
    • この場合は CP-SAT(https://developers.google.com/optimization/cp) のようなものがうまくスケールした可能性がある
      このソルバーは、とんでもない数の変数と制約を簡単に扱え、組み込みのヒューリスティックも優れている
    • 昔のプランナーは、どの規則を適用するかを決める メタ規則やヒューリスティックを含めて、探索空間を減らしていた
      あるシステムは問題を異なる表現に分け、特化した自動ソルバーを接続していた
      Jahob Analysis System と Cyc が思い浮かぶ
      実用面で、古典 AI の中で最もすっきりしていた設計は Procedural Reasoning System で、弱点を現代的な方法で補って作り直した版を一度見てみたい
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • なぜ高品質な オープンソースソルバーがないのか不思議に思う
      他の数値計算分野では最先端技術がオープンソースであることが多いのに、最適化分野だけなぜ違うのか、いつも疑問だった
    • 結果や性能の面で見ると、Prolog をぼんやり思い浮かべながら適当に書いた 深さ優先探索と実際には大きく違わないのではないかと思う

  • 制約プログラミングコミュニティで活発な HN ユーザー hakank、つまり Hakan Kjellerstrand が Picat の資料や例を多数集めたサイトがある: http://www.hakank.org/picat/

  • いつものように Prologを勧めたい
    優雅で理解しやすく、より成熟しており、有限領域制約解決が欲しいなら標準構成だけでも十分
    そのほか MiniZinc は、さまざまな目的に特化した複数のソルバーへアクセスするための優れたインターフェースなので、専門家でなければ望む結果により近づける可能性が高い
    Prolog には多くの利点があるが、良い性能を出すには必要な「機械的な勘」がすぐに相当なものになりうる
    Picat で何かを書いたなら、同じものを別の言語でどう書くかも考えてみるとよい
    こうしたおもちゃ問題は他の言語でも簡単で、ほとんどの関数型言語では Dijkstra や A* は数行で済み、結局は探索アルゴリズムの状態空間を定義するだけ、という場合が多い

  • レビュアーに Predrag がいてうれしかったが、同時にまったく意外ではなかった
    Firebase technical screen は、こういうツールがあればずっと簡単だっただろうし、結局また一つの 最適化問題だった
    Picat でもう一度解いてみたい気もする
    彼はプログラミング言語方面でも興味深いことをしている: https://github.com/obi1kenobi/trustfall

  • 最初に思ったのは「自分で解かなければならない 型システムみたいだな」だった
    TypeScript で素朴に表現しようとしてみたが、a、b、c がすべて同じになりうるので、何も解決されなかった
    正しく表現しようとした結果、ある程度使えそうな形までは行ったが、依然としてアサーションを使っており、Y の型もきちんと表現できない
    この過程はむしろ、プランナー風プログラムが単純さと簡潔さの面でどれほど強力かを示している
    TypeScript はこの種の制約を表現できるほど強力ではないようだ
    試した TS Playground のリンク: http://tinyurl.com/3p2pzdtn

  • GOAP がまた言及されているのを見るとうれしい
    F.E.A.R. の敵があれほど面白かった秘密のソースで、Jeff Orkin の仕組みに関する論文も読みやすくて面白い

  • Prolog と一部の CLPFD を実務で使っているが、本当に良い
    どこにでもあってほしいし、もっと正確には、純粋性を重視する論理コアを置いて、命令型の動作は端へ押しやりたい
    業界がこんなに悪いツールに閉じ込められているように見えて残念だ

  • Prolog に似ていて興味深い

  • こういうプログラミング方式自体は、完全に新しいわけではない
    大学で Prolog を学んだし、かなり似て見えるが、Prolog にはプランナー機能がなかった
    ただし プランナーは問題を解く非常に優雅で単純な方法だ
    記事末尾のビデオゲーム関連の部分を見て興味が湧いた
    プランナー機能は、数行の明確なコードで問題をとても簡単に解けるようにしてくれるが、命令型で書いたアルゴリズムと比べると性能はどうなのだろうか？
    Picat は似た言語と比べるとかなり効率的なようだが [1]、「標準的な」言語との比較は見つけられなかった
    [1]: https://arxiv.org/abs/1405.2538

  • コンピュータに到達すべき状態だけを伝えるという夢は、自分にもある
    プランニングコミュニティやソルバーには詳しくなく、ortools を素朴に触った程度だが、A* である状態から目標状態へ行くコード生成を試したことがある
    状態間を移動するためのアセンブリ命令を生成し、関数呼び出しの隠れた状態遷移まで見つけて目標に到達する
    探索速度を上げるために Python multiprocessing で並列実行もしたし、スレッドごとに近傍生成が異なるため、動的な近傍生成を使った
    当初の試みでは A* を並列化するのが難しく、シャーディングが必要だった
    自分の実験の夢は、コンピュータに「今持っているもの」と「欲しいもの」を伝えれば、正しい移動経路を自力で見つけてくれることだ
    個人的には、プログラミングは Factorio や工場のような 物流に近いと見ている
    だから「sliding puzzle」と呼んでいる。正しい絵を見るために、物をあちこち動かさなければならないパズルだからだ
    GitHub リポジトリとメモ: https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit: https://replit.com/@Chronological/SlidingPuzzle3