Dialnet-TecnicasDeInteligenciaArtificialParaLaSolucionDeLa-4742651.pdf

8/11/2019 Dialnet-TecnicasDeInteligenciaArtificialParaLaSolucionDeLa-4742651.pdf

1/6

Scientia et Technica Ao XIV, No 39, Septiembre de 2008. Universidad Tecnolgica de Pereira. ISSN 0122-1701 135

Fecha de Recepcin: (Letra Times New Roman de 8 puntos)Fecha de Aceptacin: Dejar en blanco

TCNICAS DE INTELIGENCIA ARTIFICIAL PARA LA SOLUCIN DE LABERINTOS DEESTRUCTURA DESCONOCIDA.

New Artificial intelligence techniques for solution of labyrinths with unknown structure

RESUMENDebido a que la bsqueda es el ncleo de muchos procesos inteligentes, esnecesario escoger la estructura de control apropiada con el fin de que el procesode bsqueda sea eficiente. La inteligencia artificial proporciona varias tcnicasde bsqueda que tienen una formulacin matemtica, la cual hace posible suimplementacin computacional bajo el esquema de programacin estructurada.En este trabajo se presentan las tcnicas de bsqueda en amplitud y en

profundidad, las cuales son tcnicas de inteligencia artificial, para la solucin deun problema de gran complejidad matemtica como lo es la solucin de unlaberinto de estructura desconocida.

PALABRAS CLAVES: Bsqueda en espacios desconocidos, laberitos, tcnicasde inteligencia artificial.

ABSTRACTBecause of the search process is a central problem in many intelligent processes,

it is necessary to choose the appropriate control structure in order that the

search process will be efficient. The artificial intelligence provides some search

techniques which have a mathematical formulation, in which is possible thecomputational implementation, under the structured programming. This paper

presents the techniques of amplitude and depth search, which are artificial

intelligence techniques, to solve a problem with high mathematical complexity

which is the solution of a labyrinth of unknown structure.

KEYWORDS:Artificial intelligence techniques, labyrinth, search in unknownspaces.

JASON MOLINA VARGASIngeniero Electricista, M. Sc (c).AnalistaXm los expertos en [email protected]

CARLOS TORRES PINZNIngeniero Electricista, M. Sc (c).Jefe seccin proyectos dpto. E&AIngenio la Cabaa S.A.

[email protected]

CARLOS RESTREPO PATIOIngeniero Electricista, M. Sc.Ph. D.(c) en Ingeniera Electrnica.Universidad Rovira I [email protected]

Grupo de investigacin de electrnicade potencia

Universidad Tecnolgica de Pereira

1. INTRODUCCIN

Un laberinto es un lugar formado por calles yencrucijadas, intencionalmente complejo para confundir aquien se adentre en l. El hombre desde la antigedad seha preocupado por disear intrincados laberintos y almismo tiempo por buscar formas para recorrerlos sinextraviarse. Un ejemplo muy claro de esto lo proporcionala mitologa griega en la cual se describe cmo Ddaloconstruy un laberinto muy complicado para el rey

Minos en el cual esconda este un minotauro y el cual fuehallado por Teseo. En la actualidad el inters por loslaberintos ha despertado nuevamente y esto se debe a la

bsqueda del hombre por disear robots que realicenactividades de forma ms inteligente.

Para solucionar un laberinto de estructura conocida sepueden emplear muchos mtodos como llenar loscaminos sin salida, este es un algoritmo simple, muyrpido y que no requiere mucha memoria. Otro mtodode solucin muy conocido es el de recorrer la pared ycada vez que hay un cruce se gira a la derecha, estealgoritmo es muy empleado por los robots que solucionan

laberintos debido a su simple implementacin. Otros

mtodos menos empleados son los de rehacer caminos,eliminar colisiones y moverse al azar [1]. Dado que lasolucin de un laberinto de estructura desconocida es un

problema muy complejo se emplean tcnicas deinteligencia artificial para la bsqueda de la solucin. Eneste artculo se hace una descripcin general sobre lainteligencia artificial centrndose en un sistema de

produccin para describir las estrategias de controlempleadas para la solucin de laberintos. Finalmente se

presenta en los resultados una comparacin en tiempo de

solucin entre las tcnicas empleadas para diferenteslaberintos.

2. DEFINICIN DEL PROBLEMA

El problema que se quiere abordar en este artculo es lasolucin de un laberinto de estructura desconocida. A

