Catherine Taine-Cheikh

Condition, interrogation and exception Remarks on particles in Berber

Comparison of the different Berber dialects (whether they be considered languages, dialects or local varieties) shows that there are a great many shared characteristics, particularly from a typological perspective. The degree of similarity varies however depending on the element studied. Conjunctions have been recognized as one of the least unified of elements: «Le système des conjonctions varie notablement d'un parler ou d'un dialecte (ou langue) à l'autre, ce qui permet de les considérer comme un outillage relativement récent, que chacun des groupes berbérophones a élaboré pour son propre compte. À côté d'éléments berbères, on y reconnaît souvent des emprunts à l'arabe» (Galand 1988: 225). 1 This diversity is indeed found in the inventory of those Berber particles which introduce the protases of hypotheses. However, the number of markers is much lower if one takes into account the probable origin of the basic units these markers are built upon. From this perspective, it is necessary to examine all of these particles' uses and meanings. This examination will focus on observed convergence in order to shed light on grammaticalization pathways.

ad in Zenaga

Zenaga is an endangered Mauritanian language. It is generally classified apart, as a language variety belonging to a distinct linguistic set. In this peripheral variety (located in the south-westernmost part of the Berber area) the uses of ad vary widely, as in other Berber varieties, and show some specificities. For example, Zenaga is the only Berber variety where ad 2 has a fully grammaticalized use as a conditional particle ('if'). The various occurrences of Zenaga ad are examined in Taine-Cheikh 2010a where several possible grammaticalization pathways are laid out, based on uses of ad as a deictic, for instance as a demonstrative and copula. Below is a brief summary of the various uses of ad in Zenaga.

A/ ad is a proximal demonstrative pronoun (M.Sg äḏ vs. F.Sg täḏ vs. M.Pl əḏniḏ), a demonstrative clitic (Sg -äḏ vs. Pl -iḏ) and an invariable copula (with non adjectival nominal predicates). These three possibilities are illustrated in (1):

(1) äḏ / äräbīy=äḏ äḏ änäḫtəf this.one / M.child.SG=this.SG COP M.wary.SG 'This one / this child is wary.' B/ ad is an invariable particle used to introduce independent clauses expressing orders, prohibitions or injunctions C/ ad is an invariable particle used to introduce dependent clauses in second position. The latter may be: i) completive clauses (verb in the aorist) of governing verbs expressing orders, requests or wishes (expressed to others or to oneself) ii) indirect speech (verb in the aorist), e.g. indirect orders, following verbs such as 'say' or 'ask' iii) quotatives (verb in the perfective or imperfective) following the verb 'say'3 iv) indirect polar questions following verbs such as yäžgäDʸäh 'ask, question, interrogate', yuẓẓaˀṛ 'look', wär yəssən 'not know', yäƶnäzgäm 'think, seek to understand'. In the case of indirect questions, äđ must be followed by a verbal auxiliary frozen in the 3rd M.sg person: either yu(u)gä 'become, unfold (time)', or (more rarely) yuṃrä 'already be'.

(2) wär Sən-äg äḏ^ y-u(u)gä y-əššäh^ḏäh NEG know.PFV-1SG if 3M.SG-become.PFV 3M.SG-come.PFV=PROX 'I do not know if he came.'

When the verb in the subordinate clause is in the imperfective -and not in the perfective as in (2)-, it is usually preceded by the future auxiliary yänhäyä (... äḏ^y-u(u)gä y-änhäyä y-əttäššäh^ḏäh '... if he will come'). D/ ad is an invariable particle used to introduce protases of conditional clauses. i) When äḏ is used on its own (+ verb in the aorist, with or without negation) it is used as a conditional (the 'simple' condition which often shows a tendency to conflate with the temporal in 'when, every time that'):

(3) äḏ wär^ y-äšbi y-uḟḟuḏ if NEG 3M.SG-drink.AOR 3M.SG-be.thirsty.AOR 'If (when) he does not drink, he is thirsty.'

ii) When äḏ is followed by the frozen form yu(u)gä, the sentence takes on the meaning of a factual, referential hypothesis, used to express an alternative:

(4) äḏ^ y-u(u)gä y-əšbä wär^ y-uḟḟuḏ if 3M.SG-become.PFV 3M.SG-drink.PFV NEG 3M.SG-be.thirsty.NEG.PFV 'If he drank, he is not thirsty.' [but if he did not drink, he is thirsty] Within the irrealis system, one thus sees that äḏ covers a wide array of uses, where only counter-factual hypotheses are impossible (the particle (h)äm is used instead).

Similar to the äḏ used to introduce injunctions, prohibitions, wishes, requests, or even simply speech, the äḏ used in conditionals probably stems from a deictic (in a broad sense). Moreover, the äḏ used in protases can be more specifically used as an actualizer, where the clause is used to express fictional actualization (setting the clause in the referential sphere of all possible worlds). 4 From that perspective, the conditional äḏ may be more closely linked to injunctive äḏ and polar question äḏ. This possibility of a tighter link between conditions and questions has only one visible manifestation in Zenaga, which is the widespread -and highly specific-use of the frozen verb form y-u(u)gä. In other Berber varieties certain factors seem to indicate that the systems are evolving in similar ways.

is in Tamazight and Tashlhit

Tamazight5 and Tashlhit refer to two large dialect areas in central and southern Morocco, corresponding, respectively, to the Middle-Atlas and to Soûs. The particle ad is found there, but the invariable morpheme is is used in a great variety of contexts, for example in questions and, to a more limited extent, in conditionals.

A/ is is regularly described as being used to introduce independent or content questions. In this use, is is never mandatory («Une intonation montante suffit à donner à l'énoncé chleuh une valeur interrogative» Galand 1988: 222), 6 but its presence does trigger affix displacement (such as the pronominal or adverbial -t in (6), used for spatial orientation). 7 In Tashlhit:

(5

) is i-Ša u-srdun? Q 3M.SG-eat.PFV M.AS-mule.SG
'Did the mule eat?' (Galand 1988: 222) 'Did he come yesterday?' (Penchoen 1973a: 82).

B/ In contrast, is is obligatory when it introduces an indirect question. Example (11) shows that these two uses of is (as a direct and an indirect question marker) can coexist in a single sentence.

Tashlhit (Destaing 1920: 261) (9) i-seqsa t is i-herš These examples show that ini 'say' takes on the meaning of 'think' when it is followed by is, whereas isin 'know' retains its full verb meaning with is but takes on modal ability meaning when the construction contains the particle ad.

For Galand, the is, in ( 19) and (20), is not a true subordinator, but is rather a particle made up of the determiner prop i and the preposition s.9 Thus the original construction would be better rendered by the explanatory phrase 'it is that'. 'As for me, I have not seen anything.' E/ Lastly, the particle is is also found in hypotheses. i) is is used relatively rarely as a conditional particle, nonetheless the Tamazight Dictionnaire (Taifi 1991: 607) In contrast, Bentolila (1981: 310) considers that in Aït Seghrouchen Tamazight, hypothetical meaning is rendered through inversion (like in the two verses of La Fontaine's fable: 'Se mire-t-on près d'un rivage / Ce n'est pas soi qu'on voit'). In ( 25), the initial is indeed appears to function in the same way as the interrogative adverb is: 'Is the weather beautiful? Women are taking the timshins 10 from the tent.' Therefore the grammaticalization of is as a conditional marker appears limited, even within Tamazight. 11 However, given that the difference in analysis for ( 24) and ( 25) is mostly due to the difference in intonation, it is easy to see how the language may have gone from free association between two independent clauses to a single sentence with two linked clauses. ii) In Tuareg, the particle as, for which the etymology and usage in relatives are comparable to that of is, has undergone specific changes in the southern varieties. In these varieties it is used both as a complementizer (following verbs such as issân 'know') and as an adverbial subordinator. The particle, which literally means 'the situation entailing (such and such a thing)' can, in certain contexts, take on temporal meaning ('when'), causal meaning ('given that'), or hypothetical meaning ('if'). The various stages in this grammaticalization process are well documented in Galand (2002Galand ( [1987]]). Although these uses are quite different from what one finds for is, it is interesting to note that in 10 timŠin was not translated by Bentolila, but this lexeme is comparable to timšušin, the plural of tamšušt which Taifi (ibid.: 438) translates as 'old threadbare mat '. 11 In Ighchan Tashlhit, the conditional particle is iġ 'if, when' (virtual). The origins of this particle are similar to those of is: see i s 'the one with' and i ġ 'the one in ' (cf. Galand 1988:226). There is also mtaD is 'if' (irrealis), but in this case the presence of is probably denotes a lesser degree of specificity than mta(D).

(25) is i-La u-ẓġal, La TKs-n-t Q 3M.SG-
Tamasheq of North-East Burkina Faso, «[t]he conjunction as is frequently used to express 'if' or 'when'» (Sudlow 2011: 95). For example as in ( 26):

(26) as ǎmtǎll-ǎġ səsseġədǎd=ahi if make.a.mistake.PRV-1SG correct.IMP.SG=PR.OBJ.1SG

'If I make a mistake, correct me.' F/ In Tamazight and Tashlhit, exceptions are often expressed by the prepositions ġār and/or (a)bla (cf. [START_REF] Destaing | Etude sur la Tachelḥît du Soûs. I Vocabulaire français-berbère[END_REF]: 256, Bentolila 1981: 217, Taifi 1991: 17). These originally Arabic particles clearly show no relation to is/as. On the contrary, the Zenaga preposition äš 'with the exception of, except' [START_REF] Taine-Cheikh | Dictionnaire Zénaga -Français. Le berbère de Mauritanie par racines dans une perspective comparative[END_REF]: 470, 2011: 546) is akin to is/as. The difference in frication is simply the regular reflex of the change s>š (which is why in Zenaga the complementizer for example is äyš and not is/as). In support of this posited kinship is Bentolila's study of oaths (1988). He shows that the particles which appear in the positive real verb phrases of oaths often had the original meaning 'only'. This is true not only of abla and (a)ġar/ġir, but also of has and ḫs, particles ending in -s found in central Morocco, amongst, respectively, the Zemmours and the Aït Sadden 64). In Zenaga, one finds a particle āš (which is different from but similar to the exception particle äš) used in a positive oath concerning a future event (Taine-Cheikh 2010b: 202-3). Its close correspondence to central Moroccan has strengthens the kinship hypothesis between the various s/š particles. In this context, a relation between the above mentioned particles is/as and the restrictive particles becomes entirely plausible.

m(a) in the northern varieties

Chamito-Semitic shows a varied use of particles built upon the basic element m-12 -e.g. in interrogatives and indefinites. This phenomenon is also found in Berber, particularly in interrogative pronouns ('who?', 'what?') and adverbial ones ('where?', 'when?', 'how?', 'why?'), with a tendency to spread to conditional particles in certain varieties.

The polyfunctional ma

It is in the northern varieties, especially in Morocco and Algeria, that the uses of the invariable particle ma have diversified the most. It is not uncommon that it be used to introduce both interrogatives (direct and indirect) and the protasis of conditionals.

A/ ma is an interrogative adverb, it is sometimes in competition with is, but is more widely found outside of Tashlhit and Tamazight. i) Above (in 2.A), we did not provide any examples of is as an interrogative adverb in Aït Seghrouchen Tamazight. This is not because is never has the meaning of an interrogative in this variety, but rather because, strictly speaking, the interrogative adverb is not is, but ma. 13 Only ma can introduce polar questions, to which a yes/no answer is possible, as in ( 28):

(28) ma d ˤli?

Q PRED Ali 'Is it Ali (or not)?'

ii) Map 292 of the Atlas des variétés berbères du Rif (Lafkioui 2007: 240) shows that the interrogative ma is found in a great many varieties (both eastern and central). In eastern Rifain, Kossmann (2000: 179) notes that it is more common to use ma than to use only intonation:

(29) ma ṯ-əlli-ḏ mliḥ?

Q 2-be.IPRV-SG well 'Are you well?'

iii) The interrogative ma is also used in Aures Chaouia:

( 'Is the matter solved?' (Dallet 1982: 475) 13 Bentolila (1981: 188-9) specifies on the one hand that one does find the combination ma-is (only in that order) and, on the other hand, that with is, it is a simple request for confirmation, as in ( 27), where the primary meaning of 'is it that...' can still be clearly felt.

(27) iz d ˤli?

'is it really Ali?' B/ The use of ma for indirect polar questions is found in the same varieties (with the apparent exception of Tamazight). i) In eastern Rifain (Kossmann,ibid.: 180) Furthermore, it must be noted that one also finds longer forms in Kabyle: ma d ay and ma d ara (Naït-Zerrad, ibid.: 145).

m(a) derivatives

Chaouia very clearly shows the three cumulative uses of ma (direct and indirect questions + condition), as does Kabyle, to a lesser degree. This is less the case in other varieties where the particle ma often needs additional material to be used as a conditional. Moreover, it is important to note that many varieties only use the element m(a) as a constitutive part of larger pronominal, adverbial or conjunctive units. In the case of conditional particles, it can be very difficult to identify the origin of all of the elements, but the presence of m(a) is as recurrent in conditionals as it is in units with interrogative meaning.

A/ mer and its variants In Berber, for irrealis hypotheses, specific particles are used, e.g. mer/mur/mr in Tamazight and mer/mmer/lemmer in Kabyle. The fact that they are usually followed by the negative perfective strengthens Taifi's proposed etymology (1991: 426;1993:218-9) which posits that in m(e)r/mur one can detect the presence of the negation ur/wr. 15B/ mata, mala, mara and their variants Generally speaking, variation consists in the presence or not of a vowel following the nasal m-, and possible gemination of the second consonant. In some dialect areas, the second consonant varies but the overall pattern appears invariable (this is said to be the case in Soûs, where one finds mla, mra, mta 'if'). In other areas, e.g. in the Rif, the pattern shows variation, but the second consonant is usually a liquid: mala, malla, may, mara (Lafkioui 2007: 230). 16 Lastly, in certain cases, the dental variant is dominant: mta/metta in Figuig,17 matta (or batta) in Ouargla. Furthermore, it is probably necessary to consider that there are at least two distinct formations. Even though in Ouargla the conditional particle matta does not require verb satellite displacement, in contrast to the indefinite matta (Delheure 1987: 200), etymological kinship is not impossible. As for the liquid consonant particles, their origin could be «la particule ma suivie de la forme verbale yəlla 'il est'»,18 as suggested by Kossmann (2000: 199) for eastern Rifain, where the variant mayəlla coexists alongside malla.

C/ maka and its variants will be studied in the next section of this paper.

Variants to the element k(a)

In many ways, the element k(a) appears to be a variant of m(a) (and even sometimes of is), even though, within the conditional system, it mostly appears as a second element added to m(a), as in maka.

