The use of household robotics has increased massively in the 21st century, with vacuum cleaners being one of the most common use cases in this field. Robot vacuum cleaners require good path planning, even in environments containing obstacles to be useful. One challenge to this is the fact that the robot often does not have knowledge of its environment, as all rooms are different and sometimes rearranged. Four different algorithms were tested to compare their performance in realistic home settings: random walk, closest first scan, BA* and our custom made hybrid BA* algorithm. Random walk is a simple algorithm where its path is determined by chance. It performed poorly when considering the amount of moves taken, especially when used in rooms with more complex obstacles and when a high degree of coverage was desirable, although was somewhat better in the amount of turns necessary. It may be more suited for situations with fewer obstacles and where good coverage is less of a priority. Closest first scan, which walks randomly to unvisited spaces while creating a map to improve performance in high coverage scenarios, performed slightly worse than BA* but still offered a significant improvement over random walk in the amount of moves taken. It performed poorly when considering the amount of turns taken. BA* is a more sophisticated approach that walks deterministically and creates a map of its environment during the run, which it then uses to find uncovered space. It performed well, both in moves and turns, always achieving full coverage and rarely visited covered spaces. Hybrid BA* showed promising results when dealing with changes in the environment. Limitations of our work includes a low resolution of our simulation and optimistic assumptions about the reliability of robot hardware.

Användandet av robotik i hushåll har sett en stor ökning i det nya årtusandet, dammsugare är en av de vanligaste användningarna i detta fält. Robotdammsugare kräver bra ruttplanering, även i miljöer som innehåller hinder för att vara användbara. En utmaning som uppstår är att roboten kan ej ha kunskap om sin egen miljö, för att alla rum är unika och blir ibland omflyttade. Detta leder till problem om roboten gör för många antaganden. Fyra olika algoritmer valdes ut för att jämföra deras prestanda i realistiska hemmiljöer: random walk, closest first scan, BA* och vår egenutveckled hybrida BA* algoritm. Random walk är en enkel algoritm där vägen som tas är bestämd av slumpen. Den presterade dåligt i mängden steg nödvändigt för täckning, särskilt i rum med mer komplexa hinder och när en hög grad av täckning krävdes. Dock så presterade den någorlunda bättre i antal svängningar. Den kan vara mer lämpad i fall med färre hinder och där bra täckning är mindre av en prioritet. Closest first scan är en icke-deterministisk algoritm som går slumpmässigt till otäckta granar samtidigt som den skapar en intern karta som den använder till att förbättra prestanda vid hög täckning. Den presterade någorlunda sämre än BA* men fortfarande betydligt bättre än random walk i antal steg. Den presterade dålig i antal svängningar. BA* är en mer sofistikerad algoritm som skapar en karta av sin miljö under körning, vilket den sedan använder sig av för att upptäcka ej täckta utrymmen. Den presterade väl i både antal steg samt svängningar, en full täckning av arean uppnåddes alltid och den återbesökte sällan redan täckta utrymmen. Hybrida BA* visade goda resultat för förändringar i sin miljö Begränsningar i vårt arbete har varit en låg upplösning i simuleringen samt optimistiska antagningar om pålitligheten av robotars hårdvara.