Browsing by Author "Shivashankar, Vikas"
Now showing 1 - 2 of 2
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 Hierarchical Goal Networks: Formalisms and Algorithms for Planning and Acting(2015) Shivashankar, Vikas; Nau, Dana S; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In real-world applications of AI and automation such as in robotics, computer game playing and web-services, agents need to make decisions in unstructured environments that are open-world, dynamic and partially observable. In the AI and Robotics research communities in particular, there is much interest in equipping robots to operate with minimal human intervention in diverse scenarios such as in manufacturing plants, homes, hospitals, etc. Enabling agents to operate in these environments requires advanced planning and acting capabilities, some of which are not well supported by the current state of the art automated planning formalisms and algorithms. To address this problem, in my thesis I propose a new planning formalism that addresses some of the inadequacies in current planning frameworks, and a suite of planning and acting algorithms that operate under this planning framework. The main contributions of this thesis are: - Hierarchical Goal Network (HGN) Planning Formalism. This planning formalism combines aspects (and therefore harnesses advantages) of Classical Planning and Hierarchical Task Network (HTN) Planning, two of the most prominent planning formalisms currently in use. In particular, HGN planning algorithms, while retaining the efficiency and scalability advantages of HTNs, also allows incorporation of heuristics and other reasoning techniques from Classical Planning. - Planning Algorithms. Goal Decomposition Planner (GDP) and the Goal Decomposition with Landmarks (GoDeL) planner are two HGN planning algorithms that combines hierarchical decomposition with classical planning heuristics to outperform state-of-the-art HTN planners like SHOP and SHOP2. - Integration with Robotics. The Combined HGN and Motion Planning (CHaMP) algorithm integrates GoDeL with low-level motion and manipulation planning algorithms in Robotics to generate plans directly executable by robots. Given the need for autonomous agents to operate in open, dynamic and unstructured environments and the obvious need for high-level deliberation capabilities to enable intelligent behavior, the planning-and-acting systems that are developed as part of this thesis may provide unique insights into ways to realize these systems in the real world.