\section{AI Project - Bicycle Route Search
GA}\label{ai-project---bicycle-route-search-ga}

An implementation of multiple-solution route-finding (genetic) algorithm
for cyclists.

\subsection{Licensing}\label{licensing}

\begin{itemize}
\tightlist
\item
  to be decided
\end{itemize}

\subsection{Build Requirements}\label{build-requirements}

The project requires C++17 standard support. Furthermore, it requires
the following libraries to be installed on the system:

\begin{itemize}
\tightlist
\item
  Boost - version 1.68.0 or higher (with modules
  \texttt{program\_options} and \texttt{system})
\item
  OpenMP
\item
  bzip2
\item
  zlib
\item
  Expat
\end{itemize}

These prerequisities are contained within a custom-made docker image -
https://gitlab.fi.muni.cz/xsevc/ai-project-docker. A built docker image
can be found at https://hub.docker.com/r/sevc/ai-project.

\subsection{Submodules}\label{submodules}

Other dependencies are included as Git submodules:

\begin{itemize}
\tightlist
\item
  \href{https://github.com/ArashPartow/exprtk}{ExprTk} - for convenient
  grade function user input
\item
  \href{https://github.com/nlohmann/json}{JSON for Modern C++} - for
  reading of Overpass map and input configuration files
\item
  \href{https://github.com/seleznevae/libfort}{libfort} - for table
  printouts in log messages
\end{itemize}

Use the \texttt{-\/-recursive} flag while issuing \texttt{git\ clone} or
call \texttt{git\ submodule\ update\ -\/-init\ -\/-recursive} separately
to fetch them.

\subsection{Building}\label{building}

First, create and switch to a directory for an out-of-source build:

\begin{verbatim}
mkdir build && cd build
\end{verbatim}

Now, generate the build system files via CMake, e.g.:

\begin{verbatim}
cmake .. -G "Unix Makefiles"
\end{verbatim}

Finally, run:

\begin{verbatim}
make -j <BUILD_PROCESS_COUNT>
\end{verbatim}

\subsection{Usage}\label{usage}

The algorithm is run using the following command:

\begin{verbatim}
ai_project_evolve -c <CONFIG_FILE>
\end{verbatim}

\texttt{\textless{}CONFIG\_FILE\textgreater{}} is a path to the input
configuration JSON file, which may look the following way:

\begin{verbatim}
{
  "map_path": "../maps/cr_regions/jihomoravsky.json",
  "parameters": {
    "points": [
      { "lat": 49.2072808, "lon": 16.6019825 },
      { "lat": 49.3351631, "lon": 16.7180686 },
      { "lat": 49.2072808, "lon": 16.6019825 }
    ],
    "distance": 60,
    "grade": {
      "function": "0",
      "sampling_step": 0.01,
      "max_misalignment": 1
    },
    "way_type_preferences": {
      "trunk_link": 0.5,
      "primary_link": 0.5,
      "residential": 0.5,
      "cycleway": 0.5,
      "service": 0.25,
      "track": 0.5
    }
  },
  "output_path": "../outputs/kras",
  "output_verbosity": ["log_time", "final"],
  "iteration_count": 100,
  "initial_count": 1000,
  "final_count": 10,
  "distance_cost_factor": 1;
  "grade_cost_factor": 1;
  "crossover_probability_factor": 1;
  "mutation_probability_factor": 1;
  "way_initialization_reuse_cost_factor": 1;
  "way_mutation_reuse_cost_factor": 1;
  "reproducing_ratio": 0.5;
  "remove_duplicates": true,
  "fill_missing": true,
  "thread_count": 1,
  "deterministic": true
}
\end{verbatim}

\subsubsection{Explanation:}\label{explanation}

\begin{itemize}
\tightlist
\item
  \texttt{map\_path} - path to the \textbf{preprocessed} OSM JSON map
  file (relative to the config file)
  (\href{https://wiki.openstreetmap.org/wiki/OSM_JSON}{Wiki})
\item
  the preprocessed OSM JSON file is created using:

  \begin{enumerate}
  \def\labelenumi{\arabic{enumi}.}
  \tightlist
  \item
    \texttt{script/download\_elevation/download\_elevation.html} - to
    add non-standard \texttt{"ele"} values to nodes (from
    \href{https://api.mapy.cz/}{Mapy API}, allowing \textasciitilde{}10
    nodes/s)
  \item
    \texttt{ai\_project\_preprocess} - to ``normalize'' the ways in the
    followind steps:
  \item
    split ways on junctions
  \item
    concatenate ways on non-junctions
  \end{enumerate}
\item
  \textbf{\texttt{parameters} - the user input parameters of the desired
  route}
\item
  \textbf{\texttt{points} - a list of WGS84 transit points to which all
  routes will be constrained}

  \begin{itemize}
  \tightlist
  \item
    each point is snapped to the map by finding the closest junction
    node
  \end{itemize}
\item
  \textbf{\texttt{distance} - the desired route distance {[}km{]}}
\item
  \texttt{grade}

  \begin{itemize}
  \tightlist
  \item
    \textbf{\texttt{function} - the (partial) grade function (km to \%)
    in \href{https://github.com/ArashPartow/exprtk}{ExprTk format}}
  \item
    \texttt{sampling\_step} - the interval at which the above function
    will be sampled {[}km{]}
  \item
    \texttt{max\_misalignment} - the maximum allowed misalignment of the
    grade function and the route {[}km{]}
  \end{itemize}
\item
  \texttt{way\_type\_preferences} - weights of way types in
  non-deterministic heuristics (initialization, mutation); not used by
  the cost function

  \begin{itemize}
  \tightlist
  \item
    the available types are \texttt{unclassified}, \texttt{primary},
    \texttt{secondary}, \texttt{tertiary}, \texttt{trunk\_link},
    \texttt{primary\_link}, \texttt{secondary\_link},
    \texttt{tertiary\_link}, \texttt{residential},
    \texttt{living\_street}, \texttt{cycleway}, \texttt{service},
    \texttt{track}
    (\href{https://wiki.openstreetmap.org/wiki/Key:highway}{Wiki})
  \item
    if not mentioned, the value defaults to \texttt{1}
  \end{itemize}
\item
  \texttt{output\_path} - the path of the root output folder (relative
  to the config file), containing:
\item
  \texttt{iteration\_*} folders, containing:

  \begin{itemize}
  \tightlist
  \item
    \texttt{place\_*.gpx} files - solutions sorted by cost in ascending
    order
  \item
    \texttt{info.csv} - statistics table about the solutions, i.e.~total
    cost, distance cost, grade cost, distance, elevation and
    corresponding medians, means and standard deviations
  \end{itemize}
\item
  \texttt{initial} - symlink to \texttt{iteration\_0}
\item
  \texttt{final} - symlink to
  \texttt{iteration\_\textless{}iteration\_count\textgreater{}}
\item
  \texttt{place\_*.gpx} - symlink to
  \texttt{iteration\textless{}iteration\_count\textgreater{}/place*.gpx}
\item
  \texttt{info.csv} - symlink to
  \texttt{iteration\textless{}iteration\_count\textgreater{}/info.csv}
\item
  \texttt{output\_verbosity} - flags to filter the introspection output:
\item
  \texttt{none} - no output
\item
  \texttt{all} - combination of:

  \begin{itemize}
  \tightlist
  \item
    \texttt{save\_all} - combination of

    \begin{itemize}
    \tightlist
    \item
      \texttt{save\_solutions} - combination of:

      \begin{itemize}
      \tightlist
      \item
        \texttt{save\_initial\_solutions}
      \item
        \texttt{save\_intermediate\_solutions}
      \item
        \texttt{save\_final\_solutions}
      \end{itemize}
    \item
      \texttt{save\_info} - combination of:

      \begin{itemize}
      \tightlist
      \item
        \texttt{save\_initial\_info}
      \item
        \texttt{save\_intermediate\_info}
      \item
        \texttt{save\_final\_info}
      \end{itemize}
    \end{itemize}
  \item
    \texttt{log\_all} - combination of:

    \begin{itemize}
    \tightlist
    \item
      \texttt{log\_info} - combination of:

      \begin{itemize}
      \tightlist
      \item
        \texttt{log\_initial\_info}
      \item
        \texttt{log\_intermediate\_info}
      \item
        \texttt{log\_final\_info}
      \end{itemize}
    \item
      \texttt{log\_phases} - log which phase is currently in progress
      (initialization, recombination, etc.)
    \item
      \texttt{log\_iterations} - log which iteration is currently in
      progress
    \item
      \texttt{log\_time} - log the time taken for the whole algorithm
    \end{itemize}
  \end{itemize}
\item
  \texttt{initial\_info} - combination of \texttt{save\_initial\_info}
  and \texttt{log\_initial\_info},
\item
  \texttt{intermediate\_info} - combination of
  \texttt{save\_intermediate\_info} and \texttt{log\_intermediate\_info}
\item
  \texttt{final\_info} - combination of \texttt{save\_final\_info} and
  \texttt{log\_final\_info}
\item
  \texttt{info} - combination of \texttt{final\_info} and
  \texttt{intermediate\_info}
\item
  \texttt{initial} - combination of \texttt{save\_initial\_solutions}
  and \texttt{initial\_info}
\item
  \texttt{intermediate} - combination of
  \texttt{save\_intermediate\_solutions} and \texttt{intermediate\_info}
\item
  \texttt{final} - combination of \texttt{save\_final\_solutions} and
  \texttt{final\_info}
\item
  \textbf{\texttt{iteration\_count} - the number of iterations to
  perform (\texttt{0} - initialization only)}
\item
  \texttt{initial\_count} - size of the initial population
\item
  \texttt{final\_count} - the number of final outputs
\item
  \texttt{thread\_count} - the number of threads to use for
  parallelizable tasks, i.e.~recombination, cost function computation
  and output serialization
\item
  \texttt{*\_factor} - various exponential and multiplicative factors -
  additional hyperparameters
\item
  \texttt{reproducing\_ratio} - the ratio of solutions in a given
  population that will reproduce
\item
  \texttt{remove\_duplicates} - enables/disables duplicate solution
  removal after crossover and mutation to boost diversity
\item
  \texttt{fill\_missing} - enables/disables supplying the current
  population with solutions discarded from the previous population
  (before crossover and mutation) in order to prevent premature
  convergence
\item
  \texttt{deterministic} - a boolean flag whether to guarantee that for
  the same input, the output will be the same each time
\end{itemize}

\subsection{Evaluation}\label{evaluation}

Evaluation is done by repeatedly running the algorithm using the
following command:

\begin{verbatim}
ai_project_evaluate -c <CONFIG_FILE>
\end{verbatim}

\texttt{\textless{}CONFIG\_FILE\textgreater{}} is a path to the input
configuration JSON file, which is very similar to the config file for
the evolution itself:

\begin{verbatim}
{
  "map_path": "../../maps/cr_regions/jihomoravsky.json",
  "parameters": {
    "point_count": 2,
    "distance": 50,
    "grade": {
      "defined_portion": 0.5,
      "distance_per_interval": 2,
      "sampling_step": 0.001,
      "max_misalignment": 0
    },
    "way_type_preferences": {
      "trunk_link": 0.1,
      "primary_link": 0.1,
      "residential": 0.1,
      "cycleway": 0.1,
      "service": 0.05,
      "track": 0.25
    }
  },
  "output_path": "../outputs/test",
  "iteration_count": 100,
  "initial_count": 1000,
  "final_count": 10,
  "distance_cost_factor": 1;
  "grade_cost_factor": 1;
  "crossover_probability_factor": 1;
  "mutation_probability_factor": 1;
  "way_initialization_reuse_cost_factor": 1;
  "way_mutation_reuse_cost_factor": 1;
  "reproducing_ratio": 0.5;
  "remove_duplicates": true,
  "fill_missing": true,
  "run_count": 10,
  "thread_count": 12,
  "deterministic": true
}
\end{verbatim}

\subsubsection{Explanation:}\label{explanation-1}

\begin{itemize}
\tightlist
\item
  \texttt{parameters} - mixed parameters for generation, as well as
  evaluation
\item
  \texttt{point\_count} - the number of transit points that will be
  deduced (min. \texttt{2})
\item
  \texttt{distance} - the \textbf{approximate} distance of the tested
  route
\item
  \texttt{grade}

  \begin{itemize}
  \tightlist
  \item
    \texttt{defined\_portion} - the \textbf{approximate} portion of
    grade samples, which are defined
  \item
    \texttt{distance\_per\_interval} - the mean distance of intervals,
    which are used to deduce the grade input
  \item
    intervals are randomly cleared to NaN, until the desired
    \texttt{defined\_portion} is reached (crossed from above)
  \end{itemize}
\item
  \texttt{output\_path} - the path of the root output folder (relative
  to the config file), containing:
\item
  \texttt{case\_*} - output folder for each case, additionally
  containing:

  \begin{itemize}
  \tightlist
  \item
    \texttt{expected.gpx} - the route from which the input parameters
    for this case were generated
  \item
    \texttt{similarity.csv} - the results of measuring similarity
    between the final solutions and the expected route (including mean,
    median and standard deviation)
  \end{itemize}
\item
  \texttt{similarity.csv} - aggregation of the best similarity results
  from each case
\item
  \texttt{run\_count} - the number of cases to run
\end{itemize}

The rest of the parameters is inherited from the evolution and each of
these parameters is passed as-is.
