Stanford Research Institute Problemlösare

Stanford Research Institute Problem Solver, känd under sin akronym STRIPS , är en automatiserad planerare utvecklad av Richard Fikes och Nils Nilsson 1971 på SRI International . Samma namn användes senare för att referera till det formella språket för inmatningarna till denna planerare. Detta språk är basen för de flesta språken för att uttrycka av automatiserade planeringsproblem som används idag; sådana språk är allmänt kända som handlingsspråk . Den här artikeln beskriver bara språket, inte planeraren.

Definition

En STRIPS-instans består av:

• Ett initialt tillstånd;
• Specifikationen av målet anger – situationer som planeraren försöker nå;
• En uppsättning åtgärder. För varje åtgärd ingår följande:
  • förutsättningar (vad måste fastställas innan åtgärden utförs);
  • postvillkor (vad som fastställs efter att åtgärden utförts).

Matematiskt är en STRIPS-instans en fyrfaldig ${\displaystyle \langle P,O,I,G\rangle } ,$ där varje komponent har följande betydelse:

1. $P$ är en uppsättning villkor (dvs propositionsvariabler );
2. $O$ är en uppsättning operatorer (dvs. åtgärder); varje operator är i sig en fyrdubbel ${\displaystyle \langle \alpha ,\beta ,\gamma ,\delta \rangle } , där$ varje element är en uppsättning villkor. Dessa fyra uppsättningar specificerar, i ordning, vilka villkor som måste vara sanna för att åtgärden ska kunna köras, vilka som måste vara falska, vilka som görs sanna av åtgärden och vilka som görs falska;
3. $I$ är initialtillståndet, givet som den uppsättning villkor som initialt är sanna (alla andra antas vara falska);
4. $G$ är specifikationen av måltillståndet; detta ges som ett par $\langle N,M\rangle$ , som anger vilka villkor som är sanna respektive falska för att ett tillstånd ska betraktas som ett måltillstånd.

En plan för en sådan planeringsinstans är en sekvens av operatörer som kan exekveras från initialtillståndet och som leder till ett måltillstånd.

Formellt är ett tillstånd en uppsättning villkor: ett tillstånd representeras av den uppsättning villkor som är sanna i det. Övergångar mellan tillstånd modelleras av en övergångsfunktion, som är en funktion som mappar tillstånd till nya tillstånd som är resultatet av exekvering av åtgärder. Eftersom tillstånd representeras av uppsättningar av villkor, är övergångsfunktionen relativt STRIPS-instansen $\langle P,O,I,G\rangle$ en funktion

$\operatorname {succ} :2^{P}\times O\rightarrow 2^{P},$

där $2^{P}$ är mängden av alla delmängder av $P$ , och är därför mängden av alla möjliga tillstånd.

Övergångsfunktionen $\operatorname {succ}$ för ett tillstånd ${\displaystyle C\subseteq P} ,$ kan definieras enligt följande, med det förenklade antagandet att åtgärder alltid kan utföras men inte har någon effekt om deras Förutsättningarna är inte uppfyllda:

$\operatorname {succ} (C,\langle \alpha ,\beta ,\gamma ,\delta \rangle )$	= $(C\backslash \delta )\cup \gamma$	om $\alpha \subseteq C$ och $\beta \cap C=\varnothing$
	= $C$	annat

Funktionen $\operatorname {succ}$ kan utökas till sekvenser av åtgärder med följande rekursiva ekvationer:

$\operatorname {succ} (C,[\ ])=C$

$\operatorname {succ} (C,[a_{1},a_{2},\ldots,a_{n}]) =\operatörsnamn {succ} (\operatörsnamn {succ} (C,a_{1}),[a_{2},\ldots ,a_{n}])$

En plan för en STRIPS-instans är en sekvens av åtgärder så att det tillstånd som blir resultatet av att utföra åtgärderna i ordning från det initiala tillståndet uppfyller målvillkoren. Formellt är $[a_{1},a_{2},\ldots ,a_{n}]$ en plan för ${\ displaystyle G=\langle N,M\rangle }$ om $F=\operatörsnamn {succ} (I,[a_{1} ,a_{2},\ldots ,a_{n}])$ uppfyller följande två villkor:

$N\subseteq F$

$M\cap F=\varnothing$

Tillägg

Ovanstående språk är faktiskt den propositionella versionen av STRIPS; i praktiken handlar förhållanden ofta om objekt: till exempel att positionen för en robot kan modelleras av ett predikat $At$ , och $At(room1)$ betyder att roboten är i rum1. I det här fallet kan åtgärder ha fria variabler , som implicit är existentiellt kvantifierade. Med andra ord representerar en handling alla möjliga propositionella åtgärder som kan erhållas genom att ersätta varje fri variabel med ett värde.

Det initiala tillståndet anses vara fullt känt på språket som beskrivs ovan: villkor som inte finns i $I$ antas alla vara falska. Detta är ofta ett begränsande antagande, eftersom det finns naturliga exempel på planeringsproblem där utgångsläget inte är fullt känt. Förlängningar av STRIPS har utvecklats för att hantera delvis kända initiala tillstånd.

Ett exempel på SRIPS-problem

En apa är på plats A i ett labb. Det finns en låda på plats C. Apan vill ha bananerna som hänger i taket på plats B, men den måste flytta lådan och klättra upp på den för att nå dem.

 Initialt tillstånd: At(A), Level(låg), BoxAt(C), BananasAt(B) Måltillstånd: Ha(bananer) Åtgärder: // flytta 

 från X till Y _Flytta(X, Y)_ Förutsättningar: At(X) ), Level(låg) Postvillkor: inte At(X), At(Y) // klättra upp på rutan _ClimbUp(Location)_ Förutsättningar: At(Location), BoxAt(Location), Level(low) Postconditions: Level( hög), inte Level(låg) // klättra ner från rutan _ClimbDown(Location)_ Förutsättningar: At(Location), BoxAt(Location), Level(high) Postconditions: Level(low), not Level(high) // flytta apa och box från X till Y _MoveBox(X, Y)_ Förutsättningar: At(X), BoxAt(X), Level(low) Postvillkor: BoxAt(Y), inte BoxAt(X), At(Y), inte Vid(X) // ta bananerna _TakeBananas(Location)_ Förutsättningar: At(Location), BananasAt(Location), Level(high) Postconditions: Have(bananer) 

Komplexitet

Att bestämma om det finns någon plan för en propositionell STRIPS-instans är PSPACE-komplett . Olika restriktioner kan tillämpas för att avgöra om en plan existerar i polynomtid eller åtminstone göra den till ett NP-komplett problem.

Makrooperatör

I problemet med apa och banan måste robotapan utföra en sekvens av åtgärder för att nå bananen i taket. En enda åtgärd ger en liten förändring i spelet. För att förenkla planeringsprocessen är det vettigt att uppfinna en abstrakt handling, som inte är tillgänglig i den normala regelbeskrivningen. Superaktionen består av handlingar på låg nivå och kan nå mål på hög nivå. Fördelen är att beräkningskomplexiteten är lägre och längre uppgifter kan planeras av lösaren.

Att identifiera nya makrooperatorer för en domän kan realiseras med genetisk programmering . Tanken är att inte planera själva domänen, utan i försteget skapas en heuristik som gör det möjligt att lösa domänen mycket snabbare. I samband med förstärkningsinlärning kallas en makrooperatör ett alternativ. I likhet med definitionen inom AI-planering är tanken att tillhandahålla en tidsmässig abstraktion (spänner över en längre period) och att modifiera speltillståndet direkt på ett högre lager.

Se även

• Action Description Language (ADL)
• Automatiserad planering
• Hierarkiskt uppgiftsnätverk
• Planning Domain Definition Language (PDDL)
• Sussman anomali

Vidare läsning

• C. Bäckström och B. Nebel (1995). Komplexitetsresultat för SAS+ planering. Computational Intelligence , 11:625-656.
• T. Bylander (1991). Komplexitetsresultat för planering. I Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI'91), sidorna 274-279.
•   Russell, Stuart J .; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2