Agents operating in physical environments need to be able to handle delays in the input and output signals since neither data transmission nor sensing or actuating the environment are instantaneous. Shields are correct-by-construction runtime enforcers that guarantee safe execution by correcting any action that may cause a violation of a formal safety specification. Besides providing safety guarantees, shields should interfere minimally with the agent. Therefore, shields should pick the safe corrective actions in such a way that future interferences are most likely minimized. Current shielding approaches do not consider possible delays in the input signals in their safety analyses. In this paper, we address this issue. We propose synthesis algorithms to compute delay-resilient shields that guarantee safety under worst-case assumptions on the delays of the input signals. We also introduce novel heuristics for deciding between multiple corrective actions, designed to minimize future shield interferences caused by delays. As a further contribution, we present the first integration of shields in a realistic driving simulator. We implemented our delayed shields in the driving simulator Carla. We shield potentially unsafe autonomous driving agents in different safety-critical scenarios and show the effect of delays on the safety analysis.

§ INTRODUCTION

Due to the complexity of nowadays autonomous, AI-based systems, approaches that guarantee safety during runtime are gaining more and more attention [Könighofer et al., 2022].
A maximally-permissive enforcer, often called a shield, overwrites any actions from the agent that may cause a safety violation in the future [Alshiekh et al., 2018].
In order to enforce safety while being maximally permissive,
the shield has to compute the latest point in time where safety can still be enforced.
For that reason, shields are often computed by constructing a safety game from
an environmental model that captures all safety-relevant dynamics and a formal safety specification.
The maximally-permissive winning strategy $\rho$
within any state, all actions that will not cause a safety violation over the infinite time horizon. Given a state, we call an action safe if the action is contained in $\rho$, and an action is called unsafe otherwise.
Shields allow any actions that are safe according to $\rho$.

Incorporating delays in safety computations is necessary for almost any real-world control problem. Delays are caused by data collection, processing, or transmission
and are therefore omnipresent for any agent operating in a complex environment.
Not addressing these delays can be the root of many safety-critical problems.

Delay-resilient shielding scheme.

Let us assume that a car detects a pedestrian at position $(x,y)$,
and it is aware of a time delay $\delta$ between sensing and acting.
The vehicle has to plan its next actions in such a way that they are safe for any position of the pedestrian in the interval $(x\pm \varepsilon, y \pm \varepsilon)$, where $\varepsilon$ is defined via assumptions on the pedestrian's velocity and the delay $\delta$.

In this paper, we propose synthesis algorithms for delay-resilient shields,
i.e. shields that guarantee safety under assumptions on the worst-case delay on the inputs.
Figure <ref> shows the shielding settings under delay.

To synthesize delay-resilient shields, we incorporate a worst-case delay in the safety game, which induces imperfect state information [Chen et al., 2020].
The delay-resilient shields are then computed from the maximally-permissive winning strategy in the delayed safety game.
In order to obtain a fixed replacement action for any unsafe action,
we have to determinize the maximally-permissive strategy.
To do so, we can define a property over the state space
and set the action maximizing such property as the one fixed by the shield.
We study two such properties: controllability and robustness.
The controllability value assigns to any state $s$ the maximal delay on the input under which $s$ stays safe.
The robustness value of a state $s$ is the length of the minimal path from $s$ to any unsafe state.
We discuss how to maximize a state property under the uncertainty introduced by the delayed input.

In our experiments, we integrate shielding under delay in the driving simulator
Carla [Dosovitskiy et al., 2017].
Our results show the effects of delays on the safety analysis and that our method is scalable enough to be applied in complex application domains.
As a second case study, we perform experiments on a gridworld
and compare the performance of delay-resilient shields with different worst-case delay.
The source code to reproduce the experiments,

are available on the accompaning repository[<https://github.com/filipcano/safety-shields-delayed>].

Related work.
Shields for discrete systems were introduced in [Bloem et al., 2015]
and several extensions and applications have already been published [Tappler et al., 2022, Pranger et al., 2021, Jansen et al., 2020], e.g., shielding for reinforcement learning agents [Carr et al., 2022, Könighofer et al., 2021, Elsayed-Aly et al., 2021].
Chen et al. [Chen et al., 2018, Chen et al., 2020] investigated the synthesis problem for time-delay discrete systems by the reduction to solving
two-player safety games.
We base our shields
on their proposed algorithm for solving delayed safety games.
Note that the delayed games discussed in [Winter and Zimmermann, 2020]
follow a different concept.
In their setting, a delay is a lookahead granted by the input player as an advantage to the delayed player: the delayed player P1 lags behind input
player P0 in that P1 has to produce the $i$-th action when
$i+j$ inputs are available.
In contrast,
we do not grant a lookahead into future inputs but consider reduced information due to input data being delivered to the agent with delay, which renders our agent equivalent to their input player.
The notion of delay employed in this paper also is different from that in timed games [Behrmann et al., 2007].
In timed games, delay refers to the possibility of deliberately
delaying the next single action.
However, both players have full and up-to-date information in timed games.
In the continuous and hybrid domains, control barrier functions [Ames et al., 2019] are used to enforce safety.
Prajna et al. extended the notion of barrier certificates to time-delay systems [Prajna and Jadbabaie, 2005].
Bai et al. [Bai et al., 2021] introduced a new model of hybrid
systems, called delay hybrid automata, to capture the continuous dynamics of dynamical
systems with delays.
However, this work does not address the fact that
state observation in embedded systems is de facto in discrete time
and that a continuous-time shielding mechanism therefore would require adequate interpolation between sampling points.

§ PRELIMINARIES - SHIELDING WITHOUT DELAYS

We briefly outline the classical approach for computing shields via safety games.
We refer to [Alshiekh et al., 2018] for more details and formal definitions.
The classical approach to computing shields consists of the following steps:

Step 1. Construct the safety game.
The possible interactions between the environment and the agent can naturally be modelled as a 2-player game. The game is played in alternating moves by the two
players: the environment player picks a next input $i \in \mathcal{I}$
(e.g., sensor data, movement of other agents),
and the agent player picks a next action $a \in \mathcal{A}$.
The game is played on a game graph $\mathcal{G} = \langle \mathcal{S}, \mathcal{E} \rangle$.
The set $\mathcal{S}$ represents the states of the environment, including the state information of the agent that is operating within the environment. The transitions $\mathcal{E} : \mathcal{S} \times \mathcal{I} \times \mathcal{A} \rightarrow\mathcal{S} $ model how the states are updated, depending on the chosen input $i\in \mathcal{I}$ and the chosen action $a \in \mathcal{A}$.
The game graph is complemented by a winning condition in form of a safety specification which defines unsafe states
on  $\mathcal{G}$. The agent loses whenever the play reaches some unsafe state.

Step 2. Compute the maximally-permissive winning strategy.
The objective of the agent player is to always select actions avoiding
unsafe states, while the environment player tries to drive the game to an unsafe state by picking adequate inputs.
Solving the safety game refers to computing a winning strategy $\rho$ for the agent: any play that is played according to $\rho$ (i.e., the agent always picks actions that are contained in $\rho$)
is winning for the agent, meaning that no unsafe states are visited.
For safety games with full information, memoryless winning strategies
$\rho : \mathcal{S} \times \mathcal{I} \rightarrow{2^\mathcal{A}}$
exist [Thomas, 1995].
A maximally-permissive winning strategy subsumes the behaviour of every winning strategy, i.e., at any move, the maximally-permissive winning strategy allows any action that is contained in some winning strategy.

Step 3. Implement a shield by fixing actions.
For any move, we call an action safe if the action is contained in the maximally-permissive winning strategy $\rho$, and call it unsafe otherwise. To implement a shield, we have to define for every unsafe action a concrete safe replacement action.

Given a state $s \in \mathcal{S}$, an input $i \in \mathcal{I}$, and an action $a \in \mathcal{A}$,
a shield is implemented in the following way:

* If $a\in\rho(s,i)$, the shields outputs $a$.

* If $a\notin\rho(s,i)$, the shield outputs
$a' \in \mathcal{A}$ with $a'\in\rho(s,i)$.

The shield is attached to the agent. At every time step, the shield reads the current input and suggested action from the agent, and either forwards the suggested action to the environment if it is safe ($a\in\rho(s,i)$), or replaces the action with a safe action $a'$. Different heuristics have been proposed to decide the choice of $a'$, all with the goal to minimize future shield interferences [Könighofer et al., 2017].

Complexity. Creating and solving the safety game (steps 1 and 2)
has a cost of $\mathcal O(|\mathcal S|)$.
The cost of step 3 depends on the heuristic chosen to decide the corrective safe action.

§ SHIELDING UNDER DELAYED INPUTS

The setting for shielding under delayed inputs is depicted in Figure <ref>.
The delayed information is forwarded sequentially
from the environment to the agent and to the shield.
This corresponds to having a FIFO-buffer
in the information channels.
Let us assume a worst-case delay of $\delta \in \mathbb{N}$ steps.
The shield would therefore have to decide about the safety of an action after some finite execution
$s_0,i_1,a_1,s_1,i_2,a_2,\dots,s_n,i_n$ already having just seen its proper prefix $s_0,i_1,a_1,s_1,\dots,s_{n-\delta}$.
Thus, the shield is not aware of the current state $s_n$.
Instead, it only has access to a proper prefix
of the full state history.
Nevertheless, the shield has to
decide on the safety of the current action $a_n$ of the agent without knowing the remainder of the state history.

Synthesis of delay-resilient shields.
We propose a synthesis algorithm to compute delay-resilient shields. Our algorithm extends the classical game-based  synthesis approach by computing winning strategies under delay.
Our synthesis algorithm performs the following steps:

Step 1-2. As for the delay-free case.
Our algorithm to compute delay-resilient
shields starts by synthesizing a maximally-permissive winning strategy $\rho$ for the delay-free safety game $\mathcal{G}$, as discussed in the previous section.

Step 3. Compute winning strategy under delay.
Playing a game under delay $\delta$ amounts to pre-deciding actions $\delta$ steps in advance.
Even though this makes the control problem harder,
the existence of a winning strategy under such delays is still decidable.

However, for games with delayed inputs, memoryless strategies are not powerful enough.
For a game under delay $\delta$, a winning strategy $\rho_{\delta}$ requires a memory of size $\delta$ to queue the $\delta$ latent actions, i.e.,
$\rho_{\delta} : \mathcal{S} \times \mathcal{I} \times \mathcal{A} ^\delta \rightarrow \mathcal{S}$.
Since straightforward reductions to delay-free games induce a blow-up of the game graph,
which is strictly exponential in the magnitude of the delay [Tripakis, 2004],
we use an
incremental approach.
In the following, we sketch the idea of the algorithm,
further details are in [Chen et al., 2020].
The algorithm incrementally computes the maximally-permissive winning strategies for increasing delays and reduces game-graph size in between.
As controllability (i.e., the agent wins from this state) under
delay $k$ is a necessary condition for controllability under delay $k' > k$, each
state uncontrollable under delay $k$ can be removed before computing the winning strategy for larger delay.
The algorithm returns the maximally-permissive winning strategy
$\rho_{\delta}$ that is winning the original game $\mathcal{G}$ under dely $\delta$.
Although the theoretical worst-case complexity is  $\mathcal O(|\mathcal S|^\delta)$, the incremental algorithm has been proven to be very efficient in practice [Chen et al., 2020].

Step 4. Implement a shield by fixing actions.
A delay-resilient shield has to
correct actions that are unsafe under delay.
Given a state $s \in \mathcal{S}$, an input $i \in \mathcal{I}$, the $\delta$ latent actions
$A = [a_1,\dots,a_{\delta}] \in \mathcal{A}^{\delta}$, and the next action $a$,
a delay-resilient shield is implemented as follows:

* If $a\in\rho_{\delta}(s,i,A)$, the shields outputs $a$.

* If $a\notin\rho_{\delta}(s,i,A)$, the shield outputs

We propose two novel state properties used to
decide on the concrete corrective action $a'$ selected in the delayed case.

* Controllability $\phi_c$:
The value $\phi_c(s)$ of a state $s$ is the maximum delay for which $s$ is controllable, using some threshold
$\delta_{\max}$ to limit the largest considered delay.

* Robustness $\phi_r$:  The value $\phi_r(s)$ of a state $s$ is the length of the minimal path from $s$ to any unsafe state.

Using $\phi_c$ as decision heuristic results
in shields that minimize expected shield interferences caused by delays.
We compute the controllability values
by computing the maximally-permissive winning strategies
$\rho_1,\dots,\rho_{\delta_{\max}}$ for the delays
$\delta\in\{1,\dots,\delta_{\max}\}$ and using them to decide on the controllability of states.
The cost of pre-computing this heuristic for all states is the cost of solving the game for delay up to $\Delta$, in the worst-case $\mathcal O(|\mathcal S|^{\delta_{\max}})$.

Using $\phi_r$ as decision heuristic results
in shields that minimize future expected shield interferences caused by actions that violate safety,
not necessarily related to safety violations due to delays.
Intuitively, this is the case since a high robustness value suggests that the agent is in a state that “easily” satisfies safety,
while values near zero suggest that the system is close to violating it.
The cost of computing this heuristic for all states is $\mathcal O(|S|)$, which adds to the time for solving the delayed safety game.

While the decision heuristic of $\phi_c$ is specially designed for minimizing shield interferences caused by delays, computing  $\phi_c$ for large thresholds $\delta_{\max}$ is computationally expensive. In the experimental section, we will discuss that using shields maximizing $\phi_r$ resulted in almost the same interference rates while being less computationally expensive.

In the delayed setting, the shield is not aware of the current state.
Therefore, a delay-resilient shield has to pick a corrective action such that the expected
controllability or robustness value is maximized.

Let $\delta$ be the worst-case delay,
let $s$ be the last state the shield is aware of,
and let $A= [a_1,\dots,a_{\delta}]$ be the buffer of latent actions.
Then the forward set
$\mathcal{S}_F \subseteq \mathcal{S}$ contains all states that can be reached from $s$
performing the actions $A$.
In other words, $s_f$ is contained in $\mathcal{S}_F$ if there exists a set of inputs $i_1,\dots,i_{\delta}\in \mathcal I$ such that
the execution defined by the transition relation of $\mathcal{G}$ is

We suggest picking the corrective action such that
the average controllability or robustness value of the corresponding forward set is maximized.

§ EXPERIMENTS - SHIELDED DRIVING IN CARLA

We implemented our delayed shields in the driving simulator Carla [Dosovitskiy et al., 2017].
In all scenarios, the default autonomous driver agent in Carla is used
with adequate modifications to make it a more reckless driver.
To capture the continuous
dynamics of Carla
using discrete models,
we designed the safety game with
overly conservative transitions, i.e., accelerations are overestimated and braking power is underestimated.
In both scenarios we use delay-resilient shields maximizing robustness.
All experiments were executed on a computer with
AMD Ryzen 9 5900 CPU, 32GB of RAM running
Ubuntu 20.04.

§.§ Shielding against Collisions with Cars

We consider a scenario in which two cars (one of them controlled by the driver agent) approach an uncontrolled intersection. The shield has to guarantee collision avoidance for any braking and acceleration behaviour of the uncontrolled car, while the observation of the uncontrolled car is delayed. A screenshot of the Carla simulation is given in Figure <ref>.

Shield computation.
To compute delay-resilient shields, the
scenario is encoded as a safety game $\mathcal{G} = \langle \mathcal{S}, \mathcal{E} \rangle$.
We model each car with two state variables:

* $P_{\mathrm{agent}}$ and $P_{\mathrm{env}}$ represent respectively the distances of the agent's car and the environment's car to the crossing.
The range is $P_\mathrm{agent} = P_\mathrm{env} = \{0, 2, 4, \dots, 100 \}~\unit{\metre}$.

* $V_{\mathrm{agent}}$ and $V_{\mathrm{env}}$ represent  the velocity of the agent’s car and the environment's car, resp.
The range is $V_\mathrm{agent} = V_\mathrm{env} = \{0, 1, 2, \dots, 20 \}~\unit[per-mode=symbol]{\metre\per\second}$.

Each time step in the game corresponds to $\Delta t= 0.5~\unit{\second}$ in the simulation.
Each car can perform three actions:
$\mathtt a$ (accelerate), $\mathtt b$ (brake) or $\mathtt c$ (coast, touch no pedal).
Therefore, the set of inputs is
$\mathcal{I}=\{\mathtt a_\mathrm{env},
\mathtt b_\mathrm{env}, \mathtt c_\mathrm{env}\}$ and the set of actions is
$\mathcal{A}=\{\mathtt a_\mathrm{agent},
\mathtt b_\mathrm{agent}, \mathtt c_\mathrm{agent}\}$.
In our model, braking and throttling have the effect of applying a constant acceleration of $a=\pm 2~\unit[per-mode=symbol]{\metre\per\second^2}$.
Therefore, the position $p_t$ at time step $t$ is updated
[The velocity is applied as negative because the car
gets closer to the intersection at every step.]
$p_{t+\Delta t} = p_t - v_t\Delta t - \tfrac{1}{2}a\Delta t^2$, and the velocity as $v_{t+\Delta t} = v_t + a\Delta t$.
Unsafe states represent collisions, therefore
$\mathcal{S_\mathrm{unsafe}}=\{(p_\mathrm{agent}, v_\mathrm{agent},
p_\mathrm{env}, v_\mathrm{env}) : p_\mathrm{agent} = p_\mathrm{env}\}$.
From the safety game, we compute delay-resilient shields that maximize the expected robustness.

In Figure <ref>, we plot the speed of the agent's
car against time and shield interferences (coloured bars) for different delays,
expressed in steps of $\Delta t = 0.5~\unit{\second}$.
As expected, the shield interferes over a longer time for increasing delays.
For delay 0, the agent's car brakes continuously until it escapes danger.
For larger delays, the shields force the car to brake earlier, accounting for the worst-case behaviour of the other car.
The shield always prepares for worst-case behaviour of the environment,
which often does not materialize subsequently.
This explains why the shields change between activity and inactivity several times in the same execution, especially for larger delays.
We tested the shields for several safety-critical scenarios, varying positions and velocities, and were able to avoid collisions in all cases.
In Table <ref>, we give the synthesis times to compute the shields.
Each delay step in Table <ref> corresponds to
$\Delta t = 0.5~\unit{\second}$.

Scenario: cars at an intersection.

Velocity and shield activation over time.

2lDelay (in steps)                                    0        1       2         3
2*Syn. times (in s)                    Car example
1.5        13       48       167
Pedestrian  ex.
0.8      9     34         119

Shield synthesis times (in seconds).

§.§ Shielding against Collisions with Pedestrians

In the second experiment, we compute shields for collision avoidance with pedestrians. Similar to before, the shields guarantee safety under delay even under the worst possible behaviour of the pedestrians.
A screenshot of the Carla simulation is given in Figure <ref>.

Shield computation.
The car, which is controlled by the driver agent, is modelled in the same manner as before. Pedestrians are controlled by the environment and only have as state variables their position.
In our model, we assume that a pedestrian can move $1~\unit{\metre}$ in any direction within one timestep of $\Delta t=0.5~\unit{\second}$.
We consider a state to be unsafe whenever the ego car moves fast while being close to a pedestrian and the pedestrian is closer to the crosswalk than the car.
$\mathcal{S_\mathrm{unsafe}}=\{(p_\mathrm{agent}, v_\mathrm{agent},
p_\mathrm{ped}) :
(v_\mathrm{agent} > 2~\unit[per-mode=symbol]{\metre\per\second}
\land |p_\mathrm{agent}-p_\mathrm{ped}|<5~\unit{\metre}
\land p_\mathrm{ped} < p_\mathrm{agent})\}$.

In Figure <ref> we plot,
for each interference of the shield,
the distance from the pedestrian and the speed of the car at which the shield interferes.
Since pedestrians are modelled in such a way that they are able to move towards the car,
the shield has to consider actual pedestrian positions closer
to the car than observed due to the delays in sensing the pedestrian.
The larger the delay, the more uncertainty the
shield has about the current position of the pedestrian and the earlier the shield initiates braking.
The synthesis times are given in Table <ref>.

In our experiments, the game enters occasionally states with empty strategy
due to discretization errors.
However, the safety specification was never violated.

Scenario: pedestrians at crosswalk.

Shield activation for pedestrian scenario.

§ EXPERIMENTS - SHIELDING IN A GRIDWORLD

Gridworld with possible states after delay $\delta=1$.

Our final case study is an extension of the one from [Chen et al., 2020].
Figure <ref> illustrates a grid world of size $3n+4\times 9$,
where the width is parameterized
by the number of pairs of dead-ends $ n$.
There are two actors that operate in the grid world:
a robot (controlled by the agent) and
a kid (controlled by the environment).
The safety specification requires the robot to avoid any collision with the kid.

Game Graph.
The game graph
encoding the relevant safety dynamics for the grid world is $\mathcal G =\langle S, \mathcal E \rangle$.
The states encode the position of both the robot and the kid.
Thus a state is of the form $(x_0,y_0,x_1,y_1)$,
where $(x_0,y_0)$ is the position of the robot and
$(x_1, y_1)$ is the position of the kid.
Input letters modify the position of the kid $(x_0,y_0)$,
while action letters modify the position of the robot $(x_1,y_1)$.
At every time step, the kid can move 1 step in each direction.
The robot can move zero, one or two steps in each direction, and can also perform three-step L-shaped moves.

Any illegal transition (those that would go out of boundaries or clash with the grey region depicted in Figure <ref>) is changed to
$\mathtt{N}$ (“no move”).

2cDelay (steps)                                    0        1       2         3
2*Score                    Robust.        42.5        34.3      31.5       26.8
Control.       41.3      33.9     31.8          27.5
2*Interventions            Robust.        90.9       107.5      114.1     122.0
Control.     85.0     95.9      106.9        122.7

Performance of different shielding strategies.

Results: Interference Rates. To evaluate the interference of the shields during runtime, we implemented a robot with the goal to collect treasures that are placed at random positions in a grid world with $4$ dead ends. At any time step, there is one treasure placed in the grid world. As soon as this treasure is collected, the next treasure spawns at a random position. Collecting a treasure rewards the agent with $+1$.)
The kid is implemented such that it chases the robot in a stochastic way.

Table <ref> shows for delays $\delta\in\{0,1,2,3\}$
(1) the score obtained by the robot and
(2) the number of times the shield had to intervene
on plays of $2000$ time steps.
Since both the robot and the kid are implemented with stochastic behaviour,
each data point in the table is the average of 100 plays.

The results show that the agent's score decreases with the delay, as expected.
Since the shield has more uncertainty about the current position of the kid,
it enforces a larger distance between the current position of the robot and the last observed position of the kid.
For the same reason, the shields need to interfere more frequently
with increasing delays.
Additionally, we compared the corrective actions
chosen by shields that maximize controllability with the actions chosen by shields that maximize robustness. We noticed that in most states, both shields pick the same corrective action,
leading to similar results.

Results: Synthesis Times.
Figure <ref> depicts synthesis times against delays
for shields maximizing robustness $\phi_{r}$ (images/rs.png),
and controllability $\phi_{c}$ (images/dr.png), respectively.
To compare with a baseline,
we also include the cost of computing
the maximally-permissive strategy in the delayed safety game
for our implementation (images/pres.png)
and the implementation of [Chen et al., 2020]
The improvement of our method compared to the baseline
results from a faster implementation in C++,

with only minor algorithmic reasons.
The cut-off value for controllability is set to $\delta_{\max} = 3$.
Since the cost for computing shields grows exponentially with $\delta$,
the synthesis times for shields maximizing robustness grow exponentially.
This effect does not show for shields maximizing controllability,
as they always compute the maximally-permissive strategy until delay $\delta_{\max}$ irrespective of the particular delay $\delta$.

Synthesis times for a fixed number of 4 dead ends.

§ CONCLUSION

We propose a new synthesis approach to construct shields
that are able to guarantee safety under delays in the input data.
We introduce two shielding strategies that are specifically targeted to minimize
shield interference.
We demonstrate the applicability of our approach in complex applications such as autonomous driving.
In future work, we want to develop shields that are both resilient to delays and able to achieve high performance in probabilistic environments.
Computing delay-resilient games for continuous time by solving timed safety games
is also a promising direction for further research.

§ ACKNOWLEDGMENTS

This work has received funding from the European Union’s Horizon 2020 research
and innovation programme under grant agreement N$^\circ$ 956123 - FOCETA.
It also received funding from  Deutsche Forschungsgemeinschaft under grant no.
DFG FR 2715/5-1 “Konfliktresolution und kausale Inferenz mittels integrierter sozio-technischer Modellbildung”, and by the State of Lower Saxony within the Zukunftslabor Mobilität.
This work was also supported in part by the State Government of Styria, Austria – Department Zukunftsfonds Steiermark.

[Alshiekh et al., 2018]
Alshiekh, M.; Bloem, R.; Ehlers, R.; Könighofer, B.; Niekum, S.; and
Topcu, U. 2018.
Safe Reinforcement Learning via Shielding.
In Proceedings of the AAAI Conference on Artificial
Intelligence (AAAI) 2018, 2669–2678. AAAI Press.

[Ames et al., 2019]
Ames, A. D.; Coogan, S.; Egerstedt, M.; Notomista, G.; Sreenath, K.; and
Tabuada, P. 2019.
Control Barrier Functions: Theory and Applications.
In Proceedings of the European Control Conference (ECC) 2019,
3420–3431. IEEE.

[Bai et al., 2021]
Bai, Y.; Gan, T.; Jiao, L.; Xia, B.; Xue, B.; and Zhan, N. 2021.
Switching controller synthesis for delay hybrid systems under
In Bogomolov, S.; and Jungers, R. M., eds., Proceedings of the
International Conference on Hybrid Systems: Computation and Control (HSCC)
2021, 3:1–3:11. ACM.

[Behrmann et al., 2007]
Behrmann, G.; Cougnard, A.; David, A.; Fleury, E.; Larsen, K. G.; and Lime, D.
UPPAAL-Tiga: time for playing games!
In Proceedings of the International Conference on Computer
Aided Verification (CAV) 2007, 121–125. Springer.

[Bloem et al., 2015]
Bloem, R.; Könighofer, B.; Könighofer, R.; and Wang, C. 2015.
Shield Synthesis: - Runtime Enforcement for Reactive Systems.
In Baier, C.; and Tinelli, C., eds., Proceedings of the
International Conference on Tools and Algorithms for the Construction and
Analysis of Systems (TACAS) 2015, 533–548. Springer.

[Carr et al., 2022]
Carr, S.; Jansen, N.; Junges, S.; and Topcu, U. 2022.
Safe Reinforcement Learning via Shielding under Partial

[Chen et al., 2018]
Chen, M.; Fränzle, M.; Li, Y.; Mosaad, P. N.; and Zhan, N. 2018.
What's to Come is Still Unsure - Synthesizing Controllers Resilient
to Delayed Interaction.
In Proceedings of the International Symposium on Automated
Technology for Verification and Analysis (ATVA) 2018, 56–74. Springer.

[Chen et al., 2020]
Chen, M.; Fränzle, M.; Li, Y.; Mosaad, P. N.; and Zhan, N. 2020.
Indecision and delays are the parents of failure—taming them
algorithmically by synthesizing delay-resilient control.
Acta Informatica, 1 – 32.

[Dosovitskiy et al., 2017]
Dosovitskiy, A.; Ros, G.; Codevilla, F.; Lopez, A.; and Koltun, V. 2017.
CARLA: An Open Urban Driving Simulator.
In Proceedings of the Conference on Robot Learning (CoRL)
2017, 1–16. PMLR.

[Elsayed-Aly et al., 2021]
Elsayed-Aly, I.; Bharadwaj, S.; Amato, C.; Ehlers, R.; Topcu, U.; and Feng,
L. 2021.
Safe Multi-Agent Reinforcement Learning via Shielding.
In Proceedings of the International Conference on Autonomous
Agents and Multiagent Systems (AAMAS) 2021, 483–491. ACM.

