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 an a grid:

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

With Vita this can be done defining a new move class that encodes the i-th move / step of a path:

class move : public vita::ga::integer
{
public:
  enum cardinal_dir {north, south, west, east};

  move() : vita::ga::integer({0, 4})  {}

  /* ... */
};

A move is an integer terminal (vita::ga::integer with four distinct value) and, essentially, it's just syntactic sugar.

The chromosome/individual will contain a sequence of moves (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:

vita::problem prob;

const auto length(m.size() * m[0].size());
prob.chromosome<move>(length);

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 vita::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 (it isn't the best one since there is a small detour):

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

---

We can try with a more challenging maze:

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 std::size_t sup_length(m.size() * m[0].size() * 4);

allows GA 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 move class to a direction class. Now direction::west means (to the run function): walk westbound till hitting a wall / reaching a crossing. This allows to store in a single locus what previously required multiple steps (loci).

This simple modification is very effective:

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

As before this isn't the optimal solution but it's good enough.

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