PathCover: A Fast Convex Decomposition along a Path via Randomized Iterative Space Partitioning (RISP) on Point Clouds

Abhijeet M. Kulkarni; Guoquan Huang; Ioannis Poulakakis; Kunal S. Narkhede

REVIEW 3 major objections 5 minor 38 references

PathCover: A Fast Convex Decomposition along a Path via Randomized Iterative Space Partitioning (RISP) on Point Clouds

T0 review · 3 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read PathCover claims that randomized sampling can carve obstacle-free convex corridors from raw point clouds in expected linear time, and validates the claim with an order-of-magnitude speedup over optimization-based methods.

desk verdict RISP is a genuinely new randomized corridor-generation idea with credible conditional theory, but the expected-linear-time claim hangs on an unproven elimination condition whose empirical support is a fitted curve, not a verification. read the letter →

arxiv 2608.05586 v1 pith:FXHBF6MU submitted 2026-08-06 cs.RO

Kunal S. Narkhede , Abhijeet M. Kulkarni , Guoquan Huang , Ioannis Poulakakis This is my paper · ORCID

classification cs.RO

keywords safecorridorconvexpolytopedecompositionrandomizedalgorithmpointcloudmotionplanningLiDARnavigationmultiplicativedriftreal-timereplanning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

PathCover is a pipeline that turns raw point-cloud data into safe corridors, which are sequences of overlapping convex polytopes that enclose a robot's reference path and serve as constraints for trajectory optimization. The paper's central claim is that its core routine, Randomized Iterative Space Partitioning (RISP), constructs each obstacle-free polytope in expected linear time under a mild probabilistic condition on point elimination, and that the full PathCover algorithm terminates in finitely many steps and covers any obstacle-free path. If these claims hold, corridor generation no longer requires expensive iterative optimization and can keep pace with sensor-rate replanning on commodity hardware. The authors support the claims with benchmarks showing an order-of-magnitude reduction in computation time over standard methods, plus closed-loop simulations and hardware deployment on a quadrupedal robot.

What carries the argument

The engine is the randomized separating hyperplane: a sampled obstacle point $p$ defines a hyperplane perpendicular to $p - y_{\text{seed}}$ that passes near the sample, strictly separating the seed from $p$ and eliminating every obstacle point on the far side. The complexity guarantee rests on condition (5), a multiplicative-drift assumption that the remaining point count shrinks by a constant factor with fixed probability each round; the proof applies a multiplicative drift theorem to bound the expected iteration count by $O(\log n)$. Redundant half-spaces are pruned by mapping each facet to a dual point and taking a Quickhull convex hull of these dual points.

What would settle it

Run RISP on point clouds arranged on a circle or sphere centered at the seed, so that every separating hyperplane removes only the sampled point; if the measured runtime grows quadratically with the number of points and the per-step elimination fraction decays as $1/n$, condition (5) fails and the $O(n)$ guarantee does not apply to this configuration.

Watch

Extended reading notes

Core claim

The paper establishes that RISP repeatedly samples an obstacle point $p$ from the cloud, erects the separating hyperplane $h = \{x\,:\, a^{\top}x = b\}$ with $a = p - y_{\text{seed}}$ and $b = a^{\top}y_{\text{seed}} + (1-\alpha)\|a\|^2$, and discards every point on the side opposite the seed, which guarantees termination because the sampled point itself is always removed. Theorem 2 states that if condition (5) holds, namely that each hyperplane removes at least a fraction $\beta$ of the remaining points with probability at least $r$, then the expected runtime is $O(n)$ and the worst-case runtime is $O(n^2)$, with an $O(\log n)$ expected number of iterations via multiplicative drift. PathCover seeds successive RISP calls at the intersection of the current polytope with the path, producing overlapping polytopes, and Theorem 1 guarantees finite termination and coverage of the entire path.

Load-bearing premise

The linear-time guarantee rests on the unproved assumption that every random sample removes a constant fraction of the remaining obstacle points with probability at least $r$, a property the paper fits to measured runs rather than derives from any point-cloud model.

Editorial extensions

If this is right

