Project: 3D Motion Planning

---

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

These scripts contain a basic planning implementation that includes...

And here's a lovely image of my results (ok this image has nothing to do with it, but it's a nice example of how to include images in your writeup!)

Here's	A	Snappy	Table
1	highlight	bold	7.41
2	a	b	c
3	italic	text	403
4	2	3	abcd

Implementing Your Path Planning Algorithm

1. Set your global home position

This is accomplished by reading the colliders.csv by using the csv python package and extracting the first line into lattitude and longitude variables.

And here is a lovely picture of our downtown San Francisco environment from above!

2. Set your current local position

Drone local location is determined by making a translation from current global to local location using the global_to_local() function.

Meanwhile, here's a picture of me flying through the trees!

3. Set grid start position from local position

Grid start position is set by offsetting the current position with the start position rather than the map center at line 153.

4. Set grid goal position from geodetic coords

This step is to handle random grid goal locations. This is achieved by continually setting the grid goal in an iterative loop until the drone reaches the desired goal location.

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

The diagonal motion is achieved by setting diagonal directions(NORTH_WEST,NORTH_EAST,SOUTH_WEST,SOUTH_EAST) by offsetting the cost of action in the tuple using numpy sqrt function in the Action class.

6. Cull waypoints

For this I used the ray tracing method with Bresenham algorithm. The idea is simply to prune the paths of unnecessary waypoints through free space.

Execute the flight

1. Does it work?

It works great!