%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2345678901234567890123456789012345678901234567890123456789012345678901234567890
% 1 2 3 4 5 6 7 8
\documentclass[letterpaper, 10 pt, conference]{ieeeconf} % Comment this line out
% if you need a4paper
%\documentclass[a4paper, 10pt, conference]{ieeeconf} % Use this line for a4
% paper
\IEEEoverridecommandlockouts % This command is only
% needed if you want to
% use the \thanks command
\overrideIEEEmargins
\usepackage{graphicx}
% See the \addtolength command later in the file to balance the column lengths
% on the last page of the document
% The following packages can be found on http:\\www.ctan.org
%\usepackage{graphics} % for pdf, bitmapped graphics files
%\usepackage{epsfig} % for postscript graphics files
%\usepackage{mathptmx} % assumes new font selection scheme installed
%\usepackage{times} % assumes new font selection scheme installed
%\usepackage{amsmath} % assumes amsmath package installed
%\usepackage{amssymb} % assumes amsmath package installed
\title{\LARGE \bf
EL LABERINTO EN LA METODOLOGIA DE LA DIFERENCIA TEMPORAL$^{1}$
Carrera de Ingeniera en Sistemas Computacionales$^{2}$
Universidad De Guayaquil$^{3}$
}
%\author{ \parbox{3 in}{\centering Huibert Kwakernaak*
% \thanks{*Use the $\backslash$thanks command to put information here}\\
% Faculty of Electrical Engineering, Mathematics and Computer Science\\
% University of Twente\\
% 7500 AE Enschede, The Netherlands\\
% {\tt\small h.kwakernaak@autsubmit.com}}
% \hspace*{ 0.5 in}
% \parbox{3 in}{ \centering Pradeep Misra**
% \thanks{**The footnote marks may be inserted manually}\\
% Department of Electrical Engineering \\
% Wright State University\\
% Dayton, OH 45435, USA\\
% {\tt\small pmisra@cs.wright.edu}}
%}
\author{Martillo Rosales$^{1}$ , Grcia Carmen$^{2}$ and Pesantez Daniela$^{3}$% <-this % stops a space
\thanks{Este trabajo es realizado bajo los estandares Aprendizaje Reforzado del lenguaje netbeans basado al juego de laberinto con la metodologia difernecial temporal}% <-this % stops a space
}
\begin{document}
\maketitle
\thispagestyle{empty}
\pagestyle{empty}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
La solucion a un problema dado consiste en encontrar un camino desde un nodo representando el estado inicial, hasta el estado final deseado.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{INTRODUCCION}
La siguiente memoria pretende aclarar y exponer el trabajo llevado a cabo para la realización de un estudio relacionado en el contexto de la Inteligencia Artificial, este estudio se llevará a cabo mediante el uso del famoso juego "Comecocos", de ahí su nombre "Comecocos vs Laberintos con técnicas de búsqueda". Para ello, se intentará explicar con la mayor claridad y brevedad posible el trabajo llevado a cabo en el periodo de realización del mismo.
En este contexto, se describirán los métodos de búsqueda utilizados, tanto informados como no informados, siendo esta última una metodología que realiza un recorrido en el espacio de búsqueda de una forma sistemática, pero sin tener en cuenta ningún tipo de información sobre el dominio del problema que se está resolviendo.
\section{Trabajos Relacionados}
\subsection{Algoritmos de Backtracking}
El backtracking o vuelta atrás es una técnica algorítmica de resolución general de problemas mediante una búsqueda sistemática de soluciones.
Se descompone la tarea a realizar en tareas parciales y se prueba sistemáticamente cada una de estas, que a su vez se descompondrán en subtareas.
Cuando al elegir una tarea se comprueba que no lleva a una solución, se debe volver atrás, y probar con otra
\subsection{Utilizar recursividad}
En general, las soluciones recursivas son menos eficientes que las iterativas (coste mayor en tiempo y memoria).
Consejos:
Los algoritmos que por naturaleza son recursivos y donde la solución iterativa es complicada y debe manejarse explícitamente una pila para emular las llamadas recursivas, deben resolverse por métodos recursivos.
Cuando haya una solución obvia al problema por iteración, debe evitarse la recursividad
\section{DATOS}
lienzo1.hilo.start(); jButton1.setEnabled(false); jMenuItem1.setEnabled(false); lienzo1.f=2; hilo.start();
\subsection{Explicacion de La Variable}La función load permite incorporar gráficos a partir de archivos BMP, PNG, JPEG etc load genera un objeto Surface que
representará a la imagen en la memoria del equipo el retorno de setmode también es una superficie, pero esta representa lo que veremos en pantalla. Se utiliza (generalmente) para dibujar en pantalla. blit recibe la superficie a imprimir y su posición. La posición consiste en una coordenada (x, y).
Los juegos generalmente utilizan un bucle de repetición (llamado main loop).Ejecuta pequeñas operaciones muy rápidamente. Agrupa todo lo relacionado con el personaje, atributos, comportamiento. El método “update” contiene el comportamiento del personaje.
\subsection{Breve descripción de la estructura de la memoria} A continuación se detalla la estructura que seguirá la presente memoria, para facilitar en la medida de lo posible su comprensión.
Basándonos en que el objetivo de este estudio consiste en la resolución de tres problemas usando en cada uno un tipo de algoritmo en concreto, la explicación de cada uno de estos se dividirá en tres bloques. Y a su vez, en cada uno de estos, se detallan las siguientes secciones:
· Objetivo: Se comenta brevemente los que se quiere conseguir, y cuál es el algoritmo a desarrollar.
· Solución al problema propuesto: Es decir, cómo ha sido resuelto el problema desde un punto de vista conceptual y sin entrar en detalles de implementación.
· Ventajas e inconvenientes detectados: Antes y después del proceso de implementación.
· Pseudocódigo: Detalles sobre la implementación del algoritmo.
· Pruebas y resultados: Testeo del funcionamiento del algoritmo con el mayor detalle posible.
Además, en la descripción de los algoritmos se pretenderá utilizar una notación y un nivel de detalle que faciliten la comprensión de los mismos.
\subsection{Explicacion de La Variable}La tarea es encontrar la ruta mas corta entre una ciudad inicial s y una ciudad meta t. Los c´ırculos son estados a visitar: Las flechas representan sucesores.Las etiquetas en las flechas son distancias. Los cuadros son distancias lineales a la meta.
\section{Metodologia}
A groso modo el algoritmo implementado se divide en tres funciones: chooseMove, CapturaMovimiento y BusquedaProfundidad. Siendo esta última donde se desarrolla verdaderamente la búsqueda en profundidad.
La Función chooseMove, es la encargada de pasar el movimiento que tiene que realizar el pacman al programa general, en esta inicialmente se procede a guardar el estado actual del pacman, se inicializan las estructuras de datos usadas para almacenar los nodos visitados y para almacenar los movimientos y se llama a la función BusquedaProfundidad.
La función CapturaMovimiento, es usada dentro de la función BusquedaProfundidad para transformar todos los estados por los que ha pasado pacman para llegar el objetivo, a los movimientos necesarios para llegar a este. A continuación se presenta el pseudocódigo de esta función:
La función recibe como argumentos 2 estados, el origen y donde queremos ir.
CapturaMovimiento( Estado sOrigen, Estado sFinal){
Creamos lista à legalMoves, con los movimientos legales de sOrigen.
Generamos un estado auxiliar à sAux, vacío;
Para ( todos los legalMoves ) hacer
Asignamos a sAux, el movimiento legalMove, actual.
Si ( El estado sAux, es igual a sFinal, con el legalMove actual)
Retornamos ese legalMove;
Finpara
// No se puede acceder al estado sFinal,con ningún movimiento
Retornamos null;
}
Por último, se procede a comentar la función BusquedaProfundidad. Como se ha comentado anteriormente esta es una función recursiva, que recibe como argumento un Estado y el número de puntos que hay actualmente en el tablero. Este segundo argumento ayudará a descubrir si en el estado actual pacman llega al objetivo, es decir, se ha comido un punto.
En esta situación, se retornará una lista con todos los estados que han llevado al objetivo, y se devolverá el control a la función chooseMove.
La primera vez que se llama a la función el estado actual será el correspondiente a la situación inicial del juego y el número de dots será 0. El pseudocódigo será el siguiente:
ArrayList de estados: BusquedaProfundidad ( State sActual, int NumeroDots){
Si ( el estado actual sActual es objetivo) entonces
Capturamos el historial de estados hasta esta situación.
Retornamos la lista con los estados.
Sino
Si ( La posición de sActual no ha sido visitada )
Se guarda en la estructura de datos de visitados.
legalMoves = Capturamos los movimientos legales de sActual.
Para ( Todos los legalMoves ) hacer
sNext = estado siguiente con el movimiento actual.
Si ( sNext no ha sido visitado, y no es el padre del estado actual sState ) entonces
ListaEstados (lista de estados a el Objetivo) = BusquedaProfundidad(sNext, Número de dots con sActual);
Si (ListaEstados no es vacia ) entonces
Comprobamos si el número de estados que tiene es mejor, que el camino encontrado anteriormente. Y si es mejor, seleccionamos esta.
Finsi
Finsi
Finpara
Finsi
Si llegamos hasta este punto, no existe ningún camino al objetivo, desde el hijo actual.
Entonces retornamos null;
}
\subsection{Formalmente, un MDP}
Es una tupla M =< S,A, Φ, R > formada por: Un conjunto finito de estados S({1, ..., n}). Un conjunto finito de acciones A, que pueden depender de cada estado: Una función de recompensa ( R), que define la meta y mapea cada estado–acción a un número ´ (recompensa), indicando lo deseable del estado; Un modelo del ambiente o función de transición de estados Φ : A × S → S que nos dice la probabilidad de alcanzar el estado s ′ ∈ S al realizar la acción a ∈ A en el estado s ∈ S, que se puede denotar como Φ(s ′ |s, a).
Utilizan la experiencia para encontrar la función de valor.
Calcula una política pseudo–óptima.
Se basan en la actualización por el nuevo estado:
\begin{figure}[bh]
\centerline{\includegraphics[width=5cm]{MDP.png}} % si es otro formato , sin extension
\vspace*{8pt}
\caption{A schematic illustration of dissociative recombination. The
direct mechanism, 4m$^2_\pi$ is initiated when the
molecular ion S$_{\rm L}$ captures an electron with kinetic energy.}
\end{figure}
$$
s’ V(s) ← V(s) + α[r + γV(s’)-V(s)] ← s’
$$
\subsection{Elementos Adicionales }
\begin{itemize}
\item Política (π): define como se comporta el sistema en cierto tiempo. Es un mapeo (a veces estocástico) de los ´ estados a las acciones.
\item Función de valor ( V): indica lo que es bueno a largo plazo. Es la recompensa total que un agente puede esperar acumular empezando en un estado s (V(s)) o en un estado haciendo una acción a (Q(s, a)) • Las recompensas están dadas por el ambiente, pero ´ los valores se deben de estimar (aprender) en base a las observaciones. Aprendizaje por refuerzo aprende las funciones de valor mientras interactúa con el ambiente.
\item La aproximación lineal de la función no es la única opción. Más recientemente, los métodos basados en las ideas de estadística no paramétrica se han explorado (qu e se pueden ver para construir sus propias características).
\item Método SARSA $$ Q(st, at) = Q(st, at) + α rt+1 + γQ(st+1, at+1) − Q(st, at) A $$
\end{itemize}
\section{Resultados}
Al intentar resolver este tipo de problemas, es necesario establecer una serie de pautas que ayudarán a determinar un orden en su resolución. Para ello, se establecerán una serie de simplificaciones, desde un punto de vista conceptual, que serán útiles para dejar las ideas un poco más claras, dejando así, de forma transitoria de lado la parte de implementación del algoritmo, para centrarnos exclusivamente en la idea de resolución del problema.
En primer lugar, consideraremos en principio que el espacio de búsqueda es un grafo, lo que simplifica bastante las operaciones, ya que de este modo será posible generar un algoritmo que no recaiga en bucles infinitos, permitiendo así la posibilidad de ir almacenando los nodos visitados y cerrados para no repetir caminos, cosa que no se puede realizar usando búsqueda en árboles.
Para simular este grafo, se decide usar una función recursiva, de tal manera que se establece como nodo raíz la posición en la que se encuentra el pacman a la hora de realizar una nueva búsqueda, y tras comprobar si este es objetivo se expande generando los hijos a los que puede acceder. En el siguiente ejemplo se detalla gráficamente, siendo el nodo (1,0) el nodo raíz, y los nodos (1,1) y (1,2) los hijos de este. (Ver Figuras 1 y 2).
En este punto, es correcto mencionar que se realizará una nueva búsqueda cada vez que el pacman pretende comerse un nuevo punto. Así conseguimos reducir considerablemente el coste computacional necesario para realizar una búsqueda de estas características, ya que se alcanzarán profundidades más manejables.
Con todo lo anterior, es fácil comprender que dentro de la función recursiva, primero se comprobará si el estado actual es objetivo, y posteriormente se comprueba si existe alguna rama hija que permita alcanzar el objetivo establecido.
Para realizar la comprobación anterior, se selecciona el primer hijo que se encuentra y se llama a la función recursiva pasándole este como argumento. En cada llamada a esta función, se realiza un cambio de contexto en el estado del algoritmo, es decir, el nodo que antes era hijo, pasa a ser un nodo raíz, para posteriormente poder expandir sus hijos y seguir con la búsqueda.
Con esta transformación se consigue ir recorriendo paso a paso todos los nodos del grafo basándonos en los “estados virtuales[1]”, para así estudiar el camino a seguir de la forma más sencilla posible. Una vez encontrado el objetivo, se transforman los estados por los que se ha ido pasando, en los movimientos que tiene que realizar pacman para llegar.
Si por esta rama no se encuentra el objetivo, se retornará false, y se realizará la misma comprobación con todos los hijos. Así, se tiene conciencia de que estamos usando un algoritmo en profundidad.
Para que la realización del algoritmo sea posible, es necesario utilizar una serie de estructuras de datos. En concreto, se utiliza una lista para almacenar los nodos visitados, y una pila donde se almacenará los movimientos que tiene que realizar pacman hasta llegar al objetivo.
Además, y como extra al algoritmo, cada vez que se retorna un camino válido hasta el objetivo, se comprueba que tenga el menor número de pasos posibles. Con esto se tiene la certeza de que el camino encontrado en cada búsqueda será óptimo.
section{iLUSTRACION DEL PROGRAMA}
Como ya se ha comentado anteriormente, una de las ventajas de usar un algoritmo de búsqueda en profundidad basado en grafos, es que se pueden almacenar los nodos visitados para no recaer en bucles infinitos.
Al principio del desarrollo de la práctica, en vez de usar este tipo de estructuras de datos, pensé en resolver el problema mediante árboles, pero tras analizar el problema en profundidad y realizar algunas pruebas de implementación, pude observar que el pacman realizaba muchos movimientos absurdos y en ocasiones incluso no pasaba del primer nivel.
\begin{figure}[bh]
\centerline{\includegraphics[width=5cm]{laberinto.png}} % si es otro formato , sin extension
\vspace*{8pt}
\caption{A schematic illustration of dissociative recombination. The
direct mechanism, 4m$^2_\pi$ is initiated when the
molecular ion S$_{\rm L}$ captures an electron with kinetic energy.}
\end{figure}
Se observa además que el algoritmo consume mucho coste computacional, sobre todo en niveles elevados, ya que como los puntos están más separados, es necesario expandir más nodos y la profundidad de la búsqueda se hace realmente compleja.
\subsection{Corridas iniciales}
\begin{itemize}
\item Se llama a expandir $$r([], l(s, 0/0), 9999,, si, Solucion)$$
\item La primer llamada no satisface meta(Nodo).
\item El primer caso es expandir la hoja$$ l(s, 0/0). $$
\item La primera parte del trabajo, lo hace bagof /3 que computa los sucesores de s con sus distancias asociadas$$ Succ/[a/2, e/2].$$
\item El predicado listaSuccs/3 construye la lista de posibles ´arboles
sucesores $$As/[l(a, 7/2), l(e, 9/2)].$$
\item Con esa lista mejor $$ rF/2 $$ encuentra que el mejor $$ r F1/7 y $$
\item Se llama recursivamente a expandir con el ´arbol expandido a $$ t(s, 7/0, [l(a, 7/2), l(e, 9/2)]).$$ El resto no ha cambiado.
\end{itemize}
\subsection{Contiunaci´on de la corrida}
\begin{itemize}
\item La tercer llamada es expandir $$([],t(s, 7/0, [l(a, 7/2), l(e, 9/2)]), 9999,, si, Solucion).$$
\item Como $$ F/9 9999 $$ la evaluaci´on continua en el tercer caso.
\item Se actualiza el umbral con el mejor F del resto de la expansion$$ [l(a, 7/2), l(e, 9/2)] (el valor de F para a ya esta guardado en el nodo s, 7/.. $$
\item se llama recursivamente a expandir el camino recorrido aumentado con s Camino,$$ Arbol/l(a, 7/2), el Umbral1/9 $$ y el resto sigue igual.
\item continuar $$/7 $$ decide como procede la b´usqueda de acuerdo al arbol expandido. Si una soluci´on Sol se ha encontrado, se regresa este valor. En cualquier otro caso, la expansi´on continua dependiendo del valor de Solucionado (no o nunca).
\end{itemize}
\section{TABLA DE RESULTADO}
Una vez analizados los diferentes algoritmos propuesto el siguiente paso es verificar la
efectividad instalándolo en un mecanismo autónomo, para esta parte del experimento
usaremos, el lenguaje de programación
\subsection{EXPLICACION DE LA TABLA}
Basados en las necesidades de construir un software flexible, que le permita guiarse en
diferentes escenarios hasta encontrar la salida y que aprenda como encontrar el camino.
Estas necesidades se traducen en un conjunto de parámetros e índices descritos a
continuación. El sistema “Laberinto Virtual” está diseñado para crear escenarios virtuales y recorrerlos de una
forma artificial
\begin{figure}[bh]
\centerline{\includegraphics[width=5cm]{grafico3.png}} % si es otro formato , sin extension
\vspace*{8pt}
\caption{La figura nos visualizara lo que se basa en el software de las estadisticas de cuanto es su renmiento de tiempo como lo podemos apreciar en ambas graficas.}
\end{figure}
\subsection{FIGURA DE LA TABLA}
Una decoración alrededor del escenario.
● Un laberinto de ladrillo.
● Enemigos con autonomía
● y movimientos en bloque.
\begin{table}[h]
\caption{An Example of a Table}
\label{table_example}
\begin{center}
\begin{tabular}{|c||c|}
\hline
s & T\\
\hline
A & M\\
\hline
\end{tabular}
\end{center}
\end{table}
\begin{figure}[bh]
\centerline{\includegraphics[width=5cm]{tabla.png}} % si es otro formato , sin extension
\vspace*{8pt}
\caption{La figuranos representa la coneccion de los nodos mediante los resultados de la tabla asignada}
\end{figure}
\begin{figure}[thpb]
\centering
\framebox{\parbox{3in}{El tiempo efectivo es el tiempo que sistema encuentra el camino sin tomar en cuenta la búsqueda, ya que el sistema lo sigue aprovechando el camino aprendido..
}}
%\includegraphics[scale=1.0]{figurefile}
\caption{Mostraremos los resultados indicados}
\label{figurelabel}
\end{figure}
Figure Labels: Use 8 point Times New Roman for Figure labels. Use words rather than symbols or abbreviations when writing Figure axis labels to avoid confusing the reader. As an example, write the quantity ÒMagnetizationÓ, or ÒMagnetization, MÓ, not just ÒMÓ. If including units in the label, present them within parentheses. Do not label axes only with units. In the example, write ÒMagnetization (A/m)Ó or ÒMagnetization {A[m(1)]}Ó, not just ÒA/mÓ. Do not label axes with a ratio of quantities and units. For example, write ÒTemperature (K)Ó, not ÒTemperature/K.Ó
\section{CONCLUSION}
La resolución de problemas en IA requiere, normalmente, determinar una secuencia de acciones o decisiones. Esta secuencia será ejecutada posteriormente por un agente con el fin de alcanzar un objetivo a partir de una situación inicial dada. Dependiendo del problema concreto, la ejecución de la secuencia de acciones o decisiones tiene asociado un coste que se tratará de minimizar.
Con el desarrollo de esta práctica, queda más claro que no todos los métodos a utilizar para la resolución de un problema tienen el mismo coste y en consecuencia la misma complejidad. Siendo los métodos de búsqueda informados más idóneos para el tipo de problema expuesto en esta ocasión.
\addtolength{\textheight}{-12cm} % This command serves to balance the column lengths
% on the last page of the document manually. It shortens
% the textheight of the last page by a suitable amount.
% This command does not take effect until the next page
% so it should come on the page before the last. Make
% sure that you do not shorten the textheight too much.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Pruebas y Resultados}
Los datos de las pruebas se capturan al final del nivel al que llega AGENTE, aunque se realiza la búsqueda para encontrar cada punto, los datos aquí expuestos corresponderán a la suma total del último nivel completado, siendo este el más complejo computacionalmente.
\section*{AGRADECIMIENTO}
Agradezco a la informacion brindada del ingeniero y mis companeros y asi poder obtener nuevo conocimientos; a su vez tener la oportunidad de exponerlo
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
\bibitem{c1} F. H. MARTINEZ SARMIENTO, “Projection, design and construction of robotic platform for artificial intelligence research.” in Tecnura [online]., 2010.
\bibitem{c2} S. Russell, “Un enfoque moderno. pearson prentice hall,” in Segunda Edicin, May 2004.
\bibitem{c3} M. Villares Souto, “Entorno de juegos para la aplicacin de tcnicas de i.a,” in Proyecto Fin de Carrera, Facultad de Informtica de la Universidad de A Corua, 2004, pp. 145–155.
\bibitem{c4} S. D. y Eduardo Zalama Casanova, “A mobile robot with enhanced gestual abilities.”
\bibitem{c5} J. M. C. y J. M. Molina, “Introduccin a la teora de agentes y sistemas multiagente.”
\bibitem{c6} Michael L. Littman, Anthony R. Cassandra, and Leslie Pack Kaelbling. Learning policies for partially observable environments: Scaling up. In Proceedings of the Twelfth International Conference on Machine Learning, pages 362–370. Morgan Kaufmann, 1995.
\bibitem{c7} Shivaram Kalyanakrishnan, Yaxin Liu, and Peter Stone. Half field offense in robocup soccer: A multiagent reinforcement learning case study. In RoboCup 2006: Robot Soccer World Cup X, pages 72–85. Springer-Verlag, 2006.
\bibitem{c8} Alexander A.Sherstov and Peter Stone. Function approximation via tile coding: Automating parameter choice. In Lecture Notes in Computer Science: Abstraction, Reformulation and Approximation, pages 194–205. Springer Berlin / Heidelberg, 2005.
\bibitem{c9}Jing Peng and Ronald J. Williams. Incremental multi-step q-learning. In Machine Learning, pages 226–232. Morgan Kaufmann, 1994.
\bibitem{c10}R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, 1957.
\bibitem{c11}Peter Stone, Richard S. Sutton, and Gregory Kuhlmann. Reinforcement learning for robocup soccer keepaway. Adaptive Behavior, 13(3):165–188, 2005.
\end{thebibliography}
\end{document}