# Multipath agents
for modular multitask ML systems

Andrea Gesmundo
Google Research
<EMAIL_ADDRESS>

###### Abstract

A standard ML model is commonly generated by a single method that specifies
aspects such as architecture, initialization, training data and
hyperparameters configuration. The presented work introduces a novel
methodology allowing to define multiple methods as distinct agents. Agents can
collaborate and compete to generate and improve ML models for a given tasks.
The proposed methodology is demonstrated with the generation and extension of
a _dynamic modular multitask ML system_ solving more than one hundred image
classification tasks. Diverse agents can compete to produce the best
performing model for a task by reusing the modules introduced to the system by
competing agents. The presented work focuses on the study of agents capable
of: 1) reusing the modules generated by concurrent agents, 2) activating in
parallel multiple modules in a frozen state by connecting them with trainable
modules, 3) condition the activation mixture on each data sample by using a
trainable router module. We demonstrate that this simple per-sample parallel
routing method can boost the quality of the combined solutions by training a
fraction of the activated parameters.

##  1 Introduction

This work extends the $\mu$Net line of research (Gesmundo & Dean, 2022a; b;
Gesmundo, 2022a; b). This line of research aims to define and demonstrate
novel methodologies to enable the creation of dynamic large-scale multi-modal
multitask modular intelligent systems that can be indefinitely and
collaboratively extended. Such intelligent systems can accelerate and automate
Machine Learning (ML) development and innovation by enabling higher quality
solutions with higher efficiency/automation and lower the entry barrier for
less specialized users.

This work demonstrates the _method heterogeneity_ and _collaborative ML
development_ capabilities enabled by the _multiagent framework_ introduce by
Gesmundo (2022b). The use of collaborative agents is demonstrated by applying
the _continual development methodology_ (Gesmundo, 2022a) to extend the
$\mu$3Net system (Gesmundo, 2022b). The $\mu$3Net system is a multitask system
solving jointly 124 image classification tasks. This system is composed by a
set of modules/components and a set of models/paths. Different paths can share
modules. Each path connects a subset of modules to define a model for a task.
Such models/paths are generated by multiple installations of a _singlepath
agent_ (i.e. one instantiation per task). This publication describes the
extension of such system into a “Mutant Multiagent Multipath Multitask
Network” ($\mu$4Net). $\mu$4Net introduces a novel _multipath agent_ capable
of generating architectures activating multiple parallel paths. The multipath
agent can be instantiated by specifying an assigned task. Each multipath agent
combines available models/paths in a frozen state (i.e. with no additional
training). The frozen paths are connected with trainable connector modules.
Furthermore, the aggregation of the representations generated by the parallel
paths is controlled by a router module. The router learns to weigh the
activated paths conditioning on features of each input sample.

The following sections define the method implemented by the multipath agent,
and report an empirical study aimed to analyze the properties and motivate the
novel design elements.

##  2 Method

This section details the method implemented by the proposed multipath agent.

###  2.1 Multipath architecture

Figure 1:  Representation of an exemplar architecture generated by a
_multipath agent_ within a _modular multitask system_ solving 3 tasks. Each
task is assigned to an instance of a singlepath agent. Each singlepath agent
generates a path/model solving the assigned task. Paths can share
modules/knowledge if beneficial. An additional multipath agent generates an
improved solution for Task 1 by augmenting the logits produced by the path
solving Task 1 (_main path_). The main logits are augmented with the
representations produced by support paths. The support representations are
mapped into the target logits space by using connector modules. The
aggregation of the logits is performed by a per-sample router conditioned on
the main path logits. The multipath agent cannot alter the activated paths and
can train only the router and connectors modules.

The proposed multipath agent generates architectures designed to provide an
effective way to boost the quality achieved by the model/path generated by the
singlepath agent solving the same task. Figure 1 represents the type of
multipath architectures generated by the multipath agent. These multipath
architectures are composed by:

  1. 1.

_Main path_. The main path is the model generated by the singlepath agent
solving the same task. The main path is used in a frozen state (i.e. cannot be
altered during the evolution or training of the multipath structures).

  2. 2.

_Support paths_. An arbitrary number of additional paths can be activated in
parallel to improve the main path. Support paths are also used in a frozen
state. In general, the only requirement for support paths is to be capable of
processing the input samples provided by the target task. In the application
considered (i.e. extension of the $\mu$3Net system), all the existing paths
solve image classification tasks. Thus any path in the system can be used as a
support path with minimal pre-processing adaptations (i.e. image resizing).

  3. 3.

_Connector modules_. The representation produced by each support path provides
additional information to improve the main model/path. In general, this
additional information can be used to augment any internal representation of
the main model. In the instantiation presented, the support representations
are used to improve the logits of the main path ($\mu$3Net solves jointly 124
image classification tasks each with different label set). Trainable
connectors modules are used to map the representation produced by each support
path into the logits space of the target task. Therefore, connectors are
required to change the shape of the representation tensor and map its
semantic. In the proposed instantiation, the connector modules are implemented
as a single fully connected layer (FCL). The connectors are zero initialized.
Therefore, the output of the multipath models is initially determined only by
the main path, as the initialized connectors output zeros.

  4. 4.

_Router module_. The logits produced by the main path are aggregated with the
logits produced by the connected support paths. The aggregation is performed
by a weighted average of the different logits tensors. The weights are
provided by a trainable router module. The weights are sample specific. Per-
sample weighting can grant more influence to paths providing specialized
knowledge relevant to each example. The router needs to be conditioned on the
input sample to be able to produce per-sample weights. In general, any
representation of the input sample can be used. In the proposed instantiation,
the router is conditioned on the main path logits. The router is also
implemented as a single fully connected layer. A softmax is applied to the
output of the FCL to produce normalized weights. All the parameters of the
router’s FCL are zero initialized except for the bias value corresponding to
the main path weight, that is set to impose a prior over the main path weight,
as detailed in Section 2.1.1. Furthermore, the routing weights are applied
only during the forward pass, while gradients are computed as if the logits
are aggregated with a sum as detailed and motivated in Section 2.1.2

Many multipath agents can be executed in parallel and asynchronously, each
assigned to a distinct target task. The use of a path can be shared across
many multipath architectures as the paths are always used in a frozen state.
Notice that the implementation of such multipath architecture can be rendered
efficient by caching the representations produced by the paths (i.e. each
input is always mapped to the same representation as single paths are frozen).
Furthermore the execution of a support path can be skipped if the router
produces a weight close to zero for its representation (i.e. in this case, the
representation can be replaced with zero padding, as it would not be a
relevant factor of the aggregation).

Figure 2:  Graph representing $\mu$3Net (Gesmundo, 2022b) with an additional
multipath structure (highlighted with black edges) providing an improved
solution for the imagenet2012 task. The single path model achieve 86.66% test
accuracy while the multipath model achieves 87.39% by training only 3 fully
connected layers (i.e. 1 for the router and 2 for the connector modules). This
multipath model leverages the representation generated by the paths trained on
the tasks i_naturalist2017 and imagenet_a. Each task is identified with a
unique color. Top rectangular nodes represent the head module of each task.
Each sequence of edges of the same color defines the sequence of modules
composing each model. Internal nodes are represented with the color of the
task on which the parameters of the corresponding module were fine-tuned last.
Input nodes of highlighted paths report the correspondent task name. Input
nodes of non-highlighted paths are omitted.

####  2.1.1 Router bias initialization

This section describes the technique used to initialize the parameters of the
router’s FCL in order to achieve the following properties:

  1. 1.

Set the initial routing weight assigned to the main path to:
${w_{main}^{*}\in[0,1]}$.

  2. 2.

Distributes the remaining weight uniformly across the support paths:
${w_{support_{n}}=(1-w_{main}^{*})/{(|\mathcal{P}|-1)}}$, where $\mathcal{P}$
is the set of activated paths (i.e. main path $\cup$ support paths) and
${n\in[1,|\mathcal{P}\\!-\\!\\{main\\}|]}$.

The initialization method proposed in this section guarantees these properties
to be valid for the initialized state of any multipath architecture,
regardless of the number of activated support paths.

These properties are achieved by zero initializing all the parameters of the
router’s FCL with exception of the bias value corresponding to the main path,
which needs to be set to:

$b_{main}^{init}=\ln\left(\frac{1}{(\frac{1}{w_{main}^{*}}-1)}\cdot(|\mathcal{P}|-1)\right)$
(1)

###### Proof.

The computation producing the routing weights can be expressed as:

$\mathbf{w}:=\left|\begin{array}[]{c}w_{main}\\\ w_{support_{1}}\\\ \vdots\\\
w_{support_{|\mathcal{P}|-1}}\end{array}\right|=softmax(W\cdot\mathbf{x}+\mathbf{b})$

Where $\mathbf{x}$ is the tensor inputted to the router’s FCL, $\mathbf{b}$ is
the bias vector of the router’s FCL, and $W$ is the parameters matrix of its
kernel. Considering that $W$ is zero initialized, the initial state of the
routing weights is simplified to:
$\mathbf{w}^{init}=softmax(\mathbf{b}^{init})$. By applying the softmax
formula, the initial value of $w_{main}$ results:

$w_{main}^{init}=\frac{e^{b_{main}^{init}}}{e^{b_{main}^{init}}+\sum_{n=1}^{|\mathcal{P}|-1}e^{b_{support_{n}}^{init}}}$
(2)

Considering that all the bias values corresponding to support paths are zero
initialized (i.e. ${b_{support_{n}}^{init}\\!=0\ \ \forall\
n\in[1,|\mathcal{P}\\!-\\!\\{main\\}|]}$):

$w_{main}^{init}=\frac{e^{b_{main}^{init}}}{e^{b_{main}^{init}}+|\mathcal{P}|-1}$
(3)

Finally, $b_{main}^{init}$ can be substituted by applying equation (1):

$w_{main}^{init}\\!=\\!\frac{\left(\frac{1}{(\frac{1}{w_{main}^{*}}-1)}\cdot(|\mathcal{P}|\\!-\\!1)\right)}{\left(\frac{1}{(\frac{1}{w_{main}^{*}}-1)}\cdot(|\mathcal{P}|\\!-\\!1)\right)+|\mathcal{P}|\\!-\\!1}\\!=\\!\frac{\frac{1}{(\frac{1}{w_{main}^{*}}-1)}}{\frac{1}{(\frac{1}{w_{main}^{*}}-1)}+1}\\!=\\!\frac{1}{1+(\frac{1}{w_{main}^{*}}-1)}\\!=\\!w_{main}^{*}$
(4)

Also the initial routing weight of support paths matches with the stated
properties, $\forall n\in[1,|\mathcal{P}|-1]$:

