Arrow Research search

Author name cluster

David W. Aha

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

24 papers
2 author rows

Possible papers

24

IJCAI Conference 2017 Conference Paper

A Goal Reasoning Agent for Controlling UAVs in Beyond-Visual-Range Air Combat

  • Michael W. Floyd
  • Justin Karneeb
  • Philip Moore
  • David W. Aha

We describe the Tactical Battle Manager (TBM), an intelligent agent that uses several integrated artificial intelligence techniques to control an autonomous unmanned aerial vehicle in simulated beyond-visual-range (BVR) air combat scenarios. The TBM incorporates goal reasoning, automated planning, opponent behavior recognition, state prediction, and discrepancy detection to operate in a real-time, dynamic, uncertain, and adversarial environment. We describe evidence from our empirical study that the TBM significantly outperforms an expert-scripted agent in BVR scenarios. We also report the results of an ablation study which indicates that all components of our agent architecture are needed to maximize mission performance.

PDF Details

ICAPS Conference 2017 Conference Paper

A New Approach to Temporal Planning with Rich Metric Temporal Properties

  • Son Thanh To
  • Benjamin Johnson 0003
  • Mark Roberts
  • David W. Aha

Temporal logics have been used in autonomous planning to represent and reason about temporal planning problems. However, such techniques have typically been restricted to either (1) representing actions, events, and goals with temporal properties or (2) planning for temporally-extended goals under restrictive assumptions. We introduce Mixed Propositional Metric Temporal Logic (MPMTL) where formulae are built over mixed binary and continuous real variables. We introduce a planner, MTP, that solves MPMTL problems and includes a SAT-solver, model checker for a polynomial fragment of MPMTL, and a forward search algorithm. We extend PDDL 2. 1 with MPMTL syntax to create MPDDL and an associated parser. The empirical study shows that MTP outperforms the state-of-the-art PDDL+ planner SMTPlan+ on several domains it performed best on and MTP performs and scales on problem size well for challenging domains with rich temporal properties we create.

Details

ICAPS Conference 2016 Conference Paper

Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems

  • Ron Alford
  • Gregor Behnke
  • Daniel Höller
  • Pascal Bercher
  • Susanne Biundo
  • David W. Aha

Hierarchical Task Network (HTN) planning is a formalism that can express constraints which cannot easily be expressed by classical (non-hierarchical) planning approaches. It enables reasoning about procedural structures and domain-specific search control knowledge. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because it is not clear how to estimate the goal distance for a partially-ordered task network. When using SHOP2-style progression, a task network of yet unprocessed tasks is maintained during search. In the general case it can grow arbitrarily large. However, many — if not most — existing HTN domains have a certain structure (called tail-recursive) where the network's size is bounded. We show how this bound can be calculated and exploited to automatically translate tail-recursive HTN problems into non-hierarchical STRIPS representations, which allows using both hierarchical structures and classical planning heuristics. In principle, the approach can also be applied to non-tail-recursive HTNs by incrementally increasing the bound. We give three translations with different advantages and present the results of an empirical evaluation with several HTN domains that are translated to PDDL and solved by two current classical planning systems. Our results show that we can automatically find practical bounds for solving partially-ordered HTN problems. We also show that classical planners perform similarly with our automatic translations versus a previous hand-bounded HTN translation which is restricted to totally-ordered problems.

Details

IJCAI Conference 2016 Conference Paper

Hierarchical Planning: Relating Task and Goal Decomposition with Task Sharing

  • Ron Alford
  • Vikas Shivashankar
  • Mark Roberts
  • Jeremy Frank
  • David W. Aha

Considerable work has focused on enhancing the semantics of Hierarchical Task Networks (HTNs) in order to advance the state-of-the-art in hierarchical planning. For instance, the Hierarchical Goal Netwwork (HGN) formalism operates over a hierarchy of goals to facilitate tighter integration of decompositional planning with classical planning. Another example is the Action Notation Markup Language (ANML) which adds aspects of generative planning and task-sharing to the standard HTN semantics. The aim of this work is to formally analyze the effects of these modifications to HTN semantics on the computational complexity and expressivity of HTN planning. To facilitate analysis, we unify goal and task planning into Goal-Task Network (GTN) planning. GTN models use HTN and HGN constructs, but have a solution-preserving mapping back to HTN planning. We then show theoretical results that provide new insights into both the expressivity as well as computational complexity of GTN planning under a number of different semantics. Our work lays a firm footing to clarify exact semantics for recent planners based on ANML, HGNs, and similar hierarchical languages.

PDF Details

ICAPS Conference 2015 Conference Paper

