Sym-k is a state-of-the-art top-k planner. The objective of top-k planning is to determine a set of k different plans with lowest cost for a given planning task.

Main source:

• Speck, D.; Mattmüller, R.; and Nebel, B. 2020. Symbolic top-k planning. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), S. 9967-9974. AAAI Press. (pdf)

@InProceedings{speck-et-al-aaai2020,
  author =       "David Speck and Robert Mattm{\"u}ller and Bernhard Nebel",
  title =        "Symbolic Top-k Planning",
  editor =       "Vincent Conitzer and Fei Sha",
  booktitle =    "Proceedings of the Thirty-Fourth {AAAI} Conference on
                  Artificial Intelligence ({AAAI} 2020)",
  publisher =    "{AAAI} Press",
  year =         "2020",
  pages =        "9967--9974"
}

Based on:

• Fast Downward: http://www.fast-downward.org/ (22.06)
• Symbolic Fast Downward: https://people.cs.aau.dk/~alto/software.html

Currently we only support Linux systems. The following should install all necessary dependencies.

$ sudo apt-get -y install cmake g++ make python3 autoconf automake

Sym-k should compile on MacOS with the GNU C++ compiler and clang with the same instructions described above.

$ ./build.py 

We recommend to use the following configuration which uses bidirectional search.

$ ./fast-downward.py domain.pddl problem.pddl --search "sym-bd()"

Other configurations are forward or backward search: --search "symk-fw()" or --search "symk-bw()".

We recommend to use the following configuration which uses bidirectional search and reports the best k plans. Note that you can also specify num_plans=infinity if you want to find all possible plans.

$ ./fast-downward.py domain.pddl problem.pddl --search "symk-bd(plan_selection=top_k(num_plans=**k**))"

We recommend to use the following configuration which uses bidirectional search and reports the k plans with quality bound q. Quality 1<=q<=infinity is a multiplier that is multiplied to the cost of the cheapest solution. For example, q=1 reports only the cheapest plans, where quality=infinity corresponds to the top-k planning.

$ ./fast-downward.py domain.pddl problem.pddl --search "symq-bd(plan_selection=top_k(num_plans=**k**),quality=**q**)"

It is possible to generate loopless/simple plans, i.e., plans that do not visit any state more than once. In general, the option to consider and generate only simple plans can be combined with any Sym-k search engine and with different plan selectors by setting the simple parameter to true. See the following two examples and our ICAPS 2022 Paper.

$ ./fast-downward.py domain.pddl problem.pddl --search "symk-bd(simple=true,plan_selection=top_k(num_plans=**k**))"

$ ./fast-downward.py domain.pddl problem.pddl --search "symq-bd(simple=true,plan_selection=top_k(num_plans=**k**),quality=**q**)"

By default, the planner performs a relevance analysis and removes components such as variables and actions that are irrelevant to achieving the goal. Although such variables and actions can in principle lead to further (simple) plans, they are classified as irrelevant and removed when translating PDDL to SAS+. If you wish to obtain all plans (even the non-relevant ones), please use the following options:

$ ./fast-downward.py --translate --search domain.pddl problem.pddl --translate-options --keep-unimportant-variables --search-options --search "symk-bd(plan_selection=top_k(num_plans=**k**))

It is possible to run sym-k also with forward or backward search instead of bidirectional search, e.g., with --search "symk-fw(...)" or --search "symk-bw(...)". Depending on the domain, one of these configurations may be faster than bidirectional search ("--search symk-bd(...)").

It is possible to create plans until a number of plans or simply a single plan is found that meets certain requirements. For this purpose it is possible to write your own plan selector. During the search, plans are created and handed over to a plan selector with an anytime behavior.

An example of a plan selector is the unordered_selector, which considers two plans as equivalent if their action multi-sets are equivalent. In other words, plans with the same multi-set of actions form an equivalence class and only one representative plan is reported for each equivalence class. Note that plan selectors can be combined with the different planning configurations.

We recommend to use the following configurations which use bidirectional search.

$ ./fast-downward.py domain.pddl problem.pddl --search "symk-bd(plan_selection=unordered(num_plans=**k**))"

$ ./fast-downward.py domain.pddl problem.pddl --search "symq-bd(plan_selection=unordered(num_plans=**k**),quality=**q**)"

Two simple examples of plan selectors are the top_k_selector and the top_k_even_selector. For this purpose it is possible to write your own plan selector. The most important function is add_plan, in which you can specify whether a newly generated plan shall be accepted or rejected. To create your own plan selector, you can copy the .cc and .h files of one of these two selectors and adjust them accordingly. Also add the new file name to DownwardFiles.cmake, similar to the other selection files. Finally, if you want to find a plan with your awesome_selector selector (the name of the selector you specified for the plugin in the .cc file), you can use the following command.

$ ./fast-downward.py domain.pddl problem.pddl --search "symk-bd(plan_selection=awesome_selector(num_plans=1))"

Note, that you can also search for the best k plans using your selector.