Pagina Radice del Progetto: Robot Planning (esplorazione dell'ambiente)

Un robot deve costruire la mappa di un ambiente a lui aprioristicamente sconosciuto e modellizzato come un grafo non diretto e connesso. L'obiettivo del robot è quello di esplorare tutti i nodi e tutti gli archi, minimizzando il numero di spostamenti (sempre lungo un arco del grafo).

Vorremmo codificare in noweb e c++ un algoritmo esposto nel seguente lavoro.

Panaite, Petricsor; Pelc, Andrzej
Exploring unknown undirected graphs.
J. Algorithms 33 (1999), no. 2, 281--295.

Come possibile approfondimento, è apparso un lavoro più recente.

Panaite, Petricsor; Pelc, Andrzej
Impact of topographic information on graph exploration efficiency.
Networks 36 (2000)

Ma per dare consistenza al lavoro credo che la principale possibilità sia quella di curare la visualizzazione del comportamento dell'algoritmo.

[Back] created:   30 Aprile 2001
updated:   30 Aprile 2001 		© Dipartimento di Matematica
University of Verona