Tight Bounds for HTN Planning

  • Ron Alford
  • Pascal Bercher
  • David W. Aha

Although HTN planning is in general undecidable, there are many syntactically identifiable sub-classes of HTN problems that can be decided. For these sub-classes, the decision procedures provide upper complexity bounds. Lower bounds were often not investigated in more detail, however. We generalize a propositional HTN formalization to one that is based upon a function-free first-order logic and provide tight upper and lower complexity results along three axes: whether variables are allowed in operator and method schemas, whether the initial task and methods must be totally ordered, and where recursion is allowed (arbitrary recursion, tail-recursion, and acyclic problems). Our findings have practical implications, both for the reuse of classical planning techniques for HTN planning, and for the design of efficient HTN algorithms.

Details

IJCAI Conference 2015 Conference Paper

Tight Bounds for HTN Planning with Task Insertion

  • Ron Alford
  • Pascal Bercher
  • David W. Aha

Hierarchical Task Network (HTN) planning with Task Insertion (TIHTN planning) is a formalism that hybridizes classical planning with HTN planning by allowing the insertion of operators from outside the method hierarchy. This additional capability has some practical benefits, such as allowing more flexibility for design choices of HTN models: the task hierarchy may be specified only partially, since “missing required tasks” may be inserted during planning rather than prior planning by means of the (predefined) HTN methods. While task insertion in a hierarchical planning setting has already been applied in practice, its theoretical properties have not been studied in detail, yet – only EXPSPACE membership is known so far. We lower that bound proving NEXPTIMEcompleteness and further prove tight complexity bounds along two axes: whether variables are allowed in method and action schemas, and whether methods must be totally ordered. We also introduce a new planning technique called acyclic progression, which we use to define provably efficient TIHTN planning algorithms.

PDF Details

SoCS Conference 2015 Conference Paper

Tight Bounds for HTN Planning with Task Insertion (Extended Abstract)

  • Ron Alford
  • Pascal Bercher
  • David W. Aha

Hierarchical Task Network (HTN) planning with task insertion (TIHTN planning) is a variant of HTN planning. In HTN planning, the only means to alter task networks is to decompose compound tasks. In TIHTN planning, tasks may also be inserted directly. In this paper we provide tight complexity bounds for TIHTN planning along two axis: whether variables are allowed and whether methods must be totally ordered.

Details

AIJ Journal 2013 Journal Article

Multiparticipant chat analysis: A survey

  • David C. Uthus
  • David W. Aha

We survey research on the analysis of multiparticipant chat. Multiple research and applied communities (e. g. , AI, educational, law enforcement, military) have interest in this topic. After introducing some context, we describe relevant problems and how these have been addressed using AI techniques. We also identify recent research trends and unresolved issues that could benefit from more attention.

Details DOI

IJCAI Conference 2011 Conference Paper

Integrated Learning for Goal-Driven Autonomy

  • Ulit Jaidee
  • H
  • eacute; ctor Mu
  • ntilde; oz-Avila
  • David W. Aha

Goal-driven autonomy (GDA) is a reflective model of goal reasoning that controls the focus of an agent's planning activities by dynamically resolving unexpected discrepancies in the world state, which frequently arise when solving tasks in complex environments. GDA agents have performed well on such tasks by integrating methods for discrepancy recognition, explanation, goal formulation, and goal management. However, they require substantial domain knowledge, including what constitutes a discrepancy and how to resolve it. We introduce LGDA, a learning algorithm for acquiring this knowledge, modeled as cases, that and integrates case-based reasoning and reinforcement learning methods. We assess its utility on tasks from a complex video game environment. We claim that, for these tasks, LGDA can significantly outperform its ablations. Our evaluation provides evidence to support this claim. LGDA exemplifies a feasible design methodology for deployable GDA agents.

PDF Details DOI

JMLR Journal 2009 Journal Article

Cautious Collective Classification

  • Luke K. McDowell
  • Kalyan Moy Gupta
  • David W. Aha

Many collective classification (CC) algorithms have been shown to increase accuracy when instances are interrelated. However, CC algorithms must be carefully applied because their use of estimated labels can in some cases decrease accuracy. In this article, we show that managing this label uncertainty through cautious algorithmic behavior is essential to achieving maximal, robust performance. First, we describe cautious inference and explain how four well-known families of CC algorithms can be parameterized to use varying degrees of such caution. Second, we introduce cautious learning and show how it can be used to improve the performance of almost any CC algorithm, with or without cautious inference. We then evaluate cautious inference and learning for the four collective inference families, with three local classifiers and a range of both synthetic and real-world data. We find that cautious learning and cautious inference typically outperform less cautious approaches. In addition, we identify the data characteristics that predict more substantial performance differences. Our results reveal that the degree of caution used usually has a larger impact on performance than the choice of the underlying inference algorithm. Together, these results identify the most appropriate CC algorithms to use for particular task characteristics and explain multiple conflicting findings from prior CC research. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

