Mireille Fares
email: fares@isir.upmc.com

Catherine I Pelachaud
email: catherine.pelachaud@upmc.fr

Nicolas Obin
email: nicolas.obin@ircam.fr

Multimodal modeling of expressiveness for human-machine interaction

Keywords: multimodality, speech, gestures, prosody, intelligent embodied conversational agents

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Human-Human interaction inherently involves the communication through multiple channels. We employ several modalities, both sequentially and in parallel, to communicate in our daily life. The multimodal channels adopted in human communication are verbal and non-verbal [START_REF] Norris | Analyzing multimodal interaction: A methodological framework[END_REF]. Non-verbal are non-vocal signals that are sent by means of facial expressions, gaze, body postures, head or arm movements. The speech modality involves the speech content (words) and vocal signals such as speech prosody and acoustic signals. Both verbal and non-verbal modalities are essential to send and perceive new information. They both reflect our socio-emotional behavior which includes our psychological state and attitude. During a human-human interaction the alignment phenomena (tone of voice, speed of body movement) are signs of common understanding and engagement in the interaction [START_REF] Castellano | Expressive copying behavior for social agents: A perceptual analysis[END_REF][START_REF] Sidner | Where to Look: A Study of Human-Robot Engagement[END_REF]. Communicative modalities should be taken into consideration when developing Human Computer Interaction (HCI) applications because computers are becoming more integrated in our daily life. As a matter of fact, in the past decade, many HCI applications such as personal assistants, tutoring systems, reception agents, chatbots, smartphones and home assistants are being extremely used in our daily life. The rise of such applications are leading humans to interact with virtual agents.

A key problem in the design of virtual assistants is how to maintain user's engagement [START_REF] Bickmore | Maintaining engagement in long-term interventions with relational agents[END_REF][START_REF] Bickmore | Establishing and Maintaining Long-Term Human-Computer Relationships[END_REF] during the interaction so that the interaction lasts long and stays fluent. The main limitations concern are on the one hand the agent's weak expressiveness, and on the other hand the agent's weak adaptation of his behavior to the behavior of the user. As a matter of fact (i.e Alexa and Google Home), rendering the interaction very short, and lacking in variety and interest. On the other hand, the agent does not adapt its behavior with respect to the interlocutor's behavior which decreases the engagement of the user in the interaction [START_REF] Castellano | Expressive copying behavior for social agents: A perceptual analysis[END_REF]. The behavior of the agent greatly impacts the user's attentive commitment, the duration of the interaction, as well as the user's understanding of the transmitted messages.

The present paper is part of a thesis work that aims to better understand and model the mechanisms that govern multimodal interaction (voice and gesture) between a human and a machine. We aim to develop an engaging conversational agent (ECA) with expressive gestures and prosody, capable of maintaining the attention of the interlocutor during the conversation, emphasizing important points, and making the interaction last longer by improving its quality. The ECA will be able to reinforce the interlocutor's engagement by adapting its behavior according to the behavior of the interlocutor. As a first step of our work, we present in this paper a State-of-the-Art review of how to design engaging virtual agents with expressive gestures and prosody. In the following sections, we discuss the different points that should be taken into account when designing an ECA capable of detecting the user's engagement level, maintaining and reinforcing it by displaying an appropriate behavior. We also discuss some of the existing models of the agent's behavior, based on different scenarios. An emphasis is placed on gestural and prosodic expressivity of the agent.

ENGAGING EMBODIED CONVERSATIONAL AGENTS

Engagement is "the process by which two (or more) participants establish, maintain and end their perceived connection during interactions they jointly undertake" as defined by Sidner et al [START_REF] Sidner | Where to look: A study of human-robot interaction[END_REF]. The design of Embodied Conversational Agents (ECA) capable of rendering the users engaged in the interaction, is essential and critical for Human Agent Interaction applications [START_REF] Clavel | Fostering User Engagement in Face-to-Face Human-Agent Interactions: A Survey[END_REF]. Various applications such as tutoring systems [START_REF] Mello | AutoTutor and affective autotutor: Learning by talking with cognitively and emotionally intelligent computers that talk back[END_REF], ambient assisting living [START_REF] Bickmore | Health dialog systems for patients and consumers[END_REF][START_REF] Griol | Modeling the User State for Context-Aware Spoken Interaction in Ambient Assisted Living[END_REF], and virtual museum agents [START_REF] Cafaro | First Impressions in Human-Agent Virtual Encounters[END_REF][START_REF] Campano | I like this painting too": When an ECA Shares Appreciations to Engage Users[END_REF][START_REF] Gockley | Designing robots for long-term social interaction[END_REF][START_REF] Kopp | A Conversational Agent as Museum Guide -Design and Evaluation of a Real-World Application[END_REF] convey the importance of maintaining the user's engagement during his/her interaction with the agent. User engagement is marked by nonverbal social behaviors at specific moments of the interaction: it can be feedback signals (to indicate being in phase with the interactant), a form of imitation (i.e. smiling for another smile or making the tone of the voice resemble that of the interactant), or signals synchronized with those of the interactant (management of speaking turns). In addition to that, the behavior of the agent should adapt to the multimodal behavior of the interlocutor [START_REF] Castellano | Expressive copying behavior for social agents: A perceptual analysis[END_REF][START_REF] Sidner | Where to Look: A Study of Human-Robot Engagement[END_REF]. In other words, it should be capable of adapting its behavior with respect to the behavior of the interlocutor, to strengthen the latter's engagement in interaction.

The two components underlying the engagement process are the attentional involvement and emotional involvement [START_REF] Peters | An exploration of user engagement in HCI[END_REF]. Shortterm engagement is needed for performing a specific task during the interaction, whereas long-term engagement is essential for longer periods of interactions [START_REF] Bickmore | Health dialog systems for patients and consumers[END_REF]. The development of an engaging ECA must take into account the socio emotional behavior of users which are expressed by means of verbal or non-verbal signals [START_REF] Clavel | Fostering User Engagement in Face-to-Face Human-Agent Interactions: A Survey[END_REF]. A socio emotional behavior includes user's social attitudes as well as their emotions. As Scherer defines it, a social attitude is "an affective style that spontaneously develops or is strategically employed in the interaction with a person" [START_REF] Scherer | What are emotions? And how can they be measured[END_REF]. An engaging agent detects the engagement level of its interlocutor and maintains it by displaying an socio-emotional behavior during the interaction. Some studies prefer to detect the user's level of engagement by analyzing his/her signals (such as the location of his/her face), instead of his/her socio emotional behavior [START_REF] Bohus | Managing Human-Robot Engagement with Forecasts and[END_REF]. Other studies prefer to focus on acoustic features such as prosody, voice quality, and spectral features. Prosodic cues are also informative of the engagement level of the users, in the form of global cues (long term patterns), and local cues (short-term) [START_REF] Sidner | Where to look: A study of human-robot interaction[END_REF]. Furthermore, engagement can be reflected not only in vocal signals, but also in the speech of the interlocutor [START_REF] Sidner | Where to look: A study of human-robot interaction[END_REF]. User engagement cannot happen if the agent isn't expressive. In the following sections, we review the state of art of gestural expressivity and prosodic expressivity.

GESTURAL EXPRESSIVITY

An ECA with expressive gestures is capable of having a varied and coherent expression so that it can maintain the attention of the interlocutor. It is also capable of emphasizing important ideas, while leveraging the quality of the interaction, and lengthening its duration (to exceed one or two speaking turns). A key challenge in designing ECAs with expressive gestures, is to display the right gestures at the right time. For instance, the signification of a ring gesture can change according to other body movements as well as the utterance that are produced simultaneously [START_REF] Streeck | Elements of Meaning in Gesture[END_REF]. In addition to that, a ring gesture can also be used as a kinesic sign, to substitute speech [START_REF] Streeck | Elements of Meaning in Gesture[END_REF]. In this case, other body movement occurring at the same time can change its meaning. For instance, facial expressions of the person doing a ring gesture, can transform the meaning of this gesture: it can be a positive meaning such as "perfect" or "delicious", or a negative one such as "zero" or "worthlessness".

In a human-human interaction, gestures and speech are synchronized in one speaker, or even during an interaction with another speaker [START_REF] Mark L Knapp | Nonverbal communication in human interaction[END_REF]. A little change in one gesture will occur at the same time with the beginning of change in another behavior such as a phonological segment. For instance, stressed syllables are frequently in line with gestural strokes and even eye blinks [START_REF] Mark L Knapp | Nonverbal communication in human interaction[END_REF]. During an interaction, we tend to mimic each-other unconsciously, following the "Chamelon effect" by matching and mirroring each-other with our postures, facially, and vocally [START_REF] Mark L Knapp | Nonverbal communication in human interaction[END_REF]. This way, humans adapt their behavior passively and unintentionally. Gestures and body movements convey emotional intentions [START_REF] Dahl | Visual perception of expressiveness in musicians' body movements[END_REF]. For instance, in [START_REF] Castellano | Automated analysis of body movement in emotionally expressive piano performances[END_REF], they demonstrate that the quantity of motion of the upper body and the velocity of head are sensitive to positive emotional valence of the emotional expression. Developing human-like body language expressions in virtual agents and in robots enhance their expressiveness and improve their sociability.

Modeling agent's non-verbal behavior as well as its gestures' expressivity can be performed in multiple ways, based on different scenarios. In [START_REF] Cafaro | Exploiting evolutionary algorithms to model nonverbal reactions to conversational interruptions in user-agent interactions[END_REF], they designed a behavioral and computational model based on an evolutionary algorithm for generation behaviors following an interruption. They used an interactive genetic algorithm since it is capable of exploring the space of solutions. In [START_REF] Rodriguez | Spontaneous talking gestures using generative adversarial networks[END_REF], they use Generative Adversarial Networks (GAN) to generate gestures using upper body sequence of joint positions which are aligned with each utterance. They show that high expressivity can be achieved with a low number of degrees of freedom. In [START_REF] Yoon | Robots learn social skills: End-to-end learning of co-speech gesture generation for humanoid robots[END_REF], they present a learning-based co-speech gesture generation system. Since the co-speech gesture generation problem consists of mapping a sequence of words to a sequence of human poses, this problem is close to the neural machine translation that uses sequence to sequence mapping. Therefore, they chose to use a neural network architecture that is composed of an encoder (for speech-text understanding) and a decoder (to produce a sequence of gestures/frame by frame poses). The model captures speech context by using a bidirectional recurrent neural network, and the results are sent to the decoder to produce gesture motions. They have used a recurrent neural network for decoding, with a soft attention mechanism so that the decoder focuses on specific words instead of the whole utterance when producing poses. The model produces different types of gestures: iconic, metaphoric, deictic, and beat gestures.

PROSODIC EXPRESSIVITY

Humans' voice is the "mirror of the soul": it can reflect our emotional states and feelings. Our most personal experience can be expressed by the mean of speech, in multiple degree of variation, rendering each expression a unique act. Prosody refers to all suprasegmental aspects of speech [START_REF] Xu | Prosody, tone and intonation[END_REF]. It involves pitch, duration, amplitude, and voice quality that are used to perform lexical contrasts and convey meaning. As the articulatory functional principle states, speech is a system for transmitting communicative meanings that can be lexical, post-lexical, affective, and social ones. Nowadays, a key problem in the development of Text-to-Speech Systems (TTS) is that they only focus on the physiological (gender, age, intrinsic and co-intrinsic characteristics) speech generation as well as short-term variations of speech parameters (i.e the articulations) [START_REF] Obin | MeLos: Analysis and modelling of speech prosody and speaking style[END_REF]. Therefore, TTS systems are very monotonous, and prosody is a real concern since the generated prosodic parameters have a poor variability. Thus, it is very important to consider implementing expressive TTS systems when designing virtual agents or even physical robots. TTS systems used in robotics are very monotonous, lacking prosodic expressivity. Some of the prosodic tools that can express a speaker's affective and emotional state are non-lexical sounds. Non-lexical sounds are non-phonological sounds that are generated during the speech or outside the talk turn. These sounds are prosodically relevant, and they can convey the speaker's emotions, intentions, attitudes and mental state [START_REF] Ameka | Interjections: The universal yet neglected part of speech[END_REF][START_REF] Schröder | Experimental study of affect bursts[END_REF][START_REF] Schröder | Perception of non-verbal emotional listener feedback[END_REF]. There exist different types of nonlexical sounds such as interjections (i.e. Aie! Ah!), fillers (words used for pausing, i.e. um, okay, uh), grunts (guttural sounds made by humans/animals), and bursts (very brief, discrete, nonverbal expressions of affect in both face and voice as triggered by clearly identifiable events [START_REF] Eva | Affect bursts: dynamic patterns of facial expression[END_REF], i.e. Wow!). All these non-lexical sounds are pure prosodic tools and could be indicators of the emotional and affective of the speaker. In [START_REF] Aubergé | The eee corpus: socio-affective" glue" cues in elderlyrobot interactions in a smart home with the emoz platform[END_REF], they show that these sounds given to a robot in a smart home create a strong "socio-affective glue" with elderly. "Glue" designates the process that is dynamically constructed during an interaction which is considered as an emerging global system whose interactants are not complete subsystems [START_REF] Aubergé | La glu socio-affective: enjeux et risques du robot «compagnon[END_REF]. This socio-affective glue allows speakers to actively build communicative channel during an interaction. Imitation can also produce a socio-affective "glue" in children language acquisition [START_REF] Tomasello | Understanding and sharing intentions: The origins of cultural cognition[END_REF]. Human-machine interactions can become as natural as human-human interactions by employing speech with prosodic expressiveness, that is, speech with emotional content [START_REF] Monzo | Voice quality modelling for expressive speech synthesis[END_REF]. The emotional content of speech can be conveyed by manipulating the voice quality as well as prosody parameters (f0, duration, and energy). Recent work suggest employing both quality voice and prosody parameters to improve the acoustic modelling of expressive speech. In the last few years, research has focused on the Harmonic plus Noise Model (HNM) to generate high quality and versality and perform speech transformation by modifying the speech prosody. For instance, humans can combine different voice pitch with different body motions to signal their desire to take the floor during interactions, and as a result, interlocutors react to their signals and therefore making the turn-taking mechanism happen [START_REF] Starkey | Some signals and rules for taking speaking turns in conversations[END_REF].

In a human-human interaction, speech and movement are rhythmically coordinated in syllables and even smaller units [START_REF] Mark L Knapp | Nonverbal communication in human interaction[END_REF]. For instance, humans can combine different voice pitch with different body motions to signal their desire to take the floor during interactions, and as a result, interlocutors react to their signals and therefore making the turn-taking mechanism happen [START_REF] Starkey | Some signals and rules for taking speaking turns in conversations[END_REF].

DISCUSSION

The previous two sections summarized the latest work related to gestural and prosodic expressivity. Despite the great findings and conclusions that these work draw, further research efforts should be directed at the development of more expressive gestures and prosody. For instance, as we have previously discussed, in [START_REF] Castellano | Automated analysis of body movement in emotionally expressive piano performances[END_REF] they demonstrate that the quantity of head motion displayed by a pianist is sensitive to positive emotional valence of expression. The main limitation of this study is that their analysis and experiments are based on one musician (pianist) playing one instrument (the piano). In addition to that, they didn't investigate all emotional expressive movements, and analyze various modalities of expressions that musicians can do while playing (i.e. gaze, posture, facial expressions, ...). In [START_REF] Rodriguez | Spontaneous talking gestures using generative adversarial networks[END_REF], they use GANs to generate gestures using upper body sequence of joint positions which are aligned with each utterance. They generate gesture movements without taking into account the semantic meaning of the spoken text, nor putting emphasis on important words. In this case, multimodal and soft attention mechanisms [START_REF] Vaswani | Attention is all you need[END_REF] could be used to allow the model to focus on specific parts of the text, instead of looking at the whole utterance. This can be developed under an encoder/decoder framework, to allow finding semantic and syntactic alignments. Additionally, visual attention models could be used to pay attention to specific parts of the upper body region and reduce the amount of the information to process. Moreover, in [START_REF] Yoon | Robots learn social skills: End-to-end learning of co-speech gesture generation for humanoid robots[END_REF], they present a learning-based co-speech gesture generation system. This system makes excessive gestures and participants in the experiments noted that motions were "jerky", "fast" and "jump around from motion to motion". Moreover, participants noted that gestures were faster than speech which makes the interaction looks unnatural. In addition to that, the system lacks the personalization of robots' gestures: all robots make the same gestures when exposed to one speech context. There are no parameters to control the robots' expressiveness. Furthermore, prosody is not taken into consideration when generating co-speech gestures: the system lacks prosodic expressiveness.

FUTURE WORK

For future work, we plan to model the gestural and prosodic expressiveness, while taking into consideration all the points discussed in the previous section. Emphasis will be placed on two essential aspects of the modelling. On one hand, we will focus on the development of architectures that are structured on several time scales to improve the modeling of prosodic and gestural variability at the sentence level as well as the whole speech. On the other hand, we will focus on the learning of a coherent multimodal behavior by using multimodal attention mechanisms applied to the synchronicity of the generated prosody and gestures. Furthermore, we will work on making the agent's behavior coherently aligned with that of its interlocutor by using interactive and imitation learning.

ACKNOWLEDGMENTS

We would like to thank Sorbonne Center for Artificial Intelligence (SCAI) for funding this thesis.


Jean-Baptiste Thomazo

Eric Lauga

Benjamin Le Révérend

E Wandersman

A M Prevost

Collective stiffening of soft hair assemblies

Many living systems use assemblies of soft and slender structures whose deflections allow them to mechanically probe their immediate environment. In this work, we study the collective response of artificial soft hair assemblies to a shear flow by imaging their deflections. At all hair densities, the deflection is found to be proportional to the local shear stress with a proportionality factor that decreases with density. The measured collective stiffening of hairs is modeled both with a microscopic elastohydrodynamic model that takes into account long-range hydrodynamic hair-hair interactions and a phenomenological model that treats the hair assemblies as an effective porous medium. While the microscopic model is in reasonable agreement with the experiments at low hair density, the phenomenological model is found to be predictive across the entire density range.

