DocumentCode :
2420074
Title :
Probabilistic path planning for multiple robots with subdimensional expansion
Author :
Wagner, Glenn ; Kang, Minsu ; Choset, Howie
Author_Institution :
Robot. Inst., Carnegie Mellon Univ., Pittsburgh, PA, USA
fYear :
2012
fDate :
14-18 May 2012
Firstpage :
2886
Lastpage :
2892
Abstract :
Probabilistic planners such as Rapidly-Exploring Random Trees (RRTs) and Probabilistic Roadmaps (PRMs) are powerful path planning algorithms for high dimensional systems, but even these potent techniques suffer from the curse of dimensionality, as can be seen in multirobot systems. In this paper, we apply a technique called subdimensional expansion in order to enhance the performance of probabilistic planners for multirobot path planning.We accomplish this by exploiting the structure inherent to such problems. Subdimensional expansion initially plans in each individual robot´s configuration space separately. It then couples those spaces when robots come into close proximity with one another. In this way, we constrain a probabilistic planner to search a low dimensional space, while dynamically generating a higher dimensional space where necessary. We show in simulation that subdimensional expansion enhanced PRMs can solve problems involving 32 robots and 128 total degrees of freedom in less than 10 minutes. We also demonstrate that enhancing RRTs and PRMs with subdimensional expansion can decrease the time required to find a solution by more than an order of magnitude.
Keywords :
mobile robots; multi-robot systems; path planning; probability; configuration space; high dimensional systems; low dimensional space search; multiple robots; multirobot path planning; path planning algorithms; probabilistic path planning; probabilistic roadmaps; rapidly-exploring random trees; subdimensional expansion; Collision avoidance; Educational robots; Path planning; Planning; Probabilistic logic; Robot kinematics;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Robotics and Automation (ICRA), 2012 IEEE International Conference on
Conference_Location :
Saint Paul, MN
ISSN :
1050-4729
Print_ISBN :
978-1-4673-1403-9
Electronic_ISBN :
1050-4729
Type :
conf
DOI :
10.1109/ICRA.2012.6225297
Filename :
6225297
Link To Document :
بازگشت