• Soundness, Completeness, Optimality

  of the algorithms are important

  (compared to "planning" in other AI fields)

States as 1st-order logic formula, described in PDDL language.

(empty x0 y0)
(is panel6 x1 y0)
(up    y0 y1), (down y1 y0)...
(right x0 x1), (left x0 x1)...

The cost of human involved for converting real-world problems into inputs for domain-independent symbolic systems

(embedding the lambda calculus inside a neural architecture)

ARMS (Yang AIJ07) LOCM (ICAPS09) Argall (AIJ09) Mourao (UAI12)

All taking the symbolic inputs to find the action models

Near-Symbols : Parses natural language sentences with a clear grammatical structure.

"Constructing Symbolic Representations for High-Level Planning" (AAAI14)

What it does

Converting a Semi-MDP Model to a PDDL Model by set-theoretic representation

i.e. Model-to-Model conversion, not generating a model from the scratch

Semi-MDP contains Action Symbols

move and interact (Playroom)

Sensor inputs are structured (Labels for "State Variable" are known)

x/y-distance, light level, whether a monkey cries

→ Each sensor has a distinct meaning (no overwrap)

Handles Images, but with strong assumptions (almost symbol) e.g.

Tic-Tac-Toe with Ellipse Detectors (Bardu 10)

→ Almost immediately provides propositions

→ Also, Domain-dependent ("3x3 grid" "Ellipse" are hard-coded)

No Prior Knowledge : labels/symbols such as "9 tiles", "moving"

No Prior Knowledge : labels/symbols such as "9 tiles", "moving"

No Prior Knowledge : Domain-independent Image-based planner

They are randomly sampled image transitions

