Arbeitsgruppe Grundlagen der Künstlichen Intelligenz

[2008]    [2007]    [2006]    [2005]    [2004]    [2003]    [2002]    [2001]    [2000]    [1999]    [1998]    [1997]    [1996]   

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

2008

• Thomas Keller und Sebastian Kupferschmid.
  Automatic Bidding for the Game of Skat.
  In Proceedings of the 31st Annual German Conference on AI (KI 2008). Springer-Verlag 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (BIB)
  

  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.
  

• 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.
  To appear.
  (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.

• Martin Wehrle, Sebastian Kupferschmid und Andreas Podelski.
  Useless Actions are Useful.
  In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008). 2008.
  To appear.
  

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

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

• 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), NECTAR track. AAAI Press 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (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). AAAI Press 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (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). AAAI Press 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (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). AAAI Press 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (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)
  

2007

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

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

• Henning Dierks, Sebastian Kupferschmid und Kim G. Larsen.
  Automatic Abstraction Refinement for Timed Automata.
  In Jean-François Raskin und P. S. Thiagarajan, Proceedings of the 5th International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS 2007), S. 114-129. Springer-Verlag 2007.
  (Abstract einblenden) (Abstract ausblenden) (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 und Markus Knauff.
  Cross cultural similarities in topological reasoning.
  In COSIT 2007. Springer 2007.
  

• Malte Helmert, Patrik Haslum und Jörg Hoffmann.
  Flexible Abstraction Heuristics for Optimal Sequential Planning.
  In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007), S. 176-183. AAAI Press 2007.
  (Abstract einblenden) (Abstract ausblenden) (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 und Bernhard Nebel.
  Recording and Segmenting Table Soccer Games -- Initial Results.
  In Proceedings of the 1st International Symposium on Skill Science 2007 (ISSS 2007), S. 61-67. 2007.
  Poster.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  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 und Thomas Fangmeier.
  Negation in Spatial Reasoning: A Computational Approach.
  In Proceedings of the 30th Annual German Conference on Artificial Intelligence (KI 2007), S. 175-189. 2007.
  

• Silvia Richter, Malte Helmert und Charles Gretton.
  A Stochastic Local Search Approach to Vertex Cover.
  In Proceedings of the 30th Annual German Conference on Artificial Intelligence (KI 2007), S. 412-426. 2007.
  (Abstract einblenden) (Abstract ausblenden) (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 und 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 und 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 und 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 und 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 und 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), S. 61-67. 2007.
  Experiment Video.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  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 und 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), S. 665-670. AAAI Press 2007.
  

• Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Diedrich Wolter, Berhard Nebel und 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 und Laurence Wolsey, Proceedings of the 4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2007), S. 288-302. Springer 2007.
  (PDF)
  

• Gabriele Röger und Bernhard Nebel.
  Expressiveness of ADL and Golog: Functions Make a Difference.
  In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), S. 1051-1056. AAAI Press 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  The main focus in the area of action languages, such as GOLOG, was put on expressive power, while the development in the area of action planning was focused on efficient plan generation. An integration of GOLOG and planning languages would provide great advantages. A user could constrain a systems behavior on a high level using GOLOG, while the actual low-level actions are planned by an efficient planning system. First endeavors have been made by Eyerich et al. by identifying a subset of the situation calculus (which is the basis of GOLOG) with the same expressiveness as the ADL fragment of PDDL. However, it was not proven that the identified restrictions define a maximum subset. The most severe restriction appears to be that functions are limited to constants. We will show that this restriction is indeed necessary in most cases.

• Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet und Sven Koenig.
  Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning.
  In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), S. 1007-1012. AAAI Press 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  Heuristic search is a leading approach to domain-independent planning. For cost-optimal planning, however, existing admissible heuristics are generally too weak to effectively guide the search. Pattern database heuristics (PDBs), which are based on abstractions of the search space, are currently one of the most promising approaches to developing better admissible heuristics. The informedness of PDB heuristics depends crucially on the selection of appropriate abstractions (patterns). Although PDBs have been applied to many search problems, including planning, there are not many insights into how to select good patterns, even manually. What constitutes a good pattern depends on the problem domain, making the task even more difficult for domain-independent planning, where the process needs to be completely automatic and general. We present a novel way of constructing good patterns automatically from the specification of planning problem instances. We demonstrate that this allows a domain-independent planner to solve planning problems optimally in some very challenging domains, including a STRIPS formulation of the Sokoban puzzle.

• Marco Ragni und Felix Steffenhagen.
  A cognitive computational model for spatial reasoning.
  In AAAI Spring Symposium 2007. AAAI Press 2007.
  

• Sebastian Kupferschmid, Klaus Dräger, Jörg Hoffmann, Bernd Finkbeiner, Henning Dierks, Andreas Podelski und Gerd Behrmann.
  UPPAAL/DMC - Abstraction-based Heuristics for Directed Model Checking.
  In Orna Grumberg und Michael Huth, Proceedings of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2007), S. 679-682. Springer-Verlag 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Uppaal/DMC is an extension of Uppaal that provides generic heuristics for directed model checking. In this approach, the traversal of the state space is guided by a heuristic function which estimates the distance of a search state to the nearest error state. Our tool combines two recent approaches to design such estimation functions. Both are based on computing an abstraction of the system and using the error distance in this abstraction as the heuristic value. The abstractions, and thus the heuristic functions, are generated fully automatically and do not need any additional user input. Uppaal/DMC needs less time and memory to find shorter error paths than Uppaal's standard search methods.

• Vittorio Ziparo, Alexander Kleiner, Bernhard Nebel und Daniele Nardi.
  RFID-Based Exploration for Large Robot Teams.
  In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2007), S. 4606-4613. Rome, Italy 2007.
  (PDF)
  

• Geert-Jan Kruijff und Michael Brenner.
  Modelling Spatio-Temporal Comprehension in Situated Human-Robot Dialogue as Reasoning About Intentions and Plans.
  In AAAI Spring Symposium on Intentions. 2007.
  

• Sanjiang Li und Bernhard Nebel.
  Qualitative spatial representation and reasoning: A Hierarchical approach.
  The Computer Journal, S. 391-402. 2007.
  (Abstract einblenden) (Abstract ausblenden)
  

  The ability to reason in space is crucial for agents in order to make informed decisions. Current high-level qualitative approaches to spatial reasoning has serious decisionsciencies in not recting the hierarchical nature of spatial data and human spatial cognition. This paper proposes a framework for hierarchical representation and reasoning about topological information, where a continuous model of space is approximated by a collection of discrete sub-models, and spatial information is hierarchically represented in discrete sub-models in a rough set manner. The work is based on the GRCC theory, where continuous and discrete models of space are coped in a uni-ulmed way. Reasoning issues such as determining the mereological (part-whole) relations between two rough regions are also discussed. Moreover, we consider an important problem that is closely related to map generalization in cartography and Geographical Information Science. Given a spatial considerguration at a spatialner level, we show how to construct a configuration at a coarser level while preserving the mereological relations.

• Michael Brenner, Nick Hawes, John Kelleher und Jeremy Wyatt.
  Mediating Between Qualitative and Quantitative Representations for Task-Orientated Human-Robot Interaction.
  In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI 2007). Hyderabad, India 2007.
  

• Jens Classen, Patrick Eyerich, Gerhard Lakemeyer und Bernhard Nebel.
  Towards an Integration of Golog and Planning.
  In 20th International Joint Conference on Artificial Intelligence (IJCAI 2007). AAAI Press 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The action language Golog has been applied successfully to the control of robots, among other things. Perhaps its greatest advantage is that a user can write programs which constrain the search for an executable plan in a xible manner. However, when general planning is needed, Golog supports this only in principle, but does not measure up with state-of-the-art planners. In this paper we propose an integration of Golog and planning in the sense that planning problems, formulated as part of a Golog program, are solved by a modern planner during the execution of the program. Here we focus on the ADL subset of the plan language PDDL. First we show that the semantics of ADL can be understood as progression in the situation calculus, which underlies Golog, thus providing us with a correct embedding of ADL within Golog. We then show how Golog can be integrated with an existing ADL planner for closed-world initial databases and compare the performance of the resulting system with the original Golog.

• Robert Mattmüller und Jussi Rintanen.
  Planning for Temporally Extended Goals as Propositional Satisfiability.
  In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), S. 1966-1971. 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  Planning for temporally extended goals (TEGs) expressed as formulae of Linear-time Temporal Logic (LTL) is a proper generalization of classical planning, not only allowing to specify properties of a goal state but of the whole plan execution. Additionally, LTL formulae can be used to represent domain-specific control knowledge to speed up planning. In this paper we extend SAT-based planning for LTL goals (akin to bounded LTL model-checking in verification) to partially ordered plans, thus significantly increasing planning efficiency compared to purely sequential SAT planning. We consider a very relaxed notion of partial ordering and show how planning for LTL goals (without the next-time operator) can be translated into a SAT problem and solved very efficiently. The results extend the practical applicability of SAT-based planning to a wider class of planning problems. In addition, they could be applied to solving problems in bounded LTL model-checking more efficiently.

• Marco Ragni, Thomas Fangmeier, Lara Webber und Markus Knauff.
  Preferred mental models: How and why they are so important in human reasoning with spatial relations.
  In Proceedings of the Spatial Cognition V Conference. 2007.
  

2006

• Till Mossakowski, Lutz Schroeder und Stefan Wölfl.
  A categorical perspective on qualitative constraint calculi.
  In Qualitative Constraint Calculi - Application and Integration, Workshop at KI 2006. 2006.
  

• Marco Ragni.
  Reasoning in Dynamic Environments.
  In Qualitative Constraint Calculi - Application and Integration, Workshop at KI 2006. 2006.
  

• Patrick Eyerich, Bernhard Nebel, Gerhard Lakemeyer und Jens Classen.
  Golog and PDDL: What is the Relative Expressiveness?
  In Proc. of International Symposium on Practical Cognitive Agents and Robots. University of Western Australia Press 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Action formalisms such as GOLOG or FLUX have been developed primarily for representing and reasoning about change in a logical framework. For this reason, expressivity was the main goal in the development of these formalisms. In another line of research, efficiency of planning methods was the topmost goal resulting in the basic STRIPS language, which has only moderate expressivity. The planning language PDDL developed since 1998 is an extension of basic STRIPS with many expressive features. Now the interesting question is how PDDL compares to GOLOG or other action languages from an expressivity point of view. We will show that a GOLOG fragment, which we call Restricted Basic Action Theories, is as expressive as the ADL fragment of PDDL. To prove this equivalence we use the compilation framework. From a practical point of view, this result can be used for employing efficient planners inside a GOLOG interpreter.

• Michael Brenner und Bernhard Nebel.
  Continual Planning and Acting in Dynamic Multiagent Environments.
  In Proceedings of the International Symposium on Practical Cognitive Agents and Robots. Perth, Australia 2006.
  (PDF)
  

