The most popular approaches to make motion planning possible are sampling-based. This makes it more tractable and is more computationally efficient.

There are 2 main things that we use sampling for

1. Computing C-space obstacles is hard —> use a collision checker
2. Planning in continuous high-dimensional space is hard —> construct a discrete graph approximation

Graph Creation

First of all, to begin planning for our environment, we need a data structure to represent our configuration space. The graph is a great data structure for this, since we will then apply path searching algorithms on it to search for the most optimal paths (See Heuristic Search)

Lattice Sampling

One easy solution would be create a grid over the space, with nodes evenly spaced through out.

Edges of a node are connected with every neighbouring node

This is however very computationally intensive over a large configuration space, nearly impossible in navigation tasks

Uniform Random Sampling

We sample the space uniformly and place nodes on the sampled points.

Then, we simply connect vertices within a certain radius (r-disc) or k nearest neighbors.

This can help tackle large configuration spaces.

However, note that uniformly random is not always desirable as it leaves a lot of space unexplored.

To evaluate why the 2 above strategies both have undesirable effects, let’s formalise our objective in the graph creation problem.

We want to create a graph that do not leave large unexplored spaces, we quantify this by a large pink circle. A good graph should be sparse and free-space coverage and connectivity

• In the lattice strategy, the pink ball is quite small.

  However, it can be observed that the path cannot be on the be as close to the obstacles as the optimal path should be, as the graph is structured and aligned with the obstacles.

  In the most adversarial case, due to the standard structure of the lattice, the nodes can all lie in long rectangular obstacles laid over the space. No solution can be derived.

• In the uniformly random sampling strategy, it can observed that the pink ball has a large size. This shows that it left lots of unexplored space and is not desirable.

Low-Dispersion Sampling

One such sampling sequence is the Halton sequence

This is so far the best strategy presented. The intuition is that the $i+1^{th}$ point is selected to be the center of the pink circle.

Steering and Collision Detection