PaperlayerView exact revision on arXiv

Source-linked AI summary

BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm

William Yeoh, Ariel Felner, Sven Koenig

arXiv:1401.3490v1cs.AI

TL;DR

DCOPs require agents to coordinate values under costly constraints, while optimal solving is NP-hard and practical algorithms must respect memory and communication limits. The paper introduces BnB-ADOPT, combining ADOPT’s asynchronous framework with depth-first branch-and-bound search, and reports faster optimal search alongside relative-error approximations.

  • Problem

    DCOP optimization is NP-hard, and existing bounded-error support provides absolute but not relative solution-cost bounds while practical applications require memory-bounded asynchronous algorithms.

  • Method

    BnB-ADOPT combines ADOPT’s message-passing framework with depth-first branch-and-bound search and adds relative-error and weighted-heuristics approximation mechanisms.

  • Results

    BnB-ADOPT was up to one order of magnitude faster than ADOPT on varied large DCOP problems and as fast as NCBB on most tested problems.

  • Takeaways & Limitations

    Relative-error mechanisms provide a more meaningful way to trade solution cost for runtime, while the Weighted Heuristics Mechanism dominated the other tested mechanisms.

  • Takeaways & Limitations

    The authors identify reducing sent messages, handling lost messages, and comparisons with additional DCOP algorithms as future work.

Abstract

from arXiv · show

Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, and Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.

1. Introduction

DCOPs formulate distributed coordination as minimizing summed constraint costs, motivating memory-bounded asynchronous search. The paper introduces BnB-ADOPT and reports faster optimal search plus relative-error approximations.

  • DCOPs assign finite-domain values to agents while constraints impose costs, and optimal solving minimizes total cost but is NP-hard.
  • Constraint optimization extends ordinary constraint satisfaction by representing preferences through constraint costs rather than only satisfied or unsatisfied constraints.
  • Fully Decentralized DCOP Algorithms: Fully decentralized inference and search algorithms trade memory requirements against communication or computational time under different conditions.Inference methods can use exponential memory, whereas search methods use polynomial memory but may send exponentially many messages.
  • 1.2.1 BnB-ADOPT: BnB-ADOPT changes ADOPT’s best-first search to depth-first branch-and-bound while retaining its asynchronous, concurrent, memory-bounded communication framework.The design targets depth-bounded DCOP search trees and restricts communication to agents sharing constraints.
  • 1.2.2 Bounded-Error Approximations: Two new mechanisms let users specify relative error bounds, addressing a limitation of absolute error bounds when the minimal solution cost is unknown.The mechanisms are implemented on top of BnB-ADOPT.
  • 1.3 Experimental Results: Up to one order of magnitude faster, BnB-ADOPT outperformed ADOPT on varied large problems and was as fast as NCBB on most tested problems.The experiments covered graph coloring, sensor-network, and meeting-scheduling problems.

2. DCOP Problems

A DCOP consists of agents, finite domains, and binary constraints whose costs depend on assigned values. Its solution space can be represented with AND/OR search trees that exploit independent subproblems.

  • 2.1 Definition of DCOP Problems: A DCOP contains a finite set of agents, finite value domains, and binary constraints assigning nonnegative costs to agent-value pairs.
  • 2.1 Definition of DCOP Problems: The formulation assumes one value per agent, while multi-variable formulations can be reduced to this representation, allowing agent and variable to be used interchangeably.
  • 2.2 Solution Space: AND/OR search trees use pseudo-trees to avoid sequentially assigning values in independent DCOP subproblems.
  • 2.2 Solution Space: OR nodes represent agents and branches represent values, while AND nodes represent partial solutions and their delta costs.For node v, the cited example gives partial solution {(a1, 1), (a2, 1), (a4, 1)} and delta cost 3.

3. BnB-ADOPT

The paper presents BnB-ADOPT as a standalone description of a memory-bounded asynchronous DCOP search algorithm, without requiring prior knowledge of ADOPT.

  • BnB-ADOPT is introduced through a self-contained description rather than as a modification requiring in-depth knowledge of ADOPT.

3.1 Search Strategies of ADOPT and BnB-ADOPT

