Othmane Belmoukadam
email: othmane.belmoukadam@inria.fr

Chadi Barakat
email: chadi.barakat@inria.fr

QoE-driven Cache Placement for Adaptive Video Streaming: Minding the Viewport

To handle the increasing demand for video streaming, ISP's and service providers use edge servers to cache video content to reduce the rush on their servers, balance the load between them and over the network, and smooth out the traffic variability. The dynamic adaptive streaming over HTTP protocol (DASH) makes videos available in multiple representations, and end-users can switch video resolution as a function of their network conditions and terminal display capacity (e.g., bandwidth, screen resolution). In this context, we study a viewportaware caching optimization problem for dynamic adaptive video streaming that appropriately considers the client viewport size and access speed, the join time, and the characteristics of videos. We formulate and study the proposed optimization problem as an Integer Linear Program (ILP) that balances minimal join time and maximal visual experience, subject to the cache storage capacity. Our framework sheds light on optimal caching performance. Our proposed heuristic provides guidelines on the videos, and the representations of each video, to cache based on the video popularity, its encoding information, and the distribution of end-user display capacity and access speed in a way to maximize the overall end-user QoE.

I. INTRODUCTION

The internet hosts plenty of services of all categories putting considerable pressure on its infrastructure, with internet video traffic being unavoidably the nightmare of operators. It is expected that by 2023, video traffic will account for 73% of the global mobile data traffic [START_REF] Ericsson | Ericsson Mobility Report[END_REF]. Lately, with the pandemic and the mobility restrictions, real-time entertainment based on streaming video and audio has become even more critical and has accelerated this continued growth [START_REF] Feldmann | The lockdown effect: Implications of the covid-19 pandemic on internet traffic[END_REF]. End-users expect the best quality and can be frustrated by any service interruption, hence resulting in considerable economic losses for providers. In light of this rapid growth and increased economic impact, internet service providers feel more pressure to optimize their networks to meet the expectations of their end-users. For example, to prioritize or load balance traffic efficiently, ISP's need information on end-users QoE rather than just capturing the network Quality of Service (QoS). But, video QoE is dependent on the content itself (i.e., the video bitrate and resolution) and on the application-level QoS metrics such as the start-up delay, the duration of stalls, and the resolution switches [START_REF] Pastrana-Vidal | Sporadic frame dropping impact on quality perception[END_REF]- [START_REF] Moorthy | Video quality assessment on mobile devices: Subjective, behavioral and objective studies[END_REF]. It also depends on the viewport size [START_REF] Cermak | The relationship among video quality, screen resolution, and bit rate[END_REF], which can be defined as the number of pixels, both vertically and horizontally, on which the video is displayed. However, in the era of data encryption, all these metrics impacting the end-user QoE can be hard to infer.

Caching is another solution emerging through the surface. The main question is how to select the appropriate video to cache to maximize the overall users' QoE without exceeding the cache storage capacity. Several papers in the literature tackle the caching aspect for multimedia, in particular for video content (Sec., II). However, in the light of diverse and advanced equipment, the limitation of existing caching schemes and QoE-driven optimizations is overlooking the end-user display capacity. Studies have shown that different viewport resolutions have different bandwidth requirements even for the same QoE level [START_REF] Cermak | The relationship among video quality, screen resolution, and bit rate[END_REF]. On the same topic, we were able to leverage the existing relationship between screen resolution, video resolution, and QoE to formulate a resource allocation problem that maximizes the QoE for a set of users streaming videos over the same bottleneck link [START_REF] Belmoukadam | On accounting for screen resolution in adaptive video streaming: A qoe-driven bandwidth sharing framework[END_REF]. In this work, we propose a new cache placement optimization framework for adaptive video streaming that jointly accounts for the impact of end-user display capacity and video characteristics (e.g., encoding bitrate and popularity) in addition to the internet access speed. In plan, we formulate the optimal cache placement problem as an Integer Linear Program (ILP) aiming to maximize the average QoE over a set of users with a constraint on the cache storage capacity. The optimal solution, using CPLEX [START_REF] Ibm | ILOG CPLEX optimization studio[END_REF], can find the best selection of videos and representations to cache, ensuring minimal join time and maximal visual experience. Further, we develop a practical greedy caching heuristic using the optimal placement's footprint, offering a near-optimal performance in terms of average QoE per request. Overall, the main contributions of our paper are as follows; (i) We formulate the optimal cache placement problem for adaptive video streaming, the proposed framework leverages the users' viewport size heterogeneity and allocates the cache storage based on an objective function reflecting the QoE relation to the video content (bitrate), the applicationlevel QoS (join time), the viewport size and the access speed distribution; (ii) We propose a near-optimal heuristic called QoEscoreM ax to solve for the optimization problem in a greedy way. We introduce a metric called QoEscore to rank video representations and decide about caching them or not. This metric incorporates the expected QoE resulting from caching a particular representation of a certain video; (iii) We conduct simulations with multiple settings and show that our heuristic outperforms legacy caching strategies in terms of QoE gain.

II. RELATED WORK

Caching is an attractive solution for handling the increasing demand for video content. In particular, mobile edge caching (MEC) leverages storage capacity within the network to host popular multimedia content, easing video traffic delivery, smoothing its variability, and reducing congestion and access delay [START_REF] Abbas | Mobile edge computing: A survey[END_REF], [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. Authors in [START_REF] Liu | Caching at the wireless edge: design aspects, challenges, and future directions[END_REF] discuss thoroughly the benefits and limitations of caching content at the wireless edge and the needs to be considered for designing cache placement strategies. They also introduce methods to predict the popularity distribution and user preferences. Always in the wireless context, researchers have proposed the use of small cells called "helpers" to add caching functionality at the cellular access. The femtocache approach incorporates a wireless distributed caching network that assists the base station by handling requests of popular files that have been cached, thus minimizing the download delay of users [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF], [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF]. The work in [START_REF] Poularakis | Approximation algorithms for mobile data caching in small cell networks[END_REF] formulates a joint routing and caching problem while considering the bandwidth capacity constraints of the small cell base stations (SBS), aiming to maximize the fraction of content requests served locally by the deployed SBS's. Sengupta et al. propose an architecture to identify popular multimedia content by proactively pushing it close to the edge of the wireless network, thereby alleviating backhaul load [START_REF] Sengupta | Cache aided wireless networks: Tradeoffs between storage and latency[END_REF].

To the best of our knowledge, the literature is still missing a study that accounts for the viewport resolution and its heterogeneity across the viewing users when addressing video caching. This constitutes the main focus of our paper.

III. FRAMEWORK AND SYSTEM MODEL

A. Framework

We consider a single edge cache scenario as depicted in Fig. 1. The origin server stores a catalog of video files, each of which is encoded into different representations. At the access, we have an edge server able to prefetch video files and cache them in advance. In general, edge servers are geographically closer to the users; the origin server leverages their caching storage to push popular content to the network edge during the off-peak hours, reducing the load on the origin server and resulting in more optimized delay and more convenient user experience. Usually, content providers put in place several edge servers to be as close as possible to different end-users, and one user can connect to several edge servers at a time. However, in this first study and to confirm the sound of our approach, we consider the case of one edge server. This assumption is similar to considering end-users able to connect to one edge server [START_REF] Jin | Optimal transcoding and caching for adaptive streaming in media cloud: an analytical approach[END_REF], which is also equivalent to optimize for each edge server individually.

In our context, whenever a client wants to play a video, it sends via its DASH client a request to the origin server, which gets redirected to the closest edge server, delivering back the highest video representation available and supported by the client network connection. If multiple representations of the requested video are available, the edge server will deliver back Fig. 1: Framework description the one affordable by the client connection and her terminal display capacity. Usually, when no representation is found on the edge server, the user request is served directly by the origin server, delivering the best video representation affordable by the bottleneck link between the end-user and the origin server.

B. System model

We consider a catalog of F video files available at the origin server. Each video f ∈ F is available in R representations, such that ∀ r ∈ R and ∀ f ∈ F, B f,r is the encoding bitrate of the representation r of video f . Moreover, we consider the R representations of each video to be ranked in increasing order of bitrates such that B f,r-1 ≤ B f,r , 1 < r ≤ |R|. We will also assume that all videos have the same duration T . Such assumption has often been adopted in the literature for simplicity and with no loss of generality [START_REF] Jin | Optimal transcoding and caching for adaptive streaming in media cloud: an analytical approach[END_REF]. Let E c be the cache of the edge server, and let S c be its available cache storage capacity in Bytes. On the other hand, let D denote the set of users' devices that request videos and that are eligible to communicate with E c . Each d ∈ D reaches E c with a download rate capacity equal to c d which we assume to be fully dedicated to the video streaming of the device. This capacity, already captured by the DASH client, can be approximated from past delivered chunks. Moreover, we denote by v d the viewport resolution of device d. As for content popularity distribution, we assume it to be stationary over the optimization period, and we consider requests to be independent of each other following the well-known Independent Reference Model. We denote by P f the popularity of video f and we normalize it in such a way that it becomes equal to the probability that any request issued by any device d ∈ D hits video f independently of the other requests [START_REF] Jin | Optimal transcoding and caching for adaptive streaming in media cloud: an analytical approach[END_REF].

We aim for a cache placement decision to be made by the origin server, or any other controller, in a discrete-time manner. In terms of end-user viewport size (v d ), content providers have access to this information as it is communicated between the DASH client and the DASH server. Such data can be inferred using machine learning with features calculated on the video encrypted traffic [START_REF] Belmoukadam | From encrypted video traces to viewport classification[END_REF].

C. QoE modeling

The video QoE models in state of the art focus mainly on application-level QoS metrics. However, the viewport size is also an important factor impacting the visual experience.

1) From bitrate to QoE: We capture the relationship between the viewport size and the selected video resolution (e.g., encoding bitrate) and the latter's impact on the QoE. We leverage an exponential QoE model calibrated offline using an open-source dataset [START_REF] Cermak | The relationship among video quality, screen resolution, and bit rate[END_REF]. This model maps the encoding bitrate, z BR , with the perceived user experience, z M OS , for a set of standard viewport sizes. Using the dataset in [START_REF] Cermak | The relationship among video quality, screen resolution, and bit rate[END_REF], we extrapolate a vector Z where each entry has two values (z BR ,z M OS ) then use the mean square error method to fit curves according to Equation [START_REF] Ericsson | Ericsson Mobility Report[END_REF]. In plain, the β v d derived with curve fitting describes the shape of the function for the viewport resolution of the device d, and QoE max is the maximum anticipated QoE value.

QoE v d = exp QoE max (1 -e -βv d x ).
(1)

2) From join time to QoE: We also account for the join time (initial delay), which is the time it takes the video to start playing out. According to authors in [START_REF] Krishnan | Video stream quality impacts viewer behavior: Inferring causality using quasi-experimental designs[END_REF], users start abandoning the video session after 2 seconds of join time, and 80% of them leave the session when their join time exceeds 60 seconds. We consider a logarithmic model for the impact of the join time on the QoE as proposed in [START_REF] Hossfeld | Initial delay vs. interruptions: Between the devil and the deep blue sea[END_REF]. Equation ( 2) provides a version of this model fitted by the authors of [START_REF] Hossfeld | Initial delay vs. interruptions: Between the devil and the deep blue sea[END_REF] using a crowd-sourced dataset of YouTube video streaming. In this equation, join d is the join time experienced by device d, which can be set to the time needed to fill up the playout buffer on the device. Equation ( 3) provides an estimation of this time using the encoding bitrate of the representation r of video f , B f,r , the playout buffer size in seconds, δ, and the user connection speed c d .

QoE join d = -0.963 × log(join d + 5.381) + 5, (2)
join d = δ × B f,r c d . (3)

IV. VIEWPORT AWARE OPTIMAL CACHE PLACEMENT

The viewport-aware cache placement problem for adaptive video streaming can be described as follows. Given a catalog of videos and the different available representations, the video popularity distribution, the end-user maximum download speed, the end-user viewport resolution, select the most rewarding set of video representations to be cached such that the total system utility is maximized as constrained to cache storage capacity.

A. Utility function

For simplicity and without loss of generality, we consider a caching system where a representation of a video file is either fully cached or not cached at all. We assume that any representation can be played out on any viewport and that devices have different viewport resolutions and internet connection speeds. Further, any representation exceeding the resolution of the viewport brings the maximum level of QoE [START_REF] Mansy | Network-layer fairness for adaptive video streams[END_REF]. In this context representing better the reality, the decision on the best representations to cache becomes more complex to solve. To reach an optimal solution, we first start by introducing a binary variable α f,r for the action of caching a representation or not. We then complement it with another binary variable per device d called γ d f,r that specifies which representation of video f is served by the cache to device d in case one or more representations of the video are available in the cache. Otherwise, the request is served by the origin server.

α f,r = 1, if f ile(f, r) cached 0, otherwise (4)
γ d f,r = 1, if f ile(f, r) served to d 0, otherwise (5)
We define the QoE-driven utility function for a request issued by device d as the average QoE reward overall videos of the catalog while conditioning on the viewport resolution and the device's connection speed d. We write it as a weighted sum of the two QoE functions defined in Section III-C:

Qgain d = f ∈F P f r∈R γ d f,r × (a × QoE v d + b × QoE join d ).
(6) (a, b) are system parameters that can be tuned to adjust the importance of each QoE aspect.

B. Problem formulation

The QoE-driven cache placement problem for adaptive streaming can be formulated as an Integer Linear Program (ILP) in the following way:

max α,γ d∈D Qgain d (7)
subject to:

f ∈F r∈R α f,r × B f,r × T ≤ S c , (8)
r∈R γ d f,r ≤ 1, ∀f ∈ F, ∀d ∈ D, (9)
γ d f,r ≤ α f,r , ∀f ∈ F, ∀r ∈ R, ∀d ∈ D, (10)
α f,r ∈ {0, 1}, (11)
γ d f,r ∈ {0, 1}. (12)
In this problem formulation, the objective is to maximize the overall QoE reward summed over the set of devices as defined in ( 7) and ( 6), while considering the network conditions, the video characteristics (e.g., popularity and encoding bitrate) and the end-user viewport size. The constraint in (8) represents the cache size constraint, with B f,r * T being the part of the cache occupied if we cache file (f, r). The constraint in (9) makes sure that each device can only download one representation per cached video. The constraint in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] establishes the relationship between the two decision variables such that a video representation can be served only if it is already cached. Finally, the constraints in [START_REF] Liu | Caching at the wireless edge: design aspects, challenges, and future directions[END_REF] and ( 12) define the binary decisions of caching and serving, respectively.

C. QoEscoreMax

We present a greedy heuristic named QoEscoreM ax based on the notion of QoEscore. The QoEscore is a new metric we introduce to calculate for each video representation the QoE gain that would result from caching it, summed over the set of devices. Following the same reasoning as in Eq. ( 6), we write:

QoEscore f,r = d∈D P f * (a * QoE v d + b * QoE join d ).
To further account for the cache space occupied by the video file, we normalize the score by the square of its volume in Bytes, B f,r * T 1 . We use the normalized score to rank representations in decreasing order of QoE gain. The QoEscoreM ax algorithm caches files having the highest QoEscore in the limit of the cache storage.

By studying the footprint of the optimal solution as solved by CPLEX, we found out that depending on the network conditions and the viewport resolution distribution. We might only need one representation to hit the optimal. Following this optimal footprint, we update QoEscoreM ax to limit the number of representations per video. Overall, we iterate over the QoEscore ranked list with three possible options: either replacing, adding, or simply skipping. For instance, for file (f, r), if we do not have the previous representation cached (e.g., cached f,r-1 = 0), we add the (f, r) representation directly to the cache while increasing the cache occupancy, otherwise, a delatQoEgain is computed between the two cache states: (1) the new representation replaces the previous one, and [START_REF] Feldmann | The lockdown effect: Implications of the covid-19 pandemic on internet traffic[END_REF] the new representation is skipped. A value of delatQoEgain positive means replacing the previous representation is beneficial and so is taken. Otherwise, no action is taken until the following representation of video f is found in the ranked list of QoEscore. This heuristic is detailed in Algorithm 1.

Result:

Cached -binary placement list (F, R) QoEscore(F, R), S c , cache occ , T, B (F, R) while B (f,r) * T + cache occ ≤ S c do if cached (f,r-1) = 0 then cached (f,r) = 1 cache occ = cache occ + B (f,r) * T else if deltaQoEgain(file(f,r), file(f,r-1)) ≥ 0 then cached (f,r) = 1 cached (f,r-1) = 0 cache occ = cache occ -B (f,r-1) * T cache occ = cache occ + B (f,r) * T end end (f, r) =QoEscore.

next key end

Algorithm 1: QoEscoreMax 1 The normalization by the square of the volume was shown empirically to provide better results than the normalization by the volume itself.

In terms of complexity, assuming the lookup operations of O(1) (i.e., hash maps), the running time of the proposed QoEscoreM ax greedy algorithm is O((F R) 2 D), resulting in polynomial time complexity. The CPLEX provides the optimal solution using the branch-and-cut search. This method follows a search tree consisting of nodes representing a relaxed LP subproblem. Each subproblem can be solved using the SIMPLEX method with exponential time complexity.

V. PERFORMANCE EVALUATION

To assess the efficiency of our approach, we compare it to state of the art approaches such as popularity-based caching, which takes into consideration the video popularity [START_REF] Jin | Optimal transcoding and caching for adaptive streaming in media cloud: an analytical approach[END_REF], [START_REF] Li | Streamcache: Popularitybased caching for adaptive streaming over information-centric networks[END_REF] and Femtocaching which minimizes the average download delay of video content [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF]. Beside our heuristic QoEscoreM ax, we study different variants of our optimal solution, in particular we show results for (i) ScreenCache which does not put any limit on the number of cached representations per video, and (ii) 1 -rep -ScreenCache and 2 -rep -ScreenCache which limit the number of cached representations per video to maximum 1 ( r∈R α f,r ≤ 1) and 2 ( r∈R α f,r ≤ 2) representations, respectively. For popularity-based caching, we implement a greedy version called P opularityCache that caches representations in increasing bitrate order using the popularity ranking. For F emtoCache, we use CPLEX to get its optimal solution leveraging the video popularity and the network conditions.

A. Simulation settings

We develop a numerical simulator in Python where videos are cached and QoE calculated according to Eq. ( 1), ( 2) and (3). We consider a network of 20 devices and sample the devices' viewports over a set of standard viewport sizes (420x240, 640x360, 850x480, 1280x720, 1920x1080). In terms of network access, we consider two scenarios depicting a case where users have either high download rates (from 10 to 18 Mbps) or poor/medium download rates (from 1 to 7 Mbps). As for video content, we consider a catalog of 20 videos of same duration T = 60s, each video is encoded in 7 representations with encoding bitrates (0.25, 0.55, 0.95, 1.5, 2.6, 5, 8 Mbps). We further assume that the popularity of the videos follows a Zipf distribution with parameter 0.56 [START_REF] Li | Qoe-driven mobile edge caching placement for adaptive video streaming[END_REF]. Last, the storage capacity is varied as multiple of the average size of a video representation.

