Archived Website: This website is a static snapshot for archival purposes only. It is no longer maintained or updated.

planner.plannertypes
Class PlannerTypeC

java.lang.Object
  |
  +--java.lang.Thread
        |
        +--planner.Planner
              |
              +--planner.plannertypes.PlannerTypeC
public class PlannerTypeC
extends Planner

Der PlannerTypeC ist eine GraphPlan-Variante, die Pl?ne f?r dynamische Objektwelten erzeugt und STRIPS-Operatoren mit disjunktiven Nachbedingungen erlaubt.

Planungsstrategie:
GraphPlan (GP) (siehe Blum and Furst, 1997) gilt derzeit als einer der schnellsten Planner-Algorithmen f?r STRIPS-beschr?nkte klassische Planungsdom?nen. Bei der Adaption dieses Ansatzes f?r die Suche im Web mussten insbes. zwei Probleme gel?st werden:

  1. Die Objektwelt ist nicht mehr endlich und statisch, sondern dynamisch. Jede w?hrend einer Suche neu hinzukommende URL erweitert die Objektwelt.
  2. F?r klassische, in ihren Vorbedingungen erf?llte STRIPS-Operatoren kann Ausf?hrbarkeit nicht garantiert werden. Suchmachinenanfragen k?nnen fehlschlagen oder zu unerwarteten Ergebnissen f?hren, so dass die Nachbedingungen nicht erreicht werden.
F?r die vorliegende GP-Variante PG343-GP wurden folgende L?sungsans?tze entwickelt:
  1. Ist in der Signatur eines Operator (genauer: f?r ein PredArgument innerhalb der Operator-Postcondition) vermerkt, dass dieser bei seiner Ausf?hrung "ein neues Objekt in die Welt setzen wird", so kann GraphPlan schon zum Planungszeitpunkt (wo nur der Objekttyp, aber nicht das konkrete neue Objekt bekannt ist) dieses "virtuelle" Objekt verwalten und einbeziehen.
  2. Mehrere, disjunktiv verkn?pfte Operator-Nachbedingungen sind zugelassen, so dass bei unsicheren, schwerer abzusch?tzenden Operationen mehrere Nachbedigungsf?lle ber?cksichtigt werden k?nnen. Der GP-PG343 betrachtet einen Operator mit m Nachbedingungen intern als m Operatoren, von denen der i-te Operator (1 <= i="i" <="<" auf="auf" die="die" i-te="i-te" Nachbedingung="Nachbedingung" abzielt.="abzielt." Durch="Durch" diese="diese" interne="interne" Operatatorinterpretation="Operatatorinterpretation" greift="greift" der="der" ?bliche="?bliche" GP-Algorithmus.="GP-Algorithmus." />L>



Thread-Funktinalit?t und Eventhandling:
Siehe Ausf?hrungen in Planner.

Version:
2.0 [99-12-19]
Author:
Christian Fischbach
See Also:
Planner, PlanExecution, Operator

Field Summary
private  java.util.LinkedList bestOpsLL
          LinkedList der Operatoren nach Gewichtung
private  boolean couldExecOnePlan
          speichert, ob mind.
private static int dynWorldObjectsCounter
          Counter f?r Anzahl der dynamisch erzeugten "virtuellen" Weltobjekte.
private  Level graphExpansionLevel
          Planning Graph level, das gerade expandiert wird (Propositon- oder Actionlevel).
static Operator noOp
          Alle Propositionen des PLevel P_i werden durch noOps im ALevel A_i ins PLevel P_{i+1} ?bertragen.
private static int planExecuteFinishedEvent
          int Konstante fuer Event planExecuteFinishedEvent Fuer Gesamtuebersicht siehe Planner.
private static int planReadyFinishedEvent
          int Konstante fuer Event planReadyFinishedEvent F?r Gesamt?bersicht siehe Planner.
(package private)  Operator targetMatchOp
          Operator zur Ueberpr?fung, ob das Ziel bereits erreicht ist.
 
Fields inherited from class planner.Planner
alreadyCalledEval, destroyThread, planInfo, plannerID, planReadyAborted, searchID, suspended
 
Fields inherited from class java.lang.Thread
contextClassLoader, daemon, eetop, group, inheritedAccessControlContext, initial_stack_memory, MAX_PRIORITY, MIN_PRIORITY, name, NORM_PRIORITY, priority, PrivateInfo, single_step, stillborn, stopThreadPermission, target, threadInitNumber, threadQ, values
 
Constructor Summary
PlannerTypeC(PlanInformation planInfo)
          Konstruktor des Planers.
 
Method Summary
private  boolean aNodePlan2PlanTree(java.util.LinkedList aNodePlan)
          Generiert aus dem uebergebenen aNodePlan einen entsprechenden PlanTree.
private  boolean checkPropositionExclusivity(PNode p0, PNode p1)
          Markiert zwei Propositionen p0, p1 als "wechselseitig exklusiv", falls in A_{i-1} alle p0-erzeugenden Aktionen "wechselseitig exklusiv" mit allen p1-erzeugenden Aktionen sind.
private  boolean compeetingNeedsActions(ANode a0, ANode a1)
          "Compeeting Needs"-Test fuer zwei Aktionen a0 und a1.
private  void createNextActionLevel()
          Erweitert den planningGraph um das n?chste Actionlevel (ALevel).
private  void createNextPropositionLevel()
          Erweitert den Planning Graph um das n?chste Proposition-Level (PLevel).
private  ANode createNoOp4PNode(PNode pNode)
          Erzeugt f?r ?bergebenen ANode aus PLevel P_i noOp f?r ALevel A_i.
 PlanInformation eval()
          PG343-Graphplan
private  boolean expandPlanningGraph()
          Versucht, den Planning Graph um ein Action- und ein Proposition-Level zu expandieren.
private  boolean extractSolution()
          R?ckw?rtssuche im PlanningGraph nach einem g?ltigen Plan.
private  boolean findALevelSolutions4Goals(java.util.ListIterator[] goalAddingActionsLI, java.util.LinkedList[] goalAddingActionsLL, int goal2AchieveIndex, PLevel currentPLevel, java.util.LinkedList solLL)
          Sucht fuer ein Array von P_i-Propositionen (=goals) alle Mengen von A_{i-1} Aktionen, die wechselseitig nicht exklusiv sind und die diese Propositionen (=goals) adden, also alle A_{i-1}-Level L?sungen.
private  void getBestOps()
          Liest aus der OperatorDB die Operatoren nach Gewichtung sortiert aus.
private  boolean goalSetCreationStep(PNode[] goals, PLevel currentPLevel, java.util.LinkedList solLL)
          Sucht rekursiv f?r goals aus P-Level P_i des Planning Graph in R?ckw?rtsrichtung nach A-Level A_{i-1} L?sungen.
private  boolean graphHasLeveledOff()
           
private  boolean graphHasReachedMaxLevel()
          Testet, ob der Planning Graph die maximale Anzahl von Leveln erzeugt hat.
static int incDynWorldObjectsCounter()
          Inkrementiert den Z?hler dynWorldObjectsCounter.
private  void initializePlanningGraph()
          Initialisiert den Planning Graph, i.e.
private  boolean interferenceActions(ANode a0, ANode a1, boolean oneDirectionChecked)
          "Interference"-Test fuer zwei Aktionen a0 und a1.
private  java.util.LinkedList pNodeMatches4Op(java.util.ListIterator[] pNodesLI, java.util.LinkedList[] pNodesLL, Operator theOp, int itLevel)
          findet fuer den uebergebene Operator alle PNodes-Mengen, von denen jede die op-Preconditions matcht und deren Elemente nicht mutual exclusiv sind.
private  Predicate proposMatchesPrecond(Predicate propos, Predicate precond)
          versucht, die Operator Precondition precond mit der Proposition propos zu matchen.
 void run()
          ?berschriebene Thread-Methode run.
protected  void triggerEvent(int eventIntId)
          Triggert abhaengig vom uebergebenen int eventIntId den entsprechenden Event.
 
Methods inherited from class planner.Planner
alreadyUsedAction, getPlanInfo, getPlannerID, myDestroy, myResume, mySuspend, setPlanInfo, setPlannerID
 
Methods inherited from class java.lang.Thread
, activeCount, checkAccess, countStackFrames, currentThread, destroy, dumpStack, enumerate, exit, getContextClassLoader, getName, getPriority, getThreadGroup, init, interrupt, interrupt0, interrupted, isAlive, isDaemon, isInterrupted, isInterrupted, join, join, join, nextThreadNum, registerNatives, resume, resume0, setContextClassLoader, setDaemon, setName, setPriority, setPriority0, sleep, sleep, start, stop, stop, stop0, suspend, suspend0, toString, yield
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

bestOpsLL

private java.util.LinkedList bestOpsLL
LinkedList der Operatoren nach Gewichtung
Since:
version 1.0

graphExpansionLevel

private Level graphExpansionLevel
Planning Graph level, das gerade expandiert wird (Propositon- oder Actionlevel).
Since:
version 1.0

noOp

public static final Operator noOp
Alle Propositionen des PLevel P_i werden durch noOps im ALevel A_i ins PLevel P_{i+1} ?bertragen.
Since:
version 1.0

couldExecOnePlan

private boolean couldExecOnePlan
speichert, ob mind. ein C-Plan vollstaendig ausgefuehrt werden konnte.

dynWorldObjectsCounter

private static int dynWorldObjectsCounter
Counter f?r Anzahl der dynamisch erzeugten "virtuellen" Weltobjekte.
Since:
version 1.0

targetMatchOp

Operator targetMatchOp
Operator zur Ueberpr?fung, ob das Ziel bereits erreicht ist. Seine Vorbedingung (Operator.precond): die Zielpr?dikate (PlanInformation.targetPredicates).
Since:
version 1.0

planReadyFinishedEvent

private static final int planReadyFinishedEvent
int Konstante fuer Event planReadyFinishedEvent F?r Gesamt?bersicht siehe Planner.
Since:
version 1.0

planExecuteFinishedEvent

private static final int planExecuteFinishedEvent
int Konstante fuer Event planExecuteFinishedEvent Fuer Gesamtuebersicht siehe Planner.
Since:
version 1.7
Constructor Detail

PlannerTypeC

public PlannerTypeC(PlanInformation planInfo)
Konstruktor des Planers.
Since:
version 1.0
Method Detail

run

public void run()
?berschriebene Thread-Methode run. Startet diesen Planer als Thread.
Overrides:
run in class Planner
Since:
version 1.3

eval

public PlanInformation eval()
PG343-Graphplan
Overrides:
eval in class Planner
Since:
version 1.0

initializePlanningGraph

private void initializePlanningGraph()
Initialisiert den Planning Graph, i.e. erzeugt das erste Proposition-Level aus den Anfangsbedingungen (den PlanInformation.startPredicates).
Since:
version 1.0

expandPlanningGraph

private boolean expandPlanningGraph()
Versucht, den Planning Graph um ein Action- und ein Proposition-Level zu expandieren. Abbruchbedingungen sind 1) wenn nach 70 Leveln noch kein Plan gefunden werden konnte und 2) wenn ein ALevel ausschliesslich aus noOps besteht.
Returns:
boolean zeigt Erfolg (true) oder Misserfolg (false -- eine der Abbruchbedingungen trifft zu) der Graph Expansion an.
Since:
version 1.0