ADOPT uses memory-bounded best-first search, whereas BnB-ADOPT replaces this strategy with depth-first branch-and-bound while retaining the same general search framework. The strategies differ in how they retain, reconstruct, expand, and prune partial solutions.

  • ADOPT: best-first search: ADOPT traverses the search tree in best-first order by repeatedly selecting the lowest-cost unexplored partial solution.Its list initially contains the root’s child AND nodes and is updated as search proceeds.
  • ADOPT: best-first search: ADOPT terminates when the upper bound is no larger than the lower bound, yielding a minimal solution cost of 12 after fifteen steps in the example.The upper bound is the cost of the best solution found, while the lower bound is an optimistic estimate.
  • ADOPT: memory limitation: To remain memory-bounded, ADOPT stores only one root-to-current branch and repeatedly reconstructs branches previously purged from memory.In the example, it discards the branch to node f and later reconstructs it before expanding node v.
  • BnB-ADOPT: depth-first branch-and-bound: Depth-first branch-and-bound expands the stack’s top node, prunes it when its cost reaches the upper bound, and otherwise pushes its grandchildren.Nodes can be ordered by increasing solution cost so the smallest-cost grandchild is expanded first.

3.2 Description of BnB-ADOPT

BnB-ADOPT combines ADOPT’s distributed notation, bound maintenance, and message framework with bounds that are updated through the pseudo-tree. Monotonic bound tightening and the root termination condition establish optimality.

  • Notation and cost terms: BnB-ADOPT uses contexts, pseudo-tree relationships, delta costs, gamma costs, and child-agent sets to represent partial solutions and subtree costs.A context contains ancestor values; delta costs capture relevant assigned constraints, while gamma costs minimize over the agent and its descendants.
  • Notation and cost terms: Gamma costs combine an AND node’s delta cost with child OR-node gamma costs, while an OR node takes the minimum gamma cost among its child AND nodes.The root gamma cost equals the minimal solution cost.
  • Bound maintenance: Agents maintain lower and upper bounds for OR nodes, AND nodes, and child OR nodes under their current contexts.These bounds are initialized using admissible heuristic values and then repeatedly updated with information from neighboring agents.
  • Bound maintenance: Bound updates preserve validity while lower bounds monotonically increase and upper bounds monotonically decrease.After finite time, the root’s termination condition and the bound property imply that the DCOP problem is solved optimally.
  • Bound maintenance: Bounds propagate upward from leaf agents through the pseudo-tree, with parent agents combining child bounds and delta costs at successive levels.The simplified Figure 6 trace illustrates sequential updates from leaves to the root.

3.2.3 Adhering to Memory Limitations

BnB-ADOPT meets memory limits by storing bounds for only one context at a time rather than for every possible ancestor assignment. This reduces per-agent memory to linear in the number of agents under the stated domain condition.

  • Memory guarantee: Using these techniques, BnB-ADOPT has memory requirements per agent that are linear in the number of agents.The memory-bounded implementation adapts techniques introduced for ADOPT.
  • Context storage: The number of contexts can be exponential in an agent’s pseudo-tree depth, so storing bounds for every context violates the memory limitation.In the example, agent a3 has four contexts corresponding to ancestor-value combinations.
  • Context storage: Each agent therefore maintains bounds for only one context at a time, whose size is at most linear in the number of agents.The number of stored bounds becomes linear in domain cardinality multiplied by the number of child agents.

3.2.4 Performing Depth-First Search

BnB-ADOPT implements asynchronous depth-first branch-and-bound through VALUE, COST, and TERMINATE messages, context changes, and monotonic value exploration. In the example, it reaches the optimal cost after nine cycles.

  • Depth-first search: BnB-ADOPT performs depth-first search by allowing each agent to take each value at most once until its upper bound changes sufficiently.Monotonically non-increasing upper bounds prevent an agent from immediately returning to a previously abandoned value.
  • Asynchronous message processing: BnB-ADOPT uses VALUE messages to propagate contexts downward and COST messages to propagate bounds upward through the pseudo-tree.TERMINATE messages propagate downward after the root satisfies the termination condition.
  • Asynchronous message processing: Agents process VALUE messages by adopting the requested context, then recomputing bounds and sending updated VALUE and COST messages.A context change initializes bounds, selects a best value, and communicates with child and parent agents.
  • Asynchronous message processing: Agents process compatible COST messages by incorporating the received bounds into their own bound updates.Incompatible contexts are not used for the receiving agent’s bound updates.
  • Example trace: BnB-ADOPT terminates after nine cycles with minimal solution cost 12 in the example.The root sends TERMINATE messages once its upper and lower bounds meet the termination condition.

3.2.5 Performing Branch-and-Bound

BnB-ADOPT adds threshold-based pruning to its asynchronous search, allowing agents to change values earlier when lower bounds reach desired thresholds.

  • Each agent maintains a threshold T_Ha, initialized to infinity; the root threshold remains infinity.Non-root agents use thresholds for pruning.
  • An agent changes to its best value when its value-specific upper bound reaches the pruning quantity min{T_Ha, X_a}.This can trigger a value change earlier than in the original procedure.
  • After changing value, an agent sends VALUE messages to its children and a COST message to its parent.This preserves the basic asynchronous communication pattern while incorporating pruning.
  • VALUE messages now include each child’s desired threshold, which the child adopts upon receipt.The desired threshold is selected so the child’s lower bound reaches that threshold.

3.2.6 Further Enhancements

BnB-ADOPT further reduces redundant work through reduced contexts, informed bound reuse, and more compact VALUE/COST message updates.

  • Reduced contexts: Reduced contexts retain only relevant ancestor values, so agents more often avoid changing contexts and reinitializing bounds.For example, agent a4’s reduced context contains only agent a2’s value rather than agents a1 and a2.
  • VALUE and COST messages: Agents send VALUE messages to children and pseudo-children containing identity, value, and desired threshold rather than the full desired context.Recipients update ancestor values only when the incoming value is more recent.
  • VALUE and COST messages: Agents use counters ID_a to determine which context values are more recent.A larger ID indicates a more recent value, and message/context values carry these IDs.
  • Bounds: If a child’s reduced context excludes agents whose values changed, the parent can preserve relevant bounds for that child.This optimization reduces unnecessary bound initialization when contexts change.
  • Bounds: When a child’s context remains compatible after a COST-driven context change, the parent reuses the child’s bounds instead of reinitializing them.The COST message’s bounds are more informed than initialized bounds.

3.2.7 Pseudocode

The BnB-ADOPT pseudocode specifies asynchronous handlers for initialization, VALUE, COST, and TERMINATE messages, using compatible and recency-aware contexts.

  • Figure 9 presents pseudocode shared by every agent, with the self variable identifying the executing agent.The context is implicit in X_a rather than indexing every variable explicitly.
  • Compatible(X, X′) holds when no agent is assigned different values in the two contexts.The predicate checks whether the contexts contain conflicting assignments.
  • PriorityMerge(X, X′) keeps the more recent value for an agent when both contexts contain that agent.Recency is determined by comparing the agents’ IDs.
  • VALUE handlers update ancestor values and thresholds, while COST handlers process child contexts and bounds.TERMINATE handlers record termination messages received from the parent.
  • BnB-ADOPT retains ADOPT’s message framework, memory requirements, message types, bound semantics, and bound-update equations.Its key difference is using thresholds for pruning rather than ADOPT’s alternative threshold use.

3.2.8 Trace

The trace follows bound initialization, asynchronous VALUE/COST propagation, context updates, value changes, and termination in a sample DCOP problem.

  • Termination: 9 cycles produce a minimal solution cost of 12, after which TERMINATE messages propagate down the pseudo-tree.The root updates its lower bound to 12 before initiating termination.
  • Trace overview: Figures 10 and 11 trace lower- and upper-bound updates, while Table 2 traces all variables.These displays summarize the example execution described in the surrounding text.
  • Cycle 1: Cycle 1 initializes contexts, bounds, values, IDs, and thresholds, then agents exchange VALUE and COST messages.Leaf agents compute bounds from delta costs, while internal agents initialize heuristic bounds.
  • Cycles 3–9: Subsequent COST messages reflect updated contexts and bounds as agents propagate the changed assignment through the pseudo-tree.The trace records changed messages from agents a3 and a4 in Cycle 3 and later cycles.

4. Bounded-Error Approximations

BnB-ADOPT supports three bounded-error mechanisms that trade solution cost for shorter runtime. Absolute-error bounds use an additive tolerance, while Relative Error and Weighted Heuristics mechanisms provide multiplicative guarantees.

  • Three approximation mechanisms let BnB-ADOPT trade solution cost for a smaller runtime under user-defined error bounds.The mechanisms are an adapted Absolute Error Mechanism, a Relative Error Mechanism, and a Weighted Heuristics Mechanism.
  • 4.1 Absolute Error Mechanism: The Absolute Error Mechanism terminates when the root upper bound is no larger than b plus the root lower bound.The returned solution cost can exceed the minimal cost by at most the user-defined absolute error bound b.
  • 4.2 Relative Error Mechanism: The Relative Error Mechanism uses a user-defined factor p to terminate when the root upper bound is no larger than p times the root lower bound.It provides a multiplicative error specification without requiring the minimal solution cost a priori.
  • 4.3 Weighted Heuristics Mechanism: The Weighted Heuristics Mechanism multiplies admissible heuristic values by a user-defined weight w to obtain a relative error bound.Its root lower bound is a lower bound on w times the minimal solution cost, and termination uses that bound.

5. Correctness and Completeness

