% Exemple d'utilisation de la classe 'roadef' ------
% --------------------------------------------------

\documentclass{roadef_en}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{color}
\usepackage{makeidx}
\usepackage{tikz}
\begin{document}

% Le titre du papier
\title{A mixed-integer linear formulation for data collection from buried sensors with a drone}

% Le titre court
\def\shorttitle{Short title}

% Les auteurs et leur numéro d'affiliation
\author{Y.HU$^1$, F. BENDALI$^1$, J.MAILFERT$^1$, C. CARIOU$^2$, L. MOIROUX-ARVIS$^2$}

% Les affiliations par ordre croissant des numéros d'affiliation et séparées par \and
\institute{
Laboratoire, LIMOS, UMR CNRS 6158, Université Clermont Auvergne \\
\email{Yuankang.HU@doctorant.uca.fr}
\and
Laboratoire, TSCF, UR INRAE\\
\email{Christophe.Cariou@inrae.fr}
}

\maketitle
\thispagestyle{empty}

% Les mots-clés
\keywords{Automated Drone Control; Close Enough Traveling Salesman Problem; Integer Linear Programming.}

\section{Introduction}

Nowadays, communication sensors are widely used in agricultural fields to measure the physical properties of the topsoil. For protection purposes, these devices are usually buried in the crops. As a result, their radio signals suffer attenuation, leading to a reduced communication range. These communication ranges which are modeled as truncated hemispheres of various sizes define the neighborhoods of the sensors. In our study, an unmanned aerial vehicle (UAV) collects sensor data by flying through the communication regions of sensors at different altitudes taking obstacles into account.

In this presentation, we first describe a mixed-integer linear programming model for optimizing the drone path that avoids obstacles. Then, a genetic algorithm is proposed to determine an order on the sensor areas. The CPLEX solver calculates the best coordinates of the hitting points for each sensor domain according to that order.

%In this presentation, we propose a mixed integer linear programming model for optimizing the drone path while avoiding obstacles. A genetic algorithm, used as a metaheuristic, determines the visiting order of the sensor areas. Given this order, the CPLEX solver calculates the optimal coordinates of the hitting points for each sensor domain.

Numerical experiments on INRAE instances with up to 70 sensors will also be given.
%\begin{figure}[htbp]
% \centering
% \includegraphics[width=0.2\textwidth]{drone.png}
% \caption[Fig]{Communication range model of sensors\cite{bib3}}\label{fig:Drone}
%\end{figure}
%\end{comment}

\section{A Mixed-Integer Linear Formulation}

Our approach is based on the Close Enough Traveling Salesman Problem (CETSP)\cite{bib1, bib2}. In the CETSP, we have to find a visiting order between $n$ target domains and select a hitting point in each of them.
We assume that the domain of a sensor \( i, i \in V \), is a parallelepiped centered at the sensor location $c_i$. The drone only needs to hit a point $s_i$ of this zone for considering the place $i$ as visited.
The take-off (resp. landing) area of the drone is numbered by 0 (resp. $n+1$).

In order to obtain a mixed linear model, the distance between two hitting points $s_i$ and $s_j$ is the Manhattan distance $d_1(s_i,s_j)$.

Thus we get the following formulation.

%\begin{equation}
\begin{align}
\min \quad & \sum_{(i,j) \in \mathcal{E}} \alpha_{ij} \label{fon_obj}\\
\text{s.t.} \quad
& \alpha_{ij} \geq d_1(s_i, s_j) - D_M (1 - x_{ij}) && \forall (i,j) \in \mathcal{E} \label{ineq_1}\\
& x=(x_{ij}) \in \mathcal{X} \nonumber \\
%& \sum_{j=0}^{n+1} x_{ij} = 1 && \forall i \in \mathcal{V} \setminus \{n+1\} \\
%& \sum_{j=0}^{n+1} x_{ji} = 1 && \forall i \in \mathcal{V} \setminus \{0\} \\
& s_i\in \mathcal{C}_i && \forall i \in \mathcal{V} \nonumber \\
& \alpha_{ij} \geq 0 && \forall (i,j) \in \mathcal{E} \nonumber
\end{align}
%\end{equation}

