Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

CLEF 2023: Conference and Labs of the Evaluation Forum, September 18–21, 2023,
Thessaloniki, Greece

<EMAIL_ADDRESS><EMAIL_ADDRESS>
# PULSAR at MEDIQA-Sum 2023: Large Language Models Augmented by Synthetic
Dialogue Convert Patient Dialogues to Medical Records

Viktor Schlegel  Hao Li  Yuping Wu  Anand Subramanian  Thanh-Tung Nguyen
Abhinav Ramesh Kashyap  Daniel Beck  Xiaojun Zeng  Riza Theresa Batista-
Navarro  Stefan Winkler  Goran Nenadic  ASUS Intelligent Cloud Services
(AICS), Singapore.  Dept. of Computer Science, University of Manchester,
United Kingdom.  Dept. of Computer Science, National University of Singapore,
Singapore.  School of Computing and Information Systems, University of
Melbourne, Australia.

(2023)

###### Abstract

This paper describes PULSAR, our system submission at the ImageClef 2023
MediQA-Sum task on summarising patient-doctor dialogues into clinical records.
The proposed framework relies on domain-specific pre-training, to produce a
specialised language model which is trained on task-specific natural data
augmented by synthetic data generated by a black-box LLM. We find limited
evidence towards the efficacy of domain-specific pre-training and data
augmentation, while scaling up the language model yields the best performance
gains. Our approach was ranked second and third among 13 submissions on task B
of the challenge. Our code is available at https://github.com/yuping-
wu/PULSAR.

###### keywords:

Abstractive Summarisation AI for Healthcare Dialogue Summarisation Natural
Language Processing

##  1 Introduction

With the recent successes of generative large language models (LLMs) on a
variety of tasks [1] and domains [2], even in the face of data scarcity [3],
there is vivid interest in identifying potential application scenarios that
could benefit from the power of LLMs. One of the promising domains is
healthcare [4] as many administrative tasks involve the transformation of
textual data. LLM-based approaches that assist hospital staff in repetitive
administrative tasks have the potential to improve operational efficiency and
documentation quality, optimise revenue streams, reduce cognitive load on
healthcare experts, and ultimately result in better and more effective patient
care [5].

A range of different scenarios have been investigated for the suitability of
LLM-based assistance, such as summarising patient progress notes as discharge
summaries [6] or identifying problems that need treatment during a patient’s
hospital course [7]. One of the potential tasks is summarising doctor-patient
dialogue as medical records [8]. Dialogue summarisation, an established task
in the Natural Language Processing (NLP) community, aims to identify salient
topics in a multi-turn dialogue [9]. State-of-the-art approaches typically
formulate the problem as abstractive summarisation, making the task a prime
candidate for further investigation of the potential of LLMs in clinical
settings. In this scenario, conversations between patients and doctors need to
be transformed into (excerpts of) clinical documentation. For example, if a 27
year old female patient mentions that they are experiencing _“Sore throat,
runny nose, dry cough and fever 37.5 ∘C”_, the corresponding entry can be the
_“Subjective”_ section of a medical record excerpt, e.g., _“Patient is a 27
year old female who presents with sore throat, runny nose dry cough and a
fever of 37.5 ∘C.”_ This documentation is typically performed by the
consulting doctor or an attending nurse. Despite bearing potential impact for
automation, with clinical staff spending at least 35 minutes of their time
every other day on writing such clinical notes [10], this task was
underexplored by the NLP community, compared to other hospital-related tasks,
such as clinical coding [11, 12], or generating radiology reports [13]. More
recently, the task has received more attention [14], however studies thus far
have either focussed on narrow department selections [15, 16], did not focus
on medical documentation generation [17], or have not released their data
publicly [18].

To that end, the ImageClef 2023 MediSum shared task released a collection of
dialogues and corresponding clinical notes in an effort to spark interest and
advance the state of the art in dialogue as clinical note summarisation [8].
The task revolves around three core sub-tasks: _(A)_ identifying the topic of
a conversation from a selection of possible medical note sections (i.e.,
_“Subjective”_ in the previous example), _(B)_ summarising conversation
snippets to appropriate sections in medical records, and, finally, _(C)_
summarising full conversations to full medical records. While conversations
are synthetic, the corresponding clinical notes are real, doctor-written
documentation.

Our guiding objective to participate in this task was to investigate, how well
a recently proposed LLM training framework can generalise to new tasks with as
little adaptation as possible [19]. At its core, the framework _(i)_ fine-
tunes a LLM with a pre-training objective that learns to reconstruct a pseudo-
summary consisting of automatically extracted medical terms and _(ii)_ employs
data augmentation (DA) by instructing Black-Box LLMs to obtain task-specific
training data. As such, the DA framework supports any LLM, such as Bloom [20],
GPT-3 [21] or GPT-3.5 [22].

Our submission for task B was ranked second best overall among all
participants. Although we have not actively sought to compete in Task C, we
observed that our data augmentation technique could improve the performance,
particularly when the training data is scarce. These findings underline the
potential of LLMs in various settings as well as the generalisability of our
proposed approach.

##  2 Task Definition

In this section, we describe and formalise the three tasks of the ImageClef
2023 MediSum challenge.

#### Task A – Dialogue2Topic Classification

In this task, participants need to identify the topic of a conversation. The
list of possible topics corresponds to the 20 different fine-grained sections
that can be part of a medical record, such as _“Subjective”_ , i.e., the
subjective description of symptoms by the patient.

#### Task B – Dialogue2Note Summarization

Here, participating systems need to convert a conversation on a specific topic
into a corresponding section in the medical record. This task can be regarded
as conditional generation, sequence-to-sequence translation or abstractive
summarisation. Approaches are evaluated on multiple natural language
generation metrics, both based on n-gram overlap, i.e., ROUGE [23], as well as
semantic similarity [24, 25]. 1201 training and 100 validation examples are
provided. 200 examples form the test set.

#### Task C – Full-Encounter Dialogue2Note Summarization

This task is formulated similarly to Task B, however here, the inputs are full
notes and the evaluated systems need to generate medical record outputs for
the four general sections _“Subjective”_ , _“Objective Exam”_ , _“Objective
Results”_ and _“Assessment and Plan”_. This task features only 67 training and
20 validation examples, with 40 examples reserved for testing. The systems are
evaluated based on their output for each of the sections using the ROUGE
metrics from Task B; the results are averaged across all sections. An
alternative mode of evaluation combines all outputs into one single record and
measures the n-gram overlap by means of the ROUGE score.

####

The tasks appear to be arranged as a progression, where, given a dialogue, a
segmentation and classification model could segment the topics of the
conversation (Task A) to be used as input for a Dialogue Snippet Summarisation
Model (Task B), the output of which can be arranged as a full medical record
(Task C). However, as our goal was to evaluate how well the proposed framework
generalises to the tasks with as little adaptation as possible, we decide not
to make any task-specific adaptations even if they could provide beneficial
given the particular arrangement of the tasks. Thus, we do not rely on any
additional information, treat tasks B and C in isolation, and disregard task A
for not being a generative task.

##  3 Methodology

Figure 1: Example of the pre-train objective of PULSAR. Both Masked Language
Model (MLM) and Gap Sentences Generation (GSG) have been employed in this
scenario. Red and orange arrows exemplify the UMLS and N2C2 MLM masking
strategy, respectively. Meanwhile, the black arrow shows the GSG masking
strategy, where a whole sentence has been masked.

###  3.1 Language model Pre-training

Motivated by the success of predicting masked words [26] and contiguous spans
[27] as self-supervised training objectives, we customised the pre-training
objectives for the medical domain generation task to concatenate “gap text
spans (sentences)” into a pseudo-summary. Each masked span is a medical term
from the input text identified by the QuickUMLS [28] or a NER model fine-tuned
on a N2C2 dataset (i2b2-2010 challenge [29]). Specifically, as shown in Figure
1, pre-training consisted of three different policies: first, when both
QuickUMLS and N2C2 NER models identified entities, the QuickUMLS results were
used in 70% of cases and the results of the N2C2 NER model were used in 30%.
Second, when only one of them predicted any output, that output was used for
masking. Third, when neither had any output, then 15% of the sentences were
masked at random. These text spans were replaced with “sentinel” mask tokens
$<extra\underline{~{}}id\underline{~{}}i>$ to inform the model that input was
masked. In order to provide the model with sufficient medical knowledge, we
used the MIMIC-III [11], a pre-trained corpus of 2 million data, which
consists of a large number of clinical records, such as admission notes,
discharge summaries or lab results.

###  3.2 Data Augmentation (DA)

Both tasks suffer from scarcity of training data, specifically Task C, which
requires generating comprehensive clinical notes based on lengthy patient-
doctor conversations based on only 67 training examples. These may be
insufficient to train a model capable of performing well on the task. To
address this issue, we adopt data augmentation to generate additional examples
for training, as this has been shown to improve performance in data-scarce
scenarios [30, 31].

#### Prompting Strategy

We observed that Large Language Models (LLMs) such as ChatGPT are proficient
in understanding clinical context and manipulating clinical data. Therefore,
we utilise a pre-existing LLM to generate data for the model’s training.
Ideally, the data generation approach would involve providing conversations
and requesting the LLM to produce the corresponding medical note. However, we
are limited by the fact that we only have 67 full-length conversations in our
dataset. Nonetheless, we have access to a significantly larger number of
medical notes. Hence, we invert the task by prompting the LLM with a medical
note (or its snippet) and ask it to generate a hypothetical conversation
between the doctor and the patient. We then use the generated conversations as
input to train our model to produce the corresponding clinical note.

We employ the OpenAI ChatGPT API (gpt-35-turbo) for data augmentation,
utilising a two-stage prompting strategy to generate data effectively. In the
first stage, we use in-context learning with one-shot prompting to prompt the
LLM to generate a fictitious conversation between the doctor and patient based
on the medical note, while adhering to important guidelines. We provide only
one example picked from the training set as we are limited by token context
windows for the API. In the second stage (only performed for task C), we
prompt the model to include conversational fillers such as “ums”, “uh”, and
“hmm” to the generated conversation from the first stage, as we noticed that
the model did not include these fillers despite our instructions in the first
stage.

#### Dataset Utilised

For task B, we extract matching subsection headings from the MIMIC-III
database [11], adapting the pre-processing method from Yang et al. [32] to
identify section headers. We rank the generations based on their average Rouge
similarity to all training instances and pick the top-scoring $n$
conversations.

For task C, we utilise a corpus of freely available medical notes scraped from
MTSamples, which is available on Kaggle111https://mtsamples.com/ and
https://www.kaggle.com/datasets/tboyle10/medicaltranscriptions, respectively.
Since the dataset contains medical transcriptions of notes from various
medical specialities, we devise a method to pick samples from the dataset that
are the closest to the medical notes in our training set. To do this, we
identify and curate a list of the section headers in the training set through
a heuristic approach by exploiting the fact that section headers are usually
written in all capital letters. We split the document by newline and extract
the lines which are fully upper-cased and add these contents to our list of
section headers. We then score the medical notes in MTSamples based on the
number of headers that each document has based on the curated list from the
previous step and pick the top $n$ documents from MTSamples with the highest
scores to use as input for DA. We end up with a corpus of 746 data samples due
to the fact that some inputs were flagged as offensive by OpenAI’s content
moderating policy.

