pathfinding_tutorial

Pathfinding

The problem we want to solve is to get from a starting point to a goal point while 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 Genetic Algorithms (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, it's 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 moves that slam into walls.

The fitness function is:

auto f = [m, start, goal](const ga::individual &x)
{
  const auto final(run(x, m, 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 a good solution in a few generations (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 with:

• bigger population / more generations
• higher mutation rate
• 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 a consistent 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 or reaching a crossing. This allows soring 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.