uuml; ller

IJCAI Conference 2016 Conference Paper

State-Dependent Cost Partitionings for Cartesian Abstractions in Classical Planning

• Thomas Keller
• Florian Pommerening
• Jendrik Seipp
• Florian Gei
• szlig; er
• Robert Mattm
• uuml; ller

Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by distributing action costs among the heuristics. We introduce state-dependent cost partitionings which take context information of actions into account, and show that an optimal state-dependent cost partitioning dominates its state-independent counterpart. We demonstrate the potential of our idea with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it has the potential to improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning. Our empirical results give evidence that ignoring the context of actions in the computation of a cost partitioning leads to a significant loss of information.

IJCAI Conference 2016 Conference Paper

The Inconsistency in Gö del's Ontological Argument: A Success Story for AI in Metaphysics

• Christoph Benzm
• uuml; ller
• Bruno Woltzenlogel Paleo

This paper discusses the discovery of the inconsistency in Gö del's ontological argument as a success story for artificial intelligence. Despite the popularity of the argument since the appearance of Gö del's manuscript in the early 1970s, the inconsistency of the axioms used in the argument remained unnoticed until 2013, when it was detected automatically by the higher-order theorem prover Leo-II. Understanding and verifying the refutation generated by the prover turned out to be a time-consuming task. Its completion, as reported here, required the reconstruction of the refutation in the Isabelle proof assistant, and it also led to a novel and more efficient way of automating higher-order modal logic S5 with a universal accessibility relation. Furthermore, the development of an improved syntactical hiding for the utilized logic embedding technique allows the refutation to be presented in a human-friendly way, suitable for non experts in the technicalities of higher-order theorem proving. This brings us a step closer to wider adoption of logic-based artificial intelligence tools by philosophers.

IJCAI Conference 2015 Conference Paper

Delete Relaxations for Planning with State-Dependent Action Costs

• Florian Gei
• szlig; er
• Thomas Keller
• Robert Mattm
• uuml; ller

Most work in planning focuses on tasks with stateindependent or even uniform action costs. However, supporting state-dependent action costs admits a more compact representation of many tasks. We investigate how to solve such tasks using heuristic search, with a focus on delete-relaxation heuristics. We first define a generalization of the additive heuristic hadd to such tasks and then discuss different ways of computing it via compilations to tasks with state-independent action costs and more directly by modifying the relaxed planning graph. We evaluate these approaches theoretically and present an implementation of hadd for planning with state-dependent action costs. To our knowledge, this gives rise to the first approach able to handle even the hardest instances of the combinatorial ACADEMIC ADVISING domain from the International Probabilistic Planning Competition (IPPC) 2014.

IJCAI Conference 2007 Conference Paper

• Adi Botea
• Martin M
• uuml; ller
• Jonathan Schaeffer

Research on macro-operators has a long history in planning and other search applications. There has been a revival of interest in this topic, leading to systems that successfully combine macro-operators with current state-of-the-art planning approaches based on heuristic search. However, research is still necessary to make macros become a standard, widely-used enhancement of search algorithms. This article introduces sequences of macro-actions, called iterative macros. Iterative macros exhibit both the potential advantages (e. g. , travel fast towards goal) and the potential limitations (e. g. , utility problem) of classical macros, only on a much larger scale. A family of techniques are introduced to balance this trade-off in favor of faster planning. Experiments on a collection of planning benchmarks show that, when compared to low-level search and even to search with classical macro-operators, iterative macros can achieve an impressive speed-up in search.

IJCAI Conference 2007 Conference Paper

• Robert Mattm
• uuml; ller
• Jussi Rintanen

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.

IJCAI Conference 2007 Conference Paper

• Kazuki Yoshizoe
• Akihiro Kishimoto
• Martin M
• uuml; ller

Thomsen's λ search and Nagai's depth-first proof-number (DFPN) search are two powerful but very different AND/OR tree search algorithms. Lambda Depth-First Proof Number search (LDFPN) is a novel algorithm that combines ideas from both algorithms. λ search can dramatically reduce a search space by finding different levels of threat sequences. DFPN employs the notion of proof and disproof numbers to expand nodes expected to be easiest to prove or disprove. The method was shown to be effective for many games. Integrating λ order with proof and disproof numbers enables LDFPN to select moves more effectively, while preserving the efficiency of DFPN. LDFPN has been implemented for capturing problems in Go and is shown to be more efficient than DFPN and more robust than an algorithm based on classical λ search.

IJCAI Conference 2007 Conference Paper

• David Silver
• Richard Sutton
• Martin M
• uuml; ller

We explore an application to the game of Go of a reinforcement learning approach based on a linear evaluation function and large numbers of binary features. This strategy has proved effective in game playing programs and other reinforcement learning applications. We apply this strategy to Go by creating over a million features based on templates for small fragments of the board, and then use temporal difference learning and self-play. This method identifies hundreds of low level shapes with recognisable significance to expert Go players, and provides quantitive estimates of their values. We analyse the relative contributions to performance of templates of different types and sizes. Our results show that small, translation-invariant templates are surprisingly effective. We assess the performance of our program by playing against the Average Liberty Player and a variety of computer opponents on the 9x9 Computer Go Server. Our linear evaluation function appears to outperform all other static evaluation functions that do not incorporate substantial domain knowledge.

AAMAS Conference 2003 Conference Paper

Elicitation of User Preferences for Multi-attribute Negotiation

• Yutao Guo
• J
• ouml; rg P. M
• uuml; ller