Many living systems use assemblies of soft and slender structures to mechanically probe their immediate environment. In animals, their deflection triggers the response of mechanosensitive nervous endings embedded at their base that convert mechanical stresses into a neural response [1]. Rodents, in particular, use their facial whiskers to spatially localize objects and discriminate their texture by contact [START_REF] Arabzadeh | Scholarpedia of Touch[END_REF]. Spiders and crickets have legs covered with hairs that can detect minute changes in an air flow [START_REF] Bathellier | [END_REF]4]. Fish have a lateral line that consists of an assembly of hair structures (neuromasts) allowing them to orient themselves in a flow and detect the presence of prey and predators in their vicinity [5]. The human tongue itself is covered with filiform papillae that are deformed during food mastication and participate in in-mouth texture perception [START_REF] Ghom | Textbook of Oral Pathology[END_REF][START_REF] Yamashita | Tongue: Anatomy, Kinematics and Diseases[END_REF][START_REF] Doty | Handbook of Olfaction and Gustation[END_REF]. At smaller length scales, that of cells, slender structures (primary cilia) play an important role in mechanosensation processes [START_REF] Malicki | [END_REF]. Given such ubiquity, numerous biomechanical models have been developed to predict the deformation of elongated structures when submitted to contact [10,11] and viscous stresses [12][13][14]. To test these models within simplified frameworks, artificial hairy systems have been used. These usually consist of slender pillars anchored to a substrate, whose deflections are monitored optically under controlled stresses [15][16][17].

The deflection of an isolated pillar in a viscous flow has been successfully predicted using elastohydrodynamics [13,14,18]. In biological systems, however, hairs are usually densely packed and their mechanical behavior is likely subjected to hydrodynamic interactions. Indeed, the presence of a pillar in a flow disturbs the velocity field around it and produces a long-range flow perturbation. When two pillars are sufficiently far apart, these perturbations decay sufficiently fast and hydrodynamic interactions are negligible. As pillars get closer, hydrodynamic interactions play an increasing role and modify the deflection of pillars. Understanding mechanotransduction processes of hair assemblies thus requires one to take into account the hydrodynamic couplings. Such interactions have been explored in the context of cell locomotion [19], fish schools [20], and bird flocks [21], but are barely studied for anchored and passive fiber assemblies.

In a previous work [18], we have shown that deflections of an isolated elastomeric pillar submitted to a shear flow are proportional to the local shear stresses. In the context of in-mouth texture perception, we concluded that filiform papillae could act as sensitive stress sensors. In this Rapid Communication, we extend our biomimetic approach to assemblies of pillars at varying surface densities. We probe experimentally and theoretically how the density of pillars changes their collective deflections.

We used a minimal biomimetic setup sketched in Fig. 1(a) (see [18] and Supplemental Material [22]). Briefly, it consists in mimicking soft hair assemblies with a pool made of an elastomer, whose bottom is decorated with cylindrical pillars of diameter 2a = 100 μm and length L = 435 ± 7 μm. The pool is placed at the bottom of a rheometer (MCR 302, Anton Paar) whose PP40 planar rotating tool is used to impose the flow. This rheometer has built-in fluorescence microscopy capabilities allowing one to image at 100 frames/s (fps) the pillars tips through the optically transparent pool. This is done thanks to fluorescent particles embedded at the tips. Soft hair assemblies were fabricated using micromilling and elastomer molding techniques. Two types of patterns were drilled on the same mold, a first one consisting of isolated holes serving as references, and a second one comprising a square pattern of densely distributed holes of mesh size d. Hair assemblies were obtained by pouring in the molds a liquid PDMS (polydimethylsiloxane; Sylgard 184, Dow Corning, USA)-crosslinker mixture, followed by a curing in an oven (12 h, T = 65 • C) and unmolding. Figure 1(b) shows an example of a resulting substrate imaged using a macroscope with fluorescence imaging capabilities. The Young's modulus of the PDMS elastomer was measured to be E = 2.7 ± 0.8 MPa. Solutions of glycerol (Sigma-Aldrich) mixed in Millipore deionized water at different concentrations were used. Their dynamic viscosities η were measured with the rheometer operating in a plate-plate geometry. Pillar tip deflections δ were measured [18] by correlating images of a pillar in its deformed state with a reference image where the pillar is at rest [Fig. 1(c)]. From the two-dimensional correlation function, we extract the maximum displacement δ with a spatial resolution of about 20 nm [Fig. 1(d)].

Experiments were carried out as follows. First, a substrate with a given number density of pillars n = 1/d 2 was positioned on the rheometer's base. Accurate determination of the gap H (i.e., distance from the base of the pool to the lower surface of the rotating plate) was determined. The pool was then filled with the liquid. The rotating plate was finally brought 550 μm above the pillars summits (yielding H = 1 mm) and set in motion at a constant angular velocity ω, causing pillars deflection. Each experiment consisted of 11 successive 10-s-long measurements. The first one was performed without any flow to provide an unperturbed reference state, while the ten subsequent measurements were done with increasing ω distributed on a logarithmic scale. Their values were chosen so that δ ranges from 1 to 10 μm. The analysis of the displacements was performed in the steady-state regime, yielding δ as a function of the shear stress σ = η γ with γ = ρω/H the shear rate and ρ the radial coordinate of the pillar [Fig. 1(a)]. Given the error on the gap H thickness (typically 20 μm [18]), the relative error on σ is about 2%. Over the whole range of shear rates γ , the Reynolds number Re = ρL 2 γ /η varies from 10 -4 to 10 -1 , and thus the flow remains laminar in all cases. For each density n, six independent experiments were carried out to measure the deflections of three different isolated pillars and three pillars in the dense region.

As shown previously [18], in steady state, the maximum displacement of an isolated pillar δ 0 increases linearly with σ (Fig. 2, diamonds), in agreement with the model of [13] and writes

δ 0 = K 0 L 5 a 4 E ηρω H = κ 0 σ (1)
with K 0 a numerical factor whose value is determined experimentally. Note that depending on the substrate, κ 0 can vary from 0.5 to 5 μm/Pa due to slight sample to sample variations of L and E . This explains why we used composite pools consisting of two regions with isolated and dense pillars. At all n, we still measure a linear relationship between δ and σ with δ = κσ (Fig. 2). Note that we normalized the deflection by κ 0 to take into account sample to sample variability. The slope of these normalized curves is then κ/κ 0 = δ/δ 0 . It is smaller than 1 and decreases with n, implying that denser pillars bend less than isolated ones. Figure 3(a) shows, for all combined experiments, the dependence of δ/δ 0 with n normalized by a characteristic density n 0 = 1/L 2 ≈ 5.3 mm -2 . Note that the reference point at n = 0.04 mm -2 (n/n 0 = 7 × 10 -3 ) has been added on the graph with δ/δ 0 = 6) with the five nearest neighbors [respectively, Eq. (7) in the continuum limit]. The red solid curve is a fit with Eq. ( 9) based on the phenomenological model of [23] where the value of α has been fitted. Points surrounded by dashed line circles correspond to those in Fig. 2 with the same color code. Inset: Log-linear plot of the main graph. (b) Sketch of the hair assembly system with the geometrical characteristics used in the dilute model. The upper rigid plate positioned at a distance H from the bottom of the pool is sheared along the x direction with a velocity V.

1. Clearly, within error bars, δ/δ 0 decreases nonlinearly with n.

Theoretically, the bending of an isolated elastic cylindrical pillar subject to a given flow has been derived in [13]. In steady state, the balance between bending and the drag force from the fluid yields (in units of L)

d 4 δ dy 4 = -u x (y), (2)
where u x is the flow velocity along the x direction and y the pillar's longitudinal coordinate [Fig. 3(b)]. Equation ( 2) can be solved with boundary conditions δ(0) = 0, δ (0) = 0 (clamped pillar at its base) and δ (1) = 0, δ (1) = 0 (free pillars tips), where prime symbols stand for spatial derivatives with respect to y. For instance, for an isolated cylindrical pillar subjected to a shear flow, one obtains Eq. ( 1). As a first attempt to model our data, we have derived an exact calculation of the induced flow perturbation by all pillars at the location of a given pillar. A pillar's deformation along the flow direction u = V y/H [with V the upper plate velocity; see Fig. 3(b)] is due to the drag force from the fluid. In turn, the pillar exerts an opposite force with the same magnitude in the -u direction. Consequently, this force tends to decrease the effective total flow in the u direction acting on all other pillars. One thus expects a reduction of δ in pillar assemblies, i.e., a collective stiffening. Below, we first compute the flow field induced by a single pillar and then sum up all individual pillars contributions to obtain the net flow from the whole assembly.

The flow induced by one pillar is calculated as resulting from the superposition of point forces along the pillar. For a point force located at a distance h above the flat bottom surface, and assuming no-slip boundary conditions, the flow can be obtained using the hydrodynamic image method [24,25]. At a given location r pq from the point force F p , the flow can be computed analytically in the dilute limit (|r pq | L) as

u p→q (r pq ) = 3h 4πη (F p • e pq )e pq |r pq | 3 y, (3)
where e pq = r pq /|r pq |. The whole net flow induced by one pillar p can be computed by the superposition of the force per unit length on the fluid f p along the length of the pillar. In the limit of small deformations, it may be written as

u net p→q (r pq ) = 3 4πη L 0 hf p (h)dh • e pq |r pq | 3 ye pq . ( 4
)
Taking f p = -4πηu(h)e x as a viscous force density and approximating the background flow as a shear flow u(h) = γ h, one obtains

u net p→q (r pq ) = -( γ y) L 3 |r pq | 3 (e x • e pq ) e pq . ( 5
)
The collective deformation in the dilute limit is obtained by summing up on all pillars these hydrodynamic interactions. The total flow acting on pillar q is therefore u q = p =q u net p→q (r pq ). The deflection δ q of the tip of pillar q is obtained by solving Eq. ( 2) with the total flow given by the sum of the background flow plus perturbations, u + u q , yielding