At this stage, we consider a = b = 0.5 in Eq. ( 6), such that the encoding bitrate and the join time have the same importance on the user experience. To compare the different caching strategies, we use the metric AverageQoE/request, representing the average perceived QoE over the set of devices and videos. Each request targeting a random video in the catalog will be potentially served by the cache given the selection of cached representations and following the process described in Sec. III. This metric, between 0 and 4.5 (maximum QoE), also includes the notion of hit/miss, as the cache misses will result in zero contribution to the QoE gain . We do not consider

B. Simulation results

For space constraints, we only show results related to uniform viewport resolution distribution. Other viewport resolution distributions have demonstrated similar behavior as the one we will show next.

We start with the scenario of high access rates. We plot in Fig. 2(a) the AverageQoE/request vs. cache capacity, viewports of the 20 devices were sampled uniformly. Here, the optimal ScreenCache derived by the CPLEX results in the same QoE as 1 -rep -ScreenCache and 2 -rep -ScreenCache, suggesting that one representation per video can strike the optimal. On the other hand, F emtoCache and P opularityCache perform similarly, and below the optimal, the reason is that P opularityCache by proceeding in increasing order of bitrates ends up giving priority to the smallest representations, which results in almost the same behavior as the F emtoCache scheme which tries to minimize the average file download delay. Meanwhile, QoEscoreM ax outperforms the previous two caching strategies and highlights a nearoptimal performance. Thanks to using the QoEscore metric, QoEscoreM ax favorites the most rewarding representations making possible the caching of other than the lowest representation if needed by some viewports and some access links. Large viewport resolutions with good internet access make schemes focusing on minimizing the file download delay less efficient than the optimal that cache directly those representations providing the maximum QoE gain.

In a second scenario, we consider devices with poor to medium internet access (i.e., part of devices cannot accom-Fig. 3: QoE vs catalog size modate all representations). This scenario is more challenging as it requires caching a mix of representations depending on the access speed and the viewport. Here, one can expect 1rep -ScreenCache to diverge from unlimited ScreenCache as the cache size increases. As we can observe in Fig. 2(b), the 1 -rep -ScreenCache scheme starts indeed diverging from the optimal as the cache size increases. Finding one representation per video that approximates well the optimal for all viewports is no longer possible as some accesses are slow and cannot accommodate high-quality representations. However, we can see that the 2-rep-ScreenCache keeps up and shows almost the same behavior as the unlimited optimal. To further understand this behavior, we analyze the footprint of ScreenCache; the optimal considers two representations for popular videos while holding the least popular videos to one representation. QoEscoreM ax sustains its good performance through the different viewport distributions.

Moreover, we test the behavior of our solution for a larger video catalog. We plot in Fig. 3 the average QoE per request for the scenario of good network conditions while scaling up the catalog size at a fixed cache size of ten times the average representation size (10 * Avg(B f,r ) * T Mbits). Overall, the QoE value is negatively correlated with the catalog size for all caching strategies, making sense since the storage capacity remains the same and the pressure on the cache increases. However, the decline of ScreenCache and QoEscoreM ax is slower than F emtoCache and P opularityCache as the former can better utilize the available storage by caching the most rewarding content directly rather than caching lowquality videos for unpopular content.

VI. SENSITIVITY ANALYSIS

Here, we evaluate the impact of the QoE model parameters on the cache placement strategy. We study the impact of the balance between join time and bitrate, and show results for good network conditions and uniform viewport distribution.

1) Video bitrate over join time: In this part, we give more importance to QoE v d linking the bitrate to the QoE, with a = 0.9 and b = 0.1. We plot in Fig. 4(a) the average QoE per request (plus its standard deviation) for different viewport sizes and different caching schemes. Overall, we observe that the QoE decreases as we move toward larger viewports. Between the caching schemes, ScreenCache and QoEscoreM ax result in almost the same QoE level per view- 2) Join time over video bitrate: Here, we assume that the QoE model in Eq. ( 6) is mostly based on the join time by considering a = 0.1 and b = 0.9. Since QoE join d is negatively correlated with join d (Eq. ( 2) and (3)), one would expect the optimal solution to be selecting representations with smallest encoding rate as they reduce the join time. Differently speaking, the model now largely prefers the smoothness of the playout on the quality of the rendered resolution, which is closer in mind to existing placement schemes that seek to minimize the file download delay by caching first the low representations. We illustrate the obtained results in Fig. 4(b). When favoring the join time, and regardless of the viewport size, the different caching schemes converge to almost the same QoE level, thus, caching almost the same content.

VII. CONCLUSION AND FUTURE WORK

In this work, we study a QoE-driven cache placement optimization for adaptive video streaming while accounting for the end-user viewport. We formulate the problem as an ILP and derive the optimal selection of videos and representations to be cached for different internet accesses and viewport size distributions. We also present QoescoreM ax, a practical caching heuristic with near-optimal performance. Simulation results show that our solution strikes the trade-off between optimal QoE and efficient storage management. Moreover, they provide insights on video representations selection based on network conditions and the importance of the balance between join time and video bitrate. In good network conditions, one representation can lead to optimal QoE. For mild network conditions, the selection process has to account for the videos' popularity before adding another video representation.

We plan to extend this study by testing our solution in a cooperative caching scenario where coordination between multiple edge servers is enabled and orchestrated by a main controller, mainly in the context of Software Defined Networks.

  Fig. 2: Average QoE per request, uniform viewport distribution

  Fig. 4: Average QoE per viewport


Ayoub Ridani

Othmane-Latif Ouabi

Nico F Declercq

Cédric Pradalier

On-plate autonomous exploration for an inspection robot using ultrasonic guided waves

This article presents an active-sensing strategy based on frontier exploration to enable the autonomous reconstruction of the geometry of a metal surface by a mobile robot relying on ultrasonic echoes. Such a strategy can be beneficial to the development of a fully autonomous robotic agent for the inspection of large metal structures such as storage tanks or ship hulls. The developed method relies on a grid map generated by detecting the first echo within the measurements referring to the closest edge to the sensor, and it employs a utility function that we define to balance travel cost and information gain using an estimation of the plate geometry obtained via beamforming. Next, the sensor is directed to the next best location. The developed method is evaluated in simulation and compared with multiple algorithms, essentially closest and random frontier point selection. Finally, an experiment using a mobile robot equipped with co-localized pair of transducers is used to validate the viability of the approach.