[Jansen et al., 2020]
Jansen, N.; Könighofer, B.; Junges, S.; Serban, A.; and Bloem, R. 2020.
Safe Reinforcement Learning Using Probabilistic Shields (Invited
In Konnov, I.; and Kovács, L., eds., Proceedings of the
International Conference on Concurrency Theory (CONCUR) 2020, 3:1–3:16.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

[Könighofer et al., 2017]
Könighofer, B.; Alshiekh, M.; Bloem, R.; Humphrey, L. R.;
Könighofer, R.; Topcu, U.; and Wang, C. 2017.
Shield synthesis.
Formal Methods in System Design, 51(2): 332–361.

[Könighofer et al., 2022]
Könighofer, B.; Bloem, R.; Ehlers, R.; and Pek, C. 2022.
Correct-by-Construction Runtime Enforcement in AI - A Survey.
In Principles of Systems Design - Essays Dedicated to Thomas A.
Henzinger on the Occasion of His 60th Birthday, 650–663. Springer.

[Könighofer et al., 2021]
Könighofer, B.; Rudolf, J.; Palmisano, A.; Tappler, M.; and Bloem, R.
Online Shielding for Stochastic Systems.
In Proceedings of the NASA Formal Methods Symposium (NFM)
2021, 231–248. Springer.

[Prajna and Jadbabaie, 2005]
Prajna, S.; and Jadbabaie, A. 2005.
Methods for Safety Verification of Time-Delay Systems.
In Proceedings of the IEEE Conference on Decision and Control
(CDC) 2005, 4348–4353. IEEE.

[Pranger et al., 2021]
Pranger, S.; Könighofer, B.; Tappler, M.; Deixelberger, M.; Jansen, N.;
and Bloem, R. 2021.
Adaptive Shielding under Uncertainty.
In Proceedings of the American Control Conference (ACC) 2021,
3467–3474. IEEE.

[Tappler et al., 2022]
Tappler, M.; Pranger, S.; Könighofer, B.; Muskardin, E.; Bloem, R.; and
Larsen, K. G. 2022.
Automata Learning Meets Shielding.
In Proceedings of the International Symposium on Leveraging
Applications of Formal Methods, Verification and Validation (ISoLA) 2022,
335–359. Springer.

[Thomas, 1995]
Thomas, W. 1995.
On the synthesis of strategies in infinite games.
In Proceedings of the Symposium on Theoretical Aspects of
Computer Science (STACS) 1995, 1–13. Springer.

[Tripakis, 2004]
Tripakis, S. 2004.
Decentralized control of discrete-event Systems With bounded or
Unbounded Delay communication.
IEEE Transactions on Automatic Control, 49(9): 1489–1501.

[Winter and Zimmermann, 2020]
Winter, S.; and Zimmermann, M. 2020.
Finite-state strategies in delay games.
Information and Computation, 272: 104500.


# Acoustic Analogue for Quantum Field Theory with a Source term

Akshat<EMAIL_ADDRESS>
Department of Physics, Shiv Nadar Institution of Eminence
Greater Noida, Uttar Pradesh-201314, India

###### Abstract

We propose a non-relativistic fluid analogue model for a scalar field coupled
to a classical source. The generic analogue gravity model involves the phonon-
field which is coupled to the acoustic metric. We work in the special
relativity limit of the acoustic analogue. By assuming a time dependent
external potential on the fluid system, we are able to model a source term for
the scalar field. Upon quantisation, phonon creation due to the source is
studied.

##  1 Introduction

Unruh, in 1981, predicted that in a non-relativistic fluid, a trans-sonic flow
produces a thermal spectrum of phonons similar to Hawking radiation from black
holes [1]. Subsequently, several aspects of the analogy between fluid
mechanics and systems coupled to gravity have been better understood and
analogue gravity continues to be an active area of research [2].

At the core of the analogy is the following principle — the equivalence
between low-momentum phonon physics and quantum field theory in curved
spacetime [5]. As a consequence, extensive work has been done in constructing
models analogous to the behaviour of quantum fields within black hole physics
and cosmology [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17].

Some acoustic analogue models have also been constructed for quantum field
theory (QFT) in flat spacetimes [18, 19]. Todd et al. explored acoustic
analogues for Compton scattering [18]. They differentiated between in-universe
observers namely ones coupled to the acoustic metric and who see acoustic
Lorentz invariance, and other observes who uncoupled observers who do not.
While in the present paper we will be concerned with the acoustic metric
framework, there are other ways in which analogues models for QFT can be
constructed using phonon physics. For example, Leizerovitch and Reznik [19]
have proposed an analogue model for Quantum Electrodynamics within Bose-
Einstein condensates.

Within the acoustic metric analogy, choosing the background fluid to be
stationary corresponds to an analogue Minkowski spacetime. Thus we end up with
a massless, free Klein-Gordon (KG) theory.

In this paper we wish to understand, in a top-down way, the limits of this
fluid analogy to the KG field theory. One can immediately see that the fluid
analogy breaks down as soon as one tries to go beyond the free theory, as the
phonon-interactions are not $\sim\phi^{4}$ or $\sim\phi^{3}+\phi^{4}$. Thus
including phonon interactions would lead to the violation of the analogue
Lorentz symmetry [20]. Also, within this acoustic-metric framework, one cannot
study interactions between two different fields as there is only one field
coupled to the acoustic metric, namely that of sound.

However, there is one kind interaction of that both, has physical implications
for the phonons in the fluid, and which can be included without disturbing the
Lorentz invariance in the analogy. This is namely the interaction of the
quantum field with an external classical source. In the rest of the paper we
will see how assuming a time dependent external potential on the fluid system
can be used to model a scalar field with a source term and how such a system
leads to phonon creation in the vacuum upon quantisation.

This paper is organised as follows. In section 2, we revisit parts of Visser’s
derivation for the acoustic metric [4]. We modify a few physical assumptions
to obtain a classical KG equation with a source term. In section 3, we explore
some consequences of the system upon quantisation. We end with a summary in
section 4.

##  2 Massless scalar field equation with source

We assume fluid to be barotropic, inviscid and irrotational. The dynamics is
completely described by the continuity and Euler equations.

We start with the continuity equation given by

$\displaystyle\frac{\partial}{\partial
t}\rho+\vec{\nabla}\cdot(\rho\vec{v})=0$ (1)

The Euler equation of motion reads

$\rho\frac{\mathrm{d}v}{\mathrm{~{}d}t}\equiv\rho\left[\displaystyle\frac{\partial}{\partial
t}\vec{v}+(\vec{v}\cdot\vec{\nabla})\vec{v}\right]=\vec{F}$ (2)

Since the fluid is inviscid the only terms of relevance in $\vec{F}$ are the
ones of the pressure gradient and external potential $\chi$. For example,
$\chi$ could be the gravitational potential. As such we can write
$\vec{F}=-\nabla p-\rho\nabla\chi$. Thus equation (2) acquires the form

$\rho\left[\displaystyle\frac{\partial}{\partial
t}\vec{v}+(\vec{v}\cdot\vec{\nabla})\vec{v}\right]=-\nabla p-\rho\nabla\chi$
(3)

Upon rearranging:

$\partial_{t}\vec{v}=-(\vec{v}\cdot\vec{\nabla})\vec{v}-\frac{1}{\rho}\nabla
p-\nabla\ \chi$

and using the identity for vector products

$(\vec{v}\cdot\vec{\nabla})\vec{v}=-\vec{v}\times(\nabla\times\vec{v})+\frac{1}{2}\nabla
v^{2}$

we are led to

$\partial_{t}\vec{v}=\vec{v}\times(\nabla\times\vec{v})-\frac{1}{\rho}\nabla
p-\nabla\left(\frac{1}{2}v^{2}+\chi\right)$ (4)

Since the fluid is irrorational which means $\nabla\times\vec{v}=0$, we can
define a velocity potential $\phi$ in the manner $\vec{v}=-\nabla\phi$
implying

$-\partial_{t}\left(\nabla\phi\right)=-\frac{1}{\rho}\nabla
p-\nabla\left(\frac{1}{2}\left(\nabla\phi\right)^{2}+\chi\right)$ (5)

Employing the barotropic condition i.e. $\rho\equiv\rho(p)$ enables us to
define a quantity $h$ whose gradient has the integral representation

$b(p)=\int_{0}^{p}\frac{dp^{\prime}}{\rho\left(p^{\prime}\right)}$ (6)

Thus

$\nabla b=\frac{1}{\rho}\nabla p$ (7)

As a result the Euler equation becomes

$\nabla\left(-\partial_{t}\phi+b+\frac{1}{2}(\nabla\phi)^{2}+\chi\right)=0$
(8)

which immediately suggests that

$-\partial_{t}\phi+b+\frac{1}{2}(\nabla\phi)^{2}+\chi=\Lambda$ (9)

where the constant $\Lambda$ can be absorbed in $\chi$ resulting in a simpler
version of the Euler equation

$-\partial_{t}\phi+b+\frac{1}{2}(\nabla\phi)^{2}+\chi=0$ (10)

Let us now adopt the well-known procedure of linearisation with respect to a
small parameter $\epsilon$ in which the density $\rho$, pressure $p$, $\phi$
and $\chi$ are represented by

$\displaystyle\rho=\rho_{0}+\epsilon\rho_{1}+O\left(\epsilon^{2}\right)$ (11)
$\displaystyle p=p_{0}+\epsilon p_{1}+O\left(\epsilon^{2}\right)$ (12)
$\displaystyle\phi=\phi_{0}+\epsilon\phi_{1}+O\left(\epsilon^{2}\right)$ (13)

This leads to the linearisation of the barotropy relation

The barotropic condition gives us

$b(p)=h\left(p_{0}+\epsilon
p_{1}+O\left(\epsilon^{2}\right)\right)=\int_{0}^{p+\epsilon
p_{1}+O\left(\epsilon^{2}\right)}\frac{dp^{\prime}}{\rho\left(p^{\prime}\right)}=b(p_{0})+\epsilon\frac{p_{1}}{\rho_{0}+\epsilon\rho_{1}}+O\left(\epsilon^{2}\right)\\\
\\\ $ (14)

This can be written up to an order of $\epsilon$

$b_{0}+\frac{\epsilon p_{1}}{\rho_{0}+\epsilon\rho_{1}}\approx
b_{0}+\frac{\epsilon p_{1}}{\rho_{0}}\\\ $ (15)

Additionally, we also linearise the external potential

$\chi=\chi_{0}+\epsilon\chi_{1}+O\left(\epsilon^{2}\right)$ (16)

As we shall see, this perturbation in the external potential eventually leads
to the presence of the source in the field equation.

Since we want to get to flat-spacetime QFT, at this point we can make some
simplifying assumptions. We assume background fluid to be at rest i.e.
$\vec{v}_{0}=0$ implying $\phi_{0}$ is a constant. Additionally we assume the
background fluid density $\rho_{0}$ and pressure $p_{0}$ to be constant.

Following the linearisation, the continuity equation becomes

$\partial_{t}\rho_{1}+\nabla.(\rho_{0}\vec{v}_{1})=0$ (17)

And the Euler equation takes the form

$-\partial_{t}\phi_{1}+\frac{p_{1}}{\rho}+\chi_{1}=0$ (18)

Since, fluid is barotropic, using equation (18), $\rho_{1}$ takes the form

$\rho_{1}=\frac{\partial\rho}{\partial
p}\rho_{0}(\partial_{t}\phi_{1}-\chi_{1})$ (19)

In such fluid systems, sound is defined as the a consequence of perturbation
in the fluid quantities with the speed of sound given by

$c_{s}^{-2}\equiv\frac{\partial\rho}{\partial p}$ (20)

Plugging this into the continuity equation, we get

$\frac{1}{c_{s}^{2}}\partial_{t}(\partial_{t}\phi_{1}-\chi_{1})-\nabla^{2}\phi_{1}=0$
(21)

Upon rearranging terms, we get

$\Box\phi_{1}\equiv\left(\frac{1}{c_{s}^{2}}\partial_{t}^{2}-\nabla^{2}\right)\phi_{1}(\vec{x},t)=\frac{\partial_{t}\chi_{1}(\vec{x},t)}{c_{s}^{2}}$
(22)

We see we have obtained the massless KG equation coupled to a classical source
$j(\vec{x},t)$ defined as

$j(\vec{x},t)\equiv\frac{\partial_{t}\chi_{1}(\vec{x},t)}{c_{s}^{2}}$ (23)

We see that assuming that the external potential has a perturbation and that
this perturbation is time-dependent leads to the source term. Further, one
might think that the presence of only the time derivative in the source term
could lead to inconsistencies with the analogue Lorentz symmetry. However,
this choice works just fine as the system we are working with is completely
non-relativistic and thus has a unique time coordinate — the laboratory time.

What we are interested in is the quantum version of equation (22) which would
then be the equation of motion for a phonon field [21, 22]. Note that since
the source term is due to the external potential and not a part of the fluid
system, it is still classical.

Thus we end up with a scalar quantum field coupled to a classical source. From
here on, it is a standard textbook calculation [23, 24]. Nevertheless, in the
next section we shall sketch out some results in particular those related to
particle creation. We shall consider $\hbar=c_{s}=1$. Further, to simplify
notation we shall write $\phi_{1}$ as $\phi$.

##  3 Particle creation

The Lagrangian density corresponding to equation (22) is

$\mathcal{L}=\frac{1}{2}\partial_{\mu}\phi\partial^{\mu}\phi+j\phi$ (24)

As defined above, $j(x)$ is non-zero only for a finite time. We are interested
in solutions after $j(x)$ has been turned off. The solution takes the
following form

$\phi(x)=\phi_{f}(x)+\phi_{s}(x)$ (25)

Here $\phi_{f}$ is the standard solution to the source free quantised KG
equation that is

$\phi_{f}(x)=\int\frac{d^{3}k}{(2\pi)^{3}}\frac{1}{\sqrt{2\omega_{\vec{k}}}}(a_{\vec{k}}e^{ikx}+a_{\vec{k}}^{\dagger}e^{-ikx})$
(26)

The addition to the solution can be written in term of the retarded Green
function

$\phi_{s}(x)=i\int d^{4}yD_{R}(x-y)j(y)$ (27)

Since its all in the past, $D_{R}$ simplifies and we get

$\phi_{s}(x)=i\int
d^{4}y\int\frac{d^{3}k}{(2\pi)^{3}}\frac{1}{2\omega_{\vec{k}}}(e^{-ik(x-y)}-e^{ik(x-y)})j(y)$
(28)

Since the integral is over all $y$, we can make use of the Fourier transform
of $j(y)$

$\tilde{j}(k)=\int dye^{iky}j(y)$ (29)

Plugging this into equation (28) we see equation (25) takes the following form

$\phi(x)=\int\frac{d^{3}k}{(2\pi)^{3}}\frac{1}{\sqrt{2\omega_{\vec{k}}}}\left(\left(a_{\vec{k}}+i\frac{\tilde{j}(k)}{\sqrt{2\omega_{\vec{k}}}}\right)e^{ikx}+\left(a_{\vec{k}}^{\dagger}-i\frac{\tilde{j}^{*}(k)}{\sqrt{2\omega_{\vec{k}}}}\right)e^{-ikx}\right)$
(30)

The creation and annihilation operators have been shifted by a function. The
new set of states constructed out of the shifted operators are the field
theoretic versions of coherent states [25].

Therefore, we can define new set of creation and annihilation operators
$A_{\vec{k}}$ and $A^{\dagger}_{\vec{k}}$ such that

$A_{\vec{k}}\equiv a_{\vec{k}}+i\frac{\tilde{j}(k)}{\sqrt{2\omega_{\vec{k}}}}$
(31)

In terms of these, the number operator $N$ can be written as

$N=\int\frac{d^{3}k}{(2\pi)^{3}}A^{\dagger}_{\vec{k}}A_{\vec{k}}$ (32)

For the source free theory, the number operator $N_{f}$ would simply be
$A^{\dagger}_{\vec{k}}A_{\vec{k}}\xrightarrow{}a^{\dagger}_{\vec{k}}a_{\vec{k}}$
in the above equation. In that case by definition, the vacuum expectation
value of $N_{f}$ is 0.

We are interested in calculating the vacuum expectation value of the number
operator $N$

$\matrixelement{0}{N}{0}=\int\frac{d^{3}k}{(2\pi)^{3}}\frac{1}{2\omega_{\vec{k}}}|\tilde{j}(k)|^{2}$
(33)

Note that the vacuum state here is that of the free vacuum. We thus see the
effects of the source on the free theory. We can check that upon considering
the external potential to be time-independent $j$ and consequently $\tilde{j}$
vanish. In this case equation (33) tells us that the particle number is 0.
Thus, we see that it is the time dependent potential that leads to particle
creation. These particles are indeed phonons given by the on-shell Fourier
modes of the source.

We note that despite being a straightforward calculation, there are aspects of
quantum fields with a classical source which are not well understood.
Recently, Tinti et al. highlighted the non-trivial dynamics of scattering
processes in the presence of time dependent classical sources [26]. Another
interesting work in this context is by Fulling et al. in which they explore
the consistency between classical and quantum field theory using an external
source [27].

Lastly, we want to emphasise that our analysis involved certain simplifying
assumptions. To extend this to a physically testable situation these
assumptions need to be carefully relaxed. Our model has finite size i.e. the
integration over all $y$ is, in fact, over a finite region. This will lead to
discretization in the $k$ values. More importantly, the $k$ values will have
an associated UV cut-off, like in QFT. For the analogue model this becomes
even more important because as mentioned in the introduction, the analogy with
QFT in curved spacetimes holds only for low-momentum phonon physics.

##  4 Summary

In this paper, we presented a non-relativistic acoustic analogue model for a
relativistic quantum field theory coupled to a classical source in flat
spacetimes. We assumed the external potential acting on the fluid system to
have a time dependent perturbation which, in turn, mimicked the classical
source. We studied how this source in the analogue model would lead to the
production of phonons in the fluid.

## References

  * [1] Unruh W. G. Phys. Rev. Lett. 46 (1981) 1351.
  * [2] Barcelo C. et. al.Living Rev. Relativ. 14 (2011) 1-159.
  * [3] Braunstein S.L et al. Nat. Rev. Phys. 5 (10) (2023) 612-622.
  * [4] Visser M. Class. Quant. Grav. 15 (1998) 1767.
  * [5] Visser M. Int. J Mod. Phys. D12 (2003) 04.
  * [6] Anacleto M. A. et al. Annals Phys. 440 (2022) p 2004. 168837.
  * [7] Steinhauer J. et al. Nat. Comm. 13 (1) (2022) 2890.
  * [8] Berti E. et Phys. Rev. D70, (2004) 124006.
  * [9] Barcelo C. et. al. Int. J Mod. Phys. D12 (2003) 09.
  * [10] Bilic N. 1999 Class. Quant. Grav. 16 3953\.
  * [11] Patrick S. et al. Phys. Rev. Lett. 126 (4) (2021) 041105.
  * [12] Barcelo C. et al. Class. Quant. Grav. 18 (17) (2001) 3595.
  * [13] Jacquet M. et al. Eur. Phys. J. D 76, (8)(2022) 152.
  * [14] Ling R. et al. Phys. Rev. D104 (10) (2021) 104003.
  * [15] Balbinot R. A. et al. La Rivista del Nuovo Cimento 28 (2005) 1-55.
  * [16] Pandey A. Grav. Cosmo. 30 (2) (2024) pp. 228–233.
  * [17] Das S. R. et al. JHEP 04 (2011) 030.
  * [18] Todd S. L. et al. Phys. Rev. D104 6 (2021) 064035.
  * [19] Leizerovitch S. et al. Phys. Rev. A95 4 (2017), p.043611.
  * [20] Barcelo C. et al. New J. Phys. 6 (1) (2004) 186.
  * [21] Barcelo C. et al. Class. Quant. Grav. 18 6 (2001): 1137.
  * [22] Liberati S. et al. Class. Quant. Grav. 23 (9) (2006) 3129.
  * [23] Coleman S. Notes from Sidney Coleman’s Physics 253a [arxiv:1110.5013]
  * [24] Peskin M. E. et al.  An Introduction to quantum field theory (1995)(Addison-Wesley, Reading, USA).
  * [25] Bagchi B. et al. Int. J Mod. Phys. A35 (19) (2022), p.2030011.
  * [26] Tinti L et al. (unpublished) (2024) [arXiv:2403.15531].
  * [27] Fulling S.A. et al. Proc. Roy. Soc. A476 2243 (2020), p.20200656.


11institutetext: ∗Bosch Corporation Research, +Bosch Chassis Systems Control,
11email: {jieun.kim, cory.henson, kevin.huang,anhtuan.tran2, wan-
<EMAIL_ADDRESS>
# Accelerating Road Sign Ground Truth Construction with Knowledge Graph and
Machine Learning

Ji Eun Kim∗ Cory Henson∗ Kevin Huang∗ Tuan A. Tran+ Wan-Yi Lin∗

###### Abstract

Having a comprehensive, high-quality dataset of road sign annotation is
critical to the success of AI-based Road Sign Recognition (RSR) systems. In
practice, annotators often face difficulties in learning road sign systems of
different countries; hence, the tasks are often time-consuming and produce
poor results. We propose a novel approach using knowledge graphs and a machine
learning algorithm - variational prototyping-encoder (VPE) - to assist human
annotators in classifying road signs effectively. Annotators can query the
Road Sign Knowledge Graph using visual attributes and receive closest matching
candidates suggested by the VPE model. The VPE model uses the candidates from
the knowledge graph and a real sign image patch as inputs. We show that our
knowledge graph approach can reduce sign search space by 98.9%. Furthermore,
with VPE, our system can propose the correct single candidate for 75% of signs
in the tested datasets, eliminating the human search effort entirely in those
cases.

###### keywords:

Knowledge Graph, Meta-Learning, Road Sign Classification, Data Annotation,
Crowd-sourcing, Human in the Loop, Autonomous Driving

##  1 Introduction

Recognizing and understanding road signs are important features of advanced
driver-assistance systems (ADAS), which are offered in modern vehicles via
technologies such as road-sign recognition (RSR) or intelligent speed adaption
(ISA)111These features are mandatory in all new cars sold within Europe from
May 2022 [3]. Recent RSR and ISA solutions heavily use Machine Learning
methods and require comprehensive, high-quality datasets of road sign
annotation as ground truth. To be ready for real-world usage, the ground truth
must be built from test drives around the world. The number of road sign
images to be annotated can be enormous, up to more than ten millions each
year. Any representative sample of these images that covers enough countries
and conditions will be of considerable size. It is therefore crucial to
optimize the annotation task and minimize annotator’s time in each session.

There are two main challenges in performing a road sign annotation task.
First, there are too many road signs to search through to find a matching one
(USA alone has more than 800 federally approved road signs, and 10 states in
USA have their own state conventions which are different from the federal
convention [23]). This makes manual classification of each sign instance
against a full palette of signs infeasible222Note that we define ”sign” as a
prototypical sign, and differentiate it from ”sign instance” which is an
instance of a prototypical sign as seen in drive data. For example, if a set
of images contains 4 stop signs and 4 yield signs, then there are 8 sign
instances in total, and 2 signs (stop and yield).. One solution is to have a
machine learning system limit the number of candidates for human annotators to
search from (e.g., to 5 signs).

The second challenge lies in the fact that different countries follow
different conventions on road signs. For instance, USA follows MUTCD [23],
while European countries adopt the Vienna convention [9]. Some countries adopt
multiple conventions, and some introduce different variants in features such
as colors, fonts, size, etc. This is illustrated in Figure 1. No annotator
possesses full knowledge of all road sign systems and may choose the wrong
ones, especially when the instance is not clear (e.g., gray-scale images,
night images, and so forth).

Figure 1: Examples of Various Road Signs Across Countries Representing
Different Shapes, Colors, Icons and Languages

In this work, we address the above issues with a novel solution that combines
knowledge graph and machine learning to assist annotators and accelerate the
ground truth annotation. The idea is that all road signs have some basic
visual features, and we can navigate through the knowledge graph of these
visual features (focusing on country-specific sub-graphs by using GPS data
associated with the images), to locate the candidate signs, supporting the
sense-making of human annotators. We show that this approach can reduce the
search space for signs by 98.9%, from 845 signs to 8.92 signs. This reduction
in search space translates to reduced search effort and time by human
annotators for locating the correct sign. To further reduce the search space,
we propose to use a Variational Protoyping-Encoder (VPE [16]) that uses one-
shot learning to find matching signs, even if unseen in prior training data.
To summarize our contribution, in this work we have:

  * •

introduced Road Sign Ontology (RSO) to represent salient features of road
signs,

  * •

proposed crowd-sourcing techniques to construct the Road Sign Knowledge Graph
at scale across countries and states

  * •

used knowledge graph to reduce the sign search space by 98.9%

  * •

built a VPE model that is combined with the knowledge graph to further reduce
the search space. This approach can propose the correct single candidate for
75% of signs in the tested datasets even for unseen signs during the training
phase, eliminating the human search effort altogether in those cases

In the following sections, we quickly summarize related work, explain the
construction of the ontology and knowledge graph, and detail our knowledge
graph and machine learning-assisted road sign annotation pipeline. Finally, we
present our experimental results on internal and public datasets.

##  2 Related Work

#### Road Sign Detection and Classification

Due to the ubiquitous presence of road signs, detecting and classifying them
are important tasks in automated driving research [28, 25]. A typical
framework involves the detecting of bounding boxes containing road signs from
video or image data [21], then mapping them to canonical signs, often
represented by an image prototype. While much of existing work focused on the
visual properties of the road signs such as color [18], shape, and templates
[19, 20], the varying of such properties as regulated in different conventions
is not well addressed [21]. Although there are several open datasets for road
sign recognition and classification [25, 26, 17, 6], they cover only a very
small portion of the signs and face several challenges when adapted to the
international setting.

#### Using Knowledge Graph to Improve Evaluation

Our work is characterised by the usage of an ontology and knowledge graphs to
assist human annotators in complex tasks. In this perspective, it has been
studied in crowd-sourcing research communities, by introducing domain
knowledge to support human sense-making and learning during the microtask.
Early work in this direction can be found in database or text mining
applications [8, 11]. For visual tasks, some open ontologies are built to help
humans annotate the biomedical concepts [7]. To the best of our knowledge, the
use of a large-scale knowledge graph, consisting not only of taxonomy but also
of Resource Description Framework (RDF) facts curated from several sources for
evaluating visual tasks in autonomous driving area is completely unexplored.

Our construction of the Road Sign Knowledge Graph is also inspired by related
work in evaluating quality of large-scale linked data using crowd-sourcing
[14, 24]. For images, previous work suggests that careful design of microtask
should take into account visual effects on human across countries [14].

#### Meta-Learning for Road Signs

A recent approach for dealing with the incompleteness of road sign classes is
to use meta-learning, including few-shot and one-shot learning [27, 16]. The
idea is to represent each unseen road sign class with an image prototype,
which is jointly encoded with existing classes, either driven by a distance
metric or a meta-model, to learn to translate each real image depicting a road
sign. Some work combines knowledge graph into meta-learning to improve the
performance via concept propagation [15]. In autonomous driving, to the best
of our knowledge, our work is the first to propose the combination of
knowledge graph and one-shot learning to construct ground truth efficiently.

##  3 Road Sign Ontology

This section describes an ontology for representing and reasoning about road
signs; namely, the Road Sign Ontology (RSO). This ontology, and its conformant
knowledge graph (see Section 4), is used to assist in the data annotation
process and the training of machine learning models for road sign
classification. RSO seeks to represent the salient visual features of a road
sign that are discernible through sight or imaging, and is modeled using the
Web Ontology Language (OWL2) [13]. See Figure 2 for a visualization of the
primary ontology concepts.

While designing RSO, two primary requirements were considered. First, the
ontology should represent the features of road signs that are beneficial to
the performance of machine learning algorithms. Second, the ontology should
represent concepts at an appropriate level of granularity that enables human
annotators to effectively identify road signs and their visual features when
looking at an image.

###  3.1 Road Sign Features

The primary features of a road sign to be represented include its shape,
color, text, and printed icons.

#### Shape

RSO distinguishes between two types of shapes associated with a road sign. The
most obvious is the shape of the physical plate. For example, in the United
States, stop signs have an octagon shape, yield signs have a downward triangle
shape, and speed limit signs have a rectangular shape. There are 11 different
shapes that the physical plate of a road sign could take. The second type of
shape includes geometric shapes that are printed on the physical plate. Common
printed geometric shapes include arrows, circles, and diagonal lines. RSO
represents 9 different printed shapes.

#### Color

Similar to shape, RSO distinguishes between multiple different types of color
associated with a road sign. Specifically, a road sign can have a foreground
color, a background color, and a border color. 11 common colors are enumerated
within the ontology.

#### Icon

Icons are a special type of shape printed on a road sign that depict various
objects. The types of objects often depicted include vehicles, people,
animals, and assorted traffic infrastructure (e.g., a traffic light). Given
the large number of possible distinct icons, RSO only defines a few common
categories, including: animal, infrastructure, nature, person, vehicle, and
other.

#### Text

Many road signs include printed text. Stop signs print the word STOP, yield
signs print the word YIELD, and speed limit signs include both the words Speed
Limit and a number. Rather than enumerating all possible text that may be
printed on a sign, RSO allows the text of a specific sign to be annotated
using an OWL Datatype Property. While RSO does not define enumerations for all
possible text on a road sign, it does enable the categorization of text into
various types, based on the intended meaning or use. The categories of text
include: speed, height, weight, time, name, and number. As an example, the
text of a speed-limit sign is identified with the speed category, while the
text of a sign announcing entrance to a town is identified with the name
category.

(a) Class Hierarchy

(b) Object Properties

Figure 2: Visualization of the Road Sign Ontology with Protege [22]

###  3.2 Road Sign Conventions and Prototypes

In practice, road signs must adhere to convention. It is this adherence that
allows and empowers a person to detect and identify the meaning of a sign with
only a brief glance. Such conventions define rules and constraints on how road
signs of various types should be printed and displayed. There are three
primary road sign conventions in use today: the Vienna Convention [12], the
MUTCD Convention [23], and the SADC Convention [4]. The Vienna Convention is
used primarily in Europe and China; the MUTCD Convention (i.e., Manual on
Uniform Traffic Control Devices) is used primarily in the United States; and
the SADC Convention (i.e., Southern African Development Community) is used
primarily in Africa. Variations of these conventions may be defined and used
for more specific geo-spatial regions. For example, each state in the United
States may either adhere to the federal version of MUTCD or they may define
their own state-specific version. Each road sign represented by RSO may be
associated with the convention to which it adheres.

Conventions also provide standard images that depict the sign. These standard
images are often referred to as prototypes and provide a template for the
design, construction, and illustration of signs in manuals. Prototypes often
come in two versions, a full color version and a gray-scale version. RSO
enables road signs to link to these prototype images on the Web.

###  3.3 Alignment with Domain Vocabularies

While the Road Sign Ontology defines a general vocabulary to catalog visual
and conventional properties of road signs, we need to extend it to include
other non-ontological structure of existing road sign datasets, and to tailor
to domain-specific (ADAS) applications used in commercial systems. This is
important to allow the machine learning and computer vision models, which is
developed using the specific labels of the datasets or domain-specific
taxonomy, to interoperate with the knowledge graphs. In our work, we integrate
three open datasets: LISA [21], representing US signs, GTSRB [25],
representing German signs, and TT-100K [28], representing Chinese signs. Each
of these datasets have a vocabulary that is tailored to representing signs
only in a specific region. In addition, we also model the taxonomy used in our
different in-house annotation applications, which cover road signs of 72
countries, and are optimized for TSR function development. Below we present
the high-level approach of our alignment.

To integrate these datasets, we create domain-specific vocabularies and put
them under each corresponding namespace. Of course, there is a significant
overlap between namespaces, but the alignment is non-trivial, for example in
two following cases:

Road Sign Categories — The way that road signs are categorized is different
for each domain and dataset. Each uses a distinct number of categories with
divergent levels of granularity. As an example, a road sign (e.g., truck speed
limit 60) can be mapped to a single category truck speed limit within one
dataset (TT-100K), while mapped to both a truck sign category and a speed
limit sign category in another (GTSRB).

Road Sign Features — Road sign features are also represented at different
levels of abstraction within the various domains and datasets. While our
special in-house annotation tools enable annotators to describe detailed
features of the road signs, open datasets only use prototypical images.
Furthermore, GTSRB provides for each sign different prototypes with variants
in foreground, background, and border, while TT-100k and LISA use only one
prototype per each.

Figure 3 illustrates how the Road Sign Ontology is aligned with domain
vocabularies. The standard owl:equivalentClass is used to link the sign
categories, and new relations are introduced for equivalent road sign
features. We also introduce the class Variant to embrace the different
prototypes as in the case of GTSRB.

Figure 3: Example of aligning the concept of road sign, in RSO, with concepts
in other vocabularies.

##  4 Road Sign Knowledge Graph

This section describes our approach to build the Road Sign Knowledge Graph at
scale based on RSO discussed in Section 3. We need to design the knowledge
graph specifically to enable the recognition of road signs in different
applications. However, building the knowledge graph manually is both time
consuming and difficult due to lack of comprehensive domain knowledge of human
annotators. In our work, we develop a two-step system: First, we rely on the
crowd to construct the large-scale graphs with basic properties. Second, we
align and extend the graphs to ”fine-tune” to domain-specific data and
vocabularies. Below we detail our approach.

###  4.1 Road Sign Knowledge Graph Construction with Crowdsourcing

As the number of localized road signs is considerably large and requires many
people who know different languages used in different locations, we leverage
crowds recruited from three online crowd-sourcing marketplaces with global
registered work-forces: Amazon Mechanical Turk [1] , Click Worker [2] and
UpWork [5]. We design two tasks in each platform:

#### Identifying Road Sign Templates for Various Countries

In the first task, we ask the crowd to find a Web site that provides official
road sign documents having templates of the road sign for a target country or
state. We ask at least three crowd workers to get consensus on recommended
sources. After identifying a source, manual template extraction is required if
the identified resource does not support a separate image file format for each
road sign template.

#### Road Sign Feature Extraction

In the second task, we create a web-based application for crowd workers to
extract the sign features used for constructing the road sign knowledge graph.
A snapshot of the user interface is shown in Figure 4. In detail, the crowd
worker is asked to look at a road sign template and provide the plate shape,
background color, border color, additional shapes (e.g., left arrow) inside
the plate, icons (e.g., vehicle), text and variants (e.g., street name) if
applicable. This microtask can be done by any crowd workers and does not
require road sign knowledge i.e., the meaning of a given road sign template.
All answers can be selected from the provided options, except text that should
be typed in the text field. Therefore, we do not specify any driving
experience as qualification or require any training; we simply provide an
instruction with examples and recruit workers whose approval rate is greather
than 98%. However, each HIT includes one gold standard road sign, for which
the system knows the ground truth in order to screen scammers who
intentionally try to fool our system. Each individual sign template is
presented to one worker, and one internal expert reviews the answers from the
worker, followed by an additional review with another internal expert for
further clarification if necessary.

We have constructed a generic road sign knowledge graph with 2,804 road signs
from two different countries as of the reporting date. (The number of signs
will be increased when adding signs for more countries.) In detail, 281 HITs
(i.e., Human Intelligent Task) are published to Amazon Mechanical Turk when
extracting sign features for U.S federal signs, three US states signs and
German signs. Each HIT includes up to 10 road sign templates. The number of
questions for each sign template varied based on sign features shown in each
template. 7 to 11 questions are answered for an individual sign template. It
took 23.7 minutes on average to complete one HIT. The workers provided correct
answers (98%) for most questions on shapes, icons, and text. We observed that
some colors such as yellow and orange are not properly annotated by a handful
workers, possibly due to color representation in the screen they used. We did
not reject these answers but correct the answers during the review process.
Surprisingly 35% of answers are incorrect when they are asked to provide
variants or units for certain signs. For instance, a no parking sign (see the
last sign in 1) includes a time variant (8:30 AM to 5:30PM), but some workers
were not able to recognize this time variant. Also the ground truth for the
SPEED LIMIT 30 unit is ”miles per hour”, but some workers gave ”miles” as the
unit. 41% of workers reported that they drive everyday and 6% of workers do
not have a driving license. We have not seen any differences in the road sign
knowledge graph annotation quality with respect to workers’ driving
experience. 1% of scammers are detected when running this batch of HITs.

Figure 4: Screenshot of the Crowdsourcing Task for Road Sign Attribute
Extraction

Validated attributes for each sign template are translated into RDF facts of a
corresponding entity of type Sign in the _generic knowledge graph_. Next, we
describe how the facts are refined to produce different domain-specific
graphs.

###  4.2 Alignment of Road Sign Knowledge Graph to Domain-specific Knowledge
Graphs

To get the knowledge graphs specific to different domains, we first create a
separate graph for each domain from the relevant sub-graph of the generic
knowledge graph (for instance, a sub-graph containing all facts about a target
country or state). We then perform the following three alignments to extend
and refine the domain-specific graphs:

  * •

Automated Reasoning: As our RSO is compliant to OWL-DL, the system can perform
semantic reasoning to add more facts, such as adding category to the sign via
its color and shapes. The reasoning can also create facts in different
granularity . For example, the property has foreground color can be refined to
has icon color, has text color, has shape within a sign color using the
subsumption, or mapped to a more generic property has color.

  * •

Auto-transformation for individual triples: If the content in a triple in the
generic graph is transformable, we apply rules to get more facts. For
instance, the text ”SPEED LIMIT 30” can be transformed into two triples with
”SPEED LIMIT” as a text and 30 as a numerical value in the domain-specific
graph.

  * •

Manual alignment: Finally, experts of ontology alignment are also advised to
add new vocabularies into the domain-specific graphs when needed. For example,
the category/class names used in a domain are often acronyms, which cannot be
automated without additional inputs.

The result of this step is a generic road sign knowledge graph and multiple
domain-specific graphs. The graphs with new signs are regularly reviewed by
domain experts. Meanwhile, only relevant graphs are loaded into the downstream
annotation task (described in Section 5) to mitigate implications of any
remaining inconsistency.

###  4.3 Notes on Architecture

The knowledge graphs are stored and processed in the StarDog Enterprise
Cluster333https://www.stardog.com. We use a MongoDB444https://www.mongodb.com
database to store intermediate annotations and perform multiple validation
before storing it in StarDog. We extended JenaBean [10] to convert the Web
application data model to the triples that follow Road Sign Ontology (RSO)
described in Section 3. We use the built-in semantic reasoning and regular
expression capabilities in StarDog to perform the graph alignment.

##  5 Knowledge Graph and Machine Learning Assisted Road Sign Annotation
Pipeline

This section describes how the proposed Road Sign Knowledge Graph and the
domain Road Sign Knowledge Graph is used in our road sign annotation tool,
along with a machine learning classifier, to assist a human annotator on an
image.

Figure 5: Road Sign Annotation Process

#### Tasks for the Human Annotator

As shown in Figure 5, the task for the human annotators is to draw a bounding
box around a road sign on an image and select a matching sign prototype from a
small palette of signs. We do not expect the human annotators possess
knowledge on traffic systems which often vary across countries. Furthermore,
this simple task does not require a separate training session about road signs
to complete. Instead, annotators interact with the system by providing road
sign features which are visible inside of the bounding box they draw on the
Web UI. The annotator provides visual attributes such as plate sign shape and
background color as common attributes, and icons, text and additional shapes
as optional attributes. Then, they are asked to select a sign template from
the ordered candidates. The task execution time and quality depends on the
search space, i.e., the number of candidates they have to visually compare,
and the quality of the image. If a road sign is not exactly matching with any
candidates, then a worker selects a most matching sign or a default sign
template that represents common attributes such as plate shape and background
color with an indication of missing a sign template. This indication is
further used by the system to add missing signs to the knowledge graph. Note
that road signs in the wild are sometimes customized and knowledge graph
constructed based on the official documents cannot cover all possible
variation at the beginning of the system deployment. Rather we support to
scale up while running the system with workers’ feedback.

#### Use of Road Sign Knowledge Graph and Machine Learning Model

Our tool supports the human annotator by providing a handful of road sign
candidates that match the attributes given through a knowledge graph search.
If the number of sign candidates is greater than a threshold K, then the
machine learning model is applied to further reduce the number of candidates.

We integrate the Variational Prototypical Encode (VPE) model [16] to predict
top-K road sign candidates. The inputs for the VPE model are: 1) a cropped
image patch around the bounding box that the annotator draws on the real road
image and 2) sign templates filtered by the Road Sign Knowledge Graph. These
two inputs are encoded into the latent space, and nearest neighbor
classification is used to rank road sign templates. The system returns top K
candidates back to the human annotator.

