¡!DOCTYPE HTML PUBLIC¿ ¡html¿¡head¿¡title¿ EPTCS 370: Games, Automata, Logics
and Formal Verification ¡/title¿ ¡style¿ body width: 90background: #ffee88;
margin: 0 auto; text-align: justify; margin-bottom: 2em;

hr.sep border-top: solid 1px #cc0000; p.indent text-indent: 1.5em; margin-
bottom: 0pt; margin-top: 0pt; a text-decoration: none; td.fill border-bottom:
dotted 1px #cc0000; ¡/style¿ ¡script type=”text/javascript”¿ function
changeText() document.getElementById(’sitemap’).innerHTML = ’¡table
width=100’¡tbody¿¡tr¿¡td align=”left”¿’+ ’¡font size=-1¿’+ ’¡b¿DOI:¡/b¿ ¡a
href=”http://dx.doi.org/10.4204/EPTCS.370”¿’+ ’10.4204/EPTCS.370¡/a¿¡br¿’+
’¡b¿ISSN:¡/b¿
2075-2180¡/font¿¡br¿¡br¿¡br¿¡br¿¡br¿¡br¿¡br¿¡br¿¡br¿¡br¿¡br¿¡br¿’+ ’¡/td¿¡td
align=”left” bgcolor=”#ffffff”¿¡ul¿’+ ’¡li¿¡a
href=”http://published.eptcs.org/” target=”_top”¿Published Volumes¡/a¿’+
’¡li¿¡a href=”http://forthcoming.eptcs.org/” target=”_top”¿Forthcoming
Volumes¡/a¿’+ ’¡li¿¡a href=”http://eptcs.org/” target=”_top”¿About EPTCS¡/a¿’+
’¡li¿¡a href=”http://editors.eptcs.org/” target=”_top”¿Editorial Board¡/a¿’+
’¡li¿¡a href=”http://hardcopy.eptcs.org/” target=”_top”¿Ordering
Hardcopy¡/a¿’+ ’¡li¿¡a href=”http://info.eptcs.org/” target=”_top”¿Information
for ’+ ’Authors and Event Organisers¡/a¿’+ ’ ¡ul¿’+ ’ ¡li¿ ¡a
href=”http://style.eptcs.org/” target=”_top”¿LaTeX style file and’+ ’
formatting instructions¡/a¿’+ ’ ¡ul¿’+ ’ ¡li¿¡a
href=”http://eptcs.web.cse.unsw.edu.au/eptcsstyle.zip”
target=”_top”¿eptcsstyle.zip¡/a¿’+ ’ ¡/ul¿’+ ’ ¡li¿ ¡a
href=”http://copyright.eptcs.org/” target=”_top”¿Copyright¡/a¿’+ ’ ¡/ul¿’+
’¡li¿¡a href=”http://apply.eptcs.org/” target=”_top”¿’+ ’Application to
Publish in EPTCS¡/a¿’+ ’¡li¿¡a href=”http://login.eptcs.org/”
target=”_top”¿Login Page for Editors and Authors’+
’¡/ul¿¡/td¿¡/tr¿¡/tbody¿¡/table¿’; ¡/script¿ ¡/head¿ ¡body¿ ¡div id=’sitemap’¿
¡table width=100¡td align=’left’¿ ¡font size=-1¿ ¡b¿DOI:¡/b¿ ¡a
href=”http://dx.doi.org/10.4204/EPTCS.370”¿ 10.4204/EPTCS.370¡/a¿¡br¿
¡b¿ISSN:¡/b¿ 2075-2180¡/font¿ ¡/td¿¡td align=’left’¿ ¡input style=”cursor:
pointer” type=’button’ onclick=’changeText()’ value=’EPTCS Site Map’/¿
¡/td¿¡td align=’right’¿ ¡input style=”cursor: pointer” type=’button’
value=’EPTCS Home Page’ onClick=’parent.location=”http://eptcs.org/”’/¿
¡/td¿¡td align=’right’¿ ¡input style=”cursor: pointer” type=’button’
value=’Published Volumes’
onClick=’parent.location=”http://published.eptcs.org/”’/¿ ¡/td¿¡td
align=’right’¿ ¡input style=”cursor: pointer” type=’button’ value=’Forthcoming
Volumes’ onClick=’parent.location=”http://forthcoming.eptcs.org/”’/¿
¡/td¿¡/tr¿¡/table¿¡/div¿

¡center¿ ¡h1¿EPTCS 370¡/h1¿ ¡h1¿¡font size=5¿Proceedings of the 13th
International Symposium on¡/font¿ ¡br¿Games, Automata, Logics and Formal
Verification ¡br¿¡font size=3¿Madrid, Spain, September 21-23, 2022¡/font¿¡/h1¿
Edited by: Pierre Ganty and Dario Della Monica ¡/center¿ ¡hr class=sep¿ ¡table
width=100¡tr¿¡td class=fill¿¡i¿¡a href=”#EPTCS370.0”¿ Preface¡/a¿¡/i¿¡/br¿
¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡b¿Invited Presentation:¡/b¿ ¡a
href=”#EPTCS370.0.1”¿ Techniques for Unambiguous Systems¡/a¿¡/i¿¡/br¿ Wojciech
Czerwiński¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡b¿Invited Presentation:¡/b¿
¡a href=”#EPTCS370.0.2”¿ Learning Languages of Infinite Words¡/a¿¡/i¿¡/br¿
Dana Fisman¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡b¿Invited Presentation:¡/b¿ ¡a
href=”#EPTCS370.0.3”¿ State Complexity of Population Protocols¡/a¿¡/i¿¡/br¿
Javier Esparza¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡b¿Invited Presentation:¡/b¿ ¡a
href=”#EPTCS370.0.4”¿ Towards Multiset Semantics Database Theory: How I
Learned to Stop Worrying and Love Linear Algebra¡/a¿¡/i¿¡/br¿ Jerzy
Marcinkowski¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.1”¿ On the Existential Fragments of
Local First-Order Logics with Data¡/a¿¡/i¿¡/br¿ Benedikt Bollig, Arnaud
Sangnier and Olivier Stietel¡/td¿¡td align=”right”¿1¡/td¿¡/tr¿ ¡tr¿¡td
class=fill¿¡i¿¡a href=”http://dx.doi.org/10.4204/EPTCS.370.2”¿ Capturing
Bisimulation-Invariant Exponential-Time Complexity Classes¡/a¿¡/i¿¡/br¿
Florian Bruse, David Kronenberger and Martin Lange¡/td¿¡td
align=”right”¿17¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.3”¿ Complexity through Translations
for Modal Logic with Recursion¡/a¿¡/i¿¡/br¿ Luca Aceto, Antonis Achilleos,
Elli Anastasiadi, Adrian Francalanza and Anna Ingolfsdottir¡/td¿¡td
align=”right”¿34¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.4”¿ Schema-Based Automata
Determinization¡/a¿¡/i¿¡/br¿ Joachim Niehren, Momar Sakho and Antonio Al
Serhali¡/td¿¡td align=”right”¿49¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.5”¿ Generating Tokenizers with Flat
Automata¡/a¿¡/i¿¡/br¿ Hans de Nivelle and Dina Muktubayeva¡/td¿¡td
align=”right”¿66¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.6”¿ Analyzing Robustness of
Angluin’s L* Algorithm in Presence of Noise¡/a¿¡/i¿¡/br¿ Igor Khmelnitsky,
Serge Haddad, Lina Ye, Beno#x00ee;t Barbot, Benedikt Bollig, Martin Leucker,
Daniel Neider and Rajarshi Roy¡/td¿¡td align=”right”¿81¡/td¿¡/tr¿ ¡tr¿¡td
class=fill¿¡i¿¡a href=”http://dx.doi.org/10.4204/EPTCS.370.7”¿ Parametric
Interval Temporal Logic over Infinite Words¡/a¿¡/i¿¡/br¿ Laura Bozzelli and
Adriano Peron¡/td¿¡td align=”right”¿97¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.8”¿ Realizable and Context-Free
Hyperlanguages¡/a¿¡/i¿¡/br¿ Hadar Frenkel and Sarai Sheinvald¡/td¿¡td
align=”right”¿114¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.9”¿ Controller Synthesis for
Timeline-based Games¡/a¿¡/i¿¡/br¿ Renato Acampora, Luca Geatti, Nicola
Gigante, Angelo Montanari and Valentino Picotti¡/td¿¡td
align=”right”¿131¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.10”¿ CryptoSolve: Towards a Tool for
the Symbolic Analysis of Cryptographic Algorithms¡/a¿¡/i¿¡/br¿ Dalton
Chichester, Wei Du, Raymond Kauffman, Hai Lin, Christopher Lynch, Andrew M.
Marshall, Catherine A. Meadows, Paliath Narendran, Veena Ravishankar, Luis
Rovira and Brandon Rozek¡/td¿¡td align=”right”¿147¡/td¿¡/tr¿ ¡tr¿¡td
class=fill¿¡i¿¡a href=”http://dx.doi.org/10.4204/EPTCS.370.11”¿ Adversarial
Formal Semantics of Attack Trees and Related Problems¡/a¿¡/i¿¡/br¿ Thomas
Brihaye, Sophie Pinchinat and Alexandre Terefenko¡/td¿¡td
align=”right”¿162¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.12”¿ Avoid One’s Doom: Finding
Cliff-Edge Configurations in Petri Nets¡/a¿¡/i¿¡/br¿ Giann Karlo Aguirre-
Sambon#x00ed;, Stefan Haar, Lo#x00ef;c Paulev#x00e9;, Stefan Schwoon and Nick
W#x00fc;rdemann¡/td¿¡td align=”right”¿178¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.13”¿ Comparing Channel Restrictions
of Communicating State Machines, High-level Message Sequence Charts, and
Multiparty Session Types¡/a¿¡/i¿¡/br¿ Felix Stutz and Damien Zufferey¡/td¿¡td
align=”right”¿194¡/td¿¡/tr¿ ¡tr¿¡td class=fill¿¡i¿¡a
href=”http://dx.doi.org/10.4204/EPTCS.370.14”¿ Characterizing the Decidability
of Finite State Automata Team Games with Communication¡/a¿¡/i¿¡/br¿ Michael
Coulombe and Jayson Lynch¡/td¿¡td align=”right”¿213¡/td¿¡/tr¿ ¡/table¿ ¡hr
class=sep¿¡h1 align=left¿¡a name=’EPTCS370.0’¿Preface¡/a¿¡/h1¿

