Hiding the What, Not Just the Where: Deceptive Planning over Semantic Goal Embeddings

An agent moving through an environment leaks information: every step it takes lets an observer sharpen a guess about where it is going. Existing deceptive path planning deliberately delays that reveal, but only in the crudest sense — it treats goals as bare map coordinates and ambiguity as "roughly equidistant from two pins." Real observers, human or automated, rarely reason that way. They ask a semantic question: is the agent heading to a fuel depot, a communication relay, a medical station? Two buildings a block apart can serve entirely different functions, and two buildings on opposite sides of a city can serve the same one. A path that is perfectly ambiguous between coordinates can be completely revealing about category. This proposal argues that deception should be planned over what a goal means, not only where it sits, and that representing goals as language embeddings — continuous vectors derived from natural-language descriptions — is what makes that both expressive and computationally tractable at scale.

The scale angle is not incidental; it is the reason embeddings earn their place. Exact deceptive planning is brutally expensive: evaluating an observer's belief over a map of 8,895 nodes took more than 9,000 seconds in Xu et al.'s study of magnitude-based deception, and their geometric fix (downscaling the map by a factor of 8 to finish in under 3 seconds) paid for the speedup with a substantial drop in successful deception. Meanwhile, strategic-state search over many goals fares no better — Pozanco et al.'s optimal centroid search fails outright beyond 16 candidate goals, though their heuristic variant cuts runtime from over 500 seconds to under 0.2. Our claim is that the combinatorial wall in deceptive planning is partly an artifact of treating goals as unrelated discrete symbols, and that a low-dimensional embedding of goal semantics replaces per-goal-pair bookkeeping with inner products — turning an exact computation that explodes with the goal count into an amortized one that grows gently.

Core Claim

Deceptive path planning has never been formulated over semantic goal representations; every cited formulation models goals as coordinates or graph nodes (Masters and Sardiña; Pozanco et al.; Xu et al.; Fatemi et al.; Chen et al.), and the label-embedding literature has never touched path costs, obstacles, or sequential planning (Mueller et al.; Zhang et al.). The two literatures are disjoint, and each one's open problem is the other's solved problem. We propose to close the gap in both directions at once. Specifically: (1) an agent should obfuscate the observer's belief about the goal's semantic class — its functional category — and only secondarily its identity within that class, because class-level confidence is what an observer with conceptual knowledge actually acquires first; and (2) a dual-encoder architecture — one network embedding observed trajectory prefixes, another embedding goal descriptions — makes the observer model an inner-product computation whose cost per step is linear in the number of goals times a small embedding dimension, rather than a per-goal path-likelihood evaluation. The same embeddings give the planner a heuristic: a "semantically ambiguous" state is one whose trajectory embedding is equidistant, in embedding space, from the plausible goal classes — a continuous generalization of Pozanco et al.'s centroid states, which minimized average distance across discrete goal coordinates.

Research Program

The first deliverable is a benchmark, because none exists. We will annotate maps from the Moving-AI grid-pathfinding suite (Sturtevant) — the same source used by Masters and Sardiña's 50-problem deceptive-planning suite — with functional descriptions. Each candidate goal location receives a natural-language description ("a fuel storage depot behind the perimeter fence"), drawn from a controlled vocabulary of overlapping categories, so that goals vary independently in physical position and semantic class: nearby goals with different functions, distant goals with the same function, and near-synonymous descriptions whose embeddings partially overlap, in the way Zhang et al.'s description-enhanced embeddings handle multi-sense definitions. Goal counts will range from 4 to 1,000, because the interesting failure regime is precisely where exact methods die.

The second deliverable is the amortized observer. We train a dual-encoder model — the architecture whose speed at scale is documented by COTS, which ran cross-modal retrieval over 10,000 times faster than single-stream fusion models at comparable accuracy on 14 million pairs — to imitate an exact Bayesian goal recognizer of the Ramírez-and-Geffner type on small maps where the exact computation is feasible, then apply it unchanged to large maps and large goal sets. The trajectory encoder reads the observed prefix; the goal encoder reads the description. The observer's posterior is a softmax over similarities:

$$P(g_i \mid o_{1:t}) \;\propto\; \exp\!\big(s(\phi(o_{1:t}),\, e_i)/\tau\big),$$

where $\phi(o_{1:t})$ embeds the trajectory prefix observed so far, $e_i$ embeds goal $i$'s description, $s$ is cosine similarity, and $\tau$ is a temperature fit to the exact recognizer on small maps. One property of this design matters more than any other: the goal embeddings are precomputed once, so a belief update over $N$ goals costs $N$ dot products — no per-goal path planning, no pairwise distances.