The correctness analysis establishes finite termination for BnB-ADOPT and its suboptimal variants, then gives optimality and bounded-error guarantees for the respective algorithms.

  • The proofs apply to BnB-ADOPT and its suboptimal variants unless explicitly stated otherwise.The analysis defines correct contexts, bound-update behavior, and potential-based progress properties under asynchronous message delays.
  • With an unchanged context, lower bounds are monotonically non-decreasing while upper bounds are monotonically non-increasing.This follows because the relevant delta values remain constant and the bounds are updated by the algorithm’s update equations.
  • If ancestor values remain unchanged for at least |A| · (∆ + ϵ) + ϵ, an agent’s context becomes correct during a subsequent interval.The argument accounts for finite message delay ∆ and cycle duration ϵ, including propagation through pseudo-child agents.
  • Theorem 1 states that BnB-ADOPT and its suboptimal variants terminate after a finite amount of time.The potential decreases by more than a positive constant whenever an agent changes value after its context stops changing.
  • Theorem 2 states that BnB-ADOPT terminates with the minimal solution cost γr.The suboptimal variants instead provide the absolute, relative, and weighted upper bounds established in Theorems 3–5.

6. Experimental Evaluations

The experiments compare BnB-ADOPT with ADOPT and NCBB across multiple DCOP types and evaluate three bounded-error BnB-ADOPT variants. BnB-ADOPT generally gains speed on harder problems, while approximation improves runtime as allowed error increases.

  • Experimental setup: The experiments compare BnB-ADOPT with ADOPT and NCBB using NCCCs and cycles across graph coloring, sensor network, and meeting scheduling problems.NCCCs combine processing and communication time, whereas cycles measure the longest message chain.
  • Optimal DCOP search algorithms: BnB-ADOPT is generally faster than NCBB on sparse graphs, but their difference becomes negligible when communication is slow.NCBB sends updates along pseudo-tree backedges, whereas BnB-ADOPT sends messages only to parent agents; the effect is stronger in dense graphs.
  • Optimal DCOP search algorithms: BnB-ADOPT is at least half an order of magnitude faster than ADOPT on small graph-coloring problems, with speedup increasing as problem complexity grows.The same trend appears as the constraint-cost range increases and for sensor-network and meeting-scheduling problems.
  • Optimal DCOP search algorithms: ADOPT can outperform BnB-ADOPT on simple problems because best-first search exploits well-informed heuristics, while BnB-ADOPT avoids repeatedly reconstructing purged partial solutions.With well-informed heuristics, ADOPT explores fewer unique contexts but many more repeated contexts than BnB-ADOPT.
  • Suboptimal BnB-ADOPT variants: When the relative error bound is 3, all three variants produce normalized solution costs below 1.3 rather than 3, although costs increase with the bound.AEM usually yields larger normalized solution costs than REM at the same relative error bound.
  • Suboptimal BnB-ADOPT variants: As the relative error bound increases, all three suboptimal BnB-ADOPT variants reduce normalized runtime and approach near-immediate termination around a bound of 2.0.The absolute-error variant often terminates faster than the relative-error variant because its corresponding absolute bound can be larger.
  • Suboptimal BnB-ADOPT variants: For a normalized solution cost of 1.05, normalized runtimes are about 0.18 for WHM, 0.30 for AEM, and 0.35 for REM, making WHM the best-performing variant.This ordering also appears for sensor-network and meeting-scheduling problems.

7. Conclusions

The paper introduces BnB-ADOPT, combining ADOPT’s asynchronous communication framework with depth-first branch-and-bound search, and evaluates approximation mechanisms for trading solution cost against runtime.

  • BnB-ADOPT: BnB-ADOPT changes ADOPT’s best-first search to depth-first branch-and-bound while retaining its message-passing and communication framework.The algorithm is memory-bounded and supports concurrent, asynchronous agents communicating only when they share constraints.
  • Experimental results: Up to one order of magnitude faster than ADOPT, BnB-ADOPT found cost-minimal solutions across a variety of large DCOP problems.It was as fast as NCBB for most of these problems.
  • Approximation mechanisms: Three approximation mechanisms trade BnB-ADOPT solution cost for smaller runtime: absolute error, relative error, and weighted heuristics.The relative-error mechanism lets users specify a relative rather than absolute error bound.
  • Approximation mechanisms: The Weighted Heuristics Mechanism dominated the Absolute Error Mechanism and Relative Error Mechanism in the experiments.The authors state that it should also apply to other DCOP search algorithms because they benefit from heuristic-focused search.
  • Future work: Future work targets reducing sent messages, handling lost messages, studying pseudo-tree and preprocessing effects, and comparing against additional DCOP algorithms.Planned comparisons include OptAPO, DPOP, and their variants.
Loading 1401.3490v1…