Swarm Intelligence (SI) is a young field of study from which solutions to complex problems have been proposed based on how some natural organisms (e.g. ants, bees and others) achieve many of their daily tasks through simple sets of interactions. This thesis proposes two models for area exploration and coverage based on SI principles. These two models present a novel approach based on the combination of: ants’ pheromones, in order to keep track of visited places; and bird flocks or fish schooling, so as to move and collaborate. An implementation of both models was done in order to simulate and evaluate both the emergent behavior of the agents as well as their area exploration and coverage performance. Based on the outcome of the simulations it is concluded that both models are able to perform the exploration and coverage task and that one model is better than the other.

Η παρούσα διπλωματική εργασία μελετά το θέμα της πλοήγησης ενός ρομποτικού οχήματος με στόχο την εξερεύνηση μιας περιοχής η οποία είτε είναι ελεύθερη είτε περιέχει εμπόδια σε γνωστές θέσεις. Για αυτό το πρόβλημα εξερεύνησης, υπάρχει επίσης ένας περιορισμός που αφορά το όχημα: θα πρέπει αυτό κατά τη διάρκεια της εξερεύνησης να διατηρεί την επικοινωνία του με ένα σταθερό σταθμό βάσης. Για να αντιμετωπιστεί το σύνθετο αυτό θέμα και για να αναπτυχθεί ένας αλγόριθμος για την πειραματική διαδικασία, αρχικά θεωρήθηκε ένα μοντέλο κινοδυναμικών εξισώσεων για το ρομποτικό όχημα. Στη συνέχεια, για το μοντέλο αυτό παρουσιάστηκε ένας μη-γραμμικός ελεγκτής που σχεδιάστηκε για παρακολούθηση επιθυμητών τροχιών. Για να υλοποιηθεί ο εν λόγω ελεγκτής, ήταν απαραίτητος ο εντοπισμός της θέσης του ρομποτικού οχήματος και αυτό επετεύχθη πειραματικά μέσω επεξεργασίας εικόνας. Το ρομπότ αναγνωριζόταν στις εικόνες που λαμβάνονταν από μια κάμερα παρακολούθησης, και με κατάλληλη γεωμετρική ανάλυση ήταν εφικτή η εκτίμηση της θέσης και του προσανατολισμού του ρομπότ. Για την επικοινωνία του ρομπότ με το σταθμό βάσης αναπτύχθηκε ασύρματο δίκτυο ΙΕΕΕ 802.15.4 και για την αξιολόγηση της ποιότητας της επικοινωνίας αυτής χρησιμοποιήθηκε το Received Signal Strength Indicator (RSSI). Ο αλγόριθμος σχεδιασμού διαδρομής, ο οποίος καθοδηγεί το ρομπότ στο περιβάλλον με στόχο την εξερεύνηση όλων των ελεύθερων σημείων, αξιοποίησε την εκ των προτέρων γνώση για τα εμπόδια, καθώς και τις μετρήσεις του RSSI κατά τη διάρκεια του πειράματος, ώστε να πετύχει το στόχο του. Πιο συγκεκριμένα, χρησιμοποιήθηκε μια on-line μέθοδος που πετυχαίνει όσο το δυνατόν μεγαλύτερη κάλυψη του περιβάλλοντος υπό τον περιορισμό της επικοινωνίας, έχοντας σαν οδηγό μια προσχεδιασμένη διαδρομή εξερεύνησης. Στο τέλος της εργασίας παρουσιάζονται πειραματικά αποτελέσματα και συμπεράσματα για τα διάφορα αντικείμενα της μελέτης. / The present diploma thesis studies the subject of the navigation of a robotic vehicle for the exploration of an environment which is either free or contains obstacles in known locations. For this area coverage problem, there is an additional constraint: during the exploration the robot must maintain its communication with a stationary base station. In order to address this complex subject and to develop an algorithm for the experimental procedure, a kinodynamic model is initially assumed for the robotic vehicle. Then, a non-linear controller is designed for this model to achieve tracking of reference trajectories. For the implementation of this controller, the localization of the robotic vehicle was necessary and it was achieved via image processing during the experiments. The robot was recognized in images taken by a surveillance camera, and after appropriate geometric analysis, it was possible to estimate the position and the orientation of the robot. For the robot-base communication, an IEEE 802.15.4 wireless network was developed and in order to evaluate the quality of this communication, the Received Signal Strength Indicator (RSSI) was utilised. The path planning algorithm, which navigates the robot inside the environment to explore all the available locations, achieved its goal by combining the prior knowledge about the obstacles and the RSSI measurements during the experiments. Specifically, an on-line method that achieves maximum possible coverage of the environment under the communication constraint was employed, using a pre-designed exploring path as a guide. At the end of this thesis, some experimental results and conclusions are presented concerning the versatile subjects of this study.

