Graphplan

Graphplan es un algoritmo para la planificación automática desarrollado por Avrim Blum y Merrick Furst en 1995.El algoritmo toma como entrada un problema de planificación expresado en STRIPS y produce, de ser posible, una secuencia de operaciones para llegar a un estado final.En un grafo de espacio de estado: Por el contrario, en un grafo de planificación: El primer nivel contiene hechos atómicos verdaderos que identifican el estado inicial.También se mantienen las listas de hechos incompatibles que no pueden ser verdaderos al mismo tiempo y acciones incompatibles que no se pueden ejecutar en conjunto.El algoritmo extiende iterativamente el grafo de planificación, probando que no hay soluciones de longitud i-1 antes de buscar planes de longitud i por encadenamiento hacia atrás: suponiendo que los objetivos son verdaderos, el algoritmo de Graphplan busca las acciones y estados previos desde el cual el objetivo puede ser alcanzado, podando muchos de ellos mientras sea posible gracias a la información incompatible.