AFAICT (I've been out of the field for a long time now) Chapman's work has been largely forgotten, which is a shame because it's brilliant IMHO. TWEAK is (or at least ought to be considered) the special relativity of classical planning.
Re:Sussman anomaly
by nerdponx on Monday January 15, 2018 @10:10AM
(#16150938)
I wonder if there are similar "anomalies" to be found when training statistical/machine-learning models on top of other statistical/machine-learning models. That basically amounts to greedy search: optimize step 1, then optimize step 2 conditional on step 1 already being optimized. The "right way" would be to train both modeling stages simultaneously, but in many cases that's either mathematically or computationally intractable.
This anomaly seems to be a name for when your program gets stuck in a local minima that is particular to rule based reasoning systems.
Machine learning is mostly about numerical optimization/exploration in high dimensions, so they can't really get stuck in the same way; your oscillating code could converge after a long time, but you probably need to solve the halting problem to know.
Re:Sussman anomaly
by ryanianian on Monday January 15, 2018 @12:39PM
(#16151998)
> Machine learning is mostly about numerical optimization/exploration in high dimensions
That may be true right now, but eventually for ML to be "true AI" it will have to move to discrete optimization/exploration as opposed to (relatively) continuous problems like I think you're describing. This "anomaly" exists in the discrete space. The below conversation threads explore this better but with different words.
Re:Sussman anomaly
by ryanianian on Tuesday January 16, 2018 @10:54AM
(#16159052)
My intuition is that this is how the human brain works, but I think we'd be missing out on a big opportunity if we limit computers to this. A continuous solution to a discrete problem may hugely under-perform the truly optimized discrete solution.
Re:Sussman anomaly
by maxander on Monday January 15, 2018 @02:17PM
(#16152687)
A great deal of research was done (and is still being done) in discrete-reasoning AI; aside from a few successful applications (e.g., military logistics,) very little ever came of it, at least in the direction of "general intelligence."
Our intuitions about how our minds work are typically really bad, which makes it difficult to see what the needed techniques are to replicate them.
Re:Sussman anomaly
by jerf on Monday January 15, 2018 @11:07AM
(#16151307)
I'd imagine it's solvable by just about everything. This is one of those cases where the core problem isn't that the problem is hard, it is that it is so easy that it is a challenge to get humans to even perceive it as a problem on such a small scale. Any planning system will hit something like this all but immediately.
I'd say a lot of the earliest AI optimism was a failure to understand just how hard things that in the simplest case are so simple we don't even perceive them as problems in the first place. For a much more complicated example, I doubt anyone in 1970 would imagine that in 2018 we're still trying to get robots to walk from here to there. (Yes, lots of progress has been made, but it's still very much cutting edge, a research project, and a bespoke one-off effort each time, not a "Oh, I'll just swing on down to the robot store and pick up a walking chassis".) We don't see it as a challenge because for our conscious minds, by the time we're old enough to be doing robotics research, it's zero cognitive effort for us.
Re:Sussman anomaly
by FabHK on Monday January 15, 2018 @04:30PM
(#16153620)
Moravec's paradox - stuff we thought is hard (chess, derivatives) is easy, while stuff we think is easy (face recognition, getting out of a car, opening a door) is really hard.
Re:Sussman anomaly
by lloeki on Monday January 15, 2018 @05:03PM
(#16153834)
To be fair, it takes us humans a solid couple of years of continuous training to make sense of our sensory inputs and get accustomed to our limbs enough to begin doing anything significant with them, so I am regularly flabbergasted at the expectations we place in our lowly contraptions to outdo us by two to three orders of magnitude.
Re:Sussman anomaly
by Frqy3 on Monday January 15, 2018 @09:55PM
(#16155435)
Humans have had millions of years of system level optimisation (evolution) which then only needs a couple of additional years to train the wetware to operate the system for daily activity.
Chess has only been around a mere 1,500 years and has had an evolutionary impact on only a very minute portion of the population. Hence it takes a few additional years to specialise a human for optimal chess performance.
Re:Sussman anomaly
by mannykannot on Monday January 15, 2018 @12:19PM
(#16151831)
This solves the problem by searching the graph of reachable states (and presumably doing cycle detection, at least in depth-first mode), which avoids the problem of picking an unsuitable sub-goal by considering all possible ones. While this is a perfectly good solution, it doesn't seem to throw much light on how human intelligence works. A person is likely to notice, for example, that extending any stack that does not have C on the bottom is not helpful, without mentally running through all possibilities, but just on the basis that it will have to be torn down at some point, to move the bottom block to where it belongs.
Of course human intelligence also stumbles on planing problems of true complexity. So it is still possible that human intelligence does something like a naive graph search, and this is good enough in the common case.
Re:Sussman anomaly
by mannykannot on Monday January 15, 2018 @03:49PM
(#16153318)
I do not think naive search would give rise to the sort of reasoning that I posit in my initial post, even as a post-facto rationalization rather than as part of actually solving the problem.
Re:Sussman anomaly
by ColinWright on Monday January 15, 2018 @04:04PM
(#16153426)
The goals here are "on(A,B)" and "on(B,C)". Clearly these are not independent.
The problem is that neither can be done before the other. If you start on one, it blocks the other. I'd've thought this was clear from the article, but since you ask the question I assume it isn't. That being the case, what are you suggesting that isn't covered in the article?
Re:Sussman anomaly
by ColinWright on Monday January 15, 2018 @05:41PM
(#16154115)
But part of the point is that in real problems you state what you want, not realising that other things might be necessary. Here it turns out to be necessary that C is on the ground, but that is something that the system should be able to deduce from the goals given.
As I've said elsewhere, this is a minimal example of the kind of thing that can be required. This sort of thing can and does occur "in disguise" as a tiny, hidden sub-component of real problems, where you, the human, don't have the luxury of going "Oh, it's obvious what's wrong."
Re:Sussman anomaly
by phkahler on Monday January 15, 2018 @11:44AM
(#16151569)
The only reason this is a problem is if you try to achieve the stated conditions independently. If you envision the complete solution (a stack of blocks) you build it immediately by placing C then B then A.
This seems similar to how people tend to focus on short term goals at the expense of longer term ones. Similarly, it's hacking vs architecture in software. You can fail by doing to much of either one.
Re:Sussman anomaly
by crowbahr on Monday January 15, 2018 @12:07PM
(#16151747)
Yes, obviously you could give the program the goal of "Stack blocks in order A:B:C" but that's not the point of the conundrum here.
Imagine they are 30 different goals all of which need to be aligned in slightly odd ways to achieve the ultimate task. You're having to prioritize pieces in non-linear fashion to slowly build up the base as you're solving individual steps that seem entirely tangential to the overarching goal. You might have to take 4 or 5 steps back sometimes to achieve 1 step forward.
That's the problem here. It's not this simple 3 block solution: that's only used to get you to wrap your head around the simplest possible complexity.
Re:Sussman anomaly
by hood_syntax on Monday January 15, 2018 @12:15PM
(#16151810)
I feel like the goals are framed incorrectly relative to the context. What's most important is not that B is above C, and A is above B, but that C is on the bottom. If framed that way, you can work backwards from the base case.
Re:Sussman anomaly
by Chris2048 on Tuesday January 16, 2018 @05:57AM
(#16157267)
I believe a similar problem affects TDD, and in general any methodology that assumed that longer processes are modularisable into smaller problems.
Ask someone to TDD a Sudoku, where the simple rules have inter-dependency. You can write three tests:
1) each column contains numbers 1-9
2) each row contains numbers 1-9
3) each box/subgrid contains numbers 1-9
But the solution must pass all simultaneously. The usual "write test, pass test" loop entails writing two lots of useless code if you try passing one/two alone - "write test, pass test, throw away what you just wrote cause the real crux is interdependence"...
Re:Sussman anomaly
by graycat on Monday January 15, 2018 @12:02PM
(#16151723)
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.
Re:Sussman anomaly
by mannykannot on Monday January 15, 2018 @12:21PM
(#16151851)
None of your examples are nearly as simple as this one - that is its value. Also, considering how humans might approach the problem throws some light on how natural intelligence works.
Re:Sussman anomaly
by graycat on Monday January 15, 2018 @01:39PM
(#16152419)
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!
Re:Sussman anomaly
by jpfr on Thursday January 18, 2018 @03:05PM
(#16180819)
Convex optimization and its mixed-integer counterparts have developed amazing results. But not all planning problems fit this framework.
There is an entire community dealing with "AI planning". They try to find action-sequences leading to a desired outcome. Every action is defined by preconditions and effects. Most of the benchmark cannot even be sensibly formulated in terms of a mixed-integer optimization problem.
Re:Sussman anomaly
by federicosan on Monday January 15, 2018 @02:38PM
(#16152828)
I learned this while writing a planning research project for Udacity Artificial Intelligence course, the anomaly was really pointed out by Allen Brown one of Sussman's students.
Re:Sussman anomaly
by m3kw9 on Monday January 15, 2018 @04:33PM
(#16153642)
Seem like the issue arises from artificial constraints which seem to purposely create a problem. I.e If you can place the blocks all over the table, this issue would not arise. I don’t see why they need to put in a constraint where you can only place blocks in 2 locations.
Re:Sussman anomaly
by ColinWright on Monday January 15, 2018 @04:41PM
(#16153701)
> I don’t see why they need to put in a constraint where you can only place blocks in 2 locations.
There is no such constraint. The problem is easily solved by first putting C on the table, then putting B on C, then putting A on B.
However, in a non-interleaved solver it will look at the goals and try to achieve them. Here is some reasoning.
Let's do "on(B,C)" first.
Easy. Great. Now let's do "on(A,B)". Oh no! We have to undo our success with "on(B,C)" before we can start to make progress with "on(A,B)". That's annoying.
OK, instead let's try "on(A,B)".
To do this it will move C from A to the table, then move A onto B. Now it wants to solve "on(B,C)" but it can't do that because A is on B, preventing B from being moved. So, as it says in the article, it has to undo the achievement of "on(A,B)" in order to achieve "on(B,C)"
So it has to achieve a goal, then un-achieve it, then re-achieve it. The point of the anomaly is to recognise that in a non-interleaved solver this will sometimes be necessary.
And yes, wee can all see that this particular instance is easy to solve, but this kind of semi-deadlock occurs in disguise in much larger systems. The point of this particular construction is to highlight some of the otherwise non-obvious implicit interdependencies.
Re:Sussman anomaly
by krick on Monday January 15, 2018 @06:05PM
(#16154274)
It still doesn't seem any insightful to me. Either there is assumption that any sequence of subgoals can be achieved independently of each other or there isn't.
If there is such assumption then... well, I don't know why you even attempted to write a "generic problem-solver" that way, because it obviously isn't the case in the domain where this "anomaly" is presented.
If there's no such assumption, then (again, obviously) the problem itself isn't moving something on top of something, but rather to construct a finite (!) sequence of actions, that will satisfy all dependencies between the sub-sequences. "Planning algorithm" whatever it is just cannot start moving things unless it has constructed a complete plan of finite sequence of actions.
Sure, sometimes you deliberately write a program that doesn't make tree of all possible outcomes and just "acts" (because efficiency, memory constraints, etc.), but then you know beforehand that your program isn't really solving the problem for sure, it just happens so that your heuristic works. And if it doesn't work — it's a bad heuristic and you know you have to find a better one.
You wouldn't be surprised (and wouldn't call it an anomaly, for sure) if an algorithm that always greedily puts a smaller ring on top of next smaller one fails to move a Hanoy tower, would you?
https://dspace.mit.edu/handle/1721.1/15119
AFAICT (I've been out of the field for a long time now) Chapman's work has been largely forgotten, which is a shame because it's brilliant IMHO. TWEAK is (or at least ought to be considered) the special relativity of classical planning.
Machine learning is mostly about numerical optimization/exploration in high dimensions, so they can't really get stuck in the same way; your oscillating code could converge after a long time, but you probably need to solve the halting problem to know.
That may be true right now, but eventually for ML to be "true AI" it will have to move to discrete optimization/exploration as opposed to (relatively) continuous problems like I think you're describing. This "anomaly" exists in the discrete space. The below conversation threads explore this better but with different words.
Our intuitions about how our minds work are typically really bad, which makes it difficult to see what the needed techniques are to replicate them.
Solution to the Sussman Anomaly
https://github.com/primaryobjects/strips/blob/master/Readme....
I'd say a lot of the earliest AI optimism was a failure to understand just how hard things that in the simplest case are so simple we don't even perceive them as problems in the first place. For a much more complicated example, I doubt anyone in 1970 would imagine that in 2018 we're still trying to get robots to walk from here to there. (Yes, lots of progress has been made, but it's still very much cutting edge, a research project, and a bespoke one-off effort each time, not a "Oh, I'll just swing on down to the robot store and pick up a walking chassis".) We don't see it as a challenge because for our conscious minds, by the time we're old enough to be doing robotics research, it's zero cognitive effort for us.
https://en.wikipedia.org/wiki/Moravec%27s_paradox
One of my favourite videos is this compilation of robots falling (failing) during the simplest tasks at the 2015 DARPA challenge:
https://www.youtube.com/watch?v=g0TaYhjpOfo
Chess has only been around a mere 1,500 years and has had an evolutionary impact on only a very minute portion of the population. Hence it takes a few additional years to specialise a human for optimal chess performance.
The problem is that neither can be done before the other. If you start on one, it blocks the other. I'd've thought this was clear from the article, but since you ask the question I assume it isn't. That being the case, what are you suggesting that isn't covered in the article?
- C should be on the ground; B should be on top of C; A should be on top of B
As I've said elsewhere, this is a minimal example of the kind of thing that can be required. This sort of thing can and does occur "in disguise" as a tiny, hidden sub-component of real problems, where you, the human, don't have the luxury of going "Oh, it's obvious what's wrong."
This seems similar to how people tend to focus on short term goals at the expense of longer term ones. Similarly, it's hacking vs architecture in software. You can fail by doing to much of either one.
Imagine they are 30 different goals all of which need to be aligned in slightly odd ways to achieve the ultimate task. You're having to prioritize pieces in non-linear fashion to slowly build up the base as you're solving individual steps that seem entirely tangential to the overarching goal. You might have to take 4 or 5 steps back sometimes to achieve 1 step forward.
That's the problem here. It's not this simple 3 block solution: that's only used to get you to wrap your head around the simplest possible complexity.
The problem then becomes one of identifying the crucial part of the challenge. If framed that way, your comment doesn't really help.
Ask someone to TDD a Sudoku, where the simple rules have inter-dependency. You can write three tests:
1) each column contains numbers 1-9
2) each row contains numbers 1-9
3) each box/subgrid contains numbers 1-9
But the solution must pass all simultaneously. The usual "write test, pass test" loop entails writing two lots of useless code if you try passing one/two alone - "write test, pass test, throw away what you just wrote cause the real crux is interdependence"...
> 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.
https://news.ycombinator.com/item?id=16152419
just below.
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!
There is an entire community dealing with "AI planning". They try to find action-sequences leading to a desired outcome. Every action is defined by preconditions and effects. Most of the benchmark cannot even be sensibly formulated in terms of a mixed-integer optimization problem.
This seminal paper is a good entry-point to the field: http://www.jair.org/media/1705/live-1705-2731-jair.pdf
A bit of background research would do good before calling the problem at the center of a very active community "childish".
There is no such constraint. The problem is easily solved by first putting C on the table, then putting B on C, then putting A on B.
However, in a non-interleaved solver it will look at the goals and try to achieve them. Here is some reasoning.
Let's do "on(B,C)" first.
Easy. Great. Now let's do "on(A,B)". Oh no! We have to undo our success with "on(B,C)" before we can start to make progress with "on(A,B)". That's annoying.
OK, instead let's try "on(A,B)".
To do this it will move C from A to the table, then move A onto B. Now it wants to solve "on(B,C)" but it can't do that because A is on B, preventing B from being moved. So, as it says in the article, it has to undo the achievement of "on(A,B)" in order to achieve "on(B,C)"
So it has to achieve a goal, then un-achieve it, then re-achieve it. The point of the anomaly is to recognise that in a non-interleaved solver this will sometimes be necessary.
And yes, wee can all see that this particular instance is easy to solve, but this kind of semi-deadlock occurs in disguise in much larger systems. The point of this particular construction is to highlight some of the otherwise non-obvious implicit interdependencies.
If there is such assumption then... well, I don't know why you even attempted to write a "generic problem-solver" that way, because it obviously isn't the case in the domain where this "anomaly" is presented.
If there's no such assumption, then (again, obviously) the problem itself isn't moving something on top of something, but rather to construct a finite (!) sequence of actions, that will satisfy all dependencies between the sub-sequences. "Planning algorithm" whatever it is just cannot start moving things unless it has constructed a complete plan of finite sequence of actions.
Sure, sometimes you deliberately write a program that doesn't make tree of all possible outcomes and just "acts" (because efficiency, memory constraints, etc.), but then you know beforehand that your program isn't really solving the problem for sure, it just happens so that your heuristic works. And if it doesn't work — it's a bad heuristic and you know you have to find a better one.
You wouldn't be surprised (and wouldn't call it an anomaly, for sure) if an algorithm that always greedily puts a smaller ring on top of next smaller one fails to move a Hanoy tower, would you?