\section{Introduction}
Hard X-ray imaging spectroscopy is actively used in the wide field from astronomy to industry and medical imaging.
However, the imaging capability of existing photon-counting detectors still has a lot of room for improvement.
We have been developing  Double-sided Strip Detectors based on cadmium telluride diode (CdTe-DSD), which provide a far superior energy resolution to conventional detectors, owing to a Schottky junction on the surface of CdTe \cite{takahashi1999high, takahashi2001recent}.

One advantage of the DSD configuration compared with the pixel-type detector is that signals can be measured from both anode and cathode strips.
Since the $\mu\tau$ products (mobility times lifetime) in CdTe differ by a factor of ten between holes and electrons, the amounts of signals accumulated on the cathode and anode sides differ according to the depth of the interaction point (DoI) \cite{takahashi2001recent, salccin2014fisher}.
If a photon interacts with the detector at a point close to the anode side, for example, more holes are trapped, and the signal on the cathode side, i.e., the total energy, will be weaker than that on the anode side. Conversely, we can estimate the DoI for each event from the difference in the observed signals between the cathode and anode sides and can use it to improve the energy and position resolutions.

Another piece of information provided by the detector in the DSD configuration is charge sharing.
The charge cloud generated in the detector may spread out across multiple strips \cite{koenig2013charge, furukawa2020imaging}, depending on where the incoming photon interacts in the detector.
If charge sharing happens, signals from the event are detected on adjacent strips and the ratio of the amounts of the signals between the strips depends on the location of the original interaction in the detector.
Conversely, utilizing the ratio of the signals enables us to  improve the position resolution to a finer degree than the strip pitch.

Previously, we developed new energy and position reconstruction methods that utilized the DoI estimated from the measured signals from both side strips for 60 $\mu$m strip pitch CdTe-DSDs (strip width of 50 $\mu$m and the gap between adjacent strips of 10 $\mu$m) \cite{furukawa2020imaging}. The detector is developed for the Focusing Optics X-ray Solar Imager (FOXSI-3) sounding rocket experiment \cite{krucker2009focusing, musset2019ghost}.
We achieved an energy resolution of 0.8 keV (FWHM) for the 13.9 keV line peak using both sides of energy information for single and double-strip events (the type of events of which the signal is split to and detected on two adjacent strips).
We also demonstrated by modeling the charge propagation on the basis of the DoI and sharing energies between adjacent strips that the position resolution finer than the strip pitch could be achieved.
However, the ratio of charge-sharing events for 20 keV photons on the cathode side was limited to 25\% \cite{furukawa2020imaging}.
Given that charge sharing is essential to achieve a sub-strip position resolution, a higher ratio is more desirable to achieve a better position resolution.
In particular, the position resolution of $\lesssim 30~\mathrm{\mu m}$ and the energy resolution of $\lesssim 1~\mathrm{keV}$ are required at the same time for the upcoming fourth launch FOXSI-4 \cite{2020AGUFMSH0480011G, Camilo2021} in 2024 to provide simultaneous diagnostics of specifically and spatially separated coronal and chromospheric emission.

We propose a novel concept of widening a gap between adjacent strips to enhance the ratio of charge-sharing events.
One way to increase the charge-sharing probability is to reduce a strip pitch, which we have attempted with some success in the past \cite{furukawa2020imaging, furukawa2019development}.
However, it is difficult to pursue this direction further to ensure a certain yield level with the current technology.
This concept also has merit in making a sensitive area of the detector larger while keeping the number of read-out channels.
So far, the concept has never been experimentally proved, and it may have downsides, such as potential degradation in spectral performance and/or detection efficiency.

To examine the concept, we developed a wide-gap CdTe strip detector, in which the gap between adjacent strips is much wider than the width of the strips. In this paper, we report the results of our experiments to  evaluate  the effect of strip and gap widths on the charge-sharing properties, as well as
spectral performance and detection efficiency. We also describe our new energy-reconstruction method to compensate for the charge loss caused by wide gaps.
Finally, we  report the results of a theoretical simulation to evaluate our experimental results.

\begin{figure}[H]
\begin{center}
\includegraphics[width=1.0\hsize]{fig/setup_widegap.pdf}
\caption{A photograph of the wide-gap CdTe strip detector (upper) and a schematic view of the electrode configuration (lower). The detector is connected to a VATA-SGDs ASIC \cite{watanabe2014si} for pulse-height measurement. The fanout part is covered with a 1 mm thick tungsten plate to accurately evaluate the difference in charge-sharing properties caused by strip and gap widths.}
\label{setup_mini}
\end{center}
\end{figure}

\section{Detector configurations}
Figure \ref{setup_mini} shows a photograph of the wide-gap CdTe strip detector that we developed and a schematic view of the electrode configuration.
The detector is 1 mm thick and has 64 platinum strip electrodes on the cathode side and a common indium electrode on the anode side (i.e., The detector is a single-sided strip detector configuration).
The widths of strips and gaps between the strips are varied from $60~\mathrm{\mu m}$ strip pitch ($30~\mathrm{\mu m}$ strip width and $30~\mathrm{\mu m}$ gap width) to $80~\mathrm{\mu m}$ strip pitch ($30~\mathrm{\mu m}$ strip width and $50~\mathrm{\mu m}$ gap width).
The signal is read only from the cathode side with the Application Specific Integrated Circuits (ASICs) (i.e., the energy and position (1-dimension) information is obtained only from the cathode side.).
The ASIC has 64 channels, and each channel contains a preamplifier, a fast shaper for self-triggering, and a slow shaper for pulse-height measurement (VATA-SGD ASICs \cite{watanabe2014si}, originally developed for the Soft Gamma-ray Detector (SGD) onboard the ASTRO-H (Hitomi) satellite \cite{takahashi2014astro}).

The detector was housed in a metal box and kept cooled at $-10$ degrees Celsius.
The bias voltage was set to 500 V.
To accurately evaluate the difference due to strip and gap widths, we covered the fanout part (which connects the detector and ASIC) with a 1 mm thick tungsten plate and irradiated the detector  on the cathode side with X-rays from  an ${}^{241}$Am source. The distance between the detector and the radiation source was set to $D = 120~\mathrm{mm}$ for the size of the detector $L = 4.95~\mathrm{mm}$ and accordingly,
the difference in X-ray intensity due to the difference in the distance from the radiation source  to the detector surface was limited to ${(L/D)}^2 = {(4.95~\mathrm{mm}/120~\mathrm{mm})}^2 \sim 0.2\% $

In the following sections, we present the results based on signals extracted from five consecutive channels in one or more sets out of the following four sets of combinations for strip and gap widths.
We focus on the energy range for the FOXSI observation target ($E \lesssim 30~\mathrm{keV}$).
\begin{description}
\setlength{\parskip}{0cm}
\setlength{\itemsep}{0cm}
\item[Set (A)]~~strip width 30~$\mathrm{\mu m}$ -- gap width 30~$\mathrm{\mu m}$
\item[Set (B)]~~strip width 30~$\mathrm{\mu m}$ -- gap width 40~$\mathrm{\mu m}$
\item[Set (C)]~~strip width 30~$\mathrm{\mu m}$ -- gap width 50~$\mathrm{\mu m}$
\item[Set (D)]~~strip width 40~$\mathrm{\mu m}$ -- gap width 40~$\mathrm{\mu m}$
\end{description}

\begin{figure*}[!]
\begin{center}
\includegraphics[width=1.0\hsize]{fig/spect_before.pdf}
\caption{Spectra of ${}^{241}$Am for (left) single-strip events and (right) double-strip events in each set of strip and gap regions: sets (A)--(D) in red, orange, green, and blue, respectively. The energy spectrum of FOXSI-3 CdTe-DSD is also overlaid in black. For a double-strip event, the sum of the strip energies is adopted as its photon energy (i.e., $E=E_i+E_{i+1}$, where $E_i$ and $E_{i+1}$ are the detected energies on the $i$-th and ($i+1$)-th strips, respectively). The energy threshold of each strip is set to 1.5 keV.}
\label{spect_before}
\end{center}
\end{figure*}

\begin{figure*}[!]
\begin{center}
\includegraphics[width=1.0\hsize]{fig/ratio_energy.pdf}
\caption{Relationships between the energies detected on adjacent strips for (left) FOXSI-3 CdTe-DSD and the (right) wide-gap detector of the set (c) for double-strip events. The four points in the 60 keV peak line are the X-ray fluorescence of Cd and Te (23 keV and 27 keV). The 60 keV events are less for the wide-gap detector of the set (c) because the ratio of three and four strip events are increased to $\sim 50$\%.}
\label{ratio_energy}
\end{center}
\end{figure*}

\begin{figure*}[!]
\begin{center}
\includegraphics[width=1.0\hsize]{fig/mod_method.pdf}
\caption{(a) Relationships between the difference $ E_{diff} = E_{i} - E_{i+1}$ and the sum $E_{sum} = E_i + E_{i+1}$ of the strip energies for double-strip events. The peak positions of the V-shaped structures are fitted  with quartic functions.
(b) the gain correction factors derived from the determined quartic model functions are multiplied to panel (a), resulting in the relationship where  the reconstructed energy $E_{mod}$ is a constant value with respect to $E_{diff}$.}
\label{mod_method}
\end{center}
\end{figure*}

\begin{figure*}[!]
\begin{center}
\includegraphics[width=1.0\hsize]{fig/spect2.pdf}
\caption{(a) Spectra of the (black) sum of the strip energies $E_{sum}$ and the (red) reconstructed energy $E_{mod}$ for double-strip events. All $E_{diff}$ events are used. (b) A spectrum for single-strip and reconstructed double-strip events (red). The spectrum of FOXSI-3 CdTe-DSD is also overlaid (black).}
\label{reconst_spect}
\end{center}
\end{figure*}

\section{Effect on Spectroscopic Performance}\label{sec:spec}
\subsection{Energy loss in wide-gap configurations}
Figure \ref{spect_before} shows the energy spectra of ${}^{241}$Am source obtained  with each set of strip-and-gap-widths regions. Here in the spectrum, the sum of the strip energies $E_{sum}$ is used for a double-strip event.
Let us define $E_i$ and $E_{i+1}$ as the strip energies directly converted from the signals detected in the adjacent $i$-th and ($i+1$)-th strips and then $E_{sum}=E_i+E_{i+1}$. The energy threshold of each strip is set to 1.5 keV. The events spreading over three or more strips accounted for the remaining 2\%, and we would ignore these events in the following analyses.
In Figure~\ref{spect_before}, we also overlay, for comparison, the energy spectrum of FOXSI-3 CdTe-DSD with a 60 $\mu$m strip pitch  (50 $\mu$m strip and 10 $\mu$m\ gap), the thickness of which is 0.75 mm, where the bias voltage is set to 200 V.

The obtained spectra for single-strip events show no significant deterioration in spectral performance in the wide-gap CdTe detectors (0.9 keV in FWHM for the widest-gap set (C) at the 13.9 keV peak) from that in FOXSI-3 CdTe-DSD, except for the presence of a low-energy tail component, which appears increasingly more noticeable for wider-gap detectors.

In contrast, the spectral performance for double-strip events apparently deteriorated with the peaks shifting to the lower-energy side.
Figure~\ref{ratio_energy} shows the relationships of the energies detected in adjacent strips for double-strip events.
For FOXSI-3 CdTe-DSD, there is a linear relationship between the energies detected in adjacent strips ($E_i+E_{i+1}=const.$).
This implies that a simple summation of the energies on adjacent strips is a reasonable method to reconstruct incident X-ray energies.
In contrast, for wider-gap detectors, the sum of the energies deviates from the constant and  is smaller. The tendency is particularly noticeable for the events for which the energies between adjacent strips are similar ($E_i \simeq E_{i+1}$); the events of this type occur when  photons interact with the material in the detector at a location  close to the center of the gap. The spectrum in Figure~\ref{spect_before} and relationship plot in Figure~\ref{ratio_energy} indeed imply that part of the charge induced by an incoming photon is lost during charge accumulation in the detector and that the amount of the charge loss is likely to be a function of the photon-interaction position inside the detector \cite{koch2021charge,abbene2018digital}.

In the next subsection, we develop an energy reconstruction method for compensating for the charge loss as a result of an adoption of wide gaps on the detector, with which the energy dependence of charge-sharing properties is accurately assessed, with the aim of achieving the similar spectral performance to that with predecessors (specifically, FOXSI-3 CdTe-DSD).

\subsection{Energy Reconstruction algorithm and improved spectra}
The amount of energy loss due to the wide-gaps depends on the difference in the energies in adjacent strips, which depends on the interaction positions of photons.
We developed an energy-reconstruction method by empirically determining the relationships of the sum ($E_{sum} = E_i + E_{i+1}$) and difference ($E_{diff} = E_{i}-E_{i+1}$) of the strip energies for double-strip events.
In this section, we focus on the widest-gap set (C).

First, we fit the peak position of the V-shaped structure of each ${}^{241}$Am line peak with a quartic function ($a_0 + a_1|E_{diff}| + a_2E_{diff}^2 + a_4E_{diff}^4$, see Figure \ref{mod_method}(a)).
Second, we obtain the reconstructed energy $E_{mod}$ by multiplying the sum of the strip energies of a double-strip event $E_{sum}$ by the gain correction factor (see Figure \ref{mod_method} (b)).
The gain correction factor is calculated based on the best-fit model functions for each line peak of ${}^{241}$Am so that $E_{mod}$ is a constant value with respect to $E_{diff}$.
Finally, we calculate the reconstructed energies between the line peaks of ${}^{241}$Am with the linear interpolation using the Delaunay triangulation \cite{delaunay1934bn, lee1980two}, which utilizes the TGraph2D class in the ROOT framework \cite{brun1997root}.

Figure \ref{reconst_spect} (a) shows the spectra of the sum of the strip energies $E_{sum}$ and the reconstructed energy $E_{mod}$ for double-strip events.
The deterioration of spectroscopic performance due to the charge loss is properly reconstructed, and the energy resolution is improved from 1.9 keV to 1.2 keV (FWHM) at the 13.9 keV peak after the reconstruction.
Figure \ref{reconst_spect} (b) shows the summed spectrum of the single-strip events and the reconstructed double-strip events (51\% and 47\% of the total events, respectively).
The energy resolution for the combined spectrum of single-strip and reconstructed double-strip events was found to be 1.0 keV (FWHM) at the peak of 13.9 keV, while a sufficient spectroscopic performance is maintained despite wider gaps than those of the FOXSI-3 CdTe-DSDs.

Let us give a brief comment on the limitation of the current detector for the pilot study and potential future improvement.
In our current wide-gap detector, signals were read only from the cathode side. Ideally, a wide-gap structure can be implemented also on the anode side, and signals are also read from it; then, we can, in principle, take into account the effect of charge trapping as a function of the DoI by using energy information obtained from both the anode and cathode sides \cite{furukawa2020imaging}, although the reconstruction method requires some further development to accommodate the information of DoI.
As such, this detector and method have a realistic potential for further improvement.

\begin{figure}[H]
\begin{center}
\includegraphics[width=1.0\hsize]{fig/percent.pdf}
\caption{Ratio of charge-sharing events for each set of strip-and-gap widths where the events corresponding to the 17.8 keV peak of ${}^{241}$Am are extracted. For comparison, the ratio of charge-sharing events for  FOXSI-3 CdTe-DSD is also shown. The energy threshold of each strip is set to 1.5 keV.
}
\label{percent}
\end{center}
\end{figure}