I. INTRODUCTION

Monitoring the health of structures is a major stake (if not critical) in many different fields of Industry. Ultrasoundbased inspection methods have been identified as a promising solution for the long-range inspection of materials. Structures under consideration are usually made of metal (e.g., pipes, rails...) or composite materials (e.g., plane outer shapes...).

On the one hand, most of the recent ultrasound-based inspection methods are meant to be deployed on static networks of sensors permanently attached to the structure, with an application to Structural Health Monitoring (SHM). However, such methods can only be used to monitor a very restricted area. On the other hand, ultrasound-based autonomous robotic inspection has not yet been established, whereas it could benefit from the agent mobility to precisely assess, through acoustic tomography, the integrity of large structures such as ship hulls or storage tanks.

While precise localization of a mobile agent on a platebased metal structure has been identified as a fundamental requirement to long-range robotic inspection [START_REF]Bugwright2, autonomous robotic inspection and maintenance on ship hulls and storage tanks, description of the innovative action[END_REF], Ultrasonic Guided Waves (UGWs) have proven to be useful for both plate geometry reconstruction and on-plate robot localization, yielding an innovative solution to the SLAM problem [START_REF] Ouabi | A fastslam approach integrating beamforming maps for ultrasoundbased robotic inspection of metal structures[END_REF]. Yet, this solution has been assessed without using a real robotic platform and with pre-defined paths. *This work is part of the BugWright2 project. This project is supported by the European Commission under grant agreement 871260 -BugWright2. 1 Ayoub Ridani, Othmane-Latif Ouabi, Nico F. Declercq and Cédric Pradalier are with the International Research Lab Georgia Tech -CNRS, IRL 2958, Metz, France. {aridani, oouabi, cedric.pradalier}@georgiatech-metz.fr 2 Nico F. Declercq is also with Georgia Institute of Technology, Atlanta, GA 30332-0250, USA. declercq@gatech.edu From a robotic perspective, plate geometry reconstruction and defect detection can be considered as a mapping problem, for which autonomous solutions are desirable [START_REF]Bugwright2, autonomous robotic inspection and maintenance on ship hulls and storage tanks, description of the innovative action[END_REF]. Autonomous robotic exploration is a major research issue in robotics incorporating the aspect of how to make decisions for the next actions to maximize information gain and minimize costs. Frontier-based approaches yield common solutions to the exploration problem and are extensively used to map indoor environments. For our application, such strategies may be leveraged to determine relevant robot trajectories, to achieve fast and accurate reconstruction of the plate geometry, and under the constraint that the robot stays on the plate during the reconstruction, without crossing any boundary.

In this work, we consider a mobile unit equipped with a pair of co-localized piezoelectric transducers for emission and reception of ultrasonic waves as presented in Fig. 1b. In contrast with standard sensing technology (range-finder laser, ultra-wideband beacons, sonar...), the exploitation of guided waves measurements in a pulse-echo setup is more challenging due to their dispersive nature which causes wavepacket deformation when the propagation distance is large, but also due to the overlapping of the multiple reflections of the incident wave on the plate boundaries, which results in diffuse mixture data.

In [START_REF] Ouabi | A fastslam approach integrating beamforming maps for ultrasoundbased robotic inspection of metal structures[END_REF], a map building technique is presented in which we estimate the boundaries of a rectangular plate. Here, we aim at pursuing this work by introducing an autonomous exploration technique integrating UGWs and exploiting the estimated plate geometry while limiting ourselves to flat rectangular plates. Frontier exploration is taken as the basic framework for exploration and we use a grid map, that we call In-plate Points Grid illustrated in Fig. 1a, computed using the detection of the closest edge to the sensor and the plate estimation to define areas that are inside the plate such that during robot motion, the sensor remains on the plate preventing the plate's geometry from being lost. The contributions of this paper are summarized as follows:

1) A demonstration of the utility of using the In-plate Points Grid map in combination with the geometry estimator [START_REF] Ouabi | A fastslam approach integrating beamforming maps for ultrasoundbased robotic inspection of metal structures[END_REF] to map a "safe space" that ensures the sensor remains on the plate during robot motion. 2) An integration of UGWs sensing modality with the frontier exploration approach that balances information gain and travel cost. 3) A demonstration of the method's validity on simulation and real-world scenarios using a mobile robot on a rectangular metallic plate.

II. RELATED WORK

Robotics exploration, which uses mobile robots to map unknown environments, has been studied for years. Among the various proposed methods, frontier-based exploration is one of the classical approaches [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF]. The key to effective frontier exploration is the selection of target frontier points. In the original method [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF], the closest frontier is selected as the next target. In most cases, exploration strategies select the next best frontier by evaluating candidate locations according to different criteria resulting in various extensions of the basic frontier-based exploration strategy [START_REF] Juliá | A comparison of path planning strategies for autonomous exploration and mapping of unknown environments[END_REF]- [START_REF] Fang | Autonomous robotic exploration based on frontier point optimization and multistep path planning[END_REF]. In [START_REF] González-Baños | Navigation strategies for exploring indoor environments[END_REF] a utility function balancing the travel cost with the information gain is defined. In [START_REF] Amigoni | A multi-objective exploration strategy for mobile robots[END_REF], a more principled approach to aggregate criteria, based on multi-objective optimization, is proposed. Currently, two methods are applied to compute information gain: one uses direct measurements of undetected space size in the visible region of the target frontier point [START_REF] Amigoni | A multi-objective exploration strategy for mobile robots[END_REF], and the other uses the information entropy method [START_REF] Bourgault | Information based adaptive robotic exploration[END_REF]. In both cases, the nominal sensor range is used to define the region expected to be explored for a given frontier point. In our case, using the sensor range to compute information gain is inappropriate because Lamb waves propagate over long distances in metallic plates exceeding the standard dimensions of these plates.