¡p¿This volume contains the proceedings of GandALF 2022, the Thirteenth
International Symposium on Games, Automata, Logics, and Formal Verification.
The symposium was held in Madrid, Spain, September 21-23, 2022.¡/p¿ ¡p¿The
GandALF symposium was established by a group of Italian computer scientists to
provide an opportunity for researchers interested in logic for computer
science, automata theory, game theory, to gather and discuss the application
of formal methods to the specification, design, and verification of complex
systems. Previous editions of GandALF were held in Padova, Italy (2021);
Brussels, Belgium (2020); Bordeaux, France (2019); Saarbr#252;cken, Germany
(2018); Rome, Italy (2017); Catania, Italy (2016); Genoa, Italy (2015);
Verona, Italy (2014); Borca di Cadore, Italy (2013); Napoli, Italy (2012); and
Minori, Italy (2011 and 2010). It is a forum where people from different
areas, and possibly with different backgrounds, can fruitfully interact, with
a truly international spirit, as witnessed by the composition of the program
and steering committee and by the country distribution of the submitted
papers.¡/p¿ ¡p¿The program committee selected 14 papers (out of 20
submissions) for presentation at the symposium. Each paper was reviewed by at
least two referees, and the selection was based on originality, quality, and
relevance to the topics of the call for papers. The scientific program
included presentations on automata, logics for computer science and
verification, complexity theory, formal methods and languages, games,
synthesis algorithms and security. The program included four invited talks,
given by Wojciech Czerwi#324;ski (University of Warsaw, Poland), Javier
Esparza (Technische Universit#228;t M#252;nchen, Germany), Dana Fisman (Ben-
Gurion University, Israel), and Jerzy Marcinkowski (University of Wroc#322;aw,
Poland). We are deeply grateful to them for contributing to this year edition
of GandALF.¡/p¿ ¡p¿We would like to thank the authors who submitted papers for
consideration, the speakers, the program committee members and the additional
reviewers for their excellent work. We also thank Eddie Kohler for the HotCRP
conference review software, EPTCS and arXiv for hosting the proceedings; in
particular, we thank Rob van Glabbeek for the precise and prompt technical
support with issues related with the proceeding publication procedure.¡/p¿
¡p¿Finally we would like to thank the local organisers, and especially Tania
Rodr#237;guez and Mar#237;a Alcaraz for making sure the event ran
smoothly.¡/p¿ ¡p¿Dario Della Monica and Pierre Ganty¡/p¿ ¡h2 id=”program-
chairs”¿Program Chairs¡/h2¿ ¡ul¿ ¡li¿Dario Della Monica, University of Udine
(Italy)¡/li¿ ¡li¿Pierre Ganty, IMDEA Software Institute, Madrid (Spain)¡/li¿
¡/ul¿ ¡h2 id=”program-committee”¿Program Committee¡/h2¿ ¡ul¿ ¡li¿Christel
Baier, TU Dresden (Germany)¡/li¿ ¡li¿Suguman Bansal, University of
Pennsylvania (USA)¡/li¿ ¡li¿Nathalie Bertrand, Inria (France)¡/li¿ ¡li¿Filippo
Bonchi, University of Pisa (Italy)¡/li¿ ¡li¿Laura Bozzelli, Universit#224;
degli Studi di Napoli Federico II (Italy)¡/li¿ ¡li¿V#233;ronique Bruy#232;re,
University of Mons (Belgium)¡/li¿ ¡li¿David de Frutos Escrig, Universidad
Complutense de Madrid (Spain)¡/li¿ ¡li¿Cezara Dr#259;goi, AWS¡/li¿ ¡li¿Mohamed
Faouzi Atig, Uppsala University (Sweden)¡/li¿ ¡li¿Adrian Francalanza,
University of Malta (Malta)¡/li¿ ¡li¿Orna Kupferman, The Hebrew University
(Israel)¡/li¿ ¡li¿Konstantinos Mamouras, Rice University (USA)¡/li¿ ¡li¿Roland
Meyer, TU Braunschweig (Germany)¡/li¿ ¡li¿Fabio Mogavero, Universit#224; degli
Studi di Napoli Federico II (Italy)¡/li¿ ¡li¿Paritosh Pandya, IIT Bombay
(India)¡/li¿ ¡li¿Pawe#322; Parys, University of Warsaw (Poland)¡/li¿
¡li¿Guillermo P#233;rez, University of Antwerp (Belgium)¡/li¿ ¡li¿Pierre-Alain
Reynier, LIS, Aix-Marseille University amp; CNRS (France)¡/li¿ ¡li¿Andrea
Turrini, Institute of Software, Chinese Academy of Sciences (China)¡/li¿
¡li¿Georg Zetzsche, Max Planck Institute for Software Systems - MPI-SWS
(Germany)¡/li¿ ¡/ul¿ ¡h2 id=”steering-committee”¿Steering Committee¡/h2¿ ¡ul¿
¡li¿Luca Aceto, Reykjavik University (Iceland)¡/li¿ ¡li¿Javier Esparza,
University of Munich (Germany)¡/li¿ ¡li¿Salvatore La Torre, University of
Salerno (Italy)¡/li¿ ¡li¿Angelo Montanari, University of Udine (Italy)¡/li¿
¡li¿Mimmo Parente, University of Salerno (Italy)¡/li¿ ¡li¿Jean-Fran#231;ois
Raskin, Universit#233; libre de Bruxelles (Belgium)¡/li¿ ¡li¿Martin
Zimmermann, University of Liverpool (UK)¡/li¿ ¡/ul¿ ¡h2 id=”external-
reviewers”¿External Reviewers¡/h2¿ ¡p¿Adriano Peron, Adrien Pommellet, Antoine
Mottet, Bartosz Klin, Eryk Kopczy#324;ski, Ga#235;tan Staquet, Giannicola
Scarpa, Ji Guan, Joseph Lallemand, Lo#239;c H#233;lou#235;t, Moses Ganardi,
Ramanathan Srinivasan, Sylvain Lombardy, and Wanwei Liu.¡/p¿ ¡hr class=sep¿¡h1
align=left¿¡a name=’EPTCS370.0.1’¿Techniques for Unambiguous Systems¡/a¿¡/h1¿

¡b¿Wojciech Czerwi#x0144;ski¡/b¿ (¡i¿University of Warsaw, Poland¡/i¿) ¡p¿
¡p¿In recent years it became apparent that many decision problems can be
solved efficiently on unambiguous systems (systems in which each word is
accepted by at most one run). I will show first a classical approach for
solving language equivalence by weighted automata. Then I will present novel
techniques, which helped us solve the problem for vector addition systems.
Finally I plan to advertise an interesting related problem of multiplicity
equivalence, which seems to reveal some connections between the unambiguity
problem and other fields of mathematics.¡/p¿ ¡hr class=sep¿¡h1 align=left¿¡a
name=’EPTCS370.0.2’¿Learning Languages of Infinite Words¡/a¿¡/h1¿

¡b¿Dana Fisman¡/b¿ (¡i¿Ben-Gurion University, Israel¡/i¿) ¡p¿ ¡p¿The problem
of inferring an automaton model of a black box system has found many
applications in formal methods of system design. If the black-box system
implements (or can be abstracted as) a regular language of finite words, it
can be inferred in polynomial time using query learning. In this talk we’ll
discuss the problem we face when the black-box system implements a regular
language of infinite words (e.g. the black-box is a reactive system).¡/p¿
¡p¿While there are automata processing infinite words e.g. (Buechi automata)
that have the same structure as automata on finite words (DFAs), learning them
seems to be a harder problem. During the talk we will get acquainted with the
ideas behind learning algorithms for regular languages, the obstacles in
devising learning algorithms for regular languages of infinite words, and
state-of-the-art results on learnability of acceptors of regular languages of
infinite words.¡/p¿ ¡hr class=sep¿¡h1 align=left¿¡a name=’EPTCS370.0.3’¿State
Complexity of Population Protocols¡/a¿¡/h1¿

¡b¿Javier Esparza¡/b¿ (¡i¿Technische Universit#x00e4;t M#x00fc;nchen,
Germany¡/i¿) ¡p¿ ¡p¿Population protocols were introduced by Angluin et al. in
2004 to study the theoretical properties of networks of mobile sensors with
very limited computational resources. They have also been proposed as a
natural computing model, with molecules, cells, or microorganisms playing the
role of sensors.¡/p¿ ¡p¿In a population protocol an arbitrary number of
indistinguishable, finite-state agents interact randomly in pairs to
collectively decide if their initial global configuration satisfies a given
property. The property is formalized as a predicate that maps each initial
configuration to an output, 0 or 1. Starting from an initial configuration,
the agents eventually agree to the correct output almost surely, and continue
producing it forever. The protocol is said to stabilize to the correct
output.¡/p¿ ¡p¿Population protocols can decide exactly the semilinear
predicates, or, equivalently, the predicates expressible in Presburger
arithmetic. Current research concentrates on investigating the amount of
resources needed to decide a given predicate. The standard resources, time and
memory, translate for population protocols into expected time to stabilization
and number of states of each agent. In this talk we concentrate on the state
complexity of population protocols, for which matching upper and lower bounds
have been found in the last few years.¡/p¿ ¡hr class=sep¿¡h1 align=left¿¡a
name=’EPTCS370.0.4’¿Towards Multiset Semantics Database Theory: How I Learned
to Stop Worrying and Love Linear Algebra¡/a¿¡/h1¿

