Source code for hybrid_aif.planning.tree

"""Level-wise expansion of the policy tree, and the two folds the planners take over it.

:func:`expand_level` applies every first-step action to every node of one level.
:func:`evaluate_policy_tree` and :func:`evaluate_policy_tree_total` fold the tree
by path sums into the per-policy term tree and G of the enumerated grid;
:func:`evaluate_branching_tree` branches each child over its outcomes and folds by
a softmax expectation per level (sophisticated planning). The children of node
``i`` sit at ``i·b + a``, so leaf order is the order of
:func:`~hybrid_aif.planning.enumerate.enumerate_policies` and policy ``p``'s
depth-``t`` ancestor is ``p // b^(H − 1 − t)``.

Design: docs/design/system.md (policy tree)
"""

import math

import jax
import jax.numpy as jnp
import jax.tree_util as jtu
from jax import Array

from hybrid_aif.interval import Interval
from hybrid_aif.objectives.base import TermTree, total
from hybrid_aif.planning.base import (
    Beliefs,
    BranchFn,
    StepTermsFn,
    TerminalTermsFn,
    TransitionFn,
    UseBound,
)
from hybrid_aif.planning.enumerate import _merge_trees, _step_warrant, enumerate_policies


[docs] def expand_level( qs_nodes: Beliefs, actions: Array, transition_fn: TransitionFn, step_terms: StepTermsFn, t: int, ) -> tuple[Beliefs, TermTree]: """Push every node through every action: one level of the policy tree. ``qs_nodes`` is a belief pytree with a leading node axis ``n``; ``actions`` is int32 ``(b, K)``. Returns the children's beliefs, leading axis ``n·b`` (child of ``i`` under ``a`` at ``i·b + a``), and each child's step term tree with the same leading axis. ``t`` is the static step index, passed to ``step_terms`` as an int32 scalar. """ n = jtu.tree_leaves(qs_nodes)[0].shape[0] b = actions.shape[0] step = jnp.int32(t) def one(qs: Beliefs, action: Array) -> tuple[Beliefs, TermTree]: qs_next = transition_fn(qs, action) return qs_next, step_terms(qs_next, action, step) over_actions = jax.vmap(one, in_axes=(None, 0)) children, trees = jax.vmap(over_actions, in_axes=(0, None))(qs_nodes, actions) def flatten(x: Array) -> Array: return x.reshape((n * b,) + x.shape[2:]) return jtu.tree_map(flatten, children), jtu.tree_map(flatten, trees)
def _first_step_actions( num_controls: tuple[int, ...], controlled: tuple[bool, ...] ) -> tuple[Array, Array]: """The grid's first-step control set ``(b, len(num_controls))``.""" return enumerate_policies(num_controls, 1, controlled)[:, 0, :] def _repeat_nodes(tree, branching: int): """Carry every node's leaves down to its ``branching`` children (child ``i·b + a`` of ``i``).""" return jtu.tree_map(lambda x: jnp.repeat(x, branching, axis=0), tree)
[docs] def evaluate_policy_tree( num_controls: tuple[int, ...], controlled: tuple[bool, ...], policy_len: int, init_qs: Beliefs, transition_fn: TransitionFn, step_terms: StepTermsFn, terminal_terms: TerminalTermsFn | None = None, ) -> tuple[TermTree, Array]: """Score every policy of the grid by summing the step term trees along its path. ``terminal_terms`` at the horizon-end beliefs is merged in once. Returns the term tree (leading per-policy axis on every leaf) and the aligned policy set, ``enumerate_policies(num_controls, policy_len, controlled)``. """ policies = enumerate_policies(num_controls, policy_len, controlled) actions = _first_step_actions(num_controls, controlled) b = actions.shape[0] qs = jtu.tree_map(lambda x: x[None], init_qs) out: TermTree = {} for t in range(policy_len): qs, tree = expand_level(qs, actions, transition_fn, step_terms, t) out = _merge_trees(_repeat_nodes(out, b), tree) if terminal_terms is not None: out = _merge_trees(out, jax.vmap(terminal_terms)(qs)) return out, policies
[docs] def evaluate_policy_tree_total( num_controls: tuple[int, ...], controlled: tuple[bool, ...], policy_len: int, init_qs: Beliefs, transition_fn: TransitionFn, step_terms: StepTermsFn, terminal_terms: TerminalTermsFn | None = None, ) -> tuple[Interval, Array]: """Score every policy of the grid straight to its G, one Interval per node. The metrics-free sibling of :func:`evaluate_policy_tree`: each level's step tree is folded with :func:`~hybrid_aif.objectives.base.total` and added to the parent's G (an empty level passes it through), then the terminal terms. Seeded with the step tree's static ``derived`` and ``approximate`` flags. Returns the per-policy G and the aligned policy set. """ policies = enumerate_policies(num_controls, policy_len, controlled) actions = _first_step_actions(num_controls, controlled) b = actions.shape[0] warrant, approximate = _step_warrant(init_qs, transition_fn, step_terms, policies) qs = jtu.tree_map(lambda x: x[None], init_qs) g = Interval(jnp.zeros((1,)), jnp.zeros((1,)), warrant, approximate) for t in range(policy_len): qs, tree = expand_level(qs, actions, transition_fn, step_terms, t) g = _repeat_nodes(g, b) if tree: g = g + total(tree) if terminal_terms is not None: g = g + total(jax.vmap(terminal_terms)(qs)) return g, policies
def _point(tree: TermTree, use_bound: UseBound) -> Array: """The chosen point of ``total(tree)``, one value per leading index.""" g = total(tree) return {"midpoint": g.midpoint, "lower": g.lower, "upper": g.upper}[use_bound] # Bytes the deepest level holds per child: BRANCHING_BELIEF_FACTOR times its belief plus # BRANCHING_BYTES_PER_NODE. The fixed part is the top of the range measured on 2026-10-23 on # categorical beliefs (about 100 to 290 bytes; mostly unfused step-term intermediates); the part # in proportion to the belief covers intermediates that grow with it (a Gaussian belief's # covariance products; measured 3.9 to 4.9 beliefs per child on Gaussian beliefs of 16 to 64 # dimensions, so 6 leaves a margin of about a fifth). Both err high. # Design: docs/design/sophisticated-memory.md (SM2). BRANCHING_BELIEF_FACTOR = 6 BRANCHING_BYTES_PER_NODE = 290 def belief_bytes(init_qs: Beliefs) -> int: """Bytes of one belief: its leaves' sizes, from their static shapes and dtypes.""" return sum( int(math.prod(x.shape)) * jnp.dtype(x.dtype).itemsize for x in jtu.tree_leaves(init_qs) ) def _per_child(belief_bytes: int) -> int: return BRANCHING_BELIEF_FACTOR * belief_bytes + BRANCHING_BYTES_PER_NODE def branching_tree_bytes( n_actions: int, n_outcomes: int, horizon: int, belief_bytes: int, split_depth: int | None = None, batch_size: int | None = None, ) -> int: """Estimated bytes the deepest level of :func:`evaluate_branching_tree` holds. Whole-level (``batch_size`` ``None``): every one of the ``(A·m)^(H−1)·A`` deepest children at once, each :data:`BRANCHING_BELIEF_FACTOR` beliefs plus :data:`BRANCHING_BYTES_PER_NODE`. Chunked at ``split_depth``: ``batch_size`` subtrees at once, each ``(A·m)^(H−1−d)·A`` children, plus the ``(A·m)^d`` nodes at the split. ``batch_size`` is taken to divide the node count, as :func:`chunk_choice` chooses it; a remainder would add its own subtrees. """ per_child = _per_child(belief_bytes) width = n_actions * n_outcomes if batch_size is None or split_depth is None or not 1 <= split_depth <= horizon - 1: return width ** (horizon - 1) * n_actions * per_child nodes = width**split_depth subtree = width ** (horizon - 1 - split_depth) * n_actions * per_child return min(batch_size, nodes) * subtree + nodes * per_child def _largest_divisor(n: int, at_most: int) -> int: """The largest divisor of ``n`` that is at most ``at_most`` (at least 1).""" return next(k for k in range(max(1, min(at_most, n)), 0, -1) if n % k == 0) def chunk_choice( n_actions: int, n_outcomes: int, horizon: int, belief_bytes: int, budget: int, split_depth: int | None = None, ) -> tuple[int, int | None]: """``(split_depth, batch_size)`` that keep the estimate (:func:`branching_tree_bytes`) within ``budget``; ``batch_size`` is ``None`` when the whole level fits, or when no node lies at ``split_depth`` to chunk over (outside ``1 … horizon − 1``). A given ``split_depth`` is kept, with the largest batch that fits. Without one, the split deepens from 1 until a single subtree fits. The batch is the largest divisor of the node count that fits, so ``lax.map`` has no remainder to evaluate beside its batches. When not even one subtree fits at any depth, the batch is 1 at the depth whose estimate is least (the nodes held at the split grow with depth as the subtrees shrink), and the budget is a best effort. """ if branching_tree_bytes(n_actions, n_outcomes, horizon, belief_bytes) <= budget: return (1 if split_depth is None else split_depth), None if horizon < 2 or (split_depth is not None and not 1 <= split_depth <= horizon - 1): return (1 if split_depth is None else split_depth), None per_child = _per_child(belief_bytes) width = n_actions * n_outcomes depths = list(range(1, horizon)) if split_depth is None else [split_depth] held = { d: (width**d * per_child, width ** (horizon - 1 - d) * n_actions * per_child) for d in depths } for d in depths: nodes_bytes, subtree = held[d] if budget - nodes_bytes >= subtree: return d, _largest_divisor(width**d, (budget - nodes_bytes) // subtree) least = min(depths, key=lambda d: sum(held[d])) return least, 1 def _soft_value(G: Array, gamma: float, ok: Array | None) -> Array: """``Σ_a softmax(−γ G)_a G_a`` along the last axis; an action with ``ok`` false has ``G = +∞`` there, so it takes no weight and adds nothing.""" if ok is None: return jnp.sum(jax.nn.softmax(-gamma * G, axis=1) * G, axis=1) weights = jax.nn.softmax(jnp.where(ok, -gamma * G, -jnp.inf), axis=1) return jnp.sum(weights * jnp.where(ok, G, 0.0), axis=1)
[docs] def evaluate_branching_tree( actions: Array, horizon: int, gamma: float, init_qs: Beliefs, transition_fn: TransitionFn, step_terms: StepTermsFn, terminal_terms: TerminalTermsFn | None = None, branch_fn: BranchFn | None = None, use_bound: UseBound = "midpoint", legal: Array | None = None, split_depth: int = 1, batch_size: int | None = None, ) -> Array: """The root's per-action G under sophisticated (closed-loop) planning. Each child is scored by the ``use_bound`` point of its step tree (zero when empty) and, short of the horizon, branched by ``branch_fn`` over its ``m`` outcomes (``m = 1`` without a branch closure); the last depth adds the terminal terms. The fold runs bottom-up:: G(node, a) = g_step(child) + Σ_o p(child, o) · V(child, o) V(node) = Σ_a softmax(−γ · G(node, ·))_a · G(node, a) with ``V = 0`` below the deepest children. Returns ``G`` at the root, ``(b,)``. The deepest level holds ``(b·m)^(H−1)·b`` beliefs. ``legal`` is a bool ``(horizon, b)``: ``legal[t, a]`` false gives action ``a`` at depth ``t ≥ 1`` the value ``+∞`` in that node's softmax, so it carries no weight in ``V``; the tree still expands it. Row 0 is not read: the root's ``G`` is returned unmasked. A mask with no true entry in a row has no action to weigh at that depth, and gives ``NaN``. With ``batch_size`` set, the ``(b·m)^split_depth`` nodes at depth ``split_depth`` (1 ≤ ``split_depth`` ≤ ``horizon − 1``) have their subtrees evaluated that many at a time with :func:`jax.lax.map` instead of all at once; the result is the same up to float rounding, and the deepest level held at once shrinks to ``batch_size`` subtrees. """ if horizon < 1: raise ValueError(f"evaluate_branching_tree: horizon must be at least 1, got {horizon}") if batch_size is not None and batch_size < 1: raise ValueError( f"evaluate_branching_tree: batch_size must be at least 1, got {batch_size}" ) if batch_size is not None and split_depth < 1: raise ValueError( "evaluate_branching_tree: split_depth must be at least 1 (the root is one node, " f"with nothing to chunk over), got {split_depth}" ) b = actions.shape[0] def values(qs: Beliefs, t_start: int) -> tuple[Array, Array]: """``(G, V)`` of the nodes ``qs`` at depth ``t_start``: ``G`` ``(n, b)``, ``V`` ``(n,)``.""" levels: list[tuple[int, Array, Array | None]] = [] v_tail = None for t in range(t_start, horizon): n = jtu.tree_leaves(qs)[0].shape[0] if batch_size is not None and t == split_depth and t > t_start and batch_size < n: v_tail = jax.lax.map( lambda q, t=t: values(jtu.tree_map(lambda x: x[None], q), t)[1][0], qs, batch_size=batch_size, ) break children, tree = expand_level(qs, actions, transition_fn, step_terms, t) g = _point(tree, use_bound) if tree else jnp.zeros((n * b,)) p = None if t + 1 < horizon: if branch_fn is None: p, qs = jnp.ones((n * b, 1)), children else: p, after = jax.vmap(branch_fn)(children) qs = jtu.tree_map(lambda x: x.reshape((-1,) + x.shape[2:]), after) elif terminal_terms is not None: g = g + _point(jax.vmap(terminal_terms)(children), use_bound) levels.append((t, g, p)) v = v_tail for t, g, p in reversed(levels): if p is not None: g = g + jnp.sum(p * v.reshape(p.shape), axis=1) G = g.reshape(-1, b) ok = legal[t][None, :] if legal is not None and t >= 1 else None v = _soft_value(G, gamma, ok) return G, v G, _ = values(jtu.tree_map(lambda x: x[None], init_qs), 0) return G[0]