Reward machines (RMs) inform reinforcement learning agents about the reward structure of the environment, enabling support for non-Markovian tasks and improving sample efficiency.However, learning with RMs is ill-suited for long-horizon problems where subtasks can be completed in any order.In such cases, the amount of information to learn increases exponentially with the number of unordered subtasks.We address this issue by introducing three generalisations of RMs: (1) Numeric RMs allow users to express complex tasks in a compact form. (2) In agenda RMs, states are associated with an agenda that tracks the remaining subtasks to complete. (3) Coupled RMs have coupled states associated with each subtask in the agenda.In addition, we introduce QCoRM, a new task-decomposition Q-learning-based algorithm that leverages coupled RMs and preserves global optimality guarantees in tabular settings.Our experiments across four domains---featuring both discrete and continuous action and state spaces---demonstrate that QCoRM scales better than baseline algorithms for long-horizon problems with unordered subtasks.

Recent work on learning for classical planning has primarily focused on exclusively employing the learned heuristics or policies. However, no purely learning-based method has consistently outperformed state-of-the-art planners to date. To address this, we return to the research paradigm that integrates learned domain knowledge with traditional, non-learned planning techniques. We propose a novel and simple approach for learning transition classifiers, using tree-based statistical learning over description logic features. In experiments, we evaluate various strategies for integrating learned classifiers with the FF heuristic, a state-of-the-art non-learned heuristic. Our results demonstrate that augmenting classical heuristics with transition classifiers leads to substantial performance improvements. The strongest variant combines classifier-based lookahead search with learned knowledge to avoid transitions into unsolvable states, frequently outperforming state-of-the-art traditional and learning-based planners.

The Beluga Challenge, recently organized by the Tuples con-sortium, offered a track on explainable planning (XAIP), to the best of our knowledge the first XAIP competition to date. Within the setting of the Beluga logistics domain, participantswere given a planning task and a plan, and were supposed toanswer a query to explain to a human expert certain choices made in the plan. The queries ask about particular state atomsthat were achieved and alternatives “why achieve this atom A instead of that atom B?”, action reordering “can I do A before B instead?”, or about the consequences of object removal “what happens if we forbid to use object X?”. In this work, we propose counterfactual reasoning to come up with explanations that answer these queries. We design task reformulations, modifications that alter the input planning task, such that the solutions for the modified task allow to explain the choices made in the initial plan. Our framework generalizes the queries posed in the Beluga challenge. To obtain textual explanations, we employ a large language model (LLM) that allows our system to be used without planning-specific knowledge. We empirically show that solving the modifiedtask is similarly hard as finding a plan for the original task,showing that our approach is efficient for practical usage.

Saturated cost partitioning (SCP) is one of the strongest methods for admissibly combining heuristics for optimal classical planning. The quality of an SCP heuristic depends heavily on the order in which its component heuristics are considered. For high accuracy, it is essential to maximize over multiple SCP heuristics computed using different component orders. However, for n component heuristics, even enumerating all n! orders is usually infeasible. Consequently, previous work resorted to using greedy algorithms and local optimization. In contrast, we present the first practical method for computing the perfect SCP heuristic that is equivalent to considering all component orders. We show that a set of SCP heuristics forms an additive disjunctive heuristic, which allows us to concisely represent component orders as a directed acyclic graph. Furthermore, once certain components have been considered, the order of the remaining components often becomes irrelevant. By exploiting this characteristic, we can reduce the size of the heuristic representation by several orders of magnitude in practice. Finally, our work makes it possible to compare the quality of existing SCP methods with that of the perfect SCP heuristic, revealing that existing approximations are nearly optimal for standard benchmarks.

One key decision for heuristic search algorithms is how tobalance exploration and exploitation. In classical planning,novelty search has come out as the most successful approachin this respect. The idea is to favor states that contain previ-ously unseen facts when searching for a plan. This is done bymaintaining a record of the tuples of facts observed in previ-ous states. Then the novelty of a state is the size of the small-est previously unseen tuple. The most successful version ofnovelty search is best-first width search (BFWS), which com-bines novelty measures with heuristic estimates. An orthog-onal approach to balance exploration-exploitation is to useseveral open-lists. These open-lists are ordered using differ-ent heuristic estimates, which diversify the information usedin the search. The search algorithm then alternates betweenthese open-lists, trying to exploit these different estimates.This is the approach used by LAMA, a classical planner that,a decade after its release, is still considered state-of-the-artin agile planning. In this paper, we study how to combineLAMA and BFWS. We show that simply adding the strongestopen-list used in BFWS to LAMA harms performance. How-ever, we show that combining only parts of each planner leadsto a new state-of-the-art agile planner.

Multiple Sequence Alignment (MSA) is a fundamental prob-lem in computational biology that is used to understand theevolutionary history of protein, DNA, or RNA sequences. Anoptimal alignment for two sequences can efficiently be foundusing dynamic programming, but computing optimal align-ments for more sequences continues to be a hard problem. Acommon method to solve MSA problems is A∗ search with admissible heuristics, computed from subsets of the input se-quences. In this paper, we consider MSA from the perspectiveof cost partitioning and relate the existing heuristics for MSAto uniform cost partitioning and post-hoc optimization, twowell-known techniques from the automated planning litera-ture. We show that the MSA heuristics are bounded by uni-form cost partitioning and that post-hoc optimization yieldsstrictly dominating heuristics. For a common benchmark setof protein sequences and a set of DNA sequences, we showthat the theoretical dominance relations between the heuris-tics carry over to practical instances

Multiple Sequence Alignment (MSA) is a fundamental problem in computational biology that is used to understand the evolutionary history of protein, DNA, or RNA sequences. An optimal alignment for two sequences can efficiently be found using dynamic programming, but computing optimal alignments for more sequences continues to be a hard problem. A common method to solve MSA problems is A* search with admissible heuristics, computed from subsets of the input sequences. In this paper, we consider MSA from the perspective of cost partitioning and relate the existing heuristics for MSA to uniform cost partitioning and post-hoc optimization, two well-known techniques from the automated planning literature. We show that the MSA heuristics are bounded by uniform cost partitioning and that post-hoc optimization yields strictly dominating heuristics. For a common benchmark set of protein sequences and a set of DNA sequences, we show that the theoretical dominance relations between the heuristics carry over to practical instances.