Computer Science Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2756
Browse
2 results
Search Results
Item Refinement Acting vs. Simple Execution Guided by Hierarchical Planning(2021) Bansod, Yash; Nau, Dana; Systems Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Humans have always reasoned about complex problems by organizing them into hierarchical structures. One approach to artificial intelligence planning is to design intelligent agents capable of breaking complex problems into multiple levels of abstraction so that at any one level, the problem becomes small and simple. However, for an agent to reason at multiple levels of abstraction, it needs knowledge at those abstraction levels. Hierarchical Task Network (HTN) planning allows us to do precisely that. This thesis presents a novel HTN planning algorithm that uses iterative tree traversal to refine HTNs. We also develop a purely reactive HTN acting algorithm using a similar procedure. Preserving the hierarchy in HTN plans can be helpful during execution. We make use of this fact to develop an algorithm for integrated HTN planning and acting. We show through experiments that our algorithm is an improvement over a widely used approach to planning and control.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.