el 24 de septiembre del 2009 @ CONAIS, UJAT

Coordinación en Sistemas MultiagentesDra. Elisa Schaeffer

Trabajo colaborativo

! Entre personas (cooperación y trabajo en equipo)! Entre máquinas (automatización & control, sistemas inteligentes)! Interacción humano-computadora (usabilidad, sistemas inteligentes)

TareaContribución Contribución

Coordinación

! Para llevar a cabo la colaboración, se requiere la coordinación de las acciones tomadas por los participantes para cumplir con la meta compartida del trabajo.

1

2

3a

3b

4

5b

5a6

Meta

Sistemas

! Simples, complicados o complejos

! Deterministas o probabilistas

! Centralizados o distribuidos

Trabajo actual con el Dr. Moisés Hinojosa Rivera como parte de la tesis de maestría del Lic. Oliver Avalos Rosales.

Agentes

! Entidades (independientes)

! Físicos, de software o abstractos

! Cada agente tiene una identidad

! Observan su ambiente (via sensores o lectores)

! Interactuan con su ambiente (via actuadores)

Trabajo actual con el Dr. Virgilio González y González como parte de la tesis de maestría del Lic. Oliver Avalos Rosales.

Sistema simple, determinista & centralizado

González, Garza, Castillo & Schaeffer, 2009.

Sistema complejo, no determinista & distribuido

Carlos Alberto Castillo Salazar: Optimización de Costos de Reemplazo en Redes Sensoras Inalámbricas. Tesis de Licenciatura, IME, FIME, UANL, octubre 2009.

Comunicación

! Para colaborar, estos agentes se comunican entre ellos a través de un intercambio de mensajes.

! Entre agentes de software, estos pueden ser llamadas a los métodos públicos de otro agente, mecanismos como eventos o “buzones” para mensajes entrantes.

! Entre agentes físicos, métodos frecuentes de comunicación incluyen la radio (bluetooth entre otros) y otras redes de telecomunicación (alámbricas o inalámbricas).

Interacción indirecta

! Las acciones que toman los agentes modifican su ambiente o su estado interno.! Los otros agentes llegan a observar estos cambios que afecta su

comportamiento posterior. ! Modelo matemático:

! x es un agente y xt es su estado en tiempo t! !(x) es el conjunto de agentes que x está observando! f() es una función que goberna los cambios del estado interno de x! g() es una función que modela el efecto de las observaciones de x sobre los demás! xt = 1 significa que el agente x emite un señal al tiempo t

Interacción indirecta

! x es un agente y xt es su estado en tiempo t! !(x) es el conjunto de agentes que x está observando! f() es una función que goberna los cambios del estado interno de x! g() es una función que modela el efecto de las observaciones de x sobre los demás! xt = 1 significa que el agente x emite un señal al tiempo t

xt+1 =�

f(xt) + g(Γ(x), t), si ∃y ∈ Γ(x) tal que yt = 1f(xt), en otro caso.

¿Qué?

A ver...

Un grafo

Vértice (nodo)

Aristas (conexiones)

Métricas de calidad

! Cantidad de mensajes intercambiados durante la colaboración.

! Cantidad de distintos canales de comunicación utilizados.

! Grado de participación de cada agente en la realización de la tarea.

! Duración total de la realización de la tarea.

Coordinación óptima

! Es deseable que los agentes lleven a cabo su tarea en el tiempo mínimo, con una cantidad mínima de mensajes, utilizando el número mínimo de canales de comunicación y que el balance de carga de trabajo entre los agentes sea aproximadamente uniforme.

! ¿Qué todo afecta a esto?

! La topología (= las conexiones entre los agentes)! El protocolo de comunicación entre ellos! La confiabilidad de los canales de comunicación

Problemas & algoritmos

! Algoritmo = una serie de pasos que permiten construir una solución a un problema o identificar su existencia a partir de un conjunto de datos.

! Problemas de decisión / construcción / optimización

! Algoritmos deterministas / no deterministas

! Algoritmos exactos / aproximados / heurísticos

Algoritmos adaptativos

! Nuestra investigación está dirigida hacia el diseño e implementación de algoritmos adaptativos de coordinación en sistemas multiagentes.

! Bajo una topología dinámica, el sistema vuelve al estado deseado de manera autónoma.

Adaptativo = el comportamiento cambia para acomodar el algoritmo a las condiciones prevalentes observados

Dinámico = presenta cambios (tales como movimiento o falla en la operación de los agentes)

Autónoma = sin intervención activa de parte de algo externo al sistema (como por ejemplo un operador, usuario, etcétera)

Fundamentos teóricos

Utilizamos conceptos matemáticos de

‣ álgebra lineal y en particular

‣ la teoría espectral de grafos

en el modelado y análisis de

los sistemas,

los algoritmos y

la calidad de coordinación obtenida.

Álgebra lineal

! En la teoría de grafos, teoría de control y la teoría de sistemas dinámicos no lineales, el objeto de estudio se puede representar con una matriz:

1 3 9 7 82 6 3 0 13 3 0 0 24 9 1 9 00 0 2 7 3

2

63

0 1

Aristas que salen del vértice azul

Av = λvuA = λu

Vectores y valores propios(eigenvectores/valores)

! El espectro de la matriz (o algún variante suyo) revela propiedades y comportamientos del sistema modelado:

Nadie realmente hace esto a mano...

! ... sino con herramientas de software libres como Octave (http://www.octave.org)octave:1> A = [1, 3, 9, 7, 8; 2, 6, 3, 0, 1; 3, 3, 0, 0, 2; 4, 9, 1, 9, 0; 0, 0, 2, 7, 3]A =

1 3 9 7 8 2 6 3 0 1 3 3 0 0 2 4 9 1 9 0 0 0 2 7 3

octave:2> [V, D] = eig(A);octave:3> diag(D)ans =

16.37949 + 0.00000i -4.66455 + 0.00000i 3.47550 + 4.43371i 3.47550 - 4.43371i 0.33405 + 0.00000i

octave:4>

Excepto mis estudiantes porque les obligo para que entiendan y no olvidan cómo se definen...

Hipótesis

Por controlar las propiedades espectrales de la topología de conexiones entre los agentes, podemos variar el comportamiento del sistema al sincronizarse.

Metodología

✓ análisis teórico

✓ experimentos estadísticos

✓ simulación por computadora

✓ prototipos robóticos

Trabajo actual

! Simulaciones implementadas en los lenguajes ANSI C y Java.

! Análisis numérico en Octave & Matlab.

! En la construcción y programación de los prototipos, usamos los Lego Mindstorms NXT y la plataforma lejOS para programarlos en el lenguaje Java.

Favorito de los estudiantes de Verano Científico 2009

Equipo de trabajo! Dos tesistas de doctorado y una de maestría trabajan en esta temática conmigo:

" M.C. Tania Turrubiates López" M.C. Vanesa Avalos Gaytán" Lic. Nidia Lizzeth Gómez Duarte

! Están en la etapa inicial de estudio del estado del arte y de simulaciones preliminarias.

! En el Verano Cientifico 2009, el Ing. Francisco Celyecac Marreros diseñó & implementó un sistema de comunicación bluetooth que permite a los robots NXT “bailar”, siguiendo a un robot líder quien les comunica los pasos del baile.

Colaboradores

Contamos con un proyecto de investigación de Ciencias Báscias de SEP-CONACyT 2008 Estudio sobre la sincronización y coordinación de sistemas electromecánicos ($1,000,000). El responsable técnico de este proyecto es el Dr. Jesús de León Morales. El interés del Dr. León en esta temática no es nuevo. Él fue asesor de la tesis doctoral del Dr. Juan Ángel Rodríguez Liñán, Esquemas de sincronización para sistemas caóticos, que recibió el Premio de la Investigación UANL 2009 en el área de las Ciencias Exactas.

Aplicaciones potenciales

Telecomunicaciones

Manufactura

¿Ideas?

Gracias por su atención.

http://it.ciidit.uanl.mx/~elisa/elisa.schaeffer@uanl.edu.mx(81) 1340 4000 ext. 1637 & 1509

Contesto preguntas ahora y cuándo quieran.