Alignment-based compositional semantics for instruction following

1 Introduction

• The model represents instruction following as nested alignments: sentence sequences align to atomic actions, and each sentence–action pair aligns syntax to an action graph.These alignments support grounded compositional semantics without requiring an intermediate logical representation of sentence meaning.Source: §1 · p. 1
• A graph-valued conditional random field scores instruction–action alignments and environment transitions over full plans, enabling planning machinery rather than independent action decisions.Sequence-level reasoning can distinguish actions specified by text from actions performed automatically to satisfy pragmatic constraints.Source: §1 · p. 1
• 15–20% relative error reductions over several state-of-the-art results, while outperforming strong task-specific baselines on all three benchmarks.The benchmarks are map reading, maze navigation, and puzzle solving.Source: §1 · p. 2
• The benchmarks vary in plan length and complexity and in the quantity and quality of their accompanying language; the framework also addresses noisy text and over- or under-specified plans.The introduction notes that these tasks pose challenging search problems.Source: §1 · p. 2, Figure 1 · p. 2

2 Related work

• Semantic parsers map text to formal commands and learn from reward provided by executing predicted commands, but their scoring cannot incorporate current or future environment state.They generally require a task-specific formal language, limiting environments with novel strings or arbitrary real quantities.Source: §2 · p. 2
• Semantic-parsing work has studied maze navigation, while a blocks-world task was introduced for situated parsing of spatial robot commands.Policy-based approaches have also been evaluated on map reading and gameplay.Source: §2 · pp. 2–3
• Greedy inference in a semantic parser can have a policy interpretation, a distinction noted for Vlachos and Clark (2014).This is distinct from policy estimators that learn directly over primitive actions.Source: §2 · p. 2
• Linear policy estimators incorporate instructions into state observations and select primitive actions, but flat features cannot model language or action compositionality.Such approaches are restricted to problems simple enough, and action spaces small enough, to characterize effectively with a single feature vector.Source: §2 · pp. 2–3
• The two families have been applied to disjoint task sets; the paper seeks to combine their strengths for general instruction following.Prior work combining aspects of both addressed a different class of gameplay problems.Source: §2 · pp. 2–3

3 Representations

• Training examples pair an instruction sequence with a demonstrated action sequence, which can also be represented as state–action–state triples.Each instruction and action is treated as a structured object rather than a raw string or primitive action.Source: §3 · p. 3
• Instructions are represented by dependency-parse trees, while each situated action is represented by a grounding graph supplied by the environment model.The alignment connects sentence syntax to the environment state through its grounding graph.Source: §3 · p. 3, Figure 2 · p. 3
• Grounding graphs represent action and environment entities with nodes and edges bearing features such as action indicators, distances, and visible landmark names.The graph formalism is intended to accommodate task-specific choices and can be constructed from structured virtual environments or perceptual-system outputs.Source: §3 · p. 4
• With atomic-entity and relation labels, unique node labels, and single-feature edges, grounding graphs recover the existentially quantified portion of first-order logic.The representation can implement large parts of classical neo-Davidsonian semantics.Source: §3 · p. 4
• Graph labels and features can represent strings and real values, allowing lexical features such as edit distance to connect words with landmark names.These features support behavior with novel strings or other features unseen during training.Source: §3 · p. 4
• A joining feature function maps pairs of label sets to feature vectors, with task-specific choices intended to emulate prior modeling decisions.The framework is designed to remain flexible across experiments.Source: §3 · p. 4

4 Model

• Path structure links instruction sequences to action sequences, while action structure models the compositional relationship between utterances and the actions they specify.Source: §4 · p. 4
• A block-structured, graph-valued conditional random field combines alignment potentials relating instructions to actions with transition potentials encoding the environment model.Its variables take structured values, and sentences align to subsets of state–action sequences.Source: Figure 3 · p. 5

Path structure: aligning utterances to actions

• Latent sequence alignments support under- and over-specified plans and lookahead, rather than requiring each instruction to map immediately to an action.When the agent faces a wall, an implicit rotate action may be needed before it can follow an explicit direction.Source: Path structure: aligning utterances to… · p. 5
• Sequence alignments are constrained to be monotonic; with a fixed alignment, the globally normalized model is equivalent to a linear-chain CRF.Source: Path structure: aligning utterances to… · p. 5

