Kairos: Semantics-Aware Orchestration of Planning Engines across Classical, Numeric, Temporal and Hybrid PDDL

1 Introduction

• Online planning must cover changing PDDL models, answer within a robot’s control loop, and avoid invalid plans or unexplained failures.The introduction frames coverage, latency, and trust as distinct demands.Source: §1 · p. 2
• Kairos tests whether one system can cover PDDL from STRIPS to PDDL+ while matching specialized planners’ speed and stating what each answer guarantees.The motivating problem is that systems choosing one fragment-specific planner inherit its coverage gaps.Source: §1 · pp. 2–3
• Task semantics first determines applicable engines and transformations; only then does Kairos allocate shared time and memory among them.The task profile includes temporal simplicity, which can make faster compressed search applicable.Source: §1 · pp. 2–3
• Every returned plan is independently validated, while “unsolvable” is reserved for exhaustion of a search whose exhaustion proves unsolvability.Otherwise, Kairos reports no plan found and explains why.Source: §1 · pp. 2–3
• Kairos contributes a public benchmark with feature-oriented families and unsolvable instances, plus one-feature probes for measuring planner support.Its experiments assess coverage, latency, planner support, engine ablations, and validator agreement with VAL.Source: §1 · p. 3

2 Preliminaries

• The paper covers PDDL features from STRIPS and ADL through numeric and temporal constructs, preferences, object fluents, and PDDL+ processes and events.For temporal plans, it follows PDDL 2.1 happening and open-interval semantics, and for PDDL+ it follows Fox and Long’s process and event semantics.Source: §2 · p. 3
• Temporal tasks that need no overlap can use compression and later scheduling; tasks requiring concurrency need snap-action search with an STN.Temporal simplicity is defined as solvability without concurrent actions.Source: §2 · p. 3

3 Related Work

• Operational support is measured by execution on one-feature tasks, since declared requirement flags may not match planner behavior.The probe table distinguishes accepted plans from doubtful outcomes and rejection or no answer.Source: §3 · p. 4, Table 1 · p. 5
• Unlike same-fragment portfolios, Kairos uses task semantics to exclude engines that cannot represent a task, recommend potentially faster incomplete engines, and interpret failures from engine properties.Its answer contract is enforced inside the planner, unlike a unified interface that exposes planners with their own coverage.Source: §3 · pp. 4–5

4 Architecture

• The validator evaluates parsed PDDL rather than normalized, grounded, or compressed tasks, so planner transformations cannot validate their own errors.The parser and semantic checks are shared, leaving input misreading as a remaining dependence.Source: §4 · p. 5, Figure 1 · p. 6
• Grounding reserves memory from a shared budget and stops at its limit; search structures also account for memory in that budget.The pipeline hands off from grounding to lifted search when grounding does not fit.Source: §4 · p. 6, Figure 1 · p. 6

5 The Task Profile

• The profile records task features, size, and temporal simplicity; temporal simplicity matters because compressed search is much faster than snap-action search when applicable.The check by values avoids false concurrency alarms caused by variables whose transient values are never read.Source: §5 · p. 6
• Under fixed-duration and other stated hypotheses, every sequential plan of the compressed task can be scheduled as a valid temporal plan.Returned plans are validated, and a sequential schedule remains the fallback when resource ordering freedom does not validate.Source: §5 · p. 7
• Simple by value is not a completeness criterion: a task may need overlapping actions despite having no transient value read by another action.The two-robot table-lifting example has no sequential plan, although overlapping preparations solve it.Source: §5 · p. 7
• When compressed search finds no plan, Kairos may try a relaxed task whose exhaustion can prove unsolvability under stated assumptions, then use snap-action search if no proof results.The relaxed numeric state space may be unbounded, so the search need not terminate or be cheap.Source: §5 · p. 8

6 Engines

• Kairos assigns five engines to classical or numeric ground tasks, simple-by-value temporal tasks, concurrency, hybrid dynamics, and tasks too large to ground.All engines share the front end, validator, and memory budget.Source: §6 · p. 8
• M1 combines greedy best-first search and weighted A* with landmarks, numeric subgoaling, and a novelty queue.Its unread-numeric-variable projection increased classical-suite coverage from 117 to 140 of 220 during development.Source: §6 · p. 8
• M2 searches an instantaneous compression of eligible durative actions, then orders happenings and computes an earliest schedule.Constant-increment/decrement resources do not order happenings by themselves, preserving shared-capacity concurrency when the plan validates.Source: §6 · p. 9
• M3 searches start and end snap actions with an incremental STN, using makespan as its search cost.Timed initial literals constrain interfering happenings, and temporal deadlines can prune states that cannot reach a goal in time.Source: §6 · p. 9
• The hybrid engine discretizes time with short or condition-triggered waits, forces applicable events, integrates processes with RK4, and validates plans in continuous time.Non-linear conditions enter the relaxed graph linearized around the current state.Source: §6 · p. 9
• The lifted engine avoids grounding for classical tasks that exceed the budget, generating successors through state joins and lazy heuristic and novelty queues.Its projected partial joins reduce combinations per layer from 17502 to 1750 in the drive-truck logistics example.Source: §6 · p. 9

7 Orchestration

• Hard applicability constraints exclude engines that cannot represent the task, while semantic guidance can prefer an incomplete strategy before scheduling shares time and memory.The decisions are kept distinct so an inapplicable engine is not confused with an unsuccessful search.Source: §7 · p. 9
• The phase shares and thresholds were set by hand on public suites, then fixed; their sensitivity was not optimized and is left for future work.The orchestrator does not see domain names, so it cannot tune shares per domain.Source: §7 · pp. 9–10
• Ground search hands over to lifted search when grounding fails or uses more than one quarter of the memory limit.Ground search typically needs about three times the memory of its task.Source: §7 · p. 10

8 Answers and Guarantees

• Only a complete M1 configuration that exhausts its open list proves a task has no plan, subject to the stated search assumptions.For the lifted engine, the result holds up to a collision of its 128-bit state keys.Source: §8 · pp. 10–11
• Kairos reports an optimal plan only under the stated non-temporal, non-negative-cost conditions; it does not report makespan optimality for temporal tasks.For other metric forms, it searches with unit costs, does not prune, and says so.Source: §8 · pp. 11–12
• When no plan is returned, Kairos identifies which engine gave up and whether exhaustion proves anything, or explains an unreachable goal through its facts and preconditions.The fuse example illustrates that exhausting an incomplete engine's space does not prove unsolvability.Source: §8 · p. 12, Figure 2 · p. 12

9 Validation

• Every returned plan is checked against the parsed domain and problem, independently of search and planner transformations, but a shared parser means a PDDL misreading could affect both.A comparison with VAL addresses that remaining dependence; plans that fail validation are never delivered.Source: §9 · p. 12
• Kairos integrates linear continuous effects exactly, but validates non-linear dynamics numerically with fourth-order Runge–Kutta steps of 0.01 s.A condition that becomes true and false within one step, or a tangency, can be missed; the fixed step's sensitivity is unmeasured.Source: §9 · p. 13
• VAL is not reused because it lacks some syntax and non-linear coverage, is a command rather than an embeddable library call, and provides less targeted diagnostics.Kairos reports the failing step, plan-file line, condition, and falsifying values.Source: §9 · p. 13

10 Implementation and Platform

• The C++20 library and command-line program support embedding, anytime search, plan output, and standalone validation; Kairos is also distributed through ROS 2, conda, Python, and planutils.The source, benchmark, experiment scripts, and raw results are public.Source: §10 · pp. 13–14
• Kairos has 979 tests covering stages, heuristics, task equivalence, and end-to-end validation, with sanitizers, parser fuzzing, and at least 90% line coverage.Continuous integration tests within a 512 MB memory cgroup and builds ROS 2 packages for every target.Source: §10 · p. 14

11 Benchmark

• PlanSys2-at-scale tasks are generated at six sizes with three seeds, and each has a validated reference plan, making every generated problem solvable by construction.Reference plans certify solvability but are not used by planners or to select problems.Source: §11 · p. 14
• The benchmark separates nine comparative suites (1,756 tasks), a 450-task feature bank for checking Kairos's answers, and 26 probes used for Table 1.The feature bank is not comparative because other planners reject or fail on many tasks outside their supported features.Source: §11 · pp. 14–15, Table 5 · p. 15

12.1 Method

• Runs used 30 s and 3 GB per task, validated every plan, and compared domain-level bootstrap intervals because tasks within a domain are correlated.Each configuration ran once per task, so the reported intervals do not account for run-to-run timing variability.Source: §12.1 · pp. 15–16

