Zibo Ke

Felipe Pedreros Bustos

Jenny Atwood

Anne Costille

Kjetil Dohlen

El Hadi

Jean-Luc Gach

Glen Herriot

Zoltan Hubert

Pierre Jouve

Patrick Rabou

Jean-Pierre Veŕan

Lianqi Wang

Thierry Fusco

Benoit Neichel

Performance of a complementary metal-oxide-semiconductor sensor for laser guide star wavefront sensing

Keywords: CMOS detector, Wavefront sensing, Extremely Large Telescopes, ELT, TMT, Laser Guide Stars

Introduction

The astronomical community has just launched the construction of the largest ground-based telescopes, with the European Southern Observatory's Extremely Large Telescope (ESO ELT) and its primary mirror of 39 m in diameter on one hand, and the Thirty Meter Telescope (TMT) and its 30 m primary mirror on the other hand. These telescopes will answer fundamental questions ranging from the detection and characterization of exoplanets [START_REF] Hawker | High-resolution spectroscopy and high contrast imaging with the ELT: looking for O 2 in Proxima b[END_REF] to the formation and evolution of the first galaxies of the universe. [START_REF] García-Lorenzo | Black hole-galaxy scaling relation evolution from Z∼2.5: Simulated observations with HARMONI on the ELT[END_REF] In order to achieve their scientific goals, the TMT and the ESO ELT require the use of adaptive optics (AO) to compensate for the aberrations introduced by atmospheric turbulence in the wavefront of the objects under study. [START_REF] Bonnet | Adaptive optics at the ESO ELT[END_REF] An AO system needs a bright star within the field of view of observation to measure the wavefront distortions using a wavefront sensor (WFS), typically a Shack-Hartmann WFS. These distortions are corrected in real-time by applying a feedback signal into a deformable mirror located in the optical path of the telescope, resulting in a flattened wavefront and therefore a near diffraction-limited image delivered to the science instrument. If a bright natural star is not available, an artificial beacon (laser guide star or LGS) is created by means of optical excitation of a layer of sodium atoms between 85 km and 100 km in altitude using one or several lasers launched from the telescope. [START_REF] Happer | Atmospheric-turbulence compensation by resonant optical backscattering from the sodium layer in the upper atmosphere[END_REF][START_REF] Primmerman | Compensation of atmospheric optical distortion using a synthetic beacon[END_REF] The light emitted from the LGS is then used as a reference for the WFS in the AO system. 1 Laser excitation of the sodium layer produces a long column of fluorescent atoms whose extension depends on the pointing angle of the telescope and the vertical density profile of the sodium layer. For an observer located only a few meters off-axis from the laser launch telescope (LLT), the

LGS appears as an elongated object instead of a point source. The LGS spot elongation becomes dramatic for a 39 m-class telescope with side LLT configuration as the ESO ELT. [START_REF] Vernet-Viard | LGS Na spot elongation and Rayleigh scattering effects on Shack-Hartmann wavefront sensor performances[END_REF] For example, the LGS produced by a 30 cm laser beam projected at zenith, will be seen by the sub-aperture of a Shack-Hartmann WFS opposite to the LLT on a 39 m diameter telescope as an elongated spot of about 10-20 arcsec long and about 1 arcsec width. The situation is less dramatic for the TMT, as it uses a central launch scheme, reducing the expected elongation by a factor ≈2 compared with the configuration of the ESO ELT. In all cases, the spot elongation depends on the pointing angle.

For a Shack-Hartmann WFS, the spot elongation introduces several issues. On the one hand, it reduces the signal-to-noise ratio since the same amount of photons once concentrated in a small spot are now distributed on a larger area on the detector, and on the other hand, it increases the wavefront error due to the growing uncertainty in the estimation of the center of gravity (CoG) of an elongated spot. [START_REF] Thomas | Study of optimal wavefront sensing with elongated laser guide stars[END_REF] In addition, the spot truncation due to highly elongated spots not completely imaged on a given sub-aperture, leads to a bias in the estimation of the CoG in proportion to the fraction of truncation. [START_REF] Clare | Mitigation of truncation effects in elongated Shack-Hartmann laser guide star wavefront sensor images[END_REF] Thus, the major challenges of LGS wavefront sensing at the ELTs scale lie on i) performing a robust wavefront analysis on a single object strongly extended and whose elongation varies across the pupil, and ii) developing a large, fast and low-noise wavefront sensor able to image the full pupil and, at the same time, provide enough sampling for both elongated and non-elongated spots. While several post-processing strategies to mitigate elongated elongated LGS have been developed, [START_REF] Schreiber | An optical solution to the LGS spot elongation problem[END_REF][START_REF] Basden | On-sky demonstration of matched filters for wavefront measurements using ELT-scale elongated laser guide stars[END_REF][START_REF] Berdja | Experimental results on using artificial neural networks for accurate centroiding in Shack-Hartmann wavefront sensors with elongated spots[END_REF][START_REF] Béchet | Optimal reconstruction for closed-loop groundlayer adaptive optics with elongated spots[END_REF][START_REF] Ribak | Reduction of laser spot elongation in adaptive optics[END_REF][START_REF] Gilles | Shack-Hartmann wavefront sensing with elongated sodium laser beacons: centroiding versus matched filtering[END_REF] we devote this work to the study of a recently-released complementary metal oxide semiconductor (CMOS) sensor intended to be used in a Shack-Hartmann WFS for the ESO ELT and the TMT.

In Sec. 2 we lay out the primary requirements of a LGSWFS for ELTs and give an overview of possible technological solutions. In Sec. 3 we characterize a candidate CMOS sensor for the LGSWFS. In Sec. 4 we provide an analysis of the impact of this type of sensor in wavefront sensing. In Sec. 5 we present two examples of implementation of this sensor in LGS WFS for ESO ELT and TMT. Finally, in Sec. 6 we assess our results and provide recommendations for the use of a CMOS sensor in the ongoing design of LGSWFS.

A detector for LGS wavefront sensing

Requirements for ELTs

To guarantee a correct measurement of the incident wavefront, the telescope pupil must be spatially sampled with a constant pitch of about 50 cm on the primary mirror. Taking as example the 39 m diameter telescope of the ESO ELT, the Shack-Hartmann wavefront sensor needs to accommodate at least 78×78 sub-pupils.

In a linear regime the LGS spots must be sampled at the accepted Nyquist sampling criteria of 2 pixels per FWHM. The minimum size of the LGS spot seen by the WFS depends on a number of factors like the laser beam size, telescope altitude, zenith angle, seeing, and thickness of the sodium layer. Statistical analysis of the LGS spot size at Paranal, shows a median angular spot size in the non-elongated direction of 1.5 arcsec FWHM and as low as of 0.95 arcsec FWHM in good atmospheric conditions. [START_REF] Oberti | The AO in AOF[END_REF][START_REF] Hackenberg | ESO 4LGSF: Integration in the VLT, Commissioning and on-sky results[END_REF] Taking an LGS spot size of 1.0 arcsec, a pixel scale of 0.5 arcsec/pixel is required to fulfill the Nyquist criteria. Furthermore, if we consider a spot elongation of 16 arcsec on the outermost sub-pupils (this is the case for a ≈20 km vertical thickness sodium layer and a pointing angle of 30 • ), then a total of ≈32×32 pixels per sub-pupil are needed to avoid truncation of the spot in the vertical or horizontal direction. To first order, a wavefront sensor with a full size of at least 2496×2496 pixels would be necessary to sample the ESO ELT pupil using 78 sub-pupils across and avoiding truncation of the elongated spot while keeping the non-elongated direction sampled within the Nyquist criteria. Following a similar approach, the TMT configuration would require a wavefront sensor with 960×960 pixels.

