Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems

William YEOH; Pradeep VARAKANTHAM; Xiaoxun SUN; Sven KOENIG; Xiaoxun Sun

Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems

William YEOH, Pradeep VARAKANTHAM, Xiaoxun SUN, Sven KOENIG, Xiaoxun Sun

Australian Council for Educational Research (ACER)

Research output: Contribution to journal › Article › peer-review

Abstract

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper bounds from the previous DCOP when solving the next one in the sequence. Our experimental results show that the speedup gained from this procedure increases with the amount of memory the agents have available.

Original language	English
Journal	Research Collection School Of Computing and Information Systems
Publication status	Published - 1 May 2011

Disciplines

Artificial Intelligence and Robotics
Business
Operations Research, Systems Engineering and Industrial Engineering

Access to Document

https://ink.library.smu.edu.sg/sis_research/1343

Cite this

@article{dd0360fbcade44018ee062e46aa2ba8e,

title = "Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems",

abstract = " Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper bounds from the previous DCOP when solving the next one in the sequence. Our experimental results show that the speedup gained from this procedure increases with the amount of memory the agents have available.",

author = "William YEOH and Pradeep VARAKANTHAM and Xiaoxun SUN and Sven KOENIG and Xiaoxun Sun",

year = "2011",

month = may,

day = "1",

language = "English",

journal = "Research Collection School Of Computing and Information Systems",

}

TY - JOUR

T1 - Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems

AU - YEOH, William

AU - VARAKANTHAM, Pradeep

AU - SUN, Xiaoxun

AU - KOENIG, Sven

AU - Sun, Xiaoxun

PY - 2011/5/1

Y1 - 2011/5/1

N2 - Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper bounds from the previous DCOP when solving the next one in the sequence. Our experimental results show that the speedup gained from this procedure increases with the amount of memory the agents have available.

AB - Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper bounds from the previous DCOP when solving the next one in the sequence. Our experimental results show that the speedup gained from this procedure increases with the amount of memory the agents have available.

M3 - Article

JO - Research Collection School Of Computing and Information Systems

JF - Research Collection School Of Computing and Information Systems

ER -