• Malte Helmert, Robert Mattmüller und Sven Schewe.
  Selective Approaches for Solving Weak Games.
  In Proceedings of the Fourth International Symposium on Automated Technology for Verification and Analysis (ATVA 2006), S. 200-214. Springer-Verlag 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  Model-checking alternating-time properties has recently attracted much interest in the verification of distributed protocols. While checking the validity of a specification in alternating-time temporal logic (ATL) against an explicit model is cheap (linear in the size of the formula and the model), the problem becomes EXPTIME-hard when symbolic models are considered. Practical ATL model-checking therefore often consumes too much computation time to be tractable.

  In this paper, we describe a novel approach for ATL model-checking, which constructs an explicit weak model-checking game on-the-fly. This game is then evaluated using heuristic techniques inspired by efficient evaluation algorithms for and/or-trees.

  To show the feasibility of our approach, we compare its performance to the ATL model-checking system MOCHA on some practical examples. Using very limited heuristic guidance, we achieve a significant speedup on these benchmarks.

• Jan-Georg Smaus.
  Representing Boolean Functions as Linear Pseudo-Boolean Constraints.
  In CP 2006 Workshop on the Integration of SAT and CP techniques. 2006.
  

• Jona Boeddinghaus, Marco Ragni, Markus Knauff und Bernhard Nebel.
  Simulating spatial reasoning using ACT-R.
  In Proceedings of the Seventh International Conference on Cognitive Modeling (ICCM 2006). 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We present an ACT-R model of spatial reasoning based on the SRM model (Spatial Reasoning by Models). This model maps spatial working memory to a two-dimensional array and uses a spatial focus to place objects in the array, manipulate the position of objects, and inspect the array to find spatial relations that are not given in the premises. Since the SRM explains many experimental findings only on a qualitative level, we implemented it into an ACT-R model. Not only does the model show some well-known effects in spatial reasoning and offers a good insight into the processes in the SRM model, but in addition it also allows us to predict reasoning times. The Model is accessible through a Java interface, which can be found and run from the following website http://www.informatik.uni-freiburg.de/~srm.

• Malte Helmert, Robert Mattmüller und Gabriele Röger.
  Approximation Properties of Planning Benchmarks.
  In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), S. 585-589. 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  For many classical planning domains, the computational complexity of non-optimal and optimal planning is known. However, little is known about the area in between the two extremes of finding some plan and finding optimal plans. In this contribution, we provide a complete classification of the propositional domains from the first four International Planning Competitions with respect to the approximation classes PO, PTAS, APX, poly-APX, and NPO.

• Jörg Hoffmann, Jan-Georg Smaus, Andrey Rybalchenko, Sebastian Kupferschmid und Andreas Podelski.
  Using Predicate Abstraction to Generate Heuristic Functions in Uppaal.
  In Stefan Edelkamp und Alessio Lomuscio, Proceedings of the 4th Workshop on Model Checking and Artificial Intelligence (MoChArt 2006), S. 51-66. Springer-Verlag 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We focus on checking safety properties in networks of extended timed automata, with the well-known Uppaal system. We show how to use predicate abstraction, in the sense used in model checking, to generate search guidance, in the sense used in Artificial Intelligence (AI). This contributes another family of heuristic functions to the growing body of work on directed model checking. The overall methodology follows the pattern database approach from AI: the abstract state space is exhaustively built in a pre-process, and used as a lookup table during search. While typically pattern databases use rather primitive abstractions ignoring some of the relevant symbols, we use predicate abstraction, dividing the state space into equivalence classes with respect to a list of logical expressions (predicates). We empirically explore the behavior of the resulting family of heuristics, in a meaningful set of benchmarks. In particular, while several challenges remain open, we show that one can easily obtain heuristic functions that are competitive with the state-of-the-art in directed model checking.

• Marco Ragni, Thomas Fangmeier, Lara Webber und Markus Knauff.
  Complexity in Spatial Reasoning.
  In Proceedings of the 28th Annual Cognitive Science Conference (CogSci-06). 2006.
  

• Alexander Kleiner, Johann Prediger und Bernhard Nebel.
  RFID Technology-based Exploration and SLAM for Search And Rescue.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2006), S. 4054-4059. Beijing, China 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Robot search and rescue is a time critical task, i.e. a large terrain has to be explored by multiple robots within a short amount of time. The efficiency of exploration depends mainly on the coordination between the robots and hence on the reliability of communication, which considerably suffers under the hostile conditions encountered after a disaster. Furthermore, rescue robots have to generate a map of the environment which has to be sufficiently accurate for reporting the locations of victims to human task forces. Basically, the robots have to solve autonomously in real-time the problem of Simultaneous Localization and Mapping (SLAM). This paper proposes a novel method for real-time exploration and SLAM based on RFID tags that are autonomously distributed in the environment. We utilized the algorithm of Lu and Milios [8] for calculating globally consistent maps from detected RFID tags. Furthermore we show how RFID tags can be used for coordinating the exploration of multiple robots. Results from experiments conducted in the simulation and on a robot show that our approach allows the computationally efficient construction of a map within harsh environments, and coordinated exploration of a team of robots.

• Christian Dornhege und Alexander Kleiner.
  Visual Odometry for Tracked Vehicles.
  In Proceedings of the IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2006). Gaithersburg, USA 2006.
  (PDF)
  

• Alexander Kleiner, Nils Behrens und Holger Kenn.
  Wearable computing meets multiagent systems: a real-world interface for the RoboCupRescue simulation platform.
  In Proceedings of the Workshop on Agent Technology for Disaster Management at AAMAS'06, S. 116-123. Hakodate, Japan 2006.
  (PDF)
  

