Pith. sign in

REVIEW 4 major objections 5 minor 19 references

Online Motion Planning Over Multiple Homotopy Classes with Gaussian Process Inference

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

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

Pith's one-line read The paper claims that a robot planner can avoid dynamic obstacles by keeping several interconnected route options in one factor graph and reoptimizing them at every step, deliberately switching between obstacle-bypassing route classes…

desk verdict A clearly-described incremental extension of GPMP-GRAPH; the online prune-and-reoptimize loop is plausible, but the paper never measures whether its claimed mechanism—retaining multiple homotopy classes—actually survives pruning. read the letter →

arxiv 1908.00641 v1 pith:3BFYLXDR submitted 2019-08-01 cs.RO

Keshav Kolur , Sahit Chintalapudi , Byron Boots , Mustafa Mukadam This is my paper · ORCID
classification cs.RO
keywords onlinemotionplanninghomotopyclassesGaussianprocessinferencefactorgraphstrajectoryoptimizationdynamicenvironmentsreplanningswitching
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

This paper tries to establish that an online planner can improve performance in dynamic environments by keeping multiple obstacle-bypassing routes in a single factor graph and reoptimizing them as the world changes. Instead of committing to one trajectory, the proposed POSH algorithm re-plans over the whole interconnected graph at every time step, prunes states it can no longer reach in time, and extracts the current lowest-cost path with a graph search. The claim is that this prune-and-reoptimize loop lets the robot switch between homotopy classes mid-execution, escaping local minima that trap single-trajectory optimizers. In simulated 2D environments with noisy measurements and execution, this leads to higher success and lower collision intensity than the batch multi-chain planner and the single-chain optimizer it is compared with. If true, the value is a practical recipe for keeping future route options alive without the cost of full replanning from scratch.

What carries the argument

The machinery is a factor graph of interconnected Gaussian-process trajectory chains: a bipartite graph whose variable nodes are trajectory waypoints and whose factor nodes enforce smoothness and collision avoidance. Optimizing the whole graph with a nonlinear least-squares routine evaluates many route candidates at once; a complete graph search (A*) then reads off the lowest-cost feasible path; and a depth-first search prunes support states that become unreachable in time before the next optimization. Warm-starting the optimizer from the previous solution keeps each step cheap. The interconnection structure is what lets distinct homotopy classes coexist in one optimization, and the pruning is what makes the online loop tractable.

What would settle it

Count the distinct h-signatures (route-class identifiers) among paths in the pruned graph at each time step. If a reported homotopy switch happens while the pruned graph contains only one h-signature, the switching mechanism is not what the paper says it is.

Watch

Extended reading notes

Core claim

The central discovery is that homotopy switching can be made an online, deliberate operation rather than a passive response to obstacle motion. POSH maintains multiple interconnected trajectories as a factor graph, optimizes the whole graph each time step, selects the best path with A*, then prunes only states that are unreachable in time. Because several distinct homotopy classes survive in the pruned graph, the next optimization can return a path that cannot be deformed into the current one without hitting an obstacle. The paper reports that in a dynamic narrow passageway this mechanism yields a 100% success rate over 10 Monte-Carlo runs (versus 10% for both baselines), and in a random dynamic forest it improves success rate from roughly 12% and 8% to about 29% while reducing collision intensity.

Load-bearing premise

The pruned and reoptimized graph must keep at least two genuinely different obstacle-bypassing route classes; the paper itself acknowledges that different trajectories can collapse into the same route class, and if that happens the method reduces to single-route planning and its claimed advantage disappears.

Editorial extensions

If this is right

  • In environments where obstacles move and block the current route, a robot using POSH can switch to a different homotopy class before the current path becomes infeasible, rather than being pushed into a corner by reoptimizing a single trajectory.
  • On the dynamic narrow passage benchmark, POSH achieves a 100% success rate with an average of 1–2 homotopy switches, while the single-chain and batch-graph baselines succeed only 10% of the time.
  • In the dynamic forest benchmark, POSH raises success rate from 11.92% (batch graph) and 8.46% (single chain) to 29.23%, and lowers collision intensity from 5.1% and 8.3% to 1.9%.
  • An intermediate number of chains (four) performs best; two chains cover too few homotopy classes and six chains collapse into redundant classes.
  • Per-step optimization time (0.077 s average after t=0) stays below the 0.5 s time step, so the loop is fast enough for online use.