12.2 Q1: Coverage and latency

• Kairos solves the most tasks at the full limit on every suite and among first-plan reporters at 100 ms and 1 s, with its largest differences on numeric, PDDL3, PDDL+ and PlanSys2 suites.At the full limit, the classical comparison is 166 tasks against LAMA’s 160, while the numeric comparison is 299 against ENHSP’s 208.Source: §12.2 · p. 16, Table 6 · p. 17

12.3 Q2: Support

• Kairos handles all 17 probed features, while no other evaluated planner handles more than eight; single-feature probes are only a lower bound on full feature support.The probes count crashes, invalid plans, and rejected inputs as failures for the relevant feature.Source: §12.3 · pp. 17–18

12.2 Q1: Coverage and latency

• Domain-resampled gains are significant on five suites and above zero on PDDL3; the classical gain against LAMA is within the noise, while the concurrency and durations tests lack power for significance.On classical tasks, Kairos solves 111 at 1 s against lama-first’s 75.Source: §12.2 · p. 16, Table 7 · p. 19
• Median first-plan time is below 0.15 s on every suite except PDDL+ (0.31 s) and hard-to-ground (0.28 s), and Kairos has the highest IPC score on classical and numeric suites.The classical IPC scores are 154.5 for Kairos and 152.5 for LAMA; numeric scores are 292.7 for Kairos and 166.5 for ENHSP.Source: §12.2 · p. 16, Table 8 · p. 19, Table 9 · p. 20

12.4 Q3: Ablation

• Compressed temporal search nearly matches the full planner on temporal tasks (179 against 180), while the novelty fallback adds 9 classical and 27 numeric tasks at the limit.On numeric tasks, the portfolio is slightly slower at short limits than lazy FF alone; unread-numeric-variable projection was measured in development versions, not a controlled ablation of the release.Source: §12.4 · p. 19, Table 10 · p. 20

12.5 Q4: Agreement with VAL

• Among 3,045 cases VAL could decide, the validators agreed on 3,024 verdicts; all 21 disagreements were checked and traced to a PDDL+ convention or VAL defects.For command-line runs, Kairos’s validator took 1.4 ms per plan at the median, compared with VAL’s 3.0 ms.Source: §12.5 · p. 21

12.6 Q5: Tasks without a plan

• Kairos answered unsolvable on ten of eleven generated tasks without plans and returned no plan found on the remaining task; no planner gave a wrong answer in the feature bank.Kairos never answered unsolvable on a task another planner solved.Source: §12.6 · pp. 21–22, Table 11 · p. 21

13 Case Studies

• For a fuse-mending task, the profile selects M3 because the match provides light only while burning, allowing mending to overlap the match.Mending starts with the match; its over-all condition holds on the open interval (0, 2).Source: §13 · p. 22
• For a pump-and-tank task with a process and spill event, Kairos uses 0.1 s time steps and validates continuous process behavior and event avoidance.A long wait crosses five seconds but stops just before the goal condition becomes true.Source: §13 · p. 22

14 Limitations and Scope of the Conclusions

• Temporal engines M2, M3, and time-step search are incomplete, so their failures yield no plan found rather than proofs of unsolvability.Some proof claims depend on implementation properties tested by property-based tests but not formally verified.Source: §14 · p. 22
• Validated plans follow the PDDL semantics used by Kairos, but non-linear dynamics receive numerical, not certified, validation.Kairos uses ENHSP’s same-instant PDDL+ convention, which VAL does not share; physical executability is not established.Source: §14 · pp. 22–23
• The evaluation covers nine suites with one run per task, and its comparisons reduce but do not remove noise from the unpinned processor and startup accounting.Orchestration shares were hand-selected using public suites also used in evaluation; robustness on independent domains and sensitivity to the settings remain unestablished.Source: §14 · p. 23
• Feature support is operationally demonstrated by a small probe task, not established for every combination; grounding memory can also limit large tasks.The conclusion confines its performance claims to the evaluated suites, planners, versions, and protocol.Source: §14 · p. 23, §15 · p. 23

15 Conclusion

• Kairos solved more tasks than the strongest evaluated planner of each suite at full limits and the most among planners reporting first plans at 100 ms and 1 s.On classical planning, its 30 s gain over LAMA was not significant.Source: §15 · p. 23