pesar de que es previsible que la mayora de la gentenicamente con esta sentencia acte correctamente, ladefinicin del problema tal y como est, es incompleta.Para construir un programa que solucione laberintos,

primero se debe especificar la posicin inicial en el


2/6

Scientia et Technica Ao XIV, No 39, Septiembre de 2008. Universidad Tecnolgica de Pereira.136

laberinto, las reglas que definen los movimientos legalesy la posicin en el laberinto que representa la solucin[2,3]. Adems, se debe especificar previamente elobjetivo implcito de no realizar movimientos legalesdentro del laberinto, sino solucionar el laberinto, si es

posible. Es bastante fcil dar una descripcin formal ycompleta del problema; en la posicin inicial, el mvil seencuentra inmerso en una matriz lgica de tamaodesconocido en la cual se representa una pared por ununo y un camino por un cero. El mvil ser capaz delevantar un mapa de su entorno y agregar componentes ala matriz inicial slo en posiciones verticales uhorizontales a medida que explora el laberinto y de estaforma va aumentando el tamao de la matriz lgica [4].El mvil slo se podr mover a una posicin de la matrizsi la posicin a la que quiere llegar tiene un cero,mediante estos movimientos legales se puede llegar a lasolucin del laberinto partiendo de la posicin inicial.

Se ha definido el problema de solucionar laberintos comoun problema de movimientos a travs de un espacio deestados, donde cada estado corresponde a un movimientolegal dentro del laberinto [5]. La representacin comoespacio de estados forma la base de la mayora de losmtodos de inteligencia artificial (IA), y su estructuracorresponde con aquella de resolver problemas por dosimportantes razones: Permite definir formalmente el problema, mediante la

necesidad de convertir alguna situacin dada en lasituacin deseada usando un conjunto de operaciones

permitidas.

Permite definir el proceso de resolver un problemacomo una combinacin de tcnicas conocidas,representadas por una regla que define un movimientoen el espacio de bsqueda. La tcnica general deexploracin en el espacio intenta encontrar algunaruta desde el estado actual hasta un estado objetivo.La bsqueda es un proceso de gran importancia en laresolucin de problemas difciles para los que no sedispone de tcnicas ms directas.

El problema puede resolverse con el uso de las reglas encombinacin con una estrategia apropiada de control paratrasladarse a travs del espacio problema hasta encontrar

una ruta desde un estado inicial hasta un estado objetivo[6]. De esta forma, el proceso de bsqueda esfundamental en la solucin de problemas. La bsqueda esun mecanismo general que puede utilizarse cuando no seconoce otro mtodo ms directo [7,8]. Si la estructura dellaberinto se conoce de antemano, se podran empleartcnicas heursticas para solucionar el laberintooptimizando el recorrido, pero debido a que el laberintoes desconocido no se puede plantear una funcin objetivo

para optimizar y es por esto que se debe emplear unmtodo de bsqueda.

3. TCNICAS DE INTELIGENCIA ARTIFICIAL

Una tcnica de IA es un mtodo que utiliza conocimientoexpresado, de tal forma que represente las

generalizaciones, que sea comprendido por las personasque lo proporcionan, que pueda modificarse fcilmente

para corregir errores y reflejar los cambios en el mundo yen nuestra visin del mundo, que pueda usarse en grancantidad de situaciones aun cuando no sea totalmente

preciso o completo y que pueda usarse para ayudar asuperar su propio volumen, ayudando a acotar el rango de

posibilidades que normalmente deben ser consideradas[9,10].

Aunque las tcnicas de IA deben disearse de acuerdocon las restricciones impuestas por los problemas de IA,existe cierto grado de independencia entre los problemas

y las tcnicas para su solucin. Los programas quesolucionan problemas de IA ponen en manifiesto tresimportantes tcnicas que son: la bsqueda, el uso delconocimiento y la abstraccin [1,8]. La bsqueda

proporciona una forma de resolver problemas en los queno se dispone de un mtodo ms directo, el uso delconocimiento resuelve problemas complejosaprovechando las estructuras de los objetos involucradosy la abstraccin proporciona una forma de separaraspectos y variaciones importantes de aquellos otros sinimportancia y que en caso contrario podran hacercolapsar un proceso [3].

Para solucionar problemas complejos, los programas queutilizan las tcnicas de IA presentan numerosas ventajasfrente a los que no lo hacen. Los primeros son msrobustos; no se equivocarn frente a una pequea

perturbacin en la entrada. El conocimiento del programaes comprendido fcilmente por la gente. Estos programas

pueden trabajar con facilidad en grandes problemas endonde los mtodos directos fallan [2,8].

