M.Sc Thesis


M.Sc StudentRivlin Or
SubjectGeneralized Planning with Deep Reinforcement
Learning
DepartmentDepartment of Autonomous Systems and Robotics
Supervisors ASSOCIATE PROF. Erez Karpas
ASSOCIATE PROF. Tamir Hazan


Abstract

A hallmark of intelligence is the ability to deduce general principles from examples, which are correct beyond the range of those observed. Generalized Planning deals with finding such principles for a class of planning problems, so that principles discovered using small instances of a domain can be used to solve much larger instances of the same domain. For example, one can always find the exit of a maze by following a specific wall and moving along it, which would work for any maze that has an exit. Such a strategy might not be the most efficient, but will always provide a valid solution. Finding such principles is a challenging problem, usually tackled with tool from the planning literature. In this work we study the use of Deep Reinforcement Learning and Graph Neural Networks to learn policies that can generalize well. We model PDDL states and goals as graphs and exploit the generalization capabilities of GNNs in order to train on very small instances and and solve much larger ones in a zero-shot manner. We embed our trained policies inside a search algorithm and compare against a state of the art heuristic planner, achieving superior results in terms of expanded nodes. Our policies successfully generalize to instances that are orders of magnitude larger than those they were trained on.