Like m(a), k(a) is an element found in Semitic with negative and interrogative meaning (see Faber 1991: 414). 19 In Berber, k(a) may either be used on its own, or may constitute part of various particles, often with interrogative meaning. A/ The use of ka in polar questions is rare but not unknown: it is found in western Rifain even though most of that dialect area uses ma (Lafkioui 2007: 237;240, map 292). In Figuig, the particle waš serves to introduce direct questions. It is also used for indirect questions governed by certain verbs: t-eqqel waš... 'she was looking to see whether...' (Kossmann 1997: 322). If one allows that waš can be segmented into two elements, wa-20 and -š, the second element could be analyzed as a representative of k(a). This would be further proof of this particle's wide array of uses. In Zenaga, the element k appears in the global formulaic question: 21 käyḏ? taˀK-äyḏ? 'what is/what did?', where one recognizes the interrogative taˀK 'what?' followed by the demonstrative äyḏ (Taine-Cheikh 2008: 293). Also in Zenaga, the element k appears in the reinforcing discourse marker äk/äK (one must note in this case however the presence of the initial vowel ä-):

(39) niˀK äk aḍmā-g äyš ...

I indeed think.PRV-1SG

COMP 'As for me, I think that...'

In Ouargla one finds uses comparable to those of Zenaga äk(k) and more particularly to those of Tamazight is. Delheure (ibid.:137,182) indicates that in Ouargla there are two particles which can be used with the 19 For Lipiński (ibid.: 483), ka-is first and foremost a «deictic and asseverative particle». 20 One should note that Figuig wa, which is a component element of wala 'even..., ...as well', is also a shortened form, as is la (Kossmann 1997: 344-5).

21 In this case it is often preceded by the element taˀ which raises the question of whether this dental consonant element is akin to Figuig and Ouargla (ma)ta.

presentative meaning 'as for X': both akk and amm w a. 22 B/ Parallel to these uses which tend to serve to structure information and for modality, the element k-also serves as a component in indefinites having the meaning 'each' (e.g. Tuareg ak and Zenaga äkki) or 'every' (e.g. Kabyle ak w ). When coupled with the particle m(a)-, 23 it provides various expressions. They can be interrogative as in the Tahaggart pronoun maněkk 'what [is]?' or manner phrases as in the Tawəlləmət lexeme əmmək 'manner of being, nature...'. They can also be both at once, as in the adverb 'how?' which is expressed by amek in Kabyle, mək/amək/mam(ə)k in Ouargla, maka/maša in Tamazight and maneš in Figuig. 24 C/ It is another coupling between m(a) + k(a) which serves as the conditional particle in the various Berber varieties. Although the apodosis particles seem to be akin to the others, 25 the forms remain distinct: voicing and/or a more marked tendency to palatalize k (>š) locally create this difference. In Tamazight for example, the potential and realizable hypothetical particle is mek and more crucially meš (Bentolila ibid.: 318-9, Taifi 1991: 414) -a form which is both similar to and distinct from ma 'is it that?' and maka/maša 'how?'. 26 Inversely, in Ouargla, the reduced vowel form mək means 'how?' while the form containing the vocalism -a-a has the meaning 'if, in the case that' (Delheure ibid.: 187):

(40) maka d nətta, ụhụ if PRED him no
'If it is him, I refuse (no).'

We will return shortly to a possible etymology for makan, the second variant found in Ouargla, even if the origin of kagella 'if', to which we shall now turn, appears highly similar to that of makan. kagella is a variant of kan noted (along with ouilla) by Laoust (1912: 77) in the Algerian Chenoua variety. It could be composed along the same lines as mayəlla and essentially only differ in its replacement (before the existence 22 amm w a is considered a borrowing from Arabic, but this does not exclude parallel developments. Cf. the presence of amma in western Rifain (Kossmann 2000: 170) and more importantly of uma in Tamazight (Taifi ibid.: 398). 23 This can however also be the case for the indefinite, cf. makk (ma akk 'that which all') 'each' in Ouargla (Delheure,ibid.: 137).

24 Cf. Foucauld 1951-1952: 1163, Prasse & al. 2003: 533, Dallet 1982: 494, Delheure 1987: 187, Taifi 1991: 414, Kossmann 1997: 204. 25 See Lipiński (ibid.: 548), contra Taifi (1993: 219). For the latter, the š in Tamazight meš is the truncated form of ka / ša which means 'thing, something' and which stems from kra, the form used with the same meaning in Tashlhit and Kabyle. The hypothesis is interesting, but could be due to coincidence (the evolution from kra to ka/ša being triggered through influence from the original particle k-). Indeed, in Ouargla, for example, 'if' is expressed by maka, and the lexeme 'thing' šra has indeed retained its r (Delheure ibid.: 324-5).

26 maka/maša is also used in Tamazight with the meaning 'but, however' -as is maša in Rifain (Kossmann 2000: 194).

verb yəlla) of ma by ka.

Based on this hypothesis, let us now consider the case of the preposition ġayr/ġir 'except'. This preposition is a borrowing from Arabic, and can be used as a preposition, as in Ouargli (ibid.: 249). In Chenoua, in contrast, the exception particle is ġerka 'only if' (ibid.: 78):

(41) hezḏa ġerka sen-aṯ n tsebbaṯ 3F.SG.crush.PRV only two-F of F.AS.grain.PL 'She crushed only two grains.'

In Chenoua, the recurrence of the element ka thus seems to establish a particular link between conditional and exception particles.27

- + + - - - maka... + - - + - + kagella + - - - - -

kan in the eastern varieties

In Berber, and more particularly in the eastern varieties, kan/kān is often used as an introductory particle -for, among other uses, the conditional.

Originally it was the Arabic existence verb kān(a) which, in the various Arabic dialects, has been grammaticalized with different uses, and became an invariable form (cf. Taine-Cheikh 2014). A/ In Arabic, ka(a)n is very commonly found introducing the protasis of conditionals, either alone or in more complex units (lukān, in kān...). The same is true in Berber. i) The phrase in kān is close to the canonic Arabic form where the particle (ˀ)in, of deictic origin, is followed by the verb kān(a) in the perfective (always frozen in Berber). The use of in before kān is rare however, and the only other trace of it we were able to find was in the Libyan Sokna variety [START_REF] Sarnelli | Il dialecto berbero di Sokna[END_REF]). 28ii) The phrase lu(u)ka(a)n (composed of kān preceded by a presentative particle) is also borrowed, more or less as such, from the Arabic. 29 It is found in Kabyle (where it is in competition with limmer), in the Algerian Chenoua variety (for past irrealis) and as far away as in Rifain, in the abbreviated form luk. It most often occurs however in Libyan varieties. In the Nefousa variety, the variant lūkân coexists alongside others, with closely related origins and etymologies: liākân, liâ, ídā kān (Béguinot 1931: 94, 127). 30 In contrast, in the Augila variety, luka(a)n is the only conditional particle of Arabic origins -the others being endu/úndu and amur (Paradisi 1960: 174). In Zuara, the l in lukan can be omitted (Mitchell 2009: 112) 'If it is about studying, he studies with him.' iv) Lastly, as in a certain number of Arabic dialects, one finds uses of ka(a)n on its own. This is the case in El-Foqāha, in the Fezzan region (Paradisi 1963: 121). It is also the case in Siwa Oasis Egyptian (Laoust 1931: 137) 'If you do not want to come with me, I will go alone.' B/ ka(a)n (or one of its variants: la-kân, ləkkān, (yä)kûn...) is used at times in Arabic, to express exceptions or restrictions. It is quite frequently found in the Maghreb, particularly in the eastern varieties -from western Algeria to Libya. In Berber, a comparable use of kan 'except, only' has sometimes been noted in this same eastern region. 31 For the Tunisian Sened variety, Provotelle (1911: 114) C/ In Arabic, the particle which introduces direct questions is often also used to introduce conditionals: iḏa, (ˀ)in, (ˀ)in ka(a)n, more rarely kān alone, contrary to (a)kān in the Sudanese Šukriyya variety, and to (yä)kān in Mauritanian ḥassāniyya. In Berber, it would seem that Siwi -a variety under strong Arabic influence -is alone in using the particle kan in this same context (Laoust 1931: 137)

