Planning Graphs in AI

Planning graphs play a vital role in AI planning by visually representing possible states and actions that aid in decision-making. This article explores STRIP-like domains that construct and analyze the compact structure called graph planning. We will also delve into the role of mutual exclusion, providing a suitable example using a graph planning algorithm.

A Planning Graph is a data structure primarily used in automated planning and artificial intelligence to find solutions to planning problems. It represents a planning problem’s progression through a series of levels that describe states of the world and the actions that can be taken. Here’s a breakdown of its main components and how it functions:

1. Levels: A Planning graph has two alternating types of levels: action levels and state levels. The first level is always a state level, representing the initial state of the planning problem.
2. State Levels: These levels consist of nodes representing logical propositions or facts about the world. Each successive state level contains all the propositions of the previous level plus any that can be derived by the actions of the intervening action levels.
3. Action Levels: These levels contain nodes representing actions. An action node connects to a state level if the state contains all the preconditions necessary for that action. Actions in turn can create new state conditions, influencing the subsequent state level.
4. Edges: The graph has two types of edges: one connecting state nodes to action nodes (indicating that the state meets the preconditions for the action), and another connecting action nodes to state nodes (indicating the effects of the action).
5. Mutual Exclusion (Mutex) Relationships: At each level, certain pairs of actions or states might be mutually exclusive, meaning they cannot coexist or occur together due to conflicting conditions or effects. These mutex relationships are critical for reducing the complexity of the planning problem by limiting the combinations of actions and states that need to be considered.

• Level S₀: It is the initial state of the planning graph that consists of nodes each representing the state or conditions that can be true.
• Level A₀: Level A₀ consists of nodes that are responsible for taking all specific actions in terms of the initial condition described in the S₀.
  • S_i: It represents the state or condition which could hold at a time i, it may be both P and ¬P.
  • A_i: It contains the actions that could have their preconditions satisfied at i.

The planning graph has a single proposition level that contains all the initial conditions. The planning graph runs in stages, each stage and its key workings are described below:

1. Extending the Planning Graph: At stage i (the current level), the graph plan takes the planning graph from stage i-1 (the previous stage) and extends it by one time step. This adds the next action level representing all possible actions given the propositions (states) in the previous level, followed by the proposition level representing the resulting states after actions have been performed.
2. Valid Plan Found: If the graph plan finds a valid plan, it halts the planning process.
3. Proceeding to the Next Stage: If no valid plan is found, the algorithm determines that the goals are not all achievable in time i and moves to the next stage.

Mutual exclusion in graph planning refers to the principle that certain actions or propositions cannot coexist or occur simultaneously due to inherent constraints or dependencies within the planning problem. Mutex relations can hold between actions and literals under various conditions.

Mutex Conditions Between Actions

• Inconsistent Effects: One action negates the effect of another.
• Interference: One action deletes a precondition or creates an add-effect of another.
• Competing Needs: Precondition of action a and precondition of action b cannot be true simultaneously.

Mutex Conditions Between Literals

• Negation of Each Other: Two literals are mutually exclusive if one is the negation of the other.
• Achieved by Mutually Exclusive Actions: No pair of non-mutex actions can make both literals true at the same level.

To understand the concept of planning a graph, let’s use the CAKE example. This illustration demonstrates various states and actions to achieve the goal of successfully eating the cake. By examining these states, we can see how actions transition from one state to another to reach the desired outcome.

Initial State (S0)

• Have(Cake): We have the cake.
• ¬Eaten(Cake): The cake has not been eaten yet.

Action Level (A0)

The action level represents possible actions that can transition the state from S0 to the next state. In our example, the available action is:

• Eat(Cake): Represents the action to eat the cake.

Next State (S1)

The next state is determined by the action taken at the action level based on the propositional variables. In the CAKE example, we have four propositional variables in the next state:

• Have(Cake): If no action is performed (no-op), we will still have the cake.
• ¬Have(Cake): If the action Eat(Cake) is performed, we will no longer have the cake.
• Eaten(Cake): If the action Eat(Cake) is performed, the cake will have been eaten.
• ¬Eaten(Cake): If no action is performed (no-op), the cake will still be uneaten.

Performance of Mutual Exclusion in Planning Graph

At state level S1, all literals are obtained by considering any subset of actions at A0. In simple terms, state level S1 holds all possible outcomes after the actions in A0 are considered. In our example, since we only have the Eat(Cake) action at A0, S1 will list all possible outcomes with and without the action being taken.

Mutual Exclusion

Mutual exclusion occurs when a conflict arises between literals, indicating that the two literals cannot occur together. These conflicts are represented by mutex links, which reveal mutually exclusive propositions in S1.

For instance, if we eat the cake, we cannot have the cake at the same time. Thus, Have(Cake) and Eaten(Cake) would be mutually exclusive. The mutex links define the set of states, revealing which combinations of literals are not possible together.

For example:

• If Eat(Cake) is performed, Have(Cake) and ¬Eaten(Cake) cannot be true simultaneously.
• If Eat(Cake) is not performed, ¬Have(Cake) and Eaten(Cake) cannot be true together.

Second Action Level (A1) and State Level (S2)

Continuing from the above example, we introduce two more levels: Action-level (A1) and State-level (S2).

Actions Available at A1 from S1

• Bake(Cake): The precondition for this action is ¬Have(Cake). If ¬Have(Cake) is true in S1, applying Bake(Cake) results in Have(Cake) in S2. This action does not affect the Eaten(Cake) or ¬Eaten(Cake) states.
• Eat(Cake): The precondition for this action is Have(Cake). If Have(Cake) is true in S1, applying Eat(Cake) results in ¬Have(Cake) and Eaten(Cake) in S2.

1. Expand the Planning Graph: The graph is expanded level by level until it reaches level n where all the goals are present and non-mutex.
2. Check for Plan Existence: If the planning graph levels off before all goals are present and non-mutex, the algorithm fails.
3. Search for Valid Plan: The algorithm performs a back search from the last level to the initial state to find a sequence of actions leading to the goals without violating mutex constraints.
4. Expand if No Valid Plan Found: If no valid plan is found, another level is added and the search is repeated until a plan is found or the graph levels off.

function GRAPHPLAN(problem) returns solution or failure
       graph ← INITIAL-PLANNING-GRAPH(problem)
       goals  ← CONJUCTIONS(problems.GOAL)
       loop do
             if goals all non-mutex in last level of graph then do
                    solution ← EXTRACT-SOLUTION(graph, goals, NUMLEVELS(graph)
                    if solution ≠ failure then return solution
                    else if NO-SOLUTION-POSSIBLE(graph) then return failure
             graph ← EXPAND-GRAPH(graph, problem)

The elements in the planning graph are described as increasing or decreasing monotonically:

• Literals Increase Monotonically
• Actions Increase Monotonically
• Mutexes Decrease Monotonically

Due to these properties, the presence of a finite number of actions and literals enables the planning graph to eventually level off.

The graph plan algorithm leverages planning graphs to systematically explore and resolve planning problems. By incorporating mutual exclusion principles, it ensures consistency and feasibility. Through the CAKE example, we have demonstrated how planning graphs efficiently handle complex scenarios.