On the other hand, [START_REF] Miranda | Lamb wave-based mapping of plate structures via frontier exploration[END_REF] recently introduced Lamb wavebased frontier exploration strategy (LFE), demonstrating the potential contribution of Lamb wave-based sensing to the field of mobile robot exploration. The work considers a pair of transducers in a pitch-catch configuration on the surface of an isotropic metallic plate structure. The method's major drawbacks, as mentioned by the authors, include the inability to map the entirety of a sharp corner of a structure. The transducers are limited in their placement to the edges to avoid the risk of falling off the structure; thus, there is always an edge closer to the transducers than the corner point. Besides, gridlock situations occur also when the bounding box used to estimate the environment is inaccurate, resulting in inaccurate estimations, and it is impossible to distinguish between the complete mapping and gridlock without knowing the upper limit of obtainable coverage. In addition, transducers are manually positioned in the desired position, moving them instantaneously between two locations. However, in a real-world scenario, a mobile robot moves continuously to the desired position, gathering more information about its surroundings, and the optimality of the chosen goal doesn't necessarily persist.

III. METHOD

A mobile robot equipped with a co-located transmitter/receiver pair of transducers and moving on a metal surface is considered. The emitter sends a pulse s(t) to excite guided waves in the plate material at each scanning phase, and the receiver collects the acoustic response z(t) containing the ultrasonic echoes. We restrict ourselves to mapping assuming a well-known position and frontier-based exploration is taken as the basic framework. We seek to find the optimum frontier points to take autonomous action to reconstruct the geometry of the plate in a fast manner, without getting too close to the plate's boundaries. Plate estimation and In-plate Points Grid update are kept running in the background, which continuously integrate robot pose and acoustic measurements. At each exploration step, the following steps are followed:

• Frontier points are extracted from the grid map.

• A utility function is used to evaluate the potential destinations.

• The candidate pose with the highest utility is selected as the next goal. • The robot navigates to the target position. The map is continuously updated as the robot moves toward the goal. If the goal is reached or is no longer valid (discussed in more details in section III.D.) or if the local exploration step is attained, the exploration process is run again. The frontier exploration is considered complete when there are no more frontier points to evaluate regarding their distance to the edge. A graphical overview of the proposed approach is presented in Fig. 2.

A. Plate geometry estimation

As in [START_REF] Ouabi | A fastslam approach integrating beamforming maps for ultrasoundbased robotic inspection of metal structures[END_REF], echo detection and plate geometry reconstruction are based on a propagation model which is used to construct ẑ(r, t), the expected signal that would be received if the incident wave is reflected at a distance r to the transducers. Given measurement z i (t), the correlation signal:

z i (r) = z i (t), ẑ(r, t) z i (t), z i (t) ẑ(r, t), ẑ(r, t) (1)
is computed and its envelope:

e i (r) = |z i (r) + jH(z i )(r)| (2)
is retrieved, as the most likely first-order reflections can be identified by its local maxima. Next, plate boundaries are represented by 2D lines with parameters (r, θ) which define the line equation with:

x • cos θ + y • sin θ -r = 0.
These boundaries are subsequently detected by constructing first the beamforming map given measurements z 1..T obtained all along the robot trajectory x 1..T :

L T (r, θ) = T i=1 e i (|x i • cos θ + y i • sin θ -r|)
where x i = (x i , y i ) is the robot position during time-step i.

Next, the optimization problem:

M = arg max M L T (M) = arg max M 4 l=1 L T (r l , θ l )
is solved with the method described in [START_REF] Ouabi | A fastslam approach integrating beamforming maps for ultrasoundbased robotic inspection of metal structures[END_REF] to identify the map M = {r l , θ l } l=1... [START_REF] Juliá | A comparison of path planning strategies for autonomous exploration and mapping of unknown environments[END_REF] , where the four lines are restricted to define a rectangle altogether.

B. In-plate Points Grid

Our construction of the grid is equivalent to the occupancy grid mapping framework [START_REF] Thrun | Probabilistic Robotics (Intelligent Robotics and Autonomous Agents)[END_REF]. Let the In-Plate grid G be decomposed into n × m evenly-spaced grid cells where the i-th grid cell c i is assigned a static binary variable o(c i ) for i ∈ {1, . . . , n × m} that is defined as o(c i ) = 0 when c i is inside the plate and o(c i ) = 1 otherwise. The grid's construction relies on detecting the closest edge to the sensor to identify which areas are inside the plate. And, we use the map M to estimate the direction of arrival of the echo within a Bayesian framework to determine which areas are outside the plate. The beamforming map L T (r, θ) also uses the grid's information to filter the lines with parameters (r, θ) such as a line l = (r l , θ l ) is filtered if it contains a point which is inside the plate. Overall, as the coverage of explored area increases, more lines of the beamforming map are filtered, indirectly increasing the plate's geometry estimation recovery speed. Furthermore, due to page limit constraints, this mapping approach is not detailed here.

C. Frontier generation and evaluation

After each In-plate Points Grid update, each grid cell has a state probability. We use a thresholding method to assign discrete states obtaining then a deterministic world model [START_REF] Moravec | High resolution maps from wide angle sonar[END_REF]. We choose a threshold δ for which a grid cell is labeled as in-plate for a state probability lower than δ and unknown otherwise. Frontier points are then generated based on an edge detection technique borrowed from computer vision [START_REF] Roberts | Machine Perception of Three-Dimensional Solids[END_REF].

The frontier points evaluation function is the basis for frontier points selection. We evaluate the frontier points from the following two factors: information gain at the frontier point and the Euclidean distance to the robot's pose.

The information gain is defined as the area of an unknown region expected to be explored for a given frontier point p k and quantified using Shannon entropy:

I(p k , M) = c∈V k e(c) (3)
where V k is the set of grid cells contained in the expected area of measurement defined by a circle centered in the frontier point p k with a radius equivalent to the distance to the closest edge given the plate's estimation M (Fig. 3), and e(c) refers to the entropy of the probability distribution ôt (c) such as:

e(c) = -ô t (c)log(ô t (c)) -(1 -ôt (c))log(1 -ôt (c))
We note ôt (c i ) = p(o(c i )/x 1:t , z 1:t ) the in-plate probability of grid c i where z 1:t the set of all measurements up to time t, and x 1:t is the path of the robot defined through the sequence of all poses. We evaluate both unknown regions and regions where the map is still uncertain by taking into account the entropy of both observed and unobserved grid cells. The second factor is the Euclidean distance d(p k ) from the sensor's pose to the frontier point p k . Each factor of the utility function is subjected to a min-max normalization to map its values to a range between 0 and 1:

fk = f k -min(f ) max(f ) -min(f )
where f k is the factor associated to the frontier point p k and f the set containing the factor associated to all frontier points. Based on both factors, the utility function is then defined as:

U (p k , M) = α(1 -d(p k )) + (1 -α) Î(p k , M) (4)
where d(p k ) and Î(p k , M) are the normalized factors and α is a weight parameter that varies between 0 and 1 to adjust the importance of each factor. Given N nominee points, the next goal is the point with the highest utility evaluation as:

p opt = argmax p k {U (p k , M), k ∈ [1, N ]} (5)

D. Validity of frontier points and exploration stopping condition

We create another grid layer naming it Radius Grid R (Fig. 4b) with the same dimensions as the In-plate Points Grid G. R is updated simultaneously as G using the robot pose x t and the echo retrieved from the measurement z t . The goal of this grid is to define the validity of frontier points in terms of their estimated distance from the true edge to avoid crossing any plate boundaries. For each grid cell, g i is assigned the minimum measured echo that passed by this cell. The validity of a frontier point p i is defined by its associated Radius Grid value; if this value is less than a defined threshold ρ, p i is then labeled as an invalid candidate point. This method, which uses the first echo, is a heuristic that gives information if the sensor is too close to a real edge. It also allows us to set a stopping condition for the exploration process: there are no more valid candidate points. Fig. 4 illustrates the In-plate Points Grid as well as the parallel Radius Grid layer defining valid and invalid frontier points for ρ = 0.2m.

E. Repetitive Re-checking and the exploration algorithm

The map is updated continuously during navigation to the selected location. As a result, some new frontier points will be generated, some old frontiers will no longer be valid, and the selected point may no longer be the optimal target. It is, therefore, unnecessary to continue traveling to the chosen location [START_REF] Fang | Autonomous robotic exploration based on frontier point optimization and multistep path planning[END_REF], [START_REF] Holz | A comparative evaluation of exploration strategies and heuristics to improve them[END_REF]. We address this problem by defining a local exploration path step size s exp . Each time when the traveled distance of the robot reaches the step size, the next optimal target is selected using the exploration strategy. Algorithm 1 summarizes the overall implementation of our exploration strategy:

IV. EXPERIMENTAL EVALUATION

To evaluate the feasibility and viability of our approach, we present several tests conducted in simulation and with a real robot. We measure, as exploration time progresses, the distance traveled by the robot and the percentage of covered area (as done, e.g., in [START_REF] Holz | A comparative evaluation of exploration strategies and heuristics to improve them[END_REF]), namely the percentage of the area of cells labeled as inside the plate relative to the real area of the plate. For both the simulated and real-world experiments, we work on a flat rectangular metallic plate with dimensions 1700 × 1000 × 6 mm 3 and we use α = 0.7, δ = 0.3, s exp = 20cm, ρ = 15cm and the grid size = 1 × 1 cm 2 .

p opt = argmax p k U (p k , M), k ∈ [1, N ] ;
A. Echo detection First, we illustrate the echo-detection principle. The emitted signal is a 2-cycle burst at 100kHz. We show, in Fig. 5, the measured acoustic signal z i (t) for a sensor position (28, 50) centimeters relative to the plate's corner. Fig. 5.b shows the resulting correlation signal z i (r) computed using eq.( 1) and its envelope e i (r) calculated with eq.( 2) as explained in [START_REF] Ouabi | A fastslam approach integrating beamforming maps for ultrasoundbased robotic inspection of metal structures[END_REF].

The method relies on the detection of the first peak (local maxima) in the correlation using peak properties. In this case, prominence is used as the main property. The prominence of a peak is defined as the shortest drop in altitude required to reach any higher terrain from the summit and is used, here, to distinguish the echo from noisy peaks, because the higher the prominence, the more important the peak is.

To automate the process of peak detection, first, we retrieve all the peaks of the correlation and calculate the prominence of each peak. Next, we calculate the k th percentile p k of these values. Then, we recalculate the peaks with a required prominence higher than the percentile value found in the first step. Fig. 5 illustrates the result of the method for a prominence value p k = 85%. The red line presents the peak detected at 29.3cm and the green line presents the expected echo given the ground truth pose (x, y) which is defined by min(x, y, w-x, h-y) where (w, h) are the width and height of the plate. The error between the ground truth and peak detected in Fig. 5 is 1.4 cm.

B. Simulation

Simulations are performed in a Python environment to evaluate the proposed method. We simulate the two colocated transducers as a particle with a position referring to the central position between the two. The signals are simulated using the measurement model based on the propagation model as explained in [START_REF] Ouabi | A fastslam approach integrating beamforming maps for ultrasoundbased robotic inspection of metal structures[END_REF] and correlation is retrieved as shown in Fig. 5.

In Fig. 6, we show the In-plate Points Grid and the exploration path of the particle. We also represent the estimated geometry, the valid and invalid frontier points, and the selected candidate point based on the utility function defined. In step 1, the estimated plate is incorrectly estimated as expected since only one measurement was integrated. Because all of the points are within the same distance of the sensor position, only the expected area to explore is used to differentiate the utility of the points. The next goal is then randomly chosen from one of the four points pointing to the edges. As in step 41, the three closest edges and the orientation are well estimated. The sensor moved closer to the left part of the plate until no valid candidate points remained; consequently, the sensor went to the center of the plate to acquire the maximum area to explore. In step 83, the shape has been approximately fully recovered and 83% of the plate has been covered with the interior points grid. Leading to the final step 125, the sensor followed the remaining frontier points until there were no valid frontier points left, indicating the end of the frontier exploration process.

Step 1

Step 41

Step 83

Step 125

Fig. 6: Interior points grid and path generated by the exploration algorithm. The estimated plate is the red rectangle. The true outline of the plate and the true sensor positions correspond to the black rectangle and blue particle respectively. The valid (resp. invalid) frontier points correspond to the red (resp. black) dots. The green particle refers to the selected candidate point.

