8/16/2019 Procesos Inteligentes 1ra Fase
1/117
PROCESOS INTELIGENTESIngeniería Mecatrónica - UCSM
M.Sc. Sergio Mestas Ramos
8/16/2019 Procesos Inteligentes 1ra Fase
2/117
¿ QUÉ ES LA INTELIGENCIA ARTIFICIAL ?
8/16/2019 Procesos Inteligentes 1ra Fase
3/117
Inteligencia Artificial – Intentos de Definición
- Bellman (1978)- Automatización de actividades que vinculamos con procesos delpensamiento humano, tales como, toma de decisiones, resoluciónde problemas, aprendizaje.
- Winston (1992).- Estudio de las computaciones que permiten percibir, razonar y
actuar.
- Minsky (1986)- Arte de construir máquinas capaces de hacer cosas que requieren
inteligencia en caso de que fuesen hechas por seres humanos.
- Luger (1989)- Rama de la informática que trata de la automatización del
comportamiento inteligente.
8/16/2019 Procesos Inteligentes 1ra Fase
4/117
La Inteligencia Artificial
Es un campo de la ciencia que trata de realizar, conmáquinas, tareas que pueden ser realizadas por elhombre, aplicando cualquier tipo de razonamiento.
En cierta media cualquier programa de computador puede considerarse inteligente. El problema esdiferenciar entre lo que se considera un “programainteligente” y el que no lo es.
Un programa inteligente es aquel que exhibe uncomportamiento similar al humano cuando se enfrentaa un problema idéntico.
8/16/2019 Procesos Inteligentes 1ra Fase
5/117
Sistemas que PIENSAN como humanos Sistemas que PIENSAN racionalmente
“El nuevo y exitante esfuerzo de hacer que los
computadores piensen”“La automatización de actividades que
vinculamos con procesos de pensamientohumano, actividades como la toma dedecisiones, resolución de problemas,aprendizaje..”
“El estudios de las facultades mentales
mediante el uso de modelos computacionales”“El estudio de los cálculos que hacen posible
percibir, razonar y actuar”
Sistemas que ACTÚAN como humanos Sistemas que ACTÚAN racionalmente
“Desarrollar máquinas con capacidad para
realizar funciones que cuando son realizadas por personas requieren de inteligencia”
“El estudio de cómo lograr que loscomputadores realicen tareas, que por elmomento, los humanos hacen mejor”
“La inteligencia Computacional es el estudio
del diseño de agentes inteligentes”
“Está relacionada con conductas inteligentes en
artefactos”
8/16/2019 Procesos Inteligentes 1ra Fase
6/117
Pensar como un humano- Es necesario contar con un mecanismo para determinar cómo
piensan los humanos- Una vez que se tenga una teoría al respecto, se podrá expresar
esa teoría en la forma de un programa de computadoras
- Si los datos de E/S y los tiempos de reacción del programa sonsimilares a los de un humano existe la evidencia de que algunos de
los mecanismos del programa se pueden comparar con los del loshumanos
- Ciencia cognitiva: Convergen modelos computacionales de IA ytécnicas experimentales de psicología intentando elaborar teoríasprecisas y verificables sobre el funcionamiento de la mente
humana
8/16/2019 Procesos Inteligentes 1ra Fase
7/117
Pensar racionalmente- Intentar codificar la “manera correcta de pensar”. Un proceso de
razonamiento irrefutable
- Aristóteles fue uno de los primeros, a través de sus silogísmos(esquemas de estructuras de argumentación en las que siempre sellega a conclusiones correctas si partimos de premisas correctas)
- Lógica. Notación precisa para definir sentencias sobre todo tipo de
elementos del mundo y especificar relaciones entre ellos- Ya en 1965 habían programas que resolvían cualquier problemaque pudiera expresarse mediante la notación de la lógica
- No es fácil transformar conocimiento informal y expresarlo entérminos formales, sobre todo cuando el conocimiento es inferior al
100%- Es diferente a resolver un problema “en principio” y hacerlo en lapráctica. Hay problemas que aún con unos pocos datos puedenagotar los recursos computacionales
8/16/2019 Procesos Inteligentes 1ra Fase
8/117
Actuar racionalmente- Un enfoque basado en agentes. Algo que razona- Los agentes informáticos se deben distinguir de los programas
convencionales
- Perciben su entorno. Persisten en el tiempo. Se adaptan a loscambios y son capaces de alcanzar objetivos diferentes
- Un agente racional actúan con la intención de alcanzar el mejor resultado, ó cuando hay incertidumbre, el mejor resultadoesperado.
- Las habilidades que se necesitan en la prueba de Turing debenpermitir emprender acciones racionales
- Es necesario contar con la capacidad para representar elconocimiento y razonar basándonos en él
- El enfoque de la IA basados en las leyes del pensamiento ponetodo el énfasis en hacer inferencias correctas, lo cual podríaconsiderarse como racional. Sin embargo una inferencia correcta
no depende siempre de la racionalidad. Hay situaciones en las queno hay nada correcto que hacer y es necesario tomar una decisiónTambién hay maneras de actuar racionalmente que no implicanrealizar inferencias
8/16/2019 Procesos Inteligentes 1ra Fase
9/117
Inteligencia Artificial – Como surge
8/16/2019 Procesos Inteligentes 1ra Fase
10/117
Prueba de Turing
- Alan Turing. 1950- Proporciona una definición operacional y satisfactoria
de Inteligencia
- Prueba basada en la incapacidad de diferenciar entre
entidades artificiales y seres humanos- En la actualidad, programar una computadora para
que supere la prueba requiere un trabajo considerable
- El computador supera la prueba si un evaluador
humano no es capaz de distinguir si las respuestas auna serie de preguntas, son de una persona ó no.
8/16/2019 Procesos Inteligentes 1ra Fase
11/117
Capacidades que debe tener la computadora:
Procesamiento de lenguaje natural: Para poder comunicarsesatisfactoriamente en lenguaje natural
Representación del conocimiento: Para almacenar lo que seconoce ó siente
Razonamiento automático: Para utilizar el conocimientoalmacenado para responder a preguntas y extraer nuevasconclusiones
Aprendizaje automático: Para adaptarse a nuevas circunstancias
y para detectar y extrapolar patrones
8/16/2019 Procesos Inteligentes 1ra Fase
12/117
Capacidades que debe tener la computadorapara la interacción física entre el evaluador y el
computador:
Prueba Global de Turing:
Visión computacional Para percibir objetosRobótica: Para manipular y mover objetos
8/16/2019 Procesos Inteligentes 1ra Fase
13/117
8/16/2019 Procesos Inteligentes 1ra Fase
14/117
Fundamentos de la IA
8/16/2019 Procesos Inteligentes 1ra Fase
15/117
Fundamentos de la IAFilosofía
¿Existen reglas formales para extraer conclusiones válidas?. ¿Cómo segenera la inteligencia mental? ¿De donde viene el conocimiento?¿Cómo se pasa del conocimiento a la acción?
Silogísmos: Aristóteles. Extracción de conclusiones mecánicamentea partir de premisas iniciales)
Dualismo: Descartes. Existe una parte de la mente que está al
margen de la naturaleza. Los animales no poseen estacualidad dual; e igualmente a las máquinas)Materialismo: Las operaciones del cerebro realizadas de acuerdo con
las leyes de la física constituyen la mente)Empírico: Nada existe en la mente que no haya pasado por los
sentidosInducción: Las reglas generales se obtienen mediante la exposición
a asociaciones repetidas entre sus elementosPositivismo lógico: Todo el conocimiento se puede caracterizar
mediante teorías lógicas relacionadasTeoría de la confirmación: Intenta explicar cómo el conocimiento se
obtiene a partir de la experiencia
8/16/2019 Procesos Inteligentes 1ra Fase
16/117
8/16/2019 Procesos Inteligentes 1ra Fase
17/117
8/16/2019 Procesos Inteligentes 1ra Fase
18/117
Fundamentos de la IA
Neurociencia¿Cómo procesa información el cerebro?
Neurociencia: Estudio del sistema neurológico y enespecial el cerebro. La forma exacta en
que el cerebro genera los pensamientos.Neuronas: El cerebro está formado por células
nerviosas llamadas neuronas que han sidoobservadas y estudiadas individualmente
8/16/2019 Procesos Inteligentes 1ra Fase
19/117
Fundamentos de la IA
Psicología¿Cómo piensan y actúan los humanos y los animales?
Conductismo: Rechaza cualquier teoría en la que intervenganprocesos mentales. Insistieron en el estudio exclusivo de
mediciones objetivas de percepciones (estímulos) y de lasacciones resultantes (respuestas)
Psicología cognitiva: Conceptualización del cerebro como undispositivo de procesamiento de Información. Pone énfasis en quela percepción entraña cierto tipo de inferencia lógica inconsciente
Ciencia cognitiva: Utilización de modelos informáticos paramodelar la psicología de la memoria, el lenguaje y el pensamientológico.
8/16/2019 Procesos Inteligentes 1ra Fase
20/117
Fundamentos de la IA
Ingeniería Computacional¿Cómo se puede construir un computador eficiente?
Computadora: La IA necesita además de Inteligencia y un Artefacto (la computadora).
Hardware: Cada generación de dispositivos ha conllevado aun aumento en la velocidad de proceso ycapacidad de almacenamiento
Software: Los Sistemas operativos, los lenguajes de progra-mación y las herramientas modernas para escribir
programas. La investigación en IA ha generadonumerosas ideas importantes: Tiempo compartido,intérpretes imperativos, interfases gráficas,entornos de desarrollo rápido, programaciónsimbólica, funcional, dinámica, orientada a objetos.
8/16/2019 Procesos Inteligentes 1ra Fase
21/117
Fundamentos de la IA
Teoría del Control y cibernética¿Cómo pueden los artefactos operar bajo su propio control?
Teoría del control: Ver el comportamiento determinista comoalgo emergente de un mecanismo
regulador que intenta minimizar el “error”(la diferencia entre el estado actual y elobjetivo)
Cibernética: Modelos cognitivos matemáticos ycomputacionales
Función objetivo: Teoría del control moderna, basados endiseñar sistemas que maximizan unafunción objetivo en el tiempo.
8/16/2019 Procesos Inteligentes 1ra Fase
22/117
Fundamentos de la IA
Lingüística¿Cómo está relacionado el lenguaje con el pensamiento?
Lingüística computacional: Convergencia entre la lingüísticamoderna y la IA (procesamiento
de lenguaje natural)
8/16/2019 Procesos Inteligentes 1ra Fase
23/117
Historia de la IAPeríodo de Gestación (1943-1956)
• Modelo de neuronas artificiales (1943)
• Reglas de actualización de aprendizaje (1949)
• Programas de ajedrez para computadoras (1950,1953)
• Primera computadora para simular una red de 40 neuronas a
partir de un computador de tubos de vacío (1951)• Lenguaje LISP. Primer lenguaje de IA (1958)
Reunión en el Darmouth College (1956)
• Programa capaz de demostrar teoremas de lógica
• Aparece por primera vez el término: “Inteligencia Artificial”
8/16/2019 Procesos Inteligentes 1ra Fase
24/117
Historia de la IAEntusiasmo y grandes expectativas (1952-1965)
• GPS. Solucionador general de problemas. Aborda un problemacomo un conjunto de subproblemas y posibles cursos de acción.
• Juego de damas con aprendizaje de la experiencia de laspartidas jugadas (1952)
• Contribuciones de McCarthy en el MIT. LISP Compartido ydesarrollo del EC (programa que incorpora conceptos derepresentación y conocimiento) (1958)
• Contribuciones de McCarthy en Stanford. Sistema deplanificación y respuesta de preguntas (1969). Solución a
problemas limitados (micromundos ANALOGY: analogíageométrica)
8/16/2019 Procesos Inteligentes 1ra Fase
25/117
Historia de la IADosis de Realidad (1966-1974)
• Se predijo que en 10 años habría una máquina inteligente
• Teoría de NP-Completos
• Programa ELIZA, en el MIT, que simulaba el comportamiento deun psicoanalista (1965)
• Experimentos en Machine Evolution (ahora llamados algoritmosgenéticos)
• Perceptrones. Tipo de redes neuronales (1969)
8/16/2019 Procesos Inteligentes 1ra Fase
26/117
Historia de la IASistemas basados en conocimientos (1969-1979)
• Dendral. Sistema para inferir estructuras moleculares
• Mycin. Sistema para el diagnóstico médico de enfermedadessanguíneas
• Se modela la incertidumbre• HPP. Proyecto de programación heurística
• SHDRLU. Sistema para la comprensión del lenguaje natural.
• Lenguaje PROLOG (1972)
8/16/2019 Procesos Inteligentes 1ra Fase
27/117
Historia de la IAIA como industria (1980-1988)• R1. Primer sistema experto comercial, para la elaboración de pedidos• Proyecto de quinta generación en Japón (máquina PROLOG)• Máquinas optimizadas para ejecutar LISP• Se produce un impacto industrial en los campos como la robótica y la
visión artificial
Regreso a las redes neronales (1986-presente)• Hopfield. Rumelhart y Hinton. Nuevos modelos de RN• Reconocimiento de voz (HMM)• Incertidumbre (Bayes)• Robótica• Aprendizaje• Realidad virtual
8/16/2019 Procesos Inteligentes 1ra Fase
28/117
8/16/2019 Procesos Inteligentes 1ra Fase
29/117
8/16/2019 Procesos Inteligentes 1ra Fase
30/117
TÉCNICAS DE INTELIGENCIA ARTIFICIAL
o Redes neuronales artificiales (RNA)o Razonamiento Basados En Casos (RCB)o Algoritmos Genéticos (AG)o Lógica Difusa (LD)
• Sistemas Multiagente• Sistemas Basados en Conocimiento.• Visión Computacional• Procesamiento de Voz y Lenguaje Natural• Computación Evolutiva•
Robótica• Aprendizaje Mecánico.• Técnicas Heurísticas (recocido simulado)
8/16/2019 Procesos Inteligentes 1ra Fase
31/117
REDES NEURONALES ARTIFICIALES (RNA)
Basadas en la hipótesis de Hebb (1949): Presenta demanera intuitiva el modo en que las neuronasmemorizan información y se plasman sintéticamente enla famosa regla de aprendizaje de Hebb.
Esta regla indica que las conexiones entre dosneuronas se refuerzan si ambas son activadas.Muchos de los algoritmos actuales proceden de los
conceptos de este psicólogo.
Son utilizadas básicamente para problemas declasificación de patrones y agrupamiento (clustering)
8/16/2019 Procesos Inteligentes 1ra Fase
32/117
8/16/2019 Procesos Inteligentes 1ra Fase
33/117
ALGORITMOS GENÉTICOS (AG)
• Es una técnica de búsqueda basada en la teoría de la evolución deDarwin.• Se basa en los mecanismos de selección que utiliza la naturaleza:
• Los individuos más aptos de una población son los que sobreviven puesse adaptan más fácilmente a los cambios que se producen en su
• entorno.
• Los cambios se traducen en transformaciones en los genes de unindividuo (unidad básica de codificación de cada uno de los atributos deun ser vivo)
• Las características más destacadas de un individuo (p.e, los que lepermiten adaptarse mejor a su entorno) se deben transmitir a susdescendientes.
• Un AG empieza por uno o varios individuos y mediante operaciones detransformación y selección va haciendo evolucionar su especie,desarrollando individuos mejores.
8/16/2019 Procesos Inteligentes 1ra Fase
34/117
8/16/2019 Procesos Inteligentes 1ra Fase
35/117
Agentes
Un agente es todo aquelloque puede considerarseque percibe su ambiente
mediante sensores y queresponde o actúa en talambiente por medio de
efectores.
8/16/2019 Procesos Inteligentes 1ra Fase
36/117
Agentes Naturales
• Agente: cuerpo biológico
• Entorno: naturaleza
• Sensores: ojos, oídos, lengua, piel, etc.
• Efectores: piernas, brazos, manos, etc.
• Medida de rendim iento: sobrevivir, reproducirse,
8/16/2019 Procesos Inteligentes 1ra Fase
37/117
Agentes artificiales
• Agentes hardware (robots):
• Interactúan directamente con un entorno físico
• Disponen de un “cuerpo” físico
• Sensores: cámaras, telémetros infrarojos, etc.
• Efectores: ruedas/piernas, manipuladores, etc.
8/16/2019 Procesos Inteligentes 1ra Fase
38/117
Agentes artificiales
• Agentes software (softbots):
• Actúan en entornos virtuales (p.e. Internet)
• Todo software: no necesitan manipular físicamente el
entorno
• Sensores y efectores: dependientes del entorno
8/16/2019 Procesos Inteligentes 1ra Fase
39/117
Agentes inteligentes
Actúan de forma racional en su entorno
Agente Racional es el que percibe y actúa paracumplir con sus objetivos con base a sus creencias delo que es correcto
8/16/2019 Procesos Inteligentes 1ra Fase
40/117
Agente Racional …
• La racionalidad de un agente depende de cuatrofactores:• La medida del rendimiento: define el grado de éxito
del agente en el cumplimiento de sus objetivos.• La secuencia de percepciones: todo lo que hapercibido el agente hasta ese momento.
• El conocimiento del medio: todo el conocimiento que
ha acumulado en el medio en que habita.• Las acciones que el agente puede ejecutar.
8/16/2019 Procesos Inteligentes 1ra Fase
41/117
Comportamiento Racional
Comportamiento racional:
• El que se realiza a partir de la secuencia de
percepciones hasta el momento, y el conocimiento a priori sobre el entorno.
• El que elige entre las capacidades, la acción quemaximice la medida de rendimiento
8/16/2019 Procesos Inteligentes 1ra Fase
42/117
Algunas característicasadicionales:
Autonomía: Cuanto más se rige su comportamiento por su propia experiencia y
Cuanto menos depende de sus conocimientos a priori)
Aprendizaje: Cuando no sólo recopila información,sino que aprende de lo que percibe
8/16/2019 Procesos Inteligentes 1ra Fase
43/117
Entorno de trabajo de los agentes (REAS)
• Rendimiento ó metas
• Entorno ó ambiente
• Actuadores ó acciones
• Sensores ó percepciones
8/16/2019 Procesos Inteligentes 1ra Fase
44/117
REAS: Ejemplos
8/16/2019 Procesos Inteligentes 1ra Fase
45/117
PROGRAMA PARA UN AGENTE
• Es una función que, a partir de las percepciones delagente, le permite realizar las acciones. El trabajo de la IAes diseñar el programa del agente.
• Se ejecuta en algún dispositivo de cómputo, el cual esllamado arquitectura.
8/16/2019 Procesos Inteligentes 1ra Fase
46/117
Tipos de Programas para Agentes
• Agentes reactivos (reflejo) simple
• Agentes reactivos basados en modelos (con estado interno)
• Agentes basados en metas (u objetivos)
• Agentes basados en utilidad
8/16/2019 Procesos Inteligentes 1ra Fase
47/117
Agentes Reactivos Simples
Este tipo de agente nocontiene internamenteestados y sus procesos oacciones que realiza sonrespuestas a la entrada de
percepciones. Ignoran las percepciones históricas
8/16/2019 Procesos Inteligentes 1ra Fase
48/117
Agentes Reactivos SimplesUn agente reflejo simple almacena asociaciones entrada/salida
frecuentes en forma de reglas condición-acción (también reglassituación-acción o producciones).Ejemplo: La asociación:
si el coche de delante frena y sus luces
de freno se encienden, entonces elagente taxista deberá advertirlo yempezar a frenar
También se almacena de la forma:si coche-delante-frena entonces empezar-a-frenarLos humanos tenemos muchas de estas asociaciones:
reflejos innatosrespuestas aprendidas
http://turismoobjetivo.files.wordpress.com/2010/01/fila-autos-autovia-2.jpg
8/16/2019 Procesos Inteligentes 1ra Fase
49/117
Agentes reactivos basados en modelos(con estado interno)
Este tipo de agente guardaestados internos sobre la historia
percibida lo cual le sirve para
ejecutar una acción. Lossensores no nos pueden informar a la vez de todos los estados quemaneja nuestro ambiente, es por este caso que el agente necesita
actualizar algo de informaciónen el estado interno.
Agentes reactivos basados en modelos (con
8/16/2019 Procesos Inteligentes 1ra Fase
50/117
Agentes reactivos basados en modelos (conestado interno)
En ocasiones no es posible tomar una decisión a partir de una sola percepción porque los sensores no proporcionan toda la información.Ejemplo:
si el coche de delante es un modelo antiguono se podría determinar si ha frenado a partir de una única imagen
Un agente reflejo con estado interno mantiene la información quenecesita para distinguir entre estados diferentes del mundo
La percepción actual se interpreta a partir del estado anterior utilizandoinformación sobre:
cómo evoluciona el mundo independientemente del agentecómo influyen en el mundo las acciones del agente
http://images.google.com.pe/imgres?imgurl=http://www.bravocars.es/wp-content/uploads/2009/12/volkswagen_golf_led_detras.jpg&imgrefurl=http://www.bravocars.es/2009/12/10/el-volkswagen-golf-vi-ahora-con-luces-traseras-de-diodos-led/&usg=__Wi1KIwcc3iIjWjUJp-_tjUPYqro=&h=360&w=550&sz=76&hl=es&start=48&itbs=1&tbnid=Nro2eGHCBEtkSM:&tbnh=87&tbnw=133&prev=/images?q=luces+traseras&start=40&hl=es&sa=N&gbv=2&ndsp=20&tbs=isch:1
8/16/2019 Procesos Inteligentes 1ra Fase
51/117
Agentes basados en metas
Además de los estados, los agentesnecesitan cierto tipo de informaciónsobre sus metas Estas metas van adetallar las situaciones a las que se
desea llegar de este modo, el programade agente puede combinar las metascon la información de los resultados(acciones) que emprenda y de estamanera poder elegir aquellas acciones
que permitan alcanzar la meta
8/16/2019 Procesos Inteligentes 1ra Fase
52/117
Agentes basados en metasA veces no es posible tomar una decisión únicamente a
partir del estado actual del mundo.Ejemplo.Al llegar a un cruce el taxi puede realizar distintas acciones
Un agente basado en objetivos utiliza una descripción de
las metas a alcanzar que le sirve para escoger entre lasdistintas acciones posibles, por ejemplo el destino del pasajero.
La toma de decisiones basada en objetivos ≠ la toma de
decisiones basada en reglas condición-acción:tiene en cuenta el estado en el futuro
es mas flexibleLa búsqueda y la planificación son dos subáreas de la IAdedicadas a la resolución de problemas utilizando objetivos
http://images.google.com.pe/imgres?imgurl=http://farm2.static.flickr.com/1044/1448987799_38afab58d2.jpg?v=0&imgrefurl=http://www.flickr.com/photos/gonzalez-alba/1448987799/in/set-72157602157145969/&usg=__0suhUqY2k2DnonLdrp36X73k6W4=&h=500&w=437&sz=203&hl=es&start=6&itbs=1&tbnid=nk_2-Qa7gbDurM:&tbnh=130&tbnw=114&prev=/images?q=cruce+de+vias&hl=es&sa=N&gbv=2&ndsp=20&tbs=isch:1
8/16/2019 Procesos Inteligentes 1ra Fase
53/117
Agentes Basados en Utilidad
Utiliza un modelo del mundo, junto con una función deutilidad que calcula sus
preferencias entre los estados
del mundo. Después seleccionala acción que le lleve a alcanzar la mayor utilidad esperada,entre todos los resultados
posibles
8/16/2019 Procesos Inteligentes 1ra Fase
54/117
Agentes Basados en UtilidadLos objetivos únicamente no bastan para asegurar un comportamiento Ideal.
Ejemplo.Diferentes secuencias de acciones pueden llevar al destino que el pasajerodesea, pero algunas son mas rápidas, seguras o baratas que otras
Un agente basado en la utilidad utiliza un criterio para estimar el grado desatisfacción de un estado para el agente que le sirve para escoger entre distintasacciones válidas.
La utilidad es una función que asocia a un estado un número real, y debe
considerar situaciones problemáticas, ejemplo, compromiso adecuado a adoptar en caso de objetivos en conflicto.
La búsqueda en juegos es una subárea de la IA que utiliza funciones de utilidaden la resolución de problemas
8/16/2019 Procesos Inteligentes 1ra Fase
55/117
Agentes Reactivos
Los agentes reactivos representan una categoría especialde agentes que no posee modelos simbólicos internos desu entorno. En su lugar, ellos actúan/responden en unamanera estímulo/respuesta al presente estado delambiente en el cual se encuentran.
8/16/2019 Procesos Inteligentes 1ra Fase
56/117
Agentes Reactivos
Los agentes reactivos se basan en tres ideas claves:
1. No existe una especificación o plan a priori del comportamientodel agente reactivo. La dinámica de la interacción conduce a unaalta complejidad.
2. Descomposición en tareas. Un agente reactivo es visto como unacolección de módulos que operan en forma autónoma y sonresponsables de tareas específicas (sensar, controlar el motor,efectuar cálculos, etc.). La comunicación entre los módulos esmínima y de muy bajo nivel.
3. Tienden a operar sobre representaciones bien conocidas por lossensores, en contraste a las representaciones simbólicas de alto nivelque abundan en otros tipos de agentes.
Ej l
8/16/2019 Procesos Inteligentes 1ra Fase
57/117
Ejemplo:Un robot que se encuentra en un espacio bidimensional
dividido en cuadrículasEste robot esta limitado por una frontera, dentro de lacual hay también objetos inmóviles (no existen caminoscuyo ancho sea menor a dos cuadrículas)
El robot debe seguir la siguiente pauta decomportamiento:
-Ir a una celda fronteriza, o que limite con un objeto, y
seguir su perímetro indefinidamente.El robot debe ser capaz de percibir si una determinadacelda esta libre para ser ocupada o no, y para ello debellevar a cabo acciones
8/16/2019 Procesos Inteligentes 1ra Fase
58/117
• El robot puede percibir si las (8) celdas que lo rodeanestán libres o no. Estas ocho entradas sensoriales las
llamaremos:• s1, s2, s3, s4, s5, s6, s7,s8
• Estas variables tendrán el valor• 0 si están vacías
• 1 si están ocupadas
• El robot puede moverse a una celda libre adyacenteque este en su misma fila o columna. Por tanto, existen4 movimientos posibles:
Norte, mueve el robot hacia arribaEste, mueve el robot hacia la derecha.Sur , mueve el robot hacia abajo.Oeste, mueve el robot hacia la izquierda.
8/16/2019 Procesos Inteligentes 1ra Fase
59/117
8/16/2019 Procesos Inteligentes 1ra Fase
60/117
8/16/2019 Procesos Inteligentes 1ra Fase
61/117
Percepción y Acción• Para realizar el diseño, lo común seria dividir el cálculo
de una acción, a partir de las señales sensoriales, endos fases distintas:
• En la fase de procesamiento perceptual se genera unvector de características x ( x1 ,… xN ) y
• En la fase de cálculo de la acción se selecciona unaacción teniendo en cuenta dicho vector.
• Los valores de este vector pueden ser números reales obien categorías. Las características binarias constituyenun caso especial ya que pueden ser consideradas comocaracterísticas numéricas (0 , 1) o categorizadas (V o F).
8/16/2019 Procesos Inteligentes 1ra Fase
62/117
8/16/2019 Procesos Inteligentes 1ra Fase
63/117
ó
8/16/2019 Procesos Inteligentes 1ra Fase
64/117
Acción• Dadas las cuatro características definidas
anteriormente, el siguiente paso es definir una funciónque, de dichas características, nos proporcione laacción adecuada para llevar a cabo la tarea delseguimiento de los bordes.
• -Si ninguna de las características toma el valor uno(quiere decir que el robot percibe que todas las celdasalrededor están vacías), la acción pude ser moverse acualquier lugar. Tomaremos que se mueva al norte.
• -Si al menos una característica es 1, se aplicarán lassiguientes reglas:
Si x1=1 y x2=0, moverse al esteSi x2=1 y x3=0, moverse al sur Si x3=1 y x4=0, moverse al oesteSi x4=1 y x1=0, moverse al norte
8/16/2019 Procesos Inteligentes 1ra Fase
65/117
Representación e implementación de lasfunciones
• Álgebra booleana (utilización de conectivas: . + y –(conjunción, disyunción y negación)
• Sistemas de producción (reglas de producción:
c1 -> a1)
• Redes (circuitos lógicos y funciones booleanas paraimplementar una red de compuertas lógicas)
8/16/2019 Procesos Inteligentes 1ra Fase
66/117
Esquema general de un Agente Resolvente-Problemas
globales: Acciones, Estado, Objetivo, Problema
función Agente R-P(percepción) retorna Acciones
estado
8/16/2019 Procesos Inteligentes 1ra Fase
67/117
8/16/2019 Procesos Inteligentes 1ra Fase
68/117
Definición formal del Problema: (cont…)
-Costo del camino: Se asigna un costo numérico a cadacamino. El agente R-P elige una función costo que refleje unamedida de rendimiento. Por ejemplo, para el caso de lasciudades podría ser la distancia en kilómetros.
Supondremos que el costo del camino se calcula sumando loscostos individuales de las acciones a lo largo del camino:
c( a, x, y ) Costo Individual de la acción a la cualnos lleva del estado x al y.
-Solución Óptima: La solución cuyo costo del camino es elmínimo entre todas las posibles soluciones.
8/16/2019 Procesos Inteligentes 1ra Fase
69/117
Oradea
Neamt
Iasi
Vaslui
Eforie
Hirsova
SibiuFagaras
Mehadia
Dobreta
Urziceni
Rimnicu Vilcea
Craiova
Pitesti
Giurgiu
Zerind
Arad
Timisoara
Lugoj
Bucharest
87
92
142
98
86
85
90
211
101138
97
146
120
99
75
70
111
118
75
71
151
140
80
8/16/2019 Procesos Inteligentes 1ra Fase
70/117
8/16/2019 Procesos Inteligentes 1ra Fase
71/117
El juego de las ocho fichas
(tablero de 3x3 y 8 fichas (1 al 8). Una celda vacía.
Estados: La descripción de un estado especifica la ubicación de cada una de las ochofichas en una de las nueve celdas. También se incluye la posición del espacio vacío.
Estado inicial: Cualquiera .
Acciones: El espacio vacío puede moverse a la izquierda, a la derecha, arriba o abajo.
Test de Objetivo: El estado debe coincidir con la configuración de la derecha (mostradaen la figura)
Costo del camino: Cada paso cuesta 1, así que el costo de la ruta corresponde a lalongitud de la ruta.
8/16/2019 Procesos Inteligentes 1ra Fase
72/117
8/16/2019 Procesos Inteligentes 1ra Fase
73/117
Mundo de la Aspiradora(Hay solo dos localizaciones. La aspiradora sabe
donde está y si hay suciedad ó no en ese lugar)
Estados: Agente está en una de las doslocalizaciones, cada una de las cuales puede estarsucia ó no (en total 2 x 22 estados).Estado inicial: CualquieraAcciones: Desplazarse a la izquierda, derecha y
aspirar.Test de Objetivo: No hay suciedad en ninguna de lasceldas.Costo del camino: Cada acción cuesta 1.
8/16/2019 Procesos Inteligentes 1ra Fase
74/117
L
S
R
L L
L
L
L L
L
R
R
R
R
R
R
R
S
SS
8/16/2019 Procesos Inteligentes 1ra Fase
75/117
8/16/2019 Procesos Inteligentes 1ra Fase
76/117
Búsqueda de Soluciones:
Veremos algunas técnicas que utilizan el Árbol de búsqueda,obtenido a partir del estado inicial y la función sucesor
- Nodo de Búsqueda (raíz del árbol, estado inicial)
-Expandir: Proceso de aplicar la función sucesor -Generar: Al expandir se generan nuevos estados
-Estrategia de búsqueda: El proceso de elegir cuál será el
siguiente estado a Expandir
8/16/2019 Procesos Inteligentes 1ra Fase
77/117
Cada nodo del Árbol de Búsqueda:
Es una estructura de datos que contiene:-Estado (estado del espacio de estados que se corresponde conel nodo)
-Nodo Padre (el nodo en el árbol que ha generado a ese nodo)-Acción (la acción que se aplica al padre para generar el nodo)
-Costo del camino (el costo del camino desde el estado inicialal nodo, denotado por g(n) )
-Profundidad (longitud del camino desde el estado inicial alnodo)
8/16/2019 Procesos Inteligentes 1ra Fase
78/117
Estrategias de búsquedas:• No informada o a ciegas.
• Informadas o heurísticas.No Informadas ó a Ciegas: Significa que no se tieneinformación adicional acerca de los estados. La únicainformación es la que proporciona la formulación del
problema. Sólo generan sucesores y distinguen si hanllegado al objetivo ó no.
Informadas ó Heurísticas: Estrategias en las que se sabe,cuando un estado no es objetivo, si es mas “prometedor” que
otro.
8/16/2019 Procesos Inteligentes 1ra Fase
79/117
Estrategias de Búsquedas No Informadas (A ciegas)
• Búsqueda Primero en Anchura• Búsqueda de Costo Uniforme• Búsqueda Primero en Profundidad• Búsqueda Primero en Profundidad Limitada• Búsqueda Primero en Profundidad con profundidad iterativa• Búsqueda Bidireccional
8/16/2019 Procesos Inteligentes 1ra Fase
80/117
Estrategias de Búsquedas Informadas (Heurísticas):
• Búsqueda Primero el Mejor
• Búsqueda A*
8/16/2019 Procesos Inteligentes 1ra Fase
81/117
Criterios para evaluar las estrategias:
Completitud¿La estrategia garantiza encontrar una solución, si es que
esta existe?
Complejidad en tiempo¿Cuánto tiempo se necesitara para encontrar una solución?
Complejidad en espacio¿Cuánta memoria se necesita para efectuar la búsqueda?
Optimización¿Con esta estrategia se encontrará una Solución Óptima?
8/16/2019 Procesos Inteligentes 1ra Fase
82/117
Utiliza el concepto de Frontera (Todos los nodos delárbol que han sido generados, pero no expandidos.Al comienzo, antes de aplicar por primera vez lafunción Sucesor, la frontera contiene únicamente a laraíz del árbol .
La estrategia de búsqueda consistirá entonces endeterminar, de la frontera, cuál será el siguiente nodoa expandir
Algoritmo General de Búsqueda
utilizando árboles
Al it G l d Bú d
8/16/2019 Procesos Inteligentes 1ra Fase
83/117
Algoritmo General de Búsquedautilizando árboles (continuación)
Utiliza una Lista, para representar la frontera.-Operaciones sobre la Lista:
-Crear-Vacía?
-Primero-Eliminar Primero-Insertar Uno
-Insertar Todos
-Utiliza una función Expandir que retorna todos losnodos resultantes de expandir uno determinado
8/16/2019 Procesos Inteligentes 1ra Fase
84/117
Algoritmo General
funcion Busqueda_Arbol(problema)
retorna Solución
Crear(frontera)
frontera
8/16/2019 Procesos Inteligentes 1ra Fase
85/117
Función Expandir
funcion Expandir(nodo, problema) retorna Conjunto de Nodosconjunto
8/16/2019 Procesos Inteligentes 1ra Fase
86/117
Búsqueda Primero en Anchura
Es una estrategia de búsqueda sencilla. Se expande primero el nodo raíz, y luego todos los nodos sucesoresde éste; a continuación todos los sucesores de éstosúltimos y así sucesivamente. En general, se expanden
todos los nodos de una misma profundidad, antes deexpandir cualquier nodo del próximo nivel.
8/16/2019 Procesos Inteligentes 1ra Fase
87/117
8/16/2019 Procesos Inteligentes 1ra Fase
88/117
8/16/2019 Procesos Inteligentes 1ra Fase
89/117
Búsqueda de Costo Uniforme
En lugar de expandir el nodo más superficial, expandeaquel que tiene menor costo en su camino.Mediante esta estrategia se puede encontrar la solución
más barata siempre y cuando se satisfaga un requisitomuy sencillo “costo de la ruta nunca debe ir disminuyendo
conforme avanzamos por la ruta”.
Notar que si todos los costos son iguales a 1, la estrategiase comporta similar a la de Primero en Anchura.
8/16/2019 Procesos Inteligentes 1ra Fase
90/117
Búsqueda de Costo Uniforme (cont…)
Se puede implementar, mediante el Algoritmo General,
considerando la Lista como una Cola de Prioridad, cuyocriterio para obtener el Primero (Eliminar) de la Cola seríael de menor Costo.
8/16/2019 Procesos Inteligentes 1ra Fase
91/117
Búsqueda Primero en Profundidad
Esta búsqueda se centra en expandir un único camino desde la raíz.
Siempre se expande el nodo más profundo en la frontera actual.En el caso de llegar a un “callejón sin salida” se retrocede hasta el
nodo más cercano (siguiendo al nodo padre) donde se puede tomaruna rama alternativa para poder seguir avanzando.
Búsqueda Primero en Profundidad (cont )
8/16/2019 Procesos Inteligentes 1ra Fase
92/117
Búsqueda Primero en Profundidad (cont…)
Se puede implementar, mediante el Algoritmo General,considerando la Lista, como una Pila (cuyas operacionesfuncionan en forma LIFO (último en entrar, primero en salir). Deesta manera el siguiente nodo a expandir siempre será el últimoque se haya colocado en la pila de ese nivel, garantizando esto
que la expansión vaya aumentando en la profundidad de losnodos.
Es común aplicar esta estrategia mediante una algoritmorecursivo que recorra el árbol en Pre-Orden
Tiene modestos requisitos de memoria. Sólo necesita almacenar un camino, junto con los hermanos restantes no expandidos encada nodo.
8/16/2019 Procesos Inteligentes 1ra Fase
93/117
Búsqueda de Profundidad Limitada
8/16/2019 Procesos Inteligentes 1ra Fase
94/117
q
Similar a la estrategia de Primero en Profundidad,pero se trata de eliminar el problema de que sepuedan general árboles “ilimitados”. Para elloestablece un límite L a la profundidad del árbol.Todo nodo cuya profundidad sea L, no esexpandido (se considera sin sucesores).El problema que puede pasar es si escogemos un
valor de L menor que la profundidad del Objetivo,en cuyo caso no llegaríamos a la Solución.
Búsqueda Primero en Profundidad con
8/16/2019 Procesos Inteligentes 1ra Fase
95/117
Búsqueda Primero en Profundidad conProfundidad Iterativa.
Combina la estrategia de Primero en Profundidad conla de Profundidad Limitada, comenzando con Límiteigual a 0, aumentándolo de 1 en 1 hasta encontrar el
objetivo.
Combina las ventajas de las dos estrategias.
8/16/2019 Procesos Inteligentes 1ra Fase
96/117
Búsqueda Bidireccional
La idea es ejecutar dos búsquedas simultáneas: unahacia delante, desde el estado inicial y otra hacia atrás,desde el estado objetivo
La búsqueda termina cuando las dos búsquedas seencuentren (las búsqueda deben comprobar, antes dela expansión, si los nodos de sus fronteras coinciden)
8/16/2019 Procesos Inteligentes 1ra Fase
97/117
Ejercicios:
Aplicar los Algoritmos deBúsqueda Primero en AnchuraBúsqueda de Costo Uniforme
Búsqueda Primero en ProfundidadA los ejemplos de:-La aspiradora, comenzando en el estado en que la aspiradoraestá a la izquierda y ambas celdas están sucias-Ciudades, comenzado en Arab, para llegar a Bucarest
8/16/2019 Procesos Inteligentes 1ra Fase
98/117
RESOLUCIÓN DE PROBLEMASMEDIANTE BÚSQUEDAS
BÚSQUEDA INFORMADA(HEURÍSTICAS)
8/16/2019 Procesos Inteligentes 1ra Fase
99/117
Búsquedas Informadas (Heurísticas)Utilizan conocimiento específico del
problema, más allá de la definición del problema en sí mismo
Pueden encontrar la solución de manera
más eficiente
Búsquedas Informadas
8/16/2019 Procesos Inteligentes 1ra Fase
100/117
Búsquedas Informadas(Heurísticas)
Búsqueda Primero El Mejor
- Búsqueda Voraz (Avara)
- Búsqueda A*
Búsqueda Primero el Mejor
8/16/2019 Procesos Inteligentes 1ra Fase
101/117
Búsqueda Primero el Mejor
-Caso particular del algoritmo general de búsqueda en Árboles en la cual se selecciona elsiguiente nodo a expandir en base a unafunción de evaluación f(n)
-La evaluación mide la “distancia” al objetivo
-Se expande el nodo con la evaluación más
baja
8/16/2019 Procesos Inteligentes 1ra Fase
102/117
Búsqueda Primero el Mejor (cont…)-Se implementa de manera similar al método de “Búsqueda conCosto Uniforme”, mediante una cola de prioridad
-La función de evaluación nos brinda el nodo que “parece” ser elmejor y por tanto el que se debe expandir
-Familia de algoritmos basados en una función heurística h(n)
h(n) = costo estimado del camino más barato desde el nodo n hasta
el Objetivo
Búsqueda Voraz (Avara) Primero el Mejor
8/16/2019 Procesos Inteligentes 1ra Fase
103/117
q ( ) j
-Expande el nodo más cercano al Objetivo,
asumiendo que probablemente conduzca másrápidamente a la solución.
-La función de evaluación f(n) sería la funciónheurística h(n)
f(n) = h(n)
h(n) = costo estimado del camino más barato desde el nodo nhasta el Objetivo
Búsqueda Voraz (Avara) Primero el Mejor
8/16/2019 Procesos Inteligentes 1ra Fase
104/117
q ( ) j
-El término Voraz ó Avara es porque en cada
paso trata de ponerse tan cerca del objetivocomo pueda, seleccionando el nodo con menorfunción de evaluación f(n)
-No necesariamente brinda la solución óptima(ver ejemplo de las ciudades)
-Al igual que los otros métodos estudiados esnecesario verificar los “callejones sin salidas”(no exapandir estados repetidos)
Ejemplo. Objetivo: Estar en la ciudad Bucharest
8/16/2019 Procesos Inteligentes 1ra Fase
105/117
Oradea
Neamt
Iasi
Vaslui
Eforie
Hirsova
SibiuFagaras
Mehadia
Dobreta
Urziceni
Rimnicu Vilcea
Craiova
Pitesti
Giurgiu
Zerind
Arad
Timisoara
Lugoj
Bucharest
87
92
142
98
86
85
90
211
101138
97
146
120
99
75
70
111
118
75
71
151
140
80
Consideraremos como función de evaluación
8/16/2019 Procesos Inteligentes 1ra Fase
106/117
(función heurística):
Distancia en Línea Recta
hDLR (n) = Distancia en Línea Recta desde laciudad n hasta Bucharest
8/16/2019 Procesos Inteligentes 1ra Fase
107/117
8/16/2019 Procesos Inteligentes 1ra Fase
108/117
Solución de Búsqueda Voraz (Primero el Mejor):
8/16/2019 Procesos Inteligentes 1ra Fase
109/117
Arad – Sibiu – Fagaras – Bucharest
Costo total: (140+99+211) = 450
Sin embargo:
Arad – Sibiu – Rimmicu – Pitesti – Bucharest
Costo total: (140+80+97+101) = 418
Búsqueda A* Primero el Mejor: Minimizar el
8/16/2019 Procesos Inteligentes 1ra Fase
110/117
costo estimado total de la solución:
-Evalúa los nodos combinando g(n) y h(n)g(n): costo de haber alcanzado n
h(n): costo para llegar desde n hasta el objetivo
f(n) = g(n) + h(n) Costo más barato estimado de la solución através de n
f(n) Combina el costo del camino para llegar a n y el costo
estimado para llegar desde n al objetivo.
- En cada paso se expande el nodo con el valor más bajo def( ) ó d ( )+h( )
8/16/2019 Procesos Inteligentes 1ra Fase
111/117
f(n), ó sea, de g(n)+h(n)
- La búsqueda A* es óptima siempre y cuando la función
heurística h(n) se una heurística admisible.
-Significa que la función nunca sobreestime el costo dealcanzar el objetivo
-Son funciones optimistas-En el ejemplo hDLR es admisible ya que la distancia en línearecta entre dos puntos es el camino más corto.
8/16/2019 Procesos Inteligentes 1ra Fase
112/117
8/16/2019 Procesos Inteligentes 1ra Fase
113/117
Otros Algoritmos:
8/16/2019 Procesos Inteligentes 1ra Fase
114/117
Búsqueda A* con Profundidad Iterativa (A*PI):
Similar al algoritmo de profundidad iterativa, peroutilizando f(n) (g+h) como criterio de corte en cada iteración, enlugar de la profundidad. El valor del corte es el costo f(n) más
pequeño de cualquier nodo que haya excedido el corte de la
iteración anterior.
Búsqueda recursiva del primero mejor (BRPM):
Similar al algoritmo de primero el mejor, pero en un espacio
lineal, sin almacenar todo el árbol, sino almacenando únicamente la pista del mejor valor f alternativo disponible desde cualquierantepasado del nodo actual. Si el nodo excede ese límite se regresaal camino alternativo.
Funciones Heurísticas:Ejemplo del juego de las 8 fichas:
8/16/2019 Procesos Inteligentes 1ra Fase
115/117
h1: número de piezas mal colocadas. Es admisible dado quetoda pieza que esté fuera de lugar, tiene que ser necesariamentemovida.
h2: suma de las distancias de las piezas a su posición en el
objetivo (suma horizontal y vertical-Distancia Manhattan). Esadmisible porque cada movimiento de un pieza la acerca alobjetivo
Funciones Heurísticas:Ejemplo del juego de las 8 fichas:
8/16/2019 Procesos Inteligentes 1ra Fase
116/117
h1: número de piezas mal colocadas.= 8
h2: suma de las distancias de las piezas a su posición en elobjetivo
= 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
Ejercicio: Determinar una ruta desde A hasta I aplicando losalgoritmos:
8/16/2019 Procesos Inteligentes 1ra Fase
117/117
algoritmos:
a) Búsqueda Voraz Primero el Mejor
b) Búsqueda A*
AE
F
H
B
C
I
G
131
105
111
75 88
125
147
47
114
50
99
105
Distancias en linea recta a I
A - 295
B - 280
C - 218
D - 147
E - 193
F - 148
G - 99
H - 105
Recommended