##  4 Empirical Evaluation

###  4.1 Experiments set-up

We aim to empirically evaluate, how well our framework can solve the problem
of converting patient dialogues to medical records. We pursue the following
questions:

  1. [(i)]

  2. 1.

How well can our proposed approach convert doctor-patient dialogues to Medical
Records?

  3. 2.

Does the domain-specific pre-training objective improve performance?

  4. 3.

What is the impact of model scale on the performance?

  5. 4.

Does synthetic data augmentation improve performance on the tasks?

To answer question _(i)_ we empirically evaluate our proposed framework on the
task B and C test sets of the ImageClef Challenge. For evidence towards
question _(ii)_ , we compare the performance of PULSAR to that of equally-
sized Flan-t5 models. Regarding question _(iii)_ , we compare the performance
of variously sized models of the same architecture and for question _(iv)_ ,
we compare the performance of models trained on available data only to those
fine-tuned on synthetically generated conversation data.

###  4.2 Implementation Details

#### Pre-training

PULSAR-* is initialised with weights from the corresponding Flan-t5-* models
[33] and pre-trained with four NVIDIA Tesla A100 80GB GPUs for 1 epoch on all
MIMIC-III notes. Huggingface Accelerate is used to optimise GPU memory usage
with the Fully Sharded Data Parallel (FSDP) paradigm. We set the training
batch size per GPU device as 4 and the gradient accumulation step as 8 to
accelerate the training process.

#### Fine-tuning

We fine-tune all models for 3 epochs. We experiment with encoder-decoder
Flan-T5, PULSAR and Clinical-T5 [34]models, with the configurations *-Large
(0.9B Parameters), *-3B and *-11B. Unless stated otherwise, the models are
trained on two A100 80GB GPUs with cumulative batch size of 8 and the learning
rate of $3^{-5}$. For the largest of them, i.e., (Flan-t5-11B and PULSAR-11B),
we use FSDP with CPU offloading. We also experiment with a decoder-only model,
LLAMA-13B, freezing and quantising the base model in eight bit [35] and using
the parameter-efficient LoRA [36] method. More details on hyper-parameter
choice are reported in the appendix.

Table 1: Validation set performance as measured by {1,2}-gram overlap Rouge-{1,2} and longest sequence overlap Rouge-L Rouge-LSum. Models with the *-$n$DG were augmented with $n$ synthetic examples. The *-header suffix denotes that the section header was used as input. ID | Setting | Rouge
---|---|---
|  | R1 | R2 | RL | RLSum
| _11B and 7B models_
11B2 | PULSAR-11B | 49.20 | 22.25 | 41.36 | 45.57
11B1 | Flan-T5-11B | 50.75 | 27.92 | 44.93 | 47.58
7B1 | LLaMA-7B-LoRA | 39.3 | 15.7 | 33.1 | 33.1
| _3B models_
3B4 | PULSAR-3B-735DG | 37.89 | 17.83 | 30.40 | 34.76
3B3 | Flan-T5-3B-735DG | 41.44 | 19.05 | 33.93 | 38.41
3B2 | PULSAR-3B | 37.92 | 16.64 | 30.64 | 34.58
3B1 | Flan-T5-3B | 41.91 | 19.41 | 33.76 | 38.04
| _Large models ($<$ 1B parameters)_
L4 | Flan-T5-large-header | 38.70 | 16.82 | 31.85 | 36.22
L3 | Flan-T5-large-1000DG | 39.41 | 17.04 | 31.85 | 36.78
L2 | Flan-T5-large | 39.27 | 17.42 | 31.95 | 36.49
L1 | Clinical-T5-large | 19.11 | 8.34 | 16.31 | 17.29
Table 2: Test set performance as measured by {1,2}-gram overlap Rouge-{1,2}, longest sequence overlap Rouge-L and Rouge-LSum and semantic similarity metrics BertScore-F1 and Bleurt; ranked by their aggregation. submission | R1 | R2 | RL | RLSum | BS-F1 | Bleurt | Agg
---|---|---|---|---|---|---|---
SuryaKiran_run3 | 43.98 | 18.44 | 35.01 | 35.01 | 72.31 | 55.67 | 57.32
Flan-T5-11B | 42.99 | 20.04 | 35.69 | 35.69 | 72.18 | 55.49 | 56.89
PULSAR-11B | 41.78 | 19.25 | 34.16 | 34.16 | 72.11 | 55.52 | 56.47
Tredence_run1 | 42.44 | 17.24 | 35.3 | 35.3 | 72.07 | 53.3 | 55.94
SuryaKiran_run2 | 42.09 | 18.83 | 34.2 | 34.2 | 71.37 | 54.23 | 55.90
SuryaKiran_run1 | 40.56 | 17.59 | 32.72 | 32.72 | 71.09 | 53.24 | 54.96
LLaMA-7B-LoRA | 38.15 | 17.3 | 31.42 | 31.42 | 71.77 | 51.52 | 53.82
HuskyScribe_run1 | 37.67 | 15.04 | 31.26 | 31.26 | 70.54 | 50.37 | 52.86
Tredence_run2 | 36.21 | 13.84 | 29.66 | 29.66 | 68.82 | 47.29 | 50.77
uetcorn_run1 | 29.11 | 10.73 | 22.94 | 22.94 | 65.85 | 49.42 | 48.13
uetcorn_run2 | 28.75 | 10.69 | 23.09 | 23.09 | 65.96 | 49.22 | 47.98
uetcorn_run3 | 28.72 | 10.7 | 23.04 | 23.04 | 65.92 | 49.13 | 47.92
SKKU-DSAIL_run1 | 26.03 | 11.31 | 18.22 | 18.22 | 59.29 | 53.05 | 46.12

###  4.3 Results and analysis

At a glance, Table 1 shows the results of our empirical study and Table 2
shows the final ranking of all participating systems according to the official
evaluation by task organisersIn the following, we discuss our findings in
context of the questions outlined in the motivation of this empirical study.

#### Our approach generalises well to the dialogue summarisation task.

Overall, our approach generalises well to Task B, with our best model (Table
1, 11B1) surpassing the $50$ Rouge-1 scores mark, which means that on average,
half of the prediction tokens are found in reference and vice versa. The high
Rouge-L score of $44$ suggests that most of these overlapping tokens indeed
form a sequence. However, these scores may be “boosted” by the presence of
many short target sequences in the evaluation data, such as
_“Noncontributory.”_ or _“No known allergies.”_ , when a dialogue revolves
around a topic that does not contribute to the patients’ hospital visit.

We find that the utilising the outputs of task A—the section headers—does not
contribute to improving the overall performance, compare Table 1, L2 and L4.
We observed the same trend across all model sizes (not reported here for
brevity).

In the absence of established baselines, we interpret the official rankings of
the shared task in Table 2 as additional evidence towards the success of our
approach.

#### There is no conclusive evidence that domain-specific pre-training is
beneficial.

Comparing 11B1 and 11B2, and 3B1 and 3B2 in Table 1, respectively, we observe
that domain-specific pre-training by learning to predict missing medical terms
in MIMIC-III notes appears not beneficial, with the gap being smaller for
bigger models. One possible reason for this is the domain mismatch between
pre-training and application data. MIMIC-III is dominated by inpatient
progress notes which track the patients’ status along the hospital stay and
contain abbreviations, repetitions, incomplete sentences and medical jargon.
Conversely, the medical records in the challenge are well-written and stem
most likely from admission notes or outpatient encounters, where most of the
_initial_ documentation about a new patients’ particulars, such as their chief
complaint, medical history and drug allergies happens. Additionally, input
dialogues have a colloquial tone, further adding to the domain mismatch
between pre-training and fine-tuning.

#### Model scale yields the biggest performance improvements.

Comparing L*, 3B* and 11B* results in Table 1, we can see a clear trend where
larger models of the same family consistently perform better. The biggest hike
in performance is observed between the 3B and 11B models. This observation is
in line with most literature on model scale as driver of performance and the
reason for emergent abilities in LLMs [37].

We also find that the model trained with adapters can learn to perform on the
task successfully, despite the relatively small (around 1.1% of the full 7B
model) number of trainable parameters. However, our results suggest that
updating all models’ parameters is more effective, as even smaller models
outperform the 7B adapter model (Table 1, L2, 3B* compared to 7B1).

#### Data Augmentation can be helpful if training data is extremely scarce.

Larger models obtain enough signal from the training data of Task B, as there
is no clear improvement in scores for the 3B models (Table 1, 3B1 vs. 3B3 and
3B2 vs. 3B4). Meanwhile, data augmentation can lead to consistent, albeit
minor, improvements for smaller models (Table 1, L2 vs. L3). When training
data is scarce (i.e., Task C) data augmentation helps with the performance.
Subjectively, models exhibit typical generation errors such as hallucination
and input copying, (see Figure 2 in Appendix) and data augmentation seems to
alleviate this issue. Quantitatively, data augmentation improves performance
across all metrics (27.64 vs 29.41 R1, 9.79 vs 11.60 R2, 16.24 vs 19.18 RL and
23.63 vs 26.08 RLSum without and with DA, respectively). We find the results
promising, as the optimised model seems to perform well without any task-
specific adaptation. Ultimately, however, this simple approach does not
compete with other, potentially task specific information exploiting
submissions, with the best of them scoring almost 20 Rouge-1 points higher
(20.32 R2, 24.30 RL and 45.06 RLSum).

##  5 Conclusion

In this work, we present an LLM framework and adapt it to the task of dialogue
note summarisation. While we find that the approach generalises well to this
new task, there is mixed evidence of the efficacy of both domain-specific pre-
training and data augmentation. Our experiments seem to align with the “bitter
lesson of AI”222http://www.incompleteideas.net/IncIdeas/BitterLesson.html, in
that model scale seems to trump domain-specific adaptations. This, in turn,
supports the narrative of the transformative potential of LLMs in healthcare
[38], as larger LLMs become more readily available.

Our findings suggest further avenues for future work: We argued that the pre-
training objective may suffer from domain mismatch. As such, experimenting
with other domain-specific objectives might improve the performance of the
downstream tasks. Furthermore, it is unclear how the choice of hyper-
parameters for both training and inference stages (i.e., decoding arguments)
impacts the overall performance. Finally, we have left it for future work to
investigate, whether data augmentation could provide beneficial with a more
advanced filtering strategy, for example by only augmenting examples with
certain length or specific section headers. As such, we will expand the work
reported in this paper by experimenting with different pre-training
objectives, performing a more rigorous hyper-parameter optimisation and
investigating the impact of data augmentation more closely.

## Limitations

The results described in this paper should be interpreted within the following
context:

  * •

The language of the conversations is English. Due to the dominance of English
data during pre-training, it is expected that all LLMs that we inspected
perform better on English. It is unclear how well the approach will transfer
to other languages.

  * •