createNextActionLevel

private void createNextActionLevel()
Erweitert den planningGraph um das n?chste Actionlevel (ALevel).
Since:
version 1.0

createNoOp4PNode

private ANode createNoOp4PNode(PNode pNode)
Erzeugt f?r ?bergebenen ANode aus PLevel P_i noOp f?r ALevel A_i.
Since:
version 1.0

createNextPropositionLevel

private void createNextPropositionLevel()
Erweitert den Planning Graph um das n?chste Proposition-Level (PLevel).
Since:
version 1.0

extractSolution

private boolean extractSolution()
R?ckw?rtssuche im PlanningGraph nach einem g?ltigen Plan.
extractSolution initiiert die Plansuche.
goalSetCreationStep leistet rekursiv die eigentliche R?ckw?rtssuche.
findALevelSolutions4Goals Hilfsmethode f?r goalSetCreationStep
sucht f?r aktuelles P_i-Level A_{i-1} L?sungen;
aNodePlan2PlanTree Generiert aus dem aNodePlan (LinkedList von aNode[])
einen entsprechenden PlanTree
Since:
version 1.0

goalSetCreationStep

private boolean goalSetCreationStep(PNode[] goals,
                                    PLevel currentPLevel,
                                    java.util.LinkedList solLL)
Sucht rekursiv f?r goals aus P-Level P_i des Planning Graph in R?ckw?rtsrichtung nach A-Level A_{i-1} L?sungen. Die ANode-Aktionen innerhalb EINER A-Level L?sung sind "parallel ausf?hrbar". Die aneinandergeh?ngten A-Level-L?sungen ergeben zusammen einen g?ltigen Plan in ANode-Notation.
Parameters:
goals - PNode[], die aktuellen goals aus P-Level P_i, die in ALevel A_{i-1} zu l?sen sind.
currentPLevel - PLevel P_i, in dem die goals vorkommen. Level-time i ist mindestens 1 (dann Termination).
Returns:
LinkedList von ANode[]. Ist die Liste == null, so ist die R"uckw?rtssuche nach einem g?ltigen Plan gescheitert. Ansonsten enth?lt die Liste einen g?ltigen Plan in ANode-Notation.
Since:
version 1.0

findALevelSolutions4Goals

private boolean findALevelSolutions4Goals(java.util.ListIterator[] goalAddingActionsLI,
                                          java.util.LinkedList[] goalAddingActionsLL,
                                          int goal2AchieveIndex,
                                          PLevel currentPLevel,
                                          java.util.LinkedList solLL)
