**SVRAI**
Búsqueda Clásica como MDPs
# Problemas de búsqueda
Los problemas de búsqueda son un caso particular de Procesos de Decisión de Markov donde las funciones de transición son deterministas, así que, en el marco que estamos viendo, un problema de búsqueda tradicional se puede modelar como encontrar una secuencia adecuada de acciones para maximizar la recompensa obtenida sobre las transiciones deterministas posteriores. Algunos problemas de búsqueda bien conocidos son los puzzles de piezas deslizantes, el cubo de Rubik, el Sokoban y la búsqueda de caminos más cortos.
En un problema de búsqueda, elegimos una acción en el momento $t$ basándonos en la observación del estado $s_t$ y recibimos una recompensa $r_t$. El espacio de acciones $A$ y el espacio de estados $S$ se definen de forma similar a la aproximación de búsquedas clásicas sobre espacios de estados. Aunque algunos algoritmos asumen que estos conjuntos (estados y acciones) son finitos, no es necesario en general. En esta aproximación, el estado evoluciona de forma determinista y sólo depende del estado actual y de la acción realizada. Denotaremos por $A(s)$ el conjunto de acciones válidas para el estado $s$. Cuando no hay acciones válidas, se considera que el estado es absorbente y produce una recompensa nula para todos los pasos de tiempo futuros. Los estados _objetivo_, por ejemplo, suelen ser absorbentes.
La función de transición de estados, en este caso, determinista, $T(s, a)$, devuelve el estado sucesor $s'$ resultante de ejecutar la acción $a$ desde el estado $s$, mientras que la función de recompensa $R(s, a)$ devuelve la recompensa recibida por ellos. A diferencia de los casos con incertidumbre, los problemas de búsqueda clásicos no suelen incluir un factor de descuento $\gamma$ que penalice las recompensas futuras. El objetivo es elegir una secuencia de acciones que maximice la suma de recompensas (lo que llamamos *rendimiento* anteriormente).
El siguiente código proporciona una estructura de datos para representar los problemas de búsqueda. Compárese con la estructura que se ha definido para representar Procesos de Decisión de Markov.
~~~~~~
struct Search
𝒮 # state space
𝒜 # valid action function
T # transition function
R # reward function
end
~~~~~~
# Grafos de búsqueda
Cuando trabajamos con un problema de búsqueda con espacios de estado y acción finitos, podemos usar una representación como **grafo** para la estructura que las acciones inducen en el espacio de estados, donde los nodos corresponden a los estados y las aristas a las transiciones entre estados (a cada arista de un estado de origen a uno de destino se le asocia una acción que da lugar a esa transición y la recompensa esperada al realizar esa acción desde el estado origen). La siguiente figura muestra un subconjunto de este grafo de búsqueda para un 8-puzzle (puzzle de fichas deslizantes de tamaño $3 \times 3$, no se indican las acciones, porque son obvias y únicas a partir de los estados que conecta):
Muchos algoritmos de búsqueda en grafos realizan una búsqueda desde un estado inicial y se abren en abanico a partir de él. Al hacerlo, estos algoritmos trazan un **árbol de búsqueda**. El estado inicial es el nodo **raíz**, y cada vez que pasamos de $s$ a $s'$ aplicando una acción durante la búsqueda, se añade una arista de $s$ y un nuevo nodo $s'$ al árbol de búsqueda. La siguiente figura muestra un árbol de búsqueda para el mismo 8-puzzle:
Los algoritmos que veremos a continuación proporcionan diversas aproximaciones al problema de realizar una búsqueda más eficiente para maximizar el rendimiento obtenido en el transcurso de ir desde un estado origen hasta un estado objetivo. Debe tenerse en cuenta que, a pesar de abordar el problema de la decisión secuencial, en general no son aplicables si estamos trabajando con acciones no deterministas.
# Búsqueda hacia Adelante
Quizás el algoritmo de búsqueda en grafos más simple es el de **búsqueda hacia adelante** (`forward_search`), que determina la mejor acción a tomar desde un estado inicial `s` mirando todas las posibles transiciones acción-estado hasta una profundidad (u horizonte) `d`. En la profundidad `d`, el algoritmo utiliza una estimación del valor del estado `U(s)` (las funciones de valor aproximadas devuelven $0$ cuando se encuentren en un estado sin acciones disponibles). El algoritmo se llama a sí mismo recursivamente en profundidad, dando como resultado un árbol de búsqueda y devolviendo una tupla con una acción óptima `a` y su valor esperado de horizonte finito `u`.
~~~~~~
function forward_search(𝒫::Search, s, d, U)
𝒜, T, R = 𝒫.𝒜(s), 𝒫.T, 𝒫.R
if isempty(𝒜) || d ≤ 0
return (a=nothing, u=U(s))
end
best = (a=nothing, u=-Inf)
for a in 𝒜
s′ = T(s,a)
u = R(s,a) + forward_search(𝒫, s′, d-1, U).u
if u > best.u
best = (a=a, u=u)
end
end
return best
end
~~~~~~
Evidentemente, la búsqueda en profundidad puede ser un desperdicio, ya que se visitan todos los estados alcanzables para la profundidad dada. La búsqueda hasta la profundidad `d` dará como resultado un árbol de búsqueda con $O(|A|^d)$ nodos para un problema con $|A|$ acciones. La figura siguiente muestra un ejemplo de un árbol de búsqueda obtenido al ejecutar la búsqueda hacia adelante en el 8-puzzle hasta profundidad 2: se visitan todos los estados alcanzables en dos pasos, y algunos se visitan más de una vez; hay un camino hacia el nodo terminal, con un retorno de $-1$, mientras que todos los demás caminos tienen un retorno de $-2$.
# Branch and Bound
Un método general conocido como **branch and bound** puede reducir significativamente el cálculo utilizando información sobre los límites superior e inferior de la recompensa esperada. Denotamos por $\bar{Q}(s, a)$ al límite superior de la recompensa por tomar la acción $a$ desde el estado $s$, y por $\underline{U}(s)$ al límite inferior de la utilidad del estado $s$. La búsqueda branch and bound sigue el mismo procedimiento que la búsqueda hacia adelante, pero itera sobre las acciones según su límite superior, y procede a un nodo sucesor sólo si el mejor valor posible que podría devolver es mayor que el que ya se ha descubierto siguiendo una acción anterior.
~~~~~~
function branch_and_bound(𝒫::Search, s, d, Ulo, Qhi)
𝒜, T, R = 𝒫.𝒜(s), 𝒫.T, 𝒫.R
if isempty(𝒜) || d ≤ 0
return (a=nothing, u=Ulo(s))
end
best = (a=nothing, u=-Inf)
for a in sort(𝒜, by=a->Qhi(s,a), rev=true)
if Qhi(s,a) ≤ best.u
return best
end
u = R(s,a) + branch_and_bound(𝒫, T(s,a), d-1, Ulo, Qhi).u
if u > best.u
best = (a=a, u=u)
end
end
return best
end
~~~~~~
En el algoritmo anterior, la búsqueda se realiza hasta la profundidad `d` con una función de valor de límite inferior `Ulo` ($\underline{U}$) y una función de valor de acción de límite superior `Qhi` ($\bar{Q}$). La tupla con nombre devuelta consiste en la mejor acción `a` y su valor esperado de horizonte finito `u`.
No se garantiza que BB reduzca el cálculo con respecto a la búsqueda hacia adelante, ya que ambos enfoques tienen la misma complejidad temporal en el peor de los casos. La eficiencia del algoritmo depende en gran medida de la heurística.
# Programación Dinámica
Ninguno de los dos algoritmos anteriores recuerdan si un estado ha sido visitado previamente, por lo que gastan recursos computacionales al evaluar algunos estados múltiples veces. La **programación dinámica** evita la duplicación de esfuerzos al recordar cuándo se ha resuelto previamente un subproblema concreto, y por ello puede aplicarse a problemas en los que una solución óptima puede construirse a partir de soluciones óptimas de sus subproblemas, una propiedad denominada **subestructura óptima**. Por ejemplo, si la secuencia óptima de acciones de $s_1$ a $s_3$ pasa por $s_2$, entonces los subcaminos de $s_1$ a $s_2$ y de $s_2$ a $s_3$ también son óptimos.
Esta subestructura se muestra en la siguiente figura, donde la secuencia de estados de la izquierda forma un camino óptimo desde el estado inicial hasta el estado terminal. Los problemas de camino más corto tienen una subestructura óptima, lo que significa que la secuencia del estado inicial al estado intermedio también es óptima, al igual que la secuencia del estado intermedio al estado terminal.
El algoritmo incluye un diccionario, `M`, que, a modo de *memoria*, almacena tuplas de estado y profundidad de evaluaciones anteriores, lo que permite al método devolver resultados calculados previamente. La búsqueda se realiza hasta la profundidad `d`, momento en el que se estima el valor terminal con una función de valor aproximado `U`. La tupla con nombre devuelta consiste en la mejor acción `a` y su valor esperado de horizonte finito `u`.
~~~~~~
function dynamic_programming(𝒫::Search, s, d, U, M=Dict())
if haskey(M, (d,s))
return M[(d,s)]
end
𝒜, T, R = 𝒫.𝒜(s), 𝒫.T, 𝒫.R
if isempty(𝒜) || d ≤ 0
best = (a=nothing, u=U(s))
else
best = (a=first(𝒜), u=-Inf)
for a in 𝒜
s′ = T(s,a)
u = R(s,a) + dynamic_programming(𝒫, s′, d-1, U, M).u
if u > best.u
best = (a=a, u=u)
end
end
end
M[(d,s)] = best
return best
end
~~~~~~
En el caso de la búsqueda de grafos, cuando se evalúa un estado, se comprueba primero el diccionario para ver si el estado ha sido visitado previamente y, si es así, se devuelve su valor almacenado (el almacenamiento en caché de los resultados de cálculos costosos para poder recuperarlos en lugar de volver a calcularlos en el futuro se denomina **memorización**). En caso contrario, evaluamos el estado de forma normal y almacenamos el resultado en el diccionario.
# Búsqueda heurística
La **búsqueda heurística** (también conocida como **búsqueda informada**) mejora BB ordenando sus acciones en base a una función heurística proporcionada, $\bar{U}(s)$, que es un límite superior del retorno. Al igual que la programación dinámica, la búsqueda heurística cuenta con un mecanismo que permite almacenar en caché las evaluaciones de estados ya visitados para evitar el cálculo redundante. Además, la búsqueda heurística no requiere la función de valor de cota inferior que necesita BB (la implementación que se muestra a continuación utiliza dos funciones de valor: la heurística para guiar la búsqueda y una función de valor aproximada para evaluar los estados terminales).
~~~~~~
function heuristic_search(𝒫::Search, s, d, Uhi, U, M)
if haskey(M, (d,s))
return M[(d,s)]
end
𝒜, T, R = 𝒫.𝒜(s), 𝒫.T, 𝒫.R
if isempty(𝒜) || d ≤ 0
best = (a=nothing, u=U(s))
else
best = (a=first(𝒜), u=-Inf)
for a in sort(𝒜, by=a->R(s,a) + Uhi(T(s,a)), rev=true)
if R(s,a) + Uhi(T(s,a)) ≤ best.u
break
end
s′ = T(s,a)
u = R(s,a) + heuristic_search(𝒫, s′, d-1, Uhi, U, M).u
if u > best.u
best = (a=a, u=u)
end
end
end
M[(d,s)] = best
return best
end
~~~~~~
En el algoritmo mostrado se parte del estado, `s`, y se busca hasta una profundidad máxima, `d`. Además, utiliza una heurística, `Uhi`, para guiar la búsqueda, la función de valor aproximado, `U`, para evaluar los estados terminales, y un diccionario, `M`, que contiene tuplas de estados y profundidad para almacenar en caché los valores de los estados previamente explorados.
Las acciones se clasifican en función de la recompensa inmediata más una estimación heurística del rendimiento futuro:
$$R(s, a) + U(T(s, a))$$
Para garantizar la optimalidad, la heurística debe ser **admisible** y **consistente**: una heurística es admisible si está acotada inferiormente por la verdadera función de valor, y es consistente si nunca es menor que la recompensa esperada al pasar a un estado vecino, es decir, si $U(s) \geq R(s, a) + U(T(s, a))$.