Thanks for the specific reference; I've been meaning to look over all the papers on the home page for a few days now, and will read in more depth this weekend, I hope.
It sounds like the graph-based planning is most useful when the ground-truth map is expected to be dynamic, or perhaps when it is large enough that the metrical (global) planner will have difficulty planning typical movements. I do see some drastic loop closures from time to time in my tests in my apartment, but I think these will go away when I get around to implementing sensor fusion with my motor encoder and cheap IMU, so the odometry improves. And, of course, there are no ground-truth dynamic changes to my apartment; the graph map should be relatively fixed.
So, I'll put down graph-based high-level planning, per the right side of that Figure 2, on my list of stretch goals. I imagine that it would be the most useful goal-setting API to offer to a high-level abstract planner (either human or automated). For instance, at least some of the Neato vacuum cleaners are known to do super-global navigation based on a set (graph?) of waypoints (nodes?), on a roughly one-per-room basis.
Postdoc in MIT's MAE department; doing visiting ML work at JHU.