Reading between the lines

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

  • Implicit in the paper: a receding-horizon version that adds new support states each step would directly attack the acknowledged chain-collapse problem, since the current formulation only prunes and never grows additional chains.
  • Natural next test: the pruning rule assumes the robot reaches the expected state at each time step; if execution delays are large, states are pruned that should have been kept, so timing robustness is a separate requirement.
  • The h-signature is inherently a 2D construction (vertical rays from obstacle centers), so extending POSH to 3D is not a matter of tuning—it needs a different topological signature for route classes.
  • Since A* can only return the best path that remains in the pruned graph, the method's performance ceiling is graph coverage; adding new states during execution would be the direct way to raise that ceiling.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper presents POSH (Planning Online by Switching Homotopies), an online extension of GPMP-GRAPH. POSH maintains a factor graph of multiple interconnected trajectory chains between start and goal. At each time step it optimizes the entire graph given the current signed distance field, extracts a lowest-cost path via A*, prunes states that are unreachable in time, executes the first control, and repeats. The intended advantage is that retaining trajectories in several homotopy classes allows the planner to switch homotopies online as moving obstacles change the cost landscape, avoiding local minima that trap single-chain planners. The evaluation compares POSH with GPMP-GRAPH and GPMP2 in two simulated 2D dynamic environments (narrow passageway and dynamic forest) using success rate, collision intensity, distance, number of homotopy switches, and computation time. A secondary experiment varies the number of chains. The paper claims improved performance and attributes it to online homotopy switching.

Significance. The idea is timely and the algorithmic contribution is a natural, clearly described extension of an existing method. If the central causal claim were directly supported, POSH would be a useful addition to online trajectory optimization in dynamic environments, and the paper would offer a concrete demonstration of the value of topological diversity in factor-graph planning. The paper is transparent about limitations, notably the acknowledged possibility of homotopy collapse in Section V. Strengths include the use of a standard inference framework (GTSAM/GPMP2), reporting of computation times, a sensitivity study on the number of chains, and a demonstration video. The main weakness is that the experiments do not directly measure the mechanism that is claimed to be responsible for the improvement, and the statistical basis of the comparisons is thin.

major comments (4)
  1. [Sections III-B, III-C, V; Tables I-II] The paper's central claim is that POSH's success comes from maintaining trajectories in multiple homotopy classes (Section III-A) and switching among them online. However, no experiment measures whether the pruned and reoptimized graph actually retains multiple distinct homotopy classes over time. The metrics reported are homotopy switches of the executed path, not the h-signature distribution of the candidate paths in the graph. Since pruning removes states and no new chains or support states are ever added, the available homotopy-class diversity is monotonically non-increasing; as the authors acknowledge in Section V, trajectories can collapse into the same homotopy class. To support the causal claim, the paper should report, at each time step, the number of distinct h-signatures among the chains or among the low-cost paths returned by A*, and show that diversity is preserved when POSH switches. Without such evidence, the improved success rates could equally be explained by online reoptimization of a single good solution.
  2. [Section IV-A] The baseline comparison does not isolate the effect of homotopy-class maintenance. GPMP-GRAPH is described as an offline method and, in the comparison, its multi-chain graph is pruned to a single chain after the first time step, after which it is treated like a GPMP2 chain (Section IV). Thus the comparison conflates two factors: keeping multiple chains versus replanning the entire graph online. An ablation is needed—for example, a variant that reoptimizes the full multi-chain graph online but always commits to the current homotopy class, or a multi-chain graph whose chains are intentionally initialized in the same homotopy class. Without such a control, the paper's attribution of the improvement to homotopy switching instead of to online reoptimization of a larger graph is not established.
  3. [Section IV, Tables I and II] The empirical claims rest on only ten Monte-Carlo runs per environment, reported as point estimates without error bars, confidence intervals, or significance tests. In the dynamic forest, the success-rate gap between POSH (29.23%) and GPMP-GRAPH (11.92%) corresponds to a small number of successes over 130 runs and may not be statistically significant. The paper should report standard deviations or confidence intervals for all metrics and apply an appropriate significance test (for example, a paired test over the common random seeds or a binomial test for success rates). This is necessary to support the claimed improvement.
  4. [Section IV-B, Table III] The hyperparameters NI, RI, and QI are tuned to give good performance for POSH and GPMP-GRAPH, but not for GPMP2, which is a single-chain method and may be at an unfair disadvantage. More importantly, Table III shows that POSH's success rate varies from 22.31% (NI=2) to 29.23% (NI=4) to 18.85% (NI=6), indicating sensitivity to the tuned number of chains. The paper should describe the tuning procedure (e.g., validation environments and ranges searched) and report results across the tested values of NI rather than only the best configuration, so that the reader can assess whether the headline improvement is robust to reasonable hyperparameter choices.
