Abstract-Sampling-baserade algoritmer som den snabbt utforskande Random Tree (RRT) har nyligen föreslagits som en effektiv metod för beräknings svårt rörelse planering problem. Även om det är känt att RRT-algoritmen snabbt kan hitta en genomförbar lösning, finns det inga garantier för kvaliteten på en sådan lösning, t.ex. med avseende på en viss kostnadsfunktion. För att ta itu med denna begränsning föreslog författarna nyligen en ny algoritm, kallad RRT *, som säkerställer asymptotisk optimalitet, dvs. nästan säker konvergens av lösningen tillbaka av algoritmen till en optimal lösning, samtidigt som samma egenskaper hos standard RRT algoritm, både när det gäller beräkning av genomförbara lösningar, och beräknings komplexitet. I detta dokument, RRT * algoritmen utvidgas för att hantera olika begränsningar. Ett tillräckligt villkor för asymptotisk optimalitet ges. Det visas att RRT * algoritmen utrustad med någon lokal styrning som uppfyller detta villkor konvergerar till en optimal lösning nästan säkert. I synnerhet tillhandahålls enkla lokala styrningsförfaranden för en Dubins fordon samt en dubbelintegratör. Simuleringsexempel ges också för dessa system som jämför RRT och RRT * algoritmer.
I REF fastställdes tillräckliga villkor för att säkerställa asymptotisk optimalitet för RRT*-algoritmen för system med differentialbegränsningar, och det visades hur man applicerar RRT* på två specifika fall av kinodynamiska system: Dubins bil och den dubbla integratorn.
Optimal kinodynamic motion planning using incremental sampling-based methods
{'venue': '49th IEEE Conference on Decision and Control (CDC)', 'journal': '49th IEEE Conference on Decision and Control (CDC)', 'mag_field_of_study': ['Computer Science']}