Diskussion

Vi har som nævnt i test afsnittet lavet test b˚ ade for enkelte funktioner og hele test scenarier. I begge tilfælde ville en mere vidtrækkende test strategi være lækkert, men skønnes for omfattende. Opst˚ ar der et problem undervejs i plan-lægningen, er det at finde hvor ulykken opst˚ ar ganske vanskeligt. Outputtet fra plan-grafen er gigantisk og selv ved mindre problemer dannes træer med 150 noder der er filtret sammen p˚ a kryds og tværs. Findes der ikke en løsning, m˚ a man afbryde træet n˚ ar det eksempelvis har undersøgt 50.000 noder - hvor gik det galt?. Debugge hele systemet er derved meget tidskrævende. Eventuelle problemer der opst˚ ar er vi, belært af erfaring, ret sikre p˚ a skyldes m˚ aden hvorp˚ a handlinger sletter og opretter ˚ abne betingelser. Specificeres en handling ikke or-dentligt(og det kan være svært) vil der ikke returneres en brugbar plan. Selve op-sætningen omkring algoritmen har efter indledende test ikke givet nævneværdige problemer.

Anvendelighed af POP med STRIPS Vi har gennem implementeringen af POP f˚ aet en god føling med algoritmen og STRIPS. For at systemets virkeligt kan siges at være alsidigt, vil nogle af de nævnte udvidelser skulle indbygges.

STRIPS giver en god og intuitiv tilgang til planlægning. Id´ een med dens anven-delse til snart sagt alle problemer, hvori du kan beskrive verden med betingelser og handlinger der manipulerer med disse er genial. De hovedsagelige proble-mer der gør at STRIPS(og dens overbygninger) ikke ses i alt mekanik, er to-foldig. Naturligvis er algoritmens meget d˚ arlige worstcasekøretid grundstammen i dens begrænsede anvendelsesmuligheder. Som nævnt forværres beregningstiden alvorligt med antallet af handlinger og betingelser. Der skal ikke alt for mange komponenter til før køretiden er for slem til at benyttes i realtime systemer.

Dette problem eksistere selvsagt i al planlægning.

Det andet problem er lidt mere bekymrende for STRIPS o.lig. sprog. Det er

desværre ikke let ’blot’ at tilføje en række handlinger og betingelser, s˚ a

k-larer algoritmen det selv. Designet og sammenhængen mellem disse kan være

meget svært. Kunne gennem talrige test kan man se om de rigtige forbindelser i

plantræet bliver oprettet, s˚ a at ens ønskede problemstillinger kan løses. Som

nævnt er disse test meget tidskrævende. Alene vores simple eksempel med

LEGO, hvor antallet af handlinger er forholdsvis begrænsede, har vi m˚ atte bruge

anseeligt mere tid p˚ a debug end rent design.

2.9 Diskussion 27

2.9.1 Implementerings vanskeligheder

At give et generelt indblik i nogle af de problemer der kan opst˚ a i et planrums søgetræ, kan være vanskeligt da de typisk er meget situations afhængige. Enkelte nævneværdige problemer vil dog blive listet i nedenst˚ aende. De tjener mere til at vise rent praktiske vanskeligheder end bidrage til det teoretiske grundlag; af samme grund kan afsnittet springes over eller let læses.

Vedligeholdelse af ˚ abne betingelser N˚ ar en ny operator opfylder en ˚ aben betingelse, skal den sørge for at vedligeholde og opdatere listen over ˚ abne betingelser.

Dette gøres dels ved at slette den netop opn˚ aede betingelse fra listen, samt ved at oprette de nye ˚ abne betingelser operatoren kræver opfyldt. Endvidere kan det ses at det er fornuftigt, at operatoren sletter de betingelser fra listen som den yderligere opfylder.

De fleste handlinger tager et sæt af betingelser med variabler, manipulerer med disse og smider dem tilbage ind p˚ a den ˚ abne liste. Tager handlingen flere betingelser, med forskellige variabler, er det ikke trivielt at f˚ a afgjort hvilke betingelser der konjunktivt udgør handlingens effekt.

Eksempelvis ses handlingen ’SeperateItems’ der deler et objekt i to. Handlingen har forh˚ andsbetingelsen item(x, y) og effektbetingelserne item(x) & item(y).

Hvis handlingen oprettes p˚ a baggrund af item(A), m˚ a den finde item(A) i ˚ abne betingelser, slette den og oprette en ny ˚ aben betingelse item(A, y). Kan den endvidere opfylde en anden ˚ aben betingelse item(B), vil item(A, B) kunne in-stantieres med det samme i ˚ abne betingelser. Det er dog ikke ligetil at gennemg˚ a