• Alexander Kleiner, Christian Dornhege, Rainer Kuemmerle, Michael Ruhnke, Bastian Steder, Bernhard Nebel, Patrick Doherty, Mariusz Wzorek, Piotr Rudol, Gianpaolo Conte, S. Durante und D. Lundstrom.
  RoboCupRescue - Simulation League Team RescueRobots Freiburg (Germany), Team Description Paper.
  In CDROM Proceedings of the International RoboCup Symposium '05. Bremen, Germany 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  This paper describes the approach of the RescueRobots Freiburg team, which is a team of students from the University of Freiburg that originates from the former CS Freiburg team (RoboCupSoccer) and the ResQ Freiburg team (RoboCupRescue Simulation). Furthermore we introduce linkMAV, a micro aerial vehicle platform. Our approach covers RFID-based SLAM and exploration, autonomous detection of relevant 3D structures, visual odometry, and autonomous victim identification. Furthermore, we introduce a custom made 3D Laser Range Finder (LRF) and a novel mechanism for the active distribution of RFID tags.

• Alexander Kleiner und Vittorio Ziparo.
  RoboCupRescue - Simulation League Team RescueRobots Freiburg (Germany), Team Description Paper.
  In CDROM Proceedings of the International RoboCup Symposium '06. Bremen, Germany 2006.
  (PDF)
  

• Malte Helmert.
  New Complexity Results for Classical Planning Benchmarks.
  In Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS 2006), S. 52-61. AAAI Press 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  The 3rd and 4th International Planning Competitions have enriched the set of benchmarks for classical propositional planning by a number of novel and interesting planning domains. Although they are commonly used for the purpose of evaluating planner performance, the planning domains themselves have not yet been studied in depth. In this contribution, we prove complexity results for the decision problems related to finding some plan, finding an optimal sequential plan, and finding an optimal parallel plan in these planning domains. Our results also provide some insights into the question why planning is hard for some of the domains under consideration.

• Stefan Ratschan und Jan-Georg Smaus.
  Verification-Integrated Falsification of Non-deterministic Hybrid Systems.
  In Proceedings of the 2nd IFAC Conference on Analysis and Design of Hybrid Systems (ADHS 2006). 2006.
  

• Marco Ragni und Stefan Wölfl.
  Temporalizing Cardinal Directions: From Constraint Satisfaction to Planning.
  In Proceedings of the Knowledge Representation Conference (KR 2006). 2006.
  (PDF)
  

• Marco Ragni und Felix Steffenhagen.
  An implementation of the SRM-model.
  In Technical Report of the Spatial Cognition Conference Poster Session. University Bremen 2006.
  

• Sebastian Kupferschmid und Malte Helmert.
  A Skat Player Based on Monte Carlo Simulation.
  In H. Jaap van den Herik, Paolo Ciancarini und H. H. L. M. Donkers, Proceedings of the Fifth International Conference on Computer and Games (CG 2006), S. 135-147. Springer-Verlag 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ) (BIB)
  

  We apply Monte Carlo simulation and alpha-beta search to the card game of Skat, which is similar to Bridge, but different enough to require some new algorithmic ideas besides the techniques developed for Bridge. Our Skat-playing program integrates well-known techniques such as move ordering with two new search enhancements. Quasi-symmetry reduction generalizes symmetry reductions, popularized by Ginsberg's Partition Search algorithm, to search states which are "almost equivalent". Adversarial heuristics generalize ideas from single-agent search algorithms like A* to two-player games, leading to guaranteed lower and upper bounds for the score of a game position. Combining these techniques with state-of-the-art tree search algorithms, our program determines the game-theoretical value of a typical Skat hand (with perfect information) in 10 milliseconds.

• Malte Helmert.
  The Fast Downward Planning System.
  Journal of Artificial Intelligence Research 26, S. 191-246. 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  Fast Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners such as HSP and FF, Fast Downward is a progression planner, searching the space of world states of a planning task in the forward direction. However, unlike other PDDL planning systems, Fast Downward does not use the propositional PDDL representation of a planning task directly. Instead, the input is first translated into an alternative representation called multi-valued planning tasks, which makes many of the implicit constraints of a propositional planning task explicit. Exploiting this alternative representation, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, called the causal graph heuristic, which is very different from traditional HSP-like heuristics based on ignoring negative interactionse of operators.

  In this article, we give a full account of Fast Downward's approach to solving multi-valued planning tasks. We extend our earlier discussion of the causal graph heuristic to tasks involving axioms and conditional effects and present some novel techniques for search control that are used within Fast Downward's best-first search algorithm: preferred operators transfer the idea of helpful actions from local search to global best-first search, deferred evaluation of heuristic functions mitigates the negative effect of large branching factors on search performance, and multi-heuristic best-first search combines several heuristic evaluation functions within a single search algorithm in an orthogonal way. We also describe efficient data structures for fast state expansion (successor generators and axiom evaluators) and present a new non-heuristic search algorithm called focused iterative-broadening search, which utilizes the information encoded in causal graphs in a novel way.

  Fast Downward has proven remarkably successful: It won the "classical" (i.e., propositional, non-optimising) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. Our experiments show that it also performs very well on the benchmarks of the earlier planning competitions and provide some insights about the usefulness of the new search enhancements.

• Sebastian Kupferschmid, Jörg Hoffmann, Henning Dierks und Gerd Behrmann.
  Adapting an AI Planning Heuristic for Directed Model Checking.
  In Antti Valmari, Proceedings of the 13th International SPIN Workshop (SPIN 2006), S. 35-52. Springer-Verlag 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  There is a growing body of work on directed model checking, which improves the falsification of safety properties by providing heuristic functions that can guide the search quickly towards short error paths. Techniques of this kind have also been made very successful in the area of AI Planning. Our main technical contribution is the adaptation of the most successful heuristic function from AI Planning to the model checking context, yielding a new heuristic for directed model checking. The heuristic is based on solving an abstracted problem in every search state. We adapt the abstraction and its solution to networks of communicating automata annotated with (constraints and effects on) integer variables. Since our ultimate goal in this research is to also take into account clock variables, as used in timed automata, our techniques are implemented inside Uppaal. We run experiments in some toy benchmarks for timed automata, and in two timed automata case studies originating from an industrial project. Compared to both blind search and some previously proposed heuristic functions, we consistently obtain significant, sometimes dramatic, search space reductions, resulting in likewise strong reductions of runtime and memory requirements.