¡b¿Jerzy Marcinkowski¡/b¿ (¡i¿University of Wroc#x0142;aw, Poland¡/i¿) ¡p¿
¡p¿For the last ten years, or maybe more, I have been a Database Theorist.¡/p¿
¡p¿Like all (or at least most of) the Database Theorists I modelled the real-
world-database relations, and real-world answers to the queries, as sets. If
my query was quot;Exists y Cat(y) and Owns(x,y)quot;, and my database happened
to contain the tuples quot;Cat(Tibby)quot; and quot;Owns(Andreas, Tibby)quot;
then – clearly – the constant quot;Andreasquot; was an element of the answer
set.¡/p¿ ¡p¿I studied this model, using the methodology of mathematics. My
toolbox was simple. It comprised some specific Database Theory concepts (like
Chase) and some simple Computation Theory tricks (including maybe some
automata-based arguments). Using this toolbox I constructed reasonings, which
were occasionally complicated, but always elementary. It was fun.¡/p¿ ¡p¿But
then, in early 2021, someone asked me what would happen to my results
concerning Query Determinacy (whatever it is) if I considered a more realistic
model, in which database relations, and answers to the queries, are multisets
rather than sets. So, if my database knew that Andreas actually has six cats,
the answer (multi)set would contain the constant quot;Andreasquot; with
multiplicity six.¡/p¿ ¡p¿We started to think about it (with my very clever
students, Jaros#322;aw Kwiecie#324; and Piotr Ostropolski-Nalewaja) and soon
we realized that this minor change in the assumptions about the model leads to
a major change in the tools we need to study it. This felt to us like entering
a completely new world. Suddenly the language and the methods from Linear
Algebra appear so naturally that it is fair to say that they impose themselves
on the researchers.¡/p¿ ¡p¿Clearly, we were not the first Database Theorists
to set foot on this new continent. People have attempted to re-examine old
Database Theory results, in the multiset-semantics scenario, for about 30
years now. But such attempts were few. And this is (I guess) exactly because
in order to make any progress here one needs to learn totally new tools.¡/p¿
¡p¿To our surprise we learned that this continent had also been visited before
by the Mathematicians. They had constructed a number of structures there, some
of them of some use for us. That’s a bit frustrating, because they use
different terms to call some notions, and it is not always straightforward to
understand how to translate their own results to our language.¡/p¿ ¡p¿My talk
will be a story by a traveller astonished by what he saw during his first
short trip to the little known continent of Multiset-Semantics Database
Theory.¡/p¿ ¡p¿To give you a glimpse of the techniques that appear there I
will present some results and arguments from our PODS 2022 paper
quot;Determinacy of Real Conjunctive Queries. The Boolean Casequot; (with
Kwiecie#324; and Ostropolski-Nalewaja). But I will also mention the adventures
of other travellers to this new land, with particular emphasis on the famous
Conjunctive Query Containment Problem.¡/p¿

¡hr class=sep¿ ¡/body¿¡/html¿


# Exploring Unstructured Environments using Minimal Sensing on Cooperative
Nano-Drones

Pedro Arias-Perez1, Alvika Gautam2, Miguel Fernandez-Cortizas1,
David Perez-Saura1, Srikanth Saripalli2 and Pascual Campoy1 1is with the
Computer Vision and Aerial Robotics Group at Universidad Politécnica de
Madrid, Spain (CVAR-UPM) at the Centre for Automation and Robotics C.A.R.
(UPM-CSIC). {pedro.ariasp, miguel.fernandez.cortizas, david.perez.saura,
<EMAIL_ADDRESS>with the Department of Mechanical Engineering, Texas
A&M University, College Station, TX, USA {alvikag<EMAIL_ADDRESS>work was partially funded by FPU20/07198 of the Spanish Ministry for
Universities and by the project INSERTION ref. ID2021-127648OBC32, “UAV
Perception, Control and Operation in Harsh Environments”, funded by the
Spanish Ministry of Science and Innovation under the program “Projects for
Knowledge Generating”.For the purpose of Open Access, and in fulfillment of
the obligations arising from the grant agreement, the author has applied a
Creative Commons Attribution 4.0 International (CC BY 4.0) license to any
Author Accepted Manuscript version arising from this submission.

###### Abstract

Recent advances have improved autonomous navigation and mapping under payload
constraints, but current multi-robot inspection algorithms are unsuitable for
nano-drones due to their need for heavy sensors and high computational
resources. To address these challenges, we introduce _ExploreBug_ , a novel
hybrid frontier range bug algorithm designed to handle limited sensing
capabilities for a swarm of nano-drones. This system includes three primary
components: a mapping subsystem, an exploration subsystem, and a navigation
subsystem. Additionally, an intra-swarm collision avoidance system is
integrated to prevent collisions between drones. We validate the efficacy of
our approach through extensive simulations and real-world exploration
experiments involving up to seven drones in simulations and three in real-
world settings, across various obstacle configurations and with a maximum
navigation speed of 0.75 m/s. Our tests demonstrate that the algorithm
efficiently completes exploration tasks, even with minimal sensing, across
different swarm sizes and obstacle densities. Furthermore, our frontier
allocation heuristic ensures an equal distribution of explored areas and paths
traveled by each drone in the swarm. We publicly release the source code of
the proposed system to foster further developments in mapping and exploration
using autonomous nano drones.

Video: https://vimeo.com/cvarupm/cf-exploration

Code: https://github.com/pariaspe/cf_exploration

##  I Introduction

Exploration and mapping of unknown unstructured environments is a crucial area
of research in the field of mobile robotics. As the technology of nano-sized
drones advances [1][2][3], their utility in both indoor and outdoor autonomous
tasks has gained considerable prominence. A nano-sized drone typically weighs
$\thicksim$50 g or less and is the size of a palm. These drones are
particularly well-suited for potentially hazardous indoor exploration missions
due to their small size, which ensures safety around humans, and their agility
and speed, which are essential for effective exploration. Moreover, their low
cost contributes to their feasibility for widespread use as they are easily
replaceable.

Figure 1: View of one nano-drone performing a exploration of an unknown
unstructured environment.

Building on the capabilities of individual nano-drones, the use of drone
swarms enhances these operations significantly. Swarms leverage the collective
speed and maneuverability of multiple drones, which theoretical and empirical
research confirms can accomplish tasks more efficiently and rapidly than a
single drone [4]. Moreover, the strategic deployment of multiple drones
introduces a level of redundancy, thereby enhancing the overall system’s fault
tolerance, compared to a single drone. Additionally, cooperating robots can
significantly reduce sensor uncertainty thanks to the information overlap
between different robots.

Several authors in the literature have shown promising progress in robotic
exploration [5, 6, 7]. Available algorithms strongly rely on complex sensors,
as depth cameras or 3D lidars, for obstacle avoidance and mapping. However,
current nano-drones can not adopt these algorithms as the restricted payload
resources for on-board sensors and computational power. The available payload
in nano-drones is in the order of grams. Therefore, it is only possible to
mount light and low-power sensors that can only provide sparse and noisy
measurements. Consequently, the minimal sensing capacity introduces a
challenging exploration problem.

In this work, we present _ExploreBug_ , a coordination algorithm for a group
of nano-drones to perform an efficient full exploration. Our method aims to
address the challenge of minimal sensing exploration. Against latest
contributions in the topic, where authors focus on exploration time and speed,
we pursue to grow smaller not stronger. Our aim is to evaluate similar
techniques on smaller platforms, how far we can push the limits and evaluate
the trade-offs accordingly.

Concisely, the main contributions of this work are as follows:

  1. 1.

Design of a novel exploration algorithm that effectively utilizes minimal
sensing capabilities (four single-beam range sensors) tailored specifically
for nano-drones.

  2. 2.

Extensive experimental evaluation of the proposed approach in simulated and
real environments, demonstrating promising results.

  3. 3.

Finally, we contribute by making the code of the proposed system open-source
enabling researchers to evaluate and develop upon our framework.

##  II Related Work

###  II-A Multi-robot Exploration

Autonomous exploration of unknown environments has been a common robotics
research topic over the last two decades. One of the most popular approaches
is a frontier-based exploration technique, first introduced in [8]. The main
concept behind frontier-based exploration is moving to the boundary where
explored space meets uncharted territory to maximize new information about the
world. By constantly moving to these new frontiers, a robot can expand its map
into unexplored areas until the entire environment is fully mapped. Burgard et
al. present one of the first frontier-based exploration solution for a team of
robots [5]. Their approach chooses the appropriate target points for the
individual robots so that simultaneously takes into account the cost of
reaching a target point and its utility, which is reduced whenever the target
point is assigned to a robot. In [9], Mannucci et al. propose a 3D exploration
strategy based on a combination of local and global information for a team of
ﬂying robots with constrained payload. Motivated by the insufficient
exploration rate, Zhou et al. provide FUEL [10], a hierarchical framework that
can support fast drone exploration in complex unknown environments. Later,
they extend their prior work for a fleet of decentralized drones, suggesting a
new system named RACER [11]. They decompose the unknown space into hgrid and
distribute the task units among quadrotors by a pairwise interaction, assuming
asynchronous and unreliable communication. Hui et al. consider a limited
communication bandwidth between the multi-drone system. Their decentralized
exploration planning framework, named DDPM [12], uses a lightweight
information structure which enables exploration with little overlap. Each
drone maintains a topological graph to save the information structure, serving
as a high-level understanding and abstraction of the environment. Bartolomei
et al. suggest a higher-level reasoning for multi-robot missions [13]. Each
individual drone has the ability to alternate between various execution modes.
This balance involves a cautious exploration of yet completely unknown regions
and more aggressive exploration of smaller, unfamiliar areas within the space.

Nevertheless, despite the progress in the topic in recent years, there are big
limitations to apply these solutions on nano-drones. All systems previously
cited require heavy sensors, as depth cameras or 3d lidars, and high
computational power of their algorithms. Resource restrictions on nano-drones
rule out the currently available solutions for frontier-based exploration.

###  II-B Nano-Drones & Minimal Sensing

Recently, several studies have shown enormous improvement in autonomous
navigation and mapping [14, 15], both key components to fulfill an
exploration. As a result of the extreme payload constraints of nano-sized
drones, previous works have sought alternative exploration strategies.
A promising bug exploration algorithm was introduced by McGuire et al. [16].
This algorithm empowered a swarm of nano quadcopters to effectively navigate
through unfamiliar and cluttered environments, ultimately returning to their
initial starting location. In [17], Duisterhof et al. propose Sniffy Bug, a
bug-inspired autonomous swarm to seek gas leaks in unknown environments. Their
exploration strategy rely in the observed gas concentrations by the swarm,
which indicates search directions, while the bug navigation is performed in
two stages, line following and wall following. In [18], Lamberti et al.
present a bio-inspired autonomous exploration for object detection. The
authors compare four different navigation policies from random to scan
spinning, showing the pseudo-random policy the best result. Pourjabar et al.
suggest a system design to achieve robust autonomous exploration capabilities
for a swarm of nano-drones in [19]. Their multi-sensory approach combines
lightweight single-beam laser ranging, low resolution camera and an ultra-
wide-band based ranging module.

However, none of these approaches exploit the benefits of the environment
representation of frontier-based exploration methods. Motivated by this
scarcity, in this work we present a minimal sensing frontier-based exploration
technique capable to be carried by nano-drones.

##  III Methodology

The overall problem considered in this work is to perform a full map
exploration with a nano-drone swarm. The main constraint of nano drones is
their low capabilities on payload. Therefore, onboard sensors are limited
which implies spare sensing and mapping. We propose an exploration pipeline
that can deal with minimal sensing. This strategy allows a full exploration
for nano-drones. Due to its limited payload, in our system each drone only
carries four single-beam range sensors, pointing front, back, right, and left,
and 4 meters maximum range. Because of the sensor used, the exploration
performed is a 2D problem, so that the drones don’t change their altitude
during their mapping and exploration task.
Another relevant assumption is that agents can be localized in a common
reference frame and they share an infinite-range communication channel between
them.

###  III-A System Overview

Figure 2: Overview of the pipeline. Blue boxes belong to the mapping sub-
system, green boxes to the exploration sub-system, orange boxes to the
navigator sub-system and red boxes to the intra-swarm collision avoidance sub-
system.

The system comprises of three main components: a mapping sub-system, an
exploration sub-system, and a navigator sub-system, each corresponding to a
specific phase of the mission. Fig. 2 provides an overview of the pipeline.

In the mapping phase, each agent utilizes readings from the multi-ranger
sensor, shared among the swarm, to create a common map. Given that the sensor
collects only 2D information about the environment, the map is encoded as an
occupancy grid.

The exploration phase consists of three steps: the exploration strategy,
frontier generation, and frontier allocation. The exploration strategy employs
a hybrid frontier range bug algorithm. Subsequently, a set of available
frontiers is generated from the map, and based on the swarm’s state, the most
suitable frontier is allocated on demand to each agent.

Finally, the navigator transmits motion references to the controller to reach
the goal point. The navigation system’s primary component is a local path
planner, leveraging Aerostack2 [20], a framework for developing autonomous
aerial robotics systems. Aerostack2 facilitates the initiation, pausing, or
cessation of high-level robotics abstractions, known as behaviors (e.g., go to
way-point, hover, or take off), streamlining drone motion control.

Alongside these systems, an intra-swarm collision avoidance system operates to
prevent collisions among drones. It tracks the position of each drone and, if
a potential collision is detected, it temporarily halts one drone’s navigator
and initiates a safety maneuver to prevent the collision. Once the safety
distance is reestablished, the navigator resumes its operation, ensuring the
exploration continues safely.

###  III-B Explore Bug

The exploring strategy operates as a finite state machine (FSM), depicted in
Fig. 3, where each drone begins at the “Init” state. The approach is similar
to CautiousBug [21] or Rotate-and-measure [18], where a conservative spiral
search is performed before going to a specific location. This ensures a safer
exploration strategy by thoroughly scanning the environment before navigation.
During the “Sense” phase, the drone continuously collects data from the
surroundings at a rate of 20 Hz.

Figure 3: FSM of the ExploreBug algorithm.

Frontiers, which represent potential next points for navigation, are
identified over the generated map, leading to the “Navigate to Frontier”
state. It should be noted that the term navigation implies the need of a map
and can only be performed on the already explored surroundings. Frontier
generation and allocation to drones is described in subsequent subsections in
detail. Upon reaching the goal ($d_{front}<d_{th}$), the robot returns to the
“Sense” state.

Due to the symmetry of the range-sensor, spinning consist of a $\frac{\pi}{2}$
radians turn only $\psi_{goal}=\psi_{0}+\frac{\pi}{2}$. Rotating just occurs
during the “Sense” state since navigation can be performed without yaw
control. Our cautious algorithm ensures to fly under already known environment
only, so the drone will not fly over an obstacle.

During the navigation state, if two or more drones are within a safety margin
distance $R_{other}<R_{coll}$, the one that’s closest to its goal
($d_{front}<d^{\prime}_{front}$) transitions into the “Drone Avoidance” state
(that is, change in altitude and hover to avoid collision), while the other
drone continues to fly without any avoidance maneuver. This ensures a quicker
return to the navigation state once the safety distance is restored. Finally,
when no frontiers are left, the exploration is consider as finished and the
algorithm enters into “End” state, which is accessible from any other state
within the FSM.

(a) Map

(b) Edges

(c) Frontiers clustered

(d) Frontiers filtered

Figure 4: Frontier generation pipeline: (a) map, (b) edges extraction, (c)
frontiers clustered and (d) frontiers filtered. $M_{free}$ are represented in
white, $M_{obs}$ in black and $M_{unk}$ in gray. Each color pictures pixels
and centroid from every frontier.

###  III-C Frontier Generation

Given the sensor’s nature, occupancy grid maps are selected to represent the
environment. These maps maintain the probability of each grid cell being empty
or occupied. Occupancy maps have been proven to be an efficient and powerful
description of the surroundings incrementally updating the map based on the
sensor readings [22].

Local occupancy grids are received from each drone and stored in a cell grid
central map $M$. Cells can be unknown or have a certainty to be occupied/free,
$M=M_{free}\cup M_{obs}\cup M_{unk}$. This occupation probability is updated
based on the hit or miss of the sensor readings. The central map is used to
obtain a set of frontiers $F$, where $F\subseteq M$. A frontier $f_{i}$ is
formed by a group of consecutive cells in the grid and it is determined by a
unique frontier descriptor. A descriptor is formed by the centroid $c_{i}$,
orientation $\psi_{i}$ and area $A_{i}$ (or number of cells) of the frontier.

$\forall f_{i}\in F,\;f_{i}:\\{c_{i},\psi_{i},A_{i}\\}$ (1)

Frontiers $F$ are obtained from the relative complement of $M_{obs}$ in the
edges detected over $M_{free}$, $canny(M_{free})$ (Eq. 2). After the
extraction, frontiers are clustered based on pixel connectivity and filtered
depending on their area. If a frontier is smaller than a lower threshold it is
discarded, whether if it is bigger that an upper threshold it is split. The
Algorithm 1 describes frontier generation.

$F=canny(M_{free})\cap M_{obs}$ (2)

Fig. 4 shows the frontier generation pipeline, from the global map $M$ (Fig.
4(a)) to the frontiers extracted $F$ (Fig. 4(d)). Edges detected over the map
$canny(M_{free})$ are presented in Fig. 4(b). Finally, Fig. 4(c) exhibits the
frontiers clustered previous to the filtering.

Algorithm 1 Frontier generation

$M$: current grid map

$\bar{M}_{free}=M_{obs}\cup M_{unk}$

$\bar{M}_{obs}=M_{free}\cup M_{unk}$

$E=$ canny($\bar{M}_{free}$)

$F=$ $\bar{M}_{obs}\cap E$

for all $f_{i}\in F$ do

if $A_{i}<lower\\_threshold$ then

remove $f_{i}$ from $F$

else if $A_{i}>upper\\_threshold$ then

split $f_{i}$ $\triangleright$ By pixel continuity

end if

end for

###  III-D Frontier Allocator

Goal choosing relies on the frontier candidates and the drone swarm. The
optimization problem is defined in Equation 3. Cost function depends on two
terms. First minimizes the path to next frontier. We believe that the
exploration rate is maximized during the “Sense” phase and not during the
“Navigation” state since navigation occurs over already mapped area. Second
term minimizes the overlap between agents, maximizing distance between them.

$G^{\ast}=\operatorname*{argmax}_{G}\quad\frac{1}{X}\sum_{i}^{F}\sum_{j}^{X}d_{ij}-2\sum_{i}^{F}c_{i}$
(3)

where $G^{\ast}$ is the optimal frontier, $X$ is the set of drones, $F$ is the
set of frontiers, $d_{ij}$ is the distance between the frontier allocated to
drone $i$ and frontier $j$ and $c_{i}$ is the distance between frontier $i$
and the current drone.

The proposed heuristic does not have any constraints related to the robot
motion. Exploration algorithm trades safety against speed. Each nano-drone is
already stopping when reaching the goal frontier to fulfill the scan action,
so motion speed is not taken into account while allocating next frontier.
Moreover, there is no need to change heading during navigation since path goes
through known space and sensor symmetry.

##  IV Experimental Validation

To show the performance of our algorithm, we performed several experiments
varying world size, obstacle density and swarm size. The experimental
validation was done in both real and simulated environments.

###  IV-A Experimental setup

The nano-drones used to form the swarm in our experiments are Bitcraze
Crazyflie 2.1 quadcopters, each weighing 27 grams with a diameter of 10 cm.
These drones are equipped with a multi-ranger deck featuring five VL53L1x
Time-of-Flight (ToF) sensors, capable of measuring distances up to 4 meters
with millimeter precision at a frequency of 20 Hz. Additionally, each drone
carries a motion capture marker deck, with the total drone payload, including
the battery, being under 10 grams.

Our experiment scenarios replicated non-structured environments, using
cylindrical poles as obstacles that imitate forest trees for both simulated
and real environments (see Fig. 1). The variety in our experiments stemmed
from different parameters such as the density of these obstacles, the size of
the drone swarm, and the initial placement of drones and obstacles’ location
within the testing area.

Simulations are conducted using Gazebo replicating Crazyflie characteristics.
The quadcopter dynamics are simulated based on RotorS [23] using the ground
truth of the drone. A multi-ranger deck imitation is placed onboard as the
only payload.

The exploration algorithm leverages Aerostack2 [20] for navigation and
control, enabling the use of a consistent algorithm across both simulated and
real-world setups. However, there are slight variations in the Aerostack2
components used in each system. Specifically, the interfaces connecting the
platforms to Aerostack2 differ and the state estimator plugins vary.
Aerostack2 functions uniformly across both environments, providing a seamless
transition from simulation to actual deployment.

###  IV-B Exploration in Simulated Scenarios

We benchmark the proposed exploration strategy in a Gazebo simulation. We test
the algorithm using different swarm size, setting diverse starting points for
the swarm, varying the obstacle density and world size. In all experiments, we
set the navigation speed to $0.75m/s$, the spin speed to $0.15$ $rad/s$, and
the sensor range to $4m$. The remaining parameters are shown in Table I.

Parameter | Value
---|---
Map resolution | 0.1
Sensor range | 4
Safety distance to obstacles | 0.4
Safety distance to other drones | 2.0
Navigation speed | 0.75
Reached distance threshold | 0.2
Spin speed | 0.15
Yaw threshold | 0.15
Minimum frontier size | 1.5
Maximum frontier size | 3.5
TABLE I: Parameter configuration for simulation experiments.

(a) Average exploration rate for the 0.05 $obs/m^{2}$ density scenario. The
shaded area shows the standard deviation.

(b) Exploration time per swarm size depending on the obstacle density. Low
stands for 0.05 $obs/m^{2}$, medium for 0.1 $obs/m^{2}$ and high for 0.2
$obs/m^{2}$.

Figure 5: Simulation experiment results up to seven drones. Obstacle density [$obs/m^{2}$] | # of drones | Time [s] | Area [%] | Path Length [m] | Overlap [%]
---|---|---|---|---|---
0.05 | 1 | 2831.79 $\pm$ 59.62 | 99.37 $\pm$ 0.01 | 986.66 $\pm$ 24.51 | -
2 | 1438.00 $\pm$ 45.98 | 99.37 $\pm$ 0.02 | 972.4 $\pm$ 34.08 | 25.79 $\pm$ 8.67
3 | 935.40 $\pm$ 24.79 | 99.32 $\pm$ 0.01 | 913.10 $\pm$ 23.65 | 16.88 $\pm$ 3.27
5 | 624.98 $\pm$ 21.77 | 99.37 $\pm$ 0.02 | 920.92 $\pm$ 26.87 | 31.32 $\pm$ 5.17
7 | 494.99 $\pm$ 22.17 | 99.14 $\pm$ 0.66 | 1037.30 $\pm$ 46.89 | 35.26 $\pm$ 5.06
0.1 | 1 | 2979.00 $\pm$ 91.46 | 98.56 $\pm$ 0.06 | 1008.97 $\pm$ 37.59 | -
2 | 1467.00 $\pm$ 29.25 | 98.62 $\pm$ 0.04 | 998.47 $\pm$ 18.87 | 24.0 $\pm$ 6.16
3 | 983.39 $\pm$ 23.43 | 98.62 $\pm$ 0.03 | 941.17 $\pm$ 22.53 | 17.85 $\pm$ 2.52
5 | 694.60 $\pm$ 27.77 | 98.63 $\pm$ 0.02 | 1008.51 $\pm$ 39.45 | 30.29 $\pm$ 5.45
7 | 500.80 $\pm$ 20.02 | 98.67 $\pm$ 0.02 | 1126.36 $\pm$ 34.72 | 36.06 $\pm$ 3.44
0.2 | 1 | 3560.80 $\pm$ 125.83 | 95.19 $\pm$ 1.13 | 1153.33 $\pm$ 19.85 | -
2 | 1944.99 $\pm$ 99.69 | 96.26 $\pm$ 0.62 | 1214.82 $\pm$ 86.44 | 26.42 $\pm$ 8.81
3 | 1246.79 $\pm$ 49.86 | 95.02 $\pm$ 0.98 | 1153.14 $\pm$ 64.81 | 25.18 $\pm$ 8.35
5 | 852.38 $\pm$ 49.70 | 96.28 $\pm$ 1.02 | 1265.07 $\pm$ 69.12 | 27.73 $\pm$ 3.01
7 | 598.61 $\pm$ 37.37 | 96.54 $\pm$ 0.43 | 1288.79 $\pm$ 91.09 | 35.71 $\pm$ 3.99
TABLE II: Results of the simulation experiments up to seven drones. We report
the average and standard deviation for the completion time, percentage of area
explored and total path traveled for the swarm. Best results are highlighted
in bold. Lowest times correspond to the highest drones number, nonetheless
shortest path lengths match with lowest overlap. Increasing the swarm size
slightly increases the overlap.

We assemble three simulation universes with different obstacle densities. Each
scenario is 50x50m in size with an obstacle density of 0.05, 0.1, and 0.2
$obs/m^{2}$ respectively. We perform experiments with one, two, three, five,
and seven drones for each proposed environment.

We observed that the exploration rate, or how the area discovered evolves,
increased similarly in the three scenarios as we added more drones to the
exploration algorithm. Fig. 5(a) shows the exploration results at the low
obstacle density environment. Additionally, we observed that increasing the
number of obstacles in the scenario drops the exploration rate (see Fig.
5(b)). Fig. 6(c) exhibits a top view of a three drones exploration on a low
obstacle density universe. The top view demonstrates that the frontier
allocation heuristic distributes equally the area to explore into the swarm,
while other heuristics fail to.

A comprehensive summary of the results is detailed in Table II. An exploration
experiment is considered as completed when no frontier is available. Time
starts when drones are taking off and finishes when all drones have landed.
Area column represents the ratio between the known and the full map. The path
length is the sum of all drone paths. Overlap stands for the intersection
between all drone-explored regions. These results show (1) exploration time
decreases by increasing the size of the swarm and increases by increasing the
density of obstacles; (2) the area explored remains similar regardless of the
number of drones; (3) path length remains similar regardless the number of
drones and increases with the number of obstacles and (4) overlap increases
with the number of drones and remains similar with the obstacle density.

(a) Nearest frontier. Time 1030$s$, path length 1026.1$m$ and overlap
34.48$\%$.

(b) Maximum distance between drones. Time 1562$s$, path length 1329.73$m$,
overlap 46.4$\%$.

(c) Ours. Time 942$s$, path length 917.06$m$ and overlap 14.18$\%$.

Figure 6: Exploration experiments with different frontier allocation
heuristic. Each colored line represents the trajectory followed by each drone,
while the shaded areas symbolizes the explored regions. Colored diamonds shows
drones starting points and black dots represent the obstacles in the
environment.

###  IV-C Real-World Experiments

To validate our approach in real-world scenarios, we perform extensive
experiments varying the swarm size, starting point of each drone, and
obstacles configuration. We conduct all real-world experiments in a $8\times
8$ $m^{2}$ space with an obstacle density around 0.05 $obs/m^{2}$. We set the
navigation speed to $0.75$ $m/s$ and the spin speed to $0.1$ $rad/s$. The
multi-ranger deck’s maximum range was clipped up to 2m due to the available
size area limitation. Complete set of parameters are shown in Table III.

Parameter | Value
---|---
Map resolution | 0.1
Sensor range | 2
Safety distance to obstacles | 0.25
Safety distance to other drones | 1.0
Navigation speed | 0.75
Reached distance threshold | 0.2
Spin speed | 0.1
Yaw threshold | 0.15
Minimum frontier size | 1.5
Maximum frontier size | 3.5
TABLE III: Configuration for real-world experiments.

Fig. 8 shows three exploration experiments with different numbers of drones
from a top view. Exploration algorithm can adapt to various swarm sizes
successfully completing the mission.

Figure 7: Average exploration rate for the real world experiments. The shaded
area shows the standard deviation.

(a) One drone. Time 194.0$s$ and path length 40.64$m$.

(b) Two drones. Time 75.98$s$, path length 37.38$m$ and overlap 28.16$\%$.

(c) Three drones. Time 93.98$s$, path length 47.22$m$ and overlap 37.27$\%$.

Figure 8: Real flight exploration experiments with different number of drones.
Each colored line represents the trajectory followed by each drone, while the
shaded areas symbolizes the explored regions. Colored diamonds shows drones
starting points and black dots represent the obstacles in the environment.

Fig. 7 illustrates how the area discovered evolves over time. As expected,
exploration rate increases with the number of drones. Comprehensive results
for real-world experiments are summarised in Table IV. Each column description
(Time, Area, Path length, Overlap) is same as that in the simulation
experiments.

# | Time [s] | Area [%] | Path Length [m] | Overlap [%]
---|---|---|---|---
1 | 176.0 $\pm$ 31.13 | 92.16 $\pm$ 5.2 | 39.29 $\pm$ 8.48 | -
2 | 78.63 $\pm$ 3.77 | 93.45 $\pm$ 1.5 | 36.9 $\pm$ 2.42 | 30.69 $\pm$ 2.38
3 | 79.25 $\pm$ 13.46 | 96.67 $\pm$ 2.8 | 47.55 $\pm$ 11.5 | 39.23 $\pm$ 11.0
TABLE IV: Results of the real world experiments according to the number of
drones. We report the average and standard deviation for the completion time,
percentage of area explored and total path traveled for the swarm. Best
results are highlighted in bold.

Results show high similarity to the simulated ones. Lowest time, path length
and overlap correspond to the two drones experiment. This result is due to the
size of the world, small for a three drones exploration, where the overlap
increases considerably, and therefore the path length, while the time remains
similar.

(a)

(b)

(c)

(d)

Figure 9: Intra-swarm collision avoidance sequence. (a) A potential crash is
detected; (b) drone navigator at the left is paused and the safety maneuver is
started; (c) safety maneuver ends and (d) the navigator resumes its operation.

Fig. 9 shows an intra-swarm collision avoidance sequence. A potential crash is
detected (Fig. 9(a)), the drone navigator at the left is paused and a safety
maneuver is started, performing a change in altitude to avoid the second drone
(Fig. 9(b)). Once the safety distance is reestablished, the safety maneuver
ends (Fig. 9(c)) and the navigator resumes its operation (Fig. 9(d)), ensuring
the exploration continues safely.

###  IV-D Discussion

####  IV-D1 Swarm size

Results demonstrated that the largest swarm size achieves the fastest times
thanks to our method, which evenly distributes the exploration area. However,
the highest drone number are not the shortest in path due to the overlap
induced. Swarm optimal size energetically speaking (roughly calculated from
path length) depends on the world size and obstacle density, showing for the
simulation experiments an optical number of three drones and for the real
flights an optimal number of two drones.

####  IV-D2 Agent workload

The proposed heuristic distributes equally both the area explored and path
traveled by each agent of the swarm. Reducing the overlap between the areas
explored increases the exploration rate, so an equal distribution of the area
is crucial. Table V shows the impact of each drone in the global algorithm.
Notice that the results displayed refer to each drone individually, instead to
the global system ones showed in the tables before. Values obtained for the
standard deviation reflect a low impact for both area and path length.

# of drones | Area / Drone [%] | Path Length / Drone [m]
---|---|---
1 | 98.98 $\pm$ 0.01 | 986.66 $\pm$ 24.51
2 | 62.37 $\pm$ 4.43 | 486.20 $\pm$ 17.56
3 | 39.13 $\pm$ 2.59 | 304.37 $\pm$ 9.43
5 | 28.23 $\pm$ 3.07 | 184.18 $\pm$ 6.51
7 | 22.17 $\pm$ 2.64 | 148.19 $\pm$ 10.97
TABLE V: Impact of each drone area explored and path travelled, mean and
standard deviation, on the global algorithm for the 0.05 $obs/m^{2}$ density
simulated scenario. Best results are highlighted in bold.

####  IV-D3 Frontier allocation heuristic

Based on the proposed frontier allocation heuristic, we studied the effect of
each term of the optimization problem (Eq. 2). On one hand, cancelling the
second term (which maximizing distance between agents), each drone navigates
to the nearest frontiers which behaves erratically following a pure greedy
heuristic. On the other hand, cancelling the first term (which ensures going
to a near frontier), each navigates to furthest frontier drawing a spiral
around the map center where the exploration ends. Fig. 6 shows a top view
exploration result cancelling each term of the heuristic.

##  V Conclusions and Future Work

In this work, we propose a coordination algorithm for a nano-drones swarm to
address the minimal-sensing exploration problem. Our exploration pipeline
leverages a novel hybrid frontier range bug algorithm that effectively handles
limited sensing capabilities. This strategy allows complete exploration using
just four single-beam range sensors per nano drone. Additionally, safety is
ensured via a simple intra-swarm collision avoidance algorithm that prevents
the drones from colliding with each other, especially during an overlap of the
exploration area.

We evaluated our algorithm across various scenarios, including both simulated
environments and real-world settings, and varied parameters such as world
size, obstacle density, and swarm size. The results confirmed successful
comprehensive explorations and demonstrated the potential advantages of using
swarms of nano-drones. Our frontier allocation heuristic also showed an equal
distribution of explored areas and paths traveled for each agent in the swarm,
therefore reducing the exploration time as the number of drones increases.

As a part of future work, we aim to decentralize our algorithm to develop a
more scalable approach. Decentralization will require better environmental
representations, which are crucial for sharing information among the swarm and
minimizing the data transmission to reduce the memory footprint, thus enabling
the algorithm to run onboard. Furthermore, we plan to test our exploration
algorithm under conditions of noisy state estimations derived from onboard
sensor data.

## References

  * [1] D. Palossi, J. Singh, M. Magno, and L. Benini, “Target following on nano-scale unmanned aerial vehicles,” in _2017 7th IEEE international workshop on advances in sensors and interfaces (IWASI)_. IEEE, 2017, pp. 170–175.
  * [2] X. Zhang, B. Xian, B. Zhao, and Y. Zhang, “Autonomous flight control of a nano quadrotor helicopter in a gps-denied environment using on-board vision,” _IEEE Transactions on Industrial Electronics_ , vol. 62, no. 10, pp. 6392–6403, 2015.
  * [3] D. Jaisinghani, T. U. Rehman, R. Mulkey, and A. Berns, “Iot in the air: Thread-enabled flying iot network for indoor environments,” in _2023 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops)_. IEEE, 2023, pp. 142–147.
  * [4] D. Guzzoni, A. Cheyer, L. Julia, and K. Konolige, “Many robots make short work: Report of the sri international mobile robot team,” _AI magazine_ , vol. 18, no. 1, pp. 55–55, 1997.
  * [5] W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider, “Coordinated multi-robot exploration,” _IEEE Transactions on robotics_ , vol. 21, no. 3, pp. 376–386, 2005.
  * [6] C. Zhu, R. Ding, M. Lin, and Y. Wu, “A 3d frontier-based exploration tool for mavs,” in _2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI)_. IEEE, 2015, pp. 348–352.
  * [7] H. Oleynikova, Z. Taylor, R. Siegwart, and J. Nieto, “Safe local exploration for replanning in cluttered unknown environments for microaerial vehicles,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 3, pp. 1474–1481, 2018.
  * [8] B. Yamauchi, “A frontier-based approach for autonomous exploration,” in _Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA’97.’Towards New Computational Principles for Robotics and Automation’_. IEEE, 1997, pp. 146–151.
  * [9] A. Mannucci, S. Nardi, and L. Pallottino, “Autonomous 3d exploration of large areas: A cooperative frontier-based approach,” in _Modelling and Simulation for Autonomous Systems: 4th International Conference, MESAS 2017, Rome, Italy, October 24-26, 2017, Revised Selected Papers 4_. Springer, 2018, pp. 18–39.
  * [10] B. Zhou, Y. Zhang, X. Chen, and S. Shen, “Fuel: Fast uav exploration using incremental frontier structure and hierarchical planning,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 779–786, 2021.
  * [11] B. Zhou, H. Xu, and S. Shen, “Racer: Rapid collaborative exploration with a decentralized multi-uav system,” _IEEE Transactions on Robotics_ , 2023.
  * [12] Y. Hui, X. Zhang, H. Shen, H. Lu, and B. Tian, “Dppm: Decentralized exploration planning for multi-uav systems using lightweight information structure,” _IEEE Transactions on Intelligent Vehicles_ , 2023.
  * [13] L. Bartolomei, L. Teixeira, and M. Chli, “Fast multi-uav decentralized exploration of forests,” _IEEE Robotics and Automation Letters_ , 2023.
  * [14] H. Zhou, Z. Hu, S. Liu, and S. Khan, “Efficient 2d graph slam for sparse sensing,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2022, pp. 6404–6411.
  * [15] V. Niculescu, T. Polonelli, M. Magno, and L. Benini, “Nanoslam: Enabling fully onboard slam for tiny robots,” _IEEE Internet of Things Journal_ , 2023.
  * [16] K. McGuire, C. De Wagter, K. Tuyls, H. Kappen, and G. C. de Croon, “Minimal navigation solution for a swarm of tiny flying robots to explore an unknown environment,” _Science Robotics_ , vol. 4, no. 35, p. eaaw9710, 2019.
  * [17] B. P. Duisterhof, S. Li, J. Burgués, V. J. Reddi, and G. C. de Croon, “Sniffy bug: A fully autonomous swarm of gas-seeking nano quadcopters in cluttered environments,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 9099–9106.
  * [18] L. Lamberti, L. Bompani, V. J. Kartsch, M. Rusci, D. Palossi, and L. Benini, “Bio-inspired autonomous exploration policies with cnn-based object detection on nano-drones,” in _2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, 2023, pp. 1–6.
  * [19] M. Pourjabar, M. Rusci, L. Bompani, L. Lamberti, V. Niculescu, D. Palossi, and L. Benini, “Multi-sensory anti-collision design for autonomous nano-swarm exploration,” _arXiv preprint: 2312.13086_ , 2023.
  * [20] M. Fernandez-Cortizas, M. Molina, P. Arias-Perez, R. Perez-Segui, D. Perez-Saura, and P. Campoy, “Aerostack2: A software framework for developing multi-robot aerial systems,” _arXiv preprint arXiv:2303.18237_ , 2023.
  * [21] E. Magid and E. Rivlin, “Cautiousbug: A competitive algorithm for sensory-based robot navigation,” in _2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)(IEEE Cat. No. 04CH37566)_ , vol. 3. IEEE, 2004, pp. 2757–2762.
  * [22] H. P. Moravec, “Sensor fusion in certainty grids for mobile robots,” _AI magazine_ , vol. 9, no. 2, pp. 61–61, 1988.
  * [23] F. Furrer, M. Burri, M. Achtelik, and R. Siegwart, _Robot Operating System (ROS): The Complete Reference (Volume 1)_. Cham: Springer International Publishing, 2016, ch. RotorS—A Modular Gazebo MAV Simulator Framework, pp. 595–625.


# VAuLT: Augmenting the Vision-and-Language Transformer
for Sentiment Classification on Social Media

###### Abstract

We propose the Vision-and-Augmented-Language Transformer (VAuLT). VAuLT is an
extension of the popular Vision-and-Language Transformer (ViLT), and improves
performance on vision-and-language (VL) tasks that involve more complex text
inputs than image captions while having minimal impact on training and
inference efficiency. ViLT, importantly, enables efficient training and
inference in VL tasks, achieved by encoding images using a linear projection
of patches instead of an object detector. However, it is pretrained on
captioning datasets, where the language input is simple, literal, and
descriptive, therefore lacking linguistic diversity. So, when working with
multimedia data in the wild, such as multimodal social media data, there is a
notable shift from captioning language data, as well as diversity of tasks. We
indeed find evidence that the language capacity of ViLT is lacking. The key
insight and novelty of VAuLT is to propagate the output representations of a
large language model (LM) like BERT to the language input of ViLT. We show
that joint training of the LM and ViLT can yield relative improvements up to
$20\%$ over ViLT and achieve state-of-the-art or comparable performance on VL
tasks involving richer language inputs and affective constructs, such as for
Target-Oriented Sentiment Classification in TWITTER-2015 and TWITTER-2017, and
Sentiment Classification in MVSA-Single and MVSA-Multiple. Our code is
available at https://github.com/gchochla/VAuLT.

Index Terms—  Vision-and-Language, Transformers, Social media, Sentiment
Classification

##  1 Introduction

Fig. 1: VAuLT propagates representations from a LM to a VLM in a modular
fashion. We show that even with little tuning data, language representations
can be effectively used to significantly improve the performance of ViLT on
tasks with greater linguistic and construct diversity than captioning
datasets.

The study of social media can have positive societal outcomes. Interest in the
importance of emotion has been growing beyond science [8] to law [27], and
politics [26]. Social media users readily express their emotions about their
experiences and world events through multimedia content such as videos,
images, memes, and raw text. This allows researchers to use machine learning
(ML) methods to study, for instance, the dynamics of public perception and
opinion and to provide feedback to policy makers and inform future actions
[12]. Social media are also ripe with opportunities for social manipulation
[4]. This manipulation can be personalized based on user data [1], or use
network effects [11]. Mitigating these risks and identifying widespread
manipulation attempts hence becomes pivotal.

Due to the massive volume of data and the dynamic nature of social media,
constant streams of data are required, thus efficiency is of the essence. In
addition, multimedia content necessitates multimodal modeling, as users can
use these extra degrees of freedom to convey complex and conflicting meanings,
for instance in irony. Moreover, a multimodal model should be able to handle a
subset of its input modalities if a post is missing the rest [24].

Many state-of-the-art vision-and-language models (VLM), e.g., VL-BERT [25] and
ViLBERT [17], contain an object detector, such as Faster-RCNN [22], to compute
input visual features. Object detectors are costly to run relative to the rest
of the pipeline [15], which can be prohibitive for social media applications.
Hence, we turn to the Vision-and-Language Transformer (ViLT) [15], whose
visual input consists of linearly projected image patches.

Regardless, these models, designed to understand and extract information from
multimedia content such as vision and language, are frequently trained only on
images and their captions crawled from the web. Image captions are a weak form
of language supervision, often describing literal content with simple syntax
and little subtlety, deviating substantially from the text of social media
posts.

In this paper, we propose the Vision-and-Augmented-Language Transformer
(VAuLT), which directly addresses the impoverished language representations of
ViLT by processing the language input through a pretrained large language
model (LM) (Figure 1). We find that VAuLT is able to outperform ViLT on a
variety of tasks involving affective constructs common in social media,
including TWITTER-2015, TWITTER-2017 [28], and MVSA [21].

Our key contributions can be summarized as follows:

  * •

In VAuLT, we stack Transformer architectures, a pretrained LM and VLM, and
jointly train them end-to-end, yielding substantial performance gains from
little tuning data.

  * •

We show that VAuLT competes with or outperforms state-of-the-art methods for
the social media analysis tasks examined.

  * •

We provide evidence that the performance trade-offs of ViLT and VAuLT depend
on the complexity of the image and language components commensurate with the
relative richness of, and variety within, the modalities in the source and
target domains, as well as the tasks themselves.

##  2 Related Work

###  2.1 Language Transformers

Transformers pretrained on general-purpose text grants them the ability to be
used as backbones for many downstream tasks [6]. Such models can also be
pretrained on more specialized corpora to improve their transferability to
specific domains, like BERTweet [20], a model trained on tweets.

###  2.2 Vision-and-Language (VL) Transformers

Similar to language transformers, VL transformers [25, 17] are trained with
multiple input modalities on web-crawled captions, and yield state-of-the-art
results on many multimodal tasks [2]. These models frequently use region-of-
interest (ROI) features extracted from a pretrained object detector [22] as
their Transformer’s visual inputs. However, this visual embedding step is
computationally expensive during training and inference [15], requiring
caching of features. ViLT [15], based on the Vision Transformer (ViT) [7],
proposed using image patches as visual input to the Transformer model instead.
This results in slightly worse model performance, but is much more
computationally efficient. However, ViLT also has limited language
understanding capacity due to being initialized from ViT and pretrained solely
on image caption data. VAuLT overcomes this issue by replacing ViLT’s language
embedding inputs with features extracted from a large LM pretrained on greater
linguistic diversity, which can also be selected to more closely suit the
needs of the downstream task.

###  2.3 Affective Analysis on Social Media

Researchers tend to focus on single modalities when analyzing emotion and
sentiment in social media posts, such as text-only [19], and image-only [23]
datasets.

Emotion recognition from text has long relied on word-counting techniques [9],
which can be deployed at scale but disregard context. LSTMs [3] and
Transformers [5] capture context and provide superior performance with less
interpretability.

On the other hand, multimodal affect modeling tasks with social media have
predominantly focused on sentiment [28, 21, 13]. [28] have annotated tweets
with their corresponding images for sentiment expressed towards entities in
the text, resulting in the Target-oriented Sentiment Classification (TMSC)
task and the TWITTER-15 and TWITTER-17 datasets. Similarly, MVSA [21] has
annotations for sentiment expressed in the text and the image of a tweet.
User-provided tags have been used as “self-reports” of emotion in scraped
multimodal data from Tumblr [13].

The proposed approaches for the aforementioned tasks typically involve
dedicated architectures or targeted modifications of VL Transformers. An
example of the former is TomBERT [28] for TMSC. TomBERT consists of multiple
components: first, a ResNet [10] extracts visual features. Then, a cross-
attention layer is used to query these visual features using target embeddings
extracted from BERT [6]. Parallel to the visual feature extraction, the text
sequence is passed though another BERT, and is concatenated with the refined
visual features and fed to a multimodal encoder, also a BERT.

##  3 Methodology

###  3.1 Task Definitions

####  3.1.1 Sentiment Classification

For our purposes, “Sentiment Classification” corresponds to classifying an
image and text pair as positive, neutral, or negative.

####  3.1.2 Target-oriented Sentiment Classification (TMSC)

TMSC extends the basic sentiment classification formulation to opinion
expressed toward given targets within the text of multimodal tweets. In our
setting, sentiment targets were repurposed from types of named entities, and
an input tweet can contain multiple targets.

###  3.2 Vision-and-Language Transformer (ViLT)

ViLT is a multimodal transformer. The language component of ViLT follows
conventional practices and embeds input tokens with a look-up table. On the
other hand, the visual component of ViLT follows ViT [7], segmenting each
image into non-overlapping square patches, flattening the resulting values,
and mapping them to the input space using a linear projection.

ViLT is pretrained on image captioning datasets like MSCOCO [16]. Its
pretraining objectives include: image-text matching and word-patch alignment,
and masked language modeling and whole word masking. The former group of
objectives focuses on enforcing joint modeling of the two modalities, while
the latter is centered on the language understanding of the model. Explicit
language training is necessary since the model is initialized from ViT
weights, itself trained on images, in contrast to previous works that
initializes weights from LMs [25, 17], thus ViLT’s language understanding
comes solely from image-captioning datasets.

###  3.3 Vision-and-Augmented Language Transformer (VAuLT)

The proposed VAuLT can use any LM that produces token embeddings for tokenized
text, irrespective of the specific tokenizer. We have this requirement because
we use the sequence of embeddings produced by the LM to replace the canonical
language input of ViLT. Therefore, we are essentially substituting the
context-free representations from the lookup table of ViLT, with context-aware
representations [6] from the output layer of a LM. Images are embedded in the
canonical fashion with ViLT’s trained linear projection of patches.

Concretely, given an input image-text pair, and a specific LM and its
tokenizer, we tokenize the input text sequence and pass this through the LM to
produce its output contextual embeddings. Along with these embeddings, we pass
these two input streams through ViLT. Note that position embeddings, etc., are
added in both ViLT’s and the LM’s forward pass.

| TWITTER-15 | TWITTER-17 | MVSA-M | MVSA-S
---|---|---|---|---
Model | Acc | mac-F1 | Acc | mac-F1 | Acc | w-F1 | Acc | w-F1
ViLT |  $70.5{\scriptstyle\pm 1.3}$ |  $62.6{\scriptstyle\pm 2.5}$ |  $62.6{\scriptstyle\pm 0.1}$ |  $58.1{\scriptstyle\pm 0.7}$ |  $69.1{\scriptstyle\pm 0.8}$ |  $67.0{\scriptstyle\pm 0.3}$ |  $74.4{\scriptstyle\pm 1.5}$ |  $73.7{\scriptstyle\pm 1.6}$
VAuLT† |  $75.6{\scriptstyle\pm 0.8}$ |  $70.0{\scriptstyle\pm 1.7}$ |  $70.2{\scriptstyle\pm 0.4}$ |  $67.8{\scriptstyle\pm 0.1}$ |  $70.0{\scriptstyle\pm 0.7}$ |  $68.9{\scriptstyle\pm 0.7}$ |  $\mathbf{78.0}{\scriptstyle\pm 1.2}$ |  $77.4{\scriptstyle\pm 1.4}$
VAuLT⋆ |  $\mathbf{77.5}{\scriptstyle\pm 0.4}$ |  $\mathbf{72.9}{\scriptstyle\pm 0.5}$ |  $71.0{\scriptstyle\pm 0.5}$ |  $\mathbf{69.5}{\scriptstyle\pm 0.7}$ |  $70.3{\scriptstyle\pm 1.6}$ |  $67.0{\scriptstyle\pm 2.9}$ |  $72.8{\scriptstyle\pm 5.6}$ |  $71.8{\scriptstyle\pm 5.8}$
EF-CaTr-BERT [14] |  $\mathbf{77.9}{\scriptstyle\pm 0.8}$ |  $\mathbf{73.9}{\scriptstyle\pm 0.8}$ |  $\mathbf{72.3}{\scriptstyle\pm 0.3}$ |  $\mathbf{70.2}{\scriptstyle\pm 0.2}$ | - | - | - | -
ITIN [29] | - | - | - | - | 73.5 | - | 75.2 | -
Table 1: Direct comparison between ViLT, VAuLT (†: w/ BERT, bert-base-uncased,
or ⋆: w/ BERTweet, vinai/bertweet-base), and the state-of-the-art on each
benchmark. Bold indicates best performance based on ranges, where available.

We use LMs like BERT and BERTweet that have not been trained on similar
datasets with ViLT or tokenize text in the same manner as ViLT does. That is
to say, the language tokens might not correspond to the tokens ViLT has been
trained with.

##  4 Experiments

Overall, our goal is to show that VAuLT improves upon ViLT on multimodal,
small-scale, affective datasets derived from social media, in our case
Twitter. More than that, we also show that ViLT can achieve competitive
performance over dedicated architectures for such datasets, and VAuLT can even
exceed their performance.

###  4.1 Datasets

We use TWITTER-15 and TWITTER-17 [28] annotated for the task of TMSC. The
former contains 1548 positive, 630 negative and 3169 neutral examples. The
latter contains 2516 positive, 728 negative and 2728 neutral examples. We use
the splits provided by the authors. Accuracy and macro F1 are typical
evaluation criteria. We predict for one target at a time, even if the tweet
contains multiple. We follow [28] in replacing the target of interest with the
placeholder $T$, and appending the target as a second sequence.

We also evaluate our model on MVSA-Multiple and MVSA-Single [21], pre-
processed for Sentiment Classification. Initially, both datasets contain
annotations for the sentiment of both the image and the text of a tweet. MVSA-
Single has annotations from solely one annotator, while MVSA-Multiple utilizes
three separate annotators, plus more examples. We merge the annotations into a
single annotation and aggregate across annotators, as is customary [29]. The
filtered MVSA-Single contains 2683 positive, 460 negative and 1358 neutral
examples. The filtered MVSA-Multiple contains 11318 positive, 4408 negative
and 1298 neutral examples. We also had to remove 3 additional samples from
MVSA-Multiple because of corrupted images (example IDs: 3151, 3910 and 5995).
Since canonical splits are not provided and evaluation criteria are not well-
defined, we follow previous work in randomly splitting the data 8:1:1 [29] and
use accuracy to compare. We also include the weighted F1 score of our methods
as our best guess as to what other methods are reporting as merely “F1 score”.

###  4.2 Implementation details

We use Python v3.7.4, PyTorch v1.11.0, and transformers v4.19.2.

We keep our learning rate at $2\cdot 10^{-5}$ unless specified. We use linear
warm-up for $10\%$ of the training steps and then linear decay to $0$. In re-
implementations of published models, we use the specified hyperparameter
configuration.

Test performance (mean and standard deviation) is reported after 3 different
training runs with fixed hyperparameters. The main tuning of all of the
hyperparameters but the number of training epochs was performed on TWITTER-15
and TWITTER-17. We searched for whether to use bias correction in AdamW,
selecting no bias correction, the number of epochs (ran for 15 epochs and
picked the best performing one based on average accuracy and macro F1 for
MVSA-Multiple and MVSA-Single, and $\\{8,15,25\\}$ for TWITTER-15 and
TWITTER-17), and whether to integrate the placeholder $T$ to the tokenizer as
a standalone token in TWITTER-15 and TWITTER-17 (yes for VAuLT; no for ViLT,
existing baselines, and variants thereof).

We find that divergence in the training of VAuLT can rarely occur, but those
runs can be filtered by observing degradation in the training metrics. While
we had to correct for such artifacts during development, no such instances
occurred on the test sets.

We use simple random cropping instead of the augmentation utilized in ViLT for
simplicity. We use augmentation in all cases where ViLT’s linear projection is
solely used to extract image embeddings. We use
ekphrasis111https://github.com/cbaziotis/ekphrasis to pre-process the text of
the tweets, but we remove the special characters added by the library around
the names of the tags (e.g., when “$<$user$>$” would have been the original
substitute for the actual Twitter handle appearing in a tweet, we simple use
“user”). We also substitute emojis for their plain-text descriptions in
parentheses, when they would be dropped by a tokenizer. In particular, in our
work, only BERTweet’s tokenization preserves emojis. Because the text of
TWITTER-15 and TWITTER-17 has been independently pre-processed, we do not use
ekphrasis on them.

We use 2 NVIDIA GeForce GTX 1080 Ti GPUs (12GB of memory). We only use one GPU
per model, limiting our training batch sizes to 16 or 32, always choosing the
maximum possible of the two.

###  4.3 Comparison with ViLT

First and foremost, let us focus on the comparison of the evaluation metrics
between ViLT and VAuLT, where we indeed find that VAuLT exceeds ViLT’s
performance across all examined affective social media data. Results can be
seen in Table 1. We can see that VAuLT with BERTweet improves upon ViLT in
TWITTER-15 and TWITTER-17, with relative improvements between $9.9\%$ and
$19.6\%$. VAuLT with BERT also provides substantial improvements but still
lags behind compared to BERTweet, and only we find overlapping ranges across
the two versions of VAuLT on TWITTER-17’s accuracy.

Smaller yet still substantial improvements are observed in MVSA-Multiple and
MVSA-Single. In particular, for this set of benchmarks, VAuLT with BERT
performs favorably compared to ViLT and VAuLT with BERTweet. In fact, for the
latter, we observe large fluctuations in performance, emphasized by the large
deviation presented in Table 1. Otherwise, performance is analogous to VAuLT’s
with BERT. Quantitatively, improvements over ViLT are up to approximately 5%.
It has to be noted that ranges are overlapping for VAuLT and ViLT in MVSA-
Multiple accuracy.

###  4.4 Comparisons with State of the Art

For completeness, we also compare VAuLT and ViLT with state-of-the-art models
for the examined benchmarks. We do not elaborate on the state-of-the-art
models because of the variety of tasks, as well as them being not central to
the main goals of our work. We find that VAuLT can outperform or be
competitive with dedicated state-of-the-art models in terms of our evaluation
criteria.

We observe, in Table 1, that VauLT with BERTweet has overlapping performance
ranges with the state-of-the-art model, EF-CaTr-BERT, on TWITTER-15 and
TWITTER-17, except for accuracy in TWITTER-17.

For MVSA-Multiple and MVSA-Single, we have mixed results. We achieve state-of-
the-art results for MVSA-Single, where we improve upon the previous best
accuracy by 3.8 absolute percentage points (note that our best-guess F1 score
is also the state of the art if our assumption is correct). In MVSA-Multiple,
our models are still outperformed by the competition. Caveats in the
evaluation in MVSA include the random splits that are used in the literature,
often with different cardinalities in the different splits, while evaluation
criteria remain opaque, and pre-processing, aggregation and normalization
techniques could differ between different works.

###  4.5 Ablation Studies

####  4.5.1 Frozen LM

| TWITTER-15 | TWITTER-17
---|---|---
Model | Acc | mac-F1 | Acc | mac-F1
ViLT |  $70.5{\scriptstyle\pm 1.3}$ |  $62.6{\scriptstyle\pm 2.5}$ |  $62.6{\scriptstyle\pm 0.1}$ |  $58.1{\scriptstyle\pm 0.7}$
VAuLT† |  $75.6{\scriptstyle\pm 0.8}$ |  $70.0{\scriptstyle\pm 1.7}$ |  $\mathbf{70.2}{\scriptstyle\pm 0.4}$ |  $67.8{\scriptstyle\pm 0.1}$
VAuLT⋆,f |  $68.8{\scriptstyle\pm 0.6}$ |  $58.8{\scriptstyle\pm 1.5}$ |  $64.0{\scriptstyle\pm 0.9}$ |  $61.0{\scriptstyle\pm 0.6}$
VAuLT⋆ |  $\mathbf{77.5}{\scriptstyle\pm 0.4}$ |  $\mathbf{72.9}{\scriptstyle\pm 0.5}$ |  $\mathbf{71.0}{\scriptstyle\pm 0.5}$ |  $\mathbf{69.5}{\scriptstyle\pm 0.7}$
Table 2: Comparing ViLT and VAuLT (f: using a frozen LM, and †: w/ BERT, bert-
base-uncased, or ⋆: w/ BERTweet, vinai/bertweet-base) on TWITTER-15 and
TWITTER-17. Bold indicates best based on ranges.

We first examine whether ViLT can “read” the outputs of a LM without any
adjustments on the part of the latter. That is to say, we keep the LMs frozen.
[18] showed that early layers of transformers change significantly less than
later layers during fine-tuning, implying that fine-tuning of the LM in VAuLT
may be unnecessary. However, we find joint training to be essential.

Results can be seen in Table 2. Overall, fine-tuning of the language model
appears essential, since we see such notable degradation in performance, as
VAuLT with a frozen LM drops to the level or even below ViLT. This
demonstrates the necessity of fine-tuning the LMs in conjunction with ViLT.

####  4.5.2 Deep Vision vs. Deep Language

In this section, we present an experiment supporting the hypothesis that the
complexity of the modality-specific components and their effect on the final
performance depends on the domain addressed, and that the linear projections
used by ViLT and ViT do not inherently restrict the model’s performance. We do
so by introducing and studying two variants of TomBERT we call TomVAuLT and
TomViLT, solely for the purposes of examining our hypothesis in this section.

TomVAuLT extends TomBERT by replacing the multimodal encoder with ViLT. The
multimodal encoder in TomBERT is responsible for the final classification, and
its input consists of the queried features from ResNet and the contextual
embeddings of the tweet from BERT. In this way, we replace the visual
embeddings of ViLT with ResNet features, while we also retain the BERT that
pre-processes the tweet before the multimodal encoder, giving us VAuLT in that
regard. By disposing of that BERT from TomVAuLT, we arrive at the other
variant, TomViLT, where only ViLT is used to process the text inputs. We
compare these with ViLT and VAuLT using BERT on the dev sets of TWITTER-15 and
TWITTER-17. In this manner, we present all possible configurations:  i) ViLT:
no deep encoder,  ii) VAuLT: deep language encoder,  iii) TomViLT: deep visual
encoder,  iv) TomVAuLT: both deep encoders.

Our results, shown in Table 3, demonstrate that having a deep visual encoder
actually hurts performance in the presence of a deep language encoder,
contrasting previous assumptions that transferring a “strong” visual
vocabulary is essential, which to the best of our knowledge is a novel
analytical result.

| TWITTER-15 | TWITTER-17
---|---|---
Model | Acc | mac-F1 | Acc | mac-F1
TomViLT |  $73.2{\scriptstyle\pm 0.7}$ |  $66.1{\scriptstyle\pm 1.3}$ |  $67.3{\scriptstyle\pm 0.5}$ |  $64.4{\scriptstyle\pm 0.7}$
ViLT |  $69.6{\scriptstyle\pm 1.0}$ |  $60.3{\scriptstyle\pm 1.5}$ |  $64.0{\scriptstyle\pm 1.2}$ |  $58.0{\scriptstyle\pm 1.5}$
TomVAuLT |  $73.2{\scriptstyle\pm 0.5}$ |  $67.1{\scriptstyle\pm 0.4}$ |  $67.3{\scriptstyle\pm 0.9}$ |  $61.1{\scriptstyle\pm 0.9}$
VAuLT |  $\mathbf{75.0}{\scriptstyle\pm 0.6}$ |  $\mathbf{69.0}{\scriptstyle\pm 0.9}$ |  $\mathbf{67.8}{\scriptstyle\pm 1.0}$ |  $\mathbf{64.9}{\scriptstyle\pm 0.9}$
Table 3: Comparing ViLT, VAuLT, TomViLT and TomVAuLT on TWITTER-15 and
TWITTER-17. Bold indicates best based on means only.