\section{Ratio of Charge Sharing}
By developing the energy reconstruction method to compensate the charge loss by wide-gaps, it makes possible to accurately assess the energy dependence of charge sharing properties.
Figure \ref{percent} shows the obtained ratios of charge-sharing events among the events for the incoming photons at the 17.8 keV peak of ${}^{241}$Am, or specifically, in an energy range of 16--19 keV, for FOXSI-3 CdTe-DSD and our sets (A)--(D) of wide-gap CdTe-DSD.
The energy threshold of each strip was set to 1.5 keV.

In the case of the same 60 $\mathrm{\mu}$m strip pitch, the ratio of double-strip events for FOXSI-3 CdTe-DSD (gap 10~$\mathrm{\mu}$m) was 24.3\%, whereas the ratio increases to 41.0\% when the gap width is widened to 30~$\mathrm{\mu}$m (set (A)).
Moreover, as the gap width is widened to 40~$\mathrm{\mu}$m and 50~$\mathrm{\mu}$m, the ratio of double-strip events increases  up to 49.9\% for the widest-gap set (C).  In consequence, we confirmed that the ratio of double-strip events can be increased by increasing the gap width.

\section{Detection Efficiency}
We evaluated the detection efficiency of the wide-gap detector, which might be degraded from the existing model. Table \ref{det_eff} shows the count rates of events for an energy range of 10--30 keV  from ${}^{241}$Am.
The error of the count rate is evaluated by dividing the total 154 hours of data by 1 hour and taking the standard deviation of each count rate.
In the analysis, events from five consecutive strips were extracted for each set of strip and gap widths. In this case, if the detection efficiency on the detector surface and the spatial distribution of the irradiation from the ${}^{241}$Am source are both uniform, the count rate is proportional to the strip pitch.  Table~\ref{det_eff} also lists the count rates normalized by the strip pitch for comparison.
We found that the detection efficiency was invariable in the 10--30 keV energy band regardless of the gap width, even as large as 50~$\mathrm{\mu}$m within the margin of error.
\begin{table}[htb]
  \centering
  \caption{Count rates at each set of strip and gap widths in the energy range of 10--30 keV of X-rays from ${}^{241}$Am}
  \scalebox{0.8}{
  \begin{tabular}{l|c|c}
     & Count Rate &  Normalized Count Rate \\
    & [counts/s] & [$10^{-3}$ counts/s/$\mathrm{\mu m}$] \\\hline \hline
    Set (A):& \multirow{2}{*}{$0.345 \pm 0.020$} & \multirow{2}{*}{$5.75 \pm 0.34$} \\
    strip 30~$\mathrm{\mu}$m -- gap 30~$\mathrm{\mu}$m & & \\
    \hline
    Set (B):& \multirow{2}{*}{$0.424 \pm 0.022$} & \multirow{2}{*}{$6.05 \pm 0.31$} \\
    strip 30~$\mathrm{\mu}$m -- gap 40~$\mathrm{\mu}$m  & & \\
    \hline
    Set (C):& \multirow{2}{*}{$0.488 \pm 0.027$} & \multirow{2}{*}{$6.10 \pm 0.33$} \\
    strip 30~$\mathrm{\mu}$m -- gap 50~$\mathrm{\mu}$m & & \\
    \hline
    Set (D):& \multirow{2}{*}{$0.492 \pm 0.026$} & \multirow{2}{*}{$6.14 \pm 0.33$} \\
    strip 40~$\mathrm{\mu}$m -- gap 40~$\mathrm{\mu}$m & & \\
    \hline
  \end{tabular}
  }
  \label{det_eff}
\end{table}

\section{Modeling of Detector Response}
We conducted the response simulation to make a prospective of the position resolution we can obtain for the wide-gap CdTe strip detector.
Accurate modeling of the X-ray detector response is also important for accurate interpretation of the results of experiments with the detector and future detector development.
We numerically investigated the response of the wide-gap CdTe strip detector, specifically the dependence of charge-sharing properties on photon-interaction positions, based on the Shockley--Ramo theorem that an induced charge at electrodes is calculated by integrating a weighting potential along a carrier trajectory.

\subsection{Simulation setup}
The charge $Q$ induced on electrodes of the detector can be calculated  according to the Shockley--Ramo theorem \cite{eskin1999signals, he2001review}.
In the theorem, a mathematical concept of ``weighting potential'' ~$\phi_{w}$ is introduced.
When the carrier density $q(\vec{r})$  moves from  the interaction position $\vec{r_0}$ to the position $\vec{r_f}$, the induced charge $Q$ at the electrode on the cathode or anode side is  given by:

\begin{align}
Q=\int^{\vec{r_f}}_{\vec{r_0}} q(\vec{r'})\vec{E_w}(\vec{r'})\cdot d\vec{r'},
\label{chargeeff}
\end{align}
where $\vec{E_w} = -\nabla \phi_w$ is the weighting field.
The trajectory of the carrier is a function of the actual electric field $\vec{E}$.

The weighting potential $\phi_{w}$  depends only on the detector geometry and electrode configuration and can be calculated by solving Laplace's equation $\Delta \phi_{w} = 0$ with  boundary conditions of $\phi_{w} = 1$ at the electrode of interest and $\phi_{w} = 0$ at all other electrodes. As for the boundary condition at the gaps, we assumed that the potential on the gap between two electrodes  is a linear decreasing function from 1 at the edge of the electrode of interest to 0 at the edge of the  other electrode.
Figure~\ref{weight_pot} (upper panel) illustrates the boundary conditions and the detector geometry. The weighting potential $\phi_{w}$ is calculated as follows:
\begin{flalign}
    &\mbox{Anode: }\nonumber	\\
    &~~\phi_{w} = \sum _{m=1}^\infty A_m(x_c) \sin{\left(\frac{m\pi}{a}x\right)}\sinh{\left(\frac{m\pi}{a}z\right)}\\
    &\mbox{Cathode: }\nonumber \\
    &~~\phi_{w} = \sum _{m=1}^\infty A_m(y_c) \sin{\left(\frac{m\pi}{a}y\right)}\sinh{\left(\frac{m\pi}{a}(L-z)\right)}\\
    &~A_m(x_{c}) = \frac{8a}{(m\pi)^2 G \sinh{\left(\frac{m\pi L}{a}\right)}} \nonumber\\
    &~~~~~~~~~\times \sin{\left(\frac{m\pi}{a}x_{c}\right)}\sin{\left(\frac{m\pi}{a}\frac{U}{2}\right)}\sin{\left(\frac{m\pi}{a}\frac{G}{2}\right)},
\end{flalign}
\label{weighting_pot2}
where $a$ and $L$ are the size and thickness of the detector, $U$ and $G$ are the widths of the strip pitch and gaps, respectively, and a pair of $x_c$ and $y_c$ is the center position of the target electrode of calculation \cite{hagino2012imaging}.
Figure \ref{weight_pot} (lower panel) shows the calculated weighting potential $\phi_{w}$ for FOXSI-3 CdTe-DSD and the wide-gap CdTe strip detector (set (A)).
The potential distribution was found to show a steep rise  near the electrode; the fact suggests that  the signal  mainly  originates from  carrier movement near the read-out electrode and that the motions of holes and electrons mainly contribute to the signals on the cathode and anode sides, respectively (``small-pixel effect'').
In addition, the weighting potential in the gap region has a higher value for the wide-gap detector.
Hence, a considerable amount of signal should be induced in also the adjacent strip, in addition to the strip closest to the interaction point.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=1.0\hsize]{fig/weight_pot.pdf}
\caption{Upper:  Schematic illustration of the boundary condition and  detector geometry for the simulation. Lower: Weighting potential for FOXSI-3 CdTe-DSD and the wide-gap CdTe strip detector (set (A)). }
\label{weight_pot}
\end{center}
\end{figure}