Action structure: aligning words to percepts

• Within a sentence–action pair, hidden structure-to-structure alignments connect words and syntactic dependencies with graph nodes and relations.The scoring function softens grammar-like constraints by allowing words to license predicates, multiple words to specify one predicate, and edges to be skipped.Source: Action structure: aligning words to… · pp. 5–6
• The word–graph scoring function combines aligned word–node scores with scores for aligned descendants, and remains well-defined with cyclic relation graphs when the dependency parse has no cycles.Source: Action structure: aligning words to… · p. 6

5 Learning and inference

• Latent alignments make the training objective harder than the convex objective obtained without them, so the method replaces summation with maximization and alternates conditional updates.The procedure uses iterated conditional modes to alternate between maximizing over alignments and parameters.Source: §5 · p. 6
• O(|x||y|) time suffices to sum over structure-to-structure alignments when graph out-degree is bounded by a constant.The dynamic program computes the alignment score using a chart over words and graph nodes.Source: §5 · p. 6
• Because the normalizer over all candidate action sequences is intractable in the state spaces considered, training approximates it using alternative actions sampled from the environment model.Parameter optimization uses L-BFGS, and alignment maximization can be performed exactly with Viterbi.Source: §5 · pp. 6–7
• At test time, the model alternates over alignments and output paths, using Viterbi for both when feasible and beam search for paths when Viterbi is computationally infeasible.Known path-length bounds allow dynamic programs to consider paths of all lengths.Source: §5 · p. 7

Map reading

• Map reading tests informal, sometimes redundant spoken instructions, with grammatical errors and test landmarks never observed during training.The task uses maps with landmark coordinates and names, and instructions specify a path to an unlabeled destination.Source: §6 · p. 7
• The map model learns directional preferences for “top,” supports allocentric and egocentric references, and prefers nearer destinations when choices arise.The reported “top” feature favors positioning above a landmark, sometimes below it, and rarely to the side; proximity preferences are text-independent.Source: Table 2 · p. 7, §6 · p. 7

Evaluation results

• Across the three tasks, the model achieves state-of-the-art results in map reading and puzzle solving and outperforms task-specific maze-navigation systems.The map results are reported as a substantial margin; the maze comparison also includes a baseline without action structure.Source: §6 · pp. 7–8, Table 1 · p. 7, Table 4 · p. 8

Maze navigation

• Maze navigation requires highly compositional language, and the model outperforms task-specific systems and its variant without grounding graphs.Table 3 reports success as the percentage of actions yielding a correct position and orientation after one instruction, under leave-one-map-out evaluation.Source: §6 · p. 8, Table 3 · p. 8

Puzzle solving

• Crossblock’s search challenge is finding a sequence that eliminates all blocks; the model’s text-informed heuristic solves instances that naïve beam search misses.The model achieves state-of-the-art performance when matching the human-specified plan exactly and substantially outperforms a no-text baseline on task completion.Source: §6 · p. 8, Table 4 · p. 8

Evaluation results

• The authors identify lookahead and high-level reasoning as important in instruction following, while proposing more sophisticated planner coupling as future work.They describe inducing planning heuristics from side information such as text as a problem for future work.Source: §6 · p. 8

• The paper presents an alignment-based compositional model for following natural-language instruction sequences and demonstrates its effectiveness on varied tasks.Source: §7 · p. 8
• The framework provides modular interfaces for studying fundamental linguistic issues from a machine-learning perspective.Source: §7 · p. 9
• Learned pragmatics helps resolve ambiguous map references, infer missing maze steps, and turn vague Crossblock hints into plans.A more comprehensive solution might model how instruction-givers’ beliefs over sequences give rise to instructions.Source: §7 · p. 9
• The graph alignment model generalizes classical logical techniques and provides compositional semantics without an explicit formal language for sentence meaning.The authors suggest extending it to question answering.Source: §7 · p. 9
• The general approach yields substantial gains across multiple tasks and contexts.Source: §7 · p. 9