6 ms·
Sussman anomaly
- nerdponx 9y agoI 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.
- SiempreViernes 9y agoThis 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.
- ryanianian 9y ago> 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.
- canjobear 9y agoOr it will just get better and better at working with continuous approximations to discrete problems.
- ryanianian 9y agoMy 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.
- maxander 9y agoA 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.
- primaryobjects 9y agoThis is a classic AI planning problem, solvable with STRIPS. Solution to the Sussman Anomaly https://github.com/primaryobjects/strips/blob/master/Readme.md#sussman-anomaly-solution https://github.com/primaryobjects/strips/blob/master/Readme....
- RyanShook 9y agoAre there any unsolved/unsolvable anomalies similar to this one?
- graycat 9y agoI'd say that all the NP-complete problems are of this kind and much worse.
- jerf 9y agoI'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.
- FabHK 9y agoMoravec'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. https://en.wikipedia.org/wiki/Moravec%27s_paradox 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 https://www.youtube.com/watch?v=g0TaYhjpOfo
- deleted 9y ago[deleted]
- phkahler 9y agoThe 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.
- crowbahr 9y agoYes, 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.
- hood_syntax 9y agoI 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.
- CarolineW 9y agoThat feels trivially like saying: "If you can identify the crucial part of the challenge then it's easy." The problem then becomes one of identifying the crucial part of the challenge. If framed that way, your comment doesn't really help.
- totalZero 9y agoIt's more like saying you need to use inference to identify constrained parts of the solution.
- graycat 9y agoEarly 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.
- lisper 9y agoThis problem was definitively solved by David Chapman in his 1985 masters thesis: https://dspace.mit.edu/handle/1721.1/15119 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.
- federicosan 9y agoI 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.
- natch 9y agoNaive question: What is the problem with simply detecting dependencies amongst the goals, and then proceeding to tackle the dependencies in order?
- ColinWright 9y agoThe 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?
- mojuba 9y agoI think the confusion comes from the formulation of the problem itself. It is incomplete. Here is a task that I think is solvable: - C should be on the ground; B should be on top of C; A should be on top of B
- ColinWright 9y agoBut 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."
- m3kw9 9y agoSeem 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.
- ColinWright 9y ago> 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.
- krick 9y agoIt 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?
- deleted 9y ago[deleted]
- Chris2048 9y agoI 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"...