AND* Project

AND* is an uncomplicated FOND planning algorithm with strong theoretical guarantees.

• Messa and Pereira, "A Best-First Search Algorithm for FOND Planning and Heuristic Functions to Optimize Decompressed Solution Size", ICAPS 2023. (link)

• Messa and Pereira, "Policy-Space Search: Equivalences, Improvements, and Compression", submitted to AIJ. (arXiv)

---

This project version was mainly tested in Linux Mint 21.2 and Ubuntu 22.04.

Note: A newer version of the AND* Project might be available on GitHub.

---

Installing Dependencies (Ubuntu 22.02)

apt-get install -y \
    git \
    python3 \
    python3-pip \
    make \
    g++ \
    libboost-all-dev \
    libgmp3-dev \
    gap \
    nauty

git submodule update --init --recursive

python3 -m pip install -r requirements.txt

This project also uses:

• A modified version of the PRP's PDDL to SAS+ translator, placed at ./dep/translator/
• A modified version of the PRP's solution validator, placed at ./dep/validator/
• Our proposed FOND solution compressor, placed at ./dep/compressor/

More information about the modifications of the PRP's translator and validator can be found on this page.

---

Building

make

---

Running

./and_star.py domain.pddl problem.pddl

Optional: --optimal (to run AND* in optimality mode, which is slower)

---

Low-level Interface

./and_star domain.pddl problem.pddl policyHeuristic stateHeuristic searchEngine equivalenceDetection symmetryDetection deadlockDetection

• policyHeuristic: count, nearest, delta-nearest, delta-pathmax
• stateHeuristic: blind, max, lmcut, ff, add, star
• searchEngine: best-first, 2-weighted-first, greedy-first
• equivalenceDetection: id, lanes, in-out, out
• symmetryDetection: false, greedy, true
• deadlockDetection: true, false, fix

You can also specify an extra argument to change the IP solver used by the compressor.

Strongest setting: (incomplete – it may incorrectly prune all solutions and fail)

./and_star domain.pddl problem.pddl delta-pathmax lmcut 2-weighted-first out true true

If it fails, try this safe setting:

A safe setting: (sound and complete)

./and_star domain.pddl problem.pddl delta-pathmax lmcut 2-weighted-first id false true

For optimality, change 2-weighted-first to best-first in the safe setting.