• English
• Deutsch

• University of Freiburg
• Faculty of Engineering
• Department of Computer Science

Publications

Complete list of publications

• sorted by year of publication
• sorted by author
• sorted by area

Recent publications (last 12 months):

(Show all abstracts) (Hide all abstracts)

• Jens Witkowski and David C. Parkes.
  A Robust Bayesian Truth Serum for Small Populations.
  In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012). 2012.
  To appear.
  (Show abstract) (Hide abstract) (PDF)
  

  Peer prediction mechanisms allow the truthful elicitation of private signals (e.g., experiences, or opinions) in regard to a true world state when this ground truth is unobservable. The original peer prediction method is incentive compatible for any number of agents n ≥ 2, but relies on a common prior, shared by all agents and the mechanism. The Bayesian Truth Serum (BTS) relaxes this assumption. While BTS still assumes that agents share a common prior, this prior need not be known to the mechanism. However, BTS is only incentive compatible for a large enough number of agents, and the particular number of agents required is uncertain because it depends on this private prior. In this paper, we present a robust BTS for the elicitation of binary information which is incentive compatible for every n ≥ 3, taking advantage of a particularity of the quadratic scoring rule. The robust BTS is the first peer prediction mechanism to provide strict incentive compatibility for every n ≥ 3 without relying on knowledge of the common prior. Moreover, and in contrast to the original BTS, our mechanism is numerically robust and ex post individually rational.

• Jens Witkowski and David C. Parkes.
  Peer Prediction without a Common Prior.
  In Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012). 2012.
  To appear.
  (Show abstract) (Hide abstract) (PDF)
  

  Reputation mechanisms at online opinion forums, such as Amazon Reviews, elicit ratings from users about their experience with different products. Crowdsourcing applications, such as image tagging on Amazon Mechanical Turk, elicit votes from users as to whether or not a job was duly completed. An important property in both settings is that the feedback received from users (agents) is truthful. The peer prediction method introduced by Miller et al. [2005] is a prominent theoretical mechanism for the truthful elicitation of reports. However, a significant obstacle to its application is that it critically depends on the assumption of a common prior amongst both the agents and the mechanism. In this paper, we develop a peer prediction mechanism for settings where the agents hold subjective and private beliefs about the state of the world and the likelihood of a positive signal given a particular state. Our shadow peer prediction mechanism exploits temporal structure in order to elicit two reports, a belief report and then a signal report, and it provides strict incentives for truthful reporting as long as the effect an agent’s signal has on her posterior belief is bounded away from zero. Alternatively, this technical requirement on beliefs can be dispensed with by a modification in which the second report is a belief report rather than a signal report.

• Andreas Hertle, Christian Dornhege, Thomas Keller and Bernhard Nebel.
  Planning with Semantic Attachments: An Object-Oriented View.
  In Proceedings of the European Conference on Artificial Intelligence (ECAI). 2012.
  To appear.
  

• Christian Becker-Asano.
  Affective Computing Combined with Android Science.
  KI - Künstliche Intelligenz Vol. 25, pp. 245-250. 2011.
  (PDF) (BIB)
  

