• English
• Deutsch

• Albert-Ludwigs-Universität Freiburg
• Technische Fakultät
• Institut für Informatik

Thomas Keller – Publikationen

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

2020

• Florian Geißer, David Speck und Thomas Keller.
  Trial-based Heuristic Tree Search for MDPs with Factored Action Spaces.
  In Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020), S. 38-47. 2020.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  MDPs with factored action spaces, i.e. where actions are described as assignments to a set of action variables, allow reasoning over action variables instead of action states, yet most algorithms only consider a grounded action representation. This includes algorithms that are instantiations of the trial-based heuristic tree search (THTS) framework, such as AO* or UCT. To be able to reason over factored action spaces, we propose a generalisation of THTS where nodes that branch over all applicable actions are replaced with subtrees that consist of nodes that represent the decision for a single action variable. We show that many THTS algorithms retain their theoretical properties under the generalised framework, and show how to approximate any state-action heuristic to a heuristic for partial action assignments. This allows to guide a UCT variant that is able to create exponentially fewer nodes than the same algorithm that considers ground actions. An empirical evaluation on the benchmark set of the probabilistic track of the latest International Planning Competition validates the benefits of the approach.

2019

• Florian Geißer, David Speck und Thomas Keller.
  An Analysis of the Probabilistic Track of the IPC 2018.
  In Proceedings of the ICAPS-2019 Workshop on the International Planning Competition (WIPC 2019), S. 27-35. 2019.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The International Planning Competition 2018 consisted of several tracks on classical, temporal and probabilistic planning. In this paper, we focus on the discrete MDP track of the probabilistic portion of the competition.

  We discuss the changes to the input language RDDL, which give rise to new challenges for planning systems, and analyze each of the eight competition domains separately and highlight unique properties. We demonstrate flaws of the used evaluation criterion, the IPC score, and discuss the need for optimal upper bounds. An evaluation of the three top-performers, including their post-competition versions, and a brief analysis of their performance highlights the strengths and weaknesses of the individual approaches.

2016

• Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer und Robert Mattmüller.
  State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning (Extended Abstract).
  In Proceedings of the 39th German Conference on Artificial Intelligence (KI 2016). 2016.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by partitioning action costs among the abstractions. 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 state-dependent cost partitionings with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it can sometimes improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning.

• Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer und Robert Mattmüller.
  State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning:Full Proofs.
  Technischer Bericht CS-2016-002, University of Basel, 2016.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  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. This technical report contains the full proofs for Theorem 1, Theorem 3 and Lemma 1.

• Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer und Robert Mattmüller.
  State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning.
  In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016). 2016.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  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.

• Florian Geißer, Thomas Keller und Robert Mattmüller.
  Abstractions for Planning with State-Dependent Action Costs.
  In Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016). 2016.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  Extending the classical planning formalism with state-dependent action costs (SDAC) allows an up to exponentially more compact task encoding. Recent work proposed to use edge-valued multi-valued decision diagrams (EVMDDs) to represent cost functions, which allows to automatically detect and exhibit structure in cost functions and to make heuristic estimators accurately reflect SDAC. However, so far only the inadmissible additive heuristic has been considered in this context. In this paper, we define informative admissible abstraction heuristics which enable optimal planning with SDAC. We discuss how abstract cost values can be extracted from EVMDDs that represent concrete cost functions without adjusting them to the selected abstraction. Our theoretical analysis shows that this is efficiently possible for abstractions that are Cartesian or coarser. We adapt the counterexample-guided abstraction refinement approach to derive such abstractions. An empirical evaluation of the resulting heuristic shows that highly accurate values can be computed quickly.

2015

• Florian Geißer, Thomas Keller und Robert Mattmüller.
  Delete Relaxations for Planning with State-Dependent Action Costs.
  In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). 2015.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Most work in planning focuses on tasks with state-independent 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 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 the generalized additive heuristic 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.

• Florian Geißer, Thomas Keller und Robert Mattmüller.
  Delete Relaxations for Planning with State-Dependent Action Costs.
  In Proceedings of the 8th Annual Symposium on Combinatorial Search (SoCS 2015). 2015.
  Extended abstract of the IJCAI 2015 paper by the same name.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Supporting state-dependent action costs in planning admits a more compact representation of many tasks. We generalize the additive heuristic and compute it by embedding decision-diagram representations of action cost functions into the RPG. We give a theoretical evaluation and present an implementation of the generalized additive heuristic. This allows us to handle even the hardest instances of the combinatorial Academic Advising domain from the IPPC 2014.

• Thomas Keller und Florian Geißer.
  Better Be Lucky Than Good: Exceeding Expectations in MDP Evaluation.
  In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015). AAAI Press 2015.
  Erratum: On page 7, we mention that the results at IPPC would have differed by "-0.09", "+0.04" and "+0.05", which should read "-0.009", "+0.004" and "+0.005" instead.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  We introduce the MDP-Evaluation Stopping Problem, the optimization problem faced by participants of the International Probabilistic Planning Competition 2014 that focus on their own performance. It can be constructed as a meta-MDP where actions correspond to the application of a policy on a base-MDP, which is intractable in practice. Our theoretical analysis reveals that there are tractable special cases where the problem can be reduced to an optimal stopping problem. We derive approximate strategies of high quality by relaxing the general problem to an optimal stopping problem, and show both theoretically and experimentally that it not only pays off to pursue luck in the execution of the optimal policy, but that there are even cases where it is better to be lucky than good as the execution of a suboptimal base policy is part of an optimal strategy in the meta-MDP.

2014

• Tim Schulte und Thomas Keller.
  Balancing Exploration and Exploitation in Classical Planning.
  In Proceedings of the Seventh Annual Symposium on Combinatorial Search (SoCS 2014) (SoCS 2014). 2014.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Successful heuristic search planners for satisficing planning like FF or LAMA are usually based on one or more best first search techniques. Recent research has led to planners like Arvand, Roamer or Probe, where novel techniques like Monte-Carlo Random Walks extend the traditional exploitation-focused best first search by an exploration component. The UCT algorithm balances these contradictory incentives and has shown tremendous success in related areas of sequential decision making but has never been applied to classical planning yet. We make up for this shortcoming by applying the Trial-based Heuristic Tree Search framework to classical planning. We show how to model the best first search techniques Weighted A* and Greedy Best First Search with only three ingredients: action selection, initialization and backup function. Then we use THTS to derive four versions of the UCT algorithm that differ in the used backup functions. The experimental evaluation shows that our main algorithm, GreedyUCT*, outperforms all other algorithms presented in this paper, both in terms of coverage and quality.

• Andreas Hertle, Christian Dornhege, Thomas Keller, Robert Mattmüller, Manuela Ortlieb und Bernhard Nebel.
  An Experimental Comparison of Classical, FOND and Probabilistic Planning.
  In Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014), S. 297-308. Springer 2014.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Domain-independent planning in general is broadly applicable to a wide range of tasks. Many formalisms exist that allow to describe different aspects of realistic problems. Which one is best is not clear as usually more expressiveness comes with a cost in planning time. Under the assumption that hard guarantees are not required, users are faced with a decision between multiple approaches. In this work we study the effect of nondeterministic action outcomes. As a generic model we use a probabilistic description in the form of Markov Decision Processes (MDPs). We define abstracting translations into a classical planning formalism and fully observable nondeterministic (FOND) planning. Our goal is to give insight into how state-of-the-art systems perform on different MDP planning domains. We evaluate those MDPs by running state-of-the-art planning systems on the abstracted formalisms.

• Florian Geißer, Thomas Keller und Robert Mattmüller.
  Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games.
  In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), S. 357-362. 2014.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In General Game Playing, a player receives the rules of an unknown game and attempts to maximize his expected reward. Since 2011, the GDL-II rule language extension allows the formulation of nondeterministic and partially observable games. In this paper, we present an algorithm for such games, with a focus on the single-player case. Conceptually, at each stage, the proposed Norns algorithm distinguishes between the past, present and future steps of the game. More specifically, a belief state tree is used to simulate a potential past that leads to a present that is consistent with received observations. Unlike other related methods, our method is asymptotically optimal. Moreover, augmenting the belief state tree with iteratively improved probabilities speeds up the process over time significantly. As this allows a true picture of the present, we additionally present an optimal version of the well-known UCT algorithm for partially observable single-player games. Instead of performing hindsight optimization on a simplified, fully observable tree, the true future is simulated on an action-observation tree that takes partial observability into account. The expected reward estimates of applicable actions converge towards the true expected rewards even for moves that are only used to gather information. We prove that our algorithm is asymptotically optimal for single-player games and POMDPs and support our claim with an empirical evaluation.

2013

• Thomas Keller und Malte Helmert.
  Trial-based Heuristic Tree Search for Finite Horizon MDPs.
  In Proceedings of the 1st Multidisciplinary Conference on Reinforcement Learning and Decision Making (RLDM 2013), S. 101-105. 2013.
  Extended abstract of the ICAPS 2013 paper by the same name.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Dynamic programming is a well-known approach for solving MDPs. In large state spaces, asynchronous versions like Real-Time Dynamic Programming (RTDP) have been applied successfully. If unfolded into equivalent trees, Monte-Carlo Tree Search algorithms are a valid alternative. UCT, the most popular representative, obtains good anytime behavior by guiding the search towards promising areas of the search tree and supporting non-admissible heuristics. The global Heuristic Search algorithm AO* finds optimal solutions for MDPs that can be represented as acyclic AND/OR graphs. Despite the differences, these approaches actually have much in common. We present the Trial-based Heuristic Tree Search (THTS) framework that subsumes these approaches and distinguishes them based on only five ingredients: heuristic function, backup function, action selection, outcome selection, and trial length. We describe the ingredients that model RTDP, AO* and UCT within this framework, and use THTS to combine attributes of these algorithms step by step in order to derive novel algorithms with superior theoretical properties. We merge Full Bellman and Monte-Carlo backup functions to Partial Bellman backups, and gain a function that both allows partial updates and a procedure that labels states when they are solved. DP-UCT combines attributes and theoretical properties from RTDP and UCT even though it differs from the latter only in the used Partial Bellman backups. Our main algorithm, UCT* adds a limited trial length to DP-UCT to inherit the global search behavior of AO*, which ensures that parts of the state space that are closer to the root are investigated more thoroughly. The experimental evaluation shows that both DP-UCT and UCT* are not only superior to UCT, but also outperform P ROST, the winner of the International Probabilistic Planning Competition (IPPC) 2011 on the benchmarks of IPPC 2011.

• Thomas Keller und Malte Helmert.
  Trial-based Heuristic Tree Search for Finite Horizon MDPs.
  In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), S. 135-143. 2013.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Dynamic programming is a well-known approach for solving MDPs. In large state spaces, asynchronous versions like Real-Time Dynamic Programming have been applied successfully. If unfolded into equivalent trees, Monte-Carlo Tree Search algorithms are a valid alternative. UCT, the most popular representative, obtains good anytime behavior by guiding the search towards promising areas of the search tree. The Heuristic Search algorithm AO∗ finds optimal solutions for MDPs that can be represented as acyclic AND/OR graphs.

  We introduce a common framework, Trial-based Heuristic Tree Search, that subsumes these approaches and distinguishes them based on five ingredients: heuristic function, backup function, action selection, outcome selection, and trial length. Using this framework, we describe three new algorithms which mix these ingredients in novel ways in an attempt to combine their different strengths. Our evaluation shows that two of our algorithms not only provide superior theoretical properties to UCT, but also outperform state-of-the-art approaches experimentally.

2012

