Abstract-Vi presenterar lägre bundna träd-RRT (LBT-RRT), en enkel-query provtagning-baserad rörelseplanering algoritm som är asymptotiskt nära optimal. Nämligen konvergerar den lösning som utvinns ur LBT-RRT till en lösning som ligger inom en approximationsfaktor på 1 + ε för den optimala lösningen. Vår algoritm möjliggör en kontinuerlig interpolering mellan den snabba RRT-algoritmen och den asymptotiskt optimala RRT*- och RRG-algoritmen när kostnadsfunktionen är sökvägens längd. När approximationsfaktorn är 1 (dvs. ingen approximation är tillåten) beter sig LBT-RRT som RRG. När approximationsfaktorn är obunden beter sig LBT-RRT som RRT. Däremellan visas LBT-RRT producera vägar som har högre kvalitet än RRT skulle producera och köra snabbare än RRT* skulle köras. Detta görs genom att upprätthålla ett träd som är en del av RRG färdplanen och en andra, extra graf, som vi kallar den lägre bundna grafen. Kombinationen av de två färdplanerna, som är snabbare att upprätthålla än den färdplan som upprätthålls av RRT*, garanterar effektivt asymptotisk nära optimalitet. Vi föreslår att använda LBT-RRT för hög kvalitet när som helst rörelseplanering. Vi demonstrerar algoritmens prestanda för scenarier som sträcker sig från 3 till 12 grader av frihet och visar att även för små approximativa faktorer producerar algoritmen högkvalitativa lösningar (jämförbara med RRG och RRT*) med lite drifttid overhead jämfört med RRT.
Lower Bound Tree-RRT (LBT-RRT) REF algoritm upprätthåller två grafer och de kan kombineras för att generera den slutliga vägen med en approximationsfaktor.
Asymptotically Near-Optimal RRT for Fast, High-Quality Motion Planning
{'venue': 'IEEE Transactions on Robotics', 'journal': 'IEEE Transactions on Robotics', 'mag_field_of_study': ['Engineering', 'Mathematics', 'Computer Science']}