Timezone: »

 
Poster
Sub-Goal Trees -- a Framework for Goal-Based Reinforcement Learning
Tom Jurgenson · Or Avner · Edward Groshev · Aviv Tamar

Tue Jul 14 10:00 AM -- 10:45 AM & Tue Jul 14 11:00 PM -- 11:45 PM (PDT) @ Virtual
in Poster Session 4 »

Many AI problems, in robotics and other domains, are goal-directed, essentially seeking a trajectory leading to some goal state. Reinforcement learning (RL), building on Bellman's optimality equation, naturally optimizes for a single goal, yet can be made goal-directed by augmenting the state with the goal. Instead, we propose a new RL framework, derived from a dynamic programming equation for the all pairs shortest path (APSP) problem, which naturally solves goal-directed queries. We show that this approach has computational benefits for both standard and approximate dynamic programming. Interestingly, our formulation prescribes a novel protocol for computing a trajectory: instead of predicting the next state given its predecessor, as in standard RL, a goal-conditioned trajectory is constructed by first predicting an intermediate state between start and goal, partitioning the trajectory into two. Then, recursively, predicting intermediate points on each sub-segment, until a complete trajectory is obtained. We call this trajectory structure a sub-goal tree. Building on it, we additionally extend the policy gradient methodology to recursively predict sub-goals, resulting in novel goal-based algorithms. Finally, we apply our method to neural motion planning, where we demonstrate significant improvements compared to standard RL on navigating a 7-DoF robot arm between obstacles.

Keywords: Algorithms · Planning and Control · Reinforcement Learning · Reinforcement Learning Theory · Reinforcement Learning - General
[ Slides] 

Author Information

Tom Jurgenson (Technion)
Or Avner (Technion)
Edward Groshev (Osaro, Inc.)
Aviv Tamar (Technion)

More from the Same Authors