当前位置：和泉文库 > 计算机 > 《Artificial Intelligence：A Modern Approach》教学资源（教材，英文版）Part IV Planning 11 Planning

《Artificial Intelligence：A Modern Approach》教学资源（教材，英文版）Part IV Planning 11 Planning

文件格式：PDF，文件大小：325.05KB，售价：11.92元

文档详细内容（约42页）

380 Chapter 11. Planning Init(At(C1, SFO) ∧ At(C2, JFK) ∧ At(P1, SFO) ∧ At(P2, JFK) ∧ Cargo(C1) ∧ Cargo(C2) ∧ Plane(P1) ∧ Plane(P2) ∧ Airport(JFK) ∧ Airport(SFO)) Goal(At(C1, JFK) ∧ At(C2, SFO)) Action(Load(c, p, a), PRECOND: At(c, a) ∧ At(p, a) ∧ Cargo(c) ∧ Plane(p) ∧ Airport(a) EFFECT: ¬ At(c, a) ∧ In(c, p)) Action(Unload(c, p, a), PRECOND: In(c, p) ∧ At(p, a) ∧ Cargo(c) ∧ Plane(p) ∧ Airport(a) EFFECT: At(c, a) ∧ ¬ In(c, p)) Action(Fly(p, from, to), PRECOND: At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to) EFFECT: ¬ At(p, from) ∧ At(p, to)) Figure 11.2 A STRIPS problem involving transportation of air cargo between airports. The STRIPS and ADL notations are adequate for many real domains. The subsections that follow show some simple examples. There are still some significant restrictions, however. The most obvious is that they cannot represent in a natural way the ramifications of actions. For example, if there are people, packages, or dust motes in the airplane, then they too change location when the plane flies. We can represent these changes as the direct effects of flying, whereas it seems more natural to represent the location of the plane’s contents as a logical consequence of the location of the plane. We will see more examples of such STATE CONSTRAINTS state constraints in Section 11.5. Classical planning systems do not even attempt to address the qualification problem: the problem of unrepresented circumstances that could cause an action to fail. We will see how to address qualifications in Chapter 12. Example: Air cargo transport Figure 11.2 shows an air cargo transport problem involving loading and unloading cargo onto and off of planes and flying it from place to place. The problem can be defined with three actions: Load, Unload, and Fly. The actions affect two predicates: In(c, p) means that cargo c is inside plane p, and At(x, a) means that object x (either plane or cargo) is at airport a. Note that cargo is not At anywhere when it is In a plane, so At really means “available for use at a given location.” It takes some experience with action definitions to handle such details consistently. The following plan is a solution to the problem: [Load(C1, P1, SFO), Fly(P1, SFO, JFK), Load(C2, P2, JFK), Fly(P2, JFK, SFO)] . Our representation is pure STRIPS. In particular, it allows a plane to fly to and from the same airport. Inequality literals in ADL could prevent this

Section 11.1. The Planning Problem 381 Example: The spare tire problem Consider the problem of changing a flat tire. More precisely, the goal is to have a good spare tire properly mounted onto the car’s axle, where the initial state has a flat tire on the axle and a good spare tire in the trunk. To keep it simple, our version of the problem is a very abstract one, with no sticky lug nuts or other complications. There are just four actions: removing the spare from the trunk, removing the flat tire from the axle, putting the spare on the axle, and leaving the car unattended overnight. We assume that the car is in a particularly bad neighborhood, so that the effect of leaving it overnight is that the tires disappear. The ADL description of the problem is shown in Figure 11.3. Notice that it is purely propositional. It goes beyond STRIPS in that it uses a negated precondition, ¬At(Flat, Axle), for the PutOn(Spare, Axle) action. This could be avoided by using Clear (Axle) instead, as we will see in the next example. Init(At(Flat, Axle) ∧ At(Spare, Trunk )) Goal(At(Spare, Axle)) Action(Remove(Spare, Trunk ), PRECOND: At(Spare, Trunk ) EFFECT: ¬ At(Spare, Trunk ) ∧ At(Spare, Ground)) Action(Remove(Flat, Axle), PRECOND: At(Flat, Axle) EFFECT: ¬ At(Flat, Axle) ∧ At(Flat, Ground)) Action(PutOn(Spare, Axle), PRECOND: At(Spare, Ground) ∧ ¬ At(Flat, Axle) EFFECT: ¬ At(Spare, Ground) ∧ At(Spare, Axle)) Action(LeaveOvernight, PRECOND: EFFECT: ¬ At(Spare, Ground) ∧ ¬ At(Spare, Axle) ∧ ¬ At(Spare, Trunk ) ∧ ¬ At(Flat, Ground) ∧ ¬ At(Flat, Axle)) Figure 11.3 The simple spare tire problem. Example: The blocks world BLOCKS WORLD One of the most famous planning domains is known as the blocks world. This domain consists of a set of cube-shaped blocks sitting on a table.3 The blocks can be stacked, but only one block can fit directly on top of another. A robot arm can pick up a block and move it to another position, either on the table or on top of another block. The arm can pick up only one block at a time, so it cannot pick up a block that has another one on it. The goal will always be to build one or more stacks of blocks, specified in terms of what blocks are on top of what other blocks. For example, a goal might be to get block A on B and block C on D. 3 The blocks world used in planning research is much simpler than SHRDLU’s version, shown on page 20

