TL;DR
This paper introduces the first method for automatically generating flexible temporal plans (Temporal Planning Networks or TPNs) from standard temporal planning problems. By merging diverse plans generated by a novel temporal diverse planner, they create compact TPNs that can handle uncertainty in real-world robotic applications, making TPN-based systems more practical.
What Problem Does This Paper Address?
Robots operating in dynamic environments, especially alongside humans, face significant uncertainty. While completely ignoring uncertainty is dangerous and accounting for all possibilities is computationally infeasible, a middle ground is using "flexible plans with choices." Temporal Planning Networks (TPNs) are a formalism for such plans, allowing a system to make decisions at runtime to adapt to unfolding events. However, a major hurdle has been the manual effort required to construct these TPNs, often needing domain experts. This paper aims to automate this TPN generation process, making flexible planning more accessible.
Methods
The authors propose a two-stage approach:
- Diverse Temporal Planning: They first adapt an existing diverse planning method (based on top-k planning) to the temporal domain. This involves defining a "Temporal Plan Skeleton" (TPS) which captures the sequence of events in a plan, independent of their exact timing. They then develop a temporal plan elimination formulation to generate multiple plans with distinct TPSs.
- Merging Diverse Plans into a TPN: Once a set of diverse plans (and their TPSs) is obtained, the core challenge is to merge them into a single, compact TPN. They start with a "naive" TPN where each diverse plan is a separate branch. Then, they identify compatible time points (events) across different plans. Compatibility is defined based on whether executing the remainder of one plan's sequence from the other's state can still achieve the goal (fully or semi-compatible). Finally, they formulate this merge selection as a Constraint Optimization Problem (COP) to maximize the number of merges, thereby minimizing the TPN's size and complexity.
Datasets
The authors evaluated their approach on domains from the temporal track of the International Planning Competition (IPC) in 2011, 2014, and 2018. They excluded domains with actions whose durations depend on the current state, as their TPN formalism doesn't support this. They also extended their method to work with classical planning instances by requiring users to specify action durations.
Key Insights and Ideas
- Temporal Plan Skeleton (TPS) is Key: Recognizing that temporal plans differ not just in timing but in the sequence of events is crucial. Defining a TPS allows for a meaningful notion of "diversity" in temporal planning, analogous to diverse classical plans.
- Merging for Compactness: The core idea is that by merging compatible points across different plans, we can create a single, more compact representation (TPN) that implicitly covers multiple execution paths. This is more efficient than having separate plans for every possibility.
- Compatibility as a Foundation for Merging: Defining "full" and "semi" compatibility between events from different plans provides a principled way to identify potential merge points. This moves beyond simple state-space comparisons, which can be brittle.
- COP for Optimal Merging: Framing the merge selection as a Constraint Optimization Problem allows for systematically finding the best set of merges to maximize compactness, balancing the desire for many merges with the computational cost.
Key Results
- The proposed method can automatically generate TPNs from temporal planning problems.
- The generated TPNs are significantly more compact than the "naive" TPNs that simply branch out for each diverse plan. For example, in Table 2, compactness values range from 0.03 to 0.72, indicating substantial size reduction.
- The approach scales well, generating TPNs that generalize the set of plans they were derived from.
- The empirical evaluation showed varying success rates depending on the chosen parameters (number of diverse plans
k, compatibility type, and transitivity rules), but generally demonstrated the feasibility of the approach.
Limitations and Future Work
- Controllable TPNs Only: The current work focuses on generating TPNs with only controllable decisions. Future work aims to address uncontrollable decisions (e.g., from human actions or environment changes) by generating TPNUs (Temporal Planning Networks under Uncertainty).
- Domain-Specific Action Durations: For classical planning instances, the method requires users to specify action durations. If not provided, it defaults to duration 1, which might not reflect real-world scenarios.
- Optimality of TPN Size: While the COP aims to maximize merges, the authors acknowledge that their technique is not necessarily optimal in terms of TPN size.
- Human-Centric Metrics: Future work could optimize for metrics beyond just TPN size, such as ease of explanation to humans, mental effort for human counterparts, or flexibility for human input.
- Handling Dynamic Durations: The current TPN formalism does not support actions whose durations depend on the current state, limiting its applicability in some domains.
Summary updated