Sussman anomaly
en.wikipedia.org
en.wikipedia.org
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:
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?