Arbeitsgruppe Grundlagen der Künstlichen Intelligenz

[Michael Brenner]    [Markus Büttner]    [Yannis Dimopoulos]    [Christian Dornhege]    [Christoph Dornheim]    [Patrick Eyerich]    [Jens-Steffen Gutmann]    [Wolfgang Hatzack]    [Malte Helmert]    [Jörg Hoffmann]    [Alexander Kleiner]    [Jana Koehler]    [Sebastian Kupferschmid]    [Christian Köhler]    [Robert Mattmüller]    [Bernhard Nebel]    [Marco Ragni]    [Jochen Renz]    [Jussi Rintanen]    [Gabriele Röger]    [Alexander Scivos]    [Jan-Georg Smaus]    [Sebastian Trüg]    [Thilo Weigel]    [Bruno Welsch]    [Matthias Westphal]    [Stefan Wölfl]    [Dapeng Zhang]   

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

Michael Brenner

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

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

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

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

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

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

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

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

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

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

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

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

• Michael Brenner.
  A Multiagent Planning Language.
  In Workshop on PDDL (ICAPS 2003). Trento, Italy 2003.
  (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)
  

Markus Büttner

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

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

Yannis Dimopoulos

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

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

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

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

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

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

Christian Dornhege

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

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

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

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

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

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

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

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

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

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

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

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

Christoph Dornheim

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

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

Patrick Eyerich

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

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

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

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

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

Jens-Steffen Gutmann

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

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

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

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

Wolfgang Hatzack

• Wolfgang Hatzack und Bernhard Nebel.
  Solving the Operational Traffic Control Problem.
  In A. Cesta und D. Borrajo, 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.

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

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

Malte Helmert

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

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

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

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

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

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

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

• Malte Helmert und Gabriele Röger.
  How Good is Almost Perfect?
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008). AAAI Press 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

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

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

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

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

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

• Silvia Richter, Malte Helmert und Matthias Westphal.
  Landmarks Revisited.
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008). AAAI Press 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Malte Helmert.
  Decidability and Undecidability Results for Planning with Numerical State Variables.
  In M. Ghallab, J. Hertzberg und P. Traverso, 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) (PS.GZ)
  

  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.

• 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) (PS.GZ)
  

  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, Proceedings of the 6th European Conference on Planning (ECP 2001), S. 349-360. 2001.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  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.

Jörg Hoffmann

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

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

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

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

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

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

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

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

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

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

• Jörg Hoffmann.
  Local Search Topology in Planning Benchmarks: A Theoretical Analysis.
  In M. Ghallab, J. Hertzberg und P. Traverso, 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)
  

• Jörg Hoffmann und Bernhard Nebel.
  RIFO revisited: Detecting Relaxed Irrelevance.
  In A. Cesta und D. Borrajo, 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, Proceedings of the 6th European Conference on Planning (ECP 2001). 2001.
  (PS.GZ) (PDF)
  

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