Institut für Informatik, Universität Freiburg

Oberseminar AG Künstliche Intelligenz

Winter 1996/97

• 23.10.96 Wolfgang Hatzack: Failure Recovery during Plan Execution in the Situation Calculus

  Autonomous operation of an agent in the real world can be made much more efficient and robust when taking into account that failures can occur. One important aspect of failure recovery is replanning, and we will discuss an approach for reducing replanning effort. First, we introduce a general framework in which one can formally deal with goals, actions, failures, and plans. Within this framework, we formulate our approach which is also well-suited for applications where one can be content with the satisfaction of only some parts of a goal specification. Furthermore, we will show how this approach can be implemented efficiently in a situation calculus framework. The central notion is that of a abeled dependency graph, which can be used to reveal the connection between actions and parts of a goal specifications. Given an action sequence generated by a GOLOG program, we finally discuss a heuristic that can be used to obtain so-called partial goal specifications, which are vital for the construction of labeled dependency graphs.

• 06.11.96 Jens-Steffen Gutmann: Vergleich von Algorithmen zur Selbstlokalisierung eines mobilen Roboters
  Diese Arbeit beschäftigt sich mit dem Problem der Selbstlokalisierung eines autonomen mobilen Roboters, also der Frage "Wo bin ich?". Ziel der Arbeit ist es, ein Verfahren auf dem Roboter des AMOS-Projekts (Autonome mobile Systeme) des FAW Ulm (Forschungsinstitut für anwendungsorientierte Wissensverarbeitung) zu implementieren, das die Positionsbestimmung realisiert. Der Aktionsbereich des Roboters ist dabei auf das FAW-Gebäude beschränkt. Für diese Aufgabe wurden einige in der Literatur vorhandene Ansätze für den Einsatz auf dem AMOS-Roboter hin untersucht. Dabei konzentrierte sich die Untersuchung auf Verfahren, die 2d-Abstandsprofile miteinander vergleichen. Die Verfahren wurden mit simulierten und realen Scans getestet und die Resultate miteinander verglichen. Dabei stellte sich heraus, daß eine geeignete Kombination der untersuchten Verfahren die besten Resultate liefert. Weiterhin wurde eine Methode erarbeitet, die durch eine Fehlerbetrachtung der Überdeckungsverfahren und eine auf dem Kalman-Filter basierende Fusion der Positionsschätzung von Koppelnavigation und Scanüberdeckung eine optimale Schätzung der Roboterposition bestimmt.

  27.11.96: Jochen Renz: Qualitatives räumliches Schließen: Berechnungseigenschaften und effiziente Algorithmen

  Nach einer kurzen Einführung in qualitatives räumliches Schließen und das RCC-Kalkül werden diesbezüglich verschiedene komplexitätstheoretische Ergebnisse vorgestellt. Es soll gezeigt werden, daß das Konsistenzproblem für RCC-8 NP-vollständig ist. Durch Modifikation einer von Bennett entwickelten multi-modallogischen Formulierung von RCC-8 kann eine Transformation auf Aussagenlogik vorgenommen werden. Dadurch kann eine Teilmenge des gesamten Kalküls gefunden werden, für die das Konsistenzproblem in polynomialer Zeit gelöst werden kann. Es kann nachgewiesen werden, daß diese Teilmenge maximal ist. Außerdem soll gezeigt werden, daß der üblicherweise unvollständige Pfadkonsistenzalgorithmus für diese Teilmenge vollständig ist.

  11.12.96 -- Strategiesitzung

  08.01.97: Yannis Dimopoulos: A Transaction Model for Non-deterministic and Non-chronological Database Updates

  In this talk we introduce SofTrans, a new transaction model that handles database transactions that contain updates that can be non-deterministic (i.e. view updates that can be realized in different ways) and non-chronological (i.e. updates that arrive to the system in an order that does not necessarily reflect the order in which the corresponing changes happened in the world). In order to achieve these enchanced capabilities SofTrans uses the valid time information associated with each transaction and allows for these to pend waiting for more information that may enable them to commit. Despite the necessary deviation of SofTrans from the standard model, it enjoys desirable properties such as consistency and atomicity.

  22.01.97: fällt aus

  29.01.97: Stefan Jäger (Daimler-Benz Forschungszentrum Ulm): Handschrifterkennung

  Handschrift ist fuer den Menschen eine natuerliche Form der Uebermittlung und Speicherung von Daten. In vielen Bereichen stellt die Handschrift die bequemste Moeglichkeit der Kommunikation dar. Ziel der Handschrifterkennung ist es, geschriebene Woerter maschinell zu verarbeiten und automatisch zu erkennen. Ein besonders erfolgreiches Anwendungsfeld ist die Postautomatisierung, in der handgeschriebene Adressen automatisch gelesen werden. Immer haeufiger wird die Handschrifterkennung auch fuer Mensch-Maschine-Schnittstellen eingesetzt, wie sie z.B. in Personal Digital Assistants (PDAs) zum Einsatz kommen. In dem Vortrag werden die verschiedenen Anwendungsfelder mit ihren unterschiedlichen Anforderungen kurz vorgestellt. Anschliessend werden Probleme der Komplexitaet und weitere theoretische Fragestellungen behandelt. Angelehnt an ein kognitives Modell wird ein theoretischer Formalismus entwickelt, mit dem sich unterschiedliche Verarbeitungsschritte in gleicher Weise loesen lassen.

  05.02.97: Jana Koehler: Reasoning about Sets via Atomic Decomposition

  We introduce a new technique that translates cardinality information about finite sets into simple arithmetic terms thereby enabling a system to reason about such set cardinalities by solving arithmetic equation problems. The atomic decomposition technique separates a collection of sets into smallest mutually disjoint components (``atoms'') such that the cardinality of the sets are just the sum of the cardinalities of their atoms. With this idea, it is possible to have languages combining arithmetic formulas with set terms and to translate the formulas of this combined logic into pure arithmetical formulas. As a particular application, we show how this technique yields new inference procedures for concept languages with so-called number restriction operators.
  Joint work with Hans Juergen Ohlbach, Imperial College, London.

  12.02.97: Lea Meyer (IIG): Probabilistic language learning under monotonicity constraints

  The study of probabilistic learning can be motivated by the fact that people enlarge their learning power by accepting that their learning processes may fail with a certain probability. In general, the learning power increases even if the probability has to be close or equal to 1. Moreover, the learning power is strictly increasing when the probability decreases. Hence, the question arises if there exist ``natural'' formal learning models that reflect this human abilities. It turns out that this question can be answered affirmatively when dealing with conservative, strong-monotonic and monotonic probabilistic inductive inference with respect to appropriate hypotheses spaces. In particular, we prove for monotonic inductive learning that probabilistic learning is more powerful than deterministic learning even if the probability is claimed to be 1. Furthermore, we investigate if and how the additional power of probabilistic learning machines can be characterized in quantitative terms. Our first approach deals with learning machines having access to an oracle, i.e., we investigate if the additional power of probabilistic learning machines can be compensated with the help of a ``teacher''. Thereby, we show that each learning problem which can be solved by a probabilistic learning machine with a probability p>1/2 can be solved by a learning machine having access to an oracle which is Turing-equivalent to the halting problem. Our second approach is motivated by the fact that each learning problem which can be solved by a probabilistic learning machine with a probability p>1/2 can be solved by a deterministic learning machine which may construct new hypotheses during its learning process. Thus, we investigate ``how much work'' a deterministic learning machine has to perform in order to even out the additional power of a probabilistic inference machine.