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.

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

MIROLO, Claudio;
2003-01-01

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/673420
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact