Online exploration and search in graphs

There are three fundamental online problems in robotics: naviga-tion/search, localization, and exploration. Constructing a complete map of an unknown environment while using a short path is the task of autonomous robots when they have to explore a whole environ-ment. Besides the practical problems that arise when an autonomous robot needs to travel through real terrain there is the question of how well the robot will perform compared to an optimal strategy that has complete knowledge of the environment and can plan an exploration path in advance. The robot must always decide its further move-ments online and with only partial knowledge of the already explored environment. Different models of the environment lead to different algorithms that try to cope with the difficulties given by a particular modeling. The advantage of modeling environments as graphs lies in the fact that the geometric features are neglected and one can concentrate on the combinatorial aspects of the exploration problem. While we are fo-cusing on directed graphs in the case of exploration we consider both directed and undirected graphs for the search problem, in which the robot needs to find a specific goal. The thesis begins with a short explanation of the motivation behind online search and exploration. We survey existing algorithms, involv-ing a detailed discussion of some of those algorithms, which - or parts of which - are reused in some of our algorithms. The thesis continues with the study of the problem of exploring an unknown, strongly connected directed graph G. Starting at some ver-tex of the graph, we must visit every edge and every vertex at least once. The goal is to minimize the number of edge traversals. It is known that the competitive ratio of online algorithms for this prob-lem depends on the deficiency d of the graph, which is the minimum number of edges that must be added to make the graph Eulerian. We present the first deterministic online exploration algorithm whose competitive ratio is polynomial in the deficiency d of G (it is O(d7)). An extensive experimental study investigates all major online graph traversal algorithms. This includes many simple natural algorithms as well as more sophisticated strategies, and some variants of the original algorithms. Our work helps to provide a better insight into the practical perfor-mance of these algorithms on various graph families. It is to observe that all tested algorithms perform closely to the optimum offline al-gorithm in a huge family of random graphs. Only few very specific lower bound examples cause bad results. The remainder of the thesis is concerned with the questions of how efficiently we can search an unknown environment for a goal in an unknown position, and how much it would help if the environment were known. We answer these questions for general graphs and trees, by providing online search strategies that are as good as the best offline search algorithms, up to a constant factor. Furthermore, we show that for some more restricted environments no online search strategies with this performance guarantee exist