Instrument de proiectare asistată a problemelor de satisfacere a

constrângerilor

şi rezolvarea distribuită a acestora pe sisteme multiagent.

Algoritmi distribuiţi de rezolvare

Sistem multiagent

• este un sistem în care mai mulţi agenţi semi-autonomi interacţionează pentru a rezolva probleme

• protocoale de comunicaţie, arhitecturi de agenţi, limbaje de comunicaţie între agenţi, rezolvare de probleme distribuite.

Problema de satisfacere a constrângerilor

• Are 3 componente: – variabile– valori– constrângeri

• Exemplu:– x1 <> x2, unde x1,x2 pot lua valorile {1,2}

Problema de satisfacere a constrângerilor distribuită

• Este o problemă CSP în care variabilele şi constrângerile sunt împărţite între mai mulţi agenţi care acţionează numai pe baza cunoştinţelor lor locale, fără un control global.

Algoritmi

• Backtracking sincron

• backtracking asincron

• căutare asincronă cu angajament minim

Problema reginelor pentru N = 6

Restricţii:

• să nu se afle pe aceeaşi linie

• să nu se afle pe aceeaşi coloană.

• să nu se afle pe aceeaşi diagonală

Backtracking asincron

• Agentul a6 nu găseşte o valoare consistentă

• trimite mesaj de tip incorect agentului a4

• a4 îşi schimbă valoarea

Algoritm de căutare cu angajament minim

• Fiecare agent are o prioritate care poate fi modificată dinamic

• când un agent ia o decizie greşită prioritatea lui scade

Probleme rezolvate

• problema reginelor

• problema generală de satisfacere a constrângerilor cu restricţii exprimate prin ecuaţii de gradul întâi.