RTH - return by own tracks

[digitalentity]

Keep record of flight track and follow the same path when doing RTH

[stronnag]

This seems like an ambitious undertaking, and one that seems to require some magical heuristics to be usable. My typical use case is to fly randomly around my field for 15 minutes and then hit RTH to land the machine for me. I'd prefer (and so would my lipos) that the FC did not try to reverse this process.

I can see the use case for 'fly off into the blue yonder and come back avoiding the same obstacles that I manually avoided on the way out'. Intrigued to see how this can be implemented.

[oleost]

It's a great feature that of course needs to be user configurable where one chooses which kind of RTH procedure one want.

Different procedure fits different purposes of flying.

[digitalentity]

This obviously will be a configurable option. This feature was requested by long range FPV flyers (mostly airplane flyers) who fly in the woods or mountains - getting into failsafe behind a mountain would cause some bad things to happen when doing a usual RTH, however "fly the route backaward" is much safer in this case.

[Linjieqiang]

Great.Happy to see this feature.

[csurf]

I've long thought about this type of feature.

The way that I envisioned it was to have an algorithm that will detect large changes in course/altitude (eg, large climb from 'x' altitude to 'y' altitude, 90 degree course change, etc.) and then record a 'breadcrumb waypoint' whenever the course varies by some predefined amount. On the return trip in RTH mode, the plane would need to hit the breadcrumbs on the way back.

There would need to be some kind of user-configurable thresholds / course averaging in order to get an overall idea of 'where the plane is generally going', and possibly eliminate/combine overlapping or redundant waypoints. Also, RTH would need to be smart enough to avoid trying to fly toward breadcrumbs that have already been bypassed (eg., you're on your way back home and then engage RTH... If you're almost home when this happens, then you wouldn't want it to try to fly out to the last/furthest breadcrumb when you might have already surpassed all of the RTH breadcrumbs on the return voyage)

Not sure how complicated the math would need to be, but it could probably be simplified in some ways (eg, maybe we could disable it for POS hold mode, or, perhaps we could use a switch channel in order to let the pilot manually set the 'breadcrumb waypoints' for the return trip). Since this would mainly be used by long-range flyers, the flying patterns wouldn't be expected to be very erratic. IOW, the user would need to disable it for regular flying and enabling it for (long-range) flights with simple flight plans.

[digitalentity]

Yes, logic is going to be complicated but that's worth the effort.

[bk79]

a simple solution would be to fill the wp whenever the sticks are released, but of course there could be a huge number the limit of the wp and the use it as reverse mission, it could be a starting point and the logic could be developed to clean the waypoints (ex..not storing the wp which are close than 5m or less)

2017-01-17 11:56 GMT+01:00 Konstantin Sharlaimov notifications@github.com:

Yes, logic is going to be complicated but that's worth the effort.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/iNavFlight/inav/issues/962#issuecomment-273107153, or mute the thread https://github.com/notifications/unsubscribe-auth/ALSWiu-T9vnIy-Li1-F_V-UV2DL95wu6ks5rTJ56gaJpZM4LVOap .

[too-many-projects]

Maybe set a configurable distance value as the return waypoint generation limit. Eg. say set it for 50 meters, then when it gets more than 50 meters from the last stored return waypoint a new return waypoint is generated. This would give you your breadcrumbs for the trip. Then if RTH is triggered and RTH via breadcrumbs is set then it goes to the nearest return waypoint and then works it's way back down the list. That way if you had travelled out 500 meters from home and had flown back 250 meters when the RTH is triggered. Then the return waypoint at around the 250 meter point would be the nearest and it would return from there. It wouldn't retrace the entire trip back out to 500 meters from home.

[csurf]

just to add to @too-many-projects's suggestion..., a possible problem I can foresee is if the algo tries to choose a nearby breadcrumb that's 'behind' the current position... example:

• breadcrumbs are set every 50m
• plane is flying back home and has reached "248m-from-home" mark.
• since it's only 2m from the 250m waypoint, it circles around and tries to go to it (based on a 'get nearest waypoint' algo), when it should have actually tried to fly toward the 200m mark

so, I suppose we'd need a reliable way of picking the correct 'next' breadcrumb to avoid this issue.

I guess we could mark each waypoint as 'reached' if the plane hits them on the way back, but then we'd have to assume that the pilot will fly close enough to each breadcrumb on the return to consider them as being 'hit'

thoughts?

[too-many-projects]

Maybe in the calculation to get on the breadcrumb trail the nearest two RTH waypoints are found and then the nearest to home is selected. This should get the plane heading in the correct direction. I don't think there is a totally fail proof method of getting home using waypoints but depending on the circumstances and obstacles it may be better than a straight line or a retrace all your steps RTH. It would be up to the pilot to choose which method would work best for the flight.

[digitalentity]

For initial implementation I think we'll just re-track the path back. After initial implementaiton the algorithm of entering the return path can be further improved.

[night-ghost]

points reducing and loop removal algorithm in action https://www.youtube.com/watch?v=D5UGfn47i8U&feature=youtu.be

[digitalentity]

@night-ghost impressive! Is the algorithm open-source? How long will it take to do it's job on an 72 MHz ARM CPU?

[night-ghost]

times on logs are on STM32F103 on the same 72MHz. But no, I withdraw plans to make this library open-source because of this. But I can provide sources under NDA

[night-ghost]

original video without Youtube's glitches - here

[digitalentity]

@night-ghost you want to make a library that could be used in both INAV and APM?

Unfortunately neither we nor APM can link against any non-GPL software here, so we either have to re-implement your algorithm (which I might be able to do some day if you will allow it) or re-invent it.

[digitalentity]

Can the logic be made faster? 1-1.5ms is marginal and 2.5ms is certainly unacceptable without RTOS which we don't have here.

[night-ghost]

Unfortunately neither we nor APM can link against any non-GPL software

It means that you don't read The Story :)

Can the logic be made faster?

it is theoretically best algorithm for accuracy_ratio / time. It guarantees that the track does not deviate from the initial by more than epsilon. I can further minimize the standard deviation, but it takes time to increase threefold.

Moreover, the points reducing does not have quadratic or even a linear dependence on the number of points, eliminating loops has linear dependence.

In order to ensure accuracy it uses a lots of float calculations. So It should be used as low-priority thread so there are calls to yield() after each small operation and one tick don't more than 100uS. Moreover there is no enough memory in F1 so it is only for F3/F4: real track should have up to 5000 points or 40Kbytes of memory for track itself.

PS. In this video loops removing does ASAP. It can be changed to collect loops and remove them only on return or when memory near full, with the construction of a complete graph of links and finding the shortest path in it - which greatly improves return distance, but in that case there will be quadratic complexity and execution time up to some seconds, so this mode is only for companion computer.

[digitalentity]

It means that you don't read The Story :)

I've read the story and I understand your concerns about commercial licensing. But that's not how things go in opensource world. GPL explicitly prohibits linking with any closed source software. Both INAV and APM are under GPL, so no commercial license. Basically we have only one option - your library needs to be open source under GPL.

Moreover there is no enough memory in F1 so it is only for F3/F4: real track should have up to 5000 points or 40Kbytes of memory for track itself.

How frequent do you need base points to be? I'm planning on recording a track point i.e. each 100m or if heading changes considerably. I don't want to support more than 256 track points which should be enough for at least 25km track anyway.

So It should be used as low-priority thread so there are calls to yield() after each small operation and one tick don't more than 100uS.

I don't want to migrate to RTOS for this feature to happen so no yield() is possible. Something else will have to be done to make this work for INAV.

[night-ghost]

But that's not how things go in opensource world

It means there are two different worlds of open source, because in the world of kernel and quagga team does not require a complete redesign of good working library from a commercial product, offered as a gift. And for some reason in that world projects are not closed one after the other :)

