The Hong Kong University of Science and Technology
Department of Computer Science


PhD Thesis Defence


"Online Exploration and Search in Graphs"

By

Mr. Gerhard Wolfgang Trippen

Abstract

There are three fundamental online problems in robotics:
navigation/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 the whole environment. Besides
the practical problems that arise when an autonomous robot needs to travel
through real terrain there is the question how good will the robot 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 movements online and with only the 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 the 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 focusing on
directed graphs in the case of exploration we consider both directed
graphs and undirected graphs for the search problem, in which the robot
needs to find a specific goal.

The thesis begins with a short motivation behind online search and
exploration. We survey existing algorithms, involving a detailed
discussion of some of those algorithms, that -- or parts of that -- 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 vertex 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 problem 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 helped to provide a better insight into the practical performance
of these algorithms on various graph families. It is to observe that all
the tested algorithm have a performance very close to the optimum offline
algorithm 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, how
efficiently we can search an unknown environment for a goal in unknown
position, and how much it would help if the environment were known.

We answer these questions for general graphs, 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.


Date:			Friday, 23 June 2006

Time:			2:00p.m.-4:00p.m.

Venue:			Room 5501
			Lifts 25-26

Chairman:		Prof. David Zweig (SOSC)

Committee Members:	Prof. Rudolf Fleischer (Supervisor, Fudan University)
			Prof. Mordecai Golin (Supervisor)
			Prof. Sunil Arya
			Prof. Derick Wood
			Prof. Beifang Chen (MATH)
			Prof. Naoki Katoh (Architecture & Architectural Systems,
					   Kyoto Univ.)


**** ALL are Welcome ****