The problem of organizing and exploiting spatial knowledge for navigation is an important issue in the field of autonomous mobile systems. In particular, partitioning the environment map into connected clusters allows for significant topological features to be captured and enables decomposition of path-planning tasks through a divide-and-conquer policy. Clustering by discovery is a procedure for identifying clusters in a map being learned by exploration as the agent moves within the environment, and yields a valid clustering of the available knowledge at each exploration step. In this work, we define a fitness measure for clustering and propose two incremental heuristic algorithms to maximize it. Both algorithms determine clusters dynamically according to a set of topological and metric criteria. The first one is aimed at locally minimizing a measure of "scattering" of the enlilies belonging lo clusters, and parlially rearranges the existing clusters at each exploration step. The second estimates the positions and dimensions of clusters according to a global map of density. The two algorithms are compared in terms of optimality, efficiency, robustness, and stability. 191996 ICCE.

Dynamic clustering of maps in autonomous agents

Maio D.;Maltoni D.;Rizzi S.
1996

Abstract

The problem of organizing and exploiting spatial knowledge for navigation is an important issue in the field of autonomous mobile systems. In particular, partitioning the environment map into connected clusters allows for significant topological features to be captured and enables decomposition of path-planning tasks through a divide-and-conquer policy. Clustering by discovery is a procedure for identifying clusters in a map being learned by exploration as the agent moves within the environment, and yields a valid clustering of the available knowledge at each exploration step. In this work, we define a fitness measure for clustering and propose two incremental heuristic algorithms to maximize it. Both algorithms determine clusters dynamically according to a set of topological and metric criteria. The first one is aimed at locally minimizing a measure of "scattering" of the enlilies belonging lo clusters, and parlially rearranges the existing clusters at each exploration step. The second estimates the positions and dimensions of clusters according to a global map of density. The two algorithms are compared in terms of optimality, efficiency, robustness, and stability. 191996 ICCE.
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/897471
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 6
social impact