2011 sma-slides-02

Arquitectura Agentes Reactivos Agentes con estado Agentes logicos Agentes y metas Agentes y utilidad Referencias

Agentes y Sistemas Multi-AgentesArquitecturas y Programas Agente

Dr. Alejandro Guerra-Hernandez

Departamento de Inteligencia ArtificialFacultad de Fısica e Inteligencia Artificial

Universidad [email protected]

http://www.uv.mx/aguerra

Maestrıa en Inteligencia Artificial 2011


Arquitectura abstracta (Wooldridge, 2002)

I El ambiente puede caracterizarse por medio de un conjuntofinito de estados discretos posibles, definido como:

E = {e, e ′, . . . }

I La aptitud de un agente, se define como el conjunto finito deacciones que este puede ejecutar:

Ac = {α, α′, . . . }

I Una corrida de un agente en un ambiente se define como unasecuencia finita de estados y acciones intercalados:

r = e0α0−→ e1

α1−→ e2α2−→ e3

α3−→ · · · αu−1−→ eu


Corridas

I Sea R el conjunto de todas las posibles secuencias finitassobre E y Ac .

I Definimos RAc como el subconjunto de las corridas queterminan en una accion

I y RE como el subconjunto de las corridas que terminan en unestado del ambiente.

I Para modelar el efecto de una accion en el ambiente, usamosuna funcion de transicion (Fagin et al., 1995):

τ : RAc → ℘(E )

I Si τ(r) = ∅ para todo r ∈ RAc , se dice que el sistema haterminado su corrida.


Ambiente y Agentes

I Un ambiente se define como una tripleta Env = 〈E , e0, τ〉donde E es el conjunto de los posibles estados del ambiente,e0 ∈ E es un estado inicial y τ es la funcion de transicion deestados.

I Los agentes se modelan como funciones que mapean corridasque terminan en un estado del ambiente, a acciones:

Ag : RE → Ac


Sistema Agente

I Un sistema agente es una tupla conformada por un agente yun ambiente.

I El conjunto de posibles corridas del agente Ag en el ambienteEnv se denota como R(Ag ,Env)

I Una secuencia de la forma: (e0, α0, e1, α1, e2, . . . ) representauna corrida del agente Ag en el ambiente Env si y solo siEnv = 〈E , e0, τ〉; α0 = Ag(e0); y para u > 0:

eu ∈ τ((e0, α0, . . . , αu−1))

yαu = Ag((e0, α0, . . . , eu))


Programa de agente

I Puesto que nuestra tarea es implementar programas deagente, podemos usar la formalizacion propuesta para definirun programa de agente que acepte percepciones de suambiente y regrese acciones sobre este.

Agente basado en mapeo ideal

1: function Agente-Mapeo-Ideal(p) . p es una percepcion.2: percepciones ← percepciones ∪ p3: acci on← busca(percepciones,mapeo) . mapeo predefinido.4: return acci on5: end function


Programa de ambiente

I Un programa basico de ambiente ilustra la relacion entre estey los agentes situados en el.

Ambiente

1: procedure Ambiente(e, τ, ags, fin) . e Estado incial del ambiente.2: repeat3: for all ag ∈ ags do . ags Conjunto de agentes.4: p(ag)← percibir(ag , e)5: end for6: for all ag ∈ ags do7: acci on(ag)← ag(p(ag))8: end for9: e ← τ(

⋃ag∈ags acci on(ag)) . τ Funcion de transicion.

10: until fin(e) . fin Predicado de fin de corrida.11: end procedure


Percepcion y accion

I Sea Per un conjunto no vacıo de percepciones, la funcionpercibir/2 se define como el mapeo del conjunto de estadosdel ambiente E al conjunto de percepciones posibles Per :

percibir : E → Per

I La funcion accion/1 se define entonces como el mapeo entreconjuntos de percepciones y el conjunto de acciones posiblesdel agente:

acci on : Per → Ac

I Un agente puede definirse ahora como la tupla:

Ag = 〈percibir , acci on〉


