inteligencia artificial

SEGUNDO CICLO

2 Agentes inteligentes

Donde se discutirá la naturaleza de los agentes ideales, sus diversos hábitats y las
formas de organizar los tipos de agentes existentes.

El Capítulo 1 identifica el concepto de agente racional como central en la perspectiva

de la inteligencia artificial que presenta este libro. Esta noción se concreta más a lo lar-
go de este capítulo. Se mostrará como el concepto de racionalidad se puede aplicar a una
amplia variedad de agentes que operan en cualquier medio imaginable. En el libro, la
idea es utilizar este concepto para desarrollar un pequeño conjunto de principios de di-
seño que sirvan para construir agentes útiles, sistemas que se puedan llamar razonable-
mente inteligentes.
Se comienza examinando los agentes, los medios en los que se desenvuelven, y la
interacción entre éstos. La observación de que algunos agentes se comportan mejor que
otros nos lleva naturalmente a la idea de agente racional, aquel que se comporta tan bien
como puede. La forma de actuar del agente depende de la naturaleza del medio; algu-
nos hábitats son más complejos que otros. Se proporciona una categorización cruda del
medio y se muestra cómo las propiedades de un hábitat influyen en el diseño de agen-
tes adecuados para ese entorno. Se presenta un número de «esquemas» básicos para el
diseño de agentes, a los que se dará cuerpo a lo largo del libro.

2.1 Agentes y su entorno

MEDIOAMBIENTE Un agente es cualquier cosa capaz de percibir su medioambiente con la ayuda de sen-
sores y actuar en ese medio utilizando actuadores1. La Figura 2.1 ilustra esta idea sim-

1
Se usa este término para indicar el elemento que reacciona a un estímulo realizando una acción (N. del RT).
38 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

Agente Sensores
Percepciones

Medio ambiente
?

Acciones
Actuadores

Figura 2.1 Los agentes interactúan con el medioambiente mediante sensores y efectores.

SENSOR ple. Un agente humano tiene ojos, oídos y otros órganos sensoriales además de manos,
piernas, boca y otras partes del cuerpo para actuar. Un agente robot recibe pulsaciones
ACTUADOR
del teclado, archivos de información y paquetes vía red a modo de entradas sensoriales
y actúa sobre el medio con mensajes en el monitor, escribiendo ficheros y enviando pa-
quetes por la red. Se trabajará con la hipótesis general de que cada agente puede perci-
bir sus propias acciones (pero no siempre sus efectos).
PERCEPCIÓN El término percepción se utiliza en este contexto para indicar que el agente puede
SECUENCIA DE
recibir entradas en cualquier instante. La secuencia de percepciones de un agente
PERCEPTORES refleja el historial completo de lo que el agente ha recibido. En general, un agente
tomará una decisión en un momento dado dependiendo de la secuencia completa de per-
cepciones hasta ese instante. Si se puede especificar qué decisión tomará un agente para
cada una de las posibles secuencias de percepciones, entonces se habrá explicado más
o menos todo lo que se puede decir de un agente. En términos matemáticos se puede de-
FUNCIÓN DEL AGENTE cir que el comportamiento del agente viene dado por la función del agente que proyecta
una percepción dada en una acción.
La función que describe el comportamiento de un agente se puede presentar en for-
ma de tabla; en la mayoría de los casos esta tabla sería muy grande (infinita a menos
que se limite el tamaño de la secuencia de percepciones que se quiera considerar). Dado
un agente, con el que se quiera experimentar, se puede, en principio, construir esta ta-
bla teniendo en cuenta todas las secuencias de percepción y determinando qué acción
lleva a cabo el agente en respuesta2. La tabla es, por supuesto, una caracterización ex-
terna del agente. Inicialmente, la función del agente para un agente artificial se imple-

2
Si el agente selecciona la acción de manera aleatoria, entonces sería necesario probar cada secuencia mu-
chas veces para identificar la probabilidad de cada acción. Se puede pensar que actuar de manera aleatoria
es ridículo, pero como se verá posteriormente puede ser muy inteligente.
 AGENTES INTELIGENTES 39

PROGRAMA DEL mentará mediante el programa del agente. Es importante diferenciar estas dos ideas.
AGENTE
La función del agente es una descripción matemática abstracta; el programa del agente
es una implementación completa, que se ejecuta sobre la arquitectura del agente.
Para ilustrar esta idea se utilizará un ejemplo muy simple, el mundo de la aspirado-
ra presentado en la Figura 2.2. Este mundo es tan simple que se puede describir todo lo
que en él sucede; es un mundo hecho a medida, para el que se pueden inventar otras va-
riaciones. Este mundo en particular tiene solamente dos localizaciones: cuadrícula A y
B. La aspiradora puede percibir en qué cuadrante se encuentra y si hay suciedad en él.
Puede elegir si se mueve hacia la izquierda, derecha, aspirar la suciedad o no hacer nada.
Una función muy simple para el agente vendría dada por: si la cuadrícula en la que
se encuentra está sucia, entonces aspirar, de otra forma cambiar de cuadrícula. Una
muestra parcial de la función del agente representada en forma de tabla aparece en la
Figura 2.3. Un programa de agente simple para esta función de agente se mostrará
posteriormente en la Figura 2.8.

A B

Figura 2.2 El mundo de la aspiradora con dos localizaciones solamente.

Secuencia de percepciones Acción

[A, Limpio] Derecha

[A, Sucio] Aspirar
[B, Limpio] Izquierda
[B, Sucio] Aspirar
[A, Limpio], [A, Limpio] Derecha
[A, Limpio], [A, Sucio] Aspirar
— —
— —
— —
[A, Limpio], [A, Limpio], [A, Limpio] Derecha
[A, Limpio], [A, Limpio], [A, Sucio] Aspirar
— —
— —
— —

Figura 2.3 Tabla parcial de una función de agente sencilla para el mundo de la aspiradora que se
muestra en la Figura 2.2.
40 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

Revisando la Figura 2.3, se aprecia que se pueden definir varios agentes para el mundo
de la aspiradora simplemente rellenando la columna de la derecha de formas distintas.
La pregunta obvia, entonces es: ¿cuál es la mejor forma de rellenar una tabla? En otras
palabras, ¿qué hace que un agente sea bueno o malo, inteligente o estúpido? Estas pre-
guntas se responden en la siguiente sección.
Antes de terminar esta sección, es necesario remarcar que la noción de agente es su-
puestamente una herramienta para el análisis de sistemas, y no una caracterización ab-
soluta que divida el mundo entre agentes y no agentes. Se puede ver una calculadora de
mano como un agente que elige la acción de mostrar «4» en la pantalla, dada la secuencia
de percepciones «2
2 ». Pero este análisis difícilmente puede mejorar nuestro
conocimiento acerca de las calculadoras.

2.2 Buen comportamiento:

el concepto de racionalidad
AGENTE RACIONAL Un agente racional es aquel que hace lo correcto; en términos conceptuales, cada elemento
de la tabla que define la función del agente se tendría que rellenar correctamente. Obvia-
mente, hacer lo correcto es mejor que hacer algo incorrecto, pero ¿qué significa hacer lo
correcto? Como primera aproximación, se puede decir que lo correcto es aquello que per-
mite al agente obtener un resultado mejor. Por tanto, se necesita determinar una forma de
medir el éxito. Ello, junto a la descripción del entorno y de los sensores y actuadores del
agente, proporcionará una especificación completa de la tarea que desempeña el agente.
Dicho esto, ahora es posible definir de forma más precisa qué significa la racionalidad.

Medidas de rendimiento
MEDIDAS DE Las medidas de rendimiento incluyen los criterios que determinan el éxito en el com-
RENDIMIENTO
portamiento del agente. Cuando se sitúa un agente en un medio, éste genera una secuencia
de acciones de acuerdo con las percepciones que recibe. Esta secuencia de acciones hace
que su hábitat pase por una secuencia de estados. Si la secuencia es la deseada, enton-
ces el agente habrá actuado correctamente. Obviamente, no hay una única medida
adecuada para todos los agentes. Se puede preguntar al agente por su opinión subjetiva
acerca de su propia actuación, pero muchos agentes serían incapaces de contestar, y otros
podrían engañarse a sí mismos3. Por tanto hay que insistir en la importancia de utilizar
medidas de rendimiento objetivas, que normalmente determinará el diseñador encarga-
do de la construcción del agente.
Si retomamos el ejemplo de la aspiradora de la sección anterior, se puede proponer
utilizar como medida de rendimiento la cantidad de suciedad limpiada en un período de

3
Los agentes humanos son conocidos en particular por su «acidez», hacen creer que no quieren algo des-
pués de no haberlo podido conseguir, por ejemplo, «Ah bueno, de todas formas no quería ese estúpido Pre-
mio Nobel».
 AGENTES INTELIGENTES 41

ocho horas. Con agentes racionales, por supuesto, se obtiene lo que se demanda. Un agen-
te racional puede maximizar su medida de rendimiento limpiando la suciedad, tirando
la basura al suelo, limpiándola de nuevo, y así sucesivamente. Una medida de rendimiento
más adecuada recompensaría al agente por tener el suelo limpio. Por ejemplo, podría ga-
nar un punto por cada cuadrícula limpia en cada período de tiempo (quizás habría que
incluir algún tipo de penalización por la electricidad gastada y el ruido generado). Como
regla general, es mejor diseñar medidas de utilidad de acuerdo con lo que se quiere para
el entorno, más que de acuerdo con cómo se cree que el agente debe comportarse.
La selección de la medida de rendimiento no es siempre fácil. Por ejemplo, la no-
ción de «suelo limpio» del párrafo anterior está basada en un nivel de limpieza medio a
lo largo del tiempo. Además, este nivel medio de limpieza se puede alcanzar de dos for-
mas diferentes, llevando a cabo una limpieza mediocre pero continua o limpiando en pro-
fundidad, pero realizando largos descansos. La forma más adecuada de hacerlo puede
venir dada por la opinión de un encargado de la limpieza profesional, pero en realidad
es una cuestión filosófica profunda con fuertes implicaciones. ¿Qué es mejor, una vida
temeraria con altos y bajos, o una existencia segura pero aburrida? ¿Qué es mejor, una
economía en la que todo el mundo vive en un estado de moderada pobreza o una en la
que algunos viven en la abundancia y otros son muy pobres? Estas cuestiones se dejan
como ejercicio para los lectores diligentes.

Racionalidad
La racionalidad en un momento determinado depende de cuatro factores:
• La medida de rendimiento que define el criterio de éxito.
• El conocimiento del medio en el que habita acumulado por el agente.
• Las acciones que el agente puede llevar a cabo.
• La secuencia de percepciones del agente hasta este momento.
DEFINICIÓN DE
AGENTE RACIONAL Esto nos lleva a la definición de agente racional:
En cada posible secuencia de percepciones, un agente racional deberá emprender aque-
lla acción que supuestamente maximice su medida de rendimiento, basándose en las evi-
dencias aportadas por la secuencia de percepciones y en el conocimiento que el agente
mantiene almacenado.
Considerando que el agente aspiradora limpia una cuadrícula si está sucia y se mueve a
la otra si no lo está (ésta es la función del agente que aparece en la tabla de la Figu-
ra 2.3), ¿se puede considerar racional? ¡Depende! Primero, se debe determinar cuál es
la medida de rendimiento, qué se conoce del entorno, y qué sensores y actuadores tiene
el agente. Si asumimos que:
• La medida de rendimiento premia con un punto al agente por cada recuadro lim-
pio en un período de tiempo concreto, a lo largo de una «vida» de 1.000 períodos.
• La «geografía» del medio se conoce a priori (Figura 2.2), pero que la distribución
de la suciedad y la localización inicial del agente no se conocen. Las cuadrículas
se mantienen limpias y aspirando se limpia la cuadrícula en que se encuentre el
agente. Las acciones Izquierda y Derecha mueven al agente hacia la izquierda y
42 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

derecha excepto en el caso de que ello pueda llevar al agente fuera del recinto, en
este caso el agente permanece donde se encuentra.
• Las únicas acciones permitidas son Izquierda, Derecha, Aspirar y NoOp (no ha-
cer nada).
• El agente percibe correctamente su localización y si esta localización contiene su-
ciedad.
Puede afirmarse que bajo estas circunstancias el agente es verdaderamente racional; el
rendimiento que se espera de este agente es por lo menos tan alto como el de cualquier
otro agente. El Ejercicio 2.4 pide que se pruebe este hecho.
Fácilmente se puede observar que el agente puede resultar irracional en circunstan-
cias diferentes. Por ejemplo, cuando toda la suciedad se haya eliminado el agente osci-
lará innecesariamente hacia delante y atrás; si la medida de rendimiento incluye una pe-
nalización de un punto por cada movimiento hacia la derecha e izquierda, la respuesta
del agente será pobre. Un agente más eficiente no hará nada si está seguro de que todas
las cuadrículas están limpias. Si una cuadrícula se ensucia de nuevo, el agente debe iden-
tificarlo en una de sus revisiones ocasionales y limpiarla. Si no se conoce la geografía
del entorno, el agente tendrá que explorarla y no quedarse parado en las cuadrículas A
y B. El Ejercicio 2.4 pide que se diseñen agentes para estos casos.

Omnisciencia, aprendizaje y autonomía

OMNISCIENCIA Es necesario tener cuidado al distinguir entre racionalidad y omnisciencia. Un agente
omnisciente conoce el resultado de su acción y actúa de acuerdo con él; sin embargo,
en realidad la omnisciencia no es posible. Considerando el siguiente ejemplo: estoy pa-
seando por los Campos Elíseos y veo un amigo al otro lado de la calle. No hay tráfico
alrededor y no tengo ningún compromiso, entonces, actuando racionalmente, comenzaría
a cruzar la calle. Al mismo tiempo, a 33.000 pies de altura, se desprende la puerta de un
avión4, y antes de que termine de cruzar al otro lado de la calle me encuentro aplastado.
¿Fue irracional cruzar la calle? Sería de extrañar que en mi nota necrológica apareciera
«Un idiota intentando cruzar la calle».
Este ejemplo muestra que la racionalidad no es lo mismo que la perfección. La ra-
cionalidad maximiza el rendimiento esperado, mientras la perfección maximiza el resul-
tado real. Alejarse de la necesidad de la perfección no es sólo cuestión de hacer justicia
con los agentes. El asunto es que resulta imposible diseñar un agente que siempre lleve
a cabo, de forma sucesiva, las mejores acciones después de un acontecimiento, a menos
que se haya mejorado el rendimiento de las bolas de cristal o las máquinas de tiempo.
La definición propuesta de racionalidad no requiere omnisciencia, ya que la elección
racional depende sólo de la secuencia de percepción hasta la fecha. Es necesario ase-
gurase de no haber permitido, por descuido, que el agente se dedique decididamente a
llevar a cabo acciones poco inteligentes. Por ejemplo, si el agente no mirase a ambos la-
dos de la calle antes de cruzar una calle muy concurrida, entonces su secuencia de per-

4
Véase N. Henderson, «New door latches urged for Boeing 747 jumbo jets» (es urgente dotar de nuevas
cerraduras a las puertas de los Boeing jumbo 747), Washington Post, 24 de agosto de 1989.
 AGENTES INTELIGENTES 43

cepción no le indicaría que se está acercando un gran camión a gran velocidad. ¿La
definición de racionalidad nos está indicando que está bien cruzar la calle? ¡Todo lo con-
trario! Primero, no sería racional cruzar la calle sólo teniendo esta secuencia de per-
cepciones incompleta: el riesgo de accidente al cruzarla sin mirar es demasiado grande.
Segundo, un agente racional debe elegir la acción de «mirar» antes de intentar cruzar la
calle, ya que el mirar maximiza el rendimiento esperado. Llevar a cabo acciones con la
intención de modificar percepciones futuras, en ocasiones proceso denominado reco-
RECOPILACIÓN DE
INFORMACIÓN pilación de información, es una parte importante de la racionalidad y se comenta en
profundidad en el Capítulo 16. Un segundo ejemplo de recopilación de información lo
EXPLORACIÓN proporciona la exploración que debe llevar a cabo el agente aspiradora en un medio ini-
cialmente desconocido.
La definición propuesta implica que el agente racional no sólo recopile información,
APRENDIZAJE sino que aprenda lo máximo posible de lo que está percibiendo. La configuración ini-
cial del agente puede reflejar un conocimiento preliminar del entorno, pero a medida que
el agente adquiere experiencia éste puede modificarse y aumentar. Hay casos excepcio-
nales en los que se conoce totalmente el entorno a priori. En estos casos, el agente no
necesita percibir y aprender; simplemente actúa de forma correcta. Por supuesto, estos
agentes son muy frágiles. Considérese el caso del humilde escarabajo estercolero. Des-
pués de cavar su nido y depositar en él su huevos, tomó una bola de estiércol de una pila
cercana para tapar su entrada. Si durante el trayecto se le quita la bola, el escarabajo con-
tinuará su recorrido y hará como si estuviera tapando la entrada del nido, sin tener la bola
y sin darse cuanta de ello. La evolución incorporó una suposición en la conducta del
escarabajo, y cuando se viola, el resultado es un comportamiento insatisfactorio. La avis-
pa cavadora es un poco más inteligente. La avispa hembra cavará una madriguera, saldrá
de ella, picará a una oruga y la llevará a su madriguera, se introducirá en la madriguera
para comprobar que todo está bien, arrastrará la oruga hasta el fondo y pondrá sus
huevos. La oruga servirá como fuente de alimento cuando los huevos se abran. Hasta
ahora todo bien, pero si un entomólogo desplaza la oruga unos centímetros fuera cuan-
do la avispa está revisando la situación, ésta volverá a la etapa de «arrastre» que figura
en su plan, y continuará con el resto del plan sin modificación alguna, incluso después
de que se intervenga para desplazar la oruga. La avispa cavadora no es capaz de apren-
der que su plan innato está fallando, y por tanto no lo cambiará.
Los agentes con éxito dividen las tareas de calcular la función del agente en tres
períodos diferentes: cuando se está diseñando el agente, y están los diseñadores encar-
gados de realizar algunos de estos cálculos; cuando está pensando en la siguiente opera-
ción, el agente realiza más cálculos; y cuando está aprendiendo de la experiencia, el agente
lleva a cabo más cálculos para decidir cómo modificar su forma de comportarse.
AUTONOMÍA Se dice que un agente carece de autonomía cuando se apoya más en el conocimiento
inicial que le proporciona su diseñador que en sus propias percepciones. Un agente ra-
cional debe ser autónomo, debe saber aprender a determinar cómo tiene que compensar
el conocimiento incompleto o parcial inicial. Por ejemplo, el agente aspiradora que
aprenda a prever dónde y cuándo aparecerá suciedad adicional lo hará mejor que otro
que no aprenda. En la práctica, pocas veces se necesita autonomía completa desde el
comienzo: cuando el agente haya tenido poca o ninguna experiencia, tendrá que actuar
de forma aleatoria a menos que el diseñador le haya proporcionado ayuda. Así, de la
44 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

misma forma que la evolución proporciona a los animales sólo los reactivos necesarios
para que puedan sobrevivir lo suficiente para aprender por ellos mismos, sería razona-
ble proporcionar a los agentes que disponen de inteligencia artificial un conocimiento
inicial, así como de la capacidad de aprendizaje. Después de las suficientes experien-
cias interaccionando con el entorno, el comportamiento del agente racional será efecti-
vamente independiente del conocimiento que poseía inicialmente. De ahí, que la incor-
poración del aprendizaje facilite el diseño de agentes racionales individuales que tendrán
éxito en una gran cantidad de medios.

2.3 La naturaleza del entorno

Ahora que se tiene una definición de racionalidad, se está casi preparado para pensar en
la construcción de agentes racionales. Primero, sin embargo, hay que centrarse en los
ENTORNOS DE
TRABAJO
entornos de trabajo, que son esencialmente los «problemas» para los que los agentes
racionales son las «soluciones». Para ello se comienza mostrando cómo especificar un
entorno de trabajo, ilustrando el proceso con varios ejemplos. Posteriormente se mos-
trará que el entorno de trabajo ofrece diferentes posibilidades, de forma que cada una
de las posibilidades influyen directamente en el diseño del programa del agente.

Especificación del entorno de trabajo

En la discusión de la racionalidad de un agente aspiradora simple, hubo que especificar
las medidas de rendimiento, el entorno, y los actuadores y sensores del agente. Todo ello
forma lo que se llama el entorno de trabajo, para cuya denominación se utiliza el
REAS acrónimo REAS (Rendimiento, Entorno, Actuadores, Sensores). En el diseño de un agen-
te, el primer paso debe ser siempre especificar el entorno de trabajo de la forma más
completa posible.
El mundo de la aspiradora fue un ejemplo simple; considérese ahora un problema
más complejo: un taxista automático. Este ejemplo se utilizará a lo largo del capítulo.
Antes de alarmar al lector, conviene aclarar que en la actualidad la construcción de un
taxi automatizado está fuera del alcance de la tecnología actual. Véase en la página 31
la descripción de un robot conductor que ya existe en la actualidad, o lea las actas de la
conferencia Intelligent Transportation Systems. La tarea de conducir un automóvil, en
su totalidad, es extremadamente ilimitada. No hay límite en cuanto al número de nue-
vas combinaciones de circunstancias que pueden surgir (por esta razón se eligió esta ac-
tividad en la presente discusión). La Figura 2.4 resume la descripción REAS para el en-
torno de trabajo del taxi. El próximo párrafo explica cada uno de sus elementos en más
detalle.
Primero, ¿cuál es el entorno de trabajo en el que el taxista automático aspira a con-
ducir? Dentro de las cualidades deseables que debería tener se incluyen el que llegue
al destino correcto; que minimice el consumo de combustible; que minimice el tiem-
po de viaje y/o coste; que minimice el número de infracciones de tráfico y de moles-
tias a otros conductores; que maximice la seguridad, la comodidad del pasajero y el
 AGENTES INTELIGENTES 45

Medidas de
Tipo de agente Entorno Actuadores Sensores
rendimiento
Taxista Seguro, rápido, Carreteras, Dirección, Cámaras, sónar,
legal, viaje otro tráfico, acelerador, velocímetro,
confortable, peatones, freno, señal, GPS, tacómetro,
maximización clientes bocina, visualizador de
del beneficio visualizador la aceleración,
sensores del
motor, teclado

Figura 2.4 Descripción REAS del entorno de trabajo de un taxista automático.

beneficio. Obviamente, alguno de estos objetivos entran en conflicto por lo que habrá
que llegar a acuerdos.
Siguiente, ¿cuál es el entorno en el que se encontrará el taxi? Cualquier taxista debe
estar preparado para circular por distintas carreteras, desde caminos rurales y calles ur-
banas hasta autopistas de 12 carriles. En las carreteras se pueden encontrar con tráfico,
peatones, animales, obras, coches de policía, charcos y baches. El taxista también tie-
ne que comunicarse tanto con pasajeros reales como potenciales. Hay también elecciones
opcionales. El taxi puede operar en California del Sur, donde la nieve es raramente un
problema, o en Alaska, donde raramente no lo es. Puede conducir siempre por la de-
recha, o puede ser lo suficientemente flexible como para que circule por la izquierda
cuando se encuentre en el Reino Unido o en Japón. Obviamente, cuanto más restringi-
do esté el entorno, más fácil será el problema del diseño.
Los actuadores disponibles en un taxi automático serán más o menos los mismos que
los que tiene a su alcance un conductor humano: el control del motor a través del acele-
rador y control sobre la dirección y los frenos. Además, necesitará tener una pantalla de
visualización o un sintetizador de voz para responder a los pasajeros, y quizás algún me-
canismo para comunicarse, educadamente o de otra forma, con otros vehículos.
Para alcanzar sus objetivos en el entorno en el que circula, el taxi necesita saber dónde
está, qué otros elementos están en la carretera, y a qué velocidad circula. Sus sensores
básicos deben, por tanto, incluir una o más cámaras de televisión dirigidas, un velocí-
metro y un tacómetro. Para controlar el vehículo adecuadamente, especialmente en las
curvas, debe tener un acelerador; debe conocer el estado mecánico del vehículo, de forma
que necesitará sensores que controlen el motor y el sistema eléctrico. Debe tener
instrumentos que no están disponibles para un conductor medio: un sistema de posicio-
namiento global vía satélite (GPS) para proporcionarle información exacta sobre su
posición con respecto a un mapa electrónico, y sensores infrarrojos o sonares para
detectar las distancias con respecto a otros coches y obstáculos. Finalmente, necesitará
un teclado o micrófono para que el pasajero le indique su destino.
La Figura 2.5 muestra un esquema con los elementos REAS básicos para diferentes
clases de agentes adicionales. Más ejemplos aparecerán en el Ejercicio 2.5. Puede
sorprender a algunos lectores que se incluya en la lista de tipos de agente algunos pro-
gramas que operan en la totalidad del entorno artificial definido por las entradas del
teclado y los caracteres impresos en el monitor. «Seguramente», nos podamos pregun-
46 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

Medidas de
Tipo de agente Entorno Actuadores Sensores
rendimiento
Sistema de Pacientes sanos, Pacientes, Visualizar Teclado para
diagnóstico reducir costes, hospital, preguntas, la entrada de
médico demandas personal pruebas, síntomas,
diagnósticos, conclusiones,
tratamientos, respuestas de
casos pacientes

Sistema de Categorización Conexión con el Visualizar la Matriz de pixels

análisis de de imagen satélite en órbita categorización de colores
imágenes de correcta de una escena
satélites

Robot para la Porcentaje de Cinta Brazo y mano Cámara, sensor

selección de componentes transportadora articulados angular
componentes clasificados en con
los cubos componentes,
correctos cubos

Controlador de Maximizar la Refinería, Válvulas, Temperatura,

una refinería pureza, operadores bombas, presión,
producción y calentadores, sensores
seguridad monitores químicos

Tutor de inglés Maximizar la Conjunto de Visualizar los Teclado de

interactivo puntuación de estudiantes, ejercicios, entrada
los estudiantes agencia sugerencias,
en los exámenes examinadora correcciones

Figura 2.5 Ejemplos de tipos de agentes y sus descripciones REAS.

tar, «¿este no es un entorno real, verdad?». De hecho, lo que importa no es la distinción

entre un medio «real» y «artificial», sino la complejidad de la relación entre el com-
portamiento del agente, la secuencia de percepción generada por el medio y la medida
de rendimiento. Algunos entornos «reales» son de hecho bastante simples. Por ejemplo,
un robot diseñado para inspeccionar componentes según pasan por una cinta transpor-
tadora puede hacer uso de varias suposiciones simples: que la cinta siempre estará
iluminada, que conocerá todos los componentes que circulen por la cinta, y que hay
solamente dos acciones (aceptar y rechazar).
AGENTES SOFTWARE En contraste, existen algunos agentes software (o robots software o softbots) en en-
SOFTBOTS
tornos ricos y prácticamente ilimitados. Imagine un softbot diseñado para pilotar el si-
mulador de vuelo de un gran avión comercial. El simulador constituye un medio muy
detallado y complejo que incluye a otros aviones y operaciones de tierra, y el agente
software debe elegir, en tiempo real, una de entre un amplio abanico de posibilidades.
O imagine un robot diseñado para que revise fuentes de información en Internet y para
que muestre aquellas que sean interesantes a sus clientes. Para lograrlo, deberá poseer
cierta habilidad en el procesamiento de lenguaje natural, tendrá que aprender qué es lo
que le interesa a cada cliente, y tendrá que ser capaz de cambiar sus planes dinámica-
 AGENTES INTELIGENTES 47

mente, por ejemplo, cuando se interrumpa la conexión con una fuente de información o
cuando aparezca una nueva. Internet es un medio cuya complejidad rivaliza con la del
mundo físico y entre cuyos habitantes se pueden incluir muchos agentes artificiales.

Propiedades de los entornos de trabajo

El rango de los entornos de trabajo en los que se utilizan técnicas de IA es obviamente
muy grande. Sin embargo, se puede identificar un pequeño número de dimensiones en
las que categorizar estos entornos. Estas dimensiones determinan, hasta cierto punto, el
diseño más adecuado para el agente y la utilización de cada una de las familias principales
de técnicas en la implementación del agente. Primero se enumeran la dimensiones, y
después se analizan varios entornos de trabajo para ilustrar estas ideas. Las definiciones
dadas son informales; capítulos posteriores proporcionan definiciones más precisas y
ejemplos de cada tipo de entorno.
TOTALMENTE
OBSEVABLE • Totalmente observable vs. parcialmente observable.
Si los sensores del agente le proporcionan acceso al estado completo del medio
en cada momento, entonces se dice que el entorno de trabajo es totalmente obser-
vable5. Un entorno de trabajo es, efectivamente, totalmente observable si los sen-
sores detectan todos los aspectos que son relevantes en la toma de decisiones; la
relevancia, en cada momento, depende de las medidas de rendimiento. Entornos
totalmente observables son convenientes ya que el agente no necesita mantener nin-
gún estado interno para saber qué sucede en el mundo. Un entorno puede ser par-
cialmente observable debido al ruido y a la existencia de sensores poco exactos o
porque los sensores no reciben información de parte del sistema, por ejemplo, un
agente aspiradora con sólo un sensor de suciedad local no puede saber si hay su-
ciedad en la otra cuadrícula, y un taxi automatizado no pude saber qué están pen-
sando otros conductores.
DETERMINISTA • Determinista vs. estocástico.
ESTOCÁSTICO
Si el siguiente estado del medio está totalmente determinado por el estado actual
y la acción ejecutada por el agente, entonces se dice que el entorno es determinista;
de otra forma es estocástico. En principio, un agente no se tiene que preocupar de
la incertidumbre en un medio totalmente observable y determinista. Sin embargo,
si el medio es parcialmente observable entonces puede parecer estocástico. Esto
es particularmente cierto si se trata de un medio complejo, haciendo difícil el man-
tener constancia de todos las aspectos observados. Así, a menudo es mejor pen-
sar en entornos deterministas o estocásticos desde el punto de vista del agente. El
agente taxi es claramente estocástico en este sentido, ya que no se puede predecir
el comportamiento del tráfico exactamente; más aún, una rueda se puede reventar
y un motor se puede gripar sin previo aviso. El mundo de la aspiradora es deter-

5
La primera edición de este libro utiliza los términos accesible e inaccesible en vez de total y parcialmen-
te observable; no determinista en vez de estocástico; y no episódico en vez de secuencial. La nueva ter-
minología es más consistente con el uso establecido.
48 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

minista, como ya se describió, pero las variaciones pueden incluir elementos es-
tocásticos como la aparición de suciedad aleatoria y un mecanismo de succión
ineficiente (Ejercicio 2.12). Si el medio es determinista, excepto para las acciones
ESTRATÉGICO de otros agentes, decimos que el medio es estratégico.
EPISÓDICO • Episódico vs. secuencial6.
SECUENCIAL
En un entorno de trabajo episódico, la experiencia del agente se divide en episo-
dios atómicos. Cada episodio consiste en la percepción del agente y la realización
de una única acción posterior. Es muy importante tener en cuenta que el siguien-
te episodio no depende de las acciones que se realizaron en episodios previos. En
los medios episódicos la elección de la acción en cada episodio depende sólo del
episodio en sí mismo. Muchas tareas de clasificación son episódicas. Por ejem-
plo, un agente que tenga que seleccionar partes defectuosas en una cadena de mon-
taje basa sus decisiones en la parte que está evaluando en cada momento, sin tener
en cuenta decisiones previas; más aún, a la decisión presente no le afecta el que
la próxima fase sea defectuosa. En entornos secuenciales, por otro lado, la deci-
sión presente puede afectar a decisiones futuras. El ajedrez y el taxista son
secuenciales: en ambos casos, las acciones que se realizan a corto plazo pueden
tener consecuencias a largo plazo. Los medios episódicos son más simples que los
secuenciales porque la gente no necesita pensar con tiempo.
ESTÁTICO • Estático vs. dinámico.
DINAMICO
Si el entorno puede cambiar cuando el agente está deliberando, entonces se dice
que el entorno es dinámico para el agente; de otra forma se dice que es estático.
Los medios estáticos son fáciles de tratar ya que el agente no necesita estar
pendiente del mundo mientras está tomando una decisión sobre una acción, ni
necesita preocuparse sobre el paso del tiempo. Los medios dinámicos, por el con-
trario, están preguntando continuamente al agente qué quiere hacer; si no se ha
decidido aún, entonces se entiende que ha tomado la decisión de no hacer nada.
Si el entorno no cambia con el paso del tiempo, pero el rendimiento del agente cam-
SEMIDINÁMICO bia, entonces se dice que el medio es semidinámico. El taxista es claramente
dinámico: tanto los otros coches como el taxi se están moviendo mientras el
algoritmo que guía la conducción indica qué es lo próximo a hacer. El ajedrez, cuan-
do se juega con un reloj, es semideterminista. Los crucigramas son estáticos.
DISCRETO • Discreto vs. continuo.
CONTINUO
La distinción entre discreto y continuo se puede aplicar al estado del medio, a la
forma en la que se maneja el tiempo y a las percepciones y acciones del agente.
Por ejemplo, un medio con estados discretos como el del juego del ajedrez tiene
un número finito de estados distintos. El ajedrez tiene un conjunto discreto de
percepciones y acciones. El taxista conduciendo define un estado continuo y un
problema de tiempo continuo: la velocidad y la ubicación del taxi y de los otros
vehículos pasan por un rango de valores continuos de forma suave a lo largo del

6
La palabra «secuencial» se utiliza también en el campo de la informática como antónimo de «paralelo».
Los dos significados no están relacionados.
 AGENTES INTELIGENTES 49

tiempo. Las conducción del taxista es también continua (ángulo de dirección, etc.).
Las imágenes captadas por cámaras digitales son discretas, en sentido estricto, pero
se tratan típicamente como representaciones continuas de localizaciones e inten-
sidades variables.
AGENTE INDIVIDUAL • Agente individual vs. multiagente.
MULTIAGENTE
La distinción entre el entorno de un agente individual y el de un sistema mul-
tiagente puede parecer suficientemente simple. Por ejemplo, un agente resol-
viendo un crucigrama por sí mismo está claramente en un entorno de agente
individual, mientras que un agente que juega al ajedrez está en un entorno con
dos agentes. Sin embargo hay algunas diferencias sutiles. Primero, se ha descrito
que una entidad puede percibirse como un agente, pero no se ha explicado qué
entidades se deben considerar agentes. ¿Tiene el agente A (por ejemplo el agen-
te taxista) que tratar un objeto B (otro vehículo) como un agente, o puede tra-
tarse méramente como un objeto con un comportamiento estocástico, como las
olas de la playa o las hojas que mueve el viento? La distinción clave está en iden-
tificar si el comportamiento de B está mejor descrito por la maximización de una
medida de rendimiento cuyo valor depende del comportamiento de A. Por
ejemplo, en el ajedrez, la entidad oponente B intenta maximizar su medida de
rendimiento, la cual, según las reglas, minimiza la medida de rendimiento del
COMPETITIVO agente A. Por tanto, el ajedrez es un entorno multiagente competitivo. Por otro
lado, en el medio definido por el taxista circulando, el evitar colisiones maxi-
miza la medida de rendimiento de todos los agentes, así pues es un entorno mul-
COOPERATIVO tiagente parcialmente cooperativo. Es también parcialmente competitivo ya
que, por ejemplo, sólo un coche puede ocupar una plaza de aparcamiento. Los
problemas en el diseño de agentes que aparecen en los entornos multiagente son
a menudo bastante diferentes de los que aparecen en entornos con un único agen-
te; por ejemplo, la comunicación a menudo emerge como un comportamiento
racional en entornos multiagente; en algunos entornos competitivos parcial-
mente observables el comportamiento estocástico es racional ya que evita las
dificultades de la predicción.

Como es de esperar, el caso más complejo es el parcialmente observable, estocástico,

secuencial, dinámico, continuo y multiagente. De hecho, suele suceder que la mayoría
de las situaciones reales son tan complejas que sería discutible clasificarlas como real-
mente deterministas. A efectos prácticos, se deben tratar como estocásticas. Un taxista
circulando es un problema, complejo a todos los efectos.
La Figura 2.6 presenta las propiedades de un número de entornos familiares. Hay
que tener en cuenta que las respuestas no están siempre preparadas de antemano. Por
ejemplo, se ha presentado el ajedrez como totalmente observable; en sentido estricto, esto
es falso porque ciertas reglas que afectan al movimiento de las torres, el enroque y a mo-
vimientos por repetición requieren que se recuerden algunos hechos sobre la historia del
juego que no están reflejados en el estado del tablero. Estas excepciones, por supuesto,
no tienen importancia si las comparamos con aquellas que aparecen en el caso del
taxista, el tutor de inglés, o el sistema de diagnóstico médico.
50 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

Entornos de trabajo Observable Determinista Episódico Estático Discreto Agentes

Crucigrama Totalmente Determinista Secuencial Estático Discreto Individual
Ajedrez con reloj Totalmente Estratégico Secuencial Semi Discreto Multi

Póker Parcialmente Estratégico Secuencial Estático Discreto Multi

Backgammon Totalmente Estocástico Secuencial Estático Discreto Multi

Taxi circulando Parcialmente Estocástico Secuencial Dinámico Continuo Multi

Diagnóstico médico Parcialmente Estocástico Secuencial Dinámico Continuo Individual

Análisis de imagen Totalmente Determinista Episódico Semi Continuo Individual

Robot clasificador Parcialmente Estocástico Episódico Dinámico Continuo Individual

Controlador de refinería Parcialmente Estocástico Secuencial Dinámico Continuo Individual

Tutor interactivo de inglés Parcialmente Estocástico Secuencial Dinámico Discreto Multi

Figura 2.6 Ejemplos de entornos de trabajo y sus características.

Otras entradas de la tabla dependen de cómo se haya definido el entorno de trabajo.

Se ha definido el sistema de diagnóstico médico como un único agente porque no es
rentable modelar el proceso de la enfermedad en un paciente como un agente; pero incluso
el sistema de diagnóstico médico podría necesitar tener en cuenta a pacientes recalci-
trantes y empleados escépticos, de forma que el entorno podría tener un aspecto mul-
tiagente. Más aún, el diagnóstico médico es episódico si se concibe como proporcionar
un diagnóstico a partir de una lista de síntomas; el problema es secuencial si ello trae
consigo la propuesta de una serie de pruebas, un proceso de evaluación a lo largo del
tratamiento, y demás aspectos. Muchos entornos son, también, episódicos si se obser-
van desde un nivel de abstracción más alto que el de las acciones individuales del agen-
te. Por ejemplo, un torneo de ajedrez consiste en una secuencia de juegos; cada juego
es un episodio, pero (a la larga) la contribución de los movimientos en una partida al re-
sultado general que obtenga el agente no se ve afectada por los movimientos realizados
en la partida anterior. Por otro lado, las decisiones tomadas en una partida concreta son
ciertamente de tipo secuencial.
El repositorio de código asociado a este libro (aima.cs.berkeley.edu) incluye la
implementación de un número de entornos, junto con un simulador de entornos de pro-
pósito general que sitúa uno o más agentes en un entorno simulado, observa su com-
portamiento a lo largo del tiempo, y los evalúa de acuerdo con una medida de rendimiento
dada. Estos experimentos no sólo se han realizado para un medio concreto, sino que se
CLASE DE ENTORNOS han realizado con varios problemas obtenidos de una clase de entornos. Por ejemplo,
para evaluar un taxista en un tráfico simulado, sería interesante hacer varias simulacio-
nes con diferente tipo de tráfico, claridad y condiciones atmosféricas. Si se diseña un
agente para un escenario concreto, se pueden sacar ventajas de las propiedades especí-
ficas de ese caso en particular, pero puede no identificarse un buen diseño para condu-
GENERADOR cir en general. Por esta razón, el repositorio de código también incluye un generador
DE ENTORNOS
de entornos para cada clase de medios que selecciona hábitats particulares (con ciertas
posibilidades) en los que ejecutar los agentes. Por ejemplo, el generador de un entorno
 AGENTES INTELIGENTES 51

para un agente aspiradora inicializa el patrón de suciedad y la localización del agente

de forma aleatoria. Después, es interesante evaluar la eficacia media del agente en el con-
texto de la clase del entorno. Un agente racional para una clase de entorno maximiza el
rendimiento medio. Los Ejercicios del 2.7 al 2.12 guían el proceso de desarrollo de una
clase de entornos y la evaluación de varios agentes.

2.4 Estructura de los agentes

Hasta este momento se ha hablado de los agentes describiendo su conducta, la acción
que se realiza después de una secuencia de percepciones dada. Ahora, se trata de cen-
trarse en el núcleo del problema y hablar sobre cómo trabajan internamente. El trabajo
PROGRAMA
DEL AGENTE de la IA es diseñar el programa del agente que implemente la función del agente que
proyecta las percepciones en las acciones. Se asume que este programa se ejecutará en
ARQUITECTURA algún tipo de computador con sensores físicos y actuadores, lo cual se conoce como
arquitectura:
Agente  arquitectura
programa
Obviamente, el programa que se elija tiene que ser apropiado para la arquitectura. Si el
programa tiene que recomendar acciones como Caminar, la arquitectura tiene que tener
piernas. La arquitectura puede ser un PC común, o puede ser un coche robotizado con
varios computadores, cámaras, y otros sensores a bordo. En general, la arquitectura hace
que las percepciones de los sensores estén disponibles para el programa, ejecuta los pro-
gramas, y se encarga de que los actuadores pongan en marcha las acciones generadas.
La mayor parte de este libro se centra en el diseño de programas para agentes, aunque
los Capítulos 24 y 25 tratan sobre sensores y actuadores.

Programas de los agentes

Los programas de los agentes que se describen en este libro tienen la misma estructura:
reciben las percepciones actuales como entradas de los sensores y devuelven una acción
a los actuadores7. Hay que tener en cuenta la diferencia entre los programas de los agen-
tes, que toman la percepción actual como entrada, y la función del agente, que recibe la
percepción histórica completa. Los programas de los agentes reciben sólo la percepción
actual como entrada porque no hay nada más disponible en el entorno; si las acciones
del agente dependen de la secuencia completa de percepciones, el agente tendría que re-
cordar las percepciones.
Los programas de los agente se describirán con la ayuda de un sencillo lenguaje pseu-
docódigo que se define en el Apéndice B. El repositorio de código disponible en Inter-

7
Hay otras posibilidades para definir la estructura del programa para el agente; por ejemplo, los programas
para agentes pueden ser subrutinas que se ejecuten asincrónicamente en el entorno de trabajo. Cada una de
estas subrutinas tienen un puerto de entrada y salida y consisten en un bucle que interpreta las entradas del
puerto como percepciones y escribe acciones en el puerto de salida.
52 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

función AGENTE-DIRIGIDO-MEDIANTE TABLA(percepción) devuelve una acción

variables estáticas: percepciones, una secuencia, vacía inicialmente
tabla, una tabla de acciones, indexada por las secuencias de
percepciones, totalmente definida inicialmente

añadir la percepción al final de las percepciones

acción ; CONSULTA(percepciones, tabla)
devolver acción

Figura 2.7 El programa AGENTE-DIRIGIDO-MEDIANTE TABLA se invoca con cada nueva percepción
y devuelve una acción en cada momento. Almacena la secuencia de percepciones utilizando su pro-
pia estructura de datos privada.

net contiene implementaciones en lenguajes de programación reales. Por ejemplo, la

Figura 2.7 muestra un programa de agente muy sencillo que almacena la secuencia de
percepciones y después las compara con las secuencias almacenadas en la tabla de ac-
ciones para decidir qué hacer. La tabla representa explícitamente la función que define
el programa del agente. Para construir un agente racional de esta forma, los diseñado-
res deben realizar una tabla que contenga las acciones apropiadas para cada secuencia
posible de percepciones.
Intuitivamente se puede apreciar por qué la propuesta de dirección-mediante-tabla
para la construcción de agentes está condenada al fracaso. Sea P el conjunto de posibles
percepciones y T el tiempo de vida del agente (el número total de percepciones que re-
cibirá). La tabla de búsqueda contendrá Tt1
P
t entradas. Si consideramos ahora el taxi
automatizado: la entrada visual de una cámara individual es de 27 megabytes por segundo
(30 fotografías por segundo, 640  480 pixels con 24 bits de información de colores).
Lo cual genera una tabla de búsqueda con más de 10250.000.000.000 entradas por hora de con-
ducción. Incluso la tabla de búsqueda del ajedrez (un fragmento del mundo real peque-
ño y obediente) tiene por lo menos 10150 entradas. El tamaño exageradamente grande de
estas tablas (el número de átomos en el universo observable es menor que 1080) signifi-
ca que (a) no hay agente físico en este universo que tenga el espacio suficiente como para
almacenar la tabla, (b) el diseñador no tendrá tiempo para crear la tabla, (c) ningún agen-
te podría aprender todas las entradas de la tabla a partir de su experiencia, y (d) incluso
si el entorno es lo suficientemente simple para generar una tabla de un tamaño razona-
ble, el diseñador no tiene quien le asesore en la forma en la que rellenar la tabla.
A pesar de todo ello, el AGENTE-DIRIGIDO-MEDIANTE TABLA hace lo que nosotros que-
remos: implementa la función deseada para el agente. El desafío clave de la IA es en-
contrar la forma de escribir programas, que en la medida de lo posible, reproduzcan un
comportamiento racional a partir de una pequeña cantidad de código en vez de a partir
de una tabla con un gran número de entradas. Existen bastantes ejemplos que muestran
qué se puede hacer con éxito en otras áreas: por ejemplo, las grandes tablas de las raíces
cuadradas utilizadas por ingenieros y estudiantes antes de 1970 se han reemplazado por
un programa de cinco líneas que implementa el método de Newton en las calculadoras
electrónicas. La pregunta es, en el caso del comportamiento inteligente general, ¿puede
la IA hacer lo que Newton hizo con las raíces cuadradas? Creemos que la respuesta es
afirmativa.
 AGENTES INTELIGENTES 53

En lo que resta de esta sección se presentan los cuatro tipos básicos de programas
para agentes que encarnan los principios que subyacen en casi todos los sistemas inte-
ligentes.
• Agentes reactivos simples.
• Agentes reactivos basados en modelos.
• Agentes basados en objetivos.
• Agentes basados en utilidad.
Después se explica, en términos generales, cómo convertir todos ellos en agentes que
aprendan.

Agentes reactivos simples

AGENTE REACTIVO El tipo de agente más sencillo es el agente reactivo simple. Estos agentes seleccionan
SIMPLE
las acciones sobre la base de las percepciones actuales, ignorando el resto de las per-
cepciones históricas. Por ejemplo, el agente aspiradora cuya función de agente se pre-
sentó en la Figura 2.3 es un agente reactivo simple porque toma sus decisiones sólo con
base en la localización actual y si ésta está sucia. La Figura 2.8 muestra el programa para
este agente.
Hay que tener en cuenta que el programa para el agente aspiradora es muy pequeño
comparado con su tabla correspondiente. La reducción más clara se obtiene al ignorar
la historia de percepción, que reduce el número de posibilidades de 4T a sólo 4. Otra re-
ducción se basa en el hecho de que cuando la cuadrícula actual está sucia, la acción no
depende de la localización.
Imagínese que es el conductor del taxi automático. Si el coche que circula delante
frena, y las luces de freno se encienden, entonces lo advertiría y comenzaría a frenar. En
otras palabras, se llevaría a cabo algún tipo de procesamiento sobre las señales visuales
para establecer la condición que se llama «El coche que circula delante está frenando».
Esto dispara algunas conexiones establecidas en el programa del agente para que se eje-
REGLA DE cute la acción «iniciar frenado». Esta conexión se denomina regla de condición-acción8,
CONDICIÓN-ACCIÓN y se representa por
si el-coche-que-circula-delante-está-frenando entonces iniciar-frenada.

