One approach towards planning a path in configuration space is to simply map the free space onto a discrete raster which reduces the path planning problem within each of the cells to a trivial problem (move on a straight line) as it is completely traversable. By this means, we end up with a discrete graph search problem, which are relatively easy to solve. The simplest cell decomposition matches the free space onto a regularly spaced grid but more complex methods are possible.
Cell decomposition has advantage of an easy implementation, but also suffers some deficiencies:
• The amount of grid cells increases exponentially with the dimension of the configuration space.
• Polluted cells (cells which contain free and occupied space) are problematic. If included, they might lead to solutions, which are in reality blocked, if omitted, some valid solutions would be missing.
The latter problem could be solved by further subdivision of the affected cells or by requiring exact cell decomposition by allowing irregularly shaped cells. Those new cells would need to have an ‘easy’ way to compute a traversal through them, which would lead to complex geometric problem.
Another problem is the fact that a path through such a cell grid can contain arbitrary sharp corners, which would be impossible to perform by real life robots. Such a path can lead very close to obstacle, rendering even the slightest motion errors fatal.
No comments:
Post a Comment