# Validating a virtual human and automated feedback system for training
doctor-patient communication skills

Kurtis Haut∗ Caleb Wohn∗ Benjamin Kane∗ Tom Carrol† Catherine Guigno∗
Varun Kumar∗ Ron Epstein† Lenhart Schubert$*$ Ehsan Hoque∗
∗University of Rochester Department of Computer Science
† University of Rochester Medical Center

###### Abstract

111Kurtis Haut and Caleb Wohn share the distinction of first authorship.

Effective communication between a clinician and their patient is critical for
delivering healthcare maximizing outcomes. Unfortunately, traditional
communication training approaches that use human standardized patients and
expert coaches are difficult to scale. Here, we present the development and
validation of a scalable, easily accessible, digital tool known as the
Standardized Online Patient for Health Interaction Education (SOPHIE) for
practicing and receiving feedback on doctor-patient communication skills.
SOPHIE was validated by conducting an experiment with 30 participants. We
found that participants who underwent SOPHIE performed significantly better
than the control in overall communication, aggregate scores, empowering the
patient, and showing empathy ($p<0.05$ in all cases). One day, we hope that
SOPHIE will help make communication training resources more accessible by
providing a scalable option to supplement existing resources.

###### Index Terms:

Doctor-Patient Communication, Artificial Intelligence, Web-based Feedback
System

##  I Introduction

Figure 1: SOPHIE Feedback System \- The feedback is divided into four
sections; Transcript, Empower, be Explicit, and Empathize. The upper left
contains the transcript with embedded conversational suggestions. The Empower
section contains the metrics number of questions asked, number of open-ended
questions asked, and turn-taking with lecture and question coloring. The be
Explicit section contains the metrics hedge words percentage with word cloud,
speaking rate and reading level. The Empathize section contains the metrics
personal pronouns percentage, average empathy score (1-7) with word cloud, and
positive emotion (sentiment) over time graphs for the user, SOPHIE, and the
“ideal” sentiment trajectory.

60% of late-stage cancer patients leave their doctor’s office without fully
understanding their prognosis [1] and 79% of patients feel emotionally
unsupported by their doctors [2]. Past research has shown that poor
communication by doctors leads to lower quality healthcare outcomes at a
higher cost [2][3][4][5][6]. Unfortunately, low cost communication training
videos or reading materials have been shown to have little effect [7][8].
Training courses using standardized patients (SPs) are a viable remedy widely
used in medical schools [9][10]. For example, our institution offers
interdisciplinary workshops for practicing patient care professionals (e.g.,
physicians, nurses, advanced practice providers, social workers, and
chaplains) through the Advanced Communication Training (ACT) program[11],
which teaches the MVP (Medical situation, Values, Plan) paradigm and
emphasizes the 3 E skills: Empower, be Explicit, Empathize skills[12].
Receiving feedback has been found to improve the communication skills of
clinicians. For example, feedback from communication coaching experts based on
recorded interactions with real patients has been shown to improve a
clinician’s ability to empathize with their patient and empower them by
eliciting questions [13]. However, due to the cost and limited availability of
human SPs and coaches who can provide relevant feedback, these traditional
approaches are hard to scale. The need for a scalable solution is compounded
by the diminishing effects of communication training over the course of a
physician’s career [14].

We developed SOPHIE (Standardized Online Patient for Health Interaction
Education) [15] to address this need. SOPHIE is a fully automated web-based
system allowing medical professionals to have a conversation with a virtual
human using their computer’s speakers and microphone. After the conversation,
the system automatically analyzes the transcript to provide immediate,
quantified, and personalized feedback.

Using virtual patients for educating health professionals is not a new concept
[16]. Prior work has shown the value of virtual patients in practicing empathy
in a low stress environment [17], and much promise is granted to using virtual
patients as a cost-effective pedagogical approach for developing countries
[18]. The recent advancements in avatar generation and natural language
understanding have opened up exciting possibilities for creating more
realistic, interactive systems capable of providing user feedback that was
previously not possible.

Indeed, the feedback component of the SOPHIE system represents a distinct
contribution (see Fig. 1). Although prior work has shown that receiving
feedback helps clinicians improve their communication skills [19], there are
few existing tools to generate feedback automatically [20]. Our feedback
system is unique in that it utilizes the previously validated MVP/3E’s model
of doctor-patient communication. It provides a quantitative analysis of the
conversation for medical professionals to review, as well as text
recommendations for improvement.

We validated the feasibility of this system in a experiment with 30
participants (See Fig. 4). We found that participants who underwent the
educational intervention with SOPHIE performed significantly better in overall
communication and achieved higher aggregate scores compared to participants
who did not ($p<0.05$). We also observed statistically significant results for
empowering the patient and showing empathy. We hope the SOPHIE system will
eventually be utilized as a scalable solution to supplement existing
communications training or as a low-cost alternative for resource deprived
communities.

##  II Methods

###  II-A The SOPHIE System

The educational intervention with the SOPHIE system has three components. The
user begins by watching an instructional video about the MVP/3E’s
communication paradigm followed by viewing a tutorial video on how to use the
SOPHIE system. The final component of the intervention is two conversations
with SOPHIE, including feedback after each conversation. SOPHIE portrays an
older female patient with advanced lung cancer who is seeking information
about the prognosis. The feedback page is split into 4 main sections: a
transcript, and one section for each of the three E’s (see Fig. 1). The
transcript section allows the user to review their conversation. Segments of
the conversation where the medical professional engaged in lecturing (i.e.
spoke for too long) are given a red background, and segments where the medical
professional empowered the patient by asking a question are given a green
background. Some segments in the transcript display suggestions for open-ended
questions or empathetic statements that the medical professional could have
used. The feedback system was developed through an iterative design process
with close collaboration between programmers and palliative care specialists,
and many of the metrics are based on statistical analysis of doctor-patient
communication, as discussed in [21].

###  II-B Dialogue Management

SOPHIE’s dialogue manager uses a symbolic, schema-based approach. Although
LLMs have recently achieved impressive results [22][23], at the time of
development, they were deemed ill-suited to this task for a variety of issues.
Bender et al. argued that large language models (e.g., the current state-of-
the-art) are generally insufficient for true language understanding as well as
carry their own risks and potential ethical issues [24]. Large language models
also come with the additional risk of going “off the rails” of the
conversation parameters which makes them unpredictable and difficult to
control. Without having the ability to control the dialogue, presenting the
user with opportunities to practice specific communication skills poses a real
challenge in application consistency. As a result of these issues, we chose to
take a symbolic approach. The conversations with SOPHIE are driven by eta,
which uses flexible, modifiable dialogue schema (i.e., expected event types
expressed as conversational statements) to imitate natural human
conversations. The dialogue manager dynamically plans and enacts the
conversation in real time by combining a user interpretation process with
these dialogue schema[25][26][27]. See figure 3 for an example of the dialogue
and see Fig. 2 for an overview of the dialogue manager’s architecture). The
user interpretation process is handled by a set of pattern transduction rules
that map user utterances into simplified context-independent “gist clauses”
given the immediate context of the preceding dialogue turn. The gist clause
provides an explicit representation of the meaning of the user’s utterances
that the system can then respond to. Response generation, which is also
handled by a pattern transduction process, can involve the selection of a
particular reaction by the system to the user’s gist clause, or the invocation
of a new schema (e.g., the system may invoke a schema for SOPHIE discussing
her medical concerns if asked a relevant question by the doctor). In the case
where the system fails to extract a gist-clause, it may either ask the user to
repeat and clarify their utterance, or give a generic default reaction
specific to the current schema. Ultimately, a schema guided approach to
dialogue management was chosen over using a large, neural language model (such
as GPT3) in order to have more control over the dialogue.

Figure 2: Eta Dialogue Management Architecture \- The dialogue manager relies
on a database of general schema knowledge including dialogue schemas (top), as
well as dialogue context and episodic memory (bottom). The dialogue manager
interleaves processing of several submodules for processing input (blue;
left), guiding system behavior through dynamic instantiation of a dialogue
schema (green; center), and generating output (red; right). The numbered edges
represent the flow for how the system interacts with the user.

###  II-C Quantifying Complex Human Communication Skills

Empower - We quantified empowerment using three key metrics; Questions-asked,
open-questions asked and turn-taking. The need to quantify both types of
questions was made apparent after consultation with Oncologists and Palliative
Care specialists at University of Rochester Medical Center (URMC). A closed
question helps the medical professional check patient understanding of the
medical situation and prognosis while an open-ended question gives the patient
an opportunity to reveal more sensitive information about their emotional
state. We used expression matching to determine what type of question was
asked and kept track of the total number in each category. Questions are
useful for quantifying empowerment because this inevitably invites the user to
take control of the conversation and thus tends to empower them. For example,
by asking a question, the patient can express their concerns and voluntarily
reveal external factors that would otherwise be hidden to the medical
professional.

