Abstract-Under det senaste årtiondet har inkrementella provtagningsbaserade rörelseplaneringsalgoritmer, såsom de snabbt utforskande Random Trees (RRTs) visat sig fungera bra i praktiken och ha teoretiska garantier såsom probabilistisk fullständighet. Hittills har dock inga teoretiska gränser fastställts för kvaliteten på den lösning som erhålls genom dessa algoritmer. Det första bidraget från detta dokument är ett negativt resultat: det är bevisat att kostnaden för den bästa vägen i RRT under milda tekniska förhållanden nästan säkert sammanfaller med ett icke-optimalt värde. För det andra, en ny algoritm beaktas, kallas den snabbutforskande Random Graph (RRG), och det visas att kostnaden för den bästa vägen i RRG konvergerar till den optimala nästan säkert. För det tredje, en trädversion av RRG introduceras, kallas RRT * algoritm, som bevarar den asymptotiska optimalitet av RRG samtidigt som en trädstruktur som RRT. Analysen av de nya algoritmerna bygger på nya kopplingar mellan samplingsbaserade rörelseplaneringsalgoritmer och teorin om slumpmässiga geometriska grafer. När det gäller beräknings komplexitet, det visas att antalet enkla operationer som krävs av både RRG och RRT * algoritmer är asymptotiskt inom en konstant faktor av det som krävs av RRT.
Nyligen utvecklat RRT * REF ger garantier för att proverna är fullständiga och att lösningen är optimal.
Incremental Sampling-based Algorithms for Optimal Motion Planning
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Engineering']}