Introducción a la Inteligencia Artificial
 

1-Introducción


 
1.1. Definición de Inteligencia Artificial (IA) y evolución histórica
1.2. Técnicas de resolución de problemas de IA
1.3. Criterios de éxito de la IA
1.4. Resolución de problemas de IA:  


1.1. Definición de Inteligencia Artificial  

En la bibliografía del área encontramos diferentes definiciones que pueden darnos una idea de lo que se llama inteligencia artificial:
 

Desde el punto de vista de los objetivos, la IA puede considerarse como parte de la ingeniería o de la ciencia: Algunas aplicaciones de la inteligencia artificial: Desarrollo histórico de la Inteligencia Artificial según Jackson:
   

1.2. Técnicas de resolución de problemas de IA  

Uno de los resultados que surgieron de las primeras investigaciones en IA fue que la inteligencia necesita conocimiento. El conocimiento posee algunas propiedades poco deseables como:
 

Una técnica de IA es un método que explota el conocimiento representado de manera que se cumpla que:
  Se pueden caracterizar las técnicas de IA con independencia del problema a tratar.

Para solucionar problemas complicados, los programas que utilizan las técnicas de IA presentan numerosas ventajas con respecto a los que no lo hacen:

Como contraposición, generalmente tienen más complejidad que otras soluciones.

Se analizan brevemente a continuación dos tipos de problemas bien diferenciados, y dentro de cada uno se ejemplifica lo que se entiende por una técnica de IA.

Ejemplo 1: tres en raya

A continuación se plantean tres soluciones diferentes del problema de tres en raya analizando la conveniencia de cada una. Para mejor detalle de las mismas consultar [Rich98].
 

Ejemplo 2: respuestas a preguntas

Se quiere realizar un programa que a partir de un texto escrito en español pueda responder a preguntas en español sobre este texto. En este caso, es más difícil que en el ejemplo anterior determinar formalmente y con precisión en qué consiste el problema y en qué consiste una solución correcta para él. Un ejemplo de programa de preguntas y respuestas en inglés es el programa POLITICS (Carbonell,  1980).

A continuación se plantean tres soluciones diferentes analizando la conveniencia de cada una. Para mejor detalle de las mismas consultar [Rich98].
 

Estos ejemplos ponen de manifiesto tres importantes técnicas de IA:

1.3. Criterios de éxito de la IA  

Para determinar el éxito de un programa de IA, se deben realizar las siguientes preguntas:

Test de Turing

En 1950, Alan Turing propuso el siguiente método para determinar si una máquina es capaz de pensar. Una persona es un entrevistador y se halla en una habitación separado de otra persona y un ordenador a evaluar. El entrevistador hace preguntas a ambos de forma escrita. Si luego de un cierto número de preguntas y respuestas, el interrogador no puede identificar quién es el computador y quién es la persona, entonces podemos decir que el computador piensa.

¿Se puede calibrar el éxito de la IA en dominios más restringidos? Por ejemplo,

Cuando se quiere diseñar un programa de IA, se debe intentar especificar tan bien como sea posible el criterio de éxito para el funcionamiento del programa en su dominio particular.
 



1.4. Resolución de problemas de IA   

 

Para construir un sistema que resuelva un sistema específico, es necesario:

1- Definir el problema formalmente con precisión.
2- Analizar el problema.
3- Representar el conocimiento necesario para resolver el problema.
4- Elegir la mejor técnica que resuelva el problema y aplicarla.
 

1.4.1. Definición formal del problema

El primer paso para diseñar un programa que resuelva un problema es crear una descripción formal y manejable del propio problema. Sería adecuado contar con programas que produzcan descripciones formales a partir de descripciones informales, proceso denominado operacionalización. Dado que por ahora no se conoce la forma de construir estos programas este proceso debe hacerse manualmente.

Hay problemas que por ser artificiales y estructurados son fáciles de especificar (por ej. el ajedrez, el problema de las jarras de agua, etc. ). Otros problemas naturales, como por ej. la comprensión del lenguaje, no son tan sencillos de especificar.

Para producir una especificación formal de un problema se deben definir:
 

Un estado es la representación de un problema en un instante dado. Para definir el espacio de estados no es necesario hacer una enumeración exhaustiva de todos los estado válidos, sino que es posible definirlo de manera más general.

El estado inicial consiste en uno o varios estados en los que puede comenzar el problema. El estado objetivo consiste en uno o varios estados finales que se consideran solución aceptable.

Las reglas describen las acciones u operadores que posibilitan un pasaje de estados. Una regla tiene una parte izquierda y una parte derecha. La parte izquierda determina la aplicabilidad de la regla, es decir, describe los estados a los que puede aplicarse la regla. La parte derecha describe la operación que se lleva a cabo si se aplica la regla, es decir, como obtener el estado sucesor.

Por ejemplo, en el problema de jugar al ajedrez:

Dado que escribir exhaustivamente todas las reglas es imposible prácticamente, (en el ejemplo, escribir todas las posiciones de tablero), las reglas deben escribirse de la manera más general posible.

La representación como espacio de estados forma parte de la mayoría de los métodos de IA. Su estructura se corresponde con la resolución de problemas porque:

Ejercicio 1: Problema de las jarras de agua

Se tienen dos jarras de agua, una de 4l y otra de 3l sin escala de medición.
Se desea tener 2l de agua en la jarra de 4l. Las siguientes operaciones son válidas: llenar las jarras, tirar agua de las jarras, pasar agua de una jarra a otra.
 
Solución:
 

{ (X,Y)/ X son los litros en la jarra de 4l con 0<=X<=4 AND Y son los litros de la jarra de 3l con 0<=Y<=3 } 1. Llenar la jarra de 4l: Si (X,Y) AND  X<4  => (4,Y)

2. Llenar la jarra de 3l: Si (X,Y) AND Y<3  => (X,3)

3. Vaciar la jarra de 4l: Si (X,Y) AND X>0  => (0, Y)

4. Vaciar la jarra de 3l: Si (X,Y) AND Y>0  => (X, 0)

5. Pasar agua de la jarra de 4l a la jarra de 3l hasta llenarla: Si (X,Y) AND X>0 AND  X+Y>=3  => (X-(3-Y),3)

6. Pasar agua de la jarra de 3l a la jarra de 4l hasta llenarla: Si (X,Y) AND Y>0 AND  X+Y>=4  => (4, Y-(4-X))

7. Pasar toda el agua de la jarra de 4l a la jarra de 3l: Si (X,Y) AND X>0 AND X+Y<3  => (0,X+Y)

8. Pasar toda el agua de la jarra de 3l a la jarra de 4l: Si (X,Y) AND Y>0 AND X+Y<4  => (X+Y,0)
 

El programa debería encontrar un pasaje de estados para ir del estado (0,0) al estado (2,0). Puede existir más de un pasaje de estados hacia la solución, por ejemplo:

(0,0) => (0,3) => (3,0) => (3,3) => (4,2) => (0,2) => (2,0)

en la cual, a partir del estado inicial, se aplicaron las reglas 2, 8, 2, 6, 3 y 8, hasta conseguir el estado objetivo.

Otro pasaje de estados hacia la solución es la siguiente

(0,0) => (4,0) => (1,3) => (1,0) => (0,1) => (4,1) => (2,3) => (2,0)
 
en la cual se aplicaron las reglas 1, 5, 4, 7, 1, 5 y 4
 

Con respecto a las reglas se puede concluir que:
 

 
Ejercicio 2: Problema de los Caníbales y Monjes
 

1.4.2. Estrategia de control: Métodos de búsqueda

El problema puede resolverse con el uso de reglas en combinación con una estrategia de control para trasladarse a través del espacio de estados hasta encontrar un camino desde el estado inicial hasta el estado final. Se elige una regla entre aquellas cuya parte izquierda concuerda con el estado actual. Se aplica la regla elegida realizando el cambio de estado tal como se describe en la parte derecha de la regla. Si el nuevo estado es estado objetivo o final se ha encontrado la solución. En caso contrario se continúa con la aplicación de reglas al nuevo estado.

Una estrategia de control especifica el orden en el que se deben aplicar las reglas, así como también la forma de resolver conflictos cuando es posible aplicar más de una regla. Para que una estrategia de control sea válida debe cumplir con dos requisitos:

En caso de no contar con una aproximación directa al problema, el proceso de búsqueda resulta fundamental en la resolución del mismo. Los algoritmos de búsqueda detallados a continuación son ejemplos de estrategias de control sistemáticas. Todos se basan en considerar un árbol de estados cuya raíz es el estado inicial, y en cada nivel se hallan los estados sucesores correspondientes.
  Este algoritmo de búsqueda visita cada nodo del árbol por niveles, es decir, visita todos los nodos de un nivel antes de visitar los del siguiente. A continuación se detalla un pseudo-código de este algoritmo:

Lista_nodos = [estado_inicial];
Mientras Not Vacia(lista_nodos)

Fin Mientras;

Este algoritmo básico debería modificarse para detectar el caso en que se vuelva a alcanzar un estado que ya ha sido visitado con anterioridad. En este caso, debería realizarse una "poda" de la rama del árbol, ya que en caso contrario se volvería a generar un subárbol ya generado.

Con la búsqueda a lo ancho se asegura que una vez alcanzada una solución no existe otra ruta hacia la solución que tenga menor cantidad de pasos. Una desventaja de este algoritmo es que para alcanzar una solución de n pasos, debe haber explorado todo el espacio de estados hasta ese nivel.

Ejercicio:
Realizar el árbol de búsqueda a lo ancho para encontrar la solución del problema de las jarras de agua.
 
 