• Jens Claßen, Gabriele Röger, Gerhard Lakemeyer and Bernhard Nebel.
  PLATAS – Integrating Planning and the Action Language Golog.
  KI – Künstliche Intelligenz 26, pp. 61-67. 2012.
  (Authors' preprint. The final publication is available at www.springerlink.com.).
  (Show abstract) (Hide abstract) (PDF)
  

  Action programming languages like Golog allow to define complex behaviors for agents on the basis of action representations in terms of expressive (first-order) logical formalisms, making them suitable for realistic scenarios of agents with only partial world knowledge. Often these scenarios include sub-tasks that require sequential planning. While in principle it is possible to express and execute such planning sub-tasks directly in Golog, the system can performance-wise not compete with state-of-the-art planners. In this paper, we report on our efforts to integrate efficient planning and expressive action programming in the Platas project. The theoretical foundation is laid by a mapping between the planning language Pddl and the Situation Calculus, which is underlying Golog, together with a study of how these formalisms relate in terms of expressivity. The practical benefit is demonstrated by an evaluation of embedding a Pddl planner into Golog, showing a drastic increase in performance while retaining the full expressiveness of Golog.

• Christian Dornhege and Alexander Kleiner.
  A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
  In Proceedings of the IEEE International Symposium on Safety, Security and Rescue Robotics (SSRR). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  We consider the problem of an autonomous robot searching for objects in unknown 3d space. Similar to the well known frontier-based exploration in 2d, the problem is to determine a minimal sequence of sensor viewpoints until the entire search space has been explored. We introduce a novel approach that combines the two concepts of voids, which are unexplored volumes in 3d, and frontiers, which are regions on the boundary between voids and explored space. Our approach has been evaluated on a mobile platform equipped with a manipulator searching for victims in a simulated USAR setup. First results indicate the real-world capability and search efficiency of the proposed method.

• Alexander Kleiner, Dali Sun and D. Meyer-Delius.
  ARMO: Adaptive Road Map Optimization for Large Robot Teams.
  In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS). 2011.
  To appear.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Autonomous robot teams that simultaneously dispatch transportation tasks are playing more and more an important role in present logistic centers and manufacturing plants. In this paper we consider the problem of robot motion planning for large robot teams in the industrial domain. We present adaptive road map optimization (ARMO) that is capable of adapting the road map in real time whenever the environment has changed. Based on linear programming, ARMO computes an optimal road map according to current environmental constraints (including human whereabouts) and the current demand for transportation tasks from loading stations in the plant. For detecting dynamic changes, the environment is describe by a grid map augmented with a hidden Markov model (HMM). We show experimentally that ARMO outperforms decoupled planning in terms of computation time and time needed for task completion.

• Alexander Kleiner, A. Kolling, K. Sycara and M. Lewis.
  Hierarchical Visibility for Guaranteed Search in Large-Scale Outdoor Terrain.
  Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS). 2011.
  To appear.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Searching for moving targets in large environments is a challenging task that is relevant in several problem domains, such as capturing an invader in a camp, guarding security facilities, and searching for victims in large-scale search and rescue scenarios. The guaranteed search problem is to coordinate the search of a team of agents to guarantee the discovery of all targets. In this paper we present a self-contained solution to this problem in 2.5D real-world domains represented by digital elevation models (DEMs). We introduce hierarchical sampling on DEMs for selecting heuristically the close to minimal set of locations from which the entire surface of the DEM can be guarded. Locations are utilized to form a search graph on which search strategies for mobile agents are computed. For these strategies schedules are derived which include agent paths that are directly executable in the terrain. Presented experimental results demonstrate the performance of the method. The practical feasibility of our approach has been validated during a field experiment at the Gascola robot training site where teams of humans equipped with iPads successfully searched for adversarial and omniscient evaders. The field demonstration is the largest-scale implementation of a guaranteed search algorithm to date.

• Q. Hamp, L. Reindl and Alexander Kleiner.
  Lessons Learned from German Research for USAR.
  In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR). 2011.
  To appear.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  We present lessons learned in USAR research within the framework of the German research project I-LOV. After three years of development first field tests have been carried out by professionals such as the Rapid Deployment Unit for Salvage Operations Abroad (SEEBA). We present results from evaluating search teams in simulated USAR scenarios equipped with newly developed technical search means and digital data input terminals developed in the I- LOV project. In particular, the bioradar, a ground-penetrating radar system for the detection of humanoid movements, a semi-active video probe for rubble pile exploration of more than 10 m length, and the decision support system FRIEDAA were evaluated and compared with conventional search methods. Results of this evaluation indicate that the developed technologies foster advantages in USAR, which are discussed in this paper.

