Plano de gráficos

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 nombre " plan de grafos " se debe al uso de un grafo 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 grafo del espacio de estados .

En el grafo del espacio de estados :

• Los nodos son estados posibles,
• y los bordes indican la posibilidad de alcanzarlo mediante una acción determinada.

Por el contrario, en el gráfico de planificación de Graphplan :

• Los nodos son acciones y hechos atómicos, organizados en niveles alternos,
• y los bordes son de dos tipos:
  1. desde un hecho atómico hasta las acciones para las que es una condición,
  2. Desde una acción hasta los hechos atómicos, los hace verdaderos o falsos.

El primer nivel contiene información atómica verídica que identifica el estado inicial.

También se mantienen listas de hechos incompatibles que no pueden ser ciertos al mismo tiempo y de acciones incompatibles que no pueden ejecutarse simultáneamente.

A continuación, el algoritmo extiende iterativamente el grafo de planificación, demostrando que no existen soluciones de longitud l-1 antes de buscar planes de longitud l mediante encadenamiento hacia atrás: suponiendo que los objetivos son verdaderos, Graphplan busca las acciones y los estados anteriores desde los que se pueden alcanzar los objetivos, eliminando tantos como sea posible gracias a la información de incompatibilidad.

Un enfoque estrechamente relacionado con la planificación es la Planificación como Satisfacibilidad ( Satplan ). Ambos reducen el problema de la planificación automatizada a la búsqueda de planes con diferentes horizontes temporales fijos.

• A. Blum y M. Furst (1997). Planificación rápida mediante análisis de grafos de planificación . Inteligencia artificial. 90:281-300.

• Página principal de Graphplan de Avrim Blum
• PLPLAN: Una implementación de GraphPlan en Java
• NPlanner: Una implementación de GraphPlan en .NET. Archivado el 31/12/2013 en Wayback Machine.
• Emplan y JavaGP: implementaciones de Graphplan en C++ y Java.
• Conferencia de MIT OpenCourseWare sobre GraphPlan y la creación de gráficos de planificación.