Key points are not available for this paper at this time.
Cet article considère le problème de permettre l'exécution persistante d'une tâche multi-drone sous des limites énergétiques. Les drones se voient attribuer un ensemble de lieux et leur tâche est de garantir qu'au moins un drone sera présent, par exemple pour la surveillance, sur chaque lieu à tout moment. En raison des limitations énergétiques, les drones doivent être remplacés de temps en temps et revenir à la maison pour que leurs batteries puissent être remplacées. Nos objectifs sont d'identifier le nombre minimum de drones de rechange nécessaires pour accomplir la tâche sans décharger les batteries, et de fournir une stratégie de remplacement de drones. Nous présentons une procédure efficace pour calculer si un drone de rechange est suffisant pour une tâche donnée et proposons une stratégie de remplacement optimale. Si plus d'un drone est nécessaire, nous visons à trouver le nombre minimum de drones de rechange requis, et étendons la stratégie de remplacement à plusieurs drones de rechange en introduisant une nouvelle variante de Bin-Packing, appelée Bin Maximum Item Double Packing (BMIDP). Étant donné que le problème est vraisemblablement difficile sur le plan computationnel, nous fournissons un algorithme d'approximation glouton de premier ajustement pour résoudre efficacement le problème BMIDP. Pour la version hors ligne, dans laquelle tous les lieux sont connus à l'avance, nous prouvons une limite supérieure du facteur d'approximation de 1,5, et pour la version en ligne, dans laquelle les lieux sont donnés un par un, nous montrons par le biais de simulations approfondies que l'approximation donne un facteur moyen de 1,7.
Hartuv et al. (Mon,) ont étudié cette question.