Optimizing workspace division for multi-UAV systems

Abstract

(English) With the advance of UAV-related technology using several drones in the context of a single mission becomes more and more common. New problems and challenges appear as a result.

When analyzing research works on using systems of multiple UAVs we could notice that the majority of the authors provided few details on how the path planning or workspace division was done. Out of those researchers who mentioned it, some pointed out that the planning or area partitioning was performed by hand. Other researchers presented brief ideas of algorithms with too little information to implement it. In other research works very brief lists of algorithms were given that could solve the problem. And even in those cases when the information on the algorithms was provided, the algorithms themselves did not have any freely available implementations.

The purpose of this thesis is to fill the gap in the area of workspace division in order to facilitate the usage of systems consisting of multiple UAVs.

In order to accomplish the aforementioned goal, in this thesis, we performed analysis of the literature on the subject of workspace decomposition between multiple robots and UAVs in particular. As it will be shown later, there are almost no research works published in this area.

We implemented two state of the art algorithms and shared information on how we achieved that and what were the aspects that needed clarification or could be improved. We analyzed thoroughly the produced results, and propose improvements to the algorithm that yielded better results. And finally, we proposed, implemented, and analyzed two alternative algorithms based on the obtained experience. These algorithms outperformed the algorithm from the literature in terms of quality of the resulting partition. One algorithm solves the partition problem for convex polygons and the other one solves the partition problem for non-convex polygons. Finally, we have summarized a set of open problems that could be solved in future.

(Català) Amb l'avenç de la tecnologia relacionada amb UAVs, l'ús de múltiples drons en el context d'una única missió és cada cop més habitual. Com a resultat apareixen nous problemes i reptes.

Analitzant els treballs de recerca sobre l'ús de sistemes de múltiples UAVs, vam observar que la majoria dels autors proporcionaven pocs detalls sobre com s'havia realitzat la planificació de la trajectòria o la divisió de l'àrea de treball. D'aquells investigadors que ho esmentaven, alguns van assenyalar que la planificació o la partició de l'àrea es feia a mà. Altres investigadors presentaven idees breus d'algorismes, però informació insuficient per implementar-los. En altres treballs de recerca es van donar llistes molt breus d'algorismes que podrien resoldre el problema. I fins i tot en aquells casos en què es va proporcionar la informació sobre els algorismes, els mateixos algorismes no tenien cap implementació disponible lliurement.

L'objectiu d'aquesta tesi és omplir el buit en l'àrea de divisió de l'espai de treball per tal de facilitar l'ús de sistemes formats per múltiples UAVs.

Per tal d'aconseguir l'objectiu esmentat, en aquesta tesi, hem realitzat una anàlisi de la literatura sobre el tema de la descomposició de l'espai de treball entre múltiples robots i UAV en particular. Com es mostrarà, pràcticament no hi ha treballs de recerca publicats en aquest àmbit.

Hem implementat dos algorismes d'última generació i hem compartit informació sobre com ho hem aconseguit i quins eren els aspectes que calia aclarir o es podrien millorar. Hem analitzat a fons els resultats produïts i hem proposat millores a l'algorisme que han donat millors resultats. Finalment, vam proposar, implementar i analitzar dos algorismes alternatius basats en l'experiència obtinguda. Aquests algorismes van superar l'algoritme de la literatura en termes de qualitat de la partició resultant. Un algorisme resol el problema de partició per a polígons convexos i l'altre soluciona el problema de partició per a polígons no convexos. Finalment, hem resumit un conjunt de problemes oberts que es podrien resoldre en el futur.