Arbeitsgruppe Grundlagen der Künstlichen Intelligenz

Vollständige Liste der Publikationen

• sortiert nach Veröffentlichungszeitpunkt
• sortiert nach Autoren
• sortiert nach Themengebieten

Aktuelle Veröffentlichungen (letzte 12 Monate):

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

• Armin Hornung und Dapeng Zhang.
  On-Line Detection of Rule Violations in Table Soccer.
  In KI 2008: Advances in Artificial Intelligence (KI 2008), S. 217-224. Springer Berlin/Heidelberg, Kaiserslautern, Germany 2008.
  Poster.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  In table soccer, humans can not always thoroughly observe fast actions like rod spins and kicks. However, this is necessary in order to detect rule violations for example for tournament play. We describe an automatic system using sensors on a regular soccer table to detect rule violations in realtime. Naive Bayes is used for kick classication, the parameters are trained using supervised learning. In the on-line experiments, rule violations were detected at a higher rate than by the human players. The implementation proved its usefulness by being used by humans in real games and sets a basis for future research using probability models in table soccer.

• Thomas Keller und Sebastian Kupferschmid.
  Automatic Bidding for the Game of Skat.
  In Andreas R. Dengel, Karsten Berns, Thomas M. Breuel, Frank Bomarius und Thomas R. Roth-Berghofer, Proceedings of the 31st Annual German Conference on AI (KI 2008), S. 95-102. Springer-Verlag 2008.
  (Abstract einblenden) (Abstract ausblenden) (BIB) (PDF)
  

  In recent years, researchers started to study the game of Skat. The strength of existing Skat playing programs is definitely the card play phase. The bidding phase, however, was treated quite poorly so far. This is a severe drawback since bidding abilities influence the overall playing performance drastically. In this paper we present a powerful bidding engine which is based on a k-nearest neighbor algorithm.

• Dapeng Zhang und Armin Hornung.
  A Table Soccer Game Recorder.
  In Video Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2008). Nice, France 2008.
  Digest and Video.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  Our table soccer robot can already challenge even professional human players. Next, the robot should play games by using human-like skills. As a foundation of this research, our table soccer game recorder can save and replay games played by humans. This video shows the construction and functionality of the recording system.

  We use three types of sensors mounted on a regular game table. The movement of a game rod is measured by an optical distance sensor. Its turning is observed by a magnetic rotary encoder. Two laser measurement systems are synchronized to determine the position of the ball. The raw sensor data is smoothed by an approach using multi-model Kalman filter. We developed several software modules for the system. The modules provide a basis for the future research.

• Patrick Eyerich, Michael Brenner und Bernhard Nebel.
  On the Complexity of Planning Operator Subsumption.
  In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008). 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Formal action models play a central role in several subfields of AI because they are used to model application domains, e.g., in automated planning. However, there are hitherto no automated methods for relating such domain models to each other, in particular for checking whether one is a specialization or generalization of the other. In this paper, we introduce two kinds of subsumption relations between operators, both of which are suitable for modeling and verifying hierarchies between actions and operators: applicability subsumption considers an action to be more general than another if the latter can be replaced by the first at each point in each sound sequence of actions; abstraction subsumption exploits relations between actions from an ontological point of view. For both kinds of subsumption, we prove complexity results for verifying operator subsumption in three important subclasses: The problems are NP-complete when the expressiveness of the operators is restricted to the well-known basic STRIPS formalism, Sigma_p_2-complete when we admit boolean logical operators and undecidable when the full power of the planning language ADL is permitted.

• Gabriele Röger, Malte Helmert und Bernhard Nebel.
  On the Relative Expressiveness of ADL and Golog: The Last Piece in the Puzzle.
  In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008). 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Integrating agent programming languages and efficient action planning is a promising approach because it combines the expressive power of languages such as Golog with the possibility of searching for plans efficiently. In order to integrate a Golog interpreter with a planner, one has to understand, however, which part of the expressiveness of Golog can be captured by the planning language. Using Nebel's compilation framework, we identify a maximal fragment of basic action theories, the formalism Golog is based on, that is expressively equivalent to the ADL subset of PDDL. As we will show, almost all features that permit to specify incomplete information in basic action theories cannot be compiled to ADL.

• Jussi Rintanen, Bernhard Nebel, J. Christopher Beck und Eric Hansen.
  Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008).
  AAAI Press, Menlo Park, California USA 2008.
  

• Martin Wehrle, Sebastian Kupferschmid und Andreas Podelski.
  Useless Actions are Useful.
  In Jussi Rintanen, Bernhard Nebel, J. Christopher Beck und Eric Hansen, Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008), S. 388-395. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Planning as heuristic search is a powerful approach to solving domain independent planning problems. In recent years, various successful heuristics and planners like FF, LPG, Fast Downward or SGPlan have been proposed in this context. However, as heuristics only estimate the distance to goal states, a general problem of heuristic search is the existence of plateaus in the search space topology which can cause the search process to degenerate. Additional techniques like helpful actions or preferred operators that evaluate the "usefulness" of actions are often successful strategies to support the search in such situations.

  In this paper, we introduce a general method to evaluate the usefulness of actions. We propose a technique to enhance heuristic search by identifying "useless" actions that are not needed to find optimal plans. In contrast to helpful actions or preferred operators that are specific to the FF and Causal Graph heuristic, respectively, our method can be combined with arbitrary heuristics. We show that this technique often yields significant performance improvements.

• Malte Helmert und Héctor Geffner.
  Unifying the Causal Graph and Additive Heuristics.
  In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008). 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Many current heuristics for domain-independent planning, such as Bonet and Geffner's additive heuristic and Hoffmann and Nebel's FF heuristic, are based on delete relaxations. They estimate the goal distance of a search state by approximating the solution cost in a relaxed task where negative consequences of operator applications are ignored. Helmert's causal graph heuristic, on the other hand, approximates goal distances by solving a hierarchy of "local" planning problems that only involve a single state variable and the variables it depends on directly.

  Superficially, the causal graph heuristic appears quite unrelated to heuristics based on delete relaxation. In this contribution, we show that the opposite is true. Using a novel, declarative formulation of the causal graph heuristic, we show that the causal graph heuristic is the additive heuristic plus context. Unlike the original heuristic, our formulation does not require the causal graph to be acyclic, and thus leads to a proper generalization of both the causal graph and additive heuristics. Empirical results show that the new heuristic is significantly better informed than both Helmert's original causal graph heuristic and the additive heuristic and outperforms them across a wide range of standard benchmarks.

• Jan-Georg Smaus und Jörg Hoffmann.
  Relaxation Refinement: A New Method to Generate Heuristic Functions.
  In Doron Peled und Michael Wooldridge, Proceedings of the 5th Workshop on Model Checking and Artificial Intelligence (MoChArt 2008). Springer-Verlag 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In artificial intelligence, a relaxation of a problem is an overapproximation whose solution in every state of an explicit search provides a heuristic solution distance estimate. The heuristic guides the exploration, potentially shortening the search by exponentially many search states. The big question is how a good relaxation for the problem at hand should be derived. In model checking, overapproximations are called abstractions, and abstraction refinement is a powerful method developed to derive approximations that are sufficiently precise for verifying the system at hand. In our work, we bring these two paradigms together. We pioneer the application of (predicate) abstraction refinement for the generation of heuristic functions that are intelligently adapted to the problem at hand. We investigate how an abstraction refinement process for generating heuristic functions should differ from the process used in the verification context. We do so in the context of DMC of timed automata. We obtain a variety of interesting insights about this approach.

• Pascal Bercher und Robert Mattmüller.
  A Planning Graph Heuristic for Forward-Chaining Adversarial Planning.
  In Proceedings of the 18th European Conference on Artificial Intelligence (ECAI 2008). IOS Press 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  In contrast to classical planning, in adversarial planning, the planning agent has to face an adversary trying to prevent him from reaching his goals. In this paper, we investigate a forward-chaining approach to adversarial planning based on the AO* algorithm. The exploration of the underlying AND/OR graph is guided by a heuristic evaluation function, inspired by the relaxed planning graph heuristic used in the FF planner. Unlike FF, our heuristic uses an adversarial planning graph with distinct proposition and action layers for the protagonist and antagonist. First results suggest that in certain planning domains, our approach yields results competitive with the state of the art.

• Matthias Westphal und Stefan Wölfl.
  Bipath Consistency Revisited.
  In Proceedings of the ECAI'08 Workshop on Spatial and Temporal Reasoning. Patras, Greece 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  In the field of qualitative spatial and temporal reasoning combinations of constraint calculi have attracted considerable research interest in recent years. Beside combinations of spatial and temporal calculi, it is an important research topic to develop generic methods for combining calculi dealing with different spatial aspects. The prototypical example is the combination of the region connection calculus RCC8 and the point algebra first discussed by Gerevini and Renz, which allows to represent, and reason about, topological and size information about spatially extended objects. To solve constraints in this calculus, Gerevini and Renz also proposed an algorithm, the bipath consistency algorithm, which allows for deciding consistency of a given constraint network for specific sets of relations combining topology and size. In this article we will compare the "bipath consistency"-based combination method to the standard method, which is to combine calculi by generating a new calculus and applying the standard path consistency method. Gerevini and Renz's calculus combining topological and size information will serve as the running example of such combinations and also as a test case for an empirical analysis.

• Zeno Gantner, Matthias Westphal und Stefan Wölfl.
  GQR - A Fast Reasoner for Binary Qualitative Constraint Calculi.
  In Proceedings of the AAAI'08 Workshop on Spatial and Temporal Reasoning. Chicago, USA 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  GQR (Generic Qualitative Reasoner) is a solver for binary qualitative constraint networks. GQR takes a calculus description and one or more constraint networks as input, and tries to solve the networks using the path consistency method and (heuristic) backtracking. In contrast to specialized reasoners, it offers reasoning services for different qualitative calculi, which means that these calculi are not hard-coded into the reasoner. Currently, GQR supports arbitrary binary constraint calculi developed for spatial and temporal reasoning, such as calculi from the RCC family, the intersection calculi, Allen's interval algebra, cardinal direction calculi, and calculi from the OPRA family. New calculi can be added to the system by specifications in a simple text format or in an XML file format. The tool is designed and implemented with genericity and extensibility in mind, while preserving efficiency and scalability. The user can choose between different data structures and heuristics, and new ones can be easily added to the object-oriented framework. GQR is free software distributed under the terms of the GNU General Public License.

• Malte Helmert, Patrik Haslum und Jörg Hoffmann.
  Explicit-State Abstraction: A New Method for Generating Heuristic Functions.
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 1547-1550. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)
  

  Many AI problems can be recast as finding an optimal path in a discrete state space. An abstraction defines an admissible heuristic function as the distances in a smaller state space where arbitrary sets of states are "aggregated" into single states. A special case are pattern database (PDB) heuristics, which aggregate states iff they agree on the state variables inside the pattern. Explicit-state abstraction is more flexible, explicitly aggregating selected pairs of states in a process that interleaves composition of abstractions with abstraction of the composites. The increased flexibility gains expressive power: sometimes, the real cost function can be represented concisely as an explicit-state abstraction, but not as a PDB. Explicit-state abstraction has been applied to planning and model checking, with highly promising empirical results.

• Malte Helmert und Gabriele Röger.
  How Good is Almost Perfect?
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 944-949. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)
  

  Heuristic search using algorithms such as A* and IDA* is the prevalent method for obtaining optimal sequential solutions for classical planning tasks. Theoretical analyses of these classical search algorithms, such as the well-known results of Pohl, Gaschnig and Pearl, suggest that such heuristic search algorithms can obtain better than exponential scaling behaviour, provided that the heuristics are accurate enough.

  Here, we show that for a number of common planning benchmark domains, including ones that admit optimal solution in polynomial time, general search algorithms such as A* must necessarily explore an exponential number of search nodes even under the optimistic assumption of almost perfect heuristic estimators, whose heuristic error is bounded by a small additive constant.

  Our results shed some light on the comparatively bad performance of optimal heuristic search approaches in "simple" domains such as GRIPPER. They suggest that in many domains, further improvements in run-time require changes to other parts of the planning algorithm than the heuristic estimator.

• Malte Helmert und Robert Mattmüller.
  Accuracy of Admissible Heuristic Functions in Selected Planning Domains.
  In Proceedings of the 23nd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 938-943. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)
  

  The efficiency of optimal planning algorithms based on heuristic search crucially depends on the accuracy of the heuristic function used to guide the search. Often, we are interested in domain-independent heuristics for planning. In order to assess the limitations of domain-independent heuristic planning, it appears interesting to analyse the (in)accuracy of common domain-independent planning heuristics in the IPC benchmark domains. For a selection of these domains, we analytically investigate the accuracy of the h⁺ heuristic, the h^m family of heuristics, and certain (additive) pattern database heuristics, compared to the perfect heuristic h^*. Whereas h⁺ and additive pattern database heuristics usually return cost estimates proportional to the true cost, non-additive h^m and non-additive pattern-database heuristics can yield results underestimating the true cost by arbitrarily large factors.

• Silvia Richter, Malte Helmert und Matthias Westphal.
  Landmarks Revisited.
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 975-982. AAAI Press 2008.
  Note: After publication, we found a bug in our implementation that affects the results in the columns "CG heuristic/local" and "blind heuristic/local" of Table 1. The version of the paper available for download here corrects these errors.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)
  

  Landmarks for propositional planning tasks are variable assignments that must occur at some point in every solution plan. We propose a novel approach for using landmarks in planning by deriving a pseudo-heuristic and combining it with other heuristics in a search framework. The incorporation of landmark information is shown to improve success rates and solution qualities of a heuristic planner. We furthermore show how additional landmarks and orderings can be found using the information present in multi-valued state variable representations of planning tasks. Compared to previously published approaches, our landmark extraction algorithm provides stronger guarantees of correctness for the generated landmark orderings, and our novel use of landmarks during search solves more planning tasks and delivers considerably better solutions.

• Sebastian Kupferschmid, Martin Wehrle, Bernhard Nebel und Andreas Podelski.
  Faster than Uppaal?
  In A. Gupta und S. Malik, Proceedings of the 20th International Conference on Computer Aided Verification (CAV 2008), S. 552-555. Springer-Verlag 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  It is probably very hard to develop a new model checker that is faster than Uppaal for verifying correct timed automata. In fact, our tool Mcta does not even try to compete with Uppaal in this (i.e., Uppaal's) arena. Instead, Mcta is geared towards analyzing incorrect specifications of timed automata. It returns (shorter) error traces faster.

• Dapeng Zhang, Bernhard Nebel und Armin Hornung.
  Switching Attention Learning - A Paradigm for Introspection and Incremental Learning.
  In Proceedings of Fifth International Conference on Computational Intelligence, Robotics and Autonomous Systems (CIRAS 2008). Linz, Austria 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  Humans improve their sport skills by eliminating one recognizable weakness at a time. Inspired by this observation, we define a learning paradigm in which different learners can be plugged together. An extra attention model is in charge of iterating over them and chosing which one to improve next. The paradigm is named Switching Attention Learning (SAL). The essential idea is that improving one model in the system generates more "improvement space" for the others. Using SAL, an application for tracking the game ball in a table soccer game-recorder is implemented. We developed several models and learners which work together in the SAL framework, producing satisfying results in the experiments. The related problems, advantages, and perspective of the switching attention learning are discussed in this paper.

• Sebastian Kupferschmid, Jörg Hoffmann und Kim G. Larsen.
  Fast Directed Model Checking via Russian Doll Abstraction.
  In C. R. Ramakrishnan und J. Rehof, Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2008), S. 203-217. Springer-Verlag 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Directed model checking aims at speeding up the search for bugs in a system through the use of heuristic functions. Such a function maps states to integers, estimating the state's distance to the nearest error state. The search gives a preference to states with lower estimates. The key issue is how to generate good heuristic functions, i.e., functions that guide the search quickly to an error state. An arsenal of heuristic functions has been developed in recent years. Significant progress was made, but many problems still prove to be notoriously hard. In particular, a body of work describes heuristic functions for model checking timed automata in Uppaal, and tested them on a certain set of benchmarks. Into this arsenal we add another heuristic function. With previous heuristics, for the largest of the benchmarks it was only just possible to find some (unnecessarily long) error path. With the new heuristic, we can find provably shortest error paths for these benchmarks in a matter of seconds. The heuristic function is based on a kind of Russian Doll principle, where the heuristic for a given problem arises through using Uppaal itself for the complete exploration of a simplified instance of the same problem. The simplification consists in removing those parts from the problem that are distant from the error property. As our empirical results confirm, this simplification often preserves the characteristic structure leading to the error.

• Malte Helmert.
  Understanding Planning Tasks: Domain Complexity and Heuristic Decomposition.
  Band 4929 von Lecture Notes in Artificial Intelligence.
  Springer-Verlag, Heidelberg 2008.
  (Springer Online)
  

• Stephen Balakirsky, Stefano Carpin, Alexander Kleiner, Michael Lewis, Arnoud Visser, Jijun Wang und Vittorio Amos Ziparo.
  Towards heterogeneous robot teams for disaster mitigation: Results and Performance Metrics from Robocup Rescue.
  Journal of Field Robotics. 2007.
  (PDF)
  

• Alexander Kleiner und Christian Dornhege.
  Real-time Localization and Elevation Mapping within Urban Search and Rescue Scenarios.
  Journal of Field Robotics. 2007.
  (PDF)
  

• Alexander Kleiner, Christian Dornhege und Dali Sun.
  Mapping disaster areas jointly: RFID-Coordinated SLAM by Humans and Robots.
  In Proceedings of the IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2007). Rome, Italy 2007.
  (PDF)
  

• Holger Kenn und Alexander Kleiner.
  Towards the Integration of Real-Time Real-World Data in Urban Search and Rescue Simulation.
  In J. Loeffler and M. Kann, Int. Workshop on Mobile Information Technology for Emergency Response - MobileResponse 2007, S. 106-115. 2007.
  (PDF)
  

• Alexander Kleiner und Rainer Kuemmerle.
  Genetic MRF model optimization for real-time victim detection in Search and Rescue.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007). San Diego, California 2007.
  (PDF)
  

• Alexander Kleiner und Dali Sun.
  Decentralized SLAM for Pedestrians without direct Communication.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007). San Diego, California 2007.
  (PDF)
  

• Vittorio Amos Ziparo, Alexander Kleiner, Luca Marchetti, Alessandro Farinelli und Daniele Nardi.
  Cooperative Exploration for USAR Robots with Indirect Communication.
  In Proceedings of the 6th IFAC Symposium on Intelligent Autonomous Vehicles (IAV 2007). 2007.
  

• Christian Dornhege und Alexander Kleiner.
  Behavior maps for online planning of obstacle negotiation and climbing on rough terrain.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007). San Diego, California 2007.
  (PDF)
  

• Christian Dornhege und Alexander Kleiner.
  Behavior maps for online planning of obstacle negotiation and climbing on rough terrain.
  In Video Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007). San Diego, California 2007.
  

• Jochen Renz und Bernhard Nebel.
  Qualitative Spatial Reasoning using Constraint Calculi.
  In M. Aiello, I. Pratt-Hartmann und J. van Benthem, Handbook of Spatial Logics, S. 161-215. Springer-Verlag 2007.
  

• Marco Ragni, Stefan Schleipen und Felix Steffenhagen.
  Solving proportional analogies: A computational model.
  In Proceedings of AnICA 2007. 2007.
  

• Marco Ragni.
  Deductive Spatial Reasoning: A Computational and Cognitive Perspective.
  KI Themenheft Spatial Reasoning. 2007.