The third deliverable is the planner. The agent's objective at each step is to delay the observer's confidence about the true goal's class, subject to a bound on path cost. Concretely, we maximize the time until the observer's posterior mass on the true class crosses a threshold, while the total path stays within a factor $1+\varepsilon$ of the optimal cost:

$$\max \; t^* \;=\; \max \Big\{ t : \sum_{i \in C_{\text{true}}} P(g_i \mid o_{1:t}) < \delta \Big\}, \quad \text{cost(path)} \le (1+\varepsilon)\,\text{cost(path}^*\text{)},$$

where $C_{\text{true}}$ is the semantic class of the real goal and $\delta$ is the detection threshold. Planning proceeds hierarchically, mirroring the dissimulation/simulation taxonomy of Masters and Sardiña: first pick a cover class — a semantically plausible alternative whose description embedding is close enough to the truth to stay credible but functionally different enough to matter — then plan a spatially deceptive route within the cover class using classical ambiguity techniques. This two-level structure is exactly what single-level coordinate deception cannot express: Lourenço et al.'s belief-obfuscation framing and Strouse et al.'s information-minimizing "poker-faced" agent both flatten intent into one categorical variable.

One design decision is shaped directly by a negative result: the goal embeddings will be fine-tuned jointly with the deception objective rather than frozen after pre-training. UNICORN's decoupling gap finding showed that latent representations trained by mutual-information objectives alone are not optimized for what the downstream policy actually needs; a goal embedding that is good for text classification is not necessarily arranged so that "deceptively ambiguous" states exist and are reachable. We treat this as a hypothesis to test, not an assumption (see Decisive Checks).

Proposed Experiments

The primary evaluation is on the semantically annotated Moving-AI maps. Metrics are: time-to-class-detection $t^*$ (steps until the observer's true-class posterior exceeds $\delta$); path-cost ratio versus the optimal truthful path; and wall-clock planning and belief-evaluation time as the goal count $N$ grows from 4 to 1,000. The central scaling result we want is a curve of deception retention versus $N$: exact and geometric-abstraction methods should degrade as $N$ grows, while the amortized embedding method should stay nearly flat in both deception and runtime, because its per-step cost is a batched inner product.

A second experiment isolates the semantic claim. We construct matched pairs of scenarios: one where a coordinate-ambiguous midpoint sits between two goals of the same class, and one where it sits between goals of different classes. A coordinate-only observer cannot distinguish these; a class-aware observer (our dual encoder, and separately an LLM prompted as an observer) collapses the first case instantly. Classical strategies — including the pruned-dissimulation $\pi_{d4}$ that Masters and Sardiña report achieving full deception at substantially lower cost than simulation $\pi_{d1}$ — should show near-zero class-level deception in the same-class-adjacent regime, while our planner, which can pick a cover class across the map, should not. Robustness to observer type is measured by running every agent against both a coordinate-only observer and a class-aware observer; a deception method that only fools one of them is of limited use.

A third experiment tests transfer in the spirit of Fatemi et al., whose graph-network policy trained on 8×8 and 16×16 grids transferred zero-shot to unseen 32×32 grids, but along the goal-set axis instead of the map-size axis: train the trajectory encoder and planner on maps with 8 goals, evaluate with 500 goals never seen in training, including descriptions paraphrased to test whether the encoder generalizes by meaning rather than by memorized strings. This is the regime where Chen et al.'s count-based DPP_Q improved average deceptiveness by 12.53% over the $\pi_{d1}$–$\pi_{d4}$ baselines but was confined to 10×10 grids with a single decoy; no reported result exists on Lacuna for deceptive planning with more than a handful of candidate goals, which is the point.

Baselines

The do-nothing reference is the optimal truthful path (A* on the grid). It defines the cost floor — every deceptive method is charged as a percentage overhead against it — and the zero-deception ceiling on $t^*$: an optimal path reveals the goal as fast as anything can, so any method that fails to beat it on time-to-detection is doing nothing. The strongest classical competitor is the strategy family of Masters and Sardiña, run on our annotated maps with the same observer, the same cost budget, and the same detection threshold; their $\pi_{d4}$ pruned-dissimulation is the one to beat on cost-adjusted deception, and their suite construction (three injected bogus goals on Moving-AI maps) is the template ours extends. The strongest scale competitor is Xu et al.'s subgoal-graph method: we give it the identical wall-clock budget on identical maps and compare deception retention as goal count grows — their reported trade-off (offline evaluation cut from over 9,000 seconds to under 3 seconds at scaling factor $k=8$, with a substantial drop in successful deceptive paths, and near-minimal deception loss only at $k=2$) is the number to match on runtime while beating on deception. The strongest learned competitor is Fatemi et al.'s graph-network RL agent, which we run with its own deception bonus on our maps and, for fairness on the multi-goal question, also in an extended variant we implement with several decoys, since their formulation supports exactly one. Beating it means higher $t^*$ at matched cost on maps with goal counts beyond its single-decoy design. Finally, two ablations isolate the proposal's key ingredient: the identical planner and observer with goal embeddings replaced first by one-hot class identifiers and second by centroids of geometric clustering of goal coordinates — if the semantic embedding is doing real work, both ablations should collapse specifically in the same-class-adjacent and paraphrase conditions, not in general.

Why not just…?

Why not just cluster goals geometrically and assign group IDs? This is the cheapest version of our idea and the most serious threat. Geometric clustering plus centroid planning (Pozanco et al.) would capture some hierarchical deception without any language model. It falls short on two counts that our experiments will measure directly. First, physical proximity and functional similarity dissociate — an embassy beside a power plant — so geometric clusters misidentify the classes a knowledgeable observer actually uses, and the same-class-adjacent experiment is built to expose exactly this: geometric clustering produces cover classes that a class-aware observer sees through instantly. Second, the evidence on discrete identifiers is consistent: Mueller et al. report that semantically empty class indices required 16–32 training examples where label grounding needed 1–4, with 49.2% versus 23.9% one-shot accuracy on Yahoo! Answers, and this data hunger reappears in our setting as failure to generalize to paraphrased goal descriptions the clustering never saw. The one-hot ablation is the honest test: if it matches our full method on every condition, the semantic claim is wrong and we will say so.

Why not just use subgoal graphs for scale? Xu et al. already solved the runtime problem, so a reviewer will ask why a new representation is needed. The answer is that their abstraction compresses the map while our method compresses the goal set, and the two failure axes are independent: their own results show the speedup at $k=8$ costs a substantial fraction of successful deceptive paths, and their retrieval stage between abstract waypoints risks leaking intent through truthful sub-trajectories. Our scaling wall is different — goal count, not node count — and no reported result on Lacuna shows any method maintaining deception past a few dozen candidate goals. The scaling experiment directly compares the two on the axis each was built for; if subgoal graphs dominate on both axes, our method has no reason to exist, and we will report that.

Why not just have an LLM plan the deceptive path end-to-end? A large language model knows what a fuel depot is and could verbalize a plan. The file's evidence is against it on the two counts that matter here: Mueller et al. note that generative decoding is markedly slower than discriminative embedding matching at inference and carries hallucination risk, and in physical planning a hallucinated coordinate is a colliding or non-executable trajectory, while the two-stream COTS result shows dual encoders preserving cross-modal accuracy at more than 10,000 times the inference speed of single-stream fusion. Our design still uses an LLM, but in the right place: as the class-aware observer in the robustness experiment, where its world knowledge makes it the strongest adversary to fool. If an LLM observer defeats our planner, that is a finding, not a failure of the experiment.

Why not just reward deception in vanilla RL and let it learn? Chen et al. found count-based Q-learning prone to local optima and confined to small grids, and Fatemi et al. showed that RL without graph-structured perception fails to transfer across map scales at all. More fundamentally, a scalar deception bonus over an open goal set has no gradient signal about which cover story to sell — the semantic structure our planner reasons over is exactly the piece the reward-only formulation cannot represent. We will nonetheless run a PPO agent with our class-level deception reward as a baseline, because if the reward alone suffices, the explicit embedding machinery is unjustified.

Decisive Checks

Three results would decide the proposal. First, the flat scaling curve: deception retention and per-step belief-update cost roughly independent of $N$ from 4 to 1,000 goals, against the degradation of exact and subgoal-graph baselines — this is the scale claim, and it rests on the amortized inner-product observer, not on any property of language itself. Second, the dissociation result: in same-class-adjacent scenarios, classical coordinate deception collapses under a class-aware observer while the cover-class planner does not, and the one-hot and geometric-clustering ablations collapse alongside the classical methods — this is the semantic claim, and it is falsifiable by the ablation. Third, the coupling result: jointly fine-tuned goal embeddings beat frozen text-classification embeddings on reachable-ambiguity (whether states exist whose trajectory embedding is genuinely equidistant between plausible classes), testing whether UNICORN's decoupling gap transfers to this setting. If the first two hold and the third fails, the contribution survives with frozen embeddings and a simpler recipe; if the first two fail, the coordinate-centric paradigm was right all along, and that too would be worth knowing — the literature currently offers no experiment that could have told us.