  Reinforcement learning algorithms such as hindsight experience replay (HER)
and hindsight goal generation (HGG) have been able to solve challenging robotic
manipulation tasks in multi-goal settings with sparse rewards.
  HER achieves its training success through hindsight replays of past
experience with heuristic goals, but under-performs in challenging tasks in
which goals are difficult to explore.
  HGG enhances HER by selecting intermediate goals that are easy to achieve in
the short term and promising to lead to target goals in the long term.
  This guided exploration makes HGG applicable to tasks in which target goals
are far away from the object's initial position.
  However, HGG is not applicable to manipulation tasks with obstacles because
the euclidean metric used for HGG is not an accurate distance metric in such
environments.
  In this paper, we propose graph-based hindsight goal generation (G-HGG), an
extension of HGG selecting hindsight goals based on shortest distances in an
obstacle-avoiding graph, which is a discrete representation of the environment.
  We evaluated G-HGG on four challenging manipulation tasks with obstacles,
where significant enhancements in both sample efficiency and overall success
rate are shown over HGG and HER.
  Videos can be viewed at https://sites.google.com/view/demos-g-hgg/.
