Research Group on the Foundations of Artificial Intelligence

[AI Planning]    [Knowledge Representation]    [Robotics]    [Other]   

(Show all abstracts) (Hide all abstracts)

AI Planning

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

• Gabriele Röger, Malte Helmert and 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.
  (Show abstract) (Hide abstract) (PDF)
  

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

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

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

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

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

• Pascal Bercher and Robert Mattmüller.
  A Planning Graph Heuristic for Forward-Chaining Adversarial Planning.
  In Proceedings of the 18th European Conference on Artificial Intelligence (ECAI 2008). IOS Press 2008.
  To appear.
  (Show abstract) (Hide abstract) (PDF)
  

  In contrast to classical planning, in adversarial planning, the planning agent has to face an adversary trying to prevent him from reaching his goals. In this paper, we investigate a forward-chaining approach to adversarial planning based on the AO* algorithm. The exploration of the underlying AND/OR graph is guided by a heuristic evaluation function, inspired by the relaxed planning graph heuristic used in the FF planner. Unlike FF, our heuristic uses an adversarial planning graph with distinct proposition and action layers for the protagonist and antagonist. First results suggest that in certain planning domains, our approach yields results competitive with the state of the art.

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

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

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

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

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

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

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

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

• Silvia Richter, Malte Helmert and Matthias Westphal.
  Landmarks Revisited.
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008). AAAI Press 2008.
  To appear.
  (Show abstract) (Hide abstract) (PDF)
  

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

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

• Malte Helmert, Patrik Haslum and Jörg Hoffmann.
  Flexible Abstraction Heuristics for Optimal Sequential Planning.
  In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007), pp. 176-183. AAAI Press 2007.
  (Show abstract) (Hide abstract) (PDF)
  

  We describe an approach to deriving consistent heuristics for automated planning, based on explicit search in abstract state spaces. The key to managing complexity is interleaving composition of abstractions over different sets of state variables with abstraction of the partial composites.

  The approach is very general and can be instantiated in many different ways by following different abstraction strategies. In particular, the technique subsumes planning with pattern databases as a special case. Moreover, with suitable abstraction strategies it is possible to derive perfect heuristics in a number of classical benchmark domains, thus allowing their optimal solution in polynomial time.

  To evaluate the practical usefulness of the approach, we perform empirical experiments with one particular abstraction strategy. Our results show that the approach is competitive with the state of the art.

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

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

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

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

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

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

• Robert Mattmüller and Jussi Rintanen.
  Planning for Temporally Extended Goals as Propositional Satisfiability.
  In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 1966-1971. 2007.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

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

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

• Malte Helmert, Robert Mattmüller and Gabriele Röger.
  Approximation Properties of Planning Benchmarks.
  In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), pp. 585-589. 2006.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

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

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

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

• Malte Helmert.
  The Fast Downward Planning System.
  Journal of Artificial Intelligence Research 26, pp. 191-246. 2006.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Malte Helmert.
  Complexity results for standard benchmark domains in planning.
  Artificial Intelligence 143 (2), pp. 219-262. 2003.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

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

  In this contribution, we try to remedy this fact by providing a map of the computational complexity of non-optimal and optimal planning for the set of domains used in the competitions. We identify a common transportation theme shared by the majority of the benchmarks and use this observation to define and analyze a general transportation problem that generalizes planning in several classical domains such as LOGISTICS, MYSTERY and GRIPPER. We then apply the results of that analysis to the actual transportation domains from the competitions. We next examine the remaining benchmarks, which do not exhibit a strong transportation feature, namely SCHEDULE and FREECELL.

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

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

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

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

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

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

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

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

• Sylvie Thiebaux, Jörg Hoffmann 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)
  

• Malte Helmert.
  Decidability and Undecidability Results for Planning with Numerical State Variables.
  In M. Ghallab, J. Hertzberg and P. Traverso, Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002), pp. 303-312. AAAI Press 2002.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

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

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

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

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

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

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

• Stefan Edelkamp and Malte Helmert.
  The Model Checking Integrated Planning System (MIPS).
  AI Magazine 22 (3), pp. 67-71. 2001.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

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

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

• Malte Helmert.
  On the Complexity of Planning in Transportation Domains.
  In A. Cesta and D. Borrajo, Proceedings of the 6th European Conference on Planning (ECP 2001), pp. 349-360. 2001.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

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

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

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

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

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

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

• 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.
  Local Search Topology in Planning Benchmarks: An Empirical Analysis.
  In Proceedings of the 17th International Joint Conference on Artificial Intelligence. Seattle, Washington, USA 2001.
  (PS.GZ) (PDF)
  

• Jörg Hoffmann 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)
  

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

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

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

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

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

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

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

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

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

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

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

• Bernhard Nebel.
  Compilation Schemes: A Theoretical Tool for Assessing the Expressive Power of Planning Formalisms.
  In KI-99: Advances in Artificial Intelligence. Springer-Verlag, Bonn 1999.
  (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.

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

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

• Yannis Dimopoulos, Bernhard Nebel 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.

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

Knowledge Representation

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

• Gabriele Röger, Malte Helmert and 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.
  (Show abstract) (Hide abstract) (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.

• Marco Ragni, Stefan Schleipen and Felix Steffenhagen.
  Solving proportional analogies: A computational model.
  In Proceedings of AnICA 2007. 2007.
  

• Marco Ragni.
  Deductive Spatial Reasoning: A Computational and Cognitive Perspective.
  KI Themenheft Spatial Reasoning. 2007.
  

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

• Stefan Schleipen, Marco Ragni and Thomas Fangmeier.
  Negation in Spatial Reasoning: A Computational Approach.
  In Proceedings of the 30th Annual German Conference on Artificial Intelligence (KI 2007), pp. 175-189. 2007.
  

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

• Marco Ragni, Thomas Fangmeier and Stefan Schleipen.
  What about negation in spatial reasoning?
  In Proceedings of the 29th Annual Cognitive Science Conference (CogSci 2007). Lawrence Erlbaum Associates 2007.
  

• Marco Ragni and Felix Steffenhagen.
  Qualitative spatial reasoning: A cognitive and computational approach.
  In Proceedings of the 29th Annual Cognitive Science Conference (CogSci 2007). Lawrence Erlbaum Associates 2007.
  

• Stefan Wölfl, Till Mossakowski and Lutz Schröder.
  Qualitative constraint calculi: Heterogeneous verification of composition tables.
  In Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2007), pp. 665-670. AAAI Press 2007.
  

• Frank Dylla, Lutz Frommberger, Jan Oliver Wallgrün, Diedrich Wolter, Berhard Nebel and Stefan Wölfl.
  SailAway: Formalizing navigation rules.
  In Proceedings of the Artificial and Ambient Intelligence Symposium on Spatial Reasoning and Communication (AISB 2007). 2007.
  

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

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

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

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

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

• Patrick Eyerich, Bernhard Nebel, Gerhard Lakemeyer 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.

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

• Jona Boeddinghaus, Marco Ragni, Markus Knauff 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.

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

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

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

• Marco Ragni, Markus Knauff 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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