kud and its variants in the southern central area

The different varieties in the Tuareg area are characterized, like Libyan Ghadamès Berber, by the use of a particle based on ku-. This particle, which shows a certain degree of regional variation, is partially used in free variants (kud/kūd/nkūd/kud-ənta/kunta). In substance, it has comparable uses to those discussed above. A/ In its most frequent use, kud introduces the first clause in complex sentences. kud can be used as a temporal subordinator, possibly with causal connotations, as in the Ghadamsi example in (47) (Lanfry 1973: 242) According to this hypothesis, the etymology of ku(d) would be akin to that of kān: the same Arabic root KWN, but a form derived from a noun phrase rather than from a verb form. 33 In Ghadamès, the initial nasal consonant in nkūd, a variant of kūd, does not a priori bear any relation to the n in (i)inkan, unless one imagines a mixed form reflecting dual origins (li-kawni-hi on one hand, (ˀ)in-kān(a) on the other). Be that as it may, the particle regularly introduces conditional protases, 34 as can be seen in the following example (Lanfry ibid 'if (when) the elder entered the room...'

In Tuareg, kud is the most frequently occurring form. However, in Tahaggart, one also finds ku and kudit (Foucauld 1951(Foucauld -1952: 742) : 742) and, further to the south-west, a suffixed variant -nta: kunta in the Tadraq of Kidal and kud-ənta in the Tamaghit of Oudalan (Sudlow 2011: 356). B/ The above-studied element k(a) is not entirely unknown in southern Berber. In Ghadamsi, ak has supplanted wel as a negation particle in independent or main verb clauses (Lanfry ibid.: 143,388). In 32 kud very probably derives from the Maghrebin kūn, kū 'given that, since, because' from the Classical Arabic kawn 'existence, event, incident' (li-kawni-hi 'because he' etc.). kūn is often shortened to kū which may have been borrowed by Tuareg and expanded into əd ('in the incident that'). 33 In Maghreb Arabic, kwn means 'action of being, existing, such or such a state'; 'because, given that, because'; lkwnh kbīr 'because he was big' (Beaussier 1958: 886). 34 Lanfry (ibid.: 180-1, n° 0893) also translates the particle (i)lām by 'if', however this particle, the etymology of which is highly mysterious (could there be some relation to the two particles l-and m-?), appears in a specific structure, of a correlative type: (i)lām... (i)lām... Tuareg, it is less a negation particle, except perhaps in kala 'no' (Motylinski 1908: 51) than one of interrogation, as well as, more originally, one of insistence. 35 In Mali Tamashek for example, ák is one of the «[c]lause-initial particles for polar (i.e. 'yes-no') interrogatives» (Heath 2005: 649). 36 It is possible that the existence of this element k(a) or ak played a role in the morphogenesis of the indirect question particle. Whatever the possible effect, this particle's form is currently identical to that of the conditional, namely kud or one of its variants. In Ghadamès, one finds examples of dependent interrogatives following verbs such as elləm 'look' or essən 'know', illustrated in (51) ( C/ In Ghadamès, exceptions are expressed using ḫalef 'except' (Lanfry ibid.: 137 number 0661). In Tuareg, they are often expressed using (a)sel/(a)selid or using ar, a particle which probably shares its origins with the preposition 'until' (pronounced ar or har depending on the dialect, cf. Heath 2005: 618). 38 However, with the meaning 'except if, unless, only if', Tuareg also uses expressions where one recognizes the particle kud: «Une forme plus pleine se trouve dans la préposition/conjonction kundăba 'si ce n'est, excepté; à moins que' = kudăba = kud-ba-t» (Prasse 2005: 169). 39 (53) is an example of kundəba in Aïr Tuareg (Kossmann 2011: 172):

35 This is true for the particle ak 'there, then' which, in Niger, is frequently suffixed to the personal pronouns in the 2nd person (Prasse & al. 2003: 351). 36 ák also has wider uses as an «appetizer» (Heath ibid.) «in clause-initial position before a topicalized NP, followed by a WH-interrogative» but «it can be glossed contextually as 'or rather', introducing a self-correction». 37 has developed bleached meanings and has become the dependent question marker 38 About mäššär 'except' in Zenaga and its possible link with ār, cf. Taine-Cheikh 2011: 546-7. 39 a fuller form can be found in the preposition/conjunction kundăba 'if not, excepted, unless' = kudăba = kud-ba-t 'It is only if you give me an underskirt that I will descend.'

The fact that the Tuareg exception particle also shows a certain amount of convergence with the conditional and indirect question particles indicates that the previously observed similarities are not due simply to homonymy. The study of the particles used in Berber to express conditions shows that there are true convergences, albeit with some variation. These convergences have a spatial dimension: five regions each show a preference for one of the variants (or group of variants): ad in Mauritania, is in southern Morocco, ma, (a)k/ka and maka in the northern dialects (in Morocco and Algeria), kan in the eastern dialects and lastly kud in the southern dialects. This highlights how innovations tend to spread from one group of speakers to another, in keeping with the wave propagation model.

Convergences are also to be found in the meanings of the particles. Particles which serve to introduce the protasis of a conditional are often more or less closely linked to, on one hand, those which (directly or indirectly) introduce interrogative clauses and, on the other hand, those used to express exceptions. 40Table 1 summarizes these results in a simplified manner (all variants are not noted, e.g. complex particles such as in kan or lukan). The other uses of these same particles are listed on lines 6 to 9.

found in some Arabic varieties, belong at least in part to the domain of borrowings.

Specific abbreviations

Table 1 .

 1 The particle ad in Zenaga

		condi-tional	indirect question	deictic/pre-sentative	comple-mentizeur	injonction /wish
	ad	+	+	+	+	+
	ad^ y-u(u)gä	+	+	-	-	-

  provides several examples.

	(24) is	t-ri-d	ad^ t-eddu-d	ġer	ssuq,
	if	2-want.PRV-SG	POT=2-go.AOR-SG	to	M.souk.SG
	kker		zikk
	get.up.IMP.SG	early

'If you want to go to the souk, get up early.'

Table 2 .

 2 Particles with -s/-š in Berber

		condi-tional	direct & indirect question	excep-tion	deictic/ presen-tative	comple-mentizeur	temporal subor-dinator
	is Maroc	(+)	+	-	+	+	-
	as touareg	+	-	+	-	+	+
	äš zénaga	-	-	+	-	-	-

  In some of these same varieties, the particle ma may be used to introduce the protasis in conditionals. i) In Aures Chaouia, where ma 'if' and ma 'what' are homonymous with the negative particle ma:

					:
	(33) ˤəbbəṛ	ma	a	lam=d=y-as
	measure.IMP.SG	if	POT	PR.OBL.2F.SG=PROX=3M.SG-go.AOR
	'See if it fits you!'
	ii) In Aures Chaouia (Penchoen, ibid.: 54):
	(34) t-raˤa		ma		dag=š
	3F.SG-look.PRV	if		in=PR.3SG
	ša		n Y =ḥ.braṛ
	something	of=lumps
	'She checks if it (the milk) contains lumps.'
	iii) In the Algerian Chenoua dialect (Cherchell region)
	(35) k'abel	ma	tsaġ-en 14
	look.IMP.SG	if	IPRV.rain-3PL
	'Check if it rains.' (Laoust 1912: 77)
	iv) In Kabyle:
	(36) Ur ẓri-ġ		ara	ma	ad	y-eddu
	NEG	know.NEG.PRV-1SG	NEG.2	if
	(37) ma=u=ġar=s.n=š		labas	n y =surḍggn
	if= NEG=to=PR.3PL=NEG2	much	of=M.AS.money.PL
	(38) ma y-ehwa=yak		ḫas	at=t-eġṛeḍ
	if	3M.SG-like.PRV=PR.OBJ.2SG	only	POT=2-read.AOR.SG

POT 3M.SG-come.AOR 'I do not know if he will come.' (Naït-Zerrad 2001: 147) C/ 'If they do not have much money [...]'

(Penchoen, ibid.: 55)

ii) In Kabyle where, on its own, ma can take on the meaning 'if' when it is followed by the perfective, as in (38):

'If you like it, you can read it.'

(Dallet, ibid.: 476)

Table 3 .

 3 Particles with m-in Berber

		conditional	direct question	indirect question
	ma	+	+	+
	m(e)r, m(a)ta, m(a)la...	+	-	-

Table 4 .

 4 Particles with k (or k>š) in Berber

		condi-tional	direct question	indirect question	excep-tion	deictic/ presen-tative	indefinite /interro-gative
	(a)k/ka	-	+	-	+	+	+
	waš

  considers ġir and kän equivalents: [...] ġir idjet/kän idjet '[...] except only one'. In Zuara, kan on its own is noted by Mitchell (ibid.: 108):

	(45) ´əddwa	w=əttitš-´ən=ti	kan
	medicines	NEG=give.NEG.IPRV-3PL=PR.OBJ.3M.SG	except
	i=ṃaṃṃu	d=ṃáḍun
	to=someone	PRED=sick.man
	'They only give medicines (lit. medicines they give them only) to
	someone who is ill', i.e. 'only the sick man takes medicines'.

