Situation Calculus Synthesis

This tool provides controller synthesis/orchestration of resource programs $\delta_i$ (where each program has a corresponding logical action theory) to realise a high-level target program (recipe). Recipes and resource programs are in the ConGolog programming language and compiled to characteristic graphs by this tool, where resource programs can be non-terminating/infinite, but recipe programs must be terminating.

Logical action theories for resource programs are given by situation calculus basic action theories, $\mathcal{D_i}$. Situation calculus is a second-order logic with equality for reasoning about actions in AI with three disjoint sorts: actions, objects, and situations. Preconditions are specified for each action (and possibly for certain configurations of compound/concurrent actions), and successor state axioms encode causal laws of changes to fluents as a result of performing actions (dynamic predicates).

This tool implements two different possible solvers/search algorithms for controller synthesis, namely: A* search (A*), and Greedy Search (GS).

Build instructions

Requirements

• CMake (>=3.26)
• Git (for submodule cloning)
• A C++23 compiler
• Ninja (required by the supplied CMake presets), or another CMake-supported build tool such as Make when configuring without a preset
• GraphViz for visualisation (dot must be in PATH)

On Debian/Ubuntu, Fedora, or Arch Linux, respectively, the development tools can be installed with:

sudo apt install cmake ninja-build g++ git graphviz
sudo dnf install cmake ninja-build gcc-c++ git graphviz
sudo pacman -S cmake ninja gcc git graphviz

Package names and the available CMake version vary between distribution releases. Before configuring, the tools used by the preset build can be checked with:

cmake --version
ninja --version
c++ --version
dot -V

Cloning & updating

Clone the repository alongside its submodules (shallow submodule cloning is optional).

git clone --recurse-submodules --shallow-submodules https://github.com/nightly/scs
git submodule update --init --recursive

During development, to correctly pull any newly added Git submodules to your local repository (git pull alone doesn't suffice):

git submodule update --recursive

CMake

The supplied Linux presets use Ninja. From the repository root, configure and build a release version with:

cmake --preset linux-release
cmake --build out/build/linux-release --parallel "$(nproc)"

For a debug build followed by the complete test suite:

cmake --preset linux-debug
cmake --build out/build/linux-debug --parallel "$(nproc)"
ctest --test-dir out/build/linux-debug --parallel "$(nproc)" --output-on-failure

If Ninja is unavailable but Make is installed, configure without a preset and select CMake's Unix Makefiles generator:

cmake -S . -B build -G "Unix Makefiles" -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel "$(nproc)"
ctest --test-dir build --output-on-failure

On macOS use the macos-debug preset. Windows presets are x64-debug and x64-release. The project can also be opened in an IDE with CMake support.

Layout

• app: contains the interactive CLI and unified paper-results applications.
• bench: contains all the project's benchmarks
• data: has some sample programs
• docs: contains some incomplete basic documentation/implementation notes
• examples: small example programs that can be ran/viewed
• exports: any directory marked exports gives any system/user-generated output
• external: 3rd party dependencies added as Git submodules
• src/scs: SCS library code
• tests: holds all tests & test data

Running benchmarks with memory profiling

To run benchmarks with memory profiling, navigate to bin/Benchmarks directory, for a given benchmark executable's file (e.g. bm.exe) run the following: bm.exe --benchmark_format=json

This is required because Google Benchmark's console output/VS runner doesn't report memory usage statistics, it is only given properly in the JSON format.

Reproducing the paper results

The unified scs_paper application runs the complete experimental evaluation and writes tab-separated text files. Use a Release build for meaningful timings:

cmake --preset linux-release
cmake --build out/build/linux-release --target scs_paper --parallel "$(nproc)"
./bin/Release/scs_paper

By default, each run creates exports/paper-results/<UTC timestamp>/ containing grounding.tsv, astar.tsv, gbfs.tsv, phase_cost.tsv, phase_transitions.tsv, scaling.tsv, and run.tsv. Controller suites also export solved plans as GraphViz files named astar-2-controller.gv, astar-3-controller.gv, gbfs-2-controller.gv, and gbfs-3-controller.gv; the three-resource A* file is present only if that attempt finds a controller. The complete suite is intentionally sequential and can take several hours; its three-resource A* attempt has a three-hour default timeout.

Available controls are:

./bin/Release/scs_paper --list
./bin/Release/scs_paper --suite tables --astar-timeout 5m
./bin/Release/scs_paper --suite limits --output-dir exports/my-paper-run
./bin/Release/scs_paper --suite scaling --scaling-resources 3,10,100,1000

Suites are all, tables, grounding, controllers, limits, and scaling. An explicitly selected output directory must be empty. Timings use Google Benchmark CPU time; wall time is included as a diagnostic column. Each measured iteration starts from fresh experiment and solver state with random seed 2010, so results may differ from the original MSVC/Ryzen measurements.

After its two-resource quick baseline, the scaling suite keeps three hinge resources active and adds one-state Nop resources that do not occur in the recipe or change any fluent. This isolates the overhead of increasing the facility size from the cost of making the recipe itself more complex. Its cost limits grow only enough to offset the extra Nop entries, preserving the original three-resource search envelope. Default geometric checkpoints extend to 2,048 total resources; --scaling-resources accepts any comma-separated set of totals of at least two.

Credits

• Situation calculus for controller synthesis in manufacturing systems with first-order state representation
• Boost's:
  • Container hash library
  • flat_map, flat_set
• Google Test and Google Benchmark
• Planning and verification in the agent language Golog
• ankerl::unordered_dense::{map, set}