Dana S. Nau

AAAI Conference 2026 Conference Paper

Probabilistic Hierarchical Goal Network Planning with UCT

• David H. Chan
• Mark Roberts
• Dana S. Nau

Hierarchical goal networks (HGNs) provide a framework for goal-directed planning by decomposing high-level goals into ordered subgoals. While prior work has examined non-determinism for hierarchical planning (specifically, HTNs), scant work studies how HGNs can help in stochastic settings. We introduce a formalism for probabilistic HGN planning with action-insertion semantics, enabling probabilistic planners to incorporate domain knowledge from goal decomposition methods. We design and evaluate two UCT-based algorithms for solving probabilistic HGN planning problems: an asymptotically optimal approach and a compressed, shared-value approach that optimizes separately for each goal within the goal-subgoal hierarchy. We compare our two UCT-based HGN search algorithms experimentally on modified benchmark domains from the FOND HTN literature. Our results demonstrate that on larger problems, the compressed search converges more quickly and outperforms the asymptotically optimal search. This suggests that HGNs can be effective in probabilistic planning, and compression may yield better performance on large problems in anytime settings with stochastic action outcomes.

AAMAS Conference 2025 Conference Paper

Automating Curriculum Learning for Reinforcement Learning using a Skill-Based Bayesian Network

• Vincent Hsiao
• Mark Roberts
• Laura M. Hiatt
• George Konidaris
• Dana S. Nau

A major challenge for reinforcement learning is automatically generating curricula to reduce training time or improve performance in some target task. We introduce SEBNs (Skill-Environment Bayesian Networks) which model a probabilistic relationship between a set of skills, a set of goals that relate to the reward structure, and a set of environment features to predict policy performance on (possibly unseen) tasks. We develop an algorithm that uses the inferred estimates of agent success from an SEBN to weigh the possible next tasks by expected improvement. We evaluate the benefit of the resulting curriculum on three environments: a discrete gridworld, continuous control, and simulated robotics. The results show that SEBN-based curricula frequently outperform other baselines.

ECAI Conference 2025 Conference Paper

Landmark-Assisted Monte Carlo Planning

• David H. Chan
• Mark Roberts
• Dana S. Nau

Landmarks—conditions that must be satisfied at some point in every solution plan—have contributed to major advancements in classical planning, but they have seldom been used in stochastic domains. We formalize probabilistic landmarks and adapt the UCT algorithm to leverage them as subgoals to decompose MDPs; core to the adaptation is balancing between greedy landmark achievement and final goal achievement. Our results in benchmark domains show that well-chosen landmarks can significantly improve the performance of UCT in online probabilistic planning, while the best balance of greedy versus long-term goal achievement is problem-dependent. The results suggest that landmarks can provide helpful guidance for anytime algorithms solving MDPs.

ICAPS Conference 2021 Conference Paper

Decentralized Refinement Planning and Acting

• Ruoxi Li
• Sunandita Patra
• Dana S. Nau

We describe Dec-RPAE, a system for decentralized multi-agent acting and planning in partially observable and non-deterministic environments. The system includes both an acting component and an online planning component. The acting component is similar to RAE, a well-known acting engine, but incorporates changes that enable it to be used by multiple autonomous agents working independently in a collaborative setting. Each agent runs a local copy of Dec-RPAE, with a set of hierarchical refinement methods using operational models that specify various ways to accomplish its designated tasks. To perform actions, the agent uses Dec-RPAE’s acting component to execute the methods in the agent’s environment. To advise the acting component on which method to execute, the planning component repeatedly does Monte Carlo simulations of the methods to estimate their potential outcomes. Agents can communicate with each other to exchange information about their states, tasks, goals, and plans in order to cooperatively succeed in their respective missions. Our experimental results demonstrate that Dec-RPAE is useful for improving the agents’ performances.

ICAPS Conference 2020 Conference Paper

Integrating Acting, Planning, and Learning in Hierarchical Operational Models

• Sunandita Patra
• James Mason
• Amit Kumar 0013
• Malik Ghallab
• Paolo Traverso
• Dana S. Nau

We present new planning and learning algorithms for RAE, the Refinement Acting Engine (Ghallab, Nau, and Traverso 2016). RAE uses hierarchical operational models to perform tasks in dynamically changing environments. Our planning procedure, UPOM, does a UCT-like search in the space of operational models in order to find a near optimal method to use for the task and context at hand. Our learning strategies acquire, from online acting experiences and/or simulated planning results, a mapping from decision contexts to method instances as well as a heuristic function to guide UPOM. Our experimental results show that UPOM and our learning strategies significantly improve RAE's performance in four test domains using two different metrics: efficiency and success ratio.

JAIR Journal 2018 Journal Article

Extending Classical Planning with State Constraints: Heuristics and Search for Optimal Planning

• Patrik Haslum
• Franc Ivankovic
• Miquel Ramirez
• Dan Gordon
• Sylvie Thiebaux
• Vikas Shivashankar
• Dana S. Nau

We present a principled way of extending a classical AI planning formalism with systems of state constraints, which relate - sometimes determine - the values of variables in each state traversed by the plan. This extension occupies an attractive middle ground between expressivity and complexity. It enables modelling a new range of problems, as well as formulating more efficient models of classical planning problems. An example of the former is planning-based control of networked physical systems - power networks, for example - in which a local, discrete control action can have global effects on continuous quantities, such as altering flows across the entire network. At the same time, our extension remains decidable as long as the satisfiability of sets of state constraints is decidable, including in the presence of numeric state variables, and we demonstrate that effective techniques for cost-optimal planning known in the classical setting - in particular, relaxation-based admissible heuristics - can be adapted to the extended formalism. In this paper, we apply our approach to constraints in the form of linear or non-linear equations over numeric state variables, but the approach is independent of the type of state constraints, as long as there exists a procedure that decides their consistency. The planner and the constraint solver interact through a well-defined, narrow interface, in which the solver requires no specialisation to the planning context.

AAMAS Conference 2017 Conference Paper

Understanding Norm Change: An Evolutionary Game-Theoretic Approach

• Soham De
• Dana S. Nau
• Michele J. Gelfand

Human societies around the world interact with each other by developing and maintaining social norms, and it is critically important to understand how such norms emerge and change. In this work, we define an evolutionary gametheoretic model to study how norms change in a society, based on the idea that different strength of norms in societies translate to different game-theoretic interaction structures and incentives. We use this model to study, both analytically and with extensive agent-based simulations, the evolutionary relationships of the need for coordination in a society (which is related to its norm strength) with two key aspects of norm change: cultural inertia (whether or how quickly the population responds when faced with conditions that make a norm change desirable), and exploration rate (the willingness of agents to try out new strategies). Our results show that a high need for coordination leads to both high cultural inertia and a low exploration rate, while a low need for coordination leads to low cultural inertia and high exploration rate. This is the first work, to our knowledge, on understanding the evolutionary causal relationships among these factors.

ICAPS Conference 2014 Conference Paper

On the Feasibility of Planning Graph Style Heuristics for HTN Planning

• Ron Alford
• Vikas Shivashankar
• Ugur Kuter
• Dana S. Nau

In classical planning, the polynomial-time computability of propositional delete-free planning (planning with only positive effects and preconditions) led to the highly successful Relaxed Graphplan heuristic. We present a hierarchy of new computational complexity results for different classes of propositional delete-free HTN planning, with two main results: We prove that finding a plan for the delete-relaxation of a propositional HTN problem is NP-complete: hence unless P=NP, there is no directly analogous GraphPlan heuristic for HTN planning. However, a further relaxation of HTN planning (delete-free HTN planning with task insertion) is polynomial-time computable. Thus, there may be a possibility of using this or other relaxations to develop search heuristics for HTN planning.

ICAPS Conference 2014 Conference Paper

Optimal Planning with Global Numerical State Constraints

• Franc Ivankovic
• Patrik Haslum
• Sylvie Thiébaux
• Vikas Shivashankar
• Dana S. Nau

Automating the operations of infrastructure networks such as energy grids and oil pipelines requires a range of planning and optimisation technologies. However, current planners face significant challenges in responding to this need. Notably, they are unable to model and reason about the global numerical state constraints necessary to capture flows and similar physical phenomena occurring in these networks. A single discrete control action can affect the flow throughout the network in a way that may depend on the entire network topology. Determining whether preconditions, goals and invariant conditions are satisfied requires solving a system of numerical constraints after each action application. This paper extends domain-independent optimal planning to this kind of reasoning. We present extensions of the formalism, relaxed plans, and heuristics, as well as new search variants and experimental results on two problem domains.

