Polygon-based Random Tree Search Algorithm for a Size-Changing Robot

Fig. 1.  Summary figure of the study: (a) The octahedron shape VTT; (b) Path planning through the narrow passage; (c) Locomotion simulation through the narrow passage.

We proposed the Polygon-based Random Tree (PRT) search algorithm for path planning of the Variable Topology Truss (VTT) system [1]. PRT search algorithm finds the path to the goal by generating the series of support polygons. In the previous study, we constrained the size of the support polygon within a certain range. However, VTT can change its volume a lot by using spiral zipper actuators. By using this feature, VTT can squeeze into a narrow area by reducing its size, and take a large step to increase efficiency in a wide area by increasing its size. This study introduces the Polygon-based Random Tree search algorithm with varying support polygon sizes (PRT-V). Fig. 1 summarizes the PRT-V algorithm. 

Fig. 2. Process of analyzing a workspace: (a) Given workspace; (b) A Voronoi diagram is generated; (c) The rough trajectory to the goal is generated by finding the shortest path on Voronoi diagram. (d) Stopover points are selected based on the minimum distance from obstacles.

The algorithm finds stopover points and determines the desired size of the support polygon at the point. To find proper stopover points, we used a Voronoi diagram to figure out where is the important points. A Voronoi diagram is used for generating a rough trajectory from the initial point to the goal point. Stopover points are determined from bottleneck points along the Voronoi path. The selection criteria find local minima or maxima based on the distance to obstacles. Fig. 2 shows the stopover point determination process by using the Voronoi diagram. The stopover points are denoted as red dots.

Fig. 3. Path planning simulation. For workspace 1: (a) Voronoi path and stopover points; (d) Desired support polygons. For workspace 2: (b) Voronoi path and stopover points; (e) Desired support polygons. For workspace 3: (c) Voronoi path and stopover points; (f) Desired support polygons.

We applied the PRT algorithm to generate the support polygon trajectories between stopover points. Instead of maintaining the support size, we revised the algorithm to slowly change the size of the support polygons step by step to reach the required size at the next stopover point. To figure out the performance of the PRT-V algorithm, we conducted path planning simulations in three workspaces: Workspace 1 with 40 randomly generated circular obstacles; Workspace 2 with a zigzag-shaped narrow passage; Workspace 3 with two separate narrow passages. The path planning simulation results are presented in Fig. 3. The PRT-V algorithm could successfully generate support polygon paths in three workspaces. Using the non-impact rolling locomotion as we did in the previous study [2], we conducted locomotion simulation through the generated support polygon trajectory. The simulation was successful and the snapshots of the simulation in workspace 2 were presented in Fig. 4.

Fig. 4. Snapshots from locomotion simulation through the narrow passage: (a) Moving in a large space; (b) Retracting size to go into a narrow passage; (c) Increasing size again after the passage.

[1] S. Park, J. Bae, S. Lee, M. Yim, J. Kim, and T. Seo, “Polygon-based random tree search planning for variable geometry truss robot,” IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 813–819, 2020.

[2] S. Park, E. Park, M. Yim, J. Kim, and T. Seo, “Optimization-based nonimpact rolling locomotion of a variable geometry truss,” IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 747–752, 2019.