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

• Thomas Keller and Malte Helmert.
  Trial-based Heuristic Tree Search for Finite Horizon MDPs.
  In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS13). 2013.
  (Show abstract) (Hide abstract) (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.

• Christian Becker-Asano, Severin Gustorff, Kai Oliver Arras, Kohei Ogawa, Shuichi Nishio, Hiroshi Ishiguro and Bernhard Nebel.
  Robot embodiment, operator modality, and social interaction in tele-existence: a project outline.
  In Proceedings of the 8th ACM/IEEE international conference on Human-robot interaction, pp. 79-80. 2013.
  

• Christian Dornhege and Alexander Kleiner.
  A Frontier-Void-Based Approach for Autonomous Exploration in 3D.
  Advanced Robotics 27 (6). 2013.
  To appear.
  

• Kai M. Wurm, Christian Dornhege, Cyrill Stachniss, Bernhard Nebel and Wolfram Burgard.
  Coordinating Heterogeneous Teams of Robots using Temporal Symbolic Planning.
  Autonomous Robots. 2013.
  To appear.
  

• Nicole C. Krämer, Stefan Kopp, Christian Becker-Asano and Nicole Sommer.
  Smile and the world will smile with you-The effects of a virtual agent's smile on users’ evaluation and behavior.
  International Journal of Human-Computer Studies 71 (3), pp. 335-349. 2012.
  

• Christian Becker-Asano and Hiroshi Ishiguro.
  Intercultural Differences in Decoding Facial Expressions of the Android Robot Geminoid F.
  Journal of Artificial Intelligence and Soft Computing Research 1 (3), pp. 215-231. 2012.
  (Show abstract) (Hide abstract)
  

  As android robots become increasingly sophisticated in their technical as well as artistic design, their non-verbal expressiveness is getting closer to that of real humans. Accordingly, this paper presents results of two online surveys designed to evaluate a female android's facial display of five basic emotions. Being interested in intercultural differences we prepared both surveys in English, German, as well as Japanese language, and we not only found that in general our design of the emotional expressions "fearful" and "surprised" (...)

• Julien Hué and Matthias Westphal.
  Revising Qualitative Constraint Network: Definition and Implementation.
  In Internation Conference on Tools for Artificial Intelligence (ICTAI), pp. 548-555. 2012.
  (Show abstract) (Hide abstract) (PDF)
  

  Qualitative Spatial and Temporal Reasoning is a central topic in Artificial Intelligence. In particular, it is aimed at application scenarios dealing with uncertain information and thus needs to be able to handle dynamic beliefs. This makes merging and revision of qualitative information important topics. While merging has been studied extensively, revision which describes what is happening when one learns new information about a static world has been overlooked. In this paper, we propose to fill the gap by providing two revision operations for qualitative calculi. In order to implement these operations, we give algo- rithms for revision and analyze the computational complexity of these problems. Finally, we present an implementation of these algorithms based on a qualitative constraint solver and provide an experimental evaluation.

• Julien Hué, Matthias Westphal and Stefan Wölfl.
  An automatic Decomposition Method for Qualitative Spatial and Temporal Reasoning.
  In Internation Conference on Tools for Artificial Intelligence (ICTAI), pp. 588-595. 2012.
  (Show abstract) (Hide abstract) (PDF)
  

  Qualitative spatial and temporal reasoning is a research field that studies relational, constraint-based formalisms for representing, and reasoning about, spatial and temporal information. The standard approach for checking consistency is based on an exhaustive representation of possible configurations between three entities, the so-called composition tables. These tables, however, encode semantic background knowledge in a redundant way, which becomes a size and efficiency issue, when the composition table needs to be grounded as done in SAT encodings of problem instances. In this paper, we present a new framework that allows for decomposing composition tables into logically simpler parts, while preserving logical equivalence, e.g., the decomposition in start- and end-points for Allen’s Interval Calculus. We show that finding such decompositions is an NP-complete problem and present a SAT-based method to generate decompositions. Finally, we discuss the impact of our decomposition method on SAT encodings of problem instances, and present a reasoning system built on decompositions that compares favorably with state-of-the-art solvers.

• Stefan Kohlbrecher, Karen Petersen, Gerald Steinbauer, Johannes Maurer, Peter Lepej, Suzana Uran, Rodrigo Ventura, Christian Dornhege, Andreas Hertle, Raymond Sheh and Johannes Pellenz.
  Community-Driven Development of Standard Software Modules for Search and Rescue Robots.
  In Safety, Security and Rescue Robotics (SSRR). 2012.
  

• Stefan Wölfl (ed.).
  Poster and Demo Track of the 35th German Conference on Artificial Intelligence (KI-2012), September 24-27, 2012, Saarbrücken, Germany.
  2012.
  (PDF)
  

• Christian Becker-Asano, Kai Oliver Arras, Bernhard Nebel and Hiroshi Ishiguro.
  The Effect of Anthropomorphism on Social Tele-Embodiment.
  In IROS 2012 Workshop on Human-Agent Interaction. 2012.
  (Show abstract) (Hide abstract)
  

  This paper outlines our approach to explore the impact of using two different robotic embodiments on an operators ability to convey emotional and conversational nonverbal signals to a distant interlocutor. Although a human's ability to produce and interpret complex, dynamic facial expressions is seen as an important factor for human-human social interaction, it remains controversial in humanoid/android robotics, whether recreating such expressiveness is really worth the technical challenge, or not. (...)

• Birgit Kleim, Thomas Ehrig, Corinna Scheel, Christian Becker-Asano, Bernhard Nebel and Brunna Tuschen-Caffier.
  Bewältigungsverhalten in Notfallsituationen aus klinisch-psychologischer Perspektive.
  Zeitschrift für Klinische Psychologie und Psychotherapie 41 (3), pp. 166-179. 2012.
  

• Corinna N. Scheel, Birgit Kleim, Julian Schmitz, Christian Becker-Asano, Dali Sun, Bernhard Nebel and Brunna Tuschen-Caffier.
  Psychophysiologische Belastungsreaktivität nach einem simulierten Feuer in einer Parkgarage.
  Zeitschrift für Klinische Psychologie und Psychotherapie 41 (3), pp. 180-189. 2012.
  

• Matthias Westphal and Julien Hué.
  Nogoods in Qualitative Constraint-based Reasoning.
  In KI 2012: Advances in Artificial Intelligence (KI 2012), pp. 180-192. Springer-Verlag 2012.
  (Authors' preprint. The final publication is available at www.springerlink.com.).
  (Show abstract) (Hide abstract) (PDF)
  

  The prevalent method of increasing reasoning efficiency in the domain of qualitative constraint-based spatial and temporal reasoning is to use domain splitting based on so-called tractable subclasses. In this paper we analyze the application of nogood learning with restarts in combination with domain splitting. Previous results on nogood recording in the constraint satisfaction field feature learnt nogoods as a global constraint that allows for enforcing generalized arc consistency. We present an extension of such a technique capable of handling domain splitting, evaluate its benefits for qualitative constraint-based reasoning, and compare it with alternative approaches.

• Stephanie Embgen, Matthias Luber, Christian Becker-Asano, Marco Ragni, Vanessa Evers and Kai Oliver Arras.
  Robot-Specific Social Cues in Emotional Body Language.
  In Proc. IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN'12), pp. 1019-1025. 2012.
  (Show abstract) (Hide abstract)
  

  Humans use very sophisticated ways of bodily emotion expression combining facial expressions, sound, gestures and full body posture. Like others, we want to apply these aspects of human communication to ease the interaction between robots and users. In doing so we believe there is a need to consider what abstraction of human social communicative behaviors is appropriate for robots. The study reported in this paper is a pilot study to not offer simulated emotion but to offer an abstracted robot version of emotion expressions (...)

• Yusra Alkhazraji, Martin Wehrle, Robert Mattmüller and Malte Helmert.
  A Stubborn Set Algorithm for Optimal Planning.
  In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012). 2012.
  To appear.
  (Show abstract) (Hide abstract) (PDF)
  

  We adapt a partial order reduction technique based on stubborn sets, originally proposed for detecting dead ends in Petri Nets, to the setting of optimal planning. We demonstrate that stubborn sets can provide significant state space reductions on standard planning benchmarks, outperforming the expansion core method.

• Patrick Eyerich.
  Preferring Properly: Increasing Coverage while Maintaining Quality in Anytime Temporal Planning.
  In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012). 2012.
  To appear.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Temporal Fast Downward (TFD) is a successful temporal planning system that is capable of dealing with numerical values. Rather than decoupling action selection from scheduling, it searches directly in the space of time-stamped states, an approach that has shown to produce plans of high quality at the price of coverage. To increase coverage, TFD incorporates deferred evaluation and preferred operators, two search techniques that usually decrease the number of heuristic calculations by a large amount. However, the current definition of preferred operators offers only limited guidance in problems where heuristic estimates are weak or where subgoals require the execution of mutex operators. In this paper, we present novel methods for refinement of this definition and show how to combine the diverse strengths of different sets of preferred operators using a restarting procedure incorporated into a multi-queue best-first search. These techniques improve TFD's coverage drastically and preserve the average solution quality, leading to a system that solves more problems than each of the competitors of the temporal satisficing track of IPC 2011 and clearly outperforms all of them in terms of IPC score.

