Browsing by Author "Kuter, Ugur"
Now showing 1 - 6 of 6
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 HTN Planning in Answer Set Programming(2002-05-22) Dix, Jurgen; Kuter, Ugur; Nau, Dana S.In 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 Learning and Verification of Safety Parameters for Airspace Deconfliction(2009-11-30) Rebguns, Antons; Green, Derek; Levine, Geoffrey; Kuter, Ugur; Spears, DianaWe present a Bayesian approach to learning flexible safety constraints and subsequently verifying whether plans satisfy these constraints. Our approach, called the Safety Constraint Learner/Checker (SCLC), is embedded within the Generalized Integrated Learning Architecture (GILA), which is an integrated, heterogeneous, multi-agent ensemble architecture designed for learning complex problem solving techniques from demonstration by human experts. The SCLC infers safety constraints from a single expert demonstration trace, and applies these constraints to the solutions proposed by the agents in the ensemble. Blame for constraint violations is then transmitted to the individual learning/planning/reasoning agents, thereby facilitating new problem-solving episodes. We discuss the advantages of the SCLC and demonstrate empirical results on an Airspace Planning and Deconfliction Task, which was a benchmark application in the DARPA Integrated Learning Program.Item Planning Under Uncertainty: Moving Forward(2006-07-24) Kuter, Ugur; Nau, Dana S.; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Reasoning about uncertainty is an essential component of many real-world planning problems, such as robotic and space applications, military operations planning, air and ground traffic control, and manufacturing systems. The two predominant approaches for planning under uncertainty are based on Markov Decision Processes (MDPs) and Symbolic Model Checking. Despite the recent advances in these approaches, the problem of how to plan under uncertainty is still very hard: the planning algorithms must reason about more than one possible execution path in the world, and the sizes of the solution plans may grow exponentially. This dissertation describes a suite of new planning algorithms for planning under uncertainty. The new algorithms are much more efficient than the previous techniques; in some cases, they find solutions exponentially faster than the previous ones. In particular, our contributions are as follows: (1) A method to take any forward-chaining classical planning algorithm, and systematically generalize it to work for planning in nondeterministic planning domains, where the likelihood of the possible outcomes of the actions are not known. (2) A way, called "Forward State-Space Splitting (FS3)," to take the search control (i.e., pruning) technique of any forward-chaining classical planner, such as TLPlan [BK00], TALplanner [KD01], and SHOP2 [NAI+03], and combine it with BDDs. The result of this combination is a suite of new planning algorithms for nondeterministic planning domains. (3) A way to incorporate the pruning technique of a forward-chaining classical planner into the previous algorithms developed for planning with MDPs. The result is a suite of enhanced planning algorithms for MDP planning. The new planning techniques described here have good potential to be applicable to other research areas as well. In particular, this dissertation describes such potentials in Reinforcement Learning, Hybrid Systems Control, and Planning with Temporal Uncertainty. Finally, the closing remarks include a discussion on the challenges of using search control in planning under uncertainty and some possible ways to address those challenges.