• English
• Deutsch

• Albert-Ludwigs-Universität Freiburg
• Technische Fakultät
• Institut für Informatik

Publikationen nach Themengebieten

[Handlungsplanung]    [Wissensrepräsentation]    [Robotik]    [Andere]   

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

Handlungsplanung

• Kai M. Wurm, Christian Dornhege, Cyrill Stachniss, Bernhard Nebel und Wolfram Burgard.
  Coordinating Heterogeneous Teams of Robots using Temporal Symbolic Planning.
  Autonomous Robots. 2013.
  To appear.
  

• Stefan Wölfl (Hrsg.).
  Poster and Demo Track of the 35th German Conference on Artificial Intelligence (KI-2012), September 24-27, 2012, Saarbrücken, Germany.
  2012.
  (PDF)
  

• Yusra Alkhazraji, Martin Wehrle, Robert Mattmüller und Malte Helmert.
  A Stubborn Set Algorithm for Optimal Planning.
  In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012). 2012.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We adapt a partial order reduction technique based on stubborn sets, originally proposed for detecting dead ends in Petri Nets, to the setting of optimal planning. We demonstrate that stubborn sets can provide significant state space reductions on standard planning benchmarks, outperforming the expansion core method.

• Patrick Eyerich.
  Preferring Properly: Increasing Coverage while Maintaining Quality in Anytime Temporal Planning.
  In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012). 2012.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Temporal Fast Downward (TFD) is a successful temporal planning system that is capable of dealing with numerical values. Rather than decoupling action selection from scheduling, it searches directly in the space of time-stamped states, an approach that has shown to produce plans of high quality at the price of coverage. To increase coverage, TFD incorporates deferred evaluation and preferred operators, two search techniques that usually decrease the number of heuristic calculations by a large amount. However, the current definition of preferred operators offers only limited guidance in problems where heuristic estimates are weak or where subgoals require the execution of mutex operators. In this paper, we present novel methods for refinement of this definition and show how to combine the diverse strengths of different sets of preferred operators using a restarting procedure incorporated into a multi-queue best-first search. These techniques improve TFD's coverage drastically and preserve the average solution quality, leading to a system that solves more problems than each of the competitors of the temporal satisficing track of IPC 2011 and clearly outperforms all of them in terms of IPC score.

• Silvan Sievers, Manuela Ortlieb und Malte Helmert.
  Efficient Implementation of Pattern Database Heuristics for Classical Planning.
  In Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS 2012), S. 105-111. AAAI Press 2012.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Despite their general success in the heuristic search community, pattern database (PDB) heuristics have, until very recently, not been used by the most successful classical planning systems. We describe a new efficient implementation of pattern database heuristics within the Fast Downward planner. A planning system using this implementation is competitive with the state of the art in optimal planning, significantly improving over results from the previous best PDB heuristic implementation in planning.

• Patrick Eyerich.
  Preferring Properly: Increasing Coverage while Maintaining Quality in Anytime Temporal Planning.
  In Proceedings of the ICAPS-12 Workshop on Heuristics and Search for Domain Independent Planning (HSDIP 2012). 2012.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Temporal Fast Downward (TFD) is a successful temporal planning system that is capable of dealing with numerical values. Rather than decoupling action selection from scheduling, it searches directly in the space of time-stamped states, an approach that has shown to produce plans of high quality at the price of coverage. To increase coverage, TFD incorporates deferred evaluation and preferred operators, two search techniques that usually decrease the number of heuristic calculations by a large amount. However, the current definition of preferred operators offers only limited guidance in problems where heuristic estimates are weak or where subgoals require the execution of mutex operators. In this paper, we present novel methods for refinement of this definition and show how to combine the diverse strengths of different sets of preferred operators using a restarting procedure incorporated into a multi-queue best-first search. These techniques improve TFD's coverage drastically and preserve the average solution quality, leading to a system that solves more problems than each of the competitors of the temporal satisficing track of IPC 2011 and clearly outperforms all of them in terms of IPC score.

• Andreas Hertle, Christian Dornhege, Thomas Keller und Bernhard Nebel.
  Planning with Semantic Attachments: An Object-Oriented View.
  In Proceedings of the European Conference on Artificial Intelligence (ECAI 2012). 2012.
  (PDF) (BIB)
  

• Jens Claßen, Gabriele Röger, Gerhard Lakemeyer und Bernhard Nebel.
  PLATAS – Integrating Planning and the Action Language Golog.
  KI – Künstliche Intelligenz 26, S. 61-67. 2012.
  (Authors' preprint. The final publication is available at www.springerlink.com.).
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Action programming languages like Golog allow to define complex behaviors for agents on the basis of action representations in terms of expressive (first-order) logical formalisms, making them suitable for realistic scenarios of agents with only partial world knowledge. Often these scenarios include sub-tasks that require sequential planning. While in principle it is possible to express and execute such planning sub-tasks directly in Golog, the system can performance-wise not compete with state-of-the-art planners. In this paper, we report on our efforts to integrate efficient planning and expressive action programming in the Platas project. The theoretical foundation is laid by a mapping between the planning language Pddl and the Situation Calculus, which is underlying Golog, together with a study of how these formalisms relate in terms of expressivity. The practical benefit is demonstrated by an evaluation of embedding a Pddl planner into Golog, showing a drastic increase in performance while retaining the full expressiveness of Golog.

• Alper Aydemir, Moritz Göbelbecker, Andrzej Pronobis, Kristoffer Sjöö und Patric Jensfelt.
  Plan-based Object Search and Exploration Using Semantic Spatial Knowledge in the Real World.
  In Proceedings of the 5th European Conference on Mobile Robotics (ECMR 2011). 2011.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In this paper we present a principled planner based approach to the active visual object search problem in unknown environments. We make use of a hierarchical planner that combines the strength of decision theory and heuristics. Furthermore, our object search approach leverages on the conceptual spatial knowledge in the form of object cooccurences and semantic place categorisation. A hierarchical model for representing object locations is presented with which the planner is able to perform indirect search. Finally we present real world experiments to show the feasibility of the approach.

• Moritz Göbelbecker, Charles Gretton und Richard W. Dearden.
  A Switching Planner for Combined Task and Observation Planning.
  In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI 2011). 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  From an automated planning perspective the problem of practical mobile robot control in realistic environments poses many important and contrary challenges. On the one hand, the planning process must be lightweight, robust, and timely. Over the lifetime of the robot it must always respond quickly with new plans that accommodate exogenous events, changing objectives, and the underlying unpredictability of the environment. On the other hand, in order to promote efficient behaviours the planning process must perform computationally expensive reasoning about contingencies and possible revisions of subjective beliefs according to quantitatively modelled uncertainty in acting and sensing. Towards addressing these challenges, we develop a continual planning approach that switches between using a fast satisficing ``classical'' planner, to decide on the overall strategy, and decision-theoretic planning to solve small abstract subproblems where deeper consideration of the sensing model is both practical, and can significantly impact overall performance. We evaluate our approach in large problems from a realistic robot exploration domain.

• Moritz Göbelbecker, Alper Aydemir, Andrzej Pronobis, Kristoffer Sjöö und Patric Jensfelt.
  A Planning Approach to Active Visual Search in Large Environments.
  In Proceedings of the AAAI-11 Workshop on Automated Action Planning for Autonomous Mobile Robots (PAMR). 2011.
  Workshop version of the ECMR11 paper "Plan-based Object Search and Exploration Using Semantic Spatial Knowledge in the Real World".
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In this paper we present a principled planner based approach to the active visual object search problem in unknown environments. We make use of a hierarchical planner that combines the strength of decision theory and heuristics. Furthermore, our object search approach leverages on the conceptual spatial knowledge in the form of object co-occurrences and semantic place categorisation. A hierarchical model for representing object locations is presented with which the planner is able to perform indirect search. Finally we present real world experiments to show the feasibility of the approach.

• Raz Nissim, Jörg Hoffmann und Malte Helmert.
  Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning.
  In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011), S. 1983-1990. 2011.
  Erratum: In Section 7, we introduce greedy bisimulation as only respecting the bisimulation property for transitions (s, l, s') where sd(s) <= sd(s'). The implementation we evaluate in Section 8 is actually even more greedy than that, only respecting transitions where sd(s) < sd(s'). Using the definition from Section 7 leads to a strategy that behaves very similarly to the strategies using regular (non-greedy) bisimulation on these benchmarks..
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&s yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -- not distinguishing between certain groups of operators -- without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a hybrid of two such variants is competitive with the leading heuristic LM-cut.

• Moritz Göbelbecker, Charles Gretton und Richard W. Dearden.
  A Switching Planner for Combined Task and Observation Planning.
  In Electronic Proceedings of the Workshop on Decision Making in Partially Observable, Uncertain Worlds: Exploring Insights from Multiple Communities at the Twenty-Second International Join Conference on Artificial Intelligence (DMPOUW 2011). 2011.
  Workshop version of the AAAI11 paper of the same title..
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  From an automated planning perspective the problem of practical mobile robot control in realistic environments poses many important and contrary challenges. On the one hand, the planning process must be lightweight, robust, and timely. Over the lifetime of the robot it must always respond quickly with new plans that accommodate exogenous events, changing objectives, and the underlying unpredictability of the environment. On the other hand, in order to promote efficient behaviours the planning process must perform computationally expensive reasoning about contingencies and possible revisions of subjective beliefs according to quantitatively modelled uncertainty in acting and sensing. Towards addressing these challenges, we develop a continual planning approach that switches between using a fast satisficing ``classical'' planner, to decide on the overall strategy, and decision-theoretic planning to solve small abstract subproblems where deeper consideration of the sensing model is both practical, and can significantly impact overall performance. We evaluate our approach in large problems from a realistic robot exploration domain.

• Marc Hanheide, Charles Gretton, Richard Dearden, Nick Hawes, Jeremy Wyatt, Andrzej Pronobis, Alper Aydemir, Moritz Göbelbecker und Hendrik Zender.
  Exploiting Probabilistic Knowledge under Uncertain Sensing for Efficient Robot Behaviour.
  In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011). 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Robots must perform tasks efficiently and reliably while acting under uncertainty. One way to achieve efficiency is to give the robot common-sense knowledge about the structure of the world. Reliable robot behaviour can be achieved by modelling the uncertainty in the world probabilistically. We present a robot system that combines these two approaches and demonstrate the improvements in efficiency and reliability that result. Our first contribution is a probabilistic relational model integrating common-sense knowledge about the world in general, with observations of a particular environment. Our second contribution is a continual planning system which is able to plan in the large problems posed by that model, by automatically switching between decision-theoretic and classical procedures. We evaluate our system on object search tasks in two different real-world indoor environments. By reasoning about the trade-offs between possible courses of action with different informational effects, and exploiting the cues and general structures of those environments, our robot is able to consistently demonstrate efficient and reliable goal-directed behaviour.

• Thomas Keller und Patrick Eyerich.
  A Polynomial All Outcome Determinization for Probabilistic Planning.
  In Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp und Malte Helmert (Hrsg.), Proceedings of the 21th International Conference on Automated Planning and Scheduling (ICAPS 2011), S. 331-334. AAAI Press 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Most predominant approaches in probabilistic planning utilize techniques from the more thoroughly investigated field of classical planning by determinizing the problem at hand. In this paper, we present a method to map probabilistic operators to an equivalent set of probabilistic operators in a novel normal form, requiring polynomial time and space. From this, we directly derive a determinization which can be used for, \eg, replanning strategies incorporating a classical planning system. Unlike previously described all outcome determinizations, the number of deterministic operators is not exponentially but polynomially bounded in the number of parallel probabilistic effects, enabling the use of more sophisticated determinization-based techniques in the future.

• Carmel Domshlak, Malte Helmert, Erez Karpas, Emil Keyder, Silvia Richter, Gabriele Röger, Jendrik Seipp und Matthias Westphal.
  BJOLP: The Big Joint Optimal Landmarks Planner (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 91-95. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  BJOLP, The Big Joint Optimal Landmarks Planner uses landmarks to derive an admissible heuristic, which is then used to guide a search for a cost-optimal plan. In this paper we review landmarks and describe how they can be used to derive an admissible heuristic. We conclude with presenting the BJOLP planner.

• Silvia Richter, Matthias Westphal und Malte Helmert.
  LAMA 2008 and 2011 (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 50-54. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  LAMA is a propositional planning system based on heuristic search with landmarks. This paper describes two versions of LAMA that were entered into the 2011 International Planning Competition: the original LAMA as developed for the 2008 competition and a new re-implementation of LAMA that uses the latest version of the Fast Downward Planning Framework.

  Landmarks are propositions that must be true in every solution of a planning task. LAMA uses a heuristic derived from landmarks in conjunction with the well-known FF heuristic. LAMA builds on the Fast Downward Planning System using non-binary (but finite domain) state variables and multi-heuristic search. A weighted A* search is used with iteratively decreasing weights, so that the planner continues to search for plans of better quality until the search is terminated. LAMA combines cost-to-goal and distance-to-goal estimates with the aim of finding good solutions using reasonable runtime.

• Malte Helmert und Carmel Domshlak.
  LM-Cut: Optimal Planning with the Landmark-Cut Heuristic (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 103-105. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The LM-Cut planner uses the landmark-cut heuristic, introduced by the authors in 2009, within a standard A* progression search framework to find optimal sequential plans for STRIPS-style planning tasks. This short paper recapitulates the main ideas surrounding the landmark-cut heuristic and provides pointers for further reading.

• Raz Nissim, Jörg Hoffmann und Malte Helmert.
  The Merge-and-Shrink Planner: Bisimulation-based Abstraction for Optimal Planning (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 106-107. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Merge-and-shrink abstraction is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. The Merge-and-shrink planner uses two different strategies for making these choices, both based on the well-known notion of bisimulation. The resulting heuristics are used in two sequential runs of A* search.

• Carmel Domshlak, Malte Helmert, Erez Karpas und Shaul Markovitch.
  The SelMax Planner: Online Learning for Speeding up Optimal Planning (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 108-112. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The SelMax planner combines two state-of-the-art admissible heuristics using an online learning approach. In this paper we describe the online learning approach employed by SelMax, briefly review the Fast Downward framework, and describe the SelMax planner.

• Malte Helmert, Gabriele Röger, Jendrik Seipp, Erez Karpas, Jörg Hoffmann, Emil Keyder, Raz Nissim, Silvia Richter und Matthias Westphal.
  Fast Downward Stone Soup (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 38-45. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Fast Downward Stone Soup is a sequential portfolio planner that uses various heuristics and search algorithms that have been implemented in the Fast Downward planning system.

  We present a simple general method for concocting "planner soups", sequential portfolios of planning algorithms, and describe the actual recipes used for Fast Downward Stone Soup in the sequential optimization and sequential satisficing tracks of IPC 2011.

• Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger und Jendrik Seipp.
  FD-Autotune: Automated Configuration of Fast Downward (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 31-37. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The FD-Autotune submissions for the IPC-2011 sequential tracks consist of three instantiations of the latest, highly parametric version of the Fast Downward Planning Framework. These instantiations have been automatically configured for performance on a wide range of planning domains, using the well-known ParamILS configurator. Two of the instantiations were entered into the sequential satisficing track and one into the sequential optimising track. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by state-of-the-art automated configuration procedures, and how ParamILS was then used to obtain performance-optimised configurations.

• Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger und Jendrik Seipp.
  FD-Autotune: Domain-Specific Configuration using Fast Downward (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Planning and Learning Part. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The FD-Autotune learning planning system is based on the idea of domain-specific configuration of the latest, highly parametric version of the Fast Downward Planning Framework by means of a generic automated algorithm configuration procedure. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by state-of-the-art automated configuration procedures. FD-Autotune uses the well-known ParamILS configurator and was realised using the recently developed HAL experimentation environment.

• Malte Helmert, Gabriele Röger und Erez Karpas.
  Fast Downward Stone Soup: A Baseline for Building Planner Portfolios.
  In Proceedings of the ICAPS-2011 Workshop on Planning and Learning (PAL), S. 28-35. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Fast Downward Stone Soup is a sequential portfolio planner that uses various heuristics and search algorithms that have been implemented in the Fast Downward planning system.

  We present a simple general method for concocting "planner soups", sequential portfolios of planning algorithms, and describe the actual recipes used for Fast Downward Stone Soup in the sequential optimization and sequential satisficing tracks of IPC 2011.

  This paper is, first and foremost, a planner description. Fast Downward Stone Soup was entered into the sequential (non-learning) tracks of IPC 2011. Due to time constraints, we did not enter it into the learning competition at IPC 2011. However, we believe that the approach might still be of interest to the planning and learning community, as it represents a baseline against which other, more sophisticated portfolio learners can be usefully compared.

• Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger und Jendrik Seipp.
  FD-Autotune: Domain-Specific Configuration using Fast Downward.
  In Proceedings of the ICAPS-2011 Workshop on Planning and Learning (PAL), S. 13-20. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  In this work, we present the FD-Autotune learning planning system, which is based on the idea of domain-specific configuration of the latest, highly parametric version of the Fast Downward Planning Framework by means of a generic automated algorithm configuration procedure. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by a state-of-the-art automated configuration procedure. Additionally, we give preliminary results obtained from applying our approach to the nine domains of the IPC-2011 learning track, using the well-known ParamILS configurator and the recently developed HAL experimentation environment.

• Raz Nissim, Jörg Hoffmann und Malte Helmert.
  Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning.
  In Proceedings of the ICAPS-2011 Workshop on Heuristics for Domain-independent Planning (HDIP), S. 5-13. 2011.
  Superseded by the IJCAI 2011 paper by the same name.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&s yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -- not distinguishing between certain groups of operators -- without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a hybrid of two such variants is competitive with the leading heuristic LM-cut.

• Jendrik Seipp und Malte Helmert.
  Fluent Merging for Classical Planning Problems.
  In Proceedings of the ICAPS-2011 Workshop on Knowledge Engineering for Planning and Scheduling (KEPS), S. 47-53. 2011.
  Note: This version of the paper fixes two mistakes (in Def. 2 and in the text after Def. 3) that are present in the version of the paper that is linked from the workshop webpage..
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Fluent merging is a reformulation technique for classical planning problems that can be applied automatically or semi-automatically. The reformulation strives to transform a planning task into a representation that allows a planning algorithm to find solutions more efficiently or to find solutions of better quality. This work introduces different approaches for fluent merging and evaluates them within a state-of-the-art planning system.

• J. Benton, Patrick Eyerich und Subbarao Kambhampati.
  Enhancing Search for Satisficing Temporal Planning with Objective-driven Decisions.
  In Proceedings of the ICAPS-2011 Workshop on Heuristics for Domain-independent Planning, S. 59-65. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Heuristic best-first search techniques have recently enjoyed ever-increasing scalability in finding satisficing solutions to a variety of automated planning problems, and temporal planning is no different. Unfortunately, achieving efficient computational performance often comes at the price of clear guidance toward solution of high quality. This fact is sharp in the case of many best-first search temporal planners, who often use a node evaluation function that is mismatched with the objective function, reducing the likelihood that plans returned will have a short makespan but increasing search performance. To help mitigate matters, we introduce a method that works to progress search on actions declared ``useful'' according to makespan, even when the original search may ignore the makespan value of search nodes. We study this method and show that it increases over all plan quality in most of the benchmark domains from the temporal track of the 2008 International Planning Competition.

• Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp und Malte Helmert (Hrsg.).
  Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS 2011).
  AAAI Press, Menlo Park, California, USA 2011.
  

• Matthias Westphal, Christian Dornhege, Stefan Wölfl, Marc Gissler und Bernhard Nebel.
  Guiding the Generation of Manipulation Plans by Qualitative Spatial Reasoning.
  Spatial Cognition & Computation: An Interdisciplinary Journal 11 (1), S. 75-102. 2011.
  (Abstract einblenden) (Abstract ausblenden) (DOI) (BIB)
  

  Manipulation planning is a complex task for robots with a manipulator arm that need to grasp objects in the environment, specifically under narrow spatial conditions restricting the workspace of the robot. A popular approach for generating motion plans is probabilistic roadmap planning. However, the sampling strategy of such planners is usually unguided, and hence may lead to motion plans that seem counterintuitive for a human observer. In this article we present an approach that generates heuristics for the probabilistic sampling strategy from spatial plans that abstract from concrete metric data. These spatial plans describe a free trajectory in the workspace of the robot on a purely qualitative level, i.e., by employing spatial relations from formalisms considered in the domain of Qualitative Spatial and Tem- poral Reasoning. We discuss how such formalisms and constraint-based reasoning methods can be applied to approximate geometrically feasible motions. The paper is completed by an evaluation of a hybrid planning system in different spatial settings showing that run-times are notably improved when an abstract plan is considered as a guidance heuristic.

• D. Skočaj, M. Kristan, A. Leonardis, M. Mahnič, A. Vrečko, M. Janíček, G.-J. M. Kruijff, P. Lison, M. Zillich, C. Gretton, M. Hanheide und Moritz Göbelbecker.
  A system approach to interactive learning of visual concepts.
  In Tenth International Conference on Epigenetic Robotics (EPIROB 2010). 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In this work we present a system and underlying mechanisms for continuous learning of visual concepts in dialogue with a human.

• Kai M. Wurm, Christian Dornhege, Patrick Eyerich, Cyrill Stachniss, Bernhard Nebel und Wolfram Burgard.
  Coordinated Exploration with Marsupial Teams of Robots using Temporal Symbolic Planning.
  In Proceedings of the 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010). 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  The problem of autonomously exploring an environment with a team of robots received considerable attention in the past. However, there are relatively few approaches to coordinate teams of robots that are able to deploy and retrieve other robots. Efficiently coordinating the exploration with such marsupial robots requires advanced planning mechanisms that are able to consider symbolic deployment and retrieval actions. In this paper, we propose a novel approach for coordinating the exploration with marsupial robot teams. Our method integrates a temporal symbolic planner that explicitly considers deployment and retrieval actions with a traditional cost-based assignment procedure. Our approach has been implemented and evaluated in several simulated environments and with varying team sizes. The results demonstrate that our proposed method is able to coordinate marsupial teams of robots to efficiently explore unknown environments.

• Silvia Richter und Matthias Westphal.
  The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.
  Journal of Artificial Intelligence Research 39, S. 127-177. 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  LAMA is a classical planning system based on heuristic forward search. Its core feature is the use of a pseudo-heuristic derived from landmarks, propositional formulas that must be true in every solution of a planning task. LAMA builds on the Fast Downward planning system, using finite-domain rather than binary state variables and multi-heuristic search. The latter is employed to combine the landmark heuristic with a variant of the well-known FF heuristic. Both heuristics are cost-sensitive, focusing on high-quality solutions in the case where actions have non-uniform cost. A weighted A∗ search is used with iteratively decreasing weights, so that the planner continues to search for plans of better quality until the search is terminated.

  LAMA showed best performance among all planners in the sequential satisficing track of the International Planning Competition 2008. In this paper we present the system in detail and investigate which features of LAMA are crucial for its performance. We present individual results for some of the domains used at the competition, demonstrating good and bad cases for the techniques implemented in LAMA. Overall, we find that using landmarks improves performance, whereas the incorporation of action costs into the heuristic estimators proves not to be beneficial. We show that in some domains a search that ignores cost solves far more problems, raising the question of how to deal with action costs more effectively in the future. The iterated weighted A∗ search greatly improves results, and shows synergy effects with the use of landmarks.

• Blai Bonet und Malte Helmert.
  Strengthening Landmark Heuristics via Hitting Sets.
  In Helder Coelho, Rudi Studer und Michael Wooldridge (Hrsg.), Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), S. 329-334. IOS Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (technical report with proofs; PDF) (slides of Blai's ECAI 2010 presentation; PDF) (slides of Malte's SS 2010 group seminar presentation; PDF)
  

  The landmark cut heuristic is perhaps the strongest known polytime admissible approximation of the optimal delete relaxation heuristic h⁺. Equipped with this heuristic, a best-first search was able to optimally solve 40% more benchmark problems than the winners of the sequential optimization track of IPC 2008. We show that this heuristic can be understood as a simple relaxation of a hitting set problem, and that stronger heuristics can be obtained by considering stronger relaxations. Based on these findings, we propose a simple polytime method for obtaining heuristics stronger than landmark cut, and evaluate them over benchmark problems. We also show that hitting sets can be used to characterize h⁺ and thus provide a fresh and novel insight for better comprehension of the delete relaxation.

• Emil Keyder, Silvia Richter und Malte Helmert.
  Sound and Complete Landmarks for And/Or Graphs.
  In Helder Coelho, Rudi Studer und Michael Wooldridge (Hrsg.), Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), S. 335-340. IOS Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Landmarks for a planning problem are subgoals that are necessarily made true at some point in the execution of any plan. Since verifying that a fact is a landmark is PSPACE-complete, earlier approaches have focused on finding landmarks for the delete relaxation Π⁺. Furthermore, some of these approaches have approximated this set of landmarks, although it has been shown that the complete set of causal delete-relaxation landmarks can be identified in polynomial time by a simple procedure over the relaxed planning graph. Here, we give a declarative characterisation of this set of landmarks and show that the procedure computes the landmarks described by our characterisation. Building on this, we observe that the procedure can be applied to any delete-relaxation problem and take advantage of a recent compilation of the m-relaxation of a problem into a problem with no delete effects to extract landmarks that take into account delete effects in the original problem. We demonstrate that this approach finds strictly more causal landmarks than previous approaches and discuss the relationship between increased computational effort and experimental performance, using these landmarks in a recently proposed admissible landmark-counting heuristic.

• Malte Helmert.
  Lessons Learned from Benchmarking in the Automated Planning Community.
  In Proceedings of the ECAI 2010 Workshop on Benchmarking Intelligent (Multi-) Robot Systems. 2010.
  (PDF)
  

• Marc Hanheide, Nick Hawes, Jeremy Wyatt, Moritz Göbelbecker, Michael Brenner, Kristoffer Sjöö, Alper Aydemir, Patric Jensfelt, Hendrik Zender und Geert-Jan Kruijff.
  A Framework for Goal Generation and Management.
  In Proceedings of the AAAI Workshop on Goal-Directed Autonomy. 2010.
  (Abstract einblenden) (Abstract ausblenden) (BIB)
  

  Goal-directed behaviour is often viewed as an essential char- acteristic of an intelligent system, but mechanisms to generate and manage goals are often overlooked. This paper addresses this by presenting a framework for autonomous goal gener- ation and selection. The framework has been implemented as part of an intelligent mobile robot capable of exploring unknown space and determining the category of rooms au- tonomously. We demonstrate the efficacy of our approach by comparing the performance of two versions of our inte- grated system: one with the framework, the other without. This investigation leads us conclude that such a framework is desirable for an integrated intelligent system because it re- duces the complexity of the problems that must be solved by other behaviour-generation mechanisms, it makes goal- directed behaviour more robust in the face of a dynamic and unpredictable environments, and it provides an entry point for domain-specific knowledge in a more general system.

• Michael Brenner.
  Creating Dynamic Story Plots with Continual Multiagent Planning.
  In Maria Fox und David Poole (Hrsg.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010), S. 1517-1522. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  An AI system that is to create a story (autonomously or in interaction with human users) requires capabilities from many subfields of AI in order to create characters that themselves appear to act intelligently and believably in a coherent story world. Specifically, the system must be able to reason about the physical actions and verbal interactions of the characters as well as their perceptions of the world. Furthermore it must make the characters act believably--i.e. in a goal-directed yet emotionally plausible fashion. Finally, it must cope with (and embrace!) the dynamics of a multiagent environment where beliefs, sentiments, and goals may change during the course of a story and where plans are thwarted, adapted and dropped all the time. In this paper, we describe a representational and algorithmic framework for modelling such dynamic story worlds, Continual Multiagent Planning. It combines continual planning (i.e. an integrated approach to planning and execution) with a rich description language for modelling epistemic and affective states, desires and intentions, sensing and communication. Analysing story examples generated by our implemented system we show the benefits of such an integrated approach for dynamic plot generation.

• Patrick Eyerich, Thomas Keller und Malte Helmert.
  High-Quality Policies for the Canadian Traveler's Problem.
  In Maria Fox und David Poole (Hrsg.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010), S. 51-58. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost.

  We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.

• Patrick Eyerich, Thomas Keller und Malte Helmert.
  High-Quality Policies for the Canadian Traveler's Problem (Extended Abstract).
  In Ariel Felner und Nathan Sturtevant (Hrsg.), Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS 2010), S. 147-148. AAAI Press 2010.
  Extended abstract of the AAAI paper by the same name.
  (PDF)
  

• Michael Brenner.
  Dynamic Plot Generation by Continual Multiagent Planning (extended abstract).
  In Proceedings of the 9th Int. Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010). 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We describe how, by modelling plot generation as a Continual Multiagent Planning process, dynamic stories can be generated in which characters not only inteleave perception, action and interaction, but in which also beliefs and motivations may change repeatedly, thus driving the plot forward.

• J. Benton, Kartik Talamadupula, Patrick Eyerich, Robert Mattmüller und Subbarao Kambhampati.
  G-value Plateaus: A Challenge for Planning.
  In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 259-262. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Recent years have seen the development of several scalable planners, many of which follow the string of successes found in using heuristic, best-first search methods. While this provides positive reinforcement for continuing work along these lines, fundamental problems arise when handling objectives whose value does not change with each search operation. An extreme case of this occurs when handling the objective of generating a temporal plan with short makespan. Typically used heuristic search methods assume strictly positive edge costs for their guarantees on completeness and optimality to hold, while the usual "fattening" and "advance time" steps of heuristic search algorithms for temporal planning have the potential for zero-cost edges, resulting in "g-value plateaus". In this paper we point out some underlying difficulties with using modern heuristic search methods for optimizing makespan and discuss how the presence of these problems contributes to the poor performance of makespan-optimizing heuristic search planners. To further illustrate this, we show empirical results on recent benchmarks using a planner made with makespan optimization in mind.

• Moritz Göbelbecker, Thomas Keller, Patrick Eyerich, Michael Brenner und Bernhard Nebel.
  Coming Up with Good Excuses: What To Do When No Plan Can be Found.
  In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 81-88. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  When using a planner-based agent architecture, many things can go wrong. First and foremost, an agent might fail to execute one of the planned actions for some reasons. Even more annoying, however, is a situation where the agent is incompetent, i.e., unable to come up with a plan. This might be due to the fact that there are principal reasons that prohibit a successful plan or simply because the task's description is incomplete or incorrect. In either case, an explanation for such a failure would be very helpful. We will address this problem and provide a formalization of coming up with excuses for not being able to find a plan. Based on that, we will present an algorithm that is able to find excuses and demonstrate that such excuses can be found in practical settings in reasonable time.

• Malte Helmert und Hauke Lasinger.
  The Scanalyzer Domain: Greenhouse Logistics as a Planning Problem.
  In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 234-237. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We introduce the Scanalyzer planning domain, a domain for classical planning which models the problem of automatic greenhouse logistic management.

  At its mathematical core, the Scanalyzer domain is a permutation problem with striking similarities to common search benchmarks such as Rubik's Cube or TopSpin. At the same time, it is also a real application domain, and efficient algorithms for the problem are of considerable practical interest.

  The Scanalyzer domain was used as a benchmark for sequential planners at the last International Planning Competition. The competition results show that domain-independent automated planners can find solutions of comparable quality to those generated by specialized algorithms developed by domain experts, while being considerably more flexible.

• Robert Mattmüller, Manuela Ortlieb, Malte Helmert und Pascal Bercher.
  Pattern Database Heuristics for Fully Observable Nondeterministic Planning.
  In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 105-112. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF) (BIB)
  

  When planning in an uncertain environment, one is often interested in finding a contingent plan that prescribes appropriate actions for all possible states that may be encountered during the execution of the plan. We consider the problem of finding strong and strong cyclic plans for fully observable nondeterministic (FOND) planning problems. The algorithm we choose is LAO*, an informed explicit state search algorithm. We investigate the use of pattern database (PDB) heuristics to guide LAO* towards goal states. To obtain a fully domain-independent planning system, we use an automatic pattern selection procedure that performs local search in the space of pattern collections. The evaluation of our system on the FOND benchmarks of the Uncertainty Part of the International Planning Competition 2008 shows that our approach is competitive with symbolic regression search in terms of problem coverage and speed.

• Gabriele Röger und Malte Helmert.
  The More, the Merrier: Combining Heuristic Estimators for Satisficing Planning.
  In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 246-249. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (technical report; PDF)
  

  We empirically examine several ways of exploiting the information of multiple heuristics in a satisficing best-first search algorithm, comparing their performance in terms of coverage, plan quality, speed, and search guidance. Our results indicate that using multiple heuristics for satisficing search is indeed useful. Among the combination methods we consider, the best results are obtained by the alternation method of the "Fast Diagonally Downward" planner.

• Patrick Eyerich, Thomas Keller und Malte Helmert.
  High-Quality Policies for the Canadian Traveler's Problem.
  In Proceedings of the ICAPS-2010 Workshop on Planning and Scheduling Under Uncertainty. 2010.
  Superseded by the AAAI 2010 paper by the same name.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost.

  We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.

• Patrick Eyerich, Thomas Keller und Bernhard Nebel.
  Combining Action and Motion Planning via Semantic Attachments.
  In Proceedings of the Workshop on Combining Action and Motion Planning at ICAPS 2010 (CAMP 2010), S. 19. 2010.
  Extended Abstract.
  (PDF) (BIB)
  

• Nick Hawes, Marc Hanheide, Kristoffer Sjöö, Alper Aydemir, Patric Jensfelt, Moritz Göbelbecker, Michael Brenner, Hendrik Zender, Pierre Lison, Ivana Kruijff-Korbayov, Geert-Jan M. Kruijff und Michael Zillich.
  Dora The Explorer: A Motivated Robot.
  In Proc. of 9th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010). 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Dora the Explorer is a mobile robot with a sense of curios- ity and a drive to explore its world. Given an incomplete tour of an indoor environment, Dora is driven by internal motivations to probe the gaps in her spatial knowledge. She actively explores regions of space which she hasn't previously visited but which she expects will lead her to further unex- plored space. She will also attempt to determine the cate- gories of rooms through active visual search for functionally important objects, and through ontology-driven inference on the results of this search.

