5 ms·

Early on the OP has in part > The problem was first identified by Sussman as a part of his PhD research. Sussman (and his supervisor, Marvin Minsky) believed t

Early on the OP has in part > 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.

qubyte 9y ago
In fairness, the thesis is dated 1975, and it remains a useful thought experiment due to its simplicity.
- graycat 9y ago
  1975? 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!

qubyte 9y ago

In fairness, the thesis is dated 1975, and it remains a useful thought experiment due to its simplicity.

graycat 9y ago
1975? 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!