˚ abne betingelser for at finde tidligere ting der kan opfyldes. Hvis der eksisterer flere objekter item(C), item(D) etc. er det ikke let at afgøre hvilken en han-dlingen der skal benyttes sammen med item(A).

Det har vist sig ganske svært at lave en generel funktion, der uafhængigt af den kontekst en handling oprettes p˚ a baggrund af, kan vedligeholde listen over ˚ abne betingelser. Ideelt set skal der kunne slettes alle ˚ abne betingelser en vilk˚ arlig handling, med et uspecificeret antal betingelser og variabler, opfylder; kunne oprettes nye betingelser med en korrekt sammenhæng mellem variablerne i forh˚ andsbetingelser og effektbetingelserne; kunne tilføjes handlingens effekt-betingelser til liste over tidligere handlinger osv. Selvom de korrekte effekt-betingelser bliver tilføjet listen over ˚ abne betingelser er rækkefølgen langt fra ligegyldig.

Alene heuristikmæssigt kan en ombytning af rækkefølgen af betingelser der

til-føjes til listen, have anseelig betydning. Fald og stigninger fra 100 til 2000 noder

der undersøges i træet, har været observeret. En specifik h˚ andtering af hver

enkelt handling er derfor ofte nødvendigt og tidskrævende (konsekvenserne p˚ a

plantræet skal undersøges til bunds), og gør at det ikke er en simpel sag at tilføje

nye handlinger og betingelser.

Information til r˚ adighed En node i en planrums graf (i modsætning til i tilstandsrum) har som nævnt ovenfor den egenskab at den kun skal koncen-trere sig om sin lille del af en overordnet plan. Den har ikke oplysninger om konsekvenser andre dele af træet kan have p˚ a verdenstilstanden. Der er i POP*

trusselsh˚ andtering, men det best˚ ar ikke i at den enkelte handling, overvejer hvad hele træets kumulerede effekt er og træffer valg udfra dette. Det har den fordel at rangeringen ikke er rigid men fleksibel. Ulempen er dog at en node ikke kan f˚ a oplysninger nogen steder fra om tilstanden af verden.

Eksempelvis ses M ove(x, y) handling der flytter fra et koordinat x til et andet y. Det kan ikke ses udfra den initiale tilstand om der er et objekt i vejen mellem de to koordinater - dette objekt kan være flyttet eller lagt i vejen af en anden gren i træet. Ligeledes kan det heller ikke afgøres af slutbetingelserne, da de blot beskriver egenskaber der ønskes verden skal tilføjes efter eksekveringen af planen (ikke hele verdens tilstanden). Endvidere er det ikke muligt at søge igennem det midlertidige træ og beregne effekten af disse handlinger, da det jo naturligt ikke er afgjort om de handlinger overhovedet er med i den endelige løsning.

M ove(x, y) m˚ a derfor lave betingelser der søger for at der ikke er objekter p˚ a vejen, og det komplicerer systemet en del. Det ses at da verdens tilstanden ikke kan oplyses under planlægningsfasen, er en effektiv heuristik vanskelig. I en verden hvor man rykker rundt p˚ a et kort og samler ting op, kunne man lave et globalt m˚ al koordinat som alle M ove(x, y) handlinger vil søge hen mod for at mindske heuristikken. Start koordinatet for robotten kunne naturligt vælges (start da robotten er regressiv). Starter robotten samme sted som den slutter, men skal hente et objekt p˚ a et endnu ikke specificeret sted, vil heuristikken betyde at algoritmen undersøger muligheder tæt rundt om start, i stedet for at g˚ a direkte efter objektet.

Gentagelse af tilstand Teoretisk kan der være store forbedringer at opn˚ a i plansøgningen, hvis tilstande der allerede er ekspanderet, ikke behøves undersøgt igen. Hvis en gren af søgningen har n˚ aet en tilstand (ligegyldigt hvordan) og en anden del af grenen n˚ ar den samme tilstand p˚ a en alternativ m˚ ade, vil den videre søgning være ens for de to grene og de m˚ a formodes lige langt fra en løsning.

Der er i designet forsøgt adskillelige forsøg p˚ a at definere en tilstand s˚ a den er restriktiv nok til at ens tilstande bliver anerkendt, uden at udelukke tilstande der kan føre til en løsning. En delplans instans af definitionen er undervejs vha. en strengs hashkode gemt i et hashmap. N˚ ar en plan udvælges fra den prioriterede kø, checkes først om en plan med ens tilstand er undersøgt først. Er den det, behøves planen ikke at blive ekspanderet.

Uden at g˚ a i detaljer med selve forsøgende p˚ a definitionerne af en tilstand,