función AGENTE-ASPIRADORA-REACTIVO([localización, estado]) devuelve una acción

si estado  Sucio entonces devolver Aspirar

de otra forma, si localización  A entonces devolver Derecha
de otra forma, si localización  B entonces devolver Izquierda

Figura 2.8 Programa para el agente aspiradora de reactivo simple en el entorno definido por las
dos cuadrículas. Este programa implementa la función de agente presentada en la Figura 2.3.

8
También llamadas reglas de situación-acción, producciones, o reglas si-entonces.
54 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

Los humanos también tienen muchas de estas conexiones, algunas de las cuales son res-
puestas aprendidas (como en el caso de la conducción) y otras son reacciones innatas
(como parpadear cuando algo se acerca al ojo). A lo largo de esta obra, se estudiarán
diferentes formas en las que se pueden aprender e implementar estas conexiones.
El programa de la Figura 2.8 es específico para el entorno concreto de la aspirado-
ra. Una aproximación más general y flexible es la de construir primero un intérprete de
propósito general para reglas de condición-acción y después crear conjuntos de reglas
para entornos de trabajo específicos. La Figura 2.9 presenta la estructura de este programa
general de forma esquemática, mostrando cómo las reglas de condición-acción permi-
ten al agente generar la conexión desde las percepciones a las acciones. No se preocu-
pe si le parece trivial; pronto se complicará. Se utilizan rectángulos para denotar el estado
interno actual del proceso de toma de decisiones del agente y óvalos para representar la
información base utilizada en el proceso. El programa del agente, que es también muy
simple, se muestra en la Figura 2.10. La función INTERPRETAR-ENTRADA genera una
descripción abstracta del estado actual a partir de la percepción, y la función REGLA-COIN-
CIDENCIA devuelve la primera regla del conjunto de reglas que coincide con la descrip-
ción del estado dada. Hay que tener en cuenta que la descripción en términos de «reglas»

Agente Sensores

Cómo es el mundo

Medio ambiente
ahora

Reglas de condición-acción Qué acción debo

tomar ahora

Actuadores

Figura 2.9 Diagrama esquemático de un agente reactivo simple.

función AGENTE-REACTIVO-SIMPLE(percepción) devuelve una acción

estático: reglas, un conjunto de reglas condición-acción

estado ; INTERPRETAR-ENTRADA(percepción)
regla ; REGLA-COINCIDENCIA(estado, reglas)
acción ; REGLA-ACCIÓN[regla]
devolver acción

Figura 2.10 Un agente reactivo simple, que actúa de acuerdo a la regla cuya condición coincida
con el estado actual, definido por la percepción.
 AGENTES INTELIGENTES 55

y «coincidencias» es puramente conceptual; las implementaciones reales pueden ser tan

simples como colecciones de puertas lógicas implementando un circuito booleano.
Los agentes reactivos simples tienen la admirable propiedad de ser simples, pero
poseen una inteligencia muy limitada. El agente de la Figura 2.10 funcionará sólo si
se puede tomar la decisión correcta sobre la base de la percepción actual, lo cual es
posible sólo si el entorno es totalmente observable. Incluso el que haya una pequeña
parte que no se pueda observar puede causar serios problemas. Por ejemplo, la regla
de frenado dada anteriormente asume que la condición el-coche-que-circula-delante-
está-frenando se puede determinar a partir de la percepción actual (imagen de vídeo
actual) si el coche de enfrente tiene un sistema centralizado de luces de freno.
Desafortunadamente, los modelos antiguos tienen diferentes configuraciones de luces
traseras, luces de frenado, y de intermitentes, y no es siempre posible saber a partir de
una única imagen si el coche está frenando. Un agente reactivo simple conduciendo
detrás de un coche de este tipo puede frenar continuamente y de manera innecesaria,
o peor, no frenar nunca.
Un problema similar aparece en el mundo de la aspiradora. Supongamos que se eli-
mina el sensor de localización de un agente aspiradora reactivo simple, y que sólo tie-
ne un sensor de suciedad. Un agente de este tipo tiene sólo dos percepciones posibles:
[Sucio] y [Limpio]. Puede Aspirar cuando se encuentra con [Sucio]. ¿Qué debe hacer
cuando se encuentra con [Limpio]? Si se desplaza a la Izquierda se equivoca (siempre)
si está en la cuadrícula A, y si de desplaza a la Derecha se equivoca (siempre) si está en
la cuadrícula B. Los bucles infinitos son a menudo inevitables para los agentes reacti-
vos simples que operan en algunos entornos parcialmente observables.
Salir de los bucles infinitos es posible si los agentes pueden seleccionar sus accio-
ALEATORIO nes aleatoriamente. Por ejemplo, si un agente aspiradora percibe [Limpio], puede lan-
zar una moneda y elegir entre Izquierda y Derecha. Es fácil mostrar que el agente se
moverá a la otra cuadrícula en una media de dos pasos. Entonces, si la cuadrícula está
sucia, la limpiará y la tarea de limpieza se completará. Por tanto, un agente reactivo simple
con capacidad para elegir acciones de manera aleatoria puede mejorar los resultados que
proporciona un agente reactivo simple determinista.
En la Sección 2.3 se mencionó que un comportamiento aleatorio de un tipo adecua-
do puede resultar racional en algunos entornos multiagente. En entornos de agentes in-
dividuales, el comportamiento aleatorio no es normalmente racional. Es un truco útil que
ayuda a los agentes reactivos simples en algunas situaciones, pero en la mayoría de los
casos se obtendrán mejores resultados con agentes deterministas más sofisticados.

Agentes reactivos basados en modelos

La forma más efectiva que tienen los agentes de manejar la visibilidad parcial es alma-
cenar información de las partes del mundo que no pueden ver. O lo que es lo mismo,
ESTADO INTERNO el agente debe mantener algún tipo de estado interno que dependa de la historia perci-
bida y que de ese modo refleje por lo menos alguno de los aspectos no observables del
estado actual. Para el problema de los frenos, el estado interno no es demasiado exten-
so, sólo la fotografía anterior de la cámara, facilitando al agente la detección de dos lu-
ces rojas encendiéndose y apagándose simultáneamente a los costados del vehículo. Para
56 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

otros aspectos de la conducción, como un cambio de carril, el agente tiene que mante-
ner información de la posición del resto de los coches si no los puede ver.
La actualización de la información de estado interno según pasa el tiempo requiere
codificar dos tipos de conocimiento en el programa del agente. Primero, se necesita al-
guna información acerca de cómo evoluciona el mundo independientemente del agen-
te, por ejemplo, que un coche que está adelantando estará más cerca, detrás, que en un
momento inmediatamente anterior. Segundo, se necesita más información sobre cómo
afectan al mundo las acciones del agente, por ejemplo, que cuando el agente gire hacia
la derecha, el coche gira hacia la derecha o que después de conducir durante cinco mi-
nutos hacia el norte en la autopista se avanzan cinco millas hacia el norte a partir del pun-
to en el que se estaba cinco minutos antes. Este conocimiento acerca de «cómo funcio-
na el mundo», tanto si está implementado con un circuito booleano simple o con teorías
científicas completas, se denomina modelo del mundo. Un agente que utilice este mo-
AGENTE BASADO
EN MODELOS delo es un agente basado en modelos.

Sensores
Estado
Cómo evoluciona el mundo Cómo es el mundo
ahora

Medio ambiente
Qué efectos causan mis acciones

Reglas de condición-acción Qué acción debo

tomar ahora

Agente Actuadores

Figura 2.11 Un agente reactivo basado en modelos.

función AGENTE-REACTIVO-CON-ESTADO(percepción) devuelve una acción

estático: estado, una descripción actual del estado del mundo
reglas, un conjunto de reglas condición-acción
acción, la acción más reciente, inicialmente ninguna

estado ; ACTUALIZAR-ESTADO(estado, acción, percepción)

regla ; REGLA-COINCIDENCIA(estado, reglas)
acción ; REGLA-ACCIÓN[regla]
devolver acción

Figura 2.12 Un agente reactivo basado en modelos, que almacena información sobre el estado
actual del mundo utilizando un modelo interno. Después selecciona una acción de la misma forma
que el agente reactivo.
 AGENTES INTELIGENTES 57

La Figura 2.11 proporciona la estructura de un agente reactivo simple con estado in-
terno, muestra cómo la percepción actual se combina con el estado interno antiguo para
generar la descripción actualizada del estado actual. La Figura 2.12 muestra el progra-
ma del agente. La parte interesante es la correspondiente a la función Actualizar-Esta-
do, que es la responsable de la creación de la nueva descripción del estado interno. Ade-
más de interpretar la nueva percepción a partir del conocimiento existente sobre el
estado, utiliza información relativa a la forma en la que evoluciona el mundo para co-
nocer más sobre las partes del mundo que no están visibles; para ello debe conocer cuál
es el efecto de las acciones del agente sobre el estado del mundo. Los Capítulos 10 y 17
ofrecen ejemplos detallados.

Agentes basados en objetivos

El conocimiento sobre el estado actual del mundo no es siempre suficiente para decidir
qué hacer. Por ejemplo, en un cruce de carreteras, el taxista puede girar a la izquierda,
girar a la derecha o seguir hacia adelante. La decisión correcta depende de dónde quiere
ir el taxi. En otras palabras, además de la descripción del estado actual, el agente nece-
META sita algún tipo de información sobre su meta que describa las situaciones que son
deseables, por ejemplo, llegar al destino propuesto por el pasajero. El programa del agen-
te se puede combinar con información sobre los resultados de las acciones posibles (la
misma información que se utilizó para actualizar el estado interno en el caso del agen-
te reflexivo) para elegir las acciones que permitan alcanzar el objetivo. La Figura 2.13
muestra la estructura del agente basado en objetivos.
En algunas ocasiones, la selección de acciones basadas en objetivos es directa, cuan-
do alcanzar los objetivos es el resultado inmediato de una acción individual. En otras oca-

Sensores
Estado
Cómo es el mundo
Cómo evoluciona el mundo ahora
Medio ambiente

Qué pasará si realizo

Qué efectos causan mis acciones la acción A

Que acción debo

Objetivos llevar a cabo ahora

Agente Actuadores

Figura 2.13 Un agente basado en objetivos y basado en modelos, que almacena información del
estado del mundo así como del conjunto de objetivos que intenta alcanzar, y que es capaz de se-
leccionar la acción que eventualmente lo guiará hacia la consecución de sus objetivos.
58 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

siones, puede ser más complicado, cuando el agente tiene que considerar secuencias com-
plejas para encontrar el camino que le permita alcanzar el objetivo. Búsqueda (Capítu-
los del 3 al 6) y planificación (Capítulos 11 y 12) son los subcampos de la IA centra-
dos en encontrar secuencias de acciones que permitan a los agentes alcanzar sus metas.
Hay que tener en cuenta que la toma de decisiones de este tipo es fundamentalmen-
te diferente de las reglas de condición–acción descritas anteriormente, en las que hay que
tener en cuenta consideraciones sobre el futuro (como «¿qué pasará si yo hago esto y
esto?» y «¿me hará esto feliz?»). En los diseños de agentes reactivos, esta información
no está representada explícitamente, porque las reglas que maneja el agente proyectan
directamente las percepciones en las acciones. El agente reactivo frena cuando ve luces
de freno. Un agente basado en objetivos, en principio, puede razonar que si el coche que
va delante tiene encendidas las luces de frenado, está reduciendo su velocidad. Dada la
forma en la que el mundo evoluciona normalmente, la única acción que permite alcan-
zar la meta de no chocarse con otros coches, es frenar.
Aunque el agente basado en objetivos pueda parecer menos eficiente, es más flexi-
ble ya que el conocimiento que soporta su decisión está representado explícitamente y
puede modificarse. Si comienza a llover, el agente puede actualizar su conocimiento so-
bre cómo se comportan los frenos; lo cual implicará que todas las formas de actuar re-
levantes se alteren automáticamente para adaptarse a las nuevas circunstancias. Para el
agente reactivo, por otro lado, se tendrán que rescribir muchas reglas de condición-ac-
ción. El comportamiento del agente basado en objetivos puede cambiarse fácilmente para
que se dirija a una localización diferente. Las reglas de los agentes reactivos relaciona-
das con cuándo girar y cuándo seguir recto son válidas sólo para un destino concreto y
tienen que modificarse cada vez que el agente se dirija a cualquier otro lugar distinto.

Agentes basados en utilidad

Las metas por sí solas no son realmente suficientes para generar comportamiento de gran
calidad en la mayoría de los entornos. Por ejemplo, hay muchas secuencias de acciones
que llevarán al taxi a su destino (y por tanto a alcanzar su objetivo), pero algunas son
más rápidas, más seguras, más fiables, o más baratas que otras. Las metas sólo propor-
cionan una cruda distinción binaria entre los estados de «felicidad» y «tristeza», mien-
tras que una medida de eficiencia más general debería permitir una comparación entre
estados del mundo diferentes de acuerdo al nivel exacto de felicidad que el agente al-
cance cuando se llegue a un estado u otro. Como el término «felicidad» no suena muy
científico, la terminología tradicional utilizada en estos casos para indicar que se pre-
UTILIDAD fiere un estado del mundo a otro es que un estado tiene más utilidad que otro para el
agente9.
FUNCIÓN DE UTILIDAD Una función de utilidad proyecta un estado (o una secuencia de estados) en un nú-
mero real, que representa un nivel de felicidad. La definición completa de una función
de utilidad permite tomar decisiones racionales en dos tipos de casos en los que las me-
tas son inadecuadas. Primero, cuando haya objetivos conflictivos, y sólo se puedan al-

9
La palabra «utilidad» aquí se refiere a «la cualidad de ser útil».
 AGENTES INTELIGENTES 59

Sensores
Estado
Cómo es el mundo
Cómo evoluciona el mundo ahora

Medio ambiente
Qué efectos causan Qué pasará si realizo
mis acciones la acción A

Utilidad Estaré contento

en este estado

Qué acción debo

llevar a cabo ahora

Agente Actuadores

Figura 2.14 Un agente basado en utilidad y basado en modelos. Utiliza un modelo del mundo,
junto con una función de utilidad que calcula sus preferencias entre los estados del mundo. Des-
pués selecciona la acción que le lleve a alcanzar la mayor utilidad esperada, que se calcula haciendo
la media de todos los estados resultantes posibles, ponderado con la probabilidad del resultado.

canzar algunos de ellos (por ejemplo, velocidad y seguridad), la función de utilidad de-
termina el equilibrio adecuado. Segundo, cuando haya varios objetivos por los que se
pueda guiar el agente, y ninguno de ellos se pueda alcanzar con certeza, la utilidad pro-
porciona un mecanismo para ponderar la probabilidad de éxito en función de la impor-
tancia de los objetivos.
En el Capítulo 16, se mostrará cómo cualquier agente racional debe comportarse como
si tuviese una función de utilidad cuyo valor esperado tiene que maximizar. Por tanto,
un agente que posea una función de utilidad explícita puede tomar decisiones raciona-
les, y lo puede hacer con la ayuda de un algoritmo de propósito general que no dependa
de la función específica de utilidad a maximizar. De esta forma, la definición «global»
de racionalidad (identificando como racionales aquellas funciones de los agentes que pro-
porcionan el mayor rendimiento) se transforma en una restricción «local» en el diseño
de agentes racionales que se puede expresar con un simple programa.
La Figura 2.14 muestra la estructura de un agente basado en utilidad. En la Parte IV
aparecen programas de agentes basados en utilidad, donde se presentan agentes que to-
man decisiones y que deben trabajar con la incertidumbre inherente a los entornos par-
cialmente observables.

Agentes que aprenden

Se han descrito programas para agentes que poseen varios métodos para seleccionar ac-
ciones. Hasta ahora no se ha explicado cómo poner en marcha estos programas de agen-
tes. Turing (1950), en su temprano y famoso artículo, consideró la idea de programar
sus máquinas inteligentes a mano. Estimó cuánto tiempo podía llevar y concluyó que «Se-
60 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

ría deseable utilizar algún método más rápido». El método que propone es construir má-
quinas que aprendan y después enseñarlas. En muchas áreas de IA, éste es ahora el mé-
todo más adecuado para crear sistemas novedosos. El aprendizaje tiene otras ventajas,
como se ha explicado anteriormente: permite que el agente opere en medios inicialmente
desconocidos y que sea más competente que si sólo utilizase un conocimiento inicial.
En esta sección, se introducen brevemente las principales ideas en las que se basan los
agentes que aprenden. En casi todos los capítulos de este libro se comentan las posibi-
lidades y métodos de aprendizaje de tipos de agentes concretos. La Parte VI profundi-
za más en los algoritmos de aprendizaje en sí mismos.
Un agente que aprende se puede dividir en cuatro componentes conceptuales, tal y
ELEMENTO DE
APRENDIZAJE
como se muestra en la Figura 2.15. La distinción más importante entre el elemento de
aprendizaje y el elemento de actuación es que el primero está responsabilizado de hacer
ELEMENTO DE
ACTUACIÓN
mejoras y el segundo se responsabiliza de la selección de acciones externas. El elemento
de actuación es lo que anteriormente se había considerado como el agente completo:
recibe estímulos y determina las acciones a realizar. El elemento de aprendizaje se rea-
CRÍTICA limenta con las críticas sobre la actuación del agente y determina cómo se debe modi-
ficar el elemento de actuación para proporcionar mejores resultados en el futuro.
El diseño del elemento de aprendizaje depende mucho del diseño del elemento de
actuación. Cuando se intenta diseñar un agente que tenga capacidad de aprender, la pri-
mera cuestión a solucionar no es ¿cómo se puede enseñar a aprender?, sino ¿qué tipo de
elemento de actuación necesita el agente para llevar a cabo su objetivo, cuando haya
aprendido cómo hacerlo? Dado un diseño para un agente, se pueden construir los me-
canismos de aprendizaje necesarios para mejorar cada una de las partes del agente.
La crítica indica al elemento de aprendizaje qué tal lo está haciendo el agente con
respecto a un nivel de actuación fijo. La crítica es necesaria porque las percepciones por
sí mismas no prevén una indicación del éxito del agente. Por ejemplo, un programa de

Nivel de actuación

Crítica Sensores

retroalimentación
Medio ambiente

cambios
Elemento de Elemento
aprendizaje de actuación
conocimiento
objetivos a
aprender

Generador
de problemas

Agente Actuadores

Figura 2.15 Modelo general para agentes que aprenden.

 AGENTES INTELIGENTES 61

ajedrez puede recibir una percepción indicando que ha dado jaque mate a su oponente,
pero necesita tener un nivel de actuación que le indique que ello es bueno; la percepción
por sí misma no lo indica. Es por tanto muy importante fijar el nivel de actuación. Con-
ceptualmente, se debe tratar con él como si estuviese fuera del agente, ya que éste no
debe modificarlo para satisfacer su propio interés.
GENERADOR DE El último componente del agente con capacidad de aprendizaje es el generador de
PROBLEMAS
problemas. Es responsable de sugerir acciones que lo guiarán hacia experiencias nue-
vas e informativas. Lo interesante es que si el elemento de actuación sigue su camino,
puede continuar llevando a cabo las acciones que sean mejores, dado su conocimiento.
Pero si el agente está dispuesto a explorar un poco, y llevar a cabo algunas acciones que
no sean totalmente óptimas a corto plazo, puede descubrir acciones mejores a largo pla-
zo. El trabajo del generador de problemas es sugerir estas acciones exploratorias. Esto
es lo que los científicos hacen cuando llevan a cabo experimentos. Galileo no pensaba
que tirar piedras desde lo alto de una torre en Pisa tenía un valor por sí mismo. Él no tra-
taba de romper piedras ni de cambiar la forma de pensar de transeúntes desafortunados
que paseaban por el lugar. Su intención era adaptar su propia mente, para identificar una
teoría que definiese mejor el movimiento de los objetos.
Para concretar el diseño total, se puede volver a utilizar el ejemplo del taxi automa-
tizado. El elemento de actuación consiste en la colección de conocimientos y procedi-
mientos que tiene el taxi para seleccionar sus acciones de conducción. El taxi se pone
en marcha y circula utilizando este elemento de actuación. La crítica observa el mundo
y proporciona información al elemento de aprendizaje. Por ejemplo, después de que el
taxi se sitúe tres carriles hacia la izquierda de forma rápida, la crítica observa el lenguaje
escandaloso que utilizan otros conductores. A partir de esta experiencia, el elemento de
aprendizaje es capaz de formular una regla que indica que ésta fue una mala acción, y
el elemento de actuación se modifica incorporando la nueva regla. El generador de pro-
blemas debe identificar ciertas áreas de comportamiento que deban mejorarse y sugerir
experimentos, como probar los frenos en carreteras con tipos diferentes de superficies
y bajo condiciones distintas.
El elemento de aprendizaje puede hacer cambios en cualquiera de los componentes
de «conocimiento» que se muestran en los diagramas de agente (Figuras 2.9, 2.11, 2.13,
y 2.14). Los casos más simples incluyen el aprendizaje directo a partir de la secuencia
percibida. La observación de pares de estados sucesivos del entorno puede permitir que
el agente aprenda «cómo evoluciona el mundo», y la observación de los resultados de
sus acciones puede permitir que el agente aprenda «qué hacen sus acciones». Por ejem-
plo, si el taxi ejerce una cierta presión sobre los frenos cuando está circulando por una
carretera mojada, acto seguido conocerá cómo decelera el coche. Claramente, estas dos
tareas de aprendizaje son más difíciles si sólo existe una vista parcial del medio.
Las formas de aprendizaje mostradas en los párrafos precedentes no necesitan el ac-
ceso a niveles de actuación externo, de alguna forma, el nivel es el que se utiliza uni-
versalmente para hacer pronósticos de acuerdo con la experimentación. La situación es
ligeramente más compleja para un agente basado en utilidad que desee adquirir infor-
mación para crear su función de utilidad. Por ejemplo, se supone que el agente conduc-
tor del taxi no recibe propina de los pasajeros que han recorrido un trayecto de forma
incómoda debido a una mala conducción. El nivel de actuación externo debe informar
62 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

al agente de que la pérdida de propinas tiene una contribución negativa en su nivel de

actuación medio; entonces el agente puede aprender que «maniobras violentas no con-
tribuyen a su propia utilidad». De alguna manera, el nivel de actuación identifica parte
de las percepciones entrantes como recompensas (o penalizaciones) que generan una
respuesta directa en la calidad del comportamiento del agente. Niveles de actuación in-
tegrados como el dolor y el hambre en animales se pueden enmarcar en este contexto.
El Capítulo 21 discute estos asuntos.
En resumen, los agentes tienen una gran variedad de componentes, y estos compo-
nentes se pueden representar de muchas formas en los programas de agentes, por lo que,
parece haber una gran variedad de métodos de aprendizaje. Existe, sin embargo, una
visión unificada sobre un tema fundamental. El aprendizaje en el campo de los agentes
inteligentes puede definirse como el proceso de modificación de cada componente del
agente, lo cual permite a cada componente comportarse más en consonancia con la in-
formación que se recibe, lo que por tanto permite mejorar el nivel medio de actuación
del agente.