The conversations are synthetic in that they have been written based on
existing medical notes, rather than transcribed from real patient-doctor
dialogues. While the quality has been evaluated by medical professionals, it
is unclear how well the performance would translate to real-world scenarios.

  * •

The obtained results should be regarded as preliminary, as robust empirical
results such as hyper-parameter optimisation for fine-tuning, pre-training
policy selection, exhaustive search for best-performing prompts for data
augmentation and strategies for data selection are often impossible given the
time constraints of academic challenges and shared tasks.

## References

  * Sanh et al. [2022] V. Sanh, A. Webson, C. Raffel, S. Bach, L. Sutawika, Z. Alyafeai, A. Chaffin, A. Stiegler, A. Raja, M. Dey, et al.,  Multitask prompted training enables zero-shot task generalization,  in: International Conference on Learning Representations 2022, 2022.
  * Agrawal et al. [2022] M. Agrawal, S. Hegselmann, H. Lang, Y. Kim, D. Sontag,  Large language models are few-shot clinical information extractors,  in: Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, 2022, pp. 1998–2022.
  * Brown et al. [2020] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al.,  Language models are few-shot learners,  Advances in neural information processing systems 33 (2020) 1877–1901.
  * Singhal et al. [2022] K. Singhal, S. Azizi, T. Tu, S. S. Mahdavi, J. Wei, H. W. Chung, N. Scales, A. Tanwani, H. Cole-Lewis, S. Pfohl, et al.,  Large language models encode clinical knowledge,  arXiv preprint arXiv:2212.13138 (2022).
  * Rajpurkar et al. [2022] P. Rajpurkar, E. Chen, O. Banerjee, E. J. Topol,  Ai in health and medicine,  Nature medicine 28 (2022) 31–38.
  * Searle et al. [2023] T. Searle, Z. Ibrahim, J. Teo, R. J. Dobson,  Discharge summary hospital course summarisation of in patient electronic health record text with clinical concept guided deep pre-trained transformer models,  Journal of Biomedical Informatics 141 (2023) 104358.
  * Gao et al. [2023] Y. Gao, T. Miller, M. Afshar, D. Dligach,  Bionlp workshop 2023 shared task 1a: Problem list summarization,  "Proceedings of the 22nd Workshop on Biomedical Language Processing" (2023).
  * Yim et al. [2023] W. Yim, A. Ben Abacha, N. Snider, G. Adams, M. Yetisgen,  Overview of the mediqa-sum task at imageclef 2023: Summarization and classification of doctor-patient conversations,  in: CLEF 2023 Working Notes, CEUR Workshop Proceedings, CEUR-WS.org, Thessaloniki, Greece, 2023.
  * Feng et al. [2022] X. Feng, X. Feng, B. Qin,  A survey on dialogue summarization: Recent advances and new frontiers,  in: CLEF 2023 Working Notes, CEUR Workshop Proceedings, 2022.
  * Hripcsak et al. [2011] G. Hripcsak, D. K. Vawdrey, M. R. Fred, S. B. Bostwick,  Use of electronic clinical documentation: time spent and team interactions,  Journal of the American Medical Informatics Association 18 (2011) 112–117.
  * Johnson et al. [2016] A. E. Johnson, T. J. Pollard, L. Shen, L.-w. H. Lehman, M. Feng, M. Ghassemi, B. Moody, P. Szolovits, L. Anthony Celi, R. G. Mark,  Mimic-iii, a freely accessible critical care database,  Scientific data 3 (2016) 1–9.
  * Nguyen et al. [2023] T.-T. Nguyen, V. Schlegel, A. Kashyap, S. Winkler, S.-S. Huang, J.-J. Liu, C.-J. Lin,  Mimic-iv-icd: A new benchmark for extreme multilabel classification,  arXiv preprint arXiv:2304.13998 (2023).
  * Monshi et al. [2020] M. M. A. Monshi, J. Poon, V. Chung,  Deep learning in generating radiology reports: A survey,  Artificial Intelligence in Medicine 106 (2020) 101878.
  * Abacha et al. [2023] A. B. Abacha, W. Yim, Y. Fan, T. Lin,  An empirical study of clinical note generation from doctor-patient encounters,  in: EACL, Association for Computational Linguistics, 2023, pp. 2283–2294.
  * Kazi and Kahanda [2019] N. Kazi, I. Kahanda,  Automatically generating psychiatric case notes from digital transcripts of doctor-patient conversations using text mining,  PeerJ Prepr. 7 (2019) e27497.
  * Enarvi et al. [2020] S. Enarvi, M. Amoia, M. D.-A. Teba, B. Delaney, F. Diehl, S. Hahn, K. Harris, L. McGrath, Y. Pan, J. Pinto, et al.,  Generating medical reports from patient-doctor conversations using sequence-to-sequence models,  in: Proceedings of the First Workshop on Natural Language Processing for Medical Conversations, 2020, pp. 22–30.
  * Yim and Yetisgen-Yildiz [2021] W.-w. Yim, M. Yetisgen-Yildiz,  Towards automating medical scribing: Clinic visit dialogue2note sentence alignment and snippet summarization,  in: Proceedings of the Second Workshop on Natural Language Processing for Medical Conversations, 2021, pp. 10–20.
  * Joshi et al. [2020] A. Joshi, N. Katariya, X. Amatriain, A. Kannan,  Dr. summarize: Global summarization of medical dialogue by exploiting local structures,  arXiv preprint arXiv:2009.08666 (2020).
  * Li et al. [2023] H. Li, Y. Wu, V. Schlegel, R. Batista-Navarro, T.-T. Nguyen, A. Ramesh Kashyap, X. Zeng, D. Beck, S. Winkler, G. Nenadic,  Pulsar: Pre-training with extracted healthcare terms for summarising patients’ problems and data augmentation with black-box large language models,  arXiv preprint (2023).
  * Scao et al. [2022] T. L. Scao, A. Fan, C. Akiki, E. Pavlick, S. Ilić, D. Hesslow, R. Castagné, A. S. Luccioni, F. Yvon, M. Gallé, et al.,  Bloom: A 176b-parameter open-access multilingual language model,  arXiv preprint arXiv:2211.05100 (2022).
  * Brown et al. [2020] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, D. Amodei,  Language models are few-shot learners,  in: NeurIPS, 2020.
  * Ouyang et al. [2022] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al.,  Training language models to follow instructions with human feedback,  in: Advances in Neural Information Processing Systems, volume 35, 2022, pp. 27730–27744.
  * Lin [2004] C.-Y. Lin,  Rouge: A package for automatic evaluation of summaries,  in: Text summarization branches out, 2004, pp. 74–81.
  * Sellam et al. [2020] T. Sellam, D. Das, A. Parikh,  Bleurt: Learning robust metrics for text generation,  in: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020, pp. 7881–7892.
  * Zhang et al. [2020] T. Zhang, V. Kishore, F. Wu, K. Q. Weinberger, Y. Artzi,  Bertscore: Evaluating text generation with bert,  in: International Conference on Learning Representations, 2020.
  * Joshi et al. [2020] M. Joshi, D. Chen, Y. Liu, D. S. Weld, L. Zettlemoyer, O. Levy,  Spanbert: Improving pre-training by representing and predicting spans,  Trans. Assoc. Comput. Linguistics 8 (2020) 64–77.
  * Raffel et al. [2020] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, P. J. Liu,  Exploring the limits of transfer learning with a unified text-to-text transformer,  J. Mach. Learn. Res. 21 (2020) 140:1–140:67.
  * Soldaini and Goharian [2016] L. Soldaini, N. Goharian,  Quickumls: a fast, unsupervised approach for medical concept extraction,  in: MedIR workshop, sigir, 2016, pp. 1–4.
  * Uzuner et al. [2011] Ö. Uzuner, B. R. South, S. Shen, S. L. DuVall,  2010 i2b2/va challenge on concepts, assertions, and relations in clinical text,  J. Am. Medical Informatics Assoc. 18 (2011) 552–556.
  * Schick and Schütze [2021] T. Schick, H. Schütze,  Generating datasets with pretrained language models,  in: Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, 2021, pp. 6943–6951.
  * Li et al. [2023] H. Li, V. Schlegel, R. Batista-Navarro, G. Nenadic,  Do you hear the people sing? key point analysis via iterative clustering and abstractive summarisation,  arXiv preprint arXiv:2305.16000 (2023).
  * Yang et al. [2022] Z. Yang, S. Wang, B. P. S. Rawat, A. Mitra, H. Yu,  Knowledge injected prompt based fine-tuning for multi-label few-shot icd coding,  arXiv preprint arXiv:2210.03304 (2022).
  * Chung et al. [2022] H. W. Chung, L. Hou, S. Longpre, B. Zoph, Y. Tay, W. Fedus, E. Li, X. Wang, M. Dehghani, S. Brahma, et al.,  Scaling instruction-finetuned language models,  arXiv preprint arXiv:2210.11416 (2022).
  * Lehman et al. [2023] E. Lehman, E. Hernandez, D. Mahajan, J. Wulff, M. J. Smith, Z. Ziegler, D. Nadler, P. Szolovits, A. Johnson, E. Alsentzer,  Do we still need clinical language models?,  arXiv preprint arXiv:2302.08091 (2023).
  * Dettmers et al. [2022] T. Dettmers, M. Lewis, Y. Belkada, L. Zettlemoyer,  Llm. int8 (): 8-bit matrix multiplication for transformers at scale,  arXiv preprint arXiv:2208.07339 (2022).
  * Hu et al. [2022] E. J. Hu, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, W. Chen, et al.,  Lora: Low-rank adaptation of large language models,  in: International Conference on Learning Representations, 2022.
  * Wei et al. [2011] J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, S. Borgeaud, D. Yogatama, M. Bosma, D. Zhou, D. Metzler, et al.,  Emergent abilities of large language models,  Transactions on Machine Learning Research 8 (2011).
  * Qiu et al. [2023] J. Qiu, L. Li, J. Sun, J. Peng, P. Shi, R. Zhang, Y. Dong, K. Lam, F. P.-W. Lo, B. Xiao, et al.,  Large ai models in health informatics: Applications, challenges, and the future,  arXiv preprint arXiv:2303.11568 (2023).

##  Appendix A Hyper-parameters for training and inference

We initialise LoRA with $r=16$, $\alpha=16$ on the query, key, value and
output projection weights of all layers of the base model ($Q,K,V$ and $O$,
respectively). The model is trained on a single A100 80GB GPU with a learning
rate of $3^{-4}$ for the adapter weights. For both encoder-decoder and decoder
only settings, during training, we optimise the parameters of the language
models to minimise the cross-entropy loss between each token of the prediction
and the corresponding token of the ground truth answer sequence using teacher
forcing. For encoder-decoder models, we limit the length of input dialogues to
at most 496 and the length of output notes to at most 214 tokens, respectively
(95th percentile). For the decoder model, we limit the length of input and
output combined to at most 696 tokens. During inference, we set no limits to
input and output sequence lengths and decode the prediction using beam search
with 6 (4 for LLaMa), temperature of 1.0, top k of 50 (40 for LLaMa) and top p
of 1.0 (0.7 for LLaMa).