$w_{support_{n}}^{init}\\!\\!=\\!\frac{e^{b_{support_{n}}^{init}}}{e^{b_{main}^{init}}\\!+\\!\sum_{n=1}^{|\mathcal{P}|-1}e^{b_{support_{n}}^{init}}}\\!=\\!\frac{\frac{1}{|\mathcal{P}|-1}}{\frac{1}{(\frac{1}{w_{main}^{*}}-1)}\\!+\\!1}\\!=\\!\frac{\frac{1}{|\mathcal{P}|-1}}{\frac{\frac{1}{w_{main}^{*}}}{\frac{1}{w_{main}^{*}}-1}}\\!=\\!\frac{\frac{1}{|\mathcal{P}|-1}}{\frac{1}{1-w_{main}^{*}}}\\!=\\!\frac{1\\!-\\!w_{main}^{*}}{|\mathcal{P}|-1}\vspace{8pt}$
(5)

∎

During preliminary experiments, we have observed that initializing with a
higher $w_{main}^{*}$ can have two visible effects:

  1. 1.

The quality of an initialized multipath model matches of the quality achieved
by the frozen main path (also considering that connectors are zero
initialized). The higher $w_{main}^{*}$ is set the less likely it is that the
quality of the multipath model drops below the main path quality during
training. Conversely, a too high $w_{main}^{*}$ can slow the learning of the
routing patterns required to leverage the additional information provided by
the support paths.

  2. 2.

Faster converge of the multipath model training. This finding matches with the
main design intuition as the main path is expected to be the most influential
in average. In fact, the value used in the following experiments is set to a
value within the range that have been measured at convergence of preliminary
experiments: ${w_{main}^{*}\\!=80\%}$.

####  2.1.2 Backprop decoupled routing

In general, routing methods rely on the aggregation of alternative
representations produced by different modules or experts. A common application
of this design pattern are mixture of experts architectures (Shazeer et al.,
2017). The routers are usually trained jointly with the modules whose output
is aggregated. During the forward pass, the routing weights are applied to
select the most relevant representation/module. The weighting has also the
effect of scaling the gradients that modules received during backward
propagation (i.e. assigning a low weight to a module will results in
proportionally diminished gradients). Thus, routers tend to produce
distributions that are excessively skewed toward a few modules that perform
better during early training. In practice, the training of unselected modules
grinds to a halt because their gradients vanishes as the “quality” gap with
respect to the trained modules increases. Thus, routing methods can often
suffer from load balance issues and suboptimal quality. This common issue has
be referred to as the _rich gets richer_ effect (Shen et al., 2019). This
effect is more accentuated for the proposed multipath method, because the main
path is initialized with a converged model, while the support paths require
training of the connector. Common solutions rely on auxiliary loss factors
such as _entropy regularization_ of the routing weights distribution to reduce
its skewness. Such solutions add complexity as additional logic is required to
gather and propagate through the network the information needed for the
auxiliary loss factors computation. Furthermore, auxiliary loss factors
require to tune additional hyperparameters such as the scaling parameters.

In this section we introduce an alternative solution that does not require
additional hyperparameters and can be defined and implemented within the
weighted aggregation logic. The proposed technique is based on applying
different aggregations for the forward pass and backward pass.

The standard router weighted aggregation can be represented as:

$\mathbf{a}=R\cdot\mathbf{w}=\left|\begin{array}[]{c}\mathbf{r}_{1}\\\
\vdots\\\ \mathbf{r}_{M}\end{array}\right|\cdot\mathbf{w}$ (6)

Where $\mathbf{w}$ is the vector of routing weights, $M$ is the number of
modules whose representations are being aggregated, $\mathbf{r}_{i}$ denotes
each representation, and $R$ represents the matrix obtained by stacking the
representations. The proposed technique consists in applying the standard
aggregation during the forward propagation but applying an unweighted
aggregation during the backward propagation:

$\mathbf{a}_{backprop}=\left|\begin{array}[]{c}\mathbf{r}_{1}\\\ \vdots\\\
\mathbf{r}_{M}\end{array}\right|\cdot\mathbf{1}$ (7)

Notice that this allows the modules to receive unscaled gradients,
independently from the selection choice of the router. This property is
particularly critical for the instantiation of the multipath method proposed,
as the connectors can be trained even if the router naturally tends to
converge to select the main path during early training.

Let $stopgradient(\cdot)$ represent a function that acts as the identity
function during the forward propagation but stops the flow of gradients during
the backward propagation:

$stopgradient(x)=\begin{cases}x,\ \ \ \text{if forward propagation}\\\ 0,\ \ \
\text{if backward propagation}\end{cases}$ (8)

The forward and backward propagation formulas (6 and 7) can be represented
jointly by using the ${stopgradient(\cdot)}$ function:

$\mathbf{a}_{joint}=stopgradient(R)\cdot\mathbf{w}+R\cdot\mathbf{1}-stopgradient(R\cdot\mathbf{1})$
(9)

During the forward propagation: ${\mathbf{a}_{joint}=R\cdot\mathbf{w}}$, since
$stopgradient(\cdot)$ has no effect in this phase and the remaining two
factors cancel out: ${(R\cdot\mathbf{1}-stopgradient(R\cdot\mathbf{1}))=0}$.
While, during the backward propagation, the modules receive gradients only
through the factor ${R\cdot\mathbf{1}}$, that is unaffected by the routing
weights. Notice that the router is still trained following the standard
aggregation formula (6) as the router receives gradients only through the
factor: ${stopgradient(R)\cdot\mathbf{w}}$.

Notice that, the used formulation does not allow the modules to specialize on
the subset of samples for which the router selects them with higher weight.
For applications where specialization may be more important, it is possible to
define alternative solutions based on the same backprop decoupling intuition.
For example:

$\mathbf{a}^{\prime}_{backprop}=\left|\begin{array}[]{c}\mathbf{r}_{1}\\\
\vdots\\\
\mathbf{r}_{M}\end{array}\right|\cdot\left|\begin{array}[]{c}w_{1}/EM\\!A(w_{1})\\\
\vdots\\\ w_{N}/EM\\!A(w_{N})\end{array}\right|$ (10)

Where each weight is scaled by its exponential moving average:
$EM\\!A(\cdot)$. Notice that this solution still avoids the _rich gets richer_
effect, since $\mathbb{E}[w_{i}/EM\\!A(w_{i})]\cong 1$ even if
$\mathbb{E}[w_{i}]\rightarrow 0$.

####  2.1.3 Router learning rate multiplier

The learning rate applied to the router module is allowed to be set
independently from the global learning rate applied to the other components.
This is parametrized by adding a new hyperparameter: _router learning rate
multiplier_. This hyperparameter determines the learning rate applied to the
router by scaling the global learning rate:

$learning\mbox{-}rate_{router}=\lambda\cdot learning\mbox{-}rate$ (11)

Where $\lambda$ represents the router learning rate multiplier hyperparamter.
This multiplicative formalization allows for a learning rate scaling
implementation that is self-contained within the router module by using the
$stopgradient(\cdot)$ function:

$\mathbf{o}_{grad\mbox{-}scaled}=\lambda\cdot\mathbf{o}+(1-\lambda)\cdot
stopgradient(\mathbf{o})$ (12)

Where $\mathbf{o}$ represents the output tensor of the router module. During
the forward pass: ${\mathbf{o}_{grad\mbox{-}scaled}=\mathbf{o}\ \ \ \forall\ \
\lambda\in\mathbb{R}}$. While, during the backward propagation, the gradients
applied are scaled by $\lambda$ as:
${\mathbf{o}_{grad\mbox{-}scaled}=\lambda\cdot\mathbf{o}}$.

The incremental auto-tuning method (Gesmundo & Dean, 2022a) can be applied
also to $\lambda$. The need for a distinct learning rate for the router and
its default value and auto-tuning range have been identified during
preliminary experiments (see Table 1).

Notice that, the presented modular learning rate scaling technique is
generally applicable to any module, as the logic expressed by equation (12)
can be applied to the output of any module. For example it can be applied to
modules of the models generated by the singlepath agent to scale the learning
rate of each module independently.

###  2.2 Multipath models sampling

In this section we define the method used to sample multipath models. This
sampling method is intentionally designed to be as similar as possible to the
singlepath agent’s model sampling (Gesmundo, 2022b), in order to demonstrate
its generality and allow for a fair comparison. In this section we give a
summary of the method, for further details refer to prior work and published
code.

####  2.2.1 Parent model selection

New multipath models are sampled by mutation. We refer to the model being
mutated as the _parent model_. The agent attempts to sample the parent model
from a set of multipath models previously sampled and scored by the same
agent. We refer to this set of candidate parent models as the _population_.
The models in the population are visited in decreasing order of score,
starting with the highest scoring one. Each model, $m$, can be accepted as
parent at random with probability:

$p_{parent}(m)=0.5^{\\#of\\!fsprings(m)}$ (13)

Where $\\#of\\!fsprings(m)$ denotes the number models that have been
previously generated by using $m$ as parent. If the current candidate parent
is not selected, then iteratively the model with the next best score is
considered to be selected as parent with probability $p_{parent}(\cdot)$. If a
full iteration on the population is completed without a successful parent
model selection (i.e. the population is empty or all candidates are rejected),
then a _randomly initialized multipath model_ is used as parent. This random
model is sampled as follow:

  1. 1.

its hyperparameters are copied from the configuration of the highest scoring
model in the population. If the population is empty, then the hyperparameters
are set to the default values (see Table 1).

  2. 2.

its support paths are uniformly sampled without replacement from the set of
the single paths available in the system.

  3. 3.

the connectors are zero initialized and the router is initialized with the
bias initialization technique defined in Section 2.1.1.

Table 1:  Hyperparameters search space. Sequences of valid values for each
automatically tunable hyperparameter. Bold values are defaults. Underlined
values highlight the differences with the search space used by the single path
agent (Gesmundo, 2022a). The image resolution cannot be tuned by the multipath
agent, since each activated path is used in a frozen state and needs to be
provided with an image resolution matching its configuration. An additional
hyperparameter has been added to scale the learning rate applied to the router
module. _Optimizer hyperparameters_
---
Learning rate $\in$ [0.0001, 0.0002, 0.0005, 0.001, 0.002, 0.005, 0.01, 0.02,
0.05, 0.1, 0.2, 0.5]
Learning rate schedule warm up ratio $\in$ [0, 0.01, 0.02, 0.05, 0.1, 0.2,
0.3]
Momentum $\in$ [0.5, 0.6, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95, 0.98, 0.99]
Nesterov update $\in$ [False, True]
Router learning rate multiplier $\in$ [0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1]
_Data Preprocessing hyperparameters_
Cropped area range min $\in$ [0.05, 0.5, 0.95, 1.0]
Cropped aspect ratio range min $\in$ [0.5, 0.75, 1.0]
Flip left/right $\in$ [False, True]
Brightness delta $\in$ [0.0, 0.01, 0.02, 0.05, 0.1, 0.2]
Contrast delta $\in$ [0.0, 0.01, 0.02, 0.05, 0.1, 0.2]
Saturation delta $\in$ [0.0, 0.01, 0.02, 0.05, 0.1, 0.2]
Hue delta $\in$ [0.0, 0.01, 0.02, 0.05, 0.1, 0.2]
Image quality delta $\in$ [0.0, 0.01, 0.02, 0.05, 0.1, 0.2]
Image resolution pixels $\in$ [224, 384]

####  2.2.2 Model mutation

Two types of model mutations are available:

  1. 1.

_Hyperparameter mutation_. Hyperparameters of the optimizer and preprocessing
can be mutated. The hyperparameter set and their value defaults and ranges is
equivalent to the one used by the singlepath agent (Gesmundo, 2022a) with 2
exceptions: 1) image resolution tuning is disabled since each activated path
is used in a frozen state and needs to be provided with an image with
resolution matching its training configuration. 2) an additional optimizer
hyperparameter has been added to scale the learning rate applied to the router
module. The hyperparameters value changes are sampled by using the same
_incremental hyperparameter mutation_ technique used by the singlepath agent
(Gesmundo & Dean, 2022a). The default value and auto-tuning range of the
_router learning rate multiplier_ have been identified during preliminary
experiments. The default values for each of the remaining hyperparameters is
set to the most frequently used value by the models included in the $\mu$3Net
system (see Gesmundo (2022b) Figure 6).

  2. 2.

