pathfinding_tutorial

Pathfinding

The problem we want to solve is to get from a starting point to a goal point avoiding obstacles.

---

NOTE. There are many efficient, ad-hoc algorithms (e.g. A*) that should be preferred for real pathfinding tasks, but this is a good example of the flexibility of GA.

---

The general idea is to consider an individual as a sequence of moves on a grid:

individual = {north, north, west, south, east, south... }

The direction of the i-th move / step of a path can be represented by an enum:

enum cardinal_dir {north, south, west, east};  // an integer in the [0, 4[ interval

The chromosome/individual will contain a sequence of cardinal_dirs (with a one-to-one relationship between a locus of an individual and a step of the path).

Now the question is: what is the maximum path length?

The answer has a direct impact on the size of an individual / chromosome. The optimal solution cannot be longer than the number of cells on the grid (m.size() * m[0].size()).

That, despite being a rough approximation, is enough for an example:

const auto length(m.size() * m[0].size());
ga_problem prob(length, {0, 4});

The run function performs, on the map/grid, the moves encoded in an individual (from a starting point to the final point reached):

std::tie(final_cell, length_of_path) = run(individual, maze, start, goal)

run simply ignores slamming-into-the-wall-moves.

The fitness function is:

auto f = [maze, start, goal](const i_ga &x)
{
  const auto final(run(x, maze, start, goal));

  return -distance(final.first, goal) - final.second / 1000.0;
};

We minimize:

• primary objective - the distance to the goal point
• secondary objective - the total length of the path (soft constraint, hence the 1 / 1000.0 scaling factor).

Our map is actually a maze:

encoded as a 2D grid (a vector of strings):

const cell_coord start{0, 0}, goal{16, 8};
const maze m =
{
  " *       ",
  " * *** * ",
  "   *   * ",
  " *** ****",
  " *   *   ",
  " ***** **",
  "   *     ",
  "** * ****",
  "   * *   ",
  "** * * * ",
  "   *   * ",
  " ******* ",
  "       * ",
  "**** * * ",
  "   * * * ",
  " *** * **",
  "     *   "
};

The full source for this example is contained in the examples/pathfinding01.cc file.

As you can see a small population can find, in a few generations, a good solution (in the example it isn't the best one since there is a small detour):

-----------
|S*       |
|.* *** * |
|.  *   * |
|.*** ****|
|.*   *   |
|.***** **|
|...*     |
|**.* ****|
|...* *   |
|**.* * * |
|...*   * |
|.******* |
|.......* |
|**** *.* |
|   * *.* |
| *** *.**|
|     *..G|
-----------

---

We can try with a more challenging maze:

The maze is larger and has a peculiarity: the previous best path now leads to a local optimum (a dead end very near the goal cell).

Executing multiple runs, it becomes clear that, in the current form, it's very difficult for the GA to reach the goal.

As always a full spectrum of general approaches can be experimented:

• bigger population / more generations
• higher mutation rate
• different evolutionary strategy (e.g. vita::alps_es instead of vita::std_es)
• specific crossover / mutation operator
• a gene repair operator which erases bad moves (instead of ignoring them) and fills up the individual.

However a simple observation is very clarifying: increasing the maximum length of a path up to (at least):

const auto length(m.size() * m[0].size() * 4);

allows to consistently find a solution. So the real problem is in the adopted encoding scheme.

To take advantage of the nature of the maze we change the meaning of cardinal_dir. Now (to the run function) west will mean: walk westbound till hitting a wall / reaching a crossing. This allows to store in a single locus what previously required multiple steps (loci).

The modification is very effective:

-------------------
|S*.......        |
|.*.*** *.********|
|...*   *.........|
| *** *********.*.|
| *   *.......*.*.|
| *****.*****.***.|
|   *...    *.*...|
|** *.***** *.*.* |
|   *.*...* *.*.* |
|** *.*.*.* *.*.* |
|   *...*.* *...* |
| *******.********|
|       *.*.......|
|**** * *.*.*****.|
|   * * *...*   *.|
| *** * ***** * *.|
|     *       * *G|
-------------------

As before the solution could be sub-optimal but it's often quite good.

The full source code for the improved example is contained in the examples/pathfinding02.cc file.