Collaborative Terrain Exploration via a Distributed Graph Algorithm in Multi-Robot Systems
Author
Angelov, Dimitar Valentinov
Term
4. term
Education
Publication year
2025
Submitted on
2025-06-13
Pages
9
Abstract
Exploring unfamiliar terrain is vital in emergencies—such as rapidly mapping partially collapsed buildings—and in routine work like mining, underground surveys, and precision agriculture. This thesis extends the Greedy Graph algorithm, a distributed, graph-based method that helps multiple robots explore unknown spaces efficiently. The approach lets robots jointly build a real-time graph map (nodes and edges) as they move, and coordinate without a central controller to avoid redundant coverage. We improve the original method by refining how robots choose their next exploration targets and by introducing simple task allocation heuristics that divide work among robots. We validate the extended algorithm and its variations in simulated environments and compare it with established methods, including The Next Frontier and Minotaur. The results show faster exploration and better scalability as environments and robot teams grow.
Udforskning af ukendt terræn er vigtig i nødsituationer—fx hurtig kortlægning af delvist kollapsede bygninger—og i mere almindelige opgaver som minedrift, underjordiske undersøgelser og præcisionslandbrug. Denne afhandling udvider Greedy Graph-algoritmen, en distribueret, grafbaseret metode, der hjælper flere robotter med effektivt at udforske ukendte områder. Tilgangen lader robotterne sammen opbygge et fælles kort som en graf i realtid (noder og kanter), mens de bevæger sig, og koordinere uden central styring for at undgå gentagen dækning. Vi forbedrer den oprindelige metode ved at forfine, hvordan robotter vælger deres næste mål, og ved at introducere enkle opgavefordelings-heuristikker, der deler arbejdet mellem robotterne. Vi validerer den udvidede algoritme og dens varianter i simulerede miljøer og sammenligner med etablerede metoder som The Next Frontier og Minotaur. Resultaterne viser hurtigere udforskning og bedre skalerbarhed, efterhånden som miljøer og robotteams vokser.
[This apstract has been rewritten with the help of AI based on the project's original abstract]
Keywords