State Transition Graphs for Continuous Motion Planning

20 concepts15 papers2 proposals

Planning trajectories for physical systems—whether a humanoid robot navigating a cluttered room, an autonomous vehicle executing a sharp turn, or a virtual avatar synthesizing realistic human motion—presents a fundamental computational challenge. The space of possible movements is continuous, high-dimensional, and bound by complex constraints like physics, safety, and visual realism. Attempting to optimize a trajectory directly within this continuous space often leads to severe computational bottlenecks or local minima.

To bypass these challenges, a powerful paradigm has emerged: discretizing the continuous state space into a structured state transition graph. By representing valid configurations or short motion snippets as nodes, and permissible movements between them as directed edges, the problem of continuous trajectory generation is transformed into a discrete graph search. This approach works because it shifts the computational burden: instead of solving complex differential equations or high-dimensional optimization problems at runtime, a system can rapidly traverse a pre-computed or structured network of valid states using highly efficient pathfinding algorithms.

Defining the Nodes: What Constitutes a State?

The first step in building a state transition graph is defining what a node represents. Depending on the domain, a node abstracts a specific point or a localized sequence within the continuous space.

In character animation and digital human modeling, nodes typically represent discrete frames, motion primitives, or recurring behavioral patterns. For instance, Liu 0015 et al. construct motion graphs where vertices represent foundational motion primitives. To handle massive datasets more efficiently, Beaudoin introduces "motion-motif graphs," which distill complex motion capture libraries by clustering recurring patterns into abstract motif nodes. This concept extends naturally to specialized communication; Rastgoo et al. highlight how motion graphs stitch together discrete segments of recorded data to produce fluid sign language, while Zhou et al. utilize video motion graphs where individual video frames serve as nodes to synthesize lifelike speech gestures.

In robotics and manipulation, nodes capture physical configurations, contact states, or environmental relationships:

  • Contact Formations: An early framework in A Qualitative Discretization for Two-Body Contacts discretizes the continuous relative motion between 3D objects into distinct "Contact Formations" to simplify assembly planning.
  • Grasp Configurations: For multi-stage manipulation, Bronars et al. map transitions between distinct grasp states, while Toussaint et al. propose "Regrasp Maps" that combine spatial regions and specific grasp configurations into single nodes to solve long-horizon tasks.
  • Locomotion Modes: For systems capable of multiple types of movement, Suh et al. define nodes as discrete states within different locomotion modes (such as driving versus flying).

For autonomous vehicles, the abstraction is closely tied to kinematics. Stiller et al. discretize vehicle states into configuration graphs where each node explicitly defines a position, orientation, and curvature.

[ Continuous Space ] ---> Discretization ---> [ Graph Representation ]
                                                (Nodes: Primitives / Contact States)
                                                (Edges: Valid Transitions)

Defining the Edges: Ensuring Feasible Transitions

A graph is only as useful as the validity of its edges. An edge between two nodes represents a physically realizable, safe, or visually seamless transition. Determining whether an edge should exist—and what its computational "cost" is—requires evaluating the underlying constraints of the physical or virtual world.

In robotic locomotion, edges often dictate how a machine alters its relationship with the environment. Mandery et al. and Borràs et al. model whole-body multi-contact motions by defining edges as the literal addition or removal of a single contact point (such as a hand leaning on a table). To guarantee that these transitions do not cause a robot to fall or violate hardware limits, Ames employs a formal safety oracle to systematically evaluate and verify that transitions between dynamic motion primitives on legged robots remain strictly within safe operational boundaries.

In generative video and animation, edges must ensure visual continuity rather than physical stability. To prevent jarring cuts between disparate motions, Regateiro et al. project animation frames into a learned latent space. Edges are then weighted based on shape and appearance similarity metrics calculated directly within this latent space, allowing the system to compute and interpolate smooth, plausible intermediate frames.

Global Search and Local Execution

Once the continuous space is mapped to a validated graph, finding a trajectory reduces to a shortest-path or minimum-cost search. This formulation guarantees global optimality within the bounds of the graph, bypassing the local minima that plague continuous optimization techniques.

[ Start Node ] --(A* / Dijkstra Search)--> [ Optimal Edge Sequence ] ---> [ Continuous Blending / Execution ]

For global pathfinding, traditional graph search algorithms are highly effective. Choi et al. integrate probabilistic roadmaps with posture transition graphs, utilizing a modified Dijkstra's algorithm to compute a minimum-cost sequence of motion clips and target footprints. Similarly, Stiller et al. apply the A* algorithm to configuration graphs, using a cost function designed to minimize steering fluctuations and path deviations to ensure smooth driving maneuvers.

Alternatively, the graph can be traversed dynamically to react to real-time inputs. Gillies et al. demonstrate this in responsive avatar animation: instead of planning a fixed path from start to finish, the system performs a continuous "graph walk," where a learned value function evaluates the outgoing edges at each node to select the next motion clip based on live environmental or audio features.

Ultimately, state transition graphs succeed because they bridge the gap between high-level semantic planning and low-level execution. By decoupling the combinatorial challenge of sequencing actions from the geometric challenge of smoothing trajectories, they provide a scalable, robust framework for motion synthesis across robotics, autonomous systems, and computer graphics.

Key Foundational Work

Motion Path Synthesis for Intelligent Avatar (2003) — contributed 3 concept elements to this direction.
Planning biped locomotion using motion capture data and probabilistic roadmaps (2003) — contributed 2 concept elements to this direction.
A Qualitative Discretization for Two-Body Contacts (1995) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_latent_space_motion_graphs_4c3122a1,
  title = {latent-space motion graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/latent-space-motion-graphs/rdr_4c3122a1435f40239d51f9f0ac2e8204},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_latent_space_motion_graphs_4c3122a1_v1,
  title = {latent-space motion graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/latent-space-motion-graphs/rdr_4c3122a1435f40239d51f9f0ac2e8204/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake