accuracy of 30.3% on single sentences and 0.3 on complete paragraphs
EXTRACTIVE
Table TABREF8 shows the results for the baseline models as well as the HUMAN measured performance on the task. The human performance provides an upper bound for the RUN task performance, while the simple baselines provide lower bounds. The best baseline model is NO-MOVE, reaching an accuracy of 30.3% on single sentences and 0.3 on complete paragraphs. For the HUMAN case, paragraph accuracy reaches above 80.
1909.08970
Introduction Ġand ĠBackground </s> The Ġtask Ġof Ġinterpreting Ġand Ġfollowing Ġnatural Ġlanguage Ġ( NL ) Ġnavigation Ġinstructions Ġinvolves Ġinter le aving Ġdifferent Ġsignals , Ġat Ġthe Ġvery Ġleast Ġthe Ġlinguistic Ġutter ance Ġand Ġthe Ġrepresentation Ġof Ġthe Ġworld . ĠFor Ġexample , Ġin Ġturn Ġright Ġon Ġthe Ġfirst Ġintersection , Ġthe Ġinstruction Ġneeds Ġto Ġbe Ġinterpreted , Ġand Ġa Ġspecific Ġobject Ġin Ġthe Ġworld Ġ( the Ġintersection ) Ġneeds Ġto Ġbe Ġlocated Ġin Ġorder Ġto Ġexecute Ġthe Ġinstruction . ĠIn ĠNL Ġnavigation Ġstudies , Ġthe Ġrepresentation Ġof Ġthe Ġworld Ġmay Ġbe Ġprovided Ġvia Ġvisual Ġsensors ĠB IB REF 0 , ĠB IB REF 1 , ĠB IB REF 2 , ĠB IB REF 3 , ĠB IB REF 4 Ġor Ġas Ġa Ġsymbolic Ġworld Ġrepresentation . ĠThis Ġwork Ġfocuses Ġon Ġnavigation Ġbased Ġon Ġa Ġsymbolic Ġworld Ġrepresentation Ġ( re ferred Ġto Ġas Ġa Ġmap ). </s> Previous Ġdatasets Ġfor ĠNL Ġnavigation Ġbased Ġon Ġa Ġsymbolic Ġworld Ġrepresentation , ĠHC RC ĠB IB REF 5 , ĠB IB REF 6 , ĠB IB REF 7 Ġand ĠSA IL ĠB IB REF 8 , ĠB IB REF 9 , ĠB IB REF 10 , ĠB IB REF 11 , ĠB IB REF 12 , ĠB IB REF 13 , ĠB IB REF 14 , ĠB IB REF 15 Ġpresent Ġrelatively Ġsimple Ġworlds , Ġwith Ġa Ġsmall Ġfixed Ġset Ġof Ġentities Ġknown Ġto Ġthe Ġnavig ator Ġin Ġadvance . ĠSuch Ġrepresentations Ġbypass Ġthe Ġgreat Ġcomplexity Ġof Ġreal Ġurban Ġnavigation , Ġwhich Ġconsists Ġof Ġlong Ġpaths Ġand Ġan Ġabundance Ġof Ġpreviously Ġunseen Ġentities Ġof Ġdifferent Ġtypes . </s> In Ġthis Ġwork Ġwe Ġintroduce ĠReal istic ĠUrban ĠNavigation Ġ( R UN ), Ġwhere Ġwe Ġaim Ġto Ġinterpret Ġnavigation Ġinstructions Ġrelative Ġto Ġa Ġrich Ġsymbolic Ġrepresentation Ġof Ġthe Ġworld , Ġgiven Ġby Ġa Ġreal Ġdense Ġurban Ġmap . ĠTo Ġaddress ĠRUN , Ġwe Ġdesigned Ġand Ġcollected Ġa Ġnew Ġdataset Ġbased Ġon ĠOpen Street Map , Ġin Ġwhich Ġwe Ġalign ĠNL Ġinstructions Ġto Ġtheir Ġcorresponding Ġroutes . ĠUsing ĠAmazon ĠMechanical ĠTurk , Ġwe Ġcollected Ġ25 15 Ġinstructions Ġover Ġ3 Ġregions Ġof ĠManhattan , Ġall Ġspecified Ġ( and Ġverified ) Ġby Ġ( respective ) Ġsets Ġof Ġhumans Ġworkers . ĠThis Ġtask Ġraises Ġseveral Ġchallenges . ĠFirst Ġof Ġall , Ġwe Ġassume Ġa Ġlarge Ġworld , Ġproviding Ġlong Ġroutes , Ġvulnerable Ġto Ġerror Ġpropagation ; Ġsecondly , Ġwe Ġassume Ġa Ġrich Ġenvironment , Ġwith Ġentities Ġof Ġvarious Ġdifferent Ġtypes , Ġmost Ġof Ġwhich Ġare Ġunseen Ġduring Ġtraining Ġand Ġare Ġnot Ġknown Ġin Ġadvance ; Ġfinally , Ġwe Ġevaluate Ġon Ġthe Ġfull Ġroute Ġintended , Ġrather Ġthan Ġon Ġlast - position Ġonly . </s> We Ġthen Ġpropose Ġa Ġstrong Ġneural Ġbaseline Ġfor ĠRUN Ġwhere Ġwe Ġaugment Ġa Ġstandard Ġenc oder - dec oder Ġarchitecture Ġwith Ġan Ġentity Ġabstraction Ġlayer , Ġattention Ġover Ġwords Ġand Ġworlds , Ġand Ġa Ġconstantly Ġupdating Ġworld - state . ĠOur Ġexperimental Ġresults Ġand Ġab lation Ġstudy Ġshow Ġthat Ġthis Ġarchitecture Ġis Ġindeed Ġbetter - equipped Ġto Ġtreat Ġgrounding Ġin Ġrealistic Ġurban Ġsettings Ġthan Ġstandard Ġsequence - to - sequence Ġarchitectures . ĠGiven Ġthis ĠRUN Ġbenchmark , Ġempirical Ġresults , Ġand Ġevaluation Ġprocedure , Ġwe Ġhope Ġto Ġencourage Ġfurther Ġinvestigation Ġinto Ġthe Ġtopic Ġof Ġinterpreting ĠNL Ġinstructions Ġin Ġrealistic Ġand Ġpreviously Ġunseen Ġurban Ġdomains . </s> [ 1 ] The Ġtask Ġdefined Ġby ĠB IB REF 6 Ġis Ġof Ġmoving Ġbetween Ġentities Ġonly . </s> The ĠRUN ĠTask Ġand ĠDat as et </s> In Ġthis Ġwork Ġwe Ġaddress Ġthe Ġtask Ġof Ġfollowing Ġa Ġsequence Ġof ĠNL Ġnavigation Ġinstructions Ġgiven Ġin Ġcoll oqu ial Ġlanguage Ġbased Ġon Ġa Ġdense Ġurban Ġmap . </s> The Ġinput Ġto Ġthe ĠRUN Ġtask Ġwe Ġdefine Ġis Ġas Ġfollows : Ġ( i ) Ġa Ġmap Ġwith Ġrich Ġdetails Ġdivided Ġinto Ġtiles , Ġ( ii ) Ġan Ġexplicit Ġstarting Ġpoint , Ġand Ġ( iii ) Ġa Ġsequence Ġof Ġnavigation Ġinstructions Ġwe Ġhence forth Ġrefer Ġto Ġas Ġa Ġnavigation Ġparagraph Ġ. ĠWe Ġrefer Ġto Ġeach Ġsentence Ġas Ġan Ġinstruction , Ġand Ġwe Ġassume Ġthat Ġfollowing Ġthe Ġindividual Ġinstructions Ġin Ġthe Ġparagraph Ġone Ġby Ġone Ġwill Ġlead Ġthe Ġagent Ġto Ġthe Ġintended Ġend - point . ĠThe Ġoutput Ġof ĠRUN Ġis Ġthe Ġentire Ġroute Ġdescribed Ġby Ġthe Ġparagraph , Ġi . e ., Ġall Ġcoordinates Ġup Ġto Ġand Ġincluding Ġits Ġend - point , Ġpinned Ġon Ġthe Ġmap . </s> In Ġorder Ġto Ġaddress ĠRUN Ġwe Ġdesigned Ġand Ġcollected Ġa Ġnovel Ġdataset , Ġhence forth Ġthe ĠRUN Ġdataset , Ġwhich Ġis Ġbased Ġon ĠOpen Street Map Ġ( OS M ). ĠThe Ġmap Ġcontains Ġrich Ġlayers Ġand Ġan Ġabundance Ġof Ġentities Ġof Ġdifferent Ġtypes . ĠEach Ġentity Ġis Ġcomplex Ġand Ġcan Ġcontain Ġ( at Ġleast ) Ġfour Ġlabels : Ġname , Ġtype , Ġis _ building = y / n , Ġand Ġhouse Ġnumber . ĠAn Ġentity Ġcan Ġspread Ġover Ġseveral Ġtiles . ĠAs Ġthe Ġmaps Ġdo Ġnot Ġoverlap , Ġonly Ġvery Ġfew Ġentities Ġare Ġshared Ġamong Ġthem . ĠThe ĠRUN Ġdataset Ġalign s ĠNL Ġnavigation Ġinstructions Ġto Ġcoordinates Ġof Ġtheir Ġcorresponding Ġroute Ġon Ġthe ĠOS M Ġmap . </s> We Ġcollected Ġthe ĠRUN Ġdataset Ġusing ĠAmazon ĠMechanical ĠTurk Ġ( MT ur k ), Ġallowing Ġonly Ġnative ĠEnglish Ġspeakers Ġto Ġperform Ġthe Ġtask . ĠWe Ġcollected Ġinstructions Ġbased Ġon Ġthree Ġdifferent Ġareas , Ġall Ġin Ġurban , Ġdense Ġparts Ġof ĠManhattan . ĠThe Ġsize Ġof Ġeach Ġmap Ġis Ġ$ 0 . 5 $ Ġ$ km ^{ 2 } $. ĠThe Ġdataset Ġcontains Ġ25 15 Ġnavigation Ġinstructions Ġ( equal Ġto Ġ389 Ġcomplete Ġparagraphs ) Ġpaired Ġwith Ġtheir Ġroutes . ĠThe Ġparagraphs Ġare Ġcrowd - s ourced Ġfrom Ġ389 Ġdifferent Ġinstructors , Ġof Ġwhich Ġstyle Ġand Ġlanguage Ġvary ĠB IB REF 18 . </s> Our Ġdata Ġcollection Ġprotocol Ġis Ġas Ġfollows . ĠFirst , Ġwe Ġasked Ġthe ĠM Tur k Ġworker Ġto Ġdescribe Ġa Ġroute Ġbetween Ġtwo Ġlandmarks Ġof Ġtheir Ġchoice . ĠAfter Ġhaving Ġdescribed Ġthe Ġcomplete Ġroute Ġin ĠNL , Ġthe Ġsame Ġworker Ġwas Ġinstructed Ġto Ġpin Ġtheir Ġdescribed Ġroute Ġon Ġthe Ġmap . ĠThis Ġwas Ġmoder ated Ġby Ġshowing Ġthem Ġthe Ġparagraph Ġthey Ġnarrated , Ġsentence Ġby Ġsentence , Ġso Ġthat Ġthey Ġhave Ġto Ġpin Ġon Ġthe Ġmap Ġeach Ġinstruction Ġseparately . ĠA Ġworker Ġcould Ġonly Ġpin Ġroutes Ġon Ġstreet Ġpaths . ĠFurthermore , Ġon Ġevery Ġturn Ġthe Ġworker Ġhad Ġto Ġmark Ġan Ġexplicit Ġpoint Ġon Ġthe Ġmap Ġwhich Ġmarked Ġthe Ġdirection Ġin Ġwhich Ġthe Ġworker Ġneeds Ġto Ġmove Ġnext . ĠAn Ġexample Ġof Ġsimple Ġindividual Ġinstructions Ġand Ġtheir Ġrespective Ġroute Ġis Ġgiven Ġin ĠFigure ĠFIG REF 5 . </s> We Ġthen Ġasked Ġa Ġdis j oint Ġset Ġof Ġworkers Ġ( testers ) Ġto Ġverify Ġthe Ġroutes Ġby Ġdisplaying Ġthe Ġstarting Ġpoint Ġof Ġthe Ġroute , Ġand Ġdisplaying Ġthe Ġinstructions Ġin Ġthe Ġparagraph Ġsentence - by - sent ence . ĠThe Ġt ester Ġhad Ġto Ġpin Ġthe Ġfinal Ġpoint Ġof Ġthe Ġsentence . ĠEach Ġroute Ġwas Ġtested Ġby Ġthree Ġdifferent Ġworkers . ĠTesting Ġthe Ġroutes Ġallowed Ġus Ġto Ġfind Ġincorrect Ġroutes Ġ( paragraph s Ġthat Ġdon 't Ġmatch Ġan Ġactual Ġpath ) Ġand Ġdiscard Ġthem . ĠThey Ġalso Ġprovide Ġan Ġestimate Ġof Ġthe Ġhuman Ġperformance Ġon Ġthe Ġtask Ġ( Rep orted Ġin ĠSection ĠSEC REF 4 , ĠExper iments ). </s> Having Ġcollected Ġthe Ġdata , Ġwe Ġdivided Ġthe Ġmap Ġinto Ġtiles , Ġeach Ġtile Ġis Ġ11 . 132 Ġm ĠX Ġ11 . 132 Ġm . ĠEach Ġtile Ġcontains Ġthe Ġlabels Ġof Ġthe Ġentities Ġit Ġdisplays Ġon Ġthe Ġmap , Ġsuch Ġas Ġrestaurants , Ġtraffic - lights , Ġetc ., Ġand Ġthe Ġwalk able Ġstreets Ġin Ġit . ĠEach Ġwalk able Ġstreet Ġis Ġcomposed Ġof Ġan Ġordered Ġlist Ġof Ġtiles , Ġincluding Ġa Ġstarting Ġtile Ġand Ġan Ġend Ġtile . ĠTable ĠT AB REF 1 Ġshows Ġstatistics Ġover Ġthe Ġdataset . ĠTable ĠT AB REF 2 Ġcharacterize Ġlinguistic Ġphenomena Ġin ĠRUN , Ġcategorized Ġaccording Ġto Ġthe Ġcatalogue Ġof ĠB IB REF 16 . ĠTable ĠT AB REF 3 Ġshows Ġa Ġquantitative Ġcomparison Ġof Ġthe ĠRUN Ġdataset Ġto Ġprevious Ġdatasets Ġof Ġmap - based Ġnavigation . ĠThe Ġtable Ġunderscores Ġsome Ġkey Ġfeatures Ġof ĠRUN , Ġrelative Ġto Ġthe Ġprevious Ġtasks . ĠRUN Ġcontains Ġlonger Ġpaths Ġand Ġmany Ġmore Ġentities Ġthat Ġare Ġunique , Ġthus Ġappearing Ġfor Ġthe Ġfirst Ġtime Ġduring Ġtesting ; Ġthe Ġsize Ġof Ġthe Ġmap Ġis Ġon Ġa Ġdifferent Ġscale Ġthan Ġprevious Ġtasks , Ġthus , Ġampl ifying Ġthe Ġgrounding Ġchallenge ; Ġthe Ġnumber Ġof Ġtiles Ġmoved Ġis Ġaccordingly Ġlarger Ġthan Ġin Ġprevious Ġdatasets , Ġhence Ġincreasing Ġthe Ġvulnerability Ġto Ġerror Ġpropagation . </s> Overall , ĠRUN Ġcontains Ġchallenging Ġlinguistic Ġphenomena , Ġat Ġleast Ġas Ġin Ġprevious Ġwork , Ġand Ġa Ġrich Ġenvironment , Ġwith Ġmore Ġrealistic Ġpaths Ġthan Ġin Ġprevious Ġtasks . </s> Mod els Ġfor ĠRUN </s> We Ġmodel ĠRUN Ġas Ġa Ġsequence - to - sequence Ġlearning Ġproblem , Ġwhere Ġwe Ġmap Ġa Ġsequence Ġof Ġinstructions Ġto Ġa Ġsequence Ġof Ġactions Ġthat Ġshould Ġbe Ġperformed Ġin Ġorder Ġto Ġpin Ġthe Ġactual Ġpath Ġon Ġthe Ġmap . ĠThe Ġexecution Ġsystem Ġwe Ġprovide Ġfor Ġthe Ġtask Ġdefines Ġthree Ġtypes Ġof Ġactions : Ġ* T URN , Ġ* W ALK , Ġ* END . Ġ* T URN Ġis Ġone Ġof Ġthe Ġfollowing : Ġright - turn , Ġleft - turn , Ġturn - around . ĠThe Ġturning Ġmove Ġis Ġnot Ġnecessarily Ġan Ġexact Ġ90 - degree Ġturn ; Ġthe Ġexecution Ġsystem Ġlooks Ġfor Ġthe Ġclosest Ġturn Ġoption . Ġ* W ALK Ġis Ġa Ġchange Ġof Ġposition Ġin Ġthe Ġdirection Ġwe Ġare Ġfacing . ĠThe Ġstreets Ġcan Ġbe Ġcurved , Ġso Ġ* W ALK Ġis Ġrelative Ġto Ġthe Ġstreet Ġthat Ġthe Ġagent Ġis Ġon . ĠEach Ġstreet Ġis Ġan Ġordered - list Ġof Ġtiles , Ġso Ġan Ġaction Ġof Ġwalking Ġtwo Ġsteps Ġis Ġin Ġfact Ġtwo Ġactions Ġof Ġ* W ALK , Ġin Ġthe Ġdirection Ġthe Ġagent Ġis Ġfacing . ĠThe Ġ* END Ġaction Ġdefines Ġthe Ġend Ġof Ġeach Ġroute . ĠThe Ġinput Ġconsists Ġof Ġan Ġinstruction Ġsequence Ġ$ x _{ 1 : N } $, Ġa Ġmap Ġ$ M $, Ġand Ġa Ġstarting Ġpoint Ġ$ p _ 0 $ Ġon Ġthe Ġmap . ĠThe Ġoutput Ġis Ġa Ġsequence Ġof Ġactions Ġ$ a ^ * _{ 1 : T } $ Ġto Ġbe Ġexecuted . </s> Where Ġ$ x _ i $ Ġdenote Ġsentences , Ġ$ a _ i $ Ġdenotes Ġactions , Ġ$ M $ Ġis Ġthe Ġmap Ġand Ġ$ p _ 0 $ Ġis Ġthe Ġstarting Ġpoint . </s> Our Ġbasic Ġmodel Ġfor ĠRUN Ġis Ġa Ġsequence - to - sequence Ġmodel Ġsimilar Ġto Ġthe Ġwork Ġof ĠB IB REF 19 Ġon ĠSA IL , Ġand Ġinspired Ġby ĠB IB REF 20 . ĠIt Ġis Ġbased Ġon ĠCondition ed ĠGeneration Ġwith ĠAttention Ġ( C GA ). ĠTo Ġthis Ġmodel Ġwe Ġadded Ġan ĠEntity Ġabstraction Ġlayer Ġ( C GA E ) Ġand Ġa ĠWorld - state Ġrepresentation Ġ( C GA EW ). ĠIt Ġthus Ġconsists Ġof Ġsix Ġcomponents Ġwe Ġdescribe Ġin Ġturn ĠâĢĵ ĠEnc oder , ĠDecoder , ĠAttention , ĠEntity ĠAb st raction , ĠWorld - State ĠProcessor , ĠExecution - System . ĠThe Ġcomplete Ġarchitecture Ġis Ġdepicted Ġin ĠFig . ĠFIG REF 7 . </s> The ĠEnc oder Ġtakes Ġthe Ġsequence Ġof Ġwords Ġthat Ġassemb les Ġa Ġsingle Ġsentence Ġand Ġenc odes Ġit Ġas Ġa Ġvector Ġusing Ġa Ġbi L ST M ĠB IB REF 21 . ĠThe ĠDecoder Ġis Ġan ĠL ST M Ġgenerating Ġa Ġsequence Ġof Ġactions Ġthat Ġthe Ġexecution - system Ġcan Ġperform , Ġaccording Ġto Ġweights Ġdefined Ġby Ġan ĠAttention Ġlayer . ĠThe ĠEntity ĠAb st raction Ġcomponent Ġdeals Ġwith Ġout - of - voc abulary Ġwords Ġ( OO V ). ĠWe Ġadopt Ġa Ġsimilar Ġapproach Ġto ĠB IB REF 22 , ĠB IB REF 23 , Ġreplacing Ġphrases Ġin Ġthe Ġsentences Ġwhich Ġrefer Ġto Ġpreviously Ġunseen Ġentities Ġwith Ġvariables , Ġprior Ġto Ġdelivering Ġthe Ġsentence Ġto Ġthe ĠEnc oder . ĠE . g ., ĠWalk Ġfrom ĠMacy 's Ġto Ġ7 th Ġstreet Ġturns Ġinto ĠWalk Ġfrom ĠX 1 Ġto ĠY 1 . ĠVari ables Ġare Ġtyped Ġ( stre ets , Ġrestaurants , Ġetc .) Ġand Ġare Ġnumbered Ġbased Ġon Ġtheir Ġorder Ġof Ġoccurrence Ġin Ġthe Ġsentence . ĠThe Ġnumbering Ġres ets Ġafter Ġevery Ġutter ance , Ġso Ġthe Ġmodel Ġremains Ġwith Ġa Ġhandful Ġof Ġtyped Ġentity - vari ables . ĠThe ĠWorld - State ĠProcessor Ġmaps Ġvariables Ġto Ġthe Ġentities Ġon Ġthe Ġmap Ġwhich Ġare Ġmentioned Ġin Ġthe Ġsentence . ĠThe Ġworld - state Ġrepresentation Ġconsists Ġof Ġtwo Ġvectors , Ġone Ġrepresenting Ġthe Ġentities Ġat Ġthe Ġcurrent Ġposition , Ġand Ġone Ġrepresenting Ġthe Ġentities Ġin Ġthe Ġpath Ġahead . ĠThe ĠAttention Ġlayer Ġconsiders Ġthe Ġsequence Ġof Ġencoded Ġwords Ġas Ġwell Ġas Ġcurrent Ġworld - state , Ġand Ġprovides Ġweights Ġon Ġthe Ġwords Ġfor Ġeach Ġof Ġthe Ġdec oder Ġsteps . ĠIn Ġboth Ġtraining Ġand Ġtesting , Ġthe ĠExecution - System Ġexecutes Ġeach Ġaction Ġseparately Ġto Ġproduce Ġthe Ġnext Ġposition . </s> Exper iments </s> We Ġevaluate Ġour Ġmodel Ġon ĠRUN Ġand Ġassess Ġthe Ġcontribution Ġof Ġthe Ġparticular Ġcomponents Ġthat Ġwe Ġadded Ġon Ġtop Ġof Ġthe Ġstandard ĠC GA Ġmodel . </s> We Ġtrain Ġthe Ġmodel Ġusing Ġa Ġnegative Ġlog - like lihood Ġloss , Ġand Ġused ĠAdam ĠB IB REF 24 Ġoptimization . ĠFor Ġweights Ġinitialization Ġwe Ġrely Ġon ĠB IB REF 25 . ĠWe Ġused Ġa Ġgrid Ġsearch Ġto Ġvalidate Ġthe Ġhyper - param eters . ĠThe Ġmodel Ġconver ged Ġat Ġaround Ġ30 Ġepoch s Ġand Ġproduced Ġgood Ġresults Ġwith Ġ0 . 9 Ġdrop - out Ġand Ġa Ġbeam Ġof Ġsize Ġ4 . ĠDuring Ġinference , Ġwe Ġseek Ġthe Ġbest Ġcandidate Ġpath Ġusing Ġbeam - search Ġand Ġnormal ize Ġthe Ġscores Ġof Ġthe Ġsequences Ġaccording Ġto ĠB IB REF 26 . </s> We Ġfollow Ġthe Ġevaluation Ġmethodology Ġdefined Ġby ĠB IB REF 9 Ġfor ĠSA IL Ġwhere Ġwe Ġuse Ġthree - fold Ġvalidation , Ġand Ġin Ġeach Ġfold , Ġwe Ġuse Ġtwo Ġmaps Ġfor Ġtraining Ġ( 90 %) Ġand Ġvalidation Ġ( 10 %) Ġand Ġtest Ġon Ġthe Ġthird Ġone . ĠWe Ġreport Ġa Ġsized - weight ed Ġaverage Ġtest Ġresult . ĠFor Ġall Ġmodels Ġwe Ġreport Ġthe Ġaccuracy Ġper Ġsingle Ġsentences Ġand Ġfull Ġparagraphs . ĠSuccess Ġis Ġmeasured Ġby Ġgenerating Ġan Ġexact Ġroute , Ġnot Ġstr iding Ġaway Ġfrom Ġthe Ġpath . ĠThe Ġlast Ġposition Ġon Ġthe Ġpath Ġshould Ġbe Ġwithin Ġfive Ġtile Ġe ucl ide an Ġdistance Ġfrom Ġthe Ġintended Ġdestination , Ġas Ġthe Ġposition Ġexplained Ġin Ġthe Ġinstruction Ġmight Ġnot Ġbe Ġspecific Ġenough Ġfor Ġone Ġtile . ĠIn Ġsingle - sent ences , Ġthe Ġlast Ġposition Ġshould Ġalso Ġbe Ġfacing Ġthe Ġcorrect Ġdirection . </s> We Ġprovide Ġthree Ġsimple Ġbas elines Ġfor Ġthe ĠRUN Ġtask : Ġ( 1 ) ĠNO - MO VE : Ġthe Ġonly Ġposition Ġconsidered Ġis Ġthe Ġstarting Ġpoint ; Ġ( 2 ) ĠRAND OM : ĠAs Ġin ĠB IB REF 4 , Ġturn Ġto Ġa Ġrandomly Ġselected Ġheading , Ġthen Ġexecute Ġa Ġnumber Ġof Ġ* W ALK Ġactions Ġof Ġan Ġaverage Ġroute ; Ġ( 3 ) ĠJ UMP : Ġat Ġeach Ġsentence , Ġextract Ġentities Ġfrom Ġthe Ġmap Ġand Ġmove Ġbetween Ġthem Ġin Ġthe Ġorder Ġthey Ġappear . ĠIf Ġthe Ġ* W ALK Ġaction Ġis Ġinvalid Ġwe Ġtake Ġa Ġrandom Ġ* T URN Ġaction . </s> Table ĠT AB REF 8 Ġshows Ġthe Ġresults Ġfor Ġthe Ġbaseline Ġmodels Ġas Ġwell Ġas Ġthe ĠHUM AN Ġmeasured Ġperformance Ġon Ġthe Ġtask . ĠThe Ġhuman Ġperformance Ġprovides Ġan Ġupper Ġbound Ġfor Ġthe ĠRUN Ġtask Ġperformance , Ġwhile Ġthe Ġsimple Ġbas elines Ġprovide Ġlower Ġbounds . ĠThe Ġbest Ġbaseline Ġmodel Ġis ĠNO - MO VE , Ġreaching Ġan Ġaccuracy Ġof Ġ30 . 3 % Ġon Ġsingle Ġsentences Ġand Ġ0 . 3 Ġon Ġcomplete Ġparagraphs . ĠFor Ġthe ĠHUM AN Ġcase , Ġparagraph Ġaccuracy Ġreaches Ġabove Ġ80 . </s> Table ĠT AB REF 8 Ġshows Ġthe Ġresults Ġof Ġour Ġmodel Ġas Ġan Ġab lation Ġstudy , Ġand ĠTable ĠT AB REF 9 Ġshows Ġtypical Ġerrors Ġof Ġeach Ġvariant . ĠWe Ġsee Ġthat ĠC GA E Ġoutper forms ĠC GA , Ġas Ġthe Ġswap Ġof Ġentities Ġwith Ġvariables Ġlowers Ġthe Ġcomplexity Ġof Ġthe Ġlanguage Ġthat Ġthe Ġmodel Ġneeds Ġto Ġlearn , Ġallowing Ġthe Ġmodel Ġto Ġeffectively Ġcope Ġwith Ġunseen Ġentities Ġat Ġtest Ġtime . ĠWe Ġfurther Ġfound Ġthat , Ġin Ġmany Ġcases , ĠC GA E Ġproduces Ġthe Ġright Ġtype Ġof Ġaction , Ġbut Ġit Ġdoes Ġnot Ġproduce Ġenough Ġof Ġit Ġto Ġreach Ġthe Ġintended Ġdestination . ĠWe Ġattribute Ġthese Ġerrors Ġto Ġthe Ġabsence Ġof Ġa Ġworld - state Ġrepresentation , Ġresulting Ġin Ġan Ġincap ability Ġto Ġground Ġinstructions Ġto Ġspecific Ġlocations . ĠC GA EW Ġimproves Ġupon ĠC GA E Ġas Ġthe Ġexistence Ġof Ġworld - state Ġin Ġthe Ġscore Ġof Ġthe Ġattention Ġlayer Ġallows Ġthe Ġmodel Ġbetter Ġlearn Ġthe Ġgrounding Ġof Ġentities Ġin Ġthe Ġinstruction Ġto Ġthe Ġmap . ĠHowever Ġour Ġbest Ġmodel Ġstill Ġfails Ġon Ġfeatures Ġnot Ġcaptured Ġby Ġour Ġworld - state : Ġabstract Ġunmarked Ġentities Ġsuch Ġas Ġblocks , Ġintersections , Ġetc , Ġand Ġgeneric Ġentities Ġsuch Ġas Ġtraffic - lights Ġ( Tab . ĠT AB REF 9 ). </s> Conclusion </s> We Ġintroduce ĠRUN , Ġa Ġnew Ġtask Ġand Ġdataset Ġfor ĠNL Ġnavigation Ġin Ġrealistic Ġurban Ġenvironments . ĠWe Ġcollected Ġ( and Ġverified ) ĠNL Ġnavigation Ġinstructions Ġaligned Ġwith Ġactual Ġpaths , Ġand Ġpropose Ġa Ġstrong Ġneural Ġbaseline Ġfor Ġthe Ġtask . ĠOur Ġab lation Ġstudies Ġshow Ġthe Ġsignificant Ġcontribution Ġof Ġeach Ġof Ġthe Ġcomponents Ġwe Ġpropose . ĠIn Ġthe Ġfuture Ġwe Ġplan Ġto Ġextend Ġthe Ġworld - state Ġrepresentation , Ġand Ġenable Ġthe Ġmodel Ġto Ġground Ġgeneric Ġand Ġabstract Ġconcepts Ġas Ġwell . ĠWe Ġfurther Ġintend Ġto Ġadd Ġadditional Ġsignals , Ġfor Ġinstance Ġcoming Ġfrom Ġvision Ġ( cf . ĠB IB REF 16 ), Ġfor Ġmore Ġaccurate Ġlocalization . </s> Acknowled gments </s> We Ġthank ĠYo av ĠGoldberg Ġand ĠYo av ĠArt zi , Ġfor Ġtheir Ġadvice Ġand Ġcomments . ĠWe Ġthank Ġthe ĠON LP Ġteam Ġat Ġthe ĠOpen ĠUniversity Ġof ĠIsrael , Ġfor Ġfruitful Ġdiscussions Ġthroughout Ġthe Ġprocess . ĠWe Ġfurther Ġthank Ġthe Ġanonymous Ġreviewers Ġfor Ġtheir Ġhelpful Ġcomments . ĠThis Ġresearch Ġwas Ġpresented Ġat ĠGeorgetown ĠUniversity , ĠCornell ĠUniversity , Ġand ĠTel - Av iv ĠUniversity . ĠThis Ġresearch Ġis Ġsupported Ġby ĠEuropean ĠResearch ĠCouncil , ĠE RC - St G - 2015 Ġscheme , ĠGrant Ġnumber Ġ6 77 352 , Ġand Ġby Ġthe ĠIsrael ĠScience ĠFoundation Ġ( IS F ), ĠGrant Ġnumber Ġ17 39 / 26 , Ġfor Ġwhich Ġwe Ġare Ġgrateful .
Introduction and Background The task of interpreting and following natural language (NL) navigation instructions involves interleaving different signals, at the very least the linguistic utterance and the representation of the world. For example, in turn right on the first intersection, the instruction needs to be interpreted, and a specific object in the world (the intersection) needs to be located in order to execute the instruction. In NL navigation studies, the representation of the world may be provided via visual sensors BIBREF0, BIBREF1, BIBREF2, BIBREF3, BIBREF4 or as a symbolic world representation. This work focuses on navigation based on a symbolic world representation (referred to as a map). Previous datasets for NL navigation based on a symbolic world representation, HCRC BIBREF5, BIBREF6, BIBREF7 and SAIL BIBREF8, BIBREF9, BIBREF10, BIBREF11, BIBREF12, BIBREF13, BIBREF14, BIBREF15 present relatively simple worlds, with a small fixed set of entities known to the navigator in advance. Such representations bypass the great complexity of real urban navigation, which consists of long paths and an abundance of previously unseen entities of different types. In this work we introduce Realistic Urban Navigation (RUN), where we aim to interpret navigation instructions relative to a rich symbolic representation of the world, given by a real dense urban map. To address RUN, we designed and collected a new dataset based on OpenStreetMap, in which we align NL instructions to their corresponding routes. Using Amazon Mechanical Turk, we collected 2515 instructions over 3 regions of Manhattan, all specified (and verified) by (respective) sets of humans workers. This task raises several challenges. First of all, we assume a large world, providing long routes, vulnerable to error propagation; secondly, we assume a rich environment, with entities of various different types, most of which are unseen during training and are not known in advance; finally, we evaluate on the full route intended, rather than on last-position only. We then propose a strong neural baseline for RUN where we augment a standard encoder-decoder architecture with an entity abstraction layer, attention over words and worlds, and a constantly updating world-state. Our experimental results and ablation study show that this architecture is indeed better-equipped to treat grounding in realistic urban settings than standard sequence-to-sequence architectures. Given this RUN benchmark, empirical results, and evaluation procedure, we hope to encourage further investigation into the topic of interpreting NL instructions in realistic and previously unseen urban domains. [1]The task defined by BIBREF6 is of moving between entities only. The RUN Task and Dataset In this work we address the task of following a sequence of NL navigation instructions given in colloquial language based on a dense urban map. The input to the RUN task we define is as follows: (i) a map with rich details divided into tiles, (ii) an explicit starting point, and (iii) a sequence of navigation instructions we henceforth refer to as a navigation paragraph . We refer to each sentence as an instruction, and we assume that following the individual instructions in the paragraph one by one will lead the agent to the intended end-point. The output of RUN is the entire route described by the paragraph, i.e., all coordinates up to and including its end-point, pinned on the map. In order to address RUN we designed and collected a novel dataset, henceforth the RUN dataset, which is based on OpenStreetMap (OSM). The map contains rich layers and an abundance of entities of different types. Each entity is complex and can contain (at least) four labels: name, type, is_building=y/n, and house number. An entity can spread over several tiles. As the maps do not overlap, only very few entities are shared among them. The RUN dataset aligns NL navigation instructions to coordinates of their corresponding route on the OSM map. We collected the RUN dataset using Amazon Mechanical Turk (MTurk), allowing only native English speakers to perform the task. We collected instructions based on three different areas, all in urban, dense parts of Manhattan. The size of each map is $0.5$ $km^{2}$. The dataset contains 2515 navigation instructions (equal to 389 complete paragraphs) paired with their routes. The paragraphs are crowd-sourced from 389 different instructors, of which style and language vary BIBREF18. Our data collection protocol is as follows. First, we asked the MTurk worker to describe a route between two landmarks of their choice. After having described the complete route in NL, the same worker was instructed to pin their described route on the map. This was moderated by showing them the paragraph they narrated, sentence by sentence, so that they have to pin on the map each instruction separately. A worker could only pin routes on street paths. Furthermore, on every turn the worker had to mark an explicit point on the map which marked the direction in which the worker needs to move next. An example of simple individual instructions and their respective route is given in Figure FIGREF5. We then asked a disjoint set of workers (testers) to verify the routes by displaying the starting point of the route, and displaying the instructions in the paragraph sentence-by-sentence. The tester had to pin the final point of the sentence. Each route was tested by three different workers. Testing the routes allowed us to find incorrect routes (paragraphs that don't match an actual path) and discard them. They also provide an estimate of the human performance on the task (Reported in Section SECREF4, Experiments). Having collected the data, we divided the map into tiles, each tile is 11.132 m X 11.132 m. Each tile contains the labels of the entities it displays on the map, such as restaurants, traffic-lights, etc., and the walkable streets in it. Each walkable street is composed of an ordered list of tiles, including a starting tile and an end tile. Table TABREF1 shows statistics over the dataset. Table TABREF2 characterize linguistic phenomena in RUN, categorized according to the catalogue of BIBREF16. Table TABREF3 shows a quantitative comparison of the RUN dataset to previous datasets of map-based navigation. The table underscores some key features of RUN, relative to the previous tasks. RUN contains longer paths and many more entities that are unique, thus appearing for the first time during testing; the size of the map is on a different scale than previous tasks, thus, amplifying the grounding challenge; the number of tiles moved is accordingly larger than in previous datasets, hence increasing the vulnerability to error propagation. Overall, RUN contains challenging linguistic phenomena, at least as in previous work, and a rich environment, with more realistic paths than in previous tasks. Models for RUN We model RUN as a sequence-to-sequence learning problem, where we map a sequence of instructions to a sequence of actions that should be performed in order to pin the actual path on the map. The execution system we provide for the task defines three types of actions: *TURN, *WALK, *END. *TURN is one of the following: right-turn, left-turn, turn-around. The turning move is not necessarily an exact 90-degree turn; the execution system looks for the closest turn option. *WALK is a change of position in the direction we are facing. The streets can be curved, so *WALK is relative to the street that the agent is on. Each street is an ordered-list of tiles, so an action of walking two steps is in fact two actions of *WALK, in the direction the agent is facing. The *END action defines the end of each route. The input consists of an instruction sequence $x_{1:N}$, a map $M$, and a starting point $p_0$ on the map. The output is a sequence of actions $a^*_{1:T}$ to be executed. Where $x_i$ denote sentences, $a_i$ denotes actions, $M$ is the map and $p_0$ is the starting point. Our basic model for RUN is a sequence-to-sequence model similar to the work of BIBREF19 on SAIL, and inspired by BIBREF20. It is based on Conditioned Generation with Attention (CGA). To this model we added an Entity abstraction layer (CGAE) and a World-state representation (CGAEW). It thus consists of six components we describe in turn – Encoder, Decoder, Attention, Entity Abstraction, World-State Processor, Execution-System. The complete architecture is depicted in Fig. FIGREF7. The Encoder takes the sequence of words that assembles a single sentence and encodes it as a vector using a biLSTM BIBREF21. The Decoder is an LSTM generating a sequence of actions that the execution-system can perform, according to weights defined by an Attention layer. The Entity Abstraction component deals with out-of-vocabulary words (OOV). We adopt a similar approach to BIBREF22, BIBREF23, replacing phrases in the sentences which refer to previously unseen entities with variables, prior to delivering the sentence to the Encoder. E.g., Walk from Macy's to 7th street turns into Walk from X1 to Y1. Variables are typed (streets, restaurants, etc.) and are numbered based on their order of occurrence in the sentence. The numbering resets after every utterance, so the model remains with a handful of typed entity-variables. The World-State Processor maps variables to the entities on the map which are mentioned in the sentence. The world-state representation consists of two vectors, one representing the entities at the current position, and one representing the entities in the path ahead. The Attention layer considers the sequence of encoded words as well as current world-state, and provides weights on the words for each of the decoder steps. In both training and testing, the Execution-System executes each action separately to produce the next position. Experiments We evaluate our model on RUN and assess the contribution of the particular components that we added on top of the standard CGA model. We train the model using a negative log-likelihood loss, and used Adam BIBREF24 optimization. For weights initialization we rely on BIBREF25. We used a grid search to validate the hyper-parameters. The model converged at around 30 epochs and produced good results with 0.9 drop-out and a beam of size 4. During inference, we seek the best candidate path using beam-search and normalize the scores of the sequences according to BIBREF26. We follow the evaluation methodology defined by BIBREF9 for SAIL where we use three-fold validation, and in each fold, we use two maps for training (90%) and validation (10%) and test on the third one. We report a sized-weighted average test result. For all models we report the accuracy per single sentences and full paragraphs. Success is measured by generating an exact route, not striding away from the path. The last position on the path should be within five tile euclidean distance from the intended destination, as the position explained in the instruction might not be specific enough for one tile. In single-sentences, the last position should also be facing the correct direction. We provide three simple baselines for the RUN task: (1) NO-MOVE: the only position considered is the starting point; (2) RANDOM: As in BIBREF4, turn to a randomly selected heading, then execute a number of *WALK actions of an average route; (3) JUMP: at each sentence, extract entities from the map and move between them in the order they appear. If the *WALK action is invalid we take a random *TURN action. Table TABREF8 shows the results for the baseline models as well as the HUMAN measured performance on the task. The human performance provides an upper bound for the RUN task performance, while the simple baselines provide lower bounds. The best baseline model is NO-MOVE, reaching an accuracy of 30.3% on single sentences and 0.3 on complete paragraphs. For the HUMAN case, paragraph accuracy reaches above 80. Table TABREF8 shows the results of our model as an ablation study, and Table TABREF9 shows typical errors of each variant. We see that CGAE outperforms CGA, as the swap of entities with variables lowers the complexity of the language that the model needs to learn, allowing the model to effectively cope with unseen entities at test time. We further found that, in many cases, CGAE produces the right type of action, but it does not produce enough of it to reach the intended destination. We attribute these errors to the absence of a world-state representation, resulting in an incapability to ground instructions to specific locations. CGAEW improves upon CGAE as the existence of world-state in the score of the attention layer allows the model better learn the grounding of entities in the instruction to the map. However our best model still fails on features not captured by our world-state: abstract unmarked entities such as blocks, intersections, etc, and generic entities such as traffic-lights (Tab. TABREF9). Conclusion We introduce RUN, a new task and dataset for NL navigation in realistic urban environments. We collected (and verified) NL navigation instructions aligned with actual paths, and propose a strong neural baseline for the task. Our ablation studies show the significant contribution of each of the components we propose. In the future we plan to extend the world-state representation, and enable the model to ground generic and abstract concepts as well. We further intend to add additional signals, for instance coming from vision (cf. BIBREF16), for more accurate localization. Acknowledgments We thank Yoav Goldberg and Yoav Artzi, for their advice and comments. We thank the ONLP team at the Open University of Israel, for fruitful discussions throughout the process. We further thank the anonymous reviewers for their helpful comments. This research was presented at Georgetown University, Cornell University, and Tel-Aviv University. This research is supported by European Research Council, ERC-StG-2015 scheme, Grant number 677352, and by the Israel Science Foundation (ISF), Grant number 1739/26, for which we are grateful.
How well did the baseline perform?
bd419f4094186a5ce74ba6ac1622b24e29e553f4
How Ġwell Ġdid Ġthe Ġbaseline Ġperform ?
acc uracy Ġof Ġ30 . 3 % Ġon Ġsingle Ġsentences Ġand Ġ0 . 3 Ġon Ġcomplete Ġparagraphs
<s> How Ġwell Ġdid Ġthe Ġbaseline Ġperform ? </s> Introduction Ġand ĠBackground </s> The Ġtask Ġof Ġinterpreting Ġand Ġfollowing Ġnatural Ġlanguage Ġ( NL ) Ġnavigation Ġinstructions Ġinvolves Ġinter le aving Ġdifferent Ġsignals , Ġat Ġthe Ġvery Ġleast Ġthe Ġlinguistic Ġutter ance Ġand Ġthe Ġrepresentation Ġof Ġthe Ġworld . ĠFor Ġexample , Ġin Ġturn Ġright Ġon Ġthe Ġfirst Ġintersection , Ġthe Ġinstruction Ġneeds Ġto Ġbe Ġinterpreted , Ġand Ġa Ġspecific Ġobject Ġin Ġthe Ġworld Ġ( the Ġintersection ) Ġneeds Ġto Ġbe Ġlocated Ġin Ġorder Ġto Ġexecute Ġthe Ġinstruction . ĠIn ĠNL Ġnavigation Ġstudies , Ġthe Ġrepresentation Ġof Ġthe Ġworld Ġmay Ġbe Ġprovided Ġvia Ġvisual Ġsensors ĠB IB REF 0 , ĠB IB REF 1 , ĠB IB REF 2 , ĠB IB REF 3 , ĠB IB REF 4 Ġor Ġas Ġa Ġsymbolic Ġworld Ġrepresentation . ĠThis Ġwork Ġfocuses Ġon Ġnavigation Ġbased Ġon Ġa Ġsymbolic Ġworld Ġrepresentation Ġ( re ferred Ġto Ġas Ġa Ġmap ). </s> Previous Ġdatasets Ġfor ĠNL Ġnavigation Ġbased Ġon Ġa Ġsymbolic Ġworld Ġrepresentation , ĠHC RC ĠB IB REF 5 , ĠB IB REF 6 , ĠB IB REF 7 Ġand ĠSA IL ĠB IB REF 8 , ĠB IB REF 9 , ĠB IB REF 10 , ĠB IB REF 11 , ĠB IB REF 12 , ĠB IB REF 13 , ĠB IB REF 14 , ĠB IB REF 15 Ġpresent Ġrelatively Ġsimple Ġworlds , Ġwith Ġa Ġsmall Ġfixed Ġset Ġof Ġentities Ġknown Ġto Ġthe Ġnavig ator Ġin Ġadvance . ĠSuch Ġrepresentations Ġbypass Ġthe Ġgreat Ġcomplexity Ġof Ġreal Ġurban Ġnavigation , Ġwhich Ġconsists Ġof Ġlong Ġpaths Ġand Ġan Ġabundance Ġof Ġpreviously Ġunseen Ġentities Ġof Ġdifferent Ġtypes . </s> In Ġthis Ġwork Ġwe Ġintroduce ĠReal istic ĠUrban ĠNavigation Ġ( R UN ), Ġwhere Ġwe Ġaim Ġto Ġinterpret Ġnavigation Ġinstructions Ġrelative Ġto Ġa Ġrich Ġsymbolic Ġrepresentation Ġof Ġthe Ġworld , Ġgiven Ġby Ġa Ġreal Ġdense Ġurban Ġmap . ĠTo Ġaddress ĠRUN , Ġwe Ġdesigned Ġand Ġcollected Ġa Ġnew Ġdataset Ġbased Ġon ĠOpen Street Map , Ġin Ġwhich Ġwe Ġalign ĠNL Ġinstructions Ġto Ġtheir Ġcorresponding Ġroutes . ĠUsing ĠAmazon ĠMechanical ĠTurk , Ġwe Ġcollected Ġ25 15 Ġinstructions Ġover Ġ3 Ġregions Ġof ĠManhattan , Ġall Ġspecified Ġ( and Ġverified ) Ġby Ġ( respective ) Ġsets Ġof Ġhumans Ġworkers . ĠThis Ġtask Ġraises Ġseveral Ġchallenges . ĠFirst Ġof Ġall , Ġwe Ġassume Ġa Ġlarge Ġworld , Ġproviding Ġlong Ġroutes , Ġvulnerable Ġto Ġerror Ġpropagation ; Ġsecondly , Ġwe Ġassume Ġa Ġrich Ġenvironment , Ġwith Ġentities Ġof Ġvarious Ġdifferent Ġtypes , Ġmost Ġof Ġwhich Ġare Ġunseen Ġduring Ġtraining Ġand Ġare Ġnot Ġknown Ġin Ġadvance ; Ġfinally , Ġwe Ġevaluate Ġon Ġthe Ġfull Ġroute Ġintended , Ġrather Ġthan Ġon Ġlast - position Ġonly . </s> We Ġthen Ġpropose Ġa Ġstrong Ġneural Ġbaseline Ġfor ĠRUN Ġwhere Ġwe Ġaugment Ġa Ġstandard Ġenc oder - dec oder Ġarchitecture Ġwith Ġan Ġentity Ġabstraction Ġlayer , Ġattention Ġover Ġwords Ġand Ġworlds , Ġand Ġa Ġconstantly Ġupdating Ġworld - state . ĠOur Ġexperimental Ġresults Ġand Ġab lation Ġstudy Ġshow Ġthat Ġthis Ġarchitecture Ġis Ġindeed Ġbetter - equipped Ġto Ġtreat Ġgrounding Ġin Ġrealistic Ġurban Ġsettings Ġthan Ġstandard Ġsequence - to - sequence Ġarchitectures . ĠGiven Ġthis ĠRUN Ġbenchmark , Ġempirical Ġresults , Ġand Ġevaluation Ġprocedure , Ġwe Ġhope Ġto Ġencourage Ġfurther Ġinvestigation Ġinto Ġthe Ġtopic Ġof Ġinterpreting ĠNL Ġinstructions Ġin Ġrealistic Ġand Ġpreviously Ġunseen Ġurban Ġdomains . </s> [ 1 ] The Ġtask Ġdefined Ġby ĠB IB REF 6 Ġis Ġof Ġmoving Ġbetween Ġentities Ġonly . </s> The ĠRUN ĠTask Ġand ĠDat as et </s> In Ġthis Ġwork Ġwe Ġaddress Ġthe Ġtask Ġof Ġfollowing Ġa Ġsequence Ġof ĠNL Ġnavigation Ġinstructions Ġgiven Ġin Ġcoll oqu ial Ġlanguage Ġbased Ġon Ġa Ġdense Ġurban Ġmap . </s> The Ġinput Ġto Ġthe ĠRUN Ġtask Ġwe Ġdefine Ġis Ġas Ġfollows : Ġ( i ) Ġa Ġmap Ġwith Ġrich Ġdetails Ġdivided Ġinto Ġtiles , Ġ( ii ) Ġan Ġexplicit Ġstarting Ġpoint , Ġand Ġ( iii ) Ġa Ġsequence Ġof Ġnavigation Ġinstructions Ġwe Ġhence forth Ġrefer Ġto Ġas Ġa Ġnavigation Ġparagraph Ġ. ĠWe Ġrefer Ġto Ġeach Ġsentence Ġas Ġan Ġinstruction , Ġand Ġwe Ġassume Ġthat Ġfollowing Ġthe Ġindividual Ġinstructions Ġin Ġthe Ġparagraph Ġone Ġby Ġone Ġwill Ġlead Ġthe Ġagent Ġto Ġthe Ġintended Ġend - point . ĠThe Ġoutput Ġof ĠRUN Ġis Ġthe Ġentire Ġroute Ġdescribed Ġby Ġthe Ġparagraph , Ġi . e ., Ġall Ġcoordinates Ġup Ġto Ġand Ġincluding Ġits Ġend - point , Ġpinned Ġon Ġthe Ġmap . </s> In Ġorder Ġto Ġaddress ĠRUN Ġwe Ġdesigned Ġand Ġcollected Ġa Ġnovel Ġdataset , Ġhence forth Ġthe ĠRUN Ġdataset , Ġwhich Ġis Ġbased Ġon ĠOpen Street Map Ġ( OS M ). ĠThe Ġmap Ġcontains Ġrich Ġlayers Ġand Ġan Ġabundance Ġof Ġentities Ġof Ġdifferent Ġtypes . ĠEach Ġentity Ġis Ġcomplex Ġand Ġcan Ġcontain Ġ( at Ġleast ) Ġfour Ġlabels : Ġname , Ġtype , Ġis _ building = y / n , Ġand Ġhouse Ġnumber . ĠAn Ġentity Ġcan Ġspread Ġover Ġseveral Ġtiles . ĠAs Ġthe Ġmaps Ġdo Ġnot Ġoverlap , Ġonly Ġvery Ġfew Ġentities Ġare Ġshared Ġamong Ġthem . ĠThe ĠRUN Ġdataset Ġalign s ĠNL Ġnavigation Ġinstructions Ġto Ġcoordinates Ġof Ġtheir Ġcorresponding Ġroute Ġon Ġthe ĠOS M Ġmap . </s> We Ġcollected Ġthe ĠRUN Ġdataset Ġusing ĠAmazon ĠMechanical ĠTurk Ġ( MT ur k ), Ġallowing Ġonly Ġnative ĠEnglish Ġspeakers Ġto Ġperform Ġthe Ġtask . ĠWe Ġcollected Ġinstructions Ġbased Ġon Ġthree Ġdifferent Ġareas , Ġall Ġin Ġurban , Ġdense Ġparts Ġof ĠManhattan . ĠThe Ġsize Ġof Ġeach Ġmap Ġis Ġ$ 0 . 5 $ Ġ$ km ^{ 2 } $. ĠThe Ġdataset Ġcontains Ġ25 15 Ġnavigation Ġinstructions Ġ( equal Ġto Ġ389 Ġcomplete Ġparagraphs ) Ġpaired Ġwith Ġtheir Ġroutes . ĠThe Ġparagraphs Ġare Ġcrowd - s ourced Ġfrom Ġ389 Ġdifferent Ġinstructors , Ġof Ġwhich Ġstyle Ġand Ġlanguage Ġvary ĠB IB REF 18 . </s> Our Ġdata Ġcollection Ġprotocol Ġis Ġas Ġfollows . ĠFirst , Ġwe Ġasked Ġthe ĠM Tur k Ġworker Ġto Ġdescribe Ġa Ġroute Ġbetween Ġtwo Ġlandmarks Ġof Ġtheir Ġchoice . ĠAfter Ġhaving Ġdescribed Ġthe Ġcomplete Ġroute Ġin ĠNL , Ġthe Ġsame Ġworker Ġwas Ġinstructed Ġto Ġpin Ġtheir Ġdescribed Ġroute Ġon Ġthe Ġmap . ĠThis Ġwas Ġmoder ated Ġby Ġshowing Ġthem Ġthe Ġparagraph Ġthey Ġnarrated , Ġsentence Ġby Ġsentence , Ġso Ġthat Ġthey Ġhave Ġto Ġpin Ġon Ġthe Ġmap Ġeach Ġinstruction Ġseparately . ĠA Ġworker Ġcould Ġonly Ġpin Ġroutes Ġon Ġstreet Ġpaths . ĠFurthermore , Ġon Ġevery Ġturn Ġthe Ġworker Ġhad Ġto Ġmark Ġan Ġexplicit Ġpoint Ġon Ġthe Ġmap Ġwhich Ġmarked Ġthe Ġdirection Ġin Ġwhich Ġthe Ġworker Ġneeds Ġto Ġmove Ġnext . ĠAn Ġexample Ġof Ġsimple Ġindividual Ġinstructions Ġand Ġtheir Ġrespective Ġroute Ġis Ġgiven Ġin ĠFigure ĠFIG REF 5 . </s> We Ġthen Ġasked Ġa Ġdis j oint Ġset Ġof Ġworkers Ġ( testers ) Ġto Ġverify Ġthe Ġroutes Ġby Ġdisplaying Ġthe Ġstarting Ġpoint Ġof Ġthe Ġroute , Ġand Ġdisplaying Ġthe Ġinstructions Ġin Ġthe Ġparagraph Ġsentence - by - sent ence . ĠThe Ġt ester Ġhad Ġto Ġpin Ġthe Ġfinal Ġpoint Ġof Ġthe Ġsentence . ĠEach Ġroute Ġwas Ġtested Ġby Ġthree Ġdifferent Ġworkers . ĠTesting Ġthe Ġroutes Ġallowed Ġus Ġto Ġfind Ġincorrect Ġroutes Ġ( paragraph s Ġthat Ġdon 't Ġmatch Ġan Ġactual Ġpath ) Ġand Ġdiscard Ġthem . ĠThey Ġalso Ġprovide Ġan Ġestimate Ġof Ġthe Ġhuman Ġperformance Ġon Ġthe Ġtask Ġ( Rep orted Ġin ĠSection ĠSEC REF 4 , ĠExper iments ). </s> Having Ġcollected Ġthe Ġdata , Ġwe Ġdivided Ġthe Ġmap Ġinto Ġtiles , Ġeach Ġtile Ġis Ġ11 . 132 Ġm ĠX Ġ11 . 132 Ġm . ĠEach Ġtile Ġcontains Ġthe Ġlabels Ġof Ġthe Ġentities Ġit Ġdisplays Ġon Ġthe Ġmap , Ġsuch Ġas Ġrestaurants , Ġtraffic - lights , Ġetc ., Ġand Ġthe Ġwalk able Ġstreets Ġin Ġit . ĠEach Ġwalk able Ġstreet Ġis Ġcomposed Ġof Ġan Ġordered Ġlist Ġof Ġtiles , Ġincluding Ġa Ġstarting Ġtile Ġand Ġan Ġend Ġtile . ĠTable ĠT AB REF 1 Ġshows Ġstatistics Ġover Ġthe Ġdataset . ĠTable ĠT AB REF 2 Ġcharacterize Ġlinguistic Ġphenomena Ġin ĠRUN , Ġcategorized Ġaccording Ġto Ġthe Ġcatalogue Ġof ĠB IB REF 16 . ĠTable ĠT AB REF 3 Ġshows Ġa Ġquantitative Ġcomparison Ġof Ġthe ĠRUN Ġdataset Ġto Ġprevious Ġdatasets Ġof Ġmap - based Ġnavigation . ĠThe Ġtable Ġunderscores Ġsome Ġkey Ġfeatures Ġof ĠRUN , Ġrelative Ġto Ġthe Ġprevious Ġtasks . ĠRUN Ġcontains Ġlonger Ġpaths Ġand Ġmany Ġmore Ġentities Ġthat Ġare Ġunique , Ġthus Ġappearing Ġfor Ġthe Ġfirst Ġtime Ġduring Ġtesting ; Ġthe Ġsize Ġof Ġthe Ġmap Ġis Ġon Ġa Ġdifferent Ġscale Ġthan Ġprevious Ġtasks , Ġthus , Ġampl ifying Ġthe Ġgrounding Ġchallenge ; Ġthe Ġnumber Ġof Ġtiles Ġmoved Ġis Ġaccordingly Ġlarger Ġthan Ġin Ġprevious Ġdatasets , Ġhence Ġincreasing Ġthe Ġvulnerability Ġto Ġerror Ġpropagation . </s> Overall , ĠRUN Ġcontains Ġchallenging Ġlinguistic Ġphenomena , Ġat Ġleast Ġas Ġin Ġprevious Ġwork , Ġand Ġa Ġrich Ġenvironment , Ġwith Ġmore Ġrealistic Ġpaths Ġthan Ġin Ġprevious Ġtasks . </s> Mod els Ġfor ĠRUN </s> We Ġmodel ĠRUN Ġas Ġa Ġsequence - to - sequence Ġlearning Ġproblem , Ġwhere Ġwe Ġmap Ġa Ġsequence Ġof Ġinstructions Ġto Ġa Ġsequence Ġof Ġactions Ġthat Ġshould Ġbe Ġperformed Ġin Ġorder Ġto Ġpin Ġthe Ġactual Ġpath Ġon Ġthe Ġmap . ĠThe Ġexecution Ġsystem Ġwe Ġprovide Ġfor Ġthe Ġtask Ġdefines Ġthree Ġtypes Ġof Ġactions : Ġ* T URN , Ġ* W ALK , Ġ* END . Ġ* T URN Ġis Ġone Ġof Ġthe Ġfollowing : Ġright - turn , Ġleft - turn , Ġturn - around . ĠThe Ġturning Ġmove Ġis Ġnot Ġnecessarily Ġan Ġexact Ġ90 - degree Ġturn ; Ġthe Ġexecution Ġsystem Ġlooks Ġfor Ġthe Ġclosest Ġturn Ġoption . Ġ* W ALK Ġis Ġa Ġchange Ġof Ġposition Ġin Ġthe Ġdirection Ġwe Ġare Ġfacing . ĠThe Ġstreets Ġcan Ġbe Ġcurved , Ġso Ġ* W ALK Ġis Ġrelative Ġto Ġthe Ġstreet Ġthat Ġthe Ġagent Ġis Ġon . ĠEach Ġstreet Ġis Ġan Ġordered - list Ġof Ġtiles , Ġso Ġan Ġaction Ġof Ġwalking Ġtwo Ġsteps Ġis Ġin Ġfact Ġtwo Ġactions Ġof Ġ* W ALK , Ġin Ġthe Ġdirection Ġthe Ġagent Ġis Ġfacing . ĠThe Ġ* END Ġaction Ġdefines Ġthe Ġend Ġof Ġeach Ġroute . ĠThe Ġinput Ġconsists Ġof Ġan Ġinstruction Ġsequence Ġ$ x _{ 1 : N } $, Ġa Ġmap Ġ$ M $, Ġand Ġa Ġstarting Ġpoint Ġ$ p _ 0 $ Ġon Ġthe Ġmap . ĠThe Ġoutput Ġis Ġa Ġsequence Ġof Ġactions Ġ$ a ^ * _{ 1 : T } $ Ġto Ġbe Ġexecuted . </s> Where Ġ$ x _ i $ Ġdenote Ġsentences , Ġ$ a _ i $ Ġdenotes Ġactions , Ġ$ M $ Ġis Ġthe Ġmap Ġand Ġ$ p _ 0 $ Ġis Ġthe Ġstarting Ġpoint . </s> Our Ġbasic Ġmodel Ġfor ĠRUN Ġis Ġa Ġsequence - to - sequence Ġmodel Ġsimilar Ġto Ġthe Ġwork Ġof ĠB IB REF 19 Ġon ĠSA IL , Ġand Ġinspired Ġby ĠB IB REF 20 . ĠIt Ġis Ġbased Ġon ĠCondition ed ĠGeneration Ġwith ĠAttention Ġ( C GA ). ĠTo Ġthis Ġmodel Ġwe Ġadded Ġan ĠEntity Ġabstraction Ġlayer Ġ( C GA E ) Ġand Ġa ĠWorld - state Ġrepresentation Ġ( C GA EW ). ĠIt Ġthus Ġconsists Ġof Ġsix Ġcomponents Ġwe Ġdescribe Ġin Ġturn ĠâĢĵ ĠEnc oder , ĠDecoder , ĠAttention , ĠEntity ĠAb st raction , ĠWorld - State ĠProcessor , ĠExecution - System . ĠThe Ġcomplete Ġarchitecture Ġis Ġdepicted Ġin ĠFig . ĠFIG REF 7 . </s> The ĠEnc oder Ġtakes Ġthe Ġsequence Ġof Ġwords Ġthat Ġassemb les Ġa Ġsingle Ġsentence Ġand Ġenc odes Ġit Ġas Ġa Ġvector Ġusing Ġa Ġbi L ST M ĠB IB REF 21 . ĠThe ĠDecoder Ġis Ġan ĠL ST M Ġgenerating Ġa Ġsequence Ġof Ġactions Ġthat Ġthe Ġexecution - system Ġcan Ġperform , Ġaccording Ġto Ġweights Ġdefined Ġby Ġan ĠAttention Ġlayer . ĠThe ĠEntity ĠAb st raction Ġcomponent Ġdeals Ġwith Ġout - of - voc abulary Ġwords Ġ( OO V ). ĠWe Ġadopt Ġa Ġsimilar Ġapproach Ġto ĠB IB REF 22 , ĠB IB REF 23 , Ġreplacing Ġphrases Ġin Ġthe Ġsentences Ġwhich Ġrefer Ġto Ġpreviously Ġunseen Ġentities Ġwith Ġvariables , Ġprior Ġto Ġdelivering Ġthe Ġsentence Ġto Ġthe ĠEnc oder . ĠE . g ., ĠWalk Ġfrom ĠMacy 's Ġto Ġ7 th Ġstreet Ġturns Ġinto ĠWalk Ġfrom ĠX 1 Ġto ĠY 1 . ĠVari ables Ġare Ġtyped Ġ( stre ets , Ġrestaurants , Ġetc .) Ġand Ġare Ġnumbered Ġbased Ġon Ġtheir Ġorder Ġof Ġoccurrence Ġin Ġthe Ġsentence . ĠThe Ġnumbering Ġres ets Ġafter Ġevery Ġutter ance , Ġso Ġthe Ġmodel Ġremains Ġwith Ġa Ġhandful Ġof Ġtyped Ġentity - vari ables . ĠThe ĠWorld - State ĠProcessor Ġmaps Ġvariables Ġto Ġthe Ġentities Ġon Ġthe Ġmap Ġwhich Ġare Ġmentioned Ġin Ġthe Ġsentence . ĠThe Ġworld - state Ġrepresentation Ġconsists Ġof Ġtwo Ġvectors , Ġone Ġrepresenting Ġthe Ġentities Ġat Ġthe Ġcurrent Ġposition , Ġand Ġone Ġrepresenting Ġthe Ġentities Ġin Ġthe Ġpath Ġahead . ĠThe ĠAttention Ġlayer Ġconsiders Ġthe Ġsequence Ġof Ġencoded Ġwords Ġas Ġwell Ġas Ġcurrent Ġworld - state , Ġand Ġprovides Ġweights Ġon Ġthe Ġwords Ġfor Ġeach Ġof Ġthe Ġdec oder Ġsteps . ĠIn Ġboth Ġtraining Ġand Ġtesting , Ġthe ĠExecution - System Ġexecutes Ġeach Ġaction Ġseparately Ġto Ġproduce Ġthe Ġnext Ġposition . </s> Exper iments </s> We Ġevaluate Ġour Ġmodel Ġon ĠRUN Ġand Ġassess Ġthe Ġcontribution Ġof Ġthe Ġparticular Ġcomponents Ġthat Ġwe Ġadded Ġon Ġtop Ġof Ġthe Ġstandard ĠC GA Ġmodel . </s> We Ġtrain Ġthe Ġmodel Ġusing Ġa Ġnegative Ġlog - like lihood Ġloss , Ġand Ġused ĠAdam ĠB IB REF 24 Ġoptimization . ĠFor Ġweights Ġinitialization Ġwe Ġrely Ġon ĠB IB REF 25 . ĠWe Ġused Ġa Ġgrid Ġsearch Ġto Ġvalidate Ġthe Ġhyper - param eters . ĠThe Ġmodel Ġconver ged Ġat Ġaround Ġ30 Ġepoch s Ġand Ġproduced Ġgood Ġresults Ġwith Ġ0 . 9 Ġdrop - out Ġand Ġa Ġbeam Ġof Ġsize Ġ4 . ĠDuring Ġinference , Ġwe Ġseek Ġthe Ġbest Ġcandidate Ġpath Ġusing Ġbeam - search Ġand Ġnormal ize Ġthe Ġscores Ġof Ġthe Ġsequences Ġaccording Ġto ĠB IB REF 26 . </s> We Ġfollow Ġthe Ġevaluation Ġmethodology Ġdefined Ġby ĠB IB REF 9 Ġfor ĠSA IL Ġwhere Ġwe Ġuse Ġthree - fold Ġvalidation , Ġand Ġin Ġeach Ġfold , Ġwe Ġuse Ġtwo Ġmaps Ġfor Ġtraining Ġ( 90 %) Ġand Ġvalidation Ġ( 10 %) Ġand Ġtest Ġon Ġthe Ġthird Ġone . ĠWe Ġreport Ġa Ġsized - weight ed Ġaverage Ġtest Ġresult . ĠFor Ġall Ġmodels Ġwe Ġreport Ġthe Ġaccuracy Ġper Ġsingle Ġsentences Ġand Ġfull Ġparagraphs . ĠSuccess Ġis Ġmeasured Ġby Ġgenerating Ġan Ġexact Ġroute , Ġnot Ġstr iding Ġaway Ġfrom Ġthe Ġpath . ĠThe Ġlast Ġposition Ġon Ġthe Ġpath Ġshould Ġbe Ġwithin Ġfive Ġtile Ġe ucl ide an Ġdistance Ġfrom Ġthe Ġintended Ġdestination , Ġas Ġthe Ġposition Ġexplained Ġin Ġthe Ġinstruction Ġmight Ġnot Ġbe Ġspecific Ġenough Ġfor Ġone Ġtile . ĠIn Ġsingle - sent ences , Ġthe Ġlast Ġposition Ġshould Ġalso Ġbe Ġfacing Ġthe Ġcorrect Ġdirection . </s> We Ġprovide Ġthree Ġsimple Ġbas elines Ġfor Ġthe ĠRUN Ġtask : Ġ( 1 ) ĠNO - MO VE : Ġthe Ġonly Ġposition Ġconsidered Ġis Ġthe Ġstarting Ġpoint ; Ġ( 2 ) ĠRAND OM : ĠAs Ġin ĠB IB REF 4 , Ġturn Ġto Ġa Ġrandomly Ġselected Ġheading , Ġthen Ġexecute Ġa Ġnumber Ġof Ġ* W ALK Ġactions Ġof Ġan Ġaverage Ġroute ; Ġ( 3 ) ĠJ UMP : Ġat Ġeach Ġsentence , Ġextract Ġentities Ġfrom Ġthe Ġmap Ġand Ġmove Ġbetween Ġthem Ġin Ġthe Ġorder Ġthey Ġappear . ĠIf Ġthe Ġ* W ALK Ġaction Ġis Ġinvalid Ġwe Ġtake Ġa Ġrandom Ġ* T URN Ġaction . </s> Table ĠT AB REF 8 Ġshows Ġthe Ġresults Ġfor Ġthe Ġbaseline Ġmodels Ġas Ġwell Ġas Ġthe ĠHUM AN Ġmeasured Ġperformance Ġon Ġthe Ġtask . ĠThe Ġhuman Ġperformance Ġprovides Ġan Ġupper Ġbound Ġfor Ġthe ĠRUN Ġtask Ġperformance , Ġwhile Ġthe Ġsimple Ġbas elines Ġprovide Ġlower Ġbounds . ĠThe Ġbest Ġbaseline Ġmodel Ġis ĠNO - MO VE , Ġreaching Ġan Ġaccuracy Ġof Ġ30 . 3 % Ġon Ġsingle Ġsentences Ġand Ġ0 . 3 Ġon Ġcomplete Ġparagraphs . ĠFor Ġthe ĠHUM AN Ġcase , Ġparagraph Ġaccuracy Ġreaches Ġabove Ġ80 . </s> Table ĠT AB REF 8 Ġshows Ġthe Ġresults Ġof Ġour Ġmodel Ġas Ġan Ġab lation Ġstudy , Ġand ĠTable ĠT AB REF 9 Ġshows Ġtypical Ġerrors Ġof Ġeach Ġvariant . ĠWe Ġsee Ġthat ĠC GA E Ġoutper forms ĠC GA , Ġas Ġthe Ġswap Ġof Ġentities Ġwith Ġvariables Ġlowers Ġthe Ġcomplexity Ġof Ġthe Ġlanguage Ġthat Ġthe Ġmodel Ġneeds Ġto Ġlearn , Ġallowing Ġthe Ġmodel Ġto Ġeffectively Ġcope Ġwith Ġunseen Ġentities Ġat Ġtest Ġtime . ĠWe Ġfurther Ġfound Ġthat , Ġin Ġmany Ġcases , ĠC GA E Ġproduces Ġthe Ġright Ġtype Ġof Ġaction , Ġbut Ġit Ġdoes Ġnot Ġproduce Ġenough Ġof Ġit Ġto Ġreach Ġthe Ġintended Ġdestination . ĠWe Ġattribute Ġthese Ġerrors Ġto Ġthe Ġabsence Ġof Ġa Ġworld - state Ġrepresentation , Ġresulting Ġin Ġan Ġincap ability Ġto Ġground Ġinstructions Ġto Ġspecific Ġlocations . ĠC GA EW Ġimproves Ġupon ĠC GA E Ġas Ġthe Ġexistence Ġof Ġworld - state Ġin Ġthe Ġscore Ġof Ġthe Ġattention Ġlayer Ġallows Ġthe Ġmodel Ġbetter Ġlearn Ġthe Ġgrounding Ġof Ġentities Ġin Ġthe Ġinstruction Ġto Ġthe Ġmap . ĠHowever Ġour Ġbest Ġmodel Ġstill Ġfails Ġon Ġfeatures Ġnot Ġcaptured Ġby Ġour Ġworld - state : Ġabstract Ġunmarked Ġentities Ġsuch Ġas Ġblocks , Ġintersections , Ġetc , Ġand Ġgeneric Ġentities Ġsuch Ġas Ġtraffic - lights Ġ( Tab . ĠT AB REF 9 ). </s> Conclusion </s> We Ġintroduce ĠRUN , Ġa Ġnew Ġtask Ġand Ġdataset Ġfor ĠNL Ġnavigation Ġin Ġrealistic Ġurban Ġenvironments . ĠWe Ġcollected Ġ( and Ġverified ) ĠNL Ġnavigation Ġinstructions Ġaligned Ġwith Ġactual Ġpaths , Ġand Ġpropose Ġa Ġstrong Ġneural Ġbaseline Ġfor Ġthe Ġtask . ĠOur Ġab lation Ġstudies Ġshow Ġthe Ġsignificant Ġcontribution Ġof Ġeach Ġof Ġthe Ġcomponents Ġwe Ġpropose . ĠIn Ġthe Ġfuture Ġwe Ġplan Ġto Ġextend Ġthe Ġworld - state Ġrepresentation , Ġand Ġenable Ġthe Ġmodel Ġto Ġground Ġgeneric Ġand Ġabstract Ġconcepts Ġas Ġwell . ĠWe Ġfurther Ġintend Ġto Ġadd Ġadditional Ġsignals , Ġfor Ġinstance Ġcoming Ġfrom Ġvision Ġ( cf . ĠB IB REF 16 ), Ġfor Ġmore Ġaccurate Ġlocalization . </s> Acknowled gments </s> We Ġthank ĠYo av ĠGoldberg Ġand ĠYo av ĠArt zi , Ġfor Ġtheir Ġadvice Ġand Ġcomments . ĠWe Ġthank Ġthe ĠON LP Ġteam Ġat Ġthe ĠOpen ĠUniversity Ġof ĠIsrael , Ġfor Ġfruitful Ġdiscussions Ġthroughout Ġthe Ġprocess . ĠWe Ġfurther Ġthank Ġthe Ġanonymous Ġreviewers Ġfor Ġtheir Ġhelpful Ġcomments . ĠThis Ġresearch Ġwas Ġpresented Ġat ĠGeorgetown ĠUniversity , ĠCornell ĠUniversity , Ġand ĠTel - Av iv ĠUniversity . ĠThis Ġresearch Ġis Ġsupported Ġby ĠEuropean ĠResearch ĠCouncil , ĠE RC - St G - 2015 Ġscheme , ĠGrant Ġnumber Ġ6 77 352 , Ġand Ġby Ġthe ĠIsrael ĠScience ĠFoundation Ġ( IS F ), ĠGrant Ġnumber Ġ17 39 / 26 , Ġfor Ġwhich Ġwe Ġare Ġgrateful .