The cell decomposition approach gives idea to identify between geometricareas, or cells, that are free and areas that are occupied by objects. Thebasic cell decomposition path-planning algorithm can be summarized as follows9:· Firstly, divide F into simple,connected regions called “cells”.· Secondly, determine which openscells are adjacent and construct a “connectivity graph”.· Thirdly find the cells in whichthe initial and goal configurations lie and search for a path in theconnectivity graph to join the initial and goal cell.· Finally, from the sequence ofcells found with an appropriate searching algorithm, compute a path within eachcell, for example, passing through a sequence of wall-following motions or bythe midpoints of the cell boundaries and movements along straight lines. Fig.
2. Approximate Cell DecompositionIn cell decomposition methods the most importantaspect is the placement of the boundaries between cells. If the boundaries areplaced as a function of the structure of the environment, such that thedecomposition is lossless, then the method is termed exact cell decomposition 51,52,53.
If the decomposition results inan approximation of the actual map, the system is termed approximate celldecomposition55,54,56 and next is Probabilistic CellDecomposition 57,58 which is similarto approximate Cell Decomposition except that cells boundaries do not representany physical meaning. Cell Decompositon is commonly used in robot motionplanning scenarios 59,60,61-64,57,65.Fujii et al., Park et al.
, and Yang andGu et al. 48,49,50 discussed theproposal of separating large learning spaces to several smaller ones resultingin ease of exploration. According to Nora H. Sleumer & Nadine Tschichold Gurman 14, algorithm isbased on the exact cell decomposition obtained when the segments representingthe walls of the building are extended to infinite lines. The main advantagesof this method are that the decomposition of the work space of the robot isintuitive and that the shape of the cells allows for robust and flexible pathplanning.