Q:

What is the difference between 4-point and 8-point connectivity in graph based planning?

In graph-based planning (say, A*), states are connected to their neighbors.  How should one decide whether to connect to the 4 neighbors or the 8 neighbors?  What are the pros and cons of each approach?

A:

I believe it simply boils down to what your robot can do.
If you are for some reason restricted to moving only in 4 directions, then you connect each grid cell to 4.
If you can go in 8 directions, you connect each grid cell to 8.
If you can go in 6 directions, you use a honeycomb grid and connect each grid cell to 6.
There is no generic answer. If you plan to go diagonally with a robot that can't perform the action, that's bad planning. If you plan to only go horizontally and vertically while your robot can take shortcuts, that's also bad planning.

A:

Graph-based planning algorithms are typically performed for high level planning, for example getting a robot across an office. But, the actual actuator planning for the robot is planned completely differently. This means it completely depends on your application and your desired level of complexity. If you have a grid in which cells are either occupied or not occupied, you may not want your robot transitioning diagonally for fear of collision with the neighboring cells. 
In technical terms, it doesn't matter at all if you use 4 or 8 way connectivity for algorithms like A*.