Propiedades de la percepcion

I Sean e ∈ E y e ′ ∈ E , tal que e 6= e ′ peropercibir(e) = percibir(e ′). Desde el punto de vista del agente,e y e ′ son indistinguibles.

I Dados dos estados del ambiente e, e ′ ∈ E ,percibir(e) = percibir(e ′) sera denotado como e ∼ e ′.

I El ambiente es accesible para el agente, si y solo si |E | = | ∼ |y entonces se dice que el agente es omnisciente.

I Si | ∼ | = 1 entonces se dice que el agente no tiene capacidadde percepcion, es decir, el ambiente es percibido por el agentecomo si tuviera un estado unico.


Agentes reactivos

I Los agentes reactivos, o reflex, seleccionan sus accionesbasados en su percepcion actual del ambiente, ignorando elresto de su historia perceptual.

Agente

percepción acción

Ambiente

sensado actuación


Agentes reactivos

I Basados en reglas percepcion - accion.

Programa de agente reactivo

1: function Agente-Reactivo(e)2: estado ← percibir(e)3: regla← selecci onAcci on(estado, reglas) . reglas predefinidas.4: acci on← acci onRegla(regla)5: return acci on6: end function


Limitaciones de los agentes reactivos

I Aunque hay otras maneras de implementar agentes reactivos(arquitectura subsumida, redes de comportamiento, etc.),todos comparten una limitacion formal: producen uncomportamiento racional, solo si la decision correcta puedeobtenerse a partir de la percepcion actual del agente.

I Esto es, su comportamiento es correcto si, y solo si, elambiente es observable o efectivamente observable.


Estado interno

I La forma mas eficiente de enfrentar un ambiente inaccesiblees llevando un registro de lo percibido, de forma que el agentetenga acceso mediante este registro, a lo que en ciertomomento ya no puede percibir.

I Sea I el conjunto de estados internos posibles de un agente.Redefinimos la funcion accion para mapear estados internos aacciones posibles:

acci on : I → Ac

I Una nueva funcion siguiente/2, mapea estados internos ypercepciones a estados internos. Se usa para actualizar elestado interno del agente:

siguiente : I × Per → I


Agentes con estado interno

I Un agente con estado interno interactua con su ambientecomo se muestra.

Agente

percepción acción

Ambiente

EstadoSiguiente

sensado

actuación


Programa de agente con estado

I El programa de un agente con estado es muy parecido al deun agente reactivo:

Programa de agente con estado

1: function Agente-Con-Estado(e) . e ∈ E2: p ← percibir(e)3: estado ← siguiente(estado, p)4: regla← selecci onAcci on(estado, reglas) . reglas predefinidas.5: acci on← Acci onRegla(regla)6: return acci on7: end function


Enfoque IA tradicional

I El comportamiento racional puede obtenerse a partir de unarepresentacion simbolica del ambiente y el comportamientodeseado.

I El agente manipulara sintacticamente esta representacion paraactuar.

I Llevada al extremo, esta aproximacion nos lleva a formular elestado de un agente como un conjunto formulas logicas y laseleccion de accion como demostracion de teoremas odeduccion logica.


Agentes e inferencia

I Sea L el conjunto de formulas bien formadas en la logica deprimer orden clasica.

I El conjunto de bases de conocimiento en L se define comoD = ℘(L), es decir, el conjunto de conjuntos de fbf en L. Loselementos de D se denotan ∆,∆1, . . .

I El estado interno del agente es siempre un miembro de D. Elproceso de decision del agente especifica mediante unconjunto de reglas de inferencia ρ.