Table 5 .

 5 The particle kan in Berber

		:
	(46) la	ssen-aġ	kan g	us=əd
	NEG	know.PRV-1SG	if	POT	[3M.SG].come.PRV=PROX
	'I do not know if he will come.'
		conditional		indirect question	exception	existence verb
	kan	+		+		+	+

  kud provient très probablement de la conj[onction] maghrébine kūn, kū 'vu que, parce que, puisque; car' qui provient du classique kawn 'existence; événement, incident' (li-kawni-hi 'parce qu'il' etc.). kūn s'abrège souvent en kū qui a pu être emprunté par le touareg et élargi de əd ('dans l'incident que').» 32

	(48) kud	i-Tḥasab,		i-TrTab
	while	3M.SG.count.IPRV	3M.SG-set.the.amount.of.tax.IPRV
	'While counting (cattle livestock), he sets the amount of tax.'
	(49) kud	i-Tġar,		Tġaṛ-n-t
	as	3M.SG-dry.IPRV	dry.IPRV-3PL-F
	'As (the snail) dried, (the warts) dried (also).'
	However, it is only in the southern central area that ku-and its variants
	have specialized as conditional particles. For Prasse (2005: 169), the
	particle kud, kudet 'if' which introduces the potential conditional stems
	from Arabic:
				:
	(47) nkūd	ferren-n-et	aneˤ	əẓẓed-n-et,
	if	riddle.IPRV-3PL-F	or	grind.IPRV-3PL-F
	'While they riddled and ground (grain)...'
	This use is also found in Tamazight, where kud (or kkud, cf. Taifi 1991:
	322), has also been noted with the meaning 'at the same time as, as long
	as' (Bentolila ibid.: 335):

«

Table 6 .

 6 The particle kud/nkūd in Berber

	conditional	indirect question	exception	temporal subordinator
	kud/nkūd...	+	+	+	+
	CONCLUSION

The conjunction system varies noticeably from one local variant or dialect (or language) to the next. This indicates that they are a relatively recent tool, which each of the Berber speaking groups created independently. Alongside Berber elements, one often finds borrowings from Arabic.

/ad/ is generally pronounced[aeđ], with an interdental consonant, hence its transcription äḏ. Furthermore, for simplicity's sake, assimilations are generally not transcribed (only marked by ^).

This use of ad is only found in Zenaga (as is the case for the two following uses).

The set protasis-apodosis then functions as a pairing of the type topic-commentary (cf. Taine-Cheikh 2011: 390-393).

The term Tamazight is used here in its narrow sense.

For further information on the origins and explanatory values of is, see the article byGaland (2002Galand ( [1987]]: 241-256), and more particularly pages 249-253.

For Semitic, see[START_REF] Faber | The Diachronic Relationship between Negative and Interrogative Markers in Semitic[END_REF] andLipiński (2001: 336-8, 467, 480, 546).

tsaġen [implied ouaman] 'it is raining' -literally 'get caught [waters]', cf. Laoust ibid.: 138.

Its use for the potential, as in Kabyle (cf.Dallet, ibid.: 511), thus appears to be a secondary expansion.

See also mala in the Beni-Salah dialect, spoken on the slopes of the Blida Atlas, not far from Algiers(Laoust 1912:77).

It is important to note that in Figuig m(et)ta is also used to link an operant verb to the following clause if that clause expresses doubt or uncertainty(Kossmann 1997: 322).

the particle ma followed by the verb form yəlla 'it is'.

This same element appears to be present (in the form ka>ša) in ḥaša 'except' in Kabyle(Dallet ibid.: 302). One also finds mak d (d being the predicative) 'nothing but, only that' in Ouargla(Delheure ibid.: 187).

For example p. 33, § III, ln 12.

On this particle in Semitic, see namely. Furthermore, this raises the question whether the particle l-, which one finds for example in Kabyle in limmer, is not its Berber equivalent.

An older document provided a more Berber form: ma 'si'(Motylinski 1898: 36).

It has also been noted in Kabyle (Mettouchi, personal communication).

These polygrammaticalizations are comparable to those of the French si ('if').

In the World Lexicon of Grammaticalization, the conditional is only listed as a source of grammaticalization for the concessive. However, Heine and Kuteva note four possible sources for the conditional (2002: 329): «conditional < (1) copula (2) s-question [marker of polar (yes-no) questions] (3) say (4) temporal».

If one adopts these hypotheses, Berber shows three of the four sources:

(1) ad and is;

(2) (a)k and ma; (4) kud. The case of kan does not fit this framework, but could be explained by the deletion, preceding the existence verb, of the particle (ˀ)in, of deictic origins.

Looking at the table, one sees another trait shared by ad and is/as: that of being used both to introduce the protasis of conditionals and as a complementizer. 41 However, ad and is/as are not radically different from the other particles: they all appear to have originally been used more for discursive purposes than for morphosyntactic ones. This is well illustrated by the marker is, which continues to be optional in direct questions, although it is not alone in this. 42 Originally, the primary role of particles was to introduce an element or clause, to question or on the contrary reaffirm its reality (even when only in a fictive mode). Thus grammaticalization affected specific linguistic tools such as demonstratives, presentatives, topicalizing and focalizing particles, and existence verbs. 43 There is no single grammaticalization path, but rather several, partially parallel, paths (leading, in several cases, to morphemes with mixed origins). Among the chosen grammaticalization paths, some are highly frequent crosslinguistically. Others, more rare,


Rabbia Asghar

Lukas Rummelhard

Anne Spalanzani

Christian Laugier

Allo-centric Occupancy Grid Prediction for Urban Traffic Scene Using Video Prediction Networks

Keywords: Scene Prediction, Deep Learning, Autonomous Vehicles

Prediction of dynamic environment is crucial to safe navigation of an autonomous vehicle. Urban traffic scenes are particularly challenging to forecast due to complex interactions between various dynamic agents, such as vehicles and vulnerable road users. Previous approaches have used egocentric occupancy grid maps to represent and predict dynamic environments. However, these predictions suffer from blurriness, loss of scene structure at turns, and vanishing of agents over longer prediction horizon. In this work, we propose a novel framework to make long-term predictions by representing the traffic scene in a fixed frame, referred as allo-centric occupancy grid. This allows for the static scene to remain fixed and to represent motion of the ego-vehicle on the grid like other agents'. We study the allo-centric grid prediction with different video prediction networks and validate the approach on the real-world Nuscenes dataset. The results demonstrate that the allo-centric grid representation significantly improves scene prediction, in comparison to the conventional ego-centric grid approach.

I. INTRODUCTION

Prediction of traffic scene evolution is essential to an autonomous vehicle for planning as well as detecting dangerous situations. In urban traffic scenarios, the vehicles not only interact with other vehicles, but also share space with vulnerable road users such as pedestrians and cyclists. Key challenges involve the uncertainty and multi-modality of the behaviour of agents in the environment, and complex multiagents interactions [START_REF] Mozaffari | Deep learning-based vehicle behavior prediction for autonomous driving applications: A review[END_REF]. While human drivers show superior ability to forecast the agents' behaviour and interactions in such traffic scenes, it remains a challenge for autonomous vehicles.

Data-driven methods provide powerful tools to solve prediction problems, particularly dealing with complex social interactions [START_REF] Alahi | Social lstm: Human trajectory prediction in crowded spaces[END_REF]. Most conventional approaches are object or agent-based and rely on heavily pre-processed data [START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF], [START_REF] Ettinger | Large scale interactive motion forecasting for autonomous driving: The waymo open motion dataset[END_REF]. Dynamic Occupancy Grip Maps (DOGMs), on the other hand, allow for end-to-end learning due to their discretized spatial representation, without higher-level segmentation [START_REF] Nègre | Hybrid sampling bayesian occupancy filter[END_REF]. Additionally, DOGMs are versatile in terms of sensor dependency, and can be generated from a variety of raw sensor data, such as Lidar or camera images. In our work, we use Bayesian-filter-based DOGM [START_REF] Rummelhard | Conditional monte carlo dense occupancy tracker[END_REF] that provide us with a spatially-dense model representation of static and dynamic space, as well as free and unknown space in the environment, as shown in Fig1.

As the DOGM is generated using data from the vehiclemounted sensors, the grid is traditionally ego-centric,i.e. the position of ego-vehicle is fixed in the grid. While this is an effective method in scene representation, it complicates the long-term prediction problem. For a dynamic ego-vehicle, the complete scene translates and/or rotates around the egovehicle, even the static components in the scene. Therefore, the prediction network must transform every cell in the grid, leading to blurry and vanishing static scene at longer prediction time horizons.

To address this, we instead generate DOGMs with respect to a fixed reference frame, referred as allo-centric grid. While the observed space around the ego-vehicle remains the same, the static scene structure in the allo-centric grid remains fixed. This is illustrated in Fig. 1 where the egovehicle is encircled, the vehicle moves like other agents in the scene.

We approach the long-term multi-step predictions of allocentric DOGM as a video prediction problem due to the inherent similarities between an image and an occupancy grid, and both being a spatio-temporal problem [START_REF] Oprea | A review on deep learning techniques for video prediction[END_REF]. Results incorporating different video prediction networks are studied, including state-of-the-art recurrent neural networks and memory-augmented network approaches. We compare and evaluate the prediction results of allo-centric and ego-centric grids for identical scenes and demonstrate the superior performances of the allo-centric grid predictions.

The proposed approach is validated with the real-world NuScenes dataset [START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF] of urban traffic scenes. We show that allo-centric grids significantly improve the prediction results and demonstrate the ability to retain the scene structure and learn behaviours.

The paper is organized as follows. Section II discusses related work to video and scene predictions. Section III describes the system overview. Section IV and V present implementations, results and analysis. Finally conclusions are drawn in section VI.

II. RELATED WORK A. Video Prediction

Spatio-temporal deep-learning methods have been effectively used for video prediction problems. Commonly, combinations of Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs) are incorporated. CNNs are capable of extracting spatial information and capturing inter-dependencies of the surrounding pixels while RNNs, such as long short-term memory (LSTM) blocks, [START_REF] Wang | Predrnn: A recurrent neural network for spatiotemporal predictive learning[END_REF]. Building on their original approach [START_REF] Wang | Predrnn: Recurrent neural networks for predictive learning using spatiotemporal lstms[END_REF], they introduce memorydecoupled spatio-temporal LSTM (ST-LSTM) blocks, feature zigzag memory flow and a novel curriculum learning strategy to improve prediction results. Kim et al. takes inspiration from memory-augmented networks to use external memory (LMC-Memory) to learn and store long-term motion dynamics and propose a memory query decomposition to address the high-dimensionality of motions in video predictions [START_REF] Lee | Video prediction recalling long-term motion context via memory alignment learning[END_REF].

B. Occupancy Grid Prediction

Jeon et al. proposed conventional ConvLSTM to predict interaction-intensive traffic scenes on occupancy grids [START_REF] Jeon | Traffic Scene Prediction via Deep Learning: Introduction of Multi-Channel Occupancy Grid Map as a Scene Representation[END_REF]. The approach represents only vehicles in the occupancy grid, their states extracted from camera inputs. Desquaire et al. [START_REF] Dequaire | Deep tracking in the wild: End-to-end tracking using recurrent neural networks[END_REF], proposed an end-to-end object-tracking approach by incorporating directly Lidar sensor data to predict the binary grid, using recurrent neural network. To incorporate egovehicle motion, they utilize a spatial transformer to allow internal memory of RNNs to learn environment of the state. Mohajerin et al. [START_REF] Mohajerin | Multi-step prediction of occupancy grid maps with recurrent neural networks[END_REF] suggested an RNN-based architecture with a difference learning method, and makes OGM prediction in the field of view of ego-vehicle front camera. Schreiber et al. [START_REF] Schreiber | Long-term occupancy grid prediction using recurrent neural networks[END_REF] proposed an encoder-decoder network architecture, along with skip connections, to make long-term DOGM predictions. While they collect the sensor data from an autonomous vehicle, the vehicle remains stationary and only acts as the sensor collection point at different intersections. Itkina et al. proposed to use evidential occupancy grid and implement PredNet architecture for the prediction [START_REF] Itkina | Dynamic environment prediction in urban scenes using recurrent representation learning[END_REF]. The approach is then carried forward to develop the double-pronged architecture [START_REF] Toyungyernsub | Double-Prong ConvLSTM for Spatiotemporal Occupancy Prediction in Dynamic Environments[END_REF] and attention-augmented ConvLSTM [START_REF] Lange | Attention Augmented ConvLSTM for Environment Prediction[END_REF]. The latter work is able to make long-term predictions, however at turns the predictions still lose the scene structure. Mann et al. [START_REF] Mann | Predicting future occupancy grids in dynamic environment with spatio-temporal learning[END_REF] addressed the problem of OGM prediction in urban scenes by incorporating vehicles semantics in the environment. Their proposed method depends on the annotated vehicle data labels available in the dataset.

Contrary to the conventional Occupancy Grid Prediction, we present an allo-centric DOGM representation to predict the urban traffic scene with respect to a fixed reference frame. Apart from the conventional recurrent representation learning approaches, we also use memory-augmented learning-based video-prediction method, in relevance to learning long-term motion context of the dynamic agents.

III. SYSTEM OVERVIEW

We discuss here the overall proposed approach for allocentric DOGM prediction, the pipeline is summarized in Fig. 1.

A. Dynamic Occupancy Grid Maps

Dynamic occupancy grid maps provide a discretized representation of environment in a bird's eye view, where every cell in the grid is independent and carries information about the associated occupancy and velocity.

To generate DOGMs, we incorporate the Conditional Monte Carlo Dense Occupancy Tracker (CMCDOT) [START_REF] Rummelhard | Conditional monte carlo dense occupancy tracker[END_REF]. This approach associates four occupancy states to the grid. Each cell carries the probabilities of the cell being i) occupied and static, ii) occupied and dynamic, iii) unoccupied or free and iv) if the occupancy is unknown. The probabilities of these four states sum to one. In our work, we make use of three of these states and represent the grid as an RGB image. The channels Red, Green and Blue represent the unknown state, dynamic state and static state respectively. The associated probabilities of the cell in the 3-channel DOGM grid are interpreted as the pixel values of the RGB images. The RGB grid images can be seen in Fig. 12. Low probabilities in all three channels leave the grid-image black, therefore, representing free space.