δ q δ 0 = e x -L 3 p =q 1 |r pq | 3 (e x • e pq )e pq . ( 6
)
The right-hand side of Eq. ( 6) can be computed analytically for both square and hexagonal lattices of pillars (see Supplemental Material [22]). In both cases, we obtain that this term does not depend on the orientation of the lattice with respect to e x . Alternatively, we may estimate this term by taking the continuous limit. In cylindrical coordinates centered on pillar p, with e r and e θ the unit vectors, and r the position of the pillar, Eq. ( 6) becomes

δ q δ 0 = e x - 2π 0 ∞ d n
cos θ e r r 3 r dr dθ = 1 -π (nL 2 ) 3/2 . (7) Predictions of Eq. ( 6), taking into account the five nearest neighbors to match with our experimental system, are plotted in Fig. 3(a) with the dashed line. The result from the continuous limit approximation of Eq. ( 7) is plotted with the dot-dashed line. The theoretical results agree with the experiments in the small n/n 0 limit, as expected from the dilute approximation.

To go beyond our microscopic model valid in the dilute limit, we use the model of Alvarado et al. [23]. In that work, the authors computed the shear flow in a dense assembly of high aspect ratio cylindrical pillars treated as a porous medium of effective height h e . Solving both Stokes' equation for the flow above the pillar bed and Brinkman's equation for the flow in the bed, they obtain the flow velocity u(y) valid for 0 < y < h e as

u(y) = V sinh(y/ ) (H -h e ) cosh(h e / ) + sinh(h e / ) , (8)
where V = ρω is the velocity of the upper plate [Fig. 3(b)], the pore size, and H the gap between the plates. For small deformations δ L, and thus h e L. To compute pillars bending, we solved Eq. ( 2) with u x given by Eq. ( 8), yielding δ δ 0 = 120 11

β 5 S -β 4 - 1 2 β 3 S + 1 3 β 2 C (1 -L/H )C + β(L/H )S (9)
with β = /L, S = sinh(β -1 ), and C = cosh(β -1 ). Taking the pore size as = α/ √ n = αd, the data of Fig. 3 have been fitted with Eq. ( 9) with α as a free parameter. This model captures our data on the whole range of n/n 0 [Fig. 3(a)] with α = 0.35 ± 0.02 and thus a pore size of the order of the mesh size d. The parameter α relates the mesh size of the lattice to the pore size of the hair assembly. A similar value of 0.46 was obtained for turbulent flow over carbon nanotube forests by Battiato et al. [26].

Soft hair assemblies are ubiquitous in biology [14]. Recently, Pellicciotta et al. [START_REF] Pellicciotta | Proc. Natl. Acad. Sci. USA[END_REF] have studied the collective beating of active motile cilia of brain cells subjected to oscillatory flows. They demonstrated an enhanced hydrodynamic screening with the number of cilia which reduces their synchronization with the external flow. Similarly, in flagellar systems, pairs of beating flagella of unicellular micro-organisms can be synchronized solely through hydrodynamic interactions in the far field [START_REF] Brumley | [END_REF]. However, for micro-organisms bearing few flagella, this synchronization is more complex and involves an elastic basal coupling in addition to hydrodynamics interactions [START_REF] Wan | Proc. Natl. Acad. Sci. USA[END_REF]. Overall, there is, however, a lack of quantitative studies of how dense assemblies of pillars deform in flows. Coq et al. [START_REF] Coq | [END_REF] investigated the dynamics of a bed of magnetic microcilia distributed on a square lattice and submitted to a precessing magnetic field. They showed that at high surface density, the collective beating yields a symmetry breaking of the circular precession. Like us, they interpreted their results using the models of Refs. [24,25]. They derived an expression for the dependence of the amplitude of the hydrodynamic interactions versus density, which is very similar to our Eq. ( 6) (see Supplemental Material of [START_REF] Coq | [END_REF]). However, they do not test experimentally its dependence with the pillars density. Moreover, it is only valid at low pillars density when n 1/L 2 and thus cannot apply to their experimental results for which nL 2 ≈ 20. In another context, Bhushan [31] has also reported drag reductions in microtextured channels with undeformable pillars. However, the reduction results from superhydrophobicity effects and not hydrodynamic interactions.

Our study provides a complete experimental test of this model over a wide range of n. We demonstrate that the bending of pillars remains proportional to the shear stress at any n. We also show that in the dilute limit, our microscopic model is in reasonable agreement with our data. The collective bending of the hair assemblies decays typically over a density of order 1/L 2 . In addition, we demonstrate that hydrodynamical interactions do not depend on the topology of the lattices (square or hexagonal) nor on its orientation with respect to the flow. At higher n, typically nL 2 0.5, our data show discrepancies with the dilute model. This could result from the fact that, to compute Eq. ( 3), we neglected the near-field terms in 1/r 5 which are expected to have important contributions at large n. To describe our measurements over the whole pillar density range, we have thus used the recent phenomenological model of [23] describing the pillar assemblies as a porous medium. In [23], the authors have successfully tested their model, however limited to three different densities (all above n 0 ), and they did not probe the deflections of pillars induced by such flows. We show here that solving Eq. ( 2) with their flow field allows one to reproduce faithfully the pillars deflections at any density with the porosity as a single fit parameter. We find again that the characteristic density is of order 1/L 2 . This analytical method complements the very recent numerical predictions of Stein and Shelley [32]. Interestingly, an asymptotic expansion of Eq. ( 9) at very high density (n n 0 ) yields δ/δ 0 ∼ 1/n, in agreement with [32].

In many biological systems, the deformation of soft hair assemblies is the primary mechanical input measured by mechanoreceptors. We have shown that at high density of pillars, their effective deformation can be significantly reduced. In the particular case of mammalian tongues for instance, filiform papillae are densely packed with a typical density nL 2 that ranges from 0.1 to 1. Our work shows that at these densities, the reduction of papillae deflections should reach about half of their nominal deflection if papillae were isolated. Biologically, this mechanism could induce an enhanced protection of the sensory structure by avoiding large deformations. We have also shown that this collective stiffening is independent of spatial organization and orientation of the lattice with respect to the flow. It therefore suggests that such sensory systems are robust to flow direction. Beyond the particular case of vertebrate tongues, our results should be also applicable to a wide range of biological systems.

FIG. 1 .

 1 FIG. 1. (a) Sketch of the experimental setup (side view along a diameter). (b) Composite image of a PDMS substrate with a density of pillars n ≈ 4 mm -2 obtained with fluorescence imaging. The green color indicates the presence of green fluorescent particles on the pillar's tips. (c) Typical fluorescence snapshots of a pillar's summit at rest (left panel) and in steady flow (right panel). The green dashed line circles delimit the perimeter of the pillar. (d) Semilogarithmic plot of the displacement δ of a single pillar versus time during a typical experiment after a sudden start of the rheometer's tool at t = 0 s. Inset: sketches of sectional views of a pillar at rest (left panel) and subject to a steady shear liquid flow (right panel).

1 FIG. 2 .

 12 FIG.2. Log-log plot of the normalized displacement, δ/κ 0 , of a single pillar's tip in steady state versus the local shear stress σ for four different pillars number densities, n = 0.04 mm -2 (referred to as an isolated pillar; diamonds), n = 1 mm -2 (circles), n = 4 mm -2 (squares), and n = 10 mm -2 (stars). For these experiments, the angular velocity ω was varied and different pillar's radial positions ρ and viscosities η were used (ρ = 5.6, 7.0, 7.5 mm and η = 0.458, 0.320, 0.468 Pa s for n = 1, 4, 10 mm -2 , respectively). Solid lines are linear fits.

FIG. 3 .

 3 FIG. 3. (a)Dimensionless pillar tip deformation δ/δ 0 versus normalized pillars density n/n 0 with n 0 = 5.3 mm -2 (squares). Each point is an average over nine experiments and error bars are taken as the standard deviation over these nine measurements. The green dashed (respectively, blue dash-dotted) line is the prediction of Eq. (6) with the five nearest neighbors [respectively, Eq. (7) in the continuum limit]. The red solid curve is a fit with Eq. (9) based on the phenomenological model of[23] where the value of α has been fitted. Points surrounded by dashed line circles correspond to those in Fig.2with the same color code. Inset: Log-linear plot of the main graph. (b) Sketch of the hair assembly system with the geometrical characteristics used in the dilute model. The upper rigid plate positioned at a distance H from the bottom of the pool is sheared along the x direction with a velocity V.

The authors acknowledge financial support from Centre de Recherche et Développement Nestlé S.A.S., Marne la Vallée, France and Société des Produits Nestlé SA, Vevey, Switzerland. They also thank I. Barbotteau and G. Marchesini for their careful reading of the manuscript and support. Fi-nally, the authors acknowledge the support of C. J. Pipe and thank G. Debrégeas and C. Frétigny for fruitful discussions.


Edward Beeching

Jilles Dibangoye

Olivier Simonin

Christian Wolf

Learning to plan with uncertain topological maps

Keywords: Visual navigation, topological maps, graph neural networks

