PaperlayerView exact revision on arXiv

Source-linked AI summary

FONDANT: Strong and Best-Effort Planning via Antichains

Benjamin Aminof, Tuan Khai Nguyen, Sasha Rubin

arXiv:2609.35160v1cs.AI

TL;DR

FOND planning asks how to act when no policy guarantees reaching the goal against every nondeterministic outcome. FONDANT uses antichains to represent winning regions and produces strong and best-effort policies; it outperforms comparison planners in coverage on the evaluated benchmarks, while its best-effort results include 46 answers versus BeSyftP’s 34. Its reported limitation includes one rectangle instance neither tool could decide because of a memory-cap overrun and a timeout.

  • Problem

    In FOND planning, actions can have multiple possible effects, and a strong policy that guarantees reaching the goal against every outcome may not exist.

    Source: §1 · p. 1

  • Method

    FONDANT represents upward-closed winning regions by antichains and uses ranked instructions to induce policies for strong and best-effort planning.

    Source: §1 · p. 1

  • Results

    FONDANT outperformed PR2 and FOND-SAT in strong-planning coverage and answered 46 best-effort instances versus BeSyftP’s 34.

    Source: §6.1 · p. 9, §6.2 · p. 10

  • Takeaways & Limitations

    The conclusion reports at least comparable performance on some domains and better scaling on large instances in some domains.

    Source: §7 · p. 11

    On rectangle p15, neither tool returned a verdict: FONDANT’s grounding exceeded the memory cap, and BeSyftP timed out.

    Source: §6.2 · p. 11

Abstract

from arXiv · show

A classical solution concept in fully observable nondeterministic (FOND) planning, is the strong policy (aka winning strategy in the closely related area of reactive synthesis), i.e., such a policy ensures that the goal is reached in an adversarial environment. When strong policies are not available or there is no evidence that the environment is adversarial, one can resort to best-effort policies, which always exist, and which follow the classic decision-theoretic principle that an agent should not use a dominated strategy. A typical positional best-effort policy works as follows: from every state, it follows a strong policy if one exists from that state (such states are called ``strong-winning''), else a weak policy if one exists from that state (``weak-winning''), and else is unconstrained (``losing''). In this work, we introduce a sound and complete planner for both best-effort planning and strong planning. The algorithm that underpins the planner is quite simple: it represents certain sets of states, such as the winning regions, by their $\subseteq$-minimal elements. The algorithm returns uniform policies, i.e., it returns a policy $\pi_t$ that is a strong solution starting in every strong-winning state, and it returns a policy $\pi_w$ that is a weak solution starting in every weak-winning state, and it provides a certificate for the set of losing states. We implemented the algorithm with some simple optimizations (calling it FONDANT), and evaluated it on a benchmark set consisting of the instances that were used in the evaluation of leading strong planners PR2 and FOND-SAT, and the best-effort planner BeSyftP. On coverage, our implementation is at least as good on all domains, and outperforms on some domains; and on wall time, it is slower on small and medium-sized instances, and outperforms on larger instances.

1 Introduction

FONDANT addresses strong and best-effort FOND planning without assuming a cooperative or adversarial environment. It represents upward-closed winning regions by antichains and introduces an instruction-set policy representation, alongside an evaluation on established planner benchmarks.

1 Introduction

  • FONDANT represents upward-closed winning regions by their minimal elements, called antichains, and uses ranked instructions to induce policies.Each instruction gives an action applicable to states containing its atom set; the induced policy selects an applicable instruction with smallest rank.Source: §1 · p. 1
  • Strong and best-effort FOND planning are EXPTIME-complete, so the implementation combines classic optimizations with the algorithm.The listed optimizations are mutex groups, h2 pruning, and hmax-style heuristic selection.Source: §1 · p. 1
  • The evaluation uses 222 instances from eight strong-planning domains and 47 instances from BeSyftP’s public best-effort repository.The strong-planning set was used to evaluate PR2 and FOND-SAT.Source: §1 · p. 2

1.1 Related Work

  • Earlier strong-planning approaches include explicit AND/OR and regression search, repeated replanning, and SAT-based synthesis; PR2 and PR2’s predecessors represent policies differently from FONDANT.PRP groups states sharing an action, while PR2 uses controller DAGs; FONDANT groups states but searches applicable instructions by rank.Source: §1.1 · p. 2
  • Best-effort solutions have been studied in games, temporal synthesis, and robotics, and a prior tool handles FOND problems with LTLf goals.The cited prior work includes Berwanger 2007; Faella 2009; Brenguier, Raskin, and Sassolas 2014; Aminof, De Giacomo, and Rubin 2021; Muvvala, Amorese, and Lahijanian 2022; and De Giacomo, Parretti, and Zhu 2023.Source: §1.1 · p. 2
  • Antichain algorithms also appear in automata and LTL synthesis, where upward-closed winning regions are represented through minimal elements.The related LTL synthesis algorithm uses a safety-game objective, the counterpart of FONDANT’s strong objective; the works differ in domain and antichain growth.Source: §1.1 · p. 2

2 Preliminaries

The preliminaries define FOND problems and their policies, then characterize strong-winning and weak-winning regions and introduce antichains as compact representations of upward-closed sets.

2.1 FOND planning problems

  • A FOND problem specifies atoms, an initial condition, a goal condition, and actions with preconditions and nondeterministic effects; states are sets of true atoms.Policies map histories to applicable actions, and positional policies depend only on the current state.Source: §2.1 · p. 2

2.2 Solution concepts for FOND planning problems

  • A strong policy reaches the goal under every environment choice, whereas a weak policy reaches it under some choice.The strong-winning region is built from goal states by repeatedly adding states with an action whose every effect leads into the prior layer; the weak-winning region uses an action with at least one such effect.Source: §2.2 · p. 3
  • A best-effort policy is not strictly dominated, and a positional one can combine a uniform strong policy on T with a uniform weak policy on W outside T.The resulting policy is best-effort; best-effort policies always exist.Source: §2.2 · p. 3

2.3 Upward-closed sets and Antichains

  • An upward-closed set is uniquely represented by its antichain of minimal elements, and adding a qualifying new minimal state extends that basis.Basis extension removes elements strictly containing the new state and adds that state, expanding the represented upward closure while staying within X.Source: §2.3 · p. 3

3 Representing policies by instruction-sets

The paper represents memoryless policies as sets of ranked instructions and shows this representation can express any memoryless policy. The proof’s construction uses one instruction per domain state, though smaller sets are possible in some cases.

3 Representing policies by instruction-sets

  • A ranked instruction ⟨x, a, r⟩ associates an action with states containing x, plus a non-negative integer rank.The instruction set induces a memoryless policy by selecting an applicable instruction with minimum rank, with ties broken arbitrarily.Source: §3 · p. 4
  • Every memoryless policy can be represented exactly by a set of ranked instructions.The proof assigns ranks decreasing as states grow under subset inclusion, then includes one instruction for each state and its policy action.Source: §3 · p. 4
  • The proof’s representation uses one instruction per domain state, although some domains and policy classes admit smaller instruction sets.Source: §3 · p. 4

4 Planning with antichains

FONDANT represents strong- and weak-winning regions by minimal states because both regions are upward-closed. It computes these bases, derives uniform winning policies from ranked instructions, and can prune unreachable candidates without changing correctness.

4.1 Representing Winning Region By Bases

  • Upward closure means each winning region can be represented by its minimal states, forming a compact basis for both strong and weak winning.The upward-closure result follows from monotone action preconditions and successor updates.Source: §4.1 · p. 4

4.2 Computing the bases of the winning regions

  • Starting from the goal states, the strong-winning basis is built iteratively from minimal universal predecessors; the resulting antichain is the basis of the strong-winning region.The algorithm terminates after at most |T| iterations.Source: §4.2 · pp. 4–5
  • For the weak-winning basis, existential predecessors replace universal ones, and the resulting antichain is the basis of the weak-winning region.The correctness theorem covers both the strong and weak versions of the algorithm.Source: §4.2 · p. 5

4.3 Computing an instructions-set that induces a uniform strong-winning (resp. weak-winning) policy

  • Recording ranks, witness actions, and witness states lets the algorithm construct instructions inducing uniform strong- or weak-winning policies.Rank descent guarantees every strong-policy play, or some weak-policy play, reaches a goal within the instruction rank.Source: §4.3 · pp. 5–6

4.4 An optimization that prunes unreachable candidate states

  • Pruning candidates that violate mutex groups removes unreachable states while preserving the winning-region bases and the uniform policies on the remaining states.The resulting upward closures differ from the full winning regions only by unreachable states.Source: §4.4 · pp. 6–7

5 Implementation

FONDANT combines precomputation with an optimized antichain search and a final classification step. Its implementation uses mutex information, heuristic ordering, and runtime steering to guide candidate selection.

5 Implementation

  • The implementation combines the strong- and weak-winning versions of Algorithm III to classify the initial state and produce a best-effort policy.Its three stages are precomputation, core search, and finalisation.Source: §5 · p. 7

5.1 Precomputation

  • For PDDL benchmarks, Fast Downward translates instances to SAS+, after which FONDANT computes mutex groups and a selection heuristic.The implementation follows the standard translation approach used by prior planners.Source: §5.1 · p. 7

Mutex groups

  • Pair-fixpoint h2 computes sound but incomplete size-2 mutex groups, and aborts on time or memory limits without registering partial results.The time budget is 1% of the instance time cap; the tables are quadratic in the number of atoms.Source: Mutex groups · p. 7

Heuristic computation

  • The heuristic computes forward delete-relaxed costs from the initial state and backward costs to the goal using hmax aggregation.A Dial-bucket Dijkstra pass computes each set of costs over the relaxed action graph.Source: Heuristic computation · p. 7

5.2 Core Algorithm

  • The core search maintains an incremental candidate pool and set-trie basis, ordering candidates by a potential that favors atoms cheap from the initial state and costly from the goal.A monotone heap key supports minimal-candidate selection; the set-trie supports average O(|At|) insertion and coverage checks.Source: §5.2 · pp. 7–8
  • Runtime steering adds penalties for drift across flat potential regions and periodically favors shallower derivation chains through temporary depth windows.Drift penalties alter pool keys after updates; depth terms are applied in windows and then dropped.Source: §5.2 · p. 8

5.3 Finalisation

  • If a strong-basis state is contained in the initial state, FONDANT reports strong-winning; otherwise it searches for weak-winning and reports losing if neither basis contains such a state.The weak-winning result supports construction of a best-effort policy.Source: §5.3 · pp. 8–9

6 Experiments

The experiments compare FONDANT with established strong and best-effort planners on published benchmark sets, then extend several strong-planning families to test scaling. FONDANT achieves broader coverage in both settings, with runtime advantages varying by instance size and domain.

6 Experiments

  • The evaluations used published strong-planning and best-effort benchmark sets, with per-instance limits of 1800 seconds and 16 GiB.The strong set came from eight domains used in FOND-SAT benchmarking; the 47 best-effort instances came from BeSyftP’s public repository.Source: §6 · p. 9, §6.2 · p. 10
  • The strong-planning benchmark comprised 222 instances across eight domains, with nine non-strong-winning cases identified as weak-winning.The strong-winning coverage table restricts its scope to strong-winning instances; the benchmark excluded specified outcomes in zenotravel and tireworld before reporting those results.Source: §6.1 · p. 9, §6 · p. 9

6.1 Results for strong-winning

  • FONDANT solved all 213 strong-winning instances within 12.2 s, versus 204 for PR2 and 162 for FOND-SAT.The coverage comparison is over the strong-winning instances under the 1800 s cap.Source: Table 1 · p. 9, §6.1 · p. 9
  • PR2 was faster on instances it solved in under a second, while FONDANT’s fixed precomputation—especially mutex computation—dominated some small and medium runtimes.On those rows, the core algorithm ran at millisecond scale.Source: §6.1 · pp. 9–10
  • FONDANT’s strong-planning phase also supplied certificates for nine instances without strong-winning solutions, while FOND-SAT timed out on all nine.PR2 either timed out or established only that no strong plan of width ≤5 existed, which the authors say is not a valid certificate of non-winning.Source: §6.1 · p. 10
  • On expanded domains, FONDANT stayed fast on doors and triangle-tireworld, while PR2’s runtime rose sharply or timed out on some larger instances.FONDANT solved all forty expanded triangle-tireworld instances in under 7.3 s; at 36-city zenotravel, PR2 exhausted widths 1–5 while FONDANT returned a strong plan.Source: §6.1 · p. 10, Figure 2 · p. 11

6.2 Best-effort results

  • On 47 best-effort instances, FONDANT answered 46 versus BeSyftP’s 34, and their classifications agreed wherever both answered.FONDANT decided the instances BeSyftP left unanswered in 0.19–44.6 s; among jointly answered cases, BeSyftP was faster on seven crafted tireworld variants, while FONDANT was faster by two to three orders of magnitude on other domains.Source: §6.2 · p. 10, Table 4 · p. 11

7 Conclusion and future work

The conclusion presents an antichain-based planner for strong and best-effort FOND planning that classifies instances as strong-winning, weak-winning, or neither. It reports better scaling than PR2 on large instances in some domains and identifies strategy-size, selection, and evaluation extensions as future work.

7 Conclusion and future work

  • The antichain-based algorithm supports both strong and best-effort FOND planning and classifies instances as strong-winning, weak-winning, or neither.Source: §7 · p. 11
  • Compared with PR2, FONDANT does at least as well on some domains and scales better on large instances in some domains.Source: §7 · p. 11
  • Future work targets smaller instruction sets for uniform strong policies, improved selection mechanisms, and broader best-effort and strong-winning test sets.Source: §7 · p. 11
Loading 2609.35160v1…