RRT and the piano mover’s problem
Fig.17: special case on the edge of obstacle
As shown in this figure, the centre of the block is still in the ‘rectangle region’ so the algorithm will us the function we deduced in 2.32 to check if it collides with the obstacle. According to the function, it collides because one of its vertices is below the blue dotted line. However, as shown clearly on the graph, it is far from colliding and there is room for it to come closer without being blocked. As for future development, apart from solving the questions mentioned above, this way of approaching PMP can be developed into 3-dimensional planning problem as well. More information is needed to uniquely identify a state of the object in a 3-dimensional world, e.g., positions and rotations in three directions. But we can use linear algebra to extend the approach above. The hard part will also be how to come up with the obstacles in higher-level search space. A very promising focus is trying to find a general algorithm to generate obstacles in higher-level maps for any shape of obstacles.
Bibliography
Knispel, L. Matousek, R (2013) ‘A Performance Comparison of Rapidly - exploring Random Tree and Dijkstra’s Algorithm for Holonomic Robot Path Planning’ Recent Advances in Applied and Theoretical Mathematics , 154-162 LaValle, S. M. (1998) ‘Rapidly -Ex ploring Random Trees: a new tool for path planning’, Technical Report 98, 11 LaValle, S. M. (2006) Planning algorithms . New York: Cambridge University Press Schwartz, J.T. Sharir, M. (1983) ‘On the ‘piano movers'‘ Problem I. the case of a two -dimensional rigid polygonal body moving amidst polygonal barriers’, Communications on Pure and Applied Mathematics , 36(3), 345 – 398 SZanlongo, Köse, T. motion-planning/rrt-algorithms. https://github.com/motion-planning/rrt-algorithms. Consulted: 20/7/21 Taylor, CJ. Robotics: Computational Motion Planning. https://www.coursera.org/learn/robotics-motion- planning/home/welcome. Consulted: 23/6/21
210
Made with FlippingBook interactive PDF creator