ECAI Conference 2014 Conference Paper

Predicting Agents' Behavior by Measuring their Social Preferences

• Kan-Leung Cheng
• Inon Zuckerman
• Dana S. Nau
• Jennifer Golbeck

There are many situations in which two or more agents (e. g. , human or computer decision makers) interact with each other repeatedly in settings that can be modeled as repeated stochastic games. In such situations, each agent's performance may depend greatly on how well it can predict the other agents' preferences and behavior. For use in making such predictions, we adapt and extend the Social Value Orientation (SVO) model from social psychology, which provides a way to measure an agent's preferences for both its own payoffs and those of the other agents.

ICRA Conference 2013 Conference Paper

Model-predictive target defense by team of unmanned surface vehicles operating in uncertain environments

• Eric Raboin
• Petr Svec
• Dana S. Nau
• Satyandra K. Gupta

In this paper, we present a heuristic planning approach for guarding a valuable asset by a team of autonomous unmanned surface vehicles (USVs) operating in a continuous state-action space. The team's objective is to maximize the amount of time it takes an intruder boat to reach the asset. The team must cooperatively deal with uncertainty about which boats are actual intruders, employ active blocking to slow down intruders' movement towards the asset, and intelligently distribute themselves around the target to optimize future guarding opportunities. Our planner incorporates a market-based algorithm for allocating tasks to individual USVs by forward-simulating the mission and assigning estimated utilities to candidate task-allocation plans. The planner can be automatically adapted to a specific mission by optimizing the behaviors used to fulfil individual tasks. We present detailed simulation results that demonstrate the effectiveness of our approach.

SoCS Conference 2012 Conference Paper

HTN Problem Spaces: Structure, Algorithms, Termination

• Ron Alford
• Vikas Shivashankar
• Ugur Kuter
• Dana S. Nau

For HTN planning, we formally characterize and classify four kinds of problem spaces in which each node represents a planning problem or subproblem. Two of the problem spaces are searched by current HTN planning algorithms; the other two problem spaces are new. This enables us to provide: Sufficient (and in one case, necessary) conditions for finiteness of each kind of problem space. The conditions can be evaluated up-front to see if an HTN planning problem is finite. Loop-detection tests that can be used in HTN planners to ensure termination when the problem space is finite. A way to compute the correct value for an upper-bound parameter in an HTN-to-PDDL translation algorithm published in IJCAI-2009. Planning algorithms that utilize the two new problem spaces to guarantee termination on broader classes of planning problems than previous HTN planning algorithms.

ECAI Conference 2012 Conference Paper

Improving Local Decisions in Adversarial Search

• Brandon Wilson
• Inon Zuckerman
• Austin Parker
• Dana S. Nau

Until recently, game-tree pathology (in which a deeper game-tree search results in worse play) has been thought to be quite rare. We provide an analysis that shows that every game should have some sections that are locally pathological, assuming that both players can potentially win the game.

TIST Journal 2010 Journal Article

Evolution of state-dependent risk preferences

• Patrick Roos
• J. Ryan Carr
• Dana S. Nau

Researchers have invested much effort in constructing models of the state-dependent (sometimes risk-averse and sometimes risk-prone) nature of human decision making. An important open question is how state-dependent risk behavior can arise and remain prominent in populations. We believe that one part of the answer is the interplay between risk-taking and sequentiality of choices in populations subject to evolutionary population dynamics. To support this hypothesis, we provide simulation and analytical results for evolutionary lottery games, including results on evolutionary stability. We consider a parameterized class of imitation dynamics in which the parameter 0 ≤ α ≤ 1 yields the replicator dynamic with α = 1 and the imitate-the-better dynamic with α = 0. Our results demonstrate that for every population dynamic in this class except for the replicator dynamic, the interplay between risk-taking and sequentiality of choices allows state-dependent risk behavior to have an evolutionary advantage over expected-value maximization.

AIJ Journal 2010 Journal Article

When is it better not to look ahead?

• Dana S. Nau
• Mitja Luštrek
• Austin Parker
• Ivan Bratko
• Matjaž Gams

