SSII tema 6

1 files changed, 620 insertions, 0 deletions

diff --git a/si/n6.lyx b/si/n6.lyx
new file mode 100644
index 0000000..b4b3e21
--- /dev/null
+++ b/si/n6.lyx
@@ -0,0 +1,620 @@
+#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é necesita la regla que se cumpla para poder ejecutable, 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 aparecen en el subconjunt
+o unificado.
+ 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
+
+, 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
+uEnOtroCaso{
+\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 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 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