🚀 go-pugleaf

From: XIISJSCH@DDATHD21.bitnet
To: mod-ki@unido.informatik.uni-dortmund.de
Date: Mon Apr  1 17:42:58 MSZ 1991
Subject: <mod-ki 0681> Bericht von den kleinen PuK-Workshops
Keywords: Berichte, Planen und Konfigurieren

mod-ki message 0681
************************************************************************
          Bericht von den beiden kleinen Workshops der Fachgruppe
                        "Planen und Konfigurieren"
                             27. Maerz 1991

Ende des vergangenen Jahres fanden die beiden  "kleinen"  Workshops  der
Fachgruppe Planen und Konfigurieren statt. Dieser  Bericht  ueber  diese
Workshops erscheint zugegebenermassen etwas spaet, die Themen sind  aber
nach wie vor aber aktuell.

1. Die "technischen" Daten:
Thema          : Abstraktion (beim           Planen und Logik
                 Planen und Konfigurieren)
Tag            : 19. 11. 1990                3. 12. 1990
Ort            : GMD St. Augustin            TH Darmstadt
Anz. Vortraege : 6                           8
Anz. Teilnehmer: ca. 20                      ca. 30
Folgeaktivit.  : sind keine geplant          sind keine geplant
Organisator    : Alexander Horz              Josef Schneeberger
beteiligte FGn : "Planen und Konfigurieren"  "Planen und Konfigurieren"
                 (FG 1.5.3),                 (FG 1.5.3), "Deduktions-
                                             systeme" (FG 1.2.1) und
                                             "Nichtmonotones Schliessen"
                                             (FG 1.2.2)

Die  Teilnehmerzahl  bei  beiden   Workshops   sollte   moeglichst   auf
25 Personen beschraenkt bleiben, um eine echte Diskussion zu  erreichen.
Wenn auch die Zahl nicht ganz eingehalten werden konnte,  so  waren  die
Diskussionen auf beiden Workshops recht lebhaft. Im folgenden werde  ich
kurz meinen subjektiven Eindruck von den wesentlichen Themen auf  beiden
Workshops wiedergeben.

2.  Workshop "Abstraktion (beim Planen und Konfigurieren)"
2.1 Schwerpunkte der Diskussionen
Da  der  Begriff  der  Abstraktion  im  Umfeld  der  Planerei  und  beim
Konfigurieren   recht   unterschiedlich   benutzt   wird,   wurde   sehr
ausfuehrlich diskutiert, welches  die charakterisierenden  Eigenschaften
von  Abstraktion   sind   (z.B.:   sie   muss   die   Beschreibung   des
Problems/Sachverhalts  vereinfachen,  die  Effizienz  bzw.  Komplexitaet
einer Problemloesung  verbessern  oder  die  wesentlichen  Merkmale  des
Problems muessen erhalten bleiben).  Besondere  Kopfschmerzen  bereitete
die offensichtlich  notwendige  "Zweckgebundenheit"  von  Abstraktionen,
da diese Eigenschaft sehr stark von der jeweiligen Anwendung,  ja  sogar
vom Problem abhaengig ist. So kann man  Zweckgebundenheitheit  etwa  als
Kompelxitaetsreduktion fuer  eine  bestimmte  Problemloesung  auffassen.

Ein weiterer  Begriff,  naemlich  "Aufloesung",  wurde  zur  schaerferen
Eingrenzung des Begriffs Abstraktion betrachtet: Eine andere  Aufloesung
veraendert nur die Schaerfe  der  Information  (d.h.  man  erhaelt  mehr
Information), waehrend der Wechsel einer  Abstraktionsstufe  eine  echte
Veraenderung der verfuegbaren Information bedeutet.

Der Wechsel von einer Ebene auf eine Meta-Ebene  scheint  eine  weitere,
davon verschiedene Variation zu sein.

2.2 Vortraege:
 - A. Horz: Begruessung und Einfuehrung.
 - J. Meyer-Fujara: Aspekte von Granularitaet in wissensbasierten
   Systemen.
 - F. Maedler: Problemzerlegung als optimalitaetserhaltende
   Operatorabstraktion.
 - H. Doerner: Zur Operatorabstraktion des Konfigurierens.
 - J. Weiner und B. Stein: Priorisierung von Anforderungen und
   funktionale Abstraktion.
 - U. Drouven: Abstraktion zur Relaxation von Problemstellungen und zur
   Loesungssuche.
 - Abschlussdiskussion.

2.3 Ein paar Details
A. Horz begruesste die Workshop-Teilnehmer und versuchte als Einfuehrung
eine Charakterisierung der wesentlichen Eigenschaften  von  Abstraktion.
J. Meyer-Fujara  identifizierte  Granularitaet  als  einen  wesentlichen
Aspekt von Abstraktion. Dabei bedeutet  Abstraktion  nicht  nur  Verlust
(Nicht-Unterscheidbarkeit),   sondern   auch   Gewinn   (Struktur)   von
Information. Die  Erhaltung  der  Optimalitaet  eines  Planes  ist  fuer
F. Maedler ein wichtiges Merkmal von Operatorabstraktion. Dabei wird der
Raum der moeglichen Plaene wird durch einige wenige Operatoren  --  sog.
Nadeloehre   (formal   Dedekind-Schnitte)   --   charakterisiert.   Nach
Gespraechen    mit    den    Experten    werden     Hypothesen     ueber
Nadeloehr-Kandidaten  aufgestellt   und   explizit   ueberprueft.   Eine
Konfigurierung kann nach H. Doerner aus der Analyse des  (Design-)Ziels,
der   Beschreibung    elementarer   Zusammenhaenge/Eigenschaften,    der

Komposition  von  Elementarteilen  und  anschliessendem  Test   gewonnen
werden.  Ein  Abhaengigkeitsnetz  kann  dabei  zur  "Serialisierung  von
Teilaufgaben" ausgenutzt werden. U. Drouven charakterisierte Abstraktion
als Problemreduktion, Problemdekomposition  und  Constraint  Relaxation.
Dabei  muss  sich  Abstraktion  intensional  beschreiben   lassen.   Die
Abschlussdiskussion konzentrierte sich noch einmal  auf  die  Festlegung
von charakteristischen Eigenschaften einer Abstraktion. Als  Invarianten
wurden   identifiziert:   Struktur,   Funktion   und    Qualitaet    der
repraesentierten Objekte, als Varianten: die Komplexitaet  des  Problems
oder die  Darstellung  /  Beruecksichtigung  von  Ausnahmen.  Dabei  ist
selbstverstaendlich die Maechtigkeit der Modellierungssprache  relevant.

3. Workshop "Planen und Logik"
3.1 Schwerpunkte der Diskussionen
Ein Thema zog sich als roter Faden durch  die  Diskussionen:  Wie  stark
kann die Ausdrucksmaechtigkeit einer Logik sein,  damit  sie  zum  einen
fuer die Beschreibung von Weltzustaenden  ausreicht,  zum  anderen  fuer
Planungsverfahren  noch  handhabbar  (z.B.  fuer  "Theoriekonstruktion")
bleibt.  Genauer  lautet  die  Frage,  ob  man  sich  gundsaetzlich  auf
Aussagenlogik beschraenken muss. Fuer die Entscheidbarkeit der  Kalkuele
ist das auf jeden Fall von Vorteil und die Implementierungstechniken auf
Seiten des Planers sind auch einigermassen gut verstanden (STRIPS / ATMS
/ TMS). Wenn die Aussagenlogik aber nicht ausdrucksstark genug ist,  wie
sehen  dann  Erweiterungen   aus   bzw.   ist   Modallogik   mit   einer
Repraesentation der Weltzugriffspfade als Terme ein geeigneter Kandidat.

Eng damit verwandt ist die Fragestellung,  ob  es  logische  Formalismen
(Kalkuele)   gibt,   die   fuer   realistische   Probleme    (z.B.   die
Echtzeit-Planung von Flugzeugbewegungen) verwendbar sind.

