Using Multi-Objective Methods on Single-Objective Planning with Operator Grouping
Authors
Leemet, Lauri ; Larsen, Lucas Martin
Term
4. term
Education
Publication year
2026
Abstract
This thesis addresses how to efficiently produce multiple meaningfully different plans in classical planning without spending effort on redundant variants. Prior work used operator groups and a Forbid Iterative (FI) scheme to generate plans that are non-dominated in group counts, but this required restarting search and reformulating the task after each plan. We instead recast the problem as multi-objective planning by turning each operator group into its own objective, so the target set of plans corresponds to the Pareto-optimal front. We implement a translation to MO Group Tasks within an existing multi-objective planner and evaluate on optimal STRIPS benchmarks. Compared to FI, the MO approach achieves slightly higher coverage, and we observe tasks where one planner solves quickly while the other fails to solve at all. A runtime analysis indicates that, unlike in multi-objective shortest-path on explicit graphs, dominance checking is not a major bottleneck; most time is spent computing heuristic values and expanding nodes. Varying the cost function (objective order and how original cost is incorporated) does not materially change coverage but can alter the time and expansions needed for the first solution. Finally, we explore focal search for MO tasks in two variants: a simple heuristic-sorted focal list slightly reduces expansions with low overhead, while a non-dominated-only focal list reduces expansions more at the cost of significant overhead. Overall, translating operator grouping into multi-objective planning provides a practical way to compute diverse, non-dominated plans and yields a modest coverage improvement over FI in our tests.
Denne afhandling undersøger, hvordan man effektivt genererer flere meningsfuldt forskellige planer i klassisk planlægning uden at spilde tid på redundante variationer. Tidligere arbejde brugte operatørgrupper og en iterativ Forbid Iterative (FI)-tilgang til at finde planer, der ikke domineres i antallet af anvendte grupper, men denne metode medførte gentagne genstarter af søgningen og omformuleringer af opgaven. Her omformuleres problemet i stedet som multiobjektiv planlægning, hvor hver operatørgruppe bliver et separat mål, så de ønskede planer svarer til den Pareto-optimale mængde. Vi implementerer en oversættelse til MO Group Tasks i en eksisterende multiobjektiv planner og evaluerer på optimale STRIPS-benchmarks. Sammenlignet med FI opnår MO-tilgangen en lidt højere dækning, og vi ser opgaver, hvor den ene planner er hurtig, mens den anden slet ikke løser opgaven. En runtime-analyse viser, at dominanstjek ikke er den dominerende tidsfaktor i MO-planlægningsopgaver; tiden går primært til heuristikberegninger og nodeudvidelser. Ændringer i omkostningsfunktionen (rækkefølge af mål og inddragelse af den oprindelige omkostning) påvirker ikke dækningen væsentligt, men kan ændre tiden og antallet af udvidelser til den første løsning. Endelig afprøver vi fokalsøgning i MO-søgning med to varianter: en enkel variant reducerer udvidelserne en smule med lav tids-overhead, mens en variant, der begrænser fokal-listen til ikke-dominerede noder, reducerer udvidelserne mere på bekostning af en markant tids-overhead. Samlet set viser arbejdet, at oversættelsen til multiobjektiv planlægning er en praktisk måde at finde diverse, ikke-dominerede planer på, med en beskeden forbedring i dækning i forhold til FI.
[This apstract has been generated with the help of AI directly from the project full text]