Sucht fuer ein Array von P_i-Propositionen (=goals) alle Mengen von A_{i-1} Aktionen, die wechselseitig nicht exklusiv sind und die diese Propositionen (=goals) adden, also alle A_{i-1}-Level L?sungen.
Parameters:
goalAddingActionsLI - ListIterator[] ?ber die goalAddingsActionsLL
goalAddingActionsLL - LinkedList[] von ANode. goalAddingActionsLL[i] enth?lt die Aktionen, die das i-te goal hinzuf?gen.
goal2AchieveIndex - int Index des goals, zu dem eine hinzuf?genden Aktion gesucht wird.
Returns:
LinkedList von ANode[]. Die Aktionen eines solchen ANode-Array sind wechselseitig nicht exklusiv und adden die aktuellen goals.
Since:
version 1.0

aNodePlan2PlanTree

private boolean aNodePlan2PlanTree(java.util.LinkedList aNodePlan)
Generiert aus dem uebergebenen aNodePlan einen entsprechenden PlanTree.
Parameters:
aNodePlan - LinkedList von paralell ausf?hrbaren ANode[]
Since:
version 1.0

interferenceActions

private boolean interferenceActions(ANode a0,
                                    ANode a1,
                                    boolean oneDirectionChecked)
"Interference"-Test fuer zwei Aktionen a0 und a1.
Returns:
boolean true, falls a0 eine Vorbedingung oder einen add-Effekt von a1 loescht ODER umgekehrt, false, sonst.
Since:
version 1.0

compeetingNeedsActions

private boolean compeetingNeedsActions(ANode a0,
                                       ANode a1)
"Compeeting Needs"-Test fuer zwei Aktionen a0 und a1.
Returns:
boolean true, falls eine a0-Vorbedingung exklusiv zu einer a1-Vorbedingung im davor liegenden Proposition Level ist, false sonst.
Since:
version 1.0

checkPropositionExclusivity

private boolean checkPropositionExclusivity(PNode p0,
                                            PNode p1)
Markiert zwei Propositionen p0, p1 als "wechselseitig exklusiv", falls in A_{i-1} alle p0-erzeugenden Aktionen "wechselseitig exklusiv" mit allen p1-erzeugenden Aktionen sind.
Since:
version 1.0

proposMatchesPrecond

private Predicate proposMatchesPrecond(Predicate propos,
                                       Predicate precond)
versucht, die Operator Precondition precond mit der Proposition propos zu matchen. Voraussetzung: Beide Praedikatsignaturen sind kompatibel. Ist precond nicht instantiiert, wird die Instantiierung von propos uebernommen. Ist precond instantiiert, muss diese identisch zur Instantiierung von propos sein, ansonsten kein Match moeglich.
Since:
version 1.0

pNodeMatches4Op

private java.util.LinkedList pNodeMatches4Op(java.util.ListIterator[] pNodesLI,
                                             java.util.LinkedList[] pNodesLL,
                                             Operator theOp,
                                             int itLevel)
findet fuer den uebergebene Operator alle PNodes-Mengen, von denen jede die op-Preconditions matcht und deren Elemente nicht mutual exclusiv sind.
Parameters:
pNodesLI - Array von ListIterator. i-ter Iterator iteriert ueber i-te LinkedList von pNodesLL.
pNodesLL - Array von LinkedList. i-te LinkedList enthaelt Liste von PNodes, die evtl. die i-te Operator-Precond matchen.
op - Der Operator, fuer den matchende pNodes-Mengen gefunden werden sollen.
itLevel - Iterationslevel, Index im Precond-Array des Operators. Initial mit 0 zu belegen.
Returns:
LinkedList die als Liste von Paaren (Operator, PNode[]) zu interpretiren ist. Operator ist jeweils eine einzufuegende Aktion fuer das aktuelle Aktionslevel, PNode[] sind die PNodes, auf als precondEdges der Aktion gesetzt werden muessen.
Since:
version 1.0

graphHasLeveledOff

private boolean graphHasLeveledOff()

graphHasReachedMaxLevel

private boolean graphHasReachedMaxLevel()
Testet, ob der Planning Graph die maximale Anzahl von Leveln erzeugt hat.
Returns:
true, wenn die maximale Levelanzahl erreicht ist, false sonst.
Since:
version 1.3

triggerEvent

protected void triggerEvent(int eventIntId)
Triggert abhaengig vom uebergebenen int eventIntId den entsprechenden Event. Fuer eine Gesamtuebersicht der int Konstanten fuer events siehe Planner.
Parameters:
eventIntId - int Konstante, die den auszul"osenden Event beschreibt.
Since:
version 1.0

getBestOps

private void getBestOps()
Liest aus der OperatorDB die Operatoren nach Gewichtung sortiert aus.
Returns:
ListIterator die ausgelesenen Operatoren
Since:
version 1.1

incDynWorldObjectsCounter

public static int incDynWorldObjectsCounter()
Inkrementiert den Z?hler dynWorldObjectsCounter.
Returns:
int den inkrementierten Wert des Z?hlers dynWorldObjectsCounter.
Since:
version 1.4