_Support path mutation_. The set of support paths used by the parent model can
be altered by adding or removing one support path. If a support path is added,
then a new single path is sampled (avoiding duplicates) and a new zero-
initialized connector module is added. If a support path is removed, then its
connector is removed and the number of activated support paths is reduced by
one. In both cases the parameters of the router are reset. Any trainable
component inherited from the parent model is cloned in order to guarantee
immutability of the pre-existing models (equivalent to the layer cloning
mutation used by singlepath agents Gesmundo (2022a)). For the experiments
described in this paper, the default number of used paths is 2 and the maximum
is 3.

The selected parent model can be mapped to a newly sampled multipath model by
applying a subset of the possible mutation actions. Any candidate mutation is
selected for application with probability $\mu(\delta|m)$, where $\delta$
represents the candidate mutation, $m$ is the parent model, and $\mu(\cdot)$
is the learned $\mu$ function as defined in Gesmundo (2022a).

####  2.2.3 Evolutionary cycles

The logic of the evolutionary cycles and the specific configuration used in
the following experiments matches the logic used by the singlepath agent
(Gesmundo, 2022b).

Each multipath agent searches for the best scoring architecture by performing
evolutionary cycles. At the end of each cycle only the best scoring model is
retained in the system and evaluated on the test set, while other models are
discarded. During each cycle, 16 models are sampled with the method described
in Section 2.2. Each agent samples and trains 4 models in parallel. Each model
is trained on one of the 4 TPUv4 MegaCore chips available. During training,
the model is evaluated on the validation set 4 times at regular intervals. The
quality measured on the validation set is used as score. Only the checkpoint
corresponding to the intermediate evaluation achieving the best score is
retained. The scored models are then inserted in the agent’s population,
$\mathcal{P}$, to be used as candidate parent and possibly become the new best
scoring model. Early population pruning is performed by discarding the models
that did not achieve a better score than their parent (Gesmundo & Dean,
2022a).

Table 2:  Comparison between the quality achieved by the proposed multipath agent and alternative methods on the imagenet2012 task. Both the validation accuracy (used as score by the $\mu$Net agents) and the test accuracy (computed on a held-out dataset) are reported. Each multipath agent experiment is repeated 10 times and lasts 15 evolutionary cycles. The mean of the 10 accuracies and its standard error (s.e.m.) is reported for each multiagent experiment. The maximum of the 10 test accuracies is also reported. As baselines, the mean test accuracy achieved by Dosovitskiy et al. (2021) with 3 fine-tuning repetitions of a ViT Large model matching pretraining and size of the $\mu$Net root model is reported. For the singlepath agent baseline, the accuracy achieved by the path included in the $\mu$3Net version of the system is reported in the “mean” column, while the best test accuracy recorded through the whole history of the $\mu$Net system is reported in the “max” column. The _Ablation study_ and _Headroom analysis_ sections report results achieved by modifications of the multipath agent method as described in Sections 3.2 and 3.3. For each set of ablation and headroom experiments, the significance of the test accuracy deltas achieved with respect to the unmodified multipath agent is measured as _p_ -value computed with the _independent two-sample t-test_. with respect to the multipath agent experiment repetitions. Plots representing the change over time of these metrics are reported in Figure 3. Results are discussed in Section 3.  Method | Validation acc. (%) | Test accuracy (%)
---|---|---
| mean $\pm$s.e.m. | mean $\pm$s.e.m. | max |  _p_ -value
Multipath agent | 79.25 $\pm$0.05 | 87.19 $\pm$0.03 | 87.29 |
_Baseline methods_
ViT Large fine-tuning |  | 85.30 $\pm$0.01 |  |
Singlepath agent | 78.54 | 86.66 | 86.74 |
_Multipath agent: Ablation study_
Ablate backprop decoupled routing | 78.65 $\pm$0.02 | 86.72 $\pm$0.03 | 87.00 | 6.3$\\!\times\\!$10${}^{\text{-}9}$
Ablate router learning rate scaling | 78.79 $\pm$0.01 | 86.81 $\pm$0.03 | 86.96 | 9.1$\\!\times\\!$10${}^{\text{-}8}$
Ablate per-sample routing | 79.00 $\pm$0.04 | 87.11 $\pm$0.04 | 87.28 | 0.13
Ablate router bias initialization | 79.19 $\pm$0.04 | 87.12 $\pm$0.04 | 87.27 | 0.22
_Multipath agent: Headroom analysis_
Force i_naturalist2017 selection | 79.33 $\pm$0.02 | 87.26 $\pm$0.03 | 87.39 | 0.08

##  3 Experiments

This section reports an empirical study of the proposed multipath agent. In
all the experiments reported, the proposed method is applied to extend the
$\mu$3Net system (Gesmundo, 2022b). As benchmark we use the imagenet2012 task
(Russakovsky et al., 2015). This task has been introduced in the $\mu$Net
system with a singlepath method by Gesmundo & Dean (2022b). Imagenet2012 has
been chosen for the multipath agent study because: 1) it has the biggest
headroom compared to state-of-the-art among the 124 tasks solved by the
$\mu$3Net system, 2) the models setting the stat-of-the-art for this task are
significantly bigger than the singlepath models currently constituting the
$\mu$3Net system. Therefore, quality gains can be expected on this benchmark
by leveraging more parameters and knowledge.

The “ _repetitions on independent system replicas_ ” method (introduced in
Section 5.3 of Gesmundo & Dean (2022b)) is employed to measure the variance of
the reported metrics. Each multipath agent experiment reported is repeated 10
times. Each repetition is executed on an independent copy of the $\mu$3Net
system. Metrics are reported as average aggregated across the 10 repetitions
paired with the standard error of the mean. Each experiment performs 15
evolutionary cycles. To accelerate convergence, the search space is restricted
by excluding from the set of candidate support paths the models trained on
VTAB-1k tasks (Zhai et al., 2019), as paths trained on corresponding VTAB-full
tasks can provide a strictly more informative representation.

All the experiments can be reproduced by using the published
artefacts111Source-code of the multipath agent and checkpoints of different
versions of the $\mu$Net system are available at
https://github.com/google-research/google-research/tree/master/muNet: a) the
multipath agent code, b) $\mu$3Net checkpoint, c) tasks from the Tensorflow
datesets catalog.

Methods comparison on the imagenet2012 benchmark

Validation accuracy

Test accuracy

Figure 3:  Comparison of the validation and test accuracies achieved
throughout the evolutionary process by the variations of the multipath agent
method described in Section 3. Each curve represents the accuracy averaged
across the 10 experiment repetitions executing the corresponding multipath
method variation. The shaded area represents the standard error of the mean.
The accuracy achieved by the singlepath agent is displayed as an horizontal
line for reference. Numerical values of the accuracies achieved at the
completion of the $15^{th}$ evolutionary cycle are reported in Table 2.
Results are discussed in Section 3.

###  3.1 Baseline methods

The quality achieved by the proposed multipath agent on the imagenet2012
benchmark are reported in Table 2 and Figure 3. The achieved average test
accuracy of 87.19% can be considered significantly higher than the average
test accuracy of 85.30% (Dosovitskiy et al., 2021) achieved by fine-tuning a
ViT Large model equivalent to the root model used by $\mu$Net system (Gesmundo
& Dean, 2022b).

Quality gains are also achieved against the singlepath model for imagenet2012
that is part of the $\mu$3Net system: 86.66% (Gesmundo, 2022b). Notice that
this is the path used as _main path_ for the architectures generated by the
multipath agent.

###  3.2 Ablation study

The proposed multipath agent method is characterize by particular design
elements:

  1. 1.

Per-sample routing (see Section 2.1).

  2. 2.

Router bias initialization (see Section 2.1.1).

  3. 3.

Backprop decoupled routing (see Section 2.1.2).

  4. 4.

Router learning rate scaling (see Section 2.1.3).

Section 2 introduces the motivating intuitions for each of these design
elements. During the development phase, quality gains have been measured for
each design element with preliminary experiments. In this section, we validate
the findings with reproducible experiments. Each experiment ablates one of the
design elements to measure its impact on convergence speed and quality
achieved within the training budget of 15 evolutionary cycles.

####  3.2.1 Ablate backprop decoupled routing

The backward propagation decoupled routing method has been introduced as a
solution to the _rich gets richer_ effect (see Section 2.1.2). In the context
of the proposed method, this effect causes the router to early converge to
select exclusively the main path, thus preventing the support paths from
training. Therefore, disabling this design element is expected to result in
the quality of the multipath models to converge to the quality of the main
path in most cases.

This ablation is performed by replacing the _backprop decoupled routing_
(equation 9) the standard router weighted aggregation (equation 6). Note that,
the forward pass and gradient computation of the router are unaltered by this
ablation, only the backward pass of the connector modules is altered.

Table 2 and Figure 3 report the results. 8 out of the 10 replicas collapse to
selecting exclusively the main path, thus resulting into an test accuracy
equivalent to that of the main path: $\in$[86.65%, 86.68%]. Only two
repetitions avoid the collapse effect and achieve a higher test accuracy:
87.00% and 86.80%.

We propose the _backprop decouple routing_ solution as it is compatible with
the modular nature of the methodology developed by the $\mu$Net line of
research (see Section 2.1.2). Such modularity is not provided by the common
solutions to _router early convergence_ issues such as auxiliary loss factors.

####  3.2.2 Ablate per-sample routing

The router component provides weights determining the influence of each path
onto the output. The router is conditioned on a representation of each input
sample, thus allowing to provide a different aggregation weighting for each
sample. To evaluate the effect of the per-sample router, we ablate it by
replacing the weighted aggregation of with a sum aggregation. This results in
the removal of the router component, and loss of per-sample conditioning of
the aggregation.

In practice, this ablation is achieved by replacing the aggregation logic
(equation 9) with a sum of the representation, that can be expressed as:
$\mathbf{a}=R\cdot\mathbf{1}$. Note that, this results in a different forward
pass computation, however the gradients computed for the connector modules are
unaltered.

This ablation results in lower average accuracy. The quality loss is more
pronounced in the first half of the experiment and on the validation set.

Notice that, the proposed method requires to compute all the representations
of the paths included in the sampled architecture as the router function is
limited to produce aggregation weights (_soft-routing_). This method can be
extended to sparsely activate the alternative paths conditioning on the router
weights (_hard routing_) as it is usual in sparsely activated mixture-of-
expert layers. Hard routing extensions can allow to achieve higher compute
efficiency, scaling or per-sample erogenous compute properties. In such
extensions the role of the per-sample router module becomes critical as the
selection of the paths to activate depends on its output.

####  3.2.3 Ablate router bias initialization

The _router bias initialization_ is ablated by applying zero initialization to
all the parameters of the router. This leads the initialized router to produce
a uniform distribution of routing weights. This ablation has the weaker
significance compared to the other considered. In preliminary experiments, we
observed a stronger significance on tasks with smaller training set, as the
initial bias becomes less relevant the longer the training.

####  3.2.4 Ablate router learning rate scaling

The _learning rate scaling_ technique results having a critical impact on the
achieved quality. The learning rate scaling is ablated by simply applying the
global learning rate also to the router component, i.e. disabling the logic
represented by equation (12).

###  3.3 Headroom analysis

The set of paths connected by a multitask architecture ($\mathcal{P}$) is
sampled at random among the set of all the paths available in the system:
$\mathcal{S}$. Even though the configuration of the reported experiments caps
the maximum amount of paths to 3, the resulting search space of paths
combinations cannot be exhaustively explored with the provided exploratory
budget of 15 evolutionary cycles (16 models are sampled each cycle). Dynamic
systems such as $\mu$Net are designed to continuously expand to solve an
unbounded number of tasks: $|\mathcal{S}|\rightarrow\inf$. In this context,
the random sampling method is expected to decrease in efficacy as the number
of possible paths combination grows rapidly: number of paths combinations
${=|\mathcal{S}|!\ /\
((|\mathcal{S}|\\!-\\!|\mathcal{P}|)!\cdot|\mathcal{P}|!)}$.

The experiment reported in this section aims to estimate the headroom
available for improved agents capable of performing a more informed selection
of the paths that contain relevant knowledge for each task/sample. This
experiment executes the proposed multipath agent with a constraint in the
selection of the first support path. The path trained on i_naturalist2017 is
forced to be used as first support path. This path has been chosen based on an
analysis done on the best scoring multipath architectures generated by the
multipath experiments reported in previous sections. The analysis shows that a
small set of paths are frequently selected as support in the highest scoring
models, these are the paths are trained on tasks such as: i_naturalist2017,
imagenet_a, imagenet_r. imagenet_a and imagenet_r are datasets have explicitly
collected to augment the imagenet2012 task. While i_naturalist2017 is a large
dataset of natural domain images. More than 30% of imagenet2012 classes
identify entities in the natural domain. Furthermore, these paths carry
knowledge of multiple tasks on which their ancestors have been trained. For
example, imagenet_a appears to have been mutated from i_naturalist2017 and
still share most of its components (see Figure 2). Forcing the assignment of
the first support path has the effect of restricting the search space to a
size that is more feasibly explorable with random sampling within the given
evolutionary budget. And may give us a sense of what is the headroom for
methods that use a more informed logic to select the activated paths (e.g.
condition the sampling distribution on paths/task meta-features or on the
results achieved by past samplings).

The result of this experiment show that: 1) higher quality is achievable, 2)
the peak test accuracy (within noise) can be achieved with a significant
reduced exploratory budget.

##  4 Related work

This paper contributes to a line of research aiming to define and demonstrate
a novel ML research methodology enabling the creation of _dynamic large-scale
multi-modal multitask modular intelligent systems_ that can be indefinitely
extended through the collaboration of multiple contributors: (Gesmundo & Dean,
2022a; b; Gesmundo, 2022a; b).

In the following paragraphs, we refer to prior work that has been influential
in the design of the multipath agent method.

Ensemble learning relies on the parallel combination of several models to
obtain better generalization (Kurutach et al., 2018). This technique has been
applied consistently with success also to neural networks, providing quality
gains and higher training stability in the vast majority of its applications.
The success of the proposed parallel activation of paths can be interpreted
with similar intuitions to those motivating ensemble learning. Although, there
are major differences: 1) models ensembling combines models trained on the
same tasks, while the proposed method combines model/paths trained on
different tasks, 2) models ensembling allows to compose frozen models while
the aggregation logic can be subject to training independently, instead the
multipath activation requires training of the paths trained on different tasks
to adapt to the target task (i.e. with trainable connector modules), 3)
applications of ensemble learning do not normally include per-sample
conditioned aggregation.

Per-sample routing is a characteristic of mixture-of-expert (MoE) methods
(Shazeer et al., 2017). MoE routers are conditioned on the same input provided
to the experts. While, the proposed design leverages the presence of a _main
path_. This allows to provide a more informative representation of the input
to the router, that enables to minimize the number of trainable parameters
(i.e. the router is a single fully connected layer). Furthermore we propose
alternative solutions to the common routing convergence issues that are
compatible with the modular nature of the proposed research methodology.

Prior work has also explored the application of distinct learning rates to
different components of a sparsely activated architecture (Artetxe et al.,
2021; Fedus et al., 2022).

_Backprop decoupled routing_ is a technique that relies on the decoupling of
the forward and backward pass logic. Although defined to provide a different
functionality, the gumbel-softmax technique (Jang et al., 2016) also relies on
decoupling of the forward and backward pass.

Merullo et al. (2022) has demonstrated the possibility to achieve competitive
performance by connecting frozen models with trainable connectors. Their work
focuses on serial connections, while the multipath architecture applies a
similar intuition to parallel connections. Also, both methods rely on the use
of a architecturally minimalistic connector.

###  4.1 Extended survey

In the remainder of this section, we provide a survey of topics related to the
$\mu$Net line of research.

The proposed system is designed to be immune from common multitask learning
pitfalls: catastrophic forgetting, gradients interference, negative transfer.
Cross-task transfer-learning has gained popularity, especially through
transfer learning from a model pre-trained on a large amount of data for one
or a few general tasks, and then fine-tuned on a small amount of data for a
related downstream task. This approach has been shown to be very effective in
a wide variety of problems across many modalities, including language (Devlin
et al., 2019; Raffel et al., 2020) and vision (Dosovitskiy et al., 2021; He et
al., 2016). The success of transfer-learning applications hinges on adequate
prior knowledge selection to avoid typical negative transfer pitfalls
(Rosenstein, 2005; Wang et al., 2019). Common solutions rely on data or model
selection techniques, often putting emphasis on the efficiency of the
exploration (Zhang et al., 2020; Mensink et al., 2021), also method aiming to
automate knowledge selection at a layer level have been proposed Sun et al.
(2020a). Transfer learning capabilities are critical for multitask models. ML
models trained jointly on multiple tasks can be affected by gradients
interference if any subset of parameters receive gradients jointly from
multiple sources (Chen et al., 2018; Yu et al., 2020), and by catastrophic
forgetting of prior knowledge as new tasks are learned (McCloskey & Cohen,
1989; French, 1999). These knowledge loss problems can be alleviated with
weighted combination of tasks (Liu et al., 2019b; Sun et al., 2020b) and
gradient transformation methods (Chen et al., 2018; Sener & Koltun, 2018;
Kendall et al., 2018). Stronger guarantees are provided by methods that
compartmentalize task specific knowledge in dedicated parameter subsets
(Rebuffi et al., 2017; Houlsby et al., 2019; Rusu et al., 2016; Rosenfeld &
Tsotsos, 2020). Addressing catastrophic forgetting and identifying what subset
of parameters/knowledge that is beneficial to share with each task is also
critical for continual learning or life long learning methods (McCloskey &
Cohen, 1989; French, 1999; Ramesh & Chaudhari, 2022), some also considering a
modular approach (Véniat et al., 2020).

The proposed method relies on an evolutionary approach to jointly search the
spaces of models architectures, hyperparameters, and prior knowledge
selection. The automation of hyperparameter tuning has been commonly addressed
with Bayesian optimization (Srinivas et al., 2010; Bergstra et al., 2011;
Snoek et al., 2012), evolutionary methods have also been explored for this
purpose (Jaderberg et al., 2017; Zhang et al., 2011). Hyperparameters tuning
can be considered related to the neural architecture search (NAS), as
architectures can be defined by the selection of a sequence of architectural
hyperparameters. Initially, NAS methods have been based on reinforcement
learning techniques (Zoph & Le, 2017) but also sample efficient evolutionary
approaches have been proposed (Real et al., 2019; Maziarz et al., 2018).
Parameter-sharing based NAS methods aim to reduce the typically high training
cost (Pham et al., 2018; Liu et al., 2019a; Kokiopoulou et al., 2019).
Optimization for multi-factor quality/cost trade-offs have been explored (Tan
et al., 2019).

Prior methods have been proposed to achieve dynamic architecture extensions
(Chen et al., 2016; Cai et al., 2018), some also focusing on an unbounded
stream of tasks (Yoon et al., 2018; Yao et al., 2020), or achieving immunity
from catastrophic forgetting (Rusu et al., 2016; Li & Hoiem, 2018; Li et al.,
2019; Rosenfeld & Tsotsos, 2020).

Sparse activation allows to decouple knowledge/parameters growth from
computational cost increase. Performance improvements of state-of-the-art
models often requires growth in terms of trainable parameters (Kaplan et al.,
2020). Sparse activation techniques at sub-layer level (Shazeer et al., 2017;
Du et al., 2021) or network route level (Fernando et al., 2017) allow to
decouple model size growth from compute cost. This is achieved by integrating
a routing technique that selects the appropriate subset of parameters storing
the most relevant knowledge for each task, sample or token/patch.

The ability of jointly solve a large amount of tasks is commonly associated
with progress toward Artificial General Intelligence (AGI). Advancements in
scaling language models (Brown et al., 2020; Thoppilan et al., 2022) allowed
to achieve novel discourse, reasoning and zero/few shot learning capabilities
that can be applied to new tasks without/minimal additional training. Recent
work aims to extend these achievements beyond text modality by defining static
architectures for an extended subset of modalities (Alayrac et al., 2022; Reed
et al., 2022). These are a few examples of the ML models contributing to the
line of research achieving incremental milestone toward AGI. Though, each
model is trained from scratch with considerable resources consumption. The
introduction of abstractions allowing to modularize, dynamically extend and
reuse these large models may contribute to accelerate the rate of innovation.

Large scale $\mu$Net experiments have been enabled by the use of the ML-
Pathways framework (Barham et al., 2022).

##  5 Conclusion

We presented a novel agent capable of generating architectures activating
multiple paths within a modular multitask system such as $\mu$Net.
Furthermore, paths activation is conditioned on the input allowing to select
and combine the relevant knowledge for each sample. We demonstrated that such
method can be applied to achieve the quality headroom available to tasks with
high ambiguity and large dataset that can benefit from the use of models with
more knowledge/parameters such as imagenet2012. We defined novel design
elements of critical importance, such as: _modular learning rate scaling_ and
_backprop decoupled routing_. These elements are compatible with the modular
nature of the novel methodology developed by the $\mu$Net line of research,
but are also generically applicable to arbitrary neural network architectures.

We have provided empirical evidences suggesting that further headroom can be
achieved with a mutation sampling logic of higher sophistication than random
sampling. We expect this headroom to widen as the complexity of the design
space increases with more tasks and methods being added to continuously
expanding systems such as $\mu$Net.

Future work can continue to build toward extending the set of tasks and
connectable model architectures and enabling transfer of knowledge across
different input/output modalities.

## References

  * Alayrac et al. (2022) Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katie Millican, Malcolm Reynolds, Roman Ring, Eliza Rutherford, Serkan Cabi, Tengda Han, Zhitao Gong, Sina Samangooei, Marianne Monteiro, Jacob Menick, Sebastian Borgeaud, Andy Brock, Aida Nematzadeh, Sahand Sharifzadeh, Mikolaj Binkowski, Ricardo Barreira, Oriol Vinyals, Andrew Zisserman, and Karen Simonyan.  Flamingo: a visual language model for few-shot learning.  _ArXiv_ , abs/2204.14198, 2022.
  * Artetxe et al. (2021) Mikel Artetxe, Shruti Bhosale, Naman Goyal, Todor Mihaylov, Myle Ott, Sam Shleifer, Xi Victoria Lin, Jingfei Du, Srini Iyer, Ramakanth Pasunuru, Giridhar Anantharaman, Xian Li, Shuohui Chen, Halil Akın, Mandeep Baines, Louis Martin, Xing Zhou, Punit Singh Koura, Brian O’Horo, Jeff Wang, Luke Zettlemoyer, Mona Diab, Zornitsa Kozareva, and Ves Stoyanov.  Efficient large scale language modeling with mixtures of experts.  _ArXiv_ , abs/2112.10684, 2021.
  * Barham et al. (2022) Paul Barham, Aakanksha Chowdhery, Jeffrey Dean, Sanjay Ghemawat, Steven Hand, Daniel Hurt, Michael Isard, Hyeontaek Lim, Ruoming Pang, Sudip Roy, Brennan Saeta, Parker Schuh, Ryan Sepassi, Laurent El Shafey, Chandramohan A. Thekkath, and Yonghui Wu.  Pathways: Asynchronous distributed dataflow for ml.  _ArXiv_ , abs/2203.12533, 2022.
  * Bergstra et al. (2011) James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl.  Algorithms for hyper-parameter optimization.  In _NIPS_ , 2011.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, T. J. Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeff Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  _ArXiv_ , abs/2005.14165, 2020.
  * Cai et al. (2018) Han Cai, Tianyao Chen, Weinan Zhang, Yong Yu, and Jun Wang.  Efficient architecture search by network transformation.  In _AAAI_ , 2018.
  * Chen et al. (2016) Tianqi Chen, Ian J. Goodfellow, and Jonathon Shlens.  Net2net: Accelerating learning via knowledge transfer.  _CoRR_ , abs/1511.05641, 2016.
  * Chen et al. (2018) Zhao Chen, Vijay Badrinarayanan, Chen-Yu Lee, and Andrew Rabinovich.  Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks.  In _ICML_ , 2018.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL_ , 2019.
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  _ArXiv_ , abs/2010.11929, 2021.
  * Du et al. (2021) Nan Du, Yanping Huang, Andrew M. Dai, Simon Tong, Dmitry Lepikhin, Yuanzhong Xu, Maxim Krikun, Yanqi Zhou, Adams Wei Yu, Orhan Firat, Barret Zoph, Liam Fedus, Maarten Bosma, Zongwei Zhou, Tao Wang, Yu Emma Wang, Kellie Webster, Marie Pellat, Kevin Robinson, Kathleen S. Meier-Hellstern, Toju Duke, Lucas Dixon, Kun Zhang, Quoc V. Le, Yonghui Wu, Z. Chen, and Claire Cui.  Glam: Efficient scaling of language models with mixture-of-experts.  _ArXiv_ , abs/2112.06905, 2021.
  * Fedus et al. (2022) William Fedus, Jeff Dean, and Barret Zoph.  A review of sparse expert models in deep learning.  _ArXiv_ , abs/2209.01667, 2022.
  * Fernando et al. (2017) Chrisantha Fernando, Dylan S. Banarse, Charles Blundell, Yori Zwols, David R Ha, Andrei A. Rusu, Alexander Pritzel, and Daan Wierstra.  Pathnet: Evolution channels gradient descent in super neural networks.  _ArXiv_ , abs/1701.08734, 2017.
  * French (1999) Robert M. French.  Catastrophic forgetting in connectionist networks.  _Trends in Cognitive Sciences_ , 3:128–135, 1999.
  * Gesmundo (2022a) Andrea Gesmundo.  A continual development methodology for large-scale multitask dynamic ml systems.  _ArXiv_ , 2209.07326, 2022a.
  * Gesmundo (2022b) Andrea Gesmundo.  A multiagent framework for the asynchronous and collaborative extension of multitask ml systems.  _ArXiv_ , 2209.14745, 2022b.
  * Gesmundo & Dean (2022a) Andrea Gesmundo and Jeff Dean.  munet: Evolving pretrained deep neural networks into scalable auto-tuning multitask systems.  _ArXiv_ , 2205.10937, 2022a.
  * Gesmundo & Dean (2022b) Andrea Gesmundo and Jeff Dean.  An evolutionary approach to dynamic introduction of tasks in large-scale multitask learning systems.  _ArXiv_ , 2205.12755, 2022b.
  * He et al. (2016) Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 770–778, 2016.
  * Houlsby et al. (2019) Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin de Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly.  Parameter-efficient transfer learning for nlp.  In _ICML_ , 2019.
  * Jaderberg et al. (2017) Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M. Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, Iain Dunning, Karen Simonyan, Chrisantha Fernando, and Koray Kavukcuoglu.  Population based training of neural networks.  _ArXiv_ , abs/1711.09846, 2017.
  * Jang et al. (2016) Eric Jang, Shixiang Shane Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax.  _ArXiv_ , abs/1611.01144, 2016.
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, T. J. Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeff Wu, and Dario Amodei.  Scaling laws for neural language models.  _ArXiv_ , abs/2001.08361, 2020.
  * Kendall et al. (2018) Alex Kendall, Yarin Gal, and Roberto Cipolla.  Multi-task learning using uncertainty to weigh losses for scene geometry and semantics.  _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 7482–7491, 2018.
  * Kokiopoulou et al. (2019) Efi Kokiopoulou, Anja Hauth, Luciano Sbaiz, Andrea Gesmundo, Gábor Bartók, and Jesse Berent.  Fast task-aware architecture inference.  _ArXiv_ , abs/1902.05781, 2019.
  * Kurutach et al. (2018) Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and P. Abbeel.  Model-ensemble trust-region policy optimization.  _ArXiv_ , abs/1802.10592, 2018.
  * Li et al. (2019) Xilai Li, Yingbo Zhou, Tianfu Wu, Richard Socher, and Caiming Xiong.  Learn to grow: A continual structure learning framework for overcoming catastrophic forgetting.  In _ICML_ , 2019.
  * Li & Hoiem (2018) Zhizhong Li and Derek Hoiem.  Learning without forgetting.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 40:2935–2947, 2018.
  * Liu et al. (2019a) Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  _ArXiv_ , abs/1806.09055, 2019a.
  * Liu et al. (2019b) Shengchao Liu, Yingyu Liang, and Anthony Gitter.  Loss-balanced task weighting to reduce negative transfer in multi-task learning.  In _AAAI_ , 2019b.
  * Maziarz et al. (2018) Krzysztof Maziarz, Andrey Khorlin, Quentin de Laroussilhe, and Andrea Gesmundo.  Evolutionary-neural hybrid agents for architecture search.  _ArXiv_ , abs/1811.09828, 2018.
  * McCloskey & Cohen (1989) Michael McCloskey and Neal J. Cohen.  Catastrophic interference in connectionist networks: The sequential learning problem.  _Psychology of Learning and Motivation_ , 24:109–165, 1989\.
  * Mensink et al. (2021) Thomas Mensink, Jasper R. R. Uijlings, Alina Kuznetsova, Michael Gygli, and Vittorio Ferrari.  Factors of influence for transfer learning across diverse appearance domains and task types.  _IEEE transactions on pattern analysis and machine intelligence_ , PP, 2021.
  * Merullo et al. (2022) Jack Merullo, Louis Castricato, Carsten Eickhoff, and Elizabeth-Jane Pavlick.  Linearly mapping from image to text space.  _ArXiv_ , abs/2209.15162, 2022.
  * Pham et al. (2018) Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean.  Efficient neural architecture search via parameter sharing.  In _ICML_ , 2018.
  * Raffel et al. (2020) Colin Raffel, Noam M. Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _ArXiv_ , abs/1910.10683, 2020.
  * Ramesh & Chaudhari (2022) Rahul Ramesh and Pratik Chaudhari.  Model zoo: A growing brain that learns continually.  In _ICLR_ , 2022.
  * Real et al. (2019) Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le.  Regularized evolution for image classifier architecture search.  In _AAAI_ , 2019.
  * Rebuffi et al. (2017) Sylvestre-Alvise Rebuffi, Hakan Bilen, and Andrea Vedaldi.  Learning multiple visual domains with residual adapters.  In _NIPS_ , 2017.
  * Reed et al. (2022) Scott Reed, Konrad Zolna, Emilio Parisotto, Sergio Gomez Colmenarejo, Alexander Novikov, Gabriel Barth-Maron, Mai Gimenez, Yury Sulsky, Jackie Kay, Jost Tobias Springenberg, Tom Eccles, Jake Bruce, Ali Razavi, Ashley D. Edwards, Nicolas Manfred Otto Heess, Yutian Chen, Raia Hadsell, Oriol Vinyals, Mahyar Bordbar, and Nando de Freitas.  A generalist agent.  _ArXiv_ , abs/2205.06175, 2022.
  * Rosenfeld & Tsotsos (2020) Amir Rosenfeld and John K. Tsotsos.  Incremental learning through deep adaptation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 42:651–663, 2020.
  * Rosenstein (2005) Michael T. Rosenstein.  To transfer or not to transfer.  In _NIPS 2005_ , 2005.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and Li Fei-Fei.  Imagenet large scale visual recognition challenge.  _International Journal of Computer Vision_ , 115:211–252, 2015.
  * Rusu et al. (2016) Andrei A. Rusu, Neil C. Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell.  Progressive neural networks.  _ArXiv_ , abs/1606.04671, 2016.
  * Sener & Koltun (2018) Ozan Sener and Vladlen Koltun.  Multi-task learning as multi-objective optimization.  In _NeurIPS_ , 2018.
  * Shazeer et al. (2017) Noam M. Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc V. Le, Geoffrey E. Hinton, and Jeff Dean.  Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.  _ArXiv_ , abs/1701.06538, 2017.
  * Shen et al. (2019) Tianxiao Shen, Myle Ott, Michael Auli, and Marc’Aurelio Ranzato.  Mixture models for diverse machine translation: Tricks of the trade.  In _International Conference on Machine Learning_ , 2019.
  * Snoek et al. (2012) Jasper Snoek, H. Larochelle, and Ryan P. Adams.  Practical bayesian optimization of machine learning algorithms.  In _NIPS_ , 2012.
  * Srinivas et al. (2010) Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger.  Gaussian process optimization in the bandit setting: No regret and experimental design.  In _ICML_ , 2010.
  * Sun et al. (2020a) Ximeng Sun, Rameswar Panda, and Rogério Schmidt Feris.  Adashare: Learning what to share for efficient deep multi-task learning.  _ArXiv_ , abs/1911.12423, 2020a.
  * Sun et al. (2020b) Yu Sun, Shuohuan Wang, Yukun Li, Shikun Feng, Hao Tian, Hua Wu, and Haifeng Wang.  Ernie 2.0: A continual pre-training framework for language understanding.  _ArXiv_ , abs/1907.12412, 2020b.
  * Tan et al. (2019) Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, and Quoc V. Le.  Mnasnet: Platform-aware neural architecture search for mobile.  _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 2815–2823, 2019.
  * Thoppilan et al. (2022) Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam M. Shazeer, Apoorv Kulshreshtha, Heng-Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, Yaguang Li, Hongrae Lee, Huaixiu Zheng, Amin Ghafouri, Marcelo Menegali, Yanping Huang, Maxim Krikun, Dmitry Lepikhin, James Qin, Dehao Chen, Yuanzhong Xu, Zhifeng Chen, Adam Roberts, Maarten Bosma, Yanqi Zhou, Chung-Ching Chang, I. A. Krivokon, Willard James Rusch, Marc Pickett, Kathleen S. Meier-Hellstern, Meredith Ringel Morris, Tulsee Doshi, Renelito Delos Santos, Toju Duke, Johnny Hartz Søraker, Ben Zevenbergen, Vinodkumar Prabhakaran, Mark Diaz, Ben Hutchinson, Kristen Olson, Alejandra Molina, Erin Hoffman-John, Josh Lee, Lora Aroyo, Ravindran Rajakumar, Alena Butryna, Matthew Lamm, V. O. Kuzmina, Joseph Fenton, Aaron Cohen, Rachel Bernstein, Ray Kurzweil, Blaise Aguera-Arcas, Claire Cui, Marian Croak, Ed Chi, and Quoc Le.  Lamda: Language models for dialog applications.  _ArXiv_ , abs/2201.08239, 2022.
  * Véniat et al. (2020) Tom Véniat, Ludovic Denoyer, and Marc’Aurelio Ranzato.  Efficient continual learning with modular networks and task-driven priors.  _ArXiv_ , abs/2012.12631, 2020.
  * Wang et al. (2019) Zirui Wang, Zihang Dai, Barnabás Póczos, and Jaime G. Carbonell.  Characterizing and avoiding negative transfer.  _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 11285–11294, 2019.
  * Yao et al. (2020) Huaxiu Yao, Yingbo Zhou, Mehrdad Mahdavi, Zhenhui Jessie Li, Richard Socher, and Caiming Xiong.  Online structured meta-learning.  _ArXiv_ , abs/2010.11545, 2020.
  * Yoon et al. (2018) Jaehong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang.  Lifelong learning with dynamically expandable networks.  _ArXiv_ , abs/1708.01547, 2018.
  * Yu et al. (2020) Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn.  Gradient surgery for multi-task learning.  _ArXiv_ , abs/2001.06782, 2020.
  * Zhai et al. (2019) Xiaohua Zhai, Joan Puigcerver, Alexander Kolesnikov, Pierre Ruyssen, Carlos Riquelme, Mario Lucic, Josip Djolonga, André Susano Pinto, Maxim Neumann, Alexey Dosovitskiy, Lucas Beyer, Olivier Bachem, Michael Tschannen, Marcin Michalski, Olivier Bousquet, Sylvain Gelly, and Neil Houlsby.  The visual task adaptation benchmark.  _ArXiv_ , abs/1910.04867, 2019.
  * Zhang et al. (2011) Jun Zhang, Zhi hui Zhan, Ying Lin, Ni Chen, Yue jiao Gong, Jinghui Zhong, Henry Shu hung Chung, Yun Li, and Yu hui Shi.  Evolutionary computation meets machine learning: A survey.  _IEEE Computational Intelligence Magazine_ , 6:68–75, 2011\.
  * Zhang et al. (2020) Wen Zhang, Lingfei Deng, Lei Zhang, and Dongrui Wu.  A survey on negative transfer.  _ArXiv_ , abs/2009.00909, 2020.
  * Zoph & Le (2017) Barret Zoph and Quoc V. Le.  Neural architecture search with reinforcement learning.  _ArXiv_ , abs/1611.01578, 2017.