Prediction of unseen classes is crucial in the road sign annotation due to
rare road signs in the long tail. Model prediction of conventional
classification with known classes cannot assist human annotators effectively
unless that model is trained with large datasets that include rare classes.
The encoder in the training phase of VPE encodes real images to latent
distribution and the decoder reconstructs the encoded distribution back to a
prototype that corresponds to the input image. By doing so, the trained
encoder is used as a feature extractor and VPE learns image similarity and
prototypical concepts instead of learning classification itself. Therefore,
the pre-trained model can predict novel classes that are unknown during the
training time.

#### Querying the Domain Knowledge Graph and Human Validation

Upon the final selection of a matching road sign prototype, the system queries
our domain specific knowledge graph to get relevant attributes needed for
annotation, such as a corresponding class name, class description, colors,
sign shape and text along with a coordinate of the bounding box.

##  6 Evaluation

This section provides experimental results to validate our assumption that the
knowledge graph and VPE model can reduce the number of sign templates which
the annotator has to search through to create ground truth.

###  6.1 Search Space Reduction with Road Sign Knowledge Graph

First we discuss the search space reduction from the knowledge graph alone.

#### Dataset Used in the Evaluation

Our first evaluation uses 51,000 frames of road scenes recorded from one of
front cameras mounted in our testing vehicles. The recorded frames cover
various cities in US. A total of 6,253 road signs instances are observed. 50
road sign classes are annotated in this dataset. Note that a road sign class
in this data model can have multiple sign templates if the meaning of signs
are the same in the application. For example, SPEED LIMIT 30 and SPEED LIMIT
50 have the same road sign class with a different value (30 and 50
respectively) for each sign. Some road signs that are not relevant to the
application are modeled as other classes.

#### Knowledge Graph Used in the Evaluation

The Road Sign Knowledge Graph constructed with 845 US federal MUTCD sign
templates are used for this experiment. We select only one sign template for
each class and run SPARQL queries. Common query parameters for all signs are
plate shape and background color. Shape within a sign, icon and text are used
optionally depending on the sign template.

#### Evaluation Results

To understand the distribution of signs on the graph, we run queries with
common parameters (shape and background color) on the graph database. The
query results show that 42% of signs have rectangle shape and white background
color, and 14% of signs have diamond shape and yellow background color.

We run 50 queries with common and optional query parameters to evaluate the
search space reduction for observed sign classes in our dataset. Table 1 shows
the distribution of the search space size range used from the evaluation. The
results show that the size of the search space is reduced by 98.9% (from 845
to a mean of 8.92 signs) on average when querying road signs with minimum 3
and maximum 5 attributes. The reduced number of road sign candidates should
decrease the efforts for the human annotator because the number of comparison
against a real sign is reduced proportionally.

Table 1: Search space reduction distribution

search space size | percentage(%) | mean | stdev
---|---|---|---
1 to 5 | 38% | 8.92 | 7.36
6 to 10 | 16%
11 to 15 | 20%
16 to 20 | 12%
21 to 25 | 14%

