Agentes de búsqueda online y ambientes desconocidos

Agentes de búsqueda online y ambientes desconocidos.

Hasta ahora nos hemos centrado en agentes que usan algoritmos de búsqueda M ine Ellos calculan una solución completa antes de poner un pie en el mundo real, y luego ejecutan la solución sin recurrir a su percepciones. En contraste, un agente de búsqueda ai línea (onünt$ A funciona nto-calando el cálculo y la acción: primero toma una acción, entonces observa el entorno y calcula la siguiente acción. La búsqueda online es una buena idea en dominios dinámicos o semidinámicos (dominios donde hay una penalización por holgazanear y por utilizar demasiado tiempo para cal­ cular). La búsqueda online es una idea incluso mejor para dominios estocásticos. En ge­ neral, una búsqueda offline debería presentar un plan de contingencia exponencialmente grande que considere todos los acontecimientos posibles, mientras que una búsqueda on- line necesita sólo considerar lo que realmente pasa. Por ejemplo, a un agente que juega al ajedrez se le aconseja que haga su primer movimiento mucho antes de que se haya resuelto el curso completo del juego.

Problemas de búsqueda en línea (online) Un problema de búsqueda online puede resolverse solamente por un agente que ejecute acciones, más que por un proceso puramente computacional. Asumiremos que el agen­te sabe lo siguiente:

• Acciones (s), que devuelve una lista de acciones permitidas en el estado s,

• Funciones de coste individual c(s, a, d) (notar que no puede usarse hasta que el agente sepa que y es el        resultado); y

• Test-Objetivo (y.

Agentes de búsqueda en línea (online).

Después de cada acción, un agente online recibe una percepción al decirle que estado ha alcanzado; de esta información, puede aumentar su mapa del entorno. El mapa ac­ tual se usa para decidir dónde ir después. Esta intercalación de planificación y acción significa que los algoritmos de búsqueda online son bastante diferentes de los algorit­ mos de búsqueda offline vistos anteriormente. Por ejemplo, los algoritmos offline como A* tienen la capacidad de expandir un nodo en una parte del espacio y luego inmedia­ tamente expandir un nodo en otra parte del espacio, porque la expansión de un nodo im­ plica simulación más que verdaderas acciones. Un algoritmo online, por otra parte, puede expandir sólo el nodo que ocupa físicamente. Para evitar viajar a través de todo el árbol para expandir el siguiente nodo, parece mejor expandir los nodos en un orden local. La búsqueda primero en profundidad tiene exactamente esta propiedad, porque (menos cuando volvemos hacia atrás) el siguiente nodo a expandir es un hijo del nodo anteriormente expandido. En la Figura 4.20 se muestra un agente de búsqueda primero en profundidad onli­ ne. Este agente almacena su mapa en una tabla, resultado[a,d[, que registra el estado que resulta de ejecutar la acción a en el estado s. Siempre que una acción del estado actual no haya sido explorada, el agente intenta esa acción. La dificultad viene cuando el agen­ te ha intentado todas las acciones en un estado. En la búsqueda primero en profundidad offline, el estado es simplemente quitado de la cola; en una búsqueda online, el agente tiene que volver atrás físicamente. La búsqueda primero en profundidad, significa vol­ ver al estado el cual el agente incorporó el estado actual más recientemente. Esto se consigue guardando una tabla que pone en una lista, para cada estado, los estados predece­ sores a los cuales aún no ha vuelto. Si el agente se ha quedado sin estados a los que vol­ ver, entonces su búsqueda se ha completado. Recomendamos al lector que compruebe el progreso del Agente-BPP-Online cuando se aplica al laberinto de la Figura 4.18. Es bastante fácil ver que el agente, en el caso peor, terminará por cruzar cada enlace en el espacio de estados exactamente dos veces. Por exploración, esto es lo óptimo; para encontrar un objetivo, por otra parte, la proporción competitiva del agente podría ser arbitrariamente mala si se viaja sobre un camino largo cuando hay un objetivo directamente al lado del estado inicial. Una va­ riante online de la profundidad iterativa resuelve este problema; para un entorno re­ presentado por un árbol uniforme, la proporción competitiva del agente es una constante pequeña. A causa de su método de vuelta atrás, el Agente-BPP-Online trabaja sólo en espa­ cios de estados donde las acciones son reversibles. Hay algoritmos ligeramente más com­ plejos que trabajan en espacios de estados generales, pero ninguno de estos algoritmos tiene una proporción competitiva acotada.

Búsqueda local en línea (online).

Como la búsqueda primero en profundidad, la búsqueda de asconitin de colmas tie­ ne la propiedad de localidad en sus expansiones de los nodos. £De hecho, porque man­ tiene un estado actual en memoria, la búsqueda de ascensión de colinas es ya un algoritmo de búsqueda on/inel Desafortunadamente, no es muy útil en su forma más simple por­ que deja al agente que se sitúe en máximos locales con ningún movimiento que hacer. Por otra parte, los reinicios aleatorios no pueden utilizarse, porque el agente no puede moverse a un nuevo estado. cam ino aleatorio En vez de reinicios aleatorios, podemos considerar el uso de un carino aleatorio para explorar el entorno. Un camino aleatorio selecciona simplemente al azar una de las acciones disponibles del estado actual; se puede dar preferencia a las acciones que to­ davía no se han intentado. Es fácil probar que un camino aleatorio encontrará al final un objetivo o termina su exploración, a condición de que el espacio sea finito15. Por otra parte, el proceso puede ser muy lento. La Figura 4.21 muestra un entorno en el que un camino aleatorio utilizará un número exponencial de pasos para encontrar el objetivo, porque, en cada paso, el progreso hacia atrás es dos veces más probable que el progre­ so hacia delante. El ejemplo es artificial, por supuesto, pero hay muchos espacios de es­ tados del mundo real cuya topología causa estas clases de «trampas» para los caminos aleatorios. Aumentar a la ascensión de colinas con memoria más que aleatoriedad, resulta ser una aproximación más eficaz. La idea básica es almacenar una «mejor estimación ac­ tual» H(s) del coste para alcanzar el objetivo desde cada estado que se ha visitado. El comienzo de H(s) es justo la estimación heurística h(s) y se actualiza mientras que el agen­ te gana experiencia en el espacio de estados. La Figura 4.22 muestra un ejemplo senci­ llo en un espacio de estados unidimensional. En (a), el agente parece estar estancado en un mínimo local plano en el estado sombreado. Más que permanecer donde está, el agen­ te debe seguir por donde parece ser la mejor trayectoria al objetivo, basada en las esti­ maciones de los costes actuales para sus vecinos. El coste estimado para alcanzar el objetivo a través de un vecino y es el coste para conseguir s1 más el coste estimado para conseguir un objetivo desde ahí, es decir, c(s, a, y) + H{st). En el ejemplo, hay dos ac­ ciones con costos estimados 1 + 9 y 1 + 2, así parece que lo mejor posible es mover­ se a la derecha. Ahora, está claro que la estimación del costo de dos para el estado sombreado fue demasiado optimista. Puesto que el mejor movimiento costó uno y con­ dujo a un estado que está al menos a dos pasos de un objetivo, el estado sombreado debe estar por lo menos a tres pasos de un objetivo, así que su H debe actualizarse adecua­ damente, como se muestra en la figura 4.22(b). Continuando este proceso, el agente se moverá hacia delante y hacia atrás dos veces más, actualizando Hcada vez y «apartan­ do» el mínimo local hasta que se escapa a la derecha.