2.5 Resumen
En este capítulo se ha realizado un recorrido rápido por el campo de la IA, que se ha pre-
sentado como la ciencia del diseño de los agentes. Los puntos más importantes a tener
en cuenta son:
• Un agente es algo que percibe y actúa en un medio. La función del agente para
un agente especifica la acción que debe realizar un agente como respuesta a cual-
quier secuencia percibida.
• La medida de rendimiento evalúa el comportamiento del agente en un medio. Un
agente racional actúa con la intención de maximizar el valor esperado de la me-
dida de rendimiento, dada la secuencia de percepciones que ha observado hasta el
momento.
• Las especificaciones del entorno de trabajo incluyen la medida de rendimiento,
el medio externo, los actuadores y los sensores. El primer paso en el diseño de un
agente debe ser siempre la especificación, tan completa como sea posible, del en-
torno de trabajo.
• El entorno de trabajo varía según distintos parámetros. Pueden ser total o parcial-
mente visibles, deterministas o estocásticos, episódicos o secuenciales, estáticos
o dinámicos, discretos o continuos, y formados por un único agente o por varios
agentes.
• El programa del agente implementa la función del agente. Existe una gran va-
riedad de diseños de programas de agentes, y reflejan el tipo de información que
se hace explícita y se utiliza en el proceso de decisión. Los diseños varían en efi-
ciencia, solidez y flexibilidad. El diseño apropiado del programa del agente de-
pende en gran medida de la naturaleza del medio.
• Los gentes reactivos simples responden directamente a las percepciones, mien-
tras que los agentes reactivos basados en modelos mantienen un estado interno
 AGENTES INTELIGENTES 63

que les permite seguir el rastro de aspectos del mundo que no son evidentes según
las percepciones actuales. Los agentes basados en objetivos actúan con la inten-
ción de alcanzar sus metas, y los agentes basados en utilidad intentan maximizar
su «felicidad» deseada.
• Todos los agentes pueden mejorar su eficacia con la ayuda de mecanismos de
aprendizaje.

NOTAS BIBLIOGRÁFICAS E HISTÓRICAS

El papel central de la acción en la inteligencia (la noción del razonamiento práctico)
se remonta por lo menos a la obra Nicomachean Ethics de Aristóteles. McCarthy
(1958) trató también el tema del razonamiento práctico en su influyente artículo
Programs with Common Sense. Los campos de la robótica y la teoría de control tienen
interés, por su propia naturaleza, en la construcción de agentes físicos. El concepto
CONTROLADOR de un controlador, en el ámbito de la teoría de control, es idéntico al de un agente en
IA. Quizá sorprendentemente, la IA se ha concentrado durante la mayor parte de su
historia en componentes aislados de agentes (sistemas que responden a preguntas,
demostración de teoremas, sistemas de visión, y demás) en vez de en agentes comple-
tos. La discusión sobre agentes que se presenta en el libro de Genesereth y Nilsson (1987)
fue una influyente excepción. El concepto de agente en sí está aceptado ampliamente
ahora en el campo y es un tema central en libros recientes (Poole et al., 1998; Nilsson,
1998).
El Capítulo 1 muestra las raíces del concepto de racionalidad en la Filosofía y la Eco-
nomía. En la IA, el concepto tuvo un interés periférico hasta mediados de los 80, don-
de comenzó a suscitar muchas discusiones sobre los propios fundamentos técnicos del
campo. Un artículo de Jon Doyle (1983) predijo que el diseño de agentes racionales po-
dría llegar a ser la misión central de la IA, mientras otras áreas populares podrían sepa-
rarse dando lugar a nuevas disciplinas.
Es muy importante tener muy en cuenta las propiedades del medio y sus conse-
cuencias cuando se realiza el diseño de los agentes racionales ya que forma parte de la
tradición ligada a la teoría de control [por ejemplo los sistemas de control clásicos (Dorf
y Bishop, 1999) manejan medios deterministas y totalmente observables; el control óp-
timo estocástico (Kumar y Varaiya, 1986) maneja medios parcialmente observables y
estocásticos y un control híbrido (Henzinger y Sastry, 1998) maneja entornos que con-
tienen elementos discretos y continuos]. La distinción entre entornos totalmente y par-
cialmente observables es también central en la literatura sobre programación dinámi-
ca desarrollada en el campo de la investigación operativa (Puterman, 1994), como se
comentará en el Capítulo 17.
Los agentes reactivos fueron los primeros modelos para psicólogos conductistas como
Skinner (1953), que intentó reducir la psicología de los organismos estrictamente a co-
rrespondencias entrada/salida o estímulo/respuesta. La evolución del behaviourismo
hacia el funcionalismo en el campo de la psicología, que estuvo, al menos de forma par-
cial, dirigida por la aplicación de la metáfora del computador a los agentes (Putnam, 1960;
Lewis, 1966) introdujo el estado interno del agente en el nuevo escenario. La mayor par-
64 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

te del trabajo realizado en el campo de la IA considera que los agentes reactivos puros
con estado interno son demasiado simples para ser muy influyentes, pero los trabajos
de Rosenschein (1985) y Brooks (1986) cuestionan esta hipótesis (véase el Capítulo 25).
En los últimos años, se ha trabajado intensamente para encontrar algoritmos eficientes
capaces de hacer un buen seguimiento de entornos complejos (Hamscher et al., 1992).
El programa del Agente Remoto que controla la nave espacial Deep Space One (descrito
en la página 27) es un admirable ejemplo concreto (Muscettola et al., 1998; Jonsson et
al., 2000).
Los agentes basados en objetivos están presentes tanto en las referencias de Aristó-
teles sobre el razonamiento práctico como en los primeros artículos de McCarthy sobre
IA lógica. El robot Shakey (Fikes y Nilsson, 1971; Nilsson, 1984) fue el primer robot
construido como un agente basado en objetivos. El análisis lógico completo de un agen-
te basado en objetivos aparece en Genesereth y Nilsson (1987), y Shoham (1993) ha
desarrollado una metodología de programación basada en objetivos llamada programa-
ción orientada a agentes.
La perspectiva orientada a objetivos también predomina en la psicología cogniti-
va tradicional, concretamente en el área de la resolución de problemas, como se mues-
tra tanto en el influyente Human Problem Solving (Newell y Simon, 1972) como en
los últimos trabajos de Newell (1990). Los objetivos, posteriormente definidos como
deseos (generales) y las intenciones (perseguidas en un momento dado), son funda-
mentales en la teoría de agentes desarrollada por Bratman (1987). Esta teoría ha sido
muy influyente tanto en el entendimiento del lenguaje natural como en los sistemas
multiagente.
Horvitz et al. (1988) sugieren específicamente el uso de la maximización de la uti-
lidad esperada concebida racionalmente como la base de la IA. El texto de Pearl (1988)
fue el primero en IA que cubrió las teorías de la probabilidad y la utilidad en profundi-
dad; su exposición de métodos prácticos de razonamiento y toma de decisiones con in-
certidumbre fue, posiblemente, el factor individual que más influyó en el desarrollo de
los agentes basados en utilidad en los 90 (véase la Parte V).
El diseño general de agentes que aprenden representado en la Figura 2.15 es un clá-
sico de la literatura sobre aprendizaje automático (Buchanan et al., 1978; Mitchell,
1997). Ejemplos de diseños, implementados en programas, se remontan, como poco, has-
ta los programas que aprendían a jugar al ajedrez de Arthur Samuel (1959, 1967). La
Parte VI está dedicada al estudio en profundidad de los agentes que aprenden.
El interés en los agentes y en el diseño de agentes ha crecido rápidamente en los úl-
timos años, en parte por la expansión de Internet y la necesidad observada de desarro-
llar softbots (robots software) automáticos y móviles (Etzioni y Weld, 1994). Artículos
relevantes pueden encontrarse en Readings in Agents (Huhns y Singh, 1998) y Funda-
tions of Rational Agency (Wooldridge y Rao, 1999). Multiagent Systems (Weiss, 1999)
proporciona una base sólida para muchos aspectos del diseño de agentes. Conferencias
dedicadas a agentes incluyen la International Conference on Autonomous Agents, la In-
ternational Workshop on Agent Theories, Architectures, and Languages, y la Interna-
tional Conference on Multiagent Systems. Finalmente, Dung Beetle Ecology (Hanski y
Cambefort, 1991) proporciona gran cantidad de información interesante sobre el com-
portamiento de los escarabajos estercoleros.
 AGENTES INTELIGENTES 65

EJERCICIOS
2.1 Defina con sus propias palabras los siguientes términos: agente, función de agente,
programa de agente, racionalidad, autonomía, agente reactivo, agente basado en modelo,
agente basado en objetivos, agente basado en utilidad, agente que aprende.
2.2 Tanto la medida de rendimiento como la función de utilidad miden la eficiencia del
agente. Explique la diferencia entre los dos conceptos.
2.3 Este ejercicio explora las diferencias entre las funciones de los agentes y los programas
de los agentes.
a) ¿Puede haber más de un programa de agente que implemente una función de
agente dada? Proponga un ejemplo, o muestre por qué una no es posible.
b) ¿Hay funciones de agente que no se pueden implementar con algún programa
de agente?
c) Dada una arquitectura máquina, ¿implementa cada programa de agente exacta-
mente una función de agente?
d) Dada una arquitectura con n bits de almacenamiento, ¿cuántos posibles pro-
gramas de agente diferentes puede almacenar?
2.4 Examínese ahora la racionalidad de varias funciones de agentes aspiradora.
a) Muestre que la función de agente aspiradora descrita en la Figura 2.3 es real-
mente racional bajo la hipótesis presentada en la página 36.
b) Describa una función para un agente racional cuya medida de rendimiento mo-
dificada deduzca un punto por cada movimiento. ¿Requiere el correspondiente
programa de agente estado interno?
c) Discuta posibles diseños de agentes para los casos en los que las cuadrículas lim-
pias puedan ensuciarse y la geografía del medio sea desconocida. ¿Tiene senti-
do que el agente aprenda de su experiencia en estos casos? ¿Si es así, qué debe
aprender?
2.5 Identifique la descripción REAS que define el entorno de trabajo para cada uno de
los siguientes agentes:
a) Robot que juega al fútbol;
b) Agente para comprar libros en Internet;
c) Explorador autónomo de Marte;
d) Asistente matemático para la demostración de teoremas.
2.6 Para cada uno de los tipos de agente enumerados en el Ejercicio 2.5, caracterice el
medio de acuerdo con las propiedades dadas en la Sección 2.3, y seleccione un diseño de
agente adecuado.
Los siguientes ejercicios están relacionados con la implementación de entornos y agen-
tes para el mundo de la aspiradora.
2.7 Implemente un simulador que determine la medida de rendimiento para el entorno
del mundo de la aspiradora descrito en la Figura 2.2 y especificado en la página 36. La
implementación debe ser modular, de forma que los sensores, actuadores, y las caracte-
rísticas del entorno (tamaño, forma, localización de la suciedad, etc.) puedan modificar-
66 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

se fácilmente. (Nota: hay implementaciones disponibles en el repositorio de Internet que

pueden ayudar a decidir qué lenguaje de programación y sistema operativo seleccionar).

2.8 Implemente un agente reactivo simple para el entorno de la aspiradora del Ejercicio
2.7. Ejecute el simulador del entorno con este agente para todas las configuraciones ini-
ciales posibles de suciedad y posiciones del agente. Almacene la puntuación de la actua-
ción del agente para cada configuración y la puntuación media global.

2.9 Considere una versión modificada del entorno de la aspiradora del Ejercicio 2.7, en
el que se penalice al agente con un punto en cada movimiento.
a) ¿Puede un agente reactivo simple ser perfectamente racional en este medio? Ex-
plíquese.
b) ¿Qué sucedería con un agente reactivo con estado? Diseñe este agente.
c) ¿Cómo se responderían las preguntas a y b si las percepciones proporcionan al
agente información sobre el nivel de suciedad/limpieza de todas las cuadrícu-
las del entorno?
2.10 Considere una versión modificada del entorno de la aspiradora del Ejercicio 2.7,
en el que la geografía del entorno (su extensión, límites, y obstáculos) sea desconocida,
así como, la disposición inicial de la suciedad. (El agente puede ir hacia arriba, abajo, así
como, hacia la derecha y a la izquierda.)
a) ¿Puede un agente reactivo simple ser perfectamente racional en este medio? Ex-
plíquese.
b) ¿Puede un agente reactivo simple con una función de agente aleatoria superar
a un agente reactivo simple? Diseñe un agente de este tipo y medir su rendimiento
en varios medios.
c) ¿Se puede diseñar un entorno en el que el agente con la función aleatoria ob-
tenga una actuación muy pobre? Muestre los resultados.
d) ¿Puede un agente reactivo con estado mejorar los resultados de un agente reac-
tivo simple? Diseñe un agente de este tipo y medir su eficiencia en distintos me-
dios. ¿Se puede diseñar un agente racional de este tipo?
2.11 Repítase el Ejercicio 2.10 para el caso en el que el sensor de localización sea
reemplazado por un sensor «de golpes» que detecte si el agente golpea un obstáculo o si
se sale fuera de los límites del entorno. Supóngase que el sensor de golpes deja de fun-
cionar. ¿Cómo debe comportarse el agente?

2.12 Los entornos de la aspiradora en los ejercicios anteriores han sido todos determi-
nistas. Discuta posibles programas de agentes para cada una de las siguientes versiones
estocásticas:
a) Ley de Murphy: el 25 por ciento del tiempo, la acción de Aspirar falla en la lim-
pieza del suelo si está sucio y deposita suciedad en el suelo si el suelo está lim-
pio. ¿Cómo se ve afectado el agente si el sensor de suciedad da una respuesta
incorrecta el diez por ciento de las veces?
b) Niño pequeño: en cada lapso de tiempo, cada recuadro limpio tiene un diez por
ciento de posibilidad de ensuciarse. ¿Puede identificar un diseño para un agen-
te racional en este caso?
 Resolver problemas
3 mediante búsqueda

En donde veremos cómo un agente puede encontrar una secuencia de acciones

que alcance sus objetivos, cuando ninguna acción simple lo hará.

Los agentes más simples discutidos en el Capítulo 2 fueron los agentes reactivos, los cua-
les basan sus acciones en una aplicación directa desde los estados a las acciones. Tales
agentes no pueden funcionar bien en entornos en los que esta aplicación sea demasiado
grande para almacenarla y que tarde mucho en aprenderla. Por otra parte, los agentes
basados en objetivos pueden tener éxito considerando las acciones futuras y lo deseable
de sus resultados.
AGENTE RESOLVENTE- Este capítulo describe una clase de agente basado en objetivos llamado agente re-
PROBLEMAS
solvente-problemas. Los agentes resolventes-problemas deciden qué hacer para en-
contrar secuencias de acciones que conduzcan a los estados deseables. Comenzamos de-
finiendo con precisión los elementos que constituyen el «problema» y su «solución», y
daremos diferentes ejemplos para ilustrar estas definiciones. Entonces, describimos
diferentes algoritmos de propósito general que podamos utilizar para resolver estos pro-
blemas y así comparar las ventajas de cada algoritmo. Los algoritmos son no informa-
dos, en el sentido que no dan información sobre el problema salvo su definición. El
Capítulo 4 se ocupa de los algoritmos de búsqueda informada, los que tengan cierta idea
de dónde buscar las soluciones.
Este capítulo utiliza los conceptos de análisis de algoritmos. Los lectores no fami-
liarizados con los conceptos de complejidad asintótica (es decir, notación O()) y la NP
completitud, debería consultar el Apéndice A.

3.1 Agentes resolventes-problemas

Se supone que los agentes inteligentes deben maximizar su medida de rendimiento. Como
mencionamos en el Capítulo 2, esto puede simplificarse algunas veces si el agente puede
68 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

elegir un objetivo y trata de satisfacerlo. Primero miraremos el porqué y cómo puede

hacerlo.
Imagine un agente en la ciudad de Arad, Rumanía, disfrutando de un viaje de vaca-
ciones. La medida de rendimiento del agente contiene muchos factores: desea mejorar
su bronceado, mejorar su rumano, tomar fotos, disfrutar de la vida nocturna, evitar re-
sacas, etcétera. El problema de decisión es complejo implicando muchos elementos y
por eso, lee cuidadosamente las guías de viaje. Ahora, supongamos que el agente tiene
un billete no reembolsable para volar a Bucarest al día siguiente. En este caso, tiene sen-
tido que el agente elija el objetivo de conseguir Bucarest. Las acciones que no alcanzan
Bucarest se pueden rechazar sin más consideraciones y el problema de decisión del agen-
te se simplifica enormemente. Los objetivos ayudan a organizar su comportamiento li-
mitando las metas que intenta alcanzar el agente. El primer paso para solucionar un pro-
FORMULACIÓN
DEL OBJETIVO
blema es la formulación del objetivo, basado en la situación actual y la medida de
rendimiento del agente.
Consideraremos un objetivo como un conjunto de estados del mundo (exactamente
aquellos estados que satisfacen el objetivo). La tarea del agente es encontrar qué secuencia
de acciones permite obtener un estado objetivo. Para esto, necesitamos decidir qué ac-
ciones y estados considerar. Si se utilizaran acciones del tipo «mueve el pie izquierdo
hacia delante» o «gira el volante un grado a la izquierda», probablemente el agente nun-
ca encontraría la salida del aparcamiento, no digamos por tanto llegar a Bucarest, por-
que a ese nivel de detalle existe demasiada incertidumbre en el mundo y habría dema-
FORMULACIÓN siados pasos en una solución. Dado un objetivo, la formulación del problema es el
DEL PROBLEMA
proceso de decidir qué acciones y estados tenemos que considerar. Discutiremos con más
detalle este proceso. Por ahora, suponemos que el agente considerará acciones del tipo
conducir de una ciudad grande a otra. Consideraremos los estados que corresponden a
estar en una ciudad1 determinada.
Ahora, nuestro agente ha adoptado el objetivo de conducir a Bucarest, y considera
a dónde ir desde Arad. Existen tres carreteras desde Arad, una hacia Sibiu, una a Timi-
soara, y una a Zerind. Ninguna de éstas alcanza el objetivo, y, a menos que el agente este
familiarizado con la geografía de Rumanía, no sabría qué carretera seguir2. En otras pa-
labras, el agente no sabrá cuál de las posibles acciones es mejor, porque no conoce lo
suficiente los estados que resultan al tomar cada acción. Si el agente no tiene conoci-
miento adicional, entonces estará en un callejón sin salida. Lo mejor que puede hacer
es escoger al azar una de las acciones.
Pero, supongamos que el agente tiene un mapa de Rumanía, en papel o en su me-
moria. El propósito del mapa es dotar al agente de información sobre los estados en los
que podría encontrarse, así como las acciones que puede tomar. El agente puede usar esta
información para considerar los siguientes estados de un viaje hipotético por cada una
de las tres ciudades, intentando encontrar un viaje que llegue a Bucarest. Una vez que

1
Observe que cada uno de estos «estados» se corresponde realmente a un conjunto de estados del mundo,
porque un estado del mundo real especifica todos los aspectos de realidad. Es importante mantener en men-
te la distinción entre estados del problema a resolver y los estados del mundo.
2
Suponemos que la mayoría de los lectores están en la misma situación y pueden fácilmente imaginarse cómo
de desorientado está nuestro agente. Pedimos disculpas a los lectores rumanos quienes no pueden aprove-
charse de este recurso pedagógico.
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 69

ha encontrado un camino en el mapa desde Arad a Bucarest, puede alcanzar su objeti-

vo, tomando las acciones de conducir que corresponden con los tramos del viaje. En
general, un agente con distintas opciones inmediatas de valores desconocidos puede
decidir qué hacer, examinando las diferentes secuencias posibles de acciones que le con-
duzcan a estados de valores conocidos, y entonces escoger la mejor secuencia.
BÚSQUEDA Este proceso de hallar esta secuencia se llama búsqueda. Un algoritmo de búsque-
SOLUCIÓN
da toma como entrada un problema y devuelve una solución de la forma secuencia de
acciones. Una vez que encontramos una solución, se procede a ejecutar las acciones que
EJECUCIÓN ésta recomienda. Esta es la llamada fase de ejecución. Así, tenemos un diseño simple
de un agente «formular, buscar, ejecutar», como se muestra en la Figura 3.1. Después
de formular un objetivo y un problema a resolver, el agente llama al procedimiento de
búsqueda para resolverlo. Entonces, usa la solución para guiar sus acciones, haciendo
lo que la solución le indica como siguiente paso a hacer —generalmente, primera ac-
ción de la secuencia— y procede a eliminar este paso de la secuencia. Una vez ejecuta-
da la solución, el agente formula un nuevo objetivo.
Primero describimos el proceso de formulación del problema, y después dedicare-
mos la última parte del capítulo a diversos algoritmos para la función BÚSQUEDA. En este
capítulo no discutiremos las funciones ACTUALIZAR-ESTADO y FORMULAR-OBJETIVO.
Antes de entrar en detalles, hagamos una breve pausa para ver dónde encajan los
agentes resolventes de problemas en la discusión de agentes y entornos del Capítulo 2.
El agente diseñado en la Figura 3.1 supone que el entorno es estático, porque la for-
mulación y búsqueda del problema se hace sin prestar atención a cualquier cambio que
puede ocurrir en el entorno. El agente diseñado también supone que se conoce el esta-
do inicial; conocerlo es fácil si el entorno es observable. La idea de enumerar «las lí-

función AGENTE-SENCILLO-RESOLVENTE-PROBLEMAS(percepción) devuelve una acción

entradas: percepción, una percepción
estático: sec, una secuencia de acciones, vacía inicialmente
estado, una descripción del estado actual del mundo
objetivo, un objetivo, inicialmente nulo
problema, una formulación del problema
estado ← ACTUALIZAR-ESTADO(estado, percepción)
si sec está vacía entonces hacer
objetivo ← FORMULAR-OBJETIVO(estado)
problema ← FORMULAR-PROBLEMA(estado,objetivo)
sec ← BÚSQUEDA(problema)
acción ← PRIMERO(secuencia)
sec ← RESTO(secuencia)
devolver acción

Figura 3.1 Un sencillo agente resolvente de problemas. Primero formula un objetivo y un pro-
blema, busca una secuencia de acciones que deberían resolver el problema, y entonces ejecuta las
acciones una cada vez. Cuando se ha completado, formula otro objetivo y comienza de nuevo. No-
temos que cuando se ejecuta la secuencia, se ignoran sus percepciones: se supone que la solución
encontrada trabajará bien.
70 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

neas de acción alternativas» supone que el entorno puede verse como discreto. Final-
mente, y más importante, el agente diseñado supone que el entorno es determinista.
Las soluciones a los problemas son simples secuencias de acciones, así que no pueden
manejar ningún acontecimiento inesperado; además, las soluciones se ejecutan sin
prestar atención a las percepciones. Los agentes que realizan sus planes con los ojos
cerrados, por así decirlo, deben estar absolutamente seguros de lo que pasa (los teóri-
LAZO ABIERTO cos de control lo llaman sistema de lazo abierto, porque ignorar las percepciones rom-
pe el lazo entre el agente y el entorno). Todas estas suposiciones significan que trata-
mos con las clases más fáciles de entornos, razón por la que este capítulo aparece tan
pronto en el libro. La Sección 3.6 echa una breve ojeada sobre lo que sucede cuando
relajamos las suposiciones de observancia y de determinismo. Los Capítulos 12 y 17
entran más en profundidad.

Problemas y soluciones bien definidos

