The papers Temporal Task And Motion Planning with Metric Time for Multiple Object Navigation, by Elisa Tosello, Alessandro Valentini and Andrea Micheli, and Automatic Selection of Macro-Events for Heuristic-Search Temporal Planning by Alessandro La Farciola, Alessandro Valentini and Andrea Micheli was accepted for the 39th Annual AAAI Conference on Artificial Intelligence.
Temporal Task And Motion Planning with Metric Time for Multiple Object Navigation
Abstract: Integrating metric time into Task And Motion Planning (TAMP) is challenging, especially with simultaneous object motion. Existing work focuses on classical and numeric TAMP, not considering deadlines, motions overlapping in time, and other temporal constraints. In this paper, we fill this gap by formalizing Temporal Task and Motion Planning (TTAMP) for multi-object navigation. We propose a novel interleaved planning technique for this problem, which leverages incremental Satisfiability Modulo Theory to ensure efficient reasoning on deadlines and action duration coupled with a motion planner supporting simultaneous object motion. Geometric data on encountered obstacles prunes unreachable symbolic regions, while temporal bounds limit the geometric search space. For multiple moving objects, our algorithm contextualizes the conflicts learned from the motion planner on overlapping actionsgit so that entire classes of temporal plans are pruned from the search space of the task planner, ensuring the eventual termination of the interplay. We provide a comprehensive benchmark suite and demonstrate the effectiveness of our solver in leveraging these scenarios.
Automatic Selection of Macro-Events for Heuristic-Search Temporal Planning
Abstract: One of the major techniques to tackle temporal planning problems is heuristic search augmented with a symbolic representation of time in the states. Adding composite actions (macro-actions) to the problem is a simple and powerful approach to create ``shortcuts'' in the search space, at the cost of increasing the branching factor of the problem and thus the execution time of a heuristic search planner. Hence, it is of paramount importance to select the right macro-actions and minimize their number to optimize the planner performance. In this paper, we introduce "macro-events": a simple, yet powerful, "shortcut" model similar to macro-actions for the case of temporal planning. Then, we present a novel ranking function to extract and select a suitable set of macro-events from a dataset of valid plans. In our ranking approach, we consider an estimation of the hypothetical search space for a blind search under four different exploitation schemata. Finally, we experimentally demonstrate that the proposed approach yields a substantial performance improvement for a state-of-the-art temporal planner.