In situations where one needs to make a sequence of decisions, it is often believed that looking ahead will help produce better decisions. However, it was shown 30 years ago that there are “pathological” situations in which looking ahead is counterproductive. Two long-standing open questions are (a) what combinations of factors have the biggest influence on whether lookahead pathology occurs, and (b) whether it occurs in real-world decision-making. This paper includes simulation results for several synthetic game-tree models, and experimental results for three well-known board games: two chess endgames, kalah (with some modifications to facilitate experimentation), and the 8-puzzle. The simulations show the interplay between lookahead pathology and several factors that affect it; and the experiments confirm the trends predicted by the simulation models. The experiments also show that lookahead pathology is more common than has been thought: all three games contain situations where it occurs.

ICAPS Conference 2009 Conference Paper

Thinking Ahead in Real-Time Search

• Dana S. Nau
• Ugur Kuter
• Emre Sefer

We consider real-time planning problems in which some states are unsolvable, i. e. , have no path to a goal. Such problems are difficult for real-time planning algorithms such as RTA* in which all states must be solvable. We identify a property called k-safeness, in which the consequences of a bad choice become apparent within k moves after the choice is made. When k is not too large, this makes it possible to identify unsolvable states in real time. We provide a modified version of RTA* that is provably complete on all k-safe problems. We derive k-safeness conditions for real-time deterministic versions of the well-known Tireworld and Racetrack domains, and provide experimental results showing that our modified version of RTA* works quite well in these domains.

ECAI Conference 2008 Conference Paper

Combining Domain-Independent Planning and HTN Planning: The Duet Planner

• Alfonso Emilio Gerevini
• Ugur Kuter
• Dana S. Nau
• Alessandro Saetti
• Nathaniel Waisbrot

Despite the recent advances in planning for classical domains, the question of how to use domain knowledge in planning is yet to be completely and clearly answered. Some of the existing planners use domain-independent search heuristics, and some others depend on intensively-engineered domain-specific knowledge to guide the planning process. In this paper, we describe an approach to combine ideas from both of the above schools of thought. We present Duet, our planning system that incorporates the ability of using hierarchical domain knowledge in the form of Hierarchical Task Networks (HTNs) as in SHOP2 [14] and using domain-independent local search techniques as in LPG [8]. In our experiments, Duet was able to solve much larger problems than LPG could solve, with only minimal domain knowledge encoded in HTNs (much less domain knowledge than SHOP2 needed to solve those problems by itself).

ICAPS Conference 2008 Conference Paper

Using Classical Planners to Solve Nondeterministic Planning Problems

• Ugur Kuter
• Dana S. Nau
• Elnatan Reisner
• Robert P. Goldman

Researchers have developed a huge number of algorithms to solve classical planning problems. We provide a way to use these algorithms, unmodified, to generate strong-cyclic solutions in fully-observable nondeterministic planning domains. Our experiments show that when using our technique with FF and SGPlan (two well-known classical planners), its performance compares quite favorably to that of MBP, one of the best-known planners for nondeterministic planning problems.

ICAPS Conference 2006 Conference Paper

Learning to Do HTN Planning

• Okhtay Ilghami
• Dana S. Nau
• Héctor Muñoz-Avila

We describe HDL, an algorithm that learns HTN domain descriptions by examining plan traces produced by an expert problem-solver. Prior work on learning HTN methods requires that all the methods' information except for their preconditions be given in advance so that the learner can learn the preconditions. In contrast, HDL has no prior information about the methods. In our experiments, in most cases HDL converged fully with no more than about 200 plan traces. Furthermore, even when HDL was given only half the plan traces it required to fully converge, it usually was able to produce HTN methods that were sufficient to solve more than 3/4 of the planning problems in the test set.

ECAI Conference 2006 Conference Paper

The Incompleteness of Planning with Volatile External Information

• Tsz-Chiu Au
• Dana S. Nau

In many real-world planning environments, some of the information about the world is both external (the planner must request it from external information sources) and volatile (it changes before the planning process completes). In such environments, a planner faces two challenges: how to generate plans despite changes in the external information during planning, and how to guarantee that a plan returned by the planner will remain valid for some period of time after the planning ends. Previous works on planning with volatile information have addressed the first challenge, but not the second one. This paper provides a general model for planning with volatile external information in which the planner offers a guarantee of how long the solution will remain valid after it is returned, and an incompleteness theorem showing that there is no planner that can succeed in solving all solvable planning problems in which there is volatile external information.

ICAPS Conference 2005 Conference Paper

A Hierarchical Task-Network Planner based on Symbolic Model Checking

• Ugur Kuter
• Dana S. Nau
• Marco Pistore
• Paolo Traverso

Although several approaches have been developed for planning in nondeterministic domains, solving large planning problems is still quite difficult. In this work, we present a novel algorithm, called YoYo, for planning in nondeterministic domains under the assumption of full observability. This algorithm enables us to combine the power of search-control strategies as in Planning with Hierarchical Task Networks (HTNs) with techniques from the Planning via Symbolic Model-Checking (SMC). Our experimental evaluation confirms the potentialities of our approach, demonstrating that it combines the advantages of these paradigms.

ICML Conference 2005 Conference Paper

Learning approximate preconditions for methods in hierarchical plans

• Okhtay Ilghami
• Héctor Muñoz-Avila
• Dana S. Nau
• David W. Aha

ECAI Conference 2004 Conference Paper

Utilizing Volatile External Information During Planning

• Tsz-Chiu Au
• Dana S. Nau
• V. S. Subrahmanian

ICAPS Conference 2002 Conference Paper

CaMeL: Learning Method Preconditions for HTN Planning

• Okhtay Ilghami
• Dana S. Nau
• Héctor Muñoz-Avila
• David W. Aha

A great challenge in using any planning system to solve real-world problems is the difficulty of acquiring the domain knowledge that the system will need. We present a way to address part of this problem, in the context of Hierarchical Task Network (HTN) planning, by having the planning system incrementally learn conditions for HTN methods under expert supervision. We present a general formal framework for learning HTN methods, and a supervised learning algorithm, named CaMeL, based on this formalism. We present theoretical results about CaMeL’s soundness, completeness, and convergence properties. We also report experimental results about its speed of convergence under different conditions. The experimental results suggest that CaMeL has the potential to be useful in real-world applications.

JELIA Conference 2002 Conference Paper

Theoretical and Empirical Aspects of a Planner in a Multi-agent Environment

• Jürgen Dix
• Héctor Muñoz-Avila
• Dana S. Nau
• Lingling Zhang

Abstract We give the theoretical foundations and empirical evaluation of a planning agent, ashop, performing HTN planning in a multi-agent environment. ashop is based on ASHOP, an agentised version of the original SHOP HTN planning algorithm, and is integrated in the IMPACT multi-agent environment. We ran several experiments involving accessing various distributed, heterogeneous information sources, based on simplified versions of noncombatant evacuation operations, NEO’s. As a result, we noticed that in such realistic settings the time spent on communication (including network time) is orders of magnitude higher than the actual inference process. This has important consequences for optimisations of such planners. Our main results are: (1) using NEO’s as new, more realistic benchmarks for planners acting in an agent environment, and (2) a memoization mechanism implemented on top of shop, which improves the overall performance considerably.

ICAPS Conference 2000 Conference Paper

New Advances in GraphHTN: Identifying Independent Subproblems in Large HTN Domains

• Amnon Lotem
• Dana S. Nau

We describe in this paper a new method for extracting knowledge on Hierarchical Task-Network (HTN) planning problems for speeding up the search. This knowledge is gathered by propagating properties through an AND/OR tree that represents disjunctively all possible decompositions of an HTN planning problem. We show how to use this knowledge during the search process of our GraphHTN planner, to split the current refined planning problem into independent subproblems. We also present new experimental results comparing GraphHTN with ordinary HTN decomposition (as implemented in the UMCP planner). The comparison is performed on a set of problems from the UM Translog domain - a large HTN transportation domain that is considerably more complicated than the well known “logistics” domain. Finally, so that we could compare GraphHTN with actionbased planners such as IPP and Blackbox, we translated the UM Translog domain into a STRIPS-style representation. We found that GraphHTN performed considerably better on UM Translog than IPP and Blackbox.

AAAI Conference 1999 Conference Paper

Using Planning Graphs for Solving HTN Planning Problems

