Translating Colored Petri Nets to Lifted Numeric Planning Tasks: Lifted Planning Tasks to Colored Petri Nets
Authors
Lassen, Sebastian ; Ginnerup, Henrik Nørgaard
Term
4. term
Education
Publication year
2024
Submitted on
2024-06-07
Pages
57
Abstract
Colored Petri nets (CPNs) model concurrent systems using tokens that carry data (“colors”). Lifted numerical planning is an AI planning formalism that keeps actions and objects in a variable (lifted) form and includes numeric variables. This thesis connects these two formalisms in both directions. First, it introduces a method to translate general CPNs into lifted numerical planning tasks and provides arguments that the translation preserves the behavior of the original net. Second, it improves an earlier method that translates classical lifted planning tasks into CPNs. Both translations are implemented, their outputs are validated, and they are evaluated against established tools. The CPN-to-planning translation is run with the numeric planner ENHSP and compared to the CPN verification tool TAPAAL. The planning-to-CPN translation is run in TAPAAL and compared to a translation from fully grounded planning tasks and to the Fast Downward planner (lama-first configuration). Results show that the CPN-to-planning approach is generally outperformed by TAPAAL. More importantly, it correctly classifies reachability queries—questions about whether a particular state can be reached—within the limits of the stated theorem, and the thesis proposes a way to remove this limitation. The improved planning-to-CPN translation produces correct results and can now handle a much larger subset of lifted planning tasks, although it remains substantially slower than Fast Downward and the grounded translation.
Farvede Petri-net (CPN’er) er modeller til at beskrive samtidige systemer med tokens, der bærer data ("farver"). Løftede numeriske planlægningsopgaver er en AI-planlægningsformalisme, hvor handlinger og objekter forbliver variable (løftet) i stedet for at blive fuldt udfoldet, og hvor talværdier indgår. Denne afhandling forbinder de to formaliser i begge retninger. For det første præsenteres en metode til at oversætte generelle CPN’er til løftede numeriske planlægningsopgaver, sammen med argumenter for, at oversættelsen bevarer nettets adfærd. For det andet forbedres en tidligere metode, der oversætter klassisk løftet planlægning til CPN. Begge oversættelser er implementeret, deres output er valideret, og de er afprøvet mod etablerede værktøjer. Oversættelsen fra CPN til planlægning køres med den numeriske planner ENHSP og sammenlignes med CPN-verifikationsværktøjet TAPAAL. Oversættelsen fra planlægning til CPN køres i TAPAAL og sammenlignes med en oversættelse fra fuldt grundede planlægningsopgaver og med planlægningssystemet Fast Downward (lama-first-konfigurationen). Resultaterne viser, at CPN-til-planlægning generelt klarer sig dårligere end TAPAAL. Vigtigere er dog, at den korrekt klassificerer nåbarhedsspørgsmål—om en bestemt tilstand kan nås—inden for begrænsningen i den formulerede sætning, og afhandlingen foreslår en løsning til at fjerne denne begrænsning. Den forbedrede planlægning-til-CPN-oversættelse giver korrekte resultater og kan nu håndtere en langt større delmængde af løftede planlægningsopgaver, selv om den stadig er væsentligt langsommere end Fast Downward og den grundede oversættelse.
[This apstract has been rewritten with the help of AI based on the project's original abstract]
Keywords