PROBLEMA Un problema puede definirse, formalmente, por cuatro componentes:
ESTADO INICIAL • El estado inicial en el que comienza el agente. Por ejemplo, el estado inicial para
nuestro agente en Rumanía se describe como En(Arad).
• Una descripción de las posibles acciones disponibles por el agente. La formula-
FUNCIÓN SUCESOR ción3 más común utiliza una función sucesor. Dado un estado particular x, SU-
CESOR-FN(x) devuelve un conjunto de pares ordenados
acción, sucesor, donde cada
acción es una de las acciones legales en el estado x y cada sucesor es un estado
que puede alcanzarse desde x, aplicando la acción. Por ejemplo, desde el estado
En(Arad), la función sucesor para el problema de Rumanía devolverá
{
Ir(Sibiu), En(Sibiu),
Ir(Timisoara), En(Timisoara),
Ir(Zerind), En(Zerind)}
ESPACIO DE ESTADOS Implícitamente el estado inicial y la función sucesor definen el espacio de esta-
dos del problema (el conjunto de todos los estados alcanzables desde el estado ini-
cial). El espacio de estados forma un grafo en el cual los nodos son estados y los
arcos entre los nodos son acciones. (El mapa de Rumanía que se muestra en la Fi-
gura 3.2 puede interpretarse como un grafo del espacio de estados si vemos cada
carretera como dos acciones de conducir, una en cada dirección). Un camino en
CAMINO
el espacio de estados es una secuencia de estados conectados por una secuencia
de acciones.
TEST OBJETIVO • El test objetivo, el cual determina si un estado es un estado objetivo. Algunas ve-
ces existe un conjunto explícito de posibles estados objetivo, y el test simplemente
comprueba si el estado es uno de ellos. El objetivo del agente en Rumanía es el
conjunto {En(Bucarest)}. Algunas veces el objetivo se especifica como una pro-
piedad abstracta más que como un conjunto de estados enumerados explícitamente.
Por ejemplo, en el ajedrez, el objetivo es alcanzar un estado llamado «jaque mate»,
donde el rey del oponente es atacado y no tiene escapatoria.

3
Una formulación alternativa utiliza un conjunto de operadores que pueden aplicarse a un estado para ge-
nerar así los sucesores.
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 71

Oradea
71
Neamt

Zerind 87
75 151
Iasi
Arad
140
92
Sibiu Fagaras
99
118
Vaslui
80
Rimnicu Vilcea
Timisoara
142
111 Pitesti 211
Lugoj 97
70 98
85 Hirsova
Mehadia 146 101 Urziceni
75 138 86
Bucarest
Dobreta 120
90
Craiova Eforie
Giurgiu

Figura 3.2 Un mapa de carreteras simplificado de parte de Rumanía.

COSTO DEL CAMINO • Una función costo del camino que asigna un costo numérico a cada camino. El
agente resolvente de problemas elige una función costo que refleje nuestra medida
de rendimiento. Para el agente que intenta llegar a Bucarest, el tiempo es esencial,
así que el costo del camino puede describirse como su longitud en kilómetros. En
este capítulo, suponemos que el costo del camino puede describirse como la suma
de los costos de las acciones individuales a lo largo del camino. El costo indivi-
COSTO INDIVIDUAL
dual de una acción a que va desde un estado x al estado y se denota por c(x,a,y).
Los costos individuales para Rumanía se muestran en la Figura 3.2 como las dis-
tancias de las carreteras. Suponemos que los costos son no negativos4.
Los elementos anteriores definen un problema y pueden unirse en una estructura de da-
tos simple que se dará como entrada al algoritmo resolvente del problema. Una solución
de un problema es un camino desde el estado inicial a un estado objetivo. La calidad de
SOLUCIÓN ÓPTIMA la solución se mide por la función costo del camino, y una solución óptima tiene el cos-
to más pequeño del camino entre todas las soluciones.

Formular los problemas

En la sección anterior propusimos una formulación del problema de ir a Bucarest en
términos de estado inicial, función sucesor, test objetivo y costo del camino. Esta
formulación parece razonable, a pesar de omitir muchos aspectos del mundo real. Para

4
Las implicaciones de costos negativos se exploran en el Ejercicio 3.17.
72 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

comparar la descripción de un estado simple, hemos escogido, En(Arad), para un viaje

real por el país, donde el estado del mundo incluye muchas cosas: los compañeros de
viaje, lo que está en la radio, el paisaje, si hay algunos policías cerca, cómo está de le-
jos la parada siguiente, el estado de la carretera, el tiempo, etcétera. Todas estas consi-
deraciones se dejan fuera de nuestras descripciones del estado porque son irrelevantes
para el problema de encontrar una ruta a Bucarest. Al proceso de eliminar detalles de
ABSTRACCIÓN una representación se le llama abstracción.
Además de abstraer la descripción del estado, debemos abstraer sus acciones. Una
acción de conducir tiene muchos efectos. Además de cambiar la localización del vehí-
culo y de sus ocupantes, pasa el tiempo, consume combustible, genera contaminación,
y cambia el agente (como dicen, el viaje ilustra). En nuestra formulación, tenemos en
cuenta solamente el cambio en la localización. También, hay muchas acciones que omi-
tiremos: encender la radio, mirar por la ventana, el retraso de los policías, etcétera. Y
por supuesto, no especificamos acciones a nivel de «girar la rueda tres grados a la iz-
quierda».
¿Podemos ser más precisos para definir los niveles apropiados de abstracción? Pien-
se en los estados y las acciones abstractas que hemos elegido y que se corresponden con
grandes conjuntos de estados detallados del mundo y de secuencias detalladas de acciones.
Ahora considere una solución al problema abstracto: por ejemplo, la trayectoria de Arad
a Sibiu a Rimnicu Vilcea a Pitesti a Bucarest. Esta solución abstracta corresponde a una
gran cantidad de trayectorias más detalladas. Por ejemplo, podríamos conducir con la
radio encendida entre Sibiu y Rimnicu Vilcea, y después lo apagamos para el resto del
viaje. La abstracción es válida si podemos ampliar cualquier solución abstracta a una
solución en el mundo más detallado; una condición suficiente es que para cada estado
detallado de «en Arad», haya una trayectoria detallada a algún estado «en Sibiu», etcé-
tera. La abstracción es útil si al realizar cada una de las acciones en la solución es más
fácil que en el problema original; en este caso pueden ser realizadas por un agente que
conduce sin búsqueda o planificación adicional. La elección de una buena abstracción
implica quitar tantos detalles como sean posibles mientras que se conserve la validez y
se asegure que las acciones abstractas son fáciles de realizar. Si no fuera por la capaci-
dad de construir abstracciones útiles, los agentes inteligentes quedarían totalmente ab-
sorbidos por el mundo real.

3.2 Ejemplos de problemas

La metodología para resolver problemas se ha aplicado a un conjunto amplio de entor-
nos. Enumeramos aquí algunos de los más conocidos, distinguiendo entre problemas de
PROBLEMA DE
JUGUETE juguete y del mundo-real. Un problema de juguete se utiliza para ilustrar o ejercitar
los métodos de resolución de problemas. Éstos se pueden describir de forma exacta y
concisa. Esto significa que diferentes investigadores pueden utilizarlos fácilmente para
PROBLEMA DEL
MUNDO REAL comparar el funcionamiento de los algoritmos. Un problema del mundo-real es aquel
en el que la gente se preocupa por sus soluciones. Ellos tienden a no tener una sola des-
cripción, pero nosotros intentaremos dar la forma general de sus formulaciones.
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 73

Problemas de juguete
El primer ejemplo que examinaremos es el mundo de la aspiradora, introducido en el
Capítulo 2. (Véase Figura 2.2.) Éste puede formularse como sigue:
• Estados: el agente está en una de dos localizaciones, cada una de las cuales pue-
de o no contener suciedad. Así, hay 2
22  8 posibles estados del mundo.
• Estado inicial: cualquier estado puede designarse como un estado inicial.
• Función sucesor: ésta genera los estados legales que resultan al intentar las tres
acciones (Izquierda, Derecha y Aspirar). En la Figura 3.3 se muestra el espacio
de estados completo.
• Test objetivo: comprueba si todos los cuadrados están limpios.
• Costo del camino: cada costo individual es 1, así que el costo del camino es el
número de pasos que lo compone.
Comparado con el mundo real, este problema de juguete tiene localizaciones discretas,
suciedad discreta, limpieza fiable, y nunca se ensucia una vez que se ha limpiado. ( En
la Sección 3.6 relajaremos estas suposiciones). Una cosa a tener en cuenta es que el es-
tado está determinado por la localización del agente y por las localizaciones de la su-
ciedad. Un entorno grande con n localizaciones tiene n 2n estados.

D
I D

I
A A

D D
I D I D

I I
A A
A A
D
I D

A A

Figura 3.3 Espacio de estados para el mundo de la aspiradora. Los arcos denotan las acciones: I
 Izquierda, D  Derecha, A  Aspirar.

8-PUZZLE El 8-puzle, la Figura 3.4 muestra un ejemplo, consiste en un tablero de 3
3 con ocho
fichas numeradas y un espacio en blanco. Una ficha adyacente al espacio en blanco pue-
de deslizarse a éste. La meta es alcanzar el estado objetivo especificado, tal como se mues-
tra a la derecha de la figura. La formulación estándar es como sigue:
• Estados: la descripción de un estado especifica la localización de cada una de las
ocho fichas y el blanco en cada uno de los nueve cuadrados.
74 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

• Estado inicial: cualquier estado puede ser un estado inicial. Nótese que cualquier
objetivo puede alcanzarse desde exactamente la mitad de los estados iniciales po-
sibles (Ejercicio 3.4).
• Función sucesor: ésta genera los estados legales que resultan de aplicar las cua-
tro acciones (mover el blanco a la Izquierda, Derecha, Arriba y Abajo).
• Test objetivo: comprueba si el estado coincide con la configuración objetivo que
se muestra en la Figura 3.4. (son posibles otras configuraciones objetivo).
• Costo del camino: el costo de cada paso del camino tiene valor 1, así que el cos-
to del camino es el número de pasos.
¿Qué abstracciones se han incluido? Las acciones se han abstraído a los estados ini-
ciales y finales, ignorando las localizaciones intermedias en donde se deslizan los
bloques. Hemos abstraído acciones como la de sacudir el tablero cuando las piezas no
se pueden mover, o extraer las piezas con un cuchillo y volverlas a poner. Nos dejan con
una descripción de las reglas del puzle que evitan todos los detalles de manipulaciones
físicas.

7 2 4 1 2

5 6 3 4 5

8 3 1 6 7 8

Estado Inicial Estado Objetivo

Figura 3.4 Un ejemplo típico del 8-puzle.

PIEZAS DESLIZANTES El 8-puzle pertenece a la familia de puzles con piezas deslizantes, los cuales a menu-
do se usan como problemas test para los nuevos algoritmos de IA. Esta clase general
se conoce por ser NP completa, así que no esperamos encontrar métodos perceptible-
mente mejores (en el caso peor) que los algoritmos de búsqueda descritos en este
capítulo y en el siguiente. El 8-puzle tiene 9!2  181,440 estados alcanzables y se
resuelve fácilmente. El 15 puzle (sobre un tablero de 4
4) tiene alrededor de 1,3 tri-
llones de estados, y configuraciones aleatorias pueden resolverse óptimamente en pocos
milisegundos por los mejores algoritmos de búsqueda. El 24 puzle (sobre un tablero de
5
5) tiene alrededor de 1025 estados, y configuraciones aleatorias siguen siendo ab-
solutamente difíciles de resolver de manera óptima con los computadores y algoritmos
actuales.
PROBLEMA 8-REINAS
El objetivo del problema de las 8-reinas es colocar las ocho reinas en un tablero de
ajedrez de manera que cada reina no ataque a ninguna otra. (Una reina ataca alguna pie-
za si está en la misma fila, columna o diagonal.) La Figura 3.5 muestra una configura-
ción que no es solución: la reina en la columna de más a la derecha está atacando a la
reina de arriba a la izquierda.
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 75

Figura 3.5 Casi una solución del problema de las 8-reinas. (La solución se deja como ejercicio.)

Aunque existen algoritmos eficientes específicos para este problema y para el problema
general de las n reinas, sigue siendo un problema test interesante para los algoritmos de
FORMULACIÓN búsqueda. Existen dos principales formulaciones. Una formulación incremental que im-
INCREMENTAL
plica a operadores que aumentan la descripción del estado, comenzando con un estado
FORMULACIÓN
vacío; para el problema de las 8-reinas, esto significa que cada acción añade una reina
COMPLETA DE al estado. Una formulación completa de estados comienza con las ocho reinas en el
ESTADOS
tablero y las mueve. En cualquier caso, el coste del camino no tiene ningún interés porque
solamente cuenta el estado final. La primera formulación incremental que se puede
intentar es la siguiente:
• Estados: cualquier combinación de cero a ocho reinas en el tablero es un estado.
• Estado inicial: ninguna reina sobre el tablero.
• Función sucesor: añadir una reina a cualquier cuadrado vacío.
• Test objetivo: ocho reinas sobre el tablero, ninguna es atacada.
En esta formulación, tenemos 64  63  57  3
1014 posibles combinaciones a in-
vestigar. Una mejor formulación deberá prohibir colocar una reina en cualquier cuadra-
do que esté realmente atacado:
• Estados: son estados, la combinación de n reinas (0  n  8), una por columna
desde la columna más a la izquierda, sin que una reina ataque a otra.
• Función sucesor: añadir una reina en cualquier cuadrado en la columna más a la
izquierda vacía tal que no sea atacada por cualquier otra reina.
Esta formulación reduce el espacio de estados de las 8-reinas de 3
1014 a 2.057, y las
soluciones son fáciles de encontrar. Por otra parte, para 100 reinas la formulación ini-
cial tiene 10400 estados mientras que las formulaciones mejoradas tienen cerca de 1052
estados (Ejercicio 3.5). Ésta es una reducción enorme, pero el espacio de estados mejo-
rado sigue siendo demasiado grande para los algoritmos de este capítulo. El Capítulo 4
76 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

describe la formulación completa de estados y el Capítulo 5 nos da un algoritmo senci-

llo que hace el problema de un millón de reinas fácil de resolver.

Problemas del mundo real

PROBLEMA Hemos visto cómo el problema de búsqueda de una ruta está definido en términos de
DE BÚSQUEDA
DE UNA RUTA posiciones y transiciones a lo largo de ellas. Los algoritmos de búsqueda de rutas se han
utilizado en una variedad de aplicaciones, tales como rutas en redes de computadores,
planificación de operaciones militares, y en sistemas de planificación de viajes de líne-
as aéreas. Estos problemas son complejos de especificar. Consideremos un ejemplo
simplificado de un problema de viajes de líneas aéreas que especificamos como:
• Estados: cada estado está representado por una localización (por ejemplo, un ae-
ropuerto) y la hora actual.
• Estado inicial: especificado por el problema.
• Función sucesor: devuelve los estados que resultan de tomar cualquier vuelo pro-
gramado (quizá más especificado por la clase de asiento y su posición) desde el
aeropuerto actual a otro, que salgan a la hora actual más el tiempo de tránsito del
aeropuerto.
• Test objetivo: ¿tenemos nuestro destino para una cierta hora especificada?
• Costo del camino: esto depende del costo en dinero, tiempo de espera, tiempo
del vuelo, costumbres y procedimientos de la inmigración, calidad del asiento, hora,
tipo de avión, kilometraje del aviador experto, etcétera.
Los sistemas comerciales de viajes utilizan una formulación del problema de este tipo,
con muchas complicaciones adicionales para manejar las estructuras bizantinas del pre-
cio que imponen las líneas aéreas. Cualquier viajero experto sabe, sin embargo, que
no todo el transporte aéreo va según lo planificado. Un sistema realmente bueno debe
incluir planes de contingencia (tales como reserva en vuelos alternativos) hasta el punto
de que éstos estén justificados por el coste y la probabilidad de la falta del plan
original.
PROBLEMAS
TURÍSTICOS Los problemas turísticos están estrechamente relacionados con los problemas de
búsqueda de una ruta, pero con una importante diferencia. Consideremos, por ejem-
plo, el problema, «visitar cada ciudad de la Figura 3.2 al menos una vez, comenzan-
do y finalizando en Bucarest». Como en la búsqueda de rutas, las acciones corresponden
a viajes entre ciudades adyacentes. El espacio de estados, sin embargo, es absoluta-
mente diferente. Cada estado debe incluir no sólo la localización actual sino también
las ciudades que el agente ha visitado. El estado inicial sería «En Bucarest; visitado
{Bucarest}», un estado intermedio típico sería «En Vaslui; visitado {Bucarest, Urzi-
ceni, Vaslui}», y el test objetivo comprobaría si el agente está en Bucarest y ha visi-
PROBLEMA DEL
tado las 20 ciudades.
VIAJANTE DE El problema del viajante de comercio (PVC) es un problema de ruta en la que cada
COMERCIO
ciudad es visitada exactamente una vez. La tarea principal es encontrar el viaje más cor-
to. El problema es de tipo NP duro, pero se ha hecho un gran esfuerzo para mejorar las
capacidades de los algoritmos del PVC. Además de planificación de los viajes del
viajante de comercio, estos algoritmos se han utilizado para tareas tales como la plani-
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 77

ficación de los movimientos de los taladros de un circuito impreso y para abastecer de

máquinas a las tiendas.
DISTRIBUCIÓN VLSI Un problema de distribución VLSI requiere la colocación de millones de compo-
nentes y de conexiones en un chip verificando que el área es mínima, que se reduce al
mínimo el circuito, que se reduce al mínimo las capacitaciones, y se maximiza la pro-
ducción de fabricación. El problema de la distribución viene después de la fase de di-
seño lógico, y está dividido generalmente en dos partes: distribución de las celdas y
dirección del canal. En la distribución de las celdas, los componentes primitivos del cir-
cuito se agrupan en las celdas, cada una de las cuales realiza una cierta función. Cada
celda tiene una característica fija (el tamaño y la forma) y requiere un cierto número de
conexiones a cada una de las otras celdas. El objetivo principal es colocar las celdas en
el chip de manera que no se superpongan y que quede espacio para que los alambres que
conectan celdas puedan colocarse entre ellas. La dirección del canal encuentra una ruta
específica para cada alambre por los espacios entre las celdas. Estos problemas de bús-
queda son extremadamente complejos, pero definitivamente dignos de resolver. En el Ca-
pítulo 4, veremos algunos algoritmos capaces de resolverlos.
NAVEGACIÓN DE
UN ROBOT La navegación de un robot es una generalización del problema de encontrar una
ruta descrito anteriormente. Más que un conjunto discreto de rutas, un robot puede mo-
verse en un espacio continuo con (en principio) un conjunto infinito de acciones y esta-
dos posibles. Para un robot circular que se mueve en una superficie plana, el espacio es
esencialmente de dos dimensiones. Cuando el robot tiene manos y piernas o ruedas que
se deben controlar también, el espacio de búsqueda llega a ser de muchas dimensiones.
Lo que se requiere es que las técnicas avanzadas hagan el espacio de búsqueda finito.
Examinaremos algunos de estos métodos en el Capítulo 25. Además de la complejidad
del problema, los robots reales también deben tratar con errores en las lecturas de los
SECUENCIACIÓN PARA
sensores y controles del motor.
EL ENSAMBLAJE La secuenciación para el ensamblaje automático por un robot de objetos com-
AUTOMÁTICO
plejos fue demostrado inicialmente por FREDDY (Michie, 1972). Los progresos desde
entonces han sido lentos pero seguros, hasta el punto de que el ensamblaje de objetos
tales como motores eléctricos son económicamente factibles. En los problemas de en-
samblaje, lo principal es encontrar un orden en los objetos a ensamblar. Si se elige un
orden equivocado, no habrá forma de añadir posteriormente una parte de la secuencia
sin deshacer el trabajo ya hecho. Verificar un paso para la viabilidad de la sucesión es
un problema de búsqueda geométrico difícil muy relacionado con la navegación del ro-
bot. Así, la generación de sucesores legales es la parte costosa de la secuenciación para
el ensamblaje. Cualquier algoritmo práctico debe evitar explorar todo, excepto una
fracción pequeña del espacio de estados. Otro problema de ensamblaje importante es
DISEÑO DE
PROTEÍNAS
el diseño de proteínas, en el que el objetivo es encontrar una secuencia de aminoáci-
dos que se plegarán en una proteína de tres dimensiones con las propiedades adecua-
das para curar alguna enfermedad.
En la actualidad, se ha incrementado la demanda de robots software que realicen la
BÚSQUEDA EN
INTERNET
búsqueda en Internet, la búsqueda de respuestas a preguntas, de información relacio-
nada o para compras. Esto es una buena aplicación para las técnicas de búsqueda, por-
que es fácil concebir Internet como un grafo de nodos (páginas) conectadas por arcos.
Una descripción completa de búsqueda en Internet se realiza en el Capítulo 10.
78 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

3.3 Búsqueda de soluciones

Hemos formulado algunos problemas, ahora necesitamos resolverlos. Esto se hace me-
diante búsqueda a través del espacio de estados. Este capítulo se ocupa de las técnicas de
ÁRBOL DE BÚSQUEDA búsqueda que utilizan un árbol de búsqueda explícito generado por el estado inicial y la
función sucesor, definiendo así el espacio de estados. En general, podemos tener un gra-
fo de búsqueda más que un árbol, cuando el mismo estado puede alcanzarse desde varios
caminos. Aplazamos, hasta la Sección 3.5, el tratar estas complicaciones importantes.
La Figura 3.6 muestra algunas de las expansiones en el árbol de búsqueda para en-
NODO DE BÚSQUEDA
contrar una camino desde Arad a Bucarest. La raíz del árbol de búsqueda es el nodo de
búsqueda que corresponde al estado inicial, En(Arad). El primer paso es comprobar si
éste es un estado objetivo. Claramente es que no, pero es importante comprobarlo de modo
que podamos resolver problemas como «comenzar en Arad, consigue Arad». Como no
estamos en un estado objetivo, tenemos que considerar otros estados. Esto se hace ex-
EXPANDIR pandiendo el estado actual; es decir aplicando la función sucesor al estado actual y ge-
GENERAR
nerar así un nuevo conjunto de estados. En este caso, conseguimos tres nuevos estados:
En(Sibiu), En(Timisoara) y En(Zerind). Ahora debemos escoger cuál de estas tres po-
sibilidades podemos considerar.
Esto es la esencia de la búsqueda, llevamos a cabo una opción y dejamos de lado las
demás para más tarde, en caso de que la primera opción no conduzca a una solución.
Supongamos que primero elegimos Sibiu. Comprobamos si es un estado objetivo (que
no lo es) y entonces expandimos para conseguir En(Arad), En(Fagaras), En(Oradea) y
En(RimnicuVilcea). Entonces podemos escoger cualquiera de estas cuatro o volver atrás
y escoger Timisoara o Zerind. Continuamos escogiendo, comprobando y expandiendo
hasta que se encuentra una solución o no existen más estados para expandir. El estado
ESTRATEGIA DE
BÚSQUEDA
a expandir está determinado por la estrategia de búsqueda. La Figura 3.7 describe in-
formalmente el algoritmo general de búsqueda en árboles.
Es importante distinguir entre el espacio de estados y el árbol de búsqueda. Para el
problema de búsqueda de un ruta, hay solamente 20 estados en el espacio de estados,
uno por cada ciudad. Pero hay un número infinito de caminos en este espacio de esta-
dos, así que el árbol de búsqueda tiene un número infinito de nodos. Por ejemplo, los
tres caminos Arad-Sibiu, Arad-Sibiu-Arad, Arad-Sibiu-Arad-Sibiu son los tres prime-
ros caminos de una secuencia infinita de caminos. (Obviamente, un buen algoritmo de
búsqueda evita seguir tales trayectorias; La Sección 3.5 nos muestra cómo hacerlo).
Hay muchas formas de representar los nodos, pero vamos a suponer que un nodo es
una estructura de datos con cinco componentes:
— ESTADO: el estado, del espacio de estados, que corresponde con el nodo;
— NODO PADRE: el nodo en el árbol de búsqueda que ha generado este nodo;
— ACCIÓN: la acción que se aplicará al padre para generar el nodo;
— COSTO DEL CAMINO: el costo, tradicionalmente denotado por g(n), de un cami-
no desde el estado inicial al nodo, indicado por los punteros a los padres; y
— PROFUNDIDAD: el número de pasos a los largo del camino desde el estado inicial.
Es importante recordar la distinción entre nodos y estados. Un nodo es una estructura
de datos usada para representar el árbol de búsqueda. Un estado corresponde a una
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 79