• Alexander Kleiner, Bernhard Nebel and V.A. Ziparo.
  A Mechanism for Dynamic Ride Sharing based on Parallel Auctions.
  In Proc. of the 22th International Joint Conference on Artificial Intelligence (IJCAI). 2011.
  (to appear).
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Car pollution is one of the major causes of green- house emissions, and traffic congestion is rapidly becoming a social plague. Dynamic Ride Sharing (DRS) systems have the potential to mitigate this problem by computing plans for car drivers, e.g. commuters, allowing them to share their rides. Ex- isting efforts in DRS are suffering from the problem that participants are abandoning the system after repeatedly failing to get a shared ride. In this paper we present an incentive compatible DRS solution based on auctions. While existing DRS systems are mainly focusing on fixed assignments that minimize the totally travelled distance, the presented approach is adaptive to individual preferences of the participants. Furthermore, our system allows to tradeoff the minimization of Vehicle Kilometers Travelled (VKT) with the overall probability of successful ride-shares, which is an important feature when bootstrapping the system. To the best of our knowledge, we are the first to present a DRS solution based on auctions using a sealed-bid second price scheme.

• D. Meyer-Delius, M. Beinhofer, Alexander Kleiner and W. Burgard.
  Reducing the Ambiguity in the Environment by Placing Artificial Landmarks to Improve Mobile Robot Localization.
  In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA). 2011.
  (to appear).
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Robust and reliable localization is a fundamental prerequisite for successful robot navigation. Although there exist many solutions to the localization problem, environments can be inherently ambiguous so that different robot locations cannot to be distinguished using the sensors of the robot. This is particularly critical in comercial environments, for example in warehouses, containing long corridors and symmetric structures. This ambiguity makes localization approaches more likely to diverge or even prevent the pose of the robot from being uniquely estimated at all. In this paper we propose the utilization of artificial landmarks to reduce the inherent ambiguity in the environment, and present an efficient, localization-oriented approach to landmark placement. Our approach provides us with both the location and number of landmarks to be placed in order to improve the localization performance of the robot in a given environment. Experimental results show that by intelligently placing the landmarks we can improve the localization performance of the robot.

• Christian Becker-Asano, Dali Sun, Birgit Kleim, Corinna Scheel, Brunna Tuschen-Caffier and Bernhard Nebel.
  Outline of an Empirical Study on the Effects of Emotions on Strategic Behavior in Virtual Emergencies.
  In Affective Computing and Intelligent Interaction, pp. 508-517. 2011.
  (PDF) (BIB)
  

• Christian Becker-Asano.
  Invited Commentary: On Guiding the Design of an Ill-defined Phenomenon.
  International Journal of Synthetic Emotions Vol. 2 (2), pp. 66-67. 2011.
  (PDF) (BIB)
  

• Danijel Skocaj, Matej Kristan, Alen Vrecko, Marko Mahnic, Miroslav Janicek, Geert-Jan M. Kruijff, Marc Hanheide, Nick Hawes, Thomas Keller, Michael Zillich and 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.
  (Show abstract) (Hide abstract) (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.

• Alper Aydemir, Moritz Göbelbecker, Andrzej Pronobis, Kristoffer Sjöö and Patric Jensfelt.
  Plan-based Object Search and Exploration Using Semantic Spatial Knowledge in the Real World.
  In Proceedings of the 5th European Conference on Mobile Robotics (ECMR 2011). 2011.
  To appear.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  In this paper we present a principled planner based approach to the active visual object search problem in unknown environments. We make use of a hierarchical planner that combines the strength of decision theory and heuristics. Furthermore, our object search approach leverages on the conceptual spatial knowledge in the form of object cooccurences and semantic place categorisation. A hierarchical model for representing object locations is presented with which the planner is able to perform indirect search. Finally we present real world experiments to show the feasibility of the approach.

• Manuel Bodirsky and Stefan Wölfl.
  RCC8 is Polynomial on Networks of Bounded Treewidth.
  In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 756-761. AAAI Press 2011.
  (Show abstract) (Hide abstract) (PDF) (DBLP)
  

  We construct an homogeneous (and ω-categorical) representation of the relation algebra RCC8, which is one of the fundamental formalisms for spatial reasoning. As a consequence we obtain that the network consistency problem for RCC8 can be solved in polynomial time for networks of bounded treewidth.

• Matthias Westphal, Stefan Wölfl, Bernhard Nebel and Jochen Renz.
  On Qualitative Route Descriptions: Representation and Computational Complexity.
  In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 1120-1125. AAAI Press 2011.
  (Show abstract) (Hide abstract) (PDF) (DBLP)
  

  The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route networks with the qualitative information necessary to evaluate and optimize route descriptions with regard to ambiguities in them. We identify different agent models that differ in how agents are assumed to process route descriptions while navigating through route networks. Further, we analyze the computational complexity of matching route descriptions and paths in route networks in dependency of the agent model. Finally we empirically evaluate the influence of the agent model on the optimization and the processing of route instructions.

• Moritz Göbelbecker, Charles Gretton and Richard W. Dearden.
  A Switching Planner for Combined Task and Observation Planning.
  In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI 2011). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  From an automated planning perspective the problem of practical mobile robot control in realistic environments poses many important and contrary challenges. On the one hand, the planning process must be lightweight, robust, and timely. Over the lifetime of the robot it must always respond quickly with new plans that accommodate exogenous events, changing objectives, and the underlying unpredictability of the environment. On the other hand, in order to promote efficient behaviours the planning process must perform computationally expensive reasoning about contingencies and possible revisions of subjective beliefs according to quantitatively modelled uncertainty in acting and sensing. Towards addressing these challenges, we develop a continual planning approach that switches between using a fast satisficing ``classical'' planner, to decide on the overall strategy, and decision-theoretic planning to solve small abstract subproblems where deeper consideration of the sensing model is both practical, and can significantly impact overall performance. We evaluate our approach in large problems from a realistic robot exploration domain.

• Jens Witkowski, Sven Seuken and David C. Parkes.
  Incentive-Compatible Escrow Mechanisms.
  In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI 2011). 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  The most prominent way to establish trust between buyers and sellers on online auction sites are reputation mechanisms. Two drawbacks of this approach are the reliance on the seller being long-lived and the susceptibility to whitewashing. In this paper, we introduce so-called escrow mechanisms that avoid these problems by installing a trusted intermediary which forwards the payment to the seller only if the buyer acknowledges that the good arrived in the promised condition. We address the incentive issues that arise and design an escrow mechanism that is incentive compatible, efficient, interim individually rational and ex ante budget-balanced. In contrast to previous work on trust and reputation, our approach does not rely on knowing the sellers' cost functions or the distribution of buyer valuations.

• Moritz Göbelbecker, Alper Aydemir, Andrzej Pronobis, Kristoffer Sjöö and Patric Jensfelt.
  A Planning Approach to Active Visual Search in Large Environments.
  In Proceedings of the AAAI-11 Workshop on Automated Action Planning for Autonomous Mobile Robots (PAMR). 2011.
  Workshop version of the ECMR11 paper "Plan-based Object Search and Exploration Using Semantic Spatial Knowledge in the Real World".
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  In this paper we present a principled planner based approach to the active visual object search problem in unknown environments. We make use of a hierarchical planner that combines the strength of decision theory and heuristics. Furthermore, our object search approach leverages on the conceptual spatial knowledge in the form of object co-occurrences and semantic place categorisation. A hierarchical model for representing object locations is presented with which the planner is able to perform indirect search. Finally we present real world experiments to show the feasibility of the approach.

