A New Cell-Subdivision Approach to Plan Free Translations in Cluttered Environments

This paper presents a thorough discussion of the potential of a new cell-subdivision approach to plan translations of a convex polygon in a cluttered environment, where the focus is on planning simple motions on the basis of a fine-grained description of the workspace. A free path is planned in two main stages. The first stage exploits a plane-sweep paradigm in order to build a cell subdivision holding much relevant topological information on the free space and organizing a set of polygonal chains that approximate the boundaries of the configuration space obstacles. Then, the computations in the second stage are driven by an A* scheme designed to search the cell subdivision. During the search the bounding chains are subject to further refinements, but the cell graph is no longer modified. Among the remarkable features of the proposed technique we can mention: simple interface with the geometric modeler, based on two collision-detection primitives; small number of cells and adjacencies; incremental characterization of the free space. A few numerical results suggest that the new technique should be worth considering for applications, where appropriate; in particular, it seems to perform better than other approaches based on quadtrees. Moreover, it is quite interesting to observe that the cost of finding collision-free paths grows with the number of convex obstacles, whereas it is almost independent of the overall number of sides: we can interpret this result as supporting the choice of representing the obstacles decomposed into convex components. A succinct comparison between algorithmic and human intuitive path planning is also discussed in order to appraise the rate of redundant information processed by the algorithm, but we can also see that human planners behave significantly better only when the solutions are easy to find.