Beyond Exhaustive Search Rule Learning with Informed Search
Authors
Jakobsen, Frederik Langkilde ; Bohnstedt, Rune ; Droob, Alexander
Term
4. term
Education
Publication year
2024
Submitted on
2024-06-07
Abstract
Klassisk planlægning er et centralt problem i kunstig intelligens: at bestemme en rækkefølge af handlinger, der fører til et mål. Når antallet af mulige handlinger og tilstande stiger, eksploderer antallet af muligheder, og udtømmende søgning bliver upraktisk. Denne afhandling præsenterer Beyond Exhaustive Search (BES), en metode der lærer at klassificere handlinger i et planlægningsproblem som lovende ("gode") eller mindre nyttige ("dårlige"). Målet er at fokusere søgningen og undgå at udforske muligheder, der sandsynligvis ikke fører til en løsning. BES tilpasser Induktiv Logikprogrammering (ILP)—en form for maskinlæring, der udleder logiske regler ud fra eksempler—og bruger POCL‑grafer (partial order causal link), som beskriver kausale forbindelser og delvis rækkefølge i planer, til at udvinde ekstra viden fra allerede løste planlægningsproblemer. Kandidatregler vurderes med et relationalt databasehåndteringssystem (RDBMS), og de endelige klassifikatorer bygges som beslutningstræer ved hjælp af STreeD, et rammeværk der konstruerer små, optimale binære beslutningstræer. Eksperimenter viser, at BES opnår resultater på niveau med det førende ILP‑værktøj Aleph og dets forgænger YAPHG, og at det kan producere modeller i tilfælde, hvor både Aleph og YAPHG ikke kan. Selvom integration af BES i planlægningssystemer stadig mangler at blive undersøgt, peger de lovende forudsigelsesevner på praktiske anvendelser, f.eks. til at styre delvis instansiering (partial grounding) og andre planlægningsopgaver.
Classical planning is a core problem in artificial intelligence: deciding a sequence of actions that leads to a goal. As the number of possible actions and states grows, the space of possibilities explodes, making exhaustive search impractical. This thesis presents Beyond Exhaustive Search (BES), a method that learns to classify actions in a planning problem as promising ("good") or unhelpful ("bad"). The aim is to focus the search and avoid exploring options that are unlikely to lead to a solution. BES adapts Inductive Logic Programming (ILP)—a machine learning approach that induces logical rules from examples—and uses partial order causal link (POCL) graphs—representations of causal connections and partial ordering in plans—to extract additional knowledge from solved planning problems. It evaluates candidate rules with a relational database management system (RDBMS) and builds the final classifiers as decision trees using STreeD, a framework that constructs small, optimal binary decision trees. Experiments show that BES achieves results comparable to the state-of-the-art ILP tool Aleph and its predecessor YAPHG, and it can produce models in cases where both Aleph and YAPHG fail. While integrating BES directly into planning systems remains future work, its predictive capabilities suggest practical uses, such as guiding partial grounding (deciding which action instances to consider) and other planning tasks.
[This summary has been rewritten with the help of AI based on the project's original abstract]
Documents