Formation Flight Path Planning Algorithm

Подписаться 2,2 тыс.

Просмотров 6 тыс.

50% 1

A swarm of aircraft path plan to take advantage of the efficiency gain from flying together as a formation. I first explain how birds take advantage of one another to reduce induced drag and the challenges associated with applying this method to aircraft today. I then explain why it is difficult to predict formation flight paths and the algorithm I came up with to solve it. I then show the python function working with pygame and finish off with some conclusions about how an algorithm like this could be useful to implement formation flight swarm behavior in the future.
Thanks for watching! If you have any questions about my implementation or otherwise, feel free to ask. I glossed over a lot of details for the sake of brevity.
Sources:
1: • Birds gliding through ...
2: Lissaman PB, Shollenberger CA. Formation flight of birds. Science. 1970 May 22;168(3934):1003-5. doi: 10.1126/science.168.3934.1003. PMID: 5441020.
3: • WW1 Flight School - Un...
4: www.air-and-space.com/Wing%20...
5: • Airbus Commercial Airc...
6: • Zipline Keynote 2023 |...
7: • The AutoLoader & curbs...
8: • Exploring the Cutting-...
9: • A Unique RC Aircraft! ...
10: • Chasing the VTOL Tail-...
11: • Watch how Amazon is pr...
12: P. E. Hart, N. J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," in IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, July 1968, doi: 10.1109/TSSC.1968.300136.
13: Karaman, Sertac, and Emilio Frazzoli. "Sampling-based algorithms for optimal motion planning." The international journal of robotics research 30.7 (2011): 846-894.
Relevant Formation Flight Papers:
14: Xu, Jia, et al. "Aircraft route optimization for formation flight." Journal of Aircraft 51.2 (2014): 490-501.
15: Shen, He, et al. "ENERGY-SAVING FORMATION FLIGHT."
16: Xu, Jia, et al. "Aircraft route optimization for heterogeneous formation flight." 53rd AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference 20th AIAA/ASME/AHS Adaptive Structures Conference 14th AIAA. 2012.
17: Mahboubi, Zouhair, et al. "Camera based localization for autonomous UAV formation flight." Infotech@ Aerospace 2011. 2011. 1658.

Наука

Опубликовано:

27 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 35

@jeffreychen1191 Год назад

This was fascinating. You should explore what happens when the efficiency increases as a function of how many drones are flying together (instead of just fixed at 70%). My rough hypothesis is that when birds fly together, it is a bit like tricking the air to think there's just one bird with a very high aspect ratio wing. So the more birds, the larger the equivalent big-bird aspect ratio, and the higher the collective L/D. Implementing this might motivate the algorithm to prefer formation flying even more.

@peterryseck Год назад

Thank you! Yeah exactly, and there’s a lot more aspects to explore here such as the leader bird switching positions with others and coordinating that switch based on who needs to fly furthest.

@AerialWaviator Год назад

A fascinating problem to explore. There are many details to consider when comes to real world application. For example with actual aircraft the flight path lengths will vary from the ground path lengths due to wind. Flying into a headwind will make effective flight paths longer, vs shorter (time) for paths that align with the wind. Other details like how the additional aircraft are position relative to the first can vary based on speed and design and weight of an aircraft. No complaints, just realizing the real world complexity. Love the visualizations and the detailed explanations.

@mattynov Год назад

As always, this is great work and fantastic, clear technical communication 👍🏻

@peterryseck Год назад

Thanks for the kind words and support 😊

@hagenoneill9142 Год назад

Based on your previous videos, id suggest using ROS2 + PX4 instead of Ardupilot to code this. It's a bit steeper of a learning curve but its way better maintained than Ardupilot so you will have less headaches!

@DathCoco 20 дней назад

would be interesting to have a more dynamic approach where the drone will check if there is a drone in the area with a similar flight path. Both drones would need to ad hoc decide if the path adjustments would be worth to fly together. This would have the effect that there could be multiple rendezvous and breakup points per flight. For this I'd write the algo in a way that every 'plane' would build the optimal path along some nodes and whenever there is a 'plane' nearby the middle path of both will be calculated and compared against the optimal path. This could be done in a loop for N waypoints (N < remaining nodes in flight path) to generate the optimal path.

@DathCoco 20 дней назад

this approach has the benefit of being closer to a real world scenario where not every plane would have to start and stop synchronised

@thirtythreeeyes8624 Год назад

I see this becoming a thing with kamikaze drones flying in flocks to increase the loiter time and have them break off as needed.

@ThereAreNoHandlesLeft Год назад

Don't give them ideas!

@angelorondini5835 Год назад

They might be easier to shoot down though that way

@a0abes Год назад

since you allow for longer distance travelled to increase efficiency, aren't there some other options that should be considered for more optimal routing ? (realizing that complexity might explode). The thoughts below revolve around scenarios where a formation flight might have occurred but for slight mismatch in timing when passing over a possible randevou point. This can be ""corrected"" by a) varying speed - drone (a) should slow down, so the drone (b) can catchup with it b) delayed or staggered departure - drone (a) should take off slightly after (b) so they coincide at the right point and time

@peterryseck Год назад

Good questions! Yes there are definitely other factors to consider which makes the problem explode in complexity/computational expense which I've simply chosen to ignore as a result. For instance, flying fast will require greater energy/unit of distance vs. flying slow, so the factor of energy consumption in relation to scheduling is not something I chose to consider, I think it could be important depending on the exact set of conditions/start/end points. Another thing I chose to ignore, environmental factors like wind direction might influence the direction of flight and might cause aircraft to join one another faster should they need to travel upwind.