382 Chapter 11.Planning We will use On(to indicate that m the top of: the top ofy will be love(b,r,y) no oth er ble e on it On(,or,al tively, precona s in AD We can stay within the STRIPS language,however,by introducing a new predicate,Clear(),that is true when nothing ison The action Move moves a block from to y if b hband y are clear.After the move is made,x is clear but y is not.A formal description of Move in STRIPS is Action(Moue(b.x.u)」 PRECOND:On(b,)A Clear(b)A Clear(y), EFFECT:On(b,y)A Clear()AOn(b,)AClear(y)) is the table.When tion has effect Clear(Table tion C able ome To fx this to be cl to move ,we do two things.First,we introd luce another action to om the EFFECT:On(b,Table)AClear(r)AOn(b,)). Second,we take the interpretation of Clear(b)to be"there is a clear space on b to hold a block."Under this interpretation,Clear(Table)will always be true.The only problem is that nothing prevents the planner from using Move(b.,Table)instead of MoveToTable(b,) We could live with this problem-it will lead to a larger-than-necessary search space,but will not lead to incorrect answers-or we could introduce the predicate Block and add Block(b)A Block(y)to the precondition of Move. Finally,there is the problem of spurious actions such as Move(B,C.C),which should be a no-op,but which has contradictory effects.It is common to ignore such problems. because they seldom cause incorrect plans to be produced.The correct approach is add in- equality preconditions as shown in Figure 11.4. 11.2 PLANNING WITH STATE-SPACE SEARCH Now we tu our to planning algorithms The most straightforward approach is to state-space searc a planning problem specify btprendiiondeffetiposirrci se Because the des either forward from the initial state or backward from the goal,as shown in Figure 11.5.We can also use the explicit action and goal representations to derive effective heuristics automatically. Forward state-space search Planning with forward state-space search is similar to the problem-solving approach of Chap ter 3.It is sometimes called pr essionplanning.because it moves in the forward direction

382 Chapter 11. Planning We will use On(b, x) to indicate that block b is on x, where x is either another block or the table. The action for moving block b from the top of x to the top of y will be Move(b, x, y). Now, one of the preconditions on moving b is that no other block be on it. In first-order logic, this would be ¬∃ x On(x, b) or, alternatively, ∀ x ¬On(x, b). These could be stated as preconditions in ADL. We can stay within the STRIPS language, however, by introducing a new predicate, Clear(x), that is true when nothing is on x. The action Move moves a block b from x to y if both b and y are clear. After the move is made, x is clear but y is not. A formal description of Move in STRIPS is Action(Move(b, x, y), PRECOND:On(b, x) ∧ Clear(b) ∧ Clear(y), EFFECT:On(b, y) ∧ Clear(x) ∧ ¬On(b, x) ∧ ¬Clear(y)) . Unfortunately, this action does not maintain Clear properly when x or y is the table. When x = Table, this action has the effect Clear(Table), but the table should not become clear, and when y = Table, it has the precondition Clear(Table), but the table does not have to be clear to move a block onto it. To fix this, we do two things. First, we introduce another action to move a block b from x to the table: Action(MoveToTable(b, x), PRECOND:On(b, x) ∧ Clear(b)), EFFECT:On(b, Table) ∧ Clear(x) ∧ ¬On(b, x)) . Second, we take the interpretation of Clear(b) to be “there is a clear space on b to hold a block.” Under this interpretation, Clear(Table) will always be true. The only problem is that nothing prevents the planner from using Move(b, x, Table) instead of MoveToTable(b, x). We could live with this problem—it will lead to a larger-than-necessary search space, but will not lead to incorrect answers—or we could introduce the predicate Block and add Block(b)∧ Block(y) to the precondition of Move. Finally, there is the problem of spurious actions such as Move(B, C, C), which should be a no-op, but which has contradictory effects. It is common to ignore such problems, because they seldom cause incorrect plans to be produced. The correct approach is add inequality preconditions as shown in Figure 11.4. 11.2 PLANNING WITH STATE-SPACE SEARCH Now we turn our attention to planning algorithms. The most straightforward approach is to use state-space search. Because the descriptions of actions in a planning problem specify both preconditions and effects, it is possible to search in either direction: either forward from the initial state or backward from the goal, as shown in Figure 11.5. We can also use the explicit action and goal representations to derive effective heuristics automatically. Forward state-space search Planning with forward state-space search is similar to the problem-solving approach of ChapPROGRESSION ter 3. It is sometimes called progression planning, because it moves in the forward direction

384 Chapter 11.Planning ulting from an action ed by ad (i t nrst-orde case.we must apply the unifier from the preconditions to the effect literals.)Note that a single succ function works for all planning problems-a consequence of using an explicit action representation The goal test checks whether the state satisfies the goal of the planning problem. .The step cost ofeach action is typically 1.Although it would be easy to allow different costs for different actions,this is seldom done by STRIPS planners. problem is finit A pianingalg rom th days of planning re assumed that for und1998) state-spa is n come up 11.1.First,f ddre problen app m each approa a go n ar cargo problem with nas d 2 the cargo at airpor airport e Is mp pro ny the p the cargo But finding the solutio ecause the average b ng facto each of the scan ny to othe er airports,and each of the 200 packages eithe paded (if it is loaded),or ade any plane at its airport (if it is unloaded).Or average,let's say the re are about 1000 possible actions,so the search tree up to the dept the obviouss has about 100 nodes.It is clear that a very accurate heuristic will be ed to ma this kind of search efficient.We will discuss some possible heuristics after looking at backward search Backward state-space search Backward state-space search was described briefy as part of bidirectional search in Chapter 3 We noted there that backward search can be difficult to implement when the goal states are described by a set of constraints rather than being listed explicitly.In particular,it is not always obvious how to generate a description of the possible predecesse ofthesctofgal states.We will sce that the STRIPS representation makes this quite easy be ause sets of states an be described by the literals that must be true in those states The main adya of backward search is that it allows us to consider only relevant actions al For ample the al in our 10-airport ai cargo pro ble is to hav e20 es of arg re pr iselv At(C1.B)A At(C2.B)A...A At(C20.B) Now consider the coniunct At(C B)Working backwards.we can seek actions that have this as an effect.There is only one:Unload(Cp,B),where plane p is unspecified