PDF Details

IJCAI Conference 2007 Conference Paper

  • David McSherry
  • David W. Aha

Eliminating previously recommended products in critiquing limits the choices available to users when they attempt to navigate back to products they critiqued earlier in the dialogue (e. g. , in search of cheaper alternatives). In the worst case, a user may find that the only product she is prepared to accept (e. g. , having ruled out cheaper alternatives) has been eliminated. However, an equally serious problem if previous recommendations are not eliminated is that products that satisfy the user's requirements, if any, may be unreachable by any sequence of critiques. We present a new version of progressive critiquing that leaves open the option of repeating a previous recommendation while also addressing the unreachability problem. Our empirical results show that the approach is most effective when users refrain from over-critiquing attributes whose current values are acceptable.

PDF Details

KER Journal 2005 Journal Article

Advances in conversational case-based reasoning

  • David W. Aha
  • David McSherry
  • Qiang Yang

A considerable amount of research in case-based reasoning (CBR) has recently focused on conversational CBR as a means of providing more effective support for interactive problem solving. We review progress made to date and identify challenges that remain to be addressed.

Details DOI

KER Journal 2005 Journal Article

Case-based reasoning commentaries: introduction

  • David W. Aha
  • Cindy Marling
  • Ian Watson

We are delighted to present this special issue of The Knowledge Engineering Review, as it marks a significant accomplishment of the case-based reasoning (CBR) community. Its 19 commentaries, written by 41 authors, represent a compendium on the state-of-the-art in CBR. These evolved from a 2003 workshop that was held at Waiheke Island and Queenstown, New Zealand and chaired by Alec Holt and Ian Watson. The workshop's delegates identified the primary topics of CBR research and application, selected representative influential publications for each topic, and were encouraged to co-author commentaries on each topic with other CBR experts who were unable to attend. These collaborations produced the articles you now see. While several reviews exist on CBR (e.g. Marir & Watson, 1994; López de Mántaras & Plaza, 1997; Lenz et al., 1998), few have been published recently or have similar historical and subject breadth.

Details DOI

AAAI Conference 2005 System Paper

TIELT: A Testbed for Gaming Environments

  • Matthew Molineaux
  • David W. Aha

Many AI researchers want to test the utility of their systems in complex task environments defined by (e.g., real-time strategy) gaming simulators and/or simulators of computergenerated forces. Also, many developers of commercial and military gaming simulators seek behaviors that can be supported by these systems. However, these integrations require great effort. We will demonstrate the late Alpha version of TIELT, a testbed designed to fill these needs.

PDF Details

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.

Details

AIJ Journal 1998 Journal Article

A probabilistic framework for memory-based reasoning

  • Simon Kasif
  • Steven Salzberg
  • David Waltz
  • John Rachlin
  • David W. Aha

In this paper, we propose a probabilistic framework for memory-based reasoning (MBR). The framework allows us to clarify the technical merits and limitations of several recently published MBR methods and to design new variants. The proposed computational framework consists of three components: a specification language to define an adaptive notion of relevant context for a query; mechanisms for retrieving this context; and local learning procedures that are used to induce the desired action from this context. We primarily focus on actions in the form of a classification. Based on the framework we derive several analytical and empirical results that shed light on MBR algorithms. We introduce the notion of an MBR transform, and discuss its utility for learning algorithms. We also provide several perspectives on memory-based reasoning from a multi-disciplinary point of view.

Details DOI

KER Journal 1997 Journal Article

Simplifying decision trees: A survey

  • LEONARD A. BRESLOW
  • David W. Aha

Induced decision trees are an extensively-researched solution to classification tasks. For many practical tasks, the trees produced by tree-generation algorithms are not comprehensible to users due to their size and complexity. Although many tree induction algorithms have been shown to produce simpler, more comprehensible trees (or data structures derived from trees) with good classification accuracy, tree simplification has usually been of secondary concern relative to accuracy, and no attempt has been made to survey the literature from the perspective of simplification. We present a framework that organizes the approaches to tree simplification and summarize and critique the approaches within this framework. The purpose of this survey is to provide researchers and practitioners with a concise overview of tree-simplification approaches and insight into their relative capabilities. In our final discussion, we briefly describe some empirical findings and discuss the application of tree induction algorithms to case retrieval in case-based reasoning systems.

Details DOI
v2026.09.13