Graphplan es un algoritmo para la planificación automatizada desarrollado por Avrim Blum y Merrick Furst en 1995. Graphplan toma como entrada un problema de planificación expresado en STRIPS y produce, si es posible, una secuencia de operaciones para alcanzar un estado objetivo.
El plan del gráfico de nombres se debe al uso de un gráfico de planificación novedoso , para reducir la cantidad de búsqueda necesaria para encontrar la solución a partir de la exploración directa del gráfico del espacio de estados .
También se mantienen listas de hechos incompatibles que no pueden ser ciertos al mismo tiempo y acciones incompatibles que no pueden ejecutarse juntas.
Luego, el algoritmo extiende iterativamente el gráfico de planificación, demostrando que no hay soluciones de longitud l-1 antes de buscar planes de longitud l mediante el encadenamiento hacia atrás: suponiendo que las metas sean verdaderas, Graphplan busca las acciones y estados previos a partir de los cuales las metas pueden ser alcanzados, podando tantos como sea posible gracias a la información de incompatibilidad.
Un enfoque estrechamente relacionado con la planificación es la planificación como satisfacción ( Satplan ). Ambos reducen el problema de planificación automatizada para buscar planes de diferentes longitudes de horizonte fijo.