Planificacion

Llamaremos planificación al proceso de buscar y articular una secuencia de acciones que permitan alcanzar un objetivo. Por ejemplo, si nuestro objetivo es viajar desde un pueblo perdido de Asturias y queremos llegar a Guatemala, la secuencia de acciones serían los diferentes medios de transporte que hay que tomar para llegar. Otro ejemplo podría ser que tuviéramos

un robot en un laberinto y nuestro objetivo fuera sacarlo de él; en este caso, nuestras acciones serían los tramos recorridos en línea recta y los giros que da el robot.

Para formalizar el problema de planificación existen 2 notaciones principales: ADL y STRIPS. Ambos coinciden en el uso de la lógica para representar el estado inicial, el objetivo y las acciones. También están de acuerdo en que, para aplicar una acción, es necesario cumplir con unas condiciones previas y, después de haber ejecutado la acción, habrá causado algunos efectos.

Para obtener la secuencia de acciones, es decir, el resultado del problema de planificación, existen varios enfoques:

Búsquedas en el espacio de estados que operan hacia adelante (desde el estado inicial), o hacia atrás (desde la meta) aplicando las acciones. También existen heurísticas (estrategias) efectivas que nos ayudan en la búsqueda. Estos enfoques funcionan bien cuando los subobjetivos son independientes.

Si los subobjetivos no son independientes, a menudo es una buena idea utilizar algoritmos de planificación de orden parcial (POP), que exploran el espacio del plan sin comprometerse con una secuencia de acciones completamente ordenada. Trabajan hacia atrás desde el objetivo y agregan acciones para planificar cómo alcanzar cada subobjetivo.

Otras estrategias prometedoras son el algoritmo GRAPHPLAN y el algoritmo SATPLAN.

A la hora de trabajar no en mundos cerrados, sino en el mundo real, debemos tener en cuenta varias consideraciones. Muchas acciones consumen recursos: tiempo, dinero, materias primas, etc. por lo que debemos tener en cuenta medidas numéricas. Las redes de tareas jerárquicas (HTN) permiten sugerencias sobre el dominio del diseñador. La información incompleta se puede manejar mediante la planificación que utiliza acciones sensoriales para obtener la información que necesita. La planificación multiagente es necesaria cuando hay otros agentes en el entorno con los que cooperar, competir o coordinarse.

Los problemas y soluciones que se abordan en la planificación tienen aplicaciones directas en la gestión de tareas (workflow), control de misiones complejas (espaciales, satélites, militares, etc.), turismo (visitas a ciudades, planificación de rutas,…), procesos de enseñanza/aprendizaje , robótica (planificar caminos), ...

Para el problema de la planificación, las licencias libres han brillado por su ausencia. Sin embargo, todos los algoritmos se distribuyen con su código, lo que también es cierto en arquitecturas embebidas como PRODIGY, muy utilizadas en planificación.