We train an agent to navigate in 3D environments using a hierarchical strategy including a high-level graph based planner and a local policy. Our main contribution is a data driven learning based approach for planning under uncertainty in topological maps, requiring an estimate of shortest paths in valued graphs with a probabilistic structure. Whereas classical symbolic algorithms achieve optimal results on noise-less topologies, or optimal results in a probabilistic sense on graphs with probabilistic structure, we aim to show that machine learning can overcome missing information in the graph by taking into account rich high-dimensional node features, for instance visual information available at each location of the map. Compared to purely learned neural white box algorithms, we structure our neural model with an inductive bias for dynamic programming based shortest path algorithms, and we show that a particular parameterization of our neural model corresponds to the Bellman-Ford algorithm. By performing an empirical analysis of our method in simulated photo-realistic 3D environments, we demonstrate that the inclusion of visual features in the learned neural planner outperforms classical symbolic solutions for graph based planning.

Introduction

A critical part of intelligence is navigation, memory and planning. An animal that is able to store and recall pertinent information about their environment is likely to exceed the performance of an animal whose behavior is purely reactive. Many control and navigation problems in partially observed 3D environments involve long term dependencies and planning. It has been shown that humans and other animals navigate through the use of waypoints combined with a local locomotion policy [START_REF] Wang | Human spatial representation: Insights from animals[END_REF][START_REF] Gupta | Unifying map and landmark based representations for visual navigation[END_REF]. In this work, we mimic this strategy by proposing a hierarchical planner, which performs high-level long term planning using an uncertain topological map (a valued graph including visual features) combined with a local RL-based policy navigating between high-level waypoints proposed by the graph planner. Our main contribution is a way to combine symbolic planning Fig. 1: A trained agent navigates to a goal location with a hierarchical planner. A high-level planner proposes new target nodes in a topological map (a graph), which are used as an objective for a local point-goal policy. The graph is estimated from an explorative rollout and, as such, uncertain: the opacities of the edges correspond to estimations of connectivity between nodes (darker lines = higher confidence). In this example we observe a low probability of connection between the node at the agent's position (orange) and its nearest neighbor, whereas from the visual observation associated to the node we can see there is a traversable space between the two nodes.

with machine learning, and we look to structure a neural network architecture to incorporate landmark based planning in unseen 3D environments.

When solving visual navigation tasks, biological or artificial agents require an internal representation of the environment if they want to solve more complex tasks than random exploration. We target a scenario where an agent is trained on a large-scale set of 3D environments to learn to reason on planning and navigation. When faced with a previously unseen environment, the agent is given the opportunity to build a representation by doing an explorative rollout from a previously learned explorative policy. It can then exploit this internal representation in subsequent visual navigation tasks. This corresponds to many realistic situations, where robots are deployed to indoor environments and are allowed to familiarize themselves before performing their tasks [START_REF] Savinov | Semi-parametric topological memory for navigation[END_REF].

Our agent constructs an imperfect topological map of its environment in the form of a graph, where nodes correspond to places and valued edges to connections. Edges are assigned two different values, the first one being spatial distances, the second one being probabilities indicating whether it is possible to navigate between the two nodes. Nodes are also assigned rich visual features extracted from images taken at the corresponding places in the environment. After deployment, the agent faces visual navigation tasks requiring it to find a specific location in the environment provided by a set of images corresponding to different viewpoints, extending the task proposed in [START_REF] Zhu | Target-driven visual navigation in indoor scenes using deep reinforcement learning[END_REF]. The objective is to identify the goal location in the internal representation, and to provide an estimate for the shortest path to it. The main difficulty we address here is the fact that this path is an estimate only, since the ground truth path is not available during testing / deployment.

Whilst planning in graphs with known connectivity has been solved for many decades [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF][START_REF] Bellman | On a routing problem[END_REF], planning under uncertainty remains an ongoing area of research. Whereas optimal results in a probabilistic sense exist for graphs with probabilistic connectivity, we aim to show that machine learning can overcome missing information in the graph by taking into account rich high-dimensional node features, in particular features extracted from image observations associated with specific nodes. We train a graph neural network in a fully supervised way to predict estimates of the shortest path, using vision to overcome uncertainty in the connectivity information. We present a new variant of graph neural networks imbued with specific inductive bias, and we show that this structure can be parameterized to fallback to the classical Bellman-Ford algorithm.

Figure 1 illustrates the hierarchical planner: a neural graph based planner runs an outer loop providing estimates for next way-point on a graph, which are used as target nodes for a local RL-based policy running an inner loop and providing feedback to high-level planner on reached locations. Both planners take into account visual features, either stored in the graph (graph based planner), or directly as observations provided by the environment (local policy). The two planners are trained separately -the graph based planner in a fully supervised way from ground truth graphs, the local policy with RL and a point-goal strategy. This work makes the following contributions:

-A hierarchical model combining high-level graph based planning with a local point goal policy for robot navigation; -A trainable high-level neural planner which combines an uncertain topological map (graph) with rich node features to learn to estimate shortest paths in noisy and unknown environments. -A variant of graph networks encoding inductive bias inspired by dynamic programming-based shortest path algorithms. -We evaluate the performance of the method in challenging and visually realistic 3D environments and show that it outperforms optimal symbolic planning on noisy topological maps.

Related work

Classical planning and graph search -A large body of work is available on classical planning on graphs, notable references include [START_REF] Lavalle | Planning algorithms[END_REF][START_REF] Remolina | Towards a general theory of topological maps[END_REF]. In robotics, there have been a number of works applying classical planning in topological maps for indoor robot navigation, for instance [START_REF] Shatkay | Learning topological maps with weak local odometric information[END_REF]54].

Planning under imperfect information -In many realistic robotic problems, the current state of the world is unknown. Though sensor observations provide measurements about the current state of the world, these measurements are usually incomplete or noisy because of disturbances that distort their values.

Planning problems that face these issues are referred to as planning problems under imperfect information. Research on this topic has a long history, which can be traced back to the seminal work by [START_REF] Åström | Optimal control of markov processes with incomplete state information[END_REF] presenting the first non-trivial exact dynamic programming algorithm for partially observable Markov decision processes (POMDPs). While there are other models [31, chap 12], POMDPs emerged as the standard framework to formalize and solve (single-agent) sequential decision-making problems with imperfect information about the state of the world [START_REF] Kaelbling | Planning and acting in partially observable stochastic domains[END_REF]. Since the agent does not have access to the actual state of the world, it acts based solely on its entire history of actions and observations, or the corresponding belief state, i.e., the posterior probability distribution over the states given the history [START_REF] Åström | Optimal control of markov processes with incomplete state information[END_REF][START_REF] Smallwood | The optimal control of partially observable markov processes over a finite horizon[END_REF]. Approaches for finding optimal solutions have been intensively investigated in the 2000s, ranging from dynamic programming [START_REF] Kaelbling | Planning and acting in partially observable stochastic domains[END_REF] to heuristic search methods [START_REF] Smith | Heuristic search value iteration for pomdps[END_REF][START_REF] Kurniawati | Sarsop: Efficient point-based pomdp planning by approximating optimally reachable belief spaces[END_REF]. Key to these approaches is the idea that one can recast the original problem into a continuous-state fully observable Markov decision process, where states are belief states or histories [START_REF] Åström | Optimal control of markov processes with incomplete state information[END_REF]. Doing so allows theory and algorithm that applies for MDPs to also apply to POMDPs, albeit in much larger (and possibly continuous) state space. Another significant result of this literature is proof that the optimal value function is a piece-wise linear and convex function of the belief states, which allows the design of algorithms with faster rates of convergence [START_REF] Smallwood | The optimal control of partially observable markov processes over a finite horizon[END_REF]. For a thorough discussion on existing solvers for POMDPs, the reader can refer to [START_REF] Shani | A survey of point-based pomdp solvers[END_REF].

Deep Reinforcement Learning -The field of Deep Reinforcement Learning (RL) has gained attention with successes on board games [START_REF] Silver | A general reinforcement learning algorithm that masters chess, shogi, and go through self-play[END_REF] and Atari games [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF]. Recent works have applied Deep RL for the control of an agent in 3D environments [START_REF] Mirowski | Learning to Navigate in Complex Environments[END_REF] [24], exploring the use of auxiliary tasks such as depth prediction, loop detection and reward prediction to accelerate learning. Other recent work uses street-view scenes to train an agent to navigate in city environments [START_REF] Mirowski | Learning to Navigate in Cities Without a Map[END_REF]. To infer long term dependencies and store pertinent information about the partially observable environment, network architectures typically incorporate recurrent memory such as Gated Recurrent Units [START_REF] Chung | Gated Feedback Recurrent Neural Networks[END_REF] or Long Short-Term Memory [START_REF] Hochreiter | Long Short-Term Memory[END_REF]. Extensions to memory based neural approaches began with Neural Turing Machines [START_REF] Graves | Neural turing machines[END_REF] and Differentiable Neural Computers [START_REF] Graves | Hybrid computing using a neural network with dynamic external memory[END_REF], and have since been adapted to expand the capacity of Deep RL agents [START_REF] Wayne | Unsupervised predictive memory in a goal-directed agent[END_REF]. Spatially structured memory architectures have been shown to augment an agent's performance in 3D environments and are broadly split into two categories: metric maps which discretize the environment into a grid based structure and topological maps which produce node embeddings at key points in the environment. Research in learning to use a metric map is extensive and includes spatially structured memory [START_REF] Parisotto | Neural map: Structured memory for deep reinforcement learning[END_REF],

Neural SLAM based approaches [START_REF] Zhang | Neural SLAM[END_REF] and approaches incorporating projective geometry and neural memory [START_REF] Gupta | Cognitive mapping and planning for visual navigation[END_REF][START_REF] Bhatti | Playing doom with slam-augmented deep reinforcement learning[END_REF], these techniques are combined, extended and evaluated in [START_REF] Beeching | Egomap: Projective mapping and structured egocentric memory for deep rl[END_REF]. Other notable works in include that of Value Iteration Networks (VIN) [START_REF] Tamar | Value iteration networks[END_REF] which approximate the value iteration algorithm with a CNN, applied planning in small fully observable state spaces (grid worlds). While VIN and our work structure planners, VINs use convolutions to approximate classical value iteration, while we use a graph representation and a novel GNN architecture with recurrent updates to approximate the Bellman-Ford algorithm. [START_REF] Karkus | Qmdp-net: Deep learning for planning under partial observability[END_REF] plans under uncertainty in partially observable gridworld environments. Here uncertainty refers to POMPs, the classical QMDP algorithm is used as inductive bias for a neural network, whereas in our work uncertainty is over node connectivity in a graph constructed in a previously unseen environment. [START_REF] Srinivas | Universal planning networks[END_REF] which is applied in observable state spaces to learn a forward model in a latent space to plan appropriate actions; they are not hierarchical, are not graph-based and do not appear to plan under uncertainty. Similar to ours, they are applied to goal driven problems.

Research combining learning, navigation in 3D environments and topological representations has been limited in recent years with notable works being [START_REF] Savinov | Semi-parametric topological memory for navigation[END_REF] who create graph a through random exploration in ViZDoom RL environment [START_REF] Kempka | ViZ-Doom: A Doom-based AI research platform for visual reinforcement learning[END_REF]. [START_REF] Eysenbach | Search on the replay buffer: Bridging planning and reinforcement learning[END_REF] also performs planning in 3D environments on a graph-based structure created from randomly sampled observations, with node distances estimated with value estimates. The downside of these approaches is that in order to generalize to an unseen environment, many random samples must be taken in order to populate the graph.

Graph neural networks -Graph Neural Networks (GNN) are deep networks that operate on graphs directly. They have recently shown great promise in domains such as knowledge graphs [START_REF] Schlichtkrull | Modeling relational data with graph convolutional networks[END_REF], chemical analysis [START_REF] Gilmer | Neural message passing for quantum chemistry[END_REF], protein interactions [START_REF] Fout | Protein interface prediction using graph convolutional networks[END_REF], physics simulations [START_REF] Battaglia | Interaction networks for learning about objects, relations and physics[END_REF] and social network analysis [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF]. These types of architectures enable learning from both node features and graph connectivity. Several review papers have covered graph neural networks in great detail [START_REF] Bronstein | Geometric deep learning: going beyond euclidean data[END_REF][START_REF] Battaglia | Relational inductive biases, deep learning, and graph networks[END_REF][START_REF] Wu | A comprehensive survey on graph neural networks[END_REF][START_REF] Zhou | Graph neural networks: A review of methods and applications[END_REF]. GNNs have been applied to shortest path planning in travelling salesmen problems [START_REF] Li | Combinatorial optimization with graph convolutional networks and guided tree search[END_REF][START_REF] Joshi | An efficient graph convolutional network technique for the travelling salesman problem[END_REF] and it has been reasoned that they can approximate optimal symbolic planning algorithms such as the Bellman-Ford algorithm [START_REF] Xu | What can neural networks reason about?[END_REF]. This work applies a novel variant of GNN in order to solve approximate planning problems, where classical methods may struggle to deal with uncertainty.

Hierarchical navigation with uncertain graphs

We train an agent to navigate in a 3D visual environment and to exploit an internal representation, which it is allowed to obtain from an explorative rollout before the episode. Our objective is image goal, i.e. target-driven navigation to a location which is provided through a (visual) image. We extend the task introduced in [START_REF] Zhu | Target-driven visual navigation in indoor scenes using deep reinforcement learning[END_REF] by generalizing to unseen environment configurations without the need to retrain the agent for a novel environment.

From the explorative rollout obtained with an agent trained with RL, which is further described in section 3.3, we create an uncertain topological map covering the environment, i.e. a valued graph G={V, V , E, L, D}, where V={1, . . . N } is a set of nodes, V is a K×N matrix of rich visual node features of dimensions K, E ∈ [0, 1] N ×N is a set of edge probabilities where E i,j is the probability of having an edge between nodes i and j, L is a matrix of node locations and D is a distance matrix, where D i,j is a distance between nodes i and j. While D encodes a distance in a path planning sense, E encodes the probability of j being directly accessible from i with obstructions. The uncertainty encoded by this probability can be considered to be a combination of aleatory variability, i.e. uncertainty associated with natural randomness of the environment, as well as epistemic uncertainty, i.e. uncertainty associated with variability in computational models for estimating the graph, in our case the explorative policy trained with RL and taking into account visual observations.

Once the topological map is obtained, the objective of the agent at each episode is to navigate to a location given an image, which is provided as additional observation at each time step. The agent acts in 3D environments like Habitat [START_REF] Savva | Habitat: A Platform for Embodied AI Research[END_REF] (see section 5), receiving images of the environment as observations and predicting actions from a discrete space (forward, turn left 10 • , turn right 10 • ). We propose a hierarchical planner performing actions at two different levels:

A high-level graph based planner that operates on longer time scale τ and iteratively proposes new point-goals nodes p τ g that are predicted, by a Graph Neural Network, to be on the shortest path from the agent to the estimated location of the target image. A local policy that has been trained to navigate to a local point-goal p τ g , which has been provided by the high-level policy. The local policy operates for a maximum of m time-steps, where m is a hyper-parameter, set to 10. The agent has been trained with an additional STOP action, so that it can learn to terminate the local policy in the case that it reaches p τ g in under m steps.

The two planners communicate through estimated locations, the graph planner indicating the next waypoint to the local policy as a location, and the local policy (after termination) providing an estimate of its reached location back to the high-level planner. The planner updates its current node estimate as the nearest neighboring node and planning continues.

High-level planning with uncertain graphs

The objective of the high-level planner is to estimate the shortest path from the current position S∈V in the graph to a terminal node T ∈V, whose identity is estimated as the node whose visual features are closest to the target image in cosine distance. Planning takes into account the distances between nodes encoded in D as well as estimated edge connectivity encoded in E. As an edge (i, j) may have a large connection probability E i,j but still be obstructed in reality, the goal is to learn a trainable planner parameterized by parameters θ, which takes into account visual features V to overcome the uncertainty in the graph connectivity. To this end, we assume the ground truth connectivity E * available during training only. Figure 2 illustrates the different types of solutions this problem admits: the optimal shortest path is only available on ground truth data (Figure 2a), the objective is to use the noisy uncertain graph (Figure 2b) and provide an estimate of the optimal solution taking into account visual features (Figure 2d). This is unlike the optimal solution in a probabilistic sense calculated from a symbolic algorithm (Figure 2c). We propose a trainable planner, which consists of a novel graph neural network architecture with dedicated inductive bias for planning. Akin to graph networks [START_REF] Battaglia | Relational inductive biases, deep learning, and graph networks[END_REF], the node embeddings are updated with messages over the edges, which propagate information over the full graph. While it has been shown that graph networks can be trained to perform planning [START_REF] Xu | What can neural networks reason about?[END_REF], we aim to closely mimic the structure of the Bellman-Ford algorithm and we embue the planner with additional inductive bias and a supervised objective to explicitly learn to calculate shortest paths from data. To this end, each node i of the graph is assigned an embedding x i = [v i , e i , t i , d i , s i ] where v i are visual features from the memory matrix V , t i is a boolean value indicating if the node is the target, e i are the edge connection probabilities from node i to all other nodes, d i are the distances for node i to all other nodes, s i is a one hot vector identifying the node (part of the identity matrix I).

We motivate our proposed neural model with the following objective: the planner should be able to exploit information contained in the graph connectivity, but also in the visual features, to be able to find the shortest path from a given current node to a given target node. As with classical planning algorithms, it will thus eventually be required to keep for each node a latent representation of the bound d i on the shortest distance as well as information on the identity of the outgoing edge to the neighbor lying on the shortest path, the predecessor function Π(i). Known algorithms (Dijstra, Bellman-Ford) perform iterative updates of these variables (d i , Π i ) by comparing them with neighboring nodes and the corresponding inter-node distances, updating the bound d i and Π i when a shorter path is found than the current one. This is usually done by iterating over the successors of a given node i.

In our trained model, these variables are not made explicit, but they are supposed to be learned as a unique vectorial latent representation for each node i in the form of an internal state r i , which generally holds current information on the reasoning of the agent. The input to each iteration of the graph network is, for each node i, the node embedding x i , and the node state r i , which we concatenate to form a single node vector n i :

n i = [x i , r i ] = [v i , e i , t i , d i , s i , r i ]
As classically done in graph neural networks, this representation is updated iteratively by exchanging messages between nodes in the form of trainable functions. The messages and trainable functions of our model are given as follows, illustrated in Figure 3, and will be motivated in detail further below.

m i,j = W 1 [n i , n j ] σ(W 2 [n i , n j ]) (1)
r i = φ r←h ({m i,j } ∀j , h i ) (2)
Here, is the Hadamard product, W . are weight matrices, and r i is the updated latent representation after one round of updates. The features x i do not change during these operations. Equation ( 1) is inspired from gated linear layers [START_REF] Dauphin | Language modeling with gated convolutional networks[END_REF], and enables each node to identify whether it is the target, and update its representation of the bound. We use gated linear layers in order to provide the network with the capacity to update bound estimates for its neighbors.

Equation [START_REF] Åström | Optimal control of markov processes with incomplete state information[END_REF] integrates messages from all neighbors j of node i, updating its latent representation. Since planning requires this step to update internal bounds on shortest paths, akin to shortest path algorithms that rely on dynamic programming, we serialize the updates from different neighbors into a sequence of updates, which allows the network to learn to calculate minimum functions on bound estimates. In particular, we model this through a recurrent network in a Gated Recurrent Unit variant [START_REF] Chung | Empirical evaluation of gated recurrent neural networks on sequence modeling[END_REF], using a hidden state vector h i associated to each node i. The step is structured to mimic the min operation of the Bellman-Ford algorithm (see section 3.2 for details on this equivalence).

Equation (2) can thus be rewritten in more detail as follows: Going sequentially over the different neighbors j of node i, the hidden state h i is updated as follows:

h [j] i = W 3 m i,j + W 4 h [j-1] i (3)
For simplicity, we omitted the gating equations of GRUs and presented a single layer GRU. In practice we include all gating operations and use a stacked GRU with two layers. The output of the recurrent unit is a non-linear function of the last hidden state, providing the new latent value r i :

r i = M LP (h N i ) (4)
where M LP is a two-layer neural network with ReLU activations. The above messages are exchanged and accumulated for k steps where k is a hyper-parameter which should be at least the largest span of the graphs in the dataset. The action distribution f A (r i ) is then estimated for each node in the graph as a linear mapping of the node embeddings followed by a softmax activation function.

A i = f A (r i ) = softmax(W r i ) (5)

Relations to optimal symbolic planners

As mentioned before, our neural planner could in theory be instantiated with a specific set of network parameters such that it corresponds to a known symbolic planner calculating an optimal path in a certain sense. To illustrate the relationship of the network structure, in particular the recurrent nature of the graph updates, we will layout details for the case where the planner performs the estimation of a shortest path given the distance matrix and ignoring the uncertainty information -an adaptation to an optimal planner in the probabilistic sense can be done in a straightforward manner. To avoid misunderstandings, we insist that the reasoning developed in this sub section is for illustration and general understanding of the chosen inductive network bias only, the real network parameters are fully trained with supervised learning as explained in section 4.

Handcrafting a parameterization requires imposing a structure on the node state r i , which otherwise is a learned representation. In our case, the node state will be composed of the bound b i on the shortest path from the given node to the target node (a scalar), and the current estimate Π i of the identity of predecessor node of node i w.r.t. the shortest path, which can be represented as a 1-in-K encoded vector indicating a distribution over nodes.

Standard Bellman-Ford symbolic bound updates iteratively update the bound for a given node i by examining all its neighbors j and checking whether a shorter path can be found passing through neighbor j. This can be written in a sequential form s.t. the bound gets updated iterating through the neighbors j=1. . .J i of node i: b

[0] i = b i b [j] i = min(b [j-1] i , b j + d ij ) b i = b [Ji] i (6)
where b i is the bound before the round of updates for node i, and b i is the bound after the round of updates for node i.

In our neural formulation, the message updates given in equation ( 2), further developed in (3), mimic the Bellman-Ford bound update given in Equations ( 6). This provided motivation for our choice of a recurrent neural network in the graph neural network, as we require the update of the recurrent state h j i in Equation ( 3) to be able to perform a minimum operation and an arg min operation (or differentiable approximations of min and arg min).

Graph creation from explorative rollouts

Graphs were generated during the initial rollout from an exploratory policy trained with Reinforcement Learning. During training, the agent interacts with training environments and receives RGB-D image observations calculated as a projection from the 3D environment. The agent is trained to explore the environment and to maximize coverage, i.e. to visit as much space as possible as quickly as possible similar to [START_REF] Chaplot | Learning to explore using active neural slam[END_REF][START_REF] Chen | Learning exploration policies for navigation[END_REF].

To learn to estimate the graph connectivity, we add an auxiliary loss to the agent's objective function, f link (o i , o j , h i ) which is trained to classify whether two locations are in line of sight of each other, conditioned on the visual features o i , o j from the two locations and the agent's hidden state h i . Node features were calculated with a CNN [START_REF] Lecun | Gradient-Based Learning Applied to Document Recognition[END_REF]. Ground truth line of sight measurements were computed by 2D ray tracing on an occupancy map of each environment. In order to limit the size of the graph to a maximum number of nodes k, we aim to maximize each node's coverage of the environment using a Gaussian kernel function. At each time step a new node is observed by the agent, previous node positions are compared with a Gaussian kernel function (eq. 7) in order to identify the index of the most redundant node r, which is removed from the graph and replaced with the new node, node connectivities are then recomputed with f link (.), where L i is the location of node i.

r = arg min i   j K(L i , L j )   , K(v, v ) = exp( -v -v 2 2σ 2 ), (7)

Training

The high-level graph based planneris trained in a purely supervised way. We generate ground truth labels by running a symbolic algorithm (Dijkstra [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]) on a set of valued ground truth training graphs described with the method detailed in Section 3.3. In particular, the supervised training algorithm takes as input uncertain/noisy graphs, which include visual features, and is supervised to learn to produce paths, which are calculated from known ground truth graphs unavailable during test time. During training we treat path planning as a classification problem where for a given target, each node must learn to predict the subsequent node on the optimal path to the target. Formally for each node i we predict a distribution A i and aim to match a ground-truth distribution A * i , which is a one-hot vector, minimizing cross entropy loss L(A, A * ) = -n i=1 A * i log A i . We augment training with a novel version of mod-drop [START_REF] Neverova | Moddrop: adaptive multi-modal gesture recognition[END_REF], a training algorithm for multi-modal data, which drops modalities probabilistically during training. In our case, during training we extend the node connection probabilities in the input with the ground truth node adjacencies and mask either the probabilities or the adjacencies with a probability of 50%, during training we linearly taper the masking probability from 50% to 100% over the first 250 epochs. This ensures that the final model requires only connection probabilities, but the reasoning performed during message passing and recurrent updates can be bootstrapped from the ground truth adjacency matrix. Training curves on unseen validation data are shown in figure 5b. The local policyis a recurrent version of AtariNet [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] with two output heads for the action distribution and value estimates. The network was trained with a reinforcement learning algorithm Proximal Policy Optimization (PPO) [START_REF] Schulman | Proximal policy optimization algorithms[END_REF] to navigate with discrete actions to a local point-goal. Point-goals were generated to be within 5m of the spawn location of agent. A dense reward was provided that corresponds to a decrease in geodesic distance to the target, a large reward (10.0) was provided when the agent reached the target and the STOP action was used. The episode was terminated when either the STOP action was used or after 500 time-steps. A small negative reward of -0.01 was given at each time-step to encourage the agent to complete the task quickly. The explorative policy for graph creationis trained with PPO [START_REF] Schulman | Proximal policy optimization algorithms[END_REF]. We aim to maximize coverage that is within the field of view of the agent. We create an occupancy grid of the environment with a grid spacing of 10cm. The first time a cell is observed the agent receives a reward of 0.1. A cell is considered to observable if it is free space, within 3m of the agent and in the field of view of the agent. Agent performance is shown in Figure 4b.

Experiments

We evaluated our method in simulated 3D environments, in particular the Habitat [START_REF] Savva | Habitat: A Platform for Embodied AI Research[END_REF] simulator with the visually realistic Gibson dataset [START_REF] Xia | Gibson env: realworld perception for embodied agents[END_REF]. During training, the agent interacts with 72 different training environments from Gibson, where each environment corresponds to a different apartment or house, and receives as input observation an observed RGB-D image. We evaluate our method on a set

Method

Acc H-SPL Symbolic (GT)

1.00 1.00 Neural planner (GT) 0.921 0.983 of 16 held out environments that were unseen during training by either the local policy, the exploratory policy or the high-level neural planner.

High-level graph-based planner

The neural planner was implemented in PyTorch [START_REF] Paszke | Pytorch: An imperative style, high-performance deep learning library[END_REF], the hyper-parameters are given in the supplementary material. We compare two metrics, accuracy of prediction of the next way-point along the optimal path and the SPL metric [START_REF] Anderson | On evaluation of embodied navigation agents[END_REF], both for paths of length two or greater. As we evaluate SPL for both the high level planner and the hierarchical planner-controller, we refer to the high-level planner's SPL as H-SPL to avoid ambiguity. Symbolic baselines -We compare the neural planner to two symbolic baselines, both of which reason on the uncertain graph only, without taking into account rich node features. While these baselines are "optimal" with respect to their respective objective functions, they are optimal with respect to the amount of information available to them, which is uncertain: (i) Thresholding -In order to generate non-probabilistic edge connections, we threshold the connection probabilities with values ranging from 0-1 in steps of 0.1. After threshholding the graph, path planning was performed with Dijkstra's algorithm; (ii) A custom cost function for Dijkstra's algorithm weighting distances and probabilities: We vary the weighting λ in order to control the trade-off of distance and connection probability. In the limit where λ is 0, the graph is a fully connected graph, whereas high values of λ would lead to finding the most probable path. Results of both symbolic baselines for varying hyper-parameters are shown in Figure 4a, we observe that they perform poorly under uncertainty. In both cases we aim to evaluate the accuracy of their predictions with respect to the symbolic baseline on the ground truth graph, i.e. Dijkstra on the shortest path. As graphs can contain many source-target pairs that are within 1 step, we report accuracy on source-target pairs separated by at least 2 steps.