How frequent do you need base points to be? I'm planning on recording a track point i.e. each 100m

every second, points filtered out if distance from last less epsilon. 100m is absolutely useless because if I turn by 90 gr on 50 meters from last point then on return UAV will move in 35 meters off original track. If I fly over mountain river having width 30 meters then result will be sad.

Discussed algorithm only memorizes cue points, and when memory full can increase epsilon until there is room for new points. So 5000 points enough for the pedestrian walks in the woods all day, and then the algorithm will bring back to home by the shortest way of your track. UAVS rarely uses so winding roads :) So epsilon can be 0.5meters - and UAV will successfully return by a narrow streets.

I don't want to migrate to RTOS

As I said some time ago, yield() can be realized even without RTOS, code was provided.

Something else will have to be done to make this work for INAV.

Our mission to offer - your to refuse. :D

[martinbudden]

@digitalentity , GPL code can link with non-GPL libraries. You have to be careful how you do it, but it can be done. Also, I think it is possible to resolve the yield issue with needing to convert to RTOS.

@night-ghost - we are in the process of doing the 1.6 release of iNav and don't want to add anything major to that at the moment. We are also quite busy on testing etc for 1.6, so can't really spend too much time looking at this. However once 1.6 has been released (target date is end of February), we can look at this in more detail.

[digitalentity]

@martinbudden, @night-ghost yes, I know it's possible. We have several choices here:

1. If we link dynamically - we have no issues in most cases (not an option for embedded system)
2. If we explicitly allow linking with a specific library in a exception clause in our license (see https://www.gnu.org/licenses/gpl-faq.en.html#GPLIncompatibleLibs)
3. If we re-license under a more permissive license.

Options 2 and 3 can be done only if all of the authors (in GPL sense) agree to modify the license - this will include all of the people listed in commit history if we have at least one line of their code left in our source tree.

[digitalentity]

Personally, I would propose to re-license INAV under Mozilla Public License (MPL).

MPL compatible with GPL meaning we won't have (a lot of) issues sharing the code with Betaflight, but MPL also allows linking against closed-source libraries which open a world of new possibilities.

Speaking of feature discussed here - MPL will allow us to have this feature available in official INAV binaries, without giving it out to the world to use. This is not entirely in open-source sense, but it will allow us to move forward faster.

EDIT: Did a quick check - we'll have to get permission to re-license of c. 100 people including TC, so, probably not an easy task

[night-ghost]

GPL don't require me to share sources for all world for free - it requires to give sources to legal owner of product when requested, may be with some small fee. And only to legal owner! And don't prevents to sell software - just see to RHEL.

[digitalentity]

In GPL sense anybody who gets the binary is a legal owner of the product. Once this person requests the code you are obliged to give it and you can't prevent that person from sharing the code.

I.e. you say "my library is GPL, but I can sell it to you for 1k$". I pay the money, get the library and ask "hey, where's the source code?". You give me the source code and I upload it to public repo on GitHub. You can't prevent this from happening.

[stronnag]

You would still require the consent of all copyright holders to relicence to MPL. Given the range of contributers (Alex in Paris, timecop el al), I doubt you could ever achieve this.

It would solve many problems if this capability ran on its own daughter board, communicating with the FC over a simple protocol. Then @night-ghost could sell his proprietary creation to all who wanted it, and we can continue to enjoy the freedom of free, GPL software.

[flounderscore]

@stronnag +1

[digitalentity]

I need to look at who are authors of the current code and whether this code is used at all. I figure the list will be down to a few dozen people in which case contacting them all might be doable.

A daughterboard will certainly solve many issues (with this feature and others). However I think re-implementing @night-ghost's algorithm might be possible in the long run.

I'll probably initially implement this feature in it's simplest form - retrace the whole route back. Then we'll see who will be using it and we might even have some math guy coming in and improving the logic.

[flounderscore]

I'm totally ob-board with @stronnag. I doubt that adding one feature that, as you say @digitalentity, warrants dropping GPL. Also, personally I still don't see how this approach is going to work (safely) in three dimensions.

[WaspFPV]

@flounderscore 3D is not necessary. In an outdoor environment, you could track the path in 2D for easier loop detection and finding a good path home, but remember the altitude of each point and make sure you always fly at least the altitude of the next and current waypoint. That only assumes you do not fly under anything. As a side note, I am against dropping GPL and using closed source code in iNav.

[digitalentity]

It's not dropping GPL as in "make closed source", it's dropping GPL as in "allow to use closed source components". But yes, one feature is probably not worth the effort.

I think initially it can still be a 2D approach - keep altitude as defined by configuration and only maintain a safe 2D path home. I even have an idea how to do it in O(nlog(n)) complexity.

[WaspFPV]

@digitalentity if we use closed source code, can we still compile our own binaries? Do we get the closed source code in object files?

[digitalentity]

@andre92, see my above comments - at the moment we can't link with closed-source libraries without either re-licensing or adding a licensing exception (both require collecting consent from 100s contributers)

[too-many-projects]

I think the chances of getting 100+ people to agree is very unlikely. Especially as the agreement is solely for the integration of closed source code. Is an algorithm for reducing redundant way points in a return path so rare? It sounds like a exercise that would be handed out in a computer science class. I am not saying that it is a trivial exercise but is it such a breakthrough that it could not be repeated by the open source community? The effort at getting those 100 people to sign off on the plan seems like it would take more effort than just creating an open source version of the way point reduction code. It also sounds like there is already differences of direction. eg. 2D versus 3D. Also wouldn't integrating closed source code cause more issues? What happens if the owner of the closed source code decides to drop support, doesn't fix bugs, won't add requested features, etc. If it is open source many minds can work on problems, features and improvements. Is this possible with closed source code?

[too-many-projects]

If there is no other options for a way point reduction RTH best path calculator then an external hardware module sounds like the best option. No licensing issues, no processor load issues, no memory issues etc. The external module would behave like an airborne ground station. It would collect positional information from the flight controller and in the event of a RTH situation it could feed the controller a flight plan for it to follow. That would probably allow implementation with minor changes to the flight controller software. Basically passing the RTH status through to the external module and allowing the external module to give it way points to follow even though it is in RTH mode. If for some reason the external module failed then the flight controller would just follow it's normal RTH process. This would also make the commercialisation of the external module and the embedded algorithm much easier. It would also allow different versions of the module to be developed, some suited to airplane flight some for in-building quadcopters and others for hiking or bushwalking etc.

[Jetrell]

Years later... I was wondering what happened to this request. An idea came to me of how to simplify this concept and still allow the basis of its need to be fulfilled.

The main purpose for this function is to get a model out of a tight spot when a failsafe or video loss occurs. So that really only means that the TrackBack points (GPS pos, Altitude and Heading) need to be at their highest resolution within a few hundred meters from the point where TrackBack is triggered.

The idea would be to - * Record each marker point according to the models Speed and Distance traveled. e.g.

• Speed < 20kph - Leave a marker every 5 meters
• Speed > 20kph and < 60kph - Leave a marker every 20 meters
• Speed > 60kph - Leave a marker every 50 meters

Then once the model has traveled >300 meters from the location where the last marker point that was recorded. I would note this reference in the program. Then after the model has traveled a farther 300 meters and TrackBack has still not been triggered in that distance. It would erase all markers in that previous 300meters, except for the first one. That way it would keep the marker points in order and limit the memory used. Plus this could also be expanded on, by erasing even more intermediate marker points along the trip, as the models flight distance or distance from home increase. This would eliminate most of the unnecessary flying all over the place when using this feature.

[breadoven]

Closed by https://github.com/iNavFlight/inav/pull/7988 ?