betaFeedback

WorksComputer Science

Capturability-Aware Footstep Planning in Cluttered Environments: A Recursively Feasible Sequential MPC on Axis-Aligned Safe Corridors

Abstract

A fundamental aspect of humanoid footstep planning is to jointly guarantee obstacle avoidance and locomotion stability. This paper presents a capturability-aware sequential Model Predictive Control (MPC) framework for Linear Inverted Pendulum (LIP)-based humanoid footstep planning in the presence of obstacles. The proposed method combines obstacle avoidance with capturability constraints through safe corridors constructed as sequences of intersecting rectangles, yielding a sequential MPC framework with recursive feasibility guarantees for the LIP-based planning layer. The planner autonomously adapts to constrained scenarios, switching to in-place walking when obstructions—such as doors assumed to be open during planning but unexpectedly found to be closed during execution—block forward motion. Performance is largely independent of the prediction horizon, allowing high success rates while keeping the computational cost low. The approach is validated in high-fidelity simulations with the humanoid robot Digit, demonstrating a practical solution for capturable humanoid footstep planning in cluttered environments.

Introduction

Ensuring safe navigation in cluttered, human-centric environments is a necessity for humanoid robots. A key challenge is footstep planning, which must produce feasible step sequences that guide the robot to its goal while ensuring both collision avoidance and reliable locomotion. Existing methods often rely on Reduced Order Model (ROM) to generate obstacle-free plans without explicit locomotion stability guarantees, whereas approaches focused on the latter typically ignore obstacles. This paper addresses this gap by integrating capturable locomotion with safe corridors, resulting in a capturability-aware sequence of Model Predictive Control (MPC) schemes for footstep planning with recursive feasibility guarantees.

For navigation in cluttered environments, a common strategy is to decompose the free space into a Safe Corridor (SC); a sequence of overlapping convex polytopes; that allows the robot to move from its initial location to the destination without collisions. SCs have been widely applied in motion planning for quadrotors [1], [2], ground robots [3], and humanoids and bipeds [4], [5]. They can be constructed from a seed point using Iterative Regional Inflation by Semidefinite Programming (IRIS) [6], [3], path-based ellipsoidal dilation [2], or voxel-based methods [7], [8]. The Axis Aligned Safe Corridors (AASC) in [7] are particularly appealing for their separable box constraints and efficient collision checking, while encompassing a wide range of environments where obstacles can be effectively approximated by rectangular bounds. By design, however, SCs are purely geometric constraints that ensure collision avoidance, and thus produce motion plans that do not explicitly account for kinodynamic effects.

Overview of the proposed capturability-aware planning framework

Figure 1. Overview of the proposed capturability-aware planning framework: Axis-aligned SCs enable a sequential MPC scheme that reliably drives the robot to its destination, avoiding obstacles and ensuring recursive feasibility.

Turning our attention to bipedal robots, MPC has emerged as a prominent framework for motion planning, as it naturally integrates system dynamics and constraints within a unified optimization problem [9]. Combined with reduced-order models such as the Linear Inverted Pendulum (LIP) [10], MPC-based approaches have been applied to address a wide range of challenges, from tracking velocity commands [11], [12] to navigating cluttered environments [13], [4], and overtaking moving obstacles [14]. The work of [4] leveraged the decomposition provided by SCs to react to global navigation as a sequence of localized MPC subproblems, thereby reducing computational complexity by restricting planning to the robot’s immediate neighborhood. Nevertheless, a key challenge in MPC-based planners is ensuring recursive feasibility [15], [16], so that feasibility at the current step guarantees feasibility at all future steps.

Recursive feasibility is typically ensured by appropriately designing the terminal components of the MPC, either via a terminal constraint or a terminal cost [15], [16]. Building on the concept of capturability [17], LIP-based MPC approaches have incorporated terminal capture-point constraints to guarantee stability and recursive feasibility [18], [19], though such constraints can hinder convergence for short prediction horizons [20]. The work in [21] established recursive feasibility and stability for given footsteps by constraining future Zero Moment Point (ZMP) velocities, conjecturing values beyond the horizon. Subsequent work in [22] removed the need for a predefined footstep plan via a step-timing adaptation module. A computationally efficient walking pattern generator was proposed in [23] that ensures gait viability by selecting the next step’s location and timing. While these studies address walking in unbounded regions, the presence of environmental boundaries introduces additional constraints that may undermine feasibility. This issue was partially addressed in [24], which introduced a finite-step capture-region constraint, dynamically updated to allow the robot to stop or advance while preserving recursive feasibility. Nevertheless, ensuring feasible MPC footstep plans in the presence of obstacles remains largely open.

To address this gap, this paper proposes a capturability-aware sequential MPC framework for humanoid footstep planning amid obstacles. More specifically, a novel SC generation framework based on a sequence of intersecting rectangles, each associated with capturability guarantees, together with a switching policy that provides conditions for preserving capturability during transitions between consecutive rectangles along the corridor. This substantially extends existing approaches by combining obstacle avoidance, absent from [24], with locomotion-stability considerations not provided by the purely geometric strategy of [4]. Building on this construction, we then develop a LIP-based sequential MPC formulation that guarantees recursive feasibility, thereby jointly ensuring collision-free navigation and capturable footstep planning. High-fidelity MuJoCo simulations with Digit, including comparisons with [4] in randomly generated environments with axis-aligned rectangular obstacles, demonstrate the method’s intrinsic safety and graceful degradation: when obstructions such as closed doors prevent progress, the robot autonomously slows down and switches to in-place walking, unlike approaches that do not explicitly account for capturability. The proposed method provides a practical and reliable solution for capturability-aware humanoid footstep planning in cluttered environments.

LIP-based Capturability & Restricted Spaces

This section discusses the formulation of a recursively feasible LIP-based MPC footstep planner for navigation in obstacle-free rectangular regions.

The Linear Inverted Pendulum and Capturability

The Linear Inverted Pendulum (LIP) model represents a point mass supported by a massless prismatic leg, with the mass constrained to move on a horizontal plane at constant height HH; see Figure 2(a). Its state is given by the position (x,y)∈R2(x,y) \in\mathbb{R}^2 and velocity (x˙,y˙)∈R2(\dot{x},\dot{y}) \in\mathbb{R}^2 of the mass in the inertial frame, while the stance foot location is given by (ux,uy)∈R2(u^x,u^y) \in\mathbb{R}^2. The LIP dynamics along the XX-axis are

Linear Inverted Pendulum model, three-dimensional COM evolution, and top view of COM, DCM, and CCM trajectories

Figure 2. (a) Linear Inverted Pendulum (LIP) model: Center of Mass (COM) moves in a constant-height plane (pink), with the kinematically feasible foot placement region in yellow. (b) 3D evolution of COM (red), Divergent Component of Motion (DCM) offset (blue), and Convergent Component of Motion (CCM) offset (orange dashed); rectangular regions B\mathcal{B} (green) and S\mathcal{S} (blue). (c) Top view of COM, DCM, CCM trajectories and the rectangles B\mathcal{B}, S\mathcal{S}.

ddt[xx˙]=[01ωo20][xx˙]+[0−ωo2]ux(1)\frac{d}{dt} \begin{bmatrix} x \\ \dot{x} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ \omega_o^2 & 0 \end{bmatrix} \begin{bmatrix} x \\ \dot{x} \end{bmatrix} + \begin{bmatrix} 0 \\ -\omega_o^2 \end{bmatrix}u^x \tag*{(1)}

where ωo=g/H\omega_o = \sqrt{g/H} and gg is the gravitational acceleration. By replacing xx with yy and uxu^x with uyu^y in (1), the dynamics along the YY-axis is derived.

Diagonalizing the state matrix in (1) results in the following alternative choice of states

ξx=x+x˙/ωoandηx=x−x˙/ωo(2)\xi^x = x + \dot{x}/\omega_o \qquad\text{and} \qquad\eta^x = x - \dot{x}/\omega_o \tag*{(2)}

and integrating the resulting state-space representation gives

ξx(t)=eωot(ξx(0)−ux)+ux(3)\xi^x(t) = e^{\omega_o t}(\xi^x(0)-u^x)+u^x \tag*{(3)}
ηx(t)=e−ωot(ηx(0)−ux)+ux.(4)\eta^x(t) = e^{-\omega_o t}(\eta^x(0)-u^x)+u^x . \tag*{(4)}

The unstable (3) and stable (4) solutions correspond, respectively, to the Divergent (DCM) and Convergent (CCM) Components of Motion; see [25] and Figure 2(b). Replacing the exponent “xx” with “yy” in (3)–(4) gives the analogous expressions in the YY direction. Following [23], we define ξ−u\xi-u and η−u\eta-u as the DCM and CCM offsets, respectively.

Assuming each step has duration TT and that the interval spanned by the kk-th step is [kT,(k+1)T][kT,(k+1)T], the LIP state and input at the beginning of the kk-th step are given by xk=[xk x˙k yk y˙k]T\mathbf{x}_k = [x_k\ \dot{x}_k\ y_k\ \dot{y}_k]^\mathsf{T} and uk=[ukx uky]T\mathbf{u}_k = [u_k^x\ u_k^y]^\mathsf{T} yielding the following step-to-step dynamics

xk+1=Axk+Buk.\mathbf{x}_{k+1}=A\mathbf{x}_k+B\mathbf{u}_k.

where A=diag⁡{A^,A^}A=\operatorname{diag}\{\hat{A},\hat{A}\}, B=diag⁡{B^,B^}B=\operatorname{diag}\{\hat{B},\hat{B}\} and A^,B^\hat{A},\hat{B} are block diagonal matrices obtained as detailed in Section 3. We also define y=Cx=[x y]T\mathbf{y}=C\mathbf{x}=[x\ y]^\mathsf{T}. The discrete evolution of the system must adhere to the robot’s kinematic constraints, which can be captured by the foot reachability set

Uk={(ukx,uky)∣lx≤ukx−uk−1x≤lx and ly≤m(uky−uk−1y)≤ly}(5)\mathcal{U}_k=\left\{(u_k^x,u_k^y)\mid l^x\leq u_k^x-u_{k-1}^x\leq l^x \ \text{and}\ l^y\leq m(u_k^y-u_{k-1}^y)\leq l^y\right\} \tag*{(5)}

for k≥1k\geq1, m=1m=1 for a right stance foot and m=−1m=-1 otherwise. The rectangular region [lx,lˉx]×[ly,lˉy][l^x,\bar{l}^x]\times[l^y,\bar{l}^y] approximates the set of swing-leg placements that are kinematically feasible when the current stance foot is located at uk−1=(uk−1x,uk−1y)u_{k-1}=(u_{k-1}^x,u_{k-1}^y); see Figure 2(a).

The simplicity of the LIP dynamics allows an explicit computation of the NN-step capture region1 in the form

CN=CNx×CNy(6)\mathcal{C}_N=\mathcal{C}_N^x\times\mathcal{C}_N^y \tag*{(6)}

for N∈{0,1,…}∪{∞}N\in\{0,1,\ldots\}\cup\{\infty\}. Indeed, Digit’s symmetric foot placement in the XX-direction where lˉx=−lx=lx\bar{l}^x=-l^x=l^x results in symmetric NN-step capture regions

CNx={r∈R∣dNx≤r≤dˉNx}(7)\mathcal{C}_N^x=\{r\in\mathbb{R}\mid d_N^x\leq r\leq\bar{d}_N^x\} \tag*{(7)}

with bounds d‾Nx=−d‾Nx=dNx\underline{d}^{x}_{N}=-\overline{d}^{x}_{N}=d^{x}_{N} computed recursively by [17]

d0x=0anddNx=e−ωoT(lx+dN−1x).(8)d^{x}_{0}=0 \quad\text{and} \quad d^{x}_{N}=e^{-\omega_{o}T}\left(l^{x}+d^{x}_{N-1}\right). \tag*{(8)}

The lateral asymmetry in Digit’s foot placement makes the computation of the corresponding region in the YY-direction

CNy={r∈R∣d‾Ny≤r≤d‾Ny}(9)\mathcal{C}^{y}_{N}=\left\{r\in\mathbb{R}\mid\underline{d}^{y}_{N}\leq r\leq\overline{d}^{y}_{N}\right\} \tag*{(9)}

more involved; however, explicit expressions for the bounds d‾Ny\underline{d}^{y}_{N} and d‾Ny\overline{d}^{y}_{N} in (9) were recently derived in [24]. These are omitted for brevity. Note also that the derivations in subsequent sections will focus on the XX-direction; the corresponding YY-direction analysis is analogous, though more involved, and will be omitted for clarity.

Capturability & Restricted Spaces

Consider a rectangular region B=[βx,β‾x]×[βy,β‾y]\mathcal{B}=\left[\beta^{x},\overline{\beta}^{x}\right]\times\left[\beta^{y},\overline{\beta}^{y}\right] within which the COM must remain; see Figure 2(c). Enforcing this geometric constraint in a footstep planner ensures boundary collision avoidance. However, capturability is not guaranteed, motivating the development of a new constraint formulation. This can be achieved by computing a new rectangle S=[w‾x,w‾x]×[w‾y,w‾y]\mathcal{S}=\left[\underline{w}^{x},\overline{w}^{x}\right]\times\left[\underline{w}^{y},\overline{w}^{y}\right] inscribed in B\mathcal{B} so that restricting footsteps u=(ux,uy)\mathbf{u}=(u^{x},u^{y}) in S\mathcal{S} guarantees both capturability and COM containment in B\mathcal{B}. For brevity, the construction of this rectangle is detailed below only for the xx-direction; the yy-direction is analogous.

Without loss of generality, consider the first step in a sequence of steps; i.e., k=0k=0. To ensure that the LIP’s state is NN-step capturable, we require that the DCM offset satisfies ξ0x−u0x∈CNx\xi^{x}_{0}-u^{x}_{0}\in\mathcal{C}^{x}_{N}, which by (7) results in d‾Nx≤ξ0x−u0x≤d‾Nx\underline{d}^{x}_{N}\leq\xi^{x}_{0}-u^{x}_{0}\leq\overline{d}^{x}_{N}. Multiplying this inequality with eωote^{\omega_{o}t} and using (3) gives the following bound for the DCM evolution

eωotd‾Nx≤ξx(t)−u0x≤eωotd‾Nxe^{\omega_{o}t}\underline{d}^{x}_{N}\leq\xi^{x}(t)-u^{x}_{0}\leq e^{\omega_{o}t}\overline{d}^{x}_{N}

for t∈[0,T)t\in[0,T). Next we turn our attention to the CCM offset. From [24] we have that −c‾x≤ηkx−ukx≤c‾x-\overline{c}^{x}\leq\eta^{x}_{k}-u^{x}_{k}\leq\overline{c}^{x} for k≥0k\geq0, where c‾x>0\overline{c}^{x}>0 is explicitly computable. Multiplying this inequality for k=0k=0 with e−ωote^{-\omega_{o}t} and using (4) gives

−e−ωotc‾x≤ηx(t)−u0x≤e−ωotc‾x-e^{-\omega_{o}t}\overline{c}^{x}\leq\eta^{x}(t)-u^{x}_{0}\leq e^{-\omega_{o}t}\overline{c}^{x}

for t∈[0,T)t\in[0,T). Combining these two inequalities and noting that x(t)=12(ξx(t)+ηx(t))x(t)=\frac{1}{2}\left(\xi^{x}(t)+\eta^{x}(t)\right) by (2), results in

eωotd‾Nx−e−ωotc‾x2≤x(t)−u0x≤eωotd‾Nx+e−ωotc‾x2\frac{e^{\omega_{o}t}\underline{d}^{x}_{N}-e^{-\omega_{o}t}\overline{c}^{x}}{2}\leq x(t)-u^{x}_{0}\leq\frac{e^{\omega_{o}t}\overline{d}^{x}_{N}+e^{-\omega_{o}t}\overline{c}^{x}}{2}

for t∈[0,T)t\in[0,T), thus bounding the XX-component of the COM so that the first step is NN-step capturable.

Now, to avoid collisions with the boundary of B\mathcal{B}, the lower and upper bounds of the last inequality need to be such that x(t)∈[βx,β‾x]x(t)\in[\beta^{x},\overline{\beta}^{x}] for all t∈[0,T)t\in[0,T); equivalently,

βx≤inf⁡t∈[0,T)12(eωotd‾Nx−e−ωotc‾x)+u0x\beta^{x}\leq\inf_{t\in[0,T)}\frac{1}{2}\left(e^{\omega_{o}t}\underline{d}^{x}_{N}-e^{-\omega_{o}t}\overline{c}^{x}\right)+u^{x}_{0}
β‾x≥sup⁡t∈[0,T)12(eωotd‾Nx+e−ωotc‾x)+u0x.\overline{\beta}^{x}\geq\sup_{t\in[0,T)}\frac{1}{2}\left(e^{\omega_{o}t}\overline{d}^{x}_{N}+e^{-\omega_{o}t}\overline{c}^{x}\right)+u^{x}_{0}.

These conditions specify the admissible interval for u0xu^{x}_{0}, with lower and upper bounds w‾x\underline{w}^{x} and w‾x\overline{w}^{x}, respectively; that is u0x∈[w‾x,w‾x]u^{x}_{0}\in[\underline{w}^{x},\overline{w}^{x}]. The procedure for computing w‾y\underline{w}^{y} and w‾y\overline{w}^{y} is analogous and is omitted for brevity. The end result is the inscribed rectangle S\mathcal{S} shown in Figure 2(c), within which the foot can be placed to guarantee NN-step capturability while avoiding boundary violations. The parameter NN governs the conservativeness of S\mathcal{S}, with N→∞N\rightarrow\infty yielding the most restrictive set.

Recursively Feasible MPC in Rectangular Regions

With the inscribed rectangle S=[w‾x,w‾x]×[w‾y,w‾y]\mathcal{S}=\left[\underline{w}^{x},\overline{w}^{x}\right]\times\left[\underline{w}^{y},\overline{w}^{y}\right] computed as above, an MPC scheme can be formulated for footstep planning that simultaneously ensures capturability and boundary avoidance while providing recursive feasibility guarantees. Let LL denote the prediction horizon of the MPC and for ℓ=1,…,L\ell=1,\ldots,L, define the running cost as

Jℓ(xℓ,uℓ)=∥xℓ−xdes∥2+∥Cxℓ−uℓ∥2\mathcal{J}_{\ell}(\mathbf{x}_{\ell},\mathbf{u}_{\ell})=\left\|\mathbf{x}_{\ell}-\mathbf{x}^{\mathrm{des}}\right\|^{2}+\left\|\mathbf{C}\mathbf{x}_{\ell}-\mathbf{u}_{\ell}\right\|^{2}

where xdes\mathbf{x}^{\mathrm{des}} is the desired LIP state and the second term penalizes excessively long steps. The terminal cost is

JL(xL)=∥xL−xdes∥2.\mathcal{J}_{L}(\mathbf{x}_{L})=\left\|\mathbf{x}_{L}-\mathbf{x}^{\mathrm{des}}\right\|^{2}.

In our MPC formulation, we set L=NL=N; this choice results in less conservative sets.

To incorporate capturability into the MPC, we first compute the maximum number of steps the LIP can take within S\mathcal{S} along the forward x+x^{+}, backward x−x^{-}, rightward y+y^{+}, and leftward y−y^{-} directions. For conciseness, we focus on the forward direction. The allowable number of steps equals the maximum-length lxl^{x} steps the robot can take from its current foot position uxu^{x} before reaching the boundary w‾x\overline{w}^{x} of S\mathcal{S}, i.e., Nx+=⌊∣w‾x−ux∣/lx⌋N^{x+} = \left\lfloor|\overline{w}^{x} - u^{x}|/l^{x}\right\rfloor. Similar equations can be written for the other directions, namely, Nx−N^{x-}, Ny+N^{y+}, Ny−N^{y-}. Grouping the allowable number of steps in all directions in ν=[Nx+ Nx− Ny+ Ny−]\nu= [N^{x+}\ N^{x-}\ N^{y+}\ N^{y-}], we define the ν\nu-step (S\mathcal{S}-restricted) capture region as