Corridor generation can run at LiDAR frame rates on modest CPUs, enabling continuous replanning without conservative hover-and-stop behaviors.
The resulting corridor uses fewer polytopes than segment-per-path methods, directly reducing the number of constraints passed to the downstream trajectory optimizer.
Runtime is predictable with low variance, fitting fixed replanning windows in real-time control loops.
The method operates directly on raw point clouds, avoiding global map inflation and the growing latency of long-horizon occupancy maps.
The single geometric operation at the core makes the method easy to implement, debug, and trust in field deployment.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper, condition (5) could potentially be proven for locally coplanar LiDAR clouds if the angular distribution of obstacle points relative to the seed is shown to have bounded density, which would make the linear-time guarantee instance-independent rather than empirically fitted.
The same iterative partitioning idea might extend to non-convex free space by seeding along a medial axis or using a hierarchy of seeds, although the paper only treats the single-seed-per-polytope case.
RISP could serve as a fast conservative warm start for optimization-based inflaters such as IRIS, potentially combining linear-time initialization with larger final volumes.
The expected $O(\log n)$ iteration count hints at a streaming variant that incrementally updates the polytope as new LiDAR scans arrive, but such an online version is not explored in the paper.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short take: this is a real algorithmic idea, not a repackaging of IRIS/Decomp. RISP's random sampling with separating hyperplanes and elimination is new, and the drift-based analysis under condition (5) is a legitimate way to structure the complexity argument. The completeness proof (Theorem 1) is careful and convincing; the clearance-based progress bound is a nice touch. Reported speedups are large and the code link suggests reproducibility. The paper deserves referee time.

