The airplane example was from 1973.

The NASA example was from about 1977.

The assignment problem was work of Ford and Fulkerson way before 1975.

Actually the assignment problem can be nicely done with just the simplex algorithm of linear programming. At first cut, the problem appears to be another nasty, NP-complete problem in combinatorial optimization, but for this problem the simplex algorithm can be started with a initial integer solution, and then on this problem the simplex algorithm will, automatically, naturally, with no extra effort, maintain an integer solution and find an optimal integer solution. Specializing the simplex algorithm in this way can yield "the network simplex algorithm" and can save on the computing, but it's still just the simplex algorithm. IIRC more recently D. Bertsekas at MIT has a guaranteed polynomial algorithm for this problem.

IIRC the history, G. Dantzig invented linear programming and the simplex algorithm in the late 1940s at RAND for the USAF due to his experience in WWII of trying to solve military logistic problems, e.g., move 10,000 soldiers and all their stuff 5000 miles in a feasible way and in least time/cost. That's a planning problem.

Going back to the 1950s, linear programming was used for the planning problems for the first US nuclear powered submarines. Part of the work was the "critical path" -- the time for the necessarily sequential work on this path was the time for the whole project, and saving one hour on this path would do the whole project faster by the one hour. So, how to allocate money to the projects to minimize the time for the critical path? First cut, it's linear programming problem.

There is a large class of planning problems in optimization over time, call it sequential decision making or some such, maybe under uncertainty. IIRC R. Bellman did his first good work on these problems well before 1973. He called his work dynamic programming. Now, for the uncertainty case, with the mathematical assumptions made really clear for the probabilistic aspects, the field is Markov decision processes and/or stochastic optimal control.

My observation here: There's been a lot of really good work on challenging problems in planning with Dantzig, Bellman, and others going back to the 1950s and late 1940s.

Optimization has long since identified a class of algorithms called "greedy": So, roughly, attack the problem in steps, and at each step do what just for that step seems to be the best, greedy action, basically ignoring what might do in future steps. Well it's nice when a greedy algorithm will solve a problem, but optimization, here for the OP, combinatorial optimization, has long known that often there can be no effective greedy algorithm.

It appears that the Sussman anomaly is that when humans solve the block stacking problem, the humans have to discover that a greedy algorithm won't work and have to think ahead a little. But, no doubt, one way and another, humans have been doing that for thousands of years.

When I, really an applied mathematician, once joined an AI (artificial intelligence) group, I was surprised to find some of our student workers, who had had computer science courses in AI, talking about "planning" problems and mentioning the block stacking problem as an example. I was shocked to hear that description, attitude, etc. about planning: That is, from the view of applied math, what they were talking about was totally trivial, kindergarten stuff, where the applied math stuff had been way past that for decades and where those students were ignoring the applied math stuff. So, right, maybe the Sussman and block stacking work on "planning" was closer to some of childish, even primitive, human psychology than to how to make progress, e.g., as in applied math, for solving real planning problems.

So, maybe, MAYBE!!!, if we got started on how human intelligence works and made a lot of progress there, and do this as a part of computer science, then as a special case we would also see how to re-do the Dantzig, Bellman, Bertsekas, etc. work and much more but already inside computer science and not outside computing as in just the applied math. Maybe.

So, maybe my goals were in that sense lower than Sussman's: I just wanted means, applied math if it could help, to solve real planning problems assuming that, with a good solution, we would then, as essentially a quite separate step, have to program a computer to do do the arithmetic and manipulate the data. So, maybe Sussman was hoping that computer science could program a computer to be intelligent much like a human and, in effect, do the applied math, as necessary, internally on its own. So, his block stacking was a start on what such AI would have to do? Gee, I was just interested in the applied math to say how to program a computer to get solutions!!! But if Sussman and/or AI can program a computer to discover and print out a proof that P = NP, fine with me!