Program 14.12 Testing the depth-first planner Testing and data test-plan (Name, Plan) initial_state (Name,I), final state (Name,F), transform(I,F,Plan). suggest(to_block(X,Y,Z), State) member(on(X,Z),State), block(2). suggest (to-place(X,Y,Z), State) member(on(X,Z),State), place(2). choose_action(Action, State1, State2) legal_action(Action, Statel). A sim- ple definition suffices to produce intelligent behavior in our example problem: choose_action(Action, Statei, State2) - suggest (Action, State2), legal_action(Action, Statel). The predicate legal action can be re- placed by a predicate choose_action(Action, State1, State2). It is easy to incorporate a little more intelligence by first trying to achieve one of the goal states. After that, block b is moved to q, block a is moved to p and b, and after 20 more random moves, the final configuration is reached. The first plan it produces is horrendous, however: Program 14.11 successfully solves the simple problem given as Pro- gram 14.12. For each, the conditions for which it is legal must be specified, and a method given for updating the state as a result of performing the action. There are two possible actions, moving to a block and moving to a place. ![]() Program 14.11 A depth-first planner The nondeterministic algorithm used by the planner is given by the recursive clause of transform/4 in the program: While the desired state is not reached, find a legal action, update the current state, check that it has not been visited before. substitute (X,Y,Xs, Ys) - See Exercise 3.3(i). update(to-place(X,Y,Z), State, Statel) substitute (on (X,Y),on(X,2), State, Statel). update(to_block(X,Y,Z),State, Statel) substitute (on(X,Y),on(X,Z),State, Statel). clear (X,State) - not member(on(A,X), State). legal_action(to_block(Block1,Y,Block), State) on (Block1, y, State), clear(Block1, State), block (Block2), Block1 # Block2, clear(Block2, State). legal_action(to-place (Block,Y,Place), State) - on(Block, Y, State), clear (Block, State), place(Place), clear (Place, State). transform(State1, State2, Visited, ) - legal_action(Action, Statel), update (Action, State1, State), not member (State, Visited), transform(State, State2, [State|Visited), Actions). transform (State1, State2,Plan) - transform(State1, State2, ,Plan). Transform(State1, State2,Plan) Plan is a plan of actions to transform Statel into State2. The predicates clear/2 and on/3 in Pro- gram 14.11 take advantage of this representation. The state descriptions allow easy testing of whether a block or place X is clear in a given state by checking that there is no relation of the form on (A,X). The state descriptions are ordered in the sense that the on relation for a precedes that of b, which precedes the on relation for c. For example, the initial and final states in Figure 14.4 are, respectively, and [on(a,b),on(b, c),on(c,r)). They represent the facts that are true in the state. States are represented by a list of relations of the form on (X,Y), where X is a block and Y is a block or place. ![]() A plan of actions, Plan, is produced that transforms State1 into State2 when executed. The top-level procedure of Program 14.11 solving the problem is transform (Statei, State2,Plan). For an action to succeed, the top of the moved block must be clear, and also the place or block to which it is being moved must be clear. The actions allowed are moving a block from the top of a block to a place and moving a block from one block to another. There are three blocks, a, b, and c, and three places, p, q, and r. Figure 14.4 gives the initial state and the desired final state of a blocks world problem. The problem is to form a plan in the blocks world, that is, to specify a sequence of actions for restacking blocks to achieve a particular con- figuration. It combines the two extensions mentioned before – keeping an accumulator of what has been traversed, and computing a path. The program is written nondeterministically, essen- tially performing a depth-first search. This section is completed with a program for building simple plans in the blocks world. This is discussed further in Section 16.2. To do so, breadth-first search is necessary. A a b с b р a r р q Figure 14.4 Initial and final states of a blocks world problem The program is not guaranteed to reach every node of an infinite graph.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |