Eric A. Hansen

JAIR Journal 2022 Journal Article

Strategy Graphs for Influence Diagrams

• Eric A. Hansen
• Jinchuan Shi
• James Kastrantas

An influence diagram is a graphical model of a Bayesian decision problem that is solved by finding a strategy that maximizes expected utility. When an influence diagram is solved by variable elimination or a related dynamic programming algorithm, it is traditional to represent a strategy as a sequence of policies, one for each decision variable, where a policy maps the relevant history for a decision to an action. We propose an alternative representation of a strategy as a graph, called a strategy graph, and show how to modify a variable elimination algorithm so that it constructs a strategy graph. We consider both a classic variable elimination algorithm for influence diagrams and a recent extension of this algorithm that has more relaxed constraints on elimination order that allow improved performance. We consider the advantages of representing a strategy as a graph and, in particular, how to simplify a strategy graph so that it is easier to interpret and analyze.

AIJ Journal 2021 Journal Article

An integrated approach to solving influence diagrams and finite-horizon partially observable decision processes

• Eric A. Hansen

We show how to integrate a variable elimination approach to solving influence diagrams with a value iteration approach to solving finite-horizon partially observable Markov decision processes (POMDPs). The integration of these approaches creates a variable elimination algorithm for influence diagrams that has much more relaxed constraints on elimination order, which allows improved scalability in many cases. The new algorithm can also be viewed as a generalization of the value iteration algorithm for POMDPs that solves non-Markovian as well as Markovian problems, in addition to leveraging a factored representation for improved efficiency. The development of a single algorithm that integrates and generalizes both of these classic algorithms, one for influence diagrams and the other for POMDPs, unifies these two approaches to solving Bayesian decision problems in a way that combines their complementary advantages.

UAI Conference 2020 Conference Paper

Improved Vector Pruning in Exact Algorithms for Solving POMDPs

• Eric A. Hansen
• Thomas Bowman

Exact dynamic programming algorithms for solving partially observable Markov decision processes (POMDPs) rely on a subroutine that removes, or “prunes, ” dominated vectors from vector sets that represent piecewise-linear and convex value functions. The subroutine solves many linear programs, where the size of the linear programs is proportional to both the number of undominated vectors in the set and their dimension, which severely limits scalability. Recent work improves the performance of this subroutine by limiting the number of constraints in the linear programs it solves by incrementally generating relevant constraints. In this paper, we show how to similarly limit the number of variables. By reducing the size of the linear programs in both ways, we further improve the performance of exact algorithms for POMDPs, especially in solving problems with larger state spaces.

IJCAI Conference 2016 Conference Paper

A POMDP Approach to Influence Diagram Evaluation

• Eric A. Hansen
• Jinchuan Shi
• Arindam Khaled

We propose a node-removal/arc-reversal algorithm for influence diagram evaluation that includes reductions that allow an influence diagram to be solved by a generalization of the dynamic programming approach to solving partially observable Markov decision processes (POMDPs). Among its potential advantages, the algorithm allows a more flexible ordering of node removals, and a POMDP-inspired approach to optimizing over hidden state variables, which can improve the scalability of influence diagram evaluation in solving complex, multi-stage problems. It also finds a more compact representation of an optimal strategy.

UAI Conference 2013 Conference Paper

Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search

• Arindam Khaled
• Eric A. Hansen
• Changhe Yuan

A limited-memory influence diagram (LIMID) generalizes a traditional influence diagram by relaxing the assumptions of regularity and noforgetting, allowing a wider range of decision problems to be modeled. Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this paper, we introduce an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently.

ICAPS Conference 2011 Conference Paper

Dynamic State-Space Partitioning in External-Memory Graph Search

• Rong Zhou 0001
• Eric A. Hansen

The scalability of optimal sequential planning can be improved by using external-memory graph search. State-of-the-art external-memory graph search algorithms rely on a state-space projection function, or hash function, that partitions the stored nodes of the state-space search graph into groups of nodes that are stored as separate files on disk. Search performance depends on properties of the partition; whether the number of unique nodes in a file always fits in RAM, the number of files into which the nodes of the state-space graph are partitioned, and how well the partition captures local structure in the graph. Previous work relies on a static partition of the state space, but it can be difficult for a static partition to simultaneously satisfy all of these criteria. We introduce a method for dynamic partitioning and show that it leads to improved search performance in solving STRIPS planning problems.

UAI Conference 2011 Conference Paper

Improving the Scalability of Optimal Bayesian Network Learning with External-Memory Frontier Breadth-First Branch and Bound Search

• Brandon M. Malone
• Changhe Yuan
• Eric A. Hansen
• Susan Bridges

UAI Conference 2011 Conference Paper

Suboptimality Bounds for Stochastic Shortest Path Problems

• Eric A. Hansen

SoCS Conference 2010 Conference Paper

Edge Partitioning in Parallel Structured Duplicate Detection

• Rong Zhou 0001
• Tim Schmidt
• Eric A. Hansen
• Minh Binh Do
• Serdar Uckun

We show how edge partitioning, a technique originally developed for external-memory search, can be used to reduce the number of slow synchronization operations needed in parallel graph search. We show that edge partitioning improves on a previous technique called parallel structured duplicate detection by allowing a higher degree of concurrency, even for search problems with little or no inherent locality. For domain-independent graph search, we also show that edge partitioning significantly improves search speed by improving the efficiency of precondition checking. We demonstrate the effectiveness of this approach to parallel graph search for domain-independent STRIPS planning.

UAI Conference 2010 Conference Paper

Solving Multistage Influence Diagrams using Branch-and-Bound Search

• Changhe Yuan
• Xiaojian Wu
• Eric A. Hansen

A branch-and-bound approach to solving influence diagrams has been previously proposed in the literature, but appears to have never been implemented and evaluated – apparently due to the difficulties of computing effective bounds for the branch-and-bound search. In this paper, we describe how to efficiently compute effective bounds, and we develop a practical implementation of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solving influence diagrams with multiple stages.

IJCAI Conference 2009 Conference Paper

• Changhe Yuan
• Eric A. Hansen

The MAP (maximum a posteriori assignment) problem in Bayesian networks is the problem of finding the most probable instantiation of a set of variables given partial evidence for the remaining variables. The state-of-the-art exact solution method is depth-first branch-and-bound search using dynamic variable ordering and a jointree upper bound proposed by Park and Darwiche [2003]. Since almost all search time is spent computing the jointree bounds, we introduce an efficient method for computing these bounds incrementally. We point out that, using a static variable ordering, it is only necessary to compute relevant upper bounds at each search step, and it is also possible to cache potentials of the jointree for efficient backtracking. Since the jointree computation typically produces bounds for joint configurations of groups of variables, our method also instantiates multiple variables at each search step, instead of a single variable, in order to reduce the number of times that upper bounds need to be computed. Experiments show that this approach leads to orders of magnitude reduction in search time.

IJCAI Conference 2009 Conference Paper

• Rong Zhou
• Eric A. Hansen

Breadth-first and depth-first search are basic search strategies upon which many other search algorithms are built. In this paper, we describe an approach to integrating these two strategies in a single algorithm that combines the complementary strengths of both. We show the benefits of this approach using the treewidth problem as an example.

UAI Conference 2008 Conference Paper

Sparse Stochastic Finite-State Controllers for POMDPs

• Eric A. Hansen

Bounded policy iteration is an approach to solving infinite-horizon POMDPs that represents policies as stochastic finite-state controllers and iteratively improves a controller by adjusting the parameters of each node using linear programming. In the original algorithm, the size of the linear programs, and thus the complexity of policy improvement, depends on the number of parameters of each node, which grows with the size of the controller. But in practice, the number of parameters of a node with non-zero values is often very small, and does not grow with the size of the controller. Based on this observation, we develop a version of bounded policy iteration that leverages the sparse structure of a stochastic finite-state controller. In each iteration, it improves a policy by the same amount as the original algorithm, but with much better scalability.

IJCAI Conference 2007 Conference Paper

• Rong Zhou
• Eric A. Hansen

There is currently much interest in using external memory, such as disk storage, to scale up graph-search algorithms. Recent work shows that the local structure of a graph can be leveraged to substantially improve the efficiency of external-memory graph search. This paper introduces a technique, called edge partitioning, which exploits a form of local structure that has not been considered in previous work. The new technique improves the scalability of structured approaches to external-memory graph search, and also guarantees the applicability of these approaches to any graph-search problem. We show its effectiveness in an external-memory graph-search algorithm for domain-independent STRIPS planning.

AAAI Conference 2007 Conference Paper

Indefinite-Horizon POMDPs with Action-Based Termination

• Eric A. Hansen

For decision-theoretic planning problems with an indefinite horizon, plan execution terminates after a finite number of steps with probability one, but the number of steps until termination (i. e. , the horizon) is uncertain and unbounded. In the traditional approach to modeling such problems, called a stochastic shortest-path problem, plan execution terminates when a particular state is reached, typically a goal state. We consider a model in which plan execution terminates when a stopping action is taken. We show that an action-based model of termination has several advantages for partially observable planning problems. It does not require a goal state to be fully observable; it does not require achievement of a goal state to be guaranteed; and it allows a proper policy to be found more easily. This framework allows many partially observable planning problems to be modeled in a more realistic way that does not require an artificial discount factor.

ICAPS Conference 2007 Conference Paper

Prioritizing Bellman Backups without a Priority Queue

• Peng Dai
• Eric A. Hansen

Several researchers have shown that the efficiency of value iteration, a dynamic programming algorithm for Markov decision processes, can be improved by prioritizing the order of Bellman backups to focus computation on states where the value function can be improved the most. In previous work, a priority queue has been used to order backups. Although this incurs overhead for maintaining the priority queue, previous work has argued that the overhead is usually much less than the benefit from prioritization. However this conclusion is usually based on a comparison to a non-prioritized approach that performs Bellman backups on states in an arbitrary order. In this paper, we show that the overhead for maintaining the priority queue can be greater than the benefit, when it is compared to very simple heuristics for prioritizing backups that do not require a priority queue. Although the order of backups induced by our simple approach is often sub-optimal, we show that its smaller overhead allows it to converge faster than other state-of-the-art priority-based solvers.

AIJ Journal 2006 Journal Article

Breadth-first heuristic search

• Rong Zhou
• Eric A. Hansen

Recent work shows that the memory requirements of A* and related graph-search algorithms can be reduced substantially by only storing nodes that are on or near the search frontier, using special techniques to prevent node regeneration, and recovering the solution path by a divide-and-conquer technique. When this approach is used to solve graph-search problems with unit edge costs, we show that a breadth-first search strategy can be more memory-efficient than a best-first strategy. We also show that a breadth-first strategy allows a technique for preventing node regeneration that is easier to implement and can be applied more widely. The breadth-first heuristic search algorithms introduced in this paper include a memory-efficient implementation of breadth-first branch-and-bound search and a breadth-first iterative-deepening A* algorithm that is based on it. Computational results show that they outperform other systematic search algorithms in solving a range of challenging graph-search problems.

ICAPS Conference 2006 Conference Paper

Memory-Efficient Symbolic Heuristic Search

• Rune Møller Jensen
• Eric A. Hansen
• Simon Richards
• Rong Zhou 0001

A promising approach to solving large state-space search problems is to integrate heuristic search with symbolic search. Recent work shows that a symbolic A* search algorithm that uses binary decision diagrams to compactly represent sets of states outperforms traditional A* in many domains. Since the memory requirements of A* limit its scalability, we show how to integrate symbolic search with a memory-efficient strategy for heuristic search. We analyze the resulting search algorithm, consider the factors that affect its behavior, and evaluate its performance in solving benchmark problems that include STRIPS planning problems.

ICAPS Conference 2005 Conference Paper

Beam-Stack Search: Integrating Backtracking with Beam Search

• Rong Zhou 0001
• Eric A. Hansen

We describe a method for transforming beam search into a complete search algorithm that is guaranteed to find an optimal solution. Called beam-stack search, the algorithm uses a new data structure, called a beam stack, that makes it possible to integrate systematic backtracking with beam search. The resulting search algorithm is an anytime algorithm that finds a good, sub-optimal solution quickly, like beam search, and then backtracks and continues to find improved solutions until convergence to an optimal solution. We describe a memory-efficient implementation of beam-stack search, called divide-and-conquer beam-stack search, as well as an iterative-deepening version of the algorithm. The approach is applied to domain-independent STRIPS planning, and computational results show its advantages.

IJCAI Conference 2005 Conference Paper

Bounded Policy Iteration for Decentralized POMDPs

• Daniel S. Bernstein
• Eric A. Hansen
• Shlomo

We present a bounded policy iteration algorithm for infinite-horizon decentralized POMDPs. Policies are represented as joint stochastic finite-state controllers, which consist of a local controller for each agent. We also let a joint controller include a correlation device that allows the agents to correlate their behavior without exchanging information during execution, and show that this leads to improved performance. The algorithm uses a fixed amount of memory, and each iteration is guaranteed to produce a controller with value at least as high as the previous one for all possible initial state distributions. For the case of a single agent, the algorithm reduces to Poupart and Boutilier’s bounded policy iteration for POMDPs.

ICAPS Conference 2004 Conference Paper

Breadth-First Heuristic Search

• Rong Zhou 0001
• Eric A. Hansen

Recent work shows that the memory requirements of best- first heuristic search can be reduced substantially by using a divide-and-conquer method of solution reconstruction. We show that memory requirements can be reduced even further by using a breadth-first instead of a best-first search strategy. We describe optimal and approximate breadth-first heuristic search algorithms that use divide-and-conquer solution reconstruction. Computational results show that they outperform other optimal and approximate heuristic search algorithms in solving domain-independent planning problems.

AAAI Conference 2004 Conference Paper

Dynamic Programming for Partially Observable Stochastic Games

• Eric A. Hansen

We develop an exact dynamic programming algorithm for partially observable stochastic games (POSGs). The algorithm is a synthesis of dynamic programming for partially observable Markov decision processes (POMDPs) and iterated elimination of dominated strategies in normal form games. We prove that when applied to finite-horizon POSGs, the algorithm iteratively eliminates very weakly dominated strategies without first forming a normal form representation of the game. For the special case in which agents share the same payoffs, the algorithm can be used to find an optimal solution. We present preliminary empirical results and discuss ways to further exploit POMDP theory in solving POSGs.

AAAI Conference 2004 Conference Paper

Space-Efficient Memory-Based Heuristics

• Rong Zhou
• Eric A. Hansen

A memory-based heuristic is a heuristic function that is stored in a lookup table. Very accurate heuristics have been created by building very large lookup tables, sometimes called pattern databases. Most previous work assumes that a memorybased heuristic is computed for the entire state space, and the cost of computing it is amortized over many problem instances. But in some cases, it may be useful to compute a memory-based heuristic for a single problem instance. If the start and goal states of the problem instance are used to restrict the region of the state space for which the heuristic is needed, the time and space used to compute the heuristic may be substantially reduced. In this paper, we review recent work that uses this idea to compute space-efficient heuristics for the multiple sequence alignment problem. We then describe a novel development of this idea that is simpler and more general. Our approach leads to improved performance in solving the multiple sequence alignment problem, and is general enough to apply to other domains.

AAAI Conference 2004 Conference Paper

Structured Duplicate Detection in External-Memory Graph Search

• Rong Zhou
• Eric A. Hansen

We consider how to use external memory, such as disk storage, to improve the scalability of heuristic search in statespace graphs. To limit the number of slow disk I/O operations, we develop a new approach to duplicate detection in graph search that localizes memory references by partitioning the search graph based on an abstraction of the state space, and expanding the frontier nodes of the graph in an order that respects this partition. We demonstrate the effectiveness of this approach both analytically and empirically.

IJCAI Conference 2003 Conference Paper

Sparse-Memory Graph Search

• Rong Zhou
• Eric A. Hansen

We describe a framework for reducing the space complexity of graph search algorithms such as A* that use Open and Closed lists to keep track of the frontier and interior nodes of the search space. We propose a sparse representation of the Closed list in which only a fraction of already expanded nodes need to be stored to perform the two functions of the Closed List - preventing duplicate search effort and allowing solution extraction. Our proposal is related to earlier work on search algorithms that do not use a Closed list at all [Korf and Zhang, 2000]. However, the approach we describe has several advantages that make it effective for a wider variety of problems.

UAI Conference 2003 Conference Paper

Symbolic Generalization for On-line Planning

• Zhengzhu Feng
• Eric A. Hansen
• Shlomo Zilberstein

Symbolic representations have been used successfully in off-line planning algorithms for Markov decision processes. We show that they can also improve the performance of on-line planners. In addition to reducing computation time, symbolic generalization can reduce the amount of costly real-world interactions required for convergence. We introduce Symbolic Real-Time Dynamic Programming (or sRTDP), an extension of RTDP. After each step of on-line interaction with an environment, sRTDP uses symbolic model-checking techniques to generalizes its experience by updating a group of states rather than a single state. We examine two heuristic approaches to dynamic grouping of states and show that they accelerate the planning process significantly in terms of both CPU time and the number of steps of interaction with the environment.

ICAPS Conference 2003 Conference Paper

Synthesis of Hierarchical Finite-State Controllers for POMDPs

• Eric A. Hansen
• Rong Zhou 0001

We develop a hierarchical approach to planning for partially observable Markov decision processes (POMDPs) in which a policy is represented as a hierarchical finite-state controller. To provide a foundation for this approach, we discuss some extensions of the POMDP framework that allow us to formalize the process of abstraction by which a hierarchical controller is constructed. We describe a planning algorithm that uses a programmer-defined task hierarchy to constrain the search space of finite-state controllers, and prove that this algorithm converges to a hierarchical finite-state controller that is "-optimal in a limited but well-defined sense, related to the concept of recursive optimality.

AIJ Journal 2001 Journal Article

LAO∗: A heuristic search algorithm that finds solutions with loops

• Eric A. Hansen
• Shlomo Zilberstein

Classic heuristic search algorithms can find solutions that take the form of a simple path (A∗), a tree, or an acyclic graph (AO∗). In this paper, we describe a novel generalization of heuristic search, called LAO∗, that can find solutions with loops. We show that LAO∗ can be used to solve Markov decision problems and that it shares the advantage heuristic search has over dynamic programming for other classes of problems. Given a start state, it can find an optimal solution without evaluating the entire state space.

AIJ Journal 2001 Journal Article

Monitoring and control of anytime algorithms: A dynamic programming approach

• Eric A. Hansen
• Shlomo Zilberstein

Anytime algorithms offer a tradeoff between solution quality and computation time that has proved useful in solving time-critical problems such as planning and scheduling, belief network evaluation, and information gathering. To exploit this tradeoff, a system must be able to decide when to stop deliberation and act on the currently available solution. This paper analyzes the characteristics of existing techniques for meta-level control of anytime algorithms and develops a new framework for monitoring and control. The new framework handles effectively the uncertainty associated with the algorithm's performance profile, the uncertainty associated with the domain of operation, and the cost of monitoring progress. The result is an efficient non-myopic solution to the meta-level control problem for anytime algorithms.

ICAPS Conference 2000 Conference Paper

Dynamic Programming for POMDPs Using a Factored State Representation

• Eric A. Hansen
• Zhengzhu Feng

Contingent planning -- constructing a plan in which action seh, ction is contingent on imperfect infornlation received during plan execution - can be forma]ized ~s the problemof solving a partially observabh, Markov decision process (POMDP). Traditional dynamic programmiug algorittmm for POMDPsuse a flat state representation that enunmrat(. sall possible states au, l staCe tr~msitions. By contrast, AI plmming algorithms use a fiwt. ored state rcpres(. ntation that supports state abstraction and allows prolfloms with large state spaces to be represented and solved nmre efficiently. Boutilier ~mdPeele (1996) have recently described howa factored state rcpresent. ation c~ut be exploited by a dynamic programmingalgorithm for POMDPs. We. extend their framework, describe an implementationof it, test its performance, and assess how mucl~ this approach improves the computational effk: iency of dynaanic l)rogrammingfi, r POMDPs.

AAAI Conference 1998 Conference Paper

Heuristic Search in Cyclic AND / OR Graphs

• Eric A. Hansen

Heuristic search algorithms can find solutions that take the form of a simple path (A*), a tree or acyclic graph(AO*). Wepresent a novel generalization of heuristic search (called LAO*) that can find solutions withloops, that is, solutions that take the formof a cyclic graph. Weshowthat it can be used to solve Markov decision problemswithout evaluating the entire state space, givingit an advantage over dynamic-programming algorithms such as policy iteration andvalueiteration as an approachto stochastic planning.

UAI Conference 1998 Conference Paper

Solving POMDPs by Searching in Policy Space

• Eric A. Hansen

Most algorithms for solving POMDPs iteratively improve a value function that implicitly represents a policy and are said to search in value function space. This paper presents an approach to solving POMDPs that represents a policy explicitly as a finite-state controller and iteratively improves the controller by search in policy space. Two related algorithms illustrate this approach. The first is a policy iteration algorithm that can outperform value iteration in solving infinitehorizon POMDPs. It provides the foundation for a new heuristic search algorithm that promises further speedup by focusing computational effort on regions of the problem space that are reachable, or likely to be reached, from a start state.

AAAI Conference 1996 Conference Paper

Monitoring the Progress of Anytime Problem-Solving

• Eric A. Hansen

Anytime algorithms offer a tradeoff between solution quality and computation time that has proved useful in applying artificial intelligence techniques to time-critical problems. To exploit this tradeoff, a system must be able to determine the best time to stop deliberation and act on the currently available solution. When the rate of improvement of solution quality is uncertain, monitoring the progress of the algorithm can improve the utility of the system. This paper introduces a technique for run-time monitoring of anytime algorithms that is sensitive to the variance of the algorithm’ s performance, the time-dependent utility of a solution, the ability of the run-time monitor to estimate the quality of the currently available solution, and the cost of monitoring. The paper examines the conditions under which the technique is optimal and demonstrates its applicability.

AAAI Conference 1994 Conference Paper

Cost-Effective Sensing during Plan Execution

• Eric A. Hansen

Between sensing the world after every action (as in a reactive plan) and not sensing at all (as in an openloop plan), lies a continuum of strategies for sensing during plan execution. If sensing incurs a cost (in time or resources), the most cost-effective strategy is likely to fall somewhere between these two extremes. Yet most work on plan execution assumes one or the other. In this paper, an efficient, anytime planner is described that controls the rate of sensing during plan execution. The sensing interval is determined by the state during plan execution, as well as by the cost of sensing, so that an agent can sense more often when necessary. The planner is based on a generalization of stochastic dynamic programming.