cost(i, j) = D i,j -λ log(E i,j ) (8
Image driven recurrent baseline -We also compare to an end-to-end RL approach where the current observation and target image are provided to a CNN based RL agent trained from reward. The agent architecture is a siamese CNN with a recurrent GRU. We train with a dense reward of improvement in geodesic distance between the agent and the target, and provide a reward of 10 when the agent reaches the goal. We used PPO, and trained for 200 M environment frames.

In Table 1a, we compare the neural planner,the two symbolic baselines and the recurrent baseline. We can see, that even without visual features, the neural planner is able to outperform the "optimal" symbolic baselines. This can be explained with the fact, that the baselines optimize a fixed criterion, whereas the neural planner can learn to exploit patterns in the connection probability matrix E to infer valuable information on shortest ground truth path. The gap further increases when the neural planner can use visual features. The positive impact of modality mixing (see section 4) is shown in Figure 5b.

As a sanity check, table 1b compares the optimal symbolic planner against the neural planner trained with ground truth adjacencies provided as input. We observe that the results of the neural planner are close to optimum in this case.

We evaluated our approach with different amounts of training data, ranging from 8,000 graphs to 74,000 training graphs (Figure 5a). Note that one training graph spawns 32×32 possible source-target combinations, leading to a maximum amount of 75,000,000 training instances.

Hierarchical planning and control (topological & local policy)

We evaluated the neural graph planner coupled with the local policy. For a given episode, the graph planner estimates the next node in the path to a target image and provides its location to the local policy, which executes for m time-steps. The planner then re-plans from the nearest neighbor to the agent's current position, this back and forth process of planning and navigating continues until either the agent reaches the target or 500 low-level time-steps have been conducted. We report accuracy as percentage of runs completed successfully and SPL in table 2, albeit measured on low-level trajectories as opposed to graph space. We combine the local policy with various graph planners, and can see that the neural graph planners greatly outperform the symbolic baselines. We perform two evaluations of the neural planner; a deterministic evaluation where point-goals are chosen with the argmax of the A distribution and a non-deterministic one by sampling from A. The motivation is that by sampling, the planner can escape from local minima and loops created by errors in approximation. This is confirmed when studying rollouts from the agents, and also quantitatively through the performances shown 6, where in step 10 we can see that navigation is robust w.r.t. local errors in planning (the purple line crossing white non-traversable space).

Ablation: Effect of chosen inductive bias

As developed in sections 3.1 and 3.2, our graph based planner includes a particular inductive bias, which allows it to represent the Bellman-Ford algorithm for the calculation of shortest or best paths. This bias is implemented as a recurrent model (a GRU) running sequentially over the message passing procedures, as illustrated in Figure 3. Figure 7 ablates the effect of this additional bias as a function of data sizes ranging from 8,000 to 74,000 example graphs, each one evaluated with 32 2 =1,024 different combinations of starting and end points.

The differences are substantial, and we can see that our model is able to exploit increasing amounts of data and translates them into gains in performance, whereas standard graph convolutional networks don't -we conjecture that they lack in structure allowing them to pick up the required reasoning.

Conclusion

We demonstrated that path planning algorithms can be approximated with learning when structured in a manner that is akin to classical path planning algorithms. We have performed an empirical analysis of the proposed solution in photo-realistic 3D environments and have shown that in uncertain environments graph neural networks can outperform their symbolic counterparts by incorporating rich visual features as part of their planning procedure. Our method can be used to augment a vision based agent with the ability to form long term plans under uncertainty in novel environments, without a priori knowledge of the particular environment. We have analysed the empirical performance of the neural planning algorithm with a variety of dataset sizes, shown that the high-level planner can be coupled with a low-level policy and evaluated the hierarchical performance on an image-goal task. 7 Supplementary material

Fig. 2 :

 2 Fig. 2: Illustration of the different types of solutions to the high-level graph planning problem: (a) the ground truth graph (unavailable during testing) with the shortest path from node S to node T in red; (b) the uncertain graph available during test time. This graph is fully connected and for each edge a connection probability is available. For clarity we here show only edges where the connection probability is above a threshold. The edge from A→B is wrongly estimated as not connected; (c) an "optimal" path taking into account both probabilities and distances; (d) A learned shortest path, where the visual features at node A indicate passage to node B. We supervise a network to predict the GT path (a).

Fig. 3 :

 3 Fig. 3: (a) An example graph; (b) One iteration of the neural graph planner's message passing and bound update. Incoming messages from neighbors are serialized and fed through a recurrent unit, which creates inductive bias for learning minima necessary for bound updates.

Fig. 4 :

 4 Fig. 4: (a) Symbolic baselines Dijkstra on -left: thresholded probs., right: cost function(8). (b) Left: Average return. Right: Accuracy of line of sight predictions.

Fig. 5 :

 5 Fig. 5: (a) Accuracy and H-SPL with increasing size of data when the GNN is trained with and without visual features. (b) Modality mixing (GT connections and probabilities), we observe a 2.3% improvement over single modality training.

Fig. 6 :

 6 Fig. 6: Six time-steps from a rollout of the hierarchical planner (graph+local) in an unseen testing environment. For each time-step: left -RGB-D observation, right -map of the environment (unseen) with graph nodes, source node, target node, agent position(black), nearest neighbour to the agent, local point-goal provided by the high level planner and planned path. Further examples can be found in the supplementary material, including failure cases.

Fig. 7 :

 7 Fig.7: Ablation of the addition of a GRU for the accumulation of incoming messages. This recurrent unit was added to ensure that the model could represent the Bellman-Ford algorithm.

7. 1 Figure 8

 18 Figure8shows example graphs extracted from three different environments extracted with the method described in section 3.3 of the main paper.

Fig. 8 : 7 . 2

 872 Fig. 8: Examples of top down maps and graphs from three environments. For each environment -Top-left: topological map with ground truth connectivities, top-right: topological map with connection probabilities estimated by the learned f link function with line opacity corresponding to the link probability, bottomleft: ground truth shortest path between a source an target node, bottom-right: shortest path estimated by the Graph Neural Planner. Note the very bottom-right prediction connects two nodes that are not connected in the ground truth, this example would not be counted as a valid path during evaluation of the SPL metric.

7. 3

 3 Effect of the length m of the local policyIn figure11of this document we show the effect of the parameter m of the local policy, described in section 3, page 6, of the main document, when evaluated on a limited random subset of the validation data (1,200 problem instances).

Fig. 9 :

 9 Fig. 9: Six time-steps from a rollout of the hierarchical planner (graph+local) in an unseen testing environment. For each time-step: left -RGB-D observation, right -map of the environment (unseen) with graph nodes, source node, target node, agent position(black), nearest neighbour to the agent, local point-goal provided by the high level planner and planned path.

Fig. 10 :

 10 Fig. 10: Failure case -Six time-steps from a rollout of the hierarchical planner (graph+local) in an unseen testing environment. For each time-step: left -RGB-D observation, right -map of the environment (unseen) with graph nodes, source node, target node, agent position(black), nearest neighbour to the agent, local point-goal provided by the high level planner and planned path.

Table 1 :

 1 Reporting H-SPL and accuracy of the neural planner's predictions in unseen environments; neural planner trained with 72,000 graphs

	(a) Results on uncertain graphs	(b) Results on ground truth graphs
	Method	Acc H-SPL
	Symbolic (threshold)	0.114 0.184
	Symbolic (custom cost) 0.115 0.269
	Neural (w/o visual)	0.251 0.468
	Neural (w visual)	0.262 0.501

  )

	0.26		0.500
	0.24		0.475
	0.16 0.18 0.20 0.22 Validation accuracy		0.450 0.375 0.400 0.425 Validation H-SPL
	0.14		0.350
	0.12	10000 20000 30000 40000 50000 60000 70000 Training dataset size Connection probabilities Probabilities and visual features	0.300 0.325	10000 20000 30000 40000 50000 60000 70000 Training dataset size Connection probabilities Probabilities and visual features

Table 2 :

 2 Performance of the hierarchical graph planner & local policy

	Method: Planner + Local policy	Success rate SPL
	Graph oracle (optimal point-goals, not comparable)	0.963	0.882
	Random	0.152	0.111
	Recurrent Image-goal agent	0.548	0.248
	Symbolic (threshold)	0.621	0.527
	Symbolic (custom cost)	0.707	0.585
	Neural planner (sampling)	0.966	0.796
	planner (deterministic)	0.983	0.877
	in table 2. A visualization of steps from an episode is shown in Figure

Acknowledgements -This work was funded by grant Deepvision (ANR-15-CE23-0029, STPGP479356-15), a joint French/Canadian call by ANR & NSERC; Compute was provided by the CNRS/IN2P3 Computing Center (Lyon, France), and by GENCI-IDRIS (Grant 2019-100964).

The m parameter limits the maximum number of steps the local policy can take before giving control back to the high-level graph planner. We recall that the local policy can also decide to terminate the inner loop earlier through an explicit STOP action. We see that performance of the planner and policy is comparable up to 20 time-steps, which means the computationally costly planning step can performed less frequently than the low level control of the local policy, without a reduction in performance.

Hyper-parameters

Table 3 provides the hyper-parameters for the three different neural models used in this work:

the explorative policy used to create the graphs, trained through RL; the graph based high-level planner, trained in a supervised way, and the local policy, trained through RL.