> The problem was first identified by Sussman as a part of his PhD research. Sussman (and his supervisor, Marvin Minsky) believed that intelligence requires a list of exceptions or tricks, and developed a modular planning system for "debugging" plans. Most modern planning systems can handle this anomaly, but it is still useful for explaining why planning is non-trivial.
So, planning is "non-trivial"?
Hmm ....
Is that a new, surprising observation?
Okay, let's see:
(1) Suppose for positive integers m and n we have m workers, n jobs for the workers to do, for each worker a list of what jobs they are able to do and want to assign each worker to one job, a different job for each worker, to get the most workers assigned. So, how might we do that?
(2) Suppose we also have for each pair of a worker and a job how fast that worker can do that job. Now we want to assign the workers to the jobs so that the slowest assignment made is as fast as possible.
For (2), once on a job, as I arrived to work, NASA had just called. They had two satellites, A and B. Each satellite had some number of channels for signals; each signal needed a channel, and each channel could server just one signal. The signals assigned to satellite A were already fixed. The question was how to assign the remaining signals to satellite B.
Here was the problem: For each signal assigned to a channel in B, there would be an angle in the sky between A and B where that assignment would cause signal interference. So, the question was how to make the assignments to minimize the largest interference angle encountered.
(3) A fly by night small package delivery service has 33 fast airplanes wants to serve 90 US cities. Currently all the planes are in a central US city. The city has packages to be delivered to the 90 cities. All the planes are empty. And we have good estimates of the package loads at each of the 90 US cities to be carried by the planes to the central city. We have good estimates for the operating capabilities and costs for the planes. We have time windows at each of the cities where the planes must arrive. The question is, which planes should go to which cities to carry all the loads, meet all the limitations and requirements, and minimize the total cost. If we can't guarantee to minimize the total cost to the last fraction of a penny, then get the total down as far as is reasonably possible and also have a lower bound number the total must be greater than or equal to and where the total is for practical terms close to that lower bound.
So, these three are all problems in planning. Really, compared with the block stacking in the OP, none of the three problems is trivial. It turns out that there is at least one polynomial algorithm for the first two problems, but no doubt even simple versions of the third problem are in NP-complete.
Lesson: We have long known that planning is non-trivial.