2005

• Marco Ragni, Markus Knauff und Bernhard Nebel.
  A Computational Model for Spatial Reasoning with Mental Models.
  In Proceedings of the 27th Annual Cognitive Science Conference (CogSci-05). 2005.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We propose a computational model for spatial reasoning by means of mental models. Our SRM model (Spatial Reasoning by Models) maps spatial working memory to a twodimensional array and uses a spatial focus that places objects in the array, manipulates the position of objects, and inspects the array to find spatial relations that are not given in the premises. The SRM model results in a computational complexity measure that relies on the number of operations in the array and the number of relations that must be handled. The performance of the SRM model is compared to the performance of human subjects reported in the literature and in our own study.

• Marco Ragni und Alexander Scivos.
  Dependency Calculus: Reasoning in a General Point Algebra.
  In KI 2005: Advances in Artificial Intelligence, 28th Annual German Conference on AI. (KI 2005). 2005.
  (PDF)
  

• Marco Ragni und Stefan Wölfl.
  Temporalizing Spatial Calculi: On Generalized Neighborhood Graphs.
  In Proceedings of the 28th Annual German Conference on AI (KI 2005), S. 64-78. 2005.
  (PDF)
  

• Sylvie Thiebaux, Jörg Hoffmann und Bernhard Nebel.
  In Defense of Axioms in PDDL.
  Artificial Intelligence 168 (1-2), S. 38-69. 2005.
  (Abstract einblenden) (Abstract ausblenden)
  

  There is controversy as to whether explicit support for PDDL-like axioms and derived predicates is needed for planners to handle real-world domains effectively. Many researchers have deplored the lack of precise semantics for such axioms, while others have argued that it might be best to compile them away. We propose an adequate semantics for PDDL axioms and show that they are an essential feature by proving that it is impossible to compile them away if we restrict the growth of plans and domain descriptions to be polynomial. These results suggest that adding a reasonable implementation to handle axioms inside the planner is beneficial for the performance. Our experiments confirm this suggestion.

• Thilo Weigel, Klaus Rechert und Bernhard Nebel.
  Behavior Recognition and Opponent Modeling for Adaptive Table Soccer Playing.
  In U. Furbach, KI 2005: Advances in Artificial Intelligence. Proceedings of the 28th Annual German Conference on Artificial Intelligence, S. 335-350. Springer-Verlag 2005.
  

• Marco Ragni und Alexander Scivos.
  Dependency Calculus: Reasoning in a General Point Relation Algebra.
  In Poster Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005). 2005.
  (PDF)
  

• Alexander Kleiner, Michael Brenner, Tobias Braeuer, Christian Dornhege, Moritz Goebelbecker, Matthias Luber, Johann Prediger, Joerg Stueckler und Bernhard Nebel.
  Successful Search and Rescue in Simulated Disaster Areas.
  In Proceedings of the International RoboCup Symposium '05. Osaka, Japan 2005.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  RoboCupRescue Simulation is a large-scale multi-agent simulation of urban disasters where, in order to save lives and minimize damage, rescue teams must effectively cooperate despite sensing and communication limitations. This paper presents the comprehensive search and rescue approach of the ResQ Freiburg team, the winner in the RoboCupRescue Simulation league at RoboCup 2004. Specific contributions include the predictions of travel costs and civilian lifetime, the efficient coordination of an active disaster space exploration, as well as an any-time rescue sequence optimization based on a genetic algorithm. We compare the performances of our team and others in terms of their capability of extinguishing fires, freeing roads from debris, disaster space exploration, and civilian rescue. The evaluation is carried out with information extracted from simulation log files gathered during RoboCup 2004. Our results clearly explain the success of our team, and also confirm the scientific approaches proposed in this paper.

• Alexander Kleiner, Bastian Steder, Christian Dornhege, Daniel Hoefler, Daniel Meyer-Delius, Johann Prediger, Joerg Stueckler, Kolja Glogowski, Markus Thurner, Matthias Luber, Michael Schnell, Rainer Kuemmerle, Timothy Burk, Tobias Braeuer und Bernhard Nebel.
  RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany), Team Description Paper.
  In CDROM Proceedings of the International RoboCup Symposium '05. Osaka, Japan 2005.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  This paper describes the approach of the RescueRobots Freiburg team. RescueRobots Freiburg is a team of students from the university of Freiburg, that originates from the former CS Freiburg team (RoboCupSoccer) and the ResQ Freiburg team (RoboCupRescue Simulation). Due to the high versatility of the RoboCupRescue competition we tackle the three arenas by a a twofold approach: On the one hand we want to introduce robust vehicles that can safely be teleoperated through rubble and building debris while constructing three-dimensional maps of the environment. On the other hand we want to introduce a team of autonomous robots that quickly explore a large terrain while building a two-dimensional map. This two solutions are particularly wellsuited for the red and yellow arena, respectively. Our solution for the orange arena will finally be decided between these two, depending on the capabilities of both approaches at the venue. In this paper, we introduce some preliminary results that we achieved so far from map building, localization, and autonomous victim identification. Furthermore we introduce a custom made 3D Laser Range Finder (LRF) and a novel mechanism for the active distribution of RFID tags. 1 Introduction RescueRobots Freiburg is a team of students from the university of Freiburg. The team originates from the former CS Freiburg team[6], which won three times the RoboCup world championship in the RoboCupSoccer F2000 league, and the ResQ Freiburg team[2], which won the last RoboCup world championship in the RoboCupRescue Simulation league. The team approach proposed in this paper is based on experiences gathered at RoboCup during the last six years. Due to the high versatility of the RoboCupRescue competition we tackle the three arenas by a twofold approach: On the one hand we want to introduce a vehicle that can safely be teleoperated through rubble and building debris while constructing threedimensional maps of the environment. On the other hand we want to introduce an autonomous team of robots that quickly explore a large terrain while building a twodimensional map. This two solutions are particularly well-suited for the red and yellow arena, respectively. Our solution for the orange arena will finally be decided between these two, depending on the capabilities of both approaches at the venue.

