Research Group on the Foundations of Artificial Intelligence

(Show all abstracts) (Hide all abstracts)

2008

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

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

2007

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

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

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

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

• Gabriele Röger and Bernhard Nebel.
  Expressiveness of ADL and Golog: Functions Make a Difference.
  In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), pp. 1051-1056. AAAI Press 2007.
  (Show abstract) (Hide abstract) (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 and Daniele Nardi.
  RFID-Based Exploration for Large Robot Teams.
  In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2007), pp. 4606-4613. Rome, Italy 2007.
  (PDF)
  

• Sanjiang Li and Bernhard Nebel.
  Qualitative spatial representation and reasoning: A Hierarchical approach.
  The Computer Journal, pp. 391-402. 2007.
  (Show abstract) (Hide abstract)
  

  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 and Bernhard Nebel.
  Towards an Integration of Golog and Planning.
  In 20th International Joint Conference on Artificial Intelligence (IJCAI 2007). AAAI Press 2007.
  (Show abstract) (Hide abstract) (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 and 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.
  (Show abstract) (Hide abstract) (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 and 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 and Bernhard Nebel.
  Simulating spatial reasoning using ACT-R.
  In Proceedings of the Seventh International Conference on Cognitive Modeling (ICCM 2006). 2006.
  (Show abstract) (Hide abstract) (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 and 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), pp. 4054-4059. Beijing, China 2006.
  (Show abstract) (Hide abstract) (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 and D. Lundstrom.
  RoboCupRescue - Simulation League Team RescueRobots Freiburg (Germany), Team Description Paper.
  In CDROM Proceedings of the International RoboCup Symposium '05. Bremen, Germany 2006.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  A Computational Model for Spatial Reasoning with Mental Models.
  In Proceedings of the 27th Annual Cognitive Science Conference (CogSci-05). 2005.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  In Defense of Axioms in PDDL.
  Artificial Intelligence 168 (1-2), pp. 38-69. 2005.
  (Show abstract) (Hide abstract)
  

  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 and 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, pp. 335-350. Springer-Verlag 2005.
  

• Alexander Kleiner, Michael Brenner, Tobias Braeuer, Christian Dornhege, Moritz Goebelbecker, Matthias Luber, Johann Prediger, Joerg Stueckler and Bernhard Nebel.
  Successful Search and Rescue in Simulated Disaster Areas.
  In Proceedings of the International RoboCup Symposium '05. Osaka, Japan 2005.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany), Team Description Paper.
  In CDROM Proceedings of the International RoboCup Symposium '05. Osaka, Japan 2005.
  (Show abstract) (Hide abstract) (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 and 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 and Bernhard Nebel.
  The Finest of Its Class: The Natural Point-Based Ternary Calculus LR for Qualitative Spatial Reasoning.
  In Spatial Cognition IV, pp. 283-303. Springer-Verlag 2005.
  

2004

• Christian Freksa, Markus Knauff, Bernd Krieg-Brückner, Bernhard Nebel and Thomas Barkowsky.
  Spatial Cognition IV.
  Springer-Verlag, Berlin, Heidelberg, New York 2004.
  

• Thilo Weigel, Dapeng Zhang, Klaus Rechert and Bernhard Nebel.
  Adaptive Vision for Playing Table Soccer.
  In S. Biundo, T. Frühwirth and G. Palm, KI 2004: Advances in Artificial Intelligence. Proceedings of the 27th Annual German Conference on Artificial Intelligence, pp. 424-438. Springer-Verlag 2004.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Decision-Theoretic Planning for Playing Table Soccer.
  In S. Biundo, T. Frühwirth and G. Palm, KI 2004: Advances in Artificial Intelligence. Proceedings of the 27th Annual German Conference on Artificial Intelligence, pp. 213-225. Springer-Verlag 2004.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Applying Automatic Planning Techniques to Airport Ground-Traffic Control: A Feasibility Study.
  In S. Biundo, T. Frühwirth and G. Palm, KI 2004: Advances in Artificial Intelligence. Proceedings of the 27th Annual German Conference on Artificial Intelligence, pp. 183-197. Springer-Verlag 2004.
  

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

• Christian Köhler, Artur Ottlik, Hans-Hellmut Nagel and Bernhard Nebel.
  Qualitative Reasoning Feeding Back into Quantitative Model-Based Tracking.
  In Proceedings of the 16th European Conference on Artificial Intelligence (ECAI 2004), pp. 1041-1042. IOS Press 2004.
  (Show abstract) (Hide abstract) (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 and Yulia Babovitch-Lierler.
  When Are Behaviour Networks Well-Behaved?
  In Proceedings of the 16th European Conference on Artificial Intelligence (ECAI 2004), pp. 672-676. IOS Press 2004.
  (Show abstract) (Hide abstract) (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 and 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, pp. 65-75. Kaiserslautern 2004.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Künstliche Intelligenz.
  Fischer, Frankfurt/Main 2003.
  (Amazon)
  

• Reinhard Moratz, Bernhard Nebel and 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, pp. 385-400. Springer-Verlag 2003.
  

• Alankar Karol, Bernhard Nebel, Christopher Stanton and 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.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  In Defense of PDDL Axioms.
  In Proceedings of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico 2003.
  (Show abstract) (Hide abstract) (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 and 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 and Francesca Toni.
  On the Computational Complexity of Assumption-based Argumentation for Default Reasoning.
  Artificial Intelligence 141 (1-2), pp. 57-78. 2002.
  (Show abstract) (Hide abstract) (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 and 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.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Dynamic Decentralized Area Partitioning for Cooperating Cleaning Robots.
  In ICRA'02. 2002.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Towards a Life-Long Learning Soccer Agent.
  In Proceedings of the International RoboCup Symposium '02. Fukuoka, Japan 2002.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Exploring AI in the New Millenium.
  Morgan Kaufmann, San Francisco 2002.
  

• Bernhard Nebel.
  Helfer aus dem Stadion.
  Gehirn & Geist Nr. 1/2002, pp. 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 and Alexander Scivos.
  Formal Properties of Constraint Calculi for Qualitative Spatial Reasoning.
  Künstliche Intelligenz Heft 4/02, pp. 14-18. 2002.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  KiRo - An Autonomous Table Soccer Player.
  In Proceedings of the International RoboCup Symposium '02. Fukuoka, Japan 2002.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  CS Freiburg: Coordinating Robots for Successful Soccer Playing.
  IEEE Transactions on Robotics and Automation 18 (5), pp. 685-699. 2002.
  (Show abstract) (Hide abstract)
  

  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 and Bernhard Nebel.
  Solving the Operational Traffic Control Problem.
  In A. Cesta and D. Borrajo, Proceedings of the 6th European Conference on Planning (ECP 2001). 2001.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  RIFO revisited: Detecting Relaxed Irrelevance.
  In A. Cesta and D. Borrajo, Proceedings of the 6th European Conference on Planning (ECP 2001). 2001.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Cooperative Sensing in Dynamic Environments.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-2001). 2001.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  CS Freiburg: Global View by Cooperative Sensing.
  In International RoboCup Symposium 2001. 2001.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  A Fast, Accurate, and Robust Method for Self-Localization in Polygonal Environments Using Laser-Range-Finders.
  Advanced Robotics 14 (8), pp. 651-668. 2001.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  The FF Planning System: Fast Plan Generation Through Heuristic Search.
  Journal of Artificial Intelligence Research 14, pp. 253-302. 2001.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  What makes the difference between HSP and FF?
  In IJCAI Workshop on Empirical AI. Seattle 2001.
  (PS.GZ) (PDF)
  

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

• Guido Isekenmeier, Bernhard Nebel and Thilo Weigel.
  Evaluation of the Performance of CS Freiburg 1999 and CS Freiburg 2000.
  In International RoboCup Symposium 2001. 2001.
  (Show abstract) (Hide abstract) (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 and 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.
  (Show abstract) (Hide abstract) (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 and R. Trappl, Multi-Agent Systems and Applications, pp. 404-414. Springer-Verlag 2001.
  (Show abstract) (Hide abstract) (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), pp. 234-249. 2001.
  (Show abstract) (Hide abstract) (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 and P. B. Baltes, International Encyclopedia of the Social and Behavioral Sciences. Kluwer, Dordrecht 2001.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Efficient Methods for Qualitative Spatial Reasoning.
  Journal of Artificial Intelligence Research 15, pp. 289-318. 2001.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation.
  In Proc. COSIT-2001. Springer-Verlag 2001.
  (Show abstract) (Hide abstract) (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 and Maximilian Thiel.
  CS Freiburg: Doing the Right Thing in a Group.
  In P. Stone, G. Kraetzschmar and T. Balch, RoboCup 2000: Robot Soccer World Cup IV, pp. 52-63. Springer-Verlag 2001.
  (Show abstract) (Hide abstract) (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 and Boris Szerbakowski.
  CS Freiburg 2001.
  In International RoboCup Symposium 2001. 2001.
  (Show abstract) (Hide abstract) (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 and Markus Dietl.
  CS Freiburg: Sophisticated Skills and Effective Cooperation.
  In Proc. European Control Conference (ECC-01). Porto, Portugal 2001.
  (Show abstract) (Hide abstract) (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 and 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.
  (Show abstract) (Hide abstract) (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 and Thilo Weigel.
  The CS Freiburg Team: Playing Robotic Soccer Based on an Explicit World Model.
  AI Magazine 21 (1), pp. 37-46. 2000.
  (Show abstract) (Hide abstract) (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 and Christian Reetz.
  CS Freiburg: Architektur und Aktionsauswahl im Roboterfuball.
  In Proc. AMS-2000. 2000.
  (Show abstract) (Hide abstract) (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, pp. 271-315. 2000.
  (Show abstract) (Hide abstract) (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, pp. 469-490. Kluwer, Dordrecht 2000.
  (Show abstract) (Hide abstract) (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), p. 763. Berlin, Germany 2000.
  (Show abstract) (Hide abstract) (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 and Thilo Weigel.
  The CS Freiburg 2000 Team.
  In Fourth International Workshop on RoboCup. Melbourne, Australia 2000.
  (PS.GZ) (PDF)
  

1999

• Yannis Dimopoulos, Bernhard Nebel and 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.
  (Show abstract) (Hide abstract) (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 and 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.
  (Show abstract) (Hide abstract) (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 and 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, pp. 93-108. Springer-Verlag, Berlin, Heidelberg, New York 1999.
  (Show abstract) (Hide abstract) (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 and 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 and 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.
  (Show abstract) (Hide abstract) (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.
  (Show abstract) (Hide abstract) (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.
  (Show abstract) (Hide abstract) (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, pp. 12-19. 1999.
  (Show abstract) (Hide abstract) (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 and F. Keil, MIT Encyclopedia of the Cognitive Sciences. MIT Press, Cambridge, MA 1999.
  

• Bernhard Nebel, Jens-Steffen Gutmann and Wolfgang Hatzack.
  The CS Freiburg '99 Team.
  In Third International Workshop on RoboCup. 1999.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus.
  Artificial Intelligence 108 (1-2), pp. 95-149. 1999.
  (Show abstract) (Hide abstract) (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 and F Keil, MIT Encyclopedia of the Cognitive Sciences, pp. 324-325. MIT Press, Cambridge, MA 1999.
  

1998

• Bernhard Nebel.
  How Hard is it to Revise a Belief Base?
  In D. Dubois and H. Prade, Handbook of Defeasible Reasoning and Uncertainty Management Systems, pp. 77-145. Kluwer, Dordrecht, The Netherlands 1998.
  (Show abstract) (Hide abstract) (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 and Augustinus Topor.
  CS Freiburg's Participation at RoboCup'98: The World Champions in Robotic Soccer.
  AI Communications 11, pp. 243-248. 1998.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Efficient Methods for Qualitative Spatial Reasoning.
  In Proceedings of the 13th European Conference on Artificial Intelligence (ECAI'98). 1998.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Spatial Reasoning with Topological Information.
  In C. Freksa, C. Habel and K. F. Wender, Spatial Cognition - An interdisciplinary approach to representation and processing of spatial knowledge, pp. 351-372. Springer-Verlag, Berlin 1998.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  KI-97: Advances in Artificial Intelligence.
  Springer-Verlag, Berlin, Heidelberg, New York 1997.
  (Show abstract) (Hide abstract)
  

  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 and Jana Koehler.
  Encoding planning problems in non-monotonic logic programs.
  In Proc. European Conference on Planning 1997 (ECP-97), pp. 169-181. Springer-Verlag 1997.
  (Show abstract) (Hide abstract) (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 and Bernhard Nebel.
  Navigation mobiler Roboter mit Laserscans.
  In Autonome Mobile Systeme 1997 (AMS'97), pp. 36-47. Springer-Verlag 1997.
  (Show abstract) (Hide abstract) (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 and Yannis Dimopoulos.
  Extending Planning Graphs to an ADL Subset.
  In Proc. European Conference on Planning 1997 (ECP-97), pp. 273-285. Springer-Verlag 1997.
  (Show abstract) (Hide abstract) (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 and Jana Koehler.
  Ignoring Irrelevant Facts and Operators in Plan Generation.
  In Proc. European Conference on Planning 1997 (ECP-97), pp. 338-350. Springer-Verlag 1997.
  (Show abstract) (Hide abstract) (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.

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

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

• Jochen Renz and Bernhard Nebel.
  On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus.
  In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI'97), pp. 522-527. 1997.
  (Show abstract) (Hide abstract) (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.

1996

• Bernhard Nebel.
  Artificial Intelligence: A Computational Perspective.
  In G. Brewka, Principles of Knowledge Representation, pp. 237-266. CSLI Publications 1996.
  (Show abstract) (Hide abstract) (PS.GZ)
  

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

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

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

• Bernhard Nebel.
  Terminologische Logiken.
  In G. Strube, B. Becker, C. Freksa, U. Hahn, K. Opwis and G. Plam, Wörterbuch der Kognitionswissenschaft, p. 385. Klett-Cotta, Stuttgart 1996.
  

• Bernhard Nebel.
  Subsumption.
  In G. Strube, B. Becker, C. Freksa, U. Hahn, K. Opwis and G. Plam, Wörterbuch der Kognitionswissenschaft, p. 695. Klett-Cotta, Stuttgart 1996.
  

1995

• Bernhard Nebel and Hans-Jürgen Bürckert.
  Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra.
  Journal of the ACM 42, pp. 43-66. 1995.
  (Show abstract) (Hide abstract) (PS.GZ) (TAR.GZ)
  

  We introduce a new subclass o