• Christian Dornhege, Marc Gissler, Matthias Teschner und Bernhard Nebel.
  Integrating Symbolic and Geometric Planning for Mobile Manipulation.
  In IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2009). 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Mobile manipulation requires to solve multiple subproblems. One is planning in high-dimensional configuration spaces, that we approach in this work. We decompose the manipulation problem into a symbolic and a geometric part. The symbolic part is implemented as a classical symbolic planner that tightly integrates a geometric planner enabling us to efficiently generate correct plans. A probabilistic roadmap planner constitutes the geometric part. During the computation of the roadmap we utilize proximity queries to determine non-colliding configurations and to verify collision-free paths between configurations accurately and efficiently. We demonstrate experiments in two scenarios, one of these being the manipulator dexterity test scenario that was used in NIST's response robot evaluation in Disaster City.

• Christian Dornhege, Patrick Eyerich, Thomas Keller, Sebastian Trüg, Michael Brenner und Bernhard Nebel.
  Semantic Attachments for Domain-Independent Planning Systems.
  In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 114-121. AAAI Press 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Solving real-world problems using symbolic planning often requires a simplified formulation of the original problem, since certain subproblems cannot be represented at all or only in a way leading to inefficiency. For example, manipulation planning may appear as a subproblem in a robotic planning context or a packing problem can be part of a logistics task. In this paper we propose an extension of PDDL for specifying semantic attachments. This allows the evaluation of grounded predicates as well as the change of fluents by externally specified functions. Furthermore, we describe a general schema of integrating semantic attachments into a forward-chaining planner and report on our experience of adding this extension to the planners FF and Temporal Fast Downward. Finally, we present some preliminary experiments using semantic attachments.

• Patrick Eyerich, Robert Mattmüller und Gabriele Röger.
  Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning.
  In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 130-137. AAAI Press 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF) (BIB)
  

  Planning systems for real-world applications need the ability to handle concurrency and numeric fluents. Nevertheless, the predominant approach to cope with concurrency followed by the most successful participants in the latest International Planning Competitions (IPC) is still to find a sequential plan that is rescheduled in a post-processing step. We present Temporal Fast Downward (TFD), a planning system for temporal problems that is capable of finding low-makespan plans by performing a heuristic search in a temporal search space. We show how the context-enhanced additive heuristic can be successfully used for temporal planning and how it can be extended to numeric fluents. TFD often produces plans of high quality and, evaluated according to the rating scheme of the last IPC, outperforms all state-of-the-art temporal planning systems.

• Dunbo Cai, Jörg Hoffmann und Malte Helmert.
  Enhancing the Context-Enhanced Additive Heuristic with Precedence Constraints.
  In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 50-57. AAAI Press 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Recently, Helmert and Geffner proposed the context-enhanced additive heuristic, where fact costs are evaluated relative to context states that arise from achieving first a pivot condition of each operator. As Helmert and Geffner pointed out, the method can be generalized to consider contexts arising from arbitrary precedence constraints over operator conditions instead. Herein, we provide such a generalization. We extend Helmert and Geffner's equations, and discuss a number of design choices that arise. Drawing on previous work on goal orderings, we design a family of methods for automatically generating precedence constraints. We run large-scale experiments, showing that the technique can help significantly, depending on the choice of precedence constraints. We shed some light on this by profiling the behavior of all possible precedence constraints, using a sampling technique.

• Malte Helmert und Carmel Domshlak.
  Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?
  In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 162-169. AAAI Press 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (Dagstuhl abstract; PDF)
  

  Current heuristic estimators for classical domain-independent planning are usually based on one of four ideas: delete relaxations, critical paths, abstractions, and, most recently, landmarks. Previously, these different ideas for deriving heuristic functions were largely unconnected.

  We prove that admissible heuristics based on these ideas are in fact very closely related. Exploiting this relationship, we introduce a new admissible heuristic called the landmark cut heuristic, which compares favourably with the state of the art in terms of heuristic accuracy and overall performance.

• Silvia Richter und Malte Helmert.
  Preferred Operators and Deferred Evaluation in Satisficing Planning.
  In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 273-280. AAAI Press 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Heuristic forward search is the dominant approach to satisficing planning to date. Most successful planning systems, however, go beyond plain heuristic search by employing various search-enhancement techniques. One example is the use of helpful actions or preferred operators, providing information which may complement heuristic values. A second example is deferred heuristic evaluation, a search variant which can reduce the number of costly node evaluations. Despite the wide-spread use of these search-enhancement techniques however, we note that few results have been published examining their usefulness. In particular, while various ways of using, and possibly combining, these techniques are conceivable, no work to date has studied the performance of such variations. In this paper, we address this gap by examining the use of preferred operators and deferred evaluation in a variety of settings within best-first search. In particular, our findings are consistent with and help explain the good performance of the winners of the satisficing tracks at IPC 2004 and 2008.

• Christoph Betz und Malte Helmert.
  Planning with h+ in Theory and Practice.
  In Proceedings of the 2nd Workshop on Heuristics for Domain-independent Planning at ICAPS 2009. 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Many heuristic estimators for classical planning are based on the so-called delete relaxation, which ignores negative effects of planning operators. Ideally, such heuristics would compute the actual goal distance in the delete relaxation, i.e., the cost of an optimal relaxed plan, denoted by h+. However, current delete relaxation heuristics only provide (often inadmissible) estimates to h+ because computing the correct value is an NP-hard problem.

  In this work, we consider the approach of planning with the actual h+ heuristic from a theoretical and computational perspective. In particular, we provide domain-dependent complexity results that classify some standard benchmark domains into ones where h+ can be computed efficiently and ones where computing h+ is NP-hard. Moreover, we study domain-dependent implementations of h+ which show that the h+ heuristic provides very informative heuristic estimates compared to other state-of-the-art heuristics.

• Gabriele Röger und Malte Helmert.
  Combining Heuristic Estimators for Satisficing Planning.
  In Proceedings of the 2nd Workshop on Heuristics for Domain-independent Planning at ICAPS 2009. 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The problem of effectively combining multiple heuristic estimators has been studied extensively in the context of optimal planning, but not in the context of satisficing planning. To narrow this gap, we empirically examine several ways of exploiting the information of multiple heuristics in a satisficing best-first search algorithm, comparing their performance in terms of coverage, plan quality and runtime. Our empirical results indicate that using multiple heuristics for satisficing search is indeed useful and that the best results are not obtained by the most obvious combination methods.

• Christoph Betz und Malte Helmert.
  Planning with h+ in Theory and Practice.
  In Bärbel Mertsching, Marcus Hund und Zaheer Aziz (Hrsg.), Proceedings of the 32nd Annual German Conference on Artificial Intelligence (KI 2009), S. 9-16. Springer-Verlag 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Many heuristic estimators for classical planning are based on the so-called delete relaxation, which ignores negative effects of planning operators. Ideally, such heuristics would compute the actual goal distance in the delete relaxation, i.e., the cost of an optimal relaxed plan, denoted by h+. However, current delete relaxation heuristics only provide (often inadmissible) estimates to h+ because computing the correct value is an NP-hard problem.

  In this work, we consider the approach of planning with the actual h+ heuristic from a theoretical and computational perspective. In particular, we provide domain-dependent complexity results that classify some standard benchmark domains into ones where h+ can be computed efficiently and ones where computing h+ is NP-hard. Moreover, we study domain-dependent implementations of h+ which show that the h+ heuristic provides very informative heuristic estimates compared to other state-of-the-art heuristics.

• Pascal Bercher und Robert Mattmüller.
  Solving Non-deterministic Planning Problems with Pattern Database Heuristics.
  In B. Mertsching, M. Hund und Z. Aziz (Hrsg.), Proceedings of the 32nd Annual Conference on Artificial Intelligence (KI 2009), S. 57-64. Springer-Verlag 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF) (BIB)
  

  Non-determinism arises naturally in many real-world applications of action planning. Strong plans for this type of problems can be found using AO* search guided by an appropriate heuristic function. Most domain-independent heuristics considered in this context so far are based on the idea of ignoring delete lists and do not properly take the non-determinism into account. Therefore, we investigate the applicability of pattern database (PDB) heuristics to non-deterministic planning. PDB heuristics have emerged as rather informative in a deterministic context. Our empirical results suggest that PDB heuristics can also perform reasonably well in non-deterministic planning. Additionally, we present a generalization of the pattern additivity criterion known from classical planning to the non-deterministic setting.

• Michael Brenner und Bernhard Nebel.
  Continual Planning and Acting in Dynamic Multiagent Environments.
  Journal of Autonomous Agents and Multiagent Systems 19 (3), S. 297-331. 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In order to behave intelligently, artificial agents must be able to deliberatively plan their future actions. Unfortunately, realistic agent environments are usually highly dynamic and only partially observable, which makes planning computationally hard. For most practical purposes this rules out planning techniques that account for all possible contingencies in the planning process. However, many agent environments permit an alternative approach, namely continual planning, i.e. the interleaving of planning with acting and sensing.

  This paper presents a new principled approach to continual planning that describes why and when an agent should switch between planning and acting. The resulting continual planning algorithm enables agents to deliberately postpone parts of their planning process and instead actively gather missing information that is relevant for the later refinement of the plan. To this end, the algorithm explictly reasons about the knowledge (or lack thereof) of an agent and its sensory capabilities. These concepts are modelled in the planning language MAPL. Since in many environments the major reason for dynamism is the behaviour of other agents, MAPL can also model multiagent environments, common knowledge among agents, and communicative actions between them. For Continual Planning, MAPL introduces the concept of of assertions, abstract actions that substitute yet unformed subplans.

  To evaluate our continual planning approach empirically we have developed MAPSIM, a simulation environment that automatically builds multiagent simulations from formal MAPL domains. Thus, agents can not only plan, but also execute their plans, perceive their environment, and interact with each other. Our experiments show that, using continual planning techniques, deliberate action planning can be used efficiently even in complex multiagent environments.

• Martin Wehrle und Malte Helmert.
  The Causal Graph Revisited for Directed Model Checking.
  In Jens Palsberg und Zhendong Su (Hrsg.), Proceedings of the 16th International Static Analysis Symposium (SAS 2009), S. 86-101. Springer-Verlag 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (Dagstuhl abstract; PDF)
  

  Directed model checking is a well-established technique to tackle the state explosion problem when the aim is to find error states in large systems. In this approach, the state space traversal is guided through a function that estimates the distance to nearest error states. States with lower estimates are preferably expanded during the search. Obviously, the challenge is to develop distance functions that are efficiently computable on the one hand and as informative as possible on the other hand. In this paper, we introduce the causal graph structure to the context of directed model checking. Based on causal graph analysis, we first adapt a distance estimation function from AI planning to directed model checking. Furthermore, we investigate an abstraction that is guaranteed to preserve error states. The experimental evaluation shows the practical potential of these techniques.

• Malte Helmert.
  Research Statement: Heuristic Search for Domain-Independent Planning.
  In 2nd International Symposium on Combinatorial Search (SoCS 2009). 2009.
  (PDF)
  

• Jörg Hoffmann, Piergiorgio Bertoli, Malte Helmert und Marco Pistore.
  Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection.
  Journal of Artificial Intelligence Research 35, S. 49-117. 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Thanks to recent advances, AI Planning has become the underlying technique for several applications. Figuring prominently among these is automated Web Service Composition (WSC) at the "capability" level, where services are described in terms of preconditions and effects over ontological concepts. A key issue in addressing WSC as planning is that ontologies are not only formal vocabularies; they also axiomatize the possible relationships between concepts. Such axioms correspond to what has been termed "integrity constraints" in the actions and change literature, and applying a web service is essentially a belief update operation. The reasoning required for belief update is known to be harder than reasoning in the ontology itself. The support for belief update is severely limited in current planning tools.

  Our first contribution consists in identifying an interesting special case of WSC which is both significant and more tractable. The special case, which we term forward effects, is characterized by the fact that every ramification of a web service application involves at least one new constant generated as output by the web service. We show that, in this setting, the reasoning required for belief update simplifies to standard reasoning in the ontology itself. This relates to, and extends, current notions of "message-based" WSC, where the need for belief update is removed by a strong (often implicit or informal) assumption of "locality" of the individual messages. We clarify the computational properties of the forward effects case, and point out a strong relation to standard notions of planning under uncertainty, suggesting that effective tools for the latter can be successfully adapted to address the former.

  Furthermore, we identify a significant sub-case, named strictly forward effects, where an actual compilation into planning under uncertainty exists. This enables us to exploit off-the-shelf planning tools to solve message-based WSC in a general form that involves powerful ontologies, and requires reasoning about partial matches between concepts. We provide empirical evidence that this approach may be quite effective, using Conformant-FF as the underlying planner.

• Geert-Jan Kruijff und Michael Brenner.
  Phrasing Questions.
  In AAAI Spring Symposium on Agents that Learn from Human Teachers. 2009.
  

• Malte Helmert.
  Concise finite-domain representations for PDDL planning tasks.
  Artificial Intelligence 173, S. 503-535. 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We introduce an efficient method for translating planning tasks specified in the standard PDDL formalism into a concise grounded representation that uses finite-domain state variables instead of the straight-forward propositional encoding.

  Translation is performed in four stages. Firstly, we transform the input task into an equivalent normal form expressed in a restricted fragment of PDDL. Secondly, we synthesize invariants of the planning task that identify groups of mutually exclusive propositions which can be represented by a single finite-domain variable. Thirdly, we perform an efficient relaxed reachability analysis using logic programming techniques to obtain a grounded representation of the input. Finally, we combine the results of the third and fourth stage to generate the final grounded finite-domain representation.

  The presented approach has originally been implemented as part of the Fast Downward planning system for the 4th International Planning Competition (IPC4). Since then, it has been used in a number of other contexts with considerable success, and the use of concise finite-domain representations has become a common feature of state-of-the-art planners.

• Michael Brenner.
  Continual Collaborative Planning for Mixed-Initiative Action and Interaction.
  In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008). 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Multiagent environments are often highly dynamic and only partially observable which makes deliberative action planning computationally hard. In many such environments, however, agents can take a more proactive approach and suspend planning for partial plan execution, especially for active information gathering and interaction with others. This paper presents a new algorithm for Continual Collaborative Planning (CCP) that enables agents to deliberately interleave planning, acting, perception and communication. Our implementation of CCP has been evaluated with MAPSIM, a tool that automatically generates multiagent simulations from formal multiagent planning (MAP) domains. For different such simulations, we show how CCP leads to collaborative planning and acting and, despite minimal linguistic capabilities, to fairly natural dialogues between agents.

• Michael Brenner und Ivana Kruijff-Korbayova.
  A Continual Multiagent Planning Approach to Situated Dialogue.
  In Proceedings of the 12th Workshop on the Semantics and Pragmatics of Dialogue (LonDial 2008). 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Situated dialogue is usually tightly integrated with behavior planning, physical action and perception. This paper presents an algorithmic framework, Continual Collaborative Planning (CCP), for modeling this kind of integrated behavior and shows how CCP agents naturally blend physical and communicative actions. For experiments with conversational CCP agents we have developed MAPSIM, a software environment that can generate multiagent simulations from formal multiagent planning problems automatically. MAPSIM permits comparison of CCP-based dialogue strategies on a wide range of domains and problems without domain-specific programming. Despite their linguistic capabilities being limited MAPSIM agents can already engage in fairly realistic situated dialogues. Our ongoing work is taking this approach from simulation to real human-robot interaction.

• Geert-Jan Kruijff, Michael Brenner und Nick Hawes.
  Continual Planning for Cross-Modal Situated Clarification in Human-Robot Interaction.
  In Proceedings of the 17th IEEE International Symposium on Robots and Human Interactive Communication (RO-MAN 2008). 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Current robots do not fully understand the world they are situated in, including what humans talk to them about. A fundamental problem in robotics is thus how a robot can clarify such a lack of understanding. This paper addresses the question of how a robot can create a plan for resolving a need for clarification. This paper characterizes situated clarification as an information need which may arise in any sensory-motoric modality interpreting the situated context of the robot, or any deliberative modality referring to that context. The paper then focuses on how, once a clarification need has been identified, the robot can create a plan in which one or more modalities are involved in resolving it. Modalities are involved on the basis of the types of information they can provide. These information types are identified in the ontologies the modalities use to interconnect their content with content of other modalities ("information fusion"). We take a continual approach to planning and execution monitoring. This provides the abiltity to re-plan depending on modality availability and success in resolving (part of) a clarification need. We illustrate our implementation of this approach with several examples from our system.

• Paul Plöger, Kai Pervölz, Christoph Mies, Patrick Eyerich, Michael Brenner und Bernhard Nebel.
  The DESIRE Service Robotics Initiative.
  Künstliche Intelligenz 08 (4), S. 29-32. 2008.
  (Abstract einblenden) (Abstract ausblenden)
  

  We present some advanced hardware units and an appropriate component based SW architecture for DESIRE. As an example we describe the integration of a enhanced AI task planner which allows for higher flexibility and dependability during complex task execution.

