Ανάπτυξη μεθόδων εξερεύνησης και πλήρους κάλυψης αγνώστου χώρου από ρομπότ με εφαρμογή σε αναζήτηση θυμάτων. / Robot exploration and full coverage of an unknown space with application in victim detection and identification.

The diploma thesis aims at the implementation and analysis of methods designed to optimize the exploration of a robot in an unknown environment with or without the presence of potential victims. The primary objective was to develop software for autonomous vehicle navigation in order to be used by P.A.N.D.O.R.A. team, during its participation in the Robo-Cup world competition in Istanbul, July 2011. For this reason, tests were performed in simulated environments as well as with the real P.A.N.D.O.R.A. robotic vehicle. The experiment’s setups included both simulated and real environments. The presentation of the algorithms is divided into three parts: - Path Planning - Navigation - Victim Identification The first part consists of a study on popular methods and their variants of constructing routes, which a robot can follow in a given environment, in order to compare them in terms of execution time, quality of path and the ability to find solutions in demanding or complex environments. Their implementation includes graph theory and tree structures in many forms. Moreover Hill Climbing algorithms were utilized in order to achieve maximum improvement in the quality of the path. Experiments carried out in this part of the thesis, were conducted in static environments so that the methods would be checked and compared under the same conditions of exploration. In the second part, navigation methods were developed to achieve quick and effective exploration of an a priori unknown environment. The implementation basis of most of these methods was the topological graph obtained from the Generalized Voronoi Diagram (GVD). Moreover, an additional method for robot navigation was developed, which instead of exploiting the topological graph, uses Dijkstra’s algorithm to drive the robot to uncovered areas of the explored space. This is performed not by simple target selection, as with other methods, but with proper polarization of each approach route towards the uncovered areas. It is noteworthy that this is not a standalone navigation method, but acts as an improvement rule to the basic one. The experiments were performed both in simulated and real environments as well. The measured quantities were the total time of navigation and the rate of increasing covered space during the exploration. Finally, the third part presents methods for identifying and approaching a victim. At the same time, an alteration in the navigation method is proposed, in case of existence of multiple human casualties during exploration. The prior is based on the results that were extracted from the experiments in the previous part. Due to the lack of sensors in simulation and the existence of high levels of noise when collecting data from real sensors, experiments conducted in this part were limited to functional testing of the algorithms and were not used to extract any conclusions about the quality of navigation.