In this paper, we consider the problem of using a drone to collect information within orchards in order to detect bugs. An orchard can be modeled as an aisle-graph, which is a regular data structure formed by consecutive aisles where trees are arranged in a straight line. For monitoring the presence of bugs, a drone flies close to the trees and takes videos and/or pictures that will be analyzed offline. As the drone's energy is limited, only a subset of locations in the orchard can be visited with a fully charged battery. Those places that are most likely to be infested should be selected to promptly detect the parasite. We study the budgeted constrained position selection problem in the orchard from an algorithmic point of view. We present the Single-drone Orienteering Aisle-graph Problem (SOAP), a variant of the well-known orienteering problem where the finite resource is the drone's battery. We first show that SOAP can be optimally solved for aisle-graphs in polynomial time. However, the optimal solution is not efficient for large orchards. Then, we propose two efficient heuristics that work even for large (orchard) instances. After a thorough analysis of the proposed solutions, we evaluate their performance by simulation experiments on both synthetic and real data sets.

Drone-based Optimal and Heuristic Orienteering Algorithms Towards Bug Detection in Orchards / Sorbelli, FB; Coro, F; Das, SK; Palazzetti, L; Pinotti, CM. - ELETTRONICO. - (2022), pp. 117-124. ((Intervento presentato al convegno 18th Annual International Conference on Distributed Computing in Sensor Systems, DCOSS 2022 [10.1109/DCOSS54816.2022.00032].

Drone-based Optimal and Heuristic Orienteering Algorithms Towards Bug Detection in Orchards

Palazzetti, L
;
2022

Abstract

In this paper, we consider the problem of using a drone to collect information within orchards in order to detect bugs. An orchard can be modeled as an aisle-graph, which is a regular data structure formed by consecutive aisles where trees are arranged in a straight line. For monitoring the presence of bugs, a drone flies close to the trees and takes videos and/or pictures that will be analyzed offline. As the drone's energy is limited, only a subset of locations in the orchard can be visited with a fully charged battery. Those places that are most likely to be infested should be selected to promptly detect the parasite. We study the budgeted constrained position selection problem in the orchard from an algorithmic point of view. We present the Single-drone Orienteering Aisle-graph Problem (SOAP), a variant of the well-known orienteering problem where the finite resource is the drone's battery. We first show that SOAP can be optimally solved for aisle-graphs in polynomial time. However, the optimal solution is not efficient for large orchards. Then, we propose two efficient heuristics that work even for large (orchard) instances. After a thorough analysis of the proposed solutions, we evaluate their performance by simulation experiments on both synthetic and real data sets.
18th Annual International Conference on Distributed Computing in Sensor Systems, DCOSS 2022
18th Annual International Conference on Distributed Computing in Sensor Systems, DCOSS 2022
Sorbelli, FB; Coro, F; Das, SK; Palazzetti, L; Pinotti, CM
File in questo prodotto:
File Dimensione Formato  
DCOSS_2022___Orienteering_on_Orchards_with_Drones.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: DRM non definito
Dimensione 779.55 kB
Formato Adobe PDF
779.55 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2158/1288886
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact