Skip to content

Latest commit

 

History

History
76 lines (46 loc) · 4.31 KB

writeup_template.md

File metadata and controls

76 lines (46 loc) · 4.31 KB

Project: 3D Motion Planning

Quad Image

Required Steps for a Passing Submission:

  1. Load the 2.5D map in the colliders.csv file describing the environment.
  2. Discretize the environment into a grid or graph representation.
  3. Define the start and goal locations.
  4. Perform a search using A* or other search algorithm.
  5. Use a collinearity test or ray tracing method (like Bresenham) to remove unnecessary waypoints.
  6. Return waypoints in local ECEF coordinates (format for self.all_waypoints is [N, E, altitude, heading], where the drone’s start location corresponds to [0, 0, 0, 0].
  7. Write it up.
  8. Congratulations! Your Done!

Rubric Points

Here I will consider the rubric points individually and describe how I addressed each point in my implementation.

Writeup / README

1. Provide a Writeup / README that includes all the rubric points and how you addressed each one. You can submit your writeup as markdown or pdf.

You're reading it! Below I describe how I addressed each rubric point and where in my code each point is handled.

Explain the Starter Code

1. Explain the functionality of what's provided in motion_planning.py and planning_utils.py

planning_utils contains the code needed to run A* on a grid representation of the environment. motion_planning contains most of the same movement logic as backyard_flyer, with the important addition of the planning state and the plan_path method. Currently, plan_path has a lot of the boilerplate code necessary, but sets the goal distance as 10 metres north and east of the current position. In the path created (which doesnt have to go through obstacles), it sets every path point as a waypoint and sends that path plan.

Implementing Your Path Planning Algorithm

1. Set your global home position

Here students should read the first line of the csv file, extract lat0 and lon0 as floating point values and use the self.set_home_position() method to set global home. Explain briefly how you accomplished this in your code.

I used open() and read the first line of the file, parsing the string into a lat,lon tuple

2. Set your current local position

Here as long as you successfully determine your local position relative to global home you'll be all set. Explain briefly how you accomplished this in your code.

I called the global_to_local function

3. Set grid start position from local position

This is another step in adding flexibility to the start location. As long as it works you're good to go!

Simply added local position to the start point

4. Set grid goal position from geodetic coords

This step is to add flexibility to the desired goal location. Should be able to choose any (lat, lon) within the map and have it rendered to a goal location on the grid.

I set a position roughly above Battery and clay, but these values are easily changed

5. Modify A* to include diagonal motion (or replace A* altogether)

Minimal requirement here is to modify the code in planning_utils() to update the A* implementation to include diagonal motions on the grid that have a cost of sqrt(2), but more creative solutions are welcome. Explain the code you used to accomplish this step.

I used a 2D Voronoi graph crunstructed based off the target altitude instead. In order to accomplish this, I pulled a lot of the code from the exercises and made minor modifications. The cost is the distance between points, and the provided A* algorithm is replaced with graph-based variant

6. Cull waypoints

For this step you can use a collinearity test or ray tracing method like Bresenham. The idea is simply to prune your path of unnecessary waypoints. Explain the code you used to accomplish this step.

This no longer necessary with a graph based search

Execute the flight

1. Does it work?

It works!

Double check that you've met specifications for each of the rubric points.

Extra Challenges: Real World Planning

For an extra challenge, consider implementing some of the techniques described in the "Real World Planning" lesson. You could try implementing a vehicle model to take dynamic constraints into account, or implement a replanning method to invoke if you get off course or encounter unexpected obstacles.