Arbeitsgruppe Grundlagen der Künstlichen Intelligenz

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

2008

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

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

• Gabriele Röger, Malte Helmert und Bernhard Nebel.
  On the Relative Expressiveness of ADL and Golog: The Last Piece in the Puzzle.
  In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008). 2008.
  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.

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

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

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

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

2007

• Anthony G. Cohn, Christian Freksa und Bernhard Nebel.
  Spatial Cognition: Specialization and Integration.
  Technischer Bericht , Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), 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. 61-67. 2007.
  Poster.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

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

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

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

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

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

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

2006

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

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

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

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

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

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

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

2005

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

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

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

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

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

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

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

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

2004

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

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

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

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

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

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

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

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

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

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

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

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

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

2003

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

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

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

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

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.

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

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

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

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

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

2001

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

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

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

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

• 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.
  Seventeenth International Joint Conference on Artificial Intelligence (IJCAI 2001).
  Morgan Kaufmann, Seattle, Washington, USA 2001.
  

• Bernhard Nebel.
  Cooperating Physical Robots: A Lesson in Playing Robotic Soccer.
  In M. Luck, V. Marik, O. Stepankova und R. Trappl, 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.

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

• Bernhard Nebel.
  Logics for Knowledge Representation.
  In N. J. Smelser und P. B. Baltes, 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.

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

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

2000

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

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

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

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

1999

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

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

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

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

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

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

1998

• Bernhard Nebel.
  How Hard is it to Revise a Belief Base?
  In D. Dubois und H. Prade, 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.

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

• 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 und Bernhard Nebel.
  Spatial Reasoning with Topological Information.
  In C. Freksa, C. Habel und K. F. Wender, 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.

1997

• Gerhard Brewka, Christopher Habel und Bernhard Nebel.
  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, 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.

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

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