Planerare av Graphplan familjen (Graphplan, IPP, STAN...) anses för närvarande vara de mest effektiva på många planeringsområden. Deras delvis ordnade planer kan representeras som sekvenser av åtgärder. De åtgärder som genereras av Graphplan uppfyller en stark självständighet egenskap som gör att man kan manipulera varje uppsättning som en helhet. Vi presenterar en detaljerad formell analys som visar att självständighetskriteriet delvis kan mildras för att ta fram giltiga planer i den mening som avses i diagramplan. Två åtgärder på samma nivå i planeringsgrafen behöver inte betecknas som ömsesidigt uteslutande om det finns en möjlig ordning mellan dem som respekterar ett kriterium om "godkännande", mindre begränsat än kriteriet om oberoende. Beställningen mellan åtgärderna kan göras efter det att planen har genererats, och utvinningen av lösningsplanen kräver en extra kontrollprocess som garanterar att en beställning kan hittas för åtgärder som övervägs samtidigt, på varje nivå av planeringsgrafen. Denna studie leder oss till att genomföra en modifierad grafplan, LCGP (för "Last Committed GraphPlan"), som fortfarande är sund och komplett och i allmänhet producerar planer som har färre nivåer än de i Graphplan (samma antal i de värsta fallen). Vi presenterar en experimentell studie som visar att LCGP inom klassiska planeringsområden löser fler problem än planerare från familjen Graphplan (Graphplan, IPP, STAN...). I de flesta fall överträffar LCGP också de andra planerarna. Inledning Under de senaste åren har utvecklingen av en ny familj av planeringssystem som bygger på planeringsplanen [2] lett till många utvecklingar i planeringen. Grafplan utvecklar, nivå efter nivå, ett kompakt sökområde som kallas planerings-graf. Under detta byggnadsstadium använder den inte alla förhållanden mellan tillståndsvariabler eller åtgärder som beaktas i andra planeringstekniker som tillståndssökning eller sökning i utrymmet för partiella planer. I diagramplan är dessa begränsningar endast beräknade och memorerade på varje nivå som ömsesidiga undantag, så att planeringsgrafen kan ses som en dynamisk CSP [10; 11; 18; 23]. Sökutrymmet är lättare att utveckla, men ett andra steg, som kallas extraktionsstadiet, är nödvändigt för att försöka ta fram en giltig plan från planeringsgrafen och uppsättningarna av ömsesidiga undantag. Flera metoder har använts för att förbättra diagramplan: minskning av sökytan före extraktionsfasen [7; 19], förbättring av domänrepresentationsspråket [9; 14; 15; 22; 23], förbättring av extraktionsstadiet [8; 10; 11; 13; 16; 24]. I alla dessa arbeten förblir strukturen i de genererade planerna densamma oavsett vilken grafkonstruktionsmetod som används. En plan för diagramplan kan således representeras som en minimal sekvens av åtgärder som beaktas samtidigt: varje steg i algoritmen producerar en nivå av planeringsgrafen, varje nivå är ansluten till en uppsättning åtgärder i planen. Varje uppsättning Q av åtgärder som visas i en sekvens som produceras av Graphplan är sådan att beräkningen av den slutliga situationen Ef, som produceras genom tillämpning av åtgärder Q, från en inledande situation Ei, är oberoende av i vilken ordning dessa åtgärder tillämpas. Detta beror på att alla åtgärder som Graphplan håller under extraktionsfasen verifiera en egenskap I (Independence), lätt att testa, som tillåter dem att köras parallellt. Den slutliga situationen Ef beräknas direkt från den ursprungliga situationen Ei och från den globala tillämpningen av åtgärderna i den inställda Q. Vi har etablerat en annan egenskap A (auktorisation) som är mindre restriktiv än jag (jag menar A) och lättare att verifiera. Denna egenskap garanterar existensen av minst en serialisering S av åtgärder av Q (men kräver inte dess beräkning). Tillämpningen av denna sekvens på en inledande situation Ei kan fortfarande beräknas som om uppsättningarna av åtgärder verifierade självständighet egendom. Den slutliga situationen Ef kan fortfarande anses vara resultatet av den globala tillämpningen av åtgärder av Q, men dessa åtgärder kan inte alltid genomföras parallellt: en giltig beställning (som kan innehålla parallella åtgärder) måste hittas. Vi har utvecklat en Graphplan-liknande planerare som kallas LCGP (Least Committed Graphplan, se [4; 5] ) som fungerar på samma sätt: den gradvis konstruerar en stratifierad graf, sedan söker den för att extrahera en plan. Grafen som Graphplan skulle ha byggt är en del av LCGP-grafen (jfr. exempel nedan) på samma nivå. Så, mål i allmänhet visas tidigare (på samma gång i de värsta fallen). LCGP omvandlar sedan den producerade planen till en grafplansliknande plan. Den snabbare beräkningen av en lösning har en kostnad: de planer som erhålls med LCGP kanske inte är optimala, i den meningen att de kan ha fler nivåer än de som produceras av Graphplan. I praktiken ger LCGP snabbt en lösning på många klassiska riktmärken (Logistics, Blocks-world, Ferry...) där Graphplan inte kan ta fram en plan efter en betydande körtid. Vi introducerar nedan, på ett litet exempel, den grundläggande idén om tillståndsförhållandet och de förändringar det innebär för Graphplan. Låt oss först informellt erinra oss de grundläggande elementen i diagramplan. Föremål i världen representeras av markatomer (kallade förslag), tillstånd i världen är listor över förslag, och åtgärder är tredubblar listor över förslag: förutsättningar (förslag som måste finnas i staten innan åtgärden genomförs), lägga till effekter (förslag läggs till i staten) och del effekter (förslag tas bort från staten). Den Graphplan algoritm bygger först planerings-grafen, en stratifierad graf som interleaves två typer av noder: förslag noder och åtgärd noder. Dessa noder samlas in i nivåer, som innehåller en uppsättning förslag noder och en uppsättning åtgärder noder vardera. Den första nivån innehåller endast förslagen om det ursprungliga tillståndet i världen. Den andra nivån innehåller de åtgärder som är tillämpliga i det ursprungliga tillståndet (åtgärder som har alla sina förutsättningar närvarande i det ursprungliga tillståndet), och no-ops för varje förslag i det ursprungliga tillståndet. En no-op är en åtgärd vars förutsättning är ett förslag och lägga till effekt är samma förslag. No-ops tillåter diagramplan för att lösa ramproblemet: ett förslag som inte tas bort av en åtgärd kommer att finnas i nästa tillstånd om motsvarande no-op tillämpas. Den andra nivån innehåller också tilläggseffekter av varje åtgärd på den andra nivån (inklusive förslag från det ursprungliga tillståndet, tack vare no-ops). På varje nivå registreras binära ömsesidiga undantag. Två förslag utesluter varandra när varje par av handlingar som frambringar dem är ömsesidigt uteslutande, och två handlingar utesluter varandra när de har ömsesidigt uteslutande förutsättningar eller när de inte är oberoende. Två åtgärder är oberoende när ingen av dem tar bort en förutsättning eller en ytterligare effekt av den andra. Åtgärder kommer inte att läggas till på nästa nivå om någon av deras förutsättningar utesluter varandra. Denna process fortsätter tills följande egenskap verifieras: antingen är alla förslag av målet närvarande i den sista nivån och inga av de målförslag är ömsesidigt uteslutande, eller problemet har visat sig vara omöjligt att lösa med avseende på en mer komplex egendom (jfr. [3] för närmare upplysningar). Om problemet inte är olösligt kan en lösning extraheras med en bakåtkedjad algoritm som kortfattat beskrivs i exemplet nedan. Om ingen lösning hittas förlängs planeringsgrafen med ytterligare en nivå och extraktionsfasen börjar igen tills en lösning hittas eller problemet visar sig vara olösligt. Nu kommer ett exempel som illustrerar skillnaden mellan grafplan och LCGP. Den uppsättning förslag är P = {a, b, c, d} och uppsättningen åtgärder är A = {A, B, C}, med: Förutsättningar för A = {a} Förutsättningar för B = {a} Förutsättningar för C = {b, c} Lägg till effekter av A = {b} Lägg till effekter av B = {c} Lägg till effekter av C = {d} Del effekter av A = {} Del effekter av B = {a} Del effekter av C = {} Det ursprungliga tillståndet för problemet är I = {a} och målet är G = {d}. Planeringsdiagrammet för diagramplan visas i figur 1. En fullständig svart linje från ett förslag till en åtgärd (från vänster till höger) utgör en förutsättningslänk, och från en åtgärd till ett förslag representerar den en tilläggseffekt. Dashed linjer representerar del effekter, och grå linjer representerar no-ops. Eftersom no-op av b och åtgärden B inte är ömsesidigt uteslutande. På nivå 3 kan åtgärden C tillämpas och målet d visas. Lösningen kan nu extraheras genom den bakåtkedjade algoritmen. En mållista skapas som endast innehåller d. Algoritmen letar efter åtgärder som hävdar förslagen i mållistan på nivå 3. Den enda åtgärd som hävdar d är C. Mållistan är nu en förening av förutsättningarna för varje genomtänkt åtgärd: {b, c}. Algoritmen registrerar att C tillhör den nuvarande planen på nivå 3, och letar efter åtgärder på nivå 2 som hävdar förslaget i mållistan. Vissa par av åtgärder kan inte väljas, eftersom de utesluter varandra: {A, B}, {A, no-op of c}, {no-op of b, no-op of c}. Det enda möjliga valet är {no-op av b, B} som registreras i den nuvarande planen på nivå 2. Mållistan är nu {b, a} och de enda möjliga åtgärderna på nivå 1 är {A, no-op of a}. Den producerade planen (utan "no-ops", som endast är användbara för konstruktionen av grafen och extraktionsstadiet) är A, B och C. Tillståndsförhållandet är en partiell uppmjukning av självständighetsförhållandet, och är inte symmetriskt. En åtgärd A tillåter en åtgärd B när A inte tar bort en förutsättning för B och B inte tar bort en tilläggseffekt av A, så åtgärden B kan tillämpas efter åtgärden A och den resulterande staten innehåller föreningen av tilläggseffekterna av A och B. Två åtgärder är nu ömsesidigt uteslutande när de har ömsesidigt uteslutande förutsättningar eller när ingen av dessa två åtgärder tillåter den andra. Figur 2 visar LCGP:s planritning. På nivå 1 utesluter således inte förslagen b och c varandra, och åtgärd C kan tillämpas på nivå 2. Målet d visas nu på nivå 2 och extraktionsfasen kan utföras. Mållistan initieras med {d}, och algoritmen letar efter en åtgärd som hävdar d: åtgärden C registreras sedan i den nuvarande planen på nivå 2. Mållistan är nu förutsättningarna för C: {b, c}. De enda åtgärder som hävdar förslagen i mållistan är nu de åtgärder A och B som inte är ömsesidigt uteslutande som tidigare, eftersom A godkänner B. Algoritmen måste utföra ett extra test, för att säkerställa att en beställning av dessa åtgärder kan hittas. Eftersom vi bara har två åtgärder, är beställningen uppenbar och den producerade planen är den som produceras av Graphplan: A, B, C. Ett problem kan uppstå när algoritmen överväger minst tre åtgärder samtidigt. Faktum är att om vi betraktar de tre åtgärderna C, D, E sådana att C tillåter D men D inte tillåter C, D tillåter E men E inte tillåter D, och E godkänner inte C men C inte tillåter E, ingen beställning av {C, D, E} kan hittas:  på C, D, E, E, E, D, D är omöjliga eftersom C inte godkänner E; och med en cirkulär permutation av dessa två beställningar, alla andra order är omöjliga. Ett exempel på en klassisk referensdomän där detta problem kan uppstå är domänen Blocks-world med följande åtgärder: MoveFromTable(A, B), MoveFromTable(B, C) och MoveFromTable(C, A). I det ursprungliga tillståndet, de tre blocken A, B och C är på bordet, och målet är {on (A, B), on(B, C), on(C, A)} som är uppenbarligen omöjligt; men det måste bevisas av planeraren. De tre åtgärder som beskrivs ovan ger förslag på målet, och det finns inget par av ömsesidigt uteslutande åtgärder. I själva verket, MoveFromTable(B, C) tillåter MoveFromTable(A, B): efter att flytta B på C, är det fortfarande möjligt att flytta A på B. Men MoveFromTable(A, B) tillåter inte MoveFromTable(B, C): efter att ha flyttat A på B är B inte klart, så det kan inte tas (ett block kan flyttas endast när det är klart). Vi är exakt i det fall som beskrivs ovan med åtgärderna C, D, E. Det är viktigt att notera att sökandet efter en beställning kan utföras i polynom tid av en topologisk sort algoritm. I avsnitt 2 presenterar vi en formell analys av självständighets- och tillståndsförhållandena. I Avsnitt 3 beskriver vi sättet att ändra diagramplan för att ta fram tillståndsbaserade planer, och för att omvandla dem till självständighetsbaserade planer. I Avsnitt 4 visar vi experimentella resultat som jämför effektiviteten i vårt förhållningssätt till den klassiska grafplan. Relaterat arbete diskuteras i avsnitt 5 och våra slutsatser redovisas i avsnitt 6.  För det första formaliserar vi strukturen i planritningen (jfr. Punkt 2.1. Sedan föreslår vi att diagramplan, med hjälp av självständighetskriteriet, överkonspirerar valet av åtgärder i de uppsättningar åtgärder som beaktas samtidigt (jfr. Se avsnitt 2.2. Vi visar sedan att detta kriterium kan mildras för att få fram planer med en annan struktur. Dessa planer kan lätt omvandlas till planer som Graphplan kunde ha producerat (jfr punkt 2.3), och som leder till samma resulterande tillstånd. Det viktigaste inslaget i en plan är en åtgärd, som är ett exempel på en operatör. I diagramplan är operatörer Strips-liknande operatörer, utan att förneka sina förutsättningar. Vi använder ett första ordningens logikspråk L, konstruerat från ordförråden Vx, Vc, Vp som respektive betecknar finita osammanhängande uppsättningar av symboler av variabler, konstanter och predikat. Vi använder inte funktionssymboler. En operatör, betecknad som o, är en trippel  tillpr, annons, de med pr, annons och de betecknar ändliga uppsättningar av atomformler av språket L. Prec(o), Add(o) respektive Del(o) betecknar uppsättningarna pr, ad och de av operatören o. O betecknar den ändliga uppsättningen av operatörer. Ett tillstånd är en ändlig uppsättning atomformler på marken (dvs. utan några variabla symboler). En atomformel på marken kallas också ett förslag. P betecknar uppsättningen av alla de satser som kan konstrueras med språket L. En åtgärd som betecknas av en är en mark instans o på ett sätt som är ett exempel på en operatör o som erhålls genom att tillämpa en substitution  på ett språk som L definieras med språket L så att pr på marken, annonsen och de på marken och annonsen och de på är osammanhängande uppsättningar. Prec(a), Add(a), Del(a) respektive betecknar uppsättningarna pr., ad och de och representerar förutsättningarna, lägger till och tar bort a. A betecknar den ändliga uppsättningen åtgärder, som är alla möjliga markinstanciations av O:s operatörer. Den huvudsakliga struktur som vi kommer att använda i följande, sekvensen av åtgärder, kommer att representera planerna i diagramplan och LCGP: den definierar den ordning i vilken åtgärderna beaktas med tanke på genomförandet av de åtgärder som de innehåller. Alla sekvenser och uppsättningar av åtgärder kommer att vara ändliga. En sekvens av uppsättningar av åtgärder S noteras  och Qi på, med n  till. Om n = 0, S är den tomma sekvensen: S =  och Qi.0 =  på; om n > 0, S kan noteras, Q1, Q2,..., Qn. Om åtgärderna är singletons (dvs. Q1 = {a1}, Q2 = {a2},..., Qn = {an}), den tillhörande sekvensen av åtgärder kallas en sekvens av åtgärder och kommer att noteras
I REF införs begreppet godkända lineariseringar, vilket innebär en ordning för genomförandet av två åtgärder.
Least commitment in graphplan
{'venue': 'Artificial Intelligence', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}