■:ニューロシンボリック Classical Planning
Masataro Asai
(MIT-IBM Watson AI Lab, IBM Research, Cambridge)

質問はZoomに書き込み

1.

Part 1:

記号接地とグラフィカルモデル

2.

⽕星に取り残された! うわ やっべ どうしよう?

3.

どっちの「知性」がいいですか?
経験に基づく勘だけ でどうにかなる?
"考えるな、感じろ" でうまく⾏きますか?

ちょっと 頭を使って 臨機応変に対応しますか?

Deliberative (熟考) agent
Reflex (反射) agent→ 私がやりたいのは 熟考エージェント
しかも、 ⽣のセンサー⼊力(画像)を直接使えるやつ

4.

古典プランナ (古典⾃動計画ソルバ):8パズルをミリ秒単位で解ける.
記号的探索・推論システムは爆速でも PDDL があるときにしか 適⽤不可能.
(:actionmove-up ...
:precondition (and(empty ?x ?y-old) ...)
:effects(and (not (empty ?x ?y-old))...))PDDL : Planning Domain Description Language

5.

弱点: 画像ベース⼊力 になると適⽤不可能
なぜならプランナは実⾏するのにPDDLモデルが必要!

Latplan (AAAI18, ICAPS19, IJCAI20, JAIR 22) はこの問題を解決
画像に対する事前知識なし (画像に対するアノテーションなど)
⼈に由来するラベル・記号は⼀切なし : "タイルが9つある", "動く"6.

Latplan の⽬標: 知識獲得ボトルネックの解消
状態遷移の観測データ

PDDL Model→(:actionmove-up:precondition(and(empty ?x ?y-old) ...)
:effects(and (not (empty ?x ?y-old))...))
Latplan が⾃動化すべき作業は 2つ あり、これらは別のタスク:
1. 記号⽣成:シンボル = PDDL内で使われる語彙Types
Examplesオブジェクト panel 7 , x 0 , y 0 …
述語(empty ?x ?y)命題
p 28 = (empty x 0 y 0 )アクション(slide-up panel 7 x 0 y 1 )2. アクションモデル獲得:

状態遷移ルールをシンボルを⽤いて表現することWhen Empty(x, yold) ∧ … ;Then ¬Empty(x,yold) ∧ …

7.

Latplan は PDDL を⾃動⽣成 (IJCAI20, JAIR22)

7.1.

Latplan は PDDL を⾃動⽣成 (IJCAI20, JAIR22)

7.2.

Latplan は PDDL を⾃動⽣成 (IJCAI20, JAIR22)

Latplan が⽣成・接地するシンボルは すべて 無名シンボル ( gensym )⼈間の使う ⾃然⾔語シンボル は扱わない
⾃然⾔語シンボルへの接地は 寄⽣的 記号接地(*) とよばれる
理由: ⼈間の作った世界の離散化に依存しているから (例: 虹 は7⾊?)(*) Taddeo, Mariarosaria, and Luciano Floridi. "Solving the symbol grounding
problem: a critical review of fifteen years of research." Journal of
Experimental & Theoretical Artificial Intelligence 17.4 (2005): 419-445.
Created: 2024-09-06 Fri 14:46

8.

Latplan が解けるパズル/プランニング問題の例

8-puzzle, 15-puzzle, Lights-Out, Twisted Lights-out, Blocksworld, Sokoban

8.1.

成功率 (1ドメインあたり40タスク)

8.2.

成功例 / 失敗例

9.

このシステムの肝: ⽣成モデリング +ちゃんと古典プランニングのことを勉強すること
Latplan は PDDLと互換性のあるアクションモデルを画像から学習する.
「PDDLと互換性がある」ってどういう意味 ?
アクション: a = Eat(pizza)
前提条件: pre(a) = ¬full() ∧ have(pizza ) — 空腹かつピザがある
効果: 削除効果: del(a) = {have(pizza )} — ピザはなくなって
効果: 追加効果: add(a) = {full()} — 満腹になる
状態遷移ルール: z t+1 = (z t ∖ del(a) ) ∪ add(a)効果 del(a), add(a) は z t に依存しない.

よくある世界モデル は そこをわかってない！ (⾃動計画の⼈がいない)
よくある世界モデル: z t+1 = なぞのニューラルネット(z t , a)

PDDLに変換できない → ⾼速なソルバを使えない

10.

⾼速ソルバのためにPDDL記号モデルを学習→⾔語の制約を NNモデルに埋め込まないといけない
PDDLでは、アクションの効果と状態 z t は独⽴している.
→ z t と独⽴な変数 e を導⼊する必要あり。

これを 離散的隠れ変数 (Gumbel-Softmax) + 変分学習 で訓練。
グラフィカルモデルが数学的根拠を与える

11.

離散表現学習: Gumbel-Softmax VAE ほか

11.1. 離散表現学習: Gumbel-Softmax VAE ほか

2017年ぐらい以降、多数の⼿法が考案されている(REBAR, RELAX, VQVAE, SQVAE, …)
ニューロシンボリックをするなら要チェック!

12.

シンボル は⼀種類だけではない
命題シンボル (handempty, …) vs. アクションシンボル (pickup,…).

これらは 別の名前空間に存在する.
⾃然⾔語シンボルも同様:
I like an apple : 動詞
Thanks for the like on Facebook! : 名詞
Common Lisp (Lisp-2) vs. Scheme (Lisp-1)→ 別の名前空間 にあるシンボルは別の⾔語制約が必要。

13.

PDDL: 6つの名前空間, 6つのメカニズム

13.1. PDDL: 6つの名前空間, 6つのメカニズム

13.2. PDDL: 6つの名前空間, 6つのメカニズム

13.3. PDDL: 6つの名前空間, 6つのメカニズム

問題シンボル: 「マリオのステージを表すシンボル」→ 別の状態空間を⽣成
Stage 1-1, Stage 1-2, …

13.4. PDDL: 6つの名前空間, 6つのメカニズム

問題シンボル: 「マリオのステージを表すシンボル」→ 別の状態空間を⽣成
Stage 1-1, Stage 1-2, …
ドメインシンボル: 「別のゲームを表すシンボル」 → 別のアクションを⽣成
マリオ、ゼルダ、ドンキーコング、F-Zero …

13.5. PDDL: 6つの名前空間, 6つのメカニズム

問題シンボル: 「マリオのステージを表すシンボル」→ 別の状態空間を⽣成
Stage 1-1, Stage 1-2, …
ドメインシンボル: 「別のゲームを表すシンボル」 → 別のアクションを⽣成
マリオ、ゼルダ、ドンキーコング、F-Zero …

14.

実際 Latplan を述語論理に拡張可 (ICLR2021 workshop)
Latplan/FOSAE++ : 画像内の異なるオブジェクトに使えるアクションを学習

追加制約: Successor State Axiom (⾮束縛変数の禁⽌ [Reiter, 1991])
アクション: a = Eat(pizza) : 引数 pizza

効果: 発表(フロム, アーマードコアの新作)↑ pizzaを使わないので禁⽌

新たな制約が 述語シンボル のグラウンディングを可能にした15.

Extending the generative model (unpublished)
Lifted actions,Parameters x

Predicates, too.
Compatible withFirst Order Logic.

Temporal actions,Action durations d

Compatible with
LTL.

Domain symbol D,
Problem symbol P

Allows mixeddomain training?

16.

Part 1: Conclusion
Goal: 理性的な実世界エージェント

Latplan で記号接地異なるシンボルは 別々の制約が必要

⽣成モデルによって制約を精緻に記述可能

記号接地するなら 対象⾔語を ちゃんと 理解して 正しく モデル化しよう!

質問: 2つまで17.

Part 2:

理性的な実世界エージェントのアーキテクチャを考える→ 表現学習以外 の プランニング+機械学習18.

理性的な実世界エージェントのアーキテクチャ

18.1. 理性的な実世界エージェントのアーキテクチャ

18.2. 理性的な実世界エージェントのアーキテクチャ

18.3. 理性的な実世界エージェントのアーキテクチャ

18.4. 理性的な実世界エージェントのアーキテクチャ

18.5. 理性的な実世界エージェントのアーキテクチャ

18.6. 理性的な実世界エージェントのアーキテクチャ

18.7. 理性的な実世界エージェントのアーキテクチャ

19.

探索ヒューリスティクスの学習:

RL(ICAPS 2022)

SL(IJCAI 2024)

20.

ICAPS22

21.

Value function learning
SGD Loss function:

11∑ |V (s) − E a∈A [Q(a, s)]| 2|B| s∈B 2
B : batches in the experience replay
Research Questions:

Q: RLだけで 古典プランニングを解けるか? (A: 不可)
Q: RLだけで プランニングを⾼速化できるか? (A: 不可)
Q: プランニングの道具と適切に組み合わせれば? (A: 可)Lessons learned: 古典プランニングを⽢く⾒るな

22.

Why Classical Plannning is difficult for RL?
Rewards in Classical Planning:′1ifsis a goal,′r(s, a, s ) = {0 otherwise.

This is extremely sparse.
Any non-goal states are equally worthless
No guidance for RL until a goal,
which is difficult to find in the first place!

23.

Potential-Based Reward Shaping (PBRS)
for Sparse Rewards
Given a potential function ϕ(s) , redefine rewards as:r^(s, a, s ′ ) = r(s, a, s ′ ) + γϕ(s ′ ) − ϕ(s).
Important: PBRS preserves the optimal value function

V γ∗ (s) = V^γ∗ (s) + ϕ(s).

= learning the residual from ϕ(s)Ng, Harada, Russell. "Policy invariance under reward transformations: Theory andapplication to reward shaping." ICML. Vol. 99. 1999.
Created: 2024-09-06 Fri 14:46

24.

Heuristic Function h(s) in classical planningDistance estimateh(s) = 5⟷s − s 1 − s 2 − s 3 − s 4 − goal (おおよそ)Many implementations: h add , h FF , h CEA , …
(Bonet&Geffner 01, Hoffmann 01, Helmert 08) もっと新しいのもある

Heuristics satisfies thePBRS requirements

Let's use h(s) for PBRS!

25.

Issue 1: Discounting
RL : discounted rewards ↔ Planning : undiscounted costs
Our solution:
Training : Convert h(s) → h γ (s) : discounting h(s) for PBRSh(s)1 − γ h(s)ϕ(s) = h γ (s) = ∑ γ ⋅ 1 =.
1−γt=1t

Planning : Convert V γ (s) → V (s) : undiscounting a learned V γ (s)1 − γ V (s)V γ (s) =⇔ V (s) = log γ (1 − (1 − γ)V γ (s)).
1−γ

26.

Issue 2: Handling First-Order Logic Input
Our solution: Neural Logic Machine (NLM) [Dong et. al. ICLR 2019]26.1. Issue 2: Handling First-Order Logic Input
Our solution: Neural Logic Machine (NLM) [Dong et. al. ICLR 2019]26.2. Issue 2: Handling First-Order Logic Input
Our solution: Neural Logic Machine (NLM) [Dong et. al. ICLR 2019]26.3. Issue 2: Handling First-Order Logic Input
Our solution: Neural Logic Machine (NLM) [Dong et. al. ICLR 2019]26.4. Issue 2: Handling First-Order Logic Input
Our solution: Neural Logic Machine (NLM) [Dong et. al. ICLR 2019]26.5. Issue 2: Handling First-Order Logic Input
Our solution: Neural Logic Machine (NLM) [Dong et. al. ICLR 2019]26.6. Issue 2: Handling First-Order Logic Input
Our solution: Neural Logic Machine (NLM) [Dong et. al. ICLR 2019]

Size & Permutation invariant to FOL binary inputs
Quite useful for various FOL tasks
ILP [Dong et. al. ICLR 2019]
Regression (our work)

27.

Results
Skipped28.

ICAPS 2022 : Conclusion
Sparse Rewards
1 if s is a goal,r(s) = {0 otherwise.

Potential-Based
Reward Shaping

ゴールにたどり着くのがとても難しいV γ∗ (s) = V^γ∗ (s) + ϕ(s)ϕ(s) = 距離の⾒積もり h(s)Sparse Reward を解決

Discounting

First-Order Logic Input

1 − γ h(s)h γ (s) =1−γ
V (s) = log γ (1 − (1 − γ)V γ (s))
これがないとh(s) = ∞ のとき死ぬ

異なるサイズの問題に汎化

Q: RLだけで 古典プランニングを解けるか? (A: 不可)
Q: RLだけで プランニングを⾼速化できるか? (A: 不可)
Q: プランニングの道具と適切に組み合わせれば? (A: 可)Lessons learned: 古典プランニングを⽢く⾒るな

29.

IJCAI24

RL 嫌いなんで … 教師あり学習!

30.

Task: Learn the shortest path cost

30.1. Task: Learn the shortest path cost

30.2. Task: Learn the shortest path cost

Q: Can we exploit the admissibility of heuristics in training?

31.

Stop using (Mean) Square Errors!

31.1. Stop using (Mean) Square Errors!

31.2. Stop using (Mean) Square Errors!

31.3. Stop using (Mean) Square Errors!

31.4. Stop using (Mean) Square Errors!

31.5. Stop using (Mean) Square Errors!

31.6. Stop using (Mean) Square Errors!

31.7. Stop using (Mean) Square Errors!

31.8. Stop using (Mean) Square Errors!

31.9. Stop using (Mean) Square Errors!

31.10. Stop using (Mean) Square Errors!

32.

32.1.

32.2.

32.3.

33.

Thinking with Distributions
Is N (μ, σ) the correct distribution for h ∗ ?

33.1. Thinking with Distributions
Is N (μ, σ) the correct distribution for h ∗ ?

33.2. Thinking with Distributions
Is N (μ, σ) the correct distribution for h ∗ ?

33.3. Thinking with Distributions
Is N (μ, σ) the correct distribution for h ∗ ?

33.4. Thinking with Distributions
Is N (μ, σ) the correct distribution for h ∗ ?

33.5. Thinking with Distributions
Is N (μ, σ) the correct distribution for h ∗ ?

34.

What is the correct distribution?
Follow the Maximum Entropy Principle (Jaynes 1957):

Choose the distribution with the largest entropy
among those that satisfy the expert knowledge / constraint.

↪ We know a lower bound h ≤ h ∗ !
This is our expert knowledge!

35.

What is the max-ent distribution for our assumption?

35.1. What is the max-ent distribution for our assumption?

35.2. What is the max-ent distribution for our assumption?

35.3. Results

36.

IJCAI 2024 : Conclusion
We learn h ∗Square error = Gaussian

Gaussian is a lie

Max-ent: Truncated Gaussian

Take-home message: Whenever you see a square error, doubt it!

37.

理性的な実世界エージェントのアーキテクチャ

38.

探索アルゴリズムの改善:

MCTS +GaussianBandit(ECAI 2024)

MCTS +
Power Bandit(SoCS 2024
extendedabstract)

39.

ECAI 2024

40.

Monte Carlo Tree Search (General version)

40.1. Monte Carlo Tree Search (General version)

40.2. Monte Carlo Tree Search (General version)

40.3. Monte Carlo Tree Search (General version)

40.4. Monte Carlo Tree Search (General version)

40.5. Monte Carlo Tree Search (General version)

40.6. Monte Carlo Tree Search (General version)

40.7. Monte Carlo Tree Search (General version)

40.8. Monte Carlo Tree Search (General version)

Heuristic function
Game✗ Hand-coded(e.g., Go)✗ Not accurate

40.9. Monte Carlo Tree Search (General version)

Heuristic function

Simulation / RolloutGame✗ Hand-coded✔ Finite horizon (9x9)(e.g., Go)✗ Not accurate

40.10. Monte Carlo Tree Search (General version)

Heuristic function

Simulation / Rollout

Game✗ Hand-coded✔ Finite horizon (9x9)(e.g., Go)✗ Not accurate✔ Dense reward40.11. Monte Carlo Tree Search (General version)

Heuristic function

Simulation / Rollout

Game✗ Hand-coded✔ Finite horizon (9x9)(e.g., Go)✗ Not accurate✔ Dense reward

ClassicalPlanning40.12. Monte Carlo Tree Search (General version)

Heuristic function

Simulation / Rollout

Game✗ Hand-coded✔ Finite horizon (9x9)(e.g., Go)✗ Not accurate✔ Dense reward

ClassicalPlanning✗ Infinite horizon

40.13. Monte Carlo Tree Search (General version)

Heuristic function

Simulation / Rollout

Game✗ Hand-coded✔ Finite horizon (9x9)(e.g., Go)✗ Not accurate✔ Dense reward

Classical✗ Infinite horizon

Planning✗ Sparse reward40.14. Monte Carlo Tree Search (General version)

Heuristic function

Simulation / Rollout

Game✗ Hand-coded✔ Finite horizon (9x9)(e.g., Go)✗ Not accurate✔ Dense reward

Classical✔ Automated✗ Infinite horizon

Planning✗ Sparse reward40.15. Monte Carlo Tree Search (General version)

Heuristic function

Simulation / Rollout

Game✗ Hand-coded✔ Finite horizon (9x9)(e.g., Go)✗ Not accurate✔ Dense reward

Classical✔ Automated✗ Infinite horizon

Planning✔ Domain-Independent ✗ Sparse reward

41.

Backup in MCTS : Avg

41.1. Backup in MCTS : Avg vs. Min

41.2. Backup in MCTS : Avg vs. Min = GBFS, A*

GBFS: Traditional SotA
UCT has been bad(UCT = MCTS+UCB1)

Schulte and Keller. "Balancing exploration and exploitation in classical planning."
SOCS, 2014
Created: 2024-09-06 Fri 14:4642.

Why: Poor theoretical understanding of bandits.
UCB1 i = μ i − c√ logniN , for μ i ∈ [0, c]
N : parent visit, n i : visit for child i
μ i : mean over the subtree of i
Rewards must have a known, fixed, shared reward range.
But h(s) have no known range!
Requirments unsatisfied. All theoretical guarantees violated.
Our solution: Gaussian Bandit defined on Entire R = [−∞, ∞]UCB1-Normal2 i = μ i − σ i √log N , for μ i ∈ R
μ i , σ i : mean / stdev over the subtree of i43.

Results (ECAI 2024)

44.

New Algorithm : Model the minimum correctly
Fit the data to…
UCB1

a known finite support distribution [0, 1] , [3, 5]

UCB1-Normal a Gaussian distribution[−∞, ∞]Do heuristics have known bounds e.g. [3, 5] ? No!
Are heuristic samples ∈ [−∞, ∞] ? No! It is non-negative!

0 ≥ h(s)Gaussian assumption is STILL WRONG

45.

What distribution is the right answer?
Range
Gaussian

Unbounded ✗Exponential Half-BoundedUniform

BoundedHow it is distributed?

45.1. What distribution is the right answer?
RangeGaussian

How it is distributed?

Unbounded ✗Exponential Half-Bounded Smallest value is most common ✗Uniform

BoundedEqually likely around min and max

45.2. What distribution is the right answer?
RangeGaussian

How it is distributed?

Unbounded ✗Exponential Half-Bounded Smallest value is most common ✗Uniform

BoundedEqually likely around min and max

PowerBounded

Smallest value is rare46.

But Why? What theory justifies Power?
Central Limit Theorem: Given i.i.d. RVs x 0 , … x n , there is a sequencea n > 0, b n s.t. ∃μ, σnxi − bn
Sn = ∑⟶ N (μ, σ)ani=0

46.1. But Why? What theory justifies Power?
Central Limit Theorem: Given i.i.d. RVs x 0 , … x n , there is a sequencea n > 0, b n s.t. ∃μ, σnxi − bn
Sn = ∑⟶ N (μ, σ)ani=0Extreme Value Theorem type 1: Given i.i.d. RVs x 0 , … x n , there is asequence a n > 0, b n s.t. ∃μ, σ, ξxi − bn
M n = max
⟶ EVD(μ, σ, ξ)an46.2. But Why? What theory justifies Power?
Central Limit Theorem: Given i.i.d. RVs x 0 , … x n , there is a sequencea n > 0, b n s.t. ∃μ, σnxi − bn
Sn = ∑⟶ N (μ, σ)an
i=0Extreme Value Theorem type 1: Given i.i.d. RVs x 0 , … x n , there is asequence a n > 0, b n s.t. ∃μ, σ, ξxi − bn
M n = max
⟶ EVD(μ, σ, ξ)anExtreme Value Theorem type 2: Given i.i.d. RVsx 0 < … < x k < … < x n , there is a sequence a n > 0, b n s.t. ∃μ, σ, ξp(x|x > x k ) ⟶ GPD(μ, σ, ξ)GPD : Generalized Pareto Distribution is the way to go. Why?

46.3. Power, Uniform, Exponential, Pareto are special casesof Generalized Pareto GPD(θ, σ, ξ) .
minmax

ξ > 0 = Paretoθ∞ξ = 0 = Exponentialθ∞ξ < 0 = (Flipped) Power θ θ − σξ
ξ = −1 = Uniformθ θ − σξξ < −1θ θ − σξ47.

Modeling the average47.1. Modeling the average = Fitting the dist. with Gaussian

47.2. Modeling the maximum

47.3. Modeling the maximum = Fitting the tail dist. with GP

48.

New Algorithm : Model the minimum correctly
Fitting GPD itself is difficult (computational issue)→ fit subclasses: Uniform and PowerLower bound Upper bound
UCB1Known 0Shape

Known 1

UCB1-Normal −∞∞UCB1-Uniform Unknown ℓ

Unknown u

Fixed, Flat

Unknown u

Rare near goals

UCB1-Power

Known 0i
UCB1-Uniform i = ui +l− (u i − l i )√6n i log N2ai
UCB1-Power i = auii+1− u i √6n i log N

49.

Results (SoCS 2024 Extended Abstract)

50.

ECAI 2024 + SoCS 2024: Conclusion
UCT is slow inClassical Planningμ − c√ logniN(ECAI 2024)
Use GaussianBandit!

μ − σ√log NWhy?

(SoCS 2024)
Use Uniform /Power!
u i +l i− (u i − l i )√6n i log N2ui ai√6n i log N
a i +1 − u ih(s) ∉ [0, c]h(s) ∈ [−∞, ∞](fixed range)

STILL WRONG!

0 ≤ h(s)Use bandits correctly!

51.

Conclusion & Take-home message
記号接地:
PDDLを 正しく モデル化しよう!
→グラフィカルモデル
ヒューリスティクス学習:
RL : Reward Shaping を 正しく やろう!

Discouning , Undiscounting
SL : h ∗ (s) を 正しく モデル化しよう!
Truncated Gaussian
探索アルゴリズム改善 / Bandit:h(s) を 正しく モデル化しよう!
→ Gaussian, Power

正しさへのこだわりはいつか実を結ぶはず(⼤変だけど)52.

Deep RL は 正しい か?
研究のやり⽅に問題があるように思われる

1つの変更で全部が影響受ける
なぜ性能良くなったのか、わからなくない?

再現性の問題も、ある…
Leslie Kaelbring: RLの評価は最低20シードないと認めない！
Deep RL は 全部ごった煮

The science as a sane researcher:

表現学習

Split the architecture into parts

ヒューリスティック

Study each part individually

探索アルゴリズム

Correct mathematical modeling

Active Learning

こういうアプローチに⽴ち返るのがいいと思います…

Contiual Learning

53.

LLM + Planning (, Reasoning) が成功するには?
単体ではおそらくプランニング不可 by Rao (Subbarao Kambhampati)
おおよそRLと同じような問題を抱えている (ごった煮)
全部⼀度にこなそうとしている
表現学習 : ここだけはとても汎化している
探索 : 全くしていない(Reflex Agent) か ⾮常に原始的 (CoT)
ヒューリスティクス : 「常識」の丸暗記
プランニングに対する 解像度 が低い
Gundawar, Atharva, et al. "Robust Planning with LLM-Modulo Framework: Case
Study in Travel Planning." arXiv
Kambhampati, Subbarao, et al. "LLMs Can't Plan, But Can Help Planning in LLMModulo Frameworks." arXiv
Valmeekam, Karthik, et al. "On the planning abilities of large language models-acritical investigation." Neurips 2023
Created: 2024-09-06 Fri 14:4654.

⾃分が将来的にやりそうなネタ
表現学習 : LLM を使ってPDDL⽣成 (Latplanと同じ)
ヒューリスティクス : LLM を使ってロボットのガイド
Planning Modulo LLM : 探索の中からLLMを使う
探索 : LLM で CDCL とかやると⾯⽩そう
現在あまりインターンは採⽤していないが、共同研究は可能!
MIT-IBM Watson AI Lab