Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems

Armstrong, Aaron A.; Durfee, Edmund H.

Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Distributed Artificial Intelligence. Pages 620-624.

Abstract

Cooperative distributed problem solving (COPS) by loosely-coupled agents can be effectively modeled as a distributed constraint satisfaction problem (DCSP) where each agent has multiple local variables. DCSP protocols typically impose (partial) orders on agents to ensure systematic exploration of the search space, but the ordering decisions can have a dramatic effect on the overall problem-solving effort. In this paper, we examine several heuristics for ordering agents, and conclude that the best heuristics attempt to order agents based on the cumulative difficulty of finding assignments to their local variables. Less costly heuristics are sometimes also effective depending on the structure of the variables' constraints, and we describe the tradeoffs between heuristic cost and quality . Finally, we also show that a combined heuristic, with weightings determined through a genetic algorithm, can lead to the best performance.

Aaron A. Armstrong, and Edmund H. Durfee. 1997. Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97. IJCAI, 620–624. https://ijcai.org/proceedings/1997/91

@inproceedings{ijcai1997p91,
  title     = {Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems},
  author    = {Armstrong, Aaron A. and Durfee, Edmund H.},
  booktitle = {Proceedings of the Fifteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-97}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Martha E. Pollack},
  pages     = {620--624},
  year      = {1997},
  note      = {Distributed Artificial Intelligence},
  url       = {https://ijcai.org/proceedings/1997/91},
}

TY  - CPAPER
TI  - Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems
AU  - Armstrong, Aaron A.
AU  - Durfee, Edmund H.
T2  - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1997
SP  - 620
EP  - 624
UR  - https://ijcai.org/proceedings/1997/91
ER  -