algorithm for support structures using RRT and PRM.

TO derive new algorithm for support structures for 3d-printing in constrained space using random sampling techniques like RRT and PRM.

The motivation for combining Rapidly-exploring Random Tree (RRT) and Probabilistic Roadmap (PRM) algorithms stems from the need for efficient and reliable support structures in complex 3D printing tasks, especially those with overhanging features. Designing effective support structures requires navigating a large configuration space to ensure collision-free points while also optimizing the connections between these points for stability and minimal material usage. RRT is particularly advantageous due to its rapid exploration of high-dimensional spaces through random sampling, which allows it to quickly identify collision-free points in irregular and obstacle-rich environments, making it well-suited for discovering initial support points. However, RRT’s random nature can sometimes lead to longer, less optimal paths between support points, which is where PRM becomes valuable.

By incorporating PRM, we leverage its ability to construct a detailed roadmap of the free space, which provides efficient and shorter paths between support points, enhancing the overall stability of the structure. PRM's pre-computed roadmap offers a quick and optimized path-finding capability, allowing us to connect various support points efficiently, which is crucial for reducing material usage and improving the strength of the supports. Combining RRT’s exploration and PRM’s path optimization ensures that the support structure meets the dual goals of structural reliability and material efficiency, creating a robust support network that is capable of supporting complex overhanging features in 3D printing.

Algorithm: Support Structure Generation for F-Shape Using RRT and PRM

Input

1. Map: A binary occupancy map representing free space and obstacles.

2. Start and Goal Points: Defined starting position (`startPose`) and ending target position (`goalPose`) for the planning.

3. Obstacle Definition: An F-shaped structure that serves as the primary model around which supports will be planned.

4. RRT and PRM Parameters:

- For RRT:

- `MaxConnectionDistance`: Maximum distance allowed for each connection.

- `MaxIterations`: Limit for RRT growth.

- For PRM:

- `NumNodes`: Number of nodes for roadmap construction.

- `ConnectionDistance`: Maximum distance for connecting nodes in the roadmap.

Output

- Collision-Free Path: A path from the start to the goal avoiding obstacles.

- Support Points: Locations on the F-shape requiring support structures for stability during 3D printing.

- Bridge Points: Key points connecting segments that support overhanging parts of the F-shape.

Procedure

Step 1: Generate F-Shape Map (Define Obstacle Environment)

1. Create the Binary Occupancy Map:

• Initialize a binary map with specified dimensions.

2. Define Boundaries and Obstacles:

• Add boundaries around the edges of the map to represent the outer edges of the print space.
• Place obstacle blocks and segments within the map to represent the F-shape structure.

3. Display Map:

• Plot the map to confirm the obstacles are correctly defined and visually form an “F” shape.

Step 2: Initial RRT Planning for Support Points

1. Define Configuration Space and Bounds:

• Define allowable values for x and y positions, and angle for a Dubins state space, which restricts the turning radius.
• Set up the `startPose` and `goalPose` positions.

2. Create Dubins State Space and Validator:

• Define a state space with a minimum turning radius.
• Set up a validator with a small `ValidationDistance` to ensure collision checks along short segments.

3. Initialize RRT Planner:

• Set `MaxConnectionDistance` and `MaxIterations` to control RRT expansion.
• Run the RRT planner from `startPose` to `goalPose`.

4. Plot Initial RRT Path:

• Display the entire tree generated by RRT, showing connections and branches that avoid obstacles in reaching the goal.

Step 3: Define Points Requiring Support on F-Shape

1. Identify Support Points:

• Mark points on the F-shape where overhangs exist and support structures are necessary to avoid unsupported printing.

2. Plot Support Points:

• Highlight these support points on the map for a clear visual of support needs.

3. Define Bridge Points:

• Identify segments that span horizontally and add necessary bridge points to connect these segments to the base.

Step 4: Bridge Length Calculation and Support Requirement

1. Define Horizontal Segments for Bridge Points:

• Specify start and end points for each line segment in the F-shape that requires support.

2. Calculate Properties for Each Segment:

• For each line segment, calculate:

- `L_slope`: The slope of the line.

- `phi`: The angle of inclination.

- `L`: The total length of the segment.

3. Support Structure Requirement Check:

• For each line segment:

- If L_slope is less than 1, support structures are needed.

- Divide the segment into equal intervals for placing support points.

- Store these support points in arrays xn and yn for plotting.

Step 5: Iterative RRT Tree Data Integration

1. Connect Support Points with RRT Tree Data:

• For each support point in the list:

- Define the support point as a new start position.

- Use the RRT tree to find the nearest connection point for each support.

2. Store Connections:

• Save the coordinates of each connection.

3. Plot Connections:

• Draw connections from each support point to the closest point in the RRT tree, providing a visual confirmation.

Step 6: PRM Planning for Optimal Paths Between Support Points and Goal.

1. Inflate Map for PRM Planning:

• Copy and slightly inflate the map to account for clearance in the PRM path planning.

2. Initialize PRM Planner:

• Set `NumNodes` and `ConnectionDistance` parameters.
• Configure PRM planner with the inflated map.

3. Run PRM from Each Support Point to Goal:

• For each support point:

- Attempt to find a collision-free path to the goal.

- If a path is not found, increase `NumNodes` and retry.

- Save each path in `pathCell` for visualization.

4. Plot PRM Paths:

• Display the PRM connections from support points to the goal.

Step 7:Final Visualization of Paths and Supports

1. Plot Paths from Support Points to Goal:

• For each path in ‘pathCell’, plot the trajectory to show the PRM-generated route.

2. Display Final Connections:

• Overlay all paths, support points, bridge segments, and RRT paths on the map.

3. Validate and Confirm:

• Ensure all necessary support points have paths to the goal, and there are no unsupported segments in the F-shape.