Hui en dia, molts problemes reals poden modelar-se com problemes
de satisfacció de restriccions (CSPs) i es resolen usant tècniques
específiques de satisfacció de restriccions. Estos problemes
pertanyen a àrees com ara la Intel·ligència Artificial, la
Investigació Operativa, sistemes d'informació, bases de dades,
etc. La majoria d'estos problemes poden modelar-se de forma
natural per mitjà de CSPs. No obstant això, alguns d'estos
problemes són de naturalesa distribuïda, bé per motius de
seguretat o bé per requeriments de privacitat o restriccions
espacials; açò requereix que aquest tipus de problemes es
modelitzen com a problemes de satisfacció de restriccions
distribuïts (DCSPs), on el conjunt de variables i restriccions del
problema està distribuït entre un conjunt d'agents que
s'encarreguen de resoldre el seu propi subproblema i han de
coordinar-se amb la resta d'agents per a aconseguir una solució al
problema global.

En la literatura de satisfacció de restriccions, la necessitat de
manejar DCSP va començar a tractar-se a principis dels 90. No
obstant això, la majoria dels investigadors que treballen en aquest
camp centren la seua atenció en algorismes on cada agent maneja una
única variable. Estos algorismes poden ser transformats perquè cada
agent manege múltiples variables, encara que els algorismes
resultants no són escalables per a manejar grans subproblemes locals
degut tant als requeriments espacials com al seu cost computacional.
Per tant, la resolució de problemes reals per mitjà d'aquest tipus
d'algorismes resulta pràcticament inviable.

En esta tesi presentem nous algorismes per a la resolució de
problemes de satisfacció de restriccions distribuïts capaços de
manejar múltiples variables per agent. Estos algorismes realitzen un
maneig eficient de la informació obtinguda per mitjà de la
comunicació entre els agents per a aconseguir una major eficiència
durant el procés de resolució. A més, els seus requeriments
espacials són mínims, per la qual cosa és capaç de manejar grans
subproblemes locals. Diversos algorismes i tècniques heurístiques
són presentades en esta tesi perquè cada agent realitze eficaçment
la cerca de solucions parcials del seu subproblema.

A més, els problemes de satisfacció de restriccions poden també
modelar grans problemes reals, que generalment impliquen models
amb un gran nombre de variables i restriccions. Aquest tipus de
problemes pot ser manejat de manera global únicament mitjançant un
exagerat cost computacional. Açò motiva la següent contribució
d'esta tesi que consisteix en particionar aquest tipus de
problemes per a tractar-los posteriorment més eficaçment per mitjà
dels algorismes proposats per a resoldre DCSPs. En esta tesi
plantegem tres formes de particionar un problema: la primera es
basa en tècniques de particionament de grafs, la segona en la
identificació d'estructures d'arbre i la tercera en la
identificació d'entitats pròpies de cada subproblema. Tant les
propostes de particionamiento de CSPs, com els nous algoritmes de
resolució de DCSPs, constituïxen el nucli de les aportacions
d'esta tesi. Finalment s'avaluen els mètodes proposats sobre
escenaris de prova, s'efectua una revisió crítica i es plantegen
línies de futur.