#LyX 2.3 created this file. For more info see http://www.lyx.org/ \lyxformat 544 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \begin_preamble \usepackage{amssymb} \end_preamble \use_default_options true \begin_modules algorithm2e \end_modules \maintain_unincluded_children false \language spanish \language_package default \inputencoding auto \fontencoding global \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_minted 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style french \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Standard \series bold Planificar \series default es obtener una secuencia de acciones para llegar a un estado objetivo. Esto se puede hacer con técnicas de búsqueda, pero el espacio de búsqueda suele ser muy complejo, los problemas no suelen ser descomponibles y los estados de búsqueda suelen ser complejos porque requieren buena parte del entorno, por lo que se suelen usar algoritmos específicos. \end_layout \begin_layout Standard El \series bold problema del marco \series default o \series bold de la estructura \series default ( \emph on \lang english frame problem \emph default \lang spanish ) es el de qué permanece sin cambios al aplicar una regla; el de la \series bold cualificación \series default es qué debe cumplirse para poder ejecutar una regla, y el de la \series bold ramificación \series default es qué elementos cambian. \end_layout \begin_layout Standard Un \series bold plan lineal \series default es una secuencia de acciones para ir de un estado inicial a un estado objetivo, y un \series bold plan no lineal \series default es una familia de acciones con un orden parcial de forma que cada secuenciación de esas acciones que respete el orden parcial es un plan lineal. \end_layout \begin_layout Section STRIPS \end_layout \begin_layout Standard \series bold STRIPS \series default ( \emph on \lang english Stanford Research Institute Problem Solver \emph default \lang spanish ) es un planificador lineal o \series bold de orden total \series default que usa una forma restringida de lógica de situaciones. Los problemas están formados por un estado inicial, un estado objetivo y un conjunto de acciones, y los literales o proposiciones atómicas que aparecen no tienen variables resultado de funciones. \end_layout \begin_layout Standard Los estados inicial e intermedios son conjunciones de literales sin variables, y los estados objetivo y subobjetivos son conjunciones de literales en las que todas las variables se cuantifican existencialmente con ámbito global en la proposición. \end_layout \begin_layout Standard Un \series bold unificador \series default entre dos fórmulas lógicas que no comparten variables libres es una asociación de variables a valores tal que, al aplicarla por sustitución a las variables libres de las dos fórmulas, queda la misma fórmula. Si existe, las dos fórmulas \series bold unifican \series default . \end_layout \begin_layout Standard Las acciones están formadas por: \end_layout \begin_layout Itemize Un \series bold antecedente \series default o \series bold fórmula de precondición \series default , una conjunción de proposiciones atómicas en que las variables (libres) se entienden cuantificadas existencialmente, y que indica cuándo se puede aplicar la regla. Para que la regla sea aplicable a un estado, debe existir un \series bold unificador más general \series default de la fórmula a la conjunción de un subconjunto de los literales en el estado, que se puede obtener creando unificadores de literales y viendo que sean consistentes. \end_layout \begin_layout Itemize Una \series bold lista de supresión \series default , una lista de literales cuyas variables deben aparecer en el antecedente y que, al aplicar la regla, dejan de ser ciertos. \end_layout \begin_layout Itemize Una \series bold fórmula de adición \series default , una lista de literales cuyas variables deben aparecer en el antecedente y que, al aplicar la regla, se hacen ciertos. \end_layout \begin_layout Section Búsqueda \end_layout \begin_layout Standard Lo más sencillo es obtener un plan lineal con técnicas de búsqueda ya conocidas, pero como las descripciones de acciones indican tanto precondiciones como efectos, la búsqueda se puede hacer hacia delante, del estado inicial hasta un objetivo, o hacia atrás, del objetivo al estado inicial. \end_layout \begin_layout Standard En el caso de reglas tipo STRIPS, aplicar una regla hacia atrás genera un subobjetivo. Para obtenerlo, unificamos un subconjunto de los literales del objetivo con la fórmula de adición, aplicamos el unificador a todo el objetivo y la regla y tomamos la conjunción de la fórmula de precondición de la regla con la regresión de los literales del objetivo que no están en el subconjunto de literales que se unificó con la regla de adición. La \series bold regresión \series default de un literal es Falso si el literal aparece en la lista de supresión, Cierto si aparece en la de adición y el propio literal en otro caso. \end_layout \begin_layout Standard El espacio de subobjetivos es más amplio que el espacio de estados obtenido de aplicar las reglas hacia delante, pero el literal Cierto se puede obviar y se pueden podar los subobjetivos que contienen Falso o que es fácil ver en el contexto que son imposibles. \end_layout \begin_layout Standard La búsqueda exhaustiva no es práctica, por lo que se deben usar heurísticas. \end_layout \begin_layout Section Pila de objetivos \end_layout \begin_layout Standard STRIPS usa una planificación lineal mediante una pila de subobjetivos con el Algoritmo \begin_inset CommandInset ref LatexCommand ref reference "alg:strips" plural "false" caps "false" noprefix "false" \end_inset o \begin_inset CommandInset ref LatexCommand ref reference "alg:stripshit" plural "false" caps "false" noprefix "false" \end_inset , que puede usar heurísticas para ordenar los literales de un objetivo compuesto al apilarlos y para elegir qué unificador usar y qué regla elegir para un objetivo simple. Se pueden obtener planes subóptimos por una mala ordenación de los objetivos. \begin_inset Foot status open \begin_layout Plain Layout De hecho, en algunos problemas una mala ordenación puede evitar encontrar una solución. \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset Float algorithm wide false sideways false status open \begin_layout Plain Layout \begin_inset ERT status open \begin_layout Plain Layout \backslash Entrada{Estado inicial $s$, estado objetivo $o$ y conjunto de reglas $R$.} \end_layout \begin_layout Plain Layout \backslash Salida{Camino $P$ de $s$ a $f$.} \end_layout \begin_layout Plain Layout $P \backslash gets(s)$ \backslash ; \end_layout \begin_layout Plain Layout $S \backslash gets(o)$% \end_layout \begin_layout Plain Layout \backslash tcp*{{ \backslash rm $S$ es la pila de objetivos, que también contiene reglas.}} \end_layout \begin_layout Plain Layout \backslash Mientras{$S \backslash neq \backslash emptyset$}{ \end_layout \begin_layout Plain Layout Extraer el último $p$ de $S$ \backslash ; \end_layout \begin_layout Plain Layout \backslash uSSi{$p$ es una regla aplicable a $s$}{ \end_layout \begin_layout Plain Layout Aplicar $p$ a $s$ obteniendo un nuevo $s$ \backslash ; \end_layout \begin_layout Plain Layout $P \backslash gets Pps$ \backslash ; \end_layout \begin_layout Plain Layout } \backslash uEnOtroCasoSi{$p$ unifica con $s$ por algún $U$}{ \end_layout \begin_layout Plain Layout Aplicar $U$ a todos los elementos de $S$ \backslash ; \end_layout \begin_layout Plain Layout } \backslash uEnOtroCasoSi{$p=:l_1 \backslash land \backslash dots \backslash land l_n$ con $n \backslash geq2$}{ \end_layout \begin_layout Plain Layout $S \backslash gets Spl_1 \backslash cdots l_n$ \backslash ; \end_layout \begin_layout Plain Layout } \backslash EnOtroCaso{ \end_layout \begin_layout Plain Layout Elegir $r \backslash in R$ cuya fórmula de adición unifique con $p$ \backslash ; \end_layout \begin_layout Plain Layout Sea $l_1 \backslash land \backslash dots \backslash land l_n$ la precondición de $r$ unificada, \end_layout \begin_layout Plain Layout $S \backslash gets Srl_1 \backslash cdots l_n$ \backslash ; \end_layout \begin_layout Plain Layout } \end_layout \begin_layout Plain Layout } \end_layout \end_inset \end_layout \begin_layout Plain Layout \begin_inset Caption Standard \begin_layout Plain Layout \begin_inset CommandInset label LatexCommand label name "alg:strips" \end_inset Método de planificación de STRIPS. \end_layout \end_inset \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset Float algorithm wide false sideways false status open \begin_layout Plain Layout estado:=estado-inicial; plan:=[ ]; pila:=[ ]; \end_layout \begin_layout Plain Layout apilar objetivo en pila; \end_layout \begin_layout Plain Layout repetir hasta que pila esté vacía \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset si el objetivo en la cima de la pila se empareja con descripción del estado entonces \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset \begin_inset space \quad{} \end_inset quitar de la pila y aplicar la sustitución a las expresiones que están debajo \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset sino, si el objetivo en la cima de pila es conjunción de objetivos entonces \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset \begin_inset space \quad{} \end_inset seleccionar un orden de los sub-objetivos y apilarlos en pila \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset sino, si resueltos todos los sub-objetivos pero no resuelto objetivo entonces \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset \begin_inset space \quad{} \end_inset reconsiderar objetivo compuesto y apilarlos en la pila \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset sino, si la cima de pila es un objetivo simple \begin_inset Quotes cld \end_inset sg \begin_inset Quotes crd \end_inset entonces \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset \begin_inset space \quad{} \end_inset elegir operador \begin_inset Quotes cld \end_inset OP \begin_inset Quotes crd \end_inset cuya lista de adición se empareja con \begin_inset Quotes cld \end_inset sg \begin_inset Quotes crd \end_inset \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset \begin_inset space \quad{} \end_inset reemplazar el objetivo \begin_inset Quotes cld \end_inset sg \begin_inset Quotes crd \end_inset con el operador \begin_inset Quotes cld \end_inset OP \begin_inset Quotes crd \end_inset \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset \begin_inset space \quad{} \end_inset apilar precondiciones de \begin_inset Quotes cld \end_inset OP \begin_inset Quotes crd \end_inset en pila \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset sino, si la cima de la pila es un operador \begin_inset Quotes cld \end_inset OP \begin_inset Quotes crd \end_inset entoncces \end_layout \begin_layout Plain Layout \begin_inset space \quad{} \end_inset \begin_inset space \quad{} \end_inset estado:=aplicar(OP,estado); plan=[plan;OP] \end_layout \begin_layout Plain Layout \begin_inset Caption Standard \begin_layout Plain Layout \begin_inset CommandInset label LatexCommand label name "alg:stripshit" \end_inset Versión de mierda del algoritmo STRIPS que aparece en las diapositivas y por la que pueden preguntar. \end_layout \end_inset \end_layout \end_inset \end_layout \begin_layout Section Planificación de orden parcial \end_layout \begin_layout Standard La planificación no lineal o \series bold de orden parcial \series default se basa en descomponer el problema y trabajar en varios subobjetivos independie ntemente y creando un plan a partir de ellos. Suele haber acciones ficticias inicio y final. La \series bold planificación de compromiso mínimo \series default es la idea de tomar solo las acciones y unificaciones estrictamente necesarias. \end_layout \begin_layout Standard Aunque podemos representar un plan con un diagrama de grafo de orden parcial, también podemos hacerlo como sigue: dibujamos todas las acciones a realizar con un círculo, conectado por debajo a los literales de la precondición y por encima a los de la lista de adición, representados por un cuadrado, y en particular inicio tiene como lista de adición las condiciones iniciales y fin tiene como precondiciones los literales del objetivo unificados. \end_layout \begin_layout Standard Cuando una acción \begin_inset Formula $A$ \end_inset va antes que otra \begin_inset Formula $B$ \end_inset , en general conectamos cada precondición de \begin_inset Formula $B$ \end_inset con una adición igual de \begin_inset Formula $A$ \end_inset o de otro ancestro que no aparezca en la lista de supresión de otra acción posterior en el camino, pero si el motivo de que vaya antes es que \begin_inset Formula $B$ \end_inset suprime una precondición de \begin_inset Formula $A$ \end_inset , se dibuja una flecha de \begin_inset Formula $A$ \end_inset a la precondición de \begin_inset Formula $B$ \end_inset que suprime, llamada \series bold arco amenaza \series default . \end_layout \begin_layout Standard Son planificadores no lineales NOAH, MOLGEN y SIPE. \end_layout \begin_layout Section Planificación jerárquica \end_layout \begin_layout Standard Consiste en dividir el problema en niveles de complejidad, de forma que se crea un plan de alto nivel y cada acción del plan se ejecuta con las acciones de un plan del nivel inferior, hasta llegar a un nivel suficiente de detalle. Esto permite resolver problemas complejos en los que no es posible hacer una búsqueda completa. \series bold ABSTRIPS \series default ( \emph on \lang english Abstraction-Based STRIPS \emph default \lang spanish ) es un planificador jerárquico creado por Earl D. Sacerdoti en 1973. \end_layout \begin_layout Standard El \series bold valor crítico \series default de una precondición es una medida de la dificultad de satisfacerla, como por ejemplo el número de acciones que satisfacen la precondición. En cada nivel de la jerarquía se tratan precondiciones con igual valor crítico, empezando con un plan que considera las precondiciones de mayor valor crítico dando por satisfechas las demás. Si hay problemas, volvemos al nivel anterior para buscar otro plan. \end_layout \end_body \end_document