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?
What is the difference between 4-point and 8-point connectivity in graph based planning?
$\begingroup$ The question might be a bit too general, and would likely depend on the dynamics of the robot, as well as the internal representation of the environment (ie. whether it is even grid based). $\endgroup$– ronalchnOct 25, 2012 at 2:14
$\begingroup$ This question only makes sense if the environment is grid based. Additionally, assuming that the environment is meant to be grid-based, you could explain why it depends on the dynamics of the robot -- because even I don't see it. $\endgroup$– sylvain.joyeuxOct 25, 2012 at 6:04
$\begingroup$ Either use at least 8 direction or smooth the resulting path. $\endgroup$– danijarJan 20, 2014 at 20:48
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.
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*.
Assuming that (1) you are representing your environment as a grid (which is the only case where the 4-neighbor vs. 8-neighbor question makes sense) and (2) you are planning for navigation (which is the most common use case for grid-based representations)
I personally would not make much a case for 4-neighbour makes not much sense. What you would do by connecting only 4 neighbour per cell is force the robot to go only in "straight" directions. It is already a problem as it is with 8 neighbours, as one usually already has to "smooth" the result or use other approaches to interpret the resulting path.
Graph-based planning is a simplification of a space (that may be continuous) into the set of possible branching points, each representing the decisions that can be made. In a pure simulation, that simplification usually goes as far as working in terms of steps instead of distance or time. So, restricting movement to the 4 cardinal directions would be the correct choice because you'd want all the distances to be equal.
For a simulation with diagonals, it should still work -- provided that you adjust your algorithm so that diagonal step costs $\sqrt 2$ times more than the vertical/horizontal steps (which pushes you back in the direction of a continuous space, difficult to simulate). But it might make more sense to just adopt a hexagonal grid if you want more ways to move between squares. (For more discussion on grid types and their algorithms, see http://www-cs-students.stanford.edu/~amitp/game-programming/grids/)
You have a car-style robot -- front-wheel steering. You might represent 3 possible branches from each state: turn left, go straight, and turn right. In this case, a hexagonal grid would make the most sense; at every space, only 3 of the 6 neighbors would be valid and exactly which ones would depend on the direction you came from. This would reflect reality more than a cardinal-directions grid because to reach the space to your immediate right (or left) would require a U-turn over a few extra spaces.
You have a gantry robot -- X and Y actuation. In this case, both motors can be active at once, so moving diagonally "costs" the same as moving vertically or horizontally. The 8-neighbor square grid would be correct.
You are simulating a large room with some objects that move. If you allow diagonal movement, you lose the ability to use an integer for the time component -- things would end up only partway between squares. The 4-neighbor square grid would be correct.
In generally there is difference between 4 and 8 neighborhood in many algorithms which are graph based, (such as A*, MRF(markov random field), edge detection algorithm and etc).
This depend on computational complexity, time, performance or some things like this (Trade off/balance between of them).
I will give some examples:
- in MRF algorithm you can choose 4 neighborhood in each pixel (left, right, up, down)
- or you can choose 8 neighborhood in each pixel (left, right, top, down, top right, top left, down right, down left)
- or you can choose 8 neighborhood again in each pixel which 4 of them is assigned to current frame neighborhood pixels, and 4 of them is assigned to last frame neighborhood pixels