Motion Planning

In our project, we embarked on the challenge of piloting a starship through a complex map filled with both static and dynamic asteroid formations. To tackle this task effectively, we adopted a solution approach centered around Rapidly-exploring Random Trees (RRT*), a traditional algorithm in motion planning.

Our approach involved several key components:

1. Create Motion Primitives: At each timestep, we generated a set of motion primitives representing feasible actions the starship could take, such as velocity changes and directional adjustments.

2. KD-tree for Distance Computation: Utilizing a KD-tree data structure enabled efficient computation of distances between the starship’s current position and potential future states.

3. Box-Distance Measure for Caution: Given the dynamic and potentially hazardous nature of the environment, we employed a box-distance measure to ensure cautious navigation, accounting for the size and shape of both the starship and surrounding obstacles.

4. Collision Checking via Safety Certificates: Before executing any motion primitive, we rigorously checked for collisions using safety certificates, ensuring that the selected action wouldn’t lead to a collision with asteroids or other obstacles.

5. Optimal Path in RRT Graph*: Through iterative exploration and refinement, RRT* algorithm gradually constructed a graph representing feasible paths through the asteroid field, aiming to find the optimal trajectory while avoiding collisions.

6. Cost Function: To guide the selection of motion primitives, we defined a cost function that evaluated the desirability of each action based on factors such as distance to the goal, potential collisions, and fuel consumption.

7. Time Estimation for Motion Primitives: Each motion primitive was associated with an estimated time required for execution, allowing for more accurate planning and decision-making.

By integrating these elements into our simulation framework, we were able to successfully navigate the starship through the challenging environment, dynamically adjusting our trajectory to avoid collisions and reach the designated destination efficiently. Our project demonstrates the effectiveness of RRT* and associated techniques in enabling safe and optimal motion planning in complex, real-time scenarios.