The following methods are compared to our approach: the classic frontier method (closest frontier point) [START_REF] Yamauchi | A frontier-based approach for autonomous exploration[END_REF], picking random points from frontier points, and our method using the true plate's geometry instead of the estimated map. In the case of closest and random frontier point selection, the sensor moves until it reaches the selected point before moving on to the next valid location. To have a fair comparison, we present results up to 83% of mean coverage, because some runs end without reaching full coverage. We show in Fig. 7 the average coverage increase calculated over 50 runs for each algorithm. The same starting position is used for each run corresponding to 20 cm to the plate's corner. We also represent the 10% and 90% quantiles to assess the repeatability of each approach. The method using the true plate's geometry, shown in red, produces an approximate deterministic result with a low standard deviation up to 63% of coverage, demonstrating the benefit of having a known map. The curve rises quickly, providing on average 70% coverage after 1 m of displacement. The closest selection method grows in a roughly linear fashion with an average coverage rate of 0.15%/cm and presents a behavior approximately equal to the random approach with a higher standard deviation. On the other hand, though a random approach will eventually produce a map, random choices may not provide an efficient sequence for mapping an environment. As expected, the approach underperforms when compared to other algorithms.

Our method, on average, outperforms random and closest frontier exploration as made evident by the mean result curves of Fig 7 as it takes into account information gain and navigation cost.

C. Real-world experiment

The origin of the xy-coordinate system is at the bottom left corner of the plate as shown in Fig. 1.b. As presented in Fig. 1a, we use two co-located transducers fixed on a spring mechanism mounted on a TurtleBot to maintain constant contact with the surface. A layer of water is added to the plate's surface as a coupling medium for the transducers used in the acoustic measurements. Considering the projection on the plate of both the rotation center of the robot and the middle point between the two transducers, the distance between these two points is 32 cm. We use two-tone bursts of a sinusoidal wave at 100 kHz as the excitation and a sampling frequency of 1,25 MHz. Moreover, the direct incident signal is smoothly removed from the data as it does not correspond to a reflection on an edge. This filtering limits the distance at which the signal containing the information about the closest edge can be detected to about 15 cm limiting then the sensor's positioning from the edge. For values less than that, the first echo is misdetected, resulting in an In-plate Points Grid that crosses the real plate's boundaries.

Throughout all the experiments, we use a camera with AR tags tracking [START_REF] Niekum | Ros package: ar track alvar[END_REF] as an external localization system as shown in Fig. 1a. Also, to evaluate the system independently of the quality of the controller, while the robot has a strong tendency to slide, the movement between waypoints is implemented with the joystick.

The two methods, namely closest and random frontier selection, are compared to our approach, as done in the simulation. As it may be seen in Fig. 1.a, the In-plate Points Grid exceeds the plate's real geometry mainly because of a misdetected closest edge. Several factors could cause the echo detection error, including changes in the propagation model due to the use of water as a couplant between the transducers and the plate, not enough water between the transducer and the plate, and human errors while positioning the ar tags to locate the robot on the plate. The mapping method is sensitive to large misdetected echoes. In this case, lines representing the true edges could be filtered. The robot then risks exceeding the edges resulting in an overall incorrect geometry estimation.

We run each algorithm five times each with the same starting position corresponding to (25cm, 45cm). To have a fair comparison and similar to what we did in the simulation, we present results up to 91% of the mean coverage. Fig. 8 illustrates the mean coverage value. The upper bound is the full coverage computed during the exploration process, and the lower bound is the full coverage minus the error coverage (i.e. covered area outside the plate).

In the proposed method, the coverage percentage increases fast, reaching 83% with a displacement of 2.38m. We remark that the random approach outperforms our method at the beginning but plateaus around 80% coverage. The main reason is that random procedure may choose distant points, resulting in rapid coverage increase but fails to obtain all details at the end. The proposed exploration algorithm outperforms the two other methods balancing between traveling cost and information gain.

V. CONCLUSIONS

In this paper, we present a novel application and integration of UGWs with the frontier exploration strategy, that takes into account the estimated geometry of the plate, balancing the information gain and the travel cost. Both in simulation and real-world experiments carried out in a laboratory environment, the proposed approach outperforms random and closest frontier selection in terms of coverage increase rate. The next step will be to integrate the exploration method with a SLAM framework to account for the state estimation error. Besides, the automated first echo detection can be further investigated to be more robust given that more complex and noisy signals are expected on a large metal structure and in an outdoor environment. Finally, robot dynamics can be considered when selecting frontier points to minimize velocity changes and maintain a consistently high speed for fast reconstruction and exploration of the plate.

Fig. 1 :

 1 Fig. 1: Representative intermediate result for the proposed method in a realworld scenario. (a) Computed In-plate Points Grid. The blue dot refers to the sensor position whereas the purple dot is the goal position. The green lines represent the estimated plate edges and valid (resp. invalid) frontier points are the red (resp. black) dots. (b) Representation of the associated configuration on the lab experiment.

Fig. 2 :

 2 Fig. 2: Block diagram of the proposed method.

Fig. 3 :

 3 Fig. 3: Graphic representation illustrating an example of the expected area to explore (bounded by the dashed pink circle) for two frontier points (pink dots) given the plate geometry estimation (blue lines). The black rectangle illustrates the true outline of the plate. For simplicity, gray cells are used to illustrate both out of the plate and unknown cells.

Fig. 4 :

 4 Fig. 4: (a) The red rectangle represents the estimated map in simulation of a 1.7 × 1 m 2 plate. The sensor position and path are represented by the blue dot and blue polyline. The red (resp. black) dots illustrate valid (resp. invalid) frontier points; (b) The associated Radius Grid R.

Algorithm 1 :

 1 Exploration Input : In-plate Points Grid G, Radius Grid R, Robot Pose x t , Plate Estimation M. Output: Goal pose p opt . Γ = {f p 1 , f p 2 , ..., f p n } = GetF rontier(G) ; {p 1 , p 2 , ..., p N } = V alidP oints(Γ, R, ρ) ; for k = 1 to N do d(p k ) = EuclidianDistance(p k , x t ) ; V k = EstimatedV iew(p k , M) ; I(p k , M) = c∈V k e(c) ; U (p k , M) = α(1 -d(p k )) + (1 -α) Î(p k , M) ; end

Fig. 5 :

 5 Fig. 5: Illustration of the echo detection principle for a real signal based on correlation with the propagation model in a 1700 × 1000 × 6 mm 3 metallic plate. a) the acoustic measurement. b) representation of the correlation signal (blue) and its envelope (orange), the retrieved echo (red line) and ground true echo (green line) based on exterior localization.

Fig. 7 :

 7 Fig. 7: Exploration results for the four exploration approaches in terms of coverage increase as a function of the traveled distance.

Fig. 8 :

 8 Fig. 8: Comparing the approaches in real-world experiment.