384 Chapter 11. Planning • The actions that are applicable to a state are all those whose preconditions are satisfied. The successor state resulting from an action is generated by adding the positive effect literals and deleting the negative effect literals. (In the first-order case, we must apply the unifier from the preconditions to the effect literals.) Note that a single successor function works for all planning problems—a consequence of using an explicit action representation. • The goal test checks whether the state satisfies the goal of the planning problem. • The step cost of each action is typically 1. Although it would be easy to allow different costs for different actions, this is seldom done by STRIPS planners. Recall that, in the absence of function symbols, the state space of a planning problem is finite. Therefore, any graph search algorithm that is complete—for example, A ∗—will be a complete planning algorithm. From the earliest days of planning research (around 1961) until recently (around 1998) it was assumed that forward state-space search was too inefficient to be practical. It is not hard to come up with reasons why—just refer back to the start of Section 11.1. First, forward search does not address the irrelevant action problem—all applicable actions are considered from each state. Second, the approach quickly bogs down without a good heuristic. Consider an air cargo problem with 10 airports, where each airport has 5 planes and 20 pieces of cargo. The goal is to move all the cargo at airport A to airport B. There is a simple solution to the problem: load the 20 pieces of cargo into one of the planes at A, fly the plane to B, and unload the cargo. But finding the solution can be difficult because the average branching factor is huge: each of the 50 planes can fly to 9 other airports, and each of the 200 packages can be either unloaded (if it is loaded), or loaded into any plane at its airport (if it is unloaded). On average, let’s say there are about 1000 possible actions, so the search tree up to the depth of the obvious solution has about 100041 nodes. It is clear that a very accurate heuristic will be needed to make this kind of search efficient. We will discuss some possible heuristics after looking at backward search. Backward state-space search Backward state-space search was described briefly as part of bidirectionalsearch in Chapter 3. We noted there that backward search can be difficult to implement when the goal states are described by a set of constraints rather than being listed explicitly. In particular, it is not always obvious how to generate a description of the possible predecessors of the set of goal states. We will see that the STRIPS representation makes this quite easy because sets of states can be described by the literals that must be true in those states. RELEVANCE The main advantage of backward search is that it allows us to consider only relevant actions. An action is relevant to a conjunctive goal if it achieves one of the conjuncts of the goal. For example, the goal in our 10-airport air cargo problem is to have 20 pieces of cargo at airport B, or more precisely, At(C1, B) ∧ At(C2, B) ∧ . . . ∧ At(C20, B) . Now consider the conjunct At(C1, B). Working backwards, we can seek actions that have this as an effect. There is only one: Unload(C1, p, B), where plane p is unspecified

点击进入文档下载页（PDF格式）

共42页，可试读14页，点击继续阅读 ↓↓

您可能感兴趣的文档

点击购买下载（PDF）

下载及服务说明

购买前请先查看本文档预览页，确认内容后再进行支付；
如遇文件无法下载、无法访问或其它任何问题，可发送电子邮件反馈，核实后将进行文件补发或退款等其它相关操作；
邮箱：

文档浏览记录