Kairos (καιρός)

A modern temporal and numeric PDDL planner in C++20, usable as a library and as an executable.

Kairos aims to be a reference PDDL planner: broad language coverage, efficient on large problems, robust, and easy to embed. It is developed within the PlanSys2 organization and will become a planner for PlanSys2, but it does not depend on ROS.

How it compares: on classical, numeric, temporal and robotics benchmarks, and on PlanSys2 problems scaled up to thousands of objects, Kairos solves more problems than LAMA, the winners of the IPC 2023 classical and numeric tracks, OPTIC, TFD, POPF, ENHSP and the other planners it was measured against, under the same limits, and as many or more of them within 100 ms and 1 s. Results and method in docs/benchmark.md; which PDDL features each planner handles in docs/pddl-support.md.

Why another planner?

The planners that cover most of PDDL 2.1 (POPF, OPTIC, TFD, LPG) are no longer maintained, are hard to build, and were not designed to be used as libraries: global state, no cancellation, plans returned through stdout. The actively developed ones cover only part of the language (numeric but not temporal, or temporal without temporal heuristics). Very few optimize metrics that combine time and numeric fluents.

Kairos is written from scratch to close that gap.

Goals

• Coverage. PDDL 2.1 level 3 (durative actions, required concurrency, numeric fluents), PDDL 2.2 (derived predicates, timed initial literals), full ADL also inside durative actions, and general metrics. PDDL 3 constraints and preferences and object fluents. Later: PDDL+.
• Efficiency. A fast engine for temporally simple problems (action compression plus rescheduling) and a complete one for required concurrency (snap actions with partial-order states and an incremental STN), chosen automatically by analyzing the task.
• Anytime. Get the first valid plan as soon as possible, keep searching in the background, and receive each better plan through a callback.
• Modest hardware. Plan on the robot’s own computer (Raspberry Pi, Jetson): memory has a budget by default, and Kairos degrades gracefully instead of failing when it gets close.
• Robustness. Precise error messages with file, line and column; no crash on malformed input; cancellable; deterministic with a fixed seed.
• Easy to use. A small C++ API without global state, a command-line tool, PDDL validation without planning, and human-readable debug output per planner stage.
• Measured. A reproducible benchmark against the existing planners on IPC domains and on scaled-up PlanSys2 problems, with every plan checked by an independent validator.

Usage

#include <kairos/kairos.hpp>

// From files...
auto domain = kairos::load_domain("domain.pddl");
auto problem = kairos::load_problem("problem.pddl", *domain);
// ...or from strings already in memory
auto domain2 = kairos::parse_domain(domain_text);
auto problem2 = kairos::parse_problem(problem_text, *domain2);
// (on failure, ok() is false and diagnostics() say what and where)

kairos::Planner planner;

// In the calling thread: the best plan within the timeout
kairos::SolveOptions options;
options.timeout = std::chrono::seconds(10);
kairos::SolveResult result = planner.solve(*problem, options);
if (result.status == kairos::Status::Solved) {
  std::cout << kairos::to_string(*result.plan, kairos::PlanFormat::Ipc);
}

// Anytime, in its own thread: first plan as soon as possible, better ones through the callback
kairos::SearchOptions anytime;
anytime.timeout = std::chrono::seconds(60);
kairos::Search search = planner.start(*problem, anytime,
  [](const kairos::PlanUpdate & update) {
    // update.plan (validated, with its cost), update.index, update.elapsed
  });
auto first = search.wait_first(std::chrono::seconds(5));
kairos::SolveResult best = search.wait();  // or search.stop(); destroying it stops it too

result.status tells what happened (Solved, Unsolvable (proved), NoPlanFound (no proof), Timeout, Cancelled, OutOfMemory, Unsupported, InvalidInput, GroundingTooLarge), result.stop_reason why a

File truncated at 100 lines see the full file

Contribution Guidelines

As an open-source project, we welcome and encourage the community to submit patches directly to Kairos. In our collaborative open source environment, standards and methods for submitting changes help reduce the chaos that can result from an active development community.

This document explains how to report bugs and request enhancements, and how to submit patches so that they are accepted quickly in the codebase.

Licensing

Licensing is very important to open source projects. It helps ensure the software continues to be available under the terms that the author desired.

Kairos is licensed under the Apache 2.0 license, and contributions are made under the same license. Every source file starts with the Apache-2.0 header used across the repository.

A license tells you what rights you have as a developer, as provided by the copyright holder. It is important that the contributor fully understands the licensing rights and agrees to them. Sometimes the copyright holder isn’t the contributor, such as when the contributor is doing work on behalf of a company.

Developer Certification of Origin (DCO)

To make a good faith effort to ensure licensing criteria are met, Kairos requires the Developer Certificate of Origin (DCO) process to be followed.

The DCO is an attestation attached to every contribution made by every developer. In the commit message of the contribution, the developer simply adds a Signed-off-by statement and thereby agrees to the DCO.

When a developer submits a patch, it is a commitment that the contributor has the right to submit the patch per the license. The DCO agreement is shown below and at http://developercertificate.org/.

Developer's Certificate of Origin 1.1

By making a contribution to this project, I certify that:

(a) The contribution was created in whole or in part by me and I
    have the right to submit it under the open source license
    indicated in the file; or

(b) The contribution is based upon previous work that, to the
    best of my knowledge, is covered under an appropriate open
    source license and I have the right under that license to
    submit that work with modifications, whether created in whole
    or in part by me, under the same open source license (unless
    I am permitted to submit under a different license), as
    Indicated in the file; or

(c) The contribution was provided directly to me by some other
    person who certified (a), (b) or (c) and I have not modified
    it.

(d) I understand and agree that this project and the contribution
    are public and that a record of the contribution (including
    all personal information I submit with it, including my
    sign-off) is maintained indefinitely and may be redistributed
    consistent with this project or the open source license(s)
    involved.

DCO Sign-Off Methods

The DCO requires that a sign-off message, in the following format, appears on each commit in the pull request:

Signed-off-by: Sofforus Jones <sjones@gmail.com>

The DCO text can either be manually added to your commit body, or you can add either -s or --signoff to your usual Git commit commands. If you forget to add the sign-off you can also amend a previous commit with the sign-off by running git commit --amend -s. If you’ve pushed your changes to GitHub already you’ll need to force push your branch after this with git push -f.

Note: the name and email address of the account you use to submit your PR must match the name and email address on the Signed-off-by line in your commit message.

Reporting bugs and requesting features

Open an issue at github.com/PlanSys2/kairos/issues. For a bug, include:

• the domain and problem (or the smallest ones that show it), and the plan if it is about validation;
• the exact command or API call, and what you expected;
• the output with -v, or with --debug=<channels> for the stage that fails (for instance --debug=ground,search);
• the Kairos version (kairos --version) and your platform and compiler.

Submitting patches

• One branch and one pull request per change, against main, with a clear description of what changes and why.
• Every change comes with its tests in the same pull request. Tests cover edge values and sequences, not just the happy path. Bugs get a regression test.

File truncated at 100 lines see the full file