Vi utvecklar en ny analys av provtagningsbaserad rörelseplanering i Euclidean utrymme med enhetlig slumpmässig provtagning, vilket avsevärt förbättrar det berömda resultatet av Karaman och Frazzoli och efterföljande arbete. I synnerhet bevisar vi förekomsten av en kritisk anslutning radie proportionell mot Y(n À1=d ) för n prover och d dimensioner: under detta värde planeraren garanteras att misslyckas (liknande visas av Karaman och Frazzoli). Ännu viktigare, för större radievärden planeraren är asymptotiskt (nära)optimalt. Dessutom ger vår analys en explicit lägre gräns på 1 À O (n À1 ) om sannolikheten för framgång. En praktisk konsekvens av vårt arbete är att asymptotisk (nära) optimalitet uppnås när varje prov är ansluten till endast Y(1) grannar. Detta är i skarp kontrast till tidigare arbete som kräver Y( log n) anslutningar, som induceras av en radie av orderlogg n 1=d. Vår analys gäller den probabilistiska färdplansmetoden (PRM), liksom en mängd olika ''PRM-baserade'-planerare, inklusive RRG, FMT*, och BTT. Kontinuum percolation spelar en viktig roll i våra bevis. Slutligen utvecklar vi liknande teori för alla ovan nämnda planerare när de konstrueras med deterministiska prover, som sedan sparifieras på ett slumpmässigt sätt. Vi anser att denna nya modell, och dess analys, är intressant i sig.
I en nyligen publicerad rapport REF fastställs förekomsten av en kritisk anslutningsradie r * = γ 1 n 1/d, där γ är konstant: om r < r * då PRM är garanterad att misslyckas (även när n → γ), och om r > r * då är det garanterat att konvergera a.a.s.
The critical radius in sampling-based motion planning
{'venue': None, 'journal': 'The International Journal of Robotics Research', 'mag_field_of_study': ['Computer Science', 'Mathematics']}