• Amnon Lotem
• Dana S. Nau
• James A. Hendler
• University of Maryland

In this paper we present the GraphHTN algorithm, a hybrid planning algorithm that does Hierarchical Task-Network (HTN) planning using a combination of HTN-style problem reduction and Graphplan-style planning-graph generation. We also present experimental results comparing GraphHTN with ordinary HTN decomposition (as implemented in the UMCP planner) and ordinary Graphplan search (as implemented in the IPP planner). Our experimental results show that (1) the performance of HTN planning can be improved significantly by using planning graphs, and (2) that planning with planning graphs can be sped up by exploiting HTN control knowledge.

AIJ Journal 1996 Journal Article

On the nature and role of modal truth criteria in planning

• Subbarao Kambhampati
• Dana S. Nau

Chapman's paper, “Planning for conjunctive goals”, has been widely acknowledged for its contribution toward understanding the nature of partial-order planning, and it has been one of the bases of later work by others—but it is not free of problems. This paper addresses some problems involving modal truth and the modal truth criterion (MTC). Our results are as follows: (i) Even though modal duality is a fundamental property of classical modal logics, it does not hold for modal truth in Chapman's plans; i. e. , “necessarily p” is not equivalent to “not possibly -p”. (ii) Although the MTC for necessary truth is correct, the MTC for possible truth is incorrect: it provides necessary but insufficient conditions for ensuring possible truth. Furthermore, even though necessary truth can be determined in polynomial time, possible truth is NP-hard. (iii) If we rewrite the MTC to talk about modal conditional truth (i. e. , modal truth conditional on executability) rather than modal truth, then both the MTC for necessary conditional truth and the MTC for possible conditional truth are correct; and both can be computed in polynomial time. (iv) The MTC plays a different role in plan generation than it does in checking the correctness of plans, and this has led to several misconceptions about the MTC. Several researchers have mistakenly attempted to simplify the MTC by eliminating the white-knight declobbering clause from it; and others have used Chapman's results to conjecture that partial-order planning will not scale up to more expressive action representations. We point out that these ideas are misconceptions, and explain why.

AIJ Journal 1995 Journal Article

Complexity, decidability and undecidability results for domain-independent planning

• Kutluhan Erol
• Dana S. Nau
• V.S. Subrahmanian

In this paper, we examine how the complexity of domain-independent planning with STRIPS-style operators depends on the nature of the planning operators. We show conditions under which planning is decidable and undecidable. Our results on this topic solve an open problem posed by Chapman (1987), and clear up some difficulties with his undecidability theorems. For those cases where planning is decidable, we explain how the time complexity varies depending on a wide variety of conditions: • • whether or not function symbols are allowed; • • whether or not delete lists are allowed; • • whether or not negative preconditions are allowed; • • whether or not the predicates are restricted to be propositional (i. e. , 0-ary); • • whether the planning operators are given as part of the input to the planning problem, or instead are fixed in advance. • • whether or not the operators can have conditional effects.

ICAPS Conference 1994 Conference Paper

UMCP: A Sound and Complete Procedure for Hierarchical Task-network Planning

• Kutluhan Erol
• James A. Hendler
• Dana S. Nau

One big obstacle to understanding the nature of hierarchical task network(HTN)planning has been the lack of a dear theoretical framework. In particular, no one has yet presented a clear and concise HTNalgorithm that is sound and complete. In this paper, we present a formal syntax and semantics for HTNplanning. Based on this syntax and semantics, we are able to define an algo~thm for HTNplanning and prove it sound m~dcomplete.

AIJ Journal 1992 Journal Article

On the complexity of blocks-world planning

• Naresh Gupta
• Dana S. Nau

In this paper, we show that in the best-known version of the blocks world (and several related versions), planning is difficult, in the sense that finding an optimal plan is NP-hard. However, the NP-hardness is not due to deleted-condition interactions, but instead due to a situation which we call a deadlock. For problems that do not contain deadlocks, there is a simple hill-climbing strategy that can easily find an optimal plan, regardless of whether or not the problem contains any deleted-condition interactions. The above result is rather surprising, since one of the primary roles of the blocks world in the planning literature has been to provide examples of deleted-condition interactions such as creative destruction and Sussman's anomaly. However, we can explain why deadlocks are hard to handle in terms of a domain-independent goal interaction which we call an enabling-condition interaction, in which an action invoked to achieve one goal has a side-effect of making it easier to achieve other goals. If different actions have different useful side-effects, then it can be difficult to determine which set of actions will produce the best plan.

UAI Conference 1985 Conference Paper

An Evaluation of Two Alternatives to Minimax

• Dana S. Nau
• Paul Walton Purdom Jr.
• Chun-Hung Tzeng

In the field of Artificial Intelligence, traditional approaches to choosing moves in games involve the we of the minimax algorithm. However, recent research results indicate that minimizing may not always be the best approach. In this paper we summarize the results of some measurements on several model games with several different evaluation functions. These measurements, which are presented in detail in [NPT], show that there are some new algorithms that can make significantly better use of evaluation function values than the minimax algorithm does.

NMR Workshop 1984 Conference Paper

An Abductive Non-Monotonic Logic

• James A. Reggia
• Dana S. Nau

AIJ Journal 1984 Journal Article

General Branch and Bound, and its relation to A∗ and AO∗

• Dana S. Nau
• Vipin Kumar
• Laveen Kanal

Branch and Bound (B&B) is a problem-solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. Various heuristic search procedures used in artificial intelligence (AI) are considered to be related to B&B procedures. However, in the absence of any generally accepted terminology for B&B procedures, there have been widely differing opinions regarding the relationships between these procedures and B&B. This paper presents a formulation of B&B general enough to include previous formulations as special cases, and shows how two well-known AI search procedures (A∗ and AO∗) are special cases of this general formulation.

AIJ Journal 1983 Journal Article

Pathology on game trees revisited, and an alternative to minimaxing

• Dana S. Nau

Almost all game tree search procedures used in artificial intelligence are variants on minimaxing. Until recently, it was almost universally believed that searching deeper on the game tree with such procedures would in general yield a better decision. However, recent investigations have revealed the existence of many game trees and evaluation functions which are ‘pathological’ in the sense that searching deeper consistently degrades the decision. This paper extends these investigations in two ways. First, it is shown that whenever the evaluation function satisfies certain properties, pathology will occur on any game tree of high enough constant branching factor. This result, together with Monte Carlo studies on actual games, gives insight into the causes of pathology. Second, an investigation is made of a possible cure for pathology: a probabilistic decision procedure which does not use minimaxing. Under some conditions, this procedure gives results superior to minimaxing.

AAAI Conference 1982 Conference Paper

A General Paradigm for AI Search Procedures

• Dana S. Nau

This paper summarizes work on a General Branch and Bound formulation which includes previous formulations as special cases and provides a unified approach to understanding most heuristic search procedures developed in A.I.

AIJ Journal 1982 Journal Article

An investigation of the causes of pathology in games

• Dana S. Nau

Game trees are a useful model of many kinds of decision-making situations, and have been the subject of considerable investigation by researchers in both artificial intelligence and decision analysis. Until recently it was almost universally believed that searching deeper on a game tree would in general improve the quality of a decision. However, recent theoretical investigations [8–10] by this author have demonstrated the existence of an infinite class of game trees for which searching deeper consistently degrades the quality of a decision. This paper extends the previous work in two ways. First, the existence of pathology is demonstrated in a real game (Pearl's Game) using a real evaluation function. This pathological behavior occurs despite the fact that the evaluation function function increases dramatically in accuracy toward the end of the game. Second, the similarities and differences between this game and a related nonpathological game are used as grounds for speculation on why pathology occurs in some games and not in others.

AIJ Journal 1982 Journal Article

The last player theorem

• Dana S. Nau

Game trees are an important model of decision-making situations, both in artificial intelligence and decision analysis, but many of the properties of game trees are not well understood. One of these properties is known as biasing: when a minimax search is done to an odd search depth, all moves tend to look good, and when it is done to an even search depth, all modes tend to look bad. One explanation sometimes proposed for biasing is that whenever a player makes a move his position is ‘strengthened’, and that the evaluation function used in the minimax search reflects this. However, the mathematical results in this paper suggest that biasing may instead be due to the errors made by the evaluation function.

AAAI Conference 1980 Conference Paper

Pathology on Game Trees: A Summary of Results

• Dana S. Nau