Why are 'cell decomposition' methods in motion planning given the name, "combinatorial" motion planning?


2 Answers 2


Let's take a look what combinatorics is all about:

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

Cell decomposition (or any graph based motion planning for that matter) operates on some finite structure. That sounds plausible, as choosing from infinitely many options can be a hard thing to do.

Note that the countable discrete structure can contain elements that in some sense represent infinitely many choices. Say for example if each cell is a polygon and you want to find a path from one side to another one, there are infinitely many ways to do this, even if you use a straight line to connect the starting and end point. That's because each side of a polygon is a line and thus consist of infinitely many points that you could start from.

But the general structure is still finite, because you have a finite amount of cells.

Aspects of combinatorics include counting the structures of a given kind and size (enumerative combinatorics),

If they are countable, then they can be counted. It sounds trivial, but it is very important information. If you want to implement cell decomposition, you want to know what kinds of cells to expect and how many there are.

  • Are there 20 polygons with up to 6 sides each? Or 15000 cells given as analytical equations? Your choices for memory, processor and algorithms will likely be different for the two above.
  • You might have some concave cells. Maybe you want to decompose them further into convex cells. That increases the amount of cells that you are dealing with.
  • Some cells could be so small that your robot couldn't even enter them. Or could only access them from some sides. It the motion cannot happen on some cells, it doesn't make too much sense to include them for motion planning.

deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory)

Such criteria could be

  • the length of the path
  • the time it takes to travel along the path
  • the necessary turns
  • the width of the smallest passage in the path, if you want to carry that big box for example

finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization)

That seems to be the obvious one. It's often desirable to find the shortest path. But the shortest path is not necessarily the quickest one. Parcel delivery services for example calculate their routes by avoiding left turns in big cities. Maybe there's a path that's energetically optimal.

If there's a traffic jam on the freeway, what alternative route should people choose? It's likely a good idea to spread the throughput of traffic across many alternative paths, because a single road could not handle the amount of cars from a traffic jam on the freeway.


I'd guess it's because some use is made of the vocabulary (and perhaps even the tools) of the branch of mathematics called "combinatorial topology".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.