Gsoc 2018 idea for path optimization

Hello,
I am student currently studying software engineering in third year. I am very motivated and excited towards adrupilot because i am currently using it in my capstone project. I am currently working on project by using autonomous quad-copter for helping farmer to identify diseases in the crop. So the biggest problem i encountered is the battery or flight time. So i wanted to implement a module in adrupilot to minimize and optimize the route of flight over a given area. This would save time and energy of quadcopter as well. This can be done with the help of convex hull algorithm and optimization using genetic algorithms. So kindly review my idea and tell me about further working and making proposal on it.

1 Like

Is the optimization process must be executed on the quadcopter or can it be executed on the ground control station? If the latter is true, then you can use the python scripting feature on mission planner; http://ardupilot.org/planner/docs/using-python-scripts-in-mission-planner.html
You can make a waypoint/mission generator or even mission modification mid flight.

more particularly talking about check this research paper http://ieeexplore.ieee.org/document/7502538/?reload=true on the optimized path for multi-copters. This can be used in variety of applications.

Based on the paper, I think you can start from the Survey Grid module on Mission Planner. It is used to generate waypoints for a survey/mapping mission; https://diydrones.com/profiles/blogs/how-to-plan-missions-for-aerial-survey
This is assuming that the path optimization is executed before the flight (like in the paper)

I have read the documentation of Survey Grid module on Mission Planner. Survey Grid automatically create waypoints and camera control commands to survey a specified polygon.But what i understood was that it does not provide optimized path for the polygon. So i want to optimize the path so the duration of flight can be minimal.

Yup. Maybe you can start by branching survey grid and add a module in the waypoint generator to optimize the flight time/path length (Survey grid as starting point).


This is sample code that i used to optimize the simple function and calculate its maximum or minimum value. In similar way the the path by waypoint generator can be optimized.

Sounds interesting and looking forward to your proposal.

I have a preference for having as much as possible implemented on the drone itself instead of in the ground stations. The reason is that the ArduPilot team has more control over the code on the drone and putting it on the drone means that all users can use the feature, regardless of which ground station they chose.

Of course, the algorithms may not fit on a Pixhawk but we have other more powerful flight controllers (like the Emlid Edge) and Companion Computers are also a good way to add processing power to the drone.

It’s great to hear you’re already using ArduPilot. Definitely highlight that in your proposal.

I am glad to hear that. I was preferring ground station than on drone because it will be more easier to select areas and way points on ground station and our path is more better understandable and visualizer by user. As you are saying that ArduPilot team has more control over the code on drone, Please guide me how i can put it on drone and give me some hint or starting point for it or Is it ok to remain at ground station.

I think for us to mentor properly, the solution needs to be mostly on the drone. We simply don’t have mentors familiar with the ground stations (mission planner, etc) so I’m afraid a lot of work on the ground stations might not end up getting merged into master and the effort would be lost.

To do path optimization on the drone itself, it would probably be best to start by building it into auto mode. Copter’s auto mode is implemented in the mode_auto.cpp and commands_logic.cpp files. Also the AP_Mission library holds the points uploaded by the user. I don’t really know much about the algorithms you’re proposing but perhaps it requires iterating through the user specified waypoints and then perhaps when the vehicle is flying between two points it doesn’t fly a straight path?

The code for flying a path between two waypoints is in our AC_WPNav library. It’s actually surprisingly complex to fly between two waypoints smoothly and accurately. Don’t want to scare you but just wanted to highlight that understanding how it works now will take some effort (but the mentors including me are here to help).

@rmackay9 I understand your viewpoint and problem completely. I have studied the information provided by you regarding porting my method from ground station to drone itself. Here is what i found regarding these:-
1.mode_auto is used for navigating the copter according to a predefined mission script which includes the waypoints and other jobs to do like triggering camera at particular point.
2.Ap_mission is the library which holds the waypoints which copter has to follow during the mission and all the other information regarding mission.These waypoints are given by the user.
3.Ac_wapnav is the library which is is used to navigate the copter between two waypoints provided in ap_mission library.
(guide me if i am wrong in something)
Here is what can we do to port as much possible code on the drone itself:-
Instead of giving waypoints for navigation the user gives the end point of the area which he has to map . Then a matrix of area is made from this points which will cover all the area. Then optimization using Genetic Algorithms runs in order to find optimal path.obviously the special obstacles and considerations like tall buildings and vegatation area also considered, this path will be in the form of distinct waypoints which contains all the information. so these waypoints are synced with ap_mission library and in used in auto mode to navigate in these points and collect required information.
Please review these and guide me for further improvements and considerations.

1 Like

@umarpreet1,
That sounds pretty good. I definitely think the user just giving start and finish is good and having the algorithm come up with a list of intermediate waypoints is also really good. I think it would be best if all those intermediate points weren’t stored as mission commands but instead just held in RAM (a bit like how the SmartRLT library works)… still,putting them into the mission as a first step would be fine.

This sounds really good. I see your draft proposal is in so I’ll review it in the next day or so.