Los esfuerzos dedicados a construir programas que llevena cabo tareas de la misma forma que el hombre, sedividen en dos clases. Los programas de la primera clasese encargan de aquellos problemas que una computadora

puede resolver fcilmente, pero cuya solucin implica el

uso de mecanismos de los que no dispone el hombre; estetipo de problemas no se adapta mucho con la definicinde tarea pertinente a la IA. La segunda clase de

programas son los que intentan modelar elcomportamiento humano, ellos realizan tareas que seadaptan claramente con la definicin de tareas de IA,haciendo tareas que no son triviales para unacomputadora [3,10].

Hay varias razones para querer modelar la forma detrabajar humana para llevar a cabo estas tareas: verificarlas teoras psicolgicas de la actuacin humana, capacitarlas computadoras para comprender el comportamiento

humano, capacitar la gente para comprender a las


3/6

Scientia et Technica Ao XIV, No 39, Septiembre de 2008. Universidad Tecnolgica de Pereira. 137

computadoras y explotar el conocimiento que se puedebuscar en el hombre [2]. Esta ltima motivacin esprobablemente la ms importante, debido a que elhombre es el sistema del que mejor se conoce el cmolleva a cabo las tareas con las que estamos familiarizadosy por lo tanto tiene sentido fijarse en l para buscar pistasde cmo actuar. Si lo que se quiere es escribir programasque simulen el comportamiento humano ante una tarea, laforma de medir el xito est en que el comportamientodel programa corresponda con el humano, as comomediante distintas clases de experimentos y anlisis de

protocolos. En este sentido no se busca un programa quesimplemente sea tan bueno como sea posible, se busca un

programa que falle donde la gente lo hace [8].

Es necesario aclarar que la pregunta de si una mquinaposee inteligencia o puede pensar, es demasiado difusapara poder contestarla con precisin. Sin embargo, con

frecuencia es posible construir un programa queencuentre un criterio de rendimiento para una tareaconcreta. Esto no significa que el programa realice latarea de la mejor manera posible, slo significa que seentiende como mnimo una forma de hacer al menos

parte de una tarea. Cuando se quiere disear un programade IA, se debe intentar especificar tan bien como sea

posible el criterio de xito para el funcionamiento delprograma en su particular y restringido dominio [1].

Para construir un sistema que resuelva un problemaespecfico, es necesario realizar estas cuatro acciones: Definir el problema con precisin. La definicin debe

incluir especificaciones precisas tanto sobre lassituaciones iniciales como sobre las situacionesfinales que se aceptaran como soluciones al

problema. Analizar el problema. Algunas caractersticas de gran

importancia pueden tener un gran efecto sobre laconveniencia o no de utilizar diversas tcnicas queresuelvan el problema.

Aislar y representar el conocimiento necesario pararesolver el problema.

Elegir la mejor tcnica que resuelva el problema yaplicarla al problema particular.

4. SISTEMA DE PRODUCCIN

Debido a que la bsqueda es el ncleo de muchosprocesos inteligentes, es adecuado estructurar losprogramas de IA de forma que se facilite describir ydesarrollar el proceso de bsqueda. Los sistemas de

produccin proporcionan tales estructuras [2]. Unsistema de produccin consiste en: Un conjunto de reglas. Una o ms bases de datos/conocimiento. Una estrategia de control que especifique el orden en

el que las reglas se comparan con la base de datos, y

la forma de resolver los conflictos que surjan cuandovarias reglas puedan ser aplicadas a la vez.

Un aplicador de reglas.

El proceso de solucin del problema puede modelarsecomo un sistema de produccin. El problema que se

plantea es escoger la estructura de control apropiada parael sistema de produccin con el fin de que el proceso de

bsqueda sea lo ms eficiente posible [1,2].

4.1 Estrategias de control

El primer requisito que debe cumplir una buena estrategiade control es que cause algn cambio, las estrategias decontrol que no causen cambio de estado nunca alcanzanla solucin. El segundo requisito que debe cumplir una

buena estrategia de control es que sea sistemtica [10].

Para tener una buena claridad de las estrategias de controlen la solucin de laberintos, se presenta en la Figura 1, amodo de ejemplo un laberinto que un mvil, representado

por un crculo negro, desea solucionar; siendo la solucindel laberinto el tringulo negro. Las paredes del laberintoson cuadros grises y las posiciones en el laberinto serepresentan por una letra acompaada por un nmero, deesta forma la posicin inicial se localiza en E9 y la

posicin final en H1. En la figura 2 se presenta un rbolde bsqueda para el laberinto de la Figura 1. En la razdel rbol se encuentra el estado inicial, todas lasramificaciones de la raz se generan al aplicar cada una

de las reglas al estado inicial. Cada bifurcacin en unarama representa un punto del laberinto con varioscaminos y una rama de la que no sale ninguna

bifurcacin puede ser un callejn sin salida o la solucin.

4.1.1 Bsqueda en amplitud

Este mtodo va construyendo un grafo de estadosexplicito mediante la aplicacin de los operadoresdisponibles al nodo inicial, despus aplica los operadoresdisponibles a los nodos sucesores directos del nodoinicial, y as sucesivamente [5,6]. Este procedimiento de

bsqueda acta de manera uniforme a partir del nodoinicial.

Este tipo de bsqueda consiste en ir explorando el rbolpor ramas del mismo nivel, es decir, no se podr exploraruna rama superior si la rama inferior no se ha explorado

por completo.

La bsqueda en amplitud no queda atrapada explorandocallejones sin salida, adems, si existe una solucin la

bsqueda en anchura garantiza que se encuentre. Siexisten mltiples soluciones se encuentra la solucinmnima, es decir, la que requiera el mnimo nmero de

pasos. Esto est garantizado por el hecho de que noexplora una ruta larga hasta que se hayan examinado

todas las rutas ms cortas que ella.


4/6


Figura 1. Laberinto.

Figura 2. rbol de bsqueda

4.1.2 Bsqueda en profundidad

En este proceso de bsqueda se genera slo un sucesordel nodo en cada paso, es decir, cada vez que se obtieneun nuevo sucesor, se le aplica a este un nuevo operador yse obtiene un nuevo sucesor, y as sucesivamente.

En este tipo de bsqueda se avanza por una sola rama delrbol hasta que se encuentre una solucin o hasta que sellegue a un callejn sin salida [3]. En el caso de llegar aun callejn sin salida se retorna hasta la raz para iniciaruna nueva bsqueda. La bsqueda en profundidadnecesita menos memoria ya que slo almacena los nodosdel camino que se siguen en ese instante. Esto contrastacon la bsqueda en anchura en la cual debe almacenarsetodo el rbol que haya sido generado hasta ese momento.

5. SOFTWARE DESARROLLADO

Se desarrollo utilizando Wx Dev C++ un software para elestudio de los diferentes mtodos de solucin de

laberintos llamado Teseo. En la Figura 3 se presenta la

interfaz grfica de Teseo con la cual se pueden construirdiferentes tipos de laberintos como el que se muestra, elcual equivale al de la Figura 5.

Figura 3. Panel inicial de Teseo.

En la Figura 4 se ilustra las diferentes funciones deTeseo, entre las que se destaca la posibilidad de construircualquier tipo de laberinto, almacenarlo, cargar laberintos

previamente diseados, escoger un mtodo de solucinpara el laberinto como la velocidad a la que se quiere

solucionar, tambin es posible visualizar las matrices dediseo la cuales contiene las coordenadas de cada uno delos muros del laberinto y la del recorrido en la cual semuestra la solucin del laberinto dada por el mtodo desolucin seleccionado.

6. RESULTADOS

En la Figura 5 se muestra un laberinto que contienecircuitos cerrados conocido como simplementeconectado. Se presentan en la tabla 1 los tiempos de cadauna de las tcnicas de bsqueda en amplitud y

profundidad para cinco diferentes intentos. En la Tabla 1se observa que la bsqueda en amplitud es un mtodo queconsigue los mejores tiempos en promedio y en todos losintentos se observa que es una tcnica con tiempos muyuniformes. Para llegar a la solucin del laberinto la

bsqueda en amplitud realiz un recorrido completo dellaberinto.

En la Figura 6 se muestra un laberinto que contienemuros separados conocido como conexiones mltiples.Se muestran en la Tabla 2, los resultados para cincointentos de solucin empleando la bsqueda en amplitudy profundidad. Este tipo de laberinto no puede sersolucionado empleando el usual mtodo de recorrer una

pared y girar siempre en una misma direccin en las


5/6

Scientia et Technica Ao XIV, No 39, Septiembre de 2008. Universidad Tecnolgica de Pereira. 139

bifurcaciones ya que su estructura de muros separadosocasiona un recorrido en crculos sobre la mismatrayectoria sin llegar a la solucin.

Figura 5. Laberinto del tipo simplemente conectado

AmplitudTiempo [s]

ProfundidadTiempo [s]

17.09 33.1215.76 42.3516.46 37.9516.71 31.9517.55 38.17

16.710.67 36.704.21

Tabla 1. Resultados para el laberintosimplemente conectado

Figura 6. Laberinto del tipo conexiones mltiples.

Se observa de la Tabla 2 que la bsqueda en amplitud obtieneen promedio el mejor tiempo para la solucin del laberinto,aunque tambin se observa que el mejor tiempo de un intentolo obtuvo la bsqueda en profundidad, con un tiempo muyinferior a los empleados por la bsqueda en amplitud. Esteltimo tiempo se obtuvo recorriendo la ruta mnima entre elobjetivo y el punto inicial.

AmplitudTiempo [s]

ProfundidadTiempo [s]

20.74 36.9321.18 21.3519.82 3.9419.60 28.4521.67 26.93

20.600.88 23.5212.30

Tabla 2. Resultados para el laberinto conexiones mltiples

Figura 4. Funciones de Teseo.


6/6


7. APORTES Y CONCLUSIONES

Se desarroll un software con el cual se pueden disear

diferentes tipos de laberintos para hacer una comparacinentre las diferentes tcnicas de inteligencia artificial de

bsqueda y de esta forma lograr un mejor entendimientode las mismas. Adems fueron planteados dos mtodosde solucin de laberintos usando tcnicas de inteligenciaartificial, los cuales son la bsqueda en profundidad yamplitud.

El mtodo de bsqueda en amplitud obtiene en promediolos mejores tiempos de solucin a pesar de tener querecorrer todo el laberinto empleando ms memoria pararealizar la bsqueda, por otro lado, la bsqueda en

profundidad es ms aleatoria en cuanto al tiempo de

solucin, no obstante puede obtener mejores tiempos quela bsqueda en amplitud y menor cantidad de memoria,pero en promedio sus tiempos de bsqueda son mayores.Dependiendo del tipo de laberinto ingresado, cadamtodo empleado entrega una solucin mejor que la otra.

8. REFERENCIAS BIBLIOGRFICAS

[1] S. J. Russell, P. Norvig, Inteligencia Artificial:un enfoque moderno, Mexico, Prentice HallHispanoamericana, S.A. 1996.

[2] R. S. Aylett, G. J. Petley, P. W. H. Chung, B.Chen, D. W. Edwards, AI planning: solutions

for real world problems, Knowledge-BasedSystems, Elsevier, Vol. 13, No. 2, 2000, pp. 61-69(9).

[3] D. C. Dracopoulos, Neural robot path planning:The maze problem, Neural Computing &Applications, Springer London, ISSN0941-0643(Print) 1433-3058, Vol. 7, No. 2, June, 1998,

pp.115-120, April 06, 2005.[4] S. Srinivasan, D.P. Mital, S. Haque, A novel

solution for maze traversal problems usingartificial neural networks, Computers andElectrical Engineering, Vol. 30, 2004, pp. 563572.

[5]

W. Shenga, Q. Yang, J. Tan, N. Xi, Distributedmulti-robot coordination in area exploration,Robotics and Autonomous Systems, Elsevier,2006, doi:10.1016/j.robot.2006.06.003.

[6] S. Carpin, G. Pillonetto, Motion Planning UsingAdaptive Random Walks, IEEE TransactionsOn Robotics, Vol. 21, No. 1, Febrero 2005.

[7] B. Tovar, L. Muoz-Gmez, R. Murrieta-Cid, M.Alencastre-Miranda, R. Monroy, S. Hutchinsona,Planning exploration strategies for simultaneouslocalization and mapping, Robotics andAutonomous Systems, Elsevier, Vol 54, 2006,

pp. 314331.[8] N. Nilsson, Inteligencia Artificial, una nueva

sntesis, Espaa, McGraw-Hill/Interamericanade Espaa, S.A. 2001.

[9] A.J. Bagnall, Z.V. Zatuchna, On theClassification of Maze Problems, Applicationsof Learning Classifier Systems, Studies in, Bull,Springer, pp. 307-316, 2005.

[10] P. Gerard, O. Siguad, YACS: CombiningDynamic Programming with Generalization inClassifier Systems, Advances in LearningClassifier Systems. Springer, 2001, pp. 5269.

Dialnet-TecnicasDeInteligenciaArtificialParaLaSolucionDeLa-4742651.pdf

Documents

Transcript of Dialnet-TecnicasDeInteligenciaArtificialParaLaSolucionDeLa-4742651.pdf