Graphplan

Graphplan és un algoritme per a la planificació automàtica desenrollat per Avrim Blum i Merrick Furst en 1995. L'algoritme pren com a entrada un problema de planificació expressat en STRIPS i produïx, de ser posible, una seqüència d'operacions per a aplegar a un estat final.

El nom graphpla és per l'utilisació d'un grafo de planificació, per a reduir la cantitat de busca necessària per a trobar la solució en l'exploració directa d'un grafo d'espai d'estat.

En un grafo d'espai d'estat:

• els nodos són possibles estats,
• i les arestes indiquen la alcanzabilidad a través de certes accions.

Pel contrari, en un grafo de planificació:

• els nodos són les accions i fets atòmics, disposts en nivells alterns,
• i les arestes són de dos tipos:
  1. d'un fet atòmic a les accions de les quals és una condició,
  2. d'una acció als fets atòmics a on es convertix en verdader o fals.

El primer nivell conté fets atòmics verdaders que identifiquen l'estat inicial.

També es mantenen les llistes de fets incompatibles que no poden ser verdaders al mateix temps i accions incompatibles que no es poden eixecutar en conjunt.

L'algoritme estén iterativamente el grafo de planificació, provant que no hi ha solucions de llongitut i-1 abans de buscar plans de llongitut i per encadenament cap a arrere: suponent que els objectius són verdaders, l'algoritme de Graphplan busca les accions i estats previs des del qual l'objectiu pot ser alcançat, podant molts d'ells mentres siga possible gràcies a l'informació incompatible.

Un enfocament molt relacionat en la planificació és la Planificació com Satisfacibilidad (Satplan). Abdós reduïxen el problema de planificació automàtica per a buscar els plans de diferents llongituts de tamany fix.

Referències

• A. Blum and M. Furst (1997). Fast planning through planning graph analysis. Artificial intelligence. 90:281-300.

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