• Jörg Hoffmann und Sebastian Kupferschmid.
  A Covering Problem for Hypercubes.
  In Leslie Pack Kaelbling und Alessandro Saffiotti, Poster Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), S. 1523-1524. 2005.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ) (BIB)
  

  We introduce a new NP-complete problem asking if a "query" hypercube is (not) covered by a set of other "evidence" hypercubes. This comes down to a form of constraint reasoning asking for the satisfiability of a CNF formula where the logical atoms are inequalities over single variables, with possibly infinite variable domains. We empirically investigate the location of the phase transition regions in two random distributions of problem instances. We introduce a solution method that iteratively constructs a representation of the non-covered part of the query cube. In particular, the method is not based on backtracking. Our experiments show that the method is, in a significant range of instances, superior to the backtracking method that results from translation to SAT, and application of a state-of-the-art DP-based SAT solver.

• Michael Brenner, Nanda Wijermans, Timo Nuessle und Bart de Boer.
  Simulating and Controlling Civilian Crowds in Robocup Rescue.
  In RoboCup. Osaka, Japan 2005.
  Winner of the RoboCupRescue Infrastructure Competition 2005.
  

• Stefan Wölfl und Till Mossakowski.
  CASL specifications of qualitative calculi.
  In Spatial Information Theory: Cognitive and Computational Foundations, Proceedings of COSIT'05, S. 200-217. 2005.
  

• Michael Brenner.
  Planning for Multiagent Environments: From Individual Perceptions to Coordinated Execution.
  In Workshop on Multiagent Planning and Scheduling (ICAPS 2005). Monterey, USA 2005.
  (PDF)
  

• Jussi Rintanen.
  Conditional planning in the discrete belief space.
  In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005). 2005.
  

• Markus Büttner und Jussi Rintanen.
  Satisfiability Planning with Constraints on the Number of Operators.
  In Proceedings of the Thirteenth International Conference of Automated Planning and Scheduling (ICAPS 2005). Monterey, Califonia, USA 2005.
  

• Markus Büttner.
  Enhanced Prefetching- and Caching Strategies for Single and Multi-Disk Systems.
  ACTA INFORMATICA 236. 2005.
  

• Stefan Wölfl.
  Events in branching time.
  Studia Logica 79 (2), S. 255-282. 2005.
  

• Thilo Weigel.
  KiRo -- A Table Soccer Robot Ready for the Market.
  Künstliche Intelligenz Heft 01/05. 2005.
  (PS.GZ) (PDF)
  

• Bernhard Nebel, Thilo Weigel und Joachim Koschikowski.
  Tischfußball, Hockey oder dergleichen und Verfahren zur automatischen Ansteuerung der an Stangen angeordneten Spielfiguren eines Tischspielgeräts für Fußball-, Hockey- oder dergleichen.
  Deutsches Patent- und Markenamt Patent DE 102 12 475. 2005.
  (PDF)
  

• Alexander Kleiner.
  Game AI: The shrinking gap between computer games and AI systems Ambient Intelligence.
  Ambient Intelligence:The evolution of technology, communication and cognition towards the future of human-computer interaction. 2005.
  (PDF)
  

• Alexander Scivos und Bernhard Nebel.
  The Finest of Its Class: The Natural Point-Based Ternary Calculus LR for Qualitative Spatial Reasoning.
  In Spatial Cognition IV, S. 283-303. Springer-Verlag 2005.
  

2004

• Marco Ragni und Stefan Wölfl.
  Branching Allen: Reasoning with Intervals in Branching Time.
  In Spatial Cognition IV: Reasoning, Action, Interaction, International Conference Spatial Cognition 2004, 2004. Proceedings. Springer-Verlag 2004.
  (PDF)
  

• Christian Freksa, Markus Knauff, Bernd Krieg-Brückner, Bernhard Nebel und Thomas Barkowsky.
  Spatial Cognition IV.
  Band 3343 von Lecture Notes in Artificial Intelligence.
  Springer-Verlag, Berlin, Heidelberg, New York 2004.
  

• Jussi Rintanen, Keijo Heljanko und Ilkka Niemelä.
  Parallel encodings of classical planning as satisfiability.
  In J. J. Alferes und J. Leite, Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004), S. 307-319. Springer-Verlag 2004.
  (PS.GZ) (PDF)
  

• Stefan Wölfl.
  Qualitative action theory: A comparison of the semantics of Alternating-time Temporal Logic and the Kutschera-Belnap approach to agency.
  In J. J. Alferes und J. Leite, Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004). Springer-Verlag 2004.
  (PS.GZ) (PDF)
  

