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
- 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.
- 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.
- 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.
- 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.