Rapidly Exploring Random Trees (RRTs) is a famous algorithm family for solving path/motion planning problems that are generally encountered in robotics applications. They are known to outperform deterministic path planners in highly cluttered/unknown environments due to their probabilistical nature.

     RRT library has been initiated with four RRT variants, each building on top of the previous one. RRT, RRT*, Bidirectional RRT*(BiRRT*) and Bidirectional RRT* with Heuristics (BiRRT* /w). The library is implemented in C++ with as much as possible compile-time programming provided through Template Meta-Programming (TMP). Due to its compile-time nature, it is quite efficient when compared to other research candidates. (Boost’s Rtree) implementation is used as the underlying fringe for nearest neighbor, search and insert operations. However it turned out that when the dimensionality of the problem grows, Rtree revealed out as an inefficient data structure. Due to that, one of the future goals is the replacement of it with a more suitable data structure (e.g. (Octree) or (OctoMap).

     Single-robot motion planning is a well-studied domain; on the other hand, multi-robot motion planning is mostly solved with mediocre solutions (e.g. completely decoupled motion planning of the agents with ensured prevention of robot-robot collisions through other measures such as different flight/drive lanes and etc.) or remains disclosed in the context of the industrial applications as the efforts of private companies. Having all said, there are academical attempts to solve the multi-robot motion planning problems, yet they are very few in number when compared to single-robot case. Nonetheless, as the robots become more ubiquitious and entangled with each other, it is compulsory to come up with proper multi-robot solutions. Therefore this project will explore the possibilities of the applications of RRT algorithm family on the multi-robot motion planning in the 2nd stage. sRRT and Subdimensional Expansion has been chosen as the algorithm and framework to pursue this goal.