##  5 Conclusion

In this work, we introduce VAuLT. It utilizes a large pretrained LM, such as
BERT, to propagate enhanced language representations to ViLT in order to
perform multimodal tasks. We find that this pre-processing to be integral, as
ViLT’s impoverished language representations, owning to its limited language
exposure during pretraining, cannot be easily fine-tuned to perform out-of-
distribution tasks, such as affective analysis on multimodal social media
data. Our approach obviates the requirements for extensive pretraining of ViLT
on the desired domains, as the appropriate LMs can bridge the distribution
shift between source and target. Importantly, we demonstrate state-of-the-art
or competitive performance of VAuLT.

Our work opens up several research directions. Anecdotal evidence from
experiments not presented in this work indicate VAuLT struggles with pure
reasoning tasks compared to ViLT, a direction left for future research.
Second, we observe rare divergences during training. This hints at possible
misalignment of the output space of the LM and the input space of ViLT. Third,
we offer some evidence that shallow visual encoders but deep language encoders
can achieve better classification performance to alternatives, a paradigm that
could be investigated in greater detail. Finally, VAuLT can be used in
multilingual settings with the proper LM choice.

Despite the utility of multimodal emotion recognition on social media, as
discussed earlier, multiple ethical concerns can be raised. These include
utilization of these models for the identification and suppression of dissent
and free speech beyond text, such as in the form of images and memes, as well
as their general integration in the aforementioned social manipulation tools,
rendering them more powerful with the inclusion of visual capabilities.