Turn-taking was quantified by keeping track of the total time for both the
user and SOPHIE respectfully. Whether or not the user was lecturing for their
turn was based off a previous voice study [21] and informally takes place when
a medical professional is speaking for too long. This quantifies empowerment
because unequal turn taking could signal a lack of empowerment for the user if
their turns are too long and frequent in comparison to SOPHIE’s.

Empathize -  We quantified empathize using three key metrics; sentiment
trajectory, empathy word cloud and personal pronouns. Sentiment trajectory was
computed based off the work of Ali et al. [21], who analyzed sentiment in the
VOICE dataset led by Sen et al. [28]. They defined a “sentiment trajectory” as
an average sentiment vector across time. Sentiment was computed using VADER
[29] and is on a -1 to +1 scale. They used k-means clustering to identify
“sytles” of sentiment trajectory and logistic regression to identify if any
style was associated with good conversation outcomes where “good” is
determined by the level of patient prognosis understanding. The best style was
“dynamic,” having high sentiment early on in the conversation, low sentiment
in the middle (likely to match patient sentiment after hearing the prognosis),
and high sentiment at the end (likely to express encouragement, care and
support). Our idea was that perhaps some of the complexity of empathy could be
captured and quantified overall using this sentiment trajectory.

The empathy word cloud was computed using work from Sedoc et al. [30] who
developed a lexicon which maps 10k words to empathy ratings on a 1-7 scale
using a Mixed-Level, Feed Forward Network. We mapped every word spoken by the
user through this lexicon and computed the average empathy from that. The word
cloud is creating using the 15 most frequent words. We hoped that this would
roughly quantify empathy for the entire conversation, but recognize the
weakness in its inability to quantify statements on a sentence-level (which is
where most empathy is likely to take place).

Personal pronouns were chosen to quantify empathy based of work by Sen et al.
in 2017 [28] who used LIWC to analyze the correlation between different
categories of words and patient ratings of doctors in the VOICE dataset.
Interestingly, they found that higher rankings were correlated with the use of
personal pronouns (e.g. I, You, etc.). We computed pronoun usages using NLTK
part-of-speech tagging [31]. Intuitively, using pronouns makes a conversation
more empathetic by appearing more personable as compared to generic, disease
specific speech.

be Explicit -  We quantified being Explicit using three metrics; speaking
rate, reading grade and hedge words. Speaking rate was found to be associated
with patient understanding [21] and is related to being explicit (e.g., if a
physician speaks too slowly, or too quickly they probably are not
communicating in an explicit manner). This is computed simply by taking the
average words spoken per minute.

Reading grade was chosen quantify the complexity of the speech to address the
issue of doctors using too much medical jargon when communicating a prognosis.
Complex speech makes it more difficult for patients to understand their
medical situation and we make the assumption that less complex speech is more
explicit. We computed the reading grade using the standard measure of the
Flesch-Kincaid readability test[32] which outputs the linguistic complexity in
terms of U.S. school grades (e.g., 1st grade to 12th grade).

Hedge words were computed using a simple list of hedge words established from
prior work by counting the percentage of a user’s words that appeared on the
list. The most frequent 10 hedge words are made note of and a word cloud is
constructed. The 2020 Horowitz et al’s paper on the MVP paradigm which SOPHIE
attempts to model mentions avoiding hedging as a key part of being explicit
[12]. Thus, measuring hedging helps to quantify this skill directly for the
user.

###  II-D Experiment

We conducted an experiment consisting of 30 participants with medical
backgrounds (12 medical students, 9 nurses, 4 internal medicine residents, 2
physician’s assistants, 2 psychologists, and 1 hospital chaplain).
Participants were randomized (1:1 ratio) into intervention and control groups,
stratified by professional/training background. The intervention group
underwent the educational intervention with the SOPHIE system while the
control group received no training (see Fig. 4a and 4b).

After the educational intervention, we evaluated the communication skills of
the participants using human standardized patients (SPs). Every participant
had a conversation with a SP via a video call. Immediately after each
interaction, the SP rated the conversation using a standard scale developed
with assistance from palliative care specialists. These ratings were
statistically compared using a Mann Whitney U test to determine whether there
were any significant differences between the the two groups as a result of
undergoing the educational intervention with the SOPHIE system (see Fig. 4c).
Additionally, participants in the treatment group completed a UI/UX survey
designed to inform future iterations of the SOPHIE System.

###  II-E Justification for Evaluation Metrics

SP Rating Scale - Our rating scale was developed in close collaboration with
URMC Oncologists and Palliative Care Specialists. There was no existing rating
scale that was appropriate as is for our experiment although prior work exists
[33]. We wanted to measure whether a clinician improved based on behaviors the
SOPHIE system was designed to give feedback on and reinforce. The full rating
scale can be seen in table I and is based on behaviors the human SP observes
during their interation.

UX/UI Rating Scale - We broke the UX scale down into three components; namely
system usability, virtual human and dialogue (see Figure 5). We chose a
representative sample of system usability statements from the well-established
System Usability Scale (SUS)[34][35]. The statements for the virtual human and
dialogue sections were developed by the research team after robust
discussions. We wanted to evaluate the realism of the virtual human (e.g., the
ability to look and sound like a real cancer patient). Realism in this context
is meant to include holistic aspects of the interaction such as lip syncing.
Discussions with our medical collaborators indicated the importance of
emotional expression in real patient encounters and we therefore incorporated
statements to quantify the user’s perception of the virtual human’s ability to
emote. Our dialogue statements were focused on quantifying the quality of the
dialogue itself. Aspects of the dialogue such as whether the responses were
fluent, natural, relevant, logical and/or emotionally expressive were selected
as the criteria. All statements were evaluated on a 1-5 likert scale with 5
representing strong agreement.

Our UI rating scale was also developed by the research team. We simply had the
research subjects evaluate the utility of each UI element on the system
feedback screen (see Fig. 1 using a 1-5 likert scale with 5 representing high
utility. Likert scales allows for more nuance [36] in survey responses and are
appropriate for gathering feedback for system improvement.

Figure 3:

Sample excerpt from conversation with SOPHIE

> SOPHIE: I’ve already scanned the results, but don’t understand what they are
> telling me. Could you explain what they mean?
>  user: So unfortunately Sophie I have some bad news. It looks like the
> cancer has grown and spread.
>  SOPHIE: Those are not the words I wanted to hear. I mean, I was bracing for
> the worst, since I could tell by the pain that it’s bad. But to hear that
> the cancer has spread is quite depressing. What does it all mean for me?
>  user: How much information would you like to know about the prognosis?
>  SOPHIE: I feel very anxious about my condition. I feel like it’s gotten
> worse. I want to know what this means for me.
>  user: What concerns do you have about the future?
>  SOPHIE: What worries me the most is just how uncertain my future is. Some
> days I believe my condition will get better and others I brace myself for
> the worst. Is there any way you can let me know what I should expect?

##  III Results

###  III-A Ratings Comparison

Figure 4: Experiment with 30 participants \- a) Intervention group, underwent educational intervention with SOPHIE before speaking to SP. b) Control group, received no training before speaking to SP. c) Overall ratings comparison between control (blue) and intervention (tan) bold denotes significant differences. The numbers have been normalized to a 0-1 scale with 1 being “good.” The raw numbers and full question text can be found in Table I by looking up the question ID. (Images of participants used with permission). TABLE I: Average SP ratings for each item in the rating scale. Italics and an asterisk (“*”) denote $p\leq 0.05$ ID |  Question | Control Mean | Intervention Mean | p-value
---|---|---|---|---
q1 |  The participant elicited the patient’s major concerns within the first 5 minutes of the conversation. | 0.867 | 1.0 | 0.175
q2 |  The participant asked for permission to share information about prognosis. | 0.533 | 0.8 | 0.114
q3 |  The participant asked how much information the patient would like concerning prognosis. | 0.333 | 0.8 | 0.03*
q4 |  The participant checked the patient’s prognostic understanding by asking them to state what they understood, using a teach-back approach. | 0.133 | 0.267 | 0.282
q5 |  The participant actively encouraged the patient to ask questions using facilitating questions/statements (e.g., What questions do you have? At this point many patients have questions etc.). | 0.333 | 0.6 | 0.078
q6 |  The participant helped the SP make a plan regarding with whom, and when, to convey prognostic information to family members. | 0.2 | 0.467 | 0.123
q7 |  The participant gave the SP many opportunities to talk. | 0.467 | 0.867 | 0.024*
q8 |  Empower Rating | 5.267 | 6.133 | 0.003*
q9 |  The participant described the medical situation (the cancer has spread) clearly and without euphemism or jargon. | 0.8 | 0.8 | 0.488
q10 |  The participant shared the prognosis accurately (a few months - less than one year). | 0.6 | 0.667 | 0.476
q11 |  The participant used clear language without euphemism or jargon when sharing the prognosis. | 0.533 | 0.667 | 0.252
q12 |  The participant used difficult to understand medical jargon. | -0.733 | -0.933 | 0.079
q13 |  The participant lectured the patient (uninterrupted information for what seemed like a long time). | -0.533 | -0.8 | 0.067
q14 |  be Explicit rating | 5.667 | 6.067 | 0.084
q15 |  The participant was generally empathetic. | 0.667 | 1.0 | 0.04*
q16 |  The participant used states of empathy. | 0.467 | 0.667 | 0.205
q17 |  The participant used silence appropriately in response to patient emotion. | 0.333 | 0.667 | 0.051
q18 |  The participant validated the SP emotional responses. | 0.533 | 0.867 | 0.027*
q19 |  Empathize Rating | 5.533 | 6.0 | 0.102
q20 |  Overall Communicator | 5.067 | 6.0 | 0.003*
– |  Total | 29.6 | 36.067 | 0.005*

We used four SPs for the experiment. Each SP had an equal number of
intervention and control participants ($\pm 1$). A Bonferroni corrected
pairwise t-test showed no significant differences between ratings given by the
different SPs.

We found that the intervention group performed significantly better on the
“overall communicator” (intervention: 6.000, control: 5.067, $p<0.05$) and
“aggregate score” (intervention: 36.067, control: 29.600 $p<0.05$) metrics.
For every other question, there was a trend towards the intervention group,
but the difference was not always statistically significant. See Table I for
the full results.

###  III-B UI/UX Surveys

Participants in the intervention group rated each feedback metric shown in
figure 1 on a 1-5 Likert scale and the results can be seen in table II.
Overall, we found that the most useful feedback metrics were the reading
level, speaking rate, hedge words, transcript and turn-taking. The least
useful metrics were positive emotion, empathy words and personal pronouns. It
is important to note that user’s ratings of the feedback metrics may not
equate to what they actually learned. For example, participants rated the
empathy metrics relatively low, yet still performed significantly better on 2
of the 5 empathy ratings according to the Human SP evaluation.

Additionally, participants rated four components of the SOPHIE system; System
Usability, Virtual Human, Dialogue, and Feedback. Every question was likewise
asked on a 1-5 point Likert scale with 5 meaning most strongly agree. Fig. 5
depicts the UX experience for system usability, virtual human and dialogue.
Overall, participants rated the system as easy to use with the virtual human
having a realistic voice and appearance. However, the dialogue appears to be a
major point of weakness in the experiment. Its responses were not rated as
natural, logical, or realistic, and it did not appear to understand the user.
Importantly, though, SOPHIE kept the conversation relevant, despite the
variety of ways in which users could respond. SOPHIE’s ability to display
emotion received mixed ratings.

Despite these limitations, debriefing interviews with participants in the
intervention group indicated that participants saw overall utility in our
system, and participants expressed an interest in using the tool if
improvements to the dialogue and virtual human allowed the interaction to be
more realistic.

Figure 5: UX survey responses -  System Usability: The system appears easy to
use, however, participants would not use system frequently. Virtual Human:
SOPHIE looked realistic, is capable of showing emotion through voice, yet
lacks ability to express emotions through facial expression. Dialogue:
SOPHIE’s responses were relevant to her medical condition. However, she did
not appear to understand the user and her responses were judged as not fluent
or natural, illogical, and unlike a real patient.

##  IV Discussion

###  IV-A Improving Communication Skills

Human communication is pragmatic, with patterns developing over time to become
habitual and difficult to change [37]. We speculate that the extent to which
an individual’s communication behaviors can be modified is dependent on how
well a person’s subjective experience and recollection can be meaningfully
connected to clearly-presented and actionable feedback. Based on our
experiment, we see that the combination of interacting with SOPHIE and
receiving automated feedback improved participant’s use of the Empower and
Empathize skills and their overall communication. To what extent this increase
was the result of simply interacting with SOPHIE versus receiving feedback on
the interaction cannot be established based on this experiment, as we didn’t
have a population which had the conversation but not the feedback. However,
one indicator of the importance of feedback may be that the users rated the
feedback system more highly than the dialogue and virtual human. We suspect
that the feedback system is a major contributor to the differences observed.
For example, a user, upon reviewing the transcript of their most recent
conversation with SOPHIE and observing that they only asked three questions,
may realize that they can better empower the patient by asking more questions.
Similarly, as the user is reviewing the transcript, they become aware of
empathetic statements they could have used. This knowledge seems to inform
subsequent conversations based on the ratings from the human SPs (see q3 -
asking questions - and q15 - empathetic statements - in table I). This
suggests that the system’s feedback could result in an actionable plan for
improvement. Further experiments with SOPHIE will be needed to confirm these
intuitions about the efficacy of the feedback system.

Although we did see differences in the being Explicit skill, they were not
statistically significant. This may change as we run future experiments with
larger sample sizes. Additionally, we are planning further improvements to the
SOPHIE system based on our UI/UX feedback from study participants (see section
IV-C). Ultimately, we believe the consistency of the virtual human, dialogue
and feedback system would allow a healthcare professional to hone a variety of
communication skills through repeated practice.

###  IV-B Promoting Equity and Access

The SOPHIE communication resources can be made accessible to anybody with a
computer, microphone and internet connection. The accessibility of the system
is highlighted by the fact that users rated SOPHIE as easy to use, and in
particular disagreed with the statement “I needed to learn a lot of things
before I could get going with this system.” The scalable, web-based nature of
SOPHIE makes it a low-cost alternative to synchronous training with human SPs,
and could make communication training more readily available to rural or low-
income regions. This would promote equity by making communication training
available to more healthcare professionals regardless of the financial
resources available to them.

Specific aspects of SOPHIE could also be customized to reflect a diverse range
of patients. Attributes like SOPHIE’s age, race, gender, language, and
personality could be modified to represent all demographics of patient
populations. Additionally, the context of the module could be readily changed.
In the future, users could choose from dozens of healthcare modules focusing
on specific types of conversations with customized virtual humans uniquely
suited for the purpose. Different types of patient personalities could be
programmed to help practice responding to different reactions and attitudes
from diverse patients.

TABLE II: User ratings for feedback metrics -  All metrics were rated using a 1-5 Likert scale for the statement “I found the $<$metric$>$ feedback useful.” The most useful metrics were reading level, speaking rate, and hedge words. The least useful metrics were positive emotion, empathy words and personal pronouns. Feedback Component | Average rating
---|---
Questions Asked | 3.385
Open Ended Questions | 3.538
Turn taking | 3.846
“Empower” metrics total | 3.590
Personal Pronouns | 3.231
Empathy Words | 3.077
Positive Emotion | 2.769
“Empathize” metrics total | 3.026
Hedge Words | 3.846
Speaking Rate | 4.000
Reading Level | 4.231
“be Explicit” metrics total | 4.026
Transcript | 3.846
Suggestions in Transcript | 3.538

###  IV-C Future of SOPHIE

Despite efforts to improve communication skills, a clinician may fall back
into their old habits unconsciously. Thus, there is a need to consistently
practice these difficult conversations for maintaining, or, even enhancing, a
medical professional’s skill proficiency. Future generations of SOPHIE aim to
satisfy this need by improving upon the system weaknesses discovered from the
UI/UX responses: namely, the dialogue management as well as the emotional
expressiveness of the SOPHIE virtual human. Additionally, we plan to iterate
further with medical professionals to perfect the feedback system (especially
in regards to feedback elements that received low scores).

The feedback system may be extended to other applications in the future as
well. For example, clinicians could have an application on their phones that
could be used during real patient encounters. With the patient’s consent, a
clinician could use the app to analyze the conversation. The app could
generate a checklist that the clinician could quickly review to determine if
they need to spend more time addressing a specific area with their patient.
The data could even be tracked over time to help the clinician monitor their
performance and obtain user-led, personalized insights. For example, the
clinician could view the system’s recommended SOPHIE modules to refresh or
improve certain communication skills. What the clinician decides to do based
on this feedback is entirely their own and the design focus should always be
to empower the clinician.

###  IV-D Limitations

The limitations for this study are our small sample size, lack of clarity of
which factors of the SOPHIE system caused the improvements and a lack of
formal validation for the rating scales used. We elaborate on these
limitations in our ethical statement which can be found after the conclusion.

###  IV-E Contributing to SOPHIE

Regretfully, the SOPHIE code base is not open-source. The SOPHIE project is an
ongoing venture between the University of Rochester Computer Science (URCS)
Department and the University of Rochester Medical Center (URMC). Once
deployed, the research staff may release a starter kit for researchers who
wish to run similar experiments. However, we are actively recruiting
participants for clinical trials and seeking additional collaborations from
other medical schools. If interested, please email Kurtis Haut at
<EMAIL_ADDRESS>
##  V Conclusion

