Abstract-Bi-riktad sökning är en allmänt använd strategi för att öka framgången och konvergensen av provtagningsbaserade rörelseplaneringsalgoritmer. Ändå är få resultat tillgängliga som slår samman både dubbelriktad sökning och asymptotisk optimalitet till befintliga optimala planerare, såsom PRM *, RRT *, och FMT *. Syftet med detta dokument är att fylla denna lucka. Specifikt presenterar detta dokument en dubbelriktad, provtagningsbaserad, asymptotiskt optimal algoritm som heter Bi-riktad FMT * (BFMT * ) som utökar den snabba marschträd (FMT * ) algoritm till dubbelriktad sökning samtidigt bevara sina viktiga egenskaper, främst lat sökning och asymptotic optimalitet genom konvergens i sannolikhet. BFMT * utför en två-källa, lat dynamisk programmering rekursion över en uppsättning slumpmässigt ritade prover, motsvarande generera två sökträd: en i kostnad-för att komma utrymme från den ursprungliga konfigurationen och en annan i kostnad att gå utrymme från målkonfigurationen. Numeriska experiment illustrerar fördelarna med BFMT * över dess enkelriktade motsvarighet, samt ett antal andra state-of-the-art planerare. Rörelseplanering är beräkning av vägar som styr system från en initial konfiguration till en uppsättning mål konfiguration (s) runt närliggande hinder, samtidigt som eventuellt optimera en objektiv funktion. Problemet har en lång och rik historia inom robotik, och många algoritmiska verktyg har utvecklats; vi hänvisar den intresserade läsaren till [1] och referenser där. Det kan hävdas att provtagningsbaserade algoritmer är bland de mest genomgripande och utbredda planerarna inom robotik, inklusive den probabilistiska färdplansalgoritmen (PRM) [2], den expansiva rymdträdsalgoritmen (EST) [3], [4], och den snabbt utforskande slumpmässiga trädalgoritmen (RRT) [5]. Sedan deras utveckling, ansträngningar för att förbättra "kvalitet" av vägar ledde till asymptotiskt-optimala (AO) varianter av RRT och PRM, namngivna RRT * respektive PRM *,, där kostnaden för den returnerade lösningen konvergerar nästan säkert till det optimala eftersom antalet prover närmar sig oändlighet [6] Även om sådana dubbelriktade versioner av RRT och PRM är probabilistically komplett, de inte åtnjuter optimala garantier. Nästa logiska steg i sökandet efter snabba planeringsalgoritmer är utformningen av dubbelriktade, samplingsbaserade, asymptotiska-optimala algoritmer. Såvitt vi vet är de enda tillgängliga resultaten i detta sammanhang [18] och det opublicerade arbetet [19], som båda diskuterar dubbelriktade genomföranden av RRT *. Inget arbete ger dock ett matematiskt stelbent bevis på asymptotisk optimalitet som utgår från de första principerna. Syftet med detta dokument är därför att föreslå och noggrant analysera en sådan algoritm. Bidragsuttalande: I detta dokument introduceras algoritmen Bidirective Fast Marching Tree (BFMT * ). 1 Till det bästa av författarnas kunskap är detta den första trädbaserade, asymptotiskt optimala dubbelriktade provtagningsbaserade planeraren. BFMT * utökar FMT * till dubbelriktad sökning och utför i huvudsak en "lazy", dubbelriktad dynamisk programmering rekursion över en uppsättning probabilistiskt dragna prover i det fria konfigurationsutrymmet. Bidraget från detta dokument är trefaldigt. Först presenterar vi BFMT * algoritmen i Avsnitt III. För det andra bevisar vi rigoröst den asymptotiska optimaliteten hos BFMT * (enligt begreppet sannolikhetskonvergens) och karakteriserar dess konvergensgrad i avsnitt IV. Vi noterar att konvergenshastigheten för FMT * i [11] endast bevisas för hinderfria konfigurationsutrymmen, medan vi generaliserar detta resultat för att möjliggöra förekomsten av hinder. Slutligen utför vi numeriska experiment i sektion V över ett antal planeringsutrymmen som föreslår BFMT * konvergerar till en optimal lösning minst lika snabbt som FMT *, PRM *, och RRT *, och ibland betydligt snabbare. Låt X vara en d-dimensionell konfiguration utrymme, och låt X obs vara hinder regionen, så att X \ X obs är en 1 Den asterisk *, uttalad "stjärna", är avsedd att representera asymptotic optimality mycket lik för RRT * och PRM * algoritmer.
BFMT Ã, som är en dubbelriktad version av FMT Ã, infördes av REF.
An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning
{'venue': 'Proceedings of the ... IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE/RSJ International Conference on Intelligent Robots and Systems', 'journal': 'Proceedings of the ... IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE/RSJ International Conference on Intelligent Robots and Systems', 'mag_field_of_study': ['Computer Science', 'Medicine']}