Planificacion Automatica
-
Upload
shelley-khloe -
Category
Documents
-
view
21 -
download
0
description
Transcript of Planificacion Automatica
-
UNIVERSIDAD NACIONAL
DEL CALLAO
ESCUELA PROFESIONAL DE INGENIERIA DE
SISTEMAS
CURSO: INTELIGENCIA ARTIFICIAL
PROFESOR: ALCANTARA RAMIREZ, MANUEL
TEMA: PLANIFICACIN AUTOMTICA Y EXTRACCIN DE LA INFORMACIN
ALUMNA: PARIHUAMAN ALMINAGORTA, SHELLEY RAQUEL
CODIGO: 1125220221
2015
-
Planificacin Automtica
Donde veremos cmo un agente puede extraer ventaja del conocimiento de la
estructura de un problema para construir complejos planes de accin.
I. Agentes Planificadores
Desde principios de los 70, la comunidad de IA especializada en planificacin se ha preocupado
del problema de diseo de agentes artificiales capaces de actuar en un entorno.
La planificacin se puede ver como una forma de programacin automtica: el diseo de un
curso de accin que satisfar un cierto objetivo.
Dentro de la comunidad de la IA simblica, se ha asumido desde hace tiempo que algn tipo de
sistema planificador debe formar parte de los componentes centrales de cualquier agente
artificial.
La idea bsica es dotar al agente planificador:
Representacin del objetivo a alcanzar
Representacin de las acciones que puede realizar
Representacin del entorno
Capacidad de generar un plan para alcanzar el objetivo
II. Planificacin
Qu es un plan?
Es una secuencia (lista) de acciones, que llevan de un estado inicial a un estado final.
Llamaremos planificacin al proceso de bsqueda y articulacin de una secuencia de
acciones que permitan alcanzar un objetivo.
-
III. Ejemplos paradigmticos de planificacin
Hay ejemplos que se repiten de forma reiterada en la literatura de Planificacin
Torres de Hanoi
8-puzzle, 15-puzzle,.
Mundo de los bloques (Blocks World)
IV. Aplicaciones:
Aplicaciones de la Planificacin: en la vida diaria
Ejemplo de Han Yu (University of Central Florida)
-
Aplicaciones de la Planificacin: gestin de workflows
Ejemplo de Han Yu (University of Central Florida)
Aplicaciones de la Planificacin: exploracin espacial
Mars Exploration Rovers; La planificacin de las tareas a realizar durante un da
marciano se realiza automticamente por un programa a partir de los objetivos de
exploracin que fija el personal de misin en la Tierra.
V. Arquitectura de un Sistema de Planificacin Automtica
-
VI. Tipos de Planes
Planes parcialmente ordenados (Partial-order plan)
- Compuesto por un conjunto de acciones ordenadas parcialmente.
- Existen restricciones de secuencia en estas acciones.
- Un algoritmo de generacin de planes se puede usar para transformar un plan
parcialmente ordenado en un plan totalmente ordenado
Planes totalmente ordenados (Total-order plan)
- Compuesto por un conjunto de acciones totalmente ordenado.
VII. Planificacin Clsica Considera entornos que son: o Completamente observables: el planificador percibe perfectamente el estado del
entorno y el efecto de sus acciones en el entorno.
o Deterministas: se pueden predecir y predefinir los efectos de todas las acciones
o Finitos: existe un conjunto finito de acciones y de estados
o Estticos: el entorno solo cambia cuando el agente planificador acta sobre l.
o Discretos: el entorno se puede describir de forma discreta
o Tiempo discreto (se suele medir en ciclos de ejecucin)
o Acciones discretas (las acciones suelen verse como unidades y necesitar un ciclo de
ejecucin)
o Objetos discretos: las descripciones de los objetos son discretas
o Efectos discretos: los efectos de las acciones suelen ser directamente observables una
vez se ha ejecutado la accin.
-
Planificacin Clsica: teora formal (I)
Ac = {1, ... , n}: un conjunto fijo de acciones.
< P, D, A> un descriptor para una accin
P es un conjunto de frmulas en lgica de primer orden que caracterizan la
precondicin de la accin
D es un conjunto de frmulas en lgica de primer orden que caracterizan
aquellos hechos que se vuelven falsos por la ejecucin de (delete list)
A es un conjunto de frmulas en lgica de primer orden que caracterizan
aquellos hechos que se vuelven ciertos por la ejecucin de (add list)
Un problema de planificacin es una tripleta
Planificacin Clsica: teora formal (II)
=(1, ... , n): un plan con respecto al problema de planificacin determina
una secuencia de n+1 modelos:
donde 0 = y
Un plan es aceptable ssi ,para todo
Un plan es correcto ssi
es aceptable, y
VIII. Mtodos de Planificacin:
1. Planificacin Lineal: STRIPS
Objetivo: construccin de un sistema de control para el robot Shakey
Representacin de operadores
-Problema del marco: qu ocurre con el contexto del mundo cuando se ejecuta una accin?
-Solucin (hiptesis strips): solo cambian las cosas que aparecen en las post-condiciones de cada
operador
-Bsqueda:
Nodos: estado actual y pila de metas-operadores
Nodo raz: estado inicial y conjuncin de metas
-
Heurstica: seleccionar siempre alguno de los sucesores de cada nodo
-Idea: Meter en la pila las metas por conseguir y los operadores que consiguen dichas metas.
Sacar de la pila las metas que sean ciertas en el estado actual y los operadores que se ejecuten.
Algoritmo de strips
Repetir hasta que pila=0 OR no se puedan expandir ms nodos
- Si la cima de la pila del nodo es una conjuncin de metas
-Si la conjuncin es cierta en el estado Entonces se elimina de la pila
-Si no, generar como sucesores todas las posibles combinaciones de las metas
Seleccionar una de ellas
- Si la cima de la pila del nodo es una meta
- Si la meta es cierta en el estado Entonces se elimina de la pila
- Si no, Si hay bucle de meta Entonces retroceder
-Si no, generar un sucesor por cada instanciacin de operador que aade dicha meta
Si hay sucesores Entonces elegir uno
Si no, retroceder
- Si la cima de la pila del nodo es un operador instanciado
Si el operador instanciado se puede ejecutar
Entonces ejecutar operador, quitarlo de la pila y aadirlo al plan
Si no, se introducen sus precondiciones en la pila
Representacin de operadores
QUITAR(x; y)
Precondiciones: encima(x; y),libre(x),brazo-libre
Aadidos: sujeto(x),libre(y)
Borrados: encima(x; y),brazo-libre,libre(x)
LEVANTAR(x)
Precondiciones: en-mesa(x),libre(x),brazo-libre
Aadidos: sujeto(x)
Borrados: en-mesa(x),brazo-libre,libre(x)
PONER(x; y)
Precondiciones: sujeto(x),libre(y)
Aadidos: encima(x; y),libre(x),brazo-libre
Borrados: sujeto(x),libre(y)
DEJAR(x)
Precondiciones: sujeto(x)
Aadidos: en-mesa(x),libre(x),brazo-libre
Borrados: sujeto(x)
-
Ejemplo de strips
Problema: linealidad
STRIPS asume independencia entre las metas, por lo que las trata linealmente: hasta que
no encuentra un plan para obtener una meta, no pasa a las siguientes metas. No funciona
cuando hay recursos limitados, por lo que es:
Incompleta: existe solucin, pero no la encuentra
Problema del cohete chino
No optima: no encuentra la solucin optima
anomala de sussman
2. Planificacin No Lineal
Consideracin de varias metas al mismo tiempo. Pensar con un conjunto de metas: no es
necesario generar completamente un plan de una meta para estudiar al mismo tiempo el
resto
-
Expandir un grafo en el que las metas (y los operadores) son nodos y se pueden
seleccionar las metas en cualquier orden
Segn espacio de problemas:
-Estados (strips, prodigy): nodos del _rbol representan estados
-Planes (noah, tweak, ucpop, snlp, o-plan): nodos del 9rbol representan planes
Segn plan generado:
-Orden total: secuencia _nica de operadores
-Orden parcial: mltiples secuencias posibles
Segn toma de decisiones:
-Compromiso casual: toman decisiones continuamente
-Mnimo compromiso: solo toman decisiones cuando se ven forzados
No hay una tcnica mejor que otra
IX. Expresividad y extensiones
-
Extraccin de Informacin
Cuyo objetivo es extraer automticamente informacin estructurada o
semiestructurada desde documentos legibles por la mquina.
I. Visin Panormica
En la actualidad, la informacin constituye un elemento de gran importancia dentro de nuestras
vidas. La tecnologa moderna nos ha puesto delante volmenes increbles de informacin, mucha
de la cual, por estar disponible en textos escritos en lenguaje natural sin restricciones, necesita de
un procesamiento previo para poder ser usada y aplicada a la resolucin de los problemas que
tenemos que enfrentar.
Debido al gran almacenamiento de informacin existente en textos, el tiempo que requiere su
procesamiento manual para la extraccin de aquella que resultante relevante es muy pequeo.
Por eso se va haciendo imprescindible el uso de sistemas automticos que ayuden a procesar o
extraer el contenido conceptual encerrado en esos volmenes. Un aspecto fundamental de este
proceso de informacin tiene que ver con la cantidad de conocimiento que deber ser aplicado
para la extraccin de informacin relevante a la solucin del problema, el cual, por lo general, solo
tienen los expertos en el problema y la necesidad, por tanto, de hacer asequible y manipulable
este conocimiento para su resolucin.
Una de las estrategias ms comnmente adoptadas es la Recuperacin de Informacin, pero la
Extraccin de Informacin - tcnica de Inteligencia Artificial- es una estrategia diferente, ya que a
partir de la primera se obtienen documentos con informacin significativa, mientras que un
sistema de Extraccin obtiene hechos de los documentos, son por tanto, complementarios.
Los sistemas de Extraccin de Informacin (SEI) operan en un contexto formado por un conjunto
de textos en lenguaje natural para extraer determinados conceptos que son de nuestro inters
para una aplicacin especfica. Estos textos, en unin de la informacin definida para ser extrada,
conforman el dominio de trabajo de un SEI.
-
II. En qu consiste?
La extraccin de informacin consiste en obtener informacin de forma selectiva de un
documento. Previamente se ha de haber determinado el tipo de informacin que interesa extraer
para cada uno de los dominios que se van a tratar. Para ello se definen unas plantillas o esquemas
correspondientes al dominio del problema que se desea tratar. El proceso de extraccin consiste
en procesar los documentos, detectar para cada uno de ellos el tipo (o los tipos) de plantillas a los
que se ajusta y rellenar los campos de cada plantilla seleccionada con elementos extrados del
documento.
III. Patrones de extraccin de la informacin
Debido al enorme volumen de datos, que adems se incrementan cada minuto, es muy
complicado poder recuperar informacin relevante. Y se consideran relevantes las pginas que son
capaces de satisfacer una necesidad de informacin del usuario. Para que los buscadores sean
capaces de recuperar pginas con informacin relevante han de extraer la informacin clave. Por
lo tanto la recuperacin y la extraccin de la informacin estn relacionadas. No pudindose
recuperar pginas relevantes de las que no se haya extrado antes los datos clave.
Los criterios de extraccin de los datos son:
- Patrones Lxicos.
Los patrones de tipo lxico son las palabras que utilizamos para la bsqueda de informacin. Estas
palabras se analizan por si solas y de forma independiente al contexto.
Incluso a nivel bsico como es la palabra hay problemas para su correcto procesado. Los ms
comunes, y en algunos casos corregidos automticamente por los buscadores son:
Puntuacin: URSS vs U.R.S.S
Capitalizacin: Madrid vs MADRID
Espaciamiento: J.S. ELCANO vs J. S. ELCANO
Abreviaciones y acrnimos: "extraccin de informacin" vs EI
-
Omisin de caracteres: Madness vs Madnes
Adicin de caracteres: Madness vs Maddness
Substituciones: Day vs Dai
Cambio de orden: daily vs dialy
Las formas de corregir estos errores son para la capitalizacin y la puntuacin con el uso de
normalizacin. Y para las abreviaciones y acrnimos se suelen utilizar tablas de traduccin.
Con los problemas de cambio de caracteres se utilizan algoritmos de clculo de coste variable
llamado "Distancia de cambiar de una unidad de informacin A a otra B" que queda de definida de
la siguiente forma:
D(A,B) = min [ S + I + B]
Donde S es el nmero de caracteres sustituidos, I es el nmero de inserciones realizadas, y B se
refiere al nmero de letras que han sido eliminadas.
De esta forma se pueden utilizar patrones lxicos para la extraccin y recuperacin de palabras
que aunque no se deletrean igual, lxicamente se refieren a la misma informacin.
- Patrones Sintcticos.
El patrn sintctico ms usado en la recuperacin de la informacin es el llamado part-of-speech
(POS) de una palabra, es decir, las partes del habla que son: sustantivo, verbo, artculo, adjetivo,
etc.
En la recuperacin de informacin se realiza un marcaje de "POS" cuando se asignan estas
categoras gramaticales a cada palabra dada, es decir, cuando se indica la funcin de cada palabra
en el contexto especfico de la oracin. Este marcaje se hace considerando caractersticas
morfolgicas y sintcticas del lenguaje, esto es importante ya que los nombres generalmente
designan personas, lugares, cosas, y otros conceptos fsicos y abstractos, los verbos suelen
utilizarse para designar acciones y procesos y los adjetivos describen propiedades y estados de los
nombres.
En este proceso de reconocimiento de patrones, lo que se obtiene al final es un etiquetado de la
siguiente forma:
El resto segn la categorizacin de DeRose (1988) [1]: AT=artculo, VB=verbo, RB=adverbio,
VBD="past-tense-verb", PPO=pronombre personal y PP$=pronombre posesivo
-
Este etiquetado seguira con cada unidad sintctica, especialmente con el verbo, en el que se
tendra que tener en cuenta las terminaciones verbales para saber a que modo, tiempo, persona y
voz, corresponde una unidad de informacin.
- Patrones Semnticos.
Los patrones de tipo semntico se basan en los metadatos semnticos que se aaden a la web
para describir el contenido, el significado y la relacin de los datos.
En la actualidad, la World Wide Web est basada principalmente en documentos escritos en
HTML, un lenguaje de marcas que sirve para crear hipertexto en Internet. HTML es vlido para
adecuar el aspecto visual del documento e incluir objetos multimedia en el texto (imgenes,
esquemas de dilogo, etc.). Pero da pocas posibilidades para categorizar los elementos que
configuran el texto ms all de las tpicas funciones estructurales, como sucede con otros
lenguajes de maquetacin (tipo LaTeX).
HTML permite mediante una herramienta de visualizacin (como un navegador o un agente de
usuario) mostrar por ejemplo un catlogo de objetos en venta. El cdigo HTML de este catlogo
puede explicitar aspectos como "el ttulo del documento" es Ferretera Acme; pero no hay forma
de precisar dentro del cdigo HTML si el producto M270660 es una "batera Acme", con un "precio
de venta al pblico" de 200 , o si es otro tipo de producto de consumo (es decir, es una batera
elctrica y no un instrumento musical, o un puchero). Lo nico que HTML permite es alinear el
precio en la misma fila que el nombre del producto. No hay forma de indicar "esto es un catlogo",
"batera Acme" es una batera elctrica, o "200 " es el precio. Tampoco hay forma de relacionar
ambos datos para describir un elemento especfico en oposicin a otros similares en el mismo
catlogo.
La Web Semntica se ocupar de resolver estas deficiencias. Para ello dispone de tecnologas de
descripcin de los contenidos, como RDF y OWL, adems de XML, el lenguaje de marcas diseado
para describir los datos. Estas tecnologas se combinan para aportar descripciones explcitas de los
recursos de la Web (ya sean estos catlogos, formularios, mapas u otro tipo de objeto
documental). De esta forma el contenido queda desvelado, como los datos de una base de datos
accesibles por Web, o las etiquetas inmersas en el documento (normalmente en XHTML, o
directamente en XML, y las instrucciones de visualizacin definidas en una hoja de estilos aparte).
Estas etiquetas hacen posible a los gestores de contenidos interpretar los documentos y realizar
procesos inteligentes de captura y tratamiento de informacin.
-
- Patrones de discurso.
El uso de patrones de discurso para la extraccin y recuperacin de informacin, est referido a las
caractersticas de unidades de informacin dentro de un marco de discurso, o dentro de un marco
de escritura o de estilo.
Un ejemplo muy simple sobre estos patrones de extraccin es el llamado "discourse distance". En
el proceso de extraccin la distancia entre dos entidades de informacin es a menudo importante
pues se asume que la distancia es inversamente proporcional con relacin de significados.
Los patrones de discurso ms importantes, que como se puede ver estn en relacin con los
semnticos son:
Atributos retricos
Atributos temporales
Atributos de relaciones espaciales
Los esquemas de usos de patrones de discurso usados ms recientemente apuntan a describir el
contenido temporal de las pginas Web para poder realizar inferencias sobre las mismas.
IV. Arquitectura General
sta arquitectura genrica es descrita como "una cascada de mdulos que en cada paso agregan
estructura al documento, y algunas veces, filtran informacin relevante por medio de aplicar
reglas o patrones".
V. El Problema
El problema consiste en la generacin de un sistema de extraccin de informacin sobre el
dominio de las inscripciones de inmuebles o terrenos a expropiar por un municipio para realizar
distintos tipos de obras.
Se pretende obtener informacin relevante en base a estructuras de datos previamente definidas
plantillas de elementos- de los escribanos actuantes, los padrones catastrales involucrados en la
operacin, la ubicacin de stos, su registro (inscripcin y fecha), el destino de la expropiacin,
-
etc. Los elementos a ser extrados se presentan en una plantilla en la Fase 3 de la Descripcin del
sistema.
Descripcin del sistema
Fase 1: Tokenizacin: con la ayuda del tagger Freeling, etiquetar cada palabra de documento, as
como signos de puntuacin.
Fase 2: Reconocimiento:
i) Entidades con nombre: con la ayuda de diccionarios, habr que identificar nombres de
las personas (escribanos en este caso) actuantes en el acto de la inscripcin.
ii) Nmeros: padrn, inscripcin
iii) Fechas
iv) Direcciones
Fase 3: Confeccin y llenado de una estructura de plantilla(XML) con la informacin extrada en el
reconocimiento:
Recursos necesarios para el desarrollo
Se piensa que el desarrollo del reconocedor puede estar escrito en Perl o Jlex (para encontrar los
patrones que conforman las plantillas).
Se utilizarn los siguientes recursos:
- Tagger Freeling
- Diccionario de nombres
- Corpus de escrituras de inscripciones sin formato
-
Referencias Bibliogrficas y Webgrficas:
Grupo de Planificacin y Aprendizaje (PLG) - Universidad Carlos III de Madrid
RUSSELL, S. J.: NORVlG, P. INTELIGENCIA ARTIFICIAI. UN ENFOQUE M0DERNO Segunda
edicin PEARSON EDUCACION. S.A., Madrid. 2004
file:///G:/Protected/UNAC/IA/4-PL1-IntroPlanificaci%C3%B3n.pdf
Julio. Gonzalo. Arroyo. y M. Felisa. Verdejo. Mallo. - Tecnologas del Lenguaje
(Recuperacion Y extraccin del Lenguaje)
Referencia [1] DeRose, Stephen J. 1988. Grammatical category disambiguation by
statistical optimization. Computational Linguistics 14.1: 31-39.
http://www.itl.nist.gov/iaui/894.02/related_projects/muc/index.html
http://recupera1patrones.50webs.com/
http://www.galeon.com/recuperacionpatrones/arquitectura.html