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.
El nombre graphplan es debido a la utilización de un grafo de planificación, para reducir la cantidad de búsqueda necesaria para encontrar la solución en la exploración directa de un grafo de espacio de estado.
En un grafo de espacio de estado:
- los nodos son posibles estados,
- y las aristas indican la alcanzabilidad a través de ciertas acciones.
Por el contrario, en un grafo de planificación:
- los nodos son las acciones y hechos atómicos, dispuestos en niveles alternos,
- y las aristas son de dos tipos:
- de un hecho atómico a las acciones de las cuales es una condición,
- de una acción a los hechos atómicos donde se convierte en verdadero o falso.
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.
Un enfoque muy relacionado con la planificación es la Planificación como Satisfacibilidad (Satplan). Ambos reducen el problema de planificación automática para buscar los planes de diferentes longitudes de tamaño fijo.
Referencias
editar- 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
Enlaces externos
editar- Avrim Blum, página de inicio de Graphplan
- PLPLAN: Implementación en Java del algoritmo GraphPlan
- NPlanner: Implementación en .NET del algoritmo GraphPlan Archivado el 31 de diciembre de 2013 en Wayback Machine.
- Emplan y JavaGP: Implementación en C++ y Java del algoritmo Graphplan
Datos: Q5597338
