H-DPOP: Using Hard Constraints for Search Space Pruning in DCOP
In distributed constraint optimization problems, dynamic programming methods have been recently proposed (e.g. DPOP). In dynamic programming many valuations are grouped together in fewer messages, which produce much less networking overhead than search. Nevertheless, these messages are exponential i...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2008
|
| Subjects: | |
| Online Access: | https://ink.library.smu.edu.sg/sis_research/2215 https://ink.library.smu.edu.sg/context/sis_research/article/3215/viewcontent/H_DPOP__Using_Hard_Constraints_for_Search_Space_Pruning_in_DCOP.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | In distributed constraint optimization problems, dynamic programming methods have been recently proposed (e.g. DPOP). In dynamic programming many valuations are grouped together in fewer messages, which produce much less networking overhead than search. Nevertheless, these messages are exponential in size. The basic DPOP always communicates all possible assignments, even when some of them may be inconsistent due to hard constraints. Many real problems contain hard constraints that significantly reduce the space of feasible assignments. This paper introduces H-DPOP, a hybrid algorithm that is based on DPOP, which uses Constraint Decision Diagrams (CDD) to rule out infeasible assignments, and thus compactly represent UTIL messages. Experimental results show that H-DPOP requires several orders of magnitude less memory than DPOP, especially for dense and tightly-constrained problems. |
|---|