• Jan-Georg Smaus.
  Termination of Logic Programs Using Various Dynamic Selection Rules.
  In Proceedings of the 20th International Conference on Logic Programming (ICLP'04). 2004.
  (PS.GZ) (PDF)
  

• Thilo Weigel, Dapeng Zhang, Klaus Rechert und Bernhard Nebel.
  Adaptive Vision for Playing Table Soccer.
  In S. Biundo, T. Frühwirth und G. Palm, KI 2004: Advances in Artificial Intelligence. Proceedings of the 27th Annual German Conference on Artificial Intelligence, S. 424-438. Springer-Verlag 2004.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  For real time object recognition and tracking often color-based methods are used. While these methods are very ecient, they usually dependent heavily on lighting conditions. In this paper we present a robust and ecient vision system for the table soccer robot KiRo. By exploiting knowledge about invariant characteristics of the table soccer game, the system is able to adapt to changing lighting conditions dynamically and to detect relevant objects on the table within a few milliseconds. We give experimental evidence for the robustness and efficiency of our approach.

• Moritz Tacke, Thilo Weigel und Bernhard Nebel.
  Decision-Theoretic Planning for Playing Table Soccer.
  In S. Biundo, T. Frühwirth und G. Palm, KI 2004: Advances in Artificial Intelligence. Proceedings of the 27th Annual German Conference on Artificial Intelligence, S. 213-225. Springer-Verlag 2004.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Table soccer (also called foosball) is much simpler than real soccer. Nevertheless, one faces the same challenges as in all other robotics domains. Sensors are noisy, actions must be selected under time pressure and the execution of actions is often less than perfect. One approach to solve the action selection problem in such a context is decision-theoretic planning, i.e., identifying the action that gives the maximum expected utility. In this paper we present a decisiontheoretic planning system suited for controlling the behavior of a table soccer robot. The system employs forward-simulation for estimating the expected utility of alternative action sequences. As demonstrated in experiments, this system outperforms a purely reactive approach in simulation. However, this superiority of the approach did not extend to the real soccer table.

• Sebastian Trüg, Jörg Hoffmann und Bernhard Nebel.
  Applying Automatic Planning Techniques to Airport Ground-Traffic Control: A Feasibility Study.
  In S. Biundo, T. Frühwirth und G. Palm, KI 2004: Advances in Artificial Intelligence. Proceedings of the 27th Annual German Conference on Artificial Intelligence, S. 183-197. Springer-Verlag 2004.
  

• Bernhard Nebel.
  Formal Methods in Robotics.
  In Logics in Artificial Intelligence, 9th European Conference (JELIA 2004), S. 4. Springer-Verlag 2004.
  

• Christian Köhler, Artur Ottlik, Hans-Hellmut Nagel und Bernhard Nebel.
  Qualitative Reasoning Feeding Back into Quantitative Model-Based Tracking.
  In Proceedings of the 16th European Conference on Artificial Intelligence (ECAI 2004), S. 1041-1042. IOS Press 2004.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ) (technical report; PDF) (technical report; PS.GZ)
  

  Tracking vehicles in image sequences of innercity road traffic scenes still constitutes a challenging task. Even if a-priori knowledge about the 3D shape of vehicles, of background structure and vehicle motion is provided, (partial) occlusion and dense vehicle queues easily can cause initialization and tracking failures. Improving the tracking approach requires numerous and time-consuming experiments. Yet, these difficulties can be eased considerably by endowing the system with a part of the qualitative knowledge, that a human observer uses in order to judge the results. In the case reported here, a system for qualitative reasoning has been coupled with a quantitative model-based tracking system in order to explore the feedback from qualitative reasoning into the geometric tracking subsystem.

• Bernhard Nebel und Yulia Babovitch-Lierler.
  When Are Behaviour Networks Well-Behaved?
  In Proceedings of the 16th European Conference on Artificial Intelligence (ECAI 2004), S. 672-676. IOS Press 2004.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Agents operating in the real world have to deal with a constantly changing and only partially predictable environment and are nevertheless expected to choose reasonable actions quickly. This problem is addressed by a number of action-selection mechanisms. Behaviour networks as proposed by Maes are one such mechanism, which is quite popular. In general, it seems not possible to predict when behaviour networks are well-behaved. However, they perform quite well in the robotic soccer context. In this paper, we analyse the reason for this success by identifying conditions that make behaviour networks goal converging, i.e., force them to reach the goals regardless of the details of the action selection scheme. In terms of STRIPS domains one could talk of self-solving planning domains.

• Jussi Rintanen.
  Evaluation strategies for planning as satisfiability.
  In R. Lopez de Mantaras und L. Saitta, Proceedings of the 16th European Conference on Artificial Intelligence (ECAI 2004), S. 682-687. IOS Press 2004.
  (PS.GZ) (PDF)
  

• Jussi Rintanen.
  Distance estimates for planning in the discrete belief space.
  In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI 2004), S. 525-530. AAAI Press 2004.
  (PS.GZ) (PDF)
  

• Christian Köhler.
  Selecting Ghosts and Queues from a Car Trackers Output using a Spatio-Temporal Query Language.
  In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2004), S. 619-624. Washington, D.C., USA 2004.
  (PDF) (PS.GZ)
  

• Jörg Hoffmann, Julie Porteous und Laura Sebastia.
  Ordered Landmarks in Planning.
  Journal of Artificial Intelligence Research 22, S. 215-278. 2004.
  (PS.GZ)
  

• Timo Nuessle, Alexander Kleiner und Michael Brenner.
  Approaching Urban Disaster Reality: The ResQ Firesimulator.
  In Proceedings of the International RoboCup Symposium '04. Lisbon, Portugal 2004.
  (PDF)
  

• Alexander Kleiner, Michael Brenner, Tobias Braeuer, Christian Dornhege, Moritz Goebelbecker, Matthias Luber, Johann Prediger und Joerg Stueckler.
  ResQ Freiburg: Team Description and Evaluation, Team Description Paper, Rescue Simulation League.
  In CDROM Proceedings of the International RoboCup Symposium '04. Lisbon, Portugal 2004.
  (PDF)
  