For task C, we use the same arguments as for task C, with the exception of
limiting the input length to 2048 and output length to 990 during training, in
order to fit the GPU during training.

##  Appendix B Qualitative example

Figure 1 shows qualitative examples generated by our models trained on task C
training data with and without data augmentation, respectively.

Flan-T5-3B |  Flan-T5-3B-746DG
---|---
Alexander is a 62-year-old male, with a past medical history significant for reflux, who presents for follow-up of his chronic problems. He is so thankful you put him on that medicine for his reflux. The protonix that he had, w- made an amazing change in his life. He’s really comfortable now. He eats whatever he wants, and he feels so much better. The doctor is glad to hear that. Okay. How are you doing, kind of, managing your diet? I know, you have to do some lifestyle modifications, like cutting back on caffeine and spicy foods and alcohol. How are you doing with that? _[patient] I’m doing really well. I moved over from caffeine, over to green tea. [doctor] Okay. [patient] and it, it is so, m- it doesn’t cause as much problem as it did with, when he was drinking so many energy drinks a day…_ |  HISTORY OF PRESENT ILLNESS: Alexander is a 62-year-old male with a past medical history significant for reflux. He presents for follow-up of his chronic problems. He has a good support system at home. He has a big family. All his kids call and check on him every day. He does not have any symptoms of chest pain, shortness of breath, belly pain, nausea or vomiting. He does not have any symptoms of nausea or vomiting. On physical examination, I do not hear any carotid bruits in his neck. I do hear a slight 2/6 systolic ejection murmur, which I’ve heard in the past, so that’s stable. His lungs are nice and clear, and he does have 1+ pitting edema bilaterally in his lower extremities. I think he is doing a good job watching his diet. He could just be retaining a little bit of fluid, maybe just from standing all day.
Figure 2: Example excerpts of outputs for Task C produced by models with and
without data augmentation. An instance of input copying is highlighted in
italics.


# CRAWLING: a Crowdsourcing Algorithm on Wheels for Smart Parking

Émiland Garrabé  Department of Information and Electrical Engineering and
Applied Mathematics, University of Salerno, Fisciano, 84084, Italy
<EMAIL_ADDRESS>Giovanni Russo  Department of Information and
Electrical Engineering and Applied Mathematics, University of Salerno,
Fisciano, 84084, Italy<EMAIL_ADDRESS>
###### Abstract

We present the principled design of CRAWLING: a CRowdsourcing Algorirthm on
WheeLs for smart parkING. CRAWLING is an in-car service for the routing of
connected cars. Specifically, cars equipped with our service are able to
crowdsource data from third-parties, including other cars, pedestrians, smart
sensors and social media, in order to fulfill a given routing task. CRAWLING
relies on a solid control-theoretical formulation and the routes it computes
are the solution of an optimal control problem where cars maximize a reward
capturing environmental conditions while tracking some desired behavior. A key
feature of our service is that it allows to consider stochastic behaviors,
while taking into account streams of heterogeneous data. We propose a stand-
alone, general-purpose, implementation of CRAWLING and we show its
effectiveness on a set of scenarios aimed at illustrating all the key features
of our service. Simulations show that, when cars are equipped with CRAWLING,
the service effectively orchestrates the vehicles, making them able to react
online to road conditions, minimizing their cost functions. The code
implementing our service and to replicate the numerical results is made openly
available.

##  1 Introduction

By $2050$, it is expected[1] that $66$% of the World population will live in
urban environments, with many of our cities set to become megacities. Hence,
also driven by the Internet of Things (IoT) revolution and the explosion in
the amount of available data, many governments and local authorities have
adopted (or are in the process of adopting) concepts based on Smart Cities to
tackle the key challenges related to the growing intensive urbanization[2]. As
a result, much research and development effort is currently devoted to the
design of IoT and data-driven services with the goal of making Smart Cities
sustainable[3], capable of improving the quality of life of their Citizens
with subsequent societal, economic and environmental impacts. The design of
Intelligent Transportation Systems (ITSs) is central to achieve each of these
goals and an exciting opportunity is offered by the possibility of designing,
and deploying, services leveraging the increasing pervasiveness of connected
cars.
In this context, we propose the principled design of a data-driven service
based on crowdsourcing for the routing of connected cars, CRAWLING
(CRowdsourcing Algorithm on WheeLs for smart parkING). Connected cars equipped
with CRAWLING are able to crowdsource the skills/services they need in order
to fulfill a given routing task. The service is also designed to allow cars
equipped with CRAWLING to gather data from other sources, such as other cars,
pedestrians, smart sensors or social media. As a result, vehicles equipped
with CRAWLING become an active part of a sharing economy[4] ecosystem, where
vehicles share, and create, skills that can be used within the service. A key
feature of our service is that it is built around a framework that
intrinsically allows to consider stochastic behaviors, thus explicitly
accounting for users’ stochasticity and to capture their privacy requirements.
Specifically, CRAWLING exploits a recent data-driven control algorithm[5, 6]
that returns a randomized behavior for the car (i.e., a probability function)
by solving a sequential decision-making problem[7] that formalizes the
tracking of a desired behavior expressed in probabilistic terms. That is, our
service systematically minimizes a cost function consisting of: (i) a reward
capturing road/traffic conditions; (ii) a regularizer that biases the solution
towards some target behavior, allowing CRAWLING to keep into account the
possible preferences of passengers.
While CRAWLING can be tailored towards generic routing problems, for
concreteness we focus here on the problem of routing cars to find parking
spaces. Smart parking allocation is attracting much research attention[8, 9,
10, 11], as roaming for parking is known to be a major source of pollution,
traffic and user stress[12, 13, 14]. In a broader context, lack of
coordination in transportation systems is believed to be correlated to an
increase in circulating vehicles[15]. To mitigate this, in the context of
parking management, urban sensors can be used to monitor the availability of
parking spaces and the key challenge becomes that of designing algorithms that
are able to optimally route the flow of vehicles[16]. Currently, many such
algorithms rely on deterministic decision-making[17]. For example, methods[18]
for solving multi-depot vehicle routing frame the problem via deterministic
optimization, using binary decision variables. On the other hand, the use of
stochastic frameworks has been gaining traction in the Intelligent
Transportation Systems (ITSs) literature, for example in the context of
differential privacy where privacy is achieved by injecting noise in the
system[19], or in driver[20] or pedestrian[21] intent prediction. Efforts to
leverage users’ data in Smart City contexts are also the focus of much
attention[22, 23], for example for energy[24] or taxi[25] demand prediction,
or congestion analysis[26]. While such efforts often focus on modelling[27]
and/or artificial intelligence methods[28, 29], some specialized stochastic
optimization frameworks have also arisen, for example in parking
assignment[30]. Finally, data-driven ITSs, and the data-driven analysis of
ITSs[31] have also gained traction, although heterogeneous datasets, emerging
from different information streams that need to be merged, have been singled
out as a challenge[32]. As an example of one such stream, social media
monitoring has been recently used to identify trends related to traffic
obstructions[33] and monitor traffic in real time[34].
In summary, the key contributions of the paper can be summarized as follows:
after formalizing the smart parking problem as a data-driven control problem,
we propose the principled design of CRAWLING and present a stand-alone,
general-purpose, implementation of the service. The service provably returns
the optimal behavior for cars on which it is equipped. Then, we evaluate its
computation times and discuss how these are suitable for routing applications.
We also show, via simulations leveraging the microscopic traffic simulator
SUMO[35], the effectiveness of CRAWLING in orchestrating the use of parking
spaces in a University Campus during rush hours in the morning. Simulations
show that CRAWLING effectively directs the connected cars, confirming that
cars equipped with our service improve their average time-to-parking, avoiding
unfavourable areas of the map and reacting online to environmental changes
(reported, in the scenarios we consider, via social media).
The paper is organized as follows. In Section 2, we begin by introducing the
data-driven control framework exploited by CRAWLING, and subsequently
describing its design, the implementation and the scenarios used to assess its
performance. Then, in Section 3, we report the results obtained with the
service. We do so by first evaluating the computational efficiency and then
discussing the performance obtained on the reference scenarios, which were
specifically chosen to validate all the key features of the service. Finally,
we give concluding remarks, and discuss the relevance of the results, Section
4.

###  1.1 Notation

We note the set of road links, or lanes in what follows, as $\mathcal{X}$.
Time is discrete and, at time step $k$, the connected car occupies link
$\mathbf{x}_{k}\in\mathcal{X}$. The probability of a connected car of going
from $\mathbf{x}_{k-1}$ to $\mathbf{x}_{k}$ is denoted by
$\pi(\mathbf{x}_{k}|\mathbf{x}_{k-1})$. The car has available a number of
services (or sources) and the $i$-th service/source is denoted by
$\pi^{(i)}(\mathbf{x}_{k}|\mathbf{x}_{k-1})$. The target behavior of the car
represents the behavior that passengers would like to track in the absence of
road (or environmental) disruptions: this is denoted by
$p(\mathbf{x}_{k}|\mathbf{x}_{k-1})$. Finally, the reward obtained by the car
at time $k$ for being on $\mathbf{x}_{k}$ is denoted by
$r_{k}(\mathbf{x}_{k})$. As we shall see, the reward is used in our service to
capture road/environmental disruptions that might not be known to the vehicle
passengers. Also, we denote by
$\pi(\mathbf{x}_{1},\ldots,\mathbf{x}_{N}|\mathbf{x}_{0})$ and
$p(\mathbf{x}_{1},\ldots,\mathbf{x}_{N}|\mathbf{x}_{0})$ the product of the
transition probabilities $\pi(\mathbf{x}_{k}|\mathbf{x}_{k-1})$ and
$p(\mathbf{x}_{k}|\mathbf{x}_{k-1})$, respectively. These joint probability
functions clearly depend on the initial condition of the car,
$\mathbf{x}_{0}$, i.e. the starting link/lane of the trip. Finally, we let:
(i) $\mathbb{E}_{p}[h(\mathbf{X})]:=\sum h(\mathbf{x})p(\mathbf{x})$ be the
expectation of $h(\cdot)$ with the sum taken over the support of the
probability function $p(\mathbf{x})$; (ii) the Kullback-Leibler (KL)
divergence[36] of $p(\mathbf{x})$ with respect to $q(\mathbf{x})$, with
$p(\mathbf{x})$ absolutely continuous with respect to $q(\mathbf{x})$ is
$\mathcal{D}_{\text{KL}}\left(p(\mathbf{x})\mid\mid q(\mathbf{x})\right):=\sum
p(\mathbf{x})\log\frac{p(\mathbf{x})}{q(\mathbf{x})}$ and measures the
proximity of the pair $p(\mathbf{x})$, $q(\mathbf{x})$. We use the Matlab-like
notation $k_{1}:k_{2}$ to denote the set of integers between the integers
$k_{1}$ and $k_{2}$ (included). Consequently, $\\{w_{k}\\}_{k_{1}:k_{2}}$
denotes the set $\\{w_{k_{1}},\ldots,w_{k_{2}}\\}$.