(a) Estado inicial Arad

Sibiu Timisora Zerind

Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea

(b) Después de expandir Arad Arad

Sibiu Timisora Zerind

Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea

(c) Después de expandir Sibiu Arad

Sibiu Timisora Zerind

Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea

Figura 3.6 Árboles de búsqueda parciales para encontrar una ruta desde Arad hasta Bucarest. Se
sombrean los nodos que se han expandido; los nodos que se han generado pero todavía no se han
expandido se rodean en negrita; los nodos que todavía no se han generado se marcan con líneas
discontinuas.

función BÚSQUEDA-ÁRBOLES(problema,estrategia) devuelve una solución o fallo

inicializa el árbol de búsqueda usando el estado inicial del problema
bucle hacer
si no hay candidatos para expandir entonces devolver fallo
escoger, de acuerdo a la estrategia, un nodo hoja para expandir
si el nodo contiene un estado objetivo entonces devolver la correspondiente solución
en otro caso expandir el nodo y añadir los nodos resultado al árbol de búsqueda

Figura 3.7 Descripción informal del algoritmo general de búsqueda en árboles.

configuración del mundo. Así, los nodos están en caminos particulares, según lo defi-
nido por los punteros del nodo padre, mientras que los estados no lo están. En la Figu-
ra 3.8 se representa la estructura de datos del nodo.
También necesitamos representar la colección de nodos que se han generado pero
FRONTERA todavía no se han expandido – a esta colección se le llama frontera. Cada elemento de
80 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

NODO-PADRE

Nodo ACCIÓN = derecha

5 4 PROFUNDIDAD = 6
COSTO DEL CAMINO = 6
6 1 88
ESTADO
7 3 22

Figura 3.8 Los nodos son estructuras de datos a partir de los cuales se construye el árbol de bús-
queda. Cada uno tiene un padre, un estado y varios campos. Las flechas señalan del hijo al padre.

NODO HOJA la frontera es un nodo hoja, es decir, un nodo sin sucesores en el árbol. En la Figura 3.6,
la frontera de cada árbol consiste en los nodos dibujados con líneas discontinuas. La re-
presentación más simple de la frontera sería como un conjunto de nodos. La estrategia
de búsqueda será una función que seleccione de este conjunto el siguiente nodo a ex-
pandir. Aunque esto sea conceptualmente sencillo, podría ser computacionalmente cos-
toso, porque la función estrategia quizá tenga que mirar cada elemento del conjunto para
escoger el mejor. Por lo tanto, nosotros asumiremos que la colección de nodos se im-
COLA plementa como una cola. Las operaciones en una cola son como siguen:
— HACER-COLA(elemento, …) crea una cola con el(los) elemento(s) dado(s).
— VACIA?(cola) devuelve verdadero si no hay ningún elemento en la cola.
— PRIMERO(cola) devuelve el primer elemento de la cola.
— BORRAR-PRIMERO(cola) devuelve PRIMERO(cola) y lo borra de la cola.
— INSERTA(elemento,cola) inserta un elemento en la cola y devuelve la cola resul-
tado. (Veremos que tipos diferentes de colas insertan los elementos en órdenes
diferentes.)
— INSERTAR-TODO(elementos,cola) inserta un conjunto de elementos en la cola y de-
vuelve la cola resultado.
Con estas definiciones, podemos escribir una versión más formal del algoritmo general
de búsqueda en árboles. Se muestra en la Figura 3.9.

Medir el rendimiento de la resolución del problema

La salida del algoritmo de resolución de problemas es fallo o una solución. (Algunos al-
goritmos podrían caer en un bucle infinito y nunca devolver una salida.) Evaluaremos
el rendimiento de un algoritmo de cuatro formas:
COMPLETITUD • Completitud: ¿está garantizado que el algoritmo encuentre una solución cuando
esta exista?
OPTIMIZACIÓN • Optimización: ¿encuentra la estrategia la solución óptima, según lo definido en
la página 62?
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 81

función BÚSQUEDA-ÁRBOLES(problema,frontera) devuelve una solución o fallo

frontera ← INSERTA(HACER-NODO(ESTADO-INICIAL[problema]), frontera)
hacer bucle
si VACIA?(frontera) entonces devolver fallo.
nodo ← BORRAR-PRIMERO(frontera)
si TEST-OBJETIVO[problema] aplicado al ESTADO[nodo] es cierto
entonces devolver SOLUCIÓN(nodo)
frontera ← INSERTAR-TODO(EXPANDIR(nodo,problema),frontera)

función EXPANDIR(nodo,problema) devuelve un conjunto de nodos

sucesores ← conjunto vacío
para cada (acción,resultado) en SUCESOR-FN[problema](ESTADO[nodo]) hacer
s ← un nuevo NODO
ESTADO[s] ← resultado
NODO-PADRE[s] ← nodo
ACCIÓN[s] ← acción
COSTO-CAMINO[s] ← COSTO-CAMINO[nodo]  COSTO-INDIVIDUAL(nodo,acción,s)
PROFUNDIDAD[s] ← PROFUNDIDAD[nodo]  1
añadir s a sucesores
devolver sucesores

Figura 3.9 Algoritmo general de búsqueda en árboles. (Notemos que el argumento frontera pue-
de ser una cola vacía, y el tipo de cola afectará al orden de la búsqueda.) La función SOLUCIÓN de-
vuelve la secuencia de acciones obtenida de la forma punteros al padre hasta la raíz.

COMPLEJIDAD EN • Complejidad en tiempo: ¿cuánto tarda en encontrar una solución?

TIEMPO
• Complejidad en espacio: ¿cuánta memoria se necesita para el funcionamiento de
COMPLEJIDAD EN la búsqueda?
ESPACIO
La complejidad en tiempo y espacio siempre se considera con respecto a alguna medi-
da de la dificultad del problema. En informática teórica, la medida es el tamaño del gra-
fo del espacio de estados, porque el grafo se ve como una estructura de datos explícita
que se introduce al programa de búsqueda. (El mapa de Rumanía es un ejemplo de esto.)
En IA, donde el grafo está representado de forma implícita por el estado inicial y la fun-
ción sucesor y frecuentemente es infinito, la complejidad se expresa en términos de tres
FACTOR DE
RAMIFICACIÓN
cantidades: b, el factor de ramificación o el máximo número de sucesores de cualquier
nodo; d, la profundidad del nodo objetivo más superficial; y m, la longitud máxima de
cualquier camino en el espacio de estados.
El tiempo a menudo se mide en términos de número de nodos generados5 durante
la búsqueda, y el espacio en términos de máximo número de nodos que se almacena en
memoria.
COSTO DE LA Para valorar la eficacia de un algoritmo de búsqueda, podemos considerar el costo
BÚSQUEDA
de la búsqueda (que depende típicamente de la complejidad en tiempo pero puede in-

5
Algunos textos miden el tiempo en términos del número de las expansiones del nodo. Las dos medidas se
diferencian como mucho en un factor b. A nosotros nos parece que el tiempo de ejecución de la expansión
del nodo aumenta con el número de nodos generados en esa expansión.
82 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

COSTE TOTAL cluir también un término para el uso de la memoria) o podemos utilizar el coste total,
que combina el costo de la búsqueda y el costo del camino solución encontrado. Para el
problema de encontrar una ruta desde Arad hasta Bucarest, el costo de la búsqueda es
la cantidad de tiempo que ha necesitado la búsqueda y el costo de la solución es la lon-
gitud total en kilómetros del camino. Así, para el cálculo del coste total, tenemos que
sumar kilómetros y milisegundos. No hay ninguna conversión entre los dos, pero quizá
sea razonable, en este caso, convertir kilómetros en milisegundos utilizando una esti-
mación de la velocidad media de un coche (debido a que el tiempo es lo que cuida el
agente.) Esto permite al agente encontrar un punto óptimo de intercambio en el cual el
cálculo adicional para encontrar que un camino más corto llegue a ser contraproducen-
te. El problema más general de intercambios entre bienes diferentes será tratado en el
Capítulo 16.

3.4 Estrategias de búsqueda no informada

BÚSQUEDA NO Esta sección trata cinco estrategias de búsqueda englobadas bajo el nombre de búsqueda
INFORMADA
no informada (llamada también búsqueda a ciegas). El término significa que ellas no
tienen información adicional acerca de los estados más allá de la que proporciona la
definición del problema. Todo lo que ellas pueden hacer es generar los sucesores y
BÚSQUEDA distinguir entre un estado objetivo de uno que no lo es. Las estrategias que saben si un
INFORMADA
estado no objetivo es «más prometedor» que otro se llaman búsqueda informada o
BÚSQUEDA búsqueda heurística; éstas serán tratadas en el Capítulo 4. Todas las estrategias se dis-
HEURÍSTICA
tinguen por el orden de expansión de los nodos.

Búsqueda primero en anchura

BÚSQUEDA PRIMERO
EN ANCHURA
La búsqueda primero en anchura es una estrategia sencilla en la que se expande pri-
mero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, des-
pués sus sucesores, etc. En general, se expanden todos los nodos a una profundidad en
el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel.
La búsqueda primero en anchura se puede implementar llamando a la BÚSQUEDA-
ÁRBOLES con una frontera vacía que sea una cola primero en entrar primero en salir
(FIFO), asegurando que los nodos primeros visitados serán los primeros expandidos. En
otras palabras, llamando a la BÚSQUEDA-ÁRBOLES(problema,COLA-FIFO()) resulta una
búsqueda primero en anchura. La cola FIFO pone todos los nuevos sucesores genera-
dos al final de la cola, lo que significa que los nodos más superficiales se expanden an-
tes que los nodos más profundos. La Figura 3.10 muestra el progreso de la búsqueda en
un árbol binario sencillo.
Evaluemos la búsqueda primero en anchura usando los cuatro criterios de la sección
anterior. Podemos ver fácilmente que es completa (si el nodo objetivo más superficial
está en una cierta profundidad finita d, la búsqueda primero en anchura lo encontrará
después de expandir todos los nodos más superficiales, con tal que el factor de ramifi-
cación b sea finito). El nodo objetivo más superficial no es necesariamente el óptimo;
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 83

A A A A

B C B C B C B C

D E F G D E F G D E F G D E F G

Figura 3.10 Búsqueda primero en anchura sobre un árbol binario sencillo. En cada etapa, el pró-
ximo nodo a expandir se indica con una marca.

técnicamente, la búsqueda primero en anchura es óptima si el costo del camino es una

función no decreciente de la profundidad del nodo (por ejemplo, cuando todas las ac-
ciones tienen el mismo coste).
Hasta ahora, la información sobre la búsqueda primero en anchura ha sido buena.
Para ver por qué no es siempre la estrategia a elegir, tenemos que considerar la cantidad
de tiempo y memoria que utiliza para completar una búsqueda. Para hacer esto, consi-
deramos un espacio de estados hipotético donde cada estado tiene b sucesores. La raíz
del árbol de búsqueda genera b nodos en el primer nivel, cada uno de ellos genera b no-
dos más, teniendo un total de b2 en el segundo nivel. Cada uno de estos genera b nodos
más, teniendo b3 nodos en el tercer nivel, etcétera. Ahora supongamos que la solución
está a una profundidad d. En el peor caso, expandiremos todos excepto el último nodo
en el nivel d (ya que el objetivo no se expande), generando bd 1  b nodos en el nivel
d  1. Entonces el número total de nodos generados es
b  b2  b3  ...  bd  (bd1  b)  O(bd1).
Cada nodo generado debe permanecer en la memoria, porque o es parte de la frontera o
es un antepasado de un nodo de la frontera. La complejidad en espacio es, por lo tanto,
la misma que la complejidad en tiempo (más un nodo para la raíz).
Los que hacen análisis de complejidad están preocupados (o emocionados, si les gus-
ta el desafío) por las cotas de complejidad exponencial como O(bd  1). La Figura 3.11
muestra por qué. Se enumera el tiempo y la memoria requerida para una búsqueda pri-
mero en anchura con el factor de ramificación b  10, para varios valores de profundi-

Profundidad Nodos Tiempo Memoria

2 1.100 11 segundos 1 megabyte
4 111.100 11 segundos 106 megabytes
6 107 19 minutos 10 gigabytes
8 109 31 horas 1 terabytes
10 1011 129 días 101 terabytes
12 1013 35 años 10 petabytes
14 1015 3.523 años 1 exabyte

Figura 3.11 Requisitos de tiempo y espacio para la búsqueda primero en anchura. Los nú-
meros que se muestran suponen un factor de ramificación b  10; 10.000 nodos/segundo; 1.000
bytes/nodo.
84 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

dad d de la solución. La tabla supone que se pueden generar 10.000 nodos por segundo
y que un nodo requiere 1.000 bytes para almacenarlo. Muchos problemas de búsqueda
quedan aproximadamente dentro de estas suposiciones (más o menos un factor de 100)
cuando se ejecuta en un computador personal moderno.
Hay dos lecciones que debemos aprender de la Figura 3.11. Primero, son un problema
más grande los requisitos de memoria para la búsqueda primero en anchura que el tiem-
po de ejecución. 31 horas no sería demasiado esperar para la solución de un problema
importante a profundidad ocho, pero pocos computadores tienen suficientes terabytes
de memoria principal que lo admitieran. Afortunadamente, hay otras estrategias de bús-
queda que requieren menos memoria.
La segunda lección es que los requisitos de tiempo son todavía un factor importan-
te. Si su problema tiene una solución a profundidad 12, entonces (dadas nuestras supo-
siciones) llevará 35 años encontrarla por la búsqueda primero en anchura (o realmente
alguna búsqueda sin información). En general, los problemas de búsqueda de comple-
jidad-exponencial no pueden resolverse por métodos sin información, salvo casos pe-
queños.

Búsqueda de costo uniforme

La búsqueda primero en anchura es óptima cuando todos los costos son iguales, porque
siempre expande el nodo no expandido más superficial. Con una extensión sencilla, po-
demos encontrar un algoritmo que es óptimo con cualquier función costo. En vez de ex-
BÚSQUEDA DE COSTO pandir el nodo más superficial, la búsqueda de costo uniforme expande el nodo n con
UNIFORME
el camino de costo más pequeño. Notemos que si todos los costos son iguales, es idén-
tico a la búsqueda primero en anchura.
La búsqueda de costo uniforme no se preocupa por el número de pasos que tiene
un camino, pero sí sobre su coste total. Por lo tanto, éste se meterá en un bucle infi-
nito si expande un nodo que tiene una acción de coste cero que conduzca de nuevo al
mismo estado (por ejemplo, una acción NoOp). Podemos garantizar completitud si el
costo de cada paso es mayor o igual a alguna constante positiva pequeña . Esta con-
dición es también suficiente para asegurar optimización. Significa que el costo de un
camino siempre aumenta cuando vamos por él. De esta propiedad, es fácil ver que el
algoritmo expande nodos que incrementan el coste del camino. Por lo tanto, el primer
nodo objetivo seleccionado para la expansión es la solución óptima. (Recuerde que la
búsqueda en árboles aplica el test objetivo sólo a los nodos que son seleccionados para
la expansión.) Recomendamos probar el algoritmo para encontrar el camino más cor-
to a Bucarest.
La búsqueda de costo uniforme está dirigida por los costos de los caminos más que
por las profundidades, entonces su complejidad no puede ser fácilmente caracterizada
en términos de b y d. En su lugar, C* es el costo de la solución óptima, y se supone
que cada acción cuesta al menos- .- Entonces la complejidad en tiempo y espacio del
peor caso del algoritmo es O(b  C*  ), la cual puede ser mucho mayor que bd. Esto es
porque la búsqueda de costo uniforme, y a menudo lo hace, explora los árboles gran-
des en pequeños pasos antes de explorar caminos que implican- pasos -
grandes y quizás
útiles. Cuando todos los costos son iguales, desde luego, la b  C*  es justamente bd.
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 85

Búsqueda primero en profundidad

BÚSQUEDA PRIMERO La búsqueda primero en profundidad siempre expande el nodo más profundo en la
EN PROFUNDIDAD
frontera actual del árbol de búsqueda. El progreso de la búsqueda se ilustra en la Figu-
ra 3.12. La búsqueda procede inmediatamente al nivel más profundo del árbol de bús-
queda, donde los nodos no tienen ningún sucesor. Cuando esos nodos se expanden, son
quitados de la frontera, así entonces la búsqueda «retrocede» al siguiente nodo más su-
perficial que todavía tenga sucesores inexplorados.
Esta estrategia puede implementarse por la BÚSQUEDA-ÁRBOLES con una cola últi-
mo en entrar primero en salir (LIFO), también conocida como una pila. Como una al-
ternativa a la implementación de la BÚSQUEDA-ÁRBOLES, es común aplicar la búsqueda
primero en profundidad con una función recursiva que se llama en cada uno de sus hi-
jos. (Un algoritmo primero en profundidad recursivo incorporando un límite de profun-
didad se muestra en la Figura 3.13.)
La búsqueda primero en profundidad tiene unos requisitos muy modestos de memoria.
Necesita almacenar sólo un camino desde la raíz a un nodo hoja, junto con los nodos
hermanos restantes no expandidos para cada nodo del camino. Una vez que un nodo se

A A A

B C B C B C

D E F G D E F G D E F G

H I J K L M N O H I J K L M N O H I J K L M N O

A A A

B C B C B C

D E F G D E F G D E F G

H I J K L M N O H I J K L M N O H I J K L M N O

A A A

B C B C B C

D E F G D E F G D E F G

H I J K L M N O H I J K L M N O H I J K L M N O

A A A

B C B C B C

D E F G D E F G D E F G

H I J K L M N O H I J K L M N O H I J K L M N O

Figura 3.12 Búsqueda primero en profundidad sobre un árbol binario. Los nodos que se han ex-
pandido y no tienen descendientes en la frontera se pueden quitar de la memoria; estos se muestran
en negro. Los nodos a profundidad 3 se suponen que no tienen sucesores y M es el nodo objetivo.
86 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

función BÚSQUEDA-PROFUNDIDAD-LIMITADA(problema,límite) devuelve una solución, o

fallo/corte
devolver BPL-RECURSIVO(HACER-NODO(ESTADO-INICIAL[problema]),problema,límite)

función BPL-RECURSIVO(nodo,problema,límite) devuelve una solución, o fallo/corte

ocurrió un corte ← falso
si TEST-OBJETIVO[problema](ESTADO[nodo]) entonces devolver SOLUCIÓN(nodo)
en caso contrario si PROFUNDIDAD[nodo]  límite entonces devolver corte
en caso contrario para cada sucesor en EXPANDIR(nodo,problema) hacer
resultado ← BPL-RECURSIVO(sucesor,problema,límite)
si resultado  corte entonces ocurrió un corte ← verdadero
en otro caso si resultado  fallo entonces devolver resultado
si ocurrió un corte? entonces devolver corte en caso contrario devolver fallo

Figura 3.13 Implementación recursiva de la búsqueda primero en profundidad.

ha expandido, se puede quitar de la memoria tan pronto como todos su descendientes

han sido explorados. (Véase Figura 3.12.) Para un espacio de estados con factor de ra-
mificación b y máxima profundidad m, la búsqueda primero en profundidad requiere al-
macenar sólo bm  1 nodos. Utilizando las mismas suposiciones que con la Figura 3.11,
y suponiendo que los nodos a la misma profundidad que el nodo objetivo no tienen nin-
gún sucesor, nos encontramos que la búsqueda primero en profundidad requeriría 118
kilobytes en vez de diez petabytes a profundidad d  12, un factor de diez billones de
veces menos de espacio.
BÚSQUEDA HACIA Una variante de la búsqueda primero en profundidad, llamada búsqueda hacia
ATRÁS
atrás, utiliza todavía menos memoria. En la búsqueda hacia atrás, sólo se genera un su-
cesor a la vez; cada nodo parcialmente expandido recuerda qué sucesor se expande a con-
tinuación. De esta manera, sólo se necesita O(m) memoria más que el O(bm) anterior.
La búsqueda hacia atrás facilita aún otro ahorro de memoria (y ahorro de tiempo): la idea
de generar un sucesor modificando directamente la descripción actual del estado más que
copiarlo. Esto reduce los requerimientos de memoria a solamente una descripción del
estado y O(m) acciones. Para hacer esto, debemos ser capaces de deshacer cada modi-
ficación cuando volvemos hacia atrás para generar el siguiente sucesor. Para problemas
con grandes descripciones de estados, como el ensamblaje en robótica, estas técnicas son
críticas para tener éxito.
El inconveniente de la búsqueda primero en profundidad es que puede hacer una elec-
ción equivocada y obtener un camino muy largo (o infinito) aun cuando una elección
diferente llevaría a una solución cerca de la raíz del árbol de búsqueda. Por ejemplo, en
la Figura 3.12, la búsqueda primero en profundidad explorará el subárbol izquierdo en-
tero incluso si el nodo C es un nodo objetivo. Si el nodo J fuera también un nodo obje-
tivo, entonces la búsqueda primero en profundidad lo devolvería como una solución; de
ahí, que la búsqueda primero en profundidad no es óptima. Si el subárbol izquierdo fue-
ra de profundidad ilimitada y no contuviera ninguna solución, la búsqueda primero en
profundidad nunca terminaría; de ahí, que no es completo. En el caso peor, la búsque-
da primero en profundidad generará todos los nodos O(bm) del árbol de búsqueda, don-
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 87

de m es la profundidad máxima de cualquier nodo. Nótese que m puede ser mucho más
grande que d (la profundidad de la solución más superficial), y es infinito si el árbol es
ilimitado.

Búsqueda de profundidad limitada

Se puede aliviar el problema de árboles ilimitados aplicando la búsqueda primero en pro-
fundidad con un límite de profundidad
predeterminado. Es decir, los nodos a profun-
didad
se tratan como si no tuvieran ningún sucesor. A esta aproximación se le llama
BÚSQUEDA DE
PROFUNDIDAD búsqueda de profundidad limitada. El límite de profundidad resuelve el problema del
LIMITADA
camino infinito. Lamentablemente, también introduce una fuente adicional de incom-
pletitud si escogemos
d, es decir, el objetivo está fuera del límite de profundidad.
(Esto no es improbable cuando d es desconocido.) La búsqueda de profundidad limita-
da también será no óptima si escogemos

d. Su complejidad en tiempo es O(b
) y su
complejidad en espacio es O(b
). La búsqueda primero en profundidad puede verse como
un caso especial de búsqueda de profundidad limitada con
 .
A veces, los límites de profundidad pueden estar basados en el conocimiento del pro-
blema. Por ejemplo, en el mapa de Rumanía hay 20 ciudades. Por lo tanto, sabemos que
si hay una solución, debe ser de longitud 19 como mucho, entonces
 19 es una op-
ción posible. Pero de hecho si estudiáramos el mapa con cuidado, descubriríamos que
cualquier ciudad puede alcanzarse desde otra como mucho en nueve pasos. Este núme-
DIÁMETRO ro, conocido como el diámetro del espacio de estados, nos da un mejor límite de pro-
fundidad, que conduce a una búsqueda con profundidad limitada más eficiente. Para la
mayor parte de problemas, sin embargo, no conoceremos un límite de profundidad bue-
no hasta que hayamos resuelto el problema.
La búsqueda de profundidad limitada puede implementarse con una simple modifi-
cación del algoritmo general de búsqueda en árboles o del algoritmo recursivo de bús-
queda primero en profundidad. En la Figura 3.13 se muestra el pseudocódigo de la bús-
queda recursiva de profundidad limitada. Notemos que la búsqueda de profundidad
limitada puede terminar con dos clases de fracaso: el valor de fracaso estándar indicando
que no hay ninguna solución; el valor de corte indicando que no hay solución dentro del
límite de profundidad.

