Dr.

Romeo Sánchez Nigenda

TEMAS SELECTOS DE
INTELIGENCIA
ARTIFICIAL
 Competencia

• Diseñar e implementar sistemas inteligentes y adaptativos de

la información utilizando técnicas de inteligencia artificial

• REGLAMENTO:
 Datos de Contacto

• Dr. Romeo Sánchez Nigenda

• E-mail: [Link]@[Link]
• WWW: [Link]
• Google Scholar:
[Link]
• ORCID: [Link]
 Texto:

• Artificial Intelligence: A Modern Approach. Russell&Norvig.

Third Edition. Pearson.

Material de Software:

Apoyo • JAVA: [Link]

• ECLIPSE IDE (Java EE Developers):
[Link]
• AIMA Repositorio: [Link]
• WEKA:
[Link]
 Introducción a Agentes Inteligentes

Algoritmos de Resolución de Problemas

• Estrategias de Búsqueda Clásica

• Búsqueda Heurística
• Algoritmos Locales de Optimización
• Algoritmos Evolutivos
• Problemas de Satisfacción con Restricciones
Temario
Lógica, razonamiento y Planeación

• Lógica e Inferencia
• Planeación Clásica

Introducción a Aprendizaje Computacional

• Aprendizaje Supervisado
• Aprendizaje no Supervisado
Calificación Actividades: 60% (incluye proyecto)
• Introducción a Agentes Inteligentes Exámenes: 40% (medio y final)
• Algoritmos de Resolución de Problemas
• Actividades: 50% (incluye proyecto)
Estrategias de Búsqueda Clásica
Exámenes: 50% (medio y final)
• Búsqueda Heurística
• Algoritmos Locales de Optimización
Participación: Puntos extra
• Algoritmos Evolutivos
• Problemas de Satisfacción con Restricciones
• Lógica, razonamiento y Planeación
• Lógica e Inferencia
• Planeación Clásica
• Introducción a Aprendizaje Computacional
• Aprendizaje Supervisado
• Aprendizaje no Supervisado
 Modelación en
Planificación
*Slides aumentados con información de Dr. Subbarao Kambhampati
Modelo Conceptual de Planificación
Descripción del:
Estado inicial y Dominio Descripción de A, E, γ
objetivos

Problema
Planificador

Estado de
1. Ambiente
Plan
Ejecución

Controlador/Simulador

Observaciones Acciones
Sistema de Transición de
Estados,  = (S,A,E,γ)
S = {Estados}
Sistema  A = {Acciones}
E= Eventos exógenos
γ = {Función de transición}
Eventos
Ejemplo de Modelo de Planificación:
El Mundo de los Bloques
• Número de bloques finito
• Mesa infinita
• Un bloque puede colocarse encima de otro, o sobre la mesa
• Existe una mano de robot que puede sostener únicamente un
bloque a la vez
• El objetivo es mover bloques de una configuración a otra

C A
B B
A C

Estado Inicial Objetivo

•  = (S,A,E,γ)
• γ : S * (A U E) => 2S
• S = {s0, s1,…, sn} Función de
• A = {pickUp, putDown, unStack, stack} Transición de Estados
• E={}
• γ : transiciones entre estados según acciones.
γ

unStack putDown

D s0 S1 s2
C C C
D
B B B

A A A D

Stack pickUp
Modelo Conceptual de Planificación
Descripción del:
Estado inicial y Dominio
objetivos
Descripción de A, E, γ
Problema
Planificador

Estado de Plan
Ejecución
Dada o en O, se
produce acción a en A
Función de observación Controlador/Simulador
h: S => O

Observaciones Acciones

S1
C Sistema γ
D
B

II. Controlador
A
Eventos
Modelo Conceptual de Planificación
Descripción del:
Estado inicial y Dominio Descripción de A, E, γ
objetivos

Problema
Planificador
III. Datos de
Entrada
Estado de Plan
Ejecución
Se ignora, a menos que
el proceso de
planificación sea en Controlador/Simulador
línea (tiempo real)

Observaciones Acciones

Sistema γ

Eventos
 Problema de Planificación
•  = (S,A,E,γ)
• Estado inicial: s0
• Objetivos: estado, conjunto de estados, trayectoria de
estados, función objetivo, …
• SG = S 2

unStack putDown

D s0 S1 s2
C C C
D
B B B

A A A D

Stack pickUp

S0 SG
Modelo Conceptual de Planificación
Descripción del:
Estado inicial y Dominio Descripción de γ
objetivos

