Institut für Informatik, Universität Freiburg

Oberseminar Künstliche Intelligenz

Sommer 1999

• 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.