• Raz Nissim, Jörg Hoffmann and Malte Helmert.
  Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning.
  In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 1983-1990. 2011.
  Erratum: In Section 7, we introduce greedy bisimulation as only respecting the bisimulation property for transitions (s, l, s') where sd(s) <= sd(s'). The implementation we evaluate in Section 8 is actually even more greedy than that, only respecting transitions where sd(s) < sd(s'). Using the definition from Section 7 leads to a strategy that behaves very similarly to the strategies using regular (non-greedy) bisimulation on these benchmarks..
  (Show abstract) (Hide abstract) (PDF)
  

  A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&s yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -- not distinguishing between certain groups of operators -- without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a hybrid of two such variants is competitive with the leading heuristic LM-cut.

• Moritz Göbelbecker, Charles Gretton and Richard W. Dearden.
  A Switching Planner for Combined Task and Observation Planning.
  In Electronic Proceedings of the Workshop on Decision Making in Partially Observable, Uncertain Worlds: Exploring Insights from Multiple Communities at the Twenty-Second International Join Conference on Artificial Intelligence (DMPOUW 2011). 2011.
  Workshop version of the AAAI11 paper of the same title..
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  From an automated planning perspective the problem of practical mobile robot control in realistic environments poses many important and contrary challenges. On the one hand, the planning process must be lightweight, robust, and timely. Over the lifetime of the robot it must always respond quickly with new plans that accommodate exogenous events, changing objectives, and the underlying unpredictability of the environment. On the other hand, in order to promote efficient behaviours the planning process must perform computationally expensive reasoning about contingencies and possible revisions of subjective beliefs according to quantitatively modelled uncertainty in acting and sensing. Towards addressing these challenges, we develop a continual planning approach that switches between using a fast satisficing ``classical'' planner, to decide on the overall strategy, and decision-theoretic planning to solve small abstract subproblems where deeper consideration of the sensing model is both practical, and can significantly impact overall performance. We evaluate our approach in large problems from a realistic robot exploration domain.

• Marc Hanheide, Charles Gretton, Richard Dearden, Nick Hawes, Jeremy Wyatt, Andrzej Pronobis, Alper Aydemir, Moritz Göbelbecker and Hendrik Zender.
  Exploiting Probabilistic Knowledge under Uncertain Sensing for Efficient Robot Behaviour.
  In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011). 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Robots must perform tasks efficiently and reliably while acting under uncertainty. One way to achieve efficiency is to give the robot common-sense knowledge about the structure of the world. Reliable robot behaviour can be achieved by modelling the uncertainty in the world probabilistically. We present a robot system that combines these two approaches and demonstrate the improvements in efficiency and reliability that result. Our first contribution is a probabilistic relational model integrating common-sense knowledge about the world in general, with observations of a particular environment. Our second contribution is a continual planning system which is able to plan in the large problems posed by that model, by automatically switching between decision-theoretic and classical procedures. We evaluate our system on object search tasks in two different real-world indoor environments. By reasoning about the trade-offs between possible courses of action with different informational effects, and exploiting the cues and general structures of those environments, our robot is able to consistently demonstrate efficient and reliable goal-directed behaviour.

