Loading...
Please wait, while we are loading the content...
Similar Documents
A complete distributed constraint optimization method for non-traditional pseudotree arrangements (2007)
| Content Provider | CiteSeerX |
|---|---|
| Author | Atlas, James |
| Description | Distributed Constraint Optimization (DCOP) is a general framework that can model complex problems in multi-agent systems. Several current algorithms that solve general DCOP instances, including ADOPT and DPOP, arrange agents into a traditional pseudotree structure. We introduce an extension to the DPOP algorithm that handles an extended set of pseudotree arrangements. Our algorithm correctly solves DCOP instances for pseudotrees that include edges between nodes in separate branches. The algorithm also solves instances with traditional pseudotree arrangements using the same procedure as DPOP. We compare our algorithm with DPOP using several metrics including the induced width of the pseudotrees, the maximum dimensionality of messages and computation, and the maximum sequential path cost through the algorithm. We prove that for some problem instances it is not possible to generate a traditional pseudotree using edge-traversal heuristics that will outperform a cross-edged pseudotree. We use multiple heuristics to generate pseudotrees and choose the best pseudotree in linear space-time complexity. For some problem instances we observe significant improvements in message and computation sizes compared to DPOP. |
| File Format | |
| Language | English |
| Publisher Date | 2007-01-01 |
| Publisher Institution | In: AAMAS |
| Access Restriction | Open |
| Subject Keyword | Multi-agent System Traditional Pseudotree Arrangement General Framework Several Current Algorithm Maximum Sequential Path Cost Maximum Dimensionality Multiple Heuristic Extended Set Arrange Agent Pseudotree Arrangement Non-traditional Pseudotree Arrangement Traditional Pseudotree Structure Cross-edged Pseudotree Linear Space-time Complexity Induced Width Separate Branch Several Metric Dpop Algorithm Dcop Instance Complex Problem Traditional Pseudotree Constraint Optimization Method Significant Improvement Edge-traversal Heuristic Computation Size General Dcop Instance Problem Instance Constraint Optimization |
| Content Type | Text |
| Resource Type | Article |