Ein weiterer Schwerpunkt  -- ein Evergreen bei den Logikern --  war  die
Frage nach der  Semantik  eines  x-beliebigen  (neuen  oder  deduktiven)
Verfahrens zur Planung.

3.2 Vortraege:
 - J. Schneeberger: Kurze Einfuehrung in das Thema des Workshops.
 - C. Weidenbach: Das Planungsproblem aus formal-logischer Sicht.
 - G. Brewka, J. Hertzberg: How To Do Things with Worlds: On Formalizing
   Actions and Plans.
 - G. Grosse: Towards a Theory of Simultaneous Actions.
 - J. Schneeberger: Replanning.
 - B. Fronhoefer: Linear Proofs in a Modal Planning Framework.
 - D. Boehme, J. Theuerkauf: Loesungsansaetze fuer ein Planungssystem
   zur Unterstuetzung von Fluglotsen.
 - R. Rodosek: Ueber eine logische Planungssprache und Anforderungen
   daran.
 - K. Witulski: Planning in a Social System.

Noch mehr Details
C. Weidenbach  stellte  eine   modale   Logik   zur   Formulierung   von
Planungsproblemen  vor.  Die  Abarbeitung  erfolgt  mit  den   bekannten
Uebersetzungsverfahren  und  Theorembeweisern   fuer   Praedikatenlogik.
J. Hertzberg diskutierte den Ansatz des "possible worlds  planning"  von
Ginsberg/Smith und zeigte, dass es dabei Probleme  mit  unvollstaendiger
Information gibt. Er stellt einen Loesungsansatz vor, der  auf  Modellen
statt auf Formelmengen  basiert.  Als  Konsequenz  daraus  ergibt  sich,
dass partielle Weltbeschreibungen in  Planungssystemen  auf  Mengen  von
Grundatomen  beschraenkt  werden  sollten.  G. Grosse  beschrieb   einen
Ansatz, wie synergetische Effekte von  simultanen  Aktionen  beschrieben
werden  koennen   und   zeigte   anhand   eines   Beispiels,   wie   ein
Syntheseverfahren  fuer   solche   Aktionen   angepasst   werden   kann.
J. Schneeberger  diskutierte  die  Behandlung   von   Plandefekten   bei
Plan-Ausfuehrungsfehlern.  B. Fronhoefer  beschrieb  die   Synthese  von
Plaenen  mit  Hilfe  linearer  Konnektionsbeweise  und  diskutierte  die
Erweiterung dieses Ansatzes um eine modale  Formalisierung  der  Formeln
und die Einfuehrung von "Default"-Konnektionen. Eine besonders  lebhafte
Diskussion schloss sich an den Vortrag von D. Boehme  und  J. Theuerkauf
an. Sie beschrieben eine Anwendung des  Planens  auf  die  Fuehrung  des
rollenden  Verkehrs  auf  hochbelasteten   Flughaefen.   Dabei   muessen
innerhalb  sehr  kurzer  Zeitspannen  Plaene  fuer  viele   verschiedene
Flugzeugfuehrer gemacht werden. Zusaetzlich erschwert wird  das  Problem
durch   die   hohe   Dynamik   der    Umgebung    und    die    strengen
Sicherheitsanforderungen. Sie  beschrieben  ein  Architekturkonzept  und
stellten   die    Frage,    ob    klassische    bzw.    logikorientierte
Planungsverfahren  Beitraege  zur  Loesung   dieses   Problems   leisten
koennten.  R. Rodosek  beschrieb  eine  logikorientierte   Sprache   zur
Formalisierung  von   "scheduling"   Problemen   und   K. Witulski   ein
Planungssystem (auf Aussagenlogik) fuer eine Anwendung im Sozialbereich.

Josef Schneeberger
FG Intellektik, FB Informatik, Technische Hochschule Darmstadt
Alexanderstr. 10, D--6100 Darmstadt (Germany)
Phone: +49 (6151) 16-3638, email: xiisjsch@ddathd21.bitnet
************************************************************************