[YeGoblynQueenne]

That's right, environment conditions play a huge role and modulate efficacy to a great degree. And the same applies to pathfinding with osbstacle avoidance otherwise we'd all have our robot maids and self-driving cars already.

But we have the theory down pat, is what I was trying to say. There's a lot of engineering still that remains to do, but e.g. Dijkstra's algorithm... works.

I had a longer comment in place of the one I made above, that tried to caveat this a bit more. I also linked to this survey:

A Comprehensive Survey of Path Planning Algorithms for Autonomous Systems and Mobile Robots: Traditional and Modern Approaches

https://www.sciencedirect.com/science/article/pii/S259012302...

That's just one review, there's more. The striking thing is that there are so many approaches for robotics path planning. That means a) it's a problem for which many solutions are known but b) there's not one dominant approach. One reason for that is what you point out, that it doesn't always work that well.

And that's just path planning, i.e. figuring out where to walk. Gait is a whole other ball game, figuring out how to get there.

[cpgxiii]

The reality of robotics is that the existence of the theory often means little about practical feasibility. I have myself joked about problems being solved in the '80s, but the joke is really something closer to "all of the interesting problems in planning and control were solved in the' 80s and known to be intractable", because the theoretical complexity is just prohibitive.

The last 40 or so years haven't really moved the needle on theoretical complexity, but we have developed new methods and improved existing methods (and also computers have gotten massively better) such that a much larger subset of the problem space is actually practically solvable. Even still, it is almost trivially easy to go from a practically-solvable problem to a practically-unsolvable one, and much of the confusion that exists in the popular understanding of robot capabilities is the result of the solvable/unsolvable line being so close and subtle.

On the topic of bipedal (and quadrupedal) locomotion, I think you could actually argue that we very much do not understand how to solve the problem, and exhibit #1 is that basically everyone (Boston Dynamics included) is giving up on MPC-based control and adopting RL-based controllers which seem to work better but are much less comprehensible from a theory standpoint.

[YeGoblynQueenne]

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.