The minimum required photon return flux of an LGS generated with state-of-the-art 20 W lasers is near 4 × 10 6 photons/s/m 2 , therefore the photon flux in a square sub-pupil of 50 cm side length is on the order of 1×10 6 photons/s. Given the nominal integration time of 2 ms (500 Hz) required for AO correction, and provided an estimated optical throughput of 35%, the number of photons per frame on a single sub-aperture of the WFS is ≈ 700 photons. The detection signal-to-noise-ratio (SNR) can be expressed as

SNR = N P × QE N P × QE + n pix × RON 2 , ( 1
)
where N P is the number of photons per sub-aperture per frame, QE is the quantum efficiency of the detector, RON is the root-mean-squared (RMS) read-out noise in electrons/pixel/frame, and n pix is the number of pixels used to sample the LGS spot. Assuming N P = 700 photons, QE = 0.7, n pix = 4, and RON = 3 e -/pixel/frame, we get an SNR of 21 for the case of a non-elongated spot. Considering an elongated spot covering 16 arcsec, we require n pix = 2 × 32 = 64 pixels for which we get an SNR of 15. At this point, we approach the read-out-noise-limited regime and, for example, doubling read-out noise (RON = 6 e -/pixel/frame) gives an SNR of 9 for the same elongated spot. Therefore, it is critical that the read-out noise of the sensor used for the Shack-Hartmann WFS be as low as possible.

This example shows that an adequate detector for LGS wavefront sensing requires a) a large number of pixels, b) to operate at fast frame rates, and c) to have a very low read-out noise, as specified before. Such a detector has not yet being developed as it is beyond the current technological capabilities, hence the final design of the wavefront sensor is constrained to the availability of existing detectors that can partially or in full, satisfy the aforementioned requirements.

Different technological strategies have been followed to try to answer this challenge. On the one hand, dedicated custom detector developments have been proposed both for the TMT and the ESO ELT. For the former, the idea was to exploit the specific geometry of the LGS spots, and a radial charge-coupled device (CCD) has been proposed to fit the spot elongations. [START_REF] Beletic | The Ultimate CCD for Laser Guide Star Wavefront Sensing on Extremely Large Telescopes[END_REF] Indeed, due to the central launch configuration, the spots seen by each of the LGSWFS Shack-Hartmann will be radially oriented. The proposed design implemented sub-apertures of about 4×16 pixels, with a radial geometry adapted to the spot elongation. For the ESO ELT, a custom technological development toward a large 1600×1600 pixels sensor was also attempted, [START_REF] Downing | AO WFS detector developments at ESO to prepare for the E-ELT[END_REF] resulting in a 800×800 pixels detector (Large Visible adaptive optics Sensor Module, LVSM). [START_REF] Downing | Update on development of WFS cameras at ESO for the ELT[END_REF] In this paper we explore an alternative route offered by CMOS detectors, potentially offering large arrays, with low-noise and high frame-rate.

CMOS technology for LGS wavefront sensing

CMOS detectors are becoming competitive with respect to traditional CCD for astronomical detection. The construction design of CCDs in which there is only one or few read-out amplifiers for the whole array, increases the overall detector latency as the charge from each pixel are read out sequentially through the amplifiers. In contrast, CMOS technology has one read-out amplifier per pixel allowing massive parallel readout through read-out buses, hence reducing the latency of the sensor array. There are several ways to implement this process across the whole 2D array.

Classically, the sensor can be read line-by-line which is known as rolling shutter architecture. This architecture has the advantage to use only a few transistors per pixel (3 or 4) leading to simpler and lower noise CMOS imagers. However, each line of the array is exposed and read out sequentially so at different instants across the whole array. For objects moving at speeds comparable with the frequency of read-out, the images acquired with a rolling shutter sensor exhibit a distortion artifact called jelly effect. This is a potential disadvantage for wavefront sensing, because of the WFS may not be able to capture the state of the turbulence during one frame without introducing temporal shifts over the pupil spots.

However, in 1997 Fossum [START_REF] Fossum | Active pixel sensor array with electronic shuttering[END_REF] introduced a more complex architecture using 5 transistors per pixel giving the ability to take a snapshot of the scene and store it in a memory which is then read out sequentially while the next image is integrated. In this scheme all pixels are read out at different instants, but exposed for the same amount of time, hence eliminating the temporal shifts in the final image. This architecture has the drawback of high read-out noise because of the Johnson-Nyquist reset noise that remains during read out. Later, more complex architectures using 6 transistors [START_REF] Yasutomi | Two-stage charge transfer pixel using pinned diodes for low-noise global shutter imaging[END_REF] or even 8 or 11 transistors architectures 22 permitted to integrate a correlated double sampling circuitry in each pixel that subtracts the thermal noise at the expense of a much higher pixel complexity. Usually these imagers use finer lithographic pitch CMOS processes to keep the ratio of detection diode and transistor surface at an acceptable level compared to simpler architectures. The memory zone needs to be metal shielded to avoid collecting light, therefore the pixel fill factor of global shutter devices cannot reach 100% by construction, even if they are back illuminated. To overcome this limitation, micro lenses are integrated in the sensor to concentrate the light falling across the pixel on the detection diode. [START_REF] Zhang | Optical design of microlens array for CMOS image sensors[END_REF] However, this also brings a reduction in the sensor's sensitivity for oblique angle of incidence. This effect is seldom reported, but it plays an important role in the design of a wavefront sensor.

Recent developments in CMOS technology for astronomical applications [START_REF] Downing | Backside-illuminated, high-QE, 3e-RoN, fast 700fps, 1760x1680 pixels CMOS imager for AO with highly parallel readout[END_REF][START_REF] Downing | LGSD/NGSD: high speed visible CMOS imagers for E-ELT adaptive optics[END_REF] facilitated the rapid improvement in their performance that narrows or even surpass the gap with CCD. For example, the use of pinned photodiode reduces the dark current significantly, [START_REF] Fossum | A review of the pinned photodiode for ccd and cmos image sensors[END_REF] and increasing the conversion gain or the implementation of source-follower transistor structures reduce readout noise to sub-electron levels. [START_REF] Guidash | Reduction of cmos image sensor read noise to enable photon counting[END_REF] High quantum efficiency is another characteristic relevant for low-light applications, which has been addressed by using back-thinned CMOS sensors. [START_REF] Jerram | Back-thinned CMOS sensor optimization[END_REF] In addition to achieving high performance, another advantage of CMOS detectors is their capability to be operated at room temperature or alternatively with simple water-cooling, without the need of cryocoolers. This feature drastically reduce the complexity of the instrument.

In the following sections, we report on the characterization of a large CMOS sensor and its impact on the performance of laser guide star wavefront sensing.

3 Characterization of a CMOS sensor

Parameters

The sensor we evaluate is a Sony CMOS detector model IMX425LLJ on board of a C-BLUE One camera manufactured by First Light Imaging. 29 The detector array has 1604 × 1104 active pixels, each of which with a square size of 9.0 µm ×9.0 µm. The active pixels include an analog-to-digital converter of 8, 10, or 12-bits and global shutter read-out. The quantum efficiency reported by the manufacturer is 0.70 at 590 nm.

In the following we present the characterization of read-out noise, angle of acceptance and cosmetics of the CMOS sensor.

Noise characterization

The main three sources of noise in an optical sensor are the read-out noise, the photon noise, and the fixed pattern noise (FPN). Read-out noise arises from the process of reading the pixel data. Photon noise is due to the quantum fluctuations of the light source and its occurrence is characterized by a

Poisson probability distribution. The FPN is caused by spatial inhomogeneities across the sensor array in the analog-to-digital converter (ADC) embedded in each pixel.

In order to characterize the noises of the sensor, the photon transfer curve (PTC) can be obtained. The PTC describes the relationship between the output signal at different flux levels and the corresponding fluctuations (standard deviation) of the output signal. [START_REF] Janesick | Photon Transfer[END_REF] We assume that the total noise of the sensor in analog-to-digital units (ADU) is σ Total (ADU) and it can expressed as

σ Total (ADU) = [σ 2 RON (ADU) + σ 2 PN (ADU) + σ 2 FPN (ADU)] 1/2 , (2)
where σ RON (ADU) is the read-out noise, σ PN (ADU) is the photon noise, and σ FPN (ADU) is the fixed pattern noise.

The total noise can be obtained as the standard deviation of the average flux on a certain region in the sensor after offset subtraction. The photon noise in ADU can be expressed as

σ PN (ADU) = S(ADU) K(e -/ADU) 1/2 , (3)
where S(ADU) is the average flux of the frame, and K(e -/ADU) is the average conversion gain of the pixels.

The fixed pattern noise is stationary and it can be removed by taking the difference of two consecutive frames acquired with the same exposure time. [START_REF] Janesick | Photon Transfer[END_REF] Then, the sum of read-out and photon noises can be expressed as

σ RON+PN (ADU) = N PIX i=1 [F 1 i (ADU) -F 2 i (ADU)] 2 2N PIX 1/2 , (4)
where F 1 i (ADU) and F 2 i (ADU) is the output signal of pixels i of two consecutive frames within a region of N PIX pixels.

After removing the fixed pattern noise, we can estimate the photon noise as

σ PN (ADU) = σ RON+PN (ADU) 2 -σ RON (ADU) 2 1/2 . (5)
In order to get results in electron unit, we need to obtain the gain of the pixel which can be expressed as

K(e -/ADU) = S(ADU) σ 2 PN (ADU) . (6)
The measurements to characterize the PTC were performed as follows. A fiber-coupled lightemitting-diode (LED) with central wavelength of 595 nm and linewidth of 80 nm was used as a light source. The beam out of the fiber back-illuminated a diffuse white-translucent surface placed in front of the sensor. Black tubing was used between the illuminated surface and the sensor to An alternative method consists in acquiring a series of dark frames with short integration time (0.01 ms) and computing the temporal standard deviation of individual pixels. The distribution of noise over the full array is shown as the histogram in Fig. 1 (right). The median read-out noise is 2.06 e -, which is consistent with the result obtained from the photon transfer curve. The tail that appears on the distribution is attributed to random telegraph noise (RTN) arising from traps at the thin-layer interface in the source-follower gate region of metal-oxide-semiconductor field-effect transistors (MOSFET) of individual pixels. [START_REF] Wang | Random telegraph signal in cmos image sensor pixels[END_REF]

Angle of acceptance

CMOS sensors have small microlenses at the surface of their pixels that enhance their photon collection efficiency. [START_REF] Zhang | Optical design of microlens array for CMOS image sensors[END_REF][START_REF] Connolly | High concentration factor diffractive microlenses integrated with cmos single-photon avalanche diode detector arrays for fill-factor improvement[END_REF] Although the on-axis sensitivity is improved, incident light at oblique angles is focalized off the center of the photosensitive area into light-insensitive structures of the pixel. This leads to a reduction in sensitivity for a light beam with a large angle of incidence. The characterization of the angle of acceptance is critical for the optical design of the wavefront sensor as it allows choosing the appropriate beam F-ratio that minimizes the detection losses.

The measurements setup is described as follows. The output beam from a fiber-coupled LED source (595 nm central wavelenght, 80 nm FWHM linewidth) is collimated with a 100 mm lens to a 23 mm diameter beam. A filter of 10 nm FWHM width centered at 590 nm is used to narrow the spectral width of the source around the sodium emission wavelength. A pupil of 4.2 mm clips the beam that is imaged with a 1:1 lens system into the center of the sensor plane. The sensor is mounted on a micrometric stage that allows on-axis and horizontal rotation. For an initial on-axis position, the sensor is rotated ±26 • in the horizontal plane. A sequence of 100 frames is obtained for each angular position. The resultant average of the 100 frames is calculated. A window of 100×100 pixels centered in the circular footprint of the beam is used for processing. The average of all pixels in the window is taken as the representative intensity of the pixels. Due to the reducing irradiance on the sensor with increasing angle (the beam becomes elliptical on the sensor plane for large incidence angles), a factor of 1/ cos(γ) is applied to the normalized intensity values, where γ is the tilt angle of the sensor plane. After the full horizontal range is measured, the sensor plane is rotated in the optical axis and a new series of measurements are taken by rotating the sensor around the horizontal plane. Repeating this process, a complete angular sensor response is characterized.

Figure 2 shows the normalized response of the sensor in eight transverse planes. In the same figure, a contour plot representation of the angular response is shown. The response of the sensor is maximal at 0 • incidence and decreases for larger angles. For each plane, the angular response is symmetric around the normal, but the acceptance angle is wider in the vertical direction. This could be explained by the presence of a rectangular photosensitive area elongated across the vertical axis.

Any systematic mismatch between the microlenses and the pixels would result in a tilt of the acceptance direction. In addition to the measurements presented in Fig. 2, we measured the angular response on 100×100 pixels windows located at the edges of the sensor in the x and y planes,

showing no difference among them in the direction of maximum efficiency nor in the angular width. This indicates that the angle of acceptance is homogeneous over the sensor.

We will show in section 4.3 how the angle of acceptance leads to light losses as a function of the focal ratio of the incident beam on the detector.

Cosmetic

Because the size of the spot on the wavefront sensor is near a single pixel within the subaperture, it is crucial that the sensor array is free of defective elements (also called cosmetic defects). Hot (bright) or cold (dark) pixels in a subaperture would cause a bias in the centroiding calculation, or a complete loss of the measurement if the defective pixel is located within the LGS spot. [START_REF] Gousset | Modeling of high-precision wavefront sensing with new generation of cmt avalanche photodiode infrared detectors[END_REF] Other cosmetic defects may include pixels with temporal instability and non-linear behaviour.

To characterize the presence of defective pixels we take a flat illuminated image with mean intensity at half the full-well-capacity, and we calculate the histogram (Fig. 3). We found no dark nor bright pixels over the entire array, which rules out any loss in performance due to defective elements.

where N T is the full width at half maximum (FWHM) of the spot on the image, N S is the side length of the sub-aperture in pixels, σ RON is the read-out noise, and S e is the number of photons per sub-aperture and per frame.

Similarly, the weighted CoG (WCoG) can be expressed as: 35

σ 2 WCoG = N 2 T 8 ln(2)S e • N 2 T + N 2 W 2N 2 T + N 2 W 2 Photon + π(N 2 T + N 2 W ) 2 128(ln(2)) 2 • σ RON S e 2 Read-out , (8)
where N W is the FWHM of a weighted gaussian function. We compare the theoretical centroiding error using the expressions above versus simulated and measured center-of-gravity errors. Figure

CoG linearity

The spot size relative to the dimensions of the pixels, i.e. the spot sampling frequency (s), can have a significant impact in the linearity of the centroid estimation as the spot size approaches the size of a pixel. Even at the accepted Nyquist sampling criteria of s = 2 pixel per FWHM, centroid non-linearities start to build up depending on the profile function on the detector. [START_REF] Robertson | Detector Sampling of Optical/IR Spectra: How Many Pixels per FWHM?[END_REF] Therefore, the selection of the spot sampling frequency in a wavefront sensor is a trade-off between minimum noise (small spot size) and high centroid linearity (large spot size). In this section we study how the centroid varies as a function of the sampling frequency and as a function of the lateral displacement of the spot over the CMOS sensor, and we compare with simulations.

The experimental arrangement consists of a fiber-coupled LED source with a fiber core of 400 µm placed at a distance of 1300 mm from a lens of 24 mm clear aperture and 40 mm focal length that forms an image of the source at the surface of the CMOS sensor located at 40 mm from the lens. In this simple configuration, the magnification of the optical system is M = 40/1300 = 0.03076. The theoretical size of the image is 12.3 µm or 1.36 pixels. A lateral displacement of the source is also magnified in proportion to M . In the current setup, the source is laterally shifted with a step of δ S = 40 µm, corresponding to a spot lateral displacement step of δ I = 1.2 µm.

We move the spot by 25.2 µm in steps of 1.2 µm over almost 3 pixels. For each step, we acquire 30 consecutive images and calculate the CoG for each frame. The average CoG relative to the initial pixel position and the standard deviation of the CoG are calculated as a function of the pixel position of the spot. In order to understand any possible effects of the acceptance angle in the linearity of the CoG, we repeat the procedure at different tilt angles of the sensor such that the CoG linearity can be evaluated for several angles of incidence.

The CoG at each angle of incidence θ and for a given spot sampling frequency s can be represented as a linear function plus an oscillating term as follows:

CoG (θ,s) (x) = A x + B Linear + W s sin(2πx + φ x ) Residual , (9)
where x is the pixel displacement, A and B are parameters of the linear CoG response, W s is the amplitude of CoG oscillations at a sampling frequency s, and φ x is an arbitrary pixel phase. Figure 7 shows the residual of the data shown in Fig. 6, i.e. the difference between the measured CoG's and the linear fit. This corresponds to the residual term of Eq. 9. We show the residuals data obtained at normal incidence and for three spot sizes: 1.10 pixel FWHM, 1.13 pixel FWHM, and 1.34 pixel FWHM, that were obtained by slightly shifting the focal plane in the optical axis direction. The spot size are estimated using a Gaussian fit and their values correspond to the spot sampling frequency s. For each measurement, a sine function is fit to the data (blue curve)

and the result of a simulation is also displayed (red curve). There is a good agreement among simulations, the fit curve, and measurements. The amplitude of the residual CoG, i.e. the degree of non-linearity, is described by the parameter W s in Eq. 9. The value of W s for each measurement is shown in the figure. For the most undersampled case (s = 1.10 pixel), the degree of nonlinearity reaches 4.2% of a pixel and for the least undersampled case (s = 1.34 pixel) the degree of non-linearity is reduced to 1.0% of a pixel. These measurements show that the increase in CoG non-linearities in the CMOS sensor under study behave as expected, and that sampling the spot frequency below the Nyquist criteria yield a degree of non-linearities that is relatively small compared to the pixel size. Note that in the case of elongated spots, as expected for ELTs, the sampling will be different along the short and long axes of the spots. The conditions reproduced here correspond to the worst case expected for the short axis. In the elongation direction, the sampling of the spot will likely be above the Nyquist criteria, hence the linearity error vanishes.

The estimated spot size and the linearity response include any cross-talk effect between adjacent pixels, however, we assume that cross-talk is negligible (<1%) based on studies performed on a similar CMOS sensor [START_REF] Estribeau | CMOS pixels crosstalk mapping and its influence on measurements accuracy in space applications[END_REF] and the fact that microlenses minimize this effect.

Transmission loss due to angle of acceptance

The angular response characteristic of the CMOS sensor gives rise to a transmission loss through the focalizing element (e.g. lenslet array of the Shack-Hartmann wavefront sensor) as off-axis rays are focalized into the sensor with a slanted angle of incidence.

The photon flux transmission due to the angle of acceptance can be estimated as:

η acc = +α -α Ĝ(x, y)dxdy H(α) , (10)
where Ĝ(x, y) is an estimate of the normalized angular response obtained with interpolation of the measured data over the horizontal and vertical angular directions (see Fig. 2), H(α) is a function that describes the lenslet window seen from the detector, and α is the beam detector angle given by

α = 1 M arctan + 1 2 1 2F , ( 11
)
where F is the lenslet nominal side F-number, ≤ 1 is the linear fill factor of the lenslet array, and M is the magnification of any optical relay between the lenslet array and the sensor plane.

The beam F-number on the detector side is F d = 1/(2 tan(α)). For the case of a square lenslet H square (α) = 4α 2 and for the case of a circular lenslet H circular (α) = πα 2 . These expressions assume no loss between the lenslet array and the detector other than the detector angular response.

We also assume image telecentricity, i.e. the chief rays are always at normal incidence on the detector, independent of the position of the lenslet over the pupil and of the distance of the object from the center of the field of view.

Assuming = 1 (no apodization in the lenslet array) and the measured angular response of the CMOS sensor, we estimate the transmission through a Shack-Hartmann wavefront sensor as a function of the detector F-number for the case of a circular and square lenslet configuration, as shown in Fig. 8. A reduction in transmission of 4% and 6% occurs at f /3.0 for the circular and square lenslet, respectively. Smaller beam F-ratios lead to a stronger reduction in transmission as the beam is focalized at larger angles. This analysis shows that purely geometric considerations in the design of a Shack-Hartmann wavefront sensor with a CMOS sensor, result in light losses that should be taken into account to minimize the impact in the overall throughput of the optical system.

Examples of implementation of a CMOS detector into a LGS WFS

In this section we provide a preliminary design of a full LGS WFS arm for the ESO ELT and the TMT. For the former, we take as an example the Laser Tomography Adaptive Optics (LTAO) system of HARMONI, [START_REF] Thatte | HARMONI: first light spectroscopy for the ELT: instrument final design and quantitative performance predictions[END_REF] which will make use of the 6 LGS provided by the ESO ELT. For the latter, we show the implementation for NFIRAOS, [START_REF] Crane | NFIRAOS adaptive optics for the Thirty Meter Telescope[END_REF] the TMT Multi-Conjugate Adaptive Optics (MCAO) system. The goal of this section is not to report on a final design for the these instruments, but rather to show that a practical implementation of the CMOS sensor described in this article is feasible in LGS WFS.

HARMONI design

The main parameters of the LGSWFS for HARMONI are summarized in Table 1. To decrease the maximum angle of arrival on the detector from LGSS, we propose to use a double lenslet concept. Figure 9 shows the ray tracing for a classical lenslet and a double lenslet [START_REF] Hawker | High-resolution spectroscopy and high contrast imaging with the ELT: looking for O 2 in Proxima b[END_REF] . The double-lenslet has the advantage of creating a telecentric image and of reducing the steepest beam angle by half. For the case of a classical lenslet placed on top of the detector, the maximum beam angle at the edge of the sub-aperture is given by

θ single m = arctan d f = arctan 1 F ≈ 1 F , (12)
where d and f are the lenslet diameter and focal length, respectively, and F is the lenslet focal ratio. However, for a double lenslet with equal focal length on each curved face, the maximum exit beam angle from the second lenslet face (a telecentric image plane) is equal to the on-axis beam given by

θ double m = arctan d 2f = arctan 1 2F ≈ 1 2F . ( 13
)
The maximum beam angle in the double-lenslet configuration is one half with respect to the maximum beam angle of a single lenslet, and it is also equal for on-axis and off-axis objects, i.e.

it provides the same beam angle over the full field of view (FoV).

For LTAO, a FoV of at least 16×16 arcsec2 is required. As described above, one of the challenges imposed by the CMOS detector arises from the acceptance angle. The optical design of the lenslet array must then be carefully thought in order to minimize flux loses at the coupling with the detector. The acceptance angle is linked to the maximum focal ratio that can be accepted by the detector.

The focal ratio of the beam onto the detector plane is determined by specific parameters and the following formula:

F d = N • d D • β , ( 14
)
where N is number of sub-apertures, d is the pixel size, D is the telescope pupil diameter and

β

Optical Relay

Due to the wide FoV required for LTAO, the focal length of a lenslet array placed in front of the detector would be very short (near 0.5 mm as it can be calculated in the previous section), which makes it technically difficult to assemble inside the detector chip. This problem is common with other ELTs instruments, and similar conclusions apply to NFIRAOS as well. The implementation of an optical relay between the lenslet and the detector increases the overall size and the number of elements in the WFS, but it also relaxes the manufacturing complexity and tolerances of the lenslet array design. It also allows for a better management of the beam angles and acceptance within the detector. Therefore, an optical relay has three purposes: i) decouple the lenslet array focal plane from the detector focal plane, ii) reimage the telecentric image plane from the double-lenslet array at the detector plane, and iii) compress the pupil size from the lenslet array pupil to the detector size. The pupil diameter on the lenslet array is fixed to be 24 mm, due to other optical and manufacturing constraints. The pupil size on the detector is 9.792 mm, hence the magnification factor is M = 1/2.45. In order to provide high optical performance, both in terms of image quality and distortions, a six-lenses design has been proposed as shown in Fig. 10. The overall performance of this relay has been specified such that the distortion shall be less than ±0.03 sub-aperture with respect to a perfect grid, with a variation of less than ±0.01 sub-apertures within operating conditions during the instrument lifetime. In terms of optical quality, the relay does not degrade the quality of the spot image when taking onto account the quadratic sum of the contributors to the wavefront error budget. This relay also preserves the telecentricity, as this is an important factor for coupling light with detector pixels (see Section 5.1.1), and the telecentricity error is less than ±1.5

• at the detector level. Although the system contains a large number of optical surfaces, the penalty in terms of transmission budget is minor since highly efficient monochromatic anti-reflective (AR) coatings are available. High performance coatings with less than 0.25% reflectivity are considered here. In summary, the HARMONI design employing a double sided lenslet array with an optical relay has several advantages:

• Reduction of the beam angle after the lenslet array.

• Creation of a telecentric image.

• Using a thick substrate of 3.75 mm, the focus of the lenslets can be on the backside of the substrate, therefore printing the same lenslet with the same focal length.

• Reduction of the size of the optics inside the relay.

• Reduction of the distortion of the relay optics.

The technical feasibility of such double lenses has been verified with industrial companies, and no issues have been identified. A prototype has been built and tested, showing the conformity of the lenslet built with HARMONI specifications.

TMT NFIRAOS design

The current baseline for NFIRAOS is provided in table 2. One interesting feature of the CMOS detector is that the read-out architecture can be configured to skip rows. One can therefore decide to only read a region of interest (ROI), the full width of the detector, and the maximum frame rate is increased in proportion to the number of rows skipped.

Since TMT has a smaller diameter and will launch its LGSs from behind the secondary mirror, NFIRAOS will see significantly less-elongated spots than HARMONI. The FoV of the NFIRAOS WFS subapertures does not need to be as large and therefore only a portion of the detector can be read. This opens a tradeoff space between the number of sub-apertures, the number of pixels per sub-aperture and the maximum frame rate.

For NFIRAOS, simulations show that a 10 arcsec sub-aperture field of view is sufficient for all simulated sodium profiles with no penalty due to truncation and a pixel scale of 1 arcsec is optimal except for very poor seeing conditions (r 0 ≈ 0.1 m) where a larger pixel scale could provide better

performance. We add one extra pixel per sub-aperture to accommodate slope offsets. It was also found that slightly over sampling the pupil with 75×75 sub-apertures, compared to the 60×60 deformable mirror (DM), helps to reduce the wavefront reconstruction error, especially in poor seeing conditions or higher signal level cases than our conservative baseline.

The minimal number of pixels required to accommodate the NFIRAOS configuration is 825×825 (11 pixels per sub-aperture over 75 sub-apertures). However, the CMOS camera will read 848×1608 pixels. The extra pixels are allocated among various optomechanical tolerances, as described in the next section.

With this design, the maximum achievable frame rate is slightly over 600 Hz which is still acceptable for the expected LGS signal levels and wind speed.

ROI flexibility and tolerancing

The WFS concept permits loosening or even avoiding various traditionally tight tolerances due to: the flexible readout region; the 23 additional pixels; and an array of 100×100 lenslets.

For example, oversampling the 60×60 DM actuator grid completely removes the strict alignment tolerances to register actuators to lenslet corners, which are usually needed for a Fried geometry. Furthermore, to handle DM pupil illumination shifts at the oversized 100×100 lenslet array, software can select an arbitrary set of lenslets. However, tolerances on magnification of the pupil image remain constrained, because sub-apertures are discretized into 11 pixels. E.g. to read 76×76 sub-apertures would require 11 rows of pixels, too large a fraction of the 23 pixel margin.

The most innovative use of the extra pixels is to handle slope offsets larger than the notional 1 arcsecond budget for non-common path aberration (NCPA) calibration. But that budget applies per sub-aperture. The square regions of pixels for each spot do not have to lie on a square grid.

By adding "leap pixels" periodically between sub-apertures (Fig. 11 left), larger dynamic range of offsets can be calibrated, providing they are slowly varying across the pupil, which is the case for low-order aberrations.

One important situation is differential focus among six LGS WFSs. Time-varying global (common) distance to the sodium layer will be compensated by changing the optical path length to the WFSs via a trombone consisting of two mirrors in a V on a moving stage. However, one trombone cannot exactly compensate focus for all LGSs unless they are built and installed perfectly. Differential focus produces a different magnification of the spot pattern among the WFS, and deducts from the slope budget. However we can fix it in software by "stenciling" 11×11 pixels from the image. The stencils are chosen to always keep the slope offset within 0.5 pixel of the center.

Note that to avoid collisions between sub-aperture ROI stencils, we can only add space between them. So for e.g. astigmatism where the calibrated spot pattern is compressed in one axis and expanded orthogonally, the trombone controller calibration would be biased to always expand the pattern.

As shown in the right panel of Fig. 11, clocking of the lenslets versus the detector is handled in software. Note that because the outer active DM actuators are not in a circle, but actually a polygon with flat sides of several actuators in a line, clocking the spot pattern as shown does mean that WFS spots at vertices of the polygon do move outwards by approximately a pixel. However, the most difficult constraint remains the profile tolerance (single digits of microns for tilts plus piston) of the detector with respect to the lenslets due to defocusing in fast beams.

When NFIRAOS operates at -30 • C thermo-mechanical analysis of the camera design indicates that the detector moves ≈ 20 µm axially towards the lens mounting interface and the optical relay shrinks in the opposite direction, compared to room temperature. We will jointly optimize the athermalization of the relay lens barrel, described below, to account for both.

Lenslet array

For NFIRAOS, we have N = 75, d = 9 µm, D = 30 m, β = 1 arcsec/pixel, providing a focal ratio of F d = 4.64 at the detector. The steepest angle of incidence at the edge of the field of view with a conventional lenslet array would be θ single m = 12.2 • resulting in light loss due to the limited acceptance angle of the CMOS pixels. This angle, and therefore the loss, would be further increased because of our proposed scheme to skip pixels in order to use larger slope offsets (section 5.2.2). This motivates the use, like HARMONI, of a double-sided lenslet array, illustrated in Fig. 9.(b) where the second surface acts as a field lens to produce a telecentric image at the detector, thus reducing the steepest angle by half. For the proposed NFIRAOS design, the main parameters of the required lenslet array are 210 µm pitch, a radius of both surfaces of 0.945 mm and thickness of 3 mm. Such a lenslet array is considered well within the capabilities of manufacturers.

Optical relay

For NFIRAOS, the pupil diameter on the lenslet array was chosen to be 15.75 mm, leading to a relay with magnification M = 1/2. Smaller pupil sizes make the relay shorter and therefore easier to package, but the lenslets become faster, and therefore significantly more challenging and expensive to fabricate. The 15.75 mm pupil diameter was chosen as a reasonable tradeoff.

The proposed relay is shown in Fig. 12. It has six lenses and is actually quite similar to that of HARMONI. The only possibly concerning element is the F2 lens, which exhibits a large curvature that could be costly to fabricate. The full optical path from the sodium layer, through TMT and NFIRAOS, and through the lenslet and relay to the detector, has been modeled. The images from the top and bottom of the sodium layer are easily resolved in the model. The glasses chosen for this design are all highly transmissive in the visible spectrum, with a bulk absorption of <1%. The overall throughput will therefore depend on the quality of the coatings. As in HARMONI, NFIRAOS plans to use high performance monochromatic dielectric coatings.

We have evaluated the performance of a CMOS sensor compatible with the current requirements of wavefront sensor of laser guide stars in the context of extremely large telescopes.

We have shown that the read-out noise of ≈3 e -is achievable for a large sensor array. The statistical distribution of read-out noise over the sensor shows a tailed shape which is characteristic of CMOS sensors. The impact of this read-out noise excess in the centroid estimation accounts for a factor of <2 above 500 photons/sub-aperture/frame.

The average angular response of the sensor was characterized showing a two-axes symmetry with full width half maximum of 42.6 • in the vertical direction and 25.4 • in the horizontal direction.

The angle of acceptance leads to a light transmission loss depending of the beam aperture on the sensor. For a square lenslet, a drop of 10% in transmission is found for a beam focal ratio on the detector of F d = 2.5. We provide the calculated transmission curves for circular and square lenslet shapes as a reference for wavefront sensor designers using this type of detectors.

The error of center of gravity was employed as a metric to evaluate the performance of the detector to wavefront sensing. We simulated and measured the CoG errors as a function of the photon flux and found a good agreement between theory and experimental results. The centroiding linearity was measured for different spot size and angles of incidence. The rising of non-linearities in the estimation of the CoG is in agreement with our simulations and shows that for a sampling frequency of 1.36 pixel per FWHM (Nyquist undersampled), the degree of non-linearities is 1.0% of a pixel.

Finally, we show two examples of practical implementations of this detector in LGS wavefront sensors for ESO ELT/HARMONI and TMT/NFIRAOS adaptive optics systems. The need of additional relay optics between the microlens array and the detector is common in both cases due to the differences in size between the CMOS sensor and the pupil. Moreover, the telecentric double-sided lenslet array in the HARMONI design, also adopted in NFIRAOS, comes as an innovative solution to achieve the required sub-aperture FoV despite the CMOS architecture intrinsically limiting the acceptance angle into the pixels. In the case of NFIRAOS, only a sub-region of the detector needs to be read, which allows operating at higher frame rate, as well as greatly relaxing key opto-mechanical tolerances. For HARMONI, a larger LGS elongation is expected and all pixels of the detector are needed to accommodate a larger sub-aperture FoV that minimizes truncation over most of the pupil. These two examples show that this type of detector is very suitable for LGS wavefront sensing on extremely large telescopes.

the first light Integral Field Spectrograph instrument for the European ELT, assisted by Laser Tomography AO.

Biographies of other authors are not available.

  photon noise sets in and follows a linear relationship on the log-log coordinates as shown in yellow squares and with a linear fit. At high levels of signal pixels start to saturate. The full well capacity S FW characterizes the saturation point and it can be calculated by the product between the signal value in ADU at the saturation point and the gain. Then, the estimated read-out noise, full well capacity and gain are σ RON = 3.05 ± 0.15 e -, K = 0.2473 ± 0.012 e -/ADU, and S FW = 931 e -, respectively.

Fig 1 (

 1 Fig 1 (Left) Measured photon transfer curve of the CMOS detector. (Right) The histogram of read-out noise.

Fig 2 (

 2 Fig 2 (Left) Normalized pixel angular response of CMOS detector in eight transverse planes (Right) Contour plot of the averaged-normalized angular pixel response.

Fig 3 2 = N 2 T 8

 3228 Fig 3 Logarithmic histogram of the flat illuminated image. No dead nor hot pixels are found.

4

  photon-noise and read-out-noise components of the theoretical centroiding variance according to equations 7 and 8. We assumed σ RON = 2.06 e -, as measured previously. Using N S = 5 pixels and N W = 4 pixels, read-out noise dominates the centroiding error in the low-flux regime below ≈ 4× 10 2 (photons/sub-aperture/frame) in the case of CoG estimation, and below ≈ 2×10 2 (photons/subaperture/frame) for WCoG. The solid-blue line is the total variance of the CoG estimators. The green and orange squares are simulated centroiding errors. A gaussian spot of FWHM = 1.5 pixels was simulated on a 13×13 pixels sub-aperture. Photon noise was added to the simulated spot, as well as read-out noise following the skewed distribution shown in Fig.1. The centroids of 500 simulated spots were estimated for each flux level using the CoG and WCoG methods. The simulated data points in the figure show the temporal variance in the x and y direction of the sequence. In addition, centroiding measurements were performed by focalizing a spot of FWHM = 1.5 pixels at the center of the sensor. The width was estimated by a gaussian fit on the measured spot. A sequence of 500 frames with 2 ms integration time was obtained for each flux level, and the variance of the CoG sequence was calculated which corresponds to the centroiding error shown in Fig.4. There is a good agreement between the simulated errors and the measurements, and a reasonable agreement with the theoretical curves. The WCoG is able to reduce the centroiding error by a factor of ≈2 at a nominal flux of 1000 (photons/subaperture/frame).

Fig 4 (

 4 Fig 4 (Left) Comparison of error variance of CoG among real measurements, simulation and theory. (Right) Comparison based on weighted CoG.

Fig 5

 5 Fig 5 Centroiding error based on a theoretical Gaussian distribution of read-out noise and measured skewed distribution of read-out noise.

Figure 6

 6 Figure 6 shows the calculated CoG relative to the initial pixel position as a function of the pixel displacement for incidence angles between -20 • and +20 • . A linear fit is estimated for each data set. The values of the slopes of the linear component of the CoG (parameter A) for all tilt angles are shown in the inset table in the same figure. The measured linear slope deviate less than 5% with respect to the ideal linear response (A = 1), showing a small effect on the linearity as a result of the angle of acceptance.

Fig 6

 6 Fig 6 Measured CoG as a function of the pixel displacement with the sensor tilted at five different angles. A linear fit is applied to each data set. The spot sampling frequency was estimated as 1.13 pixels FWHM. The linear slope parameter A for each data set is shown at the top left.

Fig 7

 7 Fig 7 Residual CoG as a funcion of the pixel displacement compared to a sine fit function and simulations for a spot sampling frequency of (a) 1.10 pixels FWHM, (b) 1.13 pixel FWHM and (c) 1.34 pixel FWHM. All measurements obtained at normal incidence.

Fig 8

 8 Fig 8 Transmission efficiency due to angle of acceptance of a CMOS sensor as a function of the detector side beam F-number.

Fig 9

 9 Fig 9 Schematic ray tracing comparison between (a) single lenslet in front of the detector and (b) double lenslet fabricated in the same substrate. In the double lenslet, an optical relay is required to re-image the telecentric focal plane on the detector plane. The maximum incidence angle on the sensor plane is reduced by half with respect to the single lenslet, and chief rays are parallel to the optical axis across the full FoV.

  is the on-sky pixel scale. For N = 68, d = 9 µm, D = 39 m and β = 1.1 arcsec/pixel, the detector beam focal ratio is F d = 2.94 corresponding to a beam detector angle θ d = 9.64 • , following the relationship θ d = arctan(1/(2F d )). A total of 68 sub-apertures require 1088 pixels, or 16 pixels per sub-aperture. If we consider 1 guard pixel between sub-apertures (for alignment margin purposes), there are 15 useful pixels per sub-aperture, covering a total FoV of 16.5 arcsec. The maximum beam angle from the telecentric image plane θ double m is related to the detector beam angle θ d as θ double m ≈ θ d • M , with M the magnification of the relay. Using M = 1/2.45, then θ double m = 3.94 • and F = 7.27 (Eq. 13). Considering the pupil of 24 mm and 68 sub-apertures, a double lenslet array with 353 µm lenslet pitch is required. The focal length of the lenslet can be found as f = F • d , which gives f = 2.57 mm. Both powered surfaces of the double-lenslet are manufactured in the same substrate made of fused silica with index of refraction n = 1.4584 at 589 nm, therefore the double lenslet must have a thickness of f × n = 3.75 mm.

Fig 10

 10 Fig 10 Ray tracing diagram of the HARMONI LGS wavefront sensor, depicting the double-lenslet array, optical relay and detector. The overall length of the relay is about 150 mm.

Fig 11 (

 11 Fig 11 (Left) Leap Pixels for low order NCPA. (Right) Software defined stencils for clocking lenslets versus detector.

Fig 12

 12 Fig 12 Ray tracing diagram of the lenslet, optical relay and detector. The overall length of the relay is about 380 mm.

Table 1

 1 Specifications of the HARMONI LGS WFS.

	Parameter	Value	Comment
	ESO ELT primary mirror diameter	39 m	Size of the pupil
	# LGS	6	Side launch provided by 4 launch stations (2×2 + 2×1)
	# Subaperture	68×68	Spatial sampling of 57 cm. Square lenslets.
	# pixels per subaperture	16×16	with at least 15×15 useful pixels
	LGSWFS pixel scale	1.1 arcsec/pixel	Required for sampling LGS spots
	Subaperture Field of View	16.5 arcsec	Side FoV. Required for minimizing truncation
	5.1.1 Lenslet Array

Table 2

 2 Specifications of the NFIRAOS LGS WFS.

	Parameter	Value	Comment
	TMT primary mirror diameter	30 m	Size of the entrance pupil
	# LGS	6	Central launch provided by a single launch station
	# Subaperture	75×75	Spatial sampling of 40 cm
	LGS WFS pixel scale	1.0 arcsec/pixel	Required for sampling LGS spots
	Subaperture Field of View	11 arcsec	Required for avoiding truncation
	5.2.1 Detector configuration

Although individual lenslets have a square geometry, we assume inscribed circular optics in the following calculations. Diagonal beam apertures are √

2 faster than side beam apertures.

Acknowledgments Z.K. acknowledges financial support from China Scholarship Council award no. 201806010330. This project received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 893150. This work also benefited from the support of the WOLF project ANR-18-CE31-0018 of the French National Research Agency (ANR). This document has been prepared as part of the activities of OPTICON H2020 (2017-2020) Work Package 1 (Calibration and test tools for AO assisted E-ELT instruments). OP-TICON is supported by the Horizon 2020 Framework Programme of the European Commission's (Grant number 730890). This work was supported by the Action Spécifique Haute Résolution Angulaire (ASHRA) of CNRS/INSU co-funded by CNES. This work has been partially supported by the LabEx FOCUS ANR-11-LABX-0013


Manuel Trotta
email: manuel.trotta@emse.fr

Claudia Archetti

Dominique Feillet

Alain Quilliot

Pickup and delivery problems with autonomous vehicles on rings

Introduction

In this work we investigate on-demand transportation services carried out using autonomous vehicles on circular networks. We called these problems Pickup and Delivery Problems on Rings (PDP-R). Concerning problems defined on circles, the exisiting literature is limited. In [START_REF] Guan | Routing a vehicle of capacity greater than one[END_REF] the multiple capacity nonpreemptive vehicle routing problem on cycles is studied. Gendrau et al. [START_REF] Gendreau | Heuristics for the traveling salesman problem with pickup and delivery[END_REF] developed a linear time exact algorithm for the Single-Vehicle Pickup and Delivery Problem defined on a cycle graph. Tzoreff et al. [START_REF] Tzoreff | The vehicle routing problem with pickups and deliveries on some special graphs[END_REF] studied the Vehicle Routing Problem with Pickup and Delivery on some special graphs.

2 Problem description, classification scheme and complexity results [START_REF] Trotta | Pickup and delivery problems with autonomous vehicles on rings[END_REF] and can be described as follows. The context is that of a circular layout (a ring) with m stations, numbered from 0 to m -1 in a clockwise direction. The distance from station j to station j + 1 is denoted as δ j,j+1 and L = m-2 j=0 δ j,j+1 + δ m-1,0 is the total length of the ring. The problem consists in scheduling a set R of n transportation requests where each request i ∈ R asks for the transportation of a quantity of goods (or number of people) q i from a pickup station s i to a delivery station t i . Each request specifies also a release date r i and a due date d i , that correspond, respectively, to the earliest time for pickup and the latest time for delivery. A fleet of V vehicles of capacity Q is available at the depot (station 0) to serve the transportation requests. All the vehicles start their tours from the depot and get back to it when all requests are served. One of the contributions of this work is a classification scheme for PDP-R problems based on three fields α|β|γ where α contains information about the number of vehicles and vehicle capacity, β specifies whether vehicles travel in one or both directions, whether release and due dates are defined and whether request have unitary demands, and γ corresponds to the objective function. Table 1 summarizes the words that compose the fields together with their meaning.

PDP-R have been introduced in

Field

Name Description

α 1 or V > 1 number of available vehicles 1 or Q > 1 or Q v vehicle capacity (Q v if
(if i is completed in tour k) or k + 1 if it is completed in tour k + 1.
Then, the objective is to minimize CLT where CLT ≥ V v=1 K k=1 c ik x ikv (1 ≤ i ≤ n) subject to the constraints that all requests must be satisfied and that vehicle capacities cannot be exceeded. K represents an upper bound on the number of tours needed. We then strengthened the formulation with some symmetry-breaking constraints imposing that the i first requests have to be assigned to vehicles in set {1, . . . , i}. We generated randomly 5960 instances. We set m = 10 stations, n requests (n ∈ {20, 40, 80, 160}) random distances between consecutive stations in [START_REF] Guan | Routing a vehicle of capacity greater than one[END_REF]10], V ∈ {1, 2, 3} and Q ∈ {1, 2, 4, 8}, random demands in [1, Q] and four combinations for release and due dates: t-t, t-w, w-t, w-w (with t = tight and w = wide). We compared the performances of the formulation with a simple greedy algorithm in which vehicles turn all together along the ring and if a vehicle is at a station m and a request i with starting station m can be served, i is assigned to v. If multiple requests can be served at the same time, the algorithm breaks ties by sorting them according to the following criteria (taken in this order): earliest due date, largest demand, longest distance to reach the delivery node. We solved all instances (to optimality or proven infeasible) with CPLEX 12.9.0. Table 3 K k=1 c ik x ikv . We ran computational tests on the same instances used for V, Q|sd, r i , d i |CLT , but this time we set a time limit of 30 minutes. CPLEX solved 3014 out of 3123 feasible instances (a feasible solution or infeasibility proven for all instances). We compared the performances of the model with a greedy algorithm similar to the one described in section 3 that breaks ties among requests by sorting them according to the following criteria (taken in this order): earliest due date, shortest distance to reach the delivery node, largest demdand. Table 4 summarizes the computational results. Problem on a circle. This problem is polynomial-time solvable [START_REF] Atallah | Efficient solutions to some transportation problems with applications to minimizing robot arm travel[END_REF]. We propose an alternative algorithm for it. The variant where vehicles can have arbitrary capacity is denoted by 1, Q|bd, u|CLT . This variant is also know as the multiple capacity nonpreemptive vehicle routing problem on cycles. In [START_REF] Guan | Routing a vehicle of capacity greater than one[END_REF] it is proven NP-hard. As a consequence, all variants where vehicles have capacity more than 1 are NP-hard. We proposed an ILP formulation for variant V, Q|bd, u, r i , d i |CLT and 2 MILP formulations for variant V, Q|bd, r i , d i |CLT .

Table 1 :

 1 Name and description of the various words of the fieldsWe obtained the following results related to the computational complexity of different classes of problems.

		bd		both directions
		r i	pickups are subject to release dates
		d i	deliveries are subject to due dates
		u		demands are unitary
		C max		makespan
	γ	C i		total completion time
		CLT		closing time
		Name	Complexity	Proof
		1, 1|sd, u|CLT	P	Exact algorithm
		V, 1|sd, u|CLT	NP-hard	Reduction from 3-SAT
		1, Q|sd, u|CLT	NP-hard	Equivalent to V, 1|sd, u|CLT
		1, 1|sd, u, r i , d i |CLT	NP-hard	Reduction from (γ, µ)-Colouring
		1, 1|sd, u| C i	NP-hard	Reduction from Sum Colouring
		1, 1|bd, u|CLT	P	Exact algorithm(s)
		1, Q|bd, u|CLT	NP-hard	[1]

they have different capacities) β sd single-direction (clockwise or counterclockwise) md mixed single-direction (each vehicle follows a single direction)

Table 2 :

 2 Summary of the complexity results of the problems addressed problem are NP-hard. We developed an ILP model to solve the most general variant (V, Q|sd, r i , d i |CLT ). In this model there is only one kind of decision variable x ikv equal to 1 if request i is started in tour number k and assigned to vehicle v. The cost c ik of starting request i in tour k is either k

3 Single direction and closing time objective function

The simplest variant in this class is 1, 1|sd, u|CLT . We proved it has polynomial-time complexity by describing an exact algorithm. We proved that all possible generalizations of this

Table 3 :

 3 Maximum CPU time and greedy GAP for CLT instances

	4 Single direction and total completion time objective func-
	tion
	We proved that the simplest variant in this class (1, 1|sd, u| C i ) is NP-hard by reduction
	from the Sum Colouring Problem that is NP-complete. As a consequence, all possible
	generalizations are NP-hard. We used an ILP model based on the model described in
	section 3 with a different objective function, i.e. min	i∈R	V v=1

Table 4 :

 4 Maximum CPU time and greedy GAP for C i instances5 Both directions and closing time objective functionThe simplest variant in this class is 1, 1|bd, u|CLT and it is also known as the Stacker Crane

	β	max CPU(s) max greedy GAP(%) (opt.) max greedy GAP(%) (feas.)
	sd, u	3.3	6.3	-
	sd, u, r i , d i	1.6	46.7	-
	sd	1800	17.5	16.5
	sd, r i , d i	1800	30.2	10.9