• 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), S. 518-527. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  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), S. 544-550. AAAI Press 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 (Hrsg.).
  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 (Hrsg.), 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), S. 140-147. AAAI Press 2008.
  (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.

• Jens Claßen, Viktor Engelmann, Gerhard Lakeymeyer und Gabriele Röger.
  Integrating Golog and Planning: An Empirical Evaluation.
  In Proceedings of the 12th International Workshop on Nonmonotonic Reasoning (NMR 2008), S. 10-18. 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The Golog family of action languages has proven to be a useful means for the high-level control of autonomous agents, such as mobile robots. In particular, the IndiGolog variant, where programs are executed in an online manner, is applicable in realistic scenarios where agents possess only incomplete knowledge about the state of the world, have to use sensors to gather necessary information at runtime and need to react to spontaneous, exogenous events that happen unpredictably due to a dynamic environment. Often, the specification of such an agent’s program also involves that certain subgoals have to be solved by means of planning. IndiGolog supports this in principle by providing a variety of lookahead mechanisms, but when it comes to pure, sequential planning, these usually cannot compete with modern state-of-the-art planning systems, most of which being based on the Planning Domain Definition Language PDDL. Previous theoretical results provide insights on the semantical compatibility between Golog and PDDL and how they compare in terms of expressiveness. In this paper, we complement these results with an empirical evaluation that shows that equipping IndiGolog with a PDDL planner (FF in our case) pays off in terms of the runtime performance of the overall system. For that matter, we study a number of example application domains and compare the needed computation times for varying problem sizes and difficulties.

• 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), S. 921-922. IOS Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF) (poster; PDF) (BIB)
  

  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), 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 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 938-943. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF) (BIB)
  

  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.

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

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

• Malte Helmert und Gabriele Röger.
  How Good is Almost Perfect?
  In Proceedings of the ICAPS-2007 Workshop on Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges. 2007.
  Superseded by the AAAI 2008 paper by the same name.
  (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.
  On the Accuracy of Admissible Heuristic Functions in Selected Planning Domains.
  In Proceedings of the ICAPS-2007 Workshop on Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges. 2007.
  Superseded by the AAAI 2008 paper by the same name.
  (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 assessing 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^k family of heuristics, and certain (additive) pattern database heuristics, compared to the optimal heuristic h^*. Whereas h⁺ and additive pattern database heuristics usually return cost estimates proportional to the true cost, non-additive h^k and non-additive pattern-database heuristics can yield results underestimating the true cost by arbitrarily large factors.

• Michael Brenner.
  Situation-Aware Interpretation, Planning and Execution of User Commands by Autonomous Robots.
  In Proceedings of the 16th IEEE International Symposium on Robots and Human Interactive Communication (ROMAN 2007). Jeju, Korea 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)
  

  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.

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

• Jens Claßen, Patrick Eyerich, Gerhard Lakemeyer und Bernhard Nebel.
  Towards an Integration of Golog and Planning.
  In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), S. 1846-1851. AAAI Press 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  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) (poster; PDF) (BIB)
  

  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.

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

  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 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)
  

  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.

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

  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.

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

  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.

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

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

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

• 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 (Hrsg.), 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.
  

• 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 (Hrsg.), 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)
  

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

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

  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)
  

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

  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 analysis to the actual transportation domains from the competitions. We next examine the remaining benchmarks, which do not exhibit a strong transportation feature, namely SCHEDULE and FREECELL.

  Relating the results of our analysis to empirical work on the behavior of the recently very successful FF planning system, we observe that our theoretical results coincide well with data obtained from empirical investigations.

• Ronen Brafman und Jörg Hoffmann.
  Conformant Planning via Heuristic Forward Search.
  In Proceedings of the Workshop on Planning under Uncertainty and Incomplete Information at ICAPS'03. Trento, Italy 2003.
  (PS.GZ)
  

• Stefan Edelkamp und Jörg Hoffmann.
  Quo Vadis, IPC-4? - Proposals for the Classical Part of the 4th International Planning Competition.
  In Proceedings of the Workshop on the Competition at ICAPS'03. Trento, Italy 2003.
  (PS.GZ)
  

• Jörg Hoffmann.
  The Metric-FF Planning System: Translating "Ignoring Delete Lists" to Numeric State Variables.
  Journal of Artificial Intelligence Research Special issue on the 3rd International Planning Competition. 2003.
  (PS.GZ)
  

• Jörg Hoffmann und Hector Geffner.
  Branching Matters: Alternative Branching in Graphplan.
  In Proceedings of the Thirteenth International Conference on Automated Planning and Scheduling. Trento, Italy 2003.
  (PS.GZ)
  

• Jussi Rintanen.
  Complexity of planning with partial observability.
  In Proceedings of the ICAPS'03 workshop on Planning under Uncertainty. 2003.
  (PDF)
  

• Jussi Rintanen.
  Symmetry reduction for SAT representations of transition systems.
  In Proceedings of the Thirteenth International Conference on Automated Planning and Scheduling (ICAPS 2003). AAAI Press 2003.
  (PDF)
  

• Jussi Rintanen.
  Expressive equivalence of formalisms for planning with sensing.
  In Proceedings of the Thirteenth International Conference on Automated Planning and Scheduling (ICAPS 2003). AAAI Press 2003.
  (PDF)
  

• Sylvie Thiebaux, Jörg Hoffmann und Bernhard Nebel.
  In Defense of PDDL Axioms.
  In Proceedings of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico 2003.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  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 they are a non-essential feature which is best compiled 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.

• Sylvie Thiebaux, Jörg Hoffmann und Bernhard Nebel.
  In Defense of PDDL Axioms.
  In Proceedings of the Workshop on the Competition at ICAPS'03. Trento, Italy 2003.
  (PS.GZ)
  

• Malte Helmert.
  Decidability and Undecidability Results for Planning with Numerical State Variables.
  In M. Ghallab, J. Hertzberg und P. Traverso (Hrsg.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002), S. 303-312. AAAI Press 2002.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  These days, propositional planning can be considered a quite well-understood problem. Good algorithms are known that will solve a wealth of very different and sometimes challenging planning tasks, and theoretical computational properties of both general STRIPS-style planning and the best-known benchmark problems have been established.

  However, propositional planning has a major drawback: The formalism is too weak to allow for the easy encoding of many genuinely interesting planning problems, specifically those involving numbers. A recent effort to enhance the PDDL planning language to cope with (among other additions) numerical state variables, to be used at the third international planning competition, has increased interest in these issues.

  In this contribution, we analyze "STRIPS with numbers" from a theoretical point of view. Specifically, we show that the introduction of numerical state variables makes the planning problem undecidable in the general case and many restrictions thereof and identify special cases for which we can provide decidability results.

• Jörg Hoffmann.
  Local Search Topology in Planning Benchmarks: A Theoretical Analysis.
  In M. Ghallab, J. Hertzberg und P. Traverso (Hrsg.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002). AAAI Press 2002.
  (PS.GZ) (PDF)
  

• Jörg Hoffmann.
  Extending FF to Numerical State Variables.
  In Proceedings of the 15th European Conference on Artificial Intelligence. Lyon, France 2002.
  (PS.GZ)
  

• Jussi Rintanen.
  Backward plan construction under partial observability.
  In M. Ghallab, J. Hertzberg und P. Traverso (Hrsg.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002). AAAI Press 2002.
  (PDF)
  

• Stefan Edelkamp und Malte Helmert.
  The Model Checking Integrated Planning System (MIPS).
  AI Magazine 22 (3), S. 67-71. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  MIPS was the first general planning system based on model checking methods. It can handle the STRIPS subset of the PDDL language and some additional features from ADL, namely negative preconditions and (universal) conditional effects. At the AIPS 2000 conference, MIPS was one of five planning systems to be awarded for "Distinguished Performance" in the fully automated track.

  This short paper gives a brief introduction to BDDs and explains the basic planning algorithm employed by MIPS, using a simple logistics problem as an example.

• Malte Helmert.
  On the Complexity of Planning in Transportation Domains.
  In A. Cesta und D. Borrajo (Hrsg.), Proceedings of the 6th European Conference on Planning (ECP 2001), S. 349-360. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The efficiency of AI planning systems is usually evaluated empirically. Some benchmark problems are of particular importance in this context, especially the ones used in the competitions of the 1998 and 2000 AIPS conferences. Many of these benchmarks share a common theme of transporting portables, making use of mobiles traversing a map of locations and roads.

  In this contribution, we embed these benchmarks into a well-structured hierarchy of transportation problems and study the computational complexity of optimal and non-optimal planning in this family of domains. We identify the key domain features that make transportation tasks hard and try to shed some light on the recent success of planning systems based on heuristic local search, as observed in the AIPS 2000 competition.

• Wolfgang Hatzack und Bernhard Nebel.
  Solving the Operational Traffic Control Problem.
  In A. Cesta und D. Borrajo (Hrsg.), Proceedings of the 6th European Conference on Planning (ECP 2001). 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  The operational traffic control problem comes up in a number of different contexts. It involves the coordinated movement of a set of vehicles and has by and large the flavor of a scheduling problem. In trying to apply scheduling techniques to the problem, one notes that this is a job-shop scheduling problem with blocking, a type of scheduling problem that is quite unusual. In particular, we will highlight a condition necessary to guarantee that job-shop schedules can be executed in the presences of the blocking constraint. Based on the insight that the traffic problem is a scheduling problem, we can derive the computational complexity of the operational traffic control problem and can design some algorithms to deal with this problem. In particular, we will specify a very simple method that works well in fast-time simulation contexts.

• Jörg Hoffmann und Bernhard Nebel.
  RIFO revisited: Detecting Relaxed Irrelevance.
  In A. Cesta und D. Borrajo (Hrsg.), Proceedings of the 6th European Conference on Planning (ECP 2001). 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  RIFO, as has been proposed by Nebel et al., is a method that can automatically detect irrelevant information in planning tasks. The idea is to remove such irrelevant information as a pre­process to planning. While RIFO has been shown to be useful in a number of domains, its main disadvantage is that it is not completeness preserving. Furthermore, the pre­process often takes more running time than nowadays state­of­the­art planners, like FF, need for solving the entire planning task. We introduce the notion of relaxed irrelevance, concerning actions which are never needed within the relaxation that heuristic planners like FF and HSP use for computing their heuristic values. The idea is to speed up the heuris­ tic functions by reducing the action sets considered within the relaxation. Starting from a sufficient condition for relaxed irrelevance, we introduce two preprocessing methods for filtering action sets. The first preprocessing method is proven to be completeness­preserving, and is empirically shown to terminate fast on most of our testing examples. The second method is fast on all our testing examples, and is empirically safe. Both methods have drastic pruning impacts in some domains, speeding up FF's heuristic function, and in effect the planning process.

• Julie Porteous, Laura Sebastia und Jörg Hoffmann.
  On the Extraction, Ordering, and Usage of Landmarks in Planning.
  In A. Cesta und D. Borrajo (Hrsg.), Proceedings of the 6th European Conference on Planning (ECP 2001). 2001.
  (PS.GZ) (PDF)
  

• Michael Brenner.
  A Formal Model for Planning with Time and Resources in Concurrent Domains.
  In Workshop on Planning with Resources (IJCAI 2001). Seattle, Washington, USA 2001.
  (PS.GZ)
  

• Jörg Hoffmann.
  FF: The Fast-Forward Planning System.
  AI Magazine 22 (3), S. 57-62. 2001.
  (PS.GZ) (PDF)
  

• Jörg Hoffmann und Bernhard Nebel.
  The FF Planning System: Fast Plan Generation Through Heuristic Search.
  Journal of Artificial Intelligence Research 14, S. 253-302. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP's heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.

• Jörg Hoffmann.
  Local Search Topology in Planning Benchmarks: An Empirical Analysis.
  In Proceedings of the 17th International Joint Conference on Artificial Intelligence. Seattle, Washington, USA 2001.
  (PS.GZ) (PDF)
  

• Jörg Hoffmann und Bernhard Nebel.
  What makes the difference between HSP and FF?
  In IJCAI Workshop on Empirical AI. Seattle 2001.
  (PS.GZ) (PDF)
  

• Jörg Hoffmann und Bernhard Nebel.
  Towards Thorough Empirical Methods for AI Planning.
  In IJCAI Workshop on Empirical AI. Seattle 2001.
  (PS.GZ) (PDF)
  

• Jussi Rintanen.
  Complexity of probabilistic planning under average rewards.
  In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001). Morgan Kaufmann, San Francisco, California 2001.
  (PS.GZ) (PDF)
  

• Jussi Rintanen und Jörg Hoffmann.
  An overview of recent algorithms for AI planning.
  Künstliche Intelligenz Heft 2/01, S. 5-11. 2001.
  (PS.GZ) (PDF)
  

• Jörg Hoffmann.
  A Heuristic for Domain Independent Planning and its Use in an Enforced Hill-climbing Algorithm.
  In Proceedings of the 14th Workshop on New Results in Planning, Scheduling and Design (PuK 2000) at ECAI 2000, S. 62-67. Berlin, Germany 2000.
  (PS.GZ)
  

• Jana Koehler und Jörg Hoffmann.
  On the Instantation of ADL Operators Involving Arbitrary First-Order Formulas.
  In Proceedings of the 14th Workshop on New Results in Planning, Scheduling and Design (PuK 2000) at ECAI 2000, S. 74-82. Berlin, Germany 2000.
  (PS.GZ)
  

• Jörg Hoffmann.
  A Heuristic for Domain Independent Planning and its Use in an Enforced Hill-climbing Algorithm.
  In Proceedings of the 12th International Symposium on Methodologies for Intelligent Systems. Charlotte, North Carolina, USA 2000.
  (PS.GZ)
  

• Jana Koehler und Jörg Hoffmann.
  On Reasonable and Forced Goal Orderings and their Use in an Agenda-Driven Planning Algorithm.
  Journal of Artificial Intelligence Research 12, S. 338-386. 2000.
  (PS.GZ)
  

• Bernhard Nebel.
  On the Compilability and Expressive Power of Propositional Planning Formalisms.
  Journal of Artificial Intelligence Research 12, S. 271-315. 2000.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  The recent approaches of extending the GRAPHPLAN algorithm to handle more expressive planning formalisms raise the question of what the formal meaning of ``expressive power'' is. We formalize the intuition that expressive power is a measure of how concisely planning domains and plans can be expressed in a particular formalism by introducing the notion of ``compilation schemes'' between planning formalisms. Using this notion, we analyze the expressiveness of a large family of propositional planning formalisms, ranging from basic STRIPS to a formalism with conditional effects, partial state specifications, and propositional formulae in the preconditions. One of the results is that conditional effects cannot be compiled away if plan size should grow only linearly but can be compiled away if we allow for polynomial growth of the resulting plans. This result confirms that the recently proposed extensions to the GRAPHPLAN algorithm concerning conditional effects are optimal with respect to the ``compilability'' framework. Another result is that general propositional formulae cannot be compiled into conditional effects if the plan size should be preserved linearly. This implies that allowing general propositional formulae in preconditions and effect conditions adds another level of difficulty in generating a plan.

• Bernhard Nebel.
  On the Expressive Power of Planning Formalisms: Conditional Effects and Boolean Preconditions in the STRIPS Formalism.
  In J. Minker (Hrsg.), Logic-Based Artificial Intelligence, S. 469-490. Kluwer, Dordrecht 2000.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  The notion of ``expressive power'' is often used in the literature on planning. However, it is usually only used in an informal way. In this paper, we will formalize this notion using the ``compilability framework'' and analyze the expressive power of some variants of STRIPS allowing for conditional effects and arbitrary Boolean formulae in preconditions. One interesting consequence of this analysis is that we are able to confirm a conjecture by Bäckström that preconditions in conjunctive normal form add to the expressive power of propositional STRIPS. Further, we will show that STRIPS with conditional effects is incomparable to STRIPS with Boolean formulae as preconditions. Finally, we show that preconditions in conjunctive normal form do not add any expressive power once we have conditional effects.

• Jussi Rintanen.
  An Iterative Algorithm for Synthesizing Invariants.
  In Proceedings of the 17th National Conference on Artificial Intelligence / 12th Innovative Applications of AI Conference. AAAI Press 2000.
  (PS.GZ) (PDF)
  

• Jussi Rintanen.
  Incorporation of Temporal Logic Control into Plan Operators.
  In W. Horn (Hrsg.), ECAI 2000. Proceedings of the 14th European Conference on Artificial Intelligence. IOS Press, Amsterdam 2000.
  (PS.GZ) (PDF)
  

• Jana Koehler und Jörg Hoffmann.
  Planning with Goal Agendas.
  In Proceedings des 13. Workshops Planen und Konfigurieren (PuK 1999) auf der 10. Tagung Expertensysteme (XPS-99). Würzburg, Germany 1999.
  (PS.GZ)
  

• Jörg Hoffmann und Jana Koehler.
  A new Method to Query and Index Sets.
  In Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI 1999). Stockholm, Sweden 1999.
  (PS.GZ) (extended technical report; PS.GZ)
  

• Bernhard Nebel.
  Compilation Schemes: A Theoretical Tool for Assessing the Expressive Power of Planning Formalisms.
  In KI-99: Advances in Artificial Intelligence. Springer-Verlag, Bonn 1999.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (extended technical report; PS.GZ)
  

  The recent approaches of extending the GRAPHPLAN algorithm to handle more expressive planning formalisms raise the question of what the formal meaning of ``expressive power'' is. We formalize the intuition that expressive power is a measure of how concisely planning domains and plans can be expressed in a particular formalism by introducing the notion of ``compilation schemes'' between planning formalisms. Using this notion, we analyze the expressive power of a large family of propositional planning formalisms and show, e.g., that Gazen and Knoblock's approach to compiling conditional effects away is optimal.

• Bernhard Nebel.
  What is the Expressive Power of Disjunctive Preconditions?
  In Proceedings of the 5th European Conference on Planning (ECP 1999). 1999.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  While there seems to be a general consensus about the expressive power of a number of language features in planning formalisms, one can find many different statements about the expressive power of disjunctive preconditions. Using the ``compilability framework,'' we show that preconditions in conjunctive normal form add to the expressive power of propositional STRIPS, which confirms a conjecture by Bäckström. Further, we show that preconditions in conjunctive normal form do not add any expressive power once we have conditional effects.

• Bernhard Nebel.
  Die Ausdrucksstärke von Planungsformalismen: Eine formale Charakterisierung.
  Künstliche Intelligenz Heft 3/99, S. 12-19. 1999.
  (Abstract einblenden) (Abstract ausblenden) (preliminary version; PS.GZ)
  

  Die Ausdrucksstärke von Planungsformalismen wird in vielen Arbeiten im Gebiet der Handlungsplanung thematisiert, ohne daß der Begriff jedoch formal fundiert wird. Insbesondere im Kontext des von Blum und Furst entwickeltem Graphplan-Algorithmus gewinnt dieses Thema Relevanz, da viele Forschungsarbeiten sich mit dem Problem auseinandersetzen, ob und wie der Graphplan-Algorithmus erweitert werden kann, um ausdrucksstarke Formalismen zu behandeln. In diesem Papier wird eine Methode zur Messung der relativen Ausdrucksstä;rke von Planungsformalismen vorgestellt, das auf Ideen aus dem Gebiet der Wissenskompilation beruht. Die Intuition ist dabei, daß ein Formalismus so mächtig wie ein zweiter Formalismus ist, falls sich alle Domänenbeschreibungen des zweiten Formalismus "einfach" innerhalb des ersten Formalismus ausdrücken lassen und die resultierenden Pl"ane nicht zu stark aufgebläht werden. Diese intuitive Charakterisierung der relativen Ausdrucksstärke wird mit Hilfe von sogenannten "Kompilationsschemata" formalisiert, und darauf aufbauend werden propositionale Planungsformalismen entsprechend ihrer Ausdrucksstärke klassifiziert.

• Jana Koehler.
  Solving Complex Planning Tasks Through Extraction of Subproblems.
  In Proceedings of the 4th International Conference on Artificial Intelligence Planning Systems (AIPS-98). 1998.
  (PS.GZ)
  

• Jana Koehler.
  Planning under Resource Constraints.
  In Proceedings of the 13th European Conference on Artificial Intelligence (ECAI'98). 1998.
  (PS.GZ)
  

• Yannis Dimopoulos, Bernhard Nebel und Jana Koehler.
  Encoding planning problems in non-monotonic logic programs.
  In Proc. European Conference on Planning 1997 (ECP-97), S. 169-181. Springer-Verlag 1997.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  In this paper we study a framework for encoding planning problems in logic programs with negation as failure. In contrast to other research work that focuses on the representional adequacy of nonmontonic logic programming as a language for describing theories of action and change, here we are concerned with more practical issues. Namely, we examine the effectiveness of an existing implementation of the stable models semantics called "Smodels" in solving a series of hard planning problems. We discuss representational issues and point out factors that can influence the performance of the method. It turns out that for careful and compact encodings, the performance of the method in a number of different domains, is comparable to that of planners like GRAPHPLAN and SATPLAN.

• Jana Koehler, Bernhard Nebel, Jörg Hoffmann und Yannis Dimopoulos.
  Extending Planning Graphs to an ADL Subset.
  In Proc. European Conference on Planning 1997 (ECP-97), S. 273-285. Springer-Verlag 1997.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  We describe an extension of GRAPHPLAN to a subset of ADL that allows conditional and universally quantified effects in operators in such a way that almost all interesting properties of the original Graphplan algorithm are preserved.

• Bernhard Nebel, Yannis Dimopoulos und Jana Koehler.
  Ignoring Irrelevant Facts and Operators in Plan Generation.
  In Proc. European Conference on Planning 1997 (ECP-97), S. 338-350. Springer-Verlag 1997.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  It is traditional wisdom that one should start from the goals when generating a plan in order to focus the plan generation process on potentially relevant actions. The GRAPHPLAN system, however, which is the most efficient planning system nowadays, builds a ``planning graph'' in a forward-chaining manner. Although this strategy seems to work well, it may possibly lead to problems if the planning task description contains irrelevant information. Although some irrelevant information can be filtered out by GRAPHPLAN, most cases of irrelevance are not noticed.

  In this paper, we analyze the effects arising from ``irrelevant'' information to planning task descriptions for different types of planners. Based on that, we propose a family of heuristics that select relevant information by minimizing the number of initial facts that are used when approximating a plan by backchaining from the goals ignoring any conflicts. These heuristics, although not solution-preserving, turn out to be very useful for guiding the planning process, as shown by applying the heuristics to a large number of examples from the literature.

Wissensrepräsentation

• Stefan Wölfl (Hrsg.).
  Poster and Demo Track of the 35th German Conference on Artificial Intelligence (KI-2012), September 24-27, 2012, Saarbrücken, Germany.
  2012.
  (PDF)
  

• Matthias Westphal und Julien Hué.
  Nogoods in Qualitative Constraint-based Reasoning.
  In KI 2012: Advances in Artificial Intelligence (KI 2012), S. 180-192. Springer-Verlag 2012.
  (Authors' preprint. The final publication is available at www.springerlink.com.).
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The prevalent method of increasing reasoning efficiency in the domain of qualitative constraint-based spatial and temporal reasoning is to use domain splitting based on so-called tractable subclasses. In this paper we analyze the application of nogood learning with restarts in combination with domain splitting. Previous results on nogood recording in the constraint satisfaction field feature learnt nogoods as a global constraint that allows for enforcing generalized arc consistency. We present an extension of such a technique capable of handling domain splitting, evaluate its benefits for qualitative constraint-based reasoning, and compare it with alternative approaches.

• Anthony G. Cohn, Jochen Renz und Stefan Wölfl (Hrsg.).
  Proceedings of the IJCAI-2011 Workshop on Benchmarks and Applications of Spatial Reasoning, Barcelona, Spain, July 17, 2011.
  2011.
  (PDF)
  

• Matthias Westphal und Jochen Renz.
  Evaluating and Minimizing Ambiguities in Qualitative Route Instructions.
  In ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM-GIS 2011). ACM 2011.
  

• Manuel Bodirsky und Stefan Wölfl.
  RCC8 is Polynomial on Networks of Bounded Treewidth.
  In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), S. 756-761. AAAI Press 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  We construct an homogeneous (and ω-categorical) representation of the relation algebra RCC8, which is one of the fundamental formalisms for spatial reasoning. As a consequence we obtain that the network consistency problem for RCC8 can be solved in polynomial time for networks of bounded treewidth.

• Matthias Westphal, Stefan Wölfl, Bernhard Nebel und Jochen Renz.
  On Qualitative Route Descriptions: Representation and Computational Complexity.
  In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), S. 1120-1125. AAAI Press 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route networks with the qualitative information necessary to evaluate and optimize route descriptions with regard to ambiguities in them. We identify different agent models that differ in how agents are assumed to process route descriptions while navigating through route networks. Further, we analyze the computational complexity of matching route descriptions and paths in route networks in dependency of the agent model. Finally we empirically evaluate the influence of the agent model on the optimization and the processing of route instructions.

• Antje Krumnack, Leandra Bucher, Jelica Nejasmic, Bernhard Nebel und Markus Knauff.
  A model for relational reasoning as verbal reasoning.
  Cognitive Systems Research 12 (3-4), S. 377-392. 2011.
  

• Bernhard Nebel und Christian Freksa.
  AI Approaches to Cognitive Systems – The Example of Spatial Cognition.
  Informatik-Spektrum 34 (5), S. 462-468. 2011.
  

• Mehul Bhatt, Hans Guesgen, Stefan Wölfl und Shyamanta Hazarika.
  Qualitative Spatial and Temporal Reasoning: Emerging Applications, Trends, and Directions.
  Spatial Cognition & Computation: An Interdisciplinary Journal 11 (1), S. 1-14. 2011.
  (DOI)
  

• Matthias Westphal, Christian Dornhege, Stefan Wölfl, Marc Gissler und Bernhard Nebel.
  Guiding the Generation of Manipulation Plans by Qualitative Spatial Reasoning.
  Spatial Cognition & Computation: An Interdisciplinary Journal 11 (1), S. 75-102. 2011.
  (Abstract einblenden) (Abstract ausblenden) (DOI) (BIB)
  

  Manipulation planning is a complex task for robots with a manipulator arm that need to grasp objects in the environment, specifically under narrow spatial conditions restricting the workspace of the robot. A popular approach for generating motion plans is probabilistic roadmap planning. However, the sampling strategy of such planners is usually unguided, and hence may lead to motion plans that seem counterintuitive for a human observer. In this article we present an approach that generates heuristics for the probabilistic sampling strategy from spatial plans that abstract from concrete metric data. These spatial plans describe a free trajectory in the workspace of the robot on a purely qualitative level, i.e., by employing spatial relations from formalisms considered in the domain of Qualitative Spatial and Tem- poral Reasoning. We discuss how such formalisms and constraint-based reasoning methods can be applied to approximate geometrically feasible motions. The paper is completed by an evaluation of a hybrid planning system in different spatial settings showing that run-times are notably improved when an abstract plan is considered as a guidance heuristic.

• Jochen Renz und Stefan Wölfl.
  A Qualitative Representation of Route Networks.
  In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), S. 1091-1092. IOS Press 2010.
  (DBLP)
  

• Matthias Westphal, Stefan Wölfl und Jason Jingshi Li.
  Restarts and Nogood Recording in Qualitative Constraint-based Reasoning.
  In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), S. 1093-1094. IOS Press 2010.
  Also, see the follow up paper at KI 2012: Nogoods in Qualitative Constaint-based Reasoning.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  This paper introduces restart and nogood recording techniques in the domain of qualitative spatial and temporal reasoning. Nogoods and restarts can be applied orthogonally to usual methods for solving qualitative constraint satisfaction problems. In particular, we propose a more general definition of nogoods that allows for exploiting information about nogoods and tractable subclasses during backtracking search. First evaluations of the proposed techniques show promising results.

• Florian Pommerening, Stefan Wölfl und Matthias Westphal.
  Right-of-Way Rules as Use Case for Integrating GOLOG and Qualitative Reasoning.
  In Bärbel Mertsching, Marcus Hund und Muhammad Zaheer Aziz (Hrsg.), Proceedings of the 32nd Annual Conference on Artificial Intelligence (KI 2009), S. 468-475. Springer-Verlag 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  Agents interacting in a dynamically changing spatial environment often need to access the same spatial resources. A typical example is given by moving vehicles that meet at an intersection in a street network. In such situations right-of-way rules regulate the actions the vehicles involved may perform. For this application scenario we show how the Golog framework for reasoning about action and change can be enhanced by external reasoning services that implement techniques known from the domain of Qualitative Spatial Reasoning.

• Bernhard Nebel und Jochen Renz.
  A fixed-parameter tractable algorithm for spatio-temporal calendar management.
  In Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI 2009), S. 879--884. AAAI Press 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Calendar management tools assist users with coordinating their daily life. Different tasks have to be scheduled according to the user preferences. In many cases, tasks are at different locations and travel times have to be considered. Therefore, these kinds of calendar management problems can be regarded as spatio-temporal optimisation problems and are often variants of traveling salesman problems (TSP) or vehicle routing problems. While standard TSPs require a solution to include all tasks, prize-collecting TSPs are more suited for calendar management problems as they require a solution that optimises the total sum of ``prizes'' we assigned to tasks at different locations. If we now add time windows that limit when tasks can occur, these prize-collecting TSPs with time windows (TW-TSP) are excellent abstractions of spatio-temporal optimisation problems such as calendar management. Due to the inherent complexity of TW-TSPs, the existing literature considers mainly approximation algorithms or special cases. We present a novel algorithm for TW-TSPs that enables us to find the optimal solution to TW-TSP problems occurring in real-world calendar management applications efficiently. Our algorithm is a fixed-parameter tractable algorithm that depends on the maximal number of tasks that can be re-visited from some other task, a parameter which is small in the application scenario we consider.

• Matthias Westphal und Stefan Wölfl.
  Qualitative CSP, finite CSP, and SAT: Comparing methods for qualitative constraint-based reasoning.
  In Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI 2009). 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  Qualitative Spatial and Temporal Reasoning (QSR) is concerned with constraint-based formalisms for representing, and reasoning with, spatial and temporal information over infinite domains. Within the community it has been a widely accepted assumption that genuine qualitative reasoning methods outperform other reasoning methods that are applicable to encodings of qualitative CSP instances. Recently this assumption has been tackled by several authors, who proposed to encode qualitative CSP instances as finite CSP or SAT instances. In this paper we report on the results of a broad empirical study in which we compared the performance of several reasoners on instances from different qualitative formalisms. Our results show that for small-sized qualitative calculi (e.g. Allen's interval algebra and RCC-8) a state-of-the-art implementation of QSR methods currently gives the most efficient performance. However, on recently suggested large-size calculi, e.g. OPRA_4, finite CSP encodings provide a considerable performance gain. These results confirm a conjecture by Bessière stating that support-based constraint propagation algorithms provide better performance for large-sized qualitative calculi.

• Stefan Wölfl und Matthias Westphal.
  On combinations of binary qualitative constraint calculi.
  In Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI 2009). 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  Qualitative constraint calculi are representation formalisms that allow for efficient reasoning about spatial and temporal information. Many of the calculi discussed in the field of Qualitative Spatial and Temporal Reasoning can be defined as combinations of other, simpler and more compact formalisms. On the other hand, existing calculi can be combined to a new formalism in which one can represent, and reason about, different aspects of a domain at the same time. For example, Gerevini and Renz presented a loose combination of the region connection calculus RCC-8 and the point algebra: the resulting formalism integrates topological and qualitative size relations between spatially extended objects. In this paper we compare the approach by Gerevini and Renz to a method that generates a new qualitative calculus by exploiting the semantic interdependencies between the component calculi. We will compare these two methods and analyze some formal relationships between a combined calculus and its components. The paper is completed by an empirical case study in which the reasoning performance of the suggested methods is compared on random test instances.

• Bernhard Nebel und Stefan Wölfl.
  Benchmarking of Qualitative Spatial and Temporal Reasoning Systems.
  2009.
  AAAI Technical Report SS-09-02.
  (AAAI)
  

• 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), S. 518-527. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  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), S. 544-550. AAAI Press 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.

• Jens Claßen, Viktor Engelmann, Gerhard Lakeymeyer und Gabriele Röger.
  Integrating Golog and Planning: An Empirical Evaluation.
  In Proceedings of the 12th International Workshop on Nonmonotonic Reasoning (NMR 2008), S. 10-18. 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The Golog family of action languages has proven to be a useful means for the high-level control of autonomous agents, such as mobile robots. In particular, the IndiGolog variant, where programs are executed in an online manner, is applicable in realistic scenarios where agents possess only incomplete knowledge about the state of the world, have to use sensors to gather necessary information at runtime and need to react to spontaneous, exogenous events that happen unpredictably due to a dynamic environment. Often, the specification of such an agent’s program also involves that certain subgoals have to be solved by means of planning. IndiGolog supports this in principle by providing a variety of lookahead mechanisms, but when it comes to pure, sequential planning, these usually cannot compete with modern state-of-the-art planning systems, most of which being based on the Planning Domain Definition Language PDDL. Previous theoretical results provide insights on the semantical compatibility between Golog and PDDL and how they compare in terms of expressiveness. In this paper, we complement these results with an empirical evaluation that shows that equipping IndiGolog with a PDDL planner (FF in our case) pays off in terms of the runtime performance of the overall system. For that matter, we study a number of example application domains and compare the needed computation times for varying problem sizes and difficulties.

• Christian Freksa, Nora Newcombe, Peter Gärdenfors und Stefan Wölfl (Hrsg.).
  Spatial Cognition VI: Learning, Reasoning, and Talking about Space, International Conference Spatial Cognition 2008 (SC '08), Freiburg, Germany, September 15-19, 2008.
  Band 5248 von Lecture Notes in Artificial Intelligence.
  Springer 2008.
  (Springer) (DBLP)
  

• Diedrich Wolter, Frank Dylla, Stefan Wölfl, Jan Oliver Wallgrün, Lutz Frommberger, Bernhard Nebel und Christian Freksa.
  SailAway: Spatial Cognition in Sea Navigation.
  Künstliche Intelligenz 08 (1), S. 28-30. 2008.
  (DBLP)
  

• Frank Dylla, Diedrich Wolter, Lutz Frommberger, Christian Freksa, Stefan Wölfl und Bernhard Nebel.
  Qualitative Methoden zur Steuerung von Agenten - SailAway: Raumkognition zur Steuerung von Schiffen.
  Industrie Management 4. 2008.
  (BIB)
  

• Marco Ragni und Stefan Wölfl.
  Reasoning about topological and positional information in dynamic settings.
  In Proceedings of the Twenty-First International FLAIRS Conference (2008), S. 606-611. 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  Typical application fields of spatial and spatio-temporal representation formalisms and reasoning techniques include geographic information systems (GIS), mobile assistance systems for route finding, layout descriptions, and navigation tasks of robots interacting with humans. Often these formalisms focus on specific spatial aspects in that they use either topological or positional relations. In this paper we propose a formalism which allows for representing topological and positional relations between disks in the plane. Although this formalism employs a rather abstract representation of objects as disks, it provides an interesting test-bed for investigating typical problems that arise when topological and positional information about objects are combined, or when such combined formalisms are used to represent continuous changes in the considered application scenario.

• Jochen Renz und Bernhard Nebel.
  Qualitative Spatial Reasoning using Constraint Calculi.
  In M. Aiello, I. Pratt-Hartmann und J. van Benthem (Hrsg.), 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.
  

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

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

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

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

• 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.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  In the domain of qualitative constraint reasoning, a subfield of AI which has evolved in the past 25 years, a large number of calculi for efficient reasoning about spatial and temporal entities has been developed. Reasoning techniques developed for these constraint calculi typically rely on so-called composition tables of the calculus at hand, which allow for replacing semantic reasoning by symbolic operations. Often these composition tables are developed in a quite informal, pictorial manner--a method which seems to be error-prone. In view of possible safety critical applications of qualitative calculi, however, it is desirable to formally verify these composition tables. In general, the verification of composition tables is a tedious task, in particular in cases where the semantics of the calculus depends on higher-order constructs such as sets. In this paper we address this problem by presenting a heterogeneous proof method that allows for combining a higher-order proof assistance system (such as Isabelle) with an automatic (first order) reasoner (such as SPASS or VAMPIRE). The benefit of this method is that the number of proof obligations that is to be proven interactively with a semi-automatic reasoner can be minimized to an acceptable level.

• Diedrich Wolter, Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Bernhard Nebel und Stefan Wölfl.
  Qualitative Spatial Reasoning for Rule Compliant Agent Navigation.
  In Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2007), S. 673-674. AAAI Press 2007.
  (DBLP)
  

• 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.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Agents that have to solve navigational tasks need to consider aspects that go far beyond single-agent goal-directed deliberation: What an agent does in a specific situation often interferes with what other agents do at the same time. In order to avoid conflicts or even collisions, situations in space are governed by laws, rules, and agreements between the involved agents. For this reason, artificial agents interacting with humans must be able to process such rule sets, which are usually formulated in natural language. In this paper we present a case study on how to formalize navigation rules in the domain of sea navigation. We present an approach that uses qualitative representations of navigation rules. Qualitative spatial reasoning methods can be applied to distinguish permissible actions in the set of all possible actions. We argue that an agent’s spatial representation can be modeled on a qualitative level in a natural way and that this also empowers sophisticated high-level agent control.

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

• Marco Ragni und Felix Steffenhagen.
  A cognitive computational model for spatial reasoning.
  In AAAI Spring Symposium 2007. AAAI Press 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.

• Jens Claßen, Patrick Eyerich, Gerhard Lakemeyer und Bernhard Nebel.
  Towards an Integration of Golog and Planning.
  In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), S. 1846-1851. AAAI Press 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  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.

• Stefan Wölfl und Till Mossakowski.
  Qualitative Constraint Calculi - Application and Integration, Workshop at KI 2006, Bremen, Germany, June 14, 2006, Workshop Proceedings.
  2006.
  (PDF)
  

• 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 Proceedings of the International Symposium on Practical Cognitive Agents and Robots (PCAR 2006), S. 93-104. University of Western Australia Press 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  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.

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

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

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

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

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

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

• 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.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  In AI a large number of calculi for efficient reasoning about spatial and temporal entities have been developed. The most prominent temporal calculi are the point algebra of linear time and Allen's interval calculus. Examples of spatial calculi include mereotopological calculi, Frank's cardinal direction calculus, Freksa's double cross calculus, Egenhofer and Franzosa's intersection calculi, and Randell, Cui, and Cohn's region connection calculi. These calculi are designed for modeling specific aspects of space or time, respectively, to the effect that the class of intended models may vary widely with the calculus at hand. But from a formal point of view these calculi are often closely related to each other. For example, the spatial region connection calculus RCC5 may be considered a coarsening of Allen's (temporal) interval calculus. And vice versa, intervals can be used to represent spatial objects that feature an internal direction. The central question of this paper is how these calculi as well as their mutual dependencies can be axiomatized by algebraic specifications. This question will be investigated within the framework of the Common Algebraic Specification Language (CASL), a specification language developed by the Common Framework Initiative for algebraic specification and development (COFI). We explain scope and expressiveness of CASL by discussing the specifications of some of the calculi mentioned before.

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

  The concept of event is one of the key notions of many theories dealing with causality or agency. In this paper we study different approaches to events that share the basic assumption that events can be analyzed fruitfully in branching-time structures. The terminological framework developed thereby may be helpful for further analyses in the fields of causality and agency and also in those fields of computational semantics, where similar concepts are considered.

• 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.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  Allen’s interval calculus is one of the most prominent formalisms in the domain of qualitative spatial and temporal reasoning. Applications of this calculus, however, are restricted to domains that deal with linear flows of time. But how the fundamental ideas of Allen’s calculus can be extended to other, weaker structures than linear orders has gained only little attention in the literature. In this paper we will investigate intervals in branching flows of time, which are of special interest for temporal reasoning, since they allow for representing indeterministic aspects of systems, scenarios, planning tasks, etc. As well, branching time models, i. e., treelike non-linear structures, do have interesting applications in the field of spatial reasoning, for example, for modeling traffic networks. In a first step we discuss interval relations for branching time, thereby comprising various sources from the literature. Then, in a second step, we present some new complexity results concerning constraint satisfaction problems of interval relations in branching time.

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

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

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

• 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 (Hrsg.), Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004). Springer-Verlag 2004.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (DBLP)
  

  Qualitative action theory deals with purely qualitative descriptions and formal representations of agency, i.e., agents and their possibilities for intervening in the causal flow of events. This means that, contrary to game theory, qualitative action theory abstains from any metric evaluation of the outcomes of actions. In this paper we present and compare two qualitative approaches to action theory that have been discussed in the literature. The first one coming from philosophical action theory is the Kutschera-Belnap approach, which is the semantic basis of so-called Stit-logics. The second approach is the semantics of Alur, Henzinger, and Kupferman's Alternating-time Temporal Logic (ATL). In computer science, ATL has been introduced as an extension of Computational Tree Logic (CTL) to allow for modeling systems that interact with their environment. Surprisingly, although both approaches are very close in spirit, a systematic analysis of the mutual dependencies between these approaches does not exist. The paper aims at bringing together these two research streams, which seem to have been developed independently in philosophy and computer science. In particular, we will investigate the assumptions with which both approaches may be considered equivalent. Finally, further research on this topic promises interesting results that translate between the approaches presented here.

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

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

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

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

• Christian Köhler.
  The Occlusion Calculus.
  In Proceedings Workshop on Cognitive Vision. Zürich, Switzerland 2002.
  (PS.GZ) (PDF)
  

• Bernhard Nebel.
  The Philosophical Soccer Player.
  In Proceedings of the Eights International Conference on Principles and Knowledge Representation and Reasoning (KR-02), S. 631. 2002.
  

• Yannis Dimopoulos, Bernhard Nebel und Francesca Toni.
  On the Computational Complexity of Assumption-based Argumentation for Default Reasoning.
  Artificial Intelligence 141 (1-2), S. 57-78. 2002.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Bondarenko et al. have recently proposed an abstract framework for default reasoning. Besides capturing most existing formalisms and proving that their standard semantics all coincide, the framework extends these formalisms by generalising the semantics of admissible and preferred arguments, originally proposed for logic programming only. In this paper we analyse the computational complexity of credulous and sceptical reasoning under the semantics of admissible and preferred arguments for (the propositional variant of) the instances of the abstract framework capturing theorist, circumscription, logic programming, default logic, and autoepistemic logic. Although the new semantics have been tacitly assumed to mitigate the computational hardness of default reasoning under the standard semantics of stable extensions, we show that in many cases reasoning under the admissibility and preferability semantics is computationally harder than under the standard semantics. In particular, in the case of autoepistemic logic, sceptical reasoning under preferred arguments is located at the fourth level of the polynomial hierarchy, whereas the same form of reasoning under stable extensions is located at the second level.

• Alfonso Gerevini und Bernhard Nebel.
  Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen's Interval Calculus: Computational Complexity.
  In Proceedings of the 15th European Conference on Artificial Intelligence (ECAI'02). 2002.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  There exist a number of qualitative constraint calculi that are used to represent and reason about temporal or spatial configurations. However, there are only very few approaches aiming to create a spatio-temporal constraint calculus. Similar to Bennett et al., we start with the spatial calculus RCC-8 and Allen's interval calculus in order to construct a qualitative spatio-temporal calculus. As we will show, the basic calculus is NP-complete, even if we only permit base relations. When adding the restriction that the size of the spatial regions persists over time, or that changes are continuous, the calculus becomes more useful, but the satisfiability problem appears to be much harder. Nevertheless, we are able to show that satisfiability is still in NP.

• Bernhard Nebel und Alexander Scivos.
  Formal Properties of Constraint Calculi for Qualitative Spatial Reasoning.
  Künstliche Intelligenz Heft 4/02, S. 14-18. 2002.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  In the previous two decades, a number of qualitative constraint calculi have been developed, which are used to represent and reason about spatial configurations. A common property of almost all of these calculi is that reasoning in them can be understood as solving a binary constraint satisfaction problem over infinite domains. The main algorithmic method that is used is constraint propagation in the form of the path-consistency method. This approach can be applied to a wide range of different aspects of spatial reasoning. We describe how to make use of this representation and reasoning technique and point out the possible problems one might encounter.

• Bernhard Nebel.
  Logics for Knowledge Representation.
  In N. J. Smelser und P. B. Baltes (Hrsg.), International Encyclopedia of the Social and Behavioral Sciences. Kluwer, Dordrecht 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Knowledge representation and reasoning plays a central role in Artificial Intelligence, and formal logic has become the prevalent formal tool in this area. We give a brief historical sketch of the development of the field and describe what interesting developments the last two decades have brought in terms of new logical formalisms. In particular, we argue that the important point about using logic is not so much which particular logic used, but that the logic method is used to understand knowledge and reasoning.

• Jochen Renz und Bernhard Nebel.
  Efficient Methods for Qualitative Spatial Reasoning.
  Journal of Artificial Intelligence Research 15, S. 289-318. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  The theoretical properties of qualitative spatial reasoning in the RCC-8 framework have been analyzed extensively. However, no empirical investigation has been made yet. Our experiments show that the adaption of the algorithms used for qualitative temporal reasoning can solve large RCC-8 instances, even if they are in the phase transition region -- provided that one uses the maximal tractable subsets of RCC-8 that have been identified by us. In particular, we demonstrate that the orthogonal combination of heuristic methods is successful in solving almost all apparently hard instances in the phase transition region up to a certain size in reasonable time.

• Jussi Rintanen.
  Partial implicit unfolding in the Davis-Putnam procedure for quantified Boolean formulae.
  In R. Nieuwenhuis und A. Voronkov (Hrsg.), International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR01), S. 362-376. Springer-Verlag 2001.
  (PS.GZ)
  

• Alexander Scivos und Bernhard Nebel.
  Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation.
  In Proc. COSIT-2001. Springer-Verlag 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  The Double Cross calculus has been proposed for the purpose of navigation based on qualitative information about spatial configurations. Up until now, however, no results about algorithmic properties of this calculus are known. First, we explore the possibility of applying constraint propagation techniques to solve the reasoning problem in this calculus. For this purpose, we have to generalize the known techniques for binary relations because the Double Cross calculus is based on ternary relations. We will show, however, that such a generalization leads to problems. The Double Cross calculus is not closed under composition and permutation. Further, as we will show, there exists no finite refinement of the base relations with such a closure property. Finally, we show that determining satisfiability of constraint systems over Double Cross relations is NP-hard, even if only the base relations of the Double Cross calculus are used. On the positive side, however, we show that the reasoning problem is solvable in PSPACE.

• Mathias Broxvall, Peter Jonsson und Jochen Renz.
  Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints.
  In Sixth International Conference on Principles and Practice of Constraint Programming (CP'00). Singapore 2000.
  (PS.GZ)
  

• Yannis Dimopoulos, Bernhard Nebel und Francesca Toni.
  Finding Admissible and Preferred Arguments Can be Very Hard.
  In Principles of Knowledge Representation and Reasoning, Proceedings of the 7th International Conference (KR'2000). 2000.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Bondarenko et al. have recently proposed an extension of the argumentation-theoretic semantics of admissible and preferred arguments, originally proposed for logic programming only, to a number of other nonmonotonic reasoning formalisms. In this paper we analyse the computational complexity of credulous and sceptical reasoning under the semantics of admissible and preferred arguments for (the propositional variant of) some well-known frameworks for nonmonotonic reasoning, i.e. Theorist, Circumscription and Autoepistemic Logic. While the new semantics have been assumed to mitigate the computational problems of nonmonotonic reasoning under the standard semantics of stable extensions, we show that in many cases reasoning under the new semantics is computationally harder than under the standard semantics. In particular, for Autoepistemic Logic, the sceptical reasoning problem under the semantics of preferred arguments is located at the fourth level of the polynomial hierarchy, two levels above the same problem under the standard semantics. In some cases, however, reasoning under the new semantics becomes easier - reducing to reasoning in the monotonic logics underlying the nonmonotonic frameworks.

• Reinhard Moratz, Jochen Renz und Diedrich Wolter.
  Qualitative Spatial Reasoning about Line Segments.
  In 14th European Conference on Artificial Intelligence (ECAI'00). Berlin, Germany 2000.
  (PS.GZ)
  

• Bernhard Nebel.
  Knowledge Representation and Reasoning - The Theoretical Side of AI.
  In 14th European Conference on Artificial Intelligence, Proceedings (ECAI 2000), S. 763. Berlin, Germany 2000.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Representing knowledge and reasoning with it is at the heart of most AI systems. Nevertheless, the field of Knowledge Representation and Reasoning (KR&R) does not seem to have much impact on practical work in AI. I will try to point out the reasons for the discrepancy and I will argue that KR&R can be understood as Theoretical Artifical Intelligence. Further, I point out a number of fruitful applications of KR&R techniques.

• Jochen Renz, Reinhold Rauh und Markus Knauff.
  Towards Cognitive Adequacy of Topological Spatial Relations.
  In C. Freksa, W. Brauer, C. Habel und K. F. Wender (Hrsg.), Spatial Cognition II - Integrating abstract theories, empirical studies, formal models, and practical applications. Springer-Verlag, Berlin 2000.
  (PS.GZ) (PDF)
  

• Yannis Dimopoulos, Bernhard Nebel und Francesca Toni.
  Preferred Arguments are Harder to Compute than Stable Extensions.
  In Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI 1999). Stockholm, Sweden 1999.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  Based on an abstract framework for nonmonotonic reasoning, Bondarenko et al. have extended the logic programming semantics of admissible and preferred arguments to other nonmonotonic formalisms such as circumscription, auto-epistemic logic and default logic. Although the new semantics have been tacitly assumed to mitigate the computational problems of nonmonotonic reasoning under the standard semantics of stable extensions, it seems questionable whether they improve the worst-case behaviour. As a matter of fact, we show that credulous reasoning under the new semantics in propositional logic programming and propositional default logic has the same computational complexity as under the standard semantics. Furthermore, sceptical reasoning under the admissibility semantics is easier - since it is trivialised to monotonic reasoning. Finally, sceptical reasoning under the preferability semantics is harder than under the standard semantics.

• Christoph Dornheim.
  Graph Embedding with Topological Cycle-Constraints.
  In J. Kratochvil (Hrsg.), Proceedings of the 7th International Symposium on Graph Drawing (GD 1999). Stirin, Czech Republic 1999.
  (PS.GZ)
  

• Bernhard Nebel.
  Frame-Based Systems.
  In R. A. Wilson und F. Keil (Hrsg.), MIT Encyclopedia of the Cognitive Sciences. MIT Press, Cambridge, MA 1999.
  

• Hans Jürgen Ohlbach und Jana Koehler.
  Modal Logics, Description Logics and Arithmetic Reasoning.
  Artificial Intelligence 109 (1-2), S. 1-31. 1999.
  (PS.GZ)
  

• Jochen Renz.
  Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis.
  In Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI 1999). Stockholm, Sweden 1999.
  (PS.GZ)
  

• Jochen Renz und Bernhard Nebel.
  On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus.
  Artificial Intelligence 108 (1-2), S. 95-149. 1999.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question for the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the ``Region Connection Calculus'' RCC-8. We extend Bennett's encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset path-consistency is sufficient for deciding consistency.

• Christoph Dornheim.
  Undecidability of Plane Polygonal Mereotopology.
  In A. G. Cohn, L. Schubert und S. C. Shapiro (Hrsg.), Principles of Knowledge Representation and Reasoning, Proceedings of the 6th International Conference (KR'98). Trento, Italy 1998.
  (PS.GZ)
  

• Alfonso Gerevini und Jochen Renz.
  Combining Topological and Qualitative Size Constraints for Spatial Reasoning.
  In Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP'98). 1998.
  (slightly revised; PS.GZ)
  

• Bernhard Nebel.
  How Hard is it to Revise a Belief Base?
  In D. Dubois und H. Prade (Hrsg.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, S. 77-145. Kluwer, Dordrecht, The Netherlands 1998.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  If a new piece of information contradicts our previously held beliefs, we have to revise our beliefs. This problem of belief revision arises in a number of areas in Computer Science and Artificial Intelligence, e.g., in updating logical database, in hypothetical reasoning, and in machine learning. Most of the research in this area is influenced by work in philosophical logic, in particular by Gärdenfors and his colleagues, who developed the theory of belief revision. Here we will focus on the computational aspects of this theory, surveying results that address the issue of the computational complexity of belief revision.

• Jochen Renz und Bernhard Nebel.
  Efficient Methods for Qualitative Spatial Reasoning.
  In Proceedings of the 13th European Conference on Artificial Intelligence (ECAI'98). 1998.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (C programs used for the evaluation; TAR.GZ) (hard instances; TAR.GZ)
  

  The theoretical properties of qualitative spatial reasoning in the RCC-8 framework have been analyzed extensively. However, no empirical investigation has been made yet. Our experiments show that the adaption of the algorithms used for qualitative temporal reasoning can solve large RCC-8 instances, even if they are in the phase transition region - provided that one uses the maximal tractable subset of RCC-8 that has been identified by us. In particular, we demonstrate that the orthogonal combination of heuristic methods is successful in solving almost all apparently hard instances in the phase transition region up to a certain size in reasonable time.

• Jochen Renz.
  A Canonical Model of the Region Connection Calculus.
  In A.G. Cohn, L. Schubert und S.C. Shapiro (Hrsg.), Principles of Knowledge Representation and Reasoning, Proceedings of the 6th International Conference (KR'98). Trento, Italy 1998.
  (PS.GZ)
  

• Jochen Renz und Bernhard Nebel.
  Spatial Reasoning with Topological Information.
  In C. Freksa, C. Habel und K. F. Wender (Hrsg.), Spatial Cognition - An interdisciplinary approach to representation and processing of spatial knowledge, S. 351-372. Springer-Verlag, Berlin 1998.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  This chapter summarizes our ongoing research on topological spatial relationship using the Region Connection Calculus. We are addressing different questions and problems that arise when using this calculus including representational issues, e.g., how can regions be represented and what is the required dimension of the applied space, computational issues, e.g., how hard is it to reason with the calculus and are there efficient algorithms, and cognitive issues, i.e, is the calculus cognitively adequate.

• Markus Knauff, Reinhold Rauh und Jochen Renz.
  A Cognitive Assessment of Topological Spatial Relations: Results from an Empirical Investigation.
  In Proceedings of the 3rd International Conference on Spatial Information Theory (COSIT'97). 1997.
  (PS.GZ)
  

• Bernhard Nebel.
  Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class.
  CONSTRAINTS 1 (3), S. 175-190. 1997.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (C programs used for the evaluation; TAR.GZ)
  

  While the worst-case computational properties of Allen's calculus for qualitative temporal reasoning have been analyzed quite extensively, the determination of the empirical efficiency of algorithms for solving the consistency problem in this calculus has received only little research attention. In this paper, we will demonstrate that using the ORD-Horn class in Ladkin and Reinefeld's backtracking algorithm leads to performance improvements when deciding consistency of hard instances in Allen's calculus. For this purpose, we prove that Ladkin and Reinefeld's algorithm is complete when using the ORD-Horn class, we identify phase transition regions of the reasoning problem, and compare the improvements of ORD-Horn with other heuristic methods when applied to instances in the phase transition region. Finally, we give evidence that combining search methods orthogonally can dramatically improve the performance of the backtracking algorithm.

• Hans Jürgen Ohlbach und Jana Koehler.
  Role Hierarchies and Number Restrictions.
  In Proc. Int. Workshop on Description Logics '97 (DL'97). 1997.
  (PS.GZ) (extended technical report; PS.GZ)
  

• Jochen Renz und Bernhard Nebel.
  On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus.
  In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI'97), S. 522-527. 1997.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question for the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the "Region Connection Calculus" RCC-8. We extend Bennett's encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset path-consistency is sufficient for deciding consistency.

• Bernhard Nebel.
  Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class.
  In Proceedings of the 12th European Conference on Artificial Intelligence (ECAI'96). 1996.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  While the worst-case computational properties of Allen's calculus for qualitative temporal reasoning have been analyzed quite extensively, the determination of the empirical efficiency of algorithms for solving the consistency problem in this calculus has received only little research attention. In this paper, we will demonstrate that using the ORD-Horn class in Ladkin and Reinefeld's backtracking algorithm leads to performance improvements when deciding consistency of hard instances in Allen's calculus. For this purpose, we prove that Ladkin and Reinefeld's algorithm is complete when using the ORD-Horn class, we identify phase transition regions of the reasoning problem, and compare the improvements of ORD-Horn with other heuristic methods when applied to instances in the phase transition region. Finally, we give evidence that combining search methods orthogonally can dramatically improve the performance of the backtracking algorithm.

Robotik

• Christian Becker-Asano, Severin Gustorff, Kai Oliver Arras, Kohei Ogawa, Shuichi Nishio, Hiroshi Ishiguro und Bernhard Nebel.
  Robot embodiment, operator modality, and social interaction in tele-existence: a project outline.
  In Proceedings of the 8th ACM/IEEE international conference on Human-robot interaction, S. 79-80. 2013.
  

• Christian Dornhege und Alexander Kleiner.
  A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
  Advanced Robotics 27 (6). 2013.
  To appear.
  

• Kai M. Wurm, Christian Dornhege, Cyrill Stachniss, Bernhard Nebel und Wolfram Burgard.
  Coordinating Heterogeneous Teams of Robots using Temporal Symbolic Planning.
  Autonomous Robots. 2013.
  To appear.
  

• Christian Becker-Asano und Hiroshi Ishiguro.
  Intercultural Differences in Decoding Facial Expressions of the Android Robot Geminoid F.
  Journal of Artificial Intelligence and Soft Computing Research 1 (3), S. 215-231. 2012.
  (Abstract einblenden) (Abstract ausblenden)
  

  As android robots become increasingly sophisticated in their technical as well as artistic design, their non-verbal expressiveness is getting closer to that of real humans. Accordingly, this paper presents results of two online surveys designed to evaluate a female android's facial display of five basic emotions. Being interested in intercultural differences we prepared both surveys in English, German, as well as Japanese language, and we not only found that in general our design of the emotional expressions "fearful" and "surprised" (...)

• Stefan Kohlbrecher, Karen Petersen, Gerald Steinbauer, Johannes Maurer, Peter Lepej, Suzana Uran, Rodrigo Ventura, Christian Dornhege, Andreas Hertle, Raymond Sheh und Johannes Pellenz.
  Community-Driven Development of Standard Software Modules for Search and Rescue Robots.
  In Safety, Security and Rescue Robotics (SSRR). 2012.
  

• Christian Becker-Asano, Kai Oliver Arras, Bernhard Nebel und Hiroshi Ishiguro.
  The Effect of Anthropomorphism on Social Tele-Embodiment.
  In IROS 2012 Workshop on Human-Agent Interaction. 2012.
  (Abstract einblenden) (Abstract ausblenden)
  

  This paper outlines our approach to explore the impact of using two different robotic embodiments on an operators ability to convey emotional and conversational nonverbal signals to a distant interlocutor. Although a human's ability to produce and interpret complex, dynamic facial expressions is seen as an important factor for human-human social interaction, it remains controversial in humanoid/android robotics, whether recreating such expressiveness is really worth the technical challenge, or not. (...)

• Stephanie Embgen, Matthias Luber, Christian Becker-Asano, Marco Ragni, Vanessa Evers und Kai Oliver Arras.
  Robot-Specific Social Cues in Emotional Body Language.
  In Proc. IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN'12), S. 1019-1025. 2012.
  (Abstract einblenden) (Abstract ausblenden)
  

  Humans use very sophisticated ways of bodily emotion expression combining facial expressions, sound, gestures and full body posture. Like others, we want to apply these aspects of human communication to ease the interaction between robots and users. In doing so we believe there is a need to consider what abstraction of human social communicative behaviors is appropriate for robots. The study reported in this paper is a pilot study to not offer simulated emotion but to offer an abstracted robot version of emotion expressions (...)

• Andreas Hertle, Christian Dornhege, Thomas Keller und Bernhard Nebel.
  Planning with Semantic Attachments: An Object-Oriented View.
  In Proceedings of the European Conference on Artificial Intelligence (ECAI 2012). 2012.
  (PDF) (BIB)
  

• Christian Becker-Asano.
  Affective Computing Combined with Android Science.
  KI - Künstliche Intelligenz Vol. 25, S. 245-250. 2011.
  (PDF) (BIB)
  

• Christian Dornhege und Alexander Kleiner.
  A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
  In Proceedings of the IEEE International Symposium on Safety, Security and Rescue Robotics (SSRR). 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We consider the problem of an autonomous robot searching for objects in unknown 3d space. Similar to the well known frontier-based exploration in 2d, the problem is to determine a minimal sequence of sensor viewpoints until the entire search space has been explored. We introduce a novel approach that combines the two concepts of voids, which are unexplored volumes in 3d, and frontiers, which are regions on the boundary between voids and explored space. Our approach has been evaluated on a mobile platform equipped with a manipulator searching for victims in a simulated USAR setup. First results indicate the real-world capability and search efficiency of the proposed method.

• Alexander Kleiner, Dali Sun und D. Meyer-Delius.
  ARMO: Adaptive Road Map Optimization for Large Robot Teams.
  In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS). 2011.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Autonomous robot teams that simultaneously dispatch transportation tasks are playing more and more an important role in present logistic centers and manufacturing plants. In this paper we consider the problem of robot motion planning for large robot teams in the industrial domain. We present adaptive road map optimization (ARMO) that is capable of adapting the road map in real time whenever the environment has changed. Based on linear programming, ARMO computes an optimal road map according to current environmental constraints (including human whereabouts) and the current demand for transportation tasks from loading stations in the plant. For detecting dynamic changes, the environment is describe by a grid map augmented with a hidden Markov model (HMM). We show experimentally that ARMO outperforms decoupled planning in terms of computation time and time needed for task completion.

• Alexander Kleiner, A. Kolling, K. Sycara und M. Lewis.
  Hierarchical Visibility for Guaranteed Search in Large-Scale Outdoor Terrain.
  Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS). 2011.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Searching for moving targets in large environments is a challenging task that is relevant in several problem domains, such as capturing an invader in a camp, guarding security facilities, and searching for victims in large-scale search and rescue scenarios. The guaranteed search problem is to coordinate the search of a team of agents to guarantee the discovery of all targets. In this paper we present a self-contained solution to this problem in 2.5D real-world domains represented by digital elevation models (DEMs). We introduce hierarchical sampling on DEMs for selecting heuristically the close to minimal set of locations from which the entire surface of the DEM can be guarded. Locations are utilized to form a search graph on which search strategies for mobile agents are computed. For these strategies schedules are derived which include agent paths that are directly executable in the terrain. Presented experimental results demonstrate the performance of the method. The practical feasibility of our approach has been validated during a field experiment at the Gascola robot training site where teams of humans equipped with iPads successfully searched for adversarial and omniscient evaders. The field demonstration is the largest-scale implementation of a guaranteed search algorithm to date.

• Q. Hamp, L. Reindl und Alexander Kleiner.
  Lessons Learned from German Research for USAR.
  In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR). 2011.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We present lessons learned in USAR research within the framework of the German research project I-LOV. After three years of development first field tests have been carried out by professionals such as the Rapid Deployment Unit for Salvage Operations Abroad (SEEBA). We present results from evaluating search teams in simulated USAR scenarios equipped with newly developed technical search means and digital data input terminals developed in the I- LOV project. In particular, the bioradar, a ground-penetrating radar system for the detection of humanoid movements, a semi-active video probe for rubble pile exploration of more than 10 m length, and the decision support system FRIEDAA were evaluated and compared with conventional search methods. Results of this evaluation indicate that the developed technologies foster advantages in USAR, which are discussed in this paper.

• D. Meyer-Delius, M. Beinhofer, Alexander Kleiner und W. Burgard.
  Reducing the Ambiguity in the Environment by Placing Artificial Landmarks to Improve Mobile Robot Localization.
  In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA). 2011.
  (to appear).
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Robust and reliable localization is a fundamental prerequisite for successful robot navigation. Although there exist many solutions to the localization problem, environments can be inherently ambiguous so that different robot locations cannot to be distinguished using the sensors of the robot. This is particularly critical in comercial environments, for example in warehouses, containing long corridors and symmetric structures. This ambiguity makes localization approaches more likely to diverge or even prevent the pose of the robot from being uniquely estimated at all. In this paper we propose the utilization of artificial landmarks to reduce the inherent ambiguity in the environment, and present an efficient, localization-oriented approach to landmark placement. Our approach provides us with both the location and number of landmarks to be placed in order to improve the localization performance of the robot in a given environment. Experimental results show that by intelligently placing the landmarks we can improve the localization performance of the robot.

• Danijel Skocaj, Matej Kristan, Alen Vrecko, Marko Mahnic, Miroslav Janicek, Geert-Jan M. Kruijff, Marc Hanheide, Nick Hawes, Thomas Keller, Michael Zillich und Kai Zhou.
  A system for interactive learning in dialogue with a tutor.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2011). 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  In this paper we present representations and mechanisms that facilitate continuous learning of visual concepts in dialogue with a tutor and show the implemented robot system. We present how beliefs about the world are created by processing visual and linguistic information and show how they are used for planning system behaviour with the aim at satisfying its internal drive -- to extend its knowledge. The system facilitates different kinds of learning initiated by the human tutor or by the system itself. We demonstrate these principles in the case of learning about object colours and basic shapes.

• Alper Aydemir, Moritz Göbelbecker, Andrzej Pronobis, Kristoffer Sjöö und Patric Jensfelt.
  Plan-based Object Search and Exploration Using Semantic Spatial Knowledge in the Real World.
  In Proceedings of the 5th European Conference on Mobile Robotics (ECMR 2011). 2011.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In this paper we present a principled planner based approach to the active visual object search problem in unknown environments. We make use of a hierarchical planner that combines the strength of decision theory and heuristics. Furthermore, our object search approach leverages on the conceptual spatial knowledge in the form of object cooccurences and semantic place categorisation. A hierarchical model for representing object locations is presented with which the planner is able to perform indirect search. Finally we present real world experiments to show the feasibility of the approach.

• Moritz Göbelbecker, Alper Aydemir, Andrzej Pronobis, Kristoffer Sjöö und Patric Jensfelt.
  A Planning Approach to Active Visual Search in Large Environments.
  In Proceedings of the AAAI-11 Workshop on Automated Action Planning for Autonomous Mobile Robots (PAMR). 2011.
  Workshop version of the ECMR11 paper "Plan-based Object Search and Exploration Using Semantic Spatial Knowledge in the Real World".
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In this paper we present a principled planner based approach to the active visual object search problem in unknown environments. We make use of a hierarchical planner that combines the strength of decision theory and heuristics. Furthermore, our object search approach leverages on the conceptual spatial knowledge in the form of object co-occurrences and semantic place categorisation. A hierarchical model for representing object locations is presented with which the planner is able to perform indirect search. Finally we present real world experiments to show the feasibility of the approach.

• Marc Hanheide, Charles Gretton, Richard Dearden, Nick Hawes, Jeremy Wyatt, Andrzej Pronobis, Alper Aydemir, Moritz Göbelbecker und Hendrik Zender.
  Exploiting Probabilistic Knowledge under Uncertain Sensing for Efficient Robot Behaviour.
  In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011). 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Robots must perform tasks efficiently and reliably while acting under uncertainty. One way to achieve efficiency is to give the robot common-sense knowledge about the structure of the world. Reliable robot behaviour can be achieved by modelling the uncertainty in the world probabilistically. We present a robot system that combines these two approaches and demonstrate the improvements in efficiency and reliability that result. Our first contribution is a probabilistic relational model integrating common-sense knowledge about the world in general, with observations of a particular environment. Our second contribution is a continual planning system which is able to plan in the large problems posed by that model, by automatically switching between decision-theoretic and classical procedures. We evaluate our system on object search tasks in two different real-world indoor environments. By reasoning about the trade-offs between possible courses of action with different informational effects, and exploiting the cues and general structures of those environments, our robot is able to consistently demonstrate efficient and reliable goal-directed behaviour.

• A. Kolling, Alexander Kleiner, M. Lewis und K. Sycara.
  Computing and Executing Strategies for Moving Target Search.
  In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA). 2011.
  (to appear).
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We address the problem of searching for moving targets in large outdoor environments represented by height maps. To solve the problem we present a complete system that computes from an annotated height map a graph representation and search strategies based on worst-case assumptions about all targets. These strategies are then used to compute a schedule and task assignment for all agents. We improve the graph construction from previous work and for the first time present a method that computes a schedule to minimize the execution time. For this we consider travel times of agents determined by a path planner on the height map. We demonstrate the entire system in a real environment with an area of 700,000m2 in which eight human agents search for two intruders using mobile computing devices (iPads). To the best of our knowledge this is the first demonstration of a search system applied to such a large environment.

• R. Kümmerle, B. Steder, Christian Dornhege, Alexander Kleiner, G. Grisetti und W. Burgard.
  Large Scale Graph-based SLAM using Aerial Images as Prior Information.
  Autonomous Robots 30, S. 25-39. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  The problem of learning a map with a mobile robot has been intensively studied in the past and is usually referred to as the simultaneous localization and mapping (SLAM) problem. However, most existing solutions to the SLAM problem learn the maps from scratch and have no means for incorporating prior information. In this paper, we present a novel SLAM approach that achieves global consistency by utilizing publicly accessible aerial photographs as prior information. It inserts correspondences found between stereo and three-dimensional range data and the aerial images as constraints into a graph-based formulation of the SLAM problem. We evaluate our algorithm based on large real-world datasets acquired even in mixed in- and outdoor environments by comparing the global accuracy with state-of-the-art SLAM approaches and GPS. The experimental results demonstrate that the maps acquired with our method show increased global consistency.

• Wei Mou und Alexander Kleiner.
  Online Learning Terrain Classification for Adaptive Velocity Control.
  In Proceedings of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR 2010). 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Safe teleoperation during critical missions, such as urban search and rescue and bomb disposal, requires careful velocity control when different types of terrain are found in the scenario. This can particularly be challenging when mission time is limited and the operator’s field of view affected. This paper presents a method for online adapting robot velocities according to the terrain classification from vision and laser readings. The classifier adapts itself to illumination variations, and can be improved online given feedback from the operator.

• Nick Hawes, Marc Hanheide, Kristoffer Sjöö, Alper Aydemir, Patric Jensfelt, Moritz Göbelbecker, Michael Brenner, Hendrik Zender, Pierre Lison, Ivana Kruijff-Korbayov, Geert-Jan M. Kruijff und Michael Zillich.
  Dora The Explorer: A Motivated Robot.
  In Proc. of 9th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010). 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Dora the Explorer is a mobile robot with a sense of curios- ity and a drive to explore its world. Given an incomplete tour of an indoor environment, Dora is driven by internal motivations to probe the gaps in her spatial knowledge. She actively explores regions of space which she hasn't previously visited but which she expects will lead her to further unex- plored space. She will also attempt to determine the cate- gories of rooms through active visual search for functionally important objects, and through ontology-driven inference on the results of this search.

• Andreas Kolling, Alexander Kleiner, Michael Lewis und Katia Sycara.
  Solving Pursuit-Evasion Problems on Height Maps.
  In IEEE International Conference on Robotics and Automation (ICRA 2010) Workshop: Search and Pursuit/Evasion in the Physical World: Efficiency, Scalability, and Guarantees (WSPE ICRA 2010). 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In this paper we present an approach for a pursuit-evasion problem that considers a 2.5d environment represented by a height map. Such a representation is particularly suitable for large-scale outdoor pursuit-evasion. By allowing height information we not only capture some aspects of 3d visibility but can also consider target heights. In our approach we construct a graph representation of the environment by sampling points and their detection sets which extend the usual notion of visibility. Once a graph is constructed we compute strategies on this graph using a modification of previous work on graph-searching. This strategy is converted into robot paths that are planned on the height map by classifying the terrain appropriately. In experiments we investigate the performance of our approach and provide examples including a map of a small village with surrounding hills and a sample map with multiple loops and elevation plateaus. Experiments are carried out with varying sensing ranges as well as target and sensor heights. To the best of our knowledge the presented approach is the first viable solution to 2.5d pursuit-evasion with height maps.

• Daniel Maier und Alexander Kleiner.
  Improved GPS Sensor Model for Mobile Robots in Urban Terrain.
  In IEEE International Conference on Robotics and Automation (ICRA 2010), S. 4385-4390. 2010.
  (Video).
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Autonomous robot navigation in outdoor scenarios gains increasing importance in various growing application areas. Whereas in non-urban domains such as deserts the problem of successful GPS-based navigation appears to be almost solved, navigation in urban domains particularly in the close vicinity of buildings is still a challenging problem. In such situations GPS accuracy significantly drops down due to multiple signal reflections with larger objects causing the so-called multipath error. In this paper we contribute a novel approach for incorporating multi- path errors into the conventional GPS sensor model by analyzing environmental structures from online generated point clouds. The approach has been validated by experimental results conducted with an all- terrain robot operating in scenarios requiring close- to-building navigation. Presented results show that positioning accuracy can significantly be improved within urban domains.

• Alexander Kleiner und Christian Dornhege.
  Mapping for the Support of First Responders in Critical Domains.
  Journal of Intelligent and Robotic Systems (JINT), S. 1-29. 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In critical domains such as urban search and rescue (USAR), and bomb disposal, the deployment of teleoperated robots is essential to reduce the risk of first responder personnel. Teleoperation is a difficult task, particularly when controlling robots from an isolated safety zone. In general, the operator has to solve simultaneously the problems of mission planning, target identification, robot navigation, and robot control. We introduce a system to support teleoperated navigation with real-time mapping consisting of a two-step scan matching method that re-considers data associations during the search. The algorithm processes data from laser range finder and gyroscope only, thereby it is independent from the robot platform. Furthermore, we introduce a user-guided procedure for improving the global consistency of maps generated by the scan matcher. Globally consistent maps are computed by a graph-based maximum likelihood method that is biased by localizing crucial parts of the scan matcher trajectory on a prior given geo-tiff image. The approach has been implemented as an embedded system and extensively tested on robot platforms designed for teleoperation in critical situations, such as bomb disposal. Furthermore, the system was evaluated in a test maze by first responders during the Disaster City event in Texas 2008.

• Sören Schwertfeger, Adam Jacoff, Chris Scrapper, Johannes Pellenz und Alexander Kleiner.
  Evaluation of Maps using Fixed Shapes: The Fiducial Map Metric.
  In Proc. of the Int. Workshop on Performance Metrics for Intelligent Systems (PerMIS), S. 344-351. NIST 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Mapping is an important task for mobile robots. Assessing the quality of those maps is an open topic. A new approach on map evaluation is presented here. It makes use of artificial objects placed in the environment named "Fiducials". Using the known ground-truth positions and the positions of the fiducials identified in the map, a number of quality attributes can be assigned to that map. Depending on the application domain those attributes are weighed to compute a final score. During the 2010 NIST Response Robot Evaluation Exercise at Disaster City an area was populated with fiducials and different mapping runs were performed. The maps generated there are assessed in this paper demonstrating the Fiducial approach. Finally this map scoring algorithm is compared to other approaches found in literature.

• A. Kolling, Alexander Kleiner, M. Lewis und and K. Sycara.
  Pursuit-Evasion in 2.5d based on Team-Visibility.
  In Proceedings of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS 2010), S. 4610-4616. 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In this paper we present an approach for a pursuit-evasion problem that considers a 2.5d environment represented by a height map. Such a representation is particularly suitable for large-scale outdoor pursuit-evasion, captures some aspects of 3d visibility and can include target heights. In our approach we construct a graph representation of the environment by sampling points and computing detection sets, an extended notion of visibility. Moreover, the constructed graph captures overlaps of detection sets allowing for a coordinated team-based clearing of the environment with robots that move to the sampled points. Once a graph is constructed we compute strategies on it utilizing previous work on graph-searching. This is converted into robot paths that are planned on the height map by classifying the terrain appropriately. In experiments we investigate the performance of our approach and provide examples including a sample map with multiple loops and elevation plateaus and two realistic maps, one of a village and one of a mountain range. To the best of our knowledge the presented approach is the first viable solution to 2.5d pursuit-evasion with height maps.

• Dali Sun, Alexander Kleiner und and C. Schindelhauer.
  Decentralized Hash Tables For Mobile Robot Teams Solving Intra-Logistics Tasks.
  In Proceedings of the 9th Int. Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), S. 923-930. 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Although a remarkably high degree of automation has been reached in production and intra-logistics nowadays, human labor is still used for transportation using handcarts and forklifts. High labor cost and risk of injury are the undesirable consequences. Alternative approaches in automated warehouses are fixed installed conveyors installed either overhead or floor-based. The drawback of such solutions is the lack of flexibility, which is necessary when the production lines of the company change. Then, such an installation has to be re-built. In this paper, we propose a novel approach of decentralized teams of autonomous robots performing intra-logistics tasks using distributed algorithms. Centralized solutions suffer from limited scalability and have a single point of failure. The task is to transport material between stations keeping the communication network structure intact and most importantly, to facilitate a fair distribution of robots among loading stations. Our approach is motivated by strategies from peer-to-peer-networks and mobile ad-hoc networks. In particular we use an adapted version of distributed heterogeneous hash tables (DHHT) for distributing the tasks and localized communication. Experimental results presented in this paper show that our method reaches a fair distribution of robots over loading stations.

• Marc Gissler, Christian Dornhege, Bernhard Nebel und Matthias Teschner.
  Deformable Proximity Queries and their Application in Mobile Manipulation Planning.
  In Symposium on Visual Computing (ISVC 2009), S. 79-88. AAAI Press 2009.
  (Abstract einblenden) (Abstract ausblenden) (BIB)
  

• Alexander Kleiner, Chris Scrapper und Adam Jacoff.
  RoboCupRescue Interleague Challenge 2009: Bridging the gap between Simulation and Reality.
  In Proceedings of the Int. Workshop on Performance Metrics for Intelligent Systems (Permis 2009), S. 123-129. NIST 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Teleoperation is a difficult task, particularly when controlling robots from an isolated operator station. In general, the operator has to solve nearly blindly the problems of mission planning, target identification, robot navigation, and robot control at the same time. The goal of the proposed system is to support teleoperated navigation with real-time mapping. We present a novel scan matching technique that re-considers data associations during the search, enabling robust pose estimation even under varying roll and pitch angle of the robot enabling mapping on rough terrain. The approach has been implemented as an embedded system and extensively tested on robot platforms designed for teleoperation in critical situations, such as bomb disposal. Furthermore, the system has been evaluated in a test maze by first responders during the Disaster City event in Texas 2008. Finally, experiments conducted within different environments show that the system yields comparably accurate maps in real-time when compared to higher sophisticated offline methods, such as Rao-Blackwellized SLAM.

• Alexander Kleiner und Christian Dornhege.
  Operator-Assistive Mapping in Harsh Environments.
  In IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2009), S. 1-6. 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Teleoperation is a difficult task, particularly when controlling robots from an isolated operator station. In general, the operator has to solve nearly blindly the problems of mission planning, target identification, robot navigation, and robot control at the same time. The goal of the proposed system is to support teleoperated navigation with real-time mapping. We present a novel scan matching technique that re-considers data associations during the search, enabling robust pose estimation even under varying roll and pitch angle of the robot enabling mapping on rough terrain. The approach has been implemented as an embedded system and extensively tested on robot platforms designed for teleoperation in critical situations, such as bomb disposal. Furthermore, the system has been evaluated in a test maze by first responders during the Disaster City event in Texas 2008. Finally, experiments conducted within different environments show that the system yields comparably accurate maps in real-time when compared to higher sophisticated offline methods, such as Rao-Blackwellized SLAM.

• Rainer Kümmerle, Bastian Steder, Christian Dornhege, Michael Ruhnke, Giorgio Grisetti, Cyrill Stachniss und Alexander Kleiner.
  On Measuring the Accuracy of SLAM Algorithms.
  Autonomous Robots 27 (4), S. 387-407. 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In this paper, we address the problem of creating an objective benchmark for evaluating SLAM approaches. We propose a framework for analyzing the results of a SLAM approach based on a metric for measuring the error of the corrected trajectory. This metric uses only relative relations between poses and does not rely on a global reference frame. This overcomes serious shortcomings of approaches using a global reference frame to compute the error. Our method furthermore allows us to compare SLAM approaches that use different estimation techniques or different sensor modalities since all computations are made based on the corrected trajectory of the robot.

  We provide sets of relative relations needed to compute our metric for an extensive set of datasets frequently used in the robotics community. The relations have been obtained by manually matching laser-range observations to avoid the errors caused by matching algorithms. Our benchmark framework allows the user to easily analyze and objectively compare different SLAM approaches.

• Geert-Jan Kruijff und Michael Brenner.
  Phrasing Questions.
  In AAAI Spring Symposium on Agents that Learn from Human Teachers. 2009.
  

• Wolfram Burgard, Cyrill Stachniss, Giorgio Grisetti, Bastian Steder, Rainer Kümmerle, Christian Dornhege, Michael Ruhnke, Alexander Kleiner und Juan D. Tardos.
  A Comparison of SLAM Algorithms Based on a Graph of Relations.
  In Proceedings of the 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009), S. 2089-2095. IEEE 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In this paper, we address the problem of creating an objective benchmark for comparing SLAM approaches. We propose a framework for analyzing the results of SLAM approaches based on a metric for measuring the error of the corrected trajectory. The metric uses only relative relations between poses and does not rely on a global reference frame. The idea is related to graph-based SLAM approaches in the sense that it considers the energy needed to deform the trajectory estimated by a SLAM approach to the ground truth trajectory. Our method enables us to compare SLAM approaches that use different estimation techniques or different sensor modalities since all computations are made based on the corrected trajectory of the robot. We provide sets of relative relations needed to compute our metric for an extensive set of datasets frequently used in the SLAM community. The relations have been obtained by manually matching laser-range observations. We believe that our benchmarking framework allows the user an easy analysis and objective comparisons between different SLAM approaches.

• Rainer Kümmerle, Bastian Steder, Christian Dornhege, Alexander Kleiner, Giorgio Grisetti und Wolfram Burgard.
  Large Scale Graph-based SLAM using Aerial Images as Prior Information.
  In Proceedings of 2009 Robotics: Science and Systems (RSS 2009). 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  To effectively navigate in their environments and accurately reach their target locations, mobile robots require a globally consistent map of the environment. The problem of learning a map with a mobile robot has been intensively studied in the past and is usually referred to as the simultaneous localization and mapping (SLAM) problem. However, existing solutions to the SLAM problem typically rely on loop-closures to obtain global consistency and do not exploit prior information even if it is available. In this paper, we present a novel SLAM approach that achieves global consistency by utilizing publicly accessible aerial photographs as prior information. Our approach inserts correspondences found between three-dimensional laser range scans and the aerial image as constraints into a graph-based formulation of the SLAM problem. We evaluate our algorithm based on large real-world datasets acquired in a mixed in- and outdoor environment by comparing the global accuracy with state-of-the-art SLAM approaches and GPS. The experimental results demonstrate that the maps acquired with our method show increased global consistency.

• Dali Sun, Alexander Kleiner und T. M. Wendt.
  Multi-Robot Range-Only SLAM by Active Sensor Nodes for Urban Search and Rescue.
  In Robocup 2008: Robot Soccer World Cup XII, S. 318-330. Springer 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  To jointly map an unknown environment with a team of autonomous robots is a challenging problem, particularly in large environments, as for example the devastated area after a disaster. Under such conditions standard methods for Simultaneous Localization And Mapping (SLAM) are difficult to apply due to possible misinterpretations of sensor data, leading to erroneous data association for loop closure. We consider the problem of multi-robot range-only SLAM for robot teams by solving the data association problem with wireless sensor nodes that we designed for this purpose. The memory of these nodes is utilized for the exchange of map data between multiple robots, facilitating loop-closures on jointly generated maps. We introduce RSLAM, which is a variant of FastSlam, extended for range-only measurements and the multi-robot case. Maps are generated from robot odometry and range estimates, which are computed from the RSSI (Received Signal Strength Indication). The proposed method has been extensively tested in USARSim, which serves as basis for the Virtual Robots competition at RoboCup, and by real-world experiments with a team of mobile robots. The presented results indicates that the approach is capable of building consistent maps in presence of real sensor noise, as well as to improve mapping results of multiple robots by data sharing.

• Geert-Jan Kruijff, Michael Brenner und Nick Hawes.
  Continual Planning for Cross-Modal Situated Clarification in Human-Robot Interaction.
  In Proceedings of the 17th IEEE International Symposium on Robots and Human Interactive Communication (RO-MAN 2008). 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Current robots do not fully understand the world they are situated in, including what humans talk to them about. A fundamental problem in robotics is thus how a robot can clarify such a lack of understanding. This paper addresses the question of how a robot can create a plan for resolving a need for clarification. This paper characterizes situated clarification as an information need which may arise in any sensory-motoric modality interpreting the situated context of the robot, or any deliberative modality referring to that context. The paper then focuses on how, once a clarification need has been identified, the robot can create a plan in which one or more modalities are involved in resolving it. Modalities are involved on the basis of the types of information they can provide. These information types are identified in the ontologies the modalities use to interconnect their content with content of other modalities ("information fusion"). We take a continual approach to planning and execution monitoring. This provides the abiltity to re-plan depending on modality availability and success in resolving (part of) a clarification need. We illustrate our implementation of this approach with several examples from our system.

• Armin Hornung und Dapeng Zhang.
  On-Line Detection of Rule Violations in Table Soccer.
  In Andreas R. Dengel, Karsten Berns, Thomas M. Breuel, Frank Bomarius und Thomas R. Roth-Berghofer (Hrsg.), Proceedings of the 31st Annual German Conference on AI (KI 2008), S. 217-224. Springer-Verlag 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.

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

• Dapeng Zhang.
  Robot Plays Table-Soccer.
  In Proc. of Dagstuhl Seminar (08372), Computer Science in Sport - Mission and Methods 2008. 2008.
  Presentation (in .ppt) .
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Our research focuses on learning approaches with robot KiRo. KiRo is a table soccer robot which can challenge even advanced human players. Previously, we developed a method using learning by imitation, by which KiRo can automatically acquire the demonstrated actions. Recently, we constructed a game-recorder which collects data from the human-played games. The in-process work is about explaining the recorded data, which is to classify and to evaluate human's skills. A brief overview of the previous work is addressed, and the perspective is discussed.

• Thilo Weigel und Bernhard Nebel.
  Tischfußball: Mensch versus Computer.
  Informatik Spektrum 31, S. 323-332. 2008.
  (Abstract einblenden) (Abstract ausblenden)
  

  Table soccer 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. KiRo and StarKick are two systems that have been built to play this game against humans. These systems are interesting because they are the first computerized physical games that are played on a level competitive with experienced humans. Furthermore, these systems enable us to evaluate different AI techniques in context, e.g., action selection methods, as is shown in the paper.

• 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), S. 99-104. 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.

• Alexander Kleiner, G. Steinbauer und F. Wotawa.
  Towards automated online diagnosis of robot navigation software.
  In Proc. of Int. Conf. on Simulation, Modeling and Programming for Autonomous Robots (SIMPAR), S. 159-170. Springer 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Control software of autonomous mobile robots comprises a number of software modules that typically interact in a very complex way. Their proper interaction and the robustness of each single module strongly influences the safety during navigation in the field. Particularly in unstructured environments, unforeseen situations are likely to occur, causing erroneous behaviors of the robot. The proper handling of such situations requires an understanding of cause and effect within the complex interactions of the system. In this paper we present an approach which is able to automatically derive a model of the communication behavior within a component-orientated control software. The model can be used for online diagnosis in order to increase system robustness during runtime. We demonstrate model learning and system diagnosis on three different robot systems which were controlled by software modules communicating based on the widely used IPC (Inter Process Communication) standard. The demonstrated learning and diagnosis was carried out without any a priori knowledge about the systems.

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

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

• Michael Brenner.
  Situation-Aware Interpretation, Planning and Execution of User Commands by Autonomous Robots.
  In Proceedings of the 16th IEEE International Symposium on Robots and Human Interactive Communication (ROMAN 2007). Jeju, Korea 2007.
  (PDF)
  

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

• 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), S. 3005-3011. 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  To autonomously navigate on rough terrain is a challenging problem for mobile robots, requiring the ability to decide whether parts of the environment can be traversed or have to be bypassed, which is commonly known as Obstacle Negotiation (ON). In this paper, we introduce a planning framework that extends ON to the general case, where different types of terrain classes directly map to specific robot skills, such as climbing stairs and ramps. This extension is based on a new concept called behavior maps, which is utilized for the planning and execution of complex skills. Behavior maps are directly generated from elevation maps, i.e. two-dimensional grids storing in each cell the corresponding height of the terrain surface, and a set of skill descriptions. Results from extensive experiments are presented, showing that the method enables the robot to explore successfully rough terrain in real-time, while selecting the optimal trajectory in terms of costs for navigation and skill execution.

• Alexander Kleiner und R. Kümmerle.
  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), S. 3025-3030. 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  One primary goal in rescue robotics is to deploy a team of robots for coordinated victim search after a disaster. This requires robots to perform subtasks, such as victim detection, in real-time. Human detection by computationally cheap techniques, such as color thresholding, turn out to produce a large number of false-positives. Markov Random Fields (MRFs) can be utilized to combine the local evidence of multiple weak classifiers in order to improve the detection rate. However, inference in MRFs is computational expensive. In this paper we present a novel approach for the genetic optimizing of the building process of MRF models. The genetic algorithm determines offline relevant neighborhood relations with respect to the data, which are then utilized for generating efficient MRF models from video streams during runtime. Experimental results clearly show that compared to a Support Vector Machine (SVM) based classifier, the optimized MRF models significantly reduce the false-positive rate. Furthermore, the optimized models turned out to be up to five times faster then the non-optimized ones at nearly the same detection rate.

• Alexander Kleiner und Christian Dornhege.
  Real-time Localization and Elevation Mapping within Urban Search and Rescue Scenarios.
  Journal of Field Robotics 24, S. 723-745. 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Urban Search And Rescue (USAR) is a time critical task. Rescue teams have to explore a large terrain within a short amount of time in order to locate survivors after a disaster. One goal in Rescue Robotics is to have a team of heterogeneous robots that explore autonomously, or partially guided by an incident commander, the disaster area. Their task is to jointly create a map of the terrain and to register victim locations, which can further be utilized by human task forces for rescue. Basically, the robots have to solve autonomously in real-time the problem of Simultaneous Localization and Mapping (SLAM), consisting of a continuous state estimation problem and a discrete data association problem. Extraordinary circumstances after a real disaster make it very hard to apply common techniques. Many of these have been developed under strong assumptions, for example, they require polygonal structures, such as typically found in office-like environments. Furthermore, most techniques are not deployable in real-time. In this paper we propose real-time solutions for localization and mapping, which all have been extensively evaluated within the test arenas of the National Institute of Standards and Technology (NIST). We specifically deal with the problems of vision-based pose tracking on tracked vehicles, the building of globally consistent maps based on a network of RFID tags, and the building of elevation maps from readings of a tilted Laser Range Finder (LRF). Our results show that these methods lead under modest computational requirements to good results within the utilized testing arenas.

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

• S. Balakirsky, S. Carpin, Alexander Kleiner, M. Lewis, A. Visser, J. Wang und V.A. Ziparo.
  Towards heterogeneous robot teams for disaster mitigation: Results and Performance Metrics from Robocup Rescue.
  Journal of Field Robotics 24, S. 943-967. 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Urban Search And Rescue is a growing area of robotic research. The RoboCup Federation has recognized this, and has created the new Virtual Robots competition to complement its existing physical robot and agent competitions. In order to successfully compete in this competition, teams need to field multi-robot solutions that cooperatively explore and map an environment while searching for victims. This paper presents the results of the first annual RoboCup Rescue Virtual competition. It provides details on the metrics used to judge the contestants as well as summaries of the algorithms used by the top four teams. This allows readers to compare and contrast these effective approaches. Furthermore, the simulation engine itself is examined and real-world validation results on the engine and algorithms are offered.

• V.A. Ziparo, Alexander Kleiner, L. Marchetti, A. Farinelli und and D. Nardi.
  Cooperative Exploration for USAR Robots with Indirect Communication.
  In Proceedings of the 6th IFAC Symposium on Intelligent Autonomous Vehicles (IAV 2007). 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  To coordinate a team of robots for exploration is a challenging problem, particularly in unstructured areas, as for example post-disaster scenarios where direct communication is severely constrained. Furthermore, conventional methods of SLAM, e.g. those performing data association based on visual features, are doomed to fail due to bad visibility caused by smoke and fire. We use indirect communication (based on RFIDs), to share knowledge and use a gradient-like local search to direct robots towards interesting areas. To share a common frame of reference among robots we use a feature based SLAM approach (where features are RFIDs). The approach has been evaluated on a 3D simulation based on USARSim.

• 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) (BIB)
  

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

• 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.
  (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), S. 1-6. 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We consider the problem of jointly performing SLAM by humans and robots in Urban Search And Rescue (USAR) scenarios. In this context, SLAM is a challenging task. First, places are hardly re-observable by vision techniques since visibility might be affected by smoke and fire. Second, loop-closure is cumbersome due to the fact that firemen will intentionally try to avoid performing loops when facing the reality of emergency response, e.g.USAR, while they are searching for victims. Furthermore, there might be places that are only accessible to robots, making it necessary to integrate humans and robots into one team for mapping the area after a disaster. In this paper, we introduce a method for jointly correcting individual trajectories of humans and robots by utilizing RFID technology for data association. Hereby the poses of humans and robots are tracked by a PDR (Pedestrian Dead Reckoning), and slippage sensitive odometry, respectively. We conducted extensive experiments with a team of humans, and a human-robot team within a semi-outdoor environment. Results from these experiments show that the introduced method allows to improve single trajectories based on the joint graph, even if they do not contain any loop.

• H. Kenn und Alexander Kleiner.
  Towards the Integration of Real-Time Real-World Data in Urban Search and Rescue Simulation.
  In MobileResponse, S. 106-115. Springer 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  The coordinated reaction to a large-scale disaster is a challenging research problem. The Robocup rescue simulation league addresses this research problem but is currently lacking an interface to real-world real-time data to test the validity of both simulation and simulated reactions. In this paper, we describe a wearable-computing-based real world interface to the Robocup Resuce simulation software and provide some updated results of preliminary evaluations.

• 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), S. 1461-1466. 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We consider the problem of Decentralized Simultaneous Localization And Mapping (DSLAM) for pedestrians in the context of Urban Search And Rescue (USAR). In this context, DSLAM is a challenging task. First, data exchange fails due to cut off communication links. Second, loop-closure is cumbersome due to the fact that fireman will intentionally try to avoid performing loops, when facing the reality of emergency response, e.g. while they are searching for victims. In this paper, we introduce a solution to this problem based on the non-selfish sharing of information between pedestrians for loop-closure. We introduce a novel DSLAM method which is based on data exchange and association via RFID technology, not requiring any radio communication. The approach has been evaluated within both outdoor and semi-indoor environments. The presented results show that sharing information between single pedestrians allows to optimize globally their individual paths, even if they are not able to communicate directly.

• 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) (BIB)
  

  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.

• 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 - Robot 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)
  

• 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). 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Localization and mapping on autonomous robots typically requires a good pose estimate, which is hard to acquire if the vehicle is tracked. In this paper we describe a solution to the pose estimation problem by utilizing a consumer-quality camera and an Inertial Measurement Unit (IMU). The basic idea is to continuously track salient features with the KLT feature tracker over multiple images taken by the camera and to extract from the tracked features image vectors resulting from the robot's motion. Each image vector is taken for a voting that best explains the robot's motion. Image vectors vote according to a previously trained ^\m2102tile coding^\m2112 classificator that assigns to each possible image vector a translation probability. Our results show that the proposed single camera solution leads to sufficiently accurate pose estimates of the tracked vehicle.

• Alexander Kleiner, N. Behrens und H. Kenn.
  Wearable computing meets multiagent systems: A real-world interface for the RoboCupRescue simulation platform.
  In First International Workshop on Agent Technology for Disaster Management at AAMAS06, S. 116-123. AAMAS Press 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  One big challenge in disaster response is to get an overview over the degree of damage and to provide this information, together with optimized plans for rescue missions, back to teams in the field. Collapsing infrastructure, limited visibility due to smoke and dust, and overloaded communication lines make it nearly impossible for rescue teams to report the total situation consistently. This problem can only be solved by efficiently integrating data of ^\m2102many^\m2112 observers into a single consistent view. A Global Positioning System (GPS) device in conjunction with a communication device, and sensors or simple input methods for reporting observations, offer a realistic chance to solve the data integration problem. We propose preliminary results from a wearable computing device, acquiring disaster relevant data, such as locations of victims and blockades, and show the data integration into the RoboCupRescue Simulation platform, which is a benchmark for MAS within the RoboCup competitions. We show exemplarily how the data can consistently be integrated and how rescue missions can be optimized by solutions developed on the RoboCupRescue simulation platform. The preliminary results indicate that nowadays wearable computing technology combined with MAS technology can serve as a powerful tool for Urban Search and Rescue (USAR).

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

• Alexander Kleiner, Michael Brenner, Tobias Braeuer, Christian Dornhege, Moritz Göbelbecker, 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.

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

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

• Thilo Weigel, Dapeng Zhang, Klaus Rechert und Bernhard Nebel.
  Adaptive Vision for Playing Table Soccer.
  In S. Biundo, T. Frühwirth und G. Palm (Hrsg.), 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 (Hrsg.), 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.

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

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

• 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 Göbelbecker, 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)
  

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

• Alankar Karol, Bernhard Nebel, Christopher Stanton und Mary-Anne Williams.
  Case Based Game Play in the RoboCup Four-Legged League: Part I The Theoretical Model.
  In RoboCup Symposium 2003, S. 739-747. Padova, Italy 2003.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Robot Soccer involves planning at many levels, and in this paper we develop high level planning strategies for robots playing in the RoboCup FourLegged League using case based reasoning. We develop a framework for developing and choosing game plays. Game plays are widely used in many team sports e.g. soccer, hockey, polo, and rugby. One of the current challenges for robots playing in the RoboCup Four-Legged League is choosing the right behaviour in any game situation. We argue that a flexible theoretical model for using case based reasoning for game plays will prove useful in robot soccer. Our model supports game play selection in key game situations which should in turn significantly advantage the team.

• Alexander Kleiner und Thorsten Buchheim.
  A Plugin-Based Architecture For Simulation In The F2000 League.
  In Proceedings of the International RoboCup Symposium '03. Padova, Italy 2003.
  (PS.GZ) (PDF)
  

• Bernhard Nebel.
  The Philosophical Soccer Player.
  In Proceedings of the Eights International Conference on Principles and Knowledge Representation and Reasoning (KR-02), S. 631. 2002.
  

• Dr. Ansgar Bredenfeld und Thilo Weigel.
  Kickende Computer.
  c't 13/2002, S. 86. 2002.
  (HTML)
  

• Markus Jäger und Bernhard Nebel.
  Dynamic Decentralized Area Partitioning for Cooperating Cleaning Robots.
  In ICRA'02. 2002.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  If multiple cleaning robots are used to cooperatively clean a larger room, e.g., an airport, the room must be partitioned among the robots. This paper describes a dynamic and decentralized method to partition a certain area among multiple robots. The area is divided into polygons, which are allocated by the robots. After a robot has allocated a certain polygon, it is responsible for cleaning the polygon. The method described in this paper does not need any global synchronization and does not require a global communication network.

• Alexander Kleiner, Markus Dietl und Bernhard Nebel.
  Towards a Life-Long Learning Soccer Agent.
  In Proceedings of the International RoboCup Symposium '02. Fukuoka, Japan 2002.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  One problem in robotic soccer (and in robotics in general) is to adapt skills and the overall behavior to a changing environment and to hardware improvements. We applied hierarchical reinforcement learning in an SMDP framework learning on all levels simultaneously. As our experiments show, learning simultaneously on the skill level and on the skill selection level is advantageous since it allows for a smooth adaption to a changing environment. Furthermore, the skills we trained turn also out to be quite competitive when run on the real robotic players of the players of our CS Freiburg team.

• Bernhard Nebel.
  Helfer aus dem Stadion.
  Gehirn & Geist Nr. 1/2002, S. 6-8. 2002.
  

• Bernhard Nebel.
  Fußball und Künstliche Intelligenz: Vom Denken zum Handeln.
  Künstliche Intelligenz Heft 1/02. 2002.
  (PS.GZ) (PDF)
  

• Thilo Weigel und Bernhard Nebel.
  KiRo - An Autonomous Table Soccer Player.
  In Proceedings of the International RoboCup Symposium '02. Fukuoka, Japan 2002.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  This paper presents the table soccer game as a new domain for the research in the fields of robotics and artificial intelligence. A system capable of playing table soccer on a competitive level and in a fully autonomous way is described. It can serve a human both as a teammate and an opponent but also allows for matches between two artificial players. As the presented system can be utilized for various purposes it is an attractive innovation for research, education and entertainment.

• Thilo Weigel, Jens-Steffen Gutmann, Markus Dietl, Alexander Kleiner und Bernhard Nebel.
  CS Freiburg: Coordinating Robots for Successful Soccer Playing.
  IEEE Transactions on Robotics and Automation 18 (5), S. 685-699. 2002.
  (Abstract einblenden) (Abstract ausblenden)
  

  Robotic soccer is a challenging research domain because many different research areas have to be addressed in order to create a successful team of robot players. This paper presents the CS Freiburg team, the winner in the middle size league at RoboCup 1998, 2000 and 2001. The paper focuses on multi-agent coordination for both perception and action. The contributions of this work are new methods for tracking ball and players observed by multiple robots, team coordination methods for strategic team formation and dynamic role assignment, a rich set of basic skills allowing to respond to large range of situations in an appropriate way, an action selection method based on behavior networks as well as a method to learn the skills and their selection. As demonstrated by evaluations of the different methods and by the success of the team, these methods permit the creation of a multi-robot group, which is able to play soccer successfully. In addition, the developed methods promise to advance the state of the art in the multi-robot field.

• Minoru Asada, Tucker Balch, Raffaelo D'Andrea, Masahiro Fujita, Bernhard Hengst, Gerhard Kraetzschmar, Pedro Lima, Nuno Lau, Henrik Lund, Daniel Polani, Paul Scerri, Satoshi Tadokoro, Thilo Weigel und Gordon Wyeth.
  RoboCup-2000: The Fourth Robotic Soccer World Championships.
  AI Magazine 22 (1), S. 11-38. 2001.
  (PS.GZ) (PDF)
  

• Markus Dietl, Jens-Steffen Gutmann und Bernhard Nebel.
  Cooperative Sensing in Dynamic Environments.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-2001). 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  This work presents methods for tracking objects from noisy and unreliable data taken by a team of robots. We develop a multi­object tracking algorithm based on Kalman filtering and a single­object tracking method involving a combination of Kalman filtering and Markov localization for outlier detection. We apply these methods in the context of robot soccer for robots participating in the middle­size league and compare them to a simple averaging method. Results including situations from real competition games are presented.

• Markus Dietl, Jens-Steffen Gutmann und Bernhard Nebel.
  CS Freiburg: Global View by Cooperative Sensing.
  In International RoboCup Symposium 2001. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Global vision systems as found in the small size league are prohibited in the middle size league. This paper presents methods for creating a global view of the world by cooperative sensing of a team of robots. We develop a multi­object tracking algorithm based on Kalman filtering and a single­object tracking method involving a combination of Kalman filtering and Markov localization for outlier detection. We apply these methods for robots participating in the middle­size league and compare them to a simple averaging method. Results including situations from real competition games are presented.

• Jens-Steffen Gutmann, Thilo Weigel und Bernhard Nebel.
  A Fast, Accurate, and Robust Method for Self-Localization in Polygonal Environments Using Laser-Range-Finders.
  Advanced Robotics 14 (8), S. 651-668. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Self-localization is important in almost all robotic tasks. For playing an aesthetic and effective game of robotic soccer, self-localization is a necessary prerequisite. When we designed our robotic soccer team for participating in robotic soccer competitions, it turned out that all existing approaches did not meet our requirements of being fast, accurate, and robust. For this reason, we developed a new method, which is presented and analyzed in this paper. This method is one of the key components and is probably one of the explanations for the success of our team in national and international competitions. We present also experimental evidence that our method outperforms other self-localization methods in the RoboCup environment.

• Guido Isekenmeier, Bernhard Nebel und Thilo Weigel.
  Evaluation of the Performance of CS Freiburg 1999 and CS Freiburg 2000.
  In International RoboCup Symposium 2001. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  One of the questions one may ask when following research in robotic soccer is whether there is a measurable progress over the years in the robotic leagues. While everybody who has followed the games from 1997 to 2000 would agree that the robotic soccer players in the F2000 league have improved their playing skills, there is no hard evidence to justify this opinion. We tried to identify a number of criteria that measure the ability to play robotic soccer and analyzed all the games CS Freiburg played at RoboCup 1999 and 2000. As it turns out, for almost all criteria, there is a statistically significant increase for CS Freiburg and the opponent teams demonstrating that the level of play has indeed increased from 1999 to 2000.

• Markus Jäger und Bernhard Nebel.
  Decentralized Collision Avoidance, Deadlock Detection, and Deadlock Resolution for Multiple Mobile Robots.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-2001). 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  This paper describes a method for coordinating the independently planned trajectories of multiple mobile robots to avoid collisions and deadlocks among them. Whenever the distance between two robots drops be­ low a certain value, they exchange information about their planned trajectories and determine whether they are in danger of a collision. If a possible collision is detected, they monitor their movements and, if necessary, insert idle times between certain segments of their trajectories in or­ der to avoid the collision. Deadlocks among two or more robots occur if a number of robots block each other in a way such that none of them is able to continue along its trajectory without causing a collision. These deadlocks are reliably detected. After a deadlock is detected, the trajectory planners of each of the involved robots are successively asked to plan an alternative trajectory until the deadlock is resolved. We use a combination of three fully distributed algo­ rithms to reliably solve the task. They do not use any global synchronization and do not interfere with each other.

• Bernhard Nebel.
  Cooperating Physical Robots: A Lesson in Playing Robotic Soccer.
  In M. Luck, V. Marik, O. Stepankova und R. Trappl (Hrsg.), Multi-Agent Systems and Applications, S. 404-414. Springer-Verlag 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Having a robot that carries out a task for you is certainly of some help. Having a group of robots seems to be even better because in this case the task may be finished faster and more reliably. However, dealing with a group of robots can make some problems more difficult. In this paper we sketch some of the advantages and some problems that come up when dealing with groups of robots. In particular, we describe techniques as they have been developed and tested in the area of robotic soccer.

• Thilo Weigel, Willi Auerbach, Markus Dietl, Burkhard Dümler, Jens-Steffen Gutmann, Kornel Marko, Klaus Müller, Bernhard Nebel, Boris Szerbakowski und Maximilian Thiel.
  CS Freiburg: Doing the Right Thing in a Group.
  In P. Stone, G. Kraetzschmar und T. Balch (Hrsg.), RoboCup 2000: Robot Soccer World Cup IV, S. 52-63. Springer-Verlag 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  The success of CS Freiburg at RoboCup 2000 can be attributed to an effective cooperation between players based on sophisticated soccer skills and a robust and accurate self-localization method. In this paper, we present our multi-agent coordination approach for both, action and perception, and our rich set of basic skills which allow to respond to a large range of situations in an appropriate way. Furthermore our action selection method based on an extension to behavior networks is described. Results including statistics from CS Freiburg final games at RoboCup 2000 are presented.

• Thilo Weigel, Alexander Kleiner, Florian Diesch, Markus Dietl, Jens-Steffen Gutmann, Bernhard Nebel, Patrick Stiegeler und Boris Szerbakowski.
  CS Freiburg 2001.
  In International RoboCup Symposium 2001. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  The CS Freiburg team has become F2000 champion the third time in the history of RoboCup. The success of our team can probably be attributed to its robust sensor interpretation and its team play. In this paper, we will focus on new developments in our vision system, in our path planner, and in the cooperation component.

• Thilo Weigel, Jens-Steffen Gutmann, Bernhard Nebel, Klaus Müller und Markus Dietl.
  CS Freiburg: Sophisticated Skills and Effective Cooperation.
  In Proc. European Control Conference (ECC-01). Porto, Portugal 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  The success of CS Freiburg at RoboCup 2000 can be attributed to a robust and accurate perception approach and an effec­ tive cooperation between players based on sophisticated soc­ cer skills. In this paper, we present our multi­agent coordi­ nation approach for both, action and perception, and our rich set of basic skills which allow to respond to a large range of situations in an appropriate way. Furthermore, our action se­ lection method based on an extension to behavior networks is described. Results including statistics from CS Freiburg final games at RoboCup 2000 are presented.

• Jens-Steffen Gutmann, Wolfgang Hatzack, Immanuel Herrmann, Bernhard Nebel, Frank Rittinger, Augustinus Topor und Thilo Weigel.
  The CS Freiburg Team: Playing Robotic Soccer Based on an Explicit World Model.
  AI Magazine 21 (1), S. 37-46. 2000.
  (Abstract einblenden) (Abstract ausblenden) (preliminary version; PS.GZ) (preliminary version; PDF)
  

  Robotic soccer is an ideal task to demonstrate new techniques and to explore new problems. Moreover, problems and solutions can be easily communicated because soccer is a well-known game. Our intention in building a robotic soccer team and participating in RoboCup'98 was, first of all, to demonstrate the usefulness of the self-localization methods we have developed. Secondly, we wanted to show that playing soccer based on an explicit world model is much more effective than other methods. Thirdly, we intended to explore the problem of building and maintaining a global team world model. As has been demonstrated by the performance of our team, we were successful on the first two points. Moreover, robotic soccer gave us the opportunity to study problems in distributed, cooperative sensing.

• Jens-Steffen Gutmann, Bernhard Nebel und Christian Reetz.
  CS Freiburg: Architektur und Aktionsauswahl im Roboterfuball.
  In Proc. AMS-2000. 2000.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Roboterfußball ist ein wissenschaftliches anspruchsvolles Forschungsproblem, das erfordert, Probleme aus den Bereichen Robotik, Künstliche Intelligenz und Multi-Agenten-Systeme zu lösen und die Lösungen in einem System zu integrieren, um ein erfolgreiches Roboterfußballteam zu kreieren. In diesem Papier beschreiben wir die Schlüsselkomponenten des CS Freiburg Teams. Dabei fokussieren wir auf die Selbstlokalisation und Objekterkennungsmethoden und die Integration aller Information in ein globales Weltmodell. Basierend auf diesem Weltmodell werden dann Aktionsselektion, Pfadplanung und Kooperation realisiert. Das resultierende System ist äußerst erfolgreich und hat bisher lediglich ein Spiel in einem Wettbewerb verloren.

• Bernhard Nebel und Thilo Weigel.
  The CS Freiburg 2000 Team.
  In Fourth International Workshop on RoboCup. Melbourne, Australia 2000.
  (PS.GZ) (PDF)
  

• Jens-Steffen Gutmann, Thilo Weigel und Bernhard Nebel.
  Fast, Accurate, and Robust Self-Localization in Polygonal Environments.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '99). Kyongju, Korea 1999.
  (Abstract einblenden) (Abstract ausblenden) (preliminary version; PS.GZ)
  

  Self-localization is important in almost all robotic tasks. For playing an aesthetic and effective game of robotic soccer, self-localization is a necessary prerequisite. When we designed our robotic soccer team for RoboCup'98, it turned out that all existing approaches did not meet our requirements of being fast, accurate, and robust. For this reason, we developed a new method, which is presented and analyzed in this paper. We additionally present experimental evidence that our method outperforms other methods in the RoboCup environment.

• Jens-Steffen Gutmann, Wolfgang Hatzack, Immanuel Herrmann, Bernhard Nebel, Frank Rittinger, Augustinus Topor, Thilo Weigel und Bruno Welsch.
  The CS Freiburg Robotic Soccer Team: Reliable Self-Localization, Multirobot Sensor Integration, and Basic Soccer Skills.
  In M. Asada (Hrsg.), RoboCup-98: Robot Soccer World Cup II, S. 93-108. Springer-Verlag, Berlin, Heidelberg, New York 1999.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  Robotic soccer is a challenging research domain because problems in robotics, artificial intelligence, multi-agent systems and real-time reasoning have to be solved in order to create a successful team of robotic soccer players. In this paper, we describe the key components of the CS Freiburg team. We focus on the self-localization and object recognition method based on using laser range finders and the integration of all this information into a global world model. Using the explicit model of the environment built by these components, we have implemented path planning, simple ball handling skills and basic multi-agent cooperation. The resulting system is a very successful robotic soccer team, which has not lost any game yet.

• Jens-Steffen Gutmann, Thilo Weigel und Bernhard Nebel.
  Fast, Accurate, and Robust Self-Localization in the RoboCup Environment.
  In Third International Workshop on RoboCup. 1999.
  (PS.GZ) (extended version from Proc. IROS-99; PS.GZ)
  

• Jens-Steffen Gutmann, Wolfgang Hatzack, Immanuel Herrmann, Bernhard Nebel, Frank Rittinger, Augustinus Topor und Thilo Weigel.
  Reliable Self-Localization, Multirobot Sensor Integration, Accurate Path-Planning and Basic Soccer Skills: Playing an Effective Game of Robotic Soccer.
  In Nineth International Conference on Advanced Robotics (ICAR 1999). 1999.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  Robotic soccer is a challenging research domain because problems in robotics, artificial intelligence, multi-agent systems and real-time reasoning have to be solved in order to create a successful team of robotic soccer players. In this paper, we describe the key components of the CS Freiburg team. We focus on the self-localization and object recognition method based on using laser range finders and the integration of all this information into a global world model. Using the explicit model of the environment built by these components, we have implemented path planning, simple ball handling skills and basic multi-agent cooperation. The resulting system is a very successful robotic soccer team, which has not lost any official game yet.

• Bernhard Nebel, Jens-Steffen Gutmann und Wolfgang Hatzack.
  The CS Freiburg '99 Team.
  In Third International Workshop on RoboCup. 1999.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  Based on the design of the CS Freiburg team, which participated successfully in Robocup'98, we developed a new team of robotic soccer players. While the hardware components and software architecture remained mainly unchanged, we invested some effort to improve the sensor data gathering and interpretation, the tactical components and the behavior-based control module. The main goal is to enable the players to act in a truly cooperative style which leads, for instance, to passing the ball from one player to another.

• Jens-Steffen Gutmann, Wolfram Burgard, Dieter Fox und Kurt Konolige.
  An Experimental Comparison of Localization Methods.
  In International Conference on Intelligent Robots and Systems (IROS 98). Victoria, Canada 1998.
  (PS.GZ)
  

• Bernhard Nebel, Wolfgang Hatzack, Thilo Weigel, Jens-Steffen Gutmann, Immanuel Herrmann, Frank Rittinger und Augustinus Topor.
  CS Freiburg's Participation at RoboCup'98: The World Champions in Robotic Soccer.
  AI Communications 11, S. 243-248. 1998.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  Robotic soccer is a challenging research domain that can be used to explore new problems and to demonstrate new techniques. We participated in RoboCup'98 in order to explore the problems of cooperation in multi-robot-systems and to demonstrate our self-localization techniques based on laser range finders. In this paper we sketch the main technical points of our team, give a description of the process of developing our team before and during the competition, and describe how we viewed the competition in general.

• Sebastian Thrun, Jens-Steffen Gutmann, Dieter Fox, Wolfram Burgard und Benjamin J. Kuipers.
  Integrating Topological and Metric Maps for Mobile Robot Navigation: A Statistical Approach.
  In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98). 1998.
  (PS.GZ)
  

• Jens-Steffen Gutmann und Bernhard Nebel.
  Navigation mobiler Roboter mit Laserscans.
  In Autonome Mobile Systeme 1997 (AMS'97), S. 36-47. Springer-Verlag 1997.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  Es wird ein Verfahren zur Erstellung einer topologischen Karte aus Laserscandaten für die Navigation mobiler Roboter beschrieben. Aus einem Satz sich korrekt überdeckender 360 Grad Scans wird ein Sichtbarkeitsgraph erstellt, wobei Knoten Scanpositionen und Kanten die relative Anzahl gemeinsamer Scanpunkte (genannt Sichtbarkeit) repräsentieren. Aus der Sichtbarkeit und der Distanz der Scanpositionen wird eine subjektive Wahrscheinlichkeit für die Befahrbarkeit zwischen den Scanpositionen berechnet. Durch Annahme von Unabhängigkeit der berechneten Wahrscheinlichkeiten wird mittels uniformer Kostensuche ein möglichst kurzer und sicher befahrbarer Pfad bestimmt. Das Verfahren wurde auf einem Pioneer-1-Roboter mit SICK-Laserscanner implementiert und erprobt. Für die Navigation zu jedem Zwischenziel entlang des Pfades wurde ein gitterbasierter lokaler Wegeplaner verwendet. Dadurch konnte ein hoher Grad an Robustheit erlangt werden. Das System ist in der Lage unvorhergesehenen Hindernissen auszuweichen, nicht passierbare Wege zu erkennen und alternative Wege zu finden.

• Jens-Steffen Gutmann und Christian Schlegel.
  AMOS: Comparison of Scan Matching Approaches for Self-Localization in Indoor Environments.
  In Proceedings of the First Euromicro Workshop on Advanced Mobile Robots (EUROBOT '96), S. 61-68. 1996.
  (PS.GZ)
  

Andere

• Thomas Keller und Malte Helmert.
  Trial-based Heuristic Tree Search for Finite Horizon MDPs.
  In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS13). 2013.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Dynamic programming is a well-known approach for solving MDPs. In large state spaces, asynchronous versions like Real-Time Dynamic Programming have been applied successfully. If unfolded into equivalent trees, Monte-Carlo Tree Search algorithms are a valid alternative. UCT, the most popular representative, obtains good anytime behavior by guiding the search towards promising areas of the search tree. The Heuristic Search algorithm AO∗ finds optimal solutions for MDPs that can be represented as acyclic AND/OR graphs.

  We introduce a common framework, Trial-based Heuristic Tree Search, that subsumes these approaches and distinguishes them based on five ingredients: heuristic function, backup function, action selection, outcome selection, and trial length. Using this framework, we describe three new algorithms which mix these ingredients in novel ways in an attempt to combine their different strengths. Our evaluation shows that two of our algorithms not only provide superior theoretical properties to UCT, but also outperform state-of-the-art approaches experimentally.

• Nicole C. Krämer, Stefan Kopp, Christian Becker-Asano und Nicole Sommer.
  Smile and the world will smile with you-The effects of a virtual agent's smile on users’ evaluation and behavior.
  International Journal of Human-Computer Studies 71 (3), S. 335-349. 2012.
  

• Julien Hué und Matthias Westphal.
  Revising Qualitative Constraint Network: Definition and Implementation.
  In Internation Conference on Tools for Artificial Intelligence (ICTAI), S. 548-555. 2012.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Qualitative Spatial and Temporal Reasoning is a central topic in Artificial Intelligence. In particular, it is aimed at application scenarios dealing with uncertain information and thus needs to be able to handle dynamic beliefs. This makes merging and revision of qualitative information important topics. While merging has been studied extensively, revision which describes what is happening when one learns new information about a static world has been overlooked. In this paper, we propose to fill the gap by providing two revision operations for qualitative calculi. In order to implement these operations, we give algo- rithms for revision and analyze the computational complexity of these problems. Finally, we present an implementation of these algorithms based on a qualitative constraint solver and provide an experimental evaluation.

• Julien Hué, Matthias Westphal und Stefan Wölfl.
  An automatic Decomposition Method for Qualitative Spatial and Temporal Reasoning.
  In Internation Conference on Tools for Artificial Intelligence (ICTAI), S. 588-595. 2012.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Qualitative spatial and temporal reasoning is a research field that studies relational, constraint-based formalisms for representing, and reasoning about, spatial and temporal information. The standard approach for checking consistency is based on an exhaustive representation of possible configurations between three entities, the so-called composition tables. These tables, however, encode semantic background knowledge in a redundant way, which becomes a size and efficiency issue, when the composition table needs to be grounded as done in SAT encodings of problem instances. In this paper, we present a new framework that allows for decomposing composition tables into logically simpler parts, while preserving logical equivalence, e.g., the decomposition in start- and end-points for Allen’s Interval Calculus. We show that finding such decompositions is an NP-complete problem and present a SAT-based method to generate decompositions. Finally, we discuss the impact of our decomposition method on SAT encodings of problem instances, and present a reasoning system built on decompositions that compares favorably with state-of-the-art solvers.

• Birgit Kleim, Thomas Ehrig, Corinna Scheel, Christian Becker-Asano, Bernhard Nebel und Brunna Tuschen-Caffier.
  Bewältigungsverhalten in Notfallsituationen aus klinisch-psychologischer Perspektive.
  Zeitschrift für Klinische Psychologie und Psychotherapie 41 (3), S. 166-179. 2012.
  

• Corinna N. Scheel, Birgit Kleim, Julian Schmitz, Christian Becker-Asano, Dali Sun, Bernhard Nebel und Brunna Tuschen-Caffier.
  Psychophysiologische Belastungsreaktivität nach einem simulierten Feuer in einer Parkgarage.
  Zeitschrift für Klinische Psychologie und Psychotherapie 41 (3), S. 180-189. 2012.
  

• Johannes Löhr, Bernhard Nebel und Stefan Winkler.
  Planning Based Autonomous Lander Control.
  In Proceedings of the Astrodynamics Specialist Conference (AIAA/AAS 2012). 2012.
  (Abstract einblenden) (Abstract ausblenden)
  

  Safe landing of spacecraft on extraterrestrial surfaces implies a number of challenges. The main issue is to precisely initiate coasting, braking and landing maneuvers to safely land at a desired landing zone. Meanwhile, the increasing information level about the landing environment has to be processed and the landing trajectory eventually adapted in order to avoid hazardous situations. In this paper these time critical tasks are performed by Domain Predictive Control. It has been developed to guide dynamic systems into desired goal states by flexibly reordering atomic actions using planning algorithms from artificial intelligence. Here, the method is applied to autonomously adapt control commands and associated landing trajectories with respect to the changing environmental knowledge. Simulation results show the feasibility of this new approach and reveal issues which should be subject to future research.

• Jens Witkowski und David C. Parkes.
  A Robust Bayesian Truth Serum for Small Populations.
  In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012). 2012.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Peer prediction mechanisms allow the truthful elicitation of private signals (e.g., experiences, or opinions) in regard to a true world state when this ground truth is unobservable. The original peer prediction method is incentive compatible for any number of agents n ≥ 2, but relies on a common prior, shared by all agents and the mechanism. The Bayesian Truth Serum (BTS) relaxes this assumption. While BTS still assumes that agents share a common prior, this prior need not be known to the mechanism. However, BTS is only incentive compatible for a large enough number of agents, and the particular number of agents required is uncertain because it depends on this private prior. In this paper, we present a robust BTS for the elicitation of binary information which is incentive compatible for every n ≥ 3, taking advantage of a particularity of the quadratic scoring rule. The robust BTS is the first peer prediction mechanism to provide strict incentive compatibility for every n ≥ 3 without relying on knowledge of the common prior. Moreover, and in contrast to the original BTS, our mechanism is numerically robust and ex post individually rational.

• Thomas Keller und Patrick Eyerich.
  PROST: Probabilistic Planning Based on UCT.
  In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012), S. 119-127. 2012.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We present PROST, a probabilistic planning system that is based on the UCT algorithm by Kocsis and Szepesvari (2006), which has been applied successfully to many areas of planning and acting under uncertainty. The objective of this paper is to show the application of UCT to domain-independent probabilistic planning, an area it had not been applied to before. We furthermore present several enhancements to the algorithm, including a method that is able to drastically reduce the branching factor by identifying superfluous actions. We show how search depth limitation leads to a more thoroughly investigated search space in parts that are influential on the quality of a policy, and present a sound and polynomially computable detection of reward locks, states that correspond to, e.g., dead ends or goals. We describe a general Q-value initialization for unvisited nodes in the search tree that circumvents the initial random walks inherent to UCT, and leads to a faster convergence on average. We demonstrate the significant influence of the enhancements by providing a comparison on the IPPC benchmark domains.

• Johannes Löhr, Patrick Eyerich, Thomas Keller und Bernhard Nebel.
  A Planning Based Framework for Controlling Hybrid Systems.
  In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012). 2012.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The control of dynamic systems, which aims to minimize the deviation of state variables from reference values in a contin- uous state space, is a central domain of cybernetics and con- trol theory. The objective of action planning is to find feasible state trajectories in a discrete state space from an initial state to a state satisfying the goal conditions, which in principle ad- dresses the same issue on a more abstract level. We combine these approaches to switch between dynamic system charac- teristics on the fly, and to generate control input sequences that affect both discrete and continuous state variables. Our approach (called Domain Predictive Control) is applicable to hybrid systems with linear dynamics and discretizable inputs.

• Salem Benferhat, Julien Hué, Sylvain Lagrue und Julien Rossit.
  Merging Interval-Based Possibilistic Belief Bases.
  In International Conference on Scalable Uncertainty Management (SUM), S. 447-458. 2012.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

• Julien Hué, Mariette Sérayet, Pierre Drap, Odile Papini und Eric Würbel.
  Underwater Archaeological 3D Surveys Validation within the Removed Sets Framework.
  In Benchmarks and Applications of Spatial Reasoning (BASR), S. 39-46. 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

• Jens Witkowski und David C. Parkes.
  Peer Prediction without a Common Prior.
  In Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012). 2012.
  Supersedes the SC'11 paper "Peer Prediction with Private Beliefs".
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Reputation mechanisms at online opinion forums, such as Amazon Reviews, elicit ratings from users about their experience with different products. Crowdsourcing applications, such as image tagging on Amazon Mechanical Turk, elicit votes from users as to whether or not a job was duly completed. An important property in both settings is that the feedback received from users (agents) is truthful. The peer prediction method introduced by Miller et al. [2005] is a prominent theoretical mechanism for the truthful elicitation of reports. However, a significant obstacle to its application is that it critically depends on the assumption of a common prior amongst both the agents and the mechanism. In this paper, we develop a peer prediction mechanism for settings where the agents hold subjective and private beliefs about the state of the world and the likelihood of a positive signal given a particular state. Our shadow peer prediction mechanism exploits temporal structure in order to elicit two reports, a belief report and then a signal report, and it provides strict incentives for truthful reporting as long as the effect an agent’s signal has on her posterior belief is bounded away from zero. Alternatively, this technical requirement on beliefs can be dispensed with by a modification in which the second report is a belief report rather than a signal report.

• Alexander Kleiner, Bernhard Nebel und V.A. Ziparo.
  A Mechanism for Dynamic Ride Sharing based on Parallel Auctions.
  In Proc. of the 22th International Joint Conference on Artificial Intelligence (IJCAI). 2011.
  (to appear).
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Car pollution is one of the major causes of green- house emissions, and traffic congestion is rapidly becoming a social plague. Dynamic Ride Sharing (DRS) systems have the potential to mitigate this problem by computing plans for car drivers, e.g. commuters, allowing them to share their rides. Ex- isting efforts in DRS are suffering from the problem that participants are abandoning the system after repeatedly failing to get a shared ride. In this paper we present an incentive compatible DRS solution based on auctions. While existing DRS systems are mainly focusing on fixed assignments that minimize the totally travelled distance, the presented approach is adaptive to individual preferences of the participants. Furthermore, our system allows to tradeoff the minimization of Vehicle Kilometers Travelled (VKT) with the overall probability of successful ride-shares, which is an important feature when bootstrapping the system. To the best of our knowledge, we are the first to present a DRS solution based on auctions using a sealed-bid second price scheme.

• Christian Becker-Asano, Dali Sun, Birgit Kleim, Corinna Scheel, Brunna Tuschen-Caffier und Bernhard Nebel.
  Outline of an Empirical Study on the Effects of Emotions on Strategic Behavior in Virtual Emergencies.
  In Affective Computing and Intelligent Interaction, S. 508-517. 2011.
  (PDF) (BIB)
  

• Christian Becker-Asano.
  Invited Commentary: On Guiding the Design of an Ill-defined Phenomenon.
  International Journal of Synthetic Emotions Vol. 2 (2), S. 66-67. 2011.
  (PDF) (BIB)
  

• Jens Witkowski, Sven Seuken und David C. Parkes.
  Incentive-Compatible Escrow Mechanisms.
  In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI 2011). 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The most prominent way to establish trust between buyers and sellers on online auction sites are reputation mechanisms. Two drawbacks of this approach are the reliance on the seller being long-lived and the susceptibility to whitewashing. In this paper, we introduce so-called escrow mechanisms that avoid these problems by installing a trusted intermediary which forwards the payment to the seller only if the buyer acknowledges that the good arrived in the promised condition. We address the incentive issues that arise and design an escrow mechanism that is incentive compatible, efficient, interim individually rational and ex ante budget-balanced. In contrast to previous work on trust and reputation, our approach does not rely on knowing the sellers' cost functions or the distribution of buyer valuations.

• Johannes Löhr und Stefan Winkler.
  Comparison of Periodic System Lifting Techniques for Robust Stability Analysis of Magnetic Spacecraft Attitude Control Systems.
  In Proceedings of the Guidance Navigation and Control Conference (AIAA/GNC 2011). 2011.
  (Abstract einblenden) (Abstract ausblenden)
  

  Magnetic attitude control is a common method for low Earth orbit spacecraft. Verification of nominal (yes/no), and even more important, robust attitude stability of such systems is of significant importance for any real mission. Considering nadir-oriented operation, the linearized closed-loop attitude dynamics equations lead to a linear time periodic system. While nominal stability can be obtained from Floquet-Theory, robust stability analysis via standard μ-Analysis requires lifting procedures to convert the linear time periodic into a linear time invariant system. Two of those lifting procedures are compared in this paper: (1) "Fast Discretization", which is based on a "sample and hold" view on the periodic state space matrices, and (2) "Frequency Lifting" based on Fourier series expansion. Both methods are applied to a theoretic linear time periodic example from literature and magnetic spacecraft attitude control. The comparison focus' on applicability for real satellite missions.

• Hans-Jörg Peter, Rüdiger Ehlers und Robert Mattmüller.
  Synthia: Verification and Synthesis for Timed Automata.
  In Proceedings of the 23rd International Conference on Computer Aided Verification (CAV 2011), S. 649-655. Springer-Verlag 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We present Synthia, a new tool for the verification and synthesis of open real-time systems modeled as timed automata. The key novelty of Synthia is the underlying abstraction refinement approach that combines the efficient symbolic treatment of timing information by difference bound matrices (DBMs) with the usage of binary decision diagrams (BDDs) for the discrete parts of the system description. Our experiments show that the analysis of both closed and open systems greatly benefits from identifying large relevant and irrelevant system parts on coarse abstractions early in the solution process. Synthia is licensed under the GNU GPL and available from our website.

• Cai Zhongjie, Dapeng Zhang und Bernhard Nebel.
  Playing Tetris Using Bandit-Based Monte-Carlo Planning.
  In Proceedings of AISB 2011 Symposium: AI and Games (AISB 2011). 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Tetris is a stochastic, open-ended board game. Existing artificial Tetris players often use different evaluation functions and plan for only one or two pieces in advance. In this paper, we developed an artificial player for Tetris using the bandit-based Monte-Carlo planning method (UCT). In Tetris, game states are often revisited. However, UCT does not keep the information of the game states explored in the previous planning episodes. We created a method to store such information for our player in a specially designed database to guide its future planning process. The planner for Tetris has a high branching factor. To improve game performance, we created a method to prune the planning tree and lower the branching factor. The experiment results show that our player can successfully play Tetris, and the performance of our player is improved as the number of the played games increases. The player can defeat a benchmark player with high probabilities.

• Sebastian Kupferschmid und Martin Wehrle.
  Abstractions and Pattern Databases: The Quest for Succinctness and Accuracy.
  In Parosh A. Abdulla and K. Rustan M. Leino (Hrsg.), Proceedings of the 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2011), S. 276-290. Springer-Verlag 2011.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Directed model checking is a well-established technique for detecting error states in concurrent systems efficiently. As error traces are important for debugging purposes, it is preferable to find as short error traces as possible. A wide spread method to find provably shortest error traces is to apply the A* search algorithm with distance heuristics that never overestimate the real error distance. An important class of such distance estimators is the class of pattern database heuristics, which are built on abstractions of the system under consideration. In this paper, we propose a systematic approach for the construction of pattern database heuristics. We formally define a concept to measure the accuracy of abstractions. Based on this technique, we address the challenge of finding abstractions that are succinct on the one hand, and accurate to produce informed pattern databases on the other hand. We evaluate our approach on large and complex industrial problems. The experiments show that the resulting distance heuristic impressively advances the state of the art.

• Dapeng Zhang und Bernhard Nebel.
  Feature Induction of Linear-Chain Conditional Random Fields - A Study Based on a Simulation.
  In Proceedings of the 3rd International Conference on Agents and Artificial Intelligence (ICAART 2011). 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Conditional Random Fields (CRFs) is a probabilistic framework for labeling sequential data. Several approaches were developed to automatically induce features for CRFs. They have been successfully applied in real-world applications, e.g. in natural language processing. The work described in this paper was originally motivated by processing the sequence data of table soccer games. As labeling such data is very time consuming, we developed a sequence generator (simulation), which creates an extra phase to explore several basic issues of the feature induction of linear-chain CRFs. First, we generated data sets with different configurations of overlapped and conjunct atomic features, and discussed how these factors affect the induction. Then, a reduction step was integrated into the induction which maintained the prediction accuracy and saved the computational power. Finally, we developed an approach which consists of a queue of CRFs. The experiments show that the CRF queue achieves better results on the data sets in all the configurations.

• Brunna Tuschen-Caffier, Birgit Kleim, Christian Becker-Asano, Dali Sun, Bernhard Nebel und Corinna Scheel.
  Bewältigungsverhalten in virtuellen Notfallsituationen.
  In 7. Workshop Kongress für Psychologie und Psychotherapie. 2011.
  (BIB)
  

• Christian Becker-Asano, Dali Sun, Birgit Kleim, Corinna N. Scheel, Brunna Tuschen-Caffier und Bernhard Nebel.
  CoVE: Coping in Virtual Emergencies.
  In Workshop on Emotion and Computing - Current Research and Future Impact, S. 1. 2011.
  (PDF) (BIB)
  

• Dapeng Zhang, Cai Zhongjie und Bernhard Nebel.
  Playing Tetris Using Learning by Imitation.
  In Proceedings of the 11th annual European Conference on Simulation and AI in Computer Games (GAMEON 2010). 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Tetris is a stochastic and open-end board game. Several artificial players were developed to automatically play Tetris. These players perform well in single games. In this paper, we developed a platform based on an open source project for game competitions among multiple players. We develop an artificial player employed learning by imitation, which is novel in Tetris. The imitation tasks of playing Tetris were mapped to a standard data classification problem. The experiments showed that the performance of the player can be significantly improved when our player acquires similar game skills as those of the imitated human. Our player can play Tetris in diverse ways by imitating different players, and has chances to defeat the best-known artificial player in the world. The framework supports incremental learning because the artificial player can find stronger players and imitate their skills.

• Martin Wehrle und Sebastian Kupferschmid.
  Context-Enhanced Directed Model Checking.
  In Jaco van de Pol und Michael Weber (Hrsg.), Proceedings of the 17th International SPIN Workshop on Model Checking Software (SPIN 2010), S. 88-105. Springer-Verlag 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Directed model checking is a well-established technique to efficiently tackle the state explosion problem when the aim is to find error states in concurrent systems. Although directed model checking has proved to be very successful in the past, additional search techniques provide much potential to efficiently handle larger and larger systems. In this work, we propose a novel technique for traversing the state space based on interference contexts. The basic idea is to preferably explore transitions that interfere with previously applied transitions, whereas other transitions are deferred accordingly. Our approach is orthogonal to the model checking process and can be applied to a wide range of search methods. We have implemented our method and empirically evaluated its potential on a range of non-trivial case studies. Compared to standard model checking techniques, we are able to detect subtle bugs with shorter error traces, consuming less memory and time.

• Thomas Keller, Patrick Eyerich und Bernhard Nebel.
  Task Planning for an Autonomous Service Robot.
  In Rüdiger Dillmann, Jürgen Beyerer, Uwe Hanebeck und Tanja Schultz (Hrsg.), Proceedings on the 33rd Annual German Conference on Artificial Intelligence (KI 2010), S. 358-365. Springer-Verlag 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In the DESIRE project an autonomous robot capable of performing service tasks in a typical kitchen environment has been developed. The overall system consists of various loosely coupled subcomponents providing particular features like manipulating objects or recognizing and interacting with humans. To bring all these subcomponents together to act as monolithic system, a high-performance planning system has been implemented. In this paper, we present this system’s basic architecture and some advanced extensions necessary to cope with the various challenges arising in dynamic and uncertain environments like those a real world service robot is usually faced with.

• Rüdiger Ehlers, Robert Mattmüller und Hans-Jörg Peter.
  Combining Symbolic Representations for Solving Timed Games.
  In Proceedings of the 8th International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS 2010), S. 107-121. Springer-Verlag 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We present a general approach to combine symbolic state space representations for the discrete and continuous parts in the synthesis of winning strategies for timed reachability games. The combination is based on abstraction refinement where discrete symbolic techniques are used to produce a sequence of abstract timed game automata. After each refinement step, the resulting abstraction is used for computing an under- and an over-approximation of the timed winning states. The key idea is to identify large relevant and irrelevant parts of the precise weakest winning strategy already on coarse, and therefore simple, abstractions. If neither the existence nor nonexistence of a winning strategy can be established in the approximations, we use them to guide the refinement process. Based on a prototype that combines binary decision diagrams and difference bound matrices, we experimentally evaluate the technique on standard benchmarks from timed controller synthesis. The results clearly demonstrate the potential of the new approach concerning running time and memory consumption compared to the classical on-the-fly algorithm implemented in UPPAAL-Tiga.

• Malte Helmert und Gabriele Röger.
  Relative-Order Abstractions for the Pancake Problem.
  In Helder Coelho, Rudi Studer und Michael Wooldridge (Hrsg.), Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), S. 745-750. IOS Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The pancake problem is a famous search problem where the objective is to sort a sequence of objects (pancakes) through a minimal number of prefix reversals (flips). The best approaches for the problem are based on heuristic search with abstraction (pattern database) heuristics. We present a new class of abstractions for the pancake problem called relative-order abstractions. Relative-order abstractions have three advantages over the object-location abstractions considered in previous work. First, they are size-independent, i.e., do not need to be tailored to a particular instance size of the pancake problem. Second, they are more compact in that they can represent a larger number of pancakes within abstractions of bounded size. Finally, they can exploit symmetries in the problem specification to allow multiple heuristic lookups, significantly improving search performance over a single lookup. Our experiments show that compared to object-location abstractions, our new techniques lead to an improvement of one order of magnitude in runtime and up to three orders of magnitude in the number of generated states.

• Malte Helmert.
  Landmark Heuristics for the Pancake Problem.
  In Ariel Felner und Nathan Sturtevant (Hrsg.), Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS 2010), S. 109-110. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We describe the gap heuristic for the pancake problem, which dramatically outperforms current abstraction-based heuristics for this problem. The gap heuristic belongs to a family of landmark heuristics that have recently been very successfully applied to planning problems.

• Jens Witkowski.
  Truthful Feedback for Sanctioning Reputation Mechanisms.
  In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010). 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  For product rating environments, similar to that of Amazon Reviews, it has been shown that the truthful elicitation of feedback is possible through mechanisms which pay buyer reports contingent on the reports of other buyers. We study whether similar mechanisms can be designed for reputation mechanisms at online auction sites where the buyers' experiences are partially determined by a strategic seller. We show that this is impossible for the basic setting. However, introducing a small prior belief that the seller is a cooperative commitment player leads to a payment scheme with a truthful perfect Bayesian equilibrium.

• Hans-Jörg Peter und Robert Mattmüller.
  Component-based Abstraction Refinement for Timed Controller Synthesis.
  In Theodore P. Baker (Hrsg.), Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS 2009), S. 364-374. IEEE Computer Society 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We present a novel technique for synthesizing controllers for distributed real-time environments with safety requirements. Our approach is an abstraction refinement extension to the on-the-fly algorithm by Cassez et al. from 2005. Based on partial compositions of some environment components, each refinement cycle constructs a sound abstraction that can be used to obtain under- and over-approximations of all valid controller implementations. This enables (1) early termination if an implementation does not exist in the over-approximation, or, if one does exist in the under-approximation, and (2) pruning of irrelevant moves in subsequent refinement cycles. In our refinement loop, the precision of the abstractions incrementally increases and converges to all specification-critical components.

  We implemented our approach in a prototype synthesis tool and evaluated it on an industrial benchmark. In comparison with the timed game solver UPPAAL-Tiga, our technique outperforms the nonincremental approach by an order of magnitude.

• Bahareh Badban, Stefan Leue und Jan-Georg Smaus.
  Automated Predicate Abstraction for Real-Time Models.
  In Axel Legay and Azadeh Farzan (Hrsg.), Proceedings of the 11th International Workshop on Verification of Infinite-State Systems (INFINITY 2009), S. 36-43. 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We present a technique designed to automatically compute predicate abstractions for dense real-timed models represented as networks of timed automata. We use the CIPM algorithm in our previous work which computes new invariants for timed automata control locations and prunes the model, to compute a predicate abstraction of the model. We do so by taking information regarding control locations and their newly computed invariants into account.

• Dapeng Zhang, Cai Zhongjie, Chen Kefei und Bernhard Nebel.
  A Game Controller Based on Multiple Sensors.
  In In Proceedings of the Fifth International Conference on Advances in Computer Entertainment Tochnology (ACE 2009). 2009.
  Video.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  A digital game is normally controlled by hand. Playing such a game requires only minimum hand movements. Rather than being easy and comfortable, this game controller is designed to be physically taxing for the players. It consists of several sensors, which makes a game more lively and forces the users to be more physically active. By using different mapping methods, one game can be played in several ways. The statistics gathered from the experiments show that even though the quality of control on the chosen fighting game is not as high as with a normal joystick, the developed controller is still preferred by most of the participants. It induces much more movement than a normal joystick.

• Jens Witkowski.
  Eliciting Honest Reputation Feedback in a Markov Setting.
  In Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI 2009). 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Recently, online reputation mechanisms have been proposed that reward agents for honest feedback about products and services with fixed quality. Many real-world settings, however, are inherently dynamic. As an example, consider a web service that wishes to publish the expected download speed of a file mirrored on different server sites. In contrast to the models of Miller, Resnick and Zeckhauser and of Jurca and Faltings, the quality of the service (e.g., a server's available bandwidth) changes over time and future agents are solely interested in the present quality levels. We show that hidden Markov models (HMM) provide natural generalizations of these static models and design a payment scheme that elicits honest reports from the agents after they have experienced the quality of the service.

• Moritz Göbelbecker und Christian Dornhege.
  Realistic Cities in Simulated Environments - An Open Street Map to Robocup Rescue Converter.
  In Online-Proceedings of the Fourth International Workshop on Synthetic Simulation and Robotics to Mitigate Earthquake Disaster (SRMED 2009). 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  A general problem when developing large scale disaster simulation environments is to acquire GIS data. In this work, we tackle the problem of map generation from public sources. Usually the major problem is not only the data conversion itself, but to get access to the data at all. We solve this problem by using the website OpenStreetMap.org, that provides mapping data for the whole world in a wiki-style concept, as our source of data, thus being able to generate maps for almost any city. The data is converted to the format required by the Robocup Rescue Simulation System, enabling simulations on various real-world scenarios.

• Jörg Hoffmann, Piergiorgio Bertoli, Malte Helmert und Marco Pistore.
  Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection.
  Journal of Artificial Intelligence Research 35, S. 49-117. 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Thanks to recent advances, AI Planning has become the underlying technique for several applications. Figuring prominently among these is automated Web Service Composition (WSC) at the "capability" level, where services are described in terms of preconditions and effects over ontological concepts. A key issue in addressing WSC as planning is that ontologies are not only formal vocabularies; they also axiomatize the possible relationships between concepts. Such axioms correspond to what has been termed "integrity constraints" in the actions and change literature, and applying a web service is essentially a belief update operation. The reasoning required for belief update is known to be harder than reasoning in the ontology itself. The support for belief update is severely limited in current planning tools.

  Our first contribution consists in identifying an interesting special case of WSC which is both significant and more tractable. The special case, which we term forward effects, is characterized by the fact that every ramification of a web service application involves at least one new constant generated as output by the web service. We show that, in this setting, the reasoning required for belief update simplifies to standard reasoning in the ontology itself. This relates to, and extends, current notions of "message-based" WSC, where the need for belief update is removed by a strong (often implicit or informal) assumption of "locality" of the individual messages. We clarify the computational properties of the forward effects case, and point out a strong relation to standard notions of planning under uncertainty, suggesting that effective tools for the latter can be successfully adapted to address the former.

  Furthermore, we identify a significant sub-case, named strictly forward effects, where an actual compilation into planning under uncertainty exists. This enables us to exploit off-the-shelf planning tools to solve message-based WSC in a general form that involves powerful ontologies, and requires reasoning about partial matches between concepts. We provide empirical evidence that this approach may be quite effective, using Conformant-FF as the underlying planner.

• Alexander Schimpf, Stephan Merz und Jan-Georg Smaus.
  Construction of Büchi Automata for LTL Model Checking Verified in Isabelle/HOL.
  In Stefan Berghofer and Tobias Nipkow and Christian Urban and Makarius Wenzel (Hrsg.), Proceedings of the 22nd International Conference on Theorem Proving in Higher Order Logics (TPHOLs 2009), S. 424-439. Springer-Verlag 2009.
  (Abstract einblenden) (Abstract ausblenden) (BIB)
  

  We present the implementation of a translation of LTL formulae into automata in Isabelle/HOL, which is an essential component of LTL model checking algorithms. In automaton-based model checking, we have a system modelled as a transition system and a correctness property stated as a temporal (in our case: LTL) formula. Such a formula can be translated into a (generalised) Büchi automaton that accepts precisely those behaviours allowed by the formula. Checking correctness of the system thus amounts to a language inclusion property between the two automata. We implemented a standard translation algorithm due to Gerth et al. The correctness and termination of our implementation is shown in Isabelle/HOL, and executable code is generated using the Isabelle/HOL code generator.

• Stefan Ratschan und Jan-Georg Smaus.
  Finding Errors of Hybrid Systems by Optimising an Abstraction-Based Quality Estimate.
  In Catherine Dubois (Hrsg.), Proceedings of the 3rd International Conference on Tests And Proofs (TAP 2009), S. 153-168. Springer-Verlag 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We present an algorithm for falsifying safety properties of hybrid systems, i.e., for finding a trajectory to an unsafe state. The approach is to approximate how close a point is to being an initial point of an error trajectory using a real-valued quality function, and then to use numerical optimisation to search for an optimum of this function. The function is computed by running simulations, where information coming from abstractions computed by a verification algorithm is exploited to determine whether a simulation looks promising and should be continued or cancelled. This information becomes more reliable as the abstraction becomes more refined. We thus interleave falsification and verification attempts.

• Bahareh Badban, Stefan Leue und Jan-Georg Smaus.
  Automated Invariant Generation for the Verification of Real-Time Systems.
  In Andrew Ireland and Laura Kovács (Hrsg.), Proceedings of the 2nd International Workshop on Invariant Generation (WING 2009). 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We present an approach to automatically generating invariants for timed automata models. The CIPM algorithm that we propose first computes new invariants for timed automata control locations taking their originally defined invariants as well as the constrains on clock variables imposed by incoming state transitions into account. In doing so the CIPM algorithm also prunes idle transitions, which are transitions that can never be taken, from the automaton. We discsuss a prototype implementation of the CIPM algorithm as well as some initial experimental results.

• Stefan Ratschan und Jan-Georg Smaus.
  Finding Errors of Hybrid Systems by Optimising an Abstraction-Based Quality Estimate.
  In Tarmo Uustalu and Jüri Vain (Hrsg.), Proceedings of the 20th Nordic Workshop on Programming Theory (NWPT 2008), S. 72-74. 2008.
  (PDF) (BIB)
  

• Martin Wehrle, Sebastian Kupferschmid und Andreas Podelski.
  Transition-based Directed Model Checking.
  In Stefan Kowalewski und Anna Philippou (Hrsg.), Proceedings of the 15th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2009), S. 186-200. Springer-Verlag 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Directed model checking is a well-established technique that is tailored to fast detection of system states that violate a given safety property. This is achieved by influencing the order in which states are explored during the state space traversal. The order is typically determined by an abstract distance function that estimates a state's distance to a nearest error state. In this paper, we propose a general enhancement to directed model checking based on the evaluation of state transitions. We present a schema, parametrized by an abstract distance function, to evaluate transitions and propose a new method for the state space traversal. Our framework can be applied automatically to a wide range of abstract distance functions. The empirical evaluation impressively shows its practical potential. Apparently, the new method identifies a sweet spot in the trade-off between scalability (memory consumption) and short error traces.

• Michael Brenner und Ivana Kruijff-Korbayova.
  A Continual Multiagent Planning Approach to Situated Dialogue.
  In Proceedings of the 12th Workshop on the Semantics and Pragmatics of Dialogue (LonDial 2008). 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Situated dialogue is usually tightly integrated with behavior planning, physical action and perception. This paper presents an algorithmic framework, Continual Collaborative Planning (CCP), for modeling this kind of integrated behavior and shows how CCP agents naturally blend physical and communicative actions. For experiments with conversational CCP agents we have developed MAPSIM, a software environment that can generate multiagent simulations from formal multiagent planning problems automatically. MAPSIM permits comparison of CCP-based dialogue strategies on a wide range of domains and problems without domain-specific programming. Despite their linguistic capabilities being limited MAPSIM agents can already engage in fairly realistic situated dialogues. Our ongoing work is taking this approach from simulation to real human-robot interaction.

• 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 (Hrsg.), Proceedings of the 31st Annual German Conference on Artificial Intelligence (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.

• Jan-Georg Smaus und Jörg Hoffmann.
  Relaxation Refinement: A New Method to Generate Heuristic Functions.
  In Doron Peled und Michael Wooldridge (Hrsg.), Proceedings of the 5th Workshop on Model Checking and Artificial Intelligence (MoChArt 2008), S. 147-165. 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.

• Sebastian Kupferschmid, Martin Wehrle, Bernhard Nebel und Andreas Podelski.
  Faster than Uppaal?
  In A. Gupta und S. Malik (Hrsg.), 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.

• Sebastian Kupferschmid, Jörg Hoffmann und Kim G. Larsen.
  Fast Directed Model Checking via Russian Doll Abstraction.
  In C. R. Ramakrishnan und J. Rehof (Hrsg.), 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.

• Henning Dierks, Sebastian Kupferschmid und Kim G. Larsen.
  Automatic Abstraction Refinement for Timed Automata.
  In Jean-François Raskin und P. S. Thiagarajan (Hrsg.), 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.

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

• Jan-Georg Smaus.
  On Boolean Functions Encodable as a Single Linear Pseudo-Boolean Constraint.
  In Pascal Van Hentenryck und Laurence Wolsey (Hrsg.), 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)
  

• 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 (Hrsg.), 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.

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

  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.
  

• 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 (Hrsg.), 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.

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

• 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 (Hrsg.), Proceedings of the Fifth International Conference on Computer and Games (CG 2006), S. 135-147. Springer-Verlag 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (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.

• Sebastian Kupferschmid, Jörg Hoffmann, Henning Dierks und Gerd Behrmann.
  Adapting an AI Planning Heuristic for Directed Model Checking.
  In Antti Valmari (Hrsg.), Proceedings of the 13th International SPIN Workshop on Model Checking Software (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.

• Jörg Hoffmann und Sebastian Kupferschmid.
  A Covering Problem for Hypercubes.
  In Leslie Pack Kaelbling und Alessandro Saffiotti (Hrsg.), 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.

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

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

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

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

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

• Gerhard Lakemeyer und Bernhard Nebel (Hrsg.).
  Exploring AI in the New Millenium.
  Morgan Kaufmann, San Francisco 2002.
  

• Bernhard Nebel (Hrsg.).
  Seventeenth International Joint Conference on Artificial Intelligence (IJCAI 2001).
  Morgan Kaufmann, Seattle, Washington, USA 2001.
  

• Bernhard Nebel.
  Publikationen, Zitate, Drittmittelprojekte und Promotionen an deutschen Informatikfakultäten im Spiegel des WWW.
  Informatik-Spektrum 24 (4), S. 234-249. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ) (PDF)
  

  Will man etwas über die wissenschaftliche Produktivität einer Fakultät in Erfahrung bringen, kann man Indikatoren wie Anzahl von Publikationen, aktuelle Veröffentlichungen in internationalen Fachzeitschriften, Anzahl von Zitaten, Anzahl von Promotionen und Anzahl und Umfang von Drittmittelprojekten versuchen zu bestimmen. Mittlerweile ist im World Wide Web so viel Information vorhanden, dass die Bestimmung dieser Indikatoren keinen großen Aufwand erfordert und problemlos nachvollziehbar ist. In diesem Artikel werden die Resultate einer Auswertung zur Bestimmung der Indikatoren für die deutschen Informatik-Fakultäten, -Fachbereiche und -Institute beschrieben, die auf im WWW frei zugänglichen Quellen beruht.

• Gerhard Brewka, Christopher Habel und Bernhard Nebel (Hrsg.).
  KI-97: Advances in Artificial Intelligence.
  Band 1303 von Lecture Notes in Artificial Intelligence.
  Springer-Verlag, Berlin, Heidelberg, New York 1997.
  (Abstract einblenden) (Abstract ausblenden)
  

  This volume contains the invited contributions, accepted papers and poster presentations of the 21st German Annual Intelligence Conference, KI-97, held in Freiburg, Sept. 9-12, 1997.

• Yannis Dimopoulos, Saso Dzeroski und Antonis Kakas.
  Integrating Explanatory and Descriptive Learning in ILP.
  In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI'97), S. 900-906. 1997.
  (PS.GZ)
  

• Bernhard Nebel.
  Artificial Intelligence: A Computational Perspective.
  In G. Brewka (Hrsg.), Principles of Knowledge Representation, S. 237-266. CSLI Publications 1996.
  (Abstract einblenden) (Abstract ausblenden) (PS.GZ)
  

  Although the computational perspective on cognitive tasks has always played a major role in Artificial Intelligence, the interest in the precise determination of the computational costs that are required for solving typical AI problems has grown only recently. In this paper, we will describe what insights a computational complexity analysis can provide and what methods are available to deal with the complexity problem.

• Kontakt