Logikprogrammierung mit ASP: CMT304 Assignment Leitfaden

Einführung in die Logikprogrammierung mit ASP

Die Logikprogrammierung ist ein mächtiges Paradigma, das auf deklarativen Aussagen basiert. Anders als bei imperativen Sprachen wie Python oder Java beschreibst du was gelöst werden soll, nicht wie. Answer Set Programming (ASP) ist eine moderne Variante, die besonders für kombinatorische Optimierungsprobleme geeignet ist – ähnlich wie bei der Planung von Lieferketten oder der Terminvergabe in grossen Unternehmen. Im CMT304 Modul lernst du, wie du solche Probleme elegant modellierst.

Das Patentzuweisungsproblem verstehen

Stell dir vor, du bist beim Deutschen Patent- und Markenamt (DPMA) und musst Patentanmeldungen an Gutachter verteilen. Jeder Gutachter gibt für jede Anmeldung eine Expertise ab: Expert, Knowledgeable, Familiar oder Inexpert. Dein Ziel ist es, jede Anmeldung genau einem Gutachter zuzuweisen, unter Berücksichtigung von:

Ausgeglichene Arbeitslast (maximale Differenz m)
Maximal k Familiar-Zuweisungen pro Gutachter
Minimierung von Inexpert-Zuweisungen
Maximierung von Expert-Zuweisungen

Dieses Problem ähnelt der Matching-Problematik bei der Vergabe von Studienplätzen oder der Ressourcenplanung in der Cloud – aktuelle Themen, die auch 2026 relevant sind.

ASP Grundlagen: Fakten, Regeln und Constraints

Ein ASP-Programm besteht aus Fakten, Regeln und Constraints. Fakten sind gesicherte Wahrheiten, z.B. bid(ref, req, exp). Regeln leiten neue Wahrheiten ab, z.B. assign(R, Q) :- bid(R, Q, _). Constraints schränken gültige Lösungen ein, z.B. :- assign(R, Q1), assign(R, Q2), Q1 != Q2 (ein Gutachter kann nicht zwei Anmeldungen gleichzeitig haben – aber hier ist es genau eine pro Anmeldung).

Guess-and-Test Methodik

ASP folgt dem Guess-and-Test-Ansatz: Zuerst wird eine mögliche Lösung „geraten“ (choice rules), dann wird getestet, ob alle Bedingungen erfüllt sind (constraints). Zum Beispiel: {assign(R, Q)} :- bid(R, Q, _) bedeutet, dass jede Zuweisung eine Option ist. Dann prüfen Constraints, ob jede Anmeldung genau einmal zugewiesen wird.

Schritt-für-Schritt Encoding des Problems

1. Eingabe und Parameter

Die Eingabe besteht aus Fakten bid(ref, req, exp) und den Parametern n (Anzahl Gutachter), m (maximale Arbeitslastdifferenz) und k (maximale Familiar-Zuweisungen). Diese werden als Fakten übergeben, z.B. param(n, 3). param(m, 1). param(k, 1).

2. Choice Rule für Zuweisungen

Wir definieren: Jede Anmeldung muss genau einem Gutachter zugewiesen werden. Dazu eine Choice Rule:

{assign(R, Q)} :- bid(R, Q, _).

Zusätzlich: Jede Anmeldung erhält genau eine Zuweisung:

:- not 1 { assign(R, Q) : bid(R, Q, _) } 1.

Dies stellt sicher, dass jede Anmeldung genau einmal vorkommt.

3. Arbeitslast-Constraints

Wir berechnen die Arbeitslast jedes Gutachters:

workload(R, N) :- N = #count{ Q : assign(R, Q) }.

Dann: Die Differenz zwischen maximaler und minimaler Arbeitslast darf m nicht überschreiten:

max_load(Max) :- Max = #max{ N : workload(_, N) }.
min_load(Min) :- Min = #min{ N : workload(_, N) }.
:- max_load(Max), min_load(Min), Max - Min > M.

Dabei ist M der Parameter m.

4. Familiar-Begrenzung

Zähle, wie oft ein Gutachter Familiar zugewiesen bekommt:

familiar_count(R, C) :- C = #count{ Q : assign(R, Q), bid(R, Q, familiar) }.

Constraint:

:- familiar_count(R, C), C > K.

K ist der Parameter k.

5. Optimierung: Expert maximieren, Inexpert minimieren

Wir verwenden #maximize und #minimize:

#maximize { 1, R, Q : assign(R, Q), bid(R, Q, expert) }.
#minimize { 1, R, Q : assign(R, Q), bid(R, Q, inexpert) }.

ASP sucht dann nach Answer Sets, die diese Optimierungskriterien erfüllen.

Vollständiges Programm (problem_encoding.lp)

Hier ein minimales Beispiel, das die Struktur zeigt:

% Eingabe: bid(ref, req, exp), param(n,m,k)
% Wahl: jede Anmeldung genau einem Gutachter
{assign(R, Q)} :- bid(R, Q, _).
:- not 1 { assign(R, Q) : bid(R, Q, _) } 1.

% Arbeitslast
workload(R, N) :- N = #count{ Q : assign(R, Q) }.
max_load(Max) :- Max = #max{ N : workload(_, N) }.
min_load(Min) :- Min = #min{ N : workload(_, N) }.
:- max_load(Max), min_load(Min), Max - Min > M.

% Familiar-Begrenzung
familiar_count(R, C) :- C = #count{ Q : assign(R, Q), bid(R, Q, familiar) }.
:- familiar_count(R, C), C > K.

% Optimierung
#maximize { 1, R, Q : assign(R, Q), bid(R, Q, expert) }.
#minimize { 1, R, Q : assign(R, Q), bid(R, Q, inexpert) }.

Dokumentation und Nutzung

Das Programm wird mit einem ASP-Solver wie clingo ausgeführt. Aufruf: clingo problem_encoding.lp input.lp. Die Eingabedatei enthält die Fakten. Die Ausgabe sind alle optimalen Answer Sets.

Häufige Fehler vermeiden

Vergiss nicht, die Parameter als Fakten zu definieren.
Achte auf korrekte Syntax: Punkte am Ende jeder Regel.
Teste mit kleinen Beispielen, um die Logik zu überprüfen.

Beispiel aus der Praxis: Schulstundenplanung

Stell dir vor, du planst den Stundenplan einer Schule (ein Trendthema 2026 durch KI-gestützte Planung). Lehrer geben ihre Expertise für Fächer an. Die Bedingungen sind ähnlich: gleiche Anzahl Stunden pro Lehrer, maximale Anzahl bestimmter Fächer. ASP eignet sich hervorragend, um solche Probleme deklarativ zu lösen.

Fazit

Logikprogrammierung mit ASP ist ein mächtiges Werkzeug für komplexe Zuordnungsprobleme. Mit dem Guess-and-Test-Ansatz und Optimierungsdirektiven kannst du effiziente Lösungen finden. Nutze dieses Wissen für dein CMT304 Assignment und darüber hinaus – ob für Patentämter, Cloud-Ressourcen oder Schulplanung.