4 ms·
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
by m3kw9 9y ago
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.
- 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?
- jonbarker 9y agoThis is not solvable without moving the blocks into more than two positions.