RoboBoom
KAIST DRCD Lab· November 9, 2026· 3:00

Humanoid Footstep Planning using Graphs of Convex Sets

A KAIST DRCD Lab presenter explains a humanoid footstep planner that uses graphs of convex sets to choose steps and foot placements in real time.

In this talk

  1. 0:04

    Planning steps on a dance pad

    The planner handles a game where a humanoid matches incoming symbols by stepping on arrow-shaped panels. It chooses both which foot to move and where to place it on the selected panel.

  2. 0:29

    Online replanning under a time limit

    A six-step lookahead is updated as new symbols arrive. Each cycle builds a graph, formulates and solves an RMICP, then recovers and refines a path; average runtime is under 200 milliseconds.

  3. 1:21

    From terrain constraints to a convex-set graph

    The method starts with a nonconvex QCQP for terrain feasibility, reachability, and step costs. Its mode-aware graph uses convex feasible regions as nodes and admissible transitions as edges. Relaxed edge choices and semidefinite lifting handle nonconvex terms before a fixed-path solve refines the result.

  4. 2:23

    Benchmark results on stepping stones

    Tests use reproducible stepping-stone terrains generated with a conditional variational autoencoder. On an easier case, all three planners find feasible plans, but this method is faster. On a harder case, it alone returns a feasible plan within the time limit.

Briefs summarise talks and interviews; timestamps open the video at that moment. Claims in a talk are the speaker's own.