Experimental Setup for the IJCAI 2024 Paper: "Laying the Foundations for Solving FOND HTN Problems: Grounding, Search, Heuristics (and Benchmark Problems)"
Creators: name: Yousefi, Mohammad
name: Bercher, Pascal
Publisher: name: Zenodo
Year: 2024

description: Introduction

A snapshot of the Koala planning software, FOND domains, and additional scripts. We strongly suggest using the main repository on Github (link) for all planning purposes.

Build Instructions

The repository contains a single ZIP file, download and extract it. You should see the following structure.



domains: Contains 7 subfolder, each of which is a FOND HTN domain. The domains originally appeared in IPC 2020 (HTN Track). Our modifications are discussed in "mainfile-supp.pdf".

parser: This folder contains the parser for the extended HDDL language, which is a modified version of the PandaPI parser. In order to compile the source code you need to do the following steps (taken from the original PandaPIParser Git repository). Furthermore, we have included our compiled verion, but it may not run on your specific operating system.



Make sure g++, make, flex, and bison are installed on your system.

Run make -j to create the executable pandaPIparser

Invoke the executable with two arguements: a domain, and a problem instance. For example, suppose domain.hddl and problem.hddl are placed right next to the executable. To get a parsed version in terminal, run ./pandaPIParser domain.hddl problem.hddl



grounder: This is unchanged version of the PandaPIGrounder that we have used as our oracle for grounding. In order to compile the source code you need to do execute the following instructions line by line (taken from the original PandaPIGrounder Git repository). Furthermore, we have included our compiled verion, but it may not run on your specific operating system.

cd grounder
git submodule init
git submodule update
cd cpddl
git apply ../0002-makefile.patch
make boruvka opts bliss lpsolve
make
cd ../src
make
This will create the executable pandaPIgrounder which you can call with two arguments: the result of the parser, and a file name to write the result. For example, suppose the parsed result is saved in a file named result.htn , placed next to the executable. And, you want the output to be saved in a new file named grounded.sas+ . Run ./pandaPIgrounder result.htn grounded.sas+

serializer: This folder corresponds to Alg. 1 in our paper. It takes the result of the grounder, and re-infer an over-approximation of the original grounding. Furthermore, it also outputs the result as a JSON file to be parsed by our planner. In order to run this procedure on a grounded representation of the problem, saved in grounded.sas+ , you first need to make sure python3 is installed on your operating system, and then run python3 htn_parser.py grounded.sas+ output.json 

planner: This section corresponds to Alg. 2 in our paper, and is an implementation of the AO* algorithm, along with all of the code to support it. in order to compile the planner, you need to install Rust (and Cargo). Then, run the following command: cargo build --release to get the executable file in /target/release. Then, you need to pass the JSON file created in the previous step to the planner. The structure of the subfolders is as follows.



domain_description: This is the internal representation of the domain and the problem in our planner. The two folders correspond to HTN planning domain/problem representation, and its classical counterpart (used as a relaxarion).

graph_lib: This folder contains an implementation of the graph data structure, and functions over it. This serves as the backbone of the HTN data structure.

heuristics: As the name implies, this folder includes the implementation of heuristics.

relaxation: This folder provides the two relaxations that we have used to get a poly-time heuristic. The first one is an implementation of the RC relaxation (article), and the second one is the proposed all-outcome-determinization (section 3 of our paper).

search: This is the main search algorithm (AO*). Supported heuristics are represented as an enum in h_type.rs

task_network: This folder contains the internal representation of task networks.



results: This folder corresponds to section 7 in our paper, and contains our experimental results. Notice that there are non-deterministic decision points in the algorithm (notably, the random tie-breaking strategy when nodes have similar f-values). Thus, each run of the algorithm may result in a slightly different outcome. We have included the results that we obtained for completeness, but also suggest using statistical measures, as opposed to relying on individual data points, to assess the correctness. 

solve.py: This is a python script that glue together the steps that we mentioned, and performs a complete run from parsing to the result for one single domain and problem file. In order to run this script you need python3. Example usage: python3 solve.py domain.hddl problem.hddl . Notably, the 30-min timeout is forced in this script.

batch_solve.py: This script builds upon solve.py to solve a batch of problem instances in one domain. It takes as input a folder that must contain a domain.hddl file. The rest of the files in that folder are treated as problem instances. This script forces at most 8GB memory usage, regardless of the available memory.

readme.md: A summary of these instructions.

mainfile-supp.pdf: Contains a human-readable summary of our experimental result, and a summary of domains.