The binary vector $x=(x_{ij})$ is the incidence vector of a Hamiltonian path from node $0$ to node $n+1$.
It gives the visiting order of the sensor domains.
${x_{ij}}$ is equal to one if the drone directly travels from domain $i$ to another domain $j$. Then constraint~(\ref{ineq_1}) implies that ${\alpha_{ij}}$
will be the Manhattan distance between the point $s_i \in \mathcal{C}_i $ and the point $s_j \in \mathcal{C}_j$.
The set of vectors $x=(x_{ij})$ is denoted by ${\mathcal{X}}$.
${D_M}$ is a large constant used in the big-M technique. Let ${\mathcal{V}} = V \cup \{0, n+1\}$ and ${\mathcal{E}}$ be the set of edges.
The objective~(\ref{fon_obj}) is to minimize the total trajectory length of the UAV, while ensuring each domain is visited once and obstacles are avoided.

%Where $\boldsymbol{\mathcal{V}}$ is the set of domains (sensor areas), with the index set defined as $\mathcal{V} = [0, n+1]$, and the size $n=|V|$ and $\boldsymbol{\mathcal{E}}$ is the set of edges. $\boldsymbol{\mathcal{X}}$ is the set of incidence vectors $x^{\mu}$ where $\mu$ is a Hamiltonian path from vertex $0$ to vertex $n+1$. The binary variable $\boldsymbol{x_{ij}}$ is equal to one if the drone directly travels from domain $i$ to another domain $j$ and $\boldsymbol{\alpha_{ij}}$ is defined as the Manhattan distance between the point $s_i$ and the point $s_j$. Finally, $\boldsymbol{D_M}$ is a large constant (big-M) used to linearize constraints.
%The objective is to minimize the total trajectory length of the UAV, while ensuring each domain is visited once and obstacles are avoided.

%\section{Avoiding obstacles}
Our test zone comes from the INRAE experimental farm in Montoldre~(Allier) and is described by Airborne LiDAR data~\cite{bib2}.
A few preprocessing steps are first performed.
\begin{figure}[htbp]
\centering
\includegraphics[width=0.35\textwidth]{obstacle.png}
\caption{Obstacles within sensor range}\label{fig2}
\end{figure}
We aim to check the presence of obstacles in a cubic shaped area between every pair of sensor domains $(i,j)$ as shown in Fig~\ref{fig2} and to define the obstacle set $\Omega_{i,j}$. Subsequently, we determine the highest point $Z_{max}$ within the obstacle set $\Omega_{i,j}$ and incorporated it as a data into the MILP model for path optimization by establishing particular linear constraints.

\section{Conclusion}
In this paper, we propose a fully linear model that integrates obstacle avoidance with path planning, and solve the CETSP in cluttered environments using CPLEX as a standard MILP solver. In addition, we develop a genetic algorithm capable of computing optimized paths efficiently. The proposed approach is tested on real-world agricultural use cases.

This work was supported by the International Research Center ”Innovation
Transportation and Production Systems” of the I-SITE CAP 20-25”

\begin{thebibliography}{3}

\bibitem{bib1}
Behdani, B., \& Smith, J. C. (2014).
\newblock \emph{An integer-programming-based approach to the close-enough traveling salesman problem.}
\newblock INFORMS Journal on Computing, 26(3), 415-432.

\bibitem{bib2}
Cariou, C., Moiroux-Arvis, L., Bendali-Mailfert, F., Hu, Y., \& Mailfert, J. (2025).
\newblock \emph{Unmanned Aerial Vehicle Optimal Route Planning for Data Collection of Underground Communicating Sensor Nodes in Agriculture.}
\newblock Journal on Autonomous Transportation Systems, 3(1), 1-17.

\bibitem{bib3}
Cariou, C., Moiroux-Arvis, L., Bendali, F., Hu, Y., \& Mailfert, J. (2025, June).
\newblock \emph{Path planning of Unmanned Aerial Vehicle flying at low height for Internet of Underground Things-Application to data collection of buried communicating sensor nodes in agriculture.}
\newblock 2025 10th International Conference on Smart and Sustainable Technologies (SpliTech) (pp. 1-6). IEEE.

\end{thebibliography}
\end{document}