• English
• Deutsch

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

Yusra Alkhazraji – Publications

(Show all abstracts) (Hide all abstracts)

2016

• Dr. Yusra Alkhazraji and Martin Wehrle.
  Sleep Sets Meet Duplicate Elimination.
  In Proceedings of the Ninth Annual Symposium on Combinatorial Search (SoCS 2016) (SoCS 2016). 2016.
  (Show abstract) (Hide abstract) (PDF)
  

  The sleep sets technique is a path-dependent pruning method for state space search. In the past, the combination of sleep sets with graph search algorithms that perform duplicate elimination has often shown to be error-prone. In this paper, we provide the theoretical basis for the integration of sleep sets with common search algorithms in AI that perform duplicate elimination. Specifically, we investigate approaches to safely integrate sleep sets with optimal (best-first) search algorithms. Based on this theory, we provide an initial step towards integrating sleep sets within A* and additional state pruning techniques like strong stubborn sets. Our experiments show slight, yet consistent improvements on the number of generated search nodes across a large number of standard domains from the international planning competitions.

• Jendrik Seipp, Florian Pommerening, Silvan Sievers, Martin Wehrle, Chris Fawcett and Dr. Yusra Alkhazraji.
  Fast Downward Aidos (planner abstract).
  In the 1st Unsolvability International Planning Competition (IPC 2016). 2016.
  (Show abstract) (Hide abstract) (PDF)
  

  This paper describes the three Fast Downward Aidos portfolios we submitted to the Unsolvability International Planning Competition 2016. All three Aidos variants are implemented in the Fast Downward planning system (Helmert2006). We use a pool of techniques as a basis for our portfolios, including various techniques already implemented Fast Downward, as well as three newly developed techniques to prove unsolvability. We used automatic algorithm configuration to find a good Fast Downward configuration for each of a set of test domains and used the resulting data to select the components, their order and their time slices for our three portfolios. For Aidos 1 and 2 we made this selection manually, resulting in two portfolios comprised mostly of the three new techniques. Aidos 1 distributes the 30 minutes based on our experiments, while Aidos 2 distributes the time uniformly. Aidos 3 contains unmodified configurations from the tuning process with time slices automatically optimized for the number of solved instances per time. It is based both on the new and existing Fast Downward components. The remainder of this planner abstract is organized as follows. First, we describe the three newly developed techniques. Second, we list the previously existing components of Fast Downward that we have used for configuration. Third, we describe the benchmarks used for training and test sets. Fourth, we describe the algorithm configuration process in more detail. Finally, we briefly describe the resulting portfolios.

2015

• Robert C. Holte, Dr. Yusra Alkhazraji and Martin Wehrle.
  A Generalization of Sleep Sets Based on Operator Sequence Redundancy.
  In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015). AAAI Press 2015.
  (Show abstract) (Hide abstract) (PDF)
  

  Pruning techniques have recently been shown to speed up search algorithms by reducing the branching factor of large search spaces. One such technique is sleep sets, which were originally introduced as a pruning technique for model checking, and which have recently been investigated on a theoretical level for planning. In this paper, we propose a generalization of sleep sets and prove its correctness. While the original sleep sets were based on the commutativity of operators, generalized sleep sets are based on a more general notion of operator sequence redundancy. As a result, our approach dominates the original sleep sets variant in terms of pruning power. On a practical level, our experimental evaluation shows the potential of sleep sets and their generalizations on a large and common set of planning benchmarks.

2014

• Dr. Yusra Alkhazraji, Michael Katz, Robert Mattmüller, Florian Pommerening, Alexander Shleyfman and Martin Wehrle.
  Metis: Arming Fast Downward with Pruning and Incremental Computation (planner abstract).
  In the 8th International Planning Competition (IPC 2014) (deterministic track). 2014.
  (Show abstract) (Hide abstract) (PDF)
  

  Metis is a sequential optimal planner that implements three components on top of the Fast Downward planning system (Helmert 2006). The planner performs an A ∗ search using the following three major components: • an admissible incremental LM-cut heuristic (Pommeren- ing and Helmert 2013), • a symmetry based pruning technique (Domshlak, Katz, and Shleyfman 2012), and • a partial order reduction based pruning technique based on strong stubborn sets (Wehrle and Helmert 2012). Each of those techniques was extended to support conditional effects. In addition, Metis features a flexible invocation of partial order reduction based pruning. In what follows, we describe each of these components in detail.

2013

• Martin Wehrle, Malte Helmert, Dr. Yusra Alkhazraji and Robert Mattmüller.
  The Relative Pruning Power of Strong Stubborn Sets and Expansion Core.
  In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS13). 2013.
  (Show abstract) (Hide abstract) (PDF)
  

  In the last years, pruning techniques based on partial order reduction have found increasing attention in the planning community. One recent result is that the expansion core method is a special case of the strong stubborn sets method proposed in model checking. However, it is still an open question if there exist efficiently computable strong stubborn sets with strictly higher pruning power than expansion core. In this paper, we prove that the pruning power of strong stubborn sets is strictly higher than the pruning power of expansion core even for a straight-forward instantiation of strong stubborn sets. This instantiation is as efficiently computable as expansion core. Hence, our theoretical results suggest that strong stubborn sets should be preferred to expansion core. Our empirical evaluation on all optimal benchmarks from the international planning competitions up to 2011 supports the theoretical results.

2012

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

• Contact Legal Information