I think the move to RL-based controllers is just the latest trend tbh. There's papers to be written, so they will be written. I can't say I have seen a huge improvement in performance and they suffer from really poor generalisation certainly compared to planning and MPC.
I agree with your comment- the planning problem is in PSPACE and while there are techniques like relaxations and width-based search that allow large portions of it to be solved there are areas that remain intractable (although I'm not sure about width-based search; I haven't really tried it). But we have to distinguish between different kinds of task.
Robot navigation is a broad field, but just going from point A to point B is really hard to see as an open problem. You stick a PID controller on a robot and set some waypoints and it will happily roll, float or fly between them. Or, like I say, just do A* or Dijkstra's. Problems begin if there is anything between A and B. If it's a solid, immovable object, then that's OK. If it moves, things start to get tough. If you want a big chunk of metal moving safely in a dynamic environment full of independent agents that also go about their goals... good luck with that. Terrain, weather, visibility etc just add variables to the problem and that's bad, variables are bad, we don't want variables.
So when I said "solved" above I was really talking about "walking between arbitrary waypoints" as per the OP's turn of phrase. I might have played a bit fast and loose with "arbitrary" because obviously if one waypoint is in a tornado and the other in a volcano... But navigating between waypoints is a solved problem. It's what you do while you navigate between waypoints that's the open problem [1].
Bipedal (and quadrupedal) walking is similar but that's more robotics and less planning and so I know less about it. Still, Asimo could almost walk up a flight of stairs on its own in the '80s. Again, if you assume nice, clean, flat laboratory conditions, we know how to get a legged robot to walk. I know, I've played around with NAO and a tiny robot dog from Hiwonder. They can walk around, dance, get up on their own, shake your hand, play with a ball etc. How cute. Then of course there's all the kung-fu fighting, somersaulting, cartwheeling etc robots doing the rounds on social media. But again the problems begin as soon as you want those kinds of system to do something useful in the real world, where they need to physically interact with solid objects and moving obstacles.
So what I'd say to hedge a bit on what I commented above is that basic path planning and bipedal gaits are solved but those turn out to be only part of the problem of robotic autonomy which is itself still wide open [2].
Which is a good thing. We gotta have something to work on.
_______________________
[1] Of course, sometimes all you need to do is go boom at the far waypoint. I think sometimes people forget we have very effective autonomous navigation systems: specifically, self-guided missiles. When it's fine for a system to destroy itself when it reaches its target and causing maximum damage is a bonus, that simplifies a hell of a lot of stuff that can't be taken for granted with, e.g., self-driving cars. But, at the end of the day, a self-guided missile is exactly a system that goes from point A to point B autonomously. Fire and forget, that sort of thing.
[2] And when I say "bipedal gait is solved" I'm no saying I like the solution. I'm still smarting that my Passive Dynamic Walking project didn't get funded.