I Escribimos ∆ `ρ ψ si la fbf ψ puede ser validada en ∆.

I Definimos la funcion siguiente/2 del agente como:

siguiente : D × Per → D


Seleccion de accion como inferencia

I La inferencia se usa para computar la seleccion de accion delos agentes logicos:

Seleccion de accion para agente logico

1: function Seleccion-Accion(∆ : D,Ac) . Ac Acciones.2: for all a ∈ Ac do3: if ∆ `ρ ejecuta(a) then . ρ predefinida.4: return a5: end if6: end for7: for all a ∈ Ac do8: if ∆ 6`ρ ¬ejecuta(a) then9: return a10: end if11: end for12: return null13: end function


Metas

I Las metas describen situaciones deseables para un agente, yse definen como cuerpos de conocimiento.

I Esta concepcion de las metas esta relacionada con el conceptode espacio de estados de un problema compuesto por unestado inicial del ambiente, e0 ∈ E ; por un conjunto deoperadores o acciones que el agente puede ejecutar paracambiar de estado; y un espacio de estados deseables.

I Implıcita en la arquitectura del agente, esta su “intencion” deejecutar las acciones que el “cree” le garantizan satisfacercualquiera de sus metas. Esto se conoce en filosofıa comosilogismo practico.


Las metas de un agente

I Especificacion basada en predicados:

Ψ : R → {0, 1}

I Una corrida r ∈ R satisface la especificacion ssi Ψ(r) = 1.

I Un ambiente de tareas se define entonces como el par〈Env ,Ψ〉.

I Dado un ambiente de tareas, la siguiente expresion:

RΨ(Ag ,Env) = {r |r ∈ R(Ag ,Env) ∧Ψ(r)}

denota el conjunto de todas las corridas del agente Ag enel ambiente Env que satisfacen la tarea especificadapor Ψ.


Metas y exito

I Podemos expresar que un agente Ag tiene exito en elambiente de tareas 〈Env ,Ψ〉 de dos maneras diferentes:

I ∀r ∈ R(Ag ,Env) tenemos que Ψ(r), lo que puede verse comouna especificacion pesimista de exito, puesto que el agentetiene exito unicamente si todas sus corridas satisfacen Ψ;

I ∃r ∈ R(Ag ,Env) tal que Ψ(r), lo cual es una version optimistade la definicion de exito, puesto que especifica que el agentetiene exito si al menos una de sus corridas safisface Ψ.


Utilidad

I Una utilidad es un valor numerico que denota la bondad de unestado del ambiente.

I Implıcitamente, un agente tiene la “intencion” de alcanzaraquellos estados que maximizan su utilidad a largo termino.

I La especificacion de una tarea en este enfoque correspondesimplemente a una funcion utilidad u : E → < la cual asociavalores reales a cada estado del ambiente.

I Por ejemplo, la utilidad para una corrida r de un agente filtrode spam, puede definirse como:

u(r) =SpamFiltrado(r)

SpamRecibido(r)


Agentes optimos

I Si la funcion de utilidad u tiene algun lımite superior, por ej.,∃k k ∈ < tal que ∀r ∈ R.u(r) ≤ k, entonces es posible hablarde agentes que maximizan la utilidad esperada.

I Definamos P(r |Ag ,Env), es evidente que:∑r∈R(Ag ,Env)

P(r |Ag ,Env) = 1

I Entonces el agente optimo Agopt entre el conjunto de agentesposibles AG en el ambiente Env esta definido como:

Agopt = arg maxAg∈AG

∑r∈R(Ag ,Env)

u(r)P(r |Ag ,Env)


Racionalidad acotada

I Los agentes enfrentan limitaciones temporales y tienencapacidades limitadas de deliberacion, por lo que propone elestudio de una racionalidad acotada.

I Stuart Russell et al., introducen el concepto de agente optimoacotado, donde AGm representa el conjunto de agentes quepueden ser implementados en una maquina m.

I Esta conceptualizacion de agente racional nos dice laspropiedades del agente deseable Agopt , pero no nos dice comoimplementar tal agente.


Referencias

Fagin, R., Halpern, J. Y., Moses, Y., & Vardi, M. Y. (1995). Reasoning aboutKnowledge. Cambridge, MA., USA: MIT Press.

Wooldridge, M. (2002). An Introduction to MultiAgent Systems. West Sussex,England: John Wiley & Sons, LTD.

2011 sma-slides-02

Documents