Problema
Planificador
IV. Datos de
Salida
Estado de Plan
Ejecución
Conjunto de Instrucciones
al Controlador
Controlador/Simulador

Observaciones Acciones

Sistema γ

Eventos
 • Planificación Clásica: Secuencia de acciones
Planes! • <unStack(D), putDown(D), …>
• Policy: Mapa de estados en S a acciones en A
• {(S0, unStack(D)), (S1, putDown(D)), …}

unStack putDown

D s0 S1 s2
C C C
D
B B B

A A A D

Stack pickUp

S0 SG

Asignación de variables: SATs, CSPs, Ips, etc…

Planificación y Programación (Scheduling)
Dominio
Problema

Planificador

• Scheduling: Cuando y como ejecutar las

acciones del plan
• Restricciones de tiempo Scheduler
• Restricciones de recursos
• Funciones objetivo
• Típicamente es NP-Complete
Controlador/Simulador
• Planificación: Qué acciones utilizar para
alcanzar un conjunto de objetivos Acciones
• Puede ser mucho peor que NP-
Complete, el peor caso es “Undecidable”
Sistema γ

Eventos
 Restricciones de los modelos de planificación clásica
Descripción de γ
1. Sistema Finito Estado inicial
Estados, acciones, eventos Dominio
Objetivos
2. Totalmente observable
1. El controlador siempre conoce el estado Problema
Planificador
actual de γ, es determinístico.
2. Cada acción tiene solamente un outcome
Estado de Plan
3. Estático (No eventos exógenos)
Todos los cambios provienen del controlador
Ejecución

4. Conjunto de objetivos (estados) fijos

Controlador/Simulador
5. Planes parcialmente secuenciales
PSPACE-Complete en general
6. Acciones instantáneas (no duraciones) Observaciones Acciones
7. Planificación offline
Planificador no conoce el estado de ejecución
Sistema γ

Eventos
 Porqué no representar todos los estados del
problema explícitamente?

Es preferible usar la función de transición y la

Representaciones descripción de los operadores en el dominio para
generar el resto de estados conforme se necesiten.

Esquemas:

Representación Representación Set- Representación de

clásica theoretic variables de estados
Representación clásica
• Lenguaje lógico de primer orden (cálculo de predicados)
• No funciones, únicamente predicados y constantes

D
C
B
• Blocks-World: A
• Constantes:
• Bloques: A, B, C, D, étc.
• Predicados, nos ayudan a especificar las propiedades de un estado:
• on(?x,?y)
• on-table(?x)
• clear(?x)
• arm-empty
• holding(?x)
• Expresión Ground: No contiene variables, on(A,B)
• Expresión Lifted: Contiene al menos una variable, on(A,?y)
Representación clásica: Estados
• Estado: Conjunto S de expresiones ground.
• Representa los hechos que son verdaderos en uno de los estados Si de
el sistema de transición γ
• Solo puede existir un conjunto finito de expresiones ground,
en consecuencia, un conjunto finito de estados

• Ejemplo:
• S0 = {on-table(A), on(A,B), on(B,C), clear(C), holding(D)}

D
C
B
A
Representación clásica: Operadores
• Operador: triple o=(name(o), precond(o), effects(o))
• name(o): Nombre simbólico del operador en términos de name(?x1, ?x2,…,?xk)
• (?x1, ?x2,…,?xk) lista de variables (parámetros) de o
• precond+-(o): precondiciones, literales/predicados que deben ser verdaderas (o falsos) para
poder usar el operador
• effects+- (o): efectos del operador. Literales/predicados que el operador hará verdaderas o falsas

• Ejemplo de Operador:
putdown(?x):
precond: holding(?x)
effects: ¬holding(?x), clear(?x), arm-empty, on-table(?x)
D
• Acción: Instancia ground del operador D
putdown(D):
C
precond: holding(D) D
effects: ¬holding(D), clear(D), arm-empty, on-table(D) B
D
A D
Aplicabilidad de acciones: Forward Planning
• Una acción a es aplicable a un estado s, if s satisfies precond(a)
• if precond+(a) ⊆ s AND precond(a)- ⋂ s = ∅

• Ejemplo, putdown(D):
precond: holding(D)
effects: ¬holding(D), clear(D), arm-empty, on-table(D)
es aplicable dado el estado:
S0 = {on-table(A), on(A,B),
on(B,C), clear(C),
holding(D)}
D
C
B
A
Ejecución de acciones: Forward Planning
• Remueve los efectos negativos de a effects- (a), e
inserta los efectos positivos de a effects+(a)
• γ(s,a) = (s - effects-(a)) ⋃ effects+(a)

