RRT and the piano mover’s problem
Fig.2: RRT algorithm considering obstacles (pseudocode ) 4
q 0 is the initial point or ‘root’ of the whole tree. The algorithm iteratively connects a newly randomly generated point to the nearest point on the existing tree, which is q n . Note that q n can be any point on the edge of the tree, which does not necessarily need to be a node. STOPPING_CONFIGURATION on line 4 is used when the line established between q n and 𝛼 ( 𝑖 ) is blocked by obstacles. The function will return q s , the nearest point to 𝛼 ( 𝑖 ) on the line q n to 𝛼 ( 𝑖 ) which is able to establish an unblocked line towards q n , to be added into the tree. Figure 3 demonstrates the cases mentioned above.
Fig.3: Two special cases in the RRT algorithm
RRTs are constructed incrementally in a way that quickly reduces the expected distance of a randomly- chosen point to the tree. RRTs are particularly suited for path-planning problems that involve obstacles and differential constraints. 5 Note that RRT struggles a lot in a convex shape of map, as shown in figure 5.
Fig.4: the RRT algorithm after 45 and 2345 iterations 6
4 Knispel 2013: 156. 5 Knispel 2013: 156. 6 LaValle 2006: 230.
202
Made with FlippingBook interactive PDF creator