- Rating
- 2
- Confidence
- 1(−1)
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes GlobMP, a framework for continuous-time motion planning and trajectory steering. It represents trajectories using Bernstein polynomials and expresses collision avoidance and steering constraints through polynomial nonnegativity over the entire time interval. The objective encourages smooth trajectories by minimizing the energy of their derivatives. The paper establishes global convergence under regularity assumptions, sufficiently fine grid initialization, and exact optimization steps. It also provides approximation bounds as the trajectory representation is refined. For practical use, the authors introduce a solver based on gradient updates and approximate feasibility restoration. Experiments cover synthetic planning problems, maze navigation, multi-robot coordination, and real-robot tasks, including steering policy-generated humanoid motions. The reported results show improvements in trajectory cost or task success in several settings.
Critical strengths
-
The paper addresses collision avoidance over the entire trajectory. Checking only discrete time points can miss collisions between them, especially in tight spaces or when several robots move together. The polynomial formulation expresses safety constraints over the full time interval. This directly addresses an important limitation of sampled collision checking and gives a principled way to formulate continuous-time safety.
-
The framework supports both motion planning and trajectory steering. It combines smoothness, collision avoidance, boundary conditions, and constraints on deviation from a reference trajectory within one optimization problem. This is useful because a policy-generated motion may need adjustment to satisfy new constraints while retaining its intended behavior. The ability to handle both planning and motion adjustment makes the method relevant to several robot applications.
Critical weaknesses
-
The theory requires a sufficiently fine grid search and exact optimization steps, while the experiments use heuristic initialization and approximate solving. The effects of initialization and solver tolerances are not clearly evaluated, leaving a gap between the theory and practical results.
-
The benefit of the proposed solver alone is unclear. Newton refinement further reduces the cost by a factor of 2–3, and some comparisons use different planning budgets. These differences make the improvements difficult to attribute to the core method.
Questions for authors
- How sensitive are the success rate and final cost to initialization and solver tolerances?
- How does Algorithm 2 alone perform without Newton/SQP refinement, using the same planning budget as the baselines?
- After post-processing, are the final trajectories checked for collisions over the whole time interval, or only at sampled times?
3 comments
Response to Reviewer MqJ2- Part II
Weakness 2 (attribution and budgets): "The benefit of the proposed solver alone is unclear. … some comparisons use different planning budgets. These differences make the improvements difficult to attribute to the core method."
Question 2: "How does Algorithm 2 alone perform without Newton/SQP refinement, using the same planning budget as the baselines?"
Response: We thank the reviewer for these questions.
The solver alone (Weakness 2; Question 2). The submission did not separate the solver from the post-processing. The revision reports the solver alone.
The submitted solver alone, with no SQP polish and no Newton step and with the 60 s of the sampling baselines, returns a feasible curve on all 80 synthetic instances, at 53.8 times the cost of the full submitted pipeline at the median, and above the best baseline (newly added Table R4, row V0). With the SQP polish alone, only 50 of its 80 curves were feasible.
In the synthetic study, with the cutting-plane repair (Algorithm 2) and the INIT start, GlobMP matches the submitted costs and is lower on 9 of the 80 instances, with no SQP polish and no Newton step. A run takes 0.75 s at the median, which is less time than any baseline had. RRT-Connect and RRT* had 60 s, and GCS and SDP-MP one hour. A baseline curve refined by a Newton step reaches GlobMP's cost at the median.
In the maze, GlobMP runs inside DiRecT's sampler, with neither step. With the same information as the baselines, its success rate stays at 1.000 and its score is close to DiRecT's. The higher score of the main rows comes from wall constraints that DiRecT does not have.
In the suite, the seed alone, returned as the plan without GlobMP, passes the benchmark in 0.82 of the runs, against 0.998 with GlobMP.
Budgets (Weakness 2; Question 2). In the suite GlobMP had 300 s and MMD-CBS 60 s. Stopped at the 60 s of MMD-CBS or at DiRecT's own time, GlobMP's success rate drops by at most 0.024 (Low speed cap, 60 s), and by at most 0.009 at the Medium speed cap.
The suite numbers use the route seed; with the submitted one (the grid seed in the paper) the success rate at 60 s was 0.714.
Changes to the paper:
- Section 4.1: GlobMP without the SQP polish and the Newton step.
- Section 4.2: newly added Figure R1, suite success and planning time against DiRecT.
- Appendix A4.2: newly added Table R4, ablation of the post-processing steps (rows V0 to V2).
- Appendix A4.3: maze rows with GlobMP inside DiRecT's sampler and without wall information.
- Appendix A4.4: Tables 3–10, GlobMP rows rerun; newly added Table R6, suite success rate, planning time and budgets, including the success rate at cut budgets.
Question 1: "How sensitive are the success rate and final cost to initialization and solver tolerances?"
Response: We thank the reviewer for this question. The initialization matters. In the suite, straight-line seeds solve far fewer runs than the route seed, in which each robot follows its shortest route around the obstacles, and small changes to that seed change little on the benchmark's test (Table R5). For the final cost, GlobMP with the cutting-plane repair returns a certified curve from every one of the 2,472 route-class starts. A random class costs about twice the best at the median, and INIT picks the cheapest class on all 80 instances (newly added Table R5). Halving or doubling its grid spacing gives the same curves.
The tolerances matter little. With the tolerance ten times tighter or looser, the success rate in the suite barely changes, and all 80 synthetic curves stay certified at the same cost (Appendix A4.2; suite: Table R9).
Changes to the paper:
- Appendix A4.2: newly added Table R5, sensitivity to the seed.
- Appendix A4.5: newly added Table R9, sensitivity to the tolerances.
(continued in Part III)
Response to Reviewer MqJ2- Part III
Question 3: "After post-processing, are the final trajectories checked for collisions over the whole time interval, or only at sampled times?"
Response: We thank the reviewer for this question. In the submission, only at sampled times after post-processing. The paper did not say so. We added an exact check of the reported curves over the whole interval, and all pass in the synthetic study, on the Robotarium and in the maze. In the maze rows without wall constraints the check covers the keep-out regions only, and 39 and 19 of 100 of those plans cross a maze wall, against 42 and 39 of DiRecT's.
The suite's benchmark tests the 64 waypoints only, and we keep it so that all methods are scored alike. It joins the waypoints by straight segments, which cut the corners of our curve. Under an exact check of this motion, at the Medium speed cap, GlobMP's plan passes in 0.99 of the runs, and the best of DiRecT's 64 candidates in 0.50. The steering study is not checked in this way, because its hand-position constraints are linearized; evaluated with exact kinematics at 1 ms spacing, no solve violated them.
Changes to the paper:
- Section 4.2: the exact check of the suite plans.
- Appendix A4.3: plans that cross a maze wall without wall constraints.
- Appendix A4.5: newly added Table R10, exact check of the reported curves.
- Appendix A4.6: newly added Table R11, steering latency per solve and per chunk, with the check of the linearized constraints at 1 ms spacing.
Response to Reviewer MqJ2- Part I
Response: We thank the reviewer for this point. We added an implementation of the repair and of the start that the theorem analyses (Algorithms 2 and 1 of the revised paper; GlobMP itself is Algorithm 3). The repair solves program (5) by cutting planes, and the start is found by a search (INIT) over the pieces of the curve that does not list the grid.
Section 4.1 runs it, up to 200 robots, and in the main comparison its costs are equal to or lower than the submitted ones. Its curve class and its reduced set of INIT states are outside the theorem. In a rerun in the curve class of the theorem, with the same INIT, all 170 runs pass the exact check in the same route classes (Appendix A4.2). The other studies use a first-order restoration from heuristic seeds (initial curves). The paper says this in Appendix A4.5. The suite and the Robotarium are also rerun in the curve class of the theorem, with the repair of Algorithm 2 and collision constraints only (Table 11). The start is a prioritized one (INIT's search run one robot at a time), which is not the start of the theorem. With the speed limits dropped, all 3,360 suite runs and all 200 Robotarium instances are collision-free, and 950 of the suite plans exceed the speed cap of their setting. The maze is planned as a stand-alone problem in the setting of the theorem, with INIT on the full grid.
On the 80 instances of Section 4.1, the cutting-plane repair and the first-order restoration end at the same cost from the same start. A small example in the class of the theorem, with INIT on the full grid and an exact repair, is in Appendix A4.2. GlobMP reaches the best certified cost in all six runs at the two finer grid spacings, and with two robots in all 12 runs at the finest spacing. On the one-piece instance of the newly added Table R2, the first-order restoration stops 2.7% above the optimum from route-class seeds. The effects of the initialization and of the tolerances are reported under Question 1.
Changes to the paper:
(continued in Part II)