• Johannes Löhr, Bernhard Nebel and Stefan Winkler.
  Planning Based Autonomous Lander Control.
  In Proceedings of the Astrodynamics Specialist Conference (AIAA/AAS 2012). 2012.
  (Show abstract) (Hide abstract)
  

  Safe landing of spacecraft on extraterrestrial surfaces implies a number of challenges. The main issue is to precisely initiate coasting, braking and landing maneuvers to safely land at a desired landing zone. Meanwhile, the increasing information level about the landing environment has to be processed and the landing trajectory eventually adapted in order to avoid hazardous situations. In this paper these time critical tasks are performed by Domain Predictive Control. It has been developed to guide dynamic systems into desired goal states by flexibly reordering atomic actions using planning algorithms from artificial intelligence. Here, the method is applied to autonomously adapt control commands and associated landing trajectories with respect to the changing environmental knowledge. Simulation results show the feasibility of this new approach and reveal issues which should be subject to future research.

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

• Silvan Sievers, Manuela Ortlieb and Malte Helmert.
  Efficient Implementation of Pattern Database Heuristics for Classical Planning.
  In Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS 2012), pp. 105-111. AAAI Press 2012.
  (Show abstract) (Hide abstract) (PDF)
  

  Despite their general success in the heuristic search community, pattern database (PDB) heuristics have, until very recently, not been used by the most successful classical planning systems. We describe a new efficient implementation of pattern database heuristics within the Fast Downward planner. A planning system using this implementation is competitive with the state of the art in optimal planning, significantly improving over results from the previous best PDB heuristic implementation in planning.

