![]() For example, the predecessor description in the preceding paragraph is satisfied by the initial state. In the first-order logic, satisfaction might require a substitution for variables in the predecessor description. Termination occurs when a predecessor description is generated which is satisfied by the initial state of the planning problem. Each precondition literal of A is added, unless it already appears.Īny of the standard search algorithms can be used to carry out the search. Any positive effects of A which appear in G are deleted. The corresponding predecessor is constructed as follows: Given a goal description G, let A be an action which is relevant and consistent. Given definitions of relevance and consistency, we can now describe the general process of constructing predecessors for backward search. For example, the action load (C 2, p) would not be consistent with the current goal, because it would negate the literal At (C 2, B) (verify). An action which satisfies this restriction is called consistent. In addition to insisting that actions achieve some desired literal, we must insist that the actions do not undo any desired literals. Moreover, the sub-goal At (C 1, B) should not be true in the predecessor state which will no doubt be a goal but not relevant one (justify). Therefore, any predecessor state must include these preconditions: In (C 1, p) ˄ At (p, B) as sub-goals. The action will work only if its preconditions are satisfied. The relevant action UNLOAD (C 1 ‘ p, B) achieves the first conjunct. We have the goalĪt (C 1 B) ˄ At (C 2 B) ˄…. To see how does it work, once again consider the air cargo example. The principal question in regression planning is: what are the states from which applying a given action leads to the goal? Computing the description of these states is called regressing the goal through the action. Searching backwards is also called regression planning. Hence backward search is more efficient than forward searching. For example, our air cargo problem has about 1000 actions leading forward from the initial state, but only 20 actions working backward from the goal. This restriction to relevant actions only means that backward search often has a much lower branching factor than forward search. If a solution exists, it should be found by a backward search which allows only relevant action. A backward search which allows irrelevant actions will still be complete, but it will be much less efficient. ![]() For example, we can fly an empty plane from Mumbai to Chennai this action reaches a goal state from a predecessor state in which the plane is at Mumbai and all the goal conjuncts are satisfied. We may note that there are many irrelevant actions which can also lead to a goal state. ![]() It is thus clear that a very accurate heuristic will be needed to make this kind of search efficient. 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 1000 nodes. 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). 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. ![]() The goal is to move all the cargo at airport A to airport B. Consider for example, an air cargo problem with 10 airports, where each airport has 5 planes and 20 pieces of cargo. Mainly, this is because of a big branching factor since forward search does not address only relevant actions, (all applicable actions are considered). From the early days of planning research it is known that forward state-space search is too inefficient to be practical.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |