Bidirectional heuristic search potentially decreases search effort in combinatorial search problems amenable to backward search. To date, bidirectional search has been limited to minimization or shortest path problems. This paper extends the notion of bidirectional heuristic search to (constrained) longest-path problems. We present a bidirectional heuristic search algorithm for longest simple path (LSP) in undirected graphs, and prove its correctness. We then suggest several refinements, as well as a generalization to other types of longest path problems, such as Coil-in-a-box (CIB). Empirical evaluation shows that, as with many forms of bidirectional search, sometimes unidirectional search wins, but for a sizable chunk of problem instances, bidirectional search performs better by expanding fewer nodes and achieves a shorter runtime despite the increased overhead per expansion.

Agents operating in the real world must cope with the fact that time passes while they plan. In some cases, such as under tight deadlines, the only way for such an agent to achieve its goal is to execute an action before a complete plan has been found. This problem is called Concurrent Planning and Execution (CoPE). Previous work on CoPE relied on a value function that assumes search will finish before actions are executed, causing the agent to be overly pessimistic in many situations. In this paper, we define a new value function that takes into account the agent's ability to dispatch actions incrementally. This allows us to devise a much simpler algorithm for concurrent planning and execution. An experimental evaluation on problems with time pressure shows that the new method significantly outperforms the previous state-of-the-art.

Bidirectional heuristic search has the potential to decrease search time in combinatorial search problems amenable to backward search. To date, bidirectional search has been limited to minimization or shortest path problems. This paper extends the notion of bidirectional heuristic search to (constrained) longest path problems, which turns out to be non-trivial due to the path necessarily being part of the state and the inapplicability of standard bidirectional heuristic search techniques such as meet-in-the-middle (MM) and BAE*. We present a basic bidirectional heuristic search for longest simple path (LSP) in undirected graphs, and prove its correctness. We then suggest several refinements and optimizations, as well as a generalization to other types of longest path problems Coil-in-a-box (CIB). Empirical evaluation shows that, as with many forms of bidirectional search, sometimes unidirectional search wins, but for a sizable chunk of problem instance types, bidirectional search performs better by expanding fewer nodes and achieves a shorter runtime despite the increased overhead per expansion.

Standard temporal planning assumes that planning takes place offline, and then execution starts at time 0. Recently, situated temporal planning was introduced, where planning starts at time 0, and execution occurs after planning terminates. Situated temporal planning reflects a more realistic scenario where time passes during planning. However, in situated temporal planning a complete plan must be generated before any action is executed. In some problems with time pressure, timing is too tight to complete planning before the first action must be executed. For example, an autonomous car that has a truck backing towards it should probably move out of the way now, and plan how to get to its destination later. In this paper, we propose a new problem setting: concurrent planning and execution, in which actions can be dispatched (executed) before planning terminates. Unlike previous work on planning and execution, we must handle wall clock deadlines that affect action applicability and goal achievement (as in situated planning) while also supporting dispatching actions before a complete plan has been found. We extend previous work on metareasoning for situated temporal planning to develop an algorithm for this new setting. Our empirical evaluation shows that when there is strong time pressure, our approach outperforms situated temporal planning.

The longest simple path and snake-in-a-box are combinatorial search problems of considerable research interest. Recent work has recast these problems as special cases of a generalized longest simple path (GLSP) framework, and showed how to generate improved search heuristics for them. The greatest reduction in search effort was based on SPQR tree rules, but it was posed as an open problem how to use them optimally. Unrelated to search, a theoretical paper on the existence of simple cycles that include three given edges answers such queries in linear time with SPQR trees. These theoretical results are utilized in this paper to develop advanced heuristics and search partitioning for GLSP. Empirical results on grid-based graphs show that these heuristics can result in orders of magnitude reduction in the number of expansions, as well as significantly reduced overall runtime in most cases.

Metareasoning can be a helpful technique for controlling search in situations where computation time is an important resource, such as real-time planning and search, algorithm portfolios, and concurrent planning and execution. Metareasoning often involves an estimate of the remaining search time of a running algorithm, and several ways to compute such estimates have been presented in the literature. In this paper, we argue that many applications actually require a full estimated probability distribution over the remaining time, rather than just a point estimate of expected search time. We study several methods for estimating such distributions, including some novel adaptations of existing schemes. To properly evaluate the estimates, we introduce `put-up or shut-up games', which probe the distributional estimates without requiring infeasible computation. Our experimental evaluation reveals that estimates that are more accurate in expected value do not necessarily deliver better distributions, yielding worse scores in the game.

Navigation among dynamic obstacles is a fundamental task in robotics that has been modeled in various ways. In Safe Interval Path Planning, location is discretized to a grid, time is continuous, future trajectories of obstacles are assumed known, and planning takes place offline. In this work, we define the Real-time Safe Interval Path Planning problem setting, in which the agent plans online and must issue its next action within a strict time bound. Unlike in classical real-time heuristic search, the cost-to-go in Real-time Safe Interval Path Planning is a function of time rather than a scalar. We present several algorithms for this setting and prove that they learn admissible heuristics. Empirical evaluation shows that the new methods perform better than classical approaches under a variety of conditions.

Agents that plan and act in the real world must deal with the fact that time passes as they are planning. When timing is tight, there may be insufficient time to complete the search for a plan before it is time to act. By commencing execution before search concludes, one gains time to search by making planning and execution concurrent. However, this incurs the risk of making incorrect action choices, especially if actions are irreversible. This tradeoff between opportunity and risk is the problem addressed in this paper. Our main contribution is to formally define this setting as an abstract metareasoning problem. We find that the abstract problem is intractable. However, we identify special cases that are solvable in polynomial time, develop greedy solution algorithms, and, through tests on instances derived from search problems, find several methods that achieve promising practical performance. This work lays the foundation for a principled time-aware executive that concurrently plans and executes.

The longest simple path and snake-in-a-box are combinatorial search problems of considerable research interest. We create a common framework of longest constrained path in a graph that contains these two problems, as well as other interesting maximum path problems, as special cases. We analyze properties of this general framework, produce bounds on the path length that can be used as admissible heuristics for all problem types therein. For the special cases of longest simple path and snakes, these heuristics are shown to reduce the number of expansions when searching for a maximal path, which in some cases leads to reduced search time despite the significant overhead of computing these heuristics.

In online planning, search is concurrent with execution. Under the formulation of planning as heuristic search, when a planner commits to an action, it re-roots its search tree at the node representing the outcome of that action. For the system to remain controlled, the planner must commit to a new action (perhaps a no-op) before the previously chosen action completes. This time pressure results in a real-time search. In this time-bounded setting, it can be beneficial to commit early, in order to perform more lookahead search focused below an upcoming state. In this paper, we propose a principled method for making this commitment decision. Our experimental evaluation shows that our scheme can outperform previously-proposed fixed strategies.

There has been much recent work on finding paths in grid maps among moving obstacles. However, in addition to assuming complete omniscience regarding the map and the obstacles' trajectories, previous work has also assumed that time stands still while the agent plans. In this paper, we address situated pathfinding, in which time passes and the obstacles continue to move while the agent plans. We study the choice of state space representation and search algorithm, with a focus on whether conclusions drawn from studies in the off-line case continue to hold in a situated setting.

Agents that plan and act in the real world must deal with the fact that time passes as they are planning. In the presence of tight deadlines, there may be insufficient time to complete the search for a plan before it is time to act. One can gain additional time to search by starting to act before a complete plan is found, incurring the risk of making incorrect action choices. This tradeoff between opportunity and risk, inherent in interleaving planning and execution, is a non-trivial metareasoning problem addressed in this paper.

If a planning agent is considering taking a bus, for example, the time that passes during its planning can affect the feasibility of its plans, as the bus may depart before the agent has found a complete plan. Previous work on this situated temporal planning setting proposed an abstract deliberation scheduling scheme for maximizing the probability of finding a plan that is still feasible at the time it is found. In this paper, we extend the deliberation scheduling approach to address problems in which plans can differ in their cost. Like the planning deadlines, these costs can be uncertain until a complete plan has been found. We show that finding a deliberation policy that minimizes expected cost is PSPACE-hard and that even for known costs and deadlines the optimal solution is a contingent, rather than sequential, schedule. We then analyze special cases of the problem and use these results to propose a greedy scheme that considers both the uncertain deadlines and costs. Our empirical evaluation shows that the greedy scheme performs well in practice on a variety of problems, including some generated from planner search trees.

Recent work on bidirectional search defined a lower bound on costs of paths between pairs of nodes, and introduced a new algorithm, NBS, which is based on this bound. Building on these results, we introduce DVCBS, a new algorithm that aims to to further reduce the number of expansions. Generalizing beyond specific algorithms, we then propose a method for enhancing heuristics by propagating such lower bounds (lb-propagation) between frontiers. This lb-propagation can be used in existing algorithms, often improving their performance, as well as making them "well behaved".

Making plans that depend on external events can be tricky. For example, an agent considering a partial plan that involves taking a bus must recognize that this partial plan is only viable if completed and selected for execution in time for the agent to arrive at the bus stop. This setting raises the thorny problem of allocating the agent’s planning effort across multiple open search nodes, each of which has an expiration time and an expected completion effort in addition to the usual estimated plan cost. This paper formalizes this metareasoning problem, studies its theoretical properties, and presents several algorithms for solving it. Our theoretical results include a surprising connection to job scheduling, as well as to deliberation scheduling in time-dependent planning. Our empirical results indicate that our algorithms are effective in practice. This work advances our understanding of how heuristic search planners might address realistic problem settings.

NBS is a non-parametric bidirectional search algorithm proven to expand at most twice the number of node expansions required to verify the optimality of a solution. We introduce new variants of NBS that are aimed at finding all optimal solutions. We then introduce an algorithmic framework that includes NBS as a special case. Finally, we introduce DVCBS, a new algorithm in this framework that aims to further reduce the number of expansions. Unlike NBS, DVCBS does not have any worst-case bound guarantees, but in practice it outperforms NBS in verifying the optimality of solutions.

Recent work in bidirectional heuristic search characterize pairs of nodes from which at least one node must be expanded in order to ensure optimality of solutions. We use these findings to propose a method for improving existing heuristics by propagating lower bounds between the forward and backward frontiers. We then define a number of desirable properties for bidirectional heuristic search algorithms, and show that applying the bound propagations adds these properties to many existing algorithms (e.g. to the MM family of algorithms). Finally, experimental results show that applying these propagations significantly reduce the running time of various algorithms.

NBS is a non-parametric bidirectional search algorithm, proved to expand at most twice the number of node expansions required to verify the optimality of a solution. We introduce new variants of NBS that are aimed at finding all optimal solutions. We then introduce an algorithmic framework that includes NBS as a special case. Finally, we introduce DVCBS, a new algorithm in this framework that aims to further reduce the number of expansions. Unlike NBS, DVCBS does not have any worst-case bound guarantees, but in practice it outperforms NBS in verifying the optimality of solutions.

We examine theoretical properties of value of information (VOI) in the selection problem, and identify cases of submodularity and supermodularity. We use these properties to compute approximately optimal measurement batch policies, implemented on a “wine selection problem” example.

Multi-agent pathfinding (MAPF) is an area of expanding research interest. At the core of this research area, numerous diverse search-based techniques were developed in the past 6 years for optimally solving MAPF under the sum-of-costs objective function. In this paper we survey these techniques, while placing them into the wider context of the MAPF field of research. Finally, we provide analytical and experimental comparisons that show that no algorithm dominates all others in all circumstances. We conclude by listing important future research directions.

Given a set of items of unknown utility, we need to select one with a utility as high as possible (“the selection problem”). Measurements (possibly noisy) of item values prior to selection are allowed, at a known cost. The goal is to optimize the overall sequential decision process of measurements and selection. Value of information (VOI) is a well-known scheme for selecting measurements, but the intractability of the problem typically leads to using myopic VOI estimates. Other schemes have also been proposed, some with approximation guarantees, based on submodularity criteria. However, it was observed that the VOI is not submodular in general. In this paper we examine theoretical properties of VOI for the selection problem, and identify cases of submodularity and supermodularity. We suggest how to use these properties to compute approximately optimal measurement batch policies, with an example based on a “wine selection problem”.

Meta-reasoning can improve numerous search algorithms, but necessitates collection of statistics to be used as probability distributions, and involves restrictive meta-reasoning assumptions. The recently suggested scheme of type systems in search algorithms is used in this paper for collecting these statistics. The statistics are then used to better estimate the unknown quantity of expected regret of computing a heuristic in Rational Lazy IDA* (RLIDA*), and also facilitate a second improvement due to relaxing one of the unrealistic meta-reasoning assumptions in RLIDA*.

Conflict-Based Search (CBS) and its generalization, Meta-Agent CBS are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces ICBS, an improved version of CBS. ICBS incorporates three orthogonal improvements to CBS which are systematically described and studied. Experimental results show that each of these improvements reduces the runtime over basic CBS by up to 20x in many cases. When all three improvements are combined, an even larger improvement is achieved, producing state-ofthe art results for a number of domains.

Recent advances in metareasoning for search has shown its usefulness in improving numerous search algorithms. This paper applies rational metareasoning to IDA* when several admissible heuristics are available. The obvious basic approach of taking the maximum of the heuristics is improved upon by lazy evaluation of the heuristics, resulting in a variant known as Lazy IDA*. We introduce a rational version of lazy IDA* that decides whether to compute the more expensive heuristics or to bypass it, based on a myopic expected regret estimate. Empirical evaluation in several domains supports the theoretical results, and shows that rational lazy IDA* is a state-of-the-art heuristic combination method.

In this paper we discuss and experiment with Lazy A*, a variant of A* where heuristics are evaluated lazily and with Rational Lazy A*, which decides whether to compute the more expensive heuristics at all, based on a myopic value of information estimate. Full version appears in IJCAI-2013.

UCT, a state-of-the art algorithm for Monte Carlo tree search (MCTS) in games and Markov decision processes, is based on UCB, a sampling policy for the Multi-armed Bandit problem (MAB) that minimizes the cumulative regret. However, search differs from MAB in that in MCTS it is usually only the final ``arm pull'' (the actual move selection) that collects a reward, rather than all ``arm pulls''. Therefore, it makes more sense to minimize the simple regret, as opposed to the cumulative regret. We begin by introducing policies for multi-armed bandits with lower finite-time and asymptotic simple regret than UCB, using it to develop a two-stage scheme (SR+CR) for MCTS which outperforms UCT empirically. Optimizing the sampling process is itself a metareasoning problem, a solution of which can use value of information (VOI) techniques. Although the theory of VOI for search exists, applying it to MCTS is non-trivial, as typical myopic assumptions fail. Lacking a complete working VOI theory for MCTS, we nevertheless propose a sampling scheme that is ``aware'' of VOI, achieving an algorithm that in empirical evaluation outperforms both UCT and the other proposed algorithms.

UCT, a state-of-the art algorithm for Monte Carlo tree search (MCTS),is based on UCB, a policy for the Multi-armed Bandit problem (MAB) thatminimizes the cumulative regret. However, search differs from MAB inthat in MCTS it is usually only the final ``arm pull''that collects a reward, rather than all ``arm pulls''.Therefore, it makes more sense to minimize the simple, rather thancumulative, regret. We introduce policies formulti-armed bandits with lower simpleregret than UCB and develop a two-stage scheme (SR+CR) for MCTSwhich outperforms UCT empirically. We also propose a samplingscheme based on value of information (VOI), achieving an algorithmthat empirically outperforms other proposed algorithms.

The following sequential decision problem is considered: given a set of items of unknown utility, an item with as high a utility as possible must be selected ("the selection problem"). Measurements (possibly noisy) of item features prior to selection are allowed at known costs. The goal is to optimize the overall sequential decision process of measurements and selection. Value of information (VOI) is a well-known scheme for selecting measurements, but the intractability of the problem typically leads to using myopic VOI estimates. In the selection problem, myopic VOI frequently badly underestimates the VOI, leading to inferior measurement policies. In this paper, the strict myopic assumption is relaxed into a scheme termed semimyopic, providing a spectrum of methods that can improve the performance of measurement policies. In particular, the efficiently computable method of "blinkered" VOI is proposed, and theoretical bounds for important special cases are examined. Empirical evaluation of "blinkered" VOI in the selection problem with normally distributed item values shows that it performs much better than pure myopic VOI.

In the Canadian Traveler Problem (CTP) a traveling agent is given a weighted graph, where some of the edges may be blocked, with a known probability. The agent needs to travel to a given goal. A solution for CTP is a policy, that has the smallest expected traversal cost. CTP is intractable. Previous work has focused on the case of a single agent. We generalize CTP to a repeated task version where a number of agents need to travel to the same goal, minimizing their combined travel cost. We provide optimal algorithms for the special case of disjoint path graphs. Based on a previous UCT-based approach for the single agent case, a framework is developed for the multi-agent case and four variants are given - two of which are based on the results for disjoint-path graphs. Empirical results show the benefits of the suggested framework and the resulting heuristics. For small graphs where we could compare to optimal policies, our approach achieves near optimal results at only a fraction of the computation cost.

Various tasks in decision making and decision support systems require selecting a preferred subset of a given set of items. Here we focus on problems where the individual items are described using a set of characterizing attributes, and a generic preference specification is required, that is, a specification that can work with an arbitrary set of items. For example, preferences over the content of an online newspaper should have this form: At each viewing, the newspaper contains a subset of the set of articles currently available. Our preference specification over this subset should be provided offline, but we should be able to use it to select a subset of any currently available set of articles, e.g., based on their tags. We present a general approach for lifting formalisms for specifying preferences over objects with multiple attributes into ones that specify preferences over subsets of such objects. We also show how we can compute an optimal subset given such a specification in a relatively efficient manner. We provide an empirical evaluation of the approach as well as some worst-case complexity results.

Recent scaling up of partially observable Markov decision process (POMDP) solvers toward realistic applications is largely due to point-based methods that quickly converge to an approximate solution for medium-sized domains. These algorithms compute a value function for a finite reachable set of belief points, using backup operations. Point-based algorithms differ on the selection of the set of belief points and on the order by which backup operations are executed on the selected belief points. We first show how current algorithms execute a large number of backups that can be removed without reducing the quality of the value function. We demonstrate that the ordering of backup operations on a predefined set of belief points is important. In the simpler domain of MDP solvers, prioritizing the order of equivalent backup operations on states is known to speed up convergence. We generalize the notion of prioritized backups to the POMDP framework, showing how existing algorithms can be improved by prioritizing backups. We also present a new algorithm, which is the prioritized value iteration, and show empirically that it outperforms current point-based algorithms. Finally, a new empirical evaluation measure (in addition to the standard runtime comparison), which is based on the number of atomic operations and the number of belief points, is proposed in order to provide more accurate benchmark comparisons.

A common solution to multi-agent decision problems is to commit a team of collaborating agents to a joint plan. Once committed, any deviation from the plan by an agent, is hazardous. Hence, in many such systems, agents ignore potential beneficial actions not in the plan, (even if such "opportunistic" actions increase the expected utility of the team). We model the (stochastic) tradeoff of such opportunistic actions vs. continued commitment to the joint plan, and address this issue as a formal decision problem under uncertainty. We use a modified version of the AWOL model, presented in an earlier paper, showing how it works in the context of a simplified version of the unreal tournament (TM) computer game. Empirical results suggest that it is faster to compute the solution to the AWOL abstraction than to solve the problem in the original domain.

Agents operating in the real world need to handle both uncertainty and resource constraints. Typical problems in this domain are optimization of sequences of observations, and optimal allocation of computation tasks during reasoning and search (also known as meta-reasoning). In both domains, a crucial issue is value of information, a quantity hard to compute in general, and thus usually estimated using severe assumptions, such as myopic and independence of information sources. This paper extends recent work on non-myopic value of information in graphical models, that assumed a chain-shaped graph and exact measurements. Suitably relaxing the assumption of exact measurements still allows for a provably close approximation of the optimal subset (of observations) selection, and for approximating the optimal conditional plan. The method is shown to be efficient and to provide a significant advantage in expected reward over the myopic and greedy value of information scheme.

In recent years, CP-nets have emerged as a useful tool for supporting preference elicitation, reasoning, and representation. CP-nets capture and support reasoning with qualitative conditional preference statements, statements that are relatively natural for users to express. In this paper, we extend the CP-nets formalism to handle another class of very natural qualitative statements one often uses in expressing preferences in daily life - statements of relative importance of attributes. The resulting formalism, TCP-nets, maintains the spirit of CP-nets, in that it remains focused on using only simple and natural preference statements, uses the ceteris paribus semantics, and utilizes a graphical representation of this information to reason about its consistency and to perform, possibly constrained, optimization using it. The extra expressiveness it provides allows us to better model tradeoffs users would like to make, more faithfully representing their preferences.

Whereas data mining in structured data focuses on frequent data values, in semistructured and graph data mining, the issue is frequent labels and common specific topologies. The structure of the data is just as important as its content. We study the problem of discovering typical patterns of graph data, a task made difficult because of the complexity of required subtasks, especially subgraph isomorphism. In this paper, we propose a new apriori-based algorithm for mining graph data, where the basic building blocks are relatively large, disjoint paths. The algorithm is proven to be sound and complete. Empirical evidence shows practical advantages of our approach for certain categories of graphs

Prior work has shown that context-specific independence (CSI) in Bayes networks can be exploited to speed up belief updating. We examine how networks with variables exhibiting mutual exclusion (e.g., “selector variables”), as well as CSI, can be efficiently updated. In particular, directed-path singly connected and polytree networks that have an additional common selector variable can be updated in linear time (given null and general conjunctive evidence, respectively), where quadratic time would be needed without the mutual exclusion requirement. The above results have direct applications, as such network topologies can be used in predicting the ramifications of user selection in some multimedia data browsing systems. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 703–725, 2004.

We present a new approach for adaptive presentation of structured information, based on preference-based constrained optimization techniques rooted in qualitative decision-theory. In this approach, document presentation is viewed as a configuration problem whose goal is to determine the optimal presentation of a document, while taking into account the preferences of the content provider, viewer interaction with the browser, and, possibly, some layout constraints. The preferences of the content provider are represented by a CP-net, a graphical, qualitative preference model developed in Boutilier et al. [1999]. The layout constraints are represented as geometric constraints, integrated within the optimization process. We discuss the theoretical basis of our approach, as well as implemented prototype systems for Web pages and for general media-rich document presentation.

Collaboration of multiple intelligent agents on a shared task is a complex research issue, made particularly difficult when communication is limited or impossible. A common solution in multi-agent systems is to commit a team of collaborating agents to a joint plan. Since any deviation from the plan by an agent is hazardous, the common treatment of potential unplanned opportunities is either by ignoring them (even when "opportunistic" actions increase the expected utility of the team), or by ad-hoc rules determining whether to accept such opportunities. Neither of these solutions is desirable. In our framework, Abstract World for Opportunistic Local decisions (AWOL for short), we attempt a disciplined treatment of opportunistic actions, in the context of an existing joint plan. The idea is to model the (stochastic) tradeoff of such opportunistic actions vs. continued commitment to the joint plan, while abstracting away as much as possible from the state of the world. The abstract model is evaluated using strict decision-theoretic criteria, with the goal of applying the optimal decision on whether to accept an opportunistic action in the original domain.

Whereas data mining in structured data focuses on frequent data values, in semistructured and graph data the emphasis is on frequent labels and common topologies. Here, the structure of the data is just as important as its content. We study the problem of discovering typical patterns of graph data. The discovered patterns can be useful for many applications, including: compact representation of source information and a road-map for browsing and querying information sources. Difficulties arise in the discovery task from the complexity of some of the required sub-tasks, such as sub-graph isomorphism. This paper proposes a new algorithm for mining graph data, based on a novel definition of support. Empirical evidence shows practical, as well as theoretical, advantages of our approach.

. Counter constraints are a naturalrepresentation of constraints on the finite capacity of resources in resource-allocation type problems. They are a generic family of non-binary constraints that limit the number of variables that may be assigned particular values. Counter constraints can be represented by binary constraints, at a cost. We analyse the cost, show how a counter can be represented as a linear number of binary constraints, and demonstrate empirically that even with the optimal reduction,an explicit representation of counters is preferable to their representation as a set of binary constraints. For counter constraints, value ordering is essential. An heuristic for value ordering on constraint satisfaction problems (CSP), based on the estimated likelihoodof a solution, is presented. The proposed value ordering heuristic is useful for counter constraints, as well as for binary CSPs, where it can be used to approximate the number of solutions consistent with a particular value assignment to a variable. The proposed value ordering heuristic integrates counter constraints with binary constraint networks in a novel manner. Counter constraints are problematic for most heuristics, which are local in scope, yet we demonstrated empirically that the proposed value ordering heuristic is significantly superior to heuristics used in previous work.

Computation of marginal probabilities in Bayes nets is central to numerous reasoning and automatic decision-making systems. This paper presents a deterministic approximation scheme for this hard problem that supplies provably correct bounds by aggregating probability mass in independence-based (IB) assignments. It refines belief updating methods. It approximates posterior probabilities by finding a small number of the highest probability complete (or evidentially supported) assignments. Under certain assumptions, the probability mass in the union of these assignments is sufficient to obtain a good approximation. Such methods are especially useful for highly connected networks. Since IB assignments contain fewer assigned variables, the probability mass in each assignment is greater than in the respective complete assignment. Thus, fewer assignments are sufficient, and a good approximation can be obtained efficiently. Two classes of algorithms for finding high-probability assignments are suggested: best-first heuristic search and a special integer linear program (ILP). Since IB assignments may be overlapping events in probability space, accumulating the mass in a set of assignments may be hard. In the ILP variant, it is easy to avoid the problem by adding equations that prohibit overlap. In the best-first search algorithm, other schemes are necessary, but experimental results suggest that using inclusion-exclusion (potentially exponential-time in the worst case) in the overlap cases is not too expensive for most problem instances.