@plusmartini Год назад

Did you also make the amount of cost saving change depending on the amount of aircraft in formation? What if the aircraft take off at different times ? What other applications do you have in mind? I’m a robotics engineer with MSc in drone design, my dissertation is about unmanaged, unmanned battery swapping landing platforms for vtol UAVs. What if you have “refuel stations” spread across the region?

@peterryseck Год назад

Thanks for the good questions! I did not change the cost saving with number of aircraft, but the relative energy saved per aircraft and their relative position with other aircraft isn't as significant and assuming they all save the same amount of energy is a decent approximation. Timing/scheduling was not something I spent much effort optimizing for here, would probably need data from amazon or elsewhere to understand the specifics on that. Lots of applications in DOD, medical delivery, package delivery, surveillance, radar avoidance, etc. Sounds like a fascinating thesis! Refuel stations would probably only be needed if the range required to deliver a package is greater than the vehicle's independent range or formation range. If there were refuel locations on the map, it would be another metric to check for when calculating the final paths. So I could see it working similarly to other start/end locations, just with a different set of considerations.

@randomstatements8034 10 месяцев назад

Hi, great video! Is this script available anywhere for download and use with in own projects?

@peterryseck 10 месяцев назад

Thanks a bunch :) Not at this time, maybe I'll clean it up and publish it to a public repo though!

@randomstatements8034 10 месяцев назад

@@peterryseck that would be awesome!

@martinsavc3202 Год назад

Lovely visualization, great video. One critique: I'm not sure your using RRT* effectively. The first pass, which seems to be the regular RRT* seems to have no affect. I'm not sure if I've missed something, but after the first pass you seem to only retain the points/nodes, and rerun RRT* again with a different setting. I assume you could just select nodes at random, without any pathing calculations, and run the second pass. As for the second pass, the configuration seems a bit suspicious to me. Since you don't limit the search radius, doesn't this degenerate the RRT* to a more basic search algorithm? I'm not an expert in pathing algorithms though, I'm sure I missed some important points. Correcting my ignorance would be most welcomed.

@peterryseck Год назад

Thanks! Good questions, Yes I could skip the first pass and just increase the neighborhood radius, that was just an artifact of me figuring out how to make the algorithm work as I worked on it. The second pass is still running RRT*, the only difference is that I increased the neighborhood radius to reconnect new nodes. If I limited it, the paths between nodes would be unnecessarily discontinuous. The downside is that this is a more costly approach, because when a new node is placed on the map, it checks new paths with all the other nodes, not just a few near it.

@jcasaubon Год назад

I assume the leading bird expends more energy then the trailing birds. But is there an understanding on birds energy expenditures between leading bird and last bird?

@peterryseck Год назад

There is research on this and it does vary per bird, not sure how well it is understood though.

@jcasaubon Год назад

@@peterryseck great I’ll look into it thanks. The reason I ask is because it probably makes sense to rotate planes to rotate the heavy work/ expenses. I can imagine a world where multiple companies would want to join in formation but also share costs.

@sandmaster4444 Год назад

Did both drones get the 30% benefit or only n-1 of a set of n flying together as the leader doesn't get any benefit. The omniscient algorithm then has to direct per the greater good rather than individuals coordinating for personal gain (game theory stuff). Cycling leaders may affect the willingness to coordinate though. Very interesting idea!!!

@peterryseck Год назад

Thanks!! Good question, in this case I applied 30% benefit to all the drones as an approximation. Past research suggests the leader bird does get some benefit from flying with other birds but it's less significant. So in the case of 2 drones, we could assume a true benefit of 15% per drone assuming they alternate positions. To your latter point, yes, there are some interesting decisions that I had to make based on whether I wanted to help the entire swarm or help individual drones. For instance, when drones join together, I calculate their collective cost by calculating the norm rather than the sum, as I want a somewhat even distribution to benefit the system on a per drone basis.

@NicholasRehm Год назад

But, do you know why bird formations are sometimes asymmetric?

@peterryseck Год назад

Good question, doesn't seem like anyone has figured that out from my review of past research. I'm not sure there is any aerodynamic performance benefit to one vs. the other, perhaps it is just more convenient to fall in line closest to whichever side they're already on or they just prefer one side similar to the way we are right vs. left handed. I'll go ask a bird next time I see one

@NicholasRehm Год назад

Actually it’s because there’s more birds on one side than the other

@sandmaster4444 Год назад

@@NicholasRehmI love this joke!!! Especially when told to engineering/technical folks!

@peterryseck Год назад

🙄

@admercs Год назад

@@NicholasRehmBrutal

@henristievenard199 Год назад

Lot of work, nice video, superb theory...built on sand. The position where to fly in close formation is difficult to find, will vary with speed and altitude and in addition, this will increase collision risk. And your figure, gain of 50 or 70% of fuel is far from being demonstrated. Even if the starting point (economy of energy) has still to be demonstrated and quantified by real measurement, nice 👍 job.

@peterryseck Год назад

Thanks! 70% cost saving is theoretical, I applied 30% saving in the examples I showed.

@teddy1135 Год назад

Buying a higher quality microphone is one of the best, easiest investments you can make

@kashifzaheer7804 2 месяца назад

I need to know more about formation flight path. How to keep distance between them to avoid collision by having single path in between goal and start state. can you share code? implementation