Figure 1: CRAWLING functional architecture and its interactions with the
environment. CRAWLING is an in-car service and consists of a decision-making
(DM) algorithm, a cost module and a sampling mechanism. These components
compute the route the car should take based on environmental data and on the
available services.

##  2 Materials and methods

We now introduce CRAWLING. We first present the algorithm (Section 2.1) and
then discuss its implementation (Section 2.2) and the reference scenarios used
to assess its performance (Section 2.3). The key functional components of
CRAWLING, and its interactions with the surrounding road environment, are
schematically illustrated in Figure 1. As shown in such a figure, CRAWLING is
an in-car service: it gathers online data from the environment to feed a
suitably defined cost function and has available a number of source services
(or simply sources in what follows) to route the car. The sources are e.g.,
specialized routing services as well as directions collected from other cars
in the area also equipped with CRAWLING. Based on the cost and the available
sources, CRAWLING dynamically determines the next direction the car should
take. This is done via a decision-making (DM) algorithm that exploits recent
results in the context of data-driven control[5, 6]. The DM algorithm returns
a probability function (i.e., a policy) capturing the turning probabilities of
the car. The next road link that the car should take is then obtained by
sampling form the policy.

###  2.1 CRAWLING: description of the service

CRAWLING seeks to determine the optimal turning probabilities, say
$\tilde{\pi}(\mathbf{x}_{k}|\mathbf{x}_{k-1})$, of the car by orchestrating
the use of a set of available sources. The goal is to track a target behavior
for the car, $p(\mathbf{x}_{k}|\mathbf{x}_{k-1})$, while simultaneously
maximizing the car-specific reward $r_{k}(\mathbf{x}_{k})$. The target
behavior can be used to capture a preferred set of directions for the car
passengers. This can be computed from e.g., historical data[37, 38] and does
not depend on the road conditions. These can be instead captured through the
car-specific reward $r_{k}(\mathbf{x}_{k})$. Within the service, the reward
signal is used to capture data that are not included in the target behavior:
typically, these are related to the state of the network, including hazardous
conditions, traffic and roadworks (Scenario $1$ described in Section 2.3).
Such data can be gathered from a network of urban sensors and the reward can
also be fed by interactions with social media (Scenario $2$ in Section 2.3).
For example, in the simulations from Section 3, a component of the reward
favours road links adjacent to an available parking space, encouraging agents
to seek such spaces and park. This structure allows the reward to encompass
specifications linked to various tasks, meaning CRAWLING is not per se limited
to parking management. To introduce our service, say $S$ the number of
available sources, i.e., $\pi^{(i)}(\mathbf{x}_{k}|\mathbf{x}_{k-1})$ with
$i=1,\ldots,S$ (see Section 1.1 for the definitions). These are assumed to be
such that
$\mathcal{D}_{\text{KL}}\left(\pi^{(i)}(\mathbf{x}_{k}\mid\mathbf{x}_{k-1})\mid\mid
p(\mathbf{x}_{k}\mid\mathbf{x}_{k-1})\right)<+\infty$. This is a standing
assumption for our service that has been shown to be non-restrictive in
practice[6]. Given this set-up, the problem tackled by CRAWLING to determine
the optimal route for the car can be formalized as follows[5, 6]:

###### Problem 1

Let $N$ be a positive integer,
$\tilde{r}_{k}(\mathbf{x}_{k-1}):=\mathbb{E}_{\pi(\mathbf{x}_{k}\mid\mathbf{x}_{k-1})}\left[r_{k}(\mathbf{X}_{k})\right]$
and $\pi(\mathbf{x}_{0})$, $p(\mathbf{x}_{0})$ be priors on the initial
conditions. Find the sequence of weights
${\left\\{\boldsymbol{\alpha}_{k}^{\ast}\right\\}_{1:N}}$, with
$\boldsymbol{\alpha}^{\ast}_{k}:=[\alpha_{k}^{(1)},\ldots,\alpha_{k}^{(S)}]$
being an $S$-dimensional vector at time step $k$, solving

$\displaystyle\underset{\left\\{\boldsymbol{\alpha}_{k}\right\\}_{1:N}}{\text{min}}$
$\displaystyle\mathcal{D}_{\text{KL}}\left(\pi(\mathbf{x}_{1},\ldots,\mathbf{x}_{N}|\mathbf{x}_{0})\pi(\mathbf{x}_{0})||p(\mathbf{x}_{1},\ldots,\mathbf{x}_{N}|\mathbf{x}_{0})p(\mathbf{x}_{0})\right)-\sum_{k=1}^{N}\mathbb{E}_{\pi(\mathbf{x}_{k-1})}\left[\tilde{r}_{k}(\mathbf{X}_{k-1})\right]$
(1) $\displaystyle s.t.$ $\displaystyle\
\pi(\mathbf{x}_{k}|\mathbf{x}_{k-1})=\sum_{i\in
1:S}\alpha_{k}^{(i)}\pi^{(i)}(\mathbf{x}_{k}|\mathbf{x}_{k-1}),\ \ \ \forall
k$ $\displaystyle\sum_{i\in 1:S}\alpha_{k}^{(i)}=1,\ \
\alpha_{k}^{(i)}\in\\{0,1\\},\ \ \forall k.$

In Problem 1 the cost function formalizes the fact that the goal of CRAWLING
is to track the target behavior while maximizing the car-specific reward. The
constraints capture the fact that the solution of the problem is a probability
function and, in turn, this probability function is determined by picking one
of the sources available to CRAWLING. The problem is tackled[5, 6] by
Algorithm 1, which embeds both the cost and DM algorithm components of the
service in Figure 1. The key macro-steps of the algorithm, which outputs the
optimal solution to Problem 1, are described next.

The inputs to the algorithm (lines $1-6$) are, besides reward and sources, a
time horizon, $N$, and the current state of the agent, $\mathbf{x}_{k-1}$. The
target behavior is an optional input parameter. Indeed, if not provided to
CRAWLING, this is set to the uniform distribution (lines $7-9$). We note that,
when this happens, the first term in the cost of the problem in (1) becomes an
entropic regularizer, also widely used in the literature on reinforcement
learning[39]. The output of the algorithm (lines $10-11$) are the optimal
turning probabilities throughout the time horizon. This is essentially the
plan that the car will follow. Following the initialization phase, the for
loop computes the _reward-to-go_ for the car (this is computed by the cost
module in Figure 1) which represents how _promising_ a given direction plan is
for the car. The reward-to-go is computed via a backward recursion that starts
from the last time step in the time horizon. Intuitively, the time horizon is
a measure of _how far in the future_ CRAWLING can look to make a decision (see
Section 3.1 for the corresponding computational aspect). Specifically, in
Algorithm 1, the reward signal $r_{k}(\cdot)$ received by CRAWLING is updated
with information from the future time steps through the signal
$\hat{r}_{k}(\cdot)$, which is obtained via backward recursion. Then, the cost
of each source’s policy is calculated (lines $17-18$) and the source incurring
the smallest cost is selected, and used as the agent’s policy (i.e., turning
probabilities) – this is returned in line $23$. Finally, the next link that
the car needs to take is determined by sampling from the Sampling component
illustrated in Figure 1: this component, given the current state of the car,
samples from the next turning probability determined within Algorithm 1.

1:Inputs:

2:Current state – $\mathbf{x}_{k-1}$

3:Time horizon – $N$

4:Reward – $r_{k}(\mathbf{x}_{k})$

5:Sources – $\\{\pi^{(i)}(\mathbf{x}_{k}|\mathbf{x}_{k-1})\\}_{1:N}$, with
$i\in 1:S$

6:Target behavior (optional) –
$\\{p(\mathbf{x}_{k}|\mathbf{x}_{k-1})\\}_{1:N}$

7:if Target behavior not provided then

8: $\\{p(\mathbf{x}_{k}|\mathbf{x}_{k-1})\\}_{1:N}\leftarrow\text{uniform
distribution}$

9:end if

10:Output:

11:Optimal turning probabilities
$\\{\tilde{\pi}(\mathbf{x}_{k}|\mathbf{x}_{k-1})\\}_{1:N}$

12:Initialization:

13:Set the vectors $\mathbf{a}^{T}_{N+1}(\mathbf{x}_{N})\leftarrow 0$ and
$\tilde{\boldsymbol{\alpha}}_{N+1}\leftarrow 0$

14:for $k=N$ to $1$ do

15:
$\hat{r}_{k}(\mathbf{x}_{k})\leftarrow\mathbf{a}^{T}_{k+1}(\mathbf{x}_{k})\tilde{\boldsymbol{\alpha}}_{k+1}$

16:
$\bar{r}_{k}(\mathbf{x}_{k})\leftarrow{r}_{k}(\mathbf{x}_{k})-\hat{r}_{k}(\mathbf{x}_{k})$

17: for $i=1:S$ do

18:
$a_{k}^{(i)}(\mathbf{x}_{k-1})\leftarrow\mathcal{D}_{\text{KL}}\left(\pi^{(i)}(\mathbf{x}_{k}|\mathbf{x}_{k-1})||p(\mathbf{x}_{k}|\mathbf{x}_{k-1})\right)+\mathbb{E}_{\pi^{(i)}(\mathbf{x}_{k}|\mathbf{x}_{k-1})}\left[\bar{r}_{k}(\mathbf{X}_{k})\right]$

19: end for

20: $j_{k}\leftarrow\underset{i}{\text{argmin }}a_{k}^{(i)}(\mathbf{x}_{k-1})$

21:
$\mathbf{a}_{k}(\mathbf{x}_{k-1})\leftarrow[a_{k}^{(1)}(\mathbf{x}_{k-1}),\ldots,a_{k}^{(S_{k})}(\mathbf{x}_{k-1})]^{T}$

22:
${\boldsymbol{\alpha}}_{k}^{\ast}\leftarrow[\alpha_{k}^{(1)},\ldots,\alpha_{k}^{(S_{k})}]^{T}$,
where $\alpha_{k}^{(i)}=0$, $\forall i\neq j_{k}$ and $\alpha_{k}^{(j_{k})}=1$

23:
$\tilde{\pi}(\mathbf{x}_{k}|\mathbf{x}_{k-1})\leftarrow\pi^{(j_{k})}(\mathbf{x}_{k}|\mathbf{x}_{k-1})$

24:end for

Algorithm 1 CRAWLING in-car service

Before reporting on the implementation of CRAWLING, we also highlight here a
benefit in computing (and using as input) probability functions. First, the
sources used by CRAWLING are intrinsically stochastic and this can be useful
when the agents generating these data want to e.g. guarantee some desired
level of differential privacy. This privacy mechanism consists in corrupting
the information sent by the source with some (typically) Laplacian noise.
Hence, it can be captured with a source having a Laplacian probability
function. Moreover, Algorithm 1 does not determine the next state of the car
but rather a probability function. This aspect can be used to guarantee some
level of privacy for drivers using CRAWLING, making it possible to both
privately share their policy (which can become a source for other vehicles
equipped with CRAWLING) and determine the next direction by sampling from this
probability.

###  2.2 CRAWLING implementation and validation set-up

We now discuss the proposed implementation for CRAWLING. The code can be found
at https://tinyurl.com/wcwvcwaj. The key functional components of the
validation set-up are illustrated in Figure 2. As shown in such a figure, we
validate our service via the microscopic traffic simulator SUMO[35]. This
serves as environment (in which real maps can be imported and traffic demand
can be generated) with which CRAWLING interacts. Interactions with SUMO happen
via the Python interface TraCI: this is used to both gather the environmental
data from SUMO and to control the vehicles based on the directions provided by
Algorithm 1. Moreover, the Social Interface module gives CRAWLING the
possibility of monitoring certain social media (in our scenarios of Section
2.3, Twitter). In the set-up we propose, this is done by using the Python
library Tweepy (https://www.tweepy.org/), which allows to retrieve a given
user’s tweet history.

Figure 2: CRAWLING validation set-up. CRAWLING is implemented in Python and
interacts with SUMO. This provides the back-end simulation from which CRAWLING
gathers the relevant data through TraCI. The directions obtained via Algorithm
1 are fed back to the simulation environment via the interface TraCI. For
example, in the validation scenarios described in Section 2.3, CRAWLING
receives data such as parking availability or obstructed road links, which are
used to compute directions to connected cars equipped with our service.
CRAWLING also interfaces via a Social Interface module with information on
social media (in our second scenario, Twitter).

In the CRAWLING implementation, the discrete time steps are not uniform but
are rather associated to the vehicle changing link (i.e., when the vehicle
transitions state). This design solution removes the need for the cars to have
a synchronized clock. Algorithm 1 is then implemented via a receding horizon
strategy, thus allowing to handle possible changes in the environment.
Specifically, every time (say, $t-1$) a given car equipped with CRAWLING
transitions to a new link the algorithm:

  * •

gathers the available data and sources (in the setting of Figure 2 this is
done by parsing the data from SUMO through TraCI and from Twitter via Tweepy);

  * •

builds the reward based on new information that might have become available
during the transition to the new link;

  * •

computes the optimal plan of actions for the next $N$ links according to
Algorithm 1;

  * •

determines the next direction by sampling from
$\tilde{\pi}(\mathbf{x}_{t}|\mathbf{x}_{t-1})$. The car is then controlled
through TraCI by setting the direction obtained from the sampling.

In our code (see our gitub repository for the details) connected cars are
encoded by an _agent_ Python class, which contains information about the
user’s goal (i.e., the route/destination the driver vehicle would like to
follow/attain). Algorithm 1 used by CRAWLING also has a Python class, which
takes an agent as argument (i.e., a vehicle). This class regroups all the
methods used for the algorithm, namely the computation of the KL divergence, a
receding horizon control loop and a sampling mechanism. A simulation file is
also provided to manage the key interfaces between the agent, CRAWLING and the
simulator used to assess its performance (i.e, SUMO). Specifically, the
simulation file includes functions for updating the state of the CRAWLING
vehicle in the simulation, updating the reward and performing simulation steps
through the SUMO-Python interface TraCI. The simulation file for Scenario $1$
(see Section 2.3) also logs results when the simulation is over, while the
simulation file for Scenario $2$ (see Section 2.3) contains the necessary code
to interface CRAWLING with social media, namely Twitter. The file implements a
parsing function that, monitoring specific users (one of the authors in this
case), is called at every step. If the tweet parsed by our code has the
hashtag ’#sumo_experiment’ it is considered for parsing. In this case, the
function splits the string into individual words and searches for the word
’blocked’ (we leave the design of a more refined parser for future research)
and for a road link identifier. Then, the date of the tweet is examined to
ensure the tweet has an impact on the current trip: if the tweet was posted
before the current date it is ignored. Finally, if all the conditions are met,
the blocked road link is assigned a very negative reward as described in
Section 3.3.

Figure 3: Campus road network. Highways and parking lots ate represented by
their respective international symbols.

###  2.3 Scenarios description

We now describe the scenarios (Scenario $1$ and Scenario $2$ in what follows)
that are used to validate CRAWLING. The two scenarios were selected to
validate different aspects of our service. Namely, with Scenario $1$ we wanted
to verify the effectiveness of CRAWLING in smoothly managing a flow of cars
that, without our service, could possibly create road blocks. As such, this
scenario is centered around the management of a fleet of cars entering the
University of Salerno campus during morning rushes. Scenario $2$ was instead
aimed at verifying how CRAWLING would adapt to incoming information about road
closures made available via a Twitter account.

Scenario $1$. This scenario simulates a morning rush hour at the campus of the
University of Salerno. The campus of the University of Salerno, shown in
Figure 3 is served by two highway exits, and has three parking lots (in our
simulations, each parking lot can accommodate up to $50$ cars). The highway
exits and corresponding campus entrances will be referred to as southern and
northern entrance and the parking lots as Multipiano, Terminal and Biblioteca
parking lots (see Figure 3 for the position of such parking lots on the campus
map). In this scenario, a fleet of $150$ cars (i.e., the maximum number of
cars that can be accommodated in the simulation) arrives on campus before the
teaching begins, with students and faculty staff searching for parking spaces.
In particular, $100$ cars arrive from the northern highway exit and seek to
park on either Terminal or Biblioteca, while the $50$ remaining cars arrive
from the south and reach the Multipiano parking lot. The cars arrive on campus
one by one at $15$-second intervals, with the order of arrival being shuffled.
That is, when each car arrives, its destination on campus and whether it is
equipped with CRAWLING or not, are randomly selected. While cars arrive to
campus, roadworks are being carried out on the main ramp leading from the
northern highway exit to the campus, rendering traffic on the corresponding
links (highlighted in blue in Figure 5) difficult (the vehicles using such
links have their speed restricted to less than one kilometer per hour). This
ramp also corresponds to the preferred route of uncontrolled cars (that is,
cars not equipped with CRAWLING) that seek to park in Terminal. In Section 3
we use this scenario to benchmark the effectiveness of CRAWLING in properly
managing the flow of cars. Simulations with varying amounts of controlled cars
are performed to quantify performance.

Scenario $2$. In the second scenario, only two cars are considered. They both
enter the campus from the northern highway exit, at an interval of $30$
seconds, and seek to reach the Biblioteca parking lot. Both cars are equipped
with CRAWLING. Within the scenario, the ramp leading directly from the highway
exit to the parking lot is closed. Specifically, after the first car passes
through the exit, the ramp is shut off completely and this information is
shared through Twitter (by e.g., pedestrians in the area or the local public
authority). This information is gathered by CRAWLING and leveraged to re-route
the second car entering in the simulation, to find an alternative route that
would properly allow it to park in a suitable parking space.

##  3 Results

We now describe the results obtained with CRAWLING on the two scenarios of
Section 2.3. To do so, we first empirically investigate the computational load
incurred by CRAWLING (and discuss our design choices to make the algorithm
suitable for routing applications) and then we describe the main settings of
our simulation framework. The code can be accessed at
https://tinyurl.com/wcwvcwaj. Note that, to replicate our simulations, a
working installation of SUMO, TraCI, Tweepy and the main scientific computing
Python libraries is required, along with a Twitter account with developer
access.

###  3.1 Computational performance

To make CRAWLING suitable for in-car operation, we leverage the fact that cars
being on a given link (i.e., state $\mathbf{x}_{k-1}$) can only transition to
an outgoing link (that is, $\mathbf{x}_{k}$ can only be a link in the set of
outgoing neighbors of $\mathbf{x}_{k-1}$). This means that the support of the
pfs $\pi(\mathbf{x}_{k}|\mathbf{x}_{k-1})$,
$p(\mathbf{x}_{k}|\mathbf{x}_{k-1})$ and
$\pi(\mathbf{x}_{k}|\mathbf{x}_{k-1})$ is restricted to the outgoing
neighboring links of $\mathbf{x}_{k-1}$. Hence, only the neighbors of
$\mathbf{x}_{k-1}$ need to be considered in the computations of Algorithm 1.
Thus, in the algorithm implementation: (i) the set of outgoing neighbors
associated to the current link of the car is determined; (ii) computations are
subsequently performed only over the neighborhood (which depends on the time
horizon) rather than over the full state space (which would amount to the full
map). Using this approach, we empirically investigated if the service is fast
enough for in-car applications. We did this by running CRAWLING on each link
of the University Campus map in Figure 3 and logging the average running time.
On this map, each road link is connected, on average, to $7$ other links. We
repeated these simulations by varying, across them, both the amount of data
sources available to the decision-maker (i.e., $S$ was gradually increased
between $1$ and $6$) and the time horizon (i.e., $N$ was gradually increased
between $0$ and $5$). The results are summarized in Figure 4, leftward panel.
The figure illustrates that the computation time is linear with respect to the
number of sources (Figure 4, middle panel). This is due to the fact that
Algorithm 1 iterates once per source at each time step. More interestingly,
the computation time is approximately exponential with respect to the time
horizon (Figure 4, rightward panel). This is aspect is essentially due to the
exponential increase in the state space (even if reduced as described above)
as the time horizon, $N$, increases.

Figure 4: CRAWLING execution time as a function of available sources and time
horizon. Leftward panel: computation time (in seconds) as a function of both
time horizon and number of services. Middle panel: computation time (in
seconds) as a function of the time horizon with $6$ available sources.
Rightward panel: computation time (in seconds) as a function of the amount of
sources for a time horizon of $5$ steps ahead.

###  3.2 Simulation settings

We now report the settings that are used to implement the scenarios of Section
2.3 and to obtain the results of Section 3.3.

Scenarios settings. The parameters are set before running the simulation. In
what follows we simply say that vehicles equipped with CRAWLING are controlled
and vehicles without the service are uncontrolled. First, we created lists
containing: (i) the starting points and target parking lots for uncontrolled
vehicles; (ii) the target behavior for controlled vehicles. These lists are
then shuffled to randomize the departing order of the vehicles in the
simulation. For simulations involving both controlled and uncontrolled
vehicles, the indexes of controlled and uncontrolled vehicles are randomly
assigned. All this information is stored as .npy files. Namely: for Scenario
$1$, the files agent.npy and foe.npy contain this information. These files are
generated before each simulation to avoid biased results. This can be done
using the notebook Simulation launcher.ipynb. The relevant maps were imported
from OpenStreetMap (https://www.openstreetmap.org/) using the netconvert
software and cleaned up using netedit. A full tutorial for this procedure can
be found in the SUMO online documentation. At the beginning of each
simulation, SUMO loads the map, while TraCI adds each car from the .npy files
to the simulation. The sources, stored as numpy arrays, are loaded when
CRAWLING is launched. While SUMO runs the simulation, information including
vehicle data and network conditions is obtained in TraCI and transmitted to
CRAWLING, which builds the reward.

Car settings. All cars are implemented as TraCI agents. Controlled cars query
CRAWLING for directions each time they transition to a new link, while
uncontrolled cars are assigned a pre-defined trajectory at the beginning of
the simulation (the trajectory is determined by the built-in SUMO routing
function that determines the shortest path to the destination). Uncontrolled
cars are set to automatically park at the end of their course if possible. On
the other hand, controlled cars are assigned a parking space if they arrive to
a non-full parking lot. If the parking lot is full, both controlled and
uncontrolled cars are rerouted by assigning them a new, non-full parking lot
(for uncontrolled cars this is done by assigning them a new destination in
SUMO, while controlled agents are assigned a new target behavior).

Figure 5: Northern section of the campus with obstructions highlighted in blue
for Scenario $1$. Map imported from OpenStreetMap in SUMO via its netconvert
tool

###  3.3 Results

We now describe the simulation specifics and report the results.

Reward and behaviors settings. The reward encompasses environmental
disruptions. In our use-case, this is computed from the state of the road
links and is related to the availability of parking spaces. Specifically, at
each time step, each link adjacent to a parking lot is assigned a reward of
$100$ if the parking lot has vacant spaces, and $-10$ if not. Road links on
which traffic is perturbed are assigned an additional negative reward: (i)
$-20$ if the traffic is heavily slowed down on the link. This has been
simulated, as in Scenario $1$, by enforcing a speed limit of less than one
kilometer per hour on the perturbed road links; (ii) $-100$ if the road link
is blocked altogether (as in Scenario $2$). Before running the simulations, a
set of sources is compiled by using SUMO’s routing function: each source is
designed to represent directions leading to a different point in the network.
We build $6$ sources, using the highway exits, the parking lots and the north-
western side of the campus as destinations. This ensures that the directory of
behaviors available to the decision-maker provides a wide coverage of
directions from each lane. For each road link, the probability functions
$\pi^{(i)}(\mathbf{x}_{k}\mid\mathbf{x}_{k-1})$ of the sources are built by
assigning a high probability to the lane indicated by the routing while the
other neighbor links have a small, uniform, probability of being selected. We
also built a last source by merging behaviors of cars routed towards the
Biblioteca and Terminal parking lot. This source can be thought of as
emulating the traces from previous vehicles having navigated the campus. In
the following, the target behavior of each connected car is selected among the
sources.
Scenario $1$ specifics. Our first set of simulations follows the first
scenario outlined in Section 2.3. We implemented this scenario by simulating
$150$ cars arriving at the campus at $15$-second intervals (with a simulation
lasting approximately one hour and twenty minutes of simulated time) and
seeking to park. All cars entering the campus via the Southern exit are
directed towards the Multipiano parking lot. Uncontrolled cars entering
through the Northern exit all seek to park in the Terminal parking lot. On the
other hand, the target behavior of controlled cars entering through the
Northern exit leads to either Biblioteca or Terminal (this can be interpreted
as a target behavior being built from traces of previous CRAWLING cars having
similar goals), highlighting the interest of obtaining directions through
crowdsourcing stochastic policies. However, the road leading from the northern
entrance to the roundabout immediately to its East is obstructed, causing
traffic to significantly slow down (as described above, the speed limit on
such road links is reduced to less than one kilometer per hour). As specified
in Section 2.3, this obstruction occurs on the preferred route of uncontrolled
cars directed towards Terminal, that is, uncontrolled cars within the $100$
cars entering through the Northern highway exit. This is illustrated in Figure
5, which captures a section of the full campus map. Such obstructions can
originate from road work, or model a limited capacity of the road link related
to e.g. severe climatic conditions. In the results shown next, we run
different set of simulations with $0$, $50$, $100$ and $150$ controlled cars.
This was done to evaluate the penetration rate of the service, showing its
effectiveness as the number of cars equipped with CRAWLING increases.

Results for Scenario $1$. As shown in Figure 6, the fully uncontrolled fleet
(no vehicles equipped with CRAWLING) fails to park every agent in the
allocated time. Indeed, all uncontrolled cars arriving from the northern
highway exit are routed to the obstructed lanes. On the other hand, when the
fleet is fully controlled (with all vehicles being equipped with our service),
CRAWLING only needs approximately half the duration of the simulation to park
every car. Namely, CRAWLING allows each controlled cars to adapt its route to
avoid the obstruction, effectively orchestrating the use of the available
parking spaces. Specifically, we observed that connected cars entering from
the Northern exit were routed to the Biblioteca parking lot until it became
full. When this happened, CRAWLING rerouted the remaining cars to the Terminal
parking lot by a detour route avoiding the obstructed road links. Both
controlled and uncontrolled cars entering from the southern highway exit reach
the Multipiano parking lot, as it is the closest.

Figure 6: Confidence interval plot of the simulation results. Solid lines
represent the mean value, while the shaded area is the standard deviation.
Fully controlled fleets manage to fully park within half of the simulation
time, while fleets with less controlled cars take longer, failing to find
parking spaces for every car before the simulation ends in the extreme case.
Note that fleets with just one third of the cars using CRAWLING still
significantly outperform the baseline of uncontrolled cars.

To complement our analysis, we also recorded the average time spent by the
average car on an obstructed link and the average time-to-parking over all
simulations. These are shown in Table 1, together with the results from
Welch’s t-test[40], which we used to verify the statistical significance of
our simulations. The test is aimed at checking whether two random samples
originate from distributions having different means. In other words, a p-value
less than $0.05$ would mean that a set of simulations is statistically
insignificant and needs to be rejected. Specifically, we use the p-value to
compare the average parking time obtained in the five first simulations
performed with a set of parameters with the five last simulations following
the same parameters.

Scenario | Time (s) spent on obstruction | Average time-to-parking (s) | p-value
---|---|---|---
Fully uncontrolled | 754.2 | 2142.5 | 0.06
50 controlled | 613.1 | 1999.0 | 0.63
100 controlled | 280.2 | 1464.6 | 0.76
150 controlled | 4.1 | 1186.2 | 0.46
Table 1: Summary table for the numerical experiments. All times in seconds.

Table 1 confirms the qualitative behaviors shown in Figure 6. In particular,
the increase in the number of cars equipped with CRAWLING decreases both the
time spent on obstruction and the time-to-parking. This is due to the fact,
with more cars being controlled via CRAWLING, these were able to coordinate to
avoid the unfavorable road link, while being directed towards a parking with
space with effective capacity to accommodate the incoming cars.

Scenario $2$ specifics. For the second scenario in Section 2.3 we considered
two controlled cars entering in the campus from the North entrance, both with
the goal of reaching the western parking lot. However, after the first car
exits the highway, the road is being blocked. This information, which causes
the reward associated to the corresponding road link to sharply decrease, is
twitted. Specifically, from one of the authors’ Twitter profile, the following
tweet is made: _North highway ramp blocked $\\#$sumo_experiment_ after the
first car’s passage. Periodically, our implementation of CRAWLING checks the
Twitter account’s post history. The last tweet is parsed and, if an accident
is detected – see Section 2.2 for a description of the parsing mechanism –
CRAWLING assigns a very negative (i.e., $-100$) reward to the road link where
the disrupting event is signalled.
Results for Scenario $2$. The results are summarized in Figure 7. Such a
figure illustrates, in panel (a), the key campus areas for the scenario. At
the beginning of the scenario, no road obstruction is detected and indeed, as
shown in panel (b), the first car entering in the simulation normally
transitions through the Northern exit, following the shortest path through the
ramp. After the car passes the ramp, the road obstruction occurs (the
obstructed link is highlighted in blue in panel (c)) and the obstruction is
reported via a tweet (in this experiment, from one of the authors, see panel
(d)). Panel (d) showcases the corresponding tweet that was issued upon
detection of the road blocking. Then, panel (e) shows the result of CRAWLING
adapting to the new information. Indeed, the route for the second car is re-
computed by our service to avoid that the second car enters in the obstructed
road link. This is a result of CRAWLING detecting the reward change due to the
tweet. An interesting question is to determine a measure of trust for the
tweets to be used by CRAWLING. We leave this topic for our future research. At
the end of the simulation – panel (f) – both cars achieve their goal by
reaching their desired parking lot. A video of the corresponding simulation is
also available at https://tinyurl.com/wcwvcwaj.

Figure 7: Snapshots taken from the simulation for Scenario $2$. Panel (a):
areas of the campus interested by the use-case. Specifically, the red
rectangles denote the position of the snapshots on the map. Panel (b): first
car taking the fastest route from the Northern entrance when there is no
obstruction. Panel (c): the route is blocked after the first car has passed
the Northern entrance. Panel (d): the information about the disrupting event
is shared via a tweet. Panel (e): CRAWLING adapts to handle the disruption and
the second car takes an alternate route. Panel (f): both cars reach the
desired parking lot.

##  4 Discussion and concluding remarks

We presented the principled design of CRAWLING, an in-car service for smart
parking, for which we make our code available. The service is based on a
recent data-driven control algorithm, where the cost function has a Kullback-
Leibler divergence component, ensuring that the car tracks a certain target
behavior, i.e. a route that the user would like to take. A reward signal is
also incorporated into the cost, compiling additional information that is
collected through a network of urban sensors and on social media. A key
feature of our service is that it determines turning probabilities for cars.
Hence, the policy that is computed by the service is stochastic and it allows
to both embed in the framework the possibility that drivers do not follow the
indications provided by CRAWLING and to guarantee some desired level of
(differential) privacy for users participating to the service. After
describing the key functional components of CRAWLING, we proposed a stand-
alone, general-purpose implementation of our service and investigated its
effectiveness on two Smart Cities scenarios, leveraging SUMO for microscopic
traffic simulations. With our first scenario (morning rush) we investigated
what happens as the number of vehicles equipped with CRAWLING increases,
empirically finding that parking times can be considerably improved even when
only $30\%$ of the vehicles were controlled by our service. These simulations
were also performed with a limited amount of sources, providing encouraging
insights into the system’s ability to efficiently make decisions based on a
limited set of available services. With our second validation scenario, we
investigated the effectiveness of CRAWLING to adapt to environmental changes
reported via social media: simulations once again confirmed the benefits of
equipping cars with our service.

In a broader context, a number of considerations can be drawn from our
findings. While for concreteness we tailored CRAWLING towards parking
management, its approach can be exported to other routing applications. We see
our findings as a first step to implement an internet of skills for connected
cars. In this framework, we envisage cars to collaboratively exchange learned
skills so as to create a collective intelligence enabling cars to augment each
others’ abilities through crowdsourcing. We also note that some ventures have
already started delivering services based on data collaboratively shared by
their users, see for example the Waze application[41]. Interestingly, similar
mechanisms based on crowdsourcing can be found in neuroscience – see, for
example the recent thousand brains theory[42], which postulates that the
neocortex in our brain does not compute brand new behavioral models but it
patches simpler models from the cortical columns. Finally, in the context of
reinforcement learning, a mechanism related to CRAWLING has been recently
proposed to orchestrate the use of learning-based and model-based policies to
tackle certain control tasks. Interestingly, it has been shown that mechanisms
orchestrating these heterogeneous policies can be designed so that they can
tutor each other and this, in turn, improves learning efficiency and
performance[43, 44, 45]. Inspired by these studies, possible future directions
of our research might involve both embedding tutoring mechanisms in CRAWLING
and exploring the links between the approach we presented and certain recent
neuroscience theories. We will also embed strategies to filter social media
information for their effective use in CRAWLING. Finally, we aim at
investigating whether CRAWLING can represent an effective mechanism to fairly
regulate possible competitive behaviors between vehicles equipped with our
service and legacy, manually-driven, vehicles when these compete for the same,
limited, resource.

## Author contributions statement

G.R. designed the research. E.G. implemented the service, developed the
simulations and assessed the numerical methods. Both authors evaluated and
discussed the numerical results and contributed in writing the paper.

## Additional information

Data availability
The code, and the corresponding detailed instructions, needed to replicate the
simulations can be found at: https://tinyurl.com/wcwvcwaj
Competing interests
The authors do not declare any competing interest.

## References

  * [1] Nations, U.  World urbanization prospects: The 2014 revision, highlights. department of economic and social affairs.  _Population Division, United Nations_ 32 (2014).
  * [2] Al Nuaimi, E., Al Neyadi, H., Mohamed, N. & Al-Jaroodi, J.  Applications of big data to smart cities.  _Journal of Internet Services and Applications_ 6, 25, DOI: 10.1186/s13174-015-0041-5 (2015).
  * [3] Silva, B. N., Khan, M. & Han, K.  Towards sustainable smart cities: A review of trends, architectures, components, and open challenges in smart cities.  _Sustainable Cities and Society_ 38, 697–713, DOI: https://doi.org/10.1016/j.scs.2018.01.053 (2018).
  * [4] Crisostomi, E. _et al._ (eds.) _Analytics for the Sharing Economy: Mathematics, Engineering and Business Perspectives_ (Springer, 2020).
  * [5] Russo, G.  On the crowdsourcing of behaviors for autonomous agents.  _IEEE Control Systems Letters_ 5, 1321–1326 (2020).
  * [6] Garrabé, É. & Russo, G.  On the design of autonomous agents from multiple data sources.  _IEEE Control Systems Letters_ 6, 698–703 (2021).
  * [7] Garrabé, É. & Russo, G.  Probabilistic design of optimal sequential decision-making algorithms in learning and control.  _Annual Reviews in Control_ 54, 81–102, DOI: https://doi.org/10.1016/j.arcontrol.2022.09.003 (2022).
  * [8] Tang, C., Wei, X., Zhu, C., Chen, W. & Rodrigues, J. J.  Towards smart parking based on fog computing.  _IEEE access_ 6, 70172–70185 (2018).
  * [9] Al Amiri, W. _et al._ Privacy-preserving smart parking system using blockchain and private information retrieval.  In _2019 International Conference on Smart Applications, Communications and Networking (SmartNets)_ , 1–6 (IEEE, 2019).
  * [10] Khalid, M., Aslam, N. & Wang, L.  A reinforcement learning based path guidance scheme for long-range autonomous valet parking in smart cities.  In _2020 IEEE Eighth International Conference on Communications and Networking (ComNet)_ , 1–7 (IEEE, 2020).
  * [11] Liu, M., Naoum-Sawaya, J., Gu, Y., Lecue, F. & Shorten, R.  A distributed markovian parking assist system.  _IEEE Transactions on Intelligent Transportation Systems_ 20, 2230–2240, DOI: 10.1109/TITS.2018.2865648 (2019).
  * [12] Singer, G., Overko, R., Yilmaz, S., Crisostomi, E. & Shorten, R.  Markovian city-scale modelling and mitigation of micro-particles from tires.  _PLOS ONE_ 16, 1–22, DOI: 10.1371/journal.pone.0260226 (2021).
  * [13] Jemmali, M., Melhim, L. K. B., Alharbi, M. T., Bajahzar, A. & Omri, M. N.  Smart-parking management algorithms in smart city.  _Scientific Reports_ 12, 6533, DOI: 10.1038/s41598-022-10076-4 (2022).
  * [14] Fahim, A., Hasan, M. & Chowdhury, M. A.  Smart parking systems: comprehensive review based on various aspects.  _Heliyon_ 7, e07050, DOI: https://doi.org/10.1016/j.heliyon.2021.e07050 (2021).
  * [15] Kondor, D. _et al._ The cost of non-coordination in urban on-demand mobility.  _Scientific Reports_ 12, 1–10 (2022).
  * [16] Frazzoli, E., Dahleh, M. A. & Feron, E.  Real-time motion planning for agile autonomous vehicles.  _Journal of Guidance, Control, and Dynamics_ 25, 116–129 (2002).
  * [17] Nha, V. T. N., Djahel, S. & Murphy, J.  A comparative study of vehicles’ routing algorithms for route planning in smart cities.  In _2012 First International Workshop on Vehicular Traffic Management for Smart Cities (VTM)_ , 1–6, DOI: 10.1109/VTM.2012.6398701 (2012).
  * [18] Montoya-Torres, J. R., Franco, J. L., Isaza, S. N., Jiménez, H. F. & Herazo-Padilla, N.  A literature review on the vehicle routing problem with multiple depots.  _Computers & Industrial Engineering_ 79, 115–129 (2015).
  * [19] Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I. & Naor, M.  Our data, ourselves: Privacy via distributed noise generation.  In Vaudenay, S. (ed.) _Advances in Cryptology - EUROCRYPT 2006_ , 486–503 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2006).
  * [20] Vellenga, K. _et al._ Driver intention recognition: State-of-the-art review.  _IEEE Open Journal of Intelligent Transportation Systems_ 3, 602–616, DOI: 10.1109/OJITS.2022.3197296 (2022).
  * [21] Nayak, A., Eskandarian, A. & Doerzaph, Z.  Uncertainty estimation of pedestrian future trajectory using bayesian approximation.  _IEEE Open Journal of Intelligent Transportation Systems_ 3, 617–630, DOI: 10.1109/OJITS.2022.3205504 (2022).
  * [22] Kitchin, R.  The real-time city? big data and smart urbanism.  _GeoJournal_ 79, 1–14 (2014).
  * [23] Batty, M. _et al._ Smart cities of the future.  _The European Physical Journal Special Topics_ 214, 481–518 (2012).
  * [24] Anvari, M. _et al._ Data-driven load profiles and the dynamics of residential electricity consumption.  _Nature Communications_ 13, 1–12 (2022).
  * [25] Liao, L. _et al._ A multi-sensory stimulating attention model for cities’ taxi service demand prediction.  _Scientific Reports_ 12, 1–13 (2022).
  * [26] Çolak, S., Lima, A. & González, M. C.  Understanding congested travel in urban areas.  _Nature Communications_ 7, 1–8 (2016).
  * [27] Zhang, R., Spieser, K., Frazzoli, E. & Pavone, M.  Models, algorithms, and evaluation for autonomous mobility-on-demand systems.  In _2015 American Control Conference (ACC)_ , 2573–2587 (IEEE, 2015).
  * [28] Duarte, F. & Álvarez, R.  The data politics of the urban age.  _Palgrave Communications_ 5, 1–7 (2019).
  * [29] Park, Y., Choi, Y., Kim, K. & Yoo, J. K.  Machine learning approach for study on subway passenger flow.  _Scientific Reports_ 12, 1–20 (2022).
  * [30] Schlote, A., King, C., Crisostomi, E. & Shorten, R.  Delay-tolerant stochastic algorithms for parking space assignment.  _IEEE Transactions on Intelligent Transportation Systems_ 15, 1922–1935, DOI: 10.1109/TITS.2014.2304356 (2014).
  * [31] Kondor, D. _et al._ Addressing the “minimum parking” problem for on-demand mobility.  _Scientific Reports_ 10, 1–10 (2020).
  * [32] Zhang, J. _et al._ Data-driven intelligent transportation systems: A survey.  _IEEE Transactions on Intelligent Transportation Systems_ 12, 1624–1639, DOI: 10.1109/TITS.2011.2158001 (2011).
  * [33] Pan, B., Zheng, Y., Wilkie, D. & Shahabi, C.  Crowd sensing of traffic anomalies based on human mobility and social media.  In _Proceedings of the 21st ACM SIGSPATIAL international conference on advances in geographic information systems_ , 344–353 (2013).
  * [34] D’Andrea, E., Ducange, P., Lazzerini, B. & Marcelloni, F.  Real-time detection of traffic from twitter stream analysis.  _IEEE Transactions on Intelligent Transportation Systems_ 16, 2269–2283, DOI: 10.1109/TITS.2015.2404431 (2015).
  * [35] Lopez, P. A. _et al._ Microscopic traffic simulation using SUMO.  In _The 21st IEEE International Conference on Intelligent Transportation Systems_ (IEEE, 2018).
  * [36] Kullback, S. & Leibler, R.  On information and sufficiency.  _Annals of Mathematical Statistics_ 22, 79–87 (1951).
  * [37] Ordóñez-Hurtado, R., Russo, G., Sinnott, S. & Shorten, R.  On parsing shared information: An application from the connected car domain.  In _Analytics for the Sharing Economy: Mathematics, Engineering and Business Perspectives_ , 205–225 (Springer, 2020).
  * [38] Lassoued, Y. _et al._ A hidden markov model for route and destination prediction.  In _2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC)_ , 1–6, DOI: 10.1109/ITSC.2017.8317888 (2017).
  * [39] Haarnoja, T., Zhou, A., Abbeel, P. & Levine, S.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  _CoRR_ abs/1801.01290 (2018).  1801.01290.
  * [40] Welch, B. L.  The generalization of ‘student’s’problem when several different population varlances are involved.  _Biometrika_ 34, 28–35 (1947).
  * [41] Shaheen, S. A.  Mobility and the sharing economy.  _Transport Policy_ 51, 141–142 (2016).
  * [42] Hole, K. J. & Ahmad, S.  A thousand brains: toward biologically constrained ai.  _SN Applied Sciences_ 3, 743, DOI: 10.1007/s42452-021-04715-0 (2021).
  * [43] Rathi, M., Ferraro, P. & Russo, G.  Driving reinforcement learning with models.  In Arai, K., Kapoor, S. & Bhatia, R. (eds.) _Intelligent Systems and Applications_ , 70–85 (Springer International Publishing, Cham, 2021).
  * [44] De Lellis, F., Russo, G. & Di Bernardo, M.  Tutoring reinforcement learning via feedback control.  In _2021 European Control Conference (ECC)_ , 580–585, DOI: 10.23919/ECC54610.2021.9654881 (2021).
  * [45] Lellis, F. D., Coraggio, M., Russo, G., Musolesi, M. & di Bernardo, M.  Control-tutored reinforcement learning: Towards the integration of data-driven and model-based control.  In Firoozi, R. _et al._ (eds.) _Proceedings of The 4th Annual Learning for Dynamics and Control Conference_ , vol. 168 of _Proceedings of Machine Learning Research_ , 1048–1059 (PMLR, 2022).