Grafos de Planificación y Heurísticas

Los grafos de planificación y las heurísticas independientes del dominio son las técnicas que agilizaron la planificación clásica, al analizar de forma compacta la alcanzabilidad y al estimar automáticamente la distancia de un estado al objetivo.

Definition

Un grafo de planificación es una estructura en capas que intercala niveles de proposiciones y acciones con restricciones mutex para aproximar la alcanzabilidad; las heurísticas de planificación son funciones, a menudo calculadas a partir de dichas estructuras o de problemas con eliminación relajada, que estiman el costo de alcanzar el objetivo desde un estado.

Scope

Este tema abarca la estructura de datos del grafo de planificación introducida por Graphplan, incluyendo los niveles de proposiciones y acciones y las relaciones de exclusión mutua (mutex) que capturan qué hechos y acciones no pueden coexistir, y la familia de heurísticas independientes del dominio derivadas de problemas relajados (notablemente ignorando los efectos de eliminación) que impulsan los planificadores modernos de búsqueda heurística. Aborda cómo se calcula y utiliza la información de alcanzabilidad para guiar la búsqueda. El modelo de planificación clásica subyacente se cubre en el tema relacionado.

Core questions

• ¿Cómo representa un grafo de planificación las proposiciones y acciones alcanzables nivel por nivel?
• ¿Qué son las relaciones mutex y cómo capturan la incompatibilidad entre hechos y acciones?
• ¿Cómo se utiliza la relajación de eliminación para derivar heurísticas de planificación admisibles o informativas?
• ¿Cómo estas heurísticas convierten la planificación en una búsqueda heurística eficiente?

Key concepts

• grafo de planificación
• niveles de proposiciones y acciones
• exclusión mutua (mutex)
• Graphplan
• relajación de eliminación
• heurísticas h-max y h-add
• heurística FF y planes relajados
• búsqueda heurística hacia adelante

Key theories

Grafo de planificación y Graphplan

Graphplan construye un grafo de planificación que codifica de forma compacta qué proposiciones y acciones son alcanzables en cada nivel y qué pares son mutuamente excluyentes, luego extrae un plan buscando hacia atrás a través de esta estructura, acelerando drásticamente la planificación.

Heurísticas de relajación de eliminación

Ignorar los efectos de eliminación de las acciones produce un problema de planificación relajado que es mucho más fácil de resolver; el costo de resolver esta relajación proporciona heurísticas informativas, a menudo admisibles (como h-max y h-add y la heurística FF) que guían la búsqueda hacia adelante.

Planificación por búsqueda heurística

Los planificadores clásicos de última generación combinan heurísticas derivadas automáticamente con búsqueda primero el mejor o búsqueda voraz y mejoras como operadores preferidos, logrando un rendimiento general sólido en diversos dominios.

Clinical relevance

Los grafos de planificación y las heurísticas de relajación de eliminación son la tecnología central de los planificadores ganadores de competiciones utilizados en robótica, logística y control autónomo, donde permiten a los planificadores independientes del dominio resolver problemas grandes rápidamente sin una guía de búsqueda elaborada manualmente.

History

Graphplan de Blum y Furst (1995, versión de revista 1997) introdujo el grafo de planificación y revolucionó la velocidad de planificación. A finales de los años 90 y en la década de 2000, surgieron las heurísticas de relajación de eliminación, con el planificador FF (Hoffmann y Nebel, 2001) y posteriormente Fast Downward (Helmert, 2006) estableciendo la búsqueda hacia adelante heurística como el enfoque dominante.

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

¿Qué es un mutex en un grafo de planificación?

Una relación mutex (exclusión mutua) marca dos proposiciones o dos acciones que no pueden coexistir o aplicarse al mismo nivel, por ejemplo, porque una acción elimina una precondición de la otra. Los mutex hacen que el grafo de planificación sea una aproximación más precisa de la verdadera alcanzabilidad.

¿Por qué ignorar los efectos de eliminación proporciona una heurística útil?

Sin los efectos de eliminación, lograr un objetivo nunca deshace otro, por lo que el problema relajado es mucho más fácil de resolver y nunca más difícil que el original. El costo del plan relajado es, por lo tanto, un límite inferior o una estimación informada del costo real, lo que lo convierte en una heurística efectiva para guiar la búsqueda.