For the sake of simplicity, we assumed that the electric field was uniform ($E = V/L$, parallel to $z$-direction).
The number of strips is set to 128 on both sides, and the strip and gap widths are set in common (50~$\mathrm{\mu m}$ strip and 10~$\mathrm{\mu m}$ gap width for FOXSI-3 CdTe-DSD, and 30~$\mathrm{\mu m}$ strip and 50~$\mathrm{\mu m}$ gap width for the wide-gap detector (set(c))), and the effects of a guard ring and a fanout part are not included.
We also assumed that the density of the carriers generated by incoming X-rays at the interaction depth $z_i$ was expressed with regard to the number of electron-hole pair productions $n$:
\begin{align}
q_{e,h}(t) = (\mp e)n\exp\left(-\frac{|z(t)-z_i|}{\lambda_{e,h}}\right),
\end{align}
where $\lambda_{e,h} = (\mu\tau)_{e,h}E$ is the mean free path of carriers in CdTe. The carriers are decreased because of charge trapping.
In the calculation, we used typical values of $\left(\mathrm{\mu\tau}\right)_e, \left(\mathrm{\mu\tau}\right)_h =2.0\times10^{-3}, 1.2\times10^{-4}~$cm$ ^2$/s, respectively.
We also convoluted the response of pulse shaping in ASIC according to the following form:
\begin{align}
V_{out}(t)\propto \int^{t}_{0} h(t-t')\frac{dQ}{dt'}dt'.
\label{shaper}
\end{align}
We assumed that the induced current $dQ/dt$ was regarded as the impulse current and that $h(t)$ was a semi-Gaussian given by $h(t) = (t/\tau)e^{t/\tau}$ ($\tau = 3~\mathrm{\mu s}$).
The maximum value of output voltage $V_{max}$ was assigned to the output pulse height.
The output pulse height $V_{max}$ depends on the interaction depth $z_i$.
Given that the dependence of interaction depth is smaller in the FOXSI target energy range ($E \lesssim 30~\mathrm{keV}$ with the penetration length $l$ of CdTe for 30 keV X-rays being $l\sim 0.1~\mathrm{mm}$),
we took the weighted average of the output pulse height over the interaction depth and then converted it to detected energy in each strip:
\begin{align}
\overline{V_{max}}= \frac{\int^{L}_{0}V_{max}(z_i)e^{-\frac{z}{l}}dz_i}{\int^{L}_{0}e^{-\frac{z_i}{l}}dz_i}.
\label{pulseheight}
\end{align}

\begin{figure*}[htb]
\begin{center}
\includegraphics[width=0.95\hsize]{fig/check_posres.pdf}
\caption{Relationships between the detected energy in two adjacent strips A and B and the incident X-ray position from the center of strip A to the center of the other strip B.
Red and blue represent the energies obtained from the cathode and anode sides, respectively,  detected on strip A, and
 orange and green represent  those detected in strip B.
The X-ray energy is set to 17.8 keV and the threshold is set to 1.5 keV.
}
\label{check_posres}
\end{center}
\end{figure*}

\subsection{Results}
First, we calculated the ratio of double-strip events on the cathode side  from uniformly irradiated monochromatic X-rays  at 17.8 keV. The energy threshold was set to 1.5 keV.
Table \ref{modeling_result} shows the results of the simulation.
We found that the simulation results were consistent with our experimental results within $\sim$10\% for FOXSI-3 CdTe-DSD and $\sim$4\% for the wide-gap detector.
We conjecture that the inconsistency would be mitigated if the effects of diffusion of the carrier density and non-uniformity of the electric field are taken into account.
The detail is beyond the scope of this work, but the effect of charge diffusion may be important for the FOXSI-3 CdTe-DSD at least.
It is demonstrated for the FOXSI-3 CdTe-DSD that charge-sharing events at the cathode side increase as photons interact near the surface of the anode side \cite{furukawa2020imaging}.
In addition, based on the synchrotron beam scanning test \cite{duncan2022modeling}, the typical width of a ``zone" where double-strip events are the most common in the gap region is estimated to $\sim 20~\mathrm{\mu m}$, which is slightly large compared with the gap width of 10 $\mathrm{\mu m}$.
These results can be caused by charge diffusion.

\begin{table}[htb]
  \centering
  \caption{Comparison between the simulation and experimental results}
  \scalebox{0.76}{
  \begin{tabular}{l|c|c|c|c}
      & \multicolumn{2}{c}{Simulation} &\multicolumn{2}{|c}{ Experiment}\\\cline{2-5}
      Cathode side ($E=17.8~\mathrm{keV}$)&Single&Double&Single&Double\\\hline\hline
    FOXSI-3 CdTe-DSD
    & \multirow{2}{*}{85.5 \%} & \multirow{2}{*}{14.5 \%}  & \multirow{2}{*}{75.7 \%}  & \multirow{2}{*}{24.3 \%}\\
    strip 50 $\mathrm{\mu}$m -- gap 10 $\mathrm{\mu}$m & & & &  \\\hline
    Wide-gap strip detector
    & \multirow{2}{*}{46.3 \%} & \multirow{2}{*}{53.7 \%}  & \multirow{2}{*}{50.1 \%}  & \multirow{2}{*}{49.9 \%}\\
    strip 30 $\mathrm{\mu}$m -- gap 50 $\mathrm{\mu}$m & & & &  \\\hline
  \end{tabular}
  }
  \label{modeling_result}
\end{table}

Next, we calculated the ratio of the strip energies between two adjacent strips for a given incident X-ray position for FOXSI-3 CdTe-DSD and the wide-gap strip detector (set(c)), where the X-ray energy was set to 17.8 keV and the threshold was set to 1.5 keV.
Figure \ref{check_posres} shows the detected energy in two adjacent strips A and B for the given incident X-ray position from the center of strip A to the center of the next strip B.
For FOXSI-3 CdTe-DSD, the detected energy  was dominated on one side of the strip and the detected energy steeply shifted to the next strip in the gap region.
By contrast, for the wide-gap detector, the detected energy  was found to change gradually from one side of the strip to the other, depending on the incident X-ray position.
The obtained relationship implies that if we could determine the anode and cathode side of energies with an accuracy of 1 keV,
a position resolution  at the gap position is expected to be $\sim 6~\mathrm{\mu m}$,
as derived through evaluation of the energies on adjacent strips. In addition, even for single-strip events at the strip position, a position resolution of $\sim 30~\mathrm{\mu m}$ can be achieved.

\section{Conclusion}
We propose a novel concept of widening a gap between adjacent strips to enhance the ratio of charge-sharing events and achieve a position resolution finer than the strip.
This concept also has merit in making a sensitive area of the detector larger with the limited read-out channels.
To examine the concept, we developed a wide-gap CdTe strip detector and evaluated the effect of strip and gap widths on the charge-sharing proprieties.
We obtained an energy resolution of 1.0 keV in FWHM at 13.9 keV by applying a correction to compensate for the charge loss caused by wide gaps.
The correction also makes it possible to assess the energy dependence of the charge-sharing property accurately.
We found that the ratio of double-strip events could be increased by $\sim 50\%$ on the cathode side by making the gap wider.
Our simulation work suggests that the position resolution is expected to be $\sim 6~\mathrm{\mu m}$  at the gap position and to be $\sim 30~\mathrm{\mu m}$ even for single-strip events at the strip position.
Although, in this study, the evaluation test is conducted using the single-sided strip detector (signals were read only from the cathode side), we can make a prospective that a sub-strip position resolution is well achievable with wide-gap CdTe-DSDs, while obtaining a sufficient spectroscopic performance of $\sim$1 keV for the upcoming FOXSI-4 flight.
Furthermore, the performance of wide-gap CdTe-DSDs has a realistic potential for further improvement by taking into account the DoI effect using both anode and cathode sides of energy information.

\section*{Acknowledgement}
This work was supported by JSPS, Japan KAKENHI Grant Numbers 18H05457, 20H00153, and 22J12583.
S.N. is also supported by FoPM (WINGS Program) and JSR Fellowship, the University of Tokyo, Japan.


\section{INTRODUCTION}

Over the last decade, unmanned aerial vehicles (UAVs) have been widely used in both the military (intelligence, surveillance and reconnaissance missions) \cite{jj} and civilian (agriculture, mapping and surveying, entertainment, deliveries, disaster relief missions etc.) sectors \cite{hari1}. This sudden increase in UAVs poses a serious risk to civilians on the ground, as well as piloted aircraft and other UAVs operating in the same airspace. The rise in the number of UAVs in a given airspace necessitates a system referred to as the Unmanned Aircraft Systems Traffic Management (UTM) system that monitors and
manages these UAVs, especially at low altitudes. The UTM’s objective is to provide a safe, efficient, and secure airspace management system for the UAVs in the same airspace.\par

The primary responsibility of UTM is to ensure that UAVs keep a safe distance from other aircraft and obstacles. To accomplish this, several methods are developed. The graph-based methods are used in \cite{bae2018new} to plan the flight paths of multiple UAVs and maintain a minimum distance between them. In \cite{ong2015short}, the problem of collision avoidance is solved by decomposing a large Markov decision process (MDP) into small MDPs to find a solution offline and then combined online iteratively to produce a locally optimal solution. The A* algorithm is utilized in \cite{tan2019evolutionary} to generate flight paths for multiple UAVs in urban airspace. Thereafter, an evolutionary algorithm is employed to schedule the flights to avoid conflicts.  One of the most commonly used algorithms in UTM is the Artificial Potential Field (APF). The dynamic artificial potential field was used for collision avoidance in \cite{du2019realDynamicAPF}. In \cite{HAPTICAPF}, authors investigate the use of modified APF along with a haptic-based tele-operation. Authors of \cite{conflictAPF} use the APF and priority allocation rules for conflict resolution in UAVs. Trajectory prediction method and APF was used for maintaining a safe distance between UAVs and non cooperative obstacles in \cite{du2019automatic}. A computationally intensive collision avoidance algorithm using predictive control is proposed in \cite{ishaan} to avoid collision among multiple UAVs in the context  of UTM.
\par

The main contribution of this paper is the new UTM algorithm, termed the RRT-VO UTM algorithm, for a finite number of UAVs operating in a 2D environment with known 2D static obstacles. This  algorithm combines elements of an offline path planning algorithm and an online collision avoidance algorithm to enable efficient and safe coordination of multiple UAVs. Here, the offline path planning is accomplished using the Rapidly Exploring Random Tree (RRT)  algorithm  \cite{lavalle1998rapidlyRRT} and Velocity Obstacle (VO) algorithm \cite{fiorini1993motionVO}  provides collision avoidance. The RRT is chosen among the existing offline path planning algorithms due to its efficient exploratory ability. Similarly, the Velocity Obstacle (VO) is used for collision avoidance due to its ease of implementation and ability to handle multiple UAVs, making it well-suited for the UTM. To avoid collisions, the VO algorithm in the RRT-VO UTM algorithm searches for a suitable velocity vector for each UAV. In the proposed algorithm, the boundaries of 2D known static obstacles are represented using overlapping circles in order to apply the VO algorithm against the 2D known static obstacles.  The proposed algorithm's effectiveness is demonstrated by generating feasible paths for five quadcopters operating in the same 2D environment with known static obstacles. Also, the collision avoidance among UAVs and UAV to static obstacles is demonstrated for navigation through a challenging environment. A comparison is provided with the well known artificial potential filed (APF) method. The APF method fail to  avoid collision, whereas using the proposed method, all the UAVs were able to navigate successfully avoiding collisions.
\par
In Velocity Obstacle technique there are several ways to find a safe velocity to prevent collisions. In \cite{fioriniVO}, the authors describe two main methods: a global search and a heuristic search. The global search method is a comprehensive approach that finds the safe velocity by building a tree of possible maneuvers over time intervals. The heuristic search, on the other hand, is a more targeted approach that only searches for safe velocities at one time step using certain rules, or heuristics, to choose the best velocity from the options available. These heuristics include "To Goal", which prioritizes reaching the target with the highest velocity along the direct path; "Maximum Velocity", which chooses the highest avoidance velocity within a certain angle from the line to the goal; and "Structure", which selects the velocity that best avoids obstacles based on the level of risk they pose. \par

Our proposed RRT-VO UTM algorithm uses a hybrid approach that blends the "Structure" and "To Goal" heuristics. This means it tries to reach the goal as quickly as possible while taking into account the presence of obstacles. If an obstacle is detected, the algorithm will choose a velocity that not only avoids the obstacle but is also similar to the original velocity that was heading toward the goal. This hybrid approach considers both the direction and speed of the new velocity, allowing the unmanned aerial vehicle (UAV) to slow down or stop if necessary.

The rest of this paper is organized as follows: Section II gives the preliminaries and problem formulation. Section \ref{MA} describes the development of the RRT-VO UTM algorithm using the RRT and VO algorithms. The simulation results are discussed in Section \ref{SR}. The key findings of this paper and future research directions are summarized in Section \ref{CL}.

\section{Preliminaries and Problem formulation}
The increase in the volume of UAVs used for urban applications like package delivery, air ambulance etc. (as shown in Figure \ref{fig:utm}) demands low-altitude flight. Efficient low-altitude flight in the presence of a large number of buildings and multiple UAVs  requires algorithms that can generate optimal offline paths and also real-time collision avoidance. Static obstacles like buildings are approximated by rectangles (as illustrated in Figure \ref{fig:RRT}) for offline path generation. \\

\begin{figure}[h]
\begin{center}
\includegraphics[width= 8cm]{utm.jpg}
\caption{UAVs trying to navigate the airspace with other UAVs and buildings.}
\label{fig:utm}
\end{center}
\end{figure}

The UAVs considered are here of quadrotor type with first order velocity control implemented in the outer loop as given in equations (\ref{quad1}) and (\ref{quad2}) for X-axis and Y-axis respectively.
\begin{equation}
  \dot{X}=V_x
  \label{quad1}
\end{equation}
\begin{equation}
  \dot{Y}=V_y
  \label{quad2}
\end{equation}
Here $[X,\,Y]$ are the 2-dimensional coordinates of the UAV with respect to the inertial frame and the control input is the velocity given by $\textbf{V}=[V_x,\,V_y]^T$. The following assumptions are made in this paper. \\

\begin{enumerate}
    \item The obstacles in the environment are static and their positions are known.
    \item The known static obstacles are approximated by rectangles.
    \item The position and velocity of each UAV are broadcasted to all other UAVs.
    \item Furthermore, the UAVs are approximated by a circle with a given radius from their centre of gravity location.
    \item The starting and end waypoint location for each UAV is known and is given as input to the offline planner.
    \item The UAVs fly at a constant altitude from the ground. Thus, the motion planning is done in 2D space.

\end{enumerate}
The first objective here is to generate a safe offline path for UAVs to traverse from starting location to the destination location avoiding static obstacles. The second  objective is to avoid UAV-to-UAV collision as well as UAV-to-static obstacle collision by generating a  safe trajectory online, with a low computational complexity.
\section{ RRT-VO  UTM Algorithm}\label{MA}

