AOXRRTConnect: fix path starting at the goal, and unbounded growTree loop - #1471
Open
chenzhike110 wants to merge 2 commits into
Open
chenzhike110 wants to merge 2 commits into
chenzhike110 wants to merge 2 commits into
Conversation
…loop Fixes ompl#1420. On the "straight line check" pass `gs` is preset to REACHED, so the first growTree() on the start tree is skipped. On that same pass `tgi.xmotion` still holds the goal tree root assigned when tGoal_ was seeded, so `addedMotion = tgi.xmotion` makes `startMotion` a goal-tree node. Both reconstructed chains then lie inside the goal tree, and isStartGoalPairValid(goal_root, goal_root) still passes, so the planner reports EXACT_SOLUTION for a path that never touches the start -- zero length when the trees connect immediately. This is the zero-length path reported in ompl#1420. Three changes: * Remember the motion created from pis_.nextStart() and use it as `addedMotion` on the straight-line pass. * Guard the "step back to avoid a duplicate state" branch: when both motions are roots there is no duplicate to remove, and the current code sets goalMotion to nullptr, which connectionPoint_ then dereferences. * Check the PlannerTerminationCondition in `while (gsc == ADVANCED)`. That loop is otherwise unbounded and a single solve() can run far past its budget. The last one is not optional. AORRTC::solve()'s outer do/while(!ptc) has exactly one early exit, `if (bestCost_.value() == 0) return INVALID_GOAL`, so the zero-length path is currently the only thing that stops the unbounded loop. Fixing the path without also bounding the loop turns "wrong path" into "hangs"; so does disabling AORRTC's internal simplifySolution. Both were observed. Signed-off-by: chenzhike110 <3180103610@zju.edu.cn>
The approximate solution bookkeeping guards `approxsol = tgi.xmotion` with the `tgi.start` flag alone. On the straight line check pass `gs` is preset to REACHED, so no growTree has run on the start tree and `tgi.xmotion` still holds the goal tree root assigned when `tGoal_` was seeded. The approximate path is then reconstructed by walking parents from a goal tree node, and its first state is the goal rather than the start -- the same defect as the exact solution path fixed in the previous commit, on the other branch. Every motion carries the root of its own tree (growTree propagates `motion->root = nmotion->root`), so test tree membership directly instead of trusting the flag. This also covers any other pass where the two disagree.
This branch has not been deployed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Fixes #1420.
The reported symptom
AORRTCon aRealVectorStateSpacereturns a zero-length path whose states are allthe goal, and logs
Zero-length path found. May have a common start/goal.repro_1420.cpp(attached, OMPL-only) reproduces it deterministically:The trigger is start and goal being directly connectable — with an obstacle between
them AORRTC behaves correctly. Reproduced at dim 2 and 6, with 1 and 3 goal states.
Root cause (B):
tgi.xmotionis used for two different thingsAOXRRTConnect::solve()presetsgs = REACHEDin the "straight line check" so thefirst
growTreeon the start tree is skipped. But on that same passtgi.xmotionwasassigned the goal tree root when
tGoal_was seeded:tgi.starthas just been flipped tofalse, sostartMotion = addedMotion= the goalroot (
parent == nullptr,root == goal). Both reconstructed chains then live insidethe goal tree, and
isStartGoalPairValid(goal_root, goal_root)still returns true, sothe planner reports
EXACT_SOLUTION.The fix remembers the motion created from
pis_.nextStart()and uses it asaddedMotionon that pass.It also guards the "step back to avoid a duplicate state" branch: when both
startMotionandgoalMotionare roots there is no duplicate to remove, and thecurrent code sets
goalMotion = nullptr, which the followingconnectionPoint_ = std::make_pair(startMotion->state, goalMotion->state)dereferences.Root cause (A):
while (gsc == ADVANCED)has no termination checkNo
PlannerTerminationCondition, no iteration bound. A singlesolve()call can runfor minutes under a sub-second budget.
⚠ The two are coupled — fixing (B) alone makes things worse
AORRTC::solve()'s outerdo { ... } while (!ptc)has exactly one early exit:The zero-length path produced by (B) is therefore the only thing that currently stops
(A). We first fixed (B) alone, and separately tried disabling AORRTC's internal
simplifySolution(where #1420 currently suspects the problem) — both turned "wrongpath" into "hangs indefinitely" on a 0.4 s budget. That is why this PR fixes both.
The coupling is visible in the repro output: before the fix the
obstacle=norowsreturn in 0 ms (hitting the zero-length early return); after the fix they take the
full 400 ms budget, as an anytime planner should. That 400 ms is exactly the work
that the early return was skipping.
Validation
repro_1420.cpp: 8/8 configurations correct after the patch (|path[0]-start| = 0,and
obstacle=nonow returns the straight line,len= the start–goal distance).500 ms budget, 4 parallel AORRTC instances): 160/160 queries solved, path length
p50 2.037 rad, smoothness p50 0.4825 — unchanged from the pre-fix quality on the
queries that did succeed, so the patch does not trade quality for correctness.
GoalStateswith 2-8 states, goals from IK branches): 7/9 -> 9/9, and alarger run of 96 such queries: 96/96.
All of the above was run on
main(68614a0) with this patch applied, and the repro wasadditionally checked against 2.0.0 with and without the patch.
Note: I could not run
clang-format(not available on this machine), so the new linesfollow the surrounding style by hand -- please reformat if it does not match.
⚠ Noticed but not fixed here
pdef_accumulates three solution paths per outer round (one fromAOXRRTConnect::solve, two fromAORRTC::solve) and is never cleared — we observedthree identical entries (
9.968 9.968 9.968) for one query. That is unbounded growthplus a quadratic sorted insert as the round count rises. Left alone because it does not
affect correctness and fixing it means touching AORRTC's solution bookkeeping.
repro_1420.cpp