This thesis presents an approach to solve an optimal path planning problem for a swarm of drones. We optimize and improve information retrieval in area exploration within applications such a ‘Search and Rescue’-missions or reconnaissance missions. For this, dynamic programming has been used as a solving approach for a optimization problem. Different scenarios have been examined for two types of system, a single-agent system and a multi-agent system. First, there have been restrictions on the agents movement in a grid map and for that, optimal paths have been computed for both systems. Thereafter, two different solving approaches within dynamic programming have been tested and compared. The greedy approach which is a standard use where each agent computes the most optimal path from its own perspective and a simultaneous solving approach where the agents compute the most optimal paths according to all agents perspective. The simultaneous solving approach performed better than the greedy approach, which was expected since it is a more swarm optimal approach. However, it has a higher computational complexity which grows exponentially unlike to the greedy approach. Lastly, we discuss the case when the agents are allowed to move in all directions to optimize the information retrieval for the swarm. Here, dynamic programming turns out to have limitations for our use and purpose. For future work, a suggestion is to model the problem with multiple objective functions instead of one as has been done in this thesis. Also, it would be interesting trying another solving method for the problem. To this, I give example of two methods that would be interesting to compare, using model predictive control or a machine learning-based solution such as reinforcement learning. / Denna avhandling presenterar ett tillvägagångssätt för att lösa ett optimalt ruttplanerings problem för en drönarsvärm. Vi optimerar och förbättrar informationsinhämtningen i områdesutforskning inom applikationer som ’Search and Rescue’-uppdrag eller spaningsuppdrag. För detta har dynamisk programmering använts som en lösningsmetod till optimeringsproblem. Olika scenarier har undersökts för två typer av system, ett en-agent system och ett fler-agent system. Först har agenterna varit begränsade hur de har fått röra sig i en rutnätskarta och för det fallet har optimala vägar beräknats för båda systemen. Därefter har två olika lösningssätt inom dynamisk programmering testats och jämförts. Det giriga tillvägagångssättet som är en standardanvändning där varje agent beräknar den mest optimala vägen ur sitt eget perspektiv och en simultan lösningsmetod där agenterna beräknar de mest optimala vägarna enligt alla agenters perspektiv. Den simultana lösningsstrategin presterade bättre än den giriga, vilket var väntat eftersom det är ett mer svärmoptimalt tillvägagångssätt. Den har dock en högre beräkningskomplexitet som växer exponentiellt jämfört med den giriga metoden. Till sist diskuterar vi fallet då agenterna får röra sig i alla riktningar för att optimera informationssökningen för svärmen. Här visar sig dynamisk programmering ha begränsningar för våran användning och syfte. För framtida arbete är ett förslag att modellera problemet med flera mål funktioner istället för en som har gjorts i denna avhandling. Det skulle också vara intressant att prova ett annat lösningssätt för problemet. Till detta ger jag exempel på två metoder som skulle vara intressanta att jämföra, genom att använda modell prediktiv styrning eller en maskininlärningsbaserad lösning såsom förstärkande inlärning.