TL;DR
This paper introduces Temporal FONDs (TFONDs), a novel formalism for planning in domains where actions' effects depend on the entire history of states, not just the current one. They provide a method to solve these complex non-Markovian planning problems by reducing them to standard FOND problems, achieving a 2EXPTIME-complete complexity for planning.
What Problem Does This Paper Address?
Traditional planning algorithms often assume the Markov property: an action's outcome depends solely on the current state. However, many real-world scenarios, like the example of a robot in a research facility where contamination depends on past actions (visiting low-safety areas or disinfection stations), violate this assumption. These "non-Markovian" dynamics make planning significantly harder. While extending the state with auxiliary variables can sometimes make a domain Markovian, this can lead to an exponential blow-up in state complexity, making it impractical for humans to design. This paper tackles the challenge of formally specifying and efficiently solving planning problems in these non-Markovian, yet fully observable, nondeterministic domains.
Methods
The core contribution is the introduction of Temporal FONDs (TFONDs). TFONDs use Linear Temporal Logic on Finite Traces (LTLf) and its extension, Linear Dynamic Logic on Finite Traces (LDLf), to declaratively specify non-Markovian dynamics. This allows for succinct descriptions of history-dependent effects.
The authors propose a planning approach for TFONDs by reducing the problem to standard Fully Observable Nondeterministic Domains (FONDs). This reduction involves:
- Translating TFONDs to Finite NMFONDs: Non-Markovian FONDs (NMFONDs) are first considered, where history dependency is captured by finite-state transducers. TFONDs are shown to be equivalent to these finite NMFONDs.
- Translating Finite NMFONDs to FONDs: Finite NMFONDs are then converted into equivalent standard FONDs by introducing auxiliary state variables that encode the states of the underlying finite-state transducer. This effectively "Markovianizes" the domain.
- Solving with FOND Planners: The resulting FOND problem, along with a deterministic automaton representing the LTLf/LDLf goal, is then solved using existing, highly optimized FOND planners.
The paper also establishes a connection between TFONDs and Partially Observable Nondeterministic Planning Domains (PONDs), showing that PONDs can be represented by TFONDs that only consider observable variables, simplifying the problem by removing the need to explicitly model unobservable fluents.
Datasets
Not discussed in the paper. The paper focuses on formalisms and algorithms rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- LTLf/LDLf as a powerful language for non-Markovian dynamics: The paper demonstrates that LTLf and LDLf are well-suited for declaratively specifying complex, history-dependent effects in planning domains, offering a more intuitive and compact representation than manually engineered state extensions.
- Bridging the gap between non-Markovian and Markovian planning: The reduction from TFONDs to FONDs is a significant contribution, allowing existing, efficient FOND solvers to be leveraged for a broader class of problems. This is achieved by encoding the relevant history information into auxiliary state variables.
- The complexity of non-Markovian planning: The paper establishes that planning in TFONDs is 2EXPTIME-complete, highlighting the inherent computational cost of dealing with history-dependent dynamics, even when the domain is fully observable. This complexity arises from the need to represent the temporal logic specifications as automata.
- TFONDs as a natural alternative to PONDs: The equivalence shown between TFONDs (using only observable fluents) and PONDs is a key insight. It suggests that TFONDs can provide a cleaner way to model problems that might otherwise require dealing with unobservable states, which can be particularly beneficial for learning models from data.
Key Results
- Planning algorithm for TFONDs: A technique is presented to solve LTLf/LDLf goals in TFONDs by reducing them to standard FOND planning problems.
- Complexity Characterization: Planning for LTLf/LDLf goals in TFONDs is shown to be 2EXPTIME-complete in both the domain and the goal. This is a significant increase in complexity compared to standard FOND planning (which is EXPTIME-complete in the domain and 2EXPTIME-complete in the goal).
- Expressiveness: TFONDs are shown to capture all "finite-state" Non-Markovian Nondeterministic Fully Observable Planning Domains (NMFONDs).
- POND Equivalence: TFONDs (restricted to observable fluents) are shown to be equivalent to Partially Observable Nondeterministic Planning Domains (PONDs), offering a way to model PONDs without explicitly referring to unobservable variables.
Limitations and Future Work
- Complexity: The 2EXPTIME-complete complexity for planning in TFONDs, while theoretically established, might be a practical bottleneck for very large or complex domains.
- PDDL Integration: The paper mentions that directly incorporating PDDL features like "axioms" for derived predicates and automatically deriving persistence specifications would require further study.
- Learning TFONDs: While TFONDs offer a way to model PONDs without unobservable variables, the paper doesn't directly address how to learn TFOND models from data.
- Practical Implications of POND Equivalence: The authors suggest that further study is needed on the practical ramifications of using minimized transducers for PONDs and their corresponding TFOND representations.
Summary updated