We developed and validated a new digital tool for improving serious illness
communication training for health care professionals. We observed
significantly better performance on overall communication and higher aggregate
scores as a result of interacting with SOPHIE. This study suggests the
potential for practicing conversations with a virtual human and an automated
feedback system to improve communication skills in a scalable, on-demand
fashion. By improving access to communication training, SOPHIE could improve
the equity of our local institutions, and perhaps even the global healthcare
system.

##  VI Ethical Impact Statement

The impacts of this system will be felt by real patients, whose experiences of
receiving tragic news will be shaped by the behaviors their clinicians
developed during their communication training. Given the effect that
communication has on patient healthcare outcomes (see section I), the ethical
considerations of this work must be taken seriously. We have an obligation to
ensure the efficacy of the SOPHIE system and mitigate any potential harms it
could cause. Thus, the virtual patient dialogue and the automated feedback
must be based on the highest standard of established medical practices.
Otherwise, learned communication deficiencies could cause patient prognosis
misunderstandings, leading to healthcare choices that are unaligned with
patient values. To mitigate this risk, the development of SOPHIE has been
heavily shaped through several design iterations with expert oncologists,
palliative care specialists and other stakeholders. We plan to conduct further
experiments to validate and continually refine each subsequent generation of
SOPHIE before deploying the final version. We believe that continuous system
evaluations that appropriately keep pace with development will help maintain
high ethical standards.

Careful ethical considerations must also be made in experimental design for
the validation process and ensure participant confidentiality. In our
experiment, all participants provided informed, written consent before
beginning the study. The methods were performed in accordance with relevant
guidelines and regulations that were approved by our university’s
Institutional Review Board. All data collected has been de-identified such
that it can not be traced to a specific participant.

One limitation of our study is the small, relatively homogeneous sample size
consisting of predominantly white healthcare professionals from our local area
which reduces the generalizability of our results. Future experiments will aim
to recruit a larger, more demographically diverse sample to ensure that the
needs of all users are met.

Additionally, the rendering of the virtual human is a potential source of
bias. We are depicting a white, elderly, female with terminal lung cancer and
set personality. This could pose an ethical issue because real patients are
demographically diverse and come from a variety of backgrounds. It may be the
case that communication skills learned from interacting with SOPHIE do not
translate perfectly when communicating with patients who do not match SOPHIE’s
race, gender, age or personality. Making these features more customizeable
will be a focus of future iterations of the system. This would help healthcare
professionals prepare to communicate equally well regardless of their
patient’s demographic traits, background or personality.

##  VII Data Availability

De-identified results from the experiment are available upon request.

## References

  * [1] R. Hagerty, P. N. Butow, P. Ellis, S. Dimitry, and M. Tattersall, “Communicating prognosis in cancer care: a systematic review of the literature,” _Annals of oncology_ , vol. 16, no. 7, pp. 1005–1053, 2005\.
  * [2] B. M. Korsch and V. F. Negrete, “Doctor-patient communication,” _Scientific American_ , vol. 227, no. 2, pp. 66–75, 1972.
  * [3] J. F. Ha and N. Longnecker, “Doctor-patient communication: a review,” _Ochsner Journal_ , vol. 10, no. 1, pp. 38–43, 2010.
  * [4] D. Riedl and G. Schüßler, “The influence of doctor-patient communication on health outcomes: a systematic review,” _Zeitschrift für Psychosomatische Medizin und Psychotherapie_ , vol. 63, no. 2, pp. 131–150, 2017.
  * [5] M. A. Stewart, “Effective physician-patient communication and health outcomes: a review.” _CMAJ: Canadian medical association journal_ , vol. 152, no. 9, p. 1423, 1995.
  * [6] T. Begum, “Doctor patient communication: a review,” _Journal of Bangladesh College of Physicians and Surgeons_ , vol. 32, no. 2, pp. 84–88, 2014\.
  * [7] D. H. Arnold, C. J. Lonigan, G. J. Whitehurst, and J. N. Epstein, “Accelerating language development through picture book reading: replication and extension to a videotape training format.” _Journal of educational psychology_ , vol. 86, no. 2, p. 235, 1994.
  * [8] K. Ijaz, A. Bogdanovych, and T. Trescak, “Virtual worlds vs books and videos in history education,” _Interactive Learning Environments_ , vol. 25, no. 7, pp. 904–929, 2017.
  * [9] K. Fiscella, P. Franks, M. Srinivasan, R. L. Kravitz, and R. Epstein, “Ratings of physician communication by real and standardized patients,” _The Annals of Family Medicine_ , vol. 5, no. 2, pp. 151–158, 2007.
  * [10] A. Teherani, K. E. Hauer, and P. O’Sullivan, “Can simulations measure empathy? considerations on how to assess behavioral empathy via simulations,” _Patient education and counseling_ , vol. 71, no. 2, pp. 148–152, 2008.
  * [11] T. Carroll, C. Mooney, and R. Horowitz, “Re-act: remote advanced communication training in a time of crisis,” _Journal of pain and symptom management_ , vol. 61, no. 2, pp. 364–368, 2021.
  * [12] R. K. Horowitz, L. A. Hogan, and T. Carroll, “Mvp–medical situation, values, and plan: A memorable and useful model for all serious illness conversations,” _Journal of pain and symptom management_ , vol. 60, no. 5, pp. 1059–1065, 2020.
  * [13] K. I. Pollak, M. K. Olsen, H. Yang, N. Prose, I. Jackson, Larry R., S. O. Pinheiro, T. K. Dunbar, and K. S. Johnson, “Effect of a Coaching Intervention to Improve Cardiologist Communication: A Randomized Clinical Trial,” _JAMA Internal Medicine_ , 04 2023. [Online]. Available: https://doi.org/10.1001/jamainternmed.2023.0629
  * [14] M. DiMatteo, “The role of the physician in the emerging health care environment.” _Western Journal of Medicine_ , vol. 168, no. 5, p. 328, 1998\.
  * [15] M. R. Ali, “Online virtual standardized patient for communication skills training,” in _Proceedings of the 24th International Conference on Intelligent user Interfaces: Companion_ , 2019, pp. 155–156.
  * [16] D. A. Cook, P. J. Erwin, and M. M. Triola, “Computerized virtual patients in health professions education: a systematic review and meta-analysis,” _Academic Medicine_ , vol. 85, no. 10, pp. 1589–1602, 2010.
  * [17] A. Kleinsmith, D. Rivera-Gutierrez, G. Finney, J. Cendan, and B. Lok, “Understanding empathy training with virtual patients,” _Computers in human behavior_ , vol. 52, pp. 151–158, 2015.
  * [18] D. Dewhurst, E. Borgstein, M. E. Grant, and M. Begg, “Online virtual patients–a driver for change in medical and healthcare professional education in developing countries?” _Medical teacher_ , vol. 31, no. 8, pp. 721–724, 2009.
  * [19] A. Custer, L. Rein, D. Nguyen, K. Wentworth, and A. Dhamoon, “Development of a real-time physician–patient communication data collection tool,” _BMJ open quality_ , vol. 8, no. 4, p. e000599, 2019.
  * [20] C. Cuffy, N. Hagiwara, S. Vrana, and B. T. McInnes, “Measuring the quality of patient–physician communication,” _Journal of Biomedical Informatics_ , vol. 112, p. 103589, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1532046420302185
  * [21] M. R. Ali, T. Sen, B. Kane, S. Bose, T. Carroll, R. Epstein, L. K. Schubert, and E. Hoque, “Novel computational linguistic measures, dialogue system and the development of sophie: Standardized online patient for healthcare interaction education,” _IEEE Transactions on Affective Computing_ , 2021\.
  * [22] OpenAI, “Gpt-4 technical report,” 2023.
  * [23] S. Bubeck, V. Chandrasekaran, R. Eldan, J. Gehrke, E. Horvitz, E. Kamar, P. Lee, Y. T. Lee, Y. Li, S. Lundberg _et al._ , “Sparks of artificial general intelligence: Early experiments with gpt-4,” _arXiv preprint arXiv:2303.12712_ , 2023.
  * [24] E. M. Bender and A. Koller, “Climbing towards nlu: On meaning, form, and understanding in the age of data,” in _Proceedings of the 58th annual meeting of the association for computational linguistics_ , 2020, pp. 5185–5198.
  * [25] S. Z. Razavi, M. R. Ali, T. H. Smith, L. K. Schubert, and M. E. Hoque, “The lissa virtual human and asd teens: An overview of initial experiments,” in _Intelligent Virtual Agents_ , D. Traum, W. Swartout, P. Khooshabeh, S. Kopp, S. Scherer, and A. Leuski, Eds. Cham: Springer International Publishing, 2016, pp. 460–463.
  * [26] S. Z. Razavi, L. K. Schubert, B. Kane, M. Ali, K. V. Orden, and T. Ma, “Dialogue design and management for multi-session casual conversation with older adults,” _ArXiv_ , vol. abs/1901.06620, 2019.
  * [27] S. Z. Razavi, L. K. Schubert, M. Ali, and M. Hoque, “Managing casual spoken dialogue using flexible schemas , pattern transduction trees , and gist clauses,” 2017.
  * [28] T. Sen, M. R. Ali, M. E. Hoque, R. Epstein, and P. Duberstein, “Modeling doctor-patient communication with affective text analysis,” in _2017 seventh international conference on affective computing and intelligent interaction (ACII)_. IEEE, 2017, pp. 170–177.
  * [29] C. Hutto and E. Gilbert, “Vader: A parsimonious rule-based model for sentiment analysis of social media text,” in _Proceedings of the international AAAI conference on web and social media_ , vol. 8, no. 1, 2014, pp. 216–225.
  * [30] J. Sedoc, S. Buechel, Y. Nachmany, A. Buffone, and L. Ungar, “Learning word ratings for empathy and distress from document-level user responses,” _arXiv preprint arXiv:1912.01079_ , 2019.
  * [31] S. Bird, “Nltk: the natural language toolkit,” in _Proceedings of the COLING/ACL 2006 Interactive Presentation Sessions_ , 2006, pp. 69–72.
  * [32] L. Si and J. Callan, “A statistical model for scientific readability,” in _Proceedings of the tenth international conference on Information and knowledge management_ , 2001, pp. 574–576.
  * [33] J. M. Zill, E. Christalle, E. Müller, M. Härter, J. Dirmaier, and I. Scholl, “Measurement of physician-patient communication—a systematic review,” _PLoS one_ , vol. 9, no. 12, p. e112637, 2014.
  * [34] A. Bangor, P. T. Kortum, and J. T. Miller, “An empirical evaluation of the system usability scale,” _Intl. Journal of Human–Computer Interaction_ , vol. 24, no. 6, pp. 574–594, 2008.
  * [35] J. R. Lewis, “The system usability scale: past, present, and future,” _International Journal of Human–Computer Interaction_ , vol. 34, no. 7, pp. 577–590, 2018.
  * [36] I. E. Allen and C. A. Seaman, “Likert scales and data analyses,” _Quality progress_ , vol. 40, no. 7, pp. 64–65, 2007.
  * [37] P. Watzlawick, J. B. Bavelas, and D. D. Jackson, _Pragmatics of human communication: A study of interactional patterns, pathologies and paradoxes_. WW Norton & Company, 2011\.


# Cycle-to-Cycle Queue Length Estimation from Connected Vehicles with
Filtering on Primary Parameters

Gurcan Comert<EMAIL_ADDRESS>Negash Begashaw  Computer Sc., Phy.,
and Engineering Department, Benedict College, 1600 Harden St., Columbia, SC
USA 29204

###### Abstract

Estimation models from connected vehicles often assume low level parameters
such as arrival rates and market penetration rates as known or estimate them
in real-time. At low market penetration rates, such parameter estimators
produce large errors making estimated queue lengths inefficient for control or
operations applications. In order to improve accuracy of low level parameter
estimations, this study investigates the impact of connected vehicles
information filtering on queue length estimation models. Filters are used as
multilevel real-time estimators. Accuracy is tested against known arrival rate
and market penetration rate scenarios using microsimulations. To understand
the effectiveness for short-term or for dynamic processes, arrival rates, and
market penetration rates are changed every 15 minutes. The results show that
with Kalman and Particle filters, parameter estimators are able to find the
true values within 15 minutes and meet and surpass the accuracy of known
parameter scenarios especially for low market penetration rates. In addition,
using last known estimated queue lengths when no connected vehicle is present
performs better than inputting average estimated values. Moreover, the study
shows that both filtering algorithms are suitable for real-time applications
that require less than $0.1$ second computational time.

###### keywords:

Queue length estimation, Kalman filter, Particle filter, connected vehicles,
market penetration rate.

##  1 Introduction

Queue length estimation (QLE) with sensor technology has been getting more
attention as real-time estimation is becoming feasible. Queue lengths can be
utilized especially in intelligent transportation system operations and
control. In this usage of queue lengths, market penetration levels, coverage
of sensors, and accuracy are crucial points to consider. Given low penetration
levels, researchers aim to improve estimators by filtering (Tiaprasert et al.
(2015); Yin et al. (2018)). Real-time performance and simplicity would
facilitate methods to be used in simpler low cost controllers. Change in low
level parameters is also a concern as known constant parameters would generate
inaccurate estimates and very high or low values for low market penetration
rates (MPR). Researchers have used filtering to reduce error in such cases.
Filtering can be applied in different layers depending on the objective. Since
true queue lengths are not known, assuming relatively short unchanging
parameters would help to improve estimators. The challenges are multimodality
over longer term and underlying unknown distribution for parameters. In this
paper, we utilize Kalman and Sequential Monte Carlo (e.g., bootstrap,
particle) filters to estimate primary parameters more accurately and thereby
improve cycle-to-cycle queue length estimation at traffic intersections within
the framework of connected vehicles (CV).

Readers are referred to the survey papers by Zhao et al. (Zhao et al. (2019a))
and Guo et al.(Guo et al. (2019)) for general queue length estimation from
connected vehicles at traffic intersections, and Asanjaranti et al.
(Asanjarani et al. (2017)) for queue length estimation. Recent similar studies
include methods reconstructing trajectories (Xu et al. (2017); Rompis et al.
(2018); Zhao et al. (2019b)), cycle-to-cycle estimations (Tan et al. (2019)),
and real-time applications with high market penetration rates (Mei et al.
(2019)). Based on shockwaves and queue dynamics, Yin et al. showed
effectiveness of Kalman filter in QLE, especially within $20\%$ MPR (Yin et
al. (2018)). Discrete Fourier transform based filtering was applied by
Tiaprasert et al. (2015) on queue length estimation but not on primary
parameters. Any overestimation and underestimation on primary parameters would
be passed to QLE accuracy. Queue sizes, especially medium to high volume-to-
capacity ratios can fluctuate significantly. Filtering estimation QLs would
result as low or high trimmed values. Thus, knowing relatively fixed
parameters at a level can be better target to filter.

Stochastic models of QLEs from CVs mainly concerns with stationary (behavior
after sufficiently long time interval) or non-stationary (short-time
intervals, by cycle, and red phase). Such classification is impacted by
treatment of arrival rate, distribution, and market penetration rate (MPR)
(probe percentage). For instance, Yang and Menendez showed that 20% to 30% MPR
is required to control signals (Yang and Menendez (2018)). Although $20$ to
$30\%$ MPR is shown to be required to control signals (Yang and Menendez
(2018)), in another study Argoteet al. showed different accuracy levels, $\pm
10\%$ with $80\%$ MPR (Argote et al. (2011)). Using sensor fusion with the
existing deployed traffic sensing technology (e.g., inductive loops, license
plate recognition) was also investigated by the researchers (Wu and Yang
(2013); Li et al. (2013); Comert (2013); Tan et al. (2020); Mandal et al.
(2020)).

Even though, higher penetration levels are expected, efficient estimators
performing at low MPRs would be desirable as better data management will be
required. The question of how much data one needs is important not to overload
systems for safety and security reasons. Partially supporting these, in an
interesting report (University of Arizona (2016)), researchers have found in a
simulation environment that over 200 vehicles at $100\%$ penetration level
signal control from CVs becomes difficult due to computational overhead. Rural
roads and isolated intersections would also have lower MPRs. Regardless,
increasing QLEs and filtering inconsistent extreme over and under estimations
are very important for traffic operations and any partially observed systems.

###  1.1 Contributions of this study

Simple expectation-based QLE models and estimators with known characteristics
in Comert (2016) enable application of filtering algorithms to deal with
measurement of low MPR related errors. The estimation problem where we only
assume partially observed system becomes interesting. This approach can be
adopted for any similar problem like autonomous vehicles. Studies in
estimation of primary parameters using only fundamental CV information (i.e.,
time, location, speed, and vehicle type etc.) are getting more attention
(Comert (2016); Van Phu and Farhi (2018); Zhao et al. (2019a)). But, there are
limitations for connected vehicles with low MPRs. In this study, we aim to
improve accuracy at low MPRs by improving the low level parameter estimators
using filtering algorithms. The resulting formulae would not depend on any
primary parameters such as arrival rate or MPR. So, the method can be used for
time dependent arrival rates or MPR or under dynamic conditions.

##  2 Problem Definition

Estimation of queue lengths is one of the inherent key capabilities of
connected and autonomous vehicles for operations control. In this study, we
aim to estimate the queue lengths at traffic intersections without knowing the
true low level parameters as well as true queue lengths. CVs can share
location and time information with a time reference point (e.g., signal
timing, red duration), number of queued vehicles is aimed.

Fig. 1: An example intersection with multiple approaches generated in Vissim