##  6 Acknowledgements

We thank Kristina Lerman and Keith Burghardt for their valuable guidance. This
project was funded in part by DARPA under contract HR001121C0168.

## References

  * [1] Alfano, M., Sullivan, E., and Fard, A. E. Ethical pitfalls for natural language processing in psychology.  The Atlas of Language Analysis in Psychology (2022).

  * [2] Antol, S., Agrawal, A., Lu, J., Mitchell, M., Batra, D., Lawrence Zitnick, C., and Parikh, D. Vqa: Visual question answering.  In Proceedings of the IEEE international conference on computer vision (2015), pp. 2425–2433.
  * [3] Baziotis, C., Nikolaos, A., Chronopoulou, A., Kolovou, A., Paraskevopoulos, G., Ellinas, N., Narayanan, S., and Potamianos, A. Ntua-slp at semeval-2018 task 1: Predicting affective content in tweets with deep attentive rnns and transfer learning.  In Proceedings of The 12th International Workshop on Semantic Evaluation (2018), pp. 245–255.
  * [4] Bradshaw, S., and Howard, P. N. The global organization of social media disinformation campaigns.  Journal of International Affairs 71, 1.5 (2018), 23–32.
  * [5] Chochlakis, G., Mahajan, G., Baruah, S., Burghardt, K., Lerman, K., and Narayanan, S. Leveraging label correlations in a multi-label setting: A case study in emotion.  arXiv preprint arXiv:2210.15842 (2022).
  * [6] Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805 (2018).
  * [7] Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929 (2020).
  * [8] Dukes, D., Abrams, K., Adolphs, R., Ahmed, M. E., Beatty, A., Berridge, K. C., Broomhall, S., Brosch, T., Campos, J. J., Clay, Z., et al. The rise of affectivism.  Nature human behaviour 5, 7 (2021), 816–820.
  * [9] Garten, J., Hoover, J., Johnson, K. M., Boghrati, R., Iskiwitch, C., and Dehghani, M. Dictionaries and distributions: Combining expert knowledge and large scale textual data content analysis.  Behavior research methods 50, 1 (2018), 344–361.
  * [10] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition (2016), pp. 770–778.
  * [11] Hoover, J., Atari, M., Mostafazadeh Davani, A., Kennedy, B., Portillo-Wightman, G., Yeh, L., and Dehghani, M. Investigating the role of group-based morality in extreme behavioral expressions of prejudice.  Nature Communications 12, 1 (2021), 1–13.
  * [12] Hoover, J., Johnson, K., Boghrati, R., Graham, J., and Dehghani, M. Moral framing and charitable donation: Integrating exploratory social media analyses and confirmatory experimentation.  Collabra: Psychology 4, 1 (2018).
  * [13] Hu, A., and Flaxman, S. Multimodal sentiment analysis to explore the structure of emotions.  In proceedings of the 24th ACM SIGKDD international conference on Knowledge Discovery & Data Mining (2018), pp. 350–358.
  * [14] Khan, Z., and Fu, Y. Exploiting bert for multimodal target sentiment classification through input space translation.  In Proceedings of the 29th ACM International Conference on Multimedia (2021), pp. 3034–3042.
  * [15] Kim, W., Son, B., and Kim, I. Vilt: Vision-and-language transformer without convolution or region supervision.  In International Conference on Machine Learning (2021), PMLR, pp. 5583–5594.
  * [16] Lin, T.-Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P., and Zitnick, C. L. Microsoft coco: Common objects in context.  In European conference on computer vision (2014), Springer, pp. 740–755.
  * [17] Lu, J., Batra, D., Parikh, D., and Lee, S. Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  Advances in neural information processing systems 32 (2019).
  * [18] Merchant, A., Rahimtoroghi, E., Pavlick, E., and Tenney, I. What happens to bert embeddings during fine-tuning?  In Proceedings of the Third BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (2020), pp. 33–44.
  * [19] Mohammad, S., Bravo-Marquez, F., Salameh, M., and Kiritchenko, S. Semeval-2018 task 1: Affect in tweets.  In Proceedings of the 12th international workshop on semantic evaluation (2018), pp. 1–17.
  * [20] Nguyen, D. Q., Vu, T., and Nguyen, A. T. Bertweet: A pre-trained language model for english tweets.  arXiv preprint arXiv:2005.10200 (2020).
  * [21] Niu, T., Zhu, S., Pang, L., and El-Saddik, A. Sentiment analysis on multi-view social data.  In MultiMedia Modeling (2016), p. 15–27.
  * [22] Ren, S., He, K., Girshick, R., and Sun, J. Faster r-cnn: Towards real-time object detection with region proposal networks.  Advances in neural information processing systems 28 (2015).
  * [23] Sharma, C., Bhageria, D., Scott, W., Pykl, S., Das, A., Chakraborty, T., Pulabaigari, V., and Gamback, B. Semeval-2020 task 8: Memotion analysis–the visuo-lingual metaphor!  arXiv preprint arXiv:2008.03781 (2020).
  * [24] Srinivasan, T., Chang, T.-Y., Alva, L. L. P., Chochlakis, G., Rostami, M., and Thomason, J. Climb: A continual learning benchmark for vision-and-language tasks.  arXiv preprint arXiv:2206.09059 (2022).
  * [25] Su, W., Zhu, X., Cao, Y., Li, B., Lu, L., Wei, F., and Dai, J. Vl-bert: Pre-training of generic visual-linguistic representations.  arXiv preprint arXiv:1908.08530 (2019).
  * [26] Wahl-Jorgensen, K. Emotions, media and politics.  John Wiley & Sons, 2019.
  * [27] Wistrich, A. J., Rachlinski, J. J., and Guthrie, C. Heart versus head: Do judges follow the law of follow their feelings.  Tex. L. Rev. 93 (2014), 855.
  * [28] Yu, J., and Jiang, J. Adapting bert for target-oriented multimodal sentiment classification.  In IJCAI (2019).
  * [29] Zhu, T., Li, L., Yang, J., Zhao, S., Liu, H., and Qian, J. Multimodal sentiment analysis with image-text interaction network.  IEEE Transactions on Multimedia (2022).