• Thomas Keller and Patrick Eyerich.
  PROST: Probabilistic Planning Based on UCT.
  In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012), pp. 119-127. 2012.
  (Show abstract) (Hide abstract) (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 and 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.
  (Show abstract) (Hide abstract) (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.

• Patrick Eyerich.
  Preferring Properly: Increasing Coverage while Maintaining Quality in Anytime Temporal Planning.
  In Proceedings of the ICAPS-12 Workshop on Heuristics and Search for Domain Independent Planning (HSDIP 2012). 2012.
  To appear.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Temporal Fast Downward (TFD) is a successful temporal planning system that is capable of dealing with numerical values. Rather than decoupling action selection from scheduling, it searches directly in the space of time-stamped states, an approach that has shown to produce plans of high quality at the price of coverage. To increase coverage, TFD incorporates deferred evaluation and preferred operators, two search techniques that usually decrease the number of heuristic calculations by a large amount. However, the current definition of preferred operators offers only limited guidance in problems where heuristic estimates are weak or where subgoals require the execution of mutex operators. In this paper, we present novel methods for refinement of this definition and show how to combine the diverse strengths of different sets of preferred operators using a restarting procedure incorporated into a multi-queue best-first search. These techniques improve TFD's coverage drastically and preserve the average solution quality, leading to a system that solves more problems than each of the competitors of the temporal satisficing track of IPC 2011 and clearly outperforms all of them in terms of IPC score.

• Salem Benferhat, Julien Hué, Sylvain Lagrue and Julien Rossit.
  Merging Interval-Based Possibilistic Belief Bases.
  In International Conference on Scalable Uncertainty Management (SUM), pp. 447-458. 2012.
  (Show abstract) (Hide abstract) (PDF)
  

• Julien Hué, Mariette Sérayet, Pierre Drap, Odile Papini and Eric Würbel.
  Underwater Archaeological 3D Surveys Validation within the Removed Sets Framework.
  In Benchmarks and Applications of Spatial Reasoning (BASR), pp. 39-46. 2011.
  (Show abstract) (Hide abstract) (PDF)
  

• 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.
  Supersedes the SC'11 paper "Peer Prediction with Private Beliefs".
  (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). 2012.
  (PDF) (BIB)
  

• Contact