• No state descriptions (unlike AlphaGo (Silver et al. '16))
• No expert traces (unlike AlphaGo)
• No rewards (unlike DRL systems)

• No access to the simulator (unlike DQN (Mnih et al. '15) for Atari)

  → cannot ask for more examples

• No action symbols (no system to our knowledge)

  　　(e.g. ↑↓←→AB in Atari, grids in Go)

  → doesn't know what's happening in each transition

Plus misc techniques e.g. Batchnorm, Dropout

An AutoEncoder that enforces a certain distribution on $Z \subset \mathbb{R}^n$over the dataset $X$

You have $X=${ 10k images of apples }. If you train a Gaussian VAE on $X$, then $Z = Encode(X) \approx N(\mu,\sigma)$for some $\mu,\sigma \in \mathbb{R}^n$.

VAE needs a reparametrization trick because random distributions are non-differentiable.

Reparametrization for $N(\mu,\sigma)$: $\mu + \sigma N(0,1)$

$\mu$and $\sigma$are differentiable (trainable) vectors, $N(0,1)$is not.

Additional optimization penalty which enforces $Z \sim \textbf{Categorical}$:

　　　→ $z\;$converges to a 1-hot vector e.g. $\langle 0,0,1,0 \rangle$.

Example: Represent an MNIST image with 30 variables of 8 categories.

8-puzzle using digits from MNIST database

MNIST 8-puzzle has cleanly separated objects -> This domain does not.

Completely different puzzle problems can be solved by the same system

Does not assume "objects" are static (objects may disappear)

Does not assume grid-like structures

SAE implementation uses a denoising layer (Denoising AE, Vincent 08)

Planners typically perform a forward search (Dijkstra, $A^＊$)

Without Action Symbols, successor generation becomes challenging

• SAE with $|z|=36 \text{bit}$

  → Generate $2^{36}$potential successors, then filter the invalid

• With action symbols, (e.g. up, down, left, right)
• → We can enumerate the candidates in constant time.

Should identify the number of schemas from what is un/affected

• We do not need an action label; it is linear anyways
• Then, AMA ≡ prediction task ($\approx$scene prediction in video)
  • We can train a neural network $a(s) = t\;$by minimizing $|t-a(s)|$
  • Most DL literature follows this path

Binary classifier telling which transitions are valid

• Invalid transitions: All transitions that are not valid.
  • We lack the definition; Cannot be generated.
• Can we collect the invalid data?

  • Teleportation violates the laws of physics. (at least in a macro scale)

    

Training a positive & negative classifier from the positive & unlabelled datasets.

• Positive: Training Input. Observed data are valid, guaranteed
• Unlabelled: Successor candidates generated by the AAE
  • Some are valid, some are invalid

Noise are applied to the planning inputs (init/goal images)

G: Gaussian noise, s/p: salt/pepper noise

• Easy instances: Majority of instances are solved
• Harder instances: Still many instances are solved

LatPlan is an architecture : Any system with SAE is an implementation

Different SAE → reason about different types of raw data

• Autoencoders for text, audio [Li 2015, Deng 2010]
• Example:
  • Transition rule "This is an apple, this is a pen → oh, ApplePen!"

• When this happens, Latplan brings AI to a new level e.g.

  1000 steps of natural language reasoning with logic, not by reflex

  • Fundamentally impossible for short-sighted / greedy agents

• Latplan assumes nothing about the environment machinery (grids, movable tiles…)
• Latplan assumes fully-observable, deterministic domains
• Next step: Extending Latplan to MDP, POMDP
  • Gumbel-Softmax layer → just a Softmax layer? (probability)
  • $AO^*$, $LAO^*$algorithms for optimal planning under uncertainty

SAE can generate propositional symbols (state $s = \{q,r\ldots\}$)

• 1st-order logic (predicate $p(a,b)$)
• We need object recognition from images (parameters $a,b$)
• SAE with networks for object recognition (e.g. R-CNN) should achieve this

AMA₂ (AAE/AD) is a neural network, thus precondition/effects are in a blackbox

Hinders deriving heuristic functions

Knowledge extraction by Konidaris et al.('14,'15), δ-ILP (Deepmind) ?

Structured input (e.g. light switch, x/y-distance) ↔ unstructured image

Action Symbols (move, interact)

Just converting Semi-MDP model to a PDDL model.

Could be used for extracting PDDL from AAE/AD

TSP (Hopfield and Tank 1985)

Neurosolver for ToH (Bieszczad and Kuchar 2015)

The input/output are symbolic.

Embedded NNs inside a search to provide the search control knowledge

(i.e. node evaluation function)

Sliding-tile puzzle and Rubik’s Cube (Arfaee et al. 2011)

Classical planning (Satzger and Kramer 2013)

The game of Go (AlphaGo, Silver et al. 2016)

DQN assumes predetermined action symbols (↑↓←→+ buttons).

DQN relies on simulators. ↔ Latplan reverse-engineers a simulator.

DQN does not work when it does not know what action is even possible!

SCAN system (deepmind)

• Maps continuous latent vector and human-provided symbolic vector

  • This does not make sense. They are missing points
  • Because they don't know what symbols are for
  • They are for efficient, automated reasoning!
  • Floats are not efficient, humans shouldn't be involved

δ-ILP (Inductive Logic Programming)

• ILP robust to noise
  • Extracting rules from AAE/AD to form a PDDL?

Systems based on individual pixels lack generalization

• Noise / variations can make the data entirely different

  

• must acquire the generalized features
• = a nonlinear function that recognize the entanglements between multiple pixels

Main differences: Purposes and the abstraction layer

• AlphaGo = Subsymbolic (DLNN eval. function) + Symbolic (MCTS)

AlphaGo = Subsymbolic (NN eval. func) + Symbolic (MCTS)

• However, domain-specific – specialized in Go, "Grids" / "Stones" are known
• Huge expert trace DB — Not applicable when data are scarse (e.g. space exploration)

• Is supervised learning necessary for human?

  True intelligence should search / collect data by itself

DQN = Subsymbolic (DLNN) + Reinforcement Learning (DLNN)

Domain-independent Atari Game solver (Invader, Packman…), however:

• RL Acting: Greedily follow the learned policy → no deliberation!
• You can survive most Atari games by reflex

— Robust systems augmented by the latest DL tech

— Better Theoretical Guarantee than Reinforcement Learning

— Decision Making Independent from Learning

Machine learning may contain errors (convergence only on $t\rightarrow \infty$, not on real time)

• Images → Fraud symbols/model/graph

• Optimal path on a fraud graph or graph disconnected

  A* completeness, soundness, optimality (admissible heuristics)

• Fraud visualized plan (noisy) / no plan found

Both perception and decision making depend on training

• When the learned policy is wrong,
  • the solution could be suboptimal
  • It could even fail to find solutions (incomplete agent)

… AlphaGo was unprepared for Lee Sedol’s Move 78 because it didn’t think that a human would ever play it.

Cade Metz. "In Two Moves, that Redifined the Future." Wired, 2016

Symbols are strong abstraction mechanisms becasue

Meanings do not matter

No understanding necessary: Does a symbol $X$mean an apple or a car?

Logical reasoning by mechanical application of rules

• Domain-independent planning : mystery vs nomystery

  Logistic domains where symbol names are mangled (truck → shark)

Composable

A latent vector is a conjunction (and)

Heuristic functions use modus ponens to derive guidance