# AI Project - Bicycle Route Search GA

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

## Licensing

- to be decided

## Build Requirements

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

- Boost - version 1.68.0 or higher (with modules `program_options` and `system`)
- OpenMP
- bzip2
- zlib
- Expat

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.

## Submodules

Other dependencies are included as Git submodules:

- [ExprTk](https://github.com/ArashPartow/exprtk) - for convenient grade function user input
- [JSON for Modern C++](https://github.com/nlohmann/json) - for reading of Overpass map and input configuration files
- [libfort](https://github.com/seleznevae/libfort) - for table printouts in log messages

Use the `--recursive` flag while issuing `git clone` or call `git submodule update --init --recursive` separately to fetch them.

## Building

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

    mkdir build && cd build

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

    cmake .. -G "Unix Makefiles"

Finally, run:

    make -j <BUILD_PROCESS_COUNT>

## Usage

The algorithm is run using the following command:

    ai_project_evolve -c <CONFIG_FILE>

`<CONFIG_FILE>` is a path to the input configuration JSON file, which may look the following way:

```
{
  "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
}
```

### Explanation:

- `map_path` - path to the **preprocessed** OSM JSON map file (relative to the config file) ([Wiki](https://wiki.openstreetmap.org/wiki/OSM_JSON))
  - the preprocessed OSM JSON file is created using:
    1. `script/download_elevation/download_elevation.html` - to add non-standard `"ele"` values to nodes (from [Mapy API](https://api.mapy.cz/), allowing ~10 nodes/s)
    2. `ai_project_preprocess` - to "normalize" the ways in the followind steps:
       1. split ways on junctions
       2. concatenate ways on non-junctions
- **`parameters` - the user input parameters of the desired route**
  - **`points` - a list of WGS84 transit points to which all routes will be constrained**
    - each point is snapped to the map by finding the closest junction node
  - **`distance` - the desired route distance [km]**
  - `grade`
    - **`function` - the (partial) grade function (km to %) in [ExprTk format](https://github.com/ArashPartow/exprtk)**
    - `sampling_step` - the interval at which the above function will be sampled [km]
    - `max_misalignment` - the maximum allowed misalignment of the grade function and the route [km]
  - `way_type_preferences` - weights of way types in non-deterministic heuristics (initialization, mutation); not used by the cost function
    - the available types are `unclassified`, `primary`, `secondary`, `tertiary`, `trunk_link`, `primary_link`, `secondary_link`, `tertiary_link`, `residential`, `living_street`, `cycleway`, `service`, `track` ([Wiki](https://wiki.openstreetmap.org/wiki/Key:highway))
    - if not mentioned, the value defaults to `1`
- `output_path` - the path of the root output folder (relative to the config file), containing:
  - `iteration_*` folders, containing:
    - `place_*.gpx` files - solutions sorted by cost in ascending order
    - `info.csv` - statistics table about the solutions, i.e. total cost, distance cost, grade cost, distance, elevation and corresponding medians, means and standard deviations
  - `initial` - symlink to `iteration_0`
  - `final` - symlink to `iteration_<iteration_count>`
  - `place_*.gpx` - symlink to `iteration<iteration_count>/place*.gpx`
  - `info.csv` - symlink to `iteration<iteration_count>/info.csv`
- `output_verbosity` - flags to filter the introspection output:
  - `none` - no output
  - `all` - combination of:
    - `save_all` - combination of
        - `save_solutions` - combination of:
            - `save_initial_solutions`
            - `save_intermediate_solutions`
            - `save_final_solutions`
        - `save_info` - combination of:
            - `save_initial_info`
            - `save_intermediate_info`
            - `save_final_info`
    - `log_all` - combination of:
        - `log_info` - combination of:
            - `log_initial_info`
            - `log_intermediate_info`
            - `log_final_info`
        - `log_phases` - log which phase is currently in progress (initialization, recombination, etc.)
        - `log_iterations` - log which iteration is currently in progress
        - `log_time` - log the time taken for the whole algorithm
  - `initial_info` - combination of `save_initial_info` and `log_initial_info`,
  - `intermediate_info` - combination of `save_intermediate_info` and `log_intermediate_info`
  - `final_info` - combination of `save_final_info` and `log_final_info`
  - `info` - combination of `final_info` and `intermediate_info`
  - `initial` - combination of `save_initial_solutions` and `initial_info`
  - `intermediate` - combination of `save_intermediate_solutions` and `intermediate_info`
  - `final` - combination of `save_final_solutions` and `final_info`
- **`iteration_count` - the number of iterations to perform (`0` - initialization only)**
- `initial_count` - size of the initial population
- `final_count` - the number of final outputs
- `thread_count` - the number of threads to use for parallelizable tasks, i.e. recombination, cost function computation and output serialization
- `*_factor` - various exponential and multiplicative factors - additional hyperparameters
- `reproducing_ratio` - the ratio of solutions in a given population that will reproduce
- `remove_duplicates` - enables/disables duplicate solution removal after crossover and mutation to boost diversity
- `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
- `deterministic` - a boolean flag whether to guarantee that for the same input, the output will be the same each time

## Evaluation

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

    ai_project_evaluate -c <CONFIG_FILE>

`<CONFIG_FILE>` is a path to the input configuration JSON file, which is very similar to the config file for the evolution itself:

```
{
  "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
}
```

### Explanation:

- `parameters` - mixed parameters for generation, as well as evaluation
  - `point_count` - the number of transit points that will be deduced (min. `2`)
  - `distance` - the **approximate** distance of the tested route
  - `grade`
    - `defined_portion` - the **approximate** portion of grade samples, which are defined
    - `distance_per_interval` - the mean distance of intervals, which are used to deduce the grade input
      - intervals are randomly cleared to NaN, until the desired `defined_portion` is reached (crossed from above)
- `output_path` - the path of the root output folder (relative to the config file), containing:
  - `case_*` - output folder for each case, additionally containing:
    - `expected.gpx` - the route from which the input parameters for this case were generated
    - `similarity.csv` - the results of measuring similarity between the final solutions and the expected route (including mean, median and standard deviation)
  - `similarity.csv` - aggregation of the best similarity results from each case
- `run_count` - the number of cases to run

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