• Malte Helmert.
  A Planning Heuristic Based on Causal Graph Analysis.
  In Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), S. 161-170. AAAI Press 2004.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  In recent years, heuristic search methods for classical planning have achieved remarkable results. Their most successful representative, the FF algorithm, performs well over a wide spectrum of planning domains and still sets the state of the art for STRIPS planning. However, there are some planning domains in which algorithms like FF and HSP perform poorly because their relaxation method of ignoring the "delete lists" of STRIPS operators loses too much vital information.

  Planning domains which have many dead ends in the search space are especially problematic in this regard. In some domains, dead ends are readily found by the human observer yet remain undetected by all propositional planning systems we are aware of. We believe that this is partly because the STRIPS representation obscures the important causal structure of the domain, which is evident to humans.

  In this paper, we propose translating STRIPS problems to a planning formalism with multi-valued state variables in order to expose this underlying causal structure. Moreover, we show how this structure can be exploited by an algorithm for detecting dead ends in the search space and by a planning heuristic based on hierarchical problem decomposition.

  Our experiments show excellent overall performance on the benchmarks from the international planning competitions.

• Ronen Brafman und Jörg Hoffmann.
  Conformant Planning via Heuristic Forward Search: A New Approach.
  In Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), S. 355-364. AAAI Press 2004.
  (PS.GZ)
  

• Jussi Rintanen.
  Complexity of planning with partial observability.
  In Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), S. 345-354. AAAI Press 2004.
  (PS.GZ) (PDF)
  

• Jussi Rintanen.
  Phase transitions in classical planning: An experimental study.
  In Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), S. 101-110. AAAI Press 2004.
  (PS.GZ) (PDF)
  

• Jussi Rintanen.
  Phase transitions in classical planning: An experimental study.
  In Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning (KR 2004), S. 710-719. AAAI Press 2004.
  (PS.GZ) (PDF)
  

• Bernd Becker, Markus Behle, Fritz Eisenbrand, Martin Fränzle, Marc Herbstritt, Christian Herde, Jörg Hoffmann, Daniel Kröning, Bernhard Nebel, Ilia Polian und Ralf Wimmer.
  Bounded Model Checking and Inductive Verification of Hybrid Discrete-continuous Systems.
  In Proceedings GI/ITG/GMM-Workshop Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen, S. 65-75. Kaiserslautern 2004.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We present a concept to signicantly advance the state of the art for bounded model checking (BMC) and inductive verication (IV) of hybrid discrete-continuous systems. Our approach combines the expertise of partners coming from dierent domains, like hybrid systems modeling and digital circuit verication, bounded planning and heuristic search, combinatorial optimization and integer programming. After sketching the overall verication ow we present rst results indicating that the combination and tight integration of dierent verication engines is a rst step to pave the way to fully automated BMC and IV of medium to large-scale networks of hybrid automata.

2003

• Marco Ragni.
  Temporalizing Spatial Calculi.
  In Proceedings of the KRR-WS of the Nineteenth National Conference on Artificial Intelligence (AAAI 2004). 2003.
  

• Marco Ragni.
  An Arrangement Calculus, Its Complexity and Algorithmic Properties.
  In KI 2003: Advances in Artificial Intelligence, 26th Annual German Conference on AI (KI 2003). 2003.
  

• Marco Ragni.
  An Arrangement Calculus.
  In Proceedings of the WS on Knowledge Representation and Reasoning, 18th International Joint Conference on Artificial Intelligence (IJCAI-03). 2003.
  

• Günther Görz und Bernhard Nebel.
  Künstliche Intelligenz.
  Fischer, Frankfurt/Main 2003.
  (Amazon)
  

• Erik Schulenburg, Thilo Weigel und Alexander Kleiner.
  Self-Localization in Dynamic Environments based on Laser and Vision Data.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'03), S. 998-1004. Las Vegas, USA 2003.
  (PS.GZ) (PDF)
  

• Reinhard Moratz, Bernhard Nebel und Cristian Freksa.
  Qualitative Spatial Reasoning about Relative Position: The Tradeoff between Strong Formal Properties and Successful Reasoning about Route Graphs.
  In Spatial Cognition III, Routes and Navigation, Human Memory and Learning, Spatial Representation and Spatial Learning, S. 385-400. Springer-Verlag 2003.
  

• Michael Brenner.
  Multiagent Planning with Partially Ordered Temporal Plans.
  In Proceedings of IJCAI'03. Acapulco, Mexico 2003.
  (PDF)
  

• Jörg Hoffmann.
  Utilizing Problem Structure in Planning: A Local Search Approach.
  Band 2854 von Lecture Notes in Artificial Intelligence.
  Springer-Verlag, Berlin, Heidelberg, New York 2003.
  (Springer Online) (extended abstract; PS.GZ)
  

• Michael Brenner.
  A Multiagent Planning Language.
  In Workshop on PDDL (ICAPS 2003). Trento, Italy 2003.
  (PDF)
  

• Malte Helmert.
  Complexity results for standard benchmark domains in planning.
  Artificial Intelligence 143 (2), S. 219-262. 2003.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  The efficiency of AI planning systems is usually evaluated empirically. For the validity of conclusions drawn from such empirical data, the problem set used for evaluation is of critical importance. In planning, this problem set usually, or at least often, consists of tasks from the various planning domains used in the first two international planning competitions, hosted at the 1998 and 2000 AIPS conferences. It is thus surprising that comparatively little is known about the properties of these benchmark domains, with the exception of BLOCKSWORLD, which has been studied extensively by several research groups.

  In this contribution, we try to remedy this fact by providing a map of the computational complexity of non-optimal and optimal planning for the set of domains used in the competitions. We identify a common transportation theme shared by the majority of the benchmarks and use this observation to define and analyze a general transportation problem that generalizes planning in several classical domains such as LOGISTICS, MYSTERY and GRIPPER. We then apply the results of that