Catalogue of Artificial Intelligence Techniques
Keywords: cell, decomposition, planning, robot, search, space
Author(s): Gary Bryan
In robotics, Cell Decomposition is a technique used for movement planning.
A robot's possible states can be represented as a configuration space, containing all the possible configurations, and that can be split into two subspaces: the Free Space (the space of all attainable configurations), and the Occupied Space (the space of unattainable configurations). Cell Decomposition splits the free space into a finite set of contiguous "cells", which can be easily traversed. This turns the movement planning into a discrete graph search problem, which can be solved using standard searching techniques.
The simplest implementation is to split the space into equal cells, however problems may arise. A cell may contain part of the occupied space as well as free space, in which case either a "solution" going through this cell may not actually be possible, or an accessible path could be rejected, depending on the implementation. This can be solved by allowing those mixed cells to be recursively split into smaller cells. However, even with this step, the method is inefficient for high-dimensional problems. For these problems, allowing irregularly shaped cells, known as an Exact Cell Decomposition, is a better solution. In this case, the cells must still be simple enough to be computationally manipulated.
To avoid the robot moving too close to obstacles, a "potential field" can be introduced. This allows the robot to take into account how close a possible path is to an obstacle, and if necessary take a longer but safer path.
- Russell S. and Norvig P., Artificial Intelligence: A Modern Approach, Prentice Hall, NJ, 07458, USA, 2003, pp.916-921 (http://www.cs.berkeley.edu/~russell/aima/).