In this section, a new UTM algorithm called the RRT-VO UTM algorithm based on the RRT and VO algorithms is presented. This algorithm's goal is to generate feasible paths for N numbers of UAVs that operate in the same environment (airspace) with known static obstacles. The feasible path of a UAV is the one that has  starting and goal positions and does not collide with known static obstacles or other UAVs. The RRT-VO UTM algorithm generally has an offline path planning module and a collision avoidance module. Given the environment with known static obstacles, the RRT algorithm acts as an offline path planner that determines a path that avoids collision with known static obstacles for UAVs before their take off and starting their mission. The VO algorithm, on the other hand, is used in real-time to avoid collisions between UAVs and static obstacles
in the environment. Next, the  RRT algorithm is briefly described.
\subsection{Rapidly-Exploring Random Tree Algorithm}
Rapidly-Exploring Random Tree (RRT) is a sampling-based motion planning algorithm that is well-suited for high-dimensional complex configuration spaces (environment) with a large number of obstacles or other constraints. The main idea behind RRT is to construct a tree-like structure in the configuration
space by incrementally adding vertices that represent the possible states of the system. In each iteration, a new random configuration is chosen, and the nearest vertex in the tree is found. The algorithm then attempts to move towards the random configuration from the nearest vertex, creating a new vertex in the tree if the new configuration is in free space and not in collision. The process is
repeated until a path between the start and goal configurations is found. Figure  \ref{fig:RRT} shows the path generated by the RRT algorithm. In this figure, the tree-like structure is represented with green lines, and the small blue crosses represent the random configuration. The red squares represent the waypoints generated by the RRT algorithm.

\begin{figure}[h]
\begin{center}
\includegraphics[width= 8cm]{rrt.jpg}
\caption{Offline path generated by RRT algorithm for navigation of UAV from starting to goal position.}
\label{fig:RRT}
\end{center}
\end{figure}

\subsection{Velocity Obstacle Algorithm}

The Velocity Obstacle algorithm considers the relative motion of other UAVs in the environment and determines a set of safe velocities for the UAVs to avoid collisions. This algorithm creates a virtual "cone" around each UAV based on its current velocity and position, as well as the velocities and positions of other UAVs/obstacles in the environment. The algorithm then finds the set of safe velocities for the UAV to avoid collisions with all of the other UAVs and static obstacles by finding the intersection of the feasible velocities for the UAV. This intersection is known as the "safe velocity set" and the UAV can choose its velocity from this set to avoid collision.\par
Figure \ref{fig:cone} shows the collision cone formed between UAV A and UAV B. The collision cone, which is used to determine potential collisions between a UAV (referred to as UAV A) and other UAVs (UAV B) or obstacles (Obstacle B), is defined using two tangents on a circle from an external point. The radius of this circle is the sum of the radii of UAV A and UAV B (Obstacle B). Let $\mathbf{V_{A}}$ be  the velocity of UAV A with respect to (w.r.t)  a reference frame, $\mathbf{V_{B}}$ be the velocity of UAV B  w.r.t  the same reference frame, and $\mathbf{V_{AB}}$ be the relative velocity vector of UAV A w.r.t UAV B. If $\mathbf{V_{AB}}$ falls within the  collision cone, then a collision between UAV A and UAV B is guaranteed. To prevent this collision, the algorithm selects the $\mathbf{V_{AB}}$ that does not belong to this collision cone. Using this new $\mathbf{V_{AB}}$, the algorithm calculates new velocities ($\mathbf{V_{A}}$) for UAV A as potential solutions.
\begin{figure}[h!]
\begin{center}
\includegraphics[width=8cm]{collision_cone.jpg}
\caption{Formation of Collision cone between the UAV A and UAV B (or Obstacle B).}
\label{fig:cone}
\end{center}
\end{figure}
To compute cone, let $\angle ABX$, $\angle DAB$, and $\angle CAB$ denote the angle between the line AB and the X-axis, the angle between the lines AD and AB, and the angle between the lines CA and AB, respectively. Moreover, the position of UAV A in 2D space is represented by the coordinates $(X_{A}, Y_{A})$, and the position of UAV B is represented by the coordinates $(X_{B}, Y_{B})$. Also, the radius of UAV A and B is represented by $R_{A}$ and $R_{B}$,  respectively. Moreover,  $\angle C_{left}$ symbolizes  the angle of left  cone boundaries and $\angle C_{right}$  exemplifies the angle of right cone boundaries. $D_{AB}$ represents distance between A and B. Now, the collision cone is computed as per equations given below.
\begin{equation}
\begin{aligned}
\angle ABX =arctan\bigg(\frac{Y_{B}-Y_{A}}{X_{B}-X_{A}}\bigg)
\label{eq:1}
\end{aligned}
\end{equation}

\begin{equation}
\begin{aligned}
\angle DAB = \angle CAB  = arcsin\bigg(\frac{R_{A}+R_{B}}{D_{AB}}\bigg)
\label{eq:2}
\end{aligned}
\end{equation}

\begin{equation}
\begin{aligned}
\angle C_{left} = \angle ABX + \angle DAB
\label{eq:3}
\end{aligned}
\end{equation}

\begin{equation}
\begin{aligned}
\angle C_{right} = \angle ABX - \angle CAB
\label{eq:4}
\end{aligned}
\end{equation}

