The Causal Graph heuristic (CG) como bien sabemos no se encuentra basado sobre los delete-relaxation pero si sobre un análisis de la estructura del problema que se representa en los Causal Graph y DTG.
Con el CG Heuristic conseguimos una estimación del número de acciones necesarias para conseguir los objetivos desde un state s a un goal state s'. Siempre asumiendo que el CG es acyclic.
Éste es el punto débil de esta heurística, solo funciona sobre acyclic CG.
Geffner lo que propone es una formulación declarativa de los CG que según él lo hacen más simple y general. También comenta que la nueva heurística que él propone es mucho más rápida que la de Helmert y que además no funciona en cyclic CG. Para ésto lo que su heurística requiere és información adicional, que la llama plus Context.
Comienza comentando el funcionamiento the CG Heuristic, y como Helmert utilizó el algoritmo Dijkstra para calcular el camino más corto. Y superficialmente dice que Helmert hizo una modificación en Dijkstra.
Después explica la limitación que tiene el CG heuristic, principal motivación para acuñar el termino Context (Información adicional). Geffner dice que el procedimiento que utiliza Helmert al momento de solucionar los subproblemas no es completo, ya que consigue valores intermedios utilizando efectos secundarios, pero ignorando el impacto que ellos pueden tener en el futuro. Más concretamente se refiere a lo siguiente: Helmert, primero consigue un plan con una variable que no tiene padres desde un state s, y después con cada una de las condiciones genera un sub-problema y obtiene unos sub-planes, ignorando las condiciones que hagan referencia a la variable padre, desde el mismo state s. Es decir, no tiene en cuenta el impacto que pueden tener a futuro los sub-planes, ya que los calcula desde el mismo state s inicial.
Lo que Geffner propone es que la heurística se calcule con el estado que se vaya generando con los sub-planes, es decir, que se mantenga esta información (el la llama Context). Para ésto define la heurística en términos de una Additive heuristic (demostrando que the CG Heuristic de Helmert en realidad es una Additive Heuristic), con la única diferencia que los valores de la Heuristic son computados no solo sobre el estado inicial sino sobre todos los estados que se van generando.
En pocas palabras lo que Geffner propone es lo que yo estaba haciendo, realizar los cálculos sobre el estado que se va generando.
La otra parte es que él dice, que su heurística funciona para cyclic CG, yo eso no lo veo muy claro. Ya que él dice solamente que eso va implicit over costs. Para mi si el la basa en los DTG tarde o temprano llegaría a un ciclo.
Lo que no me convence del todo es que no coloca pruebas del buen funcionamiento de su heurística, y se queda solamente en las formulaciones matemáticas.
No hay comentarios:
Publicar un comentario