Resolución Distribuida de Problemas
La resolución distribuida de problemas estudia cómo un problema puede ser resuelto por múltiples agentes, cada uno con parte de la información o responsabilidad, que se comunican y combinan sus resultados parciales en una solución global.
Definition
La resolución distribuida de problemas es la solución cooperativa de un problema por un grupo de agentes, cada uno con conocimiento local o subproblemas, que se coordinan a través de la comunicación para producir una solución global coherente.
Scope
Este tema abarca la resolución cooperativa de problemas entre agentes que no comparten un controlador central: el intercambio de tareas y resultados, la satisfacción y optimización de restricciones distribuidas (DCSP/DCOP) con algoritmos como el retroceso asíncrono, y la coordinación de soluciones parciales bajo restricciones de comunicación y privacidad. Aborda cómo la descomposición, el cálculo local y el paso de mensajes producen soluciones globalmente consistentes. La interacción puramente competitiva y el diseño de incentivos se cubren en la teoría de juegos y el diseño de mecanismos.
Core questions
- ¿Cómo se descompone y distribuye un problema entre agentes con vistas parciales?
- ¿Cómo comparten los agentes las tareas y los resultados intermedios para construir una solución global?
- ¿Cómo se resuelve un problema de restricciones cuando las variables y las restricciones se distribuyen entre los agentes?
- ¿Cómo se equilibran el costo de comunicación y la autonomía local con la calidad de la solución?
Key concepts
- descomposición de problemas
- intercambio de tareas y resultados
- satisfacción de restricciones distribuidas (DCSP)
- optimización de restricciones distribuidas (DCOP)
- retroceso asíncrono
- paso de mensajes
- autonomía local y privacidad
- consistencia global
Key theories
- Satisfacción y optimización de restricciones distribuidas
- La satisfacción de restricciones distribuidas (DCSP) y la optimización (DCOP) generalizan los problemas de restricciones a entornos donde las variables y las restricciones son mantenidas por diferentes agentes, resueltos por algoritmos en los que los agentes intercambian asincrónicamente asignaciones de valores e información de conflictos.
- Intercambio de tareas y resultados
- La resolución cooperativa distribuida de problemas procede descomponiendo y distribuyendo tareas e intercambiando resultados parciales que los agentes integran, permitiendo que un grupo resuelva problemas que ningún agente individual podría resolver solo.
- Búsqueda distribuida asíncrona
- Algoritmos como el retroceso asíncrono permiten a los agentes buscar una asignación global consistente sin control central, utilizando el paso de mensajes priorizado para resolver conflictos mientras se preserva la autonomía local.
Clinical relevance
La resolución distribuida de problemas se aplica a la vigilancia y seguimiento multisensor, la programación distribuida y la coordinación de reuniones, la gestión de redes eléctricas y de tráfico, y cualquier entorno donde los datos o la responsabilidad se distribuyen naturalmente entre agentes que deben encontrar conjuntamente una solución consistente mientras limitan la comunicación.
History
La resolución cooperativa distribuida de problemas fue un tema fundacional de la IA distribuida, ejemplificado por el trabajo de la década de 1980 sobre redes de sensores distribuidos y sistemas de pizarra. Yokoo y sus colegas formalizaron la satisfacción de restricciones distribuidas en la década de 1990, y la optimización de restricciones distribuidas se convirtió más tarde en un marco importante para la toma de decisiones cooperativa multiagente.
Key figures
- Edmund H. Durfee
- Victor R. Lesser
- Makoto Yokoo
- Daniel D. Corkill
Related topics
Seminal works
- yokoo1998
- durfee1989
Frequently asked questions
- ¿En qué se diferencia la resolución distribuida de problemas de la computación paralela?
- La computación paralela típicamente divide un problema entre procesadores bajo control central para ir más rápido. La resolución distribuida de problemas asume agentes autónomos con su propio conocimiento local y posiblemente restricciones de privacidad o comunicación, por lo que el desafío es la coordinación y alcanzar una solución coherente, no solo la velocidad.
- ¿Qué es un problema de optimización de restricciones distribuidas?
- Es un problema de restricciones en el que las variables y las restricciones son propiedad de diferentes agentes, y los agentes deben asignar valores cooperativamente para optimizar un objetivo global (como minimizar el costo total) comunicándose solo localmente. Modela muchas tareas de coordinación cooperativa entre agentes.