PDF de programación - Capitulo 1 - Resolución de problemas

CAPITULO 1



RESOLUCIÓN DE PROBLEMAS



• Espacio de Estados
• Características Generales de los Procesos de

Búsqueda

• Estrategias de Exploración del Espacio de

Estados

• Resumen
• Textos Básicos



Fundamentos de Inteligencia Artificial

1. RESOLUCIÓN DE PROBLEMAS

No podemos decir que algo o alguien exhibe comportamiento inteligente si no
explota de manera eficaz y eficiente1 un conjunto mínimo de conocimientos. Una
arquitectura, natural o artificial, bien definida y estructurada pero vacía, no puede
utilizarse para resolver problemas mientras no incorpora procedimientos de resolución y
conocimientos propios del dominio de los problemas planteados.

Es claro que no todos los problemas son iguales, por lo que los tipos de
conocimiento necesarios van a ser diferentes también. De hecho, para ciertas clases de
problemas, lo que habitualmente entendemos como “conocimiento” puede ser sustituido
por procedimientos preestablecidos que se ejecutan mecánicamente. Así, cualquier
ordenador debidamente programado es capaz de “resolver” la ecuación:

2

x

+

4

x

0
+ =

3

Incluso, aunque con un esfuerzo de programación algo mayor, ningún ordenador

tendría excesivos problemas para resolver ecuaciones como la que sigue:

2

ax

+

bx

0
+ =

c

La resolución de este tipo de problemas no requiere necesariamente la
utilización de técnicas de inteligencia artificial. Es más, su empleo sería equivalente a
utilizar cañones para matar moscas... No sería apropiado.

En general, el tipo de problema planteado condiciona la técnica de resolución a
emplear. No obstante, la decisión de utilizar una técnica de IA o una técnica
convencional de programación puede ser también cuestión de planteamiento. Como
norma general, el empleo de técnicas de IA debe permitir la construcción de programas
que:

• Capten generalizaciones, de forma que cada situación individual que se produzca no
tenga que ser representada de forma separada. Por el contrario, todas aquellas
situaciones que compartan propiedades deben ser agrupadas.

• Hagan explícito su conocimiento, al objeto de facilitar su comprensión.

• Puedan actualizarse continuamente, de forma que sea factible modificar el

conocimiento sin tener que manipular ni alterar todo el programa.

• Puedan ser empleados en muchas situaciones, aún cuando las respuestas que

generen sean parcialmente correctas o imprecisas.

La aplicación de estos criterios en la resolución de problemas de dominios
concretos, conduce a la construcción de programas con características esencialmente


1 Decimos que un sistema es eficaz cuando es capaz de resolver correctamente un problema. Un sistema

es eficiente cuando, además de comportarse eficazmente, optimiza los recursos disponibles.

3

Fundamentos de Inteligencia Artificial

diferentes a los construidos mediante técnicas convencionales. Así, mientras los
programas de IA deben ser empleados para tratar fundamentalmente dominios
simbólicos, los programas convencionales son particularmente idóneos para tratar
dominios numéricos. Por otra parte, la búsqueda de soluciones en los dominios
apetecidos por la IA se realiza a través de procesos heurísticos2, en los que los pasos
hacia la solución suelen ir implícitos. Por el contrario, los programas convencionales
emplean procedimientos algorítmicos de búsqueda, con pasos explícitos hacia la
solución. Por último, mientras en los programas convencionales la información y el
control se encuentran físicamente integrados en una misma estructura, en los
programas de IA el conocimiento del dominio y las estructuras de control suelen estar
físicamente separados, dando como resultado arquitecturas mucho más modulares.

Como siempre ocurre, la diferencia no es lo suficientemente evidente como para
permitirnos establecer una frontera clara entre los “problemas de IA” (i.e., aquellos
para cuya resolución está indicada la aplicación de técnicas de IA), y los “problemas
convencionales” (i.e., aquellos para cuya resolución están indicadas las técnicas de
programación convencional). Sin embargo, un análisis cuidadoso del dominio nos
puede dar pistas a la hora de elegir una u otra filosofía, y evitar así errores provocados
por el hecho de no ajustar la técnica al tipo de problema que queremos resolver.

Analicemos el siguiente problema:

“Supongamos que tenemos dos cubos inicialmente vacíos, uno de 6 litros y el
otro de 8 litros. Ninguno de los cubos tiene marca ni división alguna. Disponemos de un
grifo de agua que podemos utilizar. ¿Cómo podríamos llenar el cubo de 8 litros
exactamente hasta la mitad?”

Es claro que en este problema hay un conjunto de acciones que pueden llevarse a
cabo si se cumplen unos requisitos mínimos. La situación se ilustra esquemáticamente
en la Tabla 1.1.