Cν=Cνx×Cνy(10)\mathcal{C}_{\nu} = \mathcal{C}_{\nu}^{x} \times\mathcal{C}_{\nu}^{y} \tag*{(10)}

where

Cνx={rx∈R∣d‾Nx−x≤rx≤d‾Nx+x}\mathcal{C}_{\nu}^{x} = \left\{r^{x} \in\mathbb{R} \mid\underline{d}^{x}_{N^{x-}} \le r^{x} \le\overline{d}^{x}_{N^{x+}}\right\}
Cνy={{ry∈R∣d‾Ny−y≤ry≤d‾Ny+y}for right stance{ry∈R∣−d‾Ny−y≤ry≤−d‾Ny+y}for left stance\mathcal{C}_{\nu}^{y} = \left\{ \begin{array}{ll} \left\{r^{y} \in\mathbb{R} \mid\underline{d}^{y}_{N^{y-}} \le r^{y} \le\overline{d}^{y}_{N^{y+}}\right\} & \text{for right stance}\\ \left\{r^{y} \in\mathbb{R} \mid-\overline{d}^{y}_{N^{y-}} \le r^{y} \le-\underline{d}^{y}_{N^{y+}}\right\} & \text{for left stance} \end{array} \right.

Given Cν\mathcal{C}_{\nu}, we introduce a constraint in the MPC that restricts the DCM offset to lie within Cν\mathcal{C}_{\nu} with ν\nu updated at each step to ensure both capturable evolution and boundary avoidance. The resulting MPC formulation is

minimize⁡X,U,N∑ℓ=kk+L−1Jℓ(xℓ,uℓ)+JL(xk+L)subject toxℓ+1=Axℓ+Buℓ,xk=xinitνℓ+1=νℓ−14,νk=νinit−14uℓ∈Uℓξℓ−uℓ∈Cνℓ\begin{aligned} \underset{\mathbf{X},\mathbf{U},\mathbf{N}}{\operatorname{minimize}}\quad& \sum_{\ell=k}^{k+L-1} J_{\ell}(x_{\ell},u_{\ell}) + J_{L}(x_{k+L})\\ \text{subject to}\quad& x_{\ell+1}=Ax_{\ell}+Bu_{\ell},\quad x_{k}=x_{\mathrm{init}}\\ &\nu_{\ell+1}=\nu_{\ell}-\mathbf{1}_{4},\quad\nu_{k}=\nu_{\mathrm{init}}-\mathbf{1}_{4}\\ &u_{\ell}\in\mathcal{U}_{\ell}\\ &\xi_{\ell}-u_{\ell}\in\mathcal{C}_{\nu_{\ell}} \end{aligned}

where 14=[1 1 1 1]\mathbf{1}_{4} = [1\ 1\ 1\ 1], Uℓ\mathcal{U}_{\ell} is the constraint set (5), and Cνℓ\mathcal{C}_{\nu_{\ell}} is the S\mathcal{S}-restricted capture region (10). Starting from an initial condition xinitx_{\mathrm{init}} and allowable step count νinit\nu_{\mathrm{init}}, the MPC computes sequences X={xk+1,…,xk+L}\mathbf{X} = \{x_{k+1},\ldots,x_{k+L}\}, U={uk,…,uk+L−1}\mathbf{U} = \{u_{k},\ldots,u_{k+L-1}\} and N={νk+1,…,νk+L}\mathbf{N} = \{\nu_{k+1},\ldots,\nu_{k+L}\}. Only the first control input uku_{k} is applied, after which the MPC is re-solved at the next step using the updated xinitx_{\mathrm{init}} and νinit\nu_{\mathrm{init}}. This process continues until the goal is reached. Finally, the remark below provides conditions for recursive feasibility.

Remark 1: The MPC formulated above is recursively feasible, provided that S\mathcal{S} is non-empty and that νinit\nu_{\mathrm{init}}, computed from the initial state and footstep locations as described in Section II-B, defines a viable-capture basin containing the LIP’s initial state; see [24 Section IV-C] for details. Note that these recursive-feasibility guarantees apply only to the LIP-based planning layer.

Capturable Footstep Planning Amid Obstacles

This section generalizes the results of the previous section to rectangular corridors in three steps: (i) generating a collection of sequentially intersecting axis-aligned rectangles, (ii) defining a switching policy between them, and (iii) formulating a sequential MPC with recursive feasibility guarantees via capturability, that provides footstep sequences that avoid obstacles and guide the robot to the goal.

Safe Corridor Generation

It is assumed that the environment W\mathcal{W} within which the robot operates is known. To highlight the core concepts and streamline the presentation, we consider here obstacles Oi\mathcal{O}_{i}, i=1,…,Ii=1,\ldots,I, that can be represented as axis-aligned bounding boxes^3 noting that more general obstacle shapes can also be incorporated. Let Wobs\mathcal{W}^{\mathrm{obs}} be the union of all obstacles in W\mathcal{W}.

Given the initial location of the robot, the task is to find a sequence of footsteps that take the robot to the final (desired) location, while avoiding obstacles on the way; that is, at each step kk, the robot’s COM evolves inside W∖Wobs\mathcal{W}\setminus\mathcal{W}^{\mathrm{obs}}. To achieve this, we present a systematic procedure for efficiently constructing SCs, in the form of sequences of collision-free, axis-aligned rectangles

B={y∈R2∣Py≤b, P∈Rl×2, b∈Rl}\mathcal{B} = \left\{y \in\mathbb{R}^{2} \mid Py \le b,\ P \in\mathbb{R}^{l\times2},\ b \in\mathbb{R}^{l}\right\}

that mutually intersect and connect the initial location with the goal; here the shorthand notation Py≤bPy \le b denotes the system of inequalities rjTy≤bjr_{j}^{\mathsf{T}}y \le b_{j}, j∈{1,…,l}j \in\{1,\ldots,l\} with rjTr_{j}^{\mathsf{T}} being the jj-th row of PP and bjb_{j} the jj-th element of bb.

The construction of a safe corridor begins with a sequence of points Π={p1,…,pK}∈W∖Wobs\Pi= \{p_{1},\ldots,p_{K}\} \in\mathcal{W}\setminus\mathcal{W}^{\mathrm{obs}} connecting the start and goal locations. These can be obtained via any sampling-based planner (e.g., Jump Point Search (JPS) [2] or Rapidly-exploring Random Trees (RRT) [28]), subject to the additional requirement that each consecutive line segment is obstacle-free. Given Π\Pi, we implement Algorithm 1, which takes the obstacles {O1,…,OI}\{\mathcal{O}_{1},\ldots,\mathcal{O}_{I}\} and a seed point pseed∈Πp_{\mathrm{seed}}\in\Pi as inputs and returns an obstacle-free rectangle B\mathcal{B}. Algorithm 1 calls the following functions:

Algorithm 1 Generate_Rectangles (p_seed, {O_1, ..., O_I})
1: Input: p_seed, {O_1, ..., O_I}
2: Output: B
3: O ← {O_1, ..., O_I}, i ← 1
4: while O_i ∈ O do
5:   ((r_i)^T, (b_i)) ← find_hyperplane(O_i, p_seed)
6:   B ← append(B, {((r_i)^T, (b_i))})
7:   O ← obstacle_removal(O, {((r_i)^T, (b_i))})
8:   if O is empty then
9:     break
10:  end if
11:  i ← i + 1
12: end while
13: return B
  • find_hyperplane: Given a seed point pseed\mathrm{p}_{\mathrm{seed}} from Π\Pi and the ii-th obstacle OiO_i, this function returns a separating hyperplane that not only distinguishes the obstacle from the pseed\mathrm{p}_{\mathrm{seed}} but also maximizes its distance from it.

  • obstacle_removal: Given a list of obstacles and a hyperplane, this function discards those lying opposite the seed by determining the side of the hyperplane on which each obstacle’s corner points lie.

Algorithm 1 proceeds as follows; see Figure 3 for a graphical illustration. At each iteration, the algorithm uses the seed point pseed\mathrm{p}_{\mathrm{seed}} and the current obstacle set O\mathcal{O}. It selects an obstacle from O\mathcal{O} and, via find_hyperplane, determines the halfspace of that obstacle farthest from pseed\mathrm{p}_{\mathrm{seed}}, which is then appended to B\mathcal{B}. Next, obstacle_removal updates O\mathcal{O} by discarding redundant obstacles, thereby shrinking the obstacle set at each step. This process continues until the obstacle list is empty, yielding an obstacle-free rectangle B\mathcal{B}.

Figure 3. Rectangle generation via Algorithm 1. Starting from pseed\mathrm{p}_{\mathrm{seed}}, the algorithm iteratively selects the separating hyperplane farthest from the seed for each obstacle, intersecting the resulting half-spaces to build an obstacle-free rectangle. Redundant obstacles (e.g., O3O_3, O6O_6) are discarded at each iteration. The final rectangle (red) encloses a local obstacle-free region around pseed\mathrm{p}_{\mathrm{seed}}.

To construct the safe corridor, the procedure begins by using Generate_Rectangles to generate a rectangle B0\mathcal{B}_0 that contains the initial COM location, using it as the seed point. If B0\mathcal{B}_0 also contains the goal, the process terminates. Otherwise, the algorithm scans the points in Π\Pi to identify the first one lying outside B0\mathcal{B}_0, which is then used as the new seed to compute the next rectangle Bnew\mathcal{B}_{\mathrm{new}}. The intersection B0∩Bnew\mathcal{B}_0 \cap\mathcal{B}_{\mathrm{new}} is then checked: if the two rectangles intersect, the algorithm sets B1=Bnew\mathcal{B}_1 = \mathcal{B}_{\mathrm{new}}; if not, the procedure in [4] is applied to connect B0\mathcal{B}_0 and Bnew\mathcal{B}_{\mathrm{new}} through a sequence of mutually intersecting rectangles, computing the Chebyshev centers of their intersections and using them as seed points. By repeating this process, the algorithm yields a safe corridor comprising a sequence of mutually intersecting rectangles {B0,B1,…,BM−1}\{\mathcal{B}_0, \mathcal{B}_1, \ldots, \mathcal{B}_{M-1}\}, with B0\mathcal{B}_0 containing the initial location, BM−1\mathcal{B}_{M-1} containing the goal location and Bi∩Bi+1≠∅\mathcal{B}_i \cap\mathcal{B}_{i+1} \ne\varnothing for i=0,…,M−2i = 0, \ldots, M - 2.

Extending Capturability to Safe Corridors

The safe corridor {B0,B1,…,BM−1}\{\mathcal{B}_0, \mathcal{B}_1, \ldots, \mathcal{B}_{M-1}\} constructed above is purely geometric: Constraining the robot’s COM to remain within it merely ensures collision avoidance. Our goal here is to incorporate capturability into locomotion across the entire corridor, which will enable recursive feasibility to extend from one rectangle to the full sequence. The proposed procedure consists of two stages, outlined below. First, new rectangles Si\mathcal{S}_i inscribed in Bi\mathcal{B}_i are computed using the procedure in Section II-B. Constraining footsteps within Si\mathcal{S}_i ensures both NN-step capturability and that the COM remains inside the original collision-free set Bi\mathcal{B}_i.

Second, we extend capturability across the entire corridor to ensure recursive feasibility for the sequence of MPC schemes that will be defined along it; see Section III-C below. In prior safe-corridor approaches, transitions are purely geometric: Once the COM entered the intersection of two consecutive safe regions, the feasibility region switches to the next. Such policies, however, neglect dynamics, and capturability is not guaranteed, even if it holds within each rectangle individually. To extend capturability across consecutive rectangles, a capturability-aware switching policy is required, ensuring that at the moment of switching, there exists an evolution that brings the robot to a stop without exceeding the new rectangle bounds.

To formalize this notion, we define the virtual stopping point pstop=(xstop,ystop)\mathrm{p}^{\mathrm{stop}} = (x^{\mathrm{stop}}, y^{\mathrm{stop}}) as follows. Given that the LIP is NN-step capturable in Si\mathcal{S}_i, there exists a sequence of at most NN steps that, starting from the current state and footstep, brings the LIP to a full stop. The virtual stopping point pstop\mathrm{p}^{\mathrm{stop}} is defined as the footstep location at which this complete stop occurs. Accordingly, ensuring capturability during the transition requires that—in addition to the COM and current footstep—the virtual stopping point also lies within the intersection Si∩Si+1\mathcal{S}_i \cap\mathcal{S}_{i+1} of the two rectangles; see Figure 4. This way, capturability is preserved under switching, since a guaranteed evolution exists that brings the robot to rest without leaving the next rectangle Si+1\mathcal{S}_{i+1}.

Failed (left) vs successful (right) switching policy activation

Figure 4. Failed (left) vs successful (right) switching policy activation. Switching from SiS_i to Si+1S_{i+1} occurs once the virtual stopping point (purple), the COM (red), and the current footstep (yellow) enter Si∩Si+1S_i \cap S_{i+1}. The current waypoint and DCM are also shown in green and blue, respectively.

The virtual stopping point is directly determined by the DCM offset and can be computed as follows. Focusing on the XX-direction, to ensure NN-step capturability, the XX-component of the DCM offset must be in ξNx\xi^x_N given by (7) with the relevant bounds provided by (8). Specifically, suppose we have dNx≤ξx−ux≤dˉNxd^x_N \le\xi^x - u^x \le\bar{d}^x_N. If ξx−ux≥0\xi^x - u^x \ge0, i.e., the DCM is located in front of the current footstep, we find the smallest possible number N′N' of maximum-length steps for which dN′xd^x_{N'} satisfies ξx−ux≤dˉN′x\xi^x - u^x \le\bar{d}^x_{N'}. Then, the corresponding coordinate of the virtual stopping point is xstop=ux+N′⋅lxx^{\mathrm{stop}} = u^x + N' \cdot l^x with uxu^x the current footstep location and lxl^x the maximum length of a step. The procedure is analogous for the case ξx−ux<0\xi^x - u^x < 0 with the difference that N′N' is the smallest number of steps for which dN′x≤ξx−ux\frac{d^{x}_{N'}} \leq\xi^{x} - u^{x} and xstop=ux−N′⋅lxx^{\mathrm{stop}} = u^{x-N'} \cdot l^{x}. The same procedure is applied in the YY-direction to determine the virtual stopping point coordinate ystopy^{\mathrm{stop}}, although the lateral case is more complex due to the asymmetry in foot placement.

Remark 2: The virtual stopping point pstopp^{\mathrm{stop}} certifies the existence of a safe stopping configuration within Si∩Si+1S_i \cap S_{i+1}; it does not necessarily require the robot to stop during transitions. In fact, as the robot approaches an intermediate goal, its state enters progressively lower-step capture regions, ultimately reaching the 1-step capture region. This ensures a transition to the next rectangle whenever sufficient free space is available for at least one maximum-length step, thereby preserving safety; otherwise, the robot stops at the intermediate goal, detecting that a collision with the boundary of the current rectangle SiS_i is imminent. Thus, the virtual stopping point functions as a feasibility certificate, effectively propagating recursive feasibility along the corridor.

A Sequential MPC Planner with Recursive Feasibility

We consider the ordered sequence of rectangles {S0,…,SM−1}\{S_0,\ldots,S_{M-1}\} computed from the corresponding sequence of collision-free rectangles {B0,…,BM−1}\{B_0,\ldots,B_{M-1}\} as in § 3-B. Assume that Si∩Si+1≠∅S_i \cap S_{i+1} \neq\emptyset for all i=0,…,M−2i=0,\ldots,M-2, and for each intersection Si∩Si+1S_i \cap S_{i+1} compute the corresponding center of the Chebyshev disc wi+1w_{i+1}, i=0,…,M−2i=0,\ldots,M-2, and let wMw_M denote the final destination. For generality, a desired velocity vi+1v_{i+1}, i=0,…,M−2i=0,\ldots,M-2, is assigned to each waypoint, with zero velocity at the destination, i.e., vM=0v_M=0. Thus, a sequence of triplets (Si,wi+1,vi+1)(S_i,w_{i+1},v_{i+1}), i=0,…,M−1i=0,\ldots,M-1, is obtained and used to define a corresponding sequence MPC(i)\mathrm{MPC}(i) of MPC programs to plan footsteps with recursive feasibility guarantees that drive the robot to the destination.

Specifically, MPC(i)\mathrm{MPC}(i) is formulated as in § 2-C, using the waypoint (wi+1,vi+1)(w_{i+1},v_{i+1}) to define the performance index. Given feedback from the COM state xinitx_{\mathrm{init}} and the stance foot location, the corresponding rectangle SiS_i is used to compute νinit\nu_{\mathrm{init}}. MPC(i)\mathrm{MPC}(i) is then solved to steer the LIP toward the next waypoint, keeping the evolution within SiS_i and enforcing the kinematic constraint (5). Composing the MPCs as

⋯⟶MPC(i)→{pkCOM,uk,pkstop}∈Si+1MPC(i+1)⟶⋯\cdots\longrightarrow\mathrm{MPC}(i) \xrightarrow{\{p_k^{\mathrm{COM}},u_k,p_k^{\mathrm{stop}}\}\in S_{i+1}} \mathrm{MPC}(i+1) \longrightarrow\cdots

for i=0,…,M−1i=0,\ldots,M-1, with the switching from MPC(i)\mathrm{MPC}(i) to MPC(i+1)\mathrm{MPC}(i+1) occurring when the COM state, footstep location, and virtual stopping point all lie within Si+1S_{i+1} (cf. § 3-B), results in a sequence of suggested footstep locations that drive the LIP to the final destination.

Owing to the capturability-aware construction of the safe corridors, the sequential MPC scheme described above offers recursive feasibility guarantees. To see this, assume that in the first call of MPC(0)\mathrm{MPC}(0), S0S_0 is non-empty and that the LIP’s initial footstep location u0u_0 and state x0x_0 result in a νinit\nu_{\mathrm{init}} viable-capture basin that contains x0x_0; νinit\nu_{\mathrm{init}} is computed based on S0S_0 as in § 2-C. Then, by Remark 1, MPC(0)\mathrm{MPC}(0) is recursively feasible. Now, S1S_1 is non-empty (by construction of the corridor, S0∩S1≠∅S_0 \cap S_1 \neq\emptyset) and the switching policy of § 3-B guarantees that, at the moment of switching, the LIP’s state lies within the νinit\nu_{\mathrm{init}} viable-capture basin, with νinit\nu_{\mathrm{init}} computed by its current state, footstep location and S1S_1. This follows from the fact that the conditions required to apply the policy ensure the existence of an evolution in S1S_1 that can bring the LIP to rest by eventually placing its footstep at the virtual stopping point. Hence, by Remark 1, MPC(1)\mathrm{MPC}(1) is recursively feasible. The result follows by propagating these arguments forward until all rectangles in {S0,…,SM−1}\{S_0,\ldots,S_{M-1}\} have been traversed.

Remark 3: If the desired waypoint velocity is zero, the virtual stopping point is guaranteed to enter the intersection as the LIP decelerates toward the waypoint. However, for nonzero velocities, the success of the switching policy depends on the interplay between the velocity and the intersection’s size. For nonzero velocities, the success of the switching policy depends on the interplay between the velocity and the intersection’s size. Gradually reducing the target velocity until the switching policy is activated practically eliminates this caveat.

Results

We evaluate the LIP-based sequential MPC’s performance in random scenarios, focusing on success rates and computational times. We then evaluate the method in MuJoCo simulations with the bipedal robot Digit navigating an office-like environment with door-opening constraints. In all results, the sequential MPC is implemented in CasADi [29] and solved using OSQP [30]. The suggested footsteps are realized via an Operational Space Control-based QP (OSC-QP). The objective of the OSC-QP is to track a set of weighted whole-body tasks, including Digit’s COM following the LIP, swing-foot trajectory tracking, torso orientation control, centroidal angular momentum minimization, and foot contact wrench optimization under friction cone constraints [4]. Note that alternative low-level controllers can also be used, provided they sufficiently accurately track the planned LIP dynamics and footsteps. The footstep MPC runs at a 15 Hz while the low-level OSC-QP operates at 400 Hz. The MPC update rate of 15 Hz is selected to ensure approximately five MPC iterations per Digit’s step, assuming a step duration of 300 ms, while also allowing sufficient time within each 1/4001/400 s control cycle for the OSC-QP to execute the commanded footstep before the subsequent MPC update. All computations were performed on an Intel PC with i7-9750H processor (2.60 GHz) and 16GB RAM.

Numerical Experiments and Performance Evaluation

To evaluate the efficiency of the proposed method, we generated 100 random environments, each containing 10 axis-aligned box obstacles covering 20% of a 50 m×50 m50\ \mathrm{m} \times50\ \mathrm{m} area, forming a sufficiently challenging set of environments. Across environments, the initial location is (2 m,2 m)(2\ \mathrm{m}, 2\ \mathrm{m}), the destination is (48 m,48 m)(48\ \mathrm{m}, 48\ \mathrm{m}), and both the initial and final velocities are zero. Waypoint velocities are set to Digit’s allowable speed of 1 m/s1\ \mathrm{m/s} for fast corridor traversal. For each environment, an AASC is generated as in § 3-A, after which both the proposed capturability-aware sequential MPC (§ 3-C) and the MPC scheme of [4] (hereafter, the prior method) are applied to the resulting SC.

Fig. 5(a) directly compares the two methods. The proposed method maintains high success rates (92% – 94%) across all prediction-horizon lengths, whereas the prior method achieves comparable performance only at longer horizons. Thus, the proposed scheme incurs lower computational cost, with runtimes on the order of μ\mus that scale predictably with the horizon length (Fig. 5(b)). More significantly, Fig. 5(a) highlights the distinct modes through which each method fails to transfer the robot to the destination. The proposed method exhibits two such modes, both inherently safe. The first arises when the capturability requirement results in inscribed rectangles that do not intersect, a condition that is detectable before execution. The second occurs in narrow or obstructed passages, causing the robot to resort to in-place walking when advancing may be dangerous. This is in stark contrast with the prior method, which may fail to suggest a footstep due to MPC infeasibility. Hence, unlike the prior method, the proposed method always exhibits graceful, safety-preserving behaviors.

Application to Office Spaces with Door Constraints

To show how the proposed method handles unexpected obstructions such as door constraints, consider the office-like environment shown in Figure 6, measuring 14m×7m14\mathrm{m} \times7\mathrm{m} with three rooms, two doors, and three static obstacles. Digit’s task is to move from the first to the third room while avoiding obstacles and respecting door availability. The planner is not informed of door-opening times in advance and assumes all doors are open at all times. We use a prediction horizon L=5L = 5 steps for the MPCs. Figure 6(a)–(Figure 6c) show representative snapshots of Digit navigating within the capturability-aware safe corridor illustrated in Figure 6(d). Of particular interest is the planner’s behavior with respect to door constraints highlighted in Figure 6(b)–Figure 6(c). When the next waypoint lies behind a closed door, the MPC guides the robot toward a capture state within the current rectangle. As shown in Figure 6(e), the robot autonomously slows down, switches to in-place walking and waits for the door to open. Once the door opens, the corridor extends through the doorway, becoming admissible and allowing the robot to continue toward the goal. Notably, the planner safely handles closed doors that temporarily render the destination unreachable, demonstrating robust navigation under exogenous, time-varying constraints while preserving capturability and recursive feasibility. Unlike the proposed method, the prior method lacks such guarantees and may therefore result in unsafe behaviors when encountering obstructions such as closed doors.

Figure 6. Digit navigating an office-like environment (rooms are labeled I, II and III) with two doors and three static obstacles. Start and goal points are in magenta and green; doors in red, obstacles in brown. The active SC rectangle is shown in blue and the COM trail in red. (b)-(c) Digit executing capturability-aware footsteps at closed doorways; upon door-opening, the planner resumes corridor execution. (d) Top view with capturability-aware SC, start, and goal. (e) COM speed: red boxes mark near-zero-velocity door-waiting phases; green dotted lines indicate entry into successive corridor intersections.

Conclusion

We presented a capturability-aware sequential MPC footstep planner for humanoid locomotion in cluttered environments. The central contribution is a novel capturability-aware switching policy that propagates recursive feasibility across sequentially intersecting rectangles, extending capturability guarantees along the entire safe corridor. A key feature is that the robot autonomously decides not to proceed when a closed door blocks the path, reverting to in-place walking to avoid collision and waiting until the passage is clear. Moreover, success rates are largely independent of the prediction horizon, thus substantially reducing MPC computational cost. The proposed framework lays a foundation for generating recursively feasible, collision-safe footstep plans for humanoids amid obstacles and under exogenous, time-varying constraints such as unknown door-opening times.

Acknowledgment

This project is funded by the European Union under Horizon Europe (grant No. 10135668 - HERON)

References

  1. [1]R. Deits and R. Tedrake, “Efficient mixed-integer planning for UAVs in cluttered environments,” in Proc. IEEE Int. Conf. Robot. Autom., 2015, pp. 42–49.DOI
  2. [2]S. Liu, M. Watterson, K. Mohta, K. Sun, S. Bhattacharya, C. J. Taylor, and V. Kumar, “Planning dynamically feasible trajectories for quadruped robots using safe flight corridors in 3-D complex environments,” IEEE Robot. Automat. Lett., vol. 2, no. 3, pp. 1688–1695, 2017.DOI
  3. [3]Q. Wang, Z. Wang, M. Wang, J. Ji, Z. Han, T. Wu, R. Jin, Y. Gao, C. Xu, and F. Gao, “Fast iterative region inflation for computing large 2-D/3-D convex regions of obstacle-free space,” IEEE Trans. Robot., vol. 41, pp. 3223–3243, 2025.arxiv.org/abs/2403.02977
  4. [4]K. S. Narkhede, A. M. Kulkarni, D. A. Thanki, and I. Poulakakis, “A sequential MPC approach to reactive planning for bipedal robots using safe corridors in highly cluttered environments,” IEEE Robot. Autom. Lett., vol. 7, no. 4, pp. 11 831–11 838, 2022.DOI
  5. [5]K. S. Narkhede, M. S. Motahar, S. Veer, and I. Poulakakis, “Reactive gait composition with stability: Dynamic walking amidst static and moving obstacles,” J. Dyn. Sys. Meas. Control, vol. 146, no. 5, 2024.arxiv.org/abs/2303.16165
  6. [6]R. Deits and T. Tedrake, “Computing large convex regions of obstacle-free space through semidefinite programming,” in Algorithmic Foundations of Robotics XI, H. L. Akin, N. M. Amato, V. Isler, and A. F. van der Stappen, Eds. Springer, 2015, pp. 109–124.DOI
  7. [7]F. Gao, W. Wu, Y. Lin, and S. Shen, “Online safe trajectory generation for quadrotors using fast marching method and bernstein basis polynomial,” in Proc. IEEE Int. Conf. Robot. Autom., 2018, pp. 344–351.DOI
  8. [8]F. Gao, L. Wang, B. Zhou, X. Zhou, J. Pan, and S. Shen, “Teach-Repeat-Replan: A complete and robust system for aggressive flight in complex environments,” IEEE Trans. Robot., vol. 36, no. 5, pp. 1526–1545, 2020.arxiv.org/abs/1907.00520
  9. [9]S. Katayama, M. Murooka, and Y. Tazaki, “Model predictive control of legged and humanoid robots: models and algorithms,” Adv. Robot., vol. 37, no. 5, pp. 298–315, 2023.DOI
  10. [10]S. Kajita, F. Kanehiro, K. Kaneko, K. Yokoi, and H. Hirukawa, “The 3D linear inverted pendulum mode: a simple modeling for a biped walking pattern generation,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., vol. 1, 2001, pp. 239–246.DOI
  11. [11]S. Faraji, S. Pouya, and A. Ijsppert, “Robust and agile 3D biped walking with steering capability using a footstep predictive approach,” in Proc. Robot. Sci. Syst., 2014.DOI
  12. [12]S. Xin, R. Orsolino, and N. Tsagarakis, “Online relative footstep optimization for legged robots dynamic walking using discrete-time model predictive control,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., 2019, pp. 513–520.
  13. [13]X. Xiong, J. Reher, and A. D. Ames, “Global position control on underactuated bipedal robots: Step-to-step dynamics approximation for step planning,” in Proc. IEEE Int. Conf. Robot. Autom., 2021, pp. 2825–2831.arxiv.org/abs/2011.06050
  14. [14]K. S. Narkhede, D. A. Thanki, A. M. Kulkarni, and I. Poulakakis, “Overtaking moving obstacles with Digit: Path following for bipedal robots via model predictive contouring control,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., 2023, pp. 8590–8596.arxiv.org/abs/2308.00119
  15. [15]F. Borrelli, A. Bemporad, and M. Morari, Predictive Control for Linear and Hybrid Systems. Cambridge University Press, 2017.
  16. [16]D. Q. Mayne, J. B. Rawlings, C. V. Rao, and P. O. M. Scokaert, “Survey constrained model predictive control: Stability and optimality,” Automatica, vol. 36, no. 6, pp. 789–814, 2000.DOI
  17. [17]T. Koolen, T. de Boer, J. Rebula, A. Goswami, and J. Pratt, “Capturability-based analysis and control of legged locomotion, part 1: Theory and application to three simple gait models,” Int. J. Robot. Res., vol. 31, no. 9, pp. 1094–1113, 2012.DOI
  18. [18]A. Sherikov, D. Dimitrov, and P.-B. Wieber, “Whole body motion controller with long-term balance constraints,” in Proc. IEEE-RAS Int. Conf. Humanoid Robots, 2014, pp. 444–450.DOI
  19. [19]M. Ciocca, P.-B. Wieber, and T. Fraichard, “Strong recursive feasibility in model predictive control of bipedal walking,” in Proc. IEEE-RAS Int. Conf. Humanoid Robots, 2017, pp. 730–735.
  20. [20]M. Krause, J. Englsberger, P.-B. Wieber, and C. Ott, “Stabilization of the capture point dynamics for bipedal walking based on model predictive control,” IFAC Proceedings, vol. 45, no. 22, pp. 165–171, 2012.DOI
  21. [21]N. Scianca, D. D. Simone, L. Lanari, and G. Oriolo, “MPC for humanoid gait generation: Stability and feasibility,” IEEE Trans. Robot., vol. 36, no. 8, pp. 1171–1188, 2020.DOI
  22. [22]F. M. Smaldone, N. Scianca, L. Lanari, and G. Oriolo, “Feasibility-driven step timing adaptation for robust mpc-based gait generation in humanoids,” IEEE Robot. Autom. Lett., vol. 6, no. 4, pp. 1582–1589, 2021.DOI
  23. [23]M. Khadiv, A. Herzog, S. A. A. Moosavian, and L. Righetti, “Walking control based on step timing adaptation,” IEEE Trans. Robot., vol. 36, no. 3, pp. 629–643, 2020.arxiv.org/abs/1704.01271
  24. [24]S. S. Kumbhar, A. M. Kulkarni, and I. Poulakakis, “Finite-step capturability and recursive feasibility for bipedal walking in constrained regions,” in Proc. IEEE Int. Conf. Robot. Autom., 2025, pp. 397–403.
  25. [25]J. Englsberger, C. Ott, and A. Albu-Schäffer, “Three-dimensional bipedal walking control based on divergent component of motion,” IEEE Trans. Robot., vol. 31, no. 2, pp. 355–368, 2015.DOI
  26. [26]K. Okada, M. Inaba, and H. Inoue, “Real-time and precise self collision detection system for humanoid robots,” in Proc. IEEE Int. Conf. Robot. Autom., 2005, pp. 1060–1065.DOI
  27. [27]G. Fang, Y. Tian, A. Weightman, and C. C. Wang, “Collision-aware fast simulation for soft robots by optimization-based geometric computing,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., 2022, pp. 12 614–12 621.arxiv.org/abs/2203.02054
  28. [28]S. M. LaValle, Planning Algorithms. Cambridge, UK: Cambridge University Press, 2006.
  29. [29]J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl, “CasADi-A software framework for nonlinear optimization and optimal control,” Math. Program. Comput., vol. 11, no. 1, pp. 1–36, 2019.
  30. [30]B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd, “OSQP: an operator splitting solver for quadratic programs,” Math. Program. Comput., vol. 12, no. 4, pp. 637–672, 2020.

Paper details

vlnc:W_z69pyhf8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents