Arbeitsgruppe Grundlagen der Künstlichen Intelligenz

Vollständige Liste der Publikationen

• sortiert nach Veröffentlichungszeitpunkt
• sortiert nach Autoren
• sortiert nach Themengebieten

Aktuelle Veröffentlichungen (letzte 12 Monate):

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

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

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

• Malte Helmert und Carmel Domshlak.
  Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?
  In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009). 2009.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

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

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

• Silvia Richter und Malte Helmert.
  Preferred Operators and Deferred Evaluation in Satisficing Planning.
  In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009). 2009.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

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

• Christoph Betz und Malte Helmert.
  Planning with h+ in Theory and Practice.
  In Proceedings of the 32nd Annual Conference on Artificial Intelligence (KI 2009). 2009.
  Accepted for publication.
  (Abstract einblenden) (Abstract ausblenden)
  

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

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

• Martin Wehrle und Malte Helmert.
  The Causal Graph Revisited for Directed Model Checking.
  In Proceedings of the 16th International Static Analysis Symposium (SAS 2009). 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Michael Brenner und Bernhard Nebel.
  Continual Planning and Acting in Dynamic Multiagent Environments.
  Journal of Autonomous Agents and Multiagent Systems. 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

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

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

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

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

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

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

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

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

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

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

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

• Armin Hornung und Dapeng Zhang.
  On-Line Detection of Rule Violations in Table Soccer.
  In Andreas R. Dengel, Karsten Berns, Thomas M. Breuel, Frank Bomarius und Thomas R. Roth-Berghofer, Proceedings of the 31st Annual German Conference on AI (KI 2008), S. 217-224. Springer-Verlag 2008.
  Poster.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  In table soccer, humans can not always thoroughly observe fast actions like rod spins and kicks. However, this is necessary in order to detect rule violations for example for tournament play. We describe an automatic system using sensors on a regular soccer table to detect rule violations in realtime. Naive Bayes is used for kick classication, the parameters are trained using supervised learning. In the on-line experiments, rule violations were detected at a higher rate than by the human players. The implementation proved its usefulness by being used by humans in real games and sets a basis for future research using probability models in table soccer.

• Thomas Keller und Sebastian Kupferschmid.
  Automatic Bidding for the Game of Skat.
  In Andreas R. Dengel, Karsten Berns, Thomas M. Breuel, Frank Bomarius und Thomas R. Roth-Berghofer, Proceedings of the 31st Annual German Conference on AI (KI 2008), S. 95-102. Springer-Verlag 2008.
  (Abstract einblenden) (Abstract ausblenden) (BIB) (PDF)
  

  In recent years, researchers started to study the game of Skat. The strength of existing Skat playing programs is definitely the card play phase. The bidding phase, however, was treated quite poorly so far. This is a severe drawback since bidding abilities influence the overall playing performance drastically. In this paper we present a powerful bidding engine which is based on a k-nearest neighbor algorithm.

• Dapeng Zhang und Armin Hornung.
  A Table Soccer Game Recorder.
  In Video Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2008). Nice, France 2008.
  Digest and Video.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (PS.GZ)
  

  Our table soccer robot can already challenge even professional human players. Next, the robot should play games by using human-like skills. As a foundation of this research, our table soccer game recorder can save and replay games played by humans. This video shows the construction and functionality of the recording system.

  We use three types of sensors mounted on a regular game table. The movement of a game rod is measured by an optical distance sensor. Its turning is observed by a magnetic rotary encoder. Two laser measurement systems are synchronized to determine the position of the ball. The raw sensor data is smoothed by an approach using multi-model Kalman filter. We developed several software modules for the system. The modules provide a basis for the future research.

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

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

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

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

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

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

• Jussi Rintanen, Bernhard Nebel, J. Christopher Beck und Eric Hansen.
  Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008).
  AAAI Press, Menlo Park, California USA 2008.
  

• Martin Wehrle, Sebastian Kupferschmid und Andreas Podelski.
  Useless Actions are Useful.
  In Jussi Rintanen, Bernhard Nebel, J. Christopher Beck und Eric Hansen, Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008), S. 388-395. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Planning as heuristic search is a powerful approach to solving domain independent planning problems. In recent years, various successful heuristics and planners like FF, LPG, Fast Downward or SGPlan have been proposed in this context. However, as heuristics only estimate the distance to goal states, a general problem of heuristic search is the existence of plateaus in the search space topology which can cause the search process to degenerate. Additional techniques like helpful actions or preferred operators that evaluate the "usefulness" of actions are often successful strategies to support the search in such situations.

  In this paper, we introduce a general method to evaluate the usefulness of actions. We propose a technique to enhance heuristic search by identifying "useless" actions that are not needed to find optimal plans. In contrast to helpful actions or preferred operators that are specific to the FF and Causal Graph heuristic, respectively, our method can be combined with arbitrary heuristics. We show that this technique often yields significant performance improvements.

• Malte Helmert und Héctor Geffner.
  Unifying the Causal Graph and Additive Heuristics.
  In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008), S. 140-147. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

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

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

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

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

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

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

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

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

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

• Jan-Georg Smaus und Jörg Hoffmann.
  Relaxation Refinement: A New Method to Generate Heuristic Functions.
  In Doron Peled und Michael Wooldridge, Proceedings of the 5th Workshop on Model Checking and Artificial Intelligence (MoChArt 2008), S. 147-165. Springer-Verlag 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In artificial intelligence, a relaxation of a problem is an overapproximation whose solution in every state of an explicit search provides a heuristic solution distance estimate. The heuristic guides the exploration, potentially shortening the search by exponentially many search states. The big question is how a good relaxation for the problem at hand should be derived. In model checking, overapproximations are called abstractions, and abstraction refinement is a powerful method developed to derive approximations that are sufficiently precise for verifying the system at hand. In our work, we bring these two paradigms together. We pioneer the application of (predicate) abstraction refinement for the generation of heuristic functions that are intelligently adapted to the problem at hand. We investigate how an abstraction refinement process for generating heuristic functions should differ from the process used in the verification context. We do so in the context of DMC of timed automata. We obtain a variety of interesting insights about this approach.

• Pascal Bercher und Robert Mattmüller.
  A Planning Graph Heuristic for Forward-Chaining Adversarial Planning.
  In Proceedings of the 18th European Conference on Artificial Intelligence (ECAI 2008). IOS Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (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.

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

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

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

• Matthias Westphal und Stefan Wölfl.
  Bipath Consistency Revisited.
  In Proceedings of the ECAI'08 Workshop on Spatial and Temporal Reasoning. Patras, Greece 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  In the field of qualitative spatial and temporal reasoning combinations of constraint calculi have attracted considerable research interest in recent years. Beside combinations of spatial and temporal calculi, it is an important research topic to develop generic methods for combining calculi dealing with different spatial aspects. The prototypical example is the combination of the region connection calculus RCC8 and the point algebra first discussed by Gerevini and Renz, which allows to represent, and reason about, topological and size information about spatially extended objects. To solve constraints in this calculus, Gerevini and Renz also proposed an algorithm, the bipath consistency algorithm, which allows for deciding consistency of a given constraint network for specific sets of relations combining topology and size. In this article we will compare the "bipath consistency"-based combination method to the standard method, which is to combine calculi by generating a new calculus and applying the standard path consistency method. Gerevini and Renz's calculus combining topological and size information will serve as the running example of such combinations and also as a test case for an empirical analysis.

• Zeno Gantner, Matthias Westphal und Stefan Wölfl.
  GQR - A Fast Reasoner for Binary Qualitative Constraint Calculi.
  In Proceedings of the AAAI'08 Workshop on Spatial and Temporal Reasoning. Chicago, USA 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  GQR (Generic Qualitative Reasoner) is a solver for binary qualitative constraint networks. GQR takes a calculus description and one or more constraint networks as input, and tries to solve the networks using the path consistency method and (heuristic) backtracking. In contrast to specialized reasoners, it offers reasoning services for different qualitative calculi, which means that these calculi are not hard-coded into the reasoner. Currently, GQR supports arbitrary binary constraint calculi developed for spatial and temporal reasoning, such as calculi from the RCC family, the intersection calculi, Allen's interval algebra, cardinal direction calculi, and calculi from the OPRA family. New calculi can be added to the system by specifications in a simple text format or in an XML file format. The tool is designed and implemented with genericity and extensibility in mind, while preserving efficiency and scalability. The user can choose between different data structures and heuristics, and new ones can be easily added to the object-oriented framework. GQR is free software distributed under the terms of the GNU General Public License.

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

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

• Malte Helmert und Gabriele Röger.
  How Good is Almost Perfect?
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 944-949. AAAI Press 2008.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)
  

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

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

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

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

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

• Silvia Richter, Malte Helmert und Matthias Westphal.
  Landmarks Revisited.
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 975-982. AAAI Press 2008.
  Note: After publication, we found a bug in our implementation that affects the results in the columns "CG heuristic/local" and "blind heuristic/local" of Table 1. The version of the paper available for download here corrects these errors.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)
  

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

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

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