Hierarchical Goal Networks: Formalisms and Algorithms for Planning and Acting

Abstract

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.