Institut für
Informatik, Universität Freiburg
Sommer 1999
Termin: Montag, 15-17 Uhr
- 26.04. J. Hoffmann: Ein Überdeckungsproblem für beliebig dimensionierte Hyperquader
- 03.05. B. Nebel: Compilability and Expressiveness of Planning Formalisms
-
The recent approaches of extending the Graphplan algorithm to handle more
expressive planning formalisms raise the question of what the formal meaning
of ``expressive power'' is. We formalize the intuition that expressive power
is a measure of how concisely planning domains and plans can be expressed in
a particular formalism by introducing the notion of ``compilation schemes''
between planning formalisms. Using this notion, we analyze the expressive
power of a large family of propositional planning formalisms and show, e.g.,
that Gazen and Knoblock's approach to compiling conditional
effects away is optimal, that conditional effects cannot be compiled
to CNF preconditions, but that CNF preconditions can be compiled into
conditional effects.
- 10.05. C. Dornheim
-
- 17.05. J.-S. Gutmann: Incremental Mapping of Large Cyclic Environments
-
This talk addresses the problem of building maps in large,
cyclic indoor environments from laser range finder data. Most existing
incremental methods, e.g. Kalman-filter based methods, run into problems
when the environment to be mapped contains a cycle. Therefore several
other methods have been developed in the past that are able to deal
with such loops. One technique is consistent pose registration
developed by Lu & Milios. However this method assumes that the
range data is already topologically correct, e.g. the approximate
scan positions are already known. Another approach is the expectation
maximization (EM) method used by Thrun et. al. for computing topological
correct maps. However this method requires additional information from
the user during the exploration run, e.g. button presses at several
locations, and it can't be used as an incremental method due to its
high computational complexity. This talk presents a new technique
developed at SRI Int. that uses scan-matching, map correlation,
and consistent pose registration for incremental map building.
The method is highly efficient and runs almost in real-time. Several
sample mapping runs in different environments and with different robot
systems are presented that show the capabilities and accuracy of
this approach.
- 31.05. J. Renz
-
- 07.06. Reinhard Moratz, Universität Hamburg: Qualitatives Räumliches Schließen für Kognitive Robotik
-
Grobes Wissen über räumliche Anordnungen wird vom Menschen für
viele Aufgaben eingesetzt. Davon inspiriert wurden Techniken entwickelt, räumliches Wissen qualitativ zu repräsentieren. Vorbild dabei ist die Modellierung zeitlicher Intervallrelationen durch Allen.
Insbesondere topologische Relationen wurden intensiv untersucht, da Zusammenhangswissen eine starke Analogie zu Intervallrelationen besitzt. Will man jedoch komplexe räumliche Abläufe modellieren, sind zusätzlich relative Positionsangaben als Verfeinerung notwendig. Die meisten bisher entwickelten qualitativen Positions-Kalküle benutzen Referenzsysteme, die Aussagen über Punkte auf der 2D-Ebene treffen.
In letzter Zeit wurde von verschiedener Seite Skepsis geäußert, ob sich qualitative Raumkalküle an zentraler Stelle bei der Roboternavigation einsetzen lassen. Im Ausblick wird gezeigt, daß insbesondere praxisnahe Szenarien der Roboternavigation, die von einer komplexen Interaktion zwischen dem Roboter und einem menschlichen Instrukteur ausgehen, von einem Einsatz qualitativer Techniken profitieren können.
- 28.06. Kai-Oliver Arras, EPFL Lausanne:
Multisensor EKF Localization and Feature-Based Map Building
-
The talk is about the feature-based approach to mobile robot
localization and map building in unmodified structured environments. The
advantages and drawbacks of features as perceptual entities for
navigation are discussed and the Kalman filter as estimation tool is
briefly outlined. We show that by using a multisensor setup, namely
laser range finder and monocular vision, robustness and precision of the
localization task can be improved while remaining still practicable on a
fully autonomous system as the experiments demonstrate.
The step which automates the laborous procedure of measuring an a priori
map by hand for localization is called map building. Simultaneous
localization and map building is a chicken-and-egg problem: during the
map construction the positions of robot and features are concurrently
sought. Determining the former needs knowledge of the latter and
determining the latter needs knowledge of the former. Although this
problem is theoretically well understood, several reasons lead to
difficulties in practice. Our approach of deliberative exploration as a
means against these problems will be presented and first results on a
fully autonomous robot executing the task are shown.
A high-level approach for qualitative navigation be means of symbolic
strings as concise models of local maps is finally dicussed and its
benefit as measure of distinctiveness is outlined.
- 05.07. Christian Schlegel, FAW Ulm.
Bernhard Nebel, 9.4.99