Considering Fig. 1 as an example layout, for any approach right before the
signal turns green, we aim to estimate the queue length. For instance,
consider left turn on east-west bound approach. Assuming that the blue or
darker cars are connected vehicles, we try to find total queue length of $N=7$
given last connected vehicle’s location $L=6$, number of connected vehicles
$M=2$, and arrival time during red $T=10$ seconds $s$ with remaining $R-T$
$s$.

Mathematically, the estimator $E(N_{i}|L=l_{i},T=t_{i},M=m_{i},R)$ for short
target $i$ time intervals is aimed to be described. In the estimator, $N_{i}$
is cycle-to-cycle total queue lengths at the end of analysis period, $L_{i}$
location of the last CV, $T_{i}$ is queue joining time of the CV, and $M_{i}$
is number of CVs in the queue. Using models in the literature, for Poisson
arrivals, simple $l_{i}+(1-p)\lambda(R-t_{i})$ are shown to be an unbiased
estimators. Certainly, arrival rate $\lambda$ and market penetration rate $p$
are equally difficult to determine in practice. So, several estimators for
$\lambda$ and $p$ are also given in Comert (2016). However, for low market
penetration levels less than $30\%$, estimators tend to perform with high
variance. Thus, it is intuitive to utilize filters similar to localization
idea in robotics. The difference in this problem is that there are no
landmarks assumed to correct measurements. It is advantageous to assume
constant market penetration and arrival rate for relatively short terms, e.g.,
$15$ to $30$ minutes. This assumption would allow us to locate true values
from unimodal distributions. It can be relaxed using desirably nonparametric
filtering techniques that would allow multimodal distributions. The nature of
the problem can be summarized as follows:

  * 1.

Queue lengths show nonlinear behavior with unknown distribution type.

  * 2.

The underlying process model is also very complex depending on arrival rate,
changing signal timing, day of time, and roadway geometry etc.

Alternative to such conditions can be listed as discrete Bayes filters and
particle filters. Since we are working with constant parameters within short
time intervals such as $15$ minutes, we aim to filter parameters for unimodal
distribution case. If we are able to get $[\hat{p},\hat{\lambda}]$ values as
correctly as possible, then we would be able to estimate QLs more correctly
and do not violate the constant parameter within short intervals. In the
figures presented in section 4, estimated parameters are given in incremental
time interval.

##  3 Methodology

In this study filters are mainly used to estimate primary parameters, arrival
rate ($\lambda$) and market penetration level ($p$). The impact of filtering
on the lowest level CV time, location, and count information was also checked.
Parameter filters would perform better under given consistent behavior of
noise levels and described underlying dynamics such as object movement. In
this case, no assumption was made for underlying distribution especially for
particle filter as it is considered a distribution-free multimodal method.
Whereas, KF assumes Gaussian and unimodal underlying process distribution. For
both methods, queue length estimation scenarios would be appropriate since
unimodal/constant higher level arrival rate and market penetration rates are
assumed within 15-minute time intervals.

In order to set up the application, first consider the estimators in general
form of $E(N=n|L=l,T=t,M=m)$=$l+(1-p)\lambda(R-t)$. The problem with this
estimator is lack of accuracy on $\hat{p}$ and $\hat{\lambda}$, especially at
low $p$ ($p\leq 0.30$). We aim to filter and find out true parameter values
given short-time intervals i.e., 15 minutes. Estimator combinations that best
performed in QLE (Comert (2016)) were

$\displaystyle\hat{p}$ $\displaystyle=$
$\displaystyle\left\\{\left(1-\frac{m_{i}t_{i}}{m_{i}t_{i}+(l_{i}-m_{i})R}\right),\frac{m_{i}}{l_{i}}\right\\}$
$\displaystyle\hat{\lambda}$ $\displaystyle=$
$\displaystyle\left\\{\left(\frac{l_{i}-m_{i}}{t_{i}}+\frac{m_{i}}{R}\right),\frac{l_{i}}{t_{i}}\right\\}$

Thus, queue length estimators are used in Eqs. (4) and (5) for comparison of
simple estimator in Eq. (3) with $\hat{p}=\frac{m_{i}}{(l_{i}/t_{i})R}$ and
$\hat{\lambda}=l_{i}/t_{i}$. Note that this estimator simplifies to
$\frac{Rl_{i}}{t_{i}}-m_{i}(R-t_{i})=R\hat{\lambda}-m_{i}(R-t_{i})$.