# A GIS Data Realistic Road Generation Approach for Traffic Simulation

Yacine Amara, Abdenour Amamra, Yasmine Daheur, and Lamia Saichi  Ecole
Militaire Polytechnique, Bordj El-Bahri BP 17, Algiers, Algeria  Email:
<EMAIL_ADDRESS>
###### Abstract

Road networks exist in the form of polylines with attributes within the GIS
databases. Such a representation renders the geographic data impracticable for
3D road traffic simulation. In this work, we propose a method to transform raw
GIS data into a realistic, operational model for real-time road traffic
simulation. For instance, the proposed raw to simulation-ready data
transformation is achieved through several curvature estimation,
interpolation/approximation, and clustering schemes. The obtained results show
the performance of our approach and prove its adequacy to real traffic
simulation scenario as can be seen in this
video111https://youtu.be/t8eyphcFYHc.

###### Index Terms:

Road interpolation, Road modeling, Traffic simulation, Vehicle virtual
navigation.

##  I Introduction

In recent years, applications of road traffic simulation have become
ubiquitous in everyday life: driving simulation or racing games are
increasingly attracting the attention of developers. However, the results
obtained are not always consistent with reality. When one wants to reproduce a
realistic behavior, the developer must consider the real parameters of the
road.

The realization of a real-life road simulation would make it possible to
forecast the traffic generated in a given road network. This realism, modeled
on a computer, would help managers to detect the problems present in the
network, namely congestion, accidents, user stress, an insufficient number of
channels, etc. Besides optimizing traffic on the roads without making urban
changes, such as the location of traffic lights, number, and width of lanes.

The shape of the road is complex, particularly at mountainous segments, severe
turns, etc. Therefore, finding the best mathematical function that will fit
the shape of these sections while taking into account compressing the number
of data to be stored is challenging.

Geometric processing applications rely on the geometric properties of curves
such as torsion, curvature, and tangents. In our study, we chose the curvature
metric in the road’s modeling surface, since the latter embeds the information
on the shape of the road. The actual data is extracted from the Geographic
Information System (GIS), the latter known for providing the ability to
manipulate geographical information laid out on multiple layers. The metric
being chosen; our approach is then organized as follows: extraction of the
road layer as polylines in the GIS data; curvature estimation at the
neighborhood of the points; a grouping of points in clusters according to the
sign of their curvature, and finally the approximation of clusters by
continuous mathematical functions.

Figure 1:

##  II Related works

Most of the work that has been proposed on road reconstruction is based on
procedural modeling. Roads are generated by empirical rules often based on
observation. We will classify the methods proposed in two categories: the
methods taking the input of calculated roads (procedural approaches) and the
models taking as input the data resulting from Geographic Information Systems
(GIS).

###  II-A Procedural approaches

These approaches take as input roads derived or calculated by mathematical or
optimization methods. Both, Parish et al. [1] and Jing et al. [2] generated
models of cities in which road networks played a key role. Their roads were
built from the central lines that are generated either by grammar rules named
_L-Systems_ [1], or model-based methods [2]. However, the defining laws or
models to regenerate exactly the structure of urban roads are not available.
Hence, their roads often drift from their respective real counterparts. In
addition, their methods were not designed for highways and suburban roads.

Some of these limitations have been resolved by Chen et al. [3], where they
used a tensor field from which a graph representing the road network was
calculated. This can be modified to control the locally generated road
profile. Their method permits creating large areas but does not allow the
reconstruction of existing networks because of the problem of scale
limitation. In addition, only urban roads were considered.

Another procedural model was proposed by Galin et al. [4, 5] based on a
platform for generating mapped roads that contain many types of features such
as trees, rivers, and lakes. Their roads resulted from a short path algorithm
instead of the real data. As a result, we obtain fictitious roads that do not
satisfy the constraints of civil engineering. The generated roads are
erroneous and do not match the shape of the terrain. This lack of realism is
because of the shortcomings of the proposed approaches. The major shortcoming
of these works is not to have considered the actual data as input of the
problem.

###  II-B GIS data approaches

To overcome the problems mentioned and to build more realistic roads, Bruneton
and Neyret [6] proposed a method of generating large road surfaces from GIS
data. They represented the roads with Bezier curves to join the sampled points
and then mapped them on the ground. Although this model helps to perceive
actual road coordinates, current roads are no longer built from Bezier curves.
Again, these models are affected by the lack of realism. The details and
constraints related to civil engineering discipline are not taken into
account. Road networks must be defined by simple forms such as straight lines,
arcs of circles, and clothoids. This drawback had been addressed by the
following work:

####  II-B1 LSGA algorithm

This work [7] introduces a new approach to construct smoothed curve pieces
representing realistic roads. Given a GIS database of road networks, where the
sampled points are organized as 3D polylines, this method creates horizontal
and verticals curves, then it combines them to generate the roads. The major
contribution of this work is a tree traversal algorithm that extends the
sequences of the best fit primitives and a fusion process of these primitives.
The latter must respect a certain grammar according to an automaton. This
approach offers more realistic results than those that preceded it, and the
errors are proportional to the noisiness of input data.

####  II-B2 Construction by clothoids

In [6], the algorithm for adjusting a sequence of $G_{2}$ polylines into
clothoid segments takes place in two steps: first a piecewise linear
approximation is applied, then a sequence of rigid 2D transformations is
applied in order to align the in one consistent result. Although this method
respects civil engineering constraints and models the transition between a
circular arc and a straight line with a clothoid, its first pass through the
linear segments loses the precision when estimating the radius of curvature.

####  II-B3 Automatic generation of 3D roads

This method, presented in [8], is based on a set of civil engineering rules.
It proposes a new approach for the automatic 3D generation of high-fidelity
roads. It transforms GIS data that only contains 2D information from the
central axis of the road into a 3D model of the road network. In the proposed
approach, basic road elements such as road segments, road intersection are
generated automatically to form sophisticated road networks. But in the
modeling of the axe of the road, the segments were connected by Hermite
curves, which satisfy only $G_{1}$ continuity, hence the civil engineering
constraints were not respected.

The proposed model must be realistic, that is to say, that it must meet the
constraints of civil engineering and vehicle dynamics, for this reason, our
study was based on an essential criterion which is _curvature_. Curvature, the
inverse of the radius of the circle tangent to the curve, is defined as the
norm of the acceleration vector of a body traveling the curve at unit speed.
It is the second derivative with respect to the curvilinear abscissa of the
body position.

##  III Curvature Estimation

###  III-A Definition

