Even for three blocks, stacking two counterbalanced blocks on top of another block can give an overhang of 1, while the overhang in the simple ideal case is at most 11 / 12. Multi-wide stacks using counterbalancing can give larger overhangs than a single width stack. Place N increases, meaning that it is possible to achieve any arbitrarily large overhang, with sufficient blocks.Ĭomparison of the solutions to the single-wide (top) and multi-wide (bottom) block-stacking problem with three blocks We first union the add and world state lists to get:Īnd then subtract the delete list, to get:The block-stacking problem is the following puzzle: Imaginging that we have applied pickup(a), we can now go on to apply stack(a, b). In order to complete this task, we must make holding(a) a goal, which is satisfied by applying the pickup(a) operator. We first inspect the precondition list, but there's a problem, as the arm is not currently holding the block a. So, with our example, we try to apply stack(a, b) to the initial state: That's exactly what the apply/3 predicate did in my initial post in this thread. To apply an operator, you must first make sure that the precondition list is a subset of the current world condition (otherwise it's impossible to apply it to the current world state, it wouldn't make sense to try and stack two blocks which are at the bottom of stacks, for instance) then you merge the add list to the current world state and remove the delete list, resulting in your new world state. So, we have three lists, precondition, add and delete, which are, and respectively. After the operator has been applied, one block (a) will be on another (b) and b will no longer be clear. This forms the precondition list for the operator. To stack two blocks the block that will be at the bottom of the stack must be initially clear, and the arm must be already holding the block that will be on top. We need to think of what must be true of the world prior to the application of the operator, what will be true after it's application, and what will no longer be true. Let's define a simple version of stack(a, b). The state is affected by the add and delete lists of the operators. and X will be instanced with a list of operators needed to be applied to the initial state to have it result in the goal state. You also need a goal state, which we will define as such:Īt run time, you can call ?- pln(,, X). This list would be a parameter to your top level planning predicate, let's call it pln for short. Start off with the canonical world state, all blocks are on the table, with none stacked: Your operators each have an add and delete list which modifies the world state list via the apply predicate when they are applied. Basically, your world state is kept in a Prolog list. Yes, I kind of hinted at it in my post (not wanting to spoil the problem for you too much). I'm a bit rusty with Prolog, but if you still need help then ask. precondition: ae (armEmpty), on(x, table), clear(x).All blocks are the same size, and you can't pick up a block that's underneath another block. Block world problem code how to#The program then works out how to get from the initial state to the goal state. I think he means that game that gets distributed as "Mahjong" even though it's nothing to do with the actual real-world game of that name (except for the appearance of the "tiles").No, he means the blocks world problem: you start with an arbitrary initial state, and have an arbitrary goal state. You can do this by working backwards from the goal state. You then need to find a way of taking a start state and a goal state and applying a set of operators to the initial state to result in the goal state. It's simple to write a predicate that applies an operator to the current state:Īpply(Rule, State, NewState) :- p_op(Rule, Pre, Add, Del), subset(Pre, State), union(State, Add, TState), subtract(Del, TState, NewState). This takes two blocks and stacks them on top of one another, providing that they are both "clear" (it's a simplified world representation, so don't blame me if there's faults in it :-)). These operators have a list of preconditions that must be true of the world before they can be applied, an additions list which adds facts to the world after they have been applied, and a deletion list which deletes facts from the world after they have been applied. If it's the latter, then that is quite easy (I'll show you a simple STRIPS like system):ĭefine some operators. Do you wish to make a game, or do you wish to make a planning system which will take an initial state and a goal state and generate a plan to move the blocks so that they are in the goal state?
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |