When Roadmap Completion Pays Off: A Two-Trace Analysis of Multi-Query Robot Path Planning

A reusable robot roadmap stores candidate motions as a graph and retains collision-test results for edges shared across start--goal requests. For an observed request sequence and specified operation prices, we determine whether full validation of reusable edges reduces modeled work and which request boundary minimizes it. Two executions supply the comparison: on-demand (lazy) validation throughout and completion before the first request. Every completion date adds checks on persistent edges still untested by lazy planning at the final request. When service on the completed graph is independent of earlier requests, the second trace supplies search work and terminal checks on edges incident to the current start or goal. Direct execution verified reconstruction for 17,280 schedules on 216 forty-request workloads and two search engines. With persistent and terminal checks priced equally and positive prices evaluated separately for each workload, some completion beat permanent laziness on 151 of 216 restarted A* workloads and 183 of 216 query-local Lifelong Planning A* workloads. Delaying completion beat both upfront completion and permanent laziness on one of 216 and 40 of 216 workloads, respectively. The largest limiting gains over the better endpoint were 0.258\% and 3.361\% as collision-test price approached zero. Under permanent laziness, median paired timing ratios favored restarted A* over query-local repair on generated maps. Lazy terminal attachment gave lower median suffix time than eager attachment on all 60 matched triggered A* workloads. The criterion distinguishes losses that changing the purchase date could reverse from purchases that no date would repay.

Authors

Institutions

Publication Details

Journal
Research Square
Published
2026-11-20
DOI
https://doi.org/10.21203/rs.3.rs-11790998/v1
Primary Topic
Robotic Path Planning Algorithms
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

When Roadmap Completion Pays Off: A Two-Trace Analysis of Multi-Query Robot Path Planning

Meshaal Mouawad
Research Square
Robotic Path Planning Algorithms
preprint

When Roadmap Completion Pays Off: A Two-Trace Analysis of Multi-Query Robot Path Planning

Meshaal Mouawad
preprint en

Abstract

A reusable robot roadmap stores candidate motions as a graph and retains collision-test results for edges shared across start--goal requests. For an observed request sequence and specified operation prices, we determine whether full validation of reusable edges reduces modeled work and which request boundary minimizes it. Two executions supply the comparison: on-demand (lazy) validation throughout and completion before the first request. Every completion date adds checks on persistent edges still untested by lazy planning at the final request. When service on the completed graph is independent of earlier requests, the second trace supplies search work and terminal checks on edges incident to the current start or goal. Direct execution verified reconstruction for 17,280 schedules on 216 forty-request workloads and two search engines. With persistent and terminal checks priced equally and positive prices evaluated separately for each workload, some completion beat permanent laziness on 151 of 216 restarted A* workloads and 183 of 216 query-local Lifelong Planning A* workloads. Delaying completion beat both upfront completion and permanent laziness on one of 216 and 40 of 216 workloads, respectively. The largest limiting gains over the better endpoint were 0.258\% and 3.361\% as collision-test price approached zero. Under permanent laziness, median paired timing ratios favored restarted A* over query-local repair on generated maps. Lazy terminal attachment gave lower median suffix time than eager attachment on all 60 matched triggered A* workloads. The criterion distinguishes losses that changing the purchase date could reverse from purchases that no date would repay.

Research Square
Mississippi State University (US)
Robotic Path Planning Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon