Research Group on the Foundations of Artificial Intelligence

Complete list of publications

• sorted by year of publication
• sorted by author
• sorted by area

Recent publications (last 12 months):

(Show all abstracts) (Hide all abstracts)

• Malte Helmert and Gabriele Röger.
  How Good is Almost Perfect?
  In Proceedings of the 23rd Conference on Artificial Intelligence (AAAI 2008). AAAI Press 2008.
  To appear.
  (Show abstract) (Hide abstract) (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 and Robert Mattmüller.
  Accuracy of Admissible Heuristic Functions in Selected Planning Domains.
  In Proceedings of the 23nd AAAI Conference on Artificial Intelligence (AAAI 2008). AAAI Press 2008.
  To appear.
  (Show abstract) (Hide abstract) (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.

• Sebastian Kupferschmid, Martin Wehrle, Bernhard Nebel and Andreas Podelski.
  Faster than Uppaal ?
  In A. Gupta and S. Malik, Proceedings of the 20th International Conference on Computer Aided Verification (CAV 2008), pp. 552-555. Springer-Verlag 2008.
  (Show abstract) (Hide abstract) (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.

• Sebastian Kupferschmid, Jörg Hoffmann and Kim G. Larsen.
  Fast Directed Model Checking via Russian Doll Abstraction.
  In C.R. Ramakrishnan and J. Rehof, Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2008), pp. 203-217. Springer-Verlag 2008.
  (Show abstract) (Hide abstract) (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.

• Stephen Balakirsky, Stefano Carpin, Alexander Kleiner, Michael Lewis, Arnoud Visser, Jijun Wang and 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 and Christian Dornhege.
  Real-time Localization and Elevation Mapping within Urban Search and Rescue Scenarios.
  Journal of Field Robotics. 2007.
  (PDF)
  

• Alexander Kleiner, Christian Dornhege and 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 and 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, pp. 106-115. 2007.
  (PDF)
  

• Alexander Kleiner and 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 and 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 and 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 and 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 and 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.
  

• Marco Ragni, Stefan Schleipen and 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.
  

• Henning Dierks, Sebastian Kupferschmid and Kim G. Larsen.
  Automatic Abstraction Refinement for Timed Automata.
  In Jean-François Raskin and P. S. Thiagarajan, Proceedings of the 5th International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS 2007), pp. 114-129. Springer-Verlag 2007.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  We present a fully automatic approach for counterexample guided abstraction refinement of real-time systems modelled in a subset of timed automata. Our approach is implemented in the Moby/RT tool environment, which is a CASE tool for embedded system specifications. Verification in Moby/RT is done by constructing abstractions of the semantics in terms of timed automata which are fed into the model checker Uppaal. Since the abstractions are over-approximations, absence of abstract counterexamples implies a valid result for the full model. Our new approach deals with the situation in which an abstract counterexample is found by Uppaal. The generated abstract counterexample is used to construct either a concrete counterexample for the full model or to identify a slightly refined abstraction in which the found spurious counterexample cannot occur anymore. Hence, the approach allows for a fully automatic abstraction refinement loop starting from the coarsest abstraction towards an abstraction for which a valid verification result is found. Nontrivial case studies demonstrate that this approach computes small abstractions fast without any user interaction.

• Marco Ragni, Bolormaa Tseden and Markus Knauff.
  Cross cultural similarities in topological reasoning.
  In COSIT 2007. Springer 2007.
  

• Malte Helmert, Patrik Haslum and Jörg Hoffmann.
  Flexible Abstraction Heuristics for Optimal Sequential Planning.
  In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007), pp. 176-183. AAAI Press 2007.
  (Show abstract) (Hide abstract) (PDF)
  

  We describe an approach to deriving consistent heuristics for automated planning, based on explicit search in abstract state spaces. The key to managing complexity is interleaving composition of abstractions over different sets of state variables with abstraction of the partial composites.

  The approach is very general and can be instantiated in many different ways by following different abstraction strategies. In particular, the technique subsumes planning with pattern databases as a special case. Moreover, with suitable abstraction strategies it is possible to derive perfect heuristics in a number of classical benchmark domains, thus allowing their optimal solution in polynomial time.

  To evaluate the practical usefulness of the approach, we perform empirical experiments with one particular abstraction strategy. Our results show that the approach is competitive with the state of the art.

• Dapeng Zhang and Bernhard Nebel.
  Recording and Segmenting Table Soccer Games -- Initial Results.
  In Proceedings of the 1st International Symposium on Skill Science 2007 (ISSS 2007), pp. 61-67. 2007.
  (Show abstract) (Hide abstract) (PDF)
  

  Robot KiRo can play one side of a table soccer game autonomously. Our recent research focuses on learning from and acting against human actions. Therefore recording and segmenting games played by humans are motivated. In this paper, the construction of a table soccer game recorder is sketched. An intuitive segmenting algorithm is implemented to explore the properties of the recorded data. A segmentation approach using Hidden Markov Models (HMMs) is proposed.

• Stefan Schleipen, Marco Ragni and Thomas Fangmeier.
  Negation in Spatial Reasoning: A Computational Approach.
  In Proceedings of the 30th Annual German Conference on Artificial Intelligence (KI 2007), pp. 175-189. 2007.
  

• Silvia Richter, Malte Helmert and Charles Gretton.
  A Stochastic Local Search Approach to Vertex Cover.
  In Proceedings of the 30th Annual German Conference on Artificial Intelligence (KI 2007), pp. 412-426. 2007.
  (Show abstract) (Hide abstract) (PDF)
  

  We introduce a novel stochastic local search algorithm for the vertex cover problem. Compared to current exhaustive search techniques, our algorithm achieves excellent performance on a suite of problems drawn from the field of biology. We also evaluate our performance on the commonly used DIMACS benchmarks for the related clique problem, finding that our approach is competitive with the current best stochastic local search algorithm for finding cliques. On three very large problem instances, our algorithm establishes new records in solution quality.

• Reinhard Moratz and Marco Ragni.
  Qualitative Spatial Reasoning about Relative Point Position.
  Journal of Visual Languages and Computing. 2007.
  

• Michael Brenner.
  Situation-aware interpretation, planning and execution of user commands by autonomous robots.
  In Proceedings of the 16th IEEE International Symposium on Roboz and Human Interactive Communication (ROMAN 2007). Jeju, Korea 2007.
  (PDF)
  

• Marco Ragni, Thomas Fangmeier and Stefan Schleipen.
  What about negation in spatial reasoning?
  In Proceedings of the 29th Annual Cognitive Science Conference (CogSci 2007). Lawrence Erlbaum Associates 2007.
  

• Marco Ragni and Felix Steffenhagen.
  Qualitative spatial reasoning: A cognitive and computational approach.
  In Proceedings of the 29th Annual Cognitive Science Conference (CogSci 2007). Lawrence Erlbaum Associates 2007.
  

• Nick Hawes, Aaron Sloman, Jeremy Wyatt, Michael Zillich, Henrik Jacobsson, Geert-Jan Kruijff, Michael Brenner, Gregor Berginc and Danijel Skocaj.
  Towards an Integrated Robot with Multiple Cognitive Functions.
  In Proceedings of the 22nd Conference on Artificial Intelligence (AAAI 2007). Vancouver, Canada 2007.
  (PDF)
  

• Dapeng Zhang and Bernhard Nebel.
  Learning a Table Soccer Robot a New Action Sequence by Observing and Imitating.
  In Proceedings of the Third Artificial Intelligence for Interactive Digital Entertainment Conference (AIIDE 2007), pp. 61-67. 2007.
  (Show abstract) (Hide abstract) (PDF)
  

  Star-Kick is a commercially available and fully automatic table soccer (foosball) robot, which plays table soccer games against human players on a competitive level. One of our research goals is to learn this table soccer robot skillful actions similar to a human player based on a moderate number of trials. Two independent learning algorithms are employed for learning a new lock and slide-kick action sequence by observing the performed actions and imitating the relative actions of a human player. The experiments with Star-Kick show that an effective action sequence can be learned in approximately 20 trials.

• Stefan Wölfl, Till Mossakowski and Lutz Schröder.
  Qualitative constraint calculi: Heterogeneous verification of composition tables.
  In Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2007), pp. 665-670. AAAI Press 2007.
  

• Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Diedrich Wolter, Berhard Nebel and Stefan Wölfl.
  SailAway: Formalizing navigation rules.
  In Proceedings of the Artificial and Ambient Intelligence Symposium on Spatial Reasoning and Communication (AISB 2007). 2007.
  

• Jan-Georg Smaus.
  On Boolean Functions Encodable as a Single Linear Pseudo-Boolean Constraint.
  In Pascal Van Hentenryck and Laurence Wolsey, Proceedings of the 4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2007), pp. 288-302. Springer 2007.
  (PDF)