• Thomas Keller und Patrick Eyerich.
  PROST: Probabilistic Planning Based on UCT.
  In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012), S. 119-127. 2012.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We present PROST, a probabilistic planning system that is based on the UCT algorithm by Kocsis and Szepesvari (2006), which has been applied successfully to many areas of planning and acting under uncertainty. The objective of this paper is to show the application of UCT to domain-independent probabilistic planning, an area it had not been applied to before. We furthermore present several enhancements to the algorithm, including a method that is able to drastically reduce the branching factor by identifying superfluous actions. We show how search depth limitation leads to a more thoroughly investigated search space in parts that are influential on the quality of a policy, and present a sound and polynomially computable detection of reward locks, states that correspond to, e.g., dead ends or goals. We describe a general Q-value initialization for unvisited nodes in the search tree that circumvents the initial random walks inherent to UCT, and leads to a faster convergence on average. We demonstrate the significant influence of the enhancements by providing a comparison on the IPPC benchmark domains.

• Johannes Löhr, Patrick Eyerich, Thomas Keller und Bernhard Nebel.
  A Planning Based Framework for Controlling Hybrid Systems.
  In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012). 2012.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  The control of dynamic systems, which aims to minimize the deviation of state variables from reference values in a contin- uous state space, is a central domain of cybernetics and con- trol theory. The objective of action planning is to find feasible state trajectories in a discrete state space from an initial state to a state satisfying the goal conditions, which in principle ad- dresses the same issue on a more abstract level. We combine these approaches to switch between dynamic system charac- teristics on the fly, and to generate control input sequences that affect both discrete and continuous state variables. Our approach (called Domain Predictive Control) is applicable to hybrid systems with linear dynamics and discretizable inputs.

• Andreas Hertle, Christian Dornhege, Thomas Keller und Bernhard Nebel.
  Planning with Semantic Attachments: An Object-Oriented View.
  In Proceedings of the European Conference on Artificial Intelligence (ECAI). 2012.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In recent years, domain-independent planning has been applied to a rising number of real-world applications. Usually, the description language of choice is PDDL. However, PDDL is not suited to model all challenges imposed by real-world applications. Dornhege et al. proposed semantic attachments to allow the computation of Boolean fluents by external processes called modules during planning. To acquire state information from the planning system a module developer must perform manual requests through a callback interface which is both inefficient and error-prone. In this paper, we present the Object-oriented Planning Language OPL, which incorporates the structure and advantages of modern object-oriented programming languages. We demonstrate how a domain-specific module interface that allows to directly access the planner state using object member functions is automatically gen- erated from an OPL planning task. The generated domain-specific interface allows for a safe and less error-prone implementation of modules. We show experimentally that this interface is more efficient than the PDDL-based module interface of TFD/M.

2011

• Danijel Skocaj, Matej Kristan, Alen Vrecko, Marko Mahnic, Miroslav Janicek, Geert-Jan M. Kruijff, Marc Hanheide, Nick Hawes, Thomas Keller, Michael Zillich und Kai Zhou.
  A system for interactive learning in dialogue with a tutor.
  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2011). 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  In this paper we present representations and mechanisms that facilitate continuous learning of visual concepts in dialogue with a tutor and show the implemented robot system. We present how beliefs about the world are created by processing visual and linguistic information and show how they are used for planning system behaviour with the aim at satisfying its internal drive -- to extend its knowledge. The system facilitates different kinds of learning initiated by the human tutor or by the system itself. We demonstrate these principles in the case of learning about object colours and basic shapes.

• Thomas Keller und Patrick Eyerich.
  A Polynomial All Outcome Determinization for Probabilistic Planning.
  In Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp und Malte Helmert (Hrsg.), Proceedings of the 21th International Conference on Automated Planning and Scheduling (ICAPS 2011), S. 331-334. AAAI Press 2011.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Most predominant approaches in probabilistic planning utilize techniques from the more thoroughly investigated field of classical planning by determinizing the problem at hand. In this paper, we present a method to map probabilistic operators to an equivalent set of probabilistic operators in a novel normal form, requiring polynomial time and space. From this, we directly derive a determinization which can be used for, \eg, replanning strategies incorporating a classical planning system. Unlike previously described all outcome determinizations, the number of deterministic operators is not exponentially but polynomially bounded in the number of parallel probabilistic effects, enabling the use of more sophisticated determinization-based techniques in the future.

2010

• Thomas Keller, Patrick Eyerich und Bernhard Nebel.
  Task Planning for an Autonomous Service Robot.
  In Rüdiger Dillmann, Jürgen Beyerer, Uwe Hanebeck und Tanja Schultz (Hrsg.), Proceedings on the 33rd Annual German Conference on Artificial Intelligence (KI 2010), S. 358-365. Springer-Verlag 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  In the DESIRE project an autonomous robot capable of performing service tasks in a typical kitchen environment has been developed. The overall system consists of various loosely coupled subcomponents providing particular features like manipulating objects or recognizing and interacting with humans. To bring all these subcomponents together to act as monolithic system, a high-performance planning system has been implemented. In this paper, we present this system’s basic architecture and some advanced extensions necessary to cope with the various challenges arising in dynamic and uncertain environments like those a real world service robot is usually faced with.

• Patrick Eyerich, Thomas Keller und Malte Helmert.
  High-Quality Policies for the Canadian Traveler's Problem.
  In Maria Fox und David Poole (Hrsg.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010), S. 51-58. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost.

  We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.

• Patrick Eyerich, Thomas Keller und Malte Helmert.
  High-Quality Policies for the Canadian Traveler's Problem (Extended Abstract).
  In Ariel Felner und Nathan Sturtevant (Hrsg.), Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS 2010), S. 147-148. AAAI Press 2010.
  Extended abstract of the AAAI paper by the same name.
  (PDF)
  

• Moritz Göbelbecker, Thomas Keller, Patrick Eyerich, Michael Brenner und Bernhard Nebel.
  Coming Up with Good Excuses: What To Do When No Plan Can be Found.
  In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 81-88. AAAI Press 2010.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  When using a planner-based agent architecture, many things can go wrong. First and foremost, an agent might fail to execute one of the planned actions for some reasons. Even more annoying, however, is a situation where the agent is incompetent, i.e., unable to come up with a plan. This might be due to the fact that there are principal reasons that prohibit a successful plan or simply because the task's description is incomplete or incorrect. In either case, an explanation for such a failure would be very helpful. We will address this problem and provide a formalization of coming up with excuses for not being able to find a plan. Based on that, we will present an algorithm that is able to find excuses and demonstrate that such excuses can be found in practical settings in reasonable time.

• Patrick Eyerich, Thomas Keller und Malte Helmert.
  High-Quality Policies for the Canadian Traveler's Problem.
  In Proceedings of the ICAPS-2010 Workshop on Planning and Scheduling Under Uncertainty. 2010.
  Superseded by the AAAI 2010 paper by the same name.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost.

  We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.

• Patrick Eyerich, Thomas Keller und Bernhard Nebel.
  Combining Action and Motion Planning via Semantic Attachments.
  In Proceedings of the Workshop on Combining Action and Motion Planning at ICAPS 2010 (CAMP 2010), S. 19. 2010.
  Extended Abstract.
  (PDF) (BIB)
  

2009

• Christian Dornhege, Patrick Eyerich, Thomas Keller, Sebastian Trüg, Michael Brenner und Bernhard Nebel.
  Semantic Attachments for Domain-Independent Planning Systems.
  In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 114-121. AAAI Press 2009.
  (Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)
  

  Solving real-world problems using symbolic planning often requires a simplified formulation of the original problem, since certain subproblems cannot be represented at all or only in a way leading to inefficiency. For example, manipulation planning may appear as a subproblem in a robotic planning context or a packing problem can be part of a logistics task. In this paper we propose an extension of PDDL for specifying semantic attachments. This allows the evaluation of grounded predicates as well as the change of fluents by externally specified functions. Furthermore, we describe a general schema of integrating semantic attachments into a forward-chaining planner and report on our experience of adding this extension to the planners FF and Temporal Fast Downward. Finally, we present some preliminary experiments using semantic attachments.

2008

• Thomas Keller.
  Optimales domänenspezifisches Planen in der Transport- und Routenplanungsfamilie.
  Diplomarbeit, Albert-Ludwigs-Universität, Freiburg, Germany 2008.
  In German.
  (PDF)
  

• 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 (Hrsg.), Proceedings of the 31st Annual German Conference on Artificial Intelligence (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.

• Kontakt Impressum