Abstract-snabbt utforskande Random Tree (RRT), liksom andra provtagningsbaserade rörelseplaneringsmetoder, har varit mycket framgångsrik när det gäller att lösa rörelseplaneringsproblem. Trots detta kan provtagningsbaserade planerare inte lösa alla problem av intresse på ett effektivt sätt, så uppmärksamheten vänder sig i allt högre grad till att parallellisera dem. Men en utmaning i att parallellisera RRT är den globala beräkning och kommunikation overhead av närmaste granne sökning, en nyckel operation i RRTs. Detta är en kritisk fråga eftersom det begränsar skalbarheten av tidigare algoritmer. Vi presenterar två parallella algoritmer för att ta itu med detta problem. Den första algoritmen utökar befintligt arbete genom att införa en parameter som justerar hur mycket lokal beräkning görs innan en global uppdatering. Den andra algoritmen delar radiellt konfigurationsutrymmet i regioner, konstruerar en del av trädet i varje region parallellt, och förbinder delträden, i att ta bort cykler om de finns. Genom att dela upp utrymmet ökar vi beräkningslokaliseringen och möjliggör ett skalbart resultat. Vi visar att våra strategier är skalbara. Vi presenterar resultat som visar nästan linjär skalning till hundratals processorer på ett Linuxkluster och en Cray XE6-maskin.
Jacobs m.fl. REF införde nyligen hastighetshöjningar genom att justera mängden lokal beräkning innan en uppdatering av globala datastrukturer och genom att radiellt dela in konfigurationsutrymmet i regioner.
A scalable distributed RRT for motion planning
{'venue': '2013 IEEE International Conference on Robotics and Automation', 'journal': '2013 IEEE International Conference on Robotics and Automation', 'mag_field_of_study': ['Computer Science']}