Top-k Non Operator-Group Dominated Plans Using Symbolic Search
Authors
Kettunen, Thomas Klinke ; Starup, Magnus Bindesbøl
Term
4. term
Education
Publication year
2026
Submitted on
2026-06-03
Pages
14
Abstract
Planning tasks aim to find a sequence of actions that reaches a goal at the lowest possible cost. Top-k planning looks for the k cheapest plans but often returns many that feel redundant, such as reorderings of the same actions or plans with unnecessary steps. Prior work has explored ways to handle this redundancy, including the Top-k Non Operator-Group Dominated problem, which groups equivalent operators (actions) and rules out reorderings and redundant operators within those groups. The existing solution uses an iterative process of optimal planning and task reformulation. We propose an alternative based on symbolic search, which preserves information about the state space throughout the search. We implement the algorithm and evaluate it on a wide range of planning tasks to compare its performance to the iterative approach and to examine how factors like the value of k and the number of groups affect performance.
Planlægningsopgaver handler om at finde en sekvens af handlinger, der når et mål til lavest mulig omkostning. Top-k planlægning søger de k billigste planer, men rapporterer ofte mange, der virker redundante, f.eks. omrokeringer af de samme handlinger eller planer med unødige trin. Tidligere har man foreslået metoder til at håndtere sådan redundans, bl.a. problemet Top-k Non Operator-Group Dominated, som grupperer ækvivalente operatorer (handlinger) og udelukker omrokeringer og redundante operatorer inden for grupperne. Den hidtidige løsning bruger en iterativ proces med optimal planlægning og reformulering af opgaven. Vi foreslår en alternativ tilgang baseret på symbolsk søgning, som bevarer information om tilstandsrum gennem hele søgningen. Vi implementerer algoritmen og evaluerer den på en bred vifte af planlægningsopgaver for at sammenligne ydeevnen med den iterative tilgang og undersøge, hvordan faktorer som værdien af k og antallet af grupper påvirker ydeevnen.
[This apstract has been rewritten with the help of AI based on the project's original abstract]
Keywords