Mest praktiskt arbete på På planeringssystem under de senaste femton åren har baserats på Hierarkical Task Network (HTN) nedbrytning, men hittills har det varit mycket lite analytiskt arbete på egenskaperna hos HTN planerare. Detta dokument beskriver hur komplexiteten i HTN-planering varierar med olika villkor på uppgiftsnätverken, och hur det jämförs med STRIPS-stil planering. I AI planering forskning, planering praxis (som förkroppsligas i genomförda planeringssystem) tenderar att köra långt före de teorier som förklarar beteendet hos dessa system. Det finns mycket ny analys av egenskaperna hos system för total- och delorderplanering med hjälp av STRIPS-liknande planeringsoperatörer. STRIPS-planeringssystem utvecklades dock för mer än tjugo år sedan, och det mesta av det praktiska arbetet med AI-planeringssystem under de senaste femton åren har baserats på Hierarchical Task Network (HTN) nedbrytning (t.ex. NOAH [1 I], ICKELIN [12], DEVISER [13] och SIPE [14] ). Hittills har det varit väldigt lite analytiskt arbete med HTN-planerarnas egenskaper. Ett av de främsta hindren för ett sådant arbete har varit bristen på en tydlig teoretisk ram som förklarar vad ett HTN-planeringssystem är, även om två nya dokument [9, 15] har gett viktiga första steg i denna riktning. Ett primärt mål för vårt nuvarande arbete är att definiera, analysera och explicera funktioner i utformningen av HTN-planeringssystem. Vårt arbete har framskridit tillräckligt långt för att göra komplexa analyser av HTN-planering liknande analyser som Bylander [2], Erol et al. [5] utförs för planering med STRIPS-stil operatörer. I synnerhet, Vi har undersökt hur komplexiteten i att avgöra om en plan finns beror på följande faktorer: (1) begränsningar av förekomsten och / eller beställning av icke-primitiva uppgifter i uppgiftsnätverk, (2) om "Detta arbete stöddes delvis av NSF Grant NSFD CDR-88003012 att kakel Institute for Systems Research, och NSF bidrag IR19306580 och ONR bidrag N00014-91-J-1451 till Computer Science Department. I~) J.C. Baltzer AG, Science Publishers 70 K. Erol et al.. Complexi O, resuhs för HTN planering av uppgifterna i aktivitetsnätverk måste beställas helt, och (3) om variabler är tillåtna. Tidningen är organiserad enligt följande. Avsnitt 2 innehåller en översikt över HTN-planering och vår formalisering av HTN-planering. Avsnitt 3 innehåller komplexa resultat och avsnitt 3.3 undersöker relationen mellan HTN-planering och STRIPS-planering. Grunder i HTN-planering Detta avsnitt innehåller en informell beskrivning av HTN-planering, avsedd att ge en intuitiv känsla för HTN-planering. Den exakta beskrivningen finns i avsnitten 2.2–2.4. HTN planering kan beskrivas bäst genom att kontrastera den med sin föregångare, STRIPS-stil planering I Världens representationer och åtgärderna i HTN planering är mycket lik dem av STRIPS-stil planering. Varje tillstånd i världen representeras av den uppsättning atomer som är sanna i detta tillstånd. Åtgärderna motsvarar statsövergångar, dvs. varje åtgärd är en partiell kartläggning från en uppsättning stater till en uppsättning stater. Men åtgärder i HTN planering brukar kallas primitiva uppgifter. Skillnaden mellan HTN-planerare och STRIPS-planerare ligger i vad de planerar för, och hur de planerar för det. STRIPS-stil planerare söker efter en sekvens av åtgärder som skulle föra världen till ett tillstånd som uppfyller vissa villkor, dvs. uppnå mål. Planeringen fortskrider genom att hitta operatörer som har de önskade effekterna, och genom att hävda förutsättningarna för dessa operatörer som delmål. Å andra sidan var en av anledningarna till HTN plalming att överbrygga klyftan mellan AI-planeringstekniker och verksamhetsforskningstekniker för projektledning och schemaläggning [12]. HTN planerare söker efter planer som utför uppgift nätverk, och de planerar via uppgift nedbrytning och konfliktlösning, som vi kommer att förklara inom kort. Ett aktivitetsnätverk är en samling uppgifter som måste utföras, tillsammans med begränsningar i den ordning i vilken uppgifterna utförs, hur variablerna är ögonblickliga, och vad bokstavliga måste vara sant före eller efter varje uppgift utförs. Till exempel, Bild. 1 innehåller ett aktivitetsnätverk för en resa till Las Vegas. Restriktioner gör det möjligt för användaren att ange hur han önskar att uppgifterna ska utföras. Till exempel, i Las Vegas exempel, kan användaren vilja bli rik innan du ser en show, som kan representeras som en beställningsrestriktion. Till skillnad från STRipS-stil planering, begränsningar kan eller får inte innehålla villkor på vad som måste vara sant i det slutliga tillståndet. Vi använder termen "STRIPS-stil" för att hänvisa till alla planerare (eilher total-eller partiell ordning) där planeringsoperatörerna är STRIPS-stil operatörer (dvs. operatörer som består av tre listor med atomer: en förhandslista, en tillägg lista, och en radering lista). Dessa atomer antas normalt inte innehålla några funktionssymboler. K. Erot et af, Komplexit3, resultat.[br HTN plamffng Ett aktivitetsnätverk som endast innehåller primitiva uppgifter kallas ett primitivt aktivitetsnätverk. Ett sådant nätverk kan till exempel uppstå i ett schemaläggningsproblem. I detta fall skulle en HTN planerare försöka hitta ett schema (task beställning och variabel bindningar) som uppfyller alla begränsningar. I det mer allmänna fallet kan ett aktivitetsnätverk innehålla icke-primitiva uppgifter. Icke-primitiva uppgifter är de som inte kan utföras direkt, och planeraren måste räkna ut hur man ska utföra dem. De representerar verksamheter som inbegriper perfbrering av flera uppgifter. Tänk till exempel på uppgiften att resa till New York. Det finns sevemI sätt att åstadkomma det, såsom att flyga, köra eller ta tåget. Flygning skulle innebära uppgifter som att göra bokningar, gå till flygplatsen, köpa biljett, gå ombord på planet, och det skulle bara fungera under vissa förhållanden såsom tillgång till biljetter, vara på flygplatsen i tid, ha tillräckligt med pengar för biljetten, etc, Sätt att utföra icke-primitiva uppgifter representeras med hjälp av konstruktioner som kallas metoder. En metod är av formen (c~, d) där a, är en icke-primitiv uppgift, och d är ett aktivitetsnätverk. Den anger att ett sätt att utföra uppgiften ct är att uppnå alla uppgifter i aktivitetsnätverket d utan att bryta mot begränsningarna i d. Figur 2 presenterar en (förenklad) metod för att utföra Go(X,Y). Planering fortsätter genom att börja med det ursprungliga aktivitetsnätverket d, och göra följande steg upprepade gånger, tills inga icke-primitiva uppgifter lämnas: välj en icke-primitiv uppgift (t i d och en metod (n:, dr). Ändra sedan d genom att "dekomponera" ct (dvs. ersätta a: med uppgifterna i d ~, och införliva begränsningarna i d ~ i d), Figur 3 visar hur man gör en nedbrytning på aktivitetsnätverket presenteras i bild. Jag Bildar. 2............................................................... När inga icke-primitiva uppgifter lämnas i d, nästa problem är att hitta en helt ordnad mark instantiering cr av d som uppfyller alla begränsningar. Om detta kan göras, då är cr en framgångsrik plan för det ursprungliga problemet. I praktiken har HTN-planering också flera andra aspekter. Framför allt tillhandahålls ofta funktioner som kan "avlusa" delvis reducerade aktivitetsnätverk för att eliminera potentiella problem. Dessa "kritiska" funktioner används för att hantera begränsningar, resursbegränsningar och för att ge domänspecifik vägledning. Formaliseringen som beskrivs i [6] förklarar kritiker och förhållandet mellan dessa och de begränsningar som beskrivs ovan. För denna artikels syften påverkar kritikerna inte det värsta beteendet, och därför kommer vi att utelämna denna detalj. Här är några exempel för att ytterligare klargöra skillnaderna mellan olika typer av uppgifter och STRIPS-liknande mål. Att bygga ett hus kräver många andra uppgifter att utföra (att lägga grunden, bygga väggarna, etc.).), alltså är det en sammansatt uppgift. Det skiljer sig från målet att "ha ett hus", eftersom köpa ett hus skulle uppnå detta mål uppgift, men inte den sammansatta uppgiften att bygga ett hus (agenten måste bygga det själv). Som ett annat exempel kan den sammansatta uppgiften att göra en rundresa till New York inte lätt uttryckas som en enda måluppgift, eftersom de inledande och slutliga staterna skulle vara desamma. Mål uppgifter är mycket, liknar STRIPS-stil mål. Men i STRIPS-stil planering, varje sekvens av åtgärder som gör måluttrycket sant är en giltig plan, där som i HTN planering, endast de planer som kan härledas via nedbrytningar anses vara giltiga. Detta gör det möjligt för användaren att utesluta vissa oönskade sekvenser av åtgärder som ändå gör måluttrycket sant. Tänk till exempel på målet att "vara i New York", och anta att pIanner undersöker möjligheten att köra för att uppnå detta mål, och anta att agenten inte har ett körkort. Även om att lära sig köra bil och få ett körkort kan avhjälpa situationen, kan användaren betrakta denna lösning som oacceptabel, och medan hon skriver ner metoderna för be-in (New York), kan hon sätta press på att körsättet lyckas först när agenten redan har ett körkort. Det verkar råda en viss allmän förvirring om uppgifternas karaktär och roll i HTN-planeringen. Detta förefaller till stor del bero på att HTN-planering uppstod, utan en formell beskrivning, i genomförda planeringssystem [11, 12]. Många idéer introducerades i HTN planering (såsom icke-linjäritet, partiell ordning planering, etc.) De formaliserades endast när de anpassades till planering i STRIPS-stil, och endast i detta sammanhang. Dessa idéer inte anpassat till STRiPS-stil planering (såsom sammansatta uppgifter och uppgift nedbrytning) har avfärdats som enbart effektivitet hacks. I vår formalism har vi försökt fylla luckorna och ersätta informella beskrivningar med exakta definitioner, utan att utelämna HTN-planeringskonstruktioner. Vår formalism är mestadels formad efter ICKELIN [t2] och Yangs och Kambhampatis verk [9, 15] o11 hierarkisk planering. Men vår terminologi för K. Erol et al., Complexi O, resultat för HTN plannh~g 73 som hänvisar till icke-primitiva uppgifter skiljer sig något från deras, som istället använder termen "högnivååtgärder" [11, 15]. Även om denna term har någon intuitiv appeal, föredrar vi att inte använda den, för att undvika eventuell förvirring med STRIPS-liknande åtgärder. STRIPS-liknande handlingar är atomära, och de har alltid samma effekt på världen; icke-primitiva uppgifter kan brytas ned i ett antal primitiva uppgifter, och effekten av att utföra en icke-primitiv uppgift beror inte bara på de metoder som valts för att göra nedbrytningar, utan också på att blanda sig med andra uppgifter. Sammansatta uppgifter skiljer sig också från STRIPS-liknande mål. Som vi har diskuterat tidigare representerar sammansatta uppgifter verksamheter för vilka det slutliga tillståndet kan vara helt irrelevant, eller när det gäller exempel på tur och retur kan det slutliga tillståndet vara detsamma som det ursprungliga tillståndet. Ytterligare en syn på HTN:s planering kastar helt bort sammansatta uppgifter och betraktar metoder för måluppgifter som heuristisk information om hur man går tillväga för att uppnå målen (dvs. vilken operatör man ska använda, i vilken ordning man uppnår förutsättningarna för operatören osv.). Även om detta är en fullständigt sammanhängande syn anser vi att den är restriktiv, och vi anser att det finns mer i HTN:s planering, vilket vi försöker visa i vår formalism och i avsnittet om uttryckskraft. Vårt språk £ för HTN planering är ett första ordningens språk med vissa tillägg, och det är ganska lik syntaxen för ICKELIN [12]. Vokabuläret av /; är en tuple IV, C, P, F, T, N), där V är en oändlig uppsättning av variabla symboler, C är en ändlig uppsättning av konstanta symboler, P är en ändlig uppsättning predicate syrnbols, F är en ändlig uppsättning primitiva-task symboler (beteckna åtgärder), T är en ändlig uppsättning sammansatta-task symboler, och N är en oändlig uppsättning symboler som används för att märka uppgifter. Alla dessa uppsättningar symboler är ömsesidigt åtskilda. Ett tillstånd är en lista över markatomer. De atomer som förekommer i den listan sägs vara träd i det tillståndet och de som inte visas är falska i det tillståndet. En primitiv uppgift är en syntaktisk konstruktion av formen do [f(zl,..., z~,:)], där f E F och :el,...,:c~: är termer. En måluppgift är en syntaktisk konstruktion av formen uppnå [l], där l är en bokstavlig. En sammansatt uppgift är en syntaktisk konstruktion av formen perJorm [t(:cl,..., :c~)], där ~ C T och zi,..., zk är termer. Vi hänvisar ibland till måluppgifter och sammansatta uppgifter som icke-primitiva uppgifter. Ett aktivitetsnätverk är en syntaktisk konstruktion av formen [(lzl : ctl) och n., 'n; E N 3 Intuitivt (finis kommer att formaliseras m <°Operational Semantics" avsnitt), (,~. -~ ';7') betyder att den uppgift som är märkt med.n måste föregå den som är märkt med r~/: (n, l), (l, ;) och (71, l, r~/) innebär att jag måste vara träd i staten omedelbart efter 'fT., omedelbart före <ft., och i alla stater mellan -r~. och 'n/, respektive. Både negation och disiunction är tillåtna i begränsningsformeln. Ett aktivitetsnätverk som endast innehåller primitiva uppgifter kallas ett primitivt aktivitetsnätverk. Som ett exempel, Bild. 4 visar ett block-world aktivitetsnätverk och dess grafiska representation. I detta aktivitetsnätverk finns tre uppgifter: clearing ~l, clearing v2, och flytta vi till t?2. Aktivitetsnätverket innehåller också de begränsningar som flytta vi måste göras sist, att Vl och ~ > måste vara tydliga tills vi flyttar Vl, att./Jl, 't~2,'v3 är olika block, och att on(vt, v3) vara sant omedelbart innan vi flyttas. Observera att on(~q, v3) visas som en begränsning, inte som en måluppgift. Syftet med begränsningen (on(vi, '~)3), 7z3) är att säkerställa att v3 är bunden till blocket under ~)i omedelbart före flytten. Representerar på ('~q,.~)3) som ett mål uppgift skulle innebära att flytta '~)i till någon block v3 innan vi flyttar det till v2, vilket inte är vad som är avsett. En plan är en sekvens av primitiva uppgifter på marken. En ope,ato, "är av formen [ope,ato", f('vi....,va:) (p,e:l,...,l,) En metDod är en constrtlct av formen (cx, d) där ~. är en icke-prmlitiv uppgift, och d är ett aktivitetsnätverk. Som vi kommer att definiera formellt i avsnittet "Operational Semantics" innebär denna konstruktion att ett sätt att utföra uppgiften ct är att utföra aktivitetsnätverket d, dvs. att utföra alla deluppgifter i aktivitetsnätverket utan 2 Vi tillåter också n, r~' att vara av kakelform först [n/, nO,...] eller sist[hi, 7L~,...] så att vi kan hänvisa till uppgiften thai börjar först och till den uppgift som slutar sist bland en uppsättning uppgifter, respektive. 75 bryter mot aktivitetsnätverkets begränsningsformel. Till exempel skulle en block-värld metod för att uppnå på (vl, v2) se ut (uppnå (på (vt, v2)), d), där d är aktivitetsnätverket i bild. 4........................................... För att utföra en måluppgift (uppnå [l]) behöver jag vara träd i slutändan, och detta är en implicit begränsning i alla metoder för måluppgifter. Om ett mål är ah-eady sant, då kan en tom plan användas för att uppnå det. För varje måluppgift har vi alltså en metod (uppnå [t], [r,]. : do[f]), (/, n)) som endast innehåller en dummy primitiv uppgift f utan effekter, och begränsningen att målet / är träd omedelbart innan göra [f]. Varje primitiv uppgift har exakt en operatör för det, där som en icke-primitiv uppgift kan ha ett godtyckligt antal metoder. En planeringsdomän är ett par "D = (Op, Me), där Op är en uppsättning operatörer, och jag är en uppsättning metoder. En plaming problem instans är en trippel P = (d, I, 'D), där D är en planeringsdomän, jag är det ursprungliga tillståndet, och d är det uppgiftsnätverk vi behöver planera för. Språket P är HTN språk £ genereras av konstant, predikat och uppgiftssymboler som visas i P, tillsammans med en oändlig uppsättning variabler och en oändlig uppsättning nod etiketter. Således är uppsättningen av konstanter, predikat och uppgifter alla en del av inmatningen. Därefter definierar vi vissa restriktioner för HTN-planeringsproblem. P är primitivt om aktivitetsnätverket d endast innehåller primitiva uppgifter. Detta motsvarar det fall då planeraren endast används för schemaläggning. P är regelbunden om alla aktivitetsnätverk i metoderna och d innehåller högst en icke-primitiv uppgift, och att icke-primitiv uppgift beställs med avseende på alla andra uppgifter i nätverket. Förvånansvärt nog är denna klass av HTN-planeringsproblem nära relaterade till STRipS-planering, som vi ska se i avsnitt 3.3. P är propositionellt om inga variabler är tillåtna. P är rotalh, beställd om alla uppgifter i något aktivitetsnätverk är helt beställda. PLANÖVERENSSTÄMMELSE är följande problem: givet P = (d, I, D), finns det en plan som löser P? I detta avsnitt ger vi en fast punktdefinition för en uppsättning lösningar för ett givet HTN-planeringsproblem. Beskrivning av en likvärdig modell-teoretisk semantik visas i [6]. Först definierar vi hur primitiva uppgifter förändrar världen när de utförs. Likt hur det görs i STRiPS-stil planering, vi verifierar att den primitiva uppgiften är körbar och sedan uppdatera inmatningstillståndet baserat på effekterna av den prmfinitiva uppgiften. Mer exakt, Låt s vara ett tillstånd, och f E F vara en primitiv uppgift symbol med motsvarande operatör [.] "(vl.... v/,:) 3 Alla variabler och nodetiketter i metoden måste byta namn med variabler och nodetiketter som inte visas någon annanstans. K. EIvl et al., Complexi O, resultat för HTN planering • ersätta (n < ~,j) med (last[r~ll,...,n'k] < "n,j), som 'n.j måste komma efter varje uppgift i nedbrytningen av n; l. • ersätta (n,j < n.) med (~,j < first['n/t • ersätta (~., I) med (last [n,l,...,n,k], l), som jag måste vara sant omedelbart efter den sista uppgiften i nedbrytningen av 'n.; • ersätta (~, l, 7z.  och jag är en metod i 70 för den uppgiften}.  Intuitivt, sol, (d, I, 70) är den uppsättning planer som kan härledas i n, steg, och sol (d, I, 70) är den uppsättning planer som kan härledas i ett begränsat antal steg. I [6], Vi bevisar att uppsättningen av lösningar enligt den modell-teoretiska semantik sammanfaller med sol (d, I, 70). Våra komplexa resultat sammanfattas i tabell 1. I följande avsnitt redogör vi för teorierna och diskuterar deras konsekvenser.  K. EIvl et al., Complexi O, resultat för HTN-plamzing Det är lätt att visa att vi kan simulera kontextfri grammatik inom HTN-planering genom att använda primitiva uppgifter för att emulera terminalsymboler, sammansatta uppgifter för att emulera icke-ten'nial symboler och metoder för att koda grammatikregler. Mer intressant är det faktum att vi kan simulera två sammanhangsfria grammatiker, och med hjälp av arbetsuppgifter och begränsningar, kan vi kontrollera om dessa två grammatiker har en gemensam sträng i de språk de genererar. Huruvida skärningspunkten mellan språken i två sammanhangsfri grammatik är non-tomy är ett semi-decisionable problem [8]. Således: Theorem 1. PLAN EXISTENS är strikt halvbeslutbar, även om P är begränsad till att vara propositionella, att ha högst två uppgifter i något aktivitetsnätverk, och att bara ha helt ordnade metoder. Detta resultat kan till en början verka förvånande, eftersom tillståndsrymden (dvs. antalet och storleken på tillstånd) är ändlig. Om planeringsproblemet var att hitta en väg från den ursprungliga staten till ett måltillstånd (som i STRIPS-stil planering), skulle det verkligen vara decibelt, eftersom det för detta problem, närhelst det finns en plan, finns det också en plan som inte går igenom något tillstånd två gånger, och därför behöver vi bara undersöka ett begränsat antal planer. Å andra sidan kan HTN planering innebära sammansatta uppgifter som kan kräva att gå igenom samma tillstånd många gånger, och därmed har vi det obeslutbara resultatet. Istället för att koda varje sammanhangsfri grammatikregel som en separat metod, är det möjligt att koda dessa regler med predikat i det ursprungliga tillståndet, och att ha en metod som innehåller variabler och begränsningar så att endast de nedbrytningar motsvarande K. Etvl et al., Complexi O, resultat för HTN planering 79 till grammatikreglerna kodade i det ursprungliga tillståndet är tillåtna. Därför, även när domänbeskrivningen (dvs. uppsättningen operatörer och metoder) är fast i förväg, är det möjligt att hitta planeringsdomäner för vilka planering är obeslutbar, som anges i följande teorem: Theorem 2. Det finns HTN planeringsdomäner som endast innehåller helt ordnade metoder var och en med högst två uppgifter, för vilka PLAN EXISTENS är strikt semi-decisionable. Ett sätt att göra PLANÖVERENSSTÄMMELSE fastlagd är att begränsa metoderna till att vara acykliska. I så fall kan vilken uppgift som helst utökas upp till endast ett ändligt djup, och på så sätt blir problemet deciderbart. För detta ändamål definierar vi en L:-nivå-mapping som en funktionsnivå() från markfall av uppgifter till uppsättningen {0.... k:}, så att varje gång vi har en metod som kan expandera en markuppgift a till ett aktivitetsnätverk som innehåller en markuppgift a', nivå a > nivå(a). Dessutom måste nivå a vara 0 för varje primitiv uppgift a. Intuitivt, nivå 0 tilldelar nivåer för varje markuppgift, och ser till att uppgifter kan utökas till endast lägre nivå uppgifter, etablera en acyklisk hierarki. I detta fall kan alla uppgifter utökas till ett djup av högst k. Därför, Theorem 3. PLAN EXISTENS är decibel om P har en k-nivå-mappning för vissa heltal ~:. Exempel på sådana planeringsområden finns inom tillverkning, där produkten konstrueras genom att först konstruera komponenterna och sedan kombinera dem tillsammans. Ett annat sätt att göra PLANÖVERENSSTÄMMELSE fastlagd är att begränsa samspelet mellan uppgifterna. Att begränsa aktivitetsnätverken som ska beställas helt begränsar de interaktioner som kan uppstå mellan uppgifter. Uppgifter måste utföras serievis, den ena efter den andra; interleaving deluppgifter för olika uppgifter är inte möjligt. Samspelet mellan uppgifterna är således begränsat till uppgifternas inmatnings- och utgångstillstånd, och "skyddsintervallen", dvs. de ordal som måste bevaras, vilka representeras av statliga begränsningar av formen (7~, l, fT.). Under ovanstående förhållanden kan vi skapa en tabell med en post för varje uppgift, input/output state pair, och uppsättning skyddade bokstavliga, som talar om huruvida det är möjligt att uppnå den uppgiften under dessa förhållanden. Med hjälp av dynamiska programmeringstekniker kan vi beräkna posterna i tabellen i DOUBLE-EXPTIME, eller i EXPTIME om problemet ytterligare begränsas till att vara propositionella. Som visas i nästa avsnitt, STRIP-stil planering kan modelleras med hjälp av HTNs som uppfyller dessa villkor, så vi kan använda komplexiteten resultat på STRIP-stil planering i [2, 5] för att fastställa en lägre gräns på komplexiteten i HTN planering. Således: 80 Theorem 4. PLAN EXISTENS är EXSPACE-hård och i DOUBLE-EXPTIME om P är begränsad för att beställas helt. PLANÖVERENSSTÄMMELSE är PSPACE-hård och i EXPTIME om P ytterligare begränsas till att vara propositionell. Om vi begränsar vårt planeringsproblem till att vara regelbundet, då kommer det att finnas som mest en icke-primitiv uppgift i något aktivitetsnätverk (både det ursprungliga inmatningsuppgiftsnätverket, och de som vi får genom expansioner). Således kan inte deluppgifter i expansionen av olika uppgifter blandas, vilket liknar vad som händer i Theorem 4. Men i Theorem 4 kan det finnas flera icke-primitiva uppgifter i ett aktivitetsnätverk, och vi behövde hålla koll på dem alla (vilket är anledningen till att vi använde tabellen). Om planeringsproblemet är regelbundet, behöver vi bara hålla reda på en enda icke-primitiv uppgift, dess ingång/sluttillstånd, och de skyddade bokstavliga. Eftersom storleken på ett tillstånd är som mest exponentiellt, kan problemet lösas i exponentiellt utrymme. Men även med regelbundenhet och flera andra begränsningar, är det fortfarande möjligt att minska en EXSPACE-fullständig STRipS-stil planering problem (beskrivs i [5] ) till HTN ramverket. Således: Theorem 5. PLANÖVERENSSTÄMMELSE är EXSPACE-fullbordad om P är begränsad till att vara regelbunden. Det är fortfarande EXPACE-komplett om P är ytterligare begränsad för att vara helt beställd, med högst en icke-primitiv uppgift symbol i planeringsspråket, och alla aktivitetsnätverk som innehåller högst två uppgifter. När vi ytterligare begränsar vårt problem till att vara propositionellt, är det fortfarande möjligt att definiera en minskning från propositionell STRipS-stil planering, som har visat sig vara PSPACE-fullständig [2]. Således komplexiteten går ner en nivå: Theorem 6. PLANÖVERENSSTÄMMELSE är PSPACE-fullständig om P är begränsad till att vara regelbunden och propositionell. Det är fortfarande PSPACE-komplett om P ytterligare begränsas till att beställas helt, med högst en icke-primitiv uppgift symbol i planeringsspråket, och alla aktivitetsnätverk som innehåller högst två uppgifter. Om vi tillåter variabler men istället fixa planeringsdomänen "D (dvs. uppsättning av metoder och operatörer) i förväg, då antalet markatomer och markuppgifter är polynom i längden på inmatningen till planeraren. Därför är komplexiteten i regelbunden HTN-planering med en fast planeringsdomän med variabler inte svårare än komplexiteten i regelbunden propositionell HTN-planering, som visas vara PSPACE-komplett i Theorem 6 4 I beviset för Theorem 5.17 in [5] presenteras en uppsättning av tre STRIP-operatörer med variabler för vilka planeringen är PSPACE-komplett. Den minskning som beskrivs i beviset för Theorem 5 omvandlar denna uppsättning operatörer till en vanlig HTN-planeringsdomän (med variabler) för vilken planeringen är fullständig. Därför: 4 I ett relaterat resultat, [2] visar att propositionell STRIPS-stil planering är också PSPACE-fullständig. Vi undersöker relationen mellan regelbunden HTN-planering och STRIPS-planering i avsnitt 3.3. K. Erol et al., Complexit 3, resultat för HTN planering Theorem 7, Om P är begränsad till att vara regelbunden och 71) är fast i förväg, då PLAN EXISTENS är i PSPACE. Dessutom finns det en fast regelbunden HTN planering domän D för vilken PLAN EXISTENS är PSPACE-fullständig, Antag att ett planeringsproblem är primitivt, och antingen propositionell eller helt ordnad. Sedan problemet medlemskap i NP är lätt att se: när vi icke-deterministiska gissa en total beställning och variabel bindning, kan vi kontrollera om begränsning formel på aktivitetsnätverket är nöjd i polynom tid. Dessutom, om vi inte kräver att planeringsproblemet ska vara både helt ordnad och propositionell, vår begränsning språk gör det möjligt för oss att representera tillfredsställande problem, och därmed får vi NP-hårdhet. Därför: Theorem 8. PLANÖVERENSSTÄMMELSE är NP-fullständig om P är begränsad till att vara primitiv, eller primitiv och helt ordnad, eller primitiv och propositionell. Men PLAN EXISTENS kan lösas i polynom tid om P är begränsad till att vara primitiv, helt ordnad och propositionell. Det har inte funnits något tydligt samförstånd om vad HTN kan och inte kan representera. Det ansågs allmänt att även om HTN är mer flexibla jämfört med STRIPSstyle planering, kan allt som kan göras i HTN planering också göras i STRIPS-stil planering. På grund av avsaknaden av en formalism för HTN-planering kunde sådana påståenden inte bevisas eller vederläggas. Vi tar upp denna fråga med hjälp av formalismen i detta dokument. När vi jämför HTNs och STRIPS konstaterar vi att HTN-metoden ger alla de begrepp (tillstånd, åtgärder, mål) som STRIP har. I själva verket, med tanke på en domän kodad som en uppsättning STRIPS operatörer, kan vi omvandla den till en HTN planeringsdomän, i låg-order polynom tid. En enkel omvandling skulle vara att förklara en primitiv uppgift symbol för varje STRIPS operatör, och för varje effekt av varje operatör, att deklarera en metod som liknar den i Fig. 4........................................... Varje sådan metod innehåller förutsättningarna för operatören som måluppgifter, och även den primitiva uppgift som motsvarar operatören själv. Nedan följer en mer lärorik transformation som visar att förhållandet mellan STRIPS-planering och HTN-planering är jämförbart med förhållandet mellan höger Iinear grammatik och kontextfri grammatik. Vi sammanfattar transformationen nedan; för detaljer se beviset för Theorem 5. I denna omvandling använder HTN-representation samma konstanter och predikat som används i STRIP-representationen. För varje STRIPS operatör o, förklarar vi en primitiv uppgift f med samma effekter och förutsättningar som o. Vi använder också en durnmy primitiv uppgift.t'rt med inga effekter eller förutsättningar. Vi deklarerar en enda sammansatt uppgift symbol L För varje primitiv uppgift f, Vi konstruerar en metod av formen 82 K. Eml et al., Complexi O, resultat för HTN plamffng f..1 Vi deklarerar en sista metod [pel~[ornl[l;, J] [(Tz:per[brm[t]), ('n., GI) A... A ('lz, Gm]] där GI,...,Gin är de STRIP-stil mål vi vill uppnå. Observera att omvandlingen skapar vanliga HTN-problem, som har exakt samma komplexitet som STRIPS-liknande planering. Således, precis som att begränsa kontextfri grammatik till att vara rätt linjär producerar regelbundna uppsättningar, begränsar HTN metoder för att vara regelbunden producerar STRIPS-stil planering. Nästa fråga är om det finns en förändring i den andra riktningen, det vill säga om det är möjligt att koda HTN-planeringsproblem som planeringsproblem i STRIPS-stil. Intuitivt, en sådan omvandling kan inte existera, eftersom STRIPSstyle planering saknar begreppet sammansatta uppgifter, och dess begrepp om mål är mer restriktiv än i HTN planering. Till exempel ger det inte medel för att deklarera mål / begränsningar på mellanstaterna som HTNs gör. En mer formell argumentation kan göras enligt följande. Från Theorem 1, HTN planering med ingen t\mction symboler (och därmed endast ändligt många marktermer) är semi-decisionable. Även om vi kräver att domänbeskrivning 7) ska fastställas i förväg (dvs. inte en del av inmatningen), Theorem 2 talar om för oss att det finns HTN planeringsdomäner för vilka planering är semi-definierad. Men utan funktionssymboler är planering enligt STRIPS-stil decidabile, oavsett om planeringsdomän 5 är fast i förväg eller inte [5]. Således: Theorem 9. Det finns inte en beräkningsbar funktion "(~ från uppsättningen av HTN planeringsproblem instanser till uppsättningen av STRIPS-stil planering problem instanser sådan att för alla HTN-planering problem instans P, och någon plan o", cr löser P iff (a(~) löser "(.,(P) 6 Visar om en polynom eller beräkningsbar omvandling finns är ett sätt att jämföra expressiviteten av två språk. Avsaknaden av en beräkningsbar omvandling från HTN planering till STRIPS-stil planering innebär att för vissa planeringsproblem, problemet representation i STRIP-stil planering kommer att vara exponentiellt (eller i vissa fall, även oändligt!) större än i HTN planering. Men det finns också några andra sätt på vilka man kan vilja jämföra expressivitet. Som exempel kan nämnas att Baader [1 ] har utvecklat en metod baserad på modellteoretiska semantik för att jämföra den uttrycksfulla kraften i kunskapsrepresentationsspråk. Enligt Baaders definition är ett kunskapsrepresentationsspråk L2 lika uttrycksfullt som Lq iff det finns en funktion,O (som inte behöver vara beräkningsbar) som kartlägger varje uppsättning meningar från Ll till en uppsättning meningar från L2, så att följande egenskap är nöjd när */J(FI) = F2: s Eftersom STRIP-stil planering inte inkluderar medmds, en STRIP-stil planering domän är helt enkelt en uppsättning operatörer. a För att bevisa detta teorem, använder vi standard antagandet att STRIPS operatörer inte innehåller funktionssymboler, inte heller HTN operatörer. För att anpassa Baader definition till planering språk finns det två möjliga metoder: utveckla en modell-teoretisk semantik för planering, eller använda operativa sernantik som presenteras i avsnitt 2.4. Som vi diskuterar i [6] ger dessa två tillvägagångssätt olika (icke-ekvivalenta) definitioner av hur uttrycksfullt planeringsspråk är. HTN-planering är dock mer uttrycksfull än STRipS-planering enligt båda dessa definitioner. I [6] bevisar vi detta för den modell-teoretiska definitionen; nedan presenterar vi en definition av expressivitet baserad på operationell semantik, och vi använder denna definition för att bevisa att HTN planering är mer uttrycksfull än STRIPS-stil planering. Vi definierar ett planeringsspråk Li att vara lika e.vpressive som ett planeringsspråk L2 iff det finns en funktion '/~, från uppsättningen av planering problem fall i L2 till uppsättningen av planering problem fall i L~ sådan att för varje planering problem exempel P i L2, P och.t/~ (P) har samma uppsättning av lösningar (planer) modulo symbol omnaming. .~/, behöver inte vara beräkningsbar. I bevisen för obeslutbarheten teorem har vi visat att uppsättningen av sohltions för en HTN-planering problematik kan vara någon sammanhangsfri uppsättning, eller ens skärningspunkten mellan två sammanhangsfria uppsättningar. I allmänhet kan en sådan uppsättning inte uttryckas som en uppsättning lösningar på ett planeringsproblem i STRIPS-stil, eftersom uppsättningen lösningar på ett planeringsproblem i STRIPS-stil motsvarar en regelbunden uppsättning (där staterna inom planeringsområdet motsvarar tillstånden i en ändlig automata, och åtgärderna i samband med statsövergångar). Därför finns det inte en funktion.~/J från uppsättningen av HTN-planering problem fall till uppsättningen av STRIPS-stil planering problem fall som bevarar uppsättningen av lösningar. Å andra sidan har vi presenterat en omvandling som kartlägger varje STRIPS-typ planering problem instans till en HTNplanering problem instans med samma uppsättning av lösningar. På så sätt kan vi avsluta Theorem 10. HTN planering är strikt mer uttrycksfull än STRIPS-stil planering. Kraften i HTN planering kommer från två saker: (1) tillåter flera uppgifter och godtyckliga begränsningar formler i aktivitetsnätverk, (2) sammansatta uppgifter. Tillåta flera uppgifter och godtyckliga formler ger flexibilitet - men om alI uppgifter var antingen primitiva eller mål (STRIPS-stil) uppgifter, kan dessa förmodligen uttryckas med STRIPS-stil operatörer (om än klumpigt och med hjälp av ett exponentiellt antal operatörer / predikat). Sammansatta uppgifter ger en abstrakt representation för uppsättningar av primitiva aktivitetsnätverk, liknande det sätt som icke-terminala symboler ger en abstrakt representation för uppsättningar av strängar i kontextfri grammatik. Vi har presenterat en formell beskrivning av HTN-planering, och vi har gjort en komplexitetsanalys baserad på denna formalism. Av våra resultat kan vi dra följande slutsatser: 84 K. Erol et al., Complexit 3, resultat för HTN-plätering 1. HTN planerare kan representera en bredare uppsättning av planeringsdomäner än STRIPSstyle planerare. Omvandlingarna från HTN-planeringsproblem till STRIPS-planeringsproblem har visat att STRipS-planering är ett specialfall av HTN-planering, och att relationen mellan dem är jämförbar med relationen mellan kontextfria språk och vanliga språk. Detta motsäger idén, som innehas av vissa forskare, att HTNs är bara en "effektivitet hack". 2. Utgångspunkten är följande: Hantering av interaktioner mellan icke-primitiva uppgifter ix den svåraste delen av HTN planering. I synnerhet om deluppgifter i utvidgningarna för olika uppgifter kan interleaved, då planering är obeslutbar, även under en mycket allvarlig uppsättning restriktioner. Men att begränsa planeringsproblemen helt och hållet eller regelbundet minska komplexiteten avsevärt, eftersom det begränsade samspelet mellan uppgifter. 3. Vad är det som händer? I allmänhet, vilka begränsningar vi sätter på icke-primitiva uppgifter har en större effekt på komplexiteten än om vi tillåter variabler, eller inte, eller kräver uppgifter att vara helt ordnade. 4. Vad är det som händer? Om det inte finns några begränsningar för icke-primitiva uppgifter, då vare sig vi kräver att uppgifter ska vara helt beställda eller inte har en större effekt (nämligen decisionability vs. obeslutsamhet) än whetlaer eller inte tillåter vi variabler. Men i närvaro av restriktioner för icke-primitiva uppgifter, vare sig vi tillåter variabler har en större effekt än om vi kräver uppgifter för att helt och hållet beställas. För närvarande undersöker vi hur man kan använda begränsande tillfredsställelse tekniker såsom trädsökning kontra reparation, värdebeställning och variabla order heuristik för att öka effektiviteten i HTN planering. Vi undersöker också hur vi kan utöka HTN:s aktionsrepresentation för att möjliggöra villkorliga, probabilistiska och framtida effekter.
att motivation, komplexiteten i HTN planering är betydligt värre än att planera med bara primitiva åtgärder REF.
Complexity results for HTN planning
{'venue': 'Annals of Mathematics and Artificial Intelligence', 'journal': 'Annals of Mathematics and Artificial Intelligence', 'mag_field_of_study': ['Computer Science']}