M4-T1 — Why Sample? High-Dimensional and Continuous Spaces

Learning objectives

After this lesson, you should be able to:

• Explain with numbers why the cell count of a grid grows exponentially with the dimension of the configuration space.
• State what sampling-based planners give up and what they gain compared with grid search.
• Define probabilistic completeness and resolution completeness, and say what each does not promise.
• Decide when a grid planner is still the right choice.

The intuition

Imagine searching a building for a lost badge. On a grid you check every square metre of every floor, in order. That is thorough and, for one building, perfectly reasonable. Now the badge could be in any of a hundred buildings, on any of a hundred floors, in any of a hundred rooms, in any of a hundred drawers, and you must report back the exact route to it. Checking every drawer takes longer than the lifetime of the hospital.

A sampling planner behaves like a person who walks to random places, notes which ones are open and which are locked, and links the open ones that are close together. It never checks everything. It stops as soon as a chain of open places connects the start to the goal. The price is that the chain is whatever happened to be found first, and that if the only door is very narrow, it may take many random tries before one lands in it.

The picture below counts the cells. Take 100 values per dimension, which is only 10 cm resolution over a 10 m range. The count is 100 to the power of the number of dimensions, and that line on a logarithmic axis is straight and steep.

The mathematics

The configuration space and its size

The configuration of a robot is the smallest set of numbers that fixes where every part of it is (lesson M1-T5). A planar disc robot has two numbers, a rectangle that can rotate has three, an arm has one per joint. A grid with m values per dimension over d dimensions has

m

number of values per dimension (range divided by resolution).

d

dimension of the configuration space.

C_free

the set of collision-free configurations.

ε

the fraction of the space taken by a region we must hit, such as a narrow passage.

A search needs memory for the cells it has seen and time to expand them, so the cost is at least proportional to the part of the grid it touches. In the worst case, that is all of it.

What a sampling planner needs

Sampling planners do not store the free space. They need only three operations that the robot’s model can supply cheaply:

• Sample: draw a configuration, usually uniformly at random, sometimes with a bias towards the goal.
• Collision test: is this configuration free? (lesson M4-T2).
• Local connection: can I move from configuration a to configuration b along a simple curve, such as a straight line, without hitting anything?

The set of free configurations stays implicit. It is explored through these calls, so the cost depends on how many calls are made, not on the size of the space.

What is given up, what is gained

Probabilistic completeness

A planner is probabilistically complete if, whenever a solution exists, the probability that it has found one tends to 1 as the number of samples tends to infinity. It is silent when no path exists: no finite number of failures proves it. Compare resolution completeness for grids: a path is found if one exists at the chosen cell size, and a corridor narrower than a cell is invisible.

The speed of convergence depends on how much of the space the solution needs. If a passage takes a fraction ε of the space, then the probability that n independent uniform samples contain at least one inside it is

A worked example

The cell count of a tug. Scout’s tug lives in a 10 m × 10 m yard and must also track its heading. At a resolution of 0.05 m and 2° the grid has (10 / 0.05) × (10 / 0.05) × (360 / 2) = 200 × 200 × 180 = 7.2 million cells. That is large but fine, and it is why grid planners such as Hybrid A* still work for cars (lesson M4-T6). An arm with 6 joints and 100 values each has 100⁶ = 10¹² cells: at a million cell expansions per second a full sweep would take 10⁶ seconds, about 11.6 days, and the memory for a single bit per cell would already be 125 GB.

Hitting a doorway. Suppose a doorway takes ε = 0.1% of the free space, so 0.001. One uniform sample lands in it with probability 0.001. Then

With 1000 samples the chance of at least one landing in the doorway is 1 − 0.999¹⁰⁰⁰ = 0.632. This is the narrow-passage problem: the planner needs several thousand samples, in 2D that is cheap, but the same fraction in a high-dimensional space is common, and so are tricks that sample near obstacles or bridge narrow gaps.

The same dock, two answers. In lab M4-L2 an RRT crosses a 10 m × 6 m loading dock with a few hundred nodes, and the first path it finds is about 1.6 times the shortest route (16.6 m against 10.45 m). Run on another seed and it is a different path. A grid planner on the same dock would return the same, shorter, path every time at a cost of 100 × 60 = 6000 cells at 0.1 m. In two dimensions the grid wins; the point of sampling is the dimensions in which it cannot be used.

Engineering implications and limitations

Use the grid when the grid fits

For a mobile robot on a floor map, two or three dimensions, a costmap that the rest of the stack already maintains, and a need for the same answer twice, a grid planner is the better engineering choice (module 3). Sampling is for arms, for many-joint mechanisms, and for vehicles whose motion constraints make the search space continuous (lesson M4-T5).

The collision checker is the cost

In a typical sampling planner most of the run time is spent testing configurations and edges for collisions, often over ninety percent. Budget for it: a faster checker is worth more than a cleverer sampler (lesson M4-T2).

Reproducibility and testing

Random planners make failures hard to reproduce. Log the seed with every plan, let tests fix it, and report success rates over many seeds, not one run. In the labs the page supplies the random numbers for exactly this reason.

Set a time limit and keep the first answer

Sampling planners are anytime: they can be stopped at a deadline and return the best path so far, or none. Decide what the robot does when none exists: replan, widen the search, or stop and ask for help (module 7).

Common misconceptions

Engineering takeaways

1. A grid with m values in d dimensions has m^d cells, so it fails for arms and other high-dimensional systems.
2. Sampling planners need only a way to draw configurations, test them and connect two of them; they never store the free space.
3. They are probabilistically complete, not optimal and not repeatable unless the seed is fixed.
4. Narrow passages are the weak spot: the number of samples needed grows like 1 / ε.
5. For floor maps in two or three dimensions a grid planner is usually the better tool.

References and further reading

The classic planning texts and the two papers that introduced the sampling methods.

• S. M. LaValle, “Planning Algorithms”, Cambridge University Press, 2006 (free online), chapters 5 and 14.
• L. E. Kavraki, P. Švestka, J.-C. Latombe and M. H. Overmars, “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces”, IEEE Transactions on Robotics and Automation, 12(4), 1996.
• S. Karaman and E. Frazzoli, “Sampling-based Algorithms for Optimal Motion Planning”, The International Journal of Robotics Research, 30(7), 2011.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: the operation that sampling planners call most often, the collision check.

Related content

Nothing below is required to finish this lesson.

• Lab
  M4-L2: Grow an RRT

  Find a way through the loading dock with random sampling, and see why it finds a path but not a good one.