For allo-centric grid generation, we define the grid in the world frame, close to the initial position of ego-vehicle. The state probabilities are initially computed in an egocentric grid, since we use the on-board sensor data. To ensure that we have cell information for the complete allo-centric grid dimensions when the vehicle is dynamic and moving away from the world frame origin, a much larger ego-centric DOGM is computed. This information is then fused to update every cell states in the allo-centric grid in the world frame.

We compare the allo-centric and ego-centric grids at 4 time instants for the same scene and same grid dimensions in Figure 2. In the allo-centric grid, the ego-vehicle (illustrated in the pink box) can be seen moving with respect to the grid, while it remains fixed in the ego-centric grid. It is important to note that the observable space around the ego-vehicle remains the same for both grids. However, since they are defined in different frames, the two cover different spaces in the scene at a given time. We illustrate the common space covered by both grids since the start of the sequence, marked by yellow boundary. Fig. 2: Visualization of allo-centric and ego-centric grids, generated for the same scene. The area marked by yellow lines is the common region covered by both grids up until the t-th sequence. The ego-vehicle is boxed in pink grid and the bus passing by is encircled in white.

B. Problem Formulation

We formally define the task of predicting the scene in allo-centric DOGM representation, as sequence-to-sequence learning, see Fig. 1. A sequence comprises of a set of sequential grid images that capture the evolution of a given scene. Let X t ∈ R 3xW xH and Y t ∈ R 3xW xH be the t-th frame of the 3-channel grid-image where W and H denote the width and height respectively. The input sequence for the gridimage is denoted by X t-N :t , representing N consecutive frames. Given a set of input sequence, the task of the network is to predict future grid images, i.e. output sequence. The target and predicted output sequences are denoted by Y t+1:t+P and Ŷt+1:t+P where P is the prediction horizon.

For training and testing data, the DOGMs can be generated for both the input and the target sequences, leaving behind no additional need for labelled data or human intervention. Since the input sequences, X t-N :t , and output sequences, Y t+1:t+P , are represented as images, this prediction task can be considered a video prediction problem.

C. Deep Learning Prediction Architectures

To study and compare the scene prediction with egocentric and allo-centric grids, we train our datasets with different video prediction networks. We consider 3 networks, briefly discussed in section II-A: PredNet, PredRNN, LMC-Memory with memory alignment learning (here on referred as LMC-Memory).

PredNet [START_REF] Lotter | Deep predictive coding networks for video prediction and unsupervised learning[END_REF], inspired from predictive coding, makes predictions based on how the predicted frames deviate from the target [START_REF] Rane | Prednet and predictive coding: A critical review[END_REF]. The original work tests the network on vehicle mounted camera images from Kitti dataset [START_REF] Geiger | Vision meets robotics: The kitti dataset[END_REF] and demonstrates the ability to capture both egocentric motion as well as motion of objects in camera images. We consider PredRNN [START_REF] Wang | Predrnn: A recurrent neural network for spatiotemporal predictive learning[END_REF] and LMC-Memory architecture [START_REF] Lee | Video prediction recalling long-term motion context via memory alignment learning[END_REF] as the state of the art video prediction networks that aim to capture long-term dependencies and motion context. PredRNN implements novel ST-LSTM units with a zigzag internal memory flow and proposes memory decoupling loss to discourage learning redundant features. LMC-Memory architecture, on the other hand, proposes an external memory block with its own parameters to store various motion contexts. The approach also offers an efficient computation method since the motion context for long-term multi-step predictions is computed only once for a given input sequence.

We study these networks capabilities to retain the occupancy of the static region, and the ability to predict motion of dynamic agents in DOGM.

D. Unknown Channel and Loss functions

In both ego-centric and allo-centric grids, a significant part of the scene remains unobserved, see Fig. 2 (unknown channel is represented in red). This is more pronounced in the initial frames of the allo-centric grid, where the Lidar is unable to detect the farthest area from the ego-vehicle.

While it is more relevant to learn the evolution of static and dynamic components in the scene, inclusion of unknown channel is useful for our prediction task. A Lidar based grid is often unable to capture the full shape of a vehicle. For example, we can see in Fig. 2 how the occupied cells by the bus vary in different time steps on the grid. It is only in the 2.0s time step that a rectangular shape is observed, otherwise different parts of the bus remain unknown. The unknown channel at different instants also carries spatial information of the agents with respect to the ego-vehicle. Thus, with the sequential frames and the unknown channel, we assist the network to be able to extract spatial information and learn scene representation.

The inclusion of unknown channel and emphasis on learning static and dynamic components is addressed in the loss function. Loss function L in the implemented video prediction networks is modified to carry the weighted sum of the RGB channels:

L = αL R + β(L G + L B ) (1)
where, L R , L G and L B represent the loss for unknown (red), dynamic (green) and static channels (blue) respectively. In order to encourage the network to learn and improve the prediction of the static and dynamic channels, α is always kept smaller than β.

IV. EXPERIMENTS

A. Dataset

We study the prediction performance on the real-world NuScenes dataset [START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF]. The original dataset consists of 850 scenes for training and 150 scenes for testing, each scene is approximately 20s long. We generate the DOGM gridbased on the Lidar pointcloud and available odometry. For allo-centric grid, we represent the scene with respect to a fixed reference frame and a grid dimension of 60 x 60m, with a resolution of 0.1m per cell. Each sequence starts with the ego-vehicle heading facing up, capturing the scene 10m behind and 50m ahead of it. The initial pose was selected to ensure that the ego-vehicle remains within the grid for the total sequence length, even when running at a high speed. For egocentric grid, we generate a grid of the same dimensions and resolution, and the ego-vehicle fixed in the center. Each sequence is comprised of 35 frames, a time duration of 3.5s with DOGM grid images generated every 0.1s. In total, we have 4,250 training and 750 testing sequences respectively.

B. Training