A Proofs

• The proof’s state equivalence ignores only projected numeric variables that are unread by conditions, effects, durations, axioms, or goals and defined initially.The appendix also notes that the scheduler is not required for soundness and gives conditions limiting use of the snap-task relaxation.Source: A Proofs · pp. 25–26
• Exhaustion proves no plan exists when the search visits every reachable class, discards only seen classes or proven dead ends, and tests generated goals.The lifted engine follows the same principle, with exhaustion not claimed when its budget runs out; duplicate detection relies on a 128-bit key and is subject to collision risk.Source: A Proofs · p. 26

B Heuristics and Search of M1

• M1’s relaxed exploration treats achieved facts as persistent and counts helpful numeric changes toward linear conditions to estimate relaxed-plan cost.The heuristic combines action costs with repetition counts in hFF.Source: B Heuristics and Search of M1 · p. 26
• The relaxation marks a state dead only when its over-approximation cannot reach the goal; contributors to non-linear conditions are treated as reaching them at least once.Landmarks and novelty provide additional search guidance, while greedy best-first search and weighted A* restarts define the described configurations.Source: B Heuristics and Search of M1 · p. 27

C The Lifted-Table Task

• M2 exhausted its four states on the lifted-table task, but M3 found a plan with both actions starting at 0.000 and makespan 10.The validator accepts a plan with the second action starting at 1.000 and makespan 11.Source: C The Lifted-Table Task · p. 28

D Full Tables

• Kairos solved 7/10 parking tasks, while LAMA solved 10; on folding it solved 2/10, while LAMA solved 3.The table also reports 7/10 for Kairos versus 10 for LAMA on rubiks-cube.Source: D Full Tables · p. 30
• On numeric tasks, Kairos solved 6/10 counters tasks versus ENHSP’s 10, and 4/10 sailing-wind-opt tasks versus ENHSP’s 10.Kairos solved 1/10 settlers tasks versus Metric-FF’s 3.Source: D Full Tables · p. 30
• On temporal tasks, Kairos solved 3/5 storage-time tasks versus LPG-td’s 4, and 2/5 floor-tile 2014 tasks versus LPG-td’s 5.The table also lists LPG-td and TFD at 5 against Kairos’s 4/5 on rovers-time.Source: D Full Tables · p. 30
• The listed PDDL3 and PDDL+ rows also include rival leads, such as OPTIC’s 4 against Kairos’s 1/5 on storage-preferences-complex.ENHSP solved 5 against Kairos’s 1/6 on chasing cars.Source: D Full Tables · p. 30

• The planner and benchmark are available under Apache 2.0 licenses.The benchmark license covers the problems and code.Source: E Online Resources · p. 30
• The benchmark repository includes run scripts, raw planner results, Kairos plans, pinned planner container recipes, and the Section 12.5 VAL comparison.The comparison includes the plan, domain, and problem for each disagreement.Source: E Online Resources · pp. 30–31
• The article appeared in the Journal of Artificial Intelligence Research in August 2027.Source: E Online Resources · p. 30

• Orchestration shares were set by hand or inspection, without a search over settings, and their sensitivity is left for future work.All settings are reported, but the shares were determined during development.Source: All articles · p. 31, Articles reporting on computational… · p. 32
• The theoretical checklist reports proof sketches for Propositions 2 and 4, while the hypotheses of Propositions 3 and 4 are implementation properties tested but not formally verified.Propositions 1 and 3 are proved, and compression completeness is refuted by Example 1.Source: Articles containing theoretical… · p. 31
• The checklist reports that experiments, evaluation metrics, run counts, and algorithm settings are described, while parameter exploration and optimization effort are only partially reported.The checklist also marks statistical-significance testing as a criterion, but the supplied passage does not include its response.Source: Articles reporting on computational… · pp. 31–32
• The checklist says code, raw experimental data, and execution-environment details are or will be available, with licenses permitting research and reproducibility use.With one thread, Kairos is deterministic; generators take a seed.Source: Articles reporting on computational… · p. 31
• The checklist reports that newly introduced datasets are available or will be made available, appropriately licensed, and described alongside preprocessing and splitting methods.It also says literature-derived datasets are cited and publicly available.Source: Articles using data sets · p. 32