2 El conocimiento heurístico es un conocimiento difícilmente formalizable, fruto de la experiencia, y que
se establece implícitamente para tratar de encontrar respuestas más o menos correctas, pero siempre
válidas, a problemas de dominios concretos.

4

Fundamentos de Inteligencia Artificial

PRECONDICIONES

Nº
1 El cubo de 8 litros no está lleno
2 El cubo de 6 litros no está lleno
3 El cubo de 8 litros no está vacío
4 El cubo de 6 litros no está vacío

5

6

7

8

El cubo de 8 litros no está vacío, y
El cubo de 6 litros no está lleno, y
El contenido de ambos es menor o igual a seis litros
El cubo de 6 litros no está vacío, y
El cubo de 8 litros no está lleno, y
El contenido de ambos cubos es menor o igual a 8 litros
El cubo de 6 litros no está vacío, y
El cubo de 8 litros no está lleno, y
El contenido de ambos cubos es mayor o igual a 8 litros
El cubo de 8 litros no está vacío, y
El cubo de 6 litros no está lleno, y
El contenido de ambos cubos es mayor o igual a 6 litros

ACCIONES
Llenar el cubo de 8 litros
Llenar el cubo de 6 litros
Vaciar el cubo de 8 litros
Vaciar el cubo de 6 litros
Vaciar el contenido del cubo de 8 litros
en el cubo de 6 litros

Vaciar el contenido del cubo de 6 litros
en el cubo de 8 litros

Llenar el cubo de 8 litros
con el contenido del cubo de 6 litros

Llenar el cubo de 6 litros
con el contenido del cubo de 8 litros

Tabla 1.1

Requisitos mínimos y acciones posibles relativos al problema de los dos cubos

Una secuencia de acciones que resolvería el problema inicialmente planteado
(i.e., conseguir un estado final en el que el cubo de 8 litros estuviese lleno justamente
hasta la mitad), podría ser la siguiente:

primero: Con los dos cubos vacíos ejecutar la acción número 2, con lo que tendríamos el

cubo de 8 litros vacío, y el cubo de 6 litros lleno.

segundo: Ejecutar la acción número 6, con lo que tendríamos 6 litros en el cubo de 8

litros, y el cubo de 6 litros vacío.

tercero: Repetir la acción número 2, con lo que tendríamos 6 litros en cada uno de los

cubos.

cuarto: Ejecutar la acción número 7, con lo que tendríamos el cubo de 8 litros lleno, y

nos quedarían 4 litros en el cubo de 6 litros.

quinto: Ejecutar la acción número 3, con lo que quedarían 4 litros en el cubo de 6

litros, y el cubo de 8 litros estaría vacío.

sexto: Ejecutar la acción número 6, con lo que tendríamos 4 litros en el cubo de 8
litros, y el cubo de 6 litros estaría vacío, lo que representa una posible solución
a nuestro problema.

Nótese que, en este ejemplo, la solución propuesta es sólo una de un conjunto
de soluciones válidas. En efecto, cualquier estado en el que el cubo de 8 litros estuviese
lleno por la mitad sería válido, independientemente de la cantidad de agua que hubiese
en el cubo de 6 litros.

Parece que hemos sido capaces de encontrar una solución al problema planteado.
Podríamos pensar ahora en cómo representar ambos, problema y solución, al objeto de
facilitar la posterior labor de implementación. Al respecto, consideraremos nuestro
universo de estados posibles como pares ordenados, en los que el primer elemento del

5

Fundamentos de Inteligencia Artificial

par representa el contenido del cubo de 8 litros, y el segundo elemento del par
representa el contenido del cubo de 6 litros. Las acciones que suponen transiciones
entre estados posibles las representaremos entre guiones. Con este formalismo, la
secuencia de estados por los que el problema evoluciona, desde el estado inicial hasta
que llegamos a una solución “razonable”, es la siguiente:

(0,0) -2- (0,6) -6- (6,0) -2- (6,6) -7- (8,4) -3- (0,4) -6- (4,0)

Una forma de programar una solución a este problema consiste en resolverlo
previamente sobre el papel y luego codificar la solución en un lenguaje cualquiera. Tal
procedimiento, sin duda eficaz en el tiempo, tiene no obstante serios inconvenientes.
Uno de ellos es la “rigidez” del programa resultante. Efectivamente, simplemente
variando las condiciones iniciales, o la solución buscada, el problema sería diferente y,
por lo tanto, el programa diseñado no sería válido. Hay que buscar otro enfoque.

Supongamos que podemos definir “a priori” un conjunto de situaciones posibles
y unas “reglas del juego” potencialmente útiles, y supongamos también que podemos
diseñar unas estrategias generales, que investiguen la aplicabilidad de las reglas del
juego sobre los estados para obtener otros estados, de forma que sea el ordenador quien
encuentre por sí mismo la solución al problema. Nótese que este nuevo enfoque es de
naturalez