• Thomas Keller and Patrick Eyerich.
  A Polynomial All Outcome Determinization for Probabilistic Planning.
  In Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp and Malte Helmert (eds.), Proceedings of the 21th International Conference on Automated Planning and Scheduling (ICAPS 2011), pp. 331-334. AAAI Press 2011.
  (Show abstract) (Hide abstract) (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.

• Carmel Domshlak, Malte Helmert, Erez Karpas, Emil Keyder, Silvia Richter, Gabriele Röger, Jendrik Seipp and Matthias Westphal.
  BJOLP: The Big Joint Optimal Landmarks Planner (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, pp. 91-95. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  BJOLP, The Big Joint Optimal Landmarks Planner uses landmarks to derive an admissible heuristic, which is then used to guide a search for a cost-optimal plan. In this paper we review landmarks and describe how they can be used to derive an admissible heuristic. We conclude with presenting the BJOLP planner.

• Silvia Richter, Matthias Westphal and Malte Helmert.
  LAMA 2008 and 2011 (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, pp. 50-54. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  LAMA is a propositional planning system based on heuristic search with landmarks. This paper describes two versions of LAMA that were entered into the 2011 International Planning Competition: the original LAMA as developed for the 2008 competition and a new re-implementation of LAMA that uses the latest version of the Fast Downward Planning Framework.

  Landmarks are propositions that must be true in every solution of a planning task. LAMA uses a heuristic derived from landmarks in conjunction with the well-known FF heuristic. LAMA builds on the Fast Downward Planning System using non-binary (but finite domain) state variables and multi-heuristic search. A weighted A* search is used with iteratively decreasing weights, so that the planner continues to search for plans of better quality until the search is terminated. LAMA combines cost-to-goal and distance-to-goal estimates with the aim of finding good solutions using reasonable runtime.

• Malte Helmert and Carmel Domshlak.
  LM-Cut: Optimal Planning with the Landmark-Cut Heuristic (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, pp. 103-105. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  The LM-Cut planner uses the landmark-cut heuristic, introduced by the authors in 2009, within a standard A* progression search framework to find optimal sequential plans for STRIPS-style planning tasks. This short paper recapitulates the main ideas surrounding the landmark-cut heuristic and provides pointers for further reading.

• Raz Nissim, Jörg Hoffmann and Malte Helmert.
  The Merge-and-Shrink Planner: Bisimulation-based Abstraction for Optimal Planning (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, pp. 106-107. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  Merge-and-shrink abstraction is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. The Merge-and-shrink planner uses two different strategies for making these choices, both based on the well-known notion of bisimulation. The resulting heuristics are used in two sequential runs of A* search.

• Carmel Domshlak, Malte Helmert, Erez Karpas and Shaul Markovitch.
  The SelMax Planner: Online Learning for Speeding up Optimal Planning (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, pp. 108-112. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  The SelMax planner combines two state-of-the-art admissible heuristics using an online learning approach. In this paper we describe the online learning approach employed by SelMax, briefly review the Fast Downward framework, and describe the SelMax planner.

• Malte Helmert, Gabriele Röger, Jendrik Seipp, Erez Karpas, Jörg Hoffmann, Emil Keyder, Raz Nissim, Silvia Richter and Matthias Westphal.
  Fast Downward Stone Soup (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, pp. 38-45. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  Fast Downward Stone Soup is a sequential portfolio planner that uses various heuristics and search algorithms that have been implemented in the Fast Downward planning system.

  We present a simple general method for concocting "planner soups", sequential portfolios of planning algorithms, and describe the actual recipes used for Fast Downward Stone Soup in the sequential optimization and sequential satisficing tracks of IPC 2011.

• Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger and Jendrik Seipp.
  FD-Autotune: Automated Configuration of Fast Downward (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Deterministic Part, pp. 31-37. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  The FD-Autotune submissions for the IPC-2011 sequential tracks consist of three instantiations of the latest, highly parametric version of the Fast Downward Planning Framework. These instantiations have been automatically configured for performance on a wide range of planning domains, using the well-known ParamILS configurator. Two of the instantiations were entered into the sequential satisficing track and one into the sequential optimising track. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by state-of-the-art automated configuration procedures, and how ParamILS was then used to obtain performance-optimised configurations.

• Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger and Jendrik Seipp.
  FD-Autotune: Domain-Specific Configuration using Fast Downward (planner abstract).
  In Seventh International Planning Competition (IPC 2011), Planning and Learning Part. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  The FD-Autotune learning planning system is based on the idea of domain-specific configuration of the latest, highly parametric version of the Fast Downward Planning Framework by means of a generic automated algorithm configuration procedure. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by state-of-the-art automated configuration procedures. FD-Autotune uses the well-known ParamILS configurator and was realised using the recently developed HAL experimentation environment.

• Malte Helmert, Gabriele Röger and Erez Karpas.
  Fast Downward Stone Soup: A Baseline for Building Planner Portfolios.
  In Proceedings of the ICAPS-2011 Workshop on Planning and Learning (PAL), pp. 28-35. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  Fast Downward Stone Soup is a sequential portfolio planner that uses various heuristics and search algorithms that have been implemented in the Fast Downward planning system.

  We present a simple general method for concocting "planner soups", sequential portfolios of planning algorithms, and describe the actual recipes used for Fast Downward Stone Soup in the sequential optimization and sequential satisficing tracks of IPC 2011.

  This paper is, first and foremost, a planner description. Fast Downward Stone Soup was entered into the sequential (non-learning) tracks of IPC 2011. Due to time constraints, we did not enter it into the learning competition at IPC 2011. However, we believe that the approach might still be of interest to the planning and learning community, as it represents a baseline against which other, more sophisticated portfolio learners can be usefully compared.

• Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger and Jendrik Seipp.
  FD-Autotune: Domain-Specific Configuration using Fast Downward.
  In Proceedings of the ICAPS-2011 Workshop on Planning and Learning (PAL), pp. 13-20. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

  In this work, we present the FD-Autotune learning planning system, which is based on the idea of domain-specific configuration of the latest, highly parametric version of the Fast Downward Planning Framework by means of a generic automated algorithm configuration procedure. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by a state-of-the-art automated configuration procedure. Additionally, we give preliminary results obtained from applying our approach to the nine domains of the IPC-2011 learning track, using the well-known ParamILS configurator and the recently developed HAL experimentation environment.

• Raz Nissim, Jörg Hoffmann and Malte Helmert.
  Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning.
  In Proceedings of the ICAPS-2011 Workshop on Heuristics for Domain-independent Planning (HDIP), pp. 5-13. 2011.
  Superseded by the IJCAI 2011 paper by the same name.
  (Show abstract) (Hide abstract) (PDF)
  

  A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&s yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -- not distinguishing between certain groups of operators -- without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a hybrid of two such variants is competitive with the leading heuristic LM-cut.

• Jendrik Seipp and Malte Helmert.
  Fluent Merging for Classical Planning Problems.
  In Proceedings of the ICAPS-2011 Workshop on Knowledge Engineering for Planning and Scheduling (KEPS), pp. 47-53. 2011.
  Note: This version of the paper fixes two mistakes (in Def. 2 and in the text after Def. 3) that are present in the version of the paper that is linked from the workshop webpage..
  (Show abstract) (Hide abstract) (PDF)
  

  Fluent merging is a reformulation technique for classical planning problems that can be applied automatically or semi-automatically. The reformulation strives to transform a planning task into a representation that allows a planning algorithm to find solutions more efficiently or to find solutions of better quality. This work introduces different approaches for fluent merging and evaluates them within a state-of-the-art planning system.

• J. Benton, Patrick Eyerich and Subbarao Kambhampati.
  Enhancing Search for Satisficing Temporal Planning with Objective-driven Decisions.
  In Proceedings of the ICAPS-2011 Workshop on Heuristics for Domain-independent Planning, pp. 59-65. 2011.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Heuristic best-first search techniques have recently enjoyed ever-increasing scalability in finding satisficing solutions to a variety of automated planning problems, and temporal planning is no different. Unfortunately, achieving efficient computational performance often comes at the price of clear guidance toward solution of high quality. This fact is sharp in the case of many best-first search temporal planners, who often use a node evaluation function that is mismatched with the objective function, reducing the likelihood that plans returned will have a short makespan but increasing search performance. To help mitigate matters, we introduce a method that works to progress search on actions declared ``useful'' according to makespan, even when the original search may ignore the makespan value of search nodes. We study this method and show that it increases over all plan quality in most of the benchmark domains from the temporal track of the 2008 International Planning Competition.

• Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp and Malte Helmert (eds.).
  Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS 2011).
  AAAI Press, Menlo Park, California, USA 2011.
  

• Contact