Este algoritmo de búsqueda continúa por una rama del árbol hasta encontrar la solución o decidir terminar la búsqueda por esa dirección (por llegar al estado final, por tener un largo de ruta que supera una cota máxima determina, por haber llega a un estado ya visitado, etc.). Al fracasar una ruta, se realiza un backtracking o vuelta atrás, continuando la exploración en el paso inmediatamente anterior. A continuación se detalla un pseudo-código de este algoritmo recursivo que incialmente es llamado con el estado_inicial:

Función Buscar (estado_actual) devuelve Boolean
Comienzo

Fin Buscar;

Este algoritmo básico debería modificarse para terminar la búsqueda en una rama que se alcanza un estado que ya visitado.

Con la búsqueda en profundidad no es necesario tener almacenado todo el espacio de estados, sino sólo el camino que se está explorando. Puede encontrar la solución sin tener que explorar gran parte del espacio de estados. Como desventajas de este algoritmo se señala que puede seguir una ruta infructuosa durante muchos pasos, y además la primera solución que encuentra puede distar mucho de ser la solución de mínima cantidad de pasos.
 

Existen algunos problemas en los que resulta imposible explorar el árbol del espacio de estados pues resulta en una explosión combinatoria. Por ej. en el problema del viajante, se debe encontrar la ruta mínima entre N ciudades a visitar. Si se aplica cualquiera de los dos algoritmos de búsqueda anteriores, nos encontramos ante un costo computacional no polinomial O(N!).

Una heurística es una técnica que aumenta la eficiencia de un proceso de búsqueda. El objetivo es guiar al proceso de búsqueda en la dirección más provechosa sugiriendo el camino a seguir cuando hay más de una opción.

Las heurísticas pueden ser:

Las heurísticas pueden sacrificar la completitud, es decir, pueden pasar por alto una buena solución. Sin embargo, existen varios argumentos a favor de usarlas: Las heurísticas se pueden incorporar a un proceso de búsqueda basado en reglas de dos maneras: En conclusión, las heurísticas representan el conocimiento general y específico del mundo, que hace que sea abordable solucionar problemas complejos.
 

1.4.3. Análisis del problema

Luego de definir el problema formalmente, el segundo paso en la resolución del problema es el análisis del mismo. A fin de poder elegir el método más apropiado  para resolver un problema particular, es necesario analizar distintas cuestiones que afectan a al definición del mismo y a las características de la solución deseada. Existen varias preguntas a responder acerca del problema:

1. ¿Puede descomponerse el problema en subproblemas más pequeños?
2. ¿Pueden deshacerse pasos inadecuados hacia la solución?
3. ¿Es predecible el universo del problema?
4. ¿Una solución es buena de manera absoluta o relativa?
5. ¿La solución deseada es un estado o la ruta hacia un estado?
6. ¿El conocimiento se necesita para resolver el problema o para restringir la búsqueda de la solución?
7. El programa que soluciona el problema ¿busca la solución solo o necesita interactuar con una persona?
 

1. ¿Puede descomponerse el problema en subproblemas más pequeños?

Algunos problemas pueden descomponerse en subproblemas independientes, de manera que encontrar una solución global es la composición de soluciones particulares. Por ej. en la resolución de integrales, una integral puede descomponerse por partes, y resolver las partes simples directamente o descomponerlas recursivamente.

Por otra partes, existen otros problemas que no pueden descomponerse y componer la solución a partir de las soluciones parciales de sus partes. Por el contrario, una solución necesita considerar globalmente el problema. Por ej. el problema del mundo de los bloques.

2. ¿Pueden deshacerse pasos inadecuados hacia la solución?

Algunos problemas permiten deshacer uno o varios pasos hacia una solución una vez realizados. En este aspecto, existen tres categorías en las que puede dividirse un problema:

 
3. ¿Es predecible el universo del problema?

Los problemas pueden se de:

Los problemas más difíciles de resolver son los no recuperables de consecuencia incierta. Por ej. el control del brazo de un robot: es de consecuencia incierta pues alguien puede interponer un objeto en la ruta del brazo, se puede atascar, etc.

4. ¿Una solución es buena de manera absoluta o relativa?

La solución de un problema puede consistir en encontrar:

5. ¿La solución deseada es un estado o la ruta hacia un estado?

La solución de un problema puede consistir en encontrar:

6. ¿El conocimiento se necesita para resolver el problema o para restringir la búsqueda de la solución?

El conocimiento puede emplearse para:

7. El programa que soluciona el problema ¿busca la solución solo o necesita interactuar con una persona?

Con respecto a la relación programa-usuario, existen dos tipos de programas que solucionan el problema:

Ejercicio: Torres de Hanoi

Definir formalmente y analizar los 7 puntos anteriores en el siguiente problema:

Se hallan N discos de distinto tamaño apilados sobre una base A de manera que cada disco se encuentra sobre uno de mayor radio. Existen otras dos bases vacías B y C. El objetivo es llevar todos los discos de la base A hasta la base C, para lo cual puede usarse la base B. Considerar que se puede mover sólo un disco a la vez, y cada disco puede descansar solamente en las bases y no en el suelo. Recordar que los discos deben situarse siempre sobre uno de mayor radio.