

Author: Mirolo Claudio Pagello Enrico
Publisher: Springer Publishing Company
ISSN: 0921-0296
Source: Journal of Intelligent and Robotic Systems, Vol.38, Iss.1, 2003-09, pp. : 5-30
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
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.
Related content




Dynamic sculpting and animation of free-form subdivision solids
By McDonnell Kevin T. Qin Hong
The Visual Computer, Vol. 18, Iss. 2, 2002-04 ,pp. :