A parametric curve is a function
$r:I\subset\mathbb{R}\rightarrow\mathbb{R}^{n}$, when $n=2$ it is called a
_plane curve_. The curvilinear abscissa $s$ from a point $r(t_{0})$, $t_{0}\in
I$, at a given point $r(t_{1})$, $t_{1}\in I$, is defined by:

$s(t_{1})=\int_{t_{0}}^{t_{1}}\left\lVert r^{\prime}(u)\right\rVert du$ (1)

The vector $T(s)=r^{\prime}(s)$ is called the tangent vector. The normal
vector $N(s)$ is obtained by a rotation of $90^{\circ}$ anticlockwise. The
vectors $T^{\prime}(s)$ and $N(s)$ are collinear. That is, there is a function
$k(s)$ such that:

$T^{\prime}(s)=k(s)\times N(s)$ (2)

called the _curvature_ of the curve at the point $r(s)$. The curvature also
corresponds to the variation of the direction of the tangent vector
respectively to the curvilinear abscissa: $k(s)=\theta^{\prime}(s)$, such that
:

$\theta^{\prime}(s)=\measuredangle(\overrightarrow{T(s)},\overrightarrow{(1,0)})$
(3)

Since our initial data is in discrete form, we performed a local estimation
using a sliding window. The latter is centered around a point allowing to
approximate all it neighbors within the window by a second order polynomial.
The interest of such an operation is to deduce the first and the second
derivatives, to then calculate the curvature. Several approximation methods
called _implicit parabola fitting_ proposed in [9], which have a good
performance and a fair simplicity of implementation.

###  III-B Second-order curve approximation

In the implicit parabola fitting method, proposed in [9], the curve is
described by a function such that: $y=f(x)$ or $x=f(y)$. The variation of $x$
and $y$ inside the window determines the parameterization to adopt, in fact,
if the variation of $x$ is greater than that of $y$, the algorithm will select
the case $y=f(x)$ and vice versa . In order to simplify the notation, we will
consider that $p_{0}=(0,0)$. The goal is to find $f_{0}^{{}^{\prime}}$ and
$f_{0}^{{}^{\prime\prime}}$, which minimize:

$E_{x}(f_{0}^{{}^{\prime}},f_{0}^{{}^{\prime\prime}})=\sum_{i=-q}^{q}(y_{i}-f_{0}^{{}^{\prime}}x_{i}-\frac{1}{2}f_{0}^{{}^{\prime\prime}}x_{i}^{2})^{2}$
(4)

The solution of this problem of least squares gives:

$f_{0}^{{}^{\prime}}=\frac{cg-bh}{ac-b^{2}}\quad
f_{0}^{{}^{\prime\prime}}=\frac{ah-bg}{ac-b^{2}}$ (5)

such that :

$\begin{split}a=\sum_{i=-q}^{q}x_{i}^{2}\quad g=\sum_{i=-q}^{q}x_{i}y_{i}\quad
b=\frac{1}{2}\sum_{i=-q}^{q}x_{i}^{3},\\\
h=\frac{1}{2}\sum_{i=-q}^{q}x_{i}^{2}y_{i}\quad
c=\frac{1}{4}\sum_{i=-q}^{q}x_{i}^{4}\end{split}$ (6)

(a)

(b)

Figure 2: (a) Points window, (b) Approximation by least squares

###  III-C Curvature computation

####  III-C1 Model and notation

Consider a set of points ${p_{i}}$ of a flat smooth curve $r$, in this study
the curve is parameterized by the arc length, the estimate of the curvature
for a plane curve requires an approximation of the first and second
derivatives of ${r}(s)$. Let a point $p_{0}$ be chosen . The derivation of $r$
in $p_{0}$ will be estimated from a window of size $2q+1$ around
$p_{0}:{p_{-q},p_{-q+1},\ldots,p_{q}}$ (see Fig 2(a)). We set $p_{0}=r(0)$ as
the origin, the approximation of degree two can be written in the form:

$r(s)=r^{\prime}(0)s+\frac{1}{2}+r^{\prime\prime}(0)s^{2}$ (7)

####  III-C2 The least squares approach

The estimate of $r^{\prime}(0)$, $r^{\prime\prime}(0)$ is obtained by the
least squares approach (Fig 2(b)). The weighting $w_{i}$ of the point $p_{i}$
must be positive, relatively important for small values of $|s_{i}|$ and
relatively small for large values of $|s_{i}|$.

The arc length $s_{i}$ can be estimated as follows: $\Delta l_{k}$ is the arc
length of the vector $p_{k}p_{k+1}$, where $k$ varies from $-q$ to $q-1$. The
arc length between $p_{0}$ and $p_{i}$ can be approximated by:

$\displaystyle\left\\{\begin{array}[]{ll}l_{i}=\sum_{k=0}^{i-1},i>0\\\
l_{i}=-\sum_{k=0}^{-1},i<0\end{array}\right.$ (8)

###  III-D Curvature computation for a plane curve

For the case of plane curves, the idea of the Independent coordinates method
[9] is to construct a parametric curve $(x(s),y(s))$ that approaches the curve
locally, by quadratic functions as a function of arc length.

$\displaystyle\left\\{\begin{array}[]{ll}\hat{x}(s)=x_{0}+x_{0}^{\prime}s+\frac{1}{2}x_{0}^{\prime\prime}s^{2}\\\
\hat{y}(s)=y_{0}+y_{0}^{\prime}s+\frac{1}{2}y_{0}^{\prime\prime}s^{2}\end{array}\right.$
(9)

The derivatives $x_{0}^{\prime}$ and $x_{0}^{\prime\prime}$ are estimated by
minimizing:

$E_{x}(x_{0}^{\prime},x_{0}^{\prime\prime})=\sum_{i=-q}^{q}w_{i}(x_{i}-x_{i}^{\prime}l_{i}-\frac{1}{2}x_{0}^{\prime\prime}l_{i}^{2})^{2}$
(10)

The minimization of this equation can be written in the following matrix form

$\begin{bmatrix}a_{1}&a_{2}\\\
a_{2}&a_{3}\end{bmatrix}\begin{bmatrix}x_{0}^{\prime}\\\
x_{0}^{\prime\prime}\\\ \end{bmatrix}=\begin{bmatrix}b_{x,1}\\\ b_{x,1}\\\
\end{bmatrix}$ (11)

such that :

$\begin{split}a_{1}=\sum_{i=-q}^{q}w_{i}l_{i}^{2}\quad
a_{2}=\frac{1}{2}\sum_{i=-q}^{q}w_{i}l_{i}^{3}\quad
a_{3}=\frac{1}{4}\sum_{i=-q}^{q}w_{i}l_{i}^{4}\\\
b_{x,1}=\sum_{i=-q}^{q}x_{i}w_{i}l_{i}\quad
b_{x,2}=\frac{1}{2}\sum_{i=-q}^{q}w_{i}l_{i}^{2}x_{i}\end{split}$ (12)

$I[]=a_{1}=a_{2}=a_{3}=b_{x,1}=b_{x,2}=b_{y,1}=b_{y,2}=0$

for  _i = -q; i $\leq q$; q++_ do

$I[i]\leftarrow I[i-1]+\left\lVert p_{i}p_{i-1}\right\rVert$

end for

$m=I[0]$

for  _i = -q; i $leqq$; q++_ do

$I[i]\leftarrow I[i]-m$

$w\leftarrow weight(I[i])^{2}$

$a_{1}\leftarrow a_{1}+w(I[i])^{2}$

$a_{2}\leftarrow a_{2}+\frac{w}{2}(I[i])^{3}$

$a_{2}\leftarrow a_{2}+\frac{w}{4}(I[i])^{4}$

$b_{x,1}\leftarrow b_{x,1}+w(I[i])(x_{i}-x_{0})$

$b_{y,1}\leftarrow b_{y,1}+w(I[i])(y_{i}-y_{0})$

$b_{x,2}\leftarrow b_{x,1}+\frac{w}{2}(I[i])^{2}(x_{i}-x_{0})$

$b_{y,2}\leftarrow b_{y,1}+\frac{w}{2}(I[i])^{2}(y_{i}-y_{0})$

end for

$d\leftarrow a_{1}a_{3}-a_{2}^{2}$

Algorithm 1 Weighted least square variables setting

$x_{0}^{\prime}\leftarrow(a_{3}b_{x,1}-a_{2}b_{x,2})/d$

$y_{0}^{\prime}\leftarrow(a_{3}b_{y,1}-a_{2}b_{y,2})/d$

$x_{0}^{\prime\prime}\leftarrow(a_{1}b_{x,2}-a_{2}b_{x,1})/d$

$y_{0}^{\prime\prime}\leftarrow(a_{1}b_{y,2}-a_{2}b_{y,1})/d$

$\kappa\leftarrow(x_{0}^{\prime}y_{0}^{\prime\prime}-y_{0}^{\prime}x_{0}^{\prime\prime})/\left\lVert(x_{0}^{\prime},y_{0}^{\prime})\right\rVert^{3}$

$T\leftarrow(x_{0}^{\prime},y_{0}^{\prime})/\left\lVert(x_{0}^{\prime},y_{0}^{\prime})\right\rVert$

$N\leftarrow sign(\kappa)(-T_{y},T_{x})$

Algorithm 2 Coefficient computation

The same procedure is applied for the calculation of $y_{0}^{\prime}$ and
$y_{0}^{\prime\prime}$. The tangent $T$ is obtained by the normalization of
the vector $r_{0}^{\prime}=(x_{0}^{\prime},y_{0}^{\prime})$, while the normal
vector is obtained by a rotation of $90^{\circ}$ of $T$.

##  IV Cutting according to curvature

This step will aim to cut the road into a set of primitives consisting of
straight lines, left/right turns based on the value of curvature estimated at
each point as explained in the previous step.

For this, we will execute the following processes in the order indicated. We
first start with a classification in two primitives only, that is to say
left/right turn, we continue by extracting the sections which are straight
lines independently of the primitives obtained previously and we thus finish
by eliminating the isolated points, which are of the right type because a
primitive of the right type must have a minimum number of two points. In what
follows we will detail the procedure for filtering the curvature values
according to the order of execution of the steps.

###  IV-A Preprocessing

In order to facilitate the different treatments, an initial marking of all the
points of the curve has been carried out. For this, we assigned to each point
whose curvature is positive the number +1, and -1 for those whose value of the
curvature is negative, and we stored the result in a table named ”ids” which
will be subsequently updated by the results of the different processing.

###  IV-B Left and right turns detection

Our approach was based on a local estimate of the curvature sign near the
point considered. A sliding window of size $w$ has been used to estimate the
global sign of the values inside the window by summing the values previously
assigned, so the classification of the types of sections will be carried out
as following :

  * •

The sum is positive, so it is a right turn and the point is marked +1.

  * •

The sum is negative, so it is a left turn and the point is marked -1.

  * •

The zero sum is not a possible case because the size of the window around the
point is odd.

This step is very important because it allows to assign a point to a given
turn even if the sign of its curvature does not correspond, because it is the
trend of the whole neighborhood is taken into consideration.

###  IV-C Straight line detection

Straight line detection is based on the value of the estimated curvature.
Indeed, we know that a line is characterized by a null curvature. Since the
values of the estimated curvature are not all accurate and contain noise, a
threshold $\delta$ has been set. If the curvature norm is below this
threshold, the point will be assigned to a straight line primitive. Points
satisfying the relationship $|K(s)|<\delta$ will be assigned the number 0.

###  IV-D Elimination of isolated right point

Knowing that a marked point of a straight line can not be isolated, the
solution is to go through all the points of the line and to modify those which
are of marking different from their neighbors according to the signs of the
curvature at this point, i.e. +1 marking if the curvature is positive, -1
otherwise.

while  _i $<$ ids.size()_ do

gpts gpt

gpt.type $\leftarrow$ ids[i]

gpt.id $\leftarrow$ i

gpt.nbr $\leftarrow$ 0

for  _i = 0; i $<$ ids.size(); i++_ do

if  _gpt.type $\neq$ ids[i]_ then

Break

end if

gpt.nbr++

end for

end while

Algorithm 3 Primitive assignment

##  V Turns approximation with second order polynomials

###  V-A Preprocessing

In order to interpolate curves with polynomials, a data structure has been
created to facilitate processing on the one hand and to save the results
obtained on the other hand. This data structure (”gpts”) consists of an
integer field named ”type”, which will contain the type of the primitive
according to the marking carried out in the previous step. An integer field
named ”id”, which will contain the identifier of the first point of the
primitive. An integer field named ”nbr”, which will contain the number of
points belonging to this primitive as well as two other fields ”paramX” and
”paramY”, which will be used to store the coefficients of polynomials
associated with turns. After the structure is created, the fields were
subsequently assigned according to algorithm 3.

For each left-handed or right-turn type primitive, we will proceed to the
parameterization according to the length of the arc, so we will have two
polynomials according to $x$ and $y$ such that:

$\displaystyle\left\\{\begin{array}[]{ll}x(s)=a_{0}+a_{1}s+a_{2}s^{2}+a_{3}s^{3}\\\
y(s)=b_{0}+b_{1}s+b_{2}s^{2}+b_{3}s^{3}\end{array}\right.$ (13)

The polynomials in question will be of degree 3, this choice can be justified
by the absence of inflection points since the primitives have been classified
according to their (there is not a transition in the same road segment). They
are convex or concave curves hence the choice of the polynomial regression
that is a statistical analysis that describes the variation of an dependent
random variable, called here $x$ or $y$, according to an independent random
variable, called here $s$, being the length of the arc. We seek, by
regression, to bind the variables by a polynomial of degree 3. The calculation
of the coefficients therefore amounts to solving a system of equations that
can be expressed in the following matrix form:

$\begin{pmatrix}x_{1}\\\ x_{2}\\\ \vdots\\\
x_{n}\end{pmatrix}=\begin{pmatrix}1&s_{1}^{1}&s_{1}^{2}\cdots&s_{1}^{m}\\\
1&s_{2}^{1}&s_{2}^{2}\cdots&s_{2}^{m}\\\ \vdots&\vdots&\ddots&\vdots\\\
1&s_{n}^{1}&s_{n}^{2}\cdots&s_{n}^{m}\\\ \end{pmatrix}\begin{pmatrix}a_{0}\\\
a_{1}\\\ \vdots\\\ a_{m}\end{pmatrix}$ (14)

The number $m=3$ corresponds, in our case, to the cubic polynomial regression.
We will treat the case of the polynomial $x(s)$ generated and it is the same
for $y(s)$. The problem is therefore to find the vector $\vec{a}$ in the
equation:

$\vec{x}=S\vec{a}$ (15)

The solution is given by:

$\vec{a}=(S^{T}S)^{-1}S^{T}\vec{x}$ (16)

###  V-B Error criterion

Given the needs and requirements of the realism imposed on the generated road,
we set ourselves the objective of approximating the GIS input data with lines
and polynomials of third degrees such that the maximum deviation between the
two curves does not exceed 2.0m, in this part we discuss the calculation of
error as well as treatments to be undertaken in the case of exceeding this
limit.

####  V-B1 Error computation

The error $d$ is estimated as the distance between the approximate point
$p=(x,y)$ and the entry point $p=(x,y)$, it is deduced according to the
following formula:

$d=\sqrt{(\hat{x}(s)-x(s))^{2}+(\hat{y}(s)-y(s))^{2}}$ (17)

The maximum value of this error must not exceed $\delta$ for each of the
points of the different right or polynomial primitives.

$d_{max}<\delta$ (18)

####  V-B2 Error processing

Primitives whose error exceeds the required threshold must be modified, for
this our approach is to generate from the initial primitive two primitives
such that the number of points constituting each primitive is equal to half
the number of points of the primitive. For a given primitive $C_{m}$ one
generates two primitives $C_{m/2}$ and $C_{m/2}^{\prime}$, and the same
treatment will be executed on the two new primitives in a recursive way, this
will assure us:

  * •

Compliance with the error limit required for each final primitive obtained,

  * •

The generation of a minimal number of primitives,

##  VI Results

The results obtained when applying our method are summarized in Figure (3).
The figures show the stages of our approach. Figure (3(a)) shows a sample of a
road polyline. In Figure (3(b)), the curvatures were estimated by the least
squares method. Note that this representation is more exploitable than that of
Figure (1), and that there is less disturbance in the values of the curvatures
due to windowing.

###  VI-A Curvature estimation by the implicit parabola fitting method

In order to overcome the problems encountered when calculating the curvature
by cubic splines, we opted for an estimation of the latter by the least
squares. Compared with spline, the quality of curvature values improved
significantly. Indeed, most points follow the trend of the turn where they
belong as can be seen in Figure (3(b)). Nevertheless, in the case of more
complex turns, outliers appear. Hence, we have proposed to neglect them, and
to mark a window by a single sign of curvature relative to reality.

###  VI-B Clustering

Figure (3(c)) shows that the points of the input road were grouped into three
basic categories: left turn, right turn, and straight line. We note that the
results are more refined, because this step corrects any possible residual
error of the previous section. Moreover, it allows noise reduction, by
defining the straight line segments from a given threshold, since the SIG data
being noisy, we cannot obtain zero curvature values.

This step allowed us to have the same signs of curvature for a given type of
cluster. Nevertheless, at this stage the clusters are not connected to each
other, a major problem on which the approximation will be based in the
following phases.

To overcome the problem of connection, we fix first the ends of the
primitives, then we approximate the calculated model of the initial points. In
this perspective, the Bezier curves with a least squares approximation prove
to be an adequate choice. Indeed, the first and last control point are
superimposed on their correspondents in the initial data, then the other
points are calculated by minimizing the differences between the model and the
initial data. The main disadvantage of this method is that it guaranties only
$C_{0}$ continuity between two clusters of successive points, which does not
satisfy civil engineering constraints. Moreover, in some complex turns, it
remains difficult to follow the shape of the cluster by a third degree
polynomial.

Figure (3(g), 3(h)) represents the constructed road. The initial data points
circled and clustered. Note that the resulting model does not deviate from the
input road polyline. The curves in magentas represent the edges of the road,
the input data (polylines) are in red, and the model (at the central axis) is
in blue. Figure (3(h)) illustrates the mapping of the road to the geo-
referenced satellite image corresponding to the road section. As can be seen,
the model provides a smooth representation of the road surface. We see that
complex shapes such as turns are well approximated. In addition, our model
meets the $C_{2}$ continuity (imposed by road civil engineering), along the
road without oscillations or other erratic behaviors that would compromise the
visual comfort during the simulation.

##  VII Conclusion and future works

The objective of this work was the realistic modeling of the road surface by
taking into account a number of civil engineering and vehicle dynamics
constraints. We chose curvature as a parameter describing the shape of the
road in order to approach the profile of the latter as closely as possible.

We proceed through the estimation of curvature by a windowing approach because
of the discrete nature of GIS data. In order to approach the reality, we
grouped the points into clusters according to their neighborhood’s curvature
to obtain basic forms of the road namely left/right turns and straight lines.

This being done, the next step was to find the mathematical functions as well
as the appropriate conditions and constraints to approach the initial data
with functions that respect $C_{2}$ continuity conditions.

The results obtained are satisfactory insofar as our road reconstruction
approach takes into account the real constraints, moreover the model obtained
is of $C_{2}$ continuity, which reflects the smoothness of the position, speed
and the acceleration of the simulated vehicle.

As a perspective, we plan to improve and refine this work by considering road
intersections, since the latter are frequently encountered in a real-life
situation.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 3: Processing steps of the proposed algorithms. (a) Raw road in
polyline form, (b) Curvature obtained by least squares according to the
normal, (c) Cutting of the road (left, right turns and straight lines)
according to curvature values, (d) Turns detected by the cutting algorithm,
(e) Polynomial fitting of the detected turns, (f) 3rd degree polynomials
approximation of a given turn, (g) Result: generated road surface, (h) Mapping
of the result on a real road

## References

  * [1] Yoav IH Parish and Pascal Müller  “Procedural modeling of cities”  In _Proceedings of the 28th annual conference on Computer graphics and interactive techniques_ , 2001, pp. 301–308  ACM
  * [2] Jing Sun, Xiaobo Yu, George Baciu and Mark Green  “Template-based generation of road networks for virtual city modeling”  In _Proceedings of the ACM symposium on Virtual reality software and technology_ , 2002, pp. 33–40  ACM
  * [3] Guoning Chen et al.  “Interactive procedural street modeling”  In _ACM transactions on graphics (TOG)_ 27.3, 2008, pp. 103  ACM
  * [4] Eric Galin, Adrien Peytavie, Eric Guérin and Bedřich Beneš  “Authoring hierarchical road networks”  In _Computer Graphics Forum_ 30.7, 2011, pp. 2021–2030  Wiley Online Library
  * [5] Eric Galin, Adrien Peytavie, Nicolas Maréchal and Eric Guérin  “Procedural generation of roads”  In _Computer Graphics Forum_ 29.2, 2010, pp. 429–438  Wiley Online Library
  * [6] Eric Bruneton and Fabrice Neyret  “Real-time rendering and editing of vector-based terrains”  In _Computer Graphics Forum_ 27.2, 2008, pp. 311–320  Wiley Online Library
  * [7] Hoang Ha Nguyen, Brett Desbenoit and Marc Daniel  “Realistic road path reconstruction from GIS data”  In _Computer Graphics Forum_ 33.7, 2014, pp. 259–268  Wiley Online Library
  * [8] Jie Wang, Gary Lawson and Yuzhong Shen  “Automatic high-fidelity 3D road network modeling based on 2D GIS data”  In _Advances in Engineering Software_ 76 Elsevier BV, 2014, pp. 86–98  DOI: 10.1016/j.advengsoft.2014.06.005
  * [9] Thomas Lewiner, João D. Gomes, Hélio Lopes and Marcos Craizer  “Curvature and torsion estimators based on parametric curve fitting”  In _Computers & Graphics_ 29.5 Elsevier BV, 2005, pp. 641–655  DOI: 10.1016/j.cag.2005.08.004