#### Training Time and Learning Curve

In addition, human annotators spend weeks to get trained on road sign
annotation for various countries to be able to make intelligent decisions when
they annotate signs that are different from provided road sign templates,
according to our interviews with annotation experts. Uncertainty in
classifying variants of similar road signs creates either failure in the
ground truth annotation or requires additional rigorous reviews relying on the
trained domain expert. Training time and learning curve can be improved by
increasing the number of road sign prototypes via crowd-sourced knowledge
graph construction.

###  6.2 Variational Prototyping-Encoder Model Accuracy with Respect to Search
Space Size

The VPE re-ranks the sign candidates filtered by the knowledge graph. Our
second hypothesis is that the accuracy of VPE can be improved with the reduced
number of candidate classes to the encoder during inference. This improvement
can further increase the efficiency of the human annotators by further
reducing the search space.

#### Datasets used in the Evaluation

We validate this hypothesis on two benchmark road sign datasets to evaluate
how the reduction of the search space from knowledge graph improves the
classification accuracy: 1) German Traffic Sign Recognition Benchmark
(GTSRB)[25], containing 43 classes of road signs used in Germany where they
adopt the Vienna convention. This dataset provides approximately 50,000
instances of image patches with sizes varying from 15x15 pixels to 250x250
pixels. The dataset also provides road sign template images. 2) LISA[21]
dataset, containing 47 US sign classes of 7,855 annotation from the Manual on
Uniform Traffic Control Devices (MUTCD) convention. The LISA dataset does not
contain the road sign template images; we used the road sign templates from
our Road Sign Knowledge Graph.