• Ejemplo, putdown(D):
precond: holding(D)
effects: ¬holding(D), clear(D), arm-empty, on-table(D)

D
C C
B B
A
putdown(D):
A D

S0 = {on-table(A), on(A,B), S1 = {on-table(A), on(A,B),

on(B,C), clear(C), on(B,C), clear(C), clear(D),
holding(D)} hand-empty, on-table(D)}
Representación Clásica: Problema de planificación

Dado un dominio de planificación (languaje, operadores)

• Un problema de planificación es el triple: P=(O, s0, g)

• O: Colección de operadores
• s0: Estado inicial
• g: Estado objetivo

Planes y soluciones:

• Un plan es cualquier secuencia de acciones σ<a1,a2,a3, …, an> de tal manera que cada ai es
una instancia ground de un operador en O
• Un plan es una solución para P=(O, s0, g) si es ejecutable a partir de s0 y satisface g. Es
decir, si hay estados s0, s1, s2, …, sn de tal manera que:
• γ(s0,a1) = s1
• γ(s1,a2) = s2
• γ(s2,a3) = s3
•…
• γ(sn-1,an) = sn
• sn Satisface g
 Modela la física de un dominio
(aplicación de planificación) Estados iniciales,
objetivos, funciones
Cuáles son los
Qué predicados Qué acciones son Cuál es la estructura de optimización,
efectos de tales
existen posibles de tales acciones funciones de
acciones
acumulación, entre
otras propiedades.

PDDL
Es un lenguaje centrado en acciones,
que usa precondiciones y post-
condiciones para describir la
aplicabilidad y los efectos de las
acciones respectivamente.
PDDL Separa

Dominio (Planning Domain)

• La descripción de las acciones parametrizadas que caracterizan el comportamiento de un

sistema

Problema (Planning Problem)

• La descripción de objetos específicos, condiciones iniciales y objetivos que caracterizan

una instancia del problema

Por lo tanto, un solo dominio puede vincularse a múltiples instancias de problema

GRAMÁTICA PDDL : DOMINIO
 Gramática PDDL: DOMINIO

• La definición del Dominio necesita un nombre:

• (define (domain rumania-travel-advisor)

• Uso estratificado de requerimientos para fácilmente decirle a los algoritmos lo que

se necesita para resolver un problema para esa especificación:
• (:requirements :strips :equality :typing :conditional-effects)

• Types: Tipos de objetos para representar categorizaciones entre ellos

• (:types city airport - location package)

• Constants: Símbolos que tienen el mismo significado en todos los problemas

• (:constants MTY - airport Saltillo - city)

• Predicados representan los hechos del mundo; básicamente, las relaciones entre los
objetos
• (:predicates (at ?x - package ?l - location))
Ejemplo: Dominio Blocks World
Nombre del dominio

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; 4 Op-blocks world
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Lista de requerimientos

(define (domain BLOCKS)

(:requirements :strips :typing) Predicados que conforman
(:types block) el problema
(:predicates (on ?x - block ?y - block)
(ontable ?x - block)
(clear ?x - block)
(handempty)
(holding ?x - block)
)
 Gramática PDDL: Operadores en el DOMINIO

• Las acciones se definen usando un nombre y las tres cláusulas:

• Parameters: lista de variables (argumentos) sobre los que opera la acción
• Preconditions: Descripción opcional que debe satisfacerse antes de que la acción pueda
aplicarse
• Effect: Lista de los cambios que la acción impone en el estado actual del mundo.

(:action pick-up
:parameters (?x - block)
:precondition (and (clear ?x) (ontable ?x) (handempty))
:effect
(and (not (ontable ?x))
(not (clear ?x))
(not (handempty))
(holding ?x)))
Ejemplo: Operadores Blocks World
unstack

?x
?x
?y ?y

? ?

? ?
s0 S1

(:action unstack
:parameters (?x - block ?y - block)
:precondition (and (on ?x ?y) (clear ?x) (handempty))
:effect
(and (holding ?x)
(clear ?y)
(not (clear ?x))
(not (handempty))
(not (on ?x ?y))))
Ejemplo: Operadores Blocks World
put-down

? ?
?x
? ?

? ? ?x
S1 s2

(:action put-down
:parameters (?x - block)
:precondition (holding ?x)
:effect
(and (not (holding ?x))
(clear ?x)
(handempty)
(ontable ?x)))
Ejemplo: Operadores Blocks World
pick-up

s2 S3
? ?
?x
? ?

? ?x ?

(:action pick-up
:parameters (?x - block)
:precondition (and (clear ?x) (ontable ?x) (handempty))
:effect
(and (not (ontable ?x))
(not (clear ?x))
(not (handempty))
(holding ?x)))
Ejemplo: Operadores Blocks World
stack
?x
?x
?y ?y

? ?

? ?
S1 s0

(:action stack
:parameters (?x - block ?y - block)
:precondition (and (holding ?x) (clear ?y))
:effect
(and (not (holding ?x))
(not (clear ?y))
(clear ?x)
(handempty)
(on ?x ?y)))
Ejemplo: Dominio Completo del Mundo de los Bloques
(:action put-down
(define (domain BLOCKS) :parameters (?x - block)
(:requirements :strips :typing) :precondition (holding ?x)
(:types block) :effect
(:predicates (on ?x - block ?y - block) (and (not (holding ?x))
(ontable ?x - block) (clear ?x)
(clear ?x - block) (handempty)
(handempty) (ontable ?x)))
(holding ?x - block) (:action stack
) :parameters (?x - block ?y - block)
:precondition (and (holding ?x) (clear ?y))
(:action pick-up :effect
:parameters (?x - block) (and (not (holding ?x))
:precondition (and (clear ?x) (ontable ?x) (not (clear ?y))
(handempty)) (clear ?x)
:effect (handempty)
(and (not (ontable ?x)) (on ?x ?y)))
(not (clear ?x)) (:action unstack
(not (handempty)) :parameters (?x - block ?y - block)
(holding ?x))) :precondition (and (on ?x ?y) (clear ?x)
(handempty))
:effect
(and (holding ?x)
(clear ?y)
(not (clear ?x))
(not (handempty))
(not (on ?x ?y)))))
GRAMÁTICA PDDL : PROBLEMA
 Problemas
• Una vez definido un dominio (aplicación), (define (problem BLOCKS-4-0)
(:domain BLOCKS)
tenemos que definir instancias (problemas) del
(:objects a b c d e f - block)
dominio, estas incluyen: (:INIT
• Una situación inicial (CLEAR b)
• Un goal que necesita satisfacerse (CLEAR e)
(CLEAR f)
(CLEAR d)
• Objects: Describe a los objetos que existen en la (ONTABLE a)
instancia del problema y situación inicial. Puede (ONTABLE c)
contener información también de los tipos del (ONTABLE f)
(ONTABLE d)
mismo. (HANDEMPTY)
(ON b a)
(ON e c)
• Situación inicial: )
• Lista todas las literales que son verdaderas al principio
del problema. Todos los predicados que no son
explícitamente mencionados en la situación inicial se
asumen que son falsos.
E B
C A D F
 Problemas

La definición de goals (objetivos) de una instancia incluye a todos los hechos (predicados) que
deben de satisfacerse.

Puede ser una descripción parcial.

(:goal (AND (ON c b)

(ON b a)
(ON d e)
(ON e f) C D
(ONTABLE a) B E
(ONTABLE f) A F
)
)
Problema completo del mundo de los bloques
(define (problem BLOCKS-4-0)
(:domain BLOCKS)
(:objects a b c d e f - block)
(:INIT
(CLEAR b)
(CLEAR e)
(CLEAR f)
(CLEAR d)
(ONTABLE a)
(ONTABLE c)
(ONTABLE f)
(ONTABLE d)
(HANDEMPTY)
(ON b a)
(ON e c)
)
(:goal (AND
(ON c b)
(ON b a)
(ON d e)
(ON e f)
(ONTABLE a)
(ONTABLE f)
)
)
)
 Plan

• Una solución a un problema especificado en formato PDDL es una

serie de acciones que implique:
• Que la secuencia sea posible de iniciarse desde el estado inicial del
problema; es decir, que la primera acción del plan satisface sus
condiciones de aplicabilidad dado el estado inicial

• Que el objetivo, si es verdadero, es el resultado de ejecutar la

secuencia de acciones. Es decir, que el estado resultante de aplicar
el plan es un súper set del estado objetivo.
Plan
Extensiones a PDDL
 Efectos Condicionales y Cuantificados Universalmente.

• (when P E) : Si p es verdadero antes de aplicar la acción entonces el efecto

E ocurre después de ejecutar la acción. P es una precondición secundaria.

• La acción podría todavía ser posible aún si P no es verdadero.

?z
B
?m ?l
PDDL 2.1: Expresiones Numéricas (functions/fluents)

• Las funciones representan valores asociados a los objetos del dominio,

retornan valores numéricos.

La función “amount” retorna la

cantidad de líquido (contenido) en
una jarra, mientras “capacity”
retorna la capacidad total de la
jarra.
 PDDL 2.1: Epresiones Numéricas,
PDDL 2.1: Expresiones Numéricas (functions/fluents)
Condiciones y efectos.
• Las operaciones aritméticas son construidas usando notación prefija.
• Las condicionales en expresiones numéricas son siempre comparaciones entre pares de
expresiones numéricas
• Los efectos pueden hacer uso de operaciones de asignación para actualizar el valor de las
expresiones numéricas primitivas. Por ejemplo, usando los operadores de: increase, assign, y
decrease.
• Las funciones están restringidas a ser del tipo: OBJECTn -> R
Precondición: Se puede derramar a la
Jarra 2 si la capacidad remanente en la
Acción: Derramar el líquido de la jarra 1 a la 2. jarra 2 es mayor o igual a la cantidad
actual que se derramará desde la Jarra 1

Efectos: La jarra 1 queda vacía (assign (amount ?jug1) 0), y

La cantidad de líquido en la jarra 2 se incrementa con la cantidad de líquido que se derramó de la jarra 1.
 Métricas de planeación

• Especifican las bases sobre las cuales un plan será evaluado para un
problema en particular.
• Mismos estados inicial y objetivo pueden dar planes completamente
diferentes en presencia de diferentes métricas de evaluación.
• El valor total-time puede utilizarse para referirse al tiempo total (makespan)
de un plan.
• Cualquier otra métrica de evaluación debe construirse a partir de las
expresiones numéricas primitivas que se hayan declarado dentro del
dominio, y que sean manipuladas por las acciones del mismo.
Métricas de Planeación
• La introducción de métricas, aún en la forma limitada en PDDL
2.1, hace al problema de planeación undecidable (Helmert,
2002).
 Acciones Durativas

• Existen dos tipos: discretas y continuas

• La modelación de relaciones temporales en una acción discreta se realiza a
través de efectos y condicionales temporalmente etiquetados.

• La etiqueta (anotación) de una condición establece explícitamente cuando la

proposición asociada debe ser verdadera:
– Al inicio (start) del intervalo (el punto de origen donde la acción se aplica)
– Al final (end) del intervalo (el punto donde los efectos finales de la acción son
evaluados)
– Durante todo el intervalo, desde el inicio hasta el final (se le conoce como invariant
porque permanece inalterable durante toda la duración de la acción).
 Acciones Durativas
• En el caso de efectos, la anotación en un efecto hace explícito si el efecto es:
• Inmediato (sucede al inicio del intervalo de la acción)
• Retrasado (sucede al final del intervalo de la acción)

Ejemplo de acción durativa del dominio de Rover

• No existen otros puntos en
IPC: International Planning Competition.
el tiempo que sean
(:durative-action sample_rock
accesibles, por lo que toda :parameters (?x - rover ?s - store ?p - waypoint)
la actividad discreta de la :duration (= ?duration 8)
:condition (and
acción se realiza en los (over all (at ?x ?p))
puntos de inicio (start) y (at start (at ?x ?p))
final (end) del intervalo de (at start (at_rock_sample ?p))
(at start (equipped_for_rock_analysis ?x))
duración. (at start (store_of ?s ?x))
(at start (empty ?s)))
:effect (and
(at start (not (empty ?s)))
(at end (full ?s))
(at end (have_rock_analysis ?x ?p))
(at end (not (at_rock_sample ?p))))
)
 • Se distinguen las condiciones y efectos en los puntos de start y
end del intervalo de duración de la acción, así como las
condiciones que deben de sostenerse sobre todo el intervalo.

• Para que un plan sea considerado válido, no condición lógica

puede ser afirmado o negada al mismo instante de tiempo.

• La regla de “no moving targets” establece que dos acciones no

pueden usar simultáneamente algún valor, si una de las dos lo
Validación de actualiza, ya que se volvería un “moving target” para la otra
acción que está tratando de usarlo.

Planes • Ningún valor numérico puede ser accedido o actualizado

concurrentes simultáneamente en los puntos de inicio o final de la acción. Con
acciones discretas, todo cambio numérico es modelado usando
funciones escalonadas (step functions).

• Existe la noción de actualización de recursos de manera

conservadora. Es decir, el consumo de un recurso se modela al
inicio de la acción temporal, aunque actualmente suceda
continuamente durante toda la duración de la acción. La
producción de un recurso se modela al final de la acción
temporal, aunque de nuevo pudiera ser que se produjera
continuamente durante todo el intervalo de ejecución.
 P11

V1

P1 P6 V2
P2
P3
P7 V3

P5

P9
P12
P4

P10
V4 P8