minor comments (5)
  1. [Section III-C] The term 'unreachable (in time)' is used for the pruning step but is not formally defined. Please specify the criterion used by the depth-first search to decide whether a support state is reachable given the robot's dynamics and the time step duration.
  2. [Section IV] The metric 'collision intensity' is defined only as the percentage of the trajectory spent in collisions; please state explicitly whether this is averaged over all runs or only over failed runs, and how a 'collision' is detected in simulation.
  3. [Section II-B] The h-signature construction is described for vertical rays with the caveat 'if the trajectory crosses a ray'; the paper should clarify how the method handles obstacles whose vertical rays overlap or cases where the trajectory starts or ends on a ray.
  4. [Section III-B, Algorithm 1] The optimality claim for A* is not fully justified. A* requires a discrete graph with well-defined edge costs, but the factor graph is a continuous probabilistic model; the paper should specify how edge costs are derived from the optimized factor graph and what is actually being searched.
  5. [Section IV-B] The explanation for the reduced performance at NI=6 ('too constrained' due to QI and the number of time steps) is vague; please provide a quantitative account, such as chain collapse frequency or condition numbers from the optimization.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's claims are empirical and benchmarked; its use of self-authored prior work is building-block citation, not a derivation that reduces to its inputs.

full rationale

POSH's central claim is that an online prune-and-reoptimize loop over a multi-chain factor graph enables homotopy switching and improves success in dynamic environments. This is supported by Monte Carlo comparisons to GPMP2 and GPMP-GRAPH (Tables I and II), not by a derivation from fitted constants or by an assumption that defines the outcome. The A* optimality statement in Section III-B is a standard theorem applied to the pruned graph, not a circular reduction. The reliance on GPMP-GRAPH [10] is building on a prior published algorithm; the multi-chain factor graph is an input construction, and the paper's contribution is the online pruning/reoptimization procedure. The h-signature metric from [18] is used only to count switches of the executed trajectory, not to define success. Section V's admission that 'different trajectories collapsing into the same homotopy class' can occur is a genuine limitation that weakens the causal explanation, but it is an empirical caveat rather than a circular step. No step in the paper exhibits a fitted parameter renamed as a prediction, a uniqueness claim imported from the authors, or an equivalence between a claimed result and its input by construction. Thus the appropriate finding is no significant circularity.

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

The paper introduces no new physical entities. The free parameters are experimental hyperparameters, chosen by hand rather than fitted to data in a formal sense. The axioms are standard algorithmic and modeling assumptions that the central claim depends on, most notably the assumption that the graph retains multiple homotopy classes, which the authors themselves flag as fragile in Section V.

free parameters (6)
  • Number of chains N_I
    Number of interconnected trajectory chains in the factor graph; tuned per environment. Table III shows performance varies with N_I (best at 4).
  • Ratio of interconnections R_I
    Fraction of states interconnected between chains; tuned to give good performance for the respective algorithm.
  • GP prior noise on interconnections Q_I
    Noise parameter for GP priors linking chains; tuned to give good performance.
  • Obstacle cost weight sigma_obs
    Trade-off between smoothness and collision avoidance; stated as kept constant but value not given.
  • Safety distance epsilon
    Safety margin for collision; kept constant but value not specified.
  • Execution and localization noise levels
    Noise injected into dynamics and measurements; stated as kept constant but not quantified.
assumptions (4)
  • standard math A* algorithm returns the lowest-cost path in the graph
    Used in Algorithm 1 line 5 to select the best trajectory from the optimized factor graph.
  • domain assumption Levenberg-Marquardt optimization of the factor graph converges to a useful local optimum at each time step
    The reoptimization step relies on the optimizer improving the graph quickly, especially with warm starts.
  • standard math h-signature uniquely identifies homotopy classes in the plane
    Used to count homotopy switches; based on Grigoriev and Slissenko [18].
  • domain assumption The environment changes slowly enough that the pruned graph retains relevant candidates and warm-started optimization is effective
    The online replanning assumes obstacle motion between time steps is small relative to the planning horizon.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Motion Planning Over Multiple Homotopy Classes with Gaussian Process Inference." pith.science (2026). https://pith.science/paper/3BFYLXDR

