Ardupilot Gsoc 2018 - Path Planning Project

Google Summer of Code
1

I am Naveen T R, 2nd semester MS student at Ohio State University (CSE). I came across this interesting project of Path Planning for Rovers and multicopters.
I am working on my approach to solve the problem and my proposal.
Few things I wanted to clarify (if my assumption/thinking is wrong):-

  1. The initial list of obstacles given to the user would be static obstacles.
  2. As we start our journey to destination, we can come across static or dynamic objects. We need to take an action appropriately and proceed towards our destination. (We need to consider multiple dynamic objects which might be traveling towards/obstructing our path to destination. Solving this considering all use-case might be challenging).
  3. There is a dependency of completing “Object avoidance improvements for multicopters” by adding occupancy grids using OctoMap. Path planning for multicopter requires this functionality. Can we take up both the projects?
    I believe for Path Planning in multicopters, if OctoMap is given as input that should be sufficient to proceed with implementing the solution.
  4. I have cloned the codebase and I was looking through the code which I can reuse to build this module. I felt testing would be challenging thing as part of this project. I believe we will be using SITL for testing our code changes rather than using the actual hardware devices.

Thanks for your consideration and time.

1 Like
2

An algorithm to perform path planning would consist of :-

  1. Global Path Planning: Finding a route from source to destination taking into account all static/given information.
  2. Local Path Planning: This is used to avoid obstacles within a close vicinity of the entity.
  3. A* search algorithm can be used to find the most optimal route from source to destination.

Path Planning Operation is an efficient planning operation which needs to consider the following points:-

  • There shouldn’t be any overlapping paths.(This may lead to deadlock i.e our device getting struck indefinitely)
  • The device must efficiently avoid all the obstacles in the region.
  • We will be using straight line motion to find optimal path(Straight line is specified in the problem statement).

NOTE:- I came across another alternate algorithm rapidly exploring random tree(RRT) which is widely used in autonomous robotic motion planning. An RRT grows a tree rooted at starting by randomly choosing samples from sample space. As each sample is drawn, a feasible connection is attempted between it and the nearest state in the tree.

IMPORTANT:

  • One of my major worry is whether a device (vehicle- rover or multicopter) would get stuck and cannot find a route , thereby never moving out. This may be due to inefficiency to find a way out or due to mechanical factors. When a vehicle is struck, an appropriate alarm/trigger should be sent to user. Some of these cases in my mind are as follows: vehicle’s wheels are stuck & it’s not moving, weak power/battery in our vehicle, loose track of sensors etc.