What it does well: the chaining of polytopes along a path with a bounded polytope count (vs. Decomp's one-per-segment) is practically sensible. The hardware demo on the Vision60 and the quadrotor simulation give the work credibility. The volume trade-off is disclosed honestly.

Soft spots, in order of severity. First, Theorem 2's O(n) expectation is conditional on (5), which is never proved for any point-cloud class. The paper calls it mild and leans on local coplanarity, but no concentration argument or distributional assumption is given. The empirical support in Section V-C does not close the gap: β* and r* are chosen by maximizing β·r̂(β) on the same runs used to plot E[N_k], so the envelope is a posterior fit, not a prediction. Pooling across steps hides late-iteration failures of the elimination condition. That said, the qualitative claim that structured LiDAR clouds shrink geometrically is plausible and the measured decay is real; what is missing is evidence that the drift rate stays bounded away from zero as n grows. Second, Table I's benchmark omits Galaxy despite the paper listing it as a baseline; the text says 'four state of the art methods' for 3D but Galaxy is 2D-only, so this is minor but should be cleaned up. Third, Theorem 1's statement omits the max_iter qualification: the proof bounds J by Jmax, but Algorithm 1 breaks at max_iter, so the coverage guarantee holds only when max_iter ≥ Jmax. The receding-horizon remark softens this, but the theorem as stated is imprecise. Fourth, the 'strictly separated' claim for the final polytope relies on the convexity argument referencing Boyd & Vandenberghe; that is fine.

The paper is honest about its conservatism and about the conditional nature of the theorem. The central mechanism is sound; the gap is in verifying condition (5) for realistic inputs, not in the conditional logic. Who is this for: robotics practitioners who need fast, predictable corridor generation at sensor rates, and theorists who want a clean randomized-geometry result. I'd send it to a serious robotics journal or conference; the main revision request should be to either prove (5) for a structured point-cloud model or reframe the empirical section as demonstrating a plausible regime rather than validating the theorem.

Referee Report

3 major / 5 minor

Summary. PathCover is a corridor-generation framework built on RISP, a randomized algorithm that, given a seed point and an obstacle point cloud, iteratively samples a point, constructs a separating hyperplane, discards points on the far side, and repeats until the cloud is exhausted. The paper claims that RISP runs in expected O(n) time under a probabilistic elimination condition (5), with an O(n^2) worst case, and that PathCover (Algorithm 1) builds a finite sequence of overlapping, obstacle-free polytopes covering any collision-free reference path (Theorem 1). The theoretical part also gives a drift-based proof of O(log n) expected iterations and an O((J+L)n) expected-time bound for the full corridor computation (Theorem 3). Empirical sections benchmark PathCover against Decomp, FIRI, CIRI, IRIS, and Galaxy, and validate the pipeline in a Gazebo quadrotor simulation and on a physical Ghost Robotics Vision60 quadruped. The central practical claims are order-of-magnitude speedups over optimization-based baselines and the ability to generate corridors at sensor rates.

Significance. If the expected-linear-time claim is supported by a verifiable condition, RISP/PathCover would be a meaningful practical contribution: corridor generation at LiDAR rates on commodity hardware is directly relevant to real-time MPC and trajectory optimization. The paper has real strengths: the completeness argument in Appendix A is carefully structured with explicit assumptions (Assumptions 1–2), the drift proof in Appendix B is rigorous once condition (5) is granted, and the hardware validation on a quadruped is a nontrivial demonstration. The comparisons use public baseline implementations and report timing, volume, and polytope-count statistics, which is useful evidence for the speed advantage. The main weakness is that the expected O(n) guarantee rests entirely on condition (5), which is not proved for any class of point clouds and whose empirical support in Section V-C is fitted on the same data used for the display; the claim of 'comparable corridor volumes' in the abstract is also contradicted by the paper's own tables.

major comments (3)

[III-B, Theorem 2, condition (5)] The expected O(n) complexity of RISP is entirely dependent on condition (5), which asserts that, for all iterations m before termination, a uniformly sampled point removes at least a β fraction of the remaining cloud with probability at least r. This condition is never proved for any distribution or geometric class of point clouds; the text offers only the intuition that LiDAR data are locally coplanar and states that 'both β and r can be bounded away from zero' without a supporting argument. As written, Theorem 2 is an implication from an unverified premise, and the only unconditional complexity bound is the O(n^2) worst case. This is load-bearing because the abstract and introduction present expected linear time as a central contribution.
[V-C] The empirical 'support' for condition (5) is circular. The authors compute β* = argmax β·r̂(β) and r̂* = r̂(β*) on the very same RISP runs that are then averaged to plot E[N_k], and they compare those curves against the fitted envelope n(1−β*r̂*)^k. Such a posterior fit cannot validate the per-iteration, per-history conditional probability in (5); pooling over all steps and runs can mask late iterations where elimination fractions are small. Moreover, no evidence is given that the fitted product β*r̂* remains bounded away from zero as n grows, which is necessary for a useful O(n) expectation with a constant independent of n. The section should be rewritten as a proper predictive test (e.g., train/test split or per-iteration conditional estimates with confidence intervals), and the text should distinguish between 'consistent with' and 'confirms' the condition.
[Abstract and Section IV-A, Table I] The abstract and Section IV-A claim that PathCover achieves an order-of-magnitude speedup while 'maintaining comparable corridor volumes,' but the paper's own measurements contradict this. In Table I, PathCover per-polytope volumes are roughly 30–50% lower than CIRI and Decomp (e.g., 338.30 vs 441.81 m^3 in sparse, 140.74 vs 195.98 m^3 in medium, 41.79 vs 59.06 m^3 in dense) and far below FIRI; in Table II the 3D volume ratio relative to IRIS is only 32–44%. The volume reduction is acknowledged in the Note to Practitioners but the abstract and contribution list do not qualify it. The authors should either replace 'comparable' with a quantitative statement of the speed–volume trade-off or adjust the claim.

minor comments (5)

[Table II] In the 3-D Volume ratio block for FIRI, the sparse-column entries '81.93 27.87 27.87' appear to have a typo: the max value is identical to the standard deviation and seems implausible; the authors should verify and correct this entry.
[Note to Practitioners] The repository link contains an embedded space and a line break: 'https://github.com/kunalnk123690/PathCov er .git' should be the single valid URL 'https://github.com/kunalnk123690/PathCover.git'.
[V-C] The notation 'β*r̂*' in the iteration bound (1+ln n)/(β*r̂*) is confusing; since β* and r̂* are both fitted, the product should be written as a single symbol (e.g., γ = β* r̂*) to avoid the impression of a star operator.
[Figure 5] The caption refers to 'vertical dashed lines' for termination but does not state which curves correspond to which dataset; please add explicit labels to the figure or caption.
[Conclusion] The conclusion presents the O(n) behavior as established ('we established the expected linear-time complexity of RISP under a probabilistic point-elimination condition') but does not flag that condition (5) was neither proved nor validated without circularity; a sentence acknowledging this limitation would improve accuracy.

Circularity Check

2 steps flagged · score 6.0 of 10

The empirical support for Theorem 2 fits β∗ and r̂∗ on the very runs that are then compared with the fitted envelope and used to compute 'predicted' iteration bounds, so the confirmation is a post-hoc fit rather than an independent test; the conditional theorem itself is not circular.

fitted input called prediction [Section V-C, paragraph defining β∗ and r̂∗, before Eq. (20) comparison]
"we define the empirical β elimination probability as r̂(β) = Pr{ηk ≥ β}, estimated across all steps and runs in each dataset. ... We estimate the tightest such rate by computing β∗ = arg max β∈(0,1) β·r̂(β) and r̂∗ = r̂(β∗) over a uniform grid of β. This directly identifies the pair (β∗, r̂∗) consistent with Theorem 2 that yields the fastest predicted convergence. The empirical mean E[Nk] is then computed by averaging the sequences of Nk across all runs and compared against the geometric envelope n(1−β∗r̂∗)^k from (20) ..."

The same measured sequences {Nk} are used both to estimate r̂(β), and hence to select the best-fitting β∗ and r̂∗, and to compute the empirical E[Nk] that is then plotted against the envelope n(1−β∗r̂∗)^k. Choosing β on the same data to maximize β·r̂ makes the envelope a fitted curve, not a prediction; agreement with the data is an artifact of the fitting procedure. Moreover, condition (5) is a per-step conditional bound over every reachable Pm, whereas r̂(β) is a pooled frequency over all steps and runs, so even a high pooled frequency does not verify the uniform conditional drift required by Theorem 2.
fitted input called prediction [Section V-C, final paragraph comparing predicted and observed termination times]
"The predicted iteration bounds (1 + ln n)/(β∗r̂∗) evaluate to 208 and 145 iterations for the quadrotor and quadruped clouds, respectively, whereas the observed mean termination times are 62 and 43 iterations, comfortably inside those bounds, as the vertical dashed lines in Fig. 5 indicate."

The 'predicted' iteration bounds are computed by plugging the fitted constants β∗ and r̂∗ into the drift-theoretic bound, where β∗ was selected on the same runs by maximizing β·r̂(β). The observed termination times are therefore compared against a bound whose parameters were optimized for those same runs. This is a post-hoc fit, not an out-of-sample prediction, and it does not provide independent evidence that condition (5) holds with fixed constants for arbitrary point clouds.

full rationale

The mathematical derivation chain in Theorems 1 and 2 is not circular by itself. Theorem 1 is proved from geometric clearance arguments and the RISP separation construction, and its proof is self-contained. Theorem 2 is explicitly conditional: it assumes condition (5), the existence of constants β and r with per-step elimination probability at least r, and then derives O(n) expected time via multiplicative drift. That conditional implication is valid and does not reduce to its inputs. The circularity is confined to Section V-C, where the paper attempts to validate condition (5) empirically. There, the empirical elimination probability r̂(β) is estimated from all steps and runs of the same RISP executions that are later used to compute the mean curve E[Nk] and the observed termination times. The constants β∗ and r̂∗ are then chosen from that same data by maximizing β·r̂(β), and the geometric envelope and iteration bounds are drawn using these fitted values. Agreement between the data and the fitted envelope is therefore a curve-fitting artifact, not independent confirmation. In addition, the pooled estimator r̂(β) averages over steps and runs, whereas condition (5) requires a uniform conditional bound for every reachable remaining set Pm, so the empirical procedure cannot certify the theorem's hypothesis even as a statistical statement. The paper does not prove condition (5) for any class of point clouds; it calls the condition mild and appeals to locally coplanar LiDAR structure. That lack of proof is a correctness risk rather than a circularity, and for adversarial configurations satisfying only 'each sample removes itself' the algorithm degrades to O(n^2), as the paper itself notes. There is no load-bearing self-citation: reference [8] is a prior paper by the authors but is used only to motivate safe-corridor abstractions, not to justify the new complexity results. Overall, the central conditional theorem has independent content, but the paper's empirical support for its key probabilistic premise is a fitted input presented as prediction, warranting a partial circularity score of 6.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claims rest on two standard domain assumptions (polytope workspace, interior-clear path) and on condition (5), which is not proven and is fitted to data. α and max_iter are user-set parameters; β* and r* are fitted constants.

free parameters (3)

α = not fitted, user-selected in (0,1)
Controls the placement of the separating hyperplane between the seed and the sampled point; affects polytope volume and the progress lower bound δmin in Lemma 2.
β* and r* = β*·r* = 0.063 (quadrotor), 0.087 (quadruped)
In Section V-C, β* = arg max β·r̂(β) and r̂* are estimated from the observed remaining-point sequences, then used to draw the geometric envelope and predict iteration counts. These are fitted from the same data used for validation.
max_iter = 6 (quadrotor), 1 (quadruped)
Caps the corridor horizon in receding-horizon use; not part of the completeness theorem.

assumptions (4)

domain assumption Assumption 1: workspace W is a polytope and obstacle set O is closed in W.
Used in Lemma 1 to ensure the intersection with W is a bounded polytope and to define the clearance εΓ in Lemma 2.
domain assumption Assumption 2: line segments between consecutive waypoints lie entirely in the interior of the free space F.
Ensures the path clearance εΓ is strictly positive, so every RISP polytope centered on the path contains a ball of radius (1-α)εΓ and PathCover terminates in finite steps.
ad hoc to paper Condition (5): there exist constants β in (0,1) and r in (0,1] such that Pr{N_{m+1} <= (1-β)N_m | P_m} >= r for all iterations m before exhaustion.
This is the load-bearing premise for Theorem 2's expected O(n) rate. It is never proved for any point-cloud class; Section V-C only fits β* and r* to observed data.
standard math Quickhull computes the convex hull of τ dual points in expected O(τ log τ) time.
Used in the proof of Theorem 2 for redundant-constraint removal; standard randomized incremental convex hull result under random input assumptions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of PathCover: A Fast Convex Decomposition along a Path via Randomized Iterative Space Partitioning (RISP) on Point Clouds." pith.science (2026). https://pith.science/paper/FXHBF6MU

@misc{pith2026260805586,
  author       = {Pith},
  title        = {Pith review of: PathCover: A Fast Convex Decomposition along a Path via Randomized Iterative Space Partitioning (RISP) on Point Clouds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FXHBF6MU}},
  note         = {Machine review of arXiv:2608.05586}
}

read the original abstract

Autonomous robot navigation requires the rapid generation of obstacle-free regions for trajectory planning. However, existing corridor generators struggle to meet real-time, sensor-rate computational constraints. To resolve this bottleneck, we introduce PathCover, a framework driven by RISP; a novel randomized algorithm that constructs convex polytopes directly from raw point cloud data in expected linear time under a mild probabilistic elimination condition. PathCover generates sequences of overlapping, obstacle-free polytopes that safely constrain downstream MPC and trajectory optimization. We mathematically guarantee that the algorithm terminates in finite steps while ensuring continuous progress along any obstacle-free reference path. Extensive benchmarks on synthetic and real-world LiDAR datasets demonstrate an order-of-magnitude speedup over state-of-the-art methods while maintaining comparable corridor volumes. The complete pipeline is validated via high-fidelity quadrotor simulations and physical deployment on a quadrupedal robot navigating constrained environments using live LiDAR perception.

Figures

Figures reproduced from arXiv: 2608.05586 by the authors.

**Figure 1.** Overview of PathCover: from a raw point cloud and a reference path (red) connecting the robot to the goal (green), the method builds overlapping convex polytopes whose union forms a corridor covering the path. A UTONOMOUS navigation through cluttered, unstructured environments is a fundamental requirement for modern automation. The same need recurs, in nearly identical form, in autonomous urban driving [1], legged… view at source ↗

