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.