The search for efficient exploration paths to cover an environment is a classical problem of autonomous robotics. The exploration problem studied in this work takes place in a polygonal two-dimensional environment and the robot is equipped with an omni-directional sensor with finite range. The goal is to find the optimal path to explore a percentage of the free surface of an environment. Finding the optimal exploration path implies knowing the environment and can be considered as a coverage problem with a reachability constraint: each perception location must be visible, in line of sight, from at least another perception location previously visited. The environment is discretized using a visibility-based decomposition paired with a more classical grid-based decomposition. The optimal exploration path is computed using A*. Simulation in different indoor environments show the completeness and the good performance of the proposed approach.

La ricerca di un percorso efficiente per esplorare un ambiente è un classico problema della robotica autonoma. Il problema di esplorazione studiato in questo lavoro ha luogo in un ambiente bi-dimensionale rappresentato come un poligono e considerando un robot dotato di un sensore omnidirezionale che percepisce fino a una certa distanza. L'obiettivo è quello di trovare il percorso ottimo per esplorare una data percentuale della superficie libera di un ambiente. Per raggiungere l'ottimo, il robot deve conoscere l'ambiente. Il problema da risolvere è quindi un problema di copertura con un vincolo di raggiungibilità: ogni posizione di percezione deve essere visibile, in linea d' aria, da almeno un'altra posizione precedentemente visitata. L'ambiente è discretizzato usando una decomposizione basata sulla visibilità abbinata ad una decomposizione più classica basata su griglia. Il percorso di esplorazione ottimale viene calcolato utilizzando A*. La simulazione in diversi ambienti interni mostra la completezza e le buone prestazioni dell'approccio proposto.

Combining grid- and visibility-based decompositions to find optimal off-line exploration paths for an autonomous mobile robot with limited-range perception

ORBELLI, MARCO
2018/2019

Abstract

The search for efficient exploration paths to cover an environment is a classical problem of autonomous robotics. The exploration problem studied in this work takes place in a polygonal two-dimensional environment and the robot is equipped with an omni-directional sensor with finite range. The goal is to find the optimal path to explore a percentage of the free surface of an environment. Finding the optimal exploration path implies knowing the environment and can be considered as a coverage problem with a reachability constraint: each perception location must be visible, in line of sight, from at least another perception location previously visited. The environment is discretized using a visibility-based decomposition paired with a more classical grid-based decomposition. The optimal exploration path is computed using A*. Simulation in different indoor environments show the completeness and the good performance of the proposed approach.
BASILICO, NICOLA
QUATTRINI LI, ALBERTO
ING - Scuola di Ingegneria Industriale e dell'Informazione
18-dic-2019
2018/2019
La ricerca di un percorso efficiente per esplorare un ambiente è un classico problema della robotica autonoma. Il problema di esplorazione studiato in questo lavoro ha luogo in un ambiente bi-dimensionale rappresentato come un poligono e considerando un robot dotato di un sensore omnidirezionale che percepisce fino a una certa distanza. L'obiettivo è quello di trovare il percorso ottimo per esplorare una data percentuale della superficie libera di un ambiente. Per raggiungere l'ottimo, il robot deve conoscere l'ambiente. Il problema da risolvere è quindi un problema di copertura con un vincolo di raggiungibilità: ogni posizione di percezione deve essere visibile, in linea d' aria, da almeno un'altra posizione precedentemente visitata. L'ambiente è discretizzato usando una decomposizione basata sulla visibilità abbinata ad una decomposizione più classica basata su griglia. Il percorso di esplorazione ottimale viene calcolato utilizzando A*. La simulazione in diversi ambienti interni mostra la completezza e le buone prestazioni dell'approccio proposto.
Tesi di laurea Magistrale
File allegati
File Dimensione Formato  
marco_orbelli_tesi.pdf

accessibile in internet solo dagli utenti autorizzati

Descrizione: Thesis by Marco Orbelli
Dimensione 1.88 MB
Formato Adobe PDF
1.88 MB Adobe PDF   Visualizza/Apri

I documenti in POLITesi 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/10589/152126