Comparison of Grid-Based Coverage Path Planning Methods in Planar Environments
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3016979Utgivelsesdato
2022Metadata
Vis full innførselSamlinger
Beskrivelse
Full text not available
Sammendrag
Coverage path planning (CPP) omhandler oppgaven å kunne utregne en vei som passerer gjennom alle punkter av et areal eller et volum og samtidig unngå objekter. CPP er brukt i mange applikasjoner sånn som autonome støvsugere, gressklippere, malingsroboter for biler, autonome undervanns terreng roboter, og mange flere. CPP er et forskningsområdet med fokus på mange viktige applikasjoner og av denne grunnen har jeg valgt å implementere, evaluere, forbedre og sammenligne et utvalg av metoder i denne masteroppgave. Det finnes mange forskjellige typer CPP algoritmer. Noen er on-line sensor basert og avhenger av sensor data, mens andre er off-line og bruker isteden \textit{a priori} informasjon til å dekke et området. Noen metoder blir brukt i 2-dimensjonal miljøer mens andre blir brukt 3-dimensjonale miljøer. Algoritmene implementert i denne masteren er 2-dimensjonal, off-line, Grid-baserte algoritmer. Grid-baserte metoder gjøre en tilnærmet diskretisering av miljøet og lagrer denne dataen in en grid struktur. De tre Grid-baserte metodene implementert er STC metoden av Gabriely et al. \cite{STC}. Nevral Nettverk metoden av Yang et al. \cite{NN_offline}, og Wavefront metoden av Zelinksy et al. \cite{Wavefront}. Denne masteren kommer til å angripe oppgaven ved å først implementere og verifisere de ulike metodene. Videre vil algoritmene bli simulert i ulike miljøer med økende kompleksitet. Hvis en algoritme ikke er i stand til å dekke et område på grunn av økt kompleksitet i miljøet, vil det bli gjort forbedringer til algoritmen. Den forbedrede algoritmen kommer da til å bli simulert over de samme miljøene. Når akseptable resultater har blitt generert vil en sammenligning utføres. Både Wavefront og Nevral Nettverk metoden trengte modifisering i sin implementasjon. Når man sammenligner de ulike metodene basert på de genererte resultatene kan man se at den modifiserte Nevral Nettverk metoden var i stand til å dekke 100\% av det objektfrie området, men den genererte også overlappende veier fordi den besøkte flere frie celler om igjen. Den forbedrede Wavefront algoritmen var i stand til å dekke nesten hele miljøet, men den hadde kjøretids disfavør. I tillegg var dens dekningskraft avhengig av start og sluttcelle konfigurasjonen uten noen tydelig forklaring på hvorfor. Dette påførte en viss mengde usikkerhet til dens dekningskraft. STC metoden utførte det verst i mengde området dekket blant de ulike algoritmene. Når det er sagt, genererte den ingen overlappende veier og den var i tillegg den mest konsistente algoritmen da den ikke trengte noe behov for forbedringer. I motsetning til Wavefront algoritmen, kunne den Nevral Nettverk og STC algoritmen dekke et område uavhengig av valg av startcelle. Coverage path planning (CPP) is the task of computing a path that passes through all the points of an area or a volume of space while simultaneously avoiding obstacles. CPP is essential in many applications such as autonomous vacuum cleaners, lawnmowers, car-body painting robots, autonomous underwater terrain covering robots, etc. CPP is an exciting field of science critical to many applications. For that reason, this thesis will implement, evaluate, improve and compare a selected number of methods. There exists a variety of CPP methods. Some are on-line sensor-based coverage methods that rely on real-time sensors, whereas others are off-line and rely on \textit{a priori} information about the environment. Some methods are applied to a planar environment, whereas others; to a volume of space. The algorithms implemented in this thesis fall within the category of planar, off-line, Grid-based methods. Grid-based methods perform an approximate discretization of the environment and store the data in a grid structure. The three Grid-based methods are the Spanning Tree Coverage (STC) method by Gabriely et al. \cite{STC}, the Neural Network (NN) method by Yang et al. \cite{NN_offline}, and the Wavefront method by Zelinsky et al. \cite{Wavefront}. This thesis will first implement and verify the methods. This is followed by simulation of the methods in various environments with increasing complexity. If a method in question cannot perform coverage as the complexity increases, improvements will be made, and the process will be repeated. Once adequate results have been generated, a comparison is made. Both the Wavefront and the Neural Network methods needed modification to their implementation. Comparing the various methods based on the results shows that the modified Neural Network method can cover 100\% of the free space. However, the method generated overlapping paths because it tended to revisit the same cells several times. The improved Wavefront algorithm covered almost the entire free space across all environments without any overlapping paths. However, it had run-time issues. Additionally, its covering ability depends on the start and goal cell configuration. This, in turn, injected a certain amount of uncertainty to its covering ability. The STC method performed the worst total coverage among the methods. That being said, it did not generate any overlapping paths, and it was the most consistent method, not needing any modification. In contrast to the Wavefront method, the Neural Network and the STC method could perform coverage independent of the starting cell.