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.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.
https://hdl.handle.net/10589/152126