The input sequence X t-9:t consists of 10 frames (1.0s). Each network is trained to make predictions Ŷt+1:t+25 for 25 future frames (2.5s). Both the allo-centric and egocentric datasets are trained with the original parameters of the respective video prediction network. For training with PredRNN and LMC Memory networks, both allo-centric and ego-centric grid images are resized to 192x192 pixels. PredRNN is trained with a batch size of 4 and a learning rate of 10 -4 . The number of channels of each hidden state is set to 64. The loss function is the sum of L2 and decoupling loss, and the values of α and β in Eq. ( 1) are set to 0.2 and 0.8. LMC-Memory is trained with a learning rate of 2x10 -4 , memory slot is set to 100 and ConvLSTM to 4 layers for frame predictions. The loss function is the sum of L1 and L2 losses. The values of α and β are set to 0.2 and 0.8. For training with PredNet, the grid images are resized to 160x160 pixels. The network is set to 4 hierarchical layers with an initial learning rate of 10 -3 . The loss function is the L1 loss of only the first layer, the values of α and β are set to 0.05 and 0.8. All models are trained on Adam optimizer for 30 epochs.

V. EVALUATION

For evaluation, we are particularly interested in static and dynamic agents in the scene. We discussed in section III-D, the utility of unknown regions in learning scene representation. But the unknown region occupies a big portion of the grid and, thus, in evaluation, overshadows the performance of more interesting and relevant segments: static and dynamic regions. For this reason, we evaluate the dataset and network performances based on two channels of the predicted images, the blue and green channels representing static and dynamic components in the scene. We encourage the readers to refer to the video 1 for a better visualization of the results.

1 https://youtu.be/z-0BVM93X8c

A. Quantitative Evaluation

The allo-centric and ego-centric grids at any instant observe different parts of the scene, see Fig. 2. For fair comparison between them, we modify the test dataset and crop out the part of each t-frame that has not been observed until the t-th sequence by both grids. Thus, for example, the part of the grids outside of the yellow dotted boxes in Fig. 2 are blacked out for the input sequence frames X t-N :t as well as the target frames in the output sequence Y t+1:t+P .

We measure the performances using three metrics: MSE (Mean Square Error), SSIM (Structured Similarity Indexing Method), and LPIPS (Learned Perceptual Image Patch Similarity) [START_REF] Zhang | The unreasonable effectiveness of deep features as a perceptual metric[END_REF]. MSE is calculated by the pixel-wise difference between the ground truth and the predicted frame per channel and per cell. However, with MSE, the slightest error in predicted motion can result in large errors in the egocentric grids dataset. The SSIM and LPIPS metrics evaluate the prediction results based on the structural similarity and perception similarity respectively. Lower values are better for MSE and LPIPS while higher values are better for SSIM.

Table I shows average results for the complete 2.5s prediction horizons. The MSE score of allo-centric grids is significantly lower compared to the one of ego-centric grids. Since the complete scene transforms with respect to the ego-vehicle, the MSE is always higher in the ego-centric grid. The SSIM and LPIPS scores are also significantly superior for the allo-centric grid, due to the tendency of egocentric grids to get increasingly blurry for higher prediction horizons. In Fig. 3, we plot scores of the metrics for every 0.5s prediction step. The results with allo-centric grid (shown in blue) always perform better than the ego-centric grids. Among the three prediction networks, overall PredRNN performs the best with allo-centric grids. However, with the ego-centric grids (results shown in orange), PredRNN offers a good MSE score but the SSIM and LPIPS performances drop after 1.0s. This is because PredRNN tends to make blurry and diffused predictions in the output frames; this helps reduce the MSE but the scene loses its structures. This is further seen in the qualitative results discussed in section V-B and illustrated in Fig. 4.

Network

B. Qualitative Evaluation

The prediction results between the allo-centric and egocentric grids differ drastically when the ego-vehicle is turning Fig. 3: Results with the MSE(↓), SSIM(↑) and LPIPS(↓) metrics with allo-centric and ego-centric grids for input sequences of 1.0s and prediction horizon up to 2.5s. For fair comparison, all test sequence frames were modified to only contain the scene observable in both the allo-centric and ego-centric grids. The allo-centric grid (results plotted in blue) outperforms the other with all three video prediction networks. at an intersection or driving on a curved road. Figure 4 shows results for a sequence where the ego-vehicle is exiting a roundabout. In this scene, while there are no other dynamic agents, the network needs to predict the behaviour of the egovehicle, when it is driving along the curved static segment (alluding to road structure) and is headed towards static objects/obstacles. For the allo-centric grids, the challenge is to predict the ego-vehicle pose while the scene remains static. The best results are achieved with the LMC-Memory. The vehicle pose is well-predicted up to 2.5s, its orientation is adjusted so that it does not hit the static components. For the same grid, the PredRNN fails to learn and predict the behaviour resulting in false prediction of collisions. The egovehicle, while getting more blurry, diffuses into the static obstacles on the road. With the PredNet, the ego vehicle is almost already lost at 1.5s prediction horizon. This is expected behaviour since PredNet is ideally not aimed at long-term video predictions. With all three networks, the egovehicle gets more blurry, however with PredRNN, the static scene also tends to get blurry at larger prediction horizon.

In the ego-centric grid, the whole scene rotates around the ego-vehicle. LMC-memory and PredNet significantly lose the static components ahead of the vehicle. The rotation results in increasing blurriness at every time step. PredRNN predictions are more diffused and faint blurry cells are still visible ahead of the vehicle, even at 2.5s prediction horizon. In context of planning and safe navigation, this high uncertainty in the environment structure renders the prediction results unreliable.

VI. DISCUSSION AND FUTURE WORK

In this work, we presented a novel allo-centric dynamic ocuupancy grid approach for long-term prediction of urban traffic scene, and compared it to the conventional egocentric DOGM approach. We trained and tested various video prediction networks to show that allo-centric DOGM representation has superior ability to predict the same scene.

The most significant improvement is the allo-centric grid's ability to retain the static scene structure, especially when the vehicle turns. The ego-centric grid, on the other hand tends to lose the static scene, and hence the crucial information about whether the given space is occupied or free.

The results of allo-centric grids prediction with state-ofthe-art PredRNN and LMC-Memory approaches have shown complementary benefits. PredRNN predictions, though diffuse and get more blurry, are capable of maintaining agents longer. We observe that LMC-memory shows better tendency at learning behaviours in comparison to the PredRNN.

It is pertinent to mention here that the two grids are still very similar. In both scenarios, the observable space updates relative to the position of the vehicle in the scene. Thus, in allo-centric grid while the grid is no more fixed to the ego-vehicle, the ego-vehicle bias remains.

All three video prediction networks tested in this work address the prediction problem as deterministic. However, the behaviour of agents in urban traffic scene tends to be multimodal. For future work, the addition of multimodal prediction capabilities in the network architecture would be interesting. Additionally, the incorporation of semantics in the occupancy grid such as agent type and offline road information could assist in learning behaviours and interactions.

Fig. 1 :

 1 Fig.1: Overview of our proposed approach. The allo-centric DOGM is represented as an image. Each channel red, green and blue represent unknown, dynamic and static cells respectively. The black space represents known free space. The ego-vehicle is circled in dotted line in both input and target output sequences.

Fig. 4 :

 4 Fig.4: Qualitative results for the ego-vehicle leaving a roundabout on both allo-centric (4a) and ego-centric grids (4b). The input sequence consists of 10 frames (1.0s) and output predicted sequence of up to 25 frames (2.5s). The prediction results are shown at 0.5s, 1.5s and 2.5s instants and are magnified at the interesting spaces, marked by red box in the target(ground truth) frames. The best results can be observed with LMC-Memory network with the allo-centric grid that retains the scene structure and predicts the motion of the ego-vehicle best.

TABLE I :

 I Average results with allo-centric and ego-centric grids for prediction horizon of 2.5s. The allocentric grid outperforms the other in all three video prediction networks.