Búsqueda primero en profundidad con profundidad

iterativa
BÚSQUEDA CON
PROFUNDIDAD La búsqueda con profundidad iterativa (o búsqueda primero en profundidad con pro-
ITERATIVA
fundidad iterativa) es una estrategia general, usada a menudo en combinación con la bús-
queda primero en profundidad, la cual encuentra el mejor límite de profundidad. Esto
se hace aumentando gradualmente el límite (primero 0, después 1, después 2, etcétera)
hasta que encontramos un objetivo. Esto ocurrirá cuando el límite de profundidad alcanza
d, profundidad del nodo objetivo. Se muestra en la Figura 3.14 el algoritmo. La pro-
fundidad iterativa combina las ventajas de la búsqueda primero en profundidad y pri-
mero en anchura. En la búsqueda primero en profundidad, sus exigencias de memoria
88 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

función BÚSQUEDA-PROFUNDIDAD-ITERATIVA(problema) devuelve una solución, o fallo

entradas: problema, un problema

para profundidad ← 0 a  hacer

resultado ← BÚSQUEDA-PROFUNDIDAD-LIMITADA(problema,profundidad)
si resultado  corte entonces devolver resultado

Figura 3.14 Algoritmo de búsqueda de profundidad iterativa, el cual aplica repetidamente la bús-
queda de profundidad limitada incrementando el límite. Termina cuando se encuentra una solución
o si la búsqueda de profundidad limitada devuelve fracaso, significando que no existe solución.

son muy modestas: O(bd) para ser exacto. La búsqueda primero en anchura, es completa
cuando el factor de ramificación es finito y óptima cuando el coste del camino es una
función que no disminuye con la profundidad del nodo. La Figura 3.15 muestra cuatro
iteraciones de la BÚSQUEDA-PROFUNDIDAD-ITERATIVA sobre un árbol binario de búsque-
da, donde la solución se encuentra en la cuarta iteración.
La búsqueda de profundidad iterativa puede parecer derrochadora, porque los esta-
dos se generan múltiples veces. Pero esto no es muy costoso. La razón es que en un ár-
bol de búsqueda con el mismo (o casi el mismo) factor de ramificación en cada nivel, la
mayor parte de los nodos está en el nivel inferior, entonces no importa mucho que los
niveles superiores se generen múltiples veces. En una búsqueda de profundidad iterati-
va, los nodos sobre el nivel inferior (profundidad d ) son generados una vez, los ante-
riores al nivel inferior son generados dos veces, etc., hasta los hijos de la raíz, que son
generados d veces. Entonces el número total de nodos generados es
N(BPI)  (d )b  (d  1)b2  ...  (1)bd,
que da una complejidad en tiempo de O(bd). Podemos compararlo con los nodos gene-
rados por una búsqueda primero en anchura:
N(BPA)  b  b2  ...  bd  (bd1  b).
Notemos que la búsqueda primero en anchura genera algunos nodos en profundidad
d  1, mientras que la profundidad iterativa no lo hace. El resultado es que la profun-
didad iterativa es en realidad más rápida que la búsqueda primero en anchura, a pesar
de la generación repetida de estados. Por ejemplo, si b  10 y d  5, los números son
N(BPI)  50  400  3.000  20.000  100.000  123.450
N(BPA)  10  100  1.000  10.000  100.000  999.990  1.111.100
En general, la profundidad iterativa es el método de búsqueda no informada preferido cuan-
do hay un espacio grande de búsqueda y no se conoce la profundidad de la solución.
La búsqueda de profundidad iterativa es análoga a la búsqueda primero en anchura
en la cual se explora, en cada iteración, una capa completa de nuevos nodos antes de con-
tinuar con la siguiente capa. Parecería que vale la pena desarrollar una búsqueda itera-
tiva análoga a la búsqueda de coste uniforme, heredando las garantías de optimización
del algoritmo evitando sus exigencias de memoria. La idea es usar límites crecientes de
costo del camino en vez de aumentar límites de profundidad. El algoritmo que resulta,
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 89

Límite  0 A

Límite  1 A A A

B C B C C

Límite  2 A A A A

B C B C B C B C

D E F G D E F G D E F G D E F G

A A A A

B C B C B C B C

D E F G D E F G D E F G D E F G

A A A A
Límite  3
B C B C B C B C

D E F G D E F G D E F G D E F G

H I J K L M N O H I J K L M N O H I J K L M N O H I J K L M N O

A A A A

B C B C B C B C

D E F G D E F G D E F G D E F G

H I J K L M N O H I J K L M N O H I J K L M N O H I J K L M N O

A A A A

B C B C B C B C

D E F G D E F G D E F G D E F G

H I J K L M N O H I J K L M N O H I J K L M N O H I J K L M N O

Figura 3.15 Cuatro iteraciones de la búsqueda de profundidad iterativa sobre un árbol binario.

BÚSQUEDA DE llamado búsqueda de longitud iterativa, se explora en el Ejercicio 3.11. Resulta, la-
LONGITUD ITERATIVA
mentablemente, que la longitud iterativa incurre en gastos indirectos sustanciales com-
parado con la búsqueda de coste uniforme.

Búsqueda bidireccional
La idea de la búsqueda bidireccional es ejecutar dos búsquedas simultáneas: una hacia
delante desde el estado inicial y la otra hacia atrás desde el objetivo, parando cuando las
dos búsquedas se encuentren en el centro (Figura 3.16). La motivación es que bd2  bd2
es mucho menor que bd, o en la figura, el área de los dos círculos pequeños es menor
que el área de un círculo grande centrado en el inicio y que alcance al objetivo.
La búsqueda bidireccional se implementa teniendo una o dos búsquedas que com-
prueban antes de ser expandido si cada nodo está en la frontera del otro árbol de bús-
90 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

Inicio Objetivo

Figura 3.16 Un esquema de una búsqueda bidireccional que está a punto de tener éxito, cuando
una rama desde el nodo inicio encuentra una rama desde el nodo objetivo.

queda; si esto ocurre, se ha encontrado una solución. Por ejemplo, si un problema tiene
una solución a profundidad d  6, y en cada dirección se ejecuta la búsqueda primero
en anchura, entonces, en el caso peor, las dos búsquedas se encuentran cuando se han
expandido todos los nodos excepto uno a profundidad 3. Para b  10, esto significa un
total de 22.200 nodos generados, comparado con 11.111.100 para una búsqueda prime-
ro en anchura estándar. Verificar que un nodo pertenece al otro árbol de búsqueda se puede
hacer en un tiempo constante con una tabla hash, así que la complejidad en tiempo de
la búsqueda bidireccional es O(bd2). Por lo menos uno de los árboles de búsqueda se
debe mantener en memoria para que se pueda hacer la comprobación de pertenencia, de
ahí que la complejidad en espacio es también O(bd2). Este requerimiento de espacio es
la debilidad más significativa de la búsqueda bidireccional. El algoritmo es completo y
óptimo (para costos uniformes) si las búsquedas son primero en anchura; otras combi-
naciones pueden sacrificar la completitud, optimización, o ambas.
La reducción de complejidad en tiempo hace a la búsqueda bidireccional atractiva,
PREDECESORES pero ¿cómo busca hacia atrás? Esto no es tan fácil como suena. Sean los predecesores
de un nodo n, Pred(n), todos los nodos que tienen como un sucesor a n. La búsqueda bi-
direccional requiere que Pred(n) se calcule eficientemente. El caso más fácil es cuando
todas las acciones en el espacio de estados son reversibles, así que Pred(n)  Succ(n).
Otro caso puede requerir ser ingenioso.
Consideremos la pregunta de qué queremos decir con «el objetivo» en la búsqueda
«hacia atrás». Para el 8-puzle y para encontrar un camino en Rumanía, hay solamente
un estado objetivo, entonces la búsqueda hacia atrás se parece muchísimo a la búsque-
da hacia delante. Si hay varios estados objetivo explícitamente catalogados (por ejem-
plo, los dos estados objetivo sin suciedad de la Figura 3.3) podemos construir un nuevo
estado objetivo ficticio cuyos predecesores inmediatos son todos los estados objetivo
reales. Alternativamente, algunos nodos generados redundantes se pueden evitar vien-
 RESOLVER PROBLEMAS MEDIANTE BÚSQUEDA 91

do el conjunto de estados objetivo como uno solo, cada uno de cuyos predecesores es
también un conjunto de estados (específicamente, el conjunto de estados que tienen a
un sucesor en el conjunto de estados objetivo. Véase también la Sección 3.6).
El caso más difícil para la búsqueda bidireccional es cuando el test objetivo da sólo
una descripción implícita de algún conjunto posiblemente grande de estados objetivo,
por ejemplo, todos los estados que satisfacen el test objetivo «jaque mate» en el aje-
drez. Una búsqueda hacia atrás necesitaría construir las descripciones de «todos los es-
tados que llevan al jaque mate al mover m1», etcétera; y esas descripciones tendrían que
ser probadas de nuevo con los estados generados en la búsqueda hacia delante. No hay
ninguna manera general de hacer esto eficientemente.

Comparación de las estrategias de búsqueda no informada

La Figura 3.17 compara las estrategias de búsqueda en términos de los cuatro criterios
de evaluación expuestos en la Sección 3.4.

Primero Costo Primero en Profundidad Profundidad Bidireccional

Criterio en anchura uniforme profundidad limitada iterativa (si aplicable)

¿Completa? Sía Sí-a, b - No No Sía Sía, d

Tiempo O(bd1) O(b -C*- ) O(bm) O(b
) O(bd) O(bd2)
Espacio O(bd1) O(b  C*  ) O(bm) O(b
) O(bd) O(bd2)
¿Optimal? Síc Sí No No Síc Síc, d

Figura 3.17 Evaluación de estrategias de búsqueda. b es el factor de ramificación; d es la pro-

fundidad de la solución más superficial; m es la máxima profundidad del árbol de búsqueda;
es
el límite de profundidad. Los superíndice significan lo siguiente: a completa si b es finita; b com-
pleta si los costos son   para  positivo; c optimal si los costos son iguales; d si en ambas direc-
ciones se utiliza la búsqueda primero en anchura.

3.5 Evitar estados repetidos

Hasta este punto, casi hemos ignorado una de las complicaciones más importantes al pro-
ceso de búsqueda: la posibilidad de perder tiempo expandiendo estados que ya han sido
visitados y expandidos. Para algunos problemas, esta posibilidad nunca aparece; el
espacio de estados es un árbol y hay sólo un camino a cada estado. La formulación efi-
ciente del problema de las ocho reinas (donde cada nueva reina se coloca en la colum-
na vacía de más a la izquierda) es eficiente en gran parte a causa de esto (cada estado se
puede alcanzar sólo por un camino). Si formulamos el problema de las ocho reinas para
poder colocar una reina en cualquier columna, entonces cada estado con n reinas se puede
alcanzar por n! caminos diferentes.
Para algunos problemas, la repetición de estados es inevitable. Esto incluye todos
los problemas donde las acciones son reversibles, como son los problemas de búsque-
Tema 1.- Introducción a la Computación Neuronal

INTRODUCCIÓN A LA
COMPUTACIÓN NEURONAL

1
1.1. Introducción
1.2. Características de las Redes Neuronales Artificiales
1.3. Estructura Básica de una Red Neuronal
1.4. Computación Tradicional y Computación Neuronal
1.5. Historia de la Computación Neuronal
1.6. Aplicaciones de las Redes Neuronales Artificiales
1.7. Implementación y Tecnologías Emergentes

TEMA 1.- INTRODUCCIÓN A LA COMPUTACIÓN

NEURONAL

1.1.- INTRODUCCIÓN

El cerebro humano es el sistema de cálculo más complejo que conoce el hombre. El

ordenador y el hombre realizan bien diferentes clases de tareas; así la operación de
reconocer el rostro de una persona resulta una tarea relativamente sencilla para el
hombre y difícil para el ordenador, mientras que la contabilidad de una empresa es tarea
costosa para un experto contable y una sencilla rutina para un ordenador básico.

La capacidad del cerebro humano de pensar, recordar y resolver problemas ha inspirado

a muchos científicos intentar o procurar modelar en el ordenador el funcionamiento del
cerebro humano.

Los profesionales de diferentes campos como la ingeniería, filosofía, fisiología y

psicología han unido sus esfuerzos debido al potencial que ofrece esta tecnología y
están encontrando diferentes aplicaciones en sus respectivas profesiones.

Un grupo de investigadores ha perseguido la creación de un modelo en el ordenador que

iguale o adopte las distintas funciones básicas del cerebro. El resultado ha sido una
nueva tecnología llamada Computación Neuronal o también Redes Neuronales
Artificiales.

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 1

Tema 1.- Introducción a la Computación Neuronal

El resurgimiento del interés en esta nueva forma de realizar los cálculos tras dos
décadas de olvido se debe al extraordinario avance y éxito tanto en el aspecto teórico
como de aplicación que se está obteniendo estos últimos años.

1.2.- CARACTERÍSTICAS DE LAS REDES NEURONALES

ARTIFICIALES

Las Redes Neuronales Artificiales, ANN (Artificial Neural Networks) están inspiradas
en las redes neuronales biológicas del cerebro humano. Están constituidas por
elementos que se comportan de forma similar a la neurona biológica en sus funciones
más comunes. Estos elementos están organizados de una forma parecida a la que
presenta el cerebro humano.

Las ANN al margen de "parecerse" al cerebro presentan una serie de características

propias del cerebro. Por ejemplo las ANN aprenden de la experiencia, generalizan de
ejemplos previos a ejemplos nuevos y abstraen las características principales de una
serie de datos.

Aprender: adquirir el conocimiento de una cosa por medio del estudio, ejercicio
o experiencia. Las ANN pueden cambiar su comportamiento en función del entorno. Se
les muestra un conjunto de entradas y ellas mismas se ajustan para producir unas salidas
consistentes.

Generalizar: extender o ampliar una cosa. Las ANN generalizan

automáticamente debido a su propia estructura y naturaleza. Estas redes pueden ofrecer,
dentro de un margen, respuestas correctas a entradas que presentan pequeñas
variaciones debido a los efectos de ruido o distorsión.

Abstraer: aislar mentalmente o considerar por separado las cualidades de un

objeto. Algunas ANN son capaces de abstraer la esencia de un conjunto de entradas que
aparentemente no presentan aspectos comunes o relativos.

1.3.- ESTRUCTURA BÁSICA DE UNA RED NEURONAL

Analogía con el cerebro.-

La neurona es la unidad fundamental del sistema nervioso y en particular del cerebro.

Cada neurona es una simple unidad procesadora que recibe y combina señales desde y
hacia otras neuronas. Si la combinación de entradas es suficientemente fuerte la salida
de la neurona se activa. La Figura (1.1) muestra las partes que constituyen una neurona.

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 2

Tema 1.- Introducción a la Computación Neuronal

Figura (1.1) - Componentes de una Neurona.

El cerebro consiste en uno o varios billones de neuronas densamente interconectadas.

El axón (salida) de la neurona se ramifica y está conectada a las dendritas (entradas) de
otras neuronas a través de uniones llamadas sinapsis. La eficacia de la sinpasis es
modificable durante el proceso de aprendizaje de la red.

Redes Neuronales Artificiales.-

En las Redes Neuronales Artificiales, ANN, la unidad análoga a la neurona biológica es

el elemento procesador,PE (process element). Un elemento procesador tiene varias
entradas y las combina, normalmente con una suma básica. La suma de las entradas es
modificada por una función de transferencia y el valor de la salida de esta función de
transferencia se pasa directamente a la salida del elemento procesador.

La salida del PE se puede conectar a las entradas de otras neuronas artificiales (PE)
mediante conexiones ponderadas correspondientes a la eficacia de la sinapsis de las
conexiones neuronales.

La Figura (1.2) representa un elemento procesador de una red neuronal artificial

implementada en un ordenador.

Figura (1.2) - Diagrama de una Neurona Artificial (PE).

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 3

Tema 1.- Introducción a la Computación Neuronal

Una red neuronal consiste en un conjunto de unidades elementales PE conectadas de

una forma concreta. El interés de las ANN no reside sólamente en el modelo del
elemento PE sino en las formas en que se conectan estos elementos procesadores.
Generalmente los elementos PE están organizados en grupos llamados niveles o capas.
Una red típica consiste en una secuencia de capas con conexiones entre capas
adyacentes consecutivas.

Existen dos capas con conexiones con el mundo exterior. Una capa de entrada, buffer de
entrada, donde se presentan los datos a la red, y una capa buffer de salida que mantiene
la respuesta de la red a una entrada. El resto de las capas reciben el nombre de capas
ocultas. La Figura (1.3) muestra el aspecto de una Red Neuronal Artificial.

Figura (1.3) - Arquitectura de una Red Neuronal Simple.

1.4.- COMPUTACIÓN TRADICIONAL Y COMPUTACIÓN

NEURONAL

Programación/Entrenamiento.-

Las técnicas tradicionales de programación utilizadas para la solución de un problema

requieren la creación de un algoritmo. Un algoritmo consiste en una secuencia de
instrucciones que indica el modo en el que debe proceder el sistema basado en un
ordenador para lograr el fin perseguido que es la resolución del problema.

El diseño de una secuencia de instrucciones para resolver un problema de contabilidad

es relativamente sencillo, mientras que existen muchos problemas del mundo real en los
que resulta difícil realizar un algoritmo que resuelva dichos problemas. Por ejemplo
imaginemos desarrollar un programa para cualquiera de los problemas de
reconocimiento de imágenes como el rostro de una persona. Hay muchas variaciones de
la imagen de una persona, como que presente un rostro serio o un rostro alegre,
variaciones en general que deben tenerse en cuenta a la hora de diseñar el algoritmo.

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 4

Tema 1.- Introducción a la Computación Neuronal

Las ANN, a diferencia de los algoritmos que son instrucciones previamente

programadas, deben ser previamente entrenadas. Esto significa que a la red se le
muestra en su capa de entrada unos ejemplos y ella misma se ajusta en función de
alguna regla de aprendizaje.

Arquitectura.-

Las ANN presentan una arquitectura totalmente diferente de los ordenadores

tradicionales de un único procesador. Las máquinas tradicionales basadas en el modelo
de Von Neuman tienen un único elemento procesador, la CPU (Control Process Unit)
que realiza todos los cálculos ejecutando todas las instrucciones de la secuencia
programada en el algoritmo. Cualquier CPU realiza más de cien comandos básicos,
incluyendo sumas, restas, y desplazamientos entre otros.

Los comandos o instrucciones se ejecutan secuencialmente y sincronizadas con el reloj

del sistema. Sin embargo en los sistemas de computación neuronal cada elemento PE
sólo puede realizar uno, o como mucho, varios cálculos. La potencia del procesado de
las ANN se mide principalmente por el número de interconexiones actualizadas por
segundo durante el proceso de entrenamiento o aprendizaje. Sin embargo las máquinas
de Von Neuman se miden por el número de instrucciones que ejecuta por segundo el
procesador central CPU.

La arquitectura de las ANN parte de la organización de los sistemas de procesado en

paralelo, es decir, sistemas en los que distintos procesadores están interconectados. No
obstante los procesadores son unidades procesadoras simples, diseñadas para la suma de
muchas entradas y con un ajuste automático de las conexiones ponderadas.

Sistemas Expertos.-

Los sistemas expertos difieren de la programación tradicional en que la base del

conocimiento está separada del motor de inferencia (el método del procesado del
conocimiento). Esta característica permite que todo el conocimiento adicional puede ser
añadido al sistema sin necesidad de tener que ser reprogramado todo el sistema. Esta
técnica requiere que exista una persona experta en un área y que se puedan crear reglas
que codifiquen el conocimiento.

En el desarrollo de una red neuronal no hay que programar ni el conocimiento ni las

reglas del procesamiento del conocimiento. La red neuronal aprende las reglas del
procesamiento del conocimiento mediante el ajuste de las conexiones ponderadas entre
las neuronas de distintas capas de la red.

Mientras que en los Sistemas Expertos el conocimiento se hace explícito en forma de

reglas, en la computación neuronal las ANN generan sus propias reglas aprendiendo de
los ejemplos que se les muestran en la fase de entrenamiento. El aprendizaje se consigue
a través de una regla de aprendizaje que adapta o cambia los pesos de las conexiones en
respuesta a los ejemplos de entrada, y opcionalmente también en respuesta a las salidas
deseadas. Esta característica de las ANN es lo que permite decir que las redes
neuronales aprenden de la experiencia.

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 5

Tema 1.- Introducción a la Computación Neuronal

Una característica importante de las ANN es la forma o el modo en que se almacena la

información. La memoria o el conocimiento de estas redes está distribuida a lo largo de
todas las conexiones ponderadas de la red.

Algunas ANN presentan la característica de ser "asociativas" que significa que para una
entrada parcial la red elegirá la entrada más parecida en memoria y generará una salida
que corresponda a la entrada completa.

La naturaleza de la memoria de las ANN permite que la red responda adecuadamente

cuando se le presenta una entrada incompleta o con ruido. Esta propiedad suele ser
referida como la capacidad de "generalización".

Otra característica de las ANN es la tolerancia a la falta (Fault Tolerance). Tolerancia a

la falta se refiere al hecho de que en muchas ANN si resultaran destruidos varios
elementos procesadores PE, o se alteraran las conexiones el comportamiento de la red
sería mínimamente modificado. El comportamiento varía pero el sistema no se
descompone o deja de funcionar.

Esta característica se debe a que las ANN tienen la información distribuida a lo largo de
toda la red y no está contenida en un único lugar.

1.5.- HISTORIA DE LA COMPUTACIÓN NEURONAL

En 1943, el neurobiólogo Warren McCulloch, y el estadístico Walter Pitss, publicaron

el artículo "A logical calculus of Ideas Imminent in Nervous Activity". Este artículo
constituyó la base y el inicio del desarrollo en diferentes campos como son los
Ordenadores Digitales (John Von Neuman), la Inteligencia Artificial (Marvin Minsky
con los Sistemas Expertos) y el funcionamieto del ojo (Frank Rosenblatt con la famosa
red llamada Perceptron).

En 1956, los pioneros de la Inteligencia Artificial, Minsky, McCarthy, Rochester,

Shanon, organizaron la primera conferencia de Inteligencia Artificial que fue
patrocinada por la Fundación Rochester. Esta conferencia se celebró en el verano de
1956 en la localidad inglesa de Darmouth y en muchos libros se hace referencia al
verano de este año como la primera toma de contacto seria con las redes neuronales
artificiales.

Nathaural Rochester del equipo de investigación de IBM presentó el modelo de una red
neuronal que él mismo realizó y puede considerarse como el primer software de
simulación de redes neuronales artificiales.

En 1957, Frank Rosenblatt publicó el mayor trabajo de investigación en computación

neuronal realizado hasta esas fechas. Su trabajo consistía en el desarrollo de un
elemento llamado "Perceptron".

El perceptron es un sistema clasificador de patrones que puede identificar patrones

geométricos y abstractos. El primer perceptron era capaz de aprender algo y era robusto,
de forma que su comportamiento variaba sólo si resultaban dañados los componentes

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 6

Tema 1.- Introducción a la Computación Neuronal

del sistema. Además presentaba la característica de ser flexible y comportarse

correctamente después de que algunas celdas fueran destruidas.

El perceptron fue originalmente diseñado para el reconocimiento óptico de patrones.

Una rejilla de 400 fotocélulas, correspondientes a las neuronas de la retina sensibles a la
luz, recibe el estímulo óptico. Estas fotocélulas están conectadas a elementos
asociativos que recogen los impulsos eléctricos emitidos desde las fotocélulas. Las
conexiones entre los elementos asociativos y las fotocélulas se realizan de forma
aleatoria.

Si las células presentan un valor de entrada superior a un umbral predeterminado