#### Training and Testing Process

We selected these datasets because significant differences in signs between
these two countries allow us to evaluate the effectiveness of our knowledge
graph in the VPE model when testing the model performance with road sign
classes not used during the training phase. We first trained VPE with the
GTSRB dataset. The input of the VPE model is cropped image patches from the
real road scenes and the output of the VPE model is the road sign template for
the correct class. The VPE learned image similarity represented in embedding
(vector size of 300) as well as prototypical concepts of the road sign during
the training phase.

10 signs classes having the diamond shape and the yellow background color in
the LISA dataset are used to test the performance by changing the number of
road sign templates to the pre-trained encoder. No signs in GTSRB have the
diamond shape and yellow background color. The performance covers unseen sign
classes with different features during the training time. The output of the
pre-trained encoder is the ranked list of road sign templates. We calculated
accuracy of top 1, top 3, and top 5 ranks (the ground truth template is listed
in top 1, top 3, and top 5 ranks).

#### Evaluation Results

The evaluation results shows that the accuracy of the model is increased by
10-13% when the search space size is reduced from 30 to 10 (See Table 2). The
results also demonstrate that the model predicts the ground truth template for
75% of the dataset when the search space size is 10. In these cases, the human
annotator would not need to spend any time searching for a matching sign, thus
further reducing annotation effort.

Table 2: VPE Performance Evaluation with Different Search Spaces Tested with
Signs having Diamond Shape and Yellow Background Color

search space size s accuracy (top-1) accuracy
(top-3) accuracy
(top-5) 10 0.73 0.85 0.90 20 0.69 0.80 0.85 30 0.60 0.73 0.80

##  7 Conclusion

We proposed to use Road Sign Knowledge Graph for the data annotation tool for
road sign annotation along with a meta-learning model. The ontology model for
the road signs is intended to map to various domains and applications. We
demonstrate that the construction of the Road Sign Knowledge Graph can be made
scalable for signs across states and countries by using a crowd-sourcing
approach. The evaluation results show that the search space for human
annotators can be reduced by 98.9%, from a palette of 845 signs to only 8.92
signs, reducing human effort and easing the learning curve for road sign
classification. Furthermore, the results show that integrating machine
learning with the knowledge graph can produce an exact match for 75% of signs,
eliminating human classification effort entirely in those cases.

## References

  * [1] Amazon Mechanical Turk.  https://mturk.com.  Accessed May 2020.
  * [2] ClickWorker.  https://www.clickworker.com.  Accessed May 2020.
  * [3] Regulation (EU) 2019/2144 of the European Parliament and of the Council.  https://eur-lex.europa.eu/eli/reg/2019/2144/oj.  Accessed May 2020.
  * [4] South African Road Traffic Signs Manual.  https://www.transport.gov.za/.  Accessed June 2020.
  * [5] UpWork.  https://www.upwork.com/.  Accessed May 2020.
  * [6] Rachid Belaroussi, Philippe Foucher, Jean-Philippe Tarel, Bahman Soheilian, Pierre Charbonnier, and Nicolas Paparoditis.  Road sign detection in images: A case study.  In 20th International Conference on Pattern Recognition, pages 484–488. IEEE, 2010.
  * [7] Ahmad C Bukhari, Mate Levente Nagy, Michael Krauthammer, Paolo Ciccarese, and Christopher JO Baker.  Bim: an open ontology for the annotation of biomedical images.  In ICBO, 2015.
  * [8] Xu Chu, John Morcos, Ihab F Ilyas, Mourad Ouzzani, Paolo Papotti, Nan Tang, and Yin Ye.  Katara: A data cleaning system powered by knowledge bases and crowdsourcing.  In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2015.
  * [9] Inland Transport Committee et al.  Convention on Road Traffic.  Economic Commission for Europe, Vienna, Austria, 1968.
  * [10] Taylor G Cowan.  Jenabean: Easily bind javabeans to rdf.  IBM DeveloperWorks, 2008.
  * [11] Milan Dojchinovski, Dinesh Reddy, Tomáš Kliegr, Tomáš Vitvar, and Harald Sack.  Crowdsourced corpus with entity salience annotations.  In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16), 2016.
  * [12] United Nations. Economic Commission for Europe. Transport Division.  Convention on Road Traffic of 1968 and European Agreement Supplementing the Convention (2006 Consolidated Versions).  2007\.
  * [13] Pascal Hitzler, Markus Krötzsch, Bijan Parsia, Peter F Patel-Schneider, Sebastian Rudolph, et al.  OWL 2 web ontology language primer.  W3C recommendation, 27(1):123, 2009.
  * [14] Brendan Jou, Tao Chen, Nikolaos Pappas, Miriam Redi, Mercan Topkara, and Shih-Fu Chang.  Visual affect around the world: A large-scale multilingual visual sentiment ontology.  In Proceedings of the 23rd ACM international conference on Multimedia, pages 159–168, 2015.
  * [15] Michael Kampffmeyer, Yinbo Chen, Xiaodan Liang, Hao Wang, Yujia Zhang, and Eric P Xing.  Rethinking knowledge graph propagation for zero-shot learning.  In IEEE Conference on Computer Vision and Pattern Recognition, 2019\.
  * [16] Junsik Kim, Tae-Hyun Oh, Seokju Lee, Fei Pan, and In So Kweon.  Variational prototyping-encoder: One-shot learning with prototypical images.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [17] Fredrik Larsson and Michael Felsberg.  Using Fourier descriptors and spatial models for traffic sign recognition.  In Scandinavian conference on image analysis, pages 238–249. Springer, 2011.
  * [18] Luis David Lopez and Olac Fuentes.  Color-based road sign detection and tracking.  In International Conference Image Analysis and Recognition, pages 1138–1147. Springer, 2007.
  * [19] Gareth Loy and Nick Barnes.  Fast shape-based road sign detection for a driver assistance system.  In 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 70–75. IEEE, 2004.
  * [20] Rabia Malik, Javaid Khurshid, and Sana Nazir Ahmad.  Road sign detection and recognition using colour segmentation, shape analysis and template matching.  In 2007 International Conference on Machine Learning and Cybernetics, volume 6, pages 3556–3560. IEEE, 2007.
  * [21] Andreas Mogelmose, Mohan Manubhai Trivedi, and Thomas B Moeslund.  Vision-based traffic sign detection and analysis for intelligent driver assistance systems: Perspectives and survey.  IEEE Transactions on Intelligent Transportation Systems, 13(4):1484–1497, 2012.
  * [22] Mark A Musen.  The protégé project: a look back and a look forward.  AI matters, 1(4):4–12, 2015.
  * [23] Texas MUTCD.  Manual on uniform traffic control devices.  Texas Department of Transportation, Austin, 2006.
  * [24] Elena Simperl, Jens Lehmann, Maribel Acosta, Amrapali Zaveri, Dimitris Kontokostas, and Sören Auer.  Crowdsourcing linked data quality assessment.  In International Semantic Web Conference, Oktober 2013.
  * [25] Johannes Stallkamp, Marc Schlipsing, Jan Salmen, and Christian Igel.  The german traffic sign recognition benchmark: a multi-class classification competition.  In Int. joint conference on neural networks, 2011.
  * [26] Radu Timofte, Karel Zimmermann, and Luc Van Gool.  Multi-view traffic sign detection, recognition, and 3D localisation.  Machine vision and applications, 25(3):633–647, 2014.
  * [27] Shichao Zhou, Chenwei Deng, Zhengquan Piao, and Baojun Zhao.  Few-shot traffic sign recognition with clustering inductive bias and random neural network.  Pattern Recognition, page 107160, 2019.
  * [28] Zhe Zhu, Dun Liang, Songhai Zhang, Xiaolei Huang, Baoli Li, and Shimin Hu.  Traffic-sign detection and classification in the wild.  In IEEE conference on computer vision and pattern recognition (CVPR), 2016.