**Figure 2.** Incremental application of RISP along a path to generate corridor using Algorithm 1. The path (blue) is Π = {y0, y1, y2}. The algorithm begins with y0 as seed to generate the first polytope Hnew (a). It then computes the intersection point yin between the polytope and the line segment connecting y1 and y0, uses this point as a seed, and generates another polytope (b–c). The algorithm continues until the goal is insi… view at source ↗

**Figure 3.** Corridor generation (blue) along a path (red) in an [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Receding-horizon corridor planning. (a) Quadrot [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

**Figure 5.** Figure 5: Empirical support for Theorem 2. For the Gazebo qua [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 34 canonical work pages

[1]

Real-time motion planning with applications to autonomou s urban driving,

Y . Kuwata, J. Teo, G. Fiore, S. Karaman, E. Frazzoli, and J . P . How, “Real-time motion planning with applications to autonomou s urban driving,” IEEE Trans. Control Syst. Technol. , vol. 17, no. 5, pp. 1105– 1118, 2009. 13

work page 2009
[2]

GaitMesh: Co ntroller-aware navigation meshes for long-range legged locomotion planni ng in multi- layered environments,

M. Brand˜ ao, O. B. Aladag, and I. Havoutis, “GaitMesh: Co ntroller-aware navigation meshes for long-range legged locomotion planni ng in multi- layered environments,” IEEE Robot. Automat. Lett. , vol. 5, no. 2, pp. 3596–3603, 2020

work page 2020
[3]

An integrated framew ork for cooperative aerial manipulators in unknown environments,

H. Lee, H. Kim, W. Kim, and H. J. Kim, “An integrated framew ork for cooperative aerial manipulators in unknown environments,” IEEE Robot. Automat. Lett. , vol. 3, no. 3, pp. 2307–2314, 2018

work page 2018
[4]

Universal trajectory optimization framework for differential drive robot class,

M. Zhang, N. Chen, H. Wang, J. Qiu, Z. Han, Q. Ren, C. Xu, F. G ao, and Y . Cao, “Universal trajectory optimization framework for differential drive robot class,” IEEE Trans. Autom. Sci. Eng. , vol. 22, pp. 13 030– 13 045, 2025

work page 2025
[5]

DLSC: Distributed multi-agent trajectory planning in maze-like dynamic environments usi ng linear safe corridor,

J. Park, Y . Lee, I. Jang, and H. J. Kim, “DLSC: Distributed multi-agent trajectory planning in maze-like dynamic environments usi ng linear safe corridor,” IEEE Trans. Robot. , vol. 39, no. 5, pp. 3739–3758, 2023

work page 2023
[6]

RAST: Risk-aware spatio-temporal safety corridors for ma v navigation in dynamic uncertain environments,

G. Chen, S. Wu, M. Shi, W. Dong, H. Zhu, and J. Alonso-Mora, “RAST: Risk-aware spatio-temporal safety corridors for ma v navigation in dynamic uncertain environments,” IEEE Robot. Automat. Lett. , vol. 8, no. 2, pp. 808–815, 2023

work page 2023
[7]

FA STER: Fast and safe trajectory planner for navigation in unknown envir onments,

J. Tordesillas, B. T. Lopez, M. Everett, and J. P . How, “FA STER: Fast and safe trajectory planner for navigation in unknown envir onments,” IEEE Trans. Robot. , vol. 38, no. 2, pp. 922–938, 2022

work page 2022
[8]

A sequential MPC approach to reactive planning for bipedal ro bots using safe corridors in highly cluttered environments,

K. S. Narkhede, A. M. Kulkarni, D. A. Thanki, and I. Poulak akis, “A sequential MPC approach to reactive planning for bipedal ro bots using safe corridors in highly cluttered environments,” IEEE Robot. Automat. Lett., vol. 7, no. 4, pp. 11 831–11 838, 2022

work page 2022

Show all 38 references

[9]

Fast iterative region inﬂation for comput ing large 2-D/3-D convex regions of obstacle-free space,

Q. Wang, Z. Wang, M. Wang, J. Ji, Z. Han, T. Wu, R. Jin, Y . Gao , C. Xu, and F. Gao, “Fast iterative region inﬂation for comput ing large 2-D/3-D convex regions of obstacle-free space,” IEEE Trans. Robot. , vol. 41, pp. 3223–3243, 2025

2025
[10]

Efﬁcient mixed-integer plann ing for UA Vs in cluttered environments,

R. Deits and R. Tedrake, “Efﬁcient mixed-integer plann ing for UA Vs in cluttered environments,” in Proc. IEEE Int. Conf. Robot. Autom. , 2015, pp. 42–49

2015
[11]

Planning dynamically feasible trajectories for quadrotors using safe ﬂight corridors in 3-D complex environments,

S. Liu, M. Watterson, K. Mohta, K. Sun, S. Bhattacharya, C. J. Taylor, and V . Kumar, “Planning dynamically feasible trajectories for quadrotors using safe ﬂight corridors in 3-D complex environments,” IEEE Robot. Automat. Lett. , vol. 2, no. 3, pp. 1688–1695, 2017

2017
[12]

Online dis tributed trajectory planning for quadrotor swarm with feasibility g uarantee using linear safe corridor,

J. Park, D. Kim, G. C. Kim, D. Oh, and H. J. Kim, “Online dis tributed trajectory planning for quadrotor swarm with feasibility g uarantee using linear safe corridor,” IEEE Robot. Automat. Lett. , vol. 7, no. 2, pp. 4869– 4876, 2022

2022
[13]

Bubble planner: Planning high-speed smooth quadrotor tra jectories using receding corridors,

Y . Ren, F. Zhu, W. Liu, Z. Wang, Y . Lin, F. Gao, and F. Zhang , “Bubble planner: Planning high-speed smooth quadrotor tra jectories using receding corridors,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., 2022, pp. 6332–6339

2022
[14]

Computing large convex region s of obstacle- free space through semideﬁnite programming,

R. Deits and R. Tedrake, “Computing large convex region s of obstacle- free space through semideﬁnite programming,” in Algorithmic F ounda- tions of Robotics XI , H. L. Akin, N. M. Amato, V . Isler, and A. F. van der Stappen, Eds. Springer, 2015, pp. 109–124

2015
[15]

Growing convex collision- free regions in conﬁguration space using nonlinear programming,

M. Petersen and R. Tedrake, “Growing convex collision- free regions in conﬁguration space using nonlinear programming,” arXiv:2303.14737, 2023

2023 arXiv
[16]

Ce rtiﬁed polyhedral decompositions of collision-free conﬁguratio n space,

H. Dai, A. Amice, P . Werner, A. Zhang, and R. Tedrake, “Ce rtiﬁed polyhedral decompositions of collision-free conﬁguratio n space,” Int. J. Robot. Res. , vol. 43, no. 9, pp. 1322–1341, 2024

2024
[17]

Faster algorithms for growing collision-free c onvex poly- topes in robot conﬁguration space,

P . Werner, T. Cohn, R. H. Jiang, T. Seyde, M. Simchowitz, R. Tedrake, and D. Rus, “Faster algorithms for growing collision-free c onvex poly- topes in robot conﬁguration space,” arXiv:2410.12649, 2024

2024 arXiv
[18]

Safety-assured high-speed navigation for mavs,

Y . Ren, F. Zhu, G. Lu, Y . Cai, L. Yin, F. Kong, J. Lin, N. Che n, and F. Zhang, “Safety-assured high-speed navigation for mavs, ” Sci. Robot. , vol. 10, no. 98, p. eado6187, 2025

2025
[19]

Towar ds optimizing a convex cover of collision-free space for trajectory gener ation,

Y . Wu, I. Spasojevic, P . Chaudhari, and V . Kumar, “Towar ds optimizing a convex cover of collision-free space for trajectory gener ation,” IEEE Robot. Automat. Lett. , vol. 10, no. 5, pp. 4762–4769, 2025

2025
[20]

An algorithm for generating convex obstacle -free regions based on stereographic projection,

S. Savin, “An algorithm for generating convex obstacle -free regions based on stereographic projection,” in Proc. Int. Siberian Conf. Control Commun., 2017, pp. 1–6

2017
[21]

Gener ating large convex polytopes directly on point clouds,

X. Zhong, Y . Wu, D. Wang, Q. Wang, C. Xu, and F. Gao, “Gener ating large convex polytopes directly on point clouds,” arXiv:2010.08744, 2020

2010 arXiv
[22]

Star- convex constrained optimization for visibility planning w ith application to aerial inspection,

T. Liu, Q. Wang, X. Zhong, Z. Wang, C. Xu, F. Zhang, and F. G ao, “Star- convex constrained optimization for visibility planning w ith application to aerial inspection,” in Proc. IEEE Int. Conf. Robot. Autom. , 2022, pp. 7861–7867

2022
[23]

The quickh ull algorithm for convex hulls,

C. B. Barber, D. P . Dobkin, and H. Huhdanpaa, “The quickh ull algorithm for convex hulls,” ACM Trans. Math. Softw. , vol. 22, no. 4, p. 469–483, 1996

1996
[24]

Optimal paths for polygonal robots in SE(2),

M. Kennedy, III, D. Thakur, M. Ani Hsieh, S. Bhattachary a, and V . Kumar, “Optimal paths for polygonal robots in SE(2),” J. Mechanisms Robot., vol. 10, no. 2, p. 021005, 2018

2018
[25]

Tea ch-Repeat- Replan: A complete and robust system for aggressive ﬂight in complex environments,

F. Gao, L. Wang, B. Zhou, X. Zhou, J. Pan, and S. Shen, “Tea ch-Repeat- Replan: A complete and robust system for aggressive ﬂight in complex environments,” IEEE Trans. Robot., vol. 36, no. 5, pp. 1526–1545, 2020

2020
[26]

V oxel-grid based convex dec omposition of 3D space for safe corridor generation,

C. Toumieh and A. Lambert, “V oxel-grid based convex dec omposition of 3D space for safe corridor generation,” J. Intell. Robot. Syst. , vol. 105, no. 4, p. 87, 2022

2022
[27]

OctoMap: an efﬁcient probabilistic 3D mapping framework b ased on octrees,

A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss, and W . Burgard, “OctoMap: an efﬁcient probabilistic 3D mapping framework b ased on octrees,” Auton. Robots , vol. 34, no. 3, pp. 189–206, 2013

2013
[28]

Online safe trajector y generation for quadrotors using fast marching method and bernstein bas is polyno- mial,

F. Gao, W. Wu, Y . Lin, and S. Shen, “Online safe trajector y generation for quadrotors using fast marching method and bernstein bas is polyno- mial,” in Proc. IEEE Int. Conf. Robot. Autom. , 2018, pp. 344–351

2018
[29]

GPU accelerated voxel grid g eneration for fast MA V exploration,

C. Toumieh and A. Lambert, “GPU accelerated voxel grid g eneration for fast MA V exploration,” arXiv:2112.13169, 2021

2021 arXiv
[30]

S. M. LaV alle, Planning Algorithms . Cambridge, UK: Cambridge University Press, 2006

2006
[31]

Online graph pruning for pa thﬁnding on grid maps,

D. Harabor and A. Grastien, “Online graph pruning for pa thﬁnding on grid maps,” in Proc. AAAI Conf. Artif. Intell. AAAI Press, 2011, p. 1114–1119

2011
[32]

Minimum snap trajectory gen eration and control for quadrotors,

D. Mellinger and V . Kumar, “Minimum snap trajectory gen eration and control for quadrotors,” in Proc. IEEE Int. Conf. Robot. Autom. , 2011, pp. 2520–2525

2011
[33]

Geometric tracki ng control of a quadrotor uav on SE(3),

T. Lee, M. Leok, and N. H. McClamroch, “Geometric tracki ng control of a quadrotor uav on SE(3),” in Proc. IEEE Conf. Decis. Control , 2010, pp. 5420–5425

2010
[34]

CasADi-A software framework for nonlinear optimization a nd optimal control,

J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, an d M. Diehl, “CasADi-A software framework for nonlinear optimization a nd optimal control,” Math. Program. Comput. , vol. 11, no. 1, pp. 1–36, 2019

2019
[35]

OSQP: an operator splitting solver for quadratic programs,

B. Stellato, G. Banjac, P . Goulart, A. Bemporad, and S. B oyd, “OSQP: an operator splitting solver for quadratic programs,” Math. Program. Comput., vol. 12, no. 4, pp. 637–672, 2020

2020
[36]

FA TROP: A fast constrained optimal control problem solver for robot t rajectory optimization and control,

L. V anroye, A. Sathya, J. De Schutter, and W. Decr´ e, “FA TROP: A fast constrained optimal control problem solver for robot t rajectory optimization and control,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., 2023, pp. 10 036–10 043

2023
[37]

Boyd and L

S. Boyd and L. V andenberghe, Convex Optimization. Cambridge, UK: Cambridge University Press, 2004

2004
[38]

Drift analysis a nd linear functions revisited,

B. Doerr, D. Johannsen, and C. Winzen, “Drift analysis a nd linear functions revisited,” in Proc. IEEE Congr . Evol. Comput. , 2010, pp. 1–8

2010

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

Real-time motion planning with applications to autonomou s urban driving,

Y . Kuwata, J. Teo, G. Fiore, S. Karaman, E. Frazzoli, and J . P . How, “Real-time motion planning with applications to autonomou s urban driving,” IEEE Trans. Control Syst. Technol. , vol. 17, no. 5, pp. 1105– 1118, 2009. 13

work page 2009

[2] [2]

GaitMesh: Co ntroller-aware navigation meshes for long-range legged locomotion planni ng in multi- layered environments,

M. Brand˜ ao, O. B. Aladag, and I. Havoutis, “GaitMesh: Co ntroller-aware navigation meshes for long-range legged locomotion planni ng in multi- layered environments,” IEEE Robot. Automat. Lett. , vol. 5, no. 2, pp. 3596–3603, 2020

work page 2020

[3] [3]

An integrated framew ork for cooperative aerial manipulators in unknown environments,

H. Lee, H. Kim, W. Kim, and H. J. Kim, “An integrated framew ork for cooperative aerial manipulators in unknown environments,” IEEE Robot. Automat. Lett. , vol. 3, no. 3, pp. 2307–2314, 2018

work page 2018

[4] [4]

Universal trajectory optimization framework for differential drive robot class,

M. Zhang, N. Chen, H. Wang, J. Qiu, Z. Han, Q. Ren, C. Xu, F. G ao, and Y . Cao, “Universal trajectory optimization framework for differential drive robot class,” IEEE Trans. Autom. Sci. Eng. , vol. 22, pp. 13 030– 13 045, 2025

work page 2025

[5] [5]

DLSC: Distributed multi-agent trajectory planning in maze-like dynamic environments usi ng linear safe corridor,

J. Park, Y . Lee, I. Jang, and H. J. Kim, “DLSC: Distributed multi-agent trajectory planning in maze-like dynamic environments usi ng linear safe corridor,” IEEE Trans. Robot. , vol. 39, no. 5, pp. 3739–3758, 2023

work page 2023

[6] [6]

RAST: Risk-aware spatio-temporal safety corridors for ma v navigation in dynamic uncertain environments,

G. Chen, S. Wu, M. Shi, W. Dong, H. Zhu, and J. Alonso-Mora, “RAST: Risk-aware spatio-temporal safety corridors for ma v navigation in dynamic uncertain environments,” IEEE Robot. Automat. Lett. , vol. 8, no. 2, pp. 808–815, 2023

work page 2023

[7] [7]

FA STER: Fast and safe trajectory planner for navigation in unknown envir onments,

J. Tordesillas, B. T. Lopez, M. Everett, and J. P . How, “FA STER: Fast and safe trajectory planner for navigation in unknown envir onments,” IEEE Trans. Robot. , vol. 38, no. 2, pp. 922–938, 2022

work page 2022

[8] [8]

A sequential MPC approach to reactive planning for bipedal ro bots using safe corridors in highly cluttered environments,

K. S. Narkhede, A. M. Kulkarni, D. A. Thanki, and I. Poulak akis, “A sequential MPC approach to reactive planning for bipedal ro bots using safe corridors in highly cluttered environments,” IEEE Robot. Automat. Lett., vol. 7, no. 4, pp. 11 831–11 838, 2022

work page 2022