entonces el elemento asociativo produce una salida. La Figura (1.4) presenta la
estructura de la red perceptron.

Figura (1.4) - Aplicación de la Red Perceptron.

El perceptron presenta algunas limitaciones debido a que se trataba de un dispositivo en

desarrollo. La mayor limitación la reflejaron Minsky y Papert años más tarde, y ponían
de manifiesto la incapacidad del perceptron en resolver algunas tareas o problemas
sencillos como por ejemplo la función lógica OR exclusivo.

Uno de los mayores cambios realizados en el perceptron de Rossenblatt a lo largo de la

década de los 60 ha sido el desarrollo de sistemas multicapa que pueden aprender y
categorizar datos complejos.

En 1959, Bernard Widrow en Stanford desarrolló un elemento adaptativo lineal llamado

"Adaline" (Adaptive Linear Neuron). La Adaline y una versión de dos capas, llamada
"Madaline", fueron utilizadas en distintas aplicaciones como reconocimiento de voz y
caracteres, predicción del tiempo, control adaptativo y sobre todo en el desarrollo de
filtros adaptativos que eliminen los ecos de las líneas telefónicas.

A mediados de los años 60, Minsky y Papert pertenecientes al Laboratorio de

Investigación de Electrónica del MIT (Massachussets Institute Technology) comenzaron
un trabajo profundo de crítica al perceptron. El resultado de este trabajo, el libro
Perceptrons, era un análisis matemático del concepto del perceptron. La conclusión de
este trabajo, que se transmitió a la comunidad científica del mundo entero, es que el

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 7

Tema 1.- Introducción a la Computación Neuronal

Perceptron y la Computación Neuronal no eran temas interesantes que estudiar y

desarrollar. A partir de este momento descendieron drásticamente las inversiones en la
investigación de la computación neuronal.

Uno de los pocos investigadores que continuaron con su trabajo en la computación

neuronal tras la publicación del libro Perceptrons fue James Anderson. Su trabajo se
basó en el desarrollo de un modelo lineal que consiste en un modelo asociativo
distribuido basado en el principio de Hebb (las conexiones son reforzadas cada vez que
son activadas las neuronas). Una versión extendida de este modelo lineal es el llamado
modelo Brain-State-in- a Box (BSB).

Teuvo Kohonen, de la Universidad de Helsinki, es uno de los mayores impulsores de la

computación neuronal de la década de los 70. De su trabajo de investigación destacan
dos aportaciones: la primera es la descripción y análisis de una clase grande de reglas
adaptativas, reglas en las que las conexiones ponderadas se modifican de una forma
dependiente de los valores anteriores y posteriores de las sinapsis. Y la segunda
aportación es el principio de aprendizaje competitivo en el que los elementos compiten
por responder a un estímulo de entrada, y el ganador se adapta él mismo para responder
con mayor efecto al estímulo.

Otro investigador que continuó con su trabajo de investigación en el mundo de la

computación neuronal a pesar del mal presagio que indicaron Minsky y Papert fue
Stephen Grossberg. Grossberg estaba especialmente interesado en la utilización de datos
de la neurología para construir modelos de computación neuronal. La mayoría de sus
reglas y postulados derivaron de estudios fisiológicos. Su trabajo ha constituido un gran
impulso en la investigación del diseño y construcción de modelos neuronales. Una de
estas clases de redes es la Adaptive Resonance Theory (ART).

En 1982 John Hopfield con la publicación del artículo Hopfield Model o Crossbar
Associative Network, junto con la invención del algoritmo Backpropagation se
consiguió devolver el interés y la confianza en el fascinante campo de la computación
neuronal tras dos décadas de casi absoluta inactividad y desinterés.

Hopfield presenta un sistema de computación neuronal consistente en elementos

procesadores interconectados que buscan y tienden a un mínimo de energía. Esta red
con este tipo de función de energía y mecanismo de respuesta no es mas que un caso de
la clase genérica de redes que consideró Grossberg.

Investigación de hoy en día.-

Existen muchos grupos con sede en diferentes universidades de todo el mundo que están
realizando trabajos de investigación en el área de las redes neuronales artificiales. Cada
grupo tiene diferente énfasis y motivación con los neurólogos, psicólogos del
conocimiento, físicos, programadores y matemáticos. Todos ellos ofrecen nuevos
puntos de vista e intuiciones en esta área de la técnica.

Grossberg continua trabajando en compañía de Carpenter en la Universidad de Boston,

mientras Teuvo Kohonen está en la Universidad de Helsinki. Uno de los mayores

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 8

Tema 1.- Introducción a la Computación Neuronal

grupos de investigación de los últimos años ha sido el grupo PDP (Parallel Distributed
Processing) formado por Rumelhart, McClelland y Hinton.

Rumelhart de la Universidad de Stanford es uno de los principales impulsores de la red

más utilizada en la mayoría de las aplicaciones actuales, la famosa red neuronal
Backpropagation. En la Universidad de Carnegie-Mellon, el grupo de investigación a la
cabeza con McClelland destaca por el estudio de las posibles aplicaciones de la
Backpropagation. Y en la Universidad de Toronto, Hinton y Sejnowski han desarrollado
una máquina llamada Boltzman que consiste en la red de Hopfield con dos
modificaciones significativas.

Bart Kosko ha diseñado una red llamada BAM (Bidirectional Associate Memory)
basado en la red de Grossberg. Por último indicar la existencia de grandes grupos de
investigación como los de California Institute of Technology, Massachussets Institute of
Technology, University of California Berkeley y University of California San Diego.

Conviene no olvidar el esfuerzo económico y técnico que están realizando las empresas
privadas tanto en USA como en Japón y en la Comunidad Económica Europea. Como
botón de muestra de las inversiones en estos países baste conocer que sólo en USA se
gasta más de 100 millones de dólares al año.

1.6.- APLICACIONES DE LAS REDES NEURONALES

ARTIFICIALES

Las características especiales de los sistemas de computación neuronal permiten que sea
utilizada esta nueva técnica de cálculo en una extensa variedad de aplicaciones.

La computación neuronal provee un acercamiento mayor al reconocimiento y

percepción humana que los métodos tradicionales de cálculo. Las redes neuronales
artificiales presentan resultados razonables en aplicaciones donde las entradas presentan
ruido o las entradas están incompletas. Algunas de las áreas de aplicación de las ANN
son las siguientes:

Análisis y Procesado de señales Reconocimiento de Imágenes

Control de Procesos Filtrado de ruido

Robótica Procesado del Lenguaje

Diagnósticos médicos Otros

Conversión Texto a Voz: uno de los principales promotores de la computación

neuronal en esta área es Terrence Sejnowski. La conversión texto-voz consiste en
cambiar los símbolos gráficos de un texto en lenguaje hablado. El sistema de
computación neuronal presentado por Sejnowski y Rosemberg, el sistema llamado

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 9

Tema 1.- Introducción a la Computación Neuronal

NetTalk, convierte texto en fonemas y con la ayuda de un sintetizador de voz (Dectalk)

genera voz a partir de un texto escrito.

La ventaja que ofrece la computación neuronal frente a las tecnologías tradicionales en

la conversión texto-voz es la propiedad de eliminar la necesidad de programar un
complejo conjunto de reglas de pronunciación en el ordenador. A pesar de que el
sistema NetTalk ofrece un buen comportamiento, la computación neuronal para este
tipo de aplicación abre posibilidades de investigación y expectativas de desarrollo
comercial.

Procesado Natural del Lenguaje: incluye el estudio de cómo se construyen las

reglas del lenguaje. Los científicos del conocimiento Rumelhart y McClelland han
integrado una red neuronal de proceso natural del lenguaje. El sistema realizado ha
aprendido el tiempo verbal pass tense de los verbos en Inglés. Las características
propias de la computación neuronal como la capacidad de generalizar a partir de datos
incompletos y la capacidad de abstraer, permiten al sistema generar buenos pronósticos
para verbos nuevos o verbos desconocidos.

Compresión de Imágenes: la compresión de imágenes es la transformación de

los datos de una imagen a una representación diferente que requiera menos memoria o
que se pueda reconstruir una imagen imperceptible. Cottrel, Munro y Zisper de la
Universidad de San Diego y Pisttburgh han diseñado un sistema de compresión de
imágenes utilizando una red neuronal con un factor de compresión de 8:1.

Reconocimiento de Caracteres: es el proceso de interpretación visual y de

clasificación de símbolos. Los investigadores de Nestor, Inc. han desarrollado un
sistema de computación neuronal que tras el entrenamiento con un conjunto de tipos de
caracteres de letras, es capaz de interpretar un tipo de carácter o letra que no haya visto
con anterioridad.

Reconocimiento de Patrones en Imágenes: una aplicación típica es la

clasificación de objetivos detectados por un sonar. Existen varias ANN basadas en la
popular Backpropagation cuyo comportamiento es comparable con el de los operadores
humanos. Otra aplicación normal es la inspección industrial.

Problemas de Combinatoria: en este tipo de problemas la solución mediante

cálculo tradicional requiere un tiempo de proceso (CPU) que es exponencial con el
número de entradas. Un ejemplo es el problema del vendedor; el objetivo es elegir el
camino más corto posible que debe realizar el vendedor para cubrir un número limitado
de ciudades en una área geográfica específica. Este tipo de problema ha sido abordado
con éxito por Hopfield y el resultado de su trabajo ha sido el desarrollo de una ANN que
ofrece buenos resultados para este problema de combinatoria.

Procesado de la Señal: en este tipo de aplicación existen tres clases diferentes

de procesado de la señal que han sido objeto de las ANN como son la predicción, el
modelado de un sistema y el filtrado de ruido.

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 10

Tema 1.- Introducción a la Computación Neuronal

Predicción: en el mundo real existen muchos fenómenos de los que conocemos

su comportamiento a través de una serie temporal de datos o valores. Lapedes y Farber
del Laboratorio de Investigación de los Álamos, han demostrado que la red
backpropagation supera en un orden de magnitud a los métodos de predicción
polinómicos y lineales convencionales para las series temporales caóticas.

Modelado de Sistemas: los sistemas lineales son caracterizados por la función

de transferencia que no es más que una expresión analítica entre la variable de salida y
una variable independiente y sus derivadas. Las ANN también son capaces de aprender
una función de transferencia y comportarse correctamente como el sistema lineal que
está modelando.

Filtro de Ruido: las ANN también pueden ser utilizadas para eliminar el ruido
de una señal. Estas redes son capaces de mantener en un alto grado las estructuras y
valores de los filtros tradicionales.

Modelos Económicos y Financieros: una de las aplicaciones más importantes

del modelado y pronóstico es la creación de pronósticos económicos como por ejemplo
los precios de existencias, la producción de las cosechas, el interés de las cuentas, el
volumen de las ventas etc. Las redes neuronales están ofreciendo mejores resultados en
los pronósticos financieros que los métodos convencionales.

ServoControl: un problema difícil en el control de un complejo sistema de

servomecanismo es encontrar un método de cálculo computacional aceptable para
compensar las variaciones físicas que se producen en el sistema. Entre los
inconvenientes destaca la imposibilidad en algunos casos de medir con exactitud las
variaciones producidas y el excesivo tiempo de cálculo requerido para la obtención de la
solución matemática. Existen diferentes redes neuronales que han sido entrenadas para
reproducir o predecir el error que se produce en la posición final de un robot. Este error
se combina con la posición deseada para proveer una posición adaptativa de corrección
y mejorar la exactitud de la posición final.

1.7.- IMPLEMENTACIÓN Y TECNOLOGÍAS EMERGENTES

El resurgimiento de la computación neuronal en los últimos años se ha producido por el

desarrollo teórico de nuevos modelos matemáticos del comportamiento del cerebro y
por el desarrollo de nuevas tecnologías que ya están siendo utilizadas en una gran
variedad de aplicaciones comerciales.

Entre los avances o desarrollos tecnológicos que permiten la realización de la

computación neuronal destacan los programas software de simulación, los aceleradores
hardware, los chips de silicio y los procesadores ópticos.

Simuladores Software: constituyen una de las formas más versátiles con las que
se pueden implementar redes neuronales. Estos programas constituyen todo un sistema
de desarrollo y realización de prototipos de redes neuronales. Estos programas se

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 11

Tema 1.- Introducción a la Computación Neuronal

utilizan para diseñar, construir, entrenar y probar redes neuronales artificiales para
resolver problemas complejos y problemas del mundo real.

Los primeros simuladores software se ejecutaban en ordenadores de grandes

prestaciones y el avance de los ordenadores personales en capacidad de procesado y
capacidad de memoria hace posible que exista una serie de simuladores software de
grandes prestaciones que corren sobre ordenadores personales. Entre otros paquetes
software se incluye Neural Works, Neuralyst, Explore Net y Kwowledge Net.

Aceleradores Hardware: la naturaleza paralela de la computación neuronal se

presta a realizar diseños concretos y a medida de dispositivos físicos, aceleradores
hardware, que aceleren la ejecución de los cálculos. Los aceleradores hardware para los
sistemas de computación neuronal son dispositivos físicos constituidos por diferentes
procesadores interconectados que ayudan a la realización y ejecución del
comportamiento de las ANN. Una de las ventajas de los aceleradores hardware
diseñados específicamente para la computación neuronal es el aumento de la velocidad
de procesado. Esta característica permite la utilización de las ANN en aplicaciones de
tiempo real.

Robert Hecht-Nielsen desarrolló el acelerador hardware Mark III que constaba de 8100
procesadores y trabajaba como un periférico de un VAX. La mayoría de las casas
comerciales dedicadas al diseño de las ANN han desarrollado diferentes tarjetas basadas
en los diferentes procesadores existentes, diseñadas para trabajar en el entorno de un
ordenador personal PC y presentando un progresivo ratio de actualizaciones de
interconexiones por segundo.

Chips de Silicio: Otro de los campos de la investigación en el mundo de las

ANN al margen de los simuladores software y aceleradores hardware, es la integración
de todos los componentes de computación neuronal en un chip de silicio. Un ejemplo
concreto es el chip Electronic Neural Network (EEN) de la compañía AT&T que
contiene 256 transistores-neuronas y más de 100.000 resistencias-sinapsis. Actualmente
este chip está siendo utilizado para aplicaciones de compresión del ancho de banda de
imágenes de vídeo para poder ser transmitidas por una línea telefónica. Existen muchas
compañías y centros de investigación que están trabajando en el desarrollo de circuitos
integrados que realizan computación neuronal. La mayoría de las aplicaciones de estos
chips está siendo la simulación de procesos sensitivos como la visión de imágenes y la
audición de sonidos.

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 12

Tema 2.- Fundamentos de las Redes Neuronales Artificiales

FUNDAMENTOS DE LAS REDES

NEURONALES ARTIFICIALES

2
2.1. El Prototipo Biológico
2.2. La Neurona Artificial
2.3. Redes Neuronales Artificiales de una capa y Multicapa
2.4. Entrenamiento de las Redes Neuronales Artificiales

TEMA 2.- FUNDAMENTOS DE LAS REDES

NEURONALES ARTIFICIALES

2.1.- EL PROTOTIPO BIOLÓGICO

Las diferentes configuraciones y algoritmos que se diseñan para las redes neuronales
artificiales están inspiradas en la organización del complejo sistema neuronal del
cerebro humano. No obstante conviene aclarar que esta inspiración no supone que las
ANN lleguen a emular al cerebro como algunos optimistas lo desean ya que entre otras
limitaciones el conocimiento sobre el modo de funcionamiento y comportamiento del
cerebro es bastante simple y reducido. De hecho los diseñadores de redes artificiales van
más lejos del conocimiento biológico actual y prueban nuevas estructuras que presentan
un comportamiento adecuado y útil.

El sistema nervioso humano constituido por células llamadas neuronas presenta una
estructura muy compleja. El número estimado de neuronas es de 1011 y las
interconexiones entre ellas son del orden de 1015 .

Cada neurona comparte muchas características con otras células del cuerpo humano
pero tiene propiedades particulares y especiales para recibir, procesar y transmitir
señales electroquímicas a través de todas las interconexiones del sistema de
comunicación del cerebro.

La Figura (2.1) muestra la estructura de un par de neuronas biológicas. Del cuerpo de la

neurona se extienden las dendritas hacia otras neuronas donde reciben las señales
transmitidas por otras neuronas. El punto de contacto o de conexión se llama sinapsis y

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 13

Tema 2.- Fundamentos de las Redes Neuronales Artificiales

estas entradas son dirigidas al núcleo donde se suman. Algunas de las entradas tienden a
excitar a la célula y otras sin embargo tienden a inhibir la célula. Cuando la excitación
acumulada supera un valor umbral, las neuronas envían una señal a través del axón a
otras neuronas.

La mayoría de los modelos de las ANN presenta este funcionamiento básico de la

neurona aun cuando el comportamiento real de una célula nerviosa tiene muchas
complejidades y excepciones.

Figura (2.1) - Componentes de una Neurona.

2.2.- LA NEURONA ARTIFICIAL

La neurona artificial fue diseñada para "emular" las características del funcionamiento
básico de la neurona biológica. En esencia, se aplica un conjunto de entradas a la
neurona, cada una de las cuales representa una salida de otra neurona. Cada entrada se
multiplica por su "peso" o ponderación correspondiente análogo al grado de conexión
de la sinapsis. Todas las entradas ponderadas se suman y se determina el nivel de
excitación o activación de la neurona. Una representación vectorial del funcionamiento
básico de una neurona artificial se indica según la siguiente expresión de la ecuación
(2.1).

NET = X*W ecu.(2.1)

Siendo NET la salida, X el vector de entrada y W el vector de pesos.

Normalmente la señal de salida NET suele ser procesada por una función de activación
F para producir la señal de salida de la neurona OUT. La función F puede ser una
función lineal, o una función umbral o una función no lineal que simula con mayor
exactitud las características de transferencia no lineales de las neuronas biológicas.

La Figura (2.2) representa una neurona artificial con una función de activación F.

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 14

Tema 2.- Fundamentos de las Redes Neuronales Artificiales

Figura (2.2) - Modelo de Neurona Artificial .

Las funciones F más utilizadas son la función Sigmoid y Tangente hiperbólica

expresadas en la Tabla (2.1).

Sigmoid OUT = 1 / (1+e^-NET)

Tangente hiperbólica OUT = tanh (NET)

Tabla 2.1 - Funciones de Activación

Este tipo de modelo de neurona artificial ignora muchas de las características de las
neuronas biológicas. Entre ellas destaca la omisión de retardos y de sincronismo en la
generación de la salida. No obstante, a pesar de estas limitaciones las redes construidas
con este tipo de neurona artificial presentan cualidades y atributos con cierta similitud a
la de los sistemas biológicos.

2.3.- REDES NEURONALES ARTIFICIALES DE UNA CAPA Y

MULTICAPA

La capacidad de cálculo y potencia de la computación neuronal proviene de las

múltiples conexiones de las neuronas artificiales que constituyen las redes ANN.

La red más simple es un grupo de neuronas ordenadas en una capa como se muestra en
la Figura (2.3). Los nodos circulares sólo son distribuidores de las entradas y no se
consideran constituyentes de una capa.

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 15

Tema 2.- Fundamentos de las Redes Neuronales Artificiales

Figura (2.3) - Red Neuronal de una Capa.

Cada una de las entradas está conectada a través de su peso correspondiente a cada
neurona artificial. En la práctica existen conexiones eliminadas e incluso conexiones
entre las salidas y entradas de las neuronas de una capa. No obstante la figura muestra
una conectividad total por razones de generalización.

Normalmente las redes más complejas y más grandes ofrecen mejores prestaciones en el
cálculo computacional que las redes simples. Las configuraciones de las redes
construidas presentan aspectos muy diferentes pero tienen un aspecto común, el
ordenamiento de las neuronas en capas o niveles imitando la estructura de capas que
presenta el cerebro en algunas partes.

Las redes multicapa se forman con un grupo de capas simples en cascada. La salida de
una capa es la entrada de la siguiente capa. Se ha demostrado que las redes multicapa
presentan cualidades y aspectos por encima de las redes de una capa simple. La Figura
(2.4) muestra una red de dos capas.

Figura (2.4) - Red Neuronal de dos Capas.

Conviene destacar que la mejora de las redes multicapa estriba en la función de

activación no lineal entre capas, pudiéndose llegar al caso de diseñar una red de una

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 16

Tema 2.- Fundamentos de las Redes Neuronales Artificiales

capa simple equivalente a una red multicapa si no se utiliza la función no lineal de

activación entre capas.

2.4.- ENTRENAMIENTO DE LAS REDES NEURONALES

ARTIFICIALES

Una de las principales características de las ANN es su capacidad de aprendizaje. El

entrenamiento de las ANN muestra algunos paralelismos con el desarrollo intelectual de
los seres humanos. No obstante aun cuando parece que se ha conseguido entender el
proceso de aprendizaje conviene ser moderado porque el aprendizaje de las ANN está
limitado.

El objetivo del entrenamiento de una ANN es conseguir que una aplicación

determinada, para un conjunto de entradas produzca el conjunto de salidas deseadas o
mínimamente consistentes. El proceso de entrenamiento consiste en la aplicación
secuencial de diferentes conjuntos o vectores de entrada para que se ajusten los pesos de
las interconexiones según un procedimiento predeterminado. Durante la sesión de
entrenamiento los pesos convergen gradualmente hacia los valores que hacen que cada
entrada produzca el vector de salida deseado.

Los algoritmos de entrenamiento o los procedimientos de ajuste de los valores de las

conexiones de las ANN se pueden clasificar en dos grupos: Supervisado y No
Supervisado.

Entrenamiento Supervisado: estos algoritmos requieren el emparejamiento de

cada vector de entrada con su correspondiente vector de salida. El entrenamiento
consiste en presentar un vector de entrada a la red, calcular la salida de la red,
compararla con la salida deseada, y el error o diferencia resultante se utiliza para
realimentar la red y cambiar los pesos de acuerdo con un algoritmo que tiende a
minimizar el error.

Las parejas de vectores del conjunto de entrenamiento se aplican secuencialmente y de

forma cíclica. Se calcula el error y el ajuste de los pesos por cada pareja hasta que el
error para el conjunto de entrenamiento entero sea un valor pequeño y aceptable.

Entrenamiento No Supervisado: los sistemas neuronales con entrenamiento

supervisado han tenido éxito en muchas aplicaciones y sin embargo tienen muchas
críticas debido a que desde el punto de vista biológico no son muy lógicos. Resulta
difícil creer que existe un mecanismo en el cerebro que compare las salidas deseadas
con las salidas reales. En el caso de que exista, ¿de dónde provienen las salidas
deseadas?

Los sistemas no supervisados son modelos de aprendizaje más lógicos en los sistemas
biológicos. Desarrollados por Kohonen (1984) y otros investigadores, estos sistemas de
aprendizaje no supervisado no requieren de un vector de salidas deseadas y por tanto no
se realizan comparaciones entre las salidas reales y salidas esperadas. El conjunto de

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 17

Tema 2.- Fundamentos de las Redes Neuronales Artificiales

vectores de entrenamiento consiste únicamente en vectores de entrada. El algoritmo de

entrenamiento modifica los pesos de la red de forma que produzca vectores de salida
consistentes. El proceso de entrenamiento extrae las propiedades estadísticas del
conjunto de vectores de entrenamiento y agrupa en clases los vectores similares.

Existe una gran variedad de algoritmos de entrenamiento hoy en día. La gran mayoría
de ellos han surgido de la evolución del modelo de aprendizaje no supervisado que
propuso Hebb (1949). El modelo propuesto por Hebb se caracteriza por incrementar el
valor del peso de la conexión si las dos neuronas unidas son activadas o disparadas. La
ley de Hebb se representa según la ecuación (2.2).

wij (n + 1) = wij (n) + α OUTi OUTj ecu.(2.2)

Curso: Redes Neuronales Artificiales y sus Aplicaciones © Xabier Basogain Olabe 18