%---------------------------------------------------------------------------- PLANNING %---------------------------------------------------------------------------- Planning and Problem Solving Many intelligent activities, including planning, may productively be viewed as problem solving. Thus much of what we discussed about problem solving is also applicable to planning. In particular, Means-Ends Analysis is a planning strategy too. %---------------------------------------------------------------------------- Planning and Acting AI theories of planning address complex issues such as interaction of planning with other activities such as acting, perceiving, monitoring, etc. We will discuss some of these interactions when we come to robotics. But note that an operator in planning corresponds to an possible action in the world. %---------------------------------------------------------------------------- Non-Linear Problems MEA is a control strategy useful largely for linear problems, where the agent has only one goal or its various goals are independent of one another. Non-linear problems are characterized by (i) multiple conjunctive goals, (ii) a set of operators such that the application of a sequence of operators for achieving one goal makes the achievement of another goal impossible. %---------------------------------------------------------------------------- Example of a Non-Linear Problems: --------- | A | --------- --------- --------- | C | | B | --------- --------- --------- --------- --------- | A | | B | | C | --------- --------- --------- ------------------------------- ----------------------------------- Initial state: (AND (ON C A) Goal state: (AND (ON A B) (ON A Table) (ON B C) (ON B Table)) (ON C Table) Operators: PUT Block-1 Block-2 Preconditions: (CLEARED-TOP Block-1) (CLEARED-TOP Block-2) Postconditions: (ON Block-1 Block-2) PUT Block-1 Table Preconditions: (CLEARED-TOP Block-1) Postconditions: (ON Block-1 Table) CLEAR-TOP Block-1 Preconditions: (ON Block2 Block1) Postconditions: (CLEARED-TOP Block-1) In the specification of these operators, Block-1 and Block-2 are variables (that can be bound to specific blocks in a given problem) To see the nature of non-linear problems, let us see what happens if we apply means-enads analysis to the above problem. Goal: (AND (ON A B) (ON B C) (ON C Table)) Assume that no ordering of the goals is known. Suppose that MEA (arbitrarily) starts with the goal of (ON A B). It may generate the plan ((PUT C Table) (CLEAR-TOP B) (PUT A B)) to achieve this goal. This would lead to the state (AND (ON A B)(ON C Table)). Now suppose MEA tries to achieve the goal (ON B C). It must undo the plan for achieving goal (ON A B). Now suppose that MEA starts with the goal of (ON B C) instead. It may generate the plan ((CLEAR-TOP C)(PUT B C)). This would lead to the state (AND (ON B C)(ON C A)(ON A Table)). Now when MEA tries to achieve goal (ON A B), it must undo the plan for achieving (ON B C). So, the goals and operators in this example are such that the plan (a sequence of operators) for achieving one goal interacts negatively with the other goal(s). This is an example of non-linear problems. %---------------------------------------------------------------------------- Least Commitment Strategy (or Partial Order Planning) NOAH (Sacerdoti 1975) Goal ordering is not done until absolutely necessary. NOAH's planning method: Assume that the problem is linear. ---> Use means-ends analysis for each goal independently | (without ordering of the goals) | Make partial plans for each goal | Criticize the plan to resolve interactions (if any) | Refine plan. --- Repeat So, NOAH uses CRITICS to monitor the planning process and accommodate interactions. NOAH knows of several different critics including the RESOLVE-CONFLICTS critic and the REMOVE-REDUNDANCY critic. %---------------------------------------------------------------------------- Example: The Ceiling and the Ladder Problem A robot needs to paint the ceiling and paint the ladder It has no a priori knowledge of the goal ordering. Initial State: (Next-to-Ladder) Goal State: (AND (Painted Ceiling)(Painted Ladder)) Operators: Climb-Up-Ladder: Preconditions: Next-To-Ladder, Dry-Ladder Postconditions: Next-To-Ceiling Climb-Down-Ladder: Preconditions: Next-To-Ceiling, Dry-Ladder Postconditions: Next-To-Ladder Paint-Ladder: Preconditions: Next-To-Ladder Postconditions: Painted-Ladder, NOT (Dry-Ladder) Paint-Ceiling: Preconditions: Next-To-Ceiling Postconditions: Painted-Ceiling, NOT (Dry-Ceiling) Step 1: LIST GOALS Painted-Ladder / \ S J S = Split; J = Join \ / Painted-Ceiling Step 2: MAKE PARTIAL PLANS (Post: (Pre: Painted-Ladder, Next-To-Ladder) NOT (Dry-Ladder) ---Paint-Ladder----------------------------------- / 1 \ S J \ 2 3 / ---Climb-Up-Ladder----------------Paint-Ceiling--- (Pre: (Post: (Pre: (Post: Next-to-Ladder, Next-To-Ceiling) Next-To-Ceiling) Painted-Ceiling, Dry-Ladder) NOT (Dry-Ceiling) Step 3: CRITICIZE (DETECT and RESOLVE CONFLICTS): Postcondition of Paint-Ladder (1) and precondition of Cimbu-Up-Ladder (2) are in conflict. This is found by matching the preconditions and postconditions in the partial plans for the different goals (Post: (Pre: Painted-Ladder, Next-To-Ladder) NOT (Dry-Ladder)) Paint-Ladder-----------------------------------J ^ 1 S |<---------------------------------------------^ \ 2 3 | ---Climb-Up-Ladder----------------Paint-Ceiling---> (Pre: (Post: (Pre: (Post: Next-to-Ladder, Next-To-Ceiling) Next-To-Ceiling) Painted-Ceiling, Dry-Ladder) NOT (Dry-Ceiling) Step 4: REFINE PLAN Postcondition of 3 does not match precondition of 1, so refine. (Pre: (Post: Next-To-Ceiling, (Post: (Pre: Painted-Ladder, Dry-Ladder Next-To-Ladder Next-To-Ladder) (NOT (Dry-Ladder)) Climb-Down-Ladder Paint-Ladder--->J ^ 4 1 |<---------------------------------------------^ 2 3 | S---Climb-Up-Ladder----------------Paint-Ceiling---> (Pre: (Post: (Pre: (Post: Next-to-Ladder, Next-To-Ceiling) Next-To-Ceiling) Painted-Ceiling, Dry-Ladder) NOT(Dry-Ceiling)) The result is a complete, linearized plan. %---------------------------------------------------------------------------- Discussion of NOAH: How does NOAH know (or infer) that the postcondition of 3 (which does not specify Next-to-Ceiling) matches the precondition of 2 specifies (Next-to Ceiling)? Similarly, how does it know that precondition of 1 (which specifies Dry-Ladder) matches the initial state (which does not specify Dry-Ladder)? This is very general problem in AI. One possible answer is to view each state as an assertion. Thus the initial state (Next-to-Ladder) really ``means'' that the assertion Robot(pos = Next-to-Ladder) is True. In addition, view the postconditions of operators as making some assertions True and making others False. Thus the postconditions (Painted-Ceiling) and (NOT(Dry-Ceiling)) really mean that the assertion Painted(Ceiling) is True but the assertion Dry(Ceiling) is Fales OPERATORS are defined by a set of preconditions a set of postconditions which contain assertions which become True (add-lists) and assertions which become Fales (delete-lists) In this view, the plan goes something like this: Initiat State Robot (pos = Next-to-Ladder) True Plan State 1 Robot (pos = Next-to-Ladder) is True Dry(Ladder) is True (no contradiction with Initial State) Operator Climb-Up-Ladder State 2 Robot (pos = Next-to-Ladder) is False Robot (pos = Next-to-Ceiling) is True (from the assertions of the operator) Dry(Ladder) is True (from State 1) Operator Paint Ceiling State 3 Robot (pos = Next-to-Ladder) is False Robot (pos = Next-to-Ceiling) is True Dry(Ladder) is True (from State 2) Painted(Ceiling) is True Dry(Ceiling) is False (from the assertions of the operator) Operator Climb-Down-Ladder State 4 Robot (pos = Next-to-Ladder) is True Robot (pos = Next-to-Ceiling) is False (from the assertions of the operator) Dry(Ladder) is True Painted(Ceiling) is True Dry(Ceiling) is False (from State 3) Operator Paint-Ladder State 5 Painted(Ladder) is True Dry(Ladder) is False (from the assertions of the operator) Robot (pos = Next-to-Ladder) is True Robot (pos = Next-to-Ceiling) is False Painted(Ceiling) is True Dry(Ceiling) is False (from State 4) Goal State Painted(Ladder) is True Painted(Ceiling) is True State 5 matches Goal State in that the assertations that need to be True in Goal State indeed are True in State 5, and there are no contradictions. Postconditions help in selection of operators. Operator retrieval: Match Postconditions (assertions that become True) Preconditions lead to goal decomposition. Preconditions are achieved by application of operators (plans) that result in the needed assertions becoming True. Crtics resolve interactions between subgoals and subplans. They contain "meta-planning" knowledge. %---------------------------------------------------------------------------- Copyright (c) Ashok Goel, 1994-97 College of Computing, Georgia Institute of Technology, Atlanta, Georgia 30332-0280 %----------------------------------------------------------------------------