Drone 3D Motion Plannning

(this is a partial video, see Video.mp4 for full video)

Objective

• Create a path from one point to another point, and create the path in 3D environment (a virtual city)
• Move a virtual drone to move along the path

Approach

• Applied graph to simplifiied the 3D continuous space into nodes and edges
  • First consider the obstacles in specified attitude
  • Then made edge and nodes based on Voronoi algorithm (as shown below)

• Then applied A* search algorithm to create the optimal path between nodes (the node cloest to start point and the node closest to goal point)
• This uses UdaciDrone API to control the drone

Result

• The drone could smoothly moved to the specified point (see video 'video.mp4')
• The A* search route planning was quick when using the graph, completed within a second. This is opposite to using grid, that took minutes.

Further Improvements

• The micro routes between nodes are not always optimal, since nodes are located at the center between obstacles. To further opimize the route, smoothing should be considered.

How to run

• Download the Simulator from this repository.
• Set up Conda envrionment seeing this repository and activate it ('source activate fcnd')
• Run the simulator and choose Motion Planning environment
• Run following python motion_planning.py --grid n