Borderline-based Penalization

[jara001]

In f3f53e9 a support for generating borderlines was added to Flood Fill segmentator, followed by its support for Matryoshka in 27483cd.

The idea for different penalization originates from the issues of the current one. Current one works as follows:

• Obtain candidate.
• Interpolate it using selected interpolator.
• Set _invalidpoints to 0.
• For each point in the interpolation:
  • Find out whether it is in proximity of any valid point (proximity is the grid size).
    • If not, add 1 to the _invalidpoints.
• If _invalidpoints > 0:
  • set fitness to PENALTY * _invalidpoints
• Otherwise set fitness to the one returned by the criterion.

This works quite fine, especially when a correct solution is found. However when it is not able to find a correct solution, penalization by the number of incorrectly placed may keep it in a local minimum / do not push it to the correct solutions. For an example see following figure:

Since the width of the wall is constant, there is no way for the algorithm to find out how to get a correct solution.

Therefore a new penalization was implemented, using so-called borderlines. Borderlines are sets of points on the borders between to adjacent segments. We have borderlines for each segment and for each neighbour (usually resulting into n * 2 arrays).

For each invalid point we find out its "position" regarding the segments and then we find its closest "neighbour" in the appropriate borderline.

Note: "Segment position" is found using its index in the line and by detecting between which candidate points is it located.

Borderline-based penalization works in some cases like:

However it still has its limitations:

Let me note that the PENALTY was set to 1000 in these experiments, as otherwise the fitness value would be too small. Maybe increasing it will help a little bit as well.

Both images suggest that this penalization "allows small wall collisions" as the results are "better" then correct solutions. Both lines above had their fitness a little bit over 40 (correct solution has around 26).

As a future work it would be nice to try finding the distance to an appropriately selected part of the centerline instead, as I expect that the results could be better.

Borderlines were tested using:

{
    "_version": 2,
    "_comment": "Experiment with MM+borderlines and Curvature2.",
    "loops": 10,
    "groups": -3,
    "interpolator": "cubic_spline",
    "segmentator": "flood_fill",
    "selector": "curvature2",
    "selector_args": {
        "plot": false,
        "point_distance": 0.1,
        "sampling_distance": 1.0,
        "peaks_height": 0.4,
        "peaks_distance": 16,
        "peaks_bounds": 20,
        "peaks_merge": 1.5,
        "peaks_filling": 10.0
    },
    "penalty": 1000,
    "use_borderlines": true,
    "cascade": [
        {
            "algorithm": "matryoshka",
            "budget": 3000,
            "layers": 5,
            "criterion": "profile",
            "criterion_args": {
                "overlap": 100
            },
            "criterion_init": {
                "_dummy": 0
            }
        },
        {
            "algorithm": "matryoshka",
            "budget": 1000,
            "layers": 5,
            "criterion": "profile",
            "criterion_args": {
                "overlap": 100
            },
            "criterion_init": {
                "_dummy": 0
            }
        }
    ],
    "start_points": "ng_start_points_torino2.npy",
    "valid_points": "ng_valid_points_torino2.npy",
    "logging_verbosity": 2,
    "hold_map": true,
    "plot": true,
    "plot_args": [
        {
            "_figure": {
                "function": "axis",
                "_args": [ "equal" ]
            },
            "trackPlot": [ "@track" ],
            "pointsPlot": {
                "_args": [ "@result" ]
            }
        },
        {
            "pointsPlot": {
                "_args": [ "@result" ]
            },
            "pointsScatter": {
                "_args": [ "@rcandidate" ]
            }
        }
    ],
    "prefix": "matcur21B"
}

[jara001]

Borderline penalizer was mostly finished in 97ca3362a956632ffac29d90697f788b79fa3c54. Centerline penalizer was added in ec4c54a72b8095f92419fef3810e8f4cfb3dd8db.