Browsing by Author "Nau, Dana"
Now showing 1 - 9 of 9
Results Per Page
Sort Options
Item Hierarchical Goal Network Planning: Initial Results(2011-05-31) Shivashankar, Vikas; Kuter, Ugur; Nau, DanaIn applications of HTN planning, repeated problems have arisen from the lack of correspondence between HTN tasks and classical-planning goals. We describe these problems and provide a new Hierarchical Goal Network (HGN) planning formalism that overcomes them. HGN tasks have syntax and semantics analogous to classical planning problems, and this has several benefits: HGN methods can be significantly simpler to write than HTN methods, there is a clear criterion for whether the HGN methods are correct, and classical-planning heuristic functions can be adapted for use in HGN planning. We define the HGN formalism, illustrate how to prove correctness of HGN methods, provide a planning algorithm called GNP (Goal Network Planner), and present experimental results showing that GNP’s performance compares favorably to that of SHOP2. We provide a planning-graph heuristic for optional use in GNP, and give experimental results showing the kinds of situations in which it helps or hurts GNP’s performance.Item HTN Planning in Answer Set Programming(UMIACS, University of Maryland, 2002-05-22) Dix, Jürgen; Kuter, Ugur; Nau, DanaIn this paper we introduce a formalism for solving Hierarchical Task NEtwork (HTN) Planning using Answer Set Programming (ASP). The ASP paradigm evolved out of the stable semantics for logic programs in recent years and is strongly related to nonmonotonic logics. We consider the formulation of HTM planning as described in the SHOP planning system and define a systematic translation method from SHOP's representation of the planning problems into logic programs with negation. We show that our translation is sound and complete: answer sets of the logic programs obtained by our translation correspond exactly to the solutions of the planning problems. Our approach does not rly on a particular system for computing answer sets. It can therefore serve as a means to evaluate ASP systems by using well-established benchmarks from the planning community. We tested our method on various such benchmarks and used smodels and DLV for computing answer sets. We compared our method to (1) similar approaches based on non-HTN planning and (2) SHOP, a dedicated planning system. We show that our approach outperforms non-HTN methods and that its performance is closer to that of SHOP, when we are using ASP systems which allow for nonground programs. (Also UMIACS-TR-2002-18)Item Interactive Planning under Uncertainty with Causal Modeling and Analysis(2003-01-21) Kuter, Ugur; Nau, Dana; Lemmer, John F.This paper describes a new technique for interactive planning under conditions of uncertainty. Our approach is based on the use of the Air Force Research Laboratory's Causal Analysis Tool (CAT), a system for creating and analyzing causal models similar to Bayes networks. In order to use CAT as a tool for planning, users go through an iterative process in which they use CAT to create and analyze alternative plans. One of the biggest difficulties is that the number of possible plans is exponential. In any planning problem of significant size, it is impossible for the user to create and analyze every possible plan; thus users can spend days arguing about which actions to include in their plans. To solve this problem, we have developed a way to quickly compute the minimum and maximum probabilities of success associated with a partial plan, and use these probabilities to recommend which actions the user should include in the plan in order to get the plan that has the highest probability of success. This provides an exponential reduction in amount of time needed to find the best plan. (UMIACS-TR-2003-05)Item M-Translog-2: A Planning Domain Designed for AIPS-2002(2002-10-03) Wu, Dan; Nau, DanaThis document describes UM-Translog-2, which is an extended version of the UM Translog planning domain. The extensions include some numerical-computation features to make the domain a more realistic model of transportation-logistics problems. We are proposing UM- Translog-2 as a candidate domain for AIPS-2002 planning competition. (Also UMIACS-TR-2002-82)Item Manufacturing Cell Formation by State-Space Search(1993) Ghosh, Subrata; Mahanti, Ambuj; Nagi, Rakesh; Nau, Dana; ISRThis paper addresses the problem of grouping machines in order to design cellular manufacturing cells, with an objective to minimize intercell flow. This problem is replaced to one of the major aims of group technology (GT): to decompose the manufacturing system into manufacturing cells that are as independent as possible.This problem is NP-hard. Thus, nonheuristic methods cannot address problems of typical industrial dimensions because they would require exorbitant amounts of computing time, while fast heuristic methods may suffer from sub-optimality.
We present a branch-and-bound state-space search algorithm that attempts to overcome both these deficiencies. One of the major strengths of this algorithm is its efficient branching and search strategy. In addition, the algorithm employs the efficient Inter-Cell Traffic Minimization Method to provide good upper bounds, and computes lower bounds based on a relaxation of merging.
Item On the Use of Integer Programming Models in AI Planning(1999) Vossen, Thomas; Ball, Michael O.; Lotem, Amnon; Nau, Dana; ISRRecent research has shown the promise of using propositional reasoning and search to solve AI planning problems. In this paper, we further explore this area by applying Integer Programming to solve AI planning problems. The application of Integer Programming to AI planning has a potentially significant advantage, as it allows quite naturally for the incorporation of numerical constraints and objectives into the planning domain. Moreover, the application of Integer Programming to AI planning addresses one of the challenges in propositional reasoning posed by Kautz and Selman, who conjectured that the principal technique used to solve Integer Programs---the linear programming (LP) relaxation---is not useful when applied to propositional search. We discuss various IP formulations for the class of planning problems based on the STRIPS paradigm. Our main objective is to show that a carefully chosen IP formulation significantly improves the "strength" of the LP relaxation, and that the resultant LPs are useful in solving the IP and the associated planning problems. Our results clearly show the importance of choosing the "right" representation, and more generally the promise of using Integer Programming techniques in the AI planning domain.Item SHOP and M-SHOP: Planning with Ordered Task Decomposition(2000-06-17) Nau, Dana; Cao, Yue; Lotem, Amnon; Munoz-Avila, HectorSHOP (Simple Hierarchical Ordered Planner) and M-SHOP (Multi-task-list SHOP) are planning algorithms with the following characteristics. * SHOP and M-SHOP plan for tasks in the same order that they will later be executed. This avoids some task-interaction issues that arise in other HTN planners, making the planning algorithms relatively simple. This also makes it easy to prove soundness and completeness results. * Since SHOP and M-SHOP know the complete world-state at each step of the planning process, they can use highly expressive domain representations. For example, they can do planning problems that require Horn-clause inferencing, complex numeric computations, and calls to external programs. * In our tests, SHOP and M-SHOP were several orders of magnitude faster than Blackbox, IPP, and UMCP, and were several times as fast as TLplan. * The approach is powerful enough to be used in complex real-world planning problems. For example, we are using a Java implementation of SHOP as part of the HICAP plan-authoring system for Noncombatant Evacuation Operations (NEOs). In this paper, we describe SHOP and M-SHOP, present soundness and completeness results for them, and compare them experimentally to Blackbox, IPP, TLplan, and UMCP. The results suggest that planners that generate totally ordered plans starting from the initial state can "scale up" to complex planning problems better than planners that use partially ordered plans.Item SHOP: Simple Hierarchical Ordered Planner(1999-03-17) Nau, Dana; Cao, Yue; Lotem, Amnon; Munoz-Avia, HectorSHOP (Simple Hierarchical Ordered Planner) is a domain-independent HTN Planning system with the following characteristics. * SHOP plans for tasks in the same order that they will later be executed. This avoids some of the goal-interaction issues that arise in other HTN planners, thus making the planning algorithm relatively simple. * The planning algorithm is sound and complete over a large class of problems. * Since SHOP knows the complete world-state at each step of the planning process, it can use highly expressive domain representations. For example, it can do planning problems that require complex numeric computations. * In our tests, SHOP solved problems several orders of magnitude faster than Blackbox and TLplan. This occured even though SHOP is written in Lisp and the other planners are written in C. (Also cross-referenced as UMIACS-TR 99-04)Item Theoretical and Experimental Analysis of an Evolutionary Social-Learning Game(2012-01-13) Carr, Ryan; Raboin, Eric; Parker, Austin; Nau, DanaAn important way to learn new actions and behaviors is by observing others, and several evolutionary games have been developed to investigate what learning strategies work best and how they might have evolved. In this paper we present an extensive set of mathematical and simulation results for Cultaptation, which is one of the best-known such games. We derive a formula for measuring a strategy's expected reproductive success, provide algorithms to compute near-best-response strategies and near-Nash equilibria, and provide techniques for efficient implementation of those algorithms. Our experimental studies provide strong evidence for the following hypotheses: 1. The best strategies for Cultaptation and similar games are likely to be conditional ones in which the choice of action at each round is conditioned on the agent's accumulated experience. Such strategies (or close approximations of them) can be computed by doing a lookahead search that predicts how each possible choice of action at the current round is likely to affect future performance. 2. Such strategies are likely to exploit most of the time, but will have ways of quickly detecting structural shocks, so that they can switch quickly to innovation in order to learn how to respond to such shocks. This conflicts with the conventional wisdom that successful social-learning strategies are characterized by a high frequency of innovation; and agrees with recent experiments by others on human subjects that also challenge the conventional wisdom.