Proseminar Künstliche Intelligenz

Solving games with AI has been an longstanding research benchmark in the field. While chess was  “solved”, go has been elusive due to the much larger search space. In this work we want to take a look how large search-spaces can be searched efficiently with learned heuristics.

Referenzen:

1. Mastering the game of Go with deep neural networks and tree search

Betreuer: Jakob Karalus

As creating computer processable knowledge representation systems is deemed to be a sometimes tedious task that needs the help and background knowledge of domain experts, such as medical doctors, engineers or a pizza baker, research for automatic ontology population is an ongoing topic in contemporary research. In order to extract ontological knowledge out of unstructured data i.e. large text corpora it is necessary to find algorithms that can detect concepts and relations between them reliably. In 1992 Marti A. Hearst and her group presented an algorithm to automatically detect and extract a certain linguistic relation out of large collections of English texts. Her pattern-based approach presented in this paper was widely recognized and adopted for automatic relation extraction, and became even more prominent with the rise of the World Wide Web and the massive amounts of text data along with it.

Referenzen:

1. Automatic Acquisition of Hyponyms from Large Text Corpora

Betreuer: Michael Welt

While learning with a reward function gives great results, but unfortunately it is not always possible to define a good reward function. In this topic we want to take a look a Human-in-the-loop Reinforcement Learning and investigate one approach how one could replace the reward function with human feedback.

Referenzen:

1. Deep Reinforcement Learning from Human Preferences

Betreuer: Jakob Karalus

In classical planning, the task is to drive a system from a given initial state into a goal state by applying actions whose effects are deterministic and known. Classical planning can be formulated as search problem whose nodes represent the states of the system or enviroment, and whose edges capture the state transitions that the actions make possible. State-of-the-art methods in classical planning search towards the goal using heuristic functions that are automatically derived from the problem.

Referenzen: 

1. A Concise Introduction to Models and Methods for Automated Planning (nur Teile von Kapitel 2)

Betreuer: Conny Olz

While the question how an Agent has to balance exportation vs exploitation is an essential one, the question how an Agent can effectively explore an unknow high dimensional space (with potential sparse rewards) is also highly complex. In this topic we want to take a look at one particular method how agents can perform efficient exploration by “First return, then explore”

Referenzen:

1. First return, then explore

Betreuer: Jakob Karalus

As an example for a structured knowledge representation system the WordNet database is established and well-cited in the literature for over three centuries now. Although first created in the 1980s, it is still developed and extended as of today by Princeton University. WordNet is an on-line lexical reference system whose design was inspired by psycholinguistic theories of human lexical memory. English nouns, verbs, and adjectives are organized into synonym sets, each representing one underlying lexical concept. Different relations link the synonym sets.

Referenzen:

1. Introduction to WordNet: An On-line Lexical Database (only available via Uni-Ulm internal network or VPN)
2. WordNet | A Lexical Database for English (princeton.edu)

Betreuer: Michael Welt

Games have always been a fertile ground for advancements in computer science, operations research and artificial intelligence. Solitaire card games, and Freecell in particular, have been the subject of study in both the academic literature, where they are used as a benchmark for planning heuristics, and in popular literature. Here an approach which provides provably optimal solutions to solitaire games shall be studied. It uses A* search together with an admissible heuristic function that is based on analyzing a directed graph whose cycles represent deadlock situations in the game state.

Referenzen:

1. Optimal Solitaire Game Solutions using A∗ Search and Deadlock Analysis

Betreuer: Conny Olz

An artificial intelligence system, such as a robot or a program may have a fault, which causes the system to behave abnormally. Since a system can be large and complex, it is often difficult to determine, which exactly components of the systems are responsible for the fault. In model-based diagnosis, a model of the system, such as a circuit, is used to determine possible faults. In a Reiter's Hitting Tree Set algorithm [Reiter, 1987], a model of the system is tested by repeatedly excluding subsets of the systems components until the fault is no longer observed. This way all minimal sets of components that cause the fault can be systematically explored. The goal of this seminar work, is to describe this algorithm and discuss its (dis)advantages.

Referenzen: 

1. Model-based Diagnosis: An Overview
2. A Correction to the Algorithm in Reiter's Theory of Diagnosis

Betreuer: Yevgeny Kazakov

Resolution is a well-known general-purpose theorem proving technique that can be used for checking if a set of first-order formulas is contradictory. Sometimes, proving a contradiction may not be sufficient, and it important to understand which exactly formulas cause it, e.g., for debugging purpose. A not very widely known extension of the resolution procedure with so-called answer literals, can be used to accomplish this task.

Referenzen:

1. Theorem-Proving by Resolution as a Basis for Question-Answering Systems

Betreuer: Yevgeny Kazakov

Dots-And-Boxes is a well-known and widely-played combinatorial game. While the rules of play are very simple, the state space for even very small games is extremely large, and finding the outcome under optimal play is correspondingly hard. In this paper we introduce a Dots-And-Boxes solver.
Our approach uses Alpha-Beta search and applies a number of techniques that reduce the search space to a manageable size.

Referenzen:

1. Solving Dots-And-Boxes

Betreuer: Conny Olz

A taxonomy is one of the most common representation of semantic "is-a" relationship between terms describing sets of entities. For example, "boy" is-a "child", "child" is-a "human", "human" is-an "animal". Taxonomies of specialised vocabularies of terms are used in many applications, such as medical expert system. For example, one of the commonly used taxonomies in Medicine is the "International Classification of Diseases" (short: ICD), which organises all known human diseases in a hierarchy according to their types, such as "infectious diseases" or "cardio-vascular diseases". Taxonomies are often constructed by repeatedly asking a human expert or an automated system whether a particular is-a relation between terms holds or not. For example, is "car" an "animal", or is "tree" a "plant"? For a given set of terms there can be a large number of potential questions like this. The enhanced traversal algorithm defines a particular strategy for asking such questions using which unnecessary questions can be avoided.

Referenzen:

1.  An empirical analysis of optimization techniques for terminological representation systems

Betreuer: Yevgeny Kazakov