$\displaystyle
E(\hat{N_{i}}|l_{i},t_{i},m_{i},q_{i})=\left\\{\begin{array}[]{ll}l_{i}+\left(1-\frac{m_{i}t_{i}}{l_{i}R}\right)\left(\frac{{}_{i}}{t_{i}}\right)(R-t_{i}),&l_{i}>0\\\
E(\hat{N_{j}}|l_{j},t_{j},m_{j},q_{j})\neq
0,&j=1,\cdots,(i-1),l_{i}=0\end{array}\right.$ (3) $\displaystyle
E(\hat{N_{i}}|l_{i},t_{i},m_{i},q_{i})$ $\displaystyle=$ $\displaystyle
l+\left(1-\frac{m_{i}}{l_{i}}\right)\left(\frac{l_{i}}{t_{i}}\right)(R-t)$ (4)
$\displaystyle=$ $\displaystyle
l_{i}+\left(\frac{l_{i}-m_{i}}{t_{i}}\right)(R-t_{i})$

$\displaystyle E(\hat{N_{i}}|l_{i},t_{i},m_{i},q_{i})$ $\displaystyle=$
$\displaystyle
l+\left(1-\frac{m_{i}t_{i}}{m_{i}t_{i}+(l_{i}-m_{i})R}\right)\left(\frac{l_{i}-m_{i}}{t_{i}}+\frac{m_{i}}{R}\right)(R-t_{i})$
(5) $\displaystyle=$ $\displaystyle m_{i}+\frac{R(l_{i}-m_{i})}{t_{i}}$

###  3.1 Kalman Filter

In its simplest form, Kalman filter (KF) assumes underlying Gaussian
measurements or noise (Labbe (2014)). KF also performs well if a physical
system is modeled adequately (e.g., vehicle moving dynamics). In the QLE
problem, both are not true. We may have different parameter values and no
closed-form formulas are available for dynamics of parameters (i.e., $p$,
$\lambda$) given connected vehicle information. However, it is possible to
demonstrate the problem better and can easily be implemented. After careful
experimentation, observed CV information within $\hat{\lambda}$ as
$X_{i}=\min\\{(\frac{L_{i}-M_{i}}{T_{i}}+\frac{M_{i}}{R}),0.272\\}$ and
$XC_{i}=\min\\{\frac{XL_{i}}{XT_{i}},0.280\\}$ was filtered for all
${\lambda,p}$. Similarly, market penetration rate ($\hat{p}$) was estimated
and filtered using
$X_{i}=\min\left\\{\left(1-\frac{M_{i}T_{i}}{M_{i}T_{i}+(L_{i}-M_{i})R}\right),1.00\right\\}$
and $XC_{i}=\min\\{\frac{XM_{i}}{XL_{i}},1.00\\}$.

Algorithm 1 Kalman Filter

assign:

$\hat{X_{i}}=\mu_{i}$

$S_{X_{i}}=S_{X_{i-1}}$

update:

$K_{X_{i}}=S_{X_{i}}/(S_{X_{i}}+s)$

$Y_{X_{i}}=X_{i}-\hat{X_{i}}$

$\mu_{i+1}=\mu_{i}+K_{X}Y_{X}$

$S_{X_{i+1}}=(1-K_{X_{i}})S_{X_{i}}$

In the algorithm, $S_{X_{i}}$ is the system uncertainty, $s$ is sensor
uncertainty, $K_{X_{i}}$ is the Kalman gain in cycle $i$, $X_{i}$ observation
in cycle $i$, $Y_{X_{i}}$ estimation error, and $\mu_{i+1}$ is the state
update using Kalman gain and estimation errors.

###  3.2 Particle Filters

Sequential Monte Carlo (SMC) framework contains many similar filters such as
particle, bootstrap, and sequential importance filters with slight changes in
the resampling (i.e., update) methods (Liu and Chen (1998); Gustafsson et al.
(2002); Doucet and Johansen (2009); Carvalho et al. (2010); Lopes and Tsay
(2011); Bernardo et al. (2011)). QLE setting has [$p$,$\lambda$] with
corresponding weights each showing how likely they represent true $\hat{p}$
and $\hat{\lambda}$ values. Unlike usual robotics localization problem
landmarks, sensing, or true (or noisy) parameter values are not available in
QLE application for low MPRs. Thus, after each movement, convergence to true
parameters (importance resampling) is more challenging. Heuristic SMC
filtering steps can be written within parameter estimation concepts as
follows:

  * 1.

Observe new information from the cycle as triplets [$M$,$L$,$T$] and estimate
with [$\hat{\lambda}$, $\hat{p}$].

  * 2.

Update the weights of the particles based on the new estimates from the
updated observations.

  * 3.

Based on the triplet received and new estimation of parameters, resample with
replacement to eliminate particles that are highly unlikely. Particles close
to the estimates get higher weights.

  * 4.

Estimate weighted mean and variance of the filtered $\hat{p}$,
$\hat{\lambda}$.

Algorithm 2 is adopted from Lopes (2009). Initial weights are input as
uniform, observations are denoted by $X_{i+1}\sim p(X_{i+1}|Z_{i+1},\lambda)$,
and transitions are denoted by $X_{i+1}\sim p(X_{i+1}|X_{i},\lambda)$.
Posterior distributions with $p(Z_{i},\lambda|X^{i})$ with
$X^{i}=(X_{1},...,X_{i})$. Since, we do not have movement for particles, a
particle filter (Bootstrap filter) with a simpler resampling wheel can be
written as propagate: $\\{{Z^{(j)}_{i}}\\}_{j=1}^{N}$ to
$\\{{\tilde{Z}^{(j)}_{i+1}}\\}_{j=1}^{N}$ via $p(Z_{i+1}|Z^{i})$, generate:
$\\{{Z^{(j)}_{i+1}}\\}_{j=1}^{N}$ to $\\{{\tilde{Z}^{(j)}_{i+1}}\\}_{j=1}^{N}$
via $p(Z_{i+1}|Z^{i})$, and resample with weights: ${{w}^{(j)}_{i+1}}\propto
p(X_{i+1}|{\tilde{Z}^{(j)}_{i+1}})$. In fact, without approximately defined
dynamics of particles, full version of particle filter performed very similar
with higher computational run time.

Algorithm 2 Particle Filter

N particles: $X\sim{\mathcal{N}}(0.0,0.05)$, $\hat{X}_{cycles\times n}$

for $cycle$ $i$ do

particle jittering: $X^{\prime}=X+\epsilon$

$w=f(X_{i},X^{\prime}/(1+{X^{\prime}}^{2},1.00))$

sample: $n$ $from:$ $X^{\prime}$ $with$ $p(w)$

end for

$X=X^{\prime}$, $\hat{X}_{i,1:n}=X$, median($\hat{X}$)

In algorithm 2, numerical values are selected after trial and errors on one
series (e.g., $\rho=0.88$ and $p=0.10$). Low jittering noise was selected to
prevent low resampling or fast bad convergence
$\epsilon={\mathcal{N}}(0.0,0.0005)$

##  4 Numerical Results

Numerical examples are given to show performance of the filtering approach.
Analysis include discussions for both filters and queue length estimation from
connected vehicles for fixed and varying primary parameters. Simulated
intersection queue data are used in the examples. An isolated signal with
fixed signal control in Vissim is used to test the estimators with filtered
vehicle information after revising the network generated in Comert (2016) and
default queue vehicle in Vissim is used (Liu et al. (2019)). Simple
intersection is used only for generating queueing data. As mentioned earlier
estimators can be adopted for approaches with a standing queue.

Fig. 2: Parameter estimation example with filters at $p\%$, $\rho=0.99$ as
average of 3 random seeds

Note that given required information, estimators can be used under any
condition and signal control. Queue lengths that we observe show an
autocorrelated times series as dynamic stochastic process. Thus, if estimators
perform well here, they can be used under any conditions as only fundamental
vehicle information location, time, count, and time period of estimation
(e.g., signal timing such as red, green duration) was assumed to be known.

Fig. 3: Estimation examples for $p$ with filters at $p={0.05,0.10,0.20,0.30}$,
$\rho={0.70,0.80,0.89,0.99}$ as average of 3 random seeds Fig. 4: $\lambda$
estimation examples with filters at $p={0.05,0.10,0.20,0.30}$,
$\rho={0.70,0.80,0.89,0.99}$ as average of 3 random seeds

Vehicle trace files generated from microsimulations are used to evaluate queue
length estimation without and with initial queue cases for arrival rates of
$\lambda=\\{0.163,0.190,0.218,0.239,0.267\\}$ vehicle per second ($vps$) that
correspond to volume-to-capacity ratios of
$\rho=\\{0.60,0.70,0.80,0.89,0.99\\}$ and
$p=\\{0.001,0.05,0.10,0.20,...,0.90\\}$ for the desired simple intersection
with $90$ seconds ($s$) cycle length equal $45$ $s$ red/green split. Note that
our approach is QLE given partial information about the system and can be
applied for any approach with a standing queue at a certain time period (e.g.,
red duration).

###  4.1 Fixed parameters

Cycle-to-cycle updated parameter estimators using filtering that do not
involve cumulative connected vehicles information are given in Figs. 2-8. In
order to check the impact in lowest level information (i.e., applied on
$L$,$T$,and $M$), estimator values with raw CV are denoted by $CVR$ and the
values with filtered CV information are denoted by $CVF$.

Impact is more seen in $\hat{p}$. However, resulting QLEs are not much
impacted when using raw or filtered CV values.

From Fig. 2, it can be seen that highly dispersed ratios are filtered to point
desired parameter level. However, we are not able to obtain true parameters
for $p<0.20$. At MPR $p=0.20$, parameter estimators are improved and with
filtering, we are able to track the underlying true parameter values $p$ and
$\lambda$ very closely.

Fig. 5: Performance with filters for different $p$, $\lambda$, and $\rho$

Estimator performances for $\hat{\lambda}$ for different $p$ levels and
$\hat{p}$ for different $\lambda$ levels are given in Figs. 3 and 4,
respectively. In Fig. 4, KF is able to get closer to true values at low
volume-to-capacity ratio $\rho=0.70$ and $p=0.10$. In all cases, as $p$ gets
higher, estimator performs better. Similarly, in Fig. 3, it can be seen that
estimation with filters perform well for all $\lambda$ and $p$ values. Both KF
and PF show similar behavior.

Fig. 6: Impact of filters in estimation $\%\Delta\sqrt{V}(D)/E(N)$ for
different $p$, $\lambda$, and $\rho$ average of 3 random seeds Fig. 7:
Estimation example with filters at $p=5\%$, $\rho=0.99$ as average of 3 random
seeds Fig. 8: Scenarios with changing $p$, $\lambda$, and resulting estimation
errors in $\sqrt{V(D)}$ [vehs]

In Fig. 5, estimation errors with and without filtering are presented.
Filtering improves the estimation errors compared to unknown primary
estimators (denoted by QLE1 and QLE2). With filtering, at $20\%$ market
penetration level, errors with known primary parameters can be met. As volume-
to-capacity ratio increases, filtering is able to meet and improve the queue
length estimation compared to known case.

Fig. 9: Queue length estimation examples

The differences in the form of $\%\Delta\sqrt{V}(D)/E(N)$ from QLE with known
($p$, $\lambda$) errors can be seen in Figs. 6a-d. In all $\rho$ values up to
$40\%$ MPR, QLE with filtering shows improved errors, i.e., lower than QLE1
and QLE2. This is desirable as accuracy improvement is needed at low MPR
values. Only for $rho=0.70$, after $50\%$ MPR filtering shows worse errors.
However, these errors are already very low (less than 1 vehicle in Fig. 5).
QLE with filtering shows better performance than QLE with known ($p$,
$\lambda$) up to $40\%$ in $\rho=0.99$.

Fig. 10: Parameter estimation example with filters at $p\%$, $\rho=0.99$ as
average of 3 random seeds

Example of queue length estimation is shown in Fig. 7 for $p=5\%$ and
$\rho=0.99$. Filtered estimators are able to closely follow true QLs. Extreme
reactions due to misrepresenting CAVs information are filtered.

All the examples so far have been on single parameter for relatively long
time. Estimators are able to perform well in $50$ cycles or $1.25$ hours.
Next, we consider changing parameter cases and performance of estimation with
filters.

###  4.2 Dynamic parameters

In this subsection, estimators’ performance are shown when parameters change
for shorter time intervals. Since the physics of queue evolution is not
defined in closed form for KF, it is expected that PF performs better for
multi-regime parameters as shown in Fig. 8a-b. These scenarios are arbitrarily
generated by increasing and decreasing with a peak to mimic changing traffic
conditions. Setting up full factor experiments is beyond the scope of this
paper.

Overall average estimation errors from these scenarios are also given in Fig.
8c. From the figure, we can deduce that PF performs slightly better than KF in
all scenarios. Estimation with filtering outperforms unknown parameter cases
and closely follows the estimation errors of known ($p$, $\lambda$) QLE.

Example queue length estimations are given in Fig. 9 for 4 scenarios where
overall we can see filtering helps to more closely follow true queue lengths.
Behavior of KF and PF on changing parameter estimations are shown in Fig. 10.
PF is expected to perform better under dynamic $p$ and $\lambda$ behaviors. It
is also observed that for low $p$ values, using last estimated queue length
performs much better than using average values until then. This is due to
volatile behavior of queue lengths instead of a level we are able to catch
high and low points better with last known point missing data amputation.

For computational times, for a single scenario for $1000$ cycles running KF
for $\lambda$ and $p$ estimations on a PC with 8GB of memory, Pentium I5 Quad-
Core CPU took $0.03$ $s$ and $0.04$ $s$, respectively. For running PF took
$3.50$ $s$ and $3.31$ $s$, respectively. As per cycle calculations are well
below $0.1$ $s$, both filtering algorithms can be utilized in real-time cycle-
to-cycle control and safety critical applications.

##  5 Conclusions

In this study, we investigated the impact of localization framework on queue
length estimation at low market penetration rates. We used two different
filtering methods:

(i)

Kalman filter: unimodal and Gaussian noise

(ii)

Particle filter: multimodal and noise from any distribution

The filters are fitted to queue length estimation framework where no
approximately true feedback is available.

Two cases of fixed arrival and market penetration rate parameters and changing
parameter are analyzed. Queue length estimation with filters show promising
results improving estimation by $20\%$ for high volume-to-capacity ratio of
$\rho=0.99$. For lower $\rho$ levels, with filtering by $30\%$ market
penetration rates, known queue length estimation error are matched.

Both estimation models and filters are simple and enable real-time
applications with no significant overhead. For future research, alternative
queue length estimation models will be included for more realistic arrival and
service time distributions.

## Acknowledgments

This study is partially supported by the Center for Connected Multimodal
Mobility ($C^{2}M^{2}$) (USDOT Tier 1 University Transportation Center)
headquartered at Clemson University, Clemson, South Carolina. Any opinions,
findings, and conclusions or recommendations expressed in this material are
those of the authors and do not necessarily reflect the views of the Center
for Connected Multimodal Mobility ($C^{2}M^{2}$) and the official policy or
position of the USDOT/OST-R, or any State or other entity, and the U.S.
Government assumes no liability for the contents or use thereof. It is also
partially supported by U.S. Department of Homeland Security Summer Research
Team Program Follow-On grant and NSF Grants Nos. 1719501, 1436222, 1954532,
and 1400991.

## References

  * Argote et al. (2011) Argote, J., Christofa, E., Xuan, Y., Skabardonis, A., 2011. Estimation of measures of effectiveness based on connected vehicle data. In: 2011 14th International IEEE Conference on Intelligent Transportation Systems (ITSC). IEEE, pp. 1767–1772.
  * Asanjarani et al. (2017) Asanjarani, A., Nazarathy, Y., Pollett, P. K., 2017. Parameter and state estimation in queues and related stochastic models: A bibliography. arXiv preprint arXiv:1701.08338.
  * Bernardo et al. (2011) Bernardo, J., Bayarri, M., Berger, J., Dawid, A., Heckerman, D., Smith, A., West, M., 2011. Particle learning for sequential bayesian computation. Bayesian Statistics 9 9, 317.
  * Carvalho et al. (2010) Carvalho, C. M., Johannes, M. S., Lopes, H. F., Polson, N. G., et al., 2010. Particle learning and smoothing. Statistical Science 25 (1), 88–106.
  * Comert (2013) Comert, G., 2013. Effect of stop line detection in queue length estimation at traffic signals from probe vehicles data. European Journal of Operational Research 226 (1), 67–76.
  * Comert (2016) Comert, G., 2016. Queue length estimation from probe vehicles at isolated intersections: Estimators for primary parameters. European Journal of Operational Research 252 (2), 502–521.
  * Doucet and Johansen (2009) Doucet, A., Johansen, A. M., 2009. A tutorial on particle filtering and smoothing: Fifteen years later. Handbook of nonlinear filtering 12 (656-704), 3\.
  * Guo et al. (2019) Guo, Q., Li, L., Ban, X. J., 2019. Urban traffic signal control with connected and automated vehicles: A survey. Transportation research part C: emerging technologies.
  * Gustafsson et al. (2002) Gustafsson, F., Gunnarsson, F., Bergman, N., Forssell, U., Jansson, J., Karlsson, R., Nordlund, P.-J., 2002. Particle filters for positioning, navigation, and tracking. IEEE Transactions on signal processing 50 (2), 425–437.
  * Labbe (2014) Labbe, R., 2014. Kalman and bayesian filters in python. Chap 7, 246.
  * Li et al. (2013) Li, J.-Q., Zhou, K., Shladover, S. E., Skabardonis, A., 2013. Estimating queue length under connected vehicle technology: Using probe vehicle, loop detector, and fused data. Transportation research record 2356 (1), 17–22.
  * Liu et al. (2019) Liu, H., Liang, W., Rai, L., Teng, K., Wang, S., 2019. A real-time queue length estimation method based on probe vehicles in cv environment. IEEE Access 7, 20825–20839.
  * Liu and Chen (1998) Liu, J. S., Chen, R., 1998. Sequential monte carlo methods for dynamic systems. Journal of the American statistical association 93 (443), 1032–1044.
  * Lopes (2009) Lopes, H. F., July 2009. Tutorial: An introduction to particle filters. Unpublished Tutorial.
  * Lopes and Tsay (2011) Lopes, H. F., Tsay, R. S., 2011. Particle filters and bayesian inference in financial econometrics. Journal of Forecasting 30 (1), 168–209.
  * Mandal et al. (2020) Mandal, A., Sadhukhan, P., Gaji, F., Sharma, P., 2020. Measuring real-time road traffic queue length: A reliable approach using ultrasonic sensor. In: Proceedings of the 2nd International Conference on Communication, Devices and Computing. Springer, pp. 391–398.
  * Mei et al. (2019) Mei, Y., Gu, W., Chung, E. C., Li, F., Tang, K., 2019. A bayesian approach for estimating vehicle queue lengths at signalized intersections using probe vehicle data. Transportation Research Part C: Emerging Technologies 109, 233–249.
  * Rompis et al. (2018) Rompis, S. Y., Cetin, M., Habtemichael, F., 2018. Probe vehicle lane identification for queue length estimation at intersections. Journal of Intelligent Transportation Systems 22 (1), 10–25.
  * Tan et al. (2020) Tan, C., Liu, L., Wu, H., Cao, Y., Tang, K., 2020. Fuzing license plate recognition data and vehicle trajectory data for lane-based queue length estimation at signalized intersections. Journal of Intelligent Transportation Systems, 1–18.
  * Tan et al. (2019) Tan, C., Yao, J., Tang, K., Sun, J., 2019. Cycle-based queue length estimation for signalized intersections using sparse vehicle trajectory data. IEEE Transactions on Intelligent Transportation Systems.
  * Tiaprasert et al. (2015) Tiaprasert, K., Zhang, Y., Wang, X. B., Zeng, X., 2015. Queue length estimation using connected vehicle technology for adaptive signal control. IEEE Transactions on Intelligent Transportation Systems 16, 2129–2140.
  * University of Arizona (2016) University of Arizona, University of California PATH Program, S. N. I. E., 2016\. Multi-modal intelligent traffic signal system—phase ii: System development, deployment and field test.
  * Van Phu and Farhi (2018) Van Phu, C. N., Farhi, N., 2018. Estimation of urban traffic state with probe vehicles. arXiv preprint arXiv:1811.05394.
  * Wu and Yang (2013) Wu, A., Yang, X., 2013. Real-time queue length estimation of signalized intersections based on rfid data. Procedia-Social and Behavioral Sciences 96, 1477–1484.
  * Xu et al. (2017) Xu, H., Ding, J., Zhang, Y., Hu, J., 2017. Queue length estimation at isolated intersections based on intelligent vehicle infrastructure cooperation systems. In: 2017 IEEE Intelligent Vehicles Symposium (IV). IEEE, pp. 655–660.
  * Yang and Menendez (2018) Yang, K., Menendez, M., 2018. Queue estimation in a connected vehicle environment: A convex approach. IEEE Transactions on Intelligent Transportation Systems 20 (7), 2480–2496.
  * Yin et al. (2018) Yin, J., Sun, J., Tang, K., 2018. A kalman filter-based queue length estimation method with low-penetration mobile sensor data at signalized intersections. Transportation Research Record 2672 (45), 253–264.
  * Zhao et al. (2019a) Zhao, Y., Zheng, J., Wong, W., Wang, X., Meng, Y., Liu, H. X., 2019a. Estimation of queue lengths, probe vehicle penetration rates, and traffic volumes at signalized intersections using probe vehicle trajectories. Transportation Research Record 2673 (11), 660–670.
  * Zhao et al. (2019b) Zhao, Y., Zheng, J., Wong, W., Wang, X., Meng, Y., Liu, H. X., 2019b. Various methods for queue length and traffic volume estimation using probe vehicle trajectories. Transportation Research Part C: Emerging Technologies 107, 70–91.