@misc{pith2026190800641,
  author       = {Pith},
  title        = {Pith review of: Online Motion Planning Over Multiple Homotopy Classes with Gaussian Process Inference},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3BFYLXDR}},
  note         = {Machine review of arXiv:1908.00641}
}
read the original abstract

Efficient planning in dynamic and uncertain environments is a fundamental challenge in robotics. In the context of trajectory optimization, the feasibility of paths can change as the environment evolves. Therefore, it can be beneficial to reason about multiple possible paths simultaneously. We build on prior work that considers graph-based trajectories to find solutions in multiple homotopy classes concurrently. Specifically, we extend this previous work to an online setting where the unreachable (in time) part of the graph is pruned and the remaining graph is reoptimized at every time step. As the robot moves within the graph on the path that is most promising, the pruning and reoptimization allows us to retain candidate paths that may become more viable in the future as the environment changes, essentially enabling the robot to dynamically switch between numerous homotopy classes. We compare our approach against prior work without the homotopy switching capability and show improved performance across several metrics in simulation with a 2D robot in multiple dynamic environments under noisy measurements and execution.

Figures

Figures reproduced from arXiv: 1908.00641 by the authors.

Figure 1
Figure 1. POSH being used in a dynamic environment where the robot (gray circle) is tasked to reach the goal (green circle) while avoiding obstacles (gray squares). At some time step i In (a) the robot has traveled along the green path when POSH returns a new best (lowest-cost and feasible) trajectory (red). This represents a homotopy switch from the previous best trajectory (black). It executes the first step of this new tra… view at source ↗
Figure 2
Figure 2. Factor Graph consisting of three Gauss-Markov Chains as illustrated in [10]. The white circles represent support states. Black squares are collision factors and black circles are GP priors factors. Interpolated collision factors are omitted for clarity. GP(µ(t), K(t, t0 )) where µ(t) is a vector-valued mean func￾tion and K(t, t0 ) is a matrix-valued covariance function. Fol￾lowing the definition of GP, trajectories … view at source ↗
Figure 3
Figure 3. In (a), the gray circle and green circle represent the robot and goal state respectively. The graph is warm-started from its previous state. In (b), the graph is reoptimized and then A* is used to find a low-cost trajectory (red) on the graph. In (c), edges that will no longer be traversable (dashed blue lines) after executing the first control are pruned. Finally in (d), the robot executes its first control as the … view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Possible graph initializations with (a) no connection be￾tween chains, (b) connections between chains at every other state, and (c) fully connected chains. The robot is the gray circle and the goal state is the green circle. tion found given the SDF at the last time st…
Figure 5
Figure 5. Figure 5: GPMP-GRAPH in (a) finds the lowest-cost trajectory (red) from the initial graph construction of 2 chains. It optimizes and follows this path at each time step, shown in green. In (b)-(c) the optimized path (red) continues to get pushed laterally due to the moving objec…
Figure 6
Figure 6. Figure 6: The two chain factor graph will have fallen into [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]
Figure 6
Figure 6. Figure 6: POSH successfully returns a collision free trajectory utilizing 4 chains. At each consecutive time-step t, the robot (gray circle) prunes away unreachable portion of the graph and reoptimizes the remaining graph until it reaches the goal state (green circle). The path …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 18 canonical work pages

  1. [1]

    A formal basis for the heuristic determination of minimum cost paths,

    P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics , vol. 4, no. 2, pp. 100–107, July 1968

    work page 1968

  2. [2]

    Proba- bilistic roadmaps for path planning in high-dimensional configuration spaces,

    L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Proba- bilistic roadmaps for path planning in high-dimensional configuration spaces,” Robotics and Automation, IEEE Transactions on , vol. 12, no. 4, pp. 566–580, 1996

    work page 1996

  3. [3]

    RRT-connect: An efficient approach to single-query path planning,

    J. J. Kuffner and S. M. LaValle, “RRT-connect: An efficient approach to single-query path planning,” in Robotics and Automation, 2000. Proceedings. ICRA’00. IEEE International Conference on , vol. 2. IEEE, 2000, pp. 995–1001

    work page 2000

  4. [4]

    Incremental sampling-based algorithms for optimal motion planning,

    S. Karaman and E. Frazzoli, “Incremental sampling-based algorithms for optimal motion planning,” Robotics Science and Systems VI , vol. 104, 2010

    work page 2010

  5. [5]

    CHOMP: Covariant Hamiltonian optimization for motion planning,

    M. Zucker, N. Ratliff, A. D. Dragan, M. Pivtoraiko, M. Klingensmith, C. M. Dellin, J. A. Bagnell, and S. S. Srinivasa, “CHOMP: Covariant Hamiltonian optimization for motion planning,” The International Journal of Robotics Research, vol. 32, no. 9-10, pp. 1164–1193, 2013

    work page 2013

  6. [6]

    Motion planning with sequential convex optimization and convex collision checking,

    J. Schulman, Y . Duan, J. Ho, A. Lee, I. Awwal, H. Bradlow, J. Pan, S. Patil, K. Goldberg, and P. Abbeel, “Motion planning with sequential convex optimization and convex collision checking,”The International Journal of Robotics Research , vol. 33, no. 9, pp. 1251–1270, 2014

    2014

  7. [7]

    Continuous- time gaussian process motion planning via probabilistic inference

    M. Mukadam, J. Dong, X. Yan, F. Dellaert, and B. Boots, “Continuous- time gaussian process motion planning via probabilistic inference.” The International Journal of Robotics Research (IJRR) , 2018

    work page 2018

  8. [8]

    Batch informed trees (bit*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs,

    J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, “Batch informed trees (bit*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs,” in 2015 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2015, pp. 3067–3074

    work page 2015

Show all 19 references
  1. [9]

    Regionally accelerated batch informed trees (RABIT*): A framework to integrate local information into optimal path planning,

    S. Choudhury, J. Gammell, T. Barfoot, and S. Srinivasa, “Regionally accelerated batch informed trees (RABIT*): A framework to integrate local information into optimal path planning,” in Proceedings of the 2016 IEEE Conference on Robotics and Automation (ICRA) , 2016

    2016

  2. [10]

    Motion planning with graph-based trajectories and Gaussian process inference

    E. Huang, M. Mukadam, Z. Liu, and B. Boots, “Motion planning with graph-based trajectories and Gaussian process inference.” in Proceedings of the 2017 IEEE Conference on Robotics and Automation (ICRA), 2017

    2017

  3. [11]

    Motion planning as probabilistic inference using Gaussian processes and factor graphs,

    J. Dong, M. Mukadam, F. Dellaert, and B. Boots, “Motion planning as probabilistic inference using Gaussian processes and factor graphs,” in Proceedings of Robotics: Science and Systems (RSS) , 2016

    2016

  4. [12]

    Itomp: Incremental trajectory optimization for real-time replanning in dynamic environments,

    C. Park, J. Pan, and D. Manocha, “Itomp: Incremental trajectory optimization for real-time replanning in dynamic environments,” in ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling , 06 2012

    2012

  5. [13]

    Lifelong planning a,

    S. Koenig, M. Likhachev, and D. Furcy, “Lifelong planning a,” Artificial Intelligence, vol. 155, no. 1, pp. 93 – 146, 2004

    2004

  6. [14]

    Moving target d* lite,

    X. Sun, W. Yeoh, and S. Koenig, “Moving target d* lite,” in 9th Inter- national Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10-14, 2010, Volume 1-3, 2010, pp. 67–74

    2010

  7. [15]

    Rrtx: Real-time motion plan- ning/replanning for environments with unpredictable obstacles,

    M. W. Otte and E. Frazzoli, “Rrtx: Real-time motion plan- ning/replanning for environments with unpredictable obstacles,” in WAFR, 2014

    2014

  8. [16]

    Real-time adaptive motion planning (ramp) of mobile manipulators in dynamic environments with unforeseen changes,

    J. Vannoy and J. Xiao, “Real-time adaptive motion planning (ramp) of mobile manipulators in dynamic environments with unforeseen changes,” IEEE Transactions on Robotics , vol. 24, no. 5, pp. 1199– 1212, Oct 2008

    2008

  9. [17]

    Topological con- straints in search-based robot path planning,

    S. Bhattacharya, M. Likhachev, and V . Kumar, “Topological con- straints in search-based robot path planning,” Autonomous Robots , vol. 33, no. 3, pp. 273–290, 2012

    2012

  10. [18]

    Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane,

    D. Grigoriev and A. Slissenko, “Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane,” in Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC , 01 1998

    1998

  11. [19]

    Factor graphs and GTSAM: a hands-on introduction,

    F. Dellaert, “Factor graphs and GTSAM: a hands-on introduction,” Georgia Tech Technical Report, GT-RIM-CP&R-2012-002, Tech. Rep., 2012

    2012

Pith tools

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