Here Eqn. \ref{eq:1} is for calculating $\angle ABX$, Eqn. \ref{eq:2} calculates $\angle DAB$ and $\angle CAB$. Equation \ref{eq:3} and \ref{eq:4} is for calculating the angle for left $\angle C_{left}$ and right $\angle C_{right}$ cone boundaries.
\subsection{RRT-VO UTM Algorithm}
\noindent The RRT-VO UTM algorithm  is presented in this section. To explain  the RRT-VO UTM algorithm, first assume that the starting and goal positions of all the UAVs are known. Following that, the environment is formed  by placing the obstacles in a rectangular shape. The RRT algorithm is then used offline to generate obstacle-free (collision-free with known static obstacles) waypoints from the starting and goal positions for all the UAVs in this environment. Collisions between known static obstacles and  UAVs can be avoided if the UAVs follow these waypoints. However, collisions between the UAVs may happen. Also, if UAVs attempt to avoid these collisions near static obstacles, they may collide with known static obstacles in the environment. Hence, the UTM requires collision-avoidance capabilities that can also avoid these 2D static obstacles. The velocity obstacle (VO) method is used in the RRT-VO UTM algorithm for  collision avoidance. To provide the desired collision-avoidance capabilities to the RRT-VO UTM algorithm using the velocity obstacle method,  rectangular static obstacles are represented using circular obstacles of radius $R_{obs}$ with $L$ distance apart, as shown in Fig.
\ref{fig:Obstacle}. This figure depicts the boundary of a known static obstacle as an overlapping circle. The RRT-VO UTM algorithm can compute these circles as the static obstacle's boundary and circle radius are known in advance. Therefore, using the circular representations of the known static obstacle's boundaries, the VO algorithm is capable of avoiding collisions between UAVs even when they are close to known static obstacles. Likewise, each UAVs are represented as circular obstacles of radius $R_A+R_B$ as shown in Fig. \ref{fig:cone} for  collision avoidance between UAVs. \par
\begin{figure}[h!]
\begin{center}
\includegraphics[width= 7cm]{ObstacleConvert.jpg}
\caption{Representation of a rectangular obstacle using circular obstacles to apply Velocity obstacle algorithm for collision avoidance with known static obstacles.}
\label{fig:Obstacle}
\end{center}
\end{figure}
After converting the boundaries of rectangular obstacles into overlapping circular obstacles, the new UTM algorithm assigns the first waypoint to each UAV and calculates the velocity for tracking the assigned waypoint. Subsequently, the UTM algorithm computes the relative distance between each UAV using the position information of all the UAVs. When the relative distance of  one UAV, say UAV A, from some other UAV,  say UAV B, is less than a specific value ($Dist_{uav}$), then the relative velocity $\mathbf{V_{AB}}$  is computed and checked if this velocity is inside the collision cone angles [$\angle C_{left}$, $\angle C_{right}$]. If it fall within the cone, then the UTM algorithm  search for new relative velocity, $\mathbf{V_{AB}'}$. The UTM algorithm has a search loop to identify appropriate angle (denoted by $\theta$)  ranging from  of $0$ to $2\pi$ radians with a step size of $0.2$ radians for  the $\mathbf{V_{AB}'}$. Within this loop, another search loop is implemented to determine an appropriate magnitude of new relative velocity (represented by $M$),  $\mathbf{V_{AB}'}$,  ranging from $0$ to $\|\mathbf{V_{AB}}\|_{2}$ with step size of $0.2$. Now, for each $\theta$ and $M$,   $V_{AB}'$ constructed as per Eqn. \ref{eq:5}.

\begin{equation}
\begin{aligned}
\mathbf{V_{AB}'} = [M * cos(\theta), M * sin(\theta)]
\label{eq:5}
\end{aligned}
\end{equation}
If $\mathbf{V_{AB}'}$ falls outside of the cone, then it is considered as the  potential solution and the new velocity for UAV A, $\mathbf{V_{A}' \in \mathbb{R}^{2}}$, is calculated with equation mentioned in Eqn. \ref{eq:6}.
\begin{equation}
\begin{aligned}
\mathbf{V_{A}'} = [M * cos(\theta) + {\|\mathbf{V_{B}}\|_{2}} * cos(\angle \mathbf{V_{B}}),\\ M * sin(\theta) + {\|\mathbf{V_{B}}\|_{2}} * sin(\angle \mathbf{V_{B}})]
\label{eq:6}
\end{aligned}
\end{equation}
The computed values of feasible velocities are then stored in an array $fV_{A}$. Similarly,   the collision cones are constructed for all other UAVs or obstacles.However,  no further search for new $\mathbf{V_{AB}}$ is performed. Instead, each entry in $fV_{A}$ is evaluated, and the corresponding relative velocity $\mathbf{V_{AB}'}$ is calculated. If this $\mathbf{V_{AB}'}$ falls within the cone, the corresponding $\mathbf{V_{A}'}$ is removed from $fV_{A}$. After this process has been completed for all other UAVs and obstacles, the velocity $\mathbf{V_{A}'}$ is selected from $fV_{A}$ based on its similarity to original velocity $\mathbf{V_{A}}$, as determined by the Euclidean norm. Then, the position of the UAV A is updated by using the selected $\mathbf{V_{A}'}$ as given in Equation \ref{eq:7} and \ref{eq:8}.
\begin{equation}
\begin{aligned}
X_{A} = X_{A} + dt *VX_{A}'
\label{eq:7}
\end{aligned}
\end{equation}

\begin{equation}
\begin{aligned}
Y_{A} = Y_{A} + dt *VY_{A}'
\label{eq:8}
\end{aligned}
\end{equation}

In Eqn. \ref{eq:7} \& \ref{eq:8}, $VX_{A}'$ and $VY_{A}'$ are the x and y components of $\mathbf{V_{A}'}$ and $dt$ is the time-step used for integrating the velocities. In the RRT-VO algorithm, the aforementioned process of determining a new velocity to avoid collision is repeated for each UAV in the airspace at each time-step. The pseudocode of the RRT-VO algorithm is given in Algorithm \ref{alg:RRT-VO}.
\begin{algorithm}[h!]
\caption{RRT-VO UTM Algorithm}
\label{alg:RRT-VO}
\begin{algorithmic}[1]
\State \textbf{Input:} UAV start, goal position $(X, Y)$ and initial \par velocity $(VX, VY)$ and obs. pos., width, height
\State Calculate waypoints for each UAV using RRT
\State Generate circular obstacles from rectangular obstacles
\State Assign initial waypoints to each UAV
\While{goals not reached}
\For{each UAV A}
\If{distance between A, waypoint$<Dist_{wp}$}
\State Assign next waypoint $(X_{Awp}, Y_{Awp})$ to A
\EndIf
\EndFor
\For{each UAV A}
\State Calculate velocity \par \hspace{0.3cm} $\mathbf{V_{A}}  = [kp*(X_{Awp} - X_{A}), kp*(Y_{Awp} - Y_{A})]$
\State Initialize feasible velocity set $fV_{A}$
\For{each remaining UAV B}
\If{distance between A, B $<Dist_{uav}$}
\State Calculate relative velocity \par \hspace{1.3cm} $\mathbf{V_{AB}} = [VX_{A} - VX_{B}, VY_{A} - VY_{B}]$
\State Calculate angle bound for collision cone \par \hspace{1.3cm} from Eqn. \ref{eq:3} and \ref{eq:4}
\If{$\mathbf{V_{AB}}$ lies in cone and $fV_{A}$ is empty}
\State Search for $\mathbf{V_{AB}'}$ outside cone by Eqn.\ref{eq:5}
\State Calculate $\mathbf{V_{A}'}$ from $\mathbf{V_{AB}'}$ using Eqn. \ref{eq:6} \par \hspace{1.8cm} and store in $fV_{A}$
\EndIf
\If{$\mathbf{V_{AB}}$ lies in cone \& $fV_{A}$ not empty}
\For{each $\mathbf{V_{A}'}$ in $fV_{A}$}
\State Calculate $\mathbf{V_{AB}'}$ from $\mathbf{V_{A}'}$
\If{$\mathbf{V_{AB}'}$ lies in cone}
\State Remove $\mathbf{V_{A}'}$ from $fV_{A}$
\EndIf
\EndFor
\EndIf
\EndIf
\EndFor
\For{each obstacle B}
\If{distance between A, B$<Dist_{obs}$}
\State \textbf{Repeat} steps 16-29
\EndIf
\EndFor
\State Select $\mathbf{V_{A}'}$ from $fV_{A}$ similar to original $\mathbf{V_{A}}$
\State Update UAV A's position using $\mathbf{V_{A}'}$ from \par \hspace{0.3cm} Eqn. 7 and 8
\EndFor
\EndWhile
\end{algorithmic}
\end{algorithm}

\section{SIMULATION RESULTS}\label{SR}
In this section, the effectiveness of the RRT-VO UTM algorithm is evaluated for multiple UAVs operating in the same environment with a dimension of 400~m $\times$ 400~m. The environment is made up of multiple rectangular obstacles that are converted into overlapping circular obstacles. The performance of the proposed algorithms is assessed in terms of safety \& collision-free trajectory generation and path length for five and seven quadcopters in the given environment with known static obstacles. For comparison with the proposed algorithm, the Artificial Potential Field (APF)-based UTM algorithm is used to generate paths for these UAVs operating in the same environment. APF works on the basis of attraction force to reach goal/waypoint and repulsion force to avoid collisions with other UAVs and obstacles. Suppose $(X_{A}, Y_{A})$ is the position of UAV A, $(X_{Awp}, Y_{Awp})$ as the position of assigned waypoint for UAV A and $(X_{B}, Y_{B})$ is the position of other UAV or obstacle B. The equations for calculating attractive and repulsive force are mentioned in Eqn. \ref{eq:10} \& \ref{eq:12}.

\begin{equation}
\begin{aligned}
Dir_{att} = [X_{Awp} - X_{A}, Y_{Awp} - Y_{A}]
\label{eq:9}
\end{aligned}
\end{equation}

\begin{equation}
\begin{aligned}
F_{att} = k_{att} * \frac{Dir_{att}}{\|Dir_{att}\|}
\label{eq:10}
\end{aligned}
\end{equation}

\begin{equation}
\begin{aligned}
Dir_{rep} = [X_{A} - X_{B}, Y_{A} - Y_{B}]
\label{eq:11}
\end{aligned}
\end{equation}

\begin{equation}
\begin{aligned}
F_{rep} = k_{rep} * \frac{Dir_{rep}}{\|Dir_{rep}\|}
\label{eq:12}
\end{aligned}
\end{equation}

Here, Eqn. \ref{eq:9} \& \ref{eq:11} calculates the direction vector ($Dir_{att}$  \& $Dir_{rep}$) for attraction  and repulsion force respectively.\par
The attraction and repulsion force are added together to calculate total force (shown in Eqn \ref{eq:13}) which is then used to update the position of UAV A as shown in Eq. \ref{eq:14} \& \ref{eq:15}.

\begin{equation}
\begin{aligned}
TF = F_{att} + F_{rep}
\label{eq:13}
\end{aligned}
\end{equation}

\begin{equation}
\begin{aligned}
X_{A} = X_{A} + dt*TF_{X}
\label{eq:14}
\end{aligned}
\end{equation}

\begin{equation}
\begin{aligned}
Y_{A} = Y_{A} + dt*TF_{Y}
\label{eq:15}
\end{aligned}
\end{equation}
where $TF_{X}$ and $TF_{Y}$ are the x and y component of total force ($TF$). Position of each UAV is updated similarly using equations \ref{eq:9}-\ref{eq:15} to avoid obstacles and other UAVs. \par

The RRT-VO UTM algorithm (\textbf{Algorithm \ref{alg:RRT-VO}}) is implemented in Matlab and uses the parameters given in Table \ref{tb:parameter1} for the simulations. The APF-based UTM algorithm uses the same waypoints generated by the RRT algorithm. It also uses basic mechanism such as activation of collision avoidance when another UAV or obstacle is below certain distance ($Dist_{uav}$/$Dist_{obs}$) from current UAV and assigning a new waypoint when distance of UAV from previous waypoint is less than a certain value ($Dist_{wp}$). The parameters used in APF algorithm are mentioned in Table \ref{tb:parameter2}.

\begin{table}[h!]
\begin{center}
\caption{Parameters for simulating the RRT-VO UTM algorithm}\label{tb:parameter1}
\begin{tabular}{|c||c|}
\hline
Parameter & Value \\\hline
$k_{p}$ & 0.2\\
$dt$ & 0.1 \\
$R_{uav}$ & 12 \\
$R_{obs}$ & 12 \\
$L$ & 15 \\
$Dist_{wp}$ & 10 \\
$Dist_{uav}$ & 50 \\
$Dist_{obs}$ & 20 \\\hline

\end{tabular}
\end{center}
\end{table}

\begin{table}[h!]
\begin{center}
\caption{Parameters for simulating the RRT-APF UTM algorithm}\label{tb:parameter2}
\begin{tabular}{|c||c|}
\hline
Parameter & Value \\\hline
$k_{att}$ & 8\\
$k_{rep}$ & 15\\
$dt$ & 0.1 \\
$Dist_{wp}$ & 10 \\
$Dist_{uav}$ & 50 \\
$Dist_{obs}$ & 20 \\\hline

\end{tabular}
\end{center}
\end{table}

The feasible paths generated by the RRT-VO UTM algorithm is shown in Fig. \ref{fig:5_UAV}. These paths are not colliding with any static obstacles. Also, the paths shown in Fig. \ref{fig:5_UAV} indicates that the proposed UTM algorithm is able to avoid collision with known static obstacles and other UAVs. This is substantiated with relative distance between UAVs shown in Fig. \ref{fig:5_UAV_Distance}. The relative distances are non-zero which suggest non collision between UAVs. For RRT-APF method it is clearly evident from non zero relative distance (shown in Fig. \ref{fig:5_UAV_APF_Distance}) that each UAV is able to avoid collision with other UAV. However, Fig. \ref{fig:5_UAVb} shows that UAV 2 and UAV 5 collided with obstacles (represented by circle) while trying to navigate through the environment.\par
Another point of comparison between the two algorithms is the path length. Table \ref{tb:PathLength} shows the path length of both the algorithms for the environment with five UAVs as shown in Fig. \ref{fig:5_UAV} and Fig. \ref{fig:5_UAVb}. The  "--" term in RRT-APF column for UAV 2 and 5 indicates the occurrence of a collision, thus ignoring the path length values for these cases. For each of the five UAVs, RRT-VO UTM algorithm is generating lower path length as compared to RRT-APF UTM algorithm.
Similarly, Table \ref{tb:PathLength7} shows path length of seven UAVs navigating in the same environment. In this experiment, UAV 3, UAV 4 \& UAV 6 collided with the obstacle when using RRT-APF method. Thus, the path length of these UAVs is mentioned as "--". On the other hand, the UAVs using RRT-VO UTM algorithm have shorter path lengths without any collisions when compared with RRT-APF for seven UAVs.\par

In this paper, only quadcopters are used for simulations. However, it is important to note that the RRT-VO UTM algorithm can be used to generate paths for the fixed-wing aircraft or a combination of fixed wing and quadcopters.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=8cm]{5_UAV_VO.jpg}
\caption{Five UAVs navigating the environment using RRT-VO UTM algorithm.}
\label{fig:5_UAV}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width=8cm]{5_UAV_VO_Dist.png}
\caption{Distance between the pair of UAVs while navigating the environment using RRT-VO UTM algorithm.}
\label{fig:5_UAV_Distance}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width=8cm]{5_UAV_PF.jpg}
\caption{Five UAVs navigating the environment using RRT-APF UTM algorithm. UAV 2 and UAV 5 collides with edge of the static obstacle. Top figure is the magnified image of the area in which collision occurs.}
\label{fig:5_UAVb}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width=8cm]{5_UAV_APF_Dist.png}
\caption{Distance between the pair of UAVs while navigating the environment using RRT-APF UTM algorithm.}
\label{fig:5_UAV_APF_Distance}
\end{center}
\end{figure}

 \begin{table}[h!]
\begin{center}
\caption{Path Length of five UAVs navingating the environment using RRT-VO UTM and RRT-APF UTM algorithm.}\label{tb:PathLength}
\begin{tabular}{|c||c||c|}
\hline
& RRT-VO ($m$) & RRT-APF ($m$)\\\hline
UAV 1 & 603.35 & 676.67\\
UAV 2 & 623.7 & --\\
UAV 3 & 534.77 & 632.73\\
UAV 4 & 469.23 & 616.39\\
UAV 5 & 696.16 & --\\\hline

\end{tabular}
\end{center}
\end{table}

 \begin{table}[h!]
\begin{center}
\caption{Path Length of seven UAVs navingating the environment using RRT-VO UTM and RRT-APF UTM algorithm.}\label{tb:PathLength7}
\begin{tabular}{|c||c||c|}
\hline
& RRT-VO ($m$) & RRT-APF ($m$)\\\hline
UAV 1 & 665.84 & 687.37\\
UAV 2 & 609.13 & 671.9091\\
UAV 3 & 604.9 & --\\
UAV 4 & 446.05 & --\\
UAV 5 & 608.17 & 724.66\\
UAV 6 & 612.51 & --\\
UAV 7 & 465.52 & 531.01\\\hline

\end{tabular}
\end{center}
\end{table}

\section{CONCLUSION}\label{CL}
A new UTM algorithm referred to as the RRT-VO UTM algorithm is developed by combining the Rapidly-Exploring Random Trees (RRT) and Velocity Obstacles (VO) algorithms. The tractability and effectiveness of this algorithm are demonstrated by generating safe and collision-free paths for multiple quadrotors. Furthermore, the comparison study indicates that the RRT-VO UTM algorithm outperforms the APF-based UTM algorithm in terms of safe navigation and lower path length. The proposed algorithm can also generate feasible paths for fixed-wing aircraft or a combination of fixed-wing and quadcopters. Future research will be focused on extending the RRT-VO UTM algorithm to generate feasible 3D paths for multiple UAVs.

\addtolength{\textheight}{-8cm}

\section*{ACKNOWLEDGMENT}
Author's would like to acknowledge the funding  provided by ROCKWELL COLLINS (INDIA) ENTERPRISES PVT LTD, under the project "Online Planner for UTM" to carry out this research work.

\bibliographystyle{IEEEtran}